Binaryen を使用した Wasm のコンパイルと最適化

Binaryen は、C++ で記述された WebAssembly 用のコンパイラとツールチェーン インフラストラクチャ ライブラリです。WebAssembly へのコンパイルを直感的で、高速かつ効果的なものを目指しています。この記事では、ExampleScript という合成トイ言語の例を使用して、Binaryen.js API を使用して JavaScript で WebAssembly モジュールを作成する方法を学びます。モジュールの作成、モジュールへの関数の追加、モジュールからの関数のエクスポートの基本について説明します。これにより、実際のプログラミング言語を WebAssembly にコンパイルする全体的なメカニズムについて学習できます。また、Binaryen.js とコマンドライン(wasm-opt)の両方で Wasm モジュールを最適化する方法についても説明します。

Binaryen の背景

Binaryen には、単一のヘッダーに直感的な C API があり、JavaScript から使用することもできます。WebAssembly 形式で入力を受け付けますが、一般的な制御フロー グラフも受け入れます。

中間表現(IR)は、コンパイラまたは仮想マシンがソースコードを表すために内部的に使用するデータ構造またはコードです。Binaryen の内部 IR はコンパクトなデータ構造を使用しており、使用可能なすべての CPU コアを使用して、完全に並列なコード生成と最適化を行うように設計されています。Binaryen の IR は、WebAssembly のサブセットであるため、WebAssembly にコンパイルされます。

Binaryen のオプティマイザーには、コードのサイズと速度の改善に役立つ多くのパスがあります。これらの最適化は、Binaryen をコンパイラ バックエンドとして単独で使用できるほど強力にすることを目的としています。これには、WebAssembly 固有の最適化(汎用コンパイラでは行われない可能性のある最適化)が含まれます。これは Wasm の最小化と考えることができます。

Binaryen の例として AssemblyScript

Binaryen は、Binaryen を使用して TypeScript のような言語から WebAssembly に直接コンパイルする AssemblyScript など、多くのプロジェクトで使用されています。AssemblyScript のプレイグラウンドでサンプルを試す

AssemblyScript 入力:

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

Binaryen によって生成されたテキスト形式の対応する WebAssembly コード:

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

前の例に基づいて生成された WebAssembly コードを示す AssemblyScript のプレイグラウンド。

Binaryen ツールチェーン

Binaryen ツールチェーンには、JavaScript デベロッパーとコマンドライン ユーザーの両方に便利なツールが多数用意されています。以下に、これらのツールのサブセットを示します。含まれるツールの完全なリストは、プロジェクトの README ファイルにあります。

  • binaryen.js: Wasm モジュールの作成と最適化のための Binaryen メソッドを公開するスタンドアロンの JavaScript ライブラリ。ビルドについては、npm の binaryen.js をご覧ください(または、GitHub または unpkg から直接ダウンロードしてください)。
  • wasm-opt: WebAssembly を読み込み、Binaryen IR パスを実行するコマンドライン ツール。
  • wasm-aswasm-dis: WebAssembly をアセンブルおよび逆アセンブルするコマンドライン ツール。
  • wasm-ctor-eval: コンパイル時に関数(または関数の一部)を実行できるコマンドライン ツール。
  • wasm-metadce: モジュールの使用方法に応じて柔軟に Wasm ファイルの一部を削除するコマンドライン ツール。
  • wasm-merge: 複数の Wasm ファイルを 1 つのファイルに統合し、対応するインポートをエクスポートに接続するコマンドライン ツール。JavaScript のバンドルツールに似ていますが、Wasm 用です。

WebAssembly へのコンパイル

ある言語から別の言語にコンパイルするには、通常、いくつかの手順が必要です。最も重要な手順を以下に示します。

  • 字句解析: ソースコードをトークンに分割します。
  • 構文解析: 抽象構文ツリーを作成します。
  • セマンティック分析: エラーを検出し、言語ルールを適用します。
  • 中間のコード生成: より抽象的な表現を作成します。
  • コード生成: ターゲット言語に翻訳します。
  • ターゲット固有のコード最適化: ターゲットに合わせて最適化します。

Unix の世界では、コンパイルによく使用されるツールは lexyacc です。

  • lex(Lexical Analyzer Generator): lex は、字句アナライザ(レクサーまたはスキャナとも呼ばれます)を生成するツールです。正規表現と対応するアクションのセットを入力として受け取り、入力ソースコードのパターンを認識する正規化解析ツールのコードを生成する。
  • yacc(Yet Another Compiler Compiler): yacc は、構文解析用のパーサを生成するツールです。プログラミング言語の形式的な文法記述を入力として受け取り、パーサーのコードを生成するモデルです。通常、パーサーは、ソースコードの階層構造を表す抽象構文ツリー(AST)を生成します。

実施例

この投稿の範囲では、完全なプログラミング言語を扱うことはできません。そのため、わかりやすくするために、ExampleScript という非常に限定的で役に立たない合成プログラミング言語について考えてみましょう。この言語は、具体的な例を通じて汎用オペレーションを表現することで機能します。

  • add() 関数を記述するには、任意の加算の例(2 + 3 など)をコーディングします。
  • multiply() 関数を記述するには、6 * 12 のように記述します。

事前警告に従い、完全に無用ですが、正規化アナライザが単一の正規表現 /\d+\s*[\+\-\*\/]\s*\d+\s*/ になるほどシンプルです。

次に、パーサーが必要です。実際には、名前付きキャプチャ グループ を含む正規表現(/(?<first_operand>\d+)\s*(?<operator>[\+\-\*\/])\s*(?<second_operand>\d+)/)を使用して、抽象構文木の非常に簡素化されたバージョンを作成できます。

ExampleScript コマンドは 1 行に 1 つずつ記述されるため、パーサーは改行文字で分割してコードを行単位で処理できます。先ほどの箇条書きの最初の 3 つのステップ、すなわち字句分析構文解析意味分析をチェックするにはこれで十分です。これらの手順のコードを次のリストに示します。

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

抽象構文木の各行には、firstOperandoperatorsecondOperand で構成される 3 つ組が含まれています。ExampleScript で使用できる 4 つの演算子(+-*/)ごとに、Binaryen の Module#addFunction() メソッドを使用して、新しい関数をモジュールに追加する必要があります。Module#addFunction() メソッドのパラメータは次のとおりです。

  • name: string。関数の名前を表します。
  • functionType: Signature。関数のシグネチャを表します。
  • varTypes: Type[]。指定された順序で追加のローカルを指定します。
  • body: Expression(関数の内容)。

詳細を解きほぐして分解することもできます。Binaryen のドキュメントを参照すると、この空間をナビゲートできますが、最終的には、ExampleScript の + 演算子で、利用可能ないくつかの整数演算の 1 つとして Module#i32.add() メソッドに到達します。加算には、1 つ目の加数と 2 つ目の加数という 2 つのオペランドが必要です。関数を実際に呼び出すには、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');

抽象構文木を処理した後、モジュールには 4 つのメソッドが含まれます。3 つは整数値を処理します。Module#i32.add() に基づく add()Module#i32.sub() に基づく subtract()Module#i32.mul() に基づく multiply()Module#f64.div() に基づく外れ値 divide() です。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 に 2 つの方法があります。S 式.wat ファイルとしてテキスト形式で人間が読める形式で取得する方法と、ブラウザで直接実行できる .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);

4 つのオペレーションすべてを含む 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 モジュールのエクスポートの DevTools コンソール スクリーンショット。加算、除算、乗算、減算の 4 つの関数が表示されています(公開されていないデッドコードは表示されていません)。

WebAssembly の最適化

Binaryen には、Wasm コードを最適化する 2 つの方法があります。1 つは Binaryen.js 自体に、もう 1 つはコマンドライン用です。前者は最適化ルールの標準セットをデフォルトで適用し、最適化レベルと縮小レベルを設定できます。後者では、デフォルトでルールを使用せず、完全なカスタマイズが可能です。つまり、十分なテストを行うことで、コードに基づいて最適な結果が得られるように設定を調整できます。

Binaryen.js による最適化

Binaryen で Wasm モジュールを最適化する最も簡単な方法は、Binaryen.js の Module#optimize() メソッドを直接呼び出し、必要に応じて最適化と圧縮レベルを設定することです。

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

これにより、以前に人為的に導入されたデッドコードが削除されるため、ExampleScript トイサンプルの Wasm バージョンのテキスト表現にデッドコードが含まれなくなります。また、最適化ステップの SimplifyLocals(ローカル関連のその他の最適化)と Vacuum(明らかに不要なコードを削除)によって local.set/get ペアが削除され、RemoveUnusedBrs(不要な場所からブレークを削除)によって return が削除される点にも注目してください。

 (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 ツールはおそらく最も人気があり、EmscriptenJ2CLKotlin/Wasmdart2wasmwasm-pack など、複数のコンパイラ ツールチェーンで Wasm コードを最適化するために使用されています。

wasm-opt --help

パスについて理解できるように、専門知識がなくてもわかりやすいパスを抜粋して紹介します。

  • CodeFolding: コードをマージして重複を回避します(2 つの if アームの末尾に共有命令がある場合など)。
  • DeadArgumentElimination: 関数が常に同じ定数で呼び出される場合、関数のリンク時間最適化パスで引数を削除します。
  • MinifyImportsAndExports: "a""b" に圧縮します。
  • DeadCodeElimination: 不要なコードを削除します。

最適化クックブックには、さまざまなフラグのうちどれがより重要で、最初に試してみる価値があるかを特定するためのヒントがいくつか記載されています。たとえば、wasm-opt を何度も実行すると、入力がさらに縮小されることがあります。このような場合、--converge フラグを使用して実行すると、最適化が完了して固定点に到達するまで反復処理が続行されます。

デモ

この記事で説明したコンセプトを実際に確認するには、埋め込まれたデモで、考えられるすべての ExampleScript 入力を指定します。また、デモのソースコードもご覧ください。

まとめ

Binaryen は、WebAssembly に言語をコンパイルして、生成されたコードを最適化するための強力なツールキットを提供します。JavaScript ライブラリとコマンドライン ツールが柔軟性と使いやすさを備えています。この投稿では、Wasm コンパイルの基本原則を示し、Binaryen の有効性と最大限の最適化の可能性について説明しました。Binaryen の最適化をカスタマイズするためのオプションの多くは、Wasm の内部に関する深い知識を必要としますが、通常はデフォルト設定で十分に機能します。以上で、Binaryen でのコンパイルと最適化は完了です。

謝辞

この投稿は、Alon ZakaiThomas LivelyRachel Andrew がレビューしました。