スタックマシンの動的コンパイル
気力がなくなったので、ちゃんとした文章になってませんが、、、。
NYOットやろうぜ
http://members.at.infoseek.co.jp/DrHell/ps1/index.html
yaneVM2i386.cpp 等を参考にして作ってみました。
/* * スタックマシン動的コンパイル&実行 for d言語 */ enum { MAX_STACK = 1024, MAGIC = 0x12345678 }; int sp; int stack[MAX_STACK]; ubyte program[0x1000]; ubyte *pcc = program; void compile(void *start, void *end, int num) { int size = end - start; ubyte* rc = cast(ubyte*)start; // retを探して、消す for (int i = 1;;i++) { if(rc[size - i] == 0xc3) { size -= i; break; } } // コピー for(int i = 0; i < size;i++) pcc[i] = rc[i]; for(int i = 0; i < size; i++) { // マジックナンバーの修正 if (*(cast(int*)&pcc[i]) == MAGIC) { *(cast(int*)&pcc[i])=num; i += 4; } // 相対コールの値を修正 if (pcc[i] == 0xe8) { int *ip = (cast(int*)&pcc[i+1]); *ip = *ip - (pcc - start); } } pcc += size; } // 実行コード コンパイル関数 void _pop() {++sp;} void pop() { compile(&_pop, &pop,0);} void _pushi() {stack[sp--] = MAGIC;} void pushi(int i){ compile(&_pushi, &pushi, i);} void _add() {stack[sp+2] = stack[sp+2] + stack[sp+1]; ++sp;}void add() { compile(&_add, &add, 0);} void _sub() {stack[sp+2] = stack[sp+2] - stack[sp+1]; ++sp;}void sub() { compile(&_sub, &sub, 0);} void _mul() {stack[sp+2] = stack[sp+2] * stack[sp+1]; ++sp;}void mul() { compile(&_mul, &mul, 0);} void _div() {stack[sp+2] = stack[sp+2] / stack[sp+1]; ++sp;}void div() { compile(&_div, &div, 0);} void _printi() {printf("%d\n", stack[sp+1]);} void printi() { compile(&_printi, &printi, 0);} void ret() {pcc[0] = 0xc3; pcc[1] = pcc[2] = pcc[3] = 0xcc; pcc += 4;}// ret int3 int3 int3 4byteアラインしておく。 int main() { sp = MAX_STACK - 1; printf("(1 + 2)*10-1="); // 動的コンパイル pushi(1); pushi(2); add(); pushi(10); mul(); pushi(1); sub(); printi(); ret(); // 実行 void function() exec = cast(void function())program; exec(); return 0; }
エミュレータや、VM(Virtual Machine)では、動的コンパイルにより高速化されていることをよく聞きます。
JIT (Just In Time compile)等と呼ばれているものです。
しかしながら、簡単なサンプルソースとなるとなかなか見つかりません。
そこで、D言語を使った簡単な動的コンパイルのサンプルソースを作りました。
対象とするのは、四則演算と画面出力だけの単純なスタックマシンです。
簡単にするため、元となるスタックマシンの中間コードはなくて、
直接実行時にコンパイルして、実行するだけのものです。
まずは、main関数を見てください。
コンパイルは、pop(),pushi(),add(),sub(),mul(),printi(),ret()関数を呼び行います。
コンパイルされた結果は、programという配列内に保存されます。
実行するには、program配列のアドレスを関数ポインタに代入して、関数を実行します。
さて、コンパイルはどのようにされているのでしょうか?
_pop,pop関数を見てみましょう。
void _pop() {++sp;} void pop() { compile(&_pop, &pop,0);}
_popはスタックポインタを1増やす関数です。
pop関数はcompile関数を呼び出してコンパイルする関数です。
コンパイルするには、関数の中身をコピーするので、関数の範囲を調べる必要があります。
関数の範囲は、関数のポインタから、次の定義されたもの(この場合は関数)までになります。
そのため、compile関数には、_popと、_pop関数の次に定義されているpop関数のアドレスを渡しています。
では、compile関数内を見てみましょう。
まず、関数のサイズを求めます。
次に、関数の最後は必ず、マシン語のret(0xc3)があるのですが、これがあると、次々に実行することが出来ないので
消します。そのために、retの前までをコピーするサイズにします。
次に、範囲をコピーします。
popのような関数ならば、これでOKです。
しかし、他の関数を実行するには問題があります。
それが、マジックナンバーの修正と、相対コールの修正です。
マジックナンバーの修正
pushi等で指定された値を入れるために行います。
例えば、pushiを行うには、毎回違う値が入る必要があります。
しかし、コンパイルされたプログラムは固定である必要があります。
その元の値を探して、正しい値に置き換えます。
マジックナンバーの検索
この例ではマジックナンバーには0x12345678と言った特殊な値を入れておき、
その0x12345678を検索するだけです。
この例の検索は不完全です。
マジックナンバー以外の個所に0x12345678があっても置き換えてしまいます。
これを汎用的にするには、マシン語のコードをきちんとスキャンしていく必要があります。
相対コールの修正
相対アドレスで関数呼び出しを行うcall命令のアドレスのズレを修正します。
どれだけずれているかというと、コピー元とコピー先のアドレス分です。
つまり、startからpccを引いたものを、現在の値から引いてあげればよいのです。
call命令の検索
call命令は0xe8から始まります。
ここでは単純にするため、0xe8を見つけたらcall命令であると断定しています。
これを汎用的にするには、マシン語のコードの長さを求めながら、スキャンする必要があります。
関数から戻る
さて、プログラムのコンパイルの仕方はわかりました。
あとは、実行後、コンパイルコードから正しく戻ってくるようにします。
そのためのコードをコンパイルするのがret()関数です。これは、マシン語のret(0xc3)を入れることで行います。
その後に、0xccが3つ入っているのは、4バイトアラインするためですので、なくても動作します。
さぁ、retを入れたことで1つの関数が完成しました。
あとは、先ほど説明したように、program配列のアドレスを関数ポインタに代入して、関数を実行すればOKです。