Compilación y optimización de Wasm con Binaryen

Thomas Steiner

Binaryen es una biblioteca de infraestructura de compilador y cadena de herramientas para WebAssembly, escrita en C++. Su objetivo es hacer que la compilación para WebAssembly sea intuitiva, rápida y eficaz. En esta publicación, con el ejemplo de un lenguaje de juguete sintético llamado ExampleScript, aprenderás a escribir módulos de WebAssembly en JavaScript con la API de Binaryen.js. Aprenderás los aspectos básicos de la creación de módulos, la adición de funciones al módulo y la exportación de funciones desde el módulo. Esto te brindará conocimientos sobre la mecánica general de la compilación de lenguajes de programación reales en WebAssembly. Además, aprenderás a optimizar los módulos Wasm con Binaryen.js y en la línea de comandos con wasm-opt.

Información general sobre Binaryen

Binaryen tiene una API de C intuitiva en un solo encabezado y también se puede usar desde JavaScript. Acepta entradas en formato WebAssembly, pero también acepta un gráfico de flujo de control general para los compiladores que lo prefieran.

Una representación intermedia (IR) es la estructura de datos o el código que un compilador o una máquina virtual usan de forma interna para representar el código fuente. El IR interno de Binaryen usa estructuras de datos compactas y está diseñado para la generación y optimización de código completamente paralelo, con todos los núcleos de CPU disponibles. El IR de Binaryen se compila en WebAssembly porque es un subconjunto de WebAssembly.

El optimizador de Binaryen tiene muchos pases que pueden mejorar el tamaño y la velocidad del código. El objetivo de estas optimizaciones es hacer que Binaryen sea lo suficientemente potente como para usarse como backend de compilador por sí solo. Incluye optimizaciones específicas de WebAssembly (que es posible que los compiladores de uso general no hagan), que se entienden como reducción de Wasm.

AssemblyScript como usuario de ejemplo de Binaryen

Varios proyectos usan Binaryen, como AssemblyScript, que usa Binaryen para compilar desde un lenguaje similar a TypeScript directamente a WebAssembly. Prueba el ejemplo en el campo de pruebas de AssemblyScript.

Entrada de AssemblyScript:

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

Código WebAssembly correspondiente en forma textual generado 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
 )
)

La cadena de herramientas de Binaryen

La cadena de herramientas de Binaryen ofrece una serie de herramientas útiles para los desarrolladores de JavaScript y los usuarios de línea de comandos. A continuación, se muestra un subconjunto de estas herramientas. La lista completa de las herramientas contenidas está disponible en el archivo README del proyecto.

• binaryen.js: Es una biblioteca independiente de JavaScript que expone métodos de Binaryen para crear y optimizar módulos Wasm. Para compilaciones, consulta binaryen.js en npm (o descárgalo directamente desde GitHub o unpkg).
• wasm-opt: Es la herramienta de línea de comandos que carga WebAssembly y ejecuta pases de IR de Binaryen.
• wasm-as y wasm-dis: Son herramientas de línea de comandos que ensamblan y desarman WebAssembly.
• wasm-ctor-eval: Herramienta de línea de comandos que puede ejecutar funciones (o partes de funciones) en el tiempo de compilación.
• wasm-metadce: Herramienta de línea de comandos para quitar partes de archivos Wasm de una manera flexible que depende de cómo se use el módulo.
• wasm-merge: Es una herramienta de línea de comandos que combina varios archivos Wasm en uno solo y conecta las importaciones correspondientes a las exportaciones a medida que lo hace. Es como un empaquetador para JavaScript, pero para Wasm.

Cómo compilar para WebAssembly

La compilación de un lenguaje a otro suele implicar varios pasos, los más importantes se enumeran en la siguiente lista:

• Análisis léxico: Divide el código fuente en tokens.
• Análisis sintáctico: Crea un árbol sintáctico abstracto.
• Análisis semántico: Comprueba si hay errores y aplica las reglas del idioma.
• Generación de código intermedio: Crea una representación más abstracta.
• Generación de código: Traduce al idioma de destino.
• Optimización de código específica para el objetivo: Realiza optimizaciones para el objetivo.

En el mundo de Unix, las herramientas que se usan con frecuencia para compilar son lex y yacc:

• lex (generador de analizadores léxicos): lex es una herramienta que genera analizadores léxicos, también conocidos como analizadores o escáneres. Toma un conjunto de expresiones regulares y las acciones correspondientes como entrada y genera código para un analizador léxico que reconoce patrones en el código fuente de entrada.
• yacc (Yet Another Compiler Compiler): yacc es una herramienta que genera analizadores para el análisis sintáctico. Toma una descripción gramatical formal de un lenguaje de programación como entrada y genera código para un analizador. Por lo general, los analizadores producen árboles sintácticos abstractos (AST) que representan la estructura jerárquica del código fuente.

Ejemplo práctico

Dado el alcance de esta publicación, es imposible abarcar un lenguaje de programación completo, por lo que, para simplificar, considera un lenguaje de programación sintético muy limitado y sin utilidad llamado ExampleScript que funciona expresando operaciones genéricas a través de ejemplos concretos.

• Para escribir una función add(), codificas un ejemplo de cualquier adición, por ejemplo, 2 + 3.
• Para escribir una función multiply(), escribe, por ejemplo, 6 * 12.

Según la advertencia previa, es completamente inútil, pero lo suficientemente simple como para que su analizador léxico sea una sola expresión regular: /\d+\s*[\+\-\*\/]\s*\d+\s*/.

A continuación, debe haber un analizador. En realidad, se puede crear una versión muy simplificada de un árbol de sintaxis abstracto con una expresión regular con grupos de captura nombrados: /(?<first_operand>\d+)\s*(?<operator>[\+\-\*\/])\s*(?<second_operand>\d+)/.

Los comandos de ExampleScript son uno por línea, por lo que el analizador puede procesar el código en línea dividiendo en caracteres de línea nueva. Esto es suficiente para verificar los primeros tres pasos de la lista de viñetas anterior, a saber, el análisis léxico, el análisis de sintaxis y el análisis semántico. El código de estos pasos se encuentra en la siguiente lista.

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

Generación de código intermedio

Ahora que los programas de ExampleScript pueden representarse como un árbol de sintaxis abstracto (aunque uno bastante simplificado), el siguiente paso es crear una representación intermedia abstracta. El primer paso es crear un módulo nuevo en Binaryen:

const module = new binaryen.Module();

Cada línea del árbol de sintaxis abstracta contiene un triple que consta de firstOperand, operator y secondOperand. Para cada uno de los cuatro operadores posibles en ExampleScript, es decir, +, -, * y /, se debe agregar una función nueva al módulo con el método Module#addFunction() de Binaryen. Los parámetros de los métodos Module#addFunction() son los siguientes:

• name: Un string representa el nombre de la función.
• functionType: Un Signature representa la firma de la función.
• varTypes: Un Type[] indica locales adicionales en el orden determinado.
• body: Es un Expression, el contenido de la función.

Hay algunos detalles más que desglosar, y la documentación de Binaryen puede ayudarte a navegar por el espacio, pero, en última instancia, para el operador + de ExampleScript, terminas en el método Module#i32.add() como una de las varias operaciones de números enteros disponibles. La suma requiere dos operandos, el primero y el segundo sumando. Para que se pueda llamar a la función, se debe exportar 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');

Después de procesar el árbol de sintaxis abstracta, el módulo contiene cuatro métodos, tres de los cuales funcionan con números enteros, a saber, add() basado en Module#i32.add(), subtract() basado en Module#i32.sub(), multiply() basado en Module#i32.mul() y el valor atípico divide() basado en Module#f64.div(), ya que ExampleScript también funciona con resultados de punto flotante.

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

Si trabajas con bases de código reales, a veces habrá código inactivo al que nunca se le llama. Para introducir artificialmente código muerto (que se optimizará y eliminará en un paso posterior) en el ejemplo en ejecución de la compilación de ExampleScript a Wasm, agregar una función no exportada hace el trabajo.

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

El compilador ya está casi listo. No es estrictamente necesario, pero es una práctica recomendada validar el módulo con el método Module#validate().

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

Cómo obtener el código Wasm resultante

Para obtener el código Wasm resultante, existen dos métodos en Binaryen para obtener la representación textual como un archivo .wat en expresión S como un formato legible por humanos y la representación binaria como un archivo .wasm que se puede ejecutar directamente en el navegador. El código binario se puede ejecutar directamente en el navegador. Para comprobar que funcionó, puede ser útil registrar las exportaciones.

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 continuación, se muestra la representación textual completa de un programa de ExampleScript con las cuatro operaciones. Observa que el código muerto sigue allí, pero no está expuesto según la captura de pantalla de 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)
  )
 )
)

Cómo optimizar WebAssembly

Binaryen ofrece dos formas de optimizar el código Wasm. Uno en Binaryen.js y uno para la línea de comandos. El primero aplica el conjunto estándar de reglas de optimización de forma predeterminada y te permite establecer el nivel de optimización y reducción. El segundo, de forma predeterminada, no usa reglas, sino que permite una personalización completa, lo que significa que, con suficiente experimentación, puedes adaptar la configuración para obtener resultados óptimos en función de tu código.

Cómo optimizar con Binaryen.js

La forma más directa de optimizar un módulo Wasm con Binaryen es llamar directamente al método Module#optimize() de Binaryen.js y, de manera opcional, configurar el nivel de optimización y reducción.

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

De esta manera, se quita el código muerto que se introdujo de forma artificial antes, por lo que la representación textual de la versión de Wasm del ejemplo de juguete ExampleScript ya no lo contiene. También observa cómo los pasos de optimización SimplifyLocals (optimizaciones misceláneas relacionadas con los locales) y Vacuum (quita el código claramente innecesario) quitan los pares local.set/get, y RemoveUnusedBrs quita return (quita las pausas de las ubicaciones que no son necesarias).

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

Hay muchos pases de optimización, y Module#optimize() usa los conjuntos predeterminados de los niveles de optimización y reducción. Para personalizarlo por completo, debes usar la herramienta de línea de comandos wasm-opt.

Realiza optimizaciones con la herramienta de línea de comandos wasm-opt

Para personalizar por completo los pases que se usarán, Binaryen incluye la herramienta de línea de comandos wasm-opt. Para obtener una lista completa de las opciones de optimización posibles, consulta el mensaje de ayuda de la herramienta. Es probable que la herramienta wasm-opt sea la más popular, y varias cadenas de herramientas de compiladores la usan para optimizar el código de Wasm, incluidos Emscripten, J2CL, Kotlin/Wasm, dart2wasm y wasm-pack, entre otros.

wasm-opt --help

Para que tengas una idea de los pases, aquí tienes un extracto de algunos de los que se pueden comprender sin conocimientos de expertos:

• CodeFolding: Evita el código duplicado combinándolo (por ejemplo, si dos grupos if tienen algunas instrucciones compartidas al final).
• DeadArgumentElimination: Pase de optimización del tiempo de vinculación para quitar argumentos a una función si siempre se llama con las mismas constantes.
• MinifyImportsAndExports: Los reduce a "a", "b".
• DeadCodeElimination: Quita el código no alcanzado.

Puedes encontrar una guía de soluciones de optimización disponible con varias sugerencias para identificar cuáles de las marcas son más importantes y vale la pena probarlas primero. Por ejemplo, a veces, ejecutar wasm-opt repetidamente reduce aún más la entrada. En esos casos, la ejecución con la marca --converge sigue iterando hasta que no se produce más optimización y se alcanza un punto fijo.

Demostración

Para ver en acción los conceptos que se presentan en esta publicación, juega con la demo integrada y proporciónale cualquier entrada de ExampleScript que se te ocurra. Además, asegúrate de ver el código fuente de la demostración.

Conclusiones

Binaryen proporciona un kit de herramientas potente para compilar lenguajes en WebAssembly y optimizar el código resultante. Su biblioteca JavaScript y herramientas de línea de comandos ofrecen flexibilidad y facilidad de uso. En esta publicación, se demostraron los principios básicos de la recopilación de Wasm y se destacó la eficacia y el potencial de Binaryen para la optimización máxima. Si bien muchas de las opciones para personalizar las optimizaciones de Binaryen requieren un conocimiento profundo de las funciones internas de Wasm, por lo general, la configuración predeterminada ya funciona muy bien. Por lo tanto, te deseamos complicar y optimizar con Binaryen.

Agradecimientos

Alon Zakai, Thomas Lively y Rachel Andrew revisaron esta publicación.