Nevin Heintze
ABSTRACT
We describe the design and implementation of a system for very fast points-to analysis. On code bases of about million lines of unpreprocessed C code, our system performs field-based Andersen-style points-to analysis in less than a second and uses less than 10MB of memory. Our two main contributions are a database-centric analysis architecture called compile-link-analyze (CLA), and a new algorithm for implementing dynamic transitive closure. Our points-to analysis system is built into a forward data-dependence analysis tool that is deployed within Lucent to help with consistent type modifications to large legacy C code bases.
- 1.A. Aiken, M. F. ahndrich, J. Foster, and Z. Su, "A Toolkit for Constructing Type- and Constraint-Based Program Analyses", TIC'98.]] Google Scholar
Digital Library
- 2.A. Aiken and E. Wimmers, "Solving Systems of Set Constraints", LICS, 1992.]]Google ScholarCross Ref
- 3.A. Aiken and E. Wimmers, "Type Inclusion Constraints and Type Inference", ICFP, 1993.]] Google ScholarDigital Library
- 4.L. Andersen, "Program Analysis and Specialization for the C Programming Language", PhD. thesis, DIKU report 94/19, 1994,]]Google Scholar
- 5.D. Atkinson and W. Griswold, "Effective Whole-Program Analysis in the Presence of Pointers", 1998 Symp. on the Foundations of Soft. Eng..]] Google ScholarDigital Library
- 6.S. Chandra, N. Heintze, D. MacQueen, D. Oliva and M. Siff, "ckit: an extensible C frontend in ML",to be released as an SML/NJ library.]]Google Scholar
- 7.S. Chandra and T. Reps, "Physical Type Checking for C" PASTE, 1999.]] Google ScholarDigital Library
- 8.M. Das, "Unification-Based Pointer Analysis with Directional Assignments" PLDI, 2000.]] Google ScholarDigital Library
- 9."Appendix D: Optimizing Techniques (MIPS-Based C Compiler)", Programmer's Guide: Digital UNIX Version 4.0, Digital Equipment Corporation, March 1996.]]Google Scholar
- 10.J. Foster, M. F.ahndrich and A. Aiken, "Flow-Insensitive Points-to Analysis with Term and Set Constraints" U. of California, Berkeley, UCB//CSD97964, 1997.]] Google ScholarDigital Library
- 11.M. F.ahndrich, J. Foster, Z. Su and A. Aiken, "Partial Online Cycle Elimination in Inclusion Constraint Graphs" PLDI, 1998.]] Google ScholarDigital Library
- 12.C. Flanagan and M. Felleisen, "Componential Set-Based Analysis" PLDI, 1997.]] Google ScholarDigital Library
- 13.J. Foster, M. F. ahndrich and A. Aiken, "Polymorphic versus Monomorphic Flow-insensitive Points-to Analysis for C", SAS 2000.]] Google ScholarDigital Library
- 14.N. Heintze, "Set Based Program Analysis", PhD thesis, Carnegie Mellon University, 1992.]] Google ScholarDigital Library
- 15.N. Heintze, "Set-Based Analysis of ML Programs", LFP, 1994.]] Google ScholarDigital Library
- 16.N. Heintze, "Analysis of Large Code Bases: The Compile-Link-Analyze Model" unpublished report, November 1999.]]Google Scholar
- 17.N. Heintze and J. Jaffar, "A decision procedure for a class of Herbrand set constraints" LICS, 1990.]]Google Scholar
- 18.N. Heintze and D. McAllester, "On the Cubic-Bottleneck of Subtyping and Flow Analysis" LICS, 1997.]] Google ScholarDigital Library
- 19."Programming Languages - C", ISO/IEC 9899:1990, Internation Standard, 1990.]]Google Scholar
- 20.D. McAllester, "On the Complexity Analysis of Static Analysis", SAS, 1999.]] Google ScholarDigital Library
- 21.A. Rountev and S. Chandra, "Off-line Variable Substitution for Scaling Points-to Analysis", PLDI, 2000.]] Google ScholarDigital Library
- 22.M. Shapiro and S. Horwitz, "Fast and Accurate Flow-Insensitive Points-To Analysis", POPL, 1997.]] Google ScholarDigital Library
- 23.Z. Su, M. F. ahndrich, and A. Aiken, "Projection Merging: Reducing Redundancies in Inclusion Constraint Graphs", POPL, 2000.]] Google ScholarDigital Library
- 24.B. Steensgaard, "Points-to Analysis in Almost Linear Time", POPL, 1996.]] Google ScholarDigital Library
- 25.F. Tip, "Generation of Program Analysis Tools", Institute for Logic Language and Computation dissertation series, 1995-5, 1995.]]Google Scholar
Index Terms
- Ultra-fast aliasing analysis using CLA: a million lines of C code in a second
Recommendations
Ultra-fast aliasing analysis using CLA: a million lines of C code in a second
We describe the design and implementation of a system for very fast points-to analysis. On code bases of about million lines of unpreprocessed C code, our system performs field-based Andersen-style points-to analysis in less than a second and uses less ...
Program decomposition for pointer aliasing: a step toward practical analyses
Pointer aliasing analysis is crucial to compile-time analyses for languages with general-purpose pointer usage (such as C), but many aliasing methods have proven quite costly. We present a technique that partitions the statements of a program to allow ...
Comments