Specialization Slicing
File(s)
Date
2013-08-14Author
Aung, Min
Horwitz, Susan
Joiner, Rich
Reps, Thomas
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Metadata
Show full item recordAbstract
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 (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.
Subject
Program slicing
program specialization
executable slice
feature removal
program dependence graph
pushdown system
reverse-deterministic automaton
Permanent Link
http://digital.library.wisc.edu/1793/66351Citation
TR1776-R1
Proceded by TR1776 and TR1711