Onigmoのインタプリタをdirect threaded codeに置き換えてCRubyを8%高速化した話
Ruby言語の正規表現エンジンとしても使われているOnigmo(鬼雲)を高速化したのでその話をします。
Onigmoでは、正規表現のマッチにはバイトコードインタプリタを用いてNFAの実行をしています。バイトコードインタプリタの高速化には古くから知られている技法として、direct threaded codeがあり、この技法を用いればswitch-caseを用いて実装されたインタプリタと比べると間接jumpの除去が行えるなど高速化が期待できます。実際、Onigmoでもswitch-case によるdispatchからこのdirect threaded codeに変えることで高速化しています。
... と思ったらdirect threaded codeではなく、token threaded codeという実装になっておりました。(ref: Rename USE_DIRECT_THREADED_VM to USE_TOKEN_THREADED_VM · k-takata/Onigmo@be63582 · GitHub)
token threaded codeはswitch caseに比べれば十分に速いのですが、バイトコード命令のdispatch部分(バイトコードを読み込んで、対応する命令の実装部分のアドレスを引いて、jumpする)にまだ高速化の余地があります。direct threaded codeでは命令dispatchには、バイトコード上に事前に書き込んで置いたアドレスにjumpする方式を取っているので、load 1個分速い訳ですね。
// Token threaded code void **labels = {}; uint8_t *opcode = ...; goto labels[*opcode];
// Direct threaded code void **labels = {}; uint8_t *opcode = ...; goto *(void **)opcode;
ということでtoken threaded codeをdirect threaded codeに更に置き換えることで更なる高速化を実現しました。
と言うのは簡単なのですが、実はdirect threaded codeに変更する際に少し困った問題がありました。switch-case dispatchやtoken threaded codeとは異なり、direct threaded codeではバイトコード上にopcodeではなくアドレスを書き込む必要があります。opcodを保持していた領域にアドレスを書き込めばいいかと思うかもしれませんが、Onigmoのopcodeは1byte、対してアドレスはLinux 64bit環境なら8byteなのでとても足りないです。(switch-caseやtoken threaded codeも省メモリを目的にするならば利点があったのです。) 組み込みシステムなどメモリ使用量の制約が強いような環境では適応は難しいかもしれませんが、いくらでもメモリが使える環境だったら特に問題ないかもしれませんね。
Performance comparison of regular expression engines を使ってbefore/afterを手元のM1 macbookで計測した結果が以下の通りとなります。
| Pattern | Current | Proposal | Improve Rate |
|---|---|---|---|
| Twain | 15 ms | 15 ms | 0% |
| (?i)Twain | 60 ms | 18 ms | 233% |
| [a-z]shing | 14 ms | 13 ms | 7.6% |
| Huck[a-zA-Z]+|Saw[a-zA-Z]+ | 20 ms | 16 ms | 25% |
| \b\w+nn\b | 394 ms | 414 ms | -5.1% |
| [a-q][^u-z]{13}x | 20 ms | 7 ms | 185% |
| Tom|Sawyer|Huckleberry|Finn | 25 ms | 19 ms | 31% |
| (?i)Tom|Sawyer|Huckleberry|Finn | 236 ms | 179 ms | 34% |
| .{0,2}(Tom|Sawyer|Huckleberry|Finn) | 48 ms | 38 ms | 26% |
| .{2,4}(Tom|Sawyer|Huckleberry|Finn) | 46 ms | 44 ms | 4.5% |
| Tom.{10,25}river|river.{10,25}Tom | 42 ms | 41 ms | 2.4% |
| [a-zA-Z]+ing | 509 ms | 410 ms | 24% |
| \s[a-zA-Z]{0,12}ing\s | 48 ms | 44 ms | 9% |
| ([A-Za-z]awyer|[A-Za-z]inn)\s | 101 ms | 99 ms | 2% |
| ["'][^"']{0,30}[?!.]["'] | 44 ms | 39 ms | 12% |
せっかくなので、CRubyに適応したらどのくらい速くなるかも確認しておきましょう。 お手軽なbenchmarkアプリケーションがなかったので、Computer Language Benchmarks Gameのregex-reduxを使いました。 benchmarksgame-team.pages.debian.net
Before:
$ time time ./ruby -W0 regex-redux.rb 0 < a.txt
agggtaaa|tttaccct 356
[cgt]gggtaaa|tttaccc[acg] 1250
a[act]ggtaaa|tttacc[agt]t 4252
ag[act]gtaaa|tttac[agt]ct 2894
agg[act]taaa|ttta[agt]cct 5435
aggg[acg]aaa|ttt[cgt]ccct 1537
agggt[cgt]aa|tt[acg]accct 1431
agggta[cgt]a|t[acg]taccct 1608
agggtaa[cgt]|[acg]ttaccct 2178
50833411
50000000
27388361
4.47 real 13.75 user 0.51 sys
time ./ruby -W0 regex-redux.rb 0 < a.txt 13.76s user 0.52s system 318% cpu 4.475 total
After:
$ time time ./ruby -W0 regex-redux.rb 0 < a.txt
agggtaaa|tttaccct 356
[cgt]gggtaaa|tttaccc[acg] 1250
a[act]ggtaaa|tttacc[agt]t 4252
ag[act]gtaaa|tttac[agt]ct 2894
agg[act]taaa|ttta[agt]cct 5435
aggg[acg]aaa|ttt[cgt]ccct 1537
agggt[cgt]aa|tt[acg]accct 1431
agggta[cgt]a|t[acg]taccct 1608
agggtaa[cgt]|[acg]ttaccct 2178
50833411
50000000
27388361
4.26 real 12.62 user 0.48 sys
time ./ruby -W0 regex-redux.rb 0 < a.txt 12.62s user 0.48s system 306% cpu 4.270 total
実行環境は同じくM1 macです。user の時間が13.75sec -> 12.62secと8.9%くらいの高速化が達成できるようです。悪くはなさそうです。 Onigmoのpull request、まだ手持ちのmacで限られたパターンの正規表現しかテストしていないのでマージされるかは分かりませんが、近いうちにマージされると嬉しいですね。
qrintfの最適化
H2Oの内部では，数値，文字列のフォーマッタとしてsprintfが用いられています．
我々は，最近までsprintf専用ソースコード変換器, qrintfのチューニングを行っていました． 本稿ではqrintfの概要と今回適応した工夫，そして今後の課題についてまとめておきます．
1. qrintfとは？
qrintfとはCコンパイラの１つであるgccのプリプロセッサのラッパーであり，snprintfを高速化するソースコード変換器です． 本稿執筆時点でのqrintfの変換対象はsprintfとsnprintfです．以下本文中では特にことわりのない限りsprintfと記述した場合sprintf, snprintfの両方を指します．
qrintfはソースコードに出現するsprintfで利用するフォーマット文字列を解析し，型ごとに用意された関数呼出にコードを書き換えsprintfの高速化を行います． 例えば以下のようなコードにqrintfを適応すると
sprintf(buf, "%d == 0x%x", 100, 0x64);
以下のコードに変換されます．
_qrintf_nck_finalize(
_qrintf_nck_x(
_qrintf_nck_s_len(
_qrintf_nck_d(
_qrintf_nck_init(buf),
100
),
" == 0x",
sizeof(" == 0x") - 1
),
0x64,
"0123456789abcdef")
);
qrintfを用いるとなぜ速くなるのでしょうか？これはsprintfが実行時に行っていたフォーマット文字列の解析をコンパイル時に行うことで文字列解析コストが削減されたためと考えられます．
また，READMEによるとqrintfを用いるとで今までsprintfで行われていた処理は10倍以上の高速化すると記述されています．
$ gcc -O2 examples/ipv4addr.c $ time ./a.out 1234567890 result: 73.150.2.210 real 0m2.602s user 0m2.598s sys 0m0.003s $ qrintf-gcc -O2 examples/ipv4addr.c $ time ./a.out 1234567890 result: 73.150.2.210 real 0m0.196s user 0m0.192s sys 0m0.003s
なおsprintfを含めたprintf系関数(printf, fprintf, sprintfなど)用の最適化はすでにコンパイラに最適化は導入されています．すでにclang(おそらくGCCにも)には導入されており，例えばLLVMではinstcombineの最適化パスによりprintf("x")がputchar('x')に変換されます．ただ，(LLVMの場合)非常にナイーブな最適化のみが用意されており，sprintfをシリアライザ用途で用いる場合には十分ではありません．
2. 高速化の余地
qrintfを使うことでユースケースによっては10倍以上の高速化が達成可能となりました．ただ，このままだとこの記事は情報量がゼロとなってしまうのでさらなる高速化が可能かqrintfでサポートしているフォーマッタの１つである%ldを例に検討をしていきたいと思います．
以下のコードはqrintfのランタイムで%ldを処理するコードです．
98 static inline qrintf_chk_t _qrintf_chk_s_len(qrintf_chk_t ctx, const char *s, size_t l)
99 {
100 size_t off = ctx.off;
101 ctx.off += l;
102 if (off + l <= ctx.size) {
103 } else if (off < ctx.size) {
104 l = ctx.size - off;
105 } else {
106 goto Exit;
107 }
108 for (; l != 0; --l)
109 ctx.str[off++] = *s++;
110 Exit:
111 return ctx;
112 }
276 static inline char *_qrintf_ld_core(char *p, long v)
277 {
278 if (v < 0) {
279 if (v == LONG_MIN) {
280 *--p = '1' + LONG_MAX % 10;
281 v = LONG_MAX / 10;
282 } else {
283 v = -v;
284 }
285 }
286 do {
287 *--p = '0' + v % 10;
288 } while ((v /= 10) != 0);
289 return p;
290 }
769 static inline qrintf_chk_t _qrintf_chk_ld(qrintf_chk_t ctx, long v)
770 {
771 char buf[sizeof(long) * 3], *p;
772 if (v < 0) {
773 do { int ch = '-'; if (ctx.off < ctx.size) ctx.str[ctx.off] = ch; ++ctx.off; } while (0);
774 }
775 p = _qrintf_ld_core(buf + sizeof(buf), v);
776 return _qrintf_chk_s_len(ctx, p, buf + sizeof(buf) - p);
777 }
まずqrintfはCコードのコンパイル時にsnprintf(buf, bufsiz, "%ld", v)を_qrintf_chk_ld({.buf=buf, .off=0, .size=bufsiz}, v)と変換します．
_qrintf_chk_ldではまず一時バッファを用意し(771行目)，バッファに1桁目から順に数値を文字列化していきます(_qrintf_ld_core関数)．
最後にバッファに保持されている文字列を書き込み先にコピーし処理を終えます．(_qrintf_chk_s_len関数)
さて，プロファイルをとって見ると以下2点が実行時間の多くを占めていることがわかります．
- 一時バッファ，書き込みバッファへのコピー
- 数値の文字列化ループ
それぞれについて高速化が可能か検討していきたいと思います．
2.1 一時バッファへの書き込みの除去
数値から文字列への変換の際，qrintfでは変換結果を書き込みバッファに直接書き込まずCスタックに確保した一時バッファに一旦書き込む方法をとっています．
なぜ直接書き込みバッファへの書き込みを行わずに一旦一時バッファに書き込むのでしょうか？ 理由は2つあり，1つはこれから書き込みを行う数値が実際にどの程度の長さの文字列になるかは不明でありバッファ溢れが発生する可能性があるためです． もう1つは上位桁から文字列化することができないためです．
高速に数値の桁数を計算できれば一時バッファから書き込みバッファへのコピーは除去可能と考えられます．
2.2 数値の文字列化ループ
CPU上で行う数値計算において割り算(div)はコストの高い計算の1つです．div, modを行いながら数値を文字列に変換するこのループは非常に実行コストの高い計算だと考えられます．
3. 整数値文字列変換の最適化
本節では上記で述べた2つの高速化の余地がある点について２つのコードの最適化を行います． 1つ目は桁数を特定するために対数を利用する方法，もう１つはlookupテーブルを使ったdiv/mod計算の除去，ループ展開です．
3.1 自然数の桁数
int, longなどC99の範囲でサポートされている整数型で表現可能な(0を含まない)自然数の桁数は，その自然数の常用対数と等しいです．
libmで用意されているlog10(double)を利用して常用対数を求めることも可能ですが，浮動小数点数への変換など，実行コストが高いため自然数専用のlog10関数を用意し桁数を求めることとしました．
hacker's delightやBit Twiddling Hacks に掲載されているコードを用いてlog10の計算を行っています．
208 /* from http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10 */
209 static inline unsigned _qrintf_ilog10u32(unsigned long v)
210 {
211 #define LOG2(N) ((unsigned)((sizeof(long) * 8) - __builtin_clzl((N)-1)))
212 static const unsigned long ilog10table[] = {
213 1UL,
214 10UL,
215 100UL,
216 1000UL,
217 10000UL,
218 100000UL,
219 1000000UL,
220 10000000UL,
221 100000000UL,
222 1000000000UL,
223 ULONG_MAX,
224 };
225 if (v != 0) {
226 unsigned t;
227 assert(sizeof(long) == sizeof(int));
228 t = ((LOG2(v) + 1) * 1233) / 4096;
229 return t + (v >= ilog10table[t]);
230 }
231 else {
232 return 1;
233 }
234 #undef LOG2
235 }
3.2 lookup-tableの利用
事前にlookupテーブルを用意しておく方法は古くから利用されてきた高速化手法の１つです． 今回は以下で紹介されている手法を利用し，数値を100で割った時の余り(0~99)を事前に文字列テーブルとして用意しておき，div/modの実行回数，そしてループ展開を行っています．
191 static inline const char *_qrintf_get_digit_table(void)
192 {
193 static const char digits_table[] = {
194 "00010203040506070809"
195 "10111213141516171819"
196 "20212223242526272829"
197 "30313233343536373839"
198 "40414243444546474849"
199 "50515253545556575859"
200 "60616263646566676869"
201 "70717273747576777879"
202 "80818283848586878889"
203 "90919293949596979899"
204 };
205 return digits_table;
206 }
289 static inline void _qrintf_long_core(char *p, unsigned long val)
290 {
291 const char *digits = _qrintf_get_digit_table();
292 while (val >= 100) {
293 unsigned idx = val % 100 * 2;
294 *--p = digits[idx + 1];
295 *--p = digits[idx];
296 val /= 100;
297 }
298 if (val < 10) {
299 *--p = '0' + val;
300 } else {
301 *--p = digits[val * 2 + 1];
302 *--p = digits[val * 2];
303 }
304 }
3.3 細かな工夫
3.3.1 実行時のバッファ溢れ検査のループ外巻上げ
snprintfのようにバッファが文字列を出力するのに十分な長さがない場合を考慮しながら文字列を出力する場合， これまでは1文字出力しバッファ溢れが起きていないことを確認というループを実行していました． 前述のように事前に数値の桁数がわかっていればバッファ溢れが起こるかどうかは文字列への変換前に１回確認すれば十分です．
以下のPRでは文字列変換前に数値をバッファにフィットするように値を丸め込みバッファ溢れの検査回数の削減を行っています．
https://github.com/h2o/qrintf/pull/10
3.3.2 16進数数から文字列への変換の最適化
16進数の整数は10進数の整数と異なり上位桁から4bitずつ文字列化することで数値を文字に変換することが可能です．
https://github.com/h2o/qrintf/pull/3
4. 評価
上記の最適化により，さらに約二倍の高速化を達成しました．
Original:
$ git co master Switched to branch 'master' Your branch is up-to-date with 'origin/master'. $ ./bin/qrintf-gcc -O3 examples/ipv4addr.c && time ./a.out 1234567890 result: 73.150.2.210 ./a.out 1234567890 0.22s user 0.00s system 99% cpu 0.219 total
Optimized version:
$ git co optimize_itoa Switched to branch 'optimize_itoa' Your branch is up-to-date with 'imasahiro/optimize_itoa'. $ ./bin/qrintf-gcc -O3 examples/ipv4addr.c && time ./a.out 1234567890 result: 73.150.2.210 ./a.out 1234567890 0.12s user 0.00s system 99% cpu 0.120 total
5. 関連技術
特定のライブラリ関数に特化した最適化はgccやLLVMなどコンパイラやJava言語を中心に多くの言語に搭載されています． 例えば，前述の通りLLVMではナイーブな場合ではあるがprintf関数をputs関数やputchar関数に変換する最適化が組み込まれています．（調べていませんが）おそらくCコンパイラならgccやicc，JVMならhotspotなどの最適化コンパイラにも組み込まれているでしょう．
また，本稿で紹介したlookup-tableを利用した最適化を用いているライブラリとしてhttps://github.com/miloyip/rapidjsonが挙げられます．
rapidjsonでは，lookup-tableを使って数値から文字列への変換(qrintfでは_qrintf_long_core関数)で行ったループ展開の最適化を更に適応し，ループをすべて展開しています．
本稿でもrapidjsonと同じ方法を適応することでループ除去は可能ですhttps://github.com/imasahiro/libtoa/blob/master/libtoa.h#L139． ただしコードサイズの増加は避けられず，また本稿で用いた評価環境では逆に低速化したため採用は見送っています．
6. まとめと今後の課題
本稿では，上記で述べた最適化により数値から文字列への変換の高速化を行いました． 本稿で述べた最適化はh2o/qrintf · GitHubにすでに取り込まれており，Cコンパイラにgccを利用する環境では利用可能となっています．
今後の課題として，(1) clang/llvm環境の対応, (2) 他のフォーマッタ（特に浮動小数点型）への対応があると考えられます．まずclang対応についてですが，clangではgccと全く同じインターフェースは提供していません．そのためqrintf-gccをそのままclang上で利用することはできません． 一応，qrintfをclang/llvmの最適化パスとして実装したpull requestを準備しています． ただしメンテナンスコストや，そもそもこれは正しい道なのかも含めて議論する必要はあります．
次に整数型以外の型への対応，特に浮動小数点型への対応があります．ただ，これはすでにFlorian Loitsch氏によるgrisu[1]と呼ばれる高速な浮動小数点数から文字列への変換手法があります． これを適応することで，浮動小数点数を文字列への変換の高速化が可能であると考えられます． ただ，現在私がsprintfを利用するユースケースとして浮動小数点型はほとんど無いため，あまり優先度は高くはありません．
[1] Loitsch, F.: Printing Floating-point Numbers Quickly and Accurately with Integers, Proceedings of the 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI ’10, New York, NY, USA, ACM, pp. 233–243 (online), DOI: 10.1145/1806596.1806623 (2010).
JITコードの無効化
Ruby向けJITコンパイラ RuJIT Advent Calendar 8日目です．
RuJITに最近追加された最適化（？）の１つにJITコンパイルされた機械語（以下JITコード）中で毎回実行されるメソッド再定義チェックなど実行時検査コードの除去があります．
ただ，実行時検査コードはコンパイル時においた仮定が実行時にまだ有効化を確認するコードですので無条件に除去するわけにはいきません．
RuJITではある仮定が正しくなくなったら，同じ仮定をおいているすべてのJITコードを無効化する処理をRuJITランタイムに追加し除去を可能にしています．
現在，RuJITで除去している実行時検査は２つ用意しており，メソッド再定義とProcオブジェクトの検査が対象となっています．
とここまで書いて，FirefoxのJS処理系，IonMonkeyに導入されていることを知ったので，RuJITでの解説はやめてinvalidationの解説記事へのリンクを置いておく．
トレース選択器の起動
Ruby向けJITコンパイラ RuJIT Advent Calendar 7日目です．
そろそろRuJITの中身についても書くことがなくなってきましたが，今日もRuJITの中身について書きます．今日はRuJITを起動するエントリーポイントの部分を見ていきます．
RuJITを起動するためのフック関数
RuJITを起動するためのフック関数はトレース記録用に２つ，トレース無効化に１つ用意されており，それぞれ以下のインターフェースで定義されています．（method-JIT用にもう１つ用意されていますが今回は省略します．）なお，今日はトレース記録用APIについて，明日はトレース無効化APIについて注目して書こうと思います．
void rujit_record_insn(rb_thread_t *th, rb_control_frame_t *reg_cfp, VALUE *reg_pc);
int rujit_invoke_or_make_trace(rb_thread_t *th, rb_control_frame_t *reg_cfp, VALUE *reg_pc);
void rujit_invalidate(VALUE obj);
上記２つのトレース記録用APIはVMの実装内部に埋め込まれており，分岐命令(branchif, jump, branchunless)の実行やトレース記録命令(rectrace)にそれぞれ埋め込まれています．
具体的なフック関数の呼出は以下のコードで実行されます．
// insns.def
1181 /**
1182 @c jump
1183 @e if val is not false or nil, set PC to (PC + dst).
1184 @j もし val が false か nil でなければ、PC を (PC + dst) にする。
1185 */
1186 DEFINE_INSN
1187 branchif
1188 (OFFSET dst)
1189 (VALUE val)
1190 ()
1191 {
1192 if (RTEST(val)) {
1193 VALUE *pc = GET_PC();
1194 RUBY_VM_CHECK_INTS(th);
1195 JUMP(dst);
1196 if (dst < 0) {
1197 int invoked = rujit_invoke_or_make_trace(th, GET_CFP(), pc, BIN(branchif));
1198 if (invoked) {
1199 RESTORE_REGS();
1200 SET_PC(REG_CFP->pc);
1201 TC_DISPATCH_ORIGN(__JIT__);
1202 }
1203 }
1204 }
1205 }// insns.def
2238 /**
2239 @c optimize
2240 @e invoke rujit compiler for recording hot path
2241 @j RuJITコンパイラを起動
2242 */
2243 DEFINE_INSN
2244 rectrace
2245 (VALUE dummy)
2246 ()
2247 ()
2248 {
2249 SET_PC(GET_PC() - 2);
2250 rujit_record_insn(th, GET_CFP(), GET_PC());
2251 RESTORE_REGS();
2252 TC_DISPATCH_ORIGN(rectrace);
2253 }
分岐命令の場合はフック関数は前方向へのジャンプの場合に実行され，rectrace命令では常にフック関数が実行されていることがわかりました．
この２つのAPIが具体的にどのような処理を行っているかについて見ていきます．
１つめのAPI，rujit_invoke_or_make_traceはコンパイル済みトレースを呼び出すもしくはトレースを新たに構築するAPIとなっています．
いくつかのコードを省略していますが，具体的なコードは以下のとおりです．
66 int rujit_invoke_or_make_trace(rb_thread_t *th, rb_control_frame_t *reg_cfp, VALUE *reg_pc)
67 {
68 jit_event_t ebuf, *e;
69 rujit_t *jit = current_jit;
70 jit_trace_t *trace;
78 trace = find_trace(jit, e);
79
80 if (trace_is_compiled(trace)) {
81 return trace_invoke(jit, e, trace);
82 }
コードキャッシュにコンパイル済みトレースがすでにあった場合には，トレースを実行します．
83 if (is_backward_branch(e)) {
84 if (trace == NULL) {
85 trace = rujit_alloc_trace(jit, e, NULL);
86 }
87 trace->start_pc = reg_pc;
88 }
トレースがまだ作られていない場合には空のトレースを生成します．
90 if (trace) {
91 trace->counter += 1;
92 if (trace->counter > HOT_TRACE_THRESHOLD) {
94 if (find_trace_in_blacklist(jit, trace)) {
95 return 0;
96 }
97 start_recording(jit, trace);
102 }
103 }
104 return 0;
105 }
最後にトレースの実行回数がしきい値を超えた場合にはトレースの記録を開始するという仕組みです．とくに難しいコードはありません．
ここで，start_recording関数，stop_recording関数は変数rujit_record_trace_modeのフラグに1を立てたり消したりする関数です．
rujit_record_trace_modeは後々使う変数なので頭の隅においておきます．
258 static void start_recording(rujit_t *jit, trace_t *trace)
259 {
260 rujit_record_trace_mode = 1;
265 }267 static void stop_recording(rujit_t *jit)
268 {
269 rujit_record_trace_mode = 0;
274 }
もう１つのAPIであるrujit_record_insnも見ておきます．
48 void rujit_record_insn(rb_thread_t *th, rb_control_frame_t *reg_cfp, VALUE *reg_pc)
49 {
50 rujit_t *jit = current_jit;
55 assert(is_recording(jit));
56 e = jit_event_init(&ebuf, jit, th, reg_cfp, reg_pc);
57 if (is_end_of_trace(recorder, e)) {
58 rujit_push_compile_queue(jit, recorder->cur_func);
59 stop_recording(jit);
60 }
61 else {
62 record_insn(recorder, e);
63 }
64 }
この関数では，トレース記録の終了条件を確認し，トレース記録がまだ終わっていない場合はコードを記録していきます．
さて，rujit_invoke_or_make_traceは既存のYARV命令の実装に呼出コードが追加されているため，どのように呼び出されるか明白ですが，もう１つのAPI，rujit_record_insnはYARVに新たに追加した命令rectraceの内部で呼び出されています．この命令がどのような場合に呼び出されるかについて見ていきます．
rectrace命令はバイトコードコンパイラには生成用コードはありません．
コンパイラ支援なしにどのようにこの命令を実行するかの工夫はVM実行部分にあります．
VMの評価部vm_exec_core()内部ではこのようなマクロが用意されており，このマクロは各バイトコード命令の末尾で呼び出されます．
#define NEXT_INSN() TC_DISPATCH(__NEXT_INSN__)
ところでこのNEXT_INSNですが，具体的な実装は以下のTC_DISPATCHマクロにて実装されています．
102 #define TC_DISPATCH(insn) do {\
103 void const *next_addr = (rujit_record_trace_mode) ? LABEL_PTR(rectrace) : (void const *)GET_CURRENT_INSN();\
104 goto *next_addr; \
105 } while (0);
YARVはdirect threaded codeで実装されていますのでバイトコード上に埋め込まれたアドレスにジャンプする実装となっていますが，トレース記録中（rujit_record_trace_mode = 1)は必ずrectrace命令部分に飛ぶようになってます．これで新しいバイトコード命令(rectrace)は追加したものの，比較的小さなオーバヘッドでトレース記録のon/offを行っています．
まとめ
本稿ではRuJITのトレース記録用APIについて述べた．またVMに埋め込まれている起動のための工夫について述べ，どのように呼び出されるかについても解説した．
RuJITの中間表現 LIRへのコンパイル
Ruby向けJITコンパイラ RuJIT Advent Calendar 6日目です．
今日はYARVバイトコードからLIRへの変換をサンプルコードを用いて説明する．
実行の流れ
まずはRubyプログラムのYARVバイトコードへのコンパイルについて概要を述べておく．
CRubyはRubyプログラムを読み込むとYARVバイトコードにコンパイルし，そのバイトコードを実行する．
RuJITはRubyが実行した分岐命令に対してトレース候補の選択，コンパイルを行う．
RuJITの中間表現 LIRへのコンパイル
サンプルコード
今日はCRubyのbenchmarkコードの中からbm_vm2_method.rbを実行していきます．
def m; nil; end
i = 0
while i<6_000_000
i += 1
m; m;
end
Rubyプログラムは以下のYARVバイトコードに変換されます．
== disasm: <RubyVM::InstructionSequence:<main>@bm_vm2_method.rb>========
== catch table
| catch type: break st: 0026 ed: 0054 sp: 0000 cont: 0054
| catch type: next st: 0026 ed: 0054 sp: 0000 cont: 0023
| catch type: redo st: 0026 ed: 0054 sp: 0000 cont: 0026
|------------------------------------------------------------------------
local table (size: 2, argc: 0 [opts: 0, rest: -1, post: 0, block: -1, kw: -1@-1, kwrest: -1])
[ 2] i
0000 trace 1 ( 1)
0002 putspecialobject 1
0004 putspecialobject 2
0006 putobject :m
0008 putiseq m
0010 opt_send_without_block <callinfo!mid:core#define_method, argc:3, ARGS_SIMPLE>
0012 pop
0013 trace 1 ( 5)
0015 putobject_OP_INT2FIX_O_0_C_
0016 setlocal_OP__WC__0 2
0018 trace 1 ( 6)
0020 jump 45
0022 putnil
0023 pop
0024 jump 45
// loop header [1]
0026 trace 1 ( 7)
0028 getlocal_OP__WC__0 2
0030 putobject_OP_INT2FIX_O_1_C_
0031 opt_plus <callinfo!mid:+, argc:1, ARGS_SIMPLE>
0033 setlocal_OP__WC__0 2
0035 trace 1 ( 8)
0037 putself
0038 opt_send_without_block <callinfo!mid:m, argc:0, FCALL|VCALL|ARGS_SIMPLE>
0040 pop
0041 getlocal_OP__WC__0 2 ( 6)
0043 putobject 6000000
0045 opt_lt <callinfo!mid:<, argc:1, ARGS_SIMPLE>
0047 branchif 26 // ← [2]
0049 putnil
0050 leave== disasm: <RubyVM::InstructionSequence:m@bm_vm2_method.rb>=============
0000 trace 8 ( 1)
0002 putnil
0003 trace 16 ( 3)
0005 leave
[2]が複数回（RuJITのデフォルト設定では2回）実行されるとRuJITは[1]から[2]までのパスを頻繁に実行されるパスとして識別し，トレース記録を開始します．
トレースの記録はバイトコードの実行と並行して行われ，loop headerのバイトコードの実行するとトレース記録は終了しLIR最適化が行われる．
今回得られたLIRコードは以下のようなコードとなった．
---------------
BB0 (pc=(nil)) succ=[BB1]
0000 0 StackPop
0001 0 GuardTypeNil Exit:0x7f0de99cff38 R:0000
0006 0 LoadConstFixnum Val:3
0030 0 LoadConstNil
0057 0 LoadConstFixnum Val:b71b01
0002 0 Jump TargetBB:bb:1
---------------
BB1 (pc=0x7f0de99cfe50) pred=[BB5,BB0] succ=[BB2]
[self=v21,(0, 2)=v19]
0003 0 Trace flag:1
0004 0 EnvLoad Level:0 Index:2
0005 0 StackPush Val:0004
0007 0 StackPush Val:0006
0008 0 StackPop
0009 0 StackPop
0010 0 StackPush Val:0004
0011 0 StackPush Val:0006
0012 0 GuardMethodRedefine Exit:0x7f0de99cfe78 klass_flag:1 bop:0
0013 0 GuardTypeFixnum Exit:0x7f0de99cfe78 R:0004
0014 0 StackPop
0015 0 StackPop
0016 0 FixnumAddOverflow LHS:0004 RHS:0006
0017 0 StackPush Val:0016
0018 0 StackPop
0019 0 EnvStore Level:0 Index:2 Val:0016
0020 0 Trace flag:1
0021 0 LoadSelf
0022 0 StackPush Val:0021
0023 0 StackPop
0024 0 StackPush Val:0021
0025 0 GuardMethodCache Exit:0x7f0de99cfeb0 R:0021 ci:0x7f0de99cfd10
0026 0 StackPop
0027 0 Jump TargetBB:bb:2
---------------
BB2 (pc=0x7f0de99cfeb0) pred=[BB1] succ=[BB3]
[self=v21,(0, 2)=v19]
[self=v21,(0, 2)=v19]
0028 0 InvokeMethod PC:0x7f0de99cfeb0 ci:0x7f0de99cfd10 block:-001 argc:1 argv: 0021
0029 0 Trace flag:8
0031 0 StackPush Val:0030
0032 0 Trace flag:16
0033 0 StackPop
0034 0 FramePop
0035 0 Jump TargetBB:bb:3
---------------
BB3 (pc=0x7f0de99ce188) pred=[BB2] succ=[BB4]
[self=v21,(0, 2)=v19]
[self=v39,(0, 2)=v19]
0036 0 StackPush Val:0030
0037 0 StackPop
0038 0 Trace flag:1
0039 0 LoadSelf
0040 0 StackPush Val:0039
0041 0 StackPop
0042 0 StackPush Val:0039
0043 0 GuardMethodCache Exit:0x7f0de99cfee0 R:0039 ci:0x7f0de99d16f0
0044 0 StackPop
0045 0 Jump TargetBB:bb:4
---------------
BB4 (pc=0x7f0de99cfee0) pred=[BB3] succ=[BB5]
[self=v39,(0, 2)=v19]
[self=v39,(0, 2)=v19]
0046 0 InvokeMethod PC:0x7f0de99cfee0 ci:0x7f0de99d16f0 block:-001 argc:1 argv: 0039
0047 0 Trace flag:8
0048 0 StackPush Val:0030
0049 0 Trace flag:16
0050 0 StackPop
0051 0 FramePop
0052 0 Jump TargetBB:bb:5
---------------
BB5 (pc=0x7f0de99ce188) pred=[BB4] succ=[BB1]
[self=v39,(0, 2)=v19]
[self=v39,(0, 2)=v55]
0053 0 StackPush Val:0030
0054 0 StackPop
0055 0 EnvLoad Level:0 Index:2
0056 0 StackPush Val:0055
0058 0 StackPush Val:0057
0059 0 StackPop
0060 0 StackPop
0061 0 StackPush Val:0055
0062 0 StackPush Val:0057
0063 0 GuardMethodRedefine Exit:0x7f0de99cff18 klass_flag:1 bop:7
0064 0 GuardTypeFixnum Exit:0x7f0de99cff18 R:0055
0065 0 StackPop
0066 0 StackPop
0067 0 FixnumLt LHS:0055 RHS:0057
0068 0 StackPush Val:0067
0069 0 StackPop
0070 0 GuardTypeNil Exit:0x7f0de99cff38 R:0067
0071 0 Jump TargetBB:bb:1
---------------
```
LIR上はオペランドスタック操作，ガード命令，定数定義，そして実際のプログラムの処理内容が一緒くたになって出力される．
オペランドスタック操作，ガード命令はは次の最適化フェーズで多くのコードが除去される．
---------------
BB0 (pc=(nil)) succ=[BB1]
0000 0 StackPop
0001 0 GuardTypeNil Exit:0x7f0de99cff38 R:0000
0006 0 LoadConstFixnum Val:3
0030 0 LoadConstNil
0057 0 LoadConstFixnum Val:b71b01
0002 0 Jump TargetBB:bb:1
---------------
BB1 (pc=0x7f0de99cfe50) pred=[BB5,BB0] succ=[BB3]
[self=v21,(0, 2)=v19]
0004 0 EnvLoad Level:0 Index:2
0005 0 StackPush Val:0004
0007 0 StackPush Val:0006
0012 0 GuardMethodRedefine Exit:0x7f0de99cfe78 klass_flag:1 bop:0
0013 0 GuardTypeFixnum Exit:0x7f0de99cfe78 R:0004
0014 0 StackPop
0015 0 StackPop
0016 0 FixnumAddOverflow LHS:0004 RHS:0006
0019 0 EnvStore Level:0 Index:2 Val:0016
0021 0 LoadSelf
0022 0 StackPush Val:0021
0025 0 GuardMethodCache Exit:0x7f0de99cfeb0 R:0021 ci:0x7f0de99cfd10
0026 0 StackPop
0027 0 Jump TargetBB:bb:3
---------------
BB3 (pc=0x7f0de99ce188) pred=[BB1] succ=[BB5]
[self=v21,(0, 2)=v19]
[self=v39,(0, 2)=v19]
0039 0 LoadSelf
0040 0 StackPush Val:0039
0043 0 GuardMethodCache Exit:0x7f0de99cfee0 R:0039 ci:0x7f0de99d16f0
0044 0 StackPop
0045 0 Jump TargetBB:bb:5
---------------
BB5 (pc=0x7f0de99ce188) pred=[BB3] succ=[BB1]
[self=v39,(0, 2)=v19]
[self=v39,(0, 2)=v55]
0055 0 EnvLoad Level:0 Index:2
0056 0 StackPush Val:0055
0058 0 StackPush Val:0057
0063 0 GuardMethodRedefine Exit:0x7f0de99cff18 klass_flag:1 bop:7
0064 0 GuardTypeFixnum Exit:0x7f0de99cff18 R:0055
0065 0 StackPop
0066 0 StackPop
0067 0 FixnumLt LHS:0055 RHS:0057
0070 0 GuardTypeNil Exit:0x7f0de99cff38 R:0067
0071 0 Jump TargetBB:bb:1
---------------
最適化によって得られたLIRは上記のとおりとなった．
この後RuJITはバックエンドにLIRを渡し機械語を生成する．
RuJITの中間表現 LIR
Ruby向けJITコンパイラ RuJIT Advent Calendar 4日目です．
今日はRuJITの中間表現 LIRを紹介します．
RuJITの中間表現LIRはYARVバイトコードを参考に設計したレジスタベースの中間表現で，実行時に収集した型情報をもった中間表現です．
LIRの定義はlir.defに記述されています．LIRの命令はどのように定義されているのでしょうか？．LIRの各命令は以下の形式にのっとって記述されています．
命令名 :フラグ* (命令の引数リスト)
フラグにはdef, use, trans, effect, frame, terminator, transがあり，それぞれdefは変数定義の有無，useは変数の使用，effectは副作用の有無，frameはメソッドフレーム操作の有無，そしてterminatorはブロックの末端に来て良い命令であることを示しています．
命令の引数リストはそれぞれ”引数の名前:引数の型”の形式をとっており，ここで引数の型はC言語上での型を意味します．
これだけではよくわからないので実例を出しながら説明していきます．
以下にFixnumの加算を扱うLIR命令FixnumAddOverflowの定義を示します．
FixnumAddOverflow :def :use (LHS:lir_t, RHS:lir_t)
FixnumAddOverflow，def, useのフラグを持ち，２つの引数を持つ命令です．
もう１つ例としてArray.set(Index, Value)を表す命令ArraySetの定義を示します．
ArraySet :def :use :effect (Recv:lir_t, Index:lir_t, Val:lir_t)
ArraySetはdef, use, trans, effectのアノテーションを持ち，3つの引数を持つ命令として定義されています．
# コードの自動生成
現在LIRの命令数は130命令程度となっており，命令数は開発当初から増え続ける一方となっています．命令が追加・変更されるたびにLIRの生成，dump関数，フラグの設定を行うのを正しく実装するのは困難を極めます．
そこでRuJITでは各命令用の構造体，命令生成関数，引数へのアクセッサ，dump関数，そして各種フラグを自動で生成する仕組みを導入し開発コストを抑えるようにしています．
例として先程も例としてあげたFixnumAddOverflow命令の定義から生成されたコードを見て行きたいと思います．以下にFixnumAddOverflow命令の定義を再掲しておきます．
FixnumAddOverflow :def :use (LHS:lir_t, RHS:lir_t)
現在RuJITでは主に5つのコード列を生成します．
はじめにopcodeの番号やフラグ管理用の定数定義です．
ここで定義されている値はlir_is_terminator関数やlir_is_guard関数などから直接的・関節的に参照され，RuJITの各機能を記述するのに必要な行数の削減に貢献しています．
1114 #define OPCODE_IFixnumAddOverflow 26
1115 #define LIR_USE_FixnumAddOverflow 1
1116 #define LIR_DEF_FixnumAddOverflow 1
1117 #define LIR_SIDE_EFFECT_FixnumAddOverflow 0
1118 #define LIR_IS_TERMINATOR_FixnumAddOverflow 0
1119 #define LIR_PUSH_FRAME_FixnumAddOverflow 0
1120 #define LIR_IS_GUARD_INST_FixnumAddOverflow 0
続いて命令の構造体の定義を生成します．コード生成やコード最適化器はここで定義された構造体を操作し変形・コード生成を行っていきます．
1121 typedef struct IFixnumAddOverflow {
1122 lir_inst_t base;
1123 lir_t LHS;
1124 lir_t RHS;
1125 } IFixnumAddOverflow;
次はコード生成関数です．RuJITではコード生成の際，一旦LIR命令の実態をスタック上に確保した後ヒープにコピーするという順番で命令の生成を行っています．（このような形になっているのにはいくつか理由がある．主な理由の１つには命令生成後，最適化によってすぐに不要となる命令などがあるため）ADD_INSTマクロによってコードはブロックに追加されていきます．
1127 static lir_t Emit_FixnumAddOverflow(lir_builder_t *builder, lir_t LHS, lir_t RHS)
1128 {
1129 IFixnumAddOverflow *ir = LIR_NEWINST(IFixnumAddOverflow);
1130 ir->LHS = LHS;
1131 ir->RHS = RHS;
1132 return ADD_INST(builder, ir);
1133 }
1146 static lir_t *GetNext_FixnumAddOverflow(lir_inst_t *Inst, int idx)
1147 {
1148 IFixnumAddOverflow *ir = (IFixnumAddOverflow *)Inst;
1149 switch(idx) {
1150 case 0:
1151 return &ir->LHS;
1152 case 1:
1153 return &ir->RHS;
1154 }
1155 return NULL;
1156 }
1134 static void Dump_FixnumAddOverflow(lir_inst_t *Inst)
1135 {
1136 #if DUMP_LIR > 0
1137 IFixnumAddOverflow *ir = (IFixnumAddOverflow *)Inst;
1138 fprintf(stderr, " " FMT_ID " %d FixnumAddOverflow", lir_getid(&ir->base), ir->base.flag);
1139 fprintf(stderr, " LHS:");
1140 fprintf(stderr, FMT(lir_t), DATA(lir_t, ir->LHS));
1141 fprintf(stderr, " RHS:");
1142 fprintf(stderr, FMT(lir_t), DATA(lir_t, ir->RHS));
1143 fprintf(stderr, "\n");
1144 #endif /*DUMP_LIR > 0*/
1145 }
RuJITの中間表現 LIRへのコンパイラ
Ruby向けJITコンパイラ RuJIT Advent Calendar 5日目です．
今日はYARVバイトコードからLIRへのコンパイラについて書きます．
YARVバイトコードからLIRへのコンパイラはsendやinvokeblockなど
複雑なバイトコード命令を除きほとんどが自動生成されるコードによって
変換されます．
変換ルールはyarv2lir.rbに用意されているDSLによって記述されています．
ここではローカル変数を取得するYARVバイトコードgetlocal，そして加算を扱うopt_plusのコードを紹介します．
getlocal命令はEnvLoadのLIR命令に１体１対応しているので特に難しいことはない．ここで，local.idx, local.lev, local.vはLIR命令への変換時に利用している一時変数でコードが生成された時にはC言語のローカル変数として振る舞う．つまりlocal.idx, local.leveはint型の変数，そしてlocal.vはLIRのレジスタ型の変数となっています．
245 match(:getlocal) {
246 local.idx = operand :int, 1
247 local.lev = operand :int, 2
248 local.v = emit :EnvLoad, local.lev, local.idx
249 push local.v
250 }
opt_plus命令からLIR命令の変換は実行されるパスによって生成される命令が異なる．ここではguard式によって型チェック，メソッドの再定義の検査をして対応するLIR命令の生成を行っています．
660 match(:opt_plus) {
661 local.snapshot = take_snapshot
662 local.ci = operand :CALL_INFO, 1
663 local.obj = pop
664 local.recv = pop
665 local.vobj = topn(0)
666 local.vrecv = topn(1)
667 guard(:Fixnum, local.recv, local.vrecv, local.snapshot) {
668 guard(:Fixnum, local.obj, local.vobj, local.snapshot) {
669 guard('Fixnum.+') {
670 local.v = emit :FixnumAddOverflow, local.recv, local.obj
671 push local.v
672 }
673 }
674 }
675 guard(:Float, local.recv, local.vrecv, local.snapshot) {
676 guard(:Float, local.obj, local.vobj, local.snapshot) {
677 guard('Float.+') {
678 local.v = emit :FloatAdd, local.recv, local.obj
679 push local.v
680 }
681 }
682 guard(:Fixnum, local.obj, local.vobj, local.snapshot) {
683 guard('Float.+') {
684 local.t = emit :FixnumToFloat, local.obj
685 local.v = emit :FloatAdd, local.recv, local.t
686 push local.v
687 }
688 }
689 }
ところで，RubyでDSLを記述するのは初めてだったのでRubyプログラム上でローカル変数の代入操作にフックする方法がわかっていない．
このDSLは，あまり綺麗にかけたとは思っていないので，もし上手い書き方があるのなら書き直したいところである．
