1.はじめに

これは Mobility Technologies Advent Calendar 2020 の 15日目の記事です。

Mobility Technologies (MoT) は今年の4月に旧JapanTaxi社と旧DeNA Automotive が事業統合してできた会社です。GOという配車アプリを提供しています。タクシー起点の交通リアルテック×AI大活用でサービス開発していますので、よろしければぜひMoT技術ブログを御覧ください!

明日は @tstomoki の「リモートワークで自転車に乗り始めてインスタグラマーになった話」です。

これは何

この記事は、C言語のコンパイラ開発の概要と、その中でもそれなりに手ごわかった x64 の ABI (呼び出し規約: Application Binary Interface) について一部を説明したものです。

少々ポエムも含まれております。

コンパイラ開発の敷居は意外と低いということと、低レイヤ周りの楽しさが少しでも伝われば幸いです。

開発のきっかけ

さて、エンジニアなら皆一度はコンパイラ書いてみたいですよね？

私はこれまで、javac を少し改造して null safe operator (foo?.bar の ?.部分) を追加してみたり、Hindley-Milner型推論のサンプルを実装したり、あるいは ANTLR(Java用のパーサー生成ライブラリ) でサイト訪問者の適用対象キャンペーンをリアルタイムに決定するためのSQLライクなDSL を作ったり、とコンパイラ開発に近い領域を軽く見聞きしたことはあったものの、コンパイラをまともに作ったことはありませんでした。

そんな中、数年前によく聞いていた Turing Complete FM (@ruiu さん提供) という Podcast で、C言語コンパイラのセルフホストの話がしばしば話されており、低レイヤ好きとしてはこれはいつかやりたいと思っていました。

セルフホストとコンパイラの世代

セルフホストとは、あるコンパイラのソースコードをそのコンパイラ自身がコンパイルできるということです。

何を言っているのかよくわからないかもしれませんが、例えるなら色々な部品を作れるロボットがあったして、そのロボットが自分自身を組み立てられる、という状況が近いかもしれません。

C言語に限らず、あるプログラム言語の全仕様を完全にサポートしたコンパイラであれば当たり前のことですが、自作でコンパイラを作る場合にそこまで仕上げることはちょっとしたチャレンジではあります。

もう少し具体的には以下のようになります。

C言語コンパイラ(仮に mycc と呼ぶとします) を作り、既存のコンパイラで mycc のソースコードをコンパイルしてできたバイナリを第一世代と呼びます。

その mycc のバイナリで再び mycc のソースコードをコンパイルしてできたバイナリを第二世代と呼びます。これがきちんと動作していればセルフホストは成功ということです。

その「きちんと動作していれば」を検証する一つの方法として、さらに第二世代で mycc をコンパイルして、その結果の第三世代のバイナリと第二世代のバイナリが一致していることを確認するという方法があります。

開発の動機

とはいえ、セルフホストできるコンパイラを作ることの何がいいのかさっぱりわからないと思います。

一番に来るのは完全に趣味で、それをやってみたかったから、に尽きます。他にあえて理由をあげるとすれば

コンパイラという一定の規模があるプログラムを扱えるというのは、「ちょっとやってみた」よりははるかに複雑なもの。それを自力で作れるかどうかの力試し
自分自身を生み出せるプログラムということで、いったいこのバイナリはどこから出てきたんだ？という不思議な感覚に浸れる。タイムマシーンを発明した人が過去に戻って自分に作り方を教えたら、タイムマシンを作る知識はどこから出てきたんだ的な、あるいは鶏と卵どっちが先というのが解決した世界を実感できるというか。。。

※画像は本文とは関係ありません / Thanks to pixabay

経過

ということで、まだコロナも「武漢が大変らしい」くらいの認識だった2020年の正月休みに思い立ってやり始めることにしました。

今回は、特に以下の記事を参考にしました。ただ、写経してしまうと面白くないので、できるだけコードレベルの情報は見ずに自分で作ってみる、という縛りでやることにしました。

https://www.sigbus.info/how-i-wrote-a-self-hosting-c-compiler-in-40-days
Cコンパイラをスクラッチから開発してみた（日記） ※ご本人による↑の日本語版の記事がQiita にありました
- 先に挙げた Turing Complete FM で話されていたもので、40日間で 8cc というCコンパイラを作ったという記事です
https://github.com/DoctorWkt/acwj
- どうやって見つけたか忘れてしまいましたが、セルフホストできるCコンパイラの開発のステップが具体的な実装も含めて説明されています

※その後、丁寧すぎる入門用の日本語テキストが公開されました!

低レイヤを知りたい人のためのCコンパイラ作成入門
- ただ、こちらはC言語仕様に対するカバレッジはまだまだこれからというところで、やはり上記の2つも併せて見ていくのが良いかと思います

着手後は、コロナもさることながら、会社が事業統合したり、下の娘が生まれたり、上の娘がハイパーイヤイヤ期に突入したり、上の娘の寝かしつけに毎日一時間かかったり、上の娘が「おなかすいた」→ごはんをあげる→遊んで食べない→じゃご馳走様しなさいと言われる→泣く→お父ちゃん涙を拭いて、と命令される→拭く→お腹すいたとゴネる→以下繰り返し……に付き合わなければならない、などと開発以外の苦労もなかなかでした。

途中1-2ヶ月手を付けられない時期もありましたが、10月になってようやくセルフホストに成功！

完成したコンパイラ自体は粗削りですが、つらく楽しい道のりでした。

終わってみての感想は以下のようなところでしょうか。

より複雑なコンパイラも作れる自信がついた（やる気が出てきた）。
- Go言語はGCもあるし goroutine もあるので次の題材としては面白そう
- 各種の最適化手法について今回はほとんど何もしていないが、今後は実装していきたい
- LRパーサーは「LLに縛られない文法の言語を作りたい!」という欲求がない限り手を出さないほうが良さそう
C言語の仕様（特に、どこまで変な書き方が許容されるのか）に詳しくなった。
- どの言語仕様までが C89 の範囲なのか
- #de/*comment*/fine と書けるのかどうかなど（NG)
- 細かいところでは sizeof の後ろにカッコがいらないことに気づいたり
言語仕様通りのソースをコンパイルするのが精一杯で、「変なソースコード」を「ここはこれの間違いじゃない？」と修正提案するなどはめちゃめちゃ大変
先人達は（メモリ制約やCPU・ディスクが遅くてつらい）8bit や 16bit の時代に、こんな複雑なものを商用品質で作り上げていたというのは本当にすごい

特に、関数を呼び出す部分での x64 ABI の理解と対応はかなり苦労しまた。この苦労はコンパイラ開発の本質なのか本質でないのか?? 言語を作りたいならば、アセンブラソースまで落とし込まなくても、LLVMや、もっというとC言語のソースを出力するアプローチ(例:Vlang)にして、バイナリへの変換は専門家に任せる方が効率的ではないか、という気もしてきます。

そのほか一般論になってしまいますが、コンパイラのように複雑なプログラムは事前の設計が本当に重要。しかし、現実的にはかなりのところまで開発を進めないと良い設計の勘所はわからない。そのため、一度ラフに書ききってしまい改めてゼロから書き直す、くらいの計画が良いと改めて思います。

完成したコンパイラ

https://github.com/reki2000/rcc

Linux x64 向け
ANSI C89 を基本に、一部 C99 あたりまでの言語仕様が混じったもの
- 変数宣言がブロック先頭以外でもできる
LP64 (int:32bit, long:64bit, pointer:64bit)
LL(1) っぽい手書きの左再帰下降型パーサー
生成するコードは基本的にはスタックマシン
- 空いているレジスタがあればスタックは使わないという単純なレジスタ割り付けあり (SSAは未対応)
セルフホストの実現には不要なため、未対応の言語仕様も多い。例えば
- unsigned 型
- 小数型(float, double)
- 構造体の値戻り
- __FILE__ などいくつかの特殊マクロ
- 関数型およびポインタからの関数呼び出し
- 可変長引数マクロ
- static、goto

このコンパイラはまだまだ設計を修正したいところが多くある状態のため、これからコンパイラ開発をしたい、ソースレベルで具体的なものを見たい、という方は前述のドキュメントとそのソースコードを見られることをお勧めします。

ちなみに、ソースコードが公開されているものでC言語仕様を完全カバーしたコンパイラとしては、エンジニアの Fabrice Bellard 氏(QEMU や FFmpeg を作った方。尊敬！)が1632bit時代に作った TCC も有名です。こちらはx86バイナリ出力までコンパイラがやり切っています。こちらのソースはちょっと高度すぎて、よくこんなスタイルで書ききったなというほかありません。

2. C言語のコンパイラを作るとはどういうことをやるのか

コンパイラの作り方については、前述の資料など、とてもよい解説がたくさんあるのでこの記事ではあまり深く述べません。この記事では、開発の出だしの部分、開発の敷居の低さを伝えられそうな範囲のみにしました。

今回挑戦したコンパイラは 8cc のアプローチを参考にして、「C言語のソースコードを入力するとアセンプラソースコードを出力する」というものにしました。最終的にOSが実行できるバイナリに変換したり、elf にリンクするするところはスコープ外で、ここは既存のアセンブラやリンカを使っています。

セルフホストに最低限必要な言語仕様の絞り込み

セルフホストできるコンパイラを作るうえで、「言語仕様をどこまでサポートするか」を最初に設定する必要があります。でなければ、C言語の仕様を全部実装しないとセルフホストできないということになり、かなりハードな趣味になってしまいます。

今回は以下の範囲を設定しました。

型のサイズは LP64 (int は 32bit、ポインタは64bit)
型は int, char のみ対応 (float, double はもちろん、unsigned も対応しない)
マクロ、可変長引数は後回し
libc への依存を最低限にする (そうしないと、libc の関数を呼ぶために include する各種ヘッダの中で使われている文法に全部対応しなければならない)

後から振り返ると、「文字列の key から値を引けるマップ(map)」と、「サイズを動的に拡張できる配列(vector)」を扱うユーティリティ関数を作っておくべきでした。単純になるかと期待して、「固定長で構造体の配列を確保し、順次割り当てていく」設計にしてしまったのですが、これは逆にコードの見通しが悪くボイラープレートが沢山できるものになってしまいました。

この他、デバッグ文字列を簡単に組み立てて出力するユーティリティなどの準備も、最初から厚めに準備しておく必要がありそうです。libcをなるべく使わない方針とのバランスが難しいところです。

コンパイラのビルド・テスト環境の構築

続いてコンパイラの開発を行うための枠組みを作ります。

linux 環境で gcc など既存のコンパイラでアセンブラソース用のガワを作る。
コンパイル環境の構築 - 1つのソースコードを読み込んでアセンブラソースを出力し、さきほどのガワに埋め込んでアセンブラにかけてバイナリをつくる
テスト環境の構築 - ソースコードごとに、できたバイナリを実行して期待する結果と一致しているか確認する

今回は Makefile 主体とし、テストは bash script で対応することにしました。

対応できる言語仕様を成長させていく

コンパイラ作成の流れは、以下のようなサイクルを繰り返して少しずつC言語の仕様に近づけていくというものになりました。

まず BNF という記法で言語の構文を書く
BNFのトークン定義部分に沿って、ソースコード文字列をトークンに変換する Tokenizer を作る。これは最初のほうのサイクルでほぼ終えてしまえるが、特にデバッグ表示をリッチにするために、あとから修正することもしばしば
BNFの構文定義部分に沿って、トークンを AST(抽象構文木) とよばれるツリー構造に再構成する Parser を作る。ここがコンパイラのキモですが、最適化を頑張らなければそこまで複雑ではなく、どちらかというとBNFをコード化していくという肉体労働な面があります。
AST の各ノードを対応するアセンブラの文字列に変換する Code Generator を作る。ここは低レイヤ感が半端ない
生成されたバイナリを実行し、想定通りの結果になるか、テストする

それぞれのサイクルで一度にどこまでの言語仕様をカバーしていくのかを考えることも楽しい部分です。

最初は四則演算、次に変数への代入と参照、int/char型と変数宣言の導入、関数定義、その他の演算子、ポインタと配列、struct/union/enum、typedef、if/for/while/switch、グローバル変数、変数の初期化、#include、#ifdef＆マクロ…… とここまでやればセルフホストに十分な言語仕様を持つ状態になりそうです。

3. コンパイラ開発の最初のステップの例

前述の各ステップの進め方について、最初の部分のみになりますがもう少し具体的に見ていきます

アセンブラソースのガワを作る＆どういうソースが必要か理解する

シンプルですが hello world 以上の複雑さ、ということで fibonacci を計算して出力するコードを題材にすることにします。

hello.c

#include <stdio.h>

int fib(int n) {
  return (n<=2) ? 1 : fib(n-1) + fib(n-2);
}

int main() {
  int a = fib(10);
  printf("%d",a);
  return 0;
}

gcc でアセンブラソースを出力してやります。

出力されるコードからデバッガ用の不要な行 (.cfi_で始まる行: Call Frame Information) を取り除いて表示してみると、以下のようになります。

コメントで内容の説明を付けました。
このアセンブラソースコードは AT&T 表記のため、よく見られる Intel 表記とは異なり、レジスタ名の先頭に % がついています。レジスタの記述順も Intel と AT&T では逆で、mov %r1, %r2 は R1の内容をR2にコピー になります。
x64 では 32bit レジスタ (%eax など %e... で始まる名前のレジスタ) に値をセットしたり演算結果をセットしたりすると、対応する 64bit レジスタ (%rax など %r... で始まる名前のレジスタ) の上32 bit は0でクリアされます。この時、符号拡張はされません。32bit で済ませたほうが最終的なバイナリのバイト数が減るため、下記のアセンブラソースコードでも下32bit だけを使えばよい場合は 32bit レジスタへの値のセットで済ませています。この動作は32bitレジスタの場合のみで、16bitレジスタ(%axなど)や8bitレジスタ(%alなど)にセットしても上位bit はクリアされません)

$ gcc -o hello.s -S -c hello.c
$ grep -v '.cfi_' hello.s

        .file   "hello.c"

        .text
        .globl  fib                 # ここからが関数 fib の宣言部分
        .type   fib, @function
fib:
.LFB0:
        pushq   %rbp
        movq    %rsp, %rbp          # %rbp が変数格納エリアの先頭
        pushq   %rbx                # %rbx は壊してはいけないレジスタなので保存
        subq    $24, %rsp           # 変数格納エリア用に %rbp から 24bytes 確保する。その分 %rsp をずらす
        movl    %edi, -20(%rbp)     # %edi は第一引数の値を入れるレジスタ。それを 変数 n 用の領域 (-20) に格納
        cmpl    $2, -20(%rbp)       # n<=2?
        jle     .L2                 # ならば .L2 へ

        movl    -20(%rbp), %eax     # 変数 n の値を改めて %eax に読み込み
        subl    $1, %eax            # 1 を引く (n-1)
        movl    %eax, %edi          # 第一引数用レジスタ %rdi に n-1 の値をセット
        call    fib                 # 再帰呼び出し
        movl    %eax, %ebx          # 結果を %ebx に退避しておく
        movl    -20(%rbp), %eax     # あらためて n の値を %eax に読み込み
        subl    $2, %eax            # 今度は n-2 を計算
        movl    %eax, %edi          # 第一引数用レジスタ %rdi に n-2 の値をセット
        call    fib                 # 再帰呼び出し
        addl    %ebx, %eax          # fib(n-1) + fib(n-2) の加算結果を 戻り値用レジスタ %eax にセット
        jmp     .L4
.L2:
        movl    $1, %eax            # 1を戻り値用レジスタ %eax にセット
.L4:
        addq    $24, %rsp           # return の準備で %rsp を復旧
        popq    %rbx
        popq    %rbp
        ret                         # ここまでで fib が終了
.LFE0:
        ret                         
        .size   fib, .-fib          

        .section        .rodata
.LC0:
        .string "%d"                # 文字列定数はこのように定義される 

        .text                       # ここからが関数 main の宣言部分
        .globl  main
        .type   main, @function
main:
.LFB1:
        pushq   %rbp
        movq    %rsp, %rbp          # %rbp が変数格納エリアの先頭
        subq    $16, %rsp           # 変数格納エリア用に %rbp から 16bytes 確保する。その分 %rsp をずらす
        movl    $10, %edi           # 第一引数用レジスタ(%rdi)に10をセット
        call    fib                 # fib を呼び出す
        movl    %eax, -4(%rbp)      # 戻り値 %eax の内容を オフセット -4 (変数a) に格納

        movl    -4(%rbp), %eax      # 変数aの値を改めて取得 (最適化すればここはいらない)
        movl    %eax, %esi          # 変数aの値を 第二引数用のレジスタ %rsi にセット 
        leaq    .LC0(%rip), %rdi    # "%d" のアドレスを第一引数用レジスタ %rdi にセット
        movl    $0, %eax            # 可変長引数関数呼び出しでの x64 ABIのおまじない (引数に含まれる浮動小数レジスタの数 0個をセット)
        call    printf@PLT          # printf を呼び出す。@PLT は外部の関数の場合に必要
        movl    $0, %eax            # return したい値は %eaxに入れる
        leave
        ret                         # ここまでで main が終了
.LFE1:
        .size   main, .-main
        .ident  "GCC: (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0"
        .section        .note.GNU-stack,"",@progbits

少し長いですが、そこまで複雑なことはしていないことがわかると思います。このガワの中に以下の内容が含まれていて、これから作るコンパイラが出力すべきコードがどのようなものになるべきかがおおよそ見て取れます。

関数をどのように記述するか
変数格納エリアをどのように確保するか
変数への値のセットや読みだしはどのようなコードになるか
グローバルな値 ("%d") をどのように確保するか
関数をどのように呼び出すか

以降は、このガワの中の関数の処理の部分に、我々のコンパイラが生成したアセンブラのソースコードを埋め込んでいくことになります。関数が複数ある場合も上記の fib のように main と同様の内容を関数名を変えて出力することになります。

なお、実行結果を出力する方法が最初のうちは何もないため、コンパイラ開発終盤になるまで、レジスタの値を出力したいときにはここにある printf の呼び出しコードを使いまわすことにしました。

※プログラムの戻り値にするという手もありますが、32bit の値はそのまま返せず、0-255までにカットされてしまい扱いづらい面があります (bash側の制限)

gcc という巨人の肩にのってのコンパイラの最初の一歩、意外と何とかなりそうな気がしませんか。

以降でも、どのようなアセンブラソースを出力すればよいかわからない場合はこのやり方で答えを知ることができます。

最初の Tokenizer

続いて、ファイルを読み込み、空白文字に挟まれた文字をトークンとして取り出していく処理を作ります。

予約語や演算子はそれぞれ専用のトークンに。数字で始まるものは数値トークンに、ダブルクオートで始まるものは文字定数に、それ以外を ident (識別子) トークンに切り出してトークンの配列を作ります

// や /* .. */ のコメントの読み飛ばし処理はここでやります。

C言語は行末に \ と書くと改行を無視してくれるのですが、それが1行コメントにも適用されるのか、など細かいところの把握に結構手間取ります。

また、コンパイルエラーの際に該当するソースコードの位置を出力してやる必要があるので、現在の行や桁位置もあわせてトークン内に覚えていくようにします。

  5 +  3*2  // comment
  - 20/(1+4)

のような文字列が、コメントや改行などを取り除いた

INT:5 '+' INT:3 '*' INT:2 '-' INT:20 '/' '(' INT:1 '+' INT:4 ')'

というようなトークンの並びに変換されます

ここはそれほどややこしい話はありません。そう、マクロの対応をするまでは……

四則演算の Parser

上記のようなトークンの配列に対して、BNF(に似た独自構文でよい) に沿ってパースし、合致したルールをノードとしてAST(抽象構文木)を構築していきます。

手初めてとして「カッコ付き四則演算」の式のBNFは以下のようなものになります。

#「カッコ付き四則演算式」を expr という名前で定義
expr: add  

# 加減乗除は 上位の要素を '+' などで連結したもの、と定義してやる
# 先に定義したものが後からパースされる = 計算の優先順位が低くなる
add: mul ( ( '+' | '-' ) mul )* 
mul: primary ( ( '*' | '/' ) primary )*

# 丸カッコがあるとその中にある expr を再帰的にパースする
primary: INT | '(' expr ')' 

# 数値リテラル。実際は 0x.. 表記や 先頭0は8進数 などの仕様があるのでもっと複雑
INT: ['0'-'9']+

これをたどっていくLL(1) 左再帰下降型パーサーを書いていくことになります。BNFの１行にたいして parse_なになに という関数を一つ書いていくイメージです（他によい教材がたくさんあるのでこの記事では割愛します）。

ASTの各ノードをどのようなデータ構造で表現するか、どのような単位で分類するか、というのは設計が楽しいところです。例えば加算や減算に対してそれぞれ Add, Sub など別の種類のノードを作るのか、Binop (2項演算子)という単位でいったん大分類するかなど。

さて、パーサーによって、

INT:5 '+' INT:3 '*' INT:2 '-' INT:20 '/' '(' INT:1 '+' INT:4 ')'

のようなトークン列が、演算子の優先順位やカッコも考慮した上で以下のような AST に変換されます (YAMLで表現してみました)

Add
 - Integer(5)
 - Sub 
   - Mul 
     - Integer(2) 
     - Integer(3)
   - Div 
     - Integer(20) 
     - Add 
       - Integer(1) 
       - Integer(4)

最初の Code Generator

高度なコンパイラでは、この後 SSA形式への変換という、レジスタ割り付けをしやすくする最適化処理が入るのですが、今回は以下で説明する「スタックマシン」なこともあるのでそこまではやらず（やれず）、ASTを直接アセンブラソースに変換していきます。

ということで今回はスタックマシンで実装することにしました。

スタックマシンは、各ASTノードを評価した結果をスタックに詰んでいくだけのシンプルな構造です。ノードを評価するごとに、結果をレジスタに保持せず毎回メモリに書き出していくので、その分、実行効率は悪くなります。しかし（繰り返しになりますが）本当にシンプルです。

例えば 2つの子ノードの値を加算する Add ノードが来た時の処理は

一つ目の子ノードを評価するソースコードを出力 (再帰呼び出しする)
二つ目の子ノードを評価するソースコードを出力 (再帰呼び出しする)
スタックの一番上とその次の値をとりだし、加算して結果をスタックに push するアセンブラソースを出力

具体的には

void compile(Node node) {
   ...
  case NODE_ADD:
    compile(node->lhs);
    compile(node->rhs);
    pop("%rdx");
    pop("%rax");
    gen("addq %rdx, %rax");
    push("%rax);
    break;
  ...

という処理になります。

そうすると以下のようなアセンブラソースが出力されます

 ...                # 一つ目の子の評価
 pushq %rax         # 子の評価の最後に結果がスタックに積まれる
 ...                # 二つ目の子の評価
 pushq %rax         # 子の評価の最後に結果がスタックに積まれる
 popq  %rdx
 popq  %rax
 addq  %rdx, %rax   # それぞれの子の値を加算する
 pushq %rax         # 結果をスタックに詰む
 ...

このようなサイクルを繰り替えし、少しずつ言語仕様を大きくしていくことになります。

4. その後

特に第二世代のデバッグになってくると Segmentation Fault で落ちるか無限ループするかということもしょっちゅうです。デバッグ情報を出力していないので gdbで追うのもつらく、printfデバッグを大量にいれつつ、バグを再現する最小のテストコードをコンパイラソースコードから抜き出して第一世代の出力と第二世代の出力を比較する、というようなこともやりました。

落ちた場所（たとえば比較ロジックの実行部分）が分かっても、コンパイルしているソースのどの部分のコンパイル中なのかがわからないとどうしようもないため、なるべく細かい情報をコンパイル中に表示するようにもしました。

多かったのは、typedef した型のサイズ計算が間違っていて他の変数の値と同じアドレスを指してしまったとか、ゼロクリアするしないの違いで末尾ゼロなし文字列ができてしまい文字列操作が飛んでしまったりとか、今回は対応しなかったが領域だと確保する必要があった浮動小数点レジスタのサイズを 64bit と勘違いしていた (実際は128bit）、など、原始的なものではありました。

そして、以下の敵が非常に手ごわかったのが印象深いです。

ラスボス、x64 ABI と構造体の値渡しと可変長引数

x64 に限らず、実行可能なバイナリには関数呼び出しの際にどのように引数や戻り値を受け渡しするかについて規約があります。この規約は ABI (Application Binary Interface) と呼ばれ、x64用で広く使われているのは Microsoft のもの(Windows用) と Linux 用のものです。これらは少し異なっていて互換性がありません。

正式版の資料は System V x64 ABI ですが、もう少し読みやすいものが Oracleの資料 AMD64 ABI にあります

今回のコンパイラでは割愛した浮動小数点レジスタを除くと、整数引数の受け渡しについて、以下のように規定されています

6つまでの引数はレジスタ渡しする。第一引数から順に %rdi, %rsi, %rcx, %rdx, %r8, %r9
- サイズの大きい構造体や配列の値渡しでは、値そのものはスタックに積み、そのアドレスを引数として渡す
- ただし、引数の値のサイズが 16bytes 以下の時は、「空いているレジスタがあれば」2つ使ってそこに値を直接いれる
6より後の引数は、後ろから順にスタックに積む
戻り値は %rax に入る
- サイズが8bytesを超える値を戻す場合は、呼び出し側がスタックに領域を確保し、%rax にそのアドレスをいれて呼び出す
関数呼び出し時のスタックのアラインメントは16bytes ※これが厄介

x86 (32bit) ABI ではすべてスタック渡しだったので、引数はひたすらスタックに積めばよかったのですが、これでは呼び出しのオーバーヘッドが大きくなってしまうため、x64 ABI では一部の引数(整数6つ、浮動小数点数6つ)をレジスタで渡せるようにしています。

さて、ここに構造体の値渡しが絡んでくるとややこしくなります。構造体は、16バイト以下かつレジスタがまだ空いていればレジスタ渡し、そうでなければスタック渡しになります。しかし、6を超える引数が別にあった場合は、引数は後ろからスタックに積んでいく必要があるので、先頭から引数を処理して構造体を発見したらスタックに積む、ということができません。

いったん先頭からすべての引数のサイズを個別に算出してから、それらをレジスタ渡しできるかどうかだけをどこかに記録しておき、その後、あらためて今度は後ろから順にの引数の値を評価し、結果をスタックに積むまたはレジスタにセットする、という手順を踏む必要があります。

今回は整数型しか対応していないので苦労もそこまでではないのですが、小数型の対応をするとこれがさらにややこしくなるということで、対応するのを躊躇しています……

さらに大変なのか可変長引数。呼び出す側はあまり何も考えずに引数の個数だけ前述のルールに従って引数をセットしていけばよいのですが、受け側はトリッキーな処理が必要です。

C言語での va_list va_start() va_end() va_arg() を実装するということです。

32bit 時代の ABI では引数がスタック渡しだったので、受け側の関数ではスタック上のアドレスをそのまま変数のアドレスとして流用してやればそれほどややこしくありません。が、x64 ABI では「先頭の6つだけレジスタで渡ってくるが全部で何個引数があるかわからない」というかなりややこしい状況になります。

この部分の処理はコンパイラに任されています。gcc ではこのような構造体が用意されていました。


typedef struct {
    int gp_offset;              // 整数レジスタで渡された引数の個数 (0-6)
    int fp_offset;              // 同、浮動小数点レジスタ (0-6)
    char *overflow_arg_area;    // スタック渡しされた引数の格納位置の先頭アドレス
    char *reg_save_area;        // レジスタ渡しされた引数の格納位置の先頭アドレス
} * __builtin_va_list;

可変長引数の場合は、レジスタ渡ししてもらってもそれを一旦メモリに格納して、そのアドレスを reg_save_area に入れておき、va_arg() が呼ばれるごとに gp_offset を加算。6になるまでは reg_save_area から8bytesずつ順に値を読み込む、gp_offset が6を超えたら overflow_arg_area から読み込む、という処理をしていく必要がありました。

va_arg() をコンパイラに実装するにあたっては、マクロがあると便利なため、マクロと前後しながら実装していきました。が、マクロはマクロで実装がかなり手がかかるものだったために、どちらを先にやるべきかなかなか悩む羽目に……

そして、スタックの16bytesアライン。これはコンパイル中に pushq popq を出力するたびに内部的に今のスタックのアライン状況を更新してやり、関数呼び出しで値をスタックに積む直前にアライン補正してやる必要がありました。今回の生成コードはスタックマシン型なので、アライン調整した後は気軽に push pop できず気を使いました。

最後の伏兵、マクロと`##`

コンパイラ作成において、C言語のマクロの展開は一苦労です。

Tokenizer で対応をするのですが、特に引数を持つマクロの呼び出しにおいて、展開するマクロ本体の中のマクロ引数を、マクロ呼び出し側の引数の文字列（値ではない）に書き換える必要があります。何のトークンを扱っているのか迷子になることが何度もありました。

そのほか、複数引数を持つマクロ呼び出しでは、当たり前ですがマクロ引数の区切りであるカンマ文字が出現します。しかし、マクロを展開している時点ではまだ言語の文法は意識していないため、このカンマがマクロ引数の区切りなのか、マクロ引数の中の式に出現するカンマなのか、どう区別するのかという問題もありました。

以下の例で行くと、MY_MACRO の後のカッコの中にカンマが3つありますが、最初のカンマは「第一引数の (a=1,b) という式の一部」で、値は bの値である2。真ん中のカンマがマクロ引数の区切りのカンマ。最後のカンマは第二引数の文字列がカンマを含んでいるだけ。後者は先に文字列のトークン化が走るので自然に処理はされるものの、前者はなかなか悩ましいです。結局、マクロ引数を解釈する際はカッコの開閉数をカウントして、カッコの中のカンマは無視することにしました。

#include <stdio.h>
#define MY_MACRO(a,b) printf("%d %s\n", a, b)
int main() {
  int a,b=2;
  MY_MACRO((a=1,b), "hello,again");
}

そしてもっと極悪なものがあります。C言語には ## というマクロがあり、これは「マクロの中でこれが出現したとき、前後のトークンを連結してひとつのトークンとみなす」という働きがあります

そうするとややこしいのがマクロを展開する処理で、ソースコードの文字列を順に tokenize してきた中でこれが出現すると、「ひとつ前の解析済みトークンを文字列にもどして、次のものと結合して、あらためて tokenize 」しなければならない、ということになります。トークンを文字列に戻したり、まだ処理していない「次のトークン」を先に切り出してやる必要があるなど、なかなか手ごわい内容でした。

最後に

とりとめもなく長々と書いてしまいましたが、コンパイラ開発は本当につらく楽しいものでした。設計見直しを何度やったことか……

とはいえ、セルフホストが通った時のやり切った感はなかなかのものがあります。

低レイヤ好きの方や、今使っている言語をとことん理解したい方は、腕試しにぜひセルフホストできるコンパイラの開発に挑戦してみてください！

そして、M1 の 16inch Macbook Pro が出るころまでには aarch64(ARM64)対応をしておきたいです。

参考にしたもの

9cc
- 8cc の後継のコンパイラです。現在は chibicc に引き継がれています
- セルフホストが通った後 9ccのソースコードを見て、自分のものより非常にシンプルだったのでショックかつ参考になりました。
System V Application Binary Interface AMD64 Architecture Processor Supplement (With LP64 and ILP32 Programming Models)
- x64 ABI。ひたすら読み返すことになりました。ver 0.3 だけれども 1.0 は出ているのだろうか?
Introduction to x64 Assembly
- AT&T表記ではないので違いに迷うこともありますが、そもそもアセンブリで書かれた命令の意味が分からない時に、原典として頼りになります
コンパイラ原理・技法・ツール第一般 I
- LL(1)やLR、また SSAの説明はよく理解できました。
- この本は内容がもう古いので今買うなら以下の書籍の方がおすすめとのこと。しかし、どちにもなかなかに高価なのでまだ入手していません
- コンパイラ原理・技法・ツール第二版（通称ドラゴンブック）
- コンパイラの構成と最適化手法
The syntax of C in Backus-Naur Form
- 言語仕様のBNFへの落とし込みに困ったときのカンニングペーパーとして使わせていただきました
cppreference (C Reference)
- そもそもC言語の仕様で分からない時はこちらで調査。バージョンごとの違いも記載されていて助かります

自作Cコンパイラで（x64 ABIと戦って）セルフホストに成功した話