Java JIT コンパイラの高速化手法
首藤 一幸 †
Java JIT コンパイラには，生成コードの質だけでなく，コンパイル時間，メモリ消費量，Java
仮想マシン仕様への準拠といった，多くの相反する要求が課せられている．我々は，さらに開発コストをも考慮しつつ，研究基盤として有用なものを目指し，JIT コンパイラ shuJIT を開発してきた．本稿では，そこで用いてきたコード生成手法や様々な最適化手法とそれらの効果，またそこで得た知見を紹介する．

Optimization Techniques for Java JIT Compiler
Kazuyuki Shudo†

1

とも数ヵ月程度の期間で作る．

はじめにこの方針に基づいて，相反する多くの要求のバランス

Java バイトコードの実行時（Just-in-Time，JIT）コ
ンパイラには，一般の，実行前にコンパイル処理を完了

をとり，多くの工学的選択を行ってきた．コンパイラの開発は，ソースプログラムのパーサ，中間表現の扱するコンパイラとは異なる様々な要求が課せられていい，果ては最適化までかなりの労力を要する仕事である．単に生成するコードの質が良ければよいというもる．そのため，開発においては，性能といった技術的のではなく，コンパイルによる性能上の利得がコンパ要求にとどまらず，開発に要する労力という人的，工イルによって消費される時間やメモリ消費量に見合っ学的な要素もまた重要な指標である．

たものでなければ，コンパイルするに値しないのであ

本稿では，これらの指標を考慮して開発，選択，実る．また，Java 言語や仮想マシンの仕様 [2][4] は実行装してきたコンパイル手法，最適化手法を報告する．

結果の高い再現性を狙った厳しいもので，その規定の2

一部は性能向上の妨げとなる．
相反する多くの要求がある状況では，それぞれの要

shuJITshuJIT は我々が開発してきた Java バイトコードのJIT コンパイラである．Intel 社の IA-32，いわゆる x86
プロセッサを対象とし，OS は Linux と FreeBSD をサ求に特化した処理系の出現はごく自然なことであろう．例えば Sun 社の HotSpot Server VM はコンパイ
ル時間に糸目を付けず，高い性能を得ることに特化した Java 仮想マシン（JVM）および JIT コンパイラでポートする．C 言語とアセンブリコードで記述してあある．逆に組み込み向けの処理系では，性能を多少犠り，Sun 社の Java 2 SDK などに含まれる Classic VM

牲にしてもフットプリントが小さいことを優先するかという JVM と共に動作する．

JIT コンパイラを利用した研究の基盤として利用しもしれない．
我々は，分散処理など他の研究の基盤として用いるやすいものとするために，shuJIT が生成するコード

べく，shuJIT という JIT コンパイラを開発してきたを改変しやすい構造，コード生成手法を採った（第 3[6]．この開発には，次の方針で臨んだ．

章）．その結果，作者自身が諸研究 [10][7] に利用してきただけでなく，他の研究者によっても研究の材料と• 研究基盤として利用しやすいものとする．

して利用されてきた [8]．
また，研究基盤としての利用し易さと同時に，日常• 実用的なソフトウェアとする．

利用する JIT コンパイラとしての実用性も目指してき• 少ない労力で短期間で開発する．ひとりで，長くた．この試みもおよそ成功し，1998 年 9 月の公開以† 産業技術総合研究所

National Institute ofAdvanced Industrial Science and Technology<shudo@ni.aist.go.jp> http://www.shudo.net/

来，2001 年 3 月までの 2 年半の間に，ソースコードは7558 回，バイナリは 8476 回のダウンロードがあった．
1





Java
bytecode !" #$ %  %   &
$ %  '(  & !" # #)  *
(  *+ **,."//   





074.8



dmul

shuJIT internal
instruction

x86 machine
languageflush_cachedldaddl $8,%espdmul

fmull (%esp)

dst



図 3: コード生成手法



メータを指定する．







– 生成されたコード量を記録するか否か．



























































– コンパイル結果を保存，再利用するか否か．
– メソッドを何度呼ばれた際にコンパイルするか．

図 1: SPEC JVM98 の結果








0IORSV – インライン展開するメソッドの最大コード長．

  – クラスのロード時にメソッドをコンパイルしてしまうか，呼び出された際に初めてコンパイルするか．

           

!!"– ス レッド の ス ケ ジュー ル を POSIX.1b の
SCHED FIFO ，SCHED RR ，SCHED OTHER のいずれで行うか．

   #!$$"$%&
%' &!((&   )&*+ , !!" ,  #!$$"$% 

3          コード生成手法
多くのコンパイラは，ソースプログラムを RTL と

いった中間表現に変換し，その上で各種最適化を施し，ターゲットプログラムに変換する．しかし shuJIT で

図 2: Linpack Benchmark の結果

は，一般的なこの方式を採らなかった．JIT コンパイ
ラを開発する側であらかじめ生成コードの断片を用意

性能は図 1 と図 2 に示す通りである．計測には SPEC

しておき，それらをつなぎ合わせることでコード生成

JVM98 と Linpack Benchmark を用いた．いずれも，高い値が良い結果を表す．

を行う，という方式を採用した．これは，次の 2 点を優先した結果の選択である．

shuJIT の特徴を以下にまとめる．

• 開発コストの低減• コストが低く，かつ研究の基盤として活用し易い• 生成コードの改変し易さ

コード生成手法を採用（第 3 章）．

• strictfp に対応している [7]．

具体的には，図 3 に示すように，Java バイトコード命• コンパイル結果のネイティブコードをファイルに保存，再利用できる．このために，実行前に行え

おいた x86 ネイティブコード片に置き換える．

令を shuJIT の内部命令に変換し，それを，用意してこれにより，JIT コンパイラ内にアセンブラを持つる処理と，実行が始まって初めて行える処理を峻必要がなくなり，その分の開発コストを抑えることが別している．

できた．ネイティブコード片は，JIT コンパイラ自体• 再コンパイルなしに各種の挙動を制御できる．環境変数 JAVA COMPILER OPT でオプション，パラ

を C コンパイラでコンパイルしておく際にアセンブルしておくことができるからである．また，このコー

2

Making a cache of stack top on registers

定義する．shuJIT では，2 つのレジスタをキャッシュ

TYA (JIT for x86)’s Methodに用いることとして，図 4 に示す 5 状態を定義した．

stack

top

shuJIT’s Method
memorymemorymemory.....
state 0EDX
memorymemory.....
state 1

それぞれの shuJIT 内部命令について，5 状態に応じた

EAX
memory.....

register

ECX
EDX
memory.....
state 2

ネイティブコード片を用意しておき，ネイティブコー
ド片の実行終了時の状態に応じて，次のコード片を選んでつないでいくのである（図 5）．

EDX
ECX
memory.....
state 4ECX
memorymemory.....
state 3

この手法により，shuJIT では 2 つのレジスタを，
コード片をまたいで活用することが可能となった．2
つとは少なく聞こえるかもしれない．しかし x86 はもともと 8 つの汎用レジスタしか持たない上，スタック

図 4: スタック状態

ポインタとベースポインタも汎用レジスタに含まれる．
残りの 4 レジスタも，ひとつは JVM の局所変数のベーの他のレジスタもネイティブコード片の中では活用しドを思いのままに改変することができる．その結果，ている．x86 ではたいていの RISC プロセッサよりレ

生成コードを改変する研究の基盤として利用しやすい

ジスタが少ないために，レジスタ割り付けを行うか否ものとできた．

かの差が小さいのである．また，Pentium Pro 以降の
x86 プロセッサは実際には内部に数十の物理レジスタを持ち，8 つの汎用（論理）レジスタをそれらに割り.....

スアドレスをキャッシュする目的に利用している他，そJIT 開発者自身が手で記述できるため，生成するコー

shuJIT
内部命令

コード
生成

G

Ii

Java
バイトコード
命令

初期状態

SB i

ネイティブ
コード列
終了状態

付けている（レジスタリネーミング）．一般の RISC

Ni

ではレジスタの活用は完全にコンパイラの仕事だが，

SE i

x86 ではその多くをプロセッサが担っているのである．

=

プログラムの流れ

ド生成方式では，JIT が生成するネイティブコードを等しくする

shuJIT
内部命令

I i+1

G

初期状態

終了状態

このコード生成手法は x86 に向いている．

SB i+1

ネイティブ
コード列

N i+1

4

SE i+1

=
初期状態

.....

.....

shuJIT は機能面では第 2 章で述べた特徴を持っている．純粋に使用感の向上を求める一利用者の視点から見ると，短いコンパイル時間にも関わらず，インタSB i+2

図 5: スタック状態の整合
スタック状態

高速化手法

等しくする

.....

Java
バイトコード命令

コード
生成

プリタの数倍という実用的な性能向上が得られることが特徴である．つまり，コストパフォーマンスの良さ

このコード生成方式の大きな問題は，である．

レジスタ割り付けを行えないことである．近年のコン

これらの特徴を維持するためには，最適化を実装すピュータでは，アクセス遅延が相対的に非常に大きくるか否か，施すか否かを決定する際に，得られる性能

なってしまったメインメモリをいかにアクセスしない向上だけでなく，コストも考慮しなければならない．

かが高性能達成の鍵である．上述のコード生成手法はコストとは処理に費される時間やメモリを指す．

ネイティブコード片をまたいで複数のレジスタを活用

本章では，shuJIT に実装してきた各種の低コストすることが困難であり，性能上問題である．この難点

な最適化手法を紹介する．

を緩和するため，我々はスタック状態（図 4）という考え方を導入した．

4.1

JVM のスタックは基本的にメインメモリ上に設けるのだが，スタックトップ付近はレジスタでキャッシュ

生成コード間の直接呼び出し

ひとつの JVM 内には，インタプリタで実行されるする．そこで，スタックトップやその下をどのレジス

バイトコードのままのメソッド，C，C++言語で記述

タでキャッシュしているのか，という状態をいくつかされたネイティブメソッド，すでに JIT コンパイラに

3

しないことを確認しなければならない．callee がまだ
直接呼び出し共通呼び出しインタフェース
invoke
JITCompiled
Method ()(shuJIT内)

生成コード

コンパイルされていない場合，eager にコンパイルし共通呼び出しインタフェースてしまい，確実に JIT コンパイルできることを確認するようにした．

invocation
Helper ()(shuJIT内)これらの高速化の結果，CaﬀeineMark 3.0 の Method
ベンチマークのスコアが 1812 から 441 に，つまり 4invoke(JNI)Native
Method ()(Classic VM内)

ネイティブ
メソッド

倍強に向上した．これは，333 MHz の Pentium II と......

JDK 1.1.8 ，Linux の組み合わせでの結果である．
おそらく最も多く用いられているベンチマークである SPEC JVM98，特にその一部である 227 mtrt（マ

図 6: 直接呼び出し

ルチスレッド レイトレーシング）はメソッド呼び出し
よってコンパイルされたメソッドなど，多種類のメソッの性能に敏感なので，その高速化は非常に有効である．

ドが混在する．これらはお互いを相互に呼び出すので．

4.2

そのために共通の呼び出しインタフェース，すなわち末尾再帰の除去

引数の型の並びが決められている（図 6）．shuJIT がメソッドの末尾での再帰呼び出しはメソッド先頭へ対象とする Sun の Classic VM では次の通りである．

のジャンプに置き換えられることが知られている．この置き換えは末尾再帰除去（tail recursion elimination ）(JHandle *o, struct methodblock *mb,と呼ばれ，再帰呼び出しに伴うスタックの消費や，ス

int args_size, ExecEnv *ee)

タックポインタ，ベースポインタの操作をなくせるという利点がある．

図 6 中 invokeJITCompiledMethod() は shuJIT が

末尾再帰を積極的に使う Scheme 言語のプログラム

用意している関数で，JIT コンパイラが生成したコー
ドを呼び出すいわゆるラッパ（wrapper）である．生成

ならともかく，JVM 上で実行するプログラムにおいコードの呼び出しインタフェースも各種メソッドの共て現実にこの最適化が効奏する局面は少ない．しかし，

通インタフェースと同じにしてあるのだが，生成コー

最適化のコストはとても小さいので，Java プログラム

ドと他種のメソッドではスタックの使い方，成長方向にどの程度末尾再帰が現れるのか調べる目的もあり，が異なるため，引数の積み直しを行うために同関数を直接末尾再帰の除去を shuJIT に実装した．

用意してある．
実装

つまり，JIT 生成コードどう しの呼び出し では，

メソッド呼び出しを行うバイトコード命令は数

invokeJITCompiledMethod() の呼び出しは不要であ

種類ある中で，直接末尾再帰呼び出しを行い得る命令

り，これを省くことで関数呼び出しのオーバヘッドをは invokespecial と invokestatic である．バイト

削減することができる．そこで，JIT 生成コードどう

コード命令を shuJIT 内部命令に変換する際に，末尾

しは，ラッパを介さずに直接呼び出すという高速化を再帰である場合は invokerecursive という内部命令施した．

に変換する．これが最終的に，メソッド先頭へのジャJVM では動的ディスパッチがあって，例えば JIT コ
ンパイルされたメソッドがネイティブメソッドによってオーバライドされることもあり得るため，callee が JIT
生成コードなのかどうかを caller 側で判定しなければンプに変換される．

IBM 社が配布している Java 2 SDK 付属の JIT コン
パイラ JITC もこの最適化を行う．JITC は devirtual-

先が事前に一意に決まる場合，つまり static，private

ization という手法 [3] を用いて一部の動的呼び出しを
静的呼び出しに変換できるため，devirtualize された
動的呼び出しに対しても末尾再帰除去を施している．

または ﬁnal メソッドである場合には，callee が JIT 生

この最適化はコストこそ小さいものの，実際の効果ならない．この判定コストを削減するため，呼び出し

成コードか否かの判定も省くという高速化も施した．

も大きいものではない．SPEC JVM98 くらいの大きこの高速化のためには callee が確実に JIT コンパイルさをもったプログラムであっても，直接末尾再帰を除できること，何らかの理由でコンパイルに失敗したり去できる箇所はせいぜい数箇所であり，ベンチマーク

4結果への影響は有意なものではない．

シグナルを用いることで条件分岐なしに上記の例外を検出できる．条件分岐，すなわち正常系のオーバヘッ

失敗談

ドをゼロにできるのである．

末尾再帰除去の最初の実装には不具合があった．当初，直接再帰呼び出しの直後の return を末尾

void signal_handler(int sig, ...) {struct sigcontext *sc = ...
シグナルコンテクストを取得;

再帰であるとみなしていたが，この単純な判定方法には欠陥があった．aMethod() というメソッド中に次のswitch (sig) {シグナルの種類に応じた処理 (例外の throw など)}

コードがあった場合を考える．

try { return aMethod() }catch (Exception e) { ...

シグナルコンテクスト中のプログラムカウンタを書き換える;}

return;try 節中の aMethod() の呼び出しは一見末尾再帰に見}えるが，実はそうではない．aMethod() の呼び出しで例外が発生した場合，呼び出しから戻った後，return

図 7: シグナルハンドラの処理はせずに catch 節に制御が移る．この恐れがある限り，
この呼び出しを末尾再帰としては扱うわけにはいかな

シグナルハンドラ中で行う処理を図 7 に示す．まい．もし aMethod() が例外を throw し得ないなら末尾ず，例外が発生したスレッドのコンテクスト（structsigcontext 型）を取得する．続いて，シグナルの種類とコンテクストに基づいて発生した例外の種類を判再帰として扱えるのだが，JVM ではメモリ不足や他スレッドによる強制停止（java.lang.Thread#stop() ）によって非同期に例外が発生し得る．つまり，呼び出定し，その例外を throw する．最後に，シグナルハン

し後に catch 節に制御が移る可能性のある呼び出しは，ドラから戻った後で適当な catch 節や return から実末尾再帰としては扱えないのである．

行が続くように，コンテクスト中のプログラムカウン
タの値を書き換えて，シグナルハンドラを抜ける．

この問題報告を受け，try 節中のメソッド呼び出し
を末尾再帰として扱わないように判定方法を修整した．

4.3

Code Patching shuJIT は例外の捕捉以外の目的にもシグナルを利用する．生成したコードを x86 の INT
3 命令で上書きしておいて SIGTRAP を発生させ，シグシグナルの活用

例外の捕捉

他の多くの JIT コンパイラと同様に，以ナルハンドラ中である必要な処理を行った後，INT 3

下の通り，shuJIT も OS のシグナルを例外を捕捉する

命令の上に元の命令を書き戻す．この操作によって，ために活用している．

その生成コードが初めて実行されたときのみ，ある必
要な処理を行うことができる．これを生成コードの書• SIGSEGV で NullPointerException を検出．
• SIGFPE で ArithmeticException を検出．
• SIGSEGV で StackOverflowError を検出．

き換えなしに達成するには条件分岐が必要であり，それによるオーバヘッドは避けられない．生成コードの書き換えについて，詳しくは第 4.4 節で述べる．

Classic VM 中で JVM の null は 0 で表現されているので，それをオブジェクトとしてアクセスすると SIGSEGVが 発 生 す る ．つ ま り，NullPointerException
を 検 出 で き る ．ま た ，ゼ ロ 除 算 で は SIGFPE が4.4

生成コードの書き換え

Java 言語仕様 [2] に準拠するためには，何通りかの局面で，あるバイトコード命令を初めて実行したとき

発 生 し ，ArithmeticException を 検 出 で き る ．

だけある処理を行う，という必要がある．その処理は，StackOverflowError を検出するためには，メソッ
ド呼び出しの直前にわざとスタックの成長方向の少し先，数百から数千番地先をアクセスする．もしアクセ

2 度目以降の実行では，行ってはならないか，または，性能のためにはできれば行いたくないものである．

ス先が有効なアドレスでなければ SIGSEGV が発生し，クラスの初期化 static 変数アクセス，static メソッド

スタックの溢れを検出できる．

呼び出し，インスタンス生成がクラスの初期化を

5

引き起こし得る．

コンパイルされずに性能に劣るインタプリタで実行さインスタンス生成時の諸チェック クラスが interface

れ続けてしまう．後者の方法はひとつのメソッドを 2や abstract クラスだったら IllegalAccessError

度コンパイルするので，コンパイル処理に消費されるを throw する．

時間が増えてしまう．

interface 呼び出しの呼び出し先解決結果チェック
メ ソッド が 見 付 か ら な け れ ば Incompatible

JITコンパイラが生成するコード:......
一度だけ
NOP
実行される
NOP
初回実行時のみの処理「NOP」を「JMP done」に書き換える
done:......

ClassChangeError を throw する．
JIT コンパイラの実装者にとっては，これらの処理はJIT コンパイル時に行ってしまうという実装が容易なのだが，それでは JVM 仕様には沿えない．アプリケー
ションプログラムが期待された通りに動かないことも一度実行された後:ある．

不要な処理をスキップ......
JMP done
初回実行時のみの処理「NOP」を「JMP done」に書き換える
done:......

Java 言語仕様第二版は，12.4.1 When Initialization
Occurs にて，クラスが初期化されるタイミング，つまり static ブロックの実行と static 変数の初期化が行われるタイミングを厳密に定めている．JIT コンパイラ
にとって都合の悪いことに，static 変数へのアクセスと

static メソッドの呼び出しがクラスの初期化を引き起図 8: NOP 命令をジャンプ命令で上書きする方法

こし得る．例えば，初期化されていないクラスの static
変数を読み出そうとした時点でそのクラスを初期化しse制御の流れシグナルハンドラ:

void signal_handler(...) {なければならない．

※ 初回だけの処理を行う;
コンパイル時:生成したコードを「INT 3」で上書きしておく

これを素朴に実装してしまうと，static 変数アクセスと static メソッドの呼び出しのごとに対象クラスが......
INT 3......

INT 3 を元のコードで上書きする;
シグナルコンテクスト中のプログラムカウンタを設定;

初期化済みかどうかを判定する条件分岐を行うことに
JITコンパイラがなりかねない．条件分岐のオーバヘッドは極力避けた生成するコード

い．実際には，JIT コンパイルの時点でそのクラスが}※ 実際は、ここで処理を行ってしまうとシグナルハンドラ中でシグナルが発生してしまい得るため、ここではその処理へジャンプする
トランポリンを生成し、ハンドラの後、トランポリンが実行されるようにする。

初期化済みであればこの判定処理を生成する必要はな
いため，これだけで条件分岐はかなり省ける．

図 9: ソフトウェア割り込み命令を本来の命令で上書

この頻繁な条件分岐を避けつつ，2 度目以降の実行

きする方法

では無駄な処理を行わないためには次の方法がある．

• 初めての実行はインタプリタで行い，2 度目に呼shuJIT に実装された 2 つの方法 shuJIT は，コード書き換えを行うことで，上述の問題を被ることなしに JVM 仕様に完全に準拠している．生成されて 1 度実行されたコードを上書きするのである．コード書きび出された時点で初めて JIT コンパイルを行う．

• 初めての呼び出しで JIT コンパイルを行ってしまう．このときは，必要に応じてクラスの初期化を行えるコードを生成しておく．2 度目の呼び出し

換え（code patching）の方法として以下の 2 通りを実で再度コンパイルする．今度は，初期化済みを仮装してあり，JIT コンパイラ自身を C コンパイラでコ定してコンパイルできる．

ンパイルする時点で選択できるようにしてある．
図 8: 無操作命令（NOP）をジャンプ命令（JMP）でしかし，どちらの方法も大きな問題を抱えている．前上書きする方法（ジャンプ命令法）

者の方法では，初めて呼び出されたメソッドの処理が

図 9: ソフトウェア割り込み命令（INT）を本来の命多かった場合，例えば繰り返し回数の非常に多いループがあった場合に問題が起こる．重いメソッドが JIT

令で上書きする方法（割り込み命令法）

6

ソフトウェア割り込み命令としては，もともとデバッ

上書きされる前の命令

上書き後の命令

ジャンプ命令 (JMP)

ジャンプ命令 (JMP)

無操作命令 (NOP)

無操作命令 (NOP)

割り込み命令 (INT)

本来の命令ガのために用意してある唯一の 1 バイト命令である

INT 3（0xCC）を用いた．JVM がマルチプロセッサで実行されることを考えると，複数バイトの書き換え
は atomic に行わねばならない．atomicity の保証には最悪の場合メモリバスのロックが必要であり，JIT コ
ンパイラが複雑になると共に性能上のペナルティもある．atomicity を気にせずに済むように，1 バイト命令

shuJITに実装した方法を採用した．

検討に値する方法

どちらの方法にもそれぞれの利点がある．ジャンプ

実装は可能であるものの採用する理由のない方法

命令法では，2 度目以降の実行でも毎回ジャンプ命令を実行せざるを得ないが，割り込み命令法では，2 度

図 10: コード書き換えの方法

目以降は完全に無駄のないコードになるので，数度目以降にはペナルティは皆無となる．一方，メモリ消費の少なさでどちらが勝るかは実装方法に依る．ジャン

成コードだけでなく，この例外表が消費しているメモ

プ命令法では生成コード中に初回のみの処理が何度もリも含めて消費量を計測した結果が次の通りである．

コピーされてしまうため，生成コード量の少なさは割

ジャンプ命令法

り込み命令法が勝る．しかし，割り込み命令法では，割り込み命令法1682 KB
1773 KB

上書きする本来の命令を JIT コンパイルの時点でどこかに保存しておく必要があるため，その表が消費する

結局，割り込み命令法の方がメモリを多く消費していメモリを考慮しなければならない．最終的にどちらがることがわかった．

メモリ消費の少なさで勝るかは，表管理の実装方法や
アプリケーションプログラムに依存するので，一概に考えられる他の方法断ずることはできない．

この 2 つの方法だが，コード書き換えの方法は他にもshuJIT に実装されているのは考えられる．書き換え前の命令と書き換え後の命令のshuJIT ではどちらの方法がメモリ消費量において勝るのか，Linux 上で Java 2 SDK 1.2.2を用いて調べた．アプリケーションプログラムとして組み合せによって，図 10 に示す数通りの方法があり得は，ウィンドウをひとつ開いて文字列を表示するだけ

またはジャンプ命令での上書きには，本来の命令を保のごく単純な Java アプレットを用いた．JIT コンパ

存しておく必要がないという利点がある．また，ときイラが生成したコード量の合計は次の通りで，当然なに，上書き前の命令として割り込み命令を用いないこ

がら割り込み命令法の方が少なかった．

との利点もある．例えば，ソフトウェア割り込みやシ

メモリ消費量る．本来の命令での上書きには数度目以降の実行ではペナルティを皆無にできるという利点があり，無操作

グナル関連の挙動や API はどうしてもプラットフォー
ジャンプ命令法1516 KB

ム依存になりがちなので，それらを利用すると JIT コ

割り込み命令法1408 KB

ンパイラ自体の保守性や移植性は低下しがちである．

しかし，JIT コンパイラが生成するのは直接実行され4.5

るコードだけではない．shuJIT は，ネイティブコード

インライン展開と同時に，シグナル発生時にプログラムカウンタの値

インライン展開（inlining ）はメソッド呼び出しコスから例外の種類やバイトコード上のプログラムカウン

トの削減と手続き内解析および最適化の適用範囲拡大

タを得るための例外表を生成する．shuJIT の割り込みにつながるポピュラーな最適化である．shuJIT ではそ

命令法の実装では，この例外表の各要素に，上書きすのコード生成手法の性質上，最適化の機会拡大にはつる本来の命令を保存するので，割り込み命令法を用いながらないが，メソッド呼び出しの高速化だけでも恩ると例外表のメモリ消費量は大きくなってしまう．生恵は大きいため，実装している．

7

callee をコンパイル時に特定できる場合，つまりバイ

高速化なし

高速化あり

高速化率

15535
34959

851
1567
（ミリ秒）

18.3 倍22.3 倍Pentium 4
Pentium III

トコード命令の invokespecial か invokestatic での呼び出しで，ある条件が満たされている場合に，インライン展開を行う．条件は次の通りである．

表 1: sqrt の呼び出し 10,000,000 回に要した時間• synchronized メソッドではない• catch 節を含まない

高速化なし

高速化あり

高速化率

4242
8021

1567
2226
（ミリ秒）

2.71 倍3.60 倍Pentium 4
Pentium III• ジャンプ命令を含まない

表 2: sin の呼び出し 10,000,000 回に要した時間• 長さが shuJIT 内部命令で 20 以下• caller と callee の双方とも strictfp ではないか，または，双方とも strictfp である

sin でも数倍，sqrt に至っては 20 倍前後の効果が見られた．この種の高速化はその特定のメソッドを利これらをすべて満たすメソッド呼び出しがインライン用するプログラムに対してのみ有効であるが，その効展開される．あるメソッドに対して展開処理を 2 回施果は大きい．shuJIT ではこの高速化処理が JIT コン

すので，展開されたメソッド中の呼び出しが展開されパイラに埋め込まれているので，分離や他のメソッド

るというインライン展開のネストは 2 重までである．

への拡張は容易には行えない．本来は，最適化処理は

上述の 20，2 という値はどの程度インライン展開をOpenJIT 2 [9] の Compilet のようにコンポーネントとして提供され，JIT コンパイラに対してプラグイン
できることが望ましい．

行うかというパラメータであり，JIT に対して外から指定できる（第 2 章）．インライン展開は，過度に施してしまうと，そのコード自体がキャッシュから溢れ

4.6

たり，他のコードをキャッシュから追い出すなど，性ピープホール最適化

能低下の原因ともなり得る．20，2 というパラメータ

shuJIT は，picoJava プロセッサ [5] の命令フォール

は，インライン展開の効果が大きいアクセサ（getter，

ディングに近いピープホール最適化を用いて，メモリ

setter メソッド）が展開されることを目標として決めた経験的な値である．
その他の条件は，インライン展開の処理を軽いもの

アクセスや浮動小数点数のレジスタ，メモリ間コピーに抑えるためと，実装を複雑にしないために設けたも数にコピーするために，局所変数に対してポップするのである．これらの条件が理由でアクセサを展開でき

命令と局所変数からプッシュする命令を続けて生成すを削減している．

Java コンパイラは，JVM のスタックトップを局所変ないことは少ないため，性能への影響は大きくないだ

る．操作対象が 32 ビット整数であれば istore ，iload

ろう．

という命令列となる．shuJIT 内部命令は Java バイト
コード命令に非常に近いので，この命令列をそのまま

特定メソッドのインライン展開

これまで述べた一般

ネイティブコードに変換してしまうと，ポップとプッのインライン展開の他にも，shuJIT はある特定のメ

シュという 2 度のメモリ操作を行うはめになってしま

ソッドを特別扱いして既定のコード列への展開を行う，

う．スタックトップから局所変数へのコピーを一度行

具体的には，java.lang.Math クラスの次のメソッド

えば済むにも関わらずである．

を x86 の浮動小数点演算命令に置き換える．

そこで shuJIT は，こういった簡略化が可能な命令列を検出して，別の，より処理が軽い内部命令に置き換

sqrt, sin, cos, tan, atan2, atan, log, ﬂoor,
ceil

える，というフォールディングを行う．istore ，iloadという命令列であれば，これと等価な内部命令 istld

sqrt と sin について，この高速化の効果を調べた．
表 1 と表 2 は，Linux 上で Java 2 SDK 1.3.1 を用いてに置換する．同じ方法で，浮動小数点数のレジスタと1.7 GHz の Pentium 4 と 600 MHz の Pentium III で計測した結果である．

合には値をレジスタに載せたまま演算を続けられるよ

メモリ間のコピーも削減し，浮動小数点演算が続く場
うにしている．

8この高速化は処理コストが低いながら，プログラム

この解決処理のコストは見落とされがちである．生によっては非常に効果が大きい．問題サイズ 500 × 500

成コードを保存，再利用する仕掛けを用意しても，JITの Linpack ベンチマーク [1] を 600 MHz の Pentium，

コンパイルのコストは皆無にはならないのである．

Java 2 SDK 1.3.1 ，Linux で実行した場合の結果を次に示す．
フォールディングなし
フォールディングあり

また，生成コードの保存には別の難点もある．保存
しようとすると，たとえ JIT コンパイル時にあるクラスが初期化済みであっても，それが初期化済みである

14.042 Mﬂops
19.083 Mﬂops

ことを仮定したコンパイルを行えなくなる．生成したコードを再利用する際にそのクラスが未初期化かもしれないからである．クラスが初期化済みであることをフォールディングの有無で 1.36 倍の差が開いている．

4.7

仮定できないと，コード生成手法によってはコード生

コードデータベース

成量や性能上のペナルティを被ることがある（第 4.4
節）．もっとも，shuJIT で割り込み命令法を用いた場

実行時にコンパイルを行う JIT コンパイラに対して，

合はどちらのペナルティもない．また，コードデータ

実行前にコンパイルを済ませておく Ahead-of-Time

ベースから引き出したコードはそのメソッドの 2 度目

（AOT）コンパイラは，コンパイルに費される時間が以降の実行から使うようにすることで，保存，再利用

実行時間に入ってこない点では JIT コンパイラより有する場合でもあらゆるクラスが初期化済みであること利だと言われている．

を仮定できる．

そこで，JIT コンパイラでも，生成したネイティブ

4.8

コードを保存しておいて，後日 JVM が起動された際にそのコードを再利用するという方法が考えられる．

その他小手先の高速化

この仕組みが shuJIT に実装してあり，環境変数経由

ループ先頭の整列

でオプションを指定することで利用できる（第 2 章）．

の 16 バイト境界に整列する．Pentium Pro，Pentium

JIT コンパイルすることを決定したメソッドについて，
コンパイルに取り掛かる前にコンパイル済みコードがII，Pentium III プロセッサは命令を 16 バイトずつ 1
クロックに最大で 3 命令デコードするので，ジャンプ保存されていないかどうか，コードデータベースを検先を 16 バイト境界に整列することで，デコーダの能索する．もし見付かったなら，コードデータベースか力を最大限に活用できる．

shuJIT はループの先頭をメモリ

整列によって命令列にすき間ができる．このすき間

らコードを引き出し，それをコンパイル結果とする．

は無操作命令（NOP）で埋めるか，長さが一定以上で
しかし実はコードを引き出しただけではあればジャンプ命令でスキップする．無操作命令やジャ済まない．JIT コンパイル結果のコード中には，クラス

ンプ命令にはわずかなオーバヘッドがあり，整列によ

オブジェクトやメソッドのアドレスなど，プログラム

る利得の方が必ず大きいとは限らない．そのため，速を実行するたびに変わり得る値が含まれている．ロー

くなるとは限らない．

リンク処理

ド後，これらを解決しなければならない．
ジャンプ命令の縮小

x86 の無条件相対ジャンプ命令には，5 バイト命令と 2 バイト命令の 2 通りの形式がある．

• 各種アドレスの解決:
static 変数，メソッド，C の関数，. . .
• 実行時になって作られる表への書き込み:メソッドの例外表

E9 XX XX XX XX
EB XX

shuJIT の中では，これら実行のたびに必要な解決処理とそれ以外の静的な処理が峻別してあり，静的な処理が済んだ時点でコードを保存する．コードデータベー

もしジャンプのオフセットが 1 バイトで表現可能ならスからロードしたコードについては，動的な解決処理

ら，後者の形式を用いた方が良い．shuJIT があらかじのみを行う．

め用意しているネイティブコード片の中ではジャンプ

ば，生成コード量とデコーダが扱える命令数の観点か

9

命令は常に 5 バイト命令であるが，可能であれば 2 バ[2] James Gosling, Bill Joy, Guy L. Steele Jr., and Gilad
Bracha. Java Language Specification, Second Edition. Addison Wesley, 2000.

イト命令に変換する．

[3] Kazuaki Ishizaki, Motohiro Kawahito, Toshiaki Yasue, Hideaki Komatsu, , and Toshio Nakatani. A
study of devirtualization techniques for a java justin-time compiler. In Proc. of ACM SIGPLAN Conference on Object-Oriented Programming Systems,
Languages, and Applications (OOPSLA’00), October 2000.

配 列 の 境 界 チェ ック の 改 良

JVM は 配 列に対する境界を越えたアクセスに対して
ArrayIndexOutOfBoundsException を throw しなければならない．これはもちろん JIT コンパイラが生成するコードでも同様である．

[4] Tim Lindholm and Frank Yellin. The Java T M Virtual Machine Specification. Addison Wesley, 1997.

shuJIT は初め，次のコードに相当するネイティブ
コードを生成していた．
if (index < 0)[5] Harlan McChan and Mike O’Connor. PicoJava: A
direct execution engine for Java bytecode. COMPUTER, Vol. 31, No. 10, pp. 22–30, October 1998.

throw;

if (index >= length)

throw;

この処理には 2 度の条件分岐が含まれている．後に，次の処理で境界チェックを行えることがわかった．

[7] Kazuyuki Shudo and Yoichi Muraoka. Eﬃcient
implementation of strict ﬂoating-point semantics.
In Proc. of 2nd Workshop on Java for HighPerformance Computing (in conj. with ICS’00), pp.
27–38, May 2000.

if (((unsigned)index - length) < 0)throw;
インデックスを符号なし整数とみなす，つまり，除算の後，キャリーフラグを検査するのである．これによっ[8] Matt Welsh and David Culler. Jaguar: Enablingeﬃcient communication and I/O from Java. In Concurrency: Practice and Experience, Special Issue onJava for High-Performance Applications, December
1999.

て，1 度の条件分岐で境界チェックを行える．

5[6] Kazuyuki Shudo. shuJIT—JIT compiler for Sun
JVM/x86, 1998.
http://www.shudo.net/jit/.

おわりに
本稿では，shuJIT に実装してきた様々な低コスト[9] 丸山冬彦. JIT コンパイラ向けアプリケーションフレー
ムワークの設計と実装. Master’s thesis, 東京工業大学,
February 2001.

高速化手法とその効果，また，そこで得た経験を紹介した．

[10] 首藤一幸, 根山亮, 村岡洋一. プログラマに単一マシン
ビューを提供する分散オブジェクトシステムの実現. 情報処理学会論文誌:プログラミング, Vol. 40, No. SIG
7, pp. 66–79, August 1999.

言語処理系は楽しい．shuJIT の設計，様々な最適化の実装，性能測定，JVM 仕様への追従，利用者とのイ
ンタラクション，デバッグなど，3 年間に渡ってたっ
ぷりと楽しんできた．本稿がどなたかの知的楽しみの一助となることを願って止まない．

謝辞
性能評価の環境を提供して下さった関口様をはじめとする産業技術総合研究所の皆様と早稲田大学の村岡洋一教授，第 4.2 節の失敗談で述べた欠陥を指摘して下さった前田修吾様，第 4.8 節で述べた配列境界チェッ
ク法を教示して下さった石崎一明様，shuJIT の動作報
告，問題報告を下さった利用者の皆様に感謝致します．

参考文献[1] Jack J. Dongarra and Reed Wade. Linpack benchmark — Java version.
http://www.netlib.org/benchmark/linpackjava/.

10

質疑応答
敬称は略します．

Q 田中 シグナルまわりは OS によっていろいろと異なりがちで，FreeBSD で版による違いで困った経験がある．シグナルで困った経験はないか．

A Linux ではシグナルコンテクスト（sigcontext ）を容易に取得できずにフレームを辿ってスタック上を探すというアクロバティックなことをしている．
Q 河野 コード書き換えでは命令キャッシュに書き換
え前の内容が残るなどの問題が起きがち．何か配慮をしているか．

池田駅

A 一般の RISC プロセッサでは命令キャッシュとパイ
プラインに書き換え前の内容が残るという問題に対処しなければならないが，x86 はそのあたりは勝手によきに計らってくれる．プログラマはサボれる．

Q 和田 コード書き換えの際，NOP 命令をジャンプ命
令で上書きしているが，それはジャンプ命令を本
来の命令で上書きするべきなのではないだろうか．

A 何か理由があっての選択だったと思うのだが，理由が思い浮かばない . . .
（プロシンの時点では第 4.4 節で言うところのジャンプ命令法のみが実装されていた．本来の命令で会場の池田町営田園ホール

上書きするには，その内容をどこかに保持しておかねばならないため，それを嫌って NOP をジャ
ンプで上書きする方法を採っていた．
）

ワイン城での夕食

11