算法寄存器分配 [英] Algorithm for register allocation

问题描述

我想实现一个code代/赞成我的旧的，在这里我把一切都在堆栈寄存器分配算法树木。现在我想实现塞西 - 乌尔曼算法但仅从内容我在维基百科上发现，一些网页的算法的某些部分仍不清楚我的。

I'm trying to implement a code generation/register allocation algorithm for Trees in favor of my old one, where I put everything on stack. Now I'm trying to implement Sethi-Ullman algorithm but from only contents I've found on Wikipedia and some web pages some parts of the algorithm remain unclear to me.

我正在寻找一个解释的部分我失去了一些伪code / C / C ++工作code。

I'm looking for an explanation to parts I'm missing with some pseudo-code/C/C++ working code.

1）我应该使用哪种方法来选择自由寄存器？即，寄存器堆beging使用。我使用的是什么，我认为一个非常贫穷之一：或者返回寄存器：如果previously使用的寄存器R0是，返回R1。如果R1，返回R0等。它不工作，小恩pressions。

1) Which approach should I use to chose free register? ie, the stack of registers beging used. I'm using what I consider a very poor one: Alternately return registers: if previously used register was R0, return R1. If R1, return R0 and so on. It doesn't work to small expressions.

2），我该怎么办时，标签（左）＆GT; = K和标签（右）与GT; = K ？

2) What should I do when label(left) >= K and label(right) >= K ?

这里的标签和塞西 - 厄尔曼功能

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;
    }
}

有关从像这样的EXP树：

For a tree from an exp like this:

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

以上我只提供了主要的算法，但我可以提供完整的code到测试情况下，你的机器上，如果需要的话。

Above I provided only the main algorithms, but I can provided full code to a test case on your machine, if needed.

推荐答案

我不太明白为什么 8+（2 + B * 3） EX pression不只是工作，因为对我来说，前pression不应该需要超过2个寄存器的计算。但是，如果你不能两个寄存器进行整计算，那么你需要做的溢出 - 存储寄存器在一个临时（堆栈）的位置，然后恢复从当你再次需要它的临时位置值。

I don't quite understand why the 8+(2+b*3) expression doesn't just "work", because to me, the expression shouldn't need more than 2 registers in the calculation. However, if you can't perform the whole calculation in two register, then you need to do "spilling" - storing the register in a temporary (stack) location, and then restoring the value from that temporary location when you need it again.

这是您发布的code：

This is the code you posted:

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

我们可以重写它，使用溢出：

We can rewrite it, using spilling:

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

不过，这是可以做到不溢出，这说明您正在使用的实际的算法是错误的：

However, it is possible to do without spilling, which suggests that the actual algorithm you are using is wrong:

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

或者，同样：

Or, equally:

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

我不知道，但我认为它可能是围绕你选择的第一个添加指令的左/右操作数的方式。

I'm not sure, but I think it may well be the way around you pick the left/right operand of the first ADD instruction.

我想补充一些打印输出跟随code，看看它在不同的情况下。

I would add some printouts to follow the code, and see what it does in different circumstances.

这篇关于算法寄存器分配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！