I am asked to write the reaching definition for the following code and I am wondering if my solution is correct? am I even on the right track? I truly appreciate any help or hint. Thank you.
Code:
a = 0;
while (a < 100) {
b = a + 1
c = c + b
a = b * 2
}
return c;
Step #1: finding blocks and labeling
a = 0; // block 1 | a1
while (a < 100) // block 2 |
b = a + 1 // block 3 | b2
c = c + b | c3
a = b * 2 | a3
return c; // block 3 |
Step #2: finding GEN and KILL sets for each block
| BLOCK | GEN | KILL |
|---|---|---|
| 1 | a1 | a3 |
| 2 | ∅ | ∅ |
| 3 | b3, c3, a3 | a1 |
| 4 | ∅ | ∅ |
Step #4: reviewing the algorithm to find IN and OUT sets
input: control flow graph CFG = (N, E, Entry, Exit)
// Boundary condition
OUT[Entry] = ∅
// Initialization for an iterative algorithm
For each basic block B other than Entry
OUT[B] = ∅
// iterate
While (changes to any OUT occur) {
For each basic block B other than Entry {
in[B] = ∪ (out[p]), for all predecessors p of B
out[B] = fB(in[B]) // out[B]=gen[B]∪(in[B]-kill[B])
}
Step #5 deriving the IN and OUT sets
| BLOCK | GEN | KILL | IN | OUT |
|---|---|---|---|---|
| ENTRY | ∅ | |||
| 1 | a1 | a3 | ∅ | a1 |
| 2 | ∅ | ∅ | a1 | a1 |
| 3 | b3, c3, a3 | a1 | a1 | b3, c3, a3 |
| 4 | ∅ | ∅ | b3, c3, a3, a1 | b3, c3, a3, a1 |
| EXIT | b3, c3, a3, a1 | b3, c3, a3, a1 |
