#112 Data Flow Analysis
コンパイラは、実行ファイルを最適化するために、プログラムの無駄な部分を削ぎ落としたり、効率の良い処理に書き換えます。その際、プログラムの分析が行われますが、そこで使われる技術の一つがデータフロー解析です。プログラムのある地点での変数の取りうる値や、値がどのように伝搬していくかの情報を集めて、最適化に活用します。こういった情報は、プログラムのバグを見つけるのにも有効で、例えば、0で除算が行われる可能性のある箇所を探し出すことなどができます。
セキュリティの観点からみて、ロジック系のバグを解析する上でも有効な技術であると思って、ちょっと調べてみました。
GCCにおけるデータフロー解析
GCCは、C/C++をはじめとした様々な言語のコンパイラ群で、Linuxでは標準的に使われているOSSです。歴史も長く、信頼性も高いコンパイラなので、どのようにデータフロー解析を行って最適化を行っているのか、のぞいてみました。
ソースコードは、最新のgcc-13.2.0を落としてきました。
gcc/df-core.ccにデータフロー解析の核となる処理が書かれています。コメントを読んでみると、複数のデータフロー問題に対処する処理がgcc/df-problems.ccに記述されていることがわかりました。
The file df-problems.cc provides problem instance for the most common
dataflow problems: reaching defs, upward exposed uses, live variables,
uninitialized variables, def-use chains, and use-def chains.1 到達可能定義（reaching defs）
ある地点で変数が取りうる値の集合を調べて、処理が到達可能かを分析します。例えば、以下のような処理があるとします。
a = 1; // def1
a = 2; // def2
b = a; // def3この場合、def1はdef2で上書きされてしまうので、def3に到達することはありえません。逆に、def3からみてdef1は到達不可能です。このようにして、各定義がどのような値を取れるかを分析していきます。
2 到達可能使用（upward exposed uses, reachable uses）
処理のなかで使用されない定義や到達しえないパスは、削除することができます。
a = 2;
b = 2;
if (True) {
a = 10;
} else {
b = 10;
}このとき、elseの処理が実行されることはありえないので、以下のように置き換えることができるでしょう。
b = 2;
a = 10;3 生存変数（live variables）
変数がどの範囲で有効かを分析します。
a = 1; // 変数なし
b = 2; // { a }が有効
c = 3; // { a, b }が有効
d = a + b; // { a, b }が有効。cは一度も使われないので、無効。上の例で、c変数は処理の中で使用されていないので、必要のない定義であると判定できます。 すると、下記の通り置き換えられます。
a = 1;
b = 2;
d = a + b;4 未初期化変数（uninitialized variables）
生存変数と似たアプローチで、初期化されていない変数の使用を分析できます。
a;
b = 2;
c = a + b; // aは未定義！この場合はどう最適化するんでしょうか？コンパイルエラーは出せそうですが… もうちょっと調査が必要そうです。
5 DUチェーン/UDチェーン（def-use chains / use-def chains）
ある変数の定義が使用されている範囲に関する分析です。
a = 1; // a1の定義
b = a + 1; // a1の使用
a = 100; // a2の定義
c = a * 10; // a2の使用このとき、a1とa2は別の変数として定義しても処理に支障はありません。
x = 1;
b = x + 1;
y = 100;
c = y * 10;処理の見通しは良くなりますが、これがどう最適化に寄与するのかわかりません…
まとめ
データフロー解析について探るべく、GCCを参考に調査しました。理解できない部分も多く、もう少し解析の理論について踏み込んで学ぶ必要がありそうです。GCCのように、実際にアルゴリズムとして実装されている部分も参考に、さらに理解を深めていきます！
つらそうだけど、自分でツール作ってみるのが早いかなぁ〜。
EOF