Medium ●●

⚙️ Code Generation & Register Allocation

Why it matters: Minimum-register and graph-colouring questions appear now and then.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 3 done.

Formulas

Sethi–Ullman label
leaf: 1 if left child, 0 if right child; node: l1 = l2 → l1 + 1, else max(l1, l2)
Registers needed
= label of the root
Chromatic number
min registers for the interference graph = chromatic number (NP-hard in general)

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Minimum registers to evaluate an expression
Label the expression tree or generate code with a given number of registers.
★★★
Colour the interference graph
Find the minimum registers / whether spilling is needed from liveness info.
★★★
Peephole transformation
Result of replacing a pattern.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

3 real questions from the official GATE CSE papers (2013 to 2017), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

3 questions · 0 correct of 0 attempted · marks 0 / 6

Year:
GATE 2017 Set 1 · Q52NAT2 marks
Consider the expression (a − 1) * (((b + c) / 3) + d). Let X be the minimum number of registers required by an optimal code generation (without any register spill) 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 ______.
GATE 2013 Code A · Q48MCQ2 marks
(Same code segment as the previous question.) Suppose the instruction set architecture of the processor has only two registers. The only allowed compiler optimization is code motion, which moves statements from one place to another while preserving correctness. What is the minimum number of spills to memory in the compiled code?
GATE 2013 Code A · Q49MCQ2 marks
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.

Common traps

The right operand being a memory operand means a right leaf costs 0 registers.
Two variables interfere only if they are live simultaneously.