データフロー解析

コンパイル最適化の前処理層:制御フローグラフ上でデータフローの事実を収束するまで反復伝播する。gen/kill/meet/worklist の同一フレームワークで、方向と meet 演算を変更するだけで、liveness、reaching defs、available expressions の3つの異なる問題を解くことができる。

概要

コンパイラは「プログラムの各地点で、どの変数が使用されており、どの定義がそこに到達し、どの式がすでに計算済みであるか」を知る必要がある。これらの情報は単一の命令からは得られず、制御フロー全体にわたって伝播されなければならない。⁠データフロー解析(data flow analysis) とは、プログラムの制御フローグラフ(CFG)上でデータフローの事実を反復伝播し、すべての地点で収束するまで処理を続ける手法である。

この問題を統一フレームワーク⁠(Kildall, 1973)として抽象化することで、同じ反復アルゴリズムの「方向」「meet 演算」「伝達関数」を変更するだけで、多様な解析問題を解くことができる。ここではこの統一フレームワークを解説し、その後に最も重要な3つの実例である reaching definitions、liveness、available expressions について詳しく述べる。これらは 古典的最適化 の直接的な前提知識でもある。

統一フレームワーク

データフロー解析の4つの構成要素:

• may 解析⁠(∪): 「何が可能か」を問う。過剰近似であり、過剰検出を許容して見落としを防ぐ。reaching definitions は may 解析である:ある定義が某地点に「到達する可能性がある」。
• must 解析⁠(∩): 「何が確実に言えるか」を問う。不足近似であり、誤検出を許容して見逃しを防ぐ。available expressions は must 解析である:ある式が「確実に計算済みである」。

伝達関数は通常、以下の式で表される:out[B] = gen[B] ∪ (in[B] - kill[B])(または meet に応じて ∪ の代わりに ∩ を使用)。ここで、gen はそのブロック内で「生成」される新しい事実、kill はそのブロック内で「無効化」される古い事実を指す。

反復求解: worklist アルゴリズム

CFG 全体を安定(不動点)に達するまで繰り返し走査する:

for each block B: out[B] = ∅ (または top)
worklist = all blocks
while worklist not empty:
    B = worklist.pop()
    in[B] = meet(out[predecessors of B])
    old_out = out[B]
    out[B] = gen[B] ∪ (in[B] - kill[B])     ← 伝達関数
    if out[B] changed:
        worklist.push(successors of B)        ← 変化した部分のみ伝播

終了性は、以下の2つの条件によって保証される:⁠格(lattice)の高さが有限⁠(事実集合に最大要素が存在する)かつ伝達関数が単調⁠(新しい in から導かれる新しい out が、古い値より小さくなることはない)——不動点定理。実用的な CFG においては、収束は非常に速い(通常 3〜5 回の反復で完了する)。

worklist のソート順序は収束速度に影響を与える。ランダムな順序よりも、前駆ノードがすでに更新されているノードを先に処理する(CFG のトポロジカル順序で近似する)方が効率的である。

三大古典的解析

Reaching Definitions (前方, may, ∪)

問題⁠: プログラム地点 p において、後続の代入によって上書きされずに p に到達する可能性がある代入(definition)は何か？

gen[B]:  本ブロック内で最後に変数 x に代入を行う文 (それ以前の代入は後の代入によって上書きされる)
kill[B]: 本ブロック内の新しい代入によって「殺される」、他の場所での x へのすべての代入

use-def 連鎖の構築の基礎となる。SSA 形式 が導入されると、reaching definitions は SSA IR 上では疎になり、反復求解は不要になるが、通常の IR 上では依然として必須である。

Liveness (後方, may, ∪)

問題⁠: プログラム地点 p において、変数 x の値は将来使用されるか(次の代入の前に使用されるか)？

方向を backward に変更:アウトプットから前駆ノードへ伝播
gen[B]:  本ブロック内で「使用」されるが、本ブロック内で「再定義」されていない変数
kill[B]: 本ブロック内で「再定義」されるが、その定義前に本ブロック内で「使用」されていない変数 (新しい値が古い値を上書きする)

liveness 解析はレジスタ割り当てを直接決定する:2つの変数が同時に活発でなければ、同じレジスタを共有できる⁠( レジスタ割り当て を参照)。これはコンパイル最適化において最も頻繁に行われる解析である。

Available Expressions (前方, must, ∩)

問題⁠: プログラム地点 p において、式 x + y は確実に計算済みであり、かつ x と y のいずれも再代入されていないか？

gen[B]:  本ブロック内で計算された式 (かつその後 x/y が再定義されていない)
kill[B]: 本ブロック内で x または y への代入が行われた後、x または y を含むすべての式が無効化される
meet:   ∩ (must)——ブロックの入り口での利用可能式 = 全前駆ノードの出力の共通部分

available expressions の情報は CSE(共通部分式除去) に直接利用される。もし x + y が現在の地点で利用可能であれば、再計算せずに以前の結果を使用する。

MOP vs MFP: 理想解と不動点解のギャップ

• MOP(Meet Over all Paths): プログラム地点 p について、「p に到達するすべての可能なパスが運ぶ事実」を集め、それらに対して meet を実行する。これが理想解である。
• MFP(Maximal Fixed Point): 反復不動点アルゴリズムによって得られる解。MFP ≤ MOP(格の順序において、MFP はより保守的になり得る)。

分配可能(distributive)な伝達関数⁠、つまり f(a meet b) == f(a) meet f(b) を満たす関数の場合、MFP = MOP となり、不動点が理想解となる。reaching definitions と liveness の伝達関数は分配可能であるが、定数伝播(constant propagation)の伝達関数は分配可能ではないため、MFP は MOP よりも保守的になる。

SSA における疎データフロー

SSA 形式 において、全体の反復不動点フレームワークは大幅に簡素化される:

• 各変数は1回だけ定義されるため → reaching definition は「その使用に対応する定義がどこにあるか」(直接的な def-use 連鎖、解析不要) に退化する。
• liveness は def-use グラフ上で実行できる——各定義地点から到達可能なすべての使用地点がその live range であり、CFG 全体での反復は不要。
• 「CFG 全体に事実を伝播する」多くの pass は、SSA では「dominator tree 上での単一パス伝播」に退化する。

これこそが、SSA が「疎解析(sparse analysis)」と呼ばれる理由である——データフローの事実は CFG のすべての辺ではなく、def と use の地点にのみ付随する。

参考文献

• Kildall (1973): "A Unified Approach to Global Program Optimization" — データフロー解析の統一フレームワーク
• Dragon Book: Chapter 9, Machine-Independent Optimizations — 完全な gen/kill テーブルと不動点アルゴリズムを含む
• Cooper/Torczon: "Engineering a Compiler", Chapters 8–10

Keywords: data flow analysis, gen/kill, meet operator, forward/backward, may/must, reaching definitions, liveness, available expressions, fixed-point iteration, worklist algorithm, lattice, monotonicity, MOP, MFP, distributive function, sparse analysis, SSA