SSA 形式

SSA の核心は、各値の名前に静的な定義が1つだけ存在し、明確にその定義に関連付けられていることです。「静的」が重要です：ループ内の同じ命令は動的に何度も実行され、毎回異なる結果を生成しても、SSA の要件を満たします。

SSA はデータ依存関係の表現を改善しますが、すべてのループ分析を自動的には行いませんし、物理レジスタが無限であることや、メモリへの書き込みが1回だけである必要もありません。

ブランチでの再代入、合流点での表現

通常のプログラムではまず x=1 を実行し、条件に応じて x=2 となる可能性があり、最後に x を使用します。SSA に変換すると、2つの代入は異なる名前を使用し、合流点には φ 定義が追加され、進入した前駆エッジに応じて入力が選択されます。

define i32 @choose(i1 %cond) {
entry:
  br i1 %cond, label %left, label %right
left:
  br label %merge
right:
  br label %merge
merge:
  %x = phi i32 [ 2, %left ], [ 1, %right ]
  %y = add i32 %x, 1
  ret i32 %y
}

φ は2つの入力を同時に評価して条件をチェックするのではなく、実際の制御フローエッジに関連付けられた値の選択です。この例では 3 または 2 を返します。これは IR 命令として存在できますが、ターゲット ISA に同名の機械語命令が存在する必要はありません。

支配：定義が使用に対して必ず可視か

ブロック A が B を支配するとは、エントリから B へのすべてのパスが A を通ることを意味します。通常の SSA では、定義は使用を支配すべきです。同じブロック内では、定義が使用よりも前に現れる必要があります。φ の入力は、対応する前駆エッジ上の使用に基づいてチェックされます。

即座支配関係はエントリから到達可能なブロック上で木を形成し、エントリ以外の各ノードには即座支配者が1つだけ存在します。CFG 内の合流ノードは複数の前駆を持つことができますが、支配木では2つの親を持つことはありません。菱形の CFG をそのまま支配木としてラベル付けすると、これら2つの構造が混同されます。

ループ内の φ：初期値とバックエッジの値を接続する

define i32 @count_to(i32 %n) {
entry:
  br label %header
header:
  %i = phi i32 [ 0, %entry ], [ %next, %body ]
  %more = icmp slt i32 %i, %n
  br i1 %more, label %body, label %exit
body:
  %next = add i32 %i, 1
  br label %header
exit:
  ret i32 %i
}

header に初めて進入する際は 0 を選択し、その後 body から戻ってくる際は前回の next を選択します。定義と使用がテキストや依存関係グラフ内で循環を形成することがありますが、これは SSA を違反するものではありません。したがって、不動点への収束を必要とする解析は、SSA に変更しただけですべて単一パスにはなりません。

n=2 の場合、同じ静的名前でどのように複数の動的結果を生成するか

テキスト内では %i には1つの φ 定義しかなく、%next には1つの add 定義しかありません。表は同一プログラムの3回の動的到達を記録しており、3つの競合する静的定義を導入していません。n=0 または負数の場合、最初の比較で終了し 0 を返し、body → header のバックエッジは実行されません。

choose と count_to の2つの IR セクションを同一ファイル ssa.ll に配置し、opt -passes=verify -disable-output ssa.ll を実行できます。さらに以下の C ドライバーと組み合わせて、2つのブランチと0回/複数回のループを観察します。

/* ssa-main.c：clang ssa.ll ssa-main.c -o ssa-demo */
extern int choose(_Bool);
extern int count_to(int);
int main(void) {
    return choose(1) != 3 || choose(0) != 2 ||
           count_to(-1) != 0 || count_to(0) != 0 || count_to(2) != 2;
}

CFG の body → header バックエッジを保持したまま、%i の φ から [ %next, %body ] を削除した場合、検証器は拒否すべきです。φ の入力は前駆構造と対応している必要があります。%next を通常の値として entry で直接使用した場合、その定義はその使用を支配しないため、同様に拒否されます。検証器が証明するのは IR 構造がルールを満たしていることであり、フロントエンドがソースプログラムの意図を正しく表現しているわけではありません。LLVM φ ルール

1つの φ がどのように初期値と各バックエッジを受け取るか

「どの静的命令か」と「何回目の動的到達か」を2つの座標に分けることで、ループを SSA 違反と誤判定しません。ここでは常に %i の定義は1つだけです。観察位置は header への某回の到達を選択し、進入エッジが φ が初期値を取るのか前回の結果を取るのかを決定します。i=n の回の到達では比較と終了のみが実行され、存在しない next の計算は行われません。

支配境界：定義の影響がどの合流点で選択を必要とするか

DF(X) = {Y | X は Y のある前駆を支配するが、X は Y を厳密に支配しない}。

「厳密でない支配」は、特定のループにおいて Y=X となることを許容するため、支配境界を常に X の支配領域の外の最初のノードと解釈することはできません。

古典的な構築法は、変数の定義ブロックから始まり、反復的な支配境界に φ を挿入し、新しい φ ブロックも定義源として伝播し続けます。Pruned SSA では、変数のエントリでの活性を利用して、不要な φ の挿入を回避します。これはすべての変数に対してすべての合流点に1回挿入するわけではありません。

名前変更：支配木に沿って現在のバージョンを維持する

各ソース変数のバージョンスタックを維持し、ブロックに入る際に φ の結果に対してバージョンを作成します。通常の命令をスキャンする際には、まず使用を現在のバージョンに置き換え、新しい定義に対してバージョンを作成します。ブロックを離れて後続エッジを処理する際には、対応する φ の入力を埋めます。支配木のサブノードを再帰的に処理した後、そのブロックでプッシュされたバージョンをポップします。

未初期化の使用は、ソース言語のセマンティクスまたはフロントエンドのエラー処理によって決定する必要があり、SSA を通過させるために適当に 0 を埋めてはいけません。到達不可能なブロックも、クリーンアップするか、アルゴリズムの規約に従って独立して処理する必要があります。

一般的な CFG（非正規化制御フローを含む）でも SSA を構築できます。すべてのループを単一エントリの自然ループに変換する必要はありません。後続のループ最適化のために正規化形態が必要になる場合もありますが、それは別の問題です。

支配境界：どの流入経路で「必ず通る」条件が崩れるか

「厳密でない支配」を「全く支配しない」と簡略化することはできません。以下に M に自己バックエッジを追加します：M はこのエッジの前駆 M を支配しますが、自身を厳密に支配しないため、M∈DF(M) です。通常の菱形では L または R を選択すると、別のパスが M をそのブランチから支配しなくなる様子が見られます。図の色は実際の支配集合計算からのものであり、CFG の形状自体が支配木であるわけではありません。

$$\mathrm{DF}(X)=\{Y\mid \exists P\in \mathrm{pred}(Y):X\mathrm{dom}P\wedge \neg (X\mathrm{sdom}Y)\}$$

解構：φ が生成するのはエッジ上の並列コピー

ある前駆エッジ上に複数の φ 入力がある場合、それらを結果位置への同時代入と理解できます。例えば、位置割り当て後に a←b と b←a が必要な場合、順序実行ではどちらかの古い値が失われるため、一時位置または適切な交換シーケンスを使用する必要があります。

キーエッジの前駆に複数の後続があり、後続に複数の前駆がある場合、コピーを無条件で前駆の末尾に置くことも、無条件で後続の先頭に置くこともできません。通常、エッジの分割によってそのパス専用の実行位置を構築します。

φ の入力が異なる前駆から来ているからといって、それらがプログラム全体で決して同時にアクティブではないことを意味するわけではありません。ソース値は他の場所でも使用されている可能性があるため、物理位置を共有するには干渉とコピーマージのチェックが必要であり、φ のすべての値を無条件で1つのレジスタに合成することはできません。

一連の交換コピーは同じ古い状態を読み取る必要がある

位置 a、b の古い値がそれぞれ 10、20 で、目標とする並列コピーが a←b、b←a の場合、最初の順序コピーの後に a はすでに 20 になっています。2 回目のコピーで a を読み取ると新しい値が得られ、最終的に両方が 20 になります。一時位置の役割は、先に上書きされた古い値を保持することです。

old = {"a": 10, "b": 20}
expected = {"a": old["b"], "b": old["a"]}
wrong = old.copy()
wrong["a"] = wrong["b"]
wrong["b"] = wrong["a"]
assert wrong == {"a": 20, "b": 20} and wrong != expected

actual = old.copy()
temporary = actual["a"]
actual["a"] = actual["b"]
actual["b"] = temporary
assert actual == expected

この問題は、SSA 値を再利用可能な物理位置にマッピングした後に発生するものであり、SSA 自体が同じ名前に再代入することを許可しているわけではありません。一般的な並列コピーには、非巡回チェーンと複数のサイクルが含まれる可能性があります。他の古い入力を破壊しないコピーを先に配置し、サイクルに遭遇した時点で一時位置を導入します。2つの項目を交換する場合のみ、ここで示す3ステップのテンプレートを直接使用できます。

コピーを単純に P の末尾に移動することはできません。そうすると P→X でもそれが実行されてしまいます。また、M の入口に置くこともできません。そうすると Q→M でも P からのコピーが実行されてしまいます。エッジを分割した後、M の φ 前駆を P から新しいブロックに更新する必要があり、ジャンプターゲットを変更するだけでは不十分です。

古い値が上書きされた後、別のコピーはそれを読み取れるか？

ここで上書きされるのは再利用可能な物理位置であり、SSA 名を再定義しているわけではありません。目標の右辺では同じ古い状態を読み取る必要があります。コピー動作を選択した後、画面には各位置の現在の値と最後の書き込み記録が保持されます。まず直接コピーを2回実行し、リセットして一時位置の試行を行うことで、値が失われる正確な瞬間を見つけることができます。一時位置も魔法ではありません：保存動作が遅すぎると、保存されるのはすでに上書きされた新しい値になってしまいます。

SSA 値と可変メモリとの併存

LLVM の %p = alloca i32 はポインタ値を1回だけ定義し、その後そのポインタが指すメモリに対して複数回 store できます。各 load は新しい SSA 値を生成します。SSA の制約は名前付き値に対して適用されるものであり、ヒープ全体を不変データに変えるものではありません。

mem2reg は、昇格に適したローカルスロットを SSA 値と φ に変換します。エイリアス、アドレスのエスケープ、およびサポートされていないアクセスは昇格に影響します。フロントエンドはまず alloca を使用して可変ローカル変数を表現し、昇格処理に委ねることで、自身ですぐに完全な SSA 構築を実装する必要を回避できます。LLVM 可変変数チュートリアル

検証クイックリファレンス

唯一定義、型、支配関係、φ と前駆エッジの対応、終端命令、および到達不可能なブロックの処理を確認します。CFG を変更する際には、φ の入力も更新する必要があります。エッジを削除しても対応する入力を残しておくと、IR が壊れます。

関連セクション：LLVM IR 実践、データフロー解析、レジスタ割り当て。

参考文献

• LLVM 言語リファレンス。
• LLVM：Mutable Variables。

Keywords: SSA, phi, dominator, dominance frontier, renaming, parallel copy, critical edge, mem2reg