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

Content Provider	ACM Digital Library
Author	Adve, Vikram Lenharth, Andrew Lattner, Chris
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.
Starting Page	278
Ending Page	289
Page Count	12
File Format	PDF
ISSN	03621340 15581160
DOI	10.1145/1273442.1250766
Journal	ACM SIGPLAN Notices (SIGP)
Volume Number	42
Issue Number	6
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1983-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Context-sensitive Field-sensitive Pointer analysis Static analysis Recursive data structure Interprocedural
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

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

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

Context-sensitive interprocedural points-to analysis in the presence of function pointers

Cloning-based context-sensitive pointer alias analysis using binary decision diagrams

Automatic pool allocation:improving performance by controlling data structure layout in the heap

Practical Techniques For Interprocedural Heap Analysis (1996)

Connection Analysis: A Practical Interprocedural Heap Analysis for C (1995)

Efficient context-sensitive pointer analysis for C programs

Interprocedural compatibility analysis for static object preallocation

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

Similar Documents

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

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

Context-sensitive interprocedural points-to analysis in the presence of function pointers

Cloning-based context-sensitive pointer alias analysis using binary decision diagrams

Automatic pool allocation:improving performance by controlling data structure layout in the heap

Practical Techniques For Interprocedural Heap Analysis (1996)

Connection Analysis: A Practical Interprocedural Heap Analysis for C (1995)

Efficient context-sensitive pointer analysis for C programs

Interprocedural compatibility analysis for static object preallocation

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