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

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

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

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


compiler-construction ssa
person rwallace    schedule 19.05.2015    source источник
comment
Кстати, вам не обязательно вычислять доминаторы. В относительно недавней статье представлен алгоритм построения формы SSA непосредственно из байт-кода или AST< /а>.   -  person Martin Törnwall    schedule 19.05.2015

Ответы (2)


arrow_upward
3
arrow_downward

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

person Community    schedule 19.05.2015

arrow_upward
1
arrow_downward

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

person rwallace    schedule 19.05.2015