维基百科

静态单赋值形式

在编译器的设计中，静态单赋值形式（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）的子集（不包含非本地端控制流程。当CPS被使用在IR，前者就不会发生），所以任何优化及转换，都会适用于CPS。当我们期待在C或是Fortran的编译器中使用SSA时，CPS已被广泛地使用在函数编程语言的编译器中，像是Scheme、ML及Haskell。

使用SSA的优势

编辑

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

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

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

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

编译器优化的算法，可以借由SSA的使用，达到以下的改进：

转换成SSA

编辑

将代码转换为SSA形式，最简单的方法，就是将每个被赋值的变量，以一个新的变量来取代，而新的变量名称则为一个带着版号的旧变量，举例来说：

 

我们可以改变"x   x - 3"左值的名称，以及改变变量x的使用名称，而程序仍然做着相同的事情。我们在SSA利用这个方式，建立两个新的变量x1及x2，每个变量仅赋值一次，我们同样的给予其他变量相同的形式，可以得到：

 

但还有一件事情还未完成：y在底层区块的使用，可以被指定为y1亦或是y2，这得根据它流程的来源来决定，所以我们该如何知道要使用哪一个？

答案是，我们增加一个特别的描述，称之为Φ （Phi）函数，作为最后一个区块的起始，这个描述将会产生一个新的定义y3，会根据程序运作的路径来选择y1或y2：

 

现在，在最后一个区块y的使用，可以仅使用y3，而且他们都可以得到正确的数值，此时你可能会问我们需要在x变量增加Φ函数吗？这个答案是否定的，只有一个版本的x，也就是x2就可以得到最后的结果，所以它没有这个问题。

这是一个普遍的问题，给予一个任意的控制流程图，我该如何插入Φ函数？或是用在哪一个变量？这是一个困难的问题，但是有一个有效率的解决方法，被称为 支配边界（dominance frontiers）。

注意到：Φ函数并不是真的被实现，取而代之的，他们只是编译器的标注用以代表所有变量的数值，将所有数值用Φ函数在一个存储器位置（所示相同的寄存器）组群起来。

根据Kenny Zadeck [1]表示，当SSA一开始于IBM发展时(1980年)，Φ函数最初被称为 phoney 函数，正式的名称，也就是Φ函数仅在第一次发表的时候出现。

利用支配边界计算出最小的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的定义是不需要Φ函数。


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

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年提出[3]。在由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并不一定生产最少数量的Φ函数而且需要特定程序，有些类型的分析，这些Φ函数是多余的，而且可能会导致分析性能低落。

精简的SSA

编辑

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

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

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

半精简的 SSA

编辑

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

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

透过SSA转换出来的程序

编辑

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

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

延伸

编辑

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

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

Feature-specific 的延伸保留变量单一赋值的特性，而且将它合并到新的语义，这些延伸造就了高级编程语言的一些新特色，像是数组、对象及指针。其他造就了低端结构的一些新特色，像是推测及预测。

参见

编辑

参考文献

编辑
  1. ^ Zadeck, F. Kenneth, Presentation on the History of SSA at the SSA'09 Seminar （页面存档备份，存于互联网档案馆）, Autrans, France, April 2009
  2. ^ 2.0 2.1 Cooper, Keith D.; Harvey, Timothy J.; and Kennedy, Ken. A Simple, Fast Dominance Algorithm (PDF). 2001 [2013-02-08]. （原始内容 (PDF)存档于2021-05-06）. 
  3. ^ Cytron, Ron; Ferrante, Jeanne; Rosen, Barry K.; Wegman, Mark N.; and Zadeck, F. Kenneth. Efficiently computing static single assignment form and the control dependence graph (PDF). ACM Transactions on Programming Languages and Systems. 1991, 13 (4): 451–490 [2013-02-08]. doi:10.1145/115372.115320. （原始内容 (PDF)存档于2021-05-06）. 
  4. ^ Briggs, Preston; Cooper, Keith D.; Harvey, Timothy J.; and Simpson, L. Taylor. Practical Improvements to the Construction and Destruction of Static Single Assignment Form (PDF). 1998. （原始内容 (PDF)存档于2010-06-07）. 
  5. ^ von Ronne, Jeffery; Ning Wang; Michael Franz. Interpreting programs in static single assignment form. 2004. 

外部链接

编辑
检索自“https://zh.wikipedia.org/w/index.php?title=静态单赋值形式&oldid=81637872”