Question

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?

• A. \(B_1:\{a,b,c,e,f\},\ B_2:\{d,e\},\ B_3:\{b,c,e,f\},\ B_4:\emptyset\)
• B. \(B_1:\emptyset,\ B_2:\{d,e\},\ B_3:\{a,c,f\},\ B_4:\emptyset\)
• C. \(B_1:\{a,b,c,e,f\},\ B_2:\{d,e\},\ B_3:\{c,e,f\},\ B_4:\emptyset\)
• D. \(B_1:\emptyset,\ B_2:\{d,e,f\},\ B_3:\{a,b,c,e,f\},\ B_4:\emptyset\)

Hint:

Live-out of a block is the union of live-in of its successors; since B1 and B3 form a loop, iterate the equations until the sets stop changing before reading off the live-out values.

Answer 1

The Correct Option is A

Step 1: List what each block reads and writes.
$B_1: a=b+c$ reads $\{b,c\}$, writes $a$. $B_2: d=a+e$ reads $\{a,e\}$, writes $d$. $B_3: e=a+f$ reads $\{a,f\}$, writes $e$. $B_4: g=d+e$ reads $\{d,e\}$, writes $g$. The control leaves ENTRY, passes through $B_1$, splits to $B_2$ and $B_3$, with $B_3$ looping back to $B_1$, while $B_2$ continues to $B_4$ and then to EXIT.

Step 2: Build a small table and fill it from the bottom up.
Since live variable analysis reads backward, start at the block closest to EXIT. $B_4$ has no successor, so whatever it reads is exactly what must be live coming in: $live\text{-}in(B_4)=\{d,e\}$, and $live\text{-}out(B_4)=\emptyset$.

Step 3: Move to \(B_2\), whose only successor is \(B_4\).
$live\text{-}out(B_2)=live\text{-}in(B_4)=\{d,e\}$. Remove what $B_2$ overwrites ($d$) and add what it reads ($a,e$):
\[ live\text{-}in(B_2)=(\{d,e\}\setminus\{d\})\cup\{a,e\}=\{a,e\} \]

Step 4: The loop needs a guess-and-correct pass.
Guess $live\text{-}in(B_3)=\emptyset$ at first. Then
\[ live\text{-}out(B_1)=live\text{-}in(B_2)\cup live\text{-}in(B_3)=\{a,e\} \]
\[ live\text{-}in(B_1)=(\{a,e\}\setminus\{a\})\cup\{b,c\}=\{b,c,e\} \]
Since $B_3\to B_1$, $live\text{-}out(B_3)=live\text{-}in(B_1)=\{b,c,e\}$, so
\[ live\text{-}in(B_3)=(\{b,c,e\}\setminus\{e\})\cup\{a,f\}=\{a,b,c,f\} \]
This differs from our starting guess of $\emptyset$, so we redo the loop with this better guess.

Step 5: Second pass with the corrected \(live\text{-}in(B_3)\).
\[ live\text{-}out(B_1)=\{a,e\}\cup\{a,b,c,f\}=\{a,b,c,e,f\} \]
\[ live\text{-}in(B_1)=(\{a,b,c,e,f\}\setminus\{a\})\cup\{b,c\}=\{b,c,e,f\} \]
\[ live\text{-}out(B_3)=live\text{-}in(B_1)=\{b,c,e,f\} \]
\[ live\text{-}in(B_3)=(\{b,c,e,f\}\setminus\{e\})\cup\{a,f\}=\{a,b,c,f\} \]
This matches the guess we fed in, so the loop values have settled.

Step 6: Write down the four live-out answers asked for.
\[ B_1:\{a,b,c,e,f\}\quad B_2:\{d,e\}\quad B_3:\{b,c,e,f\}\quad B_4:\emptyset \]

Step 7: Match to the options and conclude.
This exact grouping appears as option (A); the other options either wrongly zero out $B_1$, drop $b$ from $B_3$, or invent an $f$ in $B_2$ that block never touches.
\[ \boxed{B_1:\{a,b,c,e,f\},\ B_2:\{d,e\},\ B_3:\{b,c,e,f\},\ B_4:\emptyset} \]