静态单赋值

静态单赋值(SSA)是中间代码的一个特性,如果一个中间代码具有静态单赋值的特性,那么每个变量就只会被赋值一次,在实践中我们通常会用添加下标的方式实现每个变量只能被赋值一次的特性,这里以下面的代码举一个简单的例子:

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

根据分析,我们其实能够发现上述的代码其实并不需要第一个将 1 赋值给 x 的表达式,也就是这一表达式在整个代码片段中是没有作用的:

x1 := 1
x2 := 2
y1 := x2

从使用 SSA 的中间代码我们就可以非常清晰地看出变量 y1 的值和 x1 是完全没有任何关系的,所以在机器码生成时其实就可以省略第一步,这样就能减少需要执行的指令来优化这一段代码。

根据 Wikipedia 对 SSA 的介绍来看,在中间代码中使用 SSA 的特性能够为整个程序实现以下的优化:

  • 常数传播(constant propagation)

  • 值域传播(value range propagation)

  • 稀疏有条件的常数传播(sparse conditional constant propagation)

  • 消除无用的程式码(dead code elimination)

  • 全域数值编号(global value numbering)

  • 消除部分的冗余(partial redundancy elimination)

  • 强度折减(strength reduction)

  • 寄存器分配(register allocation)

从 SSA 的作用我们就能看出,因为它的主要作用就是代码的优化,所以是编译器后端(主要负责目标代码的优化和生成)的一部分;当然,除了 SSA 之外代码编译领域还有非常多的中间代码优化方法,优化编译器生成的代码是一个非常古老并且复杂的领域,这里就不会展开介绍了。