静态单赋值形式

在编译器的设计中，静态单赋值形式（static single assignment form，通常简写为SSA form或是SSA）是中介码（IR，intermediate representation)的特性，每个变数仅被赋值一次。在原始的IR中，已存在的变数可被分割成许多不同的版本，在许多教科书当中通常会将旧的变数名称加上一个下标而成为新的变数名称，以至于标明每个变数及其不同版本。在SSA，UD链（use-define chain，赋值代表define，使用变数代表use）是非常明确，而且每个仅包含单一元素。

简介SSA于1980年在IBM开始进行研究，它是由Ron Cytron、Jeanne Ferrante、Barry K. Rosen、Mark N. Wegman及F. Kenneth Zadeck所开发。

SSA同等于一个持续传递式样（CPS，continuation-passing style）的子集（不包含非本地端控制流程。当CPS被使用在IR，前者就不会发生），所以任何最佳化及转换，都会适用于CPS。当我们期待在C或是Fortran的编译器中使用SSA时，CPS已被广泛地使用在函数编程语言的编译器中，像是Scheme、ML及Haskell。1

使用SSA的优势SSA最主要的用途，是借由简化变数的特性，来进行简化及改进编译器最佳化的结果，举例来说：

y := 1 y := 2 x := y从上面的描述所知，第一行赋值行为是不需要的，因为y在第二行被二度赋值，y的数值在第三行被使用，一个程式通常会进行定义可达性分析（reaching definition analysis）来测定它。在SSA下，将会变成下列的形式：

y1 := 1 y2 := 2 x1 := y2编译器最佳化的算法，可以借由SSA的使用，达到以下的改进：

常数传播（constant propagation）

值域传播（value range propagation）

稀疏有条件的常数传播（sparse conditional constant propagation）

消除无用的程式码（dead code elimination）

全域数值编号 （global value numbering）

消除部分的冗余 （partial redundancy elimination）

强度折减（strength reduction）

暂存器配置（register allocation）1

利用支配边界计算出最小的SSA首先，我们需要Graph中支配点（Dominator）的观念：当一个点A到点B在控制流程图中，如果没有其他的路线，那么A及B就是支配点。这是相当有用的，因为如果程式进行到B就代表着A一定也会执行到，我们可以说A支配着B（B也支配着A）。

现在我们可以定义支配边界：如果A没有直接支配着B但是支配着一个B的前置程序，则节点B就是点A的支配边界（有可能点A是点B的前置程序，那么，因为任何一个点都支配着自己，点A也支配着自己，所以点A也是点B的支配边界），从A的观点来看，还有点在其他没有经过A的控制路径，可以使他们更早出现。

支配边界取得了需要Φ函式的精确的位置：如果点A定义了一个变数，那个这个变数将会达到所有点A的支配点，只有在当我们离开这些点，而且进入支配边界，我们才必须考虑其他流程会带着其它相同变数的定义。还有，在控制流程图中处理A的定义是不需要Φ函式。

用来计算支配边界集合的算法为：

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)注意：在上述的程式码，一个前置处理程序点N，是任意节点到达点N，idom(b)代表支配点B。

这是一个有效率的算法，用以寻找每个点的支配边界，这个算法最早由Cytron等于1991年提出。在由Andrew Appel所写的 "Modern compiler implementation in Java" （2002年由Cambridge University出版）第十九章也是相当有用，详情请参考此书。

Rice University的Keith D. Cooper、Timothy J. Harvey及 Ken Kennedy在他们的文章A Simple, Fast Dominance Algorithm.中所描述，这个算法使用了精心设计的数据结构来改进效能。2

减少Φ函式的数量要最小化SSA就必须放入最小数量的Φ函式，同时仍需要确保每个变数仅被赋予一次数值，而且每个变数在原始程式的参考仍旧可以指到一个独立的变数。（后面叙述的要求，是用来确保编译器在每次的操作可以写下每个运算子）

然而，有些Φ函式可能会变成无用的程式码，因为这个原因，最小化SSA并不一定生产最少数量的Φ函式而且需要特定程序，有些型态的分析，这些Φ函式是多余的，而且可能会导致分析效能低落。2

精简的SSA精简的SSA（Purned SSA form）是基于一个简单的观察：Φ函式只在一种情形下需要，就是变数在Φ函式运行之后依然活跃的时候（依然活跃代表这个数值被使用在一些路径，这些路径是以Φ函式为起点）。如果一个变数已经不再被使用，Φ函式的结果无法被使用，而且是被一个已经无用的Φ函式所赋值。

在插入Φ函式的阶段，使用活跃变数资讯（Live variable information）来决定Φ函式是否需要，以此方法建构一个精简的SSA。如果原始变数名称在Φ函式插入点内已经不再使用，则Φ函式将不会被插入。

其他的可能，是将精简化看作解决消除无用程式码问题。只有在输入的程式，不论如何使用，都将会被改写，不然就是作为其他Φ函式的参数，我们才会认为这个Φ函式是活跃的。当进入SSA形式，每个使用情况都会被该改为最接近的定义，这个定义支配着它，一个Φ函式接着将会被视为活跃的，只要最接近的定义仍然支配至少一个使用，或是一个活跃的Φ的参数。2

半精简的 SSA半精简的SSA（Semi-pruned SSA form）试图减少Φ函式的数量，而不承担高成本的运算活跃变数资讯。这是基于以下的观察：如果一个变数从未活跃于一个基本的区块，它就不需要一个Φ函式。在SSA的建构，将省略任何本地区块变数使用的Φ函式。

计算本地区块变数的集合，比起活跃变数分析，是一个简单而且快速的程序，这让半精简的SSA比起精简的SSA在计算上更有效率，换句话说，半精简的SSA将会包含较多的Φ函式。2

透过SSA转换出来的程式SSA转换出来的程式，通常不是用来直接执行（虽然透过直译SSA的方式，这是可能发生），它经常被使用在其他保留直接对应的IR上面，这可以借由将SSA建构为一个函式的集合所完成，函式的集合会对应部分的IR（基本区块、指令、运算子等等）以及它的SSA副本。当SSA不再被需要时，这些对应函式就会被拿掉，只留下最佳化过的IR。

SSA的最佳化通常会导致混乱的SSA网络（SSA-Webs），因为这些Φ指令的运算子并没有全部都有相同的根运算子，在这样的情况之下，可利用Color-out算法，初始的算法提出，作一个副本，用来计算每个前置处理的路径，这些路径若导致不同根符号的来源将被放入Φ，而非Φ的终点。还有许多算法用来解决这些问题，有些会使用更少的副本，多数是使用干扰图形（interference graph）或是将相近的副本合并。2

延伸SSA的延伸可以被分作两个类别：

Renaming scheme的延伸改变了命名的标准，还记得SSA重新命名每个被赋值的变数，替代的方案包含静态单一使用形式（static single use form，在每个描述内使用该变数时，该变数才会重新命名）及静态单一资讯形式（static single information form，每个被赋值的变数并且在支配边界前将会被重新命名）

Feature-specific的延伸保留变数单一赋值的特性，而且将它合并到新的语意，这些延伸造就了高阶编程语言的一些新特色，像是阵列、物件及指标。其他造就了低阶结构的一些新特色，像是推测及预测。2

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所