Making Context-Sensitive Points-to Analysis with Heap Cloning
Practical For The Real World
Abstract:
Context-sensitive pointer analysis algorithms with full "heap
cloning" 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 full
heap 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 lines
of 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-based
analysis, 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(N2) 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 3x-21x
in our ten largest programs, and that the savings grow strongly
with program size.
Finally, we briefly summarize results demonstrating the precision of the
analysis.
Published:
"Making Context-Sensitive Points-to Analysis with Heap Cloning
Practical For The Real World"
Chris Lattner, Andrew Lenharth, and Vikram Adve.
Proc. of the 2007 ACM SIGPLAN Conference on Programming Language
Design and Implementation (PLDI'07), San Diego, CA, Jun, 2007.
Download:
Paper:
Slides:
BibTeX Entry:
@InProceedings{DSA:PLDI07,
author = {Chris Lattner and Andrew Lenharth and Vikram Adve},
title = "{Making Context-Sensitive Points-to Analysis with Heap Cloning Practical For The Real World}",
booktitle = "{Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'07)}",
address = {San Diego, California},
month = {June},
year = {2007}
}
