在編譯器的設計中，靜態單賦值形式（static single assignment form，通常簡寫為SSA form或是SSA）是中介碼（IR，intermediate representation)的特性，每個變數僅被賦值一次。在原始的IR中，已存在的變數可被分割成許多不同的版本，在許多教科書當中通常會將舊的變數名稱加上一個下標而成為新的變數名稱，以至於標明每個變數及其不同版本。在SSA，UD鏈（use-define chain，賦值代表define，使用變數代表use）是非常明確，而且每個僅包含單一元素。
基本介紹
- 中文名：靜態單賦值形式
- 外文名：static single assignment form
- 簡寫：SSA
- 領域：計算機
簡介,使用SSA的優勢,利用支配邊界計算出最小的SSA,減少Φ函式的數量,精簡的SSA,半精簡的 SSA,透過SSA轉換出來的程式,延伸,
簡介
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
首先，我們需要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-pruned 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的延伸保留變數單一賦值的特性，而且將它合併到新的語意，這些延伸造就了高階程式語言的一些新特色，像是陣列、物件及指標。其他造就了低階結構的一些新特色，像是推測及預測。
