レジスタの割付け • • • • 中田育男著コンパイラの構成と最適化朝倉書店, 1999年第１２章５節様々な問題 • レジスタ割付けのタイミング – 命令語の選択の後 • レジスタは無限にあると仮定して命令語を作る。 – 命令語の選択の前 • 中間コードの変数をレジスタに割り当ててから目的コードを生成。 – 命令語を作るたびにレジスタ割付け • レジスタ割付けの範囲 – プログラム全体 – １つのサブルーチン – ループ（多重ループの内側から）様々な問題 • どのレジスタを割付けの対象とするか。 – できる限り範囲を広げる。 – レジスタの役割を決めてしまう。 • 大域的なレジスタ・局所的なレジスタ • サブルーチンの引数や結果の値簡単な割付け法 • 変数の参照回数変数 … 中間コードの変数や命令語のレジスタ • 参照頻度の高いものから順次に割り付ける。 • n-1までこれで割付ける。 n: レジスタの数 • それ以外の変数は残したレジスタにLoadする。簡単な割付け法（その二） • プログラムの先頭から順次割付ける。 • 空いているレジスタがなくなったら… – その場所以降で次に使われる場所が最も遠い変数が入っているレジスタ – その場所以降でその値が使われる回数が最小のもの – その値が最近使われたところからその場所までの長さが最も長いもの • を選んでその内容を退避して利用。生存区間の干渉グラフを使ったレジスタ割付け • 生存区間の干渉グラフ – 生存区間をノードとし、生存区間に重なりのある２つの生存区間を辺で結んだ無向グラフ • 変数の生存区間 – 変数が生きている区間 – 生きているとは、その値が使われる可能性があるということ。 – 大域的にはデータの流れの解析が必要。生存区間 do i = 1: a = 2: b = 3: c = 4: d = end do … c d a b * + – * d a 5 c 1 2 3 4 a b c d 干渉グラフ a 1 2 3 4 a b d b 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に加える x（およびxからのすべての辺）をGから取り除く end if end while if spill_listが空 then 取り除いた順序の逆順にノードに彩色する。 else spill_listの各ノードxの生存区間を分割するこのアルゴリズムの先頭に戻る end if 例（N=3） a c h b d f e g 例（N=3） a c h b d e g f d,e 例（N=3） a h b d e g c b,a f d,e 例（N=3） a h g b e d* h,g,b,e c b,a f d,e 例（N=3） dの生存区間を分割このためには、生存区間のグラフを参照しなければならない。 a c h b d d’ g f e スピル分割の遅延 a h g b e d* h,g,b,e c b,a f d,e 分割の遅延 a h b g e d* c f b,g h,g,b,e b,a d,e 分割の遅延 a h g b e d* c f a b,g h,g,b,e b,a d,e 分割の遅延 h g a b e d* c f g,h a b,g h,g,b,e b,a d,e 分割の遅延 g h a b e d* c f g g,h a b,g h,g,b,e b,a d,e 分割の遅延 g h a b e d* c f g g,h a b,g h,g,b,e b,a d,e 分割の遅延 g g h a b e d* c f 1 g g,h a b,g h,g,b,e b,a d,e 分割の遅延 h g g h a b e d* c f 1 2 g,h a b,g h,g,b,e b,a d,e 分割の遅延 a h g g h a b e d* c f 1 2 3 a b,g h,g,b,e b,a d,e 分割の遅延 a h b g g h a b e d* c f 1 2 3 1 b,g h,g,b,e b,a d,e 分割の遅延 a h g b e g h a b e d* c f 1 2 3 1 2 h,g,b,e b,a d,e 分割の遅延 a h b d e g g h a b e d* c f 1 2 3 1 2 3 b,a d,e 分割の遅延 a c h b d e g g h a b e d* c f 1 2 3 1 2 3 2 d,e 分割の遅延 a c h b d f e g g h a b e d* c f 1 2 3 1 2 3 2 1 生存区間の合併 • コピー命令 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 g c Briggsによると合併はできない。まず単純化使えるレジスタ数は４ f e j k b d h g c m まず単純化使えるレジスタ数は４ f e j k b d g c m まず単純化使えるレジスタ数は４ f e j k b d c m まず単純化使えるレジスタ数は４ f e j b d c m まず単純化使えるレジスタ数は４ e j b d c m まず単純化使えるレジスタ数は４ j b d c m まず単純化使えるレジスタ数は４ j b d c 合併使えるレジスタ数は４ jb d c 合併使えるレジスタ数は４ jb dc