Hiralal Agrawal
ABSTRACT
Program slices have potential uses in many software engineering applications. Traditional slicing algorithms, however, do not work correctly on programs that contain explicit jump statements. Two similar algorithms were proposed recently to alleviate this problem. Both require the flowgraph and the program dependence graph of the program to be modified. In this paper, we propose an alternative algorithm that leaves these graphs intact and uses a separate graph to store the additional required information. We also show that this algorithm permits an extremely efficient, conservative adaptation for use with programs that contain only “structured” jump statements.
- 1.H. Agrawal, R. A. DeMillo, and E. H. Spafford. Debugging with dynamic slicing and backtracking. Software Practice and Experience, 23(6):589-616, june 1993. Google Scholar
Digital Library
- 2.H. Agrawal, J. R. Horgan, E. W. Krauser, and S. L. London. Incremental regression testing. In Proceedings of the IEEE Conference on Software Maintenance, pages 348-357. The IEEE Computer Society Press, Sept. 1993. Google ScholarDigital Library
- 3.A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Took. Addison- Wesley, 1986. Google ScholarDigital Library
- 4.B. S. Baker. An algorithm for structuring flowgraphs. Journal of the ACM, 24(1):98-120, Jan. 1977. Google ScholarDigital Library
- 5.T. Ball and S. Horwitz. Slicing programs with arbitrary control flow. In Proceedings of the 1st International Workshop on Automated and Algorithmic Debugging (Lecture Notes in Computer Science 7~9), pages 206-222. Springer-Verlag, Nov. 1993. Google ScholarDigital Library
- 6.J.-F. Bergeretti and B. A. CarrY. Information-flow and data-flow analysis of while programs. A CM Transactions on Programming Languages and Systems, 7(1):37-61, Jan. 1985. Google ScholarDigital Library
- 7.R. Cartwright and M. Felleisen. The semantics of program dependence. In Proceedings of the A CM SIGPLAN'89 Conference on Programming Language Design and Implementation. ACM Press, June 1989. SIGPLAN Notices, 24(7):13-27, July 1989. Google ScholarDigital Library
- 8.J.-D. Choi and J. Ferrante. Static slicing in the presence of GOTO statements. A CM Letters on Programming Languages and Systems, 1994. To appear. Google ScholarDigital Library
- 9.D. E. Denning and P. J. Denning. Certification of programs for secure information flow. Communications of the ACM, 20(7):504-513, July 1977. Google ScholarDigital Library
- 10.J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its uses in optimization. A CM Transactions on Programming Languages and Systems, 9(3):319-349, July 1987. Google ScholarDigital Library
- 11.K. B. Gallagher. Using Program Slicing for Program Maintenance. PhD thesis, University of Maryland, College Park, MaryLand, 1990. Google ScholarDigital Library
- 12.K. B. Gallagher and J. R. Lyle. Using program slicing in software maintenance. IEEE Transactions on Software Engineering, 17(8):751-761, Aug. 1991. Google ScholarDigital Library
- 13.D. Harel. A linear time algorithm for finding dominators in flow graphs and related problems. In Proceedings of the 17th A CM Symposium on Theory of Computing, pages 185-194, May 1985. Google ScholarDigital Library
- 14.M. J. Harrold, B. Malloy, and G. Rothermel. Efficient construction of program dependence graphs. In Procee&ngs of the 1993 International Symposium on Software Testing and Analysis (I$$TA), pages 160-170. ACM Press, June 1993. Google Scholar
- 15.P. Hausler. Denotational program slicing. In Proceedings of lhe Twenty-Second Annual Hawaii International Conference on System Sciences, volume II, pages 486-494, 1989.Google ScholarCross Ref
- 16.S. Horwitz, J. Prins, and T. Reps. Integrating noninterfering versions of programs. A CM Transactions on Programming Languages and Systems, 11(3):345-387, July 1989. Google ScholarDigital Library
- 17.S. Horwitz, T. Reps, and D. Binkley. InterproceduraI slicing using dependence graphs. A CM Transactions on Programming Languages and Systems, 12(1):26-60, Jan. 1990. Google ScholarDigital Library
- 18.J. Jiang, X. Zhou, and D. j. Robson. Program slicing for C~the problems in implementation. In Proceedings of the IEEE Conference on Software Maintenance. IEEE Computer Society Press, Oct. 1991.Google ScholarCross Ref
- 19.B. Korel and J. Laski. Dynamic slicing of computer programs. Journal of Systems and Software, 13(3):187-195, Nov. 1990. Google ScholarDigital Library
- 20.T. Lengauer and R. E. Tarjan. A fast algorithm for finding dominators in a fiowgraph. A CM Transactions on Programming Languages and Systems, 1(1):121-141, July 1979. Google ScholarDigital Library
- 21.H. Longworth, L. Ott, and M. Smith. The relationship between program complexity and slice complexity during debugging tasks. In Proceedings of COMPSAC. IEEE Computer Society Press, 1986.Google Scholar
- 22.J. R. Lyle. Evaluating Variations on Program Slicing for Debugging. PhD thesis, University of Maryland, College Park, MaryLand, 1984. Google ScholarDigital Library
- 23.L. Ott and J. Thuss. The relationship between slices and module cohesion. In Proceedings of the Eleventh International Conference on Software Engineering. IEEE Computer Society Press, May 1989. Google ScholarDigital Library
- 24.K. j. Ottenstein and L. M. Ottenstein. The program dependence graph in a software development environment. In Proceedings of the A CM $IG$OFT/$IGPLAN Symposium on Practical Software Development Environments. ACM Press, Apr. 1984. SIGPLAN Notices, 19(5):177- 184, May 1984. Google ScholarDigital Library
- 25.P. W. Purdom, Jr. and E. F. Moore. Immediate predominators in directed graphs. Communications of the A CM, 15(8):777-778, Aug. 1972. Google ScholarDigital Library
- 26.T. Reps and W. Yang. The semantics of program slicing. Technical Report TR-777, Computer Science Department, University of Wisconsin, Madison, Wisconsin, June 1988.Google Scholar
- 27.R. P. Selke. A rewriting semantics for program dependence graphs. In Conference Record of the Sixteenth A CM Symposium on Principles of Programming Languages, pages i2-24. ACM Press, Jan. 1989. Google ScholarDigital Library
- 28.G. A. Venkatesh. The semantic approach to program slicing. In Proceedings of the SIGPLAN'91 Conference on Programming Language Design and Implementation. ACM Press, June 1991. SIG- PLAN Notices, 26(6):107-119, June 1991. Google ScholarDigital Library
- 29.M. Weiser. Program slicing. IEEE Transactions on Software Engineering, SE-10(4):352-357, July 1984.Google ScholarDigital Library
Index Terms
- On slicing programs with jump statements
Recommendations
On slicing programs with jump statements
Program slices have potential uses in many software engineering applications. Traditional slicing algorithms, however, do not work correctly on programs that contain explicit jump statements. Two similar algorithms were proposed recently to alleviate ...
Hamiltonian jump graphs
Let G be a nonempty graph. The jump graph J(G) of G is the graph whose vertices are edges of G, and where two vertices of J(G) are adjacent if and only if they are not adjacent in G. Equivalently, the jump graph J(G) of G is the complement of line graph ...
Thin slicing
Proceedings of the 2007 PLDI conferenceProgram slicing systematically identifies parts of a program relevant to a seed statement. Unfortunately, slices of modern programs often grow too large for human consumption. We argue that unwieldy slices arise primarily from an overly broad definition ...
Reviews
James Curtis Miller
Program slices are a useful tool in many areas of software engineering. Most earlier algorithms to create these slices could not deal with jump statements (such as goto , exit , and break ) , however. This paper examines two newer algorithms that can handle these statements. It then discusses an extension to these algorithms that, in the special case of structured jumps such as exit or break, produces the slice efficiently. This paper is worth reading by anyone who is interested in software engineering and wants to know something about newer tools. It is well written and should be readable by most computing professionals.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments