Building SSA Form

  1. 计算Dominator tree

  2. 计算控制边界
    1
    2
    3
    4
    5
    6
    7
    8
    9
    for all nodes, n, in the CFG
    DF(n) <- NULL
    for all nodes, n, in the CFG
    if n has multiple predecessors then//必须有2个或2个以上的predecessors
    for each predecessor p of n
    runner <- p
    while runner != IDom(n)
    DF(runner) <- DF(runner) U {n}
    runner <- IDom(runner)

举例如下:


最后得到Dominance Frontiers

对于n的定义语句可以放置一个PHI函数在m处,如果

  1. 插入PHI函数
    在真正插入PHI函数之前,我们需要在Dominance Frontiers的基础上,更精确的找到需要PHI函数的地方。

“The basic idea is simple. A definition of x in block b forces a ϕ-function at every node in df(b).
Since that ϕ-function is a new definition of x, it may, in turn, force the insertion of additional ϕ-functions.”

1
2
3
4
5
6
7
for each name x∈ Globals
WorkList <- Blocks(x)
for each block b∈ WorkList
for each block d in DF(b)
if d has no PHI function for x then
insert a PHI function for x in d
WorkList <- WorkList U {d}

对于每个global name x,算法将WorkList初始化为Blocks(x)。
对于WorkList上的每个block b,算法在b的支配边界(DF(b))中每个block d的起始处插入PHI函数。
在向d中添加对应于x的PHI函数之后,算法将d添加到WorkList,以反映d中对x的新赋值操作

  1. 重命名变量的名字,满足SSA规则