(57)【要約】【課題】優先して最適化するべき命令群を適切に選択する。【解決手段】コンパイル対象の対象プログラムを最適化するコンパイラ装置は、対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象である最適化対象命令として検出する命令検出部と、検出された最適化対象命令との間で実行順序が定まっており、かつ当該最適化対象命令に先立って実行される命令の集合である最適化対象命令群を選択する命令群選択部と、最適化対象命令群が、最適化対象命令群以外の命令群より効率良く実行されるように対象プログラムを最適化する最適化部とを備える。【選択図】  図１
2004362216.tif 000002
【特許請求の範囲】
【請求項１】
コンパイル対象の対象プログラムを最適化するコンパイラ装置であって、
前記対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象である最適化対象命令として検出する命令検出部と、
検出された前記最適化対象命令との間で実行順序が定まっており、かつ当該最適化対象命令に先立って実行される命令の集合である最適化対象命令群を選択する命令群選択部と、
最適化による前記最適化対象命令群の実行速度向上率が、最適化による最適化対象命令群以外の命令群の実行速度向上率より高くなるように、前記対象プログラムを最適化する最適化部と
を備えるコンパイラ装置。
【請求項２】
前記対象プログラムは、少なくとも一の関数を含み、
前記命令検出部は、前記関数を終了させる関数終了命令を、前記最適化対象命令として検出し、
前記命令群選択部は、前記関数において前記最適化対象命令に先立って実行される命令群を前記最適化対象命令群として選択する
請求項１記載のコンパイラ装置。
【請求項３】
前記命令検出部は、更に、前記対象プログラムのうち予め定められた他の種類の命令を、優先して最適化する対象から除外するべき最適化除外命令として検出し、
前記命令群選択部は、前記最適化対象命令との間に実行順序が定まり、かつ前記最適化対象命令に先立って実行される命令のうち、前記最適化除外命令として選択されていない命令の集合を、前記最適化対象命令群として選択する
請求項１記載のコンパイラ装置。
【請求項４】
前記対象プログラムは、予め定めた例外発生条件が満たされた場合に、当該例外発生条件の種類に応じた例外捕捉処理に移行し、
前記命令検出部は、前記対象プログラムの実行時に前記例外捕捉処理に移行させる前記例外発生命令を前記最適化除外命令として検出する
請求項３記載のコンパイラ装置。
【請求項５】
前記対象プログラムは、予め定めた例外発生条件が満たされた場合に、当該例外発生条件の種類に応じた例外捕捉処理に移行し、
前記命令検出部は、前記例外捕捉処理に含まれる何れかの命令を前記最適化除外命令として検出する
請求項３記載のコンパイラ装置。
【請求項６】
前記対象プログラムは、データを参照するデータ参照命令を有し、
当該データ参照命令は、参照先のデータの格納位置を解析していない参照位置未解決状態において当該データ参照命令が実行された場合に、参照先のデータの格納位置を示す情報を含む直接参照命令に書き換えられ、
前記命令検出部は、前記参照位置未解決状態の前記データ参照命令を前記最適化除外命令として検出する
請求項３記載のコンパイラ装置。
【請求項７】
前記対象プログラムは、所定のパラメータを入力として、当該パラメータに応じた処理を行う処理命令を含み、
前記処理命令と同一処理を行う命令であって、前記パラメータが予め定めた条件を満たす場合に前記処理命令より高速に実行される条件適合時処理命令と、前記パラメータが当該予め定めた条件を満たさない場合に実行される条件不適時処理命令とを、前記処理命令に代えて生成する処理命令複製部を更に備え、
前記命令検出部は、前記条件不適時処理命令を前記最適化除外命令として検出する
請求項３記載のコンパイラ装置。
【請求項８】
前記命令群選択部は、
前記最適化除外命令の直前に実行される命令を最適化除外命令として検出し、
前記最適化対象命令の直前に実行される命令を最適化対象命令として検出する実行情報伝播部と、
分岐先の何れかの命令が前記最適化対象命令である分岐命令を最適化対象命令として検出し、分岐先の何れの命令も前記最適化対象命令でなく、かつ分岐先の何れかの命令が前記最適化除外命令である分岐命令を最適化除外命令として検出する分岐命令伝播部と
を有し、前記対象プログラムのそれぞれの命令に対して前記実行情報伝播部及び前記分岐命令伝播部による処理を繰り返し適用することにより検出された前記最適化対象命令の集合を、前記最適化対象命令群として選択する
請求項３記載のコンパイラ装置。
【請求項９】
前記対象プログラムを実行することにより、前記対象プログラムに含まれる少なくとも一部の命令のそれぞれについて、当該命令の実行頻度を計測する実行頻度情報計測部を更に備え、
前記命令群選択部は、検出された前記最適化除外命令の前記実行頻度情報計測部による前記実行頻度が予め定めた第１頻度より高い場合に、当該最適化除外命令を前記最適化対象命令群として選択し、更に、検出された前記最適化対象命令の前記実行頻度情報計測部による前記実行頻度が前記第１頻度より低い値に予め定めた第２頻度より低い場合に、当該最適化対象命令を前記最適化除外命令として選択する
請求項３記載のコンパイラ装置。
【請求項１０】
前記命令群選択部は、検出された前記最適化対象命令から実行順序を遡って順次命令を選択することにより、前記最適化対象命令群を選択し、
前記最適化部は、選択された前記最適化対象命令群を順次実行する実行経路の最適化による実行速度向上率が、前記最適化対象命令群以外の命令群の最適化による実行速度向上率より高くなるように最適化する
請求項１記載のコンパイラ装置。
【請求項１１】
最適化による前記最適化対象命令群の実行速度向上率を最適化による前記最適化対象命令群以外の命令群の実行速度向上率より高くなるように最適化する処理として、前記最適化部は、前記対象プログラムにおける前記最適化対象命令群以外の最適化除外命令群を除外してコンパイルした後、前記対象プログラムを実行させ、当該最適化対象命令群が実行された結果前記最適化除外命令群の実行が必要となった場合に、前記最適化除外命令群をコンパイルする
請求項１記載のコンパイラ装置。
【請求項１２】
前記対象プログラムは、複数のページを有するメインメモリと、前記複数のページのそれぞれを利用者からアクセス可能な仮想アドレスに割り当てる仮想メモリ割当処理部とを有する装置により実行され、
前記最適化部は、前記最適化対象命令群を、前記最適化対象命令群以外の命令群とは異なる前記ページに配置することにより、最適化による前記最適化対象命令群の実行速度向上率が、最適化による前記最適化対象命令群以外の命令群の実行速度向上率より高くなるように、前記対象プログラムを最適化する
請求項１記載のコンパイラ装置。
【請求項１３】
最適化による前記最適化対象命令群の実行速度向上率を最適化による前記最適化対象命令群以外の命令群の実行速度向上率より高くなるように最適化する処理として、前記最適化部は、前記対象プログラムにおける前記最適化対象命令群以外の最適化除外命令群を除外した部分において、呼び出し側関数内の最適化対象命令群から呼び出される相手側関数内の処理を、呼び出し側の最適化対象命令群に含めて実行させるインライン展開処理を行う
請求項１記載のコンパイラ装置。
【請求項１４】
前記命令検出部は、更に、前記対象プログラムの命令のうち予め定められた他の種類の命令を、前記最適化対象命令より最適化を優先させず、かつ優先して最適化する対象から除外した最適化除外命令より優先させて最適化させる最適化準対象命令として検出し、
前記命令群選択部は、前記最適化対象命令及び前記最適化準対象命令のそれぞれとの間で実行順序が定まっており、かつ前記最適化対象命令及び前記最適化準対象命令のそれぞれに先だって実行される命令群を、前記最適化対象命令群として選択し、前記最適化準対象命令との間で実行順序が定まっており、かつ前記最適化対象命令との間で実行順序が定まっていない命令群を、最適化準対象命令群として選択し、
前記最適化部は、更に、最適化による前記最適化準対象命令群の実行速度向上率を、最適化による前記最適化対象命令群の実行速度向上率より低く、かつ最適化による前記最適化除外命令の実行速度向上率より高くなるように、前記対象プログラムを最適化する
請求項１記載のコンパイラ装置。
【請求項１５】
前記対象プログラムを実行することにより、前記対象プログラムに含まれる少なくとも一部の命令のそれぞれについて、当該命令の実行頻度を計測する実行頻度情報計測部を更に備え、
前記命令検出部は、更に、前記対象プログラムの命令のうち予め定められた他の種類の命令について、前記実行頻度情報計測部による実行頻度が予め定められた範囲内であることを更に条件として、前記最適化準対象命令として検出する
請求項１４記載のコンパイラ装置。
【請求項１６】
コンパイル対象の対象プログラムを最適化するコンパイラ装置であって、
前記対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象から除外するべき最適化除外命令として検出する命令検出部と、
検出された前記最適化除外命令から、実行順序を遡って、最適化対象として予め定められた命令を検出するまで順次命令を選択することにより、優先して最適化する対象から除外するべき最適化除外命令群を選択する命令群選択部と、
最適化による前記最適化除外命令群以外の命令群の実行速度向上率が、最適化による前記最適化除外命令群の実行速度向上率より高くなるように前記対象プログラムを最適化する最適化部と
を備えるコンパイラ装置。
【請求項１７】
コンパイル対象の対象プログラムを最適化するコンパイル方法であって、
前記対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象である最適化対象命令として検出する命令検出段階と、
検出された前記最適化対象命令との間で実行順序が定まっており、かつ当該最適化対象命令に先立って実行される命令の集合である最適化対象命令群を選択する命令群選択段階と、
最適化による前記最適化対象命令群の実行速度向上率が、最適化による前記最適化対象命令群以外の命令群の実行速度向上率より高くなるように前記対象プログラムを最適化する最適化段階と
を備えるコンパイル方法。
【請求項１８】
コンパイル対象の対象プログラムを最適化するコンパイル方法であって、
前記対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象から除外するべき最適化除外命令として検出する命令検出段階と、
検出された前記最適化除外命令から、実行順序を遡って、最適化対象として予め定められた命令を検出するまで順次命令を選択することにより、優先して最適化する対象から除外するべき最適化除外命令群を選択する命令群選択段階と、
最適化による前記最適化除外命令群以外の命令群の実行速度向上率が、最適化による前記最適化除外命令群の実行速度向上率より高くなるように前記対象プログラムを最適化する最適化段階と
を備えるコンパイル方法。
【請求項１９】
コンパイル対象の対象プログラムを最適化するコンパイラ装置としてコンピュータを機能させるコンパイラプログラムであって、
前記コンピュータを、
前記対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象である最適化対象命令として検出する命令検出部と、
検出された前記最適化対象命令との間で実行順序が定まっており、かつ当該最適化対象命令に先立って実行される命令の集合である最適化対象命令群を選択する命令群選択部と、
最適化による前記最適化対象命令群の実行速度向上率が、最適化による前記最適化対象命令群以外の命令群の実行速度向上率より高くなるように前記対象プログラムを最適化する最適化部と
して機能させるコンパイラプログラム。
【請求項２０】
前記命令検出部は、更に、前記対象プログラムのうち予め定められた他の種類の命令を、優先して最適化する対象から除外するべき最適化除外命令として検出し、
前記命令群選択部は、前記最適化対象命令との間に実行順序が定まり、かつ前記最適化対象命令に先立って実行される命令のうち、前記最適化除外命令として選択されていない命令の集合を、前記最適化対象命令群として選択する
請求項１９記載のコンパイラプログラム。
【請求項２１】
コンパイル対象の対象プログラムを最適化するコンパイラ装置としてコンピュータを機能させるコンパイラプログラムであって、
前記コンピュータを、
前記対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象から除外するべき最適化除外命令として検出する命令検出部と、
検出された前記最適化除外命令から、実行順序を遡って、最適化対象として予め定められた命令を検出するまで順次命令を選択することにより、優先して最適化する対象から除外するべき最適化除外命令群を選択する命令群選択部と、
最適化による前記最適化除外命令群以外の命令群の実行速度向上率が、最適化による前記最適化除外命令群の実行速度向上率より高くなるように前記対象プログラムを最適化する最適化部と
して機能させるコンパイラプログラム。
【請求項２２】
請求項１９から請求項２１の何れかに記載のコンパイラプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンパイラ装置、コンパイル方法、コンパイラプログラム、及び記録媒体に関する。特に本発明は、優先して最適化するべき命令群を選択するコンパイラ装置、コンパイル方法、コンパイラプログラム、及び記録媒体に関する。
【０００２】
【従来の技術】
コンパイル対象の対象プログラムに含まれる関数又はメソッド中には、頻繁に実行される命令群と、全く或いはほとんど実行されない命令群とが存在する。従来、予め対象プログラムを実行することにより各命令の実行頻度を計測しておき、頻繁に実行される命令群を優先して最適化する方法（非特許文献１参照。）、又は頻繁に実行される命令群のみをコンパイルする方法（非特許文献５参照。）が提案されている。後者の方法によると、コンパイラは、ほとんど実行されない命令群のコンパイルを、これらの命令群の実行が必要となる時点まで遅らせることができる。
また、頻繁に実行される命令群を、ほとんど実行されない命令群とは異なるメモリ上のページに配置することにより、実行されるコードの局所性を高める方法が提案されている（非特許文献２参照。）。
また、命令の実行頻度を計測しない場合であっても、最適化の結果ほとんど実行されないことが予め分かっている命令群については、当該命令群を除外してコンパイルする方法が提案されている（非特許文献３、非特許文献４参照。）。
また、最適化されたコンパイルコードの途中から実行時に遷移し、これに対応する別のバージョンのコードへ移行する技術として、ｏｎ−ｓｔａｃｋ  ｒｅｐｌａｃｅｍｅｎｔという手法が提案されている（非特許文献６参照。）。
また、プログラム中の分岐命令の分岐先を、実行プログラムの形態から経験的に予測する手法が提案されている（非特許文献７参照。）。
【０００３】
【非特許文献１】
Ｒ．Ｅ．Ｈａｎｋら著、「Ｒｅｇｉｏｎ−Ｂａｓｅｄ  Ｃｏｍｐｉｌａｔｉｏｎ：Ａｎ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ａｎｄ  Ｍｏｔｉｖａｔｉｏｎ」第２８回Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｍｉｃｒｏａｒｃｈｉｔｅｃｔｕｒｅ会議録、１５８から１６８ページ、１９９５年
【０００４】
【非特許文献２】
Ｋ．Ｐｅｔｔｉｓら著、「Ｐｒｏｆｉｌｅ  Ｇｕｉｄｅｄ  ＣｏｄｅＰｏｓｉｔｉｏｎｉｎｇ」ＡＣＭ  ＳＩＧＰＬＡＮ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅｓ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ会議録、１６から２７ページ、１９９０年６月
【０００５】
【非特許文献３】
Ｕ．Ｈｏｌｚｌｅ著、「Ａｄａｐｔｉｖｅ  Ｏｐｔｉｍｉｚａｔｉｏｎ  ｆｏｒ  ＳＥＬＦ：Ｒｅｃｏｎｃｉｌｉｎｇ  Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  ｗｉｔｈ  Ｅｘｐｌｏｒａｔｏｒｙ  Ｐｒｏｇｒａｍｍｉｎｇ」Ｐｈ．Ｄ  ｔｈｅｓｉｓ、Ｓｔａｎｆｏｒｄ  Ｕｎｉｖｅｒｓｉｔｙ、ＣＳ−ＴＲ−９４−１５２０、１９９４年８月
【０００６】
【非特許文献４】
Ｍ．Ｐａｌｅｃｚｎｙら著、「Ｔｈｅ  Ｊａｖａ  ＨｏｔＳｐｏｔ  Ｓｅｒｖｅｒ  Ｃｏｍｐｉｌｅｒ」ＵＳＥＮＩＸ  Ｊａｖａ  Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ  Ｒｅｓｅａｒｃｈ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ  Ｓｙｍｐｏｓｉｕｍ会議録１から１２ページ、２００１年４月
【０００７】
【非特許文献５】
Ｊ．Ｗｈａｌｅｙ著、「Ｐａｒｔｉａｌ  Ｍｅｔｈｏｄ  Ｃｏｍｐｉｌａｔｉｏｎ  ｕｓｉｎｇ  Ｄｙｎａｍｉｃ  Ｐｒｏｆｉｌｅ  Ｉｎｆｏｒｍａｔｉｏｎ」ＡＣＭ  ＳＩＧＰＬＡＮ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｏｂｊｅｃｔ−Ｏｒｉｅｎｔｅｄ  Ｐｒｏｇｒａｍｍｉｎｇ，Ｓｙｓｔｅｍｓ，Ｌａｎｇｕａｇｅｓ  ＆  Ａｐｐｌｉｃａｔｉｏｎｓ会議録、１６６から１７９ページ、２００１年１０月
【非特許文献６】
Ｕ．Ｈｏｌｚｌｅら著、「Ｄｅｂｕｇｇｉｎｇ  ＯｐｔｉｍｉｚｅｄＣｏｄｅ  ｔｈ  Ｄｙｎａｍｉｃ  Ｄｅｏｐｔｉｍｉｚａｔｉｏｎ」ＡＣＭ  ＳＩＧＰＬＡＮ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ会議録、３２から４３ページ、１９９２年６月
【非特許文献７】
Ｔ．Ｂａｌｌら著、「Ｂｒａｎｃｈ  Ｐｒｅｄｉｃｔｉｏｎ  ｆｏｒＦｒｅｅ」ＡＣＭ  ＳＩＧＰＬＡＮ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ会議録、３００から３１３ページ、１９９３年６月
【０００８】
【発明が解決しようとする課題】
非特許文献１、非特許文献２、及び非特許文献５におけるコンパイラは、コンパイル処理に先立って対象プログラムを実行し、命令の実行経路毎に実行頻度を計測する。しかしながら、この実行頻度の計測には多くの時間を要するので、対象プログラムの実行時にコンパイルを行う動的コンパイラにおいて、各命令の実行頻度を計測することは現実的でない。例えば、動的コンパイラにおいて、全ての命令の実行頻度を計測してしまうと、実際に対象プログラムの実行を開始するのが遅れてしまい、効率が悪い。また、実行に先立って予め対象プログラムをコンパイルする静的コンパイラにおいても、実行頻度の計測機能を有していない場合には、実行頻度の計測を行うことなく最適化する必要がある。
【０００９】
非特許文献３及び非特許文献４におけるコンパイラは、各命令の実行頻度の計測を行わないものの、ごく一部の限られた命令しかコンパイル対象から除外することができない。例えば、このコンパイラは、対象プログラムに本来存在する実行頻度の偏りを利用して、最適化するべき命令群を定めることはできない。
非特許文献７の技術は、実行プログラムの形態から各分岐命令の分岐先予測を経験的な確率から寄せ集めたものであるが、各命令の実行頻度の計測を行う必要はないものの、結果として予測が外れるケースが相当あり（１０％以上）、コンパイル対象から除外する命令群の決定の為には現実的に使用する事ができない。
そこで本発明は、上記の課題を解決することのできるコンパイラ装置、コンパイル方法、コンパイラプログラム、及び記録媒体を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【００１０】
【課題を解決するための手段】
即ち、本発明の第１の形態によると、コンパイル対象の対象プログラムを最適化するコンパイラ装置であって、対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象である最適化対象命令として検出する命令検出部と、検出された最適化対象命令との間で実行順序が定まっており、かつ当該最適化対象命令に先立って実行される命令の集合である最適化対象命令群を選択する命令群選択部と、最適化による最適化対象命令群の実行速度向上率が、最適化による最適化対象命令群以外の命令群以外の実行速度向上率より高くなるように対象プログラムを最適化する最適化部とを備えるコンパイラ装置、当該コンパイラ装置を用いたコンパイル方法、当該コンパイラ装置として実現されるコンパイラプログラム、当該コンパイルプログラムを記録した記録媒体を提供する。
なお上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションも又発明となりうる。
【００１１】
【発明の実施の形態】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、又実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
図１は、コンパイラ装置１０の機能ブロック図を示す。コンパイラ装置１０は、コンパイル対象の対象プログラムについて、優先して最適化するべき命令群を適切に選択することにより、コンパイル結果のプログラムの実行効率を高めると伴に、コンパイルに要する時間を減少させることを目的とする。
【００１２】
コンパイラ装置１０は、実行頻度情報計測部１００と、処理命令複製部１１０と、命令検出部１２０と、命令群選択部１３０と、最適化部１６０とを備える。実行頻度情報計測部１００は、コンパイル処理に先立って対象プログラムを実行することにより、対象プログラムに含まれる少なくとも一部の命令のそれぞれについて、当該命令の実行頻度を計測し、計測結果を命令群選択部１３０に送る。例えば、実行頻度情報計測部１００は、対象プログラムの各命令の処理内容を逐次解析するインタープリターの一部であり、解析した命令が示す処理を実行することにより実行頻度を計測する。これに代えて、実行頻度情報計測部１００は、予め他の方法で対象プログラムをコンパイルし、コンパイルされた当該対象プログラムを実行することにより実行頻度を計測してもよい。また、実行頻度情報計測部１００は、本実施形態に必須の構成要素ではなく、即ち、コンパイラ装置１０は、実行頻度情報計測部１００を備えなくともよい。実行頻度情報計測部１００により、コンパイラ装置１０は、より適切に命令群を選択することができる。
【００１３】
なお、本実施形態における対象プログラムとは、例えば、利用者により記述されたソースプログラムに対して所定の変換を行った中間表現であり、具体的には、Ｊａｖａ（登録商標）言語におけるバイトコード又はＲＴＬ（Ｒｅｇｉｓｔｅｒ  Ｔｒａｎｓｆｅｒ  Ｌａｎｇｕａｇｅ）等で記述された中間表現である。また、対象プログラムには、予め各種の最適化、例えば、メソッドインライニング等が行われていてもよい。これに代えて、対象プログラムとは、利用者により記述されたソースプログラムであってもよい。
また、命令とは、例えば、上記中間表現における処理の１単位である。これに代えて、命令とは、中間表現における命令の集合であってもよいし、ソースプログラムにおける文であってもよいし、対象プログラムを実行する装置における命令（例えば、ｉｎｓｔｒｕｃｔｉｏｎ）であってもよい。また、命令とは、少なくとも一の命令の集合であってもよい。例えば、命令とは、制御の流れが変更されることなく逐次的に実行される命令の集合である基本ブロックであってもよい。より具体的には、基本ブロックとは、先頭の命令及び終端の命令以外の命令は、分岐命令の分岐先及び分岐元の何れともならない命令の集合である。
【００１４】
処理命令複製部１１０は、対象プログラムを取得すると、所定の入力パラメータを入力として、当該入力パラメータに応じた処理を行う処理命令を検出する。そして、処理命令複製部１１０は、当該処理命令に代えて、以下の２つの命令を生成し、生成した結果の対象プログラムを命令検出部１２０に送る。まず、処理命令複製部１１０は、検出した当該処理命令と同一処理を行う命令であって、入力パラメータが予め定められた条件を満たす場合に当該処理命令より高速に実行される条件適合時命令を生成する。そして、処理命令複製部１１０は、検出した当該処理命令と同一処理を行う命令であって、入力パラメータが当該予め定められた条件を満たさない場合に実行される条件不適時処理命令を生成する。
【００１５】
一例としては、処理命令複製部１１０は、処理命令としてループ処理を検出し、当該ループ処理に代えて、入力パラメータが予め定められた条件、例えば配列変数へのアクセスが所定範囲内であるという条件を満たし高速に実行できる場合に実行される高速処理ループと、当該条件を満たさずに通常実行される通常処理ループとを生成するループバージョニング処理を行う。他の例としては、処理命令複製部１１０は、処理命令として所定のクラス内のデータを参照するクラス参照命令を検出してもよい。この場合、処理命令複製部１１０は、クラス参照命令に代えて、当該所定のクラスの格納位置が定まっている場合にクラス参照命令より高速に実行される静的参照命令と、当該格納位置が定まっていない場合に実行される通常参照命令とを生成するデバーチャライゼーション（Ｄｅｖｉｒｔｕａｌｉｚａｔｉｏｎ）処理を行ってもよい。
【００１６】
命令検出部１２０は、対象プログラムを処理命令複製部１１０から受け取ると、対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象である最適化対象命令として検出する。また、命令検出部１２０は、対象プログラムのうち予め定められた他の種類の命令を、優先して最適化する対象から除外するべき最適化除外命令として検出する。そして、命令検出部１２０は、これらの検出結果と伴に対象プログラムを命令群選択部１３０に送る。
【００１７】
命令群選択部１３０は、最適化対象命令および最適化除外命令の検出結果と伴に対象プログラムを命令検出部１２０から受け取る。そして、命令群選択部１３０は、当該最適化対象命令との間で実行順序が定まっており、かつ当該最適化対象命令に先立って実行される命令のうち、最適化除外命令として選択されていない命令の集合を、最適化対象命令群として選択する。また、命令群選択部１３０は、最適化除外命令のうち、実行頻度情報計測部１００による実行頻度が予め定めた第１頻度より高い命令を、最適化対象命令群に含める。また、命令群選択部１３０は、検出された最適化対象命令の実行頻度情報計測部１００による実行頻度が、第１頻度より低い値に予め定めた第２頻度より低い場合に、当該最適化対象命令を最適化除外命令として選択する。そして、命令群選択部１３０は、最適化対象命令群の選択結果と伴に対象プログラムを最適化部１６０に送る。
【００１８】
具体的には、命令群選択部１３０は、実行情報伝播部１４０と、分岐命令伝播部１５０とを有している。実行情報伝播部１４０は、最適化除外命令の直前に実行される命令を最適化除外命令として検出し、最適化対象命令の直前に実行される命令を最適化対象命令として検出する。また、分岐命令伝播部１５０は、分岐先の何れかの命令が最適化対象命令である分岐命令を最適化対象命令として検出し、分岐先の何れの命令も最適化対象命令でなく、かつ分岐先の何れかの命令が最適化除外命令である分岐命令を最適化除外命令として検出する。
【００１９】
そして、命令群選択部１３０は、対象プログラムのぞれぞれの命令に対して、実行情報伝播部１４０及び分岐命令伝播部１５０による処理を繰り返し適用することにより検出された最適化対象命令の集合を、最適化対象命令群として判断する。即ち、命令群選択部１３０は、命令検出部１２０により検出された最適化対象命令から実行順序を遡って順次命令を選択することにより、最適化対象命令群を選択する。
【００２０】
最適化部１６０は、命令群選択部１３０から受け取った選択結果に基づいて、最適化対象命令群が、最適化対象命令群以外の命令群より効率良く実行されるように対象プログラムを最適化し、最適化結果のプログラムを出力する。すなわち、最適化部１６０は、命令群選択部１３０から受け取った選択結果に基づいて、最適化による最適化対象命令群の実行速度向上率が、最適化による最適化対象命令群以外の命令群の実行速度向上率より高くなるように、対象プログラムを最適化する。
例えば、最適化部１６０は、対象プログラムにおける最適化対象命令群以外の最適化除外命令群を除外してコンパイルした後、当該対象プログラムを実行させる。そして、最適化部１６０は、最適化対象命令群が実行された結果最適化除外命令群の実行が必要となった旨を、例えば、実行コードに埋め込まれた命令等からの再コンパイル指示により検出した場合に、最適化除外命令群をコンパイルする。一例としては、最適化部１６０は、Ｒｅｇｉｏｎ−Ｂａｓｅｄ  Ｃｏｍｐｉｌａｔｉｏｎ技術（非特許文献１参照）及びｏｎ−ｓｔａｃｋ  ｒｅｐｌａｃｅｍｅｎｔ技術（非特許文献６参照）を用いて対象プログラムをコンパイルする。以上に示したように、対象プログラムの最適化によって、最適化対象命令群は、最適化前と比較し実行速度が向上する。一方、対象プログラムの最適化においては最適化対象命令群をより効率良く実行するように最適化するため、最適化による最適化除外命令群の実行速度の向上率は、最適化による最適化対象命令群の実行速度の向上率より低くなる。
【００２１】
このように、コンパイラ装置１０は、頻繁に実行されることが予測される命令を予め定めておき、当該命令を最適化対象命令として検出する。そして、コンパイラ装置１０は、当該最適化対象命令から実行順序を遡ることにより選択した最適化対象命令群を、他の命令群より優先して最適化する。これにより、コンパイラ装置１０は、事前に実際の実行頻度を全て計測できない場合であっても、最適化対象命令群を適切に選択することができる。
【００２２】
図２は、コンパイラ装置１０のフローチャートを示す。実行頻度情報計測部１００は、コンパイル処理に先立って対象プログラムを実行することにより、対象プログラムに含まれる少なくとも一部の命令のそれぞれについて、当該命令の実行頻度を計測する（ステップＳ２００）。以下、ステップＳ２００に代えてＳ２００と略称する。そして、処理命令複製部１１０は、入力パラメータに応じた処理を行う処理命令を検出し、当該処理命令に代えて、条件適合時命令及び条件不適時処理命令を生成する処理命令複製処理を行う（Ｓ２１０）。
【００２３】
命令検出部１２０は、対象プログラムを処理命令複製部１１０から受け取ると、対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象である最適化対象命令として検出する（Ｓ２２０）。例えば、命令検出部１２０は、対象プログラムに含まれている関数を終了させる関数終了命令（例えば、ＯＰＣ＿ＩＲＥＴＵＲＮ等のバイトコード）を、最適化対象命令として検出する。
【００２４】
また、命令検出部１２０は、対象プログラムのうち予め定められた他の種類の命令を、優先して最適化する対象から除外するべき最適化除外命令として検出する（Ｓ２３０）。そして、命令群選択部１３０は、最適化対象命令との間で実行順序が定まっており、かつ当該最適化対象命令に先立って実行される命令のうち、最適化除外命令として選択されていない命令の集合を、最適化対象命令群として選択する（Ｓ２４０）。
【００２５】
なお、実行順序が定まっているとは、例えば、所定の関数又はメソッド内での実行順序が定まっていることをいう。また、命令群選択部１３０は、ループ処理を終えてループ処理の先頭の命令に処理を戻す制御を示すバックエッジを除外して、実行順序が定まっているか否かを判断することが望ましい。即ち、命令群選択部１３０は、ループ処理のバックエッジを除外した場合に、最適化対象命令との間で実行順序が定まっており、かつ当該最適化対象命令に先立って実行される命令のうち、最適化除外命令として選択されていない命令の集合を、最適化対象命令群として選択する。
【００２６】
最適化部１６０は、最適化による最適化対象命令群の実行速度向上率が、最適化による最適化対象命令群以外の命令群の実行速度向上率より高くなるように対象プログラムを最適化し、最適化プログラムを出力して実行する（Ｓ２５０）。これにより、最適化部１６０は、最適化対象命令群が、最適化対象命令群以外の命令群より効率良く実行されるように対象プログラムを最適化することができる。
【００２７】
図３は、図２のＳ２３０におけるフローチャートを示す。対象プログラムは、予め定めた例外発生条件が満たされた場合に、当該例外発生条件の種類に応じた例外捕捉処理を実行する例外処理機能を有している。命令検出部１２０は、例外捕捉処理に処理を移行させる例外発生命令を最適化除外命令として検出する（Ｓ３００）。また、命令検出部１２０は、例外捕捉処理に含まれる何れかの命令を最適化除外命令として検出する（Ｓ３１０）。
【００２８】
例外処理機能の一例として、対象プログラムがＪａｖａ（登録商標）言語で記述されている場合には、例外処理とはエクセプション（Ｅｘｃｅｐｔｉｏｎ）処理であり、例外捕捉処理とは、例外ハンドラ（ｃａｔｃｈ節又はｆｉｎａｌｌｙ節）であり、例外発生命令とは、ｔｈｒｏｗ命令（例えば、ＯＰＣ＿ＡＴＨＲＯＷバイトコード）である。
【００２９】
命令検出部１２０は、対象プログラムにおいて、データを参照するデータ参照命令であって、データの格納位置の解析を終えていない参照位置未解決状態であるデータ参照命令を、最適化除外命令として検出する（Ｓ３２０）。データ参照命令とは、参照先のデータの格納位置を解析していない参照位置未解決状態において当該データ参照命令が実行された場合に、参照先のデータの格納位置を示す情報を含む直接参照命令に書き換えられる命令である。
【００３０】
一例として、Ｊａｖａ（登録商標）言語におけるデータ参照命令とは、クラス内のデータ又はメソッドを参照する命令である。そして、参照位置未解決状態とは、クラスの継承関係を表すクラス階層を解析して、参照するべきデータを有するクラスの格納位置を特定する前の状態である（例えば、Ｕｎｉｎｉｔｉａｌｉｚｅｄの状態又はＵｎｒｅｓｏｌｖｅｄの状態）。例えば、実行頻度情報計測部１００により既に実行されたデータ参照命令は、コンパイルを開始する前に直接参照命令に書き換えられている。従って、命令検出部１２０は、実行頻度情報計測部１００により未だ実行されておらず実行頻度の低いことが予測される命令として、参照位置未解決状態であるデータ参照命令を検出する。
続いて、命令検出部１２０は、条件不適時処理命令を、最適化除外命令として検出する（Ｓ３３０）。
【００３１】
このように、命令検出部１２０は、実行頻度の低いことが予測される予め定められた種類の命令を、優先して最適化する対象から除外する最適化除外命令として選択する。なお、予め定められた種類の命令とは、例えば、命令の処理内容を識別するオペランドコードが予め定められたコードである命令であってよい。即ち、命令検出部１２０は、命令に対する入力となるパラメータが異なっている場合であっても、オペランドコードが予め定められたコードであれば、予め定められた種類の命令と判断してもよい。
また、例外の発生は一般的に稀であるが、頻繁に例外が発生する場合もある。この場合、好ましくは、コンパイラ装置１０は、頻繁に発生する例外を解析し、最適化除外命令から除外する。
【００３２】
図４は、図２のＳ２４０におけるフローチャートを示す。図５は、図４のＳ４１０におけるフローチャートを示す。本図において対象プログラムは、本発明に係る命令の一例である基本ブロック毎に区分されており、命令群選択部１３０は、基本ブロックのそれぞれに対して以下の処理を適用する（Ｓ４００）。
【００３３】
命令群選択部１３０は、当該基本ブロック中の命令を最適化対象とするか否かの判定を行うべく、以下の処理を行う（Ｓ４１０）。命令群選択部１３０は、実行頻度情報計測部１００により実行頻度が計測されており（Ｓ５００：ＹＥＳ）、かつ計測された当該基本ブロックの実行頻度が予め定められた第１頻度以上である場合に（Ｓ５１０：ＹＥＳ）、当該基本ブロック中の各命令を最適化対象として選択する（Ｓ５２０）。一方、当該基本ブロックの実行頻度が予め定められた第１頻度に満たない場合に（Ｓ５１０：ＮＯ）、命令群選択部１３０は、当該基本ブロックの実行頻度が第１頻度より低い値に予め定められた第２頻度以下か否かを判断する（Ｓ５３０）。第２頻度以下の場合（Ｓ５３０：ＹＥＳ）、命令群選択部１３０は、当該基本ブロック中の命令を最適化対象から除外し、最適化除外命令群として選択する（Ｓ５４０）。
【００３４】
実行頻度情報計測部１００により実行頻度が計測されていない場合（Ｓ５００：ＮＯ）又は実行頻度が第２頻度より大きい場合（Ｓ５３０：ＮＯ）に、命令群選択部１３０は、当該基本ブロック中に最適化除外命令が存在するか否かを判断する（Ｓ５５０）。この処理により、コンパイラ装置１０は、実行頻度の一部が計測できた場合においては、計測した実行頻度に基づいて最適化対象を定めることができる。
【００３５】
当該基本ブロック中に最適化除外命令が存在する場合に（Ｓ５５０：ＹＥＳ）、命令群選択部１３０は、当該基本ブロック中の各命令を最適化除外命令として選択する（Ｓ５４０）。これにより、後続する基本ブロックが最適化対象であっても、当該基本ブロックを最適化対象から除外することができる。一方、当該基本ブロック中に最適化除外命令が存在しない場合に（Ｓ５５０：ＮＯ）、命令群選択部１３０は、当該基本ブロックの直後に実行される後続の基本ブロックに、最適化対象命令があるか否かを判断する（Ｓ５６０）。
【００３６】
当該基本ブロックの直後に実行される後続の基本ブロックの何れかに、最適化対象命令がある場合に（Ｓ５６０：ＹＥＳ）、命令群選択部１３０は、当該基本ブロック中の各命令を最適化対象として選択する（Ｓ５２０）。一方、当該基本ブロックの直後に実行される後続の基本ブロックの何れにおいても、最適化対象命令がない場合に（Ｓ５６０：ＮＯ）、命令群選択部１３０は、後続する各基本ブロックの設定、即ち、最適化除外命令があるか否かの設定を、当該基本ブロックに対する設定として反映する（Ｓ５７０）。命令群選択部１３０は、本図における上記処理を各基本ブロックに対して順次適用する（Ｓ４２０）。
【００３７】
命令群選択部１３０は、上記処理により、対象プログラム中の何れかの基本ブロックにおいて、当該基本ブロック中の命令を、最適化対象命令又は最適化除外命令として選択する設定が変更された場合に（Ｓ４３０：ＹＥＳ）、Ｓ４００に処理を戻す。一方、対象プログラム中の何れの基本ブロックにおいても、当該基本ブロック中の命令を、最適化対象命令又は最適化除外命令として選択する設定が変更されていない場合に（Ｓ４３０：ＮＯ）、命令群選択部１３０は、対象プログラム中の各命令を先頭から実行順序の方向に辿って解析することにより、最適化対象命令から最適化除外命令に分岐する境界分岐命令を検出する（Ｓ４４０）。即ち、検出された境界分岐命令が、最適化対象命令群から最適化除外命令群に制御を移す境界点となる。
【００３８】
続いて、命令群選択部１３０は、最適化対象命令又は最適化除外命令である旨の設定を、検出された境界分岐命令を始点として実行順序の方向に伝播させることにより（Ｓ４５０）、最適化除外命令群から最適化対象命令群に合流する合流点を検出する。これにより、命令群選択部１３０は、最適化除外命令群の終点を特定することができる。
【００３９】
このように、コンパイラ装置１０は、一の命令について、最適化対象命令又は最適化除外命令である旨の設定を、当該一の命令の直前に実行される他の命令に伝播させる。そして、コンパイラ装置１０は、設定の変更がない状態に収束するまでこの伝播処理を繰り返す。これにより、コンパイラ装置１０は、検出された最適化対象命令から実行順序を遡って順次命令を選択し、最適化対象命令群を選択することができる。また、コンパイラ装置１０は、検出された最適化除外命令から、実行順序を遡って、最適化対象として予め定められた命令を検出するまで、例えば、命令群選択部１３０により既に最適化対象命令群として選択された命令に遭遇するまで、順次命令を選択することにより、最適化除外命令群を選択することができる。
【００４０】
また、この際、コンパイラ装置１０は、予め定めた最適化対象命令と比較して、実際に実行頻度が高いと計測された命令を優先して最適化対象命令とする。これにより、実際の実行頻度の一部が計測できた場合には、計測した実行頻度を有効に利用することができる。例えば、対象プログラムの一部の関数についてのみ実行頻度が計測されており、かつ実行頻度の計測後に一の関数と他の関数を組み合わせて新たな関数とするインライン展開処理が行われていた場合には、同一の関数内であっても、実行頻度の計測された命令及び実行頻度の計測されていない命令が混在する場合がある。このような場合であっても、コンパイラ装置１０は、計測した実行頻度を有効に利用することができる。
【００４１】
図６は、図２のＳ２５０におけるフローチャートを示す。最適化部１６０は、対象プログラムにおける最適化対象命令群以外の最適化除外命令群を除外してコンパイルする（Ｓ６００）。より具体的には、最適化部１６０は、最適化対象命令から最適化除外命令に分岐する分岐命令の分岐先を、最適化除外命令の先頭の基本ブロックに代えて、最適化除外命令をコンパイルすると伴にコンパイル後の最適化除外命令に処理を移す命令を含む処理移行用基本ブロックとする。これにより、最適化部１６０は、制御フローの到達可能性判断処理を行うことにより、最適化除外命令群を到達不能として除外することができる。
【００４２】
なお、最適化部１６０は、最適化対象命令群を優先して最適化する一例として、部分インライン展開処理を行ってもよい。具体的には、最適化部１６０は、当該最適化対象命令群に対して、呼び出し側関数内の最適化対象命令群から呼び出される相手側関数内の処理を、呼び出し側最適化対象命令群に含めて実行させるインライン展開処理を行う。これにより、最適化部１６０は、関数又はメソッド全体に対しては関数の合計データサイズが大きくなりすぎる等の理由でインライン展開処理をできなかった場合であっても、インライン展開処理の対象を最適化対象命令群に限定することにより、インライン展開処理を適切に行うことができる。この結果、最適化部１６０は、頻繁に実行されることが予測される関数群のうち、より多くの関数やメソッドをインライン展開処理の対象とすることができる。
【００４３】
また、最適化部１６０は、非特許文献５記載の技術を用いてもよい。この技術によると、最適化部１６０は、最適化対象命令群にのみ最適化（例えば、部分的不要代入文削除（Ｐａｒｔｉａｌ  Ｄｅａｄ  Ｃｏｄｅ  Ｅｌｉｍｉｎａｔｉｏｎ）及び部分脱出解析（Ｐａｒｔｉａｌ  Ｅｓｃａｐｅ  Ａｎａｌｙｓｉｓ））を行うことができる。最適化除外命令群の実行が必要となった場合には、非特許文献６記載のｏｎ−ｓｔａｃｋ  ｒｅｐｌａｃｅｍｅｎｔ技術を使用して、再コンパイルした後、適切に処理を移行させることができる。
【００４４】
そして、最適化部１６０は、最適化結果の対象プログラムを出力して実行させる（Ｓ６１０）。最適化部１６０は、処理移行用基本ブロックに再コンパイルする命令を配置することで、当該最適化対象命令群が実行された結果最適化除外命令群の実行が必要となった場合に（Ｓ６３０：ＹＥＳ）、最適化除外命令が既にコンパイルされているか否かを判断する（Ｓ６４０）。未だコンパイルされていない場合に（Ｓ６４０：ＮＯ）、最適化部１６０は、最適化除外命令群をコンパイルし（Ｓ６５０）、Ｓ６１０に処理を戻すことにより、最適化除外命令群を含めた対象プログラムを実行する。これに代えて、最適化部１６０は、インタープリターにより最適化除外命令群を実行させてもよい。この場合は、処理移行用基本ブロックにインタープリターへ制御を移す命令を配置することによって実現される。最適化対象命令群が実行される過程で最適化除外命令群の実行が必要でなかった場合に（Ｓ６３０：ＮＯ）、最適化部１６０は、再コンパイルのため起動されることなく終了する。
【００４５】
このように、最適化部１６０は、最適化対象命令群のみをコンパイルすることにより、本来の対象プログラムと比べて命令数を減らすことができる。これにより、対象プログラムの実行効率を高め、実行速度を向上させることができる。更に、コンパイル対象となる命令数を減らすことができるので、コンパイルに要する時間を削減することができる。
【００４６】
なお、最適化対象命令群の実行効率及び／又は実行速度を高める最適化は、本図の例に限定されない。例えば、対象プログラムが、複数のページを有するメインメモリと、複数のページのそれぞれを利用者からアクセス可能な仮想アドレスに割り当てる仮想メモリ割当処理部とを有する装置により実行される場合には、最適化部１６０は、最適化対象命令群を、最適化対象命令群以外の命令群とは異なるページに配置することにより最適化してもよい。一例としては、コンパイラ装置１０は、非特許文献２に記載のＭｅｔｈｏｄ  Ｓｐｌｉｔｔｉｎｇ技術を用いてもよい。
【００４７】
図７は、対象プログラムの一例を示す。本図に示す対象プログラムは、Ｊａｖａ（登録商標）言語のアプリケーションプログラムで頻繁に実行されるｊａｖａ／ｕｔｉｌ／Ｖｅｃｔｏｒクラスにおける「ｅｌｅｍｅｎｔＡｔ」という名称の関数（メソッド）を有している。この関数は、所定の条件が成立したか否かを判断する２行目の命令と、当該条件が成立した場合に例外を発生させる例外発生命令である３行目の命令と、配列変数「ｅｌｅｍｅｎｔＤａｔａ［ｉｎｄｅｘ］」の値を戻り値として関数を終了させる関数終了命令である６行目の命令と、６行目の命令において例外が発生した場合に例外を捕捉する例外捕捉処理である７行目の命令と、７行目の命令において例外が捕捉された場合に更に他の例外を発生させる８行目の命令とを含む。
【００４８】
図８は、図７に示した対象プログラムの制御フローを示す。本図の制御フローは、図７の２行目に示す条件判断を行う基本ブロック６００と、基本ブロック６００における条件が成立した場合に例外を発生させる例外発生命令を含む基本ブロック６１０とを有する。更に、本図の制御フローは、図７の６行目に示す配列変数のアクセスを行う基本ブロック６２０と、図７の８行目の命令に相当し、配列変数のアクセスに伴う添字が所定範囲外である場合に実行される例外捕捉処理である基本ブロック６３０と、図７の６行目に示す関数を終了するリターン命令を含む基本ブロック６４０とを有する。
【００４９】
コンパイラ装置１０は、本図の対象プログラム全体をコンパイルしてしまうと、ほとんど実行されない基本ブロック６１０及び基本ブロック６３０の存在により、実行経路６５０の実行効率及び／又は実行速度を下げてしまう場合があり、更に、コンパイル結果の対象プログラムのコードサイズを増大させてしまう場合がある。そこで、コンパイラ装置１０は、頻繁に実行されることが予測される部分を優先して最適化するべく、以下の処理を行う。
【００５０】
命令検出部１２０は、関数を終了させる関数終了命令を、最適化対象命令として検出する。即ち、命令検出部１２０は、関数終了命令を含む基本ブロック６４０を最適化対象とする。また、命令検出部１２０は、例外発生命令及び例外捕捉処理をそれぞれ含む基本ブロック６１０および基本ブロック６３０を、最適化除外対象とする。
【００５１】
命令群選択部１３０は、当該最適化対象命令から実行順序を遡って順次命令を選択することにより、当該関数において最適化対象命令に先立って実行される命令群を最適化対象命令群として選択する。即ち、命令群選択部１３０は、基本ブロック６４０から実行順序を遡って基本ブロック６２０及び基本ブロック６００を順次選択し、基本ブロック６００、基本ブロック６２０、及び基本ブロック６４０中の各命令を最適化対象命令群として選択する。また、命令群選択部１３０は、検出された最適化除外命令から実行順序を遡って最適化対象命令群の一部に到達するまで順次命令を選択し、選択した当該命令の集合である最適化除外命令群を選択する。例えば、命令群選択部１３０は、例外発生命令から実行順序を遡って基本ブロック６００を検出するまでの間に選択した命令、即ち、基本ブロック６１０中の各命令を、最適化除外命令として選択する。
【００５２】
そして、最適化部１６０は、選択された最適化対象命令群を順次実行する実行経路６５０の最適化による実行速度向上率が、最適化対象命令群以外の命令群、即ち、基本ブロック６１０及び基本ブロック６３０の最適化による実行速度向上率より高くなるように最適化する。これにより、最適化部１６０は、選択された最適化対象命令群を順次実行する実行経路６５０を、最適化対象命令群以外の命令群、即ち、基本ブロック６１０及び基本ブロック６３０より効率良く実行されるように最適化することができる。
【００５３】
このように、コンパイラ装置１０は、実行頻度が高いことが予測されるリターン命令等を、最適化対象命令として選択し、実行頻度が低いことが予測される例外発生命令等を、最適化除外命令として検出する。そして、コンパイラ装置１０は、これらの命令に至る実行経路を、最適化対象命令群又は最適化除外命令群として選択する。これにより、コンパイラ装置１０は、対象プログラムの各実行経路について実行頻度を計測できない場合であっても、最適化するべき経路を適切に選択することができる。
【００５４】
図９は、変形例の動作を説明する図である。本図は、図８とは異なる対象プログラムの制御フローを示す。ここで、実行頻度情報計測部１００によって基本ブロック７４０中の命令の実行頻度が計測されており、この実行頻度は、予め定められた第１頻度から第２頻度の範囲内である。命令検出部１２０は、基本ブロック７５０におけるリターン命令を最適化対象命令として検出する。命令検出部１２０は、更に、対象プログラムの命令のうち予め定められた他の種類の命令、例えば、基本ブロック７４０の例外発生命令であって、実行頻度情報計測部１００による当該命令の実行頻度が第１頻度から第２頻度の範囲内である命令を、最適化対象命令より最適化を優先させず、かつ優先して最適化する対象から除外した最適化除外命令より優先させて最適化させる最適化準対象命令として検出する。更に、命令検出部１２０は、基本ブロック７３０中の条件不適時処理命令を最適化除外命令として検出する。
【００５５】
そして、命令群選択部１３０は、リターン命令から実行順序を遡ることにより順次命令を選択することにより、基本ブロック７５０中の命令を最適化対象命令群として選択する。更に、命令群選択部１３０は、最適化対象命令及び最適化準対象命令のそれぞれとの間で実行順序が定まっており、かつ最適化対象命令及び最適化準対象命令のそれぞれに先立って実行される命令群、例えば、基本ブロック７００中の命令群を、最適化対象命令群として選択する。即ち、実行経路７６０は、最適化対象命令群を順次実行する実行経路となる。
【００５６】
また、命令群選択部１３０は、最適化準対象命令との間で実行順序が定まっており、かつ最適化対象命令との間で実行順序が定まっていない命令群、例えば、基本ブロック７１０、基本ブロック７２０、及び基本ブロック７４０中の命令を、最適化準対象命令群として選択する。即ち、実行経路７７０は、最適化準対象命令群を順次実行する実行経路となる。また、命令群選択部１３０は、条件不適時処理命令から実行経路を遡って基本ブロック７１０に至るまでの命令の集合、即ち、基本ブロック７３０中の命令を最適化除外命令群として選択する。即ち、実行経路７８０は、最適化除外命令群を順次実行する実行経路となる。
そして、最適化部１６０は、最適化による最適化順対象命令群の実行速度向上率を、最適化による最適化対象命令群の実行速度向上率より低く、かつ最適化による最適化除外命令の実行速度向上率より高くなるように、対象プログラムを最適化する。これにより、最適化部１６０は、最適化準対象命令群を、最適化対象命令群より低く、かつ最適化除外命令より高い中程度の効率で実行されるように、対象プログラムを最適化する。
【００５７】
本変形例で示すように、コンパイラ装置１０は、最適化対象命令及び最適化除外命令に加えて、更に、最適化準対象命令を、命令の種類に応じて検出してもよい。これにより、コンパイラ装置１０は、対象プログラム中の各実行経路について、どの程度優先して最適化するべきかを詳細に定めることができる。
【００５８】
図１０は、コンパイラ装置１０のハードウェア構成の一例を示す。コンパイラ装置１０は、ホストコントローラ１０８２により相互に接続されるＣＰＵ１０００、ＲＡＭ１０２０、グラフィックコントローラ１０７５、及び表示装置１０８０を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホストコントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＲＯＭ１０１０、フレキシブルディスクドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。
【００５９】
ホストコントローラ１０８２は、ＲＡＭ１０２０と、高い転送レートでＲＡＭ１０２０をアクセスするＣＰＵ１０００及びグラフィックコントローラ１０７５とを接続する。ＣＰＵ１０００は、ＲＯＭ１０１０及びＲＡＭ１０２０に格納されたコンパイラプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ１０７５は、ＣＰＵ１０００等がＲＡＭ１０２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィックコントローラ１０７５は、ＣＰＵ１０００等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
【００６０】
入出力コントローラ１０８４は、ホストコントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ネットワークを介して他の装置と通信する。ハードディスクドライブ１０４０は、コンパイラ装置１０が使用するコンパイラプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からコンパイラプログラム又はデータを読み取り、ＲＡＭ１０２０を介して入出力チップ１０７０に提供する。
【００６１】
また、入出力コントローラ１０８４には、ＲＯＭ１０１０と、フレキシブルディスクドライブ１０５０や入出力チップ１０７０等の比較的低速な入出力装置とが接続される。ＲＯＭ１０１０は、コンパイラ装置１０の起動時にＣＰＵ１０００が実行するブートプログラムや、コンパイラ装置１０のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ１０５０は、フレキシブルディスク１０９０からコンパイラプログラム又はデータを読み取り、ＲＡＭ１０２０を介して入出力チップ１０７０に提供する。入出力チップ１０７０は、フレキシブルディスク１０９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
【００６２】
コンパイラ装置１０に提供されるコンパイラプログラムは、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。コンパイラプログラムは、記録媒体から読み出され、入出力チップ１０７０を介してコンパイラ装置１０にインストールされ、コンパイラ装置１０において実行される。
【００６３】
コンパイラ装置１０にインストールされて実行されるコンパイラプログラムは、実行頻度情報計測モジュールと、処理命令複製モジュールと、命令検出モジュールと、命令群選択モジュールと、実行情報伝播モジュールと、分岐命令伝播モジュールと、最適化モジュールとを含む。各モジュールがコンパイラ装置１０に働きかけて行わせる動作は、図１から図９において説明したコンパイラ装置１０における、対応する部材の動作と同一であるから、説明を省略する。
【００６４】
以上に示したコンパイラプログラム又はモジュールは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してコンパイラプログラムをコンパイラ装置１０に提供してもよい。
【００６５】
以上で示すように、コンパイラ装置１０は、頻繁に実行されることが予測される命令を予め定めておき、当該命令を最適化対象命令として検出する。そして、コンパイラ装置１０は、当該最適化対象命令から実行順序を遡ることにより選択した最適化対象命令群を、他の命令群より優先して最適化する。この結果、コンパイラ装置１０は、事前に実際の実行頻度を全て計測できない場合であっても、最適化対象命令群を適切に選択できる。これにより、コンパイラ装置１０は、実行頻度の高い部分に最適化を集中させると伴に、コンパイルに要する時間を削減することができる。
【００６６】
また、コンパイラ装置１０は、対象プログラムの少なくとも一部について、実際の実行頻度を計測することができる場合においては、計測した実行頻度に基づいて、他の部分の実行頻度を判断する。これにより、コンパイラ装置１０は、実行頻度の情報の一部であっても有効に利用することができる。
【００６７】
以上、本発明を実施形態を用いて説明したが、本発明の技術的範囲は上記実施形態に記載の範囲には限定されない。上記実施形態に、多様な変更または改良を加えることができる。そのような変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【００６８】
以上で示した全ての実施形態及び変形例によると、以下の各項目に示すコンパイラ装置、コンパイル方法、コンパイラプログラム、及び記録媒体が実現される。
【００６９】
（項目１）  コンパイル対象の対象プログラムを最適化するコンパイラ装置であって、前記対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象である最適化対象命令として検出する命令検出部と、検出された前記最適化対象命令との間で実行順序が定まっており、かつ当該最適化対象命令に先立って実行される命令の集合である最適化対象命令群を選択する命令群選択部と、最適化による前記最適化対象命令群の実行速度向上率が、最適化による前記最適化対象命令群以外の命令群の実行速度向上率より高くなるように前記対象プログラムを最適化する最適化部とを備えるコンパイラ装置。
（項目２）  前記対象プログラムは、少なくとも一の関数を含み、前記命令検出部は、前記関数を終了させる関数終了命令を、前記最適化対象命令として検出し、前記命令群選択部は、前記関数において前記最適化対象命令に先立って実行される命令群を前記最適化対象命令群として選択する項目１記載のコンパイラ装置。
（項目３）  前記命令検出部は、更に、前記対象プログラムのうち予め定められた他の種類の命令を、優先して最適化する対象から除外するべき最適化除外命令として検出し、前記命令群選択部は、前記最適化対象命令との間に実行順序が定まり、かつ前記最適化対象命令に先立って実行される命令のうち、前記最適化除外命令として選択されていない命令の集合を、前記最適化対象命令群として選択する項目１記載のコンパイラ装置。
【００７０】
（項目４）  前記対象プログラムは、予め定めた例外発生条件が満たされた場合に、当該例外発生条件の種類に応じた例外捕捉処理に移行し、前記命令検出部は、前記対象プログラムの実行時に前記例外捕捉処理に移行させる前記例外発生命令を前記最適化除外命令として検出する項目３記載のコンパイラ装置。
（項目５）  前記対象プログラムは、予め定めた例外発生条件が満たされた場合に、当該例外発生条件の種類に応じた例外捕捉処理に移行し、前記命令検出部は、前記例外捕捉処理に含まれる何れかの命令を前記最適化除外命令として検出する項目３記載のコンパイラ装置。
（項目６）  前記対象プログラムは、データを参照するデータ参照命令を有し、当該データ参照命令は、参照先のデータの格納位置を解析していない参照位置未解決状態において当該データ参照命令が実行された場合に、参照先のデータの格納位置を示す情報を含む直接参照命令に書き換えられ、前記命令検出部は、前記参照位置未解決状態の前記データ参照命令を前記最適化除外命令として検出する項目３記載のコンパイラ装置。
【００７１】
（項目７）  前記対象プログラムは、所定のパラメータを入力として、当該パラメータに応じた処理を行う処理命令を含み、前記処理命令と同一処理を行う命令であって、前記パラメータが予め定めた条件を満たす場合に前記処理命令より高速に実行される条件適合時処理命令と、前記パラメータが当該予め定めた条件を満たさない場合に実行される条件不適時処理命令とを、前記処理命令に代えて生成する処理命令複製部を更に備え、前記命令検出部は、前記条件不適時処理命令を前記最適化除外命令として検出する項目３記載のコンパイラ装置。
（項目８）  前記命令群選択部は、前記最適化除外命令の直前に実行される命令を最適化除外命令として検出し、前記最適化対象命令の直前に実行される命令を最適化対象命令として検出する実行情報伝播部と、分岐先の何れかの命令が前記最適化対象命令である分岐命令を最適化対象命令として検出し、分岐先の何れの命令も前記最適化対象命令でなく、かつ分岐先の何れかの命令が前記最適化除外命令である分岐命令を最適化除外命令として検出する分岐命令伝播部とを有し、前記対象プログラムのそれぞれの命令に対して前記実行情報伝播部及び前記分岐命令伝播部による処理を繰り返し適用することにより検出された前記最適化対象命令の集合を、前記最適化対象命令群として選択する項目３記載のコンパイラ装置。
【００７２】
（項目９）  前記対象プログラムを実行することにより、前記対象プログラムに含まれる少なくとも一部の命令のそれぞれについて、当該命令の実行頻度を計測する実行頻度情報計測部を更に備え、前記命令群選択部は、検出された前記最適化除外命令の前記実行頻度情報計測部による前記実行頻度が予め定めた第１頻度より高い場合に、当該最適化除外命令を前記最適化対象命令群として選択し、更に、検出された前記最適化対象命令の前記実行頻度情報計測部による前記実行頻度が前記第１頻度より低い値に予め定めた第２頻度より低い場合に、当該最適化対象命令を前記最適化除外命令として選択する項目３記載のコンパイラ装置。
（項目１０）  前記命令群選択部は、検出された前記最適化対象命令から実行順序を遡って順次命令を選択することにより、前記最適化対象命令群を選択し、前記最適化部は、選択された前記最適化対象命令群を順次実行する実行経路の最適化による実行速度向上率が、前記最適化対象命令群以外の命令群の最適化による実行速度向上率より高くなるように最適化する項目１記載のコンパイラ装置。
【００７３】
（項目１１）  最適化による前記最適化対象命令群の実行速度向上率を最適化による前記最適化対象命令群以外の命令群の実行速度向上率より高くなるように最適化する処理として、前記最適化部は、前記対象プログラムにおける前記最適化対象命令群以外の最適化除外命令群を除外してコンパイルした後、前記対象プログラムを実行させ、当該最適化対象命令群が実行された結果前記最適化除外命令群の実行が必要となった場合に、前記最適化除外命令群をコンパイルする項目１記載のコンパイラ装置。
（項目１２）  前記対象プログラムは、複数のページを有するメインメモリと、前記複数のページのそれぞれを利用者からアクセス可能な仮想アドレスに割り当てる仮想メモリ割当処理部とを有する装置により実行され、前記最適化部は、前記最適化対象命令群を、前記最適化対象命令群以外の命令群とは異なる前記ページに配置することにより、最適化による前記最適化対象命令群の実行速度向上率が、最適化による前記最適化対象命令群以外の命令群の実行速度向上率より高くなるように前記対象プログラムを最適化する項目１記載のコンパイラ装置。
（項目１３）  最適化による前記最適化対象命令群の実行速度向上率を最適化による前記最適化対象命令群以外の命令群の実行速度向上率より高くなるように最適化する処理として、前記最適化部は、前記対象プログラムにおける前記最適化対象命令群以外の最適化除外命令群を除外した部分において、呼び出し側関数内の最適化対象命令群から呼び出される相手側関数内の処理を、呼び出し側の最適化対象命令群に含めて実行させるインライン展開処理を行う項目１記載のコンパイラ装置。
【００７４】
（項目１４）  前記命令検出部は、更に、前記対象プログラムの命令のうち予め定められた他の種類の命令を、前記最適化対象命令より最適化を優先させず、かつ優先して最適化する対象から除外した最適化除外命令より優先させて最適化させる最適化準対象命令として検出し、前記命令群選択部は、前記最適化対象命令及び前記最適化準対象命令のそれぞれとの間で実行順序が定まっており、かつ前記最適化対象命令及び前記最適化準対象命令のそれぞれに先だって実行される命令群を、前記最適化対象命令群として選択し、前記最適化準対象命令との間で実行順序が定まっており、かつ前記最適化対象命令との間で実行順序が定まっていない命令群を、最適化準対象命令群として選択し、前記最適化部は、更に、最適化による前記最適化準対象命令群の実行速度向上率を、最適化による前記最適化対象命令群の実行速度向上率より低く、かつ最適化による前記最適化除外命令の実行速度向上率より高くなるように、前記対象プログラムを最適化する項目１記載のコンパイラ装置。
（項目１５）  前記対象プログラムを実行することにより、前記対象プログラムに含まれる少なくとも一部の命令のそれぞれについて、当該命令の実行頻度を計測する実行頻度情報計測部を更に備え、前記命令検出部は、更に、前記対象プログラムの命令のうち予め定められた他の種類の命令について、前記実行頻度情報計測部による実行頻度が予め定められた範囲内であることを更に条件として、前記最適化準対象命令として検出する項目１４記載のコンパイラ装置。
【００７５】
（項目１６）  コンパイル対象の対象プログラムを最適化するコンパイラ装置であって、前記対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象から除外するべき最適化除外命令として検出する命令検出部と、検出された前記最適化除外命令から、実行順序を遡って、最適化対象として予め定められた命令を検出するまで順次命令を選択することにより、優先して最適化する対象から除外するべき最適化除外命令群を選択する命令群選択部と、最適化による前記最適化除外命令群以外の命令群の実行速度向上率が、最適化による前記最適化除外命令群の実行速度向上率より高くなるように前記対象プログラムを最適化する最適化部とを備えるコンパイラ装置。
（項目１７）  コンパイル対象の対象プログラムを最適化するコンパイル方法であって、前記対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象である最適化対象命令として検出する命令検出段階と、検出された前記最適化対象命令との間で実行順序が定まっており、かつ当該最適化対象命令に先立って実行される命令の集合である最適化対象命令群を選択する命令群選択段階と、最適化による前記最適化対象命令群の実行速度向上率が、最適化による前記最適化対象命令群以外の命令群の実行速度向上率より高くなるように前記対象プログラムを最適化する最適化段階とを備えるコンパイル方法。
【００７６】
（項目１８）  コンパイル対象の対象プログラムを最適化するコンパイル方法であって、前記対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象から除外するべき最適化除外命令として検出する命令検出段階と、検出された前記最適化除外命令から、実行順序を遡って、最適化対象として予め定められた命令を検出するまで順次命令を選択することにより、優先して最適化する対象から除外するべき最適化除外命令群を選択する命令群選択段階と、最適化による前記最適化除外命令群以外の命令群の実行速度向上率が、最適化による前記最適化除外命令群の実行速度向上率より高くなるように前記対象プログラムを最適化する最適化段階とを備えるコンパイル方法。
（項目１９）  コンパイル対象の対象プログラムを最適化するコンパイラ装置としてコンピュータを機能させるコンパイラプログラムであって、前記コンピュータを、前記対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象である最適化対象命令として検出する命令検出部と、検出された前記最適化対象命令との間で実行順序が定まっており、かつ当該最適化対象命令に先立って実行される命令の集合である最適化対象命令群を選択する命令群選択部と、最適化による前記最適化対象命令群の実行速度向上率が、最適化による前記最適化対象命令群以外の命令群の実行速度向上率より高くなるように前記対象プログラムを最適化する最適化部として機能させるコンパイラプログラム。
【００７７】
（項目２０）  前記命令検出部は、更に、前記対象プログラムのうち予め定められた他の種類の命令を、優先して最適化する対象から除外するべき最適化除外命令として検出し、前記命令群選択部は、前記最適化対象命令との間に実行順序が定まり、かつ前記最適化対象命令に先立って実行される命令のうち、前記最適化除外命令として選択されていない命令の集合を、前記最適化対象命令群として選択する項目１９記載のコンパイラプログラム。
（項目２１）  コンパイル対象の対象プログラムを最適化するコンパイラ装置としてコンピュータを機能させるコンパイラプログラムであって、前記コンピュータを、前記対象プログラムのうち予め定められた種類の命令を、優先して最適化する対象から除外するべき最適化除外命令として検出する命令検出部と、検出された前記最適化除外命令から、実行順序を遡って、最適化対象として予め定められた命令を検出するまで順次命令を選択することにより、優先して最適化する対象から除外するべき最適化除外命令群を選択する命令群選択部と、最適化による前記最適化除外命令群以外の命令群の実行速度向上率が、最適化による前記最適化除外命令群の実行速度向上率より高くなるように前記対象プログラムを最適化する最適化部として機能させるコンパイラプログラム。
（項目２２）  項目１９から項目２１の何れかに記載のコンパイラプログラムを記録した記録媒体。
【００７８】
【発明の効果】
上記説明から明らかなように、本発明によれば優先して最適化するべき命令群を適切に選択することができる。
【図面の簡単な説明】
【図１】図１は、コンパイラ装置１０の機能ブロック図を示す。
【図２】図２は、コンパイラ装置１０のフローチャートを示す。
【図３】図３は、図２のＳ２３０におけるフローチャートを示す。
【図４】図４は、図２のＳ２４０におけるフローチャートを示す。
【図５】図５は、図４のＳ４１０におけるフローチャートを示す。
【図６】図６は、図２のＳ２５０におけるフローチャートを示す。
【図７】図７は、対象プログラムの一例を示す。
【図８】図８は、図７に示した対象プログラムの制御フローを示す。
【図９】図９は、変形例の動作を説明する図である。
【図１０】図１０は、コンパイラ装置１０のハードウェア構成の一例を示す。
【符号の説明】
１０  コンパイラ装置
１００  実行頻度情報計測部
１１０  処理命令複製部
１２０  命令検出部
１３０  命令群選択部
１４０  実行情報伝播部
１５０  分岐命令伝播部
１６０  最適化部
６００  基本ブロック
６１０  基本ブロック
６２０  基本ブロック
６３０  基本ブロック
６４０  基本ブロック
６５０  実行経路
７００  基本ブロック
７１０  基本ブロック
７２０  基本ブロック
７３０  基本ブロック
７４０  基本ブロック
７５０  基本ブロック
７６０  実行経路
７７０  実行経路
７８０  実行経路
【図１】
2004362216.tif 000003
【図２】
2004362216.tif 000004
【図３】
2004362216.tif 000005
【図４】
2004362216.tif 000006
【図５】
2004362216.tif 000007
【図６】
2004362216.tif 000008
【図７】
2004362216.tif 000009
【図８】
2004362216.tif 000010
【図９】
2004362216.tif 000011
【図１０】
2004362216.tif 000012