データフロー分析

データフロー解析は、コンピュータ プログラムのさまざまなポイントで計算される可能性のある値のセットに関する情報を収集する手法です。プログラムの制御フロー グラフ(CFG) は、変数に割り当てられた特定の値が伝播する可能性のあるプログラムの部分を決定するために使用されます。収集された情報は、プログラムを最適化するときにコンパイラによってよく使用されます。データフロー解析の標準的な例は、定義への到達です。

プログラムのデータフロー解析を実行する簡単な方法は、制御フローグラフの各ノードに対してデータフロー方程式を設定し、システム全体が安定するまで、つまり固定点に到達するまで、各ノードで入力からの出力をローカルに繰り返し計算して方程式を解くことです。この一般的なアプローチはキルドール法としても知られ、海軍大学院で教鞭をとっていたゲイリー・キルドールによって開発されました。^{[1] [2] [3] [4]}

データフロー解析は、プログラム内で変数がどのように定義され、使用されているかに関する情報を収集するプロセスです。プロシージャ内の各ポイントで特定の情報を取得しようとします。通常、基本ブロックの境界でこの情報を取得すれば十分です。基本ブロック内のポイントで情報を計算するのは簡単なためです。フォワードフロー解析では、ブロックの終了状態はブロックのエントリ状態の関数です。この関数は、ブロック内のステートメントの効果の組み合わせです。ブロックのエントリ状態は、その前のブロックの終了状態の関数です。これにより、一連のデータフロー方程式が生成されます。

各ブロックbについて:

${\displaystyle out_{b}=trans_{b}(in_{b})}$

${\displaystyle in_{b}=join_{p\in pred_{b}}(out_{p})}$

ここで、はブロック の転送関数です。これはエントリ状態 に作用し、終了状態 を生成します。結合操作はの先行する終了状態を結合し、エントリ状態 を生成します。 ${\displaystyle trans_{b}}$${\displaystyle b}$${\displaystyle in_{b}}$${\displaystyle out_{b}}$ ${\displaystyle join}$${\displaystyle p\in pred_{b}}$${\displaystyle b}$${\displaystyle b}$

この一連の方程式を解いた後、ブロックの入口および/または出口の状態を使用して、ブロック境界でのプログラムのプロパティを導出できます。各ステートメントの伝達関数を個別に適用して、基本ブロック内のポイントの情報を取得できます。

各データフロー解析には、それぞれ固有の転送関数と結合操作があります。一部のデータフロー問題では、逆方向フロー解析が必要です。これは同じ計画に従いますが、転送関数が終了状態に適用されてエントリ状態が生成され、結合操作が後続のエントリ状態に適用されて終了状態が生成されます。

エントリポイント(順方向フロー) は重要な役割を果たします。エントリ ポイントには先行処理がないため、エントリ状態は分析の開始時に明確に定義されます。たとえば、既知の値を持つローカル変数のセットは空です。制御フロー グラフにサイクルが含まれていない場合 (手順に明示的または暗黙的なループがない場合)、方程式を解くのは簡単です。制御フロー グラフは、トポロジカルにソートできます。このソートの順序で実行すると、各ブロックの開始時にエントリ状態を計算できます。そのブロックのすべての先行処理がすでに処理されているため、その終了状態を利用できます。制御フロー グラフにサイクルが含まれている場合は、より高度なアルゴリズムが必要です。

データフロー方程式を解く最も一般的な方法は、反復アルゴリズムを使用することです。これは、各ブロックの in-state の近似値から始まります。次に、in-state に伝達関数を適用して、out-state を計算します。これらから、join 操作を適用して in-state を更新します。最後の 2 つのステップは、in-state (および結果的に out-state) が変化しない状況である、いわゆる固定点に到達するまで繰り返されます。

データフロー方程式を解くための基本的なアルゴリズムは、ラウンドロビン反復アルゴリズムです。

i ← 1 からNまで

ノードiを初期化する

(セットはまだ変更中です)

i ← 1 からNまで

ノード i のセットを再計算する

反復アプローチが使用可能になるには、実際に固定点に到達する必要があります。これは、状態の値ドメイン、伝達関数、および結合操作の組み合わせに制約を課すことによって保証できます。

値ドメインは、有限の高さを持つ半順序である必要があります (つまり、無限の昇順チェーン< < ...はありません)。転送関数と結合操作の組み合わせは、この半順序に関して単調である必要があります。単調性により、各反復で値が同じままであるか、大きくなることが保証されますが、有限の高さにより、値が無制限に大きくなることはありません。したがって、最終的には、すべての x に対して T(x) = x という状況に到達し、これが固定点になります。 ${\displaystyle x_{1}}$${\displaystyle x_{2}}$

ブロックのイン状態は、その前のブロックのアウト状態が変わらない限り変わらないことに注意すれば、上記のアルゴリズムを簡単に改善できます。したがって、まだ処理が必要なブロックのリストである作業リストを導入します。ブロックのアウト状態が変わるたびに、その後続のブロックを作業リストに追加します。各反復で、ブロックは作業リストから削除されます。そのアウト状態が計算されます。アウト状態が変わると、ブロックの後続のブロックが作業リストに追加されます。効率を上げるために、ブロックは作業リストに複数回存在すべきではありません。

アルゴリズムは、情報生成ブロックを作業リストに入れることによって開始されます。作業リストが空になると終了します。

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

以下では、データフロー方程式を解くためのいくつかの反復順序について説明します ( CFGの反復順序に関連する概念は、ツリーの ツリートラバーサルです)。

• ランダム順序- この反復順序では、データフロー方程式が順方向または逆方向のデータフロー問題を解決するかどうかは考慮されません。そのため、特殊な反復順序と比較すると、パフォーマンスは比較的低くなります。
• ポストオーダー- これは、逆方向データフロー問題の典型的な反復順序です。ポストオーダー反復では、すべての後続ノードが訪問された後に、ノードが訪問されます。通常、ポストオーダー反復は深さ優先戦略で実装されます。
• 逆後順序- これは、順方向データフロー問題の一般的な反復順序です。逆後順序反復では、バックエッジによって後続ノードに到達する場合を除き、後続ノードのいずれかが訪問される前にノードが訪問されます。(逆後順序は事前順序と同じではないことに注意してください。)

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

以下は、データフロー解析によって計算できるコンピュータ プログラムの特性の例です。データフロー解析によって計算される特性は、通常、実際の特性の近似値にすぎないことに注意してください。これは、データフロー解析が、プログラムの正確な制御フローをシミュレートせずに、CFG の構文構造に基づいて動作するためです。ただし、実際に役立つように、データフロー解析アルゴリズムは通常、実際のプログラム特性の上限近似値と下限近似値を計算するように設計されています。

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

  b == 4の場合
     a = 5;
  それ以外 
     a = 3;
  終了
 
  a < 4 ならば
     ...

7 行目の変数の到達定義は、2 行目と4 行目のa割り当てのセットです。 a = 5a = 3

ライブ変数分析は、各プログラム ポイントについて、次回の書き込み更新の前に後で読み取られる可能性のある変数を計算します。結果は通常、 デッド コード除去によって使用され、後で値が使用されない変数に割り当てるステートメントを削除します。

ブロックの in-state は、ブロックの開始時に有効な変数のセットです。転送関数が適用され、実際に含まれる値が計算される前に、ブロック内で有効な (含まれる) すべての変数が最初に含まれます。ステートメントの転送関数は、このブロック内に書き込まれた変数を kill (有効な変数のセットから削除) することによって適用されます。ブロックの out-state は、ブロックの終了時に有効な変数のセットであり、ブロックの後続の in-state の結合によって計算されます。

初期コード:

後方分析:

cが書き込まれているため、 b3 の in-stateにはbとd のみが含まれます。 b1 の out-state は、 b2 と b3 の in-state の和集合です。 c はステートメントの直後は有効ではない ため、 b2 のcの定義は削除できます。

データフロー方程式を解くには、まずすべての in-state と out-state を空のセットに初期化します。作業リストは、作業リストに終了ポイント (b3) を挿入することで初期化されます (逆方向フローの場合に一般的)。計算された in-state は前のものと異なるため、その前の状態である b1 と b2 が挿入され、プロセスが続行されます。進行状況は以下の表にまとめられています。

b1 は b2 より前にリストに入力されたため、b1 の処理が 2 回強制されたことに注意してください (b1 は b2 の前身として再入力されました)。b2 を b1 より前に挿入すると、より早く完了できます。

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

いくつかの最近のコンパイラは、変数の依存関係を分析する方法として静的単一代入形式を使用しています。 ^[6]

2002 年に Markus Mohnen は、データフロー グラフの明示的な構築を必要とせず、代わりにプログラムの抽象的な解釈に依存し、プログラム カウンターのワーキング セットを保持する新しいデータフロー解析手法を説明しました^[7]。各条件分岐で、両方のターゲットがワーキング セットに追加されます。各パスは、可能な限り多くの命令 (プログラムの最後まで、または変更なしでループするまで) についてたどられ、その後セットから削除され、次のプログラム カウンターが取得されます。

制御フロー解析とデータフロー解析の組み合わせは、システムの機能（機能、要件、ユースケースなど）を実装するまとまりのあるソースコード領域を識別するのに有用かつ補完的であることが示されています。^[8]

効率的または一般的な解決策を持つデータフロー問題には、さまざまな特殊なクラスがあります。

上記の例は、データフロー値がセット、たとえば到達定義のセット（プログラム内の定義位置にビットを使用）またはライブ変数のセットである問題です。これらのセットは、各ビットが 1 つの特定の要素のセット メンバーシップを表すビット ベクトルとして効率的に表現できます。この表現を使用して、結合関数と転送関数をビット単位の論理演算として実装できます。結合演算は通常、ビット単位の論理和または論理積で実装される和集合または積集合です。各ブロックの転送関数は、いわゆる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 の
場合、 sは succ( b )に含まれる。
    out( b ) = out( b )またはin( s )
in( b ) = (out( b )かつkill( b )ではない)またはgen( b )

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

前述の到達定義とライブ変数の問題に加えて、次の問題がビットベクトル問題の例である: ^[10]

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

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

一般的なプログラミング言語では、IFDSベースのデータフロー解析の実装がいくつかあり、例えばJava解析用の Soot ^[12]やWALA ^{[13]フレームワークなどがある。}

すべてのビットベクトル問題は IFDS 問題でもありますが、実際に有効な変数や初期化されていない可能性のある変数など、ビットベクトル問題ではない重要な IFDS 問題がいくつかあります。

データフロー分析は通常はパスに依存しませんが、パスに依存する分析を生成するデータフロー方程式を定義することは可能です。

• フローに敏感な分析では、プログラム内のステートメントの順序が考慮されます。たとえば、フローに敏感でないポインター エイリアス分析では、「変数xとy は同じ場所を参照している可能性がある」と判断されるのに対し、フローに敏感な分析では、「ステートメント 20 の後、変数xとy は同じ場所を参照している可能性がある」と判断されることがあります。
• パス依存分析では、条件分岐命令の述語に応じて、さまざまな分析情報を計算します。たとえば、分岐に条件 が含まれている場合x>0、フォールスルーパスでは分析は であると想定しx<=0、分岐のターゲットでは が実際にx>0当てはまると想定します。
• コンテキスト依存分析は、関数呼び出しのターゲットを分析するときに呼び出しコンテキストを考慮するインタープロシージャ分析です。特に、コンテキスト情報を使用すると、元の呼び出しサイトに戻ることができますが、その情報がない場合、分析情報はすべての可能な呼び出しサイトに伝播する必要があり、精度が失われる可能性があります。

• 定義に到達する
• 生体分析
• 確定割り当て分析
• 利用可能な表現
• 一定の伝播

• 抽象的解釈
• 制御フロー分析
• XL86 について

• クーパー、キース D. ; トルゾン、リンダ ( 2003 ) [2002-01-01]。コンパイラのエンジニアリング。モーガン カウフマン。ISBN 978-1-55860-698-2。
• Muchnick, Steven Stanley (1997)。Advanced Compiler Design and Implementation。Morgan Kaufmann Publishers。ISBN 978-1-55860-320-2。
• ヘクト、マシュー S. (1977-05-03)。コンピュータ プログラムのフロー分析。プログラミング言語シリーズ。第 5 巻。エルゼビア ノース ホランド社 。ISBN 978-0-44400210-5。
• Khedker, Uday P.; Sanyal, Amitabha; Karkare, Bageshri (2009)。データフロー分析: 理論と実践。CRC Press ( Taylor and Francis Group )。
• ニールソン、フレミング;ニールソン、ハンネ・リース; ハンキン、クリス (2005)。プログラム分析の原則。Springer Science+Business Media。