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
``````

# SSA

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

# dominator tree

Domination 具有自反性（`X dom X`）和传递性（`X dom Y, Y dom Z => X dom Z`）。

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

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

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

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

# dominance frontier

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

# Dominance algorithm

``````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
``````

`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
``````

``````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
``````

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

# φ-function insertion and variable renaming

``````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
if y not in defs[v]:
w.push(y)
``````

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

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》 就用到了以上的算法。

# Reference

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

《Static Single Assignment Book》