Zenn
🦔

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

2024/01/31に公開
コンパイラ
arm64
macOS
C
記事投稿コンテスト「今年の最も大きなチャレンジ」
tech

はじめに

何番煎じか分かりませんがC コンパイラ作成入門を参考に C コンパイラを自作しました。この記事ではその過程で得られた知見をまとめます。

作ったもの

作ったものは以下のリポジトリにあります。

https://github.com/derbuihan/chibicc_ARM64/

以下のリポジトリを参考にしました。

https://github.com/rui314/chibicc

一応、以下のコミットまで写したつもりです。

https://github.com/rui314/chibicc/commit/12a9e7506c092fcbab8852db85c3aebefc8a8c81

私の最初のコミットが 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 の移植するコードを書くという方針でやっていました。その時の残骸が以下のリポジトリです。

https://github.com/derbuihan/PeachCC

途中で、流石に 2 回写経するのはしんどくなったので、ARM64 をターゲットのみを開発しました。

最初の頃は何もわかっていなかったので、x86_64 のアセンブリを理解してから、ARM64 のアセンブリを理解するという流れは結構よかったです。アセンブリへの理解が進んでくると、仕組みそのものは x86_64 でも ARM64 でも変わらないことがわかり、それがわかってからは ARM64 だけを開発していました。

CLion を使った

私は CLion を使ってこれを開発しました。CLion には C 言語の GUI のデバッガーが付属しているので、それを使ってデバッグもしていました。そのため gdb の使い方を習熟したり、printf デバッグをする必要がなく非常に楽でした。ただ、今後 OS 自作などを始める時に、常に CLion が使えるわけでもない気がしているので、いづれは gdb を使用する必要があると思っています。

CMake を使った

CLion でデバッガーを使うには CMake を使う必要があるので CMake を使いました。ただ機能はそこまで使いこなせていません。

CMake については以下に記事を書きました。

https://zenn.dev/derbuihan/articles/a3e95230113b90

苦労したこと

移植するにあたって苦労したことの一部を紹介します。

プロローグとエピローグ

プロローグとエピローグは x86_64 と ARM64 で異なるので、それを理解して移植しました。プロローグとエピローグへの理解は、アセンブリを始めるとき一番最初の壁だと思います。最初は clang の出力を丸写ししていましたが、それだとローカル変数周りのデバッグできかったので整理してきちんと理解しました。

せっかく理解したのでここで解説します。プロローグとエピローグはアセンブリ言語で関数を実装する際に関数の始めと終わりに書く処理です。x86_64 のプロローグとエピローグは、以下の記事に詳しく説明が書かれています。

https://www.sigbus.info/compilerbook#スタック上の変数領域

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命令は２つのレジスタの値を同時にスタックに格納する命令です。[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命令は２つのレジスタの値を同時にスタックから取り出す命令です。[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 の以下のコミットに対応したいです。

https://github.com/rui314/chibicc/commit/8b726b54893e11427533fcceb7206b97c25f50a6

（もしかしたらこれに対応しないと正確にはセルフホストとは呼べないのかもしれません。）

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 のチュートリアルをやってみたいです。

https://llvm.org/docs/tutorial/

一から自作するのも面白かったのですが、現代的な言語は LLVM を使っているものが多いです。そのため LLVM まで勉強しておくと何かと役に立ちそうかなと思っています。

少しやってみたいのが、セルフホスト可能な最低限の C 言語のサブセットを定義して、LLVM とか yacc とかふんだんに使って C コンパイラを作ってみたいです。そうして chibicc に挑戦する前の練習台として使えるものを作ってみたいなとか思ってます。

OS 自作

コンパイラを自作して低レイヤーに興味が出てきたので、次は OS を作ってみたいです。ファイル書き出しの仕組みとか、インターネット通信の仕組みとか、そういうのを知りたいです。今回 ARM64 に詳しくなったので、ラズパイ向けの OS とか作ってみたいです。

参考

同じことを挑戦される人向けに、chibicc 以外で参考となる資料をまとめておきます。

xcc

9cc をベースに C コンパイラを自作された方のリポジトリです。

https://github.com/tyfkda/xcc

この方は 9cc をベースとして 様々なアーキテクチャ向けにコンパイラを移植されたようで、そのターゲットには M1 Mac を含んでいます。とくにxcc -Sで出力されるアセンブリは非常に参考になります。

Linux で Arm64 アセンブリプログラミング

ARM64 のアセンブリがまとめられたページです。

https://www.mztn.org/dragon/arm6400idx.html

情報が多く説明もわかりやすいので非常に参考になります。

私のメモ

コンパイラを作成していた時のメモをスクラップ記事にまとめています。

https://zenn.dev/derbuihan/scraps/d17f5619cfe5b4

M1 Mac で C 言語のセルフホストを目指す方は参考になるかもしれません。ただ、上記のメモを見るより、clang -Sやxcc -Sで得られるアセンブリを見た方が良いかもしれません。

Discussion