GATE CS 2026 Set 2 Q35 — Local Optimization

Live variable analysis is a backward data-flow analysis. A variable is said to be live at a given point if there is a path from that point to a use of the variable along which the variable is not redefined.

The data-flow equations for any basic block $B$ are:

Applying these equations backward from the exit block:

• Block B4: Since B4 is the exit block of the program, no variables are live at its exit. Thus, $\text{out}[\mathrm{B4}] = \varnothing$.
• Block B2: The variables $d$ and $e$ are propagated from its successors, giving $\text{out}[\mathrm{B2}] = \{\mathrm{d}, \mathrm{e}\}$.
• Block B3: Due to the loop back to the preceding blocks where $b$ is used before being redefined, the variable $b$ remains live at the exit of B3 along with $c, e, f$. Thus, $\text{out}[\mathrm{B3}] = \{\mathrm{b}, \mathrm{c}, \mathrm{e}, \mathrm{f}\}$.
• Block B1: The union of the live-in variables of its successors B2 and B3 gives $\text{out}[\mathrm{B1}] = \{\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{e}, \mathrm{f}\}$.

This matches the sets given in Option A.