Code Optimization Questions and Answers

Answer: A

The live variables at block exits are B1:{a, b, c, e, f}, B2:{d, e}, B3:{b, c, e, f}, B4:∅.

Liveness flows backwards: OUT(B) is the union of IN over B's successors, and IN(B) = USE(B) ∪ (OUT(B) - DEF(B)). The edges are B1 → B2, B1 → B3, B3 → B1 and B2 → B4.

• B4 (g = d + e) leads to EXIT, and g is never used: OUT(B4) = ∅, IN(B4) = {d, e}.
• B2 (d = a + e): OUT(B2) = IN(B4) = {d, e}; IN(B2) = {a, e}.
• B1 (a = b + c) and B3 (e = a + f) form a loop. Iterating to a fixed point: IN(B1) = {b, c, e, f} and IN(B3) = {a, b, c, f}.
• OUT(B1) = IN(B2) ∪ IN(B3) = {a, b, c, e, f}; OUT(B3) = IN(B1) = {b, c, e, f}.

The options with B1:∅ ignore that a is used in both successors of B1. The option with B3:{c, e, f} drops b, which is live because B1, reached from B3, uses it.

Answer: D

The live sets at block exits are B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}.

A variable is live at a point if some path from there uses it before redefining it. Work backwards from the uses, assuming nothing is live at EXIT:

• B2 uses i and j (i = i + 1, j = j - 1) before defining them, so both are live on entry to B2.
• B4 uses a, then redefines i. Its successors are B2 and EXIT, so live-out of B4 = live-in of B2.
• B3 defines a and uses nothing; B2 flows to B3 and B4.

Solving: live-in(B4) = {a} plus (live-out(B4) minus {i}) = {a, j}; live-in(B3) = {a, j} minus {a} = {j}; live-out(B2) = {j} plus {a, j} = {a, j}; live-in(B2) = {i, j} plus ({a, j} minus {i, j}) = {a, i, j}, which is live-out of both B1 and B4. B3's exit set is live-in(B4) = {a, j}.

The first two options drop i and j at B1's exit although B2 reads them at once. The third keeps i live after B2, but i is redefined in B4 before any use on that path.