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?
Show 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.
Step 1: Understanding the Question.
We are given a control flow graph with four basic blocks, \(B_1: a=b+c\), \(B_2: d=a+e\), \(B_3: e=a+f\), \(B_4: g=d+e\), where \(B_1\) flows into both \(B_2\) and \(B_3\), \(B_3\) loops back into \(B_1\), and \(B_2\) flows into \(B_4\) which is the exit. A variable is live at a program point if there is some path from that point to a later use of the variable without an intervening redefinition. We need live-out, the set of live variables right at the exit of each block, which requires a backward data-flow analysis.
Step 2: Recall the live variable equations.
For each block, define \(use(B)\) as the variables read before being written in that block, and \(def(B)\) as the variables written in that block. Then
\[ live\text{-}in(B) = use(B) \cup (live\text{-}out(B) - def(B)) \]
\[ live\text{-}out(B) = \bigcup_{S \text{ successor of } B} live\text{-}in(S) \]
Step 3: Write down use and def for each block.
\(B_1: a=b+c \Rightarrow def=\{a\}, use=\{b,c\}\)
\(B_2: d=a+e \Rightarrow def=\{d\}, use=\{a,e\}\)
\(B_3: e=a+f \Rightarrow def=\{e\}, use=\{a,f\}\)
\(B_4: g=d+e \Rightarrow def=\{g\}, use=\{d,e\}\)
Step 4: Start from the exit and work backward through the acyclic part.
\(B_4\) is the last block before EXIT, and nothing is live after EXIT, so
\[ live\text{-}out(B_4) = \emptyset,\quad live\text{-}in(B_4) = \{d,e\} \cup (\emptyset - \{g\}) = \{d,e\} \]
\(B_2\)'s only successor is \(B_4\), so
\[ live\text{-}out(B_2) = \{d,e\},\quad live\text{-}in(B_2) = \{a,e\} \cup (\{d,e\}-\{d\}) = \{a,e\} \]
Step 5: Handle the loop between \(B_1\) and \(B_3\) with repeated passes.
\(B_1\) has two successors, \(B_2\) and \(B_3\); \(B_3\) has one successor, \(B_1\). Since this is a cycle we must iterate until the sets stop changing. On the first pass, start with \(live\text{-}in(B_3)=\emptyset\):
\[ live\text{-}out(B_1) = live\text{-}in(B_2)\cup live\text{-}in(B_3) = \{a,e\}\cup\emptyset = \{a,e\} \]
\[ live\text{-}in(B_1) = \{b,c\}\cup(\{a,e\}-\{a\}) = \{b,c,e\} \]
\[ live\text{-}out(B_3) = live\text{-}in(B_1) = \{b,c,e\} \]
\[ live\text{-}in(B_3) = \{a,f\}\cup(\{b,c,e\}-\{e\}) = \{a,b,c,f\} \]
Step 6: Feed the updated \(live\text{-}in(B_3)\) back into \(B_1\) and repeat.
\[ live\text{-}out(B_1) = \{a,e\}\cup\{a,b,c,f\} = \{a,b,c,e,f\} \]
\[ live\text{-}in(B_1) = \{b,c\}\cup(\{a,b,c,e,f\}-\{a\}) = \{b,c,e,f\} \]
\[ live\text{-}out(B_3) = live\text{-}in(B_1) = \{b,c,e,f\} \]
\[ live\text{-}in(B_3) = \{a,f\}\cup(\{b,c,e,f\}-\{e\}) = \{a,b,c,f\} \]
This matches the previous pass's \(live\text{-}in(B_3)\), so the values have stabilized; one more pass confirms \(live\text{-}out(B_1)\) and \(live\text{-}in(B_1)\) also stay the same.
