Precise Interprocedural Chopping
Thomas Reps and Genevieve Rosay
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.)
University of Wisconsin