[コンパイラ] 15. ループ最適化とコード移動

// フローグラフ：
//   1 -> 2 -> 3 -> 4
//        |    ^    |
//        v    |    v
//        5 ---+    6
//                  |
//                  v
//                  7

// 支配者木：
//        1
//        |
//        2
//      / | \
//     3  5  6
//     |     |
//     4     7
//
// 解釈：1 dom すべてのノード
//       2 dom 3,4,5,6,7
//       3 dom 4
//       6 dom 7

アルゴリズム：支配者計算

初期化：
  DOM[entry] = {entry}
  DOM[n] = すべてのノードの集合（n != entry）

反復（収束するまで）：
  for（すべてのノード n != entry）：
    DOM[n] = {n} U ( n DOM[p] )  // pはnのすべての先行者
                                  // 先行者のDOMの積集合にnを追加

DF(n) = ノードyの集合 | nがyの先行者を支配するが、y自体は（厳密には）支配しない

// フローグラフで：
//   1 -> 2 -> 3 -> 4
//        ^         |
//        +---------+   // 4 -> 2は後退辺（2 dom 4）

アルゴリズム：自然ループ構成（後退辺 n -> d）

1. loop = {d}
2. stack = {n}（nがdと異なる場合）
3. while stackが空でない：
     m = stackからpop
     if mがloopにない：
         loopにmを追加
         mのすべての先行者をstackにpush
4. 結果：loop

// フローグラフ：
//   B1 -> B2 -> B3 -> B4
//          ^          |
//          +----------+  （後退辺：B4 -> B2）
//          |
//          +-- B5（B2 -> B5、B5 -> B2も後退辺）

// 後退辺 B4 -> B2 の自然ループ：
//   {B2, B3, B4}（B2を経由せずB4に到達可能：B3、B4）

// 後退辺 B5 -> B2 の自然ループ：
//   {B2, B5}

// 外側ループ：{B1, B2, B3, B4, B5}
// 内側ループ：{B3, B4}
//
// 内側ループを先に最適化した後、外側ループを最適化
// （内側から外側へ）

アルゴリズム：ループ不変コード検出

1. 定数であるかループ外でのみ定義された被演算子を持つ命令を
   「ループ不変」としてマーク
2. 反復：
   - すべての被演算子が定数であるか、ループ外定義であるか、
     既にループ不変とマークされた定義一つだけを持つ命令を
     新たに「ループ不変」としてマーク
3. 新たなマークがなければ終了

// ループ：
//   B2: i = i + 1
//       t1 = n * 4       // nはループ外で定義 -> ループ不変
//       t2 = a[t1]       // t1がループ不変でaがループ内で不変 -> ループ不変
//       t3 = t2 + i
//       if i < 100 goto B2

// 1回目：t1 = n * 4 マーク（nがループ外定義）
// 2回目：t2 = a[t1] マーク（t1がループ不変）
// 3回目：もうない -> 終了

// 安全な場合：
//   preheader -> [B1: s: x=... ] -> B2（出口）
//   B1が出口を支配するので移動可能

// 危険な場合：
//   preheader -> B1 -> B3（出口）
//                |
//                v
//               B2: s: x=...
//   B2が出口B3を支配しない -> 移動不可
//   （sが実行されない経路が存在）

// 移動前：
//   ... -> header -> body -> ...
//           ^               |
//           +---------------+

// preheader挿入後：
//   ... -> preheader -> header -> body -> ...
//                        ^               |
//                        +---------------+

// ループ不変コードをpreheaderに配置：
//   preheader：
//     t1 = n * 4       // 移動されたコード
//     t2 = a[t1]       // 移動されたコード

// 例：
// i = i + 1        // iは基本誘導変数
// t1 = 4 * i       // t1は派生誘導変数：(i, 4, 0)
// t2 = t1 + base   // t2は派生誘導変数：(i, 4, base)

アルゴリズム：誘導変数検出

ステップ1：基本誘導変数の検出
  - ループ内で i = i + c 形式でのみ定義される変数を見つける

ステップ2：派生誘導変数の検出
  - j = c1 * i（iが基本誘導変数、c1がループ定数）
    -> jの三つ組：(i, c1, 0)
  - j = k + c2（kが誘導変数 (i, a, b)、c2がループ定数）
    -> jの三つ組：(i, a, b+c2)
  - j = c1 * k（kが誘導変数 (i, a, b)）
    -> jの三つ組：(i, c1*a, c1*b)

// 元のコード：
// i = 0
// loop:
//   t1 = 4 * i       // 乗算
//   a[t1] = 0
//   i = i + 1
//   if i < n goto loop

// 強度削減後：
// i = 0
// t1 = 0             // 初期値：4 * 0 = 0
// loop:
//   a[t1] = 0
//   i = i + 1
//   t1 = t1 + 4      // 乗算 -> 加算
//   if i < n goto loop

// 強度削減後：
// i = 0
// t1 = 0
// loop:
//   a[t1] = 0
//   i = i + 1         // iは比較でのみ使用
//   t1 = t1 + 4
//   if i < n goto loop

// 誘導変数除去後：
// t1 = 0
// limit = 4 * n       // 終了条件変換（ループ外で1回だけ計算）
// loop:
//   a[t1] = 0
//   t1 = t1 + 4
//   if t1 < limit goto loop
//
// iが完全に除去！

// 元（100回反復）
for (i = 0; i < 100; i++) {
    a[i] = 0;
}

// 4倍展開（25回反復）
for (i = 0; i < 100; i += 4) {
    a[i]   = 0;
    a[i+1] = 0;
    a[i+2] = 0;
    a[i+3] = 0;
}

// 反復回数が展開係数の倍数でない場合
// 余り処理が必要

// nが4の倍数でない可能性がある場合
i = 0
// メインループ（4倍展開）
while (i + 3 < n) {
    a[i] = 0; a[i+1] = 0; a[i+2] = 0; a[i+3] = 0;
    i += 4;
}
// 余り処理
while (i < n) {
    a[i] = 0;
    i++;
}

// 元のコード（行列の1行を初期化）
i = 0
loop:
    t1 = i * 8           // 誘導変数（乗算）
    t2 = base + t1       // 誘導変数
    *t2 = 0.0
    i = i + 1
    if i < n goto loop

// ステップ1：ループ不変コード移動
//   （この例では該当なし）

// ステップ2：強度削減
i = 0
t1 = 0                   // 初期値
t2 = base                // 初期値
loop:
    *t2 = 0.0
    i = i + 1
    t1 = t1 + 8          // 乗算 -> 加算
    t2 = t2 + 8          // 乗算 -> 加算
    if i < n goto loop

// ステップ3：誘導変数除去（iとt1を除去）
t2 = base
limit = base + n * 8     // ループ外で1回計算
loop:
    *t2 = 0.0
    t2 = t2 + 8
    if t2 < limit goto loop

// ステップ4：ループ展開（2倍）
t2 = base
limit = base + n * 8
loop:
    *t2 = 0.0
    *(t2 + 8) = 0.0
    t2 = t2 + 16
    if t2 < limit goto loop
// （余り処理コードは省略）