Question 37

A variable is live at the exit of block $B$ if it is used along some execution path starting from an outgoing edge of $B$ before being redefined.

1. In block $B_4$: statements are $i = a + 1$. It uses variable $a$ and defines $i$. At the exit of $B_4$, control can loop back to $B_2$, where $i = i + 1$ and $j = j - 1$ use variables $i$ and $j$, while $a$ may be used in future iterations. Hence $\text{LiveOut}(B_4) = \{a, i, j\}$.
2. In block $B_3$: statement is $a = 20$. Successor is $B_4$ (and through loop back to $B_2$). At exit of $B_3$, $i$ is immediately overwritten by $i = a + 1$ in $B_4$, but $j$ is needed in $B_2$, and $a$ is used in $B_4$. Hence $\text{LiveOut}(B_3) = \{a, j\}$.
3. In block $B_2$: uses $i, j$ and updates them. Successors are $B_3$ and $B_4$. If taking the edge to $B_4$, $a$ (from $B_1$) is used, and $j$ is preserved. Hence $\text{LiveOut}(B_2) = \{a, j\}$.
4. In block $B_1$: defines $i = m - 1$, $j = n$, $a = 10$. The successor $B_2$ immediately uses $i$ and $j$, and $a$ is preserved. Hence $\text{LiveOut}(B_1) = \{a, i, j\}$.

Thus, the live variable sets at block exits are B1: {a, i, j}, B2: {a, j}, B3: {a, j}, B4: {a, i, j}.