Download presentation
Presentation is loading. Please wait.
1
レジスタの割付け 中田育男著 コンパイラの構成と最適化 朝倉書店, 1999年 第１２章５節
2
様々な問題 レジスタ割付けのタイミング レジスタ割付けの範囲 命令語の選択の後 命令語の選択の前 命令語を作るたびにレジスタ割付け
レジスタは無限にあると仮定して命令語を作る。 命令語の選択の前 中間コードの変数をレジスタに割り当ててから 目的コードを生成。 命令語を作るたびにレジスタ割付け レジスタ割付けの範囲 プログラム全体 １つのサブルーチン ループ（多重ループの内側から）
3
様々な問題 どのレジスタを割付けの対象とするか。 できる限り範囲を広げる。 レジスタの役割を決めてしまう。
大域的なレジスタ・局所的なレジスタ サブルーチンの引数や結果の値
4
簡単な割付け法 変数の参照回数 参照頻度の高いものから順次に割り付ける。 n-1までこれで割付ける。
変数 … 中間コードの変数や命令語のレジスタ 参照頻度の高いものから順次に割り付ける。 n-1までこれで割付ける。 n: レジスタの数 それ以外の変数は残したレジスタにLoadする。
5
簡単な割付け法（その二） プログラムの先頭から順次割付ける。 空いているレジスタがなくなったら… を選んでその内容を退避して利用。
その場所以降で次に使われる場所が最も 遠い変数が入っているレジスタ その場所以降でその値が使われる回数が 最小のもの その値が最近使われたところから その場所までの長さが最も長いもの を選んでその内容を退避して利用。
6
生存区間の干渉グラフを使った レジスタ割付け
生存区間をノードとし、生存区間に重なりのある ２つの生存区間を辺で結んだ無向グラフ 変数の生存区間 変数が生きている区間 生きているとは、その値が使われる可能性が あるということ。 大域的にはデータの流れの解析が必要。
7
生存区間 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
8
干渉グラフ a 1 2 3 4 a b b d c d c
9
生存区間の干渉グラフを使った レジスタ割付け
干渉グラフにおいて、ノードxとyが辺で 結ばれていたら、同じレジスタに割付け することはできない。 同じレジスタ番号＝同じ色 レジスタ数＝色の数 彩色問題 NP困難
10
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の生存区間を分割する このアルゴリズムの先頭に戻る
11
例（N=3） a c h g b d f e
12
例（N=3） f d,e a c h g b d e
13
例（N=3） c b,a f d,e a h g b d e
14
例（N=3） d* h,g,b,e c b,a f d,e a h g b e
15
例（N=3） dの生存区間を分割 このためには、 生存区間のグラフを 参照しなければならない。 a c h g b d d’ f スピル e
16
分割の遅延 d* h,g,b,e c b,a f d,e a h g b e
17
分割の遅延 e b,g d* h,g,b,e c b,a f d,e a h g b
18
分割の遅延 b a e b,g d* h,g,b,e c b,a f d,e a h g
19
分割の遅延 a g,h b e b,g d* h,g,b,e c b,a f d,e h g
20
分割の遅延 h g a g,h b e b,g d* h,g,b,e c b,a f d,e g
21
分割の遅延 g h a g,h b e b,g d* h,g,b,e c b,a f d,e
22
分割の遅延 g 1 h a g,h b e b,g d* h,g,b,e c b,a f d,e g
23
分割の遅延 g 1 h 2 a g,h b e b,g d* h,g,b,e c b,a f d,e h g
24
分割の遅延 g 1 h 2 a 3 b e b,g d* h,g,b,e c b,a f d,e a h g
25
分割の遅延 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
26
分割の遅延 g 1 h 2 a 3 b e d* h,g,b,e c b,a f d,e a h g b e
27
分割の遅延 g 1 h 2 a 3 b e d* c b,a f d,e a h g b d e
28
分割の遅延 g 1 h 2 a 3 b e d* c f d,e a c h g b d e
29
分割の遅延 g 1 h 2 a 3 b e d* c f a c h g b d f e
30
生存区間の合併 コピー命令 a = b があるときに、 aとbに同じレジスタを 割り付けて、コピー命令を不要とする。 積極的な合併
スピルの原因 保守的な合併 繰り返し合併
31
保守的な合併（MCIiJ Chapter 11）
Briggs 合併ノードabと隣り合うノードのうち、 Ｋ個以上のノードと隣り合うものの数は Ｋより小さい。 George aと隣り合う任意のノードtに対して、 tはbと干渉しているか(tとbは隣り合うか)、 tはＫより少ない数のノードとしか隣り合わない Ｋ: 使えるレジスタ数
32
繰り返し合併の例 使えるレジスタ数は４ f e j k b m d h c Briggsによると 合併はできない。 g
33
まず単純化 使えるレジスタ数は４ f e j k b m d h c g
34
まず単純化 使えるレジスタ数は４ f e j k b m d c g
35
まず単純化 使えるレジスタ数は４ f e j k b m d c
36
まず単純化 使えるレジスタ数は４ f e j b m d c
37
まず単純化 使えるレジスタ数は４ e j b m d c
38
まず単純化 使えるレジスタ数は４ j b m d c
39
まず単純化 使えるレジスタ数は４ j b d c
40
合併 使えるレジスタ数は４ jb d c
41
合併 使えるレジスタ数は４ jb dc
Similar presentations
