MinCaml読解ノートが一通り完了したので、目次として各記事へのリンクを列挙する。
MinCaml読解ノートは、MinCamlコンパイラを筆者が読んだ結果を元に理解の参考のために動作やソースコードに対する解説を加えたものであって、住井氏自身による「速攻MinCamlコンパイラ概説」による解説を補い、詳しい補足や場合によりソースコードに即した説明により読者の理解の一助となることを意図している。
MinCamlの記述言語であるObjective Camlについての知識は「超特急: 一時間でわかるML超入門」の内容のみを前提とし、その範囲を超えた機能が使われ理解を妨げそうなときには説明を付した。筆者自身も当初Objective Camlについては「超入門」を読んだだけの内容しか知らなかったので、同じようにObjective Camlの知識に乏しい方でもさほど支障は生じないと思われる。
またMinCamlがターゲットとするSPARCについても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としている。
変数(すなわち無限個の仮想レジスタ)の処理を有限個の実レジスタに落とし込む処理である。変数を極力レジスタに割り当て、どうしてもレジスタが足りないときは変数をスタックに割り当てて退避し、レジスタを空ける。
「概説」の説明は有用な情報を含んでいるがそのままではまとまりに欠けるので、ここで整理要約させて頂く。
RegAlloc.hで実装。RegAlloc.g。変数からレジスタへの写像regenvと命令列を受け取りレジスタ割り当てを行った命令列と新しいregenvをデータ型NoSpillで返す。SparcAsm.fv: まだ生きている変数を返す
(現在の式と、これから後にくる命令列contを調べる)RegAlloc.target) (register targetingまたはregister coalescing)
RegAlloc.gは溢れの発生を示すToSpillを返すSave命令を挿入)Forget命令を挿入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の中心となる部分は次のように処理単位の大きさによって関数が分かれ、上位のものがより下位の関数を呼んで処理を行う。
fhで変換、メインの式をg_repeatで変換して、レジスタ割り当てされた新しいプログラムを返す。hregenvに登録し、関数本体をg_repeatで変換。g_repeatgを呼ぶ。gLetの場合は次のような処理をする。
g'_and_restoreで割り当てるg自身を再帰的に呼んで後続命令列のレジスタ割り当てを行うg'_and_restoreg'をラップする。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の処理 前編ここがレジスタ割り当ての中心であるので詳しく扱う。
前述の通り、ここでの処理は次の三ステップである。
g'_and_restoreで割り当てる。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)は必要になる。
レジスタが不足したとき以外にも変数がレジスタから外れ、バックトラックを起こすことがある。 それが関数呼び出しと条件分岐である。
これらはそれぞれ一つの仮想命令なのでg'に渡されるが、実際の処理は専用の関数g'_callとg'_ifに書かれている。
MinCamlではcaller-saveなのでレジスタは関数呼び出しで破壊されたと看做す。つまり全ての変数の生存期間はそこで区切られるので、全変数のForgetを呼び出しの直後に挿入してバックトラックする(関数の戻り値を受ける変数を除く。その変数の生存期間は呼び出しの戻った時点から始まるからである)。
これによって呼び出しの引数にならない変数は早めにレジスタを空けることになり、引数になる変数のregister targetingが成功しやすくなる。
条件分岐はもう少し話が複雑になる。
条件分岐の枝はそれぞれ独立した命令列としてg_repeatでレジスタ割り当てを行う。つまりこれらの中でバックトラックは完結し、外には出てこない。
分岐が合流する時が問題で、まず、分岐合流時点で信じられるレジスタ割り当てregenv'を計算する。これは両方の枝の終了時点を比較して、同じレジスタに同じ変数が載っているという共通部分だけを取り出したものになる。
次に、合流後に使われる変数でregenv'に載っていないものをリストアップする。これらは枝のどこかで破壊されてしまうので、合流後も参照されるからといって分岐命令まで生かしておくことはない。そこでそのような変数は全てForgetを分岐命令の直後に挿入してバックトラックする。
これらのForgetは枝の中で参照される変数の生存までは妨げない。
target src dest contsrcが以後の命令列で特定のレジスタで使われることがわかればそのようなレジスタのリストを返す (register targeting)target' src (dest, t) exptargetの下請け。target_args src all n listtargetの下請け。alloc dest cont regenv all xxを割り当てるレジスタrを決めてAlloc(r)を返す。空きレジスタがなければレジスタから溢れる変数yを決めSpill(y)を返す。add x r regenvxとレジスタrの対応をregenvに追加する。xがレジスタであれば何もしない。尚、MinCamlでは変数もレジスタも同じく文字列(Id.t)で表す。区別はその名前がレジスタの名前か否かでしかない。find x t regenvxに対応するレジスタを返す。xがregenvに登録されていなければ例外NoReg(x,t)を発生させる。xがレジスタであればそのまま返す。find' x' regenvid_or_immのx'を受け取り、即値ならそのまま返し、変数ならfindによりレジスタを返す。forget_list xs einsert_forgetの下請け。insert_forget xs exp eexpの後にリストxsにある変数のForgetを挿入して後続命令列eと連結した命令列を作り、ToSpillを返す。g'_ifやg'_callで複数の変数をまとめてForgetするために使われる。g dest cont regenv eeのレジスタ割り当て。g'_and_restore dest cont regenv expg'を呼び、NoRegエラーが発生したらRestoreを挿入。g' dest cont regenv expexpのレジスタ割り当て。g'_if dest cont regenv exp constr e1 e2IfEq等のレジスタ割り当て。g'_call dest cont regenv exp constr ys zsCallDir, CallClsのレジスタ割り当て。g_repeat dest cont regenv eh fundeff progSPARCアセンブリの整数算術命令等では、第2オペランドとしてレジスタ以外に13ビット以内の即値をとることができる(命令ワード内にエンコードできる)。そこで、そのような命令のオペランドとなっている変数が13ビット以内の整数の定数ならば即値で置き換える。
MinCamlでいうと、SparcAsm.expで定義された命令のうちid_or_immという型を含む命令がそれに当たる。
Simm13.gではLetによるリストを順に辿り、変数(仮想レジスタ)への即値代入(Set)であって値が13ビット以内であれば変数と値の対応を記録する。それ以外の命令ならSimm13.g'によって命令ごとに変数から即値への置換を試みる。
Simm13.g'では命令を一つ受け取り、即値をとり得る命令でオペランドが記憶された変数であれば即値に置き換える。
変数の参照が全て即値に置き換えられてしまった場合は変数への代入命令自体も省略する。
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
|---|---|---|---|---|---|---|
| 1 | 2 | |||||
| 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 |
