起きると外は真っ暗 †
2時間半の睡眠で28時間起きてると，簡単には起きないようです．
でsandmark 54秒 †
寝ている間に妖精さんがsandmarkを54秒で実行できるようにしてくれました．
[TOTORO d/C++Projects/umjit] > time Release/umjit sandmark.umz trying to Allocate array of size 0.. trying to Abandon size 0 allocation.. 省略 0. a8d1619e.5540e6cf SANDmark complete. 0.015u 0.000s 0:54.43 0.0% 0+0k 0+0io 690pf+0w [TOTORO d/C++Projects/umjit] >
XBYAKを使ったJITコンパイラ付きのUniversal Machine †
ICFPC2006
http://www.boundvariable.org/
XBYAK
http://homepage1.nifty.com/herumi/soft/xbyak.html
ジャストタイムコンパイラ方式
http://ja.wikipedia.org/wiki/%E3%82%B8%E3%83%A3%E3%82%B9%E3%83%88%E3%82%A4%E3%83%B3%E3%82%BF%E3%82%A4%E3%83%A0%E3%82%B3%E3%83%B3%E3%83%91%E3%82%A4%E3%83%AB%E6%96%B9%E5%BC%8F
よく分からない内にsandmarkの実行が1分切れていたのでソース公開します．
_msizeやインラインアセンブラを使っているので，VCでしかコンパイルできません．
gccでコンパイルするのに必要な作業は，そんなに多くは無いと思います．
前半で定義されている，C++でまんま書かれた関数達は，コンパイルを283行目のdefaultに任せると使われます．
普段は使っていませんが，ArrayIndexとArrayAmendmentのコンパイルは遅いので
そっちに任せると少し幸せです．
#include <vector>
#include <iostream>
#include <fstream>
#include "xbyak.h"
using namespace std;
typedef unsigned int platter;
vector<platter> array0;
platter*pArray0 = NULL;
platter registers[8]={0};
void (*compiled)() = NULL;
//const unsigned int codeAlign=23;
vector<int> labels;
unsigned char*loadProgramCode;
void compile();
void condMove(int a, int b, int c)
{
if(registers[c])
registers[a]=registers[b];
}
void arrayIndex(int a, int b, int c)
{
if(registers[b]==0)
registers[a]=array0[registers[c]];
else
registers[a]=((platter*)registers[b])[registers[c]];
}
void arrayAmendment(int a, int b, int c)
{
if(registers[a]==0)
array0[registers[b]]=registers[c];
else
((platter*)registers[a])[registers[b]]=registers[c];
}
void addition(int a, int b, int c)
{
registers[a]=registers[b]+registers[c];
}
void multiplication(int a, int b, int c)
{
registers[a]=registers[b]*registers[c];
}
void division(int a, int b, int c)
{
registers[a]=registers[b]/registers[c];
}
void nand(int a, int b, int c)
{
registers[a]=~(registers[b]®isters[c]);
}
void halt(int a, int b, int c)
{
exit(0);
}
void alloc(int a, int b, int c)
{
registers[b]=(platter)calloc(registers[c], sizeof(platter));
}
void abandonment(int a, int b, int c)
{
free((void*)registers[c]);
}
void output(int a, int b, int c)
{
putchar(registers[c]);
fflush(stdout);
}
void input(int a, int b, int c)
{
registers[c]=getchar();
}
int loadProgram(int a, int b, int c)
{
if(registers[b]!=0)
{
int size=_msize((platter*)registers[b]);
array0.resize(size/sizeof(platter));
memcpy(&array0[0], (void*)registers[b], size);
pArray0=&array0[0];
compile();
}
return labels[registers[c]]; // ジャンプ先を返す
}
void move(unsigned int platter)
{
int a = (platter>>25)&0x7;
int value = platter&0x1FFFFFF;
registers[a]=value;
}
typedef void func(int, int, int);
func*funcs[]={
condMove,
arrayIndex,
arrayAmendment,
addition,
multiplication,
division,
nand,
halt,
alloc,
abandonment,
output,
input,
};
struct jit : public Xbyak::CodeGenerator
{
union
{
unsigned int cnt;
char buf[4];
}label_;
void nextLabel()
{
++label_.cnt;
int i;
for(i=0; i<4; i++)
{
if(label_.buf[i]!=0)
break;
label_.buf[i]=1;
}
}
void stdOpe(unsigned int ope, unsigned int a, unsigned int b, unsigned int c)
{
/*
default: でC++で書いた関数を呼ぶコードを生成しているので
case 何か: のブロックをコメントアウトしても動きます．
default以外のcaseを消すと，とても消極的にコンパイルされたコードが生成されます
*/
switch(ope)
{
case 0: // cond mov
{
if(a!=b)
{
nextLabel();
mov(eax, ptr[registers+c]);
test(eax, eax);
je(label_.buf);
mov(eax, ptr[registers+b]);
mov(ptr[registers+a], eax);
L(label_.buf);
}
break;
}
/* case 1からcase 2までをコメントアウトすると
// コンパイルにかかる時間がとても短くなりますが
// 微妙に実行速度が遅くなります． sandmark : 54.43sec -> 69.06sec (CoreDuo 2.0Ghz)
//
// umixはさくさく起動した方が嬉しいのでコメントアウトしておきます．
case 1: // array index
{
nextLabel();
mov(eax, ptr[registers+b]);
test(eax, eax);
jnz(label_.buf);
// array0へのアクセス
lea(eax, ptr[pArray0]);
L(label_.buf);
mov(ecx, ptr[registers+c]);
mov(eax, ptr[eax + ecx*4]);
mov(ptr[registers+a], eax);
break;
}
case 2: // array amendment
{
nextLabel();
mov(eax, ptr[registers+a]);
test(eax, eax);
jnz(label_.buf);
// array0へのアクセス
lea(eax, ptr[pArray0]);
L(label_.buf);
mov(ecx, ptr[registers+b]);
mov(edx, ptr[registers+c]);
mov(ptr[eax+ecx*4], edx);
break;
}
//*/
case 3: // add
{
mov(eax, ptr[registers+b]);
add(eax, ptr[registers+c]);
mov(ptr[registers+a], eax);
//registers[a]=registers[b]+registers[c];
break;
}
case 4: // mult
{
mov(eax, ptr[registers+b]);
mov(ecx, ptr[registers+c]);
mul(ecx);
mov(ptr[registers+a], eax);
break;
}
case 5: // div
{
xor(edx, edx);
mov(eax, ptr[registers+b]);
mov(ecx, ptr[registers+c]);
div(ecx);
mov(ptr[registers+a], eax);
break;
}
case 6: // nand
{
mov(eax, ptr[registers+b]);
and(eax, ptr[registers+c]);
not(eax);
mov(ptr[registers+a], eax);
break;
}
case 7: // halt
{
push(0);
lea(eax, ptr[exit]);
call(eax);
break;
}
case 8: //alloc
{
push(4);
push(ptr[registers+c]);
lea(eax, ptr[calloc]);
call(eax);
mov(ptr[registers+b], eax);
pop(eax);
pop(eax);
break;
}
case 9: // abandonment
{
push(ptr[registers+c]);
lea(eax, ptr[free]);
call(eax);
pop(eax);
break;
}
case 10: // output
{
push(ptr[registers+c]);
lea(eax, ptr[putchar]);
call(eax);
push((unsigned int)stdout);
lea(eax, ptr[fflush]);
call(eax);
pop(eax);
pop(eax);
break;
}
case 11: // input
{
lea(eax, ptr[getchar]);
call(eax);
mov(ptr[registers+c], eax);
break;
}
case 12: // load program
{
// LoadProgramの中で，array0をコピーしてしまうと
// compiledの中身が破壊されるので，これだけ別領域(loadProgramCode)に作る必要がある．
// 呼び出し規約はstdcall
push(c);
push(b);
push(a);
jmp(ptr[&loadProgramCode]); // あらかじめ作っておいたものを呼ぶ
break;
}
default:
{
push(c);
push(b);
push(a);
call(ptr[funcs+ope]);
add(esp, 12);
}
}
}
jit(int codesize)
: CodeGenerator(codesize)
{
label_.cnt=0;
}
void gen(int bits)
{
unsigned int ope=(bits>>28)&0xF;
if(ope<13)
{
unsigned int c = bits &0x7; // 000000111
bits=bits>>3;
unsigned int b = bits &0x7; // 000000111
bits=bits>>3;
unsigned int a = bits &0x7; // 000000111
stdOpe(ope, a, b, c);
}
else if(ope==13)
{
unsigned int a = (bits>>25)&0x7;
unsigned int value = bits&0x1FFFFFF;
mov(ptr[registers+a], value);
}
}
};
// LoadProgramの中で，array0をコピーしてしまうと
// compiledの中身が破壊されるので，これだけ別領域に作る必要がある．
// 呼び出し規約はstdcallのつもりで呼べばOK
struct GenLoadProgram : public Xbyak::CodeGenerator
{
GenLoadProgram()
{
lea(eax, ptr[loadProgram]);
call(eax); // ジャンプ先のアドレスを返す
pop(edx);
pop(edx);
pop(edx);
// 実行指の移動
add(eax, ptr[&compiled]);
jmp(eax);
}
};
void compile()
{
jit jitc(array0.size()*29); // 生成されるコードは1platterあたり最大で29バイト(今のところ・・・)
pArray0=&array0[0];
labels.resize(array0.size());
// unsigned int max=0, last=0;
try
{
int i=0;
vector<unsigned int>::iterator it;
for(it=array0.begin(); it!=array0.end(); ++it,++i)
{
labels[i]=jitc.getSize(); // array0[i]のコードが，x86コードで何バイト目なのか分からないと，jmpとかできない
jitc.gen(*it);
// if(labels[i]-last > max)
// max=labels[i]-last;
// last=labels[i];
}
// cout << "largest code size: " << max << endl;
}
catch (Xbyak::Error err)
{
printf("ERR:%s(%d)\n", Xbyak::ConvertErrorToString(err), err);
}
catch (...)
{
printf("unkwon error\n");
}
compiled=(void (*)())jitc.getCode();
compiled();
}
inline unsigned int _fastcall changeEndian(unsigned int v)
{
_asm
{
bswap ecx;
mov eax, ecx;
}
}
int main(int argc, char**argv)
{
ifstream ifs;
char*progName="umix.umz";
if(argc==2)
progName=argv[1];
ifs.open(progName, ios::binary);
if(!ifs.good())
{
cerr << "ERROR : File '"<< progName << "' was not found." << endl;
return 1;
}
const int BS=0x400;
unsigned int tmp[BS];
for(;!ifs.eof();)
{
ifs.read((char*)tmp, sizeof(platter)*BS);
int i, cnt = ifs.gcount()/sizeof(platter);
for(i=0; i<cnt; i++)
array0.push_back(changeEndian(tmp[i]));
}
ifs.close();
GenLoadProgram genLP;
int loadProgramSize=genLP.getSize();
loadProgramCode = (unsigned char*)malloc(loadProgramSize);
memcpy(loadProgramCode, genLP.getCode(), loadProgramSize);
compile();
return 2;
}
XBYAK面白かった．オペコードを知らなくてもコンパイラが書けるなんて，とても素晴らしいです．
ただ，callに関数ポインタを直接渡せないのが不便でした．
- 使っていただいてありがとうございます．callの件は暫定対応してみました．もしよろしければお試しください(バグってたらすいません)． -- へるみ 2007-09-25 23:24:32 (火)
- ありがとうございます．早速試してみます -- naoki 2007-09-27 22:09:37 (木)
