Sethi–Ullman Register Allocation
Choose expression evaluation order to minimize simultaneously live registers.
Free theory articleChoose expression evaluation order to minimize simultaneously live registers.
Concept & interpretation
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.
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.
- First, select the Expression type control, for example "Mixed". Note the Minimum registers calculated output.
- Then, change the Evaluation order control between "Optimal", "Left first", and "Right first".
- Observe the Selected order registers and the Excess registers output to see how non-optimal choices lead to higher peak register usage.