控制依赖图可以有循环吗？
我试图准确理解控制依赖图的概念。假设我有以下控制流图（以点表示法）：
graph g {
1 -> 2;
2 -> 3;
3 -> 2;
2 -> 4;
1 -> 4
}
它有一个唯一的入口节点 (1) 和一个唯一的出口节点 (4)，以及一个循环 2 -> 2。 3-> 2.
我的问题是：这个CFG的控制依赖图是否包含从2到自身的循环边？
艾伦与肯尼迪的“优化现代架构的编译器”有一个算法可以产生这样的循环边缘。然而，Muchnick的“编译器设计与实现”的控制依赖算法并没有产生这样的优势。此外，我在文献中找不到任何用这样的环边绘制CDG的例子。我倾向于相信不存在这样的边缘，但根据控制依赖的正式定义以及根据 Allen &肯尼迪算法，应该的！
如果您可以，请给我指出一个 CDG 中存在这样一个循环的示例（最好是在同行评审的论文中，或一些教授的讲义等），或者您是否可以争论为什么 Allen & CDG 中存在这样的循环。肯尼迪的算法应该是不正确的，我很高兴知道。
I'm trying to understand precisely the notion of a control dependence graph. Suppose I have the following control flow graph (in DOT notation) :
graph g {
1 -> 2;
2 -> 3;
3 -> 2;
2 -> 4;
1 -> 4
}
It has a unique entry node (1) and a unique exit node (4), and a loop 2 -> 3 -> 2.
My question is: does the control dependence graph for this CFG contain a loop edge from 2 to itself?
Allen & Kennedy's "Optimizing compilers for modern architectures" has an algorithm that produces such a loop edge. However, Muchnick's "Compiler design & implementation"'s algorithm for control dependence does not produce such an edge. Besides, I couldn't find any examples in the literature where a CDG is drawn with such a loop edge. I tend to believe there is no such edge, but according to the formal definition of control dependence and according to Allen & Kennedy's algorithm, it should!
If you can please point me to an example where there is such a loop in a CDG (preferably in a peer-reviewed paper, or some professor's lecture notes, etc), or if you can argue why Allen & Kennedy's algorithm should be incorrect, I'd be glad to know.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这种依赖图的用途是确定如何排序操作，对吧？从这个意义上说，知道一个元素依赖于它自己是没有帮助的。如果您愿意，您可以绘制循环，但真正重要的是所有其他边缘。
The utility of such a dependence graph is determine how to order the operations, right? In that sense, it is not helpful to know that an element depends on itself. You can draw the loops if you like, but what's really important is all the other edges.
根据费兰特 1987，控制依赖循环可以存在。在第 325 页的案例 2 中，作者指出
因此，在这种情况下，节点 A 处将存在循环。
According to Ferrante 1987, control-dependence loops can exist. In Case 2 on page 325, the author specifies that
Thus there would be a loop at node A in this case.