28
S. Chakraborty et al.
We represent a program using a control flow graph G = (Locs, Edges, μ),
where Locs denotes the set of control locations (nodes) of the program, Edges ⊆
Locs×Locs×{tt, ff , U} represents the flow of control and μ : Locs → AssignSt ∪
BoolE annotates every node in Locs with either an assignment statement (of the
form v := E or A[E] := E) from the set of assignment statements AssignSt, or a
Boolean condition. Two distinguished control locations, called Start and End in
Locs, represent the entry and exit points of the program. An edge (n 1 , n 2 , label)
represents flow of control from n 1 to n 2 without any other intervening node. It
is labeled tt or ff if μ(n 1 ) is a Boolean condition, and is labeled U otherwise. If
μ(n 1 ) is a Boolean condition, there are two outgoing edges from n 1 , labeled tt
and ff respectively, and control flows from n 1 to n 2 along (n 1 , n 2 , label) only if
μ(n 1 ) evaluates to label. If μ(n 1 ) is an assignment statement, there is a single
outgoing edge from n 1 , and it is labeled U. Henceforth, we use CFG to refer to
the control flow graph.
A CFG may have cycles due to the presence of loops in the program. A backedge of a loop is an edge from the node corresponding to the last statement in
the loop body to the node representing the loop head. An exit-edge is an edge
from the loop head to a node outside the loop body. An incoming-edge is an edge
to the loop head from a node outside the loop body. We assume that every loop
has exactly one back-edge, one incoming-edge and one exit-edge. For technical
reasons, and without loss of generality, we also assume that the exit-edge of a
loop always goes to a “nop” node (say, having a statement x = x;).
Given a program, the program dependence graph (or PDG) G = (V, DE, CE)
represents data and control dependencies among program statements. Here, V
denotes vertices representing assignment statements and boolean expressions,
DE ⊆ V × V denotes data dependence edges and CE ⊆ V × V denotes control
dependence edges. Standard dataflow analysis identifies dependencies between
program variables and thereby among statements. Dependence between statements updating array elements requires a more careful analysis. Let S 1 and S 2
be two statements in loops L 1 and L 2 where there is a control-flow path from
S 1 to S 2 in the CFG. Suppose S 1 is of the form A[f (i 1 , N)] = F (. . .); where f
is an array index expression, i 1 is the loop counter variable of L 1 , and F is an
arbitrary expression. Suppose S 2 is of the form X = G(A[g(i 2 , N)]);, where X
is a variable or array element, G is an arbitrary expression, and g is an array
index expression.
Definition 1. We say that S 2 in L 2 depends on S 1 in L 1 if there exists i 1 , i 2
such that 0 ≤ i 1 < k L1 (N ) and 0 ≤ i 2 < k L2 (N ) and f (i 1 , N) = g(i 2 , N).
The routine ComputeRefinedPDG shown in Algorithm 1 constructs and
refines the program dependence graph G = (V, DE, CE) for the input program
P N . It uses the function ConstructPDG (line 1) based on the technique of
[11] to create an initial graph. For a node n in G, let def (n) and uses(n) refer to the set of variables/array elements defined and used, respectively, in the
statement/boolean expression corresponding to n. Similarly, let subscript(v, n)
refer to the index expression of the array element v referred to at node n. Predicate is-array(v) evaluates to true if v is an array element and false if v is a
S. Chakraborty et al.
We represent a program using a control flow graph G = (Locs, Edges, μ),
where Locs denotes the set of control locations (nodes) of the program, Edges ⊆
Locs×Locs×{tt, ff , U} represents the flow of control and μ : Locs → AssignSt ∪
BoolE annotates every node in Locs with either an assignment statement (of the
form v := E or A[E] := E) from the set of assignment statements AssignSt, or a
Boolean condition. Two distinguished control locations, called Start and End in
Locs, represent the entry and exit points of the program. An edge (n 1 , n 2 , label)
represents flow of control from n 1 to n 2 without any other intervening node. It
is labeled tt or ff if μ(n 1 ) is a Boolean condition, and is labeled U otherwise. If
μ(n 1 ) is a Boolean condition, there are two outgoing edges from n 1 , labeled tt
and ff respectively, and control flows from n 1 to n 2 along (n 1 , n 2 , label) only if
μ(n 1 ) evaluates to label. If μ(n 1 ) is an assignment statement, there is a single
outgoing edge from n 1 , and it is labeled U. Henceforth, we use CFG to refer to
the control flow graph.
A CFG may have cycles due to the presence of loops in the program. A backedge of a loop is an edge from the node corresponding to the last statement in
the loop body to the node representing the loop head. An exit-edge is an edge
from the loop head to a node outside the loop body. An incoming-edge is an edge
to the loop head from a node outside the loop body. We assume that every loop
has exactly one back-edge, one incoming-edge and one exit-edge. For technical
reasons, and without loss of generality, we also assume that the exit-edge of a
loop always goes to a “nop” node (say, having a statement x = x;).
Given a program, the program dependence graph (or PDG) G = (V, DE, CE)
represents data and control dependencies among program statements. Here, V
denotes vertices representing assignment statements and boolean expressions,
DE ⊆ V × V denotes data dependence edges and CE ⊆ V × V denotes control
dependence edges. Standard dataflow analysis identifies dependencies between
program variables and thereby among statements. Dependence between statements updating array elements requires a more careful analysis. Let S 1 and S 2
be two statements in loops L 1 and L 2 where there is a control-flow path from
S 1 to S 2 in the CFG. Suppose S 1 is of the form A[f (i 1 , N)] = F (. . .); where f
is an array index expression, i 1 is the loop counter variable of L 1 , and F is an
arbitrary expression. Suppose S 2 is of the form X = G(A[g(i 2 , N)]);, where X
is a variable or array element, G is an arbitrary expression, and g is an array
index expression.
Definition 1. We say that S 2 in L 2 depends on S 1 in L 1 if there exists i 1 , i 2
such that 0 ≤ i 1 < k L1 (N ) and 0 ≤ i 2 < k L2 (N ) and f (i 1 , N) = g(i 2 , N).
The routine ComputeRefinedPDG shown in Algorithm 1 constructs and
refines the program dependence graph G = (V, DE, CE) for the input program
P N . It uses the function ConstructPDG (line 1) based on the technique of
[11] to create an initial graph. For a node n in G, let def (n) and uses(n) refer to the set of variables/array elements defined and used, respectively, in the
statement/boolean expression corresponding to n. Similarly, let subscript(v, n)
refer to the index expression of the array element v referred to at node n. Predicate is-array(v) evaluates to true if v is an array element and false if v is a