Making context-sensitive points-to analysis with heap cloning practical for the real world

Chris Lattner, Andrew Lenharth, Vikram Adve

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Context-sensitive pointer analysis algorithms with full "heapcloning" are powerful but are widely considered to be too expensive to include in production compilers. This paper shows, for the first time, that a context-sensitive, field-sensitive algorithm with fullheap cloning (by acyclic call paths) can indeed be both scalable and extremely fast in practice. Overall, the algorithm is able to analyze programs in the range of 100K-200K lines of C code in 1-3 seconds,takes less than 5% of the time it takes for GCC to compile the code (which includes no whole-program analysis), and scales well across five orders of magnitude of code size. It is also able to analyze the Linux kernel (about 355K linesof code) in 3.1 seconds. The paper describes the major algorithmic and engineering design choices that are required to achieve these results, including (a) using flow-insensitive and unification-basedanalysis, which are essential to avoid exponential behavior in practice;(b) sacrificing context-sensitivity within strongly connected components of the call graph; and (c) carefully eliminating several kinds of O(N 2) behaviors (largely without affecting precision). The techniques used for (b) and (c) eliminated several major bottlenecks to scalability, and both are generalizable to other context-sensitive algorithms. We show that the engineering choices collectively reduce analysis time by factors of up to 10x-15xin our larger programs, and have found that the savings grow strongly with program size. Finally, we briefly summarize results demonstrating the precision of the analysis.

Original languageEnglish (US)
Title of host publicationPLDI'07
Subtitle of host publicationProceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation
Pages278-289
Number of pages12
DOIs
StatePublished - Oct 30 2007
EventPLDI'07: 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation - San Diego, CA, United States
Duration: Jun 10 2007Jun 13 2007

Publication series

NameProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Other

OtherPLDI'07: 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation
CountryUnited States
CitySan Diego, CA
Period6/10/076/13/07

    Fingerprint

Keywords

  • Context-sensitive
  • Field-sensitive
  • Interprocedural
  • Pointer analysis
  • Recursive data structure
  • Static analysis

ASJC Scopus subject areas

  • Software

Cite this

Lattner, C., Lenharth, A., & Adve, V. (2007). Making context-sensitive points-to analysis with heap cloning practical for the real world. In PLDI'07: Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (pp. 278-289). (Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)). https://doi.org/10.1145/1250734.1250766