Register Allocation Algorithm

Question

I am trying to implement an algorithm for allocating code generation / registration for trees in favor of my old one, where I put everything on the stack. Now I'm trying to implement the Sethi-Ullman algorithm , but from all the content that I found on Wikipedia and some web pages, some parts of the algorithm remain incomprehensible to me.

I am looking for an explanation for the parts that I am missing with some working pseudo-code / C / C ++ code.

1) What approach should I use to select a free register? those. stack of register used. I use what I consider very poor: return registers one by one: if register R0 was previously used, return R1. If R1, return R0 and so on. This does not work for small expressions.

2) What if label(left) >= K and label(right) >= K?

Here are the functions labelandsethi-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;
    }
}

For a tree from exp as follows:

2+b*3

It generates:

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

And from one such thing:

8+(2+b*3)

It generates:

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

Above, I provided only the basic algorithms, but if necessary, I can provide the full code for the test case on your computer.

Answer 1

, 8+(2+b*3) "", . , , "" - () , , .

, :

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

, 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

, , , , :

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.

, , , .