Equivalence analysis: a general technique to improve the efficiency of data-flow analyses in the presence of pointers

ABSTRACT

Existing methods to handle pointer variables during data-flow analyses can make such analyses inefficient both in time and space because the data-flow analyses must store and propagate large sets of data facts that are introduced by dereferences of pointer variable. This paper presents equivalence analysis, a general technique to improve the efficiency of data-flow analyses in the presence of pointers. The technique identifies equivalence relations among the memory locations accessed by a procedure and ensures that two equivalent memory locations share the same set of data facts in a procedure and in the procedures that are called by that procedure. Thus, a data-flow analysis needs to compute the data-flow information only for a representative memory location in an equivalence class. The data-flow information for other memory locations in the equivalence class can be derived from that of the representative memory location. Our empirical studies indicate that equivalence analysis may effectively improve the efficiency of many data-flow analyses.

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: Jong-Deok Choi , R. Cytron , J. Ferrante, On the Efficient Engineering of Ambitious Program Analysis, IEEE Transactions on Software Engineering, v.20 n.2, p.105-114, February 1994 [doi>10.1109/32.265631]
• 4: R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States [doi>10.1145/75277.75280]
• 5: Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Reducing the Cost of Data Flow Analysis By Congruence Partitioning, Proceedings of the 5th International Conference on Compiler Construction, p.357-373, April 07-09, 1994
• 6: Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
• 7: Programming Languages Research Group. PROLANGS Analysis Framework. http://www.proIangs.rutgers.edu/, Rutgers University, 1998.
• 8: 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
• 9: J. E. Hopcroft. An nlogn algorithm for minimizing states in finite automata. In Theory of Machines and Computations. Academic Press, 1971.
• 10: 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]
• 11: 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
• 12: W. A. Landi, B. G. Ryder, P. A. Stocks, S. Zhang, and R. Altucher. A schema for interprocedural modification side-effect analysis with pointer aliasing. Technical Report DCS-TR-336, Rutgers University, May 1998.
• 13: 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
• 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: 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]
• 16: Bjarne Steensgaard, Points-to Analysis by Type Inference of Programs with Structures and Unions, Proceedings of the 6th International Conference on Compiler Construction, p.136-150, April 24-26, 1996
• 17: 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]
• 18: Sean Zhang , Barbara G. Ryder , William Landi, Program decomposition for pointer aliasing: a step toward practical analyses, Proceedings of the 4th ACM SIGSOFT symposium on Foundations of software engineering, p.81-92, October 16-18, 1996, San Francisco, California, United States
• 19: Sean Zhang , Barbara G. Ryder , William A. Landi, Experiments with combined analysis for pointer aliasing, Proceedings of the 1998 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.11-18, June 16-16, 1998, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

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

Keywords:
alias analysis, data-flow analysis