Apple Siliconで進めるCコンパイラ作成入門

この記事は MICIN Advent Calendar 2024 の 10日目の記事です。
https://adventar.org/calendars/10022
前回は山崎さんの、「MICINでのエンジニア向け社内イベントの紹介」 でした。

---

本記事は「低レイヤを知りたい人のためのCコンパイラ作成入門」(以降「元記事」)をApple M3 Proで開発した記録の紹介です。

https://www.sigbus.info/compilerbook

元記事ではmacOSは対象外です。命令セットについても，Apple Siliconのネイティブ環境で動作させるためにはx86-64ではなくARM64で記述する必要があります。今回Apple Siliconでも動作するコードを書いたので，その内容を本記事では紹介します。

• 元記事はステップ28までありますが，本記事ではステップ11までが対象です。
• 各ステップごとにテストが通ったコードをGitHubのレポジトリにアップしています
• レポジトリにアップしたコードはVSCodeのC言語フォーマットをかけています

動作確認をした開発環境

• Apple M3 Pro
• macOS Sonoma 14.5

$ uname -m
arm64

$ sw_vers
ProductName:		macOS
ProductVersion:		14.5
BuildVersion:		23F79

Docker環境

元記事で説明がある通り，環境構築すれば問題なく実行できるはずです。
私の場合はGitレポジトリで管理しているため$HOMEを$(pwd)に置き換えて実行しています。

docker build -t compilerbook https://www.sigbus.info/compilerbook/Dockerfile
docker run --rm -it -v "$(pwd):/9cc" -w /9cc compilerbook

ステップ１

「整数1個をコンパイルする言語の作成」

以下のコードは、コンパイラ本体の作成からの変更点

9cc.c

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  ...

- printf(".globl main\n");
  printf("main:\n");
- printf("  mov rax, %d\n", atoi(argv[1]));
+ printf("  mov x0, %d\n", atoi(argv[1]));
  printf("  ret\n");
  return 0;
}

解説

• ARM記法では.intel_syntax noprefixは不要です
• ARM64の汎用レジスタ名はx0...x30です
• ロード命令MOVはx86-64と同名です
• インデントエラーに注意しましょう

https://github.com/masatomoty/d9cc/tree/main/step1

ステップ２

「加減算のできるコンパイラの作成」

9cc.c

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  ...

- printf(".intel_syntax noprefix\n");
  printf(".globl main\n");
  printf("main:\n");
- printf("  mov rax, %ld\n", strtol(p, &p, 10));
+ printf("  mov x0, #%ld\n", strtol(p, &p, 10));

  while (*p) {
    if (*p == '+') {
      p++;
-     printf("  add rax, %ld\n", strtol(p, &p, 10));
+     printf("  add x0, x0, #%ld\n", strtol(p, &p, 10));
      continue;
    }

    if (*p == '-') {
      p++;
-     printf("  sub rax, %ld\n", strtol(p, &p, 10));
+     printf("  sub x0, x0, #%ld\n", strtol(p, &p, 10));
      continue;
    }

    ...
  }

  ...
}

解説

• 演算命令ADDとSUBはx86-64と同名です
• ARM記法ではADDとSUBは，引数を3つ指定します。
• add x0 x1 x2はx0 = x1 + x2を意味します
• 3番目の引数はレジスタ（x0等）と定数，どちらでも指定可能です

https://github.com/masatomoty/d9cc/tree/main/step2

ステップ3

「トークナイザを導入」

9cc.c

#include <ctype.h>
...
int main(int argc, char **argv) {
  ...
  // アセンブリの前半部分を出力
- printf(".intel_syntax noprefix\n");
  printf(".globl main\n");
  printf("main:\n");

  // 式の最初は数でなければならないので、それをチェックして
  // 最初のmov命令を出力
- printf("  mov rax, %d\n", expect_number());
+ printf("  mov x0, #%d\n", expect_number());

  // `+ <数>`あるいは`- <数>`というトークンの並びを消費しつつ
  // アセンブリを出力
  while (!at_eof()) {
    if (consume('+')) {
-     printf("  add rax, %d\n", expect_number());
+     printf("  add x0, x0, #%d\n", expect_number());
      continue;
    }

    expect('-');
-   printf("  sub rax, %d\n", expect_number());
+   printf("  sub x0, x0, #%d\n", expect_number());
  }
  ...
}

解説

• ステップ2と同じく演算命令の記述を変更することで動作します

https://github.com/masatomoty/d9cc/tree/main/step3

ステップ4

「エラーメッセージを改良」

9cc.c

#include <ctype.h>

...

void gen(Node *node) {
  if (node->kind == ND_NUM) {
-   printf("  push %d\n", node->val);
+   printf("  mov x0,  #%d\n", node->val);
+   printf("  str x0, [sp, -16]!\n");
    return;
  }

  gen(node->lhs);
  gen(node->rhs);

- printf("  pop rdi\n");
- printf("  pop rax\n");
+ printf("  ldr x1, [sp], 16\n");
+ printf("  ldr x0, [sp], 16\n");

  switch (node->kind) {
  case ND_ADD:
-   printf("  add rax, rdi\n");
+   printf("  add x0, x0, x1\n");
    break;
  case ND_SUB:
-   printf("  sub rax, rdi\n");
    break;
  case ND_MUL:
-   printf("  imul rax, rdi\n");
+   printf("  mul x0, x0, x1\n");
    break;
  case ND_DIV:
-   printf("  cqo\n");
-   printf("  idiv rdi\n");
+   printf("  sdiv x0, x0, x1\n");
    break;
  }

- printf("  push rax\n");
+ printf("  str x0, [sp, -16]!\n");
}

解説

• エラーメッセージに関する差分はありません
• 乗算MULと除算SDIVの名称がx86-64と異なります
• x86-64のPUSHとPOPはARM64ではLDR，STRで記述します

https://github.com/masatomoty/d9cc/tree/main/step4
※ 参考実装にはスタック操作は含まれません。ステップ5でまとめてコミットしています。

ARM64のスタックマシンの仕組み

以降のステップではスタックマシンの理解が欠かせないため，本章でARM64のスタックマシンの解説をします。

x86-64とARM64ではスタックマシンの振る舞いが大きく異なります。スタックマシンの基本的な説明は元記事でわかりやすく説明されています。しかしx86-64ベースでの説明ということもあり，ARM64に書き直そうとした途端に多くのつまずきポイントが発生します。

スタックポインタとベースポインタ

ARM64では慣例としてベースポインタにx29を用います。

	x86-64	ARM64
スタックポインタ	rsp	sp
ベースポインタ	rbp	x29

オフセット

x86-64では8バイトずつ領域を確保しますが，ARM64では16バイトが基本単位です。x29をベースポインタとして，N×16バイト（Nは整数）ずつアドレッシングやスタックフレームの領域を確保します。

アドレッシング

ARM64でスタックからデータの読み書きする場合，ロード命令LDRとストア命令STRを使います。スタックのどの位置から処理を行うかはスタックポインタで指定します。x86-64ではPUSHやPOPを呼び出すと，暗黙的にスタックポインタの値が更新されます。一方でARM64のLDRとSTRでは値の更新するかどうかを明示的に書く必要があります。

元記事にも以下のように説明があります。しかしARM64と比較は書かれていないため，人によって見落としやすいポイントになっています。

x86-64におけるスタックマシンの実現方法
x86-64のRSPレジスタはスタックポインタとして使うことを念頭に置いて設計されています。x86-64のpushやpopといった命令は、暗黙のうちにRSPをスタックポインタとして使って、その値を変更しつつ、RSPが指しているメモリにアクセスする命令です。したがって、x86-64命令セットをスタックマシンのように使うときは、RSPをスタックポインタとして使うのが素直です。

プレインデックスとポストインデックス

データの読み書きの処理とスタックポインタの更新は実行順序が指定できます。読み書きの処理前にspのアドレスを更新することをプレインデックス，処理後にspのアドレスを更新することをポストインデックスと呼びます。STRはプレインデックス，LDRはポストインデックスで呼び出すのが，直感的でわかりやすい書き方です。

以下ではx86-64のPUSHとPOPをARM64で書き換えた場合の実装を紹介します。プレインデックスとポストインデックスは書き方が複数可能で混乱しやすいです。以下の例では①と②の2つの書き方を紹介していますが，処理内容は同一です。

PUSHの実装

プレインデックスでスタックポインタを-16バイト更新してから，x0のデータをスタックに書き込みます。

// ①
sub sp, sp, #16
str x0, [sp]

// ②
str x0, [sp, -16]!

// x86-64の場合
push rax

POPの実装

ポストインデックスでスタックポインタを16バイト更新してから，スタックからx0にデータを読み込みます。

// ①
ldr x0, [sp]
add sp, sp, #16

// ②
ldr x0, [sp], 16

// x86-64の場合
pop rax

スタックフレームの領域確保

スタックフレームの領域確保するために，元記事にあるようにプロローグとエピローグを定義します。
以下は変数26個分の領域（26個*16バイト = 416）を確保するプロローグとエピローグの書き方です。STPはレジスタのペアをメモリにストアするために利用します。プロローグはプレインデックス，エピローグはポストインデックスで書いています。

// prologue
stp x29, x30, [sp, -16]!
mov x29, sp
sub sp, sp, #416

// epilogue
.Lreturn:
mov sp, x29
ldp x29, x30, [sp], #16

ARM64のスタックマシンの説明は以上です。スタックマシンについてより詳しく理解したい方は以下の記事がおすすめです。

https://qiita.com/poteto0/items/0ac09f2acf0bc127426f#スタックポインタ
https://www.mztn.org/dragon/arm6404ldr.html

以降では元記事に戻ってステップ5以降の実装を紹介します。

ステップ5

「四則演算のできる言語の作成」

9cc.c

#include <ctype.h>

...

int main(int argc, char **argv) {
  ...

  // アセンブリの前半部分を出力
- printf(".intel_syntax noprefix\n");
  printf(".globl main\n");
  printf("main:\n");

  // 抽象構文木を下りながらコード生成
  gen(node);

  // スタックトップに式全体の値が残っているはずなので
  // それをRAXにロードして関数からの返り値とする
- printf("  pop rax\n");
+ printf("  ldr x0, [sp], 16\n");
  printf("  ret\n");
  return 0;
}

解説

• pop raxの処理をLDR命令を用いて書き変えます

https://github.com/masatomoty/d9cc/tree/main/step5

ステップ6

「単項プラスと単項マイナス」

アセンブリのコードに関連する処理が無い章なので，修正差分はありません。

https://github.com/masatomoty/d9cc/tree/main/step6

ステップ7

「比較演算子」

9cc.c

#include <ctype.h>

...

void gen(Node *node) {
  if (node->kind == ND_NUM) {
...
  case ND_EQ:
-   printf("  cmp rax, rdi\n");
-   printf("  sete al\n");
-   printf("  movzb rax, al\n");
+   printf("  cmp x0, x1\n");
+   printf("  cset x0, eq\n");
    break;
 case ND_NE:
-   printf("  cmp rax, rdi\n");
-   printf("  setne al\n");
-   printf("  movzb rax, al\n");
+   printf("  cmp x0, x1\n");
+   printf("  cset x0, ne\n");
    break;
  case ND_LT:
-   printf("  cmp rax, rdi\n");
-   printf("  setl al\n");
-   printf("  movzb rax, al\n");
+   printf("  cmp x0, x1\n");
+   printf("  cset x0, lt\n");
    break;
  case ND_LE:
-   printf("  cmp rax, rdi\n");
-   printf("  setle al\n");
-   printf("  movzb rax, al\n");
+   printf("  cmp x0, x1\n");
+   printf("  cset x0, le\n");
    break;
  }
}

解説

• 比較演算子CMPはx86-64とARM64で同名です
• SETLはCSETで書き変えます
• CSETは条件コード（EQ,NE,LT,LE）に応じてレジスタに0か1をセットします

https://github.com/masatomoty/d9cc/tree/main/step7

ステップ8

「ファイル分割とMakefileの変更」

これまで作ってきたコードのファイル分割する章です。修正差分はありません。

https://github.com/masatomoty/d9cc/tree/main/step8

ステップ9〜11

「1文字のローカル変数」
「複数文字のローカル変数」
「return文」

元記事の説明とリファレンス実装のcommitで，順序が一部入れ替わっているため，理解に時間を要しました。本記事ではリファレンス実装の順に則って説明します。

セミコロン区切りで複数の文

アセンブリに関する修正差分はありません。

https://github.com/masatomoty/d9cc/tree/main/step9_11/1_semicolons

Accept multiple statements separated by semicolons

return文

codegen.c

#include "9cc.h"

void gen(Node *node) {
...
　case ND_EXPR_STMT:
    gen(node->lhs);
-   printf("  add rsp, 8\n");
+   printf("  add sp, sp, #16\n");
    return;
  case ND_RETURN:
    gen(node->lhs);
-   printf("  pop rax\n");
+   printf("  ldr x0, [sp], 16\n");
    printf("  ret\n");
    return;
...
}

解説

• スタックポインタのインクリメントを8バイトから16バイトに変更します
• これまでのステップと同様にPOPをLDR命令で書き換えます

https://github.com/masatomoty/d9cc/tree/main/step9_11/2_return

Add "return" statement
Add the notion of the expression statement

1文字のローカル変数

codegen.c

#include "9cc.h"

void gen_addr(Node *node) {
  if (node->kind == ND_LVAR) {
    int offset = (node->name - 'a' + 1) * 8;
-   printf("  lea rax, [rbp-%d]\n", offset);
-   printf("  push rax\n");
+   printf("  sub x0, x29, #%d\n", offset);
+   printf("  str x0, [sp, -16]!\n");
    return;
  }
  error("not an lvalue");
}
void load() {
- printf("  pop rax\n");
- printf("  mov rax, [rax]\n");
- printf("  push rax\n");
+ printf("  ldr x0, [sp], 16\n");
+ printf("  ldr x0, [x0]\n");
+ printf("  str x0, [sp, -16]!\n");
}
void store() {
- printf("  pop rdi\n");
- printf("  pop rax\n");
- printf("  mov [rax], rdi\n");
- printf("  push rdi\n");
+ printf("  ldr x1, [sp], 16\n");
+ printf("  ldr x0, [sp], 16\n");
+ printf("  str x1, [x0]\n");
+ printf("  str x1, [sp, -16]!\n");
}


void gen(Node *node) {
...
  case ND_RETURN:
    gen(node->lhs);
    printf("  pop rax\n");
-   printf("  jmp .Lreturn\n");
+   printf("  b .Lreturn\n");
    return;
  }
...
}

void codegen(Node *node) {
...
  // Prologue
- printf("  push rbp\n");
- printf("  mov rbp, rsp\n");
- printf("  sub rsp, 208\n");
+ printf("  stp x29, x30, [sp, -16]!\n");
+ printf("  mov x29, sp\n");
+ printf("  sub sp, sp, #416\n");

...

  // Epilogue
- printf(".Lreturn:\n");
- printf("  mov rsp, rbp\n");
- printf("  pop rbp\n");
+ printf("  .Lreturn:\n");
+ printf("  mov sp, x29\n");
+ printf("  ldp x29, x30, [sp], #16\n");
...
}

解説

• スタックマシンの章で説明したようにPUSHとPOPの処理を書き換えます
• JMPはb .Lreturnで書き換えます
• プロローグとエピローグは前述した通りです

https://github.com/masatomoty/d9cc/tree/main/step9_11/3_single_local_var

Support single-letter local variables

複数文字のローカル変数

codegen.c

#include "9cc.h"

void gen_addr(Node *node) {
  if (node->kind == ND_VAR) {
-   printf("  lea rax, [rbp-%d]\n", node->var->offset);
-   printf("  push rax\n");
+   printf("  sub x0, x29, #%d\n", node->var->offset);
+   printf("  str x0, [sp, -16]!\n");
    return;
  }
  error("not an lvalue");
}

void codegen(Node *node) {
...
- printf("  sub rsp, %d\n", prog->stack_size);
+ printf("  sub sp, sp, #%d\n", prog->stack_size);
...
}

main.c

#include "9cc.h"
int main(int argc, char **argv)
{
  ...
  for (Var *var = prog->locals; var; var = var->next)
  {
-   offset += 8;
+   offset += 16;
    var->offset = offset;
  }
  ...
}

解説

• ここまで出てきたスタックマシンの処理に関する書き換えが中心です
• main.c内でハードコーディングされているオフセットを8から16に修正します

https://github.com/masatomoty/d9cc/tree/main/step9_11/4_multiple_local_var

Support multi-letter local variables

感想

• 単純な写経ではなく，ARM64への書き換えを行うことで，アセンブリの命令の具体的な内容やスタックマシンの仕組みについて理解が深まった
• ステップ4ぐらいまではChatGPTと写経でスラスラ進められた
• スタックマシンの操作が出てきてからChatGPTでも毎回アセンブリのコードの書き方が揺らいでしまい，余計に混乱してしまった
• コンパイラ・パーサー・BNF・スタック・アセンブリなど，低レイヤーに関する知識を学べるだけでなく，プログラミングに関する様々なテクニックも同時に得られるのが非常に秀逸な教材と感じた
• 低レイヤーに関する知識も深まってきたので，RubyやTypeScriptの言語処理についても今後学習してみようと思います

---

MICINではメンバーを大募集しています。
「とりあえず話を聞いてみたい」でも大歓迎ですので、お気軽にご応募ください！
https://recruit.micin.jp/