Компиляция и оптимизация Wasm с помощью Binaryen

Thomas Steiner

Binaryen — это библиотека компилятора и инфраструктуры цепочки инструментов для WebAssembly, написанная на C++. Она призвана сделать компиляцию в WebAssembly интуитивно понятной, быстрой и эффективной. В этой статье на примере синтетического языка ExampleScript вы научитесь писать модули WebAssembly на JavaScript с использованием API Binaryen.js. Вы изучите основы создания модулей, добавления функций в модуль и экспорта функций из модуля. Это даст вам представление об общей механике компиляции реальных языков программирования в WebAssembly. Кроме того, вы научитесь оптимизировать модули Wasm как с помощью Binaryen.js, так и в командной строке с помощью wasm-opt .

Предыстория Binaryen

Binaryen имеет интуитивно понятный C API в одном заголовочном файле и может использоваться из JavaScript . Он принимает входные данные в формате WebAssembly , но также поддерживает общий граф управления для компиляторов, которые предпочитают его.

Промежуточное представление (IR) — это структура данных или код, используемый компилятором или виртуальной машиной для представления исходного кода. Внутреннее IR Binaryen использует компактные структуры данных и предназначено для полностью параллельной генерации и оптимизации кода с использованием всех доступных ядер процессора. IR Binaryen компилируется в WebAssembly, поскольку является его подмножеством.

Оптимизатор Binaryen имеет множество проходов, которые могут улучшить размер и скорость кода. Эти оптимизации направлены на то, чтобы сделать Binaryen достаточно мощным, чтобы его можно было использовать в качестве самостоятельного бэкенда компилятора. Он включает в себя оптимизации, специфичные для WebAssembly (которые универсальные компиляторы могут не поддерживать), что можно назвать минимизацией Wasm.

AssemblyScript как пример пользователя Binaryen

Binaryen используется в ряде проектов, например, в AssemblyScript , где Binaryen компилируется из языка, похожего на TypeScript, непосредственно в WebAssembly. Ознакомьтесь с примером на плейграунде AssemblyScript.

Ввод AssemblyScript:

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

Соответствующий код WebAssembly в текстовой форме, сгенерированный 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
 )
)

Набор инструментов Binaryen

Набор инструментов Binaryen предлагает ряд полезных инструментов как для разработчиков JavaScript, так и для пользователей командной строки. Ниже перечислена лишь часть этих инструментов; полный список инструментов доступен в файле README проекта.

• binaryen.js : автономная библиотека JavaScript, предоставляющая методы Binaryen для создания и оптимизации модулей Wasm . Сборки можно найти в файле binaryen.js на npm (или скачать его напрямую с GitHub или unpkg ).
• wasm-opt : инструмент командной строки, который загружает WebAssembly и запускает в нем проходы Binaryen IR.
• wasm-as и wasm-dis : инструменты командной строки, которые собирают и разбирают WebAssembly.
• wasm-ctor-eval : инструмент командной строки, который может выполнять функции (или части функций) во время компиляции.
• wasm-metadce : Инструмент командной строки для удаления частей файлов Wasm гибким способом, который зависит от того, как используется модуль.
• wasm-merge : инструмент командной строки, который объединяет несколько файлов Wasm в один, одновременно подключая соответствующие импорты к экспортам. Похож на сборщик для JavaScript, но для Wasm.

Компиляция в WebAssembly

Компиляция одного языка в другой обычно включает несколько этапов, наиболее важные из которых перечислены в следующем списке:

• Лексический анализ: разбейте исходный код на токены.
• Синтаксический анализ: создание абстрактного синтаксического дерева.
• Семантический анализ: проверка на наличие ошибок и обеспечение соблюдения языковых правил.
• Генерация промежуточного кода: создание более абстрактного представления.
• Генерация кода: перевод на целевой язык.
• Оптимизация кода для конкретной цели: оптимизация для конкретной цели.

В мире Unix часто используемыми инструментами для компиляции являются lex и yacc :

• lex (генератор лексических анализаторов): lex — это инструмент для генерации лексических анализаторов, также известных как лексеры или сканеры. Он принимает на вход набор регулярных выражений и соответствующих действий и генерирует код для лексического анализатора, распознающего шаблоны во входном исходном коде.
• yacc (Yet Another Compiler Compiler): yacc — это инструмент, генерирующий парсеры для синтаксического анализа. Он принимает в качестве входных данных формальное описание грамматики языка программирования и генерирует код для парсера. Парсеры обычно создают абстрактные синтаксические деревья (АСД), представляющие иерархическую структуру исходного кода.

Реализованный пример

Учитывая объем этой статьи, невозможно охватить весь язык программирования, поэтому для простоты рассмотрим очень ограниченный и бесполезный синтетический язык программирования под названием ExampleScript, который работает, выражая общие операции с помощью конкретных примеров.

• Чтобы написать функцию add() , вы кодируете пример любого сложения, скажем, 2 + 3 .
• Чтобы написать функцию multiply() , вы пишете, например, 6 * 12 .

Согласно предварительному предупреждению, совершенно бесполезно, но достаточно просто для того, чтобы его лексический анализатор представлял собой одно регулярное выражение: /\d+\s*[\+\-\*\/]\s*\d+\s*/ .

Далее, необходим парсер . На самом деле, очень упрощённую версию абстрактного синтаксического дерева можно создать, используя регулярное выражение с именованными захватывающими группами : /(?<first_operand>\d+)\s*(?<operator>[\+\-\*\/])\s*(?<second_operand>\d+)/ .

Команды ExampleScript размещаются по одной в каждой строке, поэтому парсер может обрабатывать код построчно, разбивая его по символам новой строки. Этого достаточно для проверки первых трёх шагов из списка, представленного ранее, а именно лексического анализа , синтаксического анализа и семантического анализа . Код для этих шагов представлен в следующем листинге.

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

Генерация промежуточного кода

Теперь, когда программы на ExampleScript можно представить в виде абстрактного синтаксического дерева (хотя и довольно упрощённого), следующим шагом будет создание абстрактного промежуточного представления. Первым шагом будет создание нового модуля в Binaryen :

const module = new binaryen.Module();

Каждая строка абстрактного синтаксического дерева содержит тройку, состоящую из firstOperand , operator и secondOperand . Для каждого из четырёх возможных операторов в ExampleScript, а именно + , - , * , / , необходимо добавить новую функцию в модуль с помощью метода Module#addFunction() библиотеки Binaryen. Параметры методов Module#addFunction() следующие:

• name : string , представляющая имя функции.
• functionType : Signature , представляет сигнатуру функции.
• varTypes : Type[] , указывает дополнительные локальные переменные в указанном порядке.
• body : Expression , содержимое функции.

Есть ещё несколько деталей, которые стоит разобрать и разобрать, и документация Binaryen поможет вам сориентироваться, но в конечном итоге для оператора + в ExampleScript вы окажетесь у метода Module#i32.add() как одной из нескольких доступных целочисленных операций . Сложение требует двух операндов: первого и второго слагаемых. Чтобы функция была действительно вызываемой, её необходимо экспортировать с помощью 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');

После обработки абстрактного синтаксического дерева модуль содержит четыре метода, три из которых работают с целыми числами, а именно add() на основе Module#i32.add() , subtract() на основе Module#i32.sub() , multiply() на основе Module#i32.mul() и выброс divide() на основе Module#f64.div() поскольку ExampleScript также работает с результатами с плавающей точкой.

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

При работе с реальными кодовыми базами иногда встречается мёртвый код, который никогда не вызывается. Чтобы искусственно добавить мёртвый код (который будет оптимизирован и удалён на следующем этапе) в работающий пример компиляции ExampleScript в Wasm, достаточно добавить неэкспортируемую функцию.

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

Компилятор почти готов. Проверка модуля с помощью метода Module#validate() не является строго обязательной, но определённо рекомендуется.

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

Получение результирующего Wasm-кода

Для получения результирующего Wasm-кода в Binaryen существуют два метода: текстовое представление в виде .wat файла в S-выражении в удобном для восприятия формате и двоичное представление в виде .wasm файла, который можно запустить непосредственно в браузере. Для проверки работоспособности можно зарегистрировать экспорт.

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

Полное текстовое представление программы ExampleScript со всеми четырьмя операциями приведено ниже. Обратите внимание, что мёртвый код всё ещё присутствует, но не отображается, как на снимке экрана 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)
  )
 )
)

Оптимизация WebAssembly

Binaryen предлагает два способа оптимизации кода Wasm: один в самом Binaryen.js, а другой — через командную строку. Первый вариант по умолчанию применяет стандартный набор правил оптимизации и позволяет задать уровень оптимизации и сжатия, а второй по умолчанию не использует никаких правил, но допускает полную настройку. Это означает, что, поэкспериментировав, вы сможете настроить параметры для достижения оптимальных результатов в зависимости от вашего кода.

Оптимизация с помощью Binaryen.js

Самый простой способ оптимизировать модуль Wasm с помощью Binaryen — напрямую вызвать метод Module#optimize() из Binaryen.js и при необходимости задать уровень оптимизации и сжатия .

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

Это удаляет искусственно внесённый ранее мёртвый код, поэтому текстовое представление Wasm-версии примера ExampleScript больше не содержит его. Обратите внимание также на то, как пары local.set/get удаляются этапами оптимизации SimplifyLocals (различные оптимизации, связанные с локальными переменными) и Vacuum (удаление явно ненужного кода), а return удаляется методом RemoveUnusedBrs (удаление разрывов из ненужных мест).

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

Существует множество проходов оптимизации , и Module#optimize() использует заданные по умолчанию уровни оптимизации и сжатия. Для полной настройки необходимо использовать инструмент командной строки wasm-opt .

Оптимизация с помощью инструмента командной строки wasm-opt

Для полной настройки используемых проходов Binaryen включает в себя инструмент командной строки wasm-opt . Полный список возможных вариантов оптимизации можно найти в справке инструмента. wasm-opt пожалуй, самый популярный инструмент и используется несколькими цепочками компиляторов для оптимизации кода Wasm, включая Emscripten , J2CL , Kotlin/Wasm , dart2wasm , wasm-pack и другие.

wasm-opt --help

Чтобы дать вам представление о пропусках, вот выдержка из некоторых из них, понятных и без специальных знаний:

• CodeFolding: позволяет избежать дублирования кода путем его слияния (например, если две ветви if имеют общие инструкции на своем конце).
• DeadArgumentElimination: Проход оптимизации времени компоновки для удаления аргументов функции, если она всегда вызывается с одними и теми же константами.
• MinifyImportsAndExports: уменьшает их до "a" и "b" .
• DeadCodeElimination: удаление мертвого кода.

Существует книга по оптимизации с несколькими советами, которые помогут определить, какие из флагов важнее и какие стоит попробовать в первую очередь. Например, иногда многократное выполнение wasm-opt ещё больше сокращает входные данные. В таких случаях запуск с флагом --converge продолжает итерации до тех пор, пока дальнейшая оптимизация не прекратится и не будет достигнута фиксированная точка.

Демо

Чтобы увидеть концепции, представленные в этой статье, на практике, поэкспериментируйте со встроенной демонстрацией, предоставив ей любые входные данные ExampleScript, которые только сможете придумать. Также обязательно ознакомьтесь с исходным кодом демонстрации .

Выводы

Binaryen предоставляет мощный инструментарий для компиляции языков в WebAssembly и оптимизации полученного кода. Его библиотека JavaScript и инструменты командной строки обеспечивают гибкость и простоту использования. В этой публикации были продемонстрированы основные принципы компиляции Wasm, подчеркнув эффективность Binaryen и его потенциал для максимальной оптимизации. Хотя многие возможности настройки оптимизации Binaryen требуют глубоких знаний внутреннего устройства Wasm, обычно настройки по умолчанию отлично работают. Удачной компиляции и оптимизации с Binaryen!

Благодарности

Эту публикацию просмотрели Алон Закай , Томас Лайвли и Рэйчел Эндрю .