このページの目次
レジスタ割り当て
コンパイル最適化においてNP困難さが最も顕著に現れる難関: 無限の仮想レジスタを有限の物理レジスタにマッピングし、収まらない場合はスタックにスパイルする。グラフ彩色（Chaitin/Briggs）と線形走査（Poletto/Sarkar）は2つの近似解であり、SSAの弦グラフの性質により彩色が容易になる。
概要
SSA形式および最適化フェーズでは無限の仮想レジスタを使用する——新しい値ごとに独立した %v1、%v2 が割り当てられる。実際のターゲットマシンは物理レジスタが少数しかなく（x86-64 では汎用レジスタが16個、ARM64 では31個）、かつ呼び出し規約の制約を受ける。レジスタ割り当てとは、仮想レジスタを物理レジスタにマッピングするプロセスであり、マッピングしきれなかった場合はスパイル（spill）してスタックに退避させる。これはコンパイル最適化の中でNP困難さが最も顕著に現れる部分——最適レジスタ割り当てはNP完全（グラフ彩色）であるため、実際には近似アルゴリズムが用いられる。
前提: ライブネス解析
データフロー解析 のライブネス解析は、レジスタ割り当てへの入力を直接提供する:
2つの仮想レジスタ v1 と v2 について:
あるプログラムポイントで v1 と v2 が同時にライブ（活発）である場合
→ 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 の値をスタックにストア/ロードするコードを生成
スタックから順にポップし、各ノードに色を割り当てる（既に彩色された隣接ノードと衝突しないように）
Briggs の改善: degree < K のノードを即座に彩色可能と判定するのではなく、まず楽観的にそれらを削除し、ポップフェーズで彩色できないノードが見つかった場合にのみスパイルを行う。Briggs の楽観的彩色は、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²) またはそれ以上よりも大幅に高速である。その代償として、干渉グラフを参照しないため干渉していないレンジ同士をスパイルしてしまう可能性があり、グラフ彩色よりもスパイルが多くなる。線形走査はJITコンパイルでよく使用される——コンパイル時間が最優先であり、スパイルが数個増えることは許容される。
SSA がレジスタ割り当てに与える恩恵
SSA形式では、変数間の def-use 関係が自然に弦グラフ(chordal graph)構造を形成する——弦グラフの彩色は貪欲アルゴリズム（O(n)）で最適解を得ることができる。ただし注意すべきは、実際のレジスタ割り当ては通常、SSAの解体（コピーの挿入）の後に実行されるということである。φ解体によって導入されるコピーは弦グラフの性質を破壊する可能性があるが、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」であることをチェックする。
呼び出し規約と割り当てアルゴリズムの相互影響
物理レジスタは、仮想レジスタの競合だけでなく、呼び出し規約の制約も受ける:
- 引数レジスタ (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(ベースライン) — 産業用割り当てアルゴリズム。線形走査とグラフ彩色を組み合わせるハイブリッド方式