- Authors
- Name
- Youngju Kim
- @fjvbn20031
中間コード生成 - 3番地コードと型検査
中間コード生成は構文木を機械独立的な**中間表現（Intermediate Representation, IR）**に変換する段階です。この記事では主要なIR形式と型検査、制御フロー翻訳を扱います。
1. 構文木の変形
抽象構文木（AST）
ASTは構文木から不要なノードを除去した簡潔な表現です。
// a + a * (b - c) + (b - c) * d
AST:
+
/ \
+ *
/ \ / \
a * - d
/ \ / \
a - b c
/ \
b c
有向非循環グラフ（DAG）
DAGはASTで**共通部分式（common subexpression）**を共有します。
// a + a * (b - c) + (b - c) * d
DAG:
+
/ \
+ *
/ \ / \
a * | d
/ \|
a - <- (b-c)を1回だけ表現
/ \
b c
DAGの利点は以下の通りです。
- 共通部分式の自動検出: 同じ演算を共有して重複計算を防止します。
- メモリ節約: 同一のノードを再利用します。
DAG構成アルゴリズム
Node createNode(String op, Node left, Node right) {
// 同じ演算と子を持つノードが既に存在するか確認
Node existing = lookup(op, left, right);
if (existing != null) {
return existing; // 既存ノードを再利用
}
Node node = new Node(op, left, right);
insert(op, left, right, node); // ハッシュテーブルに登録
return node;
}
2. 3番地コード（Three-Address Code）
3番地コードは最も広く使用される中間表現形式です。各命令には最大1つの演算子と最大3つのアドレス（オペランドと結果）があります。
3番地コードの形式
基本形式: x = y op z
主な命令の種類:
x = y op z // 二項演算
x = op y // 単項演算
x = y // コピー
goto L // 無条件分岐
if x relop y goto L // 条件分岐
param x // パラメータ渡し
call p, n // 関数呼び出し (p: 関数, n: 引数の数)
return y // 関数戻り
x = y[i] // 配列アクセス（インデックス）
x[i] = y // 配列代入
x = &y // アドレス
x = *y // 間接参照
*x = y // 間接代入
例: 式の3番地コード変換
// 元のコード
a = b * -c + b * -c
// 3番地コード（ASTベース）
t1 = minus c
t2 = b * t1
t3 = minus c
t4 = b * t3
t5 = t2 + t4
a = t5
// 3番地コード（DAGベース - 最適化）
t1 = minus c
t2 = b * t1
t5 = t2 + t2
a = t5
3. 3番地コードの実装方式
クォドラプル（Quadruples）
4つのフィールドで構成: (op, arg1, arg2, result)
番号 | op | arg1 | arg2 | result
----+-------+------+------+-------
0 | minus | c | | t1
1 | * | b | t1 | t2
2 | minus | c | | t3
3 | * | b | t3 | t4
4 | + | t2 | t4 | t5
5 | = | t5 | | a
トリプル（Triples）
resultフィールドを除去し、命令番号で結果を参照します。
番号 | op | arg1 | arg2
----+-------+------+------
0 | minus | c |
1 | * | b | (0)
2 | minus | c |
3 | * | b | (2)
4 | + | (1) | (3)
5 | = | a | (4)
トリプルはメモリを節約しますが、命令移動時に参照の更新が必要です。
間接トリプル（Indirect Triples）
トリプルへのポインタリストを別途維持し、命令順序の変更を容易にします。
順序リスト: [0, 1, 2, 3, 4, 5]
命令の再配置: [2, 0, 3, 1, 4, 5] // 元のトリプルの修正不要
4. 静的単一代入（SSA）形式
SSA（Static Single Assignment）形式では各変数が正確に1回だけ定義されます。
// 通常の3番地コード
p = a + b
q = p - c
p = q * d // pが2回定義される
e = p + q
// SSA形式
p1 = a + b
q1 = p1 - c
p2 = q1 * d // 新しい名前p2
e1 = p2 + q1
Phi関数
制御フローが合流する地点でphi関数を使用します。
// 元のコード
if (flag) x = 1; else x = 2;
y = x;
// SSA形式
if (flag) x1 = 1; else x2 = 2;
x3 = phi(x1, x2); // どの経路から来たかによって選択
y1 = x3;
SSAの利点
- データフロー分析が単純になります: 各変数の定義が一意です。
- 最適化が容易になります: 定数伝播、デッドコード除去などが直感的になります。
- **現代のコンパイラ（LLVM、GCC）**でコアIRとして使用されています。
5. 型表現式（Type Expression）
型システムの型を表現する方法です。
基本型
boolean, char, integer, float, void
型コンストラクタ
1. 配列: array(サイズ, 要素型)
int a[10] -> array(10, integer)
2. レコード/構造体: record(フィールドリスト)
struct { int x; float y; }
-> record((x, integer), (y, float))
3. ポインタ: pointer(型)
int *p -> pointer(integer)
4. 関数: 引数型 -> 戻り値型
int f(float, char) -> float x char -> integer
型同値（Type Equivalence）
2つの同値基準があります。
構造的同値（Structural Equivalence）:
- 2つの型の構造が同じなら同値
- C言語の基本的なアプローチ
名前同値（Name Equivalence）:
- 同じ名前の場合のみ同値
- Pascal、Adaのアプローチ
例:
type A = array(10, integer)
type B = array(10, integer)
構造的同値: A == B （構造が同じ）
名前同値: A != B （名前が異なる）
6. 型検査（Type Checking）
型検査規則のSDD
E -> num { E.type = integer }
E -> num . num { E.type = float }
E -> id { E.type = lookup(id.entry) }
E -> E1 + E2 { E.type = max(E1.type, E2.type)
if compatible(E1.type, E2.type)
else type_error }
E -> E1 [ E2 ] { E.type = if E1.type == array(s, t)
and E2.type == integer
then t
else type_error }
型変換（Type Coercion）
型が異なるオペランドを自動的に変換します。
型変換の階層（自動拡大変換）:
char -> int -> long -> float -> double
例: int + float -> float + float -> float
変換規則（widening）:
E -> E1 + E2
if E1.type == integer and E2.type == integer:
E.type = integer
else if E1.type == float and E2.type == integer:
t = new Temp()
emit(t "=" "intToFloat" E2.addr)
E.type = float
else if E1.type == integer and E2.type == float:
t = new Temp()
emit(t "=" "intToFloat" E1.addr)
E.type = float
7. 制御フローの翻訳
If-Else文の翻訳
// ソースコード
if (x < 100) {
x = x + 1;
} else {
x = x - 1;
}
// 3番地コード
if x < 100 goto L1
goto L2
L1: t1 = x + 1
x = t1
goto L3
L2: t2 = x - 1
x = t2
L3: ...
While文の翻訳
// ソースコード
while (x < 100) {
x = x * 2;
}
// 3番地コード
L1: if x < 100 goto L2
goto L3
L2: t1 = x * 2
x = t1
goto L1
L3: ...
8. ブール式の翻訳
短絡評価（Short-Circuit Evaluation）
ほとんどの言語ではブール式に短絡評価を使用します。
// a < b || c < d && e < f
翻訳:
if a < b goto Ltrue
if c < d goto L1
goto Lfalse
L1: if e < f goto Ltrue
goto Lfalse
a < b が真なら残りは評価しません。
ブール式のSDD
B -> B1 || B2
B1.true = B.true
B1.false = newLabel()
B2.true = B.true
B2.false = B.false
B.code = B1.code || label(B1.false) || B2.code
B -> B1 && B2
B1.true = newLabel()
B1.false = B.false
B2.true = B.true
B2.false = B.false
B.code = B1.code || label(B1.true) || B2.code
B -> ! B1
B1.true = B.false
B1.false = B.true
B.code = B1.code
B -> E1 relop E2
B.code = gen("if" E1.addr relop E2.addr "goto" B.true)
|| gen("goto" B.false)
B -> true
B.code = gen("goto" B.true)
B -> false
B.code = gen("goto" B.false)
9. バックパッチ（Backpatching）
バックパッチは分岐先ラベルがまだ決定されていない時に、後で埋め込む技法です。
バックパッチの核心アイデア
1. 分岐命令を生成する時にターゲットアドレスを空けておく
2. ターゲットが決定したら空けておいたアドレスを埋める（backpatch）
例:
100: if x < y goto ___ <- ターゲット未定
101: goto ___ <- ターゲット未定
...
105: x = x + 1 <- ここがターゲットと判明
バックパッチ後:
100: if x < y goto 105 <- 埋め込み
101: goto ___ <- まだ未定
バックパッチで使用する関数
makelist(i): 命令番号iのみを含むリストを生成
merge(p1, p2): 2つのリストp1、p2を統合
backpatch(p, i): リストpの全命令のターゲットアドレスをiに設定
バックパッチを使用したブール式の翻訳
B -> B1 || M B2
backpatch(B1.falselist, M.quad)
B.truelist = merge(B1.truelist, B2.truelist)
B.falselist = B2.falselist
B -> B1 && M B2
backpatch(B1.truelist, M.quad)
B.truelist = B2.truelist
B.falselist = merge(B1.falselist, B2.falselist)
B -> ! B1
B.truelist = B1.falselist
B.falselist = B1.truelist
M -> epsilon
M.quad = nextquad (現在の命令番号を記録)
バックパッチの例
// a < b || c < d && e < f
生成過程:
100: if a < b goto ___ (B1.truelist = {100})
101: goto ___ (B1.falselist = {101})
102: if c < d goto ___ (B2.truelist = {102})
103: goto ___ (B2.falselist = {103})
104: if e < f goto ___ (B3.truelist = {104})
105: goto ___ (B3.falselist = {105})
バックパッチ結果:
100: if a < b goto Ltrue (truelist)
101: goto 102 (B1.false -> B2開始)
102: if c < d goto 104 (B2.true -> B3開始)
103: goto Lfalse (falselist)
104: if e < f goto Ltrue (truelist)
105: goto Lfalse (falselist)
最終truelist = {100, 104}
最終falselist = {103, 105}
10. Switch文の翻訳
// ソースコード
switch (x) {
case 1: stmt1; break;
case 5: stmt2; break;
default: stmt3;
}
// 3番地コード
t = x
if t == 1 goto L1
if t == 5 goto L2
goto L3 // default
L1: (stmt1のコード)
goto Lnext
L2: (stmt2のコード)
goto Lnext
L3: (stmt3のコード)
goto Lnext
Lnext: ...
caseが多い場合はジャンプテーブル（jump table）や二分探索で最適化します。
まとめ
| 概念 | 核心内容 |
|---|---|
| DAG | ASTから共通部分式を共有するグラフ |
| 3番地コード | 命令あたり演算子1つ、アドレス最大3つ |
| クォドラプル | (op, arg1, arg2, result) 形式 |
| トリプル | 結果を命令番号で参照 |
| SSA | 各変数が正確に1回だけ定義される形式 |
| 型検査 | 演算子とオペランドの型の互換性検証 |
| 短絡評価 | ブール式の部分評価 |
| バックパッチ | 分岐先を後から埋め込む技法 |
中間コード生成はソース言語の意味を機械独立的な形式で表現する核心段階です。次の記事ではプログラムが実行される環境である実行時環境を扱います。