WebAssembly所感

WebAssemblyをちょっといじってみて思ったところをまとめてみます。

設計思想

WebAssembly/designに設計文書がまとまっています。特にHighLevelGoals.mdから読み取れるポイントは以下の4点です。

• サンドボックス化された環境であること。
• 移植性があること。つまり、特定の実CPUアーキテクチャ等に依存しないこと。
• 少なくともC/C++の(十分に高速な)コンパイルターゲットとして機能すること。
• 安定した仕様を持つこと。

サンドボックスという観点からは、先行技術として以下のようなものが特筆に値します。

• Webサンドボックス
  • JavaScript および asm.js
  • Javaアプレット
  • Flash (ActionScript)
  • NaCl, PNaCl
• Web以外のサンドボックス
  • OSのユーザーランド、特にLinux userland

これらのサンドボックスとの比較では以下のようにWebAssemblyを特徴づけられるでしょう。 (FAQ.md も参照)

• JavaScriptと異なり、C/C++の高速なコンパイルターゲットとして機能する。
• asm.jsと異なり、コンパクトなバイナリフォーマットを持つ。
• asm.jsと異なり、既存のJavaScript処理系との相互作用に縛られない仕様策定を行える。
• JVMよりも低いレイヤーでの抽象化を提供する。 (クラスやGC^[1]などは無し)
• NaClと異なり、その仕様は特定のCPUアーキテクチャに依存しない。
• PNaClと異なり、その仕様は特定のコンパイラバックエンドの仕様(LLVM)に特化した形にはなっていない。

WebAssemblyコードを実行する処理系は、意味論の仕様を守っていれば名目上はどのように実装してもいいはずですが、設計上はJITまたはAOTコンパイラによって実CPUのネイティブコードに変換して実行することが想定されていると考えられます。また、期待される実行効率を考えると、そうすることが望ましいでしょう。

実CPUのISA/ABIとの比較

x86-64をはじめとした一般的な実CPUのISA/ABIとの比較です。

ファイル形式

プログラムはELFなどの既存のフォーマットではなく、専用のフォーマットを持つコンテナに格納されます。これは「WebAssemblyモジュールのバイナリ形式」と呼ばれるものです。この仕様はWebAssemblyの命令セットのフォーマットと統合された形で定義されています。つまり、各CPUベンダが定義するISAの上にOS固有のフォーマット (ELFへのマッピングなど) を定義する伝統的な考え方とは異なることになります。

また、WebAssemblyのコードを直接読み書きするための「アセンブリ言語」相当のフォーマットとして、テキスト形式も定義されています。これもISAレベルの形式とコンテナレベルの形式が統合された形で定義されています。また構文的にはS式を利用している点が一般的なアセンブリと異なって見えるでしょう。

入出力

外界との相互作用を行う方法は、一般的な実CPUでは以下のようになっていることが多いと思います。

• 特権プロセスの場合: 専用の入出力命令、メモリマップドI/O、割り込み
• ユーザーランドの場合: システムコール、メモリマップドI/O、シグナル

WebAssemblyにおける外界の相互作用にも同様にいくつかの方法があります。いずれについても、WebAssemblyが規定するのは汎用的な仕組みだけで、実際にどのような機能を提供するかは呼び出し元 (埋め込み側) に任されています。WASIのように、WebAssembly向けのシステムコールセットの標準化を試みるプロジェクトもあります。

• WebAssembly関数の引数(入力)と戻り値(出力)を呼び出し元が解釈することで相互作用となる。
• 逆に、外界から提供された関数を、WebAssembly側が呼び出す。
• 線形メモリ、グローバル変数、テーブルは呼び出し元から直接操作できるため、メモリマップドI/Oの一種とみなせる。

値

WebAssemblyで扱う値には透明な値と不透明な値の2種類があります。

• 透明な値 (transparent value) とは、バイト列などの形で具体的に表現を与えることが可能な値。整数、浮動小数点数など。
• 不透明な値 (opaque value) とは、外界の状態に依存しており、直列化できない値。関数参照など。

不透明な値は、一般的なISAにはあまり登場しないのではないかと思います。 (メモリにマップしてreinterpretすれば表現を読めてしまうので)

WebAssemblyには簡易的な型検査があるため、不透明な値を透明な値として読み直すような処理ははじめからできないようになっています。

レジスタファイルとメモリ

一般的なISAには2つの明示的な記憶領域があります。

• レジスタファイルは一般的に固定長で、通常は静的にアドレッシングされ、透明な値を保持します。
• メモリは一般的に可変長で、動的にアドレッシングされ、透明な値を保持します。

いっぽう、WebAssemblyの対応する記憶領域は目的別に以下のように分けらています。

• 静的にアドレッシングされる記憶領域 (レジスタファイルの類似物)
  • スタックは可変長で、静的にアドレッシングされ、透明な値と不透明な値の両方を保持します。
  • ローカル変数も可変長で、静的にアドレッシングされ、透明な値と不透明な値の両方を保持します。
  • グローバル変数はプログラムごとに固定の長さをもち、静的にアドレッシングされ、透明な値と不透明な値の両方を保持します。
• 動的にアドレッシングされる記憶領域 (メモリの類似物)
  • 線形メモリは可変長で、動的にアドレッシングされ、透明な値を保持します。
  • テーブルは可変長で、動的にアドレッシングされ、不透明な値を保持します。

このうち、WebAssemblyのスタックは一般的なISAにおけるコールスタックよりも能力が制限されています。具体的には動的なアドレッシングを行うことができません。そのためBasic C ABIではWebAssemblyのスタックと線形メモリ上に構築されたスタック構造を組み合わせてCのコールスタックを実現しています。

このように記憶領域が複雑に分割されている理由はいくつかあると考えられます。まず重要なのは、線形メモリには不透明な値を置けないという点です。線形メモリは高効率なバイト列ストレージであることが期待されるため、実行時型検査を入れるという選択肢はあまり考えられません。しかし、実行時型検査を入れない場合、不透明な値を透明な値として読み直す (reinterpret cast) 処理ができてしまうため、不透明な値を読み出せないようにしているWebAssemblyの抽象化が破壊されてしまいます。これが線形メモリとテーブルを分けている理由だと説明できます。^[2]

いっぽう、スタックとローカル変数は動的なアドレッシングを禁止することで静的に型の一致を保証できるようになっています。そのため、透明な値と不透明な値の両方を同時に扱うことを許しても特に問題はないことになります。なお、いずれも単一のフレーム内では決まった大きさしか持たない一方、関数呼び出しを通じて無制限に領域を広げることができるため、単なるレジスタファイルというよりは無限に大きなレジスタウインドウのようなイメージが近いかもしれません。

スタック上に直接値を積むのと、同じフレーム内のローカル変数に値を格納することの役割上の区別はやや曖昧です。能力上は以下の違いがあります。

• 命令のオペランドはスタックから供給されるため、少なくとも命令の直前ではスタックを利用する必要がある。
• スタックはランダムアクセスができないので、積んだ順の逆順以外の方法で値を利用する必要がある場合はローカル変数を経由する必要がある。

つまり、順序よく(逆ポーランド順でそのまま)値を計算しているときは、ローカル変数を経由してもスタックに先に積んでしまってもいいことになります。

制御フロー

WebAssemblyの制御フローはラベルベースの平坦なジャンプに基づくもの (非構造化制御フロー) ではなく、構造化されたものになっています。組み込みのスタックがある点も含めて、この部分はあまりアセンブリらしくありませんが、これについてはWhy a stack machine?で言及があります。

具体的には、WebAssemblyの基本的な制御フロー命令は以下の通りです。

• ジャンプ先を設定する命令: block, loop, if
• 分岐命令: br, br_if, br_table
  • これに加えて、フレームから脱出するのに return も使えます。

理論的には block, loop と br_if の3つだけ考えるのがわかりやすいと思います。

• br $foo は i32.const 1 br_if $foo と等価。
• br_table についても、 br_if の繰り返しとおおむね等価。
• if $foo <...1> else <...2> end は block $foo block $foo_else br_if $foo_else <...2> br $foo end <...1> end と等価。 (たぶん)

状態機械の話なので、非構造化制御フローと構造化制御フローの関係はNFAと正規表現の関係のように考えればいいでしょう。NFAと正規表現が同じ強さの言語を表現できるのと同じように、非構造化制御フローと構造化制御フローも広い意味では等価です。

ただし、その変換には追加のコストが伴います。具体的には、構造化制御フローから非構造化制御フローへの変換はほとんど自明なのに対して、非構造化制御フローから構造化制御フローへの変換 (Relooping)は難しく、一般の変換には以下のいずれかの妥協が必要です。

• 状態管理用に追加のローカル変数を持たせる。
• 基本ブロックの複製を許容する。

実際にこれらの妥協を行わないと変換できないような例として以下があります。

start:
  ; ... block 1 ...
  jump_if (...) b2
  jump b3
b2:
  ; ... block 2 ...
  jump_if (...) b3
  jump b4
b3:
  ; ... block 3 ...
  jump_if (...) b2
  jump b4
b4:
  ; ... block 4 ...
  ret

ここでは b2 ←→ b3 でループがありますが、b2からループに入るパターンとb3からループに入るパターンがあることで構造化が阻まれています。たとえばDuff's deviceはこのような制御構造を持つ例になっていますが、このようにループの途中にジャンプするパターンは実際には非構造的なパターンに位置づけられ、C/C++以外のswitch文ではできないほうが一般的だと思います。

さて、Reloopingが成功する条件はおそらく以下のように特徴づけられると思います。 (独自の考察なので間違ってたらすみません)

• あるCFGが構造化制御フローで記述されるCFGの部分グラフである ⇔ そのCFGの全ての強連結な部分集合が、成分内に支配ノードを持つ

(証明の概略) [⇒] CFGの強連結な部分集合cを1つとる。c中で、構造化制御フロー上で並べたときに最初に来る(CFG上の)基本ブロックをb1とおき、b1を直接含む(構造化制御フロー上の)ブロックをBとおく。cのノードは全てb1に到達できるが、構造化制御フロー上でb1より後ろにあることから、これらはBのループ構造を通ってb1に復帰していることになる。したがってcの基本ブロックは全てBに含まれ、b1はBの最初の基本ブロックであることがわかる。構造化制御フローではブロックに入る方法は1通りしかないので、Bを通る全てのパスはb1を経由する。

[⇐] 構造化制御フローの組み立てアルゴリズムを記述する。このアルゴリズムは、入力CFGの最大の強連結成分の大きさに対する帰納法で定義される。入力CFGから到達不能な基本ブロックを取り除いたあと、強連結成分分解する。各連結成分cについて、仮定より支配ノードdを選択する。cの誘導部分グラフから、dに入る辺を取り除いた部分グラフを考えると、このグラフは元のグラフよりも小さい強連結成分しか持たない。このグラフに対して再帰的に構造化制御フローを組み立てたあと、このコードを loop ... end で囲い、dに入る辺に対応する分岐命令を追加する。これでcに対応するコードが得られた。各強連結成分に対応するコードが得られたため、これらを連結して1つのコードにする。強連結成分同士はDAGを形成するため、トポロジカルソートして先頭から順に処理することができる。空のコードから始め、各強連結成分ごとに block <...直前のコード...> end <...現在の強連結成分に対応するコード...> というコードを作り、直前のコードから現在の強連結成分に出る辺に対応する分岐命令を追加する。これを繰り返すことで所望の構造化制御フローが生成される。

さて、この特徴付けを用いると、先ほどのグラフがReloopingできないことがわかります。{b2, b3}が強連結成分になっていますが、b1→b2, b1→b3の両方のパスがあるためいずれももう一方を支配していません。

WebAssemblyを主なターゲットとするコンパイラは、中間形式としていずれの方法を使うべきか？

コンパイラではLiveness解析など色々な目的で、「コード中の位置」をフラットに表現したいことが結構ある気がするので、結局のところ非構造化された形式のほうが便利そうな気がしますが、実際のところどうなんでしょうか？ 識者の意見を聞きたいです。

命令フォーマット

WebAssemblyのバイナリフォーマットはいわゆるバイトコードと呼ばれる形式で、低レベルでの非構造化された解釈と高レベルでの構造化された解釈の両方に適するように設計されています。

たとえば、前述のように制御フロー命令は構造化されています。これは、 block 命令が即値オペランドとして「命令列」という巨大なデータを含むという解釈です。しかし、これらの命令をバイナリ形式またはテキスト形式で記述する場合は、あたかも block 命令と end 命令が独立した命令であるかのように記述されます。これは命令列をある程度フラットな状態で扱うことが想定されているのだと思われます。

ほとんどの部分ではエンコードが一意に決定できるようになっていますが、可変長整数フォーマットで冗長な表現が許されていることが特筆に値します。このユースケースは古典的なリンカのサポートです。古典的なリンカは命令列全てを解釈せず、アセンブラが別途出力するヒントに基づいて命令列を置換します。この方式ではバイナリの長さが変わらないことが重要になるため、整数を最小長ではなく固定長でエンコードする必要があります。

このようなユースケースがあることから、WebAssemblyモジュールのパーサーを実装するにあたっては、各セクションを未解釈の状態で残すオプションを用意しておくのがよいでしょう。

型システム

WebAssemblyはC/C++のコンパイルターゲットである必要があるため、全体が型で保護されているわけではありません。たとえば、線形メモリに対するアクセス違反などは実行時に検出されます。

いっぽう、WebAssemblyの機能のうち比較的高レベルな抽象化を提供している部分については、比較的単純な型システムを用いた型検査が行われます。これにはスタック・ローカル変数・グローバル変数の扱いが含まれます。ここで使われる値型は以下のようにごく基本的な型のみからなります。

• 透明な値のための型
  • 整数型: i32, i64 (符号の区別なし)
  • 浮動小数点数型: f32, f64
  • SIMD型: v128
• 不透明な値のための型
  • 関数参照: funcref
  • extern参照: externref

これはTyped Function Referencesなどの提案によりさらに拡張される可能性があります。

現時点で型システムが単純である理由はBasic Types Onlyで説明されています。現在あるi32, i64, f64, v128は実CPUのISAにおけるレジスタにマッピングするのに適した型として必要で、f32については単精度演算 (丸めの関係で倍精度演算と等価でない) の結果として必要だと説明がつきます。不透明な値は透明な値との最低限の区別のために必要だと考えられます。それ以外の複雑な型はユーザー定義の方法で線形メモリやテーブルにマップすれば十分というのが現在の判断だと考えられます。ただ、今後GC Proposalなどで複雑な型システムを仕様レベルで取り込む必要があると判断される可能性は十分にあります。

バイナリ形式

バイナリ形式の内部構造は基本的にType-Value形式です。つまり最初の1～2バイト程度がノード種別をあらわし、ノード種別ごとに固有のデータがそれに後続します。この形式の特徴は以下の通りです。

• 1-passで読み、1-passで書くことができる。
• 全ての内容を読まないとパースできない。これは以下を意味する。
  • 不要な内容をスキップすることによる効率化が難しい。
  • 使わない部分であっても、未知のフォーマットがあればパースに失敗してしまう。

いっぽう、ごく一部のノードはTLV形式になっています。この形式はTVとは逆の以下の特徴を持ちます:

• 1-passで読めるが、書くには2-passが必要。
  • 特にWebAssemblyのTLVは長さ自体が可変長であるため、内容部分の開始位置を最初に確定できない。
• 不要な内容は読み飛ばせる。

具体的には各セクションとコードセクションのコード部分がTLVです。

また、式や制御命令中では、終了デリミタを持つ形式も使われています。この形式では、終了デリミタが発見されるまでデータを読み続けます。

テキスト形式

テキスト形式はS式のような形でWebAssemblyモジュールを記述できる形式で、以下の特徴があります。

• カスタムセクションを記述できない。 (→ WebAssembly/design#1153)
• ラベル名や変数名はテキスト形式に固有であり、バイナリ形式では整数値などに変換されてしまう。ただし、カスタムセクションの一種であるnameセクションに情報を残すことが可能。

バイナリ形式では命令列のネスト構造 (block, loop, if) を終了デリミタで表現していますが、テキスト形式でも同じように命令列のネスト構造を end という専用のトークンで表現し、S式の構造である ( ) を使いません。命令列中の ( ) は折り畳み命令という構文糖衣のために利用されます。

ツーリング

WebAssemblyの仕様自体は特定のツールチェインに依存しないように定義されていますが、普及戦略としてはLLVM/Clang(とEmscripten)を名指ししてロードマップに組み込んでいます。

これらのツールはWebAssemblyの仕様の上に追加の規約を乗せて運用していますが、これらの規約はWebAssembly/tool-conventionsにまとめられています。新しいツールは、これに従うことで既存のツールとの相互運用性を高めることができますが、もちろんあえてこれらとは異なる規約を採用することも可能です。

まとめ

• WebAssemblyはWebのコンテキスト (JavaScript) とネイティブコードのコンテキスト (C/C++ etc.) の両方の文脈が仕様に影響を与えていることが感じられ、面白い。
• 命令列やファイルのフォーマットは独自に定義されたものであり、既存のネイティブコード文脈との関連性はそれほど高くなく、むしろVM向けのコードの発想に近い。
• いっぽうで、これらのフォーマットの上に既存のツールチェインを乗せられるような相互運用性は意識されており、カスタムセクションとしてデバッグ情報やリンカ情報を含めることができるようになっている。
• 命令セットはいわゆるTyped Assembly的な発想の影響を強く受けている。これに関連して、プログラムから操作できる記憶領域も一般的なISAよりも複雑になっている。

脚注

1. GC Proposal自体はありますが、MVPにGCが含まれていないことでGCを前提にしないエコシステムがあるという特徴は変わらないでしょう。

2. ただし、元々のテーブルは関数の間接呼び出しのための静的なストレージという役割だったようです。