Indexing the extended Dyck-CFL reachability for context-sensitive program analysis
Open Access
- 31 October 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 6 (OOPSLA2) , 1438-1468
Abstract
Many context-sensitive dataflow analyses can be formulated as an extended Dyck-CFL reachability problem, where function calls and returns are modeled as partially matched parentheses. Unfortunately, despite many works on the standard Dyck-CFL reachability problem, solving the extended version is still of quadratic space complexity and nearly cubic time complexity, significantly limiting the scalability of program analyses. This paper, for the first time to the best of our knowledge, presents a cheap approach to transforming the extended Dyck-CFL reachability problem to conventional graph reachability, a much easier and well-studied problem. This transformation allows us to benefit from recent advances in reachability indexing schemes, making it possible to answer any reachability query in a context-sensitive dataflow analysis within almost constant time plus only a few extra spaces. We have implemented our approach in two common context-sensitive dataflow analyses, one determines pointer alias relations and the other tracks information flows. Experimental results demonstrate that, compared to their original analyses, we can achieve orders of magnitude (10 2 × to 10 5 ×) speedup at the cost of only a moderate space overhead. Our implementation is publicly available.Keywords
This publication has 83 references indexed in Scilit:
- Path-treeACM Transactions on Database Systems, 2011
- Analysis of recursive state machinesACM Transactions on Programming Languages and Systems, 2005
- Interconvertibility of a class of set constraints and context-free-language reachabilityTheoretical Computer Science, 2000
- SPEC CPU2000: measuring CPU performance in the New MillenniumComputer, 2000
- Undecidability of context-sensitive data-dependence analysisACM Transactions on Programming Languages and Systems, 2000
- Program analysis via graph reachabilityInformation and Software Technology, 1998
- On the calculation of transitive reduction—closure of ordersDiscrete Mathematics, 1993
- The program dependence graph and its use in optimizationACM Transactions on Programming Languages and Systems, 1987
- Ubiquitous B-TreeACM Computing Surveys, 1979
- Recognition and parsing of context-free languages in time n3Information and Control, 1967