静的単一割り当てフォーム

コンパイラ設計において、静的単一代入形式( SSA 形式または単にSSAと略されることが多い) は、各変数が正確に 1 回代入される中間表現(IR)の一種です。SSA は、 LLVM、GNU コンパイラ コレクション、および多くの商用コンパイラを含む、命令型言語用のほとんどの高品質最適化コンパイラで使用されています。

プログラムを SSA 形式に変換する効率的なアルゴリズムがあります。SSA に変換するには、元の IR の既存の変数をバージョンに分割します。新しい変数は通常、下付き文字付きの元の名前で示され、すべての定義が独自のバージョンを取得します。変数の新しいバージョンを割り当てる追加のステートメントも、2 つの制御フロー パスの結合ポイントに導入する必要がある可能性があります。SSA 形式からマシン コードへの変換も効率的です。

SSA を使用すると、使用定義チェーンの決定など、最適化に必要なさまざまな分析を簡単に実行できます。これは、変数の使用を調べるときに、その変数が値を受け取った可能性がある場所が 1 つしかないためです。ほとんどの最適化は SSA 形式を維持するように調整できるため、追加の分析なしで 1 つの最適化を次々に実行できます。SSA ベースの最適化は通常、SSA 形式以外の以前の同等のものよりも効率的で強力です。

SchemeやMLなどの関数型言語コンパイラでは、継続渡しスタイル（CPS）が一般的に使用されています。SSAは、非ローカル制御フローを除いたCPSの適切なサブセットと形式的に同等であるため、一方に基づいて定式化された最適化と変換は、通常、他方にも適用されます。CPSを中間表現として使用することは、高階関数と手続き間分析にとってより自然です。CPSはcall/ccを簡単にエンコードできますが、SSAはそうではありません。^[1]

SSA は 1980 年代にIBMの数人の研究者によって開発されました。チームの主要メンバーである Kenneth Zadeck は、開発が続く中ブラウン大学に移りました。^{[2] [3]} 1986 年の論文では、誕生点、恒等代入、および変数名の変更が導入され、変数には単一の静的代入が行われました。^{[4] 1987 年の}Jeanne Ferranteと Ronald Cytronによるその後の論文^[5]では、前の論文で行われた名前の変更によってスカラーの誤った依存関係がすべて削除されることが証明されました。^[3] 1988 年、Barry Rosen、Mark N. Wegman、および Kenneth Zadeck は恒等代入を Φ 関数に置き換え、「静的単一代入形式」という名前を導入し、現在では一般的な SSA 最適化を実証しました。^[6] Φ 関数という名前は、Rosen によって「偽関数」のより出版しやすいバージョンとして選ばれました。^[3]アルパーン、ウェグマン、ザデックは別の最適化を提示したが、ここでは「静的単一代入」という名前を使った。^[7]最終的に、1989年にローゼン、ウェグマン、ザデック、サイトロン、フェランテはプログラムをSSA形式に変換する効率的な手段を発見した。^[8]

SSA の主な有用性は、変数のプロパティを簡素化することで、さまざまなコンパイラ最適化の結果を同時に簡素化および改善する方法にあります。たとえば、次のコードを考えてみましょう。

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

人間は、最初の割り当ては不要であり、y3 行目で使用されている の値は の 2 番目の割り当てから来ていることがわかります。プログラムでは、これを判断するために到達定義分析をy実行する必要があります。ただし、プログラムが SSA 形式の場合、これらは両方とも即時です。

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

SSA の使用によって有効化または大幅に強化されるコンパイラ 最適化アルゴリズムには、次のものがあります。

• 定数伝播– 実行時計算からコンパイル時計算への変換。例えば、命令をa=3*4+5;次のように扱う。a=17;
• 値域伝播^[9] – 計算の可能性のある範囲を事前に計算し、事前に分岐予測を作成できるようにする
• スパース条件付き定数伝播– いくつかの値の範囲チェックにより、最も可能性の高い分岐を予測するテストが可能になります。
• デッドコードの排除– 結果に影響を与えないコードを削除する
• グローバル値の番号付け- 同じ結果を生成する重複した計算を置き換える
• 部分的な冗長性の除去- プログラムのいくつかのブランチで以前に実行された重複計算を削除します
• 強度の削減- 高価な操作をより安価で同等の操作に置き換えます。たとえば、整数の乗算または 2 の累乗による除算を、より安価になる可能性のある左シフト (乗算の場合) または右シフト (除算の場合) に置き換えます。
• レジスタ割り当て- 限られた数のマシンレジスタを計算にどのように使用するか最適化する

通常のコードを SSA 形式に変換することは、主に、各割り当てのターゲットを新しい変数に置き換え、変数の各使用をその時点に到達した変数の「バージョン」に置き換えることです。たとえば、次の制御フロー グラフを考えてみましょう。

「x x - 3」の左側の名前を変更し、その後のxの使用をその新しい名前に変更しても、プログラムは変更されません。これは、SSA でx ₁とx ₂という 2 つの新しい変数を作成し、それぞれに 1 回だけ割り当てることで利用できます。同様に、他のすべての変数に区別する添え字を付けると、次のようになります。 ${\displaystyle \leftarrow}$

1 つの例外を除いて、それぞれの使用がどの定義を参照しているかは明らかです。下のブロックでのyの使用は両方とも、制御フローがたどったパスに応じて、 y ₁またはy _{2 の}いずれかを参照している可能性があります。

これを解決するには、最後のブロックにΦ (ファイ) 関数と呼ばれる特別なステートメントを挿入します。このステートメントは、過去の制御フローに応じて y ₁またはy _{2 の}いずれかを「選択」して、 y ₃と呼ばれるyの新しい定義を生成します。

これで、最後のブロックは単にy ₃を使用でき、どちらの方法でも正しい値が得られます。xの Φ 関数は必要ありません。xの 1 つのバージョン、つまりx ₂だけがこの場所に到達するため、問題はありません (つまり、 Φ( x ₂、x ₂ )= x ₂ )。

任意の制御フロー グラフが与えられた場合、Φ 関数をどこに挿入するか、どの変数に挿入するかを判断することが難しい場合があります。この一般的な問題には、優位性境界と呼ばれる概念を使用して計算できる効率的な解決策があります(以下を参照)。

Φ 関数は、ほとんどのマシンではマシン操作として実装されていません。コンパイラは、すべての先行ブロックの最後に「移動」操作を挿入することで、Φ 関数を実装できます。上記の例では、コンパイラは中央左ブロックの最後にy _1からy ₃への移動を挿入し、中央右ブロックの最後にy _2からy ₃への移動を挿入する可能性があります。これらの移動操作は、コンパイラのレジスタ割り当て手順に基づいて、最終的なコードに含まれない可能性があります。ただし、このアプローチは、ワイド イシューマシンで発生する可能性がある同時操作が Φ 関数への入力を推測的に生成している場合は機能しない可能性があります。通常、ワイド イシュー マシンには、そのような状況でコンパイラが Φ 関数を実装するために使用する選択命令があります。

制御フロー グラフでは、ノード Aを通過せずにノード B に到達できない場合、ノード A は別のノード B を厳密に支配していると言われます。言い換えると、ノード B に到達した場合、A は実行されたと想定できます。A が B を厳密に支配しているか、A = B である場合、A は Bを支配している(または B がAに支配されている) と言われます。

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

ノード A の優位性境界は、 A が厳密には B を優位にしていないが、B の直前のノードを優位にしているノード B のセットです。これらは、複数の制御パスが 1 つのパスに再び結合されるポイントです。

たとえば、次のコードでは:

[1] x = ランダム()
x < 0.5の場合
    [2] 結果 = "表"
それ以外
    [3] 結果 = "表"
終わり
[4] 印刷(結果)

ノード 1 は 2、3、4 を厳密に支配し、ノード 4 の直前のノードはノード 2 と 3 です。

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

各ノードの優位性境界を見つけるための効率的なアルゴリズムがあります。このアルゴリズムは、1991年にロン・サイトロン、ジャンヌ・フェランテらによって「静的単一割り当てフォームと制御グラフの効率的な計算」で最初に説明されました。^[10]

ライス大学のキース・D・クーパー、ティモシー・J・ハーベイ、ケン・ケネディは、「シンプルで高速な優位性アルゴリズム」と題した論文でアルゴリズムを説明しています。^[11]

各ノードbについて
    ドミナンス_フロンティア(b) := {}
各ノードb
    について、bの直前のノードの数≥2
        の場合、 bの直前のノードの各pについて
            ランナー := p
            ランナー≠ idom(b)である間
                支配的フロンティア(ランナー) := 支配的フロンティア(ランナー) ∪ { b }
                ランナー := idom(ランナー)

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

「最小限の」SSA は、各名前に値が 1 回だけ割り当てられ、元のプログラム内の名前の各参照 (使用) が依然として一意の名前を参照できることを保証するために必要な最小限の数の Φ 関数を挿入します。(後者の要件は、コンパイラが各操作の各オペランドの名前を書き留めることができることを保証するために必要です。)

ただし、これらの Φ 関数の一部は不要である可能性があります。このため、最小限の SSA では、特定の手順に必要な最小限の Φ 関数が必ずしも生成されるわけではありません。分析の種類によっては、これらの Φ 関数が不要になり、分析の実行効率が低下する可能性があります。

プルーニングされた SSA 形式は、単純な観察に基づいています。Φ 関数は、Φ 関数の後に「ライブ」である変数にのみ必要です。(ここで、「ライブ」とは、値が問題の Φ 関数から始まるパスに沿って使用されることを意味します。) 変数がライブでない場合、Φ 関数の結果は使用できず、Φ 関数による割り当ては無効になります。

プルーニングされた SSA フォームの構築では、 Φ 関数挿入フェーズでライブ変数情報を使用して、特定の Φ 関数が必要かどうかを決定します。元の変数名が Φ 関数挿入ポイントでライブでない場合、Φ 関数は挿入されません。

もう 1 つの可能性は、プルーニングをデッドコード除去問題として扱うことです。この場合、入力プログラムでの使用が Φ 関数に書き換えられるか、別の Φ 関数の引数として使用される場合にのみ、Φ 関数はライブになります。SSA 形式を入力すると、各使用はそれを支配する最も近い定義に書き換えられます。Φ 関数は、ライブ Φ の少なくとも 1 つの使用または少なくとも 1 つの引数を支配する最も近い定義である限り、ライブであると見なされます。

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

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

ブロック引数はΦ関数の代替手段であり、表現上は同一ですが、実際には最適化の際により便利です。ブロックには名前が付けられ、関数パラメータとして表記されるブロック引数のリストを取ります。ブロックを呼び出すと、ブロック引数は指定された値にバインドされます。MLton 、 Swift SIL、およびLLVM MLIRはブロック引数を使用します。^[13]

SSA形式は通常、直接実行には使用されません（ただし、SSA ^[14]を解釈することは可能です）。また、SSAは直接対応する別のIRの「上」で使用されることがよくあります。これは、SSAを、既存のIR（基本ブロック、命令、オペランドなど）の部分とそのSSA対応部分とをマッピングする一連の関数として「構築」することで実現できます。SSA形式が不要になった場合は、これらのマッピング関数を破棄して、最適化されたIRのみを残すことができます。

SSA 形式で最適化を実行すると、通常、絡み合った SSA-Web が発生します。つまり、オペランドがすべて同じルートオペランドを持たない Φ 命令が存在することになります。このような場合、カラーアウトアルゴリズムを使用して SSA から抜け出します。ナイーブなアルゴリズムでは、各先行パスに沿ってコピーが導入され、異なるルート シンボルのソースが Φ の宛先とは異なる Φ に配置されます。コピー数を減らして SSA から抜け出すためのアルゴリズムは複数ありますが、そのほとんどは干渉グラフまたはその近似値を使用してコピーの結合を行います。^[15]

SSA フォームの拡張は 2 つのカテゴリに分けられます。

名前変更スキームの拡張により、名前変更の基準が変更されます。SSA 形式では、各変数に値が割り当てられると名前が変更されることを思い出してください。代替スキームには、静的単一使用形式 (各ステートメントが使用されるたびに各変数の名前が変更されます) と静的単一情報形式 (各変数に値が割り当てられると、およびポスト優位フロンティアで各変数の名前が変更されます) があります。

機能固有の拡張機能は、変数の単一割り当てプロパティを保持しますが、追加の機能をモデル化するための新しいセマンティクスを組み込んでいます。一部の機能固有の拡張機能は、配列、オブジェクト、エイリアス ポインターなどの高レベルのプログラミング言語機能をモデル化します。その他の機能固有の拡張機能は、推測や予測などの低レベルのアーキテクチャ機能をモデル化します。

• MonoはMiniと呼ばれるJITコンパイラでSSAを使用しています。
• WebKitはJITコンパイラでSSAを使用しています。^{[16] [17]}
• SwiftはLLVM IRの上にSIL（Swift Intermediate Language）と呼ばれる独自のSSA形式を定義しています。^{[18] [19]}
• ErlangはOTP 22.0でコンパイラを書き直し、「静的単一代入（SSA）に基づく中間表現を内部的に使用する」ようにし、将来のリリースではSSA上にさらなる最適化を構築する計画がある。^[20]
• LLVMコンパイラ インフラストラクチャは、主要なコード表現ですべてのスカラー レジスタ値 (メモリを除くすべて) に SSA 形式を使用します。SSA 形式は、コンパイル プロセスの後半 (多くの場合、リンク時) でレジスタ割り当てが発生した場合にのみ削除されます。
• GNUコンパイラ コレクション(GCC) は、バージョン 4 (2005 年 4 月リリース) 以降、SSA を広範に使用しています。フロントエンドは「GENERIC」コードを生成し、その後「 gimplifier 」によって「GIMPLE」コードに変換されます。次に、SSA 形式の「 GIMPLE 」に高レベルの最適化が適用されます。結果として得られる最適化された中間コードは、低レベルの最適化が適用された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のDalvik仮想マシンは、JIT コンパイラで SSA を使用します。
• Androidランタイム用のAndroidの新しい最適化コンパイラは、IRにSSAを使用します。^[24]
• 標準 ML コンパイラMLton は、中間言語の 1 つで SSA を使用します。
• LuaJITはSSAベースの最適化を多用します。^[25]
• PHPとHackコンパイラHHVMはIRでSSAを使用しています。[ ^26]
• コンパイラのミドルエンドおよびバックエンドとして使用されるライブラリであるlibFirmは、SSA対応レジスタアロケータを使用してコードが生成されるまで、すべてのスカラーレジスタ値にSSA形式を使用します。^[27]
• シェーディング言語のSSA表現であるNIRを介したさまざまなMesaドライバ。 ^[28]

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

• ETH Oberon-2コンパイラは、SSA の派生形である「GSA」を組み込んだ最初のパブリック プロジェクトの 1 つでした。
• Open64コンパイラは、グローバル スカラー オプティマイザーで SSA 形式を使用しましたが、コードは事前に SSA 形式に変換され、後で SSA 形式から取り出されます。Open64 は、SSA 形式の拡張を使用して、メモリを SSA 形式とスカラー値で表現します。
• 2002 年、研究者らは IBM の JikesRVM (当時の名称は Jalapeño) を変更して、標準 Javaバイトコードとタイプセーフ SSA ( SafeTSA ) バイトコード クラス ファイルの両方を実行できるようにし、SSA バイトコードの使用によるパフォーマンス上の大きな利点を実証しました。
• jackcc は、学術命令セット Jackal 3.0 用のオープンソース コンパイラです。中間表現には、SSA を使用したシンプルな 3 オペランド コードを使用します。興味深いバリエーションとして、Φ 関数を、レジスタ アロケータに 2 つの有効範囲を同じ物理レジスタに配置するように指示する、いわゆる SAME 命令に置き換えます。
• 1994年頃のイリノイコンサートコンパイラ^[34]は、SSAの変種であるSSU（Static Single Use）を使用していました。これは、各変数に値が割り当てられたとき、およびその変数が使用される各条件付きコンテキストで名前を変更します。基本的には、上記の静的単一情報形式です。SSU形式は、ジョン・プレヴィアックの博士論文に記載されています。
• COINS コンパイラは、ここで説明されているように、SSA フォームの最適化を使用します。
• Reservoir LabsのR-Streamコンパイラは、非SSA（クワッドリスト）、SSA、SSI（静的単一情報^[35]）形式をサポートしています。^[36]
• 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における最新のコンパイラ実装。ケンブリッジ大学出版局。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。
• Muchnick, Steven S. (1997)。高度なコンパイラの設計と実装。Morgan Kaufmann。ISBN 978-1-55860-320-2。
• Kelsey, Richard A. (1995 年 3 月)。 「継続渡しスタイルと静的単一代入形式との対応」。ACM SIGPLAN 通知。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 実装」(PDF)。 {{cite journal}}:ジャーナルを引用するには|journal=(ヘルプ)が必要です
• 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-2、 2013年3月24日閲覧

• Bosscher, Steven、Novillo, Diego。GCC に新しいオプティマイザー フレームワークが導入されました。GCC の SSA の使用と、それが古い IR と比べてどのように改善されているかについての記事。
• SSA 書誌。SSA 研究論文の広範なカタログ。
• Zadeck、F. Kenneth。「静的単一割り当てフォームの開発」、2007 年 12 月の SSA の起源に関する講演。