[コンパイラ] 14. データフロー分析フレームワーク

// ブロックB：
//  [地点1] d1: x = a + b [地点2]
//  [地点2] d2: y = x * c [地点3]
//
// IN[B] = 地点1での情報
// OUT[B] = 地点3での情報

OUT[B] = f_B(IN[B])

OUT[B] = gen[B] U (IN[B] - kill[B])

// 和集合（Union）：いずれかの経路で成立すれば含む
IN[B] = U OUT[P]  (PはBのすべての先行者)

// 積集合（Intersection）：すべての経路で成立して初めて含む
IN[B] = n OUT[P]  (PはBのすべての先行者)

命令 d: x = y op z に対して：
  gen = 定義d自体
  kill = xに対するその他すべての定義

// ブロックBにd1, d2, ..., dk命令が順に存在する場合
// 後の命令が前の命令を上書きし得る

gen[B] = gen(dk) U (gen(dk-1) - kill(dk)) U ...
kill[B] = kill(d1) U kill(d2) U ... U kill(dk)

OUT[B] = gen[B] U (IN[B] - kill[B])
IN[B]  = U OUT[P]  (PはBのすべての先行者)

// フローグラフ：
//   B1 -> B2 -> B3
//          ^     |
//          +-----+

// B1: d1: x = 5        gen={d1}, kill={d2,d4}
// B2: d2: x = x + 1    gen={d2}, kill={d1,d4}
// B3: d3: y = x         gen={d3}, kill={}
//     d4: x = y + 1     gen={d4}, kill={d1,d2}

// gen[B3] = {d4} U ({d3} - {d1,d2}) = {d3, d4}
// kill[B3] = {d1, d2}

初期値：OUT[B] = {}（すべてのBに対して）

反復1：
  IN[B1] = {}
  OUT[B1] = {d1} U ({} - {d2,d4}) = {d1}

  IN[B2] = OUT[B1] U OUT[B3] = {d1} U {} = {d1}
  OUT[B2] = {d2} U ({d1} - {d1,d4}) = {d2}

  IN[B3] = OUT[B2] = {d2}
  OUT[B3] = {d3,d4} U ({d2} - {d1,d2}) = {d3,d4}

反復2：
  IN[B2] = OUT[B1] U OUT[B3] = {d1} U {d3,d4} = {d1,d3,d4}
  OUT[B2] = {d2} U ({d1,d3,d4} - {d1,d4}) = {d2,d3}

  IN[B3] = OUT[B2] = {d2,d3}
  OUT[B3] = {d3,d4} U ({d2,d3} - {d1,d2}) = {d3,d4}

反復3：
  IN[B2] = {d1} U {d3,d4} = {d1,d3,d4}（変化なし）
  -> 収束！

// 伝達関数（逆方向）
IN[B]  = use[B] U (OUT[B] - def[B])
OUT[B] = U IN[S]  (SはBのすべての後続者)

// ブロックB：
//   x = y + z    // use: {y, z}, def: {x}
//   a = x + 1    // use: {x}, def: {a}（xは上で定義済みなのでuse[B]に含まれない）

// use[B] = {y, z}（定義前に使用された変数）
// def[B] = {x, a}（定義された変数）

// B1: a = 1; b = 2
// B2: c = a + b; d = c - a
// B3: d = b + d;（出口）

// use[B1] = {}, def[B1] = {a, b}
// use[B2] = {a, b}, def[B2] = {c, d}
// use[B3] = {b, d}, def[B3] = {d}

// 初期値：IN[B] = {}（すべてのBに対して）

反復1：（逆方向：B3 -> B2 -> B1）
  OUT[B3] = {}（出口ブロック）
  IN[B3] = {b, d} U ({} - {d}) = {b, d}

  OUT[B2] = IN[B3] = {b, d}
  IN[B2] = {a, b} U ({b, d} - {c, d}) = {a, b}

  OUT[B1] = IN[B2] = {a, b}
  IN[B1] = {} U ({a, b} - {a, b}) = {}

  -> 収束！（変化なし）

OUT[B]   = e_gen[B] U (IN[B] - e_kill[B])
IN[B]    = n OUT[P]  (PはBのすべての先行者)
IN[ENTRY] = {}

// B1: t1 = a + b; c = t1
//     e_gen[B1] = {a+b}
//     e_kill[B1] = {cを含む式}

// B2: t2 = a + b; d = t2 - c
//     e_gen[B2] = {a+b, t2-c}
//     e_kill[B2] = {dを含む式}

// B3: a = 1
//     e_gen[B3] = {}
//     e_kill[B3] = {aを含むすべての式} = {a+b}

OUT[ENTRY] = {}     // 入口点ではどの式も利用可能でない
OUT[B] = U          // 他のブロックは全体集合（すべての式）で初期化
                    // （積集合なので大きな値から始めないと正しく収束しない）

アルゴリズム：順方向データフロー分析

入力：フローグラフ、gen/kill集合、合流演算
出力：各ブロックのIN/OUT集合

1. 初期化
   OUT[ENTRY] = 初期値
   for (すべてのブロック B != ENTRY)
       OUT[B] = 初期値

2. 反復
   changed = true
   while (changed)：
       changed = false
       for (すべてのブロック B != ENTRY)：
           IN[B] = meet(OUT[P] for all predecessors P)
           oldOUT = OUT[B]
           OUT[B] = gen[B] U (IN[B] - kill[B])
           if OUT[B] != oldOUT：
               changed = true

// 到達定義分析の束
// 元素：定義の部分集合 (2^D)
// 順序：集合包含関係（部分集合）
// meet演算：和集合 (U)
// bottom：空集合 ({})
// top：全体集合 (D)

// 利用可能式分析の束
// 元素：式の部分集合 (2^E)
// 順序：逆方向集合包含関係（上位集合）
// meet演算：積集合
// bottom：全体集合 (E)
// top：空集合 ({})

// 保守的（conservative）分析：
// - 安全な側に近似
// - 最適化の機会を逃す可能性はあるが、誤った最適化は行わない

// 到達定義：実際より多くの定義が到達すると分析
//   -> 定数伝播を適用できない場合が生じ得る（安全）

// 利用可能式：実際より少ない式が利用可能と分析
//   -> 共通部分式除去を適用できない場合が生じる（安全）

// 定義d1, d2, d3, d4がある場合
// gen[B] = {d1, d3} -> ビットベクトル：1010
// kill[B] = {d2}    -> ビットベクトル：0100

// 伝達関数の計算：
// OUT = gen | (IN & ~kill)  （ビット演算で一度に処理）

アルゴリズム：ワークリストベース反復

1. すべてのブロックをワークリストに追加
2. ワークリストが空でない間：
   a. ブロックBをワークリストから取り出す
   b. OUT[B]を再計算
   c. OUT[B]が変更された場合、Bの後続者をワークリストに追加