SSA

• 2021 年 9 月 30 日
• 筆記
• llvm, SSA, 技術, 編譯器

wikipedia上關於SSA的定義如下：

In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR), which requires that each variable be assigned exactly once, and every variable be defined before it is used.
Existing variables in the original IR are split into versions, new variables typically indicated by the original name with a subscript in textbooks, so that every definition gets its own version. In SSA form, use-def chains are explicit and each contains a single element.

翻譯下來就是，編譯器設計中的一種概念，是靜態單賦值範式的簡稱，是中間表達IR的一種屬性，該屬性要求每個變數只能賦值一次，並且必須在使用前進行賦值。「賦值」這個概念在編譯器領域和「定義」是一個概念，所以真實程式語言中的各種變數，如果存在多次賦值並且多次引用不同賦值的情況的話，每次會被引用的賦值會產生一個新的變數（為了方便記憶，新的變數可以是老的變數名加上下標的方式來命名），而那些賦值了卻沒有引用，或者在多次賦值之間沒有引用語句的前一次賦值，會自動被編譯器優化掉。

在計算圖（一般也稱為DAG，Directed Acyclic Graph，有向無環圖）中，每個節點需要先定義，再使用，也就是說，每個節點的生命周期是Def-Use的過程。但節點間的關係就是每個節點先Use其他節點的值，然後生成自己的定義，並把自己的定義提供給下一個節點進行Use的過程，Use-Def-Use的關係。

例如下面從C程式碼：

1 x=1;
2 y=2;
3 x=y+1;
4 z=x*y;
5 a=z+1;

第一輪轉換的過程中變成了下面的程式碼：

1 x1=1;
2 y1=2;
3 x2=y1+1;
4 z1=x2*y1;
5 a1=z1+1;

按照SSA的原則，x1賦值之後沒有使用，所以是無用程式碼，最終按SSA規範優化之後的程式碼是：

1 y1=2;
2 x2=y1+1;
3 z1=x2*y1;
4 a1=z1+1;

而且，很明顯的x2和y1在第三行是最後一次引用，在第三行執行完x2和y1的資源就可以釋放了。