HaskellでつくるAArch64版MinCaml

前回の記事

ではBrainfuckコンパイラーを書きましたが、やはりレジスター割り付けもしないコンパイラーでは物足りないと思ったのでした。

コンパイラーを作るオンラインの教材として前回の記事ではMinCamlと「低レイヤを知りたい人のための〜」を挙げましたが、後者はレジスタ割り付けはやらないみたいなので、MinCamlをやっていくことにします。

単にAArch64対応させるだけなら元のMinCamlとの差分だけを書けば良いのですが、どうせなのでHaskellに移植します。

先に成果物を載せておくと、

です。

作業記録は

に書きましたが、この記事でも要点をまとめておきます。

目次

MinCaml雑感

オリジナルのMinCamlは

で解説とソースコードが公開されています。

MinCamlはOCamlのサブセットですが、コンパイラーを単純にするために機能はかなり削られています。

型システムで言えば型推論はあります（というか型注釈の文法がない）が多相型はありませんし、ランタイムで言えばGCも配列の範囲外検査もありません。こういう「割り切り」は随所に見られます。

私は「割り切った単純なサブセットから作る」というのが苦手で、LunarMLは最初から色々実装していった結果Hello worldを通すのに2年以上かかっています。そうならないために「割り切り」は重要なのです。MinCamlの割り切り方は勉強になります。

方針

オリジナルはOCamlで実装されていますが、ここではHaskellで実装します。字句解析と構文解析にはそれぞれAlex, Happyを使います。

HaskellでMinCamlを再実装した例は

などがあるようです。

ターゲットとしては、AArch64のアセンブリーを出力することを目指します。

構文と型

オリジナルの Type.t は型変数の単一化用に参照セルをフィールドに持っています。これをHaskellでどうするか考える必要があります。

型推論の際は型変数の部分は STRef s _ としたいですが、ひとまず任意の f :: Type -> Type を当てはめられるようにしておきます。

data TypeF f = Unit
             | Bool
             | Int
             | Float
             | Fun [TypeF f] (TypeF f)
             | Tuple [TypeF f]
             | Array (TypeF f)
             | Var !(f (Maybe (TypeF f)))

type Type = TypeF (Const Void)

型推論が終わった後は型変数は必要ないので Const Void で消せるようにしておきます。

識別子の生成

オリジナルのコードではグローバル変数を使ってプログラムのどこでもfreshな識別子を導入できるようにしています（genid/gentmp）。Haskellでそういうことを真っ当にやりたければモナドを使うことになります。

モナドで扱うべき状態が識別子用のカウンターだけであれば StateT Counter m みたいなやつを使えばいいのですが、処理によっては複数の状態変数にアクセスする必要があります。

ここでは、HasCounterという型クラスを導入してみました。あとlensを使ってみましたがそこまでしなくてもよかったかもしれない。

字句解析

Alexを使います。

オリジナルでは、字句解析の際にfreshな識別子を導入できるようにしています。その辺は AlexUserState を使いました。

ネスト可能なコメントの扱いはAlexのサンプルのhaskell.xを参考にしました。

MinCamlは字句解析の際に Array.create （と、最近の版では Array.make）を解釈しています。大胆な割り切りです。

構文解析

Happyを使います。

「概説」に載っているバージョンはshift/reduce conflictが解消されていない状態のようで、そのままHappyに移植したところ地獄を見ました。GitHubの版は解消済みのようです。

ちなみに、Happyでは happy -iinfo.txt Parser.y でconflictに関するヒントを得ることができます。

文法について愚痴っておくと、これは元のOCamlがそうなのですが、括弧を使わずにタプルを生成できる文法はしんどいです。サブセットなんだから括弧を必須にしても良かった気がします。人の好みかもしれませんが。

yaccライクなパーサージェネレーターでは %left とか %prec などの指示子を使ってshift/reduce conflictを解消するかと思いますが、ここではそういう「おまじない」には頼らない方針を取りました。LunarMLでもそういう「おまじない」には頼らない方針をとっています。

おまじないに頼らない場合、優先順位に従って非終端記号を定義していけば良いのですが、その場合 x + let y = z in a.(0) <- y; y みたいな、「二項演算子の右側にletとかが来てそっちに元の二項演算子よりも優先順位の低いやつが来る」パターンを解釈できるように頑張る必要があります。

最近のHappyにはparameterized productionというのがあるので使ってみました。

MinCamlではパーサーの段階で ; の脱糖を行なっており、パーサーに状態を持たせてfreshな識別子を生成できる必要があります。Happyではモナドが使えるので、Haskell版でもそうしました。一方、freshな型変数は後の処理（型推論の直前）で割り当てることにします。

MinCamlでは内部的には大小比較は全て <= として表しています。MinCamlでは関数の引数の評価順についてルーズ（というか、元になったOCamlでもそのはず）なので、構文解析の段階で e1 < e2 は not (e2 <= e1) みたいな感じに順番がひっくり返されています。

なお、型エラーを出す際に位置情報があると便利なので、字句解析と構文解析の際にソースの位置情報を構文木に貼り付けるようにしています。

最初、自分のマシンにオリジナルのMinCamlを導入するのが面倒だったので、パーサーの挙動を確かめるのに

を使わせて頂きました。その後自分の環境にも本家MinCamlを入れましたが。

型推論

MinCamlにはlet多相もモジュールシステムもありません。なので、やるだけです。

細かいことを言うとHaskellにもor patternが欲しいです。

構文解析で出てきた型と構文木の型は TypeF Identity, ExpF Identity でしたが、型推論の最中は TypeF (STRef s), ExpF (STRef s) となり、型推論の終了後は TypeF (Const Void), ExpF (Const Void) に変化します。

K正規化

OCamlでのグローバル変数だとかエラーの類はHaskellではモナドでやります。K正規化で使う副作用は

  • グローバル変数（読み取りのみ）：extenv
  • 状態：識別子の生成に使うカウンター
  • エラー：外部変数が対応していない使い方をされていた場合にエラーを出す（一方、assert falseに相当する部分はerrorを使いました）

です。なので、

type M = ReaderT (Map.Map Id Type.Type) (StateT Id.Counter (Either String))

みたいなモナドを定義してやります。

それ以外に特筆するべきことはありません。

α変換

やるだけです。

最適化は後回し

概説の順番的には次はβ簡約なのですが、早く動かしたかったのでコード生成部を先に実装することにしました。まあ結局最適化の部分は1日で実装できたので順番を入れ替える必要はなかったのかもしれませんが。

クロージャ変換

オリジナルのコードでは toplevel というグローバル変数を使っています。例によって State モナドを使うことにします。

仮想マシンコード生成

ここからはSPARCとAArch64で違ってくる……と言いたいところですが、どちらもRISCで似たもの同士と言うか、MinCamlがSPARC特有の使ってなさそうというか、オリジナルの SparcAsm.exp はほぼそのまま使い回せるのではないかと思います。

ニーモニックの名前がちょいちょい違ったりしますが、コード上の名前はオリジナルのSPARCに沿ったものを使おうと思います。例えばレジスターに即値を代入する命令はSPARCでは set でAArch64では mov ですが、Haskell版MinCamlでもSPARC流の Set を使います。

実際のコード生成では浮動小数点数の定数テーブルを作っているわけですが、オリジナルの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が出力されます。

この件はGitHubで報告しましたが、won’t fixみたいな感じに終わりました。残念。

一方、私のMinCamlでは 0.0 と -0.0 を区別します。

ついでにもう少し浮動小数点数の話をしておくと、MinCamlは内部的には比較演算を全て <= として表しています。すると浮動小数点数のunorderedな関係（NaNが絡むやつ）をちゃんと扱えないことになりますが、これは「割り切り」の一環ということで良いでしょう。ちゃんと扱おうとするとASTのノードを増やす必要があるので……。

仮想マシンコード生成では、状態として識別子生成のためのカウンターと、浮動小数点数の定数テーブルを持たせます。

元のSPARCのコードは整数とポインターが4バイトだったようですが、AArch64では8バイト（64ビット）が自然です。なので、offsetの計算は適宜変更します。また、align関数は必要なくなると思います。

そういえばAArch64ではldr/strの際にオフセットを3ビットシフトできるので、シフト演算（SLL）は要らないんじゃね？って感じがします。

アセンブリ生成

レジスタ割り当てよりも先にアセンブリ生成をやって、雰囲気を掴みます。

状態は

  • ラベル生成用カウンター
  • すでにSaveされた変数の集合
  • Saveされた変数の、スタックにおける位置

です。このほか、Readerモナドでアセンブリの出力先となる Handle を与えます。ストリームへの出力にIOアクションを使うので、今回のモナドは

data S = S !Id.Counter (Set.Set Id) [Id]
type M = ReaderT Handle (StateT S IO)

となります。

SPARCにはdelay slotというのがあって、オリジナルのSPARC版はジャンプの類の後にNOPが挟まっていたり、! delay slot というコメントがついた命令があったりします。なので、参考にするならPowerPCの方が良いかもしれません。

SPARCやx86 (gas)のアセンブリではレジスタの名前は % から始まるようです。一方AArch64のレジスタの名前には % がつきません。PowerPC版でもそうしているようですが、AArch64版ではプログラム内部では % から始まる名前を使い、アセンブリ出力時に % を剥がすことにしました。

Brainfuckの記事にも書きましたが、AArch64のDarwinとそれ以外ではadrp/addでラベルのアドレスをレジスタに設定するときのやり方が少し違います。ここではHaskellの System.Info モジュールの os を見て判別することにしました。クロスコンパイルする人はそんなにいないと思われるので。

クロスコンパイルと言えば、AArch64はエンディアンがどっちでもいけるみたいな話がありますが、ここではリトルエンディアンを仮定しておきます。浮動小数点数の書き出しに使います。まあ .long じゃなくて .quad とかを使えばいいのかもしれないけど……。

レジスタの使い方

AArch64には汎用レジスタは31個ありますが、いくつかはABIで用途が決まっています。

自由に使えそうな汎用レジスタはr0…r15, callee-savedなr19…r28の2グループでしょうか。浮動小数点数・SIMDレジスタはv8-v15の下位64ビットがcallee-savedなことに留意すれば自由に使えそうです。

MinCamlでは独自のスタックとヒープを持ち、そのアドレスを常時特定のレジスタ上に持っています。AArch64の場合は、これらはcallee-savedなレジスタに置くのが便利です。

ここでは、

  • 汎用：x0…x15
    • うち、closure address (reg_cl): x14
    • temporary for swap: x15
  • 浮動小数点数：d0…d7, d16…d31
    • temporary for swap: d31
  • 独自stack pointer：x27
  • 独自heap pointer：x28

としました。return addressはABIで決まっているx30を使います。

汎用レジスタのtemporary for swapはx16, x17あたりを使っても良かったかもしれません。

レジスタ割り当て

「MinCamlコンパイラでもっとも複雑な処理」、レジスタ割り当てです。

理屈は後回しにして、とりあえず写経しました。

レジスタ割り当てを実装するのは初めてなので、他の教材も当たってみました。具体的にはタイガーブックを読んでみたが、結構難しそうです。

ネットで調べた感じ、linear scanという割と高速だが伝統的な方法と比べると生成されるコードの速度は劣る（？）アルゴリズムが1999年に出ているらしいです。タイガーブックの原著は1998年だからlinear scanには触れていません。

「低レイヤを知りたい人のためのCコンパイラ作成入門」はスタックマシンでレジスタ割り当てはやっていないらしいですが、同じ作者のrui314/9cc: A Small C Compilerはlinear scanによるレジスタ割り当てをやっているようです。

動作確認

後はアセンブリで記述された（MinCamlの呼び出し規約に従う）各種ルーチン libmincaml.S とmain関数を含む stub.c を用意すればプログラムが動かせるようになるはずです。

Hello world的に画面に何か数字を出したい場合は、 printf("%lld", x) みたいなコードを書いてやればいいわけですが、Darwinの場合はここに罠があって、可変長引数関数の呼び出し規約がAArch64標準と異なります。おのれApple。

例えば

#include <stdio.h>
int main() {
    return printf("%lld\n", (long long)42);
}

というコードがあった場合、AArch64標準の呼び出し規約では42はレジスタx1に格納されるわけですが、Appleの呼び出し規約では可変長引数は常にスタックで渡されます。

C言語ではプロトタイプ宣言の有無が致命的になるケースですね。こわいこわい。

対処としては、アセンブリの側で #if で切り分ける方法もありますが、C言語側でprintfをラップする固定長引数関数を書いてそれをアセンブリから呼び出してやるのが手っ取り早いかと思います。Haskell界隈でもそうしています。例えば

int min_caml_print_int_impl(long long x) {
    return printf("%lld", x);
}

てな感じですね。

その他細かい話はZennのスクラップに書いた日記の方を見ていただくとして、結論から言うと例のレイトレことmin-rtが動きました。

min-rtは実行中になるべくクロージャを作らないことを目標にしているらしく、その成果グローバル変数がMinCamlの外側で定義されています。そのため、グローバル変数を定義したアセンブリソースを用意する必要があります。

生成されたcontest.ppmはこれです：

東大の情報科学科のCPU実験ではFPGA上の独自アーキで20秒とかかかるようです。一方、大企業の資本が惜しみなく注がれた商用CPUでは、

  • Apple M1 (3.2GHz): 0.44秒
  • Raspberry Pi 4 (Cortex-A72 / 1.5GHz): 5.86秒

という感じになりました。

ちなみに、最適化を実装した後は

  • Apple M1: 0.43秒（誤差？）
  • Raspberry Pi 4: 5.4秒

となりました。Apple M1の方は統計的な何かをしなければ違いがわからないかもしれません。

最適化

後は最適化を実装するだけです。レイトレが動いた後だと消化試合感が出てきます。

まあ、難しい最適化はやってないし、やるだけです。やりました。

コードサイズ比較

オリジナルのMinCamlのウリは小さいこと。論文によるとOCamlで書かれたコードは2040行だそうです。現在のバージョンだと

$ git ls-files *.ml *.mli *.mll *.mly SPARC/*.ml SPARC/*.mli | xargs wc -l
      99 SPARC/asm.ml
      58 SPARC/asm.mli
     254 SPARC/emit.ml
     219 SPARC/regAlloc.ml
      41 SPARC/simm.ml
     164 SPARC/virtual.ml
      46 alpha.ml
       2 alpha.mli
      22 anchor.ml
      18 assoc.ml
       1 assoc.mli
      38 beta.ml
       1 beta.mli
     106 closure.ml
      33 closure.mli
      50 constFold.ml
       1 constFold.mli
      32 elim.ml
       1 elim.mli
       1 emit.mli
      25 id.ml
      32 inline.ml
       2 inline.mli
     179 kNormal.ml
      28 kNormal.mli
     100 lexer.mll
      12 m.ml
      45 main.ml
       3 main.mli
     173 parser.mly
       1 regAlloc.mli
      11 s.ml
       1 simm.mli
      27 syntax.ml
      11 type.ml
     163 typing.ml
       3 typing.mli
       1 virtual.mli
    2004 total

なので2004行ですかね。

一方、私のHaskell版は

$ git ls-files src/*.hs src/AArch64/*.hs src/*.{x,y} | xargs wc -l
     154 src/AArch64/Asm.hs
     355 src/AArch64/Emit.hs
     251 src/AArch64/RegAlloc.hs
      62 src/AArch64/Simm.hs
     169 src/AArch64/Virtual.hs
      55 src/Alpha.hs
      17 src/Assoc.hs
      45 src/Beta.hs
     138 src/Closure.hs
      37 src/ConstFold.hs
      48 src/Elim.hs
      43 src/Id.hs
      45 src/Inline.hs
     190 src/KNormal.hs
     159 src/Lexer.x
      22 src/Logging.hs
     119 src/Main.hs
       2 src/MyPrelude.hs
     197 src/Parser.y
     105 src/Syntax.hs
      50 src/Type.hs
     239 src/Typing.hs
    2502 total

と、2502行となりました。やや多いですね。

OCamlはor patternがあるのと、Haskellだとモナド周りのあれこれがあって行数に差が出ているのかもしれません。

雑感

割とあっさりと終わってしまった……。まあ6月いっぱいとかかける気は元からなかったわけですけども。

OCamlとHaskellの違いについて。やはり副作用の扱い方が違います。OCamlだとカジュアルにグローバル変数やログ出力ができますが、Haskellだといちいちモナドを設計してやらないといけません。Functor/Applicativeの演算子とかを使うとモナドであっても簡潔に書けたりしますが、初心者に優しいかはわかりません。

今後やるべきこととして、自動テストの実装があります。今は手動で動作確認しています。LunarMLではLuaを使って自動化したりしたけど、どうするかなあ……。シェルとMakefileだけでやるのは嫌です。

発展的な方向性として、「ネイティブのスタックを使う」という方向性もあります。AArch64の場合は「下方向に伸びる」のと「16バイトアライン」に気を付けてやればOKなはずです。まあやるとしても別ブランチでしょう。

インターネットの海を見渡すとMinCamlに色々機能追加している人がいます。ですが、私の本命のコンパイラーはLunarMLなので、Haskell版MinCamlにあまりゴテゴテと機能追加してもなあという気がします。なので、Haskell版MinCamlはあくまで本家MinCamlに準じた機能とします。エラー位置のわかりやすさとか 0.0 vs -0.0 は変えましたが。あとは生成されたバイナリに --time オプションを実装して所要時間を表示できるようにしたり。

一昨年ぐらいからLunarMLに時間を使うようになって、先月末にネイティブコードを出力したいと思ってBrainfuckとかMinCamlをやったわけですが、次は何をするべきか。

昨年末に立てた目標である「機械語を出力する言語処理系（ネイティブコンパイラー）を書く」と言う目標は達成したと思っていいのか？それとも、もうちょっと別の自作言語とかをやるべきか？

あるいは、一旦言語処理系から離れるべきか？年末年始に立てた目標を改めて見直した上で考えたいです。

このエントリーをはてなブックマークに追加