
Which one of the following options is the set of live variables at the exit point of each basic block?
Correct : a
The correct answer is Option A — B1: {a, b, c, e, f}, B2: {d, e}, B3: {b, c, e, f}, B4: φ.
Live variable analysis is computed backwards from EXIT. A variable is live at a point if it will be used before being redefined on some path from that point. For each block: USE = variables read before being written; DEF = variables written. LiveOut[B] = union of LiveIn of all successors; LiveIn[B] = USE[B] ∪ (LiveOut[B] − DEF[B]).
B4 (g = d + e): No successors → LiveOut[B4] = φ. LiveIn[B4] = {d, e}.
B2 (d = a + e): Successor is B4 → LiveOut[B2] = LiveIn[B4] = {d, e}. LiveIn[B2] = {a, e} ∪ ({d, e} − {d}) = {a, e}.
B3 (e = a + f): Successor is B1 (back edge) → LiveOut[B3] = LiveIn[B1]. After iterating to fixed point: LiveIn[B1] = {b, c, e, f} → LiveOut[B3] = {b, c, e, f}. LiveIn[B3] = {a, f} ∪ ({b, c, e, f} − {e}) = {a, b, c, f}.
B1 (a = b + c): Successors are B2 and B3 → LiveOut[B1] = LiveIn[B2] ∪ LiveIn[B3] = {a, e} ∪ {a, b, c, f} = {a, b, c, e, f}. LiveIn[B1] = {b, c} ∪ ({a, b, c, e, f} − {a}) = {b, c, e, f}.
The iteration converges with LiveOut values: B1 = {a, b, c, e, f}, B2 = {d, e}, B3 = {b, c, e, f}, B4 = φ.
Similar Questions
Total Unique Visitors