Interprocedural Slicing Using Dependence Graphs
Susan Horwitz, Thomas Reps, and David Binkley
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.
(Click here to access a retrospective note about the paper:
PostScript,
PDF.)
University of Wisconsin