Rethinking incremental and parallel pointer analysis

Bozhen Liu, Jeff Huang, Lawrence Rauchwerger

Research output: Contribution to journalArticle

Abstract

Pointer analysis is at the heart of most interprocedural program analyses.However, scaling pointer analysis to large programs is extremely challenging. In this article, we study incremental pointer analysis and 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 algorithm significantly 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 incremental algorithms, two to five orders of magnitude faster than whole program pointer analysis, and also improves the performance of an incremental data race detector by orders of magnitude. Our IPA implementation is open source and has been adopted by WALA.

Original languageEnglish (US)
Article number6
JournalACM Transactions on Programming Languages and Systems
Volume41
Issue number1
DOIs
StatePublished - Mar 2019
Externally publishedYes

Keywords

  • Dynamic graph algorithms
  • Incremental pointer analysis
  • Parallelization

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Rethinking incremental and parallel pointer analysis'. Together they form a unique fingerprint.

  • Cite this