概要
**SSA（Static Single Assignment）形式**は現代コンパイラで最も広く使われる中間表現（IR）です。GCC、LLVM、HotSpot JVMなどほぼすべての主要コンパイラがSSAを基に最適化を行っています。
SSAの核心アイデアはシンプルです：**各変数がプログラムで正確に1回だけ定義される**。この単純な性質が多くの最適化を簡単かつ効率的にします。
1. SSA形式の基本概念
1.1 既存コードの問題
// 一般的な3アドレスコード
x = 1
x = 2 // xが2回定義されている！
y = x + 1 // どのxを使っているのか？ -> 2番目の定義
既存の表現では同じ変数が複数回定義されるため、定義-使用（def-use）関係を追跡するために追加の分析が必要です。
1.2 SSA変換
各定義に固有のバージョン番号を付与します：
// SSA形式
x1 = 1
x2 = 2 // 別のバージョン！
y1 = x2 + 1 // 明確にx2を使用
これで各使用（use）が正確に一つの定義（def）に対応します。別途の到達定義分析なしでも定義-使用関係が明確です。
1.3 直線コードでのSSA
分岐のないコードのSSA変換は簡単です：
// 元 // SSA
a = x + y a1 = x1 + y1
b = a - 1 b1 = a1 - 1
a = y + b a2 = y1 + b1
b = 4 * a b2 = 4 * a2
2. Phi関数
2.1 分岐での問題
制御フローが合流（merge）する地点では、どの経路から来たかによって変数の値が異なります。
// 元のコード：
if (cond)
x = 1; // 経路A
else
x = 2; // 経路B
y = x + 1; // xは1か2か？
2.2 Phi関数の導入
**Phi関数**（phi-function）は合流地点で複数の経路の値を選択します：
// SSA形式：
if (cond)
x1 = 1; // 経路A
else
x2 = 2; // 経路B
x3 = phi(x1, x2); // 合流地点：経路に応じてx1またはx2を選択
y1 = x3 + 1;
phi関数は実際に実行される命令ではありません。意味的に「この地点に到達した経路に応じて値を選択」する表記法です。
2.3 Phi関数の特性
// phi関数は合流ブロックの先頭に配置
// 複数のphi関数があればすべて「同時に」実行されると見なす
B3:
x3 = phi(x1, x2) // B1から来ればx1、B2から来ればx2
y3 = phi(y1, y2)
z1 = x3 + y3
2.4 ループでのPhi関数
// 元：
i = 0
loop:
if (i >= n) goto exit
i = i + 1
goto loop
exit:
// SSA：
i1 = 0
loop:
i2 = phi(i1, i3) // ループ進入時i1、ループ反復時i3
if (i2 >= n1) goto exit
i3 = i2 + 1
goto loop
exit:
3. SSA構築アルゴリズム
3.1 どこにPhi関数を挿入するか
素朴にすべての合流地点にphi関数を入れると多すぎるphi関数が生じます。**支配境界（Dominance Frontier）**を利用すると必要な箇所にのみphi関数を挿入できます。
3.2 支配境界とPhi関数
**核心的洞察**：変数xがブロックBで定義されると、Bの支配境界にあるブロックにphi関数が必要です。
// 理由：
// Bが支配する領域内ではxの定義が唯一
// 支配境界で他の経路の定義と合流し得る
// -> phi関数が必要な箇所 = 支配境界
3.3 SSA構築アルゴリズム
アルゴリズム：SSA構築（2段階）
第1段階：Phi関数の挿入
for（各変数v）：
W = vを定義するブロックの集合
while Wが空でない：
B = Wからブロックを一つ取り出す
for（DF(B)の各ブロックD）：
if Dにvに対するphi関数がなければ：
Dの先頭にphi関数挿入：v = phi(v, v, ...)
if DがWになければWにDを追加
//（phi関数もvの新たな定義であるため）
第2段階：変数名の変更（Renaming）
支配者木を深さ優先で巡回しながら：
各定義に新しいバージョン番号を付与
各使用を現在有効なバージョンに置換
phi関数の引数を適切な先行ブロックのバージョンに設定
3.4 構築の例
// CFG：
// B1: x = 5
// |
// B2: if cond
// / \
// B3: x=10 B4: x=20
// \ /
// B5: y = x
// 支配境界：
// DF(B3) = {B5}
// DF(B4) = {B5}
// 第1段階：B5にphi関数挿入
// B5: x = phi(x, x)
// 第2段階：名前変更
// B1: x1 = 5
// B2: if cond
// B3: x2 = 10
// B4: x3 = 20
// B5: x4 = phi(x2, x3) // B3から来ればx2、B4から来ればx3
// y1 = x4
4. SSAベース最適化
4.1 希薄条件付き定数伝播（Sparse Conditional Constant Propagation）
SSAでは定数伝播を非常に効率的に実行できます。
// SSAコード：
x1 = 3
y1 = 5
z1 = x1 + y1 // 定数畳み込み：z1 = 8
w1 = z1 * 2 // 定数畳み込み：w1 = 16
if (w1 > 10) goto L1 // 常にtrue -> goto L1
// 各変数が1回だけ定義されるので：
// x1の値 = 3（確定）
// y1の値 = 5（確定）
// z1の値 = 8（確定）
// 到達定義分析なしで直接伝播可能！
**SCCP（Sparse Conditional Constant Propagation）**アルゴリズム：
アルゴリズム：SCCP
束：Top（未確認）> 定数値 > Bottom（非定数）
1. すべてのSSA値をTopで初期化
2. 入口ブロックを実行可能として標示
3. ワークリストからSSA辺とCFG辺を取り出しながら：
- SSA辺：定義の値が変更されたら使用箇所を更新
- CFG辺：実行可能な辺のみ考慮
4. 収束するまで反復
核心：実行不能な経路の値は考慮しない
-> phi(3, Top) = 3（Topはまだ到達していない経路）
4.2 デッドコード除去
SSAではdef-useチェーンが明示的なので、使用されない定義を簡単に見つけられます。
// SSAコード：
x1 = a1 + b1 // x1を使用する箇所がない -> デッドコード
y1 = c1 * d1 // y1は下で使用される
z1 = y1 + 1
return z1
// x1除去後：
y1 = c1 * d1
z1 = y1 + 1
return z1
**攻撃的デッドコード除去（Aggressive DCE）**：
アルゴリズム：攻撃的DCE
1. 副作用のある命令を「有用」としてマーク
（return、store、入出力、関数呼び出しなど）
2. 有用な命令が使用するSSA値の定義を「有用」としてマーク
3. 反復：新たに有用になった命令の被演算子の定義を追加マーク
4. 有用でないすべての命令を除去
// 従来のDCEより強力：不要な制御フローまで除去可能
4.3 大域的値番号付け（Global Value Numbering）
同じ値を計算する式を見つけ出して重複を除去します。
// SSAコード：
a1 = x1 + y1
b1 = x1 + y1 // a1と同じ値！
// 大域的値番号付け：
// x1 + y1に値番号#1を付与
// a1の値番号 = #1
// b1の値番号 = #1（同じ演算、同じ被演算子）
// -> b1をa1に置換
**ハッシュベース値番号付け**：
アルゴリズム：SSAベースGVN
ハッシュテーブル維持：（演算子、被演算子の値番号）-> 値番号
for（支配者木の深さ優先順序で各命令）：
被演算子の値番号を検索
（演算子、被演算子値番号）でハッシュテーブル検索
if 発見：
既存の値番号をこの命令に配定（重複！）
else：
新しい値番号を付与しハッシュテーブルに追加
例：
// SSA：
// B1: a1 = x1 + y1 // 値番号：v1
// |
// B2: b1 = x1 + y1 // ハッシュ検索：(+ v(x1) v(y1)) -> v1発見！
// c1 = b1 * 2 // b1をa1に置換可能
//
// 最適化後：
// B1: a1 = x1 + y1
// B2: c1 = a1 * 2 // b1除去
4.4 SSAと他の最適化の関係
// SSAが助けになる最適化：
// 1. 定数伝播 -> def-useチェーンで効率的に伝播
// 2. デッドコード除去 -> 使用箇所のないdefを即座に識別
// 3. 値番号付け -> ハッシュベースで重複計算を識別
// 4. コピー伝播 -> phi関数を通じてコピー関係を追跡
// 5. 部分冗長除去 -> SSA辺を通じた効率的分析
// 6. レジスタ割り当て -> SSAの生存範囲がより短い
5. SSAから一般コードへの復元
5.1 Phi関数の除去
実際の機械にはphi関数がないため、SSAから離れる際にphi関数を**コピー命令**に変換します。
// SSA：
// B1: x1 = 5
// |
// B2: x2 = 10
// |
// B3: x3 = phi(x1, x2)
// phi除去後：
// B1: x1 = 5
// x3 = x1 // B3からB1の末尾に移動
// |
// B2: x2 = 10
// x3 = x2 // B3からB2の末尾に移動
// |
// B3:（phi除去済み、x3を使用）
5.2 並列コピー問題
複数のphi関数が同時に実行されるため、単純な変換では干渉が発生し得ます。
// SSA：
// B3: a2 = phi(a1, b1)
// b2 = phi(b1, a1)
// （swap意味：B2から来ればaとbを交換）
// 誤った変換：
// B2末尾：a2 = b1 // a2にb1の値
// b2 = a1 // 正しい
// 正しい変換（一時変数使用）：
// B2末尾：temp = a1
// a2 = b1
// b2 = temp
5.3 コピー合体（Copy Coalescing）
phi除去で生じたコピー命令を最小化します。
// phi除去後：
// B1: x1 = 5
// x3 = x1 // 不要なコピー
// コピー合体後：
// B1: x3 = 5 // x1とx3を同じ変数に統合
レジスタ割り当て時に**合体（coalescing）**によりこのようなコピーを除去します。x1とx3が同時に生存でなければ（干渉しなければ）同じレジスタに割り当てられます。
6. SSA形式の変形
6.1 最小SSA（Minimal SSA）
支配境界ベースで必要最小限のphi関数のみ挿入した形式です。上で説明した標準構築アルゴリズムが最小SSAを生成します。
6.2 枝刈りSSA（Pruned SSA）
最小SSAでも不要なphi関数が存在し得ます。生存変数情報を利用して使用されないphi関数を事前に除去します。
// 最小SSA：
x2 = phi(x1, x1) // 2つの引数が同じ -> 不要
y2 = phi(y1, ...) // y2がその後使用されない -> 不要
// 枝刈りSSA：上記phi関数を挿入しない
6.3 ゲート付きSSA（Gated SSA）
phi関数に条件情報を追加した拡張です。
// 通常のSSA：
x3 = phi(x1, x2)
// ゲート付きSSA：
x3 = gamma(cond, x1, x2) // condがtrueならx1、falseならx2
// 最適化により有用な情報を提供
まとめ
| 概念 | 説明 |
| ---------------- | -------------------------------------------- |
| SSA形式 | 各変数が正確に1回だけ定義される中間表現 |
| Phi関数 | 合流地点で複数経路の値を選択 |
| 支配境界 | phi関数挿入位置を決定する核心情報 |
| SCCP | 実行不能経路を考慮した希薄定数伝播 |
| 攻撃的DCE | 有用なコードから逆追跡してデッドコードを除去 |
| 大域的値番号付け | ハッシュベースで重複計算を識別 |
| Phi除去 | phi関数をコピー命令に変換 |
| コピー合体 | 不要なコピーをレジスタ割り当て時に除去 |
SSA形式は現代コンパイラ最適化の標準的な基盤です。各変数が1回だけ定義されるという単純な性質がdef-use関係を明示的にし、定数伝播、デッドコード除去、値番号付けなど様々な最適化を簡単かつ効率的に実装できるようにします。LLVM IRがSSAベースであるのは偶然ではありません。次の記事では現代コンパイラの全体的な発展方向と応用分野を見ていきます。
현재 단락 (1/232)
**SSA（Static Single Assignment）形式**は現代コンパイラで最も広く使われる中間表現（IR）です。GCC、LLVM、HotSpot JVMなどほぼすべての主要コンパイラがS...