データフロー解析

データフロー解析（）は、プログラム内の様々な位置で、取りうる値の集合に関する情報を収集する技法である。制御フローグラフ (CFG) を使って変数の値が伝播するかどうかなどの情報を集め、利用する。このようにして集められた情報はコンパイラが最適化に利用する。データフロー解析の基本は到達定義 (reaching definition) である。
あるプログラムのデータフロー解析を行う単純な方法は、制御フローグラフの各ノードについてデータフロー方程式を設定し、全体として安定した状態、すなわち不動点に到達するまで、それらの式を繰り返し計算していく。完了することを保証するためには、不動点データフロー解析に基づくデータフロー方程式が必要である。すなわち、各式のローカルな更新は単調である。この技法の基本はゲイリー・キルドールが海軍大学院で教えていたころに開発したものである。
繰り返しアルゴリズム.
データフロー方程式の不動点は「ラウンドロビン繰り返しアルゴリズム」を使って計算できる。
順序問題.
データフロー方程式の繰り返し計算の効率は、ノード群を訪れる順序に影響される。上記のラウンドロビン繰り返しアルゴリズムでは、ノードの計算順序である番号の付与がどうなるかが影響する。さらに制御フローグラフに対してデータフロー方程式が前方解析されるのか後方解析されるのかも影響する。以下では、データフロー方程式を解く繰り返し順序について若干解説している。制御フローグラフの繰り返し順序と似た概念として、木構造の走査がある。
例.
以下に、データフロー解析でコンピュータプログラムの特性を計算する例を示す。データフロー解析で計算された特性は、実際の特性の単なる近似である点に注意されたい。これは、データフロー解析がプログラムの制御フローを正確にシミュレートしているわけではなく、CFG の構造をなぞっているだけだからである。しかし近似であっても最適化という観点では有効である。
前方解析.
変数 "a" の7行目における到達定義は、行番号集合 {2, 4} である。
後方解析.
行番号 2 における生存変数の集合は {a, b} だが、行番号 1 における生存変数の集合は {a} だけである。なんとなれば、変数 "b" は行番号 2 で更新されるからである。
sensitivity（感度）.
データフロー解析は本質的にフローに関するもの (flow-sensitive) である。データフロー解析では一般に経路は考慮されない (path-insensitive) が、経路解析に使えるようなデータフロー方程式を定義することも可能である。なお、以下の用語はデータフロー解析特有のものではない。