Graph-Less Dynamic Dependence-Based Dynamic Slicing Algorithms

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.