### Graph-Less
Dynamic Dependence-Based Dynamic Slicing Algorithms

*Árpád Beszédes, Tamás Gergely and Tibor
Gyimóthy*
Using Dynamic Dependence Graphs is a well understood method
for computing dynamic program slices. However, in its basic form, the
DDG is inappropriate for practical implementation, so several
alternative approaches have been proposed by researchers. In this
paper, we elaborate on different methods in which the execution trace
is processed and, using local definition-use information, the
dependence chains are followed ``on the fly'' to construct the slices
without actually building any graphs. Naturally, various additional
data structures still need to be maintained, but these vary on the
slicing scenario. Firstly, one may want to perform the slicing in a
demand-driven fashion, or to compute many slices globally. Next, one
may be interested either in backward or forward slices. And finally,
the slices can be produced by traversing the trace either in a forward
or in a backward direction. This totals eight possibilities, of which
some give useful algorithms, while there are irrelevant combinations as
well. In this work we investigate all of them, give the basic
algorithms where appropriate and discuss on implementation experiences
and perspectives.

Keywords: Program slicing, dynamic slicing algorithms, execution
trace, program dependences.

Back