Ein LLVM nach JavaScript Compiler
Emscripten selbst ist in JavaScript entwickelt worden, da dies einige bequeme Vorteile mit sich bringt. Der Compiler kann beispielsweise numerische Ausdrücke vereinfachen, indem er sie mittels eval() direkt auswertet. Konstante Strukturen des LLVM Maschinencodes kann der Compiler intern als JavaScript-Objekte darstellen und sie mit JSON.stringify() auf simple Weise in eine Zeichenkette umwandeln, um sie einfach in dem zu erzeugenden JavaScript-Quelltext verwenden zu können.
Den Kompilierungsvorgang von Emscripten kann man in drei Hauptphasen aufteilen:
Die grundlegende Arbeitsweise von Emscripten wird am einfachsten mit einem kleinen Bespiel deutlich. Das folgende C-Programm berechnet mit einer einfachen Schleife die Summe der Zahlen von 1 bis 100 und gibt das Ergebnis aus.
#include <stdio.h>
int main ()
{
int sum = 0;
for (int i = 1; i <= 100; ++i)
sum += i;
printf("1+2+...+100=%d\n", sum);
return 0;
}
Der im ersten Schritt vom LLVM Frontend (hier clang) erzeugte LLVM Zwischencode sieht in diesem Fall so aus:
@.str = private unnamed_addr constant [16 x i8] c"1+2+...+100=%d\0A\00", align 1
define i32 @main() nounwind {
%1 = alloca i32, align 4
%sum = alloca i32, align 4
%i = alloca i32, align 4
store i32 0, i32* %1
store i32 0, i32* %sum, align 4
store i32 1, i32* %i, align 4
br label %2
; <label>:2 ; preds = %9, %0
%3 = load i32* %i, align 4
%4 = icmp sle i32 %3, 100
br i1 %4, label %5, label %12
; <label>:5 ; preds = %2
%6 = load i32* %i, align 4
%7 = load i32* %sum, align 4
%8 = add nsw i32 %7, %6
store i32 %8, i32* %sum, align 4
br label %9
; <label>:9 ; preds = %5
%10 = load i32* %i, align 4
%11 = add nsw i32 %10, 1
store i32 %11, i32* %i, align 4
br label %2
; <label>:12 ; preds = %2
%13 = load i32* %sum, align 4
%14 = call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([16 x i8]* @.str, i32 0, i32 0), i32 %13)
ret i32 0
}
(Für eine ausführliche Erläuterung der einzelnen Operationen siehe die LLVM Sprachreferenz)
Statt der Schleife selbst, finden sich hier nun mehrere Codeblöcke wieder, welche die einzelnen Teile der Schleife darstellen.
Der Code nach <label>:2 prüft die Bedingung der Schleife und springt je nach Ergebnis zu <label>:5 oder <label>:12.
<label>:5 stellt den Rumpf der Schleife dar. Hier wird die aktuelle Zahl zu der bisherigen Summe addiert.
Darauf folgt bei <label>:9 die Inkrementierung des Schleifenzählers und der Rücksprung zu <label>:2 um die Bedingung erneut zu prüfen.
Bei <label>:12 wird letztendlich die Funktion printf aufgerufen.
(Hätte man den LLVM Optimierungen an dieser Stelle freien Lauf gelassen, würde man hier nur einen printf-Aufruf mit dem eingesetzten Ergebnis der Summenberechnung wiederfinden.)
Emscriptens erster Ansatz ist es nun, zuerst jede Zeile der LLVM IR so weit wie möglich 1-zu-1 in "normalem" JavaScript umzusetzen. Das bedeutet, die add-Operationen werden zu einfachen JavaScript Additionen, ein Funktionsaufruf wird auch zu einem JavaScript Funktionsaufruf, und so weiter.
Lässt man sich diesen unoptimierten Zwischenstand ausgeben, erhält man folgenden JavaScript-Code:
function _main() {
var label = 0;
var __stackBase__ = STACKTOP; assert((STACKTOP|0) < (STACK_MAX|0));
label = 1;
while(1) switch(label) {
case 1:
var $1;
var $sum;
var $i;
$1=0;
$sum=0;
$i=1;
label = 2; break;
case 2:
var $3=$i;
var $4=(($3)|(0)) <= 100;
if ($4) { label = 3; break; } else { label = 5; break; }
case 3:
var $6=$i;
var $7=$sum;
var $8=((($7)+($6))|0);
$sum=$8;
label = 4; break;
case 4:
var $10=$i;
var $11=((($10)+(1))|0);
$i=$11;
label = 2; break;
case 5:
var $13=$sum;
var $14=_printf(((8)|0), (tempInt=STACKTOP,STACKTOP = (STACKTOP + 8)|0,assert((STACKTOP|0) < (STACK_MAX|0)),HEAP32[((tempInt)>>2)]=$13,tempInt));
STACKTOP = __stackBase__;
return 0;
default: assert(0, "bad label: " + label);
}
}
Tatsächlich enthält das erzeugte JavaScript noch eine ganze Menge Code mehr, der die main-Funktion umgibt. Dieser Teil enthält beispielsweise die Definition der _printf-Funktion, wird hier aber nicht mit dargestellt. Das oft anzutreffende |0-Anhängsel stellt eine asm.js Typannotation dar und kann hier erst mal ignoriert werden.
Dieser Code ähnelt der LLVM Darstellung sehr stark: Die Codeblöcke finden sich ganz analog in dem switch-Konstrukt wieder. Angesprungen werden die Blöcke über die Mehrfachverzweigung mit der label-Variable innerhalb einer Endlosschleife.
Statt eine konkrete Sprunganweisung zu nutzen, wird label dabei ein neuer Wert zugewiesen. Die icmp-Vergleichsoperation, auf die vorher ein bedingter br-Sprungbefehl folgte, wurde mit einer if-Verzweigung umgesetzt.
Des Weiteren erfolgen die Speicherzugriffe mit natürlichen Variablen. In früheren Versionen wurden dafür zu diesem Zeitpunkt stattdessen Referenzen auf ein JavaScript Array genutzt, welches den Heap darstellt.
Der Codefluss entspricht jedoch noch in keiner Weise einem natürlichen Programmfluss, den ein Programmierer normalerweise erzeugen würde. Die Ausführung ist daher vergleichsweise langsam, auch weil noch unnötig viele Variablen genutzt werden.
Erlaubt man Emscripten weitere Optimierungen, wird unter anderem der Relooper-Algorithmus genutzt:
function _main() {
var r1, r2, r3;
r1 = STACKTOP;
r2 = 0;
r3 = 1;
while (1) {
if (!((r3 | 0) <= 100)) {
break;
}
r2 = r2 + r3 | 0;
r3 = r3 + 1 | 0;
}
_printf(8, (tempInt = STACKTOP, STACKTOP = STACKTOP + 8 | 0, HEAP32[tempInt >> 2] = r2, tempInt));
STACKTOP = r1;
return 0;
}
Hier wurde nun der ursprüngliche Programmfluss wiederhergestellt. Die vorherigen Blöcke sind Größtenteils wieder einzelne Zeilen, wie die Addition der Summe und die Inkrementierung des Schleifenzählers. Auch werden nun wieder viel weniger Variablen benötigt.
Die Auswertung der Schleifenbedingung ist in den Rumpf der Schleife gewandert. Was die Performanz betrifft, stellt dies aber kein Problem dar und wird so belassen.
Emscripten kann auch den Google Closure Compiler anwenden, der einige weitere Optimierungen am JavaScript-Code ausführen kann.
Maßgeblich für die Wiederherstellung des Programmflusses verantwortlich ist der Relooper-Algorithmus, der eines der Kernelemente von Emscripten darstellt.
Der Heap-Speicher, den ein Programm verwendet, um Daten abzulegen und auf den es mit Zeigern zugreifen kann, stellt Emscripten mit einem typisierten JavaScript Feld dar. So weit möglich, werden die meisten Variablen, die ein Programm verwendet, mit natürlichen JavaScript Variablen abgebildet und liegen nicht in diesem Array.
Im Standard Modus wird der Speicher also durch einen einzigen typed array-Puffer dargestellt. Unterschiedliche Sichten auf diesen Puffer ermöglichen den Zugriff auf unterschiedliche Datentypen in ein und demselben Speicherbereich. Dadurch müssen Programme sich nicht an Load-Store-Consistency halten. (Load-Store-Consistency bedeutet, wenn an eine Stelle im Speicher ein Wert eines bestimmten Typs geschrieben wird, darf von dort auch nur ein Wert desselben Typs wieder gelesen werden.)
Dies hat den Vorteil, dass der durch das typisierte Feld dargestellte Speicher genauso aufgebaut werden kann, wie es C und C++ Programme normalerweise auf dem Heap tun.
Ein Nachteil ist aber, dass Aufgrund der Funktionsweise von typisierten Feldern, beim Zugriff auf 32-Bit Werte mit Zeiger-Verschiebungen gearbeitet werden muss. Daher finden sich im erzeugten JavaScript viele <<2 oder >>2 beim Zugriff auf das Heap-Array wieder.
Emscripten kann den Speicher auch noch auf andere Weisen darstellen, aber diese ist momentan die Vorgabe. Möglicherweise ändert sich die Implementation auch in Zukunft wieder, um effizientere Zugriffe zu ermöglichen.
Da das von Emscripten erzeugte JavaScript typischerweise in einem Browser laufen soll, ergeben sich daraus einige Implikationen für die Laufzeitumgebung. Ein direkter Zugriff auf das lokale Dateisystem ist beispielsweise nicht möglich.
Arbeitet das zu übersetzende Programm mit Dateien, kann auf diese durch ein virtuelles Dateisystem zugegriffen werden, welches Emscripten bereitstellt. Über dieses werden auch /dev/stdin, /dev/stdout und /dev/stderr als virtuelle Geräte bereitgestellt. Zu verwendende Dateien können bei der Erstellung des Programms mit Emscripten in diesem virtuellen Dateisystem abgelegt werden, so dass zur Laufzeit auf diese zugegriffen werden kann.
Emscripten bringt auch eine eigene in JavaScript geschriebene Implementation der C-Standardbibliothek mit, womit weitere Zugriffe auf die Laufzeitumgebung umgesetzt werden können. Außerdem stehen noch einige weitere Implementationen unterschiedlicher Bibliotheken wie SDL und GLUT teilweise zur Verfügung, die Zugriffe auf ein HTML5 canvas Element erlauben und Grafik mithilfe von WebGL darstellen können.