Efficient Comparison of Program Slices

Susan Horwitz and Thomas Reps
University of Wisconsin

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.