レジスタ割り当て（グラフ彩色）の仕組み

なぜレジスタ割り当てが要るのか

中間表現（AST/IRの設計）では変数は無限に作れます。x1, x2, t37 のような仮想レジスタ（virtual register）を必要なだけ使ってよい、というのがコンパイラ内部の前提です。ところがCPUの物理レジスタは有限で、汎用レジスタは x86-64 で16本、ARM64 で31本程度しかありません。レジスタアクセスは1サイクル、メモリアクセスはキャッシュに当たっても数サイクル、外れれば数百サイクルかかるため、どの変数を物理レジスタに載せ、どれをメモリへ追い出すかが実行速度を直接左右します。

レジスタ割り当てとは、この「無限の仮想レジスタ → 有限の物理レジスタ K 本」への写像を、できるだけメモリ退避を減らしつつ求める問題です。

生存区間と干渉グラフ

割り当ての土台は**生存解析（liveness analysis）です。ある変数は「定義された時点」から「最後に使われる時点」までの間だけ値を保持する必要があり、この区間を生存区間（live range）**と呼びます。

二つの変数の生存区間が同じ時点で重なるとき、両者は同じ物理レジスタに置けません。値を取り違えるからです。この関係を**干渉（interference）**と呼びます。

a = ...        // a 生存開始
b = ...        // b 生存開始（a もまだ生存 → a と b は干渉）
use(a)         // a 生存終了
c = ...        // c 生存開始（b は生存中だが a は終了 → c は a とは干渉しない）
use(b); use(c)

各変数を節点、干渉する組を辺とするグラフを**干渉グラフ（interference graph）**といいます。上の例では a-b と b-c に辺があり、a-c には辺がありません。重要なのは、辺で結ばれない節点同士は同じレジスタを共有できるという点です（a と c は同色にできる）。

グラフ彩色問題への帰着

ここで物理レジスタを「色」、レジスタが K 本あることを「K 色使える」と読み替えます。すると割り当ては次の制約問題になります。

干渉グラフの各節点に色を塗る。ただし辺で結ばれた節点は異なる色にする。使う色は K 色以内。

これはまさにグラフ理論のK彩色問題そのものです。彩色が成功すれば、同じ色の変数群を同じ物理レジスタへまとめて割り当てられます。問題は、一般のグラフのK彩色がNP困難であること。最適解を厳密に求めるのは現実のコードサイズでは非現実的なので、コンパイラは**ヒューリスティック（近似）**を使います。

Chaitin–Briggs の単純化と select

実用上の標準が Chaitin に始まり Briggs が改良した彩色アルゴリズムです。核心は次の観察にあります。

ある節点の次数（隣接数）が K 未満なら、他のすべてを塗り終えた後でも、隣接が高々 K-1 色しか使っていないので必ず空き色が残る。つまりその節点は後回しにしても確実に塗れる。

この性質を使い、二段階で処理します。

1. 単純化（simplify）：次数が K 未満の節点をグラフから取り除き、スタックに積む。除去で隣接の次数が下がり、新たに K 未満になる節点が出るので繰り返す。
2. 選択（select）：スタックから逆順に節点を取り出してグラフへ戻し、隣接が使っていない色を割り当てる。単純化の不変条件により、戻す時点で必ず空き色がある。

Briggs の改良点は、次数が K 以上でも実際に塗れるかもしれない節点を即スピルせず、楽観的にスタックへ積む（optimistic coloring）ことです。select で本当に色が足りなければそこで初めてスピル扱いにするため、無駄なメモリ退避が減ります。

スピル — レジスタが足りないとき

単純化が進まず残る全節点の次数が K 以上になると、K色では塗れません。このときどれかの変数を物理レジスタから諦め、メモリ（スタックフレーム）上に置く判断が**スピル（spill）**です。スピルされた変数は、使うたびにロード命令で読み、書き換えたらストア命令で戻すコードが挿入されます。

どの変数をスピルするかが品質を決めます。代表的なスピルコストの見積もりは次の比です。

spill_cost(v) = (定義回数 + 使用回数 × ループネスト重み) / 干渉次数

• 分子が追加されるメモリ命令の多さ（その変数を退避すると挿入されるロード/ストアの実行頻度）。ループ内の参照は反復回数ぶん重く数えます。
• 分母の干渉次数は、その変数を逃がすと何本の辺が消えてグラフが塗りやすくなるかの指標。

この比が小さい変数ほど割安なので優先的にスピルします。「あまり使われず、かつ多くの変数と干渉している」変数が理想的なスピル対象、という直感に対応します。スピル後は干渉グラフを作り直し、彩色をやり直します（反復）。

レジスタ合体（coalescing）

割り当て前のコードには b = a（コピー）が多く残ります。SSA解除でφ関数を展開する際にも大量のコピーが生じます。a と b が干渉していなければ同じレジスタを割り当ててコピー命令ごと消せます。これが**合体（coalescing）**で、干渉グラフ上では両節点を1つに融合する操作です。

ただし無闇に融合すると次数が上がって彩色不能になりかねません。そこで Briggs 流（融合後の高次数隣接が K 未満）や George 流（片方の高次数隣接がもう片方の隣接に包含される）といった**保守的合体（conservative coalescing）**の条件を満たすときだけ融合し、彩色可能性を壊さないようにします。

Linear Scan — 速度重視の割り当て

グラフ彩色は品質が高い反面、グラフ構築と反復で時間がかかります。JITコンパイラのようにコンパイル自体が実行時間に乗る環境では割に合いません。そこで広く使われるのが Linear Scan（線形走査）割り当てです。

考え方は単純です。各変数の生存区間を開始位置でソートした一直線として並べ、左から走査しながら、その時点で生存中の区間集合（active list）に空きレジスタを割り当てていきます。区間が終われば対応レジスタを解放し、後続へ回します。

active を開始順に空に初期化
for 各生存区間 i（開始位置順）:
    active から「終了位置 ≤ i の開始位置」の区間を退役させレジスタ解放
    if active のサイズ == K:
        active 内で「最も終了が遅い」区間 と i のうち一方をスピル
    else:
        i に空きレジスタを割当し active へ追加

彩色問題を解かず、重なり数（同時生存数）がK以下なら塗れるという区間グラフの性質を使うため、ソートを含めてほぼ線形時間で済みます。代償は精度で、生存区間に「穴（live hole）」があっても1本の区間として扱うため、グラフ彩色なら共有できたレジスタを取りこぼすことがあります。改良版の Second-chance / Linear Scan on SSA は区間を分割して穴を活かし、品質差を縮めます。

計算量の比較はBig-Oの見方どおりで、彩色の反復コストとLinear Scanの線形性のトレードオフが、コンパイラの目的（最適性かコンパイル速度か）で選択を分けます。

まとめ

レジスタ割り当ては、無限に使える仮想レジスタを有限K本の物理レジスタへ写す問題です。同時に生存する変数を辺で結んだ干渉グラフを作れば、これは「隣接を異色にするK彩色」へ帰着します。一般のK彩色はNP困難なので、Chaitin–Briggs系は「次数 < Kなら必ず塗れる」性質で単純化・選択し、詰まればスピルコストの安い変数をメモリへ逃がす近似で解きます。コピーは保守的合体で消し、品質を高めます。一方JITのように速度優先の場面では、生存区間を線形走査するLinear Scanがほぼ線形時間で実用解を出します。最適性とコンパイル速度のどちらを取るかが、二つの手法の使い分けを決めています。