Coins Register Allocation Algorithm レジスタ割り当てについて 10/30/2007 soejima yuusuke レジスタ割り当てとは？ • プログラム内の多数の変数を少数のCPUレ ジスタに多重化する技法。 • 実行速度の最大化のため、多くのオペランド をレジスタに保持するようにすること。 • レジスタ割り当てはNP完全問題である。 Spillとは？ • Spillとは「あふれ」であり、レジスタからデータ があふれる事を指す。 • 一般にプログラム内の変数の個数はプロセッ サ上で利用可能なレジスタ数より多い。 • そこで、限られたレジスタ数で、処理に必要な データをメモリとレジスタの間で上手く入れ替 えて高速化を図る。 • このspillのコストを最小化にする事が大きな 目標となる。 生存区間とグラフ化 • 変数の生/死の情報を生存区間という。（live range) • 変数ｘの生存区間と変数ｙの生存区間に共通 部分が無ければ、ｘとｙに同じレジスタを割り 付けることができる。 • 例として区間グラフで見ると分かり易い（例） • これに対して今回利用するグラフが干渉グラ フである。 干渉グラフとは • 生存区間の干渉グラフ（interference graph) とは、各生存区間（変数それぞれの）をノード として、生存区間に重なりがある任意の二つ のノードを辺（無向）で結んだグラフである。 （結ばれた変数については、同じレジスタを割 り当て出来ないので干渉する、と言える為。） • このグラフを用いて割り当てを考える。 基本となるアルゴリズム • 基本となるのは彩色アルゴリズム（graph coloring algorithm）。（プリント参照） • この基本アルゴリズムを改良していくことを 考える。 合併（coalescing) • 例えば、「a=b」というコピー命令があるとき、 a,bに同じレジスタを割り当てて、コピー命令 を不要にするとき、これを「合併」と呼ぶ。 • 合併には様々な種類がある。 ・chaitin-aggressive coalescing ・briggs-conservative coalescing ・geroge,appel-iterative coalescing ・park-optimistic coalescing 目標：卒論のテーマ • Coinsで現在実装されているiterated register coalescingから、より効果的と言われている、 optimistic registere coalescingに実装し変え る、とういうのが目標。 • 現段階では、双方の論文を読み、（実験結果 等までは読めてない）それぞれ、どのような考 えが使われているかをまとめた。 主となるchaitinのレジスタ割り当てについて • ３０２－fig-１参照 • ５ステップのフェーズに分かれている。 ・bulid (データフロー解析より干渉グラフ作成） ・coalesce（右、左辺の変数で干渉してない代入文を合併） ・simplify （法則に従い、ノードを減らしていく） ・spill （減らせないノードを選ぶ、つまりメモリーに移す） ・select （具体的に色を付けていく） • ここでの合併はaggressive（積極的）な合併 とされている 合併の弊害（negative impact） • 合併後のノードは前より通常、より多くの隣接 ノードを持つので、時に、向こう見ずな合併に より、元々色塗り可能なグラフが不可能なも のに変わってしまう恐れがある。 • またcalling conventionによってあるノードが 特別なレジスタに割り当てられてる場合（これ をprecolorと呼ぶ）、このような合併ができな い場合も出てくる。 Briggsのconservative coalescing(保守的な合併） • 以下の定義がベースとなっている。以下度数 （度数とはそのノードの隣接ノードの数）をdig とし、使える最大レジスタ数をKとする。 「ｘ、ｙというノードが与えられていて、二つは合併できる状態 であるとする。もし合併後のｘｙというノードがK個未満のdig がｋ以上のノードを持っていたなら、その合併は色塗り可能 性を変えない。」 • なぜ保守的なのか？ Biased coloringについて • Conservativeの合併ではspillせず、たくさん の代入文（コピー文）を取り除けたが、取れな い物もあった。 – それを解決するのがbias～である。これはselect のフェーズで行われる。（説明） – 具体的な例が３０４のfig-2 他にも・・ • 再実体化 – メモリ上にすでにある値をメモリからロードせずに 再度計算をしてレジスタをあけるようにする • 定数畳みこみ – a=bで両方が定数だったら合併してしまえる。 Iterated register coalescing • グラフ彩色レジスタ割り当ては全ての代入文 を消してspillをなるべく減らしたい。 – Aggressiveはたくさんのspillを生み出す – Conservativeはたくさんの代入文を残す • このアルゴリズムはコピー伝搬とレジスタ割り 当てを統合し、不必要なスピル、代入文なし に有効にレジスタを使用できる。 George,appelのiteratedレジスタ割り当てについて • 306 fig-５参照 • 主に５つのフェーズに分かれてる – – – – – Bulid Simplify Coalesce Freeze Select • ３０９で具体的にどう行われてるか説明 Optimistic coloring • Spillの決定を遅らせる・・途中２種類のspill – Potential spill • Simplifyにおいて、dig<Kのノードが無い時にspillの マークをつける代わりにグラフからただとってスタック に入れる。 – Actual spill • Select時にnodeに対して割り当てる色がない時。 今までのcoalescingについて • Aggressive – どんな干渉してない合併できるノードは全て合併 – コピー削除の量は多いがspillはよくない • Conservative – 彩色の可能性が不変なら合併する • Iterated – Conservativeよりもコピー削除する – Simplifyにおいてbriggsのcon~を行い、より保守 的な合併を行う 合併の利点 • Conservative,iteratedは合併のnegativeな 所を避けてきたが、彩色可能性を高めるとい うことを無視したものだったーー例 • Optimistic coalescingはaggressive同様、全 ての干渉してない合併できるノードを合併。し かし合併がspillを必要としたら諦めて、別々 のノードに分け、度数を減らし、彩色可能性を 増やし、spillも減るという手法 ParkのOptimisticレジスタ割り当てについて • 主に４つと２つのspillに分かれる – Build – Aggressive coalesce – Chaitin-style simplify – Select(undo coalescing) – (potential spill,actual spill) • 744 fig-６でデータフロー図 Optimisticのアイデアについて • これは、aggressiveと同じくらいコピー削除を し、だが、大幅に合併ノードのspillも減らし他 の合併方法を上回る結果に – まずaggressive合併を行いそして度数が増える 場合simplifyを行い、potential-spillを作る。 – もし合併ノードがselectでactual-spillになったらそ のノードのspill costを「undoing the coalescing」 で減らす。 • ｘｙについてそれぞれｘ、ｙに戻して干渉グラフに戻して またグラフを見てみる→digが減り色づけし易くなる。 これから・・・ 1. 付録のアルゴリズムを理解 2. コードを読んでiteratedの方を理解 3. 見習ってoptimisticを実装
© Copyright 2024 ExpyDoc
