例のアレをWebAssemblyで動かした

概要

min-caml向けのWebAssemblyバックエンドを実装し、レイトレをWebAssemblyにコンパイルして動かしました。

デモ： min-caml用WebAssemblyバックエンドのデモ — uhyohyo.net

背景

min-camlは、OCamlのサブセット向けの小さなコンパイラです。ほどよい小ささとソースコードの分かりやすさ*1から、筆者の学科では教育用に用いられています。

github.com

CPU実験という授業でコンパイラを担当する人（コンパイラ係）は、このmin-camlを改造し（一からコンパイラを実装する選択肢もありますが）、最適化を追加したり、独自のアーキテクチャ向けのバックエンドを実装したりします。

今年度はコンパイラ実験のTAをやっているのでmin-camlのソースコードを読む機会が多くなり、2年前にコンパイラ実験を受講したときのことが懐かしくなったためmin-camlをいじってみることにしました。

WebAssemblyは近年注目されている技術で、その名の通り、ウェブ用の低レベルなプログラミング言語です（詳しくは後述）。同じウェブ用の言語としては言わずとしれたJavaScriptが存在しますが、WebAssemblyはJavaScriptを置き換えるものではなく今後共存していくものであるとされています。また、アセンブリというと速そうですが実際はJavaScriptに比べて実行速度が速いわけではないというのが定説です。その代わり、パースにかかる時間がJavaScriptに比べて大きく短縮されるのが強みであるとされています。

最近のWebAssemblyの隆盛を見て、自分もWebAssemblyを勉強したいと思っていましたが、使う機会が無く困っていました。そこで、min-caml用のWebAssemblyバックエンドを作ればmin-camlをいじれるしWebAssemblyの勉強になるので一石二鳥になるということで今回実装するに至りました。何だかんだでWebAssemblyの仕様がそこそこ分かりました。

CPU実験ではレイトレーシングのプログラムが与えられます。それをコンパイルして正しく動作させることがコンパイラ係の目標となります。上の画像は、レイトレーシングのプログラムによって生成されるもので、CPU実験を知っている人の間では有名なようです。そこで、今回もWebAssemblyでレイトレプログラムを動かし、この画像を出力するところまで行いました。

結果

できたものはGitHubの↓このブランチにあります。 github.com

結論としては、WebAssemblyのバックエンドを作るのは（とりあえず作るだけなら）比較的簡単です。

min-camlにおいてバックエンドを実装するというのはClosure.tから先の変換を実装することを指しますが、実はWebAssemblyというのは関数呼び出しとかローカル変数とかいう概念があり、なんとローカル変数は任意の数使用することができます。レジスタ割り当て、レジスタの退避・PCの管理といった一般の機械語との間にあるようなギャップがありません。

なので、実装したらできました。（バグ取りはすこし苦労しましたが。）

ただし、オリジナルのmin-camlにWebAssemblyバックエンドを追加しても、レイトレプログラムを動かすにはまだ小さくないギャップがあります。そこで、ここは少しずるをして、2年前に独自アーキテクチャ向けに改造したmin-camlのバックエンドを今回の実装で置き換えました。

上でも掲載しましたが、実際にブラウザ上でWebAssemblyが実行されるデモを用意しました。

min-caml用WebAssemblyバックエンドのデモ — uhyohyo.net

*1:関数名を除けば。