Specialization Slicing
Min Aung, Susan Horwitz, 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 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.
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. 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