レジスタ割り当て

多くのプログラミング言語では、プログラマは任意の数の変数を使用できます。コンピュータはCPUのレジスタを高速に読み書きできるため、 CPUのレジスタに格納できる変数が多いほど、コンピュータプログラムの実行速度が速くなります。^{[ 1 ]}また、レジスタにアクセスするコードはよりコンパクトになる場合があり、メモリではなくレジスタを使用するとコードが小さくなり、フェッチ速度が速くなります。ただし、レジスタの数は限られています。そのため、コンパイラがコードを機械語に変換する際には、CPUの限られた数のレジスタに変数をどのように割り当てるかを決定する必要があります。^{[ 2 ] [ 3 ]}

すべての変数が同時に使用されている（または「生きている」）わけではないため、プログラムの実行中に、特定のレジスタが異なる変数を保持するために使用されることがあります。ただし、同時に使用されている 2 つの変数を同じレジスタに割り当てると、いずれかの変数が破損します。すべての変数を保持するのに十分なレジスタがない場合、一部の変数はRAMとの間で移動されることがあります。このプロセスはレジスタの「スピル」と呼ばれます。^{[ 4 ]}プログラムの実行中に、変数はレジスタにスピルされ、レジスタに格納されることがあります。この場合、この変数は「分割」されているとみなされます。^{[ 5 ]} RAM へのアクセスはレジスタへのアクセスよりも大幅に遅いため^{[ 6 ]}、コンパイルされたプログラムの実行速度が遅くなります。したがって、最適化コンパイラは、できるだけ多くの変数をレジスタに割り当てることを目指します。高い「レジスタプレッシャー」は、より多くのスピルとリロードが必要であることを意味する技術用語であり、Braun らによって「命令で同時に生きている変数の数」として定義されています。^{[ 7 ]}

さらに、一部のコンピュータ設計では、頻繁にアクセスされるレジスタをキャッシュしますmove。そのため、可能な限り命令のソースとデスティネーションに同じレジスタを割り当てることで、プログラムをさらに最適化できます。これは、コンパイラが静的単一代入形式（SSA）などの中間表現を使用している場合に特に重要です。特に、SSAが完全に最適化されていない場合、人為的に余分な命令が生成される可能性があります。move

レジスタ割り当てとは、実行時に変数をどこに格納するか、つまりレジスタ内かレジスタ外かを選択することです。変数をレジスタに格納する場合、アロケータはどのレジスタにその変数を格納するかを決定する必要があります。さらに、変数を同じ場所に保持する期間を決定することも課題となります。

レジスタアロケータは、選択された割り当て戦略に関係なく、これらの課題に対処するために一連のコアアクションに頼ることができます。これらのアクションは、いくつかの異なるカテゴリに分類できます。^{[ 8 ]}

挿入の移動

この処理は、レジスタ間の移動命令の数を増やすことで、変数がその存続期間中に1つのレジスタではなく、複数のレジスタに分散して存在するようにします。これは、分割生存範囲方式で行われます。

こぼす

この動作は、レジスタではなくメモリ（ RAMなどの主記憶装置）に変数を格納することによって行われます。^{[ 9 ]}

割り当て

この操作は、レジスタを変数に代入することによって行われます。^{[ 10 ]}

合体

この動作は、レジスタ間の移動回数を制限することによって、命令の総数を制限することから成る。例えば、異なるメソッド間で変数を識別し、その変数の全寿命にわたって1つのレジスタに格納することによって実現される。^{[ 9 ]}

多くのレジスタ割り当て手法は、1つまたは複数の特定の動作カテゴリに最適化されている。

レジスタ割り当てにはいくつかの問題があり、それらはさまざまなレジスタ割り当て手法によって対処（または回避）できます。最も一般的な3つの問題は次のとおりです。

エイリアシング

一部のアーキテクチャでは、あるレジスタに値を割り当てると、別のレジスタの値に影響を与えることがあります。これはエイリアシングと呼ばれます。たとえば、x86アーキテクチャには、16ビットまたは8ビットレジスタとしても使用できる汎用32ビットレジスタが4つあります。^{[ 11 ]}この場合、eaxレジスタに32ビット値を割り当てると、alレジスタの値に影響します。

着色前

この問題は、特定のレジスタにいくつかの変数を強制的に割り当てる行為です。たとえば、PowerPC の呼び出し規約では、パラメータは一般的に R3-R10 に渡され、戻り値は R3 に渡されます。^{[ 12 ]}

NP問題

Chaitin らは、最適なレジスタ割り当てがNP 完全問題であることを示した。この NP 完全性は、問題の構造に完全に依存する。SSA 形式のプログラムの場合、レジスタ割り当て問題のグラフ彩色部分は線形時間で解けることが示されている。一般的なグラフ彩色問題が NP 完全である原因と、レジスタ割り当て問題のいくつかのバージョンが NP 完全である原因は異なる。^{[ 13 ]}

レジスタ割り当てを解決するための主流のアプローチはグラフ彩色割り当てです。^{[ 17 ] [ 18 ]}これはChaitinらによって最初に提案されました。^{[ 4 ]} このアプローチでは、グラフのノードはレジスタ割り当ての候補となるライブ範囲（変数、一時変数、仮想/シンボルレジスタ）を表します。エッジは干渉するライブ範囲、つまり少なくとも1つのプログラムポイントで同時にライブであるライブ範囲を接続します。レジスタ割り当ては、エッジで接続された2つのノードが同じ色を受け取らないようにノードに色（レジスタ）を割り当てるグラフ彩色問題に帰着します。^{[ 19 ]}

活性解析を使用すると、干渉グラフを構築できます。干渉グラフは、ノードがプログラムの変数であるインターバルグラフであり、どの変数を同じレジスタに割り当てることができないかをモデル化するために使用されます。^{[ 20 ]}

原理

Chaitin スタイルのグラフ彩色レジスタ割り当ての主なフェーズは次のとおりです。^{[ 18 ]}

1. 番号変更：ソースプログラムでリアルタイムの射程情報を確認します。
2. 構築：干渉グラフを構築します。
3. 結合：コピー命令によって関連付けられた、互いに干渉しない変数の有効範囲をマージします。
4. スピルコスト：各変数のスピルコストを計算します。これは、変数をメモリにマッピングすることが最終的なプログラムの速度に与える影響を評価するものです。
5. 簡略化：推論グラフ内のノードの順序を構築する
6. スピルコード：レジスタとメモリ間で値をやり取りするためのロード命令やストア命令などのスピル命令を挿入します。
7. 選択：各変数にレジスタを割り当てる。

線形スキャンは、もう 1 つのグローバル レジスタ割り当てアプローチです。これは、1999 年に Poletto らによって最初に提案されました。^{[ 28 ]}このアプローチでは、コードはグラフに変換されません。代わりに、すべての変数が線形にスキャンされ、区間として表される有効範囲が決定されます。すべての変数の有効範囲が判明したら、区間が時系列順に走査されます。この走査は、有効範囲が干渉する変数を特定するのに役立つ可能性がありますが、干渉グラフは構築されず、変数は貪欲に割り当てられます。^{[ 26 ]}

このアプローチの動機はスピードです。生成されたコードの実行時間ではなく、コード生成に費やす時間です。通常、標準的なグラフ彩色アプローチは高品質のコードを生成しますが、かなりのオーバーヘッドがあります。^{[ 29 ] [ 30 ]}使用されているグラフ彩色アルゴリズムは、2 乗のコストを持っています。^{[ 31 ]}この特徴により、線形スキャンは現在、Hotspot クライアントコンパイラ、V8、Jikes RVM、^{[ 5 ]}および Android Runtime (ART) ^{[ 32 ]}など、いくつかの JIT コンパイラで使用されているアプローチです。Hotspot サーバーコンパイラは、優れたコードのためにグラフ彩色を使用しています。^{[ 33 ]}

リニアスキャンレジスタ割り当て アクティブ ← {} 各ライブ間隔iについて、開始点の昇順で、 ExpirEldIntervals(i) length(active) = Rの場合 SpillAtInterval(i) それ以外 register[i] ← 空きレジスタプールから削除されたレジスタi をアクティブに 追加し、エンドポイントの昇順でソートします。 アクティブな各間隔j に対して、終了点の昇順でExpireOldIntervals(i) を実行し、もしendpoint[j] ≥ startpoint[i]ならば、j をアクティブから 削除する。 レジスタ[j]を空きレジスタのプールに追加する SpillAtInterval(i) 流出 ← アクティブな最後の間隔 終点[spill] > 終点[i ]ならば 登録[i] ← 登録[spill] 場所[spill] ← 新しいスタック位置 活性物質からこぼれた物質を取り除くi をアクティブに 追加し、エンドポイントの昇順でソートする。 それ以外の場合は location[i] ← 新しいスタック位置

欠点と今後の改善点

しかし、線形スキャンには 2 つの大きな欠点があります。まず、貪欲な性質のため、ライフタイム ホール、つまり「変数の値が不要な範囲」を考慮しません。^{[ 35 ] [ 36 ]}さらに、スピルされた変数は、そのライフタイム全体にわたってスピルされたままになります。

ポレットの線形スキャンアルゴリズムに続いて、他にも多くの研究が行われました。たとえば、トラウブらは、より高品質なコードを生成することを目的としたセカンドチャンスビンパッキングと呼ばれるアルゴリズムを提案しました。^{[ 37 ] [ 38 ]}このアプローチでは、スピルされた変数は、標準的な線形スキャンアルゴリズムで使用されるものとは異なるヒューリスティックを使用して、後でレジスタに格納される機会を得ます。このアルゴリズムは、ライブインターバルを使用する代わりに、ライブレンジに依存しています。つまり、あるレンジをスピルする必要がある場合、その変数に対応する他のすべてのレンジをスピルする必要はありません。

線形スキャン割り当てもSSA形式を利用するように適応されました。この中間表現の特性により割り当てアルゴリズムが簡素化され、ライフタイムホールを直接計算できるようになります。^{[ 39 ]}まず、ライフタイム間隔の構築を目的としたデータフローグラフ分析に費やされる時間が短縮されます。これは、変数が一意であるためです。^{[ 40 ]}その結果、新しい割り当てごとに新しいライフ間隔が生成されるため、ライフ間隔が短くなります。^{[ 41 ] [ 42 ]}間隔とライフホールのモデリングを回避するために、ロジャースは命令の80%の間隔をうまく除去する未来アクティブセットと呼ばれる簡略化を示しました。^{[ 43 ]}

レジスタ割り当ての文脈では、コヒーレンスとは、変数間移動操作をマージして、それらの2つの変数を同じ場所に割り当てる行為です。コヒーレンス操作は、干渉グラフが構築された後に行われます。2つのノードがコヒーレンスされると、コピー操作が不要になった時点で、それらは同じ色になり、同じレジスタに割り当てられる必要があります。^{[ 44 ]}

合体処理は、干渉グラフの着色可能性にプラスとマイナスの両方の影響を与える可能性があります。^{[ 9 ]}例えば、合体処理がグラフ推論の着色可能性に与えるマイナスの影響の 1 つは、2 つのノードが合体される場合です。これは、結果のノードが合体されるノードのエッジの和集合を持つためです。^{[ 9 ]} 合体処理が推論グラフの着色可能性に与えるプラスの影響は、例えば、ノードが合体される両方のノードと干渉する場合、ノードの次数が 1 つ減少し、干渉グラフの全体的な着色可能性が向上することです。^{[ 45 ]}

合体ヒューリスティックはいくつかあります: ^{[ 46 ]}

積極的な合体

これは、Chaitin のオリジナルのレジスタアロケータで初めて導入されました。このヒューリスティックは、干渉しないコピー関連のノードを統合することを目的としています。^{[ 47 ]}コピー排除の観点からは、このヒューリスティックが最良の結果をもたらします。^{[ 48 ]}一方、積極的な統合は、推論グラフの色付け可能性に影響を与える可能性があります。^{[ 45 ]}

保守派の結集

主にアグレッシブ・コライジングと同じヒューリスティックを使用するが、干渉グラフの彩色性を損なわない場合に限り、移動をマージする。^{[ 49 ]}

反復合体

これは、グラフの着色可能性を維持しながら、一度に1つの特定の動きを削除します。^{[ 50 ]}

楽観的な統合

これは積極的な合体に基づいているが、推論グラフの彩色可能性が損なわれる場合は、可能な限り少ない移動を放棄する。^{[ 51 ]}