[科普中國]-靜態(tài)單賦值形式

在編譯器的設計中，靜態(tài)單賦值形式（static single assignment form，通常簡寫為SSA form或是SSA）是中介碼（IR，intermediate representation)的特性，每個變數(shù)僅被賦值一次。在原始的IR中，已存在的變數(shù)可被分割成許多不同的版本，在許多教科書當中通常會將舊的變數(shù)名稱加上一個下標而成為新的變數(shù)名稱，以至于標明每個變數(shù)及其不同版本。在SSA，UD鏈（use-define chain，賦值代表define，使用變數(shù)代表use）是非常明確，而且每個僅包含單一元素。

簡介SSA于1980年在IBM開始進行研究，它是由Ron Cytron、Jeanne Ferrante、Barry K. Rosen、Mark N. Wegman及F. Kenneth Zadeck所開發(fā)。

SSA同等于一個持續(xù)傳遞式樣（CPS，continuation-passing style）的子集（不包含非本地端控制流程。當CPS被使用在IR，前者就不會發(fā)生），所以任何最佳化及轉換，都會適用于CPS。當我們期待在C或是Fortran的編譯器中使用SSA時，CPS已被廣泛地使用在函數(shù)編程語言的編譯器中，像是Scheme、ML及Haskell。1

使用SSA的優(yōu)勢SSA最主要的用途，是借由簡化變數(shù)的特性，來進行簡化及改進編譯器最佳化的結果，舉例來說：

y := 1 y := 2 x := y從上面的描述所知，第一行賦值行為是不需要的，因為y在第二行被二度賦值，y的數(shù)值在第三行被使用，一個程式通常會進行定義可達性分析（reaching definition analysis）來測定它。在SSA下，將會變成下列的形式：

y1 := 1 y2 := 2 x1 := y2編譯器最佳化的算法，可以借由SSA的使用，達到以下的改進：

常數(shù)傳播（constant propagation）

值域傳播（value range propagation）

稀疏有條件的常數(shù)傳播（sparse conditional constant propagation）

消除無用的程式碼（dead code elimination）

全域數(shù)值編號 （global value numbering）

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

強度折減（strength reduction）

暫存器配置（register allocation）1

利用支配邊界計算出最小的SSA首先，我們需要Graph中支配點（Dominator）的觀念：當一個點A到點B在控制流程圖中，如果沒有其他的路線，那么A及B就是支配點。這是相當有用的，因為如果程式進行到B就代表著A一定也會執(zhí)行到，我們可以說A支配著B（B也支配著A）。

現(xiàn)在我們可以定義支配邊界：如果A沒有直接支配著B但是支配著一個B的前置程序，則節(jié)點B就是點A的支配邊界（有可能點A是點B的前置程序，那么，因為任何一個點都支配著自己，點A也支配著自己，所以點A也是點B的支配邊界），從A的觀點來看，還有點在其他沒有經(jīng)過A的控制路徑，可以使他們更早出現(xiàn)。

支配邊界取得了需要Φ函式的精確的位置：如果點A定義了一個變數(shù)，那個這個變數(shù)將會達到所有點A的支配點，只有在當我們離開這些點，而且進入支配邊界，我們才必須考慮其他流程會帶著其它相同變數(shù)的定義。還有，在控制流程圖中處理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，是任意節(jié)點到達點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.中所描述，這個算法使用了精心設計的數(shù)據(jù)結構來改進效能。2

減少Φ函式的數(shù)量要最小化SSA就必須放入最小數(shù)量的Φ函式，同時仍需要確保每個變數(shù)僅被賦予一次數(shù)值，而且每個變數(shù)在原始程式的參考仍舊可以指到一個獨立的變數(shù)。（后面敘述的要求，是用來確保編譯器在每次的操作可以寫下每個運算子）

然而，有些Φ函式可能會變成無用的程式碼，因為這個原因，最小化SSA并不一定生產(chǎn)最少數(shù)量的Φ函式而且需要特定程序，有些型態(tài)的分析，這些Φ函式是多余的，而且可能會導致分析效能低落。2

精簡的SSA精簡的SSA（Purned SSA form）是基于一個簡單的觀察：Φ函式只在一種情形下需要，就是變數(shù)在Φ函式運行之后依然活躍的時候（依然活躍代表這個數(shù)值被使用在一些路徑，這些路徑是以Φ函式為起點）。如果一個變數(shù)已經(jīng)不再被使用，Φ函式的結果無法被使用，而且是被一個已經(jīng)無用的Φ函式所賦值。

在插入Φ函式的階段，使用活躍變數(shù)資訊（Live variable information）來決定Φ函式是否需要，以此方法建構一個精簡的SSA。如果原始變數(shù)名稱在Φ函式插入點內(nèi)已經(jīng)不再使用，則Φ函式將不會被插入。

其他的可能，是將精簡化看作解決消除無用程式碼問題。只有在輸入的程式，不論如何使用，都將會被改寫，不然就是作為其他Φ函式的參數(shù)，我們才會認為這個Φ函式是活躍的。當進入SSA形式，每個使用情況都會被該改為最接近的定義，這個定義支配著它，一個Φ函式接著將會被視為活躍的，只要最接近的定義仍然支配至少一個使用，或是一個活躍的Φ的參數(shù)。2

半精簡的 SSA半精簡的SSA（Semi-pruned SSA form）試圖減少Φ函式的數(shù)量，而不承擔高成本的運算活躍變數(shù)資訊。這是基于以下的觀察：如果一個變數(shù)從未活躍于一個基本的區(qū)塊，它就不需要一個Φ函式。在SSA的建構，將省略任何本地區(qū)塊變數(shù)使用的Φ函式。

計算本地區(qū)塊變數(shù)的集合，比起活躍變數(shù)分析，是一個簡單而且快速的程序，這讓半精簡的SSA比起精簡的SSA在計算上更有效率，換句話說，半精簡的SSA將會包含較多的Φ函式。2

透過SSA轉換出來的程式SSA轉換出來的程式，通常不是用來直接執(zhí)行（雖然透過直譯SSA的方式，這是可能發(fā)生），它經(jīng)常被使用在其他保留直接對應的IR上面，這可以借由將SSA建構為一個函式的集合所完成，函式的集合會對應部分的IR（基本區(qū)塊、指令、運算子等等）以及它的SSA副本。當SSA不再被需要時，這些對應函式就會被拿掉，只留下最佳化過的IR。

SSA的最佳化通常會導致混亂的SSA網(wǎng)絡（SSA-Webs），因為這些Φ指令的運算子并沒有全部都有相同的根運算子，在這樣的情況之下，可利用Color-out算法，初始的算法提出，作一個副本，用來計算每個前置處理的路徑，這些路徑若導致不同根符號的來源將被放入Φ，而非Φ的終點。還有許多算法用來解決這些問題，有些會使用更少的副本，多數(shù)是使用干擾圖形（interference graph）或是將相近的副本合并。2

延伸SSA的延伸可以被分作兩個類別：

Renaming scheme的延伸改變了命名的標準，還記得SSA重新命名每個被賦值的變數(shù)，替代的方案包含靜態(tài)單一使用形式（static single use form，在每個描述內(nèi)使用該變數(shù)時，該變數(shù)才會重新命名）及靜態(tài)單一資訊形式（static single information form，每個被賦值的變數(shù)并且在支配邊界前將會被重新命名）

Feature-specific的延伸保留變數(shù)單一賦值的特性，而且將它合并到新的語意，這些延伸造就了高階編程語言的一些新特色，像是陣列、物件及指標。其他造就了低階結構的一些新特色，像是推測及預測。2

本詞條內(nèi)容貢獻者為:

王沛 - 副教授、副研究員 - 中國科學院工程熱物理研究所