Compiler-Bau, Teil 5
Ein für viele Programmierer wichtiges Kriterium für die Beurteilung eines Compilers ist die Güte der Codeerzeugung. Diese hängt stark davon ab, nach welchem Prinzip das Back-End des Compilers implementiert ist und ob noch zusätzliche Optimierungsphasen eingebaut wurden. Manchmal ist es auch möglich, mittels einer Option zwischen einem gut optimierten Code, dessen Generierung recht lange braucht, und einem schlechten Code, der dafür schnell erzeugt wird, zu wählen. Mit solch einem Compiler kann man während der Testphase eines Programms schnell arbeiten und bei der Fertigstellung doch einen optimierten Code erzeugen.
Wir wollen uns in dieser letzten Folge der Serie über Compiler-Bau mit verschiedenen Techniken der Codeerzeugung beschäftigen. Dabei werden wir auch kurz die Probleme betrachten, die beim Schreiben eines optimierenden Compilers zu lösen sind. Um ein Gefühl für die Komplexität der Codegenerierung zu bekommen, wollen wir uns zuerst einmal die Aufgaben ansehen, die die Codeerzeugung zu bewältigen hat. Es sind dies die Codeauswahl, die Speicherzuteilung, die Registerallokation und die Bestimmung der Berechnungsreihenfolge. Bei der Codeauswahl wird jeder Zwischencodeanweisung (siehe letzte Folge) oder jedem Knoten des attributierten Strukturbaums eine Folge von Instruktionen der Zielsprache zugeordnet. Da es meist möglich ist, ein und dasselbe Sprachkonstrukt mit verschiedenen Befehlsfolgen zu übersetzen und in verschiedener Umgebung oft verschiedene Folgen optimal sind, ist eine gute Codeauswahl recht schwierig. Die Speicherzuteilung sorgt dafür, daß jedem Objekt der Quell spräche ein ausreichend großes Stück Speicher zur Verfügung gestellt wird, und beschreibt gleichzeitig die verschiedenen Möglichkeiten des Zugriffs auf diesen Speicherbereich. Dabei muß unter Umständen auch für eine rechtzeitige Anforderung und Freigabe des Speichers zur Laufzeit gesorgt werden. Die Registerallokation ist für eine geschickte Verteilung der Variablen und Zwischenergebnisse auf Prozessorregister zuständig. Dies muß natürlich in enger Zusammenarbeit mit der Speicherzuteilung geschehen. Die Bestimmung der Berechnungsreihenfolge ist nicht trivial, da eine Umstellung der Reihenfolge von Berechnungen in manchen Fällen zu einem besseren Code führt. Braucht der linke Operand einer Addition zur Berechnung zum Beispiel zwei und der rechte drei Register, so wird bei einer naiven Codeerzeugung zuerst der linke Operand berechnet und sein Ergebnis in einem Register zwischengespeichert. Dieses Register für das Zwischenergebnis plus die drei Register für die Berechnung des rechten Operanden führen zu einem Bedarf von vier Registern. Wird hingegen zuerst die aufwendigere Berechnung des rechten Operanden (drei Register) durchgeführt, dann der linke Operand unter Benutzung von zwei Registern berechnet, wobei gleichzeitig ein Register für das Ergebnis des rechten Operanden gebraucht wird, so kommt man hier mit insgesamt drei Registern aus. Die komplette Berechnung kann also in drei statt vier Registern ausgeführt werden, wenn die Reihenfolge der Operandenberechnungen richtig gewählt wird. Um einen guten Code zu erzeugen, ist es wichtig, daß diese vier Aufgaben nicht nur für sich alleine gut gelöst werden, sondern auch optimal aufeinander abgestimmt sind. Zu beachten ist außerdem, daß es oft möglich ist, Speicherplatz zu sparen, indem ein Code gewählt wird, dessen Abarbeitung langsamer ist, und umgekehrt kann ein schnellerer Code erzeugt werden, der mehr Speicherplatz belegt. Welches Übel dabei weniger schlimm ist, hängt vom Anwendungsfall ab und kann bestenfalls per Option eingestellt werden.
Optimal
Die vier Aufgaben der Codeerzeugung können in der Regel problemlos auf dem attributierten Strukturbaum ausgeführt werden. Eine Zwischencodeerzeugung ist dabei höchsten zur leichteren Portabilität des Compilers auf andere Zielmaschinen nötig. Möchte man nicht nur einen Compiler mit einer guten Codeerzeugung schreiben, sondern einen wirklich optimierenden, so ist eine Zwischencodeerzeugung allerdings unumgänglich. Eine sehr einfache Form der Optimierung, die auch auf dem Zielcode durchgeführt werden kann, ist die Peephole-Optimierung. Der Code wird hierbei durch eine Art Guckloch (daher auch der Name) oder Fenster betrachtet, in dem nur ein kleiner Ausschnitt des Codes sichtbar ist. Sobald der Inhalt dieses Fensters mit einer von mehreren gespeicherten Schablonen übereinstimmt, wird er durch ein äquivalentes aber optimaleres Codestück ersetzt. Trotz der Einfachheit dieses Verfahrens kann es schlechteren Code oft stark verbessern. Aufgrund seiner Natur ist es allerdings nur für lokale Optimierungen geeignet. Sehr viel mächtiger, aber auch komplizierter, ist eine sogenannte Datenflußanalyse. Mit ihrer Hilfe können recht vielfältige Optimierungen durchgeführt werden, deren wichtigste Vertreter wir uns später noch kurz ansehen werden. Eine genaue Behandlung dieses Stoffs würde den Rahmen des Artikels aber sprengen, deshalb seien näher Interessierte auf [ 1 ] verwiesen. In diesem Buch werden die Codeoptimierung und ihre wichtigsten Algorithmen ausführlich behandelt. Allerdings ist gerade die globale Datenflußanalyse ein recht harter Brocken. Nach der Codeoptimierung gehen wir gegen Ende dieser Folge kurz auf Werkzeuge zur automatischen Generierung von Back-Ends ein. Zum Abschluß werden die beiden inzwischen schon mehrfach zitierten Bücher kurz vorgestellt und eine kleine Aufgabe gestellt. Doch zunächst werden wir uns ansehen, wie man die vier Aufgaben der Codeerzeugung lösen kann. Dazu werden wir uns hauptsächlich mit der Codeerzeugung von arithmetischen Ausdrücken befassen. Diese stellen in der Regel neben Prozedur- und Funktionsaufrufen die größten Anforderungen an den Codegenerator, und man kann die verschiedenen Implementierungstechniken recht gut an ihnen studieren.
Eingekellert
Zum Einstieg wollen wir uns erst einmal das einfachste Verfahren zur Codeerzeugung ansehen. Es beruht darauf, daß jeder normale arithmetische Ausdruck unabhängig von seiner Schachtelungstiefe in einen Postfixausdruck umgewandelt werden kann. Postfix heißteinfach, daß ein Operator immer nach seinen Operanden steht. Der Postfixausdruck zu ‘2 + 3’ ist also ‘2 3 +'. Klammerebenen fallen dabei weg, wie man zum Beispiel an dem Postfixausdruck für ‘a := (3 + 4) * 2‘ sieht, der ‘a 3 4 + 2 * :=‘ lautet. ‘3 4 +’ wird dabei zu ‘7’ reduziert, dann ‘7 2 *' zu ‘14‘ ausgewertet und abschließend in die Speicherstelle der Variablen a geschrieben. Solche Postfixausdrücke lassen sich sehr einfach mit einer Kellermaschine auswerten. Eine Kellermaschine besteht, wie ihr Name schon sagt, im wesentlichen aus einem Keller, der zum Ablegen von Zwischenergebnissen dient. Sie besitzt zum Beispiel die Befehle LOAD, LOADA, ADD, SUB, MUL, DIV und ASSIGN, wobei LOAD den angegebenen Wert oder den Inhalt einer Variablen auf dem Keller ablegt und LOADA dies mit der Adresse einer Variablen tut. ADD, SUB, MUL und DIV nehmen jeweils die zwei obersten Werte vom Keller und addieren, subtrahieren, multiplizieren oder dividieren sie je nach Befehl. Das Ergebnis wird zum Schluß auf dem Keller abgelegt. ASSIGN schreibt den Wert, der auf dem Keller zuoberst steht, in die Speicherstelle, deren Adresse im Keller zu zweitoberst liegt. Dem Ausdruck ‘a := (3 + 4) * 2’ und damit auch dem Postfixaudruck ‘a 3 4 + 2 * :=’ entspricht somit das folgende Kellermaschinenprogramm:
LOADA a LOAD #3 LOAD #4 ADD LOAD
#2 MUL ASSIGN
Das Gatterzeichen ‘#’ beschreibt hierbei die Tatsache, daß der dahinterstehende Wert direkt benutzt werden soll und keine Speicheradresse darstellt. Außerdem muß statt der Variablen a natürlich die Adresse der Speicherstelle angegeben werden, in der der Wert von a stehen soll. In Abb. 1 werden die einzelnen Zustände der Kellermaschine grafisch dargestellt.
LOAD %1 : MOVE.W %1, -(A7)
LOADA %1: PEA %1
ADD : MOVE.W (A7)+, D0
ADD.W D0, (A7)
SUB : MOVE.W (A7)+, D0
SUB.W D0, (A7)
MUL : MOVE.W (A7)+, D0
MULS (A7), D0
MOVE.W D0, (A7)
DIV : MOVE.W 2(A7), D0
DIVS (A7)+, D0
MOVE.W D0, (A7)
ASSIGN : MOVE.W (A7)+, D0
MOVE.L (A7)+, A0
MOVE.W D0, (A0)
Tabelle 1: Implementierung von Kellermaschinenbefehlen in 68000er-Code
PEA a
MOVE.W #3, -(A7)
MOVE.W #4, -(A7) ; 1
MOVE.W (A7)+, D0 ; 2
ADD.W D0, (A7)
MOVE.W #2, -(A7) ; 3
MOVE.W (A7)+, D0 ; 4
MULS (A7), D0
MOVE.W D0, (A7) ; 5
MOVE.W (A7)+, D0 ; 6
MOVE.L (A7)+, A0
MOVE.W D0, (A0)
*Listing 1: Einfacher 68000er-Code zur Berechnung von ’a := (3 + 4) 2’
PEA a
MOVE.W #3, -(A7)
MOVE.W #4, D0
ADD.W D0, (A7)
MOVE.W #2, D0
MULS (A7)+, D0
MOVE.L (A7)+, A0
MOVE.W D0, (A0)
Listing 2: Einfacher Code nach Peephole-Optimierung
Unter jeder Anweisung ist der Zustand nach ihrer Abarbeitung abgebildet. Da es sehr einfach ist, mit einem Mikroprozessor wie dem 68000 eine Kellermaschine zu simulieren, kann ein Kellermaschineprogramm sehr leicht in 68000er-Code umgesetzt werden. Tabelle 1 zeigt die Implementierung der Kellermaschinenbefehle durch 68000er-Code. Dabei ist im LOAD- und LOADA-Befehl %1 ein Platzhalter, der durch den jeweiligen Operanden ersetzt wird. Listing 1 enthält die Übersetzung der Befehlssequenz für den Ausdruck ‘a := (3 + 4) * 2’ mit Hilfe der Schemata aus Tabelle 1. Dieser Code erfüllt die gestellte Aufgabe offensichtlich korrekt, ist aber sehr umständlich. Die Ineffizienz des Codes fällt an den durch Zahlen markierten Stellen besonders stark ins Auge. Die Anweisungen 1 und 2 bzw. 3 und 4 können sehr leicht zu je einer zusammengefaßt werden. Die mit 5 und 6 markierten Anweisungen können sogar komplett entfallen, da sie sogenannte inverse Operationen darstellen, d.h. die eine Operation hebt die Wirkung der anderen auf. Allerdings muß dann im vorausgehenden MULS-Befehl mit Postinkrement vom Keller gelesen werden. Durch diese Optimierungen wird der Code kürzer, es entfallen Speicherzugriffe, und es wird weniger Platz auf dem Keller beansprucht.
Interessanterweise können alle drei Verbesserungen ohne weiteres von einen Peephole-Optimierer durchgeführt werden. Der Code nach der Peephole-Optimierung ist in Listing 2 abgebildet. Nach diesen Optimierungen ist der wesentliche Kritikpunkt am bisher erzeugten Code, daß die Register der 68000 nur sehr spärlich benutzt werden. Wie man diese besser nutzen kann, werden wir gleich besprechen. Doch vorher wollen wir uns noch ansehen, wie man den Code für eine Kellermaschinensimulation direkt aus dem attributierten Strukturbaum gewinnen kann, und wie wir die am Anfang erwähnten vier Aufgaben der Codeerzeugung bisher gelöst haben. Am Ende der letzten Folge wurde das Thema Zwischencode schon erwähnt. Im Prinzip sind unsere Kellermaschinenbefehle (LOAD etc.) nichts anderes als Zwischencodebefehle. Wir können sie also in einem Baumdurchlauf direkt aus dem attributierten Strukturbaum erzeugen. Eine attributierte Grammatik (siehe letzte Folge), die genau das leistet, ist in Listing 3 abgebildet. Der Operator *++’ dient wie schon in der letzten Folge zur Aneinanderreihung von Zwischencodebefehlen. Mit dieser attributierten Grammatik wird der Strukturbaum des Ausdrucks ‘a := (3 + 4) * 2’ genau in die weiter oben angegebene Sequenz von Kellermaschinenbefehlen transformiert. Da die Umwandlung des Kellercodes nach Tabelle 1 einer einfachen Makroexpansion entspricht, können die einzelnen Kellermaschinenbefehle in der attributierten Grammatik auch gleich durch die entsprechenden 68000er-Befehle ersetzt werden.
Trotzdem ist die Einführung einer Zwischensprache für das Design eines Compilers immer sinnvoll, auch wenn sie wie hier schlußendlich nie explizit vom Compiler benutzt wird. Denn die Zwischensprache erlaubt eine anschaulichere und übersichtlichere Darstellung der Codeerzeugung und hilft, daß wichtige Zusammenhänge nicht im Detail des Zielmaschinencodes untergehen. Damit wäre die Codeauswahl komplett. Was noch vollkommen fehlt, ist eine Speicherzuteilung für die Variablen. Prinzipiell legt der Compiler alle globalen Variablen einfach hintereinander im Speicherbereich für globale Daten ab und berechnet dabei jeweils den Offset vom Anfang dieses Segments oder des kompletten Programms. Dieser Offset wird statt der richtigen Adresse ins Programm eingesetzt. Die korrekte absolute Adresse wird dann beim Programmstart von der Relozierroutine des Betriebssystems ermittelt. Die lokalen Daten der einzelnen Funktionen und Prozeduren werden im Gegensatz dazu auf dem Laufzeit-Stack im Activation-Record der zugehörigen Routine abgelegt, wie dies schon in der zweiten Folge besprochen wurde. Die Speicherzuteilung muß also für jede Prozedur den Speicherbedarf der lokalen Daten berechnen und dafür sorgen, daß am Anfang jeder Prozedur Code erzeugt wird, der den von der Prozedur benötigten Platz auf dem Stack reserviert. Außerdem muß der Platz am Ende der Abarbeitung der Prozedur wieder freigegeben werden. Für jede lokale Variable wird dann der Offset vom Link-Pointer (siehe Folge 2) berechnet. Da das genaue Vorgehen der Speicherzuteilung sehr stark von der zu übersetzenden Programmier spräche abhängt, wollen wir hier nicht weiter darauf eingehen. Nach Codeauswahl und Speicherzuteilung bleiben von den vier erwähnten Aufgaben der Codeerzeugung noch die Registerallokation und die Bestimmung der Berechnungsreihenfolge übrig. Beides bleibt in der bisher vorgestellten naiven Codegenerierung im Prinzip unberücksichtigt, was ein wesentlicher Grund für den relativ schlechten Code ist.
RULE Assign ::= Ident ':=' Expr.
ATTRIBUTION
Assign.Code := {LOADA Ident:} ++ Expr.Code ++ {ASSIGN;};
RULE Expr ::= 'Expr' + 'Expr'.
ATTRIBUTION
Expr[0].Code := Expr[1].Code ++ Expr[2].Code ++ {ADD;};
RULE Expr ::= 'Expr - 'Expr'.
ATTRIBUTION
Expr[0].Code := Expr[1].Code ++ Expr[2].Code ++ {SUB;};
RULE Expr ::= 'Expr' * 'Expr'
ATTRIBUTION
Expr[0].Code := Expr[1].Code ++ Expr[2].Code ++ {MUL;};
RULE Expr ::= ’Expr’ / 'Expr'.
ATTRIBUTION
Expr[0].Code := Expr[1].Code ++ Expr[2].Code ++ {DIV;};
RULE Expr ::= Ident.
ATTRIBUTION
Expr[0].Code := {LOAD Ident;};
Listing 3: Attributierte Grammatik zur Codeerzeugung für die Kellermaschine
Register machen Beine
Ziel der Registerallokation ist es, möglichst viele Zwischenergebnisse von komplexen Berechnungen im Prozessor zu speichern und so die Anzahl der Speicherzugriffe zu minimieren. Eine Möglichkeit, die Prozessorregister besser zu nutzen, als wir es bisher getan haben, ist, die zur Verfügung stehenden Register als die obersten Elemente des Kellers zur betrachten. Erst wenn in den Registern kein Platz mehr ist, wird der echte Keller benutzt. Das Ganze ist möglich, da der Compiler die Stack-Belegung zur Übersetzungszeit berechnen und die nötigen Registerzugriffe damit erzeugen kann. Sobald ein Prozedur- oder Funktionsaufruf vorkommt, müssen die Registerinhalte allerdings doch noch auf dem Stack abgelegt werden, da sie möglicherweise während des Aufrufs verändert werden. Dieses Ablegen der Register bezeichnet man als Spilling.
Mit dieser Art der Registerallokation wollen wir uns aber nicht weiter befassen, sondern uns stattdessen gleich ein besseres Verfahren ansehen. Dies setzt die Techniken der semantischen Analyse zur Registerallokation ein. Ein Vorteil des Verfahrens ist, daß man die Bestimmung der Berechungsreihenfolge sowie ein paar weitere Optimierungen leicht integrieren kann. Außerdem ist dabei eine elegante Einbettung der ersten Phase der Codegenerierung in die semantische Analyse möglich. Die wesentliche Information zur Registerallokation ist hierbei, wieviel Register für die Berechnung der einzelnen Teilausdrücke eines kompletten Ausdrucks gebraucht werden. Als Beispiel wollen wir uns den Strukturbaum des Ausdrucks ‘a * b + (c + d) * (e + f)’ ansehen, der in Abb. 3 dargestellt ist.
RULE Expr := 'Expr' Operator 'Expr'.
ATTRIBUTION
Expr[0].LeftFirst := (Expr[1].Registers >= Expr[2].Registers);
Expr[1].Registers := IF Expr[1].Registers = Expr[2].Registers
THEN min(Expr[2].Registers + 1, n)
ELSE max (Expr[2].Registers, Expr[3].Registers
END;
Expr[3].Store := FALSE;
Expr[2].Store := (Expr[2].Registers = n) AND (Expr[3].Registers = n)
RULE Expr := Ident.
ATTRIBUTION
Expr.Registers := 1;
Expr.LeftFirst := TRUE;
Listing 4: Attributierte Grammatik zur Registerallokation
An jedem Knoten des Baums steht die Anzahl der Register, die zur Berechnung des kompletten Teilbaums, der von dem Knoten ausgeht, benötigt werden. Zur Berechnung eines Blattes (in unserem Beispiel eines der Bezeichner) wird ein Register gebraucht - und zwar das Register, in das der Wert des Bezeichners geladen wird. Für jeden Knoten des Strukturbaums wird dann wie folgt entschieden. Benötigen beide Unterbäume des Knotens gleich viele Register, ist es egal, in welcher Reihenfolge die beiden Unterbäume berechnet werden, und der Knoten, der die beiden verbindet, benötigt zur Berechnung ein Register mehr als je einer der Teilbäume. Dieses zusätzliche Register wird gebraucht, um das Ergebnis der Berechnung des ersten Teilbaums während der Berechnung des zweiten zwischenzuspeichern. Benötigt einer der Unterbäume mehr Register als der andere, so wird er zuerst berechnet, und der verbindende Knoten benötigt zur Berechnung genauso viele Register wie der teurere Teilbaum.
Das ergibt sich daraus, daß das Ergebnis der ersten, teureren Berechnung während der Auswertung des zweiten Teilbaums in einem der Register gespeichert werden kann, das gegenüber der ersten Berechnung nicht gebraucht wird. In der Abbildung sind die Kanten des Strukturbaums mit römischen Ziffern gekennzeichnet, die angeben, ob sie als erster oder zweiter Teilbaum berechnet werden. In dem Beispiel wird der Teilausdruck ‘(c + d) * (e + f)’ vor ‘a * b’ berechnet. Macht man es andersherum, müssen für die Berechnung des gesamten Ausdrucks vier statt drei Register bereitgestellt werden, da bei der teureren Berechnung drei Register plus eins, zum Speichern des Ergebnisses von 'a * b' gebraucht würden.
Wie wir sehen, haben wir auf diese Art und Weise die Anzahl der benötigten Register und die Berechnungreihenfolge in einem Rutsch ermittelt. Eins haben wir dabei allerdings außer acht gelassen. Ein realer Mikroprozessor hat natürlich nur eine begrenzte Anzahl von Registern. Daher ist es nötig, für jeden Knoten des Strukturbaums zu überprüfen, ob das Ergebnis der zugehörigen Berechnung als Zwischenergebnis im Speicher, also etwa auf dem Laufzeit-Stack, abgelegt werden muß. Dies ist nie der Fall, wenn einer der Teilbäume mehr Register als der andere benötigt. Denn dann braucht der Vaterknoten ja die gleiche Zahl von Registern wie der teurere Unterknoten. Brauchen beide Teilbäume zur Berechnung aber gleichviel Register, muß das Ergebnis der Berechnung des ersten Teilbaums im Speicher abgelegt werden, falls die Anzahl der Register je Teilbaum gleich der Anzahl der überhaupt vorhandenen Register ist. Der Vaterknoten braucht dann zur Berechnung natürlich genausoviel Platz wie seine Unterbäume, also alle Register. Eine attributierte Grammatik, die diese Berechnungen durchführt, ist in Listing 4 angegeben. Das Nichtterminal Operator steht dabei für einen beliebigen binären Operator wie ‘+’, etc., und der Wert ’n’ gibt die Anzahl der insgesamt verfügbaren Register an.
Die drei berechneten Attribute sind Registers, LeftFirst“ und Store. Registers gibt an, wieviele Register zur Berechnung des Teilbaums geraucht werden, dessen Knoten das Attribut besitzt. LeftFirst ist TRUE, falls der linke Unterbaum des Knotens zuerst ausgewertet werden soll, und Store ist TRUE, falls das Ergebnis der Berechnung dieses Knotens im Speicher abgelegt werden muß, da die Register nicht reichen. Das vorgestellte Berechnungsschema ist natürlich etwas vereinfacht, da ein Mikroprozessor wie der 68000er Befehle besitzt, die bestimmte Aufgaben mit weniger Registern lösen. Zum Beispiel kann ein Wert aus dem Speicher direkt zu einem Registerinhalt addiert werden. Um diese Befehlsart mit einzubeziehen, wird das Attribut Registers in der zweiten Regel der attributierten Grammatik nicht mit 1, sondern mit 0 initialisiert. Andere Besonderheiten lassen sich meist durch zusätzliche Regeln, die bestimmte Sonderfälle abhandeln, beschreiben. Allerdings sollte man an dieser Stelle noch nicht versuchen, Probleme der Codeselektion zu lösen, d.h. Optimierungen der Art, daß statt einem ADD.L #c, D0’ auch der schnellere und kürzere Befehl ‘ ADDQ.L#c, D0’ verwendet werden kann, wenn c zwischen 1 und 8 liegt.
Aus dem so attributierten Strukturbaum kann dann, ähnlich wie dies für die Kellermaschinencodes vorgestellt wurde, in einem weiteren Baumdurchlauf Code erzeugt werden. Nur werden die einzelnen Werte nicht auf dem Keller, sondern in Registern abgelegt. Nur wenn das Store-Attribut in einem Knoten gesetzt ist, wird das Ergebnis der Berechnung in den Speicher geschrieben. Da bisher nur festgelegt wurde, welcher Teilausdruck wieviele Register zu seiner Berechnung benötigt, muß bei der Auswahl des Codes noch eine Zuordnung der vorhandenen Prozessorregister zu den einzelnen Zwischenergebnissen durchgeführt werden. Dazu merkt man sich immer die Liste der aktuell unbelegten Register. Sobald ein neuer Wert geladen wird, wird eines dieser Register belegt. Beim Durchführen einer arithmetischen Operation werden die Register, in denen die Operanden gespeichert sind, nach der Operation wieder frei. Allerdings wird bei einem Prozessor wie dem 68000er das Register des zweiten Operanden nach der Operation durch das Ergebnis belegt. Sobald soviel Aufwand getrieben wird, um die Prozessorregister besser auszunutzen, sollte die Auswahl der Instruktionen, die zur Implementierung der Berechnungen der einzelnen Strukturbaumknoten verwandt wird, auch sorgfältiger durchgeführt werden. Bisher war die Codeauswahl darauf beschränkt, pro Knotentyp eine bestimmte Instruktionsfolge zu erzeugen, die die entsprechende Aufgabe, wie Wert laden oder zwei Werte addieren, durchführt. Besser ist es natürlich pro Knotentyp verschiedene Codesequenzen zur Verfügung zu stellen, um je nach Situation die beste auswählen zu können. Die Kriterien für diese Auswahl hängen natürlich stark von der Zielmaschine bzw. von deren Instruktionssatz ab.
Sicherlich wird auch das oben berechnete Store-Attribut zur Auswahl herangezogen, um je nachdem, ob das Ergebnis und/oder einer oder beide Operanden im Speicher liegen, die optimale Befehlsfolge auszuwählen. Die Auswahl der Codesequenzen läßt sich zum Beispiel anhand von Tabellen durchführen, wie dies etwa in [3] beschrieben wird. Immer mehr Verbreitung findet aber auch die Codeauswahl durch Mustererkennung, die wir gleich noch besprechen werden, und die sich auch sehr gut zum Bau von Generatoren für die Codeerzeugung eignet. Vorher sol 1 aber noch erwähnt werden, daß durch die Berechnung geeigneter Attribute auch boolsche Verknüpfungen optimiert übersetzt werden können. Außerdem ist es möglich, die Berechnung arithmetischer Ausdrücke durch die Verwendung algebraisch identischer Ausdrücke zu optimieren. Zum Beispiel kann es vorteilhaft sein, ‘(-a) * b' statt ’a * (-b)’ zu berechnen. Aus ’(-x) * (y - z)’ wird damit ’x * (z - y)’, was eine Negation erspart. Als nächstes wollen wir uns ein recht gutes Verfahren zur Codeselektion ansehen, das für viele verschiedene Typen von Zielmaschinen Verwendung finden kann.
Musterhafter Code
Das Grundprinzip der Codeerzeugung durch Mustererkennung (pattern matching) ist recht einfach. Der Codegenerator sucht in dem Strukturbaum nach Teilbäumen, die auf eins der ihm bekannten Muster passen. Sobald er einen solchen Teilbaum erkennt, erzeugt er einen zu dem Muster gehörenden Code, in den er unter Umständen noch Werte aus dem Strukturbaum einsetzt. Außerdem wird der Teil- im Strukturbaum durch ein neues Blatt ersetzt. Jedes der Muster zusammen mit dem Code und dem neuen Blatt ist eine Regel des Codegenerators. In Abb. 4 sind Regeln abgebildet, die es erlauben, Code für einen einfachen arithmetischen Ausdruck zu erzeugen. Eine Regel besteht aus einem Musterbaum und einem Strukturbaumblatt, die durch einen Pfeil verbunden sind. Eine solche Regel besagt, daß ein Teilbaum, der auf das vorgegebene Muster paßt, in das Blatt umgewandelt werden kann. Über dem Pfeil kann noch eine zusätzliche Bedingung stehen, die die Anwendbarkeit der Regel einschränkt, wie dies bei Regel (5) der Fall ist. Steht unter dem Pfeil ein Sternchen (*), kann die Regel auch angewandt werden, wenn die beiden Operanden des Teilbaums gegenüber dem Muster vertauscht sind. In Regel (4) ist es zum Beispiel auch möglich, daß die Konstante auf der rechten und das Register auf der linken Seite stehen.
Unter jeder der Regeln steht der Code, der erzeugt wird, sobald der Codegenerator die Regel anwendet. Die Anwendung der Regel (1) beendet die Codegenerierung, was durch den Punkt auf der rechten Seite des Pfeils angedeutet wird. Die Strukturbaumblätter mem, reg und const stehen für verschiedene Speicherklassen, wobei mem einen Operanden im Speicher, reg einen Registeroperanden und const einen konstanten Wert repräsentiert. Das Attribut der Speicherklasse wird jeweils in eckiger Klammer angegeben und ist für mem hier der Einfachheit halber der Name der Variablen, für reg die Registernummer (hier nur Datenregister) und für const der Wert der Konstanten.
In Abb. 5 wird mit den eben vorgestellten Regeln der Strukturbaum für den Ausdruck ‘x := 1 + y + z’ in Code umgewandelt. Der Teil des Baums, der auf das Muster der jeweils an ge wendeten Regel paßt, ist durch einen gestrichelten Rahmen gekennzeichnet. Die Nummer der jeweils angewendeten Regel wird über den einzelnen Pfeilen angegeben, unter dem Pfeil steht der durch die Regel erzeugte Code. Zum Schluß ist der komplette Code noch einmal am Stück angegeben. Vergleicht man den erzeugten Code mit dem, was die einfache Erzeugung von Kellermaschinecode für dieses Beispiel generieren würde, so wird die Überlegenheit der neuen Methode sehr deutlich. Eine Peephole-Optimierung erübrigt sich vollständig, da die Mustererkennung spezielle Teilbäume, die optimiert übersetzt werden können, direkt erkennt und entsprechend behandelt. Ein Beispiel ist die Regel (5), die im Sonderfall der Addition einer Konstanten, im Bereich zwischen 1 und 8, den Spezialbefehl ADDQ statt eines normalen ADD verwendet. Offen ist allerdings noch die Frage, wie der Codegenerator wissen soll, daß eine Verwendung der ebenfalls in diesem Punkt anwendbaren Regel (4) schlechter ist. Um eine solche Entscheidung zu ermöglichen, werden die einzelnen Regeln meist noch mit einem Kosten weil versehen. Der Codegenerator versucht nun, den Code derart zu erzeugen, daß die Summe der Kosten aller für einen Strukturbaum angewendeten Regeln minimal wird. Gerade bei der Behandlung von Spezialfällen können die Musterbäume durchaus größer sein, als dies in unseren Beispielregeln der Fall ist. Damit können dann auch spezielle Adressierungsarten des Prozessors ausgenutzt werden, die mehrere Knoten des Strukturbaums in einem Befehl berechnen. Die Registerverteilung und die Be Stimmung der Berechnungsreihenfolge kann bei der Codeerzeugung durch Mustererkennung ohne weiteres durch eine vorangehende Attributierung des Strukturbaums festgelegt werden, wie wir sie vorher besprochen haben.
Allgemein
Wie anfangs angekündigt, haben wir uns bei der Codeerzeugung auf arithmetische Ausdrücke konzentriert und andere Konstrukte einer Programmiersprache, wie Schleifen, Prozeduraufrufe und ähnliches, vernachlässigt. Dies ist wegen des begrenzten hier zur Verfügung stehenden Platzes geschehen und auch nicht so tragisch, da die wichtigsten Probleme und deren Lösung vorgestellt wurden. Gerade Schleifen erfordern eine Reihe von Speziallösungen und können normalerweise nicht ohne größeren Aufwand nennenswert optimiert werden. Die Art und Weise von Prozeduraufrufen ist recht stark von der implementierten Programmiersprache abhängig und kann wohl am besten durch die Benutzung von Registern zur Parameterübergabe und das Weglassen unbenutzter Eigenschaften des Aufrufmechanismus’ optimiert werden. Am wichtigsten ist im Ganzen wohl eine ausdrucksübergreifende Allokation von Registern, auf die hier aber nicht weitereingegangen werden soll.
Codierungsarbeit
Bisher haben wir uns nur mit Erzeugung von symbolischem Assemblercode beschäftigt. Um ein Programm ausführen zu können, muß es aber in echten Maschinencode umgewandelt, also noch assembliert werden. Dazu kann man einen externen Assembler verwenden, der eine Datei mit dem erzeugten symbolischen Assemblercode übergeben bekommt. Diese Methode wird des öfteren von Compilern verwendet, die unter dem Betriebssystem UNIX lauten. Durch das Verfahren wird die Portierbarkeit ei nes Compilers erhöht, da eine komplett maschinenabhängige Phase verschwindet, und außerdem spart der Compiler-Bauer auch etwas Arbeit. Erkauft werden diese Vorteile durch eine Erhöhung der Übersetzungszeit, da verstärkt relativ langsamer I/O durchgeführt werden muß und der Assembler die textuelle Repräsentation der Assembler-Datei erst wieder in eine interne Darstellung um-wandeln muß. Diese Nachteile kann man durch eine Integrierung des Assemblers in den Compiler vermeiden. Außerdem kann ein interner Assembler jede Assembler-Anweisung sofort nach ihrer Erzeugung in Maschinencode übersetzen, so daß das Programm nie komplett in Form von symbolischen Assembler-Anweisungen vorliegt. Nachdem wir nach der naiven Codegenerierung noch eine Art der Codeerzeugung kennengelernt haben, die weitaus besseren Code erzeugt, wollen wir uns jetzt noch kurz die Möglichkeiten der Codeoptimierung ansehen.
Noch besser...
Bei der Codeoptimierung geht es nicht darum, das Programm möglichst geschickt von einer Form in eine andere zu transformieren, sondern es wird schon erzeugter Code verbessert. Dies ist meist nicht der endgültige Maschinencode, sondern etwa ein Zwischencode, wie er in der letzten Folge vorgestellt wurde. Eine Möglichkeit solcher Optimierungen ist die schon erwähnte Peephole-Optimierung. Diese kann den Code zwar nur lokal verbessern, ist dafür aber recht einfach zu implementieren. Eine sehr viel mächtigere, allerdings auch aufwendigere Methode zur Optimierung von Programmen stellt die Datenflußanalyse dar. Im folgenden wollen wir uns kurz die Vorgehensweise der Datenflußanalyse ansehen und dann die Optimierungen, die sie erlaubt, besprechen. Die Datenflußanalyse operiert in der Regel auf einem Zwischencode, der dem 3-Adreß-Code aus der letzten Folge ähnlich ist. Wichtig ist außerdem, daß Variablen nicht symbolisch dargestellt werden. Stattdessen sind es Referenzen auf je eine Datenstruktur, die für jede der unterschiedlichen Variablen einmal vorkommt.
Eine solche Referenz erlaubt es, für diese Variable berechnete Information zu speichern. Der Zwischencode wird außerdem nicht linear im Speicher abgelegt, sondern in sogenannte Grundblöcke (basic blocks) aufgeteilt. Jeder Grundblock besteht aus einer Sequenz von Zwischencodeanweisungen, die genau einen Eingang und einen Ausgang besitzt. Der Grundblock kann also nur mit der ersten seiner Anweisungen betreten und in der letzten verlassen werden. Zwischendrin gibt es weder Einsprung- noch Aussprungpunkte. Die Grundblöcke werden ihrerseits zu einem Graphen verbunden, in dem jede Kante (Pfeil) einen möglichen Übergang von einem zu einem anderen Grundblock anzeigt. Innerhalb der Grundblöcke interessiert dann hauptsächlich, welche Variablen beschrieben und welche ausgelesen werden. Durch eine geschickte Kombination dieser Information aller Grundblöcke können jetzt zum Beispiel alle Zugriffe auf den Wert einer Variablen, der an einer bestimmten Stelle in die Variable geschrieben wurde, berechnet werden und damit auch, ab wo eine bestimmte Variable nicht mehr benutzt wird. Erschwert werden solche Berechnungen durch die Benutzung von Arrays und Zeigern, die den Optimierer zwingen, alle Information zu verwerfen, die durch solch einen Zugriff eventuell falsch wird.
Durch diese Berechnungen kann der Optimierer die folgenden Verbesserungen am Code durchführen. Die „Eliminierung gemeinsamer Teilausdrücke“ (common subexpression elimination) erkennt mehrfach auftretende gleichartige Berechnungen und sorgt dafür, daß das einmal berechnete Ergebnis mehrfach benutzt wird, ohne es mehrmals zu berechnen. Die „copy propagation“ behandelt Zuweisungen der Art ‘x := y‘ Solange x nicht weiter verändert wird, kann y statt x verwendet werden, was der als nächstes folgenden Optimierung eventuell die Eliminierung der Zuweisung erlaubt.
Da solche Kopieranweisungen in compilergeneriertem Code gerne Vorkommen, ist die Optimierung nicht so unsinnig, wie sie auf den ersten Blick scheinen mag. Eine weitere Optimierung ist die „Eliminierung toten Codes“ (dead-code elimination); sie entfernt, wie ihr Name schon vermuten läßt, Code, dessen Berechnungen nie benutzt werden. Zwei weitere Optimierungen sind im Zusammenhang mit Schleifen möglich. Dies ist einmal die „Codeverschiebung“ (code motion), bei der es darum geht, Berechnungen, die bei den einzelnen Schleifen durchlaufen unverändert bleiben, aus der Schleife herauszuziehen, und zweitens die „Eliminierung von Induktionsvariablen“ (induction variable elimination) zusammen mit „reduction in strength“. Bei diesen beiden geht es darum. Laufvariablen, die in einer Schleife gleichartig verändert werden, zu eliminieren oder wenigstens ihre Berechnung zu vereinfachen. Letzteres ist zum Beispiel möglich, sobald die Laufvariable i einer Schleife zu einer Berechnung wie ‘j := 2 * i‘ verwendet und bei jedem Schleifendurchlauf um eins erhöht wird. Statt in jedem Schleifendurchlauf die recht teure Multiplikation durchzuführen, kann j zu Beginn der Schleife mit dem zweifachen Wert des Startwertes von i initialisiert und anschließend mit ’j := j + 2’ erhöht werden.
Program ::= 'VAR' VarList ';' StatList 'PRINT' Ident.
VarList ::= Ident
| Ident ',' VarList.
StatList ::= Stat ';'
| Stat ';' StatList.
Stat ::= Assignment
| Conditional
| Loop.
Assignment ::= Ident ':=' Expr.
Conditional ::= 'IF Expr 'THEN' StatList ELSE’ StatList 'END'
Loop ::= 'WHILE' Expr 'DO' StatList 'END'
Expr ::= SimpleExpr RelOp SimpleExpr
| SimpleExpr.
SimpleExpr ::= SimpleExpr AddOp Product
| Product.
Product ::= Product MulOp Primitive
| Primitive.
Primitive ::= Integer
| Ident
| '(' Expr ')'.
RelOp ::= '=' | '#' | '<' | '>' | '=<' | '>='.
AddOp ::= '+' | '-'.
MulOp ::= '*' | '/'.
Listing 5: BNF einer kleinen Arithmetiksprache
Generierte Generatoren
Generatoren zur automatischen Erzeugung von Codegeneratoren können mit der Methode der Codeerzeugung per Mustererkennung recht gut erstellt werden, da diese Methode völlig unabhängig von der Zielmaschine funktioniert. Außerdem können spezielle Fähigkeiten der Zielmaschine recht einfach durch Muster, die die geeigneten Fälle abdecken, ausgenutzt werden. Ein Generator, der nach diesem Prinzip gebaut ist, ist BEG ([2]), was für „back end generator“ steht. Eine Eingabedatei für dieses Werkzeug beschreibt die Codegenerierung mit Hilfe von Regeln, die im wesentlichen aus einem Muster, einem Kostenwert und einem Programmstück bestehen. Das Programmstück wird ausgeführt, sobald die zugehörige Regel angewendet wird, und erzeugt den entsprechenden Code. Außerdem können durch zusätzliche Angaben auch noch Attribute während der Codegenerierung berechnet werden. Diese können zum Beispiel zur Bestimmung von Adressierungsarten und zur Berechnung konstanter Teilausdrücke Verwendung finden. Zusätzlich zu den Regeln muß in der Eingabedatei noch eine Beschreibung der Syntax des Strukturbaums stehen. Aus diesen Eingaben erzeugt BEG einen kompletten Codegenerator in Modula-2 oder C, der wahlweise noch mit einem der beiden in BEG eingebauten Algorithmen zur Registerallokation versehen wird. Der so erstellte Codegenerator erzeugt für jeden Strukturbaum garantiert immer den nach den angegebenen Kostenwerten optimalen Code, d.h. den Code, der die minimalen Kosten verursacht.
Hardware
Soviel zum Thema Codegenerierung. Handfeste Informationen zum Thema Compiler-Bau gibt es in den beiden schon mehrfach zitierten Büchern [1] und [3]. Dabei ist [1], das den Spitznamen Drachenbuch“ trägt, mehr an der Implementierung von Compilern orientiert. Man findet dort zu nahezu jedem Problem, das beim Bau eines Compilers auftritt, Implementierungstechniken zusammen mit teilweise recht raffinierten Tricks. Da das Buch auch gut geschrieben ist, ist es für jeden, der sich für Compiler-Bau interessiert, zu empfehlen. Das zweite Buch, das auch als „das silberne Wunder“ bekannt ist, ist eigentlich nur für Leute geeignet, die auch etwas an dem theoretischen Hintergrund interessiert sind und die eine formale Beschreibung nicht schreckt. Statt auf viele Implementierungsdetails, wird hier mehr Wert auf große Zusammenhänge und übergeordnete Prinzipien gelegt als im Drachenbuch. Wer nach der Lektüre dieser fünf Folgen zum Thema Compiler-Bau Lust bekommen hat, selbst einen Compiler zu schreiben, oder wer einfach mal ein wenig rumexperimentieren will, der kann die kleine Beispielsprache, deren Grammatik in Listing 5 abgebildet ist, mal des Spaßes halber implementieren. Ein Programm dieser Sprache besteht aus einer Variablendeklaration, einer Reihe von Anweisungen und dem Befehl, den Wert einer Variablen auszugeben. Als einzigen Datentyp gibt es ganze Zahlen (Integer). Bezeichner (Ident) der Sprache bestehen aus einer beliebigen Folge von Buchstaben. Ansonsten sollte die Sprache selbsterklärend sein. Das folgende Programm berechnet zum Beispiel die Fakultät der Zahl 5:
VAR fac, n;
n := 5;
ac := 1;
WHILE n > 0 DO
fac := fac * n;
n := n - 1 ;
END;
PRINT fac
Beim Bau eines Parsers für die Sprache muß man zuerst die Linksrekursionen entfernen, wie in Folge 3 beschrieben. Die daraus resultierende Grammatik läßt sich mit Hilfe des rekursiven Abstiegs einfach implementieren. Die semantische Analyse besteht im wesentlichen daraus zu überprüfen, daß nur deklarierte Bezeichner verwendet werden, und daß der Ausdruck in Verzweigungen und Schleifen als obersten Operator einen Vergleich enthält.
Allerdings kann alternativ auch die C-Regel benutzt werden, nach der alle Zahlen außer der Null für TRUE stehen. Bei der Codeerzeugung sollte man sich mit einem einfachen Kellerautomaten zufriedengeben und symbolischen Assemblercode in eine Datei schreiben, die dann von einem separaten Assembler in Maschinencode übersetzt wird.
Das war’s!
Die Compiler-Bau-Serie ist nun an ihrem Ende angelangt. Wenn es gelungen ist die grundlegenden Probleme des Compiler-Baus anschaulich darzustellen und ein Gefühl für die wichtigsten Problemlösungen zu vermitteln, so hat die Serie mit Sicherheit ihr Ziel erreicht. Natürlich wurde vieles nur angerissen, doch schließlich ist der Compiler-Bau ein sehr umfangreiches und komplexes Gebiet, das noch nicht einmal durch einen Wälzer wie das Drachenbuch hundertprozentig abgedeckt wird. Fragen, Kritik und Anregungen an den Autor sind jederzeit willkommen und sollten am besten an die untenstehende Adresse gesandt werden.
Manuel Chakravarty Wilhelm-Leuschner-Str. 2 7500 Karlsruhe-Oberreut
Literatur
[1] Aho/Sethi/Ullman: „Compilers: Principles, Techniques and Tools“, Addison-Wesley
[2] Emmelmann: „BEG - a Back End Generator“, User Manual (GMD Karlsruhe)
[3] Waite/Goos: „Compiler Construction“, Springer
Manuel Chakravarty