Equivalence analysis and its application in improving the efficiency of program slicing

ABSTRACT

Existing methods for handling pointer variables during dataflow analyses can make such analyses inefficient in both time and space because the data-flow analyses must store and propagate large sets of data facts that are introduced by dereferences of pointer variables. This article presents equivalence analysis, a general technique to improve the efficiency of data-flow analyses in the presence of pointer variables. 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 for only 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. The article also shows the extension to an interprocedural slicing algorithm that uses equivalence analysis to improve the efficiency of the algorithm. Our empirical studies suggest that equivalence analysis may effectively improve the efficiency of many data-flow analyses.

REFERENCES

• 1: Andersen, L. O. 1994. Program analysis and specialization for the C programming language. Tech. Rep. 94-19, University of Copenhagen.
• 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: Darren C. Atkinson , William G. Griswold, The design of whole-program analysis tools, Proceedings of the 18th international conference on Software engineering, p.16-27, March 25-29, 1996, Berlin, Germany
• 4: Jean-Francois Bergeretti , Bernard A. Carré, Information-flow and data-flow analysis of while-programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.37-61, Jan. 1985 [doi>10.1145/2363.2366]
• 5: 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]
• 6: 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]
• 7: 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
• 8: 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
• 9: Keith Brian Gallagher , James R. Lyle, Using Program Slicing in Software Maintenance, IEEE Transactions on Software Engineering, v.17 n.8, p.751-761, August 1991 [doi>10.1109/32.83912]
• 10: Rakesh Ghiya , Laurie J. Hendren, Putting pointer analysis to work, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.121-133, January 19-21, 1998, San Diego, California, United States [doi>10.1145/268946.268957]
• 11: Gupta, R., Harrold, M. J., and Soffa, M. L. 1992. An approach to regression testing using slicing. In Proceedings of the Conference on Software Maintenance---1992. (Nov.), 299--308.
• 12: 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
• 13: Michael Hind , Anthony Pioli, Which pointer analysis should I use?, Proceedings of the 2000 ACM SIGSOFT international symposium on Software testing and analysis, p.113-123, August 21-24, 2000, Portland, Oregon, United States
• 14: Hopcroft, J. E. 1971. An nlogn algorithm for minimizing states in finite automata. In Theory of Machines and Computations. Academic, New York.
• 15: 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]
• 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: 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
• 18: 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
• 19: Karl J. Ottenstein , Linda M. Ottenstein, The program dependence graph in a software development environment, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.177-184, April 1984
• 20: Programming Languages Research Group. 1998. PROLANGS analysis framework Rutgers University. Available at http://www.prolangs.rutgers.edu.
• 21: T. Reps , T. Bricker, Illustrating interference in interfering versions of programs, Proceedings of the 2nd International Workshop on Software configuration management, p.46-55, October 24-27, 1989, Princeton, New Jersey, United States
• 22: 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
• 23: Barbara G. Ryder , William A. Landi , Philip A. Stocks , Sean Zhang , Rita Altucher, A schema for interprocedural modification side-effect analysis with pointer aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.2, p.105-186, March 2001 [doi>10.1145/383043.381532]
• 24: 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
• 25: 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]
• 26: 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
• 27: 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]
• 28: Weiser, M. 1984. Program slicing. IEEE Trans. Softw. Eng. 10, 4 (July), 352--357.
• 29: 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
• 30: 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
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Algorithms, Performance, Theory, Verification

Keywords:
Alias analysis, data-flow analysis, program slicing