定義に到達する

コンパイラ理論において、ある命令の到達定義とは、その命令のターゲット変数が、介在する代入なしに、その命令のターゲット変数に到達できる（代入される）ことができる、それより前の命令のことです。例えば、次のコードでは：

d1 : y := 3d2 : x := y

d1は の到達定義ですd2。ただし、次の例では、

d1 : y := 3d2 : y := 4d3 : x := y

d1はもはや の到達定義ではありませんd3。なぜならは の到達範囲を失っているからです。d2つまり、 で定義された値はd1もはや利用できず、 に到達できませんd3

分析として

同様の名前を持つ到達定義は、コード内の特定のポイントに到達できる定義を静的に決定するデータフロー分析です。その単純さから、教科書ではデータフロー分析の標準的な例としてよく使われます。使用されるデータフロー合流演算子は集合和集合であり、分析は順方向フローです。到達定義は、use -defチェーンを計算するために使用されます

定義に到達する際に 特定の基本ブロック に使用されるデータフロー方程式は次のとおりです。 ${\displaystyle S}$

• ${\displaystyle {\rm {REACH}}_{\rm {in}}[S]=\bigcup _{p\in pred[S]}{\rm {REACH}}_{\rm {out}}[p]}$
• ${\displaystyle {\rm {REACH}}_{\rm {out}}[S]={\rm {GEN}}[S]\cup ({\rm {REACH}}_{\rm {in}}[S]-{\rm {KILL}}[S])}$

言い換えれば、 に入る到達定義の集合は、の先行する到達定義のすべてであり、 は制御フローグラフの前にあるすべての基本ブロックで構成されます。 から出る到達定義は、の先行するすべての到達定義から、 によって変数が削除される到達定義を除いたもの、および 内で生成される新しい定義を除いたものになります。 ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle pred[S]}$ ${\displaystyle pred[S]}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle S}$

汎用命令の場合、およびセットを次のように定義します。 ${\displaystyle {\rm {GEN}}}$ ${\displaystyle {\rm {KILL}}}$

• ${\displaystyle {\rm {GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{d\}}$、基本ブロック内のローカルで利用可能な定義の集合
• ${\displaystyle {\rm {KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]={\rm {DEFS}}[y]-\{d\}}$、基本ブロック内の定義によって削除された定義のセット (ローカルでは使用できないが、プログラムの残りの部分では使用可能)。

ここで、 は変数 に代入するすべての定義の集合です。ここでは代入命令に固有のラベルが付与されています。したがって、定義に到達する際の値の定義域はこれらの命令ラベルです。 ${\displaystyle {\rm {DEFS}}[y]}$ ${\displaystyle y}$ ${\displaystyle d}$

ワークリストアルゴリズム

到達定義は通常、反復ワークリストアルゴリズムを使用して計算されます

入力: 制御フローグラフ CFG = (ノード、エッジ、エントリ、エグジット)

// N内のすべてのCFGノードnを初期化します。OUT [ n ] = emptyset ; // OUT [n] = GEN[n] で最適化できます。          // すべてのノードを変更されたセットに追加します// N はグラフ内のすべてのノード、Changed = N ;  // 反復処理while ( Changed != emptyset ) { Changed内のノードnを選択します。// 変更されたセットからそれを削除します。 Changed = Changed - { n };                 // IN[n]を空に初期化します。IN [ n ] = emptyset ;    // 先行ノードのすべてのノードpについて、先行ノードの OUT[p] から IN[n] を計算します( n ) IN [ n ] = IN [ n ] Union OUT [ p ];            oldout = OUT [ n ]; // 古い OUT[n] を保存// 転送関数 f_n() を使用して OUT[n] を更新OUT [ n ] = GEN [ n ] Union ( IN [ n ] - KILL [ n ]);            // OUT[n]は以前の値と比べて何か変更されているか？if ( OUT [ n ] changed ) // oldoutとOUT[n]を比較する{ // もしそうなら、nの後続ノードすべてを、 successors ( n )内のすべてのノードsの変更されたセットに入れるChanged = Changed U { s }; } }                     

参照

• デッドコードの除去
• ループ不変コードの移動
• 到達可能な使用
• 静的単一代入形式

参考文献

• アホ, アルフレッド V.; セティ, ラヴィ & ウルマン, ジェフリー D. (1986). 『コンパイラ：原理、テクニック、ツール』 アディソン・ウェスリー. ISBN 0-201-10088-6。
• アペル、アンドリュー・W. (1999). 『MLにおける最新のコンパイラ実装』ケンブリッジ大学出版局. ISBN 0-521-58274-1。
• クーパー、キース・D. & トルゾン、リンダ (2005). 『コンパイラのエンジニアリング』 モーガン・カウフマン. ISBN 1-55860-698-X。
• スティーブン・S・マッチニック（1997年）『高度なコンパイラの設計と実装』モーガン・カウフマン社ISBN 1-55860-320-4。
• ニールソン・F、HR・ニールソン、C.・ハンキン（2005年）。『プログラム分析の原則』、シュプリンガー、ISBN 3-540-65410-0。

「https://en.wikipedia.org/w/index.php?title=Reaching_definition&oldid=1254442801」より取得