Тема 04(2016)Доминаторы и постдоминаторы (Лекции), страница 2

Алгоритм построения границ доминирования Вход: граф потока Выход: множество границ доминирования для узлов графа потока Метод: выполнить следующую программу:for all n  N do DF(n) = ;for all n  N do{if |Pred(n)| > 1 thenfor each p  Pred(n) do{r = p;while r  IDom(n) do{DF(r) = DF(r)  {n};r = Idom(r);}};}244.2 Граница доминирования4.2.4. Пример применения алгоритма построения границдоминированияГраф потокауправленияДереводоминаторовn01234567Pred(n){0,7}{1}{1}{3}{3}{4, 5}{2, 6}Dom(n){0}{0,1}{0,1,2}{0,1,3}{0,1,3,4} {0,1,3,5} {0,1,3,6} {0,1,7}Idom(n){0}{1}{1}{3}{3}{3}{1}254.2 Граница доминирования4.2.4.

Пример применения алгоритма построения границдоминированияУ графа три точки сбора – входы в узлы B1, B6 и B7.Узел B6: Pred(B6) = {B4, B5}, Idom(B6) = {B3},проходим от B5 до B3, добавляем B6 к DF(B5),проходим от B4 до B3, добавляем B6 к DF(B4).Узел B7: Pred(B7)= {B2, B6}, Idom(B7) = {B1},проходим от B2 до B1, добавляем B7 к DF(B2),проходим от B6 до B3, добавляем B7 к DF(B6)проходим от B3 до B1, добавляем B7 к DF(B3)Таблица текущих результатов:n0123456DF(Bn){B7}{B7}{B6}{B6}{B7}74.2 Граница доминирования4.2.4. Пример применения алгоритма построения границдоминированияУзел B1: Pred(B1) = {B0, B7}, Idom(B1) = {B0},У B0 нет непосредственного доминатора:Idom(B0) = ,значит B1  DF(B0).проходим от B7 до B1 (по обратному ребру),добавляем B1 к DF(B7).Окончательная таблица результатов0nDF(Bn) 1234567{B7} {B7} {B6} {B6} {B7} 4.3 Постдоминаторы4.3.1 ОпределениеВ ГПУ вершина p является постдоминатором вершины n(этот факт записывается как p postdom n или p = Postdom(n)),если любой путь от вершины n до вершины Exit проходитчерез вершину d.Замечание.

Из определения 4.2.1 следует, что каждая вершина nявляется постдоминатором самой себя: путь от n до Exitпроходит через n.284.3 Постдоминаторы4.3.2 ОпределенияОбратным графом ориентированного графа G = N, Eназывается ориентированный граф GR = N, ER, у которогонаправления всех ребер противоположны.Постдоминаторы ГПУ – это доминаторы его обратногографа.Обратная граница доминирования (RDF(n)) вершины n  Gэто обычная граница доминирования в обратном графе GR.294.3 Постдоминаторы4.3.3 Применение постдоминаторов. Зависимость по управлению.По определению, вершина m ГПУ зависит по управлению отвершины n тогда, и только тогда, когда:существует непустой путь T от n до m, такой чтоk  T – {n}: m = Postdom(k), т.е. если выполнениепрограммы пошло по пути T, то, чтобы достичь exit,оно обязательно пройдет через m.m не обязательно является строгим постдоминатором n:у n может быть несколько выходов, так что помимо Tвозможны и другие пути, проходящие через n, но потомведущие не в m, а в другие вершины.Обратная граница доминирования позволяет определять границызависимостей по управлению.304.3 Постдоминаторы4.3.4 Эквивалентность по управлениюОпределение.

Два базовых блока Bi и Bj эквивалентны поуправлению, если Bi выполняется тогда, и только тогда, когдавыполняется Bj .Утверждение. Если выполняются соотношения:Bi = Dom(Bj) и Bj = Postdom(Bi)то базовые блоки Bi и Bj эквивалентны по управлению31.