Interprocedural Slicing Using Dependence Graphs
Susan Horwitz, Thomas Reps, and David Binkley
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 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.
CR Categories and Subject Descriptors:
D.3.3 [Programming Languages]: Language Constructs --
control structures, procedures, functions, and subroutines;
D.3.4 [Programming Languages]: Processors --
compilers, optimization
General Terms: Algorithms, Design
Additional Key Words and Phrases:
attribute grammar, control dependence, data dependence,
data-flow analysis, flow-insensitive summary information, program debugging,
program dependence graph, program integration, program slicing,
subordinate characteristic graph
(Click here to access the paper:
PostScript,
PDF.)
University of Wisconsin