2時間半の睡眠で28時間起きてると,簡単には起きないようです.
寝ている間に妖精さんが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] >
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に関数ポインタを直接渡せないのが不便でした.