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