レジスタ割り当てとは
変数(すなわち無限個の仮想レジスタ)の処理を有限個の実レジスタに落とし込む処理である。変数を極力レジスタに割り当て、どうしてもレジスタが足りないときは変数をスタックに割り当てて退避し、レジスタを空ける。
「概説」の要約
「概説」の説明は有用な情報を含んでいるがそのままではまとまりに欠けるので、ここで整理要約させて頂く。
- 関数呼び出し規約: 引数はレジスタに順に載せる。戻り値は第一レジスタ。これら関数の出入口の処理は
RegAlloc.hで実装。
- 式(関数本体、メインルーチン)のレジスタ割り当て:
RegAlloc.g。変数からレジスタへの写像regenvと命令列を受け取りレジスタ割り当てを行った命令列と新しいregenvをデータ型NoSpillで返す。
- どのレジスタに変数を割り当てるか
- 空いているレジスタ (生きている変数の入っていないレジスタ)
SparcAsm.fv: まだ生きている変数を返す
(現在の式と、これから後にくる命令列contを調べる)- その変数が次に使われるときに置かれるレジスタをなるべく選び、将来の無駄なmovを削減する (
RegAlloc.target) (register targetingまたはregister coalescing)
- 関数呼び出しは全てのレジスタを破壊するのでそれより先は調べても無意味、戻り値にはそれを示す真偽値を含む
- 空きがなかったら→変数を退避してレジスタを空ける(レジスタ溢れ=register spilling)
- どのレジスタを空けるか←言及なし
- 関数呼び出しでも退避が必要 (レジスタは破壊される)→全ての生きている変数を退避
- レジスタが溢れたら
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の中心となる部分は次のように処理単位の大きさによって関数が分かれ、上位のものがより下位の関数を呼んで処理を行う。
f- プログラム全体のレジスタ割り当て。関数をそれぞれ
hで変換、メインの式をg_repeatで変換して、レジスタ割り当てされた新しいプログラムを返す。
h- トップレベル関数のレジスタ割り当て。変数(クロージャと引数)とレジスタの対応を
regenvに登録し、関数本体をg_repeatで変換。
g_repeat- ひとまとまりの式(メインの式や関数本体)のレジスタ割り当て。実際にレジスタ割り当てするために
gを呼ぶ。
g- 命令列のレジスタ割り当て。命令列中のノード一つを扱うと共に、後続命令列を処理するため自分自身を再帰的に呼ぶ。ノードが
Letの場合は次のような処理をする。
- ノードが指す命令を
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)は必要になる。
レジスタ不足以外の要因によるバックトラック: 関数呼び出しと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) exptargetの下請け。target_args src all n listtargetの下請け。
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' regenvid_or_immのx'を受け取り、即値ならそのまま返し、変数ならfindによりレジスタを返す。
forget_list xs einsert_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 expg'を呼び、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- プログラム全体のレジスタ割り当て。
