静的な単一課題フォーム

制御フローグラフにおいて、ノードAが別のノードBを厳密に支配するとは、Aを経由せずにBに到達することが不可能な場合をいう。言い換えれば、ノードBに到達した場合、Aは実行されたとみなせる。AがBを厳密に支配する場合、またはA = Bである場合、 AはBを支配している（またはBはAに支配されている）とされる。

ノードAに制御を移譲するノードは、Aの直前のノードと呼ばれる。

ノードAの支配境界とは、AがBを厳密には支配しないものの、Bの直前のノードを支配しているノードBの集合である。これらは、複数の制御パスが再び合流して単一のパスになる地点である。

例えば、以下のコードでは：

[1] x = random() x < 0.5 の場合 [2] 結果 = "表" それ以外 [3] 結果 = "tails" 終わり [4] print(結果) 

ノード1はノード2、3、4を厳密に支配しており、ノード4の直前のノードはノード2と3である。

支配境界は、Φ 関数が必要となるポイントを定義します。上記の例では、制御がノード 4 に渡される場合、result使用される定義は、制御がノード 2 から渡されたか、ノード 3 から渡されたかによって異なります。支配子で定義された変数には、適用可能な定義が 1 つしかないため、Φ 関数は必要ありません。

各ノードの支配境界を見つけるための効率的なアルゴリズムが存在する。このアルゴリズムは、1991年にRon Cytron、Jeanne Ferranteらが発表した「Efficiently Computing Static Single Assignment Form and the Control Graph」で初めて説明された。^{[ 10 ]}

ライス大学のキース・D・クーパー、ティモシー・J・ハーベイ、ケン・ケネディは、「シンプルで高速な支配アルゴリズム」というタイトルの論文でアルゴリズムについて説明しています。^{[ 11 ]}

各ノードbについて 支配領域(b) := {} 各ノード b について、 b の直前のノードの数が 2 以上 の場合、 b の直前のノードの各pについて ランナー := p while runner ≠ idom(b) dominance_frontier(runner) := dominance_frontier(runner) ∪ { b } runner := idom(runner)

上記のコードでは、idom(b)はb の直接の支配ノードであり、b を厳密に支配する唯一のノードですが、b を厳密に支配する他のどのノードも厳密に支配しません。

剪定されたSSA形式は、単純な観察に基づいています。Φ関数は、Φ関数の後で「有効」な変数にのみ必要です。（ここで「有効」とは、その値が問題のΦ関数から始まる何らかのパスに沿って使用されることを意味します。）変数が有効でない場合、Φ関数の結果は使用できず、Φ関数による代入は無効になります。

剪定されたSSA形式の構築では、 Φ関数挿入フェーズで有効変数情報を使用して、特定のΦ関数が必要かどうかを判断します。元の変数名がΦ関数挿入時点で有効でない場合、Φ関数は挿入されません。

別の方法として、枝刈りをデッドコード除去問題として扱う方法があります。この場合、Φ関数は、入力プログラム内のいずれかの用例がその関数に書き換えられる場合、または別のΦ関数の引数として使用される場合にのみ有効となります。SSA形式に入力する際、各用例は、その用例を支配する最も近い定義に書き換えられます。したがって、Φ関数は、少なくとも1つの用例を支配する最も近い定義であるか、有効なΦ関数の少なくとも1つの引数を支配する定義である限り、有効とみなされます。

半剪定SSA形式^{[ 12 ]}は、生存変数情報を計算する比較的高いコストをかけずにΦ関数の数を減らす試みです。これは、変数が基本ブロックに入るときに生存しない場合、Φ関数は必要ないという観察に基づいています。SSA構築中は、「ブロックローカル」変数のΦ関数は省略されます。

ブロックローカル変数のセットを計算する手順は、完全なライブ変数解析よりも簡単で高速であるため、半剪定SSA形式は剪定SSA形式よりも計算効率が高くなります。一方、半剪定SSA形式にはより多くのΦ関数が含まれます。

ブロック引数は、表現上は同じですが、最適化の際に実際にはより便利な Φ 関数の代替手段です。ブロックには名前が付けられ、関数パラメータとして表記されるブロック引数のリストを受け取ります。ブロックを呼び出すと、ブロック引数は指定された値にバインドされます。MLton 、Swift SIL、およびMLIR はブロック引数を使用します。^{[ 13 ]}ブロック引数により、継続渡しスタイル(CPS) との関連性がより明確になります。基本ブロックは関数であり、関数変数はブロック引数 (Φ 関数) です。

• MonoはMiniと呼ばれるJITコンパイラでSSAを使用しています。
• WebKit はJIT コンパイラで SSA を使用しています。^{[ 16 ] [ 17 ]}
• SwiftはLLVM IRの上に独自のSSA形式を定義しており、SIL（Swift Intermediate Language）と呼ばれています。^{[ 18 ] [ 19 ]}
• ErlangコンパイラはOTP 22.0で書き直され、「内部的に静的単一代入（SSA）に基づく中間表現を使用する」ようになり、将来のリリースではSSAの上に構築されたさらなる最適化が計画されている。^{[ 20 ]}
• LLVMコンパイラインフラストラクチャは、主要なコード表現において、すべてのスカラーレジスタ値（メモリを除くすべて）にSSA形式を使用します。SSA形式は、コンパイルプロセスの後半（多くの場合、リンク時）にレジスタ割り当てが行われるまで削除されません。
• GNUコンパイラコレクション（GCC）は、バージョン4（2005年4月リリース）以降、SSAを幅広く利用しています。フロントエンドは「GENERIC」コードを生成し、それが「gimplifier」によって「GIMPLE」コードに変換されます。次に、「GIMPLE」のSSA形式に対して高レベルの最適化が適用されます。最適化された中間コードはRTLに変換され、低レベルの最適化が適用されます。最後に、アーキテクチャ固有のバックエンドがRTLをアセンブリ言語に変換します。
• Go (1.7: x86-64アーキテクチャのみ、1.8: サポートされているすべてのアーキテクチャ)。^{[ 21 ] [ 22 ]}
• IBMのオープンソース適応型Java仮想マシンであるJikes RVMは、拡張配列SSAを使用しています。これは、スカラー、配列、およびオブジェクトフィールドを統一されたフレームワークで分析できるSSAの拡張機能です。拡張配列SSA分析は、最も頻繁に実行されるコード部分に適用される最大最適化レベルでのみ有効になります。
• Mozilla Firefox SpiderMonkey JavaScript エンジンは SSA ベースの IR を使用しています。^{[ 23 ]}
• Chromium V8 JavaScriptエンジンは、2010年12月に発表されたとおり、CrankshaftコンパイラインフラストラクチャにSSAを実装しています。
• PyPyは、JITコンパイラにおけるトレースに線形SSA表現を使用します。
• Android Runtime ^{[ 24 ]}とDalvik 仮想マシンはSSA を使用しています。^{[ 25 ]}
• 標準MLコンパイラであるMLtonは、中間言語の一つでSSAを使用している。
• LuaJITはSSAベースの最適化を多用している。^{[ 26 ]}
• PHPおよびHackコンパイラHHVMは、 IRにSSAを使用しています。^{[ 27 ]}
• OCamlコンパイラはCMM IR（C--の略）でSSAを使用します。^{[ 28 ]}
• コンパイラの中間およびバックエンドとして使用されるライブラリであるlibFirmは、SSA対応レジスタアロケータを使用してコードを生成するまで、すべてのスカラーレジスタ値にSSA形式を使用します。^{[ 29 ]}
• シェーディング言語のSSA表現であるNIRを介した様々なMesaドライバ。 ^{[ 30 ]}

• OracleのHotSpot Java仮想マシンは、 JITコンパイラでSSAベースの中間言語を使用しています。^{[ 31 ]}
• Microsoft Visual C++コンパイラ バックエンドは、Microsoft Visual Studio 2015 Update 3 で SSA を使用しています^{[ 32 ]}
• SPIR-Vは、 VulkanグラフィックスAPIのシェーディング言語標準であり、OpenCLコンピューティングAPIのカーネル言語であり、SSA表現である。^{[ 33 ]}
• Microsoft DirectX Shader Compilerのシェーディング言語であるDXIL は、 LLVM のフォークであるため、SSA 表現を使用します。^{[ 34 ]}
• IBMのXLコンパイラファミリーには、C、C++、Fortranが含まれる。^{[ 35 ]}
• NVIDIA CUDA ^{[ 36 ]}

• ETH Oberon-2コンパイラは、SSAの派生版である「GSA」を組み込んだ最初の公開プロジェクトの一つだった。
• Open64コンパイラは、グローバルスカラー最適化においてSSA形式を使用していますが、コードは最適化前にSSA形式に変換され、最適化後にSSA形式から元の形式に戻されます。Open64は、 SSA形式の拡張機能を使用して、メモリだけでなくスカラー値もSSA形式で表現します。
• 2002年、研究者たちはIBMのJikesRVM（当時はJalapeñoという名称だった）を改良し、標準Javaバイトコードと型安全なSSA（SafeTSA）バイトコードクラスファイルの両方を実行できるようにした。そして、SSAバイトコードを使用することでパフォーマンスが大幅に向上することを実証した。
• jackccは、学術用命令セットJackal 3.0用のオープンソースコンパイラです。中間表現には、SSAを用いたシンプルな3オペランドコードを使用します。興味深いバリエーションとして、Φ関数をSAME命令と呼ばれる命令に置き換えています。この命令は、レジスタ割り当て器に対し、2つの有効範囲を同じ物理レジスタに配置するよう指示します。
• 1994 年頃のイリノイコンサートコンパイラ^{[ 37 ]}は、SSA のバリアントである SSU (Static Single Use) を使用していました。これは、各変数に値が割り当てられるとき、およびその変数が使用される各条件コンテキストで、各変数の名前を変更します。これは基本的に、前述の静的単一情報形式です。SSU 形式は、ジョン・プレヴィアクの博士論文に記載されています。
• COINSコンパイラは、ここで説明されているようにSSA形式最適化を使用します。
• Reservoir LabsのR-Streamコンパイラは、非SSA（クワッドリスト）、SSA、およびSSI（Static Single Information ^{[ 38 ]}）形式をサポートしています。^{[ 39 ]}
• Boomerangの逆コンパイラはコンパイラではありませんが、内部表現にSSA形式を使用しています。SSAは、式の伝播の簡素化、パラメータと戻り値の識別、保存性分析などに利用されます。
• DotGNU Portable.NETは、JITコンパイラにSSAを使用していた。

• ラステッロ、ファブリス。ティシャドゥ、フローラン・ブーシェズ編。 （2022年）。SSA ベースのコンパイラ設計(PDF)。チャム。土井: 10.1007/978-3-030-80515-9。ISBN 978-3-030-80515-9. S2CID 63274602 . {{cite book}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)
• Appel, Andrew W. (1999). MLにおける最新のコンパイラ実装. Cambridge University Press. ISBN 978-0-521-58274-2。Java版もございます（ISBN 0-521-82060-X（2002年）およびC（ISBN 0-521-60765-5（1998年版）。
• クーパー、キース・D. & トルツォン、リンダ (2003).コンパイラのエンジニアリング. モーガン・カウフマン. ISBN 978-1-55860-698-2。
• ムチニック、スティーブン・S. (1997).高度なコンパイラ設計と実装. モーガン・カウフマン. ISBN 978-1-55860-320-2。
• Kelsey, Richard A. (1995 年 3 月). 「継続パス方式と静的単一代入方式の対応関係」 . ACM SIGPLAN Notices . 30 (3): 13–22 . doi : 10.1145/202530.202532 .
• Appel, Andrew W. (1998年4月). "SSAは関数型プログラミングである" . ACM SIGPLAN Notices . 33 (4): 17– 20. doi : 10.1145/278283.278285 . S2CID 207227209 . 
• Pop, Sebastian (2006). SSA表現フレームワーク：意味論、分析、およびGCC実装（博士論文）。パリ鉱業学校。
• Matthias Braun、Sebastian Buchwald、Sebastian Hack、Roland Leißa、Christoph Mallon、Andreas Zwinkau (2013)、「静的単一代入形式のシンプルかつ効率的な構築」、Compiler Construction、Lecture Notes in Computer Science、vol.  7791、Springer Berlin Heidelberg、pp. 102–122、doi : 10.1007/978-3-642-37051-9_6、ISBN  978-3-642-37050-22013年3月24日取得