(57)【要約】【課題】仮想命令コード実行環境において、ネイティブコードのメインルート走行時のインストラクションキャッシュおよびＴＬＢのヒット率の向上を図る。【解決手段】分岐検出命令埋め込み部２００はＪａｖａ中間コード１００に分岐検出命令を埋め込み、中間コード３００を生成する。中間コード３００は逐次実行され、その際に分岐検出命令が実行され、分岐回数管理テーブル３０１の当該分岐ルートのカウンタが１加算される。優先パス検出部４００は分岐回数管理テーブル３０１の内容を見て分岐率を分析し、分岐率の高い分岐ルートを選択してメインルートを検出する。メモリ配置部５００はメインルートのネイティブコードをメインルート用メモリ領域５０２へ、それ以外のルートのネイティブコードをレアルート用メモリ領域５０３へ配置する。【選択図】　　図１
2004078822.tif 000002
【特許請求の範囲】
【請求項１】
プログラム実行時の動的なデータを基に仮想命令コードの最適化および実マシン命令コードへの変換をプログラムを実行しながら動的に行う動的コンパイラを実装した仮想命令コード実行環境において、
中間コード中の、実行回数が閾値を越えたメソッドに対し、各条件分岐命令の分岐ルート中に、処理が当該分岐ルートに分岐したことを検出する分岐検出命令を埋め込む分岐検出命令埋め込み段階と、
前記分岐検出命令が埋め込まれたメソッドが実行される際に、前記分岐検出命令が実行された回数をカウントすることで、当該分岐ルートへの分岐回数をカウントする分岐回数カウント段階と、
前記分岐検出命令が埋め込まれたメソッドを先頭から走査し、条件分岐命令については該条件分岐命令の分岐ルートのうち、分岐回数が多い分岐ルートを選択することで得られるパスを優先パスと決定する優先パス検出段階と、
前記優先パスのネイティブコードはメモリのメインルート領域へ、前記優先パス以外のパスのネイティブコードは前記メモリのレアルート領域に配置するメモリ配置段階を有する、ネイティブコード配置方法。
【請求項２】
プログラム実行時の動的なデータを基に仮想命令コードの最適化および実マシン命令コードへの変換をプログラムを実行しながら動的に行う動的コンパイラを実装した仮想命令コード実行環境において、
中間コード中の、実行回数が閾値を越えたメソッドに対し、各条件分岐命令の分岐ルート中に、処理が当該分岐ルートに分岐したことを検出する分岐検出命令を埋め込む分岐検出命令埋め込み手段と、
各分岐ルートへの分岐回数の情報を保存する分岐回数管理テーブルと、
前記分岐検出命令が埋め込まれたメソッドが実行される際に、前記分岐検出命令が実行されると、前記分岐回数管理テーブルの当該分岐ルートの分岐回数の情報を更新する分岐回数カウント手段と、
前記分岐検出命令が埋め込まれたメソッドを先頭から走査し、条件分岐命令については該条件分岐命令の分岐ルートのうち、前記分岐回数管理テーブル中の分岐回数の情報が分岐回数の多いことを示している分岐ルートを選択することで得られるパスを優先パスと決定する優先パス検出手段と、
前記優先パスのネイティブコードはメモリのメインルート領域へ、前記優先パス以外のパスのネイティブコードは前記メモリのレアルート領域に配置するメモリ配置手段を有するネイティブコード配置装置。
【請求項３】
請求項１のネイティブコード配置方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、プログラム実行時の動的なデータ（プロファイル）を基に仮想命令コードの最適化および実マシン命令コードへの変換をプログラムを実行しながら動的に行う動的コンパイラを実装した仮想命令コード実行環境において、ネイティブコードをメモリに動的に配置する方法、装置、およびプログラムに関するものである。
【０００２】
【従来の技術】
プログラム実行時の動的なデータ（プロファイル）を基に仮想命令コードの最適化および実マシン命令コードへの変換をプログラムを実行しながら動的に行う既存の動的コンパイラを実装した仮想命令コード実行環境においては、ネイティブコードをメソッド単位にメモリに配置しているため、実行頻度の高いネイティブコードと実行頻度の低いネイティブコードが混在してメモリに配置されている。
【０００３】
【発明が解決しようとする課題】
このため、従来の技術では、インストラクションキャッシュ領域が有効利用されていなかった。
【０００４】
本発明の目的は、ネイティブコードのメインルート走行時のインストラクションキャッシュのキャッシュヒット率およびＴＬＢ（Ｔｒａｎｓｌａｔｉｏｎ　Ｌｏｏｋａｓｉｄｅ　Ｂｕｆｆｅｒ）のヒット率の向上を図ったネイティブコード配置方法、装置、およびプログラムを提供することにある。
【０００５】
【課題を解決するための手段】
まず、中間コード中の、実行回数が閾値を越えたメソッドに対し、各条件分岐命令の分岐ルート中に、処理が当該分岐ルートに分岐したことを検出する分岐検出命令を埋め込む。次に、分岐検出命令が埋め込まれたメソッドが実行される際に、分岐検出命令が実行された回数をカウントすることで、当該分岐ルートへの分岐回数をカウントする。次に、分岐検出命令が埋め込まれたメソッドを先頭から走査し、条件分岐命令については該条件分岐命令の分岐ルートのうち、分岐回数の多い分岐ルートを選択することで得られるパスを優先パスと決定する。最後に、優先パスのネイティブコードはメモリのメインルート領域へ、優先パス以外のパスのネイティブコードはメモリのレアルート領域に配置する。
【０００６】
本発明は、検出された優先パスを元に、複数メソッドに存在する分岐ルートをメインルート／レアルートに分類し、メインルート（優先パス）のネイティブコードをメモリのメインルート領域へまとめて配置することで、インストラクションキャッシュのキャッシュヒット率およびＴＬＢのヒット率を向上させることができる。
【０００７】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
【０００８】
図１は本発明の一実施形態のネイティブコード配置装置のブロック図で、プログラム実行時の動的なデータ（プロファイル）を基に仮想命令コードの最適化および実マシン命令コードへの変換をプログラムを実行しながら動的に行う動的コンパイラを実装した仮想命令コード実行環境の代表的な例としてＪａｖａ仮想マシンを示している。
【０００９】
本実施形態のネイティブコード配置装置はＪａｖａ中間コードインタプリタ１０１とメソッド実行回数管理テーブル１０２と分岐検出命令埋め込み部２００と分岐回数管理テーブル３０１と優先パス検出部４００とメモリ配置部５００とメモリ５０１を有している。
【００１０】
Ｊａｖａ中間コードインタプリタ１０１はＪａｖａ中間コード１００の実行、メソッド実行回数のカウント、分岐検出命令埋め込み部２００の起動、分岐回数管理テーブル３０１のカウンタの更新を行なう。
【００１１】
ネイティブコンパイラを備えた処理装置では、メソッド実行回数管理テーブル１０２を備えており、実行回数がある闘値を超えた場合に、メモリ配置部５００が機能の一部として含むネイティブコードコンパイラを起動することで、実行頻度の高いメソッドのネイティブコードへの変換を行い、処理効率を上げている。
本発明では、実行回数が闘値を超えた場合にメモリ配置部５００を起動せず、分岐検出命令埋め込み部２００を起動する。メソッド実行回数管理テーブル１０２は表１に示すように各メソッドの実行回数を管理している。
【００１２】
【表１】
2004078822.tif 000003
【００１３】
分岐検出命令埋め込み部２００はＪａｖａ中間コード１００中の、実行回数が閾値を越えたメソッドに対して分岐検出命令の埋め込みを行い、分岐検出命令が埋め込まれたメソッドのＪａｖａ中間コード３００を生成する。分岐回数管理テーブル３０１は表２に示すように分岐検出命令が埋め込まれた各メソッドにおける各分岐ルート毎の実行（分岐）回数の情報を保持する。
【００１４】
【表２】
2004078822.tif 000004
【００１５】
優先パス検出部４００は分岐検出命令が埋め込まれたメソッドの中間コード３００を先頭から走査し、分岐回数管理テーブル３０１の内容を見て各分岐命令の分岐ルートの分岐率を分析し、分岐率の高い分岐ルートを順次選択して得られるルートを個々のメソッドにおけるメインルートと判断し、メモリ配置部５００を呼び出す。メモリ配置部５００はメインルートのネイティブコードをメモリ５０１内のメインルート用メモリ領域５０２に配置し、それ以外のルートのネイティブコードをレアルート用メモリ領域５０３に配置する。
【００１６】
次に、本実施形態の動作を図２を参照して説明する。
【００１７】
１．Ｊａｖａ中間コード１００はＪａｖａ中間コードインタプリタ１０１により逐次実行され、メソッド実行回数管理テーブル１０２中の当該メソッドの実行回数が１加算される。メソッドの実行回数がある閾値を越えると、Ｊａｖａ中間コードインタプリタ１０１は分岐検出命令埋め込み部２００を起動する。
【００１８】
２．分岐検出命令埋め込み部２００はＪａｖａ中間コード１００中の、実行回数が閾値を越えたメソッドに対し分岐検出命令の埋め込みを行い、分岐検出命令の埋め込まれたメソッドの中間コードであるＪａｖａ中間コード３００を生成する。このとき、当該メソッドに対応した分岐回数管理テーブル３０１を準備し、準備ができ次第、その後はＪａｖａ中間コード１００中の相当するメソッドの代わりに、分岐検出命令を埋め込んだメソッドの中間コードであるＪａｖａ中間コード３００を使用する。
【００１９】
３．Ｊａｖａ中間コード３００を含むプログラム全体の中間コードはＪａｖａ中間コードインタプリタ１０１により逐次実行され、前出のメソッド以外に実行回数が閾値を超えるメソッドの検出を続けるとともに、Ｊａｖａ中間コード３００においては分岐検出命令が実行され、分岐検出情報が出力され、Ｊａｖａ中間コードのインタプリタ１０１によって当該メソッドの分岐回数管理テーブル３０１の当該分岐検出命令、すなわち分岐ルートのカウンタが１加算される。分岐回数管理テーブル３０１内のカウンタ（実行回数）が閾値を越えた場合、Ｊａｖａ中間コードインタプリタ１０１は優先パス検出部４００を呼び出す。なお、優先パス検出部４００を呼び出す契機としては、上記で示した分岐回数管理テーブル３０１内のカウンタのいずれかが閾値を超えた場合のほかに、分岐回数管理テーブル３０１内のカウンタの総和が閾値を超えた場合や、分岐回数管理テーブル３０１内のカウンタの全てが閾値を越えた場合や、メソッドの実行回数が閾値を超えた場合などが考えられる。
【００２０】
４．優先パス検出部４００は当該メソッドの分岐回数管理テーブル３０１の内容を見て各分岐命令の分岐ルートの分岐率を分析し、分岐率の高い分岐ルートを順次選択して得られるルートをメインルートと判断し、メモリ配置部５００を呼び出す。
【００２１】
５．メモリ配置部５００は優先パスが検出されたメソッドの中間コードをネイティブコードに変換し、メインルートのネイティブコードをメインルート用メモリ領域５０２へ配置し、それ以外のルートのネイティブコードをレアルート用メモリ領域５０３へ配置する。本動作は、実行回数がその閾値を超え、その後、分岐回数もその閾値を越えるメソッドが生じるごとに繰り返される。
【００２２】
図３は上記ステップ２と３の詳しい処理を示す図である。
【００２３】
分岐検出命令埋め込み部２００はＪａｖａ中間コード１００中の、実行回数が閾値を越えたメソッドを分析し、Ｊａｖａ中間コード１００中の条件分岐命令、図２（１）の例では、２行目と６行目の分岐命令を検出する。
【００２４】
次に、条件分岐命令の分岐ルートを検出する。図の例の２行目の分岐命令では、「ｇｏｔｏ　ｃ；」で５行目に分岐する場合（図中［１］）と、３行目が実行される場合（図中［２］）の２通りの分岐ルートがある。同様に、６行目の分岐命令では、「ｇｏｔｏ　ｅ；」で９行目に分岐する場合（図中［３］）と、７行目が実行される場合（図中［４］）の２通りの分岐ルートがある。
【００２５】
上記で検出された分岐ルートに対し、図中の例では順に１から始まる整数値をＩＤとして付与する。図中の分岐ＩＤがこれに相当する。
【００２６】
次に、分岐ルートの実行直前に分岐検出命令を埋め込む。この命令は分岐回数管理テーブル３０１の分岐ＩＤ番目のカウンタを１加算する処理である。
【００２７】
分岐検出命令の埋め込みが終わると、各分岐検出命令に対してカウンタを準備し、カウンタ全てに初期値０を設定する。
【００２８】
分岐検出命令埋め込み後のコードが実行されると、走行した分岐ルートに対応するカウンタが１加算されることになる。カウンタのいずれか１つが所定の値ｚに到達したときに、ステップ４に進む。ｚの値は分岐回数情報を収集する時間をどのくらいにしたいかにより決定する。なお、カウンタ全てに初期値ｚを設定し、ターゲットのメソッドが実行され、分岐が実行される際、分岐ルートに対応したカウンタを１減算し、カウンタのいずれか１つが０になった時にステップ４に進むようにしてもよい。
【００２９】
図４は、上記のステップ４を説明したものである。図中のコードは命令並べ替え前のＪａｖａ中間コード３００である。この中間コード３００において、２行目の分岐命令の分岐ルートの分岐率は［１］：［２］＝０．９：０．１、６行目の分岐命令の分岐ルートの分岐率は［３］：［４］＝０．３：０．７だったとする。優先パス検出部４００はＪａｖａ中間コード３００を先頭から走査し、次のように優先パス（メインルート）を決定する。
【００３０】
Ｊａｖａ中間コード３００を先頭から走査する。走査を完了した命令にはマークを付け、走査済みであることがわかるようにする。ｇｏｔｏ系の無条件分岐命令については分岐ルートを追跡する。ｉｆ、ｓｗｉｔｃｈ系の条件分岐命令については、分岐回数情報に基づき、分岐率の高い分岐ルートを追跡する。仮に分岐率が同じであった場合は何れか任意の分岐ルートを選択する。追跡中に走査完了命令にループした場合には、走査済みの末尾の命令の次に進む。ｒｅｔｕｒｎ命令を検出した時点で走査を終了する。
【００３１】
以上の処理を図中の例で示す。
（１）１行目。
（２）２行目。条件分岐命令であるため、分岐率を見ることで次は５行目に進めばよいことがわかる。
（３）５行目。
（４）６行目。条件分岐命令であるため、分岐率を見ることで次は７行目に進めばよいことがわかる。
（５）７行目。
（６）８行目。無条件分岐命令のため１０行目に進む。
（７）１０行目。
（８）１１行目。ｒｅｔｕｒｎ命令のため終了。
【００３２】
以上のように、（１）〜（８）の順である、１→２→５→６→７→８→１０→１１を優先パスと判定する。図中の「優先パス決定」はこの順序を示したものである。
【００３３】
図５は、メインルートのネイティブコードとレアルートのネイティブコードを別領域にメモリ配置するステップを説明したものである。
【００３４】
メソッドＡでは、メインルートはＡ→Ｃ→Ｄ→Ｆであり、メソッドＢでは、メインルートはＧ→Ｉ→Ｊである。メモリ５０１をメインルート用領域５０２と、レアルート用領域５０３に分けて確保し、メインルートＡ，Ｃ，Ｄ，Ｆ，Ｇ，Ｉ，Ｆをメインルート用領域５０２へ入れ、残りのＢ，Ｅ，Ｈはレアルート用領域５０３に保存する。
【００３５】
その結果、インストラクションキャッシュのフェッチ時に、メインルートがまとまってキャッシュされることになる。
【００３６】
なお、以上説明したネイティブコード配置方法は専用のハードウェアにより実現されるもの以外に、その機能を実現するためのプログラムを、コンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行するものであってもよい。コンピュータ読み取り可能な記録媒体とは、フロッピーディスク、光磁気ディスク、ＣＤ−ＲＯＭ等の記録媒体、コンピュータシステムに内蔵されるハードディスク装置等の記憶装置を指す。さらに、コンピュータ読み取り可能な記録媒体は、インターネットを介してプログラムを送信する場合のように、短時間の間、動的にプログラムを保持するもの（伝送媒体もしくは伝送波）、その場合のサーバとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含む。
【００３７】
【発明の効果】
以上説明したように、本発明によれば、プログラム実行時の動的なデータ（プロファイル）を基に仮想命令コードの最適化および実マシン命令コードへの変換をプログラムを実行しながら動的に行う動的コンパイラを実装した仮想命令コード実行環境において、プログラムのユーザコーディングを変更せずに、インストラクションキャッシュのキャッシュヒット率およびＴＬＢのヒット率が向上し、性能が向上する。
【図面の簡単な説明】
【図１】本発明の一実施形態のネイティブコード配置装置の構成図である。
【図２】図１の装置における処理手順を示す図である。
【図３】Ｊａｖａ中間コードへの分岐検出命令の埋め込みと分岐検出処理の具体例による説明図である。
【図４】分岐率分析と優先パス決定の具体例による説明図である。
【図５】メインルートとレアルートを別領域に配置する処理の具体例による説明図である。
【符号の説明】
１００　　Ｊａｖａ中間コード
１０１　　Ｊａｖａ中間コードインタプリタ
１０２　　メソッド実行回数管理テーブル
２００　　分岐検出命令埋め込み部
３００　　分岐検出命令埋め込み後のＪａｖａ中間コード
３０１　　分岐回数管理テーブル
４００　　優先パス検出部
５００　　メモリ配置部
５０１　　メモリ
５０２　　メインルート用メモリ領域
５０３　　レアルート用メモリ領域
【図１】
2004078822.tif 000005
【図２】
2004078822.tif 000006
【図３】
2004078822.tif 000007
【図４】
2004078822.tif 000008
【図５】
2004078822.tif 000009