Giga-Scale Exhaustive Points-To Analysis for Java in Under a Minute
Computing a precise points-to analysis for very large Java programs remains challenging despite the large body of research on points-to analysis. Any approach must solve an underlying context-free language reachability problem, for which the best algorithms are near-cubic in their worst-case runtime complexity, and, hence, previous work does not scale to programs with millions of lines of code.
In this work, we present a novel approach for solving the field-sensitive points-to problem for Java with the means of (1) a transitive-closure data-structure, and (2) a pre-computed set of potentially matching load/store pairs to accelerate the fixpoint calculation. Experimentation on Java benchmarks validates the superior performance of our approach over the standard context-free language reachability implementations. Our approach computes a points-to index for the OpenJDK with over 1.5 billion relations in under a minute.