MinCaml写経日記
だめぽだめぽ〜1日目〜 成果物
方針
- 実装言語にはHaskellを使う。字句解析と構文解析にはそれぞれAlex, Happyを使う。
- Haskellによる先行実装：WebAssemblyを出力するMinCamlコンパイラを実装しました - a_kawashiroのブログ こちらはParsecを利用
- AArch64のアセンブリーを出力することを目指す。
構文と型
オリジナルの Type.t は参照セルをフィールドに持っている。これをHaskellでどうするか考える必要がある。
型推論の際には STRef s _ としたいが、ひとまず任意の f :: Type -> Type を当てはめられるようにしておく。Show インスタンスは手書きする。
data TypeF f = Unit
| Bool
| Int
| Float
| Fun [TypeF f] (TypeF f)
| Tuple [TypeF f]
| Array (TypeF f)
| Var (f (Maybe (TypeF f)))
字句解析
Alexを使う。
オリジナルでは、字句解析の際にfreshな識別子を導入できるようにしている。その辺は AlexUserState を使った。
ネスト可能なコメントの扱いはサンプルのhaskell.xを参考にした。
MinCamlは字句解析の際に Array.create を解釈している。割り切りがすごい。
構文解析
Happyを使う。
shift/reduce conflictが地獄。 happy -iinfo.txt Parser.y でヒントを獲得できる。括弧を使わずにタプルを生成できるのはなんなん？
最終的に、 %left, %right, %prec などの「おまじない」には頼らない方針を採った。その場合、 x + let y = z in a.(0) <- y; y などが受理されるように頑張る必要がある。
最近のHappyにはparameterized productionsというのがある。それをうまく使えば……と思ったがそこまでうまくいかなかった。多分「何にもマッチしないnon terminal」があれば勝つる。
本当は状態を導入してfreshな識別子や型変数を生成できるようにする必要があるが、それはまた明日。
だめぽ〜2日目〜 成果物
構文解析（続き）
「概説」のparser.mlyにはshift/reduce conflictが残っていた（GitHub版では修正済み）らしいので、そのまま移植してもshift/reduce conflictが残るのは当然だった。脱力。
- Fix parsing app expression and remove all s/r conflicts by rhysd · Pull Request #5 · esumii/min-caml
昨日の続きとして、状態を持たせてfreshな識別子を生成できるようにした（; の脱糖に必要）。freshな型変数は後のパスで割り当てることにする。
昨日の段階ではルールに重複が多かったが、若干改善した。
型推論
MinCamlにはlet多相もモジュールシステムもない。なので、やるだけ。
細かいことを言うならHaskellにもor patternが欲しい。
型推論の型と構文木の型はそれぞれ TypeF Identity, ExpF Identity だったのが、型推論の最中は TypeF (STRef s), ExpF (STRef s) に変化し、型推論終了後は TypeF Identity, ExpF Identity に戻る。そのための変換関数
mapTypeM :: Applicative m => (f (Maybe (TypeF f)) -> m (TypeF g)) -> TypeF f -> m (TypeF g)
mapExpM :: Applicative m => (T.TypeF f -> m (T.TypeF g)) -> ExpF f -> m (ExpF g)
を用意した。本当は TypeF の Var の定義を Var (f (TypeF f)) にして TypeF (Const ()) → TypeF (STRef s (Maybe _)) → TypeF Identity みたいに型を変化させるべきなのかもしれない。
K正規化
OCamlでのグローバル変数だとかエラーの類はHaskellではモナドでやる。K正規化で使う副作用は
- グローバル変数（読み取りのみ）：
extenv - 状態：識別子の生成に使うカウンター
- エラー：外部変数が対応していない使い方をされていた場合にエラーを出す（一方、assert falseに相当する部分はerrorを使った）
である。なので、
type M = ReaderT (Map.Map Id Type) (StateT Int (Either String))
みたいなモナドを定義してやる。
それ以外に特筆するべきことはない。やるだけ。
α変換
やるだけ。
だめぽ〜3日目〜
とりあえず動かしたいので、最適化は後回しにしてコード生成から着手することにする。
1日目に書き忘れたけど、オリジナルのMinCamlのパーサーの挙動を確かめるのには
を使わせて頂いた。自分のマシンにOCamlを入れて手元で試せというのはごもっとも。
クロージャ変換
状態としてオリジナルのコードでは toplevel というグローバル変数を使っている。Haskellでは State モナドを使うことにする。
昨日一昨日の部分でもあった気がするけど、オリジナルではところどころでログを出力している。Haskellではそういうのはやりにくい。Debug.Trace みたいなやつはあるけどあれはマジのデバッグ用なので動作ログに使うのはなんか違う。Writer 系のモナドを活用するべきか？そこまでしなくていいか？
仮想マシンコード生成
ここからはSPARCとAArch64で違ってくる……と言いたいところだが、どちらもRISCで似たもの同士というか、MinCamlがSPARC特有の機能を使ってなさそうというか、オリジナルの SparcAsm.exp はほぼそのまま使い回せるのではないかと思われる。ニーモニックの名前がちょいちょい違ったり（SPARCでは即値を代入するのに set を使うっぽいが、AArch64では mov）するが、コード上の名前はオリジナルのSPARCに沿ったものを使おうと思う。あと即値の範囲も違うかも。
実際のコード生成では浮動小数点数の定数テーブルを作っているわけだが、オリジナルのMinCamlではその際に比較をイコールで行ってしまっているので、0.0 と -0.0 が同一視されてしまう。以下のコードで違いが出るはず：
let rec f x = x /. 0.0 = x /. -0.0 in
if f (cos 0.0) then print_int 1 else print_int 0
このコードはOCamlで実行したら0が出力されるが、MinCamlだと1になるんじゃないかな。アセンブリを眺めただけで動かせてないけど。
今日は構文木を含む AArch64Asm.hs を書いたところで終わり。実際のコード生成を行う Virtual.hs は明日以降にする。
だめぽ〜4日目〜 成果物
仮想マシンコード生成（続き）
Virtual.hs を書いた。
状態としては、識別子生成のためのカウンターと、浮動小数点数の定数テーブルを持たせる。
元のSPARCのコードは整数とポインターが4バイトだったようだが、AArch64では8バイト（64ビット）が自然である。なので、offsetの計算は適宜変更する。また、align関数は必要なくなると思う。
だめぽ〜5日目〜
アセンブリ生成
レジスタ割り当てよりも先にアセンブリ生成をやって、雰囲気を掴むことにした。
状態は
- ラベル生成用カウンター
- すでにSaveされた変数の集合 (stackset)
- Saveされた変数の、スタックにおける位置 (stackmap)
である。このほか、Readerモナドでアセンブリの出力先となる Handle を与える。ストリームへの出力にIOアクションを使うので、今回のモナドは
type M = ReaderT Handle (StateT (Int, Set.Set Id, [Id]) IO)
となる。
オリジナルのSPARC版はところどころSPARCっぽさがあるというか、ジャンプの類の後にNOPが挟まっていたり、! delay slot というコメントがついた命令があったりする。なので、どちらかというとPowerPCの方を参考にするべきだったかもしれない。
SPARCやx86 (gas)のアセンブリではレジスタの名前は % から始まるようだ。一方、AArch64のレジスタの名前は % がつかない。ここでは、プログラム内部での名前は % から始めておいて、アセンブリ出力時に % を剥がすことにした。PowerPC版もそのようにしているようだ。
現段階では、 let x = 123 in print_int x というコードに対して
.text
.align 3
.text
.global min_caml_start
min_caml_start:
.global _min_caml_start
_min_caml_start:
mov <x.1>, #123
mov x2, <x.1>
str x30, [x0, #0]
add x0, x0, #8
bl min_caml_print_int
sub x0, x0, #8
ldr x30, [x0, #0]
ret
というような擬似アセンブリを出力する。 <> で囲われているのはまだレジスタ割り当てをしていない変数だ。
だめぽ〜6日目〜
小ネタ
MinCamlでは倍精度浮動小数点数をアセンブリとして書き出す際にgethi, getloという関数で浮動小数点数を表すビット列を得ている。x86のemit.mlを見るとリトルエンディアンにも関わらずgethi/getloの順番で書き出していてバグなのではと思ったが、Cで実装されたgethi, getloがリトルエンディアン環境では名前に反した動作を行うため、結局問題はないのだった。MinCamlをクロスコンパイラとして動作させる場合は問題になるかもしれない。
MinCamlは比較演算子 <, <=, >, >= を内部的には全て一旦 <= に変換している。すると浮動小数点数のunorderedな関係の場合を正しく扱えないことになるが、ここは「割り切り」の一環と解釈できるだろう。
レジスタ割り当て
いよいよ「MinCamlコンパイラでもっとも複雑な処理」、レジスタ割り当てに取り掛かる。
レジスタ割り当てを実装するのは初めてなので、他の教材も当たってみた。具体的にはタイガーブックを読んでみたが、結構難しそう。
ネットで調べた感じ、linear scanという割と高速だが伝統的な方法と比べると生成されるコードの速度は劣る（？）アルゴリズムが1999年に出ているらしい。タイガーブックの原著は1998年だからlinear scanには触れていない。
- Massimiliano Poletto and Vivek Sarkar. 1999. Linear scan register allocation. ACM Trans. Program. Lang. Syst. 21, 5 (Sept. 1999), 895–913. https://doi.org/10.1145/330249.330250
「低レイヤを知りたい人のためのCコンパイラ作成入門」はスタックマシンでレジスタ割り当てはやっていないらしいが、同じ作者のrui314/9cc: A Small C Compilerはlinear scanによるレジスタ割り当てをやっているようだ。
理屈を考えるのは写経しながらでもいいか、と思ってとりあえず写経を始めたが終わらなかった。
だめぽ〜7日目〜
レジスタ割り当て（続き）
写経を終わらせた。理解は後で。
動作確認
これで動作に必要な部分は一通り実装したので、 libmincaml.S と stub.c を用意すればプログラムが動かせるはずだ。
……が、あちこちにバグがあり、今日はフィボナッチを動作させるところまでは至らなかった。
動かそうとしているやつ：
let rec fib a b = if a >= 100 then () else (print_int a; fib b (a + b)) in fib 0 1
〜8日目〜 成果物
動作確認
引き続き、細かいバグを潰した。
フィボナッチ数の出力に使う print_int がめちゃくちゃな値を表示するので訝しんでいたが、Darwin上では可変長引数関数の呼び出し規約がAArch64標準と異なるのが原因だった。
例えば
#include <stdio.h>
int main() {
return printf("%lld\n", (long long)42);
}
というコードがあった場合、AArch64標準の呼び出し規約では42はレジスターx1に格納されるが、Appleの呼び出し規約では可変長引数は常にスタックで渡されるのだ。Haskell界隈でこの問題はよく知っていたくせに気付くのが遅れた。
原因がわかれば対処は簡単で、printfをラップする関数をCで書いて、それをアセンブリーから呼び出せば良い。アセンブリー側で呼び出し規約の違いに対処するのはできなくはないが面倒だ。
int min_caml_print_int_impl(int64_t x) {
return printf("%" PRId64, x);
}
というわけで、フィボナッチの例を動作させることができた。
体裁を整える
これまでは標準入力からソースコードを受け取って標準出力に書き出していたが、コマンドライン引数を解釈するようにした。optparse-applicativeを使った。
オリジナルに似せて --inline m と --iter n オプションを取るようにした（最適化器がまだなので指定しても何も起こらないが）。このほか、 --print-intermediates というオプションを指定すると途中の段階のAST等を表示するようにした。
テスト
オリジナルの（OCamlで実装された）MinCamlをgit submoduleで引っ張ってきてテストを（個別に）試せるようにした。
even-odd.mlを実行するとassertionが落ちる問題にぶち当たったが、仮想マシンコード生成やレジスタ割り当てとかの際にダミーの変数名を "_" にしていた（本来はgentmpするべき）のが原因だった。ID用のカウンターを（モナドで）引き回してユニークな変数名を生成するようにして解消した。
が、今度は何も表示されない。デバッグは続く。
だめぽ〜9日目〜
テスト（続き）
昨日、even-odd.mlで何も表示されなかったのは、末尾でないクロージャー呼び出しにblrではなくbrを使っていたのが原因だった。
細々したバグを直したり、足りない関数を実装したり、コマンドとしての使い勝手を改善したりして、アーキ非依存なテストは大体通るようになった。通るというか、動作確認しただけでリファレンス実装との出力の差分は取ってないけど。
次は大きなプログラム、レイトレーシング（min-rt）を動かしたい。が、エラーが出た位置がわからないとコンパイラーのデバッグにも困るので、字句解析の際にソースの位置情報を生成して構文木に貼り付けるようにした。 その結果242行目でエラーが出ることがわかったが、今日はここまで。 →型変数のunificationにバグがあった。修正したらアセンブリ生成まで漕ぎ着けた。
だめぽ〜10日目〜 成果物
レイトレ
足りない数学関数とか入出力関数とかを実装して、グローバル変数（min-rtはグローバル変数を外部変数として定義している。多分クロージャを作らないため）も用意してやったら、レイトレが動くようになった。
生成したcontest.ppmはこれ：
東大の情報科学科の「CPU実験」の報告記事でお馴染みのやつだと思う。
MinCamlの最適化はこれから実装するわけだが、所要時間を比較できると便利かと思ってstub.cに --time オプションを実装した。
CPU実験のやつはFPGAで動く独自アーキで、レイトレの実行には20秒前後かかるらしい。一方、大企業の力が惜しみなく注がれた商用CPUではどうかというと、
- Apple M1 (3.2GHz): 0.44秒
- Raspberry Pi 4 (Cortex-A72 / 1.5GHz): 5.86秒
という結果となった。既に十分速い気がするというか、MinCaml側で最適化を実装しても誤差程度しか縮まらなかったらどうしよう、という気分になる。
レジスタの使い方
現状stack pointer（ISAで規定されたものではなく、独自）とheap pointerにはそれぞれx0とx1を使っているわけだが、Cで書かれた外部関数を呼び出す際に退避させるのが面倒なので、x19〜x28のcallee-saved registerを使うようにした方がいいかもしれない。
MinCamlは引数の個数が使えるレジスタの数に制約される。現状のHaskell実装は制約をオーバーしてもエラーが出ない気がするので、その辺のチェックも今後追加したい。
発展として、スタックとして独自確保したメモリ領域ではなくネイティブの（？）スタックを使うようにする、という方向性もアリかもしれない。その場合、「下方向に伸びる」とか「16バイトアライン」とかの制約に縛られることになるが……。
方向性
今後は最適化を実装していくことになるが、それが終わったらどうするか。
私が労力を注ぐべき本命のコンパイラーはLunarMLなので、Haskell版MinCamlは必要最小限の機能で済ませたい。つまり、本家MinCamlが実装していないような機能、多相関数やGCは実装しない。
一方で、バグ取りやコードの読みやすさ（リファクタリング、ドキュメント）には多少手間をかけてもいいと思っている。
だめぽ〜11日目〜
体裁
READMEとかLICENSEを書いてプロジェクトの体裁を整えた。
最適化
実装した。
レイトレは
- Apple M1 (3.2GHz): 0.43秒
- Raspberry Pi 4 (Cortex-A72 / 1.5GHz): 5.4秒
程度になった。Apple M1では有意差は出てない気がする。何十回も実行して統計を取れば違うのかもしれない。ラズパイでは明確に速くなった。
ログ
オリジナルのMinCamlでは各フェーズで動作ログを出している場合がある。Haskellでログを出すのは副作用なのでこれまでは省略してきたが、頑張って出すことにした。