起きると外は真っ暗

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]&registers[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 (木)

お名前: