SETHI-ULLMAN NUMBERING the fewest registers to evaluate a tree, and the order
Given an expression tree and a machine with registers, what is the minimum number of registers to evaluate it with no spills — and in what order? Label each leaf 1; a node whose children have equal labels needs label+1, otherwise the larger of the two. The root’s label is the answer, and the rule is: evaluate the heavier subtree first so its registers are free when you turn to the lighter one.
THE TECHNIQUE label(node) = l==r ? l+1 : max(l,r)
A balanced tree (a+b)*(c+d) needs one more register than a skewed a+(b+(c+d)), because balance forces two live values to meet. Pick the shape and watch the labels — and the heavier-first order — compute: live demo
HISTORY & CREDIT Sethi & Ullman, JACM 1970
“Sethi-Ullman is register allocation.” — not the global kind. It gives the optimal register count and evaluation order for one expression tree (no spills, uniform registers); global allocation across a whole function with reuse and spilling is graph colouring / linear scan (darts 161). Different scope. cited
1970 · Ravi Sethi & Jeffrey D. Ullman — “The Generation of Optimal Code for Arithmetic Expressions” (JACM 17(4)): the labelling algorithm and a proof it is optimal for a uniform register machine. 1976 · Aho & Johnson — extend optimal codegen to trees with DP (for non-uniform costs / addressing modes). ongoing · the Sethi-Ullman number is a textbook staple (the Dragon Book), still used to order sub-expressions.
The optimality is scoped: uniform registers, a tree (not a DAG — shared sub-expressions break the bound), and no spilling. Relax any and you are back to a heuristic. Sethi & Ullman, 1970
RECOMMEND FOR I-13 labels computed by the recurrence
The recurrence runs on the canonical compiler — the balanced tree needs one more register than the skewed one:
$ i13 run su.i13 # label(n) = leaf?1 : (l==r ? l+1 : max(l,r))
balanced = 3 -- (a+b)*(c+d): both sides label 2, equal -> 3
skewed = 2 -- a+(b+(c+d)): always a 1 against a 2 -> 2
Recommend: Sethi-Ullman is LIT and directly useful for an I-13 back-end — verified on the canonical compiler that (a+b)*(c+d) needs 3 registers and a+(b+(c+d)) needs 2, computed by the exact labelling recurrence (which is native I-13 recursion over an array-encoded tree). Even without a register file, the evaluation order it prescribes (heavier subtree first) minimises the live-value high-water mark on the operand stack — a real ordering win for the lowering pass. Pairs with instruction selection (158) and register allocation (161).