Loading article…
コンパイラの最適化 において、レジスタ割り当ては、ローカル自動変数と式の結果を限られた数のプロセッサ レジスタに割り当てるプロセスです。
レジスタ割り当ては、基本ブロック全体(ローカル レジスタ割り当て)、関数/プロシージャ全体(グローバル レジスタ割り当て)、または呼び出しグラフを介して横断される関数境界を越えて (プロシージャ間レジスタ割り当て) 発生する可能性があります。関数/プロシージャごとに実行される場合、呼び出し規約では、各呼び出しサイトの周囲に保存/復元を挿入する必要がある場合があります。
コンテクスト
原理
多くのプログラミング言語では、プログラマーは任意の数の変数を使用できます。コンピューターはCPUのレジスタをすばやく読み書きできるため、CPUのレジスタに多くの変数を配置できると、コンピュータープログラムの実行速度が速くなります。 [1]また、レジスタにアクセスするコードの方がコンパクトな場合もあり、メモリではなくレジスタを使用するとコードが小さくなり、フェッチが速くなります。ただし、レジスタの数には制限があります。したがって、コンパイラーがコードを機械語に変換するときに、CPUの限られた数のレジスタに変数を割り当てる方法を決定する必要があります。[2] [3]
すべての変数が同時に使用される（または「ライブ」である）わけではないので、プログラムの存続期間中、特定のレジスタが異なる変数を保持するために使用される場合があります。ただし、同時に使用されている 2 つの変数を同じレジスタに割り当てると、いずれかの変数が破損します。すべての変数を保持するのに十分なレジスタがない場合は、一部の変数が RAM に移動されたりRAMから移動されたりすることがあります。このプロセスは、レジスタの「スピル」と呼ばれます。[4]プログラムの存続期間中、変数はレジスタにスピルされ、格納される可能性があります。この場合、この変数は「分割」されていると見なされます。[5] RAM へのアクセスはレジスタへのアクセスよりも大幅に遅く[6]、コンパイルされたプログラムの実行速度が遅くなります。したがって、最適化コンパイラは、できるだけ多くの変数をレジスタに割り当てることを目指します。高い「レジスタ圧力」は、より多くのスピルとリロードが必要であることを意味する専門用語です。これは、Braun らによって「命令で同時にライブである変数の数」として定義されています。[7]
さらに、一部のコンピュータ設計では、頻繁にアクセスされるレジスタがキャッシュされます。そのため、可能な限り、命令のソースと宛先に同じレジスタを割り当てることで、プログラムをさらに最適化できますmove。これは、コンパイラが静的単一割り当て形式(SSA)などの中間表現を使用している場合に特に重要です。特に、SSA が完全に最適化されていない場合、追加の命令が人為的に生成される可能性があります。
move
レジスタ割り当てのコンポーネント
したがって、レジスタ割り当ては、実行時に変数をどこに保存するか、つまりレジスタの内側か外側かを選択することから成ります。変数をレジスタに保存する場合、アロケータはどのレジスタにこの変数を保存するかを決定する必要があります。最終的に、変数が同じ場所に留まる期間を決定することも課題となります。
レジスタアロケータは、選択された割り当て戦略に関係なく、これらの課題に対処するために一連のコアアクションに頼ることができます。これらのアクションは、いくつかの異なるカテゴリに分類できます。[8]
- 挿入を移動
- このアクションは、レジスタ間の移動命令の数を増やすことで構成されます。つまり、変数をその存続期間中に 1 つのレジスタではなく、異なるレジスタで存続させます。これは、分割存続範囲アプローチで発生します。
- こぼす
- このアクションは、変数をレジスタではなくメモリに格納することです。[9]
- 割り当て
- このアクションはレジスタを変数に割り当てることから成ります。[10]
- 合体
- このアクションは、レジスタ間の移動回数を制限し、命令の総数を制限することです。たとえば、異なるメソッド間で存続する変数を識別し、その存続期間中は1つのレジスタに格納します。[9]
多くのレジスタ割り当てアプローチは、1 つ以上の特定のアクション カテゴリを最適化します。
レジスタ割り当てでよく発生する問題
レジスタ割り当ては、さまざまなレジスタ割り当てアプローチによって対処 (または回避) できるいくつかの問題を引き起こします。最も一般的な問題のうち 3 つを次に示します。
- エイリアシング
- 一部のアーキテクチャでは、1つのレジスタに値を割り当てると、別のレジスタの値に影響を与えることがあります。これをエイリアシングと呼びます。たとえば、x86アーキテクチャには、16ビットまたは8ビットレジスタとしても使用できる4つの汎用32ビットレジスタがあります。[11]この場合、eaxレジスタに32ビット値を割り当てると、alレジスタの値に影響します。
- 着色前
- この問題は、いくつかの変数を特定のレジスタに割り当てることを強制する行為である。例えば、PowerPCの 呼び出し規約では、パラメータは一般的にR3-R10で渡され、戻り値はR3で渡される。[12]
- NP問題
- チャイティンらは、レジスタ割り当てがNP完全問題であることを示した。彼らは、任意のグラフに対して、レジスタ割り当て（ノードを表すレジスタと利用可能な色を表すマシンレジスタ）が元のグラフの色付けとなるようなプログラムを構築できることを示し、グラフの色付け問題をレジスタ割り当て問題に還元した。グラフの色付けはNP困難問題であり、レジスタ割り当てはNPであるため、これは問題のNP完全性を証明している。[13]
レジスタ割り当てテクニック
レジスタ割り当ては、コードの基本ブロックに対して行われることがあります。これは「ローカル」であると言われ、Horwitz らによって初めて言及されました。[14]基本ブロックには分岐が含まれていないため、レジスタ割り当てにおける制御フロー グラフのマージ ポイントの管理は時間のかかる操作であるため、割り当てプロセスは高速であると考えられます。[ 15 ]ただし、このアプローチは、コンパイル単位全体 (たとえば、メソッドまたはプロシージャ) に対して動作する「グローバル」アプローチほど最適化されたコードを生成しないと考えられています。[16]
グラフの色分け割り当て
グラフカラーリング割り当ては、レジスタ割り当てを解決するための一般的なアプローチです。[17] [18]これは、Chaitin らによって最初に提案されました。[4] このアプローチでは、グラフ内のノードは、レジスタ割り当ての候補となるライブ範囲 (変数、一時変数、仮想/シンボリックレジスタ) を表します。エッジは、干渉するライブ範囲、つまり少なくとも 1 つのプログラムポイントで同時にライブであるライブ範囲を接続します。レジスタ割り当ては、エッジで接続された 2 つのノードが同じ色を受け取らないように、色 (レジスタ) がノードに割り当てられるグラフカラーリング問題に帰着します。 [19]
活性解析を使用すると、干渉グラフを構築することができます。干渉グラフは、ノードがプログラムの変数である無向グラフであり、どの変数が同じレジスタに割り当てることができないかをモデル化するために使用されます。[20]
原理
チャイティンスタイルのグラフカラーリングレジスタアロケータの主なフェーズは以下のとおりです。[18]
- 再番号付け: ソース プログラム内のライブ範囲情報を検出します。
- ビルド: 干渉グラフを構築します。
- 結合: コピー命令によって関連付けられた非干渉変数の有効範囲を結合します。
- スピル コスト: 各変数のスピル コストを計算します。これにより、変数をメモリにマッピングすることが最終プログラムの速度に与える影響を評価します。
- 簡素化: 推論グラフ内のノードの順序を構築する
- スピル コード: レジスタとメモリ間で値を交換するためのスピル命令、つまりロードとストアを挿入します。
- 選択: 各変数にレジスタを割り当てます。
欠点とさらなる改善
グラフカラーリング割り当てには、3 つの大きな欠点があります。まず、どの変数をスピルするかを決定するために、NP 完全問題であるグラフカラーリングに依存しています。最小のカラーリンググラフを見つけることは、確かに NP 完全問題です。 [21] 2 番目に、ライブ範囲分割を使用しない限り、追い出された変数はどこにでもスピルされます。ストア命令はできるだけ早く、つまり変数定義の直後に挿入され、ロード命令はそれぞれ遅く、変数の使用直前に挿入されます。3 番目に、スピルされない変数は、その存続期間全体にわたって同じレジスタに保持されます。[22]
一方、単一のレジスタ名が複数のレジスタクラスに現れることがある。ここで、クラスとは、特定の役割において互換性のあるレジスタ名の集合である。そして、複数のレジスタ名が単一のハードウェアレジスタの別名である可能性がある。[23] 最後に、グラフカラーリングはレジスタを割り当てるための積極的な手法であるが、干渉グラフを使用するため計算コストが高く、最悪の場合、ライブ範囲の数の2乗のサイズになることがある。 [24] グラフカラーリングレジスタ割り当ての従来の定式化では、重複しない汎用レジスタの単一のバンクが暗黙的に想定されており、重複するレジスタペア、特殊用途レジスタ、複数のレジスタバンクなどの不規則なアーキテクチャの特徴は処理されない。[25]
チャイティンスタイルのグラフカラーリングアプローチのその後の改良は、ブリッグスらによって発見されました。それは保守的合体と呼ばれています。この改良は、2つのライブ範囲をいつマージできるかを決定する基準を追加します。主に、非干渉要件に加えて、2つの変数は、マージしてもそれ以上の流出が発生しない場合にのみ合体できます。ブリッグスらは、チャイティンの研究に2番目の改良であるバイアスカラーリングを導入しました。バイアスカラーリングは、グラフカラーリングでコピーに関連するライブ範囲に同じ色を割り当てようとします。[18]
リニアスキャン
線形スキャンは、もう 1 つのグローバル レジスタ割り当てアプローチです。これは、1999 年に Poletto らによって初めて提案されました。[26]このアプローチでは、コードはグラフに変換されません。代わりに、すべての変数が線形スキャンされ、間隔として表される有効範囲が決定されます。すべての変数の有効範囲が判明したら、間隔を時系列で走査します。この走査は、有効範囲が干渉する変数を識別するのに役立ちますが、干渉グラフは構築されず、変数は貪欲な方法で割り当てられます。[24]
このアプローチの目的は速度です。生成されたコードの実行時間ではなく、コード生成に費やされた時間の観点からの速度です。通常、標準的なグラフカラーリングのアプローチは高品質のコードを生成しますが、かなりのオーバーヘッドがあり、[27] [28] 、使用されるグラフカラーリングアルゴリズムは2次コストを持ちます。[29]この特徴により、線形スキャンは現在、Hotspotクライアントコンパイラ、V8、Jikes RVM、[5] Android Runtime（ART）などのいくつかのJITコンパイラで使用されているアプローチです。[30] Hotspotサーバーコンパイラは、その優れたコードのためにグラフカラーリングを使用しています。[31]
擬似コード
これはPolettoら[32]によって最初に提案されたアルゴリズムを説明しています。
- R は使用可能なレジスタの数です。
- active は、現在のポイントと重複し、レジスタに配置されているライブ インターバルを、終了ポイントの昇順に並べ替えたリストです。
リニアスキャンレジスタ割り当て
アクティブ ← {}
各ライブインターバルiについて、開始点の増加順に
期限切れ間隔(i)
長さ(アクティブ) = Rの場合
スピル間隔(i)
それ以外
register[i] ← 空きレジスタのプールから削除されたレジスタアクティブにi を
追加し、エンドポイントの増加順に並べ替えます
ExpireOldIntervals(i) は、アクティブ
な各間隔j に対して、エンドポイントの増加順に実行され、 endpoint[j] ≥ startpoint[i]の場合は、戻り、j をアクティブから
削除します。
レジスタ[j]を空きレジスタのプールに追加する
スピル間隔(i)
spill ← アクティブの最後の間隔
エンドポイント[spill] > エンドポイント[i]の場合
レジスタ[i] ← レジスタ[spill]
location[spill] ← 新しいスタックの場所
アクティブから流出を取り除くi をアクティブに
追加し、終了点の昇順でソートします。
location[i] ← 新しいスタック位置
欠点とさらなる改善
しかし、線形スキャンには2つの大きな欠点があります。まず、貪欲な側面のため、ライフタイムホール、つまり「変数の値が不要な範囲」が考慮されません。[33] [34]さらに、流出した変数は、そのライフタイム全体にわたって流出したままになります。
ポレットの線形スキャンアルゴリズムを踏襲した研究は他にも数多くある。例えば、トラウブらは、より高品質のコードを生成することを目的としたセカンドチャンスビンパッキングと呼ばれるアルゴリズムを提案した。[35] [36]このアプローチでは、標準の線形スキャンアルゴリズムで使用されるものとは異なるヒューリスティックを使用して、スピルされた変数を後でレジスタに格納する機会が与えられる。このアルゴリズムは、ライブ間隔を使用する代わりにライブ範囲に依存しており、つまり、ある範囲をスピルする必要がある場合、この変数に対応する他のすべての範囲をスピルする必要はない。
線形スキャン割り当てもSSA形式の利点を生かすように適応されました。この中間表現の特性により割り当てアルゴリズムが簡素化され、ライフタイムホールを直接計算できるようになりました。[37]まず、ライフタイム間隔の構築を目的としたデータフローグラフ分析にかかる時間が短縮されます。これは変数が一意であるためです。[38]その結果、新しい割り当てごとに新しいライブ間隔が対応するため、ライブ間隔が短くなります。[39] [40]間隔とライブネスホールのモデリングを回避するために、ロジャーズはフューチャーアクティブセットと呼ばれる簡略化を示し、命令の80%の間隔を削除することに成功しました。[41]
再物質化
合体
レジスタ割り当ての文脈では、合体とは、2つの変数を同じ場所に割り当てることによって、変数間の移動操作をマージする行為です。合体操作は干渉グラフが構築された後に行われます。2つのノードが合体されると、コピー操作が不要になると、それらは同じ色になり、同じレジスタに割り当てられる必要があります。[42]
合体を行うと、干渉グラフの色付け可能性にプラスの影響とマイナスの影響の両方が及ぶ可能性がある。[9]たとえば、合体がグラフの推論の色付け可能性に与えるマイナスの影響の 1 つは、2 つのノードが合体される場合で、結果のノードには合体されるノードのエッジが結合されることになる。[9] 合体が推論グラフの色付け可能性に与えるプラスの影響としては、たとえば、あるノードが合体される両方のノードに干渉する場合、ノードの次数が 1 つ減少し、干渉グラフの全体的な色付け可能性が向上することがあげられる。[43]
いくつかの合体ヒューリスティックが利用可能である：[44]
- 積極的な合体
- これは、Chaitinのオリジナルレジスタアロケータによって初めて導入されました。このヒューリスティックは、干渉しないコピー関連ノードを統合することを目的としています。 [45]コピー除去の観点から、このヒューリスティックは最良の結果をもたらします。[46]一方、積極的な統合は推論グラフの色付けに影響を与える可能性があります。[43]
- 保守派の融合
- 主に積極的合体と同じヒューリスティックを使用するが、干渉グラフの色付けを損なわない場合にのみ、動きをマージする。[47]
- 反復合体
- グラフの色彩可能性を維持しながら、一度に1つの特定の動きを削除します。[48]
- 楽観的な融合
- これは積極的な合体に基づいていますが、推論グラフの色付けが損なわれた場合、可能な限り少ない動きを放棄します。[49]
混合アプローチ
ハイブリッド割り当て
他のレジスタ割り当てアプローチの中には、レジスタの使用を最適化するために 1 つの手法だけに限定しないものもあります。たとえば、Cavazos らは、線形スキャン アルゴリズムとグラフ カラーリング アルゴリズムの両方を使用できるソリューションを提案しました。[50]このアプローチでは、どちらかのソリューションの選択が動的に決定されます。まず、機械学習アルゴリズムが「オフライン」で、つまり実行時ではなく使用されて、どの割り当てアルゴリズムを使用する必要があるかを決定するヒューリスティック関数が構築されます。次に、ヒューリスティック関数が実行時に使用され、コードの動作を考慮して、アロケータは 2 つの利用可能なアルゴリズムのいずれかを選択できます。[51]
トレースレジスタ割り当ては、Eisl らによって開発された最近のアプローチです。[3] [5]この技術は割り当てをローカルで処理します。動的プロファイリングデータを使用して、特定の制御フローグラフで最も頻繁に使用される分岐を決定します。次に、最も頻繁に使用される分岐を優先してマージポイントを無視した「トレース」（コードセグメント）のセットを推測します。各トレースは、アロケータによって個別に処理されます。このアプローチは、異なるトレース間で異なるレジスタ割り当てアルゴリズムを使用できるため、ハイブリッドと見なすことができます。[52]
分割割り当て
分割割り当ては、通常反対と見なされる異なるアプローチを組み合わせた別のレジスタ割り当て手法です。たとえば、ハイブリッド割り当て手法は、最初のヒューリスティック構築段階がオフラインで実行され、ヒューリスティックの使用がオンラインで実行されるため、分割されていると見なすことができます。[24]同様に、B. Diouf らは、オフラインとオンラインの両方の動作、つまり静的コンパイルと動的コンパイルに依存する割り当て手法を提案しました。[53] [54]オフライン段階では、最初に整数線形計画法を使用して最適なスピルセットが収集されます。次に、以前に特定された最適なスピルセットに依存するアルゴリズムを使用して、ライブ範囲に注釈が付けられますcompressAnnotation。レジスタ割り当ては、オフラインフェーズで収集されたデータに基づいて、オンライン段階で実行されます。[55]
2007年に、Bouchezらはレジスタ割り当てを複数のステージに分割し、1つのステージをスピル専用にし、もう1つのステージをカラーリングと合体専用にすることを提案しました。[56]
さまざまな技術の比較
レジスタ割り当て手法の性能を他の手法と比較するために、いくつかの指標が使用されてきました。レジスタ割り当てでは通常、コード品質（つまり、実行速度の速いコード）と分析オーバーヘッド（つまり、ソースコードを分析して最適化されたレジスタ割り当てのコードを生成するのにかかる時間）の間のトレードオフに対処する必要があります。この観点から、生成されたコードの実行時間と活性分析に費やされた時間は、さまざまな手法を比較するための適切な指標です。[57]
関連するメトリクスが選択されると、そのメトリクスが適用されるコードは、実際のアプリケーションの動作を反映するか、アルゴリズムが解決したい特定の問題に関連しているなど、利用可能で問題に関連したものでなければなりません。レジスタ割り当てに関する最近の記事では、特にDacapoベンチマークスイートが使用されています。[58]
参照
- シュトララー数、式ツリーを評価するために必要なレジスタの最小数。[59]
- レジスタ (キーワード) は、C および C++ でレジスタに配置する変数のヒントです。
- Sethi-Ullman アルゴリズム。式の評価に必要なレジスタの数が使用可能なレジスタの数を超える場合に、単一の式を評価するための最も効率的なレジスタ割り当てを生成するアルゴリズムです。
参考文献
- ^ ディッツェル＆マクレラン、1982年、p. 48.
- ^ ルネソンとニストローム、2003、p. 242.
- ^ ab アイスルら。 2016、p. 14:1。
- ^ ab Chaitin et al. 1981 年、p. 47.
- ^ abc Eisl et al. 2016、p.1。
- ^ 「コンピュータ/ネットワークのレイテンシ比較数値」。blog.morizyun.com。2018年1月6日。 2019年1月8日閲覧。
- ^ ブラウン＆ハック 2009、174ページ。
- ^ コーズ & ゴールドスタイン 2009、p. 21.
- ^ abcd Bouchez、Darte & Rastello 2007b、p. 103.
- ^ Colombet、Brandner & Darte 2011、p. 26.
- ^ 「Intel® 64 および IA-32 アーキテクチャー ソフトウェア開発者マニュアル、セクション 3.4.1」(PDF)。Intel。2019 年 5 月。2019 年 5 月 25 日のオリジナル(PDF)からアーカイブ。
- ^ 「32 ビット PowerPC 関数呼び出し規約」。
- ^ ブシェス、ダルテ、ラステッロ、2006 年、p. 4.
- ^ Horwitz et al. 1966, p.43.
- ^ Farach & Liberatore 1998、p. 566.
- ^ Eisl et al. 2017、92ページ。
- ^ アイスル、レオポルゼダー、メッセンベック、2018、p. 1.
- ^ abc ブリッグス、クーパー＆トルゾン 1992、316ページ。
- ^ ポレットとサーカール 1999、p. 896。
- ^ ルネソンとニストローム、2003、p. 241.
- ^ 1975年、618-619ページ。
- ^ Colombet、Brandner & Darte 2011、p. 1.
- ^ スミス、ラムゼイ、ホロウェイ2004年、277ページ。
- ^ abc カバゾス、モス & オボイル 2006、p. 124.
- ^ ルネソンとニストローム、2003、p. 240。
- ^ ポレットとサーカール 1999、p. 895。
- ^ ポレットとサーカール 1999、p. 902。
- ^ ウィマー＆モッセンボック 2005年、132ページ。
- ^ ヨハンソン＆サゴナス、2002、p. 102.
- ^ The Evolution of ART - Google I/O 2016。Google 。 2016年5月25日。イベントは3分47秒に発生します。
- ^ Paleczny、Vick & Click 2001、p.1。
- ^ ポレットとサーカール 1999、p. 899。
- ^ Eisl et al. 2016、p.2。
- ^ トラウブ、ホロウェイ、スミス 1998、143ページ。
- ^ トラウブ、ホロウェイ、スミス 1998、141ページ。
- ^ ポレットとサーカール 1999、p. 897。
- ^ ウィマー＆フランツ2010、170ページ。
- ^ Mössenböck & Pfeiffer 2002、234ページ。
- ^ Mössenböck & Pfeiffer 2002、233ページ。
- ^ Mössenböck & Pfeiffer 2002、229ページ。
- ^ ロジャース 2020.
- ^ チャイティン1982、90ページ。
- ^ ab Ahn & Paek 2009、p.7を参照。
- ^ パーク＆ムーン 2004年、736ページ。
- ^ チャイティン1982、99ページ。
- ^ パーク＆ムーン 2004年、738ページ。
- ^ ブリッグス、クーパー、トルゾン 1994、433 ページ。
- ^ ジョージ&アペル、1996年、p. 212.
- ^ パーク＆ムーン 2004年、741ページ。
- ^ Eisl et al. 2017、p.11。
- ^ カバゾス、モス、オボイル、2006、p. 124-127。
- ^ Eisl et al. 2016、p.4。
- ^ ディウフ他2010年66頁。
- ^ コーエン＆ロホウ 2010、p.1。
- ^ ディウフ他2010年72頁。
- ^ ブシェス、ダルテ、ラステッロ、2007a、p. 1.
- ^ ポレットとサーカール 1999、p. 901-910。
- ^ ブラックバーン他2006年、169頁。
- ^ フラジョレ、ラウール、ヴイユマン 1979.
出典
- Ahn, Minwook; Paek, Yunheung (2009). 「コピーシフトによる異種レジスタアーキテクチャのレジスタ統合技術」. ACM Transactions on Embedded Computing Systems . 8 (2): 1–37. CiteSeerX 10.1.1.615.5767 . doi :10.1145/1457255.1457263. ISSN 1539-9087. S2CID 14143277.
- Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D. (2006)。コンパイラ：原理、テクニック、ツール（第 2 版）。Addison-Wesley Longman Publishing Co., Inc. ISBN 978-0321486813。
- Appel, Andrew W.; George, Lal ( 2001)。「レジスタが少ない CISC マシンの最適スピル」。プログラミング言語の設計と実装に関する ACM SIGPLAN 2001 会議の議事録 - PLDI '01 。pp . 243–253。CiteSeerX 10.1.1.37.8978。doi :10.1145 / 378795.378854。ISBN 978-1581134148. S2CID 1380545。
- Barik, Rajkishore; Grothoff, Christian; Gupta, Rahul; Pandit, Vinayaka; Udupa, Raghavendra (2007)。「整数線形計画法を用いた最適なビット単位のレジスタ割り当て」。並列コンピューティングのための言語とコンパイラ。コンピュータサイエンスの講義ノート。第 4382 巻。pp. 267–282。CiteSeerX 10.1.1.75.6911。doi : 10.1007 /978-3-540-72521-3_20。ISBN 978-3-540-72520-6。
- Bergner, Peter; Dahl, Peter; Engebretsen, David; O'Keefe, Matthew (1997)。「干渉領域スピルによるスピルコードの最小化」。プログラミング言語の設計と実装に関する ACM SIGPLAN 1997 会議の議事録 - PLDI '97。pp. 287–295。doi : 10.1145 /258915.258941。ISBN 978-0897919074. S2CID 16952747。
- Blackburn, Stephen M.; Guyer, Samuel Z.; Hirzel, Martin; Hosking, Antony; Jump, Maria; Lee, Han; Eliot, J.; Moss, B.; Phansalkar, Aashish; Stefanović, Darko; VanDrunen, Thomas; Garner, Robin; von Dincklage, Daniel; Wiedermann, Ben; Hoffmann, Chris; Khang, Asjad M.; McKinley, Kathryn S.; Bentzur, Rotem; Diwan, Amer; Feinberg, Daniel; Frampton, Daniel (2006)。「DaCapo ベンチマーク」。第 21 回 ACM SIGPLAN オブジェクト指向プログラミング システム、言語、およびアプリケーションに関する年次会議 - OOPSLA '06 の議事録。p . 169。doi :10.1145/1167473.1167488。hdl :1885/33723. ISBN 978-1595933485. S2CID 9255051。
- Book、Ronald V. (1975 年 12 月)。「Karp Richard M.. 組み合わせ問題における縮約可能性。コンピュータ計算の複雑さ、コンピュータ計算の複雑さに関するシンポジウムの議事録、1972 年 3 月 20 ～ 22 日、IBM Thomas J. Watson Center、ヨークタウン ハイツ、ニューヨークで開催、Miller Raymond E. および Thatcher James W. 編、Plenum Press、ニューヨークおよびロンドン、1972 年、pp. 85 ～ 103」。The Journal of Symbolic Logic。40 ( 4): 618 ～ 619。doi : 10.2307 /2271828。ISSN 0022-4812。JSTOR 2271828 。
- Bouchez, Florent; Darte, Alain; Rastello, Fabrice (2006)。「レジスタ割り当て: Chaitin らの NP 完全性証明は実際に何を証明しているのか? またはレジスタ割り当ての再考: 理由と方法」。レジスタ割り当て: Chaitin らの NP 完全性証明は実際に何を証明しているのか? 。コンピュータ サイエンスの講義ノート。第 4382 巻。pp. 2–14。doi : 10.1007 /978-3-540-72521-3_21。ISBN 978-3-540-72520-6。
- Bouchez, Florent; Darte, Alain; Rastello, Fabrice ( 2007a) .「レジスタ結合の複雑さについて」。コード生成と最適化に関する国際シンポジウム (CGO'07)。pp. 102–114。CiteSeerX 10.1.1.101.6801。doi :10.1109/CGO.2007.26。ISBN 978-0-7695-2764-2. S2CID 7683867。
- ブシェズ、フローラント。ダルテ、アラン。ラステッロ、ファブリス (2007b)。 「SSA形式に基づくあらゆる場所での流出の複雑さについて」。ACM SIGPLAN の通知。42 (7): 103–114。arXiv : 0710.3642。土井：10.1145/1273444.1254782。ISSN 0362-1340。
- Braun, Matthias; Hack, Sebastian (2009)。「SSA 形式プログラムのレジスタ スピルとライブ範囲分割」。コンパイラ構築。コンピュータ サイエンスの講義ノート。第 5501 巻。pp. 174–189。CiteSeerX 10.1.1.219.5318。doi : 10.1007 / 978-3-642-00722-4_13。ISBN 978-3-642-00721-7. ISSN 0302-9743.
- Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1992). 「再物質化」. ACM SIGPLAN Notices . 27 (7): 311–321. doi :10.1145/143103.143143. ISSN 0362-1340.
- Briggs, Preston; Cooper, Keith D.; Torczon, Linda (1994). 「グラフカラーリングレジスタ割り当ての改善」. ACM Transactions on Programming Languages and Systems . 16 (3): 428–455. CiteSeerX 10.1.1.23.253 . doi :10.1145/177492.177575. ISSN 0164-0925. S2CID 6571479.
- Cavazos, John; Moss, J. Eliot B.; O'Boyle, Michael FP (2006)。「ハイブリッド最適化: どの最適化アルゴリズムを使用するか?」コンパイラ構築。コンピュータサイエンスの講義ノート。第 3923 巻。pp. 124–138。doi : 10.1007/ 11688839_12。ISBN 978-3-540-33050-9. ISSN 0302-9743.
- Chaitin, Gregory J.; Auslander, Marc A.; Chandra, Ashok K.; Cocke, John; Hopkins, Martin E.; Markstein, Peter W. (1981). 「カラーリングによるレジスタ割り当て」.コンピュータ言語. 6 (1): 47–57. doi :10.1016/0096-0551(81)90048-5. ISSN 0096-0551.
- Chaitin, GJ (1982)。「グラフカラーリングによるレジスタ割り当てとスピル」。1982年 SIGPLAN シンポジウム「コンパイラ構築」の議事録 - SIGPLAN '82 。pp . 98–101。doi : 10.1145 /800230.806984。ISBN 978-0897910743.S2CID 16872867 。
- Chen, Wei-Yu; Lueh, Guei-Yuan; Ashar, Pratik; Chen, Kaiyu; Cheng, Buqi (2018)。「Intel プロセッサ グラフィックスのレジスタ割り当て」。2018年国際コード生成および最適化シンポジウムの議事録 - CGO 2018。pp. 352–364。doi : 10.1145 /3168806。ISBN 9781450356176. S2CID 3367270。
- Cohen, Albert; Rohou, Erven ( 2010)。「異種マルチコア組み込みシステム向けのプロセッサ仮想化と分割コンパイル」。第47 回 DAC 設計自動化会議議事録。p . 102。CiteSeerX 10.1.1.470.9701。doi : 10.1145 / 1837274.1837303。ISBN 9781450300025. S2CID 14314078。
- Colombet, Quentin; Brandner, Florian; Darte, Alain (2011)。「SSA の観点から見た最適スピルの研究」。組み込みシステム向けコンパイラ、アーキテクチャ、合成に関する第 14 回国際会議議事録 - CASES '11 。p . 25。doi :10.1145/2038698.2038706。ISBN 9781450307130. S2CID 8296742。
- Diouf, Boubacar、Cohen, Albert、Rastello, Fabrice、Cavazos, John (2010)。「分割レジスタ割り当て: パフォーマンス ペナルティのない線形複雑性」。高性能組み込みアーキテクチャとコンパイラ。コンピュータ サイエンスの講義ノート。第 5952 巻。66 ～ 80 ページ。CiteSeerX 10.1.1.229.3988。doi : 10.1007 / 978-3-642-11515-8_7。ISBN 978-3-642-11514-1. ISSN 0302-9743.
- Ditzel, David R.; McLellan , HR (1982)。「レジスタ割り当ての自由化」。プログラミング言語とオペレーティングシステムのアーキテクチャサポートに関する第 1 回国際シンポジウムの議事録 - ASPLOS-I。pp . 48–56。doi :10.1145/ 800050.801825。ISBN 978-0897910668. S2CID 2812379。
- Eisl, Josef; Grimmer, Matthias; Simon, Doug; Würthinger, Thomas; Mössenböck, Hanspeter (2016)。「JIT コンパイラにおけるトレースベースのレジスタ割り当て」。第 13 回 Java プラットフォームでのプログラミングの原則と実践に関する国際会議の議事録: 仮想マシン、言語、およびツール - PPPJ '16。pp. 1–11。doi :10.1145 / 2972206.2972211。ISBN 9781450341356. S2CID 31845919。
- Eisl, Josef; Marr, Stefan; Würthinger, Thomas; Mössenböck, Hanspeter (2017)。「トレース レジスタ割り当てポリシー」(PDF)。第 14 回国際マネージ言語およびランタイム会議の議事録 - Man Lang 2017。pp. 92–104。doi : 10.1145/ 3132190.3132209。ISBN 9781450353403. S2CID 1195601。
- Eisl, Josef; Leopoldseder, David; Mössenböck, Hanspeter (2018)。「並列トレース レジスタ割り当て」。第 15 回国際マネージ言語およびランタイム会議 - Man Lang '18 の議事録。pp. 1–7。doi : 10.1145/ 3237009.3237010。ISBN 9781450364249. S2CID 52137887。
- Koes, David Ryan、Goldstein, Seth Copen (2009)。「Register Allocation Deconstructed」。フランスのニースで執筆。組み込みシステム向けソフトウェアおよびコンパイラに関する第 12 回国際ワークショップの議事録。SCOPES '09。米国ニューヨーク州ニューヨーク: ACM。pp. 21–30。ISBN 978-1-60558-696-0。
- Farach, Martin; Liberatore, Vincenzo (1998)。「ローカル レジスタ割り当てについて」。米国カリフォルニア州サンフランシスコで執筆。第9 回 ACM-SIAM 離散アルゴリズム シンポジウムの議事録。SODA '98。米国ペンシルバニア州フィラデルフィア: Society for Industrial and Applied Mathematics。pp. 564–573。ISBN 0-89871-410-9。
- Flajolet, P. ; Raoult, JC; Vuillemin, J. (1979)、「算術式の評価に必要なレジスタの数」、理論計算機科学、9 (1): 99–125、doi : 10.1016/0304-3975(79)90009-4
- George, Lal; Appel, Andrew W. (1996). 「反復レジスタ合体」。ACM Transactions on Programming Languages and Systems . 18 (3): 300–324. doi : 10.1145/229542.229546 . ISSN 0164-0925. S2CID 12281734.
- Horwitz, LP; Karp, RM; Miller, RE; Winograd, S. (1966). 「インデックスレジスタ割り当て」. Journal of the ACM . 13 (1): 43–61. doi : 10.1145/321312.321317 . ISSN 0004-5411. S2CID 14560597.
- Johansson, Erik; Sagonas, Konstantinos (2002)。「高性能 Erlang コンパイラにおける線形スキャン レジスタ割り当て」。宣言型言語の実用的側面。コンピュータ サイエンスの講義ノート。第 2257 巻。pp. 101–119。doi : 10.1007/ 3-540-45587-6_8。ISBN 978-3-540-43092-6. ISSN 0302-9743.
- Kurdahi, FJ; Parker , AC (1987)。「REAL: レジスタ割り当てプログラム」。第 24 回 ACM/IEEE 会議議事録、設計自動化会議 - DAC '87。pp. 210–215。doi : 10.1145 /37888.37920。ISBN 978-0818607813. S2CID 17598675。
- Mössenböck, Hanspeter; Pfeiffer, Michael (2002)。「SSA 形式とレジスタ制約のコンテキストにおける線形スキャン レジスタ割り当て」。コンパイラ構築。コンピュータ サイエンスの講義ノート。第 2304 巻。pp. 229–246。doi : 10.1007/ 3-540-45937-5_17。ISBN 978-3-540-43369-9. ISSN 0302-9743.
- Nickerson, Brian R. (1990). 「マルチレジスタオペランドを持つプロセッサのグラフカラーリングレジスタ割り当て」ACM SIGPLAN Notices . 25 (6): 40–52. doi :10.1145/93548.93552. ISSN 0362-1340.
- Paleczny, Michael; Vick, Christopher ; Click, Cliff (2001)。「Java HotSpot Server コンパイラ」。Java仮想マシン研究技術シンポジウム (JVM01) の議事録。米国カリフォルニア州モントレー。pp. 1–12。CiteSeerX 10.1.1.106.1919 。
- Park, Jinpyo; Moon, Soo-Mook (2004). 「楽観的レジスタ合体」. ACM Transactions on Programming Languages and Systems . 26 (4): 735–765. CiteSeerX 10.1.1.33.9438 . doi :10.1145/1011508.1011512. ISSN 0164-0925. S2CID 15969885.
- Poletto, Massimiliano; Sarkar, Vivek (1999). 「線形スキャンレジスタ割り当て」. ACM Transactions on Programming Languages and Systems . 21 (5): 895–913. CiteSeerX 10.1.1.27.2462 . doi :10.1145/330249.330250. ISSN 0164-0925. S2CID 18180752.
- Rogers, Ian (2020). 「効率的なグローバルレジスタ割り当て」. arXiv : 2011.05608 [cs.PL].
- Runeson, Johan; Nyström, Sven-Olof (2003)。「不規則なアーキテクチャのための再ターゲット可能なグラフカラーリングレジスタ割り当て」。組み込みシステム用ソフトウェアとコンパイラ。コンピュータサイエンスの講義ノート。第 2826 巻。pp. 240–254。CiteSeerX 10.1.1.6.6186。doi : 10.1007 / 978-3-540-39920-9_17。ISBN 978-3-540-20145-8. ISSN 0302-9743.
- Smith, Michael D.; Ramsey, Norman; Holloway, Glenn (2004). 「グラフカラーリングレジスタ割り当ての一般化アルゴリズム」. ACM SIGPLAN Notices . 39 (6): 277. CiteSeerX 10.1.1.71.9532 . doi :10.1145/996893.996875. ISSN 0362-1340.
- Traub, Omri; Holloway, Glenn; Smith, Michael D. (1998). 「リニアスキャンレジスタ割り当ての品質と速度」ACM SIGPLAN Notices . 33 (5): 142–151. CiteSeerX 10.1.1.52.8730 . doi :10.1145/277652.277714. ISSN 0362-1340.
- Wimmer , Christian; Mössenböck , Hanspeter (2005)。「線形スキャン レジスタ アロケータにおける最適化された区間分割」。仮想実行環境に関する第 1 回 ACM/USENIX 国際会議議事録 - VEE '05。p. 132。CiteSeerX 10.1.1.394.4054。doi :10.1145/1064979.1064998。ISBN 978-1595930477. S2CID 494490。
- Wimmer , Christian; Franz, Michael (2010)。「SSA 形式の線形スキャン レジスタ割り当て」。第 8 回 IEEE/ACM 国際コード生成および最適化シンポジウム議事録 - CGO '10。p. 170。CiteSeerX 10.1.1.162.2590。doi : 10.1145 / 1772954.1772979。ISBN 9781605586359. S2CID 1820765。
外部リンク
- 整数計画法のチュートリアル
- 会議 整数計画法と組み合わせ最適化、IPCO
- オーソワ組み合わせ最適化ワークショップ
- Bosscher, Steven、Novillo, Diego。GCC に新しいオプティマイザー フレームワークが導入されました。GCC の SSA の使用と、それが古い IR と比べてどのように改善されているかについての記事。
- SSA 書誌。SSA 研究論文の広範なカタログ。
- Zadeck、F. Kenneth。「静的単一割り当てフォームの開発」、2007 年 12 月の SSA の起源に関する講演。
- VV.AA. 「SSA ベースのコンパイラ設計」(2014)
- CiteSeerからの引用
- Agner Fogによる最適化マニュアル- x86 プロセッサ アーキテクチャと低レベル コードの最適化に関するドキュメント