(57)【要約】【課題】値再利用（メモ化：Memoization）の際、実行結果を保存しておくメモリに保持させるデータのビット長を短縮させることにより、値再利用の効率を改善させる。【解決手段】再利用命令判別部１２０は、プログラムにおける複数の命令区間の使用態様を解析してその命令区間のうち実行結果が再び利用される再利用区間を判別する。ハッシュ関数決定部２００は、再利用区間の開始アドレスのビット幅より狭いビット幅の値により再利用区間を識別する区間識別値を生成するための区間識別値生成関数を、区間識別値生成関数の候補である候補関数から決定する。機械語プログラム生成部１４０は、ハッシュ関数決定部２００により決定された区間識別値生成関数が埋め込まれた機械語プログラムを生成する。【選択図】図１
2011096153.tif 000002
【特許請求の範囲】
【請求項１】
プログラムにおける複数の命令区間の使用態様を解析して前記命令区間のうち実行結果が再び利用される再利用区間を判別する解析部と、
前記再利用区間の開始アドレスのビット幅より狭いビット幅の値により前記再利用区間を識別する区間識別値を生成するための区間識別値生成関数の候補である候補関数を用いることによって、前記区間識別値の候補である候補値を前記候補関数に関連付けて前記開始アドレスから生成する候補値生成部と、
前記候補値生成部により生成された前記候補値を前記関連付けられた候補関数ごとに候補値リストとして保持する候補値テーブルと、
前記候補値が全て互いに異なる前記候補値リストを抽出し、この抽出された候補値リストのうち前記候補値のビット幅に基づいて選択された候補値リストの前記関連付けられた候補関数を前記区間識別値生成関数として出力する区間識別値生成関数出力部と、
前記区間識別値生成関数が埋め込まれた機械語プログラムを前記解析されたプログラムおよび前記区間識別値生成関数に基づいて生成する機械語プログラム生成部と
を具備するコンパイル処理装置。
【請求項２】
前記候補関数は、ハッシュ関数であり、
前記区間識別値生成関数出力部は、前記抽出された候補値リストのうち前記候補値のビット幅に基づいて選択された候補値リストの前記関連付けられたハッシュ関数を前記区間識別値生成関数として出力する
請求項１記載のコンパイル処理装置。
【請求項３】
前記ハッシュ関数は、前記開始アドレスの最下位ビットから所定の数のビットにおける値を前記候補値とするハッシュ関数であり、
前記区間識別値生成関数出力部は、前記抽出された候補値リストのうち前記候補値のビット幅に基づいて選択された候補値リストの前記関連付けられたハッシュ関数を前記区間識別値生成関数として出力する
請求項２記載のコンパイル処理装置。
【請求項４】
前記区間識別値生成関数出力部は、前記抽出された候補値リストのうちビット幅が最も狭い前記候補値の候補値リストの前記関連付けられた候補関数を前記区間識別値生成関数として出力する請求項１記載のコンパイル処理装置。
【請求項５】
前記区間識別値生成関数出力部は、前記区間識別値生成関数として前記区間識別値生成関数を識別するための識別子を出力し、
前記機械語プログラム生成部は、前記識別子が埋め込まれた機械語プログラムを生成する
請求項１記載のコンパイル処理装置。
【請求項６】
複数の命令区間を実行して実行結果を出力する実行部と、
前記命令区間のうち実行結果が再び利用される再利用区間の開始アドレスのビット幅より狭いビット幅の値により前記再利用区間を識別する区間識別値とその前記再利用区間の入力値とその前記再利用区間の実行結果とを実行履歴として保持する履歴メモリと、
前記区間識別値および前記入力値に基づいて前記履歴メモリから前記実行履歴を検索し、前記実行履歴が検索された場合には前記実行結果を出力する履歴検索部と
を具備するデータ処理装置。
【請求項７】
前記実行部が前記再利用区間を実行したときに前記開始アドレスを出力した場合には、前記区間識別値を生成するための区間識別値生成関数を用いて前記開始アドレスから前記区間識別値を生成する区間識別値生成部をさらに具備し、
前記実行部は、前記区間識別値生成部に前記区間識別値生成関数を供給し、
前記履歴メモリは、前記区間識別値生成部により生成された前記区間識別値と前記入力値と前記実行結果とを前記実行履歴として保持し、
前記履歴探索部は、前記区間識別値と前記入力値とに基づいて前記履歴メモリから前記実行履歴を検索し、前記実行履歴が検索された場合には前記実行結果を出力する
請求項６記載のデータ処理装置。
【請求項８】
前記実行部は、前記区間識別値生成関数を前記区間識別値生成部に供給し、
前記区間識別値生成部は、前記実行部が前記再利用区間を実行したときに前記開始アドレスを出力した場合には、前記実行部から供給された前記区間識別値生成関数を用いて前記開始アドレスから前記区間識別値を生成する
請求項７記載のデータ処理装置。
【請求項９】
前記実行部は、前記区間識別値生成関数を識別する識別子を前記区間識別値生成部に供給し、
前記区間識別値生成部は、前記区間識別値生成関数の候補である候補関数から前記区間識別値生成関数を前記識別子に基づいて選択し、前記実行部が前記再利用区間を実行したときに前記開始アドレスを出力した場合には前記選択した区間識別値生成関数を用いて前記開始アドレスから前記区間識別値を生成する
請求項７記載のデータ処理装置。
【請求項１０】
前記実行部は、前記区間識別値が含まれる命令により前記再利用区間を実行した場合には前記区間識別値を前記履歴メモリに供給し、
前記履歴メモリは、前記区間識別値と前記入力値と前記実行結果とを前記実行履歴として保持し、
前記履歴探索部は、前記区間識別値と前記入力値とに基づいて前記履歴メモリから前記実行履歴を検索し、前記実行履歴が検索された場合には前記実行結果を出力する
請求項６記載のデータ処理装置。
【請求項１１】
プログラムにおける複数の命令区間の使用態様を解析して前記命令区間のうち実行結果が再び利用される再利用区間を判別する解析部と、
前記再利用区間の開始アドレスのビット幅より狭いビット幅の値により前記再利用区間を識別する区間識別値を生成するための区間識別値生成関数の候補である候補関数を用いることによって、前記区間識別値の候補である候補値を前記候補関数に関連付けて生成する候補値生成部と、
前記候補値生成部により生成された前記候補値を前記関連付けられた候補関数ごとに候補値リストとして保持する候補値テーブルと、
前記候補値が全て互いに異なる前記候補値リストを抽出し、この抽出された候補値リストのうち前記候補値のビット幅に基づいて選択された候補値リストの前記候補値を前記区間識別値として出力する区間識別値出力部と、
前記再利用区間を呼び出す命令を前記区間識別値が含まれる区間識別値付命令に変換する命令変換部と、
前記再利用区間が前記区間識別値付命令により呼び出される機械語プログラムを前記区間識別値付命令が含まれるソースプログラムに基づいて生成する機械語プログラム生成部と
を具備するコンパイル処理装置。
【請求項１２】
前記候補値生成部は、前記開始アドレスの所定の順序に従って付与された番号を入力の値とする前記候補関数を用いることによって前記候補値を生成する請求項１１記載のコンパイル処理装置。
【請求項１３】
前記候補値生成部は、前記開始アドレスを入力の値とする前記候補関数を用いることによって前記候補値を生成する請求項１１記載のコンパイル処理装置。
【請求項１４】
複数の命令区間を実行して実行結果を出力する実行部と、
前記再利用区間の開始アドレスのビット幅より狭いビット幅の値により前記再利用区間を識別する区間識別値を生成するための区間識別値生成関数の候補である候補関数を用いることによって、前記区間識別値の候補である候補値を前記候補関数に関連付けて前記開始アドレスから生成する候補値生成部と、
前記候補値生成部により生成された前記候補値を前記関連付けられた候補関数ごとに候補値リストとして保持する候補値テーブルと、
前記候補値が全て互いに異なる前記候補値リストを抽出し、この抽出された候補値リストのうち前記候補値のビット幅に基づいて選択された候補値リストの前記関連付けられた候補関数を区間識別値生成関数として出力する区間識別値生成関数出力部と、
前記実行部が前記再利用区間を実行したときに前記開始アドレスが出力された場合には前記区間識別値生成関数を用いて前記開始アドレスから前記区間識別値を生成する区間識別値生成部と、
前記再利用区間の前記区間識別値と入力値と実行結果とを実行履歴として保持する履歴メモリと、
前記区間識別値および前記入力値に基づいて前記履歴メモリから前記実行履歴を検索し、前記実行履歴が検索された場合には前記実行結果を出力する履歴検索部と
を具備するデータ処理装置。
【請求項１５】
区間識別値の候補である候補値を前記候補値を生成した候補関数ごとに候補値リストとして保持する候補値テーブルを備えるコンピュータにおけるデータ処理方法であって、
プログラムにおける複数の命令区間の使用態様を解析して前記命令区間のうち実行結果が再び利用される再利用区間を判別する解析手順と、
前記再利用区間の開始アドレスのビット幅より狭いビット幅の値により前記再利用区間を識別する前記区間識別値を生成するための区間識別値生成関数の候補である前記候補関数を用いることによって、前記区間識別値の候補である前記候補値を前記候補関数に関連付けて前記開始アドレスから生成する候補値生成手順と、
前記候補値が全て互いに異なる前記候補値リストを抽出し、この抽出された候補値リストのうち前記候補値のビット幅に基づいて選択された候補値リストの前記関連付けられた候補関数を前記区間識別値生成関数として出力する区間識別値生成関数出力手順と、
前記区間識別値生成関数が埋め込まれた機械語プログラムを前記解析されたプログラムおよび前記区間識別値生成関数に基づいて生成する機械語プログラム生成手順と
を具備するコンパイル処理方法。
【請求項１６】
区間識別値の候補である候補値を前記候補値を生成した候補関数ごとに候補値リストとして保持する候補値テーブルを備えるコンピュータにおけるプログラムであって、
プログラムにおける複数の命令区間の使用態様を解析して前記命令区間のうち実行結果が再び利用される再利用区間を判別する解析手順と、
前記再利用区間の開始アドレスのビット幅より狭いビット幅の値により前記再利用区間を識別する前記区間識別値を生成するための区間識別値生成関数の候補である前記候補関数を用いることによって、前記区間識別値の候補である前記候補値を前記候補関数に関連付けて前記開始アドレスから生成する候補値生成手順と、
前記候補値が全て互いに異なる前記候補値リストを抽出し、この抽出された候補値リストのうち前記候補値のビット幅に基づいて選択された候補値リストの前記関連付けられた候補関数を前記区間識別値生成関数として出力する区間識別値生成関数出力手順と、
前記区間識別値生成関数が埋め込まれた機械語プログラムを前記解析されたプログラムおよび前記区間識別値生成関数に基づいて生成する機械語プログラム生成手順と
をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイル処理装置に関し、特にハッシュ関数によって生成されたハッシュ値を用いて、実行結果が再利用される命令区間を識別するコンパイル処理装置、データ処理装置、および、これらにおけるコンパイル処理方法およびプログラムに関する。
【背景技術】
【０００２】
プログラムの処理速度を高速化するために種々の技術が開発されている。近年、その技術を用いた装置の一つとして、値再利用（メモ化：Memoization）と呼ばれる命令区間の実行結果を再利用する技法を用いた区間再利用装置が提案されている（例えば、特許文献１参照。）。この区間再利用装置は、プログラムの所定の命令区間における入力値および実行結果をキャッシュに保存しておくことによって、同じ命令区間を再び実行する際に入力値が一致する場合には、保存していた実行結果である出力値を出力する装置である。
【０００３】
この区間再利用装置において実行結果の検索を高速化するための装置の一つとして、検索時の索引として用いられるキャッシュインデックスを、ハッシュ関数を用いて生成する装置が提案されている（例えば、非特許文献１参照。）。このハッシュ関数を用いてキャッシュインデックスを生成する区間再利用装置は、アッカーマン関数の２つの入力の値をハッシュ関数の入力とすることによって、キャッシュインデックスであるハッシュ値を算出する。そして、この区間再利用装置は、その生成したキャッシュインデックスに基づいてアッカーマン関数の実行結果を保存し、実行結果を検索する場合にはその生成したキャッシュインデックスを索引として用いて実行結果を検索する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００４−２５８９０５号公報（図１）
【非特許文献】
【０００５】
【非特許文献１】Stephen E.Richardson著、「Caching Function Results: Faster Arithmetic by Avoiding Unnecessary Computation」、Sun Microsystems Laboratories, Inc.、１９９２年
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記の従来技術では、アッカーマン関数の２つの入力の値から生成したキャッシュインデックスを用いて実行結果を検索することによって、実行結果の検索に要する時間を削減することができる。しかしながら、このような区間再利用装置では、実行結果を保存しておくメモリのサイズに合わせた単一のハッシュ関数を用いているため、必要なキャッシュインデックスの数に応じてハッシュ関数を選択することはできないという問題が生じる。
【０００７】
このような区間再利用装置では、例えば、保持させる実行結果の数に対してハッシュ値（キャッシュインデックス）のビット長が不要に長いために検索に時間が掛かる場合がある。この検索に時間が掛かることにより、このような区間再利用装置では、値再利用の効率の低下が生じてしまう。
【０００８】
そこで、本発明はこのような状況に鑑みてなされたものであり、値再利用（メモ化）を行う際、実行結果を保存しておくメモリに保持させるデータのビット長を短縮させることにより、値再利用の効率を改善することを目的とする。
【課題を解決するための手段】
【０００９】
本発明は、上記課題を解決するためになされたものであり、その第１の側面は、プログラムにおける複数の命令区間の使用態様を解析して上記命令区間のうち実行結果が再び利用される再利用区間を判別する解析部と、上記再利用区間の開始アドレスのビット幅より狭いビット幅の値により上記再利用区間を識別する区間識別値を生成するための区間識別値生成関数の候補である候補関数を用いることによって、上記区間識別値の候補である候補値を上記候補関数に関連付けて上記開始アドレスから生成する候補値生成部と、上記候補値生成部により生成された上記候補値を上記関連付けられた候補関数ごとに候補値リストとして保持する候補値テーブルと、上記候補値が全て互いに異なる上記候補値リストを抽出し、この抽出された候補値リストのうち上記候補値のビット幅に基づいて選択された候補値リストの上記関連付けられた候補関数を上記区間識別値生成関数として出力する区間識別値生成関数出力部と、上記区間識別値生成関数が埋め込まれた機械語プログラムを上記解析されたプログラムおよび上記区間識別値生成関数に基づいて生成する機械語プログラム生成部とを具備するコンパイル処理装置およびその処理方法ならびに当該方法をコンピュータに実行させるプログラムである。これにより、候補関数から選択した区間識別値生成関数をプログラムに埋め込ませるという作用をもたらす。
【００１０】
また、この第１の側面において、上記候補関数は、ハッシュ関数であり、上記区間識別値生成関数出力部は、上記抽出された候補値リストのうち上記候補値のビット幅に基づいて選択された候補値リストの上記関連付けられたハッシュ関数を上記区間識別値生成関数として出力するようにしてもよい。これにより、ハッシュ関数をプログラムに埋め込ませるという作用をもたらす。この場合において、上記ハッシュ関数は、上記開始アドレスの最下位ビットから所定の数のビットにおける値を上記候補値とするハッシュ関数であり、上記区間識別値生成関数出力部は、上記抽出された候補値リストのうち上記候補値のビット幅に基づいて選択された候補値リストの上記関連付けられたハッシュ関数を上記区間識別値生成関数として出力するようにしてもよい。これにより、最下位ビットから所定の数のビットにおける値をハッシュ値として算出するハッシュ関数をプログラムに埋め込ませるという作用をもたらす。
【００１１】
また、この第１の側面において、上記区間識別値生成関数出力部は、上記抽出された候補値リストのうちビット幅が最も狭い上記候補値の候補値リストの上記関連付けられた候補関数を上記区間識別値生成関数として出力するようにしてもよい。これにより、全て互いに異なる候補値を生成する候補関数のうちビット幅が最も狭い候補値を生成する候補関数を区間識別値生成関数として出力させるという作用をもたらす。
【００１２】
また、この第１の側面において、上記区間識別値生成関数出力部は、上記区間識別値生成関数として上記区間識別値生成関数を識別するための識別子を出力し、上記機械語プログラム生成部は、上記識別子が埋め込まれた機械語プログラムを生成するようにしてもよい。これにより、区間識別値生成関数を識別するための識別子が埋め込まれたプログラムを生成させるという作用をもたらす。
【００１３】
また、本発明の第２の側面は、複数の命令区間を実行して実行結果を出力する実行部と、上記命令区間のうち実行結果が再び利用される再利用区間の開始アドレスのビット幅より狭いビット幅の値により上記再利用区間を識別する区間識別値とその上記再利用区間の入力値とその上記再利用区間の実行結果とを実行履歴として保持する履歴メモリと、上記区間識別値および上記入力値に基づいて上記履歴メモリから上記実行履歴を検索し、上記実行履歴が検索された場合には上記実行結果を出力する履歴検索部とを具備するデータ処理装置である。これにより、区間識別値と入力値と実行結果とを実行履歴として履歴メモリに保持させるという作用をもたらす。
【００１４】
また、この第２の側面において、上記実行部が上記再利用区間を実行したときに上記開始アドレスを出力した場合には、上記区間識別値を生成するための区間識別値生成関数を用いて上記開始アドレスから上記区間識別値を生成する区間識別値生成部をさらに具備し、上記実行部は、上記区間識別値生成部に上記区間識別値生成関数を供給し、上記履歴メモリは、上記区間識別値生成部により生成された上記区間識別値と上記入力値と上記実行結果とを上記実行履歴として保持し、上記履歴探索部は、上記区間識別値と上記入力値とに基づいて上記履歴メモリから上記実行履歴を検索し、上記実行履歴が検索された場合には上記実行結果を出力するようにしてもよい。これにより、区間識別値生成部により開始アドレスから生成された区間識別値と、実行部から供給された入力値および実行結果とを実行履歴として履歴メモリに保持させるという作用をもたらす。この場合において、上記実行部は、上記区間識別値生成関数を上記区間識別値生成部に供給し、上記区間識別値生成部は、上記実行部が上記再利用区間を実行したときに上記開始アドレスを出力した場合には、上記実行部から供給された上記区間識別値生成関数を用いて上記開始アドレスから上記区間識別値を生成するようにしてもよい。これにより、実行部から供給された区間識別値生成関数を用いて開始アドレスから区間識別値を生成させるという作用をもたらす。この場合において、上記実行部は、上記区間識別値生成関数を識別する識別子を上記区間識別値生成部に供給し、上記区間識別値生成部は、上記区間識別値生成関数の候補である候補関数から上記区間識別値生成関数を上記識別子に基づいて選択し、上記実行部が上記再利用区間を実行したときに上記開始アドレスを出力した場合には上記選択した区間識別値生成関数を用いて上記開始アドレスから上記区間識別値を生成するようにしてもよい。これにより、実行部から供給された識別値に基づいて候補関数から区間識別値生成関数を選択し、その選択した区間識別値を用いて開始アドレスから区間識別値を生成させるという作用をもたらす。
【００１５】
また、この第２の側面において、上記実行部は、上記区間識別値が含まれる命令により上記再利用区間を実行した場合には上記区間識別値を上記履歴メモリに供給し、上記履歴メモリは、上記区間識別値と上記入力値と上記実行結果とを上記実行履歴として保持し、上記履歴探索部は、上記区間識別値と上記入力値とに基づいて上記履歴メモリから上記実行履歴を検索し、上記実行履歴が検索された場合には上記実行結果を出力するようにしてもよい。これにより、実行部から供給された区間識別値と入力値と実行結果とを実行履歴として履歴メモリに保持させるという作用をもたらす。
【００１６】
また、本発明の第３の側面は、プログラムにおける複数の命令区間の使用態様を解析して上記命令区間のうち実行結果が再び利用される再利用区間を判別する解析部と、上記再利用区間の開始アドレスのビット幅より狭いビット幅の値により上記再利用区間を識別する区間識別値を生成するための区間識別値生成関数の候補である候補関数を用いることによって、上記区間識別値の候補である候補値を上記候補関数に関連付けて生成する候補値生成部と、上記候補値生成部により生成された上記候補値を上記関連付けられた候補関数ごとに候補値リストとして保持する候補値テーブルと、上記候補値が全て互いに異なる上記候補値リストを抽出し、この抽出された候補値リストのうち上記候補値のビット幅に基づいて選択された候補値リストの上記候補値を上記区間識別値として出力する区間識別値出力部と、上記再利用区間を呼び出す命令を上記区間識別値が含まれる区間識別値付命令に変換する命令変換部と、上記再利用区間が上記区間識別値付命令により呼び出される機械語プログラムを上記区間識別値付命令が含まれるソースプログラムに基づいて生成する機械語プログラム生成部とを具備するコンパイル処理装置である。これにより、区間識別値付命令が含まれるプログラムを生成させるという作用をもたらす。
【００１７】
また、この第３の側面において、上記候補値生成部は、上記開始アドレスの所定の順序に従って付与された番号を入力の値とする上記候補関数を用いることによって上記候補値を生成するようにしてもよい。これにより、開始アドレスの所定の順序に従って付与された番号から候補値を生成させるという作用をもたらす。
【００１８】
また、この第３の側面において、上記候補値生成部は、上記開始アドレスを入力の値とする上記候補関数を用いることによって上記候補値を生成するようにしてもよい。これにより、開始アドレスから候補値を生成させるという作用をもたらす。
【００１９】
また、本発明の第４の側面は、複数の命令区間を実行して実行結果を出力する実行部と、上記再利用区間の開始アドレスのビット幅より狭いビット幅の値により上記再利用区間を識別する区間識別値を生成するための区間識別値生成関数の候補である候補関数を用いることによって、上記区間識別値の候補である候補値を上記候補関数に関連付けて上記開始アドレスから生成する候補値生成部と、上記候補値生成部により生成された上記候補値を上記関連付けられた候補関数ごとに候補値リストとして保持する候補値テーブルと、上記候補値が全て互いに異なる上記候補値リストを抽出し、この抽出された候補値リストのうち上記候補値のビット幅に基づいて選択された候補値リストの上記関連付けられた候補関数を区間識別値生成関数として出力する区間識別値生成関数出力部と、上記実行部が上記再利用区間を実行したときに上記開始アドレスが出力された場合には上記区間識別値生成関数を用いて上記開始アドレスから上記区間識別値を生成する区間識別値生成部と、上記再利用区間の上記区間識別値と入力値と実行結果とを実行履歴として保持する履歴メモリと、上記区間識別値および上記入力値に基づいて上記履歴メモリから上記実行履歴を検索し、上記実行履歴が検索された場合には上記実行結果を出力する履歴検索部とを具備するデータ処理装置である。これにより、区間識別値生成関数出力部が出力した区間識別値生成関数を用いて開始アドレスから区間識別値を生成させて、この生成された区間識別値と実行部から供給された入力値および実行結果とを実行履歴として履歴メモリに保持させるという作用をもたらす。
【発明の効果】
【００２０】
そこで、本発明はこのような状況に鑑みてなされたものであり、値再利用（メモ化）を行う際、実行結果を保存しておくメモリに保持させるデータのビット長を短縮させることにより、値再利用の効率を改善することを目的とする。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１の実施の形態におけるコンパイル処理装置１００の構成例を示すブロック図である。
【図２】本発明の第１の実施の形態における再利用命令判別部１２０が解析するプログラムの一例を示す概念図である。
【図３】本発明の第１の実施の形態におけるハッシュ関数決定部２００の構成例を示すブロック図である。
【図４】本発明の第１の実施の形態における候補ハッシュ値生成部２３０が生成するハッシュ値の一例を示す概念図である。
【図５】本発明の第１の実施の形態におけるハッシュ値テーブル２４０に保持されるハッシュ値の一例を示す概念図である。
【図６】本発明の第１の実施の形態におけるハッシュ関数指定命令の一例を示す概念図である。
【図７】本発明の第１の実施の形態におけるコンパイル処理装置１００によるコンパイル処理の処理手順を示すフローチャートである。
【図８】本発明の第１の実施の形態におけるハッシュ関数決定部２００によるハッシュ関数決定処理（ステップＳ９２０）の処理手順例の前半を示すフローチャートである。
【図９】本発明の第１の実施の形態におけるハッシュ関数決定部２００によるハッシュ関数決定処理（ステップＳ９２０）の処理手順例の後半を示すフローチャートである。
【図１０】本発明の第２の実施の形態におけるデータ処理装置３００の構成例を示すブロック図である。
【図１１】本発明の第２の実施の形態におけるプロセッサコア４００とハッシュ変換部５００と履歴管理部６００との構成例を示すブロック図である。
【図１２】本発明の第２の実施の形態における履歴メモリ６３０のデータ構造の一例を示す概念図である。
【図１３】本発明の第２の実施の形態におけるデータ処理装置３００による命令処理方法の処理手順例を示すフローチャートである。
【図１４】本発明の第３の実施の形態におけるコンパイル処理装置１００の構成例を示すブロック図である。
【図１５】本発明の第３の実施の形態におけるハッシュ値決定部７００の構成例を示すブロック図である。
【図１６】本発明の第３の実施の形態におけるハッシュ値テーブル７４０に保持されるハッシュ値の一例を示す概念図である。
【図１７】本発明の第３の実施の形態における関数の呼出し命令および関数の再利用命令の一例を示す概念図である。
【図１８】本発明の第３の実施の形態におけるコンパイル処理装置１００によるコンパイル処理の処理手順を示すフローチャートである。
【図１９】本発明の第３の実施の形態におけるハッシュ値決定部７００によるハッシュ値決定処理（ステップＳ９６０）の処理手順例の前半を示すフローチャートである。
【図２０】本発明の第３の実施の形態におけるハッシュ値決定部７００によるハッシュ値決定処理（ステップＳ９６０）の処理手順例の後半を示すフローチャートである。
【図２１】本発明の第４の実施の形態におけるデータ処理装置３００の構成例を示すブロック図である。
【図２２】本発明の第４の実施の形態におけるプロセッサコア４００および履歴管理部６００の構成例を示すブロック図である。
【図２３】本発明の第４の実施の形態におけるデータ処理装置３００による命令処理方法の処理手順例を示すフローチャートである。
【図２４】本発明の第５の実施の形態におけるデータ処理装置３００の構成例を示すブロック図である。
【図２５】本発明の第５の実施の形態におけるプロセッサコア４００とハッシュ変換部５００と履歴管理部６００との構成例を示すブロック図である。
【図２６】本発明の第５の実施の形態におけるデータ処理装置３００による命令処理方法の処理手順例を示すフローチャートである。
【図２７】本発明の第５の実施の形態におけるプログラム実行処理（ステップＳ９９０）の処理手順例を示すフローチャートである。
【発明を実施するための形態】
【００２２】
以下、本発明を実施するための形態（以下、実施の形態と称する）について説明する。説明は以下の順序により行う。
１．第１の実施の形態（コンパイル処理制御：ハッシュ関数を選択してプログラムに埋め込む例）
２．第２の実施の形態（データ処理制御：ハッシュ関数が埋め込まれたプログラムを処理する例）
３．第３の実施の形態（コンパイル処理制御：ハッシュ値を選択してハッシュ値付再利用命令を生成する例）
４．第４の実施の形態（データ処理制御：ハッシュ値付再利用命令を処理する例）
５．第５の実施の形態（データ処理制御：既に生成されたオブジェクトプログラムの再利用区間の開始アドレスからハッシュ値を生成する例）
【００２３】
＜１．第１の実施の形態＞
［本発明の第１の実施の形態におけるコンパイル処理装置１００の構成例］
図１は、本発明の第１の実施の形態におけるコンパイル処理装置１００の構成例を示すブロック図である。このコンパイル処理装置１００は、ソースプログラム記憶部１１０と、再利用命令判別部１２０と、ハッシュ関数決定部２００と、機械語プログラム生成部１４０と、オブジェクトプログラム記憶部１５０とを備える。
【００２４】
ソースプログラム記憶部１１０は、コンパイルを行うソースプログラムを記憶するものである。このソースプログラムは、例えば、実行結果が再び利用される再利用区間が含まれるソースプログラムである。このソースプログラム記憶部１１０は、記憶したソースプログラムを再利用命令判別部１２０に供給する。
【００２５】
再利用命令判別部１２０は、ソースプログラム記憶部１１０から読み出したソースプログラムを解析して、再利用命令が含まれるプログラムを生成するものである。ここで、再利用命令とは、再利用区間と再利用しない区間とを、再利用される度合いに基づいて区別することによって、再利用区間が呼出された際に実行結果を再利用するための処理をデータ処理装置に行わせる命令である。
【００２６】
この再利用命令判別部１２０は、再利用候補区間抽出部１２１と、再利用候補区間解析部１２２と、再利用度生成部１２３と、再利用命令変換部１２４とを備える。この再利用命令判別部１２０は、その生成した再利用命令が含まれるプログラムをハッシュ関数決定部２００に供給する。なお、再利用命令判別部１２０は、特許請求の範囲に記載の解析部の一例である。
【００２７】
再利用候補区間抽出部１２１は、複数の命令区間のうち、実行結果を再利用する再利用区間の候補となる再利用候補区間をプログラムから抽出するものである。ここでは、コンパイル処理装置１００が処理する命令区間は関数またはループを想定するものとする。この再利用候補区間抽出部１２１は、関数およびループなどの複数回呼び出される可能性がある命令区間を再利用候補区間として抽出する。
【００２８】
また、この再利用候補区間抽出部１２１は、入力値が同じでも異なる実行結果になる関数などの実行結果が再利用できる可能性が無い関数を、再利用候補区間から除外する。なお、ここで、入力値とは、関数またはループの実行に必要な値であって、引数で構成される値であり、例えば、３つの変数を引数とする関数の場合には、この３つの変数の値である。この再利用候補区間抽出部１２１は、例えば、システムコールを含む関数または乱数発生関数を再利用候補区間の対象から除外する。この再利用候補区間抽出部１２１は、抽出した再利用候補区間の識別情報をプログラムとともに再利用候補区間解析部１２２に供給する。
【００２９】
再利用候補区間解析部１２２は、再利用候補区間抽出部１２１により抽出された再利用候補区間に関する使用態様を解析するものである。この再利用候補区間解析部１２２は、例えば、関数およびループの入力値である引数に関する内容と、関数およびループの呼出し回数に関する内容とを使用態様として解析する。また、再利用候補区間は、特許請求の範囲に記載の命令区間の一例である。
【００３０】
再利用度生成部１２３は、再利用候補区間解析部１２２から供給された解析結果に基づいて、再利用候補区間の実行結果が再び利用される度合いを示す再利用度を生成するものである。この再利用度生成部１２３は、例えば、再利用候補区間の入力値の組合せに応じて再利用度を生成する。この場合には、再利用候補区間の入力値の組合せが少ないほど再利用される度合いは高くなるため、入力値の組合せの数を分母とする再利用度を生成する。この再利用度生成部１２３は、その生成した再利用度を再利用候補区間の識別情報およびプログラムとともに再利用命令変換部１２４に供給する。
【００３１】
再利用命令変換部１２４は、再利用度生成部１２３から供給された再利用度に基づいて、実行結果を再利用させる再利用候補区間の呼出し命令を再利用命令に変換するものである。例えば、実行結果を再利用させる再利用候補区間が関数である場合には、関数を呼出す命令であるアセンブリ言語の「ｃａｌｌ」命令を、再利用命令として新たに規定した「ｍｅｍｏｃａｌｌ」命令に変換する。この再利用命令変換部１２４は、その変換した命令を含むプログラムをハッシュ関数決定部２００に供給する。
【００３２】
ハッシュ関数決定部２００は、再利用区間を識別するための開始アドレスからハッシュ値を生成するハッシュ関数を決定するものである。このハッシュ関数決定部２００は、例えば、再利用区間の開始アドレスを関数入力値として複数のハッシュ関数を用いて、再利用区間の開始アドレスに基づくハッシュ値をハッシュ関数ごとに生成する。ここで、関数入力値とは、ハッシュ関数の入力となる値である。そして、このハッシュ関数決定部２００は、複数のハッシュ関数のうち、値が全て互いに異なるハッシュ値であってビット幅が最も狭いハッシュ値を生成したハッシュ関数を決定して出力する。すなわち、このハッシュ関数決定部２００は、再利用区間の開始アドレスのビット幅より狭いビット幅の値により再利用区間を識別するハッシュ値を生成するハッシュ関数を決定して出力する。このハッシュ関数決定部２００は、その決定したハッシュ関数をプログラムとともに機械語プログラム生成部１４０に供給する。
【００３３】
機械語プログラム生成部１４０は、ハッシュ関数決定部２００から供給されたプログラムに基づいて、機械語のプログラムであるオブジェクトプログラムを生成するものである。この機械語プログラム生成部１４０は、例えば、ハッシュ関数決定部２００が決定したハッシュ関数が埋め込まれたオブジェクトプログラムを生成する。また、この機械語プログラム生成部１４０は、そのオブジェクトプログラムに埋め込まれたハッシュ関数をそのオブジェクトプログラムを実行するデータ処理装置に認識させるためのハッシュ関数指定命令をオブジェクトプログラムに追加する。この機械語プログラム生成部１４０は、その生成したオブジェクトプログラムをオブジェクトプログラム記憶部１５０に供給する。
【００３４】
オブジェクトプログラム記憶部１５０は、機械語プログラム生成部１４０から供給されたオブジェクトプログラムを記憶するものである。
【００３５】
このように、コンパイル処理装置１００は、まず、関数の実行結果が再利用される度合いに応じて関数の呼出し命令を再利用命令に変換することによって、再利用区間と再利用されない区間とが区別できるようにする。そして、コンパイル処理装置１００は、再利用区間を識別するためのハッシュ値を生成するためのハッシュ関数を決定することによって、その決定したハッシュ関数を埋め込んだプログラムを生成することができる。
【００３６】
なお、ここでは、コンパイル処理装置１００は、関数を再利用対象とする例について説明したが、ループに関しても同様に再利用対象とすることができる。
【００３７】
なお、ここでは、便宜上、再利用候補区間解析部１２２が再利用候補区間の使用態様を関数毎に解析する例について説明したが、より詳細に使用態様を解析するために関数の呼出し命令毎に解析するものとしてもよい。また、再利用度生成部１２３についても再利用度を関数毎に生成する例について説明したが、より詳細に解析するために関数の呼出し命令毎に生成するものとしてもよい。この場合において、再利用命令変換部１２４は、関数は同じであっても関数の呼出し命令毎に異なる再利用度に基づいて、関数の呼出し命令毎に呼出し命令を再利用命令に変換する。
【００３８】
また、ここでは、再利用度を生成することによって再利用命令に変換する例について説明したが、本発明はこれに限定されるものではない。例えば、関数を呼び出す命令を全て再利用対象としてもよい。
【００３９】
［本発明の第１の実施の形態における再利用命令判別部１２０が解析するプログラム例］
図２は、本発明の第１の実施の形態における再利用命令判別部１２０が解析するプログラムの一例を示す概念図である。
【００４０】
ここでは、再利用候補区間の入力値の組合せと、その入力値の組合せに基づいて再利用度生成部１２３が生成する再利用度とについて一例を説明する。ここでは、再利用候補区間解析部１２２において以下のＣ言語のプログラムが解析されたことを想定する。
【００４１】
まず、再利用候補区間解析部１２２は、図２のプログラムにおける４つの関数（ｆｕｎｃＡ乃至Ｄ）の入力値の組合せについて解析する。ｃｈａｒ型の１個の変数を引数とする関数（ｆｕｎｃＡ）については、ｃｈａｒ型は１６ビットのバイナリ文字データであるため、入力値の組合せは最大２１６個と解析する。ｃｈａｒ型の１個の変数とｂｏｏｌ（Boolean）型の１個の変数を引数とする関数（ｆｕｎｃＢ）については、ｂｏｏｌ型は１ビットのバイナリ数値データであるため、「２１６×２＝２１７」により入力値の組合せは最大２１７個と解析する。
【００４２】
さらに、ｂｏｏｌ型の１個の変数を引数とする関数（ｆｕｎｃＣ）については、入力値の組合せは最大２個と解析する。ｉｎｔ（integer）型の１個の変数を引数とする関数（ｆｕｎｃＤ）については、ｉｎｔ型は３２ビットのバイナリ数値データであるため、入力値の組合せは最大２３２個と解析する。
【００４３】
そして、再利用度生成部１２３は、４つの関数（ｆｕｎｃＡ乃至Ｄ）の解析した結果に基づいて、入力値の組合せの数を分母とする再利用度を生成することにより以下の関係の再利用度を生成する。
【数１】
2011096153.tif 000003
【００４４】
このように、ｂｏｏｌ型の１個の変数を引数とする関数（ｆｕｎｃＣ）の再利用度が１番高く、ｃｈａｒ型の１個の変数を引数とする関数（ｆｕｎｃＡ）の再利用度が２番目に高くなる。ｃｈａｒ型の１個の変数とｂｏｏｌ型の１個の変数を引数とする関数（ｆｕｎｃＢ）の再利用度が３番目に高く、ｉｎｔ型の１個の変数を引数とする関数（ｆｕｎｃＤ）の再利用度が１番低くなる。
【００４５】
すなわち、再利用候補区間解析部１２２は再利用候補区間を解析し、再利用度生成部１２３は、その解析結果に基づいて生成した再利用度により、再利用区間とする際の順位付けを再利用候補区間に対して行う。そして、再利用命令変換部１２４は、この再利用度の高い再利用候補区間から順に再利用区間として決定する。
これにより、コンパイル処理装置１００は、再利用される度合いの高い再利用候補区間を再利用区間とするオブジェクトプログラムを生成することができる。
【００４６】
［本発明の第１の実施の形態におけるハッシュ関数決定部２００の構成例］
図３は、本発明の第１の実施の形態におけるハッシュ関数決定部２００の構成例を示すブロック図である。このハッシュ関数決定部２００は、開始アドレス取得部２１０と、候補ハッシュ関数保持部２２０と、候補ハッシュ値生成部２３０と、ハッシュ値テーブル２４０と、ハッシュ関数出力部２５０とを備える。
【００４７】
開始アドレス取得部２１０は、再利用命令変換部１２４からの再利用命令を含むプログラムから再利用区間の開始アドレスを取得するものである。この開始アドレス取得部２１０は、その取得した開始アドレスを開始アドレスリストとして保持する。この開始アドレス取得部２１０は、その取得した開始アドレスを候補ハッシュ値生成部２３０に供給する。
【００４８】
候補ハッシュ関数保持部２２０は、開始アドレスをハッシュ値に変換するための複数のハッシュ関数を保持するものである。すなわち、この候補ハッシュ関数保持部２２０は、ハッシュ関数決定部２００が決定するハッシュ関数の候補となるハッシュ関数を保持する。この候補ハッシュ関数保持部２２０は、ハッシュ関数決定部２００が決定するハッシュ関数の候補として予め定められたハッシュ関数を保持する。
【００４９】
この候補ハッシュ関数保持部２２０は、例えば、１０個のハッシュ関数を保持している場合には、その１０個のハッシュ関数を候補ハッシュ値生成部２３０に供給する。また、この候補ハッシュ関数保持部２２０は、例えば、ハッシュ関数出力部２５０において１個のハッシュ関数が決定された場合には、そのハッシュ関数をハッシュ関数出力部２５０に供給する。なお、候補ハッシュ関数保持部２２０から供給されるハッシュ関数は、特許請求の範囲に記載の候補関数の一例である。
【００５０】
候補ハッシュ値生成部２３０は、開始アドレス取得部２１０から供給された開始アドレスを関数入力値とし、その関数入力値を候補ハッシュ関数保持部２２０から供給されたハッシュ関数の入力としてハッシュ値を生成するものである。すなわち、この候補ハッシュ値生成部２３０は、ハッシュ関数決定部２００が決定するハッシュ関数の候補となるハッシュ関数を用いて、再利用区間を識別するためのハッシュ値の候補となるハッシュ値を開始アドレスから生成する。また、この候補ハッシュ値生成部２３０は、ハッシュ値を生成する際に、そのハッシュ値を生成したハッシュ関数をそのハッシュ値に関連付けて、どのハッシュ関数から生成されたか識別できるようにする。
【００５１】
この候補ハッシュ値生成部２３０は、例えば、開始アドレス取得部２１０に１０個の開始アドレスが保持され、かつ、候補ハッシュ関数保持部２２０に１０個のハッシュ関数が保持されている場合には、全組合せの「１０×１０＝１００」個のハッシュ値を生成する。
【００５２】
この候補ハッシュ値生成部２３０は、その生成したハッシュ値をハッシュ値テーブル２４０に供給する。なお、候補ハッシュ値生成部２３０は、特許請求の範囲に記載の候補値生成部の一例である。また、候補ハッシュ値生成部２３０が生成するハッシュ値は、特許請求の範囲に記載の候補値の一例である。
【００５３】
ハッシュ値テーブル２４０は、候補ハッシュ値生成部２３０から供給されたハッシュ値を保持するものである。このハッシュ値テーブル２４０は、ハッシュ値をそのハッシュ値を生成したハッシュ関数ごとにハッシュ値リストとして保持する。また、このハッシュ値テーブル２４０は、保持したハッシュ値リストをハッシュ関数出力部２５０に供給する。なお、ハッシュ値テーブル２４０は、特許請求の範囲に記載の候補値テーブルの一例である。また、ハッシュ値リストは、特許請求の範囲に記載の候補値リストの一例である。
【００５４】
ハッシュ関数出力部２５０は、ハッシュ値が全て互いに異なるハッシュ値リストを抽出し、この抽出されたハッシュ値リストのうちハッシュ値のビット幅が最も狭くなるハッシュ値リストに関連付けられたハッシュ関数を出力するものである。このハッシュ関数出力部２５０は、ユニークハッシュ値リスト判別部２５１および確定ハッシュ関数選択部２５２を備える。なお、ハッシュ関数出力部２５０は、特許請求の範囲に記載の区間識別値生成関数出力部の一例である。なお、ハッシュ関数出力部２５０が出力するハッシュ関数は、特許請求の範囲に記載の区間識別値生成関数の一例である。
【００５５】
ユニークハッシュ値リスト判別部２５１は、ハッシュ値テーブル２４０に保持されているハッシュ値リストのうちハッシュ値が全て互いに異なるハッシュ値リストを判別するものである。このユニークハッシュ値リスト判別部２５１は、例えば、ハッシュ値テーブル２４０に保持された１０個のハッシュ値リストのうちハッシュ値が全て互いに異なるものが３個の場合にはその３個のハッシュ値リストを判別する。このユニークハッシュ値リスト判別部２５１は、その判別したハッシュ値リストを確定ハッシュ関数選択部２５２に供給する。
【００５６】
確定ハッシュ関数選択部２５２は、ユニークハッシュ値リスト判別部２５１から供給されたハッシュ値リストのうちハッシュ値のビット幅が最も狭くなるハッシュ値リストに関連付けられたハッシュ関数を出力するものである。すなわち、この確定ハッシュ関数選択部２５２は、候補ハッシュ関数保持部２２０が保持している複数のハッシュ関数のうちから１つのハッシュ関数を確定して、その確定したハッシュ関数を出力する。この確定ハッシュ関数選択部２５２は、ユニークハッシュ値リスト判別部２５１から供給されたハッシュ値が全て互いに異なるハッシュ値リストのうちハッシュ値のビット幅が最も狭いハッシュ値リストを一つ検出する。そして、この確定ハッシュ関数選択部２５２は、その検出したハッシュ値リストに関連付けられたハッシュ関数を候補ハッシュ関数保持部２２０から取得し、その取得したハッシュ関数を機械語プログラム生成部１４０に供給する。
【００５７】
このように、本発明の第１の実施の形態では、ハッシュ関数決定部２００を設けることにより、複数のハッシュ関数のうち全て互いに異なるハッシュ値であってビット幅が最も狭いハッシュ値を生成するハッシュ関数をプログラムに埋め込むことができる。
【００５８】
なお、ここでは、候補ハッシュ関数保持部２２０は、保持するハッシュ関数を全て候補ハッシュ値生成部２３０に供給する一例について説明したが、本発明はこれに限定されるものではない。例えば、候補ハッシュ関数保持部２２０は外部から制御できるようにすることによって、候補ハッシュ値生成部２３０に供給するハッシュ関数を、プログラムに応じて外部から指定できるようにしてもよい。
【００５９】
また、ここでは、確定ハッシュ関数選択部２５２は、ハッシュ関数を機械語プログラム生成部１４０に供給する一例について説明したが、本発明はこれに限定されるものではない。例えば、確定ハッシュ関数選択部２５２は、ハッシュ関数を指し示す識別子をハッシュ関数の代わりに供給するようにしてもよい。この例において、機械語プログラム生成部１４０は、確定ハッシュ関数選択部２５２から供給された識別子が埋め込まれたオブジェクトプログラムを生成する。これにより、ハッシュ関数をオブジェクトプログラムに埋め込む方法と比較してオブジェクトプログラムを短くすることができるため、ハッシュ関数を頻繁に交換するプログラムを実行する場合にはプログラムの実行処理を早くすることができる。なお、このハッシュ関数の代わりにオブジェクトプログラムに埋め込まれる識別子は、特許請求の範囲に記載の識別子の一例である。
【００６０】
［本発明の第１の実施の形態における候補ハッシュ値生成部２３０が生成するハッシュ値の一例］
図４は、本発明の第１の実施の形態における候補ハッシュ値生成部２３０が生成するハッシュ値の一例を示す概念図である。ここでは、開始アドレスのビット幅は６４ビットとする。また、ここでは、左端は最上位ビット（ＭＳＢ：Most Significant Bit）を示し、右端は最下位ビット（ＬＳＢ：Least Significant Bit）を示すものとする。
【００６１】
また、ここでは、一例として、候補ハッシュ関数保持部２２０が保持している複数のハッシュ関数は、再利用区間の開始アドレスの最下位ビットから所定の数のビットにおける値を算出する関数を想定する。以下の式１にこのハッシュ関数の一例を示す。
【数２】
2011096153.tif 000004
【００６２】
ここで、ｈは、候補ハッシュ値生成部２３０が生成するハッシュ値である。また、ａは、ハッシュ関数の関数入力値であり、ここではハッシュ値テーブル２４０から候補ハッシュ値生成部２３０に供給される開始アドレスである。また、＆は、ビット単位のＡＮＤ演算である。ｍｂは、数値（ｍ）を２進数（ｂ）で表現したマスクビットである。また、式１の下に示されている式２は、式１のｍを算出する式の一例である。式２のｉは、式１の算出するｈ（ハッシュ値）のビット幅を指定するための値である。
【００６３】
図４（ａ）には、ハッシュ値テーブル２４０から供給される開始アドレスの一例である開始アドレス２６１が示されている。この開始アドレス２６１は、ＬＳＢ側から第０乃至６３ビットの６４ビットで構成されるビット列である。この開始アドレス２６１は、候補ハッシュ値生成部２３０においてハッシュ関数の関数入力値として用いられる。
【００６４】
図４（ｂ）には、図４（ａ）において示した開始アドレスを関数入力値として生成されるハッシュ値の一例であるハッシュ値２６２乃至２６６が示されている。
【００６５】
ハッシュ値２６２は、式２のｉ（ビット幅）が「１」と指定された式１を用いて、開始アドレス２６１から算出されたｈ（ハッシュ値）である。式２のｉ（ビット幅）を「１」とすると、ｍは「１」となる。すなわち、式１は、次式３に示すハッシュ関数となる。
【数３】
2011096153.tif 000005
【００６６】
この式３に示すハッシュ関数により、０番の値が「０」である１ビットのハッシュ値２６２が開始アドレス２６１の０番の値（０）に基づいて算出される。
【００６７】
ハッシュ値２６３は、式２のｉ（ビット幅）が「２」と指定された式１を用いて、開始アドレス２６１から算出されたｈ（ハッシュ値）である。式２のｉ（ビット幅）を「２」とすると、ｍは「３」となる。すなわち、式１は、次式４に示すハッシュ関数となる。
【数４】
2011096153.tif 000006
【００６８】
この式４に示すハッシュ関数により、０番および１番の値が「０および１」である２ビットのビット列のハッシュ値２６３が開始アドレス２６１の０番および１番の値（０および１）に基づいて算出される。
【００６９】
ハッシュ値２６４は、式２のｉ（ビット幅）が「３」と指定された式１を用いて、開始アドレス２６１から算出されたｈ（ハッシュ値）である。式２のｉ（ビット幅）を「３」とすると、ｍは「７」となる。すなわち、式１は、次式５に示すハッシュ関数となる。
【数５】
2011096153.tif 000007
【００７０】
この式５に示すハッシュ関数により、０番乃至２番の値が「０、１および０」である３ビットのビット列のハッシュ値２６４が開始アドレス２６１の０番乃至２番の値（０、１および０）に基づいて算出される。
【００７１】
ハッシュ値２６５は、式２のｉ（ビット幅）が「４」と指定された式１を用いて、開始アドレス２６１から算出されたｈ（ハッシュ値）である。式２のｉ（ビット幅）を「４」とすると、ｍは「１５」となる。すなわち、式１は、次式６に示すハッシュ関数となる。
【数６】
2011096153.tif 000008
【００７２】
この式６に示すハッシュ関数により、０番乃至３番の値が「０、１、０および１」である４ビットのビット列のハッシュ値２６５が開始アドレス２６１の０番乃至３番の値（０、１、０および１）に基づいて算出される。
【００７３】
ハッシュ値２６６は、式２のｉ（ビット幅）が「５」と指定された式１を用いて、開始アドレス２６１から算出されたｈ（ハッシュ値）である。式２のｉ（ビット幅）を「５」とすると、ｍは「３１」となる。すなわち、式１は、次式７に示すハッシュ関数となる。
【数７】
2011096153.tif 000009
【００７４】
この式７に示すハッシュ関数により、０番乃至４番の値が「０、１、０、１および１」である５ビットのビット列のハッシュ値２６６が開始アドレス２６１の０番乃至４番の値（０、１、０、１および１）に基づいて算出される。
【００７５】
このように、本発明の第１の実施の形態では、候補ハッシュ値生成部２３０を設けることによって、複数のハッシュ関数を用いて複数のハッシュ値を生成することができる。
【００７６】
なお、ここでは、式１乃至式７において示したハッシュ関数を一例として説明したが、本発明はこれに限定されるものではない。例えば、開始アドレスの最上位から所定の数のビットと最下位から所定の数のビットとの排他的論理和（ＥＯＲ：Exclusive OR）を算出するハッシュ関数なども考えられる。
【００７７】
［本発明の第１の実施の形態におけるハッシュ値テーブル２４０に保持されるハッシュ値の一例］
図５は、本発明の第１の実施の形態におけるハッシュ値テーブル２４０に保持されるハッシュ値の一例を示す概念図である。ここでは、図４において説明した式３乃至式７のハッシュ関数を用いてハッシュ値を生成することを想定する。また、ここでは、プログラムにおける再利用区間は８個の関数（ｆｕｎｃＡ乃至ｆｕｎｃＨ）とする。
【００７８】
開始アドレスリスト２７１には、ハッシュ値テーブル２４０に登録されたハッシュ値の基となった開始アドレスのリスト名が示されている。この開始アドレスリスト２７１において、行２８２にはｆｕｎｃＡに関する値が示され、行２８３にはｆｕｎｃＢに関する値が示され、行２８４にはｆｕｎｃＣに関する値が示されている。さらに、行２８５にはｆｕｎｃＤに関する値が示され、行２８６にはｆｕｎｃＥに関する値が示され、行２８７にはｆｕｎｃＦに関する値が示され、行２８８にはｆｕｎｃＧが示され、行２８９にはｆｕｎｃＨに関する値が示されていることを表している。
【００７９】
ハッシュ値リスト２７２には、式１のｉ（ビット幅）を「５」としたハッシュ関数である式７を用いて算出されたハッシュ値のリストが示されている。ハッシュ値リスト２７２の行２８１には、式１のｉ（ビット幅）を「５」としたハッシュ関数である式７を用いたことを示す「ｉ＝５」が示されている。ハッシュ値リスト２７２の行２８２乃至２８９には、８個の関数（ｆｕｎｃＡ乃至ｆｕｎｃＨ）の開始アドレスを式７の関数入力値として算出されたハッシュ値が示されている。すなわち、ハッシュ値リスト２７２の行２８２乃至２８９には、８つの関数（ｆｕｎｃＡ乃至ｆｕｎｃＨ）の開始アドレスの最下位ビットから５ビットの値がそれぞれ示されている。このハッシュ値リスト２７２の行２８２乃至２８９に示したハッシュ値は、式７と関連付けられてハッシュ値テーブル２４０にリストとして保持される。
【００８０】
ハッシュ値リスト２７３には、式１のｉ（ビット幅）を「４」としたハッシュ関数である式６を用いて算出されたハッシュ値のリストが示されている。ハッシュ値リスト２７３の行２８１には、式１のｉ（ビット幅）を「４」としたハッシュ関数である式６を用いたことを示す「ｉ＝４」が示されている。ハッシュ値リスト２７３の行２８２乃至２８９には、８個の関数（ｆｕｎｃＡ乃至ｆｕｎｃＨ）の開始アドレスを式６の関数入力値として算出されたハッシュ値が示されている。すなわち、ハッシュ値リスト２７３の行２８２乃至２８９には、８つの関数（ｆｕｎｃＡ乃至ｆｕｎｃＨ）の開始アドレスの最下位ビットから４ビットの値がそれぞれ示されている。このハッシュ値リスト２７３の行２８２乃至２８９に示したハッシュ値は、式６と関連付けられてハッシュ値テーブル２４０にリストとして保持される。
【００８１】
ハッシュ値リスト２７４には、式１のｉ（ビット幅）を「３」としたハッシュ関数である式５を用いて算出されたハッシュ値のリストが示されている。ハッシュ値リスト２７４の行２８１には、式１のｉ（ビット幅）を「３」としたハッシュ関数である式５を用いたことを示す「ｉ＝３」が示されている。ハッシュ値リスト２７４の行２８２乃至２８９には、８個の関数（ｆｕｎｃＡ乃至ｆｕｎｃＨ）の開始アドレスを式５の関数入力値として算出されたハッシュ値が示されている。すなわち、ハッシュ値リスト２７４の行２８２乃至２８９には、８つの関数（ｆｕｎｃＡ乃至ｆｕｎｃＨ）の開始アドレスの最下位ビットから３ビットの値がそれぞれ示されている。このハッシュ値リスト２７４の行２８２乃至２８９に示したハッシュ値は、式５と関連付けられてハッシュ値テーブル２４０にリストとして保持される。
【００８２】
ハッシュ値リスト２７５には、式１のｉ（ビット幅）を「２」としたハッシュ関数である式４を用いて算出されたハッシュ値のリストが示されている。ハッシュ値リスト２７５の行２８１には、式１のｉ（ビット幅）を「２」としたハッシュ関数である式４を用いたことを示す「ｉ＝２」が示されている。ハッシュ値リスト２７５の行２８２乃至２８９には、８個の関数（ｆｕｎｃＡ乃至ｆｕｎｃＨ）の開始アドレスを式４の関数入力値として算出されたハッシュ値が示されている。すなわち、ハッシュ値リスト２７５の行２８２乃至２８９には、８つの関数（ｆｕｎｃＡ乃至ｆｕｎｃＨ）の開始アドレスの最下位ビットから２ビットの値がそれぞれ示されている。このハッシュ値リスト２７５の行２８２乃至２８９に示したハッシュ値は、式４と関連付けられてハッシュ値テーブル２４０にリストとして保持される。
【００８３】
ハッシュ値リスト２７６には、式１のｉ（ビット幅）を「１」としたハッシュ関数である式３を用いて算出されたハッシュ値のリストが示されている。ハッシュ値リスト２７６の行２８１には、式１のｉ（ビット幅）を「１」としたハッシュ関数である式３を用いたことを示す「ｉ＝１」が示されている。ハッシュ値リスト２７６の行２８２乃至２８９には、８個の関数（ｆｕｎｃＡ乃至ｆｕｎｃＨ）の開始アドレスを式３の関数入力値として算出されたハッシュ値が示されている。すなわち、ハッシュ値リスト２７６の行２８２乃至２８９には、８つの関数（ｆｕｎｃＡ乃至ｆｕｎｃＨ）の開始アドレスの最下位ビットの値がそれぞれ示されている。このハッシュ値リスト２７６の行２８２乃至２８９に示したハッシュ値は、式３と関連付けられてハッシュ値テーブル２４０にリストとして保持される。
【００８４】
このように、本発明の第１の実施の形態では、ハッシュ値テーブル２４０を用いることによって、ハッシュ値を生成したハッシュ関数に関連付けてリストとして保持することができる。
【００８５】
続いて、図５を用いて、ユニークハッシュ値リスト判別部２５１により判別されるハッシュ値リストと、確定ハッシュ関数選択部２５２が選択するハッシュ関数とについて説明する。
【００８６】
まず、ユニークハッシュ値リスト判別部２５１により、ハッシュ値が全て互いに異なるハッシュ値リストが判別され、その判別されたハッシュ値が全て互いに異なるハッシュ値リストが確定ハッシュ関数選択部２５２に供給される。この時、ハッシュ値リスト２７６は、ｆｕｎｃＡ、ｆｕｎｃＣ、ｆｕｎｃＥおよびｆｕｎｃＧのハッシュ値が「０」で重複し、さらに、その他の４つの関数のハッシュ値が「１」で重複しているため、確定ハッシュ関数選択部２５２に供給されない。
【００８７】
また、ハッシュ値リスト２７５は、ｆｕｎｃＡ、ｆｕｎｃＣおよびｆｕｎｃＥのハッシュ値が「１０」で重複し、さらに、ｆｕｎｃＢ、ｆｕｎｃＦおよびｆｕｎｃＨのハッシュ値が「１１」で重複しているため、確定ハッシュ関数選択部２５２に供給されない。さらに、ハッシュ値リスト２７４は、ｆｕｎｃＡおよびｆｕｎｃＥのハッシュ値が「１１０」で重複し、さらに、ｆｕｎｃＦおよびｆｕｎｃＨのハッシュ値が「０１１」で重複しているため、確定ハッシュ関数選択部２５２に供給されない。
【００８８】
その結果、ハッシュ値が全て互い異なるハッシュ値リストであると判別されたハッシュ値リスト２７２および２７３が、ユニークハッシュ値リスト判別部２５１により確定ハッシュ関数選択部２５２に供給される。
【００８９】
ユニークハッシュ値リスト判別部２５１からハッシュ値リストが供給されると、確定ハッシュ関数選択部２５２は、ユニークハッシュ値リスト判別部２５１から供給されたハッシュ値リストのうちビット幅が最も狭いハッシュ値のハッシュ値リストを検出する。
【００９０】
その結果、４ビットのハッシュ値のハッシュ値リスト２７３と、５ビットのハッシュ値のハッシュ値リスト２７２とのうちハッシュ値リスト２７３がビット幅が最も狭いハッシュ値のハッシュ値リストとして検出される。そして、確定ハッシュ関数選択部２５２は、ハッシュ値リスト２７３に関連付けられたハッシュ関数の式６を候補ハッシュ関数保持部２２０から取得し、ハッシュ関数決定部２００が決定したハッシュ関数としてその取得した式６を出力する。
【００９１】
このように、本発明の第１の実施の形態では、ユニークハッシュ値リスト判別部２５１を設けることによって、ハッシュ値が全て互いに異なるハッシュ値リストを、ハッシュ値テーブル２４０が保持するハッシュ値リストから判別することができる。また、確定ハッシュ関数選択部２５２を設けることによって、ユニークハッシュ値リスト判別部２５１が判別したハッシュ値リストのうち、ビット幅が最も狭いハッシュ値のハッシュ値リストに関連付けられたハッシュ関数を決定することができる。
なお、ここでは、開始アドレスの最下位ビットから所定の数のビットの値をハッシュ値とするハッシュ関数のみを用いてハッシュ値を生成する場合について説明したが、多様なハッシュ関数を用いることによりビット幅がより狭いハッシュ値を生成することができる。
【００９２】
また、ここでは、ハッシュ値が全て互いに異なるハッシュ値リストが存在する場合について説明した。しかしながら、ハッシュ値が全て互いに異なるハッシュ値リストがハッシュ値テーブル２４０に存在しない場合も考えられる。このような場合には、確定ハッシュ関数選択部２５２は、開始アドレスの値をそのまま出力する関数を出力する。あるいは、確定ハッシュ関数選択部２５２は、ハッシュ関数が無いことを示す情報を出力する。
【００９３】
［本発明の第１の実施の形態におけるハッシュ関数指定命令の一例］
次に、本発明の第１の実施の形態におけるコンパイル処理装置１００が生成するハッシュ関数指定命令について図面を参照して説明する。
【００９４】
図６は、本発明の第１の実施の形態におけるハッシュ関数指定命令の一例を示す概念図である。ここでは、データ処理装置のプロセッサコアは、ＭＩＰＳにより構成されることを想定する。また、ここでは、左端は最上位ビット（ＭＳＢ）を示し、右端は最下位ビット（ＬＳＢ）を示している。
【００９５】
図６（ａ）には、オブジェクトプログラムに埋め込まれたハッシュ関数をそのオブジェクトプログラムを実行するデータ処理装置に認識させるためのハッシュ関数指定命令の一例が示されている。このハッシュ関数指定命令は、３２個のビット（０乃至３１番）のビット列により表現されるものである。このハッシュ関数指定命令は、オペコードフィールド２９１、ハッシュ関数番地フィールド２９２、未使用フィールド２９３、および、ユーザ定義命令フィールド（ＵＤＩ：User Definable Instruction）２９５とから構成される。
【００９６】
オペコードフィールド２９１は、命令の種別を指定するフィールドである。このオペコードフィールド２９１は、第２６乃至第３１番目のビットから構成されるビット列である。このハッシュ関数指定命令のオペコードフィールド２９１には、ＳＰＥＣＩＡＬ２命令として「０１１１００」のビット列が格納される。ここで、ＳＰＥＣＩＡＬ２命令とは、ユーザが独自に定義した命令であることを指し示す命令である。
【００９７】
ハッシュ関数番地フィールド２９２は、ハッシュ関数の番地を格納するレジスタを指定するフィールドである。このハッシュ関数番地フィールド２９２は、第２１乃至第２５番目のビットから構成されるビット列である。
【００９８】
未使用フィールド２９３は、ハッシュ関数指定命令では使用されないフィールドである。未使用フィールド２９３は、第６乃至第２０番目のビットから構成される１５ビットのビット列である。この未使用フィールド２９３は、例えば、ビット列（０００００００００００００００）が格納される。
【００９９】
ユーザ定義命令フィールド（ＵＤＩ）２９５は、ＳＰＥＣＩＡＬ２命令において、ユーザが定義した複数の命令のうちの１つの命令を指定するフィールドである。このユーザ定義命令フィールド（ＵＤＩ）２９５は、第０乃至第５番目のビットから構成されるビット列である。このユーザ定義命令フィールド（ＵＤＩ）２９５は、例えば、ビット列（０１０００１）によってハッシュ関数指定命令を指定する。
【０１００】
このように、本発明の第１の実施の形態では、ハッシュ関数指定命令を用いることによって、オブジェクトプログラムに埋め込まれたハッシュ関数をデータ処理装置に利用させることができる。
【０１０１】
続いて、図３において確定ハッシュ関数選択部２５２に関する別の機能として説明した、確定ハッシュ関数選択部２５２が識別子を出力する場合に用いられる識別子供給命令について説明する。ここで、識別子供給命令とは、オブジェクトプログラムを実行するデータ処理装置に識別子を供給し、その識別子をデータ処理装置に利用させるための命令である。
【０１０２】
図６（ｂ）には、ハッシュ関数を指し示す識別子を供給する識別子供給命令の一例が示されている。この識別子供給命令は、３２個のビット（０乃至３１番）のビット列により表現されるものである。
【０１０３】
この識別子供給命令は、オペコードフィールド２９１、識別子フィールド２９４、および、ユーザ定義命令フィールド（ＵＤＩ）２９５とから構成される。なお、ここでは、識別子フィールド２９４以外の各フィールドの機能は、図６（ａ）で示したハッシュ関数指定命令の各フィールドの機能と同様のものであるため、図６（ａ）と同符号を付してここでの詳細な説明を省略する。
【０１０４】
識別子フィールド２９４は、ハッシュ関数決定部２００が決定したハッシュ関数を識別するための識別子を格納するフィールドである。この識別子フィールド２９４は、例えば、第６乃至第２５番目の２０ビットから構成されるビット列である。
【０１０５】
このように、本発明の第１の実施の形態によれば、ハッシュ関数決定部２００が決定したハッシュ関数あるいはそのハッシュ関数を指定する識別子をオブジェクトプログラムに埋め込むことができる。
なお、オペコードフィールド２９１がＳＰＥＣＩＡＬ２命令である場合には、第６乃至第２５番目の２０ビットはユーザが定義可能なエンコード空間である。このため、図６（ａ）および（ｂ）において示したハッシュ関数指定命令および識別子供給命令に限定されるものではなく、種々のパターンが考えられる。
【０１０６】
［本発明の第１の実施の形態におけるコンパイル処理装置１００の動作例］
次に、本発明の第１の実施の形態におけるコンパイル処理装置１００の処理について図面を参照して説明する。図７は、本発明の第１の実施の形態におけるコンパイル処理装置１００によるコンパイル処理の処理手順を示すフローチャートである。
【０１０７】
まず、ソースプログラム記憶部１１０からソースプログラムが読み出される（ステップＳ９１１）。次に、再利用候補区間抽出部１２１により、再利用候補区間が抽出される（ステップＳ９１２）。
【０１０８】
そして、再利用候補区間解析部１２２により、再利用候補区間の使用態様が解析される（ステップＳ９１３）。続いて、再利用度生成部１２３により、再利用候補区間の解析結果に基づいて再利用度が生成される（ステップＳ９１４）。
【０１０９】
次に、再利用命令変換部１２４により、再利用度に基づいて再利用候補区間の呼出し命令が再利用命令に変換される（ステップＳ９１５）。これは、例えば、関数が再利用候補区間である場合には、関数の呼出し命令（ｃａｌｌ）が再利用命令（ｍｅｍｏＣａｌｌ）に変換されることを意味する。このステップＳ９１１乃至Ｓ９１５の一連の処理により、再利用区間が判別される。なお、ステップＳ９１１乃至Ｓ９１５は、特許請求の範囲に記載の解析手順の一例である。
【０１１０】
そして、ハッシュ関数決定部２００により、開始アドレスのビット幅より狭いビット幅で再利用区間を識別するハッシュ値を生成するためのハッシュ関数を決定するハッシュ関数決定処理が行われる（ステップＳ９２０）。
【０１１１】
最後に、機械語プログラム生成部１４０により、ハッシュ関数を埋め込んだ機械語プログラムが解析されたプログラムおよびハッシュ関数に基づいて生成される（ステップＳ９１８）。そして、コンパイル処理は終了する。なお、ステップＳ９１８は、特許請求の範囲に記載の機械語プログラム生成手順の一例である。
【０１１２】
図８は、本発明の第１の実施の形態におけるハッシュ関数決定部２００によるハッシュ関数決定処理（ステップＳ９２０）の処理手順例の前半を示すフローチャートである。なお、ここでは、ハッシュ関数の総数とは、開始アドレスをそのまま出力するハッシュ関数と、図４において示した式３乃至式７のハッシュ関数とを合わせた数の「６」であることを想定する。
まず、開始アドレス取得部２１０により、再利用区間の開始アドレスがプログラムから取得され、開始アドレス取得部２１０に開始アドレスリストとして保持される（ステップＳ９２１）。
【０１１３】
次に、ハッシュ関数カウンタ（ｈｎ）が「１」に初期化される（ステップＳ９２２）。なお、ここで示すハッシュ関数カウンタ（ｈｎ）とは、候補ハッシュ値生成部２３０によりハッシュ値が生成されたハッシュ関数を識別する値である。例えば、このハッシュ関数カウンタ（ｈｎ）は、図５において示したハッシュ値リスト２７２乃至２７６に関連付けられた式７乃至式３を識別するために付加される「１乃至５」の値である。
【０１１４】
なお、ハッシュ関数カウンタ（ｈｎ）の値の「０」には、開始アドレスをそのまま出力するハッシュ関数が割り当てられるものとする。例えば、その開始アドレスをそのまま出力するハッシュ関数として、「ｈ（ハッシュ値）＝ａ（開始アドレス）」などが考えられる。
【０１１５】
続いて、開始アドレスカウンタ（ａｎ）が「０」に初期化される（ステップＳ９２３）。なお、ここで示す開始アドレスカウンタ（ａｎ）とは、ハッシュ関数カウンタ（ｈｎ）とともに用いることによって、ハッシュ値テーブル２４０に保持されたハッシュ値を識別する値である。
【０１１６】
例えば、この開始アドレスカウンタ（ａｎ）は、ハッシュ関数カウンタ（ｈｎ）が「１」の場合には、式７が関連付けられたハッシュ値リスト２７２の８つのハッシュ値を識別するための「０乃至７」の値である。また、この開始アドレスカウンタ（ａｎ）は、例えば、ハッシュ関数カウンタ（ｈｎ）が「５」の場合には、式３が関連付けられたハッシュ値リスト２７６の８つのハッシュ値を識別するための「０乃至７」の値である。
【０１１７】
そして、候補ハッシュ値生成部２３０により、ハッシュ関数カウンタ（ｈｎ）が指し示すハッシュ関数を用いて、開始アドレスカウンタ（ａｎ）が指し示す開始アドレスを関数入力値としてハッシュ値が算出される（ステップＳ９２４）。次に、開始アドレスカウンタ（ａｎ）に「１」が加算される（ステップＳ９２５）。
【０１１８】
続いて、開始アドレスカウンタ（ａｎ）が開始アドレスリストの開始アドレスの総数であるか否かが判断される（ステップＳ９２６）。そして、開始アドレスカウンタ（ａｎ）が開始アドレスリストの開始アドレスの総数でないと判断された場合には、ステップＳ９２４に戻る。これにより、ハッシュ関数カウンタ（ｈｎ）が指し示すハッシュ関数を用いてまだ算出されていないハッシュ値が算出される。
【０１１９】
一方、開始アドレスカウンタ（ａｎ）が開始アドレスリストの開始アドレスの総数であると判断された場合には、ハッシュ関数カウンタ（ｈｎ）に「１」が加算される（ステップＳ９２７）。
【０１２０】
続いて、ハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数であるか否かが判断される（ステップＳ９２８）。そして、ハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数でないと判断された場合には、ステップＳ９２３に戻る。これにより、まだハッシュ値が算出されていないハッシュ関数を用いてハッシュ関数が算出される。なお、ステップＳ９２２乃至Ｓ９２８は、特許請求の範囲に記載の候補値生成手順の一例である。
【０１２１】
一方、ハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数であると判断された場合には、ステップＳ９２９に進む。
【０１２２】
図９は、本発明の第１の実施の形態におけるハッシュ関数決定部２００によるハッシュ関数決定処理（ステップＳ９２０）の処理手順例の後半を示すフローチャートである。
【０１２３】
まず、図８のステップＳ９２８においてハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数であると判断された場合には、選択ハッシュ関数カウンタ（ｈ）が「０」に初期化される（ステップＳ９２９）。
【０１２４】
続いて、ハッシュ値ビット幅サイズ（ｗｓ）がハッシュ関数カウンタ（０）のハッシュ関数により生成されるハッシュ値のビット幅に変更される（ステップＳ９３１）。すなわち、ハッシュ値ビット幅サイズ（ｗｓ）には開始アドレスのビット幅の６４ビットが設定される。
【０１２５】
そして、ハッシュ関数カウンタ（ｈｎ）が「１」に変更される（ステップＳ９３２）。続いて、ユニークハッシュ値リスト判別部２５１により、ハッシュ関数カウンタ（ｈｎ）の指し示すハッシュ関数に対応するハッシュ値リストのハッシュ値が全て互いに異なるか否かが判別される（ステップＳ９３３）。そして、ハッシュ関数（ｈｎ）の指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値が全て互いに異なっていないと判別された場合には、ステップＳ９３７に進む。
【０１２６】
一方、ハッシュ関数カウンタ（ｈｎ）の指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値が全て互いに異なっていると判別された場合には、ステップＳ９３４に進む。ステップＳ９３４では、確定ハッシュ関数選択部２５２により、ハッシュ関数カウンタ（ｈｎ）の指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値のビット幅が、ハッシュ値ビット幅サイズ（ｗｓ）より小さい値であるか否かが判断される。そして、ハッシュ関数（ｈｎ）の指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値のビット幅がｗｓより小さい値ではないと判断された場合には、ステップＳ９３７に進む。
【０１２７】
一方、ハッシュ関数カウンタ（ｈｎ）の指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値のビット幅がハッシュ値ビット幅サイズ（ｗｓ）より小さい値であると判断された場合には、ステップＳ９３５に進む。ステップＳ９３５では、選択ハッシュ関数番号（ｈ）がハッシュ関数カウンタ（ｈｎ）の値に変更される。
【０１２８】
続いて、ハッシュ値ビット幅サイズ（ｗｓ）が、ハッシュ関数カウンタ（ｈｎ）が指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値のビット幅に変更される（ステップＳ９３６）。
【０１２９】
そして、ハッシュ関数カウンタ（ｈｎ）に「１」が加算される（ステップＳ９３７）。次に、ハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数であるか否かが判断される（ステップＳ９３８）。そして、ハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数でないと判断された場合には、ステップＳ９３３に戻る。
【０１３０】
一方、ハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数であると判断された場合には、選択ハッシュ関数（ｈ）が指し示すハッシュ関数がハッシュ関数決定部２００の決定したハッシュ関数として出力される（ステップＳ９３９）。なお、ステップＳ９２９乃至Ｓ９３９は、特許請求の範囲に記載の区間識別値生成関数出力手順の一例である。
【０１３１】
このように、本発明の第１の実施の形態では、全て互いに異なるハッシュ値であってビット幅が最も狭くなるハッシュ値を生成するハッシュ関数を複数のハッシュ関数から選択して、プログラムに埋め込むことができる。
【０１３２】
なお、ここでは、ハッシュ関数カウンタ（ｈｎ）の指し示すハッシュ関数に関連付けられたハッシュ値リストのハッシュ値のビット幅に基づいてハッシュ関数を選択したが、本発明はこれに限定されるものではない。例えば、ハッシュ値リストのハッシュ値のビット幅を総和した値に基づいてハッシュ関数を選択する場合なども考えられる。
【０１３３】
＜２．第２の実施の形態＞
［本発明の第２の実施の形態におけるデータ処理装置３００の構成例］
図１０は、本発明の第２の実施の形態におけるデータ処理装置３００の構成例を示すブロック図である。このデータ処理装置３００は、バス３５０を介して主記憶部３６０と相互に接続されている。また、ここでは、データ処理装置３００が処理を実行する命令区間は関数またはループであることを想定する。さらに、ここでは、データ処理装置３００は、本発明の第１の実施の形態におけるコンパイル処理装置１００により生成されたオブジェクトプログラムを実行することとする。
【０１３４】
データ処理装置３００は、プログラムにおける各処理を実行するものである。このデータ処理装置３００は、例えば、一般的なコンピュータにおいてはＣＰＵ（Central Processing Unit）により実現される。このデータ処理装置３００は、一次キャッシュ３１０と、プロセッサコア４００と、ハッシュ変換部５００と、履歴管理部６００とを備える。
【０１３５】
一次キャッシュ３１０は、プロセッサコア４００がバス３５０を介して扱う情報を一時的に保持するものである。この一次キャッシュ３１０は、命令キャッシュ３１１およびデータキャッシュ３１２を備える。
【０１３６】
命令キャッシュ３１１は、プロセッサコア４００において実行される命令を一時的に保持するものである。この命令キャッシュ３１１は、プロセッサコア４００が頻繁に実行する命令を一時的に保持することによって、プロセッサコア４００から主記憶部３６０へのアクセスを軽減させ、プロセッサコア４００におけるデータの入力待ち時間を短縮させることができる。この命令キャッシュ３１１は、例えば、主記憶部３６０から供給された再利用命令およびハッシュ関数を指定する命令をプロセッサコア４００に供給する。
【０１３７】
データキャッシュ３１２は、プロセッサコア４００の入力データおよび出力データを一時的に保持するものである。このデータキャッシュ３１２は、使用頻度の高いプロセッサコア４００の入力データを一時的に保持することによりプロセッサコア４００から主記憶部３６０へのアクセスを軽減させて、プロセッサコア４００におけるデータの入力待ち時間を軽減させる。このデータキャッシュ３１２は、例えば、主記憶部３６０から供給された関数またはループの入力値および開始アドレスをプロセッサコア４００に出力する。また、このデータキャッシュ３１２は、例えば、主記憶部３６０から供給されたハッシュ関数に関する情報をプロセッサコア４００に出力する。
【０１３８】
プロセッサコア４００は、プログラムの命令に従って演算を実行するものである。このプロセッサコア４００は、例えば、ＭＩＰＳ（Microprocessor without Interlocked Pipeline Stages）プロセッサにより実現される。プロセッサコア４００は、例えば、データキャッシュ３１２から供給される関数またはループの入力値および開始アドレスに基づいて、命令キャッシュ３１１から入力される関数またはループの区間における命令を実行し、その実行の結果を実行結果として出力する。
【０１３９】
このプロセッサコア４００は、入力される命令が再利用区間を指定する再利用命令である場合において履歴管理部６００から実行結果が供給されないときには、この命令を実行した結果である実行結果をデータキャッシュ３１２および履歴管理部６００に出力する。また、このプロセッサコア４００は、再利用命令を実行した際には、再利用命令が指定する再利用区間の開始アドレスをハッシュ変換部５００に供給する。
【０１４０】
さらに、プロセッサコア４００は、入力される命令が再利用区間を指定する再利用命令である場合において履歴管理部６００から実行結果が供給されたときには、再利用区間における処理を中止して、この再利用区間を呼び出したルーチンに戻って実行を継続する。
【０１４１】
ハッシュ変換部５００は、再利用区間の開始アドレスのビット幅より狭いビット幅で再利用区間を識別するハッシュ値に開始アドレスを変換するものである。このハッシュ変換部５００は、プログラムの命令のうちハッシュ関数を指定する命令に基づいてハッシュ関数を保持する。このハッシュ変換部５００は、その保持しているハッシュ関数を用いて、プロセッサコア４００から供給された関数またはループの開始アドレスからハッシュ値を生成する。このハッシュ変換部５００は、その生成したハッシュ値を履歴管理部６００に供給する。
【０１４２】
履歴管理部６００は、再利用区間の実行結果を保持して管理するものである。この履歴管理部６００は、プロセッサコア４００から供給された再利用区間の入力値および実行結果と、ハッシュ変換部５００から供給されたハッシュ値とを実行履歴として保持する。また、この履歴管理部６００は、ハッシュ値と関数またはループの入力値とが供給された場合には、このハッシュ値と入力値とが含まれる実行履歴を検索する。
【０１４３】
バス３５０は、データ処理装置３００の各部と主記憶部３６０との間を相互に接続するバスである。
【０１４４】
主記憶部３６０は、データ処理装置３００が動作するために必要なデータを保持するものである。この主記憶部３６０は、データ処理装置３００に処理を実行させるためのプログラムを記憶する。この主記憶部３６０は、例えば、ＲＡＭ（Random Access Memory）などが考えられる。この主記憶部３６０は、記憶しているデータを、バス３５０を介してデータ処理装置３００に出力する。
【０１４５】
［本発明の第２の実施の形態におけるプロセッサコア４００とハッシュ変換部５００と履歴管理部６００との構成例］
図１１は、本発明の第２の実施の形態におけるプロセッサコア４００とハッシュ変換部５００と履歴管理部６００との構成例を示すブロック図である。ここでは、プロセッサコア４００とハッシュ変換部５００と履歴管理部６００とが示されている。また、ここでは、プロセッサコア４００とハッシュ変換部５００と履歴管理部６００との機能は、図１０と同様のものであるため、同一の符号を付してここでの詳細な説明を省略する。
【０１４６】
プロセッサコア４００は、フェッチ部４１０と、命令デコーダ４２０と、実行部４３０と、レジスタファイル４４０とを備える。
【０１４７】
フェッチ部４１０は、命令キャッシュ３１１または主記憶部３６０からの命令を読み出すものである。このフェッチ部４１０は、その読み出した命令を一時的に保持して、その保持されている命令のうち、実行部４３０に実行させるための命令を命令デコーダ４２０に供給する。このフェッチ部４１０は、例えば、一時的に保持している命令のうち、実行部４３０において実行される再利用命令を命令デコーダ４２０に供給する。このフェッチ部４１０は、例えば、主記憶部３６０に記憶された再利用命令を命令デコーダ４２０に供給する。
【０１４８】
命令デコーダ４２０は、フェッチ部４１０から供給された命令を解読（デコード）することによって、プロセッサコア４００における構成部位を制御する制御信号を生成するものである。この命令デコーダ４２０は、例えば、命令を解読することによって実行部４３０およびレジスタファイル４４０を制御する制御信号を生成して、その生成された制御信号を実行部４３０およびレジスタファイル４４０に供給する。
【０１４９】
この命令デコーダ４２０は、フェッチ部４１０から再利用命令が供給された場合には、その再利用命令を解読することによって、実行部４３０およびレジスタファイル４４０の各々を制御する制御信号を実行部４３０およびレジスタファイル４４０に供給する。
【０１５０】
実行部４３０は、命令デコーダ４２０から供給された制御信号に基づいて、命令デコーダ４２０において解読した命令を実行するものである。この実行部４３０は、命令デコーダ４２０においてハッシュ関数を指定する命令をデコードした場合には、レジスタファイル４４０から取得したハッシュ関数を、信号線４０７を介してハッシュ変換部５００に出力する。
【０１５１】
また、この実行部４３０は、命令デコーダ４２０が再利用命令をデコードした場合には、再利用命令が指定する再利用区間の処理を開始する。そして、この再利用区間の処理の開始とともに、実行部４３０は、レジスタファイル４４０から取得した再利用区間の開始アドレスを、信号線４０８を介してハッシュ変換部５００に出力する。そして、実行部４３０は、レジスタファイル４４０から供給される再利用区間の入力値に基づいて再利用区間における処理を実行するとともに、再利用区間の入力値を、信号線４０９を介して履歴管理部６００に出力する。
【０１５２】
なお、実行部４３０は、履歴管理部６００から再利用区間の実行結果が供給された場合には、再利用区間の処理を中止するとともに、その実行結果を履歴管理部６００から供給された旨を通知する信号をフェッチ部４１０に供給する。この時、実行部４３０は、実行結果をレジスタファイル４４０に出力する。
【０１５３】
一方、実行部４３０は、履歴管理部６００から再利用区間の実行結果が供給されない場合には、再利用区間の処理を最後まで実行して、その実行結果をレジスタファイル４４０に出力するとともに信号線４０９を介して履歴管理部６００に出力する。
【０１５４】
レジスタファイル４４０は、データキャッシュ３１２から供給されたデータおよび実行部４３０から供給された実行結果を一時的に保持するものである。このレジスタファイル４４０は、例えば、命令デコーダ４２０から再利用命令に基づく制御信号が供給された場合には、再利用区間の入力値を実行部４３０に供給する。
【０１５５】
ハッシュ変換部５００は、再利用区間の開始アドレスのビット幅より狭いビット幅で再利用区間を識別するハッシュ値に開始アドレスを変換させるものである。このハッシュ変換部５００は、確定ハッシュ関数保持部５１０および確定ハッシュ値生成部５２０を備える。
【０１５６】
確定ハッシュ関数保持部５１０は、実行部４３０から供給されたハッシュ関数を保持するものである。すなわち、この確定ハッシュ関数保持部５１０は、図３において示した確定ハッシュ関数選択部２５２が確定したハッシュ関数を保持する。この確定ハッシュ関数保持部５１０は、実行部４３０から信号線４０７を介して供給されたハッシュ関数を保持し、その保持したハッシュ関数を確定ハッシュ値生成部５２０に供給する。
【０１５７】
確定ハッシュ値生成部５２０は、確定ハッシュ関数保持部５１０から供給されたハッシュ関数を用いて、実行部４３０から供給された開始アドレスからハッシュ値を生成するものである。すなわち、この確定ハッシュ値生成部５２０は、図３において示した確定ハッシュ関数選択部２５２が確定したハッシュ関数を用いて、実行部４３０から供給された開始アドレスからハッシュ値を生成する。この確定ハッシュ値生成部５２０は、信号線４０８を介して関数あるいはループの開始アドレスが供給された場合には、確定ハッシュ関数保持部５１０が保持しているハッシュ関数を用いてハッシュ値を生成する。この確定ハッシュ値生成部５２０は、その生成されたハッシュ値を信号線５０９を介して履歴対象データ保持部６１０に供給する。なお、確定ハッシュ値生成部５２０は、特許請求の範囲に記載の区間識別値生成部の一例である。なお、確定ハッシュ値生成部５２０が生成するハッシュ値は、特許請求の範囲に記載の区間識別値の一例である。また、確定ハッシュ値生成部５２０が用いるハッシュ関数は、特許請求の範囲に記載の区間識別値生成関数の一例である。
【０１５８】
履歴管理部６００は、再利用区間の実行結果を保持して管理するものであり、履歴対象データ保持部６１０と、履歴検索部６２０と、履歴メモリ６３０と、履歴登録部６４０とを備える。
【０１５９】
履歴対象データ保持部６１０は、実行部４３０および確定ハッシュ値生成部５２０から供給されたデータを一時的に保持するものである。この履歴対象データ保持部６１０は、実行部４３０から入力値が供給され、かつ、確定ハッシュ値生成部５２０からハッシュ値が供給された際には、これらを検索要求として履歴検索部６２０に供給する。この履歴対象データ保持部６１０は、例えば、実行部４３０において関数の再利用区間が実行された場合には、実行部４３０から供給された関数の入力値と、確定ハッシュ値生成部５２０から供給されたハッシュ値とを検索要求として履歴検索部６２０に供給する。また、履歴対象データ保持部６１０は、実行部４３０においてループの再利用区間が実行された場合には、実行部４３０からの入力値およびループカウンタ値と、確定ハッシュ値生成部５２０からのハッシュ値とを検索要求として履歴検索部６２０に供給する。ここで、ループカウンタ値とは、そのループ区間の何回目の実行による実行結果であるのかを示す値である。
【０１６０】
また、この履歴対象データ保持部６１０は、実行部４３０からは入力値および実行結果が供給され、確定ハッシュ値生成部５２０からはハッシュ値が供給された場合には、実行履歴を登録する条件を満たすため、これらを実行履歴として履歴登録部６４０に供給する。例えば、履歴対象データ保持部６１０は、実行部４３０において関数の再利用区間が実行された場合には、実行部４３０からの入力値および実行結果と、確定ハッシュ値生成部５２０からのハッシュ値とを実行履歴として履歴登録部６４０に供給する。また、履歴対象データ保持部６１０は、実行部４３０においてループの再利用区間が実行された場合には、実行部４３０からの入力値、実行結果、ループカウンタ値と、確定ハッシュ値生成部５２０からのハッシュ値とを実行履歴として履歴登録部６４０に供給する。
【０１６１】
履歴検索部６２０は、履歴対象データ保持部６１０から供給された検索要求に基づいて実行履歴を検索するものである。この履歴検索部６２０は、検索要求入力部６２１および実行結果出力部６２２を備える。
【０１６２】
検索要求入力部６２１は、履歴対象データ保持部６１０から供給された検索要求に基づいて履歴メモリ６３０から実行履歴を検索するものである。この検索要求入力部６２１は、例えば、関数の再利用区間を指定する命令が命令デコーダ４２０において解読された場合には、この命令により指定された関数の開始アドレスから生成されたハッシュ値と、この関数の入力値とを履歴メモリ６３０に供給する。また、この検索要求入力部６２１は、ループの再利用区間を指定する命令が命令デコーダ４２０において解読された場合には、この指定されたループの開始アドレスから生成されたハッシュ値と、入力値と、ループカウンタ値とを履歴メモリ６３０に供給する。
【０１６３】
実行結果出力部６２２は、履歴メモリ６３０において実行履歴が検索された場合に実行結果を履歴メモリ６３０から抽出して、その抽出した実行結果を実行部４３０に出力するものである。この実行結果出力部６２２は、その抽出した実行結果を、信号線６０９を介して実行部４３０に供給する。
【０１６４】
履歴メモリ６３０は、履歴登録部６４０から供給された実行履歴を保持するものである。この履歴メモリ６３０は、例えば、履歴検索部６２０から検索要求が供給された場合において、この検索要求と一致する実行履歴を保持しているときは、この実行履歴の実行結果を実行結果出力部６２２に供給する。さらに、この履歴メモリ６３０は、履歴登録部６４０から実行履歴が供給された場合には、この実行履歴を保持する。この履歴メモリ６３０は、例えば、連想メモリ（ＣＡＭ：Content Addressable Memory）により実現される。
【０１６５】
履歴登録部６４０は、履歴対象データ保持部６１０から供給された実行履歴を履歴メモリ６３０に保持させるためのデータ構造に変換して、その変換された実行履歴を履歴メモリ６３０に登録するものである。この履歴登録部６４０は、例えば、履歴検索部６２０により関数の実行履歴が検索されない場合には、その関数の開始アドレスから生成されたハッシュ値と、入力値と、実行結果とを実行履歴として履歴メモリ６３０に登録する。また、この履歴登録部６４０は、例えば、履歴検索部６２０によりループの実行履歴が検索されない場合には、ループの開始アドレスから生成されたハッシュ値と、入力値と、実行結果と、ループカウンタ値とを実行履歴として履歴メモリ６３０に登録する。
【０１６６】
このように、本発明の第２の実施の形態では、データ処理装置３００にハッシュ変換部５００を設けることによって、本発明の第１の実施の形態の装置によりハッシュ関数が埋め込まれたプログラムを実行して開始アドレスをハッシュ値に変換することができる。これにより、開始アドレスのビット幅より狭いビット幅で再利用区間を識別するハッシュ値を開始アドレスの代わりに履歴メモリ６３０に保持させることができる。
【０１６７】
すなわち、従来の技術では関数の実行履歴として開始アドレス、入力値および実行結果を履歴メモリに保持させるが、本発明の第２の実施の形態では開始アドレスのビット幅より狭いビット幅のハッシュ値、入力値および実行結果を履歴メモリ６３０に保持させる。このように、開始アドレスのビット幅より狭いビット幅のハッシュ値を開始アドレスの代わりに履歴メモリ６３０に保持させることによって、履歴メモリ６３０に保持される実行履歴の量を増加させることができる。
【０１６８】
なお、ここでは、実行部４３０から供給されたハッシュ関数を確定ハッシュ関数保持部５１０に保持させる例について説明したが、本発明はこれに限定されるものではない。例えば、図３において示した本発明の第１の実施の形態における候補ハッシュ関数保持部２２０と同一の複数のハッシュ関数を事前に確定ハッシュ関数保持部５１０に保持させるようにしてもよい。この例において、本発明の第１の実施の形態におけるコンパイル処理装置１００により、図３において説明したハッシュ関数を指し示す識別子をハッシュ関数の代わりにプログラムに埋め込む。そして、本発明の第２の実施の形態におけるデータ処理装置３００によりその識別子に基づいてハッシュ関数を特定する。
【０１６９】
この場合において、実行部４３０は、命令デコーダ４２０が識別子を指定する命令をデコードした際に、識別子をハッシュ変換部５００に出力する。そして、確定ハッシュ関数保持部５１０は、実行部４３０から供給された識別子に対応するハッシュ関数を保持している複数のハッシュ関数から選択して、その選択したハッシュ関数を確定ハッシュ値生成部５２０に供給する。
【０１７０】
これにより、ハッシュ関数を識別する識別子が埋め込まれたプログラムに基づいて、開始アドレスをハッシュ値に変換することができる。
【０１７１】
［履歴メモリ６３０のデータ構造例］
図１２は、本発明の第２の実施の形態における履歴メモリ６３０のデータ構造の一例を示す概念図である。ここでは、履歴メモリ６３０により、ハッシュ値ごとに保持された実行履歴のうち、１つのハッシュ値における実行履歴を木構造により保持する構成が示されている。この例では、引数がｎ個であり、かつ、実行結果である出力をｍ個の格納先に返す関数を想定している。
【０１７２】
この例では、木構造における関数ルート６５０と、第１の引数ノード６６１および６６２と、第ｎの引数ノード６７１乃至６７４と、第１の出力ノード６８１乃至６８４と、第ｍの出力ノード６９１乃至６９４とが示されている。
【０１７３】
関数ルート６５０には、ハッシュ値と、第１の引数ノード６６１を指し示すポインタとが示されている。
【０１７４】
第１および第ｎの引数ノード６６１、６６２および６７１乃至６７４には、履歴メモリ６３０に保持されている実行履歴における引数の入力値として、引数の値を示す入力値と、その引数の型と、その引数の格納場所を示す種類とが示されている。ここにいう格納場所とは、レジスタ番号または主記憶部３６０のメモリアドレスのことをいう。
【０１７５】
さらに、第１および第ｎの引数ノード６６１、６６２および６７１乃至６７４には、比較対象の入力値が互いに一致した場合に次の引数の引数ノードを指し示す右ポインタと、不一致の場合に同一の引数における他の引数ノードを指し示す下ポインタとが示されている。また、第ｎの引数ノード６７１乃至６７４の各々は、第１および第ｍの出力ノード６８１乃至６８４および６９１乃至６９４にそれぞれ連結されている。
【０１７６】
第１および第ｍの出力ノード６８１乃至６８４および６９１乃至６９４には、履歴メモリ６３０に保持されている実行履歴における実行結果として、実行結果の値を示す出力値と、その実行結果の格納場所を示す種類と、その実行結果の型とが示されている。さらに、第１の出力ノード６８１乃至６８４には、次の出力ノードを指し示す右ポインタが示されている。すなわち、第１および第ｍの出力ノード６８１乃至６８４および６９１乃至６９４は、連結リストを構成している。また、第ｍの出力ノード６９１乃至６９４には、出力ノードの終端を表わすヌルが示されている。
【０１７７】
このような木構造において、関数ルート６５０に示されたハッシュ値と一致するハッシュ値が履歴検索部６２０から入力されると、関数ルート６５０のポインタによって指し示された第１の引数ノード６６１において入力値の比較処理が実行される。ここにいう入力値の比較処理とは、第１の引数ノード６６１に示された入力値、種類および型である入力値と、履歴検索部６２０からの入力値とを比較することである。
【０１７８】
このとき、例えば、第１の引数ノード６６１に示された入力値と履歴検索部６２０から+の入力値とが一致した場合には、第１の引数ノード６６１の右ポインタにより指し示された次の引数ノードにおいて入力値の比較処理が実行される。一方、第１の引数ノード６６１に示された入力値と、履歴検索部６２０からの入力値とが一致しない場合には、第１の引数ノード６６１の下ポインタにより指し示された第１の引数ノード６６２において入力値の比較処理が実行される。
【０１７９】
このようにして、各引数ノードにおける比較処理による結果に基づいて右または下ポインタの指し示す引数ノードが選択され、その選択された引数ノードにおいて入力値の比較処理が順次実行される。そして、例えば、第ｎの引数ノード６７１に示された入力値と履歴検索部６２０からの入力値とが互いに一致した場合には、第ｎの引数ノード６７１の右ポインタの指し示す第１の出力ノード６８１の実行結果が履歴検索部６２０に出力される。そして、最後に、第ｍ番の出力ノード６９１の実行結果が履歴検索部６２０に出力される。
【０１８０】
このように、履歴メモリ６３０をハッシュ値ごとに木構造により構成することによって、同じ引数の入力値を重複して保持させる必要が無いため、記憶領域を節約することができる。また、ハッシュ値ごとにデータ構造を分けることによって、検索速度の低下を抑制することができる。
【０１８１】
［本発明の第２の実施の形態におけるデータ処理装置３００の動作例］
次に、本発明の第２の実施の形態におけるデータ処理装置３００の処理について図面を参照して説明する。
【０１８２】
図１３は、本発明の第２の実施の形態におけるデータ処理装置３００による命令処理方法の処理手順例を示すフローチャートである。このフローチャートは、命令デコーダ４２０によりデコードされる命令毎の処理例を説明するものであり、命令デコーダ４２０によりデコードされる命令の実行の終了をフローチャートの終了とする。
【０１８３】
まず、フェッチ部４１０およびレジスタファイル４４０に、命令デコーダ４２０によって解読（デコード）される命令およびその命令に従って実行部４３０により実行される値が読み出される（ステップＳ９４１）。次に、命令デコーダ４２０により、フェッチ部４１０から供給された命令がデコードされる（ステップＳ９４２）。
【０１８４】
続いて、実行部４３０により、デコードした命令がハッシュ関数指定命令か否かが判断される（ステップＳ９４３）。そして、デコードした命令がハッシュ関数指定命令であると判断された場合には、レジスタファイル４４０から供給されるハッシュ関数が信号線４０７を介して確定ハッシュ関数保持部５１０に登録される（ステップＳ９４４）。これにより、ハッシュ関数指定命令の実行は終了する。
【０１８５】
一方、デコードした命令がハッシュ関数指定命令でないと判断された場合には、デコードした命令が再利用命令か否かが判断される（ステップＳ９４５）。そして、デコードした命令が再利用命令でないと判断された場合には、実行部４３０により、レジスタファイル４４０から供給される入力値に基づいてその再利用区間が実行されることによって、実行結果が出力されて（ステップＳ９４６）、ステップＳ９５４に進む。
【０１８６】
一方、ステップＳ９４５の処理において、命令が再利用命令であると判断された場合には、確定ハッシュ値生成部５２０により、再利用区間の開始アドレスからハッシュ値が算出される（ステップＳ９４７）。続いて、検索要求入力部６２１により、ハッシュ値および入力値を用いて履歴メモリ６３０に実行履歴があるか否かが判断される（ステップＳ９４８）。このとき、ループが再利用区間である場合には、ハッシュ値および入力値に加えてループカウンタ値も用いて履歴メモリ６３０に実行履歴があるか否か探索される。
【０１８７】
そして、実行履歴が履歴メモリ６３０にないと判断された場合には、実行部４３０により、レジスタファイル４４０から供給される入力値に基づいてその再利用区間が実行されることによって、実行結果が出力される（ステップＳ９４９）。そして、履歴登録部６４０により、実行履歴が履歴メモリ６３０に登録される（ステップＳ９５１）。これにより、履歴メモリ６３０に実行履歴が登録される。そして、ステップＳ９５４に進む。
【０１８８】
一方、実行履歴が履歴メモリ６３０にあると判断された場合には、実行結果出力部６２２により、実行結果が出力される（ステップＳ９５２）。これにより、実行している再利用区間の実行結果が履歴メモリ６３０から出力される。続いて、実行部４３０は、実行結果が出力された再利用区間の実行を中止させる（ステップＳ９５３）。そして、ステップＳ９５４に進む。
【０１８９】
そして、ステップＳ９４６、Ｓ９５１およびＳ９５３の処理の後に、実行結果がレジスタファイル４４０に書き戻される（ステップＳ９５４）。これにより、デコードされた命令の実行は終了する。
【０１９０】
このように、本発明の第２の実施の形態では、ハッシュ変換部５００を設けることによって、ハッシュ値と入力値と実行結果とを実行履歴として履歴メモリ６３０に保持させることができる。
【０１９１】
＜３．第３の実施の形態＞
［本発明の第３の実施の形態におけるコンパイル処理装置１００の構成例］
図１４は、本発明の第３の実施の形態におけるコンパイル処理装置１００の構成例を示すブロック図である。このコンパイル処理装置１００は、図１において示したコンパイル処理装置１００のハッシュ関数決定部２００の代わりにハッシュ値付再利用命令生成部１７０を備えている。ここでは、ハッシュ値付再利用命令生成部１７０以外の構成は、図１と同様のものであるため、図１と同符号を付してここでの各部の構成の詳細な説明を省略する。
【０１９２】
ハッシュ値付再利用命令生成部１７０は、再利用区間の開始アドレスのビット幅より狭いビット幅で再利用区間を識別するハッシュ値を含む再利用命令であるハッシュ値付再利用命令を生成するものである。このハッシュ値付再利用命令生成部１７０は、ハッシュ値決定部７００およびハッシュ値付加部１７２を備える。なお、ハッシュ値付再利用命令は、特許請求の範囲に記載の区間識別値付命令の一例である。
【０１９３】
ハッシュ値決定部７００は、再利用区間の開始アドレスのビット幅より狭いビット幅で再利用区間を識別するハッシュ値を決定するものである。このハッシュ値決定部７００は、例えば、再利用区間の開始アドレスの所定の順序に従って付与された番号を関数入力値として、複数のハッシュ関数を用いてハッシュ関数ごとにハッシュ値を生成する。そして、このハッシュ値決定部７００は、複数のハッシュ関数のうち、値が全て互いに異なるハッシュ値であってビット幅が最も狭いハッシュ値を決定して出力する。このハッシュ値決定部７００は、その決定したハッシュ値をプログラムとともにハッシュ値付加部１７２に供給する。
【０１９４】
ハッシュ値付加部１７２は、ハッシュ値決定部７００により決定されたハッシュ値をそのハッシュ値が指し示す再利用区間を呼び出す再利用命令に付加してハッシュ値付再利用命令を生成するものである。このハッシュ値付加部１７２は、その生成したハッシュ値付再利用命令が含まれるプログラムを機械語プログラム生成部１４０に供給する。なお、ハッシュ値付加部１７２は、特許請求の範囲に記載の命令変換部の一例である。
【０１９５】
機械語プログラム生成部１４０は、ハッシュ値付加部１７２から供給されたハッシュ値付再利用命令が含まれるプログラムに基づいて、機械語のプログラムであるオブジェクトプログラムを生成するものである。また、この機械語プログラム生成部１４０は、オブジェクトプログラムを生成する際に、ハッシュ値のビット幅を指定する値を指定する命令をオブジェクトプログラムに埋め込む。
【０１９６】
このように、本発明の第３の実施の形態におけるコンパイル処理装置１００では、まず、関数の実行結果が再利用される度合いに応じて関数の呼出し命令を再利用命令に変換することによって、再利用される関数と再利用されない関数とが区別できるようにする。そして、本発明の第３の実施の形態におけるコンパイル処理装置１００では、再利用区間を識別するためのハッシュ値を決定してハッシュ値付再利用命令を生成することによって、そのハッシュ値付再利用命令が含まれるプログラムを生成することができる。
【０１９７】
［本発明の第３の実施の形態におけるハッシュ値決定部７００の構成例］
図１５は、本発明の第３の実施の形態におけるハッシュ値決定部７００の構成例を示すブロック図である。このハッシュ値決定部７００は、開始アドレス取得部７１０と、候補ハッシュ関数保持部７２０と、候補ハッシュ値生成部７３０と、ハッシュ値テーブル７４０と、ハッシュ値出力部７５０とを備える。
【０１９８】
開始アドレス取得部７１０は、図３において示した開始アドレス取得部２１０と同様に、再利用命令変換部１２４からの再利用命令を含むプログラムから再利用区間の開始アドレスを取得するものである。この開始アドレス取得部７１０は、その取得した開始アドレスを開始アドレスリストとして保持する。また、この開始アドレス取得部７１０は、その取得した開始アドレスの取得した順序に従って付与された番号を番号リストとして保持する。この開始アドレス取得部７１０は、取得した開始アドレスあるいは付与した番号を候補ハッシュ値生成部７３０に供給する。
【０１９９】
候補ハッシュ関数保持部７２０は、開始アドレスあるいは番号をハッシュ値に変換するための複数のハッシュ関数を保持するものである。すなわち、この候補ハッシュ関数保持部７２０は、ハッシュ値決定部７００が決定するハッシュ値の候補となるハッシュ値を生成するためのハッシュ関数の候補となるハッシュ関数を保持する。この候補ハッシュ関数保持部７２０は、予め定められたハッシュ関数を保持する。
【０２００】
この候補ハッシュ関数保持部７２０は、保持している複数のハッシュ関数を候補ハッシュ値生成部７３０に供給する。なお、候補ハッシュ関数保持部７２０から供給されるハッシュ関数は、特許請求の範囲に記載の候補関数の一例である。
【０２０１】
候補ハッシュ値生成部７３０は、開始アドレス取得部７１０から供給された開始アドレスあるいは番号を関数入力値とし、その関数入力値を候補ハッシュ関数保持部７２０から供給されたハッシュ関数の入力としてハッシュ値を生成するものである。すなわち、この候補ハッシュ値生成部７３０は、ハッシュ値決定部７００が決定するハッシュ値の候補となるハッシュ値を生成する。
【０２０２】
この候補ハッシュ値生成部７３０は、例えば、開始アドレス取得部７１０から番号が供給された場合には、候補ハッシュ関数保持部７２０から供給されたハッシュ関数を用いてその番号からハッシュ値を生成する。また、この候補ハッシュ値生成部７３０は、例えば、開始アドレス取得部７１０から開始アドレスが供給された場合には、候補ハッシュ関数保持部７２０から供給されたハッシュ関数を用いてその開始アドレスからハッシュ値を生成する。
【０２０３】
この候補ハッシュ値生成部７３０は、その生成したハッシュ値をハッシュ値テーブル７４０に供給する。なお、候補ハッシュ値生成部７３０は、特許請求の範囲に記載の候補値生成部の一例である。なお、候補ハッシュ値生成部７３０から供給されるハッシュ値は、特許請求の範囲に記載の候補値の一例である。
【０２０４】
ハッシュ値テーブル７４０は、候補ハッシュ値生成部７３０から供給されたハッシュ値を保持するものである。このハッシュ値テーブル７４０は、ハッシュ値をそのハッシュ値を生成したハッシュ関数ごとにハッシュ値リストとして保持する。また、このハッシュ値テーブル７４０は、保持したハッシュ値リストをハッシュ値出力部７５０に供給する。なお、ハッシュ値テーブル７４０は、特許請求の範囲に記載の候補値テーブルの一例である。なお、ハッシュ値リストは、特許請求の範囲に記載の候補値リストの一例である。
【０２０５】
ハッシュ値出力部７５０は、ハッシュ値が全て互いに異なるハッシュ値リストを抽出し、この抽出されたハッシュ値リストのうちハッシュ値のビット幅が最も狭くなるハッシュ値リストのハッシュ値を出力するものである。このハッシュ値出力部７５０は、ユニークハッシュ値リスト判別部７５１および確定ハッシュ値選択部７５２を備える。なお、ハッシュ値出力部７５０は、特許請求の範囲に記載の区間識別値出力部の一例である。なお、ハッシュ値出力部７５０が出力するハッシュ値は、特許請求の範囲に記載の区間識別値の一例である。
【０２０６】
ユニークハッシュ値リスト判別部７５１は、図３において示したユニークハッシュ値リスト判別部２５１と同様に、ハッシュ値テーブル７４０に保持されているハッシュ値リストのうちハッシュ値が全て互いに異なるハッシュ値リストを判別するものである。このユニークハッシュ値リスト判別部７５１は、その判別したハッシュ値リストを確定ハッシュ値選択部７５２に供給する。
【０２０７】
確定ハッシュ値選択部７５２は、ユニークハッシュ値リスト判別部７５１から供給されたハッシュ値リストのうちハッシュ値のビット幅が最も狭くなるハッシュ値リストを選択して、その選択したハッシュ値リストのハッシュ値を出力するものである。すなわち、この確定ハッシュ値選択部７５２は、ハッシュ値決定部７００が決定するハッシュ値の候補のハッシュ値からハッシュ値を確定し、その確定したハッシュ値をハッシュ値決定部７００が決定したハッシュ値として出力する。
【０２０８】
この確定ハッシュ値選択部７５２は、ユニークハッシュ値リスト判別部７５１から供給されたハッシュ値が全て互いに異なるハッシュ値リストのうちハッシュ値のビット幅が最も狭いハッシュ値リストを一つ検出する。そして、この確定ハッシュ値選択部７５２は、その検出したハッシュ値リストのハッシュ値をハッシュ値付加部１７２に供給する。
【０２０９】
このように、本発明の第３の実施の形態では、ハッシュ値決定部７００を設けることにより、全て互いに異なるハッシュ値であってビット幅が最も狭いハッシュ値を有するハッシュ値付再利用命令を含むプログラムを生成することができる。
【０２１０】
なお、ここでは、候補ハッシュ関数保持部７２０は、保持するハッシュ関数を全て候補ハッシュ値生成部７３０に供給する一例について説明したが、本発明はこれに限定されるものではない。例えば、候補ハッシュ関数保持部７２０は外部から制御できるようにすることによって、候補ハッシュ値生成部７３０に供給するハッシュ関数を制御できるようにしてもよい。また、例えば、ハッシュ値テーブル７４０から供給される番号のうち最も大きい番号に基づいて、候補ハッシュ値生成部７３０が使用するハッシュ関数を判断できるようにしてもよい。
【０２１１】
［本発明の第３の実施の形態におけるハッシュ値テーブル７４０に保持されるハッシュ値の一例］
図１６は、本発明の第３の実施の形態におけるハッシュ値テーブル７４０に保持されるハッシュ値の一例を示す概念図である。ここでは、便宜上、開始アドレス取得部７１０には、開始アドレスが取得された順序に従って付与された番号が番号リストとして保持されることを想定する。また、この番号は、ハッシュ値テーブル７４０に登録された開始アドレスに対して「１」から順に付与される値であることとする。さらに、ここでは、候補ハッシュ関数保持部７２０は、図４において説明した式３乃至式６のハッシュ関数を保持しているものとする。
【０２１２】
また、ここでは、プログラムにおける再利用区間は７個の関数（ｆｕｎｃＡ乃至ｆｕｎｃＧ）とする。なお、ここでは、開始アドレス取得部７１０は、７個の関数（ｆｕｎｃＡ乃至ｆｕｎｃＧ）をｆｕｎｃＡから順に取得してハッシュ値テーブルに供給したことを想定する。
【０２１３】
また、候補ハッシュ値生成部７３０は、ビット幅を短くするハッシュ関数のみでハッシュ値を算出する場合には、ハッシュ値テーブル７４０におけるデータ量を軽減させるために、関数入力値をそのままハッシュ値テーブル７４０に供給できることとする。すなわち、候補ハッシュ値生成部７３０は、開始アドレス取得部７１０から番号が関数入力値として供給される際には、開始アドレス取得部７１０における番号リストと同様の番号リストをハッシュ値テーブル７４０に保持させることができることとする。
さらに、この候補ハッシュ値生成部７３０は、関数入力値をそのままハッシュ値テーブル７４０に供給する場合において、ハッシュ関数の生成するハッシュ値のビット幅に関するデータをハッシュ値テーブル７４０にハッシュ値リストの代わりとして保持させることを想定する。
【０２１４】
図１６（ａ）には、ハッシュ値テーブル７４０に保持された番号リスト７７２の一例が示されている。
【０２１５】
開始アドレスリスト７７１は、ハッシュ値テーブル７４０に登録されたハッシュ値の基となった開始アドレスのリスト名が示されている。この開始アドレスリスト７７１において、行７８２にはｆｕｎｃＡに関する値が示され、行７８３にはｆｕｎｃＢに関する値が示され、行７８４にはｆｕｎｃＣに関する値が示されている。さらに、行７８５にはｆｕｎｃＤに関する値が示され、行７８６にはｆｕｎｃＥに関する値が示され、行７８７にはｆｕｎｃＦに関する値が示され、行７８８にはｆｕｎｃＧが示されていることを表している。
【０２１６】
番号リスト７７２は、候補ハッシュ値生成部７３０が関数入力値をそのままハッシュ値テーブル７４０に供給した場合において、ハッシュ値テーブル７４０に登録された番号のリストである。この番号リスト７７２は、開始アドレス（ｆｕｎｃＡ乃至ｆｕｎｃＧ）に対して付与された番号（１乃至７）が１０進数で示された値を括弧の外に表し、かつ、その番号が６４ビットの２進数で表された値を括弧の中に表している。
【０２１７】
このような番号リスト７７２をハッシュ値テーブル７４０に保持させる場合において、候補ハッシュ値生成部７３０は、ハッシュ関数の生成するハッシュ値のビット幅に関するデータをハッシュ値リストの代わりとしてハッシュ値テーブル７４０に保持させる。
【０２１８】
図１６（ｂ）には、図１６（ａ）において示した番号リスト７７２と、番号リストのビット幅を指定するデータとから想定されるハッシュ値リスト７７３乃至７７６が示されている。
【０２１９】
ハッシュ値リスト７７３には、式１のｉ（ビット幅）を「４」としたハッシュ関数である式６を用いた場合に算出されるハッシュ値のリストが示されている。このハッシュ値リスト７７３の行７８２乃至７８８には、７個の関数（ｆｕｎｃＡ乃至ｆｕｎｃＧ）の開始アドレスの取得された順序に従って付与された番号（番号リスト７７２の行７８２乃至７８８）を式６の関数入力値として算出されたハッシュ値が示されている。すなわち、ハッシュ値リスト７７３の行７８２乃至７８８には、７つの関数の開始アドレスの取得された順序に従って付与された番号（番号リスト７７２の行７８２乃至７８８）を２進数で表現したビット列の最下位ビットから４ビットの値がそれぞれ示されている。
【０２２０】
ハッシュ値リスト７７４には、式１のｉ（ビット幅）を「３」としたハッシュ関数である式５を用いた場合に算出されるハッシュ値のリストが示されている。このハッシュ値リスト７７４の行７８２乃至７８８には、７個の関数（ｆｕｎｃＡ乃至ｆｕｎｃＧ）の開始アドレスの取得された順序に従って付与された番号（番号リスト７７２の行７８２乃至７８８）を式５の関数入力値として算出されたハッシュ値が示されている。すなわち、ハッシュ値リスト７７４の行７８２乃至７８８には、７つの関数の開始アドレスの取得された順序に従って付与された番号（番号リスト７７２の行７８２乃至７８８）を２進数で表現したビット列の最下位ビットから３ビットの値がそれぞれ示されている。
【０２２１】
ハッシュ値リスト７７５には、式１のｉ（ビット幅）を「２」としたハッシュ関数である式４を用いた場合に算出されるハッシュ値のリストが示されている。このハッシュ値リスト７７５の行７８２乃至７８８には、７個の関数（ｆｕｎｃＡ乃至ｆｕｎｃＧ）の開始アドレスの取得された順序に従って付与された番号（番号リスト７７２の行７８２乃至７８８）を式４の関数入力値として算出されたハッシュ値が示されている。すなわち、ハッシュ値リスト７７５の行７８２乃至７８８には、７つの関数の開始アドレスの取得された順序に従って付与された番号（番号リスト７７２の行７８２乃至７８８）を２進数で表現したビット列の最下位ビットから２ビットの値がそれぞれ示されている。
【０２２２】
ハッシュ値リスト７７６には、式１のｉ（ビット幅）を「１」としたハッシュ関数である式３を用いた場合に算出されるハッシュ値のリストが示されている。このハッシュ値リスト７７６の行７８２乃至７８８には、７個の関数（ｆｕｎｃＡ乃至ｆｕｎｃＧ）の開始アドレスの取得された順序に従って付与された番号（番号リスト７７２の行７８２乃至７８８）を式３の関数入力値として算出されたハッシュ値が示されている。すなわち、ハッシュ値リスト７７６の行７８２乃至７８８には、７つの関数の開始アドレスの取得された順序に従って付与された番号（番号リスト７７２の行７８２乃至７８８）を２進数で表現したビット列の最下位ビットの値がそれぞれ示されている。
【０２２３】
続いて、図１６を用いて、ユニークハッシュ値リスト判別部７５１により判別されるハッシュ値リストと、確定ハッシュ値選択部７５２が選択するハッシュ値とについて説明する。
【０２２４】
まず、ユニークハッシュ値リスト判別部７５１は、この図１６（ｂ）において示したハッシュ値リスト７７３乃至７７６を、図１６（ａ）の番号リスト７７２と、ハッシュ関数の生成するハッシュ値のビット幅に関するデータとから想定する。そして、このハッシュ値リスト７７３乃至７７６からハッシュ値が全て互いに異なるハッシュ値リストを検出し、その検出したハッシュ値リストを確定ハッシュ値選択部７５２に供給する。
この時、ハッシュ値リスト７７６は、ｆｕｎｃＡ、ｆｕｎｃＣ、ｆｕｎｃＥおよびｆｕｎｃＧのハッシュ値が「１」で重複し、さらに、その他の３つの関数のハッシュ値が「０」で重複しているため、確定ハッシュ値選択部７５２に供給されない。また、ハッシュ値リスト７７５は、ｆｕｎｃＡおよびｆｕｎｃＥのハッシュ値が「０１」で重複、ｆｕｎｃＢおよびｆｕｎｃＦのハッシュ値が「１０」で重複、ｆｕｎｃＣおよびｆｕｎｃＧのハッシュ値が「１１」で重複しているため供給されない。その結果、ハッシュ値が全て互い異なるハッシュ値リストと判別されたハッシュ値リスト７７３および７７４が確定ハッシュ値選択部７５２に供給される。
【０２２５】
続いて、確定ハッシュ値選択部７５２は、供給されたハッシュ値リストからハッシュ値のビット幅が最も狭いハッシュ値リストを検出し、その検出されたハッシュ値リストのハッシュ値をハッシュ値付加部１７２に供給する。その結果、４ビットのハッシュ値のハッシュ値リスト７７３と、３ビットのハッシュ値のハッシュ値リスト７７４とのうちハッシュ値リスト７７４がビット幅が最も狭いハッシュ値のハッシュ値リストとして検出される。そして、確定ハッシュ値選択部７５２は、その検出したハッシュ値リスト７７４のハッシュ値を出力する。
【０２２６】
このように、本発明の第３の実施の形態では、候補ハッシュ値生成部７３０によりビット幅が異なるハッシュ値のみが生成される場合には、ハッシュ値テーブル７４０に関数入力値を保持させておいてもハッシュ値を決定することができる。これにより、ハッシュ値テーブル７４０におけるハッシュ値リストのデータ量を軽減させることができるため、全て互いに異なるハッシュ値のハッシュ値リストの検索などの処理を軽減させることができる。また、番号を関数入力値とする場合について説明したが、開始アドレスの場合においても同様に処理することができる。すなわち、この図１６において示した方法は、第１の実施の形態におけるハッシュ関数決定部２００でも同様に行うことができる。
【０２２７】
なお、ここでは、開始アドレスの取得された順序に従って付与された番号をハッシュ関数の関数入力値としてハッシュ値を算出したが、本発明はこれに限定されるものではない。例えば、図５において示した第１の実施の形態と同様に、開始アドレスを関数入力値とする場合も考えられる。また、開始アドレスの取得された順序を関数入力値とするではなく、再利用度生成部１２３が生成した再利用度の値に対する順序を関数入力値とする場合なども考えられる。
【０２２８】
また、ここでは、ユニークハッシュ値リスト判別部７５１は、番号リスト７７２と、ハッシュ関数の生成するハッシュ値のビット幅に関するデータとから、ハッシュ値リスト７７３乃至７７６を想定する場合について説明したが、本発明はこれに限定されるものではない。例えば、ハッシュ値出力部７５０は、値が全て互いに異なるとともに最も狭いビット幅の値を、開始アドレス取得部７１０が保持する番号リストから直接選択できるようにしてもよい。これにより、候補ハッシュ関数保持部７２０、候補ハッシュ値生成部７３０およびハッシュ値テーブル７４０を備えないハッシュ値決定部７００により、値が全て互いに異なるとともに最も狭いビット幅のハッシュ値を決定することができる。
【０２２９】
［本発明の第３の実施の形態における再利用命令の一例］
次に、本発明の第３の実施の形態におけるコンパイル処理装置１００が生成する再利用命令について図面を参照して説明する。
【０２３０】
図１７は、本発明の第３の実施の形態における関数の呼出し命令および関数の再利用命令の一例を示す概念図である。ここでは、データ処理装置のプロセッサコアはＭＩＰＳにより構成されることを想定する。また、ここでは、左端は最上位ビット（ＭＳＢ）を示し、右端は最下位ビット（ＬＳＢ）を示している。
【０２３１】
図１７（ａ）には、ＭＩＰＳ命令セットにおける関数の呼出し命令（ｃａｌｌ）であるＪＡＬＲ（Jump And Link Register）命令が示されている。ＭＩＰＳ命令セットは３２ビットの固定長の命令セットであり、このＪＡＬＲ命令は、３２個のビット（０乃至３１番）のビット列により表現されるものである。
【０２３２】
このＪＡＬＲ命令は、オペコードフィールド８１０と、関数番地フィールド（ｒｓ）８２０と、第１未使用フィールド８３０と、戻り番地フィールド（ｒｄ）８４０と、第２未使用フィールド８５０と、機能指定フィールド８６０とから構成される。
【０２３３】
オペコードフィールド８１０は、命令の種別を指定するフィールドである。このオペコードフィールド８１０は、第２６乃至第３１番目のビットから構成されるビット列である。このオペコードフィールド８１０には、ＳＰＥＣＩＡＬ命令としてビット列（００００００）が格納される。
【０２３４】
関数番地フィールド（ｒｓ）８２０は、関数の番地を格納するレジスタを指定するフィールドである。この関数番地フィールド（ｒｓ）８２０は、第２１乃至第２５番目のビットから構成されるビット列である。
【０２３５】
第１未使用フィールド８３０は、ＪＡＬＲ命令では使用されないフィールドである。この第１未使用フィールド８３０は、第１６乃至第２０番目のビット列である。この第１未使用フィールド８３０は、ＪＡＬＲ命令ではビット列（０００００）が格納される。
【０２３６】
戻り番地フィールド（ｒｄ）８４０は、関数からの戻り番地を指定するフィールドである。この戻り番地フィールド（ｒｄ）８４０は、第１１乃至第１５番目のビットから構成されるビット列である。この戻り番地フィールド（ｒｄ）８４０は、ＪＡＬＲ命令では３１番レジスタを指すビット列（１１１１１）が格納される。
【０２３７】
第２未使用フィールド８５０は、ＪＡＬＲ命令では使用されないフィールドである。この第２未使用フィールド８５０は、第６乃至第１０番目のビットから構成されるビット列である。この第２未使用フィールド８５０は、ＪＡＬＲ命令ではビット列（０００００）が格納される。
【０２３８】
機能指定フィールド８６０は、オペコードフィールド８１０により指定された命令が複数の機能を含む場合には、その複数の機能のうち１つの機能を指定するフィールドである。この機能指定フィールド８６０は、第０乃至第５番目のビットから構成されるビット列である。この機能指定フィールド８６０は、ＪＡＬＲ命令ではビット列（００１００１」）が格納される。
【０２３９】
図１７（ｂ）には、本発明の第３の実施の形態における関数のハッシュ値付再利用命令の一例が示されている。このハッシュ値付再利用命令は、３２個のビット（０乃至３１番）のビット列により表現されるものである。このハッシュ値付再利用命令は、オペコードフィールド８１０と、関数番地フィールド（ｒｓ）８２０と、第１ハッシュ値フィールド８３２および８３３と、戻り番地フィールド（ｒｄ）８４０と、第２ハッシュ値フィールド８５２および８５３と、機能指定フィールド８６０とから構成される。なお、ここでは、第１ハッシュ値フィールド８３２および８３３と、第２ハッシュ値フィールド８５２および８５３と以外の構成は、図１７（ａ）と同様のものであるため、図１７（ａ）と同符号を付してここでの説明を省略する。
【０２４０】
第１ハッシュ値フィールド８３２および８３３は、第２ハッシュ値フィールド８５２および８５３とともにハッシュ値が付加された再利用命令であることを示すフィールドである。この第１ハッシュ値フィールド８３２および８３３は、第２ハッシュ値フィールド８５２および８５３のビット列と連結させることによって、ハッシュ値を示す１０ビットの数値を示すフィールドになる。この第１ハッシュ値フィールド８３２および８３３と、第２ハッシュ値フィールド８５２および８５３とは、ＪＡＬＲ命令における第１未使用フィールド８３０および第２未使用フィールド８５０のビット列を「０００００」以外のビット列に変更したものである。ただし、この第１ハッシュ値フィールド８３２および８３３と、第２ハッシュ値フィールド８５２および８５３とは、一方のビット列が「０００００」以外ならばハッシュ値付再利用命令を指し示し、他方のビット列が「０００００」であってもよい。
【０２４１】
例えば、第１ハッシュ値フィールド８３２には、第２ハッシュ値フィールド８５２とともに、ハッシュ値の値が最も低いハッシュ値付再利用命令におけるビット列の値が格納されている。この第１ハッシュ値フィールド８３２は、第２ハッシュ値フィールド８５２と連結させることによって、１０ビットのビット列（０００００００００１）となる。すなわち、この命令を処理するデータ処理装置において、このビット列（０００００００００１）は、「１」の値のハッシュ値を指し示すと判断される。
【０２４２】
さらに、第１ハッシュ値フィールド８３３には、第２ハッシュ値フィールド８５３とともに、ハッシュ値の値が最も高いハッシュ値付再利用命令におけるビット列の値が格納されている。この第１ハッシュ値フィールド８３３は、第２ハッシュ値フィールド８５３と連結させることによって、１０ビットのビット列（１１１１１１１１１１）となる。すなわち、この命令を処理するデータ処理装置において、このビット列（１１１１１１１１１１）は、「１０２４」の値のハッシュ値を指し示すと判断される。
【０２４３】
なお、図１７（ｂ）では、ハッシュ値付加部１７２が生成するハッシュ値付再利用命令について説明した。再利用命令変換部１２４が生成するハッシュ値が付加される前の再利用命令については、第１未使用フィールド８３０および第２未使用フィールド８５０のいずれか一方のビット列が「０００００」以外のビット列に変更されたものであれば何でもよい。
【０２４４】
このように、第３の実施の形態では、ハッシュ値付加部１７２を設けることによって、ハッシュ値が付加された再利用命令を生成することができる。
【０２４５】
なお、ここでは、ＪＡＬＲの第１未使用フィールド８３０および第２未使用フィールド８５０にハッシュ値を埋め込んだハッシュ値付再利用命令について説明したが、本発明はこれに限定されるものではない。例えば、図６において示したハッシュ関数指定命令および識別子供給命令と同様に、ユーザが独自に新たにハッシュ値付再利用命令を定義してもよい。
【０２４６】
例えば、オペコードフィールド８１０にはＳＰＥＣＩＡＬ２命令を格納し、機能指定フィールド８６０には図６のユーザ定義命令フィールド（ＵＤＩ）２９５と同様に、ユーザが定義した複数の命令のうちの１つの命令を指定する値を格納する。そして、第６乃至第２５番目のユーザが定義可能なエンコード空間に、関数の番地を格納するレジスタを指定する値、関数からの戻り番地を指定する値、ハッシュ値が格納されている番地を格納する値を格納する。このハッシュ値が格納されている番地には１０ビット以上のビット幅のハッシュ値が格納できるため、これにより、１０ビットより大きいビット幅のハッシュ値が付加されたハッシュ値付再利用命令を生成することができる。
【０２４７】
このハッシュ値が格納されている番地を格納するレジスタを指定するフィールドを格納させることにより、１０ビットより大きいビット幅のハッシュ値が付加されたハッシュ値付再利用命令を生成することができる。
【０２４８】
［本発明の第３の実施の形態におけるコンパイル処理装置１００の動作例］
次に、本発明の第３の実施の形態におけるコンパイル処理装置１００の処理について図面を参照して説明する。
【０２４９】
図１８は、本発明の第３の実施の形態におけるコンパイル処理装置１００によるコンパイル処理の処理手順を示すフローチャートである。
【０２５０】
まず、ソースプログラム記憶部１１０からソースプログラムが読み出される（ステップＳ９１１）。次に、再利用候補区間抽出部１２１により、再利用候補区間が抽出される（ステップＳ９１２）。
【０２５１】
そして、再利用候補区間解析部１２２により、再利用候補区間の使用態様が解析される（ステップＳ９１３）。続いて、再利用度生成部１２３により、再利用候補区間の解析結果に基づいて再利用度が生成される（ステップＳ９１４）。
【０２５２】
次に、再利用命令変換部１２４により、再利用度に基づいて再利用候補区間の呼出し命令が再利用命令に変換される（ステップＳ９１５）。これは、例えば、関数が再利用候補区間である場合には、関数の呼出し命令（ｃａｌｌ）が再利用命令（ｍｅｍｏＣａｌｌ）に変換されることを意味する。このステップＳ９１１乃至Ｓ９１５の一連の処理により、再利用区間が判別される。
【０２５３】
そして、ハッシュ値決定部７００により、開始アドレスのビット幅より狭いビット幅で再利用区間を識別するハッシュ値を決定するハッシュ値決定処理が行われる（ステップＳ９６０）。
【０２５４】
続いて、ハッシュ値付加部１７２により、ハッシュ値付再利用命令が生成される（ステップＳ９１７）。
【０２５５】
最後に、機械語プログラム生成部１４０により、ハッシュ値のビット幅を指定する命令およびハッシュ値付再利用命令が含まれる機械語プログラムが生成される（ステップＳ９１８）。そして、コンパイル処理は終了する。
【０２５６】
図１９は、本発明の第３の実施の形態におけるハッシュ値決定部７００によるハッシュ値決定処理（ステップＳ９６０）の処理手順例の前半を示すフローチャートである。なお、ここでは、便宜上、ハッシュ値テーブル７４０には、図１６（ｂ）において示したハッシュ値リストが保持されることを想定する。なお、ここでは、ハッシュ関数の総数とは、開始アドレスをそのまま出力するハッシュ関数と、図４において示した式３乃至式７のハッシュ関数とを合わせた数の「６」であることを想定する。
【０２５７】
まず、開始アドレス取得部７１０により、再利用区間の開始アドレスがプログラムから取得され、開始アドレス取得部７１０に開始アドレスリストとして保持される（ステップＳ９６１）。続いて、開始アドレス取得部７１０に保持された開始アドレスの保持された順序に従って番号が付与され、その番号が番号リストとして保持される（ステップＳ９６２）。
【０２５８】
次に、ハッシュ関数カウンタ（ｈｎ）が「１」に初期化される（ステップＳ９６３）。なお、ここで示すハッシュ関数カウンタ（ｈｎ）とは、図８において示したハッシュ関数カウンタ（ｈｎ）と同様のものであるので、ここでの詳細な説明を省略する。なお、ハッシュ関数カウンタ（ｈｎ）の値の「０」には、図８において示したハッシュ関数カウンタ（ｈｎ）と同様に、開始アドレスをそのまま出力するハッシュ関数が割り当てられるものとする。
【０２５９】
続いて、開始アドレスカウンタ（ａｎ）が「０」に初期化される（ステップＳ９６４）。なお、ここで示す開始アドレスカウンタ（ａｎ）とは、図８において示した開始アドレスカウンタ（ａｎ）と同様のものであるので、ここでの詳細な説明を省略する。
【０２６０】
そして、候補ハッシュ値生成部７３０により、ハッシュ関数カウンタ（ｈｎ）が指し示すハッシュ関数を用いて、開始アドレスカウンタ（ａｎ）が指し示す開始アドレスに対して付与された番号を関数入力値としてハッシュ値が算出される（ステップＳ９６５）。次に、開始アドレスカウンタ（ａｎ）に「１」が加算される（ステップＳ９６６）。
【０２６１】
続いて、開始アドレスカウンタ（ａｎ）が開始アドレスリストの開始アドレスの総数であるか否かが判断される（ステップＳ９６７）。そして、開始アドレスカウンタ（ａｎ）が開始アドレスリストの開始アドレスの総数でないと判断された場合には、ステップＳ９６５に戻る。これにより、ハッシュ関数カウンタ（ｈｎ）が指し示すハッシュ関数の付与された番号を関数入力値としてまだ算出されていないハッシュ値が算出される。
【０２６２】
一方、開始アドレスカウンタ（ａｎ）が開始アドレスリストの開始アドレスの総数であると判断された場合には、ハッシュ関数カウンタ（ｈｎ）に「１」が加算される（ステップＳ９６８）。
【０２６３】
続いて、ハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数であるか否かが判断される（ステップＳ９６９）。そして、ハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数でないと判断された場合には、ステップＳ９６４に戻る。これにより、まだハッシュ値が算出されていないハッシュ関数を用いてハッシュ関数が算出される。
【０２６４】
一方、ハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数であると判断された場合には、ステップＳ９７０に進む。
【０２６５】
図２０は、本発明の第３の実施の形態におけるハッシュ値決定部７００によるハッシュ値決定処理（ステップＳ９６０）の処理手順例の後半を示すフローチャートである。
【０２６６】
まず、図１９のステップＳ９６９においてハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数であると判断された場合には、選択ハッシュ関数カウンタ（ｈ）が「０」に初期化される（ステップＳ９７０）。
【０２６７】
続いて、ハッシュ値ビット幅サイズ（ｗｓ）がハッシュ関数カウンタ（０）のハッシュ関数により生成されたハッシュ値のビット幅に変更される（ステップＳ９７１）。これにより、ハッシュ値ビット幅サイズ（ｗｓ）には開始アドレスのビット幅の６４ビットが設定される。
【０２６８】
そして、ハッシュ関数カウンタ（ｈｎ）が「１」に変更される（ステップＳ９７２）。続いて、ユニークハッシュ値リスト判別部７５１により、ハッシュ関数カウンタ（ｈｎ）の指し示すハッシュ関数に対応するハッシュ値リストのハッシュ値が全て互いに異なるか否かが判別される（ステップＳ９７３）。そして、ハッシュ関数（ｈｎ）の指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値が全て互いに異なっていないと判別された場合には、ステップＳ９７７に進む。
【０２６９】
一方、ハッシュ関数カウンタ（ｈｎ）の指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値が全て互いに異なっていると判別された場合には、ステップＳ９７４に進む。ステップＳ９７４では、確定ハッシュ値選択部７５２により、ハッシュ関数カウンタ（ｈｎ）の指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値のビット幅が、ハッシュ値ビット幅サイズ（ｗｓ）より小さい値であるか否かが判断される。そして、ハッシュ関数（ｈｎ）の指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値のビット幅がｗｓより小さい値ではないと判断された場合には、ステップＳ９７７に進む。
【０２７０】
一方、ハッシュ関数カウンタ（ｈｎ）の指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値のビット幅がハッシュ値ビット幅サイズ（ｗｓ）より小さい値であると判断された場合には、ステップＳ９７５に進む。ステップＳ９７５では、選択ハッシュ関数番号（ｈ）がハッシュ関数カウンタ（ｈｎ）の値に変更される。
【０２７１】
続いて、ハッシュ値ビット幅サイズ（ｗｓ）が、ハッシュ関数カウンタ（ｈｎ）が指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値のビット幅に変更される（ステップＳ９７６）。
【０２７２】
そして、ハッシュ関数カウンタ（ｈｎ）に「１」が加算される（ステップＳ９７７）。次に、ハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数であるか否かが判断される（ステップＳ９７８）。そして、ハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数でないと判断された場合には、ステップＳ９７３に戻る。
【０２７３】
一方、ハッシュ関数カウンタ（ｈｎ）がハッシュ関数の総数であると判断された場合には、ステップＳ９７９に進む。ステップＳ９７９では、選択ハッシュ関数（ｈ）が指し示すハッシュ関数と関連付けられたハッシュ値リストのハッシュ値がハッシュ値決定部７００の決定したハッシュ値として出力される（ステップＳ９７９）。
【０２７４】
このように、本発明の第３の実施の形態では、ハッシュ値決定部７００を設けることによって、複数のハッシュ関数のうち全て互いに異なるハッシュ値であってビット幅が最も狭くなるハッシュ値を生成するハッシュ関数のハッシュ値を出力することができる。
【０２７５】
このように、本発明の第３の実施の形態によれば、ハッシュ値付再利用命令が含まれるプログラムを生成することができる。
【０２７６】
＜４．第４の実施の形態＞
［本発明の第４の実施の形態におけるデータ処理装置３００の構成例］
図２１は、本発明の第４の実施の形態におけるデータ処理装置３００の構成例を示すブロック図である。このデータ処理装置３００は、図１０において示したデータ処理装置３００のハッシュ変換部５００を除いたものである。このデータ処理装置３００における命令キャッシュ３１１およびデータキャッシュ３１２は、図１０において示した各構成と同様の機能であるため、図１０と同一の符号を付してここでの説明を省略する。また、このデータ処理装置３００が接続されている主記憶部３６０およびその接続を介しているバス３５０は、図１０において示したものと同様の機能であるため、図１０と同一の符号を付してここでの説明を省略する。
【０２７７】
プロセッサコア４００は、図１０におけるプロセッサコア４００と同様に、プログラムの命令に従って演算を実行するものである。このプロセッサコア４００は、図１７において示したハッシュ値付再利用命令が入力された場合には、ハッシュ値付再利用命令に含まれるハッシュ値と、再利用区間の入力値とを履歴管理部６００に供給する。また、このプロセッサコア４００は、ハッシュ値付再利用命令を実行した際において履歴管理部６００から実行結果が供給されないときには、この命令を実行した結果である実行結果をデータキャッシュ３１２および履歴管理部６００に出力する。
【０２７８】
さらに、プロセッサコア４００は、入力される命令がハッシュ値付再利用命令である場合において履歴管理部６００から実行結果が供給されたときには、再利用区間における処理を中止して、この再利用区間を呼び出したルーチンに戻って実行を継続する。
【０２７９】
履歴管理部６００は、再利用区間の実行結果を保持して管理するものである。この履歴管理部６００は、プロセッサコア４００から供給されたハッシュ値と入力値と実行結果とを実行履歴として保持する。また、この履歴管理部６００は、ハッシュ値と入力値とがプロセッサコア４００から供給された場合には、このハッシュ値と入力値とが含まれる実行履歴を検索する。
【０２８０】
［本発明の第４の実施の形態におけるプロセッサコア４００および履歴管理部６００の構成例］
図２２は、本発明の第４の実施の形態におけるプロセッサコア４００および履歴管理部６００の構成例を示すブロック図である。ここでは、プロセッサコア４００と履歴管理部６００とが示されている。また、ここでは、プロセッサコア４００および履歴管理部６００の機能は、図１０および図２１と同様のものであるため、同一の符号を付してここでの詳細な説明を省略する。
【０２８１】
プロセッサコア４００は、フェッチ部４１０と、命令デコーダ４２０と、実行部４３０と、レジスタファイル４４０とを備える。なお、本発明の第４の実施の形態におけるフェッチ部４１０と、命令デコーダ４２０と、レジスタファイル４４０との機能は、図１１において示した各構成と同様の機能であるため、図１１と同一の符号を付してここでの詳細な説明を省略する。
【０２８２】
実行部４３０は、命令デコーダ４２０から供給された制御信号に基づいて、命令デコーダ４２０において解析した命令を実行するものである。この実行部４３０は、命令デコーダ４２０においてハッシュ値のビット幅を指定する命令をデコードした場合には、その命令が指定するビット幅をハッシュ値のビット幅として設定する。
【０２８３】
また、この実行部４３０は、命令デコーダ４２０がハッシュ値付再利用命令をデコードした場合、ハッシュ値付再利用命令が指定する再利用区間の処理を開始する。そして、この再利用区間の処理の開始とともに、実行部４３０は、ハッシュ値付再利用命令から取得したハッシュ値を、信号線４０９を介して履歴管理部６００に出力する。例えば、この実行部４３０は、ハッシュ値のビット幅が「５」と設定された場合には、図１７において示した第２ハッシュ値フィールド８５２および８５３の最下位ビットから５ビットの値をハッシュ値として信号線４０９を介して履歴管理部６００に出力する。
【０２８４】
そして、実行部４３０は、レジスタファイル４４０から供給される再利用区間の入力値に基づいて再利用区間における処理を実行するとともに、再利用区間の入力値を、信号線４０９を介して履歴管理部６００に出力する。
【０２８５】
なお、実行部４３０は、履歴管理部６００から再利用区間の実行結果が供給された場合には、再利用区間の処理を中止するとともに、その実行結果を履歴管理部６００から供給された旨を通知する信号をフェッチ部４１０に供給する。この時、実行部４３０は、実行結果をレジスタファイル４４０に出力する。
【０２８６】
一方、実行部４３０は、履歴管理部６００から再利用区間の実行結果が供給されない場合には、再利用区間の処理を最後まで実行して、その実行結果をレジスタファイル４４０に出力するとともに信号線４０９を介して履歴管理部６００に出力する。
【０２８７】
履歴管理部６００は、再利用区間の実行結果を保持して管理するものであり、履歴対象データ保持部６１０と、履歴検索部６２０と、履歴メモリ６３０と、履歴登録部６４０とを備える。なお、本発明の第４の実施の形態における履歴管理部６００の各構成は、ハッシュ値が実行部４３０から供給されること以外は図１１において示した各構成と同様の機能であるため、図１１と同一の符号を付してここでの詳細な説明を省略する。すなわち、図１１において示した履歴管理部６００はハッシュ変換部５００から供給されたハッシュ値を用いていたが、この本発明の第４の実施の形態における履歴管理部６００は実行部４３０から供給されるハッシュ値を用いる点が異なる。
【０２８８】
このように、本発明の第４の実施の形態では、本発明の第３の実施の形態の装置により生成されたハッシュ値付再利用命令が含まれるプログラムに基づいて、ハッシュ値と入力値と実行結果とを実行履歴として履歴メモリ６３０に保持させることができる。
【０２８９】
［本発明の第４の実施の形態におけるデータ処理装置３００の動作例］
次に、本発明の第４の実施の形態におけるデータ処理装置３００の処理について図面を参照して説明する。
【０２９０】
図２３は、本発明の第４の実施の形態におけるデータ処理装置３００による命令処理方法の処理手順例を示すフローチャートである。このフローチャートは、ハッシュ値のビット幅を指し示す命令が実行された以降の命令デコーダ４２０によりデコードされる命令毎の処理例を説明するものであり、命令デコーダ４２０によりデコードされる命令の実行の終了をフローチャートの終了とする。
【０２９１】
まず、フェッチ部４１０およびレジスタファイル４４０に、命令デコーダ４２０によって解読（デコード）される命令およびその命令に従って実行部４３０により実行される値が読み出される（ステップＳ９４１）。次に、命令デコーダ４２０により、フェッチ部４１０から供給された命令がデコードされる（ステップＳ９４２）。
【０２９２】
続いて、実行部４３０により、デコードした命令が再利用区間を指定するハッシュ値付再利用命令か否かが判断される（ステップＳ９４５）。そして、デコードした命令がハッシュ値付再利用命令でないと判断された場合には、レジスタファイル４４０から供給される入力値に基づいてその再利用区間が実行されることによって、実行結果が出力される（ステップＳ９４６）。そして、ステップＳ９５４に進む。
【０２９３】
一方、ステップＳ９４５の処理において、命令がハッシュ値付再利用命令であると判断された場合には、検索要求入力部６２１により、ハッシュ値および入力値を用いて履歴メモリ６３０に実行履歴があるか否かが判断される（ステップＳ９４８）。そして、実行履歴が履歴メモリ６３０にないと判断された場合には、実行部４３０により、レジスタファイル４４０から供給される入力値に基づいてその再利用区間が実行され、実行結果が出力される（ステップＳ９４９）。続いて、履歴登録部６４０により、実行履歴が履歴メモリ６３０に登録される（ステップＳ９５１）。これにより、履歴メモリ６３０に実行履歴が登録される。そして、ステップＳ９５４に進む。
【０２９４】
一方、実行履歴が履歴メモリ６３０にあると判断された場合には、実行結果出力部６２２により、実行結果が出力される（ステップＳ９５２）。これにより、実行している再利用区間の実行結果が履歴メモリ６３０から出力される。続いて、実行部４３０は、実行結果が出力された再利用区間の実行を中止させる（ステップＳ９５３）。そして、ステップＳ９５４に進む。
【０２９５】
そして、ステップＳ９４６、Ｓ９５１およびＳ９５３の処理の後に、実行結果がレジスタファイル４４０に書き戻される（ステップＳ９５４）。これにより、デコードされた命令の実行は終了する。
【０２９６】
このように、本発明の第４の実施の形態では、ハッシュ値と入力値と実行結果とを実行履歴として履歴メモリ６３０に保持させることができる。
【０２９７】
＜５．第５の実施の形態＞
［本発明の第５の実施の形態におけるデータ処理装置３００の構成例］
図２４は、本発明の第５の実施の形態におけるデータ処理装置３００の構成例を示すブロック図である。このデータ処理装置３００は、図１０において示したデータ処理装置３００の各構成に加えて、ハッシュ関数決定部３７０を備えている。ここでは、このハッシュ関数決定部３７０およびハッシュ変換部５００以外の各構成の機能は、図１０と同様の機能であるため、ここでの説明を省略する。
【０２９８】
ハッシュ関数決定部３７０は、プロセッサコア４００がプログラムを実行する前にハッシュ関数を決定するものである。このハッシュ関数決定部３７０は、主記憶部３６０から供給されたオブジェクトプログラムから再利用区間の開始アドレスを取得し、その開始アドレスのビット幅より狭いビット幅で再利用区間を識別するハッシュ値を生成するためのハッシュ関数を決定する。
【０２９９】
なお、このハッシュ関数決定部３７０は、図３において示した本発明の第１の実施の形態のハッシュ関数決定部２００をデータ処理装置３００に備えたものである。すなわち、この本発明の第５の実施の形態のハッシュ関数決定部３７０では、開始アドレス取得部２１０はオブジェクトプログラムを解析して再利用区間の開始アドレスを取得する。また、この本発明の第５の実施の形態では、確定ハッシュ関数選択部２５２は選択したハッシュ関数をハッシュ変換部５００に供給する。このハッシュ関数決定部３７０における開始アドレス取得部２１０および確定ハッシュ関数選択部２５２以外の各構成の機能は、図３と同様のものであるため、この本発明の第５の実施の形態での詳細な説明を省略する。
【０３００】
このハッシュ関数決定部３７０は、その決定したハッシュ関数をハッシュ変換部５００に供給する。
【０３０１】
ハッシュ変換部５００は、再利用区間の開始アドレスのビット幅より狭いビット幅で再利用区間を識別するためのハッシュ値に開始アドレスを変換するものである。このハッシュ変換部５００は、ハッシュ関数決定部３７０から供給されたハッシュ関数を保持する。このハッシュ変換部５００は、その保持しているハッシュ関数を用いて、プロセッサコア４００から供給された関数またはループの開始アドレスからハッシュ値を生成する。このハッシュ変換部５００は、その生成したハッシュ値を履歴管理部６００に供給する。
【０３０２】
このように、本発明の第５の実施の形態では、データ処理装置３００にハッシュ関数決定部３７０を設けることによって、既に生成されたオブジェクトプログラムを用いてハッシュ関数を決定することができる。
【０３０３】
［本発明の第５の実施の形態におけるプロセッサコア４００とハッシュ変換部５００と履歴管理部６００との構成例］
図２５は、本発明の第５の実施の形態におけるプロセッサコア４００とハッシュ変換部５００と履歴管理部６００との構成例を示すブロック図である。ここでは、プロセッサコア４００とハッシュ変換部５００と履歴管理部６００とが示されている。また、ここでは、プロセッサコア４００、ハッシュ変換部５００、履歴管理部６００の他に、ハッシュ変換部５００にハッシュ関数を供給するハッシュ関数決定部３７０が示されている。
【０３０４】
プロセッサコア４００は、フェッチ部４１０と、命令デコーダ４２０と、実行部４３０と、レジスタファイル４４０とを備える。なお、本発明の第５の実施の形態におけるフェッチ部４１０と命令デコーダ４２０とレジスタファイル４４０との機能は、図１１において示した各構成と同様の機能であるため、ここでの詳細な説明を省略する。
【０３０５】
実行部４３０は、命令デコーダ４２０から供給された制御信号に基づいて、命令デコーダ４２０において解析した命令を実行するものである。この本発明の第５の実施の形態における実行部４３０は、図１１において示した実行部４３０におけるハッシュ関数指定す命令を実行する機能を省いたものである。このハッシュ関数指定命令を実行する機能以外の実行部４３０の機能は、図１１において示した本発明の第１の実施の形態における実行部４３０の機能と同一であるためここでの説明を省略する。
【０３０６】
ハッシュ変換部５００は、再利用区間の開始アドレスのビット幅より狭いビット幅で再利用区間を識別するためのハッシュ値に開始アドレスを変換させるものであり、確定ハッシュ関数保持部５１０および確定ハッシュ値生成部５２０を備える。なお、本発明の第５の実施の形態における確定ハッシュ値生成部５２０の機能は、図１１において示したものと同様の機能であるため、ここでの詳細な説明を省略する。
【０３０７】
確定ハッシュ関数保持部５１０は、ハッシュ関数決定部３７０から供給されたハッシュ関数を保持するものである。この確定ハッシュ関数保持部５１０は、ハッシュ関数決定部３７０から信号線５０１を介してハッシュ関数が供給された場合にはこのハッシュ関数を保持し、その保持したハッシュ関数を確定ハッシュ値生成部５２０に供給する。
【０３０８】
履歴管理部６００は、再利用区間の実行結果を保持して管理するものであり、履歴対象データ保持部６１０と、履歴検索部６２０と、履歴メモリ６３０と、履歴登録部６４０とを備える。なお、この本発明の第５の実施の形態における履歴管理部６００の各構成の機能は、図１１において示した各構成の機能と同様のものであるため、ここでの詳細な説明を省略する。
【０３０９】
［本発明の第５の実施の形態におけるデータ処理装置３００の動作例］
次に、本発明の第５の実施の形態におけるデータ処理装置３００の処理について図面を参照して説明する。
【０３１０】
図２６は、本発明の第５の実施の形態におけるデータ処理装置３００による命令処理方法の処理手順例を示すフローチャートである。
【０３１１】
まず、ハッシュ関数決定部３７０によって、ハッシュ関数が決定される（ステップＳ９８１）。なお、このハッシュ関数決定部３７０のハッシュ関数を決定する処理手順例は、図８および９において示したハッシュ関数決定部２００の処理手順例と同様であるので、ここでの説明を省略する。
【０３１２】
続いて、ハッシュ変換部５００における確定ハッシュ関数保持部５１０において、ハッシュ関数決定部２００により決定されたハッシュ関数が保持される（ステップＳ９８２）。そして、プログラムの命令を実行するプログラム実行処理が行われる（ステップＳ９９０）。
【０３１３】
図２７は、本発明の第５の実施の形態におけるプログラム実行処理（ステップＳ９９０）の処理手順例を示すフローチャートである。このフローチャートは、プログラムの実行の開始をフローチャートの開始とし、プログラムの実行の終了をフローチャートの終了とする。
【０３１４】
まず、フェッチ部４１０およびレジスタファイル４４０に、命令デコーダ４２０によって解読（デコード）される命令およびその命令に従って実行部４３０により実行される値が読み出される（ステップＳ９４１）。次に、命令デコーダ４２０により、そのフェッチ部４１０から供給された命令がデコードされる（ステップＳ９４２）。
【０３１５】
続いて、実行部４３０により、解読（デコード）した命令が再利用命令か否かが判断される（ステップＳ９４５）。そして、デコードした命令が再利用命令でないと判断された場合には、レジスタファイル４４０から供給される入力値に基づいてその再利用区間が実行されることによって、実行結果が出力される（ステップＳ９４６）。そして、ステップＳ９５４に進む。
【０３１６】
一方、ステップＳ９４５の処理において、命令が再利用命令であると判断された場合には、確定ハッシュ値生成部５２０により、再利用区間の開始アドレスからハッシュ値が算出される（ステップＳ９４７）。続いて、検索要求入力部６２１により、ハッシュ値および入力値を用いて履歴メモリ６３０に実行情報があるか否かが判断される（ステップＳ９４８）。
【０３１７】
そして、実行履歴が履歴メモリ６３０にないと判断された場合には、実行部４３０により、レジスタファイル４４０から供給される入力値に基づいてその再利用区間が実行され、実行結果が出力される（ステップＳ９４９）。そして、履歴登録部６４０により、実行履歴が履歴メモリ６３０に登録される（ステップＳ９５１）。これにより、履歴メモリ６３０に実行履歴が登録される。そして、ステップＳ９５４に進む。
【０３１８】
一方、実行履歴が履歴メモリ６３０にあると判断された場合には、実行結果出力部６２２により、実行結果が出力される（ステップＳ９５２）。これにより、実行している再利用区間の実行結果が履歴メモリ６３０から出力される。続いて、実行部４３０は、実行結果が出力された再利用区間の実行を中止させる（ステップＳ９５３）。そして、ステップＳ９５４に進む。
【０３１９】
そして、ステップＳ９４６、Ｓ９５１およびＳ９５３の処理の後に、実行結果がレジスタファイル４４０に書き戻される（ステップＳ９５４）。これにより、デコードされた命令の実行は終了する。
【０３２０】
続いて、プログラムの実行が終了したか否かが判断される（ステップＳ９９５）。そして、プログラムの実行が終了していないと判断された場合には、ステップＳ９４１に戻り処理が繰り返される。
【０３２１】
このように、本発明の第５の実施の形態では、ハッシュ関数決定部３７０から確定ハッシュ関数保持部５１０にハッシュ関数を供給することによって、既に生成されたオブジェクトプログラムの再利用区間の開始アドレスからハッシュ値を生成することができる。
【０３２２】
このように、本発明の実施の形態によれば、値再利用の効率を改善することができる。すなわち、複数のハッシュ関数から選択したハッシュ関数を用いて開始アドレスからハッシュ値を生成することによって、ハッシュ値と入力値と実行結果とを実行履歴として履歴メモリ６３０に保持させることができる。このハッシュ値は、開始アドレスより短いビット幅で再利用区間を識別する値である。
【０３２３】
すなわち、本発明の実施の形態によれば、関数アドレスと入力値と実行結果とを実行履歴として履歴メモリ６３０に保存させる従来技術の装置と比較して、履歴メモリ６３０に保持されるデータ量を軽減することができる。これにより、履歴メモリ６３０に保持される実行履歴の数を増加させることができることによって、検索におけるヒット率を上昇させることができる。
【０３２４】
また、開始アドレスがハッシュ値となることにより、実行履歴の検索時に比較されるビット数が減少する。このことにより、検索回路を減少させることができることによって、検索に掛かる時間を減少させることができる。
【０３２５】
なお、本発明の実施の形態は本発明を具現化するための一例を示したものであり、本発明の実施の形態において明示したように、本発明の実施の形態における事項と、特許請求の範囲における発明特定事項とはそれぞれ対応関係を有する。同様に、特許請求の範囲における発明特定事項と、これと同一名称を付した本発明の実施の形態における事項とはそれぞれ対応関係を有する。ただし、本発明は実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において実施の形態に種々の変形を施すことにより具現化することができる。
【０３２６】
また、本発明の実施の形態において説明した処理手順は、これら一連の手順を有する方法として捉えてもよく、また、これら一連の手順をコンピュータに実行させるためのプログラム乃至そのプログラムを記憶する記録媒体として捉えてもよい。この記録媒体として、例えば、ＣＤ（Compact Disc）、ＭＤ（MiniDisc）、ＤＶＤ（Digital Versatile Disk）、メモリカード、ブルーレイディスク（Blu-ray Disc（登録商標））等を用いることができる。
【符号の説明】
【０３２７】
１００  コンパイル処理装置
１１０  ソースプログラム記憶部
１２０  再利用命令判別部
１２１  再利用候補区間抽出部
１２２  再利用候補区間解析部
１２３  再利用度生成部
１２４  再利用命令変換部
１４０  機械語プログラム生成部
１５０  オブジェクトプログラム記憶部
１７０  ハッシュ値付再利用命令生成部
１７２  ハッシュ値付加部
２００  ハッシュ関数決定部
２１０、７１０  開始アドレス取得部
２２０、７２０  候補ハッシュ関数保持部
２３０、７３０  候補ハッシュ値生成部
２４０、７４０  ハッシュ値テーブル
２５０  ハッシュ関数出力部
２５１、７５１  ユニークハッシュ値リスト判別部
２５２  確定ハッシュ関数選択部
３００  データ処理装置
３１０  一次キャッシュ
３１１  命令キャッシュ
３１２  データキャッシュ
３５０  バス
３６０  主記憶部
３７０  ハッシュ関数決定部
４００  プロセッサコア
４１０  フェッチ部
４２０  命令デコーダ
４３０  実行部
４４０  レジスタファイル
５００  ハッシュ変換部
５１０  確定ハッシュ関数保持部
５２０  確定ハッシュ値生成部
６００  履歴管理部
６１０  履歴対象データ保持部
６２０  履歴検索部
６２１  検索要求入力部
６２２  実行結果出力部
６３０  履歴メモリ
６４０  履歴登録部
７００  ハッシュ値決定部
７５０  ハッシュ値出力部
７５２  確定ハッシュ値選択部
【図１】
2011096153.tif 000010
【図２】
2011096153.tif 000011
【図３】
2011096153.tif 000012
【図４】
2011096153.tif 000013
【図５】
2011096153.tif 000014
【図６】
2011096153.tif 000015
【図７】
2011096153.tif 000016
【図８】
2011096153.tif 000017
【図９】
2011096153.tif 000018
【図１０】
2011096153.tif 000019
【図１１】
2011096153.tif 000020
【図１２】
2011096153.tif 000021
【図１３】
2011096153.tif 000022
【図１４】
2011096153.tif 000023
【図１５】
2011096153.tif 000024
【図１６】
2011096153.tif 000025
【図１７】
2011096153.tif 000026
【図１８】
2011096153.tif 000027
【図１９】
2011096153.tif 000028
【図２０】
2011096153.tif 000029
【図２１】
2011096153.tif 000030
【図２２】
2011096153.tif 000031
【図２３】
2011096153.tif 000032
【図２４】
2011096153.tif 000033
【図２５】
2011096153.tif 000034
【図２６】
2011096153.tif 000035
【図２７】
2011096153.tif 000036