Consider the control flow graph given below. Which one of the following options is the set of live variables at the exit point of each basic block?

To perform liveness analysis, we use the backward data-flow equations:

### Step 1: Identify $\text{use}$ and $\text{def}$ sets for each block

• Block B1 ($a = b + c$):

  $$\text{use}[B1] = \{b, c\}, \quad \text{def}[B1] = \{a\}$$

• Block B2 ($d = a + e$):

  $$\text{use}[B2] = \{a, e\}, \quad \text{def}[B2] = \{d\}$$

• Block B3 ($e = a + f$):

  $$\text{use}[B3] = \{a, f\}, \quad \text{def}[B3] = \{e\}$$

• Block B4 ($g = d + e$):

  $$\text{use}[B4] = \{d, e\}, \quad \text{def}[B4] = \{g\}$$

### Step 2: Compute $\text{IN}$ and $\text{OUT}$ sets iteratively

1. Block B4:

   • $\text{OUT}[B4] = \emptyset$

   • $\text{IN}[B4] = \{d, e\} \cup (\emptyset \setminus \{g\}) = \{d, e\}$

2. Block B2:

   • $\text{OUT}[B2] = \text{IN}[B4] = \{d, e\}$

   • $\text{IN}[B2] = \{a, e\} \cup (\{d, e\} \setminus \{d\}) = \{a, e\}$

3. Iteration 1 for B3 and B1:

   • Initializing $\text{IN}[B1] = \emptyset$:

     • $\text{OUT}[B3] = \text{IN}[B1] = \emptyset$

     • $\text{IN}[B3] = \{a, f\} \cup (\emptyset \setminus \{e\}) = \{a, f\}$

   • For B1:

     • $\text{OUT}[B1] = \text{IN}[B2] \cup \text{IN}[B3] = \{a, e\} \cup \{a, f\} = \{a, e, f\}$

     • $\text{IN}[B1] = \{b, c\} \cup (\{a, e, f\} \setminus \{a\}) = \{b, c, e, f\}$

4. Iteration 2:

   • For B3:

     • $\text{OUT}[B3] = \text{IN}[B1] = \{b, c, e, f\}$

     • $\text{IN}[B3] = \{a, f\} \cup (\{b, c, e, f\} \setminus \{e\}) = \{a, b, c, f\}$

   • For B1:

     • $\text{OUT}[B1] = \text{IN}[B2] \cup \text{IN}[B3] = \{a, e\} \cup \{a, b, c, f\} = \{a, b, c, e, f\}$

     • $\text{IN}[B1] = \{b, c\} \cup (\{a, b, c, e, f\} \setminus \{a\}) = \{b, c, e, f\}$

5. Iteration 3 (Convergence):

   • Values do not change, so the analysis has converged.

### Final $\text{OUT}$ sets (live variables at exit point):

• B1: $\{a, b, c, e, f\}$

• B2: $\{d, e\}$

• B3: $\{b, c, e, f\}$

• B4: $\emptyset$

Thus, (A) is the correct option [CS-2 Key].