Program slicing is a fundamental operation for many software engineering tools. Currently, the most efficient algorithm for interprocedural slicing is one that uses a program representation called the system dependence graph. This paper defines a new algorithm for slicing with system dependence graphs that is asymptotically faster than the previous one. A preliminary experimental study indicates that the new algorithm is also significantly faster in practice, providing roughly a 6-fold speedup on examples of 348 to 757 lines.

CR Categories and Subject Descriptors: D.2.2 [Software Engineering]: Tools and Techniques -- programmer workbench; D.2.6 [Software Engineering]: Programming Environments; D.2.7 [Software Engineering]: Distribution and Maintenance -- enhancement, restructuring; E.1 [Data Structures] graphs

General Terms: Algorithms, Performance

Additional Key Words and Phrases: dynamic programming, dynamic transitive closure, flow-sensitive summary information, program debugging, program dependence graph, program slicing, realizable path

(Click here to access the paper: PostScript, PDF.)