Marcus Denker 
  
Prof. Dr Gerhard Goos Betreuender 
  
Erweiterung eines statischen Übersetzers zu einem Laufzeitübersetzungssystem

Keywords: 

Das resultierende System soll die Funktionalität des existierenden Systems beibehalten, und die Integration weiterer Analysen ermöglichen, wie weiterer statischer Analysen als auch Laufzeitoptimierungen.

Motivation

Laufzeitübersetzer erlauben Optimierungen unter Verwendung von Informationen, die erst zur Laufzeit des Programms verfügbar sind.

Der Übersetzer muss das als Quelltext vorliegende Programm in einem ersten Schritt übersetzten. Nun werden beim Programmlauf Informationen (z. B. über die an einem Methodenaufruf vorkommenden Klassen) gesammelt.

Unter Ausnutzung dieser Informationen kann nun der Code besser optimiert werden.

Dieser Prozess kann viele Male wiederholt werden: Auch der nun generierte Code kann in einem weiteren Schritt optimiert werden. Also reicht eine Neuübersetzung aus dem Quellcode nicht aus, stattdessen muss der Übersetzer die Ergebnisse des vorherigen Laufes in einer Datenbasis speichern und in den nächsten Übersetzerlauf einbeziehen.

Zielkriterien

Aus der Aufgabenstellung ergeben sich folgende Zielkriterien für diese Arbeit:

1. Vollständiger Entwicklungszyklus unterstützt 2. Der Übersetzer erlaubt weitreichende Optimierungen 3. Integration in ein vorhandenes System

Vollständiger Entwicklungszyklus unterstützt

Der Übersetzer soll später vollständig transparent in das System Integriert werden. Das System soll sowohl neuen (als Quellcode eingegebenen) Code übersetzen als auch vorhandenen Code unter Ausnutzung von zusätzlichen Informationen weiter optimieren können.

Der Übersetzer erlaubt Optimierungen

Grund für die wiederholte Übersetzung ist die Möglichkeit, weitere Optimierungen durchzuführen. Der Übersetzer soll daher eine Zwischendarstellung bereitstellen, auf der diese Optimierungen durchgeführt werden können.

Integration in ein vorhandenes System

Der Entwurf soll für ein bestehenden System realisiert werden. Für den Test des Übersetzers ist dabei entscheidend, dass die Ausgabe des Übersetzers auch im System verwendbar ist: Die übersetzten Methoden sollen zu Testzwecken ausführbar sein.

Überblick über die Arbeit

In Kapitel folgt der Entwurf eines Übersetzers, der die in Abschnitt 1.3 definierten Anforderungen erfüllt. 

Funktionsweise klassischer Übersetzer

Die Aufgabe der Übersetzung wird zur Reduktion der Komplexität in mehrerer Phasen aufgeteilt. In den meisten Übersetzern findet sich folgende Aufteilung (siehe [START_REF] Goos | Compiler Construction[END_REF] und [START_REF] Aho | Compilers: Priciples, Techniques and Tools[END_REF]). 

Syntaktische Analyse

Bytecode-orientierte Sprachen

In Bytecode-orientierten objektorientieren Sprachen (z. B. Java oder Smalltalk) ist der Übersetzer einfacher aufgebaut: Die Zielsprache, der Bytecode, ist semantisch der Quellsprache sehr ähnlich. Es werden nur sehr einfache Optimierungen durchgeführt.

Der Ablauf ist folgender:

1. Syntaktische Analyse 2. Semantische Analyse

Erzeugung eines stackorientierten Bytecode

In diesem Fall ist also keine Zwischensprache nötig: Man generiert den Bytecode direkt aus dem unoptimierten, attributierten AST.

Bytecode als Zwischensprache

Wenn man diesen Aufbau mit dem eines klassischen Übersetzers vergleicht, so sieht man, dass die Schritte exakt den Schritten 1-3 eines klassischen Übersetzers entsprechen. Man kann den Bytecode also nicht nur als Zielsprache verstehen (ausgeführt von einer virtuellen Maschine), sondern auch als Zwischensprache.

Die Sichtweise des Bytecode als Zwischensprache ist auch naheliegend, da modernen virtuelle Maschinen den Bytecode in Maschinencode übersetzen, also die Schritte 4-6 implementieren.

Wahl einer Datenbasis: Bytecode

Unser System soll eine wiederholte Übersetzung erlauben. Dabei sollen die Ergebnisse der Übersetzungen in einer Datenbasis gespeichert und für die nächste Übersetzung wiederverwendet werden.

Wenn wir uns den Aufbau eines Bytecode-orientierten Systems ansehen, so findet sich eine geeignete Datenbasis im Bytecode selbst: Er wird zwischen den Übersetzungsläufen gespeichert, da das System ihn für die Ausführung benötigt.

Wir werden im Folgenden daher einen Bytecode-nach-Bytecode Übersetzer entwerfen.

Zwischensprache SSA

Der Bytecode dient als Datenbasis zwischen den Übersetzerläufen. Als Zwischensprache für die Optimierungsphase des Übersetzers ist er aber nicht geeignet. Als Zwischensprache wollen wir eine SSA-Darstellung implementieren. 

Aufbau des Übersetzers

Optimierungen auf SSA

Die SSA-Darstellung bietet viele Vorteile für die Optimierungsphase. Die Algorithmen sind einfacher und können alle die SSA-Darstellung als Zwischenprache verwenden, was bei anderen Repräsentationen nicht der Fall ist.

SSA Abbau

Die SSA-Darstellung enthält Phi-Funktionen. Für diese kann direkt kein Bytecode erzeugt werden. Daher muss der Übersetzer die SSA-Darstellung in eine nicht-SSA Form transformieren.

Wir werden das verwendete Verfahren für den Abbau der SSA-Darstellung im Kapitel 3 genauer betrachten.

Codegenerierung

Die Aufgabe dieser Phase der Übersetzung ist die Transformation des nun nicht mehr in SSA-Darstellung vorliegenden Baumes in Bytecode, also in eine Reihung von 8bit Zahlen.

Diese Phase lässt sich in zwei Teile gliedern: Erzeugen einer maschinenahen Repäsentation und anschließende Übersetzung dieses symbolischen Codes in Bytecode.

Zusammenfassung

In diesem Kapitel haben wir, nach einem Überblick über die Funktionsweise klassischer Übersetzer, einen Entwurf vorgestellt. Dieser soll die Anforderungen aus dem ersten Kapitel erfüllen.

Wir haben die einzelnen Phasen des entworfenen Übersetzers beschrieben.

Bevor wir den Entwurf realisieren, wird das nächste Kapitel den SSA Abbau genauer darstellen. 

Klassische Verfahren

Das einfachste Verfahren nach [CFR + 91] fügt Zuweisungen in die Vorgängerblöcke ein. Ein einfaches Beispiel zeigt Bild 3.1.

Man sieht, dass die Phi-Funktion entfernt und stattdessen die Zuweisung a3 := a1 und a3 := a2 in die entsprechenden Vorgängerblöcke eingefügt wurden.

Die eingefügten Kopien können durch Kopienweiterschaltung zu großen Teilen enfernt werden. Dies ist in den meisten aktuellen Implementierungen Teil der Registerzuteilung.

Probleme

In [START_REF] Briggs | Practical Improvements to the Construction and Destruction of Static Single Assignment Form[END_REF] wird gezeigt, dass dieses Verfahren nicht funktioniert, wenn Code umgeordnet wird. In Abschnitt 3.9 werden wir solche zwei Beispiele 

Das Phi-Kongruenz Verfahren

Ein solches Verfahren findet sich in [START_REF] Vugranam | Translating Out of Static Single Assignment Form[END_REF]. Es baut auch in den Problematischen Fällen die SSA Form korrekt ab und fügt weit weniger Kopien ein als das Standardverfahren.

Grundidee

Die Grundidee des Verfahrens beruht auf folgernder Beobachtung:

Selektiert eine Phi-Funktion zwischen identischen Variablen, so kann man die Phi-Funktion durch eine einfache Zuweisung ersetzen:

a1 := P HI(a1, a1)

kann ersetzt werden durch

a1 = a1
Ist nun, wie in diesem Fall, auch das Ziel der Phi-Funktion gleich den Eingabevariablen, so kann man den Ausdruck entfernen.

Die Idee des Verfahrens ist nun, das Programm so zu transformieren, dass die Eingabevariablen aller Phi-Funktionen identisch sind. Die Phi-Funktionen können dann einfach entfernt werden.

Einige Definitionen

Für die Darstellung des Verfahrens benötigen wir einige Definitionen.

Variablen einer Phi-Funktion

Wir verstehen unter der Menge der Variablen einer Phi-Funktion die Vereinigung zwischen den Quellvariablen der Phi-Funktion und dem Ziel, also der Variable, an die zugewiesen wird.

Beispiel:

a 3 = P HI(a 1 , a 2 ) (3.1)
a 3 ist Zielvariable, a 1 und a 2 sind Quellvariablen. Alle drei Variablen sind Teil der Phi-Funktion.

Phi Kongruenzen

Definition 1 (Phi-Verbundenheit) Gegeben sei eine Variable x aus einer Phi Funktion. Wir definieren:

PhiVerbunden(x) = {y|x und y sind Teil einer Phi-Funktion oder es existiert ein z mit: Sowohl x und z als auch y und z sind Teil einer Phi-Funktion}

Nach dieser Definition sind also zum einen alle Variablen einer Phi-Funktion verbunden, zum anderen sind alle Variablen von Phi-Funktionen dann verbunden, wenn diese Phi-Funktionen mindestens eine gleiche Variable enthalten.

Ein Beispiel:

a 3 = P HI(a 1 , a 2 ) a 5 = P HI(a 3 , a 4 )
Hier sind über die gemeinsame Variable a 3 auch a 1 und a 4 Verbunden.

Definition 2 (Phi Kongruenzklasse) Unter der Phi-Kongruenzklasse der Variable x verstehen wir die reflexive und transitive Hülle von PhiVerbunden(x).

Eine Phi-Kongruenzklasse definiert also die Menge der Variablen, die über Phi-Funktionen verbunden sind. 

Gesamtüberblick

Mit den im letzten Abschnitt erläuterten Definitionen können wir nun das Verfahren beschreiben. Es wird in 3 Schritten ablaufen:

1. Transformation TSSA nach CSSA.

2. Ersetzen aller Variablen einer Phi-Kongruenzklasse durch einen Repräsentanten.

3. Löschen aller Phi-Funktionen.

Transformation in CSSA

Wir werden zwei Verfahren die Transformation von TSSA nach CSSA vorstellen. Das einfache Verfahren ist dabei dem klassischen dahingehend ähnlich, dass pessimistisch Kopien eingefügt werden.

Das Verfahren II ist eine Verbesserung des ersten Verfahrens, es fügt weit weniger Kopien ein, ist aber aufwendiger. Wir werden in Kapitel 6 beide Verfahren in Hinsicht auf die Anzahl der eingefügten Kopien und der Laufzeit untersuchen.

Verfahren I

Das einfachste Verfahren ist dem Standardverfahren ähnlich: Wir fügen Kopien für alle Quellen in die entsprechenden Vorgängerblöcke ein. Zusätzlich wird eine Kopie für die Quellvariable hinter die Phi-Funktionen eingefügt.

Dadurch wird erreicht, dass das Programm die Phi-Kongruenzeigenschaft hat und damit in TSSA Form vorliegt.

Bild 3.2 zeigt ein Beispiel.

Dieses Verfahren erzeugt TSSA Form, hat aber den Nachteil, dass es sehr viele Kopien einfügt, die nicht nötig sind.

Verfahren II

Die Grundidee des verbesserten Verfahrens besteht darin, nur diejenigen Kopien einzufügen, die nötig sind, um die CSSA Form zu erreichen. 

Beschreibung Algorithmus Verfahren II

Die Grundidee des Verfahrens besteht darin, die Phi-Kongruenzklassen schrittweise aufzubauen und immer dann Kopien einzufügen, wenn ohne die Kopie eine Interferenz entstehen würde.

Wir iterieren dazu über alle Phi-Funktionen aller Grundblöcke.

Kongruenzklassen aufbauen

Zu Beginn initialisieren wir alle Klassen so, das jede Variable Element in seiner eigenen Kongruenzklasse ist.

Dann gehen wir alle Phi-Funktionen durch. Für jedes Paar Variablen aus einer Phi-Funktion testen wir, ob die Kongruenzklassen der beiden Variablen überlappen.

Auf Interferenz testen

Wenn die Variablen x i und x j interferieren, so müssen Kopien eingefügt werden.

Seien L j und L i die den Variablen x i und x j zugeordneten Vorgängerblöcke.

Sind beide Variablen Phi-Quellvariablen, so müssen wir 4 Fälle unterscheiden.

Dazu definieren wir

M 1 = phiKongruenzKlasse(x i ) ∪ LiveOut(L j ) M 2 = phiKongruenzKlasse(x j ) ∪ LiveOut(L i ).
1. M 1 ist nicht leer, M 2 ist leer: Eine Kopie für x i wird vorgemerkt.

2. M 1 ist leer, M 2 ist nicht leer: Eine Kopie für x j wird vorgemerkt.

3. M 1 ist nicht leer, M 2 ist nicht leer: Kopien für x i und x j werden vorgemerkt.

4. M 1 ist leer, M 2 ist leer: Eine Kopie für x i oder x j . Wir merken uns beide Kanditaten, die Entscheidung welche Kopie eingefügt wird, treffen wir nachdem alle Interferenzen der Phi-Funktion bekannt sind.

Falls eine der Variablen Ziel einer Phi-Funktion ist, so müssen wir die gleichen vier Fälle unterscheiden, wobei sich die Definition für M 1 und M 2 ändert. O.B.d.A. sei x i die Zielvariable:

M 1 = phiKongruenzKlasse(x i ) ∪ LiveOut(B) M 2 = phiKongruenzKlasse(x j ) ∪ LiveIn(B).
Dabei ist B der Grundblock, in den die Phi-Funktion vorkommt.

Verzögerte Kopien

Im vierten Fall müssen wir eine Kopie für eine von zwei möglichen Variablen einfügen. Hier kann eine geschickte Wahl der Variable bedeuten, dass weniger Kopien eingefügt werden müssen.

Wir haben diese Fälle in die Tabelle T eingetragen: Bei Interferenz von x i und x j fügen wir x i dem Eintrag T (x j ) hinzu, x j entspechend T (x i ). Die Tabelle enhält also für jede Variable eine Mengen von interferierenden Variablen.

Nun können wir diese Tabelle nach der Größe dieser Mengen sortieren und dann der Reihe nach auflösen, indem wir für die Variablen Kopien einfügen.

Mit Hilfe dieser Heuristik stellt das Verfahren sicher, dass zuerst für diejenigen Variablen Kopien eingefügt werden, die mit mehreren Variablen Interferenzen bilden. Mit einer Kopie können evtl. gleichzeitig mehrere dieser Interferenzen aufgelöst werden.

Kopien einfügen

Nun fügen wir die als nötig erkannten Kopien in das Programm ein. Dabei passen wir auch die Interferenz-und Lebendigkeitsinformationen an, da diese für die nächste Iteration benötigt werden.

Kongruenzklassen anpassen

Im letzten Schritt müssen wir die Kongruenzklassen anpassen. Das Verfahren hat sichergestellt, dass alle Variablen der Phi-Funktion nicht interferieren. Das bedeutet, dass wir einfach die Kongruenzklassen aller Variablen der Phi-Funktion vereinigen können.

Damit ist eine Phi-Funktion abgearbeitet, das Verfahren wird nun für alle weiteren Phi-Funktionen aller Grundblöcke wiederholt.

Phi-Funktionen löschen

Wenn alle Phi-Funktionen abgearbeitet sind, haben wir Kopien so eingefügt, dass das Programm die Phi-Kongruenz-Eigenschaft hat. Wir können also die Variablen der einzelnen Kongruenzklassen durch einen Repräsentanten ersetzen und die Phi-Funktionen löschen.

Beispiele

Der Algorithmus wird nun anhand der Beispiele Lost Copy und Swap erläutert. Wenn wir das klassische Verfahren aus Kapitel 3.2.1 anwenden, so geht die Kopie x = y verloren.

Lost Copy

Wir wollen nun das Phi-Kongruenz-Verfahren anwenden. Dazu inititalisieren wir die Phi-Kongruenzklassen. Alle Konguenzklassen enhalten nur die Variable selbst.

Nun gehen wir alle Phi-Funktionen durch. In unserem Beispiel gibt es nur eine Phi-Funktion, daher wird der folgende Schritt nur für diese durchgeführt.

Interferierende Paare feststellen

In diesem Fall interferiert nur ein Paar: x 2 und x 3 .

Interferenzen auflösen

Diese Intereferenz soll nun aufgelöst werden. Da x 2 Ziel der Phi-Funktion ist, bilden wir folgenden Mengen:

M 1 = phiKongruenzKlasse(x 2 ) ∪ LiveOut(L2) M 2 = phiKongruenzKlasse(x 3 ) ∪ LiveIn(L2).
Die Phi-Kongruenzklassen enhalten jeweils die Variable selber. Ausserdem ist x 2 ist in LiveOut(L2) und x 3 nicht in LiveIn(L2).

Also: M1 nicht leer, M2 leer. Wir müssen also eine Kopie für x 2 einfügen (Siehe Abschnitt 3.7.2).

Bild 3.3 (c) zeigt das Ergebnis. Es wurde eine Kopie eingefügt. Der erste Schritt ist die Initialisierung der Phi-Kongruenzklassen: Jede Variable ist Teil Element der eigenen Kongruenzklasse.

Swap

Dann berechnen wir die Lebendigkeit der Variablen am Begin und Ende der Grundblöcke: 

LiveIn(L2) = {x 2 , y 2 } LlveOut(L2) = {x 2 , y 2 } x = ...

Erste Phi-Funktion

x 1 und y 2 interferieren, y 2 ist LiveIn(L2), x 2 ist liveOut(L2). Daher müssen wir Kopien für beide Variablen einfügen.

Als nächstes werden LiveIn und LiveOut angepasst:

LiveIn(L2) = {x 2 , y 2 } LlveOut(L2) = {x 2 , y 2 }
Nun verschmelzen wir die Phi-Kongruenzklassen aller Variablen der Phi-Funktion.

Zweite Phi-Funktion

x 1 und y 2 interferieren, y 2 ist nicht LiveIn(L2), x 2 ist nicht liveOut(L2). Daher müssen wir Kopien für eine der beiden Variablen einfügen. Das Bild 3.4 (d) zeigt das Ergebnis: Es wurden drei Kopien eingefügt.

Zusammenfassung

Der Übersetzer muss die SSA-Darstellung abbauen. In diesem Kapitel haben wir die klassischen Verfahren und das Phi-Kongruenz Verfahren vorgestellt.

Bevor wir dieses Verfahren für unseren Übersetzer implementieren, gibt das nächste Kapitel einen Überblick über die Systeme und Rahmenwerke, die wir für die Implementierung verwenden werden. 

Verwendete Werkzeuge

Folgende existierende Subsysteme haben wir für die Implementierung verwendet:

• Das Squeak-System in der Version 3.7alpha (virtuelle Maschine, Entwicklungsumgebung)

• ClosureCompiler (eine Smalltalk-nach-Bytecode Übersetzer. Autor: Anthony Hannan)

• AOStA (SSA Rahmenwerk. Autor: Elliot Miranda) 

Eigenschaften

Die von AOStA erstellt SSA-Darstellung beschränkt sich auf die temporären Variablen der Methoden. Instanzvariablen werden nicht in SSA-Darstellung transformiert.

Der SSA Aufbau führt keine Wertnummerierung durch, identische Teilausdrücke werden nicht optimiert.

Definions-Nutzungs Informationen

AOStA stellt Definions-Nutzungs Informationen bereit. Jede Benutzung einer Variable hat also eine Referenz auf die Definion dieser Variable, jede Definition kennt alle ihre Benutzungen.

Typinformationen

Das AOStA-System erlaubt zu jeder Variable Typinformationen zu notieren. Smalltalk ist eine dynamisch getypte Sprache. Daher kann beim Aufbau der SSA-Darstellung nur für statisch feststellbare Fälle der Typ (also die Klasse) der Variablen festgestellt werden.

Transformationen

Für die Optimierungsphase stellen die Knotenklassen der AOStA SSA-Darstellung einfache Transformationen zur Verfügung. Man kann Knoten löschen oder durch einen anderen Knoten ersetzen. Dabei sorgt AOStA dafür, dass die Defininions-Nutzungs Verkettung korrekt bleibt.

Besucher

Mit Hilfe des Musters Besucher (siehe [START_REF] Gamma | Design Patterns[END_REF]) kann man die SSA-Darstellung durchlaufen. AOStA stellt dazu abstrakte Klassen bereit, die verschiedene Besuchsmuster definieren:

• AOBreadthFirstDominatorTreeVisitor In Reihenfolge Dominator-Baum Breitensuche.

• AODepthFirstDominatorTreeVisitor

In Reihenfolge Dominator-Baum Tiefensuche

• AONodeUnorderedVisitor ungeordnet

Optimierungen in AOStA

Mit den Besucherklassen und den Transformationen lassen sich nun Optimierungen implementieren. AOStA stellt zwei solche Optimierungen als Bespiele bereit.

Konstantenweiterschaltung

Die Konstantenweiterschaltung (constant propagation) ersetzt Zugriffe auf eine Variable, der ein konstanter Wert zugewiesen wird, im gesamten Programm durch diese Konstante.

Realisiert ist die Konstantenweiterschaltung in AOStA als Unterklasse von AOBreadthFirstDominatorTreeVisitor. Der Baum wird also in Ausführungsreihenfolge durchsucht. Zuweisungen von Konstanten werden in einer Hash-Tabelle gespeichert. Beim Besuch einer Variable wird in dieser Tabelle nachgeschlagen und die eingetragenen Variablen dann durch den konstanten Wert ersetzt.

Entfernung toten Codes

Diese Optimierung entfernt Definitionen von Variablen, die im Programm nicht genutzt werden. Durch die im Baum enthaltene Definition-Benutzungs Information ist dies leicht festzustellen:

Ist die Menge der Nutzungen leer, so wird die definierte Variable niemals genutzt. Falls die Definition keine Seiteneffekte hat, ist nicht nötig und kann entfernt werden.

Der symbolische Assemblierer IRBuilder

Der IRBuilder stellt die Funktionalität eines symbolischen Assemblierers für Squeak Bytecodes bereit. 

Beispiel

Aufbau SSA-Darstellung

Wie wir im letzten Kapitel gesehen haben, können wir einige bestehende Systeme wiederverwenden. Für den ersten Teil des Übersetzers verwenden wir das AOStA Rahmenwerk. Dieses analysiert den Bytecode und baut eine SSA-Darstellung auf. Verfahren I fügt drei Kopien ein, das zweite Verfahren keine. Wir wiederholen die Ausführung 10000 mal (siehe Tabelle 6.4).

Portierung AOStA

Wir sehen, dass die eingefügten Kopien einen großen Einfluss auf die Geschwindigkeit des Codes haben.

Zusammenfassung

In diesem Kapitel haben wir die Implementierung des Übersetzers untersucht. Für die dazu notwendigen Tests haben wir zum einen eine Sammlung von Beispielen implementiert, zum anderen den Übersetzer in das Squeak-System integriert.

Wichtig war für uns insbesondere der Abbau der SSA-Darstellung. Das verwendete Verfahren wurde auf die Anzahl der eingefügten Kopien untersucht. Der Übersetzer wurde in Squeak integriert. Wie Kapitel 4 zeigt, kann man Methoden übersetzen und den generierten Bytecode im System installieren. Dies erfüllt Kriterium 3.

Der entwickelte Übersetzer erfüllt also alle in Abschnitt 1.3 definierten Ziele.

Ausblick

Im Folgenden werden wir einige Bereiche möglicher weiterer Entwicklungen darstellen.

Verbesserungen AOStA

Das für die Realisierung des Übersetzers verwendete AOStA Rahmenwerk hat einige Schwachstellen gezeigt. Besonders die Kodierung der Phi-Funktionen sollte verbessert werden.

Eingabevariablen Phi-Funktionen

In AOStA werden die Eingabevariablen der Phi-Funktionen als Menge representiert, die Zuordnung zu den Grundblöcken geht verloren. Diese Information ist aber für die Berechnung der Lebendigkeit und SSA Abbau nötig.

Für diese Arbeit haben wir daher die Knotenklasse der Phi-Funktionen um eine Tabelle erweitert, die jeder Phi-Eingabevariable den entsprechenden Grundblock zuordnet. Diese Tabelle kann man sehr einfach während des SSA Aufbaus füllen.

Eine zukünfige AOStA Version sollte diese Tabelle mit der vorhandenen Kodierung der Phi-Eingabevariablen vereinheitlichen.

Kodierung Phi-Zuweisung

AOStA kodiert Phi-Funktionen als eine Selektorfunktion, die einer Variable über eine normale Zuweisungsoperation zugewiesen wird.

Um diese Phi-Zuweisungen von normalen Zuweisungen zu unterscheiden, bietet AOStA den Test #isPhiFunctionAssigmentNode.

Diese Kodierung hat einige Nachteile: Meist ist man nicht an der Phi-Funktion im Sinne von AOStA, sondern der gesamten Phi-Zuweisung in-

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Klassische Verfahren . . . . . . . . . . . . . . . . . . . . . . . 19 3.2.1 Probleme . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Das Phi-Kongruenz Verfahren . . . . . . . . . . . . . . . . . . 20 3.3.1 Grundidee . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.4 Einige Definitionen . . . . . . . . . . . . . . . . . . . . . . . . 21 3.4.1 Variablen einer Phi-Funktion . . . . . . . . . . . . . . 21 3.4.2 Phi Kongruenzen . . . . . . . . . . . . . . . . . . . . . 21 3.4.3 CSSA und TSSA . . . . . . . . . . . . . . . . . . . . . 22 3.4.4 Lebendigkeit und Interferenz . . . . . . . . . . . . . . . 23 3.5 Gesamtüberblick . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.6 Transformation in CSSA . . . . . . . . . . . . . . . . . . . . . 24 3.6.1 Verfahren I . . . . . . . . . . . . . . . . . . . . . . . . 24 3.6.2 Verfahren II . . . . . . . . . . . . . . . . . . . . . . . . 24 3.7 Beschreibung Algorithmus Verfahren II . . . . . . . . . . . . . 25 3.7.1 Kongruenzklassen aufbauen . . . . . . . . . . . . . . . 25 3.7.2 Auf Interferenz testen . . . . . . . . . . . . . . . . . . 26 3.7.3 Verzögerte Kopien . . . . . . . . . . . . . . . . . . . . 26 3.7.4 Kopien einfügen . . . . . . . . . . . . . . . . . . . . . . 27 3.7.5 Kongruenzklassen anpassen . . . . . . . . . . . . . . . 27 3.8 Phi-Funktionen löschen . . . . . . . . . . . . . . . . . . . . . . 27 3.9 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.9.1 Lost Copy . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.9.2 Swap . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.10 Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . 31 Überblick existierende Infrastruktur 33 4.1 Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.2 Verwendete Werkzeuge . . . . . . . . . . . . . . . . . . . . . . 33 Aufgabe der Diplomarbeit ist die Entwicklung eines Laufzeitübersetzers aus einem existierenden, statischem Übersetzer. Dazu ist basierend auf der Zwischensprache des existierenden Systems eine Datenbasis zu entwickeln, die für die Laufzeitübersetzung geeignet ist. An diese Datenbasis ist ein Front-End und ein Back-End anzuschliessen (oder existierende Module sind anzupassen). Das System soll den vollständigen Entwicklungszyklus unterstützen, vom Aufbau und Modifikation der Datenbasis durch das Einlesen von Quelltext und die Verwendung von bereits gesammelten Laufzeitdaten über die Durchführung von Optimierungen bis zur Generierung von Zielcode.

  Dieses Kapitel beschreibt den SSA Abbau. Dazu stellen wir kurz die klassischen Verfahren vor. Dabei gehen wir speziell auf die Probleme dieser Verfahren ein.Thema des zweiten Teils ist dann das Phi-Kongruenzverfahren zum Abbau der SSA-Darstellung nach[START_REF] Vugranam | Translating Out of Static Single Assignment Form[END_REF].

  Abbildung 3.1: Entfernen von Phi-Funktionen

  Abbildung 3.2: Einfache Transformation nach CSSA

Bild 3 .

 3 3 zeigt das Lost Copy Problem vor (a) und nach SSA Aufbau und Kopienweiterschaltung (b).

  Als zweites Beispiel betrachten wir das Swap Program. Das Bild 3.4 zeigt den Code vor SSA Aufbau (a) in CSSA-Darstellung (b) und nach Kopienweiterschaltung (c).

  Abbildung 3.3: Lost Copy

•

  Erzeugen von Bytecode (ClosureCompiler) • SSA-Darstellung aufbauen mit AOStA • Optimierung • Phi-Funktionen entfernen • Zählen der eingefügten Kopien • Codegenerierung (optional) • Installation des Codes im System (optional) Dabei ist die Codegenerierung optional. Dies ist nötig, da der Codegenerator noch nicht für das gesamte System Code erzeugen kann. Mit dem AORecompiler können wir nun das System übersetzen. Im nächsten Abschnitt werden wir einige Messungen vorstellen.

6. 4

 4 SSA AbbauWir wollen nun die beiden Verfahren zum SSA Abbau in drei Bereichen genauer untersuchen:• Anzahl eingefügter Kopien • Performanz Abbau • Performanz Code6.4.1 Eingefügte Kopien Als Testdaten verwenden wir zum einen die Beispielklasse, die im Zuge der Entwicklung entstand (90 Methoden), Zum anderen einen Teil des Squeak-Systems: Alle Klassen, die mit den Buchstaben A-I anfangen. (719 Klassen mit 13235 Methoden). Die Ergebnisse zeigt Tabelle 6.1. Ohne Optimierungen liegt CSSA-Form vor: Das Verfahren II fügt keine Kopien ein. Auch nach Optimierung (Kopienweiterschaltung) ist die Anzahl der eingefügten Kopien gering. Tabelle 6.4: Laufzeit Code Verfahren Zeit Verfahren I 3,4 sec Verfahren II 2,6 sec Optimierungphase nach dem SSA Abbau hinzugerechnet werden muss. Diese ist nötig, da die Kopien, wenn sie nicht minimiert werden, die Performanz verschlechtern. Dies wollen wir im nächsten Abschnitt messen.

  6.4.3 Performanz CodeWir führen Code aus, jeweils mit SSA Abbau nach beiden Verfahren. Dabei verwenden wir folgendes Beispiel: exampleWhileTrue | a | a := 1000. [a > 0] whileTrue: [ a := a -1]. ^a.

  Das Kapitel beschreibt einen Teil des Entwurfs (den SSA Abbau) genauer.Die Umsetzung des Entwurfs ist dann Thema des Kapitels 5.Die Ergebnisse und einige vergleichende Messungen stellt das Kapitel 6 vor.Das Kapitel analysiert dann die erzielten Ergebnisse anhand der Anforderungen und gibt einen Ausblick auf zukünftige Entwicklungen.

	Kapitel 2
	Entwurf
	2.1 Überblick

Im folgenden Kapitel werden wir einen Übersetzer entwerfen, der den Kriterien aus Kapitel 1.3 entspricht. Dazu betrachten wir die Funktionsweise klassischer Übersetzer und leiten daraus einen Ansatz für den Entwurf her. Dieser wird dann im zweiten Teil des Kapitels ausführlich erläutert.

  Der Entwurf aus Kapitel 2 wurde innerhalb des Squeak-Systems realisiert. Für eine diesem System sehr ähnliche Plattform, VisualWorks, steht mit dem AOStA Rahmenwerk eine Implementierung eines Teiles des Übersetzers (Analyse des Bytecodes und Aufbau SSA) zur Verfügung. Der Übersetzer baut auf diesem System auf. Wir wollen nun nach einer kurzen Einführung in Squeak das AOStA Rahmenwerk betrachten. Abschliessend folgt ein Überblick über den Assemblierer IRBuilder.

	Kapitel 4
	Überblick existierende
	Infrastruktur
	4.1 Überblick

  Das Squeak-System entstand als direkte Weiterentwicklung von Smalltalk 80 im Zuge von Alan Kays Squeak Projekt. Das System wird z. B. in [IKM + 97] oder [GR01] ausführlich beschrieben. Hier soll ein kurzer Überblick ausreichen. Squeak verwendet eine virtuelle Maschine, die eine Kellerarchitektur bereitstellt. Neben Befehlen zur Manipulation dieses Kellers (push und pop) gibt es Befehle zum Zugriff auf die lokalen Variablen der Methode und die Variablen der Instanzen.

	• IRBuilder		
		(ein symbolischer Assemblierer für Squeak Bytecode. Autor: Anthony
	Bytecode	Hannan)	AST	SSA
	4.3 Squeak AOStA	SSA-Aufbau	Opt
		Abbildung 4.1: AOStA	
	Im Zuge des AOStA Projektes sind Teile eines Übersetzers (Bytecodeanaly-
	se und SSA Aufbau) entstanden, die wir für die Implementierung unseres
	Entwurfs nutzen wollen.		
	4.4.2 Aufbau AOStA		
	Die verwendetet Sprache ist ein Dialekt von Smalltalk ([GR83]), es wurden
	aber auch Übersetzer für weitere Sprachen implementiert. Es gibt z. B. Über-
	setzer für die Sprachen E-Lang ([MS03]) und Logo ([Pap80]). Außerdem wur-
	de im Rahmen des OpenCroquet Projekts ([SKRR03][SKRR04]) ein Über-
	setzer für Javascript implementiert.	
	4.4 Das AOStA Rahmenwerk	
	Die Implementierung des Übersetzers verwendet Teile eines SSA Rahmen-
	werks, das für VisualWorks (eine kommerzielle Smalltalk implementierung)
	entwickelt wird. Dieses System wird hier kurz vorgestellt.
	4.4.1 Das AOStA Projekt	
	Ziel des AOStA Projekts ist die Realisierung der von Self ([Hö94]) bekann-
	ten dynamischen, adaptiven Optimierung in Smalltalk. AOStA ist ein Open
	Source Projekt unter der Leitung von Eliot Miranda (Firma Cincom). Einen
	Überblick findet man in [Bon03], ausführlichere Informationen bietet [Mir02].

Für die Ablaufsteuerung gibt es zum einen den Befehl send für den Aufruf von Methoden, zum anderen Sprünge für Schleifen und Bedingungen. Die virtuelle Maschine implementiert in der aktuellen Version einen Interpreter, erste experimentelle Laufzeitübersetzer existieren. Das AOStA-Rahmenwerk besteht aus drei Teilen. Am Begin steht die Analyse des Bytecodes und der Aufbau eines AST. Dieser wird dann im zweiten Schritt in SSA-Darstellung transformiert (siehe 4.1). Der dritte Teil des AOStA Systems ist ein Rahmenwerk für Optimierungen, als Beispiel werden einige einfache Optimierungen bereitgestellt. SSA Abbau und Codegenerierung sind nicht implementiert.

  Das folgende Beispiel erzeugt eine Methode, die einfach die Zahl 1 zurückgibt.Der Aufruf der Methode #compiledMethod erzeugt nicht einzig eine Reihung mit den Bytcodes, sondern ein vollständiges Objekt der Klasse CompiledMethod, das man direkt im System verwenden kann.Hier haben wir das generierte CompiledMethod Objekt als Methode #test in der Klasse Float installiert. Diese neue Methode kann nun aufgerufen werden, sowohl bei existierenden als auch neuen Instanzen der Klasse Float.

	Der generierte Bytecode: pushLiteral: 10;
	returnTop;
	5 <76> pushConstant: 1 jumpAheadTo: #continue;
	6 <7C> returnTop jumpAheadTarget: #true;
	pushLiteral: 20;
	returnTop; jumpAheadTarget: #continue; Kapitel 5
	ir.
	Man kann die Methode ausführen: Daraus erzeugt IRBuilder den Bytecode Umsetzung
	aCompiledMethod valueWithReceiver: nil arguments: #() 13 <76> pushConstant: 1
	14 <77> pushConstant: 2
	15 <B2> send: <
	16 <A8 02> jumpTrue: 20
	18 <20> pushConstant: 10 19 <7C> returnTop 5.1 Überblick
	20 <21> pushConstant: 20
	21 <7C> returnTop Wir wollen nun den Entwurf aus Kapitel 2 implementieren. Der Entwurf sieht
	folgenden Aufbau vor:
	Der IRBuilder hat also aus den symbolisch definierten Zielen nun Sprünge • Analyse des Bytecodes und Aufbau SSA 4.5.2 Symbolische Sprungziele generiert, die feste Positionen im Bytecode als Ziel haben. • Optimierungen auf SSA
	Sehr wichtig für den Einsatz des IRBuilder im Codegenerator ist die
	Möglichkeit Sprungziele symbolisch zu definieren. Hier ein einfaches Beispiel • SSA Abbau 4.6 Zusammenfassung eines if-else. ir := IRBuilder new • Code Generierung
	rargs: #(self); pushLiteral: 1; returnTop; ir. Dieses Kapitel hat die existierenden Systeme und Rahmenwerke vorgestellt, 1 < 2 ifTrue: [^10] ifFalse: [^20] erzeugt wird: vorgestellt und an Squeak angepasst. Wir wollen Bytecode erzeugen, wie er durch den Übersetzer für diesen Code auf die die Realisierung des Übersetzers aufbauen wird. Nach einem kurzen Wir werden nun die Implementierung der einzelnen Teile des Übersetzers Überblick über das Squeak-System haben wir das SSA-Rahmenwerk AOStA beschreiben.
	Eine Einführung in den symbolische Assemblierer IRBuilder schliesst dieses
	Nach Erzeugen einer IRBuilder Instanz (IRBuilder new) werden nachein-ir := IRBuilder new Kapitel ab.
	ander die Methoden #rargs:, #pushLiteral: und #returnTop aufgerufen. rargs: #(self); Im nächsten Kapitel folgt nun die Umsetzung des Übersetzers basierend auf
	Der Aufruf von #ir schliesst die Befehle ab. Die so erzeugte, bytecodenahe pushLiteral: 1; die hier vorgestellten Systeme.
	Zwischensprache kann nun in Bytecode umgesetzt werden: pushLiteral: 2;
	send: #<;
	aCompiledMethod := ir compiledMethod. jumpAheadTo: #true if: true;

oder einer bestehende Klasse als Methode hinzufügen:

Float addSelector: #test withMethod: aCompiledMethod.

  AOStA ist für VisualWorks Smalltalk entwickelt worden. VisualWorks und Squeak basieren beide auf dem Xerox Smalltalk 80 System ([GR83]). VisualWorks Smalltalk verwendet eine virtuelle Maschine mit Laufzeitübersetzer. Aus diesem Grund wurden die Bytecodes um einen LoopHead Befehl erweitert. Jeder Rücksprung hat als Ziel einen solchen LoopHead Bytecode. Dies vereinfacht das Erkennen von Schleifen und erlaubt daher einen einfachere Analysephase des Laufzeitübersetzers. Auch AOStA setzt diesen LoopHead Befehl voraus. Daher muss der Squeak Compiler angepasst werden und den entsprechenden Code erzeugen. Der verwendete Bytecode ist unbelegt und wird von der virtuellen Maschine ignoriert. Der Codeerzeuger wird also erst weiter den Empfänger der Nachricht und dann die Argumente besuchen. Danch folgt ein Aufruf der IRBuilder Instanz: Ein Bytecode zur Aufruf der Methode wird erzeugt. Man sieht hier in Zeile 11 auch ein Beispiel für den loopHead Befehl. Die Sammlung von Testfällen enthält auch die Beispiele LostCopy und Swap aus Kapitel 3. Daneben ca. 90 weitere Methoden, die im Zuge der Entwicklung des Übersetzers entstanden.

	5.2.3 Bytecode für Schleifenerkennung • Der Bytecode des gesamten Squeak-Systems
	Die Beispiele sind dabei so gewählt, dass keine im Codegenerator fehlende
	Funktionalität benötigt wird. Hier kann also der gesamte Übersetzer, ein-
	schließlich Codegenerierung, getestet werden.
	Beide Systeme wurden aber seit 1983 getrennt weiterentwickelt und weisen 5.6 Ein Beispiel Für den Test des Übersetzer ohne Codegenerator, also Aufbau SSA, Opti-daher einige Unterschiede auf. mierung, SSA Abbau, kann der Code des gesamten Squeak-Systems (und
	Diese Unterschiede betreffen z. B. die Bibliotheken. Es sind einige Anpassun-Nun soll das Zusammenspiel der einzelnen Phasen des Übersetzers anhand damit auch der Code des Übersetzers) verwendet werden.
	gen am Code nötig, um AOStA unter Squeak übersetzen zu können. eines einfachen Beispiels gezeigt werden. Wir verwenden dazu eine einfache
	Der entscheidende Unterschied ist aber der verwendete Bytecode. while Schleife: 6.3.1 Sammlung von Testfällen
	Beispielhaft zeigen wir die Unterschiede in zwei Bereichen: Die Codierung
	von Closures und ein einfaches Beispiel für unterschiedliche Bytecodes. exampleWhileFalse
	| a | 5.3 Optimierungen auf SSA a := 0.
	[a > 10] whileFalse: [a := a + 1].
	^a.
	5.2.2 Closures
	Der Smalltalk-nach-Bytecode Übersetzer generiert für exampleWhileFalse
	Smalltalk Blockobjekte können sowohl lokale Variablen definieren, als auch optimierten Code: Es werden keine Blockobjekte generiert, sondern der Code
	Variablen der Methode oder eines umschließenden Blocks referenzieren. wird offen eingebaut und durch Sprünge kodiert:
	In Squeak werden alle diese Variablen als lokale Variablen der Methode reali-Test SSA Aufbau
	siert. Eine andere Möglichkeit ist, den Blockobjekten eigene lokale Variablen 9 <75> pushConstant: 0
	zuzuordnen und auf die Variablen der Umgebung korrekt zuzugreifen: Die 10 <68> popIntoTemp: 0 Dieser Test baut die SSA-Darstellung auf und tested dann die Definitions-
	Blockobjekte sind dann anonyme Funktionen höherer Ordnung, wie sie aus funktionalen Sprachen bekannt sind. Diese Closure-Semantik (siehe [Lan64]) 11 <7E> loopHead Benutzungs-Informationen und die Rückverkettung der enstandenen SSA-5.3.1 Kopienweiterschaltung 12 <10> pushTemp: 0 Darstellung.
	wurde in Visualworks implementiert. Die Kopienweiterschaltung ist eine solche Optimierung. Sie ist sehr ähnlich 13 <20> pushConstant: 10
	In der aktuellen Squeak Version ist aber eine Closure-Semantik nicht vorhan-zur Konstantenweiterschaltung. Hier ein einfaches Beispiel: 14 <B3> send: > testExampleSwap
	den. 15 <A8 06> jumpTrue: 23 self shouldnt: [
	BB5: [ 17 <10> pushTemp: 0 methodNode := parser parse: (AOStAExamples Es existiert eine experimenteller Smalltalk-nach-Bytecode Übersetzer für t2a := 1. 18 <76> pushConstant: 1 compiledMethodAt: #exampleSwap). Squeak, der Closure-Semantik unterstützt. Die nötigen Änderungen an der s3a := t2a. 19 <B0> send: + AOCheckDefUseChains check: methodNode. virtuellen Maschine sind schon Teil von Squeak 3.6. 20 <68> popIntoTemp: 0 AOCheckParentNodeConnection new visitNode: methodNode. ^s3a] Für diese Arbeit verwenden wir daher diesen experimentellen Übersetzer in 21 <A3 F4> jumpTo: 11 ] raise: Error.
	einer leicht angepassten Version, die es erlaubt, den Übersetzer parallel zum 23 <10> pushTemp: 0
	alten Übersetzer im Squeak-System zu betreiben. Die Zuweisung s3a := t2a kann gelöscht werden, wenn man alle Vorkommen 24 <7C> returnTop Test Codegenerierung
	Damit unterztützt Squeak Closures semantisch. Der verwendete Syntax, also von s3a durch t2a ersetzt:
	die Codierung z. B. der Variablen, ist aber verschieden. Wir müssen AOStA Die Klasse AOStACodeGenVisitorTest testet die Codegenerierung. Im Fol-
	entsprechend anpassen. BB5: [ genden sehen wir den Test für das Beispiel Swap:

Das AOStA Rahmenwerk stellt einige einfache Optimierungen bereit: Entfernung von totem Code (Dead Code Elimination) und Konstanten-Weiterschaltung (Constant Propagation). Diese beiden Optimierungen sind aber bzgl. des SSA Abbaus nicht interessant. Wie in Kapitel 3.4 erwähnt, sind die Phi-Kongruenzklassen nach SSA Aufbau überlappungsfrei. Es liegt also bereits CSSA Form vor. Im Folgenden soll eine einfache Optimierung implementiert werden, die die Lebensdauer von Variablen ändert und dadurch Interferenzen zwischen Variablen erzeugt. Mittels SUnit [Bec] lassen sich nun automatisch ablauffähige Testsammlungen erstellen. Die Testsammlungen enthalten insgesamt ca. 600 Tests. Die Testsammlungen decken alle Phasen des Übersetzers ab. Daneben werden auch weitere Klassen getestet, wie z.B. die Berechnung der Lebendigkeit.

Wir wollen zwei Testklassen genauer betrachten.

Code Gen

Abbildung 2.2: Der Übersetzer liest seine Ausgabe

Diesen Baum durchläuft dann der Codegenerierungs-Besucher und erzeugt Bytecode identisch zur Eingabe.

Zusammenfassung

Der Entwurf aus Kapitel 2 wurde implementiert. Als nächstes werden wir die Ergebnisse vorstellen.

Kapitel 6 Ergebnisse

Überblick

Nachdem wir den Entwurf aus Kapitel 2 implementiert haben, wollen wir nun die Ergebnisse darstellen.

Nach einem Überblick über den Stand der Implementierung werden einige vergleichende Messungen des SSA Abbaus vorgenommen.

Stand der Implementierung

Der Entwurf wurde wie in Kapitel 3 beschrieben implementiert.

Die Codegenerierungsphase ist noch nicht ganz vollständig: So fehlen einige Optimierungen wie beispielsweise Kodierung sehr einfacher Methoden im Kopf des Methodenobjekts (Quick Methods).

Außerdem sind primitive Methoden, also der Aufruf von Code, der als Teil der virtuellen Machine implementiert ist, noch nicht realisiert.

Tests und Evaluierung

Für den Test des Übersetzers wollen wir Squeak Bytecode übersetzen lassen. Dabei werden wir zwei Gruppen von Testdaten verwenden:

• Eine Sammlung von Beispielen