Может ли график зависимости управления иметь петли?

Question

Я пытаюсь точно понять понятие графика зависимости управления.Предположим, у меня есть следующий поток управления (в нотации DOT):

graph g {
1 -> 2;
2 -> 3;
3 -> 2;
2 -> 4;
1 -> 4
}

Он имеет уникальный входной узел (1) и уникальный выходной узел (4), а также цикл 2 -> 3 ->2.

Мой вопрос: содержит ли график зависимости управления для этого CFG ребро петли от 2 до самого себя?

Аллен и Кеннеди "Оптимизация компиляторов для современных архитектур" имеет алгоритм, который создает такой край цикла.Однако алгоритм Мухника "Разработка и реализация компилятора" для зависимости от управления не дает такого преимущества.Кроме того, я не смог найти примеров в литературе, где CDG нарисован с таким ребром петли.Я склонен полагать, что такого преимущества нет, но согласно формальному определению зависимости от управления и согласно алгоритму Аллена и Кеннеди, это должно быть!

Если вы можете указать мне пример, где есть такаяЦикл в CDG (желательно в рецензируемой статье, или в лекциях какого-то профессора и т. д.), или если вы можете спорить, почему алгоритм Аллена и Кеннеди должен быть неправильным, я был бы рад узнать.

Answer 1

Полезность такого графика зависимости - определить порядок операций, верно? В этом смысле не полезно знать, что элемент зависит от самого себя. Вы можете рисовать петли, если хотите, но что действительно важно, так это все остальные края.

Answer 2

Согласно Ferrante 1987 , петли зависимости могут существовать.В случае 2 на странице 325 автор указывает, что

Все узлы в дереве post-dominator на пути от A до B, включая A и B, должны быть зависимыми от A. (В этом случае фиксируется зависимость от цикла.)

Таким образом, в этом случае в узле A будет цикл.