寄存器分配算法

Question

寄存器分配算法

c++calgorithmcompiler-constructionregister-allocation

5

我正在尝试为树实现代码生成/寄存器分配算法，以取代我以前把所有东西都放在堆栈上的旧算法。现在我正在尝试实现Sethi-Ullman算法，但是从维基百科和一些网页中找到的内容，该算法的某些部分对我来说仍然不清楚。

我正在寻找一些缺失部分的解释，并附有伪代码/C/C++工作代码。

1）我应该使用哪种方法选择空闲寄存器？即，正在使用的寄存器堆栈。我使用了我认为非常糟糕的方法：交替返回寄存器：如果先前使用的寄存器是R0，则返回R1。如果是R1，则返回R0，依此类推。它对于小表达式无效。

2）当label(left) >= K and label(right) >= K时，我应该怎么做？

这里是label和sethi-ullman函数。

REG reg()
{
    static REG r = REG_NONE;

    switch(r) {
        case REG_NONE:
            r = REG_r0;
            break;
        case REG_r0:
            r = REG_r1;
            break;
        case REG_r1:
            r = REG_r0;
            break;
        default:
            assert(0);
            break;
    }
    return r;
}

void SethiUllman(AST *node)
{
    static const int K = 2;

    if(node->left != NULL && node->right != NULL) {
            int l = node->left->n;
            int r = node->right->n;

            if(l >= K && r >= K) {
                SethiUllman(node->right);
                node->n = node->n - 1;
                //emit(node->right, REG_r0);
                SethiUllman(node->left);
                //emit(node->left, REG_r1);
            }
            else if(l >= r) {
                SethiUllman(node->left);
                SethiUllman(node->right);
                node->n = node->n - 1;
            }
            else if(l < r) {
                SethiUllman(node->right);
                SethiUllman(node->left);
                node->n = node->n - 1;
            }

            node->reg = reg();

            printf("%s %s,%s\n", 
                         op_string(node->type),
                         reg_string(node->left->reg),
                         reg_string(node->right->reg));

        }
    else if(node->type == TYPE::id) {
        node->n = node->n + 1;
        node->reg = reg();
        emit(node);
    }
    else {
        node->reg = reg();
        emit(node);
    }
}

void label(AST *node)
{
    if(node == NULL)
        return;

    label(node->left);
    label(node->right);

    if(node->left != NULL && node->right != NULL) {
        int l = node->left->n;
        int r = node->right->n;
        if(l == r)
            node->n = 1 + l;
        else
            node->n = max(1, l, r);
    }
    else if(node->type == TYPE::id) {
        node->n = 1;
    } else if(node->type == TYPE::number) {
        node->n = 0;
    }
}

对于这样一个表达式中的树结构：

2+b*3

它确实生成了：

LOAD R0,[b]
LOAD R1,3
MUL R0,R1
LOAD R1,2
ADD R1,R0

并从这样的一个：

8+(2+b*3)

它会生成：

LOAD R0,[b]
LOAD R1,3
MUL R0,R1
LOAD R1,2
ADD R1,R0
LOAD R1,8 < R1 is not preserved. I don't know how it should be done.
ADD R0,R1

以上我仅提供了主要算法，如果需要，我可以提供完整的代码来在您的计算机上测试。

- The Mask

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mats Petersson · Accepted Answer

我不太理解为什么表达式8+(2+b*3)不能直接“工作”，因为在我的理解中，这个表达式在计算时不需要超过2个寄存器。然而，如果你无法在两个寄存器中完成整个计算，那么你就需要进行“溢出” - 将寄存器存储在临时(堆栈)位置上，然后在需要时从该临时位置恢复值。

这是您发布的代码:

LOAD R0,[b]
LOAD R1,3
MUL R0,R1     ; R0 = b*3
LOAD R1,2     
ADD R1,R0     ; R1 = 2+(b*3)
LOAD R1,8 < R1 is not preserved. I don't know how it should be done.
ADD R0,R1

我们可以使用溢出技术来重写它：

LOAD R0,[b]
LOAD R1,3
MUL R0,R1     ; R0 = b*3
LOAD R1,2     
ADD R1,R0     ; R1 = 2+(b*3)
STORE R1, [tmp]
LOAD R1,8 < R1 is not preserved. I don't know how it should be done.
LOAD R0, [tmp]
ADD R0,R1

然而，可以不使用溢出来实现，这表明您正在使用的实际算法是错误的：

LOAD R0,[b]
LOAD R1,3
MUL R0,R1     ; R0 = b*3
LOAD R1,2     
ADD R0,R1     ; R0 = 2+(b*3)
LOAD R1,8     ; Use R0 above -> R1 is now free.
ADD R0,R1

或者同样地：

LOAD R0,[b]
LOAD R1,3
MUL R0,R1     ; R0 = b*3
LOAD R1,2     
ADD R1,R0     ; R1 = 2+(b*3)
LOAD R0,8     ; Store in R1 above -> R0 is now free.
ADD R0,R1

我不确定，但我认为可能是你选择第一个ADD指令的左/右操作数的方式。

我建议添加一些打印输出来跟踪代码，并查看它在不同情况下的行为。