コンパイラ

目次

• 概要
• コンパイラとは何か
• 全体パイプライン
• 字句解析
• 構文解析
• 抽象構文木AST
• 意味解析と型検査
• シンボルテーブルとスコープ
• 中間表現IR
• 代表的IRの比較
• 最適化
• 制御フローグラフとSSA
• コード生成
• レジスタ割付
• 関数呼び出しとABI
• 実行時システム
• JITとインタプリタ
• エラーメッセージと開発体験
• 現代のコンパイラ実装
• 実務ケーススタディ
• ミニ実装で流れを通す
• 8-A. LLVM の内部詳細
• 8-B. GCC vs LLVM
• 8-C. パターンマッチングコンパイラの実装
• 8-D. エラーメッセージの生成
• 8-E. 型推論と型チェック
• 8-F. アセンブリ生成の例
• まとめ
• 参考文献

概要

字句解析・構文解析・最適化・コード生成をつなげて理解する

コンパイラは、プログラミング言語で書かれたコードを、コンピュータが実行しやすい形へ変換する仕組みです。ソースコード -> トークン -> 構文木 -> 中間表現 -> 最適化 -> 機械語 という流れを、理論と実装の両面からつなげて理解します。

この章で重視すること

• コンパイラを「難しい黒魔術」ではなく、段階的な変換器として捉える
• 字句解析、構文解析、意味解析の役割差をはっきり分ける
• IR(中間表現)を中心に最適化とコード生成を理解する
• CPU、メモリ、レジスタ、ABIとのつながりを意識する
• Rust、Go、Java、C/C++、JavaScriptエンジンなど現代実装への橋をかける

コンパイラとは何か

コンパイラは、ある言語で書かれたプログラムを、別の表現へ変換するプログラムです。

一番典型的なのは、

• 入力: C、Rust、Goなどの高級言語
• 出力: アセンブリ、機械語、バイトコード、中間表現

という変換です。

コンパイラとインタプリタの違い

• コンパイラ: まとめて別表現へ変換してから実行する
• インタプリタ: 読みながらその場で解釈して実行する

ただし現代では、この境界はかなり混ざっています。

• Java: バイトコードへコンパイルしてJVMが実行
• JavaScript: まず解釈し、必要に応じてJIT
• Python: バイトコード化してVMが実行

なので「コンパイルするか、しないか」より、どの段階でどこまで前処理するか と見る方が実態に近いです。

なぜコンパイラを学ぶのか

コンパイラを学ぶと、次の疑問がつながります。

• 型エラーはどの段階で見つかるのか
• 最適化はなぜ安全に行えるのか
• 変数は最終的にどこへ置かれるのか
• 関数呼び出しはCPUでどう見えるのか
• GCや例外処理はどこまで言語処理系の責任なのか

これは programming languages、algorithms、cpu、memory、os を結びつける中心線です。

コンパイラを「翻訳機」だけで終わらせない見方

コンパイラを単なる翻訳機だと思うと、

• 入力を別の言語へ置き換えるだけ

に見えます。しかし実際には、

• 意味を保つ
• 誤りを早く見つける
• 実行機械に合わせて形を整える
• 速く、安全に、デバッグしやすくする

という複数の目的を同時に満たす必要があります。

つまりコンパイラは、

• 言語の意味論を実装する装置
• 最適化のための解析基盤
• CPUとOSへ接続する橋
• 開発者体験の一部

でもあります。

どこまでを「コンパイラ」と呼ぶか

文脈によって、compiler が指す範囲は少し違います。

• 狭義: フロントエンド + 最適化 + コード生成
• 広義: これに加えてプリプロセッサ、リンカ、ランタイム、標準ライブラリ、デバッガ情報生成まで含む

実務では、特にビルドエラーや性能問題を追うとき、コンパイラ本体だけ見ても足りないことが多いです。オブジェクトファイル生成後のリンクや、ランタイムの初期化コードまで含めて考える必要があります。

全体パイプライン

コンパイラ全体は、だいたい次の流れで動きます。

大まかに何をしているか

フロントエンド・ミドルエンド・バックエンド

コンパイラは大きく3層に分けて考えると整理しやすいです。

• フロントエンド: 言語依存の処理が多い
• ミドルエンド: 言語にもCPUにも寄りすぎない共通最適化層
• バックエンド: ターゲットCPUや実行環境への適応

LLVMが広く使われるのは、この分離がかなりきれいだからです。

1つの例を最後まで追う

たとえば次のコードを考えます。

int f(int a, int b) {
  int x = a + b;
  return x * 2;
}

各段階での見え方はおおむね次のように変わります。

これを頭に置いて各章を読むと、各技法が「どの表現に対して効くのか」が見えやすくなります。

字句解析

字句解析は、ソースコードという文字列を、意味のある最小単位へ切り分ける段階です。

たとえば

sum = a + 42;

は、次のようなトークン列になります。

• IDENT(sum)
• ASSIGN(=)
• IDENT(a)
• PLUS(+)
• INT(42)
• SEMICOLON(;)

字句解析器が見るもの

• 空白
• 改行
• コメント
• 識別子
• キーワード
• 数値リテラル
• 文字列リテラル
• 演算子
• 区切り記号

なぜ字句解析を分けるのか

字句解析を独立させると、

• 構文解析器は「文字」ではなく「単語」を相手にできる
• コメントや空白処理を前段で片付けられる
• エラー位置を整理しやすい

という利点があります。

正規表現と有限オートマトン

字句解析は、理論的には 正規表現 と 有限オートマトン に強く結びつきます。

• 識別子: [a-zA-Z_][a-zA-Z0-9_]*
• 整数: [0-9]+

のような規則をまとめて、状態機械として高速に走らせます。

この理論背景をもう少し丁寧に追うなら、計算と言語の理論 の 正規表現、有限オートマトン、DFAとNFA が対応します。

実装上の論点

• 最長一致: どこまでを1トークンとするか
• キーワード判定: if は識別子ではなく予約語
• 位置情報: 行・列・ファイル名を持つ
• エラー回復: 不正文字が出ても全体を壊しすぎない

コメントと文字列リテラルは意外に難しい

字句解析は単純そうに見えて、実際には例外が多いです。

• 文字列中の \"
• 改行をまたぐ文字列
• ネストするコメント
• raw string
• Unicode識別子

などは、単純な「正規表現だけ」で片付けにくいことがあります。

たとえばRustやC++ のraw stringは、" を途中で見てもすぐ終端だと決められません。GoやPythonでも、通常文字列とraw stringで字句規則が違います。

プリプロセッサが前にいる言語

C/C++ 系では、字句解析の前後に近い位置で プリプロセッサ が強く関わります。

• #include
• #define
• 条件付きコンパイル

が入ると、見た目のソースと、コンパイラが本当に読む入力がずれます。これがC/C++ 系のエラーメッセージやデバッグを難しくする大きな理由の1つです。

字句解析器の典型実装

• 手書きのscanner
• lex / flex
• 状態機械を自動生成するジェネレータ
• parser combinator系と組み合わせた実装

教育用には手書きが分かりやすく、産業実装では生成器や高度な手書き最適化が混ざることが多いです。

構文解析

構文解析は、トークン列が言語の文法に従っているかを確認し、その構造を木として組み立てる段階です。

例

1 + 2 * 3

をどう解釈するかは、文法と優先順位に依存します。

通常は

1 + (2 * 3)

として読みます。

構文木の直感

これは「先に掛け算がまとまり、その結果に足し算する」構造を表しています。

文法

たとえば式を簡略化すると、次のような文法で書けます。

Expr   -> Expr "+" Term | Term
Term   -> Term "*" Factor | Factor
Factor -> NUMBER | "(" Expr ")"

この文法の見方や、CFGがなぜ入れ子構造に向くのかは、計算と言語の理論 の 文脈自由文法CFG をあわせて読むと理解しやすいです。

LLとLR

構文解析には大きく次の流儀があります。

• LL系: 上から降りるように読む
• LR系: 下から畳み上げるように読む

大まかにいうと、

• LL: 人間が読みやすく、再帰下降で書きやすい
• LR: 表現力が高く、複雑な文法も扱いやすい

です。

再帰下降パーサ

小さな言語では、再帰下降パーサが理解しやすいです。

parseExpr:
  left = parseTerm()
  while next token is "+":
    consume "+"
    right = parseTerm()
    left = Add(left, right)
  return left

これは「関数呼び出しの形で文法をそのまま書く」発想です。

再帰下降パーサの最小コード例

Python風にかなり単純化すると、次のような実装になります。

class Parser:
    def __init__(self, tokens):
        self.tokens = tokens
        self.pos = 0

    def peek(self):
        if self.pos < len(self.tokens):
            return self.tokens[self.pos]
        return ("EOF", "")

    def consume(self, kind):
        token = self.peek()
        if token[0] != kind:
            raise SyntaxError(f"expected {kind}, got {token[0]}")
        self.pos += 1
        return token

    def parse_expr(self):
        node = self.parse_term()
        while self.peek()[0] == "PLUS":
            self.consume("PLUS")
            rhs = self.parse_term()
            node = ("Add", node, rhs)
        return node

    def parse_term(self):
        node = self.parse_factor()
        while self.peek()[0] == "STAR":
            self.consume("STAR")
            rhs = self.parse_factor()
            node = ("Mul", node, rhs)
        return node

    def parse_factor(self):
        kind, text = self.peek()
        if kind == "INT":
            self.consume("INT")
            return ("Int", int(text))
        if kind == "LPAREN":
            self.consume("LPAREN")
            node = self.parse_expr()
            self.consume("RPAREN")
            return node
        raise SyntaxError(f"unexpected token: {kind}")

この実装では、

• parse_expr が + の層
• parse_term が * の層
• parse_factor が最小単位

を担当しています。つまり、優先順位を関数分割で表しているわけです。

この方法の強みと弱み

• 強み: 小さな言語では読みやすく、AST生成と相性がよい
• 弱み: 演算子が多い言語では層が増えやすく、構文拡張が少し重い

そのため、式が複雑な言語ではPratt parserやparser generatorの方が扱いやすいことがあります。

左再帰と優先順位

構文解析で最初につまずきやすいのが 左再帰 と 優先順位 です。

たとえば

Expr -> Expr "+" Term | Term

は文法として自然ですが、単純な再帰下降では無限再帰しやすいです。そこで、

• 文法を右再帰や反復形へ書き換える

この「文法として自然」と「パーサとして扱いやすい」がずれる感覚は、形式言語理論と実装論の交点です。

• 優先順位ごとに関数を分ける
• Pratt parserを使う

といった工夫をします。

Pratt parserの直感

Pratt parserは、演算子ごとに結合の強さを持たせて式を読む方法です。

• * は + より強い
• = は右結合
• 関数呼び出しや添字アクセスは非常に強い

という規則をテーブルとして持てるので、式言語の実装で扱いやすいです。

曖昧な文法

有名な例として dangling else があります。

if a
  if b
    x();
  else
    y();

この else がどの if に対応するかを、文法や構文解析器の規則で決めなければなりません。

つまり構文解析は、単に木を作るだけでなく、曖昧さをどう潰すか の設計でもあります。

エラー回復

パーサが1箇所で壊れたときに、そこで完全停止するとIDEやエディタ支援がかなり弱くなります。

そのため実装では、

• ある区切り記号まで読み飛ばす
• 仮のノードを挿入する
• 推測可能な ; や ) を補う

などの方法で解析を続行することがあります。

これは「正しさ」より「開発体験」を重視した設計です。

抽象構文木AST

AST(Abstract Syntax Tree)は、プログラムの意味上重要な構造だけを残した木です。

構文木とASTの違い

• 具象構文木: 文法記号や括弧など、書き方に近い情報も多く持つ
• AST: 実行意味に必要な構造を中心に持つ

たとえば

(1 + 2)

の外側の括弧は、優先順位が確定した後はASTでは省けることがあります。

ASTが重要な理由

ASTがあると、

• 型検査しやすい
• 変数名解決しやすい
• 最適化前の意味構造を保ちやすい
• エラーメッセージの位置づけがしやすい

左は文法規則の形を多く残し、右は意味計算に必要な構造だけを残しています。ASTが後続処理で好まれるのは、この「文法ノイズの少なさ」が大きいです。

ASTノードの典型例

ASTには、たとえば次のようなノードがあります。

• Literal
• BinaryExpr
• UnaryExpr
• CallExpr
• IfExpr / IfStmt
• WhileStmt
• Block
• FunctionDecl
• ReturnStmt

この設計は、その後の型検査やコード生成のしやすさに直結します。

「文」と「式」の違い

言語によっては、

• if が文だけのこともある
• if 自体が値を返す式のこともある

など、ASTの設計に大きく影響する差があります。

RustやML系では「式としての if」が強く、C系では「文としての if」の感覚が強いです。ここは言語設計とコンパイラ設計が直接つながるポイントです。

ASTの段階で糖衣構文をほどくか

現代言語は、for-each、pattern matching、destructuring、async/awaitのような糖衣構文を多く持ちます。

コンパイラはどこかで、

• 糖衣構文を高水準のまま持つ
• 途中でより原始的な形へdesugarする

という選択をします。

この判断は、エラーメッセージ品質と最適化しやすさの両方に影響します。

という利点があります。

意味解析と型検査

構文が正しくても、意味が正しいとは限りません。

1 + true

は、字句解析も構文解析も通るかもしれませんが、型の意味としてはおかしいかもしれません。

意味解析でやること

• 名前解決
• スコープ確認
• 型検査
• 代入可能性の確認
• 関数呼び出し引数の検証
• break や return の文脈確認

型検査の直感

型検査は、「この構造の各ノードに型を伝搬させて矛盾がないかを見る」作業と考えると分かりやすいです。

型そのものを 言語設計の軸 として眺めたいときは、プログラミング言語 の 型とは何か、静的型付けと動的型付け、型推論と多相性 をあわせて読むと整理しやすいです。

静的型付けと動的型付け

• 静的型付け: 実行前に多くを検査する
• 動的型付け: 実行時に型を持ち回る

静的型付け言語でも、ジェネリクスや推論、トレイト制約などで内部はかなり複雑です。

名前解決と型検査は別問題

初心者が混同しやすいですが、

• x が何を指すか
• x の型が何か

は別問題です。

たとえば

let x = foo(bar);

では、まず

• foo という名前がどの関数か
• bar という名前がどの束縛か

を見つける必要があります。その後で、

• bar の型は何か
• foo はその型を受け取れるか
• 戻り値は x に代入できるか

を確認します。

型推論

型推論は「型を書かなくてよい魔法」ではなく、制約解決の一種です。

let x = 1
let y = x + 2

なら、

• 1 は整数
• + は両辺が同じ数値型

といった制約から x と y の型を決めます。

Hindley-Milner系ではかなり強い推論ができますが、サブタイピングやトレイト制約、所有権まで入ると一気に難しくなります。

型検査で出る現代的な論点

• nullability
• 所有権と借用
• effect system
• generic specialization
• trait resolution
• lifetime inference

ここまで入ると、意味解析は「型の確認」以上に、言語ルール全体の実装 に近くなります。

このあたりの論点は、言語利用者の立場では プログラミング言語 の 所有権と借用、並行性とメモリモデル、関数型プログラミング と対応しています。

シンボルテーブルとスコープ

シンボルテーブルは、「この名前は何者か」を管理する表です。

典型的に入る情報

• 名前
• 種類
  • 変数
  • 関数
  • 型
  • モジュール
• 型
• 宣言位置
• スコープ
• メモリ上の属性

スコープの直感

内側のスコープで同じ名前を再定義すると、外側を隠すことがあります。これを shadowing と呼びます。

実装の雰囲気

• スコープ突入時に新しい表を積む
• スコープ離脱時に表を捨てる
• 名前解決時は内側から外側へ探す

これはOSのスタックフレームやブロックスコープの直感ともつながります。

スコープと束縛のよくある落とし穴

• 同名変数のshadowing
• クロージャが外側変数を捕まえるcapture
• 前方参照を許すか
• モジュール境界をまたぐ公開 / 非公開

たとえばクロージャでは、「どの変数を値で捕まえるか、参照で捕まえるか」が後のコード生成やランタイム表現にも効いてきます。

シンボルテーブルのデータ構造

実装では次のような形が多いです。

• ハッシュテーブル + スコープスタック
• 永続マップ
• ネストしたenvironment構造

IDEやインクリメンタルコンパイラでは、再解析コストを下げるために、単純な一時表よりもう少し永続的な表現が好まれます。

中間表現IR

IR(Intermediate Representation)は、ASTと機械語の中間に置く表現です。

なぜIRが必要か

直接

• ASTから機械語

へ行くと、最適化も移植性もつらくなります。

IRを挟むと、

• フロントエンドと言語依存部分を分離できる
• 最適化を共通化できる
• バックエンドをCPUごとに切り替えやすい

ようになります。

三番地コードの直感

t1 = b * c
t2 = a + t1
return t2

これは複雑な式を、小さな1命令ずつにほどいた形です。

ASTとIRの違い

現代のIR

• LLVM IR
• GCC GIMPLE
• Rust MIR
• JVM bytecode
• WebAssembly

同じ「IR」でも、かなり高水準なものからかなり低水準なものまであります。

IRは1種類とは限らない

実装によっては、IRは複数段あります。

• 高水準IR: 言語構造をまだ多く残す
• 中水準IR: 最適化しやすい命令列にする
• 低水準IR: 機械語に近づける

RustのHIR / THIR / MIRのように複数段階へ分ける実装は珍しくありません。

IRに落とすと何が嬉しいか

たとえば for ループや match 式は、言語表面では便利ですが、そのままだと最適化しにくいことがあります。

IRに落とすと、

• 分岐
• ジャンプ
• load/store
• 単純な算術命令

のような少数の部品に揃えられるので、解析がしやすくなります。

例: ASTからIRへ

if (x < 0) {
  y = -x;
} else {
  y = x;
}
return y;

は、IRではおおむね次のような形になります。

if x < 0 goto L1
goto L2
L1:
  y1 = neg x
  goto L3
L2:
  y2 = x
  goto L3
L3:
  y3 = phi(y1, y2)
  return y3

こうすると、分岐と合流が明示され、SSAやCFGと自然につながります。

1つの式を最後まで追う

もう少し小さな例として、次の式を考えます。

result = (a + 2) * (b + 2)

ソースコード段階

人間には、+ が2回あり、その結果どうしを * している式に見えます。

AST段階

この段階では、構造はよく見えますが、まだ機械に近くはありません。

三番地コード段階

t1 = a + 2
t2 = b + 2
t3 = t1 * t2
result = t3

ここまで来ると、各演算がかなり単純になり、最適化しやすくなります。

最適化の可能性

もし 2 が何度も出てきても、それだけで共通部分式除去されるわけではありません。a + 2 と b + 2 は別式だからです。

一方で、

t1 = a + 2
t2 = a + 2
t3 = t1 * t2

のような形なら、a + 2 を1回で済ませられるかもしれません。

機械語近傍

最終的には、

• a をレジスタへ読む
• 即値 2 を足す
• b についても同じことをする
• 2つのレジスタを掛ける
• 結果を書き戻す

という、かなりCPU寄りの操作列になります。

このように、意味は保ったまま、表現だけがだんだん機械に寄っていく のがコンパイラの本質です。

代表的IRの比較

IRと一口に言っても、設計思想はかなり違います。

LLVM IR

• SSAベース
• 型付き
• 低水準寄りだが、まだ機械語ではない
• 最適化基盤として非常に強い

たとえばメモリload/storeや分岐、呼び出しが明示されるので、CPUに近い見方へ寄せやすいです。

Rust MIR

• Rust固有の意味解析結果をかなり反映する
• borrow checkやmoveの考え方とつながりやすい
• LLVM IRより高水準

MIRは「最終的なネイティブ命令に近い」というより、Rustの意味論を整理して扱う中間段階 と考える方が近いです。

JVM bytecode

• 仮想機械向け
• スタックマシン型
• CPU命令というよりJVM実行モデルに最適化されている

JVM bytecodeは「すぐハードウェアへ落とすためのIR」ではなく、「JVMが安全に、移植性高く実行するための形式」です。

WebAssembly

• 安全性と移植性を強く意識
• スタックマシンに近い
• ブラウザやサンドボックス環境との相性がよい

4つを並べると

レジスタマシン型とスタックマシン型

IRには大まかに、

• レジスタマシン型
• スタックマシン型

があります。

レジスタマシン型

t1 = a + b
t2 = t1 * c

依存関係が見やすく、最適化しやすい反面、名前管理は増えます。

スタックマシン型

push a
push b
add
push c
mul

命令列は素直ですが、値の流れは暗黙的になりやすいです。

JVMやWasmは後者に近く、LLVMは前者に近いです。

同じ式を3種類のIRで見る

たとえば

return (a + b) * c

のような式は、IRによってかなり見え方が変わります。

LLVM IR風

%t1 = add i32 %a, %b
%t2 = mul i32 %t1, %c
ret i32 %t2

依存関係が明示され、値がどこから来たかを追いやすい形です。

Rust MIR風

_1 = Add(copy _2, copy _3)
_0 = Mul(move _1, copy _4)
return

ここではmove/copyの区別が見えやすく、Rustの所有権モデルに近い視点が入ります。

JVM bytecode風

iload_1
iload_2
iadd
iload_3
imul
ireturn

中間値がスタック上に暗黙的に積まれていくので、命令列は短い一方で、データ依存は少し見えにくくなります。

比較すると何が分かるか

• LLVM IR: 最適化しやすい
• MIR: 言語意味に近い
• JVM bytecode: VM実行や検証に向く

つまりIRは、優劣というより 何を大事にした設計か が違います。

最適化

最適化は、「意味を変えずに実行を良くする」変換です。

よくある最適化

• 定数畳み込み
• 定数伝播
• 共通部分式除去
• デッドコード削除
• ループ不変式の外出し
• インライン展開
• 強度削減

定数畳み込み

2 * 3 + x

を

6 + x

にするような変換です。

デッドコード削除

結果がどこからも使われない計算を消します。

なぜ難しいのか

最適化は「速そう」では足りません。

• 例外の有無
• 副作用
• メモリ別名
• 浮動小数点の丸め
• 並行実行の可視性

を壊さない必要があります。

最適化は「全部やればいい」わけではない

最適化にはコストがあります。

• コンパイル時間が伸びる
• デバッグしにくくなる
• コードサイズが増えることがある
• CPUによって有利不利が違う

そのため実際のコンパイラは、-O0, -O1, -O2, -O3, -Os のように最適化段階を分けます。

代表的な最適化をもう少し具体的に見る

定数伝播

x = 10
y = x + 1

なら y = 11 とできるかもしれません。

共通部分式除去

t1 = a * b
t2 = a * b + 1

なら2回目の a * b を使い回せるかもしれません。

ループ不変式の外出し

for i in 0..n:
  x = a * b
  use(x, i)

で a * b がループ中に変わらないなら、外へ出せます。

強度削減

x * 8

をシフトへ変えるような発想です。ただし現代CPUでは、必ずしも単純なシフトの方が良いとは限らず、ターゲット依存の判断もあります。

最適化の安全性を何で支えるか

最適化は、解析に裏打ちされて初めて安全にできます。

• 到達可能性解析
• 生存解析
• 別名解析alias analysis
• 範囲解析
• ループ解析

つまり最適化は、派手な書き換え技法というより、解析 + 変換 の組です。

最適化前後のIRを見比べる

たとえば次のようなIRを考えます。

t1 = 2 * 3
t2 = a + 0
t3 = t1 + t2
t4 = t3
return t4

ここには、

• 2 * 3 は事前計算できる
• a + 0 は a と同じ
• t4 = t3 は単なるコピー

という簡約余地があります。

最適化前

t1 = 2 * 3
t2 = a + 0
t3 = t1 + t2
t4 = t3
return t4

最適化後

t1 = 6
t2 = a
t3 = t1 + t2
return t3

さらにパスを重ねると、

return 6 + a

のような形まで寄せられるかもしれません。

何が起きているか

最適化はこのように、1つの派手な変換 ではなく、小さな変換の積み重ねで効いてきます。

制御フローグラフとSSA

最適化を本格的にやるとき、制御フローグラフCFGが重要になります。

CFG

基本ブロックどうしの遷移をグラフにしたものです。

SSA

SSA(Static Single Assignment)は、「各変数が1回だけ代入される」形へ直した表現です。

x1 = 1
x2 = x1 + 1

のように、同じ変数名を上書きせず、版番号を振ります。

SSAの利点

• データ依存が見えやすい
• 定数伝播しやすい
• デッドコード削除しやすい
• 最適化アルゴリズムを書きやすい

phi関数

分岐合流点では、どちらの経路から来たかで値が違うので phi が使われます。

x3 = phi(x1, x2)

これは「制御経路に応じて適切な版を選ぶ」ためのIR上の仕掛けです。

SSA変換の具体例

次のようなコードを考えます。

x = 0
if cond:
  x = 1
else:
  x = 2
return x

SSA前

x = 0
if cond goto L1
goto L2
L1:
  x = 1
  goto L3
L2:
  x = 2
L3:
  return x

このままだと、最後の x がどの代入由来かを解析で追う必要があります。

SSA後

x1 = 0
if cond goto L1
goto L2
L1:
  x2 = 1
  goto L3
L2:
  x3 = 2
L3:
  x4 = phi(x2, x3)
  return x4

これで return が参照する値は常に x4 だと分かります。phi は「どちらの経路から来たかに応じて値を選ぶ仮想命令」と考えると分かりやすいです。

ループではどう見えるか

phi はループでもよく出ます。

i1 = 0
L1:
  i2 = phi(i1, i3)
  ...
  i3 = i2 + 1
  if i3 < n goto L1

この形だと、「最初の値」と「前回反復の値」が1つの変数系列として整理され、最適化や解析がしやすくなります。

基本ブロック

CFGを扱うときは、まず 基本ブロック を作ります。

基本ブロックとは、

• 途中から飛び込まれない
• 途中で分岐しない

直線的な命令列です。

これを単位にすると、制御フロー解析もデータフロー解析もかなり整理しやすくなります。

SSAが嬉しい本当の理由

SSAが便利なのは、各値の定義元がはっきりするからです。

x = ...
x = ...
x = ...

のように同じ変数が何度も更新される世界では、今のxはどの代入由来か を追うのが大変です。SSAでは版番号があるので、依存関係が見えやすくなります。

SSAは最終出力ではないことが多い

SSAは最適化には非常に向いていますが、実機命令へ落とす直前では、

• phi を消す
• moveを入れる
• 物理レジスタへ割り当てる

といった処理が必要です。つまりSSAは 便利な作業用表現 であり、そのまま機械語になるわけではありません。

コード生成

コード生成は、IRをターゲット命令列へ落とす段階です。

何を決めるのか

• どの命令を使うか
• どの値をどのレジスタへ置くか
• メモリとレジスタをどう使い分けるか
• 分岐や呼び出しをどう表現するか

生成された命令列を具体的なアセンブラとして読みたいときは、アセンブラ がそのまま橋になります。

命令選択

たとえば

t1 = a + b

を、

• ADD r1, r2
• LEA
• 即値命令

などへどう割り当てるかを決めます。

ターゲット依存性

ここから先はCPUごとの差が大きくなります。

• x86-64
• ARM64
• RISC-V
• GPU ISA

で命令セットもcalling conventionも違います。

命令選択で何が起きるか

同じIRでも、ターゲットによって良い命令列は変わります。

たとえば x * 2 + y のような式は、

• 単純な add と shift
• x86の lea
• fused multiply-addに近い形

など、CPUに応じて違う落とし方がありえます。

命令スケジューリング

命令をどの順で並べるかも重要です。

• 依存がある命令は並び替えられない
• loadの待ち時間を別命令で隠したい
• パイプライン競合を減らしたい

といった事情があるからです。

これは CPU のパイプラインや分岐予測とも直接つながります。

デバッグ情報の生成

コード生成は速い命令列を出すだけでは終わりません。

• ソース行番号
• 変数位置
• インライン展開元

などの デバッグ情報 を生成しないと、デバッガでまともに追えません。最適化が強くなるほど、ソースの変数がどこにあるか を保つのは難しくなります。

x86-64とARM64でどう違うか

次のような関数を考えます。

int add3(int a, int b, int c) {
  return a + b + c;
}

x86-64風

System V ABIでは整数引数は典型的に rdi, rsi, rdx などへ入ります。

add3:
  mov eax, edi
  add eax, esi
  add eax, edx
  ret

ARM64風

AArch64では整数引数は w0, w1, w2 などへ入ることが多いです。

add3:
  add w0, w0, w1
  add w0, w0, w2
  ret

比較すると何が分かるか

• 引数レジスタの割当が違う
• 命令記法が違う
• 即値やメモリアドレッシングの制約が違う
• caller-save / callee-saveの細部が違う

つまりコード生成は、IRをそのまま文字列化するのではなく、そのCPUとABIに最も自然な形へ落とす処理 です。

その「自然な形」が実際にどんな命令列へ見えるかは、アセンブラ の 具体的なコード例 や 呼び出し規約ABI をあわせて見ると具体化しやすいです。

レジスタ割付

レジスタは速いですが数が少ないです。どの一時変数をどのレジスタへ置くかがレジスタ割付です。

直感

• レジスタ: 机の上の手元メモ
• メモリ: 離れた棚

机に全部は置けないので、必要に応じて出し入れします。これが spill です。

干渉グラフ

同時に生きている変数は、同じレジスタを共有できません。

その関係をグラフにして彩色問題として近似的に解く考え方があります。

難しさ

• 最適割付は難しい
• spillが増えると性能が大きく落ちる
• calling conventionとも整合を取る必要がある

生存区間live range

ある値が

• 定義されてから
• 最後に使われるまで

の区間を 生存区間 と呼びます。

生存区間どうしが重なると、同じレジスタへは置けません。干渉グラフは、この重なりを可視化したものです。

線形走査linear scan

JITや高速コンパイラでは、彩色ベースより linear scan が好まれることがあります。

• 実装が比較的単純
• 速度が速い
• 品質は少し落ちることがある

というトレードオフです。

つまりレジスタ割付も、「最良」を求めるだけでなく、コンパイル時間とのバランス で選ばれます。

この三角形は、「3つの値が互いに同時に生きるなら、同じレジスタは共有できない」ことを表しています。干渉グラフは、この重なりを視覚化して割付判断を助けます。

関数呼び出しとABI

関数呼び出しは、見た目よりかなり多くの約束に支えられています。

ABIとは

ABI(Application Binary Interface)は、バイナリレベルでの約束です。

• 引数をどこへ置くか
• 戻り値をどこで返すか
• どのレジスタを呼び出し側が保存するか
• スタックをどう使うか

スタックフレーム

この約束があるから、別コンパイラで作ったオブジェクトファイル同士でも連携できます。

スタックフレームを生の命令列として見たいなら、アセンブラ の スタックと関数呼び出し が読みやすい入口です。

caller-saveとcallee-save

ABIではレジスタごとに、

• caller-save: 呼び出し側が必要なら退避
• callee-save: 呼び出される側が壊したら戻す

という約束があります。

この違いは、関数呼び出しが多いコードやレジスタ割付の結果にかなり効きます。

可変長引数や戻り値

ABIは単純な int f(int, int) だけではありません。

• 可変長引数
• 大きな構造体戻り値
• 浮動小数点引数
• ベクトル引数

では別ルールが入ることがあります。CとC++ のFFIやシステムプログラミングでここを誤ると、見た目は正しいのに呼び出しが壊れます。

実行時システム

コンパイルだけでは終わらず、実行時システムruntimeが必要なことも多いです。

代表例

• ガベージコレクション
• 例外処理
• 動的ディスパッチ
• スレッドランタイム
• 標準ライブラリ

どこまでがコンパイラか

ここは境界が曖昧です。

• コンパイラ本体
• リンカ
• ローダ
• ランタイム
• VM

まで含めて処理系として見ると、全体像がつかみやすいです。

ガベージコレクションとの関係

GC言語では、コンパイラはランタイムに多くを委ねます。

• どこにポインタがあるか
• どこがsafepointか
• どのスタック値がルートか

といった情報を、コンパイラが実行時へ渡す必要があります。

つまりGCはランタイム機能ですが、コンパイラ側の協力なしには成立しません。

GCや所有権を 言語機能としてどう比較するか は、プログラミング言語 の メモリ管理 と 所有権と借用 が補助になります。

例外処理との関係

例外処理も同様で、

• どこでunwindできるか
• catch節はどこか
• デストラクタをどう走らせるか

といった情報が必要です。これも「文法だけ分かれば終わり」ではなく、生成コードとランタイムの協調問題です。

JITとインタプリタ

JIT(Just-In-Time compilation)は、実行しながら必要な部分をコンパイルする方式です。

なぜJITを使うのか

• 実行時の型情報や頻度情報を見られる
• ホットパスだけを強く最適化できる
• 動的言語でも高性能化しやすい

典型的な流れ

JITの難しさ

• 起動が重くなる
• メモリ消費が増える
• deoptimizationが必要
• セキュリティ制約が増える

deoptimizationとは何か

JITは「たぶんこの型だろう」「この分岐はあまり来ないだろう」という仮定を置いて速くします。

しかし、その仮定が外れたら元に戻らなければいけません。これが deoptimization です。

つまりJITは、

• 速いコードを作る
• 仮定が外れたら安全に戻す

の両方を持つ必要があります。

プロファイル誘導最適化

JITだけでなくAOTコンパイラでも、

• 実行頻度
• 分岐傾向
• ホットパス

の情報を使って最適化することがあります。これがPGO(Profile-Guided Optimization)です。

コンパイラは「静的なコードだけ見ている」と思われがちですが、実際には実行情報をかなり積極的に使います。

エラーメッセージと開発体験

現代のコンパイラでは、エラーメッセージ品質はとても重要です。

良いエラーの条件

• 位置が正確
• 何が期待されていたか分かる
• 1つ目のエラーで全崩壊しすぎない
• 修正候補がある
• 型の流れが追える

例

• 単に syntax error
• ではなく
• expected ";" after expression

と出る方が圧倒的に助かります。

Rustコンパイラが高く評価される理由の1つもここです。

良い診断は内部表現の質にも依存する

良いエラーは、文面だけ工夫しても出ません。

• ASTに位置情報が正しく残っているか
• 意味解析で制約の由来を追えるか
• 型推論の失敗箇所を局所化できるか

が必要です。

つまり診断品質はUIの問題であると同時に、内部データ構造の設計問題 でもあります。

IDE時代のコンパイラ

現代では、コンパイラは cargo build や gcc のときだけ動くものではありません。

• 補完
• 定義ジャンプ
• リファクタリング
• その場の型表示

のために、エディタ内で断続的に走ります。

そのため、

• 部分的に壊れたコードも扱える
• 再解析を局所化できる
• 速く応答できる

ことが重要になります。

現代のコンパイラ実装

LLVM系

• Clang
• Rustの一部バックエンド
• Swift
• 多くの研究・産業実装

共通IRと最適化基盤を持つのが強みです。

GCC系

• C/C++
• Fortran
• Ada

長い歴史と広いターゲット対応が強みです。

言語ごとの個性

• Go: コンパイル速度とツールチェーン統合を重視
• Rust: 所有権やborrow checkを含む高度な意味解析
• Java HotSpot: VMとJITが中心
• V8: インタプリタ + JIT + deoptの設計が重要

単一パスと多段パス

昔の教育用コンパイラでは、単一パスの実装がよく出ます。しかし現代の言語は、

• ジェネリクス
• マクロ
• trait / interface解決
• borrow check
• 最適化

のように処理が複雑なので、多段パスが一般的です。

インクリメンタルコンパイル

巨大なコードベースでは、毎回フルコンパイルすると重すぎます。

そのため、

• 変更されたモジュールだけ再解析
• 依存関係だけ再型検査
• 再最適化範囲を絞る

といったインクリメンタル処理が重要になります。

Rust、TypeScript、IDE用language serverなどでは特に重要です。

実務ケーススタディ

ケース1: なぜデバッグビルドとリリースビルドで速さが違うのか

主な理由は、

• インライン展開
• デッドコード削除
• ベクトル化
• 境界チェック削減
• 定数伝播

などの最適化が有効になるからです。

ケース2: なぜ小さなコード変更で性能が大きく変わるのか

コンパイラは局所的な変更で

• レジスタ割付
• 分岐形
• インライン判断
• 自動ベクトル化

が変わることがあります。

ソースは少ししか変わらなくても、生成コードはかなり変わりえます。

ケース3: なぜ未定義動作が最適化と相性が悪いのか

C/C++ では未定義動作があると、コンパイラは「その状況は起きない前提」で変換できます。

これは高速化には効きますが、バグがあると想像以上に危険です。

ケース4: なぜ境界チェック削除が効くのか

配列アクセスのたびに境界チェックが入る言語でも、コンパイラが

• ループの範囲
• インデックスの単調性
• 配列長との関係

を証明できれば、チェックを外せることがあります。

これは安全性を捨てた最適化ではなく、安全だと証明できたから消す 最適化です。

ケース5: なぜ同じアルゴリズムでも言語ごとに速さが違うのか

差は単に「言語が速い / 遅い」ではなく、

• 生成コードの品質
• ランタイムコスト
• GCの有無
• bounds check
• inlining
• escape analysis

などの積み重ねで生まれます。

コンパイラを見ると、性能差をもう少し構造的に説明できるようになります。

ミニ実装で流れを通す

ここでは、最小の式言語を例にして、「各段階で何を作るのか」をひとまとまりで見ます。

題材

次のような小さな言語を考えます。

let x = 1 + 2 * 3;
print(x);

1. 字句解析の出力

LET IDENT(x) ASSIGN INT(1) PLUS INT(2) STAR INT(3) SEMI
PRINT LPAREN IDENT(x) RPAREN SEMI

この段階では、まだ 2 * 3 が先だとは決まっていません。単に単語へ分かれただけです。

2. 構文解析の出力

Program
  LetStmt(name=x)
    BinaryExpr(+)
      Int(1)
      BinaryExpr(*)
        Int(2)
        Int(3)
  PrintStmt
    Var(x)

ここで初めて、掛け算が足し算より内側に入る構造が確定します。

3. 意味解析の出力

• x をシンボルテーブルへ登録
• x の型を int と判断
• print(x) で x が有効範囲にあることを確認

この段階で print(y) だったら、「未定義変数 y」のエラーになります。

4. IRの出力

t1 = 2 * 3
t2 = 1 + t1
x = t2
print x

5. 最適化後

x = 7
print x

ここでは 2 * 3 と 1 + 6 を前もって計算できるので、定数畳み込みが効きます。

6. コード生成後のイメージ

mov r1, 7
store x, r1
load r2, x
call print

もちろん実際の命令列はABIやランタイム次第でもっと複雑ですが、流れとしてはこのようになります。

7. 1行ごとに何が起きるか

8. もう少し大きい題材なら何が増えるか

もしこのミニ言語に次を足すと、

• if
• while
• 関数
• 配列

IR側では次の要素が増えます。

• ラベルとジャンプ
• CFG
• phi
• スタックフレーム
• 境界チェック

つまり「小さな言語を通してみる」ことは、そのまま本格的なコンパイラの縮図を見ることでもあります。

この例から分かること

• 字句解析: 文字を単語へ分けるだけ
• 構文解析: どの演算が先かを決める
• 意味解析: 名前や型が正しいかを見る
• IR: 最適化しやすい形へほどく
• 最適化: 事前に計算できるものを消す
• コード生成: 実行機械に合う命令へ変える

この一本道が見えると、各章がバラバラの話ではなくなります。

補足: コンパイラの作り方

ここからは、実際に「小さくても動くコンパイラ」をどう作るかを、かなり具体的に見ます。最初からLLVMや最適化パイプラインへ飛ぶより、外部依存なしの最小実装 -> 必要に応じてライブラリ導入 の順で進む方が理解しやすいです。

最小コンパイラの到達目標

最初の題材としては、次のような言語で十分です。

• let x = 1 + 2 * 3;
• print(x);

ここで目指すのは、

• 字句解析できる
• ASTを作れる
• スタックマシン向け命令列へ落とせる
• その命令列をVMで実行できる

というend-to-endの流れです。

具体的な実装フロー

1. 字句解析器を書く 正規表現で LET, IDENT, INT, PLUS, STAR, SEMI などを切り出す。

2. 再帰下降パーサを書く parse_expr, parse_term, parse_factor を作り、優先順位を表現する。

3. ASTを定義する LetStmt, PrintStmt, Add, Mul, Int, Var くらいで十分。

4. コード生成器を書く ASTをたどって、PUSH_CONST, LOAD, STORE, ADD, MUL, PRINT のような命令列へ落とす。

5. 小さなVMを作る スタックと変数表を持つだけの実行器でよい。

6. 観察用オプションを付ける --emit-tokens, --emit-ast, --emit-ir, --run を用意すると、各段階の出力が見えて学習効果が高い。

まず使うライブラリ

最小実装では、外部ライブラリなし が一番おすすめです。今回のサンプルもPython標準ライブラリだけで動きます。

• re: 字句解析のための正規表現
• argparse: コマンドライン引数
• dataclasses: トークン構造体
• json: ASTの見やすい出力

もう少し実務的にするなら使う候補

実際に動く最小サンプル

このフォルダには、実際に動く最小コンパイラを置いてあります。

• tiny_expr_compiler.py
• tiny_expr_example.toy

このサンプルは、

• let
• print
• +
• *
• 括弧

だけを持つ小さな式言語を、スタックマシン命令列へコンパイルして、そのままVMで実行 します。

使い方

python3 Tech/ComputerScience/scripts/tiny_expr_compiler.py \
  Tech/ComputerScience/scripts/tiny_expr_example.toy \
  --emit-tokens --emit-ast --emit-ir --run

何が出るか

• --emit-tokens: 字句解析結果
• --emit-ast: 構文解析後のAST
• --emit-ir: コンパイル後のスタックマシン命令列
• --run: VM上での実行結果

命令列の見え方

たとえば print((1 + 2) * 3); に近い式なら、IRはおおむね次のようになります。

00: PUSH_CONST 1
01: PUSH_CONST 2
02: ADD
03: PUSH_CONST 3
04: MUL
05: PRINT

これはJVM bytecodeやWebAssemblyに近い、スタックマシン型の最小表現 です。

この最小実装で学べること

• 字句解析と構文解析の責務分離
• ASTからコード生成への木のたどり方
• 変数束縛を STORE / LOAD で表す感覚
• VMを置くと「コンパイル結果が本当に動く」こと

次にどう拡張するか

次の順で育てると自然です。

1. - と / を追加する
2. 比較演算と if を入れる
3. while を入れてジャンプ命令を足す
4. 関数定義と呼び出しを入れる
5. 型検査を足す
6. 定数畳み込みを実装する
7. SSAやregister-based IRに寄せる
8. llvmlite などでLLVM IRへ出す

「簡単なコンパイラ」を作るときの設計判断

最初の1本では、次の割り切りがかなり大事です。

• 最初は 型システムを弱くする
• エラー回復は最小限でよい
• 最適化は後回しでよい
• ターゲットは 疑似アセンブリかVM がよい
• まずは 動くend-to-end を優先する

これを守ると、教材としても実装としても崩れにくいです。

8-A. LLVM の内部詳細

IR の最適化パス

LLVM IR は複数の最適化パスを通ります。

; 最適化前
define i32 @add_one(i32 %x) {
  %1 = add i32 %x, 1
  %2 = add i32 %1, 2
  %3 = add i32 %2, 3
  ret i32 %3
}

; 最適化後（定数畳み込み + 強度削減）
define i32 @add_one(i32 %x) {
  %1 = add i32 %x, 6
  ret i32 %1
}

主要な最適化パス：

• Dead Code Elimination (DCE): 使われないコードを削除
• Constant Folding: 1 + 2 を 3 に畳み込む
• Common Subexpression Elimination (CSE): 同じ計算の重複を除去
• Strength Reduction: x * 2 を x << 1 に変換
• Inlining: 小さい関数を呼び出し元に展開
• Loop Invariant Code Motion (LICM): ループ不変式を外に出す

バックエンド：IR から マシンコード

LLVM IR
  ↓
Instruction Selection（IR を機械語命令に変換）
  ↓
Register Allocation（仮想レジスタを物理レジスタに割当）
  ↓
Instruction Scheduling（命令順序を最適化）
  ↓
Assembly Generation（アセンブリ出力）
  ↓
Machine Code（最終的なマシンコード）

8-B. GCC vs LLVM

8-C. パターンマッチングコンパイラの実装

複数パターンの効率的なマッチング

// C コード：パターンマッチを多数持つ場合
int classify(int x) {
    if (x == 1) return 1;
    if (x == 2) return 2;
    if (x == 3) return 3;
    if (x == 5) return 5;
    if (x == 7) return 7;
    return -1;
}

// コンパイラ最適化後：ジャンプテーブル
int classify(int x) {
    if (x < 1 || x > 7) return -1;
    int table[] = {-1, 1, 2, 3, -1, 5, -1, 7};
    return table[x];
}

Rust の match expression：

match x {
    0..=9 => "digit",
    'a'..='z' => "lowercase",
    'A'..='Z' => "uppercase",
    _ => "other"
}

コンパイラは範囲チェックと分岐を効率的なコードに変換します。

8-D. エラーメッセージの生成

良いコンパイラはエラー位置とコンテキストを示します。

error[E0425]: cannot find value `x` in this scope
  --> src/main.rs:3:5
   |
3 |     println!("{}", x);
   |                    ^ not found in this scope
   |
   = note: consider checking if this variable is bound in the current function

Rust は特に詳細なエラーを出すことで知られています。

8-E. 型推論と型チェック

Hindley-Milner 型推論

--型注釈なし
add x y = x + y

-- コンパイラが推論
-- add : Int -> Int -> Int
-- or
-- add : Float -> Float -> Float

Union-Find による型統一

タイプ変数 t1, t2, t3 があり：
  t1 = Int
  t2 = t1  -> t3 が与えられたとき
  
Union-Find で：
  t2 = Int（t1 の値を継承）
  t3 は未解決（関数型で制約）

8-F. アセンブリ生成の例

x86-64 ターゲット：

int add(int a, int b) {
    return a + b;
}

コンパイル後：

add:
    mov eax, edi        ; eax = a（第1引数）
    add eax, esi        ; eax += b（第2引数）
    ret                 ; 戻り値をeax で返す

ARM ターゲット：

add:
    add r0, r0, r1      ; r0 = a + b
    bx lr               ; 戻る

まとめ

コンパイラは、ソースコードを段階的に機械へ近づける変換器です。字句解析、構文解析、意味解析、IR、最適化、コード生成の流れを一本で捉えると、言語と実行基盤のつながりがはっきり見えてきます。

参考文献

公式・標準

• The Rust Compiler Development Guide

書籍

• Alfred V. Aho, Monica S. Lam, Ravi Sethi, Jeffrey D. Ullman, Compilers: Principles, Techniques, and Tools
• Keith Cooper, Linda Torczon, Engineering a Compiler
• Torben Ægidius Mogensen, Introduction to Compiler Design
• Crafting Interpreters

解説・補助

• GCC Internals
• LLVM Documentation
• System V AMD64 ABI