MinCaml: 早期退避型レジスタ割り当ての後戻り解消

書いた後になってregAlloc.target-latespill.mlとして類似の構造が既にあったのに気が付いたので、説明は簡単にする。

MinCaml 0.0.9のオリジナルのregAlloc.mlはレジスタ溢れが発生するたびにToSpillを返して溢れた変数が定義された時点まで遡って処理をやり直す。 この構造は次の二点を目的としている。

1. 変数定義の直後に、変数をスタックに記録するSave仮想命令を挿入する。
2. (Forgetノードの効果) その命令の直後にForgetノードを挿入してレジスタから溢れる変数を以後使われないよう見せかけることで、やり直し時にレジスタ割り当てを意図したレジスタに行わせる。

Forgetは一見、挿入した直前の命令のみならずそれ以前の命令にも影響するように思えるが、溢れさせるレジスタの選択方式を考え合わせると実は影響がない。call命令直後に挿入するものは例外だが、これは自由変数の収集時にtargetと同じくcall命令より先は見ないという配慮をすれば不要にできる。

従ってやり直しはレジスタ溢れを起こした命令だけでよいので、後戻りなしでも同じレジスタ割り当てが可能である。

(上記は誤った理解に基いた記述であり、レジスタと変数の対応は変わり得る。コメント欄に頂いたご指摘及び改訂したMinCaml読解ノート: レジスタ割り当てを参照。ただしレジスタ溢れの発生回数については後戻りなしでも同じくすることがやはり可能であると考える。以後もそれを踏まえて読まれたい。)

この点を踏まえ、本変更では前述の二目的をそれぞれ次のように実現する。

1. Save仮想命令を全ての変数について挿入しておき、そのうち不要なものを最後に一括して取り除く。要不要は変数がRestoreされるかどうかで決定できる。
2. 次の命令に渡すregenv(レジスタと変数の割り当て表)を直接操作する。また、割り当てるレジスタを決定するときに、自由変数の収集を関数呼び出しより先は考慮しないようにする(targetが既に行っているのと同じ配慮)。

ソースファイルはregAlloc.target-earlyspill-nobacktrack.ml。前述のようにオリジナルのregAlloc.mlよりもregAlloc.target-latespill.mlに近く、わかりやすさはそれとほぼ同じ。

比較

ほとんどのケースで0.0.9のオリジナルのものと同等のコードを出力する。唯一、test/non-tail-if.sでは僅かによいコードを出力した。

追記: テストプログラムはないもののレジスタ割り当てが悪化するケースもあるとの指摘を頂いた。コメント欄参照。

応用

余分に挿入しておいて後から不要なものを削除する、若しくは必要なものを後から挿入するという手法はRestoreにも応用できる。

関数呼び出しによりレジスタが全て破壊されるが、ここで適当な変数を仮にRestoreしてしまうことで、その後に分岐があり一方の枝と分岐の合流後でその変数を参照するような場合にロードを削減できる場合がある。余分な仮のRestoreは最後に削除する。但しtargettingを阻害しないよう仮Restoreするレジスタには条件がつく。

regAlloc.mlのバリアント

最後に、MinCaml 0.0.9に含まれるregAlloc.mlのバリアントを簡単に紹介する。後のものほど前のものよりデグレードされている。

regAlloc.target-earlyspill.ml

regAlloc.mlと同一。

regAlloc.target-latespill.ml

後戻りなし。変数の退避を、レジスタから溢れる直前に行う。同じ変数が二度三度退避されることが起こり得る。また、割り当てるレジスタの決定では関数呼び出しより先の参照を考慮してしまう弱点が存在する(Forgetを使わないにも関わらず、前述のtargetと同様の配慮がなされないため)。

regAlloc.target-nospill.ml

後戻りなし。レジスタが不足したらコンパイルを断念する。

regAlloc.notarget-nospill.ml

後戻りなし。レジスタが不足したらコンパイルを断念する。レジスタ割り当ては次にどのレジスタに割り当てるのがよいかは考慮せず、空いているレジスタを番号の若いものから順に使う。

MinCaml 0.0.3から0.0.9の変化

MinCamlの現在のバージョンである0.0.9の、MinCaml読解ノートを作成したときのもの(バージョン0.0.3に相当するようだ)からの変化を整理した。字面や表現上の変更を除くと概ね以下の通り。

言語仕様の変更

• let recが関数定義を一つだけに簡略化された。相互再帰する関数をandで並べて定義することはできなくなった。

但し入れ子にすれば相互に呼び合う関数を定義することはできる。test/even-odd.mlを参照。

内部仕様・動作の変更

• 言語仕様の変更を反映し、構文木(Syntax.t)と中間コード(KNormal.t)でLetRecの保持する関数を一つに変更。
• Syntax.tからNEq, Ltを削除。Eq, LEとNotの組み合わせで代替する。KNormal.tの表現に合わせたもの。
• 字句解析器は負の数値リテラルを単項マイナスと非負数値の2つのトークンとして返すようになった。
• 浮動小数点レジスタはSPARCで使える16個全てを利用するようになった(以前は何故か8個だけだった)。
• 定数畳み込みで即値の伝播を浮動小数点数についても行うようになった(以前は忘れられていた)。(記述は追加されたがコメントアウトされている。意図して外していることを示すためと考えられるが、改訂した読解ノートでも指摘したように浮動小数点数でもこれを避ける理由はないように思われる。)

最後の二件は以前にMinCaml読解ノートでも指摘した点が修正されたもの。

尚、浮動小数点レジスタ個数の変更に付随してエンバグしている(実害はない)。sparcAsm.mlでのco_freg_tableの計算において、ループ回数が一回多い。

実装の変更

この二点が両バージョン間の実質的な改良点と言える。

• レジスタ割り当てコードの簡素化。参照した変数がレジスタ上にない場合の処理を、命令直前にRestore(退避した変数をレジスタへのロードする命令)を挿入した命令列のレジスタ割り当てに変換することで、問題を変数への代入時のレジスタ割り当てのみに帰着させた。
• 仮想マシンコード生成において、レコード(クロージャまたはタプル)の要素を一括してロードまたはストアするコードの生成方法が改善された。同等のコード(同一ではない)を出力しながらもロジックは単純になった。

regAlloc.mlでは関数のレジスタ割り当てを行うhからg_repeatに渡される引数がAns(Nop)からAns(Mov(a))に変更されているのだが、これの狙いはよくわからない。

このほか、理解しやすさを狙いレジスタ割り当ての処理を弱めたバリエーションが付属するようになった(regAlloc.{notarget-nospill,target-nospill,target-earlyspill,target-latespill}.ml)。

MinCaml読解ノート 目次

MinCaml読解ノートが一通り完了したので、目次として各記事へのリンクを列挙する。

MinCaml読解ノートは、MinCamlコンパイラを筆者が読んだ結果を元に理解の参考のために動作やソースコードに対する解説を加えたものであって、住井氏自身による「速攻MinCamlコンパイラ概説」による解説を補い、詳しい補足や場合によりソースコードに即した説明により読者の理解の一助となることを意図している。

MinCamlの記述言語であるObjective Camlについての知識は「超特急: 一時間でわかるML超入門」の内容のみを前提とし、その範囲を超えた機能が使われ理解を妨げそうなときには説明を付した。筆者自身も当初Objective Camlについては「超入門」を読んだだけの内容しか知らなかったので、同じようにObjective Camlの知識に乏しい方でもさほど支障は生じないと思われる。

またMinCamlがターゲットとするSPARCについてもMinCamlの理解に必要と思われる範囲で簡単に説明する記事を挿入した。

1. ビルドと全体の流れ
2. 字句解析
3. 構文解析
4. 型推論
5. K正規化
6. α変換
7. β簡約
8. ネストしたletの簡約
9. インライン展開
10. 定数畳み込み
11. 不要定義削除
12. クロージャ変換
13. SPARC概要
14. 仮想マシンコード生成
15. 13bit即値最適化
16. レジスタ割り当て
17. アセンブリ出力

MinCaml読解ノート: アセンブリ出力

ようやく最終フェーズである。いよいよasに与えるアセンブリソース(*.s)を出力する。このフェーズの各関数に共通する引数ocはファイル(*.s)への出力チャネルである。

基本的には仮想マシンコードの命令に対応するアセンブリを出力するだけである。 但し次の仮想命令に伴う処理が必要となる。

• Save, Restore: スタックからのロード・ストアを生成。スタック上の変数の配置とその管理。
• IfEq等の条件分岐: 分岐命令、それぞれの分岐のコード、ラベルとジャンプ命令の生成。
• CallDir, CallCls: レジスタへの引数のセット。末尾呼び出しでない場合はスタックポインタの操作も。末尾呼び出しの最適化。

命令列や命令のアセンブリ出力(Emit.gやEmit.g'等)には最後の値を返すレジスタの指定であるdestが与えられる。これは命令に出力オペランドを持たず、命令列も最後はAnsノードなので同様に出力先を持たないためである。

命令列のアセンブリ出力 (Emit.g)

命令列中の命令について繰り返しg'を呼ぶ。その出力先はNonTail(Letが保持する出力レジスタ)であるが、命令列の末尾(Ansノード)ではdestを渡す。

命令のアセンブリ出力 (Emit.g')

TailとNonTailで大きく分かれる。

NonTailの場合は出力レジスタが与えられているので命令をそのままアセンブリ出力する。

Tailの場合は戻り値を返すレジスタを使って同様に出力した後、関数から戻るret命令を生成している。アセンブリ命令を一旦バッファに入れ、retを一つ前の命令と順番を入れ替えれば無駄なnopを無くせるが、そこまではやっていない。

Save, Restoreとスタックの管理

Save, Restoreはスタック上の変数へのストア・ロード命令に変換される。

スタック上の変数の配置を管理するのは大域変数のstackmapとstacksetである。

stackmapはスタック上の配置を表す変数名のリストである。MinCamlで扱うオブジェクトが1ワードのもの(整数やポインタ)とダブルワードのもの(浮動小数点数)しかないことを利用し、後者は同じ要素2つで表す。これによって、stackmap上での添字を4倍すれば変数のスタック上の位置(スタックポインタからの相対)が得られる。浮動小数点数を挿入する場合は必要に応じて1ワードのパディングに相当するダミーの変数名を先に追加する。

関数やクロージャが呼ばれるときは、スタックの先頭にreg_raが保持している現在の関数からのリターンアドレスを退避してから呼び出す。

これを示すようにstacksizeは変数の占める大きさより常に1ワード大きく計算する。

条件分岐命令のアセンブリ出力 (g'_tail_ifまたはg'_nontail_if)

スタックの状態を管理するstacksetが大域変数なので、保存して巻戻しつつ分岐するときとしないときの命令列をそれぞれ出力している。stacksetのみを巻戻しstackmapは触らないのは意図されたもので、これにより真偽それぞれの場合の命令列で同じ変数が異なるアドレスに割り付けられることを防いでいる。

g'_tail_ifの方はそれぞれの命令列の先でリターンするので簡単であるが、g'_nontail_ifは合流のためにラベルとジャンプを生成する必要がある。

関数適用・クロージャ適用のアセンブリ出力 (Emit.g')

まずg'_argsで引数(とクロージャへのポインタ)をレジスタに載せるコードを生成する。

このとき移動する順番をうまく考えないと、必要な値を他にコピーする前にレジスタを上書きしてしまいかねない。この順番を工夫するのが関数shuffleである。

猶、クロージャの自由変数は関数先頭でクロージャレコードからロードするコードが既に生成されている。仮想マシンコード生成を参照のこと。

現在の関数からのリターンアドレスをreg_raが保持しているが、これも関数呼び出しで破壊されるのでスタックの先頭に退避する。

末尾呼び出しであれば呼び出し先の関数にジャンプする。

そうでない場合はスタックポインタをスタックの先頭に進めてからcall命令で呼び出し、戻ってきたらスタックポインタを戻す(スタックポインタを進める命令はcall命令の次に書いてあるが、SPARCの性質によりcall命令より先に実行される)。その後reg_raにリターンアドレスを復元する。

ある関数でのスタックの使われ方は図のようになる。この例ではvar1, var2, var3, fvar1がレジスタ溢れによってスタックに退避される変数であり、そのうちfvar1は浮動小数点数である。raddrはreg_raから退避するリターンアドレスである。

|     |
+-----+<-- reg_sp
|var1 |
+-----+
|var2 |
+-----+
|var3 |
+-----+
| -   |
+-----+
|fvar1|
+- - -+
|fvar1|
+-----+
|raddr|
+-----+<-- 別の関数を呼ぶときの reg_sp
|     |

shuffleのアルゴリズム

引数それぞれについて移動先となるレジスタに他の引数が載っていないか調べ、他の引数を破壊しないものから先にmov命令を出力する。

そうすると最後に循環するレジスタのリストが残るか、リストが空になる。

循環が残る場合はスワップ用レジスタを介してそのうち2つを入れ替えることにより循環を一つ破壊し、残りを再びshuffleする。

プログラムのメインルーチンのアセンブリ出力 (Emit.f)

min_caml_startというC関数として見えるように出力する。そのためここだけsave命令とrestore命令によりレジスタウィンドウの操作を行うコードを出力する。

このmin_caml_startはstub.cの中のmainから呼び出され、(Cの関数呼び出し規約により)%i0と%i1にそれぞれ第一第二引数として渡されたスタック領域、ヒープ領域が入る。MinCamlではこれらをそのままreg_sp, reg_hpとしている。

MinCaml読解ノート: レジスタ割り当て

レジスタ割り当てとは

変数(すなわち無限個の仮想レジスタ)の処理を有限個の実レジスタに落とし込む処理である。変数を極力レジスタに割り当て、どうしてもレジスタが足りないときは変数をスタックに割り当てて退避し、レジスタを空ける。

「概説」の要約

「概説」の説明は有用な情報を含んでいるがそのままではまとまりに欠けるので、ここで整理要約させて頂く。

• 関数呼び出し規約: 引数はレジスタに順に載せる。戻り値は第一レジスタ。これら関数の出入口の処理はRegAlloc.hで実装。
• 式(関数本体、メインルーチン)のレジスタ割り当て: RegAlloc.g。変数からレジスタへの写像regenvと命令列を受け取りレジスタ割り当てを行った命令列と新しいregenvをデータ型NoSpillで返す。
• どのレジスタに変数を割り当てるか
  1. 空いているレジスタ (生きている変数の入っていないレジスタ)
     • SparcAsm.fv: まだ生きている変数を返す (現在の式と、これから後にくる命令列contを調べる)
     • その変数が次に使われるときに置かれるレジスタをなるべく選び、将来の無駄なmovを削減する (RegAlloc.target) (register targetingまたはregister coalescing)
       • 関数呼び出しは全てのレジスタを破壊するのでそれより先は調べても無意味、戻り値にはそれを示す真偽値を含む
  2. 空きがなかったら→変数を退避してレジスタを空ける(レジスタ溢れ=register spilling)
• どのレジスタを空けるか←言及なし
• 関数呼び出しでも退避が必要 (レジスタは破壊される)→全ての生きている変数を退避
• レジスタが溢れたら
  1. RegAlloc.gは溢れの発生を示すToSpillを返す
  2. 変数をなるべく早く退避する→変数の定義時点で退避(Save命令を挿入)
  3. 退避したら「生きている変数」から除外→Forget命令を挿入
  4. 退避直後からレジスタ割り当てをやり直す
• 退避した変数を再び参照するとき
  • regenvに見つからない→RegAlloc.g'で例外発生→RegAlloc.g'_and_restoreで処理(レジスタへ変数を復帰するRestore命令を挿入)

命令列と仮想命令

レジスタ割り当てでは仮想命令と命令列が重要な役割を担うので、まずそれを整理する。

命令列は主にLetノードで構成されるリストであり、末尾はAnsである。LetとAnsはそれぞれ命令を一つ指す。

これらの命令には入力オペランドの情報はあるが、出力オペランドはその命令を持つLetが定義する変数。Ansノードの場合は、レジスタ割り当てのためには出力オペランドが外から指定されなくてはならない。全ての命令列はAnsで終わるから、命令列のレジスタ割り当ては最後に結果を返すレジスタか変数を最初に指定するということになる。

命令列を構成するノードにはもう一種類、Forgetというノードがある。これは特殊な指示ノードで、レジスタ割り当ての途中で必要に応じて挿入される。

レジスタ割り当てに直接関わる仮想命令は二つある。

Save(r, x)は変数xをレジスタrからスタック上に退避する命令である。

Restore(x)はその退避された変数xをレジスタにロードする仮想命令である。

処理階層

regAlloc.mlの中心となる部分は次のように処理単位の大きさによって関数が分かれ、上位のものがより下位の関数を呼んで処理を行う。

f

プログラム全体のレジスタ割り当て。関数をそれぞれhで変換、メインの式をg_repeatで変換して、レジスタ割り当てされた新しいプログラムを返す。

h

トップレベル関数のレジスタ割り当て。変数(クロージャと引数)とレジスタの対応をregenvに登録し、関数本体をg_repeatで変換。

g_repeat

ひとまとまりの式(メインの式や関数本体)のレジスタ割り当て。実際にレジスタ割り当てするためにgを呼ぶ。

g

命令列のレジスタ割り当て。命令列中のノード一つを扱うと共に、後続命令列を処理するため自分自身を再帰的に呼ぶ。ノードがLetの場合は次のような処理をする。

1. ノードが指す命令をg'_and_restoreで割り当てる
2. 命令の出力先レジスタを割り当てる
3. g自身を再帰的に呼んで後続命令列のレジスタ割り当てを行う

g'_and_restore

g'をラップする。

g'

一命令のレジスタ割り当てを行う。命令が条件分岐や関数呼び出しの場合はg'_ifやg'_callが担当する。

処理の流れ

レジスタ割り当ての中心は関数gである。おおよそ命令列のノード一つにつきgの呼び出しが一回ネストする。処理した命令列の長さに等しい(もしくはそれ以上の)深さで再帰呼び出しすることになる。

g以下の関数は、割り当てに成功すると戻り値としてNoSpill(レジスタ割り当て後の命令列, 命令列直後のregenv)を返す。失敗するとToSpill(割り当てをやり直す命令列, レジスタから溢れた変数のリスト)を返す。

簡単に説明するとそうなるが、レジスタから変数を溢れが発生すれば割り当てをやり直すためにToSpillを返し、一度も発生しなければNoSpillを返す、と表現する方が正鵠を射ている。溢れが発生しなかったということが結果としてレジスタ割り当ての完了も意味することになる。

ToSpillによってバックトラックが駆動される。命令列のどこかでレジスタから変数が溢れてToSpillを返されると、どんどんToSpillを返して巻き戻る。どこまで戻るかというと、レジスタから溢れた変数が定義された時点までである。

そこまで戻ると、変数を退避するSave命令をLetの直後に挿入し、再びレジスタ割り当てをやり直す。 挿入されたSave命令自身はレジスタ割り当てに影響しない。では何故やり直しで結果が変わるのかというと、ToSpillを返すときにForgetが命令列に挿入されるからである。

参照した変数がレジスタに載っていなかったら

階層の一番下、命令一つを処理するのがg'である。 g'ではオペランドを変数から対応するレジスタに置き換えた命令を返す。 無条件にNoSpillを返すように見えるが、置き換えのときに変数がレジスタに載っていなければfindの中でNoRegエラーが発生する。

g'_and_restoreはこれに対処するための仕掛けである。NoRegエラーが発生すると、参照する変数をレジスタに復帰させる為のRestore命令を直前に挿入した命令列をでっち上げ、gを呼んでレジスタ割り当てさせる。

これによって、Restore命令でどのレジスタにロードするかという問題に帰着する。

gにおけるLetの処理 前編

ここがレジスタ割り当ての中心であるので詳しく扱う。

前述の通り、ここでの処理は次の三ステップである。

1. ノードが指す命令をg'_and_restoreで割り当てる。
2. 命令の出力先レジスタを割り当てる。
3. g自身を再帰的に呼んで後続命令列のレジスタ割り当てを行う。

既に見たようにステップ1は別の問題への変換で決着した。次のステップ2が、regAlloc.ml中で唯一実際にレジスタを割り当てる箇所である。

レジスタ割り当ては関数allocを呼んで行う。この関数は空きレジスタrがあればAlloc(r)を返し、なければレジスタから溢れさせる変数yを選んでSpill(y)返す。

結果がSpillならばレジスタ溢れが発生したことを示すToSpillを返して後戻りを開始する。

Allocが返された場合はステップ3の後続命令列のレジスタ割り当てに進むので、後続命令列についてgを呼び出す。NoSpillで結果が得られた場合は、自分が変換した命令と合わせてレジスタ割り当て完了した命令列を返せばよい。問題はToSpillが返されたときである。

gにおけるLetの処理 後編: バックトラックのキャッチ

後続命令列のレジスタ割り当てでToSpillが返され、しかも溢れた変数の中にこのLetで定義した変数が入っていたら、Save命令を後続命令列の前、つまりLetの直後に挿入する。

ほかにも溢れた変数があるなら、更に後戻りするためToSpillを返す。

溢れた変数がほかになければ、これ以上後戻りはせずに再び(Saveを挿入した)後続命令列を対象にレジスタ割り当てをやり直す。

g_repeat: バックトラックの最終ライン

溢れた変数がLetで定義されたローカル変数ではなく、命令列の外から与えられた引数や自由変数であった場合、当然ながら後戻りは命令列の途中で止まらずにg_repeatまで戻ってきてしまう。

この場合もすることは同じで、溢れた変数のSave命令を挿入して割り当てをやり直す。

変数を割り当てるレジスタまたはレジスタから溢れる変数の選択

gのステップ2で呼ばれるallocがこの決定を行う。

まずfvによって以後の命令列contで生きている自由変数のリストfreeを計算する。 fvはsparcAsm.mlで定義されている関数で、命令列で参照される変数のうち、その内部で束縛されたもの以外を返す。ただし途中にForgetがあると、その変数は以後参照されないものと看做される。

次に現在それらの変数で使われているレジスタlive、出来ればこのレジスタに割り当てられれば後でmovする手間が省けてよいというレジスタのリストpreferを計算し、liveに含まれない空きレジスタをまずpreferから、次いで全レジスタの中から探す。

空きレジスタがない場合、レジスタから変数を溢れさせる。そのため、freeに含まれる変数で現在レジスタに載っているものの中で、最も次に使われるタイミングが遅いものを選んでSpillを返す。

Forgetとやり直しによるレジスタ割り当ての改善

命令列に挿入されたForgetがやり直しにおいてレジスタ割り当てを改善するのは、fvがForgetされた変数をそれ以後参照されないと看做すためである。これにより、その変数の生存期間は直前に参照された時点までで切り詰められ、そこからForget挿入までの区間でレジスタが明け渡される。

その結果、レジスタ溢れを起こした命令では空きレジスタが与えられ、レジスタ割り当てが成功する。また、明け渡されたレジスタはその区間で別の変数に使うことができ、その変数に使う筈だったレジスタは更に別の変数に使えるので、register targetingを成功させる方向でレジスタ割り当てが改善される可能性がある。

一方、この区間で以前に別の変数がレジスタ溢れを起こしていた場合に、新たに空いたレジスタの利用でそれが解消できるのではないかという疑問が湧く。

考えてみたところではそれはなさそうに思える。

まず、仮定から前後関係は「変数xの直前の参照→Forget(y)→Forget(x)→xの次の参照→Restore(y)」となる(変数yは以前の試行で溢れた変数。変数xは今回の試行で新たにレジスタ溢れとなった変数。Forget(y)からRestore(y)の間にyの参照はない)。

Forget(x)の時点で二つの変数が溢れることは変えられないので、いずれにしろForget(y)は必要になる。

レジスタ不足以外の要因によるバックトラック: 関数呼び出しとif

レジスタが不足したとき以外にも変数がレジスタから外れ、バックトラックを起こすことがある。 それが関数呼び出しと条件分岐である。

これらはそれぞれ一つの仮想命令なのでg'に渡されるが、実際の処理は専用の関数g'_callとg'_ifに書かれている。

MinCamlではcaller-saveなのでレジスタは関数呼び出しで破壊されたと看做す。つまり全ての変数の生存期間はそこで区切られるので、全変数のForgetを呼び出しの直後に挿入してバックトラックする(関数の戻り値を受ける変数を除く。その変数の生存期間は呼び出しの戻った時点から始まるからである)。

これによって呼び出しの引数にならない変数は早めにレジスタを空けることになり、引数になる変数のregister targetingが成功しやすくなる。

条件分岐はもう少し話が複雑になる。

条件分岐の枝はそれぞれ独立した命令列としてg_repeatでレジスタ割り当てを行う。つまりこれらの中でバックトラックは完結し、外には出てこない。

分岐が合流する時が問題で、まず、分岐合流時点で信じられるレジスタ割り当てregenv'を計算する。これは両方の枝の終了時点を比較して、同じレジスタに同じ変数が載っているという共通部分だけを取り出したものになる。

次に、合流後に使われる変数でregenv'に載っていないものをリストアップする。これらは枝のどこかで破壊されてしまうので、合流後も参照されるからといって分岐命令まで生かしておくことはない。そこでそのような変数は全てForgetを分岐命令の直後に挿入してバックトラックする。

これらのForgetは枝の中で参照される変数の生存までは妨げない。

regAlloc.mlで定義される関数の概要

target src dest cont

変数srcが以後の命令列で特定のレジスタで使われることがわかればそのようなレジスタのリストを返す (register targeting)

target' src (dest, t) exp

targetの下請け。

target_args src all n list

targetの下請け。

alloc dest cont regenv all x

変数xを割り当てるレジスタrを決めてAlloc(r)を返す。空きレジスタがなければレジスタから溢れる変数yを決めSpill(y)を返す。

add x r regenv

変数xとレジスタrの対応をregenvに追加する。

xがレジスタであれば何もしない。尚、MinCamlでは変数もレジスタも同じく文字列(Id.t)で表す。区別はその名前がレジスタの名前か否かでしかない。

find x t regenv

変数xに対応するレジスタを返す。xがregenvに登録されていなければ例外NoReg(x,t)を発生させる。xがレジスタであればそのまま返す。

find' x' regenv

id_or_immのx'を受け取り、即値ならそのまま返し、変数ならfindによりレジスタを返す。

forget_list xs e

insert_forgetの下請け。

insert_forget xs exp e

命令expの後にリストxsにある変数のForgetを挿入して後続命令列eと連結した命令列を作り、ToSpillを返す。g'_ifやg'_callで複数の変数をまとめてForgetするために使われる。

g dest cont regenv e

命令列eのレジスタ割り当て。

g'_and_restore dest cont regenv exp

g'を呼び、NoRegエラーが発生したらRestoreを挿入。

g' dest cont regenv exp

命令expのレジスタ割り当て。

g'_if dest cont regenv exp constr e1 e2

仮想命令IfEq等のレジスタ割り当て。

g'_call dest cont regenv exp constr ys zs

仮想命令CallDir, CallClsのレジスタ割り当て。

g_repeat dest cont regenv e

関数本体やメインの式というひとまとまりの命令列をレジスタ割り当て。

h fundef

関数のレジスタ割り当て。

f prog

プログラム全体のレジスタ割り当て。

MinCaml読解ノート: 13bit即値最適化

SPARCアセンブリの整数算術命令等では、第2オペランドとしてレジスタ以外に13ビット以内の即値をとることができる(命令ワード内にエンコードできる)。そこで、そのような命令のオペランドとなっている変数が13ビット以内の整数の定数ならば即値で置き換える。

MinCamlでいうと、SparcAsm.expで定義された命令のうちid_or_immという型を含む命令がそれに当たる。

Simm13.gではLetによるリストを順に辿り、変数(仮想レジスタ)への即値代入(Set)であって値が13ビット以内であれば変数と値の対応を記録する。それ以外の命令ならSimm13.g'によって命令ごとに変数から即値への置換を試みる。

Simm13.g'では命令を一つ受け取り、即値をとり得る命令でオペランドが記憶された変数であれば即値に置き換える。

変数の参照が全て即値に置き換えられてしまった場合は変数への代入命令自体も省略する。

MinCaml読解ノート: 仮想マシンコード生成

このフェーズではSPARCアセンブリに準じた仮想マシンコードを生成する。

「概説」によると、仮想である所以は次の2点。

• 変数(レジスタ)が無限にある
• ブランチやジャンプの代わりにif-then-elseや関数呼び出しがある

つまり、これまで変数であったものが「無限にある仮想レジスタ」という位置付けに横滑りする。 条件分岐で枝分かれする中間コードの構造は変更しない。

MinCamlのコードの規約

SPARCプロセッサの概要は既に説明したが、これからマシンコードに落とし込む上で必要となるレジスタの使い方などを整理しておく。

クロージャやタプルはヒープ上に取る。ヒープは拡大する一方で、ガベージコレクションはしない。クロージャの実体は [関数のポインタ, 自由変数1, 自由変数2, ..., 自由変数n] というレコード。浮動小数点数が入る場合、その要素がダブルワード境界になるようパディングする。タプルも同様のレコード。

MinCamlでは、次のような決まりでレジスタを使う。

スタックポインタ (reg_sp)

%i0 [Cと違う。Cは%o6がスタックポインタ]

リターンアドレス (reg_ra)

%o7 [C等と同じ]

ヒープポインタ (reg_hp)

%i1

引数

残りの汎用レジスタ全て (regs = %i2〜%i7, %l0〜%l7, %o0〜%o5)

浮動小数点数の引数

浮動小数点レジスタ全て (fregs = %f0,%f2,...,%f30)

戻り値

%i2または%f0 (汎用レジスタの最初のレジスタ)

クロージャを指すレジスタ (reg_cl)

%o5

クロージャを呼ぶときは、まずreg_clにクロージャのアドレスをセットし、その先頭にある関数へのポインタをレジスタにロードして呼び出す。

関数内では変数は全て仮想レジスタと考えるので、クロージャの自由変数は関数先頭で全部レジスタにロードしてしまう。以後はレジスタ渡しされた引数やローカル変数と区別されなくなる。

仮想マシンコードの表現

仮想マシンコードのデータ型はsparcAsm.mlで定義される。このうち、命令列のデータ型がSparcAsm.t、個々の命令がSparcAsm.expである。

type t =
  | Ans of exp
  | Let of (Id.t * Type.t) * exp * t
  | Forget of Id.t * t

Forgetは今は措くとして、命令列がLetのリストであることがより明確となった。次図のように、命令列は一連のLetと末尾のAnsによるリストとなる(ただしexpには条件分岐があり得る)。

Let-Let-//-Ans
|   |      |
exp exp    exp

SparcAsm.expにはSPARC概要で述べた命令が並べられ、それに条件分岐や関数呼び出しに対応する仮想命令が加わっている。これらの構成子は入力オペランドとなるレジスタと即値をとる。出力レジスタは命令を指すLetノードの方で決まる。

and exp =
  | ...
  | Mov of Id.t
  | Neg of Id.t
  | Add of Id.t * id_or_imm
  | Sub of Id.t * id_or_imm
  | Ld of Id.t * id_or_imm
  | St of Id.t * Id.t * id_or_imm
  | ...
  | IfEq of Id.t * id_or_imm * t * t
  | IfLE of Id.t * id_or_imm * t * t
  | ...
  | CallCls of Id.t * Id.t list * Id.t list
  | CallDir of Id.l * Id.t list * Id.t list

実装

virtual.mlで定義される関数はclassify, separate, expand, g, h, f の6つ。 中間コードから仮想マシンコードへの変換の中心はVirtual.gである。 Virtual.hは関数の本体のコード生成、Viruatl.fはプログラムを構成する各関数の本体とメインの式それぞれについて変換を呼び出す。

virtual.mlで定義されるグローバル変数dataは浮動小数点数のテーブルである。 SPARCでは浮動小数点数は即値に出来ないため、定数のテーブルを作っておいてロードする。そのためにプログラム中に出現する浮動小数点数を記録する。

大きい関数を見る前に、まずは小さいものから片付けておく。 classifyは(変数名, 型)のリストxtsについてのfold_leftで、 ただし要素の型によって違う関数を適用する(Unitの場合は何もしない)。 separateとexpandはこれを用いる。

separateは変数を整数と浮動小数点数に仕分けし、 整数型の変数のリスト, 浮動小数点数のリストの2つのリストを返す。

expandはレコード中の変数のオフセットを計算しながら処理を進めるclassifyと言える。関数にはリストの要素のほか、計算中のオフセットも渡される。オフセットの計算では浮動小数点数のダブルワード境界のアラインメントを考慮する。

Virtual.g

整数の即値や算術演算のようなものはそのまま対応する命令一つに変換する。

例:

  | Closure.Add(x, y) -> Ans(Add(x, V(y)))

浮動小数点数の場合、既に述べたように即値として扱えない。そこでラベルを生成して値と共にテーブルdataに登録し、まずはこれも新しく生成した変数(レジスタ)xにアドレスを代入、そのレジスタの指すアドレスから値をロードするという2命令に変換する。

条件分岐はClosure.tと同じ構造の仮想命令なのでそのまま。

関数やクロージャの呼び出しも仮想命令なのでほとんどそのままである。

Let((x,t),e1,e2)はe1を変換したコードの後ろにe2を変換したコードを繋げる。 e1の末尾のAnsは変数xのLetに置き換えられる。

変数の参照はmov命令になる。

Closure.MakeClsの変換

クロージャの生成(Closure.MakeCls)は、トップレベル関数と束縛する自由変数を順にレコードにストアする処理である。

ここでの核心はoffsetとstore_fvの計算である。expandはオフセットを計算しながらリスト中の変数の型に応じて与えられた関数を呼ぶから、store_fvにはストア命令のリストが返される。

このストア命令のリストが実は自由変数の並びと逆になっているところがミソである。パディングが絡むオフセット計算はレコードの並び通りの順で行う必要がある。しかし実際に動くとき、ストア命令の実行は並び順の通りでなくても構わない。この着想のお蔭でこの処理が以前の版に比べ簡単になっている。

実はこれと同じ処理はもう一つある。タプルの生成がそれで、どちらも一連の変数をレコードにストアする処理である。

Virtual.h

関数の式を仮想マシンコードに変換する。関数は最初に自由変数を全てレジスタにロードする処理を入れる。これは丁度Closure.MakeClsを変換したときの逆の処理であるが、やっていることはストア命令がロード命令になっただけでほとんど同じである。

クロージャの生成にタプル生成という同種の処理があったように、こちらも同じ構造の処理がある。Closure.LetTupleの変換がそれである。

MinCaml読解ノート: SPARC概要

次のフェーズで生成する仮想マシンコードは実際のターゲットであるSPARCの命令に近いものになる。そこで、先にSPARCアーキテクチャの概要、特にMinCamlに必要な部分を中心に整理する(全部を説明するのは大変なので)。

SPARCの概要

• RISCアーキテクチャであり、メモリのロード・ストアと演算命令が分離している。
• 命令はどれも1ワード(32bit)の固定長である。
• レジスタウィンドウという独特の仕組みを持つ(MinCamlでは使っていない)。

SPARCの大きな特徴の一つはレジスタウィンドウであるが、MinCamlでは利用しない(そのほかにもSPARCでのC関数呼び出し規約は全く無視している)。

SPARCのレジスタ

SPARCのレジスタのうち、特に関係するのは次のものである。

汎用32bitレジスタ

多数あるが、一度に見えるのは32個 (r0〜r31)

プロセッサステータスレジスタ (PSR)

フラグ、モード(カーネル/ユーザモード)、CPU優先レベルなど

プログラムカウンタ (PC)

実行している命令のアドレス

ネクストプログラムカウンタ (nPC)

次に実行する命令のアドレス (プリフェッチに使われる)

演算結果の一部を入れるレジスタ (Y)

主に整数演算で使われる(乗算の上位ワード等)

32個の汎用レジスタにはレジスタウィンドウでの役割から、g0〜g7, i0〜i7, l0〜l7, o0〜o7という別名がついている。但しMinCamlではレジスタウィンドウという仕組みを使わないので、汎用レジスタについては単に同じようなレジスタが32個あると考えて差し支えない。

SPARCの浮動小数点ユニット(FPU)には32個の作業レジスタ(f0〜f31)がある。但しMinCamlで使う倍精度浮動小数点数を表すには2つのレジスタが必要なので、一度に表現できる倍精度浮動小数点数は16個である。

特定の用途に使われる汎用レジスタ

汎用レジスタのうち、いくつかのものは特定の用途に使われることが決まっている。 関数呼び出しの際、o7はリターンアドレス、o6はスタックポインタを入れるのに使われる。

またg0は特殊なレジスタで、常に値は0である。g0への値のセットは効果がない。

命令セット

SPARCの次の6種類に大別される。

• ロード・ストア
• 算術・論理演算命令
• 制御転送命令: call、ジャンプ、トラップ(システムコール発行)
• 制御レジスタ操作 (カーネルのみ)
• 浮動小数点命令
• その他

SPARCの命令はレジスタとレジスタ(または即値)間の演算が基本である。メモリ上のデータを処理するには、一旦レジスタにロードし、処理結果を再びメモリにストアする。

命令は1ワード(32ビット)の固定長。命令の多くは13ビット符号つきの即値を持てる。

算術・論理演算は3オペランド形式で、第1・第2オペランド間を演算した結果が第3オペランドのレジスタにセットされる。

オペランドの種類

reg	レジスタ
freg	浮動小数点レジスタ
simm13	13ビット符号つき即値
reg_or_imm	レジスタまたは13ビット即値
address	アドレス。 reg, simm13, reg+/-simm13, reg1+reg2の4通りが可能。

MinCamlで利用する命令一覧

ld	[address], reg	ワードをレジスタにロード
st	reg, [address]	ワードをメモリに書き込む
ldd	[address], freg	ダブルワードを浮動小数点レジスタにロード
std	freg, [address]	ダブルワードをメモリに書き込む
nop		何もしない
set	value, reg	ワードの即値をレジスタに代入 (※合成命令)
mov	reg1, reg2	レジスタ間でデータをコピー
neg	reg1, reg2	符号を反転させる
add	reg1, reg_or_imm, reg2	足し算
sub	reg1, reg_or_imm, reg2	引き算
sll	reg1, reg_or_imm, reg2	論理左シフト
fmovs	freg1, freg2	浮動小数点レジスタ間でデータをコピー
fnegs	freg1, freg2	浮動小数の符号を反転させる
faddd	reg1, reg_or_imm, reg2	倍精度浮動小数の足し算
fsubd	reg1, reg_or_imm, reg2	倍精度浮動小数の引き算
fmuld	reg1, reg_or_imm, reg2	倍精度浮動小数の乗算
fdivd	reg1, reg_or_imm, reg2	倍精度浮動小数の除算
cmp	reg, reg_or_imm	比較
fcmpd	freg1, freg2	倍精度浮動小数の比較
jmp	address	ジャンプ
be	label	条件分岐
bne	label	〃
ble	label	〃
bg	label	〃
bge	label	〃
bl	label	〃
fbe	label	浮動小数点ユニットのフラグによる条件分岐
fbne	label	〃
fble	label	〃
fbg	label	〃
fbge	label	〃
fbl	label	〃
call	label	サブルーチン呼び出し
retl		サブルーチンからの復帰

ロード・ストア命令では、アドレスはロード・ストアするデータのアラインメント境界に合わせる必要がある。

制御転送命令(ジャンプ、条件分岐、サブルーチンコール、サブルーチンからの復帰など)では、その命令の次の命令を実行してから実際の制御が移る。 これはパイプラインで仕掛かり中の処理を無駄にしないため。 ジャンプ先はワード境界に合っていなければならない。

set命令は値によって一つまたは複数の命令に翻訳される。SPARCではワード即値をレジスタに代入する命令はない(SPARCの命令は1ワードの固定長だから、ワード即値はとれない)。その代わりレジスタの上位22ビットに即値を与えるsethiという命令があり、これと論理和orを組み合わせてレジスタへのワード即値の代入を行う。

レジスタウィンドウ

既に記したようにMinCamlでは使用しないが紹介しておく。

SPARCの汎用レジスタは多数ある(プロセッサによって異なる)が、ある時点ではそのうちの32個だけが見えるようになっている。

関数呼び出しの際にウィンドウが「スライド」し、一部のレジスタが見えなくなり、代わりに新しいレジスタが使えるようになる。この仕組みをレジスタウィンドウと呼ぶ。

このときレジスタウィンドウは一部がオーバーラップして、いくつかのレジスタは呼び出し元でも呼び出し先でもアクセスできる。関数呼び出しではそのレジスタを利用して引数を渡す。

この仕組みを反映し、汎用レジスタの32個は次のように4種類に分けられそれぞれ別名がついている。

• グローバル(8) (どの関数からも見える) : g0〜g7 (r0〜r7)
• 出力 (8) (関数を呼び出すときに引数を入れる): o0〜o7 (r8〜r15)
• ローカル (8) (関数内の計算のみに利用): l0〜07 (r16〜r23)
• 入力 (8) (自分に渡された引数が入っている): i0〜i7 (r24〜r31)

グローバルの8個を除く24個がウィンドウとなる。関数呼び出しでは16個分スライドさせるので、8個がオーバーラップする。この8個は呼び出し元から見るとo0〜o7、呼び出し先の関数ではi0〜i7になる。

関数呼び出しのネストが深くなりレジスタが不足すると、割込みが発生してカーネルに制御が移り、スタック上に書き出してレジスタを空ける。

資料

SPARC V8、V9のアーキテクチャマニュアルはweb上で公開されている。大学等のwebで解説ページを見付けることもできる。

• SPARC仕様、技術書 (sparc.org)
• SPARCアセンブラの基礎 (東工大の千葉先生による)

MinCaml読解ノート: クロージャ変換

関数を、環境をとるクロージャとトップレベル関数とに仕分ける。 これまでで一番大きそうなフェーズである。

MinCamlにおけるクロージャの表現

このフェーズでは、これまで式中にあった関数定義を全て分離してトップレベルに持って来る。

関数が自由変数を参照しない場合は環境を無視してそのままトップレベルに持ってこれる。 一方、自由変数にアクセスする場合は、トップレベルに持ってきた関数だけでは意味がなく、関数と環境のセットで表すクロージャとして扱わなければならない。

MLでは変数の値は変更されない点をうまく利用し、MinCamlでは環境フレームを持たずにクロージャごとに自由変数のコピーを持たせることで実現する。 つまりクロージャは、静的なコードであるトップレベル関数と、自由変数の束縛のリストとして表現される。 トップレベル関数本体をf、その中で使われる自由変数をv₁, ..., v_nとすると クロージャの実体は{f, v₁, ..., v_n}というレコードとなる。

式やプログラムを表す型

プログラムの表現もここで変わる。

これまでは一つの式をもってプログラムとしていたが、全ての関数をトップレベルに移動し、複数のトップレベル関数のリスト+メインの式という形に分解される。 それを表すのが型Closure.progである。

式(中間コード)を表す型はKNormal.tに替えてClosure.tを使用する。

その大きな違いはLetRecが消えてクロージャ作成を示すMakeClsが登場し、関数適用がトップレベル関数の適用AppDirとクロージャの適用AppClsに細分化される点である。

また、一部でId.tに替えてId.lを使用する。これはトップレベル関数や外部の変数・関数のラベルとして最終的には定数になる性質のものである。一方Id.tのまま残ったものは全て一時的な変数となる。

KNormal.ExtFunAppはAppDirに吸収される。 外部関数もプログラム内で定義した関数も同じId.lとして扱うためである。

関数を表す型はClosure.fundefである。これの要素formal_fvがクロージャが持たされる自由変数のリストである。

変換の実装

クロージャ変換のエントリポイントであるClosure.fは、モジュール内変数toplevelを空のリストで初期化してClosure.gを呼ぶ。このリストはトップレベル関数を記録するのに使われる。

Closure.gが本体である。ほとんどのパターンではそのままKNormal.tからClosure.tへ写すだけの単純さだが、LetRecとAppの場合は案の定大仕事となる。

let rec g env known = function
  | ...

まずは簡単な関数適用の方から見てゆく。knownは自由変数を使わない関数の集合である。 そのような関数ならAppDirに、そうでなければAppClsに置き換える。また関数を示す変数をラベルに変換する。

  | KNormal.App(x, ys) when S.mem x known ->
      Format.eprintf "directly applying %s@." x;
      AppDir(Id.L(x), ys)
  | KNormal.App(f, xs) -> AppCls(f, xs)

LetRecの場合がややこしい。 let recで定義する関数本体を変換し、クロージャであればMakeClsにしなければならない。

最初に定義する関数が自由変数を持つかどうかを調べて関数かクロージャかを決め、然る後に関数本体と式e2を変換すればよさそうに思えるが、そうはなっていない。何故だろうか?

関数本体を変換する際には、そこで定義する関数の呼び出し(再帰呼び出し)があった場合にAppDirを使うかAppClsを使うかを決定しなければならない。この判断は、関数が自由変数を使うかどうかで決まる。自由変数のない関数の呼び出しはAppDirで問題ない。

LetRecの場所にMakeClsを入れてクロージャを生成するかどうかは、それに加えて式e2の中で関数が変数として参照されるかにも左右される。 一旦変数となると、それを適用する側はクロージャと関数の区別がつかないため、扱いをクロージャとしての扱いに統一せざるを得ない。そこで自由変数のないものでも、自由変数が0個のクロージャとする。このことはClosure.tにも表れていて、ラベルだけでは値として扱うことはできず、値となり得るのはUnit, Int, Float, Tuple, それにMakeClsで変数に代入されるクロージャだけとなっている。トップレベル関数を受渡しするには自由変数0個のクロージャとして扱うよりないわけである。

自由変数を調べるには、Closure.fvという関数を用いる。既に類似の目的のKNormal.fvがあるが、ここでそれでは不足である。その理由はラベルと変数を区別して扱わなければならないことによる。関数適用に現れるトップレベル関数のラベルは変数ではない。一方、単独で参照された場合(Var(x))は変数でありクロージャである。

このような理由から、判定するにはまず関数本体をClosure.tに変換する必要があるという、卵が先か鶏が先かにも似た問題が発生する。 そこで、まずとにかく一回変換して自由変数があるか調べ、その結果に基づいて(必要があれば)変換をやり直すという手順を踏むわけである。

猶、自由変数を持たない関数でもクロージャを生成する必要のある例がtest/cls-bug.mlにある。

let rec f x = x + 123 in
let rec g y = f in
print_int ((g 456) 789)

このプログラムではf自身は自由変数を使わないが、gがfを値として返すためにクロージャになる。gを呼び出す側ではクロージャと関数の区別がつかないので、戻り値は全てクロージャとして扱うためである。

クロージャ生成にどのような情報が持たせられるかは、MakeClsに与えられるパラメータzsを計算する式をみればわかる。またzsからztsが計算され、クロージャを生成するかどうかによらずトップレベル関数をリストtoplevelに追加する。

let zs = S.elements (S.diff (fv e1') (S.add x (S.of_list (List.map fst yts)))) in (* 自由変数のリスト *)
let zts = List.map (fun z -> (z, M.find z env')) zs in
toplevel := { name = (Id.L(x), t); args = yts; formal_fv = zts; body = e1' } :: !toplevel; (* トップレベル関数を追加 *)
let e2' = g env' known' e2 in
if S.mem x (fv e2') then (* xが変数としてe2'に出現するか *)
  MakeCls((x, t), { entry = Id.L(x); actual_fv = zs }, e2')
else
  e2'

toplevelに追加されるトップレベル関数にはformal_fvとして自由変数のリストが入る。クロージャによって渡される「隠れ引数」である。一方、MakeClsに渡す情報のactual_fvはそれらの自由変数のクロージャ生成時における束縛である。

あとは、外部変数・外部関数も見ておこう。変数名をラベルに変換している。関数名は"min_caml_"というプレフィクスが付けられている。

  | KNormal.ExtArray(x) -> ExtArray(Id.L(x))
  | KNormal.ExtFunApp(x, ys) -> AppDir(Id.L("min_caml_" ^ x), ys)

MinCaml読解ノート: 不要定義削除

このフェーズでは使われない変数や関数の定義を削除する。

let x = e1 in e2 という定義を削除するには2つの条件を調べればよい。

• 使われていないか? ……e2にxが出現していなければ使われていない。
• 副作用がないか? ……e1に副作用がなければ削除できる。配列の破壊的変更があれば明らかに副作用がある。他の関数を呼んでいる場合その先はわからないので副作用がないとは言い切れない。

両方の条件を満たせば、Letを取り払ってe2に置換できる。

まずここで使われるKNormal.fvから見てゆく。この関数は式を再帰的に調べて、式に出現する自由変数の集合を返す。つまり式の内部で束縛した変数は含まない(調べる式はα変換済なので束縛変数を含もうが含むまいが影響はないのだが)。

変数の集合はS.tで表す。これは標準ライブラリのSetを要素にId.tをとるよう特殊化したものである。

Elim.fではこの関数を使って、変数が使われるかどうかを調べることになる。

次に副作用をチェックするElim.effectをみる。変数の値を計算する式e1を取り、その中に破壊的変更や関数呼び出しがあれば真を返す。非常に簡単である。

let rec effect = function
  | Let(_, e1, e2) | IfEq(_, _, e1, e2) | IfLE(_, _, e1, e2) -> effect e1 || effect e2
  | LetRec(_, e) | LetTuple(_, _, e) -> effect e
  | App _ | Put _ | ExtFunApp _ -> true
  | _ -> false

内部関数の呼び出しの方は、もう少し頑張ればその先で本当に副作用があるかどうかを調べられる筈である。副作用のある関数の集合を記録し、LetRecで関数を定義する際に副作用があるものは追加すればよい。

不要定義削除の本体はElim.fである。

letの場合、式e1, e2を処理した後、e1に副作用がなく、e2で変数が使われなかった場合はめでたくLetを削除できる。

  | Let((x, t), e1, e2) ->
      let e1' = f e1 in
      let e2' = f e2 in
      let live = fv e2' in
      if effect e1' || S.mem x live then Let((x, t), e1', e2') else
      (Format.eprintf "eliminating variable %s@." x;
       e2')

let recの場合、定義した関数が式e2の中で使われていなければLetRecを削除する。変数と違って値を計算する式はないので副作用は関係せず、使われていなければ削除できる。

OCamlメモ

S.empty

空の集合(S.t)を返す。S.tはs.mlで定義される型で、標準ライブラリのSetをId.tを要素に特殊化したものである。

S.add item set

setにitemを加えた新しい集合を返す。

S.remove item set

setからitemを除いた新しい集合を返す。

S.union set1 set2

和集合を作る。

S.singleton item

要素を一つだけ含む集合を作る。

S.mem item set

集合に要素に含まれていれば真を返す。

MinCaml読解ノート: 定数畳み込み

定数畳み込みは次のような結果がわかっている式をコンパイル時に計算した値に置き換えてしまう処理である。

let x = 1 in
let y = 2 in
x + y

MinCamlでは、演算のオペランドの両方の値が定数である場合にその計算結果で置き換えることだけを実装している。だから

let x = 3 in
let y = 7 in
let x + a + y

のような場合を10+aにはできない。

まず、小さな関数から見ていく。

memi, memf, memtは変数xと環境envを受け取り、xが登録されていて値が即値のInt/Float/タプルであれば真、それ以外の場合は偽を返す。

findi, findf, findt はxの値が即値のInt/Float/タプルであれば値を返す。xが見付からないか型が合わない場合はエラーとする。

次に定数畳み込みの本体ConstFold.gである。

ソースコードと順番が前後するが、letではまず代入する式を定数畳み込みし、変数とその式を環境に追加する。

変数の評価はそのまま即値に置き換える。ただしIntの場合のみで、FloatやTupleの場合はコメントアウトされている。これらは整数と異なり最終的にメモリ上に置かれるデータとなるため重複を嫌ったものであろうか。代償として畳み込みの効率は少し落ち、(let x=1.0 in x) +. (let y=2.0 in y)のような式を一回では3.0と計算できず、最適化フェーズを2回通る必要がある。重複した浮動小数点数は後の仮想マシンコード生成にて省かれるので、ここでFloatの処理を避ける必要はないように思えるのだが。

整数の演算、浮動小数の演算は、全ての項が定数なら計算した即値で置換。

比較による条件分岐では、比較が即値同士なら真偽が確定するので生きる方の式だけを残す。

LetTupleではタプルの中身がわかっている場合はタプルを分解し、要素の数だけLetを並べた形に変換する。同時にletの場合と同様変数と式を環境に追加する。

例えば、t=(a,b,c)とわかっているとき let (x,y,z)=t in e は let x=a in let y=b in let z=c in e となる。

MinCaml読解ノート: インライン展開

小さい関数の関数適用をその本体で置き換える。 「概説」の説明の通りで、難しい点は特にない。

変数thresholdはインライン展開するかどうかを決める関数の大きさの閾値で、-inlineオプションによりセットされる。

関数sizeは式の大きさを計算する関数で、単にKNormal.tのノードの数を数え上げて決めている。

関数gがインライン展開の本体である。インライン展開する関数の表(最初は空)と式を受け取りインライン展開した式を返す。 関数定義のKNormal.LetRecと関数適用のKNormal.Appに対する処理が要。

KNormal.LetRecでは関数本体の大きさをsize関数で計算し、threshold以下であれば関数を表に登録する。

KNormal.Appは適用する関数が表に登録されているものなら、展開する関数本体の式で置き換える。 このとき、「仮引数を引数で置換」「本体の式を複製することになるため、α変換で変数名を一意なものに付け替え」をAlpha.gを使って一度に行う。Alpha.gは変換する変数名の表の初期値を外部から与えられるのでこのような流用が利く。

OCamlメモ

List.fold_left 関数 初期値 リスト

初期値をX、リストの要素をx₁...x_n、関数を中置演算子*で表すとして、
(((X * x₁) * x₂) * ... * x_n)
を計算する。 fold_leftという名前はこの計算が左結合であることによる。 これを右結合にしたfold_rightというのもあり、向きの違いを反映して型が少し異なる。

# List.fold_left (fun x y -> x@[y*2]) [0] [1;2;3];;
- : int list = [0; 2; 4; 6]
# List.fold_right (fun x y -> (x*2)::y) [1;2;3] [0];;
- : int list = [2; 4; 6; 0]

List.fold_left2 関数 初期値 リスト1 リスト2

List.fold_leftに与える引数がx_iではなくリスト1の要素x_iとリスト2の要素y_iの2つになったもの。上に倣って書き表すと
(((X * (x₁,y₁)) * (x₂,y₂)) * ... * (x_n,y_n))
のような感じになる(実際にタプルを構成するわけではないが)。

# List.fold_left2 (fun x y z -> x@[(y,z)]) [(0,0)] [1;2;3] [4;5;6];;
- : (int * int) list = [(0, 0); (1, 4); (2, 5); (3, 6)]

MinCaml読解ノート: ネストしたletの簡約

K正規化で述べたように、ここまでの中間コードはネストしたletのリストになっている。 このネストを開いて平たい一列のリストに直す。

そのために、letが入れ子になっている箇所で図のような繋ぎ替えを行う。

このための処理が見慣れないと少しややこしい。 Assoc.fの中で内部定義された関数insertは、入れ子になったリストを末尾の手前までそのまま複製しながら進む。末尾の非letの要素eに代わり、eを持ち元のリストの続きに接続するLet(xt, e, f e2)を入れる。

let rec f = function
  | [...]
  | Let(xt, e1, e2) ->
      let rec insert = function
	| Let(yt, e3, e4) -> Let(yt, e3, insert e4)
	| LetRec(fundefs, e) -> LetRec(fundefs, insert e)
	| LetTuple(yts, z, e) -> LetTuple(yts, z, insert e)
	| e -> Let(xt, e, f e2) in
      insert (f e1)

※この処理では非末尾の条件分岐はletの要素になるため厳密には完全にネストがなくなるわけではない。またこの後のインライン展開で再びネストが発生するので、以後もネストしたリストとして扱うことに変わりはない。

MinCaml読解ノート: β簡約

MinCamlでβ簡約と呼んでいるのは、変数の定義が単に別の変数のコピーであるような変数を元の変数で置き換えることである。 つまり let y = x in ... のような変数yを使う箇所を全て元の変数xで置き換える。

変数を別の変数に置き換えるという処理はα変換と似通っており、コードもほとんど同じである。 違いはletのときに変数の値を与える式が変数(KNormal.Var)である場合に限り変換を登録する点等である。

let rec g env = function
  | Add(x, y) -> Add(find x env, find y env)
  | Sub(x, y) -> Sub(find x env, find y env)
  | [...]
  | Let((x, t), e1, e2) ->
      (match g env e1 with
      | Var(y) ->
	  Format.eprintf "beta-reducing %s = %s@." x y;
	  g (M.add x y env) e2
      | e1' ->
	  let e2' = g env e2 in
	  Let((x, t), e1', e2'))
  | [...]

MinCaml読解ノート: α変換

プログラム中の束縛変数の名前を付け替えて一意な名前にする。

Alpha.findが付け替えた変数名の変換を行う関数である。envに登録されていなければ外部変数として変換せずにそのまま返す。

let find x env = try M.find x env with Not_found -> x

本体はAlpha.gで、この関数は環境(付け替え前と後の変数名の対応表)と式を受け取る。基本的には変数名をfind x envで置き換えるだけである。

letでは新しい変数名を生成して置き換え、元の変数名との対応を環境に追加して残りの式を変換する。let recの場合も同様である。let recではそれぞれの関数の引数名も変換し、関数の式をα変換するときに引数の変換も加えた環境を渡す。

let rec g env = function
  | Add(x, y) -> Add(find x env, find y env)
  | Sub(x, y) -> Sub(find x env, find y env)
  | [...]
  | IfEq(x, y, e1, e2) -> IfEq(find x env, find y env, g env e1, g env e2)
  | IfLE(x, y, e1, e2) -> IfLE(find x env, find y env, g env e1, g env e2)
  | Let((x, t), e1, e2) ->
      let x' = Id.genid x in
      Let((x', t), g env e1, g (M.add x x' env) e2)
  | [...]

MinCaml読解ノート: K正規化

K正規化の意味

K正規化は、複雑な計算の途中結果全てを変数として定義する。 これによって複雑な式が一連の単純な式に分解され、プログラムは順序づけられた単純な計算の繰り返しに姿を変える。

K正規化後の型であるKNormal.tにもそれが表れている。

type t =
  | Add of Id.t * Id.t
  | Sub of Id.t * Id.t
  | ...
  | IfEq of Id.t * Id.t * t * t
  | IfLE of Id.t * Id.t * t * t
  | Let of (Id.t * Type.t) * t * t
  | LetRec of fundef * t
  | LetTuple of (Id.t * Type.t) list * Id.t * t

全ての演算や関数適用は、式KNormal.tではなく変数Id.tをオペランドにとるようになり、KNormal.tをとるのはlet類と条件分岐のみである。 つまり、KNormal.tによる表現はletをノードとするリストとなる。

「速攻MinCamlコンパイラ概説」にある例では、a+b+c-dは次のようになる。

let tmp1=a+b in
let tmp2=tmp1+c in
tmp2-d

※正確には、MinCamlのK正規化の実装では a+b+c-dは

let tmp2 =
  let tmp1 = a+b in
  tmp1+c in
tmp2-d

に変換される。これは次のように図示できる。青い破線と数字は実行順を示す。

データ構造としては完全な一次元ではないが、これは入れ子になったリストと見ることが出来る。計算とその順序の点では先の表現と等価である。 簡単な変形を施すと先の表現のような入れ子のないリストに出来、後のネストしたletの簡約フェーズではそれを行う。

K正規化の実装

kNormal.mlで定義される関数はfv, insert_let, g, f。このうちfvは当面使われない。fはgを呼ぶだけのもので、K正規化の本体はKNormal.gである。

KNormal.gは型環境と式(Syntax.t)を取り、K正規化した式(KNormal.t)と型を返す。 最も基本的な単項演算の場合はこのようになる。

  | Syntax.Neg(e) ->
      insert_let (g env e)
	(fun x -> Neg(x), Type.Int)

insert_letはオペランドの式で変数を定義するLetノードを作り、演算ノードをそれに繋げる。ただし演算ノードはオペランドの変数名が不明では作れないので、insert_letに渡すのは演算ノードではなくそれを作るクロージャである。

insert_letでは受け取った式を調べ、単なる変数の場合はその変数をそのまま演算に渡し、letを作らない。この節約をしないと項の数だけ無駄にletが増える。

二項演算子はオペランドが2つあるのでinsert_letを重ねる。Letノードが2つ続き、その次にAddノードが来る形になる。

  | Syntax.Add(e1, e2) ->
      insert_let (g env e1)
	(fun x -> insert_let (g env e2)
	    (fun y -> Add(x, y), Type.Int))

この変換の結果は次のようになる。

Let [x] ---- Let [y] ---- Add(x,y)
|            |
(g env e1)   (g env e2)

その他、関数適用等の場合もこれと同様に出てくる式の数だけletを並べ最後にApp等のノードが来る形になる。

「ついで」の変換

「概説」にある通り、ブール値は整数の1と0に置換される。

KNormal.tでは比較・論理演算とif文を条件分岐 IfEqとIfLE による表現に置き換える。

直接KNormal.IfEq、KNormal.IfLE に変換できるのは、Syntax.If(Syntax.Eq(e1,e2), e3, e4)のようにif文の中に比較がある場合である

それ以外のif文の扱いが面白い。Syntax.tによる別の表現に言い換えた上で、もう一度KNormal.gにかけるのである。つまりLispでいうマクロのようにして実現している。

例えば、条件式が比較ではないif文Syntax.If(e1,e2,e3)は、Syntax.If(Syntax.Eq(e1, Syntax.Bool(false)), e3, e2)に言い換える。 また、単独で出現する比較は、その比較を行ってtrueまたはfalseを返すif文に態々変換されるという具合である。

OCamlメモ

fst: 'a * 'b -> 'a

二つの要素の組をとり、最初の要素を返す。早い話がLispのcar。 案の如くcdrに相当する二つ目の要素を返すものもあり、そちらはsndという。

MinCaml読解ノート: 型推論

型推論は変数や関数の型を推定する作業であり、既に述べたように構文木の中のType.Varの値を決めていく。

型推論の中核はTyping.gとTyping.unifyである。 Typing.gは型環境env (変数の名前→変数の型の写像)と式eを受け取り、式eの型を返す。

Typing.unifyは二つの型を受け取り、それらを一致させる。つまり一方が未定の型変数であれば型が決定する。双方が既知の型であれば一致しない場合にはエラーとなる。

この二つが互いを呼んで再帰的に式や式の内部の変数の型を推論する。

コードにはあまり直接表れないが型推論には自然ある程度の方向がある。特定の型を対象とする演算子からオペランドの型が決まり、変数定義では値から変数の型が決まる。関数本体の式や引数から関数の型が決まり、戻り値の型が決まるという具合である。

Typing.g

定数項であれば型はわかっているのでそれを返す。

not, -, +, *, /, -., +., *., /. では演算子から型が決定できるので、オペランドの型を推論して、その型とunifyする。

==, <= では直ちにオペランドの型はわからないが両辺の型は同じ筈なので、それぞれの推論した型同士をunifyする。式の型としてはType.Boolを返す。 それ以上は両辺の型をチェックしないので、例えばtrue < falseのような式をこの時点でエラーにすることはできない。

if式では、条件の式をType.Boolとunify。then式とelse式をそれぞれ型推論してunifyする。またその型をif式の型として返す。

letでは、=の右辺つまり値の式を型推論したものと型変数をunifyする。これで型変数の中身が決まる筈である(別の型変数を指すだけかも知れないが)。その後、変数名と型変数の組を型環境に追加して、inの後に続く式を型推論する。

let recの場合、まず関数名と関数の型変数を環境に追加する。inに続く式はこの環境を使って推論する。関数本体の式はこれに引数とその型を追加した環境を使って型推論する。

let recの型推論で関数の型変数がどのようになるかの例を挙げる。

let f x = x + 3 in f 4

この式をTyping.gにかけて型推論すると、構文木とその中の型変数は次のようになる。

Syntax.LetRec
 ([{Syntax.name =
     ("f",
      Type.Var
       {contents =
         Some (Type.Fun ([Type.Var {contents = Some Type.Int}], Type.Int))});
    Syntax.args = [("x", Type.Var {contents = Some Type.Int})];
    Syntax.body = Syntax.Add (Syntax.Var "x", Syntax.Int 3)}],
 Syntax.App (Syntax.Var "f", [Syntax.Int 4]))

ついでにletの場合も見てみよう。

let x = 1 in x + 2

この式は次のようになる。

Syntax.Let (("x", Type.Var {contents = Some Type.Int}), Syntax.Int 1,
 Syntax.Add (Syntax.Var "x", Syntax.Int 2))

変数の型推論では、束縛変数であればenvに含まれる筈であるので対応する型変数を返す。envに見付からない場合は外部変数の表であるextenvを捜す。それで見付からない場合は未定義となるが、MinCamlでは宣言のない外部変数を許しており、新しく型変数を与えてextenvに追加する。

関数適用の型推論。関数定義のみでは必ずしもその戻り値は決まらない為、実際に適用して初めて決まる。そこで、その適用における関数の型を表現した値(戻り値の型は未定なので新しい型変数を使う)と、g env eが返す関数の型変数をunifyする。

ここでMinCamlの弱点の一つに遭遇する。関数の型を示す型変数がそのまま使われているため、一度適用でunifyされてしまうと関数の型が固定されてしまい、別の型で呼べなくなる。つまりMinCamlでは関数に多相性がない。例えば次の式は型推論の段階でエラーになってしまう。

let rec f x y = if x < y then 1 else -1 in
print_int (f 3 4) ; print_int (f 2.0 1.0)

回避するには次のように型毎に別々の関数を定義する必要がある。

let rec fi x y = if x < y then 1 else -1 in
let rec ff x y = if x < y then 1 else -1 in
print_int (fi 3 4) ; print_int (ff 2.0 1.0)

型推論がありながらこれでは少し寂しい。言語としてバランスに欠ける。

Typing.unify

2つの型を突き合わせて両者が一致するか調べ、また一致するように型変数を決定する。 つまり片方が未定の型変数であればもう一方の式を代入する。ここが型変数の代入が行われる唯一の箇所である。

このとき、代入する式の中にその型変数が出現していないか調べて循環の発生を防ぐ(と「概説」にはある。だが実際に型が循環するような式はあり得るだろうか?)。

また、両者が既知の型で一致しない場合は例外を発生させる。

Typing.f

Typing.fは型推論のメインルーチンであり、受け取った構文木をTyping.gに渡して型推論する。 その結果とType.Unitをunifyしているのは単なるお節介。様々な式を通して実験するには、このunifyする部分の代わりにコメントアウトされている警告を出力するだけの式を生かすとよい。

Typing.deref_typは型変数をその中身で置き換える関数である。型変数が別の型変数を指している場合はさらにその中身を採る。外部から呼ばれるときに受け取る引数はType.Varであるが、その中身について再帰的に処理するためType.tの全ての型を扱う。

Typing.deref_termは構文木中の型変数を全てその中身で置き換える。

こうして最終的には型変数は実際の型で置き換えられる。

OCamlメモ

例外

例外の宣言: exception 名前 [of 型]

例外の送出: raise 例外

例外の捕捉:

try 式 with 
  パターン -> 式
| パターン -> 式

failwith 文字列

例外Failureを発生させる。

Format.eprintf

エラー出力する関数。

M.add key value map

mapにkeyとvalueの組を追加する。

M.add_list (key,value)のリスト map

mapに一連の組を追加する。

List.map func list

listの各要素にfuncを適用した結果のリストを返す。

List.iter2 func list1 list2

2つのリストから引数を一つずつとり2引数の関数funcを適用することを繰り返す。

List.exists elem list

リスト中に要素があるか調べる。

MinCaml読解ノート: 構文解析

MinCamlとは関係ないが、祝、サッカー日本代表ワールドカップ予選突破。素晴らしい。

構文解析ではトークン列を受け取って構文木を構築する。 ソースコードとしてはparser.mlyに文法を記述。ocamlyaccというツールを使い構文解析器を生成する。

parser.mlyからアクションを省略してMinCamlの文法を拡張BNFのように書くと次のようになり、非常に短い。

「速攻MinCamlコンパイラ概説」で説明されているが、simple_expとexpの違いは括弧で囲まなくても関数の引数になれるか否か。この区別が必要なのは、MLでは単にスペースで区切って並べるだけで関数適用になるためである。

simple_exp:
| ( exp )
| ()				/* Unit */
| true
| false
| integer
| float
| identifier
| simple_exp .( exp )		/* 配列の参照 */

exp: /* 一般の式 */
| simple_exp
| not exp
| - exp
| exp + exp
| exp - exp
| exp = exp
| exp <> exp
| exp < exp
| exp > exp
| exp <= exp
| exp >= exp
| if exp then exp else exp
| -. exp
| exp +. exp
| exp -. exp
| exp *. exp
| exp /. exp
| let identifier = exp in exp
| let rec fundef in exp
| let ( identifier { , identifier }+ ) = exp in exp
| exp simple_exp +		/* 関数適用 */
| exp { , exp }*		/* タプル */
| simple_exp . ( exp ) <- exp	/* 配列への代入 */
| exp ; exp			/* 順序評価 */
| Array.create simple_exp simple_exp	/* 配列の作成 */

fundef:
| identifier { identifier }+ = exp	/* 関数名 引数リスト 本体 */

integer:
|  -?[0-9]+
float:
|  -?[0-9]+{.[0-9]*}?{[eE][+-]?[0-9]+}?
identifier:
| _
| [a-z][a-zA-Z0-9_]*			/* 但し予約語を除く */

整数の乗算と除算がないことに気付く。

それはさておき、この構文解析器で生成する構文木のデータ型はSyntax.tである。

type t =
  | Unit
  | Bool of bool		← 定数値
  | Int of int
  | Float of float
  | Not of t			← 単項演算子。型がtというのはオペランドが式。
  | Add of t * t		← 二項演算子
  | [...]
  | Eq of t * t
  | LE of t * t
  | If of t * t * t		← 条件、THEN式、ELSE式
  | Let of (Id.t * Type.t) * t * t	← 変数(名前(Id.t)、型(Type.t))、値、式
  | Var of Id.t			← 変数の参照
  | LetRec of fundef * t	← 関数定義、メインの式
  | App of t * t list		← 関数、引数リスト(t list)
  | Tuple of t list
  | [...]
and fundef = { name : Id.t * Type.t; args : (Id.t * Type.t) list
↑ 構文木で関数を表すデータ型。name: 名前と型。args: 引数(名前と型)リスト

先に見た文法と異なり、Syntax.tには比較演算子はEqとLEしかない。残りの<>, <, >, >=は、これら2つとNotの組み合わせで表現される。

MinCamlでの型を表すデータ型はType.t。基本のデータ型はUnit, Bool, Int, Floatのみで、これに関数Fun、タプルTuple、配列Array、それに変数や関数の型を表すための型変数Varが加わる。

変数や関数の型は構文解析の時点では定まらず、次の型推論のフェーズで決定される。そのためType.VarはType.tのオプション型への参照を取る構成子とされ、書き換えが可能である。構文解析中はaddtypを通して作成され、初めはNoneで初期化され型が未定であることを示す。型推論の段階で型が決定すればこれが書き換えられる。最終的には以後の扱いを簡単にするために、型変数を型そのもので置き換えることになる。

猶parser.mly中に出てくるVarはSyntax.Var(変数の参照を示す)のことであって、Type.Varではない。

構文解析器のアクションではSyntax.tの構文ノードを作るだけである。

スタート規則がexpであるから、このコンパイラは式を一つだけしか読まない。だから変数や関数を定義してそれらを使ったプログラムを書くためには、letやlet recを延々と入れ子にし一つの式として構成することになる(test/にあるサンプルを参照)。

OCamlメモ

オプション型: 'a option

型'aの何れかの値、または無効値(None)になるような型。任意の型について自動で定義される。他の言語で、値が無効であることを示すためにnullやnilを使うのに似ている。有効な値で構成するにはSomeというデータ構成子を使う。
オプション型の定義は書くとすれば次のようになる。

type 'a option = None | Some of 'a

レコード型

複数のフィールドを持つ。早い話が構造体である。type 型名 = { 名前1 : 型; 名前2 : 型; ... }という形で宣言する。プログラム中で値を作るには{ 名前1=値; 名前2=値; ... }と書く。パターンマッチでは { 名前1 = 変数; 名前2 = 変数; ... } -> 式のように書くことができる。

MinCaml読解ノート: 字句解析

字句解析器は、lexer.mllというファイルに記述してocamllexというツールで生成する。このツールは名前の通りlexのOCaml版である。

lexer.mllでは、tokenとcommentの2つのスキャナが定義されている。

MinCamlの文法は素直な文脈自由文法で、tokenスキャナでは予約語を認識して対応するトークンを返す。

例外はコメントの処理で、(*という文字列が来るとスキャナをcommentスキャナに切り替えて読み飛ばす(アクション部で更にスキャナを呼ぶというのは今読んだ文字列を読み飛ばすことを意味する)。commentスキャナでも(*を認識していて、これが来るとcommentスキャナを二度呼ぶ。これはMinCamlではコメントのネストを許しているためで、一回目でネストしたコメントを読み飛ばし、次に現在のコメントの残りを読む。

トークンは構文解析器を記述するparser.mly中の%token命令で定義される。構文解析器を生成するocamlyaccというツールにより、それらをデータ構成子とする型Parser.tokenが定義される。

parser.mlyでのトークンの定義:

%token <bool> BOOL
%token <int> INT
%token <float> FLOAT
%token NOT
%token MINUS
%token PLUS
...

ocamlyaccにより生成されるparser.mliでのデータ型Parser.token:

type token =
  | BOOL of (bool)
  | INT of (int)
  | FLOAT of (float)
  | NOT
  | MINUS
  | PLUS
 ...

スキャナでは予約語以外の単語がくるとトークンIDENTを返す。このトークンの値となるId.tは文字列のみから成るデータ型で、以後変数や関数の名前に用いられる。

パターンマッチのダミーを示す'_'に対してはその都度新しく名前を生成する。

識別子等のアクション部で使われるLexing.lexeme lexbufという式はパターンにマッチした文字列を参照する。

OCamlメモ

open Module

他のモジュールで定義した識別子を、モジュール名のプレフィクスなしで使えるようにする。JavaのimportやC++のusing namespaceに似ている。

int_of_string: string -> int

文字列を整数として解釈する。

float_of_string: string -> float

文字列を浮動小数として解釈する。

MinCaml読解ノート: ビルドと全体の流れ

「速攻MinCamlコンパイラ概説」とMinCamlのソースコードを読んだ結果の整理がてら纏めておく。

ビルドと実行

Makefileではいくつかの変数を定義してOCamlMakefileをインクルードしている。このOCamlMakefileはOCamlによるソフトウェアの定型的なビルド手順を記述したMakefileである。FreeBSDなどのbsd.*.mkに相当する(ユーザであればportsが一番お馴染みであろう)。

OCamlMakefileが提供するターゲットとして、make byte-codeとすればコンパイルしたモジュールをバイトコードとして持つ実行ファイル、make native-codeではネイティブコードの実行ファイル、make topとすればモジュールを組み込んだ対話環境を生成する。

実行例: ./min-caml.opt test/fibとするとtest/fib.mlをコンパイルしたtest/fib.sが出来る。出力されるのはSPARCのアセンブリソースである。

メインルーチン

filesにはコマンドラインで与えられたソースファイルのリストが入る。そのファイル名それぞれについて関数fileを呼ぶ。fileでは、入力と出力をオープンして関数lexbufを呼ぶ。

lexbuf

入力を読み込み、コンパイルの各フェーズを順に実行する。MinCamlではコンパイルをデータ変換の連続したプロセスと捉える。一つ一つのフェーズがデータ変換であり、あるフェーズの出力は次のフェーズの入力となる。

全体の流れは次のようなもの。

字句解析	Lexer.token	バイト列を、トークンという単位に分割する
↓	トークン列 (呼び出し毎に新しいトークンを一つ返す関数)
構文解析	Parser.exp	構文木を構築する
↓	構文木 (Syntax.t)
型推論	Typing.f	構文木に現れる関数や変数の型を決定する
↓	構文木 (Syntax.t) [型変数を型オブジェクトで置換]
K正規化	KNormal.f	複雑な式を単純な式に分解、全ての式の値に変数を割り当てる
↓	中間コード (KNormal.t)
α変換	Alpha.f	変数名をコンパイル単位中で一意になるように付け替える
↓	中間コード (KNormal.t)
最適化	Main.iter
↓	中間コード (KNormal.t)
クロージャ変換	Closure.f	ネストした関数定義を関数とクロージャに分解する
↓	中間コード (Closure.t)と関数(Closure.fundef)のリスト
仮想マシンコード生成	Virtual.f	式を仮想マシンコードに変換する
↓	仮想マシンコードのプログラム (SparcAsm.prog) 。浮動小数定数リスト、仮想マシンコードにした関数のリストとメインの式から成る。仮想マシンコードの型はSparcAsm.t。
SPARCの13ibt即値最適化	Simm13.f	SPARCで即値オペランドにできる13bit以下の整数を即値オペランド化 (SPARCでは、それ以外の定数は演算の前に一旦レジスタにセットする必要がある)
↓	仮想マシンコードのプログラム (SparcAsm.prog)
レジスタ割り当て	RegAlloc.f	仮想マシンコードの変数(無限の仮想レジスタ)を、有限の実際のレジスタに置き換える
↓	仮想マシンコードのプログラム (SparcAsm.prog) [命令オペランドの変数をレジスタに置き換え]
アセンブリ生成	Emit.f	最終的なアセンブリソースを出力する

最適化は次の処理を最大1000回繰り返す。

β簡約	Beta.f	値をコピーするだけの変数定義を削除し、元の変数を使うようにする
↓	中間コード (KNormal.t)
ネストしたletの簡約	Alloc.f	変数の初期値を計算する式の中のletを外へ移す
↓	中間コード (KNormal.t)
インライン展開	Inline.f	小さな関数の適用をその関数の式で置き換える
↓	中間コード (KNormal.t)
定数畳み込み	ConstFold.f	定数同士の演算をその計算結果で置き換える
↓	中間コード (KNormal.t)
不要定義削除	Elim.f	使われない変数や関数を削除する
↓	中間コード (KNormal.t)

MinCaml言語の仕様

「概説」中の「MinCamlの構文と型」で述べられている通りだが、コンパイラを読むにあたっては特に次の点に留意。

• プログラムはただ一つの式から成る。test/ディレクトリにあるサンプルをいくつか見ればわかる通りである。教育目的と割り切った仕様である。構文解析の関数名がParser.expなのもこれに因る。
• GCは無い。これも割り切っている。
• 変数の値は変更されない。これはMinCamlに限らずOCamlやML等もそうである。配列や参照(MinCamlには参照はないが)も、その中身は書き換わるがそれらを指す変数は変更されることはない。
• letでは変数のみ定義。let recでは関数のみ定義。無名関数はない。

OCamlメモ

MinCamlのソースコード中では「超入門」にないライブラリや構文も使われているので、重要そうなものを挙げる。私はOCamlについて「超入門」以上の知識はないので間違いもあり得る。訂正乞う。

List.iter: ('a -> unit) -> 'a list -> unit

リストの要素それぞれに与えられた関数を適用する。 もう少し馴染みのある書き方にすると、List.iter func list (listは型'aのリスト。funcは引数を一つ受け取ってunitを返す関数) となる。早い話がSchemeのfor-each。

ignore: 'a -> unit

引数が何であろうとunitを返す。関数の戻り値を無視する意志を明示するために用いる。

M.empty (MinCamlのコードで定義しているものだが)

空のマップ型オブジェクトを返す。OCamlにはMapという型があり、モジュールMではそのキーの型をId.tに指定したものを定義していると思えばよい。C++で

template <typename Value>
class M : public std::map<Id.t, Value> { };

とするのと同じようなものだろう。