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\times$ to $10^5\times$) speedup at the cost of only a moderate space overhead.
Our implementation is publicly available.