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

2019-07-14
#compiler #binary

低レイヤを知りたい人のためのCコンパイラ作成入門（以降「低レイヤ」）を参考にして作り始めたCコンパイラがようやくセルフホスティングできるようになったので、 今までの経験をメモしておく。

リポジトリはこちら：https://github.com/tyfkda/xcc

動機

XV6という学習用OSをひとまず使えるものにしたいなぁと思っていて、Cコンパイラが動けばXV6上で開発できるようになるのでぜひとも動かしたいと思っていた。 しかし既存のソースだとCからアセンブリを出力するだけで、アセンブラやリンカはgccを使うとかしていることが多くて、そのままだと動かすのが難しいのではないかと思っていた。 「低レイヤ」もその方式なんだけど、それを直接バイナリを出力する方法で実装したらできるのではないかと、始めてみた。

進め方

「低レイヤ」では最初に整数１個をコンパイルできるだけというミニマルな状態から始めて、徐々に拡張していくという手順で進んでいく。 加減算、乗除算、ローカル変数、関数呼び出し、関数定義、という具合に少しずつ処理できる構文を増やしていく。 記事の前半は丁寧に解説されているので、基本的には手順通りに進めていけばいい。 後半はかなり飛ばし気味なので、自分で内容をちゃんと理解して進めていく必要がある。

サイトは内容が随時更新されているみたいなんだけど自分が読んだ時点ではグローバル変数の初期化まで書かれていた。 その状態だとまだセルフホスティングできなかったので、そこからは自前で実装していった。

こまごまと

出力するバイナリ形式

「低レイヤ」ではx86-64アセンブリ言語のソースをテキスト形式で出力して、gccでアセンブル・リンクして実行ファイルを作っている。 こちらの目的は実行ファイルを直接出力して動かせるようにすることなので、変更する必要がある。

LinuxではELF形式というものが使われている。 XV6も同じくELFなのでどちらでも動かせて都合がよいため、ELFを吐くようにした。

ELFはエルフヘッダとプログラムヘッダに加えてマシン語バイナリを出力すればよい。 ELF64形式に関しては ELF64を動的に生成してHello World や ELF64でQuine で試した。

C言語に対応するアセンブリを確認するには gcc -S で（gcc -S -fomit-frame-pointer -fno-asynchronous-unwind-tables ,foo/foo.c）やCompiler Explorerが便利。 アセンブリに対応するバイナリは、gcc -c foo.s && objdump -S foo.o で調べられる。

バイナリの出力はx86の命令ごとにベタにマクロを定義してやった。 例えば、

#define MOV_RAX_IND_RAX()  ADD_CODE(0x48, 0x89, 0x00)  // mov %rax, %(rax)

ADD_CODE ではマクロの可変長引数 __VA_ARGS__ を使ってデータを埋め込む：

#define ADD_CODE(...)  do { unsigned char buf[] = {__VA_ARGS__}; add_code(buf, sizeof(buf)); } while (0)

左辺値、参照

Cコンパイラを実装するにあたって、難しいのではないかと思っていたポイントが左辺値だ。 左辺値は単純なローカル変数の場合もあるし、ポインタ値を * で修飾したポイント先や配列に添字でのアクセス、構造体への.やそのポインタへの->など、いろいろな場合がある。 参照も上記のようなものに対して&でアドレスを取れるようにする必要がある。 このあたりをどうやって実装するかはなかなかやっかいなのではないかと思っていた。

「低レイヤ」ではローカル変数を追加するする際に左辺値を説明している（#左辺値と右辺値）：

このような正当な式と不正な式の区別はどのようにつければよいのでしょうか？

その問いには単純な答えがあります。Cにおいて代入式の左辺にくることができるのは、メモリのアドレスを指定する式だけです。

左辺値がメモリのアドレスを指すものとして、式の評価時にはそのアドレスを値としてやる。 代入は左辺値のアドレスに値を格納するというコードを生成する、と共通化できる。

型の表現

C言語ではintなどのプリミティブな型以外に、配列やポインタで修飾することができる。 そうした型をどうやって表現するか、同じ型かどうかの判定方法を考える必要がある。

「低レイヤ」では型を表すType構造体を

struct Type {
  enum { INT, PTR } ty;
  struct Type *ptrof;
};

と定義している。 ptrofがType*を再帰的に参照するようになっていて、これによってポインタ、ポインタのポインタ、…という具合にあらゆる型を表現できる。

同じ型かどうかを判定するには、ty が同じかどうか、同じでPTRだったらptrofの内容が同じかどうかで判定できる。

配列を追加するには、tyに配列型を表す定義（ARRAY）を追加してやればよい。 ティップスとして、C言語では配列型からポインタ型への自動変換があるので、配列用に新たにメンバを用意するんじゃなくポインタ用の ptrof と共有するほうが都合がいい。

初期値付きグローバル変数

int foo = 123; という具合に、変数の宣言時に初期値を与えることができる。 ローカル変数の場合には実行時に処理を行うことができるので、通常の代入処理をしてやればよい。

しかしグローバル変数や静的変数の場合は起動時に初期化を行うわけではなく、コード生成時にバイトの配置まで確定させておく必要がある。 またローカル変数の構造体のメンバに初期値が与えられてない場合には不定値が入っていてよいが、グローバル変数の初期値は0クリアされている必要がある。

C99の構造体の初期化子で{.member=123}などと指定できたりする（Struct and union initialization - cppreference.com）。 対応しなくて済むなら済ませたいところだけど、共用体の場合には使えないと最初のメンバしか指定できなくなってしまうので、対応する必要がある。

またグローバル変数の初期化でポインタも扱いたかったので、それも考慮する必要があった。

プリプロセッサ

C言語では定数やマクロなどに加えて標準ライブラリヘッダのインクルードも使用するので、コンパイラだけじゃなくプリプロセッサも作る必要がある。

「低レイヤ」にはプリプロセッサについては書かれてない。 そこで9ccのソースを見てみる。 tokenize内でpreprocessを呼び出して処理しているので、どうやらトークナイズ後のトークン列に対して処理しているらしい。 「プリプロセッサ」というぐらいだからコンパイラとは別の実行ファイルとして動作させるものだろうと思っていたんだけど、gccなどでも内蔵されているものらしい（要出典）。

9ccからプリプロセッサの部分だけ抜き出して…、ということは難しそうなので、自前で実装することにした。 コンパイルと分離されている方がフェーズを明確に分けることができてわかりやすい（と個人的に思う）ので、別の実行ファイルにする方針にした。

#で始まる行はディレクティブを処理し、始まらない行は通常の行としてマクロの展開を行う。 パーサやレクサはコンパイラと共有しないと重複して実装する羽目になってしまうので避けたい。 だけどそうするためには気をつけることがある。

コンパイラではパースする時点で型を決めたり参照される変数が定義されているかの検査などを済ませてしまえばいっぺんに処理できて楽なんだけど、プリプロセッサでも使用できるようにするとなると都合が悪い。 例えばdefined(FOO)という式をパースするときにdefinedやFOOが定義済みかとか、型はなにかとかを検査せずに構文木だけを取得したい。

なので構文木の構築（パース）と意味解析を分けてやる。 いっぺんに処理してしまう方法に比べると作った構文木をたどる処理が必要になるのでちょっと面倒になるけど、式のパースがプリプロセッサと共有できるようになる。

プリプロセッサ自体はてきとーに、インクルードやマクロの定義と展開、条件付きコンパイルなどの必要な要素だけを実装する。 C++でCプリプロセッサを作ったり速くしたりしたお話によると「式の展開は謎が多い」とのことで、実装の参考として blog dds: 2006.06.26 - Dave Prosser’s C Preprocessing Algorithmが紹介されていたが、あまり参照せずにちゃんと実装しなかった。

#で始まらない行も単純に出力すればよいのではなく、マクロ定義されていたら展開する必要がある。

関数で可変長引数を扱えるようにする

printfのように可変長の引数を扱うには<stdarg.h>のva_listを利用する。 自作のCコンパイラはlibcを組み込まないので、この辺のライブラリ関数も自作してやる必要がある。

関数呼び出しの引数はABIに従ってレジスタで渡されるが、「低レイヤ」では関数の頭でスタックフレーム上に格納して、変数アクセスはすべてスタックフレーム上のメモリアクセス経由で行う。 なので可変長引数を扱うva_listはポインタで、va_startに渡される変数のアドレスで初期化して、va_argではその型に応じて取り出せば実現できる。 これらは単純なマクロで実装できる。

注意点としては、可変長引数の場合intより小さい整数型もintに格上げされるので、スタックフレーム上の配置を通常とは異なるようにする必要がある。

インラインアセンブラもどき

自作Cコンパイラが直接ELFバイナリを出力してしまい分割コンパイルやリンクに未対応なのですべて完結する必要がある。 なのでエントリポイントやシステムコールもC言語上で書く必要がある。

Linux上でファイルを実行した際のエントリポイントが呼び出された段階ではABIに沿ってなくて、起動パラメータがスタック上で渡されるので通常のC言語上では書けない。 システムコールもsyscall命令呼び出しが必要なので同様。

そこでインラインアセンブラもどきを扱えるようにした。 gccみたいにアセンブリで書けるのでなく、単にバイナリを直接配置できるようにするという方法で埋め込めるようにした：

void _start(void) {
  __asm(0x48, 0x8b, 0x3c, 0x24);     // mov (%rsp), %rdi  : argcを第１引数に
  __asm(0x48, 0x8d, 0x74, 0x24, 8);  // lea 8(%rsp), %rsi : argvを第２引数に
  __asm(0xe8, __rel32("main"));      // call main         : main関数呼び出し
  __asm(0x89, 0xc7);                 // mov %eax, %edi    : 戻り値を第１引数に
  __asm(0xe9, __rel32("exit"));      // jmp exit          : exit関数呼び出し
}

void exit(int code) {
  __asm(0xb8, 0x3c, 0x00, 0x00, 0x00);  // mov $__NR_exit, %eax
  __asm(0x0f, 0x05);                    // syscall : exit システムコール
}

__asmは実際の関数ではなくて、コード生成時に引数をバイナリとして埋め込む。

セルフホスティングへの道

ある程度の文法を処理できるようになれば、ユニットテストや簡単なサンプルプログラムは動くようになる。 しかしもう少し大きな、実践的なプログラムで確認したくなってくる。 そこでわかりやすい目標がセルフホスティングだ。 自分自身のソースをコンパイルして動かすことができれば、それを使ってさらに拡張していけるというのが面白い。

不確定性バグ

でセルフホスティングできるようにしようとコンパイルしてみるが、しかしなんかしらバグがあって動かない。 第二世代でのコンパイル時に落ちる場合もあるし、第二世代でコンパイルして出力した実行ファイルを起動すると落ちる場合もある。

第一世代はgccでコンパイルしているのでデバッグ情報もあってgdbで追うこともできる。 しかし第二世代にはないので、gdbで追うには辛い。 printfでデバッグ出力をはさむと落ちなくなったりするので、原因の特定が難しい。

スタックポインタの16バイトアライン

原因が全然わからないので、x86-64の場合関数呼び出し時にスタックポインタ16バイト境界に合わせる必要がある、と読んだので（x86-64 モードのプログラミングではスタックのアライメントに気を付けよう - uchan note）やってみた。 実行時にレジスタの値を調整して合わせるのかと思ったが、8ccではpushやpopなどのスタック操作をカウントしておいてコンパイル時に決定していたので、 うまい方法だと思いそれに倣ってみた。

結果としては効果はなかった。 標準ライブラリで浮動小数点数やSIMD命令を使用する場合にアライメントが必要な場合があるらしい（要出典）が、自作コンパイラの場合どれも使用していないのでアライメントが必要にはなっていなかった。

アセンブリを出力できるようにする

ELFを直接出力してしまっているのでSegmentation Faultが起きたときにどこで落ちたかわからず、個所を特定しづらい。 そこで不本意ながらデバッグ用にアセンブリを出力できるようにして、gccでもビルドできるようにしてみた。

結果としてそれによりバグが特定できた。 原因はポインタのポストインクリメント時に使用する命令が間違っていて、8バイト領域へのインダイレクト加算をするところを2バイト領域で行ってしまっていた。 こういう凡ミスするとほんと後から苦労するから気をつけないと…。

Makefileでの環境変数参照による第二世代のテスト

コンパイラを作成する段階でユニットテストを書いて動作をテストしていくが、第二世代のコンパイラに対してもテストさせたい。 使用するコンパイラを切り替えられるようにするにはどうするか。

Makefileからテストを起動するものとして、makeの変数を指定する形で行う。 使用するコンパイラをデフォルトとして第一世代のコンパイラへのパス：

XCC=./xcc

test:
	XCC=$(XCC) ./test.sh

を指定しておいて環境変数経由でシェルスクリプトに渡して、通常はそれでテストが走るようにしておく。

第二世代のテストの場合には変数を設定してtestを呼び出す：

test-gen2:
	$(MAKE) XCC=./xcc-gen2 test

起動されるシェルスクリプト内で環境変数からコンパイラのパスを得る：

XCC=${XCC:-./xcc}

:-で環境変数が未定義だったらデフォルトの値を使用するようにする。 （参考：シェルスクリプトでの変数定義 - Qiita）

第三世代は、生成されたファイルが第二世代と差がないかどうかを diff -b でバイナリ比較する。

今後の課題

ひとまずある程度動作して、セルフホスティングできるCコンパイラを作ることができた。 今後の課題としては、

  • レジスタ活用
    • 「低レイヤ」では計算途中の値をスタックに保持する方式でコンパイルするが、x86-64はレジスタ数もそれなりにあるので活用したい。 9ccでは変数や中間の値をレジスタに割り当てるようになっているので、参考にしたい。
  • 最適化
    • 出力されるコードはお世辞にも効率的とはいえないので、多少の最適化はかけたい。
  • 分割コンパイル対応

「低レイヤ」の方々

参照

関連記事

新着記事