[コンパイラ] 13. マシン非依存コード最適化の基礎

// 最適化前
a = b + c
d = a - e
f = b + c    // b + cは既に計算済み
g = f - e

// 最適化後
a = b + c
d = a - e
f = a        // b + cの代わりにaを再利用
g = f - e    // またはg = d（a-eも共通部分式）

// ブロックB1：
//   t1 = a + b
//   ...
// ブロックB2：（B1から到達可能、aとbが変更されていない）
//   t2 = a + b    // B1のt1と同じ値

// 最適化後
// ブロックB2：
//   t2 = t1       // 再利用

// Cコード
x = a[i][j] + a[i][j+1];

// コンパイル時に生成される中間コード
t1 = i * n       // 行オフセット
t2 = t1 + j      // a[i][j]のインデックス
t3 = a[t2]
t4 = i * n       // 共通部分式！（t1と同じ）
t5 = t4 + j + 1  // a[i][j+1]のインデックス
t6 = a[t5]
x = t3 + t6

// 最適化後
t1 = i * n
t2 = t1 + j
t3 = a[t2]
t5 = t1 + j + 1  // t4の代わりにt1を再利用
t6 = a[t5]
x = t3 + t6

// 最適化前
a = b + c       // aがその後使用されなければデッドコード
d = e * f
return d

// 最適化後
d = e * f
return d

// Cコードの例
int debug = 0;    // デバッグモードオフ

void process() {
    // ... 処理ロジック ...

    if (debug) {    // 条件は常にfalse
        printf("Debug info");  // デッドコード
    }
}

// 最適化前
x = 3 + 5
y = x * 2

// 定数畳み込み後
x = 8
y = x * 2

// 定数伝播 + 定数畳み込み後
x = 8
y = 16

// 最適化前
n = 10
i = 0
limit = n - 1

// 定数伝播後
n = 10
i = 0
limit = 10 - 1  // nを10に置換

// 定数畳み込み後
n = 10
i = 0
limit = 9

// 最適化前
x = 1
if x > 0 goto L1
goto L2

// 定数伝播 + 定数畳み込み後
x = 1
if 1 > 0 goto L1  // 常にtrue
goto L2            // 到達不能

// 分岐簡約後
x = 1
goto L1

// 最適化前
while (i < limit) {
    // t = n * 4 はループ不変
    t = n * 4
    a[i] = t + i
    i = i + 1
}

// 最適化後
t = n * 4          // ループ外に移動
while (i < limit) {
    a[i] = t + i
    i = i + 1
}

命令 s: x = y op z をループ外に移動できる条件：

1. sが含まれるブロックがループのすべての出口を支配（dominate）
2. xがループ内で他の場所で定義されていない
3. ループ内でxを使用するすべての箇所がsの定義にのみ到達

// iは基本誘導変数（毎反復+1）
// jは派生誘導変数（j = 4*iなので毎反復+4）
for (i = 0; i < n; i++) {
    j = 4 * i
    a[j] = 0
}

// 最適化前
i = 0
L1: if i >= n goto L2
    j = 4 * i        // 乗算（高コスト）
    a[j] = 0
    i = i + 1
    goto L1
L2:

// 強度削減後
i = 0
j = 0              // jの初期値
L1: if i >= n goto L2
    a[j] = 0
    i = i + 1
    j = j + 4       // 乗算を加算に置換
    goto L1
L2:

// 強度削減後
i = 0
j = 0
L1: if i >= n goto L2
    a[j] = 0
    i = i + 1
    j = j + 4
    goto L1
L2:

// 誘導変数除去後（iをjに置換）
j = 0
limit = 4 * n      // 終了条件の変換
L1: if j >= limit goto L2
    a[j] = 0
    j = j + 4
    goto L1
L2:

// 最適化前
x = y
z = x + 1     // xの代わりにy使用可能

// コピー伝播後
x = y          // この行はデッドコードになり得る
z = y + 1

// 共通部分式除去後
a = b + c
...
f = a          // b + cの代わりにコピー

// コピー伝播後（fの使用箇所にaを代入）
// fが不要になればデッドコードとして除去

// ブロックB：
//   d1: x = a + b    // gen: d1, kill: xの他のすべての定義
//   d2: y = c - d    // gen: d2, kill: yの他のすべての定義

// 到達定義分析の伝達関数
OUT[B] = gen(B) U (IN[B] - kill(B))

// IN[B]はすべての先行ブロックのOUTの和集合
IN[B] = U OUT[P]  (PはBのすべての先行者)

1. 定数畳み込み / 定数伝播
   -> 定数を先に確定して他の最適化に貢献

2. 共通部分式の除去
   -> 重複計算の除去

3. コピー伝播
   -> 不要なコピーの除去準備

4. デッドコード除去
   -> 上記の最適化によって発生したデッドコードの整理

5. ループ不変コード移動
   -> ループ外へのコード移動

6. 誘導変数 / 強度削減
   -> ループ内のコスト削減

7. 反復（収束するまで）