Interprocedural slicing using dependence graphs

Abstract

A slice of a program with respect to a program point p and variable x consists of all statements of the program that might affect the value of x at point p. This paper concerns the problem of interprocedural slicing — generating a slice of an entire program, where the slice crosses the boundaries of procedure calls. To solve this problem, we introduce a new kind of graph to represent programs, called a system dependence graph, which extends previous dependence representations to incorporate collections of procedures (with procedure calls) rather than just monolithic programs. Our main result is an algorithm for interprocedural slicing that uses the new representation.

The chief difficulty in interprocedural slicing is correctly accounting for the calling context of a called procedure. To handle this problem, system dependence graphs include some data-dependence edges that represent transitive dependencies due to the effects of procedure calls, in addition to the conventional direct-dependence edges. These edges are constructed with the aid of an auxiliary structure that represents calling and parameter-linkage relationships. This structure takes the form of an attribute grammar. The step of computing the required transitive-dependence edges is reduced to the construction of the subordinate characteristic graphs for the grammar's nonterminals.

References

1. Babich78 Babich, W.A. and Jazayeri, M., "The method of attributes for data flow analysis: Part IL Demand analysis," Acts Informatica 10(3)pp. 265-272 (October 1978).
2. Banning79 Banning, J.P., "An efficient way to find the side effects of procedure calls and the aliases of variables," pp. 29-41 in Conference Record of the Sixth ACM Symposium on Principles of Programming Languages, (San Antonio, TX, Jan. 29-3 l, 1979), ACM, New York (1979).
3. Callahan88 Callahan, D., "The program summary graph and flow-sensitive interprocedural data flow analysis," Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, June 22-24, 1988), ACM SIGPLAN Notices, (June 1988).
4. Cooper88 Cooper, K.D. and Kennedy, K., .Interproceduml side-effect analysis in linear time," Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation, (Atlanta, GA, lune 22-24, 1988), ACM SIGPLANNotices, (June 1988).
5. Ferrante87 Ferrante, J., Ottenstein, K., and Warren, J., "The program delmndence graph and its use in optimization," ACM Transactions on Programruing Languages and Systems 9(3) pp. 319-349 (July 1987).
6. Horwitz87 Horwitz,, S., Prins, j,, and Reps, T,, "Integrating non-interfering versions of programs," TR-690, Computer Sciences Department, University of Wisconsin, Madison, WI (March 1987).
7. Horwitz88 Horwitz, S., Prins, J., and Reps, T., "Inmgrating non-interfering versions of programs," pp. 133-145 in Conference Record of the Fifteenth ACM Symposium on Principles of Programming Languages, (San Diego, CA, january 13-15, 1988), ACM, New York 0988).
8. Horwitz88a Horwitz, S., Reps, T., and Binldey, D., .lnterprocedural slicing using dependence graphs," TR-756, Caxtputer Sciences Department, University of Wisconsin, Madison, WI (March 1988).
9. Kastens80 Kastens, U., .Ordered attribute grammars," Acta Inf. 13(3)pp. 229- 256 (1980).
10. Knuth68 Knuth, D.E., "Semantics of context-free languages," Math. $yst. Theory 2(2) pp. 127-145 (June 1968).
11. Kou77 Kou, L.T., "On live-dead analysis for global data flow problenas," Journal ofthe ACM 24(3) pp. 473-483 (iluly 1977).
12. Kuck72 Kuek, D.J., Muraoka, Y., and Chert, S.C., "On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speed-up," 1EEE Trans. on Computers C-21(12)pp. 1293-1310 (December 1972).
13. Myers81 Myers, E., "A precise inter-procedural data flow algorithm," pp. 219- 230 in Conference Record of the Eighth ACM Symposium on Principles of Programming Languages, (Williamsburg, VA, January 26-28, 1981), ACM, New York (1981).
14. Ottenstein84 Ottenstein, K.J. and Ouenstein, L.M., "The program dependence graph in a software develognnent environment," Proceedings of the ACM $1GSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, (Pittsburgh, PA, Apr. 23-25, 1984), ACM $IGPLAN Notices 19(5) pp. 177-184 (May 1984).
15. Reps88 Reps, T. and Yang, W., "The semantics of program slicing," Tech. Rep. in preparation, Computer Sciences Department. University of Wisconsin, Madison, WI (Spring 1988).
16. Waite83 Waite, W.M. and Goos, G., Compiler Construction, Springer-Verlag, New York (1983).
17. Weiser84 Weiser, M., "Program slicing," IEEE Transactions on Software Engineering SE-10(4) pp. 352-357 (July 1984).

Index Terms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms