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 en WebAssembly sea intuitiva, rápida y eficaz. En esta publicación, aprenderás a escribir módulos de WebAssembly en JavaScript con la API de Binaryen.js a través del ejemplo de un lenguaje de juguete sintético llamado ExampleScript. Aprenderás los conceptos básicos de la creación de módulos, la adición de funciones a los módulos y la exportación de funciones desde los módulos. Esto te brindará conocimientos sobre los mecanismos generales de compilación de lenguajes de programación reales en WebAssembly. Además, aprenderás a optimizar los módulos de 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 prefieren ese formato.

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 optimización y la generación de código completamente paralelas, 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. Estas optimizaciones tienen como objetivo hacer que Binaryen sea lo suficientemente potente como para usarse como backend del compilador por sí solo. Incluye optimizaciones específicas de WebAssembly (que los compiladores de uso general podrían no realizar), que puedes considerar como una minificación de Wasm.

AssemblyScript como ejemplo de usuario de Binaryen

Binaryen se usa en varios proyectos, por ejemplo, AssemblyScript, que usa Binaryen para compilar desde un lenguaje similar a TypeScript directamente a WebAssembly. Prueba el ejemplo en el playground de AssemblyScript.

Entrada de AssemblyScript:

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

Código WebAssembly correspondiente en formato de texto 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
 )
)

El Playground de AssemblyScript muestra el código de WebAssembly generado según el ejemplo anterior.

La cadena de herramientas de Binaryen

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

  • binaryen.js: Biblioteca de JavaScript independiente que expone métodos de Binaryen para crear y optimizar módulos de Wasm. Para las compilaciones, consulta binaryen.js en npm (o descárgalo directamente desde GitHub o unpkg).
  • wasm-opt: Herramienta de línea de comandos que carga WebAssembly y ejecuta pases de IR de Binaryen en él.
  • wasm-as y wasm-dis: Herramientas de línea de comandos que ensamblan y desensamblan WebAssembly.
  • wasm-ctor-eval: Herramienta de línea de comandos que puede ejecutar funciones (o partes de funciones) en 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 usa el módulo.
  • wasm-merge: Es una herramienta de línea de comandos que combina varios archivos .wasm en un solo archivo y conecta las importaciones correspondientes a las exportaciones a medida que lo hace. Es como un bundler para JavaScript, pero para Wasm.

Compilación en WebAssembly

La compilación de un idioma a otro suele implicar varios pasos, los más importantes se enumeran a continuación:

  • Análisis léxico: Divide el código fuente en tokens.
  • Análisis sintáctico: Crea un árbol de sintaxis abstracta.
  • 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 lenguaje objetivo.
  • Optimización de código específica para el objetivo: Optimiza el código 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 lexers o scanners. Toma un conjunto de expresiones regulares y 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 de sintaxis. Toma como entrada una descripción formal de la gramática de un lenguaje de programación y genera código para un analizador. Por lo general, los analizadores producen árboles de sintaxis abstracta (AST) que representan la estructura jerárquica del código fuente.

Un ejemplo sobre el que se trabajó

Dado el alcance de esta publicación, es imposible abarcar un lenguaje de programación completo, por lo que, en aras de la simplicidad, considera un lenguaje de programación sintético muy limitado e inútil llamado ExampleScript que funciona expresando operaciones genéricas a través de ejemplos concretos.

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

Como se indicó en la advertencia previa, es completamente inútil, pero lo suficientemente simple 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 abstracta con una expresión regular que incluya grupos de captura con nombre: /(?<first_operand>\d+)\s*(?<operator>[\+\-\*\/])\s*(?<second_operand>\d+)/.

Los comandos de ExampleScript se escriben uno por línea, por lo que el analizador puede procesar el código línea por línea dividiendo los caracteres de nueva línea. Esto es suficiente para verificar los tres primeros pasos de la lista anterior, es decir, el análisis léxico, el análisis sintáctico y el análisis semántico. El código para 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 se pueden representar como un árbol de sintaxis abstracta (aunque 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 una tripleta que consta de firstOperand, operator y secondOperand. Para cada uno de los cuatro operadores posibles en ExampleScript, es decir, +, -, * y /, se debe agregar una nueva función 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 que representa el nombre de la función.
  • functionType: Un Signature que representa la firma de la función.
  • varTypes: Es un Type[] que indica configuraciones regionales adicionales, en el orden determinado.
  • body: Un Expression, el contenido de la función.

Hay algunos detalles más que analizar y desglosar, y la documentación de Binaryen puede ayudarte a navegar por el espacio, pero, finalmente, 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 primer sumando y el segundo. Para que la función sea realmente invocable, debe exportarse 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 que funcionan con números enteros, es decir, 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 que nunca se llama. Para introducir artificialmente código no utilizado (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 es suficiente.

// 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 sin duda es una buena práctica 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 S-expression 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 verificar 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 cómo el código inactivo sigue allí, pero no se expone 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)
  )
 )
)

Captura de pantalla de la consola de Herramientas para desarrolladores de las exportaciones del módulo de WebAssembly que muestra cuatro funciones: sumar, dividir, multiplicar y restar (pero no el código inactivo no expuesto).

Cómo optimizar WebAssembly

Binaryen ofrece dos formas de optimizar el código Wasm. Una en Binaryen.js y otra 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, mientras que el segundo no usa ninguna regla de forma predeterminada, 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.

Optimización con Binaryen.js

La forma más sencilla de optimizar un módulo de Wasm con Binaryen es llamar directamente al método Module#optimize() de Binaryen.js y, de manera opcional, establecer 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 inactivo que se introdujo artificialmente 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 pares local.set/get se quitan con los pasos de optimización SimplifyLocals (varias optimizaciones relacionadas con la configuración regional) y Vacuum (quita el código obviamente innecesario), y cómo RemoveUnusedBrs quita return (quita los saltos de las ubicaciones que no son necesarios).

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

Existen muchos pases de optimización, y Module#optimize() usa los conjuntos predeterminados de niveles de optimización y reducción particulares. Para una personalización completa, debes usar la herramienta de línea de comandos wasm-opt.

Cómo realizar 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 posibles opciones de optimización, consulta el mensaje de ayuda de la herramienta. La herramienta wasm-opt es probablemente la más popular de todas y la utilizan varias cadenas de herramientas del compilador para optimizar el código de Wasm, incluidas Emscripten, J2CL, Kotlin/Wasm, dart2wasm, wasm-pack y otras.

wasm-opt --help

Para que te hagas una idea de los pases, aquí tienes un fragmento de algunos que son comprensibles sin conocimientos especializados:

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

Hay un recetario de optimización disponible con varias sugerencias para identificar qué marcas son más importantes y vale la pena probar primero. Por ejemplo, a veces, ejecutar wasm-opt una y otra vez reduce aún más la entrada. En estos casos, ejecutar con la marca --converge sigue iterando hasta que no se produzca ninguna otra optimización y se alcance un punto fijo.

Demostración

Para ver los conceptos que se presentan en esta publicación en acción, prueba la demostración integrada y proporciona cualquier entrada de ExampleScript que se te ocurra. También asegúrate de ver el código fuente de la demostración.

Conclusiones

Binaryen proporciona un potente kit de herramientas para compilar lenguajes en WebAssembly y optimizar el código resultante. Su biblioteca de JavaScript y sus herramientas de línea de comandos ofrecen flexibilidad y facilidad de uso. En esta publicación, se demostraron los principios básicos de la compilación de Wasm, y se destacó la eficacia y el potencial de Binaryen para lograr una optimización máxima. Si bien muchas de las opciones para personalizar las optimizaciones de Binaryen requieren un conocimiento profundo sobre el funcionamiento interno de Wasm, por lo general, la configuración predeterminada ya funciona muy bien. Con eso, ¡feliz compilación y optimización con Binaryen!

Agradecimientos

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