Thomas Reps
Susan Horwitz
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.
- 1.Agrawal, H., "On slicing programs with jump statements," Proceedings of the ACM SIGPLAN 94 Conference on Programming Language Design and Implementation, (Orlando, FL, June 22-24, 1992), ACM SIGPLAN Notices 29(6) pp. 302-312 (June 1994). Google Scholar
Digital Library
- 2.Ball, T. and Horwitz, S., "Slicing programs with arbitrary control flow," pp. 206-222 in Proceedings of the First International Workshop on Automated and Algorithmic Debugging, (Linkoping, Sweden, May 1993), Lecture Notes in Computer Science, Vol. 749, Springer-Verlag, New York, NY (1993). Google ScholarDigital Library
- 3.Bannerjee, U., "Speedup of ordinary programs," Ph.D. dissertation and Tech. Rep. R-79-989, Dept. of Computer Science, University of Illinois, Urbana, IL (October 1979). Google ScholarDigital Library
- 4.Bates, S. and Horwitz, S., "Incremental program testing using program dependence graphs," pp. 384-396 in Conference Record of the Twentieth ACM Symposium on Principles of Programming Languages, (Charleston, SC, January 10-13, 1993), ACM, New York, NY (1993). Google ScholarDigital Library
- 5.Binkley, D., "Multi-procedure program integration," Ph.D. dissertation and Tech. Rep. TR- 1038, Computer Sciences Department, University of Wisconsin, Madison, WI (August 1991). Google ScholarDigital Library
- 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).Google Scholar
- 7.Binkley, D., "Interprocedural constant propagation using dependence graphs and a data-flow model," pp. 374-388 in Proceedings of the Fifth International Conference on Compiler Construction, (Edinburgh, U. K., April 7-9, 1994), Lecture Notes in Computer Science, Vol. 786, ed. PA. Fritzson, Springer-VerIag, New York, NY (1994). Google ScholarDigital Library
- 8.Chase, D. R., Wegman, M., and Zadeck, F.K., "Analysis of pointers and structures," Proceedings of the ACM SIGPLAN 90 Conference on Programming Language Design and Implementation, (White Plains, NY, June 20-22, 1990), ACM SIGPLAN Notices 25(6) pp. 296-310 (June 1990). Google ScholarDigital Library
- 9.Choi, J.-D. and Ferrante, J., "Static slicing in the presence of GOTO statements," ACM Letters on Programing Languages and Systems, (1994). Google ScholarDigital Library
- 10.Gallagher, K.B. and Lyle, J.R., "Using program slicing in software maintenance," IEEE Transactions on Software Engineering 17(8) pp. 751-761 (August 1991). Google ScholarDigital Library
- 11.Goff, G., Kennedy, K., and Tseng, C.-W., "Practical dependence testing," Proceedings of the ACM SIGPLAN 91 Conference on Programming Language Design and Implementation, (Toronto, Ontario, June 26-28, 1991), ACM SIGPLAN Notices 26(6) pp. 15-29 (June 1991). Google ScholarDigital Library
- 12.Horwitz, S., Pfeiffer, P., and Reps, T., "Dependence analysis for pointer variables," Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation, (Portland, OR, June 21-23, 1989), ACM SIGPLAN Notices 24(7) pp. 28-40 (July 1989). Google ScholarDigital Library
- 13.Horwitz, S., Prins, J., and Reps, T., "Integrating non-interfering versions of programs," ACM Trans. Program. Lang. Syst. 11(3) pp. 345-387 (July 1989). Google ScholarDigital Library
- 14.Horwitz, S., Reps, T., and Binkley, D., "Interprocedural slicing using dependence graphs," ACM Trans. Program. Lang. Syst. 12(1) pp. 26-60 (January 1990). Google ScholarDigital Library
- 15.Horwitz, S., "Identifying the semantic and textual differences between two versions of a program," Proceedings of the ACM SIGPLAN 90 Conference on Programming Language Design and Implementation, (White Plains, NY, June 20-22, 1990), ACM SIGPLAN Notices 25(6) pp. 234-245 (June 1990). Google ScholarDigital Library
- 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).Google Scholar
- 17.Kernighan, B. and Plauger, P., Software Took in Pascal, Addison- Wesley, Reading, MA (1981). Google ScholarDigital Library
- 18.Lakhotia, A., "Constructing call multigraphs using dependence graphs," pp. 273-284 in Conference Record of the Twentieth ACM Symposium on Principles of Programming Languages,(Charleston, SC, Jan. 11-13, 1993), ACM, New York, NY (1993). Google ScholarDigital Library
- 19.Landi, W. and Ryder, B. G., "Pointer-induced aliasing: A problem classification," pp. 93-103 in Conference Record of the Eighteenth ACM Symposium on Principles of Programming Languages, (Orlando, FL, January 1991), ACM, New York, NY (1991). Google ScholarDigital Library
- 20.Larus, J.R. and Hilfinger, P.N., "Detecting conflicts between structure accesses," Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, June 22-24, 1988), ACM SIGPLAN Notices 23(7) pp. 21-34 (July 1988). Google ScholarDigital Library
- 21.Maydan, D. E., Hennessy, J.L., and Lam, M. S., "Efficient and exact data dependence analysis," Proceedings of the ACM SIGPLAN 91 Conference on Programming Language Design and Implementation, (Toronto, Ontario, June 26-28, 1991), ACM SIGPLAN Notices 26(6) pp. 1-14 (June 1991). Google ScholarDigital Library
- 22.Ottenstein, K.J. and Ottenstein, L. M., "The program dependence graph in a software development environment," Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, (Pittsburgh, PA, Apr. 23-25, 1984), ACM SIGPLAN Notices 19(5) pp. 177-184 (May 1984). Google ScholarDigital Library
- 23.Pugh, W., "The omega test: a fast and pratical integer programming algorithm for dependence analysis," in Supercomputing 1991, (November 1991). Google ScholarDigital Library
- 24.Pugh, W. and Wonnacott, D., "Eliminating false data dependence using the omega test," Proceedings of the ACM SIGPLAN 92 Conference on Programming Language Design and Implementation, (San Francisco, CA, June 17-19, 1992), ACM SIGPLAN Notices 27(7) pp. 140-151 (July 1992). Google ScholarDigital Library
- 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).Google Scholar
- 26.Weiser, M., "Program slicing," IEEE Transactions on Software Engineering SE-10(4) pp. 352-357 (July 1984).Google ScholarDigital Library
- 27.Wolfe, M.J., "Optimizing supercompilers for supercomputers," Ph.D. dissertation and Tech. Rep. R-82-1105, Dept. of Computer Science, University of Illinois, Urbana, IL (October 1982). Google ScholarDigital Library
Index Terms
- Speeding up slicing
Recommendations
Speeding up slicing
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 ...
An efficient interprocedural dynamic slicing method
We present an efficient interprocedural dynamic slicing algorithm for structured programs. We first propose an intraprocedural dynamic slicing algorithm, and subsequently extend it to handle interprocedural calls. Our intraprocedural dynamic slicing ...
Precise executable interprocedural slices
The notion of a program slice, originally introduced by Mark Weiser, is useful in program debugging, automatic parallelization, program integration, and software maintenance. A slice of a program is taken with respect to a program point p and a variable ...
Comments