Just In Time(JIT) コンパイラとは？
Ruby向けJITコンパイラ Advent Calendar1日目．
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
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のみとなったようです．）
