概要
前回の記事ではコード生成の基本概念を見てきました。今回は実際にコードを生成する**アルゴリズム**に焦点を当てます。単純コード生成アルゴリズムから始めて、DAGベースコード生成、最適コード生成、グラフ彩色によるレジスタ割り当て、そしてピープホール最適化まで扱います。
1. 単純コード生成アルゴリズム
1.1 基本アイデア
最も基本的なコード生成アルゴリズムは、3アドレス命令 `x = y op z` を一つずつ処理しながら目的コードを生成します。
核心は**レジスタディスクリプタ**と**アドレスディスクリプタ**を維持しながら、各演算に対して最適なレジスタを選択することです。
1.2 レジスタディスクリプタ（Register Descriptor）
レジスタディスクリプタは各レジスタが現在どの変数の値を保持しているかを追跡します。
初期状態：
R1：空
R2：空
R3：空
命令 "LD R1, a" 実行後：
R1：a
R2：空
R3：空
1.3 アドレスディスクリプタ（Address Descriptor）
アドレスディスクリプタは各変数の現在の値がどこに格納されているかを追跡します。値はレジスタ、メモリ、スタックなど複数の場所に同時に存在できます。
変数 a：メモリ
変数 b：R1、メモリ
変数 c：R2
1.4 getReg関数
`getReg(x = y op z)` 関数は命令の結果を格納するレジスタを選択します。
選択優先順位：
1. yがレジスタRにあり、Rにyだけがあり、yが以後使用されなければ -> Rを選択
2. 空いているレジスタがあれば -> そのレジスタを選択
3. すべてのレジスタが使用中なら -> 最も後に使用される値を保持するレジスタを選択（spill）
1.5 コード生成の例
以下の基本ブロックに対してコードを生成してみましょう。レジスタはR1、R2の2つだけ使用可能と仮定します。
// 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
2. DAGベースコード生成
基本ブロックのDAG表現からコードを生成すると、共通部分式の除去などの最適化が自然に行われます。
2.1 DAGでのノード順序決定
DAGのノードを評価する順序をうまく選択すると、必要なレジスタ数を最小化できます。
核心原則：**あるノードを評価した直後に、そのノードの値を使用する親ノードをすぐに評価**すれば、レジスタに値を長く保持する必要がありません。
// DAG：
// (d: +)
// / \
// (v: +) (u: -)
// / \ / \
// (t: -) (u) a0 c0
// / \
// a0 b0
// 良い順序：t, u, v, d（使用直後に消費）
// 悪い順序：t, v, u, d（tを長く保持する必要あり）
2.2 ヒューリスティック順序決定アルゴリズム
アルゴリズム：DAGノード順序決定
1. ルートノード（出力がないノード）をスタックに入れる
2. スタックが空でない間：
a. スタック頂上のノードnをpopして出力
b. nの子のうちすべての親が既に出力されたものをスタックにpush
c. 複数の子が条件を満たす場合、最も左の子を先にpush
3. ツリーベース最適コード生成
3.1 Ershov数
ツリー形式の式に対して必要な最小レジスタ数を計算する方法です。
**Ershov数**の計算規則：
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個必要
3.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")
labelが大きい方を先に計算するとレジスタ使用が最適化されます。
4. グラフ彩色によるレジスタ割り当て
4.1 干渉グラフ（Interference Graph）
**干渉グラフ**は変数の同時生存（live）関係を表します。
- ノード：プログラムの各変数（または一時値）
- 辺：2つの変数が同時に生存していれば辺で接続
// コード：
// 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
4.2 グラフ彩色
k個のレジスタに変数を割り当てる問題は、干渉グラフの**k-彩色**問題と同じです。
- 隣接するノード（同時生存変数）に同じ色（レジスタ）を割り当ててはいけない
- k-彩色が可能ならk個のレジスタで十分
- 不可能なら一部の変数をメモリにspill
4.3 簡約ベース彩色アルゴリズム
Chaitinのアルゴリズム：
アルゴリズム：グラフ彩色レジスタ割り当て
1. 簡約（Simplify）：
- 次数（degree）がk未満のノードをグラフから除去しスタックにpush
- 除去後に他のノードの次数が減少し得るので繰り返し
2. Spill：
- すべてのノードの次数がk以上なら、一つを潜在的spillとして標示し除去
- spill対象の選択基準：使用頻度が低い変数、ループ外の変数
3. 選択（Select）：
- スタックからノードを一つずつ取り出しグラフに再追加
- 隣接ノードが使用していない色（レジスタ）を割り当て
- 割り当て可能な色がなければ実際のspill発生
4. 実際のSpill処理：
- spillされた変数にロード/ストアコードを挿入
- 干渉グラフを再構成しアルゴリズムを繰り返し
4.4 例
レジスタ2個（R1、R2）で彩色：
// 干渉グラフ：
// 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
5. ピープホール最適化（Peephole Optimization）
5.1 概念
**ピープホール最適化**は生成された目的コードの小さなウィンドウ（peephole）を調べながら改善する技法です。コード生成後の後処理段階で適用されます。
5.2 主なピープホール最適化技法
冗長なロード/ストアの除去
// 最適化前
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 // 乗算をシフトに置換（強度削減）
強度削減（Strength Reduction）
コストの大きい演算を同等でコストの小さい演算に置き換えます。
// 最適化前
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
5.3 ピープホール最適化の特徴
- **局所的最適化**：小さなウィンドウ（通常2-3命令）のみ観察
- **反復適用**：一度の最適化が新たな最適化の機会を作り得るため変化がなくなるまで繰り返し
- **実装が簡単**：パターンマッチングで容易に実装可能
- **効果的**：単純だがコード品質を大幅に改善
6. コード生成技法の比較
| 技法 | 範囲 | 最適性 | 複雑度 |
| -------------------- | -------------- | -------- | ------ |
| 単純コード生成 | 基本ブロック | 準最適 | 低 |
| DAGベース生成 | 基本ブロック | 準最適 | 中 |
| ツリーベース最適生成 | ツリー式 | 最適 | 中 |
| グラフ彩色割り当て | 関数全体 | 準最適 | 高 |
| ピープホール最適化 | 命令ウィンドウ | 局所最適 | 低 |
まとめ
| 概念 | 説明 |
| ------------------ | --------------------------------------------------------- |
| 単純コード生成 | レジスタ/アドレスディスクリプタを活用した逐次的コード生成 |
| getReg | 結果格納用レジスタを選択する核心関数 |
| DAGベース生成 | 共通部分式を自動的に除去しながらコード生成 |
| Ershov数 | ツリー式の最小レジスタ要求量の計算 |
| 干渉グラフ | 同時生存変数の関係をグラフで表現 |
| グラフ彩色 | 干渉グラフのk-彩色によるレジスタ割り当て |
| ピープホール最適化 | 生成コードの小さなウィンドウをパターンマッチングで改善 |
| 強度削減 | コストの大きい演算を安価な演算に置換 |
コード生成アルゴリズムはコンパイラ性能の核心です。単純なアルゴリズムでも合理的なコードを生成できますが、DAGベースのアプローチとグラフ彩色レジスタ割り当てを組み合わせるとはるかに効率的なコードが得られます。ピープホール最適化は最後の仕上げ段階として、簡単ながらも効果的なコード改善を提供します。次の記事では、マシン非依存のコード最適化技法を見ていきます。
현재 단락 (1/224)
前回の記事ではコード生成の基本概念を見てきました。今回は実際にコードを生成する**アルゴリズム**に焦点を当てます。単純コード生成アルゴリズムから始めて、DAGベースコード生成、最適コード生成、グラフ...