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

To solve the given problem, we need to determine the set of live variables at the exit point of each basic block. A live variable is a variable that holds a value that may be needed in the future. We analyze each block as follows:

1. B4: {a, i, j} at Exit
   • Block B4 updates the value of i using a. Thus, a and any variables needed in future blocks must be live.
   • The loop may iterate back, thus making i and j live as they are used again in block B2.
2. B3: {a, j} at Exit
   • Block B3 assigns a new value to a. However, j remains live to be used in block B2.
   • There's no further use of i in B3, hence not included.
3. B2: {a, j} at Exit
   • Block B2 modifies both i and j. However, a must be live because it's used in B4 for calculating the new value of i.
   • The live status of j is preserved as it's involved in the loop.
4. B1: {a, i, j} at Exit
   • All initialized variables are live since i, j, and a are directly used or involved in subsequent operations.

Thus, the correct set of live variables at the exit of each block matches the choice:

B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}