2009-02-13

近況

デブサミ 2009 に 呼んでいただきました. ありがとうございます > 関係者の方々.

で, また JS の話をしてしまいました... マンネリにもほどがありますすみません. (スライド. フォントがへんなのは OpenType font を PDF 化できない OOo for macbook のせい. ヒラギノ代かえせー) 最後のほうにでてきた 正規表現 JIT の話やベンチマークに出てくる V8 の数字は 新しいやつ を使ったものです. このへんは説明がまずく誤解されている方がいらしたようなので補足いたしますすみません. 公式サイトで宣伝されたのは今月だけど, irregexp のコード自体は以前からツリーに入っており, それを参照してます. それにしても JS 本体にはバイトコードがないくせに正規表現にはあるってどうなの V8....

JSVM のレジスタ割り当て

没ねた. 基本的にレジスタ割り当てをがんばっている JS 処理系はない, とおもう. 初代 Tamarin は linear scan register allocation というのを使っていた. 上のスライドにでてくる処理系がこれより頑張っている様子はない.

リリース当初の V8 は命令...というか構文要素単位でレジスタをメモリにフラッシュしていた. (ただし関数の呼び出しなど, 規約にしたがって引き渡すものもいくつかある.) ほんとはすごいレジスタ割り当てのアルゴリズムを使っているのかもしれないけれど, レジスタ名がハードコードされたソースからそれを伺い知るのは難しい.

SquirrelFish Extreme も基本的には似たようなもので, eax だの edx だのがソース内に散乱している. レジスタマシンである SquirrelFish VM は VM の仮想レジスタを実レジスタにマップする API がある.

ALWAYS_INLINE void JIT::emitGetVirtualRegister(int src, RegisterID dst)
{
  ...
}

二番目の引数 RegisterID には実レジスタの名前が渡される.

  ...
  emitGetVirtualRegister(currentInstruction[3].u.operand, X86::eax);
  ...

レジスタ割当器があれば仮想レジスタをマップした実レジスタを返す作りになりそうなものだ. 割当器を実装しようとしても, このままだとそれなりに難儀することだろう.

TraceMonkey/nanojit にはいちおうレジスタアロケータがある. もともと nanojit の中間表現 (LIR) が CPU 非依存なレジスタマシンになっており, レジスタ数の上限を指定する作りになっている. そうして実レジスタを LIR 上のレジスタマップするらしい. これらを実現するために, レジスタの空き状況をトラックする RegAlloc クラスとそれを元にレジスタを割り当てる Assembler::regiterAlloc() 関数などがある.

割り当てのアルゴリズム自体は局所的かつ素朴で, もし空きがあればそれを返し, なければ一番使われていないやつを返す. とはいえレジスタ割り当てを改善する下地は nanojit が一番整っている. 一方 V8 や SquirrelFish も割と容赦ない書き換えをばんばんやるので, そのうちよくはなるだろう. 計算機科学者を山ほど抱える Google でレジスタ割り当てがないってのは沽券にかかわりそうだし.

そんなわけで JSVM ウォッチではレジスタ割り当てのアルゴリズムあたりも注視しておくと良いと思います... だんだん普通のコンパイラ話になってくなあ. という気がするのは外野の想像力の限界で, 当事者にはもっと色々なアイデアがあるんだろうけれど.