自作Cコンパイラでセルフホストを達成した

記事の概要

最近書いていた自作Cコンパイラ「ycc」がセルフホストを達成しました。
これは後述するcompilerbookを読んで作ったものです。

まだまだ実装は足りていませんが、そろそろアウトプットしないとキツくなってきたので諸々をブログにまとめます。

github.com

Cコンパイラを自作し始めた経緯

最近『コンピュータシステムの理論と実装』（以降、nand2tetris）という本を完走してしまい空き時間ができたので、 やりたいことリストに入っていた「Cコンパイラ自作」をやることにしました。

yuiki.hatenablog.jp

いわゆるコンパイラの動作原理は利用者観点でざっとは理解していて、かつnand2tetrisでJackという教育用言語のコンパイラを作ったことはありました。
ただし、実際によく使われている言語の、実際によく使われているアーキテクチャ向けのコンパイラというものは作ったことがありませんでした。

そんな中、Rui Ueyamaさんが書かれた『低レイヤを知りたい人のためのCコンパイラ作成入門』（以降、compilerbook、本）というオンラインブックの存在を思い出しました。
この本はx86-64のLinux向けのアセンブリを吐き出すCコンパイラをステップバイステップで実装していくCコンパイラ自作入門書です。

www.sigbus.info

これを元にコンパイラを自作すれば、実際によく使われている言語の、実際によく使われているアーキテクチャ向けのコンパイラの動作原理を学ぶことができそうです。

また、8cc、9cc、chibiccといった自作Cコンパイラを作られているRui Ueyamaさんのコンパイラ開発手法も学ぶことができそうです。

と、いろいろ書きましたが自作Cコンパイラ、面白そうです。
ということでやってみることにしました。

自作コンパイラ「ycc」

yccはLinux向けのx86-64のアセンブリを吐き出すCコンパイラです。
とはいえコンパイラできないコードも多く、その観点では実装が現時点では不十分です。

一方で、セルフホストを達成しています。
つまり、自作コンパイラで自作コンパイラをコンパイルできます。

また、"ccでコンパイルした第1世代コンパイラ"でコンパイルした第2世代コンパイラと、 その第2世代コンパイラでコンパイルした第3世代コンパイラのバイナリが一致することも確認しました。

参考程度にセルフホストまでかかった日数*1を数えてみたところ、18日間でした。
研究も落ち着き、時間が十分に取れました。

なおyccはcompilerbook上のコードや設計を元にしているため、それに多くの影響を受けています。

実装の方針

1. コンパイラで使うCの機能は特別制限しない

例えばセルフホストを最短で実現しようとすると、コンパイラ開発で利用するCの機能を最小限に抑えるとよいと考えられます。
ただし、compilerbookはそうなるようには書かれておらず、一般的に用いられるCの機能を利用しています。
そこで本に則り、使う機能は特に制限しないようにしました。

一方でセルフホストを達成した感想としては、セルフホストをいち早く達成するために使う機能を制限するというのも方針としてはよいかもです。
次にfrom scratchするとしたらそうするかもしれません。

2. 本に書かれているコードは真似する、書かれていないところは1から実装する

本のステップ11以前はコードが本文に多く書かれてあります。
このコードを見ずに実装しても良かったのですが、Rui UeyamaさんがどこかのYouTubeの動画で「本に記載されているコードは読むこと前提で本を書いてある」のようなことを仰っていました。
そこで今回はそれに従い、本に書かれているコードは1度真似することにしました。

一方で、ステップ12以降は執筆中で本文にはコードは少なく、指針のみ書かれています。*2

そこで、ステップ12以降は本文に書かれていることを理解し、既存のコードは見ずに作っていくことにしました。
ステップ11以前でイテレーティブにコンパイラを作っていく流れを理解したので、後は自分でも作っていけそうでした。

本が終わった後（ステップ29以降）の進め方

現時点では本を終えても、セルフホストは達成できません。
そこで基本的には以下の3つを参照して実装を進めました。

本を読み、コンパイラを作ってみて得られたこと

たくさんありますが、例えば以下のようなものです。

C言語

C言語の一部のシンタックスやセマンティクスが何故このようになっているかなども自分の中で推測することもできました。
個人的には、Cはコンパイラ開発者に優しい言語になっていると感じました。
より現代に開発された言語では、コンパイラやランタイムが頑張ってくれているお陰でその上でコードを書くプログラマが比較的楽ができているということです。

広く使われている他の言語のコンパイラを作ったことがないのでわかりませんが、Cはそういう意味でもコンパイラを作りやすいのではないかと感じました。

大変だったところ

大変だったところもたくさんあります。
例えば以下のようなものです。

  • 関数呼び出し時のスタックポインタのアラインメント
  • 可変長引数の実装
  • 左辺値と右辺値の取り扱い
  • C言語
  • バグ修正

構造体の実装は見積もりよりも早く実装できました。まだ不十分ですが…。

C言語

今回はCでCのコンパイラを書きました。 コンパイラを書く上で思ったよりCも悪くないな*3という気持ちも得ましたが、バグも多く生んでしまいました。
（これはCの経験不足というのもありますが）

バグ修正

最後の方は基本的にはバグ修正にほとんどの時間を費やしました。
特に第2世代のコンパイラで第3世代のコンパイルが通らないバグ（ミスコンパイル）を修正するのが難しかったです。

修正にあたってはccでコンパイルしたコンパイラ（第1世代コンパイラ）と第1世代コンパイラでコンパイルしたコンパイラ（第2世代コンパイラ）の一部を組み合わせることで、
どのCプログラムがバグっているのかを推測していきました。

ただし、自分の中でミスコンパイルのデバッグをうまくやる手法を編み出せていません。
結局は出力されたアセンブリコードをかなり読みました。
エスパー力は高まったと思います。

ミスコンパイルの原因は大体実装不足だったので、実装できていないポイントをしっかり認識しておいてそれを元にコードを読むのと、テストを詳細に書くことが重要そうです。

どのようにバグを修正していったかというのは結構面白いと思うので、いつか形にしてみても良いかもですね。

今後

他の人が書いたCのコードをビルドできるようにしてみたいです。
現状はセルフホストできただけなので、実装しなければいけないこともたくさんあります。
例えば、現時点ではLinuxに入っているヘッダファイルがまともに読めません。

また、プリプロセッサの実装はひとまずスキップしていて現在はcppを利用しているので、そこの依存を剥がすのもやりたいです。

関連

compilerbookのココが好き

今回はcompilerbookを読みコンパイラを作りました。
少し話題は逸れますが、compilerbookの良かったところについて書いてみようと思います。

主観では以下の3点が良かったです。

  1. イテレーティブな開発スタイル
  2. 割り切り
  3. コラム

イテレーティブな開発スタイル

一般的にコードをコンパイルする際は大きく以下のような流れで処理が行われています。

  1. プリプロセス
  2. 字句解析
  3. 構文解析
  4. 意味解析
  5. コード生成

例えばnand2tetrisではコンパイラをこのステップ毎に作っていきました。
この手法の場合、コード生成に行くまでにかなりの時間がかかってしまいます。
そこでnand2tetrisでは構文解析の結果がXMLで提供されており、テストが楽でしたが今回はそうもいきません。

一方で、compilerbookではイテレーティブな開発スタイルが採用されています。
つまり巨大な仕様をステップ毎に作っていくのではなく、最小限の仕様を定めそれに基づき各ステップのコードを作ります。
そして、そのCのサブセットをどんどん大きくしていきます。

こうすることで序盤からコード生成ができるので、テストがしやすいです。
なによりすぐに「コードが動く」ので達成感が比較的簡単に味わえます。

割り切り

本では多くの割り切りが行われています。
例えば、壊れた入力（プログラム）のハンドリングが不足していたり、仕様のエッジケースに対応できていなかったりする点です。

ただしこれは良いことで、イテレーティブに作っているので後で改良していけばよいだけです。
複雑なものを作っていくためにはこういった考えが必要だと思います。

コラム

本では要所要所にコラムが書かれています。
このコラムが面白く、また著者の知識量に圧倒されます。

面白すぎて先に読んでしまいがちでした。

並行してインプットしたもの

また、並行して低レイヤ周りの知識をインプットしていたのでそれも紹介します。

Cコンパイラ作成集中講座（全14回）

compilerbookの著者であるRui UeyamaさんがYouTubeでCコンパイラ作成の集中講座を実施しており、そのアーカイブを閲覧しました。
内容に関してはcompilerbookを進めている人からの質疑がメインです。

質疑では本を進める上で役立つことが多く話されていて、参考になりました。
また、ゲストの回もあり面白いです。

www.youtube.com

その他 Rui Ueyamaさんの動画

集中講座の後に出ている4本の動画もおすすめです。

例えばミスコンパイルを修正する流れや、 www.youtube.com

chibiccの設計について知ることができます。 www.youtube.com

パタヘネ本

『コンピュータの構成と設計 MIPS Edition 第6版』（パタヘネ）がメインで扱っているのはMIPSですが、Kindleで半額だったので買って読んでいました。

コンピュータの構成と設計 MIPS Edition 第6版 上 | David Patterson, John Hennessy, 成田 光彰 | 工学 | Kindleストア | Amazon

上巻はざっと読みましたが、下巻はまだ読んでいる最中です。

まとめ

いろいろ書きすぎてうまくまとまりませんでした。

これまでC言語を書くことは多くはなかったですが、Cは私が人生で最初に取り組んだプログラミング言語でした。
そう言った意味でCコンパイラを自作するというのは非常に楽しいものでした。

趣味プロジェクトとして、今後も余暇に進めていきたいと思います。

あわせて読みたい

yuiki.hatenablog.jp

yuiki.hatenablog.jp

yuiki.hatenablog.jp

*1:これまで1度でもコミットした日

*2:とはいえこの指針に大きく助けられました。

*3:これはcompilerbookはデザインとしてメモリ解放を行っておらず、私のコンパイラもそれに従いメモリ管理のことを忘れられたというのも起因しているはずです。