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

A variable $v$ is live at a point $p$ if there exists a directed path from $p$ to a use of $v$ along which $v$ is not redefined (killed).

The data-flow equations for liveness analysis (backward analysis) are:

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

• B1: $\text{def}[B1] = \{a, i, j\}$, $\text{use}[B1] = \{m, n\}$

• B2: $\text{def}[B2] = \{i, j\}$, $\text{use}[B2] = \{i, j\}$

• B3: $\text{def}[B3] = \{a\}$, $\text{use}[B3] = \emptyset$

• B4: $\text{def}[B4] = \{i\}$, $\text{use}[B4] = \{a\}$

### Step 2: Successor relations

• $\text{succ}(B1) = \{B2\}$

• $\text{succ}(B2) = \{B3, B4\}$

• $\text{succ}(B3) = \{B4\}$

• $\text{succ}(B4) = \{B2, \text{EXIT}\}$

### Step 3: Iterative Computation of $\text{In}$ and $\text{Out}$

Iteration 1:

• $\text{Out}[B4] = \text{In}[B2] = \emptyset \implies \text{In}[B4] = \{a\} \cup (\emptyset \setminus \{i\}) = \{a\}$

• $\text{Out}[B3] = \text{In}[B4] = \{a\} \implies \text{In}[B3] = \emptyset \cup (\{a\} \setminus \{a\}) = \emptyset$

• $\text{Out}[B2] = \text{In}[B3] \cup \text{In}[B4] = \emptyset \cup \{a\} = \{a\} \implies \text{In}[B2] = \{i, j\} \cup (\{a\} \setminus \{i, j\}) = \{a, i, j\}$

• $\text{Out}[B1] = \text{In}[B2] = \{a, i, j\}$

Iteration 2:

• $\text{Out}[B4] = \text{In}[B2] = \{a, i, j\} \implies \text{In}[B4] = \{a\} \cup (\{a, i, j\} \setminus \{i\}) = \{a, j\}$

• $\text{Out}[B3] = \text{In}[B4] = \{a, j\} \implies \text{In}[B3] = \emptyset \cup (\{a, j\} \setminus \{a\}) = \{j\}$

• $\text{Out}[B2] = \text{In}[B3] \cup \text{In}[B4] = \{j\} \cup \{a, j\} = \{a, j\} \implies \text{In}[B2] = \{i, j\} \cup (\{a, j\} \setminus \{i, j\}) = \{a, i, j\}$

• $\text{Out}[B1] = \text{In}[B2] = \{a, i, j\}$

Iteration 3 (Fixed Point Reached):

• $\text{Out}[B4] = \{a, i, j\} \implies \text{In}[B4] = \{a, j\}$

• $\text{Out}[B3] = \{a, j\} \implies \text{In}[B3] = \{j\}$

• $\text{Out}[B2] = \{a, j\} \implies \text{In}[B2] = \{a, i, j\}$

• $\text{Out}[B1] = \{a, i, j\}$

Thus, the live variable sets at the exit of each block are:

• B1: $\{a, i, j\}$

• B2: $\{a, j\}$

• B3: $\{a, j\}$

• B4: $\{a, i, j\}$

This matches (D).