Sethi–Ullman Register Allocation

Sethi–Ullman Register Allocation

The Sethi–Ullman algorithm determines the optimal evaluation order of an expression tree to minimize the number of simultaneously live registers. It operates under a simple machine model where all operations are binary, leaf nodes require one register, and each binary operation overwrites one of its operands, effectively freeing the other.

Labeling Phase

The algorithm first assigns a label to each node representing the minimum number of registers required to evaluate that subtree. For a leaf node, the label is 1. For a binary operation with left child label L and right child label R:

• If L = R, the parent's label is L + 1.
• If L ≠ R, the parent's label is max(L, R).

Code Generation Phase

When generating code (or simply choosing an evaluation order), the algorithm dictates that the subtree with the larger label should be evaluated first. This is because evaluating the "harder" subtree first leaves its result in a single register while we evaluate the "easier" subtree, which requires fewer registers. Thus, the total registers needed will not exceed the requirement of the harder subtree. If we evaluated the easier subtree first, its result would consume one register, and we would then need the full register requirement of the harder subtree, potentially increasing the total number of registers needed by 1.

In the case of a tie (L = R), evaluating either side first will result in L + 1 registers. By convention, we typically evaluate the left subtree first.

Experimenting with Evaluation Orders

The interactive Sethi–Ullman Register Allocation module allows you to observe how different evaluation strategies impact register usage across various expression tree shapes.

1. First, select the Expression type control, for example "Mixed". Note the Minimum registers calculated output.
2. Then, change the Evaluation order control between "Optimal", "Left first", and "Right first".
3. Observe the Selected order registers and the Excess registers output to see how non-optimal choices lead to higher peak register usage.

Worked Example

Consider the mixed expression ((a+b)+(c+(d+e))). We will calculate the minimum registers required for each subtree and the optimal evaluation order.

First, we compute the labels for all leaf nodes:

Leaf a: 1 Leaf b: 1 Leaf c: 1 Leaf d: 1 Leaf e: 1

Next, we compute the labels for the binary operations from the bottom up:

1. a+b: Both children have label 1. Label = max(1, 1) + 1 = 2.
2. d+e: Both children have label 1. Label = max(1, 1) + 1 = 2.
3. c+(d+e): Left child (c) is 1, right child (d+e) is 2. Label = max(1, 2) = 2.
4. Root ((a+b)+(c+(d+e))): Left child (a+b) is 2, right child (c+(d+e)) is 2. Label = max(2, 2) + 1 = 3.

The minimum number of registers required for the entire expression is 3. The optimal evaluation order evaluates c+(d+e) (or a+b) first, evaluating the subtrees in a way that minimizes peak register usage.

Limitations

The classic Sethi-Ullman algorithm applies to strict expression trees without common subexpressions. If an expression can be represented as a Directed Acyclic Graph (DAG) where values are reused, finding the optimal register allocation becomes NP-complete. Furthermore, the model assumes a simple machine where all instructions are of the form R_dest = R_dest op R_src and does not account for complex instruction sets with immediate operands, memory-to-memory arithmetic, or specific calling conventions that pin variables to specific registers. It also assumes an infinite supply of virtual registers and does not handle register spilling to memory.

References

The classic Sethi-Ullman algorithm is widely taught as part of standard compiler construction courses, illustrating tree-based code generation.

• Register Allocation (CS701 Notes, UW-Madison)