3

定義に到達する問題は、データ フロー分析における最も基本的な問題の 1 つです。変数の定義と用途を含む制御フロー グラフが与えられた場合、問題は、どの変数定義が特定の用途に達するかを計算することになります。

たとえば、フロー グラフを考えてみましょう。

                    ____________
                 1:|   x <- ... |
                    ------------
                     |            \
                     |              __________
                     |           2:| x <- ... |
                     |              -----------
                     |            /
                    ____________    
                 3:|  ... <- x  |
                    ------------

ブロック 3 での変数 x の使用は、ブロック 1 またはブロック 2 のいずれかの定義から到達できます。

どの定義が用途に達するかを計算するアルゴリズムは、古典的なデータ フローの問題です。ドラゴン コンパイラの本 (新版) の表記法を使用すると、定義に到達するデータ フローの問題は次のようになります。

ドメイン : 定義のセット (例: {x <- .., ...})
方向 : 順方向
伝達関数 : fb(x) = gen(B) U (x - kill(B)) ここで、gen(B) はブロック B が生成する一連の定義と kill(B) ブロック B が削除する一連の定義
Boundary : OUT[ENTRY] = {} つまり、関数へのエントリのための定義フローはありません
演算子に適合します: U(union)、つまり定義ブロックへのフローは、先行ブロックからの定義の結合です。
式 : OUT[B] = fb(IN[B]), IN[B] = U(P in pred)OUT[P]
初期化: OUT[B] = {}

ただし、すべての定義が同じというわけではありません。たとえば、ブロック 1 の定義は、ブロック 2 の定義によって殺される可能性があるため、ブロック 3 の使用に決して到達しない可能性があります。一方、ブロック 2 の定義は、実行された場合、ブロックで使用されるまでその値を保持します。 3.

定義から使用法へのどのパスにも強制終了定義がない使用法の到達定義を見つけたいです。私の質問は、同様のデータフローの問題が存在するかどうかです（おそらく伝播など）。データフロー分析の観点からどのように解決できるか。

この問題に対する解決策は 1 つ考えられますが、解決策が既に存在する場合、車輪の再発明はしたくありません。

4

3 に答える 3

0

これが私が問題を解決した方法です。それは最も効率的な方法ではないかもしれませんが、私はそれがうまくいくと信じています。この問題を、保存された定義の問題と呼びます。最初に、到達定義を計算します。ビットセットで表される定義のセットに対して反復データフローアルゴリズムを使用しています。

そのためには、最初にすべてのブロックのgen（B）とkill（B）を計算する必要があります。これらは、それぞれ各ブロックによって生成および強制終了される定義です。ここで、kill（B）は実際のkill（B）のスーパーセットであることに注意してください。この時点ではデータフローを考慮していないため、どの定義とどのブロックから実際にキルされているのかわからないためです。

到達定義を適用した後、制御フローグラフの各ブロックにREACH_IN（B）とREACH_OUT（B）のセットがあります。保存された定義が到達定義のサブセットであることを私は知っています。それらを計算するために、私はどの定義が各ブロックへのプログラムのエントリから決して殺されることができなかったかを見つける必要があります。これらのセットをキルセットなしと呼び、グラフの各ブロックのNO_KILL_IN（B）とNO_KILL_OUT（B）を計算するアルゴリズムを提供します。これがデータフロー分析の観点からのアルゴリズムです。

ドメイン：定義のセット（例：{x <-..、...}）
方向：転送
転送関数：fb（x）= x-（kill（B）∩REACH_IN（B））ここで、kill（B）はBの強制終了をブロックする定義のセットとREACH_IN（B）Bに流入する定義のセット。
境界：NO_KILL_OUT [ENTRY] = U
（ユニバーサルセット）つまり、関数 Meet演算子の入力からすべての定義が強制終了されるわけではありません：∩（交差点）つまり、先行ブロックのいずれかで定義が強制終了されない場合、定義は強制終了されません。
方程式：NO_KILL_OUT [B] = fb（IN [B]）、NO_KILL_IN [B] =∩（P in pred）NO_KILL_OUT [P]
初期化：NO_KILL_OUT [B] = U

転送関数では、ブロックBで強制終了される実際の定義のセットであるkill（B）∩REACH_IN（B）を計算することに注意してください。これを使用しないと、過度に説得力があります。アルゴリズムは、定義が生成されたかどうかを考慮せずに、各ブロックの前後にどの定義を強制終了できなかったかを計算します。保存された定義を計算するために、交差点を実行するだけです。

PRESERVE_IN（B）= REACH_IN（B）∩NO_KILL_IN（B）
PRESERVE_OUT（B）= REACH_OUT（B）∩NO_KILL_OUT（B）

于 2011-04-17T16:47:11.873 に答える
0

問題定義を次のように変更します。

演算子を満たします: ∩(Intersect)、つまり、ブロックに流れる定義は、先行ブロックからの定義の交差です。

式 : OUT[B] = fb(IN[B]), IN[B] = ∩(P in pred)OUT[P]

于 2011-04-15T03:56:48.600 に答える
0

代わりに、時相論理を見たいと思うかもしれません。計算ツリー ロジックは、制御フロー グラフのパスのプロパティを定義するのにかなり役立ちます。このペーパーでは、CTL のデータ フロー プロパティの例をいくつか示します。

時相論理によるコンパイラ最適化の正しさの証明

于 2011-10-03T18:09:26.730 に答える