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] ∴B1and 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
0 comments:
Post a Comment