こんにちは、21Bのseasonです。この記事はtraP夏のブログリレー3日目の記事です。
自作Cコンパイラでセルフホスト達成しました。
リポジトリ: https://github.com/season1618/c-compiler/tree/main
実際にどうやって作るかを書くと長くなるので、ここでは経緯とか完成までの流れとかを書こうと思います。一応開発メモは以下に上げておきました。
開発メモ: https://github.com/season1618/note/blob/main/cs/c-compiler/index.md
経緯
大学の講義でプログラミング創造演習というのを取りました。どういう科目かというと、自分で目標を設定してプログラミングに関することを勉強したり、何らかの制作物を作って発表するというやつです。講義の時間は中間発表と最終発表以外はすべて自由時間です。毎週進捗報告をする以外に何かすることはありません。
他の人は競プロやCTFの勉強をしてる人もいれば、実用的なソフトウェアとかゲームアプリを作ってる人もいました。自分は特にそういったアイディアはなかったんですが、Cコンパイラをこの機会に作ってみることにしました。一応情報系ということで人生で一回は作ってみたいなあと思っていたので。
コンパイラとは
一般的には、人間が書いたソースコードはまずアセンブリに変換され、次にオブジェクトコードに変換されます。そして一つ以上のオブジェクトコードが結合されて実行ファイルになります。この内、ソースコードをアセンブリに変換する工程を(狭義の)コンパイルと言い、変換するプログラムを(狭義の)コンパイラと言います。CコンパイラというのはC言語のソースコードをアセンブリに変換するコンパイラです。
セルフホストとは
今回、自分はC言語でCコンパイラを書きました。CコンパイラはC言語をコンパイルするプログラムなので、もちろん十分な機能に対応すれば自分自身をコンパイルすることが可能です。これをセルフホストと言います。コンパイラがセルフホストできるというのはある程度しっかりした量の機能を備えているという証であり、自作する上での一つの目標になります。
なぜコンパイラを作るのか
本能です。
コンパイラ自作で得られる知識
大体こんな感じだと思います。
- C言語
- コンパイラの動作
- 低レイヤでの挙動
C言語を書いているだけだとその場で動けば満足してしまうので正確な知識は身に付きません(別に困らないけど)。コンパイラを作るにあたって言語仕様を読んで実際に構文解析してみることで、言語がどのように設計されているかを知ることができます。
コンパイラの動作や低レイヤでの挙動を知ると高級言語がどういう役割を果たしているのかが分かってきます。例えば、ローカル変数というのはアセンブリでは消えてしまう概念です。本来、変数は計算に必要ないものなのですが、人間に分かりやすいように高級言語には用意されているのです。
プログラミング言語や低レイヤに詳しくなれるのはもちろんですが、単純に自分で書いたプログラムが大量のアセンブリを吐き出すのを見るのも面白いですし、それらがすべて意味を持って動作しているということに素朴な感動があると思います。
まず初めに
低レイヤを知りたい人のためのCコンパイラ作成入門(以後compilerbook)を読みます。Cコンパイラ作るなら何も考えずにこれ読めば良さそう(コンパイラ自作の本は読んだことないので分からない)。
変数、関数、制御文、型、ポインタなど基本的なところは大体解説されてます。これだけでも例えば、フィボナッチ数を再帰で計算するプログラムとか色々書けるので楽しいです。
タイトルにある通り低レイヤ(CPUとかメモリ)の動きを理解しながらコンパイラを作れるのでお勧めです。最初の方はとても丁寧に解説してあるので、コードをほぼそのまま書くだけでどんどん進みます。少し進んでいくと詳細は省かれるので自分で補完する必要があります。あまり詳細に書いてあると自分で考えなくなって自作感が薄れるのでそのぐらいが丁度良いのかなあと思いました。
分からない箇所があったり、他に良い書き方がないか知りたいときは他人のコードを参考にしました。compilerbookを読みながら実装されたCコンパイラはたくさんあると思うのでgithubを探してみると良いと思います。自分はtraPの先輩が書いたコードを結構読んでました。
compilerbookの他にはこういうのを読むと勉強になると思います。
- AMD64 Architecture Programmer's Manual: AMD64 Architectureの箇所。特にVolume 1: Application Programming
- System V Application Binary Interface AMD64 Architecture Processor Supplement
- N1570: C11言語仕様の最終草稿
compilerbookで詰まったところ
compilerbookを読んでいるときに少し詰まった点を挙げておきます。
intのサイズ変更
compilerbookではintのサイズを8バイトとして読んでいました。これを後に4バイトで読むように変更するのですが、そこで少し勘違いをしていたことに気付きました。
メモリへのアクセスはメモリ番地だけを指定するのではなく、その番地から何バイト読むという風に指定します。例えば8バイト読むときは(intel syntaxなら)QWORD PTR [rbp-offset]
という風に指定します。しかし単純に[rbp-offset]
と指定しても8バイト読むことになっています。またスタック操作もデフォルトでは8バイト単位で行われるので、メモリ上のデータは必ず8バイト単位でしかアクセスできないものと思ってしまいました。
ちなみに8バイトより小さいデータ型に対応すると関数呼び出し時にスタックアラインメントを調整する処理も変更することになります。自分は、ローカル変数の確保領域をサイズの総和ではなく、それを16の倍数に切り上げたものにし、かつスタック操作を常に8バイト単位で行うようにしてアラインメント調整の変更をさぼりました。が、この時に何かバグって少し手間取りました。
上のように、データサイズを途中で中途半端なものに変えると色々と変更する点が出てきて、アラインメントが崩れてバグりやすくなるので、プログラムが小さいうちにintを4バイトとして読んでおいた方が良いかもしれません。
配列の実装
int a
の値はDWORD PTR [rbp-offset]
という感じになりますが、int a[4]
でa
の値はrbp-offset
になります。配列の先頭のアドレスはメモリに格納されているものではなくて、アドレスそのものの値(コンパイラが持っている情報)なのでちょっと混乱しました。
compilerbook読了後
compilerbook読み終わってからもやることはほとんど変わりませんでした。追加した機能は以下の通りです。
- char, int以外の基本型
- 構造体・列挙型
- typedef
- 足りない演算子や制御文
- 静的スコープ
辛かったところ
モチベ低下
最初の方はスムーズに進んだんですが、途中で少し飽きました。試験終わって、ICPC終わって、ISUCON終わって一段落したらまた回復したので良かった。
開発スピードの低下
モチベはあるんですが、プログラムを変更するのにどこから始めれば良いか迷うので、初期のようなスピード感はなくなってきます。プログラムが巨大化してくると心理的にも物理的にも変更が難しくなってきますね。機能を追加するのに少なくない箇所を破壊する必要があるので大変です。gitの便利さを実感した。
セグフォ
C言語で書いてたんですが、ポインタ使いまくってるので人生で一番セグフォしました。実行時エラーはほぼすべてセグフォでした。
バグが取れない
注意深く見るとできます。
どうしても取れない
一旦放置してグッと睨むと取れます。
自作コンパイラがコンパイルできない
頑張る
自作コンパイラでテストコードがコンパイルできない
自作コンパイラが間違っている場合と用意したテストコードが間違っている場合があるので少し大変です。
自作コンパイラでコンパイルしたテストコードが上手く実行されない
自作コンパイラが間違っている場合と用意したテストコードが間違っている場合があるので少し大変です。テストコードのアセンブリを読みました。
自作コンパイラで自作コンパイラがコンパイルできない
頑張る2
自作コンパイラで自作コンパイラをコンパイルしたものでテストコードがコンパイルできない
自作コンパイラのアセンブリを読みました。自作コンパイラのアセンブリは容赦なくジャンプ命令が含まれてるスパゲッティコードなので非常に辛い。
自作コンパイラで自作コンパイラをコンパイルしたものでコンパイルしたテストコードが上手く実行されない
自作コンパイラで自作コンパイラをコンパイルしたものでテストコードをコンパイルして実行するとき、自作コンパイラで自作コンパイラをコンパイルする段階でミスってるのと、自作コンパイラで自作コンパイラをコンパイルしたものでテストコードをコンパイルする段階でミスってるのと二つ考えられるので、バグを突き止める労力が普段のn倍になります。もはや自分が何をデバッグしてるのか分からなくなってきます。
ちなみに
自分はデバッガを使ったことがないです。なのでアセンブリを直接読んでいました。デバッガを使うと、デバッグがしやすいそうです(それはそう)。
いかがでしたか?
少しでも自作コンパイラに興味を持っていただけたら嬉しいです。
明日はlogicaさんの記事です。お楽しみに。