30
S. Chakraborty et al.
Algorithm 3 ComputeAffected(PN : Program, peelN odes : Peeled Statements)
1: G(V, DE, CE) := ComputeRefinedPDG(PN );
2: AffectedVars := {N };
N is in the affected set
3: repeat
4:
WorkList := V \ peelN odes;
all non-peeled nodes in G
5:
while WorkList = {} do
6:
Remove a node n from WorkList;
7:
if ∃v. is-array(v) ∧ (∃u. u ∈ subscript(v, n) ∧ u ∈ AffectedVars) then
8:
AffectedVars := AffectedVars ∪ v;
9:
if ∃v. v ∈ uses(n) then
10:
if ∃m. m ∈ reaching-def (v, n) ∧ m ∈ peelN odes then
11:
AffectedVars := AffectedVars ∪ def (n);
12:
if ∃m. m ∈ reaching-def (v, n) ∧ def (m) ∈ AffectedVars then
13:
AffectedVars := AffectedVars ∪ def (n);
14:
if v ∈ AffectedVars ∧ n is a assignment node then
15:
AffectedVars := AffectedVars ∪ def (n);
16:
if v ∈ AffectedVars ∧ n is a predicate node then
17:
for each edge (n, n
) ∈ CE do
18:
AffectedVars := AffectedVars ∪ def (n
);
19: until AffectedVars does not change
20: return AffectedVars;
Affected Variable Analysis. Before we discuss the generation of ∂P N , we
present an analysis that identifies variables/array elements that may take different values in P N and P N −1 . For example, the first k L (N − 1) iterations of L
in P N may not be semantically equivalent to the (entire) k L (N − 1) iterations
of L in P N −1 . This is because the semantics of statements in L may depend
on the value of N either directly or indirectly. We call variables/array elements
updated in such statements as affected variables. For every loop with statements
having potentially different semantics in P N and P N −1 , the difference program
∂P N must have a version of the loop with statements that restore the effect of
the first k L (N − 1) iterations of L in P N after the (entire) k L (N − 1) iterations of
L in P N −1 have been executed. Furthermore, for statements in P N that are not
enclosed within loops but have potentially different semantics from the corresponding statements in P N −1 , ∂P N must also rectify the values of variables/array
elements updated in such statements.
Subroutine ComputeAffected, shown in Algorithm 3, computes the set
of affected variables P N . We first construct the program dependence graph by
calling the function ComputeRefinedPDG (line 1) defined in Algorithm 1. Let
AffectedVars represent the set of affected variables/array elements. We initialize
it (line 2) with variable N since its value is different in P N and P N −1 . For a node
n in the PDG G, we use reaching -def (v, n) to refer to the set of nodes where the
variable/array element v is defined and the definition reaches its use at node n.
In line 4, we collect nodes in the graph that are not the ones peeled from loops
in P N . The loop in lines 5-18 iterates over the collected nodes to identify affected
variables. If a variable in the index expression of an array access is affected then
that array element is considered affected (lines 7-8). A definition at a node n is
affected (marked in line 11) if any variable v used in the statement (checked in
line 9) is defined in a peeled node (line 10). Similarly if the reaching definition
of v is affected (line 12) the definition at n is affected (line 13). A variable
defined in terms of an affected variable is also deemed to be affected (lines 14-
S. Chakraborty et al.
Algorithm 3 ComputeAffected(PN : Program, peelN odes : Peeled Statements)
1: G(V, DE, CE) := ComputeRefinedPDG(PN );
2: AffectedVars := {N };
N is in the affected set
3: repeat
4:
WorkList := V \ peelN odes;
all non-peeled nodes in G
5:
while WorkList = {} do
6:
Remove a node n from WorkList;
7:
if ∃v. is-array(v) ∧ (∃u. u ∈ subscript(v, n) ∧ u ∈ AffectedVars) then
8:
AffectedVars := AffectedVars ∪ v;
9:
if ∃v. v ∈ uses(n) then
10:
if ∃m. m ∈ reaching-def (v, n) ∧ m ∈ peelN odes then
11:
AffectedVars := AffectedVars ∪ def (n);
12:
if ∃m. m ∈ reaching-def (v, n) ∧ def (m) ∈ AffectedVars then
13:
AffectedVars := AffectedVars ∪ def (n);
14:
if v ∈ AffectedVars ∧ n is a assignment node then
15:
AffectedVars := AffectedVars ∪ def (n);
16:
if v ∈ AffectedVars ∧ n is a predicate node then
17:
for each edge (n, n
) ∈ CE do
18:
AffectedVars := AffectedVars ∪ def (n
);
19: until AffectedVars does not change
20: return AffectedVars;
Affected Variable Analysis. Before we discuss the generation of ∂P N , we
present an analysis that identifies variables/array elements that may take different values in P N and P N −1 . For example, the first k L (N − 1) iterations of L
in P N may not be semantically equivalent to the (entire) k L (N − 1) iterations
of L in P N −1 . This is because the semantics of statements in L may depend
on the value of N either directly or indirectly. We call variables/array elements
updated in such statements as affected variables. For every loop with statements
having potentially different semantics in P N and P N −1 , the difference program
∂P N must have a version of the loop with statements that restore the effect of
the first k L (N − 1) iterations of L in P N after the (entire) k L (N − 1) iterations of
L in P N −1 have been executed. Furthermore, for statements in P N that are not
enclosed within loops but have potentially different semantics from the corresponding statements in P N −1 , ∂P N must also rectify the values of variables/array
elements updated in such statements.
Subroutine ComputeAffected, shown in Algorithm 3, computes the set
of affected variables P N . We first construct the program dependence graph by
calling the function ComputeRefinedPDG (line 1) defined in Algorithm 1. Let
AffectedVars represent the set of affected variables/array elements. We initialize
it (line 2) with variable N since its value is different in P N and P N −1 . For a node
n in the PDG G, we use reaching -def (v, n) to refer to the set of nodes where the
variable/array element v is defined and the definition reaches its use at node n.
In line 4, we collect nodes in the graph that are not the ones peeled from loops
in P N . The loop in lines 5-18 iterates over the collected nodes to identify affected
variables. If a variable in the index expression of an array access is affected then
that array element is considered affected (lines 7-8). A definition at a node n is
affected (marked in line 11) if any variable v used in the statement (checked in
line 9) is defined in a peeled node (line 10). Similarly if the reaching definition
of v is affected (line 12) the definition at n is affected (line 13). A variable
defined in terms of an affected variable is also deemed to be affected (lines 14-