精确的数据流分析是让编译优化能高效进行的基础。 SSA就是一种高效的数据流分析技术，目前几乎所有的现代编译器，如GCC、Open64、LLVM都有将SSA技术的支持， 不仅仅是编译器，Jikes RVM, HotSpot JVM, .Net的Mono，Python的Pypy， Andoroid的Dalvik，这些虚拟机/解释器中的Just-in-Time Compiler也有了SSA的支持。 Firefox的下一代JavaScript引擎IonMonkey中，也将为其JIT引入SSA。
可以看到，几乎所有热门的语言所用的热门编译器/解释器/虚拟机中都有了SSA。
SSA即静态单赋值，Static Single-Assignment，这是一种中间表示形式。 之所以称之为单赋值，是因为每个名字在SSA中仅被赋值一次.
如下图中的一段程序的控制流图。从这张图中可以看到，最后一个基本块中y值的定义或者来自左侧的分支，或者来自右侧的分支。
SSA_example1.1
将每个赋值语句中的变量赋予一个唯一的名称后，一般新名称采用原变量+版本号（Version）的形式。 对于上面这段控制流图，就变成如下形式：
SSA_example1.2
这张图中有个问题，有分支时，若分支中有对变量的操作，就无法确定使用了哪个版本的变量。 因此，引入了PHI节点。如下图所示：
SSA_example1.3
PHI将分支中的y1和y2连接，并生成一个新的定义y3。有了PHI节点后，最后一个基本块中y3的定义来自之前的PHI节点，PHI节点中的两个操作数y1和y2分别来自左右两个分支。
在SSA中间表示中，可以保证每个被使用的变量都有唯一的定义，即SSA能带来精确的使用–定义关系。 而在图SSA_example1.1中的y值定义却非常模糊。
概括起来，SSA带来四大益处：
有了精确的对象使用–定义关系，许多利用使用–定义关系的优化就能更精确、更彻底、更高效。如
因为SSA使得依赖分析更加简单、精确，而且PHI节点中的变量不可能同时活跃。因此在SSA形式能协助完成寄存器分配。 实际上，GCC最早的SSA就是GCC 3中RTL阶段。
讲了这么多有关SSA的优点，接下来介绍一下一般编译器构建SSA的方式。
两步走战略：
此外，为了节省内存空间，简化SSA上的算法，我们需要将插入的PHI节点数目最小化。 因为PHI节点本身只是一个概念性的节点，若插入过多不必要的PHI节点，算法就需要在控制流图的汇聚点针对每个分支做分析。 可以借用变量的支配边界（dominance frontier)进行PHI节点数目最消化。一般都通过直接计算支配边界的方式插入PHI节点。
为什么还要从SSA转换回去呢？很简单，处理器不能直接执行PHI节点对应的操作。最简单的做法，直接拷贝，如下图所示：
out of ssa
但这样有一个问题，如下图。简单的拷贝算法可能改变代码的语义：
out of ssa problem
正确的做法：
上面关于SSA的讨论基本都是针对单个简单变量的SSA操作，那么对于复杂的指针、数组之类的访存,SSA应该如何处理呢？ 数组和指针使得编译器无法确定define和use的具体变量。
参考资料7给出了一种定义方式，通过引入maydef，mayuse和zero version使得编译器也能对别名（即指针和数组）存在的程序做SSA分析。 若通过指针为其所指区域赋值，就在此处插入maydef，表示可能对变量做了定义。同理，对使用指针所指向区域的值的，就插入一个mayuse。 因为无法确定指针所指向的到底是哪个变量，为了正确性，需要对所有变量都插入maydef动作。同样mayuse也是针对所有变量的。
当指针操作较多时，这种方式就会引入过多的新变量版本。因此就增加了zero version。 zero version的作用就是尽量把maydef所带来的版本数降低。 将那些很可能不会别名的都使用相同的zero version。 比如某个变量通过maydef产生了一个新版本之后，若还会有新的maydef操作，则直接生成zero version，不再生成新的version。
在堆上分配的存储空间，一般编译器都将整个堆看作一个对象，来做SSA。
因为结构体也是由很多元素构成的，所以就存在两种处理方式：把结构体整个看作一个整体做SSA、把结构体的每个元素看作一个对象做SSA。 后者相比前者，因为分的更细，在结构体操作频繁的程序中能带来不错的优化效果。
GCC的SSA
open64中的SSA主要用于循环嵌套优化、过程间优化以及普通的函数内优化。 除了循环变换和内联优化外的所有机器无关优化都基于SSA做。 这部分可以说是Open64的重要卖点，对应的代码在osprey/be/opt下。
Open64在没有过程间优化时，主要以函数为单位进行，基于控制流图和别名分析得到的信息构建SSA。
| 您可能也喜欢： |
Open64 课程–全局标量优化(WOPT II)
|
|
Open64 课程–全局标量优化(WOPT I) part II
|
|
open64课程–过程间分析优化(IPA)
|
|
Open64 课程–全局标量优化(WOPT I) part 1
|
|
Open64课程–反馈指导优化(FDO)
|
| 无觅 |