← ⚙️ Code Generation & Register Allocation
Subtopic 1 of 3

10.1Minimum registers for an expression (Sethi–Ullman)

Label each tree node with the minimum registers needed to evaluate its subtree without storing to memory. Evaluate the child with the larger label first.

+
*
+
a
b
-
c
d
*
e
+
f
g
  • leaf a: left child needs 1 register
  • leaf b: right leaf can be used from memory: 0
  • +: children labels 1 and 0 → max(1, 0) = 1
  • leaf c: left child needs 1 register
  • leaf d: right leaf can be used from memory: 0
  • -: children labels 1 and 0 → max(1, 0) = 1
  • *: children labels 1 and 1 → equal, so 1 + 1 = 2
  • leaf e: left child needs 1 register
  • leaf f: left child needs 1 register
  • leaf g: right leaf can be used from memory: 0
  • +: children labels 1 and 0 → max(1, 0) = 1
  • *: children labels 1 and 1 → equal, so 1 + 1 = 2
  • +: children labels 2 and 2 → equal, so 2 + 1 = 3

Minimum registers needed (no spills): 3

Label rule: left leaf = 1, right leaf = 0. Interior node: if the children's labels are equal, label + 1; otherwise the larger one.

Previous year questions: Code Generation & Register Allocation (3)

PYQs are grouped by topic, so this is the full set for Code Generation & Register Allocation; try the ones that match this subtopic. Open all 3 on the topic page.