4

私は自分が書いているコンパイラーのためにSSA構築を実装しています。SSAアルゴリズムには理解できないことがあります（Cytronの論文とAWAppelによる第2版の本「 ModernCompilerImplementation inJava」を使用）。変数yが1つの直線制御フローパスで初めて定義された（そして使用された）が、別の並列パスでは定義されなかった場合はどうなりますか。ジョインポイント（定義するブロックの支配辺境y）にPHI関数を挿入する必要がありますか？

x = 1;            // A
if (P)            // A
    y = x + 1;    // B
    y = y + 1;    // B
x = x + 1;        // C
return;           // C

たとえば、ブロックBには、の最初の定義がありyます。ブロックCの先頭に2つのオペランド（入力制御フローパスごとに1つ）を持つPHI命令を挿入する必要がありますか？次に、SSAの名前変更について：定義されA -> Cていないパス（Bを経由しない）からのオペランドにどのように名前を付けますか？y

Entry --- A --------- C --- Exit
           \         /
            \-- B --/
4

1 に答える 1

3

資料をもう一度読んだ後、変数の暗黙的な定義についてのAWAppelによる第2版の本ModernCompiler ImplementationinJavaでc0小さなヒントを見つけました。さらに検索すると、アルゴリズムはすべての変数が最初の基本ブロックの直前に暗黙の定義を持っていることを期待していることが明らかになりました。この暗黙の定義は、変数がグローバル、パラメーター、または初期化されていない変数であるという事実を表しています。

この暗黙の定義を追加すると、私の問題が解決し、例は次のようになります。

x1 = 1;           // A
if (P)            // A
    y1 = x1 + 1;  // B
    y2 = y1 + 1;  // B
y3 = φ(y0, y2)    // C
x2 = x1 + 1;      // C
return;           // C
于 2012-05-21T22:27:02.687 に答える