Programmiersprachen und Übersetzer
08 - Zwischencodeerzeugung

Nach der Beschreibung des IR-Codes wollen wir unser eigentliches Ziel definieren: Wir möchten aus dem abstrakten Syntaxbaum ein IR-Programm ableiten, welches ein Funktionsobjekt mit Basisblöcken voller Befehle für jede Funktion auf AST-Ebene enthält. Dazu werden wir den AST traversieren und sukzessive IR-Objekte erzeugen und hierarchisch ineinander schachteln: Das Programm enthält mehrere Funktionen; jede Funktion enthält einen oder mehrere Basisblöcke; jeder Basisblock ist eine Sequenz von Befehlen, die mit einem Sprungbefehl abgeschlossen wird. Wichtig dabei ist sich immer vor Augen zu halten, dass es Funktionen auf Ebene des ASTs gibt und Funktionen auf Ebene des IRs. Die einen werden zwar auf die anderen abgebildet, jedoch sind es gänzlich unterschiedliche Klassen, die sich keinen Code teilen.

Um diese IR-Objekte zu erzeugen, verwenden wir die auf den Folien notierte Programmierschnittstelle. So hängt die create_block()-Methode einen Basisblock an die aktuelle Funktion an und gibt uns eine Referenz auf den Block zurückErinnern Sie sich daran, dass Python, welches wir im Folgenden verwenden, ein Referenzmodell für Variablen hat. Alle Variablen referenzieren also nur Objekte, sie enthalten niemals ein Objekt und es gibt keine expliziten Zeiger. Sehr zu meinem Leidwesen….. Sollten Sie bei einer der Funktionen unsicher ob der Semantik sein, so können Sie im Übungsübersetzer nachschlagen.

Graphiken und Animationen

PreviousNext

Wollen wir nun mit der Codeerzeugung beginnen. Und wir beginnen dort, wo es spannend ist: Mittendrin bei der Codeerzeugung für Ausdrücke (Expressions). Wir nehmen also an, dass wir bereits eine Funktion und einen Basisblock erzeugt habenWie wir das konkret tun, sehen wir gleich.. Unsere Aufgabe ist es, IR-Code für einen AST-Unterbaum, der einen Wert berechnet, zu erzeugen und an den aktuellen Basisblock anzuhängen. Allgemein werden wir bei der Codeerzeugung an Basisblöcke immer nur Instruktionen anhängen, niemals irgendwas vorne oder mittendrin einfügen.

Um die Codeerzeugung zu formulieren, machen wir, wie bei der semantischen Analyse, wieder Gebrauch vom Visitor-Pattern, um jeden AST-Typen passend zu behandeln. Wir bündeln alle Generierungsfunktionen in einer CodeGeneration-Klasse (siehe Übung) und verwenden doppelten dynamischen Dispatch, um die passende Methode aufzurufen. Allerdings verwenden wir nicht nur ein Set an visit_*()-Methoden, sondern gleich drei Verschiedene, je nachdem, ob der Unterbaum zu Code für einen L-Wert (lvalue_*()), für einen R-Wert (rvalue_()), oder ganz ohne Rückgabewert (visit_*()) erzeugt werden soll. Auf diese Weise können wir im Code leicht erkennen mit welchem Ziel hier Code generiert wird.

Diesmal verwenden wir das Visitor-Pattern allerdings ohne automatische Traversierung. Es gibt also keine Maschinerie (traversal()-Funktion), die unsere Visitor-Methoden aufruft, sondern jeder Abstieg zu einem Unterbaum ist explizit im Code vermerkt. Dies erlaubt es, die Umstände der Unterbaum-Codeerzeugung genau zu kontrollieren (z.B. in welchen Basisblock soll der Code hinein erzeugt werden). Außerdem können wir den Rückgabewert der Visitor-Methoden als Rückkanal zwischen Unterbaum und aktuellem Knoten verwenden.

Wie bereits bei der Diskussion um Stack-Maschinen vs. Register-Maschinen angedeutet, berechnet der Code für einen Ausdruck einen Wert und speichert ihn in einer Variable. Wer erstellt aber die Variable in der das Ergebnis gespeichert wird? Erstellt der Aufrufende eine Variable und stellt den Auftrag "Erzeuge Code für diesen Unterbaum, sodass das Ergebnis in dieser Variable gespeichert ist!" (Top-Down) oder erstellt die Generierungsfunktion die Variable selbst und propagiert diese dem Aufrufer zurück (Bottom-Up). Es stellt sich heraus, dass beides valide Strategien sind, um die Codeerzeugung in einem Übersetzer zu strukturieren. Es sind sogar Mischungen beider Formen möglich:

class CodeGen:
    ...
    def rvalue_Literal(self, node, dst_var=None):
        if dst_var is None:
            dst_var = self.current_function.create_variable()
        self.current_block.append(Assign, dst_var, node.value)
        return dst_var

In diesem winzigen Ausschnitt, der R-Wert-Code für ein konstantes Literal erzeugtlvalue_Literal() kann es nicht geben. Überlegen Sie sich, warum!, wird eine Variable optional Top-Down übergeben. Hat der Aufrufende keine Variable mitgegeben, so erzeugen wir eine an dieser Stelle. In allen Fällen propagieren wir die Zielvariable als Rückgabewert.

Bereits am Beispiel des Literals sehen wir, dass die aktuelle Funktion und der aktuelle Basisblock als implizite Parameter in der Codeerzeugung verwendet werden. Beide Werte speichern wir als Felder in der Codeerzeugungs-Klasse. Durch Umsetzen des current_block-Feldes können wir kontrollieren, in welchen Basisblock Code für einen Unterbaum erzeugt wird. Davon werden wir bei den Kontrollstrukturen Gebrauch machen.

Bemerkenswert ist auch, dass die Codeerzeugungsmethoden nicht nur implizite Parameter bekommen, sondern das IR-Programm als Seiteneffekt erzeugen. Der Aufruf einer rvalue_*()-Methode liefert eine Variable mit dem Ergebnis und erzeugt im aktuellen Basisblock IR-Befehle, um diese Variable zu befüllen.

Auf den Folien sehen wir auch noch die R-Wert-Codeerzeugung für den Add-AST Knotentypen: Diese Methode generiert Code für die Unterbäume auf der linken (LHS) und auf der rechten (RHS) Seite der Addition, erzeugt eine Zielvariable (Bottom-Up), und hängt eine IR-Add-Instruktion an den aktuellen Basisblock an. Durch das Visitor-Pattern kann diese Methode beliebige Unterbäume verarbeiten. Sollten wir vergessen haben, eine rvalue_*()-Methode zu implementieren, würde es hier einen Laufzeitfehler geben.

So unscheinbar die Codeerzeugung für die Addition auch aussieht, so trifft sie jedoch eine weitgehende Entscheidung, die nicht unerwähnt bleiben darf: Wir legen uns hier auf eine Ausführungsreihenfolge fest, bei der zuerst die linke und dann die rechte Seite ausgewertet wird. Zuerst werden sich die Instruktionen des linken Unterbaums im Basisblock danach die des rechten Basisblocks wiederfinden. Genau diese Stellen in der Codeerzeugung, bei der wir uns auf eine Reihenfolge der Kindknoten festlegen, sind es, die die Linearisierung des ASTs durchführen.

Im Prinzip sieht die Codeerzeugung für die Berechnung von Ausdrücken gleich aus. Zuerst erzeugen wir den R-Wert Code für jeden Unterbaum und speichern das Ergebnis in jeweils einer Variable, bevor wir diese im knotenspezifischen Code verarbeiten, der wiederum eine Ergebnisvariable beschreibt. Zur Laufzeit führt dies dazu, dass die Unterbäume vor dem Elternknoten ausgewertet werden.

Beim Funktionsaufruf sehen wir, wie die Querverbindungen, die die semantische Analyse eingefügt hat, bei der Codeerzeugung verwendet wird: Wir sind angehalten, Code für den Funktionsaufruf call_expr zu generieren. An diesem AST-Knoten hängt das Attribut callee, welches im Normalfall nur der Bezeichner der aufgerufenen Funktion ist. In der semantischen Analyse (Namensauflösung) haben wir an diesen Bezeichner eine Querverbindung zur Funktionsdeklaration (call_expr.callee.decl) eingefügt. Um nun bei der Codeerzeugung von der AST-Funktionsdeklaration zur IR-Funktion zu kommen, hängen wir während der Codeerzeugung, bevor wir den Funktionskörper besuchen, ein Attribut an die AST-Deklaration:

class CodeGen:
    ...
    def visit_FuncDecl(self, decl):
        func = Function(decl.name)
        decl.ir_obj = func
        ...

Auf diese Weise verwenden wir die Querverbindungen im AST, um Informationen während der Codeerzeugung zwischen Deklarations- und Referenzierungsstelle zu transportieren. In der selben Weise werden wir bei Parameter- und Variablendeklarationen vorgehen.

Eine andere Besonderheit sehen wir beim Zuweisungsausdruck. Dort verwenden wir den R-Wert-Visitor, um die rechte Seite auszuwerten und den L-Wert-Visitor, um einen Zeiger auf die linke Seite zu generieren. Die Zuweisung selbst besteht dann aus einer einzelnen Store-Operation, die den Wert der rechten Seite an die adressierte Speicherstelle der linken Seite schreibt.

Dieses allgemeine Vorgehen (Wert von rechts, Zeiger von links, Store) funktioniert in jeder Situation, egal wie komplex der Ausdruck auf der linken Seite ist (z.B. *(foo.bar()) := ...). Allerdings erzeugt dieses allgemeine Muster für den Standardfall, bei dem eine lokale Variable auf der linken Seite steht, wenig lesbaren (und vor allem analysierbaren Code). Deswegen bauen wir an dieser Stelle einen Sonderfall dafür ein, dass eine Variable auf der linken Seite steht und sodann nur ein Assign emittiert wird. Schauen Sie sich ruhig an dieser Stelle den Übungsübersetzer an (CodeGen.rvalue_Assign()).

Graphiken und Animationen

PreviousNext

Nachdem wir Code für alle Ausdrücke abgehandelt haben, gehen wir mit der Codeerzeugung eine Stufe weiter nach oben und emittieren die Befehle, um die Kontrollflussstruktur der Funktion auf IR-Ebene abzubilden. Dazu behandeln wir die AST-Konstrukte zur Sequenzierung, Selektion und Iteration so, dass in der aktuellen IR-Funktion direkt der korrekte Kontrollflussgraph entsteht.

Als erstes betrachten wir die Sequenzierung und dort insbesondere die Codeblöcke: Aus der vagen Erinnerung an die Vorlesung zu OperationenSiehe Sequenzierung., wissen wir, dass der Sequenzoperator verwendet wird, um mehrere Statements in einer festen Reihenfolge auszuführen. Eine solche Statement-Reihung ist im AST in einem Codeblock-Knoten zusammengefasst.

Geht es nun daran, Code für diesen Block-Knoten zu generieren, sieht die Erzeugungsmethode denkbar einfach aus, denn sie besucht, in der gegebenen Reihenfolge, alle Statements des Blocks mit der visit()-Funktion (unsere Statements haben keinen Rückgabewert). Allerdings steckt der Teufel im Detail und dieses Vorgehen funktioniert nur, wenn wir eine Invariante über die visit_*() annehmen: Wir haben bereits diskutiert, dass die Erzeugungsmethoden als Seiteneffekt IR-Befehle an den aktuellen Block (current_block) anhängen. Bestehen die besuchten Statements nur aus Ausdrücken, so ist auch alles fein, da diese keine neuen Basisblöcke erzeugen wollen. Was machen wir aber mit Statements, die wiederum Kontrollflusskonstrukte, wie eine Selektion, beinhalten? Um weiterhin korrekten Code für die Sequenzierung zu generieren, muss jede visit_*()-Methode, die den potentiellen Kontrollfluss aufspaltet (eine Verzweigung im CFG einbaut), diesen an ihrem Ende wieder zusammenführen. Technisch gesehen darf der current_block am Ende zwar auf einen anderen Basisblock zeigen, dieser muss jedoch in Reihe mit dem ersten Block der Sequenzierung ausgeführt werden.

Diese etwas schwammige Bedingung lässt sich noch etwas genauer formulieren: Auf der Folie ist jeder schwarze Punkt eine Stelle im CFG und steht für den Beginn einer Statement-Ausführung. Zwischen jedem dieser Sequenzierungspunkte kann ein beliebig komplexer Kontrollfluss entstehen. Jedoch muss jeder Pfad durch den CFG, der durch einen Sequenzierungspunkt geht, vorher alle anderen Sequenzierungspunkte besucht haben. Diese Pfad-Eigenschaft heißt Dominanz-Relation: Ein Punkt A im CFG dominiert einen anderen B, wenn alle Kontrollflüsse durch B vorher A besucht haben müssen. Wir werden die Dominanz-Relation in dieser Vorlesung nicht weiter diskutieren, jedoch sei Ihnen gesagt, dass sie eine signifikante Rolle bei fortgeschritteneren Programm-Optimierungen spielt. Die entsprechenden Stichworte hierzu, wenn Sie sich weiter darüber informieren wollen, sind Dominanz-Grenze und Single-Static-Assignment-Form (SSA).

Graphiken und Animationen

PreviousNext

Bei den Selektionen schauen wir uns nur die einfachste Form der bedingten Ausführung an: if-else-Konstrukte mit Boolescher Bedingung. Am Anfang unserer Erzeugungsmethode für diesen AST-Knotentypen (Übung: visit_IfStmt()) gilt die Invariante, dass der current_block eindeutig auf einen Basisblock zeigt. In diesen Basisblock können bereits andere Befehle hinein generiert worden sein, aber jetzt sind wir an der Reihe. Zunächst müssen wir den R-Wert der Bedingung ausrechnen, falls dies ein komplexerer Ausdruck ist und, beispielsweise, logische oder arithmetische Operationen beinhaltet. Nun erzeugen wir drei neue Basisblöcke:

• BB1 für den Then-Zweig
• BB2 für den Else-Zweig
• BB3 zum Zusammenführen des gespaltenen Kontrollflusses

Den Kontrollfluss spalten wir in BB0 auf, indem wir dort, mit dem Ergebnis der Bedingung einen IfGoto-Befehl anhängen, der entweder zu BB1 oder zu BB2 verzweigt.

Für den Then-Zweig setzen wir den current_block-Zeiger auf BB1 und besuchen den entsprechenden Unterbaum im AST, um BB1 mit Befehlen zu füllen. Am Ende dieses Besuchs kann es allerdings sein, dass current_block nicht mehr auf BB1 zeigt, sondern auf einen Block BBn, der allerdings von BB1 dominiert wird. Das Bild auf den Folien zeigt also nicht die ganze Wahrheit, sondern nur den vereinfachten Fall, wenn innerhalb von ifStmt.then_block der Kontrollfluss nicht weiter aufgespalten wird. Egal wie, nach dem Besuchen des Then-Zweiges fügen wir ein Goto .BB3 ein, um den Kontrollfluss wieder zusammenzuführen.

In gleicher Weise gehen wir auch beim Else-Zweig vor. Allerdings kann es sein, dass es im AST keinen Else-Unterbaum gibt, wenn der Entwickler keinen angegeben hat. In diesem Fall generieren wir den Else-Zweig dennoch und kümmern uns in der Optimierung darum, diesen überflüssigen Block wieder zu entfernen.

Am Ende der Selektion stellen wir die Sequenzierungsinvariante wieder her, indem wir den current_block auf BB3 setzen, welcher im CFG von BB1 dominiert wird. Alle Pfade, die BB3 erreichen, haben vorher BB1 besucht.

Graphiken und Animationen

PreviousNext

Ziemlich ähnlich sieht es bei Iterationen aus. Wir schauen uns an dieser Stelle nur ganz normale while-Schleifen an. Zu Beginn erzeugen wir ebenfalls mehrere Basisblöcke, um den Kontrollfluss der Schleife abzubilden.

Anderes als bei der Selektion spalten wir allerdings die Auswertung der Bedingung in einen eigenen Basisblock (BB1) ab, da dieser nicht nur einmal beim Betreten der Schleife ausgeführt werden soll, sondern vor jedem Schleifendurchgang.

Da wir Code für eine while-Schleife, und keine do-while-Schleife, generieren, betreten wir zuerst den Schleifenkopf BB1, in den wir den Code für die Auswertung der Bedingung hinein generieren. Am Ende des Schleifenkopfes prüfen wir, ob eine weitere Iteration durchgeführt werden soll, oder ob wir hinter die Schleife zu BB3 springen.

Zu Generierung des Schleifenkörpers setzen wir current_block auf BB2 und besuchen den entsprechenden Unterbaum im AST (whileStmt.body). Wiederum könnte der Kontrollfluss innerhalb des Schleifenkörpers gespalten werden, jedoch ist dieser am Ende wieder eindeutig und wir können einen Rücksprung zum Schleifenkopf einfügen, um die nächste Runde der Iteration einzuläuten.

Am Ende der Iteration stellen wir, wie gehabt, die current_block-Invariante wieder her.

Wie bereits bei der Selektion, bei der wir leere Basisblöcke für nicht vorhandene Else-Zweige erzeugen, ist die hier präsentierte Codeerzeugung nicht optimal und der generierte IR-Code geht öfters mal einen Umweg. Wenn wir mit bloßem Augen auf solchen IR-Code schauen, könnten wir auf die Idee kommen zu sagen, dass wir doch direkt besseren IR-Code erzeugen könnten. Jedoch spricht ein wichtiges Argument gegen eine bessere Codeerzeugung: Komplexität.

Die Aufgabe der Codeerzeugung ist es, den AST für eine lineare Maschine zu sequenzieren. Alles, was wir an zusätzlicher Logik in diesem Übersetzerschritt einbauen, um besseren IR-Code zu generieren, wird die Codeerzeugung verkomplizieren. Das eigentliche Ziel der Codeerzeugung wird verwässert und weniger offensichtlich. Und wenn eines an einem Übersetzer, bei dem wir erhöhte Ansprüche an die Korrektheit stellen, von Übel ist, so ist es wenig intuitiver Code, der mehrerer Zielsetzungen gleichzeitig verfolgt.

Im Fall des Übersetzers lösen wir das Dilemma zwischen klarerer Codeerzeugung und einem effizienten Kompilat dadurch auf, dass wir den informatischen Zaubertrick Trennung der Belange anwenden und die Optimierung als weiteren Schritt bei der Übersetzung einführen. So können wir zuerst ineffizienten Code in sehr klarer Weise generieren, und dennoch ein möglichst effizientes Übersetzungsergebnis bekommen.

Außerdem haben wir einen weiteren Vorteil, der auf den Folien sehr lapidar dargestellt wird: Optimierungen werden auch auf den Benutzercode angewendet. Dies ist viel wichtiger als es zunächst erscheint. Stellen Sie sich vor, wir bauen eine Codeerzeugung, die einigermaßen effizienten Code aus dem AST erzeugt. Wenn aber das Programm an sich ineffizient programmiert wurde und Redundanzen enthält, so würden wir diese (sehr effizient) auf IR-Code abbilden. Trennen wir allerdings Codeerzeugung und Optimierung, so werden die Optimierungen nicht nur auf die generierten Ineffizienten, sondern auch auf die ineffizient programmierten Programmstücke angewendet:

int foo() {
   int bar = 2 + 3;
   int x = bar * 2;
   if (x < 0) { x = x * x; }
   int y = x - 9;
   return y;
}

In diesem Stück Beispielcode ist, bei näherer Betrachtung, ganz klar, dass foo() immer das Ergebnis 1 liefern wird. Eine Codeerzeugung zu erstellen, die dies nebenbei herausfindet, ist um Größenordnungen schwieriger, als was ich Ihnen in dieser Vorlesung gezeigt habe. In der nächsten Vorlesung werde ich mehrere, relativ einfache, Optimierungsroutinen diskutieren, die IR-Code so optimieren, dass am Ende tatsächlich nur Return 1 übrig bleibt.

Anders sieht die Geschichte bei Interpretern aus: Dort können wir nicht zuerst aufwendige Optimierung vorschalten, um den Start der Ausführung nicht übermäßig zu verzögern. Daher treffen Codeerzeugungs-Routinen, die eine interpretierte Ausführung zum Ziel haben, andere Abwägungen und führen Codeerzeugung und -optimierung deutlich vermischter aus.

Mit den bisher gesehenen Übersetzungsregeln können wir bereits einfache Programme in IR-Code überführen, sofern sie keine komplexen Datenstrukturen beinhalten. Nun könnten wir an dieser Stelle für alle möglichen Konstrukte, die in Programmiersprachen vorkommen und die wir teilweise schon in der Vorlesung behandelt haben, die Übersetzungsregeln im Detail besprechen. Aber das würde, so dicht aneinander gereiht, eher ermüdend denn erleuchtend für Sie sein. Daher habe ich mich entschieden, ein einzelnes Thema herauszugreifen und an diesem beispielhaft zu demonstrieren, wie wir bei der Codeerzeugung vorgehen. Das Thema, dem wir uns zuwenden wollen, sind RecordsSiehe Zusammengesetzte Typen., da wir an ihnen einer Vielzahl der Abbildungsprobleme begegnen, die auch bei anderen Sprachkonstrukten auftreten.

Die semantische Lücke, der wir bei Record-Datentypen begegnen, lässt sich wie folgt beschreiben: Ein Record-Typ ist eine geordnete Sequenz von Typ–Name-Paaren, die im Verbund auftreten. Wir können auf einzelne Felder eines Record-Objekts lesend bzw. schreibend zugreifen und das gesamte Record-Objekt per Zuweisung oder Funktionsaufruf durch die Gegend schieben. Dadurch, dass Records Verbünde aus mehreren Feldern sind, können Record-Objekte mehr als ein Maschinenwort umfassen.

Das Problem ist, dass bei unserer IR-Maschine alle Variablen genau ein Maschinenwort (32-Bit) breit sind. Eine Variable kann also nicht jedes beliebige Record-Objekt beinhalten. Natürlich könnten wir hergehen und unseren IR-Code erweitern, um eine möglichst einfache Codeerzeugung zu bekommen, jedoch würden wir damit die Übersetzungsleistung einfach weiter nach hinten ins Backend schieben. Außerdem können wir ja nicht für jedes neu erdachte Sprachkonstrukt den IR-Code erweitern, was wiederum eine Anpassung des gesamten Middle- und Backends erforderlich machen würde. Stattdessen werden wir das Sprachkonstrukt "Record" auf den vorgestellten IR-Code abbilden. Dazu greifen wir vier Teilbereiche an: Abbildung auf das IR-Speichermodell, Zuweisungen von Record-Objekten, Feldzugriffe und Funktionsaufrufe.

Graphiken und Animationen

PreviousNext

Als erstes nehmen wir die Abbildung der Record-Objekte auf das Speichermodell der IR-Maschine vor. Dazu bilden wir den strukturierte Record-Typen ab, indem wir festlegen, wie die Felder des Records auf den linearen Speicher abgebildet werden. Diese Abbildungsvorschrift, von abstrakten Record-Objekte auf nebeneinander liegende Speicherzellen, heißt Datenlayout.

Das Datenlayout ist abhängig von Record-Typen und kann von sprachspezifischen und architektonischen Besonderheiten beeinflusst werden. So gibt der C-Sprachstandard vor, dass Felder beim Datenlayout nicht umgeordnet werden dürfen.

Als erstes berechnet der Übersetzer, wie viel Speicher jedes einzelne Feld des Records benötigen würde, wenn es alleine allokiert wird. Enthält unser aktueller Record-Typ wiederum Record-Typen, so wird die Berechnung des Datenlayouts rekursiv für den enthaltenen Typen ausgeführt. Beim Beispiel auf den Folien arbeiten wir auf Byte-Granularität, was also nicht 1:1 auf unsere IR-Maschine übertragbar wäre.

Im zweiten Schritt berechnen wir für jedes Feld einen konstanten Feld-Offset vom Beginn des Objekts im Speicher. Da das Feld b an zweiter Stelle ist, startet sein Inhalt bei einem Offset von 4, was genau der Länge des Feldes a entspricht.

Vor dem Feld c fügen wir eine künstliche Lücke ein, da b mit 5 Bytes irregulär lang ist und c, bei einem kompakten Datenlayout keine durch 4 teilbare Adresse hätte. Solches zusätzliche Alignment, meist auf Maschinenwortbreite, führt zwar durch die entstandenen Lücken zu einem erhöhten Speicherverbrauch, kann aber den erzeugten Maschinencode oft deutlich beschleunigen. Hintergrund hier ist, dass Speicherzugriffe, die nicht Wort-weise ausgerichtet sind, auf vielen Prozessoren langsamer sindBesonders ekelhaft ist es, wenn ein Zugriff die Grenze zwischen zwei Cachezeilen oder zwei Speicherseiten überschreitet..

Haben wir jedem Feld einen Offset gegeben, so können wir die Größe für ein Record-Objekt angeben (in diesem Fall 16 Byte). Jedes Objekt vom Typen struct foo wird später nach genau diesem Layout strukturiert sein, sodass jeder Zugriff auf die Felder eines struct foo-Objekts von diesem Layout ausgehen kann. Außerdem werden die Informationen über das Datenlayout auch in den Informationen für den Debugger vermerkt, sodass dieser ein solches Objekt aus dem Speicher dekodieren und die semantische Zuordnung zwischen Feld und Speicherzelle rückgängig machen kann.

Wollen wir dynamische Typinformationen für unserer Objekte haben, so müssen wir ein zusätzliches Typ-Tag-Feld im Datenlayout vorsehen. Da diesen Typ-Feld bei allen Objekten am gleichen konstanten Offset zu finden sein muss, gibt es nur die Möglichkeit, das Tag-Feld vor dem ersten benutzerdefinierten Feld einzufügen. Alle anderen Felder rücken somit eine Position nach hinten und die Größe unseres Objekts wächst auf 20 Byte an.

Bewaffnet mit dem Datenlayout und der Größe des Typen, können wir nun zur Tat schreiten und IR-Code erzeugen. Für unser Beispiel werden wir ein Wertemodell für Variablen anstreben, da wir die Records in eine Sprache mit Referenzen einbauen wollen. Zur Erinnerung: Wertemodell bedeutet, dass eine Variable vom Typ struct foo ein entsprechendes Objekt enthält und nicht nur eine Referenz darauf (das wäre Referenzmodell). Bei Zuweisungen und Funktionsaufrufen wird das Objekt kopiert, und mit dem Ende der Variablen-Lebenszeit endet auch die Lebenszeit des Objekts. In unserem Beispiel gibt es nur lokale Variablen und keine dynamische Speicherallokation auf Sprachebene.

Treffen wir bei der Codeerzeugung auf eine Variablendeklaration/-definition, so müssen wir, da wir dem Wertemodell folgen, auch ein Objekt vom entsprechenden Typen anlegen. Auf den Folien sehen wir, dass dies für kleine Objekte, die in eine IR-Variable passen sehr einfach ist, und wir dort einfach die Variable bei der aktuellen Funktion (self.current_function) anlegen.

Anders sieht das bei Objekten aus, die größer sind als ein Maschinenwort (4 Byte), worunter auch die Record-Objekte Fallen. Um diese Fälle abzudecken verwenden wir den IR-Befehl StackAlloc, um das Objekt im aktuellen Call-Frame anzulegen. In der angelegten IR-Variable speichern wir nur die Referenz auf das neu angelegte Objekt. Gewissermaßen bilden wir das Wertemodell auf der Sprachebene auf ein Referenzmodell in der IR-Ebene ab. Was dies bedeutet werden wir im Folgenden noch sehen. Wichtig ist aber: eine IR-Variable für ein Record-Objekt enthält nur einen Zeiger!

Wollen wir dynamische Typen haben, ist das Anlegen des Objekts der Zeitpunkt, um den korrekten dynamischen Typen zu setzen. Dies führen wir, wenn gewollt, mit einem einzelnen Store Befehl durch, der ein konstant gewähltes Typ-Tag in das erste Feld des Objekts schreibt. Da wir keine benutzerdefinierten KonstruktorenSiehe Geburt von Objekten. anbieten wollen, sind wir an dieser Stelle mit der Codeerzeugung für eine Variablendefinition fertig.

Graphiken und Animationen

PreviousNext

Als erstes, denn wir sind jetzt stolze Besitzer eines Record-Objekts, wollen wir diese herumreichen und umher werfen. Dies geschieht an mehreren Stellen: Bei einer Zuweisung zu einer Variablen mit einem Record-TypSeien Sie sich gewahr, dass eine Variable vom Typ struct foo* keinen Record-Typ hat, sondern ein Zeiger ist, der auf einen Record verweist., bei Übergabe eines Record-Objekts an eine Unterfunktion und bei Verwendung eines Records als Rückgabewert. Diese drei Stellen werden wir uns im Detail ansehen.

Gemeinsam haben diese Stellen, dass es zur Kopie von Objekten kommt, da wir einer Wertesemantik folgen. Es stellt sich also die Frage: Von wo wird nach wo mit welchem Mechanismus kopiert?

Die Frage nach Quelle und Ziel ist die Frage nach dem R-Wert und dem L-Wert einer Variable mit Record-Typ. Da wir diese Variablen auf IR-Ebene als Zeiger auf Stackobjekte abbilden und dort gewissermaßen eine Referenzsemantik verwenden, fallen R- und L-Wert von Record-Objekten zusammen. In allen Fällen reichen wir einfach den Zeiger auf das Objekt herum. Erst der Verwender des R-/L-Wertes entscheidet dann, ob er aus dem Speicherbereich liest oder schreibt.

Um dies in der Codeerzeugung zu implementieren, fügen wir sowohl in der R-Wert- als auch in der L-Wert-Berechnung für Bezeichner den Sonderfall ein, dass wir ein Variable mit Record-Typen vor uns haben. Wie beim Funktionsaufruf verwenden wir die semantischen Querverweise, um zur Stelle der Variablendefinition zu kommen (expr.decl) und die IR-Variable mit dem Zeiger zu erhalten (ir_obj).

Mit dem Wissen, dass bei Objekten, die größer sind als ein einzelnes Maschinenwort, der L- und der R-Wert zusammenfallen, können wir nun auch in der Zuweisungsoperation einen weiteren Sonderfall (neben dem für Zuweisung zu Variablen) einbauen. Um vom Quellobjekt zum Zielobjekt zu kopieren, rufen wir die Laufzeitfunktion void *memcpy(void *dest, const void *src, size_t n) auf. Die Anzahl der Bytes, die kopiert werden müssen, ergibt sich aus der Berechnung des Datenlayouts.

An dieser Stelle sehen wir eine weitere Designentscheidung, die wir für unseren IR-Befehlssatz getroffen haben. Anstatt einen eigenen IR-Kopier-Befehl einzuführen, der mehr als 4 Byte kopieren kann, bedienen wir uns einer Laufzeitfunktion. Dies ist wiederum eine Entscheidung, die dazu führt, dass wir unseren IR-Code so einfach wie möglich halten können.

Bei Funktionsaufrufen müssen wir sehr ähnliche Probleme lösen wie bei der Zuweisung. Da der Call-Befehl nur Maschinenwörter zwischen Aufrufendem (caller) und Aufgerufenem (callee) transportieren kann, bleibt uns nichts anderes übrig, als eine Referenz auf das übergebene Objekt als Parameter zu verwenden. Da wir allerdings dem Wertemodell folgen wollen, müssen wir mittels der IR-Befehle die Call-by-ValueDer Aufgerufene bekommt eine Kopie des Objekts und keine Referenz (was Call-by-Reference wäre).-Semantik der Sprachebene abbilden. Dazu legen wir eine Aufrufkonvention fest: Zwar bekommt der Aufgerufene einen Zeiger, legt sich aber selbständig eine Kopie in seinem Call-Frame an, die dann im Folgendem anstatt des Parameters verwendet wird.

Im Beispiel übergeben wir src an die Funktion f als Parameter obj. Diese Funktion legt in ihrem Funktionsprolog, bevor eine Instruktion für den Entwickler ausgeführt wird, ein lokales Objekt an, dessen Zeiger in __obj gespeichert wird. Ein Aufruf zu memcpy() erledigt das kopieren der Daten, und fortan wird nur noch __obj verwendet, wo obj im AST steht.

Ein ähnliches Problem haben wir bei der Rückgabe des Objekts. Wiederum wollen wir auf Sprachebene das Objekt "by-Value" zurückgeben, können aber nur Zeiger zwischen Caller und Callee austauschen. Da die Lebenszeit des Rückgabewerts länger sein muss als die Laufzeit der Callee-Funktionsinstanz, müssen wir auch Speicher aus dem Call-Frame des Aufrufendem verwenden, um das Objekt zu transportieren.

Wir erweitern unsere Aufrufkonvention dahingehend, dass eine Funktion, die ein Record-Objekt als Rückgabewert hat, einen zusätzlichen (unsichtbaren) Parameter bekommt, mit dem der Aufrufer eine Zieladresse für die Rückgabe kommuniziert. Bei einem Return-Statement kopiert der Callee seinen Rückgabewert an diese Stelle und führt das eigentliche Return mit dem Zeiger durch.

Zusammengefasst: Unsere Record-Objekte sind zu groß für das IR-Maschinenmodell, weswegen wir diese Objekte auf IR-Ebene immer per Referenz herumreichen und an neuralgischen Stellen Kopien erstellen. Genau an dieser Stelle sehen wir, dass das Wertemodell für Variablen zu vielen Kopien von Objekten führt, denn reale Maschinen haben ebenfalls Register von fixer und begrenzter Größe; auch dort muss ständig memcpy() ausgeführt werden.

Der letzte Teil der Codeerzeugung für Records ist der, für den wir den ganzen Tanz mit den Records überhaupt erst angefangen haben: Wir wollen auf einzelne Felder in einem Record-Objekt zugreifen. Und zwar sowohl lesend als auch schreibend.

Um ein Feld beschreiben zu können, verwendet der Entwickler auf Sprachebene eine Zuweisung. Wir haben gesehen, dass die Codeerzeugung der Zuweisung für die linke Seite einen Zeiger als L-Wert berechnet und den zugewiesenen Wert als R-Wert. Also können wir die Frage nach dem Feldzugriff umformulieren und Fragen: Was ist der L-Wert eines Feldzugriffs und was ist sein R-Wert?

Für den L-Wert müssen wir die Adresse des Feldes berechnen. Diese ergibt sich daraus, dass wir auf die Basisadresse des Objekts den Offset des (statisch benannten) Feldes aus dem Datenlayout addieren. Auf den Folien sehen wir wie dies alles bei lvalue_FieldAccess()FieldAccess ist der AST Knotentyp für den Punkt-Operator: "lhs.name". ineinander greift: Um die Basisadresse der lhs zu berechnen, brauchen wir den L-Wert des Objekts (also die Adresse des Objekts). Aus dem Feldnamen name leiten wir zusammen mit dem Datenlayout das konstante Offset ab und addieren Basisadresse und konstanten Offset zum L-Wert des Feldes.

Wollen wir den R-Wert des Feldes, also seinen Inhalt, haben, so ist das relativ einfach: Dort rufen wir lvalue_FieldAccess() auf, um die Feld-Adresse zu berechnen und schieben einen Load Befehl hinterher, um das Feld auszulesen.

Am Ende möchte ich zu unserem Record-Fallbeispiel für die Codeerzeugung noch einige Bemerkungen machen: Eigentlich haben Records nicht besonders gut in unser IR-Modell gepasst. Aber zu geschickte Erzeugung von IR-Code und durch Einführung von Konventionen war es uns möglich, die zuerst diskutierte Codeerzeugung um ein weiteres Sprachfeature zu erweitern, ohne die virtuelle Maschine zu verändern. In einem richtigen Übersetzer hätten wir es uns also gespart, sowohl Middle- als auch Backend anzupassen, nur weil wir ein neues Feature in der Sprache anbieten wollen.

Ausschließlich die Verwendung von Laufzeitfunktionen zieht ein gewisses Maß an Fallout hinter sich her. Denn, wo kommt den das memcpy() her? Wer fügt die Implementierung in das fertige Programm ein? Zu diesem Zwecke kommt ein Übersetzer nicht nur als ein Binärprogramm, welches aus dem Quellcode ein Assemblerprogramm macht, daher, sondern es gibt sogenannte Run-Time Support Libraries. In diese Bibliotheken platzieren wir jene Funktionalitäten, die wir bei der Abbildung von komplexeren Sprachkonstrukten auf die einfachen IR-Befehle benötigen.

Bei GCC heißt diese Bibliothek libgcc.a. Ein kurzen Überblick über ihren Inhalt kann man mit dem Tool nm bekommenDer Pfad zur libgcc.a kann auf ihrem System anders sein., welches wir in der Vorlesung über Maschinencode noch genauer diskutieren werden:

$ nm /usr/lib/gcc/x86_64-linux-gnu/9/libgcc.a  | grep bswap
_bswapsi2.o:
0000000000000000 T __bswapsi2
_bswapdi2.o:
0000000000000000 T __bswapdi2

In dieser Auflistung sehen wir zwei Funktionen, die GCC verwendet, um die Byte-Order innerhalb eines Wortes zu vertauschen. Eine genaue Auflistung solcher Funktionen findet sich in der GCC Dokumentation. Die äquivalente Implementierung für LLVM wird in der compiler-rt Bibliothek implementiert. Dort finden wir auch die Implementierung für bswapsi2().