Como compilar e otimizar o Wasm com Binaryen

O Binaryen é uma biblioteca de infraestrutura de compilador e toolchain para WebAssembly, escrita em C++. O objetivo é tornar a compilação para WebAssembly intuitiva, rápida e eficaz. Neste post, usando o exemplo de uma linguagem sintética chamada ExampleScript, aprenda a escrever módulos WebAssembly em JavaScript usando a API Binaryen.js. Você vai aprender os conceitos básicos de criação de módulos, adição de funções a eles e exportação de funções. Isso lhe dará conhecimento sobre a mecânica geral da compilação de linguagens de programação reais para o WebAssembly. Além disso, você vai aprender a otimizar módulos Wasm com o Binaryen.js e na linha de comando com wasm-opt.

Informações sobre o Binaryen

O Binaryen tem uma API C intuitiva em um único cabeçalho e também pode ser usado em JavaScript. Ele aceita entrada em formato WebAssembly, mas também aceita um gráfico de fluxo de controle geral para compiladores que preferem isso.

Uma representação intermediária (IR, na sigla em inglês) é a estrutura de dados ou o código usado internamente por um compilador ou uma máquina virtual para representar o código-fonte. A IR interna do Binaryen usa estruturas de dados compactas e foi projetada para geração e otimização de código completamente paralelas, usando todos os núcleos de CPU disponíveis. O IR do Binaryen é compilado para o WebAssembly por ser um subconjunto dele.

O otimizador do Binaryen tem muitas passagens que podem melhorar o tamanho e a velocidade do código. O objetivo dessas otimizações é tornar o Binaryen poderoso o suficiente para ser usado como um back-end de compilador por conta própria. Ele inclui otimizações específicas da WebAssembly (que os compiladores de uso geral podem não fazer), que podem ser consideradas como minimização do Wasm.

AssemblyScript como um exemplo de usuário do Binaryen

O Binaryen é usado por vários projetos, por exemplo, AssemblyScript, que usa o Binaryen para compilar de uma linguagem semelhante ao TypeScript diretamente para o WebAssembly. Teste o exemplo no playground do AssemblyScript.

Entrada do AssemblyScript:

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

Código WebAssembly correspondente em formato de texto gerado por 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
 )
)

O playground do AssemblyScript mostrando o código da WebAssembly gerado com base no exemplo anterior.

O conjunto de ferramentas Binaryen

A cadeia de ferramentas Binaryen oferece várias ferramentas úteis para desenvolvedores JavaScript e usuários de linha de comando. Um subconjunto dessas ferramentas está listado abaixo. A lista completa de ferramentas contidas está disponível no arquivo README do projeto.

  • binaryen.js: uma biblioteca JavaScript independente que expõe métodos Binaryen para criar e otimizar módulos Wasm. Para builds, consulte binaryen.js no npm (ou faça o download diretamente do GitHub ou unpkg).
  • wasm-opt: ferramenta de linha de comando que carrega o WebAssembly e executa transmissões de IR Binaryen nele.
  • wasm-as e wasm-dis: ferramentas de linha de comando que montam e desmontam o WebAssembly.
  • wasm-ctor-eval: ferramenta de linha de comando que pode executar funções (ou partes delas) no momento da compilação.
  • wasm-metadce: ferramenta de linha de comando para remover partes de arquivos Wasm de maneira flexível, dependendo da forma como o módulo é usado.
  • wasm-merge: ferramenta de linha de comando que mescla vários arquivos Wasm em um único arquivo, conectando as importações correspondentes às exportações. É como um bundler para JavaScript, mas para Wasm.

Como compilar no WebAssembly

A compilação de uma linguagem para outra geralmente envolve várias etapas. As mais importantes estão listadas na lista abaixo:

  • Análise léxica:divida o código-fonte em tokens.
  • Análise sintática: crie uma árvore de sintaxe abstrata.
  • Análise semântica: verifique se há erros e aplique as regras do idioma.
  • Geração de código intermediária: crie uma representação mais abstrata.
  • Geração de código: traduza para o idioma de destino.
  • Otimização de código específica para o público-alvo: otimize para o público-alvo.

No mundo do Unix, as ferramentas de compilação mais usadas são lex e yacc:

  • lex (gerador de analisador lexical): lex é uma ferramenta que gera analisadores lexicais, também conhecidos como lexers ou scanners. Ele usa um conjunto de expressões regulares e ações correspondentes como entrada e gera código para um analisador léxico que reconhece padrões no código-fonte de entrada.
  • yacc (Yet Another Compiler Compiler): yacc é uma ferramenta que gera analisadores para análise sintática. Ele usa uma descrição gramatical formal de uma linguagem de programação como entrada e gera código para um analisador. Os analisadores normalmente produzem árvores de sintaxe abstratas (ASTs, na sigla em inglês) que representam a estrutura hierárquica do código-fonte.

Um exemplo prático

Considerando o escopo desta postagem, é impossível abordar uma linguagem de programação completa. Portanto, para simplificar, considere uma linguagem de programação sintética muito limitada e inútil chamada ExampleScript, que funciona expressando operações genéricas por meio de exemplos concretos.

  • Para escrever uma função add(), você programa um exemplo de qualquer adição, por exemplo, 2 + 3.
  • Para criar uma função multiply(), escreva 6 * 12, por exemplo.

De acordo com o aviso prévio, completamente inútil, mas simples o suficiente para que o analisador lexical seja uma única expressão regular: /\d+\s*[\+\-\*\/]\s*\d+\s*/.

Em seguida, é necessário ter um analisador. Na verdade, uma versão muito simplificada de uma árvore de sintaxe abstrata pode ser criada usando uma expressão regular com grupos de captura nomeados: /(?<first_operand>\d+)\s*(?<operator>[\+\-\*\/])\s*(?<second_operand>\d+)/.

Os comandos ExampleScript são um por linha, portanto, o analisador pode processar o código por linha dividindo em caracteres de nova linha. Isso é suficiente para verificar as três primeiras etapas da lista de marcadores anterior, ou seja, análise lexical, análise sintática e análise semântica. O código dessas etapas está na listagem a seguir.

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

Geração de código intermediário

Agora que os programas do ExampleScript podem ser representados como uma árvore de sintaxe abstrata (embora bastante simplificada), a próxima etapa é criar uma representação intermediária abstrata. A primeira etapa é criar um novo módulo no Binaryen:

const module = new binaryen.Module();

Cada linha da árvore de sintaxe abstrata contém um triplo que consiste em firstOperand, operator e secondOperand. Para cada um dos quatro operadores possíveis no ExampleScript, ou seja, +, -, *, /, uma nova função precisa ser adicionada ao módulo com o método Module#addFunction() do Binaryen. Os parâmetros dos métodos Module#addFunction() são os seguintes:

  • name: um string, representa o nome da função.
  • functionType: um Signature, representa a assinatura da função.
  • varTypes: um Type[] indica outros locais na ordem.
  • body: um Expression, o conteúdo da função.

Há mais alguns detalhes a serem separados e detalhados, e a documentação do Binaryen (link em inglês) pode ajudar a navegar pelo espaço, mas, eventualmente, para o operador + do ExampleScript, você acaba no método Module#i32.add() como uma das várias operações de números inteiros disponíveis. A adição requer dois operandos, o primeiro e o segundo somatório. Para que a função possa ser chamada, ela precisa ser exportada com 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');

Depois de processar a árvore de sintaxe abstrata, o módulo contém quatro métodos, três deles trabalham com números inteiros, ou seja, add() com base em Module#i32.add(), subtract() com base em Module#i32.sub(), multiply() com base em Module#i32.mul() e o valor discrepante divide() com base em Module#f64.div(), porque o ExampleScript também funciona com resultados de ponto flutuante.

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 você lidar com bases de código reais, às vezes haverá códigos mortos que nunca serão chamados. Para introduzir artificialmente o código inativo (que será otimizado e eliminado em uma etapa posterior) no exemplo em execução da compilação do ExampleScript no Wasm, adicionar uma função não exportada faz o trabalho.

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

O compilador está quase pronto agora. Não é estritamente necessário, mas é uma prática recomendada validar o módulo com o método Module#validate().

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

Como conseguir o código Wasm resultante

Para obter o código Wasm resultante, dois métodos existem no Binaryen para receber a representação textual como um arquivo .wat em expressão S em um formato legível por humanos e a representação binária como um arquivo .wasm que pode ser executado diretamente no navegador. O código binário pode ser executado diretamente no navegador. Para ver se funcionou, registrar as exportações pode ajudar.

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

A representação textual completa de um programa ExampleScript com as quatro operações está listada abaixo. Observe como o código morto ainda está lá, mas não está exposto de acordo com a captura de tela do 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)
  )
 )
)

Captura de tela do console do DevTools das exportações do módulo da WebAssembly mostrando quatro funções: adição, divisão, multiplicação e subtração (mas não o código morto não exposto).

Como otimizar o WebAssembly

O Binaryen oferece duas maneiras de otimizar o código Wasm. Uma no Binaryen.js e outra para a linha de comando. A primeira aplica o conjunto padrão de regras de otimização por padrão e permite definir o nível de otimização e redução. A segunda, por padrão, não usa regras, mas permite a personalização completa. Isso significa que, com experimentos suficientes, é possível adaptar as configurações para resultados ideais com base no código.

Como otimizar com Binaryen.js

A maneira mais simples de otimizar um módulo Wasm com o Binaryen é chamar diretamente o método Module#optimize() do Binaryen.js e, opcionalmente, definir o nível de otimização e redução.

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

Isso remove o código inativo que foi introduzido artificialmente antes, de modo que a representação textual da versão Wasm do exemplo de brinquedo ExampleScript não o contenha mais. Observe também como os pares local.set/get são removidos pelas etapas de otimização SimplifyLocals (otimizações relacionadas a locais diversos) e Vacuum (remove o código obviamente desnecessário), e o return é removido por RemoveUnusedBrs (remove quebras de locais que não são necessários).

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

Há muitas passagens de otimização, e Module#optimize() usa os conjuntos padrão de níveis de otimização e redução específicos. Para uma personalização completa, use a ferramenta de linha de comando wasm-opt.

Como otimizar com a ferramenta de linha de comando wasm-opt

Para personalizar totalmente os cartões a serem usados, o Binaryen inclui a ferramenta de linha de comando wasm-opt. Para conferir uma lista completa das possíveis opções de otimização, consulte a mensagem de ajuda da ferramenta. A ferramenta wasm-opt provavelmente é a mais conhecida das ferramentas e é usada por vários conjuntos de ferramentas de compilador para otimizar o código Wasm, incluindo Emscripten, J2CL, Kotlin/Wasm, dart2wasm, Wasm-pack e outros.

wasm-opt --help

Para você ter uma ideia dos cartões, confira um trecho de alguns que podem ser compreendidos sem conhecimento especializado:

  • CodeFolding: evita a duplicação de código mesclando-o (por exemplo, se dois ramos if tiverem algumas instruções compartilhadas no final).
  • DeadArgumentElimination: passagem de otimização de tempo de vinculação para remover argumentos de uma função se ela for sempre chamada com as mesmas constantes.
  • MinifyImportsAndExports: minimiza para "a", "b".
  • DeadCodeElimination: remova o código inoperante.

Há um manual de otimização disponível com várias dicas para identificar quais das diversas sinalizações são mais importantes e vale a pena tentar primeiro. Por exemplo, às vezes, executar wasm-opt repetidamente reduz ainda mais a entrada. Nesses casos, a execução com a flag --converge continua iterando até que não haja mais otimização e um ponto fixo seja atingido.

Demonstração

Para conferir os conceitos apresentados nesta postagem em ação, teste a demonstração embutida fornecendo qualquer entrada de ExampleScript que você conseguir pensar. Além disso, consulte o código-fonte da demonstração.

Conclusões

O Binaryen oferece um kit de ferramentas avançado para compilar linguagens para o WebAssembly e otimizar o código resultante. A biblioteca JavaScript e as ferramentas de linha de comando oferecem flexibilidade e facilidade de uso. Esta postagem demonstrou os princípios básicos da compilação do Wasm, destacando a eficácia e o potencial do Binaryen para otimização máxima. Embora muitas das opções de personalização das otimizações do Binaryen exijam um conhecimento profundo sobre os recursos internos do Wasm, geralmente as configurações padrão já funcionam muito bem. Bom trabalho compilando e otimizando com o Binaryen!

Agradecimentos

Esta postagem foi revisada por Alon Zakai, Thomas Lively e Rachel Andrew.