TY - GEN
T1 - Summary-Based context-sensitive data-dependence analysis in presence of callbacks
AU - Tang, Hao
AU - Wang, Xiaoyin
AU - Zhang, Lingming
AU - Xie, Bing
AU - Zhang, Lu
AU - Mei, Hong
N1 - Publisher Copyright:
Copyright © 2015 by the Association for Computing Machinery, Inc. (ACM).
PY - 2015/1/14
Y1 - 2015/1/14
N2 - 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.
AB - 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.
KW - CFL reachability
KW - Context-sensitive analysis
KW - Summary-based analysis
KW - TAL reachability
KW - Tree adjoining languages
UR - http://www.scopus.com/inward/record.url?scp=84939494752&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84939494752&partnerID=8YFLogxK
U2 - 10.1145/2676726.2676997
DO - 10.1145/2676726.2676997
M3 - Conference contribution
AN - SCOPUS:84939494752
T3 - Conference Record of the Annual ACM Symposium on Principles of Programming Languages
SP - 83
EP - 95
BT - POPL 2015 - Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
PB - Association for Computing Machinery
T2 - 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2015
Y2 - 12 January 2015 through 18 January 2015
ER -