The GATE Grind

GATE 2026 CS (CS2) – Question 45

Compiler Design · Code Optimization and Data Flow Analysis · 2 marks · Multiple choice

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?

  1. B1: {a, b, c, e, f}, B2: {d, e}, B3: {b, c, e, f}, B4: $\emptyset$
  2. B1: $\emptyset$, B2: {d, e}, B3: {a, c, f}, B4: $\emptyset$
  3. B1: {a, b, c, e, f}, B2: {d, e}, B3: {c, e, f}, B4: $\emptyset$
  4. B1: $\emptyset$, B2: {d, e, f}, B3: {a, b, c, e, f}, B4: $\emptyset$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) B1: {a, b, c, e, f}, B2: {d, e}, B3: {b, c, e, f}, B4: $\emptyset$

Explanation

From liveness analysis on the given control-flow graph, block $B4$ has no live variables at exit. Block $B2$ has $\{d,e\}$ live at exit. The variables needed at the entry of $B3$ are $\{a,f,b,c\}$, so combining this with the effect of $B1$ gives exit$(B1)=\{a,b,c,e,f\}$. Also, exit$(B3)=\{b,c,e,f\}$. Therefore, option (A) matches the correct live-variable sets. This question depends on the control-flow graph figure.