查看“︁静态单赋值形式”︁的源代码

{{noteTA|G1=IT}}
在[[編譯器]]的設計中，'''靜態單賦值形式'''（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 Rosen (computer scientist)|Barry K. Rosen]]、[[Mark N. Wegman]]及[[F. Kenneth Zadeck]]所開發。

SSA等同於一個[[续体传递风格]]（CPS）的子集（不包含非本地端控制流程。當CPS被使用在IR，前者就不會發生），所以任何最佳化及轉換，都會適用於CPS。當我們期待在[[C语言|C]]或是[[Fortran]]的編譯器中使用SSA時，CPS已被廣泛地使用在[[函數程式語言]]的編譯器中，像是[[Scheme]]、[[ML语言|ML]]及[[Haskell]]。

== 使用SSA的優勢 ==
SSA最主要的用途，是藉由簡化變數的特性，來進行簡化及改進編譯器最佳化的結果，舉例來說：

  y := 1
  y := 2
  x := y

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

  y<sub>1</sub> := 1
  y<sub>2</sub> := 2
  x<sub>1</sub> := y<sub>2</sub>

編譯器最佳化的演算法，可以藉由SSA的使用，達到以下的改進：

*[[常數折疊|常數傳播]] （constant propagation）
*[http://llvm.org/devmtg/2007-05/05-Lewycky-Predsimplify.pdf 值域傳播] {{Wayback|url=http://llvm.org/devmtg/2007-05/05-Lewycky-Predsimplify.pdf |date=20210121123555 }}（value range propagation）
*[[稀疏有條件的常數傳播]] （sparse conditional constant propagation）
*[[死碼刪除|消除無用的程式碼]] （dead code elimination）
*全域數值編號 （global value numbering）
*消除部分的冗餘 （partial redundancy elimination）
*[[強度折減]] （strength reduction）
*[[暫存器配置]] （register allocation）

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

<center>
[[Image:SSA example1.1.png|轉換為SSA之前的控制流程圖]]
</center>

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

<center>
[[Image:SSA example1.2.png|部分轉換到SSA的範例]]
</center>

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

答案是，我們增加一個特別的描述，稱之為''Φ （Phi）函式''，作為最後一個區塊的起始，這個描述將會產生一個新的定義<var>y</var><sub>3</sub>，會根據程式運作的路徑來選擇<var>y</var><sub>1</sub>或<var>y</var><sub>2</sub>：

<center>
[[Image:SSA example1.3.png|完全轉換到SSA的範例]]
</center>

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

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

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

根據Kenny Zadeck<ref>{{Cite web |title=Static Single-Assignment Form Seminar |url=https://compilers.cs.uni-saarland.de/ssasem/ |website=compilers.cs.uni-saarland.de |access-date=2025-01-15}}</ref>表示，當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的定義是不需要Φ函式。


<!-- 未來放置描述尋找定義支配邊界的演算法 -->用來計算支配邊界集合的演算法<ref name="Cooper_2001">{{cite paper |title=A Simple, Fast Dominance Algorithm |last=Cooper |first=Keith D. |coauthors=Harvey, Timothy J.; and Kennedy, Ken |year=2001 |url=http://www.cs.rice.edu/~keith/EMBED/dom.pdf |journal= |access-date=2013-02-08 |archive-date=2021-05-06 |archive-url=https://web.archive.org/web/20210506175117/https://www.cs.rice.edu/~keith/EMBED/dom.pdf }}</ref>為：

 '''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年提出<ref name="Cytron_1991">{{Cite journal |last=Cytron |first=Ron |last2=Ferrante |first2=Jeanne |last3=Rosen |first3=Barry K. |last4=Wegman |first4=Mark N. |last5=Zadeck |first5=F. Kenneth |title=Efficiently computing static single assignment form and the control dependence graph |url=https://dl.acm.org/doi/10.1145/115372.115320 |journal=ACM Transactions on Programming Languages and Systems |language=en |date=1991-10 |volume=13 |issue=4 |page=451-490 |doi=10.1145/115372.115320 |issn=0164-0925}}</ref>。在由Andrew Appel所寫的  "Modern compiler implementation in Java" （2002年由Cambridge University出版）第十九章也是相當有用，詳情請參考此書。

[[萊斯大學]]的Keith D. Cooper、Timothy J. Harvey及 Ken Kennedy在他們的文章''A Simple, Fast Dominance Algorithm''.<ref name="Cooper_2001" />中所描述，這個演算法使用了精心設計的資料結構來改進效能。

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

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

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

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

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

===半精簡的 SSA===
半精簡的SSA（Semi-Pruned SSA form）<ref>{{Cite journal |last=Briggs |first=Preston |last2=Cooper |first2=Keith D. |last3=Harvey |first3=Timothy J. |last4=Simpson |first4=L. Taylor |title=Practical improvements to the construction and destruction of static single assignment form |url=https://onlinelibrary.wiley.com/doi/10.1002/(SICI)1097-024X(19980710)28:83.0.CO;2-8 |journal=Software: Practice and Experience |language=en |date=1998-07-10 |volume=28 |issue=8 |doi=10.1002/(SICI)1097-024X(19980710)28:8<859::AID-SPE188>3.0.CO;2-8 |issn=0038-0644}}</ref>試圖減少Φ函式的數量，而不承擔高成本的運算活躍變數資訊。這是基於以下的觀察：如果一個變數從未活躍於一個基本的區塊，它就不需要一個Φ函式。在SSA的建構，將省略任何''本地區塊''變數使用的Φ函式。

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

==透過SSA轉換出來的程式==
SSA轉換出來的程式，通常不是用來直接執行（雖然透過直譯SSA的方式，這是可能發生<ref>{{Cite journal |last=von Ronne |first=Jeffery |last2=Wang |first2=Ning |last3=Franz |first3=Michael |title=Interpreting programs in static single assignment form |url=https://dl.acm.org/doi/10.1145/1059579.1059585 |journal=Proceedings of the 2004 workshop on Interpreters, virtual machines and emulators |series=IVME '04 |location=New York, NY, USA |publisher=Association for Computing Machinery |date=2004-06-07 |doi=10.1145/1059579.1059585 |isbn=978-1-58113-909-9}}</ref>），它經常被使用在其他保留直接對應的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]]

==參考文獻==
* {{cite book |last=Appel |first=Andrew W. |title=Modern Compiler Implementation in ML |publisher=Cambridge University Press |year=1999 |isbn=0-521-58274-1}} Also available in [[Java]] (ISBN 0-521-82060-X 2002) and [[C语言|C]] (ISBN 0-521-60765-5, 199 8) versions.
* {{cite book |last=Cooper |first=Keith D |last2=Torczon |first2=Linda |title=Engineering a Compiler |publisher=Morgan Kaufmann |year=2003 |isbn=1-55860-698-X}}
* {{cite book |last=Muchnick |first=Steven S. |title=Advanced Compiler Design and Implementation |url=https://archive.org/details/advancedcompiler00much |publisher=Morgan Kaufmann |year=1997 |isbn=1-55860-320-4}}
* {{cite journal |last=Kelsey |first=Richard A. |title=A Correspondence between Continuation Passing Style and Static Single Assignment Form |url=https://dl.acm.org/doi/10.1145/202530.202532 |journal=ACM SIGPLAN Notices |volume=30 |issue=3 |pages=13–22 |doi=10.1145/202530.202532 |date=March 1995}}
* {{cite journal |last=Appel |first=Andrew W. |title=SSA is Functional Programming |url=https://dl.acm.org/doi/10.1145/278283.278285 |journal=ACM SIGPLAN Notices |volume=33 |issue=4 |pages=17–20 |doi=10.1145/278283.278285 |date=April 1998}}
* {{cite journal |last=Pop |first=Sebastian |title=The SSA Representation Framework: Semantics, Analyses and GCC Implementation |year=2006 |url=http://cri.ensmp.fr/people/pop/papers/2006-12-thesis.pdf |journal= |access-date=2010-06-15 |archive-date=2011-04-26 |archive-url=https://web.archive.org/web/20110426142043/http://cri.ensmp.fr/people/pop/papers/2006-12-thesis.pdf |dead-url=no}}
{{Reflist}}

==外部連結==
* Bosscher, Steven; and Novillo, Diego. [http://lwn.net/Articles/84888/ GCC gets a new Optimizer Framework] {{Wayback|url=http://lwn.net/Articles/84888/ |date=20210309133710 }}. 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] {{Wayback|url=http://www.cs.man.ac.uk/~jsinger/ssa.html |date=20120204040115 }}. 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"] {{Wayback|url=http://webcast.rice.edu/webcast.php?action=details&event=1346 |date=20100620040100 }}, December 2007 talk on the origins of SSA.

[[Category:编译原理]]