2014-12-03

RuJITの動かし方

Ruby向けJIT コンパイラ RuJIT Advent Calendar 3日目です．

本稿では，RuJITのビルド方法と動かし方について説明します．
本稿ではOSX環境を前提に話を進めますが，Linux環境でも同じように動作すると思います．

ビルドに必要なソフトウェア

RuJITはCRubyのVM部分を拡張する形で実装されています．
RuJITのビルドにはCRubyのビルドで必要な以下のソフトウェアがインストールされている必要があります．

autoconf, autotool
Cコンパイラ. gcc もしくはclang

RuJITのソースコード取得

RuJITのソースコードは以下のgithubのページから取得することができます．

git clone https://github.com/imasahiro/rujit.git rujit

RuJITのビルド方法

RuJITのビルドはCRubyのビルド方法と同じくconfigure, makeを使って行います．

$ cd /path/to/rujit_src_dir
$ autoreconf -ivf # 必要に応じて
$ cd /path/to/rujit_build_dir
$ /path/to/rujit_src_dir/configure
$ make miniruby

生成されたminirubyバイナリがRuJITのバイナリとなります．（わかりにくいですね．）

RuJITのオプション

RuJITはRuJITをコンパイルする際に設定可能な定数をいくつか用意しています．その中から有用なオプションについて説明したいと思います．

チューニング用途

#define LIR_MIN_TRACE_LENGTH 8 /* min length of instructions jit compile */
#define LIR_MAX_TRACE_LENGTH 1024 /* max length of instructions jit compile */

コンパイル対象となったYARV バイトコード列はLIR命令の長さでLIR_MIN_TRACE_LENGTH <= n <= LIR_MAX_TRACE_LENGTHの時，機械語へコンパイルされます．

また，以下のオプションによって，トレースがどの程度頻繁に実行されたらコンパイル対象とするかが設定できます．

#define HOT_TRACE_THRESHOLD 2
#define BLACKLIST_TRACE_THRESHOLD 8

デバッグ用途

トレースされたYARV バイトコードの出力
#define DUMP_INST 0 /* 0:disable, 1:dump */

生成されたLIRの出力

#define DUMP_LIR 1 /* 0:disable, 1:dump */

最適化のon/off

LIRに適応する各種最適化パスのon/offがコントロールできるようになっています．
#define LIR_OPT_PEEPHOLE_OPTIMIZATION 1
#define LIR_OPT_CONSTANT_FOLDING 1
#define LIR_OPT_DEAD_CODE_ELIMINATION 1
#define LIR_OPT_INST_COMBINE 1
#define LIR_OPT_INST_COMBINE_STACK_OP 1
#define LIR_OPT_LOOP_INVARIANT_CODE_MOTION 0
#define LIR_OPT_ESCAPE_ANALYSIS 1
#define LIR_OPT_RANGE_ANALYSIS 1
#define LIR_OPT_BLOCK_GUARD_MOTION 1

コード生成器の切り替え

RuJITはバックエンドとして複数のコード生成器を切り替え可能なように設計されています．12月の段階でバックエンドとしてCコンパイラを使うCGENとLLVM コンパイラフレームワークを利用するLLVMの２種類が用意されています．（なおLLVMバックエンドは実験的実装なため非公開となっています．）
以下のオプションではバックエンドを切り替えることが可能となっています．
#define USE_CGEN 1
//#define USE_LLVM 1

まとめ

本稿では，RuJITのビルド方法と動かし方について説明しました．明日はサンプルコードを用いながらRubyプログラムがどのように機械語へコンパイルされるかを紹介したいと思います．

2014-12-03

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つのコンポーネントから構成されます．

トレース選択器
YARV バイトコードからRuJIT内部表現へのコンパイラ
コード最適化器
RuJIT内部表現から機械語へのコンパイラ

以下では，それぞれの機能について見ていきます．

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の処理の流れについて説明しました．

2014-12-01

Just In Time(JIT) コンパイラとは？

Ruby向けJIT コンパイラ Advent Calendar1日目．

１日目はJIT コンパイラについて書こうと思います．

JIT コンパイラとは？

JIT コンパイラとは，プログラム実行中にコンパイルを行うコンパイラです．Wikipediaによれば以下の様なものを指すようです．

実行時コンパイラ（Just-In-Time Compiler、JIT コンパイラ、その都度のコンパイラ）とは、ソフトウェアの実行時にコードのコンパイルを行い実行速度の向上を図るコンパイラのこと。
引用元: <cite>http://ja.wikipedia.org/wiki/実行時コンパイラ</cite>

近年では，JIT コンパイラは多くのプログラミング言語における高速化技術として必要不可欠のものとなりました．JIT コンパイラを搭載した言語処理系の例を挙げるとすれば，Java言語処理系ではHotSpot VM，Dalvik VM，JavaScript処理系ではV8やSpiderMonkeyが有名だと思います．

JIT コンパイラのコンパイル戦略

JIT コンパイラの多くは，コンパイルにより得られるメリット（速度向上）とコンパイルによるデメリット（コンパイル時間，メモリ消費）の兼ね合いからプログラム中で頻繁に実行される箇所(HotSpot)だけをコンパイルするという戦略をとっています．

そして，どのコードをコンパイル対象とするかを選択するかの戦略によってJIT コンパイラは２つに分類できます．

Method-based JIT
Trace-based JIT

Method-based JIT

Method-based JITは頻繁に実行されるメソッドをコンパイル対象とするコンパイラです．Java言語処理系HotSpotVMが採用しているコンパイル戦略だと聞いています．

この戦略の良い点は単純であるという点だと思います．悪い点は頻繁には実行されないメソッドはコンパイル対象とならない点，そして頻繁に実行されないパスを含めてコンパイルが行われてしまう点かと思います．

Trace-based JIT

Trace-based JITは実行時のプロファイル情報から頻繁に実行されるパスだけコンパイル対象とする戦略をとり，それ以外のコードはインタプリタによって実行されます．Trace-based JITのコンパイル対象は頻繁に実行されるパスのみであるためMethod-based JITに比べ，積極的な最適化が適応可能です．しかしJIT コンパイル対象以外のコードの実行が多くなるとコンパイル済みコードとインタプリタ間の遷移のオーバヘッドが無視できなくなるため全体的な速度は低下する場合もあります．

なお，Trace-based JITにおけるコンパイル対象の選択ですが，BalaらのDynamo[1]によるNext-Executing-TailとDavid HinikerらによるLast-Executed Iterationと呼ばれる２つのアルゴリズムをベースとしたものが現在使われています．詳細は論文を参照していただければと思いますが，どちらのアルゴリズムも，これまでに実行したバイトコードと現在実行しているバイトコードを元にループ構造を見つけ，それをコンパイル対象とするというアルゴリズムとなっています．

第３の戦略

Method-based JIT，Trace-based JITのどちらにも利点があり，どちらにも欠点があります．そして互いに競合する技術というわけではなく，併用することも可能です．最近までFirefox JaegerMonkeyではMethod-base，Trace-base両者のJIT コンパイラを兼ね備えたハイブリッドなコンパイル戦略も採用されていました．（ただし型推論の導入によってMethod-baseだけでも十分な性能がでることがわかったため，Method-basedのみとなったようです．）

まとめ

本稿ではJIT コンパイラの戦略について概要を述べました．今日はこの辺で．