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

Томас Штайнер

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

Справочная информация о Binaryen

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

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

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

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

Binaryen используется рядом проектов, например, AssemblyScript , который использует Binaryen для компиляции из языка, подобного TypeScript, непосредственно в WebAssembly. Попробуйте пример на игровой площадке 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
 )
)

Площадка AssemblyScript, показывающая сгенерированный код WebAssembly на основе предыдущего примера.

Инструментарий 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 (Еще один компилятор-компилятор): yacc — это инструмент, который генерирует парсеры для анализа синтаксиса. Он принимает на вход формальное описание грамматики языка программирования и генерирует код для синтаксического анализатора. Синтаксические анализаторы обычно создают абстрактные синтаксические деревья (AST), которые представляют иерархическую структуру исходного кода.

Проработанный пример

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

  • Чтобы написать функцию 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 . Для каждого из четырех возможных операторов в SampleScript, то есть + , - , * , / , в модуль необходимо добавить новую функцию с помощью метода Binaryen Module#addFunction() . Параметры методов Module#addFunction() следующие:

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

Есть еще некоторые детали, которые нужно разобрать и разобрать, и документация Binaryen может помочь вам сориентироваться в этом пространстве, но в конечном итоге для оператора + в SampleScript вы в конечном итоге попадете в метод 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() , поскольку SampleScript также работает с результатами с плавающей запятой.

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

Если вы имеете дело с реальными базами кода, иногда встречается мертвый код, который никогда не вызывается. Чтобы искусственно ввести мертвый код (который будет оптимизирован и удален на более позднем этапе) в работающем примере компиляции SampleScript в 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)
  )
 )
)

Снимок экрана консоли DevTools с экспортом модуля 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 продолжает повторяться до тех пор, пока не прекратится дальнейшая оптимизация и не будет достигнута фиксированная точка.

Демо

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

Выводы

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

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

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