データフロー分析

反復法が実用的であるためには、実際に不動点に到達する必要があります。これは、状態の値域、伝達関数、および結合演算の組み合わせに制約を課すことで保証できます。

値領域は有限の高さを持つ半順序である必要があります（つまり、無限に上昇する連鎖はありません）。${\displaystyle x_{1}}$<${\displaystyle x_{2}}$< ...)。伝達関数と結合操作の組み合わせは、この半順序に関して単調である必要があります。単調性により、各反復で値は同じか大きくなるかのどちらかになり、有限の高さにより無限に大きくなることはありません。したがって、最終的にはすべての x に対して T(x) = x となる状況に到達し、これが不動点となります。

上記のアルゴリズムは、先行するブロックの出力状態が変化しない限り、そのブロックの入力状態も変化しないことに着目することで容易に改善できます。そこで、処理待ちのブロックのリストであるワークリストを導入します。ブロックの出力状態が変化するたびに、そのブロックの後続ブロックをワークリストに追加します。各イテレーションでは、ワークリストからブロックが1つ削除され、その出力状態が計算されます。出力状態が変化した場合は、そのブロックの後続ブロックがワークリストに追加されます。効率化のため、ブロックはワークリストに複数回含まれないようにする必要があります。

このアルゴリズムは、情報生成ブロックをワークリストに追加することから開始され、ワー​​クリストが空になった時点で終了します。

データフロー方程式を反復的に解く効率は、ローカルノードを訪問する順序によって左右されます。^{[ 9 ]}さらに、データフロー方程式がCFG上の順方向データフロー解析に使用されるか逆方向データフロー解析に使用されるかによっても異なります。直感的には、順方向フロー問題では、ブロック自体の前にすべての先行ブロックが処理されている場合が最も高速です。なぜなら、その場合、反復処理は最新の情報を使用するからです。ループがない場合、各ブロックを一度だけ処理することで正しい出力状態が計算されるようにブロックを順序付けることができます。

以下では、データフロー方程式を解くためのいくつかの反復順序について説明します（CFGの反復順序に関連する概念として、ツリーの ツリー走査があります）。

• ランダムな順序- この反復順序では、データフロー方程式が順方向のデータフロー問題を解くのか、逆方向のデータフロー問題を解くのかを認識しません。そのため、専用の反復順序と比較すると、パフォーマンスは比較的劣ります。
• 後順走査- これは、後方データフロー問題における典型的な反復順序です。後順走査では、すべての後続ノードが訪問された後に、そのノードが訪問されます。通常、後順走査は深さ優先探索戦略で実装されます。
• 逆後順- これは、順方向データフロー問題における典型的な反復順序です。逆後順反復では、後続ノードがバックエッジによって到達される場合を除き、後続ノードが訪問される前に、そのノードが訪問されます。（逆後順は前順とは異なることに注意してください。）

初期状態は、正確で精度の高い結果を得るために重要です。コンパイラの最適化に結果を使用する場合、結果は保守的な情報を提供する必要があります。つまり、情報を適用してもプログラムのセマンティクスは変更されません。不動点アルゴリズムの反復では、値は最大要素の方向に取られます。したがって、すべてのブロックを最大要素で初期化しても意味がありません。少なくとも1つのブロックは、最大値より小さい値を持つ状態から始まります。詳細はデータフロー問題によって異なります。最小要素が完全に保守的な情報を表す場合、データフローの反復中でも結果を安全に使用できます。最小要素が最も正確な情報を表す場合は、結果を適用する前に不動点に到達する必要があります。

到達定義分析は、各プログラムポイントについて、そのプログラムポイントに到達する可能性のある定義のセットを計算します。

 b == 4 の場合  a = 5;  それ以外  a = 3;  endif  a < 4 の場合  ... 

7行目における変数の到達定義は、 2行目と4行目におけるa代入の集合である。a = 5a = 3

ライブ変数分析は、各プログラムポイントについて、次の書き込み更新前に読み込まれる可能性のある変数を計算します。この結果は通常、 デッドコード削除において、その後使用されない値に代入するステートメントを削除するために使用されます。

ブロックのイン状態とは、ブロックの開始時点で有効な変数の集合です。転送関数が適用され、実際の変数値が計算される前に、ブロック内で有効な（含まれている）すべての変数が初期状態で含まれます。ステートメントの転送関数は、このブロック内で記述された変数を消去する（有効な変数の集合から削除する）ことによって適用されます。ブロックのアウト状態とは、ブロックの終了時点で有効な変数の集合であり、ブロックの後続のイン状態の和集合によって計算されます。

初期コード:

逆算分析：

b3 の入力状態には、 cが書き込まれているため、bとdのみが含まれます。b1 の出力状態は、b2 と b3 の入力状態の和集合です。c はステートメントの直後には生存していないため、 b2におけるcの定義は削除できます。

データフロー方程式の解法は、まずすべての入力状態と出力状態を空集合に初期化することから始まります。ワークリストは、出口点（b3）をワークリストに挿入することで初期化されます（これは逆フローの場合によく見られます）。計算された入力状態は前のものと異なるため、その前の入力状態b1とb2が挿入され、処理が続行されます。処理の進行状況は、以下の表にまとめられています。

b1がb2より先にリストに入力されたため、b1が2回処理されることになった（b1がb2の先行要素として再入力された）。b2をb1より前に挿入していれば、処理をより早く完了できたはずだ。

空集合で初期化することは楽観的初期化です。つまり、すべての変数は最初は「デッド」状態になります。出力状態は入力状態よりも小さくなる可能性はありますが、1回の反復で出力状態が縮小することはないことに注意してください。これは、最初の反復以降、出力状態は入力状態の変化によってのみ変化するという事実からわかります。入力状態は空集合から始まるため、それ以降の反復では大きくなるしかありません。

上記の例は、データフローの値が集合である問題です。たとえば、到達定義の集合（プログラム内の定義位置を表すビットを使用）や、生存変数の集合などです。これらの集合は、各ビットが特定の要素の集合メンバーシップを表すビットベクトルとして効率的に表現できます。この表現を使用すると、結合関数と転送関数をビット単位の論理演算として実装できます。結合演算は通常、和集合または積集合であり、ビット単位の論理ORと論理ANDで実装されます。各ブロックの転送関数は、いわゆるgen集合とkill集合に分解できます。

例えば、ライブ変数解析では、結合演算はユニオンです。キルセットはブロック内で書き込まれる変数のセットであり、ゲンセットは最初に書き込まれることなく読み込まれる変数のセットです。データフロー方程式は次のようになります。

${\displaystyle out_{b}=\bigcup _{s\in succ_{b}}in_{s}}$

${\displaystyle in_{b}=(out_{b}-kill_{b})\cup gen_{b}}$

論理演算では、これは次のように読みます。

out( b ) = 0 for s in succ( b ) out( b ) = out( b )またはin( s ) in( b ) = (out( b ) and not kill( b )) or gen( b )

データフロー値の集合をビットベクトルとして表現できるデータフロー問題は、ビットベクトル問題、gen-kill問題、または局所的に分離可能な問題と呼ばれます。^{[ 13 ]}このような問題には、一般的な多項式時間解があります。^{[ 14 ]}

上記の到達定義と生存変数の問題に加えて、次の問題はビットベクトル問題の例です。^{[ 14 ]}

• 使用可能な表現
• 非常に忙しい表情
• 使用定義チェーン

手続き間有限部分集合問題またはIFDS問題は、一般的な多項式時間解を持つ別のクラスの問題です。^{[ 13 ] [ 15 ]}これらの問題の解は、コンテキスト依存およびフロー依存のデータフロー分析を提供します。

IFDS ベースのデータフロー分析は、一般的なプログラミング言語向けにいくつか実装されており、例えばJava 分析用のSoot ^{[ 16 ]}や WALA ^{[ 17 ]フレームワークなどがあります。}

ビットベクトルに関する問題はすべてIFDS問題でもあるが、真に生存している変数や初期化されていない可能性のある変数など、ビットベクトル問題ではない重要なIFDS問題がいくつか存在する。