レジスタの割付け 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第１２章５節

様々な問題 レジスタ割付けのタイミング レジスタ割付けの範囲 命令語の選択の後 命令語の選択の前 命令語を作るたびにレジスタ割付け レジスタは無限にあると仮定して命令語を作る。 命令語の選択の前 中間コードの変数をレジスタに割り当ててから 目的コードを生成。 命令語を作るたびにレジスタ割付け レジスタ割付けの範囲 プログラム全体 １つのサブルーチン ループ（多重ループの内側から）

様々な問題 どのレジスタを割付けの対象とするか。 できる限り範囲を広げる。 レジスタの役割を決めてしまう。 大域的なレジスタ・局所的なレジスタ サブルーチンの引数や結果の値

簡単な割付け法 変数の参照回数 参照頻度の高いものから順次に割り付ける。 n-1までこれで割付ける。 変数 … 中間コードの変数や命令語のレジスタ 参照頻度の高いものから順次に割り付ける。 n-1までこれで割付ける。 n: レジスタの数 それ以外の変数は残したレジスタにLoadする。

簡単な割付け法（その二） プログラムの先頭から順次割付ける。 空いているレジスタがなくなったら… を選んでその内容を退避して利用。 その場所以降で次に使われる場所が最も 遠い変数が入っているレジスタ その場所以降でその値が使われる回数が 最小のもの その値が最近使われたところから その場所までの長さが最も長いもの を選んでその内容を退避して利用。

生存区間の干渉グラフを使った レジスタ割付け 生存区間をノードとし、生存区間に重なりのある ２つの生存区間を辺で結んだ無向グラフ 変数の生存区間 変数が生きている区間 生きているとは、その値が使われる可能性が あるということ。 大域的にはデータの流れの解析が必要。

生存区間 do i = … 1: a = c * d 2: b = d + a 3: c = a – 5 4: d = b * c end do 1 2 3 4 a b c d

干渉グラフ a 1 2 3 4 a b b d c d c

生存区間の干渉グラフを使った レジスタ割付け 干渉グラフにおいて、ノードxとyが辺で 結ばれていたら、同じレジスタに割付け することはできない。 同じレジスタ番号＝同じ色 レジスタ数＝色の数 彩色問題 NP困難

Chatinのアルゴリズム 生存区間から干渉グラフGを作る spill_listを空とする while Gは空でない do if deg(x)<Nなるxが存在する then x（およびxからのすべての辺）をGから取り除く else Gのノードxを選びxをspill_listに加える end if end while if spill_listが空 then 取り除いた順序の逆順にノードに彩色する。 spill_listの各ノードxの生存区間を分割する このアルゴリズムの先頭に戻る

例（N=3） a c h g b d f e

例（N=3） f d,e a c h g b d e

例（N=3） c b,a f d,e a h g b d e

例（N=3） d* h,g,b,e c b,a f d,e a h g b e

例（N=3） dの生存区間を分割 　　このためには、 　　生存区間のグラフを 　　参照しなければならない。 a c h g b d d’ f スピル e

分割の遅延 d* h,g,b,e c b,a f d,e a h g b e

分割の遅延 e b,g d* h,g,b,e c b,a f d,e a h g b

分割の遅延 b a e b,g d* h,g,b,e c b,a f d,e a h g

分割の遅延 a g,h b e b,g d* h,g,b,e c b,a f d,e h g

分割の遅延 h g a g,h b e b,g d* h,g,b,e c b,a f d,e g

分割の遅延 g h a g,h b e b,g d* h,g,b,e c b,a f d,e

分割の遅延 g 1 h a g,h b e b,g d* h,g,b,e c b,a f d,e g

分割の遅延 g 1 h 2 a g,h b e b,g d* h,g,b,e c b,a f d,e h g

分割の遅延 g 1 h 2 a 3 b e b,g d* h,g,b,e c b,a f d,e a h g

分割の遅延 g 1 h 2 a 3 b e b,g d* h,g,b,e c b,a f d,e a h g b

分割の遅延 g 1 h 2 a 3 b e d* h,g,b,e c b,a f d,e a h g b e

分割の遅延 g 1 h 2 a 3 b e d* c b,a f d,e a h g b d e

分割の遅延 g 1 h 2 a 3 b e d* c f d,e a c h g b d e

分割の遅延 g 1 h 2 a 3 b e d* c f a c h g b d f e

生存区間の合併 コピー命令 a = b があるときに、 aとbに同じレジスタを 割り付けて、コピー命令を不要とする。 積極的な合併 スピルの原因 保守的な合併 繰り返し合併

保守的な合併（MCIiJ Chapter 11） Briggs 合併ノードabと隣り合うノードのうち、 Ｋ個以上のノードと隣り合うものの数は Ｋより小さい。 George aと隣り合う任意のノードtに対して、 tはbと干渉しているか(tとbは隣り合うか)、 tはＫより少ない数のノードとしか隣り合わない Ｋ: 使えるレジスタ数

繰り返し合併の例 使えるレジスタ数は４ f e j k b m d h c Briggsによると 合併はできない。 g

まず単純化 使えるレジスタ数は４ f e j k b m d h c g

まず単純化 使えるレジスタ数は４ f e j k b m d c g

まず単純化 使えるレジスタ数は４ f e j k b m d c

まず単純化 使えるレジスタ数は４ f e j b m d c

まず単純化 使えるレジスタ数は４ e j b m d c

まず単純化 使えるレジスタ数は４ j b m d c

まず単純化 使えるレジスタ数は４ j b d c

合併 使えるレジスタ数は４ jb d c

合併 使えるレジスタ数は４ jb dc