github.com/k-fog/bf

概要∞

大学の実験が一段落ついて暇になったので、 brainf*ckのJITコンパイラを作りました。 JIT (Just-In-Time) とは、実行時にソースコードをコンパイルする方式のことを言います。 今回作成したのは、brainf*ckのソースコードを直接x86_64のバイナリに変換しその場で実行するJITコンパイラです。 x86_64プロセッサで動くUbuntuで動作確認をしています。

brainf*ckのJITコンパイラは様々な人が制作しており、以下のリンク先を参考にしました。

• Adventures in JIT compilation: Part 1 - an interpreter (日本語訳)
• Adventures in JIT compilation: Part 2 - an x64 JIT (日本語訳)
• I made JIT Compiler for Brainf*ck lol (動画)

インタプリタ∞

まずは、brainf*ckのインタプリタを作るところから始めました。 brainf*ckは、8個の命令しか持たないシンプルなプログラミング言語なので、 処理系を書くのはとても簡単です。 プログラムはC言語で書きました。

分岐命令のジャンプ先を先に計算して配列jmpに格納しておくことで、 ソースコードの実行部分は以下のようにシンプルに実装できました。

// void interp(const char *src)
const char *s = src;
unsigned char *p = mem;

while (*s != '\0') {
    switch (*s) {
        case '+': (*p)++; break;
        case '-': (*p)--; break;
        case '>': p++; break;
        case '<': p--; break;
        case '.': putchar(*p); break;
        case ',': *p = getchar(); break;
        case '[': if (*p == 0) s = src + jmp[s - src]; break;
        case ']': if (*p != 0) s = src + jmp[s - src]; break;
    }
    s++;
}

ただ、この関数interpはソースコードを逐次解釈して実行するため、あまり効率がよくありません。

brainf*ckではデータ・ポインタ共にインクリメントかデクリメントしかできないため、 ソースコード中に同じ命令の連続がよく見られます。

例えば、Hello World!と表示する次のプログラム (Wikipediaより引用)にも同じ命令が連続している箇所がいくつもあります。

 ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

しかし、インタプリタの実装言語であるC言語では1以上の数値の足し算ができるので、 5を足すために1の足し算を5回繰り返すのは無駄です。 そこで、JITコンパイルの前段としてbrainf*ckのソースコードをランレングス圧縮 (Run Length Encoding) した中間表現に変換することにしました。

• +++++ → INC 5
• ----- → DEC 5
• >>> → INCP 3
• <<< → DECP 3

のようなイメージです。 中間表現に変換してから命令列を解釈する関数をinterp2 (source)として実装しました。

interpとinterp2それぞれで

• マンデルブロ集合を出力するプログラム
• 素数を列挙するプログラム（255を入力）

の実行時間を計ると、

という結果が得られ、2~3倍高速化することができました。

JITコンパイラ∞

本題であるJITコンパイラ化を進めます。 JITの基本原理は単純で、実行時にメモリへ機械語を書き込み、そこにジャンプするだけです。 しかし、mallocしてそのアドレスにジャンプすればよいかというとそう簡単には行かず、セグメンテーション違反でプログラムが落ちます。

// tmp.c
#include <stdio.h>
#include <stdlib.h>

int main() {
    char *mem = malloc(1);
    mem[0] = '\xC3'; // ret
    ((void (*)())mem)();
    return 0;
}

% gcc tmp.c -o tmp && ./tmp
zsh: segmentation fault (core dumped)  ./tmp

これは、ヒープ領域に実行権限がないためです。 Linuxではシステムコールのmmapやmprotectを使うことで実行可能（PROT_EXEC）なメモリ領域を取得できます。

先程のプログラムを次のように書き換えると、

// tmp2.c
#include <stddef.h>
#include <sys/mman.h>

int main() {
    char *mem = mmap(NULL, 1,
            PROT_READ | PROT_WRITE | PROT_EXEC,
            MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    mem[0] = '\xC3'; // ret
    ((void (*)())mem)();
    munmap(mem, 1);
    return 0;
}

% gcc tmp2.c -o tmp2
% ./tmp2 && echo $?
0

エラーが出ずに実行できました。

メモリに書き込んでいる0xC3はret命令を機械語に変換したものです。 C言語の関数呼び出しはコンパイラによってcall命令に変換されます。 callはスタックに戻り先アドレスを保存した上で指定したアドレスにジャンプする命令です。 そして、retはスタックから戻り先アドレスを取り出しそのアドレスにジャンプする命令なので、 このプログラムは動的に確保したmem内にジャンプした後、何もせずにmain関数の中に戻って来るという動作を行います。

動的に命令を実行できたので、後はbrainf*ckを機械語に変換することができればJITコンパイラの完成です。 ここでひとつ注意しなければならない点があり、 確保したメモリ領域にジャンプする時はC言語の関数として呼び出すためABIを守る必要があります。

機械語への変換については、JITの動作を実際に確認することが目的なので最も単純な方法を選びました。 brainf*ckの各命令に対応するアセンブリをあらかじめ書き、アセンブルした結果をバイト列としてソースコード内に直接埋め込んでいます。 パラメータ部分は一旦0x00としておき、コンパイルの際に値を書き込みます。 入出力はread, writeシステムコールを直接呼び出すようにしました。

// ===== x86_64 binaries =====
/*
mov al, [rdi]
add al, 0x00
mov [rdi], al
*/
unsigned char inc[] = {0x8A, 0x07, 0x04, 0x00, 0x88, 0x07};
unsigned char dec[] = {0x8A, 0x07, 0x2C, 0x00, 0x88, 0x07};
//                                       ^ operand !!
unsigned char incp[] = {0x48, 0x81, 0xC7, 0x00, 0x00, 0x00, 0x00}; // add rdi, IMM32
unsigned char decp[] = {0x48, 0x81, 0xEF, 0x00, 0x00, 0x00, 0x00}; // sub rdi, IMM32

/*
push rdi
mov rsi, rdi
mov rax, 1
mov rdi, 1
mov rdx, 1
syscall
pop rdi
*/
unsigned char out_bin[] = {
    0x57, 0x48, 0x89, 0xFE, 0x48, 0xC7, 0xC0, 0x01, 0x00, 0x00, 0x00, 0x48,
    0xC7, 0xC7, 0x01, 0x00, 0x00, 0x00, 0x48, 0xC7, 0xC2, 0x01, 0x00, 0x00,
    0x00, 0x0F, 0x05, 0x5F
};
/*
push rdi
mov rsi, rdi
mov rax, 0
mov rdi, 0
mov rdx, 1
syscall
pop rdi
*/
unsigned char in_bin[] = {
    0x57, 0x48, 0x89, 0xFE, 0x48, 0xC7, 0xC0, 0x00, 0x00, 0x00, 0x00, 0x48,
    0xC7, 0xC7, 0x00, 0x00, 0x00, 0x00, 0x48, 0xC7, 0xC2, 0x01, 0x00, 0x00,
    0x00, 0x0F, 0x05, 0x5F
};

/*
cmp byte ptr [rdi], 0
je <relative address>
*/
unsigned char jz[] = {0x80, 0x3F, 0x00, 0x0F, 0x84, 0x00, 0x00, 0x00, 0x00};
unsigned char jnz[] = {0x80, 0x3F, 0x00, 0x0F, 0x85, 0x00, 0x00, 0x00, 0x00};

unsigned char ret[] = {0xC3}; // ret

準備は以上で、コンパイルの過程は基本的に各命令に対応する機械語を書き込むだけです。

しかし、[命令は最初の段階ではジャンプ先がわからないため自分のアドレスを一度メモしておき、 対応する]が来たときに両命令のジャンプ先相対アドレスを更新するという方法をとりました。

brainf*ckのデータ領域はmallocで確保し引数として渡しています。 第1引数はrdiレジスタに保存されるので、そのままrdiをbrainf*ckのデータポインタとして使うことにしました。

ここまで説明したJITコンパイラは、 jitc (source)関数として実装しています。

jitcによるプログラムの実行時間を調べると次のような結果が得られました。

mandelbrotの方は当初のインタプリタと比べて約20分の1の時間で実行できています。

まとめ∞

JITコンパイラにより機械語に変換することで、brainf*ckの実行を高速化することができました。 コードの最適化等さらなる改善の余地はありそうですが、動的に機械語を生成でき満足したのでここまでとします。