Rethinking Incremental and Parallel Pointer Analysis

Pointer analysisis at the heart of most interprocedural program analyses. However, scaling pointer analysisto large programs is extremely challenging. In this article, we study incremental pointer analysisand present a new algorithm for computing the points-to information incrementally(i.e., upon code insertion, deletion, and modification). Underpinned by new observations of incremental pointer analysis, our algorithmsignificantly advances the state of the art in that it avoids redundant computations and the expensive graph reachability analysis, and preserves precision as the corresponding whole program exhaustive analysis. Moreover, it is parallel within each iteration of fixed-point computation. We have implemented our algorithm, IPA, for Java based on the WALA framework and evaluated its performance extensively on real-world large, complex applications. Experimental results show that IPA achieves more than 200X speedups over existing incrementalalgorithms, two to five orders of magnitude faster than whole program pointer analysis, and also improves the performance of an incrementaldata race detector by orders of magnitude. Our IPA implementation is open source and has been adopted by WALA.