概要
**データフロー分析**（Data-Flow Analysis）はコンパイラ最適化の核心的な基盤技術です。プログラムの各地点で特定の性質に関する情報を収集し、安全な最適化が可能かどうかを判断します。
この記事では、データフロー分析の基本概念、3つの代表的な分析（到達定義、生存変数、利用可能式）、反復アルゴリズム、そして束論の基礎を扱います。
1. データフロー分析の基本概念
1.1 分析の目標
プログラムの各地点（point）で以下のような質問に答えます：
- 変数xの値はどこで定義されたか？
- 変数xの値がその後使用されるか？
- 式 `a + b` が既に計算されて使用可能か？
1.2 プログラム地点
基本ブロックの各命令の前後を**プログラム地点**と呼びます。
// ブロックB：
// [地点1] d1: x = a + b [地点2]
// [地点2] d2: y = x * c [地点3]
//
// IN[B] = 地点1での情報
// OUT[B] = 地点3での情報
1.3 伝達関数（Transfer Function）
各基本ブロックBに対して**伝達関数** f_Bは入力情報を出力情報に変換します：
OUT[B] = f_B(IN[B])
ほとんどのデータフロー分析で伝達関数はgen/kill形式です：
OUT[B] = gen[B] U (IN[B] - kill[B])
- `gen[B]`：ブロックBで新たに生成される情報
- `kill[B]`：ブロックBで無効化される情報
1.4 合流演算（Meet/Join Operation）
一つのブロックに複数の先行ブロックがある場合、各先行ブロックの情報を合わせる演算です。
// 和集合（Union）：いずれかの経路で成立すれば含む
IN[B] = U OUT[P] (PはBのすべての先行者)
// 積集合（Intersection）：すべての経路で成立して初めて含む
IN[B] = n OUT[P] (PはBのすべての先行者)
2. 到達定義（Reaching Definitions）
2.1 概念
定義dがプログラム地点pに**到達**する = dからpまでの経路が存在し、その経路で同じ変数が再定義されない。
2.2 gen/kill集合
命令 d: x = y op z に対して：
gen = 定義d自体
kill = xに対するその他すべての定義
ブロックB全体のgen/kill：
// ブロックBにd1, d2, ..., dk命令が順に存在する場合
// 後の命令が前の命令を上書きし得る
gen[B] = gen(dk) U (gen(dk-1) - kill(dk)) U ...
kill[B] = kill(d1) U kill(d2) U ... U kill(dk)
2.3 データフロー方程式
OUT[B] = gen[B] U (IN[B] - kill[B])
IN[B] = U OUT[P] (PはBのすべての先行者)
合流演算が**和集合**である理由：どの経路を通じてでも定義が到達すればその値を使用する可能性があるため、保守的にすべて含める必要があります。
2.4 例
// フローグラフ：
// B1 -> B2 -> B3
// ^ |
// +-----+
// B1: d1: x = 5 gen={d1}, kill={d2,d4}
// B2: d2: x = x + 1 gen={d2}, kill={d1,d4}
// B3: d3: y = x gen={d3}, kill={}
// d4: x = y + 1 gen={d4}, kill={d1,d2}
// gen[B3] = {d4} U ({d3} - {d1,d2}) = {d3, d4}
// kill[B3] = {d1, d2}
反復計算：
初期値：OUT[B] = {}（すべてのBに対して）
反復1：
IN[B1] = {}
OUT[B1] = {d1} U ({} - {d2,d4}) = {d1}
IN[B2] = OUT[B1] U OUT[B3] = {d1} U {} = {d1}
OUT[B2] = {d2} U ({d1} - {d1,d4}) = {d2}
IN[B3] = OUT[B2] = {d2}
OUT[B3] = {d3,d4} U ({d2} - {d1,d2}) = {d3,d4}
反復2：
IN[B2] = OUT[B1] U OUT[B3] = {d1} U {d3,d4} = {d1,d3,d4}
OUT[B2] = {d2} U ({d1,d3,d4} - {d1,d4}) = {d2,d3}
IN[B3] = OUT[B2] = {d2,d3}
OUT[B3] = {d3,d4} U ({d2,d3} - {d1,d2}) = {d3,d4}
反復3：
IN[B2] = {d1} U {d3,d4} = {d1,d3,d4}（変化なし）
-> 収束！
3. 生存変数分析（Live-Variable Analysis）
3.1 概念
変数xがプログラム地点pで**生存（live）**である = pから始まるある経路でxが再定義される前に使用される。
3.2 逆方向分析
生存変数分析は**逆方向**（backward）分析です。プログラムの終わりから始まりに向かって遡ります。
// 伝達関数（逆方向）
IN[B] = use[B] U (OUT[B] - def[B])
OUT[B] = U IN[S] (SはBのすべての後続者)
- `use[B]`：ブロックBで定義される前に使用される変数
- `def[B]`：ブロックBで定義される変数
3.3 use/def集合の計算
// ブロックB：
// x = y + z // use: {y, z}, def: {x}
// a = x + 1 // use: {x}, def: {a}（xは上で定義済みなのでuse[B]に含まれない）
// use[B] = {y, z}（定義前に使用された変数）
// def[B] = {x, a}（定義された変数）
3.4 例
// B1: a = 1; b = 2
// B2: c = a + b; d = c - a
// B3: d = b + d;（出口）
// use[B1] = {}, def[B1] = {a, b}
// use[B2] = {a, b}, def[B2] = {c, d}
// use[B3] = {b, d}, def[B3] = {d}
// 初期値：IN[B] = {}（すべてのBに対して）
反復1：（逆方向：B3 -> B2 -> B1）
OUT[B3] = {}（出口ブロック）
IN[B3] = {b, d} U ({} - {d}) = {b, d}
OUT[B2] = IN[B3] = {b, d}
IN[B2] = {a, b} U ({b, d} - {c, d}) = {a, b}
OUT[B1] = IN[B2] = {a, b}
IN[B1] = {} U ({a, b} - {a, b}) = {}
-> 収束！（変化なし）
3.5 活用
- **デッドコード除去**：代入 `x = expr` のOUT地点でxが生存でなければデッドコード
- **レジスタ割り当て**：同時に生存する変数が干渉グラフの辺を形成
4. 利用可能式（Available Expressions）
4.1 概念
式 `x op y` がプログラム地点pで**利用可能**である = pに到達する**すべて**の経路で `x op y` が計算されており、その後xとyが再定義されていない。
4.2 データフロー方程式
OUT[B] = e_gen[B] U (IN[B] - e_kill[B])
IN[B] = n OUT[P] (PはBのすべての先行者)
IN[ENTRY] = {}
合流演算が**積集合**である理由：すべての経路で計算されていなければ安全に再利用できません。
- `e_gen[B]`：ブロックBで計算され、その後被演算子が再定義されない式
- `e_kill[B]`：ブロックBで変数xが定義されるとき、xを被演算子に含むすべての式
4.3 例
// B1: t1 = a + b; c = t1
// e_gen[B1] = {a+b}
// e_kill[B1] = {cを含む式}
// B2: t2 = a + b; d = t2 - c
// e_gen[B2] = {a+b, t2-c}
// e_kill[B2] = {dを含む式}
// B3: a = 1
// e_gen[B3] = {}
// e_kill[B3] = {aを含むすべての式} = {a+b}
4.4 初期値の重要性
利用可能式分析では初期値の設定が重要です：
OUT[ENTRY] = {} // 入口点ではどの式も利用可能でない
OUT[B] = U // 他のブロックは全体集合（すべての式）で初期化
// （積集合なので大きな値から始めないと正しく収束しない）
5. 反復アルゴリズム
5.1 一般的な反復アルゴリズム
アルゴリズム：順方向データフロー分析
入力：フローグラフ、gen/kill集合、合流演算
出力：各ブロックのIN/OUT集合
1. 初期化
OUT[ENTRY] = 初期値
for (すべてのブロック B != ENTRY)
OUT[B] = 初期値
2. 反復
changed = true
while (changed)：
changed = false
for (すべてのブロック B != ENTRY)：
IN[B] = meet(OUT[P] for all predecessors P)
oldOUT = OUT[B]
OUT[B] = gen[B] U (IN[B] - kill[B])
if OUT[B] != oldOUT：
changed = true
5.2 収束の保証
反復アルゴリズムが必ず終了する理由：
1. gen/kill伝達関数は**単調（monotone）**です - 入力が大きくなれば出力も大きくなる（または同じ）
2. データフロー値の集合は**有限**です
3. 合流演算（和集合または積集合）も単調です
したがって、各反復でOUT値は一方向にのみ変化し、有限な範囲内で最終的に安定状態に到達します。
5.3 収束速度
一般に反復回数はフローグラフの**深さ（depth）**に比例します。深さはループのネスト深さと関連します。ほとんどのプログラムで2-3回の反復で収束します。
6. 3つの分析の比較
| 特性 | 到達定義 | 生存変数 | 利用可能式 |
| -------- | ----------------- | ----------------- | --------------------- |
| 方向 | 順方向 | 逆方向 | 順方向 |
| 合流演算 | 和集合 | 和集合 | 積集合 |
| 伝達関数 | gen U (IN - kill) | use U (OUT - def) | e_gen U (IN - e_kill) |
| 初期値 | 空集合 | 空集合 | 全体集合（Entry除く） |
| 活用 | 定数伝播 | デッドコード除去 | 共通部分式除去 |
7. 束論の基礎
7.1 半順序集合（Partially Ordered Set）
データフロー分析の数学的基盤は**束論**（Lattice Theory）です。
半順序集合は集合Sと関係 `<=` で構成され、以下を満たします：
- **反射性**：`a <= a`
- **反対称性**：`a <= b` かつ `b <= a` ならば `a = b`
- **推移性**：`a <= b` かつ `b <= c` ならば `a <= c`
7.2 束（Lattice）
半順序集合で任意の2元素a、bに対して：
- **最小上界（join）**：aとb両方以上の元素のうち最小のもの
- **最大下界（meet）**：aとb両方以下の元素のうち最大のもの
この2つが常に存在すれば**束**と呼びます。
7.3 データフロー分析と束
// 到達定義分析の束
// 元素：定義の部分集合 (2^D)
// 順序：集合包含関係（部分集合）
// meet演算：和集合 (U)
// bottom：空集合 ({})
// top：全体集合 (D)
// 利用可能式分析の束
// 元素：式の部分集合 (2^E)
// 順序：逆方向集合包含関係（上位集合）
// meet演算：積集合
// bottom：全体集合 (E)
// top：空集合 ({})
7.4 不動点定理
**Tarskiの不動点定理**：完全束上の単調関数fは最小不動点を持ちます。反復アルゴリズムはこの最小不動点に収束します。
これが反復アルゴリズムの正当性（correctness）と終了性（termination）を保証する数学的基盤です。
7.5 安全性と精度
// 保守的（conservative）分析：
// - 安全な側に近似
// - 最適化の機会を逃す可能性はあるが、誤った最適化は行わない
// 到達定義：実際より多くの定義が到達すると分析
// -> 定数伝播を適用できない場合が生じ得る（安全）
// 利用可能式：実際より少ない式が利用可能と分析
// -> 共通部分式除去を適用できない場合が生じる（安全）
8. 実用的考慮事項
8.1 ビットベクトル表現
データフロー値を**ビットベクトル**で表現すると効率的です：
// 定義d1, d2, d3, d4がある場合
// gen[B] = {d1, d3} -> ビットベクトル：1010
// kill[B] = {d2} -> ビットベクトル：0100
// 伝達関数の計算：
// OUT = gen | (IN & ~kill) （ビット演算で一度に処理）
ビット演算はハードウェアレベルで非常に高速なため、大規模プログラムでも効率的です。
8.2 ワークリストアルゴリズム
単純な反復の代わりに**ワークリスト**（worklist）アルゴリズムを使用するとより効率的です：
アルゴリズム：ワークリストベース反復
1. すべてのブロックをワークリストに追加
2. ワークリストが空でない間：
a. ブロックBをワークリストから取り出す
b. OUT[B]を再計算
c. OUT[B]が変更された場合、Bの後続者をワークリストに追加
変更されたブロックの影響を受けるブロックのみを再計算するため、不要な演算を減らします。
まとめ
| 概念 | 説明 |
| ---------------- | -------------------------------------------------- |
| 伝達関数 | 基本ブロックの入力情報を出力情報に変換 |
| gen/kill集合 | ブロックで生成/無効化されるデータフロー情報 |
| 合流演算 | 複数経路の情報を合わせる演算（和集合または積集合） |
| 到達定義 | 変数の定義が特定地点に到達するか分析 |
| 生存変数 | 変数の値がその後使用されるか分析 |
| 利用可能式 | 式が既に計算されて再利用可能か分析 |
| 反復アルゴリズム | データフロー方程式を不動点まで反復計算 |
| 束論 | データフロー分析の数学的基盤 |
データフロー分析はコンパイラ最適化の理論的基盤として、最適化の安全性を保証します。束論による数学的根拠があるため、反復アルゴリズムは必ず収束し、保守的に安全な結果を提供します。次の記事では、この分析技法を活用したループ最適化を詳しく扱います。
현재 단락 (1/198)
**データフロー分析**（Data-Flow Analysis）はコンパイラ最適化の核心的な基盤技術です。プログラムの各地点で特定の性質に関する情報を収集し、安全な最適化が可能かどうかを判断します。