Cコンパイラを自作してセルフホストしました

タイトル通りなのですが、CでCのコンパイラを書いてとりあえずセルフホストできるところまでできたのでブログにこれまでやったこととかを残しておこうと思います。作ったものは以下のリンクから見れます。

どうやって作ったか

これをつくろうと思ったきっかけとして、まず低レイヤを知りたい人のためのCコンパイラ作成入門があります。このサイト自体は未完成らしいのですが、初めのほうでコンパイラ作成の基本的な部分(トークナイズ、パース、コード生成)についてわかりやすく解説しており、コンパイラにそれほど詳しくなくてもコンパイラを作り始めることができます。

このサイトの最初の方で自分のコンパイラが正しく計算結果を出力するのを目にして、さらに段々機能を付け加えていくとだんだんC言語に近づいていくのがとてもおもしろかったため、楽しくつづけることができました。

蛇足ですが(コンパイラ作成とは直接は関係ないですが)、この本で推奨されているインクリメンタルな開発の仕方は常に完成した状態で開発を進めることができるのでいきなりハードルがあがるということがなくてよかったです。

上に書いたように、このサイトでは途中でおわっています。この時点ではまだセルフホストはできないため、セルフホストするためにはさらに機能を追加する必要があります。さらに機能を追加する際には

The syntax of C in Backus-Naur form を見て, 追加したい機能に対応するBNFを確認して
Compiler Explorerでその機能はどのような使い方が許されるのかを確認して
実際にコードを書く

ということを繰り返していきました。ちなみにセルフホストまでに必要な機能としては(自分の場合は)

構造体定義 .,->
++var,--var,var++,var--
void,bool
break,continue
switch ~ case ~ default ~
enum
charのリテラル, エスケープシーケンス
%,<<,>>,|,&,||,&&,! と三項演算子
+=,-=,*= 系
typedef
可変長引数
(簡単な)キャスト

などでした。ちなみに今のところマクロ展開とリンクはサポートしていないため

gccにマクロ展開してもらう
マクロ展開したものを自分のコンパイラでコンパイルする
それらをgccでリンクしてもらう

のようにしてセルフホストしました。また最適化等は全く行っていません。

f:id:hedwig1001:20220315102938p:plain — セルフホストしてhcc2とhcc3が同じであることを確認した

面白かったポイント

なんといっても自分の書いたコードでコンパイルできるものが増えていくのを見るのがとても面白いです。はじめはただの計算しかできなかったのにfor文, 配列, 構造体などと追加していくとコンパイルできるコードが増えて、だんだん自分のコンパイラが成長しているのを感じることができます。成長過程をリンクで貼っておきます。

セルフホストできたときの感動もひとしおでした。

つらかったポイント

セグフォ

これはCで書くなら仕方ないかもしれないですが, ヌルポインタにアクセスしようとするとセグフォします。できるだけそれは防ぎたいのでエラー処理はしますが、完全に防ぐことはできないためセグフォすることがあります。そのためエラー出力を適当な箇所に入れて、セグフォしても「ここまでは正しく動いているはず」ということがわかるようにしました。

またコンパイラを書いているのでセグフォは自分の書いたコンパイラがコンパイルしたアセンブリを実行しようとした時も起こる可能性があります。こうなったらまずアセンブリを見てどこでセグフォしているか確認します。これでわかればokですがわからない場合はgdbで実行してどの行でセグフォしているか確かめてコードを修正していました。

可変長引数

構造体やenumの追加も比較的スムーズにできたのですが、可変長引数の実装にすこし苦戦しました。そもそも va_list,va_start とかは stdarg.h で定義されていると思っていたのですが、これらの実態は __builtin_hogehoge というやつらでこれはコンパイラが実装するものだとわかりました。なのでこれらを実装しなければなりません。そのために

などを参考にしました。これらをみてもよくわからないところは前述のCompiler Explorerをつかってアセンブリを実際に出力してみて、どうなっているか確かめたりしました。vfprintf() を使っているので gcc と互換性があるように実装する必要もあると思います。

また関数呼び出しで引数の数が6個以下(すべて整数orポインタ)だと引数はレジスタにセットするのですが、6個より多いとスタックにpushします。自分のコードでは7個以上の引数を持つ関数呼び出しがあったため、これもサポートしました(可変長とは関係なかった)。

知見

コンパイラ作成の過程でいろんなことを知りました。

C言語について詳しくなった

コンパイラをつくるにあたって, どういう書き方が許されてどういう書き方が許されないのかを考えることになります。そのため, C言語についての知識が増えます。たとえば

int a=1,b=2;
a,b = b,a;

という書き方はCでは合法なのですが, これはPythonの時のように a,b をスワップするという意味にはなりません。Cではexpression(正確にはassign)をカンマ区切りで何回か並べたものをexpressionとしています(くわしくは The syntax of C in Backus-Naur form を参照してください)。そのため上のコードは a; b = b; a; を並べたものと同じです。なのでスワップではなく a,b の値は変化しないということになります。

またCの構文解析がしにくいというのも身をもって実感しました。たとえば

int a;
int f(int x) { ...

の二つを考えると int f(.. のカッコにくるまで変数の定義をしているのか, それとも関数の定義をしているのかわかりません。できるだけ最初の1文字を読んだ時点でなにをパースしようとしているのかはわかると楽です。Pythonは def ... ですし, Goは var ... ,func ... ですし Rustも let ..., fn ... でこれが考慮されているらしいことがわかります。Cは昔の言語なのでしょうがないですが, Goは構文解析しやすいようにつくられているという話もなるほどなと納得できました。

アセンブリをかけるようになる。

あまりアセンブリを書いたことがなかったため, 実践的低レイヤプログラミングをみてちょっと勉強してから始めたのですが, コンパイラを作っていく過程でアセンブリを生成することになるのでアセンブリの知識がつきます。

結局アセンブリは

データを動かすmov
計算する add,sub,cmp
ジャンプする je,jmp

の3種類がほとんどで、これらを組み合わせてプログラムは動いているのだなとわかりました。

f:id:hedwig1001:20220315111103p:plain — アセンブリを見てデバッグ!

プログラムが実行される様子が(なんとなく)わかる

関数呼び出し, どのように配列アクセスしているのか, 構造体はどのようにメモリ上にのっているのか, 構造体の->は何をしているのか, 参照を渡すとはどういうことか, ポインタとはなんなのか, etc. についてきちんと理解することができます。理解しないとコンパイラが書けないので。いままでブラックボックス化していたものをひとつづつ明らかにしていく感じがありました。

いまはまだ何に役に立つかはわかりませんが, 省メモリなプログラムを書いたり, 効率の良いプログラムを書いたりするのに役立てられれば良いなと思っています。

展望

セルフホストはしましたが, 実はまだ結構サポートしていない機能や中途半端な実装になっているところがあります。

structの引数, 値渡し, 初期化式
const-expressionをコンパイル時にきちんと評価する
unsigned系
short,long,_Bool
staticの関数をファイルスコープにする
enum,typedef,local variableの同じスコープで同じ識別子となるものを宣言できないようにする。
関数ポインタの型をきちんと実装する。
#define #include とかのマクロ展開
浮動小数点数

などです。これらの機能も追加していけたら良いなと思っています。

おわりに

コンパイラ作成は面白いと思うので, 低レイヤを知りたい人のためのCコンパイラ作成入門読んでやってみてください!