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

Question

我试图准确地理解控制依赖图的概念。假设我有以下控制流图(以 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 的“Compiler design & implementation”的控制依赖算法并没有产生这样的优势。此外，我在文献中找不到任何使用这种循环边缘绘制 CDG 的示例。我倾向于相信没有这样的优势，但根据控制依赖的正式定义和 Allen & Kennedy 的算法，它应该!

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

Answer 1

这种依赖图的用途是确定如何对操作进行排序，对吗？从这个意义上说，知道一个元素依赖于它自己是没有帮助的。如果您愿意，您可以绘制循环，但真正重要的是所有其他边缘。