Specialization Slicing
Min Aung, Susan Horwitz, and Rich Joiner, and Thomas Reps
This paper defines a new variant of program slicing,
called specialization slicing, and presents
an algorithm for the specialization-slicing problem that creates
an optimal output slice.
An algorithm for specialization slicing is polyvariant:
for a given procedure
We formalize the specialization-slicing problem as a partitioning
problem on the elements of the possibly infinite unrolled program.
To manipulate possibly infinite sets of program elements, the
algorithm makes use of automata-theoretic techniques originally
developed in the model-checking community.
The algorithm returns a finite answer that is optimal
(with respect to a criterion defined in the paper).
In particular, (i) each element replicated by the specialization-slicing
algorithm provides information about specialized patterns of program
behavior that are intrinsic to the program, and (ii) the answer is
of minimal size (i.e., among all possible answers with property (i),
there is no smaller one).
The specialization-slicing algorithm provides a new way to create
executable slices.
Moreover, by combining specialization slicing with forward slicing, we
obtain a method for removing unwanted features from a program.
While it was previously known how to solve the feature-removal problem
for single-procedure programs, it was not known how to
solve it for programs with procedure calls.
(Click here to access the paper:
PDF.
University of Wisconsin
p
, the algorithm may create multiple
specialized copies of p
.
In creating specialized procedures, the algorithm must decide for
which patterns of formal parameters a given procedure should be
specialized, and which program elements should be included in each
specialized procedure.