Computer Sciences > GATE 2026 SET-2 > Compiler Design
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: φ

Correct : a

The correct answer is Option A — B1: {a, b, c, e, f}, B2: {d, e}, B3: {b, c, e, f}, B4: φ.
Live variable analysis is computed backwards from EXIT. A variable is live at a point if it will be used before being redefined on some path from that point. For each block: USE = variables read before being written; DEF = variables written. LiveOut[B] = union of LiveIn of all successors; LiveIn[B] = USE[B] ∪ (LiveOut[B] − DEF[B]).
B4 (g = d + e): No successors → LiveOut[B4] = φ. LiveIn[B4] = {d, e}.
B2 (d = a + e): Successor is B4 → LiveOut[B2] = LiveIn[B4] = {d, e}. LiveIn[B2] = {a, e} ∪ ({d, e} − {d}) = {a, e}.
B3 (e = a + f): Successor is B1 (back edge) → LiveOut[B3] = LiveIn[B1]. After iterating to fixed point: LiveIn[B1] = {b, c, e, f} → LiveOut[B3] = {b, c, e, f}. LiveIn[B3] = {a, f} ∪ ({b, c, e, f} − {e}) = {a, b, c, f}.
B1 (a = b + c): Successors are B2 and B3 → LiveOut[B1] = LiveIn[B2] ∪ LiveIn[B3] = {a, e} ∪ {a, b, c, f} = {a, b, c, e, f}. LiveIn[B1] = {b, c} ∪ ({a, b, c, e, f} − {a}) = {b, c, e, f}.
The iteration converges with LiveOut values: B1 = {a, b, c, e, f}, B2 = {d, e}, B3 = {b, c, e, f}, B4 = φ.

Similar Questions

Match the following according to input(from the left column) to the compiler phase(in the right column) that process it: (P)Syntax Tree (i)...
#168 MCQ
Consider the following code segment. x = u - t; y = x * v; x = y + w; y = t - z; y = x * y; The minimum number of total variables required to convert the abo...
#575 Fill in the Blanks
Consider the following grammar: stmt -> if expr then else expr; stmt | ε expr -> term relop term | term term -> id | number id -> a | b | c number -> [...
#594 Fill in the Blanks

Related Topics

GATE CS 2026 Set-2 Q45 live variable analysis GATE 2026 control flow graph GATE CS dataflow analysis GATE 2026 liveness analysis basic blocks GATE CS compiler design GATE 2026 LiveIn LiveOut GATE CS 2026 backwards dataflow analysis GATE

Unique Visitor Count

Total Unique Visitors

Loading......