Efficient Comparison of Program Slices
Susan Horwitz and Thomas Reps
The slice of a program with respect to a component c is a
projection of the program that includes all components that might
affect (either directly or transitively) the values of the variables
used at c.
Slices can be extracted particularly easily from a program
representation called a program dependence graph, originally
introduced as an intermediate program representation for performing
optimizing, vectorizing, and parallelizing transformations.
This paper presents a linear-time algorithm for determining whether
two slices of a program dependence graph are isomorphic.
University of Wisconsin