维基百科

静态单赋值形式

在编译器的设计中，静态单赋值形式（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”