Wasm mit Binärdateien kompilieren und optimieren

Thomas Steiner

Binaryen ist eine Compiler- und Toolchain-Infrastrukturbibliothek für WebAssembly, die in C++ geschrieben wurde. Ziel ist es, das Kompilieren in WebAssembly intuitiv, schnell und effektiv zu gestalten. In diesem Beitrag erfahren Sie anhand der synthetischen Spielzeugsprache ExampleScript, wie Sie WebAssembly-Module in JavaScript mit der Binaryen.js API schreiben. Sie lernen die Grundlagen der Modulerstellung, das Hinzufügen von Funktionen zum Modul und das Exportieren von Funktionen aus dem Modul kennen. So erhalten Sie einen Überblick über die allgemeinen Mechanismen der Kompilierung von Programmiersprachen zu WebAssembly. Außerdem erfahren Sie, wie Sie Wasm-Module sowohl mit Binaryen.js als auch über die Befehlszeile mit wasm-opt optimieren.

Hintergrund zu Binaryen

Binaryen bietet eine intuitive C-API in einem einzelnen Header und kann auch über JavaScript verwendet werden. Es akzeptiert Eingaben in WebAssembly-Form, aber auch einen allgemeinen Kontrollflussgraphen für Compiler, die das bevorzugen.

Eine Zwischenrepräsentation (Intermediate Representation, IR) ist die Datenstruktur oder der Code, der intern von einem Compiler oder einer virtuellen Maschine verwendet wird, um Quellcode darzustellen. Die interne IR von Binaryen verwendet kompakte Datenstrukturen und ist für die vollständig parallele Codegenerierung und ‑optimierung konzipiert, wobei alle verfügbaren CPU-Kerne genutzt werden. Der IR von Binaries wird in WebAssembly kompiliert, da er eine Teilmenge von WebAssembly ist.

Der Optimierer von Binaryen hat viele Durchläufe, die die Codegröße und ‑geschwindigkeit verbessern können. Diese Optimierungen sollen Binaryen so leistungsstark machen, dass es als Compiler-Backend verwendet werden kann. Es enthält WebAssembly-spezifische Optimierungen, die allgemeine Compiler möglicherweise nicht vornehmen. Das können Sie sich als Wasm-Minifizierung vorstellen.

AssemblyScript als Beispielnutzer von Binaryen

Binaryen wird von einer Reihe von Projekten verwendet, z. B. von AssemblyScript, das Binaryen verwendet, um direkt von einer TypeScript-ähnlichen Sprache in WebAssembly zu kompilieren. Beispiel im AssemblyScript-Playground ausprobieren

AssemblyScript-Eingabe:

export function add(a: i32, b: i32): i32 {
  return a + b;
}

Entsprechender WebAssembly-Code in Textform, der von Binaryen generiert wurde:

(module
 (type $0 (func (param i32 i32) (result i32)))
 (memory $0 0)
 (export "add" (func $module/add))
 (export "memory" (memory $0))
 (func $module/add (param $0 i32) (param $1 i32) (result i32)
  local.get $0
  local.get $1
  i32.add
 )
)

Die AssemblyScript-Playground-Umgebung mit dem generierten WebAssembly-Code basierend auf dem vorherigen Beispiel.

Die Binaryen-Toolchain

Die Binaryen-Toolchain bietet eine Reihe nützlicher Tools für JavaScript-Entwickler und Befehlszeilennutzer. Eine Teilmenge dieser Tools ist unten aufgeführt. Die vollständige Liste der enthaltenen Tools ist in der README-Datei des Projekts verfügbar.

  • binaryen.js: Eine eigenständige JavaScript-Bibliothek, die Binaryen-Methoden zum Erstellen und Optimieren von Wasm-Modulen bereitstellt. Informationen zu Builds finden Sie unter binaryen.js auf npm (oder laden Sie die Datei direkt von GitHub oder unpkg herunter).
  • wasm-opt: Befehlszeilentool, das WebAssembly lädt und Binaryen IR-Passes darauf ausführt.
  • wasm-as und wasm-dis: Befehlszeilentools zum Zusammenstellen und Zerlegen von WebAssembly.
  • wasm-ctor-eval: Befehlszeilentool, mit dem Funktionen (oder Teile von Funktionen) zur Kompilierzeit ausgeführt werden können.
  • wasm-metadce: Befehlszeilentool zum flexiblen Entfernen von Teilen von Wasm-Dateien, je nachdem, wie das Modul verwendet wird.
  • wasm-merge: Befehlszeilentool, mit dem mehrere Wasm-Dateien in einer einzigen Datei zusammengeführt werden. Dabei werden entsprechende Importe mit Exporten verknüpft. Es funktioniert wie ein Bundler für JavaScript, aber für Wasm.

In WebAssembly kompilieren

Das Kompilieren einer Sprache in eine andere umfasst in der Regel mehrere Schritte. Die wichtigsten sind in der folgenden Liste aufgeführt:

  • Lexikalische Analyse:Der Quellcode wird in Tokens unterteilt.
  • Syntaxanalyse:Erstellen Sie eine abstrakte Syntaxstruktur.
  • Semantische Analyse:Auf Fehler prüfen und Sprachregeln durchsetzen.
  • Generierung von Zwischencode:Erstellen Sie eine abstraktere Darstellung.
  • Codegenerierung:In die Zielsprache übersetzen.
  • Zielspezifische Codeoptimierung:Optimieren Sie für das Ziel.

In der Unix-Welt werden häufig die folgenden Tools zum Kompilieren verwendet: lex und yacc:

  • lex (Lexical Analyzer Generator): lex ist ein Tool, mit dem lexikalische Analysatoren (auch als Lexer oder Scanner bezeichnet) generiert werden. Es nimmt eine Reihe von regulären Ausdrücken und entsprechenden Aktionen als Eingabe entgegen und generiert Code für einen lexikalischen Analysator, der Muster im Eingabe-Quellcode erkennt.
  • yacc (Yet Another Compiler Compiler): yacc ist ein Tool, mit dem Parser für die Syntaxanalyse generiert werden. Es nimmt eine formale Grammatikbeschreibung einer Programmiersprache als Eingabe entgegen und generiert Code für einen Parser. Parser erstellen in der Regel abstrakte Syntaxbäume (ASTs), die die hierarchische Struktur des Quellcodes darstellen.

Beispiel

Angesichts des Umfangs dieses Beitrags ist es unmöglich, eine vollständige Programmiersprache zu behandeln. Der Einfachheit halber wird daher eine sehr begrenzte und nutzlose synthetische Programmiersprache namens „ExampleScript“ verwendet, die generische Operationen durch konkrete Beispiele ausdrückt.

  • Um eine add()-Funktion zu schreiben, codieren Sie ein Beispiel für eine beliebige Addition, z. B. 2 + 3.
  • Um eine multiply()-Funktion zu schreiben, geben Sie beispielsweise 6 * 12 ein.

Wie in der Vorwarnung erwähnt, ist sie völlig nutzlos, aber einfach genug, damit ihr lexikalischer Analysator ein einzelner regulärer Ausdruck ist: /\d+\s*[\+\-\*\/]\s*\d+\s*/.

Als Nächstes benötigen Sie einen Parser. Tatsächlich kann eine sehr vereinfachte Version eines abstrakten Syntaxbaums mithilfe eines regulären Ausdrucks mit benannten Erfassungsgruppen erstellt werden: /(?<first_operand>\d+)\s*(?<operator>[\+\-\*\/])\s*(?<second_operand>\d+)/.

ExampleScript-Befehle stehen jeweils in einer eigenen Zeile, sodass der Parser den Code zeilenweise verarbeiten kann, indem er ihn anhand von Zeilenumbruchzeichen aufteilt. Das reicht aus, um die ersten drei Schritte aus der Aufzählungsliste oben zu prüfen, nämlich lexikalische Analyse, Syntaxanalyse und semantische Analyse. Der Code für diese Schritte ist in der folgenden Auflistung enthalten.

export default class Parser {
  parse(input) {
    input = input.split(/\n/);
    if (!input.every((line) => /\d+\s*[\+\-\*\/]\s*\d+\s*/gm.test(line))) {
      throw new Error('Parse error');
    }

    return input.map((line) => {
      const { groups } =
        /(?<first_operand>\d+)\s*(?<operator>[\+\-\*\/])\s*(?<second_operand>\d+)/gm.exec(
          line,
        );
      return {
        firstOperand: Number(groups.first_operand),
        operator: groups.operator,
        secondOperand: Number(groups.second_operand),
      };
    });
  }
}

Generierung von Zwischencode

Nachdem ExampleScript-Programme nun als abstrakter Syntaxbaum (wenn auch ein recht vereinfachter) dargestellt werden können, besteht der nächste Schritt darin, eine abstrakte Zwischenrepräsentation zu erstellen. Als Erstes müssen Sie ein neues Modul in Binaryen erstellen:

const module = new binaryen.Module();

Jede Zeile des abstrakten Syntaxbaums enthält ein Triple aus firstOperand, operator und secondOperand. Für jeden der vier möglichen Operatoren in ExampleScript, d. h. +, -, *, /, muss dem Modul eine neue Funktion mit der Module#addFunction()-Methode von Binaryen hinzugefügt werden. Die Parameter der Module#addFunction()-Methoden sind:

  • name: Ein string, das den Namen der Funktion darstellt.
  • functionType: Ein Signature, der die Signatur der Funktion darstellt.
  • varTypes: Eine Type[] gibt zusätzliche Gebietsschemas in der angegebenen Reihenfolge an.
  • body: eine Expression, den Inhalt der Funktion.

Weitere Informationen finden Sie in der Binaryen-Dokumentation. Für den +-Operator von ExampleScript landen Sie schließlich bei der Module#i32.add()-Methode als eine von mehreren verfügbaren Ganzzahloperationen. Für die Addition sind zwei Operanden erforderlich, der erste und der zweite Summand. Damit die Funktion tatsächlich aufgerufen werden kann, muss sie mit Module#addFunctionExport() exportiert werden.

module.addFunction(
  'add', // name: string
  binaryen.createType([binaryen.i32, binaryen.i32]), // params: Type
  binaryen.i32, // results: Type
  [binaryen.i32], // vars: Type[]
  //  body: ExpressionRef
  module.block(null, [
    module.local.set(
      2,
      module.i32.add(
        module.local.get(0, binaryen.i32),
        module.local.get(1, binaryen.i32),
      ),
    ),
    module.return(module.local.get(2, binaryen.i32)),
  ]),
);
module.addFunctionExport('add', 'add');

Nach der Verarbeitung des abstrakten Syntaxbaums enthält das Modul vier Methoden, drei für Ganzzahlen, nämlich add() basierend auf Module#i32.add(), subtract() basierend auf Module#i32.sub(), multiply() basierend auf Module#i32.mul() und den Ausreißer divide() basierend auf Module#f64.div(), da ExampleScript auch mit Gleitkommaergebnissen arbeitet.

for (const line of parsed) {
      const { firstOperand, operator, secondOperand } = line;

      if (operator === '+') {
        module.addFunction(
          'add', // name: string
          binaryen.createType([binaryen.i32, binaryen.i32]), // params: Type
          binaryen.i32, // results: Type
          [binaryen.i32], // vars: Type[]
          //  body: ExpressionRef
          module.block(null, [
            module.local.set(
              2,
              module.i32.add(
                module.local.get(0, binaryen.i32),
                module.local.get(1, binaryen.i32)
              )
            ),
            module.return(module.local.get(2, binaryen.i32)),
          ])
        );
        module.addFunctionExport('add', 'add');
      } else if (operator === '-') {
        module.subtractFunction(
          // Skipped for brevity.
        )
      } else if (operator === '*') {
          // Skipped for brevity.
      }
      // And so on for all other operators, namely `-`, `*`, and `/`.

Wenn Sie mit tatsächlichen Codebases arbeiten, gibt es manchmal Dead Code, der nie aufgerufen wird. Um künstlich Dead Code einzuführen, der in einem späteren Schritt optimiert und entfernt wird, fügen Sie im laufenden Beispiel der Kompilierung von ExampleScript zu Wasm eine nicht exportierte Funktion hinzu.

// This function is added, but not exported,
// so it's effectively dead code.
module.addFunction(
  'deadcode', // name: string
  binaryen.createType([binaryen.i32, binaryen.i32]), // params: Type
  binaryen.i32, // results: Type
  [binaryen.i32], // vars: Type[]
  //  body: ExpressionRef
  module.block(null, [
    module.local.set(
      2,
      module.i32.div_u(
        module.local.get(0, binaryen.i32),
        module.local.get(1, binaryen.i32),
      ),
    ),
    module.return(module.local.get(2, binaryen.i32)),
  ]),
);

Der Compiler ist jetzt fast fertig. Es ist nicht unbedingt erforderlich, aber es ist auf jeden Fall empfehlenswert, das Modul mit der Methode Module#validate() zu validieren.

if (!module.validate()) {
  throw new Error('Validation error');
}

Ergebnis-Wasm-Code abrufen

Um den resultierenden Wasm-Code zu erhalten, gibt es in Binaryen zwei Methoden, um die textuelle Darstellung als .wat-Datei im S-Ausdruck als für Menschen lesbares Format und die binäre Darstellung als .wasm-Datei zu erhalten, die direkt im Browser ausgeführt werden kann. Der Binärcode kann direkt im Browser ausgeführt werden. Um zu sehen, ob es funktioniert hat, kann es hilfreich sein, die Exporte zu protokollieren.

const textData = module.emitText();
console.log(textData);

const wasmData = module.emitBinary();
const compiled = new WebAssembly.Module(wasmData);
const instance = new WebAssembly.Instance(compiled, {});
console.log('Wasm exports:\n', instance.exports);

Die vollständige textuelle Darstellung für ein ExampleScript-Programm mit allen vier Vorgängen ist unten aufgeführt. Der inaktive Code ist weiterhin vorhanden, wird aber gemäß dem Screenshot von WebAssembly.Module.exports() nicht angezeigt.

(module
 (type $0 (func (param i32 i32) (result i32)))
 (type $1 (func (param f64 f64) (result f64)))
 (export "add" (func $add))
 (export "subtract" (func $subtract))
 (export "multiply" (func $multiply))
 (export "divide" (func $divide))
 (func $add (param $0 i32) (param $1 i32) (result i32)
  (local $2 i32)
  (local.set $2
   (i32.add
    (local.get $0)
    (local.get $1)
   )
  )
  (return
   (local.get $2)
  )
 )
 (func $subtract (param $0 i32) (param $1 i32) (result i32)
  (local $2 i32)
  (local.set $2
   (i32.sub
    (local.get $0)
    (local.get $1)
   )
  )
  (return
   (local.get $2)
  )
 )
 (func $multiply (param $0 i32) (param $1 i32) (result i32)
  (local $2 i32)
  (local.set $2
   (i32.mul
    (local.get $0)
    (local.get $1)
   )
  )
  (return
   (local.get $2)
  )
 )
 (func $divide (param $0 f64) (param $1 f64) (result f64)
  (local $2 f64)
  (local.set $2
   (f64.div
    (local.get $0)
    (local.get $1)
   )
  )
  (return
   (local.get $2)
  )
 )
 (func $deadcode (param $0 i32) (param $1 i32) (result i32)
  (local $2 i32)
  (local.set $2
   (i32.div_u
    (local.get $0)
    (local.get $1)
   )
  )
  (return
   (local.get $2)
  )
 )
)

DevTools-Konsolen-Screenshot der WebAssembly-Modulexporte mit vier Funktionen: „add“, „divide“, „multiply“ und „subtract“ (aber nicht dem nicht exponierten inaktiven Code).

WebAssembly optimieren

Binaryen bietet zwei Möglichkeiten zum Optimieren von Wasm-Code. Eine in Binaryen.js selbst und eine für die Befehlszeile. Bei der ersten Methode wird standardmäßig der Standardsatz von Optimierungsregeln angewendet. Sie können den Optimierungs- und den Verkleinerungsgrad festlegen. Bei der zweiten Methode werden standardmäßig keine Regeln verwendet. Stattdessen ist eine vollständige Anpassung möglich. Das bedeutet, dass Sie die Einstellungen durch ausreichendes Testen an Ihren Code anpassen können, um optimale Ergebnisse zu erzielen.

Mit Binaryen.js optimieren

Die einfachste Methode zum Optimieren eines Wasm-Moduls mit Binaryen besteht darin, die Module#optimize()-Methode von Binaryen.js direkt aufzurufen und optional das Optimierungs- und das Komprimierungsniveau festzulegen.

// Assume the `wast` variable contains a Wasm program.
const module = binaryen.parseText(wast);
binaryen.setOptimizeLevel(2);
binaryen.setShrinkLevel(1);
// This corresponds to the `-Os` setting.
module.optimize();

Dadurch wird der zuvor künstlich eingefügte inaktive Code entfernt, sodass die textuelle Darstellung der Wasm-Version des Beispiel-Toy-Beispiels ExampleScript ihn nicht mehr enthält. Beachten Sie auch, wie die local.set/get-Paare durch die Optimierungsschritte SimplifyLocals (verschiedene lokale Optimierungen) und Vacuum (entfernt offensichtlich unnötigen Code) entfernt werden und wie return durch RemoveUnusedBrs (entfernt Zeilenumbrüche an nicht benötigten Stellen) entfernt wird.

 (module
 (type $0 (func (param i32 i32) (result i32)))
 (type $1 (func (param f64 f64) (result f64)))
 (export "add" (func $add))
 (export "subtract" (func $subtract))
 (export "multiply" (func $multiply))
 (export "divide" (func $divide))
 (func $add (; has Stack IR ;) (param $0 i32) (param $1 i32) (result i32)
  (i32.add
   (local.get $0)
   (local.get $1)
  )
 )
 (func $subtract (; has Stack IR ;) (param $0 i32) (param $1 i32) (result i32)
  (i32.sub
   (local.get $0)
   (local.get $1)
  )
 )
 (func $multiply (; has Stack IR ;) (param $0 i32) (param $1 i32) (result i32)
  (i32.mul
   (local.get $0)
   (local.get $1)
  )
 )
 (func $divide (; has Stack IR ;) (param $0 f64) (param $1 f64) (result f64)
  (f64.div
   (local.get $0)
   (local.get $1)
  )
 )
)

Es gibt viele Optimierungsdurchläufe und Module#optimize() verwendet die Standardeinstellungen für die jeweiligen Optimierungs- und Verkleinerungsstufen. Für eine vollständige Anpassung müssen Sie das Befehlszeilentool wasm-opt verwenden.

Optimieren mit dem wasm-opt-Befehlszeilentool

Für die vollständige Anpassung der zu verwendenden Durchläufe enthält Binaryen das Befehlszeilentool wasm-opt. Eine vollständige Liste der möglichen Optimierungsoptionen finden Sie in der Hilfemeldung des Tools. Das Tool wasm-opt ist wahrscheinlich das beliebteste der Tools und wird von mehreren Compiler-Toolchains zum Optimieren von Wasm-Code verwendet, darunter Emscripten, J2CL, Kotlin/Wasm, dart2wasm, wasm-pack und andere.

wasm-opt --help

Hier ist ein Auszug einiger der Durchgänge, die auch ohne Fachwissen nachvollziehbar sind:

  • CodeFolding:Vermeidet doppelten Code, indem er zusammengeführt wird (z. B. wenn zwei if-Arme am Ende einige gemeinsame Anweisungen haben).
  • DeadArgumentElimination:Link-Time-Optimierungspass zum Entfernen von Argumenten für eine Funktion, wenn sie immer mit denselben Konstanten aufgerufen wird.
  • MinifyImportsAndExports:Minimiert sie zu "a" und "b".
  • DeadCodeElimination:Entfernen Sie nicht mehr benötigten Code.

Es gibt ein Optimierungs-Kochbuch mit mehreren Tipps, um herauszufinden, welche der verschiedenen Flags wichtiger sind und zuerst ausprobiert werden sollten. Wenn Sie wasm-opt beispielsweise immer wieder ausführen, wird die Eingabe immer weiter verkleinert. In solchen Fällen wird mit dem --converge-Flag so lange iteriert, bis keine weitere Optimierung mehr erfolgt und ein Fixpunkt erreicht wird.

Demo

Wenn Sie die in diesem Beitrag vorgestellten Konzepte in Aktion sehen möchten, können Sie die eingebettete Demo ausprobieren und beliebige ExampleScript-Eingaben machen. Sehen Sie sich auch den Quellcode der Demo an.

Zusammenfassung

Binaryen bietet ein leistungsstarkes Toolkit zum Kompilieren von Sprachen in WebAssembly und zum Optimieren des resultierenden Codes. Die JavaScript-Bibliothek und die Befehlszeilentools bieten Flexibilität und Benutzerfreundlichkeit. In diesem Beitrag wurden die grundlegenden Prinzipien der Wasm-Kompilierung erläutert und die Effektivität und das Potenzial von Binaryen für maximale Optimierung hervorgehoben. Viele der Optionen zum Anpassen der Optimierungen von Binaryen erfordern zwar fundierte Kenntnisse der internen Abläufe von Wasm, aber in der Regel funktionieren die Standardeinstellungen bereits sehr gut. Viel Spaß beim Kompilieren und Optimieren mit Binaryen!

Danksagungen

Dieser Beitrag wurde von Alon Zakai, Thomas Lively und Rachel Andrew geprüft.