我试图准确地理解控制依赖图的概念。假设我有以下控制流图(以 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 的算法应该是不正确的,我很高兴知道。
最佳答案
这种依赖图的用途是确定如何对操作进行排序,对吗?从这个意义上说,知道一个元素依赖于它自己是没有帮助的。如果您愿意,您可以绘制循环,但真正重要的是所有其他边缘。
关于compiler-construction - 控制依赖图可以有循环吗?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9034979/