Compilación y optimización de Wasm con Binaryen

Thomas Steiner

Binaryen es una biblioteca de infraestructura de cadenas de herramientas y compiladores para WebAssembly, escrita en C++. Su objetivo es que la compilación en WebAssembly sea intuitiva, rápida y eficaz. En esta entrada, 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. Abordarás los conceptos 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 módulos de Wasm con Binaryen.js y en la línea de comandos con wasm-opt.

Antecedentes de Binaryen

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

Una representación intermedia (IR) es la estructura de datos o el código que un compilador o una máquina virtual usan internamente para representar el código fuente. La IR interna de Binaryen usa estructuras de datos compactas y está diseñada para la generación y optimización de código completamente paralelo, con todos los núcleos de CPU disponibles. La IR de Binaryen se compila en WebAssembly debido a que 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 que Binaryen sea lo suficientemente potente como para usarlo como backend de compilador por su cuenta. Incluye optimizaciones específicas de WebAssembly (que los compiladores de uso general podrían no hacer), que puedes considerar como reducción de Wasm.

AssemblyScript como usuario de ejemplo de Binaryen

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

Entrada de AssemblyScript:

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

Código de WebAssembly correspondiente en formato 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 zona de pruebas de AssemblyScript que 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 una serie de herramientas útiles para desarrolladores de JavaScript y usuarios de la línea de comandos. A continuación, se muestra un subconjunto de estas herramientas. La lista completa de herramientas contenidas está disponible en el archivo README del proyecto.

  • binaryen.js: Es una biblioteca de JavaScript independiente que expone los métodos de Binaryen para crear y optimizar módulos de Wasm. Para 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: Es una 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 los archivos Wasm de manera flexible que depende de cómo se use el módulo.
  • wasm-merge: Herramienta de línea de comandos que combina varios archivos de Wasm en un solo archivo y conecta las importaciones correspondientes a las exportaciones a medida que lo hace. Es como un agrupador para JavaScript, pero para Wasm.

Compila en WebAssembly

Por lo general, la compilación de un lenguaje a otro implica 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 de sintaxis abstracto.
  • Análisis semántico: Verifica si hay errores y aplica reglas de lenguaje.
  • 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 del código específico del objetivo: Realiza optimizaciones en función del objetivo.

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

  • lex (Generador de analizador léxico): lex es una herramienta que genera analizadores léxicos, también conocidos como lexers 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 de sintaxis abstractos (AST) que representan la estructura jerárquica del código fuente.

Un ejemplo trabajado

Dado el alcance de esta publicación, es imposible abordar un lenguaje de programación completo, por lo que, para simplificar, 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(), codificas un ejemplo de cualquier adición, por ejemplo, 2 + 3.
  • Para escribir una función multiply(), debes escribir, 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 mediante una expresión regular con grupos de captura con nombre: /(?<first_operand>\d+)\s*(?<operator>[\+\-\*\/])\s*(?<second_operand>\d+)/.

Los comandos de ExampleScript son de uno por línea, por lo que el analizador puede procesar el código a nivel de línea dividiendo en caracteres de línea nueva. Esto es suficiente para verificar los primeros tres pasos de la lista de viñetas anteriores, es decir, el análisis léxico, el análisis de sintaxis 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 abstracto (aunque sea 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 abstracto 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: Es un string que representa el nombre de la función.
  • functionType: Un Signature, representa la firma de la función.
  • varTypes: Un Type[], que indica los locales adicionales, en el orden dado
  • body: Es un Expression, el contenido de la función.

Hay algunos detalles más para relajarse, y la documentación de Binaryen puede ayudarte a navegar por el espacio, pero, con el tiempo, para el operador + de ExampleScript, terminarás 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. Para que la función realmente pueda llamarse, 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 abstracto, 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 muerto al que nunca se llamará. Para ingresar artificialmente un código muerto (que se optimizará y eliminará en un paso posterior) en el ejemplo actual 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 está casi listo. No es estrictamente necesario, pero te recomendamos que valides 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 y la representación binaria como un archivo .wasm que puede ejecutarse directamente en el navegador. El código binario se puede ejecutar directamente en el navegador. Para comprobar que funcionó, registrar las exportaciones puede ser útil.

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 representación textual completa para un programa ExampleScript con las cuatro operaciones se enumera a continuación. Observa que el código muerto 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 que muestra las exportaciones del módulo de WebAssembly en la que se muestran cuatro funciones: sumar, dividir, multiplicar y restar (pero no el código no expuesto).

Optimiza WebAssembly

Binaryen ofrece dos formas de optimizar el código de Wasm. una en Binaryen.js y otra en 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 de reducción. El segundo no usa reglas de forma predeterminada, sino que permite una personalización completa. Esto significa que, con suficiente experimentación, puedes adaptar la configuración para obtener resultados óptimos basados en tu código.

Optimización con Binaryen.js

La forma más directa de optimizar un módulo de 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 artificialmente antes, por lo que la representación textual de la versión de Wasm del ejemplo de juguete de ExampleScript ya no lo contiene. Observa también cómo se quitan los pares de local.set/get mediante los pasos de optimización SimplifyLocals (otras optimizaciones relacionadas con la configuración local) y Vacuum (quita el código que obviamente no es necesario), y RemoveUnusedBrs quita el 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 específicos. Para una personalización completa, debes usar la herramienta de línea de comandos wasm-opt.

Optimización con la herramienta de línea de comandos wasm-opt

Para una personalización completa de los pases que se usarán, Binaryen incluye la herramienta de línea de comandos de wasm-opt. Para obtener una lista completa de las opciones de optimización posibles, consulta el mensaje de ayuda de la herramienta. La herramienta wasm-opt es probablemente la más popular y la usan varias cadenas de herramientas de compiladores para optimizar el código Wasm, como Emscripten, J2CL, Kotlin/Wasm, dart2wasm, wasm-pack y otras.

wasm-opt --help

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

  • CodeFolding: Evita combinar el código duplicado (por ejemplo, si dos brazos if tienen algunas instrucciones compartidas al final).
  • DeadArgumentElimination: Se trata de 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 reduce a "a", "b".
  • DeadCodeElimination: Quita el código no muerto.

En esta guía de soluciones de optimización, puedes encontrar varias sugerencias para identificar cuáles de las distintas marcas son más importantes y vale la pena probar primero. Por ejemplo, si ejecutas wasm-opt de forma reiterada una y otra vez, se reduce aún más la entrada. En esos casos, la ejecución con la marca --converge continúa con la iteración hasta que no se realizan más optimizaciones y se alcanza un punto fijo.

Demostración

Para ver los conceptos presentados en esta publicación en acción, explora la demostración incorporada que proporciona 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. La biblioteca de JavaScript y las herramientas de línea de comandos ofrecen flexibilidad y facilidad de uso. En esta publicación, demostramos los principios básicos de la compilación de Wasm, con lo que se destaca la eficacia de Binaryen y su potencial para lograr la máxima optimización. Si bien muchas de las opciones para personalizar las optimizaciones de Binaryen requieren un conocimiento profundo sobre las partes internas de Wasm, por lo general, la configuración predeterminada ya funciona muy bien. ¡Feliz compilación y optimización con Binaryen!

Agradecimientos

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