使用 Sethi-Ullman 算法的表达式的代码生成器

Give a AST tree http://en.wikipedia.org/wiki/Abstract_syntax_tree，我想生成一种类似汇编的语言。我正在尝试使用塞西-乌尔曼 http://en.wikipedia.org/wiki/Sethi%E2%80%93Ullman_algorithm算法，但我对算法实现有一些疑问。

当我的寄存器用完时我该怎么办？

目前我执行以下操作：

Emit a push REG where REG是右子树的寄存器，评估左子树，得到一个空闲寄存器分配作为右子树的寄存器，然后发出一个POP REG操作地点REG也是右子树的寄存器。

我该如何实现免费注册的功能呢？目前我正在使用这样的实现而不是基于堆栈的：

enum Reg { Reg_r0, Reg_r1 };
Reg regs[] = { Reg_r0, Reg_r1 };
    Reg getreg() {
             static int c;
        if(c == sizeof(regs) / sizeof(int))
        c = 0;
        return regs[c++];
    }

这是一个伪代码（来自 C 语言）如何根据我未设置的内容（包括label()功能）

// K is the number of registers available
int K = 2;
void gen(AST ast) {
    if(ast.left != null && ast.right != null) {
        int l = ast.left.n;
        int r = ast.right.n;
        
        if(l >= K && r >= K) {
            gen(ast.right);
            ast.n -= 1;
            emit_operation(PUSH, ast.right.reg);
            gen(ast.left);
            ast.reg = getreg();
            emit_operation(POP, ast.right.reg);
        } else if(l >= r) {
            gen(ast.left);
            gen(ast.right);
            ast.n -= 1;
        } else if(l < r) {
            gen(ast.right);
            gen(ast.left);
            ast.n -= 1;
        }
        
        ast.reg = getreg();
        Reg r1 = ast.left.reg;
        Reg r2 = ast.right.reg;
        emit_operation(ast.type, r1, r2);
    } else if(ast.type == Type_id || ast.type == Type_number) {
        ast.n += 1;
        ast.reg = getreg();
        emit_load(ast);
    } else {
        print("gen() error");
        // error
    }
}

// ershov numbers
void label(AST ast) {
    if(ast == null)
        return;
    
    label(ast.left);
    label(ast.right);
    
    if(ast.type == Type_id || ast.type == Type_number)
        ast.n = 1;
    // ast has two childrens
    else if(ast.left not null && ast.right not null) {      
        int l = ast.left.n;
        int r = ast.right.n;
        
        if(l == r)
            ast.n = 1 + l;
        else
            ast.n = max(1, l, r);
    }
    // ast has one child
    else if(ast.left not null && ast.right is null)
        ast.n = ast.left.n;
    else
        print("label() error!");
}

EDIT:如果需要更多背景信息来理解这一点，请告诉我。

Sethi-Ullman 实际上只是一个调度算法，而不是一个寄存器分配算法，所以它只是告诉你order在其中执行操作以最小化所需寄存器的数量；它没有告诉你which寄存器使用在哪里。

因此，您需要将其与寄存器分配策略结合起来——通常只是一个贪婪的分配器。接下来的问题是，如果寄存器用完该怎么办——是内联插入溢出，还是中止并执行其他操作？

为了与您的调度和指令生成内联进行简单的贪婪分配（您似乎正在使用简单的gen递归过程），您需要跟踪在任何给定时间正在使用哪些寄存器。最简单的方法是添加一个额外的in_usegen 函数的参数：

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 ....

请注意，您需要单独的递归过程来计算n对于每个节点（Sethi-Ullman 本质上需要两次遍历，第一次遍历计算自下而上n第二次遍历使用自上而下的值）。

现在上面的代码根本不处理寄存器耗尽的问题。为此，您需要插入一些溢出物。一种方法是在进行递归调用之前检测所有寄存器是否都在使用中，然后溢出，然后恢复：

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 ...

当然，事实证明这并不是非常有效——通常最好早点溢出并稍后再填充，但只有当你知道你的寄存器即将用完时。