RuJIT開発日記

Ruby処理系向けトレース方式JITコンパイラRuJITの開発日記

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点を自分で理解するという目的のために開発を始めました.

 

  1. trace-based JITRubyに適した方式なのか?
  2. メソッドもしくはブロックインライン化などの最適化による性能向上の余地がRubyにどの程度残っているのか?
  3.  一般に利用されているRubyアプリケーションのなかでどこがボトルネックになっているのか

なお,RuJITは2014年4月中頃から開発を始め,2014年12月現在,3度の作りなおしを経て,現在4回目の再実装を行っている最中でありますが,そろそろ完成形が見えてたような気がしております.

RuJITの全体像

RuJITは大きく分けて4つのコンポーネントから構成されます.

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

1. トレース選択器

トレース選択器は実行中のYARVバイトコード列からトレースの検出を行います.このトレースの検出にはNET(Next Executing Tail)と呼ばれる戦略を利用して行っています.
トレース選択器は,まずトレースの起点の候補を以下の2つの条件をもとに選択します.

1つ目の条件はバイトコード列から近似的にループ構造を検出し,2つ目の条件は,すでにコンパイルされたトレースには含まれていないパスをコンパイル対象に含めることが可能となります.

これら2つの条件によって選択されたトレースの起点候補のうち,実行回数がしきい値をこえたものはトレース選択器にホットなトレースとして認識されます.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⇒ 機械語)の2種類を用意しています.
ただし,デバッグのしやすさからCコンパイラ方式のみがメンテナンスされています.

まとめ

本稿ではRuJITのモチベーション,そして概要としてRuJITの処理の流れについて説明しました.

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

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

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

JITコンパイラとは?

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

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

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

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

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

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

  • 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と呼ばれる2つのアルゴリズムをベースとしたものが現在使われています.詳細は論文を参照していただければと思いますが,どちらのアルゴリズムも,これまでに実行したバイトコードと現在実行しているバイトコードを元にループ構造を見つけ,それをコンパイル対象とするというアルゴリズムとなっています.

第3の戦略

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

 

まとめ

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

RuJIT開発日記

Ruby処理系向けトレース方式JITコンパイラRuJITの開発日記を始めました.