11 分で読了 #SSA #static single assignment #φ-function #phi node #dominator #dominance frontier #Cytron algorithm #renaming #out-of-SSA #SSA destruction #sparse analysis #mem2reg #irreducible CFG #use-def chain #virtual register #compilers #intermediate-representation

このページの目次

SSA形式

現代コンパイラ最適化の基盤：各変数はちょうど1回だけ代入され、データフロー解析は反復不動点から、スパースグラフ上の一方向スキャンへと退化します。支配木、支配境界、φ関数は、この制約をすべての制御フローグラフ上で成立させる3つの道具です。

概要

従来のIR（三地址码）では、同じ変数が複数回代入される可能性があります。データフロー解析において、ある変数 x への参照が「どの代入によって生成されたものか」を遡って特定する必要があります。これは大規模関数において、単なるパフォーマンスの問題だけでなく、正しさの問題でもあります（複数の代入点が異なるパスを通じて同じ使用点に至るため）。

SSA（Static Single Assignment） の核心となる制約は極めて簡潔です：⁠プログラム本体において、各変数はちょうど1回だけ定義される⁠。一見厳格に思えますが、φ関数（phi function） を導入することで、任意の還元可能な制御フローをSSAに変換できます。SSA形式になると、データフロー解析の多くの問題が「反復求解」から「一方向スキャン」へと変わります。なぜなら、各値には定義点が1つだけしかないため、use-defチェーンが一意に定まり、計算量が O(n²) ではなく O(n) になるからです。

なぜSSAは解析を単純にするのか：比較

従来のIR:

x = 1           ← def1
if (cond)
    x = 2       ← def2 (def1を上書き)
y = x + 1       ← ここで使われるxはdef1由来かdef2由来か？ cond次第

y = x + 1 がどの代入を使っているかを知るには、⁠到達定義（reaching definition）解析⁠（反復データフロー解析、最悪ケースで O(n²)）を行う必要があります。

SSA等価形式:

x1 = 1          ← 唯一の定義
if (cond)
    x2 = 2      ← 唯一の定義
x3 = φ(x1, x2)  ← 制御フローに応じて x1 または x2 を選択
y = x3 + 1      ← x3 を使用することが確定しており、x3の定義点はφ関数——反復解析に依存しない

各使用点は直接、唯一の定義点を指し示します。これはスパース表現（sparse representation）であり、データフロー情報はCFG全体で伝播させる必要がなく、def-useグラフ上を一度スキャンするだけで済みます。これこそが、SSAが現代の最適化インフラストラクチャの基盤となっている理由です。

SSA構築の3つの重要概念

支配木（dominator tree）

ノードAがノードBを支配（dominate） するとは、エントリからBへのすべてのパスがAを通る場合に限り成立します。支配関係は木を形成します（根はエントリブロック）。

entry はすべてのブロックを支配する
block1 は block2, block3, block4 を支配する
block2 と block3 は互いに支配しない（エントリから block2 へ到達する際に、必ずしも block3 を通るとは限らない）

支配木はCFGから計算されます。Cooperのエンジニアリングアルゴリズム（O(n·|V|)、小規模なCFGで良好なパフォーマンス）またはLengauer-Tarjanアルゴリズム（O(n log n)、大規模なCFG向け）が用いられます。⁠支配木はSSA構築の基盤であり、各変数の定義点は支配木において、その後の到達可能な使用点を「カバー」します。

支配境界（dominance frontier）

しかし、変数は「支配される点」だけで使用されるわけではありません。制御フローが合流する地点（例えば if-else の終了部）では、2つの異なる定義が「出会う」ことになります。⁠支配境界はこれらの合流点を厳密に定義します。

DF(X) = {Y | X は Y のある後続ノードを支配するが、Y は厳密には支配しない}

直訳すると、Yは「Xによって支配されなくなる最初のノード」です。YにはXの支配領域からのエッジが1つありますが、Y自体はXの支配領域の外側にあります。これらのYが、φ関数を挿入する位置となります。

φ関数：制御フロー合流点でのセレクタ

φ関数は実際の命令ではありません。それは「実際の制御フローエッジに応じて、対応するソースの値を選択する」という表記法です。

x3 = φ(block2→x1, block3→x2)
    ↑ block2 から入れば → x3 = x1; block3 から入れば → x3 = x2

コード生成フェーズでは、φ関数はレジスタやメモリ上の実際のmove命令に解消されます。同じ物理的な場所を共有するか、複数のソースレジスタからマージします（SSAの解構）。

Cytronアルゴリズム：効率的なSSA構築

Cytron (1991) のアルゴリズムは現在も標準であり、LLVMやGCCでも採用されています。2つのステップからなります。

ステップ1: φの挿入位置の決定

支配境界を使用します。

変数 v が定義されたすべてのブロック D に対して:
  D の支配境界内のすべてのブロック F に対して:    ← F は合流点
    F の入口に φ(v) を挿入
    F も「v を定義するブロック」として扱う（φ自体が定義だから）
    F の支配境界に対して再帰的に処理を行う

実際には、すべての変数に対して同時に実行します。支配境界を一度トラバースし、各変数についてφ関数が必要なブロックを記憶します。

ステップ2: 変数のリネーム

支配木上で前置順（pre-order）トラバースを行い、⁠各変数名に対応するバージョン番号のスタックを維持します。

rename(block):
    block 内の各 φ に対して:
        φ の結果に新しい変数バージョン（例: x3）を割り当てる
        x → x3 を x のバージョンスタックにプッシュ
    block 内の各命令に対して:
        命令の各使用箇所について:
            変数バージョンスタックを参照し、現在のスタックトップのバージョンに置換
        命令の各定義箇所について:
            新しいバージョン番号（例: x2）を割り当てる
            その変数 → 新しいバージョン番号 をスタックにプッシュ
    block の各後続ノードに対して:
        後続ノードの φ 引数を埋める: 現在の各変数のスタックトップバージョンを使用
    block の支配木の子ノードに対して:
        rename(child)          ← 再帰
    現在の block でプッシュされたすべてのバージョン番号をポップ ← スコープ終了

このリネーム処理は、支配木上を一度 O(N) でトラバースするだけで、すべての変数のバージョン番号付けを完了します。これは「各変数の定義点でCFG上で到達定義を行う」よりも1桁高速です。

SSAの解構：φから実行可能コードへ

SSAのφ関数は実際の命令ではないため、コード生成前に解構（destruction）する必要があります。

解構前:                          解構後 (コピー方式):
  L1: x1 = 1                     L1: x = 1
      goto L3                        goto L3
  L2: x2 = 2                     L2: x = 2
      goto L3                        goto L3
  L3: x3 = φ(x1, x2)             L3:           ← x はすでに正しい値を持っている
      use(x3)                        use(x)

考え方：φの各ソースが同じレジスタを共有できる場合、追加の命令は不要です。制御フローの先行ブロックの末尾で、値を同じレジスタに配置するだけで済みます。⁠重要なのは、1つのφの複数のソースは同時にアクティブになれない（排他的なパス由来である）ため、同じ物理的な場所を共有しても安全であることです。

複雑なケース：複数のφが互いを参照する場合、またはφと通常命令の間に依存関係の循環がある場合（例：x = φ(y, z); y = x + 1、ループ内）。これは「lost copy」や「swap」の問題であり、循環を打破するために一時変数を挿入する必要があります。Cooperら（1998）の古典的なout-of-SSAアルゴリズムです。より効率的な実装については、Pereira & Palsberg (2004) などの後続研究を参照してください。

LLVMにおけるSSAの位置づけ

LLVM IRは完全なSSAです：各仮想レジスタ（%1, %2, ...）は1回だけ代入されます。alloca/load/store はメモリエイリアスを通じてSSAを回避しますが、LLVMの mem2reg パスは、持ち上げ可能な alloca-store-load をSSA仮想レジスタへと持ち上げます。これは最適化パイプラインに入るための最初の関門です。

一度SSA形式になると、LLVMの大部分のパス（インライン展開、GVN、LICM、DCE、ループアンローリングなど）はすべてSSAに基づくスパース解析を行います。これが、LLVMの最適化が高速かつ正確である根本的な理由です。

トレードオフと失敗パターン

φの過剰挿入⁠: 支配境界の保守的な計算により、到達不可能なパスに不要なφが挿入されることがある。→ SSA解構後にデッドコード除去（DCE）によって処理されるため、正しさには影響しないが、中間状態でより多くの仮想レジスタを消費する。
非還元制御フロー（irreducible CFG）: goto や tail call に起因するCFGには、支配木の意味での「単一エントリループヘッダ」がない可能性がある。→ 標準アルゴリズムでは、まずCFGを還元する必要がある（ノード分割など）。
SSA解構による追加のコピー: φの解構により大量のコピー命令が挿入される可能性がある。→ 後続のレジスタ割り当てフェーズで、coalescingによって結合可能なコピーは消去される（SSA解構とレジスタ割り当てはペアであり、レジスタ割り当てを参照）。

参考文献

Cytron et al. (1991): "Efficiently Computing Static Single Assignment Form and the Control Dependence Graph" — SSA構築の元となったアルゴリズム
Cooper/Torczon: "Engineering a Compiler", 第8-9章（支配木の計算を含むSSAの完全な解説）
LLVM: lib/Transforms/Utils/Mem2Reg.cpp, lib/Transforms/Utils/SSAUpdater.cpp — 産業用SSA実装

Keywords: SSA, static single assignment, φ-function, phi node, dominator, dominance frontier, Cytron algorithm, renaming, out-of-SSA, SSA destruction, sparse analysis, mem2reg, irreducible CFG, use-def chain, virtual register