SSA_form

在編譯器的設計中，**靜態單賦值形式**（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。

## 使用 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）

## 轉換成 SSA

將程式碼轉換為 SSA 形式，最簡單的方法，就是將每個被賦值的變數，以一個新的變數來取代，而新的變數名稱則為一個帶著**版號**的舊變數，舉例來說：

我們可以改變 "x $\leftarrow $ x - 3" 左值的名稱，以及改變變數 x 的使用名稱，而程式仍然做著相同的事情。我們在 SSA 利用這個方式，建立兩個新的變數 x1 及 x2，每個變數僅賦值一次，我們同樣的給予其他變數相同的形式，可以得到：

但還有一件事情還未完成：y 在底層區塊的使用，可以被指定為 y1 亦或是 y2，這得根據它流程的來源來決定，所以我們該如何知道要使用哪一個？

答案是，我們增加一個特別的描述，稱之為 _Φ （Phi）函式_，作為最後一個區塊的起始，這個描述將會產生一個新的定義 y3，會根據程式運作的路徑來選擇 y1 或 y2：

現在，在最後一個區塊 y 的使用，可以僅使用 y3，而且他們都可以得到正確的數值，此時你可能會問我們需要在 x 變數增加 Φ 函式嗎？這個答案是否定的，只有一個版本的 x，也就是 x2 就可以得到最後的結果，所以它沒有這個問題。

這是一個普遍的問題，給予一個任意的控制流程圖，我該如何插入 Φ 函式？或是用在哪一個變數？這是一個困難的問題，但是有一個有效率的解決方法，被稱為 **支配邊界（dominance frontiers）** 。

注意到：Φ 函式並不是真的被實現，取而代之的，他們只是編譯器的標註用以代表所有變數的數值，將所有數值用 Φ 函式在一個記憶體位置（所示相同的暫存器）群組起來。

根據 Kenny Zadeck 表示，當 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 的定義是不需要 Φ 函式。

 
用來計算支配邊界集合的演算法為：

```
**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_. 中所描述，這個演算法使用了精心設計的資料結構來改進效能。

## 減少 Φ 函式的數量

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

然而，有些 Φ 函式可能會變成無用的程式碼，因為這個原因，最小化 SSA 並不一定生產最少數量的 Φ 函式而且需要特定程式，有些型態的分析，這些 Φ 函式是多餘的，而且可能會導致分析效能低落。

### 精簡的 SSA

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

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

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

### 半精簡的 SSA

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

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

## 透過 SSA 轉換出來的程式

SSA 轉換出來的程式，通常不是用來直接執行（雖然透過直譯 SSA 的方式，這是可能發生），它經常被使用在其他保留直接對應的 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_ 的延伸保留變數單一賦值的特性，而且將它合併到新的語意，這些延伸造就了高階程式語言的一些新特色，像是陣列、物件及指標。其他造就了低階結構的一些新特色，像是推測及預測。

## 參見

* 編譯器最佳化
* Valgrind

## 參考文獻

* Appel, Andrew W. Modern Compiler Implementation in ML. Cambridge University Press. 1999. ISBN 0-521-58274-1.  Also available in Java (ISBN 0-521-82060-X 2002) and C (ISBN 0-521-60765-5, 199 8) versions.
* Cooper, Keith D.; and Torczon, Linda. Engineering a Compiler. Morgan Kaufmann. 2003. ISBN 1-55860-698-X.
* Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann. 1997. ISBN 1-55860-320-4.
* Kelsey, Richard A. A Correspondence between Continuation Passing Style and Static Single Assignment Form. ACM SIGPLAN Notices. March 1995, **30** (3): 13–22. doi:10.1145/202530.202532.
* Appel, Andrew W. SSA is Functional Programming. ACM SIGPLAN Notices. April 1998, **33** (4): 17–20. doi:10.1145/278283.278285.
* Pop, Sebastian. The SSA Representation Framework: Semantics, Analyses and GCC Implementation (PDF). 2006 [2010-06-15]. （原始內容存檔 (PDF) 於 2011-04-26）.

## 外部連結

* Bosscher, Steven; and Novillo, Diego. GCC gets a new Optimizer Framework （頁面存檔備份，存於網際網路檔案館）. An article about GCC's use of SSA and how it improves over older IRs.
* The SSA Bibliography （頁面存檔備份，存於網際網路檔案館）. Extensive catalogue of SSA research papers.
* Zadeck, F. Kenneth. "The Development of Static Single Assignment Form" （頁面存檔備份，存於網際網路檔案館）, December 2007 talk on the origins of SSA.