Reaching Definitions:
The primary goal includes the identification of all
connections between variable definitions (“write”) and variable uses (“read”)
x
= y + z has a definition of x and uses of y and z
A definition d reaches a program point p if there exists a
CFG path that
Starts
at the program point immediately after d
Ends
at p
Does
not contain a definition of d (i.e., d is not “killed”)
Unambiguous and
Ambiguous Definitions:
a = b + c //unambiguous definition of a
……
* p = a; //ambiguous definition of a if a points to
variables;
…… other than a as well
a = k – m //unambiguous definition of a; kills the above a
The Reaching
Definition Problem
Sets of definitions comprises the domain of dataflow values
Supersets of definitions are calculated as safe values
It is safe to presume that a definition reaches a point,
even if it does not reach a point
In the expel below, it is assumed that both a = 3 and a = 6
reach the point after the completion of
if(a
== b) a = 3; else if(a == b) a =6;
The dataflow equations (constraints) are
IN[B]
= U OUT[P]
P
is a predecessor of B
OUT[B] =
GEN[B] U (IN[B]
– KILL[B])
IN[B] = f, for
all B (initialization only)
If some definitions reach B1 (entry), then IN[B1]
is initialized to that set
Forward flow DFA problem (since OUT[B]) is expressed in
terms of IN[B]), confluence operator is U
GEN[B] = set of all definitions inside B that are “visible”
immediately after the block - downwards
exposed definitions
Reaching Definitions
Analysis:
An Example – Pass 1
Figure 19
An Example – Pass 2
Figure20
An Example – Final
Figure21
An iterative
algorithm for Computing Reaching Definitions
for each
block B do {IN[B] = ∅;
OUT[B] = GEN[B];}
flag
= true;
while
flag do {flag = false;
for
each block B do {
IN[B]
= ∪ OUT[P];
p
is a predecessor of B
oldout
= OUT[B];
OUT[B]
= GEN[B] ∪ (IN[B] – KILL[B]);
If(OUT[B]
≠ oldout) flag = true;
}
}
GEN, KILL, IN and OUT are all represented
as bit vectors with one bit for each definition in the flow graph.
Reaching
Definitions:
Example:
Figure
22
Example:
We can represent GEN[B] and KILL[B]
by bit vectors. That means we can represent each di by 0’s and 1’s.
The line(1) of algorithm is for computing GEN[B] and KILL[B]
|
BLOCK
|
Gen
[B]
|
Kill[b]
|
|
B1
|
gen[B1]
= {d1,d2} = {11000}
|
kill[B1]
= {d3,d4,d5} = {00111}
|
|
B2
|
|
|
|
B3
|
gen[B3]
= {d4} = {00 010}
|
kill[B3]
= {d2,d5} = {01001}
|
|
B4
|
gen[B4]
= {d5} = {00 001}
|
kill[B4]
= {d2,d4} = {01010}
|
|
B5
|
gen[B5]
= ∅ = {00 000}
|
kill[B5]
= ∅ = {00 000}
|
According to line(2) of algorithm we initialize IN[B] = ∅ and OUT[B] = GEN[B] for all the blocks B
|
Initialization
|
||
|
BLOCK
|
in [B]
|
Out [B]
|
|
B1
|
{00000}
|
{11000}
|
|
B2
|
{00000}
|
{00100}
|
|
B3
|
{00000}
|
{00010}
|
|
B4
|
{00000}
|
{00001}
|
|
B5
|
{00000}
|
{00000}
|
Considering that we will get more than one iterations for
the while loop computation for IN[B] and OUT [B] can be done as follows.
IN[B1] = UP OUT[P],
Where p is predecessor blocks.
Predecessor of B1 is B2
IN[B1] = OUT [B2] OUT[B1] = GEN[B1]
U (IN[B1] – KILL[B1])
= 00100 = 11000 U
(00100 – 00111) = 11000
Now consider for block B2
IN[B2] = OUT[B1] + OUT[B5] ∴B1
and B5 are predecessor to B2
= 11000
+ 00000
= 11000
OUT[B2] = GEN[B2] U (IN[B2]
– KILL[B2])
= 00100
U (11000 – 10000)
= 01100
Consider for block B3
IN[B3] = OUT[B2] ∴B2 is predecessor
to B3
= 01100
OUT[B3] = GEN[B3] U (IN[B3]
– KILL[B3])
= 00010
+ (01100 = 01001)
= 00110
Similarly
IN[B4] = OUT[B3]
= 00110
OUT[B4] = GEN[B4] U (IN[B4]
– KILL[B4])
= 00001
U (00110 – 01010)
= 00101
Similarly
IN[B5] = OUT[B3] U OUT[B4]
= 00110
+ 00101
= 00111
and OUT[B5] = GEN[B5] U (IN[B5]
– KILL[B5])
= 00000
+ (00111 – 00000)
= 00111
Use of Reaching
Definitions Analysis
Goal: Potential
write-read (flow) data dependences
Program
understanding, like slicing
Compiler
optimizations
Dataflow
based testing
Semantic
checks, like use of uninitialized variables
Might
also find write-write (output) dependencies
