Sethi-Ullman is really just a scheduling algorithm, not a register allocation algorithm, so it just tells you the order in which to do operations to minimize the number of registers needed; it does not tell you which registers to use where.
So you need to combine it with a register allocation strategy -- usually just a greedy allocator. Then there's the question of what to do if you run out of registers -- do you insert spills inline, or abort and do something else?
In order to do simple greedy allocation inline with your scheduling and instruction generation (what you seem to be doing with your simple gen
recursive procedure), you'll need to keep track of which registers are in use at any given time. The easiest way is by adding an extra in_use
argument to your gen function:
typedef unsigned RegSet; /* using a simple bitmask for a set -- assuming that
* unsigned is big enough to have a bit per register */
void gen(AST *ast, RegSet in_use) {
if(ast->left != 0 && ast->right != 0) {
if (ast->left->n >= ast->right->n) {
gen(ast->left, in_use);
gen(ast->right, in_use | (1 << ast->left->reg));
} else {
gen(ast->right, in_use);
gen(ast->left, in_use | (1 << ast->right->reg)); }
ast->reg = ast->left->reg
emit_operation(ast->type, ast->left->reg, ast->right->reg);
} else if(ast->type == Type_id || ast->type == Type_number) {
ast->reg = pick_unused_register(in_use);
emit_load(ast);
} else ....
Note that you need a separate recursive pass to calculate n
for each node (Sethi-Ullman inherently requires two traversals, with the first traversal computing bottom up the n
value for the second traversal to use top-down).
Now the above code doesn't deal with running out of registers at all. To do that, you need to insert some spills. One way is to detect that all registers are in use before making a recursive call and spill then, restoring afterwards:
void gen(AST *ast, RegSet in_use) {
if(ast->left != 0 && ast->right != 0) {
Reg spill = NoRegister; /* no spill yet */
AST *do1st, *do2nd; /* what order to generate children */
if (ast->left->n >= ast->right->n) {
do1st = ast->left;
do2nd = ast->right;
} else {
do1st = ast->right;
do2nd = ast->left; }
gen(do1st, in_use);
in_use |= 1 << do1st->reg;
if (all_used(in_use)) {
spill = pick_register_other_than(do1st->reg);
in_use &= ~(1 << spill);
emit_operation(PUSH, spill); }
gen(do2nd, in_use);
ast->reg = ast->left->reg
emit_operation(ast->type, ast->left->reg, ast->right->reg);
if (spill != NoRegister)
emit_operation(POP, spill);
} else ...
Of course, this turns out to be not terribly efficient -- its usually better to spill sooner and refill later, but only when you know you're going to run out of registers.