【WASM】Cコンパイラをブラウザ上で動かす

2021-02-04
#compiler #binary

自作のCコンパイラはx86-64用となっていて、ELF64バイナリを出力する。 x86-64上で実行できるコードを出力できれば自宅のパソコン上で実行できるし、今後10年くらいはやっていけるだろうという目論見だった。 ところがいろんなプロセッサが出てきたりして、x86が主流で居続けるとはいえないかもという気がしてきた。

またRustで書いたコードをwasmにコンパイルしてブラウザで動かせる、ということを体験した。 ポインタでメモリ操作みたいな低レベルのことができる言語で書いたコードをブラウザで動かせるなんてどうなっているの？と結構驚いた。

てなことでいっちょCコンパイラからwasmを出力できるようにしてみようと考えた。

オンラインデモ

WASMのアーキテクチャ

WASMのアーキテクチャはちょっと前に調べて、特徴的なこととしては：

  • スタックマシンの命令セット（レジスタがない）
  • ローカル変数が使える
  • 扱える型は i32, i64, f32, f64 のみ（文字列すらない）
  • ジャンプはラベル（アドレス）に対してでなく、制御構文的なジャンプ（ブロックから抜けるかループで戻る）のみ
  • GCはない

扱えるデータ形式としてはオブジェクトや文字列といった便利なものがなくバイト列をゴリゴリ触れるだけだが、C程度の言語仕様から持ってくるには十分なレベルだと思う。

CコンパイラからWASMバイナリを出力する際の方針

元のコンパイラはレジスタマシンの命令列に変換するために、

  1. フロントエンド（パーサ）：Cソース→抽象構文木(AST)
  2. ミドルエンド（中間表現）：AST→中間表現(IR)
  3. バックエンド：IR→x86-64バイナリ(ELF64形式)

という手順を踏んでいる。 出力対象を切り替えるのは本来ミドルエンドまでは共有してバックエンドを差し替えることで変更できるのがいいんだけど、ちょっと難しい。

ミドルエンドではジャンプを基本ブロックの連結に変換して、最終的にラベルジャンプにする。 しかしwasmではジャンプが制御構造となっていて、任意の箇所にラベルを配置してジャンプさせるということができない。 なのでやるとしたらラベルジャンプから制御構造を復元させてやる必要がある。 制御フローグラフの解析とかしたら復元できるのかもしれないけど、簡単ではなさそう。

他にも面倒そうな点があって、

  • 式の計算が仮想レジスタ同士の3番地コードでの演算に変換されたものを、スタックマシン方式に戻す必要がある

ASTの段階であればそのまま使えるので、フロントエンドだけ共有してASTから直接wasmバイナリを出力するようにした。

いくつか実装ポイント

数値型以外のローカル変数の扱い

WASMでローカル変数として扱えるのは32/64ビットの整数／小数点数型のみで、構造体や配列は扱えない。 どうするかというと線形メモリに格納することになる。

線形メモリのどこを使うかというのは自前で管理する必要がある。 そこでグローバル変数にスタックポインタを表す変数を用意して、関数の頭でベースポインタを表すローカル変数に格納してスタックポインタをいじってやり、抜けるときに戻すという処理を自前で行う。

数値型でも&で参照を取られた場合にはポインタ経由で書き換えられるようにする必要があるため、ローカル変数にはできないので線形メモリ上に置くようにする。

関数途中からのreturn

関数の途中から return で値を伴って抜ける場合x86などの実プロセッサではABIに従って例えば eax レジスタに値を入れて呼び出し元に返る、などとする。 WASMでも return という命令で関数から抜けてスタックトップの値を返すことができるんだけど、前項のスタックポインタを戻す処理が必要な場合もあるので、関数から抜ける処理（エピローグ）は統一したい。

そうなると途中からのreturnが使えないので、戻り値を格納するローカル変数を用意して、そいつに格納してエピローグにジャンプ、エピローグ処理して戻り値を取り出して返す、というようにする。

代入式の扱い

C言語では代入が式なので複数つなげたり他の式と混ぜたりできる。 しかしWASMではローカル変数への格納（local.set）や線形メモリへの格納（i32.store）をするとスタックトップの値が取り除かれてしまう。 スタック上の値を複製するという命令もないので、代入した値を残しておくことができない （ローカル変数に対してはlocal.tee命令で格納しつつ値を残すことはできるが）。

そこで代入式を void 扱いにして、値を引き継げないものとするようにした。 代入式の値が引き続き使われる場合には内部的にローカル変数を確保して、カンマ演算子に変換するようにした （l = r を ((void)(tmp = r), (void)(l = tmp), tmp) と変換する）。

switch文

WASMでは構造化したジャンプしかできないが、 switch 文をどう実装したものか？ と悩んだがなんのことはない、 case の数だけ block をネストして、それぞれに br してやればよかった。

br_table という命令もあって、順に br_if する代わりにテーブルジャンプができる（やってない 追記：やった）。

可変長引数

WASMの関数の引数は数が固定で型もそれぞれ決まっている必要がある。 可変長引数をどうやって扱うかというと、やはり線形メモリで受け渡すことにする。 内部的に関数の引数を ... より前の引数+可変長引数格納先ポインタに変換してやる。

ポインタ長

ポインタは線形メモリ上のオフセットとして扱うが、オフセットは u32 なのでポインタも32bit長で十分。 なので sizeof(void*) == sizeof(long) == sizeof(int) == 4 にすることにした。 ILP32というデータ型モデルとのこと。 i64 は long long で扱うことになる。

コード側で判定できるようにするために __ILP32__ マクロが事前定義されているようにするとよい。

関数ポインタを使った関数呼び出し

WASMでは通常の関数の呼び出しは名前やラベルじゃなくて、関数に順に振られたインデクスを使って呼び出す。 関数ポインタを扱うにはそのインデクスを使ってやればできる、というわけではなかった。

関数ポインタとして扱いたい関数は別途テーブルというものに登録して、そのインデクスを使う必要がある。

古い関数プロトタイプ宣言

旧時代のC言語の関数のプロトタイプ宣言では引数を省略することもできる。 その場合、呼び出し側で与える引数の型が実体と合っているものとしてコンパイルされ、合ってない場合には誤動作する。

WASMでは呼び出す関数の引数の型や個数が合ってないと実行時エラーになるので、コンパイル時にエラーにしてやる。

ランタイム環境

バイナリにコンパイルする利点として、コンパイル時にもろもろ解決するのでランタイムを書かなくていいという点がある。 かといってスタンドアロンな実行ファイルが本当に独立しているということではなくて、OSのシステムコールに依存している。

同じようにwasmバイナリの世界では演算ができるだけなので、外部とやり取りする場合にはシステムコールに相当する呼び出しを用意してやる必要がある。 wasmからは import した関数の呼び出すとして実行できる。 open や read など、unistd 相当な関数を用意して呼び出せるようにしてやる。

ブラウザ上で動かす

また例によって、コンパイラのソース自身をコンパイルすればWebAssemblyとして動作するコンパイラが手に入るという、セルフホスティングが出来上がる。 今回はクロスコンパイルも含んでいるというのがちょっと面白い：

  1. Cコンパイラのソース(wcc.c) → gcc on Mac → wasmを吐けるMac上で動くCコンパイラ(wcc on Mac)
  2. Cコンパイラのソース(wcc.c) → wcc on Mac → wasmを吐けるwasm上で動くCコンパイラ(wcc on wasm)
  3. ランタイムを用意して、wcc on wasmをブラウザ上で動かす

Cコンパイラからwasmを吐けるようにするだけで、自動的にブラウザ上で動くCコンパイラが手に入った！というお得感がある。

あとはファイルシステムもどきをでっちあげて、 ブラウザで動くテキストエディタとしてAceエディタを組み込んで、 ボタンでコンパイル、実行できるようにしてやる。

問題点

ブラウザ上だけとは限らないが、WASMの問題点として、

  • 非同期処理を行えない
  • 明示的にも処理を譲れないので、同期でなにか処理が終わるまで待つことができない
  • プロセスを fork できない
  • 大域ジャンプできない

JavaScriptだとPromiseで非同期処理ができるが、現状wasmではできない。 むりやりやるとしたら関数を途中で区切っていったん処理を抜けさせて…となるけど、関数呼び出しがネストしてる箇所ではそうもいかない。

大域ジャンプできないと例外の処理ができないので、CやRustではいいけどC++では例外をどう扱うんだろうか。

未実装項目

goto によるジャンプは構造ジャンプに簡単には直せないので対応してない。 goto だけ無効にすれば大丈夫かというとそうでもなく、 switch 内部で case をまたいでループさせると構造を破るのでできない （Duff’s device）。

その他：構造体の値渡し・値返し、複合リテラル。（実装した）

感想

Cで書かれたコードをブラウザ上で動かせるというのはなかなか面白いかと思ったんだが、 ブラウザ上でわざわざC言語で苦労してコーディングしたいというニーズはないな、と気づいた…orz

関連記事

新着記事