Program slicing: Difference between revisions

Revision as of 15:40, 4 November 2017

Revision as of 20:01, 25 December 2017

Line 8:

== Static slicing ==

Based on the original definition of Weiser, informally, a static program slice S consists of all statements in program P that may affect the value of variable v atin somea pointstatement px. The slice is defined for a slicing criterion C=(x,Vv), where x is a statement in program P and Vv is a subset of variablesvariable in Px. A static slice includes all the statements that can affect the value of variable v at statement x for aany setpossible ofinput. Static slices are computed by backtracking dependencies between statements. More specifically, to compute the static slice for (x,v), we first find all possiblestatements inputsthat atcan a directly affect the pointvalue of interestv (i.ebefore statement x is encountered. Recursively, atfor each statement y which can affect the value of v in statement x){{Clarify|date=November, 2016}}.we Staticcomputer the slices arefor computedall byvariables findingz consecutivein y that affect the setsvalue of indirectlyv. relevant statements,The accordingunion toof [[dataall dependency|data]]those andslices controlis dependenciesthe static slice for (x,v).

=== Example ===

For example, consider the C program below. Let's compute the slice for ( write(sum), sum ). The value of sum is directly affected by the statements "sum = sum + i + w" if N>1 and "int sum = 0" if N <= 1. So, slice( write(sum), sum) is the union of three slices and the "int sum = 0" statement which has no dependencies:

<ol>

<li>slice( sum = sum + i + w, sum)</li>,

<li>slice( sum = sum + i + w, i)</li>,

<li>slice( sum = sum + i + w, w)</li>, and

<li>{ int sum=0 }.</li>

</ol>

It is fairly easy to see that slice( sum = sum + i + w, sum) consists of "sum = sum + i + w" and "int sum = 0" because those are the only two prior statements that can affect the value of sum at "sum = sum + i + w". Similarly, slice( sum = sum + i + w, i) only contains "for(i = 1; i < N; ++i) {" and slice( sum = sum + i + w, w) only contains the statement "int w = 7".

When we union all of those statements, we do not have executable code, so to make the slice an executable slice we merely add the end brace for the for loop. The resulting static executable slice is shown below the original code below.

<source lang="c">

int i;

int sum = 0;

int product = 1;

int w = 7;

for(i = 1; i < N; ++i) {

sum = sum + i + w;

product = product * i;

}

Line 22 ⟶ 35:

write(product);

</source>

ThisThe newstatic programexecutable isslice afor valid slicing of the above program with respect to the criterioncriteria (<code>write(sum)</code>,{ sum}): is the new program shown below.

<source lang="c">

int i;

int sum = 0;

int w = 7;

for(i = 1; i < N; ++i) {

sum = sum + i;

Line 34 ⟶ 47:

</source>

In fact, most static slicing techniques, including Weiser's own technique, will also remove the <code>write(sum)</code> statement. Since, at the statement <code>write(sum)</code>, the value of <code>sum</code> is not dependent on the statement itself. Often a slice for a particular statement x will include more than one variable. If V is a set of variables in a statement x, then the slice for (x, V) is the union of all slices with criteria (x, v) where v is a variable in the set V.

== Dynamic slicing ==