A variable is live at a point if some later instruction can read it before anything overwrites it. That one idea drives dead code elimination, common subexpression elimination and register allocation, and compilers compute it backwards, from a block's successors to its entry.
These 12 solved questions run from the IN and OUT equations through available expressions to counting the minimum registers a code segment needs. Attempt each on paper first, and treat the register questions as arithmetic: find the peak live set, then build an allocation that reaches it. For wider revision, use GATE CS Exam Preparation.
1. Liveness equations and live-at-a-point MCQs
Use these backward-analysis equations:
OUT(B) = union of IN sets of all successors
IN(B) = USE(B) union (OUT(B) - DEF(B))
Successor facts combine by union because any path may keep a variable live.
Q1. Relate two consecutive statements, GATE 2021
For a statement S in a program, in the context of liveness analysis, the following sets are defined:
USE(S): the set of variables used in S
IN(S): the set of variables that are live at the entry of S
OUT(S): the set of variables that are live at the exit of S
Consider a basic block that consists of two statements, S₁ followed by S₂. Which one of the following statements is correct?
(A) OUT(S₁) = IN(S₂)
(B) OUT(S₁) = IN(S₁) ∪ USE(S₁)
(C) OUT(S₁) = IN(S₂) ∪ OUT(S₂)
(D) OUT(S₁) = USE(S₁) ∪ IN(S₂)
Answer: (A). The exit of S₁ and the entry of S₂ are the same program point, so the two sets must agree. Nothing is read or written in between, so neither USE(S₁) nor OUT(S₂) belongs here.
Q2. Find variables live at two CFG statements, GATE 2015
A variable x is said to be live at a statement Sᵢ in a program if the following three conditions hold simultaneously:
i. There exists a statement Sⱼ that uses x
ii. There is a path from Sᵢ to Sⱼ in the flow graph corresponding to the program
iii. The path has no intervening assignment to x including at Sᵢ and Sⱼ
The variables which are live both at the statement in basic block 2 and at the statement in basic block 3 of the above control flow graph are
(A) p, s, u
(B) r, s, u
(C) r, u
(D) q, v
Answer: (C) r, u. B2 reads r and u, and r is read again in B4, so both are live there. At B3 the live set is {r, s, u, v}. The two share only r and u: B1 recomputes s before B3 reads it, and v is overwritten inside B2.
2. Data-flow analysis and optimisation-classification MCQs
These three ask you to name the analysis rather than run it, so keep the direction and the combining rule attached to each. For the transformations themselves, work through Blocks, Loops and Methods MCQs.
Technique | Direction or scope | Main use |
|---|---|---|
Liveness | Backward, successor union | Dead code; register allocation |
Reaching definitions | Forward | Reaching definitions |
Available expressions | Forward, predecessor intersection | Common-subexpression elimination |
Peephole optimisation | Contiguous window | Local rewrites |
Q3. Identify what is not a common data-flow analysis, TPSC 2024
Which of the following is NOT a common data flow analysis technique used in compilers ?
(A) Constant propagation
(B) Reaching definitions
(C) Liveness analysis
(D) Type inference
Answer: (D) Type inference. The other three run on the control flow graph, pushing sets around until they stop changing. Type inference solves type constraints and never asks which path reached a statement.
Q4. Separate constant folding from common-subexpression elimination, GATE 2014
Which one of the following is FALSE?
(A) A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end
(B) Available expression analysis can be used for common subexpression elimination
(C) Live variable analysis can be used for dead code elimination
(D) x = 4 * 5 ⇒ x = 20 is an example of common subexpression elimination
Answer: (D). Both operands of 4 * 5 are known at compile time, so rewriting it as 20 is constant folding. Common subexpression elimination needs the expression computed twice, with the second occurrence reusing the first result.
Q5. Find the false statement about a peephole window, ISRO 2011 and TPSC 2025
Which of the following statements about peephole optimization is False?
(A) It is applied to a small part of the code
(B) It can be used to optimize intermediate code
(C) To get the best out of this, it has to be applied repeatedly
(D) It can be applied to the portion of the code that is not contiguous
Answer: (D). A peephole is a short window sliding over consecutive instructions, so it rewrites only a contiguous stretch. The window being small is also why one rewrite exposes another, and why the pass is run repeatedly.
3. Definition-use chains and available-expression MCQs
A DU-chain links a definition to every use it can reach before the variable is redefined. An expression is available at a point only if every incoming path computes it and no operand has changed since.
Q6. Recognise every true property of DU-chains, ISRO 2018
DU-chains(Definition-Use) in compiler design
(A) consist of a definition of a variable and all its uses, reachable from that definition
(B) are created using a form of static code analysis
(C) are prerequisite for many compiler optimization including constant propagation and common sub-expression elimination
(D) All of the above
Answer: (D) All of the above. A DU-chain records a definition with every use it reaches without an intervening redefinition, built statically before the program runs. Constant propagation walks those links to carry a known value to its uses.
Q7. Intersect predecessor facts for available expressions, GATE 2026
Consider the control flow graph shown in the figure.
Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B4 and B5? Note: All the variables are integers.
(A) B4: { b+i } B5: { c+m }
(B) B4: { g*k } B5: { c+m }
(C) B4: { g*k, b+i } B5: { }
(D) B4: { g*k } B5: { }
Answer: (D). B4 is reached from both B2 and B3, so an expression is available there only if both paths compute it and neither kills it. B2 leaves b+i, g*k and c*4; B3 leaves g*k and c+m, since b = c + m kills b+i. The intersection is g*k, so x = g * k is redundant in B4 and y = b + i is not. In B5, c+m never survives the B2 path, so nothing is redundant.
4. Liveness, interference and register-allocation MCQs
Two values live at the same point cannot share a register, so overlapping live ranges become edges in an interference graph. Allocating registers is colouring that graph.
Q8. Pick the optimisation that uses live-variable analysis, GATE 2025
Which ONE of the following techniques used in compiler code optimization uses live variable analysis?
(A) Run-time function call management
(B) Register assignment to variables
(C) Strength reduction
(D) Constant folding
Answer: (B) Register assignment to variables. The allocator needs the live set at every point to know which values interfere. Strength reduction and constant folding never consult it.
Q9. Match register allocation to graph colouring, MPPSC 2025
Match all items in Group – 1 with correct options from those given in Group – 2.
Group – 1
P. Intermediate representation
Q. Top-down parsing
R. Runtime environments
S. Register allocation
Group – 2
1. Activation records
2. Code generation
3. Left most derivation
4. Graph coloring
(A) P - 2, Q - 3, R - 4, S - 1
(B) P - 1, Q - 2, R - 3, S - 4
(C) P - 4, Q - 2, R - 3, S - 1
(D) P - 2, Q - 3, R - 1, S - 4
Answer: (D). Top-down parsing builds a leftmost derivation (Q-3), runtime environments are organised around activation records (R-1), and register allocation colours an interference graph (S-4). That leaves P-2: code generation consumes the intermediate representation.
5. Register-pressure MCQs with worked values
Register pressure is the size of the largest live set. Each answer needs both halves: a lower bound from the peak, and an allocation that attains it.
Q10. Evaluate an expression with the minimum registers, MPPSC 2025
Consider the expression (a - b) + e * (c + d). Let X be the minimum number of registers required by an optimal code generation algorithm for a load/store architecture, in which:
i. Only load and store instructions can have memory operands, and
ii. Arithmetic instructions can have only register or immediate operands.
The value of X is ________.
(A) 4
(B) 3
(C) 2
(D) 12
Answer: (B) 3. Compute a - b into R1, build c + d in R2 and R3, load e over R3, multiply into R2, then add R2 into R1. Two fail, because holding a - b leaves one register for c + d, which needs two on a load/store machine.
Q11. Find peak liveness across a branch, GATE 2013 and BARC 2013
The following code segment is executed on a processor which allows only register operands in its instructions. Each instruction can have at most two source operands and one destination operand. Assume that all variables are dead after this code segment.
c = a + b;
d = c * a;
e = c + a;
x = c * c;
if (x > a) {
y = a * a;
} else {
d = d * d;
e = e * e;
}What is the minimum number of registers needed in the instruction set architecture of the processor to compile this code segment without any spill to memory? Do not apply any optimization other than optimizing register allocation.
(A) 3
(B) 4
(C) 5
(D) 6
Answer: (B) 4. After e = c + a the live set is {a, c, d, e}, and at the branch it is {a, x, d, e}, so three are never enough. Four suffice: a in R1, R2 for b then c then x, d in R3 and e in R4.
Q12. Count live temporaries in a straight-line program, GATE 2010
The program below uses six temporary variables a, b, c, d, e, f.
a = 1
b = 10
c = 20
d = a + b
e = c + d
f = c + e
b = c + e
e = b + f
d = 5 + e
return d + fAssuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?
(A) 2
(B) 3
(C) 4
(D) 6
Answer: (B) 3. The live set peaks at {a, b, c} before d = a + b and at {c, e, f} before b = c + e, so two cannot work. Three do, because each value dies with its last reader: a and b at d = a + b, and c at b = c + e.
6. Liveness and data flow: a checklist for the ones you missed
Match each miss to the habit that would have caught it.
Q1 or Q2: write the equations before reading the graph, then walk it backwards.
Q3, Q4 or Q5: separate the analysis from the transformation it enables. Liveness and available expressions are analyses; folding, subexpression removal and peephole rewrites are not.
Q6 or Q7: check how facts combine. Liveness unions successor facts, availability intersects predecessor facts, and one killing definition on one path is enough.
Q8 or Q9: overlapping live ranges become interference edges, and colouring that graph is register allocation.
Q10, Q11 or Q12: list the live set after every statement and take the maximum, then build an allocation that reaches it. A peak count alone is half an answer.
7. Liveness and data-flow MCQs: the short version and next step
Liveness runs backward and unions successor facts, availability runs forward and intersects predecessor facts, and register pressure is the peak live set. Redo Q2, Q7, Q11 and Q12 unaided.
Continue with Syntax-Directed Translation and Code Optimization or Parsing in Compiler Design, or take the subject in order with the GATE Guidance by Sanchit Sir course.
