論 文Java Just-in-Time コンパイラのためのコスト効率の良いコンパイル手法
首藤 一幸†

関口 智嗣†

村岡 洋一††

Cost-Eﬀective Compilation Techniques for Java Just-in-Time Compilers
Kazuyuki SHUDO† , Satoshi SEKIGUCHI† , and Yoichi MURAOKA††

あらまし Java Just-in-Time コンパイラには，生成コードの性能だけでなく，コンパイル時間の短さや Java
仮想マシン仕様への準拠といった相反する要求が課せられている．我々は，研究基盤として有用なものとすることを第 1 の目標として Just-in-Time コンパイラを開発してきた．コンパイル処理と開発のコストを抑えつつもベースラインコンパイラとして実用的な性能を達成した．本論文では，スタックキャッシュを応用したコード生
成手法，命令畳込み，シグナルを利用した例外の捕そく法，性能上のペナルティなしに Java の仕様を厳密に守るためのコード書換え手法など，当該コンパイラに実装した最適化手法を述べ，その有効性を示す．
キーワード 実行時コンパイル，Java 仮想マシン，スタックキャッシュ，命令畳込み，コード書換え

込み用途向けの処理系では，性能を多少犠牲にしても

1. ま え が き

メモリ消費量が少ないことを優先するかもしれない．

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

我々の場合は，次の方針に基づいて JIT コンパイラを開発してきた．

完了するコンパイラとは異なる様々な要求が課せられ（ 1 ） 研究基盤として利用しやすいものとする．

ている．単に生成するコードの質が良ければよいとい（ 2 ） 開発コストを抑える．

うものではなく，コンパイルによる性能上の利得がコ（ 3 ） 実用に耐える品質と性能を達成し，多くの利

ンパイルによって消費される時間やメモリ消費量に見用者を獲得する．

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

コンパイラの開発は，パーサ，中間表現の扱い，種々である．また，Java 言語や仮想マシン（JVM）の仕の最適化までかなりの労力を要する仕事である．その様 [1], [2] は実行結果の高い再現性をねらった厳しいもため，開発においては，性能に代表される技術的な要ので，その規定の一部は性能向上の妨げとなる．

求にとどまらず，開発に要する労力という人的，工学

相反する要求がある状況では，それぞれの要求に特的な要因もまた重要な指標となる．我々は，数人月程化した処理系の出現はごく自然なことであろう．例え度の労力で，研究基盤として扱いやすいソフトウェア

ば Sun 社の HotSpot Server VM がもつ JIT コンパを作成することを第 1 の目標とした．つまり，JIT コ

イラは，Hot であると認識され選択されたメソッドに

ンパイラ自体の開発コストを抑制しつつ，それを研究

ついてはコンパイル時間に糸目をつけない，高い性能に利用する際のコストも低く抑えることをねらった．

を得ることに特化した JIT コンパイラである．逆に組コンパイラが生成するコードのピーク性能を追求す
ると，開発コストは性能以上に高くなってしまうこと†

産業技術総合研究所，つくば市
National Institute of Advanced Industrial Science and Technology, Tsukuba Central 2, 1-1-1 Umezono, Tsukuba-shi,††が一般的である．そのため我々は，ピーク性能ではな
く，JIT コンパイラのもう一方の形態である，コンパ

305-8568 Japan

イル処理のコストを抑えたベースラインコンパイラを

早稲田大学理工学部，東京都開発するという方針をとった．

Waseda University, 3-4-1 Okubo, Shinjuku-ku, Tokyo, 1698555 Japan

本論文では，当該 JIT コンパイラ向けに開発，実
電子情報通信学会論文誌 D–I Vol. J86–D–I No. 4

pp. 217–231

2003 年 4 月

217電子情報通信学会論文誌 2003/4 Vol. J86–D–I No. 4

装してきたコスト効率の良いコード生成手法と最適

Java bytecode

化手法，及びその効果を報告する．コード生成手法とTranslation into shuJIT internal code

しては，あらかじめ用意したネイティブコード片をつshuJIT internal code

ないでいくというテンプレート方式を採用し，その上Optimization

で，複数レジスタを活用するためにスタックキャッシュ

shuJIT internal code

（stack caching） [3] を応用した．スタックトップの値

Replacement with native codeのみを常にレジスタに保持する JIT コンパイラ [4] や，
x86 native code

動的スタックキャッシュを採用した Java バイトコー
ドインタプリタ（Sun 社 Classic VM）はあるが，ス

図 1 shuJIT の全体構成
Fig. 1 Structure of shuJIT.

タックキャッシュ，つまり複数のキャッシュ状態を JIT
コンパイラに適用した例はない．この方式によって，開発コストとコンパイル処理のコストを低く抑えながらもテンプレートにまたがって複数のレジスタを利用

shuJIT
internal codeJava
bytecode

fill_cachearray_checklaloadできた．また，本コード生成方式は，2. で述べるように，開発者側で JIT コンパイラが生成するコードを直接的に改変できるため，研究の材料として利用しや
すい．

.....
daloaddmul
dadd
dastore.....

flush_cache
dld
dmul
dst
flush_cache
dld
dadd
dst

最適化としては，命令畳込み，インライン展開といったよく知られているものに加えて，生成コード間の直接呼出しやシグナルの利用，コード書換えといった処

Translation into
shuJIT internal code

fill_cachelastoreshuJIT
internal codex86
native code.....

fill_cachearray_checkdaload_dld
dmul
flush_cachedadd
dst_dastore

movl (%edx), %eax
fldl (%eax,%ecx,8)
addl $8, %esp
fmull (%esp).....
Replacementwith native code

Optimization(Part of Linpack#daxpy method)

理コストの低いものを実装し，本コンパイラのコード生成方式と組み合わせた場合の効果を調べた．
続く 2. では開発した JIT コンパイラの概要を述べ

Fig. 2図 2 コンパイルの例
An example of compilation.

る．コンパイラの構成や，また，採用したコード生成手法が開発コスト，研究基盤としての利用しやすさ，
コンパイル処理のコストに与える影響を論じる．3. でPC 以上の性能，メモリ容量を想定している．
本 JIT コンパイラの開発においては，研究基盤としは，より多くのレジスタを活用するために導入したスての利用しやすさだけでなく，日常の使用に耐える実タックキャッシュの得失を述べる．4. で，各最適化手用性や安定性，信頼性の達成を目標にすえた．また，法について，その性能上の効果を述べた後，5. でピー

JVM 仕様 [2] への厳密な準拠も指向してきた．これら

ク性能とアプリケーションの起動に要する時間というの要件は，研究目的のソフトウェアであっても，それ使用感を大きく左右する要因を評価し，6. でむすぶ．

を利用した派生研究の現実性，例えば評価結果がどの

2. JIT コンパイラの概要

くらい現実に則したものになっているか，を高くするために重要なものである．その結果，一定の利用者を

我々は，shuJIT という Java バイトコードの実行得ることに成功し [5]，1998 年 9 月の公開以来，2001

時（Just-in-Time）コンパイラを開発，配布してきた．

年 3 月までの 2 年半の間に，ソースコードは 7558 回，

Intel 社の IA-32，いわゆる x86 プロセッサを対象とし，OS として Linux と FreeBSD，NetBSD をサポー

バイナリーは 8476 回のダウンロードがあった．

トする．生成コードのテンプレートがアセンブリコー

メソッドを与えられると，まず，その Java バイトコー

ドで記述してある他は主に C 言語で記述されている．

ド命令列を shuJIT の内部命令に変換する．続いて，

Sun 社の Java 2 Platform, Standard Edition（Java2 SE）や Java Development Kit に含まれる Classic
VM という Java 仮想マシン（JVM）とともに動作する．対象が x86，Java 2 SE，Linux や FreeBSD，

得られた内部命令列に対して，4. で述べるいくつか

NetBSD であることに表れているように，shuJIT は218

コンパイラの構成を図 1 に示す．コンパイル対象のの最適化，具体的には，命令畳込み（4. 2），インライン展開（4. 5 及び 4. 6），直接呼出しへの変換（4. 1）を施す．最後に，内部命令列を x86 プロセッサのネイ
ティブコードに置き換える．図 2 に，Java バイトコー

論文／Java Just-in-Time コンパイラのためのコスト効率の良いコンパイル手法

ド命令からネイティブコードが得られるまでの変換例

い粒度の中間表現を経由してコード生成を行う．こうを示す．

いったコンパイラで生成コードを改変するためには，

本コンパイラの中間言語である shuJIT 内部命令は，中間表現の生成部を改変するといった直接的ではない

Java バイトコード命令に独自の命令を追加したもので方法をとらざるを得ない．更に，場合によっては，最ある．Java バイトコード命令からの変換処理は，1 対
1，または 1 対多の単純な置換えで済む．文脈によって，例えば strictfp [1], [6] であるか否かによって変適化によって生成したいコードが消えたり順序が崩れ

換結果が変わることはある．

方，本コード生成方式には，テンプレートが機種依存たりしないように配慮をする必要がある（ある種の最適化を止めたり，偽の依存関係を作っておくなど）．一最後のコード生成，つまり shuJIT 内部命令から x86

するため命令セットアーキテクチャ（ISA）ごとに用ネイティブコードへの変換は，内部命令をネイティブ意する必要があり，テンプレートに施した変更は特定

コードの断片，つまりテンプレートに置き換えていくの ISA でしか機能しないという難点がある．例えば本という方法で行う．テンプレートはあらかじめ JIT コ

コンパイラを SPARC プロセッサに移植し，x86 用テ

ンパイラ側で用意しておく．テンプレートとして記述

ンプレートに変更を加えた場合，その変更は x86 上でされるネイティブコードは，JVM のスタックを，x86しか機能しない．

プロセッサ自身のスタック操作機構，すなわち push，

pop 命令を用いてシミュレートする．
このコード生成方式は，次の効果をねらったものである．

• 開発コストの低減• JIT コンパイラが生成するコードの改変しやすさ• コンパイル処理のコスト抑制

本コンパイラが対象とする ISA は現在 x86 のみである．大きな労力を費やすことなく研究の材料を作成することが目標であったため（1. 参照），JIT コンパ
イラ自体の移植性よりも開発コストの抑制を優先した結果である．これをもし，他の ISA に移植しようとした場合，その ISA 向けにテンプレートを記述し直す必要がある．一方，機種非依存の中間表現をもとにコー
ド生成，アセンブルを行うという一般的なコンパイラ

このテンプレート方式によって，JIT コンパイラ内にの場合は，対象 ISA 向けのアセンブラの作成と，対象

アセンブラをもつ必要がなくなり，その分の開発コス

ISA 向けのパラメータ（レジスタ数など）調整などがトを抑えることができた．アセンブラが不要であるの必要となろう．どちらの手間が大きいかは場合による

は，JIT コンパイラ自体を C コンパイラでコンパイル

が，本コンパイラのテンプレート方式の方が，コンパする際に，テンプレートもアセンブルしておくことがイラ中で異機種間で共通して使えるコードの割合は低できるからである．x86 は命令のビットパターンがいいことは確かであろう．

わゆる RISC プロセッサとは違って規則的ではないため，アセンブラの開発コストが比較的高い．

テンプレート方式では，コード生成処理のコストが低いことも期待できる．もとのバイトコード命令列のコンパイラの実装は 1 人で行い，開発開始から 48

長さに比例した時間で行える．本コンパイラの開発

日後には簡単なプログラムを動作させるに至った．他

にあたっては，ベースラインコンパイラとしての価値のソフトウェアとの間で開発コストを比較することはを損なわないようにコンパイル処理を軽く保つため，困難であるが，JIT コンパイラとしてはかなり低い開コード長 n として計算量 O(n) を超える処理は行わ

発コストであろう．

ないようにした．

このコード生成方式では，テンプレートに記述されたネイティブコードの列が JIT の生成コード中にその

3. スタックキャッシュ

まま現れるため，テンプレートに変更を加えて JIT コ

テンプレートを用いたコード生成方式の大きな問題

ンパイラ自体を C コンパイラで再コンパイルするこ

は，レジスタ割付けを行いにくいことである．近年のとで，生成されるコードを直接的に改変できる．そのプロセッサでは，レジスタの有効活用が高性能達成の結果，生成コードの改変が必要な研究の材料として利かぎとなっているが，テンプレート方式では，テンプ用しやすいものとなり，各種研究の基盤として利用さレートをまたいで複数のレジスタを活用することが困れるに至った [7]〜[9]．これに対して，多くのコンパイ難である．現に，本コンパイラと同様にテンプレート

ラは RTL といったプロセッサ命令に近い，より細か方式を採っている JIT コンパイラ TYA [4] では，テン219電子情報通信学会論文誌 2003/4 Vol. J86–D–I No. 4

動的スタックキャッシュはインタプリタによく用いshuJIT
memorymemorymemory.....
state 0EDX
memorymemory.....
state 1ECX
EDX
memory.....
state 2EDX
ECX
memory.....
state 4ECX
memorymemory.....
state 3の 3 状態という実装例がある．しかし，スタックキャッ
シュを Java JIT コンパイラに適用した例はない．
本コンパイラのコード生成手法に関連する手法として，lazy code selection [10] がある．両手法の共通点

TYA (a JIT compiler for x86)
top

られ，JVM でも，Sun 社 Classic VM のインタプリタ

EAXmemory.....

は，Java バイトコード命令を対応するネイティブコー

stack

ドに直接的に置き換えるというコード生成方法であり，
register

これによってコンパイル処理を軽く保とうとしている点である．lazy code selection では，コード生成中，

図 3 キャッシュ状態
Fig. 3 Cache states.

三つのスクラッチレジスタで JVM のスタックのどの位置の値をキャッシュしているかを mimic stack を使って追跡する．mimic stack は JVM スタックをシミュ

shuJIT internal code
(part of Linpack#daxpy method) :...
(1) iload(2) iloadstate 0(3) iconst_1(1) iload(4) isub(5) iload(9) fill_cache(6) iconst_1(8) iastore1(7) isub(8) iastore1(11) iastore
state 3state 1(9) fill_cache(10) array_check(11) iastore(7) isub(5) iload(2) iload...
(4) isub(6) iconst_1(10) array_checkstate 2state 4

レートし，スタック上の要素がどこ（レジスタ，メモリ）に置かれているのかという情報を保持する．これは，本コンパイラがスタック状態を追跡することと類似している．また，lazy code selection では RISC と比較して多様である x86 のアドレッシングモードを利用して，レジスタへのロード命令と演算命令を 1 命令に畳込むことを試みる．本コンパイラでは，この畳込
みはテンプレートを記述する時点で人間が行う．両手法の違いは，lazy code selection が局所変数へのレジスタ割付けを行う点や，スタックのキャッシュに用い(3) iconst_1

るレジスタ数である．これらの違いによって，生成さ(1) Emit the native code for "iload in state 0".
(2) Emit the native code for "iload in state 1".
(3) Emit the native code for "iconst_1 in state 2".
(4) Emit the native code for "isub in state 4".
.....

れるコードの質は lazy code selection の方がよいと予

Code generation process :想できる．また，mimic stack を操作してアセンブルを行う lazy code selection よりも，状態番号に対応したコードを選ぶだけの本手法の方が，より処理が軽く

図 4 状態遷移の例
Fig. 4 An example of state transition.

開発コストが低いと予想する．
スタックキャッシュを用いたコード生成と単純なテンプレート方式の双方を実装している JIT コンパイラ

プレートをまたいでレジスタに保持できるのはスタッがないため，スタックキャッシュの効果を正確に測定す

クトップの値のみである（図 3）．

ることはできない．しかし少なくとも，SPEC JVM98

この問題を緩和するため，スタックキャッシュ（Stack
Caching）[3] を採用した．JVM のスタックは基本的にの全ベンチマークにおいて本コンパイラのスコアは

は主記憶上に設けるが，スタックトップ付近はレジス

コンパイラと同様にテンプレート方式を採用しておTYA のものを上回っている（5. 1 参照）．TYA は本タを用いてキャッシュする．図 3 のとおり，キャッシュ

り，JIT 生成コードの実行中は常に EAX レジスタでに用いるレジスタ数は 2 とし，スタックトップ付近をスタックトップの値のみをキャッシュする（図 3）．

どのレジスタでキャッシュしているのかというキャッスタックキャッシュの導入によって性能向上が期待

シュ状態を 5 通り定義した．それぞれの shuJIT 内部

できる反面，JIT コンパイラの開発コストは増加する．

命令について，5 状態に応じたテンプレート，すなわ

状態数に応じたテンプレートを用意しなければならな

ちネイティブコード片を用意しておき，各テンプレー

いためである．しかし，本コンパイラのようにキャットの実行終了時の状態に応じて，次のテンプレートをシュ状態を 5 通り定義したからといって，テンプレー

選んでいく（図 4）．

ト記述の手間は 5 倍までは増えない．各状態に対応

220

論文／Java Just-in-Time コンパイラのためのコスト効率の良いコンパイル手法

0

20

40

without direct invocation(Section 4.1)

60

80

100

%
_227_mtrt_202_jesswithout instruction
folding (Section 4.2)

_201_compress_209_db

without signal utilization(Section 4.3)

_222_mpegaudio

without folding andsignal (Section 4.2 and
4.3)_228_jack_213_javac

without general inlining(Section 4.5)

Geometric Mean

without alignment ofbranch target(Section 4.7)

Fig. 5図 5 各最適化の SPEC JVM98 への影響
The impacts of each optimization on SPEC JVM98 scores.

するテンプレートは，レジスタ名が変わるくらいで，という場合がある．例えば，シグナルの利用は JVM

処理内容はほぼ同じだからである．それでも，テンプ仕様を遵守するために有効であるし，命令畳込みはレートのコード量，ひいては JIT コンパイラ自体のJVM がスタックマシンだからこそ，テンプレートをディスク占有量，メモリ占有量が増加することは避け用いたコード生成方式に適用すると効果が高い．逆に，られない．とはいえ，本コンパイラのテンプレートは，

インライン展開のように，テンプレート方式ではそのアセンブル後のオブジェクトファイルの状態でたかだ

効果が最大限には発揮されない最適化手法もある．

か 30KByte 弱であり，PC 上で問題となるサイズではない．
スタックキャッシュによって，テンプレートを用い

本章では，本コンパイラに実装した各最適化手法について，その効果や，コード生成方式との関係，JVM仕様との関係，メモリ消費量への影響を論じる．

るコード生成でも，テンプレートをまたいで複数のレ各最適化が SPEC JVM98 のスコアに与える影響を

ジスタを活用することが可能となった．2 とは決して

図 5 に示す．これは，すべての最適化を施した場合の多い数ではないが，x86 はもともと汎用レジスタを 8

スコアを 100%として，ある最適化を行わなかった場

しかもたない上，スタックポインタとベースポインタ

合のスコアをそれぞれのベンチマークについて示したもこの汎用レジスタに含まれている．その他の 4 レジものである．値が小さいほど，その最適化を外した場

スタも，一つは JVM の局所変数のベースアドレスを合のスコア低下が大きいことを示す．つまり，最適化

キャッシュする目的に利用しており，残り 3 レジスタの効果が大きいということになる．

もテンプレートの中では活用している．

4. 最適化手法
本コンパイラは，命令畳込み，末尾再帰除去，イン

4. 1 生成コード間の直接呼出し
一つの JVM 内には，インタプリタで実行されるバ
イトコードのままのメソッド，C，C++言語で記述さライン展開といったよく知られた最適化に加えて，生れたネイティブメソッド，既に JIT コンパイラによっ

成コード間の直接呼出し，OS のシグナルの利用，コーてコンパイルされたメソッドなど，多種類のメソッド

ド書換えといった処理コストの低い最適化手法をいくが混在する．これら異なる種類のメソッドが相互に呼つか実装している．すべての処理はコード長 n として

び出し合えるようにするためには，共通の呼出し イ

最大でも計算量 O(n) である．

ンタフェース，すなわち引き数と返り値についての型

よく知られた手法であっても，適用対象が JVM での並びを規定するという方法が一般的である（図 6）．

あるために特に有効であったり，または，本コンパイ

このインタフェースは，本コンパイラが対象とする

ラのコード生成方式を前提として高い効果を発揮する

Classic VM では次のように定められている．
221

電子情報通信学会論文誌 2003/4 Vol. J86–D–I No. 4

Common invocation interfaceof Sun’s Classic VM
invoke
JITCompiled
Method ()Direct invocation
Native code

generated by shuJIT

invocation
Helper ()(provided by shuJIT)(provided by shuJIT)

invoke(JNI)Native
Method ()Commoninvocation interface

直接呼び出すためには，callee を確実にコンパイルできることの確証が必要である．コンパイルの失敗は，メモリの確保失敗など不測の理由によって起こるので，確証を得るためには実際にコンパイルを済ませる必要がある．

A native method......

(provided by Sun’s Classic VM)

そこで本コンパイラは，callee が static，private ま
たは ﬁnal メソッドであり，caller のコンパイル時点で未コンパイルであった場合には，eager に，その時点

Fig. 6図 6 直接呼出し
Direct invocation between compiled methods.

bool_t 関数名(JHandle *o, struct methodblock *mb,
int args_size, ExecEnv *ee)
図 6 中の invokeJITCompiledMethod() は本コン

でコンパイルしてしまう．これによってコンパイルの成否を確認でき，判別処理を省略できるか否かを判断できるのである．
しかし，この方法では，呼び出されないメソッドまで eager にコンパイルしてしまう可能性があり，メモリとコンパイル時間が無駄に費やされるおそれがある．
このように得失の双方があるため，本コンパイラ自体パイラ側で用意している関数であり，JIT コンパイラがを C コンパイラでコンパイルする際に，この最適化を生成したコードを呼び出すいわゆるラッパ（wrapper）

行うか否かを選択できるようにしてある．また，eager

である．JIT 生成コードと他種のメソッドでは，スタッなコンパイルを避けつつ判別処理を省くことができる

クのメモリ上の位置及び成長方向が異なるため，引き別の手法もある．すなわち，callee は呼び出された時数の積換えを行うために同関数を用意している．

点で必要に応じてコンパイルし，コンパイル成功を確

しかし，JIT 生成コード同士の呼出しでは，共通呼認できた時点で caller の JIT 生成コードを書き換えて出しインタフェースを介す必要も，スタックを積み換最適化するのである．判別処理をスキップするようにえる必要もない．ラッパの呼出しを省けば，関数呼出

コードを書き換え，callee のアドレスを書き込むのでしとスタックの積換えのコストを削減できる．そこで，ある．ただ，この方法では，caller 中には常に判別処

JIT 生成コード同士は，ラッパを介さずに直接呼び出理のためのコードが生成され，これを省略することはすという最適化を施した．

できない．つまり，eager なコンパイルによる余計なそれでも依然として，呼出し対象が JIT 生成コード

メモリ消費を抑えられる一方，若干，caller の JIT 生

かそれ以外の種類のメソッドかを実行時に判別する必

成コードが大きくなる．

要はある．動的束縛では，callee が JIT 生成コードか否かをコンパイル時に判別できるとは限らないからで

こ れ ら の 最 適 化 の 結 果 ，CaﬀeineMark 3.0 のMethod ベンチマークのスコアが 1780 から 7652 に，ある．例えば，JIT コンパイルされたメソッドがネイ

つまり約 4.3 倍に向上した．また，図 5 に示すとおり，

ティブメソッドでオーバライドされることもあるので，この判別処理は条件分岐を必要とし，実行時のオーSPEC JVM98 のスコアへの影響も非常に大きい．この最適化によって，総合スコアは 1.7 倍，最も影響の小さい 213 javac で 1.1 倍，最も影響の大きい 227 mtrtに至っては 2.9 倍となっている．これらの結果から，バヘッドを伴う．そこで，判別を削減するというもうSPEC JVM98 のスコア，特に 227 mtrt に対してメ一つの最適化を施した．callee が static，private また

ソッド呼出しの効率が非常に大きく影響することがわ

は ﬁnal メソッドである場合には，上述の判別処理をかる．

実行時のこの判別処理は避けられない．本コンパイラ
はこの判別を行うネイティブコードを生成する．

省くのである．

4. 2 命令畳込みとはいえ，JIT コンパイルは必ず成功するとは限命令畳込み（instruction folding）は，複数の命令をらない．JIT コンパイルできなかったメソッドは，イ同等なより少ない命令群に置き換えることで，命令数

ンタプリタで実行せざるを得ない．caller に対してこや処理コストを低減する最適化である．スタック操作のこで述べた最適化を施す，つまり，callee が JIT 生成

ために命令数が増えがちであるスタックマシンにおい

コードか否かを判別することなく，ラッパを介さずにて効果が高いことが知られている [11]．picoJava [12]222

論文／Java Just-in-Time コンパイラのためのコスト効率の良いコンパイル手法

を代表として，Java プロセッサへの実装例や検討例が特に高く，この最適化によってスコアが 1.16 倍に向上

多い [13]．本コンパイラは，JVM 上のスタック操作をしている（図 5）．同様に浮動小数点演算の多い Linpack ベンチマークでその効果を調べた．問題サイズ
は 500 × 500 である．

x86 のスタック操作に置き換えるというコード生成を行うため（2. 参照），スタックマシンと同様に命令畳込みの効果が期待できる．
例えば，Java コンパイラは，JVM のスタックトッ
プを局所変数にコピーする場合，局所変数に対する畳込みなし

14.042 Mﬂops

畳込みあり

19.083 Mﬂops

ポップ命令と局所変数からのプッシュ命令を続けて生命令畳み込みによって 1.36 倍と大きく向上している．

成する．32 ビット整数であれば istore，iload とい

もし，スタックキャッシュで整数レジスタだけでなう命令列である．この命令列をそのままコンパイル

く浮動小数点レジスタでもキャッシュできたとすると，すると，ポップとプッシュという 2 度のメモリ操作を

本コンパイラが実装している上述の畳込み ( 1 )∼( 4 )行ってしまう．これを，局所変数へのコピー命令に置のうち，( 2 )，( 3 )，( 4 ) は不要となる．しかしそのたき換えるのである．

めには，スタック状態の数を増やしたり，整数，浮動本コンパイラは，内部命令列の上で，メモリアクセ

小数点数の双方に用いられる型汎用のバイトコード命ス，すなわち整数及び浮動小数点数のレジスタ–メモ

令（pop，pop2，dup，dup2 など）に対して生成する

リ間コピーの削減を目的とした命令畳込みを行う．そネイティブコードを適切に選ぶためにスタックに積まのために，次に示す命令列を検出して，（）内の無駄なれている要素の型を追跡する必要が生じる．

コピーを削減する．
（）内のコピー処理を行わないよう4. 3 シグナルを利用した例外の捕そくな別種の内部命令に置き換えるのである．

OS のシグナルを利用した例外の検出は，Java のイ（ 1 ） スタック → 局所変数（→ スタック）

ンタプリタや JIT コンパイラでよく用いられる手法で（ 2 ） 浮動小数点レジスタ（→ スタック）→ 局所

ある．条件分岐なしにある種の例外を検出できるため，

変数または配列

例外が発生しない場合，つまり正常系のオーバヘッド（ 3 ） 局所変数または配列（→ スタック）→ 浮動をゼロにできる．

小数点レジスタ

具体的には，次の例外検出にシグナルを利用する．

（ 4 ） 浮動小数点レジスタ（→ スタック）→ 浮動• SIGSEGV で NullPointerException を検出．
• SIGFPE で ArithmeticException を検出．

小数点レジスタ
具体的には，例えば istore，iload という命令列を等価な内部命令 istld に置換する．この istld は，ス
タックトップから局所変数へのコピーだけを行う内部命令である．この畳込みは上記（1）の例である．
ここでいう局所変数とは Java 言語，JVM の局所変数であり，本コンパイラはこれをメモリ上に配置する．

• SIGSEGV で StackOverflowError を検出．
NullPointerException と ArithmeticExceptionの検出は多くの Java バイトコード処理系において一般的であるが，本コンパイラは StackOverflowError，すなわちスタックあふれの検出にもシグナルを活用する．

同様にスタックとは JVM のスタックであり，基本的Java 言語の null は Classic VM 中ではアドレスにはメモリ上にあるが，3. で述べたとおり，スタック0 で表現されているため，それをオブジェクトとしてアクセスするとメモリ保護違反によって SIGSEGV

トップ付近は整数レジスタでキャッシュされる．
このように，整数レジスタは 3. で述べたスタックが 発 生す る ．こ の シ グ ナ ル を シ グ ナ ル ハン ド ラ でキャッシュによって活用されるが，浮動小数点レジス

とらえることで，NullPointerException を検出でタの効率的な利用は考えられていない．それを補い，きる．また，整数のゼロ除算では SIGFPE が発生し，ArithmeticException を検出できる．

浮動小数点数の無駄なコピーを削減することが，本コンパイラにおける命令畳込みの大きな目的である．命スタックあふれを検出するためには，メソッド呼出令畳込みはよく知られた最適化手法ではあるが，そのしの直前にわざとスタックの成長方向の少し先，数百

効果と位置付けは本コンパイラ独特のものである．

から数千番地先をアクセスする．もしアクセス先が有現に，SPEC JVM98 のベンチマーク群のうち，浮効なアドレスでなければ SIGSEGV が発生する．どの

動小数点演算の多い 222 mpegaudio に対する効果が程度先をアクセスするかは，OS や libc の種類といっ223

電子情報通信学会論文誌 2003/4 Vol. J86–D–I No. 4

た環境に依存する．シグナルハンドラと例外発生処理

void signal_handler(int sig, ...) {struct sigcontext *sc = ...

を行うために充分なマージンをとっておく必要があり，

シグナルコンテクストを取得;必要なマージンは環境によるからである．

switch (sig) {シグナルの利用によって例外検出のオーバヘッドをシグナルの種類に応じた処理なくすことができる反面，例外が発生した場合の処理(例外の throw など);

コストは一般に増加する．条件分岐を用いた検出より}も，シグナルの発生及び捕そくの方が重い処理だから

シグナルコンテクスト中のプログラムカウンタを書き換える;である．このため，上記の例外が頻繁に発生するプログラムでは，この最適化によって性能が低下すること

return;}もあり得る．
例外発生の頻度はプログラムによって様々であるた

Fig. 7図 7 シグナルハンドラの処理
Signal handling for catching an exception.

め，この最適化の効果はプログラムの性質に依存する．
しかし，例外は例外的な状況でのみ使用するという方
針がプログラミングの良い方法だとみなされており，

sigcontext 型）を取得する．続いて，シグナルの種

これに従っているプログラムでは例外発生の頻度は高類とコンテクストに基づいて発生した例外の種類を判くないことが期待できる．実際に，図 5 に示したとお定し，その例外を throw する．最後に，シグナルハン

り，SPEC JVM98 のスコアは向上している．

ドラから戻った後で適当な catch 節や return から実では，例外発生の頻度がどの程度であれば性能は向行が続くように，コンテクスト中のプログラムカウン

上，あるいは低下するのか．これを見積もるために，タの値を書き換えて，シグナルハンドラを抜ける．

シグナルの利用による正常系のコスト削減量と例外発

4. 4 コード書換え

生時のコスト増加量を測定し，比較した．オブジェク

Java 言語の仕様 [1] では，クラスが初期化されるタトへの参照からインスタンス変数を読み出すというイミング，つまり static ブロックの実行と static 変数

NullPointerException を発生し得る処理を繰り返す
プログラムを用いて，参照が null の場合（例外発生）と非 null の場合（正常系），それぞれの場合についの初期化が行われるタイミングが厳密に定められてい変数へのアクセスと static メソッドの呼出しがクラスて，シグナルの利用による実行時間の増減を測った．

の初期化を引き起こすことがある．例えば，初期化さ1.7 GHz Pentium 4 では，正常系の実行時間が 10
億回当り 136 ミリ秒短縮され，逆に例外発生時の実行
時間は 100 万回当り 12302 ミリ秒延びた．600 MHz
Pentium III では，正常系の実行時間が 1 億回当りる．JIT コンパイラにとって都合の悪いことに，static

れていないクラスの static 変数を読み出そうとした場
合，その時点で初めてそのクラスを初期化しなければならない．
かといって，このために素朴に条件分岐を用いたの

334 ミリ秒短縮，例外発生時の実行時間は 10 万回当り 1521 ミリ秒延びた．繰返し 1 回当りで計算すると，ごとに条件分岐のオーバヘッドを被るはめになる．あ正常系の実行時間減少に対する例外発生時の実行時間

るコードの 2 度目以降の実行では，初期化は確実に済増加の比は次のとおりである．

んでいるためこの条件分岐は不要であり，極力避けた

1.7 GHz Pentium 490500 倍
600 MHz Pentium III 4600 倍

では，static 変数アクセスと static メソッドの呼出し

い．実際には，JIT コンパイルの時点で初期化済みのクラスについては初期化済みか否かの判定コードを生成する必要がないため，これだけで多くの条件分岐をつ ま り，イ ン ス タ ン ス 変 数 ア ク セ ス と いった省ける．しかし，JIT コンパイル時には未初期化だっ

NullPointerException を発生し得る処理において，たクラスについても，条件分岐のオーバヘッドは極力

Pentium 4 であれば，例外発生の頻度が約 9 万回に 1小さくしたい．

度より低ければこの最適化が有効である，と見積もることができる．

2 度目以降の実行では無駄な条件分岐を避ける方法
として，初めての呼出し時はインタプリタで実行してシグナルハンドラ中で行う処理を図 7 に示す．まおき，2 度目に呼び出された時点で初めて JIT コンパ

ず，例外が発生したスレッドのコンテクスト（struct

イルを行うという方法がある．例えば，Borland 社の224

論文／Java Just-in-Time コンパイラのためのコスト効率の良いコンパイル手法

Native code generated by shuJIT :......
Executed
NOP
only once
NOP
Code which has to be executed only once
Replace the above "NOP"s with "JMP done"
done:......

After executed once :Skip the code
executed once......
JMP done
Code which has to be executed only once
Replaced the above "NOP"s with "JMP done"
done:......

図 8 NOP 命令をジャンプ命令で上書きする方法
Fig. 8 Overwriting a jump instruction onto a NOP
instruction.

Control flow

Write "INT 3"
on the native code
generated by shuJIT.

......
INT 3......

Native code
generatd by shuJIT

Signal handler :void signal_handler(...) {Do the operation which have to
be executed only once; (*)
Write back the originallygenerated code on "INT 3";
Modify the program counterin obtained signal context;}(*) In reality, the signal handler do not execute the required operation by itself.
Instead the signal handler generates a trampoline code which jumps tothe operation and set the address of the trampoline into the obtained signal context.
Hence the operation is executed after the signal handler returns.
If the signal handler executes the operation by itself, more signals can occur
in the operation even though the signal handler has already been running.

図 9 ソフトウェア割込み命令を本来の命令で上書きする
方法
Fig. 9 Overwriting the original instruction onto an
instruction to cause software interruption.

に用意されている唯一の 1 バイト命令 INT 3（0xCC）

JBuilder Java 2 JIT がこの方法をとっている．しかを用いた．JVM がマルチプロセッサで実行されるこ

しこの方法では，初めて呼び出されたメソッドの実行とを考慮すると，コード書換えは atomic に行う必要

が長時間続いた場合，性能に劣るインタプリタで実行がある．atomicity の保証には最悪の場合メモリバスが続けられてしまう．この問題を回避するため，IBMのロックが必要であり，処理が複雑になると同時に性社の Java 2 SE や Sun 社の HotSpot VM は，いった

能上のペナルティもある．atomicity を気にせずに済んインタプリタで実行を始めたメソッドであっても，

むように，1 バイト命令を利用した．
本コンパイラに実装されたジャンプ命令法は，2 バイ

JIT コンパイル結果に実行を移す機構を備えている．
本 JIT コンパイラは，これらとはまた異なる方法で問トの書換えを行う．2 バイトを atomic に書き換えるた

題を回避している．

めには，通常の MOV 命令ではなく，ORP [14] と同様

4. 4. 1 shuJIT の方法に XCHG 命令を用いている．これによって atomicity

shuJIT は，コード書換えを利用して，上述の問題をが保証される [15]．ジャンプ命令法を 1 バイトの書換被ることなく，Java 言語と JVM の仕様を完全に遵守

えで実装することも可能ではある．ジャンプ命令のしている．すなわち，1 度実行した JIT 生成コードを，

ジャンプ先のみを書き換えればよい．

2 度とは実行しないようにコードを書き換えるのであどちらの方法にもそれぞれの利点がある．ジャンプ

る．これによって，初めての呼出しの時点でメソッド

命令法では，2 度目以降の実行でも毎回（無条件）ジャをコンパイルしても，条件分岐によるペナルティを被ンプ命令は実行せざるを得ないが，割込み命令法では，ることなく，Java の仕様を守ることができる．処理の2 度目以降は完全に無駄のないコードになるので，数軽いベースラインコンパイラを指向する本コンパイラ

度目以降の実行ではペナルティは皆無となる．一方，にとって，初回の呼出し時に問題なくコンパイルを行

メモリ消費の少なさでどちらが勝るかは実装方法によえることは重要な要件である．ゆえに，コード書換え

る．ジャンプ命令法では生成コード中に初回のみの処は本コンパイラ向きの手法である．

理が何度もコピーされてしまうため，生成コードだけ

コード書換えの方法としては以下の 2 通りが実装さを見ると割込み命令法が勝る．しかし，割込み命令法

れており，JIT コンパイラ自体を C コンパイラでコン

では，上書きする本来の命令を JIT コンパイルの時点パイルする時点で選択できる．

でどこかに保存しておく必要があり，そのための表が• 図 8： 無操作命令（NOP）をジャンプ命令で上書きする方法（ジャンプ命令法）• 図 9： ソフトウェア割込み命令（INT）を本来消費するメモリも考慮しなければならない．最終的にどちらが勝るかは，実装方法やアプリケーションプロ
グラムに依存する．

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

4. 4. 2 考えられる他の方法

ソフトウェア割込み命令としては，デバッガの実装用

本コンパイラに実装されているのは上述の 2 通り
225

電子情報通信学会論文誌 2003/4 Vol. J86–D–I No. 4

Overwritten instruction

Overwriting instruction

Jump instruction (JMP)

Jump instruction (JMP)

まうと，そのコード自体がキャッシュからあふれたり，
他のコードをキャッシュから追い出すなど，性能低下

No operation
instructions (NOP)No operation
instructions (NOP)

Software interrupt
instruction (INT)

Original instructions
shuJIT’s methodsの原因ともなり得る．20，2 というパラメータは，インライン展開の効果が大きいアクセサ（getter，setterメソッド）が展開されることを目標として決めた経験的な値である．
ジャンプ命令や catch 節を含むメソッドをインライ

Useful methods

ン展開しないという方針は，これを行うとジャンプ先

Implementable but useless methodsの解決処理が煩雑になり，コンパイル処理が重くなる
ことが予想されるためである．Sun 社の ExactVM も

図 10 コード書換えを行う種々の方法
Fig. 10 Various implementation methods for code
patching.

同じ方針を採用しており [16]，また，経験則どおり多くのアクセサが分岐や catch 節を含まないならば不利
益は小さい．
図 5 のとおり，SPEC JVM98 に対するこのインラの方法であるが，コード書換えの方法はほかにも考え

イン展開の効果は 228 jack にて 3%，総合スコアではられる．書換え前の命令と書換え後の命令の組合せに1%と決して高くはない．適用対象を non-virtual な呼よって，図 10 に示す数通りの方法があり得る．本来の出しに限定していることに加えて，テンプレートを用命令で上書きする方法には，数度目以降の実行でペナいたコード生成に原因があると考えている．本コンパ

ルティが皆無になるという利点があり，無操作またはイラのコード生成方式（2. 参照）では，インライン

ジャンプ命令で上書きする方法には，本来の命令を保展開によって呼出しコストは削減されても，メソッド存しておくためのメモリが必要ないという利点がある．

間最適化の機会拡大にはつながらない．そもそもそう

4. 5 インライン展開
インライン展開は，メソッド呼出しコストの削減と，手続き間解析及び最適化の適用範囲拡大につながる，
よく知られた最適化手法である．

いった最適化を行わないからである．

4. 6 特定メソッドのインライン展開
上で述べた一般のインライン展開に加えて，特定のメソッドを特別扱いしてあらかじめ用意したネイティ

本コンパイラは，callee をコンパイル時に特定できブコードに展開するというインライン展開を試みた．

る場合，つまり，対象が static，private または ﬁnal

本コンパイラへの実装は非常に容易である．特定メメソッドである呼出しについて，ある条件が満たされソッドに対応する shuJIT 内部命令とテンプレートをていればインライン展開を行う．より具体的には，バ

用意し，Java バイトコード命令を内部命令に変換する

イトコード命令 invokespecial と invokestatic で際に当該内部命令に変換すれば済む．

の non-virtual な呼出しや，invokevirtual での ﬁnal

浮動小数点演算のために用意されているメソッドの呼出しについて，次の条件が満たされていjava.lang.Math クラスに着目し，Math クラスがもれば展開を行う．

つメソッド群の浮動小数点演算命令への置換えを試み• ジャンプ命令を含まない• catch 節を含まない• 長さが shuJIT 内部命令で 20 以下• caller と callee の双方とも strictfp [1], [6] ではないか，または，双方とも strictfp である
あるメソッドに対して展開処理を 2 回施すので，展開されたメソッド中の呼出しが展開されるというインラ
イン展開のネストは 2 重までである．
上述の 20，2 という値はどの程度インライン展開を行うかというパラメータであり，実行時に環境変数として指定できる．インライン展開は，過度に施してし226

た．対象は次のメソッドである．

sqrt, sin, cos, tan, atan2, atan, log,
floor, ceil
展開によってセマンティクス，つまり演算結果が変わってしまうことを確認できているメソッド，例えば exp
については，展開を行わない．
この展開を行うことで，次の二つの理由で性能向上が得られる．

• ソフトウェアの数値演算ライブラリ fdlibm ではなく，浮動小数点演算命令が使われる．

論文／Java Just-in-Time コンパイラのためのコスト効率の良いコンパイル手法
表 1 sqrt の呼出し 10,000,000 回に要した時間
Table 1 Execution times to invoke the sqrt method
10,000,000 times.
Pentium 4
Pentium III

展開なし
15535
34959

展開あり 高速化率
851
18.3 倍1567
22.3 倍（ミリ秒）• ネイティブメソッドの呼出しが行われなくなる．
Java 2 には，全く同じメソッド群をもった二つのク
ラス java.lang.Math と java.lang.StrictMath が用意されている．StrictMath の仕様は，どんな環境でも Freely Distributable Math Library（fdlibm）と

表 2 sin の呼出し 10,000,000 回に要した時間
Table 2 Execution times to invoke the sin method
10,000,000 times.
Pentium 4
Pentium III

展開なし
4242
8021

展開あり 高速化率
1567
2.71 倍2226
3.60 倍（ミリ秒）

1.7 GHz Pentium 4 と 600 MHz Pentium III での結果を表 1 と表 2 に示す．sin でも 3 倍前後，sqrt に至っては 20 倍前後という大きな効果が得られている．
とはいえ，この種の最適化はその特定のメソッドを頻繁に呼び出すプログラムに対してのみ有効である．例

いうソフトウェアと全く同じ結果を返すというものでえば SPEC JVM98 では効果は全く期待できず，このあり，本論文で実験に用いている Sun 社，IBM 社の最適化を行わずともスコアの有意な低下は見られな

Java 2 SE は StrictMath のメソッド群を実装するた

かった．しかしそれでも，特定の場合にはその効果はめに fdlibm を用いている．一方，Math クラスのメ

非常に大きい．

ソッド群では，複数の環境で厳密に同じ結果を返すこ

この最適化処理はコンパイラに埋め込まれているとが要求されていない．そのため，環境に応じた方法

ため，実装が容易とはいえ，対応メソッドを増やすた

で計算を行って fdlibm を使うよりも高い性能を得る

めにはコンパイラ自体に手を加えなければならない．

余地がある．しかし，Sun 社，IBM 社の Java 2 SE

ソフトウェアのよい設計という観点からは，本来は，のクラスライブラリは，shuJIT が対象とする Classic

OpenJIT 2 の Compilet 構想 [17] のように最適化処

VM も含めて，Math クラスであっても StrictMath と同様に fdlibm を呼び出すことで演算を行うように実装されている．そのため，JIT コンパイラが Math ク

理をコンポーネントとして JIT コンパイラに対してプラスを特別扱いしない限りは，どんなにインライン展

本コンパイラはループの先頭をメモリの 16 バイト境

ラグインできる構造が望ましい．

4. 7 ループ先頭の整列

開しようとも演算には fdlibm が使われてしまう．性界に整列する．Pentium Pro，Pentium II，Pentium

能に勝る浮動小数点演算命令が使われることは期待でコンパイラが Math クラスを特別扱いすることが必須

III プロセッサは命令を 16 バイトずつフェッチするので，分岐先を 16 バイト境界に整列することで，デコーダの能力を最大限に活用できる．もっとも，Pentium
4 プロセッサでは，1 次命令キャッシュは，x86 命令かなのである．

ら変換された後のマイクロオペレーション（µop）をきないのである．Math クラスによる浮動小数点演算をハードウェアで行うためには，本手法のように，JIT

本手法によって性能向上が期待されるもう一つの理保持する方式となったため，この 1 次キャッシュから

由は，ネイティブメソッドの呼出しを減らせることで命令を取得できる限りは分岐先が整列されているか否ある．Java 2 SE では，sqrt など Math クラスのメ

かは性能に影響しない．分岐先を整列することの重要ソッドを呼び出すと JNI に準拠したネイティブメソッ

性は Pentium III 以前より下がった．

ドが呼び出される（以下，JNI 呼出しと呼ぶ）. JNI 呼この最適化によって，必ずしも性能が向上するとは出しは JVM の種類によらず重い処理であることが知限らない．整列によって命令列にすき間ができる．こられている．これには，引き数のスタック上レイアウのすき間は無操作命令（NOP）で埋めるか，長さが一トを JNI 規約に合わせるためのスタックへの積直しが定以上であればジャンプ命令でスキップするようにし避けられない，といった原因がある．Math クラスのている．無操作命令やジャンプ命令にはわずかなオー

メソッドを単にインライン展開しても JNI 呼出しは避バヘッドがあり，整列による利得の方が必ず大きいとけられない．そこで，本手法のように特別扱いして置は限らない．また，生成コード量も増加するため，命換することで JNI 呼出しまで削減できるのである．

令キャッシュの活用に悪い影響を及ぼし得る．とはいsqrt と sin に つ い て 性 能 上 の 効 果 を 調 べ た ．

え，この最適化によって，SPEC JVM98 の総合スコ
227電子情報通信学会論文誌 2003/4 Vol. J86–D–I No. 4

180

HotSpot Server VM
IBM JDK 1.3.0
HotSpot Client VM
OpenJITshuJIT
TYA
sunwjit.sointerpreter

SPEC JVM98

160

1.7 GHz Pentium 4

140
120
100
80
60
40
20
0

_227_mtrt _202_jess_201_
compress_209_db_222__228_jack _213_javac Geometricmpegaudio
Mean

図 11 SPEC JVM98 の結果
Fig. 11 The result of SPEC JVM98.

0

アはわずかに向上している（図 5）．

5. 性 能 評 価
以下では，PC 用の他の JIT コンパイラとの間でIBM JDK 1.3.0

5. 1 ピーク性能
本コンパイラを含めた種々の JIT コンパイラのOpenJITORP (O3 JIT)
ORP (O1 JIT)
shuJIT
Kaffe

測した．結果を図 11 と図 12 に示す．実行方法は，とで実行した．調整が許されているパラメータは，

150
MFlopsHotSpot Server VM

性能を SPEC JVM98 と Linpack ベンチマークで計SPEC に報告可能な（reportable）結果を得る方法，
すなわち，SPEC JVM98 のクラスはウェブサーバからロードし，application としてではなく applet として問題サイズ 100 で Auto Run ボタンを押すこ

100

HotSpot Client VM

ピーク性能とアプリケーション起動時間を比較することで，shuJIT の性能上の位置付けを明らかにする．

50

TYA
interpretersunwjit.so

Fig. 12

Linpack Benchmark
500 x 500
1.7 GHz Pentium 4

図 12 Linpack ベンチマークの結果
The result of Linpack Benchmark for Java.

SPEC JVM98 に含まれているプロパティファイル
（props/user）中の値をそのまま用いた．つまり，以下に述べるとおりのパラメータである．SPEC JVM98

た 7 種類のベンチマークプログラムを実行し，ある環に含まれる各ベンチマークは，最低 2 回（automin=2），

境での結果に基づいて実行時間を正規化し，その逆数

最高で 5 回（automax=5）繰り返して実行し，最良をスコアとする．総合スコアはそれらの相乗平均であの結果を採用する．ただし，前回の結果を最低でもる．Linpack Benchmark はガウスの消去法で連立 1

3%（percentTimes100=300）上回ることができなかっ次方程式を解き，結果は Flops で得られる．いずれもた場合は，その時点で繰返しを打ち切る．ベンチマー

高い値が良い結果を表す．

クの各実行の間には，500 ミリ秒（autodelay=500）

比較対象として，shuJIT と同じく PC 以上の規模のの 停 止 時 間 を 設 け る ．ま た ，各 実 行 の 間 に は性能，メモリ容量を想定している JIT コンパイラを集め

System.gc() と System.runFinalization() を呼び出す（autogc=true）．

た．すなわち, Sun 社の Java 2 SE 1.3.1 02 に含まれる
HotSpot Server VM 及び Client VM，IBM 社の Java

SPEC JVM98 は，実アプリケーションをもとにし2 SE 1.3.0 [18] [19]，Intel 社 の ORP（Open Run-228

論文／Java Just-in-Time コンパイラのためのコスト効率の良いコンパイル手法

time Platform） [14]，Transvirtual 社の Kaﬀe 1.0.6，
TYA 1.7v3 [4]，OpenJIT 1.1.16 [20]，Sun 社が Java
2 SE 1.2.2 とともに配布していた sunwjit.so，そして HotSpot Client VM のバイトコードインタプリタ

呼出しの際にそのメソッドを JIT コンパイルしてしまうという設定では，起動中に呼び出されたすべてのメ
ソッドがコンパイルされるため，起動時間に占めるコ
ンパイル時間の割合が大きくなる．そして，コンパイである．いずれの処理系でも 1.7 GHz Pentium 4 上

ル処理に要する時間の長さが起動時間に大きく反映さ

で OS として Linux 2.4.18-pre3 を用いている．以下，れることが期待できる．もし可能ならば，むしろコン

特に断りのない限り，実験結果はこの環境でのものでパイル時間を直接計測すべきだが，コンパイラのソーある．

スコードが手に入らない場合，計測のための時刻取得

ただし，ORP と Kaﬀe は SPEC に報告可能な方法

処理を追加できない．また，時刻の取得は行えたとし

で SPEC JVM98 を実行することができない．必要なライブラリが欠けているためである．このため，ORPても，OS によるプリエンプティブなプロセス切替や，Java ではごく当たり前であるスレッド切替が行われると Kaﬀe の結果は図 11 には含まれていない．

状況で，コンパイル時間を直接測定することは困難で

本コンパイラのピーク性能は，インタプリタの数倍ある．また，直観的には，アプリケーションの起動時は達成しているものの，他のコンパイラと比べて高い

間は利用者が感じるストレスを左右する大きな要因な方ではない．しかし，本コンパイラが指向する，処理ので，実際の使用感の指標ともなるだろう．

が軽くコストパフォーマンスが高いコンパイル手法は評価に使用するアプリケーションとしては，文書依然重要である．例えば，ORP [14]，Jikes RVM [21]作成ソフトウェア一太郎 Ark 1.1 と，統合開発環境

といった JVM は Java バイトコードのインタプリタ

NetBeans 3.3.1 を用いた．一太郎 Ark は，クラス数を持たず，その代わりとして，ベースラインコンパイ

が 904，圧縮後のコードサイズ（JAR ファイル）がラと呼ばれる処理の軽い JIT コンパイラをもっている．また，良いピーク性能を示している HotSpot VM

1652 キロバイトであり，NetBeans は圧縮後のコード
サイズが 2200 キロバイトという一定規模の実用ソフや IBM 社の Java 2 SE は，コンパイル対象とするメ

トウェアである．また，起動の完了を目視で判断しやソッドを厳しく限定している．未コンパイルのメソッ

すいことからこれらを選んだ．起動に要する時間は，

ドはまずインタプリタで実行され，呼出しや後方ジャ

ストップウォッチを用いて手で計測した．

ンプの回数が 1000∼10000 に達したメソッドに限って比較の対象は，JIT コンパイルを行うまでのメソッ

コンパイルする．あらゆるメソッドを時間をかけてコド呼出しの回数を指定できる JIT コンパイラ，すなわ

ンパイルするわけにはいかない以上，インタプリタやち，IBM 社の Java 2 SE 1.3.0 に含まれる JIT コン

ベースラインコンパイラの効率は重要である．

パイラ JITC 3.6 と Sun 社の HotSpot Client VM と

5. 2 アプリケーションの起動に要する時間
5. 1 の性能評価結果に表れているのは JIT コンパ

HotSpot Server VM である．shuJIT を含めて，これらの JIT コンパイラは，メソッドごとにカウンタをイラが生成したコードのピーク性能である．これらのもち，メソッド呼出しなどの際にこれを減じて，0 とベンチマークはピーク性能の測定を目的としており，なった際にそのメソッドをコンパイルする．この呼出一度コンパイルされたメソッドが頻繁に実行されるた
くなり，結果に表れない．特に SPEC JVM98 では同しカウンタの初期値は，特に指定しない場合，IBM のLinux/x86 用 JITC 3.6 では 2000，HotSpot Client
VM で 1500，HotSpot Server VM で 10000 となってじベンチマークプログラムが複数回実行されて最良のいる．ベースラインコンパイラには，呼び出された全結果が採用されるので，コンパイルに要する時間は隠メソッドをコンパイルするに耐えるだけの処理の軽さ

め，実行時間に対するコンパイル時間は相対的に小されがちである．
そこで，コンパイル処理に要する時間の比較を試みが要求されるため，shuJIT ではこの既定値は 0 としている．

た．評価の方法として，アプリケーションの起動に要呼出しカウンタの初期値を，0，3，2000，10000 とする時間を JIT コンパイラ間で比較するという方法を設定して，それぞれ，起動に要した時間を計測した．

採った．アプリケーションが起動するまでの間は，メ一太郎 Ark での結果を表 3 に，NetBeans での結果をソッドの初めての呼出しが頻繁に起こるため，JIT コ

表 4 に示す．∞ とあるのは，JIT コンパイルを禁止

ンパイルも頻繁に起きる傾向がある．特に，1 度目のして完全にインタプリタのみで実行した場合の結果で229電子情報通信学会論文誌 2003/4 Vol. J86–D–I No. 4
表 3 一太郎 Ark の起動に要する時間
Table 3 Start-up time of Ichitaro Ark.
カウンタの
IBM
HotSpot
HotSpot
初期値 shuJIT JITC Client VM Server VM
04.4 ∗ 22.1
計測不能
計測不能
3
4.0
14.1
5.9
32.1
1500
4.3
6.3
3.8 ∗
6.8
2000
4.4
5.7 ∗
3.7
6.6
10000
4.5
5.2
3.8
5.4 ∗
∞
3.9
5.0
4.0
4.1
（秒）
∗ カウンタ初期値の既定値

6. む す び
本論文では，コンパイル処理及び開発のコストを抑えつつ，研究基盤としての扱いやすさと高いコスト効率を達成した Java Just-in-Time コンパイラについて，コード生成手法と各種最適化手法を述べた．全メ
ソッドをコンパイルするベースラインコンパイラとしての使用に耐えるように，コンパイル処理のコストを低く保ちながら，インタプリタの数倍という実用的な性能を達成できることを示した．同時に，開発コスト

表 4 NetBeans の起動に要する時間
Table 4 Start-up time of NetBeans.
カウンタの
IBM
HotSpot
HotSpot
初期値 shuJIT JITC Client VM Server VM
08.9 ∗ 43.3
計測不能
計測不能
3
8.4
28.6
12.0
166.6
20.7
1500
10.3
10.8
8.6 ∗
∗
2000
10.7
10.6
8.5
20.9
10000
13.2
10.5
8.9
17.2 ∗
∞
12.2
14.0
13.0
13.4
（秒）
∗ カウンタ初期値の既定値も低く抑えたことで，1 人で 50 日前後の開発で，簡単なプログラムを動作させるに至った．
また，本コンパイラに実装した処理コストの低いい
くつかの最適化について，実装方法，性能上の効果，
コード生成手法との関係，Java 言語や仮想マシン仕様を遵守するためのペナルティ削減効果を論じた．メ
ソッド呼出しの性能が多くのベンチマークの結果に大きく影響すること，本コード生成手法に対して命令畳込みの効果が高いこと，シグナルを利用した例外検出の効果を示した．また，仕様遵守に伴う性能上のペナある．二つの HotSpot VM では，カウンタの初期値

ルティをコード書換えで回避するというベースライン

を 3 未満とした場合，試したどの Java プログラムもコンパイラ向きの手法を提案した．

起動しなかった．

派生研究の材料として扱いやすいものとするという

表 3，表 4 の結果は，厳密には，JIT コンパイラ間

目標も達成され，本コンパイラの開発者だけでなく，で公平に比較することができない．なぜなら，JVM や他の研究者によっても研究基盤として利用されるにインタプリタの実装がそれぞれ異なり，呼出しカウン

至った．

タを減じるタイミングも全く同じではないからである．

今後の課題としては，ベースラインコンパイラとイ

例えば，shuJIT が用いる JVM は Sun 社の Classic

ンタプリタの，性能，使用感，開発コストについての

VM であり，IBM JITC はそれを改造した JVM を用いている．HotSpot VM はまたそれらとは異なる

比較，呼出しカウンタのしきい値といったコンパイル

JVM である．カウンタを減じるタイミングは，shuJIT
ではメソッド呼出し時のみ，IBM JITC では呼出し及び後方ジャンプ時である．HotSpot VM も呼出し及びしたコンパイル済みコード破棄戦略などが挙げられる．

戦略の構成法，それと関連して，メモリ消費量を考慮
文[1]

Language Speciﬁcation, Second Edition”, Addison

ジャンプ時だが，ジャンプの方向が関係するか否かは公表されていない．

Wesley (2000).
[2]

T. Lindholm and F. Yellin: “The Java Virtual Ma-[3]

M. A. Ertl: “Stack caching for interpreters”, Proc.

それでも，カウンタの初期値が 0 の場合は確実に全メソッドがコンパイルされ，カウンタの減じ方は結果

chine Speciﬁcation”, Addison Wesley (1997).
ACM SIGPLAN Conference on Programming Lan-に影響を与えない．また，カウンタの初期値が小さい

guage Design and Implementation (PLDI), pp. 315–

場合に HotSpot Server VM での起動時間が 30 秒以

327 (1995).

上と非常に大きくなっており，JIT コンパイルに時間[4]が費やされていると考えることが自然である．処理が[5]

重い JIT コンパイラほど起動に時間がかかるという傾230

A. Kleine: “TYA”. http://sax.sax.de/˜ adlibit/.

首藤一幸, 村岡洋一：“Java Just-in-Time コンパイラ実用化と配布の経験”, Proc. of 第 4 回 プログラミングおよび応用のシステムに関するワークショップ (SPA2001)

向が表れており，shuJIT のコンパイル処理が軽いことを確認できた．

献

J. Gosling, B. Joy, G. Steele and G. Bracha: “Java(2001).
[6]

首藤一幸, 関口智嗣, 村岡洋一：“厳密な浮動小数点演算セ

論文／Java Just-in-Time コンパイラのためのコスト効率の良いコンパイル手法
マンティクスの java 実行時コンパイラへの実装”, 情報処
理学会研究報告, 2001-ARC-144, pp. 99–104 (2001).
[7]

[9]

14th European Conference on Object-Oriented Pro-

M. Welsh and D. Culler: “Jaguar: Enabling eﬃcient
communication and I/O from Java”, Concurrency:[8]

reﬂective JIT compile framework for Java”, Proc. ofgramming (ECOOP ’2000) (2000).
[21]

B. Alpern, C. R. Attanasio, J. J. Barton, M. G.

Practice and Experience, Special Issue on Java for

Burke, P. Cheng, J.-D. Choi, A. Cocchi, S. J. Fink,

High-Performance Applications (1999).
首藤一幸, 根山亮, 村岡洋一：“プログラマに単一マシン

D. Grove, M. Hind, S. F. Hummel, D. Lieber,

ビューを提供する分散オブジェクトシステムの実現”, 情V. Sarkar, M. J. Serrano, J. C. Shepherd, S. E. Smith,

報処理学会論文誌, 40, no.SIG 7（PRO 4）, pp. 66–79(1999).

V. C. Sreedhar, H. Srinivasan and J. Whaley: “TheK. Shudo and Y. Muraoka: “Eﬃcient implementa-

Java Performance Issue, 39, 1 (2000).

tion of strict ﬂoating-point semantics”, Proc. of 2nd

V. Litvinov, M. F. Mergen, T. Ngo, J. R. Russell,

Jalapeño virtual machine”, IBM Systems Journals,（平成 14 年 4 月 10 日受付，8 月 19 日再受付）

Workshop on Java for High-Performance Computing(in conj. with ICS’00), pp. 27–38 (2000).
[10]

A.-R. Adl-Tabatabai, M. Cierniak, G.-Y. Lueh, V. M.
Parikh and J. M. Stichnoth: “Fast, eﬀective code
generation in a Just-In-Time Java compiler”, Proc.
ACM SIGPLAN ’98 Conference on Programming
Language Design and Implementation (PLDI), pp.
280–290 (1998).

[11]

[12]

重田大助, 小川洋平, 山田克樹, 中島康彦, 富田眞治：“命令畳み込み，データ投機および再利用技術を用いた Java 仮

首藤一幸

1996 早大・理工・情報卒．1998 同大メ
ディアネットワークセンター助手．2001 同大大学院理工学研究科博士後期課程了．同想マシンの高速化”, 情報処理学会論文誌, 41, No.SIG05

年産業技術総合研究所入所．現在に至る．
博士（情報科学）．分散処理方式，プログ（HPS 1）, pp. 28–38 (2000).
H. McChan and M. O’Connor: “PicoJava: A direct

ラミング言語，言語処理系，情報セキュリ
ティ等に興味を持つ．IEEE–CS，ACM 各会員．

execution engine for Java bytecode”, COMPUTER,
31, 10, pp. 22–30 (1998).
[13]

L.-R. Ton, L.-C. Chang, M.-F. Kao, H.-M. Tseng,
S.-S. Shang, R.-L. Ma, D.-C. Wang and C.-P. Chung:“Instruction folding in Java processor”, Int’l Conference on Parallel and Distributed Systems, pp. 138–

[14]

智嗣

1984 工業技術院電子技術総合研究所入所．以来，データ駆動型スーパーコンピュー

143 (1997).

タ SIGMA-1 の開発，ネットワーク数値ラ
イブラリ Ninf，クラスタコンピューティン

M. Cierniak, G.-Y. Lueh and J. Stichnoth: “Prac-グ，グリッドコンピューティング等に関す

ticing JUDO: Java under dynamic optimizations”,

る研究に従事．2001 独立行政法人産業技術総合研究所に改組．2002 年 1 月より同所グリッド研究センター

Proc. ACM SIGPLAN ’00 Conference on Programming Language Design and Implementation (PLDI)
[15]

関口

(2000).

長．市村賞，情報処理学会論文賞受賞．グリッド協議会会長．
情報処理学会，日本応用数理学会，日本計算工学会，SIAM，Intel Corporation: “IA–32 Intel Architecture Soft-

IEEE，つくばサイエンスアカデミー各会員．

ware Developer’s Manual Volume 3: System Programming Guide” (2001).
[16]

松岡聡：“Java とかの高速化技法”, 並列処理シンポジウ
ム JSPP2000 チュートリアル資料, pp. 1–37 (2000).

[17]

丸山冬彦：“JIT コンパイラ向けアプリケーションフレー
ムワークの設計と実装”, 修士論文, 東京工業大学 (2001).

[18]

T. Suganuma, T. Ogasawara, M. Takeuchi, T. Yasue, M. Kawahito, K. Ishizaki, H. Komatsu and

洋一 （正員）1965 早大・理工・電気通信卒．1971 イリ

ノイ大学電子計算機学科博士課程了．Ph.D．
この間，Illiac-IV プロジェクトで並列処理
ソフトウェアの研究に従事．同学科助手のT. Nakatani: “Overview of the IBM Java Just-In-

後，日本電信電話公社（現 NTT）電気通信研究所に入所．1985 より早稲田大学理Time compiler”, IBM Systems Journals, Java Perfor-

工学部教授．現在同大学メディアネットワークセンター所長．

mance Issue, 39, 1 (2000).
[19]

村岡

石崎一明, 川人基弘, 今野和浩, 安江俊明, 竹内幹雄, 小笠

並列処理，マンマシンインタフェース等に興味を持つ．
「コン
ピュータアーキテクチャ」（近代科学社）など著書多数．

原武史, 菅沼俊夫, 小野寺民也, 小松秀昭：“Java Just-InTime コンパイラにおける最適化とその評価”, 電子情報通[20]

信学会技術研究報告, CPSY99-64, pp. 17–24 (1998).
H. Ogawa, K. Shimura, S. Matsuoka, F. Maruyama,
Y. Sohda and Y. Kimura: “OpenJIT: An open-ended,

231