Speeding up slicing

ABSTRACT

Program slicing is a fundamental operation for many software engineering tools. Currently, the most efficient algorithm for interprocedural slicing is one that uses a program representation called the system dependence graph. This paper defines a new algorithm for slicing with system dependence graphs that is asymptotically faster than the previous one. A preliminary experimental study indicates that the new algorithm is also significantly faster in practice, providing roughly a 6-fold speedup on examples of 348 to 757 lines.

REFERENCES

• 1: Hiralal Agrawal, On slicing programs with jump statements, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.302-312, June 20-24, 1994, Orlando, Florida, United States
• 2: Thomas Ball , Susan Horwitz, Slicing Programs with Arbitrary Control-flow, Proceedings of the First International Workshop on Automated and Algorithmic Debugging, p.206-222, May 03-05, 1993
• 3: Utpal Banerjee, Speedup of ordinary programs, 1979
• 4: Samuel Bates , Susan Horwitz, Incremental program testing using program dependence graphs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.384-396, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158694]
• 5: David Wendell Binkley, Multi-procedure program integration, University of Wisconsin at Madison, Madison, WI, 1992
• 6: Binkley, D., "Using semantic differencing to reduce the cost of regression testing," Proceedings of the 1992 Conference on Software Maintenance (Orlando, Florida), pp. 41-50 (November 9-12, 1992).
• 7: David Binkley, Interprocedural Constant Propagation using Dependence Graphs and a Data-Flow Model, Proceedings of the 5th International Conference on Compiler Construction, p.374-388, April 07-09, 1994
• 8: David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, ACM SIGPLAN Notices, v.25 n.6, p.296-310, Jun. 1990
• 9: Jong-Deok Choi , Jeanne Ferrante, Static slicing in the presence of goto statements, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.4, p.1097-1113, July 1994 [doi>10.1145/183432.183438]
• 10: 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]
• 11: Gina Goff , Ken Kennedy , Chau-Wen Tseng, Practical dependence testing, ACM SIGPLAN Notices, v.26 n.6, p.15-29, June 1991
• 12: S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, ACM SIGPLAN Notices, v.24 n.7, p.28-40, July 1989
• 13: Susan Horwitz , Jan Prins , Thomas Reps, Integrating noninterfering versions of programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.345-387, July 1989 [doi>10.1145/65979.65980]
• 14: 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]
• 15: Susan Horwitz, Identifying the semantic and textual differences between two versions of a program, ACM SIGPLAN Notices, v.25 n.6, p.234-245, Jun. 1990
• 16: Hwang, J.C., Du, M.W., and Chou, C. R., "Finding program slices for recursive procedures," in Proceedings of IEEE COMPSAC 88, (Chicago, IL, Oct. 3-7, 1988), IEEE Computer Society, Washington, DC (1988).
• 17: Brian W. Kernighan , P. J. Plauger, Software Tools in Pascal, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1981
• 18: Arun Lakhotia, Constructing call multigraphs using dependence graphs, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.273-284, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158647]
• 19: William Landi , Barbara G. Ryder, Pointer-induced aliasing: a problem taxonomy, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-103, January 21-23, 1991, Orlando, Florida, United States [doi>10.1145/99583.99599]
• 20: J. R. Larus , P. N. Hilfinger, Detecting conflicts between structure accesses, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.24-31, June 20-24, 1988, Atlanta, Georgia, United States
• 21: Dror E. Maydan , John L. Hennessy , Monica S. Lam, Efficient and exact data dependence analysis, ACM SIGPLAN Notices, v.26 n.6, p.1-14, June 1991
• 22: 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
• 23: William Pugh, The Omega test: a fast and practical integer programming algorithm for dependence analysis, Proceedings of the 1991 ACM/IEEE conference on Supercomputing, p.4-13, November 18-22, 1991, Albuquerque, New Mexico, United States [doi>10.1145/125826.125848]
• 24: William Pugh , David Wonnacott, Eliminating false data dependences using the Omega test, ACM SIGPLAN Notices, v.27 n.7, p.140-151, July 1992
• 25: Sharir, M. and Pnueli, A., "Two approaches to interprocedural data flow analysis," pp. 189-233 in Program Flow Analysis: Theory and Applications, ed. S.S. Muchnick and N.D. Jones, Prentice-Hall, Englewood Cliffs, NJ (1981).
• 26: Weiser, M., "Program slicing," IEEE Transactions on Software Engineering SE-10(4) pp. 352-357 (July 1984).
• 27: Michael Joseph Wolfe, Optimizing supercompilers for supercomputers, 1982

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Programmer workbench**

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Enhancement**

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

General Terms:
Algorithms, Performance, Theory

Keywords:
dynamic programming, dynamic transitive closure, flow-sensitive summary information, program debugging, program dependence graph, program slicing, realizable path