编译器后端寄存器分配算法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使得每个变量都有唯一的定义，因此数据流分析和优化算法可以更加简单
• 使用-定义关系链所消耗空间从指数增长降低为线性增长。若一个变量有N个使用和M个定义，若不采用SSA，则存在M×N个使用-定义关系。
• SSA中因为使用和定义的关系更加的精确，能简化构建干扰图的算法
• 源程序中对同一个变量的不相关的若干次使用，在SSA形式中会转变成对不同变量的使用，因此能消除很多不必要的依赖关系。

有了精确的对象使用–定义关系，许多利用使用–定义关系的优化就能更精确、更彻底、更高效。如

• 常数传播
• 死代码删除
• 全局
• 部分冗余删除
• 强度削弱
• 寄存器分配

2.1 SSA与寄存器分配

讲了这么多有关SSA的优点，接下来介绍一下一般编译器构建SSA的方式。

3.1 从普通中间表示到SSA

3.2 从SSA到普通中间表示

为什么还要从SSA转换回去呢？很简单，处理器不能直接执行PHI节点对应的操作。最简单的做法，直接拷贝，如下图所示：

out of ssa

但这样有一个问题，如下图。简单的拷贝算法可能改变代码的语义：

out of ssa problem

正确的做法：

• 对PHI节点的操作数和结果重命名，使其名称相同，即变成同一个变量
• 再在分支中插入拷贝操作

4.1 数组、指针等别名

4.2 堆上的存储

4.3 复合结构–结构体

GCC的SSA

• tree-ssa.c
• tree-into-ssa.c:将函数转换为SSA形式，插入PHI节点，对于未初始化的变量给出警告。
• tree-ssa-dce.c:扫描整个函数，标记无副作用且结果并未被使用的语句，所有存储操作都视为有副作用。
• tree-ssa-dom.c:支配关系相关优化：复写传播、常数传播、表达式简化、冗余消除、Jump Threading？
• tree-ssa-forwprop.c:前向传播单一引用变量，通过将仅使用一次的变量用相应的表达式替代来尝试容易删除。
• tree-ssa-copyrename.c:尝试将由拷贝动作产生的SSA变量用原变量替换之，优化符号表。
• tree-ssa-phiopt.c: 识别表达条件表达式的phi节点，并将其重写为直线代码。
• tree-ssa-alias.c:流敏感基于SSA的指向分析，得到可能-别名，一定-别名和逃逸分析信息。 这些信息将用于将变量从内存中地址可用对象提升为非别名变量，这样这些变量就能使用SSA形式的分析和优化了。
• tree-ssa-structalias.c:用于过程间的指向分析。
• tree-sra.c:将合适的无别名局部复合变量转换为一个标量集合，并进而转换为SSA形式。
• tree-ssa-dse.c:删除那些无用的存储操作
• tree-ssa-sink.c:将存储和赋值语句尽量下沉到和它们的使用点接近的位置。
• tree-ssa-pre.c:部分冗余删除、load语句移动、完全冗余删除
• tree-ssa-loop.c: SSA形式的循环优化
  • tree-ssa-loop-im.c:循环无关语句移动
  • tree-ssa-loop-ivcanon.c:循环标准化
  • tree-ssa-loop-ivopts.c:索引变量优化
  • tree-ssa-loop-unswitch.c:将循环无关的条件跳转移到循环外
  • tree-vectorizer.c, tree-vect-analyze.c, tree-vect-transform.c:自动向量化
• tree-ssa-ccp.c:条件常数传播
• tree-ssa-copy.c:条件复写传播
• tree-vrp.c:取值范围传播
• tree-outof-ssa.c:从SSA形式转换回普通形式

open64中的SSA主要用于循环嵌套优化、过程间优化以及普通的函数内优化。 除了循环变换和内联优化外的所有机器无关优化都基于SSA做。 这部分可以说是Open64的重要卖点，对应的代码在osprey/be/opt下。

Open64在没有过程间优化时，主要以函数为单位进行，基于控制流图和别名分析得到的信息构建SSA。

• opt_goto.cxx：goto语句转换，方便做SSA
• opt_loop.cxx：循环正规化
• opt_sym.cxx：构建相关符号表
• opt_alias_class.cxx：别名分类，方便别名分析
• opt_cfg.cxx：构建控制流图，包括支配树，不可到达代码识别，if语句转换
• opt_tail.cxx：尾递归消除
• opt_alias_analysis.cxx：流无关别名分析
• opt_ssa.cxx：构建基于WHIRL的SSA
• opt_dse.cxx：死store删除
• opt_htable.cxx：构建HSSA–基于哈希的全局值编号SSA
• opt_ivr.cxx：索引变量标准化
• opt_prop.cxx：复写传播
• opt_revise_ssa.cxx：将非直接变量展开成直接变量
• opt_dce.cxx：死代码删除
• opt_cfg_trans.cxx：控制流转换
• opt_rename.cxx：SSA变量重命名、更新
• opt_du.cxx：构建define-use信息
• opt_etable.cxx：基于表达式的部分冗余删除
• opt_estr.cxx：强度削弱
• opt_ehoist.cxx：代码提升
• opt_lftr2.cxx：线性代码测试、替换
• opt_vn.cxx：基于值编号的完全冗余删除
• opt_ltable.cxx：针对load的部分冗余删除
• opt_stable.cxx：store Partial Redundancy Elimination 针对store的部分冗余删除
• opt_bdce.cxx： Bitwise dead code elimination–针对结构体
• opt_htable_emit.cxx: 从SSA转换回WHIRL中间表示

• http://en.wikipedia.org/wiki/Static_single_assignment_form
• http://en.wikipedia.org/wiki/SpiderMonkey_%28JavaScript_engine%29
• Advanced Compiler Design and Implementation, by Steven S. Muchnick, Page 252-265
• Modern Compiler Implementation in C， by Andrew W. Appel, Page 433-473
• Crafting A Compiler, by Charles N. Fischer, etc , Page 410-414
• 8. Static Single Assignment Form， by Marcus Denker, http://marcusdenker.de/talks/08CC/08IntroSSA.pdf
• Effective Representation of Aliases and Indirect Memory Operations in SSA Form, Fred Chow, Sun Chan, etc. Compiler Construction 1996