macOS で動かす C コンパイラを C で作った

LISENCE と LICENSE 、正しいスペルがどっちかわからない。どうも、かわしんです。正解は LICENSE です。

僕は、よく MIT ライセンスを使います。気が向いたら WTFPL（ Do What The F*ck You Want To Public License ）を使います。趣がありますよね。

さて、僕の実家は山口にあるのですが、年末の帰省のタイミングで C コンパイラを作りました。正確には去年の 12月 30 日の東京発博多行き新幹線のぞみ号に乗った時から、今年の 1 月 4 日の夜までです。新幹線は片道5時間くらい乗ってるので開発にうってつけです。本当は東京に戻ってきたらやめると決めてたんですが、キリが悪かったので１日延長して昨日までやってました。

去年の夏あたりに Rui Ueyama さんが作った 9cc が話題になり、僕もいつか作ってみたいなと思っていました。

年末にまとまった時間が取れて、流石にそろそろ C 言語を使えるようにならないといけないと思っていたので、C 言語を理解するために C 言語を C 言語で実装してみました。

出来上がったのはこれです。MIT ライセンスです。

github.com

結局セルフコンパイルまではたどり着きませんでしたが、テストコードをコンパイルするところまでできて、キリがよかったのでここで一旦やめることにしました。

実装の方針

11 月のはじめに Rui さんがコンパイラを作る教科書の最初の部分を公開されました。

Cコンパイラ作成本、完成は相当先になりそうだし、あまりもったいぶっても仕方がないので、めっちゃ最初の部分だけとりあえず公開しました。この手順に従ってできるのは恐ろしく原始的なコンパイラですが、始めてみるキッカケにはなるかも。 https://t.co/rbHWp2kyGM
— Rui Ueyama (@rui314) November 1, 2018

この教科書で初歩的なコンパイラが作るところまでサポートしてくれるのでこの教科書に沿って実装を進め、そのあとは 9cc の実装などを参考に進めることにしました。

また、その後の開発の順番はこの記事にオススメの開発の順番が書かれているのでそれを参考にマイルストーンとしました。

Cコンパイラ制作の夏期集中コースが思っていた以上にうまくいった話｜Rui Ueyama｜note

この記事では開発の順番として 配列 を実装してから ポインタ を実装することがオススメされていますが、配列はポインタのように扱われるので、まず ポインタを実装してから配列を実装する のがいいと思いました。僕は一回配列から実装したのですがうまく行かず、実装を捨ててポインタから実装し直してから配列を実装しました。

また、これは重要な点なのですが、この教科書は スタックベースのコンパイラ を作るのに対して 9cc は レジスタベースのコンパイラ です。そのため構文解析や意味解析までは参考になりますが、アセンブリ言語への変換はあまり参考になりません。

そのため、スタックベースのコンパイラはセキュキャンのコースで一番早く実装が終わったという艮鮟鱇さんの aqcc を参考にしました。ただ、コードベースが結構違うのでアセンブリへの変換のところあたりくらいしか読んでません。

今回は、macOS 上で動くスタックベースの C コンパイラ を作りました。

工夫した点（配列の扱い）

一番工夫したのは 配列の扱い です。以下の解説では、9cc のテストを C で書き直した時点のコミットと僕の kcc の比較として解説します。

C 言語では配列はポインタと同じように扱われます。値へのアクセスは、配列・ポインタ共に配列風のアクセス（ a[1] ）とポインタ風のアクセス（ *(a+1) ）ができます。

しかし、ポインタに配列を代入できますが、配列へは配列を代入することもポインタを代入することもできません。

int a[10];
int *b;
b = a;  // OK
// a = b; // NG

a[0] = 1; a[9] = 10;
b[0];    // 1
b[9];    // 10
*a;      // 1
*(a+9); // 10

void tmp(int *x) {
    // do something
}
tmp(a); // OK

では違いは何かというと、変数が宣言された時の挙動とその変数が指し示すものです。

ポインタはその変数が宣言されるとアドレスを格納するのに必要なサイズのメモリ（ 8 バイト）が確保されます。ポインタ変数が指し示す値はアドレス値です。

一方、配列はその変数が宣言されると配列の長さ分のメモリ（ 型のサイズ * 配列の長さ ）が確保されます。配列変数が指し示す値は配列の先頭要素です。

9cc では、配列風のアクセスとポインタ風のアクセスは共に同じように ND_DEREF として構文解析されています。

// 配列アクセスの構文解析
while (consume('[')) {
  lhs = new_expr(ND_DEREF, new_binop('+', lhs, assign()));
  expect(']');
}

// ポインタアクセスの構文解析
if (consume('*'))
  return new_expr(ND_DEREF, mul());

そして意味解析の中ではこれら２つのアクセス手法は扱われていますが、ND_DEREF の対象はポインタに対するアクセスに限定され、それ以外はエラーになるように実装されています。

配列へのアクセスをポインタに対するアクセスとして読み替えるために、意味解析の中の maybe_decay() で、配列へのアクセスノードと ND_DEREF ノードの間に ND_ADDR ノードを差し込んでポインタアクセスに変換しています。

ただし、代入では配列の値に直接書き込む必要があるのでポインタに変換してはいけません。そのため、decay という対象ノードが代入として扱われているかを示すフラグを意味解析の全てに引き回して decay が false の時は ND_ADDR ノードの差し込みを行わないように実装されています。

そのために再帰的に意味解析を行う walk() 関数のインターフェイスも変更されています。

// 配列のない時のインターフェイス
static void walk(Env *env, Node *node)

// 配列の解析が含まれた時のインターフェイス
static Node *walk(Env *env, Node *node, bool decay)

decay というフラグでコンテキストを引き回すのと、構築された AST を差し替えるのがなんとなく複雑だなと思ったのでなんとか工夫できないかを検討しました。

ポイントは、配列とポインタは同じように扱われる ということです。

9cc では、意味解析ステップ で AST の配列アクセスノードをポインタアクセスノードに差し替える ことで、配列とポインタを同じように扱っています。しかし、コンテキストを引き回したり AST を差し替えるため、ソースコードはやや複雑になっています。

僕の kcc では、AST からアセンブリの変換ステップ で 配列の値へのアクセス命令をアドレスの読み込み命令に切り替える ことで、配列とポインタを同じように扱っています。これにより、意味解析ステップでは以前と同じインターフェイスを保ち、アセンブリへの変換は ND_IDENT と ND_DEREF の処理を配列へのアクセス時に切り替える条件分岐を入れるだけで済みます。

この方法では、配列へのアクセスが代入なのか値へ読み込みなのかのコンテキストを意識する必要がない ため実装が複雑になりません。

まだ、kcc は最適化などが最後まで実装できていないので本当にこの方針でいいのかはわかりませんが、とりあえず多次元配列の場合も含めてテストは通っているので大丈夫じゃないかと思っています。

macOS と Linux の非互換性

教科書、9cc、aqcc は全て Linux 上で動かすことを想定していると思います。確かに、Docker とか vagrant を使えばよかったんですが、やっぱりローカルで動かしたいなという軽い気持ちで macOS でコンパイルするコンパイラを作ることにしました。

教科書には、macOS と Linux の違いはラベルの書き方が先頭に _ をつけるようになるくらいのノリで書いてありましたが、教科書に載っている範囲を越えると割と非互換が多いのでハマります。（今教科書を確認したら、修正されて macOS は対象外になったようです。）

僕がハマった macOS と Linux との違いをここで紹介しておきます。もし macOS で作る場合は参考にしてみてください。

Makefile

Makefile で複数ファイルから実行バイナリを生成する 9cc: $(OBJS) の部分が mac に標準で用意されている make コマンドでは動きません。

ターゲット名だけでコンパイルする時はターゲット名と同じ .c ファイルが必要だったみたいです。

代わりに直接 gcc を呼び出すようにして解決しました。

CC=gcc
SRCS=$(wildcard *.c)
OBJS=$(SRCS:.c=.o)

kcc: $(OBJS)
    $(CC) -o $@ $(OBJS) $(LDFLAGS)

グローバル変数の扱い

アセンブラではグローバル変数は、.data セクションに確保してラベル経由でアクセスします。

Linux ではグローバル変数のアドレスは、lea 命令を使って取得します。

しかし、macOS では lea はエラーになります。

error: 32-bit absolute addressing is not supported in 64-bit mode
  lea rax, .L.str474

macOS では、グローバルなラベルへのアドレスはグローバルなラベルテーブル経由（ GOTPCREL ）で引いてくる必要があります。

これは、グローバル領域のメモリは再配置されることがありアドレスの絶対値を持つことができないかららしいです。（macos - Why does this movq instruction work on linux and not osx? - Stack Overflow）

また、Apple の公式ドキュメントにも GOTPCREL のサンプルコードが載っていましたが AT&T 記法であったため、それを Intel 記法にするのにも苦労しました。その苦労の結果がこれです。

  mov rax, [label@GOTPCREL + rip]

これで、グローバル領域のラベルのアドレスを rax に読み込むことができます。

stderr

テストコードの中でfprintf() でエラー出力するために extern int *stderr; が宣言されています。

Linux では、stderr は、_IO_FILE のポインタ変数です。

# Ubuntu 18.04 + gcc 環境
$ cat /usr/include/stdio.h | grep stderr
extern struct _IO_FILE *stderr;     /* Standard error output stream.  */
#define stderr stderr

しかし、macOS では stderr はマクロです。そのため僕は printf() 関数をエラー出力に追加ました。

今考えると stderr の代わりに __stderrp でよかったのかもしれないですが。

# macOS 10.14.2
$ cat /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/stdio.h | grep stderr
extern FILE *__stderrp;
#define stderr  __stderrp

スタックサイズ

これは macOS と Linux の違いではなく両方とも対応する必要があると思いますが、スタックのサイズは 16 の倍数にアライメントされている必要があります。これに結構ハマりました。

printf を呼び出すテストでローカル変数を定義するとなぜか make: *** [test] Segmentation fault: 11 のエラーが発生し、llvm でデバッグ実行すると stack_not_16_byte_aligned_error エラーが発生していたのでわかりました。

$ lldb ./tmp-test
(lldb) target create "./tmp-test"
Current executable set to './tmp-test' (x86_64).
(lldb) run
Process 69817 launched: './tmp-test' (x86_64)
Process 69817 stopped
* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=EXC_I386_GPFLT)
    frame #0: 0x00007fff59c5cc56 libdyld.dylib`stack_not_16_byte_aligned_error
libdyld.dylib`stack_not_16_byte_aligned_error:

デバッガを使えば一発でわかるエラーですが、デバッガを使う心理的障壁が高くてなかなか原因がわかりませんでした。