Summary-Based context-sensitive data-dependence analysis in presence of callbacks

Hao Tang, Xiaoyin Wang, Lingming Zhang, Bing Xie, Lu Zhang, Hong Mei

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Building a summary for library code is a common approach to speeding up the analysis of client code. In presence of callbacks, some reachability relationships between library nodes cannot be obtained during library-code summarization. Thus, the library code may have to be analyzed again during the analysis of the client code with the library summary. In this paper, we propose to summarize library code with tree-adjoining-language (TAL) reachability. Compared with the summary built with context-freelanguage (CFL) reachability, the summary built with TAL reachability further contains conditional reachability relationships. The conditional reachability relationships can lead to much lighter analysis of the library code during the client code analysis with the TAL-reachability-based library summary. We also performed an experimental comparison of context-sensitive datadependence analysis with the TAL-reachability-based library summary and context-sensitive data-dependence analysis with the CFLreachability- based library summary using 15 benchmark subjects. Our experimental results demonstrate that the former has an 8X speed-up over the latter on average.

Original languageEnglish (US)
Title of host publicationPOPL 2015 - Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
PublisherAssociation for Computing Machinery
Pages83-95
Number of pages13
ISBN (Electronic)9781450333009
DOIs
StatePublished - Jan 14 2015
Externally publishedYes
Event42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015 - Mumbai, India
Duration: Jan 12 2015Jan 18 2015

Publication series

NameConference Record of the Annual ACM Symposium on Principles of Programming Languages
Volume2015-January
ISSN (Print)0730-8566

Other

Other42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015
Country/TerritoryIndia
CityMumbai
Period1/12/151/18/15

Keywords

  • CFL reachability
  • Context-sensitive analysis
  • Summary-based analysis
  • TAL reachability
  • Tree adjoining languages

ASJC Scopus subject areas

  • Software

Cite this