自作したRISC-V向けCコンパイラでセルフホストまでこぎつけた

低レイヤを知りたい人のためのCコンパイラ作成入門

まさに低レイヤのことが分かっておらず、以前から気になっていたこの本。取り掛かってみたところ思いのほかスイスイ進められて、勢いに乗ってセルフホスト（自分が書いたコンパイラで自分自身をコンパイルするところ）までいけたので記念に書いておく。正確には C コンパイラのサブセットです。

GitHub - motemen/mocc

全体的な進め方は、

• 上記の本の通りに進めていく。
• それ以降は自作の 8queen が普通に書けるように機能を強化。
• それ以降はセルフホストを目標に進める。
  • プリプロセッサやリンカは作らず、C からアセンブリまで。

という感じ。自分は手を動かさないと進んでる気がしないので、まずは書いてみつつわからない所があれば調べる、というスタンスでいく。

あと、せっかくなので RISC-V の勉強もしたかったのでこれ向けに書く。なので実行はエミュレータ上ということになっている。機械と会話できてる感は結局少ないので、実機がほしいところだ。

よく参考にしたのは:

• riscv-elf-psabi-doc/riscv-cc.adoc
• N1570 April 12, 2011 ISO/IEC 9899:201x
• https://inst.eecs.berkeley.edu/~cs61c/fa17/img/riscvcard.pdf
• https://www.cs.cornell.edu/courses/cs3410/2019sp/schedule/slides/10-calling-notes.pdf

とか。

ちなみに GitHub Copilot を有効にしたら補完されまくってモリモリ書けたのだが、これはたぶん本家の 9cc や chibicc 由来のコードなので細かいテクは自力では書いてないのであった。

一方でネタバレはいかんよな、と思って、やっている間はあまり他の挑戦者の記録を読んでなかったのだけど、セルフホストCコンパイラaqcc 開発記がとても面白かったので自分もログを思い出せるぶんだけ書いておくことにする。最初の方は Scrapbox にメモを取りつつやってたのだけど、なんとなくどう進めればよいかがわかるようになってからはコードを書く方に集中していたのであまりログがない。コミットログから思い出しつつ書く。

2022-10-XX (day 0)

• まず RISC-V の開発環境を用意した。Docker で Linux 環境を用意するつもりだったがコンパイルに時間がかかりすぎて試行錯誤もままならず、結局 macOS に Homebrew でインストールすることにした: https://github.com/riscv-software-src/homebrew-riscv。なんかいろいろと楽ちんである。
• spike /opt/homebrew/opt/riscv-pk/riscv64-unknown-elf/bin/pk <program> のようにすると実行できる。
• この際どうも stderr への出力も stdout に出てる気がする。
• あと最初に "bbl loader" と出るのも消せなそうなんでなんとかする。
• なんだかんだでいちおう Ubuntu の devcontainer も用意したけど、結局 macOS でやるのが早くてそちらでしか書いてない。今も壊れている。

2022-10-27 (day 1)

• とりあえずコード 42 で終了するプログラムを作るらしい。
• なるほどコンパイラを作るって Hello, world からやるのかと思っていたけど最初はここからなのか、と道程を思って興奮する。
• とはいえそもそもアセンブリがまずわからないのでコンパイル結果をばらすところから始める。gcc -S でアセンブリが出力できることを知る。このときは使いこなせてなかったけど、のちのち Compiler Explorer を多用するようになった。
• そしてスタックがわからない。正確にはアセンブリでどう書くのかがわからない。このへんは最終的に Calling Convention をキーワードに、大学の講義資料などをあさってなんとなく掴んでいった。
• RISC-V の ISA (Instruction set architecture) には pop ã‚„ push みたいな便利なものはないので自分で書く。
• とりあえずスタックマシンができればスムーズで、この日は 比較演算子 あたりまで進む。
• 最初の数コミットだけかっこつけて英語で書いてたが、自分のためのプロジェクトなので日本語で書くことにした。

2022-10-28 (day 2)

• ローカル変数を実装。スタックがなんとなくわかってきた。いよいよメモリに値を書き込めるとなると不思議な感じだ。
• 制御構造を実装。j でジャンプとかするとアセンブリ書いてる感じがする。構造化されたプログラムをフラットにしていく過程なのね。
• 関数呼び出しも作っちゃう。再帰をともなう階乗まで書けて感激する。
• スタックに push したものを pop し忘れることで実行時に例外が起きていてちょっとハマった。こういうときはアセンブリを一行一行読んでいく作業……。
• 関数とローカル変数 まで到達。

2022-10-31 (day 3)

• ポインタの実装。ここまでに左辺値を扱っていたのでその延長でアドレスを取得できるのはなるほど。
• mov rax, [rax] ã‚’ RISC-V でどう書くのか分からなかったけど、ld t0, 0(t0) のようだった。
• 配列にもトライ。C の配列って要はポインタのことでしょ？ という雑な理解をしていたが実装してみると難しい。構文解析時に a が配列変数だったら &a であるとしてみることにする。このコードはあとで捨てた。
• 配列周りでなんだかアドホックなコードが増えてきて嫌になってくる。
• ローカル変数がプログラム全体のスコープを持っていたのを関数スコープにする。

2022-11-01 (day 4)

• テストが一つでも失敗したら残りのテストが走らないようになっていたけど、それだとエンバグしている箇所がひとつしか見つけられないので全て走らせるように変更。具体的には TAP を吐いて prove に食わせるようにする。使い慣れた感じだ。
• 配列の実装を変更。a ã‚’ &a にしたときに、こちらの都合で生成した擬似的なノードであることをマークする。このコードも捨てた。
• 結局変数の評価時に配列だったら特別な扱いをするようにしたらしい。

2022-11-02 (day 5)

• グローバル変数を実装。LVar とほとんど同じ GVar が登場。データ構造も操作の関数もコピペで作る。せめてリストの操作だけでも同一にしたいと思うが、あまり込み入ったことをするとセルフホストが遠のきそうでできない（結局いまもできていない）。
• 関数の宣言とグローバル変数の宣言の構文解析が混ざって読みにくくなった。
• 文字列リテラルを実装。エスケープシーケンスとかを解釈せずにアセンブリに吐き出しても分かってくれる。それで疑問に思ったけどアセンブリの文字列リテラルの仕様はどこにあるんだ？
• ファイルからの読み込みを実装。これはコピペ。
• ステップ26: 入力をファイルから読む まで到達。

2022-11-03 (day 6)

• ステップ27: 行コメントとブロックコメント まで到達。ここから先は自分で目標を持ってやっていく。8queen と、セルフホストである。
• 8queen を動かすことにはあっさり成功。for の中で変数宣言できないし、変数宣言と同時に代入もできないし、文字リテラルがないので putchar() に数字を渡さなきゃいけないし、とひどいもんだがちゃんと動いている。なかなか愛着が湧いてきた。

2022-11-04 (day 7)

• 1テストずつコンパイル→実行していた test.sh をひとつのプログラムである test/test.c に移行。自分のコンパイラがある程度は信頼できるようになってきたのでこういうこともできる。どこが壊れてるかわかんないのにテストをひとつのプログラムにまとめることなんてできないでしょ、と最初は思っていたものだけど。
• これも TAP でテスト結果を出力するものである。
• 8queen が通ってホッとしたので、ちょっとリファクタリングする。
• 変数がスコープとして関数名を持っていたのを、Node にローカル変数を持たせるように変更。スコープという概念がここでまともな形で登場する。
• セルフホストに必要な項目を書き出す。

2022-11-06 (day 8)

• グローバル変数を初期化可能に。定数値の計算のコードを書くのは面倒だな？
• ローカル変数も初期化。こちらは代入がなされたかのようにノードを生成する。
• break を実装。親 while に対応するラベルに j する。break LABEL があったらもっと面倒だったに違いない。
• あわせて、構文解析時にスコープを push/pop するようになる。

2022-11-07 (day 9)

• continue を実装。
• 自分自身をコンパイルさせようとすると最初に引っかかるところだからだと思うが、構造体に手を付けていく。parse_type() がめちゃくちゃになっていく……。
• 構造体のメンバは LVar を再利用できそう。オフセットの計算がちょっと違うようだが。
• というか構造体のメンバのアラインメントは ABI で定められていないの？

2022-11-08 (day 10)

• 9cv という名前を mocc に変更した。文字の高さが揃って、可愛らしい。
• LVar, GVar ã‚’ Var に一本化。
• struct A; みたいなのを許す。
• 単項 ! に対応。
• for (int i = 0;;) と宣言ができるようにした。for がスコープを持つようになった。
• あわせて、codegen 時に for が始まったときにスタックを積むようになった。これは失敗だったのであとでやめた。

2022-11-09..11 (day 11..13)

• enum に対応。enum で宣言されたアイテムは、その後の登場では定数値に置き換えるような実装。
• typedef に対応。TY_INT ã‚„ TY_ARRAY、TY_STRUCT と並んで TY_TYPEDEF という類を作る。
• 可変長引数に対応。va_start の存在が謎すぎて実装できる気がしなかったが、簡単な場合についてはなんとなく分かった。スタックの根本のほうに引数たちを積んでおき、va_list ap はそこへのポインタになっているというわけだ。va_start の呼び出しだけ特別に処理をすることにする。
• switch を実装してみる。switch の側から case を見つけに行ってるが、これ逆のほうがいいなあ。
• extern に対応。

2022-11-16..17 (day 14..15)

• ++ に対応。後置はやや面倒。
• extern が Type の性質のように実装していたのを Var のものに変更。
• ローカル変数のスコープの管理のため、スコープごとにスタックポインタを移動していた (day 10) のが break などと絡むと複雑になりすぎるので、構文解析時にスコープを関数のスコープにマージするよう変更。
• break などのジャンプ先も、コード生成時に行っていたのを構文解析時にやるように変更してコード生成ではスコープをほとんど意識しなくていいようにした。
• 空の return; に対応。
• 一箇所でしか使っていなかった型キャストの実装をあきらめることにして、ソースコードから除いた。
• 構造体の初期化も勢いで実装する。

2022-11-18 (day 16)

• 関数の返り値の型をようやくチェックするように。
• ヘッダファイルにセルフホスト向けの関数や変数宣言を無理やり書いていく。-D__mocc_self__ したときは #include をせずに自前の定義を使うような形だ。
• この時点でセルフホストが達成できていそう。clang でコンパイルした mocc (stage1) でコンパイルした mocc (stage2) でテストが通るようになった。

2022-11-20 (day 17)

• このエントリを書いていたら break の実装がおかしかったのを発見したので修正。
• これで clang でコンパイルした mocc (stage1) でコンパイルした mocc (stage2) と、これでコンパイルした mocc (stage3) がまったく一致するようになった!!!

やってみて

• この本ではとにかくまずはすばやく最終的な結果を出すことを目指し、早すぎる抽象化をせずに進めていくスタイルを強調していて、その通りにするとほんとうに進むのでめちゃくちゃ気持ちがいい。
• 関数ポインタは未実装。あの奇怪な型宣言をどうパーズするのかを考えるとおもしろそうなのでやってみようかな。
• 写経成分も多めでかなり端折りながらではあったけど、なかなか達成感があるし、勉強になった。自分は手触りがないとよく理解できないタチなのだけど、ABI (Application Binary Interface) がなんなのかということが肌でわかった部分は大きい。あと関数呼び出しの引数を後ろから評価する処理系がある気持ちもわかった……。
  • メチャ昔に JavaScript の処理系を書いたときは、適当に作ったらダイナミックスコープが生じてしまってナルホドと思ったものだけど、やってみないとわからないというのはこういうことだ。
• あと VSCode + clangd のおかげで C を書く体験はかなり快適だった。15年前にバイトで書いてたころとはぜんぜん違う。
• このあとはぼちぼちコードを綺麗にしていくことをしつつ余生を過ごしたい。