Susan Horwitz
Thomas Reps
David Binkley
Abstract
The notion of a program slice, originally introduced by Mark Weiser, is useful in program debugging, automatic parallelization, and program integration. A slice of a program is taken with respect to a program point p and a variable x; the slice 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. (It should be noted that our work concerns a somewhat restricted kind of slice: rather than permitting a program to b e sliced with respect to program point p and an arbitrary variable, a slice must be taken with respect to a variable that is defined or used at p.)
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 dependences 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.
- 1 AHO, A. V., SETHI, R., AND ULLMAN, J. D. Compilers: Principles, Techniques, and Tools, Addison-Wesley, Reading, Mass., 1986. Google Scholar
- 2 BAmCH, W. A., AND JAZAYERI, M. The method of attributes for data flow analysis: Part II. Demand analysis. Acta Inf. 10, 3 (Oct. 1978), 265-272.Google Scholar
- 3 BADGER, L., AND WEISER, M. Minimizing communication for synchronizing parallel dataflow programs. In Proceedings of the 1988 International Conference on Parallel Processing (St. Charles, IL, Aug. 15-19, 1988). Pennsylvania State University Press, University Park, PA, 1988.Google Scholar
- 4 BANNING, J.P. An efficient way to find the side effects of procedure calls and the aliases of variables. In Conference Record of the Sixth ACM Symposium on Principles of Programming Languages (San Antonio, Tex., Jan. 29-31, 1979). ACM, New York, 1979, pp. 29-41. Google Scholar
- 5 CALLAHAN, D. The program summary graph and flow-sensitive interprocedural data flow analysis. In Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation (Atlanta, Ga., June 22-24, 1988). ACM SIGPLAN Not. 23, 7 (July 1988), 47-56. Google Scholar
- 6 COOPER, $. D., AND KENNEDY, K. Interprocedural side-effect analysis in linear time. In Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation (Atlanta, Ga., June 22-24, 1988). ACM SIGPLAN Not. 23, 7 (July 1988), 57-66. Google Scholar
- 7 FERRANTE, J., OTTENSTEIN, $., AND WARREN, J. The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Syst. 9, 3 (July 1987), 319-349. Google Scholar
- 8 HORWITZ, S., PRINS, J., AND REPS, T. Integrating non-interfering versions of programs. TR-690, Computer Sciences Dept., Univ. of Wisconsin, Madison, March 1987.Google Scholar
- 9 I-IoRwITZ, S., PRINS, J., AND REPS, T. On the adequacy of program dependence graphs for representing programs. In Conference Record of the Fifteenth ACM Symposium on Principles of Programming Languages (San Diego, Calif., Jan. 13-15, 1988). ACM, New York, 1988, pp. 146-157. Google Scholar
- 10 HORWlTZ, S., REPS, T., AND BINKLEY, n. Interprocedural slicing using dependence graphs. In Proceedings of the ACM SIGPLAN 88 Conference on Programming Language Design and Implementation (Atlanta, Ga., June 22-24, 1988). ACM SIGPLAN Not. 23, 7 (July 1988), 35-46. Google Scholar
- 11 HORWITZ, S., PRINS, J., AND REPS, T. Integrating non-interfering versions of programs. ACM{ Trans. Program. Lang. Syst. 11, 3 (July 1989), 345-387. Google Scholar
- 12 HWANG, J. C., nu, M. W., AND CHOU, C.a. Finding program slices for recursive procedures. In Proceedings of the IEEE COMPSAC 88 (Chicago, Oct. 3-7, 1988). IEEE Computer Society, Washington, D.C., 1988.Google Scholar
- 13 KASTENS, U. Ordered attribute grammars. Acta Inf. 13, 3 (1980), 229-256.Google Scholar
- 14 KNUTH, D. E. Semantics of context-free languages. Math. Syst. Theor. 2, 2 (June 1968), 127-145.Google Scholar
- 15 Kou, L.T. On live-dead analysis for global data flow problems. J. ACM 24, 3 (July 1977), 473-483. Google Scholar
- 16 KUCK, D. J., MURAOKA, Y., AND CHEN, S.C. On the number of operations simultaneously executable in FORTRAN-like programs and their resulting speed-up. IEEE Trans. Comput. C-21, 12 (Dec. 1972), 1293-1310.Google Scholar
- 17 LYLE, J., AND WEISER, M. Experiments on slicing-based debugging tools. In Proceedings of the First Conference on Empirical Studies of Programming ( June 1986). Google Scholar
- 18 MYERS, E. A precise inter-procedural data flow algorithm. In Conference Record of the Eighth A CM Symposium on Principles of Programming Languages (Williamsburg, Va., Jan. 26-28, 1981 ). ACM, New York, 1981, pp. 219-230. Google Scholar
- 19 OTTENSTEIN, K. J., AND OTTENSTEIN, L.M. The program dependence graph in a software development environment. In Proceedings of the ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments (Pittsburgh, Pa., April 23-25, 1984). ACM SIGPLAN Not. 19, 5 (May 1984), 177-184. Google Scholar
- 20 REPS, T., AND YANG, W. The semantics of program slicing. TR-777, Computer Sciences Dept., Univ. of Wisconsin, Madison, June 1988.Google Scholar
- 21 WEISER, M. Reconstructing sequential behavior from parallel behavior projections. Inf. Process. Lett. 17 (Oct. 1983), 129-135.Google Scholar
- 22 WEmER, M. Program slicing. IEEE Trans. Softw. Eng. SE-IO, 4 (July 1984), 352-357.Google Scholar
Index Terms
- Interprocedural slicing using dependence graphs
Recommendations
Interprocedural slicing using dependence graphs
PLDI '88: Proceedings of the ACM SIGPLAN 1988 conference on Programming language design and implementationA 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 ...
Interprocedural slicing using dependence graphs
Proceedings of the SIGPLAN '88 conference on Programming language design and implementationA 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 ...
Interprocedural slicing using dependence graphs
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A SelectionA 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 ...
Reviews
Teodor Rus
The behavior of a program is usually defined by the behavior of the process performed by a computer executing a translation of the program. One tool used to study program behavior is the representation of the program by an adequate intermediate representation, such as a control flow graph of the program. Adding edges representing data dependence to this flow graph leads to various kinds of program dependence graphs. This paper approaches the problem of using a suitable program dependence graph (called the system dependence graph) to develop an algorithm to compute program slices crossing procedure call boundaries. This approach is called interprocedural slicing. A slice of a program P with respect to a program point p and a variable x consists of all statements and predicates of the program P that might affect the value of x at p . In the definition of a slice used in this paper, x must be defined or used at p . In order to compute a slice, the program P is represented as a dependence graph containing data and control dependence edges. Two “directly affected” relations are defined on this graph: If the variable x is defined at the point p of the program, then the value of x is directly affected by the values of the variables used at p and by the conditionals and loops that enclose p. If the variable x is used at the point p of the program then the value of x is directly affected by those assignments to x that reach p and by the conditionals and loops that enclose p . Using these relations, a slice of program P at point p and variable x can be computed by a reachability algorithm on the dependence graph of P . The authors consider two versions of the problem of slice computation. In version 1, the slice of the program P with respect to a program point p and a variable x consists of all statements and predicates of the program that might affect the value of x at point p . In version 2, the slice of the program P with respect to a program point p and variable x consists of a reduced program that computes the same sequence of values for x at point p . Since a slice by version 1 is not necessarily a program, the solutions to these two problems differ. For a program without procedure calls (intraprocedural slicing) a solution to version 1 of the problem of slicing also provides a solution to version 2. The reduced program required by version 2 can be obtained from the original program by restricting it to include only statements and predicates that are collected in a slice by version 1. For a program P that contains multiple calls to the same procedure, however, the statements and predicates in a slice defined as in version 1 may yield a syntactically incorrect program: different calls to the same procedure may pass different arguments. This paper addresses version 1 of the interprocedural slicing problem (with the restriction that variable x is used or defined at the point p ) and develops an algorithm that computes slices that cross procedure boundaries. First, the concept of a system dependence graph is developed. The major difficulty in interprocedural slicing is correctly accounting for the context of a called procedure. The paper solves this problem by adding to the system dependence graph edges that represent transitive dependence due to the effects of procedure calls. An attribute grammar facilitates the computation of such dependencies. This approach allows interprocedural slices to be computed in two passes, each of which is cast as a graph reachability problem.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments