[コンパイラ] 11. コード生成 - 基本ブロックとフローグラフ

概要

コンパイラの最終段階であるコード生成（Code Generation）は、中間表現（IR）を目的機械の命令に変換するプロセスです。この段階での決定が最終実行ファイルの性能に直接影響を与えるため、コード生成器の設計はコンパイラ実装で最も重要な部分の一つです。

この記事では、コード生成器設計時に考慮すべき主要な課題、目的言語モデル、アドレス指定方式、基本ブロックとフローグラフ、そしてDAG表現について見ていきます。

1. コード生成器設計の主要な課題

コード生成器を設計する際には、以下の核心的な課題を考慮する必要があります。

1.1 命令選択（Instruction Selection）

中間コードの各演算を目的機械の命令にマッピングするプロセスです。一つのIR演算が複数の命令の組み合わせで実装できるため、最適な命令を選択することが重要です。

例えば、3アドレスコード a = a + 1 を変換する場合：

// 単純変換
LD  R0, a
ADD R0, R0, #1
ST  a, R0

// インクリメント命令がある場合
INC a

目的機械に INC 命令があれば1行で処理できますが、単純変換では3つの命令が必要です。命令選択がコード品質に与える影響が大きい理由です。

1.2 レジスタ割り当て（Register Allocation）

レジスタはCPUで最も高速にアクセスできる記憶域です。変数をレジスタに割り当てるとメモリアクセスを削減し、性能を大幅に向上させることができます。

レジスタ割り当ては2つの下位問題に分かれます：

• レジスタ割り当て（Register Allocation）：どの変数をレジスタに入れるか決定
• レジスタ割り付け（Register Assignment）：具体的にどのレジスタに入れるか決定

レジスタ数は限られているため、同時に使用中（live）の変数がレジスタ数より多い場合、一部の変数をメモリに退避（spill）する必要があります。

1.3 評価順序（Evaluation Order）

演算の実行順序を変えると、必要なレジスタ数を減らすことができます。例えば：

// 順序A：レジスタ3個必要
t1 = a + b
t2 = c + d
t3 = t1 * t2

// 順序B：レジスタ2個で十分
t1 = a + b
t2 = c + d
t1 = t1 * t2

最適な評価順序を求めることは一般にNP完全問題であるため、実用的なヒューリスティックを使用します。

2. 目的言語モデル

コード生成器は特定の目的機械を対象とします。ここでは一般的なレジスタ機械モデルを使用します。

2.1 命令形式

仮想的な目的機械が以下の命令をサポートすると仮定します：

LD  dst, addr    // メモリからレジスタにロード
ST  addr, src    // レジスタからメモリにストア
OP  dst, src1, src2  // 算術/論理演算
BR  label        // 無条件分岐
CBR cond, label  // 条件分岐

2.2 アドレス指定モード

目的機械は様々なアドレス指定モードを提供します：

3. 目的コードのアドレス指定

プログラムのデータがメモリに配置される方式によって、アドレスの生成方法が異なります。

3.1 静的割り当て（Static Allocation）

コンパイル時にすべてのデータのアドレスが決定されます。グローバル変数や静的変数に使用されます。

// 静的割り当ての例
// 変数xがアドレス100番地に割り当てられた場合
LD R1, 100      // xの値をR1にロード
ADD R1, R1, #1  // x + 1を計算
ST 100, R1      // 結果をxに格納

静的割り当ての特徴：

• コンパイル時にアドレスが決定されるため高速アクセスが可能
• 再帰呼び出しをサポートできない（各呼び出しに別の空間が必要）
• C言語の static 変数がこの方式を使用

3.2 スタック割り当て（Stack Allocation）

ローカル変数は関数呼び出し時にスタックフレームに割り当てられます。

// スタックフレーム構造
// +------------------+
// | リターンアドレス   |  <- SP + 0
// | 前フレームポインタ |  <- SP + 4
// | ローカル変数 a     |  <- SP + 8
// | ローカル変数 b     |  <- SP + 12
// +------------------+

// ローカル変数aにアクセス
LD R1, 8(SP)     // SP + 8にあるaをロード

スタック割り当ては再帰呼び出しを自然にサポートします。各呼び出しごとに新しいスタックフレームが作成されるためです。

3.3 活性化レコード（Activation Record）

関数が呼び出されると、以下の情報を含む活性化レコードがスタックに作成されます：

• 実引数（actual parameters）
• 返り値（return value）
• 制御リンク（control link） - 呼び出し元の活性化レコードを指す
• アクセスリンク（access link） - 非局所変数アクセス用
• マシン状態の保存（saved machine state）
• ローカル変数と一時変数

// 関数呼び出し時のコード生成例
// call f(a, b)

// 1. パラメータの受け渡し
ST  0(SP), a     // 第1引数
ST  4(SP), b     // 第2引数
// 2. リターンアドレスの保存
ST  8(SP), returnAddr
// 3. SPの更新と分岐
ADD SP, SP, #frameSize
BR  f_entry

4. 基本ブロックとフローグラフ

4.1 基本ブロック（Basic Block）

基本ブロックは以下の条件を満たす連続した命令シーケンスです：

1. 制御フローはブロックの最初の命令にのみ進入
2. ブロックの最後の命令でのみ制御が出る
3. 途中に分岐や分岐先がない

基本ブロックを構成するアルゴリズム：

アルゴリズム：基本ブロック分割

入力：3アドレス命令シーケンス

ステップ1：リーダー（leader）の決定
  - 最初の命令はリーダー
  - 条件/無条件分岐の対象命令はリーダー
  - 分岐命令の直後の命令はリーダー

ステップ2：各リーダーから次のリーダー（または終端）直前までが一つの基本ブロック

例：

// 3アドレスコード
1: i = 1
2: j = 1
3: t1 = 10 * i
4: t2 = t1 + j
5: t3 = 8 * t2
6: a[t3] = 0.0
7: j = j + 1
8: if j <= 10 goto 3
9: i = i + 1
10: if i <= 10 goto 2
11: i = 1

リーダー：1番（最初の命令）、3番（8番の分岐先）、2番（10番の分岐先）、9番（8番の次）、11番（10番の次）

基本ブロック：

• B1：命令1-2
• B2：命令3-8
• B3：命令9-10
• B4：命令11

4.2 フローグラフ（Flow Graph）

フローグラフは基本ブロックをノードとし、ブロック間の制御フローを辺として表現した有向グラフです。

     B1 (i=1, j=1)
         |
         v
  +---> B2 (t1=10*i, ..., if j<=10 goto B2)
  |      |  \
  |      |   \(j<=10)
  |      |    +---+
  |      |        |
  |      v (j>10) |
  |     B3 (i=i+1, if i<=10 goto B2)
  |      |  \
  |      |   \(i<=10)
  |      +----+
  |
  +--- (後退辺)
         |
         v (i>10)
        B4 (i=1)

辺の種類：

• 順方向辺：B1 -> B2（自然な流れ）
• 条件辺：条件分岐による辺
• 後退辺（back edge）：ループを形成する辺（B2 -> B2、B3 -> B2）

4.3 ループ検出

フローグラフでループを検出することは最適化に非常に重要です。

**自然ループ（Natural Loop）**の定義：

• ループヘッダ（header）ノードdが存在
• 後退辺 n -> d が存在（dがnを支配）
• ループ本体はdを経由せずにnに到達できるすべてのノードとdの集合

ループの重要な性質：

• プログラム実行時間の大部分がループで消費される（90/10法則）
• ループ内部コードの最適化が全体性能に大きな影響

5. 基本ブロックのDAG表現

**DAG（Directed Acyclic Graph）**は基本ブロック内の演算間の関係を表現する効果的な方法です。

5.1 DAG構成

DAGの各ノードは以下を表します：

• リーフ（leaf）：初期値（変数の入力値や定数）
• 内部ノード：演算子とその被演算子を表す子ノード
• 各ノードにはその値を使用する変数名がラベルとして付く

5.2 DAG構成の例

以下の3アドレスコードに対するDAGを構成してみましょう：

a = b + c
b = a - d
c = b + c
d = a - d

DAG構成プロセス：

Step 1: a = b + c
    (+) [a]
   /   \
  b0    c0

Step 2: b = a - d  (aは(+)ノードを参照)
    (+) [a]       (-) [b]
   /   \         /   \
  b0    c0      (+)   d0
                 |
              [aノード]

Step 3: c = b + c  (bは(-)ノード、cはc0)
    (+) [a]       (-) [b]      (+) [c]
   /   \         /   \        /   \
  b0    c0      (+)   d0    (-)    c0
                               [bノード]

Step 4: d = a - d  (同じ演算が既に存在：(-)ノード)
    (-)ノードにdラベルを追加 -> (-) [b, d]

核心的な観察：b = a - dとd = a - dは同じ演算なので、DAGでは一つのノードとして表現されます。これが**共通部分式の除去（Common Subexpression Elimination）**です。

5.3 DAGの活用

DAGを通じて以下を発見できます：

1. 共通部分式：同じ演算が繰り返される場合に一つに統合
2. 不要なコード：結果が使用されない演算の除去
3. 定数畳み込み：被演算子がすべて定数の演算をコンパイル時に計算

// DAG最適化前
t1 = a + b
t2 = a + b    // 共通部分式
t3 = t1 * t2

// DAG最適化後
t1 = a + b
t3 = t1 * t1  // t2の代わりにt1を再利用

5.4 DAGからのコード再生成

DAGから最適化されたコードを再生成する際、ノードの評価順序によって必要なレジスタ数が変わります。

// DAG構造：
//       (*)
//      /   \
//    (+)   (-)
//   / \   / \
//  a   b c   d

// 順序1：左を先に
R1 = a + b   // (+)の結果をR1に
R2 = c - d   // (-)の結果をR2に
R1 = R1 * R2 // 最終結果

// 順序2：右を先に
R1 = c - d   // (-)の結果をR1に
R2 = a + b   // (+)の結果をR2に
R1 = R2 * R1 // 最終結果

どちらの順序も2つのレジスタが必要ですが、複雑なDAGでは順序によって必要なレジスタ数に大きな差が出ることがあります。

6. コード生成器の入力と出力

6.1 入力：中間表現

コード生成器は様々な形態の中間表現を入力として受け取ることができます：

• 3アドレスコード（Three-Address Code）：x = y op z 形式
• 抽象構文木（AST）：プログラムの構造をツリーで表現
• 線形IR：仮想マシンの命令形式

6.2 出力：目的コード

コード生成器の出力は以下のいずれかです：

• 絶対機械コード：固定されたメモリ位置にロードされるコード
• 再配置可能機械コード：リンカによって結合されるオブジェクトコード
• アセンブリコード：アセンブラをもう一度通すコード

ほとんどの実用的なコンパイラは再配置可能機械コードを生成します。

まとめ

コード生成はコンパイラの最終段階として、先行するすべての分析と最適化の結果を実際に実行可能なコードに変換します。基本ブロックとフローグラフはコード生成と最適化の基本単位となり、DAG表現は基本ブロックレベルでの局所最適化を可能にします。次の記事では、具体的なコード生成アルゴリズムとレジスタ割り当て技法を見ていきます。