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 #中間表現
このページの目次

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へのすべての経路がAを通る場合に限り、ノードBを支配（dominate） する。支配関係は木を形成する（根はエントリブロック）。

支配木: エントリから各基本ブロックへの支配関係 entry block1 block2 block3 block4 entry はすべてのブロックを支配する。block1 は block2、block3、block4 を支配する。 block2 と block3 は互いに支配しない。entry から片方へ到達する際に、もう片方を通る必要はない。両者は block4 で合流する。
  • entry はすべてのブロックを支配する
  • block1 は block2, block3, block4 を支配する
  • block2 と block3 は互いに支配しない（entry から 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の支配領域からのエッジが伸びているが、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 の支配境界へ再帰的に処理を進める

実際には、すべての変数に対して同時に実行する。支配境界を1回走査し、各変数についてφ関数が必要なブロックを記憶しておく。

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

支配木上でプリオーダー（先頭順）走査を行い、⁠各変数名に対応するバージョン番号のスタックを維持する。

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

このリネームプロセスは、支配木上で1回の O(N) 走査で全変数のバージョン番号付けを完了する。これは「各変数の定義点でCFG上で到達定義を行う」よりも1桁高速である。

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

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

解构前:                         解构后 (copy方式):
  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)

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

複雑なケース：複数のφが互いを参照する場合や、φと通常命令の間に依存関係の循環がある場合（例：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解構による追加のcopy: φの解構により大量のcopy命令が挿入される可能性がある。→ 後のレジスタ割り当てフェーズで、coalescingによって結合可能なcopyは消去される（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

関連ページ

© 2026 liz's doc