Light-weight context recovery for efficient and accurate program analyses

ABSTRACT

To compute accurate information efficiently for programs that use pointer variables, a program analysis must account for the fact that a procedure may access different sets of memory locations when the procedure is invoked under different callsites. This paper presents light-weight context recovery, a technique that can efficiently determine whether a memory location is accessed by a procedure under a specific callsite. The paper also presents a technique that uses this information to improve the precision and efficiency of program analyses. Our empirical studies show that (1) light-weight context recovery can be quite precise in identifying the memory locations accessed by a procedure under a specific call-site and (2) distinguishing memory locations accessed by a procedure under different callsites can significantly improve the precision and the efficiency of program analyses on programs that use pointer variables.

REFERENCES

• 1: L.O. Andersen. Program analysis and specialization for the C programming language. Technical Report 94-19, University of Copenhagen, 1994.
• 2: Darren C. Atkinson , William G. Griswold, Effective whole-program analysis in the presence of pointers, Proceedings of the 6th ACM SIGSOFT international symposium on Foundations of software engineering, p.46-55, November 01-05, 1998, Lake Buena Vista, Florida, United States
• 3: Programming Languages Research Group. PROLANGS Analysis Framework. Rutgers University, http://www.prolangs.rutgers.edu/, 1998.
• 4: David Grove , Greg DeFouw , Jeffrey Dean , Craig Chambers, Call graph construction in object-oriented languages, Proceedings of the 12th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.108-124, October 05-09, 1997, Atlanta, Georgia, United States
• 5: Mary Jean Harrold , Ning Ci, Reuse-driven interprocedural slicing, Proceedings of the 20th international conference on Software engineering, p.74-83, April 19-25, 1998, Kyoto, Japan
• 6: Susan Horwitz , Thomas Reps , David Binkley, Interprocedural slicing using dependence graphs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.12 n.1, p.26-60, Jan. 1990 [doi>10.1145/77606.77608]
• 7: 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
• 8: William Landi , Barbara G. Ryder , Sean Zhang, Interprocedural modification side effect analysis with pointer aliasing, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.56-67, June 21-25, 1993, Albuquerque, New Mexico, United States
• 9: Donglin Liang , Mary Jean Harrold, Efficient points-to analysis for whole-program analysis, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.199-215, September 06-10, 1999, Toulouse, France
• 10: Donglin Liang , Mary Jean Harrold, Equivalence analysis: a general technique to improve the efficiency of data-flow analyses in the presence of pointers, Proceedings of the 1999 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.39-46, September 06-06, 1999, Toulouse, France
• 11: Donglin Liang , Mary Jean Harrold, Reuse-Driven Interprocedural Slicing in the Presence of Pointers and Recursions, Proceedings of the IEEE International Conference on Software Maintenance, p.421, August 30-September 03, 1999
• 12: H. D. Pande , W. A. Landi , B. G. Ryder, Interprocedural Def-Use Associations for C Systems with Single Level Pointers, IEEE Transactions on Software Engineering, v.20 n.5, p.385-403, May 1994 [doi>10.1109/32.286418]
• 13: Atanas Rountev , Barbara G. Ryder , William Landi, Data-flow analysis of program fragments, Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineering, p.235-252, September 06-10, 1999, Toulouse, France
• 14: Marc Shapiro, II , Susan Horwitz, The Effects of the Presision of Pointer Analysis, Proceedings of the 4th International Symposium on Static Analysis, p.16-34, September 08-10, 1997
• 15: M. Weiser. Program slicing. IEEE Trans. on Softw. Eng., 10(4):352{357, July 1984.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

General Terms:
Algorithms, Design, Measurement, Performance, Reliability, Theory

Keywords:
aliasing, program analysis, slicing