Question

Consider the control flow graph shown. Which one of the following choices correctly lists the set of live variables at the exit point of each basic block? 

• A. B1: {}, B2: {a}, B3: {a}, B4: {a}
• B. B1: {i, j}, B2: {a}, B3: {a}, B4: {i}
• C. B1: {a, i, j}, B2: {a, i, j}, B3: {a, i}, B4: {a}
• D. B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}

Hint:

Live variable analysis flows backward}: start from the use points and propagate towards the entry. A variable is live if it is used along some path before being redefined.

Answer 1

The Correct Option is D

Step 1: Recall live variable analysis.
A variable is live at a program point if its value will be used on some path in the future before being redefined.

Step 2: Analyze block B4.
B4 computes \(i = a + 1\). Hence, \(a\) must be live at the entry of B4.
After B4, control flows back to B2, so both \(i\) and \(j\) may be needed again.
Thus, live set at exit of B4: {a, i, j}.

Step 3: Analyze block B3.
B3 assigns \(a = 20\) and flows into B4. In B4, \(a\) is used. Hence, \(a\) must be live at B3’s exit.
Also, since B4 requires \(j\) through the loop, \(j\) is live too.
Thus, exit(B3) = {a, j}.

Step 4: Analyze block B2.
B2 assigns \(i = i + 1\) and \(j = j - 1\). Its successors are B3 and B4.
- From B3: exit(B3) = {a, j}.
- From B4: exit(B4) = {a, i, j}.
So, overall live variables at exit(B2) = {a, j} (because \(i\) defined in B2 is redefined before use).

Step 5: Analyze block B1.
B1 initializes \(i = m-1, j = n, a = 10\). Its successor is B2, where live set is {a, j}. Also, eventually \(i\) is required later in the loop.
Thus, exit(B1) = {a, i, j}.

\[ \boxed{\text{B1: \{a, i, j\}, \; B2: \{a, j\}, \; B3: \{a, j\}, \; B4: \{a, i, j\}}} \]