Demand-driven alias analysis for C

ABSTRACT

This paper presents a demand-driven, flow-insensitive analysisalgorithm for answering may-alias queries. We formulate thecomputation of alias queries as a CFL-reachability problem, and use this formulation to derive a demand-driven analysis algorithm. The analysis uses a worklist algorithm that gradually explores the program structure and stops as soon as enough evidence is gathered to answer the query. Unlike existing techniques, our approach does not require building or intersecting points-to sets.

Experiments show that our technique is effective at answering alias queries accurately and efficiently in a demand-driven fashion. For a set of alias queries from the SPEC2000 benchmarks, an implementation of our analysis is able to accurately answer 96% of the queries in 0.5 milliseconds per query on average, using only 65 KB of memory. Compared to a demand-driven points-to analysis that constructs and intersects points-to sets on the fly, our alias analysis can achieve better accuracy while running more than 30 times faster. The low run-time cost and low memory demands of the analysis make it a very good candidate not only for compilers, but also for interactive tools, such as program understanding tools or integrated development environments (IDEs).

REFERENCES

• 1: Rajeev Alur , Mihalis Yannakakis, Model checking of hierarchical state machines, Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, p.175-188, November 01-05, 1998, Lake Buena Vista, Florida, United States
• 2: Rajeev Alur , Kousha Etessami , Mihalis Yannakakis, Analysis of Recursive State Machines, Proceedings of the 13th International Conference on Computer Aided Verification, p.207-220, July 18-22, 2001
• 3: Lars Ole Andersen. Program Analysis and Specialization for the C Programming Language. PhD thesis, DIKU, University of Copenhagen, May 1994.
• 4: Michael Benedikt , Patrice Godefroid , Thomas W. Reps, Model Checking of Unrestricted Hierarchical State Machines, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.652-666, July 08-12, 2001
• 5: Jong-Deok Choi , Michael Burke , Paul Carini, Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.232-245, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158639]
• 6: Manuvir Das , Ben Liblit , Manuel Fähndrich , Jakob Rehof, Estimating the Impact of Scalable Pointer Analysis on Optimization, Proceedings of the 8th International Symposium on Static Analysis, p.260-278, July 16-18, 2001
• 7: 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
• 8: 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
• 9: Manuel Fähndrich , Jakob Rehof , Manuvir Das, Scalable context-sensitive flow analysis using instantiation constraints, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.253-263, June 18-21, 2000, Vancouver, British Columbia, Canada
• 10: Rakesh Ghiya , Daniel Lavery , David Sehr, On the importance of points-to analysis and other memory disambiguation methods for C programs, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.47-58, June 2001, Snowbird, Utah, United States
• 11: Nevin Heintze , Olivier Tardieu, Demand-driven pointer analysis, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.24-34, June 2001, Snowbird, Utah, United States
• 12: Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States [doi>10.1145/379605.379665]
• 13: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 14: John Kodumal , Alex Aiken, The set constraint/CFL reachability connection in practice, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 15: J. Kodumal and A. Aiken. Banshee: A scalable constraint-based analysis toolkit. In In Proceedings of the International Static Analysis Symposium, London, UK, September 2005.
• 16: William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.235-248, June 15-19, 1992, San Francisco, California, United States
• 17: Chris Lattner , Andrew Lenharth , Vikram Adve, Making context-sensitive points-to analysis with heap cloning practical for the real world, Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, June 10-13, 2007, San Diego, California, USA
• 18: Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.1-14, June 24-28, 1991, Toronto, Ontario, Canada
• 19: Thomas Reps , Susan Horwitz , Mooly Sagiv, Precise interprocedural dataflow analysis via graph reachability, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-61, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199462]
• 20: Thomas Reps, Program analysis via graph reachability, Proceedings of the 1997 international symposium on Logic programming, p.5-19, November 1997, Port Washington, New York, United States
• 21: R. Rugina, M. Orlovich, and X. Zheng. Crystal: A program analysis system for C. URL: http://www.cs.cornell.edu/projects/crystal.
• 22: Diptikalyan Saha , C. R. Ramakrishnan, Incremental and demand-driven points-to analysis using logic programming, Proceedings of the 7th ACM SIGPLAN international conference on Principles and practice of declarative programming, p.117-128, July 11-13, 2005, Lisbon, Portugal [doi>10.1145/1069774.1069785]
• 23: M. Sharir and A. Pnueli. Two approaches to interprocedural data flow analysis. In S. Muchnick and N.D. Jones, editors, Program Flow Analysis: Theory and Applications. Prentice Hall Inc, 1981.
• 24: Manu Sridharan , Rastislav Bodík, Refinement-based context-sensitive points-to analysis for Java, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 25: Manu Sridharan , Denis Gopan , Lexin Shan , Rastislav Bodík, Demand-driven points-to analysis for Java, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 26: 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

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Program analysis

General Terms:
Algorithms, Languages

Keywords:
CFL reachability, alias analysis, demand-driven analysis, memory disambiguation, pointer analysis