控制依赖图可以有循环吗？

Question

我试图准确理解控制依赖图的概念.假设我有以下控制流程图(以DOT表示法):

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

它有一个唯一的入口节点(1)和一个唯一的出口节点(4),以及一个循环2 - > 3 - > 2.

我的问题是:这个CFG的控制依赖图是否包含从2到自身的循环边缘？

Allen&Kennedy的"为现代架构优化编译器"有一种算法可以产生这样的循环边缘.然而,Muchnick的"编译器设计和实现"的控制依赖算法并没有产生这样的优势.此外,我在文献中找不到任何用这样的循环边缘绘制CDG的例子.我倾向于认为没有这样的优势,但根据控制依赖的正式定义,并根据艾伦和肯尼迪的算法,它应该!

如果你能指出我在CDG中存在这样一个循环的例子(最好是在同行评审的论文中,或者某些教授的讲义等),或者你可以说为什么Allen&Kennedy的算法应该是不正确的,我很高兴知道.

Answer 1

根据Ferrante 1987 的说法，控制相关环路是可以存在的。在第 325 页的案例 2 中，作者指出

从 A 到 B 的路径上的后支配树中的所有节点（包括 A 和 B）都应该依赖于 A 进行控制。（这种情况捕获了循环依赖性。）

因此，在这种情况下，节点 A 处将出现环路。