SSA形式とコンパイラ最適化

なぜSSAなのか

コンパイラの最適化はコンパイルとインタプリタで言う「実行前の翻訳」段階で、中間表現（IR）に対して行われます。問題は、ふつうのコードでは同じ変数名が何度も再代入されることです。

x = a + b      // 定義1
x = x * 2      // 定義2（同じ名前 x）
y = x + 1

y を最適化するには「ここで使う x はどの代入か」を知る必要があり、従来は**到達定義解析（reaching definitions）**という大域データフロー解析でこれを求めていました。静的単一代入（SSA: Static Single Assignment）形式は、各変数を構文上ちょうど一度だけ代入されるよう名前を付け替えることで、この対応関係を表現そのものに埋め込みます。

x1 = a + b
x2 = x1 * 2
y1 = x2 + 1

こうすると変数名＝定義箇所が常に1対1になり、「どの定義を使うか」を探す解析が消えます。使用から定義へは名前をたどるだけ。これが、多くの最適化がSSA上で簡潔かつ高速になる根本理由です。

φ関数 — 合流点をどう扱うか

直線的なコードなら添字を振るだけで済みますが、制御フローが分岐・合流すると一つの使用に複数の定義が流れ込みます。

if (c) { x1 = 1 } else { x2 = 2 }
// ここで使う x は x1 か x2 か？

SSAはこの合流点（join）にφ（ファイ）関数という擬似命令を置きます。

x3 = φ(x1, x2)
y1 = x3 + 1

φ関数は「制御がどの前任ブロックから来たかに応じて、対応する引数の値を選ぶ」という意味を持ちます。重要なのは、φはブロックの先頭にまとめて置かれ、すべて同時・並列に評価される点です。実機の命令ではないので、SSAを解除する段階で各前任ブロック末尾へのコピー（x3 = x1 など）に展開されます。これによりSSA形式は、分岐があっても「一変数＝一定義」という不変条件を保ちます。

支配と支配辺境界 — φをどこに置くか

φ関数を全合流点に闇雲に置くと、参照されないφが大量に増えます。挿入位置を必要十分に決める鍵が**支配（dominance）**の概念です。

• ブロック D が B を支配するとは、エントリから B へのすべての経路が必ず D を通ること。
• D の支配辺境界（dominance frontier）は、「前任の少なくとも一つは D に支配されるが、自身は D に厳密支配されない」ブロックの集合。直感的には、D の影響が確実には及ばなくなる最初の合流点です。

ある変数の定義がブロック D にあるとき、その値が他経路の値と合流しうるのはまさに D の支配辺境界上です。したがって定義を含むブロックの支配辺境界にφを挿入する——これがCytron らの標準アルゴリズムです。挿入で新たな定義が生まれるため、支配辺境界を反復適用して不動点まで進めます。

最適化がSSAで「効く」理由

SSAの不変条件は、主要な最適化を局所的・線形的な操作へ簡略化します。

定数伝播を例にとると、x1 = 5 のように右辺が定数の定義は、x1 の全使用箇所をその定数で置き換えられます。x1 の定義は一意なので「本当にこの値か」を疑う大域解析が要りません。さらに**疎な条件付き定数伝播（SCCP）**は、φ関数の引数のうち到達不能な枝を ⊤（未定義＝まだ定数かもしれない最適化的な初期値）として無視し、到達可能な枝だけで値を合流させます。定数と制御可達性を同時に求めるため、単純な定数伝播より強力です（⊥ は「定数でない」を表す逆側の格子値）。

デッドコード除去は、各定義の使用リスト（def-use 連鎖）がSSAでは即座に得られることを利用します。使用が一つもない定義は削除でき、削除によりその右辺で使っていた変数の使用も減るため、ワークリスト法で連鎖的に到達不能・無用な計算を刈り取れます。

値番号付けとCSE

共通部分式除去（CSE）は「同じ計算を二度しない」最適化です。SSAでは各定義が一意な名前を持つため、右辺が構文的に等しい（かつオペランドが同じ値番号を指す）定義に同一の値番号を割り当てられます。

t1 = a + b      // value #1
// ...
t2 = a + b      // 同じ value #1 → t2 を t1 で置換

支配木に沿って走査する**支配木ベースの値番号付け（DVNT）**を使えば、ある定義が支配する範囲でのみ再利用が安全、という関係を木の構造がそのまま保証します。計算量の見積もりは計算量（Big-O）の考え方どおりで、多くのSSA最適化はIRサイズにほぼ線形です。

SSAの解除（out-of-SSA）

φは実機命令ではないため、最適化後にSSA解除してコピーへ展開します。素朴に各φ前任へコピーを挿入すると、並列同時評価の意味（lost-copy 問題・swap 問題）を壊すことがあり、依存を考慮した順序付けや一時変数の導入が必要です。展開後は同名化された変数が増えるため、コピー伝播とレジスタ割り付け（ガベージコレクションとは別レイヤの、CPUレジスタへの変数割当）で後始末します。SSAは割り付け前の干渉グラフが扱いやすい（生存区間が分割されている）という利点もあり、現代のLLVMやGCC、JITコンパイラが標準採用しています。

まとめ

SSA形式は、各変数を一度だけ代入する形へ名前を付け替えることで「使用がどの定義に対応するか」を表現に焼き込み、到達定義解析を不要にします。制御の合流はφ関数で表し、その挿入は支配辺境界で最小かつ正確に決まります。この基盤の上で、定数伝播・デッドコード除去・共通部分式除去はuse-def連鎖や値番号付けを使った局所的・線形的な操作になり、実装も実行も単純化されます。最後にSSAを解除してコピーへ戻すまでが一連の流れで、これが主要コンパイラがSSAを中核IRに据える理由です。