在編譯器的設計中，靜態單賦值形式（static single assignment form，通常簡寫為SSA form或是SSA）是中間表示（IR，intermediate representation)的特性，每個變數僅被賦值一次。在原始的IR中，已存在的變數可被分割成許多不同的版本，在許多教科書當中通常會將舊的變數名稱加上一個下標而成為新的變數名稱，以至於標明每個變數及其不同版本。在SSA中，（use-define chain，賦值代表define，使用變數代表use）是非常明確的，而且每個僅包含單一元素。
SSA於1980年在IBM開始進行研究，它是由Ron Cytron、、Barry K. Rosen、及F. Kenneth Zadeck所開發。
SSA等同於续体传递风格（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）
*[http://llvm.org/devmtg/2007-05/05-Lewycky-Predsimplify.pdf 值域傳播] （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出版）第十九章也是相當有用，詳情請參考此書。
萊斯大學的Keith D. Cooper、Timothy J. Harvey及 Ken Kennedy在他們的文章A Simple, Fast Dominance Algorithm.試圖減少Φ函式的數量，而不承擔高成本的運算活躍變數資訊。這是基於以下的觀察：如果一個變數從未活躍於一個基本的區塊，它就不需要一個Φ函式。在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
參考文獻
- Also available in Java (ISBN 0-521-82060-X 2002) and C (ISBN 0-521-60765-5, 199 8) versions.
*
*
*
*
*
引用
外部連結
- Bosscher, Steven; and Novillo, Diego. [http://lwn.net/Articles/84888/ GCC gets a new Optimizer Framework] . An article about GCC's use of SSA and how it improves over older IRs.
*[http://www.cs.man.ac.uk/~jsinger/ssa.html The SSA Bibliography] . Extensive catalogue of SSA research papers.
- Zadeck, F. Kenneth. [http://webcast.rice.edu/webcast.php?action=details&event=1346 "The Development of Static Single Assignment Form"] , December 2007 talk on the origins of SSA.
评论 (0)