Überblick
Wie in der Einführung bereits erwähnt wurde, sollte der erzeugte Compiler ausführbaren Binärcode generieren. Am Anfang stand die Idee, betriebssystemunabhängigen Binärcode zu erzeugen, da schließlich keine Betriebssystemunterstützung nötig ist, um normalen Binärcode auszuführen. Diese Annahme erwies sich ziemlich bald als falsch. Zum Einen wird für Ein- und Ausgaben Betriebssystemfunktionalität benötigt, da heutzutage kein direkter Zugriff auf BIOS-Routinen mehr möglich ist. (Unter Linux und Windows läuft der Prozessor z.B. in einem Modus, der Zugriff auf diese Routinen verbietet, weil sonst die Lauffähigkeit des Systems nicht mehr sichergestellt werden kann.) Zum Anderen muss die erzeugte Binärdatei in einem bestimmten Format vorliegen, welches betriebssystemabhängig ist. So wird von Windows das "Portable Executable Format" (PE) und von Linux das "Executable and Linking Format" (ELF) benutzt.
Am Ende fiel die Entscheidung auf ein Linux-Backend, welches x86-Prozessoren unterstützt.
Assemblercode
Um den Compiler auch im Backend zu modularisieren (und um den Überblick nicht zu verlieren), erzeugt der Compiler den Binärcode nicht direkt aus dem Zwischencode, sondern generiert vorher Assemblercode.
1. Stufe
Der Assemblercode wird in 3 Stufen erzeugt. In der 1. Stufe wird durch die linearisierte (und ggf. optimierte) Zwischencodeliste iteriert und für jede Zwischencodeanweisung der entsprechende Assemblercode generiert und in einer Assemblercodeliste gespeichert. Während sich einige Zwischencodeanweisungen wie "Label" oder "Jump" ganz einfach in eine Assembleranweisung übersetzen lassen, wird aus anderen Zwischencodeanweisungen eine ganze Folge von Assembleranweisungen generiert. So werden zum Beispiel aus der Binäroperation "BINOP" des Zwischencodes folgende Assembleranweisungen:
- Lade Register eax mit Operand 1.
- Lade Register ebx mit Operand 2.
- Führe die entsprechende binäre Operation aus.
- Speichere das Ergebnis.
Und schließlich gibt es auch noch Zwischencodeanweisungen, die so umfangreichen Binärcode erzeugen, dass der Compiler irgendwo im Programm eine Routine (einmalig) einfügt und bei der Übersetzung des Zwischencodes einfach diese Routine aufruft. Beispielsweise gilt dies für die Zwischencodeanweisungen "INPUT" und "OUTPUT".
In der nicht-optimierten Variante des Backends werden in der ersten Stufe alle temporären Variablen gezählt und dementsprechend viele Hauptspeicherzellen als Datensegment angelegt. Wird nun z.B. eine binäre Operation ausgeführt, so werden die Operanden ausgewertet und die beiden entsprechenden Hauptspeicherzellen werden in die Register eax und ebx kopiert. Nun wird die tatsächliche Operation ausgeführt und das Ergebnis im Register eax hinterlegt. Da jeder Zwischenvarible ein Platz im Hauptspeicher zugeordnet ist, erkennt der Compiler durch die Auswertung des Ergebnisausdruckes, an welche Hauptspeicherzelle das Ergebnis im Register eax nun gespeichert werden muss. Die Zwischenvariable X hat (mit 4 Byte pro Wort) also ihren Hauptspeicherplatz an der Stelle Beginn_des_Datensegmentes + 4*X
Leider wurde noch keine optimierte Variante des Backendes implementiert. Damit könnte nömlich eine Vielzahl der Hauptspeicherzugriffe eingespart werden, indem die temporären Variablen nicht grundsätzlich im Hauptspeicher zwischenspeichert, sondern solange es geht im Prozessor (in einem Register) gehalten werden. Die Vorraussetzung dafür wäre lediglich, dass jede beliebige Hauptspeicherzelle in jedes beliebige Register geladen werden kann und dass jedes Register wieder in jeder Hauptspeicherzelle gespeichert werden kann. Das wird auch schon von der Assemblercodegenerierung des Compilers geleistet. Allerdings wird dieses Feature leider noch nicht durch die Binärcodeerzeugung unterstützt und der Algorithmus, der die Zuteilung der temporären Variablen auf die Register steuert, wurde auch noch nicht implementiert.
2. Stufe
In der 2. Stufe der Assemblercodegenerierung werden den Assembleranweisungen die Adressen vergeben, an denen sie dann später im Binärprogramm stehen werden. Das wird erreicht, indem als Erstes die Startadresse für das Codesegment berechnet wird. Das Codesegment steht nach dem ELF-Header und der Program Header Table, also ist seine Startadresse die Größe des ELF-Headers (52 Byte) + Größe der Program Header Table (3 Einträge zu je 32 Byte). Es soll an dieser Stelle nicht weiter auf das Binärformat eingegangen werden, alle notwendigen Informationen stehen in der offiziellen ELF-Dokumentation.
Als Nächstes wird durch die Liste der Assembleranweisungen iteriert und es wird der jeweiligen Assembleranweisung die aktuelle Adresse übergeben. Anschließend wird die Größe der Anweisung (als binäre Anweisung, in Byte) abgefragt und auf die aktuelle Adresse addiert. Damit erhält man die Adresse der nächsten Anweisung usw.
3. Stufe
In der 2. Stufe wurde jeder Assembleranweisung ihre spätere Adresse zugeteilt. Das ist die Vorraussetztung, um nun die Labels aufzulösen. Dazu wird eine Label-Table generiert, d.h. es werden aus dem kompletten Assemblercode alle Labels gesucht und in eine gesonderte Tabelle, die Label-Table, eingetragen. (Das könnte auch weggelassen werden, aber dann müßte man bei jeder Suche nach einem Label wieder die komplette Liste der Assembleranweisungen durchsuchen.) Nun wird wieder durch die gesamte Liste der Assembleranweisungen iteriert und bei jedem Referenzieren eines Labels (bei Sprüngen, Verzweigungen, ...) wird das Label in der Label-Table gesucht, seine Adresse erfragt und schließlich die Assembleranweisung so verändert, dass nicht mehr das Label, sondern die entsprechende Adresse referenziert wird. Mit dem Abschluss dieser 3. Stufe ist der Assemblercode nun komplett generiert.
Maschinencode
Als Letztes soll der Compiler nun aus dem generierten Assemblercode ausführbaren Maschinencode erzeugen. Dieser Teil ist noch nicht ganz vollständig und noch etwas fehlerbehaftet, da die Zeit zur vollständigen Implementation nicht gereicht hat. Die Programmierung des Maschinencodegenerators kann grob in 2 Phasen unterteilt werden.
Vorbereitung
Ganz am Anfang stand die Einarbeitung in das Format des Binärcodes. Wie im letzten Kapitel schon erwähnt wurde, muss ausführbarer Code in einem bestimmten Binärdateiformat vorliegen. Im Fall des Linux-Backends ist es das "Executable and Linking Format" (ELF). Wichtig war dabei, dass beim Durcharbeiten des über 100 Seiten langen Standards kein Fehler gemacht werden sollte, da ein ganzes Programm schon nicht mehr ausführbar sein kann, wenn im Header ein Bit falsch gesetzt ist. Parallel dazu wurde ein kleines Programm geschrieben, welches eine Binärdatei erzeugt. Das größte Problem bei der Binärcodeerzeugung ist im Übrigen die erschwerte Fehlersuche. Eine Datei wird entweder ausgeführt oder nicht ausgeführt (meist mit der Fehlermeldung "Speicherzugriffsfehler"). Wo der Fehler genau liegt, muss dann mehr oder weniger geraten werden. Hinzu kommt noch, dass das Ausführen der Binärdatei erst ausprobiert werden kann, nachdem der ganze Standard durchgearbeitet wurde (weil ja sonst noch Teile der Binärdatei fehlen).
Nachdem es gelang, ein kleines Binärprogramm auszuführen, wurde getestet, wie sich die Ein- und Ausgabe, also Systemaufrufe, implementieren lassen. Die Ausgabe hat auch ziemlich schnell und ohne größere Probleme funktioniert, allerdings handelte es sich dabei nur um einen String, der ausgegeben wird. Es sollen im Fall des PL/0-Compilers aber Zahlen ausgegeben werden. Das heißt, das erzeugte Binärprogramm muss eine im Register gegebene Zahl in einen String umwandeln und diesen dann ausgeben. Und die Übersetzung der Zahl in einen String muss auch ausschließlich mit Maschinencode geschehen.
Der Output-Binärcode wird statisch in die Binärdatei geschrieben - sozusagen als Funktion. Der Outputknoten des Zischencodes wird in folgende Assembler-Anweisungen übersetzt:
- Sichere alle Register (auf dem Stack)
- Speichere die auszugebende Zahl im Register eax
- Rufe die statische Output-Funktion auf
- Lade alle gesicherten Werte vom Stack zurück ins Register
Die statische Output-Funktion macht nun Folgendes: Die Zahl wird im Register gehalten und solange sie größer als Null ist, durch Zehn dividiert. Der Rest ist jeweils eine auszugebende Ziffer und die Zahl wird somit von hinten nach vorne gebildet.
Der Algorithmus im Detail:
Man beachte, dass Zeichenketten von hinten nach vorn aufgebaut werden müssen, da die einzelnen Elemente der Zeichenkette auf einem Stack liegen, und dieser bei der Ausgabe von oben nach unten abgearbeitet wird.
Stackpointer sichern (im Register ebp, dieses wird im Laufe der Berechnung nicht verändert).
Den Wert 0x00 auf den Stack legen (push). (Linux verwendet nullterminierte Strings.)
Den Wert "\n"(=0x0a) auf den Stack legen. (Zeilenumbruch nach ausgegebener Zahl)
Prüfen, ob eax > 0. Ergebnis in ebx zwischenspeichern (codieren).
Falls eax < 0: eax = -eax.
Label 1:
Abfrage, ob eax == 0. Wenn ja, dann zu Label 2 springen.
eax durch 10 dividieren. (Der Maschinenbefehl DIV dividiert eax durch eine angegebene Zahl und legt den Quotient
in eax, den Rest in edx ab.)
edx um 48 erhöhen. (Umwandlung der Zahl in Zeichen, die Zeichen '0' bis '9' sind codiert als 48d bis 57d)
edx auf den Stack legen.
Zu Label 1 springen.
Label 2:
ebx überprüfen, ggf. '-' auf den Stack legen.
Leerzeichen auf den Stack legen.
Das Zeichen '!' auf den Stack legen.
Systemaufruf write durchführen (Ausgabestring = Stackpointer).
Alten Stackpointer wiederaufsetzen.
Zurückkehren.
|
Der genaue Code steht in backend/operators/AsmPreDef.
Binärcodegenerierung
Bei der Binärcodegenerierung wird der folgende Code ausgeführt:
CreateFile();
WriteELFHeader();
WritePHT();
WriteTextSeg();
WriteDataSeg();
WriteStrTab();
WriteSHT();
SaveCloseFile();
|
WriteELFHeader(), WritePHT(), WriteStrTab() und WriteSHT() sorgen dafür, dass die erzeugte Datei genau das Format hat, welches im ELF-Standard spezifiziert wird und somit, dass die Datei vom Betriebssystem gelesen und ausgeführt werden kann.
Von WriteTextSeg() wird nun der eigentliche ausführbare Code generiert. Dafür wird durch die Liste der Assembleranweisungen iteriert. Und weil jedes Assemblerstatement eine Methode getCode() besitzt, welche den Binärcode der Assembleranweisung zurückliefert, kann ganz einfach aus der Assemblerliste der Binärcode erhalten werden. Die Programmierung der Methode getCode() für jeden Spezialfall der Assembleranweisung entspricht der eigentlichen Binärcodegenerierung, weil hier jede Assembleranweisung in Binärcode kodiert wurde. Welche Assembleranweisung welcher Binärcodesequenz entspricht, steht dabei im "IA-32 Intel Architecture Software Developer's Manual", Teil 2 ("Instruction Set Reference").
Durch WriteDataSeg() wird schließlich jede temporäre Variable in die Binärdatei geschrieben. Wenn diese nun ausgeführt (also in den Hauptspeicher geladen) wird, so haben die temporären Variablen genau an dieser Stelle ihre Hauptspeicherzelle, in der sie zwischengespeichert werden können. So ein Datensegment könnte auch beim Laden der Binärdatei erst generiert werden, so dass die (gespeicherte) Binärdatei etwas kleiner wird, aber diese Lösung verursacht mehr Aufwand und wurde deshalb verworfen.
 Optimierung des Zwischencodes | Der Interpreter  |