Article,
Interprocedural Slicing Using Dependence Graphs
ACM Transactions on Programming Languages and Systems, (1990)
Abstract
he 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 be 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
