このページの目次
レジスタ割り当て
コンパイル最適化においてNP困難さが最も顕著に現れる難関: 無限の仮想レジスタを有限の物理レジスタにマッピングし、収まらない場合はスタックにスピルする。グラフ彩色（Chaitin/Briggs）と線形走査（Poletto/Sarkar）は2つの近似解であり、SSAの弦グラフの性質により彩色が容易になる。
概要
SSA形式および最適化フェーズでは無限の仮想レジスタが使用される——新しい値ごとに独立した %v1、%v2 が割り当てられる。実際のターゲットマシンには物理レジスタが少数しか存在せず（x86-64 では汎用レジスタが16個、ARM64 では31個）、さらに呼び出し規約（calling convention）の制約も受ける。レジスタ割り当てとは、仮想レジスタを物理レジスタにマッピングする処理であり、マッピングしきれない場合はスピル（spill）してスタックに退避させる。これはコンパイル最適化の中で最もNP困難さが際立つ部分——最適レジスタ割り当てはNP完全（グラフ彩色）であるため、実際には近似アルゴリズムが用いられる。
前提: ライブネス解析
データフロー解析におけるライブネス（liveness）情報は、レジスタ割り当ての入力として直接利用される:
仮想レジスタ v1 と v2 について:
あるプログラムポイントで v1 と v2 が同時にライブ（live）である場合
→ v1 と v2 は同じ物理レジスタを共有できない
→ 干渉グラフ（interference graph）において v1 と v2 の間に辺が存在する
ライブレンジ（live range）の構築: 各定義点から出発し、SSAの def-use チェーンをたどってすべての使用点に至るまでの「区間」が、その仮想レジスタのライブレンジとなる。phi ノードによるマージがある場合は、phi の入力元と出力先のライブレンジを接続する。
グラフ彩色による割り当て（Chaitin/Briggs）
干渉グラフの構築
ノード = 仮想レジスタ; 辺 = 任意のポイントで2つの仮想レジスタが同時にライブである場合:
v1 は BB1 で定義され、BB3 で最後に使用される
v2 は BB2 で定義され、BB3 で最後に使用される
BB3 のエントリポイントで v1 と v2 がともにライブ → v1 — v2 の辺が存在する
彩色 = 各ノードに色（物理レジスタ）を割り当て、隣接するノードは異なる色にする
アルゴリズム（Chaitin スタイル）:
グラフにノードが残っている間:
次数 degree(n) < K （K = 利用可能な物理レジスタ数）であるノード n が存在する場合:
グラフから n を削除し、n をスタックにプッシュ ← n は必ず彩色可能（隣接ノード数 < K）
それ以外の場合:
スピルコストが最小のノード s を選択
s をスピル対象としてマークし、グラフから削除 ← これを犠牲にしてスタックに退避
spill_code(s) を呼び出す: s の値をスタックへ移動するための store/load を生成
スタックから順にポップし、各ノードに色を割り当てる（既に彩色された隣接ノードと衝突しないように）
Briggs の改善点: degree < K のノードをすぐに彩色可能と判定するのではなく、まず楽観的にそれらを削除し、ポップ段階で彩色不可能なノードが見つかった場合にのみスピルを行う。Briggs の楽観的彩色は、実際には Chaitin の悲観的アルゴリズムよりも大幅に少ないスピルを生成する（Chaitin は次数≥K のノードを積極的にスピルしており、彩色可能だったノードの多くもスピルされていた）。
スピルコードの生成
レジスタが不足した場合、ある仮想レジスタの値をスタックに「スピル」する:
スピル前: スピル後:
v1 = ... v1 = ...
... = v1 (use) spill [v1_slot] = v1 ← 定義直後にストア
v1_reload = load [v1_slot] ← 使用前にロード
... = v1_reload
ただし、スピルはライブレンジを変更する——元々 v1 は ... = v1 の箇所でのみ使用されていたが、スピルによりそのライブレンジは2つに分割される（v1 と v1_reload）。これにより干渉グラフがより疎になり、彩色の圧力が緩和される可能性がある。スピル後は干渉グラフを再構築して再割り当てを行う——これは反復的に行われる。
線形走査（Poletto/Sarkar）: より高速だがスピルが多い
線形走査は、単純化されたライブモデルを使用する——点単位の正確な干渉グラフではなく、ライブレンジの線形順序を用いる:
すべての仮想レジスタのライブレンジを開始位置でソート:
「現在ライブ」リストを維持
各レンジをスキャン:
expire_old_intervals() ← 終了したレンジを削除し、占有していた物理レジスタを解放
空きレジスタがある場合:
それを割り当てる
それ以外の場合:
現在ライブ中のうちスピルコストが最小のものを選択し、スピルする
空いたレジスタを新しいレンジに割り当てる
線形走査の計算量は O(n log n)（ソートによる）であり、グラフ彩色の O(n²) やそれ以上よりもはるかに高速である。その代償として、グラフ彩色よりも多くのスピルを生成する（干渉グラフを見ないため、干渉していない2つのレンジをスピルしてしまう可能性がある）。線形走査はJITコンパイルでよく使用される——コンパイル時間が最優先であり、数個のスピル増は許容される。
SSA がレジスタ割り当てに与える恩恵
SSA形式では、変数間の def-use 関係が自然に弦グラフ（chordal graph）構造を形成する——弦グラフの彩色は貪欲アルゴリズム（O(n)）により最適解を得ることができる。ただし注意すべき点として、実際のレジスタ割り当ては通常、SSAの解体（コピーの挿入）の後に実行される。phi ノードの解体に伴うコピーは弦グラフの性質を壊す可能性があるが、coalescing フェーズでこれらのコピーをできるだけマージするため、彩色は依然として効率的に行える。
Coalescing: コピーの除去
v1 = ...
v2 = v1 ← コピー: mov 命令が必要
... = v2
v1 と v2 に同じレジスタ r を割り当てられる場合:
r = ...
... = r ← コピーが除去される
coalescing にはコストが伴う——v1 と v2 を1つのノードにマージすると、その次数が増加し、彩色不可能になる可能性がある。そのため、coalescing は保守的に行われる——彩色後にスピルを導入しないコピーのみを coalesce する。Briggs の保守的 coalescing では、マージ後のノードの次数 < K（利用可能なレジスタ数）であることをチェックする。George の保守的 coalescing では、v1 のすべての隣接ノードが「すでに v2 と衝突していないか、または次数 < K」であることをチェックする。
呼び出し規約と割り当てアルゴリズムの相互影響
物理レジスタは、仮想レジスタの競合だけでなく、呼び出し規約（calling convention）の制約も受ける:
- 引数用レジスタ（x86-64:
rdi, rsi, rdx, rcx, r8, r9）: 関数呼び出しの最初の6つの引数は、これらのレジスタに配置しなければならない。 - 戻り値用レジスタ（
rax）: 関数の戻り値は rax に格納される。 - 呼び出し先保存（callee-saved、x86-64: rbx, rbp, r12–r15）: 呼び出された関数がこれらのレジスタを変更した場合、戻る前に復元しなければならない。スピル/復元は呼び出された側が行い、呼び出し側は介入しない。
- 呼び出し元保存（caller-saved、x86-64: rax, rcx, rdx, rsi, rdi, r8–r11）: 呼び出し側が call の前後でこれらのレジスタを使用する必要がある場合、自身でスピル/復元を行わなければならない。
レジスタ割り当てアルゴリズムはこれらの制約に従わなければならない:関数のプロローグ内で、割り当てプロセス中に使用された callee-saved 物理レジスタをスタックにスピルする。call 命令の前後では、caller-saved 物理レジスタ内の値が call 後も生存しているとは仮定できない。
参考文献
- Chaitin (1982): "Register Allocation and Spilling via Graph Coloring" — グラフ彩色による割り当ての原論文
- Poletto/Sarkar (1999): "Linear Scan Register Allocation" — 線形走査による割り当ての原論文
- LLVM:
lib/CodeGen/RegAllocGreedy.cpp（デフォルトの割り当てアルゴリズム）、lib/CodeGen/RegAllocBasic.cpp（ベースライン）— 産業用割り当てアルゴリズム。線形走査とグラフ彩色を組み合わせたハイブリッド方式