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

言語機能

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

• 文
  • 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 に従って以下のように機能追加を続けた。

1. 四則演算
2. 単項マイナス
3. 比較
4. ローカル変数
5. if 文
6. for 文
7. 引数なしの関数呼び出し
8. 引数ありの関数呼び出し
9. 文字列リテラル

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

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 の解説も減っていき (構造体については完全に記載がない)、実装も離れていっている。

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

1. char、long、void
2. ポインタ
3. アドレス演算子: &
4. 間接参照演算子: *
5. sizeof
6. ポインタの演算
7. #define
8. 構造体の定義・宣言
9. 構造体の sizeof
10. メンバーアクセス
11. 論理演算子: &&、||
12. 初期化式つきの変数定義
13. 文字リテラル
14. 配列アクセス
15. 論理演算子: !
16. 返り値なしの 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世代目以降のコンパイラのバイナリが完全に一致するようになった。

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