> Research Papers > Analysis Analyzed

 : Tuesday

Demand-Driven Points-to Analysis for Java

We develop pointer analyses suitable for use highly time-constrained environments, such as just-in-time (JIT) compilers and interactive development environments (IDEs). In such environments, the running time of the analysis is critical, leading one to consider demand-driven solutions. In the worst case, however, a demand-driven analysis can take as long as an exhaustive analysis. For long-running queries, such environments could use early termination and simply stop the analysis after some timeout. Previous demand-driven pointer analyses do not perform well under such early termination constraints.

We formulate Andersen's analysis for Java as a CFL-reachability problem, and observe that it has the balanced-parentheses property seen in other program analysis problems. We use this observation to develop two new demand-driven pointer analysis algorithms, DemandFB and TargetedFS, that are suitable for use with early termination. DemandFB is an extremely simple field-based algorithm that essentially performs a depth-first search of the CFL-reachability graph. TargetedFS iteratively adds field-sensitivity to DemandFB where profitable, exploiting the balanced-parentheses structure for efficiency. We show that DemandFB is a very effective algorithm under early termination; for our clients, it can answer 89-94% of virtual call queries as precisely as an exhaustive field-sensitive Andersen's analysis, with each query taking less than 2ms. DemandFB can answer all queries in hot methods of javac with the same precision as an exhaustive field-sensitive Andersen's analysis, with a 34x speedup (and a 16x speedup over exhaustive field-based analysis). We also show that given a limited budget, TargetedFS is better than known demand-driven pointer analyses at closing the gap between DemandFB and exhaustive field-sensitive Andersen's.