Ein LLVM nach JavaScript Compiler
Der Relooper ist dafür zuständig, Hochsprachenkonstrukte wiederherzustellen. Es ist eines der komplexesten Module von Emscripten, seine grundlegende Funktionsweise soll hier anhand des vorherigen Beispiels erläutert werden. Ausführlicher wird der Algorithmus in dem Paper von Alon Zakai unter Kapitel 3.2 erläutert.
Die Eingabe, mit der Emscripten arbeitet, ist im Prinzip eine große, ungeordnete Menge aus LLVM Codestücken, die mit Marken versehen sind. Der Algorithmus verarbeitet diese Menge und erstellt daraus eine strukturierte Menge von Emscripten Codeblöcken. So ein Emscripten Block besteht jeweils aus einer Menge von LLVM Codestücken mit etwas logischer Struktur. Im Folgenden beziehen sich die Begriffe Codestück auf ein LLVM Codestück und Block auf einen Emscripten Block.
Es gibt drei Arten von Emscripten Blöcken:
Einen simple block bestehend aus:
Der loop block repräsentiert eine Schleife, bestehend aus zwei weiteren Blöcken:
Der multiple Block stellt eine (Mehrfach-)Verzweigung dar (also z.B. ein 'if' oder 'switch'), bestehend aus:
Alle Blöcke beinhalten also einen next-Block, der den darauffolgenden Block angibt. Existiert kein darauffolgender Block mehr, wird hier auf null verwiesen. Der loop und der multiple Block beinhalten zusätzlich einen, bzw. mehrere weitere Emscripten Blöcke. Nur der simple Block beinhaltet ein LLVM Codestück. So kann das gesamte Programm als eine verschachtelte Struktur von Emscripten Blöcken abgebildet werden. Auf oberster Ebene steht ein Block, der sich auf immer weitere Blöcke aufteilt und diese letztlich auf Codestücke.
Die Eingabemenge von Codestücken, die der Algorithmus verarbeitet, beinhaltet noch eine Menge von Codestücken, die Einstiegspunkte darstellen. Diese Menge der Einstiegspunkte ist eine Untermenge der ersten Menge. Ein Block beinhaltet also letztendlich mehrere Codestücke und einige dieser Codestücke können Einstiegspunkte sein.
Der Relooper durchläuft bei der Ausführung die folgenden Schritte:
Erhalte eine Menge aus Codestücken, von denen eine Untermenge Einstiegspunkte sind.
Aus diesen Codestücken soll ein Emscripten Block erzeugt werden, der insgesamt alle diese Codestücke enthält.
Berechne für jedes Codestück, welche anderen Codestücke es erreichen kann.
Dadurch erhält man für jedes Codestück eine Menge weiterer Codestücke, die es erreicht, wenn man einem der möglichen Ausführungspfade folgt.
Gibt es einen einzigen Einstiegspunkt, zu dem keines der anderen Codestück zurückkehren kann, dann erstelle einen simple Block.
Kann zu allen Einstiegspunkten zurückgekehrt werden, dann erstelle einen loop Block.
Diese vier Schritte reichen für das einfache, bereits gezeigte Programm aus, um die Hochsprachenkonstrukte wiederherzustellen. Der vollständige Algorithmus enthält noch zwei weitere Schritte:
Gibt es mehr als einen Einstiegspunkt, versuche einen multiple Block zu erstellen.
Konnte kein multiple Block erstellt werden, dann erstelle einen loop Block, wie in Punkt 4 beschrieben.
(Siehe das oben erwähnte Paper, für eine ausführliche Beschreibung dieser letzten beiden Schritte.)
Hat der Algorithmus erfolgreich einen Block erstellt, wiederholt sich die Prozedur für die neuen Blöcke, die der erstellte Block beinhaltet.
Der LLVM Maschinencode des bereits gezeigten Programms, welches die Summe der Zahlen von 1 bis 100 berechnet, hat die folgende Struktur:
┌───────────────┐
V │
[Einstieg] ──> [2] ──> [5] ──> [9]
│
V
[12]
Nun wollen wir dieses Programm, wieder mit Hochsprachenkonstrukten darstellen. Wie das Ergebnis letztendlich aussieht, haben wir ja bereits gesehen:
EINSTIEG
while (true) do
2
if (Bedingung) break
5
9
12
Unsere gegebene Menge an Codestücken sieht also so aus: { Einstieg, 2, 5, 9, 12 }. Die fetten Codestücke stellen dabei die Einstiegspunkte dar. Der nächste Schritt ist nun, für jedes Codestück die weiteren erreichbaren Codestücke zu bestimmen:
Einstieg: { 2, 5, 9, 12 }
2: { 5, 9, 2, 12 }
5: { 9, 2, 5, 12 }
9: { 2, 5, 9, 12 }
12: { }
Bis auf die leere letzte Menge, sind alle Mengen identisch.
Unsere Menge an gegebenen Codestücken enthält genau einen Einstiegspunkt, zu dem nicht wieder zurückgekehrt werden kann. Erkennbar daran, dass keine der oberen Nachfolgemengen unser Codestück 'Einstieg' enthält. Daher können wir einen simple Block erstellen, wie im dritten Schritt des Algorithmus' beschrieben:
simple
internes Codestück: 'Einstieg'
next: { 2, 5, 9, 12 }
Jetzt wiederholt sich die Prozedur für die Menge der Codestücke im next Block. Die Nachfolgemengen sind wieder identisch zu den oben bereits berechneten.
Prüfen wir also wieder, ob wir für unsere nun gegebene Menge an Codestücken wieder einen simple Block erstellen können: Wir haben wieder einen einzigen Einstiegspunkt (Codestück 2), so weit so gut. Schauen wir in der Menge, der für den Einstiegspunkt erreichbaren Codestücke nach, erkennen wir, dass wir diesmal zum Einstiegspunkt zurückkehren können. Für einen simple Block darf dies nicht der Fall sein.
Prüfen wir nun, ob wir, wie im vierten Schritt beschrieben, einen loop Block erstellen können: Da wir zu allen unseren Einstiegspunkten zurückkehren können, ist dies in der Tat möglich. Der loop Block setzt sich wie folgt zusammen:
loop
innerer Block: { 2, 5, 9 }
next: { 12 }
Das Codestück 9 muss dabei so verändert werden, dass der Sprungbefehl zu Codestück 2 durch ein 'continue' ersetzt wird. Dadurch ändern sich die erreichbaren Codestücke wie folgt:
2: { 5, 9 }
5: { 9 }
9: { }
Durch das eingesetzte 'continue' endet das Programm trotzdem nicht nach Codestück 9, sondern die Schleife wird erneut ausgeführt. Hätten wir diese Änderung hier nicht vorgenommen, würden wir endlos weitere loop Blöcke mit einem inneren Block { 2, 5, 9 } erzeugen.
Der Algorithmus wiederholt sich nun für die beiden Bestandteile unseres loop Blockes. Dabei entstehen nur noch weitere simple Blöcke, bis sich die folgende Hierarchie ergibt:
simple
▏Einstieg
▏loop
▏simple
▏ ▏2
▏ ▏simple
▏ ▏5
▏ ▏simple
▏ ▏9
▏ ▏null
▏simple
▏12
▏null
Wir haben nun erfolgreich die ursprüngliche Schleife wiederhergestellt!
Es ist übrigens auch sichergestellt, dass der Algorithmus immer terminiert, da das verbleibende Problem sich mit jedem weiteren Schritt immer etwas verringert.