Consider the control flow graph shown. Which one of the following choices…

Key insight: compute live variables by iterating LiveIn = Use ∪ (LiveOut − Def) and LiveOut = ⋃ LiveIn(successors) to a fixed point.

• Compute Use and Def for each block:

  • B1: Def = {i, j, a}, Use = {}

  • B2: Def = {i, j}, Use = {i, j}

  • B3: Def = {a}, Use = {}

  • B4: Def = {i}, Use = {a}

Reasoning (brief):

• B4 uses a, so a must be live into B4 and therefore live-out of its predecessors.

• B2 reads i and j, so i and j are live-in to B2. Because there is a loop from B4 back to B2, values that reach B2 can come from B1 or B4, making i and j live-out where needed.

• i is not live-out of B2 because along all paths from B2 the next write to i occurs in B4 (i = a + 1), so the i defined in B2 is overwritten before any future use.

Fixed-point result (live variables at the exit of each basic block):

• B1 (exit): {a, i, j}

• B2 (exit): {a, j}

• B3 (exit): {a, j}

• B4 (exit): {a, i, j}

Thus the correct listing of live variables at block exits is B1:{a, i, j}, B2:{a, j}, B3:{a, j}, B4:{a, i, j}.