(57)【要約】【課題】  アーキテクチャが独自に有している命令を有効に利用する。【解決手段】  最適化対象の対象プログラムが有する複数の部分プログラムのうち、置換対象パターンに含まれる全ての命令に対応する命令を含む部分プログラムを、最適化対象の対象部分プログラムとして検出する対象部分プログラム検出部と、対象部分プログラムのうち、置換対象パターンに含まれる命令に対応する命令以外の命令、及び、置換対象パターンと異なる実行の依存関係を有する命令に対して、対象部分プログラムに含まれる命令間の依存関係を置換対象パターンに一致させる変形を行う命令列変形部と、命令列変形部により変形された対象部分プログラムを、置換対象パターンに対応して定められた置換先命令列に置換する命令列置換部とを備えるコンパイラを提供する。【選択図】図１
2005339021.tif 000002
【特許請求の範囲】
【請求項１】
最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンを検出し、検出した前記置換対象パターンを、前記置換対象パターンに対応して定められた置換先命令列に置換する最適化するコンパイラであって、
前記対象プログラムが有する複数の部分プログラムのうち、前記置換対象パターンに含まれる全ての命令に対応する命令を含む部分プログラムを、最適化対象の対象部分プログラムとして検出する対象部分プログラム検出部と、
前記対象部分プログラムのうち、前記置換対象パターンに含まれる命令に対応する命令以外の命令、及び、前記置換対象パターンと異なる実行の依存関係を有する命令に対して、前記対象部分プログラムに含まれる命令間の依存関係を前記置換対象パターンに一致させる変形を行う命令列変形部と、
前記命令列変形部により変形された前記対象部分プログラムを、前記置換対象パターンに対応して定められた置換先命令列に置換する命令列置換部と
を備えるコンパイラ。
【請求項２】
前記対象部分プログラム検出部は、各々の当該部分プログラムにおいて、前記置換対象パターンに含まれる全ての命令に対応する命令が、前記置換対象パターンにおける各命令の実行の依存関係の示す実行順序で実行される場合に、当該部分プログラムを前記対象部分プログラムとして検出する
請求項１記載のコンパイラ。
【請求項３】
前記置換対象パターンがループ処理を含む場合において、
前記対象部分プログラム検出部は、各々の当該部分プログラムについて、当該部分プログラムが、前記ループ処理に含まれる全ての命令に対応する命令をループ処理内に含み、かつ、当該部分プログラムにおけるループ処理外の全ての命令が、前記置換対象パターンが定める依存関係に従う場合に、当該部分プログラムを前記対象部分プログラムとして検出する
請求項２記載のコンパイラ。
【請求項４】
前記置換対象パターンは、前記置換対象パターンに含まれる複数の命令の各々をノードとし、前記複数の命令間の実行の依存関係を有向エッジとした依存グラフであり、
前記対象部分プログラム検出部は、各々の当該部分プログラムについて、当該部分プログラムに含まれる複数の命令の各々をノードとし、当該複数の命令の実行の依存関係を有向エッジとした依存グラフを生成し、当該依存グラフ及び前記置換対象パターンを示す依存グラフに基づいて、当該部分プログラムを前記対象部分プログラムとして検出するか否かを判断する
請求項１記載のコンパイラ。
【請求項５】
前記置換対象パターンは、命令間の制御フローを示し、
前記置換対象パターンの依存グラフは、複数の条件の何れかが満たされた場合に前記置換対象パターングラフの外部の命令に制御を移す複数分岐命令について、当該複数分岐命令から当該外部の命令に制御を移す複数の制御フローを代表する１つのエッジである代表エッジを有し、
前記対象部分プログラム検出部は、前記複数の部分プログラムの各々について、当該部分プログラムの制御フローを示す依存グラフが、当該代表エッジに対応するエッジを有する場合に、当該部分プログラムが当該複数分岐命令を含むと判断する
請求項４記載のコンパイラ。
【請求項６】
前記対象プログラムのうち、前記置換対象パターンに含まれるメモリアクセス命令とアクセス対象のデータの型が同一のメモリアクセス命令を含む部分プログラムを、最適化の候補となる部分プログラムとして検出する最適化候補検出部を更に備え、
前記対象部分プログラム検出部は、前記最適化候補検出部により検出された部分プログラムの中から、前記対象部分プログラムを検出する
請求項１記載のコンパイラ。
【請求項７】
前記対象プログラムのうち、前記置換対象パターンに含まれるループ処理と比較してループ誘導変数の増分が同一であるループ処理を含む部分プログラムを、最適化の候補となる部分プログラムとして検出する最適化候補検出部を更に備え、
前記対象部分プログラム検出部は、前記最適化候補検出部により検出された部分プログラムの中から、前記対象部分プログラムを検出する
請求項１記載のコンパイラ。
【請求項８】
前記対象プログラムのうち、予め定められた基準回数以上繰り返し処理されるループ処理を含む部分プログラムを、最適化の候補となる部分プログラムとして検出する最適化候補検出部を更に備え、
前記対象部分プログラム検出部は、前記最適化候補検出部により検出された部分プログラムの中から、前記対象部分プログラムを検出する
請求項１記載のコンパイラ。
【請求項９】
前記対象部分プログラム検出部は、前記置換対象パターンに含まれる何れの命令にも対応しない命令である余剰命令をループ処理内に含む部分プログラムを、前記対象部分プログラムとして検出し、
前記命令列変形部は、前記対象部分プログラムのループ処理内に含まれる前記余剰命令の実行結果が、ループ処理の繰り返しによらず同一であることを条件として、当該余剰命令を当該ループ処理の外で実行させ、
前記命令列置換部は、前記余剰命令を除外した前記ループ処理を、前記置換先命令列に置換する
請求項１記載のコンパイラ。
【請求項１０】
前記対象部分プログラム検出部は、前記置換対象パターンに含まれる何れの命令にも対応しない命令である余剰命令をループ処理内に含む部分プログラムを、前記対象部分プログラムとして検出し、
前記命令列変形部は、前記対象部分プログラムのループ処理を、前記余剰命令及び前記余剰命令以外の命令列を各々実行する２つのループ処理に分割し、
前記命令列置換部は、前記余剰命令以外の命令列を、前記置換先命令列に置換する
請求項１記載のコンパイラ。
【請求項１１】
前記対象部分プログラム検出部は、前記置換対象パターンにおける実行の依存関係と異なる順序で実行される命令列を含む部分プログラムを、前記対象部分プログラムとして検出し、
前記命令列変形部は、前記対象部分プログラムにおける命令の実行順序を変更しても前記対象部分プログラムの処理結果が変更されないことを条件として、前記対象部分プログラムにおける命令の実行順序を当該依存関係に基づいて変更し、
前記命令列置換部は、命令の実行順序が変更された前記対象部分プログラムを、前記置換先命令列に置換する
請求項１記載のコンパイラ。
【請求項１２】
前記対象部分プログラム検出部は、各々の当該部分プログラムにおいて、前記置換対象パターンに含まれる何れかの命令が不足する場合に、前記置換対象パターンに含まれる全ての命令に対する、当該部分プログラムにおける当該命令に対応する命令の割合が、予め定められた基準割合以上であることを条件として、当該部分プログラムを前記対象部分プログラムとして検出する
請求項１記載のコンパイラ。
【請求項１３】
前記命令列変形部は、前記置換対象パターンに含まれる全ての命令に対応する命令のうち、前記対象部分プログラムにおいて不足している不足命令を前記対象部分プログラムに追加し、前記不足命令の追加により変化する前記対象部分プログラムの処理結果を前記不足命令が未追加の場合における処理結果に戻すキャンセル命令を生成し、前記対象部分プログラム外で実行させ、
前記命令列置換部は、追加した前記不足命令を含む対象部分プログラムを、前記置換先命令列に置換する
請求項１２記載のコンパイラ。
【請求項１４】
前記命令列変形部は、前記不足命令の処理結果が格納される記憶領域の値を前記不足命令に先立って退避する退避命令と、当該記憶領域に退避した前記値を前記不足命令の実行後に復帰する復帰命令とを、前記キャンセル命令として生成し、前記対象部分プログラム外で実行させる
請求項１３記載のコンパイラ。
【請求項１５】
前記対象部分プログラム検出部は、各々の当該部分プログラムについて、前記置換対象パターンと比較して当該部分プログラムにおいて不足している命令を当該部分プログラムに追加した場合に増加する処理時間が、前記命令列変形部により前記部分プログラムが前記置換先命令列に置換された場合に短縮される処理時間より小さい場合に、当該部分プログラムを前記対象部分プログラムとして検出する
請求項１２記載のコンパイラ。
【請求項１６】
前記命令列置換部は、前記置換先命令列の構造を示す前記置換先命令テンプレートにおける各変数を、前記対象部分プログラムにおける当該変数に対応する変数に置き換えることにより、前記置換先命令列を生成する
請求項１記載コンパイラ。
【請求項１７】
前記命令列置換部は、前記対象部分プログラムが有する２以上の命令を、当該２以上の命令による処理と同一の処理を行う１つの命令に置換する
請求項１記載のコンパイラ。
【請求項１８】
前記命令列置換部は、より長い処理時間を要するアルゴリズムによる処理の命令列を、より短い処理時間を要する他のアルゴリズムによる処理の命令列に置換する
請求項１記載のコンパイラ。
【請求項１９】
最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンを検出し、検出した前記置換対象パターンを、前記置換対象パターンに対応して定められた置換先命令列に置換するコンパイラであって、
各々の当該部分プログラムにおいて、前記置換対象パターンに含まれる全ての命令に対応する命令が、前記置換対象パターンにおける各命令の実行の依存関係の示す実行順序で実行されると判断した場合に、当該部分プログラムを前記対象部分プログラムとして検出する対象部分プログラム検出部と、
前記対象部分プログラムを、前記置換対象パターンに対応して定められた置換先命令列に置換する命令列置換部と
を備えるコンパイラ。
【請求項２０】
前記置換対象パターンが命令間で循環する依存関係を定める場合において、前記対象部分プログラム検出部は、前記置換対象パターンが定める依存関係と同一でありかつ循環の位相が異なる命令列を含む部分プログラムを、前記対象部分プログラムとして検出し、
前記命令列置換部は、前記対象部分プログラムを、前記置換先命令列に置換する
請求項１９記載のコンパイラ。
【請求項２１】
最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンを検出し、検出した前記置換対象パターンを、前記置換対象命令列に対応して定められた置換先命令列に置換する、前記対象プログラムの最適化方法であって、
前記対象プログラムが有する複数の部分プログラムのうち、前記置換対象パターンに含まれる全ての命令に対応する命令を含む部分プログラムを、最適化対象の対象部分プログラムとして検出する対象部分プログラム検出段階と、
前記対象部分プログラムのうち、前記置換対象パターンに含まれる命令に対応する命令以外の命令、及び、前記置換対象パターンと異なる実行の依存関係を有する命令に対して、前記対象部分プログラムに含まれる命令間の依存関係を前記置換対象パターンに一致させる変形を行う命令列変形段階と、
前記命令列変形段階において変形された前記対象部分プログラムを、前記置換対象パターンに対応して定められた置換先命令列に置換する命令列置換段階と
を備える最適化方法。
【請求項２２】
最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンを検出し、検出した前記置換対象パターンを、前記置換対象命令列に対応して定められた置換先命令列に置換する、前記対象プログラムの最適化方法であって、
各々の当該部分プログラムにおいて、前記置換対象パターンに含まれる全ての命令に対応する命令が、前記置換対象パターンにおける各命令の実行の依存関係の示す実行順序で実行されると判断した場合に、当該部分プログラムを前記対象部分プログラムとして検出する対象部分プログラム検出段階と、
前記対象部分プログラムを、前記置換対象パターンに対応して定められた置換先命令列に置換する命令列置換段階と
を備える最適化方法。
【請求項２３】
最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンを検出し、検出した前記置換対象パターンを、前記置換対象命令列に対応して定められた置換先命令列に置換するコンパイラとして、コンピュータを機能させるコンパイラプログラムであって、
前記コンピュータを、
前記対象プログラムが有する複数の部分プログラムのうち、前記置換対象パターンに含まれる全ての命令に対応する命令を含む部分プログラムを、最適化対象の対象部分プログラムとして検出する対象部分プログラム検出部と、
前記対象部分プログラムのうち、前記置換対象パターンに含まれる命令に対応する命令以外の命令、及び、前記置換対象パターンと異なる実行の依存関係を有する命令に対して、前記対象部分プログラムに含まれる命令間の依存関係を前記置換対象パターンに一致させる変形を行う命令列変形部と、
前記命令列変形部により変形された前記対象部分プログラムを、前記置換対象パターンに対応して定められた置換先命令列に置換する命令列置換部と
して機能させるコンパイラプログラム。
【請求項２４】
最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンを検出し、検出した前記置換対象パターンを、前記置換対象命令列に対応して定められた置換先命令列に置換するコンパイラとして、コンピュータを機能させるコンパイラプログラムであって、
前記コンピュータを、
各々の当該部分プログラムにおいて、前記置換対象パターンに含まれる全ての命令に対応する命令が、前記置換対象パターンにおける各命令の実行の依存関係の示す実行順序で実行されると判断した場合に、当該部分プログラムを前記対象部分プログラムとして検出する対象部分プログラム検出部と、
前記対象部分プログラムを、前記置換対象パターンに対応して定められた置換先命令列に置換する命令列置換部と
して機能させるコンパイラプログラム。
【請求項２５】
請求項２３及び請求項２４の何れかに記載のコンパイラプログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイラ、最適化方法、コンパイラプログラム、及び記録媒体に関する。特に、本発明は、最適化可能なことが予め分かっている命令の配列パターンを、その配列パターンに対応する置換先命令列に置換するコンパイラ、最適化方法、コンパイラプログラム、及び記録媒体に関する。
【背景技術】
【０００２】
従来、最適化対象のプログラムの中から、予め定められたパターンに一致する命令列を検出し、その命令列を、そのパターンに対応して定められた他の命令列に置換する技術が提案されている。この技術によると、例えば、ある処理を実現する一連の命令群を、その処理と同一の処理結果を得る単一の命令に置換することにより、プログラムを最適化できる。置換先の命令の一例として、ＩＢＭコーポレーションのＳ／３９０アーキテクチャにおけるＴＲＴ命令が挙げられる。
【０００３】
ＴＲＴ命令は、所定の記憶領域を先頭から順次走査して、所定の条件を満たす値が格納されているアドレス等を出力する命令である（非特許文献４参照。）。図１６は、ＴＲＴ命令による処理に対応する制御フローグラフである。ＴＲＴ命令による処理は、記憶領域bytearrayの先頭から順に記憶領域に格納された値を変数chに順次読み出し、その値が条件cond1からcondNの何れかを満たす場合に終了する一連の処理に対応する。コンパイラは、このような一連の処理を、単一のＴＲＴ命令に置換することにより、プログラムを最適化できる。
【０００４】
実施例において言及する文献は以下の通りである（非特許文献１〜３参照）。
【非特許文献１】Jianghai Fu. Directed graph pattern matching and topological e mbedding.Journal of Algorithms, 22(2):372-391, February 1997.
【非特許文献２】S.S. Muchnick. Advanced compiler design and implementation, Morgan Kaufmann Publishers, Inc., 1997.
【非特許文献３】Arvind Gupta and Naomi Nishimura. Finding Largest Subtrees and Smallest Supertrees, Algorithmica, Vol. 21, No. 2, pp. 183-210, 1998
【非特許文献４】http://publibz.boulder.ibm.com/epubs/pdf/dz9zr002.pdf のページ7-180
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、最適化対象のプログラムが、予め定められたパターンと完全に一致することは稀である。このような場合、従来は最適化を諦めていた。この結果、ＴＲＴ命令等のアーキテクチャが独自に有している命令を有効に利用できない場合があった。
【０００６】
そこで本発明は、上記の課題を解決することのできるコンパイラ、最適化方法、コンパイラプログラム、及び記録媒体を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明の第１の形態においては、最適化対象の対象プログラムの中から、予め定められた複数の命令を有する置換対象パターンを検出し、検出した置換対象パターンを、置換対象命令列に対応して定められた置換先命令列に置換するコンパイラであって、対象プログラムが有する複数の部分プログラムのうち、置換対象パターンに含まれる全ての命令に対応する命令を含む部分プログラムを、最適化対象の対象部分プログラムとして検出する対象部分プログラム検出部と、対象部分プログラムのうち、置換対象パターンに含まれる命令に対応する命令以外の命令、及び、置換対象パターンと異なる実行の依存関係を有する命令に対して、対象部分プログラムに含まれる命令間の依存関係を置換対象パターンに一致させる変形を行う命令列変形部と、命令列変形部により変形された対象部分プログラムを、置換対象パターンに対応して定められた置換先命令列に置換する命令列置換部とを備えるコンパイラ、当該コンパイラを用いる最適化方法、当該コンパイラとしてコンピュータを機能させるコンパイラプログラム、及び当該コンパイラプログラムを記録した記録媒体を提供する。
【０００８】
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明の効果】
【０００９】
本発明によれば、アーキテクチャが独自に有している命令を有効に利用することができる。
【発明を実施するための最良の形態】
【００１０】
以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【００１１】
図１は、コンパイラ１０の機能ブロック図である。コンパイラ１０は、予め定められた複数の命令を有する置換対象パターンを検出し、検出したその置換対象パターンを、置換対象パターンに対応して定められた置換先命令列に置換する。置換先命令列は、置換対象パターンと比較して効率的に実行される命令列であり、一例として、アーキテクチャ独自の高速な命令を含む。即ちこれにより、最適化対象の対象プログラムを、より効率的に実行される命令列に最適化することを目的とする。
【００１２】
コンパイラ１０は、最適化候補検出部１００と、対象部分プログラム検出部１１０と、命令列変形部１２０と、命令列置換部１３０とを備える。最適化候補検出部１００は、最適化の対象となる部分プログラムの候補を検出する。例えば、最適化候補検出部１００は、対象プログラムのうち、置換対象パターンに含まれるメモリアクセス命令とアクセス対象のデータの型が同一のメモリアクセス命令を含む部分プログラムを検出する。ここで、部分プログラムとは、例えば、メソッド、関数、又は手続きと呼ばれるプログラムの処理単位であってもよいし、ループ処理等のように制御フローの性質に基づいて定まる命令列であってもよい。
【００１３】
そして、対象部分プログラム検出部１１０は、最適化候補検出部１００により検出された複数の部分プログラムのうち、置換対象パターン２０に類似する部分プログラムを対象部分プログラム４０として検出する。例えば、対象部分プログラム検出部１１０は、置換対象パターン２０に含まれる全ての命令に対応する命令を含む部分プログラムを、最適化対象の対象部分プログラム４０として検出する。より具体的には、対象部分プログラム検出部１１０は、ある２つの命令について、処理内容が互いに同一であり、その命令から出力する制御フローの数が互いに同一であり、かつ、制御フローの移行先の命令が互いに同一である場合に、それらの命令が互いに対応すると判断する。
【００１４】
命令列変形部１２０は、対象部分プログラム４０のうち、置換対象パターン２０に含まれる命令に対応する命令以外の命令、及び、置換対象パターン２０と異なる実行の依存関係を有する命令に対して、対象部分プログラム４０に含まれる命令間の依存関係を置換対象パターン２０に一致させる変形を行う。命令列変形部１２０は、必要に応じて、その他の命令に対して変形を行ってもよい。変形された対象部分プログラムを対象部分プログラム５０とする。
【００１５】
命令列置換部１３０は、命令列変形部１２０により変形された対象部分プログラム５０を、置換対象パターン２０に対応して定められた置換先命令列に置換する。例えば、コンパイラ１０は、置換先命令列の構造を示す置換先命令テンプレート３０における各変数を、その変数に対応する対象部分プログラム５０における変数に置き換えることにより、置換先命令列を生成する。その結果、コンパイラ１０は、置換先命令列を含めた対象プログラムを結果部分プログラム６０として出力する。
【００１６】
図２（ａ）は、置換対象パターン２０の具体例を示す。置換対象パターン２０は、命令Ａ、命令Ｂ、命令Ｃ、及び命令Ｄを有する。そして、置換対象パターン２０は、命令Ａ、命令Ｂ、命令Ｃ、及び命令Ｄにおける、命令間の実行の依存関係を定める。命令間の実行の依存関係とは、例えば命令間の制御フローである。この制御フローによると、命令Ａの実行後に命令Ｂが実行され、命令Ｂの実行後に命令Ｃが実行され、命令Ｃの後に命令Ｄが実行される。そして、命令Ｄの実行後に命令Ａが再度実行される。
【００１７】
これに代えて、置換対象パターン２０は、命令間の制御依存関係を定めてもよいし、データ依存関係を定めてもよい。また、置換対象パターン２０は、制御依存関係及びデータ依存関係の双方を定めた依存グラフであるPDG(Program Dependence Graph)であってもよい。即ち、置換対象パターン２０は、置換対象パターン２０に含まれる複数の命令の各々をノードとし、これら複数の命令間の実行の依存関係を有向エッジとした依存グラフであればよい。
【００１８】
図２（ｂ）は、対象部分プログラム４０の第１の例を示す。この部分プログラムは、命令Ａ、命令Ｂ、命令Ｃ、命令Ｄ、及び命令Ａを含む。従って、この部分プログラムは、置換対象パターン２０に含まれる全ての命令に対応する命令を含む。このため、対象部分プログラム検出部１１０は、この部分プログラムを対象部分プログラム４０として検出する。このように、置換対象パターン２０が、命令間で循環する依存関係を定める場合において、対象部分プログラム検出部１１０は、置換対象パターン２０が定める依存関係と同一でありかつ循環の位相が異なる命令列を対象部分プログラム４０として検出できる。
【００１９】
そしてこの場合、命令列変形部１２０が対象部分プログラム４０を変形することなく、命令列置換部１３０は、対象部分プログラム４０を置換先命令列に置換する。この例に加えて、対象部分プログラム検出部１１０は、置換対象パターン２０が定める依存関係と同一でありかつ循環の位相も同一の命令列（即ち完全に一致する命令列）を、対象部分プログラム４０として検出してもよい。この場合も同様に、命令列変形部１２０が対象部分プログラム４０を変形することなく、命令列置換部１３０は、対象部分プログラム４０を置換先命令列に置換する。
【００２０】
図２（ｃ）は、対象部分プログラム４０の第２の例を示す。この部分プログラムは、命令Ａ、命令Ｂ、命令Ｃ、及び命令Ｄを含む。従って、この部分プログラムは、置換対象パターン２０に含まれる全ての命令に対応する命令を含む。このため、対象部分プログラム検出部１１０は、この部分プログラムを対象部分プログラム４０として検出する。このように、対象部分プログラム検出部１１０は、置換対象パターン２０における実行の依存関係と異なる順序で実行される命令列を含む部分プログラムを、対象部分プログラム４０として検出できる。
【００２１】
そしてこの場合、命令列変形部１２０は、対象部分プログラム４０における命令の実行順序を変更しても対象部分プログラム４０の処理結果が変更されないことを条件として、対象部分プログラム４０における命令の実行順序をその依存関係に基づいて変更する。具体的には、命令列変形部１２０は、命令Ｂが命令Ｃの処理結果に依存しない場合には、命令Ｂ及び命令Ｃの実行順序を入れ換える。この結果対象部分プログラム５０が生成される。そして、命令列置換部１３０は、命令の実行順序が変更された対象部分プログラム５０を、置換先命令列に置換する。
【００２２】
図２（ｄ）は、対象部分プログラム４０の第３の例を示す。この部分プログラムは、命令Ａ、命令Ｂ、命令Ｃ、命令Ｄ、及び命令Ｅを含む。従って、この部分プログラムは、置換対象パターン２０に含まれる全ての命令に対応する命令を含む。従って、対象部分プログラム検出部１１０は、この部分プログラムを対象部分プログラム４０として検出する。このように、対象部分プログラム検出部１１０は、置換対象パターン２０に含まれる何れの命令にも対応しない命令である余剰命令Ｅをループ処理内に含む部分プログラムを、対象部分プログラム４０として検出できる。
【００２３】
そしてこの場合、命令列変形部１２０は、対象部分プログラム４０のループ処理内に含まれる余剰命令の実行結果が、ループ処理の繰り返しによらず同一であることを条件として、その余剰命令をそのループ処理の外で実行させる変形を行う。これに代えて、命令列変形部１２０は、対象部分プログラム４０のループ処理を、余剰命令及び余剰命令以外の命令列を各々実行する２つのループ処理に分割してもよい。ループ処理の分割についての詳細は、非特許文献２において公知であるので、説明を省略する。そして、命令列置換部１３０は、余剰命令を除外したループ処理を、置換先命令列に置換する。
【００２４】
図２は、対象部分プログラム４０の第４の例を示す。この部分プログラムは、命令Ａ、命令Ｂ、及び命令Ｄを含む。従って、この部分プログラムにおいて、置換対象パターン２０に含まれる何れかの命令（即ち命令Ｃ）が不足する。この場合、まず、対象部分プログラム検出部１１０は、置換対象パターン２０に含まれる全ての命令のうち、この部分プログラムにおいてそれらの命令に対応する命令の割合を算出する。そして、対象部分プログラム検出部１１０は、算出したその割合が、予め定められた基準割合以上であることを条件として、その部分プログラムを対象部分プログラム４０として検出する。続いて、この場合における処理を、図３を用いて説明する。
【００２５】
図３は、図２（ｅ）に対応する対象部分プログラム４０及び対象部分プログラム５０の具体例を示す。命令列変形部１２０は、置換対象パターン２０に含まれる全ての命令に対応する命令のうち、対象部分プログラム４０において不足している不足命令である命令Ｃを、対象部分プログラム４０に追加する。そして、命令列変形部１２０は、その不足命令の追加により変化する対象部分プログラム４０の処理結果をその不足命令が未追加の場合における処理結果に戻すキャンセル命令を生成する。そのキャンセル命令を命令Ｃ-1とする。なお、命令列変形部１２０は、その効果を打ち消すべく、命令Ｃの前後でそれぞれ実行される２つの命令の組を生成してもよい。これらの命令を命令Ｃ-1before及び命令Ｃ-1afterとする。
【００２６】
一例として、命令列変形部１２０は、命令Ｃの処理結果が格納される記憶領域の値を命令Ｃに先立って退避する退避命令を命令Ｃ-1beforeとして生成する。また、命令列変形部１２０は、その記憶領域の値を命令Ｃの実行後に復帰する復帰命令を命令Ｃ-1afterとして生成する。生成された対象部分プログラム５０を図３（ａ）に図示する。そして、命令列変形部１２０は、退避命令及び復帰命令を対象部分プログラム５０外で実行させる変形を行う。変形された対象部分プログラム５０を図３（ｂ）に図示する。そしてこの場合、命令列置換部１３０は、命令Ｃを含む対象部分プログラム５０を、置換先命令列に置換する。
【００２７】
なお、好ましくは、対象部分プログラム検出部１１０は、各々の部分プログラムについて、不足命令及び退避命令等をその部分プログラムに追加した場合に増加する処理時間の見積もりを算出する。そして、対象部分プログラム検出部１１０は、命令列置換部１３０によりその部分プログラムが置換先命令列に置換された場合に短縮される処理時間の見積もりを算出する。そして、対象部分プログラム検出部１１０は、増加するその処理時間が、短縮されるその処理時間より小さい場合に、その部分プログラムを対象部分プログラムとして検出する。これにより、効率化できる部分のみを最適化することができる。
【００２８】
更に他の例として、置換対象パターン２０に含まれるある比較命令と、対象部分プログラム４０に含まれる比較命令とで、比較対象の変数のみが異なる場合には、命令列変形部１２０は、対象部分プログラム４０に含まれる比較命令における、その変数との比較対象の定数を変更してもよい。例えば、置換対象パターン２０が、命令switch(ch)を含み、対象部分プログラム４０が、命令switch(ch+1)を含む場合、命令列変形部１２０は、対象部分プログラム４０におけるcase文の定数から１を減じる変形を行う。そして、命令列変形部１２０は、対象部分プログラム４０における命令switch(ch+1)を命令switch(ch)に変形する。この結果、命令列置換部１３０は、対象部分プログラム４０に含まれる命令を置換対象パターン２０に一致させることができる。
【００２９】
図４は、コンパイラ１０が対象プログラムを最適化する処理を示すフローチャートである。最適化候補検出部１００は、最適化の候補となる部分プログラムを検出する（Ｓ４００）。具体例を述べる。まず、最適化候補検出部１００は、置換対象パターン２０に含まれるメモリアクセス命令とアクセス対象のデータの型が同一のメモリアクセス命令を含む部分プログラムを、最適化の候補となる部分プログラムとして検出する。
【００３０】
例えば、最適化候補検出部１００は、置換対象パターン２０がロード命令を含む場合には部分プログラムがロード命令を含むことを条件として、その部分プログラムを最適化の候補と判断する。同様に、最適化候補検出部１００は、置換対象パターン２０がストア命令を含む場合には部分プログラムがストア命令を含むことを条件として、その部分プログラムを最適化の候補と判断する。また、アクセス対象のデータの型とは、データ表現の範囲を示す型であるbyte, int, float, 及びdoubleの他に、データの種類を示す型（配列変数、インスタンス変数、及びクラス変数）を含む。
【００３１】
また、最適化候補検出部１００は、置換対象パターン２０がループ処理を含む場合においては、ループ処理を含む部分プログラムを、最適化の候補となる部分プログラムとして検出する。ループ処理とは、例えば、プログラムを制御フローグラフとして表した場合における強連結成分に対応する命令列をいう。また、最適化候補検出部１００は、置換対象パターン２０に含まれるループ処理と比較してループ誘導変数の増分が同一であるループ処理を含むことを更に条件として、最適化の候補となる部分プログラムを検出する。
【００３２】
また、最適化候補検出部１００は、そのループ処理が、予め定められた基準回数以上繰り返し処理されることを更に条件として、最適化の候補となる部分プログラムを検出してもよい。以上の処理により、最適化を試みる範囲を絞り込むことができるので、コンパイルに要する処理時間を短縮できる。この結果、本実施例に示す技術を、実行時コンパイラ等の動的コンパイラに適用しやすくできる。
【００３３】
なお、好ましくは、最適化候補検出部１００は、利用者が所望する最適化の程度を示す最適化レベルが設定されている場合には、その最適化レベルに応じて、最適化の候補を検出する基準を変更する。例えば、最適化候補検出部１００は、より高い最適化レベルが設定されている場合には、より低い最適化レベルが設定されている場合と比較して、より多くの部分プログラムを最適化の候補として検出する。更に、利用者の設定等によっては、最適化候補検出部１００は、Ｓ４００における処理を行わなくてもよい。
【００３４】
続いて、対象部分プログラム検出部１１０は、最適化候補の部分プログラムのうち、置換対象パターン２０に含まれる全ての命令に対応する命令を含む部分プログラムを、最適化対象の対象部分プログラムとして検出する（Ｓ４１０）。置換対象パターン２０がループ処理を含む場合について、この処理の具体例を説明する。対象部分プログラム検出部１１０は、ループ処理内の命令については、命令の対応のみを判断し、依存関係の一致を判断しない。一方、対象部分プログラム検出部１１０は、ループ処理外の命令については、命令の対応のみならず、依存関係の一致をも判断する。
【００３５】
即ち、対象部分プログラム検出部１１０は、各々の部分プログラムについて、その部分プログラムが、そのループ処理に含まれる全ての命令に対応する命令をループ処理内に含み、かつその部分プログラムにおけるループ処理外の全ての命令が、置換対象パターン２０が定める依存関係に従う場合に、その部分プログラムを対象部分プログラムとして検出する。これにより、依存関係が同一で循環の位相が異なるループ等を適切に検出できる。
【００３６】
更に詳細には、まず、対象部分プログラム検出部１１０は、各々の部分プログラムについて、その部分プログラムに含まれる複数の命令の各々をノードとし、それらの複数の命令の実行の依存関係を有向エッジとした依存グラフを生成する。そして、対象部分プログラム検出部１１０は、グラフの同型性を判定するアルゴリズムにより、生成した依存グラフと、置換対象パターン２０を示す依存グラフとの同型性を判断する。
【００３７】
一例として、対象部分プログラム検出部１１０は、非特許文献１に記載のtopological embeddingの技術により、置換対象パターン２０と同型の依存グラフを検出してもよい。これに代えて、対象部分プログラム検出部１１０は、非特許文献２に記載の方法に基づき、置換対象パターン２０との共通部分が最大のプログラム片を検出することにより、置換対象パターン２０と同型の依存グラフを検出してもよい。これらの技術によると、置換対象パターン２０の依存グラフにおけるノードとノードとの間に、任意のノードが含まれている場合であっても、同型性があると判断できる。そのため、図２(ｄ)の命令列を対象部分プログラムとして検出できる。
【００３８】
また、ループ処理の依存グラフは、無限に続く木構造として取り扱う。そこで、(ｂ)については、A-＞B-＞C-＞D-＞A-＞B-＞C-＞……と判断し、同型性を見つけることができる。(c)については、ループを展開するとA-＞C-＞B-＞D-＞A-＞C-＞B-＞D-＞A……となる。このアルゴリズムは先ほど述べたようにノード間に任意のノードが含まれることを許している。そのため、先ほどの下線を引いた部分がA-＞B-＞C-＞Dと接続されているため、これもパターンと同型性があると判断される。
【００３９】
このように、対象部分プログラム検出部１１０は、各々の当該部分プログラムにおいて、置換対象パターン２０に含まれる全ての命令に対応する命令が、置換対象パターン２０における各命令の実行の依存関係の示す実行順序で実行されると判断した場合に、部分プログラムを対象部分プログラムとして検出できる。これにより、例えば、図２(b)(c)(d)の各々の命令列を、対象部分プログラムとして検出できる。
【００４０】
更に、以下に説明する方法でtopological embeddingの技術を拡張することにより、対象部分プログラム検出部１１０は、図２（ｄ）の命令列を、対象部分プログラムとして検出できる。具体的には、まず、topological embeddingのアルゴリズムにおいて、置換対象パターン２０の何れかのノードに対応するノードが部分プログラムに不足すると判断する部分を、実際のノードの不足に関わらず、当該ノードが検出されたと判断されるように変更する。
【００４１】
そして、対象部分プログラム検出部１１０は、不足するノードが検出される毎にそのノードの識別情報を記録することにより、不足するノードの集合を求める。この結果、対象部分プログラム検出部１１０は、不足するノードの集合に基づいて、置換対象パターン２０に含まれる全ての命令のうち、部分プログラムにおいてそれらの命令に対応する命令の割合を算出できる。更に、対象部分プログラム検出部１１０は、このアルゴリズムにより、図２の（ｂ）から（ｅ）に示した特徴の２つ以上を有する命令列を検出することもできる。
【００４２】
続いて、命令列変形部１２０は、対象部分プログラムのうち、置換対象パターン２０に含まれる命令に対応する命令以外の命令、及び、置換対象パターン２０と異なる実行の依存関係を有する命令に対して、対象部分プログラム４０に含まれる命令間の依存関係を置換対象パターン２０に一致させる変形を行う（Ｓ４２０）。命令列置換部１３０は、変形された対象部分プログラム５０を、置換対象パターンに対応して定められた置換先命令列に置換する（Ｓ４３０）。なお、対象部分プログラム検出部１１０により検出された全ての命令列が、置換先命令列に置換できるとは限らない。即ち、命令列変形部１２０が、対象部分プログラム４０を変形できず、命令列置換部１３０が命令列を置換できない場合もある。
続いて、コンパイラ１０が対象プログラムを入力して最適化する４つの例を順次説明する。
【００４３】
（第１例）
図５（ａ）は、第１の例における置換対象パターン２０を示す。置換対象パターン２０は、図１６に示した命令列を検出するための置換対象パターンである。図１６に示した命令列において、switch命令（２）の分岐先は、２から２５６までの数で可変である。従って、このswitch命令を適切に検出するには、２から２５６までのそれぞれの数の分岐先を有する２５５個の置換対象パターン２０を生成する必要があるとも考えられる。しかし、多くの置換対象パターン２０と部分プログラムとを比較するのには、多くの処理時間を要するので効率的でない。
【００４４】
そこで、対象部分プログラム検出部１１０は、図示する置換対象パターン２０を用いて対象部分プログラムを検出する。この置換対象パターン２０は、複数の条件の何れかが満たされた場合に置換対象パターン２０の外部の命令に制御を移す複数分岐命令（例えばswitch命令（２））について、その複数分岐命令から外部の命令に制御を移す複数の制御フローを代表する１つのエッジである代表エッジを有する。
【００４５】
そして、対象部分プログラム検出部１１０は、部分プログラムの制御フローを示す依存グラフが、その代表エッジに対応するエッジを有する場合に、その部分プログラムがその複数分岐命令を含むと判断する。即ち、対象部分プログラム検出部１１０は、置換対象パターン２０の複数分岐命令が有するエッジより、部分プログラムの複数分岐命令が有するエッジが多いことを条件として、これらの複数分岐命令が互いに対応すると判断する。
【００４６】
図５（ｂ）は、第１の例における置換先命令テンプレート３０を示す。なお、本図は、置換先命令テンプレート３０に含まれる命令による処理内容を示すプログラムソースコードを示している。実際には、置換先命令テンプレート３０は、所定の中間コード又は機械語により記述されていてもよい。
【００４７】
置換先命令テンプレート３０において、変数bytearrayは、TRT命令が比較の対象とする値を格納する記憶領域のアドレスを示す。また、変数iは、その記憶領域を走査するためのインデックスを示す。また、命令列置換部１３０は、変数bytearrayが有する値と同数の値を格納する記憶領域を確保し、その記憶領域のアドレスを変数tableに格納する。例えば、bytearrayの記憶領域におけるインデックスiの値が、ループを終了する条件を満たす場合に、tableの記憶領域におけるインデックスiの値は、非ゼロの値をとる。
【００４８】
図６は、コンパイラ１０が最適化する対象部分プログラム４０の第１の例を示す。（ａ）は、対象部分プログラム４０の処理内容を示すソースプログラムを示す。（ｂ）は、対象部分プログラム４０の制御フローグラフである。対象部分プログラム４０によると、変数dataにより定められる記憶領域を順次走査し、定数GREATERTHAN又は定数０を検出した場合に、ループ処理を終了する。また、定数０が検出された場合にはメソッドコールからリターンする。
【００４９】
本図と図５（ａ）とを比較して明らかなように、置換対象パターン２０及び対象部分プログラム４０では、記憶領域から値を読み出す命令の処理順序が異なる。具体的には、置換対象パターン２０においては命令（１）により記憶領域から値が読み出される一方、対象部分プログラム４０においては命令（ａ）及び命令（ｅ）により記憶領域から値が読み出される。従来の技術によると、変数名等の違いを考慮せずにプログラムの同型性を判断することはできるものの、命令の配置が異なる場合にプログラムの同型性を判断できない。即ち、本図の対象部分プログラム４０を、最適化対象として検出できなかった。
【００５０】
これに対して、本実施例におけるコンパイラ１０によると、図５（ａ）の命令（１）が図６（ｂ）の命令（ａ）及び命令（ｅ）に対応することが検出できる。また、図５（ａ）の命令（２）が図６（ｂ）の命令（ｂ）及び命令（ｃ）に対応することが検出できる。更に、図５（ａ）の命令（３）が図６（ｂ）の命令（ｄ）に対応することが検出できる。
【００５１】
そして、命令列変形部１２０は、命令（ｂ）及び命令（ｃ）が連続して実行され、かつ、図５（ａ）の命令（２）に変形可能である旨を検出する。更に、命令列変形部１２０は、置換対象パターン２０及び対象部分プログラム４０において変数chの依存関係が同一である旨を検出する。更に、命令列変形部１２０は、置換対象パターン２０及び対象部分プログラム４０において、記憶領域のインデックス変数についての依存関係が同一である旨を検出する。更に、命令列変形部１２０は、対象部分プログラム４０が置換対象パターン２０と比較して余剰命令を含まない旨を検出する。以上の全ての条件が充足された場合に、命令列置換部１３０は、対象部分プログラム４０を、置換対象パターン２０に基づいて置換先命令列に置換する。
【００５２】
図７は、第１の例における結果部分プログラム６０を示す。命令列置換部１３０は、置換先命令列を生成する場合に、変数tableが示す記憶領域を生成する。例えば、変数dataの記憶領域におけるインデックスiの値が、GREATERTHAN又は0である場合に、tableの記憶領域におけるインデックスiの値は、非ゼロの値をとる。そして、命令列置換部１３０は、tableの記憶領域におけるその他の値を０に初期化する。
【００５３】
なお、この処理から明らかなように、ループ処理を終了するか否かが、インデックスiの値に基づいて定まるのであれば、命令列置換部１３０は、命令列を最適化できる。従って、対象部分プログラム検出部１１０は、ある部分プログラムと置換対象パターン２０とで、switch命令の参照対象が互いに異なる場合であっても、ループ処理を終了するか否かがインデックスiの値に基づいて定まることを条件として、その部分プログラムを対象部分プログラム４０として検出してもよい。一例として、ある部分プログラムが命令switch(map1[ch])を含む場合、対象部分プログラム検出部１１０は、配列変数map1が定数配列であることを条件として、その部分プログラムを対象部分プログラム４０として検出してもよい。
【００５４】
結果部分プログラム６０による処理を説明する。結果部分プログラム６０により、コンピュータは、while命令（３）及びTRT命令（５）により、変数dataにより定まる記憶領域を２５６バイトずつ走査する。ここで、TRT命令（５）は、ループ処理を２５６回繰り返す処理と比較して極めて高速に実行できるので、変数dataにより定まる記憶領域の走査を高速化できる。一例として、その記憶領域の最初の２５６バイト以内に０又はGREATERTHANが格納されていた場合には、命令（１）から命令（９）がこの順に実行される。このためループ処理を実行しないので、極めて効率が高い。
【００５５】
以上、第1例によると、命令列置換部１３０は、while命令及びswitch命令等の２以上の命令で実現される処理を、その処理と同一の処理を行う１つの命令であるＴＲＴ命令に置換することができる。
【００５６】
なお、第1例の変形例として、置換対象パターン２０が、変数bytearrayの値がnullであるか否かを判定するnullcheck命令を含む場合が考えられる。例えば、nullcheck命令は、命令（１）が無効なアドレスから値を読み出すことを防止する目的で、命令（１）が実行される毎に、命令（１）が実行される直前で実行される場合が多い。
【００５７】
ここで、bytearrayの値は、ループの繰り返しによらず一定である。このため、nullcheck命令の実行結果は、ループの繰り返しによらず同一である。従って、このような場合には、命令列変形部１２０がnullcheck命令をループ処理の外で実行させるので、命令列置換部１３０は、nullcheck命令を除外したループ処理を、置換先命令列に置換できる。
【００５８】
（第２例）
図８は、コンパイラ１０が最適化する対象部分プログラム４０の第２の例を示す。（ａ）は、対象部分プログラム４０の処理内容を示すソースプログラムである。（ｂ）は、対象部分プログラム４０の制御フローグラフである。対象部分プログラム４０により、コンピュータは、変数bytesにより定められる記憶領域を、変数offsetが示すインデックスにより順次走査する。そして、負の値が検出された場合に、ループ処理を終了する。
【００５９】
対象部分プログラム４０において、ループ処理は、変数offset及び変数countの２つの誘導変数を有する。即ち、本図の対象部分プログラム４０と、図５（ａ）の置換対象パターン２０とでは、プログラムの構造が明らかに異なる。従って、従来のコンパイラは、対象部分プログラム４０を最適化の対象と判断することはできなかった。
【００６０】
本実施例におけるコンパイラ１０によると、対象部分プログラム検出部１１０は、部分プログラムが置換対象パターン２０と比較して余剰命令を有している場合であっても、その部分プログラムを対象部分プログラム４０として検出できる。具体的には、図５（ｂ）の命令（１）が図８（ｂ）の命令（ａ）に対応することが検出できる。また、図５（ｂ）の命令（２）が図８（ｂ）の命令（ｂ）に対応することが検出できる。更に、図５（ｂ）の命令（３）が図６（ｂ）の命令（ｃ）に対応することが検出できる。
【００６１】
そしてこの場合、命令列変形部１２０は、余剰命令を実行させる新たなループ処理を生成する。この結果、命令列置換部１３０は、対象部分プログラムにおける余剰命令以外の命令を置換先命令列に置換できる。なお、コンパイラ１０は、新たに生成されたループ処理を更に最適化してもよい。即ち例えば、コンパイラ１０は、新たに生成されたループ処理を、変数countの値を変数offsetの値から算出する処理に最適化できる。
【００６２】
図９は、第２の例における結果部分プログラム６０を示す。命令列置換部１３０は、置換先命令列を生成する場合に、変数tableが示す記憶領域を生成する。例えば、変数bytesの記憶領域におけるインデックスiの値が、負の値である場合に、tableの記憶領域におけるインデックスiの値は、非ゼロの値をとる。そして、命令列置換部１３０は、tableの記憶領域におけるその他の値を０に初期化する。
【００６３】
結果部分プログラム６０による処理を説明する。結果部分プログラム６０により、コンピュータは、while命令（３）及びTRT命令（５）により、変数bytesにより定まる記憶領域を２５６バイトずつ走査する。ここで、TRT命令（５）は、ループ処理を２５６回繰り返す処理と比較して極めて高速に実行できるので、変数bytesにより定まる記憶領域の走査を高速化できる。一例として、その記憶領域の最初の２５６バイト以内に負の値が格納されていた場合には、命令（１）から命令（９）がこの順に実行される。このためループ処理を実行しないので、極めて効率が高い。
【００６４】
（第３例）
図１０は、コンパイラ１０が最適化する対象部分プログラム４０の第３の例を示す。本図は、対象部分プログラム４０の処理内容を示すソースプログラムである。対象部分プログラム４０により、コンピュータは、変数bytesにより定められる記憶領域を、変数offsetが示すインデックスにより順次走査する。そして、負の値が検出された場合に、ループ処理を終了する。更に、このループ処理において、変数aにより定まる記憶領域を先頭から順に０で初期化する。
【００６５】
対象部分プログラム４０において、ループ処理は、変数offset及び変数countの２つの誘導変数を有する。即ち、本図の対象部分プログラム４０と、図５（ａ）の置換対象パターン２０とでは、プログラムの構造が明らかに異なる。そしてこの場合、従来のコンパイラは、対象部分プログラム４０を最適化の対象と判断することはできなかった。
【００６６】
本実施例におけるコンパイラ１０によると、対象部分プログラム検出部１１０は、部分プログラムが置換対象パターン２０と比較して余剰命令を有している場合であっても、その部分プログラムを対象部分プログラム４０として検出できる。従って、命令列変形部１２０は、対象部分プログラム４０におけるループ処理を、余剰命令及び余剰命令以外の命令列を各々実行する２つのループ処理に分割する。
【００６７】
図１１は、第３の例における結果部分プログラム６０を示す。（ａ）は、命令列置換部１３０により置換された置換先命令列を含む結果部分プログラム６０である。図９と同様に、while命令及び条件分岐命令が、TRT命令に置換される。そして、変数aにより定まる記憶領域を初期化する余剰命令は、新たに生成されたループ処理（２）及び（３）により実行される。
【００６８】
（ｂ）は、コンパイラ１０により更に最適化された結果部分プログラム６０を示す。本図に示すように、コンパイラ１０は、変数aにより定まる記憶領域を初期化するループ処理を、ＸＣ命令に最適化してもよい。ＸＣ命令によれば、所定のサイズの記憶領域を所定の値で初期化できる。ループ処理により２５６バイトの記憶領域を順次初期化する処理と比較して、ＸＣ命令は極めて高速に実行される。このため、対象プログラムを更に効果的に最適化することができる。
【００６９】
なお、ＸＣ命令は、定数オペランドにより指定されたサイズの記憶領域を初期化することができる。例えば、命令（１）は、定数である２５６バイトのサイズの記憶領域を初期化するＸＣ命令である。更に、ＩＢＭコーポレーションのＳ／３９０によるＥＸＥＣＵＴＥ命令によれば、プログラムの実行中に、定数オペランドにより指定された値を変更することができる（非特許文献４のページ７−１０８参照。）。これにより、実質的に、ＸＣ命令は、レジスタにより指定されたサイズの記憶領域を初期化できる。例えば、本図の命令（３）は、初期化する記憶領域のサイズを示す定数オペランドが、ＥＸＥＣＵＴＥ命令により変数Ｔ＿ｉｎｃｃｏｕｎｔの値に変更されたＸＣ命令を示す。
【００７０】
（第４例）
図１２は、コンパイラ１０が最適化する対象部分プログラム４０の第４の例を示す。（ａ）は、対象部分プログラム４０の処理内容を示すソースプログラムである。（ｂ）は、対象部分プログラム４０の制御フローグラフである。対象部分プログラム４０によれば、コンピュータは、変数inputに格納されたデータにおける値が１のビットの数をカウントし、変数outputに格納する。このプログラムによると、変数inputのビット数に比例して処理時間が増加するので、効率的でない。
【００７１】
図１３は、第４の例における結果部分プログラム６０を示す。命令列置換部１３０は、図１２の対象部分プログラム４０を、本図の結果部分プログラム６０に変更する。結果部分プログラム６０によると、コンピュータは、変数inputにおける値が１のビットの数を、対象部分プログラム４０と比較して高速に実行できる。このように、命令列置換部１３０は、特定の命令に置換する処理のみならず、アルゴリズムを置換する処理を行ってもよい。即ち、命令列置換部１３０は、より長い処理時間を要するアルゴリズムによる処理の命令列を、より短い処理時間を要する他のアルゴリズムによる処理の命令列に置換してもよい。
【００７２】
図１４は、本実施例の効果を説明する図である。図６に示した対象部分プログラム４０と、図７に示した結果部分プログラム６０との速度の比較を行った。本図の表は、ループ処理を終了するまでに走査するデータの数に対する、対象部分プログラム４０に対する結果部分プログラム６０の速度の向上比率である。本図においては、２５６個のデータに対する向上比率まで示しているが、２５６を超える数のデータに対しては、更に向上比率が高まることも確かめられた。
【００７３】
また、本図に示すように、平均で８以上のデータを走査する場合においては、最適化によりプログラムの実行を効率化できることが分かる。即ち例えば、コンパイラ１０は、８以上のデータを走査する可能性が高いループ処理のみを選択して最適化することにより、プログラム全体の実行効率を高めることができる。
【００７４】
図１５は、コンパイラ１０として機能するコンピュータ５００のハードウェア構成の一例を示す。コンピュータ５００は、ホストコントローラ１０８２により相互に接続されるＣＰＵ１０００、ＲＡＭ１０２０、及びグラフィックコントローラ１０７５を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホストコントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＢＩＯＳ１０１０、フレキシブルディスクドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。
【００７５】
ホストコントローラ１０８２は、ＲＡＭ１０２０と、高い転送レートでＲＡＭ１０２０をアクセスするＣＰＵ１０００及びグラフィックコントローラ１０７５とを接続する。ＣＰＵ１０００は、ＢＩＯＳ１０１０及びＲＡＭ１０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ１０７５は、ＣＰＵ１０００等がＲＡＭ１０２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィックコントローラ１０７５は、ＣＰＵ１０００等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
【００７６】
入出力コントローラ１０８４は、ホストコントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ネットワークを介して外部の装置と通信する。ハードディスクドライブ１０４０は、コンピュータ５００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からプログラム又はデータを読み取り、ＲＡＭ１０２０を介して入出力チップ１０７０に提供する。
【００７７】
また、入出力コントローラ１０８４には、ＢＩＯＳ１０１０と、フレキシブルディスクドライブ１０５０や入出力チップ１０７０等の比較的低速な入出力装置とが接続される。ＢＩＯＳ１０１０は、コンピュータ５００の起動時にＣＰＵ１０００が実行するブートプログラムや、コンピュータ５００のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ１０５０は、フレキシブルディスク１０９０からプログラム又はデータを読み取り、ＲＡＭ１０２０を介して入出力チップ１０７０に提供する。入出力チップ１０７０は、フレキシブルディスク１０９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
【００７８】
コンピュータ５００に提供されるプログラムは、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、入出力チップ１０７０及び/又は入出力コントローラ１０８４を介して、記録媒体から読み出されコンピュータ５００にインストールされて実行される。このプログラム、例えばコンパイラプログラムがコンピュータ５００に働きかけて行わせる動作は、図１から図１４において説明したコンピュータ５００における動作と同一であるから、説明を省略する。
【００７９】
以上に示したプログラムは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ５００に提供してもよい。
【００８０】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【００８１】
【図１】図1は、コンパイラ１０の機能ブロック図である。
【図２】図２は、置換対象パターン２０及び対象部分プログラム４０の具体例を示す。
【図３】図３は、図２（ｅ）に対応する対象部分プログラム４０及び対象部分プログラム５０の具体例を示す。
【図４】図４は、コンパイラ１０が対象プログラムを最適化する処理を示すフローチャートである。
【図５】図５は、置換対象パターン２０及び置換先命令テンプレート３０の第１の例を示す。
【図６】図６は、コンパイラ１０が最適化する対象部分プログラム４０の第１の例を示す。
【図７】図７は、第１の例における結果部分プログラム６０を示す。
【図８】図８は、コンパイラ１０が最適化する対象部分プログラム４０の第２の例を示す。
【図９】図９は、第２の例における結果部分プログラム６０を示す。
【図１０】図１０は、コンパイラ１０が最適化する対象部分プログラム４０の第３の例を示す。
【図１１】図１１は、第３の例における結果部分プログラム６０を示す。
【図１２】図１２は、コンパイラ１０が最適化する対象部分プログラム４０の第４の例を示す。
【図１３】図１３は、第４の例における結果部分プログラム６０を示す。
【図１４】図１４は、本実施例の効果を説明する図である。
【図１５】図１５は、コンパイラ１０として機能するコンピュータ５００のハードウェア構成の一例を示す。
【図１６】図１６は、ＴＲＴ命令による処理に対応する制御フローグラフである。
【符号の説明】
【００８２】
１０  コンパイラ
２０  置換対象パターン
３０  置換先命令テンプレート
４０  対象部分プログラム
５０  対象部分プログラム
６０  結果部分プログラム
１００  最適化候補検出部
１１０  対象部分プログラム検出部
１２０  命令列変形部
１３０  命令列置換部
【図１】
2005339021.tif 000003
【図２】
2005339021.tif 000004
【図３】
2005339021.tif 000005
【図４】
2005339021.tif 000006
【図５】
2005339021.tif 000007
【図６】
2005339021.tif 000008
【図７】
2005339021.tif 000009
【図８】
2005339021.tif 000010
【図９】
2005339021.tif 000011
【図１０】
2005339021.tif 000012
【図１１】
2005339021.tif 000013
【図１２】
2005339021.tif 000014
【図１３】
2005339021.tif 000015
【図１４】
2005339021.tif 000016
【図１５】
2005339021.tif 000017
【図１６】
2005339021.tif 000018