ここ数年、LunarMLという「スクリプト言語のソースコードを出力する」コンパイラーを書いているわけですが、自分の中でコンパイラーと言ったらやっぱりアセンブリーを出力するものが連想されます。アセンブリーを出力する処理系を書いたことがないのにコンパイラー好きを名乗るわけにはいかないなあと思うので、ここで一念発起してアセンブリーを出力する処理系に取り組んでみようと思います。

以前、

• AArch64でJITしてみる
• Universal MachineのJITコンパイラーを書いた

という記事でレジスターマシンのVMをJITコンパイル（アセンブル？）して実行する処理系を書きました。以前と今回の違いは、今回は機械語ではなくアセンブリーを出力すること、その場で実行するのではなく実行可能ファイルの生成が目標であること、リンクという工程の考慮が必要になること、です。

この記事では、BrainfuckのプログラムをAArch64のアセンブリーに変換するコンパイラーを作ってみます。Brainfuckはコンパイラーを作るのが極端に楽なので最初の一歩に適しているのと、私のメインマシンがM1 Mac miniなのがチョイスの理由です。

資料

JITの記事と被りますが、再掲します。

AArch64の機械語についての公式の情報源は「Arm Architecture Reference Manual」です。以下のリンクからダウンロードできます：

• Arm Architecture Reference Manual Armv8, for A-profile architecture

機械語で関数を呼び出すには、呼び出し規約に関する情報も必要です。これは以下から入手できます：

• Releases · ARM-software/abi-aa
  • ABI for the Arm 64-bit Architecture > Procedure Call Standard for the Arm 64-bit Architecture

Appleのプラットフォーム向けにコードを書く場合は、Appleのマニュアルも参照する必要があります。

• Writing ARM64 Code for Apple Platforms | Apple Developer Documentation

アセンブリーを書く際は各種ディレクティブの知識も必要になります。GNU assemblerのマニュアルに色々載ってそうです：

• Using as

（まあmacOSで使うのはGNU asではなくてAppleの独自拡張が入ったClangなので、GNU asの情報はあくまで参考程度です。アセンブラーに対するAppleの独自拡張はいくつかあるようですが、まとまった情報は見つけられませんでした。）

AArch64でアセンブリー言語によるプログラミング入門という意味では、以下の記事が参考になりそうです（Linuxですが）：

• A Guide to ARM64 / AArch64 Assembly on Linux with Shellcodes and Cryptography | modexp
• Exploring AArch64 assembler – Chapter 1

実際にアセンブリー言語を書く際は、既存のCコンパイラーの動作を参考にすると良いです。Compiler Explorerとかを参考にしましょう。まあCompiler ExplorerにはmacOSには対応してなさそうなのでmacOSの人は最終的には自分でApple clangを動かすことになると思いますが……。

簡単なプログラムを手書きする

まずは簡単なプログラムを手書きしましょう。

終了コード2を返すプログラムは次のようになります：

        .text
        .globl _main
        .align 2
_main:
        mov w0, #2
        ret

Linuxと違ってmacOSではシンボルの先頭にアンダースコアがつきます。C言語の main 関数をmacOSのアセンブラーで書くには _main と書く必要があります。

.align 2 は _main を4バイト境界に揃えるという意味です。「2」は「4」を二進法で書いた時のゼロの個数です。これがないとApple clangが警告を出します。おまじないです。

コメントには // を使います。出典はArm Architecture Reference Manual > C1.2.1 General requirementsの

In Example C1-1 on page C1-225, the sequence // is used as a comment leader and A64 assemblers are encouraged to accept this syntax.

です。このほか、Apple clangはセミコロン ; も行コメントとして受け付けるようです（GNU asだとセミコロンは文区切りになります。非互換性！）。

アセンブル・リンクするにはソースをclangに食わせます。Linuxだったら _main の代わりに main と書いてGCCに与えれば良いでしょう。

$ cat exitcode.s
        .text
        .globl _main
        .align 2  // 4-byte align
_main:
        mov w0, #2
        ret
$ clang exitcode.s
$ ./a.out    
$ echo $?
2

シェルでは特殊変数 $? で直前のプログラムの終了コードを取得できます。うまくいったようですね。

次はHello worldです。普通にやるならputsを使えばいいところですが、Brainfuckに繋げたいのでputcharを使ってHello worldしてみます。

関数呼び出しをするには bl (Branch with Link) 命令を使います。bl命令はx30レジスターをPC（プログラムカウンター）+4（つまり、bl命令の次の命令）に設定し、指定されたラベルにジャンプします。putchar関数を呼び出すには引数を設定した上で bl _putchar すれば良いわけですね。関数から戻る際に使う ret 命令ではx30に入っているアドレスにジャンプすることによって、呼び出し元に戻るという動作を実現しています。x30はリンクレジスターと呼ばれます。

が、何も考えずに bl _putchar してしまうと、元々main関数の戻り先が入っていたx30を上書きしてしまいます。なので、元々のx30の値をスタックに退避させる必要があります。ここでは stp (Store Pair of Registers) 命令を使って、main関数の先頭でx29（フレームポインター）とx30（リンクレジスター）を一緒に退避させます。

stp命令にはpre-index, post-index, signed offsetという3種類がありますが、ここではpre-indexを使います。pre-indexだと先にspをずらしてからspとsp+8に値を書き込みます。アセンブリーで書くと stp x29 x30, [sp, #-16]! となります。最後にびっくりマークがつきます。

なお、AArch64ではスタックが下方向（アドレスが小さくなる方向）に伸びます。

その後、新しいフレームポインター（x29）の値としてspを設定します。この辺はおまじないじみていて正直私はまだよく分かってません。

putcharは32ビット整数（C言語のint）を一個受け取る関数です。返り値もありますがここでは無視します。AArch64の呼び出し規約では、この場合レジスターw0に引数を設定します。

つまり、C言語で言うところの putchar(0x48) みたいなことをしたければ

        mov w0, #0x48
        bl _putchar

と記述すれば良いということになります。mov命令は16ビットの即値をレジスターに代入できるやつです。即値は十進、十六進（0x から始める）の他にC言語みたいな文字リテラルもいけるようです。

まとめると、putcharを使ってHello worldするプログラムは次のようになります：

        .text
        .align 2
        .globl _main  // Linuxの場合は .globl main
_main:  // Linuxの場合は main:
        stp x29, x30, [sp, #-16]!  // x29=the frame pointer, x30=the link register
        mov x29, sp
        mov w0, #'H'  // Apple clangの場合は閉じクォートは必須、GNU asの場合は閉じクォートはあってもなくても良い
        bl _putchar  // Linuxの場合は bl putchar
        mov w0, #'e'
        bl _putchar
        mov w0, #'l'
        bl _putchar
        mov w0, #'l'
        bl _putchar
        mov w0, #'o'
        bl _putchar
        mov w0, #0x20  // 十六進リテラルも使える
        bl _putchar
        mov w0, #'w'
        bl _putchar
        mov w0, #'o'
        bl _putchar
        mov w0, #'r'
        bl _putchar
        mov w0, #'l'
        bl _putchar
        mov w0, #'d'
        bl _putchar
        mov w0, #'!'
        bl _putchar
        mov w0, #'\n'
        bl _putchar
        mov w0, #0  // 終了コード
        ldp x29, x30, [sp], #16  // frame pointerとlink registerを復帰させる
        ret

Linuxの人は適宜改変してください。

Brainfuckコンパイラー

Brainfuckの仕様はWikipediaあたりを見てください：

• Brainfuck – Wikipedia

と言っても仕様と言うほどのことは書いてませんが……。ポインターが指す先の大きさ（ワードサイズ）が何ビットなのかとか、入力がEOFに遭遇した場合はどうするのかとか、実装依存な項目が結構あります。

ここでは簡単のために

• ポインターが指す先は8ビット整数とし、オーバーフローの際はwrap aroundする
• 入力はC言語で言うところの (unsigned char)getchar() と等価とし、EOFの際には255が得られる
• 配列の大きさは65536

とします。

リファレンス実装をインタープリターとして実装しておくと、以下のようになります：

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

static unsigned char ARRAY[65536];

int main(int argc, char *argv[]) {
    if (argc <= 1) {
        fprintf(stderr, "Usage: %s program.bf\n", argv[0]);
        return 1;
    }
    FILE *f = fopen(argv[1], "r");
    if (f == NULL) {
        fprintf(stderr, "Failed to open input\n");
        return 1;
    }
    char *program = NULL;
    size_t progsize = 0;
    // 頑張ってファイルの内容を program に読み込む
    fclose(f);
    char *ip = program;
    char **stack = NULL;
    size_t stacklen = 0;
    unsigned char *ptr = ARRAY;
    while (*ip != '\0') {
        switch (*ip++) {
        case '>': ++ptr; break;
        case '<': --ptr; break;
        case '+': ++*ptr; break;
        case '-': --*ptr; break;
        case '.': putchar(*ptr); break;
        case ',': *ptr = getchar(); break;
        case '[':
            if (*ptr == 0) {
                // 対応する ']' にジャンプ
                int level = 0;
                while (*ip != '\0') {
                    char c = *ip++;
                    if (c == '[') {
                        ++level;
                    } else if (c == ']') {
                        if (level == 0) {
                            break;
                        } else {
                            --level;
                        }
                    }
                }
            } else {
                ++stacklen;
                stack = realloc(stack, sizeof(char *) * stacklen);
                stack[stacklen - 1] = ip;
            }
            break;
        case ']':
            if (*ptr == 0) {
                --stacklen;
            } else {
                ip = stack[stacklen - 1];
            }
            break;
        }
    }
}

使用するレジスター

Brainfuckをコンパイルして作成したプログラムでは、ローカル変数と呼べるものは一つしかありません。ポインター（上記のリファレンス実装で言うところの ptr）です。今回のコンパイラーでは、このポインターを固定のレジスターに割り当てることにします。

AArch64には汎用レジスターが色々ありますが、ここではx19を選択します。x19はcallee-saved registerで、putchar/getcharを呼び出す際に退避する必要がないのです。callee-saved registerは以前書いたJITでも活用しました。横着といえば横着かもしれません。

もちろん、mainに入った時のx19の値はスタックに保存して、mainから抜ける際に復帰させなくてはなりません。

一時的な計算にはw0とかを適当に使います。

配列

C言語で static unsigned char ARRAY[65536]; とやっていたやつはdataセクションに確保します。これはアセンブラーでは

        .data
_ARRAY:
        .zero 65536

と書けます。Apple clangで同等のCのコードを処理すると .zerofill とかいう謎の指令を出してきましたが、見なかったことにします。

アドレスを参照するのが問題で、textセクションに配置した変数であれば adr (Form PC-relative address) 命令でアドレスを取得できるのですが、Apple clangの場合はセクションが違うのでよくわからんエラー（error: unknown AArch64 fixup kind!）が出ます。解決法は、Apple clangの場合は

        adrp x19, _ARRAY@PAGE
        add x19, x19, _ARRAY@PAGEOFF

として、GNU asの場合は

        adrp x19, ARRAY
        add x19, x19, :lo12:ARRAY

とすれば良いようです（参考：macos – Apple Clang12 LLVM – unknown AArch64 fixup kind – Stack Overflow）。

ともかく、これで配列の初期化とアドレスのx19への代入ができました。

各種命令の実装

それぞれの命令に対応する命令列を見ていきます。

ポインターの移動 >, < ：

        add x19, x19, #1  // >
        sub x19, x19, #1  // <

連続する > や < は一つの加減算にまとめる最適化が可能です（即値として書けるのが4095までなので、4095個まで）。

ポインターの指す先の変更 +, - ：

        ldrb w0, [x19]
        add w0, w0, #1
        strb w0, [x19]

        ldrb w0, [x19]
        sub w0, w0, #1
        strb w0, [x19]

ポインターが指すものを一旦レジスター w0 に取ってきてから変更、書き戻す、という形になっています。

これも、連続する +, - は一つの加減算にまとめる最適化が可能です。

出力 .

        ldrb w0, [x19]
        bl _putchar

引数を w0 に取ってきてから putchar を呼び出します。

入力 ,

        bl _getchar
        strb w0, [x19]

getchar を呼び出した結果は w0 に入っています。

strb (Store Register Byte) 命令はオペランドの下位8ビットを指定されたアドレスに書き込みます。

ループ開始 [

L<n>_start:
        ldrb w0, [x19]
        cbz w0, L<n>_end

対応する「ループ終了」から戻ってくるのに必要なのでラベルを設置しています（<n> のところには実際は番号を入れます）。

cbz (Compare and Branch on Zero) 命令はオペランドの値が0であれば指定されたラベルにジャンプします。相対で±1MBの範囲に飛べます。

ループ終了 ]

        b L<n>_start
L<n>_end:

b (Branch) 命令は無条件ジャンプです。相対で±128MBの範囲に飛べます。

対応する [ から飛んでくるためのラベルを設置しています。

完成品

完成品はGitHubに置きました。

• minoki/brainfuck-aarch64: Brainfuck compiler for AArch64
• https://github.com/minoki/brainfuck-aarch64/blob/b13a77181f653f0cf3497971cb3ccf84b5edcd00/bfcompile.c

試し方は

$ make
$ ./bfcompile hello-simple.bf
$ clang out.s
$ ./a.out

です。Linuxの場合はclangの代わりにgccを使うことになるかもしれません。

echo.bfを試すときはCtrl-Cで終了するようにしてください。下手にCtrl-Dするとえらいことになります。

もう少し大きなプログラムを試したかったら、ELVMの8cc.jsを使って生成するという手があります。

• 8cc.js

が、これで生成したFizzBuzzをコンパイルしたout.sをclangでアセンブルするとcbz命令でerror: fixup value out of rangeというエラーが出ました。ジャンプ先が±1MBに収まらないってことですね。対策が必要そうです。

次のステップ？

Brainfuckコンパイラーは一応できましたが、やっぱりBrainfuckは単純すぎて達成感があまり得られませんでした。達成感のためには関数やローカル変数のある言語をコンパイルしないとダメな気がします。レジスター割り付けってやつもやってみないとです。

オンラインの（アセンブリーを出力する）コンパイラーを作る教材としては

• 速攻MinCamlコンパイラ概説
• 低レイヤを知りたい人のためのCコンパイラ作成入門

などがあります。いずれもAArch64ではありませんが、その辺は自力でどうにかできるでしょう。

もちろん本もあります。私の手元にある本でレジスター割り付けとかも扱ってそうなのは

• 最新コンパイラ構成技法（いわゆるタイガーブック）
• コンパイラ[第2版]（いわゆるドラゴンブック）

です。他の本や資料についてはκeenさんの

• お薦めのコンパイラの本とか | κeenのHappy Hacκing Blog

に紹介があります。

ここに挙げた教材に沿ってやるのか、あるいはつまみ食いしつつ我流でやるかはまだ決めてませんが、6月はアセンブリーを出力するタイプのコンパイラー作りに時間を使いたいと思います。