データフロー解析とプログラム最適化

データフロー解析が答える問い

コンパイラ最適化は「この変換をしても観測可能な振る舞いが変わらない」という保証の上でしか実行できません。たとえば y = x + 1 の x を定数 5 に置き換えてよいか、ある代入が一度も使われず削除できるか——これらの判断には、各プログラム点で「何が成り立っているか」を知る必要があります。**データフロー解析（data-flow analysis）**は、この種の大域的な事実を制御フローグラフ（CFG）上で機械的に求める枠組みです。

解析の舞台は中間表現のCFGです。各基本ブロックを節点、制御の流れを辺とし、各点に「事実集合」を割り当てます。代表的な解析は次の三つで、いずれも同じ数学的骨格を共有します。

到達定義 — gen と kill の前向き伝播

**到達定義（reaching definitions）**は「あるプログラム点 p に、どの代入文（定義）の値が再代入されずに届きうるか」を集めます。基本ブロック B に対し二つの集合を用意します。gen[B] は B 内で生成され末尾まで生き残る定義、kill[B] は B 内の再代入によって無効化される他所の定義です。点ごとの事実 IN[B]・OUT[B] は次の方程式を満たします。

IN[B]  = ∪ OUT[P]   （P は B の全先行ブロック）
OUT[B] = gen[B] ∪ (IN[B] − kill[B])

前向き解析なので、先行ブロックの OUT を合流（ここでは和集合）して IN を作り、転送関数 gen ∪ (IN − kill) で OUT へ進みます。和集合を取るのは「いずれかの経路で届きうる」を漏れなく拾うmay解析だからです。すべての IN/OUT を空集合で初期化し、変化がなくなるまで全ブロックを反復更新すると、最小固定点に収束します。

到達定義が一意（各使用にちょうど一つの定義が届く）と分かれば、その値を使用箇所へ直接伝播できます。この性質を表現自体に焼き込んだのがSSA形式で、到達定義解析を不要にする狙いがあります。

生存変数 — 後ろ向きの may 解析

**生存変数（live variables）**解析は「点 p の直後で保持している変数のうち、将来の経路で再代入される前に使われるものはどれか」を求めます。値が将来使われない変数は生存しておらず、その代入は不要コードとして削除でき、レジスタ割り当てでは生存区間が重ならない変数を同じレジスタへ載せられます。

生存変数は後ろ向き解析です。情報は使用箇所から定義側へ遡って伝播するため、後続ブロックの IN を合流して OUT を作ります。

OUT[B] = ∪ IN[S]   （S は B の全後続ブロック）
IN[B]  = use[B] ∪ (OUT[B] − def[B])

use[B] は B 内で再代入前に読まれる変数、def[B] は B 内で代入される変数です。「将来のどれかの経路で使われる」を拾うので、ここでも合流は和集合（may）になります。出口ブロックの OUT を空集合（または手続きの戻り値など外部から見える変数）で初期化し、固定点まで反復します。

半束上の固定点反復として定式化する

これら個別の解析は、半束（semilattice）上の単調関数の固定点という単一の理論に統合できます。事実集合の全体が半束 L をなし、合流演算 ⊓（meet。和集合解析なら集合の和、積集合解析なら積）が定義されます。各ブロックの転送関数 f_B: L → L は単調、すなわち x ⊑ y なら f_B(x) ⊑ f_B(y) を満たします。

解の正体は、CFG 全体の方程式系を満たす固定点です。複数ある固定点のうち、可能な限り情報量の多い（精度の高い）ものを採るため、最も情報の多い最上元 ⊤ から出発して反復します。この向き付けでは反復は格子を下向きに進み、得られる解は格子順序で最大の MFP（Maximum Fixed Point）解になります。注意したいのは ⊤ の正体が解析ごとに異なる点です。到達定義や生存変数のような和集合（may）解析では、格子を逆向きの集合包含で順序付けるため最上元は空集合であり、先の節で「空集合で初期化して最小固定点（＝最小の集合）に収束」と述べたのと同じ手続きを指します。**ワークリスト法（worklist algorithm）**が標準的な解法です。

全ブロックの OUT を ⊤（最も情報の多い初期値）に設定
worklist ← 全ブロック
while worklist が空でない:
    B ← worklist から1つ取り出す
    IN[B]  ← ⊓ {OUT[P] | P は B の先行}
    new    ← f_B(IN[B])
    if new ≠ OUT[B]:
        OUT[B] ← new
        worklist に B の後続を追加

MOP 解と反復解 — 分配律が橋渡しする

理論上の理想は MOP（Meet Over all Paths）解、すなわち入口から各点へ至るあらゆる経路で転送関数を合成し、その結果をすべて合流したものです。これは経路ごとに転送関数を厳密に畳んでから合流する最精密な解に対応します（ただしCFG上の全経路を対象とするため、分岐条件のせいで実行時には決して通らない経路も含む点で、真に到達可能な経路だけを畳む理想解よりは保守的です）。しかし経路数は分岐とループで指数的・無限になりうるため、直接は計算できません。

そこで実際に計算するのが、前節のブロック単位の反復で得られるMFP（Maximum Fixed Point）解です。一般に MFP は MOP より精度が落ちますが（合流を経路ごとではなくブロック境界で先に行うため）、転送関数が分配律 f(x ⊓ y) = f(x) ⊓ f(y) を満たす枠組みでは両者が一致します。到達定義・生存変数のような gen/kill 形式の解析（gen-kill問題）は分配的なので、反復で得た解がそのまま最精密解になります。定数伝播のように分配律が崩れる解析では MFP が安全側に保守化し、これが「最適化は安全だが時に控えめ」という挙動の理論的な出所です。

使用-定義連鎖と最適化への接続

到達定義と生存変数が揃うと、**使用-定義連鎖（use-def chain）とその逆の定義-使用連鎖（def-use chain）**を構築できます。ある変数の使用に対し「到達しうる定義の集合」を結ぶのが使用-定義連鎖で、これが多くの最適化の直接の入力になります。

たとえば不要コード除去は、定義 x = expr の後で x が一切生存しないなら（生存変数解析で確認）、その代入を安全に削除します。削除でさらに別の変数が不要になりうるため、ワークリストで連鎖的に刈り取ります。これらの最適化が「観測可能な振る舞いを保つ」と言い切れるのは、データフロー解析が保守的近似——実際より広めに事実を見積もり、危ない変換を決して許さない——を返すからです。

まとめ

データフロー解析は、各プログラム点で成り立つ事実をCFG上で伝播させ、半束上の単調な転送関数の固定点として求める枠組みです。到達定義は gen/kill の前向き和解析、生存変数は後ろ向き和解析で、両者から使用-定義連鎖が得られます。格子の有限高と転送関数の単調性が反復の停止を保証し、gen-kill 問題の分配律により反復解（MFP）は最精密解（MOP）に一致します。定数伝播・不要コード除去・共通部分式除去といったコンパイラ最適化は、この解析が返す保守的な近似を入力とすることで安全性を担保しています。データフロー解析は、最適化が「効く」根拠そのものを与える基盤理論です。