Aliasing analysis for a million lines of C

ABSTRACT

We will describe the design and implementation of a fast points-to analysis system. On some industrial code bases (about a million lines of unpreprocessed C code) this system performs context-insensitive field-based Andersen-style points-to analysis in less than a second and uses less than 10MB of memory. The two main contributions of the work are a database-centric analysis architecture called compile-link-analyze (CLA), and a new graph-based algorithm for implementing a form of dynamic transitive closure. An open source release of our system should be available soon.

REFERENCES

• 1: L. Andersen, "Program Analysis and Specialization for the C Programming Language", PhD. thesis, DIKU report 94/19, 1994.
• 2: Satish Chandra , Thomas Reps, Physical type checking for C, Proceedings of the 1999 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.66-75, September 06-06, 1999, Toulouse, France
• 3: Manuvir Das, Unification-based pointer analysis with directional assignments, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.35-46, June 18-21, 2000, Vancouver, British Columbia, Canada
• 4: Jeffrey S. Foster , Manuel Fahndrich , Alexander Aiken, Flow-Insensitive Points-to Analysis with Term and Set Constraints, University of California at Berkeley, Berkeley, CA, 1997
• 5: Manuel Fähndrich , Jeffrey S. Foster , Zhendong Su , Alexander Aiken, Partial online cycle elimination in inclusion constraint graphs, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.85-96, June 17-19, 1998, Montreal, Quebec, Canada
• 6: N. Heintze, "Analysis of Large Code Bases: The Compile-Link-Analyze Model" unpublished report, November 1999.
• 7: Nevin Heintze , Olivier Tardieu, Ultra-fast aliasing analysis using CLA: a million lines of C code in a second, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.254-263, June 2001, Snowbird, Utah, United States
• 8: "Programming Languages - C", ISO/IEC 9899:1990, International Standard, 1990.
• 9: Atanas Rountev , Satish Chandra, Off-line variable substitution for scaling points-to analysis, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.47-56, June 18-21, 2000, Vancouver, British Columbia, Canada
• 10: Marc Shapiro , Susan Horwitz, Fast and accurate flow-insensitive points-to analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-14, January 15-17, 1997, Paris, France [doi>10.1145/263699.263703]
• 11: Zhendong Su , Manuel Fähndrich , Alexander Aiken, Projection merging: reducing redundancies in inclusion constraint graphs, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.81-95, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325706]
• 12: Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237727]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Languages, Performance

Keywords:
C, aliasing analysis, dependence analysis, narrowing conversion errors, points-to analysis, scalable program analysis