GNU CとUNIXシステムコールだけで実行時アセンブラ
自分の持っているAndroid携帯端末にC言語コンパイラを入れようとして挫折した。
アプリケーションのクロスコンパイルは難しくないが、コンパイラ自身のクロスコンパイルは難しい。
アセンブラとリンカのクロスコンパイルはもう少し簡単かもしれない。
しかしリンカの段階に備えて、スタートアップファイルなどを適切な場所に配置する必要があるなど、色々面倒。
一方、FORTHのインタプリタ実装を追っている内に、実行時アセンブラを書きたくなった。
仮想マシンインタプリタを回す方式は、ハードウェアの分岐予測が殆ど効かない。
命令フェッチから確定までのパイプライン段数が伸びている近年のプロセッサでは、これはキツい。
一方、FORTHは言語のコア部分が単純なので、アセンブラで構築し易いらしい。
JAVAやECMAscriptやLLVMどころか、pythonなどスクリプト言語までJITコンパイラを積み始めているし、どうせアセンブラを吐くコードを書くなら、実行前アセンブラより実行時アセンブラの方が面白そうだ。
検索してみると、可読性を犠牲にしてまでコンパイラのサイズを最小化したプログラム言語brainfuckをJITコンパイルする人が沢山いるようだ。
で、出来たのが以下のC言語コード。
/* --- ソースコード --- */
#include <sys/mman.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define BUFF_SIZE 30000
#define JIT_SIZE (0x1 << 12 << 4)
typedef unsigned char byte;
static void error_abort(char *msg)
{
fprintf(stderr, "%s\n", msg);
exit(1);
}
static void *dojit(void *start, char *code, size_t length)
{
memcpy(start, code, length);
return start + length;
}
static void rip_patch(int norip, char *addr, void *num)
{
size_t tgt;
unsigned int tgt_32;
if (norip)
tgt = num;
else
tgt = num - ((size_t) addr);
tgt_32 = tgt;
memcpy(addr - 4, &tgt_32, 4);
}
int main(int argc, char **argv)
{
byte buff_body[BUFF_SIZE];
register byte *buff asm("%r12") = buff_body;
void *jit, *jit_start;
register int buff_ptr asm("%rbx") = 0;
if (argc != 2)
error_abort("argc");
{
FILE *fp = fopen(argv[1], "r");
void *loopbuf[3000];
int loop = 0;
int i;
if (NULL == fp)
error_abort("fopen");
jit =
mmap((void *) (((size_t) 0x1 << 31) - JIT_SIZE), JIT_SIZE,
PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
if (MAP_FAILED == jit)
error_abort("map");
for (i = 0; i < BUFF_SIZE; i++)
buff[i] = 0;
jit_start = jit;
while (1) {
int c = fgetc(fp);
if (EOF == c)
break;
switch (c) {
case '>':
jit = dojit(jit, "\x83\xc3\x01", 3);
break;
case '<':
jit = dojit(jit, "\x83\xeb\x01", 3);
break;
case '+':
jit = dojit(jit, "\x48\x63\xc3" "\x41\x80\x04\x04\x01", 8);
break;
case '-':
jit = dojit(jit, "\x48\x63\xc3" "\x41\x80\x2c\x04\x01", 8);
break;
case '.':
jit =
dojit(jit,
"\x48\x63\xc3" "\x48\x8b\x35____"
"\x41\x0f\xb6\x3c\x04" "\xe8____", 20);
rip_patch(0, jit, fputc);
rip_patch(0, jit - 10, &stdout);
break;
case ',':
jit =
dojit(jit,
"\x48\x8b\x3d____" "\xe8____" "\x48\x63\xd3"
"\x41\x88\x04\x14", 19);
rip_patch(0, jit - 7, fgetc);
rip_patch(0, jit - 12, &stdin);
break;
case '[':
jit =
dojit(jit,
"\x48\x63\xc3" "\x41\x80\x3c\x04\x00"
"\x0f\x8e____", 14);
loopbuf[loop] = jit;
loop++;
break;
case ']':
jit =
dojit(jit,
"\x48\x63\xc3" "\x41\x80\x3c\x04\x00"
"\x0f\x85____", 14);
loop--;
rip_patch(0, jit, loopbuf[loop]);
rip_patch(0, loopbuf[loop], jit);
break;
}
}
jit = dojit(jit, "\xe9____", 5);
rip_patch(0, jit, &&end);
fclose(fp);
mprotect(jit_start, JIT_SIZE, PROT_EXEC);
}
asm volatile ("jmp *%3":"=r" (buff_ptr):"0"(buff_ptr), "r"(buff),
"r"(jit_start):"memory", "%rax", "%rcx", "%rdx", "%rsi",
"%rdi","%r8","%r9","%r10","%r11");
asm goto (""::::end);
__builtin_unreachable();
end:
munmap(jit_start, JIT_SIZE);
return 0;
}
/* --- ソースコード完結 --- */
見ての通り、実行時コード生成部分はバイト列をベタ書き。
少なくとも、x86_64マシン上でしか動かない。
C言語のswitchループで書いたbrainfuckインタプリタを別に書いて、コンパイラの出力した各case文の機械語をobjdump -dの逆アセンブル結果を見ながら手動で切り出したものだ。
バイト列とニーモニックを同時に表示してくれるなら、機械語命令に疎くても、切り出し作業は難しくはない。
ちなみに、仮想マシンエミュレータqemuの古い版は、リンカと同じ機能を実装したツールを用意し、コンパイラがリンカに渡すファイルを分析することで、機械語切り出し作業を自動化している。
こうしてベタ書きした機械語コードを実行するのに、私は拡張インラインアセンブラを使った。
asm volatile ("jmp *%3":"=r" (buff_ptr):"0"(buff_ptr), "r"(buff),
"r"(jit_start), "memory", "%rax", "%rcx", "%rdx", "%rsi",
"%rdi","%r8","%r9","%r10","%r11");
コンパイラの最適化レベルが低いなら
goto *jit_start;
と、単にラベルジャンプにしても良かったかもしれない。
しかしこの実行時コード生成器では、brainfuckの'.'や','がC言語の外部関数を呼ぶようにしている。
systemVのC言語関数呼び出し規約では、これら外部関数がある範囲のレジスタなどを好きな様に上書き出来ることを規程している。
ところが、GNU Cはインラインアセンブラ部分を殆ど読まないし、アプリケーション構築時にしか働けないC言語コンパイラでは、実行時に生成されるコードで外部関数が呼ばれるなんて知りようがない。
単なるgoto *jit_start;では、実行時に生成されたコードがレジスタに全く触らないように、コンパイラには見えてしまう。
このため、最適化レベルを上げると、これら余っている様に見えるレジスタをコンパイラは活用してしまう恐れがある。
拡張インラインアセンブラを使うことで、書き換える可能性のある範囲をコンパイラに伝えることが出来る。
ついでに上記の理由により、systemVとは異なる呼び出し規約を使うシステム(Windowsとか)でも、このプロクラムは動作を保証出来ない。
64ビットWindowsなら、
・少なくとも今回使っている整数型では破壊するレジスタの範囲がsystemVのそれを縮小したもの。
・呼び出す関数(fgetcとfputc)の引数が少なく、スタックを使わない。
gccとUNIXシステムコールをWindowsに移植したCygwin環境なら、コンパイルするだけで動作すると思う。
そして、私が今回ハマった問題の解決策が、
asm goto (""::::end);
この一行だ。
私の使ったgcc-4.8.3の場合、これが欠けると上記のC言語コードは最適化レベル-O2以上では暴走した。
gccの吐いたアセンブラコードを見ると、上記コードのendラベルが実行時コード生成の最終処理部分に移動していた。
gccの中身なんて私はさっぱり分からないが、恐らく、endラベルを用いるgoto文を見つけられなかったため、endラベルの管理をコンパイラがサボったからだと思う。
asm文は動作を完了すると直後の文に処理が移る、とgccは見做すそうだ。
endラベルはasm文の直後にあるため、他からendラベルを使う場所が無いならば、endラベルを何処に移そうと問題は生じない。
ちなみに、このasm gotoは何もコードを生成しないため、書く場所は何処でもいい。
しかし本来ならこのendラベル指定は、
asm volatile ("jmp *%3":"=r" (buff_ptr):"0"(buff_ptr), "r"(buff),
"r"(jit_start), "memory", "%rax", "%rcx", "%rdx", "%rsi",
"%rdi","%r8","%r9","%r10","%r11" : end);
上記の様に実行時生成コードを呼び出しているasm文につけるべきものだ。
endラベルへのジャンプは実行時生成コードから行なわれるのだから。
この記法が出来ないように制限されている理由は、GNUのマニュアルによるとコンパイラの内部構造によるものらしい。
裏を返せば、GNU Cの開発者達は好き好んでこの制限をつけているわけではなく、将来の改良でこの制限はなくなると思う。
その時になれば、生成コード呼び出し部分とendラベルへのジャンプ指定が離れた場所にあったら困るはずだ。
以上、拡張インラインアセンブラの機能を活用することにより、GNU C最高レベルの最適化-O3に対しても、上記のC言語ソースコードは正しく動作するバイナリを生成する。
で、最適化を切ったバイナリと比較すると、動作速度に違いを全く見出せない。
大きなプログラムの実行は殆ど、実行時生成コードで行なわれるからだ。
実行時生成コードの品質は、私がベタ書きしたバイト列で決まり、このバイト列に対してコンパイラは何も出来ない。
しかし、最適化への対応が無駄な最大の理由は今回のプログラムが小規模だからだ、と私は言い訳する。
他のコードも沢山含まれるプログラムなら、一部のコードが最適化の足を引っ張るのは問題だろう。
勿論、下の参考URLなどで示されているように、近年ではJITコンパイルを支援するツールが整備されている。
JITアセンブルと違ってコードの最適化までする、「コンパイル」の名に恥じないツールもある。
単に実行時コード生成をしたいだけなら、逆アセンブラの出力と睨めっこして移植性の無いコードを書く必要はない。
でも、任意の仕組みAについて、Aを理解したいなら、Aを使わずに仕組みを再現する必要があると、私は信じる。
最終的にはこれらのツールを使うべきなのだろうが、最初から使うのは良くない。
-- 参考 --
A Dumb Guy in a Smart Age
Brainfuck JIT Compiler in Around 155 Lines with GNU C
http://dginasa.blogspot.jp/2012/10/brainfuck-jit-compiler-in-around-155.html
gccのラベルアドレス拡張を活用し、コンパイラの生成したコードを切り出す手法を使っている。
最適化レベルを上げると動作出来なくなるが、ベタ書き機械語バイトを記述せずに済む。
[VM][JIT]Brainf*ckで学ぶスクリプト言語処理系高速化。インタプリタ→VMインタプリタ→JITコンパイラ。 - hogeなlog
http://d.hatena.ne.jp/hogelog/20100914/p1
日本語ページ。
タイトル通り。
Josh Haberman: Hello, JIT World: The Joy of Simple JITs
http://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html
最初は最小限の機能から始めるほうが、理解しやすい。
このページでは、定数を返すしか能の無い関数を実行時生成するのに、最低限必要なものを説明している。
そして、自動化ツールに逃げるのだ。
--- 2015年1月30日19時25分 追記 ---
x86_64でのsystemVなどの呼び出し規約では、スタックポインタを操作せずにスタックに値を積むことの出来る領域「Red zone」があることを思い出した。
この領域の使われ方については、コンパイラは何も保証してくれない。
次のマイナーバージョンのコンパイラは、Red zoneの上限ギリギリに重要な変数を積むかも知れない。
だから、gotoなどのジャンプ命令で呼び出すなら、このRed zoneにも触らないように実行時生成コードを組まねばならない。
特に実行時生成コードから外部関数を呼ぶ場合は、外部関数がスタックに触っても大丈夫な様に、Red zone分だけスタックポインタを進めなければならない。
スタックポインタの操作は一命令で済むが、x86_64のsystemVでのRed zoneは128バイト。
この使われていないかも分からない領域を、実行時生成コードは無駄にスタックに積まねばならない。
普通のJITアセンブラは、gotoではなくC言語の関数呼び出しで実行時生成コードを呼び出すようにしている。
Red zoneは関数呼び出し時には片付けておく事になっているため、スタック領域を無駄にせずに済む。
それ以上に関数呼び出しなら、上記の様にGNU C拡張アセンブラ機能を酷使する必要がない。
呼び出し規約が同じなら、他のC言語コンパイラでも動くはずだ。
以下の関数呼び出し方式JITアセンブラのコードを載せて、今回の追記を完了する。
#include <sys/mman.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define BUFF_SIZE 30000
#define JIT_SIZE (((0x1 << 4) - 1) << 12)
typedef unsigned char byte;
static void error_abort(char *msg)
{
fprintf(stderr, "%s\n", msg);
exit(1);
}
static void *dojit(void *start, char *code, size_t length)
{
memcpy(start, code, length);
return start + length;
}
static void rip_patch(int norip, void *addr, void *num)
{
size_t tgt;
unsigned int tgt_32;
if (norip)
tgt = num;
else
tgt = num - addr;
tgt_32 = tgt;
memcpy(addr - 4, &tgt_32, 4);
}
int main(int argc, char **argv)
{
byte buff[BUFF_SIZE];
void *jit;
void (*jit_start) (byte *);
if (argc != 2)
error_abort("argc");
{
FILE *fp = fopen(argv[1], "r");
void *loopbuf[3000];
int loop = 0;
int i;
if (NULL == fp)
error_abort("fopen");
jit =
mmap((void *) (0x1 << 12), JIT_SIZE, PROT_WRITE,
MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
if (MAP_FAILED == jit)
error_abort("map");
for (i = 0; i < BUFF_SIZE; i++)
buff[i] = 0;
jit_start = jit;
jit =
dojit(jit,
"\x53" "\x31\xdb" "\x41\x54" "\x49\x89\xfc" "\x41\x55",
10);
while (1) {
int c = fgetc(fp);
if (EOF == c)
break;
switch (c) {
case '>':
jit = dojit(jit, "\x83\xc3\x01", 3);
break;
case '<':
jit = dojit(jit, "\x83\xeb\x01", 3);
break;
case '+':
jit = dojit(jit, "\x48\x63\xc3" "\x41\x80\x04\x04\x01", 8);
break;
case '-':
jit = dojit(jit, "\x48\x63\xc3" "\x41\x80\x2c\x04\x01", 8);
break;
case '.':
jit =
dojit(jit,
"\x48\x63\xc3" "\x48\x8b\x35____"
"\x41\x0f\xb6\x3c\x04" "\xe8____", 20);
rip_patch(0, jit, fputc);
rip_patch(0, jit - 10, &stdout);
break;
case ',':
jit =
dojit(jit,
"\x48\x8b\x3d____" "\x4c\x63\xeb" "\xe8____"
"\x43\x88\x04\x2c", 19);
rip_patch(0, jit - 4, fgetc);
rip_patch(0, jit - 12, &stdin);
break;
case '[':
jit =
dojit(jit,
"\x48\x63\xc3" "\x41\x80\x3c\x04\x00"
"\x0f\x8e____", 14);
loopbuf[loop] = jit;
loop++;
break;
case ']':
jit =
dojit(jit,
"\x48\x63\xc3" "\x41\x80\x3c\x04\x00"
"\x0f\x85____", 14);
loop--;
rip_patch(0, jit, loopbuf[loop]);
rip_patch(0, loopbuf[loop], jit);
break;
}
}
jit = dojit(jit, "\x41\x5d" "\x41\x5c" "\x5b" "\xc3", 6);
fclose(fp);
mprotect(jit_start, JIT_SIZE, PROT_EXEC);
}
//fwrite(jit_start, 1, jit - (void *) jit_start, stderr);
jit_start(buff);
munmap(jit_start, JIT_SIZE);
return 0;
}
--- 2015年1月31日21時34分 追記 ---
x86_64では、アドレス即値はほぼ32ビットのままなので、gccなどのコンパイラが吐くコードは関数やグローバル変数の位置を32ビットアドレスの範囲内にまとめている。
私はこれらのコンパイラが吐いたコードを切り貼りして機械語コード部分を作ったので、mmap()が32ビットアドレスの外に領域を確保すると、上記のコードは上手く動かない。
32ビットアドレス内の領域を確保するようmmap()に指定すれば、gccでは動く。
しかしQemuエミュルータの作者が作ったTiny C コンパイラで動かそうとすると、上記のコードは上手く動かない。
調べてみると、私の使っているLinuxでは、libcなど標準ライブラリを32ビットアドレスの範囲外にマッピングしている。
これらのライブラリが提供する関数の関数ポインタを取得しようとすると、Tiny Cではそのまま64ビットアドレスを返す。
gccやclangは32ビットアドレス内に用意した中継関数のポインタを返すので、アドレス即値を32ビットに端折って埋め込む私のコードでも動作できた。
x86_64で64ビットアドレス即値を扱える命令は、movabsしかない。
しかも、即値の代入先はレジスタだけ。
アドレスではなくアドレス先のメモリ内容を読み書き機能もあるが、その場合、メモリとの遣り取り相手にはraxレジスタしか指定できない。
幸い、処理速度は32ビットmov命令と同じ。
というわけで、実行時生成コードの外側のアドレスを64ビットで扱う以下のコードは、mmap()のアドレス指定を省いているし、Tiny Cでも動く。
#include <sys/mman.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define BUFF_SIZE 30000
#define JIT_SIZE (0x1 << 4 << 12)
typedef unsigned char byte;
static void error_abort(char *msg)
{
fprintf(stderr, "%s\n", msg);
exit(1);
}
static void *dojit(void *start, char *code, size_t length)
{
memcpy(start, code, length);
return start + length;
}
static void rip_patch(void *addr, void *num)
{
size_t tgt = num - addr;
unsigned int tgt_32 = tgt;
memcpy(addr - 4, &tgt_32, 4);
}
static void abs_patch(void *addr, void *num)
{
memcpy(addr - 8, &num, 8);
}
int main(int argc, char **argv)
{
byte buff[BUFF_SIZE];
void *jit;
void (*jit_start) (byte *);
if (argc != 2)
error_abort("argc");
{
FILE *fp = fopen(argv[1], "r");
void *loopbuf[3000];
int loop = 0;
int i;
if (NULL == fp)
error_abort("fopen");
jit =
mmap(NULL, JIT_SIZE, PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE,
-1, 0);
if (MAP_FAILED == jit)
error_abort("map");
for (i = 0; i < BUFF_SIZE; i++)
buff[i] = 0;
jit_start = jit;
jit =
dojit(jit,
"\x53" "\x31\xdb" "\x41\x54" "\x49\x89\xfc" "\x41\x55",
10);
while (1) {
int c = fgetc(fp);
if (EOF == c)
break;
switch (c) {
case '>':
jit = dojit(jit, "\x83\xc3\x01", 3);
break;
case '<':
jit = dojit(jit, "\x83\xeb\x01", 3);
break;
case '+':
jit = dojit(jit, "\x48\x63\xc3" "\x41\x80\x04\x04\x01", 8);
break;
case '-':
jit = dojit(jit, "\x48\x63\xc3" "\x41\x80\x2c\x04\x01", 8);
break;
case '.':
jit =
dojit(jit,
"\x48\xa1________" "\x48\x89\xc6"
"\x48\xb8________" "\x4c\x63\xeb"
"\x43\x0f\xb6\x3c\x2c" "\xff\xd0", 33);
abs_patch(jit - 10, fputc);
abs_patch(jit - 23, &stdout);
break;
case ',':
jit =
dojit(jit,
"\x48\xa1________" "\x48\x89\xc7"
"\x48\xb8________" "\x4c\x63\xeb" "\xff\xd0"
"\x43\x88\x04\x2c", 32);
abs_patch(jit - 9, fgetc);
abs_patch(jit - 22, &stdin);
break;
case '[':
jit =
dojit(jit,
"\x48\x63\xc3" "\x41\x80\x3c\x04\x00"
"\x0f\x8e____", 14);
loopbuf[loop] = jit;
loop++;
break;
case ']':
jit =
dojit(jit,
"\x48\x63\xc3" "\x41\x80\x3c\x04\x00"
"\x0f\x85____", 14);
loop--;
rip_patch(jit, loopbuf[loop]);
rip_patch(loopbuf[loop], jit);
break;
}
}
jit = dojit(jit, "\x41\x5d" "\x41\x5c" "\x5b" "\xc3", 6);
fclose(fp);
mprotect(jit_start, JIT_SIZE, PROT_EXEC);
}
//fwrite(jit_start, 1, jit - (void *) jit_start, stderr);
jit_start(buff);
munmap(jit_start, JIT_SIZE);
return 0;
}
アプリケーションのクロスコンパイルは難しくないが、コンパイラ自身のクロスコンパイルは難しい。
アセンブラとリンカのクロスコンパイルはもう少し簡単かもしれない。
しかしリンカの段階に備えて、スタートアップファイルなどを適切な場所に配置する必要があるなど、色々面倒。
一方、FORTHのインタプリタ実装を追っている内に、実行時アセンブラを書きたくなった。
仮想マシンインタプリタを回す方式は、ハードウェアの分岐予測が殆ど効かない。
命令フェッチから確定までのパイプライン段数が伸びている近年のプロセッサでは、これはキツい。
一方、FORTHは言語のコア部分が単純なので、アセンブラで構築し易いらしい。
JAVAやECMAscriptやLLVMどころか、pythonなどスクリプト言語までJITコンパイラを積み始めているし、どうせアセンブラを吐くコードを書くなら、実行前アセンブラより実行時アセンブラの方が面白そうだ。
検索してみると、可読性を犠牲にしてまでコンパイラのサイズを最小化したプログラム言語brainfuckをJITコンパイルする人が沢山いるようだ。
で、出来たのが以下のC言語コード。
/* --- ソースコード --- */
#include <sys/mman.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define BUFF_SIZE 30000
#define JIT_SIZE (0x1 << 12 << 4)
typedef unsigned char byte;
static void error_abort(char *msg)
{
fprintf(stderr, "%s\n", msg);
exit(1);
}
static void *dojit(void *start, char *code, size_t length)
{
memcpy(start, code, length);
return start + length;
}
static void rip_patch(int norip, char *addr, void *num)
{
size_t tgt;
unsigned int tgt_32;
if (norip)
tgt = num;
else
tgt = num - ((size_t) addr);
tgt_32 = tgt;
memcpy(addr - 4, &tgt_32, 4);
}
int main(int argc, char **argv)
{
byte buff_body[BUFF_SIZE];
register byte *buff asm("%r12") = buff_body;
void *jit, *jit_start;
register int buff_ptr asm("%rbx") = 0;
if (argc != 2)
error_abort("argc");
{
FILE *fp = fopen(argv[1], "r");
void *loopbuf[3000];
int loop = 0;
int i;
if (NULL == fp)
error_abort("fopen");
jit =
mmap((void *) (((size_t) 0x1 << 31) - JIT_SIZE), JIT_SIZE,
PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
if (MAP_FAILED == jit)
error_abort("map");
for (i = 0; i < BUFF_SIZE; i++)
buff[i] = 0;
jit_start = jit;
while (1) {
int c = fgetc(fp);
if (EOF == c)
break;
switch (c) {
case '>':
jit = dojit(jit, "\x83\xc3\x01", 3);
break;
case '<':
jit = dojit(jit, "\x83\xeb\x01", 3);
break;
case '+':
jit = dojit(jit, "\x48\x63\xc3" "\x41\x80\x04\x04\x01", 8);
break;
case '-':
jit = dojit(jit, "\x48\x63\xc3" "\x41\x80\x2c\x04\x01", 8);
break;
case '.':
jit =
dojit(jit,
"\x48\x63\xc3" "\x48\x8b\x35____"
"\x41\x0f\xb6\x3c\x04" "\xe8____", 20);
rip_patch(0, jit, fputc);
rip_patch(0, jit - 10, &stdout);
break;
case ',':
jit =
dojit(jit,
"\x48\x8b\x3d____" "\xe8____" "\x48\x63\xd3"
"\x41\x88\x04\x14", 19);
rip_patch(0, jit - 7, fgetc);
rip_patch(0, jit - 12, &stdin);
break;
case '[':
jit =
dojit(jit,
"\x48\x63\xc3" "\x41\x80\x3c\x04\x00"
"\x0f\x8e____", 14);
loopbuf[loop] = jit;
loop++;
break;
case ']':
jit =
dojit(jit,
"\x48\x63\xc3" "\x41\x80\x3c\x04\x00"
"\x0f\x85____", 14);
loop--;
rip_patch(0, jit, loopbuf[loop]);
rip_patch(0, loopbuf[loop], jit);
break;
}
}
jit = dojit(jit, "\xe9____", 5);
rip_patch(0, jit, &&end);
fclose(fp);
mprotect(jit_start, JIT_SIZE, PROT_EXEC);
}
asm volatile ("jmp *%3":"=r" (buff_ptr):"0"(buff_ptr), "r"(buff),
"r"(jit_start):"memory", "%rax", "%rcx", "%rdx", "%rsi",
"%rdi","%r8","%r9","%r10","%r11");
asm goto (""::::end);
__builtin_unreachable();
end:
munmap(jit_start, JIT_SIZE);
return 0;
}
/* --- ソースコード完結 --- */
見ての通り、実行時コード生成部分はバイト列をベタ書き。
少なくとも、x86_64マシン上でしか動かない。
C言語のswitchループで書いたbrainfuckインタプリタを別に書いて、コンパイラの出力した各case文の機械語をobjdump -dの逆アセンブル結果を見ながら手動で切り出したものだ。
バイト列とニーモニックを同時に表示してくれるなら、機械語命令に疎くても、切り出し作業は難しくはない。
ちなみに、仮想マシンエミュレータqemuの古い版は、リンカと同じ機能を実装したツールを用意し、コンパイラがリンカに渡すファイルを分析することで、機械語切り出し作業を自動化している。
こうしてベタ書きした機械語コードを実行するのに、私は拡張インラインアセンブラを使った。
asm volatile ("jmp *%3":"=r" (buff_ptr):"0"(buff_ptr), "r"(buff),
"r"(jit_start), "memory", "%rax", "%rcx", "%rdx", "%rsi",
"%rdi","%r8","%r9","%r10","%r11");
コンパイラの最適化レベルが低いなら
goto *jit_start;
と、単にラベルジャンプにしても良かったかもしれない。
しかしこの実行時コード生成器では、brainfuckの'.'や','がC言語の外部関数を呼ぶようにしている。
systemVのC言語関数呼び出し規約では、これら外部関数がある範囲のレジスタなどを好きな様に上書き出来ることを規程している。
ところが、GNU Cはインラインアセンブラ部分を殆ど読まないし、アプリケーション構築時にしか働けないC言語コンパイラでは、実行時に生成されるコードで外部関数が呼ばれるなんて知りようがない。
単なるgoto *jit_start;では、実行時に生成されたコードがレジスタに全く触らないように、コンパイラには見えてしまう。
このため、最適化レベルを上げると、これら余っている様に見えるレジスタをコンパイラは活用してしまう恐れがある。
拡張インラインアセンブラを使うことで、書き換える可能性のある範囲をコンパイラに伝えることが出来る。
ついでに上記の理由により、systemVとは異なる呼び出し規約を使うシステム(Windowsとか)でも、このプロクラムは動作を保証出来ない。
64ビットWindowsなら、
・少なくとも今回使っている整数型では破壊するレジスタの範囲がsystemVのそれを縮小したもの。
・呼び出す関数(fgetcとfputc)の引数が少なく、スタックを使わない。
gccとUNIXシステムコールをWindowsに移植したCygwin環境なら、コンパイルするだけで動作すると思う。
そして、私が今回ハマった問題の解決策が、
asm goto (""::::end);
この一行だ。
私の使ったgcc-4.8.3の場合、これが欠けると上記のC言語コードは最適化レベル-O2以上では暴走した。
gccの吐いたアセンブラコードを見ると、上記コードのendラベルが実行時コード生成の最終処理部分に移動していた。
gccの中身なんて私はさっぱり分からないが、恐らく、endラベルを用いるgoto文を見つけられなかったため、endラベルの管理をコンパイラがサボったからだと思う。
asm文は動作を完了すると直後の文に処理が移る、とgccは見做すそうだ。
endラベルはasm文の直後にあるため、他からendラベルを使う場所が無いならば、endラベルを何処に移そうと問題は生じない。
ちなみに、このasm gotoは何もコードを生成しないため、書く場所は何処でもいい。
しかし本来ならこのendラベル指定は、
asm volatile ("jmp *%3":"=r" (buff_ptr):"0"(buff_ptr), "r"(buff),
"r"(jit_start), "memory", "%rax", "%rcx", "%rdx", "%rsi",
"%rdi","%r8","%r9","%r10","%r11" : end);
上記の様に実行時生成コードを呼び出しているasm文につけるべきものだ。
endラベルへのジャンプは実行時生成コードから行なわれるのだから。
この記法が出来ないように制限されている理由は、GNUのマニュアルによるとコンパイラの内部構造によるものらしい。
裏を返せば、GNU Cの開発者達は好き好んでこの制限をつけているわけではなく、将来の改良でこの制限はなくなると思う。
その時になれば、生成コード呼び出し部分とendラベルへのジャンプ指定が離れた場所にあったら困るはずだ。
以上、拡張インラインアセンブラの機能を活用することにより、GNU C最高レベルの最適化-O3に対しても、上記のC言語ソースコードは正しく動作するバイナリを生成する。
で、最適化を切ったバイナリと比較すると、動作速度に違いを全く見出せない。
大きなプログラムの実行は殆ど、実行時生成コードで行なわれるからだ。
実行時生成コードの品質は、私がベタ書きしたバイト列で決まり、このバイト列に対してコンパイラは何も出来ない。
しかし、最適化への対応が無駄な最大の理由は今回のプログラムが小規模だからだ、と私は言い訳する。
他のコードも沢山含まれるプログラムなら、一部のコードが最適化の足を引っ張るのは問題だろう。
勿論、下の参考URLなどで示されているように、近年ではJITコンパイルを支援するツールが整備されている。
JITアセンブルと違ってコードの最適化までする、「コンパイル」の名に恥じないツールもある。
単に実行時コード生成をしたいだけなら、逆アセンブラの出力と睨めっこして移植性の無いコードを書く必要はない。
でも、任意の仕組みAについて、Aを理解したいなら、Aを使わずに仕組みを再現する必要があると、私は信じる。
最終的にはこれらのツールを使うべきなのだろうが、最初から使うのは良くない。
-- 参考 --
A Dumb Guy in a Smart Age
Brainfuck JIT Compiler in Around 155 Lines with GNU C
http://dginasa.blogspot.jp/2012/10/brainfuck-jit-compiler-in-around-155.html
gccのラベルアドレス拡張を活用し、コンパイラの生成したコードを切り出す手法を使っている。
最適化レベルを上げると動作出来なくなるが、ベタ書き機械語バイトを記述せずに済む。
[VM][JIT]Brainf*ckで学ぶスクリプト言語処理系高速化。インタプリタ→VMインタプリタ→JITコンパイラ。 - hogeなlog
http://d.hatena.ne.jp/hogelog/20100914/p1
日本語ページ。
タイトル通り。
Josh Haberman: Hello, JIT World: The Joy of Simple JITs
http://blog.reverberate.org/2012/12/hello-jit-world-joy-of-simple-jits.html
最初は最小限の機能から始めるほうが、理解しやすい。
このページでは、定数を返すしか能の無い関数を実行時生成するのに、最低限必要なものを説明している。
そして、自動化ツールに逃げるのだ。
--- 2015年1月30日19時25分 追記 ---
x86_64でのsystemVなどの呼び出し規約では、スタックポインタを操作せずにスタックに値を積むことの出来る領域「Red zone」があることを思い出した。
この領域の使われ方については、コンパイラは何も保証してくれない。
次のマイナーバージョンのコンパイラは、Red zoneの上限ギリギリに重要な変数を積むかも知れない。
だから、gotoなどのジャンプ命令で呼び出すなら、このRed zoneにも触らないように実行時生成コードを組まねばならない。
特に実行時生成コードから外部関数を呼ぶ場合は、外部関数がスタックに触っても大丈夫な様に、Red zone分だけスタックポインタを進めなければならない。
スタックポインタの操作は一命令で済むが、x86_64のsystemVでのRed zoneは128バイト。
この使われていないかも分からない領域を、実行時生成コードは無駄にスタックに積まねばならない。
普通のJITアセンブラは、gotoではなくC言語の関数呼び出しで実行時生成コードを呼び出すようにしている。
Red zoneは関数呼び出し時には片付けておく事になっているため、スタック領域を無駄にせずに済む。
それ以上に関数呼び出しなら、上記の様にGNU C拡張アセンブラ機能を酷使する必要がない。
呼び出し規約が同じなら、他のC言語コンパイラでも動くはずだ。
以下の関数呼び出し方式JITアセンブラのコードを載せて、今回の追記を完了する。
#include <sys/mman.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define BUFF_SIZE 30000
#define JIT_SIZE (((0x1 << 4) - 1) << 12)
typedef unsigned char byte;
static void error_abort(char *msg)
{
fprintf(stderr, "%s\n", msg);
exit(1);
}
static void *dojit(void *start, char *code, size_t length)
{
memcpy(start, code, length);
return start + length;
}
static void rip_patch(int norip, void *addr, void *num)
{
size_t tgt;
unsigned int tgt_32;
if (norip)
tgt = num;
else
tgt = num - addr;
tgt_32 = tgt;
memcpy(addr - 4, &tgt_32, 4);
}
int main(int argc, char **argv)
{
byte buff[BUFF_SIZE];
void *jit;
void (*jit_start) (byte *);
if (argc != 2)
error_abort("argc");
{
FILE *fp = fopen(argv[1], "r");
void *loopbuf[3000];
int loop = 0;
int i;
if (NULL == fp)
error_abort("fopen");
jit =
mmap((void *) (0x1 << 12), JIT_SIZE, PROT_WRITE,
MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
if (MAP_FAILED == jit)
error_abort("map");
for (i = 0; i < BUFF_SIZE; i++)
buff[i] = 0;
jit_start = jit;
jit =
dojit(jit,
"\x53" "\x31\xdb" "\x41\x54" "\x49\x89\xfc" "\x41\x55",
10);
while (1) {
int c = fgetc(fp);
if (EOF == c)
break;
switch (c) {
case '>':
jit = dojit(jit, "\x83\xc3\x01", 3);
break;
case '<':
jit = dojit(jit, "\x83\xeb\x01", 3);
break;
case '+':
jit = dojit(jit, "\x48\x63\xc3" "\x41\x80\x04\x04\x01", 8);
break;
case '-':
jit = dojit(jit, "\x48\x63\xc3" "\x41\x80\x2c\x04\x01", 8);
break;
case '.':
jit =
dojit(jit,
"\x48\x63\xc3" "\x48\x8b\x35____"
"\x41\x0f\xb6\x3c\x04" "\xe8____", 20);
rip_patch(0, jit, fputc);
rip_patch(0, jit - 10, &stdout);
break;
case ',':
jit =
dojit(jit,
"\x48\x8b\x3d____" "\x4c\x63\xeb" "\xe8____"
"\x43\x88\x04\x2c", 19);
rip_patch(0, jit - 4, fgetc);
rip_patch(0, jit - 12, &stdin);
break;
case '[':
jit =
dojit(jit,
"\x48\x63\xc3" "\x41\x80\x3c\x04\x00"
"\x0f\x8e____", 14);
loopbuf[loop] = jit;
loop++;
break;
case ']':
jit =
dojit(jit,
"\x48\x63\xc3" "\x41\x80\x3c\x04\x00"
"\x0f\x85____", 14);
loop--;
rip_patch(0, jit, loopbuf[loop]);
rip_patch(0, loopbuf[loop], jit);
break;
}
}
jit = dojit(jit, "\x41\x5d" "\x41\x5c" "\x5b" "\xc3", 6);
fclose(fp);
mprotect(jit_start, JIT_SIZE, PROT_EXEC);
}
//fwrite(jit_start, 1, jit - (void *) jit_start, stderr);
jit_start(buff);
munmap(jit_start, JIT_SIZE);
return 0;
}
--- 2015年1月31日21時34分 追記 ---
x86_64では、アドレス即値はほぼ32ビットのままなので、gccなどのコンパイラが吐くコードは関数やグローバル変数の位置を32ビットアドレスの範囲内にまとめている。
私はこれらのコンパイラが吐いたコードを切り貼りして機械語コード部分を作ったので、mmap()が32ビットアドレスの外に領域を確保すると、上記のコードは上手く動かない。
32ビットアドレス内の領域を確保するようmmap()に指定すれば、gccでは動く。
しかしQemuエミュルータの作者が作ったTiny C コンパイラで動かそうとすると、上記のコードは上手く動かない。
調べてみると、私の使っているLinuxでは、libcなど標準ライブラリを32ビットアドレスの範囲外にマッピングしている。
これらのライブラリが提供する関数の関数ポインタを取得しようとすると、Tiny Cではそのまま64ビットアドレスを返す。
gccやclangは32ビットアドレス内に用意した中継関数のポインタを返すので、アドレス即値を32ビットに端折って埋め込む私のコードでも動作できた。
x86_64で64ビットアドレス即値を扱える命令は、movabsしかない。
しかも、即値の代入先はレジスタだけ。
アドレスではなくアドレス先のメモリ内容を読み書き機能もあるが、その場合、メモリとの遣り取り相手にはraxレジスタしか指定できない。
幸い、処理速度は32ビットmov命令と同じ。
というわけで、実行時生成コードの外側のアドレスを64ビットで扱う以下のコードは、mmap()のアドレス指定を省いているし、Tiny Cでも動く。
#include <sys/mman.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define BUFF_SIZE 30000
#define JIT_SIZE (0x1 << 4 << 12)
typedef unsigned char byte;
static void error_abort(char *msg)
{
fprintf(stderr, "%s\n", msg);
exit(1);
}
static void *dojit(void *start, char *code, size_t length)
{
memcpy(start, code, length);
return start + length;
}
static void rip_patch(void *addr, void *num)
{
size_t tgt = num - addr;
unsigned int tgt_32 = tgt;
memcpy(addr - 4, &tgt_32, 4);
}
static void abs_patch(void *addr, void *num)
{
memcpy(addr - 8, &num, 8);
}
int main(int argc, char **argv)
{
byte buff[BUFF_SIZE];
void *jit;
void (*jit_start) (byte *);
if (argc != 2)
error_abort("argc");
{
FILE *fp = fopen(argv[1], "r");
void *loopbuf[3000];
int loop = 0;
int i;
if (NULL == fp)
error_abort("fopen");
jit =
mmap(NULL, JIT_SIZE, PROT_WRITE, MAP_ANONYMOUS | MAP_PRIVATE,
-1, 0);
if (MAP_FAILED == jit)
error_abort("map");
for (i = 0; i < BUFF_SIZE; i++)
buff[i] = 0;
jit_start = jit;
jit =
dojit(jit,
"\x53" "\x31\xdb" "\x41\x54" "\x49\x89\xfc" "\x41\x55",
10);
while (1) {
int c = fgetc(fp);
if (EOF == c)
break;
switch (c) {
case '>':
jit = dojit(jit, "\x83\xc3\x01", 3);
break;
case '<':
jit = dojit(jit, "\x83\xeb\x01", 3);
break;
case '+':
jit = dojit(jit, "\x48\x63\xc3" "\x41\x80\x04\x04\x01", 8);
break;
case '-':
jit = dojit(jit, "\x48\x63\xc3" "\x41\x80\x2c\x04\x01", 8);
break;
case '.':
jit =
dojit(jit,
"\x48\xa1________" "\x48\x89\xc6"
"\x48\xb8________" "\x4c\x63\xeb"
"\x43\x0f\xb6\x3c\x2c" "\xff\xd0", 33);
abs_patch(jit - 10, fputc);
abs_patch(jit - 23, &stdout);
break;
case ',':
jit =
dojit(jit,
"\x48\xa1________" "\x48\x89\xc7"
"\x48\xb8________" "\x4c\x63\xeb" "\xff\xd0"
"\x43\x88\x04\x2c", 32);
abs_patch(jit - 9, fgetc);
abs_patch(jit - 22, &stdin);
break;
case '[':
jit =
dojit(jit,
"\x48\x63\xc3" "\x41\x80\x3c\x04\x00"
"\x0f\x8e____", 14);
loopbuf[loop] = jit;
loop++;
break;
case ']':
jit =
dojit(jit,
"\x48\x63\xc3" "\x41\x80\x3c\x04\x00"
"\x0f\x85____", 14);
loop--;
rip_patch(jit, loopbuf[loop]);
rip_patch(loopbuf[loop], jit);
break;
}
}
jit = dojit(jit, "\x41\x5d" "\x41\x5c" "\x5b" "\xc3", 6);
fclose(fp);
mprotect(jit_start, JIT_SIZE, PROT_EXEC);
}
//fwrite(jit_start, 1, jit - (void *) jit_start, stderr);
jit_start(buff);
munmap(jit_start, JIT_SIZE);
return 0;
}
