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