JP3723019B2 - サブルーチンリターン相当の命令の分岐予測を行う装置および方法 - Google Patents

Description

【０００１】
【発明の属する技術分野】
本発明は、分岐予測機構を有する情報処理装置に係り、特に、サブルーチンリターンのための特別な命令が用意されていないアーキテクチャにおいて、サブルーチンリターン相当の命令の分岐予測を行う分岐予測装置およびその方法に関する。
【０００２】
【従来の技術】
従来の命令処理装置においては、パイプライン処理やアウトオブオーダー処理のような技術を用いて、ある命令の実行の完了を待たずに後続の命令の実行を次々と開始することで、性能の向上が図られてきた。
【０００３】
パイプライン処理において、先行する命令が、分岐命令のように後続の実行シーケンスを変更する命令である場合、分岐が成立するときに、分岐先の命令を実行パイプラインに投入する必要がある。そうしなければ、実行パイプラインが乱され、最悪の場合は、逆に性能が落ちてしまう。
【０００４】
そこで、ブランチヒストリ（分岐予測テーブル）に代表される分岐予測機構を設けて、分岐の成立・不成立を予測することで、性能の向上が図られてきた。このような装置において、分岐の成立が予測された場合には、分岐命令の後に分岐先の命令が実行パイプラインに投入されるため、分岐が実際に成立したときに実行パイプラインが乱されることがない。
【０００５】
また、サブルーチンリターン命令の分岐先（戻り先）は、その命令の性質上、実行の度に変わることが多い。これは、サブルーチンの呼び出し元であるサブルーチンコール命令の場所が実行の度に異なるためである。このような命令に対しては、リターンアドレススタックと呼ばれる専用の分岐予測機構を設けることで、性能の向上が可能となることが知られている。
【０００６】
【発明が解決しようとする課題】
しかしながら、上述した従来の分岐予測機構には、以下のような問題がある。
ＣＰＵ（中央処理装置）アーキテクチャの中には、サブルーチンコール・リターン命令対として、あらかじめ特別な命令を準備していないものがある。このようなアーキテクチャにおいて、リターンアドレススタックを採用して性能向上を図るためには、実行される分岐命令の中から、サブルーチンコール・リターン相当の命令対を動的に抽出する技術が必要となる。
【０００７】
ところが、従来の情報処理装置では、デコード時にサブルーチンコール・リターン命令であるか否かを静的に決定していたため、ハードウェアによる解釈と異なるプログラミングは好ましいものではなかった。この場合、好ましくないプログラミングにより、コール・リターン対の対応関係が、一旦、実際とずれてしまうと、リターンアドレススタックの特性上、それ以降の分岐先を次々と誤ることになる。このため、リターンアドレススタックが多段であればあるほど、性能を落としていた。
【０００８】
図１８は、このようなアーキテクチャにおいて使用される、サブルーチンコール・リターン命令対を含むプログラムの例を示している。
この例では、メインルーチンの中の命令“ｂａｌｒ １４，１５”により、サブルーチンＳ１が呼び出され（Ｃａｌｌ １）、さらにその中の命令“ｂａｌｒ１５，１３”により別のサブルーチンＳ２が呼び出されている（Ｃａｌｌ ２）。そして、条件リターン命令“ｂｃｒ ７，１５”により制御がサブルーチンＳ１に戻り（Ｒｅｔｕｒｎ ２）、さらに無条件リターン命令“ｂｃｒ １５，１４”によりメインルーチンに戻っている（Ｒｅｔｕｒｎ １）。
【０００９】
ここで、命令処理装置が、特定のオペレーションコード“ｂａｌｒ”を、サブルーチンコール相当の命令として認識し、特定のオペレーションコードとオペランドを含む無条件分岐命令“ｂｃｒ １５，ｘ”（ｘは任意）を、サブルーチンリターン相当の命令として認識するものとする。
【００１０】
この場合、サブルーチンＳ２の中の命令“ｂｃｒ ７，１５”は、サブルーチンリターン相当の命令として認識されずに、見落とされる。このため、従来のリターンアドレススタックでは、Ｃａｌｌ ２に対応するリターンがＲｅｔｕｒｎ１であると認識してしまい、分岐予測に失敗する。実際には、Ｃａｌｌ ２に対応する正しいリターンは、Ｒｅｔｕｒｎ ２である。
【００１１】
また、命令処理装置が、オペレーションコード“ｂｃｒ”を含むすべての命令を単純にサブルーチンリターン相当の命令として認識すると、サブルーチンＳ２の中の単なる条件分岐命令である“ｂｃｒ ４，３”が、Ｃａｌｌ ２に対応するリターンであると認識されてしまう。したがって、この場合も、リターンアドレススタックがコール・リターン対を誤認識することが分かる。
【００１２】
このように、リターンアドレススタックを持つ情報処理装置においては、命令の実行時に、正しいサブルーチンコール・リターン命令対を認識することが重要になる。
【００１３】
本発明の課題は、サブルーチンリターンのための特別な命令が用意されていない情報処理装置において、サブルーチンリターン相当の命令を正しく認識する分岐予測装置およびその方法を提供することである。
【００１４】
【課題を解決するための手段】
図１は、本発明の分岐予測装置の原理図である。本発明の第１の局面において、分岐予測装置は、格納手段１、比較手段２、および識別手段３を備える。
【００１５】
格納手段１は、サブルーチンコール相当の命令が検出されたとき、サブルーチンの戻り先アドレスを指定する情報を格納する。比較手段２は、サブルーチンリターン相当の命令になり得る命令が検出されたとき、そのサブルーチンリターン相当の命令になり得る命令の分岐先アドレスを指定する情報と、格納手段１に格納された戻り先アドレスを指定する情報とを比較し、比較結果を出力する。識別手段３は、その比較結果に基づいて、上記サブルーチンコール相当の命令に対応するサブルーチンリターン相当の命令を識別する。
【００１６】
実行された（実行される）命令が、サブルーチンコール相当の動作をする命令であるとき、その命令により指定される戻り先アドレスや戻り先アドレスを保持するレジスタの情報等が、戻り先アドレスを指定する情報として格納手段１に格納される。
【００１７】
次に、実行された（実行される）命令が、サブルーチンリターン相当の動作をする命令である可能性があるとき、その命令により指定される分岐先アドレスや分岐先アドレスを保持するレジスタの情報等が、分岐先アドレスを指定する情報として選択され、比較手段２により、その情報が戻り先アドレスを指定する情報と比較される。
【００１８】
そして、識別手段３は、分岐先アドレスを指定する情報と戻り先アドレスを指定する情報が一致すれば、後者の命令を前者の命令に対応するサブルーチンリターン相当の命令であると識別し、それらが一致しなければ、後者の命令を前者の命令に対応するサブルーチンリターン相当の命令ではないと識別する。
【００１９】
このように、サブルーチンの戻り先アドレスを指定する情報を用いることで、正しいサブルーチンコール・リターン相当の命令対を動的に抽出することができる。したがって、コール・リターン対の対応関係が正しく認識され、その対応関係のズレが防止される。
【００２０】
また、本発明の第２の局面において、分岐予測装置は、スタック手段４、プッシュ手段５、比較手段２、および識別手段３を備える。
スタック手段４は、サブルーチンの戻り先アドレスを指定する情報を格納する。プッシュ手段５は、サブルーチンコール相当の命令が検出されたとき、上記戻り先アドレスを指定する情報をスタック手段４にプッシュする。
【００２１】
比較手段２は、サブルーチンリターン相当の命令になり得る命令が検出されたとき、そのサブルーチンリターン相当の命令になり得る命令の分岐先アドレスを指定する情報と、スタック手段４の先頭エントリに格納された戻り先アドレスを指定する情報とを比較し、比較結果を出力する。識別手段３は、その比較結果に基づいて、上記サブルーチンコール相当の命令に対応するサブルーチンリターン相当の命令を識別する。
【００２２】
サブルーチンコール相当の動作をする命令が検出されると、プッシュ手段５は、戻り先アドレスを指定する情報をスタック手段４にプッシュする。次に、サブルーチンリターン相当の動作をする命令である可能性がある命令が検出されると、比較手段２は、その命令の分岐先アドレスを指定する情報を、スタック手段４にプッシュされた戻り先アドレスを指定する情報と比較する。
【００２３】
そして、識別手段３は、分岐先アドレスを指定する情報と戻り先アドレスを指定する情報が一致すれば、後者の命令を前者の命令に対応するサブルーチンリターン相当の命令であると識別し、それらが一致しなければ、後者の命令を前者の命令に対応するサブルーチンリターン相当の命令ではないと識別する。
【００２４】
このように、サブルーチンの戻り先アドレスを指定する情報をスタック手段４にプッシュすることで、第１の局面の分岐予測装置と同様に、コール・リターン対の対応関係が正しく認識され、その対応関係のズレが防止される。
【００２５】
また、本発明の第３の局面において、分岐予測装置は、リターンアドレススタック手段６、比較手段２、および識別手段３を備える。
リターンアドレススタック手段６は、サブルーチンコール相当の命令が検出されたとき、サブルーチンの戻り先アドレスを格納する。比較手段２は、サブルーチンリターン相当の命令になり得る命令が検出されたとき、そのサブルーチンリターン相当の命令になり得る命令の分岐先アドレスと、リターンアドレススタック手段６に格納された戻り先アドレスとを比較し、比較結果を出力する。識別手段３は、その比較結果に基づいて、上記サブルーチンコール相当の命令に対応するサブルーチンリターン相当の命令を識別する。
【００２６】
サブルーチンコール相当の動作をする命令が検出されると、その命令により指定された戻り先アドレスがリターンアドレススタック手段６にプッシュされる。次に、サブルーチンリターン相当の動作をする命令である可能性がある命令が検出されると、比較手段２は、その命令の分岐先アドレスを、リターンアドレススタック手段６にプッシュされた戻り先アドレスと比較する。
【００２７】
そして、識別手段３は、分岐先アドレスと戻り先アドレスが一致すれば、後者の命令を前者の命令に対応するサブルーチンリターン相当の命令であると識別し、それらが一致しなければ、後者の命令を前者の命令に対応するサブルーチンリターン相当の命令ではないと識別する。
【００２８】
このように、リターンアドレススタック手段６にプッシュされた戻り先アドレスを、直接、命令の分岐先アドレスと比較することで、第１の局面の分岐予測装置と同様に、コール・リターン対の対応関係が正しく認識され、その対応関係のズレが防止される。
【００２９】
例えば、図１の格納手段１およびスタック手段４は、後述する図３のリンクスタック３３、またはリターンアドレススタック３５に対応する。また、例えば、図１の比較手段２と識別手段３は、後述する図１１のＥＸＮＯＲ回路１０１、ＯＲ回路１０２、およびＡＮＤ回路１０３、または後述する図１７の比較回路１５１およびＡＮＤ回路１５２に対応する。また、図１のプッシュ手段５は、後述する図１２の制御回路に対応し、図１のリターンアドレススタック手段６は、図３のリターンアドレススタック３５に対応する。
【００３０】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施の形態を詳細に説明する。
命令処理装置においては、サブルーチンコール相当の命令により、戻り先のアドレスを格納するリンクレジスタが指定され、指定されたリンクレジスタを用いて、サブルーチンリターン相当の命令による分岐が行われる。
【００３１】
サブルーチンコールまたはリターン相当の命令は、例えば、図２に示すように、オペレーションコード（ＯＰコード）１１、第１オペランド１２、および第２オペランド１３を含む。サブルーチンコール相当の命令においては、第１オペランド１２が、リンクレジスタのレジスタ番号を表し、サブルーチンリターン相当の命令においては、第２オペランド１３が、分岐先アドレスを格納するレジスタのレジスタ番号を表す。
【００３２】
そこで、本実施形態においては、サブルーチンコール時に指定されたリンクレジスタのレジスタ番号を記録するリンクスタックを設ける。そして、リンクスタックに記録された番号のレジスタ内のアドレスを分岐先アドレスとして用いる分岐命令が出現したとき、その分岐命令をサブルーチンリターン相当の命令と認識する。
【００３３】
このような制御によれば、リンクレジスタのレジスタ番号をリンク情報として用いて、サブルーチンコール相当の命令とサブルーチンリターン相当の命令を対応付けることができ、サブルーチンコール・リターン相当の命令対を動的に抽出することが可能になる。したがって、コール・リターン対の対応関係を正しく認識することができ、その対応関係のズレが防止されるので、リターンアドレススタックによる分岐予測の精度が向上する。
【００３４】
例えば、図１８の例の場合、コール命令に含まれるリンクレジスタの番号と、リターン命令に含まれる分岐先アドレスレジスタの番号を比較すれば、正しいコール・リターン対を認識することができ、分岐予測も成功する。
【００３５】
Ｃａｌｌ １の命令“ｂａｌｒ １４，１５”の第１オペランドは、リンクレジスタの番号が“１４”であることを表しており、Ｒｅｔｕｒｎ １の命令“ｂｃｒ １５，１４”の第２オペランドは、分岐先アドレスレジスタの番号が“１４”であることを表している。したがって、後者の命令は、Ｃａｌｌ １に対応するリターン相当の命令であると認識される。
【００３６】
また、Ｃａｌｌ ２の命令“ｂａｌｒ １５，１３”の第１オペランドは、リンクレジスタの番号が“１５”であることを表しており、Ｒｅｔｕｒｎ ２の命令“ｂｃｒ ７，１５”の第２オペランドは、分岐先アドレスレジスタの番号が“１５”であることを表している。したがって、後者の命令は、Ｃａｌｌ ２に対応するリターン相当の命令であると認識される。
【００３７】
次に、特別なサブルーチンコール・リターン命令対を準備していないアーキテクチャの一例を用いて、本実施形態における情報処理装置の動作をより詳細に説明する。このようなアーキテクチャは、例えば、ＥＳＡ（enterprise systems architecture ）／３９０のＰＯＯ（principles of operation ）により規定されている。
【００３８】
サブルーチンコールとして使用可能な命令としては、サブルーチンリターン相当の命令による戻り先のアドレス（リンクアドレス）をレジスタに保存可能である命令が考えられる。このような命令には、ｂａｌ、ｂａｌｒ、ｂａｓ、ｂａｓｒ、ｂａｓｓｍ等がある。
【００３９】
また、サブルーチンリターンとして使用可能な命令としては、一般の分岐命令のほとんどが挙げられる。これらの中でも、特に、分岐先アドレスを１つのレジスタで指定する分岐命令、すなわち、ＲＲ形式命令が用いられやすい。ＲＲ形式命令には、ｂｃｒ、ｂｓｍ等がある。もちろん、これらの命令は、通常の無条件分岐命令あるいは条件分岐命令としても用いられる。
【００４０】
また、このようなアーキテクチャでは、出現頻度は低いものの、サブルーチンコール・リターン対を崩し得る命令も存在し得る。このような命令としては、例えば、ｌｐｓｗや、ｂｃ等のＲＸ形式命令が挙げられる。また、一部の割り込み事象においても、サブルーチンコール・リターン対が崩されることがある。
【００４１】
ｂｃに代表されるＲＸ形式の分岐命令は、リターン先アドレスを１つのレジスタのみで指定するとは限らず、特に、ディスプレイスメントを指定する場合がある。他にも、リンクレジスタの値を書き換える等の処理により、戻り先アドレスが変更される場合もある。
【００４２】
このような命令がサブルーチンリターンとして使用された場合、コール時にリターンアドレススタックに登録された戻り先アドレスが正しくならないので、リターン時にリターンアドレススタックを参照しないことが望ましい。その代わりに、通常の分岐命令と同じように、ブランチヒストリに登録されている予測分岐先を参照すれば、正しい戻り先アドレスが得られる可能性がある。
【００４３】
また、ｌｐｓｗは、分岐先アドレスをレジスタで直接指定せず、オペランドが指すメモリ上のデータ列を分岐先アドレスとして用いる。このような命令列が出現した場合には、コール・リターン対の対応関係が崩れてしまう可能性がある。あるいはまた、割り込みが発生した場合にも、その割り込みの種類によっては、同様にコール・リターン対が崩れてしまうことがある。
【００４４】
そこで、リターンアドレススタックに何らかの機構を組み込む必要がある。その一方法として、このような命令が実行されたときやこのような割り込みが発生したときに、リターンアドレススタックとリンクスタック双方のエントリをすべて消去してしまうことが考えられる。このような制御により、リターンアドレススタックの対応のズレが防止され、発生したズレにそれ以降の予測結果が引き摺られて性能が劣化することはなくなる。
【００４５】
また、基本的な分岐命令がハードワイヤードで実現されているにもかかわらず、一部の分岐命令は、他の複雑な動作を伴うために、マイクロコードにより制御されている場合がある。このような複雑な分岐命令は、回路が複雑になるわりには得るものが少ない等の理由で、ブランチヒストリに登録しているメリットがない。このため、リターンアドレススタックも動作しない。
【００４６】
しかしながら、前述したように、このような複雑な命令でも、サブルーチンコールもしくはリターン相当の命令になり得る場合には、その命令に対する対策を講じなければ、リターンアドレススタックの対応がずれてしまい、性能劣化の原因となる。
【００４７】
そこで、ブランチヒストリに登録されていないサブルーチンコール相当の分岐命令が実行された後に、それに対応すると考えられるサブルーチンリターン相当の命令が検出されたとき、ブランチヒストリおよびリターンアドレススタックにおいて、そのサブルーチンリターン相当の命令をリターン相当の命令とは認識しないような制御を行う。
【００４８】
また、プログラム指針書等により特定のレジスタをリンクレジスタとして使用することが推奨される場合等のように、特定のレジスタがリンクレジスタとして非常に多く使われることがある。このようなシステムでは、その特定のレジスタを用いる命令を、常に、サブルーチンコールまたはリターン相当の命令と認識することにする。これにより、リンクスタックのエントリを効率的に用いることができ、規模の小さなリンクスタックでも大きな効果が得られる。
【００４９】
また、分岐命令において、分岐先アドレスのレジスタ番号として“０”を指定すると、分岐は行われない。このようなアーキテクチャでは、レジスタ番号“０”をリンク情報として、対応するサブルーチンリターン相当の命令を判別することは不可能である。そこで、サブルーチンコール相当の命令において、リンクレジスタの番号として“０”が指定されたときには、この命令をサブルーチンコール相当の命令として認識しないようにする。
【００５０】
図３は、本実施形態における命令処理装置の構成図である。図３の命令処理装置は、命令フェッチ回路２１、分岐予測機構２２、デコーダ２３、分岐先アドレス生成回路２４、分岐命令実行処理回路２５、および命令実行完了処理回路２６を備え、命令をアウトオブオーダー方式で処理する。アウトオブオーダー処理方式を採用した命令処理装置においては、性能の向上を図るため、１つの命令実行の完了を待たずに、後続の命令列が順次複数のパイプラインに投入される。
【００５１】
命令フェッチ回路２１と分岐予測機構２２は、命令フェッチパイプラインの回路に対応する。分岐予測機構２２は、予測回路３１、比較回路３２、およびリンクスタック３３を含み、予測回路３１は、ブランチヒストリ３４とリターンアドレススタック３５を含む。
【００５２】
また、デコーダ２３、分岐先アドレス生成回路２４、分岐命令実行処理回路２５、および命令実行完了処理回路２６は、命令実行パイプラインの回路に対応する。分岐命令実行処理回路２５は、複数のＲＳＢＲ（Reservation Station for BRanch）３６を含む。
【００５３】
命令フェッチパイプラインは、命令アドレス発行サイクル（ＩＡ）、テーブルサイクル（ＩＴ）、バッファサイクル（ＩＢ）、および結果サイクル（ＩＲ）を含み、命令実行パイプラインは、デコードサイクル（Ｄ）、アドレス計算サイクル（Ａ）、実行サイクル（Ｘ）、更新サイクル（Ｕ）、およびライトサイクル（Ｗ）を含む。
【００５４】
ＲＳＢＲ３６は、分岐命令を制御するための処理待ちのスタックである。分岐命令実行処理回路２５は、アウトオブオーダー処理方式に従って、スタック内の処理可能なエントリを選択し、プログラムにより指示された順序とは異なる順序で、随時、分岐命令を実行することができる。
【００５５】
ＲＳＢＲ３６で扱われる分岐命令のうち、ｂａｌ、ｂａｌｒ（ただし、ｂａｌｒ １，１４を除く）、ｂｒａｓ、ｂａｓ、およびｂａｓｒは、サブルーチンコール相当の命令として扱われ、ｂｃｒ、ｂｓｍ、ｂａｌｒ １，１４は、サブルーチンリターン相当の命令として扱われる。また、ｂａｓｓｍは、サブルーチンコール相当の命令ではあるが、ＲＳＢＲ３６では扱われない複雑命令である。
【００５６】
分岐命令実行処理回路２５が分岐命令を実行した結果、分岐が生じることが判明した場合、分岐先の命令アドレスと分岐命令自身の命令アドレスが、対にしてブランチヒストリ３４に登録される。そして、命令フェッチ回路２１は、分岐命令をフェッチしたとき、次の命令のフェッチに先立ってブランチヒストリ３４を検索し、分岐先を予測する。
【００５７】
また、デコーダ２３がサブルーチンコール相当の命令を検出したとき、その命令のオペランドが表すリンクレジスタの番号がリンクスタック３３にプッシュされ、対応する戻り先の命令アドレスがリターンアドレススタック３５にプッシュされる。
【００５８】
また、デコーダ２３がサブルーチンリターン相当の命令になり得る命令を検出すると、比較回路３２は、リンクスタック３３の先頭エントリに登録されているレジスタ番号と、検出された命令のオペランドが表す分岐先アドレスレジスタの番号を比較する。そして、２つのレジスタ番号が一致すれば、その命令がサブルーチンリターン相当の動作をする命令であると判断し、比較結果を予測回路３１に出力する。
【００５９】
このとき、リンクスタック３３からレジスタ番号がポップされ、リターンアドレススタック３５から対応する命令アドレスがポップされる。そして、ポップされた命令アドレスが、予測分岐先として命令フェッチ回路２１に渡される。
【００６０】
リンクスタック３３のエントリは、図４に示すように、リターンアドレススタック３５のエントリと１対１に対応しており、これらの２つのスタックは、同時にプッシュ動作およびポップ動作を行う。ここでは、リンクスタック３３のエントリには、４ビットのレジスタ番号〈０：３〉が格納されており、リターンアドレススタック３５のエントリには、３２ビットの分岐先アドレス〈０：３１〉が格納されている。これらのスタックは、一般に、ｎ個（ｎ≧１）のエントリからなるｎ段のスタックとして実装される。
【００６１】
図５は、図３の命令処理装置において用いられる信号を示している。デコーダ２３は、信号＋Ｄ＿ＢＡＬＲ、＋Ｄ＿ＢＡＬ、＋Ｄ＿ＢＲＡＳ、＋Ｄ＿ＢＡＳ、＋Ｄ＿ＢＡＳＲ、＋Ｄ＿ＢＡＬＲ＿１Ｅ、＋Ｄ＿ＢＣＲ、＋Ｄ＿ＢＳＭ、＋Ｄ＿ＢＡＳＳＭ、および＋Ｄ＿ＯＰＣ〈８：１５〉を分岐命令実行処理回路２５に出力する。
【００６２】
信号＋Ｄ＿ＢＡＬＲ、＋Ｄ＿ＢＡＬ、＋Ｄ＿ＢＲＡＳ、＋Ｄ＿ＢＡＳ、＋Ｄ＿ＢＡＳＲ、＋Ｄ＿ＢＡＬＲ＿１Ｅ、＋Ｄ＿ＢＣＲ、＋Ｄ＿ＢＳＭ、および＋Ｄ＿ＢＡＳＳＭは、それぞれ、ｂａｌｒ、ｂａｌ、ｂｒａｓ、ｂａｓ、ｂａｓｒ、ｂａｌｒ １，１４、ｂｃｒ、ｂｓｍ、およびｂａｓｓｍが検出されたときに、論理“１”となる。また、信号＋Ｄ＿ＯＰＣ〈８：１５〉は、機械語命令のビット〈８：１５〉のデータを表す。
【００６３】
分岐命令実行処理回路２５は、信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬ、＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＴＮ、＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＣＡＬＬ＿ＲＴＮ＿ＲＥＧ〈０：３〉、＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＢＳＭ、および＋Ｄ＿ＢＡＳＳＭを分岐予測機構２２に出力する。
【００６４】
信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬは、命令がサブルーチンコール相当の命令と判別されたときに論理“１”となり、信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＴＮは、命令がサブルーチンリターン相当の命令になり得る命令と判別されたときに論理“１”となる。また、信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＣＡＬＬ＿ＲＴＮ＿ＲＥＧ〈０：３〉は、命令のオペランドにより指定されたレジスタ番号を表し、信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＢＳＭは、ｂｓｍ命令の実行が完了したときに論理“１”となる。
【００６５】
次に、図６から図１７までを参照しながら、図３の命令処理装置の構成と動作についてより詳細に説明する。
まず、デコーダ２３による命令デコード時に、図５に示した信号がＲＳＢＲ３６に入力され、サブルーチンコール相当の命令とサブルーチンリターン相当の命令になり得る命令が判別される。このうち、サブルーチンリターン相当の命令になり得る命令については、後述するリンクスタック３３の回路により、サブルーチンリターンとのより厳密な対応関係が識別されることになる。
【００６６】
図６は、ＲＳＢＲ３６内の判別回路を示している。図６において、入力信号−Ｄ＿ＢＡＬＲ＿１Ｅは、図５の信号＋Ｄ＿ＢＡＬＲ＿１Ｅの否定を表し、命令“ｂａｌｒ １，１４”がデコードされたときに論理“０”となる。ＡＮＤ回路４１は、入力信号＋Ｄ＿ＢＡＬＲと−Ｄ＿ＢＡＬＲ＿１Ｅの論理積を、ＯＲ回路４２に出力する。したがって、“ｂａｌｒ １，１４”以外のｂａｌｒ命令がデコードされたとき、ＡＮＤ回路４１の出力は論理“１”となる。
【００６７】
ＯＲ回路４２は、ＡＮＤ回路４１からの出力信号と、入力信号＋Ｄ＿ＢＡＬ、＋Ｄ＿ＢＲＡＳ、＋Ｄ＿ＢＡＳＲ、および＋Ｄ＿ＢＡＳの論理和を、信号＋Ｄ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬとして出力する。この信号＋Ｄ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬは、デコードされた命令がサブルーチンコール相当の命令であるときに論理“１”となるフラグとして用いられる。
【００６８】
また、ＯＲ回路４３は、入力信号＋Ｄ＿ＢＡＬＲ＿１Ｅ、＋Ｄ＿ＢＣＲ、および＋Ｄ＿ＢＳＭの論理和を、信号＋Ｄ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＥＴＵＲＮとして出力する。この信号＋Ｄ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＥＴＵＲＮは、デコードされた命令がサブルーチンリターン相当の命令になり得る命令であるときに論理“１”となるフラグとして用いられる。
【００６９】
デコードされた命令が分岐命令であれば、通常は、デコード結果がＲＳＢＲ３６に登録される。この時点で、ＲＳＢＲ３６には、サブルーチンコール・リターン判別結果を表すフラグと、リンクレジスタや分岐先アドレスレジスタの情報等が登録される。
【００７０】
ＥＳＡ／３９０ ＰＯＯのアーキテクチャでは、サブルーチンコール相当の命令になり得る命令（機械語命令）のビット〈８：１１〉にリンクレジスタの番号が指定され、サブルーチンリターン相当の命令になり得る命令（機械語命令）のビット〈１２：１５〉に分岐アドレスレジスタの番号が指定される。そこで、ビット〈８：１５〉のデータがこれらのレジスタの情報として登録される。
【００７１】
図７は、ＲＳＢＲ３６内の登録回路を示している。図７において、入力信号＋ＲＳＢＲ＿ＶＡＬＩＤは、対応するＲＳＢＲ３６が有効である間、論理“１”となる。ラッチ回路５１は、入力信号＋Ｄ＿ＯＰＣ〈８：１５〉の値をラッチし、信号＋ＲＳＢＲ＿ＯＰＣ〈８：１５〉として出力する。
【００７２】
また、ラッチ回路５２は、図６の判別回路が生成したフラグ＋Ｄ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬと＋Ｄ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＥＴＵＲＮの値をラッチし、それぞれ、信号＋ＲＳＢＲ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬと＋ＲＳＢＲ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＥＴＵＲＮとして出力する。
【００７３】
信号＋ＲＳＢＲ＿ＶＡＬＩＤが論理“１”となると、これらの情報の登録が終了し、対応するＲＳＢＲ３６が有効である間、ラッチ回路５１、５２に登録された情報が保持される。
【００７４】
次に、分岐履歴情報の更新時において、ＲＳＢＲ３６に登録されたサブルーチンコール・リターン判別結果とレジスタ情報が、その他の分岐履歴情報と同時に、分岐予測機構２２へ送出される。サブルーチンコール相当の命令である場合は、リンクレジスタの番号がレジスタ情報として選択され、サブルーチンリターン相当の命令になり得る命令である場合は、分岐先アドレスレジスタの番号がレジスタ情報として選択される。
【００７５】
図８は、ＲＳＢＲ３６内の選択回路を示している。図８において、ＡＮＤ回路６１は、図７の登録回路からの信号＋ＲＳＢＲ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬと＋ＲＳＢＲ＿ＯＰＣ〈８：１１〉の論理積を、ＯＲ回路６３に出力する。したがって、フラグ＋ＲＳＢＲ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬが立っているときは、リンクレジスタの番号がＡＮＤ回路６１から出力される。
【００７６】
また、ＡＮＤ回路６２は、図７の登録回路からの信号＋ＲＳＢＲ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＥＴＵＲＮと＋ＲＳＢＲ＿ＯＰＣ〈１２：１５〉の論理積を、ＯＲ回路６３に出力する。したがって、フラグ＋ＲＳＢＲ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＥＴＵＲＮが立っているときは、分岐先アドレスレジスタの番号がＡＮＤ回路６２から出力される。
【００７７】
そして、ＯＲ回路６３は、ＡＮＤ回路６１、６２の出力信号の論理和を、信号＋ＲＳＢＲ＿ＣＡＬＬ＿ＲＥＴＵＲＮ＿ＲＥＧ〈０：３〉として出力する。ここで、フラグ＋ＲＳＢＲ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬと＋ＲＳＢＲ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＥＴＵＲＮが同時に立つことはないので、ＯＲ回路６３は、ＡＮＤ回路６１、６２の出力信号を選択的に出力することになる。
【００７８】
信号＋ＲＳＢＲ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬ、＋ＲＳＢＲ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＥＴＵＲＮ、および＋ＲＳＢＲ＿ＣＡＬＬ＿ＲＥＴＵＲＮ＿ＲＥＧ〈０：３〉は、ぞれぞれ、図５の信号ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬ、ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＴＮ、＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＣＡＬＬ＿ＲＴＮ＿ＲＥＧ〈０：３〉として、分岐予測機構２２へ送出される。
【００７９】
ところで、前述したように、分岐命令（サブルーチンリターン相当の命令を含む）において、分岐先アドレスレジスタの番号として“０”を指定すると、分岐は行われない。また、逆に、デコード時にサブルーチンコール相当の命令と判別された命令でも、リンクレジスタの番号として“０”が指定された場合には、この命令をサブルーチンコール相当の命令として識別しない方がよい。
【００８０】
そこで、図９のような識別回路を分岐予測機構２２に設けて、送られてきたレジスタ番号が“０”でないときにのみ有効となる制御信号を生成する。図９において、ＮＡＮＤ回路７１は、信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＣＡＬＬ＿ＲＴＮ＿ＲＥＧ〈０：３〉の４つのビットの否定の論理積を求め、その論理積の否定を信号＋ＳＢＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＶＡＬとして出力する。
【００８１】
したがって、この出力信号は、信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＣＡＬＬ＿ＲＴＮ＿ＲＥＧ〈０：３〉が表すレジスタ番号が“０”でないときにのみ、論理“１”となり、リンクレジスタが有効であることを表す。この信号を用いたリンクスタック３３の制御については、後述することにする。
【００８２】
分岐命令が分岐しないことを表す分岐先アドレスレジスタの番号として、“０”以外の特定の番号が用いられた場合も、図９と同様の回路により同様の制御信号が生成される。
【００８３】
また、サブルーチンコールとして使用可能なｂａｓｓｍ命令については、ハードワイヤードではなく、マイコロコードにより実現されるため、ブランチヒストリ３４には登録されず、分岐履歴情報の更新時に情報が送られてこない。その代わりに、デコード時に生成された図５の信号＋Ｄ＿ＢＡＳＳＭが分岐予測機構２２に送出される。
【００８４】
そこで、図１０のような識別回路を分岐予測機構２２に設けて、ｂａｓｓｍ命令に関する制御を行う。ここでは、ｂａｓｓｍ命令に対応するリターン命令はｂｓｍのみであるものと仮定している。
【００８５】
図１０において、ＡＮＤ回路８１は、ラッチ回路８３の出力とＮＡＮＤ回路８４の出力の論理積をＯＲ回路８２に出力し、ＯＲ回路８２は、入力信号＋Ｄ＿ＢＡＳＳＭとＡＮＤ回路８１の出力信号の論理和をラッチ回路８３に出力する。ラッチ回路８３は、実質的にＳｅｔ−Ｒｅｓｅｔフリップフロップの動作を行い、ＯＲ回路８２の出力信号をラッチして、ＮＡＮＤ回路８４に出力する。
【００８６】
また、ＮＡＮＤ回路８４は、図５の信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＢＳＭと、図９の制御信号＋ＳＢＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＶＡＬと、ラッチ回路８３の出力信号の論理積の否定を、信号−ＳＢＲＴＮ＿ＢＡＳＳＭ＿ＢＳＭ＿ＲＴＮ＿ＶＡＬＩＤとして出力する。この信号−ＳＢＲＴＮ＿ＢＡＳＳＭ＿ＢＳＭ＿ＲＴＮ＿ＶＡＬＩＤは、論理“０”のとき、実行されたｂｓｍ命令が上記ｂａｓｓｍ命令に対応するリターン命令であることを表す。
【００８７】
このような識別回路によれば、分岐するｂａｓｓｍ命令が実行された場合には、信号＋Ｄ＿ＢＡＳＳＭが論理“１”となり、ラッチ回路８３の出力も論理“１”となる。そして、ラッチ回路８３の出力と図９の信号＋ＳＢＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＶＡＬが論理“１”である間に、ｂｓｍ命令の実行が完了して信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＢＳＭが論理“１”となると、実行されたｂｓｍ命令は上記ｂａｓｓｍ命令に対応するリターン命令であると識別される。
【００８８】
このとき、信号−ＳＢＲＴＮ＿ＢＡＳＳＭ＿ＢＳＭ＿ＲＴＮ＿ＶＡＬＩＤが論理“０”となるため、ＡＮＤ回路８１の出力も論理“０”となる。また、信号＋Ｄ＿ＢＡＳＳＭも論理“０”であるため、ラッチ回路８３の出力も論理“０”となる。
【００８９】
このように、ラッチ回路８３の出力信号は、ｂａｓｓｍ命令およびｂｓｍ命令が検出されたことを表す所定のフラグとして用いられ、分岐するｂａｓｓｍ命令が検出されたときにセットされ、それに対応するｂｓｍ命令が検出されたときにリセットされる。
【００９０】
また、信号−ＳＢＲＴＮ＿ＢＡＳＳＭ＿ＢＳＭ＿ＲＴＮ＿ＶＡＬＩＤと同時に、不図示の信号＋ＳＢＲＴＮ＿ＢＡＳＳＭ＿ＢＳＭ＿ＲＴＮ＿ＶＡＬＩＤも生成される。この信号＋ＳＢＲＴＮ＿ＢＡＳＳＭ＿ＢＳＭ＿ＲＴＮ＿ＶＡＬＩＤは、信号−ＳＢＲＴＮ＿ＢＡＳＳＭ＿ＢＳＭ＿ＲＴＮ＿ＶＡＬＩＤの否定に対応し、論理“１”のとき、実行されたｂｓｍ命令が上記ｂａｓｓｍ命令に対応するリターン命令であることを表す。
【００９１】
こうして識別されたｂａｓｓｍ命令に対応するｂｓｍ命令は、ブランチヒストリ３４あるいはリターンアドレススタック３５上では、リターン相当の命令とは認識されなくなる。なぜなら、ｂａｓｓｍ命令自身がコール相当の命令として登録されていないからである。
【００９２】
分岐予測機構２２は、分岐命令実行処理回路２５から送られてきた信号と、図９および図１０の識別回路により生成された特別な制御信号とを用いて、サブルーチンコール・リターン相当の命令を判別する。
【００９３】
図１１は、分岐予測機構２２内の判別回路を示している。図１１において、入力信号−ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＴＮは、図５の信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＴＮの否定に対応する。
【００９４】
また、入力信号＋ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫ０〈０：３〉は、リンクスタック３３の先頭エントリに保持されたレジスタ番号を表す。入力信号＋ＳＢＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＥＱ＿Ｅは、図５の信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＣＡＬＬ＿ＲＴＮ＿ＲＥＧ〈０：３〉がレジスタ番号“１４”を表すとき、論理“１”となり、それ以外の番号を表すとき、論理“０”となる。
【００９５】
ＡＮＤ回路９１は、図５の信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬと図９の信号＋ＳＢＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＶＡＬの論理積を、ＡＮＤ回路９２に出力する。ＡＮＤ回路９２は、ＡＮＤ回路９１の出力信号と信号−ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＴＮの論理積を、信号＋ＢＲ＿ＣＯＭＰ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬとして出力する。
【００９６】
この信号＋ＢＲ＿ＣＯＭＰ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬは、分岐予測機構２２において、サブルーチンコール相当の命令を表すフラグ（サブルーチンコールフラグ）として用いられる。このフラグが論理“１”のとき、分岐命令実行処理回路２５で実行された命令はサブルーチンコール相当の命令であると判別される。実行された命令がリンクレジスタとして番号“０”のレジスタを指定していた場合は、このフラグが論理“０”となり、サブルーチンコール相当の命令ではないと判別される。
【００９７】
また、ＥＸＮＯＲ回路１０１は、図５の信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＣＡＬＬ＿ＲＴＮ＿ＲＥＧ〈０：３〉と、信号＋ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫ０〈０：３〉を比較し、２つの信号の排他的論理和の否定を出力する。ＯＲ回路１０２は、ＥＸＮＯＲ回路１０１の出力信号と信号＋ＳＢＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＥＱ＿Ｅの論理和を出力する。
【００９８】
そして、ＡＮＤ回路１０３は、図５の信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＴＮと、図９の信号＋ＳＢＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＶＡＬと、図１０の信号−ＳＢＲＴＮ＿ＢＡＳＳＭ＿ＢＳＭ＿ＲＴＮ＿ＶＡＬＩＤと、ＯＲ回路１０２の出力信号の論理積を、信号＋ＢＲ＿ＣＯＭＰ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＴＮとして出力する。
【００９９】
この信号＋ＢＲ＿ＣＯＭＰ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＴＮは、分岐予測機構２２において、サブルーチンリターン相当の命令を表すフラグ（サブルーチンリターンフラグ）として用いられる。このフラグが論理“１”のとき、分岐命令実行処理回路２５で実行された命令はサブルーチンリターン相当の命令であると判別される。この判別動作は、対応する分岐履歴情報がブランチヒストリ３４やリターンアドレススタック３５に登録される前に行われる。
【０１００】
ＥＸＮＯＲ回路１０１、ＯＲ回路１０２、およびＡＮＤ回路１０３からなるサブルーチンリターン判別回路は、図３の比較回路３２に対応する。この判別回路によれば、ＥＸＮＯＲ回路１０１により、実行されたサブルーチンリターン相当の命令になり得る命令の分岐先アドレスレジスタの番号がリンクスタック３３の先頭エントリと比較され、それらが一致したとき、実行された命令がサブルーチンリターン相当の命令であると判別される。
【０１０１】
ただし、前述したように、分岐予測機構２２では、ｂａｓｓｍ命令に対応するｂｓｍ命令をリターン相当の命令として扱わないので、信号−ＳＢＲＴＮ＿ＢＡＳＳＭ＿ＢＳＭ＿ＲＴＮ＿ＶＡＬＩＤにより、ＡＮＤ回路１０３の出力が抑制されている。
【０１０２】
また、慣習的に、番号“１４”のレジスタは、サブルーチンリターンにおける分岐先アドレスレジスタとして用いられることが多い。そこで、このレジスタが分岐先アドレスレジスタとして指定された場合は、信号＋ＳＢＲＴＮ＿ＬＩＮＫ＿ＲＥＱ＿ＥＱ＿Ｅを用いて、ＥＸＮＯＲ回路１０１の比較結果にかかわらず、実行された命令をサブルーチンリターン相当の命令とみなしている。
【０１０３】
サブルーチンリターン相当の命令であることを表す分岐先アドレスレジスタの番号として、“１４”以外の特定の番号が用いられた場合も、図１１と同様の回路により同様の制御が行われる。
【０１０４】
こうして生成されたサブルーチンコールフラグとサブルーチンリターンフラグを用いて、リンクスタック３３は、図１２のような制御回路によりプッシュ動作とポップ動作を行う。ここでは、リンクスタック３３は２つのエントリからなるものとし、入力信号＋ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫ０〈０：３〉と＋ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫ１〈０：３〉は、それぞれ、先頭エントリ（エントリ０）と２番目のエントリ（エントリ１）に保持されたレジスタ番号を表している。
【０１０５】
また、入力信号−ＳＢＲＴＮ＿ＬＩＮＫ＿ＲＥＱ＿ＥＱ＿Ｅは、図１１の信号＋ＳＢＲＴＮ＿ＬＩＮＫ＿ＲＥＱ＿ＥＱ＿Ｅの否定に対応し、入力信号ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＴＡＫＥＮは、分岐命令による分岐が実行され、分岐履歴情報が更新されるときに、論理“１”となる。
【０１０６】
まず、ＡＮＤ回路１１１は、これらの２つの信号の論理積を出力する。ＡＮＤ回路１１２は、図１１のフラグ＋ＢＲ＿ＣＯＭＰ＿ＳＵＢＲＯＵＴＩＮＥ＿ＣＡＬＬとＡＮＤ回路１１１の出力信号の論理積を、動作信号＋ＰＵＳＨ＿ＲＴＮ＿ＳＴＡＣＫ＿ＬＩＮＫ＿ＲＥＧとして出力する。この信号は、リンクスタック３３およびリターンアドレススタック３５のプッシュ動作の指示に用いられ、サブルーチンコール相当の命令が実行されて分岐履歴情報が更新されるときに、論理“１”となる。
【０１０７】
また、ＡＮＤ回路１１３は、図１１のフラグ＋ＢＲ＿ＣＯＭＰ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＴＮとＡＮＤ回路１１１の出力信号の論理積を、動作信号＋ＰＯＰ＿ＲＴＮ＿ＳＴＡＣＫ＿ＬＩＮＫ＿ＲＥＧとして出力する。この信号は、リンクスタック３３およびリターンアドレススタック３５のポップ動作の指示に用いられ、サブルーチンリターン相当の命令が実行されて分岐履歴情報が更新されるときに、論理“１”となる。
【０１０８】
ここで、リンクレジスタの番号として“１４”を指定するサブルーチンコール相当の命令と、分岐先アドレスレジスタの番号として“１４”を指定するサブルーチンリターン相当の命令は、常にコール・リターン命令対を形成するものとすると、リンクスタック３３を用いなくてもこれらの対応関係を抽出することができる。
【０１０９】
そこで、このような場合にリンクスタック３３を動作させないように、信号−ＳＢＲＴＮ＿ＬＩＮＫ＿ＲＥＱ＿ＥＱ＿Ｅを用いて、プッシュ動作およびポップ動作の動作信号を抑制している。これにより、リンクスタック３３のエントリの浪費が防止され、少ない段数でも効率的な動作が可能になる。
【０１１０】
次に、ＡＮＤ回路１１４は、図５の信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＣＡＬＬ＿ＲＴＮ＿ＲＥＧ〈０：３〉と動作信号＋ＰＵＳＨ＿ＲＴＮ＿ＳＴＡＣＫ＿ＬＩＮＫ＿ＲＥＧの論理積を出力し、ＡＮＤ回路１１５は、信号＋ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫ１〈０：３〉と動作信号＋ＰＯＰ＿ＲＴＮ＿ＳＴＡＣＫ＿ＬＩＮＫ＿ＲＥＧの論理積を出力する。
【０１１１】
また、ＯＲ回路１１６は、ＡＮＤ回路１１４、１１５の出力信号の論理和を、信号＋ＳＥＴ＿ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫ０〈０：３〉として出力する。この信号は、リンクスタック３３の先頭エントリにセットされるレジスタ番号を表す。
【０１１２】
ここで、動作信号＋ＰＵＳＨ＿ＲＴＮ＿ＳＴＡＣＫ＿ＬＩＮＫ＿ＲＥＧと＋ＰＯＰ＿ＲＴＮ＿ＳＴＡＣＫ＿ＬＩＮＫ＿ＲＥＧが同時に論理“１”になることはないので、ＯＲ回路１１６は、ＡＮＤ回路１１４、１１５の出力信号を選択的に出力することになる。したがって、プッシュ動作の場合は、サブルーチンコール相当の命令により指定されたリンクレジスタの番号がセットされ、ポップ動作の場合は、リンクスタック３３の２番目のエントリに保持されたレジスタ番号がセットされる。
【０１１３】
また、ＡＮＤ回路１１７は、信号＋ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫ０〈０：３〉と動作信号＋ＰＵＳＨ＿ＲＴＮ＿ＳＴＡＣＫ＿ＬＩＮＫ＿ＲＥＧの論理積を、信号＋ＳＥＴ＿ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫ１〈０：３〉として出力する。この信号は、リンクスタック３３の２番目のエントリにセットされるレジスタ番号を表し、プッシュ動作の場合は、リンクスタック３３の先頭エントリに保持されたレジスタ番号に一致する。
【０１１４】
図１３は、リンクスタック３３内でレジスタ番号を保持するラッチ回路を示している。図１３において、入力信号−ＰＵＳＨ＿ＰＯＰ＿ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫは、プッシュ動作またはポップ動作が終了したときに論理“１”となる。
【０１１５】
ラッチ回路１２１は、図１２の信号＋ＳＥＴ＿ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫ０〈０：３〉を先頭エントリとしてラッチし、それを図１２の信号＋ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫ０〈０：３〉として出力する。また、ラッチ回路１２２は、図１２の信号＋ＳＥＴ＿ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫ１〈０：３〉を２番目のエントリとしてラッチし、それを図１２の信号＋ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫ１〈０：３〉として出力する。
【０１１６】
信号−ＰＵＳＨ＿ＰＯＰ＿ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫが論理“１”となると、これらのエントリへのレジスタ番号の登録が終了し、この信号が論理“０”になるまで、登録されたレジスタ番号が保持される。
【０１１７】
ところで、前述したｌｐｓｗ命令（複雑命令）は、サブルーチンコール・リターン命令のいずれにもなり得るため、コール・リターンの対応関係を崩すものと考えられる。あるいはまた、割り込みが発生した場合、それが割り込み処理の後に元のプログラムに戻らない種類の割り込みであれば、やはり、コール・リターンの対応関係を崩すものと考えられる。
【０１１８】
そこで、このような事象（命令や割り込み等）が発生した場合には、その命令や割り込みの実行時に、リンクスタック３３とリターンアドレススタック３５のエントリをすべてクリアして、保持された情報を無効化する。
【０１１９】
図１４は、分岐予測機構２２内の無効化回路を示している。図１４において、入力信号＋ＭＩＣＲＯ＿ＰＵＲＧＥ＿ＲＴＮ＿ＡＤＲＳ＿ＳＴＫは、リンクスタック３３とリターンアドレススタック３５のエントリをクリアする信号であり、コール・リターンの対応関係を崩すような命令や割り込みが発生したときに、論理“１”となる。
【０１２０】
ＮＯＲ回路１３１は、図１２の動作信号＋ＰＵＳＨ＿ＲＴＮ＿ＳＴＡＣＫ＿ＬＩＮＫ＿ＲＥＧと＋ＰＯＰ＿ＲＴＮ＿ＳＴＡＣＫ＿ＬＩＮＫ＿ＲＥＧ、および信号＋ＭＩＣＲＯ＿ＰＵＲＧＥ＿ＲＴＮ＿ＡＤＲＳ＿ＳＴＫの論理和の否定を、図１３の信号−ＰＵＳＨ＿ＰＯＰ＿ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫとして出力する。
【０１２１】
したがって、信号＋ＭＩＣＲＯ＿ＰＵＲＧＥ＿ＲＴＮ＿ＡＤＲＳ＿ＳＴＫが論理“１”となると、信号−ＰＵＳＨ＿ＰＯＰ＿ＲＴＮ＿ＬＩＮＫ＿ＲＥＧ＿ＳＴＫが論理“０”となり、図１３のラッチ回路１２１、１２２に保持されたレジスタ番号がクリアされる。
【０１２２】
また、サブルーチンコールに対応する戻り先、すなわち、サブルーチンコール相当の命令の直後の命令アドレスに戻らないサブルーチンリターン相当の命令を認識した場合、ブランチヒストリ３４に、そのサブルーチンリターン相当の命令の戻り先が異なることを示すフラグを設定することができる。
【０１２３】
図１５は、ＲＳＢＲ３６において、このようなフラグを生成する回路を示している。図１５において、入力信号＋Ｄ＿ＢＣは、デコーダ２３によりオペレーションコード“ｂｃ”が検出されたときに、論理“１”となる。入力信号−Ｄ＿ＤＩＳＰ＿ＥＱ＿０は、命令により指定されたディスプレイスメントが０でないときに、論理“１”となる。
【０１２４】
また、入力信号＋Ｄ＿ＢＲ＿ＥＱ＿Ｅ、＋Ｄ＿ＸＲ＿ＥＱ＿Ｅは、それぞれ、命令により指定されたベースレジスタ、インデックスレジスタの番号が“１４”のときに、論理“１”となる。これらの信号は、デコーダ２３からＲＳＢＲ３６に出力される。
【０１２５】
ＯＲ回路１４１は、信号＋Ｄ＿ＢＲ＿ＥＱ＿Ｅと＋Ｄ＿ＸＲ＿ＥＱ＿Ｅの論理和を表す信号を出力し、ＡＮＤ回路１４２は、信号＋Ｄ＿ＢＣと−Ｄ＿ＤＩＳＰ＿ＥＱ＿０、およびＯＲ回路１４１の出力信号の論理積を、信号＋Ｄ＿ＢＣ＿ＧＩＤＤＹ＿ＲＴＮとして出力する。
【０１２６】
また、ラッチ回路１４３は、ＯＲ回路１４１からの信号＋Ｄ＿ＢＣ＿ＧＩＤＤＹ＿ＲＴＮをラッチし、信号＋ＲＳＢＲ＿ＢＣ＿ＧＩＤＤＹ＿ＲＴＮとして出力する。この信号は、対応するＲＳＢＲ３６が有効である間、ラッチ回路１４３に保持され、サブルーチンリターン相当の命令の戻り先が異なることを示すフラグとして用いられる。
【０１２７】
このフラグ＋ＲＳＢＲ＿ＢＣ＿ＧＩＤＤＹ＿ＲＴＮは、信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＢＣ＿ＧＩＤＤＹ＿ＲＴＮとして分岐予測機構２２に送出され、図１６に示すように、ブランチヒストリ３４のエントリのフラグＧＩＤＤＹ ＲＴＮに設定される。
【０１２８】
図１６のブランチヒストリ３４のエントリには、フラグＧＩＤＤＹ ＲＴＮ以外に、分岐命令アドレスＩＡＲ、分岐先アドレスＴＩＡＲ、およびフラグＣＡＬＬ、ＲＴＮが格納されている。フラグＣＡＬＬ、ＲＴＮは、それぞれ、サブルーチンコールフラグ、サブルーチンリターンフラグに対応する。
【０１２９】
例えば、ディスプレイスメントｄが０でないような分岐命令“ｂｃ ｍ．ｄ（１４）”がデコードされた場合、信号＋Ｄ＿ＢＣ＿ＧＩＤＤＹ＿ＲＴＮが論理“１”となり、フラグ＋ＲＳＢＲ＿ＢＣ＿ＧＩＤＤＹ＿ＲＴＮが立つ。したがって、ブランチヒストリ３４にこの分岐命令が登録されたとき、対応するフラグＧＩＤＤＹ ＲＴＮに論理“１”が格納される。
【０１３０】
予測回路３１による分岐予測時に、このフラグＧＩＤＤＹ ＲＴＮが立っていた場合、リターンアドレススタック３５はリターン命令を予測したときと同様のポップ動作を行うが、予測回路３１は、リターンアドレススタック３５からポップされた分岐先アドレスではなく、ブランチヒストリ３４に登録された分岐先アドレスを、予測分岐先アドレスとして出力する。したがって、ブランチヒストリ３４により予測された分岐先の命令フェッチが行われ、リターンアドレススタック３５による予測結果は廃棄される。
【０１３１】
上述した実施形態においては、リンクスタック３３に登録されたリンクレジスタの番号と、実行された（実行される）命令の分岐先アドレスレジスタの番号を比較することで、その命令がサブルーチンリターン相当の命令であるか否かを判別している。これ以外の他の実施形態として、リンクスタック３３を用いず、リターンアドレススタック３５に登録されている戻り先アドレスと、実行された（実行される）命令の分岐先アドレスを比較することで、同様の判別を行うことも考えられる。
【０１３２】
この方法では、上述したｂｃ命令等のように、戻り先がコール命令の直後とならないリターン相当の命令が出現すると、認識されるコール・リターン対の対応関係が崩れてしまい、リターンアドレススタック３５の本来の性能が発揮できない。しかし、リンクスタック３３を新たに設ける必要がないというメリットがある。
【０１３３】
図１７は、分岐予測機構２２内でこのような判別を行う回路を示している。図１７において、信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＴＩＡＲは、サブルーチンリターン相当の命令になり得る命令の分岐先アドレスを表し、ＲＳＢＲ３６から送出される。
【０１３４】
比較回路１５１は、この信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＴＩＡＲをリターンアドレススタック３５の先頭エントリ（エントリ０）と比較し、それらが一致すると論理“１”の信号を出力する。ここでは、リターンアドレススタック３５は、ｎ段のスタックとして示されている。ＡＮＤ回路１５２は、図５の信号＋ＢＲＨＩＳ＿ＵＰＤＡＴＥ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＴＮと比較回路１５１の出力信号の論理積を、図１２の信号＋ＢＲ＿ＣＯＭＰ＿ＳＵＢＲＯＵＴＩＮＥ＿ＲＴＮとして出力する。
【０１３５】
図１７の判別回路は、図１１に示したサブルーチンリターン相当の命令の判別回路の代用となり、リンクスタック３３のエントリを参照しなくても、サブルーチンリターンフラグを生成することができる。したがって、この場合、リンクスタック３３は不要となる。
【０１３６】
以上説明した実施形態においては、主として、リンクスタック３３およびリターンアドレススタック３５を２段のスタックとしているが、任意の段数のスタックを用いた場合も、同様の制御を行うことができる。また、レジスタ番号や命令アドレス以外にも、サブルーチンの戻り先アドレスを指定する任意の情報を比較することで、サブルーチンコール・リターン命令対を認識することができる。
【０１３７】
【発明の効果】
本発明によれば、リターンアドレススタック等の分岐予測機構を有する情報処理装置において、正しいサブルーチンコール・リターン命令対を動的に抽出することができる。したがって、分岐予測機構におけるコール・リターン対の対応関係のズレが防止され、サブルーチンリターン相当の命令の分岐予測の精度が向上する。
【図面の簡単な説明】
【図１】本発明の分岐予測装置の原理図である。
【図２】命令コードを示す図である。
【図３】命令処理装置の構成図である。
【図４】リンクスタックとリターンアドレススタックの対応関係を示す図である。
【図５】命令処理装置で用いられる信号を示す図である。
【図６】第１の判別回路を示す図である。
【図７】登録回路を示す図である。
【図８】選択回路を示す図である。
【図９】第１の識別回路を示す図である。
【図１０】第２の識別回路を示す図である。
【図１１】第２の判別回路を示す図である。
【図１２】制御回路を示す図である。
【図１３】ラッチ回路を示す図である。
【図１４】無効化回路を示す図である。
【図１５】フラグ生成回路を示す図である。
【図１６】ブランチヒストリに登録されるエントリを示す図である。
【図１７】第３の判別回路を示す図である。
【図１８】サブルーチンコール・リターン命令対を示す図である。
【符号の説明】
１ 格納手段
２ 比較手段
３ 識別手段
４ スタック手段
５ プッシュ手段
６ リターンアドレススタック手段
１１ オペレーションコード
１２、１３ オペランド
２１ 命令フェッチ回路
２２ 分岐予測機構
２３ デコーダ
２４ 分岐先アドレス生成回路
２５ 分岐命令実行処理回路
２６ 命令実行完了処理回路
３１ 予測回路
３２、１５１ 比較回路
３３ リンクスタック
３５ リターンアドレススタック
３６ ＲＳＢＲ
４１、６１、６２、８１、９１、９２、１０３、１１１、１１２、１１３、１１４、１１５、１１７、１４２、１５２ ＡＮＤ回路
４２、４３、６３、８２、１０２、１１６、１４１ ＯＲ回路
５１、５２、８３、１２１、１２２、１４３ ラッチ回路
７１、８４ ＮＡＮＤ回路
１０１ ＥＸＮＯＲ回路
１３１ ＮＯＲ回路

Claims (13)

1. サブルーチンコール相当の命令が検出されたとき、該サブルーチンコール相当の命令により指定されたレジスタ手段のレジスタ番号を、サブルーチンの戻り先アドレスを指定する情報として格納する格納手段と、
   サブルーチンリターン相当の命令になり得る命令が検出されたとき、該サブルーチンリターン相当の命令になり得る命令により指定されるレジスタ番号と、前記格納手段に格納された前記戻り先アドレスを指定する情報としてのレジスタ番号とを比較し、比較結果を出力する比較手段と、
   前記比較結果に基づいて、前記サブルーチンコール相当の命令に対応するサブルーチンリターン相当の命令を識別する識別手段とを
   備えることを特徴とする分岐予測装置。
2. 前記レジスタ手段は、サブルーチンコール相当命令の命令により、戻り先のアドレスを格納する特定のレジスタ手段であることを特徴とする請求項１記載の分岐予測装置。
3. サブルーチンの戻り先アドレスを指定する情報を格納するスタック手段と、
   サブルーチンコール相当の命令が検出されたとき、前記戻り先アドレスを指定する情報を前記スタック手段にプッシュするプッシュ手段と、
   サブルーチンリターン相当の命令になり得る命令が検出されたとき、該サブルーチンリターン相当の命令になり得る命令の分岐先アドレスを指定する情報と、前記スタック手段の先頭エントリに格納された前記戻り先アドレスを指定する情報とを比較し、比較結果を出力する比較手段と、
   前記比較結果に基づいて、前記サブルーチンコール相当の命令に対応するサブルーチンリターン相当の命令を識別する識別手段とを備える
   ことを特徴とする分岐予測装置。
4. 前記プッシュ手段は、前記サブルーチンコール相当の命令により指定されたレジスタ手段のレジスタ番号を、前記戻り先アドレスを指定する情報として前記スタック手段にプッシュし、前記比較手段は、前記サブルーチンリターン相当の命令になり得る命令により指定された分岐先アドレスレジスタ手段のレジスタ番号と、前記スタック手段の先頭エントリに格納されたレジスタ番号とを比較し、前記識別手段は、比較された２つのレジスタ番号が一致したとき、該サブルーチンリターン相当の命令になり得る命令を、前記サブルーチンリターン相当の命令であると識別することを特徴とする請求項３記載の分岐予測装置。
5. 前記識別手段は、前記分岐先アドレスレジスタ手段のレジスタ番号が特定のレジスタ手段に対応するとき、前記比較結果にかかわらず、前記サブルーチンリターン相当の命令になり得る命令を、前記サブルーチンリターン相当の命令であると識別することを特徴とする請求項４記載の分岐予測装置。
6. 前記プッシュ手段は、前記レジスタ手段のレジスタ番号が特定のレジスタ手段に対応するとき、該レジスタ手段のレジスタ番号を前記スタック手段にプッシュしないことを特徴とする請求項４記載の分岐予測装置。
7. 前記識別手段が、前記サブルーチンリターン相当の命令になり得る命令を前記サブルーチンリターン相当の命令であると識別し、該サブルーチンリターン相当の命令による分岐が実行されたとき、前記スタック手段をポップするポップ手段をさらに備えることを特徴とする請求項３記載の分岐予測装置。
8. 分岐予測のための分岐履歴情報を格納する分岐予測テーブル手段をさらに備え、前記比較手段は、該分岐履歴情報が該分岐予測テーブル手段に登録されるとき、前記サブルーチンリターン相当の命令になり得る命令が指定するレジスタ番号と、前記戻り先アドレスを指定する情報としてのレジスタ番号とを比較することを特徴とする請求項１記載の分岐予測装置。
9. サブルーチンコールとサブルーチンリターンの対応関係を崩す可能性がある事象が発生したとき、前記格納手段に格納された情報を無効化する手段をさらに備えることを特徴とする請求項１記載の分岐予測装置。
10. 分岐予測のための分岐履歴情報を格納する分岐予測テーブル手段をさらに備え、前記サブルーチンコール相当の命令の直後に位置する命令アドレスに戻らないサブルーチンリターン相当の命令が検出されたとき、検出されたサブルーチンリターン相当の命令の戻り先が異なることを示すフラグを該分岐予測テーブル手段に設定する設定手段をさらに備えることを特徴とする請求項１記載の分岐予測装置。
11. 前記分岐予測テーブル手段は、前記サブルーチンの戻り先アドレスを格納するリターンアドレススタック手段を含み、分岐予測時に前記フラグが認識された場合、該リターンアドレススタック手段をポップし、ポップされた戻り先アドレスを予測分岐先として用いないことを特徴とする請求項１０記載の分岐予測装置。
12. 分岐予測のための分岐履歴情報を格納する分岐予測テーブル手段と、該分岐予測テーブル手段に登録されていないサブルーチンコール相当の命令が検出された場合には、所定のフラグをセットし、該登録されていないサブルーチンコール相当の命令に対応するサブルーチンリターン相当の命令が検出された場合には、該所定のフラグをリセットして、該分岐予測テーブル手段では該対応するサブルーチンリターン相当の命令をサブルーチンリターン相当の命令としては認識しない制御を行う手段とをさらに備えることを特徴とする請求項１記載の分岐予測装置。
13. サブルーチンコール相当の命令が検出されたとき、該サブルーチンコール相当の命令により指定されたレジスタ手段のレジスタ番号を、サブルーチンの戻り先アドレスを指定する情報として格納する格納手段と、
    サブルーチンリターン相当の命令になり得る命令が検出されたとき、該サブルーチンリターン相当の命令になり得る命令がレジスタ番号により指定するレジスタ手段が保持するレジスタ値と、前記格納手段に格納された前記戻り先アドレスを指定する情報としてのレジスタ番号が指定するレジスタ手段が保持するレジスタ値とを比較し、比較結果を出力する比較手段と、
    前記比較結果に基づいて、前記サブルーチンコール相当の命令に対応するサブルーチンリターン相当の命令を識別する識別手段とを
    備えることを特徴とする分岐予測装置。

Images