Wir stellen Lightbeam vor: Ein optimierender Streaming-Compiler für WebAssembly

Lightbeam ist ein neuer Streaming-Compiler für WebAssembly, der darauf ausgelegt ist, die bestmögliche Assemblierung zu erzielen und dabei noch genügend Leistung aufzubringen, um die Assemblierung schneller als die via Kabel zu empfangende WebAssembly zu erzeugen.

WebAssembly wurde für die Kompilierung im Streaming-Verfahren entwickelt, wobei bereits seit der ersten veröffentlichten Version eine Streaming-Implementierung vorhanden war - Firefox hat seit langem seinen eigenen optimierenden Streaming-Compiler und V8 hat LiftOff.

Lightbeam ist vom Konzept her ähnlich, hat aber einen anderen internen Mechanismus, der in Anbetracht der Einschränkungen zu überraschend hochwertigem Code führt. Ich werde in diesem Artikel erklären, wie er funktioniert.

Lightbeam

Lightbeam ist für die Verwendung als erster Compiler in Wasmtime und als Hauptcompiler für das Subsystem für Smart Contracts von Substrate vorgesehen.

In Bezug auf letzteres haben Sie vielleicht einige Fragen: Warum brauchen wir einen Compiler für unsere Smart Contracts? Was sind Smart Contracts überhaupt? Wollen wir wirklich einen Compiler in einen Client für die Blockchain einbauen? Antworten auf diese und weitere Fragen finden Sie in meinem Artikel über WebAssembly auf der Blockchain, aber das ist für die Zwecke dieses Artikels nicht besonders wichtig.

Wichtig ist, wie WebAssembly funktioniert und wie wir dessen Einschränkungen umgehen können, um hochwertigen Code in einem Streaming-Compiler zu erzeugen.

Streaming-Kompilation

Ich werde nicht zu sehr in die Tiefe gehen, da Lin Clark das Thema bereits viel gründlicher behandelt hat, als ich es kann, aber hier ist der springende Punkt. Wenn Sie schnelle Startzeiten für ein Programm haben wollen, haben Sie mehrere Möglichkeiten, wobei jede ihre eigenen Vor- und Nachteile hat:

- Das Programm als Maschinencode zur Verfügung stellen

• Vorteile: Sehr schnelle, berechenbare Leistung
• Nachteile: Erhebliche Sicherheitsmängel; keine Möglichkeit, Opcodes für bestimmte Mikroarchitekturen ohne komplexe Zusatzfunktionen und Laufzeitprüfungen zu verwenden; für jede Zielplattform müssen separate Programmversionen bereitgestellt werden

- Bytecode bereitstellen und einen Interpreter verwenden

• Vorteile: Einfach zu implementieren; einfach zu debuggen; einfach zusätzliche Funktionen hinzuzufügen; einfach die korrekte Ausführung zu gewährleisten; einfach eine geeignete API zu schreiben; standardmäßig 100% thread- und speichersicher; kann auf jede Plattform übertragen werden, auf der die Host-Sprache anwendbar ist
• Nachteile: Langsam (wirklich, wirklich langsam)

- Bytecode bereitstellen und einen JIT verwenden

• Vorteile: Sehr schneller Anwendungsbeginn und schnelle Ausführung; kann Funktionen im Hintergrund kompilieren (so dass nicht verwendete Funktionen nie kompiliert werden); kann die Mikroarchitektur des Hosts nutzen; kann unglaublich leistungsstarke Optimierungstechniken anwenden, die mit einem AOT-Compiler unmöglich sind
• Nachteile: Die mit Abstand komplexeste Option; standardmäßig keine Thread- oder Speichersicherheit; schneller Anwendungsbeginn im Durchschnitt, aber ohne extrem sorgfältige Implementierung kann die Startzeit im schlimmsten Fall sehr lange sein; muss für jede Zielarchitektur ein anderes Backend implementieren

- Bytecode bereitstellen und einen Streaming-Compiler verwenden

• Vorteile: Kann bei gutem Bytecode-Entwurf eine sehr gute Leistung erbringen; relativ einfach sicherzustellen, dass die Zeit für den Anwendungsbeginn selbst im schlimmsten Fall kurz ist; kann die Mikroarchitektur des Hosts optimal nutzen
• Nachteile: Muss für jede Zielarchitektur ein anderes Backend implementieren; standardmäßig keine Thread- oder Speichersicherheit; muss Bytecode unter Berücksichtigung der Beschränkungen der Streaming-Kompilierung entwerfen

Der wesentliche Grund, warum wir uns bei Parity für die Verwendung eines Streaming-Compilers entschieden haben, sind die im Zusammenhang mit der Blockchain notwendigen strikten Zeitvorgaben für die Kompilierung - derzeit verwenden wir unseren eigenen internen WebAssembly-Interpreter.

Jeder dieser Interpreter kann mit einem langsameren, aber leistungsfähigeren Compiler im Hintergrund arbeiten, da die schnellere Verarbeitungsmethode das Programm ausführt und die Ausführung auf die Ausgabe des leistungsfähigeren Compilers umschaltet, wenn diese fertig ist.

Grundlagen zu WebAssembly

Bevor ich also erklären kann, was Lightbeam im Detail macht, muss ich ein paar Dinge über WebAssembly erläutern. WebAssembly ist ein sonderbarer Zwischenbereich zwischen einer Hochsprache und einem eher traditionellen Bytecode. Es ist ein Bytecode, da es eine Maschine für Stapelspeicher ist, die durch eine Reihe von Opcodes dargestellt wird, anstatt ein textbasiertes Format zu haben. Außerdem weist es zahlreiche Eigenschaften einer Hochsprache auf, die in Bytecodes selten zu finden sind, wie z.B. hierarchisch angeordnete Blöcke unter Verwendung von block...end, bei denen es möglich ist, die Hierarchie zu durchbrechen. Des Weiteren existieren getrennte Blocktypen für Blöcke, an deren Ende man springen kann sowie für Blöcke, an deren Anfang man springen kann, und ein Konstrukt if..else..end anstelle der traditionelleren “test-and-jump”-Anweisung (es gibt zwar eine “test-and-jump”-Anweisung, man kann sie jedoch derzeit nicht einsetzen, um bedingte Anweisungen zu erzeugen). Darüber hinaus verfügt es über “locals”, ein Konzept, das den Variablen in den meisten Hochsprachen ähnelt. Diese “locals” verursachen allerdings mehr Probleme als sie es wert sind. Sie sind eher ein Überbleibsel aus der Geschichte von WebAssembly als eine nützliche Funktion.

Das heißt, obwohl WebAssembly so konzipiert ist, dass es sich mit einem Streaming-Compiler leicht kompilieren lässt, ist es in Wirklichkeit ziemlich aufwändig, aus WebAssembly direkt einen optimalen Code zu erzeugen. Das ist der Grund, warum Lightbeam das nicht so macht.

Es muss schnell gehen

Wie gelingt es Lightbeam also, einen so guten Code zu erzeugen? Nun, es gibt viele kleine Optimierungen, die dies ermöglichen, aber beginnen wir mit der Konvertierung in eine SSA-, CFG-Zwischendarstellung, wie es ein “normaler”, der kein Streaming-Compiler ist, durchführen würde. Vergleichbar ist dies mit LLVM IR oder Cranelift IR - eine einfachere Version des Eingabecodes, die es erlaubt, Optimierungen durchzuführen, ohne sich mit einer Vielzahl von Anwendungsfällen befassen zu müssen. Auf die genauen Unterschiede zu WebAssembly werde ich später noch eingehen. Der Unterschied zu LLVM IR besteht darin, dass die IR-Konvertierung von Lightbeam ein Streaming-Verfahren ist - wir können einen Stream von WebAssembly in einen Stream von IR konvertieren und das Backend kann einen Stream von IR in einen Stream von systemeigenem Code konvertieren. In der Praxis bedeutet dies, dass wir systemeigenen Code mit nur einem Opcode Lookahead erzeugen können.

Im Backend behalten wir den Überblick darüber, wo Werte gespeichert sind, so dass wir Elemente nur dann verschieben müssen, wenn es absolut notwendig ist. Das Ergebnis ist, dass Werte so weit wie möglich in Registern bleiben und seltener in den Speicher verschoben werden müssen - und wenn sie in den Speicher verschoben werden, dann in der Reihenfolge, in der sie am wenigsten gebraucht werden. Derzeit gibt es 4 Speicherplatzarten für Werte: Ein Wert kann im Speicher, in einem Register, in einer Konstanten oder als Bedingungscode gespeichert werden. Letzteres bedeutet, dass anders als bei vielen Streaming-Compilern, die einen Vergleich ziehen würden, eine Umwandlung des Vergleichsergebnisses einen Integer, einen Vergleich dieses Integers mit 0 und dann einen Sprung durchführen würden. Bei Lightbeam wird lediglich ein Vergleich und dann ein Sprung auf diesen Bedingungscode durchgeführt, genau wie bei einem Compiler ohne Streaming. Mit dieser Methode erhalten wir auch eine freie Konstantenfaltung, ohne auf Streaming verzichten zu müssen.

In unserem Fall vereinfachen wir die Konstrukte if..end, if..else..end, br_if, br_table, block..end und loop..end und reduzieren sie auf eine einzige, einheitliche Form. Im Gegensatz zu verschachtelten Blöcken in WebAssembly haben wir eine einfache Liste von Basisblöcken, die mit br, br_if oder br_table enden müssen. Anstatt viele Möglichkeiten zu haben, den Kontrollablauf zu ändern, gibt es nur noch 3¹. Zwar wird das Einfügen eines Blocks zu einer Nulloperation, aber if, else, loop und end müssen in diese Form umgewandelt werden. Dies ist in der Praxis zum Glück sehr einfach.

Die Tatsache, dass es für einen Block keine Möglichkeit gibt, einen Sprung auszuführen, ohne den Block zu beenden, ist sehr nützlich und vereinfacht die Handhabung deutlich. In WebAssembly ist dies jedoch möglich, was zu einigen Komplikationen führt. Betrachten Sie die folgende WebAssembly-Code:

(block (result i32)
  i32.const 1
  i32.const 2
  get_local 0
  br_if 0
  i32.add
)

Was man hier also sieht, ist die Konstante 2, die von der Funktion ausgegeben wird, wenn die lokale Variable mit dem Index 0 ungleich Null ist, und andernfalls die Konstanten 1 und 2, die zusammen addiert werden. Das heißt, die 1 wird nur verworfen, wenn die Verzweigung erfolgt. n der Lightbeam IR wird explizit angegeben, welche Elemente für jedes Verzweigungsziel verworfen werden. Das bedeutet, dass es unmöglich ist, diesen Fall zu übersehen oder falsch zu verarbeiten - ein Zweig, bei dem nichts verworfen wird, und ein Zweig, bei dem etwas verworfen wird, werden gleich behandelt.

Wir geben auch in jeder Kopfzeile eines Blocks die Anzahl der Aufrufe an und ob er möglicherweise verkehrte Aufrufer hat - es gibt Optimierungen, die man vornehmen kann, wenn ein Block genau einen Aufrufer² hat, und wir können die Codegenerierung für Blöcke mit null Aufrufern ganz weglassen. Aufgrund des Ansatzes von Wasm für den Kontrollfluss können wir nicht immer im Voraus wissen, wie viele Aufrufer ein Block haben wird, daher zählen wir die Anzahl der Aufrufer selbst. Bei Blöcken, die verkehrte Aufrufer haben können (d. h. Blöcke, die aus den Wasm-Instruktionen loop generiert werden, da Anweisungen zur Verzweigung in die Kopfzeile der loop Intruktion springen), funktioniert das jedoch nicht, und deshalb markieren wir explizit jeden Block, der verkehrte Aufrufer haben könnte. Sie sehen, dass ohne die einfache und ausdrückliche Bereitstellung dieser Informationen in der IR die diesbezüglichen Optimierungen äußerst kompliziert wären.

Das Herzstück des Compilers ist der virtuelle Stapelspeicher. Dies ist eine Reihefolge von zu speichernden Werten nach dem LIFO-Prinzip, die unterschiedlich aussehen können:

• Stapelspeicher: Eine Stelle im physischen Stapelspeicher (d. h. eine Speicherstelle, die ein Offset zu rsp ist). Da sich rsp innerhalb einer Funktion ändern kann, wird dieser Wert als Offset zu dem gespeichert, was rsp zu Beginn der Funktion war, und der tatsächliche Offset wird bei jedem Zugriff auf den Wert neu berechnet.
• Register: Ein Wert in einem Register. Auf einige wichtige Aspekte werde ich weiter unten näher eingehen.
• Immediate: Ein konstanter Wert, der es uns ermöglicht, die Konstanten zu falten und Optimierungen durchzuführen, wie z. B. die Verwendung der Version des Immediate-Operanden von Anweisungen wie add, anstatt die Konstante zuerst in ein Register zu übertragen.
• Zustandscode: Ein Wert, der eines der Bits im FLAGS-Register darstellt. Dies bedeutet, dass eine Vergleichsoperation, gefolgt von einem select oder br_if, in eine der cc-Formen der zugehörigen Anweisungen kompiliert werden kann. Beispielsweise lässt sich i32.lt_u + select zu cmp + cmovb kompilieren, wobei die cmp-Anweisung einige Flags in der CPU festlegt und die cmovb-Anweisung die Flags liest und das entsprechende Register auf einen bestimmten Wert setzt, wenn das b-Flag eingestellt ist. Da es nur ein FLAGS-Register gibt und viele Ereignisse dieses überschreiben, wird diese Art von Wert in ein Register überschrieben, wenn irgendetwas auf den Stapel darüber geschoben wird. In Zukunft möchten wir einen Zustandscode nur dann auslösen, wenn wir tatsächlich eine Operation durchführen, die ihn überschreibt.

Ein wichtiger Aspekt unseres “Register”-Typs ist, dass die Register Referenzzählungen sind. Damit wir verstehen, warum das so wichtig ist, müssen wir über lokale Variablen sprechen.

​​In WebAssembly gibt es zwei Stellen, an denen sich ein Wert befinden kann: auf dem (virtuellen) Stapelspeicher oder in einem lokalen Stapelspeicher. Sie können einen Wert mit set_local vom Stapelspeicher in ein lokales Verzeichnis und mit get_local von einem lokalen Verzeichnis auf den Stapelspeicher verschieben. Es gibt auch tee_local, was gleichbedeutend mit set_local gefolgt von get_local³ ist. Wie dem auch sei, für unsere Zwecke ist es wichtig, dass get_local die Verdopplung eines Wertes bewirkt. Das gilt auch für tee_local, aber der Einfachheit halber ignorieren wir das vorerst. Wenn Sie ein Verwaltungssystem für die Verwendung von Registern haben, z.B. wenn ein Register wiederverwendet werden kann, wenn es nicht mehr möglich ist, auf den Wert zuzugreifen, der sich zuvor darin befand, müssen Sie die Register neu zählen, so dass Sie z.B. ein get_local ausführen können. Danach wird der Wert in diesem lokalen Register überschrieben, ohne dass sich der alte Wert auf dem Stapelspeicher auf magische Weise ändert oder anderweitig ungültig wird. Dies ermöglicht uns jedoch einige andere Optimierungen.

Auf x86 gibt es zum Beispiel keinen wirklichen +-Operator⁴, sondern nur +=. Normalerweise müsste man ein neues Register zuweisen, das LHS des Operators dorthin kopieren und das RHS direkt hinzufügen, aber wenn der Referenzzähler für dieses Register genau 1 ist, kann man es direkt bearbeiten. Ein weiterer Grund für die Verwendung von Referenzzählung in einem Streaming-Compiler ist, dass Sie zwar in geradlinigem Code Aliasing-Werte haben können, aber beim Start eines Loops (und unter einigen anderen Umständen) alle lokalen Variablen und die Elemente des Speicherstapels an eindeutigen Stellen haben müssen. Um zu verdeutlichen, warum das so ist, lassen Sie uns ein Beispiel verwenden. Hier ist ein einfacher Loop in WebAssembly:

(func $bad_factorial (param $param i32)
  (local $counter i32)
  (local $output i32)
  (set_local $counter (get_local $param))
  (set_local $output (get_local $counter))
  (loop
    (set_local $counter
     (i32.sub (get_local $counter)
              (i32.const 1)))
    (set_local $output
     (i32.mul (get_local $output)
              (get_local $counter)))
    (br_if 0 (i32.ne (get_local $counter) (i32.const 0)))
  )
  (return (get_local $output))
)

Wenn der Loop beginnt, zeigen in dieser Funktion also beide lokalen Variablen auf dieselbe Stelle. Das ist schlecht, denn nach der ersten Iteration liegen sie an Stellen, die kein Aliasing aufweisen, und wenn wir Code erzeugen, der an derselben Stelle nach beiden Variablen sucht, werden wir am Ende das falsche Ergebnis erhalten. Wir könnten die Stellen für Variablen, die von Blöcken verwendet werden, beliebig, aber statisch und ohne Aliasing wählen (so wie Funktionen eine spezielle Konvention für Aufrufe namens SystemV haben), aber wir wollen das Verschieben von Werten nach Möglichkeit vermeiden. Beim ersten Aufruf eines Blocks versuchen wir also, die Konvention für den Aufruf des Blocks so zu setzen, wie die Werte beim ersten Aufruf liegen. Wenn wir die Konvention für den Aufruf zum ersten Mal festlegen, weisen wir die minimale Anzahl von neuen Stellen zu, die alle Aliasing-Werte beseitigen. Deshalb ist es wichtig, dass wir wissen, ob ein Block genau einen Aufrufer hat: Wenn er nur einen Aufrufer hat, können wir die Werte immer dort lassen, wo sie sind. Wenn es Aliasing-Werte gibt, dann ist das in Ordnung, da wir wissen, dass es unmöglich ist, dass dieser Block mit Werten ohne Aliasing aufgerufen wird⁵.

Eine genauere Erklärung von Lightbeams IR finden Sie in der Reihe von Artikeln, die mich zur Entwicklung des Systems geführt haben.

Was bedeutet das für mich?

Wenn Sie nur jemand sind, der mit WebAssembly als Nutzer in Kontakt kommt - d. h. Sie schreiben Code, der nach WebAssembly kompiliert wird, und die Wasm-Laufzeitumgebung ist nur eine Blackbox -, dann fragen Sie sich vielleicht, was das für Sie bedeutet. Nun, das bedeutet, dass Wasmtime zu einem wesentlich schnelleren Anwendungsbeginn führen kann und mit hoher Wahrscheinlichkeit auch eine viel gleichmäßigere Startleistung aufweisen wird. Abgesehen davon ist die Verwendung wahrscheinlich für Sie weitgehend unproblematisch. Denn im Prinzip ist es dasselbe wie der LiftOff von V8 oder der Baseline-Compiler von FireFox, nur eben für Wasmtime. Ich hoffe jedoch, dass dieser Artikel einen kleinen Einblick in die Funktionsweise dieser unkonventionellen Form des Compilers gibt.

1. Es wäre technisch möglich, br_table und br_if zu einem einheitlichen Konstrukt zusammenzufügen, aber es gibt Optimierungen, die Sie für die letztere tun können, die nicht mit der vorherigen möglich sind, so dass wir am Ende nur wieder konvertieren werden. Ich werde das vielleicht später nachholen, da es bedeutet, dass wir uns bei der Optimierung auf eine einzige Stelle konzentrieren können (wenn wir also eine br_table mit zwei Zielen als Eingabe erhalten, generieren wir Code, der genauso gut ist wie für eine br_if), aber im Moment sind sie getrennt. Wir könnten sogar br in br_table zu einem Element umwandeln, so dass wir nur eine Möglichkeit haben, mit der wir arbeiten können.
2. In einem “richtigen” optimierenden Compiler, der die Streaming-Kompilation nicht unterstützen muss, können Sie Optimierungen für Blöcke mit mehr als einem Aufrufer durchführen. Ein Streaming-Compiler kann diese Optimierungen jedoch nur für Blöcke mit genau einem Aufrufer durchführen. Ich werde jetzt nicht näher darauf eingehen, warum das so ist, ich überlasse das dem Leser als Übung, aber ich könnte in einem zukünftigen Artikel darauf zurückkommen.
3. Warum sie nicht den alten Wert des lokalen Wertes anzeigen lassen, ist mir ein Rätsel, denn das ist viel schwieriger zu erzeugen (Sie müssen eine zusätzliche lokale Variable erstellen). Das aktuelle Verhalten ist problemlos nachzubilden. Ich vermute, dass es mit den Wurzeln von Wasm als binäre Darstellung von asm.js und der Tatsache zusammenhängt, dass JavaScript a = b = c = d erlaubt, aber das ist nur Spekulation.
4. Technisch gesehen ist + ein schlechtes Beispiel, da man mit lea eine 3-Argument-Variable add nachahmen kann, aber seien Sie bitte nachsichtig mit mir.
5. Mit Werten, die Konstanten sind, haben wir das gleiche Problem wie bei Aliasing-Werten - wenn wir eine Konstante für eine bestimmte Variable zurückgeben, dieser Block dann aber mit einem anderen Wert für diese Konstante aufgerufen wird, erhalten wir am Ende das falsche Ergebnis.

Link zum originalen Artikel: https://www.parity.io/blog/lightbeam-webassembly-compiler/