WebAssembly 向けのコンパイラを作ってみる
はじめに
結構前から wasm さわってみたいと思いつつ手を出せずにいたんですが 去年 C コンパイラを学んだりしてハードルが下がった感じがあって簡単なコンパイラ実装をやりはじめました。
まずは難しい機能は入れず C 言語から大分機能を落としたサブセットのコンパイラを作ることにしました。
リポジトリはこれです。
https://github.com/tkaaad97/wasm-experiment1
例として下のコードをコンパイルすると
void printf_i(string s, int a); int add(int a, int b) { return a + b; } int main(int n, int b) { int a = 0; for (int i = 0; i < n; ++i) { a = add(a, b); } printf_i("a=%d\n", a); return a; }
出力の wasm (テキスト形式) は下のようになります。
(module (import (;0;) "" "printf_i" (func (param i64 i32))) (type (;0;) (func (param i32 i32) (result i32))) (type (;1;) (func (param i32 i32) (result i32))) (func (;1;) (type 0) (param i32 i32) (result i32) local.get 0 local.get 1 i32.add return unreachable ) (func (;2;) (type 1) (param i32 i32) (result i32) (local i32 i32) i32.const 0 local.tee 2 drop block i32.const 0 local.tee 3 drop loop local.get 3 local.get 0 i32.lt_s i32.eqz br_if 1 local.get 2 local.get 1 call 1 local.tee 2 drop local.get 3 i32.const 1 i32.add local.tee 3 drop br 0 end end i64.const 12884901888 local.get 2 call 0 local.get 2 return unreachable ) (export "memory" (memory 0)) (export "add" (func 1)) (export "main" (func 2)) (memory (;0;) 1 10) (data (;0;) (i32.const 0) "a=%d\n\00") )
WebAssembly 関連情報
wasm の仕様はここのようです。大体ここに必要なことは書かれているはずです。
wasm の入門的な記事です。最初はこのあたりを読んだりしていました。
実行するときに wasmtime の C API を使いました。その他にもコマンドラインで色々試したりできます。
コンパイラ実装について
スタックマシン
前に C コンパイラ作成したときは x86-64 でやっていてこれはレジスタマシンでした。
wasm はスタックマシンなので色々と実装が変わってきます。
x86-64 向けの実装でもメモリ上のスタックは使っていたので、 スタックマシンではレジスタに動かす必要がなくなって実装が楽になるのかなと思ってましたが、 実装を進めるとちょっと勘違いしていたことがわかりました。
wasm のスタックはメモリ上のスタックとは違って操作がかなり制限されています。
例えば関数の引数とローカル変数には local.get
という命令でアクセスできるんですが
この引数には定数のインデックスしか渡せず何らかの計算をしたインデックスを使ったりできません。
配列をローカル変数としてスタック上配置したとしてもループで回してインデックスアクセスしたりできないわけです。
なので wasm 側のスタックとは別にメモリ上にアプリケーションがスタックとして使う領域を別に用意して使うことになるんじゃないかと思います。 C 言語と違ってポインタが無い言語ではまた実装違うかなという気もします。
今回実装した言語は機能を大幅にカットしていてポインタも配列も無いので 全部 wasm 側のスタックで済ませるということにしています。
四則演算
四則演算はそのままスタックに積んでいって計算すればいいので簡単です。
四則演算の例
1 + 2 * 3 - 4 / 5 + 6
wasm
i32.const 1 i32.const 2 i32.const 3 i32.mul i32.add i32.const 4 i32.const 5 i32.div_s i32.sub i32.const 6 i32.add
関数
wasm にも関数の機能があって、これを C 言語の関数実装にも使えますが 先に触れたように引数とローカル変数におけるものが限られているのでちゃんと実装するには自前でメモリ上にスタックを作るなどする必要がありそうです。
関数には型が付きます。スタックから入力として使うデータの型とスタックに結果として残すデータの型です。 スタックに渡すデータの型や個数は実行前にチェックされて少し静的言語っぽい感じもしました。
関数の例
int add(int a, int b) { return a + b; }
wasm の例
(func (param i32 i32) (result i32) local.get 0 local.get 1 i32.add )
テキストフォーマットでは S 式のようにも書くことができます。
(func (param i32 i32) (result i32) (i32.add (local.get 0) (local.get 1)) )
if
wasm はジャンプ命令がなくてブロックがいくつかあります。
アセンブリだと普通ネストした構造はないですが wasm はこのあたり変わってて ブロックはプログラミング言語のようにネストした構造を作れます。
C 言語の if 文を実装するには wasm の if ブロックがそのまま使えます。
if 文の例
int min(int a, int b) { int c = 0; if (a < b) { c = a; } else { c = b; } return c; }
wasm
(func (param i32 i32) (result i32) (local i32) i32.const 0 local.tee 2 drop local.get 0 local.get 1 i32.lt_s if local.get 0 local.tee 2 drop else local.get 1 local.tee 2 drop end local.get 2 )
この例だとパラメーターも結果も無いので省略されていますがブロックにも関数と同じように型が付きます。
関数内で if ブロックを使って return しようとすると警告出てしまうことがありました。
警告がでるコード
(func (param i32 i32) (result i32) local.get 0 local.get 1 i32.lt_s if local.get 0 return else local.get 1 return end )
wat2wasm の警告
error: type mismatch in implicit return, expected [i32] but got []
こういう場合は unreachable を入れるといいようです。
(func (param i32 i32) (result i32) local.get 0 local.get 1 i32.lt_s if local.get 0 return else local.get 1 return end unreachable )
for
for 文 は loop ブロックと br, br_if を使って作れます。
br と br_if は break と似てますが loop ブロックに使う場合は continue のような挙動になるようです。
loop ブロックの参考
for 文の例
int a = 0; for (int i = 0; i < 10; ++i) { a = a + i; }
生成された wasm
i32.const 0 local.tee 0 drop block i32.const 0 local.tee 1 drop loop local.get 1 i32.const 10 i32.lt_s i32.eqz br_if 1 local.get 0 local.get 1 i32.add local.tee 0 drop local.get 1 i32.const 1 i32.add local.tee 1 drop br 0 end end
break 実装するときに wasm 側でどのブロックを抜けるのか知る必要があります。
例えば for の中に if があってそこで break 使う場合は二つ上のブロックを抜けるように br 2
とします。
この部分は wasm 生成する関数で今 break 使ったらどのブロック抜けるかというのを引数で渡す感じで実装しました。
文字列リテラル
data segment という機能でメモリ上に文字列データを配置することができます。
コードに持つ文字列リテラルの情報としてはメモリ上のオフセットとサイズを持っておけばいいので
i64.const にオフセットとサイズを 32bit づつにして定数として埋め込んでいます。
グローバル変数
グローバル変数も wasm 側で機能が用意されていてある程度はこれを使えるんですが C 言語の機能とはちょっと違っています。
配列や構造体、ポインタとして扱うデータなどはメモリ側に置くことになると思います。
wasm グローバル変数の初期化式には定数式しか使えないので
C 言語の機能を実装していくにはグローバル変数初期化用の関数を作ったりする必要がありそうです。
ホスト側の関数を呼ぶには
wasm の範囲では標準入出力やファイルを扱ったりできません。
かわりにホスト側の処理を呼び出すことができるような仕組みがあります。
wasmtime では C API が実装されていてホスト側の関数ポインタをモジュールの import として呼び出せるようになっています。
JavaScript 向けの処理系では wasm から JavaScript の関数を呼び出すような仕組みを持っています。
また WebAssembly System Interface (WASI) というのが提案されていて入出力やファイルシステムなどを扱うための インターフェースが定義されて色々なランタイムが実装されているようです。
WASI を使って実装された wasi-libc というのもあって C 言語で実装されたものを wasm にするときには必要になりそうです。
printf を呼ぶ
ホスト側の関数を呼べるので printf なども使えますが可変長引数の仕組みはないので 引数を変えてたくさん関数を import したりする必要があります。
それか引数もメモリ上に配置してホスト側で復元して呼び出すような感じにもできるかもしれません。
今回使ってないですが wasi-libc に printf もあるらしいです。
感想
関数があったりネストした構文があったりしてアセンブラよりかなりプログラミング言語に近く感じました。
wasm にコンパイルできる言語は色々あるので別に自分でコンパイラ書く必要はそんなにない気もしますが色々勉強になりました。
私が使いたいところとしては Web でなにか動かしたいというよりは、 例えばゲームやアプリで一部スクリプトやプラグインのようなものを動かすのに使えるかもと考えてました。
今回は大分実装を省略しましたが配列、構造体、メモリ上のスタック、コルーチン (難しそう) などそのうち実装してみたいと思いました。