レジスタ割り当て

IR（中間表現）は各中間値に新しい名前を付けることができるが、ターゲットマシンには有限かつ機能が異なるレジスタしか存在しない。レジスタ割り当ては、値が各実行セグメントでどのレジスタまたはスタックスロットに位置するかを決定し、必要なデータ移動命令を挿入する。

これは、すべての変数に対して一度に恒久的な位置を選ぶことではない。ある値はまずレジスタにあり、呼び出しを跨いでスタックに一時的に保存され、その後別のレジスタに再ロードされる可能性がある。実際の品質は、これらの範囲をどのように分割するかにかかっていることが多い。

活性範囲と干渉

もし将来のいずれかのパスで、値が上書きされる前に使用される場合、その値は現在の位置で「アクティブ（活性）」である。異なる値が同時に保持されなければならず、表現を共有できない場合、同じ物理レジスタに対して競合が生じる。干渉グラフは、このような制約を辺で表現する。

CFG（制御フローグラフ）における活性範囲には分岐や穴が含まれる可能性があり、ソースコードの行番号上の連続した区間とは一致しない。SSAのφ入力（フェイ関数の入力）は対応する先行エッジ上で使用され、異なる先行ノードからの入力を一律にマージブロックの入口で同時に使用されるものと見なすことはできない。さらに、無条件にすべてのφの来源と結果の活性範囲を一つの塊として連結することもできない。

グラフ彩色：まずは単純化モデルで理解する

K個の互換性のあるレジスタがあり、両者の干渉のみを考慮するモデルでは、レジスタは「色」であり、隣接するノードは異なる色でなければならない。一般のK彩色の判定は困難な問題であり、スピルコストの最適化はさらに複雑な問題である。現実の割り当てプロセス全体を、単なるNP完全問題の決定問題に単純化してはならない。

単純化アルゴリズムは、次数がK未満のノードを繰り返し取り除き、スタックに積む。復元時、すでに彩色された隣接ノードは最大でK-1個であり、利用可能な色が少なくとも1つ存在する。この推論は、互換性のある色などの仮定に依存しており、固定レジスタやクラスの制約を扱うには拡張が必要である。

楽観的彩色：高次数だからといって必ずしも割り当て不能ではない

残りのグラフに低次数ノードがない場合、潜在的なスピル候補を選択して取り除くことができるが、直ちにスピルを生成するわけではない。復元して彩色する際、まだ色があれば正常に割り当て、本当に色がない場合にのみスピルを行う。

これが楽観的な彩色の核心である：⁠次数がK以上またはそれ以上の候補に対する判定を保留するのであり、次数がK未満のノードの彩色可能性を疑っているわけではない。次数が高いノードの隣接ノードは色を共有する可能性があるため、隣接ノードの数が多いからといって、すべての色がすでに占有されているわけではない。

実際の候補コストは、通常、使用頻度、ループ重み、再ロードコスト、活性範囲などを組み合わせて決定される。ホットループ内で頻繁に使用される値をスピルすることは、コールドパス上の値よりも高くなることが多い。

四角形の反例：すべてのノードの次数がKでも、K色で彩色可能

K=2とし、グラフの辺を A—B、B—C、C—D、D—A とする。各ノードの次数はすべて2であり、「次数がK未満」というルールでは直ちに単純化できるノードはない。しかし、AとCが同じレジスタを共有し、BとDが別のレジスタを共有すれば十分である。

楽観的割り当てでは、まずAを潜在的なスピル候補として取り除くことができる。残りのパス B—C—D の端点の次数は1であり、さらに単純化を進められる。復元時、BとDは色を共有できるため、Aには別の色が残る。候補としてマークされた意味は、低次数によって成功が保証できない一時的な状態を示すものであり、すでにメモリアクセスの生成が必要であると証明されたわけではない。

以下に、小さなグラフで全探索を行う結果検証ツールを示す。これは産業用割り当て器の性能をシミュレートするために使用するものではない。四角形は2彩色可能であり、三角形は不可能である。「次数が高いノードが必ずしも失敗するわけではない」と「リソースが確かに不足する可能性がある」は、同じモデル内で両立し得る。

from itertools import product


def coloring(nodes, edges, k):
    for colors in product(range(k), repeat=len(nodes)):
        assigned = dict(zip(nodes, colors))
        if all(assigned[a] != assigned[b] for a, b in edges):
            return assigned
    return None


square = [("A", "B"), ("B", "C"), ("C", "D"), ("D", "A")]
assert coloring("ABCD", square, 2) is not None
triangle = [("A", "B"), ("B", "C"), ("C", "A")]
assert coloring("ABC", triangle, 2) is None
assert coloring("ABC", triangle, 3) is not None

この四角形は一般的な干渉グラフモデルの例であり、後述の「厳密なSSAの弦グラフ性」の例としては使用しない。四角形には弦（chord）がないため、一般的なグラフの楽観的単純化を説明するためにこれを使う一方で、厳密なSSAモデルのすべての前提を満たすと主張することはできない。

各ノードの次数が非常に高い場合、必ずスピルが必要か？

次数の条件は、割り当て不能であるという決定ではなく、十分な保証を提供するものである。四角形はK=2において低次数ノードを持たないが、互いに隣接していない2つのノードを同じレジスタに配置することで、合法な割り当てが可能である。以下では、手動での色付け試行を許可するとともに、小さなグラフの全探索によって独立した可行性の結論も示す。手動割り当てでの衝突と、グラフ全体がK彩色不可能であることは、区別して読むべきである。

Spill、分割、再計算

Spillは必要に応じて値をスタックに保存し、後続の使用前に再ロードする。保存およびロードの位置は最適化可能であり、常に「定義直後に書き込み、使用前直ちに読み込み」にする必要はない。挿入された新しい命令は、新しい短期間の値と制約を生成し、継続的な割り当てが必要になる可能性がある。

活性範囲の分割により、ホットセグメントはレジスタに残し、コールドセグメントは一時的に保存できる。Rematerialization（再計算）は、安価で安全に再構築可能な値（特定の定数やアドレスなど）に対して再計算を行い、メモリ読み書きを回避する。再計算も例外、副作用、ターゲットコストに従わなければならない。

スタックスロットも、ライフタイムが重ならない場合に再利用できるが、アライメント、サイズ、GC参照マッピング、デバッグ情報の更新は正しく行う必要がある。

線形走査：プログラム配置に従って範囲を処理する

基本的な線形走査は、活性範囲を区間として近似し、開始点でソートする。現在のアクティブなレジスタの集合 active を維持する。新しい区間が始まると、終了した区間のリソースが解放される。リソースが不足する場合、新しい区間または既存の区間の一部をスピル対象として選択する。

基本的な近似では、実際のライフタイム内の穴（非アクティブ期間）もアクティブとしてカウントされ、不要な圧力がかかる可能性がある。改良版では、穴、固定区間、分割、位置制約を処理できる。これはコンパイル遅延を重視する場面でよく使用されるが、任意の線形走査が任意のグラフ割り当て器よりも劣っている、または優れていると断言することはできない。

計算量は、ソート、区間データ構造、分割戦略に依存する。比較は、具体的な実装、コンパイル時間、最終的なスピルに基づいて行うべきであり、2つのアルゴリズムに無条件な計算量のラベルを貼付けてはならない。

Coalescing：コピーの消除、しかし圧力を増加させる可能性もある

v2=v1 の両側で同じレジスタが使用できる場合、コピー命令は消滅する。しかし、2つのノードをマージすると、その隣接制約もマージされるため、もともと彩色しやすいグラフをより困難にする可能性がある。

古典的なBriggsの保守的判別基準は、マージ後の隣接ノードのうち、次数がK以上の高リスクノードの数がK未満かどうかに関心がある。これは、マージ後の総次数がK未満であることを単純に要求するものではない。Georgeスタイルの判別基準は、ノードの隣接ノードが低次数であるか、またはすでに別のノードと隣接しているかなどの条件をチェックし、通常、プレ彩色と組み合わせて使用される。

これらの判別基準は、特定のグラフ彩色モデルにおける十分条件であり、すべてのマシン制約の下で万能として適用できるものではない。実装では、割り当て後にコピー消除を行うか、分割によって過度のマージによる圧力を軽減することもできる。

直接干渉がない2つのノードでも、マージ後に彩色数が増加する可能性がある

まず、パス A—B—C—D を考える。これは2色で交互に彩色できる。AとDには辺がないが、もしある候補コピーが両者を恒久的に同じ位置に共用させようとして、それらをMに合成すると、元の辺は M—B、B—C、C—M となり、3色を必要とする三角形が形成される。

from itertools import product


def can_color(nodes, edges, k):
    for values in product(range(k), repeat=len(nodes)):
        colors = dict(zip(nodes, values))
        if all(colors[a] != colors[b] for a, b in edges):
            return True
    return False


path = [("A", "B"), ("B", "C"), ("C", "D")]
assert can_color("ABCD", path, 2)
rename = {"A": "M", "B": "B", "C": "C", "D": "M"}
merged = [(rename[a], rename[b]) for a, b in path]
assert not can_color("MBC", merged, 2)
assert can_color("MBC", merged, 3)

ここでは、コピー候補と干渉辺を分けて考える。候補は消除したい移動を示し、辺は位置の共有を禁止する制約を示す。A—Dの辺がないことは、両者が直接衝突しないことを示すだけで、他の制約を一緒にマージしても同じ数のレジスタで処理できることを証明するものではない。保守的なマージ判別基準は、まさにこの間接的な圧力増加を防ぐためのものである。マージを拒否しても、コピーが恒久的に残ることを意味するものではなく、後の分割や局所的な消除によって処理される可能性がある。

直接の衝突がないのに、マージ後になぜ割り当てが不足するのか？

ノードをマージする際、それらのすべての隣接制約も一緒に持ち越さなければならない。以下では、AとDの2つの名前を1つのMに折りたたむことで、以前は両端に分かれていた制約が三角形として閉じる。この反例は、「直接干渉がない」ことだけでは恒久的なマージを承認するのに不十分であることを示している。あるcoalescingを拒否するかどうかは、依然として使用される判別基準とターゲット制約によって決定すべきであり、逆にすべてのコピーは残すべきだと解釈してはならない。

SSAがなぜ役立つか、そしてなぜすべての困難を解消しないか

厳密なSSAにおいて、正しいφ辺のセマンティクスに従って構築された干渉グラフは、利用可能な弦グラフ（chordal graph）の性質を持つ。理想的なレジスタモデルでは、適切な順序で最少の色数を効率的に求めることができる。これは干渉グラフに関するものであり、def-useグラフそのものではない。SSAレジスタ割り当て論文

現実には、スピル選択、コピーマージ、レジスタクラス、プレ彩色、サブレジスタの重なり、命令制約などがある。SSA分解における並列コピーも正しくスケジューリングする必要がある。最適な理想的彩色が、必ずしも全体のターゲット割り当てが解決されたことを意味するわけではない。

ABIと命令制約

呼び出しを跨いで生存する値は、呼び出し側保存（caller-saved）レジスタに保護なしで置くことはできない。呼び出し先保存（callee-saved）レジスタを選択するか、保存・再ロードを行うか、分割する必要がある。callee-savedレジスタを使用すると、その関数の保存・復元コストが発生する可能性がある。

パラメータと戻り値のルールは、型およびABI分類に従う。すべてのx86-64の値を「最初の6つの整数レジスタ、戻り値はRAX」として処理してはならない。2アドレス命令、暗黙のレジスタ、ベクトルレジスタグループは、追加のバインディングをもたらす。ターゲットコードとABI を参照。

割り当て品質の観察

最終的には、マシンコードとターゲット負荷を確認すべきである。インライン展開、スケジューリング、ループ展開を変更すると活性範囲が変化するため、レジスタ割り当てはバックエンドパイプラインの一部である。

参考

• Register Allocation for Programs in SSA-Form。
• LLVM Code Generator。
• データフロー解析。

Keywords: register allocation, interference graph, coloring, optimistic coloring, linear scan, spill, splitting, rematerialization, coalescing