Coinsのレジスタ割り付けアルゴリズムは、Graph Coloringアルゴリズムの改良型であるAppel-GeorgeのIterated Register Coalescingをベースにしている。
さらに、sparcの浮動小数点レジスタやintel x86のeax/ah,alレジスタを扱うため、ペアレジスタを含むレジスタセットを効率よく割り付けられるよう拡張している。
レジスタ割り付け問題を形式的に述べると以下のようになる。
このとき、各変数vに対して以下の条件を満たすレジスタrvを割り付ける。
この問題はNP完全なので、現実的時間で最適解を求めるアルゴリズムは知られていない。近似解を求めるアルゴリズムを考えることになる。
我々の考えているモデルでは、各レジスタは単一のレジスタとは限らず、複数のレジスタが組になったものもある。つまりriとrj(i≠j)が一部重なっている可能性もあるので、さらに問題は複雑である。
上記の条件を満たす割り当てが見つからなかった場合、一部変数に対してはレジスタの割り付けをあきらめる。このようなケースをspilling(溢れ)という。spillingが起こった場合は、レジスタをメモリに保存/再読み込みする命令をプログラム中に挿入する必要がある。
まずグラフカラーリングによるレジスタ割り付けアルゴリズムをおさらいしておく。
変数vを頂点とし、干渉している変数どうしを辺で結んだ無向グラフGを作る。これを干渉グラフ(Interference Graph)と呼ぶ。ある頂点と辺で結ばれている他の頂点を隣接点、頂点vから出ている辺の数をvの次数(degree)と言う。このグラフの各頂点に、隣接点とは異なるレジスタ(色)を割当てるのが目的である。
以下にアルゴリズムを示す。|Av|はAvの要素数、つまりvに対して割り付けられるレジスタの数である。
スタックSを空にする
while (Gに頂点が残っている) {
if (degree(v) < |A|である頂点vがある)
vをGから除く
else
適当なspill候補vを探してGから除く
S.push(v)
}
while (Sが空でない) {
v = S.pop()
v の隣接点で使われていないレジスタをAから選んで割当てる
空きレジスタが見つからなければ、vにspillの印を付ける
vをGの元の位置に挿入する
}
次に、このアルゴリズムにCoalescing処理を追加する。Coalescingとは、干渉していない二つの変数がコピー命令のオペランドに現れているとき、それらに同じレジスタを割り付けることによって、より効率のよいコードを生成するための技法である。
Coalescingを行うと、干渉グラフ上では二つの頂点が一つに併合されることになり、グラフは簡約された形になる。しかし併合された頂点は次数が大きくなるので、下手にcoalescingするとカラーリング可能だったグラフが不可能に変わってしまうかもしれない。そこで、このようなことが起こらないことを確認しつつcoalescingを行う。
スタックSを空にする
while (Gに頂点が残っている) {
if (Briggs条件を満たすコピー対の変数vとwがある)
vとwを併合する
else if (degree(v) < |A|である頂点vがある)
vをGから除いて S.push(v)
else
適当なspill候補vを探してGから除いて S.push(v)
}
while (Sが空でない) {
v = S.pop()
v の隣接点で使われていないレジスタをAから選んで割当てる
空きレジスタが見つからなければ、vにspillの印を付ける
vをGの元の位置に挿入する
}
変数vとwがBriggs条件を満たすとは、次のような場合をいう。
vとwを併合したグラフG'での新頂点vwの隣接点のうち、高い次数をもつ頂点の数が|Av∩Aw| (vとwの両方に割り付け可能なレジスタの数)よりも小さい
ここで頂点xが「高い次数をもつ」とは、degree(x)≧|Ax|ということである。つまり高い次数をもたない頂点は、いずれグラフから除かれるので、そのような隣接点は実質的次数には数えなくてよいということである。
Briggs条件を満たしている二頂点を併合しても、元々カラーリング可能なグラフがカラーリング不可能に変わることはない。
次はレジスタペアを扱えるように改良する。
intel 8086プロセッサを例に考えよう。このCPUは16bitレジスタax,bx,cx,dx,si,diをもち、このうちaxからdxは、上位と下位が別々の8bitレジスタah,al,bh,bl,ch,cl,dh,dlとして使える。
このCPUで16bitの変数と8bitの変数が干渉グラフ内に混在しているとき、今までと同じアルゴリズムで正しくレジスタ割り付けができるだろうか？
仮に8bit変数vの次数が4だとする。vにはahからdlまでの8個のレジスタが割当て可能だから、今までのアルゴリズムでは無条件にレジスタ割り付け可能とみなされる。しかし、vと干渉している4つの16bit変数にそれぞれax,bx,cx,dxが割当てられたらどうだろう。もはやvに割当て可能なレジスタは一つも残っていない。だからレジスタペアを含むCPUでは、出ていく辺の数を単純に次数としたのではダメだということがわかる。
そこで、辺に重みをつけてやる。8bitの変数から16bitの変数に向けて出ている辺は重み2として次数を計算するのである。vに4つの16bit変数が干渉しているなら、vの次数は8となる。
逆に、16bit変数の側から見れば、干渉している相手が8bitだろうが16bitだろうが重み1のままでよい。重みは非対称ということになる。
また、8bit変数であっても、その割当て対象のレジスタ集合が{al,bl,cl,dl}であった場合は、重みは1でよい(なぜか？)。
上で見たように、重みは元頂点vと隣接頂点wの割り当て対象レジスタ集合(以降regsetと呼ぶ)の組合せで決定されるが、二つの変数のregsetのリストをコンパイル時にいちいちしらべて重みを求めていたのでは時間がかかってしまう。
実際には、regsetのバリエーションはそれほど多くはないので、考えられるすべてのregsetを事前に列挙し、そのすべての組合せについて重みを求めて表を作成しておけば、高速に処理ができる。また変数がcoalesceされるときには、それらのregsetの共通部分を求める必要があるので、そのための表も作っておく。
MachineParamTable.javaはこのための前処理を行う。
割り付けアルゴリズムは、次数を求めるときに重みを考慮する点以外は、前掲のアルゴリズムBとほとんど同じなので省略する。次数の計算はBriggs条件のテストの際にも影響を及ぼす。
本アルゴリズムには、もう一点従来のグラフカラーリングとは異なる箇所がある。それはspill候補を選ぶ基準である。
Chaitinのアルゴリズムでは、各変数についてそれをspillさせた場合のコストを計算し、コストが最小のものを選んでいた。本アルゴリズムでもspillコストは計算しているが、それよりも優先されるのが、妨害指数(Disturbance Factor)である。
妨害指数とは、その変数の生存範囲において、参照・定義されている変数がいくつあるかを示す数である。妨害指数を求めるためには、まず妨害グラフ(Disturbance Graph)という有向グラフを作る。妨害グラフGは、干渉グラフと同様に変数を頂点にもち、変数wの生存範囲において変数vが参照または定義されているときに限り、辺v→wを含む。
下の例を見てみよう。
x = …; v = …; ... w = 3; … = w; /* last use of w */ … = x; /* last use of x */ ... … = v;
この例では、妨害グラフは{w→v,w→x,x→v,v→x}の4つの辺を持つ。その心は、「v,xにとってwは邪魔な存在だが、wにとってはvやxは邪魔ではない(存在しないも同然)。一方xとvは互いに相手の邪魔をしている」ということである。
これが干渉グラフだと{v-w,v-x,w-x}となり、wとvの一方通行関係については全くわからない。
この妨害グラフから、妨害指数を求める。vの妨害指数とは、vに向かっている辺の数である(重みは関係なし)。そして、各頂点vにつき、vの妨害指数から|Av|を引いた差を求め、この差が最大のものをspill候補とする。
すると、妨害指数の高い変数ほど早くグラフから除かれ、割り付け順序が後にまわされることになる。上の例ではvやxはwより後で割当てられるわけである。
本アルゴリズムは、レジスタがプログラムのどの部分で壊されるのかを見ていない。そのため、いったん変数にspillの印がつけられると、プログラム全体を通してメモリに置かれることになり、かなり効率を低下させる。
実際は、プログラムのごく一部(例えば関数呼出しの前後)でのみ破壊され、それ以外の部分では値をレジスタに置いておけるケースも多いのだが、現在の実装ではすべてメモリ参照になってしまう。
将来は、spill候補を選ぶさいに地理的情報を調べ、なるべく多くの部分でレジスタに置いたままのコード生成ができるように改良すべきだろう。
■