Compilazione e ottimizzazione di Wasm con Binaryen

Thomas Steiner

Binaryen è una libreria di infrastruttura per compilatori e toolchain per WebAssembly, scritta in C++. Il suo obiettivo è rendere la compilazione in WebAssembly intuitiva, veloce ed efficace. In questo post, utilizzando l'esempio di un linguaggio sintetico giocattolo chiamato ExampleScript, scopri come scrivere moduli WebAssembly in JavaScript utilizzando l'API Binaryen.js. Tratterai le nozioni di base sulla creazione dei moduli, sull'aggiunta di funzioni al modulo e sull'esportazione delle funzioni dal modulo. In questo modo, acquisirai conoscenze sulle dinamiche generali della compilazione di linguaggi di programmazione effettivi in WebAssembly. Inoltre, scoprirai come ottimizzare i moduli Wasm sia con Binaryen.js sia sulla riga di comando con wasm-opt.

Informazioni generali su Binaryen

Binaryen ha un'API C intuitiva in un unico header e può essere anche utilizzata da JavaScript. Accetta input in formato WebAssembly, ma accetta anche un grafo di flusso di controllo generale per i compilatori che preferiscono questo formato.

Una rappresentazione intermedia (IR) è la struttura di dati o il codice utilizzato internamente da un compilatore o da una macchina virtuale per rappresentare il codice sorgente. L'IR interno di Binaryen utilizza strutture di dati compatte ed è progettato per la generazione e l'ottimizzazione del codice completamente in parallelo, utilizzando tutti i core della CPU disponibili. Il codice intermedio di Binaryen viene compilato in WebAssembly perché è un sottoinsieme di WebAssembly.

L'ottimizzatore di Binaryen ha molti passaggi che possono migliorare le dimensioni e la velocità del codice. Queste ottimizzazioni hanno lo scopo di rendere Binaryen sufficientemente potente da essere utilizzato da solo come backend del compilatore. Include ottimizzazioni specifiche per WebAssembly (che i compilatori generici potrebbero non eseguire), che puoi considerare come la minimizzazione di Wasm.

AssemblyScript come utente di esempio di Binaryen

Binaryen è utilizzato da diversi progetti, ad esempio AssemblyScript, che utilizza Binaryen per compilare da un linguaggio simile a TypeScript direttamente in WebAssembly. Prova l'esempio nel playground di AssemblyScript.

Input AssemblyScript:

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

Codice WebAssembly corrispondente in formato di testo generato da 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
 )
)

Il playground di AssemblyScript che mostra il codice WebAssembly generato in base all'esempio precedente.

La toolchain Binaryen

La toolchain Binaryen offre una serie di strumenti utili sia per gli sviluppatori JavaScript sia per gli utenti della riga di comando. Un sottoinsieme di questi strumenti è elencato di seguito. L'elenco completo degli strumenti contenuti è disponibile nel file README del progetto.

  • binaryen.js: una libreria JavaScript autonoma che espone i metodi Binaryen per la creazione e l'ottimizzazione dei moduli Wasm. Per le build, consulta binaryen.js su npm (o scaricalo direttamente da GitHub o unpkg).
  • wasm-opt: strumento a riga di comando che carica WebAssembly ed esegue su di esso i passaggi IR di Binaryen.
  • wasm-as e wasm-dis: strumenti a riga di comando che assemblano e disasmontano WebAssembly.
  • wasm-ctor-eval: strumento a riga di comando che può eseguire funzioni (o parti di funzioni) in fase di compilazione.
  • wasm-metadce: strumento a riga di comando per rimuovere parti di file Wasm in modo flessibile, in base all'utilizzo del modulo.
  • wasm-merge: strumento a riga di comando che unisce più file Wasm in un unico file, collegando le importazioni corrispondenti alle esportazioni. È simile a un bundler per JavaScript, ma per Wasm.

Compilazione in WebAssembly

La compilazione di un linguaggio in un altro prevede in genere diversi passaggi, i più importanti sono elencati nel seguente elenco:

  • Analisi lessicale:suddividi il codice sorgente in token.
  • Analisi della sintassi:crea un albero sintattico astratto.
  • Analisi semantica: controlla la presenza di errori e applica le regole della lingua.
  • Generare codice intermedio:crea una rappresentazione più astratta.
  • Generare codice:traduci nella lingua di destinazione.
  • Ottimizzazione del codice in base al target:ottimizza per il target.

Nel mondo Unix, gli strumenti di compilazione più utilizzati sono lex e yacc:

  • lex (Generatore di analizzatori lessicali): lex è uno strumento che genera analizzatori lessicali, noti anche come analizzatori o scanner. Prende come input un insieme di espressioni regolari e azioni corrispondenti e genera codice per un analizzatore lessicale che riconosce i pattern nel codice sorgente di input.
  • yacc (Yet Another Compiler Compiler): yacc è uno strumento che genera parser per l'analisi della sintassi. Prende come input una descrizione formale della grammatica di un linguaggio di programmazione e genera codice per un parser. I parser tipicamente producono alberi di sintassi astratti (AST) che rappresentano la struttura gerarchica del codice sorgente.

Un esempio pratico

Dato l'ambito di questo post, è impossibile trattare un linguaggio di programmazione completo, quindi per semplicità, considera un linguaggio di programmazione sintetico molto limitato e inutile chiamato ExampleScript che funziona esprimendo operazioni generiche tramite esempi concreti.

  • Per scrivere una funzione add(), devi creare un esempio di qualsiasi operazione di addizione, ad esempio 2 + 3.
  • Per scrivere una funzione multiply(), scrivi, ad esempio, 6 * 12.

Come da avviso precedente, completamente inutile, ma abbastanza semplice per il suo analizzatore lessicale da essere una singola espressione regolare: /\d+\s*[\+\-\*\/]\s*\d+\s*/.

Poi, deve essere presente un parser. In realtà, è possibile creare una versione molto semplificata di un albero sintattico astratto utilizzando un'espressione regolare con gruppi di cattura denominati: /(?<first_operand>\d+)\s*(?<operator>[\+\-\*\/])\s*(?<second_operand>\d+)/.

I comandi ExampleScript sono uno per riga, quindi l'analizzatore può elaborare il codiceriga per riga dividendolo in base ai caratteri di a capo. È sufficiente controllare i primi tre passaggi dell'elenco puntato precedente, ovvero analisi lessicale, analisi sintattica e analisi semantica. Il codice per questi passaggi è riportato nella seguente scheda.

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

Generazione di codice intermedio

Ora che i programmi ExampleScript possono essere rappresentati come un albero sintattico astratto (anche se piuttosto semplificato), il passaggio successivo consiste nel creare una rappresentazione intermedia astratta. Il primo passaggio consiste nel creare un nuovo modulo in Binaryen:

const module = new binaryen.Module();

Ogni riga dell'albero della sintassi astratta contiene una tripla composta da firstOperand, operator e secondOperand. Per ciascuno dei quattro possibili operatori in ExampleScript, ovvero +, -, *, /, è necessario aggiungere al modulo una nuova funzione con il metodo Module#addFunction() di Binaryen. I parametri dei metodi Module#addFunction() sono i seguenti:

  • name: un string, rappresenta il nome della funzione.
  • functionType: un Signature, rappresenta la firma della funzione.
  • varTypes: un Type[] indica altri locali, nell'ordine specificato.
  • body: un Expression, i contenuti della funzione.

Esistono altri dettagli da esaminare e la documentazione di Binaryen può aiutarti a orientarti, ma alla fine, per l'operatore + di ExampleScript, arriverai al metodo Module#i32.add() come una delle varie operazioni sugli interi disponibili. L'addizione richiede due operandi, il primo e il secondo addendo. Affinché la funzione sia effettivamente richiamabile, deve essere esportata con Module#addFunctionExport().

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');

Dopo l'elaborazione dell'albero sintattico astratto, il modulo contiene quattro metodi, tre che funzionano con numeri interi, ovvero add() basato su Module#i32.add(), subtract() basato su Module#i32.sub(), multiply() basato su Module#i32.mul() e l'outlier divide() basato su Module#f64.div() perché ExampleScript funziona anche con risultati in virgola mobile.

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 `/`.

Se utilizzi basi di codice effettive, a volte è presente codice inutilizzato che non viene mai chiamato. Per introdurre artificialmente codice inutilizzato (che verrà ottimizzato ed eliminato in un passaggio successivo) nell'esempio di esecuzione della compilazione di ExampleScript in Wasm, è sufficiente aggiungere una funzione non esportata.

// 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)),
  ]),
);

Il compilatore è quasi pronto. Non è strettamente necessario, ma è buona prassi convalidare il modulo con il metodo Module#validate().

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

Ottenere il codice Wasm risultante

Per ottenere il codice Wasm risultante, in Binaryen esistono due metodi per ottenere la rappresentazione testuale come file .wat in espressione S in un formato leggibile e la rappresentazione binaria come file .wasm che può essere eseguito direttamente nel browser. Il codice binario può essere eseguito direttamente nel browser. Per verificare che funzioni, può essere utile registrare le esportazioni.

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

La rappresentazione testuale completa di un programma ExampleScript con tutte e quattro le operazioni è elencata di seguito. Tieni presente che il codice inutilizzato è ancora presente, ma non è visibile come nello screenshot di WebAssembly.Module.exports().

(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 della console DevTools delle esportazioni del modulo WebAssembly che mostra quattro funzioni: add, divide, multiply e subtract (ma non il codice inutilizzato non esposto).

Ottimizzazione di WebAssembly

Binaryen offre due modi per ottimizzare il codice Wasm. Uno in Binaryen.js e uno per la riga di comando. Il primo applica per impostazione predefinita l'insieme standard di regole di ottimizzazione e ti consente di impostare il livello di ottimizzazione e di riduzione. Il secondo per impostazione predefinita non utilizza regole, ma consente una personalizzazione completa, il che significa che con una sperimentazione sufficiente puoi personalizzare le impostazioni per ottenere risultati ottimali in base al tuo codice.

Ottimizzazione con Binaryen.js

Il modo più semplice per ottimizzare un modulo Wasm con Binaryen è chiamare direttamente il metodo Module#optimize() di Binaryen.js e, facoltativamente, impostare il livello di ottimizzazione e compressione.

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

In questo modo viene rimosso il codice inutilizzato introdotto artificialmente in precedenza, pertanto la rappresentazione testuale della versione Wasm dell'esempio di giocattolo ExampleScript non lo contiene più. Tieni presente anche come le coppie local.set/get vengono rimosse dai passaggi di ottimizzazione SimplifyLocals (ottimizzazioni varie relative ai locali) e Vacuum (rimuove il codice chiaramente non necessario) e come return viene rimosso da RemoveUnusedBrs (rimuove le interruzioni da posizioni non necessarie).

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

Esistono molti passaggi di ottimizzazione, e Module#optimize() utilizza i set predefiniti dei livelli di ottimizzazione e riduzione. Per una personalizzazione completa, devi utilizzare lo strumento a riga di comando wasm-opt.

Ottimizzazione con lo strumento a riga di comando wasm-opt

Per la personalizzazione completa delle pass da utilizzare, Binaryen include lo strumento a riga di comando wasm-opt. Per un elenco completo delle possibili opzioni di ottimizzazione, controlla il messaggio di aiuto dello strumento. Lo strumento wasm-opt è probabilmente il più popolare tra gli strumenti ed è utilizzato da diverse toolchain del compilatore per ottimizzare il codice Wasm, tra cui Emscripten, J2CL, Kotlin/Wasm, dart2wasm, wasm-pack e altri.

wasm-opt --help

Per farti un'idea dei permessi, ecco un estratto di alcuni di quelli che sono comprensibili senza conoscenze specifiche:

  • CodeFolding: evita il codice duplicato combinándolo (ad esempio, se due if branch hanno alcune istruzioni condivise alla fine).
  • DeadArgumentElimination: passaggio di ottimizzazione in fase di linking per rimuovere gli argomenti da una funzione se viene chiamata sempre con le stesse costanti.
  • MinifyImportsAndExports: le riduce a "a", "b".
  • DeadCodeElimination: rimuovi il codice inutilizzato.

È disponibile un cookbook per l'ottimizzazione con diversi suggerimenti per identificare quali dei vari indicatori sono più importanti e vale la pena provare per primi. Ad esempio, a volte l'esecuzione ripetuta di wasm-opt comprime ulteriormente l'input. In questi casi, l'esecuzione con il flag --converge continua a eseguire l'iterazione finché non viene eseguita un'ulteriore ottimizzazione e viene raggiunto un punto fisso.

Demo

Per vedere in azione i concetti introdotti in questo post, prova la demo incorporata fornendo qualsiasi input ExampleScript che ti venga in mente. Assicurati inoltre di visualizzare il codice sorgente della demo.

Conclusioni

Binaryen fornisce un potente toolkit per la compilazione di linguaggi in WebAssembly e per ottimizzare il codice risultante. La libreria JavaScript e gli strumenti a riga di comando offeriscono flessibilità e facilità d'uso. Questo post ha illustrato i principi fondamentali della compilazione Wasm, mettendo in evidenza l'efficacia e il potenziale di Binaryen per l'ottimizzazione massima. Sebbene molte delle opzioni per personalizzare le ottimizzazioni di Binaryen richiedono una conoscenza approfondita degli aspetti interni di Wasm, in genere le impostazioni predefinite sono già ottime. Buona compilazione e ottimizzazione con Binaryen.

Ringraziamenti

Questo post è stato esaminato da Alon Zakai, Thomas Lively e Rachel Andrew.