GATE CS 2026 Set 2 Q.45: Intermediate Code Generation, Data Flow Analysis and Code Optimization

Consider the control flow graph given below.

Control flow graph with ENTRY leading to basic block B1 (a = b + c); B1 branches to B2 (d = a + e) and B3 (e = a + f); B3 loops back to B1; B2 leads to B4 (g = d + e) and then EXIT.

Which one of the following options is the set of live variables at the exit point of each basic block?

B1: $\{a, b, c, e, f\}$ , B2: $\{d, e\}$ , B3: $\{b, c, e, f\}$ , B4: $\emptyset$

B1: $\emptyset$ , B2: $\{d, e\}$ , B3: $\{a, c, f\}$ , B4: $\emptyset$

B1: $\{a, b, c, e, f\}$ , B2: $\{d, e\}$ , B3: $\{c, e, f\}$ , B4: $\emptyset$

B1: $\emptyset$ , B2: $\{d, e, f\}$ , B3: $\{a, b, c, e, f\}$ , B4: $\emptyset$

Official answer and solution

Official answer: A
From: Official GATE 2026 answer key

Solution

Compute $use[B]$ and $def[B]$ for each basic block and iterate the backward data-flow equations $OUT[B] = \bigcup_{S \in succ(B)} IN[S]$ and $IN[B] = use[B] \cup (OUT[B] - def[B])$ .

For each block $B_i$ , let $use[B_i]$ be variables used before definition and $def[B_i]$ be variables defined:

$B_1$ (a = b + c): $use[B_1] = \{b, c\}$ , $def[B_1] = \{a\}$
$B_2$ (d = a + e): $use[B_2] = \{a, e\}$ , $def[B_2] = \{d\}$
$B_3$ (e = a + f): $use[B_3] = \{a, f\}$ , $def[B_3] = \{e\}$
$B_4$ (g = d + e): $use[B_4] = \{d, e\}$ , $def[B_4] = \{g\}$

Backward live-variable equations:

$OUT[B_4] = \emptyset \implies IN[B_4] = \{d, e\}$ .
$OUT[B_2] = IN[B_4] = \{d, e\} \implies IN[B_2] = \{a, e\} \cup (\{d, e\} - \{d\}) = \{a, e\}$ .
Since $B_3$ initially has $IN[B_3] = \{a, f\}$ , $OUT[B_1] = IN[B_2] \cup IN[B_3]$ contains $\{a, e, f\}$ , which gives $IN[B_1] = \{b, c\} \cup (\{a, e, f\} - \{a\}) = \{b, c, e, f\}$ .
Because $B_1$ is the successor of $B_3$ , $OUT[B_3] = IN[B_1] = \{b, c, e, f\}$ , which propagates to $IN[B_3] = \{a, f\} \cup (\{b, c, e, f\} - \{e\}) = \{a, b, c, f\}$ .
Consequently, $OUT[B_1] = IN[B_2] \cup IN[B_3] = \{a, e\} \cup \{a, b, c, f\} = \{a, b, c, e, f\}$ .

Thus the fixed-point $OUT$ sets are: $B_1:\{a, b, c, e, f\}$ , $B_2:\{d, e\}$ , $B_3:\{b, c, e, f\}$ , $B_4:\emptyset$ .

Final answer

Option (A)

Common trap

Forgetting to propagate $b, c, f$ around the loop $B_1 \rightarrow B_3 \rightarrow B_1$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 45 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source