[コンパイラ] 12. コード生成アルゴリズムとレジスタ割り当て

初期状態：
  R1：空
  R2：空
  R3：空

命令 "LD R1, a" 実行後：
  R1：a
  R2：空
  R3：空

変数 a：メモリ
変数 b：R1、メモリ
変数 c：R2

// 3アドレスコード
t = a - b
u = a - c
v = t + u
d = v + u

命令：t = a - b
  getReg -> R1（空）
  コード：LD  R1, a      // R1 = a
         LD  R2, b      // R2 = b
         SUB R1, R1, R2 // R1 = a - b = t
  レジスタ：R1=t, R2=b
  ディスクリプタ：t->R1, a->メモリ, b->R2/メモリ

命令：u = a - c
  getReg -> R2（bは以後不要）
  コード：LD  R2, a      // R2 = a
         SUB R2, R2, c  // R2 = a - c = u
  レジスタ：R1=t, R2=u

命令：v = t + u
  getReg -> R1（tは以後不要）
  コード：ADD R1, R1, R2 // R1 = t + u = v
  レジスタ：R1=v, R2=u

命令：d = v + u
  getReg -> R1（vは以後不要）
  コード：ADD R1, R1, R2 // R1 = v + u = d
  レジスタ：R1=d, R2=u

// 基本ブロック終了：生存変数dをメモリに格納
  コード：ST  d, R1

LD  R1, a
LD  R2, b
SUB R1, R1, R2
LD  R2, a
SUB R2, R2, c
ADD R1, R1, R2
ADD R1, R1, R2
ST  d, R1

// DAG：
//        (d: +)
//       /      \
//    (v: +)    (u: -)
//    /    \    /    \
// (t: -)  (u) a0    c0
//  /   \
// a0   b0

// 良い順序：t, u, v, d（使用直後に消費）
// 悪い順序：t, v, u, d（tを長く保持する必要あり）

アルゴリズム：DAGノード順序決定

1. ルートノード（出力がないノード）をスタックに入れる
2. スタックが空でない間：
   a. スタック頂上のノードnをpopして出力
   b. nの子のうちすべての親が既に出力されたものをスタックにpush
   c. 複数の子が条件を満たす場合、最も左の子を先にpush

1. リーフノード：label = 1（左の子）または 0（右の子がメモリ）
2. 内部ノードの2つの子のlabelが異なれば：label = max(l1, l2)
3. 2つの子のlabelが同じなら：label = l1 + 1

//       (*)      label = 2
//      /   \
//    (+)    (-)   label = 1, 1
//   / \    / \
//  a   b  c   d   リーフ
//
// (+)：left=1, right=0 -> 異なるので max(1,0) = 1
// (-)：left=1, right=0 -> 異なるので max(1,0) = 1
// (*)：left=1, right=1 -> 同じなので 1+1 = 2
//
// 結論：レジスタ2個必要

アルゴリズム：genCode(node)

nodeがリーフなら：
    LD Ri, node.name
そうでなければ：
    left = node.leftChild
    right = node.rightChild

    if left.label >= right.label：
        genCode(left)   // 結果がRiに
        genCode(right)  // 結果がRjに
        emit("OP Ri, Ri, Rj")
    else：
        genCode(right)  // 右を先に
        genCode(left)
        emit("OP Ri, Rj, Ri")

// コード：
// 1: a = ...
// 2: b = ...     (a live)
// 3: c = a + b   (a, b live)
// 4: d = c       (c live)
// 5: e = b + d   (b, d live)
// 6: return e

// 干渉グラフ：
//   a --- b
//   |
//   c     d --- b
//         |
//         e

アルゴリズム：グラフ彩色レジスタ割り当て

1. 簡約（Simplify）：
   - 次数（degree）がk未満のノードをグラフから除去しスタックにpush
   - 除去後に他のノードの次数が減少し得るので繰り返し

2. Spill：
   - すべてのノードの次数がk以上なら、一つを潜在的spillとして標示し除去
   - spill対象の選択基準：使用頻度が低い変数、ループ外の変数

3. 選択（Select）：
   - スタックからノードを一つずつ取り出しグラフに再追加
   - 隣接ノードが使用していない色（レジスタ）を割り当て
   - 割り当て可能な色がなければ実際のspill発生

4. 実際のSpill処理：
   - spillされた変数にロード/ストアコードを挿入
   - 干渉グラフを再構成しアルゴリズムを繰り返し

// 干渉グラフ：
//   a --- b --- c
//
// 次数：a=1, b=2, c=1

// 簡約：a（次数1 < 2）除去 -> c（次数1 < 2）除去 -> b（次数0 < 2）除去
// スタック：[a, c, b]

// 選択：
//   b -> R1（隣接なし、どの色でも可）
//   c -> R2（隣接b=R1なのでR2）
//   a -> R2（隣接b=R1なのでR2）

// 結果：a=R2, b=R1, c=R2

// 最適化前
ST a, R1
LD R1, a    // 不要なロード

// 最適化後
ST a, R1
// LD除去（R1に既にaの値がある）

// 最適化前
BR L2
ADD R1, R2, R3   // 到達不能
SUB R4, R5, R6   // 到達不能
L2:

// 最適化後
BR L2
L2:
// またはBR自体も除去可能（連続したラベルなら）

// 最適化前
BR L1
...
L1: BR L2

// 最適化後
BR L2     // L1を飛ばして直接L2へ

// 最適化前
ADD R1, R1, #0   // x + 0 = x
MUL R2, R2, #1   // x * 1 = x
MUL R3, R3, #2   // x * 2

// 最適化後
// ADD除去（恒等演算）
// MUL除去（恒等演算）
SHL R3, R3, #1   // 乗算をシフトに置換（強度削減）

// 最適化前
MUL R1, R2, #4    // 乗算（遅い）
MUL R3, R4, #8
DIV R5, R6, #2

// 最適化後
SHL R1, R2, #2    // 左シフト（速い）：x*4 = x<<2
SHL R3, R4, #3    // x*8 = x<<3
SHR R5, R6, #1    // 右シフト：x/2 = x>>1

// 最適化前
LD  R1, a
ADD R1, R1, #1
ST  a, R1

// 最適化後（機械がINC命令をサポートする場合）
INC a