mrubyのContextThreading化 その1

ちょっと前に間接分岐に関する記事を並べてみたわけだが、そもそも間接分岐自体を消してしまうテクニックも存在する。ContextThreadingという。これまた日本語の記事が無いのだが、軽い説明がこちらのブログにある。
http://d.hatena.ne.jp/higepon/20080510/1210414499
よく見たらMonaの人だった。

英語の記事。
http://www.cs.toronto.edu/~matz/dissertation/matzDissertation-latex2html/node7.html
読めないけど図を見れば何を言おうとしているのかはわかる。

ようするに、アセンブラの命令でCALL-RETを生成して命令の実行コードを呼んでやれば間接分岐は無くなるし、CALLは無条件分岐、RETはコールリターンスタックでの予測で確実にヒットさせることができる、という話だ。
問題点はコードがCPUアーキテクチャに依存することと、作り方によってはコンパイラが吐き出すコードにより動いたり動かなかったりすること。利点は速いこと。
マシン語を生成するわけだから半分JITの世界に足を突っ込んでいる。JITはCALL-RETせずに命令列を直列に配置する技術で、CALL-RETのコストが無くなる。これだけだと別にあんまり嬉しくない。世の中のJITはそこからさらに最適化を加えるから速いのだ。

現状のmrubyのコードはmrb_run内でラベルジャンプという形で命令コードを実行するから、これをCALLで呼ぶということは、Cの関数じゃないところをCALLで呼び出すということになる。Cレベルでは破綻している。GCCが吐き出すコードのスタックの使い方、レジスタの使い方、呼び出し規約などを把握して、マシン語レベルで整合性を取ってやらなければならない。
まあ、ぶっちゃけ無茶なテクニックだ。

今回はそれを実装してみよう、という話。難しいので何回かにわける予定だが、完成するかというととても怪しいと言わざるをえない。


まずirepに生成したコードを持たせるための変数を作る。

typedef struct mrb_irep {
  int idx;

  int flags;
  int nlocals;
  int nregs;

  mrb_code *iseq;
  mrb_value *pool;
  mrb_sym *syms;
  mrb_value (*ct_func)(void); // ←ココ!

  int ilen, plen, slen;
} mrb_irep;

引数を取らない、mrb_valueを返す関数へのポインタだ。ここにmallocで確保したメモリのアドレスを入れて関数呼び出しすることになる。
次に各命令の最後にRET命令を配置する。

//#define CASE(op) L_ ## op:
//#define NEXT i=*++pc; goto *optable[GET_OPCODE(i)]
//#define JUMP i=*pc; goto *optable[GET_OPCODE(i)]
#define CASE(op) L_ ## op:\
asm("subl $40, %esp");
#define NEXT i=*++pc; asm("addl $40, %esp;ret"); goto *optable[GET_OPCODE(i)]
#define JUMP i=*pc; asm("addl $40, %esp;ret"); goto *optable[GET_OPCODE(i)]

espレジスタを足したり引いたりしているのは、そこから更にCの関数を呼ぶ場合に、GCCがespを使ってスタックを参照して引数を積んだりしているからで、これをしないと命令ラベルを呼び出したときのスタックの状態はRET元のアドレスがトップに入っているのにそれを壊してしまう。40byteで足りるかどうかは微妙にわからないが、この値を正確に設定するのはたぶん無理。コード変えたら値も変わっちゃうし。GCCが出力するコードが普通のC用の考え方とちょっと違う気がする。

んで、命令を生成するところ。vm.cのINIT_DISPATCHの前に置く。いまのマクロだとINIT_DISPATCHはいきなりespをずらしに行くのでこれが動くとコケる。

  if (!irep->ct_func) {
    int index;
    unsigned char *data;
    data = mrb_malloc(mrb, irep->ilen * 5 + 3);
    for (index = 0; index < irep->ilen; index++) {
      data[index * 5] = 0xe8;
      *(int*)(data + index * 5 + 1) = ((int*)((unsigned char*)optable[GET_OPCODE(irep->iseq[index])] - (data + index * 5 + 5)));
    }
    data[index * 5] = 0xc2;
    data[index * 5 + 1] = 0x00;
    data[index * 5 + 2] = 0x00;
    irep->ct_func = (void*)data;
  }
  return irep->ct_func();

もちろんirep->ct_funcはirep生成するあちこちでNULLに初期化しておく。
call命令は5byte命令なので命令数*5と3byteのret命令用のサイズを確保する。1byteのret(c3)でも動くのだが、AMDは分岐予測器の都合で1byteのretは推奨しないようなのでわざわざ3byteのretにした。
んで、命令があるだけcall命令(e8)と飛び先アドレスを詰め込んで、retを追加して、ct_funcに入れて、呼び出す。
飛び先アドレスはbyte単位だからunsigned charポインタに変換して計算する。ポインタ同士の演算は結果がサイズで割られてしまうからその対策。アドレスは相対アドレスで、しかもcallの次の命令のアドレスとの相対なのでこのような計算になっている。
returnで値を返してみてもmrb_valueはeaxに収まらないサイズなのでうまく動いていなんじゃないかと思う。

いまのところ作ったコードは以上。この状態ではVM命令間の移動が発生するOP_JMPやRubyメソッドのOP_SEND、その他OP_EXECなどが動かない。つまり標準のmrblibが動かないのでmakeが通らない。とりあえずmrblibをからっぽにしてmakeして、以下のようなコードを実行することならできる。

__printstr__ "hello context threading world"

__printstr__というのはpメソッドやprintメソッドで使う内部処理用の出力メソッドで、Cで書かれているのでこれを呼ぶことはできる。
結果はこんな感じに。

D:\test>mruby_test --verbose test.rb
NODE_SCOPE:
  NODE_BEGIN:
    NODE_CALL:
      NODE_SELF
      method='__printstr__' (183)
      args:
        NODE_STR "hello context threading world" len 29
irep 1 nregs=4 nlocals=2 pools=1 syms=1
000 OP_LOADSELF R2
001 OP_STRING   R3      "hello context threading world"
002 OP_LOADNIL  R4
003 OP_SEND     R2      :__printstr__   1
004 OP_STOP

hello context threading world

しかしまだローカル変数とかに代入するとうまくいかなかったりするので、見落としているところがあるはず。
次はその辺の修正と、OP_JMP系が動くようにしてみたい。
そしたらベンチマークが取れるようになるんじゃないかと。