Specialization Slicing

Abstract

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.