Ich benutze diesen (siehe unten) Algorithmus (nimm die Idee von diese Antwort) zur Codegenerierung von einem Baum. Ich ziele auf x86 arch, jetzt muss ich mit mul / div Befehlen arbeiten, die Register eax / ebx als Argument verwenden.
Meine Frage ist:
Wie ändere ich das, um Operanden eines bestimmten Befehls zu laden, die in einem festen Register geladen werden? sagen wir für mul instruction load linker und rechter Teilbaum in eax und ebx Registern. Meine aktuelle Implementierung ist: pass current node begin wird als Argument ausgewertet und wenn es MUL oder DIV ist% set reg auf R0 oder R1 entsprechend der Baumseite, wenn es LEFT bzw. RIGHT ist. Wenn reg in_use ist, drücke reg auf den Stapel und markiere ihn als frei beginnen (noch nicht implemented). Die aktuelle Implementierung funktioniert nicht, da sie in assert(r1 != r2) in emit_load() function behauptet (dh beide als Argument übergebenen Register sind gleich wie r1 = REG_R0 und r2 = REG_R0 )
Mit einem One-Pass-Code-Generator wie diesem sind Ihre Möglichkeiten begrenzt. Es ist wahrscheinlich einfacher, zuerst 3-Adreßcode oder eine andere lineare Zwischenrepräsentation zu generieren und dann und dann sich Gedanken über das Targeting von Registern zu machen (dies ist der Name für das, was Sie erreichen wollen).
Nichtsdestoweniger, was Sie tun möchten, ist möglich. Der Nachteil ist, dass Sie keinen Code mit sehr hoher Qualität bekommen. Um es besser zu machen, müssen Sie diesen Generator wegwerfen und neu anfangen.
Das Hauptproblem, auf das Sie stoßen, ist, dass die Sethi-Ulman-Beschriftung kein Code-Generierungsalgorithmus ist. Es ist nur eine Möglichkeit, die Reihenfolge der Codegenerierung auszuwählen. Dir fehlen noch wichtige Ideen.
Bei all dem, was aus dem Weg ist, einige Punkte:
Das Drücken und Aufklappen von Registern, um sie vorübergehend zu speichern, macht das Leben schwierig. Der Grund ist ziemlich offensichtlich. Sie können nur auf die gespeicherten Werte in der LIFO-Reihenfolge zugreifen.
Die Dinge werden einfacher, wenn Sie "Orte" zuweisen, die entweder Register oder Speicherplätze im Stapelrahmen sein können. Die Speicherstellen erweitern effektiv die Registerdatei, um sie so groß wie nötig zu machen. Eine leichte Komplikation besteht darin, dass Sie sich für jede Funktion merken müssen, wie viele Wörter für Stellen im Stack-Frame dieser Funktion benötigt werden, und die Funktionspräambel zur Zuordnung dieser Nummer zurückübersetzen.
Implementieren Sie als Nächstes einen globalen Operandenstapel, wobei jedes Stapelelement ein PLACE ist. Ein PLACE ist ein Deskriptor, der angibt, wo sich ein Operand befindet, der durch bereits ausgegebenen Code berechnet wurde: Register oder Speicher und wie man darauf zugreift. (Für einen besseren Code können Sie PLACE auch als Benutzervariable und / oder Sofortwert definieren, aber PLACEs werden nie von dem unten beschriebenen PLACE-Allokator zurückgegeben. Je mehr Arten von PLACE Sie zulassen, desto mehr Fälle müssen es sein behandelt durch den Code-Emitter, auch unten beschrieben.)
Das allgemeine Prinzip ist "sei faul". Je später wir auf die Ausgabe von Code warten können, desto mehr Informationen sind verfügbar. Mit mehr Informationen ist es möglich, besseren Code zu generieren. Der Stapel von PLACEs macht dies recht gut.
Die Code-Generator-Invariante besteht darin, dass sie Code ausgibt, der das Ergebnis PLACE am Anfang des Operandenstapels belässt.
Sie benötigen auch einen PLACE-Allokator. Dies verfolgt die Register und die verwendeten Speicherwörter. Es weist neue Speicherwörter zu, wenn alle Register und aktuellen Wörter bereits belegt sind.
Register im PLACE-Allokator können drei mögliche Status haben: FREE, BUSY, PINNED. Ein PINNED-Register wird benötigt, um einen Wert zu speichern, der nicht verschoben werden kann. (Wir verwenden dies für Anweisungen mit spezifischen Registeranforderungen.) Ein BUSY-Register wird für einen Wert benötigt, der in Ordnung an einen anderen PLACE verschoben werden kann. Ein FREE-Register enthält keinen Wert.
Der Speicher im PLACE-Allokator ist entweder FREI oder BESETZT.
Der PLACE-Allokator benötigt mindestens diese Einstiegspunkte:
allocate_register wählt ein FREE-Register R aus, macht es BUSY und gibt R zurück. Wenn keine FREE-Register verfügbar sind, weisen Sie ein FREE-Speicherwort P zu, verschieben Sie den Inhalt eines BUSY-Registers R und geben Sie R. pin_register(R) funktioniert wie folgt: Wenn R PINNED ist, wird ein schwerwiegender Fehler ausgelöst. Wenn R BUSY ist, erhalten Sie einen FREE PLACE P (entweder Register oder Speicherwort), geben Sie einen Code aus, der den Inhalt von R nach P verschiebt, markieren Sie R PINNED und kehren Sie zurück. Wenn R FREI ist, markieren Sie es einfach PINNED und zurück. Beachten Sie, dass wenn das Pinnen oder Zuordnen von Register R das Verschieben seines Inhalts erfordert, der Zuordner das entsprechende Element im Operandenstapel aktualisieren muss. Was R war, muss zu P geändert werden. Zu diesem Zweck unterhält der Zuordner eine Zuordnung, die jedes Register zu dem Operandenstapel PLACE führt, der es beschreibt.
Damit ist der Codegenerator für binäre Ops einfach:
%Vor%Der Code-Emitter funktioniert folgendermaßen:
%Vor%Schließlich muss der Anweisungsemitter wissen, was zu tun ist, wenn seine Operanden Kombinationen von Typen aufweisen, die von dem Prozessorbefehlssatz nicht unterstützt werden. Zum Beispiel muss es möglicherweise einen Speicher PLACE in ein Register laden.
%Vor%Ich habe unbedingt viele Details rausgelassen. Fragen Sie, was nicht klar ist.
Beantwortete OP-Fragen
Sie haben Recht, dass ich stack(n) als PLACE bezeichnet habe, das n vom Anfang des Operandenstapels ist.
Blätter des Syntaxbaums drücken einfach einen PLACE für einen berechneten Wert auf dem Operandenstapel, um die Invariante zu erfüllen.
Wie oben erwähnt, können Sie entweder spezielle Arten von PLACEs für diese Operanden erstellen (vom Benutzer beschriftete Speicherplätze und / oder Direktwerte) oder - einfacher und wie Sie vorgeschlagen haben - ein Register zuweisen und Code ausgeben, der den Wert lädt In dieses Register drücken Sie dann den PLACE des Registers auf den Stapel. Die einfachere Methode führt zu unnötigen Ladeanweisungen und verbraucht mehr Register als nötig.Zum Beispiel erzeugt x = x + 1 einen Code wie:
Hier verwende ich x , um den Basiszeigeroffset der Variablen zu bezeichnen.
Mit PLACEs für Variablen und Literale können Sie leicht erhalten:
%Vor%Indem Sie den Codegenerator auf den PLACE aufmerksam machen, auf den die Zuweisung seine Antwort geben muss, können Sie
abrufen %Vor%oder äquivalent
%Vor% Erfüllen Sie dies, indem Sie dem Code-Generator einen Parameter PLACE *target hinzufügen, der beschreibt, wohin der endgültige Wert des berechneten Ausdruckswerts gehen soll. Wenn Sie gerade keinen Ausdruck kompilieren, wird dieser Wert auf NULL gesetzt. Beachten Sie, dass sich mit target die Code-Generator-Invariante ändert: Das PLACE des Ergebnisses des Ausdrucks steht am Anfang des Operanden-Stacks , sofern nicht target gesetzt ist. In diesem Fall wurde es bereits im PLACE des Ziels berechnet.
Wie würde das bei x = x + 1 funktionieren? Die Prozedur ASSIGNMENT in der Prozedur emit_code_for würde die target als PLACE für x bereitstellen, wenn sie sich rekursiv aufruft, um x + 1 zu kompilieren. Dies delegiert die Verantwortung nach unten, um den berechneten Wert an den richtigen Speicherort zu bringen, nämlich x . Der emit_code_for case für ADD ow ruft emit_code_for rekursiv auf, um die Operanden x und 1 auf dem Stack auszuwerten. Da wir PLACEs für Benutzervariablen und unmittelbare Werte haben, werden diese auf den Stapel geschoben, während überhaupt kein Code erzeugt wird. Der ADD -Emitter muss nun schlau genug sein zu wissen, dass, wenn er einen Speicherplatz L und eine Literalkonstante C auf dem Stack sieht und das Ziel auch L ist, er add L, C ausgeben kann und fertig ist.
Denken Sie daran, dass jedes Mal, wenn Sie den Code-Generator "intelligenter" machen, indem Sie ihm mehr Informationen zur Verfügung stellen, um seine Entscheidungen zu treffen, wird er länger und komplizierter, weil es mehr Fälle zu bewältigen gibt.
Tags und Links algorithm c compiler-construction code-generation compiler-theory