Codegenerator für Ausdrücke mithilfe des Sethi-Ullman-Algorithmus

Question

Gib einen AST-Baum an, ich möchte eine assembly-ähnliche Sprache generieren. Ich versuche den Sethi-Ullman-Algorithmus zu verwenden, aber ich habe einige Fragen zur Algorithmusimplementierung.

Was soll ich tun, wenn mir die Register ausgehen?

Derzeit mache ich folgendes:

Eine push REG Emittieren, wobei REG das Register des rechten Teilbaums ist, den linken Teilbaum auswerten, ein freies Register erhalten und dem Register des rechten Teilbaums zuweisen sowie dann eine POP REG-Operation emittieren, wobei REG ebenfalls das Register des rechten Teilbaums ist.

Wie soll ich die Funktion implementieren, um ein freies Register zu erhalten? Derzeit verwende ich eine Implementierung wie diese anstelle einer stapelbasierten:

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

Hier ist ein Pseudocode (aus der C-Sprache), wie man es implementieren sollte, soweit ich verstanden habe (einschließlich der label()-Funktion)

// K ist die Anzahl der verfügbaren Register
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");
        // Fehler
    }
}

// ershov-Zahlen
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 hat zwei Kinder
    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 hat ein Kind
    else if(ast.left not null && ast.right is null)
        ast.n = ast.left.n;
    else
        print("label() error!");
}

EDIT: Bitte sagen Sie mir, ob mehr Kontext benötigt wird, um dies zu verstehen.

Answer 1

Sethi-Ullman ist eigentlich nur ein Terminierungsplanungsalgorithmus, kein Registerzuordnungsalgorithmus, der Ihnen lediglich die Reihenfolge angibt, in der Operationen durchgeführt werden müssen, um die Anzahl der benötigten Register zu minimieren; er sagt Ihnen nicht, welche Register Sie wo verwenden sollen.

Sie müssen ihn also mit einer Registerallokationsstrategie kombinieren - normalerweise nur mit einem gierigen Zuweiser. Dann stellt sich die Frage, was zu tun ist, wenn die Register ausgehen - fügen Sie Zwischenspeicherungen inline ein oder brechen Sie ab und tun Sie etwas anderes?

Um eine einfache gierige Allokation in Verbindung mit Ihrer Terminierungsplanung und der Anweisungsgenerierung (was Sie anscheinend mit Ihrem einfachen genrekursiven Verfahren tun), durchzuführen, müssen Sie verfolgen, welche Register zu einem bestimmten Zeitpunkt verwendet werden. Der einfachste Weg ist, ein zusätzliches in_use-Argument zu Ihrer gen-Funktion hinzuzufügen:

typedef unsigned RegSet; /* Verwendung einer einfachen Bitmaske für eine Menge - unter der Annahme, dass
                          * unsigned groß genug ist, um ein Bit pro Register zu haben */

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

Beachten Sie, dass Sie einen separaten rekursiven Durchlauf benötigen, um n für jeden Knoten zu berechnen (Sethi-Ullman erfordert inhärent zwei Traversen, wobei die erste Traversierung bottom-up den Wert n für die zweite Traversierung berechnet, die top-down verwendet).

Der obige Code geht jedoch überhaupt nicht darauf ein, was passiert, wenn die Register ausgehen. Um das zu tun, müssen Sie einige Zwischenspeicherungen einfügen. Eine Möglichkeit besteht darin, zu erkennen, dass alle Register verwendet werden, bevor ein rekursiver Aufruf erfolgt, dann Zwischenspeicherungen einzufügen und danach wiederherzustellen:

void gen(AST *ast, RegSet in_use) {
    if(ast->left != 0 && ast->right != 0) {
        Reg spill = NoRegister; /* noch kein Zwischenspeicher */
        AST *do1st, *do2nd;     /* in welcher Reihenfolge die Kinder generiert werden sollen */
        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 ...

Natürlich stellt sich heraus, dass dies nicht besonders effizient ist - es ist normalerweise besser, früher zu zwischenspeichern und später aufzufüllen, aber nur dann, wenn Sie wissen, dass Ihnen die Register ausgehen werden.