Wasm mit Binärdateien kompilieren und optimieren

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 Artikel erfahren Sie anhand einer synthetischen Spielsprache namens ExampleScript, wie Sie WebAssembly-Module in JavaScript mit der Binaryen.js API schreiben. Sie lernen die Grundlagen des Erstellens von Modulen, das Hinzufügen von Funktionen zu Modulen und das Exportieren von Funktionen aus Modulen kennen. So erhalten Sie einen Überblick über die allgemeinen Mechanismen zum Kompilieren tatsächlicher Programmiersprachen in WebAssembly. Außerdem erfahren Sie, wie Sie Wasm-Module sowohl mit Binaryen.js als auch über die Befehlszeile mit wasm-opt optimieren.

Binärdateien

Binaryen hat eine intuitive C API in einem einzigen Header und kann auch über JavaScript verwendet werden. Es akzeptiert Eingaben im WebAssembly-Format, aber auch einen allgemeinen Grafikfluss für Compiler, die dies bevorzugen.

Eine Zwischendarstellung (Intermediate Representation, IR) ist die Datenstruktur oder der Code, die bzw. der intern von einem Compiler oder einer virtuellen Maschine zur Darstellung von Quellcode verwendet wird. Die interne IR von Binaryen verwendet kompakte Datenstrukturen und ist für die vollständig parallele Codegenerierung und -optimierung mit allen verfügbaren CPU-Kernen ausgelegt. Die IR von Binaryen wird in WebAssembly kompiliert, da sie eine Teilmenge von WebAssembly ist.

Der Binaryen-Optimierer hat viele Durchläufe, mit denen sich Codegröße und -geschwindigkeit verbessern lassen. Mit diesen Optimierungen soll Binaryen leistungsfähig genug sein, um als Compiler-Backend verwendet zu werden. Dazu gehören WebAssembly-spezifische Optimierungen, die von allgemeinen Compilern möglicherweise nicht durchgeführt werden. Sie können dies als Wasm-Minimierung betrachten.

AssemblyScript als Beispielnutzer von Binaryen

Binaryen wird von einer Reihe von Projekten verwendet, z. B. AssemblyScript, das mit Binaryen von einer TypeScript-ähnlichen Sprache direkt in WebAssembly kompiliert. Probieren Sie das Beispiel im AssemblyScript-Playground aus.

AssemblyScript-Eingabe:

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

Entsprechender WebAssembly-Code in Textform, generiert von Binaryen:

(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
 )
)

Der AssemblyScript-Playground mit dem generierten WebAssembly-Code basierend auf dem vorherigen Beispiel

Die Binaryen-Toolchain

Die Binaryen-Toolchain bietet eine Reihe nützlicher Tools sowohl für JavaScript-Entwickler als auch für Befehlszeilennutzer. Im Folgenden sind einige dieser Tools aufgeführt. Eine vollständige Liste der enthaltenen Tools finden Sie in der README-Datei des Projekts.

  • binaryen.js: Eine eigenständige JavaScript-Bibliothek, die Binaryen-Methoden zum Erstellen und Optimieren von Wasm-Modulen bereitstellt. Builds finden Sie unter binaryen.js auf npm oder können direkt von GitHub oder unpkg heruntergeladen werden.
  • wasm-opt: Befehlszeilentool, das WebAssembly lädt und darauf Binär-IR-Pässe ausführt.
  • wasm-as und wasm-dis: Befehlszeilentools zum Assemblen und Disassemblieren von WebAssembly
  • wasm-ctor-eval: Befehlszeilentool, mit dem Funktionen (oder Teile von Funktionen) zur Kompilierungszeit ausgeführt werden können.
  • wasm-metadce: Befehlszeilentool zum flexiblen Entfernen von Teilen von Wasm-Dateien, je nach Verwendung des Moduls.
  • wasm-merge: Befehlszeilentool, mit dem mehrere Wasm-Dateien in einer einzigen Datei zusammengeführt werden. Dabei werden entsprechende Importe mit Exporten verknüpft. Ähnlich wie ein JavaScript-Bundler, 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:Es wird ein abstrakter Syntaxbaum erstellt.
  • Semantischer Analyse:Prüft auf Fehler und erzwingt Sprachregeln.
  • Zwischencodegenerierung:Erstellen Sie eine abstraktere Darstellung.
  • Codegenerierung:Übersetzung in die Zielsprache.
  • Zielspezifische Codeoptimierung:Optimierung für das Ziel.

Unter Unix werden häufig die Tools lex und yacc zum Kompilieren verwendet:

  • lex (Lexical Analyzer Generator): lex ist ein Tool, mit dem lexikalische Analysetools generiert werden, die auch als Lexer oder Scanner bezeichnet werden. Es nimmt eine Reihe von regulären Ausdrücken und entsprechenden Aktionen als Eingabe entgegen und generiert Code für einen lexikalischen Analyser, 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 generieren in der Regel abstrakte Syntaxbäume (ASTs), die die hierarchische Struktur des Quellcodes darstellen.

Beispiel

Aufgrund des Umfangs dieses Artikels ist es unmöglich, eine vollständige Programmiersprache zu behandeln. Betrachten wir daher der Einfachheit halber eine sehr eingeschränkte und nutzlose synthetische Programmiersprache namens ExampleScript, die generische Vorgänge anhand konkreter Beispiele ausdrückt.

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

Wie bereits erwähnt, völlig nutzlos, aber einfach genug, dass der lexikalische Analyser ein einzelner regulärer Ausdruck sein kann: /\d+\s*[\+\-\*\/]\s*\d+\s*/.

Als Nächstes ist ein Parser erforderlich. Mit einem regulären Ausdruck mit benannten Erfassungsgruppen kann eine sehr vereinfachte Version eines abstrakten Syntaxbaums erstellt werden: /(?<first_operand>\d+)\s*(?<operator>[\+\-\*\/])\s*(?<second_operand>\d+)/.

BeispielScript-Befehle werden jeweils in einer eigenen Zeile eingegeben, damit der Parser den Code zeilenweise verarbeiten kann, indem er ihn an Zeilenvorschubzeichen teilt. Das reicht aus, um die ersten drei Schritte aus der Aufzählungsliste oben zu prüfen: lexikalische Analyse, Syntaxanalyse und semantische Analyse. Der Code für diese Schritte befindet sich in der folgenden Liste.

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),
      };
    });
  }
}

Zwischencodegenerierung

Nachdem ExampleScript-Programme jetzt als abstrakter Syntaxbaum dargestellt werden können (wenn auch ziemlich vereinfacht), besteht der nächste Schritt darin, eine abstrakte Zwischendarstellung zu erstellen. Im ersten Schritt erstellen Sie ein neues Modul in Binaryen:

const module = new binaryen.Module();

Jede Zeile des abstrakten Syntaxbaums enthält ein Triple, das aus firstOperand, operator und secondOperand besteht. Für jeden der vier möglichen Operatoren in ExampleScript, also +, -, * und /, 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 steht für den Namen der Funktion.
  • functionType: Ein Signature steht für die Signatur der Funktion.
  • varTypes: Ein Type[] gibt zusätzliche Ortsnamen in der angegebenen Reihenfolge an.
  • body: ein Expression, der Inhalt der Funktion.

Es gibt noch einige weitere Details, die Sie sich ansehen sollten. Die Binaryen-Dokumentation kann Ihnen dabei helfen. Letztendlich landen Sie beim +-Operator von ExampleScript, der Module#i32.add()-Methode, einer von mehreren verfügbaren Ganzzahloperationen. Für die Addition sind zwei Operanden erforderlich, der erste und der zweite Summand. Damit die Funktion tatsächlich aufrufbar ist, 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, von denen drei mit Ganzzahlen arbeiten, nämlich add() basierend auf Module#i32.add(), subtract() basierend auf Module#i32.sub(), multiply() basierend auf Module#i32.mul() und der 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 im laufenden Beispiel der Kompilierung von ExampleScript in Wasm künstlich inaktiven Code einzuführen, der in einem späteren Schritt optimiert und entfernt wird, fügen Sie 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 empfehlenswert, das Modul mit der Methode Module#validate() zu validieren.

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

Ergänzenden 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 visuell lesbares Format und die binäre Darstellung als .wasm-Datei abzurufen, die direkt im Browser ausgeführt werden kann. Der Binärcode kann direkt im Browser ausgeführt werden. Um zu sehen, ob der Export 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 Textdarstellung für ein ExampleScript-Programm mit allen vier Operationen ist unten aufgeführt. Der inaktive Code ist zwar noch vorhanden, wird aber nicht wie im Screenshot der WebAssembly.Module.exports() 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)
  )
 )
)

Screenshot der DevTools-Konsole mit den WebAssembly-Modulexporten, die vier Funktionen zeigen: addieren, dividieren, multiplizieren und subtrahieren (aber nicht den nicht freigegebenen Totcode)

WebAssembly optimieren

Binaryen bietet zwei Möglichkeiten, Wasm-Code zu optimieren. Eine in Binaryen.js selbst und eine für die Befehlszeile. Bei der ersten werden standardmäßig die Standardoptimierungsregeln angewendet und Sie können die Optimierungs- und Minimierungsebene festlegen. Bei der zweiten werden standardmäßig keine Regeln verwendet, sondern es ist eine vollständige Anpassung möglich. Mit ausreichenden Tests können Sie die Einstellungen also an Ihren Code anpassen, 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 die Optimierungs- und Schrumpfebene 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ührte Totcode entfernt, sodass er in der Textdarstellung der Wasm-Version des Beispiel-Scripts nicht mehr enthalten ist. Beachten Sie auch, dass die local.set/get-Paare durch die Optimierungsschritte SimplifyLocals (verschiedene lokalbezogene Optimierungen) und Vacuum (entfernt offensichtlich nicht benötigten Code) entfernt werden und das return durch RemoveUnusedBrs (entfernt Brü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. Module#optimize() verwendet die Standardeinstellungen der jeweiligen Optimierungs- und Schrumpfebenen. Für eine vollständige Anpassung müssen Sie das Befehlszeilentool wasm-opt verwenden.

Optimierung mit dem Befehlszeilentool „wasm-opt“

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

wasm-opt --help

Hier finden Sie einen Auszug aus den Karten/Tickets, die auch ohne Fachwissen verständlich sind:

  • CodeFolding:Vermeidet Codeduplikate, indem Code zusammengeführt wird (z. B. wenn zwei if-Äste am Ende gemeinsame Anweisungen haben).
  • DeadArgumentElimination:Optimierungsdurchlauf zur Linkzeit, um Argumente einer Funktion zu entfernen, wenn sie immer mit denselben Konstanten aufgerufen wird.
  • MinifyImportsAndExports:Minimiert sie auf "a", "b".
  • DeadCodeElimination:Entfernt nicht mehr benötigten Code.

Es gibt ein Optimierungshandbuch mit mehreren Tipps, mit denen Sie herausfinden können, welche der verschiedenen Flags wichtiger sind und zuerst ausprobiert werden sollten. Manchmal wird die Eingabe durch wiederholtes Ausführen von wasm-opt noch weiter verkleinert. In solchen Fällen wird die Ausführung mit dem Flag --converge wiederholt, bis keine weitere Optimierung 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 Beispiel-Script-Eingaben eingeben. Sehen Sie sich auch den Quellcode der Demo an.

Ergebnisse

Binaryen bietet ein leistungsstarkes Toolkit zum Kompilieren von Sprachen in WebAssembly und zur Optimierung des resultierenden Codes. Die JavaScript-Bibliothek und die Befehlszeilentools bieten Flexibilität und Benutzerfreundlichkeit. In diesem Beitrag wurden die Grundprinzipien der Wasm-Kompilierung erläutert. Dabei wurde die Effektivität und das Potenzial von Binaryen für eine maximale Optimierung hervorgehoben. Viele der Optionen zur Anpassung der Optimierungen von Binaryen erfordern fundiertes Wissen über die internen Funktionen von Wasm. Normalerweise funktionieren die Standardeinstellungen jedoch bereits hervorragend. Viel Spaß beim Kompilieren und Optimieren mit Binaryen!

Danksagungen

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