データフロー解析

データフロー解析（英: Data-flow analysis）は、プログラム内の様々な位置で、取りうる値の集合に関する情報を収集する技法である。制御フローグラフ (CFG) を使って変数の値が伝播するかどうかなどの情報を集め、利用する。このようにして集められた情報はコンパイラが最適化に利用する。データフロー解析の基本は到達定義 (reaching definition) である。

あるプログラムのデータフロー解析を行う単純な方法は、制御フローグラフの各ノードについてデータフロー方程式を設定し、全体として安定した状態、すなわち不動点に到達するまで、それらの式を繰り返し計算していく。完了することを保証するためには、不動点データフロー解析に基づくデータフロー方程式が必要である。すなわち、各式のローカルな更新は単調である。この技法の基本はゲイリー・キルドールが海軍大学院で教えていたころに開発したものである^[1]。

繰り返しアルゴリズム

データフロー方程式の不動点は「ラウンドロビン繰り返しアルゴリズム」を使って計算できる。

    for i ← 1 to N
         ノード i を初期化
    while (集合がまだ変化している)
         for i ← 1 to N
              ノード i における集合を再計算

順序問題

データフロー方程式の繰り返し計算の効率は、ノード群を訪れる順序に影響される。上記のラウンドロビン繰り返しアルゴリズムでは、ノードの計算順序である番号の付与がどうなるかが影響する。さらに制御フローグラフに対してデータフロー方程式が前方解析されるのか後方解析されるのかも影響する。以下では、データフロー方程式を解く繰り返し順序について若干解説している。制御フローグラフの繰り返し順序と似た概念として、木構造の走査がある。

無作為順序 (random order): 順序を気にせずにデータフロー方程式を解いていく。性能は他に比較すると低い。
後行順（帰りがけ順） (postorder): 後方データフロー問題で一般的な繰り返し順序。木構造で言えば、子ノードを全て訪れてから親ノードを訪れる順序に相当する。一般に深さ優先戦略の一部として実装される。
逆後行順 (reverse postorder): 前方データフロー問題で一般的な繰り返し順序。後行順のほぼ逆の動きだが、先行順 (preorder) とは異なる。

例

以下に、データフロー解析でコンピュータプログラムの特性を計算する例を示す。データフロー解析で計算された特性は、実際の特性の単なる近似である点に注意されたい。これは、データフロー解析がプログラムの制御フローを正確にシミュレートしているわけではなく、CFG の構造をなぞっているだけだからである。しかし近似であっても最適化という観点では有効である。

前方解析

到達定義: 到達定義解析では、プログラムの各点について、そこに到達する可能性のある定義の集合を計算する。

1: if b==4 then
2:    a = 5;
3: else 
4:    a = 3;
5: endif
6:
7: if  a < 4 then
8:    ...

変数 "a" の7行目における到達定義は、行番号集合 {2, 4} である。

後方解析

生存変数 (live variables): 生存変数解析では、プログラムの各点で変数が次に更新される前に読み取られる可能性があるかどうかを計算する。

1: a = 3;
2: b = 5;
3: c = a + b;

行番号 2 における生存変数の集合は {a, b} だが、行番号 1 における生存変数の集合は {a} だけである。なんとなれば、変数 "b" は行番号 2 で更新されるからである。

sensitivity（感度）

データフロー解析は本質的にフローに関するもの (flow-sensitive) である。データフロー解析では一般に経路は考慮されない (path-insensitive) が、経路解析に使えるようなデータフロー方程式を定義することも可能である。なお、以下の用語はデータフロー解析特有のものではない。

flow-sensitive: プログラムの文の順序を考慮する。例えば、flow-insensitive なポインタ・エイリアス解析は「変数 x と y は同じ位置を参照するかもしれない」と判断するとしたら、flow-sensitive なポインタ・エイリアス解析は「行番号 20 の後で、変数 x と y は同じ位置を参照するかもしれない」と判断する。
path-sensitive: 条件分岐命令における条件判断に関わる情報を解析する。例えば、条件分岐の条件が x>0 の場合、そのまま分岐しないで処理を続行する場合は x≤0 であり、分岐した場合は x>0 となっていると判断できる。
context-sensitive: プロシージャ間解析の一部であり、関数コールの解析にあたってそれを呼び出した側のコンテキストを考慮する。特に、そのような情報を使えば呼び出し側に戻ることが可能となるが、context-sensitive でない場合は関数を呼び出している箇所全てに解析情報が伝播することになって、精度が失われる。

脚注

^ Kildall, Gary (1973年). “A Unified Approach to Global Program Optimization”. Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages 2006年11月20日閲覧。.

参考文献

Aho, Alfred V. Sethi, Ravi. Ullman, Jeffrey D. Compilers: Principles, Techniques and Tools. Addison Wesley. 1986.
Appel, Andrew W. Modern Compiler Implementation in ML. Cambridge University Press. 1999.
Cooper, Keith D. and Torczon, Linda. Engineering a Compiler. Morgan Kaufmann. 2005.
Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann. 1997.
Hecht, Matthew S. Flow Analysis of Computer Programs. Elsevier North-Holland Inc. 1977.

[1] Kildall, Gary (1973年). “A Unified Approach to Global Program Optimization”. Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages 2006年11月20日閲覧。.

[1]