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: Read the actual control-flow graph. Block B1 executes \(a=b+c\) and branches to B2 or B3; B2 executes \(d=a+e\) and flows to B4; B3 executes \(e=a+f\) and loops back to B1; B4 executes \(g=d+e\) and exits.
Step 2: Use the liveness equations \(OUT[B]=\bigcup_{S\in succ(B)}IN[S]\) and \(IN[B]=USE[B]\cup(OUT[B]-DEF[B])\). The USE/DEF pairs are B1: \(\{b,c\},\{a\}\); B2: \(\{a,e\},\{d\}\); B3: \(\{a,f\},\{e\}\); B4: \(\{d,e\},\{g\}\).
Step 3: At the exit, \(OUT[B4]=\varnothing\), so \(IN[B4]=\{d,e\}\). Therefore \(OUT[B2]=\{d,e\}\) and \(IN[B2]=\{a,e\}\).
Step 4: Solve the B1-B3 back edge to its fixed point. The loop gives \(IN[B1]=\{b,c,e,f\}\), \(OUT[B3]=IN[B1]=\{b,c,e,f\}\), and \(IN[B3]=\{a,b,c,f\}\). Thus \(OUT[B1]=IN[B2]\cup IN[B3]=\{a,b,c,e,f\}\).
Step 5: Collect the requested exit sets: B1 \(\{a,b,c,e,f\}\), B2 \(\{d,e\}\), B3 \(\{b,c,e,f\}\), and B4 \(\varnothing\).
Final answer: \(\boxed{\text{Option (A)}}\).