定義に到達する

コンパイラ理論では、特定の命令の到達定義とは、そのターゲット変数が、介在する割り当てなしで特定の命令に到達できる (割り当てられる) 先行する命令のことです。たとえば、次のコードでは次のようになります。

d1:y:=3 です。
d2:x:=y です。

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

d1:y:=3 です。
d2:y:=4 です。
d3: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 {殺す}}}$

• ${\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 }; } }       
        
        
             
                   
    

• デッドコードの除去
• ループ不変コードの動き
• 到達可能な用途
• 静的単一割り当てフォーム

• Aho, Alfred V.; Sethi, Ravi & Ullman, Jeffrey D. (1986)。コンパイラ：原理、テクニック、ツール。Addison Wesley。ISBN 0-201-10088-6。
• Appel, Andrew W. (1999)。MLにおける最新のコンパイラ実装。ケンブリッジ大学出版局。ISBN 0-521-58274-1。
• クーパー、キース D. & トルゾン、リンダ (2005)。コンパイラのエンジニアリング。モーガン カウフマン。ISBN 1-55860-698-X。
• Muchnick, Steven S. (1997)。高度なコンパイラの設計と実装。Morgan Kaufmann。ISBN 1-55860-320-4。
• Nielson F.、HR Nielson、C. Hankin (2005)。プログラム分析の原則。Springer。ISBN 3-540-65410-0。