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

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

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

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

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

В книге Allen & Kennedy "Optimizing compilers for modern architectures" есть алгоритм, который производит такое ребро цикла. Однако алгоритм Muchnick's "Compiler design & implementation" для управляющей зависимости не дает такого края. Кроме того, я не смог найти в литературе ни одного примера, где бы CDG рисовался с таким краем цикла. Я склонен считать, что такого края нет, но согласно формальному определению зависимости управления и согласно алгоритму Аллена и Кеннеди, он должен быть!

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

6
задан anol 27 January 2012 в 14:42
поделиться