Быстрый расчет доминаторов

Question

Говорят, что при преобразовании промежуточного кода в форму статического одиночного присваивания,

1. Необходимо рассчитать доминанты базовых блоков

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])

Есть ли какой-то недостаток у этого метода, которого я не вижу?

Answer 1

Хотя быстрое и правильное вычисление доминаторов действительно не тривиально, на практике существуют гораздо более простые алгоритмы, чем Ленгауэр-Тарьян, которые бывают такими же быстрыми или быстрыми (например, для типов потоковых графов управления, которые встречаются в большинстве программ), даже в худшем случае. сложность звучит страшно. См.: Купер, Кит D.; Харви, Тимоти J; и Кеннеди, Кен (2001). "Простой, быстрый алгоритм доминирования"

Answer 2

Ах, я вижу теперь, простые методы не правильно обрабатывают графы потоков управления, которые имеют произвольно много разветвлений и объединений. Вы должны быть в состоянии найти обходные пути, и если вы хотите, чтобы код для этого был быстрым, вам нужно вычислить и запомнить полумоминаторы, и тогда, похоже, вы в конечном итоге получите Ленгауэр-Тарьян или что-то подобное в любом случае.