(57)【要約】【課題】予測精度の高い分岐予測装置および分岐予測方法を得ること。【解決手段】ブランチヒストリ２１０がコール命令の存在を検出した時点でリターンアドレススタックＸ２４０にそのコール命令に対応するリターン命令の戻り先のアドレスを格納する。分岐リザベーションステーション１５０にてコール命令の実行が完了する前にブランチヒストリ２１０がリターン命令の存在を検出した場合は、リターンアドレススタック２２０にリターン命令の戻り先のアドレスが格納されないが、この場合、出力選択回路２８０は、リターンアドレススタックＸ２４０に格納された情報を用いて正しい戻り先を予測する。【選択図】        図３
2006040173.tif 000002
【特許請求の範囲】
【請求項１】
パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測装置であって、
コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、前記分岐命令の実行履歴情報を基にして分岐予測をおこなう分岐予測手段と、
前記分岐予測手段によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する第１の戻り先アドレス記憶手段と、
サブルーチンのコール命令が実行された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する第２の戻り先アドレス記憶手段と、
前記分岐予測手段が保持している情報と、前期第１の戻り先アドレス記憶手段が保持している情報と、前期第２の戻り先アドレス記憶手段と手段が保持している情報とから適切な分岐予測結果を選択して出力する出力選択手段と
を備えたことを特徴とする分岐予測装置。
【請求項２】
前期第１の戻り先アドレス記憶手段の各エントリと前期第２の戻り先アドレス記憶手段の各エントリのいずれか一つをその時点における有効なエントリとして指定する有効エントリ指定手段をさらに備え、
前記出力選択手段は、前記分岐予測手段がリターン命令の存在を予測した場合に前記有効エントリ指定手段が示しているエントリの情報を該リターン命令の戻り先のアドレスとして出力することを特徴とする請求項１に記載の分岐予測装置。
【請求項３】
前記有効エントリ指定手段は、前記分岐予測手段がコール命令の存在を予測したならば、前期第１の戻り先アドレス記憶手段のエントリを有効なエントリとして指定することを特徴とする請求項２に記載の分岐予測装置。
【請求項４】
前記有効エントリ指定手段は、コール命令の実行が完了するか、もしくは、前記分岐予測手段がリターン命令の存在を予測したならば、前期第２の戻り先アドレス記憶手段のエントリを有効なエントリとして指定することを特徴とする請求項２または３に記載の分岐予測装置。
【請求項５】
前期第１の戻り先アドレス記憶手段の各エントリが有するバリッドビットを制御し、該エントリに格納された情報が有効であるか否かを前記出力選択手段が判断できるようにするバリッド制御手段をさらに備えたことを特徴とする請求項１〜４のいずれか一つに記載の分岐予測装置。
【請求項６】
前期バリッド制御手段は、前記分岐予測手段がコール命令の存在を予測したならば、前期第１の戻り先アドレス記憶手段のエントリを有効とすることを特徴とする請求項５に記載の分岐予測装置。
【請求項７】
前期バリッド制御手段は、コール命令の実行が完了するか、もしくは、前記分岐予測手段がリターン命令の存在を予測したならば、前期第１の戻り先アドレス記憶手段のエントリを無効とすることを特徴とする請求項５または６に記載の分岐予測装置。
【請求項８】
パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測装置であって、
コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、前記分岐命令の実行履歴情報を基にして分岐予測をおこなう分岐予測手段と、
前記分岐予測手段によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する戻り先アドレス記憶手段と、
前記分岐予測手段が保持している情報と、戻り先アドレス記憶手段と手段が保持している情報とから適切な分岐予測結果を選択して出力する出力選択手段と
を備えたことを特徴とする分岐予測装置。
【請求項９】
パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測方法であって、
コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、前記分岐命令の実行履歴情報を基にして分岐予測をおこなう分岐予測工程と、
前記分岐予測工程によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する第１の戻り先アドレス記憶工程と、
サブルーチンのコール命令が実行された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する第２の戻り先アドレス記憶工程と、
前記分岐予測工程が保持している情報と、前期第１の戻り先アドレス記憶工程が保持している情報と、前期第２の戻り先アドレス記憶工程と工程が保持している情報とから適切な分岐予測結果を選択して出力する出力選択工程と
を含んだことを特徴とする分岐予測方法。
【請求項１０】
パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測方法であって、
コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、前記分岐命令の実行履歴情報を基にして分岐予測をおこなう分岐予測工程と、
前記分岐予測工程によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する戻り先アドレス記憶工程と、
前記分岐予測工程が保持している情報と、戻り先アドレス記憶工程と工程が保持している情報とから適切な分岐予測結果を選択して出力する出力選択工程と
を含んだことを特徴とする分岐予測方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測装置および分岐予測方法に関し、特にリターン命令の分岐先の予測精度を向上させることができる分岐予測装置および分岐予測方法に関するものである。
【背景技術】
【０００２】
従来より、パイプライン方式のプロセッサにおいては、処理の高速化のために分岐予測の手法が広く用いられている。本来、プログラム中に分岐が存在する場合、分岐が確定するまでパイプラインを停止する必要があるが、分岐予測をおこなうプロセッサは、分岐を予測し、予測した分岐後の命令を投機的に実行する。
【０００３】
分岐予測には、予測が当たった場合、分岐が確定するのを待つ分の処理時間を短縮することができるという大きなメリットがあるが、予測がはずれた場合は、パイプラインをフラッシュして分岐命令の部分から処理を再実行する必要がありペナルティも大きい。このため、分岐予測においては、予測の精度が非常に重要となっている。
【０００４】
分岐予測には、一般的には、ブランチヒストリが用いられる。ブランチヒストリは、過去に実行した分岐命令のアドレスとその分岐命令により分岐した分岐先のアドレスとを対にして履歴として保持する装置である。ブランチヒストリを用いた分岐予測は、過去の履歴に基づいたものであるため、ループ処理のように同じ分岐が繰り返される場合に効果的であるが、サブルーチンからのリターン命令に対しては有効性が低い。
【０００５】
サブルーチンからのリターン命令により分岐する場合、分岐先は、サブルーチンのコール命令の次の命令となる。だが、一般的に、サブルーチンはプログラムの各所から呼び出されるため、リターン命令の戻り先は一定ではない。したがって、過去の履歴にしたがって分岐先を予測しても、予測が正しいとは限らない。
【０００６】
そこで、特許文献１では、サブルーチンのコール命令の実行時にリターン命令による戻り先のアドレスをリターンスアドレスタックに格納しておき、リターン命令については、ブランチヒストリよりリターンアドレススタックを優先して分岐予測をおこなうことで予測の精度を高める技術が開示されている。
【０００７】
【特許文献１】特開２００１−１７２５０７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、特許文献１に開示された技術は、コール命令の実行が完了した後にリターンスアドレスタックにそのコール命令に対応するリターン命令の戻り先のアドレスを格納するものであるため、命令列の先読み等により、コール命令の実行が完了する前にリターン命令がブランチヒストリによって検出された場合には、リターンスアドレスタックには戻り先のアドレスが格納されていないことになる。
【０００９】
この場合、ブランチヒストリに格納されている前回の戻り先が今回の戻り先として予測されるが、既に述べた通り、リターン命令に関してはブランチヒストリに基づいた予測の精度は高くない。このように、特許文献１に開示された技術には、リターン命令の検出タイミングによっては分岐予測の精度が低下するという問題が含まれている。
【００１０】
この発明は、上述した従来技術による問題点を解消するためになされたものであり、リターン命令による分岐先を高い精度で予測することができる分岐予測装置および分岐予測方法を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上述した課題を解決し、目的を達成するため、本発明は、パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測装置であって、コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、前記分岐命令の実行履歴情報を基にして分岐予測をおこなう分岐予測手段と、前記分岐予測手段によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する第１の戻り先アドレス記憶手段と、サブルーチンのコール命令が実行された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する第２の戻り先アドレス記憶手段と、前記分岐予測手段が保持している情報と、前期第１の戻り先アドレス記憶手段が保持している情報と、前期第２の戻り先アドレス記憶手段と手段が保持している情報とから適切な分岐予測結果を選択して出力する出力選択手段とを備えたことを特徴とする。
【００１２】
また、本発明は、パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測方法であって、コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、前記分岐命令の実行履歴情報を基にして分岐予測をおこなう分岐予測工程と、前記分岐予測工程によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する第１の戻り先アドレス記憶工程と、サブルーチンのコール命令が実行された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する第２の戻り先アドレス記憶工程と、前記分岐予測工程が保持している情報と、前期第１の戻り先アドレス記憶工程が保持している情報と、前期第２の戻り先アドレス記憶工程と工程が保持している情報とから適切な分岐予測結果を選択して出力する出力選択工程とを含んだことを特徴とする。
【００１３】
この発明によれば、分岐予測手段においてコール命令の存在が予測された場合に、コール命令が実行されるまでは第１の戻り先アドレス記憶手段をもちいて、コール命令が実行された後は第２の戻り先アドレス記憶手段をもちいてリターン命令の戻り先を予測するように構成したので、常に高い精度でリターン命令の戻り先を予測することができる。
【００１４】
また、本発明は、パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測装置であって、コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、前記分岐命令の実行履歴情報を基にして分岐予測をおこなう分岐予測手段と、前記分岐予測手段によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する戻り先アドレス記憶手段と、前記分岐予測手段が保持している情報と、戻り先アドレス記憶手段と手段が保持している情報とから適切な分岐予測結果を選択して出力する出力選択手段とを備えたことを特徴とする。
【００１５】
また、本発明は、パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測方法であって、コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、前記分岐命令の実行履歴情報を基にして分岐予測をおこなう分岐予測工程と、前記分岐予測工程によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する戻り先アドレス記憶工程と、前記分岐予測工程が保持している情報と、戻り先アドレス記憶工程と工程が保持している情報とから適切な分岐予測結果を選択して出力する出力選択工程とを含んだことを特徴とする。
【００１６】
この発明によれば、分岐予測手段においてコール命令の存在が予測された場合に、そのコール命令に対応するリターン命令の戻り先のアドレスを記憶しておき、分岐予測手段がリターン命令の存在を予測した場合は記憶していたアドレスをリターン命令の戻り先と予測するように構成したので、高い精度でリターン命令の戻り先を予測することができる。
【発明の効果】
【００１７】
本発明によれば、分岐予測手段においてコール命令の存在が予測された場合に、コール命令が実行されるまでは第１の戻り先アドレス記憶手段をもちいて、コール命令が実行された後は第２の戻り先アドレス記憶手段をもちいてリターン命令の戻り先を予測するように構成したので、常に高い精度でリターン命令の戻り先を予測することができるという効果を奏する。
【００１８】
また、本発明によれば、分岐予測手段においてコール命令の存在が予測された場合に、そのコール命令に対応するリターン命令の戻り先のアドレスを記憶しておき、分岐予測手段がリターン命令の存在を予測した場合は記憶していたアドレスをリターン命令の戻り先と予測するように構成したので、高い精度でリターン命令の戻り先を予測することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１９】
以下に添付図面を参照して、この発明に係る分岐予測装置および分岐予測方法の好適な実施の形態を詳細に説明する。
【実施例１】
【００２０】
まず、本実施例に係る分岐予測方式の原理について従来技術による分岐予測方式と比較して説明する。図１は、本実施例に係る分岐予測方式の原理を説明するためにもちいるプログラムの説明図である。
【００２１】
同図に示すように、このプログラムは、アドレスαにおいてサブルーチンＡを呼び出すためのコール命令を実行する（ステップＳ１０１）。サブルーチンＡは、アドレスδのリターン命令により終了し、プログラムは、メインルーチンのアドレスα＋８に戻って処理を継続する（ステップＳ１０２）。
【００２２】
ここで、戻り先がα＋８となるのは、このプログラムを実行するプロセッサの命令長が４バイトであり、分岐命令の後に必ず遅延命令をともなうためである。したがって、プロセッサの種類が異なる場合は、アドレスの増分は＋８とは異なる値になる場合もある。
【００２３】
プログラムは、アドレスβにて再びサブルーチンＡを呼び出すためのコール命令を実行する（ステップＳ１０３）。サブルーチンＡは、アドレスδのリターン命令により終了し、プログラムは、今回は、メインルーチンのアドレスβ＋８に戻って処理を継続する（ステップＳ１０４）。
【００２４】
このようにリターン命令による分岐先は、サブルーチンの呼び出し元によって変わるため、過去の分岐の履歴であるブランチヒストリによるリターン命令の分岐先の予測は精度の低いものになってしまう。
【００２５】
図２０は、従来の分岐予測方式による一つ目のリターン命令検出時の分岐予測について説明するための説明図である。同図に示すように、特許文献１が開示している従来技術においては、リターン命令の戻り先の予測精度を高めるためにリターンアドレススタック２２０をもちいている。
【００２６】
この従来の分岐予測方式においては、分岐リザベーションステーション１５０でコール命令が実行されると、リターンアドレススタック２２０にコール命令のアドレスに＋８したアドレスがリターン命令の戻り先のアドレスとして格納される。
【００２７】
そして、ブランチヒストリ２１０は、リターン命令を検出するとリターンヒット信号をオンにし、リターン命令の戻り先のアドレスをブランチヒストリ２１０からではなくリターンアドレススタック２２０から取得するように出力選択回路２８０に対して指示する。
【００２８】
図２０は、図１に示したプログラムのステップＳ１０２の場面を示しているが、リターンアドレススタック２２０には、アドレスαのコール命令で呼び出されたサブルーチンＡのリターン命令の戻り先のアドレスとしてα＋８が格納されている。そして、ブランチヒストリ２１０がアドレスδにリターン命令が存在することを検出したことに対応して、出力選択回路２８０がリターン命令の戻り先のアドレスとしてα＋８を正しく選択できている。
【００２９】
図２１は、従来の分岐予測方式による二つ目のリターン命令検出時の分岐予測について説明するための説明図である。同図は、図１に示したプログラムのステップＳ１０４の場面を示している。図２０の場面では、アドレスδのリターン命令の戻り先のアドレスはα＋８であったが、この場面では戻り先のアドレスはβ＋８である。
【００３０】
ブランチヒストリ２１０は、前回のδのリターン命令の戻り先のアドレスとしてα＋８を保持しているが、βのコール命令の実行が完了していれば、リターンアドレススタック２２０にβ＋８が格納され、これがリターン命令の戻り先のアドレスとしてもちいられるため問題はない。
【００３１】
しかし、命令フェッチ制御ユニット１１０による命令の先読み等により、βのコール命令の実行が完了する前にδのリターン命令の存在がブランチヒストリ２１０によって検出されてしまう場合がある。この場合、図２２に示すように、リターンアドレススタック２２０には有効な戻り先のアドレスが格納されておらず、ブランチヒストリのα＋８がアドレスδのリターン命令の戻り先のアドレスとして予測されてしまうため、予測ははずれてしまうことになる。
【００３２】
このように、リターンアドレススタック２２０を設け、コール命令の実行後にそのコール命令の次の命令のアドレスをリターンアドレススタック２２０に格納しておくことにより、多くの場合においてリターン命令の検出時に正しい戻り先のアドレスを予測することが可能になるが、この従来の分岐予測方式には改善の余地が残されている。
【００３３】
図２は、本実施例に係る分岐予測方式による二つ目のリターン命令検出時の分岐予測について説明するための説明図である。同図に示すように、本実施例に係る分岐予測方式は、リターンアドレススタック２２０以外にもうひとつ別のリターンアドレススタック（以下、「リターンアドレススタックＸ」と言う。）をもちいる。
【００３４】
本実施例に係る分岐予測方式においては、ブランチヒストリ２１０でコール命令が検出されると、リターンアドレススタックＸ２４０にコール命令のアドレスに＋８したアドレスがリターン命令の戻り先のアドレスとして格納される。
【００３５】
ブランチヒストリ２１０でコール命令が検出されるタイミングは、このコール命令に対応するリターン命令が検出されるタイミングよりも早いため、図２２のような場面であってもリターンアドレススタックＸ２４０に格納された値をもちいてリターン命令による分岐先のアドレスを正しく予測することができる。
【００３６】
図２では、アドレスβのコール命令がブランチヒストリ２１０に検出された時点で、リターンアドレススタックＸ２４０にβ＋８がリターン命令の戻り先のアドレスとして格納されている。そのため、アドレスβのコール命令の実行完了前に、ブランチヒストリ２１０によってδのリターン命令が検出されても、このリターンアドレススタックＸ２４０に格納された値をもちいることで、戻り先のアドレスを正しく予測することができている。
【００３７】
このように、リターンアドレススタックＸ２４０をもちいることにより、リターン命令による分岐先の予測の精度を改善することができ、もってプロセッサの性能を向上させることができる。
【００３８】
次に、本実施例に係る分岐予測装置の構成について説明する。図３は、本実施例に係る分岐予測装置の構成を示すブロック図である。同図に示すように、分岐予測装置２００は、命令フェッチ制御ユニット１１０と、分岐リザベーションユニット１５０と接続された構成をとる。
【００３９】
命令フェッチ制御ユニット１１０は、パイプラインで実行する命令の取得を制御するユニットである。命令フェッチ制御ユニット１１０による命令の取得要求は、実際の命令取得のためにキャッシュ制御ユニット１２０に送出されるとともに、分岐予測のために分岐予測装置２００内のブランチヒストリ２１０に対しても送出される。
【００４０】
キャッシュ制御ユニット１２０は、命令フェッチ制御ユニット１１０から要求された命令をキャッシュもしくは主記憶から取得するユニットである。キャッシュ制御ユニット１２０により取得された命令は、命令バッファ１３０に一時的に格納された後、デコーダ１４０によりデコードされ、命令の種類に応じたリザベーションステーションに送られる。
【００４１】
リザベーションステーションには、分岐リザベーションステーション１５０、整数演算リザベーションステーション１６０、浮動少数演算リザベーションステーション１７０、アドレス生成リザベーションステーション１８０などがあり、分岐命令は分岐リザベーションステーション１５０に送られてここで実行される。
【００４２】
分岐予測装置２００は、ブランチヒストリ２１０と、リターンアドレススタック２２０と、リターンアドレス演算回路２３０と、リターンアドレススタックＸ２４０と、バリッド制御回路２５０と、リターンアドレス演算回路２６０と、リターンスタックポインタ２７０と、出力選択回路２８０とを有する。
【００４３】
ブランチヒストリ２１０は、分岐リザベーションステーション１５０にて実行された分岐命令のアドレスとその命令による分岐先を対にして、その他の情報フラグとともに記憶しておく装置である。コール命令やリターン命令も分岐命令の一種であり、その分岐結果がブランチヒストリ２１０に記憶される。
【００４４】
また、ブランチヒストリ２１０は、命令フェッチ制御ユニット１１０から命令のアドレスを取得すると、自身の情報を参照して、そのアドレスに含まれる命令によって分岐が発生するか否かを判断する。そして、分岐が発生すると判断した場合には、出力選択回路２８０に対して分岐先のアドレス等の情報を送出する。
【００４５】
リターンアドレススタック２２０は、分岐リザベーションステーション１５０にて実行されたコール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶しておく装置である。リターンアドレススタック２２０の各エントリは、エントリの有効性を示すバリッドビットを備える。なお、本実施例においては、リターンアドレススタック２２０は４つのエントリからなるものとして説明するが、エントリの数は必ずしも４つである必要はない。
【００４６】
リターンアドレス演算回路２３０は、分岐リザベーションステーション１５０から伝えられたコール命令のアドレスをリターン命令の戻り先のアドレスへ変換する演算をおこない、リターンアドレススタック２２０へ送出する回路である。既に説明した通り、本実施例で説明しているプロセッサにおいては、コール命令のアドレスに＋８したものがリターン命令の戻り先のアドレスとなるが、他の仕様のプロセッサにおいては変換方式が異なる場合もある。
【００４７】
リターンアドレススタックＸ２４０は、ブランチヒストリ２１０にてコール命令が検出された場合に、そのコール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶しておく装置である。リターンアドレススタックＸ２４０の各エントリは、エントリの有効性を示すバリッドビットを備える。なお、本実施例においては、リターンアドレススタックＸ２４０は一つのエントリからなることを前提として説明するが、エントリの数は複数であってもよい。
【００４８】
バリッド制御回路２５０は、リターンアドレススタックＸ２４０のエントリのバリッドビットの状態を制御する回路である。バリッド制御回路２５０は、ブランチヒストリ２１０からのコールヒット信号等の状態に応じて、リターンアドレススタックＸ２４０のエントリのバリッドビットの状態を変更する。
【００４９】
図４は、図３に示したバリッド制御回路２５０の構成を示すブロック図である。同図に示すように、バリッド制御回路２５０は、ブランチヒストリ２１０からのコールヒット信号がオンであり、かつ、リターンスタックポインタ２７０の値が１１１の場合にリターンアドレススタック２４０のエントリのバリッドビットの状態をオンに変更する。
【００５０】
また、バリッド制御回路２５０は、ブランチヒストリ２１０からのリターンヒット信号がオンになるか、もしくは、分岐リザベーションステーション１５０からのコール命令フラグがオンになった場合にバリッドビットの状態をオフに変更する。ブランチヒストリ２１０でリターン命令が検出されれば、リターンアドレススタックＸ２４０のエントリの情報は既に使用済みになっており、分岐リザベーションステーション１５０でコール命令の実行が完了すれば、リターンアドレススタック２２０の情報が有効になっているためである。
【００５１】
リターンアドレス演算回路２６０は、ブランチヒストリ２１０が検出したコール命令のアドレスをリターン命令の戻り先のアドレスへ変換する演算をおこない、リターンアドレススタックＸ２４０へ送出する回路である。リターンアドレス演算回路２３０の場合と同様に、本実施例で説明しているプロセッサにおいては、コール命令のアドレスに＋８したものがリターン命令の戻り先のアドレスとなるが、他の仕様のプロセッサにおいては変換方式が異なる場合もある。
【００５２】
リターンスタックポインタ２７０は、リターン命令が検出された場合に使用すべきリターンアドレススタックのエントリを示す値を保持する装置である。具体的には、リターンスタックポインタ２７０保持する値が０００、００１、０１０、０１１である場合は、それぞれリターンアドレススタック２２０のＳＴＫ０、ＳＴＫ１、ＳＴＫ２、ＳＴＫ３のエントリを使用すべきことを意味する。また、値が１１１である場合は、リターンアドレススタックＸ２４０のエントリを使用すべきことを意味する。
【００５３】
図５は、図３に示したリターンスタックポインタ２７０の構成を示すブロック図である。同図に示すように、リターンスタックポインタ２７０は、＜２：０＞の３ビットからなるラッチを有し、このラッチの状態に応じた信号がオンになって送出されるようになっている。
【００５４】
ラッチの値は初期状態では０００であり、分岐リザベーションステーション１５０からコール完了信号がオンになるたびに＋１され、リターン完了信号がオンになるたびに−１される。また、ブランチヒストリ２１０からのコールヒット信号がオンになるたびに−１され、リターンヒット信号がオンになるたびに＋１される。
【００５５】
なお、リターンスタックポインタ２７０のラッチのビット数は、リターンアドレススタック２２０およびリターンアドレススタックＸ２４０のエントリが増えた場合には、それらのエントリを特定できるだけの幅に増やすものとする。
【００５６】
出力選択回路２８０は、複数の分岐情報から適切なものを選択して命令フェッチ制御ユニット１１０へ送出する回路である。具体的には、ブランチヒストリ２１０がリターン命令を検出した場合は、リターンスタックポインタ２７０が示すエントリのアドレスをリターン命令の戻り先のアドレスとして送出する。
【００５７】
図６は、図３に示した出力選択回路２８０の構成を示すブロック図である。同図に示すように、出力選択回路２８０は、２つのセレクタを有する。第１のセレクタは、リターンスタックポインタ２７０の値と各エントリのバリッドビットの状態を基にして、リターンアドレススタック２２０およびリターンアドレススタックＸ２４０のエントリから有効なエントリを選択する回路である。
【００５８】
第２のセレクタは、ブランチヒストリ２１０からのリターンヒット信号が有効であるか否かを判定し、これが有効な場合は第１のセレクタの選択結果を分岐先のアドレスとして選択し、有効でない場合にはブランチヒストリ２１０の予測したアドレスを分岐先のアドレスとして選択する回路である。
【００５９】
次に、図３に示した分岐予測装置２００の具体的な動作について説明する。図７は、図３に示した分岐予測装置２００の動作を説明するためにもちいるプログラムの説明図である。
【００６０】
同図に示すように、このプログラムは、アドレスαにおいてサブルーチンＡを呼び出すためのコール命令を実行する（ステップＳ２０１）。さらに、サブルーチンＡは、アドレスγ＋１２においてサブルーチンＢを呼び出すためのコール命令を実行する（ステップＳ２０２）。
【００６１】
サブルーチンＢは、アドレスηのリターン命令により終了し、プログラムは、サブルーチンＡのアドレスγ＋２０に戻る（ステップＳ２０３）。そして、サブルーチンＡは、アドレスδのリターン命令により終了し、プログラムは、メインルーチンのアドレスα＋８に戻って処理を継続する（ステップＳ２０４）。
【００６２】
図８は、図３に示した分岐予測装置２００のＳ２０１におけるコール命令フェッチ時の動作を説明するための説明図である。同図に示すように、命令フェッチユニット１１０は、命令を取得する旨の指示をキャッシュ制御ユニット１２０へ送るのと同時に、ブランチヒストリ２１０に対してその命令のアドレスを送出する。
【００６３】
ブランチヒストリ２１０は、自身の保持している分岐履歴を参照し、送出されたアドレスαにコール命令が存在することを検出したならば、コールヒット信号をオンにし、さらに、リターンアドレス演算回路２６０に対してコール命令の存在を検出したアドレスαを送出する。
【００６４】
リターンアドレス演算回路２６０は、受け取ったアドレスをリターン命令の戻り先のアドレスに変換した値をリターンアドレススタックＸ２４０に送出し、この値がリターンアドレススタックＸ２４０のエントリに記憶される。
【００６５】
また、ブランチヒストリ２１０からのコールヒット信号がオンになり、かつリターンスタックポインタ２７０の値が０００であることから、リターンアドレススタックＸ２４０のエントリのバリッドビットがオンになる。さらに、コールヒット信号がオンになったことにより、リターンスタックポインタ２７０の値が−１されて１１１となり、リターン命令の戻り先のアドレスの取得先としてリターンアドレススタックＸ２４０のエントリを指定するようになる。
【００６６】
このように、ブランチヒストリ２１０にてコール命令の存在が検出されると、リターンアドレススタックＸ２４０にリターン命令の戻り先のアドレスが格納され、ブランチヒストリ２１０にてリターン命令の存在が検出されればこの値が利用される状態になる。
【００６７】
ここでは、δのリターン命令がブランチヒストリ２１０に検出される前に、アドレスαのコール命令の実行が完了したものとして説明を続ける。図９は、図３に示した分岐予測装置２００のＳ２０１におけるコール命令実行時の動作を説明するための説明図である。同図に示すように、分岐リザベーションステーション１５０にてコール命令の実行が完了すると、そのコール命令による分岐の情報がブランチヒストリ２１０に記憶される。
【００６８】
また、実行が完了したコール命令のアドレスαがリターンアドレス演算回路２３０に送出され、リターンアドレス演算回路２３０は、受け取ったアドレスをリターン命令の戻り先のアドレスに変換した値をリターンアドレススタック２２０に送出し、この値をリターンアドレススタック２２０の先頭のエントリにプッシュする。
【００６９】
さらに、分岐リザベーションステーション１５０からのコール命令フラグがオンになり、これによってバリッド制御回路２５０がリターンアドレススタックＸ２４０のエントリのバリッドビットをオフにする。そして、リターンスタックポインタ２７０の値が＋１されて０００になり、リターン命令の戻り先のアドレスの取得先としてリターンアドレススタック２２０の先頭のエントリを指定するようになる。
【００７０】
このように、分岐リザベーションステーション１５０にてコール命令の実行が完了すると、リターンアドレススタック２２０にリターン命令の戻り先のアドレスが格納され、ブランチヒストリ２１０にてリターン命令の存在が検出されればこの値が利用される状態になる。
【００７１】
続いて、命令フェッチ制御ユニット１１０によってアドレスγ＋１２の命令のフェッチが指示されたものとする。図１０は、図３に示した分岐予測装置２００のＳ２０２におけるコール命令フェッチ時の動作を説明するための説明図である。
【００７２】
ブランチヒストリ２１０がアドレスγ＋１２のコール命令の存在を検出すると、図８の場面と同様の動作がおこなわれて、リターンアドレススタックＸ２４０にはリターン命令の戻り先のアドレスとしてγ＋２０が格納され、バリッドビットがオンになる。また、リターンスタックポインタ２７０の値が−１されて、リターンアドレススタックＸ２４０のエントリをリターン命令の戻り先のアドレスの有効な格納場所として指定するようになる。
【００７３】
リターンアドレススタック２２０の先頭のエントリには、アドレスαのコール命令の実行が完了したときに格納されたα＋８のアドレスが保持され、バリッドビットもオンになっているが、リターンスタックポインタ２７０が別のエントリを指しているため、この場面ではリターンアドレススタック２２０に格納された情報がリターン命令の戻り先のアドレスとして出力選択回路２８０に選択されることはない。
【００７４】
ここで、アドレスγ＋１２のコール命令の実行が完了する前にブランチヒストリ２１０によってアドレスηのリターン命令が検出されたとする。図１１は、図３に示した分岐予測装置２００のＳ２０３におけるリターン命令フェッチ時の動作を説明するための説明図である。
【００７５】
同図に示すように、リターン命令を検出したブランチヒストリ２１０は、リターンヒット信号をオンにする。これにより、出力選択回路２８０がリターン命令の戻り先のアドレスを選択して、命令フェッチ制御ユニット１１０へ送出することとなる。
【００７６】
この場面では、リターンスタックポインタ２７０の値が１１１であり、リターン命令の戻り先のアドレスの格納場所としてリターンアドレススタックＸ２４０のエントリを指定しているので、出力選択回路２８０は、リターンアドレススタックＸ２４０のエントリが保持しているγ＋２０をリターン命令の戻り先のアドレスとして命令フェッチ制御ユニット１１０へ送出する。
【００７７】
アドレスγ＋２０は、ηのリターン命令の戻り先として正しいアドレスである。もし、リターンアドレススタックＸ２４０が存在していなければ、ブランチヒストリの保持している前回のηのリターン命令の戻り先のアドレスを分岐先として予測せざるを得ず、誤った分岐予測をしてしまう可能性のある場面であるが、リターンアドレススタックＸ２４０の存在により正しい予測をおこなうことができている。
【００７８】
図１２は、図３に示した分岐予測装置２００のＳ２０３におけるリターン命令フェッチ後の動作を説明するための説明図である。同図に示すように、リターンヒット信号がオンになったことにより、リターンスタックポインタ２７０の値が＋１されて０００になり、リターンアドレススタック２２０の先頭のエントリを指すようになる。
【００７９】
また、リターンヒット信号がオンになったことにより、バリッド制御回路２５０がリターンアドレススタックＸ２４０のエントリのバリッドビットをオフに変更し、このエントリを無効化している。
【００８０】
このように、出力選択回路２８０がリターンアドレススタックＸ２４０のエントリの値をリターン命令の戻り先のアドレスとして命令フェッチ制御ユニット１１０へ送出した後は、リターンアドレススタックＸ２４０のエントリは無効化され、リターンスタックポインタ２７０はリターンアドレススタック２２０のエントリを有効なエントリとして指定するようになる。
【００８１】
ここで、さらにブランチヒストリ２１０によってアドレスδのリターン命令が検出されたとする。図１３は、図３に示した分岐予測装置２００のＳ２０４におけるリターン命令フェッチ時の動作を説明するための説明図である。
【００８２】
同図に示すように、リターン命令を検出したブランチヒストリ２１０は、リターンヒット信号をオンにする。これにより、出力選択回路２８０がリターン命令の戻り先のアドレスを選択して、命令フェッチ制御ユニット１１０へ送出することとなる。
【００８３】
この場面では、リターンスタックポインタ２７０の値が０００であり、リターンアドレススタック２２０の先頭のエントリが有効であることを示しているので、出力選択回路２８０は、リターンアドレススタック２２０の先頭のエントリが保持しているα＋８をリターン命令の戻り先のアドレスとして命令フェッチ制御ユニット１１０へ送出する。
【００８４】
アドレスα＋８は、δのリターン命令の戻り先として正しいアドレスであり、本実施例に係る分岐予測方式は正しく分岐予測をおこなうことができたことになる。なお、図１１の場面で、アドレスηのリターン命令が検出される前にアドレスγ＋１２のコール命令の実行が完了していたとしても、リターンアドレススタック２２０とリターンスタックポインタ２７０の働きにより、正しい分岐予測がおこなわれる。
【００８５】
上述してきたように、本実施例１では、リターンアドレススタックＸ２４０を設けて、ブランチヒストリ２１０でコール命令を検出した時点でここにリターン命令の戻り先のアドレスを格納するように構成したので、コール命令の実行が完了する前にリターン命令が検出された場合であっても正しい分岐予測をおこなうことができ、もって分岐予測の精度を向上させることができる。
【実施例２】
【００８６】
実施例１では、リターンアドレススタックＸをリターンアドレススタックと組み合わせて使用する例について説明したが、リターンアドレススタックＸを単独で使用することもできる。以下、リターンアドレススタックＸを単独で使用した場合について説明をおこなうこととする。
【００８７】
まず、リターンアドレススタックＸを単独で使用した場合の分岐予測装置の構成について説明する。図１４は、本実施例に係る分岐予測装置の構成を示すブロック図である。
【００８８】
分岐予測装置３００の外部の装置は実施例１と同一のため、ここでは、分岐予測装置３００の内部についてのみ説明する。図１４に示すように、分岐予測装置３００は、ブランチヒストリ３１０と、リターンアドレススタックＸ３２０と、バリッド制御回路３３０と、リターンアドレス演算回路３４０と、出力選択回路３５０とを有する。
【００８９】
ブランチヒストリ３１０は、分岐リザベーションステーション１５０にて実行された分岐命令のアドレスとその命令による分岐先を対にして、その他の情報フラグとともに記憶しておく装置である。コール命令やリターン命令も分岐命令の一種であり、その分岐結果がブランチヒストリ３１０に記憶される。
【００９０】
また、ブランチヒストリ３１０は、命令フェッチ制御ユニット１１０から命令のアドレスを取得すると、自身の情報を参照して、そのアドレスに含まれる命令によって分岐が発生するか否かを判断する。そして、分岐が発生すると判断した場合には、出力選択回路３５０に対して分岐先のアドレス等の情報を送出する。
【００９１】
リターンアドレススタックＸ３２０は、ブランチヒストリ３１０にてコール命令が検出された場合に、そのコール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶しておく装置である。リターンアドレススタックＸ３２０の各エントリは、エントリの有効性を示すバリッドビットを備える。なお、本実施例においては、リターンアドレススタックＸ３２０は一つのエントリからなることを前提として説明するが、エントリの数は複数であっても良い。
【００９２】
バリッド制御回路３３０は、リターンアドレススタックＸ３２０のエントリのバリッドビットの状態を制御する回路である。バリッド制御回路３３０は、ブランチヒストリ３１０からのコールヒット信号がオンになった場合にリターンアドレススタックＸ３２０のエントリのバリッドビットをオンにし、リターンヒット信号がオンになった場合にバリッドビットをオフにする。
【００９３】
リターンアドレス演算回路３４０は、ブランチヒストリ３１０が検出したコール命令のアドレスをリターン命令の戻り先のアドレスへ変換する演算をおこない、リターンアドレススタックＸ３２０へ送出する回路である。本実施例で説明しているプロセッサにおいては、コール命令のアドレスに＋８したものがリターン命令の戻り先のアドレスとなるが、他の仕様のプロセッサにおいては変換方式が異なる場合もある。
【００９４】
出力選択回路３５０は、複数の分岐情報から適切なものを選択して命令フェッチ制御ユニット１１０へ送出する回路である。具体的には、ブランチヒストリ３１０がリターン命令を検出してリターンヒット信号がオンになり、リターンアドレススタックＸ３２０のエントリのバリッドビットがオンである場合は、リターンアドレススタックＸ３２０のエントリのアドレスをリターン命令の戻り先のアドレスとして送出する。
【００９５】
次に、図１４に示した分岐予測装置３００の具体的な動作について説明する。ここでは、図１に示したプログラムをもちいて動作を説明することとする。
【００９６】
図１５は、図１４に示した分岐予測装置３００のＳ１０１におけるコール命令フェッチ時の動作を説明するための説明図である。同図に示すように、命令フェッチユニット１１０は、命令を取得する旨の指示をキャッシュ制御ユニット１２０へ送るのと同時に、ブランチヒストリ３１０に対してその命令のアドレスを送出する。
【００９７】
ブランチヒストリ３１０は、自身の保持している分岐履歴を参照し、送出されたアドレスαにコール命令が存在することを検出したならば、コールヒット信号をオンにし、さらに、リターンアドレス演算回路３４０に対してコール命令の存在を検出したアドレスαを送出する。
【００９８】
リターンアドレス演算回路３４０は、受け取ったアドレスをリターン命令の戻り先のアドレスに変換した値をリターンアドレススタックＸ３２０に送出し、この値がリターンアドレススタックＸ３２０のエントリに記憶される。
【００９９】
また、ブランチヒストリ３１０からのコールヒット信号がオンになったことにより、バリッド制御回路３３０がリターンアドレススタックＸ３２０のエントリのバリッドビットをオンに変更する。
【０１００】
このように、ブランチヒストリ３１０にてコール命令の存在が検出されると、リターンアドレススタックＸ３２０にリターン命令の戻り先のアドレスが格納され、ブランチヒストリ３１０にてリターン命令の存在が検出されればこの値が利用される状態になる。
【０１０１】
続いて、アドレスδのリターン命令がブランチヒストリ３１０に検出されたものとする。図１６は、図１４に示した分岐予測装置３００のＳ１０２におけるリターン命令フェッチ時の動作を説明するための説明図である。
【０１０２】
同図に示すように、リターン命令を検出したブランチヒストリ３１０は、リターンヒット信号をオンにする。これにより、出力選択回路３５０がリターン命令の戻り先のアドレスを選択して、命令フェッチ制御ユニット１１０へ送出することとなる。
【０１０３】
この場面では、リターンアドレススタックＸ３２０のエントリのバリッドビットがオンであり、このエントリが有効であることを示しているので、出力選択回路３５０は、リターンアドレススタックＸ３２０のエントリが保持しているα＋８をリターン命令の戻り先のアドレスとして命令フェッチ制御ユニット１１０へ送出する。
【０１０４】
図１７は、図１４に示した分岐予測装置３００のＳ１０２におけるリターン命令フェッチ後の動作を説明するための説明図である。同図に示すように、リターンヒット信号がオンになったことにより、バリッド制御回路３３０がリターンアドレススタックＸ３２０のエントリのバリッドビットをオフに変更し、このエントリを無効化している。
【０１０５】
このように、使用されたリターンアドレススタックＸ３２０のエントリを無効化することにより、リターンアドレススタックＸ３２０のエントリの値が誤って再度使用されることを防止している。
【０１０６】
続いて、アドレスβのコール命令がブランチヒストリ３１０に検出されたものとする。図１８は、図１４に示した分岐予測装置３００のＳ１０３におけるコール命令フェッチ時の動作を説明するための説明図である。
【０１０７】
この場面では、図１５の場面と同様の動作により、リターンアドレススタックＸ３２０にリターン命令の戻り先のアドレスとしてβ＋８が格納され、ブランチヒストリ３１０にてリターン命令の存在が検出されればこの値が利用される状態になる。
【０１０８】
続いて、アドレスδのリターン命令がブランチヒストリ３１０に検出されたものとする。図１９は、図１４に示した分岐予測装置３００のＳ１０４におけるリターン命令フェッチ時の動作を説明するための説明図である。
【０１０９】
この場面では、ブランチヒストリ３１０は、前回のアドレスδからの戻り先であるα＋８をリターン命令の戻り先と予測するが、リターンヒット信号がオンであり、リターンアドレススタックＸ３２０のエントリのバリッドビットがオンであることから、出力選択回路３５０は、リターンアドレススタックＸ３２０のエントリに格納されたβ＋８を分岐先として選択し、これを命令フェッチ制御ユニット１１０へ送出する。
【０１１０】
この場面での正しい分岐先のアドレスはβ＋８であり、分岐予測装置３００は、リターンアドレススタックＸ３２０を備えることにより正しい分岐先を予測することができていることになる。
【０１１１】
上述してきたように、本実施例２では、リターンアドレススタックＸを単独でもちいてリターン命令の戻り先の予測をおこなうように構成したが、このようにリターンアドレススタックＸを単独でもちいた場合もリターン命令の戻り先の予測の精度を向上させることができる。
【０１１２】
この場合、ブランチヒストリ３１０によるコール命令の存在の予測に基づいてリターン命令の戻り先の予測をおこなうことになるため、実施例１の場合と比較して予測の精度は低くなるが、仕組みを単純化できるというメリットがある。
【０１１３】
（付記１）パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測装置であって、
コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、前記分岐命令の実行履歴情報を基にして分岐予測をおこなう分岐予測手段と、
前記分岐予測手段によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する第１の戻り先アドレス記憶手段と、
サブルーチンのコール命令が実行された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する第２の戻り先アドレス記憶手段と、
前記分岐予測手段が保持している情報と、前期第１の戻り先アドレス記憶手段が保持している情報と、前期第２の戻り先アドレス記憶手段と手段が保持している情報とから適切な分岐予測結果を選択して出力する出力選択手段と
を備えたことを特徴とする分岐予測装置。
【０１１４】
（付記２）前期第１の戻り先アドレス記憶手段の各エントリと前期第２の戻り先アドレス記憶手段の各エントリのいずれか一つをその時点における有効なエントリとして指定する有効エントリ指定手段をさらに備え、
前記出力選択手段は、前記分岐予測手段がリターン命令の存在を予測した場合に前記有効エントリ指定手段が示しているエントリの情報を該リターン命令の戻り先のアドレスとして出力することを特徴とする付記１に記載の分岐予測装置。
【０１１５】
（付記３）前記有効エントリ指定手段は、前記分岐予測手段がコール命令の存在を予測したならば、前期第１の戻り先アドレス記憶手段のエントリを有効なエントリとして指定することを特徴とする付記２に記載の分岐予測装置。
【０１１６】
（付記４）前記有効エントリ指定手段は、コール命令の実行が完了するか、もしくは、前記分岐予測手段がリターン命令の存在を予測したならば、前期第２の戻り先アドレス記憶手段のエントリを有効なエントリとして指定することを特徴とする付記２または３に記載の分岐予測装置。
【０１１７】
（付記５）前期第１の戻り先アドレス記憶手段の各エントリが有するバリッドビットを制御し、該エントリに格納された情報が有効であるか否かを前記出力選択手段が判断できるようにするバリッド制御手段をさらに備えたことを特徴とする付記１〜４のいずれか一つに記載の分岐予測装置。
【０１１８】
（付記６）前期バリッド制御手段は、前記分岐予測手段がコール命令の存在を予測したならば、前期第１の戻り先アドレス記憶手段のエントリを有効とすることを特徴とする付記５に記載の分岐予測装置。
【０１１９】
（付記７）前期バリッド制御手段は、コール命令の実行が完了するか、もしくは、前記分岐予測手段がリターン命令の存在を予測したならば、前期第１の戻り先アドレス記憶手段のエントリを無効とすることを特徴とする付記５または６に記載の分岐予測装置。
【０１２０】
（付記８）パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測装置であって、
コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、前記分岐命令の実行履歴情報を基にして分岐予測をおこなう分岐予測手段と、
前記分岐予測手段によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する戻り先アドレス記憶手段と、
前記分岐予測手段が保持している情報と、戻り先アドレス記憶手段と手段が保持している情報とから適切な分岐予測結果を選択して出力する出力選択手段と
を備えたことを特徴とする分岐予測装置。
【０１２１】
（付記９）前記出力選択手段は、前記分岐予測手段がリターン命令の存在を予測した場合に、前記戻り先アドレス記憶手段に有効なエントリが存在すればそのエントリの情報を該リターン命令の戻り先のアドレスとして出力することを特徴とする付記８に記載の分岐予測装置。
【０１２２】
（付記１０）前期戻り先アドレス記憶手段の各エントリが有するバリッドビットを制御し、該エントリに格納された情報が有効であるか否かを前記出力選択手段が判断できるようにするバリッド制御手段をさらに備えたことを特徴とする付記８または９に記載の分岐予測装置。
【０１２３】
（付記１１）前期バリッド制御手段は、前記分岐予測手段がコール命令の存在を予測したならば、前期戻り先アドレス記憶手段のエントリを有効とすることを特徴とする付記１０に記載の分岐予測装置。
【０１２４】
（付記１２）前期バリッド制御手段は、コール命令の実行が完了するか、もしくは、前記分岐予測手段がリターン命令の存在を予測したならば、前期戻り先アドレス記憶手段のエントリを無効とすることを特徴とする付記１０または１１に記載の分岐予測装置。
【０１２５】
（付記１３）パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測方法であって、
コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、前記分岐命令の実行履歴情報を基にして分岐予測をおこなう分岐予測工程と、
前記分岐予測工程によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する第１の戻り先アドレス記憶工程と、
サブルーチンのコール命令が実行された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する第２の戻り先アドレス記憶工程と、
前記分岐予測工程が保持している情報と、前期第１の戻り先アドレス記憶工程が保持している情報と、前期第２の戻り先アドレス記憶工程と工程が保持している情報とから適切な分岐予測結果を選択して出力する出力選択工程と
を含んだことを特徴とする分岐予測方法。
【０１２６】
（付記１４）前期第１の戻り先アドレス記憶工程の各エントリと前期第２の戻り先アドレス記憶工程の各エントリのいずれか一つをその時点における有効なエントリとして指定する有効エントリ指定工程をさらに備え、
前記出力選択工程は、前記分岐予測工程がリターン命令の存在を予測した場合に前記有効エントリ指定工程が示しているエントリの情報を該リターン命令の戻り先のアドレスとして出力することを特徴とする付記１３に記載の分岐予測方法。
【０１２７】
（付記１５）前記有効エントリ指定工程は、前記分岐予測工程がコール命令の存在を予測したならば、前期第１の戻り先アドレス記憶工程のエントリを有効なエントリとして指定することを特徴とする付記１４に記載の分岐予測方法。
【０１２８】
（付記１６）前記有効エントリ指定工程は、コール命令の実行が完了するか、もしくは、前記分岐予測工程がリターン命令の存在を予測したならば、前期第２の戻り先アドレス記憶工程のエントリを有効なエントリとして指定することを特徴とする付記１４または１５に記載の分岐予測方法。
【０１２９】
（付記１７）前期第１の戻り先アドレス記憶工程の各エントリが有するバリッドビットを制御し、該エントリに格納された情報が有効であるか否かを前記出力選択工程が判断できるようにするバリッド制御工程をさらに含んだことを特徴とする付記１３〜１６のいずれか一つに記載の分岐予測方法。
【０１３０】
（付記１８）前期バリッド制御工程は、前記分岐予測工程がコール命令の存在を予測したならば、前期第１の戻り先アドレス記憶工程のエントリを有効とすることを特徴とする付記１７に記載の分岐予測方法。
【０１３１】
（付記１９）前期バリッド制御工程は、コール命令の実行が完了するか、もしくは、前記分岐予測工程がリターン命令の存在を予測したならば、前期第１の戻り先アドレス記憶工程のエントリを無効とすることを特徴とする付記１７または１８に記載の分岐予測方法。
【０１３２】
（付記２０）パイプライン方式のプロセッサにおいて分岐予測をおこなう分岐予測方法であって、
コール命令とリターン命令を含む分岐命令の実行履歴情報を記憶し、前記分岐命令の実行履歴情報を基にして分岐予測をおこなう分岐予測工程と、
前記分岐予測工程によりサブルーチンのコール命令の存在が予測された場合に、該コール命令に対応するリターン命令の戻り先のアドレスを先入れ後出し方式で記憶する戻り先アドレス記憶工程と、
前記分岐予測工程が保持している情報と、戻り先アドレス記憶工程と工程が保持している情報とから適切な分岐予測結果を選択して出力する出力選択工程と
を含んだことを特徴とする分岐予測方法。
【０１３３】
（付記２１）前記出力選択工程は、前記分岐予測工程がリターン命令の存在を予測した場合に、前記戻り先アドレス記憶工程に有効なエントリが存在すればそのエントリの情報を該リターン命令の戻り先のアドレスとして出力することを特徴とする付記２０に記載の分岐予測方法。
【０１３４】
（付記２２）前期戻り先アドレス記憶工程の各エントリが有するバリッドビットを制御し、該エントリに格納された情報が有効であるか否かを前記出力選択工程が判断できるようにするバリッド制御工程をさらに含んだことを特徴とする付記２０または２１に記載の分岐予測方法。
【０１３５】
（付記２３）前期バリッド制御工程は、前記分岐予測工程がコール命令の存在を予測したならば、前期戻り先アドレス記憶工程のエントリを有効とすることを特徴とする付記２２に記載の分岐予測方法。
【０１３６】
（付記２４）前期バリッド制御工程は、コール命令の実行が完了するか、もしくは、前記分岐予測工程がリターン命令の存在を予測したならば、前期戻り先アドレス記憶工程のエントリを無効とすることを特徴とする付記２２または２３に記載の分岐予測方法。
【産業上の利用可能性】
【０１３７】
以上のように、本発明にかかる分岐予測装置および分岐予測方法は、パイプライン方式のプロセッサにおける分岐予測に有用であり、特に、リターン命令の戻り先の予測精度を高めたい場合に適している。
【図面の簡単な説明】
【０１３８】
【図１】本実施例に係る分岐予測方式の原理を説明するためにもちいるプログラムの説明図である。
【図２】本実施例に係る分岐予測方式による二つ目のリターン命令検出時の分岐予測について説明するための説明図である。
【図３】本実施例に係る分岐予測装置の構成を示すブロック図である。
【図４】図３に示したバリッド制御回路の構成を示すブロック図である。
【図５】図３に示したリターンスタックポインタの構成を示すブロック図である。
【図６】図３に示した出力選択回路の構成を示すブロック図である。
【図７】図３に示した分岐予測装置の動作を説明するためにもちいるプログラムの説明図である。
【図８】図３に示した分岐予測装置のＳ２０１におけるコール命令フェッチ時の動作を説明するための説明図である。
【図９】図３に示した分岐予測装置のＳ２０１におけるコール命令実行時の動作を説明するための説明図である。
【図１０】図３に示した分岐予測装置のＳ２０２におけるコール命令フェッチ時の動作を説明するための説明図である。
【図１１】図３に示した分岐予測装置のＳ２０３におけるリターン命令フェッチ時の動作を説明するための説明図である。
【図１２】図３に示した分岐予測装置のＳ２０３におけるリターン命令フェッチ後の動作を説明するための説明図である。
【図１３】図３に示した分岐予測装置のＳ２０４におけるリターン命令フェッチ時の動作を説明するための説明図である。
【図１４】本実施例に係る分岐予測装置の構成を示すブロック図である。
【図１５】図１４に示した分岐予測装置のＳ１０１におけるコール命令フェッチ時の動作を説明するための説明図である。
【図１６】図１４に示した分岐予測装置のＳ１０２におけるリターン命令フェッチ時の動作を説明するための説明図である。
【図１７】図１４に示した分岐予測装置のＳ１０２におけるリターン命令フェッチ後の動作を説明するための説明図である。
【図１８】図１４に示した分岐予測装置のＳ１０３におけるコール命令フェッチ時の動作を説明するための説明図である。
【図１９】図１４に示した分岐予測装置のＳ１０４におけるリターン命令フェッチ時の動作を説明するための説明図である。
【図２０】従来の分岐予測方式による一つ目のリターン命令検出時の分岐予測について説明するための説明図である。
【図２１】従来の分岐予測方式による二つ目のリターン命令検出時の分岐予測について説明するための説明図である。
【図２２】従来の分岐予測方式による二つ目のリターン命令検出時の分岐予測が失敗する場合について説明するための説明図である。
【符号の説明】
【０１３９】
１１０    命令フェッチ制御ユニット
１２０    キャッシュ制御ユニット
１３０    命令バッファ
１４０    デコーダ
１５０    分岐レザベーションステーション
１６０    整数演算レザベーションステーション
１７０    浮動小数演算レザベーションステーション
１８０    アドレス生成レザベーションステーション
２００    分岐予測装置
２１０    ブランチヒストリ
２２０    リターンアドレススタック
２３０    リターンアドレス演算回路
２４０    リターンアドレススタックＸ
２５０    バリッド制御回路
２６０    リターンアドレス演算回路
２７０    リターンスタックポインタ
２８０    出力選択回路
３００    分岐予測装置
３１０    ブランチヒストリ
３２０    リターンアドレススタックＸ
３３０    バリッド制御回路
３４０    リターンアドレス演算回路
３５０    出力選択回路
【図１】
2006040173.tif 000003
【図２】
2006040173.tif 000004
【図３】
2006040173.tif 000005
【図４】
2006040173.tif 000006
【図５】
2006040173.tif 000007
【図６】
2006040173.tif 000008
【図７】
2006040173.tif 000009
【図８】
2006040173.tif 000010
【図９】
2006040173.tif 000011
【図１０】
2006040173.tif 000012
【図１１】
2006040173.tif 000013
【図１２】
2006040173.tif 000014
【図１３】
2006040173.tif 000015
【図１４】
2006040173.tif 000016
【図１５】
2006040173.tif 000017
【図１６】
2006040173.tif 000018
【図１７】
2006040173.tif 000019
【図１８】
2006040173.tif 000020
【図１９】
2006040173.tif 000021
【図２０】
2006040173.tif 000022
【図２１】
2006040173.tif 000023
【図２２】
2006040173.tif 000024