Compilazione e ottimizzazione di Wasm con Binaryen

Thomas Steiner

Binaryen è una libreria di infrastruttura di compilazione e toolchain per WebAssembly, scritta in C++. Lo scopo è rendere la compilazione di WebAssembly intuitiva, veloce ed efficace. In questo post, utilizzando l'esempio di un linguaggio giocattolo sintetico chiamato ExampleScript, scopri come scrivere moduli WebAssembly in JavaScript utilizzando l'API Binaryen.js. Tratteremo le nozioni di base sulla creazione di moduli, sull'aggiunta di funzioni al modulo e sulle funzioni di esportazione. In questo modo, potrai conoscere i meccanismi generali per compilare i linguaggi di programmazione effettivi in WebAssembly. Inoltre, scoprirai come ottimizzare i moduli Wasm sia con Binaryen.js che sulla riga di comando con wasm-opt.

Informazioni su Binaryen

Binaryen ha un'API C intuitiva in un'unica intestazione e può anche essere utilizzata da JavaScript. Accetta input in modulo WebAssembly, ma accetta anche un grafico del flusso di controllo generale per i compilatori che lo preferiscono.

Una rappresentazione intermedia (IR) è la struttura dei dati o il codice utilizzati internamente da un compilatore o da una macchina virtuale per rappresentare il codice sorgente. La tecnologia IR interna di Binaryen utilizza strutture di dati compatte ed è progettata per la generazione e l'ottimizzazione di codice completamente parallele, utilizzando tutti i core della CPU disponibili. La classe IR di Binaryen viene compilata in WebAssembly perché è un sottoinsieme di WebAssembly.

L'ottimizzatore di Binaryen ha molti passaggi che possono migliorare dimensioni e velocità del codice. Queste ottimizzazioni hanno lo scopo di rendere Binaryen abbastanza potente da essere usato da solo come backend del compilatore. Include ottimizzazioni specifiche per WebAssembly (che potrebbero non essere utili ai compilatori generici), che puoi pensare come minimizzazione Wasm.

AssemblyScript come utente di esempio di Binaryen

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

Input AssemblyScript:

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

Codice WebAssembly corrispondente in formato testuale 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 parco giochi 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 di moduli Wasm. Per le build, consulta binaryen.js su npm (o scaricalo direttamente da GitHub o unpkg).
  • wasm-opt: lo strumento a riga di comando che carica WebAssembly ed esegue i passaggi di Binaryen IR.
  • wasm-as e wasm-dis: strumenti a riga di comando che assemblano e disassemblano WebAssembly.
  • wasm-ctor-eval: strumento a riga di comando in grado di eseguire funzioni (o parti di funzioni) in fase di compilazione.
  • wasm-metadce: strumento a riga di comando per rimuovere parti dei file Wasm in un modo flessibile a seconda di come viene utilizzato il modulo.
  • wasm-merge: strumento a riga di comando che unisce più file Wasm in un unico file, connettendo le importazioni corrispondenti alle esportazioni nel tempo stesso. Come un bundler per JavaScript, ma per Wasm.

Compilazione in WebAssembly

La compilazione di una lingua per un'altra richiede in genere diversi passaggi, i più importanti sono elencati nell'elenco seguente:

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

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

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

Un esempio corretto

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 attraverso esempi concreti.

  • Per scrivere una funzione add(), crei il codice di un esempio di aggiunta qualsiasi, ad esempio 2 + 3.
  • Per scrivere una funzione multiply(), puoi scrivere, ad esempio, 6 * 12.

Come indicato nel pre-avviso, è completamente inutile, ma abbastanza semplice da consentire al suo analizzatore lessico di essere una singola espressione regolare: /\d+\s*[\+\-\*\/]\s*\d+\s*/.

Deve poi essere presente un analizzatore sintattico. In realtà, puoi creare una versione molto semplificata di un albero della sintassi astratto utilizzando un'espressione regolare con gruppi di acquisizione con nome: /(?<first_operand>\d+)\s*(?<operator>[\+\-\*\/])\s*(?<second_operand>\d+)/.

I comandi exampleScript sono uno per riga, quindi il parser può elaborare il codice a riga di codice suddividendolo in caratteri di nuova riga. Ciò è sufficiente per controllare i primi tre passaggi dell'elenco puntato, ovvero analisi lessicale, analisi sintetica e analisi semantica. Il codice per questi passaggi è disponibile nell'elenco seguente.

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 intermedia

Ora che i programmi ExampleScript possono essere rappresentati come un albero della sintassi astratto (sebbene piuttosto semplificato), il passaggio successivo è 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 combinazione di firstOperand, operator e secondOperand. Per ognuno dei quattro possibili operatori in ExampleScript, ovvero +, -, *, /, è necessario aggiungere una nuova funzione al modulo 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: Type[], indica ulteriori informazioni locali, nell'ordine specificato.
  • body: un Expression, i contenuti della funzione.

Ci sono ulteriori dettagli da esaminare e scomporre e la documentazione di Binaryen può aiutarti a esplorare lo spazio, ma alla fine, per l'operatore + di ExampleScript, ti ritroverai al metodo Module#i32.add() come una delle diverse operazioni sui numeri interi disponibili. L'addizione richiede due operandi, il primo e il secondo sommando. 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 della sintassi astratta, il modulo contiene quattro metodi, tre che funzionano con numeri interi, ovvero add() che si basa su Module#i32.add(), subtract() in base a Module#i32.sub(), multiply() in base a 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 ci si occupa di codebase reali, a volte ci sarà codice non valido che non viene mai chiamato. Per introdurre artificialmente codice non valido (che verrà ottimizzato ed eliminato in un passaggio successivo) nell'esempio in esecuzione della compilazione di ExampleScript in Wasm, l'aggiunta di una funzione non esportata esegue il job.

// 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 è sicuramente una buona pratica per 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 S-expression come 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 tutto abbia funzionato, il logging delle esportazioni può aiutarti.

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

Di seguito è riportata la rappresentazione testuale completa per un programma ExampleScript con tutte e quattro le operazioni. Tieni presente che il codice non valido è ancora presente, ma non è esposto 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, moltiplica e sottrae (ma non il codice non esposto).

Ottimizzazione di WebAssembly

Binaryen offre due modi per ottimizzare il codice Wasm. uno in Binaryen.js e l'altro per la riga di comando. La prima applica l'insieme standard di regole di ottimizzazione per impostazione predefinita e consente di impostare il livello di ottimizzazione e di riduzione. La seconda, per impostazione predefinita, non utilizza regole, ma consente una personalizzazione completa. Ciò significa che, con una sperimentazione sufficiente, puoi personalizzare le impostazioni per ottenere risultati ottimali in base al 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 di riduzione.

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

Questa operazione rimuove il codice non valido introdotto artificialmente in precedenza, pertanto la rappresentazione testuale della versione Wasm dell'esempio di giocattolo di esempioScript non lo contiene più. Nota anche come le coppie local.set/get vengono rimosse dai passaggi di ottimizzazione SimplifyLocals (ottimizzazioni varie correlate a utenti locali) e Vacuum (rimuove il codice ovviamente non necessario) e return viene rimosso da RemoveUnusedBrs (rimuove le interruzioni dalle località che non sono 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 molte passate per l'ottimizzazione e Module#optimize() utilizza gli insiemi predefiniti specifici 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 dei pass da utilizzare, Binaryen include lo strumento a riga di comando wasm-opt. Per ottenere un elenco completo delle possibili opzioni di ottimizzazione, consulta il messaggio di assistenza dello strumento. Lo strumento wasm-opt è probabilmente il più popolare ed è utilizzato da diverse toolchain di compilazione 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 comprensibili senza alcuna conoscenza di esperti:

  • CodeFolding: impedisce la duplicazione del codice unendolo (ad esempio, se due gruppi if hanno istruzioni condivise alla fine).
  • DeadArgumentElimination: l'ottimizzazione del tempo di collegamento è passata per rimuovere argomenti a una funzione se viene sempre chiamata con le stesse costanti.
  • MinifyImportsAndExports: la minimizza a "a", "b".
  • DeadCodeElimination: rimuovi il codice non valido.

È disponibile un libro di ricette per l'ottimizzazione con diversi suggerimenti per identificare i flag più importanti e che vale la pena provare per primi. Ad esempio, a volte l'esecuzione di wasm-opt ripetutamente più volte riduce ulteriormente l'input. In questi casi, l'esecuzione con il flag --converge continua a ripetere fino a quando non viene eseguita un'ulteriore ottimizzazione e non viene raggiunto un punto fisso.

Demo

Per vedere la pratica dei concetti presentati in questo post, provate con la demo incorporata, fornendovi qualsiasi input di exampleScript che vi 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 l'ottimizzazione del codice risultante. La libreria JavaScript e gli strumenti a riga di comando offrono flessibilità e facilità d'uso. Questo post ha dimostrato i principi fondamentali della compilazione Wasm, evidenziando l'efficacia e il potenziale di ottimizzazione di Binaryen. Sebbene molte delle opzioni per personalizzare le ottimizzazioni di Binaryen richiedano una conoscenza approfondita degli elementi interni di Wasm, in genere le impostazioni predefinite sono già efficaci. Buon lavoro con Binaryen per la compilazione e l'ottimizzazione.

Ringraziamenti

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