Static Single Assignment

Nov 26, 2022

CFG

抄维基一个例子,如下一段代码:

x = 5
x = x - 3
if x < 3:
    y = x * 2
    w = y
else:
    y = x - 3
w = x - y
z = x + y

可以转换为 control-flow graph:

SSA

SSA (static single assignment) 形式的含义是 IR 里每个变量仅被赋值一次。

最简单的办法是给每一个变量加一个后缀,变成一个新的变量:

为了解决 node 汇入时该使用哪一个变量的问题,引入了 Φ(phi)-function。含义是从第几个前驱 node 来的话就取第几个参数变量。

如果 y2 = x2 - 3 这个 node 里的 y2 使用 y1 的名字的话,最后一个 block 可以只用 y1 也就避免了插入 Φ,得到了更简单的表示。

如何得到 minimal SSA 需要引入 dominator tree。

dominator tree

回到最初的 CFG:

如果从 entry 到 node Y 的每一条路径都经过了 node X 的话,我们就说 X dominate 了 Y。(后面简写为 X dom Y。)

Domination 具有自反性(X dom X)和传递性(X dom Y, Y dom Z => X dom Z)。

也可以说 X 是 Y 的 dominator。Y 的 dominator 组成集合 dom(Y)

如上图,dom(A) = {A}dom(B) = {A, B}dom(C) = {A, C}

用集合也可以给出递归定义:

dom(Y) = ∩(dom(X) for X in preds(Y)) ∪ {Y}

Y 的 immediate dominator,简写为 idom(Y),是指非 Y 但离 Y 最近的 dominator。

可以证明 idom(Y) 最多只有一个。那么 idom 关系可以组成一颗 dominator tree。

dom(Y) 集合的定义也可以反过来用 idom 表示:

dom(Y) = {Y} ∪ {idom(Y)} ∪ {idom(idom(Y))} ··· ∪ {E}

dominance frontier

简写为 DF(X),可以理解为那些 恰好 不再受 X dominate 的 node 的集合。

比如 X dom 了 Z 的一个前驱 Y,但 Z 还有别的没有被 X dom 的前驱,导致 X 并没有 dom Z,那么 Z 就属于 DF(X)

可以看出 dominance frontier 是单个变量的不同定义在 CFG 中交汇的地方,是插入 Φ-function 的理想地方。

但插入 Φ-function 其实又算是一次变量定义。所以通常会先求一个 iterated dominance frontier(设 defs(v) 是定义了变量 v 的 nodes):

DF+(v) = DF(defs(v)) u DF(DF(defs(v))) u DF(DF(DF(defs(v)))) ...

也叫做 joins(v)

Reverse postorder

顾名思义,就是把后续遍历得到的顺序反序一下。相当于 CFG 这种有向有环图上的拓扑序。

按照该顺序来遍历 CFG 中的 node,可以保证在遍历 node 前已经遍历完它的 dominators 了。所以后文算法中遍历 node 的顺序通常指该顺序。

Dominance algorithm

根据前面定义,一个 naive 的求 dominator 集合的迭代算法可以用伪代码表示为:

for n in nodes:
    dom[n] = {1 ... N}
changed = True
while changed:
    changed = False
    for n in nodes:
        new_dom = (dom[p] for p in preds[n])  {n}
        if new_dom != dom[n]:
            dom[n] = new_dom
            changed = True

因为 dom(...) 集合可以看做是 dominator tree 上沿着 idom[...] 的向上递归到 entry 一条路径,那么 dom(A) ∩ dom(B) 就是路径的的共同前缀。

idom 数组来替代集合的话,求并集变成了求两条路径的最近公共祖先:

def intersect(a, b):
    while a != b:
        a_idx = get_reverse_postorder_index(a)
        b_idx = get_reverse_postorder_index(b)
        if a_idx < b_idx:
            b = idom[b]
        else:
            a = idom[a]
    return a

原算法可以简化为求 idom[...] 也即 dominator tree 的算法:

for n in nodes:
    idom[n] = None
idom[entry] = entry
changed = True
while changed:
    changed = False
    for n in nodes:
        if n == entry:
            continue
        new_idom = pred[n][0]  # pick first predecessor
        for p in pred[n][1:]:  # rest predecessors
            if idom[n] != None:
                new_idom = intersect(new_idom, idom[p])
        if idom[n] != new_idom:
            idom[n] = new_idom
            changed = True

有了 dominator tree 之后求 dominance frontier 也很简单。在交汇点 nidom[n] 之间所有节点,都有 n 作为其 dominance frontier 的一员:

for n in nodes:
    if len(preds[n]) >= 2:  # is a join point
        for p in preds[n]:
            runner = p
            while runner != idom[n]:
                df[runner].add(n)  # may dup
                runner = idom[runner]

这就是 《A Simple, Fast Dominance Algorithm》 中提出的算法。

φ-function insertion and variable renaming

每一个变量 v 用 dominance frontier 求 joins(v),顺便插入 Φ-function:

for v in variables:
    saw = {}     # blocks where Φ is added
    w = queue()  # working list
    for n in defs[v]:
        w.push(n)
    while w:
        x = w.pop()
        for y in df[x]:
            if y not in saw:
                add v = Φ(...) at start of y
                saw.add(y)
                if y not in defs[v]:
                    w.push(y)

这时变量名还都是原变量名,还不是 SSA,需要做一次 variable renaming。

做法是从 entry 递归向下,一边改新变量名,一边顺便记住最后使用的新变量名,以便后续节点做替换:

def ssa_rename_rec(node, last):
    if node is in saw:
        continue
    saw.add(node)

    for inst in node:  # for each instruction in node
        replace every var used in inst with last[var]
        if inst defined var:  # maybe store inst or Φ-function
            create and replace with new_var name
            last[var] = new_var

    for child of node in dominator tree:
        # child is immediately dominated by this node
        ssa_rename_rec(child, copy(last))

ssa_rename_rec(entry)

Application

《Bringing GNU Emacs to Native Code》 就用到了以上的算法。

可以在 这里 看到整套算法的 lisp 实现。

Reference

《Efficiently computing static single assignment form and the control dependence graph》

《Static Single Assignment Book》