LI.6.4 Liveness analysis · GATE 2027 Compiler Design

ACompressed recap

🧾

A variable is live at a point if its current value may be read later before being overwritten. Liveness is a backward may problem: IN = use ∪ (OUT − def), OUT = union of the successors’ IN. Inside a block, sweep backwards. Liveness enables dead-code elimination and register allocation (variables live together need different registers; in straight-line code, the largest live set gives the register count).

BMerged rule card

6.4 Liveness analysis: live variables at each point; what liveness is used for

x live at p: its value may be used on some path from p before redefinition.
use[B]: read before written in B; def[B]: assigned in B.
IN = use ∪ (OUT − def); OUT = ∪ IN of successors; backward; start ∅.
Inside a block, backwards: remove target, add operands.
Uses: dead code (dead after assignment), register allocation (max live, interference).

CInterleaved GATE-style questions

Q1NAT2 marksLiveness

In the 6-block flow graph of Lesson 6.4, how many variables are live at the start of B6?

Numerical answer: ________

Q2MCQ1 markDead

An assignment x = y + z is dead if:

(A) y is dead after it
(B) x is dead immediately after it
(C) z is live before it
(D) x was assigned before

Q3MCQ1 markMeet

At a block with two successors, OUT is:

(A) the intersection of the successors’ IN
(B) the union of the successors’ IN
(C) the successors’ OUT
(D) empty

Q4NAT1 markRegisters

Straight-line code whose live sets have sizes 2, 3, 4, 2 needs at least how many registers without spilling (simple model)?

Numerical answer: ________

Q5MCQ2 marksLiveness

In B1: x = a + b, y = x * 2; B2: a = y − 1 → B1; B3: z = x + y (edges B1→B2, B1→B3, B2→B1), OUT[B1] is:

(A) { x, y }
(B) { b, x, y }
(C) { a, b }
(D) { y }

Q6MSQ1 markuse/def

For a = b + c; b = a * 2; c = c + 1, which are in use[B]?

(A) a
(B) b
(C) c
(D) none

Q7MCQ1 markInterference

Two variables cannot share a register if:

(A) they have the same type
(B) they are live at the same point
(C) one is a temporary
(D) they are in different blocks

Q8NAT2 marksLiveness

In the straight-line block of Lesson 6.4 (p = a + b …), how many variables are live just before q = p * c?

Numerical answer: ________