Доминаторы и постдоминаторы

Работа с доминаторами и постдоминаторами нам нужна для Control Flow - анализа, а впоследствие для Data Flow - анализа.

В качестве примера мы будем обращаться к функции, реализующей построение чисел Фибоначи 0, 1 , 1, 2, 3, 5, 8, 13…

int f(m)
{
    int f0 = 0, f1 = 1, f2;
    if (m <= 1) 
        {return m;}
    for (int i = 2; i <= m; i++)
    {
        f2 = f0 + f1;
        f0 = f1;
        f1 = f2;
    }
    return f2;
}

Рассмотрим Control Flow этой функции:
cf1.JPG
На рисунке показано, как мы разбиваем инструкции на basic-блоки. Далее нам удобнее работать в терминах именно basic-блоков. Тогда CF-граф будет выглядеть так:
cf2b
  • В качестве нумерации мы используем DFO (depth-first order)

Введём теперь понятие доминатора.

Говорим, что блок A является доминатором блоком B, если любой путь из START'а в B проходит через A.

В нашем примере,
B1 dom B3,
B2 !dom B3,
B2 !dom STOP,
B5 !dom STOP,
B1 dom STOP

Доминирование есть отношение порядка - оно обладает следующими свойствами:
1) Если A == B, то A dom B
2) Если A dom B, B dom C, то A dom C
3) Если A dom B, B dom A, то A == B

Эти свойства позволяют рассматривать доминаторное дерево:
domtree.JPG

Можно ввести понятие непосредственного доминатора (immediate dominator):
A является непосредственным доминатором B (A idom B), если
1) A != B
2) A dom B
3) не существует C такого, что A dom C, C dom B

Постдоминаторы отличаются от доминаторов тем, что рассматриваются пути, исходящие из STOP'а, а не из START'а (и движемся соответственно против стрелок)

Доминаторы нам нужны, чтобы искать циклы.
Для этого мы смотрим все дуги и ищем среди них обратные, т.е. дуги вида A->B, где B доминирует над A.
Обратные дуги, как правило свидетельствуют о циклах (есть варианты, когда это не так, но мы их не рассматриваем)
Обратная дуга позволяет нам найти голову цикла. Далее мы спускаемся с головы цикла по вершинам которые он доминирует.

Алгоритм построения доминаторного дерева

//Nodes - весь набор узлов, включая Start и Stop
//Preds(node) - содержит предецессоры всех узлов
//root - корень, от которого строится дерево

proc Dom_Comp (Nodes, Pred, root)
begin
    //инициализация начальных условий
    Domin(root) := {root};

    foreach node in (Nodes - {root}) do
        Domin(node) := Nodes;

    //ядро алгоритма
    repeat
        change = false; //флаг - поменяли ли мы что-то за итерацию.
        foreach node in (Nodes - {root})
            Temp := Nodes;

            foreach pred in Preds(node)
                Temp := пересечение Temp и Domin(pred)
                D := объединение {node} и Temp

                if ( D != Domin(n) )
                    change = true;
                    Domin(n) = D;

    until (!change)

    return Domin;
end

//snark
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.