静的単一代入

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

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

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

1. SSA の利点
----------

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

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

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

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

y1 := 1 y2 := 2 x1 := y2

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

定数畳み込み
疎な条件分岐を考慮した定数伝播
デッドコード削除
大域値番号付け
部分冗長性除去
演算子強度低減
レジスタ割り付け

2. SSA への変換
-----------

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

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

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

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

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

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

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

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

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

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

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

支配辺境を求めるアルゴリズムに一つとして、下記のものがある。for each node bif the number of predecessors of b ? 2for each p in predecessors of b runner := pwhile runner ≠ idom add b to runner’s dominance frontier set runner := idom

注意：上記のコードでは、ノード n の前のノードは制御を n に渡す任意のノードであり、idom がノードの 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 1991 pp.451–490. において最初に示された。また "Modern compiler implementation in Java" by Andrew Appel  も有用である。詳細は論文を参照のこと。

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

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

"最小の" SSA はそれぞれの名前に一度だけ変数が割り当てられることを保証し、もともとのプログラムでの名前の参照が 一意の名前を参照できることを保証する。

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

3.1. Pruned SSA
---------------

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

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

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

3.2. Semi-pruned SSA
--------------------

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

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

4. SSA 形式からの変換
--------------

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

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

5. SSA の拡張
----------

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

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

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

5.1. 配列
-------

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

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

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

日本で開発された「COINSコンパイラ・インフラストラクチャ」は、SSAの全面的な導入を図っている。
ETH Oberon-2 コンパイラは SSA の変種である "GSA" を導入した最初期のプロジェクトの一つである。
LLVM Compiler Infrastructure では、コード表現において全てのスカラーレジスタの値にSSA 形式を用いている。SSA 形式は、コンパイル時にレジスタの割り当てが発生するまで破棄されない。
SGI のPro64コンパイラをベースにしたオープンソースのコンパイラ[2](Open Research Compiler）