データフロー解析

コンパイラ最適化の前処理層:制御フローグラフ上でデータフローの事実を収束するまで反復伝播する。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 のトポロジカル順序で近似する)方が、ランダムに処理するよりも効率的である。

3つの古典的解析

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 analysis)はレジスタ割り当てを直接決定する: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