最近 C++、Rust、Go のコンパイル過程を調べている。
最初の壁は、並んだ用語の多さだ。
- GCC
- Clang
- LLVM
- AST
- IR
- SSA
- MIR
- GIMPLE
- RTL
- Linker
- Loader
それぞれの単語だけを見れば、何とか理解できる気がする。でも図に並べてみると、すぐ混乱する。
後で、問題は用語の多さではなく、実際のプログラムを1つ出発点にすることだと分かった。
コンパイラは単純に「ソースコードをアセンブリに変換する」わけではない。より正確に言えば、プログラムの抽象度を段階的に下げている。
どの段階の中間表現にも、特定の問題を扱いやすくする役割がある。
次は、ごく小さな C++ プログラムを通して、主流のコンパイル経路をつなげてみる。
このコードには、意図的にいくつかの要素を残している。
この小さなプログラムだけで、主流のコンパイルフローをほぼ一通り把握できる。
1. ソースコードはコンパイラが本当に扱いたいものではない
プログラマーが見ているのは、
人間には、次のようにほぼ同じ意味だと理解しやすい。
ただし、コンパイラは最初からそう解釈できない。
ソースコードは単なる文字の流れにすぎない。
i n t 空格 x 空格 = 空格 I N C ...
コンパイラはまず文字を処理し、扱いやすい安定した構造に変換しなければならない。
現代のコンパイルフローがソースコードから直接アセンブリへ飛ばないのはこのためだ。ソースコードは人間には読みやすいが、機械が解析するには適さない。
2. プリプロセッサ：C/C++ で最初に乗るテキスト処理の層
C/C++ の場合、最初のステップは通常プリプロセスだ。
clang++ -E main.cpp -o main.ii
プリプロセッサが主に扱うのは、
#include
#define
#ifdef
#pragma
このプログラムで目を引くのは、
プリプロセス後、中心的なコードは次のようになる。
この段階では、重要な理解が一つある。
プリプロセスはセマンティック解析ではない。
型を理解するわけではない。
add が関数かどうかも分からない。
INC(add(1, 2)) が妥当かどうかも分からない。
規則に従ってテキストを展開するだけだ。
C/C++ のマクロが問題を起こしやすいのも、このためだ。マクロは関数ではない。関数のような型チェックやスコープの規則に従うこともない。
たとえば、
次のように書くと、
次のように展開される。
次のようにはならない。
C/C++ のよくある奇妙な問題の多くは、まだコンパイル処理には入っておらず、プリプロセス段階で地雷を仕込んでいただけだった。
3. 字句解析：文字を Token に切り分ける
プリプロセス後、コンパイラは字句解析を始める。
ソースコードの一部は、
次のように切り分けられる。
この段階は「単語に分ける」ことだけを担当する。
int がキーワードだと分かる。
x が識別子だと分かる。
1 が数値リテラルだと分かる。
しかし、次はまだ分からない。
x 是局部变量
add 是函数
printf 是外部函数
1 能不能传给 add
これらは字句解析が担当する範囲ではない。
Clang で Token を確認するには、
clang++ -Xclang -dump-tokens -fsyntax-only main.cpp
コンパイルエラーに不正な文字、閉じていない文字列、数値リテラル書式の誤りが現れた場合、通常この層付近で止まる。
4. 構文解析：Token から AST へ
Token はまだ一続きの並びだ。
コンパイラはプログラムの構造を知る必要がある。
たとえば、
構文解析すると木構造になり、簡略化するとおおむね次のようになる。
これが AST（抽象構文木）だ。
AST の目的は高級感を出すことではなく、ソースコードの構造を安定した形に保つことだ。
ソースコードはテキストだ。
AST は構造だ。
ここまで来て、ようやくコンパイラは次のことを分かるようになった。
这是一个变量声明
变量名是 x
初始化表达式是一个加法
加法左边是函数调用
加法右边是整数 1
ただし、AST だけではプログラムが正しいことは証明できない。
たとえば、
foo がまったく存在しなくても、まず AST は構築できる。
構文上の問題はない。
問題はセマンティクスの側だ。
Clang で AST を確認するには、
clang++ -Xclang -ast-dump -fsyntax-only main.cpp
実際の C++ の AST は非常に長くなる。テンプレート、オーバーロード、暗黙の変換、コンストラクタ、デストラクタがすべて現れる。
C++ のフロントエンドが複雑なのもこれが理由だ。Token の切り分けが難しいわけでも、構文木を描くのが難しいわけでもなく、セマンティクスが複雑なのだ。
5. セマンティック解析：コンパイラがプログラムを本当に理解し始める
セマンティック解析では、次のような問題を扱う。
add 是否存在
add 参数数量是否正确
add 参数类型是否匹配
printf 是否声明过
int x 的初始化是否合法
函数返回值是否符合声明
このコードなら、
プリプロセスすると、
セマンティック解析では次を確認する。
add 的类型是 int(int, int)
add(1, 2) 返回 int
返回值可以和 1 做加法
结果可以赋给 int x
構文は依然として成立する。
AST も構築できる。
だがセマンティック解析で、引数の型が一致しないとしてエラーになる。
開発者が普段「コンパイルエラー」と呼ぶものも、もう少し細かく分けられる。
语法错误：代码结构不合法
语义错误：结构合法，但意思不合法
链接错误：单个文件能编译，但最终符号找不到
この3種類のエラーは、それぞれまったく異なる段階で起きる。
Rust の Borrow Checker もこの大きな範囲に含まれる。
たとえば、
let r;
{
let x = 1;
r = &x;
}
println!("{}", r);
これは構文エラーではない。
コードの構造は完全に正当だ。
本当の問題はセマンティクスの側にある。x はすでにスコープを離れているため、r から参照できない。
したがって、Rust の所有権、借用、ライフタイムは、構文上の特性ではなく、より強いセマンティック解析と理解するのが正しい。
Rust のコンパイラが Go のコンパイラよりかなり複雑な理由の一つがこれだ。
6. AST は最適化に向かないので IR が必要
コンパイルフローを初めて学ぶ人は、こう思ってしまう。
源码
↓
AST
↓
汇编
このモデルは粗すぎる。
現代のコンパイラは、最適化を AST 上で長らく行うわけではない。
理由は至って単純だ。
AST はソースコードに近すぎる。
たとえば、
AST には多くのソースコード上の構造が残る。
一方、最適化器が最も気にしているのは、
这个值从哪里来
这个值被谁使用
这个计算有没有副作用
这个分支是否可达
这个变量能不能放进寄存器
这个函数能不能内联
AST はこれらの問題を扱うのに向いていない。
そこでコンパイラは AST を IR に落とす。
IR は Intermediate Representation、つまり中間表現のことだ。
このコードは、
三アドレスコードに落としたものと理解できる。
t1 = call add, 1, 2
t2 = t1 + 1
x = t2
call printf, "%d\n", x
return 0
こうすると AST より最適化に向いている。
式木は単純な命令に分解される。
データ依存関係も分かりやすくなる。
LLVM IR はもう少し次の形になる。簡略化すると、
ここには、いくつかの注目点がある。
C++ では add が次のようにコンパイルされることがある。
_Z3addii
これは C++ の name mangling（名前修飾）だ。
C++ は関数のオーバーロードをサポートするため、リンカは add という名前だけでは判別できない。
たとえば、
ソース上はどちらも add だが、リンク時には区別されなければならない。
また、printf は次のように宣言されている。
なので C++ の名前修飾は適用されず、そのまま printf となる。
printf
これが extern "C" の実用的な意味の一つだ。シンボル名を制御し、C ABI と連携できるようにする。
7. 最適化：コンパイラがプログラムの書き換えを始める
最適化を無効にした場合、コンパイラはプログラムの構造を比較的そのまま保つ。
最適化を有効にすると、
clang++ -O2 -S -emit-llvm main.cpp -o main.ll
このコードは、次のような形に最適化される可能性が高い。
define i32 @main() {
entry:
call i32 (ptr, ...) @printf(ptr @.str, i32 4)
ret i32 0
}
add(1, 2) は消える。
INC を展開したときの + 1 も消える。
x も消える。
最後に残るのは、
printf("%d\n", 4)
これはコンパイラが勝手にコードを変えたわけではない。
変更しても観測可能な挙動が変わらないことを、コンパイラが証明した結果だ。
ここでは、典型的な最適化がいくつか発生している。
函数内联：add(1, 2) 被展开
常量折叠：1 + 2 + 1 变成 4
死代码删除：中间变量 x 不再需要
Java JIT、Go の SSA、Rust の LLVM 最適化を見ていれば、これらの最適化名が何度も出てくることに気づく。
理由は単純で、プログラム最適化の基本的な問題はいずれも同じ方向を向いているから。
8. SSA：現代の最適化器が「変数への代入は1回だけ」を好む理由
SSA は現代のコンパイラ最適化を理解する鍵になる。
SSA は Static Single Assignment の略だ。
各変数は、静的プログラムの中で一度だけ代入される。
この例を見てみよう。
通常のコードでは x に2回代入する。
制御フローが複雑になると、最適化器はある地点の x がどこから来たのか判断しにくくなる。
SSA では次のような形に変える。
x1 = 1
if cond goto then else merge
then:
x2 = 2
goto merge
merge:
x3 = phi(x1, x2)
return x3
ここにある、
phi(x1, x2)
SSA の価値は、「変数が変化する」という事実を、明示的なデータフロー関係へ変えることにある。
これは最適化にとって非常に重要だ。
たとえば、
常量传播
死代码删除
公共子表达式消除
循环不变代码外提
值编号
逃逸分析
これらはいずれも SSA の恩恵を受ける。
LLVM IR は SSA 形式だ。
Go コンパイラの内部でも SSA を使っている。
HotSpot C2 も SSA に近い Sea of Nodes IR を使う。
データベースの最適化器の多くも SSA と名付けないものの、同様のデータ依存関係を保持している。
これが特定コンパイラの小さな技巧ではなく、現代的な最適化システムの基礎となる方法だ。
9. バックエンド：プラットフォーム非依存の IR からマシン依存の IR へ
LLVM IR も依然としてプラットフォームに依存しない。
たとえば、
%sum = add i32 %a, %b
この命令には、次のことが指定されていない。
x86 用哪条指令
ARM 用哪条指令
结果放哪个寄存器
参数从哪里来
调用约定是什么
これらはバックエンドが担当する。
指令选择
寄存器分配
指令调度
调用约定
栈帧布局
目标平台 ABI
同じ加算でも、x86-64 では次のようになることがある。
mov eax, edi
add eax, esi
ret
ARM64 では次のようになることがある。
add w0, w0, w1
ret
IR が同じでも、対象マシンが違えば最終的な命令も変わる。
これも LLVM の価値だ。
言語の実装者は LLVM IR を出力するだけで、LLVM のバックエンド能力を借用できる。
そうでなければ、言語を1つ書くたびに、次のすべてを自前でサポートしなければならない。
x86-64
ARM64
RISC-V
Windows ABI
Linux ABI
macOS ABI
寄存器分配
指令选择
调试信息
异常处理
これをすべて自前で対応するのは、まず現実的じゃない。
10. オブジェクトファイル：機械語でもまだ最終プログラムではない
バックエンドがアセンブリを生成すると、アセンブラがオブジェクトファイルを作成する。
clang++ -c main.cpp -o main.o
main.o には機械語が含まれるが、まだ完全なプログラムではない。
nm を使うとシンボルを確認できる。
nm main.o
次のような出力が得られるかもしれない。
0000000000000000 T _Z3addii
0000000000000010 T main
U printf
意味はおおむね次のとおり。
_Z3addii 已定义
main 已定义
printf 未定义
U printf はエラーではない。
現在のオブジェクトファイルには printf の実装がないため、リンク時に別の場所から探すと示しているだけだ。
初めて undefined reference に遭遇したとき、よく誤解されるのがこの点だ。
構文エラーでもない。
型エラーでもない。
リンク段階でシンボルの解決に失敗した 것이다。
11. リンク：ばらばらのバイナリを1つのプログラムに組み立てる
リンカが行うことは、おおむね次のように理解できる。
main.o
+
libc
+
启动代码
+
运行时库
↓
可执行文件
解決すべき問題は次のとおり。
符号解析
地址分配
重定位
静态库选择
动态库记录
入口点设置
C++ を使う場合は、さらに次が関係する。
name mangling
ODR
模板实例化
静态初始化
异常表
RTTI
虚表
たとえば、
undefined reference to `foo'
と表示された場合、リンカは foo の実装を見つけられない。
multiple definition of `foo'
と表示された場合、複数のオブジェクトファイルが同じ強シンボルを定義している。
undefined reference to `_Z3addii'
と表示された場合、C++ のシンボル名が一致していない。宣言と定義が食い違っているか、C/C++ の ABI が混在している可能性がある。
リンカは、コンパイラのフロントエンドとは別の大きなシステムだ。
大規模な C++ プロジェクトのビルド問題の多くは、コンパイラの問題ではなくリンカの問題だ。
12. ローディング：プログラム実行前、OS が引き継ぐ
実行：
./a.out
CPU がそのまま main から実行するわけでもない。
Linux では、おおよそ次の過程を経る。
内核读取 ELF
映射程序段到虚拟内存
加载动态链接器
加载共享库
处理重定位
初始化运行时
调用 main
プログラムのメモリ配置はおおよそ次のようになる。
.text 代码段
.rodata 只读数据
.data 已初始化全局变量
.bss 未初始化全局变量
heap 堆
stack 栈
厳密には、完全な流れは次のものではない。
源码 → 可执行文件
ではなく、次の形になる。
源码 → 目标文件 → 可执行文件 → 进程
コンパイラは「プログラムをどう生成するか」を解決する。
リンカは「プログラムをどう合成するか」を解決する。
ローダは「プログラムをどうプロセスに変えるか」を解決する。
13. Clang、LLVM、GCC を1つの図にどう位置づけるか
ここで各名前を見返すと、かなり整理できる。
Clang + LLVM の場合は次のようになる。
C++ Source
↓
Clang Frontend
↓
Clang AST
↓
LLVM IR
↓
LLVM Optimizer
↓
LLVM Backend
↓
Object File
↓
Linker
↓
Executable
GCC は別の経路になる。
この2つの経路は、同じ種類の問題 Facingするが、内部表現が異なる。
Clang は LLVM の別名ではない。
LLVM も Clang の別名ではない。
より正確に言えば、
Clang 是 C/C++/Objective-C 前端。
LLVM 是中端和后端基础设施。
GCC 是另一套完整编译器系统。
対応関係は、次のように整理できる。
Clang 负责读懂 C++。
LLVM 负责优化和生成机器码。
GCC 自己既有前端，也有中端和后端。
14. Rust に HIR や MIR がある理由、そして LLVM を使う理由
Rust の流れはおおよそ次のようになる。
Rust Source
↓
AST
↓
HIR
↓
THIR
↓
MIR
↓
Borrow Check
↓
LLVM IR
↓
LLVM Backend
↓
Machine Code
Rust のこの階層が複雑なのは、複雑な様子を見せたいからではない。
各層には明確な役割がある。
AST はソースコードに近い。
HIR は一部の構文糖や表層的な構造を落とし、プログラムの形を安定させる。
THIR は型チェック後の式分析に向いている。
MIR は Rust にとって重要な層で、制御フロー、move、borrow、drop、ライフタイムなどのセマンティクスを表現するのに適している。
LLVM IR は、汎用的な最適化と機械語生成の段階へ入るためのものになる。
ここrale一つ区別しておきたい。
MIR 是 Rust 语义层的 IR。
LLVM IR 是机器代码生成层的 IR。
Borrow Checker は LLVM IR に直接依存できない。
LLVM IR はすでに低水準で、その層では Rust の ownership、borrow、drop のセマンティクスを主な解析対象として扱うのに適さない。
AST に直接依存することもできない。
AST は構文の表面には近すぎて、構文糖が多いため、厳密なデータフローや制御フロー解析に向かない。
だから Rust には MIR が必要なのだった。
中間表現の本当の価値は、抽象をもう1つ増やすことではなく、特定解析に適したプログラムの形を提供することにある。
15. Go のコンパイルフローが単純に見える理由
Go のコンパイルフローをおよそまとめておくと、次のようになる。
Go Source
↓
Parser
↓
AST
↓
Type Check
↓
SSA
↓
Go Backend
↓
Machine Code
Go はデフォルトでは LLVM を使わない。
独自の SSA とバックエンドを持っている。
これは Go の設計目標と関係している。
Go 言語そのものは、意図的に単純さを保つ。
没有模板元编程
没有复杂宏系统
没有 Rust 那种 ownership 检查
没有 C++ 那种重载和隐式规则
だから Go コンパイラはより直接的な処理ができる。
Go のコンパイルが速い重要な理由の一つもこれだ。
ただし、「単純」ということは、Go コンパイラに技術的な内容が乏しいことを意味しない。
Go のエスケープ解析、インライン化、SSA 最適化、スタック成長、GC 関連メタデータの生成には、多くのエンジニアリング上の細部がある。
ただし C++ や Rust と比べれば、Go のフロントエンドのセマンティクスの複雑さは確実に低い。
16. 現代のコンパイラが新しい IR を作り続ける理由
ここまで来れば、最初の疑問にはかなり答えが出てきた。
GCC が GIMPLE と RTL を持つのはなぜ？
LLVM が LLVM IR、SelectionDAG、Machine IR を持つのはなぜ？
Rust が HIR、THIR、MIR を持つのはなぜ？
Go が SSA を持つのはなぜ？
どの段階にも適する単一の表現が存在しないからだ。
AST はソースコードの構造を表すのに適している。
HIR は表層的な構文を取り除くのに適している。
MIR は言語のセマンティクスと制御フローを表すのに適している。
LLVM IR はプラットフォームに依存しない最適化に向いている。
Machine IR はレジスタ割り当てと命令スケジューリングに向いている。
RTL は、GCC のバックエンドがマシンに近い操作を記述するのに適している。
同じプログラムでも、段階によって見方を変える必要がある。
人間にとっては、それはビジネスロジックだ。
フロントエンドにとっては、構文木だ。
型システムにとっては、制約の集合だ。
最適化器にとっては、データフローグラフだ。
バックエンドにとっては、命令選択とレジスタ割り当ての問題だ。
リンカにとっては、シンボルとリロケーションの記録だ。
ローダにとっては、ELF セグメントと共有ライブラリの依存関係だ。
コンパイラの複雑さは、まさにこれらの視点を行き来することから生まれている。
17. 本当に覚えておきたい主流のコンパイルフロー
すべての細部まで追うのではなく、主流の経路だけをおさえておけば、こう整理できる。
主なコンパイラに対応させると、次のようになる。
この図は、AST、IR、SSA を個別に暗記するより有用だ。
同じ実用的なコンパイルパイプラインの中で、各システムがどこに位置するかが分かるからだ。
18. この仕組みを学ぶと実際の開発で何に役立つのか
これは理論だけの話ではない。
マクロ起因の問題に気づいたら、プリプロセス結果を見ればよい。
clang++ -E main.cpp
構文やセマンティクスの問題なら、フロントエンドで起きていることが分かる。
clang++ -Xclang -ast-dump -fsyntax-only main.cpp
最適化前後の差を確認したかったら、LLVM IR を見ればよい。
clang++ -O0 -S -emit-llvm main.cpp -o main_O0.ll
clang++ -O2 -S -emit-llvm main.cpp -o main_O2.ll
シンボルが見つからない場合は、オブジェクトファイルを確認すればよい。
nm main.o
ELF の構造を確認したければ、
readelf -a a.out
アセンブリを確認したければ、
objdump -d a.out
これらのツールは腕を競うためのものじゃない。
コンパイルフローの異なる段階に対応している。
どの段階で問題かを絞れれば、解決はすでに半分できたようなものだ。
19. コンパイラが本当に価値を生むところ
コンパイラで最も価値があるのは、いくつかの用語ではなく、複雑なシステムを眺める方法だ。
複雑な入力が、そのまま実行されることはない。
まず、何らかの intermediate representation に変わる。
その後、解析され、制約を受け、最適化され、低いレベルに落とされ、ようやく実行層へ入る。
このパターンはコンパイラだけにあるわけではない。
データベースは SQL を論理プランと物理プランに変える。
JVM はバイトコードを内部 IR に変換し、その IR を JIT に渡す。
React は UI の更新を Fiber 構造にまとめる。
Kubernetes Scheduler はスケジューリング要求をリソース制約とスコアリングモデルに変える。
見た目は異なるものの、下層にある考え方はかなり近い。
输入不是直接执行的。
先建立表示。
再基于表示做分析和优化。
最后执行。
コンパイラは、この考え方の最も古典的で、完成度の高い版だ。
C++、Rust、Go、GCC、LLVM をつなぐ流れを腹落ちさせてから、JVM、データベース、フロントエンドフレームワーク、スケジューリングシステム回头見てみると、多くの設計が孤立した用語ではなく理解できる。