Executable Slicing via Procedure Specialization

Abstract

Although Weiser originally defined a program slice to be an executable projection of a program, much of the research on slicing has focused on closure slices, which consist of the set of statements and conditions of the program that might affect the value of a given variable at a given statement or condition of interest. While closure slices can be useful, there are some contexts in which executable slices are preferable. Closure slices are not generally executable because there can be mismatches in the slice between the sets of actual parameters at different call-sites to a procedure p and the formal parameters of p.

This paper presents a new approach to creating executable slices. Our algorithm addresses the parameter-mismatch problem by creating specialized versions of procedures that have different sets of formal parameters. Moreover, the slice returned by the algorithm is minimal: the slice consists of the set of specialized procedures that solves a certain coarsest-partition problem.

The paper presents solutions for some additional issues that arise with more realistic languages than considered in past work. It also presents the results of an experimental evaluation of the algorithm applied to C programs.