mrubyのJITの最適化事典

mrubyのJITの最適化

movの削除

RITE VMで
MOVE R2, R0 ADDI R2, 1
のようなコードを考えてます。この場合、正直にR2を代入するのは無駄です。そこで、コード生成時にはR2をR0で設定するコードを生成してしまうのではなく、R2はR0と同じですよという情報だけを持っておきます。そして、ADDI R2, 1でR2を参照するときにR0を参照します。
と、考え方は簡単なんですが、たとえばVMに戻った時どうするのかとかVMから生成コードを呼び出したときどうするのとか罠がいっぱいです。
VMに戻る時はVMのレジスタの整合性を取るようなコードを生成します。また、R0が途中で変わっちゃったらどうするの？という心配もあろうかと思いますが、現在のmrubyのコード生成ではそういうことはないはずです。証明は読者の課題とします。

一方、
　ADDI R3, 1
MOVE R2, R3
のようなコードが生成される場合もあります。この場合、
　R3 + 1 →　R2
のようにコードを生成すると代入が省けます。では、後でR3を参照したら？そういうコードも生成され得ます。そのため、R3のレジスタ情報にR2と同じですよという情報を覚えておきます。

booleanのunbox化

こんなコードはありがちなわけです。
LT R1, 1 JMPNOT R1 006
これをコンパイルすると、R1はX86のsetb命令とか(FloatとFixnumで違う)を使ってALレジスタに0か1を入れて、その後、mrubyのTrue(0xfff000200000000), Flase (0xfff00000000)に変換ます。その後、JMPNOTでR1が0xfff00000000であるか比較してジャンプするとか恐ろしくめんどくさいです。
そこで、コンパイル時に"R1の内容はALレジスタにあるよ"という情報を覚えておいて、JMPNOTをコンパイルするときにはALレジスタのcmp命令だけを出します。二度手間が無くてすっきりです。
でも、JMPNOTではなくR1をbooleanの値として使う場合は困ります。R1を参照している命令がJMPIF, JMPNOTじゃない場合は、ALレジスタの値をboxingしてR1に格納するコードを生成します。

LOADIで型タグ書き込みの省略

LOADI命令で数値を書き込む場合、その前のレジスタの内容もまた数値である場合が結構あります(ループだったりして)。また、ガードや定数など型が分かっている状況から推移して簡単な型推論みたいなことをしています。詳しくはこちらを見てください。　http://d.hatena.ne.jp/miura1729/20140416
レジスタの内容が数値だった場合にLOADIを実行した時、型タグを書きこむ処理を省いています。当然ですね。

CALL命令のSEND命令への統合

私の知る限り、RITE VMのCALL命令はproc.cで定義されているProc#callメソッドの中身でしか使われていません。このProc#callの中身はCALL命令のみでこの命令でProcオブジェクトに対応するiseqを呼び出します。Proc#callメソッドには帰ってきません。
こんな感じなので、
SEND :call→ CALL
の流れを１つにまとめることができます。SENDとCALLにちょっと(メモリへの書き込み3つ)重複があるのでこれが削れます。

LAMBDA命令の最適化

イテレータがネストすると、ループの中でProcオブジェクトが作られることになるのでちょっとやな感じです。そこで、Procオブジェクトをあらかじめプールしておいて、必要があればそこから使い、使い終わったら返すって感じでProcオブジェクトのアロケーションを抑えています。
ただ、この最適化ができるかできないかの判定は結構複雑で、しかも使える確率は低いです。
injectは友達の関数型ラブな人にはきっと有効であることでしょう。クロージャーラブなLispの人には余計なお世話でしょう。

メソッドのインライン化

まあ、出るバグの7割はこれ絡みです。TracingJITなのでメソッドは勝手にインライン化される(フレームは作る必要がある)わけですが、そうすると再帰したりプログラムが大きくなるといくら生成コード領域があっても足りなくなるので、メソッドのサイズや再帰しているかとかでメソッドを共有するかインライン化するか決めます。メソッドを共有する場合はcallinfoに戻りアドレスを入れます。

アクセサのインライン化

ao-benchがアクセサを多用するので入れました。attr_*命令で定義したアクセサだけではなく、アクセサっぽいメソッドの対象です。
こんな感じで判定しています。
　　メソッドの命令長が3
　　命令の2番目がGETIVかSETIV
多分、適用できると一番効果がある最適化です。適用できることは少ないですが。

算術演算のオーバーフローの扱い

mrubyでは足し算・引き算・掛け算の算術演算でオーバーフローになる可能性があります。オーバーフローを起こすと整数が浮動小数点数になってしまいます。つまり、これらの整数の演算の結果は整数と浮動小数点数どちらも可能性があります。そのため、厳密には演算の結果を使うたびに型のチェックが必要になりますが、そんなかったるいこと嫌です。
オーバーフローなんてほとんど起きないので、オーバーフローが起きないとしてコンパイルするのが合理的です。では、実際にオーバーフローが起きてしまったら?この場合はこれまでコンパイルしたコードを無効化(コードの先頭を即座にVMに戻るように書きかえる)して、コンパイルしなおします。
TracingJITではVMに戻るのが前提なのでこういった処理が比較的簡単にできます。よかったよかった

callinfoのアライメント合わせ

mrubyではメソッドの呼び出し履歴情報を覚えておくのにmrb_callinfoという構造体の配列を使います。この配列は動的に確保して、呼び出し履歴が深くなったらその配列を大きく取りなおすわけです。
ところで、mrb_callinfoって何バイトだと思いますか?なんと、52バイトなんですよ。なんて、半端な大きさ、12バイトダミーメンバーを付けなければって思いますよね。人間として。mrubyのJITでは8バイトJITコンパイル用に使っているので4バイトダミーを加えます。

　 struct RClass *target_class;

  mrb_code *prev_pc;
  int16_t prev_tentry_offset;
  uint16_t method_arg_ver;

  void *dummy[1];
} mrb_callinfo; 

また、X86のキャッシュラインは64バイトなので配列を64バイト余分に確保して、アライメントを合わせています。

    c->cibase_org = (mrb_callinfo *)mrb_malloc(mrb, sizeof(mrb_callinfo)*size*2 + 64);
    sci = c->cibase;
    c->cibase = (mrb_callinfo *)(((int)(c->cibase_org) + 63) & (~(64 - 1)));
    for (dci = c->cibase; sci <= c->ci; sci++, dci++) {
      *dci = *sci;
    }

ここで、cibase_orgはアライメントする前のmallocで返ってきた生アドレスです。解放するときに使います。

ガードの削除

　基本的にはVMのレジスタには何の型のデータが入っているのかコンパイル時にはわからないので、ガードを入れます。しかし、mrubyのJITでは型情報を前回コンパイルした命令から引き継ぎ、できる限り型情報を得ようとします。もし、型が分かるようであればガードを削除します。リテラルを代入した直後など型が分かってガードが省けるのはまれです。ただし、selfに関してはレシーバになる頻度が高くガードが省けるのは効果が期待できます。

リテラルの畳みこみ

こんな感じのシーケンス
LOADI R2, 0 EQ R1, :=, 1
でR2は0が入っていることは明らかなわけです。そういう場合にLOADIではR2に0を入れたふりをして実際には何もしない。コンパイル時にR2は0であるという情報を持って、EQ命令をコンパイルする。R1を0と比較することがコンパイル時に分かるのでcmp命令ではなく、test命令が使える。って感じのどう見ても速くなる最適化なんだが却って遅くなることが多い。よくわからん

良く使うメソッドのプリミティブ化

インスタンス生成の最適化