M1 Macで自作Cコンパイラをセルフホストした
はじめに
何番煎じか分かりませんがC コンパイラ作成入門を参考に C コンパイラを自作しました。この記事ではその過程で得られた知見をまとめます。
作ったもの
作ったものは以下のリポジトリにあります。
以下のリポジトリを参考にしました。
一応、以下のコミットまで写したつもりです。
私の最初のコミットが 2023 年 7 月 31 日なので、ちょうど半年ぐらいかかりました。
なぜ取り組んだのか
これを始める前は、以下のような状態でした。
- C 言語で for 文や if 文は書ける。
- ポインタはなんとなく分かる。
- メモリのデータ領域やスタック領域やヒープ領域は知らない。
- アセンブリはわからない。
去年、 C++ で LLM のモデルを動かすプロジェクトや、機械学習フレームワークのバックエンドが LLVM で最適化されている話を知って、低レイヤーの知識があると便利だなと思っていました。そんな中、C コンパイラ作成入門という記事をたまたま見つけたのでやってみました。
得られた知見
そんな C 言語やアセンブリ初心者の私が、C コンパイラを作ってみて得られた知見をまとめます。
スタックって便利
スタックってすごく便利ですね。最初、レジスタが(ARM64 には) 30 個しかないと知った時は、変数は 最大で 30 個しか使えなくて、不便だなとかと思ってました。ただこの認識は間違っていて、スタックを上手に使ってレジスタを使い回すことで、レジスタが足りなくなることはないのですね。
特にプログラミング言語のコンパイラは、言語の定義から再帰的な木構造になるので、スタックと相性が良いです。レジスタは 4 個あればかなり複雑なコンパイラが作成できるのではないでしょうか。これって、スタックさえあれば変数 4 つしか使えないのに複雑な処理ができるってことです。結構すごくないですか。
アセンブリの理解
アセンブリへの理解が深まりました。chibicc は x86_64 向けに実装されており、それを ARM64 向けに移植しました。そのため、x86_64 のアセンブリと ARM64 のアセンブリの両方の勉強ができました。
x86_64 は CISC に分類され、ARM64 は RISC に分類されています。そのため移植は難しいのかなとか思っていましたが、実際は仕組みそのものにそこまで違いはなく初心者でも無理なく移植が可能でした。(メモリ管理周りとかまで全部勉強したわけではないです。その辺りは大きく違うかもしれないです。)
両者の違いとしては、x86_64 の場合は Intel 記法と AT&T 記法の二種類があり、さらに過去の経緯からレジスタ名が複雑になってしまっているので、初心者には難しいです。ARM64 はそのあたりが綺麗に整理されてるのでわかりやすいです。ただ、この辺は些細な問題でして、考え方自体は(少なくとも私が勉強した範囲では)そこまで変わらないです。
ローカル変数とグローバル変数の違い
ローカル変数とグローバル変数の違いはわかるようになりました。C 言語の文法的には、関数内に書いてるか関数外に書いてるかの違いしかないように見えますが、仕組みは全然違います。グローバル変数はコンパイル時に値が計算されて、バイナリのデータ領域に埋め込まれます。そして、実行開始時にコードと一緒にメモリへ展開されます。一方で、ローカル変数はコードの実行中にスタック領域が確保されて、そこに値が格納されます。文法は似てますがやってることは全然違います。
結合度と凝集度
C コンパイラの自作を通じてある程度大きなコードの書き方を学びました。特に結合度と凝集度を意識してコードの複雑さを抑える手法がいかに重要かを学びました。C コンパイラを作る際は、少しずつコードに機能を加えて行くのですが、きちんとしたテクニックを使えば、複雑さを抑えながら機能を追加し続けられることを学びました。今回は写経だったので、そのテクニックを使いこなせるレベルまで習得できていませんが、この辺りを修業してちゃんとしたコードが書けるようになりたいと思いました。
工夫したこと
次は私がした工夫を説明します。
M1 Mac を使った
オリジナルの chibicc は x86_64 をターゲットにしています。最初の頃は、chibicc を完全に写経して、その後に ARM64 の移植するコードを書くという方針でやっていました。その時の残骸が以下のリポジトリです。
途中で、流石に 2 回写経するのはしんどくなったので、ARM64 をターゲットのみを開発しました。
最初の頃は何もわかっていなかったので、x86_64 のアセンブリを理解してから、ARM64 のアセンブリを理解するという流れは結構よかったです。アセンブリへの理解が進んでくると、仕組みそのものは x86_64 でも ARM64 でも変わらないことがわかり、それがわかってからは ARM64 だけを開発していました。
CLion を使った
私は CLion を使ってこれを開発しました。CLion には C 言語の GUI のデバッガーが付属しているので、それを使ってデバッグもしていました。そのため gdb の使い方を習熟したり、printf デバッグをする必要がなく非常に楽でした。ただ、今後 OS 自作などを始める時に、常に CLion が使えるわけでもない気がしているので、いづれは gdb を使用する必要があると思っています。
CMake を使った
CLion でデバッガーを使うには CMake を使う必要があるので CMake を使いました。ただ機能はそこまで使いこなせていません。
CMake については以下に記事を書きました。
苦労したこと
移植するにあたって苦労したことの一部を紹介します。
プロローグとエピローグ
プロローグとエピローグは x86_64 と ARM64 で異なるので、それを理解して移植しました。プロローグとエピローグへの理解は、アセンブリを始めるとき一番最初の壁だと思います。最初は clang の出力を丸写ししていましたが、それだとローカル変数周りのデバッグできかったので整理してきちんと理解しました。
せっかく理解したのでここで解説します。プロローグとエピローグはアセンブリ言語で関数を実装する際に関数の始めと終わりに書く処理です。x86_64 のプロローグとエピローグは、以下の記事に詳しく説明が書かれています。
ARM64 の場合は、プロローグとエピローグは次のようになります。
; prologue
stp fp, lr, [sp, -16]!
mov fp, sp
; ... function body ...
; epilogue
mov sp, fp
ldp fp, lr, [sp], 16
ret
これを理解するためには、まずはレジスタ fp
, lr
,sp
を理解する必要があります。
ARM64 は 32 個の汎用レジスタ(x0
~x31
)があります。その内、最後の 3 つには以下のような別名がついており、特別な役割を果たします。
x29 = fp (frame pointer) : ローカル変数の基準となるアドレス
x30 = lr (link register) : 関数の戻り先のアドレス
x31 = sp (stack pointer) : スタックの一番上のアドレス, xzr (zero register) としても使われる
ちなみにx31
はldp
/stp
/mov
などの命令と一緒に使われるときはsp
として使われ、add
/sub
などの命令と一緒に使われるときは xzr
として使われます。
その上で ARM64 のレジスタと x86_64 のレジスタの対応関係を整理すると以下のようになります。
ARM64 | x86_64 | 説明 |
---|---|---|
fp | rbp | ローカル変数の基準のアドレス |
lr | スタックトップ | 関数の戻り先のアドレス |
sp | rsp | スタックの一番上のアドレス |
ARM64 におけるsp
とfp
は、それぞれ x86_64 における rsp
や rbp
と同じ役割を果たします。一方で、lr
に対応するレジスタは x86_64 には存在せず、スタックの一番上に積まれたアドレスがlr
と同じ役割を果たします。
次に、x86_64 の call
/ret
命令と ARM64 の bl
/ret
命令の違いを説明します。これらは同じ関数呼び出しの機能ではありますが、僅かな違いがあります。
x86_64 の場合:
-
call
:call
命令の次の命令のアドレスをスタックトップに格納し、call
命令の引数に指定したアドレスへジャンプする。 -
ret
: スタックトップのアドレスを取り出し、そのアドレスにジャンプする。
ARM64 の場合:
-
bl
:bl
命令の次の命令のアドレスをlr
に格納し、bl
命令の引数に指定したアドレスへジャンプする。 -
ret
:lr
に格納されているアドレスにジャンプする。
このように、x86_64 と ARM64 では関数の呼び出し元のアドレスを格納する場所が異なります。x86_64 ではスタックに格納されますが、ARM64 ではlr
に格納されます。
前提の説明が終わったので ARM64 のプロローグとエピローグを解説します。関数呼び出し時点でfp
とlr
の状態は以下のようになっています。
fp = 呼び出し元の関数のローカル変数の基準となるアドレス
lr = bl命令の次の命令のアドレス
これらのレジスタの情報は関数が呼び出しもとに戻るタイミングまで取っておく必要があります。なぜなら、fp
を保存しておかないと、関数が戻った時、関数の呼び出し元でローカル変数が使えなくなってしまいます。また、lr
を保存しておかないと、関数の中でさらに関数が呼ばれて lr が書き換わった時に、元の関数に戻れなくなってしまいます。そのため、関数の一番最初でfp
とlr
の値をスタックに保存しておきます。処理としては以下のようになります。
; prologue
stp fp, lr, [sp, -16]!
mov fp, sp
stp
命令で、fp
とlr
をスタックに保存します。その後、mov 命令でfp
にsp
のアドレスを書き込み、関数のローカル変数の基準とします。関数実行中はsp
を必ず低いアドレス方向へ伸ばすように使って、必ず元のlr
とfp
の値を壊さないようにします。
ちなみに、stp
命令は2つのレジスタの値を同時にスタックに格納する命令です。[sp, -16]!
は格納した後にsp
を-16
だけ減算するという意味です。stp
命令の第三引数は、[sp, -16]
と書くとsp
を減算しないので、stp
命令の後にsub sp, sp, 16
と書く必要があります。stp
命令の第三引数に!
をつけると、stp
命令の後にsp
を減算するという意味になります。
次に、関数が終了するタイミングの処理を解説をします。関数を終了する際は、fp
とlr
の値を関数呼び出し直後の状態に戻す必要があります。そのため、関数の一番最後で以下の処理を実行します。
; epilogue
mov sp, fp
ldp fp, lr, [sp], 16
ret
fp
から関数呼び出し時点のsp
の値を書き戻します。そこから、ldp
命令で呼び出し元のfp
とlr
の値を取り出し、ret
命令で関数呼び出し元に戻ります。
ちなみに、ldr
命令は2つのレジスタの値を同時にスタックから取り出す命令です。[sp], 16
はsp
のアドレスから16
だけ加算して、そのアドレスから値を取り出すという意味です。ldp
命令の第三引数は、[sp, 16]
と書くとsp
を加算しないので、ldp
命令の後にadd sp, sp, 16
と書く必要があります。
以上が ARM64 におけるエピローグとプロローグの解説です。
Apple ARM64 の ABI
コンパイラを自作する人が最も苦労するのは、可変長引数の関数の呼び出し規約だと思います。printf
は可変長引数の関数のため、コンパイラを自作する時は正しく呼び出せるようにしないといけませんが、これが意外と複雑です。
Apple は独自の関数呼び出し規則を採用しているので、clang の出力するアセンブリを観察して移植しました。
せっかくなので Apple ARM64 の ABI の呼び出し規則について私が調べた結果を共有しておきます。きちんと公式ドキュメントを調査したわけではないです。そのため間違っている可能性があります。ご注意ください。
int add_all(int n, ...);
int main() { return add_all(3, 11, 22, 33); }
この際に、add_all
関数がどのような状態で呼び出されるのか説明します。
Apple ARM64 の ABI では、固定長の部分はレジスタで渡され、可変長の部分はスタックに渡されます。そのため、add_all(3, 11, 22, 33)
の場合、3
はレジスタx0
に格納され、11
と22
と33
はスタックに渡されます。図で示すと以下のようになります。
- レジスタ:
x0 = 3
- スタック:
--- sp + 32
--- sp + 24
33
--- sp + 16
22
--- sp + 8
11
--- sp
この図ではスタックは下に向かって伸びていると仮定しています。そのためスタックには引数の右から先に格納していく必要があります。さらに、重要なのは、M1 Mac はアライメントが 16Bytes なため、sp は 16 の倍数に調整する必要があります。そのため、3 つの可変長引数を渡す場合は、24
を繰り上げて32
に調整する必要があります。
また、関数を受ける側では、...
の部分が uint64_t
のリストのポインタが渡されてきていると解釈することで、自然に可変長引数を受け取ることができます。(これだとva_start(ap, n)
の第二引数が無視されるので厳密には間違っていると思いますが、セルフホストするにはこれで十分でした。)
数値の変換
ARM64 の整数と浮動小数点の変換は x86_64 と ARM64 で異なるので調べて移植しました。せっかく調べたので共有します。
数値の変換。
整数から浮動小数への変換
- ucvtf: 符号なし整数から浮動小数への変換
From | To | Example |
---|---|---|
u32 | f32 | ucvtf s0, w0 |
u32 | f64 | ucvtf d0, w0 |
u64 | f32 | ucvtf s0, x0 |
u64 | f64 | ucvtf d0, x0 |
- scvtf: 符号付き整数から浮動小数への変換
From | To | Example |
---|---|---|
i32 | f32 | scvtf s0, w0 |
i32 | f64 | scvtf d0, w0 |
i64 | f32 | scvtf s0, x0 |
i64 | f64 | scvtf d0, x0 |
浮動小数から整数への変換
- fcvtzs: 浮動小数から符号付き整数への変換
From | To | Example |
---|---|---|
f32 | i32 | fcvtzs w0, s0 |
f32 | i64 | fcvtzs x0, s0 |
f64 | i32 | fcvtzs w0, d0 |
f64 | i64 | fcvtzs x0, d0 |
- fcvtzu: 浮動小数から符号なし整数への変換
From | To | Example |
---|---|---|
f32 | u32 | fcvtzu w0, s0 |
f32 | u64 | fcvtzu x0, s0 |
f64 | u32 | fcvtzu w0, d0 |
f64 | u64 | fcvtzu x0, d0 |
浮動小数から浮動小数への変換
- fcvt: 浮動小数から浮動小数への変換
From | To | Example |
---|---|---|
f32 | f64 | fcvt d0, s0 |
f64 | f32 | fcvt s0, d0 |
整数から整数への変換
- sxtw: 符号付き整数から符号付き整数への変換
From | To | Example |
---|---|---|
i32 | i64 | sxtw x0, w0 |
- uxtw: 符号なし整数から符号なし整数への変換
From | To | Example |
---|---|---|
i32 | u64 | uxtw x0, w0 |
u32 | i64 | uxtw x0, w0 |
u32 | u64 | uxtw x0, w0 |
- mov: 整数から整数への変換
From | To | Example |
---|---|---|
i64 | i32 | mov w0, w0 |
i64 | u32 | mov w0, w0 |
u64 | i32 | mov w0, w0 |
u64 | u32 | mov w0, w0 |
- sxtb: 32bit 整数から 8bit 符号付き整数への変換
From | To | Example |
---|---|---|
i32 | i8 | sxtb w0, w0 |
- uxtb: 32bit 整数から 8bit 符号なし整数への変換
From | To | Example |
---|---|---|
i32 | u8 | uxtb w0, w0 |
- sxth: 32bit 整数から 16bit 符号付き整数への変換
From | To | Example |
---|---|---|
i32 | i16 | sxth w0, w0 |
- uxth: 32bit 整数から 16bit 符号なし整数への変換
From | To | Example |
---|---|---|
i32 | u16 | uxth w0, w0 |
こうやって並べてみると ARM64 のアセンブリって整理されていて良いですよね。
既知の問題
私の作ったコンパイラには以下の問題があります。セルフホストには問題がなかったので放置しています。
NaN との比較
以下のコードは、clang では 1 が出力されますが、私の作ったコンパイラでは 0 が出力されます。
int main() {
if (0.0 / 0.0 > 0.0) {
return 0;
} else {
return 1;
}
}
0.0/0.0 は NaN になります。C 言語は NaN との比較に厳格な定義があるらしいのですが、ARM64 のアセンブリで上記を自然に実装すると定義に合わないようです。clang のアセンブリは少し複雑なことをして定義に合わせているようなのですが、私の作ったコンパイラはそれを実装していません。
9 個以上の引数を取る関数
私の作成したコンパイラは 9 個以上の引数をとる関数を正しく実行できません。以下のようなコードは結果がおかしくなります。
int add_all(int a1, int a2, int a3, int a4, int a5, int a6, int a7, int a8, int a9, int a10) {
return a1 + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10;
}
int main() { return add_all(1, 2, 3, 4, 5, 6, 7, 8, 9, 10); }
ARM64 の ABI では、8 個までの引数はレジスタで渡し、それ以降はスタックで渡すことになっています。それをサポートしていないので結果がおかしくなります。ただ、私のコンパイラには 9 個以上の引数をとる関数を呼び出すコードがないので放置しています。
可変長引数の関数呼び出しのコードを流用することで綺麗に実装できる気がしますが、可変長引数の方は 8Bytes ごとに変数を詰めてけばいいんですけど、9 個以上の引数の場合は int だったらきちんと 4Bytes ごとに詰めてく必要があり、そこを細かく考えるのが面倒で放置してます。
内部で clang を使っている。
私の作ったコンパイラはアセンブラやリンカーとして clang を利用しています。
なんとなく llvm が好きなので、llvm 縛りで作っていました。llvm には gcc における as コマンドがないため、アセンブラとして clang を使うのはいいです。ただ、リンカーとして clang を使うのはちょっと違う気がしており、きちんと llvm のリンカーを使って chibicc の以下のコミットに対応したいです。
(もしかしたらこれに対応しないと正確にはセルフホストとは呼べないのかもしれません。)
stdlib.h を include できない
以下をコンパイルできないです。
#include <stdlib.h>
int main() {return 0;}
以下のようなエラーが出ます。
#if __has_include(<AvailabilityInternalPrivate.h>)
^not a function
これは私のコンパイラーが__has_include
をサポートしていないめです。Xcode に搭載されているヘッダーファイルには、こういった拡張を含むものがあるようで、それを include しようとするとエラーになります。とりあえず今はヘッダーファイルを自分で作成して、そこに定義を書いて回避しています。
次にやりたいこと
C コンパイラを作ることでさらに低レイヤーに興味が出てきました。次はどういうことをやりたいかを書いておきます。
Linux ARM64 への移植
M1 Mac でセルフホストしたのはいいのですが、M1 Mac だと少し扱いづらいので、ラズパイ向けに移植してみたいと思ってます。少し試してみたのですが、Linux の ARM64 と Apple の ARM64 は微妙にアセンブリが違うらしく、そのままでは動かなかったです。そのため修正が必要です。あと再び可変長引数の関数の ABI も違うので、ここは再び格闘が必要かなと思ってます。
アセンブラとリンカーの自作
C コンパイラを作って、アセンブリ言語まではわかったのですが、その先のバイナリまでは理解できてないです。バイナリ読んでこそ凄腕ハッカー感が出てくるので、とりあえずアセンブラを自作したいです。
Linux の場合は ELF フォーマットが使われていますが、Apple だと Mach-O という別のフォーマットが使われています。私は後者の方を作りたいです。
LLVM のチュートリアル
LLVM のチュートリアルをやってみたいです。
一から自作するのも面白かったのですが、現代的な言語は LLVM を使っているものが多いです。そのため LLVM まで勉強しておくと何かと役に立ちそうかなと思っています。
少しやってみたいのが、セルフホスト可能な最低限の C 言語のサブセットを定義して、LLVM とか yacc とかふんだんに使って C コンパイラを作ってみたいです。そうして chibicc に挑戦する前の練習台として使えるものを作ってみたいなとか思ってます。
OS 自作
コンパイラを自作して低レイヤーに興味が出てきたので、次は OS を作ってみたいです。ファイル書き出しの仕組みとか、インターネット通信の仕組みとか、そういうのを知りたいです。今回 ARM64 に詳しくなったので、ラズパイ向けの OS とか作ってみたいです。
参考
同じことを挑戦される人向けに、chibicc 以外で参考となる資料をまとめておきます。
xcc
9cc をベースに C コンパイラを自作された方のリポジトリです。
この方は 9cc をベースとして 様々なアーキテクチャ向けにコンパイラを移植されたようで、そのターゲットには M1 Mac を含んでいます。とくにxcc -S
で出力されるアセンブリは非常に参考になります。
Linux で Arm64 アセンブリプログラミング
ARM64 のアセンブリがまとめられたページです。
情報が多く説明もわかりやすいので非常に参考になります。
私のメモ
コンパイラを作成していた時のメモをスクラップ記事にまとめています。
M1 Mac で C 言語のセルフホストを目指す方は参考になるかもしれません。ただ、上記のメモを見るより、clang -S
やxcc -S
で得られるアセンブリを見た方が良いかもしれません。
Discussion