admin管理员组文章数量:1602103
支配边界及其构建算法 Dominance Frontier and its construction algorithm
- Dominance Frontier
- Alogorithm of Dominance Frontier
- 参考
Dominance Frontier是SSA插入 ϕ \phi ϕ函数、构建CDG(控制依赖图)算法的重要工具。本文介绍Dominance Frontier的概念和算法。
Dominance Frontier
《现代编译原理C语言描述(修订版)》中对Dominance Frontier的定义如下:
节点x的Dominance Frontier是所有符合下面条件的节点w的集合:x是w的前驱支配节点,但不是w的严格支配节点。
本质上,它是支配节点和非支配节点直接的”分界线“。
这个例子中,节点5是
{
5
,
6
,
7
,
8
}
\{5, 6 ,7 ,8\}
{5,6,7,8}的支配节点,
D
F
(
5
)
=
{
5
,
4
,
13
,
12
}
DF(5) = \{5, 4, 13, 12\}
DF(5)={5,4,13,12}。
Alogorithm of Dominance Frontier
《编译器设计(第二版)》提供了一种易于理解的算法,该算法以dominator tree和CFG为输入。
根据Dominance Frontier的定义我们可以知道, DF的集合中的节点必定是CFG中的汇合点; 对于 j的某些前驱节点 k,
j
∈
D
F
(
k
)
j\in DF(k)
j∈DF(k),那么对于每个
l
∈
D
o
m
(
k
)
l \in Dom(k)
l∈Dom(k),必然有
j
∈
D
F
(
l
)
j \in DF(l)
j∈DF(l),除非
l
∈
D
o
m
(
j
)
l \in Dom(j)
l∈Dom(j)。算法如下:
Dominator相关算法可以参考 支配节点树及其构建算法 Dominator-tree and its Construction Algorithms。看下面这个例子,根据上面的算法很容易得到DF集合。
参考
- [1] 现代编译原理C语言描述(修订版)
- [2] 编译器设计(第二版)
本文标签: 边界算法Dominancealgorithmconstruction
版权声明:本文标题:支配边界及其构建算法 Dominance Frontier and its construction algorithm 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/xitong/1728397234a1157150.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论