Cコンパイラを作ろうとしてみた

はじめに

みなさま、夏休みを満喫しておられるでしょうか。はじめましての方ははじめまして、@cp20 です。ちなみにこの記事は夏のブログリレー 2024の4日目の記事です。今年は去年にも増してたくさんのブログが書かれそうで楽しみにしています。

さて、この記事ではCコンパイラを自作した話をしていきます。結局バグが取れずに惜しくも完成 (完成の定義は後述) しなかったのですが、完成の3歩手前ぐらいまでは作れたので、その中で得られた経験などを書き連ねていこうと思います。

重要な追記 (2024/08/23): 実は完成していました (詳しくは後述します)

ちなみに成果物は↓のリポジトリから見れますので良かったら覗いてみてください。

自作Cコンパイラについて

コンパイラとは

世の中にはたくさんのプログラミング言語がありますが、その中でもコンパイル型言語と呼ばれるような言語 (CやRust、Goなど) はプログラムを実行する前に「コンパイル」というステップを踏みます。このコンパイルという作業を行うのが「コンパイラ」です。

コンピューター (CPU) はプログラミング言語そのものを解釈することができないので、コンパイラがそれを解釈してコンピューターが実行できる形式 (機械語) に変換します。これがコンパイルです。

Cコンパイラを作るとは

C言語のプログラムは通常次のような流れで実行ファイルになります。

C言語のプログラムをアセンブリにする (狭義のコンパイル)
アセンブリをオブジェクトファイルにする
オブジェクトファイルをn個繋げて実行ファイルにする (リンク)

ただしLLVM IRという中間言語を挟むこともできて、その場合は次のようなステップを踏むことになります。

C言語のプログラムをLLVM IRで書かれたプログラムにする (狭義のコンパイル)
LLVM IRのプログラムを (アセンブリを経由して) オブジェクトファイルにする
オブジェクトファイルをn個繋げて実行ファイルにする (リンク)

今回はC言語のプログラムをLLVM IRのプログラムに変換するコンパイラを作ることにしました。

何をもって完成とするか

「セルフホスト」できることをCコンパイラ完成の定義、つまり今回の目標とすることにしました。

C言語でCコンパイラを書くことによって、理論上は自分で書いたCコンパイラで自分の書いたCコンパイラをコンパイルすることができて、かつそのCコンパイラはもとのCコンパイラと同じ動作をするはずです。これをセルフホストと呼びます。

既存のCコンパイラによってコンパイルされた自作Cコンパイラを1cc、1ccによってコンパイルされた自作Cコンパイラを2cc、2ccによってコンパイルされた自作Cコンパイラを3ccと呼ぶことにします。実際に1ccと2ccを一致させるのは最適化などの観点から難しいので、2ccと3ccが一致することを目指します。2ccと3ccが一致すれば4cc以降も明らかに無限回コンパイルが成功します。

経緯

東工大には「プログラミング創造演習」という講義があります。 (情報工学系の専門科目) ざっくり言えば自分で設定したプログラミングに関連する課題に自分で取り組むだけの科目で、プログラミングが得意な人にはぜひオススメしたい講義です。

もう少しシステム的な話をすると、情報工学系では「手続き型プログラミング基礎」「手続き型プログラミング発展」という講義があり、それでC言語のプログラミングの基礎を学ぶのですが、既に学習している or 自分で学習することができる人は先の講義を取ることで前2つの講義の代わりとすることができます。

C言語はほとんど学んだことがなかったので創造演習を取るか悩んだのですが、創造演習でC言語を学べるような課題を設定すればいいことに気付いたので、そうしました。ただ特にC言語にまつわることでないとダメという制限はないので、競プロ、LLM、Kaggle、アプリ開発など各々好きなことをやっていました。

なぜコンパイラを作るのか

本能です。

制作過程

開発の流れ

↓の記事でも触れられていますが、低レイヤを知りたい人のためのCコンパイラ作成入門 (以下compilerbook) という記事(?)を参考に進めていました。Cコンパイラの基礎について非常に丁寧に書かれていて、Cコンパイラを作ろうという初心者の方には非常にオススメです。

ただセルフホストしようと思うと割と機能が必要で、先の記事だけだと足りません。例えばCコンパイラを作る上で (というかほぼ全てのCプログラムにおいて) 構造体を使うにも関らず、構造体の実装については全く触れられていません。そういう部分に関しては既存のCコンパイラ (具体的に言えばClang) の出力を参考にしながら開発を進めていました。

ただこの記事はx86のアセンブリにコンパイルしているので、適宜LLVM IRに読み替えながら進めていました。LLVM IRも全く触ったことがなかったのでそこも学びつつ進めていきました。とはいっても入門書などを読んだわけではなく、Clangの出力を見て、それをなんとなく理解して、それと同じような出力をするようにしました。LLVM IRの理解にはGitHub Copilot Chatがかなり役立ちました。

詰まったポイント

LLVM IRが分からない

最初の方はLLVM IRの理解が大変でした。compilerbookに沿ってtokenizer、parser、generator (code generator) の3つに分けてコンパイラ制作を進めていたのですが、LLVM IRの理解が甘い最初はgeneratorで多くのバグを埋め込みました。

パースが難しい

基本的な機能ができてきてLLVM IRへの理解度も高まってくると、次はparserでバグを生んでいました。generatorに比べて直接のデバッグが難しいので、適宜printしつつという感じでデバッグしていました。parserの難しいところは、何がvalidで何がvalidでない構文なのかを判別するのが大変というところです。上手く一般的に文法を記述したいところですが、Cの文法が予想以上に複雑で、それを上手く書き下すのは自分にはかなり難しかったです。eBNF形式で文法を書いていたのですが、正直適切に全てを記述できている気がしていません。

文法周りで言うと、単純に構文的に正しいというだけでなく、意味的に正しいかどうかを確かめる必要があるのも難しいポイントです。ただC言語はそこまで意味的な解析をすることは必要ではないので、あまり大きな詰まりポイントではなかったです。

セルフホストができない

機能が一通りそろってさぁ自分自身をコンパイルするぞと思ってやってみると、たいてい上手くいきません。構文が上手く取れていなかったり、generatorが上手く動いてなかったり、その他もろもろたくさんのエラーが起きました。

compilerbookに従って、途中まではmalloc (calloc) してfreeしないという戦略でコンパイラを書いていました。しかし途中で全くもって原因が分からないエラーが発生したので、大部分をfreeするようにしたところ上手く動きました。freeのことを考えるとメモリ管理が一気にややこしくなって、メモリのライフサイクルの管理は人間がやることではないなという感想を抱きました。

ちなみにその段階でgdbというデバッガーを使い始め、あまりの使いやすさに感動しました。デバッガーを使うとなんとSegmentation Faultのスタックトレースが取れるんですよ！すごい！(((　スタックトレースもそうですが、それ以外にもかなり便利で、開発過程で結構gdbと仲良くなることができました。

しかし2ccができて3ccを作るぞという段階でこれまた原因不明のエラーが発生してしまいました。出力されたLLVM IRをClangが出力したお手本のLLVM IRのプログラムと見比べたり、適当にいじいじしながらデバッグしていたところ、最適化をするとエラーが直るという現象が発生して、頭を悩ませました。一部最適化をしてバグを直したのですが、今現在は割とちゃんと最適化しないとバグが直せないという問題に突き当たっています。最初期から悪い設計のまま続けているので、直そうにも直す気が起きないという現状で、めんどくさくてそのまま放置しています。またちゃんと設計を考えて作り直したいですね。

追記 (2024/08/23): 最初にも書いたんですが実はセルフホストできる状態にはなっていました。ただ某つよつよエンジニアの方に指摘されたんですが、スタックが枯渇して変なところにアクセスしてセグフォになっているらしくて、スタックの上限をなくす ulimit -s unlimited をすることによって上手くビルドが通りました。

さらに言えばビルドが通った後に2ccと3ccを比較 (吐き出されたLLVM IRのプログラムのdiffを取る) すると差がないことがわかったので、無事セルフホストが達成されました。やった～～

作る上でのコツ(?)

基本compilerbookの受け売りです。compilerbookを読みながらやれば自然とできると思います。

インクリメンタルに作る

インクリメンタルに作るというのは、常に動く状態を維持するということです。C言語の文法全てを解釈できるparserを書いてからgeneratorの設計に取り掛かるのではなくて、小さい言語を動かせるコンパイラを作るところから始めます。

compilerbookで言えば、四則演算ができる言語を作り、比較演算ができるようにして、変数の概念を導入し、次に制御構文、次に関数の宣言/呼び出し、、、というように小さい言語に少しずつ機能を足していって最終的にC言語にしていきます。

インクリメンタルに作るメリットはいくつかありますが、次に代表的なものを挙げます。

バグを早期に発見して対処することができるようになる
モチベが続きやすい
機能を削りやすい

特に最初のメリットが大きいです。プログラムの開発はいかにバグを生まないかというよりも、いかにバグを発見して対処するかという戦いになりがちです。最初から一貫して作り言語としての体裁を持つことで、ちゃんと動くものができていることを確かめることができます。parserだけを実装してユニットテストを書くという手はないでもないですが、ちゃんとテストを書くのはかなり大変だと思います。

2つ目は気持ち的な話ですが、意外に重要になってくるかなと思います。最初ひたすらparserを書いているとたぶん病む気がします。言語として動くことが一番楽しいと思うので、最初から動くものを作るというのがモチベの観点で重要になってきます。

最後のやつはいかに手を抜くかという話です。C言語の仕様は最近のモダンな言語に比べれば非常に小さいとはいえ、全て実装するとなるとかなり膨大です。今回自分はセルフホストするのに必要な最低限の機能だけしか実装しないつもりだったので、うまく手を抜きたいところです。だんだん機能を追加していくという方針は、必要のない機能を実装しないという観点においては非常にやりやすいやり方です。

早すぎる最適化をしない

プログラミング一般に言われていることですが、早すぎる最適化はだいたい悪です。早すぎる抽象化も割と悪です。geekなプログラマー (ハッカー) なら超イケてる最高にcoolなコードを書きたくなる気持ちは分かるんですが、最高にcoolなコードは動かすまでが結構大変です。特に自分はC言語の初心者なので、変に気張らずに愚直に動くコードを書くことを意識しました。

compilerbookにも、早すぎる最適化をしないという観点で、freeしないという方針だったり、即値を一度スタックに入れるという方針だったりが取られています。まず動くコードを書いて、必要なら最適化しましょう。(今回最適化が本当に必要になっちゃって困ってるんですけどね～～～～)

テストを良い感じに書く

今回はTDD (テスト駆動開発) 風に開発していて、テストを書いてからそれを満たすようなコードを書くという感じで開発 (機能追加) を行っていました。コンパイラというのは入力と出力が文字列としてハッキリしているので、非常にテストがしやすいです。テストはバグ防止 (デグレ防止) という観点でも非常に重要なのですが、モチベ的な観点でも重要だと考えています。

バグ防止という観点では普通にdebuggabilityを高めるためにコンパイルから実行までのどの段階でエラーが起きているのかというのを示すようにしました。テストのステップは次のような流れを踏みます。

(自作コンパイラによる) コンパイル
(Clangによる) LLVM IR → オブジェクトファイルの変換
(Clangによる) オブジェクトファイルの結合 (リンク)
実行ファイルの実行
実行結果の比較

エラーの半分ぐらいは自作コンパイラのコンパイルで、もう半分ぐらいはオブジェクトファイルへの変換で起きました。実行ファイルが実行できなかったり、実行結果が違ったりすることもたまにあったんですが、あまりなかったです。

さらにモチベ的な観点で言うと、テストが通ると嬉しいです。え？それだけ？と思うかもしれませんが、テストが通った時の演出を付けておくと、楽しいです、かなり。ボクはそこまで凝った感じではなく、✅を表示するようにしました。これだけでも結構楽しさが増すのでオススメです。

感想

Q. C言語初心者がCコンパイラを作ろうとするとどうなるのか
A. 疲れる、でも学ぶものは多い

おわりに

いかがでしたか？Cコンパイラ制作はC言語の練習としてもちょうどいいことが分かりましたね。ぜひみなさんもCコンパイラ制作をやってみましょう！

明日は @kenken @MTECH22 @comavius の記事が出ます！おたのしみに！

おまけ

セキュリティキャンプというイベントで「Cコンパイラゼミ」というのがあるのですが、受講生が頑張っている中ボクも必死に開発していました。結局完成しなかったけどな！！！ (完成した)

みなさんがセキュキャンに行っている間、ひとりセキュキャンと称してCコンパイラをもくもく作るのであった (そろそろ完成させたいよ～～) pic.twitter.com/s6dsZU9b8p
— しーぴー 🍀 (@__cp20__) August 15, 2024