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. B1:{a, b, c, e, f}, B2:{d, e}, B3:{b, c, e, f}, B4:∅
• B. B1:∅, B2:{d, e}, B3:{a, c, f}, B4:∅
• C. B1:{a, b, c, e, f}, B2:{d, e}, B3:{c, e, f}, B4:∅
• D. B1:∅, B2:{d, e, f}, B3:{a, b, c, e, f}, B4:∅

Hint:

Live variable analysis is a backward data-flow problem: out[B] equals the union of in[successors], and in[B] equals use[B] union (out[B] minus def[B]). Start at the exit block with out = empty set and propagate backward, using the actual read/write pattern of each block's statements to get use[B] and def[B].

Answer 1

The Correct Option is A

Step 1: A variable is live on exiting a block when a future path can read its current value before overwriting it. In the actual graph B1 branches to B2/B3, B2 flows to B4, and B3 returns to B1.
Step 2: Begin at B4. Its statement \(g=d+e\) reads \(d,e\), and nothing is live after EXIT, hence \(OUT_4=\varnothing\) and \(IN_4=\{d,e\}\).
Step 3: B2 has \(d=a+e\), so its exit requires \(OUT_2=IN_4=\{d,e\}\); replacing the newly defined \(d\) by its inputs yields \(IN_2=\{a,e\}\).
Step 4: Iterate around the loop. For B3, \(e=a+f\), so its entry uses \(a,f\) and carries whatever B1 subsequently needs except its redefined \(e\). The stable sets are \(IN_1=\{b,c,e,f\}\), \(OUT_3=\{b,c,e,f\}\), and \(IN_3=\{a,b,c,f\}\).
Step 5: Since B1 can branch to either successor, \(OUT_1=IN_2\cup IN_3=\{a,b,c,e,f\}\). Thus the exit-set sequence is \((\{a,b,c,e,f\},\{d,e\},\{b,c,e,f\},\varnothing)\).
Final answer: \(\boxed{\text{(A)}}\).