RuJIT: a trace-based JIT compiler for CRubyの概要
Ruby向けJITコンパイラ RuJIT Advent Calendar 2日目です．
今日は，現在私が開発を行っているCRuby向けtrace-based JIT, RuJITの概要を説明していきたいと思います．
はじめに
RuJITはCRuby用trace-based JITコンパイラです．
開発は以下URLにて行っています．
https://github.com/imasahiro/rujit
Ruby向け最適化コンパイラ(AOTコンパイラも含む)はすでにいくつか存在しているなかで，なぜ新たに実装をしているかというと，以下3点を自分で理解するという目的のために開発を始めました．
- trace-based JITはRubyに適した方式なのか？
- メソッドもしくはブロックインライン化などの最適化による性能向上の余地がRubyにどの程度残っているのか？
- 一般に利用されているRubyアプリケーションのなかでどこがボトルネックになっているのか
なお，RuJITは2014年4月中頃から開発を始め，2014年12月現在，3度の作りなおしを経て，現在4回目の再実装を行っている最中でありますが，そろそろ完成形が見えてたような気がしております．
RuJITの全体像
RuJITは大きく分けて4つのコンポーネントから構成されます．
以下では，それぞれの機能について見ていきます．
1. トレース選択器
トレース選択器は実行中のYARVバイトコード列からトレースの検出を行います．このトレースの検出にはNET(Next Executing Tail)と呼ばれる戦略を利用して行っています．
トレース選択器は，まずトレースの起点の候補を以下の２つの条件をもとに選択します．
１つ目の条件はバイトコード列から近似的にループ構造を検出し，２つ目の条件は，すでにコンパイルされたトレースには含まれていないパスをコンパイル対象に含めることが可能となります．
これら２つの条件によって選択されたトレースの起点候補のうち，実行回数がしきい値をこえたものはトレース選択器にホットなトレースとして認識されます．RuJITはこの段階で初めてトレースの記録を開始し，実行されたバイトコード，YARV上で実行された型チェックや分岐の方向の記録などを行います．
トレースの記録は，トレース選択器がループ構造を検知した段階で終了し，得られたトレース情報からRuJIT内部表現への変換を始めます．
2. YARVバイトコードからRuJIT内部表現へのコンパイラ
トレースの記録が終了するとRuJITはトレースに含まれるYARVバイトコードからRuJIT内部表現へ変換を始めます．
この変換の際，トレース記録中に利用された型情報や分岐方向を用いてYARVバイトコードから型特殊化されたRuJIT内部表現への変換を行っています．
以下にYARVバイトコードopt_plusをRuJIT内部表現に変換する例を示します．
```
VALUE recv, obj;
if (recv was Fixnum) {
if (obj was Fixnum) {
if (Fixnum.+ was not redefined) {
EMIT FixnumAddOverflow, RegRecv, RegObj
}
}
}
```
3. コード最適化器
YARVバイトコードからRuJIT内部表現への変換が終了するとRuJITはコード最適化を行います．
現時点で適応している最適化は以下のとおりです．
- Constant Folding
- Dead Code Elimination
- Dead Store Elimination
- Loop Invariant Code Motion
- Stack Allocation
- Peephole Optimization
4. RuJIT内部表現から機械語へのコンパイラ
最後にRuJITはRuJIT内部表現から機械語に変換し，機械語をコードキャッシュに格納してRuJITのコンパイル処理は完了します．
機械語への変換にはCコンパイラ方式（RuJIT内部表現⇒Cソースコード⇒機械語）とLLVM IR方式（内部表現⇒LLVM IR⇒ 機械語）の２種類を用意しています．
ただし，デバッグのしやすさからCコンパイラ方式のみがメンテナンスされています．
まとめ
本稿ではRuJITのモチベーション，そして概要としてRuJITの処理の流れについて説明しました．
