2005年07月29日

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.gEmit.g'等)には最後の値を返すレジスタの指定であるdestが与えられる。これは命令に出力オペランドを持たず、命令列も最後はAnsノードなので同様に出力先を持たないためである。

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

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

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

TailNonTailで大きく分かれる。

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

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

Save, Restoreとスタックの管理

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

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

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は浮動小数点数である。raddrreg_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としている。

2005年07月28日

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である。LetAnsはそれぞれ命令を一つ指す。

これらの命令には入力オペランドの情報はあるが、出力オペランドはその命令を持つ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'_ifg'_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がやり直しにおいてレジスタ割り当てを改善するのは、fvForgetされた変数をそれ以後参照されないと看做すためである。これにより、その変数の生存期間は直前に参照された時点までで切り詰められ、そこから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'_callg'_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に対応するレジスタを返す。xregenvに登録されていなければ例外NoReg(x,t)を発生させる。xがレジスタであればそのまま返す。
find' x' regenv
id_or_immx'を受け取り、即値ならそのまま返し、変数ならfindによりレジスタを返す。
forget_list xs e
insert_forgetの下請け。
insert_forget xs exp e
命令expの後にリストxsにある変数のForgetを挿入して後続命令列eと連結した命令列を作り、ToSpillを返す。g'_ifg'_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
プログラム全体のレジスタ割り当て。

2005年07月24日

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

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

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

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

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

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

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。