0

中間コードを静的単一代入形式に変換すると、

  1. 基本ブロックのドミネーターを計算する必要があります

  2. 方程式の不動点としてこれを行うやや明白な方法は遅いです

  3. 高速に実行するには、かなり複雑な Lengauer-Tarjan アルゴリズムを使用する必要があります

最初の 2 点はわかりますが、3 番目の理由がよくわかりません。特に、プレオーダードミネーターツリーを計算する過程だけでできない理由はありますか？私はJavaScriptでそのバージョンを実装しましたが、うまくいくようです:

var domPreorder = [];

function doms(b) {
    b.children = [];
    for (var c of b[b.length - 1].targets)
        if (c.i == null) {
            c.i = domPreorder.length
            domPreorder.push(c)
            b.children.push(c)
            c.parent = b
            doms(c)
        }
}

f[0].i = 0
domPreorder.push(f[0])
doms(f[0])

この方法には、私が見ていない欠点がありますか?

4

2 に答える 2

3

ドミネーターを迅速かつ正確に計算することは確かに簡単ではありませんが、Lengauer-Tarjan よりもはるかに単純なアルゴリズムで、実際には (つまり、ほとんどのプログラムで発生する種類の制御フロー グラフで) 高速または高速です。複雑さは恐ろしく聞こえます。参照: クーパー、キース D.; ハーベイ、ティモシー J。とケネディ、ケン（2001）。「シンプルで高速な支配アルゴリズム」

于 2015-05-19T11:40:49.053 に答える
1

ああ、わかりました。単純な手法では、任意に多くのフォークと再結合がある制御フロー グラフを正しく処理できません。バイパス パスを見つけられるようにする必要があります。それを行うためのコードを高速にするには、セミドミネーターを計算して覚えておく必要があります。いずれにせよ、Lengauer-Tarjan または同様の線に沿った何かで終わるように見えます。

于 2015-05-19T10:46:22.780 に答える