(Last modified Wed May 07 17:18 2008)

Some definitions

Program slice

The portion of a program that affects the value of a specific variable at a specific point in the program.

Slicing criterion

The specific variable(s) and point in the program

Slicing transforms the program by (potentially) removing much of it from consideration.

Static slice

Everything that may ever affect the value for any run of the program.

Dynamic slice

Everything that will affect the value for a specific run of the program.

A dynamic slice is no larger than the corresponding static slice, and may be much smaller

A static slice is valid for any execution of the program -- flow- and context-insensitive

Conditioned slice

Everything that may affect the value for runs meeting a specific condition.  Conditioned slices conceptually range between static and dynamic slices, both in size and in generality. 

Amorphous slice

Not a subset of the original program's statements; more complex transformations are allowed, not just deleting statements.  The resulting slice is still a behavioral projection of the original program.  An amorphous slice may be static, conditioned, or dynamic. 

Forward slice

Work forward from the criterion to the parts of the program that are affected by the criterion. 

Weiser1984

Weiser's definitions, paraphrased and explicated

Listed in the order in which they appear in Weiser.

digraph

a directed graph

flowgraph

a digraph with an initial node n0

m dominates n

m and n are nodes in a flowgraph and every path from n0 to n passes through m

hammock graph

a flowgraph with an initial node n0 and final node ne

m inverse dominates n

m and n are nodes in a flowgraph and every path from n to ne passes through m

REF(n)

The variables whose values are used at statement n.  Named REF because the variables's values are referenced.

DEF(n)

The variables whose values are changed at statement n.  Named DEF because the variables's values are defined.

State trajectory   (n1, s1) (n2, s2)... (nk, sk)

A list of the statements executed during a particular run of a program, annotated with the values of the program's values at each point. 

The list must be finite. 

Formally:  a sequence of ordered pairs (node n, variablesToValues s) where n is a node (in this context, a statement) and s, the state, is a function mapping each variable to its value.  The mapping is for the values immediately before n is executed.  Each pair is a step in the state trajectory. 

Projection

"Slices reproduce a projection from the behavior of the original program."  We illustrated projection using the example of a shape projected onto the wall.  The projection is faithful to the original, but leaves out part.  The projection functions Proj' and Proj are defined below. 

Slicing criterion   ⟨i, P⟩

of a program P is a statement and the variables we care about.  Formally, ⟨i, P⟩ where i is a statement in P and V is a subset of variables in P⟩.  The slice will contain all statements that affect the value of these variables at that statement.

Proj'⟨i,V⟩((n, s))

The projection of a single step (n, s) of a state trajectory, with respect to the slicing criterion .  This function throws away everything we don't care about for a slice. 

Proj' is only used in the definition of Proj. 

The details:  The projection is to (n, s|V) if n is the slicing criterion's statement, and to nothing otherwise.  s|V is the function s (from variables to values) but restricted only to the variables in V. 

Proj' takes a single step, and produces a single step or nothing. 

Proj⟨i,V⟩(T)

is Proj' applied to an entire trajectory.  This function throws away everything we don't care about for a slice. 

Proj is only used in the definition of slice. 

The details:  Proj removes every step that is not at statement i.  There may be many steps that are at statement i, since a statement can appear many times in a state trajectory (for example due to a loop).  Or there may be no steps at that statement, since a trajectory need not reach every statement.  For the remaining steps, the state function is restricted to the variables in the slicing criterion. 

Slice S

of program P on slicing criterion C=⟨i, V⟩ is any program such that:

1. S is P with statements deleted (zero or more).
2. If P halts for a particular input, so does S.
   1. If S contains statement i, then S and P both arrive at i the same number of times, and the values of the variables in V are the same for P and S every time they are both at statement i.
   2. If S does not contain statement i, then we consider the nearest successor succ(i) to i in P that S does contain; the previous statement applies to i in P and succ(i) in S.

These two properties are later referred to as the slice properties. 

This definition formalizes our informal notion that the slice behaves the same as the original program, with respect to the variables of interest.

Statement-minimal

A slice is statement-minimal if no other slice (of the same program, on the same criterion) has fewer statements.

Relevant variables RC0

Directly-relevant variables at a specific statement. 

Formally, R⟨i, V⟩0(i) is V at statement i.  At other statements j, R contains all variables that j does not define (change) and that are relevant for the next statement; if j defines (changes) a variable that statement j+1 references, then R contains all variables that statement j references. 

This inductive definition may be used to work back from the slicing criterion statement to all statements that can precede it.

Statements included SC0

Included in the slice:  All statements that define (change) variables relevant at the following statement.

Later definitions specify how to account for alternation, iteration, and procedure calls; they are not described here. 

Finding slices

• Every program has at least one slice for any criterion -- the program itself.
• It is impossible to find the smallest possible slice for a criterion, in general; it is equivalent to solving the halting problem (Weiser sketches a proof).
• There is no unique statement-minimal slice, in general.
• With care (and the use of dataflow analysis) we can construct conservative slices, not as small as possible (or even necessarily close) but guaranteed to have the two slice properties. 

Weiser presents a succession of more-and-more exact ways of determining the set of relevant variables for each statement in the program:  for straight-line code, then for branches and loops, then for procedures, then for separately-compiled procedures.  Slicing is done by removing statements based on their relevant variables.  Which statements are removed is defined by SCi(i). 

Empirical data

The empirical data are interesting but point to no particular conclusion. 

Slice-and-splice

This section briefly discusses the use of slicing for multiprocessing.  Because a program's slices are independent, they may be executed in parallel without any communication.  When all slices have terminated, a "splicer" would merge their results into the results of the original program. 

Thomas A. Alspaugh
Assistant Professor, Informatics Dept.
School of Information and Computer Sciences