Precise Interprocedural Chopping

Thomas Reps and Genevieve Rosay
University of Wisconsin

The notion of a program slice, originally introduced by Mark Weiser, is a fundamental operation for addressing many software-engineering problems, including program understanding, debugging, maintenance, testing, and merging. A slice determines either all program elements that might affect a given element ("backward slicing") or all elements that could be affected by a given element ("forward slicing").

Jackson and Rollins introduced a related operation, called program chopping, which is a kind of "filtered" slice: Chopping answers questions of the form "What are all the program elements v that serve to transmit effects from a given source element s to a given target element t?" However, Jackson and Rollins define only a limited form of chopping: Among other restrictions, they impose the restriction that s and t be in the same procedure.

This paper solves the unrestricted interprocedural chopping problem, as well as a variety of other useful variants of interprocedural chopping.

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: program dependence graph, program slicing, program chopping, debugging, interprocedural analysis, graph reachability, realizable path

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