什么是SSA以及SSA的作用

SSA概述

SSA在Go1.7中被引入，这个特性对编译器的性能有很大的提高，但是也导致编译过程有些减速。下面来结合网上的资粮和书籍，简单说明一下SSA以及SSA的应用。

SSA 代表 static single-assignment，是一种IR(中间表示代码)，要保证每个变量只被赋值一次。这个能帮助简化编译器的优化算法。

1
2
3

y := 1
y := 2
x := y

比如上面这段代码，y = 1其实是不可用的，这个要通过定义的可达分析来确定y是要用1还是2，而SSA有一个标识符可以称之为版本或者“代“。

1
2
3

y1 := 1
y2 := 2
x1 := y2

这样就没有任何间接值了。用SSA表示的好处是对于同一个变量的无关使用表示成不同“代”，可以方便很多编译器的优化算法的实现。

一个概念:

Φ(读作fai) 函数，表示要根据控制流赋值的“代”。

例子可以参考维基里的这一段。

三个定义：

A dominate B，如果从起点开始必须通过A到达B。也就是说A是到B的必经之路。

A strictly dominate B，如果 A dominate B，并且A和B不相等。

A 的 dominance frontier 含有B，如果A没有strictly dominate B，但是 dominate 了B的一个前驱节点。

用遍历的方式确定 dominance frontier 的伪代码。

for each node b
    if the number of immediate predecessors of b ≥ 2
        for each p in immediate predecessors of b
            runner := p
            while runner ≠ idom(b)
                add b to runner’s dominance frontier set
                runner := idom(runner)

idom(b) 代表相邻的strictly dominate b的结点。这样的点只有一个，因为相邻的点有两个的话就不会是必经之路了。

如图是一个例子，2的前驱是1和7，7没有sd(strictly dominate) 2，所以把2加入到7的DF(dominate frontiers)当中。3是7的相邻sd，然后3不是2的sd所以2加入到3的DF当中，接着2是3相邻的sd，然后2不是2的sd所以把2加入到2的DF中，最后遍历到7，5和6不是7的sd所以把7加入到5和6的df当中。

df(A)可以认为是可以通过A到达的，但不是必经之路的点的集合。

有了这个定义以后就可以插入Φ函数了和重命名了。如果X中有定义a那么所有df(X)都需要a的Φ函数。并且Φ函数本身也是一个定义。

比如还是同一个例子。

1当中有j的定义，但是df(1)是空的，5当中有j的定义，并且5的df有7所以7当中要插入一个φ(j, j)。j现在在7中定义了(通过φ函数）所以df(7)中的2也要有φ(j, j)，6也有j的定义但是7已经有了φ函数了，2的df有2，但是2已经有φ函数了。类似的方式可以应用到i和k。接着对定义重命名就可以完成SSA的转换了。

SSA的应用

上面只是通俗的解释了一下SSA，没有给出更多详细的理论和算法以及证明，因为证明实在难看懂，下面说一下SSA的应用。

DEAD CODE 消除

因为每个变量都有“代”（因为大家都只被赋值一次），所以很容易检查出没有被使用的变量并且删除对应的定义。另外如果删除v=x这样的定义还要在x的use表中把这条语句删除。

简单的常量扩展

比如v = φ(c1,c2,...,cn)这种格式，如果c都是相等的可以直接替换成c，或者v=c，如果c是常量的话也可以直接替换掉。在做这些的同时也可以做其他的优化，能够在一趟遍历中都完成，比如copy propagation，x=y或者x=φ(y)都可以直接用y替换掉x。比如constant folding，x=a+b如果a+b是常量的话，可以直接用常量赋值。

当然还有其他的优化算法，出发点都是基于SSA的简单性。

从SSA转换回原始代码

y = φ(x1, x2, x3)这样的形式要根据条件分支再拆分回原来的形态，比如满足1条件，使用y=x1这样的形式。并且可能会很自然的想把x1和x2变回使用同一个寄存器，但是通过优化过程中的一些手段(copy propagation)已经把大部分move指令给优化掉了，并且重新推回x可能会有生命周期的影响，所以还是保留了“代”。

总结

其实这个就是把def-use换成了use-def方便做代码优化呀：）害我看那么久

参考文献

虎书第十九章
维基百科