(57)【要約】      （修正有）【課題】コール命令の実行完了に先行して複数のコール命令がブランチヒストリによって検出された場合に分岐予測の精度を高く保つ。【解決手段】実行が完了していないコール命令に対応するリターン命令のアドレス情報を記憶するリターンアドレススタックＸ（第２のリターンアドレススタック）に少数のエントリを用意し、それを補完するために、仮想のリターンアドレススタックＸのエントリの使用状況を保持するリターンヒットテーブルに多数のエントリを設ける。ブランチヒストリによりリターン命令の存在が予測された場合に、リターンアドレススタックＸにアドレス情報が保持されていれば、リターンアドレススタックＸに保持されたアドレス情報を優先して分岐予測結果として選択出力する。【選択図】図２−１
2006155374.tif 000002
【特許請求の範囲】
【請求項１】
パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測装置であって、
コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、この分岐命令の実行履歴情報を検索して分岐命令の存在と該分岐命令による分岐先を予測するブランチヒストリと、
サブルーチンのコール命令の実行が完了した場合に、該コール命令に対応するリターン命令の戻り先のアドレス情報を記憶する第１のリターンアドレススタックと、
前記ブランチヒストリによりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレス情報を記憶する第２のリターンアドレススタックと、
前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記第２のリターンアドレススタックにアドレス情報が保持されていれば、前記第２のリターンアドレススタックに保持されたアドレス情報を最優先で分岐予測結果として選択して出力する出力選択手段と
を備えたことを特徴とする分岐予測装置。
【請求項２】
分岐予測が失敗した場合に、前記第２のアドレススタックの内容を全消去することを特徴とする請求項１に記載の分岐予測装置。
【請求項３】
前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記第２のリターンアドレススタックに複数のアドレス情報が保持されていれば、前記第２のリターンアドレススタックに最後に記憶された有効なアドレス情報を最優先で分岐予測結果として選択して出力することを特徴とする請求項１または２に記載の分岐予測装置。
【請求項４】
前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記第２のリターンアドレススタックにアドレス情報が保持されていなければ、前記第１のリターンアドレススタックに保持されたアドレス情報を最優先で分岐予測結果として選択して出力することを特徴とする請求項１、２または３に記載の分岐予測装置。
【請求項５】
前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記第１のリターンアドレススタックと前記第２のリターンアドレススタックのいずれにもアドレス情報が保持されていなければ、前記ブランチヒストリの予測結果を分岐予測結果として選択して出力することを特徴とする請求項１〜４のいずれか一つに記載の分岐予測装置。
【請求項６】
前記ブランチヒストリによって存在が予測されたコール命令が実行完了したか否かと、該コール命令に対応するリターン命令の分岐予測が完了しているか否かを保持するコール命令状況保持手段をさらに備えたことを特徴とする請求項１〜５のいずれか一つに記載の分岐予測装置。
【請求項７】
分岐予測が失敗した場合に、前記コール命令状況保持手段の内容を全消去することを特徴とする請求項６に記載の分岐予測装置。
【請求項８】
前記コール命令状況保持手段が状況を保持しているコール命令の数を保持するカウンタをさらに備えたことを特徴とする請求項６または７に記載の分岐予測装置。
【請求項９】
前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記ブランチヒストリにより存在が予測されているが、実行が完了しておらず、かつ、対応するリターン命令の分岐予測が完了していないコール命令が存在することが前記コール命令状況保持手段によって判明した場合には、前記第２のリターンアドレススタックに保持されたアドレス情報を最優先で分岐予測結果として選択して出力することを特徴とする請求項６〜８のいずれか一つに記載の分岐予測装置。
【請求項１０】
前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記ブランチヒストリにより存在が予測されているが、実行が完了しておらず、かつ、対応するリターン命令の分岐予測が完了していないコール命令が存在することが前記コール命令状況保持手段によって判明したが、前記第２のリターンアドレススタックにアドレス情報が保持されていない場合には、前記ブランチヒストリの予測結果を分岐予測結果として選択して出力することを特徴とする請求項９に記載の分岐予測装置。
【請求項１１】
前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記ブランチヒストリにより存在が予測されているが、実行が完了しておらず、かつ、対応するリターン命令の分岐予測が完了していないコール命令が存在しないことが前記コール命令状況保持手段によって判明した場合には、前記第１のリターンアドレススタックに保持されたアドレス情報を最優先で分岐予測結果として選択して出力することを特徴とする請求項６〜１０のいずれか一つに記載の分岐予測装置。
【請求項１２】
前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記ブランチヒストリにより存在が予測されているが、実行が完了しておらず、かつ、対応するリターン命令の分岐予測が完了していないコール命令が存在しないことが前記コール命令状況保持手段によって判明し、前記第１のリターンアドレススタックにアドレス情報が保持されていない場合には、前記ブランチヒストリの予測結果を分岐予測結果として選択して出力することを特徴とする請求項１１に記載の分岐予測装置。
【請求項１３】
前記コール命令状況保持手段は、前記ブランチヒストリによって存在が予測されたコール命令の状況を命令毎にビットのオン／オフによって保持することを特徴とする請求項６〜８のいずれか一つに記載の分岐予測装置。
【請求項１４】
前記コール命令状況保持手段は、前記ブランチヒストリによってコール命令の存在が予測された場合に、管理対象のビット一つ追加して該ビットを０に設定し、前記ブランチヒストリによってリターン命令の存在が予測された場合には、管理対象のビットのうち値が０の最新のビットを１に変更し、いずれかのコール命令の実行が完了した場合には、最も古いビットを管理対象から外すことを特徴とする請求項１３に記載の分岐予測装置。
【請求項１５】
前記コール命令状況保持手段は、前記ブランチヒストリによってコール命令の存在が予測された場合に、管理対象のビット一つ追加して該ビットを１に設定し、前記ブランチヒストリによってリターン命令の存在が予測された場合には、管理対象のビットのうち値が１の最新のビットを０に変更し、いずれかのコール命令の実行が完了した場合には、最も古いビットを管理対象から外すことを特徴とする請求項１３に記載の分岐予測装置。
【請求項１６】
前記コール命令状況保持手段は、所有するビットを初期化時に全て０に設定し、前記ブランチヒストリによってコール命令の存在が予測された場合に、管理対象のビット一つ追加して該ビットを１に設定し、前記ブランチヒストリによってリターン命令の存在が予測された場合には、全ビットのうち値が１の最新のビットを０に変更し、いずれかのコール命令の実行が完了した場合には、最も古いビットを管理対象から外すことを特徴とする請求項１３に記載の分岐予測装置。
【請求項１７】
前記コール命令状況保持手段は、所有するビットを初期化時に全て１に設定し、前記ブランチヒストリによってコール命令の存在が予測された場合に、管理対象のビット一つ追加して該ビットを０に設定し、前記ブランチヒストリによってリターン命令の存在が予測された場合には、全ビットのうち値が０の最新のビットを１に変更し、いずれかのコール命令の実行が完了した場合には、最も古いビットを管理対象から外すことを特徴とする請求項１３に記載の分岐予測装置。
【請求項１８】
パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測方法であって、
コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶するブランチヒストリをもちいて、分岐命令の存在と該分岐命令による分岐先を予測する分岐命令予測工程と、
前記分岐命令予測工程によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレス情報を記憶手段に記憶する第１のリターンアドレス記憶工程と、
サブルーチンのコール命令の実行が完了した場合に、該コール命令に対応するリターン命令の戻り先のアドレス情報を記憶手段に記憶する第２のリターンアドレス記憶工程と、
前記分岐命令予測工程によりリターン命令の存在が予測された場合に、前記第１のリターンアドレス記憶工程より記憶されたアドレス情報が存在すれば、前記第１のリターンアドレス記憶工程により記憶されたアドレス情報を最優先で分岐予測結果として選択して出力する出力選択工程と
を含んだことを特徴とする分岐予測方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測装置および分岐予測方法に関し、特にコール命令の実行完了に先行して複数のコール命令がブランチヒストリによって検出された場合に分岐予測の精度を高く保つことができる分岐予測装置および分岐予測方法に関するものである。
【背景技術】
【０００２】
従来より、パイプライン方式のプロセッサにおいては、処理の高速化のために分岐予測の手法が広く用いられている。本来、プログラム中に分岐が存在する場合、分岐が確定するまでパイプラインを停止する必要があるが、分岐予測をおこなうプロセッサは、分岐を予測し、予測した分岐後の命令を投機的に実行する。
【０００３】
分岐予測には、予測が当たった場合、分岐が確定するのを待つ分の処理時間を短縮することができるという大きなメリットがあるが、予測がはずれた場合は、パイプラインをフラッシュして分岐命令の部分から処理を再実行する必要がありペナルティも大きい。このため、分岐予測においては、予測の精度が非常に重要となっている。
【０００４】
分岐予測には、一般的には、ブランチヒストリが用いられる。ブランチヒストリは、過去に実行した分岐命令のアドレスとその分岐命令により分岐した分岐先のアドレスとを対にして履歴として保持する装置である。ブランチヒストリを用いた分岐予測は、過去の履歴に基づいたものであるため、ループ処理のように同じ分岐が繰り返される場合に非常に効果的であるが、サブルーチンからのリターン命令による分岐に対しては有効性が低い。
【０００５】
サブルーチンからのリターン命令により分岐する場合、分岐先は、サブルーチンのコール命令の次の命令となる。だが、一般的に、サブルーチンはプログラムの各所から呼び出されるため、リターン命令の戻り先は一定ではない。したがって、過去の履歴にしたがって分岐先を予測しても、予測が正しいとは限らない。
【０００６】
そこで、サブルーチンのコール命令の実行時にリターン命令による戻り先のアドレスをリターンスアドレスタックに格納しておき、リターン命令については、ブランチヒストリよりリターンアドレススタックを優先して分岐予測をおこなうことで予測の精度を高める手法が広く採用されている。
【０００７】
リターンスアドレスタックは、コール命令の実行が完了した後にそのコール命令に対応するリターン命令の戻り先のアドレスを格納する。このため、命令列の先読み等により、コール命令の実行が完了する前にリターン命令がブランチヒストリによって検出された場合には、リターンスアドレスタックには戻り先のアドレスが格納されておらず、分岐予測の精度が低下するという問題がある。
【０００８】
そこで、本出願人は、特許文献１において、第２のリターンアドレススタックを設け、ブランチヒストリによってコール命令が検出された段階で、この第２のリターンアドレススタックにリターン命令の戻り先のアドレスを格納することで、上記の場合にも精度の高い分岐予測を実現する技術を提案している。
【０００９】
【特許文献１】特願２００４−２２２３９９号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、特許文献１で提案されている技術は、ブランチヒストリによってコール命令が検出された後、そのコール命令の実行が完了するまでの間にブランチヒストリによって他のコール命令が検出されることまで考慮していないという問題がある。第２のリターンアドレススタックにはリターン命令の戻り先のアドレスを格納するエントリを一つしか設けていないため、ブランチヒストリによって検出されているが、実行が完了していないコール命令が複数ある場合には、最後に検出されたコール命令に対応するリターン命令の戻り先以外のアドレスは破棄され、分岐先の予測精度が低下する。
【００１１】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、コール命令の実行完了に先行して複数のコール命令がブランチヒストリによって検出された場合に分岐予測の精度を高く保つことができる分岐予測装置および分岐予測方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するため、本発明は、パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測装置であって、コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、この分岐命令の実行履歴情報を検索して分岐命令の存在と該分岐命令による分岐先を予測するブランチヒストリと、サブルーチンのコール命令の実行が完了した場合に、該コール命令に対応するリターン命令の戻り先のアドレス情報を記憶する第１のリターンアドレススタックと、前記ブランチヒストリによりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレス情報を記憶する第２のリターンアドレススタックと、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記第２のリターンアドレススタックにアドレス情報が保持されていれば、前記第２のリターンアドレススタックに保持されたアドレス情報を最優先で分岐予測結果として選択して出力する出力選択手段とを備えたことを特徴とする。
【００１３】
また、本発明は、パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測方法であって、コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶するブランチヒストリをもちいて、分岐命令の存在と該分岐命令による分岐先を予測する分岐命令予測工程と、前記分岐命令予測工程によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレス情報を記憶手段に記憶する第１のリターンアドレス記憶工程と、サブルーチンのコール命令の実行が完了した場合に、該コール命令に対応するリターン命令の戻り先のアドレス情報を記憶手段に記憶する第２のリターンアドレス記憶工程と、前記分岐命令予測工程によりリターン命令の存在が予測された場合に、前記第１のリターンアドレス記憶工程より記憶されたアドレス情報が存在すれば、前記第１のリターンアドレス記憶工程により記憶されたアドレス情報を最優先で分岐予測結果として選択して出力する出力選択工程とを含んだことを特徴とする。
【００１４】
この発明によれば、第２のリターンアドレススタックに有効なエントリが存在する場合には、リターンスタックポインタの値に関わらず、第２のリターンアドレススタックから分岐先のアドレスを取得するように構成したので、第１のリターンアドレススタックと第２のリターンアドレススタックに格納されたアドレス情報を適切な順序で取得して精度の高い分岐予測をおこなうことができる。
【００１５】
また、本発明は、上記の発明において、前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記第２のリターンアドレススタックに複数のアドレス情報が保持されていれば、前記第２のリターンアドレススタックに最後に記憶された有効なアドレス情報を最優先で分岐予測結果として選択して出力することを特徴とする。
【００１６】
この発明によれば、第２のリターンアドレススタックに有効なエントリが複数存在する場合には、第２のリターンアドレススタックに最後に格納された有効なアドレス情報を取得するように構成したので、ブランチヒストリによって検出されているが、実行が完了していないコール命令が複数ある場合にも精度の高い分岐予測をおこなうことができる。
【００１７】
また、本発明は、上記の発明において、前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記第２のリターンアドレススタックにアドレス情報が保持されていなければ、前記第１のリターンアドレススタックに保持されたアドレス情報を最優先で分岐予測結果として選択して出力することを特徴とする。
【００１８】
この発明によれば、第２のリターンアドレススタックに有効なアドレス情報が格納されていない場合に第１のリターンアドレススタックから分岐先のアドレスを取得するように構成したので、第１のリターンアドレススタックと第２のリターンアドレススタックに格納されたアドレス情報を適切な順序で取得して精度の高い分岐予測をおこなうことができる。
【００１９】
また、本発明は、上記の発明において、前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記第１のリターンアドレススタックと前記第２のリターンアドレススタックのいずれにもアドレス情報が保持されていなければ、前記ブランチヒストリの予測結果を分岐予測結果として選択して出力することを特徴とする。
【００２０】
この発明によれば、第１および第２のリターンアドレススタックに有効なアドレス情報が格納されていない場合にブランチヒストリの予測結果を用いるように構成したので、第１のリターンアドレススタックと第２のリターンアドレススタックに格納されたアドレス情報とブランチヒストリの情報とを適切な順序で取得して精度の高い分岐予測をおこなうことができる。
【００２１】
また、本発明は、上記の発明において、前記ブランチヒストリによって存在が予測されたコール命令が実行完了したか否かと、該コール命令に対応するリターン命令の分岐予測が完了しているか否かを保持するコール命令状況保持手段をさらに備えたことを特徴とする。
【００２２】
この発明によれば、コール命令状況保持手段によって仮想の第２のリターンアドレススタックのエントリの有効性を管理するように構成したので、実際の第２のリターンアドレススタックのエントリ数を少なく抑えながら、高い精度で分岐予測をおこなうことができる。
【００２３】
また、本発明は、上記の発明において、前記コール命令状況保持手段が状況を保持しているコール命令の数を保持するカウンタをさらに備えたことを特徴とする。
【００２４】
この発明によれば、コール命令状況保持手段に情報が保持されたコール命令の件数をカウンタに保持するように構成したので、コール命令状況保持手段の仕組みを簡略化することができる。
【００２５】
また、本発明は、上記の発明において、前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記ブランチヒストリにより存在が予測されているが、実行が完了しておらず、かつ、対応するリターン命令の分岐予測が完了していないコール命令が存在することが前記コール命令状況保持手段によって判明した場合には、前記第２のリターンアドレススタックに保持されたアドレス情報を最優先で分岐予測結果として選択して出力することを特徴とする。
【００２６】
また、本発明は、上記の発明において、前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記ブランチヒストリにより存在が予測されているが、実行が完了しておらず、かつ、対応するリターン命令の分岐予測が完了していないコール命令が存在することが前記コール命令状況保持手段によって判明したが、前記第２のリターンアドレススタックにアドレス情報が保持されていない場合には、前記ブランチヒストリの予測結果を分岐予測結果として選択して出力することを特徴とする。
【００２７】
また、本発明は、上記の発明において、前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記ブランチヒストリにより存在が予測されているが、実行が完了しておらず、かつ、対応するリターン命令の分岐予測が完了していないコール命令が存在しないことが前記コール命令状況保持手段によって判明した場合には、前記第１のリターンアドレススタックに保持されたアドレス情報を最優先で分岐予測結果として選択して出力することを特徴とする。
【００２８】
また、本発明は、上記の発明において、前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記ブランチヒストリにより存在が予測されているが、実行が完了しておらず、かつ、対応するリターン命令の分岐予測が完了していないコール命令が存在しないことが前記コール命令状況保持手段によって判明し、前記第１のリターンアドレススタックにアドレス情報が保持されていない場合には、前記ブランチヒストリの予測結果を分岐予測結果として選択して出力することを特徴とする。
【００２９】
これらの発明によれば、コール命令状況保持手段に記憶された情報に基づいて、第２のリターンアドレススタックに有効なアドレス情報が格納されているか否かを判断するように構成したので、第１のリターンアドレススタックと第２のリターンアドレススタックに格納されたアドレス情報とブランチヒストリの情報とを適切な順序で取得して精度の高い分岐予測をおこなうことができる。
【００３０】
また、本発明は、上記の発明において、前記コール命令状況保持手段は、前記ブランチヒストリによって存在が予測されたコール命令の状況を命令毎にビットのオン／オフによって保持することを特徴とする。
【００３１】
また、本発明は、上記の発明において、前記コール命令状況保持手段は、前記ブランチヒストリによってコール命令の存在が予測された場合に、管理対象のビット一つ追加して該ビットを０に設定し、前記ブランチヒストリによってリターン命令の存在が予測された場合には、管理対象のビットのうち値が０の最新のビットを１に変更し、いずれかのコール命令の実行が完了した場合には、最も古いビットを管理対象から外すことを特徴とする。
【００３２】
あるいは、本発明は、上記の発明において、前記コール命令状況保持手段は、前記ブランチヒストリによってコール命令の存在が予測された場合に、管理対象のビット一つ追加して該ビットを１に設定し、前記ブランチヒストリによってリターン命令の存在が予測された場合には、管理対象のビットのうち値が１の最新のビットを０に変更し、いずれかのコール命令の実行が完了した場合には、最も古いビットを管理対象から外すことを特徴とする。
【００３３】
あるいは、本発明は、上記の発明において、前記コール命令状況保持手段は、所有するビットを初期化時に全て０に設定し、前記ブランチヒストリによってコール命令の存在が予測された場合に、管理対象のビット一つ追加して該ビットを１に設定し、前記ブランチヒストリによってリターン命令の存在が予測された場合には、全ビットのうち値が１の最新のビットを０に変更し、いずれかのコール命令の実行が完了した場合には、最も古いビットを管理対象から外すことを特徴とする。
【００３４】
あるいは、本発明は、上記の発明において、前記コール命令状況保持手段は、所有するビットを初期化時に全て１に設定し、前記ブランチヒストリによってコール命令の存在が予測された場合に、管理対象のビット一つ追加して該ビットを０に設定し、前記ブランチヒストリによってリターン命令の存在が予測された場合には、全ビットのうち値が０の最新のビットを１に変更し、いずれかのコール命令の実行が完了した場合には、最も古いビットを管理対象から外すことを特徴とする。
【００３５】
これらの発明によれば、少数のビットからなる管理テーブルによって仮想の第２のリターンアドレススタックのエントリの有効性を管理するように構成したので、実際の第２のリターンアドレススタックのエントリ数を少数にしてコストの上昇を抑制しながら、高い精度で分岐予測をおこなうことができる。
【００３６】
また、本発明は、分岐予測が失敗した場合に、前記第２のアドレススタックの内容を全消去することを特徴とする。
【００３７】
また、本発明は、分岐予測が失敗した場合に、前記コール命令状況保持手段の内容を全消去することを特徴とする。
【００３８】
これらの発明によれば、分岐予測が失敗した場合に分岐予測のための各種情報を初期化し、誤った情報に基づいて分岐予測を継続しないように構成したので、高い精度で分岐予測をおこなうことができる。
【発明の効果】
【００３９】
本発明によれば、第２のリターンアドレススタックに有効なエントリが存在する場合には、リターンスタックポインタの値に関わらず、第２のリターンアドレススタックから分岐先のアドレスを取得するように構成したので、第１のリターンアドレススタックと第２のリターンアドレススタックに格納されたアドレス情報を適切な順序で取得して精度の高い分岐予測をおこなうことができるという効果を奏する。
【００４０】
また、本発明によれば、第２のリターンアドレススタックに有効なエントリが複数存在する場合には、第２のリターンアドレススタックに最後に格納された有効なアドレス情報を取得するように構成したので、ブランチヒストリによって検出されているが、実行が完了していないコール命令が複数ある場合にも精度の高い分岐予測をおこなうことができるという効果を奏する。
【００４１】
また、本発明によれば、第２のリターンアドレススタックに有効なアドレス情報が格納されていない場合に第１のリターンアドレススタックから分岐先のアドレスを取得するように構成したので、第１のリターンアドレススタックと第２のリターンアドレススタックに格納されたアドレス情報を適切な順序で取得して精度の高い分岐予測をおこなうことができるという効果を奏する。
【００４２】
また、本発明によれば、この発明によれば、第１および第２のリターンアドレススタックに有効なアドレス情報が格納されていない場合にブランチヒストリの予測結果を用いるように構成したので、第１のリターンアドレススタックと第２のリターンアドレススタックに格納されたアドレス情報とブランチヒストリの情報とを適切な順序で取得して精度の高い分岐予測をおこなうことができるという効果を奏する。
【００４３】
また、本発明によれば、コール命令状況保持手段によって仮想の第２のリターンアドレススタックのエントリの有効性を管理するように構成したので、実際の第２のリターンアドレススタックのエントリ数を少なく抑えながら、高い精度で分岐予測をおこなうことができるという効果を奏する。
【００４４】
また、本発明によれば、コール命令状況保持手段に情報が保持されたコール命令の件数をカウンタに保持するように構成したので、コール命令状況保持手段の仕組みを簡略化することができるという効果を奏する。
【００４５】
また、本発明によれば、コール命令状況保持手段に記憶された情報に基づいて、第２のリターンアドレススタックに有効なアドレス情報が格納されているか否かを判断するように構成したので、第１のリターンアドレススタックと第２のリターンアドレススタックに格納されたアドレス情報とブランチヒストリの情報とを適切な順序で取得して精度の高い分岐予測をおこなうことができるという効果を奏する。
【００４６】
また、本発明によれば、少数のビットからなる管理テーブルによって仮想の第２のリターンアドレススタックのエントリの有効性を管理するように構成したので、実際の第２のリターンアドレススタックのエントリ数を少数にしてコストの上昇を抑制しながら、高い精度で分岐予測をおこなうことができるという効果を奏する。
【００４７】
また、本発明によれば、分岐予測が失敗した場合に分岐予測のための各種情報を初期化し、誤った情報に基づいて分岐予測を継続しないように構成したので、高い精度で分岐予測をおこなうことができるという効果を奏する。
【発明を実施するための最良の形態】
【００４８】
以下に添付図面を参照して、この発明に係る分岐予測装置および分岐予測方法の好適な実施の形態を詳細に説明する。
【実施例１】
【００４９】
まず、本実施例に係るリターン命令の分岐予測方式の概要について説明する。図１は、本実施例に係る分岐予測装置の動作を説明するための命令列を示すサンプル図である。同図に示すように、メインルーチンは、アドレスＡのコール命令によってサブルーチンＡを呼び出す（ステップＳ１０１）。サブルーチンＡは、いくつかの命令を実行した後、アドレスＣのリターン命令によってメインルーチンへ復帰する（ステップＳ１０２）。リターン命令により復帰する先のアドレスは、コール命令のアドレスの８バイト後、すなわち、Ａ＋８となる。
【００５０】
ここで、リターン命令の戻り先のアドレスがコール命令のアドレス＋８となるのは、この命令列を実行するプロセッサが４バイトの命令長をもち、さらに、コール命令の後には必ず遅延命令をともなう仕様であるからである。したがって、プロセッサの仕様によっては、リターン命令の戻り先のアドレスがコール命令のアドレス＋４となったり、コール命令のアドレス＋１６となったりする場合もありうるが、本書では、リターン命令の戻り先のアドレスはコール命令のアドレス＋８であるものとして説明することとする。
【００５１】
メインルーチンは、アドレスＤのコール命令によってサブルーチンＢを呼び出す（ステップＳ１０３）。サブルーチンＢは、いくつかの命令を実行した後、アドレスＦのコール命令によってサブルーチンＣを呼び出す（ステップＳ１０４）。サブルーチンＣは、いくつかの命令を実行した後、アドレスＨのリターン命令によってサブルーチンＢへ復帰する（ステップＳ１０５）。復帰先のアドレスはＦ＋８である。サブルーチンＢは、いくつかの命令を実行した後、アドレスＩのリターン命令によってメインルーチンへ復帰する（ステップＳ１０６）。復帰先のアドレスはＤ＋８である。
【００５２】
次に、図１で示した命令列を実行する場合を例にして、本実施例に係る分岐予測方式の概要について説明する。図２−１〜２−５は、本実施例に係る分岐予測装置の動作を説明するための説明図である。図２−１は、ブランチヒストリにより、アドレスＡでコール命令が検出された場面を示している。なお、アドレスＡでコール命令が検出される前は、分岐予測装置は初期状態であったものとする。
【００５３】
同図に示すように、この分岐予測装置には、リターンアドレススタックと、リターンアドレススタックＸと、リターンスタックポインタとが存在する。リターンアドレススタックは、一般に利用されているリターンアドレススタックであり、実行ユニットでコール命令の実行が完了した際に、当該のコール命令に対応するリターン命令の戻り先のアドレスが格納される装置である。
【００５４】
リターンアドレススタックは、複数のエントリを有し、実行ユニットでコール命令の実行が完了するたびに先頭のエントリであるＳＴＫ０へリターン命令の戻り先のアドレスがプッシュされる。たとえば、実行ユニットで２つのコール命令の実行が完了した場面では、２番目に実行されたコール命令に対応するリターン命令の戻り先のアドレスが先頭のエントリであるＳＴＫ０に格納され、最初に実行されたコール命令に対応するリターン命令の戻り先のアドレスが２番目のエントリであるＳＴＫ１に格納される。また、リターンアドレススタックは、実行ユニットでリターン命令の実行が完了するたびにポップ動作をおこなって、最新のエントリの内容を破棄する。
【００５５】
リターンアドレススタックＸは、実行ユニットでコール命令の実行が完了する前に当該のコール命令に対応するリターン命令がブランチヒストリによって検出された場合に予測精度が低下するのを改善するために設けられた第２のリターンアドレススタックであり、ブランチヒストリでコール命令が検出された際に、当該のコール命令に対応するリターン命令の戻り先のアドレスが格納される装置である。
【００５６】
前述の特許文献１においては、リターンアドレススタックＸは、一つのエントリしか有していないが、ここでは複数のエントリを有しているものとする。リターンアドレススタックＸは、ブランチヒストリでコール命令が検出されるたびに先頭のエントリであるＳＴＫ−Ｘ１からリターン命令の戻り先のアドレスを格納していく。たとえば、ブランチヒストリで２つのコール命令が検出された場面では、最初に検出されたコール命令に対応するリターン命令の戻り先のアドレスが先頭のエントリであるＳＴＫ−Ｘ１に格納され、次に検出されたコール命令に対応するリターン命令の戻り先のアドレスが２番目のエントリであるＳＴＫ−Ｘ２に格納される。
【００５７】
また、リターンアドレススタックＸは、実行ユニットでコール命令の実行が完了するたびにシフト動作をおこなって最も古いエントリの内容を追い出す。また、いずれかのエントリが分岐予測に用いられた場合には、そのエントリのバリッドビットをオフにしてエントリを無効化する。
【００５８】
リターンスタックポインタは、２つのリターンアドレススタックのエントリのうち、どのエントリが分岐予測結果の取得対象のエントリであるのかを制御する装置である。リターンスタックポインタは、初期状態では０の値を保持し、ブランチヒストリでコール命令が検出されるたびに値が−１され、リターン命令が検出されるたびに＋１される。また、実行ユニットでコール命令の実行が完了するたびに値が＋１され、リターン命令の実行が完了するたびに−１される。
【００５９】
リターンスタックポインタの値が０以上の場合、リターンアドレススタックに分岐予測結果の取得対象のエントリが存在することを意味する。値が０の場合、リターンアドレススタックの先頭のＳＴＫ０が分岐予測結果の取得対象のエントリであり、リターンスタックポインタの値が正の方向に一つ大きくなるたびに、取得対象のエントリが一つずつ移動する。たとえば、リターンスタックポインタの値が３の場合、リターンアドレススタックのＳＴＫ３が分岐予測結果の取得対象のエントリとなる。
【００６０】
リターンスタックポインタの値が負の場合、リターンアドレススタックＸに分岐予測結果の取得対象のエントリが存在することを意味する。前述の特許文献１は、リターンアドレススタックＸのエントリが一つであると想定しているため、リターンスタックポインタの値が負の場合のリターンアドレススタックＸのエントリとの対応については記述していない。
【００６１】
ここでは、リターンスタックポインタの値が−１の場合、リターンアドレススタックＸの先頭のＳＴＫ−Ｘ１が分岐予測結果の取得対象のエントリであり、リターンスタックポインタの値が負の方向に一つ大きくなるたびに、取得対象のエントリが一つずつ移動するものとしておく。たとえば、リターンスタックポインタの値が−３の場合、リターンアドレススタックＸのＳＴＫ−Ｘ３が分岐予測結果の取得対象のエントリとなる。
【００６２】
図２−１は、アドレスＡでコール命令が検出された場面であるので、リターンアドレススタックＸの先頭のＳＴＫ−Ｘ１に戻り先のアドレスとしてＡ＋８が格納され、リターンスタックポインタの値は−１されて−１となっている。ここで、ブランチヒストリによりアドレスＣのリターン命令が検出されたとすると、リターンスタックポインタの値は−１であるので、ＳＴＫ−Ｘ１に格納された値、すなわちＡ＋８が分岐予測結果として取得される。Ａ＋８は、アドレスＣのリターン命令の分岐先として正しいアドレスである。
【００６３】
この段階では、コール命令の実行が完了されていないため、リターンアドレススタックには分岐先のアドレスが格納されていないが、リターンアドレススタックＸが有効に機能して正しい分岐予測をおこなうことが可能になっている。
【００６４】
図２−２は、アドレスＣでリターン命令が検出された後の場面を示している。ＳＴＫ−Ｘ１は、分岐予測に使用されたため、バリッドビットがオフになり無効化されている。また、リターン命令の検出により、リターンスタックポインタの値は、＋１されて０となっている。図２−３は、続いてアドレスＡのコール命令の実行が完了した場面を示している。コール命令の実行の完了を受けて、リターンアドレススタックの先頭のＳＴＫ０に戻り先のアドレスＡ＋８が格納され、リターンスタックポインタの値は、＋１されて１となっている。
【００６５】
図２−４は、続いてアドレスＤでコール命令が検出された場面を示している。コール命令の検出を受けて、リターンアドレススタックＸの先頭のＳＴＫ−Ｘ１に戻り先のアドレスＤ＋８が格納され、リターンスタックポインタの値は、−１されて０となっている。図２−５は、続いてアドレスＦでコール命令が検出された場面を示している。コール命令の検出を受けて、リターンアドレススタックＸの２番目のエントリのＳＴＫ−Ｘ２に戻り先のアドレスＦ＋８が格納され、リターンスタックポインタの値は、−１されて−１となっている。
【００６６】
ここで、ブランチヒストリによりアドレスＨのリターン命令が検出されたとすると、リターンスタックポインタの値は−１であるので、ＳＴＫ−Ｘ１に格納された値、すなわちＤ＋８が分岐予測結果として取得される。Ｄ＋８は、アドレスＨのリターン命令の分岐先のアドレスではないので、誤った分岐予測がおこなわれることとなる。
【００６７】
図２−５の場面では、リターンアドレススタックＸに２つの戻り先のアドレスが格納されているが、図１の命令列の実行順序をみると、アドレスＤのコール命令は必ずアドレスＦのコール命令より先に検出されることがわかる。すなわち、リターンアドレススタックＸには、アドレスＤのコール命令に対応するリターン命令の戻り先であるＤ＋８、アドレスＦのコール命令に対応するリターン命令の戻り先であるＦ＋８の順で値が格納されることになる。
【００６８】
同様に、図１の命令列の実行順序をみると、アドレスＨのリターン命令は必ずアドレスＩのリターン命令より先に検出されることがわかる。すなわち、アドレスＨのリターン命令の戻り先であるＦ＋８は、アドレスＩのリターン命令の戻り先であるＤ＋８より先に分岐予測で利用されるはずである。
【００６９】
このことから、リターンアドレススタックＸに格納された戻り先のアドレスについては、リターンスタックポインタの値に関わらず、最後に格納されたものから使用していけばよいことがわかる。図２−５の場面で、ブランチヒストリによりアドレスＨのリターン命令が検出された場合を考えると、最後に格納された戻り先のアドレスはＦ＋８であり、アドレスＨのリターン命令の分岐先のアドレスとして正しい値である。
【００７０】
また、コール命令の検出と実行完了の順序は、必ず検出の方が先になる。すなわち、リターン命令の分岐先のアドレスは、リターンアドレススタックよりも先にリターンアドレススタックＸに格納される。コール命令の完了は必ずインオーダでおこなわれるので、リターンアドレススタックＸに戻り先が格納されたコール命令は、リターンアドレススタックに戻り先が格納されたコール命令よりも後に実行されたことになる。
【００７１】
リターン命令は、最後に実行されたコール命令に対応したものから検出されるはずであるから、リターンアドレススタックＸに格納された戻り先のアドレスは、リターンアドレススタックに格納された戻り先のアドレスよりも先に分岐予測に使用する必要がある。このことから、リターンアドレススタックＸに有効なエントリが存在する場合には、リターンスタックポインタの値に関わらず、リターンアドレススタックＸから分岐先のアドレスを取得する必要があることがわかる。
【００７２】
たとえば、図２−４の場面で、アドレスＩのリターン命令が検出された場合、リターンスタックポインタの値に従うと、Ａ＋８という誤った分岐先を取得してしまう。この場合、リターンアドレススタックＸに有効なエントリが存在するので、リターンアドレススタックＸから最後に登録されたアドレスを取得するとＤ＋８という正しい分岐先が取得される。
【００７３】
このように本実施例に係る分岐予測方式においては、リターンアドレススタックＸに有効なエントリが存在する場合には、リターンスタックポインタの値に関わらず、リターンアドレススタックＸに最後に値が格納された有効なエントリから分岐先のアドレスを取得する。この方式をとることにより、ブランチヒストリによって検出されているが、実行が完了していないコール命令が複数ある場合にも精度の高い分岐予測をおこなうことが可能になる。
【００７４】
次に、本実施例に係る分岐予測装置の構成について説明する。図３は、本実施例に係る分岐予測装置の構成を示すブロック図である。同図に示すように、分岐予測装置２００は、命令フェッチ制御ユニット１１０と、分岐リザベーションステーション１５０と接続された構成をとる。
【００７５】
命令フェッチ制御ユニット１１０は、パイプラインで実行する命令の取得を制御するユニットである。命令フェッチ制御ユニット１１０による命令の取得要求は、実際の命令取得のためにキャッシュ制御ユニット１２０に送出されるとともに、分岐予測のために分岐予測装置２００内のブランチヒストリ２１０に対しても送出される。
【００７６】
キャッシュ制御ユニット１２０は、命令フェッチ制御ユニット１１０から要求された命令をキャッシュもしくは主記憶から取得するユニットである。キャッシュ制御ユニット１２０により取得された命令は、命令バッファ１３０に一時的に格納された後、デコーダ１４０によりデコードされ、命令の種類に応じたリザベーションステーションに送られる。
【００７７】
リザベーションステーションには、分岐リザベーションステーション１５０、整数演算リザベーションステーション１６０、浮動少数演算リザベーションステーション１７０、アドレス生成リザベーションステーション１８０などがあり、分岐命令は分岐リザベーションステーション１５０に送られてここで実行される。
【００７８】
分岐予測装置２００は、ブランチヒストリ２１０と、リターンアドレススタック２２０と、リターンアドレス演算回路２３０と、リターンアドレススタックＸ２４０と、バリッド制御回路２５０と、リターンアドレス演算回路２６０と、リターンスタックポインタ２７０と、リターンアドレス選択回路２８１と、出力選択回路２８２とを有する。
【００７９】
ブランチヒストリ２１０は、分岐リザベーションステーション１５０にて実行された分岐命令のアドレスとその命令による分岐先を対にして、その他の情報フラグとともに記憶しておく装置である。コール命令やリターン命令も分岐命令の一種であり、その分岐結果がブランチヒストリ２１０に記憶される。
【００８０】
また、ブランチヒストリ２１０は、命令フェッチ制御ユニット１１０から命令列のアドレスを取得すると、自身の情報を参照して、その命令列に含まれる命令によって分岐が発生するか否かを判断する。そして、分岐が発生すると判断した場合には、出力選択回路２８２に対して分岐先のアドレス等の情報を送出する。
【００８１】
リターンアドレススタック２２０は、分岐リザベーションステーション１５０にて実行されたコール命令に対応するリターン命令の戻り先のアドレスを記憶しておく装置である。リターンアドレススタック２２０の各エントリは、エントリの有効性を示すバリッドビットを備える。リターンアドレススタック２２０の有効なエントリは、リターンアドレス選択回路２８１に対して、当該エントリに格納されたアドレス情報を送出する。なお、本実施例においては、リターンアドレススタック２２０は４つのエントリからなるものとして説明するが、エントリの数は必ずしも４つである必要はない。
【００８２】
リターンアドレス演算回路２３０は、分岐リザベーションステーション１５０から伝えられたコール命令のアドレスをリターン命令の戻り先のアドレスへ変換する演算をおこない、リターンアドレススタック２２０へ送出する回路である。既に説明した通り、本実施例で説明しているプロセッサにおいては、コール命令のアドレスに＋８したものがリターン命令の戻り先のアドレスとなるが、他の仕様のプロセッサにおいては変換方式が異なる場合もある。
【００８３】
リターンアドレススタックＸ２４０は、ブランチヒストリ２１０にてコール命令が検出された場合に、そのコール命令に対応するリターン命令の戻り先のアドレスを記憶しておく装置である。リターンアドレススタックＸ２４０の各エントリは、エントリの有効性を示すバリッドビットを備える。リターンアドレススタックＸ２４０は、リターンアドレス選択回路２８１に対して、最後に値が格納された有効なエントリの情報を送出する。
【００８４】
バリッド制御回路２５０は、リターンアドレススタックＸ２４０のエントリのバリッドビットの状態を制御する回路である。バリッド制御回路２５０は、ブランチヒストリ２１０からのコールヒット信号等の状態に応じて、リターンアドレススタックＸ２４０のエントリのバリッドビットの状態を変更する。
【００８５】
リターンアドレス演算回路２６０は、ブランチヒストリ２１０が検出したコール命令のアドレスをリターン命令の戻り先のアドレスへ変換する演算をおこない、リターンアドレススタックＸ２４０へ送出する回路である。リターンアドレス演算回路２３０の場合と同様に、本実施例で説明しているプロセッサにおいては、コール命令のアドレスに＋８したものがリターン命令の戻り先のアドレスとなるが、他の仕様のプロセッサにおいては変換方式が異なる場合もある。
【００８６】
リターンスタックポインタ２７０は、リターン命令が検出された場合に使用すべきリターンアドレススタックのエントリを示す値を保持する装置である。具体的には、リターンスタックポインタ２７０保持する値が０００、００１、０１０、０１１である場合は、それぞれリターンアドレススタック２２０のＳＴＫ０、ＳＴＫ１、ＳＴＫ２、ＳＴＫ３のエントリを使用すべきことを意味する。なお、リターンアドレススタックＸ２４０に有効なエントリが存在する場合は、リターンスタックポインタ２７０保持する値に関わらず、リターンアドレススタックＸ２４０に保持された情報を用いて分岐予測がおこなわれる。
【００８７】
リターンアドレス選択回路２８１は、リターンアドレススタック２２０、リターンアドレススタックＸ２４０およびリターンスタックポインタ２７０の情報に基づいて適切な分岐先のアドレスを選択して出力選択回路２８２へ送出する回路である。
【００８８】
図４は、図３に示したリターンアドレス選択回路２８１の処理手順を示すフローチャートである。同図に示すように、リターンアドレス選択回路２８１は、リターンアドレススタックＸ２４０から有効な分岐先のアドレス情報が送出されていれば（ステップＳ１００１肯定）、そのアドレス情報を出力選択回路２８２へ送出する（ステップＳ１００２）。リターンアドレススタックＸ２４０からの情報がない場合は（ステップＳ１００１否定）、リターンスタックポインタ２７０がリターンアドレススタック２２０の有効なエントリを指示しており（ステップＳ１００３肯定）、かつ、指示されたエントリからアドレス情報が送出されていれば（ステップＳ１００４肯定）、そのエントリに格納されているアドレス情報を出力選択回路２８２へ送出する（ステップＳ１００５）。いずれかに該当しない場合は（ステップＳ１００３否定もしくはステップＳ１００４否定）、出力選択回路２８２へのアドレス情報の送出はおこなわない。
【００８９】
出力選択回路２８２は、複数の分岐情報から適切なものを選択して命令フェッチ制御ユニット１１０へ送出する回路である。具体的には、ブランチヒストリ２１０がリターン命令を検出した場合は、リターンアドレス選択回路２８１からアドレス情報が送出されていればそのアドレスを、さもなければ、ブランチヒストリ２１０が送出しているアドレスをリターン命令の戻り先のアドレスとして送出する。
【００９０】
次に、コール命令の実行が完了した場合の本実施例に係る分岐予測装置２００の動作について説明する。図５−１〜５−３は、本実施例に係る分岐予測装置２００の動作を説明するための説明図である。図５−１は、図２−５の場面の後にアドレスＣのリターン命令の実行が完了した場面を示している。リターン命令の実行完了を受けて、リターンアドレススタックでポップ動作がおこなわれて先頭のＳＴＫ０の内容が破棄され、リターンスタックポインタの値は、−１されて−２となっている。
【００９１】
図５−２は、続いてアドレスＤのコール命令の実行が完了した場面を示している。コール命令の実行完了を受けて、リターンスタックポインタの値は、＋１されて−１となっている。また、リターンアドレススタックＸでは、シフト動作がおこなわれて先頭のＳＴＫ−Ｘ１のＤ＋８が破棄されている。一方、リターンアドレススタックでは、実行が完了したコール命令に対応するリターン命令の戻り先のアドレスであるＤ＋８が先頭のエントリであるＳＴＫ０に格納される。
【００９２】
このように本実施例に係る分岐予測装置２００においては、ブランチヒストリによって検出されたコール命令に対応するリターン命令の戻り先のアドレスが一旦リターンアドレススタックＸに格納され、そのコール命令が実行ユニットによって実行完了した際に、リターン命令の戻り先のアドレスがリターンアドレススタックＸからリターンアドレススタックへシフト動作によって移動するかのように動作する。
【００９３】
すなわち、ブランチヒストリのコール命令とリターン命令の検出が完璧であれば、リターンアドレススタックＸとリターンアドレススタックは一体のスタックとして機能し、コール命令やリターン命令の実行がどこまで進んでいるかに関わらず、ブランチヒストリで検出されたコール命令に対応するリターン命令の分岐先を常に正確に予測できることになる。
【００９４】
図５−３は、続いてアドレスＨでリターン命令が検出された場面を示している。この場合、リターンアドレススタックＸに有効なエントリが存在するため、リターンアドレススタックＸに最後に格納されたアドレス情報であるＦ＋８が分岐予測結果として取得される。リターンアドレススタックＸに複数のエントリが格納された後の場面であるが、本実施例に係る分岐予測装置２００はリターン命令の分岐先を正確に予測することに成功している。
【００９５】
上述してきたように、本実施例１では、リターンアドレススタックＸに有効なエントリが存在する場合には、リターンスタックポインタの値に関わらず、リターンアドレススタックＸに最後に値が格納された有効なエントリから分岐先のアドレスを取得するように構成したので、ブランチヒストリによって検出されているが、実行が完了していないコール命令が複数ある場合にも精度の高い分岐予測をおこなうことができる。
【実施例２】
【００９６】
実施例１で説明した分岐予測方式を用いれば、ブランチヒストリによって検出されているが、実行が完了していないコール命令が複数ある場合にも精度の高い分岐予測をおこなうことができる。しかしながら、この分岐予測方式を用いて分岐予測の精度を上げるには、リターンアドレススタックＸに十分な数のエントリを用意しなければならず、コストが上昇するという問題がある。
【００９７】
そこで、本実施例では、リターンアドレススタックＸのエントリの数を少数に抑えながら、ブランチヒストリによって検出されているが、実行が完了していないコール命令が複数ある場合に十分な精度をもって分岐予測をおこなうことができる分岐予測方式について説明することとする。
【００９８】
図６は、本実施例に係る分岐予測装置の動作を説明するための命令列を示すサンプル図である。同図に示すように、メインルーチンは、アドレスＡのコール命令によってサブルーチンＡを呼び出す（ステップＳ２０１）。サブルーチンＡは、いくつかの命令を実行した後、アドレスＣのリターン命令によってメインルーチンへ復帰する（ステップＳ２０２）。リターン命令により復帰する先のアドレスは、コール命令のアドレスの８バイト後、すなわち、Ａ＋８となる。
【００９９】
メインルーチンは、アドレスＤのコール命令によってサブルーチンＢを呼び出す（ステップＳ２０３）。サブルーチンＢは、いくつかの命令を実行した後、アドレスＦのコール命令によってサブルーチンＣを呼び出す（ステップＳ２０４）。そして、サブルーチンＣは、いくつかの命令を実行した後、アドレスＨのコール命令によってサブルーチンＤを呼び出す（ステップＳ２０５）。
【０１００】
サブルーチンＤは、いくつかの命令を実行した後、アドレスＪのリターン命令によってサブルーチンＣへ復帰する（ステップＳ２０６）。復帰先のアドレスはＨ＋８である。サブルーチンＣは、いくつかの命令を実行した後、アドレスＫのリターン命令によってサブルーチンＢへ復帰する（ステップＳ２０７）。復帰先のアドレスはＦ＋８である。サブルーチンＢは、いくつかの命令を実行した後、アドレスＬのリターン命令によってメインルーチンへ復帰する（ステップＳ２０８）。復帰先のアドレスはＤ＋８である。
【０１０１】
次に、図６で示した命令列を実行する場合を例にして、従来の分岐予測装置の動作について説明する。ここで、従来の分岐予測装置と呼んでいるのは、実施例１にて説明した分岐予測装置のことである。ここでは、リターンアドレススタックのエントリの数が２つの場合を想定して説明する。
【０１０２】
図７−１〜７−８は、従来の分岐予測装置の動作を説明するための説明図である。図７−１は、ブランチヒストリにより、アドレスＡでコール命令が検出された場面を示している。なお、アドレスＡでコール命令が検出される前は、分岐予測装置は初期状態であったものとする。
【０１０３】
同図に示すように、この分岐予測装置には、リターンアドレススタックと、リターンアドレススタックＸと、リターンスタックポインタとが存在する。リターンアドレススタックは、一般に利用されているリターンアドレススタックであり、実行ユニットでコール命令の実行が完了した際に、当該のコール命令に対応するリターン命令の戻り先のアドレスが格納される装置である。
【０１０４】
リターンアドレススタックＸは、実行ユニットでコール命令の実行が完了する前に当該のコール命令に対応するリターン命令がブランチヒストリによって検出された場合に予測精度が低下するのを改善するために設けられた第２のリターンアドレススタックであり、ブランチヒストリでコール命令が検出された際に、当該のコール命令に対応するリターン命令の戻り先のアドレスが格納される装置である。
【０１０５】
リターンスタックポインタは、リターンアドレススタックのエントリのうち、どのエントリが分岐予測結果の取得対象のエントリであるのかを制御する装置である。リターンスタックポインタの値が０以上の場合、リターンアドレススタックに分岐予測結果の取得対象のエントリが存在することを意味する。ただし、リターンアドレススタックＸに有効なエントリが存在する場合は、リターンスタックポインタが指し示すエントリは、分岐予測には用いられない。
【０１０６】
図７−１は、アドレスＡでコール命令が検出された場面であり、リターンアドレススタックＸの先頭のＳＴＫ−Ｘ１に戻り先のアドレスとしてＡ＋８が格納され、リターンスタックポインタの値は−１されて−１となっている。ここで、ブランチヒストリによりアドレスＣのリターン命令が検出されたとすると、リターンアドレススタックＸに有効なエントリが存在するので、最新のエントリであるＳＴＫ−Ｘ１に格納された値、すなわちＡ＋８が分岐予測結果として取得される。Ａ＋８は、アドレスＣのリターン命令の分岐先として正しいアドレスである。
【０１０７】
図７−２は、アドレスＣでリターン命令が検出された後の場面を示している。ＳＴＫ−Ｘ１は、分岐予測に使用されたため、バリッドビットがオフになり無効化されている。また、リターン命令の検出により、リターンスタックポインタの値は、＋１されて０となっている。図７−３は、続いてアドレスＡのコール命令の実行が完了した場面を示している。コール命令の実行の完了を受けて、リターンアドレススタックの先頭のＳＴＫ０に戻り先のアドレスＡ＋８が格納され、リターンスタックポインタの値は、＋１されて１となっている。
【０１０８】
図７−４は、続いてアドレスＤでコール命令が検出された場面を示している。コール命令の検出を受けて、リターンアドレススタックＸの先頭のＳＴＫ−Ｘ１に戻り先のアドレスＤ＋８が格納され、リターンスタックポインタの値は、−１されて０となっている。図７−５は、続いてアドレスＦでコール命令が検出された場面を示している。コール命令の検出を受けて、リターンアドレススタックＸの２番目のエントリのＳＴＫ−Ｘ２に戻り先のアドレスＦ＋８が格納され、リターンスタックポインタの値は、−１されて−１となっている。
【０１０９】
図７−６は、続いてアドレスＨでコール命令が検出された場面を示している。コール命令の検出を受けて、リターンアドレススタックＸに戻り先のアドレスであるＨ＋８がプッシュされるが、既にエントリは２つとも埋まった状態であるため、古い情報であるＤ＋８がプッシュアウトされて消えてしまう。こうして、リターンアドレススタックＸは、ＳＴＫ−Ｘ２にＨ＋８が格納され、ＳＴＫ−Ｘ１にＦ＋８が格納された状態となる。また、リターンスタックポインタの値は、−１されて−２となっている。
【０１１０】
ここで、ブランチヒストリによりアドレスＪのリターン命令が検出されたとすると、リターンアドレススタックＸに有効なエントリが存在するので、最新のエントリであるＳＴＫ−Ｘ２に格納された値、すなわちＨ＋８が分岐予測結果として取得される。Ｈ＋８は、アドレスＪのリターン命令の分岐先のアドレスとして正しいアドレスである。図７−７は、アドレスＪでリターン命令が検出された後の場面を示している。ＳＴＫ−Ｘ２は、分岐予測に使用されたため、バリッドビットがオフになり無効化されている。また、リターン命令の検出により、リターンスタックポインタの値は、＋１されて−１となっている。
【０１１１】
ここで、ブランチヒストリによりアドレスＫのリターン命令が検出されたとすると、リターンアドレススタックＸに有効なエントリが存在するので、最新のエントリであるＳＴＫ−Ｘ１に格納された値、すなわちＦ＋８が分岐予測結果として取得される。Ｆ＋８は、アドレスＫのリターン命令の分岐先のアドレスとして正しいアドレスである。図７−８は、アドレスＫでリターン命令が検出された後の場面を示している。ＳＴＫ−Ｘ１は、分岐予測に使用されたため、バリッドビットがオフになり無効化されている。また、リターン命令の検出により、リターンスタックポインタの値は、＋１されて０となっている。
【０１１２】
ここで、ブランチヒストリによりアドレスＬのリターン命令が検出されたとすると、リターンアドレススタックＸに有効なエントリが存在せず、リターンスタックポインタの値は０であるので、リターンアドレススタックのＳＴＫ０に格納された値、すなわちＡ＋８が分岐予測結果として取得される。Ａ＋８は、アドレスＬのリターン命令の分岐先のアドレスではないので、誤った分岐予測がおこなわれることとなる。
【０１１３】
ここで誤った分岐予測がおこなわれるのは、図７−６の場面でＤ＋８がエントリの数が不足しているためにプッシュアウトされたことが考慮されていないためである。本実施例に係る分岐予測装置は、リターンアドレススタックＸに多数のエントリが存在することを仮想し、それらの仮想的なエントリの有効性を管理テーブルで管理する方式をとる。
【０１１４】
図８は、本実施例に係る分岐予測方式の概要を説明するための説明図である。同図に示すように、本実施例に係る分岐予測方式では、リターンヒットテーブルとコールヒットカウンタを使用する。
【０１１５】
リターンヒットテーブルは、仮想のリターンアドレススタックＸの各エントリの有効性を管理するテーブルである。リターンヒットテーブルの各ビットは、仮想のリターンアドレススタックＸのエントリ一つに対応し、初期値として０をとる。ビットが０であれば、対応する仮想のエントリが有効であることを示し、ビットが１であれば対応する仮想のエントリが分岐予測に用いられて無効化されていることを示す。
【０１１６】
リターンヒットテーブルは、コール命令が検出されるたびに最下位のビットであるＸＨ１から順に使用され、コール命令の実行が完了するたびにシフト動作により最下位のビットの値が捨てられる。コール命令の実行が完了すれば、リターン命令の戻り先のアドレスがリターンアドレススタックに格納されるため、仮想のリターンアドレススタックＸのエントリは不要となるためである。
【０１１７】
リターンヒットテーブルは、仮想のリターンアドレススタックＸのエントリごとに１ビットあればよいので、非常に低コストで実装することができる。たとえば、アドレス長が６４ビットあるとした場合、実際のリターンアドレススタックＸに８個のエントリを設けると６４×８で５１２ビットが必要になるが、リターンヒットテーブルは８ビットあれば済むことになる。
【０１１８】
コールヒットカウンタは初期値として０をとり、コール命令が検出されるたびに＋１され、コール命令の実行が完了するたびに−１される。したがって、コールヒットカウンタの値は、ブランチヒストリによって検出されているが、実行が完了していないコール命令の数、すなわち、値が格納されている仮想のリターンアドレススタックＸのエントリの数を表す。
【０１１９】
図８では、コールヒットカウンタの値が５となっており、実行ユニットで実行が完了していないコール命令が５個あり、それらのコール命令に対応するリターン命令の戻り先のアドレスが仮想のリターンアドレススタックＸの５つのエントリに格納されていることを示している。
【０１２０】
それらのコール命令には、既に、対応するリターン命令がブランチヒストリによって検出されているものがある場合もある。図８の例では、３番目と５番目のコール命令がこれに該当し、リターンヒットテーブルの対応するビットの値が１になっている。リターン命令が検出され、不要となったエントリであっても、コール命令実行完了時にシフトアウトする順序を保持するためにリターンヒットテーブルに対応するビットが保持される。
【０１２１】
実際のリターンアドレススタックＸは、コスト等の制約から２つのエントリのみを備えるものとする。このリターンアドレススタックＸにおいては、コール命令の検出時にリターン命令の戻り先のアドレスがプッシュされ、リターン命令の検出時にポップ動作によって最新のエントリの内容が破棄される。エントリが全て埋まっている状態でコール命令が検出された場合は、最も古いエントリの内容がプッシュアウトされて破棄される。
【０１２２】
図８の例では、仮想のリターンアドレススタックＸには３つの有効なエントリが存在するが、実際のリターンアドレススタックＸには２つのエントリしか存在しないため、最も古いエントリの内容がプッシュアウトされている。しかし、リターンヒットテーブルには、本来リターンアドレススタックＸには３つのエントリが存在しているはずであることが記録されているため、図７−８の場合のように誤ってリターンアドレススタックから分岐先のアドレスが取得されることを回避することができる。
【０１２３】
本実施例に係る分岐予測方式においては、ブランチヒストリでリターン命令が検出された場合に、コールヒットカウンタの値が１以上であればリターンヒットテーブルを調べる。そして、コールヒットカウンタの指すビットから最下位ビットまでの間に一つでも値が０のビットが存在すれば、コールヒットカウンタの指す位置に最も近いビットの値を１へ変更し、実際のリターンアドレススタックＸの最新のエントリの内容を取得して分岐予測結果とする。
【０１２４】
プッシュアウトによりアドレス情報が破棄されていた場合、リターンアドレススタックＸの全てのエントリが無効化されていることがある。この場合には、リターンアドレススタックＸとリターンアドレススタックを用いた分岐予測をおこなうことはできないので、ブランチヒストリの予測結果を分岐予測結果として採用する。ブランチヒストリの予測結果は誤っている場合もあるが、誤ってリターンアドレススタックからアドレスを取得する場合に比べればはるかに精度の高い予測結果をえることができる。
【０１２５】
また、リターンヒットテーブルにおいて値が０のビットが一つも存在しなければ、仮想のリターンアドレススタックＸの全てのエントリが使用済みであることになるので、リターンスタックポインタに従ってリターンアドレススタックから戻り先のアドレスを取得する。
【０１２６】
このように本実施例に係る分岐予測方式では、リターンヒットテーブルによって仮想のリターンアドレススタックＸの各エントリの有効性を管理するように構成したので、実際のリターンアドレススタックＸのエントリの数が少ない場合であっても、高い精度を保って分岐予測をおこなうことができる。
【０１２７】
実際には、リターンアドレススタックＸに多数のアドレス情報がプッシュされる場面は少ないと想定されるため、リターンアドレススタックＸのエントリ数を少なく抑えながら分岐予測の精度を高く保つことができるこの方式は、非常に高いコストパフォーマンスを有する。
【０１２８】
次に、本実施例に係る分岐予測装置の構成について説明する。図９は、本実施例に係る分岐予測装置の構成を示すブロック図である。命令フェッチ制御ユニット１１０〜アドレス生成リザベーションステーションについては、実施例１と同様であるので説明を省略する。
【０１２９】
分岐予測装置３００は、ブランチヒストリ３１０と、リターンアドレススタック３２０と、リターンアドレス演算回路３３０と、リターンアドレススタックＸ３４０と、リターンアドレス演算回路３５０と、コールヒットカウンタ３６０と、リターンヒットテーブル３７０と、リターンスタックポインタ３８０と、リターンアドレス選択回路３９１と、出力選択回路３９２とを有する。
【０１３０】
ブランチヒストリ３１０、リターンアドレススタック３２０およびリターンアドレス演算回路３３０は、それぞれ、実施例１におけるブランチヒストリ２１０、リターンアドレススタック２２０およびリターンアドレス演算回路２３０に対応し、同様の機能を有する。
【０１３１】
リターンアドレススタックＸ３４０は、ブランチヒストリ３１０にてコール命令が検出された場合に、そのコール命令に対応するリターン命令の戻り先のアドレスを記憶しておく装置であり、Ｘ−ＴＯＰとＸ−ＮＸＴという２つのエントリを有する。リターンアドレススタックＸ３４０においては、コール命令の検出時にアドレスがプッシュされ、リターン命令検出時に最新のエントリの内容がポップアップするため、先頭のエントリであるＸ−ＴＯＰが常に最新のエントリとなる。
【０１３２】
リターンアドレス演算回路３５０は、ブランチヒストリ３１０が検出したコール命令のアドレスをリターン命令の戻り先のアドレスへ変換する演算をおこない、リターンアドレススタックＸ３４０へ送出する回路である。
【０１３３】
コールヒットカウンタ３６０は、リターンヒットテーブル３７０に対応する仮想のリターンアドレススタックＸの何番目のエントリまでアドレス情報がスタックされているかを保持する装置である。
【０１３４】
図１０は、コールヒットカウンタ３６０の回路構成を示す論理回路図である。同図に示すように、コールヒットカウンタ３６０は、仮想のエントリ数を保持するのに十分なＫビットのラッチを有し、このラッチの保持している値をＣＡＬＬ＿ＨＩＴ＿ＣＴＲ信号として出力する。ラッチは初期化時に０に設定され、ブランチヒストリ３１０からのコールヒット信号がオンになるたびに＋１され、分岐リザベーションステーション１５０からのコール命令フラグがオンになるたびに−１される。
【０１３５】
図１１は、コールヒットカウンタ３６０のデコーダ部分の論理回路図である。同図に示すように、コールヒットカウンタ３６０から出力されるＣＡＬＬ＿ＨＩＴ＿ＣＴＲ信号は、デコーダによってデコードされて、ＣＴＲ＿ＥＱ＿０〜ＣＴＲ＿ＥＱ＿ｍのいずれかの信号一つをオンにする。たとえば、ＣＡＬＬ＿ＨＩＴ＿ＣＴＲ信号の値が０であればＣＴＲ＿ＥＱ＿０がオンになり、値がｍであればＣＴＲ＿ＥＱ＿ｍがオンになる。
【０１３６】
リターンヒットテーブル３７０は、対応する仮想のリターンアドレススタックＸのエントリの有効性を示すビットを保持する装置である。リターンヒットテーブル３７０の各ビットは、初期値が０であり、対応する仮想のエントリが予測に使用された場合に１に変化する。また、コール命令の実行が完了するたびに、最も古い仮想のエントリに対応するビットがシフトアウトされる。
【０１３７】
図１２は、リターンヒットテーブル３７０の回路構成を示す論理回路図である。同図に示すように、リターンヒットテーブル３７０は、ＸＨ１〜ＸＨｍのｍビットの情報を保持し、各ビットの値は、それぞれ、ＸＨ１＿ＳＥＴ〜ＸＨｍ＿ＳＥＴ信号によって制御される。たとえば、ｊビット目のＸＨｊのビットは、ＸＨｊ＿ＳＥＴ信号によって制御される。このＸＨｊ＿ＳＥＴ信号は、ブランチヒストリ３１０からのリターンヒット信号がオンであり、かつ、リターンヒットテーブル３７０のｊビットの次のビットからコールヒットカウンタ３６０が指すビットまでの全てのビットが１の場合、もしくは、コールヒットカウンタ３６０の値がｊである場合にオンとなる。
【０１３８】
図１３は、リターンヒットテーブル３７０の出力部分の回路構成を示す論理回路図である。同図に示すように、リターンヒットテーブル３７０から出力されるＵＳＥ＿Ｘ信号は、リターンヒットテーブル３７０の最下位ビットからコールヒットカウンタ３６０が指すビットまでのいずれかのビットが１の場合にオンとなる。
【０１３９】
リターンスタックポインタ３８０は、リターン命令が検出された場合に使用すべきリターンアドレススタックのエントリを示す値を保持する装置である。具体的には、リターンスタックポインタ３８０が保持する値が０００、００１、０１０、０１１である場合は、それぞれリターンアドレススタック２２０のＳＴＫ０、ＳＴＫ１、ＳＴＫ２、ＳＴＫ３のエントリを使用すべきことを意味する。なお、リターンアドレススタックＸ３４０に有効なエントリが存在する場合は、リターンスタックポインタ３８０が保持する値に関わらず、リターンアドレススタックＸ３４０に保持された情報を用いて分岐予測がおこなわれる。
【０１４０】
図１４は、リターンスタックポインタ３８０の回路構成を示す論理回路図である。同図に示すように、リターンスタックポインタ３８０は、＜２：０＞の３ビットからなるラッチを有し、このラッチの保持している値をＲＴＮ＿ＳＴＫ＿ＰＴＲ信号として出力する。ラッチの値は初期状態では０００であり、分岐リザベーションステーション１５０からのコール命令フラグがオンになるたびに＋１され、リターン命令フラグがオンになるたびに−１される。また、ブランチヒストリ３１０からのコールヒット信号がオンになるたびに−１され、リターンヒット信号がオンになるたびに＋１される。
【０１４１】
図１５は、リターンスタックポインタ３８０のデコーダ部分の論理回路図である。同図に示すように、リターンスタックポインタ３８０から出力されるＲＴＮ＿ＳＴＫ＿ＰＴＲ信号信号は、デコーダによってデコードされて、ＰＴＲ＿ＥＱ＿０００〜ＰＴＲ＿ＥＱ＿１１１のいずれかの信号一つをオンにする。具体的には、ＲＴＮ＿ＳＴＫ＿ＰＴＲ信号の値が０〜３の場合は、それぞれ、ＰＴＲ＿ＥＱ＿０００〜ＰＴＲ＿ＥＱ＿０１１がオンになり、ＲＴＮ＿ＳＴＫ＿ＰＴＲ信号の値が負の場合は、ＰＴＲ＿ＥＱ＿１１１がオンになる。
【０１４２】
なお、リターンスタックポインタ３８０のラッチのビット数は、リターンアドレススタック３２０のエントリが増えた場合には、それらのエントリを特定できるだけの幅に増やすものとする。
【０１４３】
リターンアドレス選択回路３９１は、リターンアドレススタック３２０、リターンアドレススタックＸ３４０およびリターンスタックポインタ３８０の情報に基づいて適切な分岐先のアドレスを選択して出力選択回路３９２へ送出する回路である。
【０１４４】
出力選択回路３９２は、複数の分岐情報から適切なものを選択して命令フェッチ制御ユニット１１０へ送出する回路である。具体的には、ブランチヒストリ３１０がリターン命令を検出した場合は、リターンアドレス選択回路３９１からアドレス情報が送出されていればそのアドレスを、さもなければ、ブランチヒストリ３１０が送出しているアドレスをリターン命令の戻り先のアドレスとして送出する。
【０１４５】
図１６は、リターンアドレス選択回路３９１と出力選択回路３９２の回路構成を示す論理回路図である。同図に示すように、リターンアドレススタックＸ３４０の先頭のエントリの有効性を示すＸ＿ＴＯＰ＿ＶＡＬＩＤ信号がオンであるとき、リターンヒットテーブル３７０から出力されるＵＳＥ＿Ｘ信号がオンであれば、Ｘ＿ＴＯＰ＿ＳＥＬ信号がオンになり、リターン命令の戻り先のアドレスをリターンアドレススタックＸ３４０から取得するべきであることを示す。
【０１４６】
また、Ｘ＿ＴＯＰ＿ＶＡＬＩＤ信号がオンでないときは、リターンスタックポインタ３８０が示すリターンアドレススタック３２０のエントリが有効であれば、そのエントリに対応するＳＴＫ０＿ＳＥＬ〜ＳＴＫ３＿ＳＥＬのいずれかの信号がオンになり、リターン命令の戻り先のアドレスをリターンアドレススタック３２０から取得するべきであることを示す。
【０１４７】
Ｘ＿ＴＯＰ＿ＳＥＬ信号およびＳＴＫ０＿ＳＥＬ〜ＳＴＫ３＿ＳＥＬの信号は、同時に２つ以上がオンになることはなく、リターンアドレス選択回路３９１に相当する第１のセレクタは、オンになっている信号に対応するエントリの内容を分岐予測結果として第２のセレクタへ出力する。Ｘ＿ＴＯＰ＿ＳＥＬ信号およびＳＴＫ０＿ＳＥＬ〜ＳＴＫ３＿ＳＥＬの信号のいずれもオンでない場合には、第２のセレクタへの出力はおこなわない。
【０１４８】
出力選択回路３９２に相当する第２のセレクタは、Ｘ＿ＴＯＰ＿ＳＥＬ信号およびＳＴＫ０＿ＳＥＬ〜ＳＴＫ３＿ＳＥＬの信号のいずれかがオンであり、かつ、ブランチヒストリ３１０からのリターンヒット信号がオンであれば、第１のセレクタから出力されたアドレスを分岐予測結果として命令フェッチ制御ユニット１１０へ出力する。その他の場合は、ブランチヒストリ３１０から出力されたアドレスを分岐予測結果として命令フェッチ制御ユニット１１０へ出力する。
【０１４９】
なお、リターンアドレススタック３２０と、リターンアドレススタックＸ３４０と、コールヒットカウンタ３６０と、リターンヒットテーブル３７０と、リターンスタックポインタ３８０は、分岐予測が失敗した場合には初期状態にリセットされる。
【０１５０】
また、本実施例では、リターンヒットテーブル３７０の各ビットは、０で初期化され、リターン命令検出時に１になるものとして説明してきたが、逆に、１で初期化され、リターン命令検出時に０になるように構成することもできる。このように構成した場合の、リターンヒットテーブル３７０の構成についても説明しておく。
【０１５１】
図１７は、リターンヒットテーブル３７０の回路構成を示す論理回路図である。同図に示すように、リターンヒットテーブル３７０は、ＸＨ１〜ＸＨｍのｍビットの情報を保持し、各ビットの値は、それぞれ、ＸＨ１＿ＳＥＴ〜ＸＨｍ＿ＳＥＴ信号によって制御される。たとえば、ｊビット目のＸＨｊのビットは、ＸＨｊ＿ＳＥＴ信号によって制御される。
【０１５２】
このＸＨｊ＿ＳＥＴ信号は、ブランチヒストリ３１０からのコールヒット信号がオンとなったならば、その時点のコールヒットカウンタ３６０の値がｊ−１であった場合にオフとなり、リターンヒットテーブル３７０の対応するビットを０にする。すなわち、ブランチヒストリ３１０からのコールヒット信号がオンになった場合には、コールヒットカウンタ３６０が新たに示すことになるビットが０に更新されることになる。
【０１５３】
また、ＸＨｊ＿ＳＥＴ信号は、ブランチヒストリ３１０からのリターンヒット信号がオンとなったならば、その時点のコールヒットカウンタ３６０の値がｊより上位のビットが全て１であった場合にオンとなり、リターンヒットテーブル３７０の対応するビットを１にする。すなわち、ブランチヒストリ３１０からのリターンヒット信号がオンになった場合には、リターンヒットテーブル３７０の値が０である最上位のビットが１に更新される。
【０１５４】
このようにリターンヒットテーブル３７０の各ビットは、対応する仮想のリターンスタックＸのエントリに有効な値が存在している場合のみ０となり、その他の場合は１の値をとることになる。
【０１５５】
図１８は、リターンヒットテーブル３７０の出力部分の論理回路図である。同図に示すように、リターンヒットテーブル３７０から出力されるＵＳＥ＿Ｘ信号は、リターンヒットテーブル３７０の全てのビットの中に一つでも１でないビットが存在した場合にオンとなる。リターンヒットテーブル３７０に１でないビットが存在するということは、仮想のリターンスタックＸのエントリに有効な値が存在していることを意味する。
【０１５６】
次に、本実施例に係る分岐予測装置の動作について、図６の命令列を実行する場合を例にして説明する。図１９−１〜１９−１２は、本実施例に係る分岐予測装置の動作を説明するための説明図である。なお、ここでは、リターンヒットテーブルの各ビットを０で初期化する方式を用いた場合について説明することとする。
【０１５７】
図１９−１は、アドレスＡでコール命令が検出された場面であり、リターンアドレススタックＸの先頭のＸ−ＴＯＰに戻り先のアドレスとしてＡ＋８が格納され、リターンスタックポインタの値は−１されて−１となっている。また、コールヒットカウンタの値は、＋１されて１となっている。
【０１５８】
ここで、ブランチヒストリによりアドレスＣのリターン命令が検出されたとすると、リターンヒットテーブルの最下位ビットからコールヒットカウンタが示すビットの間に値が０のビットが存在するので、リターンアドレススタックＸの有効な最新のエントリであるＸ−ＴＯＰに格納された値、すなわちＡ＋８が分岐予測結果として取得される。Ａ＋８は、アドレスＣのリターン命令の分岐先として正しいアドレスである。
【０１５９】
図１９−２は、アドレスＣでリターン命令が検出された後の場面を示している。リターン命令の検出により、リターンアドレススタックＸではポップ動作がおこなわれ、Ｘ−ＴＯＰの情報は破棄されている。また、リターンスタックポインタの値は、＋１されて０となっている。リターンヒットテーブルではコールヒットカウンタが示しているＸＨ１のビットが１となり、対応する仮想のエントリが使用済みであることを記憶している。
【０１６０】
図１９−３は、続いてアドレスＡのコール命令の実行が完了した場面を示している。コール命令の実行の完了を受けて、リターンアドレススタックの先頭のＳＴＫ０に戻り先のアドレスＡ＋８が格納され、リターンスタックポインタの値は、＋１されて１となっている。また、コールヒットカウンタの値は、−１されて０となり、リターンヒットテーブルではシフト動作がおこなわれて最下位のビットが破棄されている。
【０１６１】
図１９−４は、続いてアドレスＤでコール命令が検出された場面を示している。コール命令の検出を受けて、リターンアドレススタックＸの先頭のＸ−ＴＯＰに戻り先のアドレスＤ＋８が格納され、リターンスタックポインタの値は、−１されて０となっている。また、コールヒットカウンタの値は、＋１されて１となっている。
【０１６２】
図１９−５は、続いてアドレスＦでコール命令が検出された場面を示している。コール命令の検出を受けて、リターンアドレススタックＸに戻り先のアドレスＦ＋８がプッシュされ、リターンスタックポインタの値は、−１されて−１となっている。また、コールヒットカウンタの値は、＋１されて２となっている。
【０１６３】
図１９−６は、続いてアドレスＨでコール命令が検出された場面を示している。コール命令の検出を受けて、リターンアドレススタックＸに戻り先のアドレスであるＨ＋８がプッシュされるが、既にエントリは２つとも埋まった状態であるため、古い情報であるＤ＋８がプッシュアウトされて消えてしまう。こうして、リターンアドレススタックＸは、Ｘ−ＴＯＰにＨ＋８が格納され、Ｘ−ＮＸＴにＦ＋８が格納された状態となる。また、リターンスタックポインタの値は、−１されて−２となり、コールヒットカウンタの値は、＋１されて３となっている。
【０１６４】
ここで、ブランチヒストリによりアドレスＪのリターン命令が検出されたとすると、リターンヒットテーブルの最下位ビットからコールヒットカウンタが示すビットの間に値が０のビットが存在するので、リターンアドレススタックＸの有効な最新のエントリであるＸ−ＴＯＰに格納された値、すなわちＨ＋８が分岐予測結果として取得される。Ｈ＋８は、アドレスＪのリターン命令の分岐先のアドレスとして正しいアドレスである。
【０１６５】
図１９−７は、アドレスＪでリターン命令が検出された後の場面を示している。リターン命令の検出により、リターンアドレススタックＸではポップ動作がおこなわれ、Ｘ−ＮＸＴの情報がＸ−ＴＯＰへ移動している。また、リターンスタックポインタの値は、＋１されて−１となっている。リターンヒットテーブルではコールヒットカウンタが示しているＸＨ３のビットが１となり、対応する仮想のエントリが使用済みであることを記憶している。
【０１６６】
ここで、ブランチヒストリによりアドレスＫのリターン命令が検出されたとすると、リターンヒットテーブルの最下位ビットからコールヒットカウンタが示すビットの間に値が０のビットが存在するので、リターンアドレススタックＸの有効な最新のエントリであるＸ−ＴＯＰに格納された値、すなわちＦ＋８が分岐予測結果として取得される。Ｆ＋８は、アドレスＫのリターン命令の分岐先のアドレスとして正しいアドレスである。
【０１６７】
図１９−８は、アドレスＫでリターン命令が検出された後の場面を示している。リターン命令の検出により、リターンアドレススタックＸではポップ動作がおこなわれ、Ｘ−ＴＯＰの情報は破棄されている。また、リターンスタックポインタの値は、＋１されて０となっている。リターンヒットテーブルではコールヒットカウンタが示しているＸＨ３のビットは既に１であるので、次のＸＨ２のビットが１となり、対応する仮想のエントリが使用済みであることを記憶している。
【０１６８】
ここで、ブランチヒストリによりアドレスＬのリターン命令が検出されたとすると、リターンヒットテーブルの最下位ビットからコールヒットカウンタが示すビットの間に値が０のビットが存在するので、リターンアドレススタックＸの最新エントリであるＸ−ＴＯＰからアドレス情報を取得しようとするが、Ｘ−ＴＯＰには既に情報が存在しないため取得することができない。この場合、リターンアドレススタックからアドレス情報を取得しても正しい分岐先のアドレスは取得できないため、ブランチヒストリの予測値を予測結果とする。
【０１６９】
ブランチヒストリが正しいアドレスを予測することができれば、分岐予測は成功する。同じ命令実行状況である図７−８の場面では、常に分岐予測が失敗するのに対し、本実施例に係る分岐予測方式では、ブランチヒストリを利用した分岐予測をおこなうことで分岐予測の精度を大幅に向上させることができる。
【０１７０】
図１９−９は、アドレスＬでリターン命令が検出された後の場面を示している。リターン命令の検出により、リターンアドレススタックＸではポップ動作がおこなわれている。また、リターンスタックポインタの値は、＋１されて１となっている。リターンヒットテーブルではＸＨ３のビットとＨＸ２のビットが既に１であるので、次のＸＨ１のビットが１となり、全ての仮想のエントリが使用済みであることを記憶している。
【０１７１】
もしも、アドレスＬのリターン命令が検出される前にアドレスＤのコール命令の実行が完了していたとすると、分岐予測の精度はさらに高くなる。アドレスＤのコール命令の実行が完了するには、アドレスＣのリターン命令の実行が完了している必要があるため、図１９−８の場面でアドレスＣのリターン命令の実行が完了したものとする。
【０１７２】
図１９−１０は、図１９−８の状況でアドレスＣのリターン命令の実行が完了した場面を示している。リターン命令の実行の完了を受けて、リターンアドレススタックではポップ動作がおこなわれて、先頭のＳＴＫ０の内容が破棄されている。また、リターンスタックポインタの値は、−１されて−１となっている。
【０１７３】
図１９−１１は、続いてアドレスＤのコール命令の実行が完了した場面を示している。コール命令の実行の完了を受けて、リターンアドレススタックの先頭のＳＴＫ０に戻り先のアドレスＤ＋８が格納され、リターンスタックポインタの値は、＋１されて０となっている。また、コールヒットカウンタの値は、−１されて２となり、リターンヒットテーブルではシフト動作がおこなわれて最下位のビットが破棄されている。
【０１７４】
ここで、ブランチヒストリによりアドレスＬのリターン命令が検出されたとすると、リターンヒットテーブルの最下位ビットからコールヒットカウンタが示すビットの間に値が０のビットが存在しないので、リターンスタックポインタが示すリターンアドレススタックのエントリであるＳＴＫ０に格納された値、すなわちＤ＋８が分岐予測結果として取得される。Ｄ＋８は、アドレスＬのリターン命令の分岐先のアドレスとして正しいアドレスである。
【０１７５】
このように、コール命令の実行が迅速に完了すれば、本実施例に係る分岐予測方式によって、リターンアドレススタックＸのエントリ数を増加させることなく、高い精度で分岐予測をおこなうことが可能となる。
【０１７６】
図１９−１２は、アドレスＬでリターン命令が検出された後の場面を示している。リターン命令の検出により、リターンアドレススタックＸではポップ動作がおこなわれている。また、リターンスタックポインタの値は、＋１されて１となっている。
【０１７７】
上述してきたように、本実施例２では、少数のビットからなる管理テーブルによって仮想のリターンアドレススタックＸのエントリの有効性を管理するように構成したので、実際のリターンアドレススタックＸのエントリ数を少なく抑えながら、高い精度で分岐予測をおこなうことができる。
【０１７８】
なお、本実施例においては、リターンヒットテーブルを最下位のビットから使用するものとして説明しているが、必ずしもこの通りの使い方をする必要はない。たとえば、最上位のビットから順に使用することも可能であり、スタックのような使い方をすることもできる。
【実施例３】
【０１７９】
実施例３で説明した分岐予測方式では、リターン命令の検出を契機として仮想エントリの管理テーブルのビットの更新をおこなったが、コール命令の検出を契機として仮想エントリの管理テーブルのビットの更新をおこなうように構成することもできる。本実施例では、コール命令の検出を契機として仮想エントリの管理テーブルのビットの更新をおこなう分岐予測方式について説明することとする。
【０１８０】
図２０は、本実施例に係る分岐予測方式の概要を説明するための説明図である。同図に示すように、本実施例に係る分岐予測方式では、Ｘバリッドテーブルとコールヒットカウンタを使用する。
【０１８１】
Ｘバリッドテーブルは、仮想のリターンアドレススタックＸの各エントリの有効性を管理するテーブルである。リターンヒットテーブルの各ビットは、仮想のリターンアドレススタックＸのエントリ一つに対応し、初期値として０をとる。そしてビットが０であれば、対応する仮想のエントリが無効であることを示し、ビットが１であれば対応する仮想のエントリが有効であることを示す。
【０１８２】
Ｘバリッドテーブルは、コール命令が検出されるたびに最下位のビットであるＸＶ１から順に１が設定され、リターン命令が検出されるたびに最上位の値が１であるビットが０にリセットされる。また、コール命令の実行が完了するたびにシフト動作により最下位のビットの値が捨てられる。コール命令の実行が完了すれば、リターン命令の戻り先のアドレスがリターンアドレススタックに格納されるため、仮想のリターンアドレススタックＸのエントリは不要となるためである。
【０１８３】
Ｘバリッドテーブルは、仮想のリターンアドレススタックＸのエントリごとに１ビットあればよいので、非常に低コストで実装することができる。たとえば、アドレス長が６４ビットあるとした場合、実際のリターンアドレススタックＸに８個のエントリを設けると６４×８で５１２ビットが必要になるが、Ｘバリッドテーブルは８ビットあれば済むことになる。
【０１８４】
コールヒットカウンタは初期値として０をとり、コール命令が検出されるたびに＋１され、コール命令の実行が完了するたびに−１される。したがって、コールヒットカウンタの値は、ブランチヒストリによって検出されているが、実行が完了していないコール命令の数、すなわち、値が格納されている仮想のリターンアドレススタックＸのエントリの数を表す。
【０１８５】
図２０では、コールヒットカウンタの値が５となっており、実行ユニットで実行が完了していないコール命令が５個あり、それらのコール命令に対応するリターン命令の戻り先のアドレスが仮想のリターンアドレススタックＸの５つのエントリに格納されていることを示している。
【０１８６】
それらのコール命令には、既に、対応するリターン命令がブランチヒストリによって検出されているものがある場合もある。図２０の例では、３番目と５番目のコール命令がこれに該当し、Ｘバリッドテーブルの対応するビットの値が０になっている。リターン命令が検出され、不要となったエントリであっても、コール命令実行完了時にシフトアウトする順序を保持するためにＸバリッドテーブルに対応するビットが保持される。
【０１８７】
実際のリターンアドレススタックＸは、コスト等の制約から２つのエントリのみを備えるものとする。このリターンアドレススタックＸにおいては、コール命令の検出時にリターン命令の戻り先のアドレスがプッシュされ、リターン命令の検出時にポップ動作によって最新のエントリの内容が破棄される。エントリが全て埋まっている状態でコール命令が検出された場合は、最も古いエントリの内容がプッシュアウトされて破棄される。
【０１８８】
図２０の例では、仮想のリターンアドレススタックＸには３つの有効なエントリが存在するが、実際のリターンアドレススタックＸには２つのエントリしか存在しないため、最も古いエントリの内容がプッシュアウトされている。しかし、Ｘバリッドテーブルには、本来リターンアドレススタックＸには３つのエントリが存在しているはずであることが記録されているため、実施例２の図７−８の場合のように誤ってリターンアドレススタックから分岐先のアドレスが取得されることを回避することができる。
【０１８９】
本実施例に係る分岐予測方式においては、ブランチヒストリでリターン命令が検出された場合に、コールヒットカウンタの値が１以上であればＸバリッドテーブルを調べる。そして、全ビット中に値が１のビットがひとつでも存在すれば、値が１である最も上位のビットの値を０へ変更し、実際のリターンアドレススタックＸの最新のエントリの内容を取得して分岐予測結果とする。
【０１９０】
プッシュアウトによりアドレス情報が破棄されていた場合、リターンアドレススタックＸの全てのエントリが無効化されていることがある。この場合には、リターンアドレススタックＸとリターンアドレススタックを用いた分岐予測をおこなうことはできないので、ブランチヒストリの予測結果を分岐予測結果として採用する。
【０１９１】
また、Ｘバリッドテーブルにおいて値が１のビットが一つも存在しなければ、仮想のリターンアドレススタックＸの全てのエントリが使用済みであることになるので、、リターンスタックポインタに従ってリターンアドレススタックから戻り先のアドレスを取得する。
【０１９２】
このように本実施例に係る分岐予測方式では、Ｘバリッドテーブルによって仮想のリターンアドレススタックＸの各エントリの有効性を管理するように構成したので、実際のリターンアドレススタックＸのエントリの数が少ない場合であっても、高い精度を保って分岐予測をおこなうことができる。
【０１９３】
次に、本実施例に係る分岐予測装置の構成について説明する。図２１は、本実施例に係る分岐予測装置の構成を示すブロック図である。命令フェッチ制御ユニット１１０〜アドレス生成リザベーションステーションについては、実施例１と同様であるので説明を省略する。
【０１９４】
分岐予測装置４００は、ブランチヒストリ４１０と、リターンアドレススタック４２０と、リターンアドレス演算回路４３０と、リターンアドレススタックＸ４４０と、リターンアドレス演算回路４５０と、コールヒットカウンタ４６０と、Ｘバリッドテーブル４７０と、リターンスタックポインタ４８０と、リターンアドレス選択回路４９１と、出力選択回路４９２とを有する。
【０１９５】
ブランチヒストリ４１０、リターンアドレススタック４２０、リターンアドレス演算回路４３０、リターンアドレススタックＸ４４０、リターンアドレス演算回路４５０、リターンスタックポインタ４８０、リターンアドレス選択回路４９１および出力選択回路４９２は、それぞれ、実施例２におけるブランチヒストリ３１０、リターンアドレススタック３２０、リターンアドレス演算回路３３０、リターンアドレススタックＸ３４０、リターンアドレス演算回路３５０、リターンスタックポインタ３８０、リターンアドレス選択回路３９１および出力選択回路３９２に対応し、同様の機能を有する。
【０１９６】
コールヒットカウンタ４６０は、Ｘバリッドテーブル４７０に対応する仮想のリターンアドレススタックＸの何番目のエントリまでアドレス情報がスタックされているかを保持する装置である。実施例２の図１０に示すように、コールヒットカウンタ４６０は、仮想のエントリ数を保持するのに十分なＫビットのラッチを有し、このラッチの保持している値をＣＡＬＬ＿ＨＩＴ＿ＣＴＲ信号として出力する。ラッチは初期化時に０に設定され、ブランチヒストリ３１０からのコールヒット信号がオンになるたびに＋１され、分岐リザベーションステーション１５０からのコール命令フラグがオンになるたびに−１される。
【０１９７】
また、実施例２の図１１に示すように、コールヒットカウンタ４６０から出力されるＣＡＬＬ＿ＨＩＴ＿ＣＴＲ信号は、デコーダによってデコードされて、ＣＴＲ＿ＥＱ＿０〜ＣＴＲ＿ＥＱ＿ｍのいずれかの信号一つをオンにする。たとえば、ＣＡＬＬ＿ＨＩＴ＿ＣＴＲ信号の値が０であればＣＴＲ＿ＥＱ＿０がオンになり、値がｍであればＣＴＲ＿ＥＱ＿ｍがオンになる。
【０１９８】
Ｘバリッドテーブル４７０は、対応する仮想のリターンアドレススタックＸのエントリの有効性を示すビットを保持する装置である。Ｘバリッドテーブル４７０の各ビットは、初期値が０であり、コール命令が検出され、対応する仮想のエントリに値が格納されたとみなされた場合に１が設定され、リターン命令が検出され、対応する仮想のエントリの値が予測に使用された場合に０にリセットされる。また、コール命令の実行が完了するたびに、最も古い仮想のエントリに対応するビットがシフトアウトされる。
【０１９９】
図２２は、Ｘバリッドテーブル４７０の回路構成を示す論理回路図である。同図に示すように、Ｘバリッドテーブル４７０は、ＸＶ１〜ＸＶｍのｍビットの情報を保持し、各ビットの値は、それぞれ、ＸＶ１＿ＳＥＴ〜ＸＶｍ＿ＳＥＴ信号によって制御される。たとえば、ｊビット目のＸＶｊのビットは、ＸＶｊ＿ＳＥＴ信号によって制御される。
【０２００】
このＸＶｊ＿ＳＥＴ信号は、ブランチヒストリ４１０からのコールヒット信号がオンとなったならば、その時点のコールヒットカウンタ４６０の値がｊ−１であった場合にオンとなり、Ｘバリッドテーブル４７０の対応するビットを１にする。すなわち、ブランチヒストリ４１０からのコールヒット信号がオンになった場合には、コールヒットカウンタ４６０が新たに示すことになるビットが１に更新されることになる。
【０２０１】
また、ＸＶｊ＿ＳＥＴ信号は、ブランチヒストリ４１０からのリターンヒット信号がオンとなったならば、その時点のコールヒットカウンタ３６０の値がｊより上位のビットが全て０であった場合にオフとなり、Ｘバリッドテーブル４７０の対応するビットを０にする。すなわち、ブランチヒストリ４１０からのリターンヒット信号がオンになった場合には、Ｘバリッドテーブル４７０の値が１である最上位のビットが０に更新される。
【０２０２】
このようにＸバリッドテーブル４７０の各ビットは、対応する仮想のリターンスタックＸのエントリに有効な値が存在している場合のみ１となり、その他の場合は１の値をとることになる。
【０２０３】
図２３は、Ｘバリッドテーブル４７０の出力部分の論理回路図である。同図に示すように、Ｘバリッドテーブル４７０から出力されるＵＳＥ＿Ｘ信号は、Ｘバリッドテーブル４７０の全てのビットの中に一つでも値が１であるビットが存在した場合にオンとなる。Ｘバリッドテーブル４７０に値が１のビットが存在するということは、仮想のリターンスタックＸのエントリに有効な値が存在していることを意味する。
【０２０４】
なお、リターンアドレススタック４２０と、リターンアドレススタック４４０と、コールヒットカウンタ４６０と、Ｘバリッドテーブル４７０と、リターンスタックポインタ４８０は、分岐予測が失敗した場合には初期状態にリセットされる。
【０２０５】
次に、本実施例に係る分岐予測装置の動作について、実施例２の図６の命令列を実行する場合を例にして説明する。図２４−１〜２４−９は、本実施例に係る分岐予測装置の動作を説明するための説明図である。なお、本実施例においては、Ｘバリッドテーブルの全てのビットが初期化時に０に設定されているものとする。
【０２０６】
図２４−１は、アドレスＡでコール命令が検出された場面であり、リターンアドレススタックＸの先頭のＸ−ＴＯＰに戻り先のアドレスとしてＡ＋８が格納され、リターンスタックポインタの値は−１されて−１となっている。また、コールヒットカウンタの値は、＋１されて１となり、コールヒットカウンタによって指し示されるＸバリッドテーブルのＸＶ１に１が設定されている。
【０２０７】
ここで、ブランチヒストリによりアドレスＣのリターン命令が検出されたとすると、Ｘバリッドテーブルに値が１のビットが存在するので、リターンアドレススタックＸの有効な最新のエントリであるＸ−ＴＯＰに格納された値、すなわちＡ＋８が分岐予測結果として取得される。Ａ＋８は、アドレスＣのリターン命令の分岐先として正しいアドレスである。
【０２０８】
図２４−２は、アドレスＣでリターン命令が検出された後の場面を示している。リターン命令の検出により、リターンアドレススタックＸではポップ動作がおこなわれ、Ｘ−ＴＯＰの情報は破棄されている。また、リターンスタックポインタの値は、＋１されて０となっている。Ｘバリッドテーブルではコールヒットカウンタが示しているＸＶ１のビットが０となり、対応する仮想のエントリが使用済みであることを記憶している。
【０２０９】
図２４−３は、続いてアドレスＡのコール命令の実行が完了した場面を示している。コール命令の実行の完了を受けて、リターンアドレススタックの先頭のＳＴＫ０に戻り先のアドレスＡ＋８が格納され、リターンスタックポインタの値は、＋１されて１となっている。また、コールヒットカウンタの値は、−１されて０となり、Ｘバリッドテーブルではシフト動作がおこなわれて最下位のビットが破棄されている。
【０２１０】
図２４−４は、続いてアドレスＤでコール命令が検出された場面を示している。コール命令の検出を受けて、リターンアドレススタックＸの先頭のＸ−ＴＯＰに戻り先のアドレスＤ＋８が格納され、リターンスタックポインタの値は、−１されて０となっている。また、コールヒットカウンタの値は、＋１されて１となり、コールヒットカウンタによって指し示されるＸバリッドテーブルのＸＶ１に１が設定されている。
【０２１１】
図２４−５は、続いてアドレスＦでコール命令が検出された場面を示している。コール命令の検出を受けて、リターンアドレススタックＸに戻り先のアドレスＦ＋８がプッシュされ、リターンスタックポインタの値は、−１されて−１となっている。また、コールヒットカウンタの値は、＋１されて２となり、コールヒットカウンタによって指し示されるＸバリッドテーブルのＸＶ２に１が設定されている。
【０２１２】
図２４−６は、続いてアドレスＨでコール命令が検出された場面を示している。コール命令の検出を受けて、リターンアドレススタックＸに戻り先のアドレスであるＨ＋８がプッシュされるが、既にエントリは２つとも埋まった状態であるため、古い情報であるＤ＋８がプッシュアウトされて消えてしまう。こうして、リターンアドレススタックＸは、Ｘ−ＴＯＰにＨ＋８が格納され、Ｘ−ＮＸＴにＦ＋８が格納された状態となる。また、リターンスタックポインタの値は、−１されて−２となり、コールヒットカウンタの値は、＋１されて３となり、コールヒットカウンタによって指し示されるＸバリッドテーブルのＸＶ３に１が設定されている。
【０２１３】
ここで、ブランチヒストリによりアドレスＪのリターン命令が検出されたとすると、Ｘバリッドテーブルに値が１のビットが存在するので、リターンアドレススタックＸの有効な最新のエントリであるＸ−ＴＯＰに格納された値、すなわちＨ＋８が分岐予測結果として取得される。Ｈ＋８は、アドレスＪのリターン命令の分岐先のアドレスとして正しいアドレスである。
【０２１４】
図２４−７は、アドレスＪでリターン命令が検出された後の場面を示している。リターン命令の検出により、リターンアドレススタックＸではポップ動作がおこなわれ、Ｘ−ＮＸＴの情報がＸ−ＴＯＰへ移動している。また、リターンスタックポインタの値は、＋１されて−１となっている。Ｘバリッドテーブルでは値が１である最上位のＸＶ３のビットが０となり、対応する仮想のエントリが使用済みであることを記憶している。
【０２１５】
ここで、ブランチヒストリによりアドレスＫのリターン命令が検出されたとすると、Ｘバリッドテーブルに値が１のビットが存在するので、リターンアドレススタックＸの有効な最新のエントリであるＸ−ＴＯＰに格納された値、すなわちＦ＋８が分岐予測結果として取得される。Ｆ＋８は、アドレスＫのリターン命令の分岐先のアドレスとして正しいアドレスである。
【０２１６】
図２４−８は、アドレスＫでリターン命令が検出された後の場面を示している。リターン命令の検出により、リターンアドレススタックＸではポップ動作がおこなわれ、Ｘ−ＴＯＰの情報は破棄されている。また、リターンスタックポインタの値は、＋１されて０となっている。Ｘバリッドテーブルでは値が１である最上位のＸＶ２のビットが０となり、対応する仮想のエントリが使用済みであることを記憶している。
【０２１７】
ここで、ブランチヒストリによりアドレスＬのリターン命令が検出されたとすると、Ｘバリッドテーブルに値が１のビットが存在するので、リターンアドレススタックＸの最新エントリであるＸ−ＴＯＰからアドレス情報を取得しようとするが、Ｘ−ＴＯＰには既に情報が存在しないため取得することができない。この場合、リターンアドレススタックからアドレス情報を取得しても正しい分岐先のアドレスは取得できないため、ブランチヒストリの予測値を予測結果とする。
【０２１８】
ブランチヒストリが正しいアドレスを予測することができれば、分岐予測は成功する。同じ命令実行状況である実施例２の図７−８の場面では、常に分岐予測が失敗するのに対し、本実施例に係る分岐予測方式では、ブランチヒストリを利用した分岐予測をおこなうことで分岐予測の精度を大幅に向上させることができる。
【０２１９】
図２４−９は、アドレスＬでリターン命令が検出された後の場面を示している。リターン命令の検出により、リターンアドレススタックＸではポップ動作がおこなわれている。また、リターンスタックポインタの値は、＋１されて１となっている。Ｘバリッドテーブルでは値が１である最上位のＸＶ１のビットが０となり、全ての仮想のエントリが使用済みであることを記憶している。
【０２２０】
なお、説明は省略するが、実施例２の場合と同様に、コール命令の実行が迅速に完了すれば、本実施例に係る分岐予測方式による分岐予測の精度はさらに高いものとなる。
【０２２１】
上述してきたように、本実施例３では、少数のビットからなる管理テーブルによって仮想のリターンアドレススタックＸのエントリの有効性を管理するように構成したので、実際のリターンアドレススタックＸのエントリ数を少なく抑えながら、高い精度で分岐予測をおこなうことができる。
【０２２２】
また、図１２と図２２を比較すれば分かるように、本実施例に係る分岐予測方式は、実施例２で説明した方式と同等の効果を、より簡略な仕組みで実現することができる。
【０２２３】
なお、本実施例においては、Ｘバリッドテーブルを最下位のビットから使用するものとして説明しているが、必ずしもこの通りの使い方をする必要はない。たとえば、最上位のビットから順に使用することも可能であり、スタックのような使い方をすることもできる。また、本実施例とはビットのオン／オフを逆にして実施することもできる。
【０２２４】
（付記１）パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測装置であって、
コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、この分岐命令の実行履歴情報を検索して分岐命令の存在と該分岐命令による分岐先を予測するブランチヒストリと、
サブルーチンのコール命令の実行が完了した場合に、該コール命令に対応するリターン命令の戻り先のアドレス情報を記憶する第１のリターンアドレススタックと、
前記ブランチヒストリによりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレス情報を記憶する第２のリターンアドレススタックと、
前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記第２のリターンアドレススタックにアドレス情報が保持されていれば、前記第２のリターンアドレススタックに保持されたアドレス情報を最優先で分岐予測結果として選択して出力する出力選択手段と
を備えたことを特徴とする分岐予測装置。
【０２２５】
（付記２）分岐予測が失敗した場合に、前記第２のアドレススタックの内容を全消去することを特徴とする付記１に記載の分岐予測装置。
【０２２６】
（付記３）前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記第２のリターンアドレススタックに複数のアドレス情報が保持されていれば、前記第２のリターンアドレススタックに最後に記憶された有効なアドレス情報を最優先で分岐予測結果として選択して出力することを特徴とする付記１または２に記載の分岐予測装置。
【０２２７】
（付記４）前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記第２のリターンアドレススタックにアドレス情報が保持されていなければ、前記第１のリターンアドレススタックに保持されたアドレス情報を最優先で分岐予測結果として選択して出力することを特徴とする付記１、２または３に記載の分岐予測装置。
【０２２８】
（付記５）前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記第１のリターンアドレススタックと前記第２のリターンアドレススタックのいずれにもアドレス情報が保持されていなければ、前記ブランチヒストリの予測結果を分岐予測結果として選択して出力することを特徴とする付記１〜４のいずれか一つに記載の分岐予測装置。
【０２２９】
（付記６）前記ブランチヒストリによって存在が予測されたコール命令が実行完了したか否かと、該コール命令に対応するリターン命令の分岐予測が完了しているか否かを保持するコール命令状況保持手段をさらに備えたことを特徴とする付記１〜５のいずれか一つに記載の分岐予測装置。
【０２３０】
（付記７）分岐予測が失敗した場合に、前記コール命令状況保持手段の内容を全消去することを特徴とする付記６に記載の分岐予測装置。
【０２３１】
（付記８）前記コール命令状況保持手段が状況を保持しているコール命令の数を保持するカウンタをさらに備えたことを特徴とする付記６または７に記載の分岐予測装置。
【０２３２】
（付記９）分岐予測が失敗した場合に、前記カウンタの内容を全消去することを特徴とする付記８に記載の分岐予測装置。
【０２３３】
（付記１０）前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記ブランチヒストリにより存在が予測されているが、実行が完了しておらず、かつ、対応するリターン命令の分岐予測が完了していないコール命令が存在することが前記コール命令状況保持手段によって判明した場合には、前記第２のリターンアドレススタックに保持されたアドレス情報を最優先で分岐予測結果として選択して出力することを特徴とする付記６〜９のいずれか一つに記載の分岐予測装置。
【０２３４】
（付記１１）前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記ブランチヒストリにより存在が予測されているが、実行が完了しておらず、かつ、対応するリターン命令の分岐予測が完了していないコール命令が存在することが前記コール命令状況保持手段によって判明したが、前記第２のリターンアドレススタックにアドレス情報が保持されていない場合には、前記ブランチヒストリの予測結果を分岐予測結果として選択して出力することを特徴とする付記１０に記載の分岐予測装置。
【０２３５】
（付記１２）前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記ブランチヒストリにより存在が予測されているが、実行が完了しておらず、かつ、対応するリターン命令の分岐予測が完了していないコール命令が存在しないことが前記コール命令状況保持手段によって判明した場合には、前記第１のリターンアドレススタックに保持されたアドレス情報を最優先で分岐予測結果として選択して出力することを特徴とする付記６〜１１のいずれか一つに記載の分岐予測装置。
【０２３６】
（付記１３）前記出力選択手段は、前記ブランチヒストリによりリターン命令の存在が予測された場合に、前記ブランチヒストリにより存在が予測されているが、実行が完了しておらず、かつ、対応するリターン命令の分岐予測が完了していないコール命令が存在しないことが前記コール命令状況保持手段によって判明し、前記第１のリターンアドレススタックにアドレス情報が保持されていない場合には、前記ブランチヒストリの予測結果を分岐予測結果として選択して出力することを特徴とする付記１２に記載の分岐予測装置。
【０２３７】
（付記１４）前記コール命令状況保持手段は、前記ブランチヒストリによって存在が予測されたコール命令の状況を命令毎にビットのオン／オフによって保持することを特徴とする付記６〜９のいずれか一つに記載の分岐予測装置。
【０２３８】
（付記１５）前記コール命令状況保持手段は、前記ブランチヒストリによってコール命令の存在が予測された場合に、管理対象のビット一つ追加して該ビットを０に設定し、前記ブランチヒストリによってリターン命令の存在が予測された場合には、管理対象のビットのうち値が０の最新のビットを１に変更し、いずれかのコール命令の実行が完了した場合には、最も古いビットを管理対象から外すことを特徴とする付記１４に記載の分岐予測装置。
【０２３９】
（付記１６）前記コール命令状況保持手段は、前記ブランチヒストリによってコール命令の存在が予測された場合に、管理対象のビット一つ追加して該ビットを１に設定し、前記ブランチヒストリによってリターン命令の存在が予測された場合には、管理対象のビットのうち値が１の最新のビットを０に変更し、いずれかのコール命令の実行が完了した場合には、最も古いビットを管理対象から外すことを特徴とする付記１４に記載の分岐予測装置。
【０２４０】
（付記１７）前記コール命令状況保持手段は、所有するビットを初期化時に全て０に設定し、前記ブランチヒストリによってコール命令の存在が予測された場合に、管理対象のビット一つ追加して該ビットを１に設定し、前記ブランチヒストリによってリターン命令の存在が予測された場合には、全ビットのうち値が１の最新のビットを０に変更し、いずれかのコール命令の実行が完了した場合には、最も古いビットを管理対象から外すことを特徴とする付記１４に記載の分岐予測装置。
【０２４１】
（付記１８）前記コール命令状況保持手段は、所有するビットを初期化時に全て１に設定し、前記ブランチヒストリによってコール命令の存在が予測された場合に、管理対象のビット一つ追加して該ビットを０に設定し、前記ブランチヒストリによってリターン命令の存在が予測された場合には、全ビットのうち値が０の最新のビットを１に変更し、いずれかのコール命令の実行が完了した場合には、最も古いビットを管理対象から外すことを特徴とする付記１４に記載の分岐予測装置。
【０２４２】
（付記１９）パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測方法であって、
コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶するブランチヒストリをもちいて、分岐命令の存在と該分岐命令による分岐先を予測する分岐命令予測工程と、
前記分岐命令予測工程によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレス情報を記憶手段に記憶する第一のリターンアドレス記憶工程と、
サブルーチンのコール命令の実行が完了した場合に、該コール命令に対応するリターン命令の戻り先のアドレス情報を記憶手段に記憶する第２のリターンアドレス記憶工程と、
前記分岐命令予測工程によりリターン命令の存在が予測された場合に、前記第２のリターンアドレス記憶工程より記憶されたアドレス情報が存在すれば、前記第１のリターンアドレス記憶工程により記憶されたアドレス情報を最優先で分岐予測結果として選択して出力する出力選択工程と
を含んだことを特徴とする分岐予測方法。
【産業上の利用可能性】
【０２４３】
以上のように、本発明にかかる分岐予測装置および分岐予測方法は、リターン命令の分岐予測に有用であり、特に、コール命令の実行完了に先行して複数のコール命令がブランチヒストリによって検出された場合に分岐予測の精度を高く保つことが必要な場合に適している。
【図面の簡単な説明】
【０２４４】
【図１】本実施例に係る分岐予測装置の動作を説明するための命令列を示すサンプル図である。
【図２−１】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２−２】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２−３】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２−４】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２−５】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図３】本実施例に係る分岐予測装置の構成を示すブロック図である。
【図４】図３に示したリターンアドレス選択回路の処理手順を示すフローチャートである。
【図５−１】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図５−２】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図５−３】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図６】本実施例に係る分岐予測装置の動作を説明するための命令列を示すサンプル図である。
【図７−１】従来の分岐予測装置の動作を説明するための説明図である。
【図７−２】従来の分岐予測装置の動作を説明するための説明図である。
【図７−３】従来の分岐予測装置の動作を説明するための説明図である。
【図７−４】従来の分岐予測装置の動作を説明するための説明図である。
【図７−５】従来の分岐予測装置の動作を説明するための説明図である。
【図７−６】従来の分岐予測装置の動作を説明するための説明図である。
【図７−７】従来の分岐予測装置の動作を説明するための説明図である。
【図７−８】従来の分岐予測装置の動作を説明するための説明図である。
【図８】本実施例に係る分岐予測方式の概要を説明するための説明図である。
【図９】本実施例に係る分岐予測装置の構成を示すブロック図である。
【図１０】コールヒットカウンタの回路構成を示す論理回路図である。
【図１１】コールヒットカウンタのデコーダ部分の論理回路図である。
【図１２】リターンヒットテーブルの回路構成を示す論理回路図である。
【図１３】リターンヒットテーブルの出力部分の回路構成を示す論理回路図である。
【図１４】リターンスタックポインタの回路構成を示す論理回路図である。
【図１５】リターンスタックポインタのデコーダ部分の論理回路図である。
【図１６】リターンアドレス選択回路と出力選択回路の回路構成を示す論理回路図である。
【図１７】リターンヒットテーブルの回路構成を示す論理回路図である。
【図１８】リターンヒットテーブルの出力部分の論理回路図である。
【図１９−１】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図１９−２】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図１９−３】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図１９−４】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図１９−５】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図１９−６】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図１９−７】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図１９−８】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図１９−９】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図１９−１０】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図１９−１１】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図１９−１２】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２０】本実施例に係る分岐予測方式の概要を説明するための説明図である。
【図２１】本実施例に係る分岐予測装置の構成を示すブロック図である。
【図２２】Ｘバリッドテーブルの回路構成を示す論理回路図である。
【図２３】Ｘバリッドテーブルの出力部分の論理回路図である。
【図２４−１】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２４−２】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２４−３】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２４−４】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２４−５】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２４−６】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２４−７】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２４−８】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【図２４−９】本実施例に係る分岐予測装置の動作を説明するための説明図である。
【符号の説明】
【０２４５】
１１０    命令フェッチ制御ユニット
１２０    キャッシュ制御ユニット
１３０    命令バッファ
１４０    デコーダ
１５０    分岐レザベーションステーション
１６０    整数演算レザベーションステーション
１７０    浮動小数演算レザベーションステーション
１８０    アドレス生成レザベーションステーション
２００    分岐予測装置
２１０    ブランチヒストリ
２２０    リターンアドレススタック
２３０    リターンアドレス演算回路
２４０    リターンアドレススタックＸ
２５０    バリッド制御回路
２６０    リターンアドレス演算回路
２７０    リターンスタックポインタ
２８１    リターンアドレス選択回路
２８２    出力選択回路
３００    分岐予測装置
３１０    ブランチヒストリ
３２０    リターンアドレススタック
３３０    リターンアドレス演算回路
３４０    リターンアドレススタックＸ
３５０    リターンアドレス演算回路
３６０    コールヒットカウンタ
３７０    リターンヒットテーブル
３８０    リターンスタックポインタ
３９１    リターンアドレス選択回路
３９２    出力選択回路
４００    分岐予測装置
４１０    ブランチヒストリ
４２０    リターンアドレススタック
４３０    リターンアドレス演算回路
４４０    リターンアドレススタックＸ
４５０    リターンアドレス演算回路
４６０    コールヒットカウンタ
４７０    リターンヒットテーブル
４８０    リターンスタックポインタ
４９１    リターンアドレス選択回路
４９２    出力選択回路
【図１】
2006155374.tif 000003
【図２−１】
2006155374.tif 000004
【図２−２】
2006155374.tif 000005
【図２−３】
2006155374.tif 000006
【図２−４】
2006155374.tif 000007
【図２−５】
2006155374.tif 000008
【図３】
2006155374.tif 000009
【図４】
2006155374.tif 000010
【図５−１】
2006155374.tif 000011
【図５−２】
2006155374.tif 000012
【図５−３】
2006155374.tif 000013
【図６】
2006155374.tif 000014
【図７−１】
2006155374.tif 000015
【図７−２】
2006155374.tif 000016
【図７−３】
2006155374.tif 000017
【図７−４】
2006155374.tif 000018
【図７−５】
2006155374.tif 000019
【図７−６】
2006155374.tif 000020
【図７−７】
2006155374.tif 000021
【図７−８】
2006155374.tif 000022
【図８】
2006155374.tif 000023
【図９】
2006155374.tif 000024
【図１０】
2006155374.tif 000025
【図１１】
2006155374.tif 000026
【図１２】
2006155374.tif 000027
【図１３】
2006155374.tif 000028
【図１４】
2006155374.tif 000029
【図１５】
2006155374.tif 000030
【図１６】
2006155374.tif 000031
【図１７】
2006155374.tif 000032
【図１８】
2006155374.tif 000033
【図１９−１】
2006155374.tif 000034
【図１９−２】
2006155374.tif 000035
【図１９−３】
2006155374.tif 000036
【図１９−４】
2006155374.tif 000037
【図１９−５】
2006155374.tif 000038
【図１９−６】
2006155374.tif 000039
【図１９−７】
2006155374.tif 000040
【図１９−８】
2006155374.tif 000041
【図１９−９】
2006155374.tif 000042
【図１９−１０】
2006155374.tif 000043
【図１９−１１】
2006155374.tif 000044
【図１９−１２】
2006155374.tif 000045
【図２０】
2006155374.tif 000046
【図２１】
2006155374.tif 000047
【図２２】
2006155374.tif 000048
【図２３】
2006155374.tif 000049
【図２４−１】
2006155374.tif 000050
【図２４−２】
2006155374.tif 000051
【図２４−３】
2006155374.tif 000052
【図２４−４】
2006155374.tif 000053
【図２４−５】
2006155374.tif 000054
【図２４−６】
2006155374.tif 000055
【図２４−７】
2006155374.tif 000056
【図２４−８】
2006155374.tif 000057
【図２４−９】
2006155374.tif 000058