静的単一代入

静的単一代入（せいてきたんいつだいにゅう、英: Static Single Assignment form, SSA）形式は、コンパイラ設計における中間表現 (IR) のひとつで、各変数が一度のみ代入されるよう定義されたものである。もともとの中間表現における変数は「バージョン」に分割され、全ての変数の定義がバージョンを表現できるよう、通例新たな変数は元の名前に添え字を付けて表現される。SSA ではuse-def 連鎖が明示的であり、連鎖は要素を一つだけ持つ。

SSA はRon Cytron、Jeanne Ferrante、Barry Rosen、Mark Wegman、Ken Zadeck および IBM の研究者たちにより1980年代に開発された。

Scheme、ML、Haskell などの関数型言語のコンパイラでは、Fortran や C などのコンパイラで SSA の利用が期待される箇所で継続渡しスタイル (CPS) を用いるのが一般的である。SSA と CPS は形式的に等価であり、最適化やコードの変換などがいずれかに施された場合、もう片方にも同様に適用することができる。

SSA の利点

変数の性質を簡単なものにすることにより様々なコンパイラ最適化を簡略化すると同時にその結果を改善することが SSA の第一の利点である。

例として、下記のようなコードを考える。

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

人間であれば、最初の代入が不要であり、3行目で使用されている y の値が2行目の代入の結果であることが分かる。これをプログラムで行う場合には、reaching definition analysisにより求める必要がある。しかし、プログラムが静的単一代入形式であれば、いずれも即座に判定可能である。

 y₁ := 1
 y₂ := 2
 x₁ := y₂

SSA を利用することにより、下記のコンパイラ最適化アルゴリズムを実現したり、あるいは改善することができる。

SSA への変換

ツリー上のコードの SSA 形式への変換は、代入の対象を新たな変数に置き換え、変数の使用箇所をその定義箇所に到達する「バージョン付き」のものに置き換えるだけの基本的に簡潔な問題である。例として、下記のような制御フローグラフを考える。

"x $\leftarrow$ x - 3" の左辺の名前を変え、それ以降 x を新たな名前に変えることができ、それでもプログラムは全く同じ動作をする。このことを利用して、SSA ではそれぞれに対して一度しか代入が行われない新たな二つの変数x₁ と x₂ を作成する。同様に、全ての変数に対してバージョンを区別するための添え字を与える。

ここで、各々の変数を使用している箇所がどの定義を参照しているかをただ一点を除いて把握している。最後のブロックの y は制御フローのどちらを通るかによって y₁ と y₂のどちらを参照するかが異なる。ではこれをどのようにして知るのか？

その答えは、Φ (ファイ) 関数と呼ばれる特別な命令を最後のブロックの始めに追加することである。この命令は、どちらの制御フローから到達したのかによって y₁ あるいは y₂ を選択し y の新たな定義 y₃ を生成する。

これにより、最後のブロックの y は y₃ を用いることができ、いずれの場合でも正し値を得ることができる。 x についても Φ 関数を追加する必要があるか？という質問があるかもしれないが、答えは「不要」である。x のバージョンは x₂ のみがこの箇所に到達しており、問題にはならない。

より一般的な質問として、任意の制御フローが与えられたとき、どこに、またどの変数に対して Φ 関数を挿入するべきか、という問題がある。これは難しい質問であるが、支配辺境(dominance frontier) と呼ばれる概念を用いて求める優れた方法がある。

ここで、Φ 関数は実際に実装されるものではなく、コンパイラに対して Φ 関数でグループとされる全ての変数の値をメモリやレジスタの同じ場所に配置するよう指示するマーカーである。

支配辺境を用いた最小 SSA の計算

まず、dominator の概念が必要である。制御フローのノード A が別のノード B を 厳密に支配する とき、A に到達しなければ B に到達することがないことを意味する。これは、B に到達していれば A のコードが動作していることが分かるため有用である。また A が B を 支配するとき、A が B を厳密に支配するか、A = B であることを意味する。

ここで、支配辺境(dominance frontier)を次のように定義することができる。A は B を厳密に支配していないが、B の直前にあるノードのいくつかを支配しているとき( A が B の直前にあれば、A 自身)、ノード B は A の支配辺境内にあるものとする。A から見ると、これらは A を介さず、最初に登場する制御パス上のノードである。

支配辺境は Φ 関数を必要とする場所を正確に捉えることができ、その定義のみ（あるいは再定義）が A の支配するノードに到達する。これらのノードを去り支配辺境に入る場合のみ、同じ変数を定義している箇所にそれ以外のフローを考慮すればよい。また、制御フローグラフ中に A の定義を扱う Φ 関数はそれ以上必要ない。

支配辺境を求めるアルゴリズムに一つとして、下記のものがある。

for each node b
    if the number of predecessors of b ? 2
        for each p in predecessors of b
            runner := p
            while runner ≠ idom(b)
                add b to runner’s dominance frontier set
                runner := idom(runner)

注意：上記のコードでは、ノード n の前のノードは制御を n に渡す任意のノードであり、idom(n) がノードの n を直接支配する。

支配辺境を見つけるための効率的なアルゴリズムが存在し、論文 "Efficiently computing static single assignment form and the control dependence graph", by R. Cytron, J. Ferrante, B. Rosen, M. Wegman and F. Zadeck, ACM Trans. on Programming Languages and Systems 13(4) 1991 pp.451–490. において最初に示された。また "Modern compiler implementation in Java" by Andrew Appel (Cambridge University Press, 2002) も有用である。詳細は論文を参照のこと。

ライス大学の Keith D. Cooper, Timothy J. Harvey, Ken Kennedy は、論文 A Simple, Fast Dominance Algorithmにおいて、アルゴリズムを提唱した。このアルゴリズムはよく設計されたデータ構造を用いてパフォーマンスを改善させている。

Φ 関数の数を減らすための方法

"最小の" SSA はそれぞれの名前に一度だけ変数が割り当てられることを保証し、もともとのプログラムでの名前の参照（変数の使用箇所）が一意の名前を参照できることを保証する。（後者はコンパイラが各操作の対象となる変数の名前を特定できるようにするために必要である）

しかし、Φ 関数の一部はデッドコードである可能性がある。このため、最小の SSA は必ずしも特定の手続きに必要な最小の Φ 関数を生成する必要はない。方法によっては、このような Φ 関数は無用であり、解析の効率を落としてしまう。

Pruned SSA

Pruned SSA 形式は非常に簡単な観察：すなわち「 Φ 関数は、それ以降に『生存している』変数にのみ必要であるに基づいており（ここでの「生存」とは変数の値が問題の Φ 関数から始まるパス上で使用されることを意味する）、変数が「生存」していなければ、Φ 関数の結果が使用されることはなく、Φ 関数による割り当ては無効である。

Pruned SSA を構築する場合には、Φ 関数を挿入する際に、生存変数情報(live variable information)を用いて与えられた Φ 関数が必要なのかどうかを判断する。もともとの変数が Φ 関数を挿入する場所ですでに「生存」していなければ、Φ 関数は挿入されない。

刈り込み(pruning)を扱うもう一つの方法としてデッドコード削除の問題がある。Φ 関数は、入力プログラム内の変数の使用箇所のいずれかが Φ 関数に置き換えられる場合のみ SSA 形式に Φ 関数が各変数の参照箇所は、その変数を支配する最も近い定義に置き換えられる。最低でも一箇所の参照箇所ないし生きた Φ 関数の引数を支配する最も近い定義であれば、生きているとみなすことができる。

Semi-pruned SSA

Semi-pruned SSA 形式 ^[1] は、生存変数の情報を求める比較的高い計算コストを要せず、Φ 関数の数を減らすための試みである。 Semi-pruned SSA は次の観察に基づいている：「変数が基本的なブロックに入る際に生存していなければ、 Φ 関数は必要ない」。従って、SSA の構築の際、ブロックの局所変数に対する Φ 関数は省略可能である。

ブロックの局所変数のセットを求めるのは完全な生存変数解析を行うより簡単で高速に実行でき、pruned な SSA 形式を求めるより高速である。一方、pruned な SSA 形式のほうが不要な Φ 関数は少ない。

SSA 形式からの変換

SSA 形式は直接実行するために有用な形式ではないため、元のコードとの直接の対応関係を保持した中間コード上で用いられることが多い。これは、SSA を既存の中間コードの要素（基本ブロック、命令、オペランドなど）と SSA での対応する要素をマップした関数として構築することで実現できる。SSA が必要なくなればこれらのマップ関数は廃棄してよく、最適化された新しい IR が残る。

SSA 形式で最適化を行うと、非常に複雑な SSA の網目構造が作成される。すなわちオペランドが必ずしも同じ起点を持たない Φ 命令が存在することになる。このような場合色分け(color-out)アルゴリズムが用いられる。単純なアルゴリズムではそれぞれの以前のパスに従ってコピーを作成するが、 Φ 関数の出力ではなく入力となる起点のシンボルが多数できてしまう。SSA からコピーの回数を少なくするためのアルゴリズムが複数あり、大半のものは干渉グラフやコピーの融合を行うための近似を行う。

SSA の拡張

SSA 形式の拡張は二種類に分類される。

改名戦略型の拡張は、異なった変数の改名基準を用いる。SSA 形式では値を代入する際に変数の名前を変えるが、これ以外の方法として各変数の参照時に名前を変える静的単一参照形式(static single use form)と、各変数の名前を代入されたときに変え、さらに変数が使用される条件節ごとに変える静的単一情報形式(static single information form)がある。

機能固有型拡張は、変数へ一度だけ代入を行うという性質を保ちつつ、新たな機能をモデル化できるよう新たな意味論を導入する。機能固有型の拡張は、配列、オブジェクトやポインタなどの高レベルプログラミング言語の機能をモデル化する。また投機実行や分岐予測などの低レベルのアーキテクチャ上の機能をモデル化する機能固有型の拡張も存在する。

配列

配列の要素レベルに対する SSA としては、1998年に Kathleen Knobe と Vivek Sarkar による Array SSA^[2]や2006年に Silvius Rus, Guobin He, Lawrence Rauchwerger による Region Array SSA^[3] などが提案されている。

SSA形式を用いたコンパイラ

前述のように理論的には1980年代にはその基本は確立されている。しかし、実際のコンパイラ（特に、プロプライエタリでないもの）への導入は比較的近年であり、従って、古いコンパイラは SSA 形式をコンパイルや最適化の一部でのみ使用し、ほとんどのものは全面的に SSA に依存することはない。SSA に大きく依存するコンパイラの例として、下記のものがある。

日本で開発された「COINSコンパイラ・インフラストラクチャ」は、SSAの全面的な導入を図っている。
ETH Oberon-2 コンパイラは SSA の変種である "GSA" を導入した最初期のプロジェクトの一つである。
LLVM Compiler Infrastructure では、コード表現において全てのスカラーレジスタの値にSSA 形式を用いている。SSA 形式は、コンパイル時（通例リンク時）にレジスタの割り当てが発生するまで破棄されない。
SGI のPro64コンパイラをベースにしたオープンソースのコンパイラORC(Open Research Compiler）は SSA 形式を大域的なスカラー最適処理に用いているが、コードは SSA 形式に変換され、後で SSA 形式から変換される。ORC はスカラーの値に加えてメモリを表現するよう SSA 形式を拡張している。
GCC、GNUコンパイラコレクションのバージョン 4 (2005年4月リリース) では　SSA が多用されている。フロントエンドがGENERICコードを生成し、次に "gimplifier" が SSA に変換し、"ミドルエンド"が最適化を行う。バックエンドが最適化された中間コードを RTL に変換して低レベルな最適化を行い、最終的に RTL がassembly languageに変換される。
IBM のオープンソース適合の Java仮想マシン "Jikes RVM" は、Extended Array SSA という SSA の拡張を用いている。これはスカラー、配列、オブジェクトのフィールドを統一されたフレームワークで解析することが可能である。Extended Array SSA の解析は、コードの最も頻繁に実行される部分に対して適用される最適化レベル最大時のみ有効になる。
2002年に、研究者が IBM の JikesRVM を標準の Javaバイトコードと型安全の SSA (SafeTSA) バイトコードのJavaクラスファイルを動作できるよう改変し(当時 Jalapeno と命名された) 、SSA バイトコードを用いて大幅なパフォーマンス向上が得られることを示した。
サン・マイクロシステムズの Java HotSpot Virtual Machine は、JIT コンパイラで SSA ベースの中間言語を用いている。
Mono は Mini と呼ばれる JIT コンパイラで SSA を用いている。
jackcc は学術用の命令セット Jackal 3.0 のためのオープンソースコンパイラである。jackcc は中間表現で、SSA の単純な 3 オペランドコードを用いている。興味深い派生物として、 Φ 関数をいわゆる SAME 命令、すなわちレジスタ割り当ての際、同じ物理レジスタに二つの値を配するよう指示する。
コンパイラではないが、 Boomerang 逆コンパイラは、内部表現に SSA 形式を用いている。SSA は式の伝播や、パラメータや戻り値の特定、保存の解析(preservation analysis) などを簡略化するために用いられている。
Portable.NET は JIT コンパイラで SSA を用いている。
libFirm は、コンパイラのための完全なグラフベースの SSA 中間表現である。

参考文献

^ Practical Improvements to the Construction and Destruction of Static Single Assignment Form (1998), Preston Briggs, Keith D. Cooper, Timothy J. Harvey, L. Taylor Simpson.
^ Array SSA form and its use in Parallelization
^ Region Array SSA

Appel, Andrew W. (1999). Modern Compiler Implementation in ML. Cambridge University Press. 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.; & Torczon, Linda. (2003). Engineering a Compiler. Morgan Kaufmann. ISBN 1-55860-698-X
Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 1-55860-320-4
Richard A. Kelsey (March 1995). “A Correspondence between Continuation Passing Style and Static Single Assignment Form”. ACM SIGPLAN Notices 30 (3): 13-22.
Andrew W. Appel (April 1998). “SSA is Functional Programming”. ACM SIGPLAN Notices 33 (4): 17-20.

外部リンク

Steven Bosscher and Diego Novillo. 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.

[1] Practical Improvements to the Construction and Destruction of Static Single Assignment Form (1998), Preston Briggs, Keith D. Cooper, Timothy J. Harvey, L. Taylor Simpson.

[2] Array SSA form and its use in Parallelization

[3] Region Array SSA

[1]

[2]

[3]