How to Learn the Sethi–Ullman Algorithm: Ershov Numbers, Evaluation Order, Register Pressure and Spill-Minimising Code Generation

Wait, What?

The same arithmetic expression can require a different number of registers depending on which subtree you evaluate first.

The Sethi–Ullman algorithm teaches a deceptively deep compiler idea: evaluation order is not merely stylistic. On a register machine, computing the “harder” subtree first can reduce temporary storage and avoid spills to memory.

For learners, this is an excellent bridge from expression trees to real machine constraints. It connects syntax trees, recursion, local optimality, resource estimation, code generation and the boundary between a clean theoretical model and modern compiler engineering.

Quick Answer

Learn Sethi–Ullman in this order: expression tree → registers as scarce resources → spills → Ershov/Sethi–Ullman labels → label bottom-up → evaluate higher-pressure subtree first → emit code → prove optimality for the model → understand where the model stops applying. Do not begin with assembly syntax. Begin with the question: “How many registers does this subtree need if I refuse to spill?”

1. Start With an Expression Tree

Take:

(a + b) * (c - d)

Its syntax tree has multiplication at the root, addition on the left, subtraction on the right, and variables at the leaves. To evaluate the root, the machine must compute both child results and keep at least one result alive while computing the other.

That “keep one result alive” requirement is where register pressure appears.

2. What Is a Spill?

A register is a fast storage location inside the processor. If all useful registers are occupied and another temporary value is needed, a compiler may store a value to memory and reload it later. That temporary store/reload is commonly called a spill.

The simplified Sethi–Ullman problem asks: in what order should an expression tree be evaluated to minimise spills, or equivalently to minimise the peak number of registers needed under the model?

3. Label the Leaves First

In the common Ershov-number presentation, each leaf requires one register to hold its value. Then internal nodes are labelled from their children.

leaf -> 1 register

Some machine-specific formulations distinguish constants or right-hand operands and may assign different base labels. That is not a contradiction; it reflects a different instruction model. The learning goal is to understand what the label means in the chosen machine model.

4. The Label Rule

Let the left and right subtree labels be L and R.

if L != R:
    label(node) = max(L, R)
else:
    label(node) = L + 1

Why? If one subtree needs more registers, evaluate it first while all registers are free. Its result occupies one register, but the smaller subtree can still fit in the remaining capacity. If both subtrees need the same number, computing either one first consumes one register for its result, so the second needs one additional register overall.

5. A Tiny Worked Example

For:

(a + b) * c

the leaves each have label 1. The subtree (a+b) has equal child labels, so it receives 2. The leaf c has 1. At the root, the labels differ: 2 and 1. Therefore the root needs max(2,1)=2 registers.

The evaluation order should be:

1. compute a+b first;
2. keep that result in one register;
3. load c using the remaining capacity;
4. multiply.

If you evaluate c first, you unnecessarily occupy a register while trying to compute the harder (a+b) subtree.

6. Equal Labels Create the Extra Register

Consider:

(a + b) * (c + d)

Each addition requires 2 registers. Once the first side has been computed, its result must remain live while the second 2-register subtree is evaluated. That pushes the root requirement to 3.

This is the most important mental model in the algorithm: equal pressure on both sides creates a peak because one completed result must coexist with the full pressure of the other subtree.

7. The Code-Generation Rule

After labels are known, code generation follows a simple preference:

• if one child has a larger label, evaluate that child first;
• if labels are equal, either order has the same register requirement under the simple model;
• combine the two child results at the parent.

The labels therefore become a compact schedule for local evaluation order.

8. This Is Resource-Aware Tree Scheduling

The algorithm is often introduced as “register allocation,” but a more precise learner-friendly view is: it computes a resource requirement for each subtree, then schedules subtrees to minimise the peak live resource demand.

That idea transfers far beyond compilers. Similar reasoning appears in task scheduling, memory planning, expression evaluation, query execution and parallel DAG scheduling.

9. Why the Algorithm Is Optimal for Its Model

The bottom-up labels encode the minimum number of registers needed without spilling. The evaluation rule uses the larger-demand subtree first, which prevents a low-demand partial result from occupying a register while the high-demand side runs.

When both demands are equal, one entire subtree must be completed before the other can finish, so one extra register is unavoidable. This local recurrence exactly captures the minimum peak requirement for a binary expression tree under the assumed register-machine model.

10. Machine Model Assumptions Matter

Real instruction sets differ. Some instructions can use memory operands directly. Some architectures have special registers, vector registers, register pairs, calling conventions or destructive two-address operations. Constants may be encoded immediately rather than loaded.

Therefore a label such as “3 registers” is not a universal truth about the expression. It is a truth relative to a machine model.

11. Trees Are Easier Than DAGs

An expression tree duplicates a common subexpression if it appears in two places. A directed acyclic graph can share that subexpression. Sharing changes the scheduling problem because a computed value may remain live across multiple uses.

The simple Sethi–Ullman recurrence is elegant precisely because a tree has no shared descendants. Once common subexpressions, arbitrary DAGs and global liveness enter the picture, register allocation becomes much more complex.

12. Noncommutative Operators Need Care

You may change evaluation order without changing operand meaning. For subtraction or division, evaluating the right subtree first does not mean swapping the operands. The emitted instruction must still preserve left-versus-right semantics.

This distinction is important: scheduling can change when a value is computed while the expression’s mathematical structure remains unchanged.

13. Register Pressure Is Not the Same as Global Register Allocation

Modern compilers perform broader register allocation across basic blocks and control flow, often using graph colouring, linear scan or more specialised methods. Sethi–Ullman solves a narrower local problem for expression-tree code generation.

That narrower scope is a strength for learning because it isolates one cause of spills and makes the optimality argument visible.

14. A Useful Pseudocode Skeleton

label(node):
    if node is leaf:
        node.need = 1
    else:
        label(node.left)
        label(node.right)
        if left.need == right.need:
            node.need = left.need + 1
        else:
            node.need = max(left.need, right.need)

emit(node):
    if node is leaf:
        load node
    else:
        first  = child with larger need
        second = the other child
        emit(first)
        preserve first result
        emit(second)
        emit operator using original operand semantics

The exact assembly details depend on the target machine. Keep the scheduling idea separate from instruction syntax.

15. Common Failure States

• Confusing a subtree’s label with the number of leaves it contains.
• Evaluating the smaller-label subtree first.
• Forgetting that equal labels add one.
• Swapping noncommutative operands when only evaluation order should change.
• Claiming the simple recurrence solves global register allocation.
• Ignoring machine-model assumptions.
• Applying the tree recurrence directly to DAGs with shared subexpressions.

16. Test With Trees That Force Different Cases

Use at least four shapes:

• a single leaf;
• a long skewed tree;
• a perfectly balanced tree;
• a mixed tree where one subtree is much deeper than the other.

For each node, write L, R, the resulting label, the chosen first subtree and the maximum live-register count observed during a simulated evaluation.

17. Practice Ladder: Beginner to Professional

• Beginner: draw an expression tree from a parenthesised arithmetic expression.
• Foundation: mark when intermediate results must stay alive.
• Intermediate: compute Ershov numbers bottom-up and predict the best evaluation order.
• Advanced: emit pseudo-assembly and count spills under a fixed register budget.
• Professional: vary the machine model, introduce constants and noncommutative operators, and explain where the simple optimality proof breaks for DAGs and whole functions.
• Transfer: describe Sethi–Ullman as peak-resource scheduling on a tree, not merely as a compiler fact to memorise.

18. A Better Way to Study This Algorithm

Use worked examples with explicit subgoals: build tree → label leaves → combine labels → choose order → emit code → verify peak registers. Research on subgoal-labelled worked examples suggests that exposing recurring problem-solving structure helps novices form reusable mental models rather than memorise surface syntax.

Then fade support. Remove the labels and ask the learner to reconstruct them. Next remove the evaluation order. Finally give only the expression and register budget. This progression moves from tracing to independent generation without jumping too early into assembly details.

Learning Hall Boundary

This article owns the Sethi–Ullman/Ershov-number method for local expression-tree evaluation order and spill-minimising code generation. It does not replace broader compiler instruction, general graph-colouring register allocation, parsing, or the existing Pratt-parsing draft. It also does not take over MindOS, Bolt or Student/Studying Interface canonical jobs.

Evidence Boundary

The foundational paper is Ravi Sethi and Jeffrey D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM 17(4), 1970: ACM record. Stanford-hosted Dragon Book lecture notes describe Ershov numbers and the use of Sethi–Ullman to minimise spills for expression trees: lecture notes. Princeton records later generalisations by Appel and Supowit: Princeton research record. The instructional design also draws on PRIMM, Parsons-problem research, code-tracing studies and subgoal-labelled worked examples in computing education.

Professional rule: you understand Sethi–Ullman when you can derive the label recurrence, explain why larger-pressure subtrees go first, preserve operand semantics while changing evaluation order, and state exactly which machine and tree assumptions make the optimality claim valid.