[コンパイラ] 19. SSA形式と現代コンパイラ最適化

// 一般的な3アドレスコード
x = 1
x = 2       // xが2回定義されている！
y = x + 1   // どのxを使っているのか？ -> 2番目の定義

// SSA形式
x1 = 1
x2 = 2      // 別のバージョン！
y1 = x2 + 1 // 明確にx2を使用

// 元                        // SSA
a = x + y                 a1 = x1 + y1
b = a - 1                 b1 = a1 - 1
a = y + b                 a2 = y1 + b1
b = 4 * a                 b2 = 4 * a2

// 元のコード：
if (cond)
    x = 1;     // 経路A
else
    x = 2;     // 経路B
y = x + 1;     // xは1か2か？

// SSA形式：
if (cond)
    x1 = 1;          // 経路A
else
    x2 = 2;          // 経路B
x3 = phi(x1, x2);   // 合流地点：経路に応じてx1またはx2を選択
y1 = x3 + 1;

// phi関数は合流ブロックの先頭に配置
// 複数のphi関数があればすべて「同時に」実行されると見なす

B3:
  x3 = phi(x1, x2)   // B1から来ればx1、B2から来ればx2
  y3 = phi(y1, y2)
  z1 = x3 + y3

// 元：
i = 0
loop:
  if (i >= n) goto exit
  i = i + 1
  goto loop
exit:

// SSA：
i1 = 0
loop:
  i2 = phi(i1, i3)    // ループ進入時i1、ループ反復時i3
  if (i2 >= n1) goto exit
  i3 = i2 + 1
  goto loop
exit:

// 理由：
// Bが支配する領域内ではxの定義が唯一
// 支配境界で他の経路の定義と合流し得る
// -> phi関数が必要な箇所 = 支配境界

アルゴリズム：SSA構築（2段階）

第1段階：Phi関数の挿入
  for（各変数v）：
    W = vを定義するブロックの集合
    while Wが空でない：
      B = Wからブロックを一つ取り出す
      for（DF(B)の各ブロックD）：
        if Dにvに対するphi関数がなければ：
          Dの先頭にphi関数挿入：v = phi(v, v, ...)
          if DがWになければWにDを追加
          //（phi関数もvの新たな定義であるため）

第2段階：変数名の変更（Renaming）
  支配者木を深さ優先で巡回しながら：
    各定義に新しいバージョン番号を付与
    各使用を現在有効なバージョンに置換
    phi関数の引数を適切な先行ブロックのバージョンに設定

// CFG：
//   B1: x = 5
//        |
//   B2: if cond
//      /     \
//   B3: x=10  B4: x=20
//      \     /
//   B5: y = x

// 支配境界：
// DF(B3) = {B5}
// DF(B4) = {B5}

// 第1段階：B5にphi関数挿入
//   B5: x = phi(x, x)

// 第2段階：名前変更
//   B1: x1 = 5
//   B2: if cond
//   B3: x2 = 10
//   B4: x3 = 20
//   B5: x4 = phi(x2, x3)  // B3から来ればx2、B4から来ればx3
//       y1 = x4

// SSAコード：
x1 = 3
y1 = 5
z1 = x1 + y1    // 定数畳み込み：z1 = 8
w1 = z1 * 2     // 定数畳み込み：w1 = 16
if (w1 > 10) goto L1  // 常にtrue -> goto L1

// 各変数が1回だけ定義されるので：
// x1の値 = 3（確定）
// y1の値 = 5（確定）
// z1の値 = 8（確定）
// 到達定義分析なしで直接伝播可能！

アルゴリズム：SCCP

束：Top（未確認）> 定数値 > Bottom（非定数）

1. すべてのSSA値をTopで初期化
2. 入口ブロックを実行可能として標示
3. ワークリストからSSA辺とCFG辺を取り出しながら：
   - SSA辺：定義の値が変更されたら使用箇所を更新
   - CFG辺：実行可能な辺のみ考慮
4. 収束するまで反復

核心：実行不能な経路の値は考慮しない
-> phi(3, Top) = 3（Topはまだ到達していない経路）

// SSAコード：
x1 = a1 + b1    // x1を使用する箇所がない -> デッドコード
y1 = c1 * d1    // y1は下で使用される
z1 = y1 + 1
return z1

// x1除去後：
y1 = c1 * d1
z1 = y1 + 1
return z1

アルゴリズム：攻撃的DCE

1. 副作用のある命令を「有用」としてマーク
   （return、store、入出力、関数呼び出しなど）
2. 有用な命令が使用するSSA値の定義を「有用」としてマーク
3. 反復：新たに有用になった命令の被演算子の定義を追加マーク
4. 有用でないすべての命令を除去

// 従来のDCEより強力：不要な制御フローまで除去可能

// SSAコード：
a1 = x1 + y1
b1 = x1 + y1    // a1と同じ値！

// 大域的値番号付け：
// x1 + y1に値番号#1を付与
// a1の値番号 = #1
// b1の値番号 = #1（同じ演算、同じ被演算子）
// -> b1をa1に置換

アルゴリズム：SSAベースGVN

ハッシュテーブル維持：（演算子、被演算子の値番号）-> 値番号

for（支配者木の深さ優先順序で各命令）：
    被演算子の値番号を検索
    （演算子、被演算子値番号）でハッシュテーブル検索
    if 発見：
        既存の値番号をこの命令に配定（重複！）
    else：
        新しい値番号を付与しハッシュテーブルに追加

// SSA：
//   B1: a1 = x1 + y1          // 値番号：v1
//       |
//   B2: b1 = x1 + y1          // ハッシュ検索：(+ v(x1) v(y1)) -> v1発見！
//       c1 = b1 * 2            // b1をa1に置換可能
//
// 最適化後：
//   B1: a1 = x1 + y1
//   B2: c1 = a1 * 2            // b1除去

// SSAが助けになる最適化：
// 1. 定数伝播      -> def-useチェーンで効率的に伝播
// 2. デッドコード除去 -> 使用箇所のないdefを即座に識別
// 3. 値番号付け    -> ハッシュベースで重複計算を識別
// 4. コピー伝播    -> phi関数を通じてコピー関係を追跡
// 5. 部分冗長除去  -> SSA辺を通じた効率的分析
// 6. レジスタ割り当て -> SSAの生存範囲がより短い

// SSA：
//   B1: x1 = 5
//        |
//   B2: x2 = 10
//        |
//   B3: x3 = phi(x1, x2)

// phi除去後：
//   B1: x1 = 5
//       x3 = x1      // B3からB1の末尾に移動
//        |
//   B2: x2 = 10
//       x3 = x2      // B3からB2の末尾に移動
//        |
//   B3:（phi除去済み、x3を使用）

// SSA：
//   B3: a2 = phi(a1, b1)
//       b2 = phi(b1, a1)
//   （swap意味：B2から来ればaとbを交換）

// 誤った変換：
//   B2末尾：a2 = b1    // a2にb1の値
//           b2 = a1    // 正しい

// 正しい変換（一時変数使用）：
//   B2末尾：temp = a1
//           a2 = b1
//           b2 = temp

// phi除去後：
//   B1: x1 = 5
//       x3 = x1     // 不要なコピー

// コピー合体後：
//   B1: x3 = 5      // x1とx3を同じ変数に統合

// 最小SSA：
x2 = phi(x1, x1)   // 2つの引数が同じ -> 不要
y2 = phi(y1, ...)   // y2がその後使用されない -> 不要

// 枝刈りSSA：上記phi関数を挿入しない

// 通常のSSA：
x3 = phi(x1, x2)

// ゲート付きSSA：
x3 = gamma(cond, x1, x2)  // condがtrueならx1、falseならx2
// 最適化により有用な情報を提供