Improved interprocedural slicing algorithm

Arun Lakhotia

Abstract

Horwitz, Reps, and Binkley (TOPLAS, 90) present an algorithm for interprocedural program slicing using a system dependence graph (SDG) representation of programs. In order to identify the set of statements in a slice their algorithm makes two traversals over the SDG; effectively traversing some edges twice. This paper presents a one pass algorithm which traverses each edge in the slice at most once. In scenarios requiring on-line union of interprocedural slices, the algorithm provides significant improvement by permitting the construction of union incrementally.

Full paper