Что такое доминатор узла и дерево доминатора?

Question

Я попробовал читать википедию о Доминатор (теория графика) Следующее определение узла доминатора:

Узел d доминирует на узле n, если каждый путь от узла ввода на N должен пройти через d.

Мне нужно понять концепцию узла доминатора, но мне не нужно глубоко уходить на графики, поэтому я пытаюсь почувствовать смысл этих определений. Я пытаюсь посмотреть на изображения на статье:

Это график:

Это должно быть доминирующее дерево для графика выше:

на основе определения выше, я думаю,

Узел 2 доминирует над узлом 3, потому что каждый путь от 3 должен пройти через 2. Почему? Чтобы пойти от 3 к себе, я должен пройти к 2. Вот почему 2 идет до 3 в дереве доминатора.

Я думаю, правильно?

Могу ли я знать также, почему это полезно в компиляторах?

Answer 1

Причина, по которой вы даете, не совсем правильно; Определение узла доминатора работает с исходного узла ( 1 $ $ в примере). Единственный способ достичь $ 3 $ from $ 1 $ - это пройти через 1 $ $ в данном графике. Следовательно, $ 2 $ Доминирует $ 3 $ . По той же причине узлы $ 4 $ через $ 6 $ также доминируют $ 2 $ а также, $ 2 $ Доминатель этих узлов (как $ 1 $ Доминирует $ 2 $ ), и эти узлы также не доминируют никаких других узлов, чем $ 1 $ и $ 2 $ :

.
• $ 3, 4 $ и $ 6 $ можно сразу же добраться до $ 1 $ через $ 2 $ .
• $ 5 $ можно добраться до $ 2 $ либо через $ 3 $ или $ 4 $ И, таким образом, единственным общим узлам в этих путях к $ 5 $ являются $ 1 $ и $ 2 $ .

Что касается применения этих концепций к компиляторам, рассмотрите график потока контроля уровня блока (или CFG для краткости) программы. Если какой-то блок $ B $ доминирует в блоке $ B '$ в CFG, то $ B $ должен был выполнен к тому времени, когда программа достигает $ B '$ . Эти знания могут быть использованы для удаления избыточных кусочков кода: Рассмотрим программу

a = (something)
b = True

if a == True:
   b = True
else:
   b = False
   

.

Здесь блок, состоящий из первых двух строк, доминирует на IF-Block, а также остальный блок. Следовательно, мы знаем, что к тому времени, когда мы перепрыгиваем на IF-Block, где мы установим b в true, он уже устанавливается в True by блок кулака, и, таким образом, компилятор может оптимизировать код, удаляя назначение в блоке IF-Black.

Вы также можете обнаружить петли в коде, анализируя, если CFG имеет ребра формы $ B '\ to b $ где снова $ b $ доминирует $ b '$ . Такой путь указывает на существование цикла, где $ b $ затем представляют заголовок петли, когда $ B '$ - это (последняя) часть тела петли.