データ処理装置、データ処理方法、プログラム変換処理装置およびプログラム変換処理方法
【課題】実行結果の再利用による再利用区間における処理時間を短縮させる
【解決手段】履歴メモリ４３０は、関数の識別情報ごとに関数の入力値および実行結果を関連付けて実行履歴として保持する。命令デコーダ３２０は、フェッチ部３１０からの関数を予告する予告命令に含まれる関数の識別情報を実行履歴検索部４１０に供給する。また、命令デコーダ３２０は、予告命令の後に読み出される命令のうち、関数の入力値を設定する入力値設定命令に基づいて、入力選択部３３２から出力される入力値を実行履歴検索部４１０に取得させる。実行履歴検索部４１０は、関数の呼出し命令の前に、その取得された識別情報および入力値と一致する実行履歴を検索する。実行結果出力部４２０は、実行履歴検索部４１０により検出された実行結果を実行部３３０に出力する。フェッチ部３１０は、関数の次に読み出すべき命令を読み出す。
【解決手段】履歴メモリ４３０は、関数の識別情報ごとに関数の入力値および実行結果を関連付けて実行履歴として保持する。命令デコーダ３２０は、フェッチ部３１０からの関数を予告する予告命令に含まれる関数の識別情報を実行履歴検索部４１０に供給する。また、命令デコーダ３２０は、予告命令の後に読み出される命令のうち、関数の入力値を設定する入力値設定命令に基づいて、入力選択部３３２から出力される入力値を実行履歴検索部４１０に取得させる。実行履歴検索部４１０は、関数の呼出し命令の前に、その取得された識別情報および入力値と一致する実行履歴を検索する。実行結果出力部４２０は、実行履歴検索部４１０により検出された実行結果を実行部３３０に出力する。フェッチ部３１０は、関数の次に読み出すべき命令を読み出す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置に関し、特に複数回実行される命令区間の実行結果を再利用するデータ処理装置およびその処理方法、ならびに、このデータ処理装置に対応するプログラムに変換するデータ変換処理装置およびその処理方法に関する。
【背景技術】
【０００２】
従来からＣＰＵ（Central Processing Unit）などのマイクロプロセッサにおいて、演算処理の高速化技術に関する研究開発が盛んに行われている。この演算処理の高速化技術として、値再利用技術という手法が考案されている。例えば、この値再利用技術をループの命令区間に適用したデータ処理装置が提案されている（例えば、特許文献１参照。）。
この値再利用技術では、プログラムの一部分である命令区間のうち、その命令区間における入力値が同じであれば実行結果も同じとなる命令区間における入力値と、その実行結果である出力値とを関連付けて再利用表に登録する。その後、同じ命令区間を再度実行する場合に、同一の入力値が再利用表に登録されていれば、その入力値に対応する出力値を再利用表から出力することによって、過去に実行された命令区間の実行結果を再利用する。このように、複数回実行される命令区間のうち、過去に実行された命令区間の実行結果を再利用することができる命令区間をここでは再利用区間という。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第３８５５０７６号公報（図１）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述の従来技術では、再利用区間における処理が再度実行されたときに、その命令区間の入力値が再利用表に登録されていれば、その再利用区間の処理を省略することができるため、命令区間の実行に要する時間を短縮することができる。しかしながら、この場合、再利用区間の処理において入力値が使用されるまでは、その再利用区間の入力値が再利用表に登録されているか否かの判断を行うことができない。このため、入力値が使用されるまで再利用表の検索を行うことができないことから、実行結果の再利用によって短縮することができる期間が制限されてしまう。
【０００５】
本発明はこのような状況に鑑みてなされたものであり、実行結果の再利用による再利用区間の処理時間をさらに短縮させることを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、複数回実行される命令区間である再利用区間が含まれる命令列に基づく処理を実行する実行部と、上記再利用区間を識別するための識別情報ごとに上記再利用区間における入力値および実行結果を関連付けて実行履歴として保持する履歴メモリと、上記再利用区間における処理の実行を予告する予告命令に基づいて上記再利用区間の入力値を取得して上記取得された入力値と上記予告命令により特定された上記識別情報とに基づいて上記実行履歴における上記実行結果を検索する実行履歴検索部と、上記予告命令によって識別された上記再利用区間における処理が実行されるときに上記実行履歴検索部により上記実行結果が抽出された場合には上記抽出された実行結果を上記実行部に出力する実行結果出力部とを具備するデータ処理装置およびその処理方法である。これにより、再利用区間の実行前において予告命令に基づいて再利用区間の入力値を取得し、その取得された入力値と予告命令により特定された識別情報とに基づいて履歴メモリにおける実行結果を検索させて、予告命令によって識別された再利用区間における処理が実行されるときに、実行結果が抽出された場合には、その抽出された実行結果を実行部に出力させるという作用をもたらす。
【０００７】
また、この第１の側面において、上記実行履歴検索部は、上記予告命令から上記再利用区間の先頭アドレスが呼び出される呼出し命令の直前の命令までの命令群のうち上記再利用区間の入力値を設定するための入力値設定命令に基づいて入力値を取得するようにしてもよい。これにより、実行履歴検索部により、予告命令の後に続く入力値設定命令によって設定されたデータを再利用区間の入力値として取得させるという作用をもたらす。
【０００８】
また、この第１の側面において、上記実行履歴検索部は、上記取得された入力値と上記予告命令に含まれる上記識別情報とに基づいて上記実行履歴における上記実行結果を検索するようにしてもよい。これにより、実行履歴検索部により、予告命令に含まれる識別情報と、予告命令に基づいて取得された入力値とを用いて履歴メモリにおける実行結果を検索させるという作用をもたらす。
【０００９】
また、この第１の側面において、上記履歴メモリは、上記識別情報である上記再利用区間の先頭アドレスごとに上記再利用区間における入力値および実行結果を関連付けて上記実行履歴として保持し、上記実行部は、上記先頭アドレスを参照するための参照情報を含む上記予告命令に基づいて上記先頭アドレスを上記実行履歴検索部に出力し、上記実行履歴検索部は、上記識別情報として上記実行部から出力された上記先頭アドレスと上記再利用区間の入力値とに基づいて上記実行履歴における上記実行結果を検索するようにしてもよい。これにより、予告命令に含まれる参照情報に基づいて再利用区間の先頭アドレスを実行部から出力させ、その実行部から出力させた再利用区間の先頭アドレスと、予告命令に基づいて取得された入力値とを用いて履歴メモリにおける実行結果を検索させるという作用をもたらす。
【００１０】
また、この第１の側面において、上記予告命令は、上記識別情報である上記再利用区間の先頭アドレスを設定するための予告設定命令であり、上記履歴メモリは、上記再利用区間の先頭アドレスごとに上記再利用区間における入力値および実行結果を関連付けて上記実行履歴として保持し、上記実行部は、上記先頭アドレスの設定先が示された設定情報を含む上記予告設定命令に基づいて上記先頭アドレスを上記設定先に設定し、上記実行履歴検索部は、上記予告設定命令に基づいて上記再利用区間の入力値を取得して上記取得された入力値と上記実行部により設定された上記先頭アドレスとに基づいて上記実行履歴における上記実行結果を検索するようにしてもよい。これにより、実行履歴検索部により、再利用区間の先頭アドレスを設定する予告設定命令によって設定された先頭アドレスと、予告設定命令に基づいて取得された入力値とに基づいて履歴メモリにおける実行履歴を検索させるという作用をもたらす。
【００１１】
また、この第１の側面において、上記履歴メモリは、上記実行履歴を削除する際の優先度と上記優先度に対応する上記再利用区間における入力値および実行結果とを関連付けて上記実行履歴として上記識別情報ごとに保持し、上記実行履歴検索部は、上記予告命令に含まれる上記優先度に基づいて上記履歴メモリにおける上記実行履歴を削除するようにしてもよい。これにより、実行履歴検索部により、実行履歴ごとに付与された優先度に基づいて、履歴メモリにおける実行履歴を削除させるという作用をもたらす。
【００１２】
また、この第１の側面において、上記実行部は、上記実行履歴検索部により上記実行履歴における上記実行結果が上記履歴メモリから抽出されない場合には上記予告命令によって識別された上記再利用区間における処理を実行し、上記実行履歴検索部は、上記予告命令に基づいて取得された上記入力値と上記実行部により実行された実行結果と上記識別情報とを上記履歴メモリに保持させるようにしてもよい。これにより、履歴メモリから実行結果が抽出されない場合には、実行履歴検索部により、予告命令に基づいて取得された入力値と、その入力値に基づいて実行された実行結果と、識別情報とを履歴メモリに保持させるという作用をもたらす。
【００１３】
また、この第１の側面において、上記履歴メモリは、上記再利用区間である関数を識別するための上記識別情報ごとに上記関数における入力値および実行結果を関連付けて上記実行履歴として保持し、上記実行履歴検索部は、上記関数の実行を予告する予告命令に基づいて上記関数の入力値を取得して上記取得された入力値と上記予告命令により特定された上記識別情報とに基づいて上記実行履歴における上記実行結果を検索し、実行結果出力部は、上記予告命令によって識別された上記関数が実行されるときに上記実行履歴検索部により上記実行結果が抽出された場合には上記抽出された実行結果を上記実行部に出力するようにしてもよい。これにより、実行履歴検索部により、関数の実行を予告する予告命令に基づいて関数の入力値を取得して、その取得された入力値と予告命令により特定された識別情報とを用いてこれらのパラメータに関連付けられた実行結果を履歴メモリから抽出し、関数が実行されるときに、実行結果部により、その抽出された実行結果を実行部に出力させるという作用をもたらす。
【００１４】
また、本発明の第２の側面は、プログラムのうち複数回実行される命令区間の各々の実行結果が互いに一致する度合いを示す再利用度を上記命令区間の使用態様に基づいて上記命令区間ごとに生成する再利用度生成部と、上記複数の命令区間のうち上記再利用度に基づいて選択された再利用区間における入力値を設定する入力値設定命令の直前に上記再利用区間における入力値の設定を予告する予告命令を生成する予告命令生成部とを具備するプログラム変換処理装置およびその処理方法である。これにより、再利用度生成部において命令区間の使用態様に基づいて命令区間ごとの再利用度を生成し、その生成された再利用度に基づいて選択された再利用区間における入力値設定命令の直前に、予告命令生成部により再利用区間の実行を予告する予告命令を生成させるという作用をもたらす。
【００１５】
また、この第２の側面において、上記予告命令生成部は、上記再利用度に基づいて選択された複数の上記再利用区間を識別するための識別情報を含む上記予告命令を生成するようにしてもよい。これにより、上記予告命令生成部により、上記再利用度に基づいて選択された複数の再利用区間を互いに識別するための識別情報を含む予告命令を生成させるという作用をもたらす。
【００１６】
また、この第２の側面において、上記予告命令生成部は、上記再利用区間の先頭アドレスを設定するためのアドレス設定命令の後に上記先頭アドレスを参照するための参照情報を含む上記予告命令を生成するようにしてもよい。これにより、アドレス設定命令の後に、予告命令生成部により、そのアドレス設定命令により設定された再利用区間の先頭アドレスを参照するための参照情報を含む予告命令を生成させるという作用をもたらす。
【００１７】
また、この第２の側面において、上記予告命令生成部は、上記再利用区間の先頭アドレスを設定するために上記先頭アドレスの設定先が示された設定情報を含むアドレス設定命令として上記予告命令を生成するようにしてもよい。これにより、再利用区間の先頭アドレスを設定するための予告命令を生成させるという作用をもたらす。
【００１８】
また、この第２の側面において、上記予告命令生成部は、上記再利用度生成部により生成された上記再利用度に応じて付与された優先度を含む上記予告命令を生成するようにしてもよい。これにより、予告命令生成部により、履歴メモリの実行履歴を削除するための優先度を含む予告命令を生成させるという作用をもたらす。
【発明の効果】
【００１９】
本発明によれば、実行結果の再利用による再利用区間における処理時間をさらに短縮することができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００２０】
【図１】本発明の第１の実施の形態におけるデータ処理装置の一構成例を示すブロック図である。
【図２】本発明の第１の実施の形態におけるデータ処理部３００および実行結果再利用処理部４００の一構成例を示すブロック図である。
【図３】本発明の第１の実施の形態における履歴メモリ４３０のデータ構造の一例を示す概念図である。
【図４】本発明の第１の実施の形態におけるデータ処理装置１００において識別情報を含む予告命令を受け付けた場合におけるデータ処理装置１００の動作概要を示す概念図である。
【図５】本発明の第１の実施の形態におけるデータ処理装置１００により実行されるプログラムの一部を例示する図である。
【図６】予告命令の実行により関数における処理時間が短縮される例を示す概念図である。
【図７】本発明の第１の実施の形態におけるデータ処理装置１００の実行結果再利用方法の処理手順の一例を示すフローチャートである。
【図８】本発明の第２の実施の形態におけるデータ処理装置１００において参照情報を含む予告命令を受け付けた場合におけるデータ処理装置１００の動作概要を示す概念図である。
【図９】本発明の第２の実施の形態におけるデータ処理装置１００により実行されるプログラムの一部を例示する図である。
【図１０】本発明の第３の実施の形態におけるデータ処理装置１００において予告設定命令を受け付けた場合におけるデータ処理装置１００の動作概要を示す概念図である。
【図１１】本発明の第３の実施の形態におけるデータ処理装置１００により実行されるプログラムの一部を例示する図である。
【図１２】本発明の第４の実施の形態におけるプログラム変換処理装置の一機能構成例を示すブロック図である。
【図１３】本発明の第４の実施の形態におけるプログラム変換処理装置５００により生成される予告命令のデータフォーマットを例示する図である。
【図１４】本発明の第４の実施の形態におけるプログラム変換処理装置５００の予告命令生成処理方法の処理手順の一例を示すフローチャートである。
【図１５】本発明の第４の実施の形態における識別情報を含む予告命令についての予告命令処理（ステップＳ９４０）の処理手順の一例を示すフローチャートである。
【図１６】本発明の第４の実施の形態における参照情報を含む予告命令についての予告命令処理（ステップＳ９５０）の処理手順の一例を示すフローチャートである。
【図１７】本発明の第４の実施の形態における予告設定命令についての予告命令処理（ステップＳ９６０）の処理手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（データ処理制御：識別情報を含む予告命令による実行結果の再利用処理の例）
２．第２の実施の形態（データ処理制御：参照情報を含む予告命令による実行結果の再利用処理の例）
３．第３の実施の形態（データ処理制御：予告設定命令による実行結果の再利用処理の例）
４．第４の実施の形態（プログラム変換制御：予告命令を含むプログラムの生成例）
【００２２】
＜１．第１の実施の形態＞
［データ処理装置の構成例］
図１は、本発明の第１の実施の形態におけるデータ処理装置の一構成例を示すブロック図である。ここでは、集積回路を構成するデータ処理装置１００と、バス１２０と、主記憶部１３０とが示されている。この集積回路は、主記憶部１３０からバス１２０を介して読み出される命令列に従って、データ処理装置１００により処理を実行するものである。
【００２３】
データ処理装置１００は、一次キャッシュ２００と、データ処理部３００と、実行結果再利用処理部４００とを備える。なお、データ処理装置１００は、特許請求の範囲に記載のデータ処理装置の一例である。一次キャッシュ２００は、バス１２０を介して主記憶部１３０から命令およびデータを読み出す際、または、書き込む際の処理によって生じる遅延時間を軽減するためのメモリである。この一次キャッシュ２００は、例えば、ＤＲＡＭ（Dynamic Random Access Memory）により実現される。
【００２４】
この一次キャッシュ２００は、命令キャッシュ２１０およびデータキャッシュ２２０を備える。命令キャッシュ２１０は、主記憶部１３０から読み出された過去の命令を一時的に保持するものである。この命令キャッシュ２１０は、データ処理部３００からの要求に従って、その保持された命令を、命令線２１９を介してデータ処理部３００に出力する。
【００２５】
また、この命令キャッシュ２１０は、データ処理部３００から要求された命令を保持している場合には、その保持している複数の命令のうち、その要求された命令をデータ処理部３００に出力する。一方、データ処理部３００から要求された命令を保持していない場合には、命令キャッシュ２１０は、データ処理部３００により主記憶部１３０から読み出された命令を保持するとともにデータ処理部３００に出力する。
【００２６】
データキャッシュ２２０は、主記憶部１３０から読み出された過去のデータを一時的に保持するものである。このデータキャッシュ２２０は、データ処理部３００からの要求に従って、その保持されたデータを、データ線２２９を介してデータ処理部３００に出力する。また、このデータキャッシュ２２０は、データ処理部３００から要求されたデータを保持している場合には、保持している複数のデータのうち、その要求されたデータをデータ処理部３００に出力する。
【００２７】
一方、データ処理部３００から要求されたデータを保持していない場合には、データキャッシュ２２０は、データ処理部３００により主記憶部１３０から読み出されたデータを保持する。また、データキャッシュ２２０は、主記憶部１３０に書き戻すためのデータがデータ処理部３００から供給された場合には、そのデータを保持する。
【００２８】
データ処理部３００は、主記憶部１３０から読み出された命令に基づく処理を実行するものである。このデータ処理部３００は、例えば、命令キャッシュ２１０を介して主記憶部１３０から命令を読み出して、その読み出された命令に従って、主記憶部１３０に記憶されたデータを、データキャッシュ２２０を介して読み出す。そして、データ処理部３００は、例えば、その読み出されたデータを用いて演算命令に基づく演算処理を実行する。
【００２９】
また、データ処理部３００は、例えば、関数の処理を実行する場合には、データキャッシュ２２０から読み出された関数における引数の入力値を用いて関数の演算処理を実行して、その演算処理の結果である実行結果をデータキャッシュ２２０に出力する。このとき、データ処理部３００は、関数における入力値および実行結果を実行結果再利用処理部４００に出力する。また、このデータ処理部３００は、例えば、プロセッサコアにより実現される。
【００３０】
実行結果再利用処理部４００は、過去に実行された命令区間の入力値と、再び実行される命令区間の入力値とが一致した場合には、その過去に実行された命令区間の実行結果を再利用するものである。ここでは、複数回実行される命令区間のうち、過去に実行された命令区間の実行結果を再利用することができる命令区間を再利用区間という。すなわち、この再利用区間とは、複数回実行される命令区間のうち、命令区間における入力値が同じであれば実行結果も同じとなる命令区間のことである。
【００３１】
この実行結果再利用処理部４００は、複数回実行される再利用区間における入力値および実行結果を実行履歴として保持する。また、この実行結果再利用処理部４００は、再び実行される再利用区間の入力値と、その保持された実行履歴の入力値とが同一である場合には、その保持された実行履歴における実行結果をデータ処理部３００に出力する。これとともに、実行結果再利用処理部４００は、その再利用区間における処理をスキップするための指示をデータ処理部３００に通知する。
【００３２】
実行結果再利用処理部４００は、例えば、再利用区間である関数の引数の入力値と、その保持された実行履歴における入力値とが同一である場合には、その保持された実行履歴における実行結果をデータ処理部３００に出力する。これとともに、実行結果再利用処理部４００は、その関数における処理をスキップするための指示をデータ処理部３００に通知する。
【００３３】
バス１２０は、データ処理装置１００と主記憶部１３０との間の通信を行うものである。このバス１２０は、主記憶部１３０に記憶されているプログラムをデータ処理装置１００に転送する。また、このバス１２０は、データ処理装置１００から出力されたデータを主記憶部１３０に転送する。
【００３４】
主記憶部１３０は、データ処理装置１００に処理を実行させるためのプログラムを記憶するものである。ここでは、このプログラムは、ＡＢＩ（Application Binary Interface）の規定に基づいて生成されたプログラムを想定する。このプログラムは、例えば、ＳＰＡＲＣ（Scalable Processor Architecture） ＡＢＩに基づいて生成されるものである。これにより、データ処理装置１００において、関数における入力値および実行結果が格納される場所を特定することができるため、実行結果の再利用を実現することができる。また、この主記憶部１３０に記憶されているプログラムには、再利用区間である関数が実行される前に、関数における処理の実行を予告する予告命令が挿入されている。
【００３５】
［データ処理部３００および実行結果再利用処理部４００の構成例］
図２は、本発明の第１の実施の形態におけるデータ処理部３００および実行結果再利用処理部４００の一構成例を示すブロック図である。ここでは、主記憶部１３０に予告命令が挿入されたプログラムが記憶されていることを想定している。
【００３６】
データ処理部３００は、フェッチ部３１０と、命令デコーダ３２０と、実行部３３０と、レジスタファイル３４０とを備える。この実行部３３０は、ロードユニット３３１と、入力選択部３３２と、演算回路３３３と、ストアユニット３３４とを備える。また、実行結果再利用処理部４００は、実行履歴検索部４１０と、実行結果出力部４２０と、履歴メモリ４３０とを備える。
【００３７】
フェッチ部３１０は、命令キャッシュ２１０に保持された命令、または、主記憶部１３０に記憶されている命令を、命令線２１９を介して読み出すものである。このフェッチ部３１０は、プログラムカウンタからの指示に従って、命令キャッシュ２１０から命令を読み出す。
【００３８】
また、フェッチ部３１０は、例えば、再利用区間である関数の呼出し命令の実行を予告する予告命令を読み出した後に、その関数における引数の入力値を設定するための入力値設定命令を読み出す。そして、その入力値設定命令の後に、フェッチ部３１０は、その関数を呼び出す呼出し命令を読み出す。すなわち、フェッチ部３１０は、再利用区間である関数の呼出し命令を読み出す前に、その関数に対応する予告命令および入力値設定命令を読み出す。
【００３９】
また、フェッチ部３１０は、その読み出された命令を命令デコーダ３２０に供給する。また、実行履歴検索部４１０により実行結果が抽出された場合には、フェッチ部３１０は、例えば、実行結果を設定するための命令を、実行履歴検索部４１０からの通知に基づいて命令デコーダ３２０に供給する。
【００４０】
命令デコーダ３２０は、フェッチ部３１０から供給された命令を解読（デコード）して、その解読内容に基づいて、実行部３３０、レジスタファイル３４０および実行履歴検索部４１０を制御するものである。この命令デコーダ３２０は、関数の実行を予告する予告命令を受け付けた場合には、その予告命令により特定される識別情報を実行履歴検索部４１０に供給する。ここにいう識別情報とは、複数の再利用区間である関数を互いに識別するための情報であり、履歴メモリ４３０に保持された実行履歴を検索するための検索キーとして用いられるものである。すなわち、命令デコーダ３２０は、予告命令によって、予告命令により特定される再利用区間である関数を実行する前に、その関数を識別するための識別情報を実行履歴検索部４１０に保持される。
【００４１】
命令デコーダ３２０は、例えば、識別情報を含む予告命令を受け付けたときは、その識別情報を履歴メモリ４３０に入力させるために、その識別情報を実行履歴検索部４１０に供給する。また、その識別情報として関数の先頭アドレスを用いる場合において、レジスタファイル３４０に関数の先頭アドレスが既に格納されているときは、命令デコーダ３２０は、その関数の先頭アドレスを参照するための参照情報を含む予告命令により識別情報を特定する。
【００４２】
このとき、命令デコーダ３２０は、その予告命令に含まれる参照情報に基づいて、レジスタファイル３４０に格納された関数の先頭アドレスを実行履歴検索部４１０に出力させる。すなわち、命令デコーダ３２０は、実行部３３０に対し、参照情報を含む予告命令に基づいて、識別情報である関数の先頭アドレスを実行履歴検索部４１０に出力させる。
【００４３】
また、識別情報として関数の先頭アドレスを用いる場合において、関数の先頭アドレスをレジスタファイル３４０に設定するためのアドレス設定命令を予告命令とするときは、命令デコーダ３２０は、その予告命令に含まれる設定情報に基づいて識別情報を特定する。
【００４４】
このとき、命令デコーダ３２０は、入力選択部３３２を介して、その予告命令に指定された設定情報が示すレジスタファイル３４０における設定先に、関数の先頭アドレスを設定する。これとともに、命令デコーダ３２０は、入力選択部３３２から出力される関数の先頭アドレスを取得するように実行履歴検索部４１０に指示する。このようなアドレス設定命令である予告命令を、ここでは予告設定命令という。したがって、命令デコーダ３２０は、実行部３３０に対し、関数の先頭アドレスの設定先が示された設定情報を含む予告設定命令に基づいて、識別情報である関数の先頭アドレスを設定先に設定させるとともに、実行履歴検索部４１０に出力させる。
【００４５】
また、命令デコーダ３２０は、関数の実行を予告する予告命令の後に受け付けた命令が、関数における引数の入力値を設定するための入力値設定命令であるか否かを判断する。この命令デコーダ３２０は、例えば、ＡＢＩの規定に基づいて入力値設定命令であるか否かを判断する。
【００４６】
この例において、ＭＩＰＳ（Microprocessor without Interlocked Pipeline Stages）のＡＢＩの規定に基づく判断例について簡単に説明する。ＭＩＰＳの規定では、引数の入力値が全て整数である場合には、４つのレジスタ４乃至７に入力値が格納され、引数が５つ以上のときには、５つ目以上の引数の入力値が主記憶部１３０のスタック領域にスタックされる。具体的には、５つ目以上の引数の入力値は、レジスタファイル３４０におけるレジスタ２９に格納されたスタックポイント値に１６以上の値を加算した値に対応するスタック領域にスタックされる。
【００４７】
したがって、命令デコーダ３２０は、例えば、ロードワード命令（ｌｗ）に示された転送先レジスタがレジスタ４乃至７である場合には、関数における引数の入力値を設定する入力値設定命令と判断する。また、命令デコーダ３２０は、引数が５以上であり、その引数の全ての入力値が整数である場合において、ストアワード命令（ｓｗ）に示された転送先レジスタがレジスタ２９であり、かつ、オフセット値が「１６」以上を示すときは、入力値設定命令と判断する。
【００４８】
そして、入力値設定命令と判断された場合には、命令デコーダ３２０は、入力選択部３３２から出力されるデータを引数の入力値として取得させるための取得信号を実行履歴検索部４１０に供給する。すなわち、命令デコーダ３２０は、予告命令から、関数を呼び出すための呼出し命令の直前の命令までの命令群のうち、関数の入力値を設定するための入力値設定命令に基づいて、引数の入力値を実行履歴検索部４１０に取得させるように制御する。
【００４９】
また、この命令デコーダ３２０は、例えば、主記憶部１３０から読み出された関数の入力値を設定するための入力値設定命令を受け付けた場合には、ロードユニット３３１から読み出された入力値をレジスタファイル３４０に格納するように制御する。これとともに、命令デコーダ３２０は、実行履歴検索部４１０に対し取得信号を供給する。
【００５０】
また、命令デコーダ３２０は、例えば、レジスタファイル３４０に格納された関数の入力値を設定するための入力値設定命令を受け付けた場合には、レジスタファイル３４０における１つのレジスタに格納された入力値を他のレジスタに転送するように制御する。これとともに、命令デコーダ３２０は、実行履歴検索部４１０に対し取得信号を供給する。
【００５１】
そして、命令デコーダ３２０は、入力値設定命令の後に、関数の先頭アドレスを呼び出すための呼出し命令を受け付けた場合には、関数に用いられる全ての入力値の設定が終了した旨を示す入力値終了信号を実行履歴検索部４１０に供給する。すなわち、この命令デコーダ３２０は、識別情報に対応する関数を呼び出すための呼出し命令を受け付けた場合には、入力値終了信号を実行履歴検索部４１０に供給する。また、命令デコーダ３２０は、実行履歴を削除する際の優先度が予告命令に含まれる場合には、その優先度を実行履歴検索部４１０に供給する。
【００５２】
実行部３３０は、命令デコーダ３２０からの制御に従って処理を実行するものである。すなわち、この実行部３３０は、複数回実行される命令区間である再利用区間が含まれる命令列に基づく処理を実行する。また、実行部３３０は、例えば、参照情報を含む予告命令が命令デコーダ３２０に供給された場合には、参照情報に示されたレジスタに格納された関数の先頭アドレスを識別情報として実行履歴検索部４１０に出力する。
【００５３】
また、実行部３３０は、例えば、予告設定命令が命令デコーダ３２０に供給された場合には、予告設定命令に含まれる関数の先頭アドレスの設定先を示す設定情報に基づいて、関数の先頭アドレスを設定先に設定する。すなわち、実行部３３０は、予告設定命令の設定情報に基づいて関数の先頭アドレスをレジスタファイル３４０に設定するとともに、関数の先頭アドレスを識別情報として実行履歴検索部４１０に出力する。
【００５４】
また、この実行部３３０は、再利用区間である関数の入力値および実行結果をレジスタファイル３４０または主記憶部１３０に出力するとともに、実行履歴検索部４１０に供給する。なお、実行部３３０は、特許請求の範囲に記載の実行部の一例である。
【００５５】
ロードユニット３３１は、命令デコーダ３２０からの制御に従って、主記憶部１３０またはデータキャッシュ２２０からデータを読み出して、その読み出されたデータを入力選択部３３２に供給するものである。このロードユニット３３１は、例えば、命令デコーダ３２０からの制御に従って、主記憶部１３０またはデータキャッシュ２２０から関数における引数の入力値を読み出して、その読み出された入力値を入力選択部３３２に供給する。
【００５６】
入力選択部３３２は、命令デコーダ３２０からの制御に従って、実行結果出力部４２０、演算回路３３３、レジスタファイル３４０および実行結果出力部４２０から出力されたデータのうち、いずれか１つのデータを選択するものである。この入力選択部３３２は、その選択されたデータを、レジスタファイル３４０および実行履歴検索部４１０に出力する。すなわち、入力選択部３３２は、命令デコーダ３２０の制御に従って、実行結果出力部４２０、演算回路３３３、レジスタファイル３４０および実行結果出力部４２０の出力のうち、いずれかをレジスタファイル３４０および実行履歴検索部４１０に出力する。
【００５７】
この入力選択部３３２は、例えば、命令デコーダ３２０に入力値設定命令としてロード命令が供給された場合には、命令デコーダ３２０の制御に従って、ロードユニット３３１からのデータを、レジスタファイル３４０および実行履歴検索部４１０に出力する。また、この入力選択部３３２は、命令デコーダ３２０に入力値設定命令としてムーブ命令が供給された場合には、命令デコーダ３２０の制御に従って、レジスタファイル３４０から出力されたデータを、レジスタファイル３４０および実行履歴検索部４１０に出力する。
【００５８】
また、入力選択部３３２は、演算処理を実行するための演算命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０の制御に従って、演算回路３３３から出力された演算結果を実行結果として、レジスタファイル３４０に出力する。また、この入力選択部３３２は、実行履歴検索部４１０により実行結果が抽出された場合には、命令デコーダ３２０からの制御に従って、実行結果出力部４２０から出力された実行結果をレジスタファイル３４０に出力する。
【００５９】
演算回路３３３は、命令デコーダ３２０からの制御に従って、演算処理を実行するものである。この演算回路３３３は、例えば、乗算、除算または積和などの演算処理を実行するための演算命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０の制御に従って、レジスタファイル３４０に格納されたデータを用いて演算処理を実行する。また、演算回路３３３は、その演算処理による演算結果を実行結果として、入力選択部３３２を介してレジスタファイル３４０に格納する。
【００６０】
ストアユニット３３４は、命令デコーダ３２０からの制御に従って、レジスタファイル３４０に格納されたデータ、または、実行結果出力部４２０から出力された実行結果を主記憶部１３０に書き戻すためのものである。このストアユニット３３４は、主記憶部１３０にデータを書き戻すためのストア命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０からの制御に従って、書き戻すべきデータを、データ線２２９を介してデータキャッシュ２２０に出力する。また、このストアユニット３３４は、実行履歴検索部４１０により実行結果が抽出された場合には、実行結果出力部４２０から出力された実行結果を、データ線２２９を介して主記憶部１３０およびデータキャッシュ２２０に書き戻す。
【００６１】
レジスタファイル３４０は、実行部３３０から出力されたデータを保持するものである。このレジスタファイル３４０は、複数のレジスタ、例えば、３２個のレジスタ０乃至３１により構成される。このレジスタファイル３４０は、命令デコーダ３２０からの制御に従って、実行部３３０から出力されたデータを、複数のレジスタのうち、１つのレジスタに格納する。
【００６２】
また、このレジスタファイル３４０は、例えば、命令デコーダ３２０からの制御に従って、複数のレジスタのうち１つのレジスタに格納されたデータを実行結果として実行部３３０または実行部３３０を介して実行履歴検索部４１０に出力する。また、このレジスタファイル３４０は、例えば、命令デコーダ３２０からの制御に従って、複数のレジスタのうち１つのレジスタに格納された関数の先頭アドレスを識別情報として実行部３３０を介して実行履歴検索部４１０に出力する。
【００６３】
実行履歴検索部４１０は、履歴メモリ４３０において識別情報ごとに保持された再利用区間における入力値および実行結果である実行履歴のうち、予告命令に基づいて取得された識別情報および入力値と同一の実行履歴における実行結果を検索するものである。この実行履歴検索部４１０は、予告命令に基づいて特定された識別情報および入力値を保持して、その保持された識別情報および入力値を履歴メモリ４３０に出力することによって、実行履歴の検索を行う。
【００６４】
この実行履歴検索部４１０は、命令デコーダ３２０の指示に従って、予告命令により特定される識別情報を取得する。この実行履歴検索部４１０は、例えば、識別情報を含む予告命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０から出力された識別情報を保持する。また、この実行履歴検索部４１０は、例えば、参照情報を含む予告命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０からの制御に従って、レジスタファイル３４０から出力された関数の先頭アドレスを識別情報として取得する。
【００６５】
さらに、この実行履歴検索部４１０は、例えば、予告設定命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０からの制御に従って、入力選択部３３２を介して、レジスタファイル３４０に格納される関数の先頭アドレスを識別情報として取得する。その識別情報が取得された後に、実行履歴検索部４１０は、入力値設定命令が命令デコーダ３２０に供給されるたびに、命令デコーダ３２０から出力される取得信号に基づいて関数の入力値を取得する。
【００６６】
すなわち、実行履歴検索部４１０は、実行部３３０から出力された識別情報である関数の先頭アドレスと、その関数の入力値とに基づいて、履歴メモリ４３０に保持された実行履歴における実行結果を検索する。そして、実行履歴検索部４１０は、関数を呼び出す呼出し命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０からの入力値終了信号に基づいて、履歴メモリ４３０に対する検索を終了する。
【００６７】
実行履歴検索部４１０は、履歴メモリ４３０から実行結果が抽出された場合には、その実行結果を実行結果出力部４２０に出力する。これとともに、実行履歴検索部４１０は、関数の処理を省略するための省略信号として、その抽出された実行結果における格納場所に関する情報をフェッチ部３１０に供給する。
【００６８】
一方、履歴メモリ４３０から実行結果が抽出されない場合には、実行履歴検索部４１０は、実行部３３０において予告命令により識別された関数における処理が実行された後に、実行部３３０から出力された実行結果を取得する。そして、実行履歴検索部４１０は、その関数の実行結果と、予告命令に基づいて取得された識別情報および入力値とを履歴メモリ４３０に保持させる。すなわち、履歴メモリ４３０から実行結果が抽出されない場合には、実行履歴検索部４１０は、予告命令の後に実行される関数の実行結果と、予告命令により保持された関数の識別情報および入力値を履歴メモリ４３０に登録する。
【００６９】
この例において、関数における処理の実行を終了するためのリターン命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０の制御によって、実行履歴検索部４１０は、レジスタファイル３４０に格納される実行結果を取得する。これにより、実行履歴検索部４１０は、予告命令により特定された関数の識別情報に対応する入力値および実行結果を関連付けて履歴メモリ４３０に保持させることができる。
【００７０】
また、実行履歴を削除する際の優先度が予告命令に含まれる場合には、実行履歴検索部４１０は、命令デコーダ３２０からの優先度と、優先度に対応する関数の入力値および実行結果とを関連付けて実行履歴として識別情報ごとに履歴メモリ４３０に保持させる。この場合において、実行履歴検索部４１０は、履歴メモリ４３０に保持された優先度に基づいて、履歴メモリ４３０における実行履歴を削除する。すなわち、実行履歴検索部４１０は、優先度が最も大きい識別情報に関連付けられた実行履歴から順番に、履歴メモリ４３０における実行履歴を削除する。なお、実行履歴検索部４１０は、特許請求の範囲に記載の実行履歴検索部の一例である。
【００７１】
実行結果出力部４２０は、実行履歴検索部４１０によって履歴メモリ４３０から実行結果が抽出された場合には、その実行結果を、入力選択部３３２を介してレジスタファイル３４０に、または、ストアユニット３３４に出力するものである。この実行結果出力部４２０は、実行結果の格納場所によって、ストアユニット３３４または入力選択部３３２に実行結果のデータを出力する。なお、実行結果出力部４２０は、特許請求の範囲に記載の実行結果出力部の一例である。
【００７２】
履歴メモリ４３０は、識別情報ごとに識別情報に対応する入力値および実行結果を関連付けて実行履歴として保持するものである。この履歴メモリ４３０は、例えば、連想メモリ（ＣＡＭ：Content Addressable Memory）により実現される。この例において、履歴メモリ４３０は、実行結果を検索するための検索キーである識別情報が実行履歴検索部４１０から入力されることによって、その識別情報に関連付けられた実行履歴の検索を開始する。
【００７３】
また、この履歴メモリ４３０は、実行履歴検索部４１０から順次供給された入力値と、履歴メモリ４３０に保持されている入力値とが全て一致する場合には、その保持された入力値に関連付けられた実行結果を実行履歴検索部４１０に出力する。すなわち、実行履歴検索部４１０から入力された識別情報および入力値と同一の実行履歴が履歴メモリ４３０から検出されることによって、実行履歴検索部４１０により履歴メモリ４３０から実行結果が抽出される。なお、履歴メモリ４３０は、特許請求の範囲に記載の履歴メモリの一例である。
【００７４】
また、履歴メモリ４３０は、例えば、実行履歴検索部４１０から供給された優先度と、優先度に対応する関数の入力値および実行結果とを関連付けて実行履歴として識別情報ごとに保持する。また、この連想メモリにより実現される履歴メモリ４３０は、例えば、実行履歴における入力値のパターンを木構造により保持する。ここで、履歴メモリ４３０におけるデータ構造の例について図面を参照して以下に説明する。
【００７５】
［履歴メモリ４３０のデータ構造例］
図３は、本発明の第１の実施の形態における履歴メモリ４３０のデータ構造の一例を示す概念図である。ここでは、履歴メモリ４３０により、複数の関数を互いに識別する識別情報ごとに保持された実行履歴のうち、１つの識別情報における実行履歴を木構造により保持する構成が示されている。この例では、引数がｎ個であり、かつ、実行結果である出力をｍ個の格納先に返す関数を想定している。また、ここでは、関数の先頭アドレスである関数アドレスを識別情報として用いることとする。
【００７６】
この例では、木構造における関数ルート４４０と、第１の引数ノード４５１および４５２と、第ｎの引数ノード４６１乃至４６４と、第１の出力ノード４７１乃至４７４と、第ｍの出力ノード４８１乃至４８４とが示されている。
【００７７】
関数ルート４４０には、識別情報である関数アドレスと、第１の引数ノード４５１を指し示すポインタとが示されている。
【００７８】
第１および第ｎの引数ノード４５１、４５２および４６１乃至４６４には、履歴メモリ４３０に保持されている実行履歴における引数の入力値として、引数の値を示す入力データと、その引数の型と、その引数の格納場所を示す種類とが示されている。ここにいう格納場所とは、レジスタファイル３４０のレジスタ番号または主記憶部１３０のメモリアドレスのことをいう。
【００７９】
さらに、第１および第ｎの引数ノード４５１、４５２および４６１乃至４６４には、比較対象の入力値が互いに一致した場合に次の引数における引数ノードを指し示す右ポインタと、不一致の場合に同一の引数における他の引数ノードを指し示す下ポインタとが示されている。また、第ｎの引数ノード４６１乃至４６４の各々に、第１および第ｍの出力ノード４７１乃至４７４および４８１乃至４８４がそれぞれ連結されている。
【００８０】
第１および第ｍの出力ノード４７１乃至４７４および４８１乃至４８４には、履歴メモリ４３０に保持されている実行履歴における実行結果として、実行結果の値を示す出力データと、その実行結果の格納場所を示す種類と、その実行結果の型とが示されている。さらに、第１の出力ノード４７１乃至４７４には、次の出力ノードを指し示す右ポインタが示されている。この第１および第ｍの出力ノード４７１乃至４７４および４８１乃至４８４は、連結リストを構成している。また、第ｍの出力ノード４８１乃至４８４の右ポインタには、出力ノードの終端を表わすヌルが示されている。
【００８１】
このような木構造において、関数ルート４４０に示された関数アドレスと一致する関数アドレスが実行履歴検索部４１０から入力されると、関数ルート４４０のポインタによって指し示された第１の引数ノード４５１において入力値の比較処理が実行される。ここにいう入力値の比較処理とは、第１の引数ノード４５１に示された入力データ、種類および型である入力値と、実行履歴検索部４１０からの入力値とを比較することである。
【００８２】
このとき、例えば、第１の引数ノード４５１に示された入力値と実行履歴検索部４１０からの入力値とが一致した場合には、第１の引数ノード４５１の右ポインタにより指し示された次の引数ノードにおいて入力値の比較処理が実行される。一方、第１の引数ノード４５１に示された入力値と、実行履歴検索部４１０からの入力値とが一致しない場合には、第１の引数ノード４５１の下ポインタにより指し示された第１の引数ノード４５２において入力値の比較処理が実行される。
【００８３】
このようにして、各引数ノードにおける比較処理による結果に基づいて右または下ポインタの指し示す引数ノードが選択され、その選択された引数ノードにおいて入力値の比較処理が順次実行される。例えば、第ｎの引数ノード４６１に示された入力値と、実行履歴検索部４１０からの入力値とが互いに一致した場合には、第ｎの引数ノード４６１の右ポインタにより第１の出力ノード４７１が指し示される。そして、第１の出力ノード４７１に保持された出力データ、種類および型を示す実行結果から順番に、第ｍ番の出力ノード４８１に保持された実行結果までが実行履歴検索部４１０に順次出力される。
【００８４】
このように、履歴メモリ４３０を識別情報ごとに木構造により構成することによって、同じ引数の入力値を重複して保持させる必要が無いため、記憶領域を節約することができる。また、識別情報ごとにデータ構造を分けることによって、検索速度の低下を抑制することができる。
【００８５】
［識別情報を含む予告命令によるデータ処理装置１００の動作例］
図４は、本発明の第１の実施の形態におけるデータ処理装置１００において識別情報を含む予告命令を受け付けた場合におけるデータ処理装置１００の動作概要を示す概念図である。図４（ａ）は、アセンブリ言語により記述された命令列の一部を例示する図である。図４（ａ）には、インデックス（ｉｎｄｅｘ）を指定する予告命令（ｎｏｔｉｃｅＣａｌｌ）と、関数（ｆｕｎｃ）を呼び出すコール命令（Ｃａｌｌ）とが示されている。
【００８６】
図４（ｂ）は、履歴メモリ４３０における識別情報ごとの実行履歴検索データの一例を示す概念図である。図４（ｂ）には、インデックス（ｉｎｄｅｘ）により示される識別情報（インデックス０乃至ｋ）の列４３１と、実行履歴検索データ（実行履歴検索データ０乃至ｋ）の列４３２との対応が示されている。ここにいう実行履歴検索データは、図３に示した木構造により構成される検索データのことを示す。
【００８７】
この場合において、予告命令（ｎｏｔｉｃｅＣａｌｌ）が命令デコーダ３２０に供給されることによって、インデックス（ｉｎｄｅｘ）により示される識別情報「インデックスｋ」が、命令デコーダ３２０から実行履歴検索部４１０に供給される。そして、実行履歴検索部４１０により、識別情報「インデックスｋ」が履歴メモリ４３０に入力されることによって、この識別情報（インデックスｋ）によって識別される関数（ｆｕｎｃ）における「実行履歴検索データｋ」に基づいて、実行履歴の検索が開始される。
【００８８】
その後、関数における引数の入力値を設定する入力値設定命令に基づいて、実行履歴検索部４１０において、関数（ｆｕｎｃ）の引数の入力値が取得され、その取得された入力値が履歴メモリ４３０に順次入力される。これにより、識別情報「インデックスｋ」に対応する実行履歴検索データ（実行履歴検索データｋ）に保持された入力値と、実行履歴検索部４１０からの入力値との比較が順次行われる。
【００８９】
そして、コール命令（ｃａｌｌ）が命令デコーダ３２０に供給されることによって、実行履歴検索部４１０により取得された識別情報および入力値と一致する実行履歴の有無が履歴メモリ４３０から実行履歴検索部４１０に通知される。すなわち、実行履歴検索部４１０により、実行履歴検索データｋによる検索結果として関数（ｆｕｎｃ）の再利用できる実行結果の有無がコール命令（ｃａｌｌ）に基づいて参照される。
【００９０】
このとき、履歴メモリ４３０から実行結果が出力された場合には、関数（ｆｕｎｃ）の実行が省略される。一方、実行結果が出力されない場合には、関数（ｆｕｎｃ）が実行されて、その実行された実行結果と、実行履歴検索部４１０によって既に取得された識別情報および入力値とが履歴メモリ４３０に保持される。
【００９１】
このように、データ処理装置１００は、関数（ｆｕｎｃ）のコール命令（ｃａｌｌ）を実行する前において、予告命令（ｎｏｔｉｃｅＣａｌｌ）に基づいて関数（ｆｕｎｃ）の引数の入力値を取得する。そして、その関数（ｆｕｎｃ）の入力値と、履歴メモリ４３０に保持された関数（ｆｕｎｃ）の入力値との比較を終了させる。次に、識別情報を含む予告命令によるデータ処理装置１００におけるより具体的な動作例について、ＭＩＰＳによる命令コードを示す図面を参照して説明する。
【００９２】
［識別情報を含む予告命令による動作例］
図５は、本発明の第１の実施の形態におけるデータ処理装置１００により実行されるプログラムの一部を例示する図である。図５（ａ）は、再利用区間として選択された関数のソースプログラムの一部の例を示す図である。図５（ｂ）は、図５（ａ）に示したソースプログラムがＭＩＰＳのアセンブリ言語により変換された命令列の一部を例示する図である。
【００９３】
図５（ａ）の上段には、５つの引数（ａ乃至ｅ）を持つ関数（ｆｕｎｃ）の呼出しが記述されている。下段には、イント（ｉｎｔ）型の関数（ｆｕｎｃ）の定義が記述されている。この関数（ｆｕｎｃ）は、イント（ｉｎｔ）型の引数として、第１の引数（ａ）、第２の引数（ｂ）、第３の引数（ｃ）、第４の引数（ｄ）および第５の引数（ｅ）を持つ。このようなソースプログラムに対し、ＭＩＰＳのアセンブリ言語により変換するとともに予告命令の挿入処理を施すことによって生成された命令列の一部が図５（ｂ）に示されている。
【００９４】
図５（ｂ）には、第１の命令列（ｎｏｔｉｃｅＣａｌｌ）、第２の命令列（ｌｗ）、第３の命令列（ｌｗ）、第４の命令列（ｍｏｖｅ）、第５の命令列（ｍｏｖｅ）、第６の命令列（ｓｗ）、第７の命令列（ｌｗ）および第８の命令列（ｊａｌｒ）が示されている。ここでは、第１乃至第５引数の入力値Ａ乃至Ｅが全て整数であることを想定している。
【００９５】
第１の命令列において、インデックス（ｉｎｄｅｘ）を指定する予告命令（ｎｏｔｉｃｅＣａｌｌ）が実行される。これにより、命令デコーダ３２０により供給されたインデックス（ｉｎｄｅｘ）により示された識別情報が実行履歴検索部４１０から履歴メモリ４３０に入力されることによって、実行履歴の検索が行われる。
【００９６】
第２の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスにオフセット値「１０００」が加算され、その加算された値によって指定される主記憶部１３０のメモリアドレスに記憶されたデータ（第１の引数の入力値Ａ）がレジスタ４（Ｒ４）に転送される。
【００９７】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示された転送先レジスタ番号が「Ｒ４」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ４（Ｒ４）に転送される入力値Ａが実行履歴検索部４１０にも供給されて、履歴メモリ４３０に保持されている第１の引数の入力値と比較される。このとき、履歴メモリ４３０に保持された第１の引数の入力値のうち、入力値Ａが保持されていれば、第２の引数の入力値の比較処理に進む。一方、入力値Ａが保持されていない場合には、実行履歴の検索を終了する。
【００９８】
第３の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスにオフセット値「１００４」が加算され、その加算された値によって指定される主記憶部１３０のメモリアドレスに記憶されたデータ（第２の引数の入力値Ｂ）がレジスタ５（Ｒ５）に転送される。
【００９９】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示される転送先レジスタ番号が「Ｒ５」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ５（Ｒ５）に格納される入力値Ｂが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第２の引数の入力値と比較される。このとき、履歴メモリ４３０に保持された第２の引数の入力値のうち、入力値Ｂが保持されていれば、第３の引数の入力値の比較処理に進む。一方、入力値Ｂが保持されていない場合には、実行履歴の検索を終了する。
【０１００】
第４の命令列において、ムーブ命令（ｍｏｖｅ）が実行される。これにより、レジスタ１０（Ｒ１０）に格納されているデータ（第３の引数の入力値Ｃ）がレジスタ６（Ｒ６）に転送される。このムーブ命令（ｍｏｖｅ）は、その転送先レジスタ番号が「Ｒ６」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ６（Ｒ６）に格納される入力値Ｃが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第３の引数の入力値と比較される。
【０１０１】
このとき、履歴メモリ４３０に保持された第３の引数の入力値のうち入力値Ｃが保持されていれば、第４の引数の入力値の比較処理に進む。一方、入力値Ｃが保持されていない場合には、実行履歴の検索を終了する。
【０１０２】
第５の命令列において、ムーブ命令（ｍｏｖｅ）が実行される。これにより、レジスタ１１（Ｒ１１）に格納されているデータ（第４の引数の入力値Ｄ）がレジスタ７（Ｒ７）に転送される。このムーブ命令（ｍｏｖｅ）は、そのムーブ命令（ｍｏｖｅ）に示される転送先レジスタ番号が「Ｒ７」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ７（Ｒ７）に格納される入力値Ｄが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第４の引数の入力値と比較される。
【０１０３】
このとき、履歴メモリ４３０に保持された第４の引数の入力値のうち入力値Ｄが保持されていれば、第５の引数の入力値の比較処理に進む。一方、入力値Ｄが保持されていない場合には、実行履歴の検索を終了する。
【０１０４】
第６の命令列において、ストアワード命令（ｓｗ）が実行される。これにより、レジスタ２９（Ｒ２９）に格納されているスタックポインタの値に「１６」が加算され、その加算された値のメモリアドレスにレジスタ１２（Ｒ１２）に格納されているデータ（第５の引数の入力値Ｅ）が転送される。このストアワード命令（ｓｗ）は、そのストアワード命令（ｓｗ）に示される転送先レジスタ番号が「Ｒ２９」であり、オフセット値が「１６」以上であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。
【０１０５】
これにより、主記憶部１３０に転送された入力値Ｅが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第５の引数の入力値と比較される。このとき、履歴メモリ４３０に保持された第５の引数の入力値のうち、入力値Ｅが保持されていれば、全ての引数の入力値Ａ乃至Ｅが一致する実行履歴における実行結果が実行履歴検索部４１０に出力される。一方、入力値Ａが保持されていない場合には、実行履歴の検索を終了する。
【０１０６】
第７の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスに、オフセット値「２０００」が加算され、その加算された値のメモリアドレスに記憶されたデータ（関数ｆｕｎｃの先頭アドレス）がレジスタ２５（Ｒ２５）に転送される。
【０１０７】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示される転送先レジスタ番号が「Ｒ２５」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令でないと判断される。このため、実行履歴検索部４１０により、入力選択部３３２から出力されたデータは取得されない。
【０１０８】
第８の命令列において、ジャンプ命令（ｊａｌｒ）が実行される。これにより、レジスタ２５（Ｒ２５）に格納されている関数（ｆｕｎｃ）の先頭アドレスの命令が読み出される。このとき、命令デコーダ３２０により、関数（ｆｕｎｃ）における全ての第１乃至第５引数の入力値の設定が終了したことを示す入力値終了信号が実行履歴検索部４１０に通知される。
【０１０９】
このとき、履歴メモリ４３０から実行結果が出力されていれば、実行履歴検索部４１０により、その実行結果が実行結果出力部４２０に出力されるとともに、関数（ｆｕｎｃ）の処理を省略するための省略信号がフェッチ部３１０に供給される。一方、履歴メモリ４３０から実行結果が出力されていなければ、実行履歴検索部４１０により、関数（ｆｕｎｃ）の実行後の実行結果と、予告命令に基づいて取得された識別情報および入力値とが履歴メモリ４３０に登録される。
【０１１０】
次に、履歴メモリ４３０に保持された実行履歴と、実行履歴検索部４１０により取得された識別情報および入力値とが一致した場合において予告命令により関数の処理時間が短縮される例について以下に図面を参照して説明する。
【０１１１】
［データ処理装置１００による関数処理の時間短縮例］
図６は、予告命令の実行により関数における処理時間が短縮される例を示す概念図である。図６（ａ）は、予告命令のないプログラムの処理を実行する従来のデータ処理装置における実行結果の再利用による短縮時間を示す概念図である。図６（ｂ）は、本発明の第１の実施の形態におけるデータ処理装置１００における実行結果の再利用による短縮時間を示す概念図である。
【０１１２】
図６（ａ）および（ｂ）では、上位ルーチンにおいて２つの引数を持つ関数がコール命令（ｃａｌｌ）によって呼び出され、その関数における処理の終了に伴うリターン命令（ｒｅｔｕｒｎ）によって下位ルーチンから復帰する例が示されている。また、ここでは、左から右に時間が経過することとする。
【０１１３】
図６（ａ）には、上位ルーチンにおける入力値Ａ設定３２１および入力値Ｂ設定３２２と、下位ルーチンにおける入力値Ａ使用３２３および入力値Ｂ使用３２４とが示されている。
【０１１４】
入力値Ａ設定３２１および入力値Ｂ設定３２２は、関数における引数の入力値が設定されるタイミングを示す。これは、図１で述べたとおり、ＡＢＩの規定に従って記述されたプログラムによる処理手順である。また、入力値Ａ使用３２３および入力値Ｂ使用３２４は、下位ルーチンである関数の処理において引数である入力値が使用されるタイミングを示す。
【０１１５】
この場合には、下位ルーチンにおいて２つの引数が全て使用（入力値Ｂ使用３２４）されるまで、関数の引数である入力値ＡおよびＢを特定することができない。このため、関数の引数である入力値ＡおよびＢが、履歴メモリ４３０に保持されている入力値と全て一致したときであっても、入力値Ｂ使用３２４からリターン命令（ｒｅｔｕｒｎ）までの短縮期間ｔ１だけしか関数の処理時間を削減することができない。
【０１１６】
図６（ｂ）には、図６（ａ）に示したタイミングに加えて予告命令４２１が示されている。この予告命令４２１は、命令デコーダ３２０によって予告命令がデコードされるタイミングを示す。予告命令４２１以外は、図６（ａ）と同様のものを示しているため、図６（ａ）と同一符号を付してここでの説明を省略する。
【０１１７】
この場合には、関数を識別するための識別情報が予告命令４２１により特定されるため、履歴メモリ４３０の検索キーである識別情報を履歴メモリ４３０に入力することによって、関数の実行履歴の検索が開始される。そして、実行履歴検索部４１０により、引数の入力値ＡおよびＢを設定するための２つの入力値設定命令に基づいて取得された入力値ＡおよびＢが、履歴メモリ４３０に供給される。
【０１１８】
その後、コール命令（ｃａｌｌ）に基づいて、その取得された入力値ＡおよびＢと、履歴メモリ４３０に保持されている入力値とが全て一致したか否かが判断される。そして、全て一致した場合には、関数である下位ルーチン（ｃａｌｌからｒｅｔｕｒｎまで）の処理に要する短縮期間ｔ２が削減される。
【０１１９】
このように、データ処理装置１００は、予告命令に含まれる識別情報および引数の入力値を予告命令に基づいて取得することによって、実行履歴検索期間ｔにおいて履歴メモリ４３０に対する実行結果の検索を終了させることができる。これにより、履歴メモリ４３０に保持された実行結果が再利用できる場合には、短縮することができる期間（短縮期間ｔ２）を、従来の短縮期間ｔ１よりも長くすることができる。
【０１２０】
［データ処理装置１００の動作例］
次に本発明の実施の形態におけるデータ処理装置１００の動作について図面を参照して説明する。
【０１２１】
図７は、本発明の第１の実施の形態におけるデータ処理装置１００の実行結果再利用方法の処理手順の一例を示すフローチャートである。
【０１２２】
まず、命令デコーダ３２０により、フェッチ部３１０から供給された予告命令が解読される（ステップＳ９１１）。そして、命令デコーダ３２０により、予告命令により特定された識別情報である履歴メモリ４３０の検索キーが実行履歴検索部４１０に供給されることによって、実行履歴検索部４１０において識別情報が取得される。すなわち、実行履歴検索部４１０により、予告命令に含まれる識別情報が取得されて、その取得された識別情報が実行履歴検索部４１０から履歴メモリ４３０に入力される（ステップＳ９１２）。これにより、履歴メモリ４３０における識別情報に対応する複数の実行履歴の検索が開始される。なお、ステップＳ９１２は、特許請求の範囲に記載の取得手順の一例である。
【０１２３】
続いて、フェッチ部３１０により、予告命令の次に実行されるべき命令が読み出される（ステップＳ９１３）。この後、命令デコーダ３２０により、フェッチ部３１０から読み出された命令が、関数の第１の引数の入力値を設定するための入力値設定命令か否かが判断される（ステップＳ９１４）。
【０１２４】
そして、入力値設定命令であると判断された場合には、命令デコーダ３２０により、入力値設定命令によって設定された引数の入力値が実行履歴検索部４１０に供給されることによって、実行履歴検索部４１０において引数の入力値が取得される（ステップＳ９２１）。なお、ステップＳ９２１は、特許請求の範囲に記載の取得手順の一例である。
【０１２５】
続いて、実行履歴検索部４１０により取得された引数の入力値が、履歴メモリ４３０における識別情報に関連付けられた引数の入力値と一致するか否かが判断される（ステップＳ９２２）。そして、両者の入力値が一致しない場合には、ステップＳ９１３の処理に戻る。
【０１２６】
一方、両者の入力値が一致した場合には、履歴メモリ４３０において、次の引数の入力値を比較するための次の引数ノードにポインタが進められて（ステップＳ９２３）、ステップＳ９１３の処理に戻る。すなわち、複数の引数ノードのうち、実行履歴検索部４１０からの入力値と一致する引数ノードがあれば、その引数ノードの右ポインタによって、次の引数ノードが指し示される。
【０１２７】
このようにして、全ての引数の入力値が設定されるまで、ステップＳ９１３、Ｓ９１４、Ｓ９２１乃至Ｓ９２３における一連の処理が繰り返し実行される。なお、ステップＳ９２２およびＳ９２３は、特許請求の範囲に記載の実行履歴検索手順の一例である。
【０１２８】
一方、ステップＳ９１４の処理において入力値設定命令でないと判断された場合には、命令デコーダ３２０により、フェッチ部３１０から読み出された命令が、関数を呼び出す呼出し命令であるか否かが判断される（ステップＳ９１５）。そして、呼出し命令でないと判断された場合には、ステップＳ９１３の処理に戻る。
【０１２９】
一方、呼出し命令と判断された場合には、入力値設定命令により設定された入力値が、履歴メモリ４３０における識別情報に関連付けられた入力値と全て一致したか否かが判断される（ステップＳ９１６）。そして、全ての入力値が一致した場合には、実行結果再利用処理が実行される（ステップＳ９２４）。すなわち、実行履歴検索部４１０により取得された識別情報および入力値に対応する履歴メモリ４３０における実行結果が、実行結果出力部４２０から出力される。そして、主記憶部１３０またはレジスタファイル３４０に書き戻されて、呼び出される関数の処理を終了する。なお、Ｓ９２４は、特許請求の範囲に記載の実行結果出力手順の一例である。
【０１３０】
一方、全ての入力値が一致しない場合には、呼び出された関数が実行される（ステップＳ９１７）。そして、実行履歴検索部４１０により、実行された関数の実行結果が取得される（ステップＳ９１８）。続いて、実行履歴検索部４１０により、その取得された実行結果と、ステップＳ９１２およびＳ９２１により取得された入力値とを履歴メモリ４３０に登録される（ステップＳ９１９）。
【０１３１】
このように、本発明の第１の実施の形態では、関数の実行を予告する予告命令によって、関数の識別情報と、その予告命令の後に実行される入力値設定命令により設定される入力値とを、関数の実行前に特定することができる。これにより、関数が呼び出されるときに、その特定された識別情報および入力値と一致する履歴メモリ４３０における実行履歴を抽出することができる。また、履歴メモリ４３０から実行履歴における実行結果が抽出された場合には、呼出し命令により呼び出される関数の実行を省略することができるため、実行結果の再利用による関数の処理時間を大幅に削減することができる。
【０１３２】
なお、本発明の第１の実施の形態では、履歴メモリ４３０の検索キーである識別情報を予告命令に含める例について説明したが、識別情報を関数の先頭アドレスとし、関数の先頭アドレスを参照するための参照情報を予告命令に含めるようにしてもよい。そこで、参照情報を含む予告命令に基づいて履歴メモリ４３０における実行履歴を検索する例を第２の実施の形態として以下に図面を参照して説明する。
【０１３３】
＜第２の実施の形態＞
［参照情報を含む予告命令によるデータ処理装置１００の動作例］
図８は、本発明の第２の実施の形態におけるデータ処理装置１００において参照情報を含む予告命令を受け付けた場合におけるデータ処理装置１００の動作概要を示す概念図である。ここでは、履歴メモリ４３０の検索キーである識別情報として関数の先頭アドレスである関数アドレスを用いることを想定している。
【０１３４】
図８（ａ）は、アセンブリ言語により記述された命令列の一部を例示する図である。図８（ａ）には、関数アドレスをレジスタ２５（Ｒ２５）に設定するロードワード命令（ｌｗ）と、参照情報（Ｒ２５）を含む予告命令（ｎｏｔｉｃｅＣａｌｌ）とが示されている。また、ここでは、レジスタ２５（Ｒ２５）に格納された関数を呼び出すコール命令（Ｃａｌｌ）が示されている。
【０１３５】
このように、予告命令（ｎｏｔｉｃｅＣａｌｌ）の参照情報には、関数アドレスが格納されているレジスタ番号（Ｒ２５）が示される。また、このような参照情報を含む予告命令を生成する場合には、コンパイル処理において、関数アドレスを設定するロードワード命令（ｌｗ）を予告命令の前に生成することを想定している。
【０１３６】
図８（ｂ）は、履歴メモリ４３０における識別情報である関数アドレスごとの実行履歴検索データの一例を示す概念図である。図８（ｂ）には、参照情報（Ｒ２５）に示されるレジスタ２５（Ｒ２５）に格納されている関数アドレス（関数アドレス０乃至ｋ）の列４３３と、実行履歴検索データ（実行履歴検索データ０乃至ｋ）の列４３４との対応表が示されている。ここにいう実行履歴検索データは、図３に示した木構造によって構成される検索データのことを示す。
【０１３７】
この場合において、命令デコーダ３２０は、予告命令（ｎｏｔｉｃｅＣａｌｌ）に含まれる参照情報（Ｒ２５）に基づいて、レジスタ２５（Ｒ２５）に格納されている「関数アドレス１」を実行履歴検索部４１０に出力させる。すなわち、実行部３３０は、参照情報を含む予告命令に基づいて関数アドレス「関数アドレス１」を実行履歴検索部４１０に出力する。そして、実行履歴検索部４１０により、その「関数アドレス１」が履歴メモリ４３０に入力されることによって、その関数アドレス１に対応する実行履歴検索データ１に基づいて、実行履歴の検索が開始される。
【０１３８】
その後、関数における引数の入力値を設定するための入力値設定命令に基づいて、実行履歴検索部４１０において、関数における引数の入力値が保持され、その保持された入力値が履歴メモリ４３０に順次入力される。これにより、関数アドレス（関数アドレス１）に対応する実行履歴検索データ（実行履歴検索データ１）に保持された入力値と、実行履歴検索部４１０からの入力値との比較が順次行われる。
【０１３９】
そして、コール命令（ｃａｌｌ）が命令デコーダ３２０に供給されることによって、実行履歴検索部４１０により取得された関数アドレスおよび入力値と一致する実行履歴の有無が、履歴メモリ４３０から実行履歴検索部４１０に通知される。すなわち、実行履歴検索部４１０により、関数アドレス１に対応する実行履歴検索データ１による検索結果として、再利用できる実行結果の有無がコール命令（ｃａｌｌ）に基づいて参照される。
【０１４０】
このとき、履歴メモリ４３０から実行結果が出力された場合には、関数の実行が省略される。一方、実行結果が出力されない場合には、関数の処理がそのまま実行されて、その実行された実行結果と、実行履歴検索部４１０によって既に保持されている識別情報および入力値とが履歴メモリ４３０に登録される。
【０１４１】
このように、データ処理装置１００は、関数（関数アドレス１）のコール命令（ｃａｌｌ）の実行前に、予告命令（ｎｏｔｉｃｅＣａｌｌ）に含まれる参照情報に基づいて、履歴メモリ４３０の検索キーである識別情報（関数アドレス１）を取得することができる。次に、参照情報を含む予告命令によるデータ処理装置１００におけるより具体的な動作例について、ＭＩＰＳによる命令コードを示す図面を参照して説明する。
【０１４２】
［参照情報を含む予告命令によるデータ処理装置１００の具体的な動作例］
図９は、本発明の第２の実施の形態におけるデータ処理装置１００により実行されるプログラムの一部を例示する図である。図９（ａ）は、再利用区間として選択された関数のソースプログラムの一部の例を示す図である。図５（ｂ）は、図５（ａ）に示したソースプログラムがＭＩＰＳのアセンブリ言語により変換された命令列の一部を例示する図である。
【０１４３】
図９（ａ）の上段には、５つの引数（ａ乃至ｅ）を持つ関数（ｆｕｎｃ）の呼出しが記述されている。下段には、イント（ｉｎｔ）型の関数（ｆｕｎｃ）の定義が記述されている。この関数（ｆｕｎｃ）は、イント（ｉｎｔ）型の引数として、第１の引数（ａ）、第２の引数（ｂ）、第３の引数（ｃ）、第４の引数（ｄ）および第５の引数（ｅ）を持つ。このようなソースプログラムに対し、ＭＩＰＳのアセンブリ言語により変換するとともに予告命令の挿入処理を施すことによって生成された命令列の一部が図９（ｂ）に示されている。
【０１４４】
図９（ｂ）には、第１の命令列（ｌｗ）、第２の命令列（ｎｏｔｉｃｅＣａｌｌ）、第３の命令列（ｌｗ）、第４の命令列（ｌｗ）、第５の命令列（ｍｏｖｅ）、第６の命令列（ｍｏｖｅ）、第７の命令列（ｓｗ）、および第８の命令列（ｊａｌｒ）が示されている。ここでは、関数の引数の入力値Ａ乃至Ｅが全て整数であることを想定している。
【０１４５】
第１の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスに、オフセット値「２０００」が加算され、その加算された値のメモリアドレスに記憶されたデータ（関数ｆｕｎｃの先頭アドレス）がレジスタ２５（Ｒ２５）に転送される。このように、主記憶部１３０から読み出された関数の先頭アドレスをレジスタファイル３４０に設定するロードワード命令を、ここではアドレス設定命令という。
【０１４６】
第２の命令列において、参照情報（Ｒ２５）を含む予告命令（ｎｏｔｉｃｅＣａｌｌ）が実行される。これにより、命令デコーダ３２０の制御により、参照情報（Ｒ２５）に基づいて、レジスタ２５に格納された識別情報である関数アドレスが実行履歴検索部４１０に出力される。すなわち、実行部３３０により、参照情報を含む予告命令に基づいて関数アドレスが実行履歴検索部４１０に出力される。そして、実行履歴検索部４１０により、その関数アドレスが履歴メモリ４３０に入力されることによって、実行履歴の検索が行われる。
【０１４７】
第３の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスにオフセット値「１０００」が加算され、その加算された値である主記憶部１３０のメモリアドレスに記憶されたデータ（第１の引数の入力値Ａ）がレジスタ４（Ｒ４）に転送される。
【０１４８】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示される転送先レジスタ番号が「Ｒ４」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ４（Ｒ４）に転送される入力値Ａが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第１の引数の入力値と比較される。このとき、履歴メモリ４３０に保持された第１の引数の入力値のうち、入力値Ａが保持されていれば、第２の引数の入力値の比較処理に進む。一方、入力値Ａが保持されていない場合には、実行履歴の検索を終了する。
【０１４９】
第４の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスにオフセット値「１００４」が加算され、その加算された値である主記憶部１３０のメモリアドレスに記憶されたデータ（第２の引数の入力値Ｂ）がレジスタ５（Ｒ５）に転送される。
【０１５０】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示された転送先レジスタ番号が「Ｒ５」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ５（Ｒ５）に格納される入力値Ｂが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第２の引数の入力値と比較される。このとき、履歴メモリ４３０に保持された第２の引数の入力値のうち、入力値Ｂが保持されていれば、第３の引数の入力値の比較処理に進む。一方、入力値Ｂが保持されていない場合には、実行履歴の検索を終了する。
【０１５１】
第５の命令列において、ムーブ命令（ｍｏｖｅ）が実行される。これにより、レジスタ１０（Ｒ１０）に格納されているデータ（第３の引数の入力値Ｃ）が、レジスタ６（Ｒ６）に転送される。このムーブ命令（ｍｏｖｅ）は、そのムーブ命令（ｍｏｖｅ）に示された転送先レジスタ番号が「Ｒ６」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ６（Ｒ６）に格納される入力値Ｃが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第３の引数の入力値と比較される。
【０１５２】
このとき、履歴メモリ４３０に保持された第３の引数の入力値のうち入力値Ｃが保持されていれば、第４の引数の入力値の比較処理に進む。一方、入力値Ｃが保持されていない場合には、実行履歴の検索を終了する。
【０１５３】
第６の命令列において、ムーブ命令（ｍｏｖｅ）が実行される。これにより、レジスタ１１（Ｒ１１）に格納されているデータ（第４の引数の入力値Ｄ）がレジスタ７（Ｒ７）に転送される。このムーブ命令（ｍｏｖｅ）は、そのムーブ命令（ｍｏｖｅ）に示された転送先レジスタ番号が「Ｒ７」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると特定される。このため、レジスタ７（Ｒ７）に格納される入力値Ｄが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第４の引数の入力値と比較される。
【０１５４】
このとき、履歴メモリ４３０に保持された第４の引数の入力値のうち入力値Ｄが保持されていれば、第５の引数の入力値の比較処理に進む。一方、入力値Ｄが保持されていない場合には、実行履歴の検索を終了する。
【０１５５】
第７の命令列において、ストアワード命令（ｓｗ）が実行される。これにより、レジスタ２９（Ｒ２９）に格納されているスタックポインタの値に「１６」が加算され、その加算された値のメモリアドレスにレジスタ１２（Ｒ１２）に格納されているデータ（第５の引数の入力値Ｅ）が転送される。このストアワード命令（ｓｗ）は、そのストアワード命令（ｓｗ）に示された転送先レジスタ番号が「Ｒ２９」であり、オフセット値が「１６」以上であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。
【０１５６】
これにより、主記憶部１３０に転送された入力値Ｅが実行履歴検索部４１０にも供給され、その供給された入力値Ｅと、履歴メモリ４３０に保持されている第５の引数の入力値とが比較される。このとき、履歴メモリ４３０に保持された第５の引数の入力値のうち、入力値Ｅが保持されていれば、全ての引数の入力値Ａ乃至Ｅが一致する実行履歴における実行結果が実行履歴検索部４１０に出力される。一方、入力値Ａが保持されていない場合には、実行履歴の検索を終了する。
【０１５７】
第８の命令列において、ジャンプ命令（ｊａｌｒ）が実行される。これにより、レジスタ２５（Ｒ２５）に格納されている関数（ｆｕｎｃ）の先頭アドレスの命令が読み出される。このとき、命令デコーダ３２０により、関数（ｆｕｎｃ）における全ての第１乃至第５引数の入力値の設定が終了したことを示す入力値終了信号が、実行履歴検索部４１０に通知される。
【０１５８】
このとき、履歴メモリ４３０から実行結果が出力されていれば、実行履歴検索部４１０により、その実行結果が実行結果出力部４２０に出力されるとともに、関数（ｆｕｎｃ）の処理を省略するための省略信号がフェッチ部３１０に供給される。一方、履歴メモリ４３０から実行結果が出力されていなければ、実行履歴検索部４１０により、関数（ｆｕｎｃ）の実行後の実行結果と、予告命令に基づいて取得された識別情報および入力値とが履歴メモリ４３０に登録される。
【０１５９】
このように、本発明の第２の実施の形態では、実行履歴検索部４１０は、予告命令により識別される関数が実行される前において、予告命令に含まれる参照情報に基づいて関数の先頭アドレスを識別情報として取得することができる。これにより、実行履歴検索部４１０は、識別情報として実行部３３０から出力された再利用区間である関数の先頭アドレスと、関数の入力値とに基づいて、履歴メモリ４３０に保持された実行履歴における実行結果を検索することができる。
【０１６０】
すなわち、実行結果再利用処理部４００は、参照情報を含む予告命令によって、実行履歴検索部４１０において識別情報および入力値を取得することができるため、関数の実行前に、履歴メモリ４３０に保持された実行履歴を検索することができる。
【０１６１】
なお、ここでは、参照情報を含む予告命令により関数アドレスを取得する例について説明したが、関数アドレスを設定するためのアドレス設定命令を予告命令とする予告設定命令を用いるようにしてもよい。次に、予告設定命令を契機に履歴メモリ４３０に保持された実行履歴を検索する例を第３の実施の形態として以下に図面を参照して説明する。
【０１６２】
＜第３の実施の形態＞
［参照情報を含む予告命令によるデータ処理装置１００の動作例］
図１０は、本発明の第３の実施の形態におけるデータ処理装置１００において予告設定命令を受け付けた場合におけるデータ処理装置１００の動作概要を示す概念図である。ここでは、履歴メモリ４３０の検索キーである識別情報として関数の先頭アドレスである関数アドレスを用いることを想定している。
【０１６３】
図１０（ａ）は、アセンブリ言語により記述された命令列の一部を例示する図である。図１０（ａ）には、関数アドレスをレジスタ２５（Ｒ２５）に設定する予告設定命令（ｍｅｍｏｌｗ）と、レジスタ２５（Ｒ２５）に格納された関数アドレスに対応する関数を呼び出すコール命令（Ｃａｌｌ）が示されている。
【０１６４】
このように、予告設定命令（ｍｅｍｏｌｗ）を用いることによって、第２の実施の形態と比べて、関数アドレスをレジスタ２５（Ｒ２５）に設定するアドレス設定命令（ｌｗ）を省略することができる。
【０１６５】
図１０（ｂ）は、履歴メモリ４３０における識別情報である関数アドレスごとの実行履歴検索データの一例を示す概念図である。図１０（ｂ）には、予告設定命令（ｍｅｍｏｌｗ）によってレジスタ２５（Ｒ２５）に設定される関数アドレス（関数アドレス０乃至ｋ）の列４３５と、実行履歴検索データ（実行履歴検索データ０乃至ｋ）の列４３６との対応表が示されている。ここにいう実行履歴検索データは、図３に示した木構造によって構成される検索データのことを示す。
【０１６６】
この場合において、命令デコーダ３２０は、予告設定命令（ｍｅｍｏｌｗ）に指定された設定情報に示されたレジスタ２５（Ｒ２５）に「関数アドレス１」を設定するとともに、実行履歴検索部４１０に「関数アドレス１」を取得させる。すなわち、実行部３３０は、関数の先頭アドレスの設定先（Ｒ２５）を示す設定情報を含む予告設定命令（ｍｅｍｏｌｗ）基づいて、関数の先頭アドレス「関数アドレス１」を設定先（Ｒ２５）に設定する。
【０１６７】
そして、実行履歴検索部４１０により、その「関数アドレス１」が履歴メモリ４３０に入力されることによって、その関数アドレス１に対応する「実行履歴検索データ１」に基づいて、実行履歴の検索が開始される。
【０１６８】
その後、関数における引数の入力値を設定するための入力値設定命令に基づいて、実行履歴検索部４１０において、引数の入力値が取得され、その取得された入力値が履歴メモリ４３０に順次入力される。これにより、関数アドレス（関数アドレス１）に対応する実行履歴検索データ（実行履歴検索データ１）に保持された入力値と、実行履歴検索部４１０からの入力値との比較が順次行われる。
【０１６９】
そして、コール命令（ｃａｌｌ）が命令デコーダ３２０に供給されることによって、実行履歴検索部４１０により取得された関数アドレス（関数アドレス１）および入力値と一致する実行履歴の有無が履歴メモリ４３０から実行履歴検索部４１０に通知される。すなわち、実行履歴検索部４１０により、関数アドレス１に対応する実行履歴検索データ１による検索結果がコール命令（ｃａｌｌ）に基づいて参照される。
【０１７０】
このとき、履歴メモリ４３０から実行結果が出力された場合には、関数の実行が省略される。一方、実行結果が出力されない場合には、関数の処理が実行されて、その実行された実行結果と、実行履歴検索部４１０によって既に取得された識別情報である関数アドレスおよび入力値とが履歴メモリ４３０に保持される。
【０１７１】
このように、データ処理装置１００は、関数（関数アドレス１）のコール命令（ｃａｌｌ）を実行する前に、予告設定命令（ｍｅｍｏｌｗ）により設定される関数アドレス（関数アドレス１）を実行履歴検索部４１０において取得することができる。次に、予告設定命令によるデータ処理装置１００におけるより具体的な動作例について、ＭＩＰＳによる命令コードを示す図面を参照して説明する。
【０１７２】
［予告設定命令によるデータ処理装置１００の具体的な動作例］
図１１は、本発明の第３の実施の形態におけるデータ処理装置１００により実行されるプログラムの一部を例示する図である。図１１（ａ）の上段には、５つの引数（ａ乃至ｅ）を持つ関数（ｆｕｎｃ）の呼出しが記述されている。下段には、イント（ｉｎｔ）型の関数（ｆｕｎｃ）の定義が記述されている。この関数（ｆｕｎｃ）は、イント（ｉｎｔ）型の引数として、第１の引数（ａ）、第２の引数（ｂ）、第３の引数（ｃ）、第４の引数（ｄ）および第５の引数（ｅ）を持つ。
【０１７３】
このようなソースプログラムに対し、ＭＩＰＳのアセンブリ言語により変換するとともに予告命令の挿入処理を施すことによって生成された命令列の一部が図１１（ｂ）に示されている。
【０１７４】
図１１（ｂ）には、第１の命令列（ｍｅｍｏｌｗ）、第２の命令列（ｌｗ）、第３の命令列（ｌｗ）、第４の命令列（ｍｏｖｅ）、第５の命令列（ｍｏｖｅ）、第６の命令列（ｓｗ）、および第７の命令列（ｊａｌｒ）が示されている。ここでは、関数の引数の入力値Ａ乃至Ｅが全て整数であることを想定している。
【０１７５】
第１の命令列において、予告設定命令（ｍｅｍｏｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスに、オフセット値「２０００」が加算され、その加算された値のメモリアドレスに記憶されたデータ（関数ｆｕｎｃの先頭アドレス）がレジスタ２５（Ｒ２５）に転送される。すなわち、実行部３３０は、予告設定命令に含まれる関数の先頭アドレスの設定先を示す設定情報を基づいて、関数の先頭アドレスを設定先に設定する。
【０１７６】
これとともに、命令デコーダ３２０により供給される取得信号に基づいて、入力選択部３３２から出力される関数アドレスが実行履歴検索部４１０により取得される。そして、実行履歴検索部４１０によりその関数アドレスが履歴メモリ４３０に入力されることによって、実行履歴の検索が行われる。
【０１７７】
第２の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスにオフセット値「１０００」が加算され、その加算された値である主記憶部１３０のメモリアドレスに記憶されたデータ（第１の引数の入力値Ａ）がレジスタ４（Ｒ４）に転送される。
【０１７８】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示された転送先レジスタ番号が「Ｒ４」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ４（Ｒ４）に転送される入力値Ａが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第１の引数の入力値と比較される。
【０１７９】
このとき、履歴メモリ４３０に保持された第１の引数の入力値のうち、入力値Ａが保持されていれば、第２の引数の入力値の比較処理に進む。一方、入力値Ａが保持されていない場合には、実行履歴の検索を終了する。
【０１８０】
第３の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスにオフセット値「１００４」が加算され、その加算された値である主記憶部１３０のメモリアドレスに記憶されたデータ（第２の引数の入力値Ｂ）がレジスタ５（Ｒ５）に転送される。
【０１８１】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示された転送先レジスタ番号が「Ｒ５」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ５（Ｒ５）に格納される入力値Ｂが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第２の引数の入力値と比較される。
【０１８２】
このとき、履歴メモリ４３０に保持された第２の引数の入力値のうち、入力値Ｂが保持されていれば、第３の引数の入力値の比較処理に進む。一方、入力値Ｂが保持されていない場合には、実行履歴の検索を終了する。
【０１８３】
第４の命令列において、ムーブ命令（ｍｏｖｅ）が実行される。これにより、レジスタ１０（Ｒ１０）に格納されているデータ（第３の引数の入力値Ｃ）がレジスタ６（Ｒ６）に転送される。このムーブ命令（ｍｏｖｅ）は、その転送先レジスタ番号が「Ｒ６」であることから、命令デコーダ３２０により引数の入力値を設定する入力値設定命令であると判断される。これにより、レジスタ６（Ｒ６）に格納される入力値Ｃが実行履歴検索部４１０にも供給されるため、実行履歴検索部４１０に供給された入力値Ｃと、履歴メモリ４３０に保持されている第３の引数の入力値とが比較される。
【０１８４】
このとき、履歴メモリ４３０に保持された第３の引数の入力値のうち入力値Ｃが保持されていれば、第４の引数の入力値の比較処理に進む。一方、入力値Ｃが保持されていない場合には、実行履歴の検索を終了する。
【０１８５】
第５の命令列において、ムーブ命令（ｍｏｖｅ）が実行される。これにより、レジスタ１１（Ｒ１１）に格納されているデータ（第４の引数の入力値Ｄ）がレジスタ７（Ｒ７）に転送される。このムーブ命令（ｍｏｖｅ）は、そのムーブ命令（ｍｏｖｅ）に示された転送先レジスタ番号が「Ｒ７」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると特定される。このため、レジスタ７（Ｒ７）に格納される入力値Ｄが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第４の引数の入力値と比較される。
【０１８６】
このとき、履歴メモリ４３０に保持された第４の引数の入力値のうち入力値Ｄが保持されていれば、第５の引数の入力値の比較処理に進む。一方、入力値Ｄが保持されていない場合には、実行履歴の検索を終了する。
【０１８７】
第６の命令列において、ストアワード命令（ｓｗ）が実行される。これにより、レジスタ２９（Ｒ２９）に格納されているスタックポインタの値に「１６」が加算され、その加算された値のメモリアドレスにレジスタ１２（Ｒ１２）に格納されているデータ（第５の引数の入力値Ｅ）が転送される。このストアワード命令（ｓｗ）は、そのストアワード命令（ｓｗ）に示された転送先レジスタ番号が「Ｒ２９」であり、オフセット値が「１６」以上であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。
【０１８８】
これにより、主記憶部１３０に転送された入力値Ｅが実行履歴検索部４１０にも供給され、その供給された入力値Ｅと、履歴メモリ４３０に保持されている第５の引数の入力値とが比較される。このとき、履歴メモリ４３０に保持された第５の引数の入力値のうち、入力値Ｅが保持されていれば、全ての引数の入力値Ａ乃至Ｅが一致する実行履歴における実行結果が実行履歴検索部４１０に出力される。一方、入力値Ａが保持されていない場合には、実行履歴の検索を終了する。
【０１８９】
第７の命令列において、ジャンプ命令（ｊａｌｒ）が実行される。これにより、レジスタ２５（Ｒ２５）に格納されている関数（ｆｕｎｃ）の先頭アドレスの命令が読み出される。このとき、命令デコーダ３２０により、関数（ｆｕｎｃ）における全ての第１乃至第５引数の入力値の設定が終了したことを示す入力値終了信号が実行履歴検索部４１０に通知される。
【０１９０】
このとき、履歴メモリ４３０から実行結果が出力されていれば、実行履歴検索部４１０により、その実行結果が実行結果出力部４２０に出力されるとともに、関数（ｆｕｎｃ）の処理を省略するための省略信号がフェッチ部３１０に供給される。一方、履歴メモリ４３０から実行結果が出力されていなければ、実行履歴検索部４１０により、関数（ｆｕｎｃ）の実行後の実行結果と、予告命令に基づいて取得された識別情報および入力値とが履歴メモリ４３０に登録される。
【０１９１】
このように、本発明の第３の実施の形態では、実行履歴検索部４１０は、関数の実行前において、その関数に対応する予告設定命令に基づいて設定される関数アドレスを識別情報として取得することができる。これにより、実行履歴検索部４１０は、実行部３３０により設定された関数の先頭アドレスと、予告設定命令により取得された関数の入力値とに基づいて、履歴メモリ４３０における実行結果を検索することができる。
【０１９２】
すなわち、実行結果再利用処理部４００は、予告設定命令によって、実行履歴検索部４１０において識別情報および入力値を取得することができるため、関数の実行前に、履歴メモリ４３０に保持された実行履歴を検索することができる。
【０１９３】
このように、本発明の第１乃至３の実施の形態では、主記憶部１３０に記憶されたプログラムに含まれる予告命令に基づいて、関数の実行結果の再利用による処理時間を大幅に短縮することができる。次に、このような予告命令をプログラムに挿入するプログラム変換装置について図面を参照して説明する。
【０１９４】
＜４．第４の実施の形態＞
［プログラム変換装置の構成例］
図１２は、本発明の第４の実施の形態におけるプログラム変換処理装置の一機能構成例を示すブロック図である。プログラム変換処理装置５００は、ソースプログラム記憶部５１０と、予告命令挿入コード生成部６００と、オブジェクトプログラム記憶部５２０とを備える。なお、プログラム変換処理装置５００は、特許請求の範囲に記載のプログラム変換処理装置の一例である。
【０１９５】
ソースプログラム記憶部５１０は、コンパイル処理の対象となるソースプログラムを記憶するものである。このソースプログラムは、実行結果が再び利用される再利用区間が含まれるソースプログラムである。このソースプログラム記憶部５１０は、その記憶されたソースプログラムを予告命令挿入コード生成部６００に供給する。
【０１９６】
予告命令挿入コード生成部６００は、ソースプログラム記憶部５１０からのソースプログラムをコンパイルすることによって、予告命令を挿入するための処理を施した後に、機械語プログラムであるオブジェクトプログラムを生成するものである。この予告命令挿入コード生成部６００は、その生成されたオブジェクトプログラムをオブジェクトプログラム記憶部５２０に記憶させる。この予告命令挿入コード生成部６００は、プログラム解析部６１０と、プログラム最適化処理部６２０と、コード生成部６３０とを備える。
【０１９７】
プログラム解析部６１０は、ソースプログラム記憶部５１０から読み出したソースプログラムに基づいて形態素解析や構文解析などの解析処理を実行するものである。このプログラム解析部６１０は、解析または最適化に適した形式の中間コードによって表現された中間表現によるプログラムを生成して、その生成されたプログラムに解析処理を実行する。
【０１９８】
また、このプログラム解析部６１０は、再利用候補区間抽出部６１１および再利用候補区間解析部６１２を備える。再利用候補区間抽出部６１１は、複数の命令区間のうち、実行結果を再利用する再利用区間の候補となる再利用候補区間をプログラムから抽出するものである。この再利用候補区間抽出部６１１は、例えば、複数回実行される命令区間である複数の関数のうち、再利用候補区間となる関数を抽出する。
【０１９９】
また、再利用候補区間抽出部６１１は、再利用候補区間の入力値が同じでも異なる実行結果になるため、実行結果が再利用できない関数を再利用候補区間から除外する。この再利用候補区間抽出部６１１は、例えば、命令区間に分岐命令を含むような関数を再利用候補区間から除外する。この再利用候補区間抽出部６１１は、その抽出された再利用候補区間の識別情報をプログラムとともに再利用候補区間解析部６１２に供給する。
【０２００】
再利用候補区間解析部６１２は、再利用候補区間抽出部６１１により抽出された再利用候補区間の使用態様を解析するものである。この再利用候補区間解析部６１２は、例えば、関数における引数の個数および型と、その１つの関数が実行される回数とを使用態様として関数ごとに解析する。この例において、再利用候補区間解析部６１２は、例えば、関数の処理内容から引数の採り得る範囲の数を使用態様の解析結果として出力する。この再利用候補区間解析部６１２は、その解析結果を、再利用候補区間の識別情報およびプログラムとともにプログラム最適化処理部６２０に供給する。
【０２０１】
プログラム最適化処理部６２０は、再利用候補区間解析部６１２から供給されたプログラムに基づいて、プログラムの実行速度を向上させるための最適化、および、コードサイズを削減するための最適化などを行うプログラム最適化処理を実行するものである。このプログラム最適化処理部６２０は、再利用度生成部６２１と、再利用区間選択部６２２と、予告命令生成処理部６２３とを備える。
【０２０２】
再利用度生成部６２１は、再利用候補区間解析部６１２から供給された解析結果に基づいて、再利用候補区間の実行結果が再び利用される度合いを示す再利用度を生成するものである。すなわち、再利用度生成部６２１は、複数回実行される命令区間の各々の実行結果が互いに一致する度合いを示す再利用度を、命令区間の使用態様に基づいて命令区間ごとに生成する。
【０２０３】
この再利用度生成部６２１は、例えば、再利用候補区間が実行される実行回数に応じて再利用度を生成する。この場合において、再利用度生成部６２１は、例えば、実行回数が大きいほど再利用度を大きく設定する。また、この再利用度生成部６２１は、例えば、再利用候補区間の入力値が採り得る範囲の数に応じて再利用度を生成する。この場合には、再利用度は、例えば、組合せの数の逆数に定数を乗算することによって算出される。このため、再利用候補区間の再利用度が大きいほど、再利用される度合いが高い再利用候補区間であることを意味する。
【０２０４】
この再利用度生成部６２１は、その生成された再利用度を、プログラムおよび再利用候補区間の識別情報とともに再利用区間選択部６２２に供給する。なお、再利用度生成部６２１は、特許請求の範囲に記載の再利用度生成部の一例である。
【０２０５】
再利用区間選択部６２２は、再利用度生成部６２１から供給された再利用候補区間の再利用度に基づいて、複数の再利用候補区間のうち、再利用区間を選択するものである。この再利用区間選択部６２２は、例えば、再利用度に関する一定の閾値（再利用閾値）以上である再利用候補区間を再利用区間として選択する。
【０２０６】
また、再利用区間選択部６２２は、例えば、履歴メモリ４３０における識別情報ごとの実行履歴を削除する際の優先度を再利用度に基づいて生成する。この例において、再利用区間選択部６２２は、再利用度が高いほど優先度が低くなるように優先度を生成する。また、再利用区間選択部６２２は、その選択された再利用区間に関する識別情報および優先度を、プログラムとともに予告命令生成処理部６２３に供給する。
【０２０７】
予告命令生成処理部６２３は、再利用区間選択部６２２により選択された再利用区間を呼び出すための呼出し命令の前に、その再利用区間を特定するための情報を含む予告命令を生成するものである。この予告命令生成処理部６２３は、その予告命令から呼出し命令の直前の命令までに、再利用区間の入力値を設定するための入力値設定命令を生成する。
【０２０８】
すなわち、予告命令生成処理部６２３は、複数の命令区間のうち、再利用度に基づいて選択された再利用区間における入力値を設定する入力値設定命令の直前に、再利用区間における入力値の設定を予告する予告命令を生成する。この予告命令生成処理部６２３は、例えば、再利用区間である関数の呼出し命令の前に予告命令を挿入するとともに、その予告命令と呼出し命令との間に入力値設定命令を生成する。
【０２０９】
また、予告命令生成処理部６２３は、例えば、呼出し命令の前において、その呼出し命令によって呼び出される関数の識別情報が含まれる予告命令を生成する。すなわち、予告命令生成処理部６２３は、再利用度に基づいて選択された複数の再利用区間を互いに識別するための識別情報を含む予告命令を生成する。この予告命令生成処理部６２３は、例えば、図５（ｂ）に表わしたように、インデックス（ｉｎｄｅｘ）により示される識別情報を含む予告命令（ｎｏｔｉｃｅＣａｌｌ）を生成する。
【０２１０】
また、予告命令生成処理部６２３は、例えば、呼出し命令の前に、その呼出し命令の実行のためにレジスタファイル３４０に予め設定された関数の先頭アドレスを参照するための参照情報が含まれる予告命令を挿入する。この場合、予告命令生成処理部６２３は、参照情報を含む予告命令の前に、関数の先頭アドレスをレジスタファイル３４０に設定するためのアドレス設定命令を生成する。すなわち、予告命令生成処理部６２３は、再利用区間の先頭アドレスを設定するためのアドレス設定命令の後に、その先頭アドレスを参照するための参照情報を含む予告命令を生成する。この例において、予告命令生成処理部６２３は、例えば、図９（ｂ）に示すように参照情報（Ｒ２５）を含む予告命令（ｎｏｔｉｃｅＣａｌｌ）を生成する。
【０２１１】
その他の例として、予告命令生成処理部６２３は、呼出し命令の前に、その呼出し命令の飛越し先である関数の先頭アドレスの設定先を示す設定情報が含まれる予告命令を予告設定命令として生成する。すなわち、予告命令生成処理部６２３は、再利用区間の先頭アドレスを設定するために、関数の先頭アドレスの設定先が示された設定情報を含むアドレス設定命令として予告命令を生成する。この例において、予告命令生成処理部６２３は、例えば、図１１（ｂ）に示すように予告設定命令（ｍｅｍｏｌｗ）を生成する。
【０２１２】
また、予告命令生成処理部６２３は、例えば、識別情報を含む予告命令、または、参照情報を含む予告命令を生成するにあたり、再利用区間選択部６２２により生成された優先度をさらに含めた予告命令を、呼出し命令の前に生成する。すなわち、予告命令生成処理部６２３は、再利用度生成部６２１により生成された再利用度に応じて付与された優先度を含む予告命令を生成する。
【０２１３】
また、この予告命令生成処理部６２３は、その生成された予告命令を含む最適化されたプログラムをコード生成部６３０に供給する。なお、予告命令生成処理部６２３は、特許請求の範囲に記載の予告命令生成処理部の一例である。
【０２１４】
コード生成部６３０は、予告命令生成処理部６２３から供給された最適化されたプログラムに基づいて、機械語プログラムのコードであるオブジェクトプログラムを生成するものである。このコード生成部６３０は、その生成したオブジェクトプログラムをオブジェクトプログラム記憶部５２０に供給する。
【０２１５】
オブジェクトプログラム記憶部５２０は、コード生成部６３０から供給されたオブジェクトプログラムを記憶するものである。このオブジェクトプログラム記憶部５２０に記憶されたオブジェクトプログラムが、図１に示した主記憶部１３０に記憶される。
【０２１６】
このように、予告命令生成処理部６２３を設けることによって、再利用区間の呼出し命令の実行前にその呼出し命令の実行を予告する予告命令が実行されるプログラムを生成することができる。また、再利用度生成部６２１を設けることによって、複数回実行される命令区間の使用態様に基づいて再利用度が生成されるため、複数の命令区間のうち、実行結果が再利用される確率の高い命令区間を再利用区間として選択することができる。
【０２１７】
［予告命令のデータフォーマットの例］
図１３は、本発明の第４の実施の形態におけるプログラム変換処理装置５００により生成される予告命令のデータフォーマットを例示する図である。ここでは、ＭＩＰＳの規定による３２ビット命令のデータフォーマットに基づく予告命令の例について示す。
【０２１８】
図１３（ａ）は、識別情報を含む予告命令のデータフォーマットを示す図である。図１３（ｂ）は、参照情報を含む予告命令のデータフォーマットを示す図である。図１３（ｃ）は、予告設定命令のデータフォーマットを示す図である。
【０２１９】
図１３（ａ）には、オペレーションコード７１１、インデックス７１２、優先度７１３および機能コード７１４を表わすフィールドがそれぞれ示されている。オペレーションコード７１１には、特殊命令（ＳＰＥＣＩＡＬ）を示す「００００００」が２６乃至３１ビットに格納される。
【０２２０】
インデックス７１２には、再利用区間選択部６２２により選択された複数の関数を互いに識別するための識別情報が１０乃至２５ビットに格納される。優先度７１３には、履歴メモリ４３０における実行履歴を削除する際の優先度が６乃至９ビットに格納される。この優先度７１３には、再利用区間選択部６２２により生成された優先度の値が格納される。機能コード７１４には、予告命令（ｎｏｔｉｃｅＣａｌｌ）として「０００１０１」が０乃至５ビットに格納される。
【０２２１】
図１３（ｂ）には、オペレーションコード７２１、優先度７２２、転送先レジスタ７２３および機能コード７２４を表わすフィールドがそれぞれ示されている。オペレーションコード７１１には、特殊命令（ＳＰＥＣＩＡＬ）を示す「００００００」が２６乃至３１ビットに格納される。
【０２２２】
優先度７２２には、履歴メモリ４３０の実行履歴を削除する際の優先度が１１乃至２５ビットに格納される。この優先度７２２には、再利用区間選択部６２２により生成された優先度の値が格納される。転送先レジスタ７２３には、参照情報として、関数の先頭アドレスが格納されているレジスタ番号が６乃至１０ビットに格納される。機能コード７２４には、予告命令（ｎｏｔｉｃｅＣａｌｌ）として「０００１０１」が０乃至５ビットに格納される。
【０２２３】
図１３（ｃ）には、オペレーションコード７３１、基準レジスタ７３２、転送先レジスタ７３３およびオフセット７３４を表わすフィールドがそれぞれ示されている。オペレーションコード７３１には、予告設定命令（ｍｅｍｏｌｗ）を示す「０１１１１１」が２６乃至３１ビットに格納される。
【０２２４】
基準レジスタ７３２には、基準アドレスが格納されているレジスタ番号（Ｒ２５）が２１乃至２５ビットに格納される。転送先レジスタ７３３には、設定先を示す設定情報として、関数を呼び出すための関数の先頭アドレスが設定されるレジスタ番号が１６乃至２０ビットに格納される。オフセット７３４には、基準アドレスに対するオフセット値が０乃至１５ビットに格納される。
【０２２５】
このような予告命令または予告設定命令が、関数を呼び出すための呼出し命令の前に、予告命令生成処理部６２３によって生成される。
【０２２６】
［プログラム変換処理装置５００の動作例］
次に本発明の第４の実施の形態におけるプログラム変換処理装置５００の動作について図面を参照して説明する。
【０２２７】
図１４は、本発明の第４の実施の形態におけるプログラム変換処理装置５００の予告命令生成処理方法の処理手順の一例を示すフローチャートである。
【０２２８】
まず、再利用候補区間抽出部６１１により、ソースプログラム記憶部５１０からソースプログラムが読み出される（ステップＳ９３１）。そして、再利用候補区間抽出部６１１により、複数回実行される命令区間である複数の関数のうち、再利用候補区間となる関数が抽出される（ステップＳ９３２）。
【０２２９】
続いて、再利用候補区間解析部６１２により、再利用候補区間抽出部６１１において抽出された再利用候補区間の使用態様が解析される（ステップＳ９３３）。この後、再利用度生成部６２１により、再利用候補区間の使用態様に基づいて再利用候補区間ごとに再利用度が生成される（ステップＳ９３４）。なお、ステップＳ９３４は、特許請求の範囲に記載の再利用度生成手順の一例である。
【０２３０】
そして、再利用区間選択部６２２により、再利用候補区間ごとの再利用度に基づいて再利用区間が選択される（ステップＳ９３５）。次に、予告命令生成処理部６２３により、再利用区間を呼び出す呼出し命令の前に予告命令を生成して、その生成された予告命令から呼出し命令の間に入力値設定命令を生成する予告命令生成処理が実行される（ステップＳ９４０）。なお、ステップＳ９４０は、特許請求の範囲に記載の予告命令生成手順の一例である。
【０２３１】
その後、コード生成部６３０により、予告命令生成処理部６２３から供給された最適化されたプログラムに基づいて、オブジェクトプログラムが生成される（ステップＳ９３６）。次に、図１３（ａ）乃至（ｃ）に示した予告命令ごとの予告命令生成処理の処理手順例について以下に図面を参照して説明する。
【０２３２】
［識別情報を含む予告命令における予告命令生成処理例］
図１５は、本発明の第４の実施の形態における識別情報を含む予告命令についての予告命令処理（ステップＳ９４０）の処理手順の一例を示すフローチャートである。
【０２３３】
まず、予告命令生成処理部６２３により、再利用区間の呼出し命令の前に、識別情報を含む予告命令が生成される（ステップＳ９４２）。例えば、図５（ｂ）に示した第１の命令列のように、インデックス（ｉｎｄｅｘ）を指定する予告命令（ｎｏｔｉｃｅＣａｌｌ）が生成される。
【０２３４】
次に、予告命令生成処理部６２３により、識別情報を含む予告命令の後に、再利用区間の入力値を設定するための入力値設定命令が生成される（ステップＳ９４３）。例えば、図５（ｂ）に示した第２乃至第６の命令列のように、入力値設定命令（２つのロードワード命令、２つのムーブ命令およびストアワード命令）が生成される。
【０２３５】
そして、予告命令生成処理部６２３により、入力値設定命令の後に、再利用区間の先頭アドレスを設定するためのアドレス設定命令が生成される（ステップＳ９４４）。例えば、図５（ｂ）に示した第７の命令列のように、アドレス設定命令（ロードワード命令）が生成される。
【０２３６】
その後、予告命令生成処理部６２３により、アドレス設定命令の後に、再利用区間の呼出し命令が生成される（ステップＳ９４５）。例えば、図５（ｂ）に示した第８の命令列のように、呼出し命令（ジャンプ命令）が生成される。
【０２３７】
予告命令生成処理部６２３により、ステップＳ９４２乃至Ｓ９４５の一連の処理が全ての再利用区間を対象に施されるまで繰り返し行われ（ステップＳ９４６）、全ての再利用区間に対する処理が終了することによって、予告命令生成処理が終了する。
【０２３８】
［参照情報を含む予告命令における予告命令生成処理例］
図１６は、本発明の第４の実施の形態における参照情報を含む予告命令についての予告命令処理（ステップＳ９５０）の処理手順の一例を示すフローチャートである。
【０２３９】
まず、予告命令生成処理部６２３により、再利用区間の先頭アドレスを設定するためのアドレス設定命令が生成される（ステップＳ９５１）。例えば、図９（ｂ）に示した第１の命令列のように、アドレス設定命令（ロードワード命令）が生成される。
【０２４０】
そして、予告命令生成処理部６２３により、アドレス設定命令の後に、参照情報を含む予告命令が生成される（ステップＳ９５２）。例えば、図９（ｂ）に示した第２の命令列のように、参照情報（Ｒ２５）を示す予告命令（ｎｏｔｉｃｅＣａｌｌ）が生成される。
【０２４１】
次に、予告命令生成処理部６２３により、参照情報を含む予告命令の後に、再利用区間の入力値を設定するための入力値設定命令が生成される（ステップＳ９４３）。例えば、図９（ｂ）に示した第３乃至第７の命令列のように、入力値設定命令（２つのロードワード命令、２つのムーブ命令およびストアワード命令）が生成される。
【０２４２】
その後、予告命令生成処理部６２３により、入力値設定命令の後に、再利用区間の呼出し命令が生成される（ステップＳ９４５）。例えば、図９（ｂ）に示した第８の命令列のように、呼出し命令（ジャンプ命令）が生成される。
【０２４３】
予告命令生成処理部６２３により、ステップＳ９５１、Ｓ９５２、Ｓ９４３およびＳ９４５の一連の処理が全ての再利用区間を対象に施されるまで繰り返し行われる（ステップＳ９４６）。そして、全ての再利用区間に対する処理が終了することによって、予告命令生成処理が終了する。
【０２４４】
［予告設定命令における予告命令生成処理例］
図１７は、本発明の第４の実施の形態における予告設定命令についての予告命令処理（ステップＳ９６０）の処理手順の一例を示すフローチャートである。
【０２４５】
まず、予告命令生成処理部６２３により、再利用区間の先頭アドレスを設定するための予告設定命令が生成される（ステップＳ９６１）。例えば、図１１（ｂ）に示した第１の命令列のように、予告設定命令（ｍｅｍｏｌｗ）が生成される。
【０２４６】
次に、予告命令生成処理部６２３により、予告設定命令の後に、再利用区間の入力値を設定するための入力値設定命令が生成される（ステップＳ９４３）。例えば、図１１（ｂ）に示した第２乃至第６の命令列のように、入力値設定命令（２つのロードワード命令、２つのムーブ命令およびストアワード命令）が生成される。
【０２４７】
その後、予告命令生成処理部６２３により、入力値設定命令の後に、再利用区間の呼出し命令が生成される（ステップＳ９４６）。例えば、図１１（ｂ）に示した第７の命令列のように、呼出し命令（ジャンプ命令）が生成される。
【０２４８】
予告命令生成処理部６２３により、ステップＳ９６１、Ｓ９４３およびＳ９４５の一連の処理が全ての再利用区間を対象に施されるまで繰り返し行われる（ステップＳ９４６）。そして、全ての再利用区間に対する処理が終了することによって、予告命令生成処理が終了する。
【０２４９】
このように、本発明の第４の実施の形態では、再利用区間の呼出し命令の前に予告命令を生成することによって、データ処理装置１００による実行結果の再利用による再利用区間の処理時間を削減することができる。また、再利用度に基づいて選択された再利用区間に予告命令生成処理を施すことによって、データ処理装置１００における実行結果の再利用率を向上させることができる。
【０２５０】
このように、本発明の実施の形態によれば、再利用区間における処理の実行を予告する予告命令に基づいてその再利用区間の実行結果の再利用処理を行うことによって、再利用区間の処理時間を大幅に削減することができる。
【０２５１】
なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、本発明の実施の形態において明示したように、本発明の実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本発明の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本発明は実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０２５２】
また、本発明の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disk）、メモリカード、ブルーレイディスク（Blu-ray Disc（登録商標））等を用いることができる。
【符号の説明】
【０２５３】
１００ データ処理装置
１２０ バス
１３０ 主記憶部
２００ 一次キャッシュ
２１０ 命令キャッシュ
２２０ データキャッシュ
３００ データ処理部
３１０ フェッチ部
３２０ 命令デコーダ
３３１ ロードユニット
３３２ 入力選択部
３３３ 演算回路
３３４ ストアユニット
３４０ レジスタファイル
４００ 実行結果再利用処理部
４１０ 実行履歴検索部
４２０ 実行結果出力部
４３０ 履歴メモリ
５００ プログラム変換処理装置
５１０ ソースプログラム記憶部
５２０ オブジェクトプログラム記憶部
６００ 予告命令挿入コード生成部
６１０ プログラム解析部
６１１ 再利用候補区間抽出部
６１２ 再利用候補区間解析部
６２０ プログラム最適化処理部
６２１ 再利用度生成部
６２２ 再利用区間選択部
６２３ 予告命令生成処理部
６３０ コード生成部
【技術分野】
【０００１】
本発明は、データ処理装置に関し、特に複数回実行される命令区間の実行結果を再利用するデータ処理装置およびその処理方法、ならびに、このデータ処理装置に対応するプログラムに変換するデータ変換処理装置およびその処理方法に関する。
【背景技術】
【０００２】
従来からＣＰＵ（Central Processing Unit）などのマイクロプロセッサにおいて、演算処理の高速化技術に関する研究開発が盛んに行われている。この演算処理の高速化技術として、値再利用技術という手法が考案されている。例えば、この値再利用技術をループの命令区間に適用したデータ処理装置が提案されている（例えば、特許文献１参照。）。
この値再利用技術では、プログラムの一部分である命令区間のうち、その命令区間における入力値が同じであれば実行結果も同じとなる命令区間における入力値と、その実行結果である出力値とを関連付けて再利用表に登録する。その後、同じ命令区間を再度実行する場合に、同一の入力値が再利用表に登録されていれば、その入力値に対応する出力値を再利用表から出力することによって、過去に実行された命令区間の実行結果を再利用する。このように、複数回実行される命令区間のうち、過去に実行された命令区間の実行結果を再利用することができる命令区間をここでは再利用区間という。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第３８５５０７６号公報（図１）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述の従来技術では、再利用区間における処理が再度実行されたときに、その命令区間の入力値が再利用表に登録されていれば、その再利用区間の処理を省略することができるため、命令区間の実行に要する時間を短縮することができる。しかしながら、この場合、再利用区間の処理において入力値が使用されるまでは、その再利用区間の入力値が再利用表に登録されているか否かの判断を行うことができない。このため、入力値が使用されるまで再利用表の検索を行うことができないことから、実行結果の再利用によって短縮することができる期間が制限されてしまう。
【０００５】
本発明はこのような状況に鑑みてなされたものであり、実行結果の再利用による再利用区間の処理時間をさらに短縮させることを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、複数回実行される命令区間である再利用区間が含まれる命令列に基づく処理を実行する実行部と、上記再利用区間を識別するための識別情報ごとに上記再利用区間における入力値および実行結果を関連付けて実行履歴として保持する履歴メモリと、上記再利用区間における処理の実行を予告する予告命令に基づいて上記再利用区間の入力値を取得して上記取得された入力値と上記予告命令により特定された上記識別情報とに基づいて上記実行履歴における上記実行結果を検索する実行履歴検索部と、上記予告命令によって識別された上記再利用区間における処理が実行されるときに上記実行履歴検索部により上記実行結果が抽出された場合には上記抽出された実行結果を上記実行部に出力する実行結果出力部とを具備するデータ処理装置およびその処理方法である。これにより、再利用区間の実行前において予告命令に基づいて再利用区間の入力値を取得し、その取得された入力値と予告命令により特定された識別情報とに基づいて履歴メモリにおける実行結果を検索させて、予告命令によって識別された再利用区間における処理が実行されるときに、実行結果が抽出された場合には、その抽出された実行結果を実行部に出力させるという作用をもたらす。
【０００７】
また、この第１の側面において、上記実行履歴検索部は、上記予告命令から上記再利用区間の先頭アドレスが呼び出される呼出し命令の直前の命令までの命令群のうち上記再利用区間の入力値を設定するための入力値設定命令に基づいて入力値を取得するようにしてもよい。これにより、実行履歴検索部により、予告命令の後に続く入力値設定命令によって設定されたデータを再利用区間の入力値として取得させるという作用をもたらす。
【０００８】
また、この第１の側面において、上記実行履歴検索部は、上記取得された入力値と上記予告命令に含まれる上記識別情報とに基づいて上記実行履歴における上記実行結果を検索するようにしてもよい。これにより、実行履歴検索部により、予告命令に含まれる識別情報と、予告命令に基づいて取得された入力値とを用いて履歴メモリにおける実行結果を検索させるという作用をもたらす。
【０００９】
また、この第１の側面において、上記履歴メモリは、上記識別情報である上記再利用区間の先頭アドレスごとに上記再利用区間における入力値および実行結果を関連付けて上記実行履歴として保持し、上記実行部は、上記先頭アドレスを参照するための参照情報を含む上記予告命令に基づいて上記先頭アドレスを上記実行履歴検索部に出力し、上記実行履歴検索部は、上記識別情報として上記実行部から出力された上記先頭アドレスと上記再利用区間の入力値とに基づいて上記実行履歴における上記実行結果を検索するようにしてもよい。これにより、予告命令に含まれる参照情報に基づいて再利用区間の先頭アドレスを実行部から出力させ、その実行部から出力させた再利用区間の先頭アドレスと、予告命令に基づいて取得された入力値とを用いて履歴メモリにおける実行結果を検索させるという作用をもたらす。
【００１０】
また、この第１の側面において、上記予告命令は、上記識別情報である上記再利用区間の先頭アドレスを設定するための予告設定命令であり、上記履歴メモリは、上記再利用区間の先頭アドレスごとに上記再利用区間における入力値および実行結果を関連付けて上記実行履歴として保持し、上記実行部は、上記先頭アドレスの設定先が示された設定情報を含む上記予告設定命令に基づいて上記先頭アドレスを上記設定先に設定し、上記実行履歴検索部は、上記予告設定命令に基づいて上記再利用区間の入力値を取得して上記取得された入力値と上記実行部により設定された上記先頭アドレスとに基づいて上記実行履歴における上記実行結果を検索するようにしてもよい。これにより、実行履歴検索部により、再利用区間の先頭アドレスを設定する予告設定命令によって設定された先頭アドレスと、予告設定命令に基づいて取得された入力値とに基づいて履歴メモリにおける実行履歴を検索させるという作用をもたらす。
【００１１】
また、この第１の側面において、上記履歴メモリは、上記実行履歴を削除する際の優先度と上記優先度に対応する上記再利用区間における入力値および実行結果とを関連付けて上記実行履歴として上記識別情報ごとに保持し、上記実行履歴検索部は、上記予告命令に含まれる上記優先度に基づいて上記履歴メモリにおける上記実行履歴を削除するようにしてもよい。これにより、実行履歴検索部により、実行履歴ごとに付与された優先度に基づいて、履歴メモリにおける実行履歴を削除させるという作用をもたらす。
【００１２】
また、この第１の側面において、上記実行部は、上記実行履歴検索部により上記実行履歴における上記実行結果が上記履歴メモリから抽出されない場合には上記予告命令によって識別された上記再利用区間における処理を実行し、上記実行履歴検索部は、上記予告命令に基づいて取得された上記入力値と上記実行部により実行された実行結果と上記識別情報とを上記履歴メモリに保持させるようにしてもよい。これにより、履歴メモリから実行結果が抽出されない場合には、実行履歴検索部により、予告命令に基づいて取得された入力値と、その入力値に基づいて実行された実行結果と、識別情報とを履歴メモリに保持させるという作用をもたらす。
【００１３】
また、この第１の側面において、上記履歴メモリは、上記再利用区間である関数を識別するための上記識別情報ごとに上記関数における入力値および実行結果を関連付けて上記実行履歴として保持し、上記実行履歴検索部は、上記関数の実行を予告する予告命令に基づいて上記関数の入力値を取得して上記取得された入力値と上記予告命令により特定された上記識別情報とに基づいて上記実行履歴における上記実行結果を検索し、実行結果出力部は、上記予告命令によって識別された上記関数が実行されるときに上記実行履歴検索部により上記実行結果が抽出された場合には上記抽出された実行結果を上記実行部に出力するようにしてもよい。これにより、実行履歴検索部により、関数の実行を予告する予告命令に基づいて関数の入力値を取得して、その取得された入力値と予告命令により特定された識別情報とを用いてこれらのパラメータに関連付けられた実行結果を履歴メモリから抽出し、関数が実行されるときに、実行結果部により、その抽出された実行結果を実行部に出力させるという作用をもたらす。
【００１４】
また、本発明の第２の側面は、プログラムのうち複数回実行される命令区間の各々の実行結果が互いに一致する度合いを示す再利用度を上記命令区間の使用態様に基づいて上記命令区間ごとに生成する再利用度生成部と、上記複数の命令区間のうち上記再利用度に基づいて選択された再利用区間における入力値を設定する入力値設定命令の直前に上記再利用区間における入力値の設定を予告する予告命令を生成する予告命令生成部とを具備するプログラム変換処理装置およびその処理方法である。これにより、再利用度生成部において命令区間の使用態様に基づいて命令区間ごとの再利用度を生成し、その生成された再利用度に基づいて選択された再利用区間における入力値設定命令の直前に、予告命令生成部により再利用区間の実行を予告する予告命令を生成させるという作用をもたらす。
【００１５】
また、この第２の側面において、上記予告命令生成部は、上記再利用度に基づいて選択された複数の上記再利用区間を識別するための識別情報を含む上記予告命令を生成するようにしてもよい。これにより、上記予告命令生成部により、上記再利用度に基づいて選択された複数の再利用区間を互いに識別するための識別情報を含む予告命令を生成させるという作用をもたらす。
【００１６】
また、この第２の側面において、上記予告命令生成部は、上記再利用区間の先頭アドレスを設定するためのアドレス設定命令の後に上記先頭アドレスを参照するための参照情報を含む上記予告命令を生成するようにしてもよい。これにより、アドレス設定命令の後に、予告命令生成部により、そのアドレス設定命令により設定された再利用区間の先頭アドレスを参照するための参照情報を含む予告命令を生成させるという作用をもたらす。
【００１７】
また、この第２の側面において、上記予告命令生成部は、上記再利用区間の先頭アドレスを設定するために上記先頭アドレスの設定先が示された設定情報を含むアドレス設定命令として上記予告命令を生成するようにしてもよい。これにより、再利用区間の先頭アドレスを設定するための予告命令を生成させるという作用をもたらす。
【００１８】
また、この第２の側面において、上記予告命令生成部は、上記再利用度生成部により生成された上記再利用度に応じて付与された優先度を含む上記予告命令を生成するようにしてもよい。これにより、予告命令生成部により、履歴メモリの実行履歴を削除するための優先度を含む予告命令を生成させるという作用をもたらす。
【発明の効果】
【００１９】
本発明によれば、実行結果の再利用による再利用区間における処理時間をさらに短縮することができるという優れた効果を奏し得る。
【図面の簡単な説明】
【００２０】
【図１】本発明の第１の実施の形態におけるデータ処理装置の一構成例を示すブロック図である。
【図２】本発明の第１の実施の形態におけるデータ処理部３００および実行結果再利用処理部４００の一構成例を示すブロック図である。
【図３】本発明の第１の実施の形態における履歴メモリ４３０のデータ構造の一例を示す概念図である。
【図４】本発明の第１の実施の形態におけるデータ処理装置１００において識別情報を含む予告命令を受け付けた場合におけるデータ処理装置１００の動作概要を示す概念図である。
【図５】本発明の第１の実施の形態におけるデータ処理装置１００により実行されるプログラムの一部を例示する図である。
【図６】予告命令の実行により関数における処理時間が短縮される例を示す概念図である。
【図７】本発明の第１の実施の形態におけるデータ処理装置１００の実行結果再利用方法の処理手順の一例を示すフローチャートである。
【図８】本発明の第２の実施の形態におけるデータ処理装置１００において参照情報を含む予告命令を受け付けた場合におけるデータ処理装置１００の動作概要を示す概念図である。
【図９】本発明の第２の実施の形態におけるデータ処理装置１００により実行されるプログラムの一部を例示する図である。
【図１０】本発明の第３の実施の形態におけるデータ処理装置１００において予告設定命令を受け付けた場合におけるデータ処理装置１００の動作概要を示す概念図である。
【図１１】本発明の第３の実施の形態におけるデータ処理装置１００により実行されるプログラムの一部を例示する図である。
【図１２】本発明の第４の実施の形態におけるプログラム変換処理装置の一機能構成例を示すブロック図である。
【図１３】本発明の第４の実施の形態におけるプログラム変換処理装置５００により生成される予告命令のデータフォーマットを例示する図である。
【図１４】本発明の第４の実施の形態におけるプログラム変換処理装置５００の予告命令生成処理方法の処理手順の一例を示すフローチャートである。
【図１５】本発明の第４の実施の形態における識別情報を含む予告命令についての予告命令処理（ステップＳ９４０）の処理手順の一例を示すフローチャートである。
【図１６】本発明の第４の実施の形態における参照情報を含む予告命令についての予告命令処理（ステップＳ９５０）の処理手順の一例を示すフローチャートである。
【図１７】本発明の第４の実施の形態における予告設定命令についての予告命令処理（ステップＳ９６０）の処理手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（データ処理制御：識別情報を含む予告命令による実行結果の再利用処理の例）
２．第２の実施の形態（データ処理制御：参照情報を含む予告命令による実行結果の再利用処理の例）
３．第３の実施の形態（データ処理制御：予告設定命令による実行結果の再利用処理の例）
４．第４の実施の形態（プログラム変換制御：予告命令を含むプログラムの生成例）
【００２２】
＜１．第１の実施の形態＞
［データ処理装置の構成例］
図１は、本発明の第１の実施の形態におけるデータ処理装置の一構成例を示すブロック図である。ここでは、集積回路を構成するデータ処理装置１００と、バス１２０と、主記憶部１３０とが示されている。この集積回路は、主記憶部１３０からバス１２０を介して読み出される命令列に従って、データ処理装置１００により処理を実行するものである。
【００２３】
データ処理装置１００は、一次キャッシュ２００と、データ処理部３００と、実行結果再利用処理部４００とを備える。なお、データ処理装置１００は、特許請求の範囲に記載のデータ処理装置の一例である。一次キャッシュ２００は、バス１２０を介して主記憶部１３０から命令およびデータを読み出す際、または、書き込む際の処理によって生じる遅延時間を軽減するためのメモリである。この一次キャッシュ２００は、例えば、ＤＲＡＭ（Dynamic Random Access Memory）により実現される。
【００２４】
この一次キャッシュ２００は、命令キャッシュ２１０およびデータキャッシュ２２０を備える。命令キャッシュ２１０は、主記憶部１３０から読み出された過去の命令を一時的に保持するものである。この命令キャッシュ２１０は、データ処理部３００からの要求に従って、その保持された命令を、命令線２１９を介してデータ処理部３００に出力する。
【００２５】
また、この命令キャッシュ２１０は、データ処理部３００から要求された命令を保持している場合には、その保持している複数の命令のうち、その要求された命令をデータ処理部３００に出力する。一方、データ処理部３００から要求された命令を保持していない場合には、命令キャッシュ２１０は、データ処理部３００により主記憶部１３０から読み出された命令を保持するとともにデータ処理部３００に出力する。
【００２６】
データキャッシュ２２０は、主記憶部１３０から読み出された過去のデータを一時的に保持するものである。このデータキャッシュ２２０は、データ処理部３００からの要求に従って、その保持されたデータを、データ線２２９を介してデータ処理部３００に出力する。また、このデータキャッシュ２２０は、データ処理部３００から要求されたデータを保持している場合には、保持している複数のデータのうち、その要求されたデータをデータ処理部３００に出力する。
【００２７】
一方、データ処理部３００から要求されたデータを保持していない場合には、データキャッシュ２２０は、データ処理部３００により主記憶部１３０から読み出されたデータを保持する。また、データキャッシュ２２０は、主記憶部１３０に書き戻すためのデータがデータ処理部３００から供給された場合には、そのデータを保持する。
【００２８】
データ処理部３００は、主記憶部１３０から読み出された命令に基づく処理を実行するものである。このデータ処理部３００は、例えば、命令キャッシュ２１０を介して主記憶部１３０から命令を読み出して、その読み出された命令に従って、主記憶部１３０に記憶されたデータを、データキャッシュ２２０を介して読み出す。そして、データ処理部３００は、例えば、その読み出されたデータを用いて演算命令に基づく演算処理を実行する。
【００２９】
また、データ処理部３００は、例えば、関数の処理を実行する場合には、データキャッシュ２２０から読み出された関数における引数の入力値を用いて関数の演算処理を実行して、その演算処理の結果である実行結果をデータキャッシュ２２０に出力する。このとき、データ処理部３００は、関数における入力値および実行結果を実行結果再利用処理部４００に出力する。また、このデータ処理部３００は、例えば、プロセッサコアにより実現される。
【００３０】
実行結果再利用処理部４００は、過去に実行された命令区間の入力値と、再び実行される命令区間の入力値とが一致した場合には、その過去に実行された命令区間の実行結果を再利用するものである。ここでは、複数回実行される命令区間のうち、過去に実行された命令区間の実行結果を再利用することができる命令区間を再利用区間という。すなわち、この再利用区間とは、複数回実行される命令区間のうち、命令区間における入力値が同じであれば実行結果も同じとなる命令区間のことである。
【００３１】
この実行結果再利用処理部４００は、複数回実行される再利用区間における入力値および実行結果を実行履歴として保持する。また、この実行結果再利用処理部４００は、再び実行される再利用区間の入力値と、その保持された実行履歴の入力値とが同一である場合には、その保持された実行履歴における実行結果をデータ処理部３００に出力する。これとともに、実行結果再利用処理部４００は、その再利用区間における処理をスキップするための指示をデータ処理部３００に通知する。
【００３２】
実行結果再利用処理部４００は、例えば、再利用区間である関数の引数の入力値と、その保持された実行履歴における入力値とが同一である場合には、その保持された実行履歴における実行結果をデータ処理部３００に出力する。これとともに、実行結果再利用処理部４００は、その関数における処理をスキップするための指示をデータ処理部３００に通知する。
【００３３】
バス１２０は、データ処理装置１００と主記憶部１３０との間の通信を行うものである。このバス１２０は、主記憶部１３０に記憶されているプログラムをデータ処理装置１００に転送する。また、このバス１２０は、データ処理装置１００から出力されたデータを主記憶部１３０に転送する。
【００３４】
主記憶部１３０は、データ処理装置１００に処理を実行させるためのプログラムを記憶するものである。ここでは、このプログラムは、ＡＢＩ（Application Binary Interface）の規定に基づいて生成されたプログラムを想定する。このプログラムは、例えば、ＳＰＡＲＣ（Scalable Processor Architecture） ＡＢＩに基づいて生成されるものである。これにより、データ処理装置１００において、関数における入力値および実行結果が格納される場所を特定することができるため、実行結果の再利用を実現することができる。また、この主記憶部１３０に記憶されているプログラムには、再利用区間である関数が実行される前に、関数における処理の実行を予告する予告命令が挿入されている。
【００３５】
［データ処理部３００および実行結果再利用処理部４００の構成例］
図２は、本発明の第１の実施の形態におけるデータ処理部３００および実行結果再利用処理部４００の一構成例を示すブロック図である。ここでは、主記憶部１３０に予告命令が挿入されたプログラムが記憶されていることを想定している。
【００３６】
データ処理部３００は、フェッチ部３１０と、命令デコーダ３２０と、実行部３３０と、レジスタファイル３４０とを備える。この実行部３３０は、ロードユニット３３１と、入力選択部３３２と、演算回路３３３と、ストアユニット３３４とを備える。また、実行結果再利用処理部４００は、実行履歴検索部４１０と、実行結果出力部４２０と、履歴メモリ４３０とを備える。
【００３７】
フェッチ部３１０は、命令キャッシュ２１０に保持された命令、または、主記憶部１３０に記憶されている命令を、命令線２１９を介して読み出すものである。このフェッチ部３１０は、プログラムカウンタからの指示に従って、命令キャッシュ２１０から命令を読み出す。
【００３８】
また、フェッチ部３１０は、例えば、再利用区間である関数の呼出し命令の実行を予告する予告命令を読み出した後に、その関数における引数の入力値を設定するための入力値設定命令を読み出す。そして、その入力値設定命令の後に、フェッチ部３１０は、その関数を呼び出す呼出し命令を読み出す。すなわち、フェッチ部３１０は、再利用区間である関数の呼出し命令を読み出す前に、その関数に対応する予告命令および入力値設定命令を読み出す。
【００３９】
また、フェッチ部３１０は、その読み出された命令を命令デコーダ３２０に供給する。また、実行履歴検索部４１０により実行結果が抽出された場合には、フェッチ部３１０は、例えば、実行結果を設定するための命令を、実行履歴検索部４１０からの通知に基づいて命令デコーダ３２０に供給する。
【００４０】
命令デコーダ３２０は、フェッチ部３１０から供給された命令を解読（デコード）して、その解読内容に基づいて、実行部３３０、レジスタファイル３４０および実行履歴検索部４１０を制御するものである。この命令デコーダ３２０は、関数の実行を予告する予告命令を受け付けた場合には、その予告命令により特定される識別情報を実行履歴検索部４１０に供給する。ここにいう識別情報とは、複数の再利用区間である関数を互いに識別するための情報であり、履歴メモリ４３０に保持された実行履歴を検索するための検索キーとして用いられるものである。すなわち、命令デコーダ３２０は、予告命令によって、予告命令により特定される再利用区間である関数を実行する前に、その関数を識別するための識別情報を実行履歴検索部４１０に保持される。
【００４１】
命令デコーダ３２０は、例えば、識別情報を含む予告命令を受け付けたときは、その識別情報を履歴メモリ４３０に入力させるために、その識別情報を実行履歴検索部４１０に供給する。また、その識別情報として関数の先頭アドレスを用いる場合において、レジスタファイル３４０に関数の先頭アドレスが既に格納されているときは、命令デコーダ３２０は、その関数の先頭アドレスを参照するための参照情報を含む予告命令により識別情報を特定する。
【００４２】
このとき、命令デコーダ３２０は、その予告命令に含まれる参照情報に基づいて、レジスタファイル３４０に格納された関数の先頭アドレスを実行履歴検索部４１０に出力させる。すなわち、命令デコーダ３２０は、実行部３３０に対し、参照情報を含む予告命令に基づいて、識別情報である関数の先頭アドレスを実行履歴検索部４１０に出力させる。
【００４３】
また、識別情報として関数の先頭アドレスを用いる場合において、関数の先頭アドレスをレジスタファイル３４０に設定するためのアドレス設定命令を予告命令とするときは、命令デコーダ３２０は、その予告命令に含まれる設定情報に基づいて識別情報を特定する。
【００４４】
このとき、命令デコーダ３２０は、入力選択部３３２を介して、その予告命令に指定された設定情報が示すレジスタファイル３４０における設定先に、関数の先頭アドレスを設定する。これとともに、命令デコーダ３２０は、入力選択部３３２から出力される関数の先頭アドレスを取得するように実行履歴検索部４１０に指示する。このようなアドレス設定命令である予告命令を、ここでは予告設定命令という。したがって、命令デコーダ３２０は、実行部３３０に対し、関数の先頭アドレスの設定先が示された設定情報を含む予告設定命令に基づいて、識別情報である関数の先頭アドレスを設定先に設定させるとともに、実行履歴検索部４１０に出力させる。
【００４５】
また、命令デコーダ３２０は、関数の実行を予告する予告命令の後に受け付けた命令が、関数における引数の入力値を設定するための入力値設定命令であるか否かを判断する。この命令デコーダ３２０は、例えば、ＡＢＩの規定に基づいて入力値設定命令であるか否かを判断する。
【００４６】
この例において、ＭＩＰＳ（Microprocessor without Interlocked Pipeline Stages）のＡＢＩの規定に基づく判断例について簡単に説明する。ＭＩＰＳの規定では、引数の入力値が全て整数である場合には、４つのレジスタ４乃至７に入力値が格納され、引数が５つ以上のときには、５つ目以上の引数の入力値が主記憶部１３０のスタック領域にスタックされる。具体的には、５つ目以上の引数の入力値は、レジスタファイル３４０におけるレジスタ２９に格納されたスタックポイント値に１６以上の値を加算した値に対応するスタック領域にスタックされる。
【００４７】
したがって、命令デコーダ３２０は、例えば、ロードワード命令（ｌｗ）に示された転送先レジスタがレジスタ４乃至７である場合には、関数における引数の入力値を設定する入力値設定命令と判断する。また、命令デコーダ３２０は、引数が５以上であり、その引数の全ての入力値が整数である場合において、ストアワード命令（ｓｗ）に示された転送先レジスタがレジスタ２９であり、かつ、オフセット値が「１６」以上を示すときは、入力値設定命令と判断する。
【００４８】
そして、入力値設定命令と判断された場合には、命令デコーダ３２０は、入力選択部３３２から出力されるデータを引数の入力値として取得させるための取得信号を実行履歴検索部４１０に供給する。すなわち、命令デコーダ３２０は、予告命令から、関数を呼び出すための呼出し命令の直前の命令までの命令群のうち、関数の入力値を設定するための入力値設定命令に基づいて、引数の入力値を実行履歴検索部４１０に取得させるように制御する。
【００４９】
また、この命令デコーダ３２０は、例えば、主記憶部１３０から読み出された関数の入力値を設定するための入力値設定命令を受け付けた場合には、ロードユニット３３１から読み出された入力値をレジスタファイル３４０に格納するように制御する。これとともに、命令デコーダ３２０は、実行履歴検索部４１０に対し取得信号を供給する。
【００５０】
また、命令デコーダ３２０は、例えば、レジスタファイル３４０に格納された関数の入力値を設定するための入力値設定命令を受け付けた場合には、レジスタファイル３４０における１つのレジスタに格納された入力値を他のレジスタに転送するように制御する。これとともに、命令デコーダ３２０は、実行履歴検索部４１０に対し取得信号を供給する。
【００５１】
そして、命令デコーダ３２０は、入力値設定命令の後に、関数の先頭アドレスを呼び出すための呼出し命令を受け付けた場合には、関数に用いられる全ての入力値の設定が終了した旨を示す入力値終了信号を実行履歴検索部４１０に供給する。すなわち、この命令デコーダ３２０は、識別情報に対応する関数を呼び出すための呼出し命令を受け付けた場合には、入力値終了信号を実行履歴検索部４１０に供給する。また、命令デコーダ３２０は、実行履歴を削除する際の優先度が予告命令に含まれる場合には、その優先度を実行履歴検索部４１０に供給する。
【００５２】
実行部３３０は、命令デコーダ３２０からの制御に従って処理を実行するものである。すなわち、この実行部３３０は、複数回実行される命令区間である再利用区間が含まれる命令列に基づく処理を実行する。また、実行部３３０は、例えば、参照情報を含む予告命令が命令デコーダ３２０に供給された場合には、参照情報に示されたレジスタに格納された関数の先頭アドレスを識別情報として実行履歴検索部４１０に出力する。
【００５３】
また、実行部３３０は、例えば、予告設定命令が命令デコーダ３２０に供給された場合には、予告設定命令に含まれる関数の先頭アドレスの設定先を示す設定情報に基づいて、関数の先頭アドレスを設定先に設定する。すなわち、実行部３３０は、予告設定命令の設定情報に基づいて関数の先頭アドレスをレジスタファイル３４０に設定するとともに、関数の先頭アドレスを識別情報として実行履歴検索部４１０に出力する。
【００５４】
また、この実行部３３０は、再利用区間である関数の入力値および実行結果をレジスタファイル３４０または主記憶部１３０に出力するとともに、実行履歴検索部４１０に供給する。なお、実行部３３０は、特許請求の範囲に記載の実行部の一例である。
【００５５】
ロードユニット３３１は、命令デコーダ３２０からの制御に従って、主記憶部１３０またはデータキャッシュ２２０からデータを読み出して、その読み出されたデータを入力選択部３３２に供給するものである。このロードユニット３３１は、例えば、命令デコーダ３２０からの制御に従って、主記憶部１３０またはデータキャッシュ２２０から関数における引数の入力値を読み出して、その読み出された入力値を入力選択部３３２に供給する。
【００５６】
入力選択部３３２は、命令デコーダ３２０からの制御に従って、実行結果出力部４２０、演算回路３３３、レジスタファイル３４０および実行結果出力部４２０から出力されたデータのうち、いずれか１つのデータを選択するものである。この入力選択部３３２は、その選択されたデータを、レジスタファイル３４０および実行履歴検索部４１０に出力する。すなわち、入力選択部３３２は、命令デコーダ３２０の制御に従って、実行結果出力部４２０、演算回路３３３、レジスタファイル３４０および実行結果出力部４２０の出力のうち、いずれかをレジスタファイル３４０および実行履歴検索部４１０に出力する。
【００５７】
この入力選択部３３２は、例えば、命令デコーダ３２０に入力値設定命令としてロード命令が供給された場合には、命令デコーダ３２０の制御に従って、ロードユニット３３１からのデータを、レジスタファイル３４０および実行履歴検索部４１０に出力する。また、この入力選択部３３２は、命令デコーダ３２０に入力値設定命令としてムーブ命令が供給された場合には、命令デコーダ３２０の制御に従って、レジスタファイル３４０から出力されたデータを、レジスタファイル３４０および実行履歴検索部４１０に出力する。
【００５８】
また、入力選択部３３２は、演算処理を実行するための演算命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０の制御に従って、演算回路３３３から出力された演算結果を実行結果として、レジスタファイル３４０に出力する。また、この入力選択部３３２は、実行履歴検索部４１０により実行結果が抽出された場合には、命令デコーダ３２０からの制御に従って、実行結果出力部４２０から出力された実行結果をレジスタファイル３４０に出力する。
【００５９】
演算回路３３３は、命令デコーダ３２０からの制御に従って、演算処理を実行するものである。この演算回路３３３は、例えば、乗算、除算または積和などの演算処理を実行するための演算命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０の制御に従って、レジスタファイル３４０に格納されたデータを用いて演算処理を実行する。また、演算回路３３３は、その演算処理による演算結果を実行結果として、入力選択部３３２を介してレジスタファイル３４０に格納する。
【００６０】
ストアユニット３３４は、命令デコーダ３２０からの制御に従って、レジスタファイル３４０に格納されたデータ、または、実行結果出力部４２０から出力された実行結果を主記憶部１３０に書き戻すためのものである。このストアユニット３３４は、主記憶部１３０にデータを書き戻すためのストア命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０からの制御に従って、書き戻すべきデータを、データ線２２９を介してデータキャッシュ２２０に出力する。また、このストアユニット３３４は、実行履歴検索部４１０により実行結果が抽出された場合には、実行結果出力部４２０から出力された実行結果を、データ線２２９を介して主記憶部１３０およびデータキャッシュ２２０に書き戻す。
【００６１】
レジスタファイル３４０は、実行部３３０から出力されたデータを保持するものである。このレジスタファイル３４０は、複数のレジスタ、例えば、３２個のレジスタ０乃至３１により構成される。このレジスタファイル３４０は、命令デコーダ３２０からの制御に従って、実行部３３０から出力されたデータを、複数のレジスタのうち、１つのレジスタに格納する。
【００６２】
また、このレジスタファイル３４０は、例えば、命令デコーダ３２０からの制御に従って、複数のレジスタのうち１つのレジスタに格納されたデータを実行結果として実行部３３０または実行部３３０を介して実行履歴検索部４１０に出力する。また、このレジスタファイル３４０は、例えば、命令デコーダ３２０からの制御に従って、複数のレジスタのうち１つのレジスタに格納された関数の先頭アドレスを識別情報として実行部３３０を介して実行履歴検索部４１０に出力する。
【００６３】
実行履歴検索部４１０は、履歴メモリ４３０において識別情報ごとに保持された再利用区間における入力値および実行結果である実行履歴のうち、予告命令に基づいて取得された識別情報および入力値と同一の実行履歴における実行結果を検索するものである。この実行履歴検索部４１０は、予告命令に基づいて特定された識別情報および入力値を保持して、その保持された識別情報および入力値を履歴メモリ４３０に出力することによって、実行履歴の検索を行う。
【００６４】
この実行履歴検索部４１０は、命令デコーダ３２０の指示に従って、予告命令により特定される識別情報を取得する。この実行履歴検索部４１０は、例えば、識別情報を含む予告命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０から出力された識別情報を保持する。また、この実行履歴検索部４１０は、例えば、参照情報を含む予告命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０からの制御に従って、レジスタファイル３４０から出力された関数の先頭アドレスを識別情報として取得する。
【００６５】
さらに、この実行履歴検索部４１０は、例えば、予告設定命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０からの制御に従って、入力選択部３３２を介して、レジスタファイル３４０に格納される関数の先頭アドレスを識別情報として取得する。その識別情報が取得された後に、実行履歴検索部４１０は、入力値設定命令が命令デコーダ３２０に供給されるたびに、命令デコーダ３２０から出力される取得信号に基づいて関数の入力値を取得する。
【００６６】
すなわち、実行履歴検索部４１０は、実行部３３０から出力された識別情報である関数の先頭アドレスと、その関数の入力値とに基づいて、履歴メモリ４３０に保持された実行履歴における実行結果を検索する。そして、実行履歴検索部４１０は、関数を呼び出す呼出し命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０からの入力値終了信号に基づいて、履歴メモリ４３０に対する検索を終了する。
【００６７】
実行履歴検索部４１０は、履歴メモリ４３０から実行結果が抽出された場合には、その実行結果を実行結果出力部４２０に出力する。これとともに、実行履歴検索部４１０は、関数の処理を省略するための省略信号として、その抽出された実行結果における格納場所に関する情報をフェッチ部３１０に供給する。
【００６８】
一方、履歴メモリ４３０から実行結果が抽出されない場合には、実行履歴検索部４１０は、実行部３３０において予告命令により識別された関数における処理が実行された後に、実行部３３０から出力された実行結果を取得する。そして、実行履歴検索部４１０は、その関数の実行結果と、予告命令に基づいて取得された識別情報および入力値とを履歴メモリ４３０に保持させる。すなわち、履歴メモリ４３０から実行結果が抽出されない場合には、実行履歴検索部４１０は、予告命令の後に実行される関数の実行結果と、予告命令により保持された関数の識別情報および入力値を履歴メモリ４３０に登録する。
【００６９】
この例において、関数における処理の実行を終了するためのリターン命令が命令デコーダ３２０に供給された場合には、命令デコーダ３２０の制御によって、実行履歴検索部４１０は、レジスタファイル３４０に格納される実行結果を取得する。これにより、実行履歴検索部４１０は、予告命令により特定された関数の識別情報に対応する入力値および実行結果を関連付けて履歴メモリ４３０に保持させることができる。
【００７０】
また、実行履歴を削除する際の優先度が予告命令に含まれる場合には、実行履歴検索部４１０は、命令デコーダ３２０からの優先度と、優先度に対応する関数の入力値および実行結果とを関連付けて実行履歴として識別情報ごとに履歴メモリ４３０に保持させる。この場合において、実行履歴検索部４１０は、履歴メモリ４３０に保持された優先度に基づいて、履歴メモリ４３０における実行履歴を削除する。すなわち、実行履歴検索部４１０は、優先度が最も大きい識別情報に関連付けられた実行履歴から順番に、履歴メモリ４３０における実行履歴を削除する。なお、実行履歴検索部４１０は、特許請求の範囲に記載の実行履歴検索部の一例である。
【００７１】
実行結果出力部４２０は、実行履歴検索部４１０によって履歴メモリ４３０から実行結果が抽出された場合には、その実行結果を、入力選択部３３２を介してレジスタファイル３４０に、または、ストアユニット３３４に出力するものである。この実行結果出力部４２０は、実行結果の格納場所によって、ストアユニット３３４または入力選択部３３２に実行結果のデータを出力する。なお、実行結果出力部４２０は、特許請求の範囲に記載の実行結果出力部の一例である。
【００７２】
履歴メモリ４３０は、識別情報ごとに識別情報に対応する入力値および実行結果を関連付けて実行履歴として保持するものである。この履歴メモリ４３０は、例えば、連想メモリ（ＣＡＭ：Content Addressable Memory）により実現される。この例において、履歴メモリ４３０は、実行結果を検索するための検索キーである識別情報が実行履歴検索部４１０から入力されることによって、その識別情報に関連付けられた実行履歴の検索を開始する。
【００７３】
また、この履歴メモリ４３０は、実行履歴検索部４１０から順次供給された入力値と、履歴メモリ４３０に保持されている入力値とが全て一致する場合には、その保持された入力値に関連付けられた実行結果を実行履歴検索部４１０に出力する。すなわち、実行履歴検索部４１０から入力された識別情報および入力値と同一の実行履歴が履歴メモリ４３０から検出されることによって、実行履歴検索部４１０により履歴メモリ４３０から実行結果が抽出される。なお、履歴メモリ４３０は、特許請求の範囲に記載の履歴メモリの一例である。
【００７４】
また、履歴メモリ４３０は、例えば、実行履歴検索部４１０から供給された優先度と、優先度に対応する関数の入力値および実行結果とを関連付けて実行履歴として識別情報ごとに保持する。また、この連想メモリにより実現される履歴メモリ４３０は、例えば、実行履歴における入力値のパターンを木構造により保持する。ここで、履歴メモリ４３０におけるデータ構造の例について図面を参照して以下に説明する。
【００７５】
［履歴メモリ４３０のデータ構造例］
図３は、本発明の第１の実施の形態における履歴メモリ４３０のデータ構造の一例を示す概念図である。ここでは、履歴メモリ４３０により、複数の関数を互いに識別する識別情報ごとに保持された実行履歴のうち、１つの識別情報における実行履歴を木構造により保持する構成が示されている。この例では、引数がｎ個であり、かつ、実行結果である出力をｍ個の格納先に返す関数を想定している。また、ここでは、関数の先頭アドレスである関数アドレスを識別情報として用いることとする。
【００７６】
この例では、木構造における関数ルート４４０と、第１の引数ノード４５１および４５２と、第ｎの引数ノード４６１乃至４６４と、第１の出力ノード４７１乃至４７４と、第ｍの出力ノード４８１乃至４８４とが示されている。
【００７７】
関数ルート４４０には、識別情報である関数アドレスと、第１の引数ノード４５１を指し示すポインタとが示されている。
【００７８】
第１および第ｎの引数ノード４５１、４５２および４６１乃至４６４には、履歴メモリ４３０に保持されている実行履歴における引数の入力値として、引数の値を示す入力データと、その引数の型と、その引数の格納場所を示す種類とが示されている。ここにいう格納場所とは、レジスタファイル３４０のレジスタ番号または主記憶部１３０のメモリアドレスのことをいう。
【００７９】
さらに、第１および第ｎの引数ノード４５１、４５２および４６１乃至４６４には、比較対象の入力値が互いに一致した場合に次の引数における引数ノードを指し示す右ポインタと、不一致の場合に同一の引数における他の引数ノードを指し示す下ポインタとが示されている。また、第ｎの引数ノード４６１乃至４６４の各々に、第１および第ｍの出力ノード４７１乃至４７４および４８１乃至４８４がそれぞれ連結されている。
【００８０】
第１および第ｍの出力ノード４７１乃至４７４および４８１乃至４８４には、履歴メモリ４３０に保持されている実行履歴における実行結果として、実行結果の値を示す出力データと、その実行結果の格納場所を示す種類と、その実行結果の型とが示されている。さらに、第１の出力ノード４７１乃至４７４には、次の出力ノードを指し示す右ポインタが示されている。この第１および第ｍの出力ノード４７１乃至４７４および４８１乃至４８４は、連結リストを構成している。また、第ｍの出力ノード４８１乃至４８４の右ポインタには、出力ノードの終端を表わすヌルが示されている。
【００８１】
このような木構造において、関数ルート４４０に示された関数アドレスと一致する関数アドレスが実行履歴検索部４１０から入力されると、関数ルート４４０のポインタによって指し示された第１の引数ノード４５１において入力値の比較処理が実行される。ここにいう入力値の比較処理とは、第１の引数ノード４５１に示された入力データ、種類および型である入力値と、実行履歴検索部４１０からの入力値とを比較することである。
【００８２】
このとき、例えば、第１の引数ノード４５１に示された入力値と実行履歴検索部４１０からの入力値とが一致した場合には、第１の引数ノード４５１の右ポインタにより指し示された次の引数ノードにおいて入力値の比較処理が実行される。一方、第１の引数ノード４５１に示された入力値と、実行履歴検索部４１０からの入力値とが一致しない場合には、第１の引数ノード４５１の下ポインタにより指し示された第１の引数ノード４５２において入力値の比較処理が実行される。
【００８３】
このようにして、各引数ノードにおける比較処理による結果に基づいて右または下ポインタの指し示す引数ノードが選択され、その選択された引数ノードにおいて入力値の比較処理が順次実行される。例えば、第ｎの引数ノード４６１に示された入力値と、実行履歴検索部４１０からの入力値とが互いに一致した場合には、第ｎの引数ノード４６１の右ポインタにより第１の出力ノード４７１が指し示される。そして、第１の出力ノード４７１に保持された出力データ、種類および型を示す実行結果から順番に、第ｍ番の出力ノード４８１に保持された実行結果までが実行履歴検索部４１０に順次出力される。
【００８４】
このように、履歴メモリ４３０を識別情報ごとに木構造により構成することによって、同じ引数の入力値を重複して保持させる必要が無いため、記憶領域を節約することができる。また、識別情報ごとにデータ構造を分けることによって、検索速度の低下を抑制することができる。
【００８５】
［識別情報を含む予告命令によるデータ処理装置１００の動作例］
図４は、本発明の第１の実施の形態におけるデータ処理装置１００において識別情報を含む予告命令を受け付けた場合におけるデータ処理装置１００の動作概要を示す概念図である。図４（ａ）は、アセンブリ言語により記述された命令列の一部を例示する図である。図４（ａ）には、インデックス（ｉｎｄｅｘ）を指定する予告命令（ｎｏｔｉｃｅＣａｌｌ）と、関数（ｆｕｎｃ）を呼び出すコール命令（Ｃａｌｌ）とが示されている。
【００８６】
図４（ｂ）は、履歴メモリ４３０における識別情報ごとの実行履歴検索データの一例を示す概念図である。図４（ｂ）には、インデックス（ｉｎｄｅｘ）により示される識別情報（インデックス０乃至ｋ）の列４３１と、実行履歴検索データ（実行履歴検索データ０乃至ｋ）の列４３２との対応が示されている。ここにいう実行履歴検索データは、図３に示した木構造により構成される検索データのことを示す。
【００８７】
この場合において、予告命令（ｎｏｔｉｃｅＣａｌｌ）が命令デコーダ３２０に供給されることによって、インデックス（ｉｎｄｅｘ）により示される識別情報「インデックスｋ」が、命令デコーダ３２０から実行履歴検索部４１０に供給される。そして、実行履歴検索部４１０により、識別情報「インデックスｋ」が履歴メモリ４３０に入力されることによって、この識別情報（インデックスｋ）によって識別される関数（ｆｕｎｃ）における「実行履歴検索データｋ」に基づいて、実行履歴の検索が開始される。
【００８８】
その後、関数における引数の入力値を設定する入力値設定命令に基づいて、実行履歴検索部４１０において、関数（ｆｕｎｃ）の引数の入力値が取得され、その取得された入力値が履歴メモリ４３０に順次入力される。これにより、識別情報「インデックスｋ」に対応する実行履歴検索データ（実行履歴検索データｋ）に保持された入力値と、実行履歴検索部４１０からの入力値との比較が順次行われる。
【００８９】
そして、コール命令（ｃａｌｌ）が命令デコーダ３２０に供給されることによって、実行履歴検索部４１０により取得された識別情報および入力値と一致する実行履歴の有無が履歴メモリ４３０から実行履歴検索部４１０に通知される。すなわち、実行履歴検索部４１０により、実行履歴検索データｋによる検索結果として関数（ｆｕｎｃ）の再利用できる実行結果の有無がコール命令（ｃａｌｌ）に基づいて参照される。
【００９０】
このとき、履歴メモリ４３０から実行結果が出力された場合には、関数（ｆｕｎｃ）の実行が省略される。一方、実行結果が出力されない場合には、関数（ｆｕｎｃ）が実行されて、その実行された実行結果と、実行履歴検索部４１０によって既に取得された識別情報および入力値とが履歴メモリ４３０に保持される。
【００９１】
このように、データ処理装置１００は、関数（ｆｕｎｃ）のコール命令（ｃａｌｌ）を実行する前において、予告命令（ｎｏｔｉｃｅＣａｌｌ）に基づいて関数（ｆｕｎｃ）の引数の入力値を取得する。そして、その関数（ｆｕｎｃ）の入力値と、履歴メモリ４３０に保持された関数（ｆｕｎｃ）の入力値との比較を終了させる。次に、識別情報を含む予告命令によるデータ処理装置１００におけるより具体的な動作例について、ＭＩＰＳによる命令コードを示す図面を参照して説明する。
【００９２】
［識別情報を含む予告命令による動作例］
図５は、本発明の第１の実施の形態におけるデータ処理装置１００により実行されるプログラムの一部を例示する図である。図５（ａ）は、再利用区間として選択された関数のソースプログラムの一部の例を示す図である。図５（ｂ）は、図５（ａ）に示したソースプログラムがＭＩＰＳのアセンブリ言語により変換された命令列の一部を例示する図である。
【００９３】
図５（ａ）の上段には、５つの引数（ａ乃至ｅ）を持つ関数（ｆｕｎｃ）の呼出しが記述されている。下段には、イント（ｉｎｔ）型の関数（ｆｕｎｃ）の定義が記述されている。この関数（ｆｕｎｃ）は、イント（ｉｎｔ）型の引数として、第１の引数（ａ）、第２の引数（ｂ）、第３の引数（ｃ）、第４の引数（ｄ）および第５の引数（ｅ）を持つ。このようなソースプログラムに対し、ＭＩＰＳのアセンブリ言語により変換するとともに予告命令の挿入処理を施すことによって生成された命令列の一部が図５（ｂ）に示されている。
【００９４】
図５（ｂ）には、第１の命令列（ｎｏｔｉｃｅＣａｌｌ）、第２の命令列（ｌｗ）、第３の命令列（ｌｗ）、第４の命令列（ｍｏｖｅ）、第５の命令列（ｍｏｖｅ）、第６の命令列（ｓｗ）、第７の命令列（ｌｗ）および第８の命令列（ｊａｌｒ）が示されている。ここでは、第１乃至第５引数の入力値Ａ乃至Ｅが全て整数であることを想定している。
【００９５】
第１の命令列において、インデックス（ｉｎｄｅｘ）を指定する予告命令（ｎｏｔｉｃｅＣａｌｌ）が実行される。これにより、命令デコーダ３２０により供給されたインデックス（ｉｎｄｅｘ）により示された識別情報が実行履歴検索部４１０から履歴メモリ４３０に入力されることによって、実行履歴の検索が行われる。
【００９６】
第２の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスにオフセット値「１０００」が加算され、その加算された値によって指定される主記憶部１３０のメモリアドレスに記憶されたデータ（第１の引数の入力値Ａ）がレジスタ４（Ｒ４）に転送される。
【００９７】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示された転送先レジスタ番号が「Ｒ４」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ４（Ｒ４）に転送される入力値Ａが実行履歴検索部４１０にも供給されて、履歴メモリ４３０に保持されている第１の引数の入力値と比較される。このとき、履歴メモリ４３０に保持された第１の引数の入力値のうち、入力値Ａが保持されていれば、第２の引数の入力値の比較処理に進む。一方、入力値Ａが保持されていない場合には、実行履歴の検索を終了する。
【００９８】
第３の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスにオフセット値「１００４」が加算され、その加算された値によって指定される主記憶部１３０のメモリアドレスに記憶されたデータ（第２の引数の入力値Ｂ）がレジスタ５（Ｒ５）に転送される。
【００９９】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示される転送先レジスタ番号が「Ｒ５」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ５（Ｒ５）に格納される入力値Ｂが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第２の引数の入力値と比較される。このとき、履歴メモリ４３０に保持された第２の引数の入力値のうち、入力値Ｂが保持されていれば、第３の引数の入力値の比較処理に進む。一方、入力値Ｂが保持されていない場合には、実行履歴の検索を終了する。
【０１００】
第４の命令列において、ムーブ命令（ｍｏｖｅ）が実行される。これにより、レジスタ１０（Ｒ１０）に格納されているデータ（第３の引数の入力値Ｃ）がレジスタ６（Ｒ６）に転送される。このムーブ命令（ｍｏｖｅ）は、その転送先レジスタ番号が「Ｒ６」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ６（Ｒ６）に格納される入力値Ｃが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第３の引数の入力値と比較される。
【０１０１】
このとき、履歴メモリ４３０に保持された第３の引数の入力値のうち入力値Ｃが保持されていれば、第４の引数の入力値の比較処理に進む。一方、入力値Ｃが保持されていない場合には、実行履歴の検索を終了する。
【０１０２】
第５の命令列において、ムーブ命令（ｍｏｖｅ）が実行される。これにより、レジスタ１１（Ｒ１１）に格納されているデータ（第４の引数の入力値Ｄ）がレジスタ７（Ｒ７）に転送される。このムーブ命令（ｍｏｖｅ）は、そのムーブ命令（ｍｏｖｅ）に示される転送先レジスタ番号が「Ｒ７」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ７（Ｒ７）に格納される入力値Ｄが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第４の引数の入力値と比較される。
【０１０３】
このとき、履歴メモリ４３０に保持された第４の引数の入力値のうち入力値Ｄが保持されていれば、第５の引数の入力値の比較処理に進む。一方、入力値Ｄが保持されていない場合には、実行履歴の検索を終了する。
【０１０４】
第６の命令列において、ストアワード命令（ｓｗ）が実行される。これにより、レジスタ２９（Ｒ２９）に格納されているスタックポインタの値に「１６」が加算され、その加算された値のメモリアドレスにレジスタ１２（Ｒ１２）に格納されているデータ（第５の引数の入力値Ｅ）が転送される。このストアワード命令（ｓｗ）は、そのストアワード命令（ｓｗ）に示される転送先レジスタ番号が「Ｒ２９」であり、オフセット値が「１６」以上であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。
【０１０５】
これにより、主記憶部１３０に転送された入力値Ｅが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第５の引数の入力値と比較される。このとき、履歴メモリ４３０に保持された第５の引数の入力値のうち、入力値Ｅが保持されていれば、全ての引数の入力値Ａ乃至Ｅが一致する実行履歴における実行結果が実行履歴検索部４１０に出力される。一方、入力値Ａが保持されていない場合には、実行履歴の検索を終了する。
【０１０６】
第７の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスに、オフセット値「２０００」が加算され、その加算された値のメモリアドレスに記憶されたデータ（関数ｆｕｎｃの先頭アドレス）がレジスタ２５（Ｒ２５）に転送される。
【０１０７】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示される転送先レジスタ番号が「Ｒ２５」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令でないと判断される。このため、実行履歴検索部４１０により、入力選択部３３２から出力されたデータは取得されない。
【０１０８】
第８の命令列において、ジャンプ命令（ｊａｌｒ）が実行される。これにより、レジスタ２５（Ｒ２５）に格納されている関数（ｆｕｎｃ）の先頭アドレスの命令が読み出される。このとき、命令デコーダ３２０により、関数（ｆｕｎｃ）における全ての第１乃至第５引数の入力値の設定が終了したことを示す入力値終了信号が実行履歴検索部４１０に通知される。
【０１０９】
このとき、履歴メモリ４３０から実行結果が出力されていれば、実行履歴検索部４１０により、その実行結果が実行結果出力部４２０に出力されるとともに、関数（ｆｕｎｃ）の処理を省略するための省略信号がフェッチ部３１０に供給される。一方、履歴メモリ４３０から実行結果が出力されていなければ、実行履歴検索部４１０により、関数（ｆｕｎｃ）の実行後の実行結果と、予告命令に基づいて取得された識別情報および入力値とが履歴メモリ４３０に登録される。
【０１１０】
次に、履歴メモリ４３０に保持された実行履歴と、実行履歴検索部４１０により取得された識別情報および入力値とが一致した場合において予告命令により関数の処理時間が短縮される例について以下に図面を参照して説明する。
【０１１１】
［データ処理装置１００による関数処理の時間短縮例］
図６は、予告命令の実行により関数における処理時間が短縮される例を示す概念図である。図６（ａ）は、予告命令のないプログラムの処理を実行する従来のデータ処理装置における実行結果の再利用による短縮時間を示す概念図である。図６（ｂ）は、本発明の第１の実施の形態におけるデータ処理装置１００における実行結果の再利用による短縮時間を示す概念図である。
【０１１２】
図６（ａ）および（ｂ）では、上位ルーチンにおいて２つの引数を持つ関数がコール命令（ｃａｌｌ）によって呼び出され、その関数における処理の終了に伴うリターン命令（ｒｅｔｕｒｎ）によって下位ルーチンから復帰する例が示されている。また、ここでは、左から右に時間が経過することとする。
【０１１３】
図６（ａ）には、上位ルーチンにおける入力値Ａ設定３２１および入力値Ｂ設定３２２と、下位ルーチンにおける入力値Ａ使用３２３および入力値Ｂ使用３２４とが示されている。
【０１１４】
入力値Ａ設定３２１および入力値Ｂ設定３２２は、関数における引数の入力値が設定されるタイミングを示す。これは、図１で述べたとおり、ＡＢＩの規定に従って記述されたプログラムによる処理手順である。また、入力値Ａ使用３２３および入力値Ｂ使用３２４は、下位ルーチンである関数の処理において引数である入力値が使用されるタイミングを示す。
【０１１５】
この場合には、下位ルーチンにおいて２つの引数が全て使用（入力値Ｂ使用３２４）されるまで、関数の引数である入力値ＡおよびＢを特定することができない。このため、関数の引数である入力値ＡおよびＢが、履歴メモリ４３０に保持されている入力値と全て一致したときであっても、入力値Ｂ使用３２４からリターン命令（ｒｅｔｕｒｎ）までの短縮期間ｔ１だけしか関数の処理時間を削減することができない。
【０１１６】
図６（ｂ）には、図６（ａ）に示したタイミングに加えて予告命令４２１が示されている。この予告命令４２１は、命令デコーダ３２０によって予告命令がデコードされるタイミングを示す。予告命令４２１以外は、図６（ａ）と同様のものを示しているため、図６（ａ）と同一符号を付してここでの説明を省略する。
【０１１７】
この場合には、関数を識別するための識別情報が予告命令４２１により特定されるため、履歴メモリ４３０の検索キーである識別情報を履歴メモリ４３０に入力することによって、関数の実行履歴の検索が開始される。そして、実行履歴検索部４１０により、引数の入力値ＡおよびＢを設定するための２つの入力値設定命令に基づいて取得された入力値ＡおよびＢが、履歴メモリ４３０に供給される。
【０１１８】
その後、コール命令（ｃａｌｌ）に基づいて、その取得された入力値ＡおよびＢと、履歴メモリ４３０に保持されている入力値とが全て一致したか否かが判断される。そして、全て一致した場合には、関数である下位ルーチン（ｃａｌｌからｒｅｔｕｒｎまで）の処理に要する短縮期間ｔ２が削減される。
【０１１９】
このように、データ処理装置１００は、予告命令に含まれる識別情報および引数の入力値を予告命令に基づいて取得することによって、実行履歴検索期間ｔにおいて履歴メモリ４３０に対する実行結果の検索を終了させることができる。これにより、履歴メモリ４３０に保持された実行結果が再利用できる場合には、短縮することができる期間（短縮期間ｔ２）を、従来の短縮期間ｔ１よりも長くすることができる。
【０１２０】
［データ処理装置１００の動作例］
次に本発明の実施の形態におけるデータ処理装置１００の動作について図面を参照して説明する。
【０１２１】
図７は、本発明の第１の実施の形態におけるデータ処理装置１００の実行結果再利用方法の処理手順の一例を示すフローチャートである。
【０１２２】
まず、命令デコーダ３２０により、フェッチ部３１０から供給された予告命令が解読される（ステップＳ９１１）。そして、命令デコーダ３２０により、予告命令により特定された識別情報である履歴メモリ４３０の検索キーが実行履歴検索部４１０に供給されることによって、実行履歴検索部４１０において識別情報が取得される。すなわち、実行履歴検索部４１０により、予告命令に含まれる識別情報が取得されて、その取得された識別情報が実行履歴検索部４１０から履歴メモリ４３０に入力される（ステップＳ９１２）。これにより、履歴メモリ４３０における識別情報に対応する複数の実行履歴の検索が開始される。なお、ステップＳ９１２は、特許請求の範囲に記載の取得手順の一例である。
【０１２３】
続いて、フェッチ部３１０により、予告命令の次に実行されるべき命令が読み出される（ステップＳ９１３）。この後、命令デコーダ３２０により、フェッチ部３１０から読み出された命令が、関数の第１の引数の入力値を設定するための入力値設定命令か否かが判断される（ステップＳ９１４）。
【０１２４】
そして、入力値設定命令であると判断された場合には、命令デコーダ３２０により、入力値設定命令によって設定された引数の入力値が実行履歴検索部４１０に供給されることによって、実行履歴検索部４１０において引数の入力値が取得される（ステップＳ９２１）。なお、ステップＳ９２１は、特許請求の範囲に記載の取得手順の一例である。
【０１２５】
続いて、実行履歴検索部４１０により取得された引数の入力値が、履歴メモリ４３０における識別情報に関連付けられた引数の入力値と一致するか否かが判断される（ステップＳ９２２）。そして、両者の入力値が一致しない場合には、ステップＳ９１３の処理に戻る。
【０１２６】
一方、両者の入力値が一致した場合には、履歴メモリ４３０において、次の引数の入力値を比較するための次の引数ノードにポインタが進められて（ステップＳ９２３）、ステップＳ９１３の処理に戻る。すなわち、複数の引数ノードのうち、実行履歴検索部４１０からの入力値と一致する引数ノードがあれば、その引数ノードの右ポインタによって、次の引数ノードが指し示される。
【０１２７】
このようにして、全ての引数の入力値が設定されるまで、ステップＳ９１３、Ｓ９１４、Ｓ９２１乃至Ｓ９２３における一連の処理が繰り返し実行される。なお、ステップＳ９２２およびＳ９２３は、特許請求の範囲に記載の実行履歴検索手順の一例である。
【０１２８】
一方、ステップＳ９１４の処理において入力値設定命令でないと判断された場合には、命令デコーダ３２０により、フェッチ部３１０から読み出された命令が、関数を呼び出す呼出し命令であるか否かが判断される（ステップＳ９１５）。そして、呼出し命令でないと判断された場合には、ステップＳ９１３の処理に戻る。
【０１２９】
一方、呼出し命令と判断された場合には、入力値設定命令により設定された入力値が、履歴メモリ４３０における識別情報に関連付けられた入力値と全て一致したか否かが判断される（ステップＳ９１６）。そして、全ての入力値が一致した場合には、実行結果再利用処理が実行される（ステップＳ９２４）。すなわち、実行履歴検索部４１０により取得された識別情報および入力値に対応する履歴メモリ４３０における実行結果が、実行結果出力部４２０から出力される。そして、主記憶部１３０またはレジスタファイル３４０に書き戻されて、呼び出される関数の処理を終了する。なお、Ｓ９２４は、特許請求の範囲に記載の実行結果出力手順の一例である。
【０１３０】
一方、全ての入力値が一致しない場合には、呼び出された関数が実行される（ステップＳ９１７）。そして、実行履歴検索部４１０により、実行された関数の実行結果が取得される（ステップＳ９１８）。続いて、実行履歴検索部４１０により、その取得された実行結果と、ステップＳ９１２およびＳ９２１により取得された入力値とを履歴メモリ４３０に登録される（ステップＳ９１９）。
【０１３１】
このように、本発明の第１の実施の形態では、関数の実行を予告する予告命令によって、関数の識別情報と、その予告命令の後に実行される入力値設定命令により設定される入力値とを、関数の実行前に特定することができる。これにより、関数が呼び出されるときに、その特定された識別情報および入力値と一致する履歴メモリ４３０における実行履歴を抽出することができる。また、履歴メモリ４３０から実行履歴における実行結果が抽出された場合には、呼出し命令により呼び出される関数の実行を省略することができるため、実行結果の再利用による関数の処理時間を大幅に削減することができる。
【０１３２】
なお、本発明の第１の実施の形態では、履歴メモリ４３０の検索キーである識別情報を予告命令に含める例について説明したが、識別情報を関数の先頭アドレスとし、関数の先頭アドレスを参照するための参照情報を予告命令に含めるようにしてもよい。そこで、参照情報を含む予告命令に基づいて履歴メモリ４３０における実行履歴を検索する例を第２の実施の形態として以下に図面を参照して説明する。
【０１３３】
＜第２の実施の形態＞
［参照情報を含む予告命令によるデータ処理装置１００の動作例］
図８は、本発明の第２の実施の形態におけるデータ処理装置１００において参照情報を含む予告命令を受け付けた場合におけるデータ処理装置１００の動作概要を示す概念図である。ここでは、履歴メモリ４３０の検索キーである識別情報として関数の先頭アドレスである関数アドレスを用いることを想定している。
【０１３４】
図８（ａ）は、アセンブリ言語により記述された命令列の一部を例示する図である。図８（ａ）には、関数アドレスをレジスタ２５（Ｒ２５）に設定するロードワード命令（ｌｗ）と、参照情報（Ｒ２５）を含む予告命令（ｎｏｔｉｃｅＣａｌｌ）とが示されている。また、ここでは、レジスタ２５（Ｒ２５）に格納された関数を呼び出すコール命令（Ｃａｌｌ）が示されている。
【０１３５】
このように、予告命令（ｎｏｔｉｃｅＣａｌｌ）の参照情報には、関数アドレスが格納されているレジスタ番号（Ｒ２５）が示される。また、このような参照情報を含む予告命令を生成する場合には、コンパイル処理において、関数アドレスを設定するロードワード命令（ｌｗ）を予告命令の前に生成することを想定している。
【０１３６】
図８（ｂ）は、履歴メモリ４３０における識別情報である関数アドレスごとの実行履歴検索データの一例を示す概念図である。図８（ｂ）には、参照情報（Ｒ２５）に示されるレジスタ２５（Ｒ２５）に格納されている関数アドレス（関数アドレス０乃至ｋ）の列４３３と、実行履歴検索データ（実行履歴検索データ０乃至ｋ）の列４３４との対応表が示されている。ここにいう実行履歴検索データは、図３に示した木構造によって構成される検索データのことを示す。
【０１３７】
この場合において、命令デコーダ３２０は、予告命令（ｎｏｔｉｃｅＣａｌｌ）に含まれる参照情報（Ｒ２５）に基づいて、レジスタ２５（Ｒ２５）に格納されている「関数アドレス１」を実行履歴検索部４１０に出力させる。すなわち、実行部３３０は、参照情報を含む予告命令に基づいて関数アドレス「関数アドレス１」を実行履歴検索部４１０に出力する。そして、実行履歴検索部４１０により、その「関数アドレス１」が履歴メモリ４３０に入力されることによって、その関数アドレス１に対応する実行履歴検索データ１に基づいて、実行履歴の検索が開始される。
【０１３８】
その後、関数における引数の入力値を設定するための入力値設定命令に基づいて、実行履歴検索部４１０において、関数における引数の入力値が保持され、その保持された入力値が履歴メモリ４３０に順次入力される。これにより、関数アドレス（関数アドレス１）に対応する実行履歴検索データ（実行履歴検索データ１）に保持された入力値と、実行履歴検索部４１０からの入力値との比較が順次行われる。
【０１３９】
そして、コール命令（ｃａｌｌ）が命令デコーダ３２０に供給されることによって、実行履歴検索部４１０により取得された関数アドレスおよび入力値と一致する実行履歴の有無が、履歴メモリ４３０から実行履歴検索部４１０に通知される。すなわち、実行履歴検索部４１０により、関数アドレス１に対応する実行履歴検索データ１による検索結果として、再利用できる実行結果の有無がコール命令（ｃａｌｌ）に基づいて参照される。
【０１４０】
このとき、履歴メモリ４３０から実行結果が出力された場合には、関数の実行が省略される。一方、実行結果が出力されない場合には、関数の処理がそのまま実行されて、その実行された実行結果と、実行履歴検索部４１０によって既に保持されている識別情報および入力値とが履歴メモリ４３０に登録される。
【０１４１】
このように、データ処理装置１００は、関数（関数アドレス１）のコール命令（ｃａｌｌ）の実行前に、予告命令（ｎｏｔｉｃｅＣａｌｌ）に含まれる参照情報に基づいて、履歴メモリ４３０の検索キーである識別情報（関数アドレス１）を取得することができる。次に、参照情報を含む予告命令によるデータ処理装置１００におけるより具体的な動作例について、ＭＩＰＳによる命令コードを示す図面を参照して説明する。
【０１４２】
［参照情報を含む予告命令によるデータ処理装置１００の具体的な動作例］
図９は、本発明の第２の実施の形態におけるデータ処理装置１００により実行されるプログラムの一部を例示する図である。図９（ａ）は、再利用区間として選択された関数のソースプログラムの一部の例を示す図である。図５（ｂ）は、図５（ａ）に示したソースプログラムがＭＩＰＳのアセンブリ言語により変換された命令列の一部を例示する図である。
【０１４３】
図９（ａ）の上段には、５つの引数（ａ乃至ｅ）を持つ関数（ｆｕｎｃ）の呼出しが記述されている。下段には、イント（ｉｎｔ）型の関数（ｆｕｎｃ）の定義が記述されている。この関数（ｆｕｎｃ）は、イント（ｉｎｔ）型の引数として、第１の引数（ａ）、第２の引数（ｂ）、第３の引数（ｃ）、第４の引数（ｄ）および第５の引数（ｅ）を持つ。このようなソースプログラムに対し、ＭＩＰＳのアセンブリ言語により変換するとともに予告命令の挿入処理を施すことによって生成された命令列の一部が図９（ｂ）に示されている。
【０１４４】
図９（ｂ）には、第１の命令列（ｌｗ）、第２の命令列（ｎｏｔｉｃｅＣａｌｌ）、第３の命令列（ｌｗ）、第４の命令列（ｌｗ）、第５の命令列（ｍｏｖｅ）、第６の命令列（ｍｏｖｅ）、第７の命令列（ｓｗ）、および第８の命令列（ｊａｌｒ）が示されている。ここでは、関数の引数の入力値Ａ乃至Ｅが全て整数であることを想定している。
【０１４５】
第１の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスに、オフセット値「２０００」が加算され、その加算された値のメモリアドレスに記憶されたデータ（関数ｆｕｎｃの先頭アドレス）がレジスタ２５（Ｒ２５）に転送される。このように、主記憶部１３０から読み出された関数の先頭アドレスをレジスタファイル３４０に設定するロードワード命令を、ここではアドレス設定命令という。
【０１４６】
第２の命令列において、参照情報（Ｒ２５）を含む予告命令（ｎｏｔｉｃｅＣａｌｌ）が実行される。これにより、命令デコーダ３２０の制御により、参照情報（Ｒ２５）に基づいて、レジスタ２５に格納された識別情報である関数アドレスが実行履歴検索部４１０に出力される。すなわち、実行部３３０により、参照情報を含む予告命令に基づいて関数アドレスが実行履歴検索部４１０に出力される。そして、実行履歴検索部４１０により、その関数アドレスが履歴メモリ４３０に入力されることによって、実行履歴の検索が行われる。
【０１４７】
第３の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスにオフセット値「１０００」が加算され、その加算された値である主記憶部１３０のメモリアドレスに記憶されたデータ（第１の引数の入力値Ａ）がレジスタ４（Ｒ４）に転送される。
【０１４８】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示される転送先レジスタ番号が「Ｒ４」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ４（Ｒ４）に転送される入力値Ａが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第１の引数の入力値と比較される。このとき、履歴メモリ４３０に保持された第１の引数の入力値のうち、入力値Ａが保持されていれば、第２の引数の入力値の比較処理に進む。一方、入力値Ａが保持されていない場合には、実行履歴の検索を終了する。
【０１４９】
第４の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスにオフセット値「１００４」が加算され、その加算された値である主記憶部１３０のメモリアドレスに記憶されたデータ（第２の引数の入力値Ｂ）がレジスタ５（Ｒ５）に転送される。
【０１５０】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示された転送先レジスタ番号が「Ｒ５」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ５（Ｒ５）に格納される入力値Ｂが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第２の引数の入力値と比較される。このとき、履歴メモリ４３０に保持された第２の引数の入力値のうち、入力値Ｂが保持されていれば、第３の引数の入力値の比較処理に進む。一方、入力値Ｂが保持されていない場合には、実行履歴の検索を終了する。
【０１５１】
第５の命令列において、ムーブ命令（ｍｏｖｅ）が実行される。これにより、レジスタ１０（Ｒ１０）に格納されているデータ（第３の引数の入力値Ｃ）が、レジスタ６（Ｒ６）に転送される。このムーブ命令（ｍｏｖｅ）は、そのムーブ命令（ｍｏｖｅ）に示された転送先レジスタ番号が「Ｒ６」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ６（Ｒ６）に格納される入力値Ｃが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第３の引数の入力値と比較される。
【０１５２】
このとき、履歴メモリ４３０に保持された第３の引数の入力値のうち入力値Ｃが保持されていれば、第４の引数の入力値の比較処理に進む。一方、入力値Ｃが保持されていない場合には、実行履歴の検索を終了する。
【０１５３】
第６の命令列において、ムーブ命令（ｍｏｖｅ）が実行される。これにより、レジスタ１１（Ｒ１１）に格納されているデータ（第４の引数の入力値Ｄ）がレジスタ７（Ｒ７）に転送される。このムーブ命令（ｍｏｖｅ）は、そのムーブ命令（ｍｏｖｅ）に示された転送先レジスタ番号が「Ｒ７」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると特定される。このため、レジスタ７（Ｒ７）に格納される入力値Ｄが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第４の引数の入力値と比較される。
【０１５４】
このとき、履歴メモリ４３０に保持された第４の引数の入力値のうち入力値Ｄが保持されていれば、第５の引数の入力値の比較処理に進む。一方、入力値Ｄが保持されていない場合には、実行履歴の検索を終了する。
【０１５５】
第７の命令列において、ストアワード命令（ｓｗ）が実行される。これにより、レジスタ２９（Ｒ２９）に格納されているスタックポインタの値に「１６」が加算され、その加算された値のメモリアドレスにレジスタ１２（Ｒ１２）に格納されているデータ（第５の引数の入力値Ｅ）が転送される。このストアワード命令（ｓｗ）は、そのストアワード命令（ｓｗ）に示された転送先レジスタ番号が「Ｒ２９」であり、オフセット値が「１６」以上であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。
【０１５６】
これにより、主記憶部１３０に転送された入力値Ｅが実行履歴検索部４１０にも供給され、その供給された入力値Ｅと、履歴メモリ４３０に保持されている第５の引数の入力値とが比較される。このとき、履歴メモリ４３０に保持された第５の引数の入力値のうち、入力値Ｅが保持されていれば、全ての引数の入力値Ａ乃至Ｅが一致する実行履歴における実行結果が実行履歴検索部４１０に出力される。一方、入力値Ａが保持されていない場合には、実行履歴の検索を終了する。
【０１５７】
第８の命令列において、ジャンプ命令（ｊａｌｒ）が実行される。これにより、レジスタ２５（Ｒ２５）に格納されている関数（ｆｕｎｃ）の先頭アドレスの命令が読み出される。このとき、命令デコーダ３２０により、関数（ｆｕｎｃ）における全ての第１乃至第５引数の入力値の設定が終了したことを示す入力値終了信号が、実行履歴検索部４１０に通知される。
【０１５８】
このとき、履歴メモリ４３０から実行結果が出力されていれば、実行履歴検索部４１０により、その実行結果が実行結果出力部４２０に出力されるとともに、関数（ｆｕｎｃ）の処理を省略するための省略信号がフェッチ部３１０に供給される。一方、履歴メモリ４３０から実行結果が出力されていなければ、実行履歴検索部４１０により、関数（ｆｕｎｃ）の実行後の実行結果と、予告命令に基づいて取得された識別情報および入力値とが履歴メモリ４３０に登録される。
【０１５９】
このように、本発明の第２の実施の形態では、実行履歴検索部４１０は、予告命令により識別される関数が実行される前において、予告命令に含まれる参照情報に基づいて関数の先頭アドレスを識別情報として取得することができる。これにより、実行履歴検索部４１０は、識別情報として実行部３３０から出力された再利用区間である関数の先頭アドレスと、関数の入力値とに基づいて、履歴メモリ４３０に保持された実行履歴における実行結果を検索することができる。
【０１６０】
すなわち、実行結果再利用処理部４００は、参照情報を含む予告命令によって、実行履歴検索部４１０において識別情報および入力値を取得することができるため、関数の実行前に、履歴メモリ４３０に保持された実行履歴を検索することができる。
【０１６１】
なお、ここでは、参照情報を含む予告命令により関数アドレスを取得する例について説明したが、関数アドレスを設定するためのアドレス設定命令を予告命令とする予告設定命令を用いるようにしてもよい。次に、予告設定命令を契機に履歴メモリ４３０に保持された実行履歴を検索する例を第３の実施の形態として以下に図面を参照して説明する。
【０１６２】
＜第３の実施の形態＞
［参照情報を含む予告命令によるデータ処理装置１００の動作例］
図１０は、本発明の第３の実施の形態におけるデータ処理装置１００において予告設定命令を受け付けた場合におけるデータ処理装置１００の動作概要を示す概念図である。ここでは、履歴メモリ４３０の検索キーである識別情報として関数の先頭アドレスである関数アドレスを用いることを想定している。
【０１６３】
図１０（ａ）は、アセンブリ言語により記述された命令列の一部を例示する図である。図１０（ａ）には、関数アドレスをレジスタ２５（Ｒ２５）に設定する予告設定命令（ｍｅｍｏｌｗ）と、レジスタ２５（Ｒ２５）に格納された関数アドレスに対応する関数を呼び出すコール命令（Ｃａｌｌ）が示されている。
【０１６４】
このように、予告設定命令（ｍｅｍｏｌｗ）を用いることによって、第２の実施の形態と比べて、関数アドレスをレジスタ２５（Ｒ２５）に設定するアドレス設定命令（ｌｗ）を省略することができる。
【０１６５】
図１０（ｂ）は、履歴メモリ４３０における識別情報である関数アドレスごとの実行履歴検索データの一例を示す概念図である。図１０（ｂ）には、予告設定命令（ｍｅｍｏｌｗ）によってレジスタ２５（Ｒ２５）に設定される関数アドレス（関数アドレス０乃至ｋ）の列４３５と、実行履歴検索データ（実行履歴検索データ０乃至ｋ）の列４３６との対応表が示されている。ここにいう実行履歴検索データは、図３に示した木構造によって構成される検索データのことを示す。
【０１６６】
この場合において、命令デコーダ３２０は、予告設定命令（ｍｅｍｏｌｗ）に指定された設定情報に示されたレジスタ２５（Ｒ２５）に「関数アドレス１」を設定するとともに、実行履歴検索部４１０に「関数アドレス１」を取得させる。すなわち、実行部３３０は、関数の先頭アドレスの設定先（Ｒ２５）を示す設定情報を含む予告設定命令（ｍｅｍｏｌｗ）基づいて、関数の先頭アドレス「関数アドレス１」を設定先（Ｒ２５）に設定する。
【０１６７】
そして、実行履歴検索部４１０により、その「関数アドレス１」が履歴メモリ４３０に入力されることによって、その関数アドレス１に対応する「実行履歴検索データ１」に基づいて、実行履歴の検索が開始される。
【０１６８】
その後、関数における引数の入力値を設定するための入力値設定命令に基づいて、実行履歴検索部４１０において、引数の入力値が取得され、その取得された入力値が履歴メモリ４３０に順次入力される。これにより、関数アドレス（関数アドレス１）に対応する実行履歴検索データ（実行履歴検索データ１）に保持された入力値と、実行履歴検索部４１０からの入力値との比較が順次行われる。
【０１６９】
そして、コール命令（ｃａｌｌ）が命令デコーダ３２０に供給されることによって、実行履歴検索部４１０により取得された関数アドレス（関数アドレス１）および入力値と一致する実行履歴の有無が履歴メモリ４３０から実行履歴検索部４１０に通知される。すなわち、実行履歴検索部４１０により、関数アドレス１に対応する実行履歴検索データ１による検索結果がコール命令（ｃａｌｌ）に基づいて参照される。
【０１７０】
このとき、履歴メモリ４３０から実行結果が出力された場合には、関数の実行が省略される。一方、実行結果が出力されない場合には、関数の処理が実行されて、その実行された実行結果と、実行履歴検索部４１０によって既に取得された識別情報である関数アドレスおよび入力値とが履歴メモリ４３０に保持される。
【０１７１】
このように、データ処理装置１００は、関数（関数アドレス１）のコール命令（ｃａｌｌ）を実行する前に、予告設定命令（ｍｅｍｏｌｗ）により設定される関数アドレス（関数アドレス１）を実行履歴検索部４１０において取得することができる。次に、予告設定命令によるデータ処理装置１００におけるより具体的な動作例について、ＭＩＰＳによる命令コードを示す図面を参照して説明する。
【０１７２】
［予告設定命令によるデータ処理装置１００の具体的な動作例］
図１１は、本発明の第３の実施の形態におけるデータ処理装置１００により実行されるプログラムの一部を例示する図である。図１１（ａ）の上段には、５つの引数（ａ乃至ｅ）を持つ関数（ｆｕｎｃ）の呼出しが記述されている。下段には、イント（ｉｎｔ）型の関数（ｆｕｎｃ）の定義が記述されている。この関数（ｆｕｎｃ）は、イント（ｉｎｔ）型の引数として、第１の引数（ａ）、第２の引数（ｂ）、第３の引数（ｃ）、第４の引数（ｄ）および第５の引数（ｅ）を持つ。
【０１７３】
このようなソースプログラムに対し、ＭＩＰＳのアセンブリ言語により変換するとともに予告命令の挿入処理を施すことによって生成された命令列の一部が図１１（ｂ）に示されている。
【０１７４】
図１１（ｂ）には、第１の命令列（ｍｅｍｏｌｗ）、第２の命令列（ｌｗ）、第３の命令列（ｌｗ）、第４の命令列（ｍｏｖｅ）、第５の命令列（ｍｏｖｅ）、第６の命令列（ｓｗ）、および第７の命令列（ｊａｌｒ）が示されている。ここでは、関数の引数の入力値Ａ乃至Ｅが全て整数であることを想定している。
【０１７５】
第１の命令列において、予告設定命令（ｍｅｍｏｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスに、オフセット値「２０００」が加算され、その加算された値のメモリアドレスに記憶されたデータ（関数ｆｕｎｃの先頭アドレス）がレジスタ２５（Ｒ２５）に転送される。すなわち、実行部３３０は、予告設定命令に含まれる関数の先頭アドレスの設定先を示す設定情報を基づいて、関数の先頭アドレスを設定先に設定する。
【０１７６】
これとともに、命令デコーダ３２０により供給される取得信号に基づいて、入力選択部３３２から出力される関数アドレスが実行履歴検索部４１０により取得される。そして、実行履歴検索部４１０によりその関数アドレスが履歴メモリ４３０に入力されることによって、実行履歴の検索が行われる。
【０１７７】
第２の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスにオフセット値「１０００」が加算され、その加算された値である主記憶部１３０のメモリアドレスに記憶されたデータ（第１の引数の入力値Ａ）がレジスタ４（Ｒ４）に転送される。
【０１７８】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示された転送先レジスタ番号が「Ｒ４」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ４（Ｒ４）に転送される入力値Ａが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第１の引数の入力値と比較される。
【０１７９】
このとき、履歴メモリ４３０に保持された第１の引数の入力値のうち、入力値Ａが保持されていれば、第２の引数の入力値の比較処理に進む。一方、入力値Ａが保持されていない場合には、実行履歴の検索を終了する。
【０１８０】
第３の命令列において、ロードワード命令（ｌｗ）が実行される。これにより、レジスタ２８（Ｒ２８）に格納されている基準アドレスにオフセット値「１００４」が加算され、その加算された値である主記憶部１３０のメモリアドレスに記憶されたデータ（第２の引数の入力値Ｂ）がレジスタ５（Ｒ５）に転送される。
【０１８１】
このロードワード命令（ｌｗ）は、そのロードワード命令（ｌｗ）に示された転送先レジスタ番号が「Ｒ５」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。このため、レジスタ５（Ｒ５）に格納される入力値Ｂが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第２の引数の入力値と比較される。
【０１８２】
このとき、履歴メモリ４３０に保持された第２の引数の入力値のうち、入力値Ｂが保持されていれば、第３の引数の入力値の比較処理に進む。一方、入力値Ｂが保持されていない場合には、実行履歴の検索を終了する。
【０１８３】
第４の命令列において、ムーブ命令（ｍｏｖｅ）が実行される。これにより、レジスタ１０（Ｒ１０）に格納されているデータ（第３の引数の入力値Ｃ）がレジスタ６（Ｒ６）に転送される。このムーブ命令（ｍｏｖｅ）は、その転送先レジスタ番号が「Ｒ６」であることから、命令デコーダ３２０により引数の入力値を設定する入力値設定命令であると判断される。これにより、レジスタ６（Ｒ６）に格納される入力値Ｃが実行履歴検索部４１０にも供給されるため、実行履歴検索部４１０に供給された入力値Ｃと、履歴メモリ４３０に保持されている第３の引数の入力値とが比較される。
【０１８４】
このとき、履歴メモリ４３０に保持された第３の引数の入力値のうち入力値Ｃが保持されていれば、第４の引数の入力値の比較処理に進む。一方、入力値Ｃが保持されていない場合には、実行履歴の検索を終了する。
【０１８５】
第５の命令列において、ムーブ命令（ｍｏｖｅ）が実行される。これにより、レジスタ１１（Ｒ１１）に格納されているデータ（第４の引数の入力値Ｄ）がレジスタ７（Ｒ７）に転送される。このムーブ命令（ｍｏｖｅ）は、そのムーブ命令（ｍｏｖｅ）に示された転送先レジスタ番号が「Ｒ７」であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると特定される。このため、レジスタ７（Ｒ７）に格納される入力値Ｄが実行履歴検索部４１０にも供給され、履歴メモリ４３０に保持されている第４の引数の入力値と比較される。
【０１８６】
このとき、履歴メモリ４３０に保持された第４の引数の入力値のうち入力値Ｄが保持されていれば、第５の引数の入力値の比較処理に進む。一方、入力値Ｄが保持されていない場合には、実行履歴の検索を終了する。
【０１８７】
第６の命令列において、ストアワード命令（ｓｗ）が実行される。これにより、レジスタ２９（Ｒ２９）に格納されているスタックポインタの値に「１６」が加算され、その加算された値のメモリアドレスにレジスタ１２（Ｒ１２）に格納されているデータ（第５の引数の入力値Ｅ）が転送される。このストアワード命令（ｓｗ）は、そのストアワード命令（ｓｗ）に示された転送先レジスタ番号が「Ｒ２９」であり、オフセット値が「１６」以上であることから、命令デコーダ３２０により、引数の入力値を設定する入力値設定命令であると判断される。
【０１８８】
これにより、主記憶部１３０に転送された入力値Ｅが実行履歴検索部４１０にも供給され、その供給された入力値Ｅと、履歴メモリ４３０に保持されている第５の引数の入力値とが比較される。このとき、履歴メモリ４３０に保持された第５の引数の入力値のうち、入力値Ｅが保持されていれば、全ての引数の入力値Ａ乃至Ｅが一致する実行履歴における実行結果が実行履歴検索部４１０に出力される。一方、入力値Ａが保持されていない場合には、実行履歴の検索を終了する。
【０１８９】
第７の命令列において、ジャンプ命令（ｊａｌｒ）が実行される。これにより、レジスタ２５（Ｒ２５）に格納されている関数（ｆｕｎｃ）の先頭アドレスの命令が読み出される。このとき、命令デコーダ３２０により、関数（ｆｕｎｃ）における全ての第１乃至第５引数の入力値の設定が終了したことを示す入力値終了信号が実行履歴検索部４１０に通知される。
【０１９０】
このとき、履歴メモリ４３０から実行結果が出力されていれば、実行履歴検索部４１０により、その実行結果が実行結果出力部４２０に出力されるとともに、関数（ｆｕｎｃ）の処理を省略するための省略信号がフェッチ部３１０に供給される。一方、履歴メモリ４３０から実行結果が出力されていなければ、実行履歴検索部４１０により、関数（ｆｕｎｃ）の実行後の実行結果と、予告命令に基づいて取得された識別情報および入力値とが履歴メモリ４３０に登録される。
【０１９１】
このように、本発明の第３の実施の形態では、実行履歴検索部４１０は、関数の実行前において、その関数に対応する予告設定命令に基づいて設定される関数アドレスを識別情報として取得することができる。これにより、実行履歴検索部４１０は、実行部３３０により設定された関数の先頭アドレスと、予告設定命令により取得された関数の入力値とに基づいて、履歴メモリ４３０における実行結果を検索することができる。
【０１９２】
すなわち、実行結果再利用処理部４００は、予告設定命令によって、実行履歴検索部４１０において識別情報および入力値を取得することができるため、関数の実行前に、履歴メモリ４３０に保持された実行履歴を検索することができる。
【０１９３】
このように、本発明の第１乃至３の実施の形態では、主記憶部１３０に記憶されたプログラムに含まれる予告命令に基づいて、関数の実行結果の再利用による処理時間を大幅に短縮することができる。次に、このような予告命令をプログラムに挿入するプログラム変換装置について図面を参照して説明する。
【０１９４】
＜４．第４の実施の形態＞
［プログラム変換装置の構成例］
図１２は、本発明の第４の実施の形態におけるプログラム変換処理装置の一機能構成例を示すブロック図である。プログラム変換処理装置５００は、ソースプログラム記憶部５１０と、予告命令挿入コード生成部６００と、オブジェクトプログラム記憶部５２０とを備える。なお、プログラム変換処理装置５００は、特許請求の範囲に記載のプログラム変換処理装置の一例である。
【０１９５】
ソースプログラム記憶部５１０は、コンパイル処理の対象となるソースプログラムを記憶するものである。このソースプログラムは、実行結果が再び利用される再利用区間が含まれるソースプログラムである。このソースプログラム記憶部５１０は、その記憶されたソースプログラムを予告命令挿入コード生成部６００に供給する。
【０１９６】
予告命令挿入コード生成部６００は、ソースプログラム記憶部５１０からのソースプログラムをコンパイルすることによって、予告命令を挿入するための処理を施した後に、機械語プログラムであるオブジェクトプログラムを生成するものである。この予告命令挿入コード生成部６００は、その生成されたオブジェクトプログラムをオブジェクトプログラム記憶部５２０に記憶させる。この予告命令挿入コード生成部６００は、プログラム解析部６１０と、プログラム最適化処理部６２０と、コード生成部６３０とを備える。
【０１９７】
プログラム解析部６１０は、ソースプログラム記憶部５１０から読み出したソースプログラムに基づいて形態素解析や構文解析などの解析処理を実行するものである。このプログラム解析部６１０は、解析または最適化に適した形式の中間コードによって表現された中間表現によるプログラムを生成して、その生成されたプログラムに解析処理を実行する。
【０１９８】
また、このプログラム解析部６１０は、再利用候補区間抽出部６１１および再利用候補区間解析部６１２を備える。再利用候補区間抽出部６１１は、複数の命令区間のうち、実行結果を再利用する再利用区間の候補となる再利用候補区間をプログラムから抽出するものである。この再利用候補区間抽出部６１１は、例えば、複数回実行される命令区間である複数の関数のうち、再利用候補区間となる関数を抽出する。
【０１９９】
また、再利用候補区間抽出部６１１は、再利用候補区間の入力値が同じでも異なる実行結果になるため、実行結果が再利用できない関数を再利用候補区間から除外する。この再利用候補区間抽出部６１１は、例えば、命令区間に分岐命令を含むような関数を再利用候補区間から除外する。この再利用候補区間抽出部６１１は、その抽出された再利用候補区間の識別情報をプログラムとともに再利用候補区間解析部６１２に供給する。
【０２００】
再利用候補区間解析部６１２は、再利用候補区間抽出部６１１により抽出された再利用候補区間の使用態様を解析するものである。この再利用候補区間解析部６１２は、例えば、関数における引数の個数および型と、その１つの関数が実行される回数とを使用態様として関数ごとに解析する。この例において、再利用候補区間解析部６１２は、例えば、関数の処理内容から引数の採り得る範囲の数を使用態様の解析結果として出力する。この再利用候補区間解析部６１２は、その解析結果を、再利用候補区間の識別情報およびプログラムとともにプログラム最適化処理部６２０に供給する。
【０２０１】
プログラム最適化処理部６２０は、再利用候補区間解析部６１２から供給されたプログラムに基づいて、プログラムの実行速度を向上させるための最適化、および、コードサイズを削減するための最適化などを行うプログラム最適化処理を実行するものである。このプログラム最適化処理部６２０は、再利用度生成部６２１と、再利用区間選択部６２２と、予告命令生成処理部６２３とを備える。
【０２０２】
再利用度生成部６２１は、再利用候補区間解析部６１２から供給された解析結果に基づいて、再利用候補区間の実行結果が再び利用される度合いを示す再利用度を生成するものである。すなわち、再利用度生成部６２１は、複数回実行される命令区間の各々の実行結果が互いに一致する度合いを示す再利用度を、命令区間の使用態様に基づいて命令区間ごとに生成する。
【０２０３】
この再利用度生成部６２１は、例えば、再利用候補区間が実行される実行回数に応じて再利用度を生成する。この場合において、再利用度生成部６２１は、例えば、実行回数が大きいほど再利用度を大きく設定する。また、この再利用度生成部６２１は、例えば、再利用候補区間の入力値が採り得る範囲の数に応じて再利用度を生成する。この場合には、再利用度は、例えば、組合せの数の逆数に定数を乗算することによって算出される。このため、再利用候補区間の再利用度が大きいほど、再利用される度合いが高い再利用候補区間であることを意味する。
【０２０４】
この再利用度生成部６２１は、その生成された再利用度を、プログラムおよび再利用候補区間の識別情報とともに再利用区間選択部６２２に供給する。なお、再利用度生成部６２１は、特許請求の範囲に記載の再利用度生成部の一例である。
【０２０５】
再利用区間選択部６２２は、再利用度生成部６２１から供給された再利用候補区間の再利用度に基づいて、複数の再利用候補区間のうち、再利用区間を選択するものである。この再利用区間選択部６２２は、例えば、再利用度に関する一定の閾値（再利用閾値）以上である再利用候補区間を再利用区間として選択する。
【０２０６】
また、再利用区間選択部６２２は、例えば、履歴メモリ４３０における識別情報ごとの実行履歴を削除する際の優先度を再利用度に基づいて生成する。この例において、再利用区間選択部６２２は、再利用度が高いほど優先度が低くなるように優先度を生成する。また、再利用区間選択部６２２は、その選択された再利用区間に関する識別情報および優先度を、プログラムとともに予告命令生成処理部６２３に供給する。
【０２０７】
予告命令生成処理部６２３は、再利用区間選択部６２２により選択された再利用区間を呼び出すための呼出し命令の前に、その再利用区間を特定するための情報を含む予告命令を生成するものである。この予告命令生成処理部６２３は、その予告命令から呼出し命令の直前の命令までに、再利用区間の入力値を設定するための入力値設定命令を生成する。
【０２０８】
すなわち、予告命令生成処理部６２３は、複数の命令区間のうち、再利用度に基づいて選択された再利用区間における入力値を設定する入力値設定命令の直前に、再利用区間における入力値の設定を予告する予告命令を生成する。この予告命令生成処理部６２３は、例えば、再利用区間である関数の呼出し命令の前に予告命令を挿入するとともに、その予告命令と呼出し命令との間に入力値設定命令を生成する。
【０２０９】
また、予告命令生成処理部６２３は、例えば、呼出し命令の前において、その呼出し命令によって呼び出される関数の識別情報が含まれる予告命令を生成する。すなわち、予告命令生成処理部６２３は、再利用度に基づいて選択された複数の再利用区間を互いに識別するための識別情報を含む予告命令を生成する。この予告命令生成処理部６２３は、例えば、図５（ｂ）に表わしたように、インデックス（ｉｎｄｅｘ）により示される識別情報を含む予告命令（ｎｏｔｉｃｅＣａｌｌ）を生成する。
【０２１０】
また、予告命令生成処理部６２３は、例えば、呼出し命令の前に、その呼出し命令の実行のためにレジスタファイル３４０に予め設定された関数の先頭アドレスを参照するための参照情報が含まれる予告命令を挿入する。この場合、予告命令生成処理部６２３は、参照情報を含む予告命令の前に、関数の先頭アドレスをレジスタファイル３４０に設定するためのアドレス設定命令を生成する。すなわち、予告命令生成処理部６２３は、再利用区間の先頭アドレスを設定するためのアドレス設定命令の後に、その先頭アドレスを参照するための参照情報を含む予告命令を生成する。この例において、予告命令生成処理部６２３は、例えば、図９（ｂ）に示すように参照情報（Ｒ２５）を含む予告命令（ｎｏｔｉｃｅＣａｌｌ）を生成する。
【０２１１】
その他の例として、予告命令生成処理部６２３は、呼出し命令の前に、その呼出し命令の飛越し先である関数の先頭アドレスの設定先を示す設定情報が含まれる予告命令を予告設定命令として生成する。すなわち、予告命令生成処理部６２３は、再利用区間の先頭アドレスを設定するために、関数の先頭アドレスの設定先が示された設定情報を含むアドレス設定命令として予告命令を生成する。この例において、予告命令生成処理部６２３は、例えば、図１１（ｂ）に示すように予告設定命令（ｍｅｍｏｌｗ）を生成する。
【０２１２】
また、予告命令生成処理部６２３は、例えば、識別情報を含む予告命令、または、参照情報を含む予告命令を生成するにあたり、再利用区間選択部６２２により生成された優先度をさらに含めた予告命令を、呼出し命令の前に生成する。すなわち、予告命令生成処理部６２３は、再利用度生成部６２１により生成された再利用度に応じて付与された優先度を含む予告命令を生成する。
【０２１３】
また、この予告命令生成処理部６２３は、その生成された予告命令を含む最適化されたプログラムをコード生成部６３０に供給する。なお、予告命令生成処理部６２３は、特許請求の範囲に記載の予告命令生成処理部の一例である。
【０２１４】
コード生成部６３０は、予告命令生成処理部６２３から供給された最適化されたプログラムに基づいて、機械語プログラムのコードであるオブジェクトプログラムを生成するものである。このコード生成部６３０は、その生成したオブジェクトプログラムをオブジェクトプログラム記憶部５２０に供給する。
【０２１５】
オブジェクトプログラム記憶部５２０は、コード生成部６３０から供給されたオブジェクトプログラムを記憶するものである。このオブジェクトプログラム記憶部５２０に記憶されたオブジェクトプログラムが、図１に示した主記憶部１３０に記憶される。
【０２１６】
このように、予告命令生成処理部６２３を設けることによって、再利用区間の呼出し命令の実行前にその呼出し命令の実行を予告する予告命令が実行されるプログラムを生成することができる。また、再利用度生成部６２１を設けることによって、複数回実行される命令区間の使用態様に基づいて再利用度が生成されるため、複数の命令区間のうち、実行結果が再利用される確率の高い命令区間を再利用区間として選択することができる。
【０２１７】
［予告命令のデータフォーマットの例］
図１３は、本発明の第４の実施の形態におけるプログラム変換処理装置５００により生成される予告命令のデータフォーマットを例示する図である。ここでは、ＭＩＰＳの規定による３２ビット命令のデータフォーマットに基づく予告命令の例について示す。
【０２１８】
図１３（ａ）は、識別情報を含む予告命令のデータフォーマットを示す図である。図１３（ｂ）は、参照情報を含む予告命令のデータフォーマットを示す図である。図１３（ｃ）は、予告設定命令のデータフォーマットを示す図である。
【０２１９】
図１３（ａ）には、オペレーションコード７１１、インデックス７１２、優先度７１３および機能コード７１４を表わすフィールドがそれぞれ示されている。オペレーションコード７１１には、特殊命令（ＳＰＥＣＩＡＬ）を示す「００００００」が２６乃至３１ビットに格納される。
【０２２０】
インデックス７１２には、再利用区間選択部６２２により選択された複数の関数を互いに識別するための識別情報が１０乃至２５ビットに格納される。優先度７１３には、履歴メモリ４３０における実行履歴を削除する際の優先度が６乃至９ビットに格納される。この優先度７１３には、再利用区間選択部６２２により生成された優先度の値が格納される。機能コード７１４には、予告命令（ｎｏｔｉｃｅＣａｌｌ）として「０００１０１」が０乃至５ビットに格納される。
【０２２１】
図１３（ｂ）には、オペレーションコード７２１、優先度７２２、転送先レジスタ７２３および機能コード７２４を表わすフィールドがそれぞれ示されている。オペレーションコード７１１には、特殊命令（ＳＰＥＣＩＡＬ）を示す「００００００」が２６乃至３１ビットに格納される。
【０２２２】
優先度７２２には、履歴メモリ４３０の実行履歴を削除する際の優先度が１１乃至２５ビットに格納される。この優先度７２２には、再利用区間選択部６２２により生成された優先度の値が格納される。転送先レジスタ７２３には、参照情報として、関数の先頭アドレスが格納されているレジスタ番号が６乃至１０ビットに格納される。機能コード７２４には、予告命令（ｎｏｔｉｃｅＣａｌｌ）として「０００１０１」が０乃至５ビットに格納される。
【０２２３】
図１３（ｃ）には、オペレーションコード７３１、基準レジスタ７３２、転送先レジスタ７３３およびオフセット７３４を表わすフィールドがそれぞれ示されている。オペレーションコード７３１には、予告設定命令（ｍｅｍｏｌｗ）を示す「０１１１１１」が２６乃至３１ビットに格納される。
【０２２４】
基準レジスタ７３２には、基準アドレスが格納されているレジスタ番号（Ｒ２５）が２１乃至２５ビットに格納される。転送先レジスタ７３３には、設定先を示す設定情報として、関数を呼び出すための関数の先頭アドレスが設定されるレジスタ番号が１６乃至２０ビットに格納される。オフセット７３４には、基準アドレスに対するオフセット値が０乃至１５ビットに格納される。
【０２２５】
このような予告命令または予告設定命令が、関数を呼び出すための呼出し命令の前に、予告命令生成処理部６２３によって生成される。
【０２２６】
［プログラム変換処理装置５００の動作例］
次に本発明の第４の実施の形態におけるプログラム変換処理装置５００の動作について図面を参照して説明する。
【０２２７】
図１４は、本発明の第４の実施の形態におけるプログラム変換処理装置５００の予告命令生成処理方法の処理手順の一例を示すフローチャートである。
【０２２８】
まず、再利用候補区間抽出部６１１により、ソースプログラム記憶部５１０からソースプログラムが読み出される（ステップＳ９３１）。そして、再利用候補区間抽出部６１１により、複数回実行される命令区間である複数の関数のうち、再利用候補区間となる関数が抽出される（ステップＳ９３２）。
【０２２９】
続いて、再利用候補区間解析部６１２により、再利用候補区間抽出部６１１において抽出された再利用候補区間の使用態様が解析される（ステップＳ９３３）。この後、再利用度生成部６２１により、再利用候補区間の使用態様に基づいて再利用候補区間ごとに再利用度が生成される（ステップＳ９３４）。なお、ステップＳ９３４は、特許請求の範囲に記載の再利用度生成手順の一例である。
【０２３０】
そして、再利用区間選択部６２２により、再利用候補区間ごとの再利用度に基づいて再利用区間が選択される（ステップＳ９３５）。次に、予告命令生成処理部６２３により、再利用区間を呼び出す呼出し命令の前に予告命令を生成して、その生成された予告命令から呼出し命令の間に入力値設定命令を生成する予告命令生成処理が実行される（ステップＳ９４０）。なお、ステップＳ９４０は、特許請求の範囲に記載の予告命令生成手順の一例である。
【０２３１】
その後、コード生成部６３０により、予告命令生成処理部６２３から供給された最適化されたプログラムに基づいて、オブジェクトプログラムが生成される（ステップＳ９３６）。次に、図１３（ａ）乃至（ｃ）に示した予告命令ごとの予告命令生成処理の処理手順例について以下に図面を参照して説明する。
【０２３２】
［識別情報を含む予告命令における予告命令生成処理例］
図１５は、本発明の第４の実施の形態における識別情報を含む予告命令についての予告命令処理（ステップＳ９４０）の処理手順の一例を示すフローチャートである。
【０２３３】
まず、予告命令生成処理部６２３により、再利用区間の呼出し命令の前に、識別情報を含む予告命令が生成される（ステップＳ９４２）。例えば、図５（ｂ）に示した第１の命令列のように、インデックス（ｉｎｄｅｘ）を指定する予告命令（ｎｏｔｉｃｅＣａｌｌ）が生成される。
【０２３４】
次に、予告命令生成処理部６２３により、識別情報を含む予告命令の後に、再利用区間の入力値を設定するための入力値設定命令が生成される（ステップＳ９４３）。例えば、図５（ｂ）に示した第２乃至第６の命令列のように、入力値設定命令（２つのロードワード命令、２つのムーブ命令およびストアワード命令）が生成される。
【０２３５】
そして、予告命令生成処理部６２３により、入力値設定命令の後に、再利用区間の先頭アドレスを設定するためのアドレス設定命令が生成される（ステップＳ９４４）。例えば、図５（ｂ）に示した第７の命令列のように、アドレス設定命令（ロードワード命令）が生成される。
【０２３６】
その後、予告命令生成処理部６２３により、アドレス設定命令の後に、再利用区間の呼出し命令が生成される（ステップＳ９４５）。例えば、図５（ｂ）に示した第８の命令列のように、呼出し命令（ジャンプ命令）が生成される。
【０２３７】
予告命令生成処理部６２３により、ステップＳ９４２乃至Ｓ９４５の一連の処理が全ての再利用区間を対象に施されるまで繰り返し行われ（ステップＳ９４６）、全ての再利用区間に対する処理が終了することによって、予告命令生成処理が終了する。
【０２３８】
［参照情報を含む予告命令における予告命令生成処理例］
図１６は、本発明の第４の実施の形態における参照情報を含む予告命令についての予告命令処理（ステップＳ９５０）の処理手順の一例を示すフローチャートである。
【０２３９】
まず、予告命令生成処理部６２３により、再利用区間の先頭アドレスを設定するためのアドレス設定命令が生成される（ステップＳ９５１）。例えば、図９（ｂ）に示した第１の命令列のように、アドレス設定命令（ロードワード命令）が生成される。
【０２４０】
そして、予告命令生成処理部６２３により、アドレス設定命令の後に、参照情報を含む予告命令が生成される（ステップＳ９５２）。例えば、図９（ｂ）に示した第２の命令列のように、参照情報（Ｒ２５）を示す予告命令（ｎｏｔｉｃｅＣａｌｌ）が生成される。
【０２４１】
次に、予告命令生成処理部６２３により、参照情報を含む予告命令の後に、再利用区間の入力値を設定するための入力値設定命令が生成される（ステップＳ９４３）。例えば、図９（ｂ）に示した第３乃至第７の命令列のように、入力値設定命令（２つのロードワード命令、２つのムーブ命令およびストアワード命令）が生成される。
【０２４２】
その後、予告命令生成処理部６２３により、入力値設定命令の後に、再利用区間の呼出し命令が生成される（ステップＳ９４５）。例えば、図９（ｂ）に示した第８の命令列のように、呼出し命令（ジャンプ命令）が生成される。
【０２４３】
予告命令生成処理部６２３により、ステップＳ９５１、Ｓ９５２、Ｓ９４３およびＳ９４５の一連の処理が全ての再利用区間を対象に施されるまで繰り返し行われる（ステップＳ９４６）。そして、全ての再利用区間に対する処理が終了することによって、予告命令生成処理が終了する。
【０２４４】
［予告設定命令における予告命令生成処理例］
図１７は、本発明の第４の実施の形態における予告設定命令についての予告命令処理（ステップＳ９６０）の処理手順の一例を示すフローチャートである。
【０２４５】
まず、予告命令生成処理部６２３により、再利用区間の先頭アドレスを設定するための予告設定命令が生成される（ステップＳ９６１）。例えば、図１１（ｂ）に示した第１の命令列のように、予告設定命令（ｍｅｍｏｌｗ）が生成される。
【０２４６】
次に、予告命令生成処理部６２３により、予告設定命令の後に、再利用区間の入力値を設定するための入力値設定命令が生成される（ステップＳ９４３）。例えば、図１１（ｂ）に示した第２乃至第６の命令列のように、入力値設定命令（２つのロードワード命令、２つのムーブ命令およびストアワード命令）が生成される。
【０２４７】
その後、予告命令生成処理部６２３により、入力値設定命令の後に、再利用区間の呼出し命令が生成される（ステップＳ９４６）。例えば、図１１（ｂ）に示した第７の命令列のように、呼出し命令（ジャンプ命令）が生成される。
【０２４８】
予告命令生成処理部６２３により、ステップＳ９６１、Ｓ９４３およびＳ９４５の一連の処理が全ての再利用区間を対象に施されるまで繰り返し行われる（ステップＳ９４６）。そして、全ての再利用区間に対する処理が終了することによって、予告命令生成処理が終了する。
【０２４９】
このように、本発明の第４の実施の形態では、再利用区間の呼出し命令の前に予告命令を生成することによって、データ処理装置１００による実行結果の再利用による再利用区間の処理時間を削減することができる。また、再利用度に基づいて選択された再利用区間に予告命令生成処理を施すことによって、データ処理装置１００における実行結果の再利用率を向上させることができる。
【０２５０】
このように、本発明の実施の形態によれば、再利用区間における処理の実行を予告する予告命令に基づいてその再利用区間の実行結果の再利用処理を行うことによって、再利用区間の処理時間を大幅に削減することができる。
【０２５１】
なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、本発明の実施の形態において明示したように、本発明の実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本発明の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本発明は実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０２５２】
また、本発明の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disk）、メモリカード、ブルーレイディスク（Blu-ray Disc（登録商標））等を用いることができる。
【符号の説明】
【０２５３】
１００ データ処理装置
１２０ バス
１３０ 主記憶部
２００ 一次キャッシュ
２１０ 命令キャッシュ
２２０ データキャッシュ
３００ データ処理部
３１０ フェッチ部
３２０ 命令デコーダ
３３１ ロードユニット
３３２ 入力選択部
３３３ 演算回路
３３４ ストアユニット
３４０ レジスタファイル
４００ 実行結果再利用処理部
４１０ 実行履歴検索部
４２０ 実行結果出力部
４３０ 履歴メモリ
５００ プログラム変換処理装置
５１０ ソースプログラム記憶部
５２０ オブジェクトプログラム記憶部
６００ 予告命令挿入コード生成部
６１０ プログラム解析部
６１１ 再利用候補区間抽出部
６１２ 再利用候補区間解析部
６２０ プログラム最適化処理部
６２１ 再利用度生成部
６２２ 再利用区間選択部
６２３ 予告命令生成処理部
６３０ コード生成部
【特許請求の範囲】
【請求項１】
複数回実行される命令区間である再利用区間が含まれる命令列に基づく処理を実行する実行部と、
前記再利用区間を識別するための識別情報ごとに前記再利用区間における入力値および実行結果を関連付けて実行履歴として保持する履歴メモリと、
前記再利用区間における処理の実行を予告する予告命令に基づいて前記再利用区間の入力値を取得して前記取得された入力値と前記予告命令により特定された前記識別情報とに基づいて前記実行履歴における前記実行結果を検索する実行履歴検索部と、
前記予告命令によって識別された前記再利用区間における処理が実行されるときに前記実行履歴検索部により前記実行結果が抽出された場合には前記抽出された実行結果を前記実行部に出力する実行結果出力部と
を具備するデータ処理装置。
【請求項２】
前記実行履歴検索部は、前記予告命令から前記再利用区間の先頭アドレスが呼び出される呼出し命令の直前の命令までの命令群のうち前記再利用区間の入力値を設定するための入力値設定命令に基づいて入力値を取得する請求項１記載のデータ処理装置。
【請求項３】
前記実行履歴検索部は、前記取得された入力値と前記予告命令に含まれる前記識別情報とに基づいて前記実行履歴における前記実行結果を検索する請求項１記載のデータ処理装置。
【請求項４】
前記履歴メモリは、前記識別情報である前記再利用区間の先頭アドレスごとに前記再利用区間における入力値および実行結果を関連付けて前記実行履歴として保持し、
前記実行部は、前記先頭アドレスを参照するための参照情報を含む前記予告命令に基づいて前記先頭アドレスを前記実行履歴検索部に出力し、
前記実行履歴検索部は、前記識別情報として前記実行部から出力された前記先頭アドレスと前記再利用区間の入力値とに基づいて前記実行履歴における前記実行結果を検索する
請求項１記載のデータ処理装置。
【請求項５】
前記予告命令は、前記識別情報である前記再利用区間の先頭アドレスを設定するための予告設定命令であり、
前記履歴メモリは、前記再利用区間の先頭アドレスごとに前記再利用区間における入力値および実行結果を関連付けて前記実行履歴として保持し、
前記実行部は、前記先頭アドレスの設定先が示された設定情報を含む前記予告設定命令に基づいて前記先頭アドレスを前記設定先に設定し、
前記実行履歴検索部は、前記予告設定命令に基づいて前記再利用区間の入力値を取得して前記取得された入力値と前記実行部により設定された前記先頭アドレスとに基づいて前記実行履歴における前記実行結果を検索する
請求項１記載のデータ処理装置。
【請求項６】
前記履歴メモリは、前記実行履歴を削除する際の優先度と前記優先度に対応する前記再利用区間における入力値および実行結果とを関連付けて前記実行履歴として前記識別情報ごとに保持し、
前記実行履歴検索部は、前記予告命令に含まれる前記優先度に基づいて前記履歴メモリにおける前記実行履歴を削除する
請求項１記載のデータ処理装置。
【請求項７】
前記実行部は、前記実行履歴検索部により前記実行履歴における前記実行結果が前記履歴メモリから抽出されない場合には前記予告命令によって識別された前記再利用区間における処理を実行し、
前記実行履歴検索部は、前記予告命令に基づいて取得された前記入力値と前記実行部により実行された実行結果と前記識別情報とを前記履歴メモリに保持させる
請求項１記載のデータ処理装置。
【請求項８】
前記履歴メモリは、前記再利用区間である関数を識別するための前記識別情報ごとに前記関数における入力値および実行結果を関連付けて前記実行履歴として保持し、
前記実行履歴検索部は、前記関数の実行を予告する予告命令に基づいて前記関数の入力値を取得して前記取得された入力値と前記予告命令により特定された前記識別情報とに基づいて前記実行履歴における前記実行結果を検索し、
実行結果出力部は、前記予告命令によって識別された前記関数が実行されるときに前記実行履歴検索部により前記実行結果が抽出された場合には前記抽出された実行結果を前記実行部に出力する
請求項１記載のデータ処理装置。
【請求項９】
プログラムのうち複数回実行される命令区間の各々の実行結果が互いに一致する度合いを示す再利用度を前記命令区間の使用態様に基づいて前記命令区間ごとに生成する再利用度生成部と、
前記複数の命令区間のうち前記再利用度に基づいて選択された再利用区間における入力値を設定するための入力値設定命令の直前に前記再利用区間における入力値の設定を予告する予告命令を生成する予告命令生成部と
を具備するプログラム変換処理装置。
【請求項１０】
前記予告命令生成部は、前記再利用度に基づいて選択された複数の前記再利用区間を識別するための識別情報を含む前記予告命令を生成する請求項９記載のプログラム変換処理装置。
【請求項１１】
前記予告命令生成部は、前記再利用区間の先頭アドレスを設定するためのアドレス設定命令の後に前記先頭アドレスを参照するための参照情報を含む前記予告命令を生成する請求項９記載のプログラム変換処理装置。
【請求項１２】
前記予告命令生成部は、前記再利用区間の先頭アドレスを設定するために前記先頭アドレスの設定先が示された設定情報を含むアドレス設定命令として前記予告命令を生成する請求項９記載のプログラム変換処理装置。
【請求項１３】
前記予告命令生成部は、前記再利用度生成部により生成された前記再利用度に応じて付与された優先度を含む前記予告命令を生成する請求項９記載のプログラム変換処理装置。
【請求項１４】
複数回実行される命令区間である再利用区間が含まれる命令列に基づく処理を実行する実行部と、前記再利用区間を識別するための識別情報ごとに前記再利用区間における入力値および実行結果を関連付けて実行履歴として保持する履歴メモリとを備えるデータ処理装置におけるデータ処理方法であって、
前記再利用区間における処理の実行を予告する予告命令により特定された前記識別情報と前記予告命令により特定された前記再利用区間の入力値とを取得する取得手順と、
前記取得手順により取得された前記識別情報と前記入力値とに基づいて前記実行履歴における前記実行結果を検索する実行履歴検索手順と、
前記予告命令によって識別された前記再利用区間における処理が実行されるときに前記実行履歴検索部により前記実行結果が抽出された場合には前記抽出された実行結果を前記実行部に出力する実行結果出力手順と
を具備するデータ処理方法。
【請求項１５】
プログラムのうち複数回実行される複数の命令区間各々の実行結果が互いに一致する度合いを示す再利用度を前記命令区間の使用態様に基づいて前記命令区間ごとに生成する再利用度生成手順と、
前記複数の命令区間のうち前記再利用度に基づいて選択された再利用区間における入力値を設定するための入力値設定命令の直前に前記再利用区間における入力値の設定を予告する予告命令を生成する予告命令生成手順と、
を具備する予告命令生成処理方法。
【請求項１】
複数回実行される命令区間である再利用区間が含まれる命令列に基づく処理を実行する実行部と、
前記再利用区間を識別するための識別情報ごとに前記再利用区間における入力値および実行結果を関連付けて実行履歴として保持する履歴メモリと、
前記再利用区間における処理の実行を予告する予告命令に基づいて前記再利用区間の入力値を取得して前記取得された入力値と前記予告命令により特定された前記識別情報とに基づいて前記実行履歴における前記実行結果を検索する実行履歴検索部と、
前記予告命令によって識別された前記再利用区間における処理が実行されるときに前記実行履歴検索部により前記実行結果が抽出された場合には前記抽出された実行結果を前記実行部に出力する実行結果出力部と
を具備するデータ処理装置。
【請求項２】
前記実行履歴検索部は、前記予告命令から前記再利用区間の先頭アドレスが呼び出される呼出し命令の直前の命令までの命令群のうち前記再利用区間の入力値を設定するための入力値設定命令に基づいて入力値を取得する請求項１記載のデータ処理装置。
【請求項３】
前記実行履歴検索部は、前記取得された入力値と前記予告命令に含まれる前記識別情報とに基づいて前記実行履歴における前記実行結果を検索する請求項１記載のデータ処理装置。
【請求項４】
前記履歴メモリは、前記識別情報である前記再利用区間の先頭アドレスごとに前記再利用区間における入力値および実行結果を関連付けて前記実行履歴として保持し、
前記実行部は、前記先頭アドレスを参照するための参照情報を含む前記予告命令に基づいて前記先頭アドレスを前記実行履歴検索部に出力し、
前記実行履歴検索部は、前記識別情報として前記実行部から出力された前記先頭アドレスと前記再利用区間の入力値とに基づいて前記実行履歴における前記実行結果を検索する
請求項１記載のデータ処理装置。
【請求項５】
前記予告命令は、前記識別情報である前記再利用区間の先頭アドレスを設定するための予告設定命令であり、
前記履歴メモリは、前記再利用区間の先頭アドレスごとに前記再利用区間における入力値および実行結果を関連付けて前記実行履歴として保持し、
前記実行部は、前記先頭アドレスの設定先が示された設定情報を含む前記予告設定命令に基づいて前記先頭アドレスを前記設定先に設定し、
前記実行履歴検索部は、前記予告設定命令に基づいて前記再利用区間の入力値を取得して前記取得された入力値と前記実行部により設定された前記先頭アドレスとに基づいて前記実行履歴における前記実行結果を検索する
請求項１記載のデータ処理装置。
【請求項６】
前記履歴メモリは、前記実行履歴を削除する際の優先度と前記優先度に対応する前記再利用区間における入力値および実行結果とを関連付けて前記実行履歴として前記識別情報ごとに保持し、
前記実行履歴検索部は、前記予告命令に含まれる前記優先度に基づいて前記履歴メモリにおける前記実行履歴を削除する
請求項１記載のデータ処理装置。
【請求項７】
前記実行部は、前記実行履歴検索部により前記実行履歴における前記実行結果が前記履歴メモリから抽出されない場合には前記予告命令によって識別された前記再利用区間における処理を実行し、
前記実行履歴検索部は、前記予告命令に基づいて取得された前記入力値と前記実行部により実行された実行結果と前記識別情報とを前記履歴メモリに保持させる
請求項１記載のデータ処理装置。
【請求項８】
前記履歴メモリは、前記再利用区間である関数を識別するための前記識別情報ごとに前記関数における入力値および実行結果を関連付けて前記実行履歴として保持し、
前記実行履歴検索部は、前記関数の実行を予告する予告命令に基づいて前記関数の入力値を取得して前記取得された入力値と前記予告命令により特定された前記識別情報とに基づいて前記実行履歴における前記実行結果を検索し、
実行結果出力部は、前記予告命令によって識別された前記関数が実行されるときに前記実行履歴検索部により前記実行結果が抽出された場合には前記抽出された実行結果を前記実行部に出力する
請求項１記載のデータ処理装置。
【請求項９】
プログラムのうち複数回実行される命令区間の各々の実行結果が互いに一致する度合いを示す再利用度を前記命令区間の使用態様に基づいて前記命令区間ごとに生成する再利用度生成部と、
前記複数の命令区間のうち前記再利用度に基づいて選択された再利用区間における入力値を設定するための入力値設定命令の直前に前記再利用区間における入力値の設定を予告する予告命令を生成する予告命令生成部と
を具備するプログラム変換処理装置。
【請求項１０】
前記予告命令生成部は、前記再利用度に基づいて選択された複数の前記再利用区間を識別するための識別情報を含む前記予告命令を生成する請求項９記載のプログラム変換処理装置。
【請求項１１】
前記予告命令生成部は、前記再利用区間の先頭アドレスを設定するためのアドレス設定命令の後に前記先頭アドレスを参照するための参照情報を含む前記予告命令を生成する請求項９記載のプログラム変換処理装置。
【請求項１２】
前記予告命令生成部は、前記再利用区間の先頭アドレスを設定するために前記先頭アドレスの設定先が示された設定情報を含むアドレス設定命令として前記予告命令を生成する請求項９記載のプログラム変換処理装置。
【請求項１３】
前記予告命令生成部は、前記再利用度生成部により生成された前記再利用度に応じて付与された優先度を含む前記予告命令を生成する請求項９記載のプログラム変換処理装置。
【請求項１４】
複数回実行される命令区間である再利用区間が含まれる命令列に基づく処理を実行する実行部と、前記再利用区間を識別するための識別情報ごとに前記再利用区間における入力値および実行結果を関連付けて実行履歴として保持する履歴メモリとを備えるデータ処理装置におけるデータ処理方法であって、
前記再利用区間における処理の実行を予告する予告命令により特定された前記識別情報と前記予告命令により特定された前記再利用区間の入力値とを取得する取得手順と、
前記取得手順により取得された前記識別情報と前記入力値とに基づいて前記実行履歴における前記実行結果を検索する実行履歴検索手順と、
前記予告命令によって識別された前記再利用区間における処理が実行されるときに前記実行履歴検索部により前記実行結果が抽出された場合には前記抽出された実行結果を前記実行部に出力する実行結果出力手順と
を具備するデータ処理方法。
【請求項１５】
プログラムのうち複数回実行される複数の命令区間各々の実行結果が互いに一致する度合いを示す再利用度を前記命令区間の使用態様に基づいて前記命令区間ごとに生成する再利用度生成手順と、
前記複数の命令区間のうち前記再利用度に基づいて選択された再利用区間における入力値を設定するための入力値設定命令の直前に前記再利用区間における入力値の設定を予告する予告命令を生成する予告命令生成手順と、
を具備する予告命令生成処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１１−３９８５６（Ｐ２０１１−３９８５６Ａ）
【公開日】平成２３年２月２４日（２０１１．２．２４）
【国際特許分類】
【出願番号】特願２００９−１８７６２２（Ｐ２００９−１８７６２２）
【出願日】平成２１年８月１３日（２００９．８．１３）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
【公開日】平成２３年２月２４日（２０１１．２．２４）
【国際特許分類】
【出願日】平成２１年８月１３日（２００９．８．１３）
【出願人】（０００００２１８５）ソニー株式会社 (34,172)
【Ｆターム（参考）】
[ Back to top ]