セルフホスト可能な C コンパイラを作った

はじめに

- C コンパイラと言えば、世界三大自作したいソフトウェアの一角である。というわけで『低レイヤを知りたい人のためのCコンパイラ作成入門』 (以下 compilerbook) 片手に作ることにした。 -

- 実装する機能を適切に絞ってやればゴールデンウィークの間 (2025-05-03 から 2025-05-06) にセルフホストまで持っていけるのではないか？という仮説を立て、ISO 8601 の表記で 4日間を表す “P4D” を冠して P4Dcc と名付けた。 -

- P4Dcc のリポジトリはこちら -

レギュレーション

- 実装するのは C 言語からアセンブリ言語への変換部分のみ。アセンブラやリンカは GCC をそのまま用いる -
- compilerbook を読みながら実装してよい -
- compilerbook に記載されたソースコードを除き、コンパイラのソースコードを読まない -
- GCC の出力は見てもよい。それ以外のコンパイラの出力 (特に 9cc などの compilerbook 準拠のコンパイラ) は見ない -
- ソースコードの生成やデバッグに AI を使わない。ツールの使用方法を調べる目的 (GCC に渡すフラグなど) には使ってよい -

設計

- ゴールデンウィークの4日間で終わらせたいので、実装する言語機能は最低限に絞ることが必要になる。今回は次のような設計とした (compilerbook の設計を踏襲しているものは除く)。 -

- 宣言の文法を単純にパースできるものに絞る -
- - typedef をサポートしない -
  - - 構造体には必ず struct キーワードを書く -
  -
- - 配列型をサポートしない -
  - - 常にヒープに確保してポインタ経由で扱う -
  -
- - 以上の制限により、型に関する情報が必ず変数名の前に来る -
-
- 無くてもなんとかなる構文糖を実装しない。ソースを書くときに頑張る -
- - インクリメント・デクリメント演算子 (1足したり引いたりする) -
- - 複合代入演算子 (左辺と右辺で 2回書く) -
  - - なお、+= と -= はセルフホスト達成後に実装された -
  -
- - while (for で置き換える) -
  - - なお、while はセルフホスト達成後に実装された -
  -
- - switch (if で置き換える) -
- - ほか多数 -
-
- プリプロセッサのほとんどを実装しない -
- - 数値または識別子へ置換する単純な #define のみサポートする -
- - 特に、#include をサポートしないのは重要な設計判断。すべて 1ファイルでおこなう -
-
- グローバル変数を用いない -
- - stdin、stdout、stderr を含む -
- - これは compilerbook とは大きく設計が変わった部分 -
- - これにより、トップレベルに来るのは関数か構造体の定義/宣言のみとなった -
-
- 変数のシャドウイングを実装しない -
- - 変数は常に関数スコープ -
- - グローバル変数もないので、スコープチェーンの実装が不要になる -
-

言語機能

- 最終的にサポートされた機能は以下のとおり。 -

- 文 -
- - if / else -
- - for -
- - break -
- - continue -
- - return -
- - while (実装はセルフホスト達成後) -
-
- 式 -
- - 二項演算 -
  - - + / - / * / / / % -
  - - == / != -
  - - < / <= / > / >= -
  - - && / || -
  -
- - 代入 -
  - - = -
  - - += / -= (実装はセルフホスト達成後) -
  -
- - 単項演算: - / ! / * / & / sizeof -
- - 関数呼び出し: f(a, b) -
- - 配列アクセス: a[b] -
- - メンバ呼び出し: a.b / a->b -
- - 整数リテラル -
- - 文字列リテラル -
-
- 型 -
- - char -
- - int -
- - long -
- - void -
- - struct -
- - それらのポインタ -
-
- 宣言・定義 -
- - 関数 -
- - 構造体 -
-
- プリプロセッサ -
- - 引数なし #define -
-

開発

- 時系列順に開発の様子を辿っていく。 -

1日目 (2025-05-03)

- compilerbook では整数一つのパース・コード生成から始めるが、今回は以下のようなソースをパースしてコード生成するところからスタートすることにした。 -

int main() {
-    return 42;
-}

- この時点で、struct Token、struct Parser、struct AstNode、struct CodeGen といった主要なデータ構造が定義され、この後もほぼ同じソース設計のまま進めている。 -

- compilerbook のようなインクリメンタルな進め方を取らずに、最初から普通の言語処理系のような構成にしたのには理由がある。 -

- それは、どのくらいの言語機能があればコンパイラを作るのに十分かをこの時点で見積もるためである。開発を開始する前にも必要な言語機能にはあたりを付けていたが、実際にプロトタイプを作ってみて、これだけの機能セットがあれば足りるだろうという正確な TODO リストを作りたかった。実際、このとき作ったチェックリストはこのあともほとんど変わっていない (大きな変化点は、配列型をサポートしないと決めたことくらいか)。 -

- このあとは、おおむね compilerbook に従って以下のように機能追加を続けた。 -

- 四則演算 -
- 単項マイナス -
- 比較 -
- ローカル変数 -
- if 文 -
- for 文 -
- 引数なしの関数呼び出し -
- 引数ありの関数呼び出し -
- 文字列リテラル -

- 一日の終わりには、次のようなプログラムのテストが通るようになった。 -

int printf();
-
-int main() {
-    int i;
-    for (i = 1; i <= 100; i = i + 1) {
-        if (i % 15 == 0) {
-            printf("FizzBuzz\n");
-        } else if (i % 3 == 0) {
-            printf("Fizz\n");
-        } else if (i % 5 == 0) {
-            printf("Buzz\n");
-        } else {
-            printf("%d\n", i);
-        }
-    }
-    return 0;
-}

2日目 (2025-05-03)

- この時点で、不足している機能はおおよそ2つ。ポインタと構造体である。 -

- このあたりからは compilerbook の解説も減っていき (構造体については完全に記載がない)、実装も離れていっている。 -

- 以下のように実装を進めていった。 -

- char、long、void -
- ポインタ -
- アドレス演算子: & -
- 間接参照演算子: * -
- sizeof -
- ポインタの演算 -
- #define -
- 構造体の定義・宣言 -
- 構造体の sizeof -
- メンバーアクセス -
- 論理演算子: &&、|| -
- 初期化式つきの変数定義 -
- 文字リテラル -
- 配列アクセス -
- 論理演算子: ! -
- 返り値なしの return -

- &、*、sizeof あたりの実装が終わるとかなり C 言語らしくなっていき楽しい。 -

- このあたりから、セルフホストに向けて逆方向からのアプローチも並行しておこなっている。セルフホストするためには処理系のソースコードで使っている言語機能をすべて実装する必要があるわけだが、これまでは処理系が扱える機能を拡充していくという方向だった。この逆、つまり処理系のソースコードで使っている機能を減らすことでもセルフホストに近付いていく。 -

- 例えば、このコンパイラは typedef をサポートしていないが、開発中ずっと typedef を使わないというのは面倒だ。そこで、セルフホストがある程度現実的になるまでは構造体を typedef しておいて、途中のどこかで typedef を手で脱糖する。 -

- これらの作業をおこなうことで、処理系自身のソースコード main.c をパースしてバイナリを出力することができるようになった。いわゆる第2世代のコンパイラである。この現時点ではまだ第2世代コンパイラは何もできない (何を与えてもクラッシュする)。 -

3日目 (2025-05-03)

- さて、第2世代コンパイラが手に入ったので、ここからは地獄のデバッグ作業が始まる。多段になっているために問題が起きている箇所の特定が難しい。 -

- ……と考えていたのだが、実際のところデバッグは1時間ほどで終わってしまった。修正したのは1点のみ。なんのことはない、2日目終了時点でほとんど完成していたわけだ。 -

- 記念すべき (?) 最後のバグはこちら。 -

         gen_expr(g, ast->expr1, GEN_RVAL);
-     } else {
-         gen_expr(g, ast->expr1, GEN_RVAL);
--        gen_lval2rval(ast->expr1->ty);
-+        gen_lval2rval(ast->expr1->ty->to);
-     }
- }

- メモリアドレスから参照先の値を得る際、その型によってロードする命令の種類を変える必要があるのだが、その切替をポインタ型でおこなっていた。正しくは、そのポインタ型が指す型を元にして切り替えなければならない。 -

- これを修正すると、第2世代コンパイラが第3世代コンパイラを出力できるようになり、その後も第N世代が第N+1世代を生成できるようになった。 -

- あとは、第2世代のコンパイラがそれ以降のコンパイラとバイナリレベルで一致するかどうかを確かめればよい。実際に調べてみると、ほとんどの場所が一致したもののどの世代も 6バイトだけ異なることがわかった。 -

- 一体どこが異なるのか。hexdump の差分がこちら。 -

$ diff -u <(hexdump -C p4dcc2) <(hexdump -C p4dcc3)
-@@ -5090,7 +5090,7 @@
- 00015db0  72 72 61 79 5f 65 6e 74  72 79 00 66 72 61 6d 65  |rray_entry.frame|
- 00015dc0  5f 64 75 6d 6d 79 00 5f  5f 66 72 61 6d 65 5f 64  |_dummy.__frame_d|
- 00015dd0  75 6d 6d 79 5f 69 6e 69  74 5f 61 72 72 61 79 5f  |ummy_init_array_|
--00015de0  65 6e 74 72 79 00 63 63  6d 69 42 49 59 6b 2e 6f  |entry.ccmiBIYk.o|
-+00015de0  65 6e 74 72 79 00 63 63  53 71 64 47 76 57 2e 6f  |entry.ccSqdGvW.o|
- 00015df0  00 66 61 74 61 6c 5f 65  72 72 6f 72 00 72 65 61  |.fatal_error.rea|
- 00015e00  64 5f 61 6c 6c 00 74 6f  6b 65 6e 69 7a 65 00 74  |d_all.tokenize.t|
- 00015e10  79 70 65 5f 6e 65 77 00  74 79 70 65 5f 6e 65 77  |ype_new.type_new|

- fatal_error、read_all、tokenize type_new はいずれも main.c で定義された関数の名前である。このことから考えると、これは GCC が埋め込んだシンボルテーブルである可能性が高い。わずかに異なっている 6バイトは、ランダム生成された何かのように見える。 -

- そこで gcc に -s (シンボルテーブルを削除するフラグ) を渡してみると、めでたく2世代目以降のコンパイラのバイナリが完全に一致するようになった。 -

- これにてセルフホスト達成である。 -

おわりに

- 最終的な実装は1900行ほど、所要時間は20時間弱となった。 -

- 正直なところ、思ったより早く終わって拍子抜けしている。これは compilerbook がうまく実装順を整理しているのと、アセンブリの細かい落とし穴を事前に解説して潰していることが大きいと思われる。 -

- 当初の仮説どおり、サポートする機能を慎重に選ぶことにより短期間でセルフホストまで持っていくことができた。案外簡単に作れてしまうので、まとまった休みに是非いかがだろうか。 -