GATE 2026 CS2 Q.45: solution and answer

GATE 2026 · CS2Q.45 · 2 marks · MCQ

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?

GATE 2026 CS2 question 45: Control flow graph. — Figure from the GATE 2026 CS2 paper. It is part of the question.

(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:∅

Answer and solution

ANSWER

The live variables at the exit of each block are B1: {a, b, c, e, f}, B2: {d, e}, B3: {b, c, e, f}, B4: ∅. This is option A.

Official answer: ASource: Official answer key, GATE 2026 CS2 (IIT Guwahati)

A variable is live at a point if its current value may be used on some path before it is redefined. Liveness runs backward: $OUT (B) = ⋃_{S \in succ (B)} IN (S)$ and $IN (B) = use (B) \cup (OUT (B) - def (B))$ .
Block use and def sets: B1 use ${b, c}$ , def ${a}$ . B2 use ${a, e}$ , def ${d}$ . B3 use ${a, f}$ , def ${e}$ . B4 use ${d, e}$ , def ${g}$ . Successors: B1 to B2 and B3, B2 to B4, B3 to B1, B4 to EXIT.
B4: $OUT (B 4) = \emptyset$ because nothing is used after EXIT. So $IN (B 4) = {d, e}$ .
B2: $OUT (B 2) = IN (B 4) = {d, e}$ , and $IN (B 2) = {a, e} \cup ({d, e} - {d}) = {a, e}$ .
B1 and B3 form a loop, so iterate from empty sets. Start with $IN (B 1) = \emptyset$ . Then $OUT (B 3) = \emptyset$ and $IN (B 3) = {a, f}$ .
Then $OUT (B 1) = IN (B 2) \cup IN (B 3) = {a, e, f}$ and $IN (B 1) = {b, c} \cup ({a, e, f} - {a}) = {b, c, e, f}$ .
Second pass: $OUT (B 3) = IN (B 1) = {b, c, e, f}$ , so $IN (B 3) = {a, f} \cup ({b, c, e, f} - {e}) = {a, b, c, f}$ .
Then $OUT (B 1) = {a, e} \cup {a, b, c, f} = {a, b, c, e, f}$ and $IN (B 1) = {b, c} \cup {b, c, e, f} = {b, c, e, f}$ . This is unchanged, so a fixed point is reached.
Live at block exits: B1 ${a, b, c, e, f}$ , B2 ${d, e}$ , B3 ${b, c, e, f}$ , B4 $\emptyset$ . This is option A.

KEY IDEA

Live-variable analysis is a backward data-flow problem. Compute OUT as the union of the successors' IN sets, and IN = use ∪ (OUT − def). Where blocks form a loop, iterate from empty sets until nothing changes.

WATCH OUT FOR

Reporting the live-in sets instead of the live-out sets. Another slip is stopping after one pass over the B1–B3 loop, which leaves B3's exit set short of {b, c, e, f}. A third is forgetting that B3 redefines e, so e is removed from IN(B3) and enters OUT(B1) only through B2's use of e.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 6 Optimisation questions, with notes

GATE 2026 CS2 Q.45: solution and answer

Answer and solution

More Optimisation questions