编译器构造 – 控制依赖图是否有循环？

发布时间：2020-12-13 20:48:01 所属栏目：百科来源：网络整理

导读：我试图准确理解控制依赖图的概念.假设我有以下控制流程图(以DOT表示法)： graph g {1 - 2;2 - 3;3 - 2;2 - 4;1 - 4} 它具有唯一的入口节点(1)和唯一的出口节点(4),以及循环2 – 3 – 2. 我的问题是：这个CFG的控制依赖图是否包含从2到自身的循环边缘？艾伦

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

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

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

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

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

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

根据 Ferrante 1987,可以存在控制依赖循环.在第325页的案例2中,作者指定了

All nodes in the post-dominator tree on the path from A to B,
including A and B,should be made control dependent on A. (This case
captures loop dependence.)

因此,在这种情况下,节点A将存在循环.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!