(57)【要約】本発明による情報処理装置では、フェッチした命令に対する分岐ヒストリ情報を記憶しておく。そして分岐予測をミスしたとき、記憶しておいたこの分岐ヒストリ情報を用いて、分岐予測に用いられるＢＨＲ情報を復元する。これにより、分岐予測ミスが生じても正確にＢＨＲ情報を復元することが出来る。よって予測精度を向上することができる。
2004068337.tif 000002
【特許請求の範囲】
【請求項１】
分岐予測制御に複数サイクル要する情報処理装置において、
フェッチした命令に対する分岐ヒストリ情報を記憶する分岐ヒストリ情報記憶手段と、
前記命令が分岐命令で、該分岐命令に対する分岐予測をミスしたとき、前記分岐ヒストリ情報記憶手段に記憶された分岐ヒストリ情報を用いて、分岐予測に用いられるＢＨＲ情報を復元するＢＨＲ再構成手段と、
を備えることを特徴とする情報処理装置。
【請求項２】
前記分岐ヒストリ情報は、前記複数サイクル分のＢＨＲ情報に基づいた情報を含むことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記分岐ヒストリ情報は、前記フェッチした命令の分岐予測に用いられたＢＨＲ情報及び他のＢＨＲ情報との差分情報を含むことを特徴とする請求項２に記載の情報処理装置。
【請求項４】
前記分岐予測制御に３サイクル要し、分岐ヒストリ情報は、フェッチした命令の分岐予測に用いられた第１のＢＨＲ情報、該第１のＢＨＲ情報の次に用いられた第２のＢＨＲ情報と該第１のＢＨＲ情報の差分を示す第１の差分情報、前記第２のＢＨＲ情報の次に用いられた第３のＢＨＲ情報と前記第２のＢＨＲ情報の差分を示す第２の差分情報を含むことを特徴とする請求項４に記載の情報処理装置
【請求項５】
条件分岐に対してＴａｋｅｎと予測し実際はＮｏｔ−Ｔａｋｅｎだった時、前記ＢＨＲ再構成手段は、前記分岐ヒストリ情報内の前記第１のＢＨＲ情報に前記第１の差分情報及び第２の差分情報を適用して求めてＢＨＲ情報を復元後の前記第１のＢＨＲ情報、前記第２のＢＨＲ情報及び前記第３のＢＨＲ情報とすることを特徴とする請求項４に記載の情報処理装置。
【請求項６】
非条件分岐に対して同一ｓｌｏｔ内でその命令より前にＮｏｔ−Ｔａｋｅｎと予測した命令がある時、前記ＢＨＲ再構成手段は、前記分岐ヒストリ情報内の前記第１のＢＨＲ情報に前記第１の差分情報及び第２の差分情報を適用し、更に１ｓｈｉｆｔして求めたＢＨＲ情報を復元後の前記第１のＢＨＲ情報、前記第２のＢＨＲ情報及び前記第３のＢＨＲ情報とすることを特徴とする請求項４に記載の情報処理装置。
【請求項７】
非条件分岐に対して同一ｓｌｏｔ内でその命令より前にＮｏｔ−Ｔａｋｅｎと予測した命令がない時、前記ＢＨＲ再構成手段は、前記分岐ヒストリ情報内の前記第１のＢＨＲ情報に前記第１の差分情報及び第２の差分情報を適用し、更に０ｓｈｉｆｔして求めたＢＨＲ情報を復元後の前記第１のＢＨＲ情報、前記第２のＢＨＲ情報及び前記第３のＢＨＲ情報とすることを特徴とする請求項４に記載の情報処理装置。
【請求項８】
条件分岐に対してＮｏｔ−Ｔａｋｅｎと予測し実際はＴａｋｅｎの場合でキャリーが発生する時、前記ＢＨＲ再構成手段は、前記分岐ヒストリ情報内の第１のＢＨＲ情報を復元後の第１のＢＨＲ情報、前記分岐ヒストリ情報内の第１のＢＨＲ情報に対して前記第１の差分情報を適用して求めたＢＨＲ情報を復元後の第２のＢＨＲ情報、前記分岐ヒストリ情報内の第１のＢＨＲ情報に対して前記第１の差分情報及び第２の差分情報を適用して求めたＢＨＲ情報を復元後の第３のＢＨＲ情報とすることを特徴とする請求項４に記載の情報処理装置。
【請求項９】
条件分岐に対してＮｏｔ−Ｔａｋｅｎと予測し実際はＴａｋｅｎの場合でキャリーが発生しない時、前記ＢＨＲ再構成手段は、前記分岐ヒストリ情報内の第１のＢＨＲ情報に対して前記第１の差分情報を適用して求めたＢＨＲ情報を復元後の第１のＢＨＲ情報、前記分岐ヒストリ情報内の第１のＢＨＲ情報に対して前記第１の差分情報及び第２の差分情報を適用して求めたＢＨＲ情報を復元後の第２のＢＨＲ情報、前記分岐ヒストリ情報内の第１のＢＨＲ情報に対して前記第１の差分情報、第２の差分情報及び固有値の第３の差分情報を適用して求めたＢＨＲ情報を復元後の第３のＢＨＲ情報とすることを特徴とする請求項４に記載の情報処理装置。
【請求項１０】
前記ＢＨＲ情報を前記複数サイクル分記憶するＢＨＲ情報記憶手段を更に備え、前記ＢＨＲ情報を更新する際、前記ＢＨＲ情報記憶手段内の複数のＢＨＲ情報を順番に更新することを特徴とする請求項１に記載の情報処理装置。
【請求項１１】
前記ＢＨＲ情報記憶手段内の複数のＢＨＲ情報の差分情報を記憶する差分情報記憶手段を更に備え、前記差分情報は前記ＢＨＲ情報記憶手段内のＢＨＲ情報が更新される際に共に更新されることを特徴とする請求項１０に記載の情報処理装置。
【請求項１２】
前記ＢＨＲ再構成手段は、前記分岐ヒストリ情報から分岐予測ミスの種別を判別し、該種別に基づいて前記ＢＨＲ情報を復元することを特徴とする請求項１に記載の情報処理装置。
【請求項１３】
前記ＢＨＲ再構成手段は、前記分岐ヒストリ情報から前記分岐予測ミスが、条件分岐に対してＴａｋｅｎと予測で実際はＮｏｔ−Ｔａｋｅｎ、非条件分岐に対して同一ｓｌｏｔ内でその命令より前にＮｏｔ−Ｔａｋｅｎと予測した命令がある、非条件分岐に対して同一ｓｌｏｔ内でその命令より前にＮｏｔ−Ｔａｋｅｎと予測した命令がない、条件分岐に対してＮｏｔ−Ｔａｋｅｎと予測し実際はＴａｋｅｎの場合でキャリーが発生する、及び条件分岐に対してＮｏｔ−Ｔａｋｅｎと予測し実際はＴａｋｅｎの場合でキャリーが発生しない、の５つの種別に対応するかどうかを判別することを特徴とする請求項１２記載の情報処理装置。
【請求項１４】
フェッチした分岐命令の分岐予測を行う為の分岐予測情報をフェッチアドレスに対応させて記憶するテーブルを更に備え、前記ＢＨＲ情報は、前記テーブルを参照する際に用いられることを特徴とする請求項１に記載の情報処理装置。
【請求項１５】
前記分岐予測制御に３サイクル要し、前記ＢＨＲ情報を３つ記憶するＢＨＲ情報記憶手段を更に備えることを特徴とする請求項１に記載の情報処理装置。
【請求項１６】
分岐予測制御に複数サイクル要する情報処理装置で用いられる分岐予測制御装置であって、
フェッチした命令に対する分岐ヒストリ情報を記憶する分岐ヒストリ情報記憶手段と、
前記命令が分岐命令で、該分岐命令に対する分岐予測をミスしたとき、前記分岐ヒストリ情報記憶手段に記憶された分岐ヒストリ情報を用いて、分岐予測に用いられるＢＨＲ情報を復元するＢＨＲ再構成手段と、
を備えることを特徴とする分岐予測制御装置。
【請求項１７】
分岐予測制御に複数サイクル要する情報処理装置で用いられ、分岐予測ミスの際、分岐予測に用いられるＢＨＲ情報を復元するＢＨＲ再構成装置であって、
分岐予測ミスの通知と共に分岐予測ミスした命令に対する分岐ヒストリ情報を受け取る手段と、
前記命令が分岐命令で、該分岐命令に対する分岐予測をミスしたとき、前記分岐ヒストリ情報記憶手段に記憶された分岐ヒストリ情報を用いて、分岐予測に用いられるＢＨＲ情報を復元する手段と、
を備えることを特徴とするＢＨＲ再構成装置。
【請求項１８】
分岐予測制御に複数サイクル要する情報処理装置で用いられ、分岐予測ミスの際、分岐予測に用いられるＢＨＲ情報を復元するＢＨＲ情報復元方法であって、
フェッチした命令に対する分岐ヒストリ情報を記憶し、
前記命令が分岐命令で、該分岐命令に対する分岐予測をミスしたとき、記憶した分岐ヒストリ情報を用いて、分岐予測に用いられるＢＨＲ情報を復元することを特徴とする分岐予測制御装置。
【発明の詳細な説明】
【技術分野】  本発明はパイプライン処理を行なう情報処理装置についての技術に関し、更に詳しくは分岐予測におけるパイプライン制御についての技術に関する。
【背景技術】  半導体テクノロジの進歩と共に高集積化、高クロック化が進んでいるマイクロプロセサに代表される情報処理装置では、近年、命令の実行処理速度を上げる為に、１つの命令を実行する際に行われる処理を複数のステージに分け、各ステージの処理機構を独立して並列動作させることにより処理の高速化を図るパイプライン技術が用いられている。また多くの情報処理装置では、このようなパイプラインを複数備えるスーパスカラとよばれる手法が採用されており、複数のパイプラインで投機的に命令が実行されている。
パイプライン処理を行なう場合、いくつもの命令を流れ作業的に同時に実行するので、分岐命令でメモリ内の別の部分に分岐してしまうと、処理を開始している後続の命令を全て破棄しなくてはならず、処理効率が低下する。これを防ぐための手法として、情報処理装置では分岐予測が行われる。分岐予測では、分岐命令が分岐するかどうかを予測し、分岐しそうな場合は分岐先の命令をパイプラインに流しこむ。
この分岐予測の手法の一つとして、分岐の履歴を記録しておき、この履歴に基づいて分岐するかどうかを予測する方式がある。
この方式では、ＢＨＴ（Ｂｒａｎｃｈ  Ｈｉｓｔｏｒｙ  Ｔａｂｌｅ）と呼ばれる分岐履歴に基づいた分岐予測情報を記録した記憶領域を参照して分岐の強度を判断し、分岐予測を行なう。この時ＢＨＴを検索するタグとしては、命令フェッチ時のアドレス（以下ＦＰＣという）、及びグローバルヒストリレジスタ（以下ＢＨＲ（Ｂｒａｎｃｈ  Ｈｉｓｔｏｒｙ  Ｒｅｇｉｓｔｅｒ）という）内の値（以下ＢＨＲ情報という）の組み合わせを使用する方式が一般的である。
図１は、分岐履歴を用いた方法による分岐予測の説明図である。
同図において、ＢＨＴ１はフェッチされたアドレス屋ＢＨＲ情報に基づく不図示のタグと、そのタグに対応するアドレスの分岐情報において分岐が行われたかどうかに基づいた２ｂｉｔの分岐予測情報を記録するテーブルである。またＢＨＲ２は、直近に実行された複数（同図の場合５つ）の分岐命令において、どのような分岐予測が行われたかを示す履歴を記録する複数ビット（同図の場合５ビット）構成のレジスタである。
分岐予測を行なう際、情報処理装置内では、フェッチされたプログラムカウンタ値（ＦＰＣ）とその時のＢＨＲ２内のＢＨＲ情報からタグを生成し、このタグを用いてＢＨＴ１を検索してＢＨＴ１から読み出した分岐予測情報から分岐予測を行なう。
ＢＨＴ１には、分岐予測情報としてＳｔｒｏｎｇｌｙ  Ｎｏｔ−Ｔａｋｅｎ、Ｗｅａｋｌｙ  Ｎｏｔ−Ｔａｋｅｎ、Ｓｔｒｏｎｇｌｙ  Ｔａｋｅｎ及びＷｅａｋｌｙ  Ｔａｋｅｎの４つのいずれかが記憶されている。そして、ＢＨＴ１から読み出された分岐予測情報が、Ｓｔｒｏｎｇｌｙ  Ｎｏｔ−ＴａｋｅｎまたはＷｅａｋｌｙ  Ｎｏｔ−Ｔａｋｅｎの時はＮｏｔ−Ｔａｋｅｎと予測され、Ｓｔｒｏｎｇｌｙ  Ｔａｋｅｎ又はＷｅａｋｌｙ  Ｔａｋｅｎの時はＴａｋｅｎと予測される。尚このＢＨＴ１内の分岐予測情報は、実際に分岐が行われたかどうかの結果に基づいて順次更新されてゆく。尚以下の説明では、分岐命令において、分岐を行なう若しくは行なうと予測する場合はＴａｋｅｎ、分岐を行なわない若しくは行なわないと予測する場合はＮｏｔ−Ｔａｋｅｎという。
また分岐予測の結果が求まると、ＢＨＲ２では１ビット左シフトされ、予測の結果が最下位のビットにセットされる。例えば分岐（Ｔａｋｅｎ）と予測した場合には１が、非分岐（Ｎｏｔ−Ｔａｋｅｎ）を予測した場合には０がセットされる。尚以下の説明でＢＨＲの最下位ビットに１がセットされてシフトされる場合を１ｓｈｉｆｔ、０がセットされてシフトされる場合を０ｓｈｉｆｔという。
分岐命令において分岐が行われるかどうかを命令フェッチ時に予測しながら処理を先に進める分岐予測の手法をパイプラインに適用した場合、分岐予測をミスした時には、パイプラインの各スロットに現在の処理に関与しないステージが生じるいわゆるパイプラインバブルが生じ、性能が大幅に低下する。
分岐予測では、予測ミスによる性能に対するペナルティが大きいため、性能向上のためには、予測精度を高めることが重要となる。また予測制度を高める為には、分岐予測を外した場合に分岐予測前の状態を如何に再現するかも重要になる。
分岐予測に対する技術としては、様々な提案が成されているが、例えば特開平６−３０１５３４号公報（情報処理装置）に開示された手法がある。
上記公報には、分岐命令より前の命令を実行するパイプラインと分岐命令後の命令を先行実行するパイプラインとを２つの実行パイプラインを持つ構成が開示されている。そして分岐予測を外した場合は、パイプラインを切り替えることによって状態を元に戻すことができる。
また分岐履歴を用いたものに対するものとして、特開２００１−２４３０６９号公報（分岐予測装置及び分岐予測方法）には、分岐予測情報の状態遷移が実際の分岐動作とはずれるのに対処する為、分岐予測の状態遷移をパイプライン上の同一分岐命令の分岐予測状態にバイパスする手法が開示されている。
分岐履歴を用いた方法では、従来、パイプラインの浅い構造の情報処理装置においては、ＢＨＴ１を検索して分岐予測を行ってから、次のフェッチを行なうまでが１サイクル内で行われるため、ＦＰＣ、ＢＨＲ情報の更新制御が容易であった。しかし近年、動作クロックの高周波化によって性能を向上させることが一般的になっており、そのためにパイプラインを深くする制御構造が用いられるようになっている。そのため、このような情報処理装置では、命令フェッチ時の分岐予測が、数サイクルに渡って行われるようになる。
またパイプラインが深い場合、命令フェッチアドレス（ＦＰＣ）とＢＨＲ１内の値によって、ＢＨＴ２を検索して分岐予測を行なう構成の情報処理装置では、命令フェッチを開始してからある一定のサイクル後に分岐予測を行なう制御構造となる場合がある。そして、分岐予測をミスすると、ミスした分岐命令の直後に戻って再フェッチする必要があるが、その為に分岐命令用のリザベーションステーションに分岐命令に関する情報を格納しておき、分岐ミスが確定するとリザベーションステーションに格納された情報を用いて、その分岐命令をフェッチしたときの状態に戻してフェッチをやり直す。
この時ＢＨＲ情報についても、各パイプラインで更新制御を行ない分岐命令をフェッチした時点での値に戻すことになるが、パイプラインが深く、フェッチが数サイクルにわたる場合、ＢＨＲ情報についてはフェッチした時点のパイプラインの状態をすべて復元することはできず、例えばＢＨＲ情報の復元処理として、分岐予測ミスが発生した時のＢＨＲ情報をそのまま用いてＢＨＲ情報を復元する等の処理が行われる。
しかしこの場合には、分岐命令をフェッチした時点のＢＨＲ情報が正確に復元されるわけではないので、分岐予測の精度が低下してしまうという問題がある。
【発明の開示】
本発明による情報処理装置は、分岐予測制御に複数サイクル要する情報処理装置を前提とし、分岐ヒストリ情報記憶手段及びＢＨＲ再構成手段を備える。
分岐ヒストリ情報記憶手段は、フェッチした命令に対する分岐ヒストリ情報を記憶する。
ＢＨＲ再構成手段と前記命令が分岐命令で、該分岐命令に対する分岐予測をミスしたとき、前記分岐ヒストリ情報記憶手段に記憶された分岐ヒストリ情報を用いて、分岐予測に用いられるＢＨＲ情報を復元する。
これにより分岐予測ミスが生じても正確にＢＨＲ情報を復元することが出来る。よって予測精度を向上することができる。
また分岐ヒストリ情報を、前記複数サイクル分のＢＨＲ情報に基づいた情報、例えば前記フェッチした命令の分岐予測に用いられたＢＨＲ情報及び他のＢＨＲ情報との差分情報を含む構成とすることにより、また簡易な構成や制御によって正確な分岐予測制御を実現することが出来る。
【図面の簡単な説明】  図１は、分岐履歴を用いた方法による分岐予測の説明図である。
図２は、本実施例における情報処理装置の分岐予測に関する部分の構成を示すブロック図である。
図３は、本実施例の情報処理装置における、予測ミス時のＢＨＲ情報の復元の原理を示す説明図である。
図４は、分岐予測が全て正しかった場合の本実施例における情報処理装置でのＢＨＲ情報の変化例を示す図である。
図５は、Ｎｏｔ−Ｔａｋｅｎと予測した分岐命令が実際にはＴａｋｅｎだった場合の本実施例における情報処理装置でのＢＨＲ情報の変化例を示す図である。
図６（ａ）はキャリーが発生しない場合、図６（ｂ）はキャリーが発生する場合を示したｓｌｏｔ及びキャリーの説明図である。
図７は、Ｔａｋｅｎと予測して実際にはＮｏｔ−Ｔａｋｅｎだった場合で、キャリーが発生しない場合のＢＨＲ情報の変化例を示す図である。
図８は、Ｔａｋｅｎと予測して実際にはＮｏｔ−Ｔａｋｅｎだった場合で、キャリーが発生する場合のＢＨＲ情報の変化例を示す図である。
図９は、ＢＨＲ及びそのの周辺部分の構成例を示すブロック図である。
図１０は、ＢＨＲ再構成部の概略構成を示す図である。
図１１は、ＢＨＲ再構成部の構成をより詳細に示す図である。
図１２は、分岐予測が正しかった場合の本実施例における情報処理装置でのＢＨＲ情報の更新動作例を示す図である。
図１３は、分岐予測ミスをした場合の本実施例における情報処理装置でのＢＨＲ情報の更新動作例を示す図である。
【発明を実施するための最良の形態】  図２は、本実施例における情報処理装置の分岐予測に関する部分の構成を示すブロック図である。
同図において、本実施例における情報処理装置は、ＢＨＲ１１、ＢＨＴ１２、ｂｒｈｉｓ（ｂｒａｎｃｈ  ｈｉｓｔｏｒｙ）１３、１次命令キャッシュ１４、分岐予測制御部１５、命令デコード部１７、分岐命令専用リザベーションステーション１８、ＢＨＲ再構成部１９、整数命令専用リザベーションステーション２０、浮動小数点演算専用リザベーションステーション２１、ＬＯＡＤ／ＳＴＯＲＥ命令専用リザベーションステーション２２、整数演算器２３、浮動小数点演算器２４及び１次データキャッシュ２５を備えている。
ＢＨＲ１１は、グローバルヒストリレジスタで、直近に実行された複数の分岐命令（本実施例の場合、分岐命令１０個分）において、Ｔａｋｅｎだった場合は‘１’、Ｎｏｔ−Ｔａｋｅｎだった場合は‘０’として記録された分岐履歴を保持する１０ビットのレジスタである。また本実施例における情報処理装置では、このＢＨＲ１１が複数のＢＨＲ情報を記憶する構成を持つ。
ＢＨＴ１２は、フェッチされたアドレス等から生成される不図示のタグと、そのタグに対応するアドレスにおいて実際に分岐が行われたかどうかに基づく２ビットの分岐予測情報を記録するテーブルである。本実施例では、ＢＨＴ１２は、２ビット×１６ｋアドレスの構成をもつものとする。ｂｒｈｉｓ１３は、過去に実行された分岐命令についての情報を持つテーブルで、参照されたアドレスの命令コードが分岐命令かどうか、分岐命令の場合そのターゲットアドレスやどんな属性の分岐命令か等の情報が記録されている。ｂｒｈｉｓ１３は、アドレスから生成されたＴａｇを記憶しており、フェッチアドレスから生成されるＴａｇがｂｒｈｉｓ１３内のＴａｇとを比較し（Ｔａｇ  Ｍａｔｃｈ）、ヒットしてｂｒｈｉｓ１３から情報が読み出されると、分岐予測制御部１５はフェッチされた命令コードが分岐命令だと判断する。１次命令キャッシュ１４は、１次の命令キャッシュメモリで命令デコード部１７はこの１次命令キャッシュ１４からデコードする命令コードを読み出す。
分岐予測制御部１５は、分岐予測処理を司るもので、ＦＰＣによるｂｒｈｉｓ１３とのＴａｇ  Ｍａｔｃｈの結果からＦＰＣによって参照される命令が分岐命令かどうかを調べ、また同時にＦＰＣとその時のＢＨＲ１１内のＢＨＲ情報によってＢＨＴ１２から読み出された分岐予測情報に基づいて分岐命令がＴａｋｅｎかＮｏｔ−Ｔａｋｅｎかの分岐予測を行なう。またその分岐予測の結果に基づいて、ＢＨＲ１１内のＢＨＲ情報を更新する。
命令Ｆｅｔｃｈ制御部１６は、分岐予測制御部１５による分岐予測結果等に基づいてフェッチアドレスを生成するもので、このフェッチアドレスを用いて、ＢＨＴ１２、ｂｒｈｉｓ１３及び一次命令キャッシュ１４が参照される。命令デコード部１７は、フェッチされた命令コードを一次命令キャッシュ１４から読み出してデコードし、その結果に基づいてフェッチされた命令を整数命令専用リザベーションステーション２０、浮動小数点演算専用リザベーションステーション２１及びＬＯＡＤ／ＳＴＯＲＥ命令専用リザベーションステーション２２のいずれかに振り分ける。分岐命令専用リザベーションステーション１８は、条件分岐命令の分岐条件となる各種状態を示すコンディションコードレジスタを監視して、分岐予測制御部１５によって行われた分岐予測の結果がミスしたかどうかを判断し、ミスした場合には復元パス２６を介して予測ミスの通知と共にＢＨＲ情報を復元するための分岐ヒストリ情報を命令Ｆｅｔｃｈ制御部１６及びＢＨＲ再構成部１９に送る。
ＢＨＲ再構成部１９は、分岐命令専用リザベーションステーション１８から予測ミスの通知を受けると分岐ヒストリ情報に基づいて、ＢＨＲ情報を予測をミスした分岐命令がフェッチされた時の状態に戻す。このＢＨＲ再構成部１９の動作についての詳細は後述する。
整数命令専用リザベーションステーション２０及び浮動小数点演算専用リザベーションステーション２１は、それぞれ整数演算命令及び浮動小数点演算命令用のリザベーションステーションで、命令デコード部１７によって振り分けられた命令を蓄え、順番の組換え等を行った後整数演算器２３若しくは浮動小数点演算器２４に送出する。またＬＯＡＤ／ＳＴＯＲＥ命令専用リザベーションステーション２２は、メモリへのＬＯＡＤ／ＳＴＯＲＥ命令用のリザベーションステーションで、命令デコード部１７によって流し込まれた命令に基づいて１次データキャッシュ２５にアクセスする。
整数演算器２３は、整数演算命令を処理する演算器、浮動小数点演算器２４は、浮動小数点演算命令を実行処理する演算器である。１次データキャッシュ２５は、１次のデータキャッシュメモリで、ＬＯＡＤ／ＳＴＯＲＥ命令専用リザベーションステーション２２は、ＬＯＡＤ／ＳＴＯＲＥ命令に対してこの１次データキャッシュ２５に対してアクセスする。
命令Ｆｅｔｃｈ制御部１６によって示されたフェッチ時のアドレス（ＦＰＣ）に基づいて、一次命令キャッシュ１４から読み出された命令コードは命令デコード部１７によってデコードされる。また分岐予測制御部１５ではその時のＢＨＲ１１内のＢＨＲ情報とＦＰＣを用いてＢＨＴ１２及びｂｒｈｉｓ１３を参照し、分岐予測を行う。そして分岐予測に用いたＢＨＲ情報は、パイプラインのステージの進行と共に、その差分情報等と共に分岐ヒストリ情報として命令デコード部１７、分岐命令専用リザベーションステーション１８と転送されてゆく。そして分岐命令専用リザベーションステーション１８において、分岐予測ミスと判断され、再フェッチを行なう際には、分岐命令専用リザベーションステーション１８は対応する分岐ヒストリ情報をＢＨＲ再構成部１９に送り、ＢＨＲ再構成部１９はこの分岐ヒストリ情報に基づいて、この分岐命令に対して正確に予測が行われた状態にＢＨＲ情報を復元する。
図３は、本実施例の情報処理装置における、予測ミス時のＢＨＲ情報の復元の原理を示す説明図である。
本実施例の情報処理装置では、図３（ａ）に示すように、各パイプライン毎にそのパイプラインの命令がフェッチされた時のＢＨＲ情報を示す分岐ヒストリ情報が、分岐予測制御部１５から、命令Ｆｅｔｃｈ制御部１６、命令デコード部１７、分岐命令専用リザベーションステーション１８と転送されてゆく。分岐命令専用リザベーションステーション１８には、複数の命令の分岐ヒストリ情報が保持されており、分岐命令専用リザベーションステーション１８で分岐予測ミスと判断されると、その分岐命令の分岐ヒストリ情報が分岐ミスの通知と共にＢＨＲ再構成部１９に送られる。そしてＢＨＲ再構成部１９では、この分岐ヒストリ情報に基づいてｎサイクル分のＢＨＲ情報を復元してＢＨＲ１１に戻し、再フェッチの時には、この復元されたＢＨＲ情報に基づいて分岐予測が行われる。尚このｎの値は、パイプラインの構成や、命令フェッチに要するステージ数等に基づいて決まる。
分岐ヒストリ情報としては、様々なものが考えられるが、例えば命令コードをフェッチしてからｎサイクル分全てのＢＨＲ情報を分岐ヒストリ情報として持つ構成が考えられる。或いは、図３（ｂ）のようにフェッチした時のＢＨＲ情報及びこのＢＨＲ情報とその後のｎサイクル分のＢＨＲ情報との差分情報を分岐ヒストリ情報として持つ構成が考えられる。
図３（ｂ）に示した差分情報を持つ構成の場合、ハードウエア資源を節約できるので、以下の例ではこの構成を用いた例を示す。
本実施例における情報処理装置は、命令フェッチ部分において以下のような３つのステージを持つパイプライン構造を備えるものとする。
Ａステージで、ＢＨＴ１２、ｂｒｈｉｓ１３、一次命令キャッシュ１４を検索する。
Ｔステージで、ｂｒｈｉｓ１３、ＢＨＴ１２の読み出しを行なう。
Ｕステージで、ｂｒｈｉｓ１３のＴａｇ  Ｍａｔｃｈを行ないＴａｇ  Ｍａｔｃｈ情報に基づき、ＢＨＴ１２による分岐予測を行なう。
このように、本実施例でのパイプラインでは、ＡステージでＢＨＴ情報を用いてＢＨＴ１２を参照し、３サイクル後のＵステージで分岐予測の結果が確定する。よってＢＨＲ１１は、３サイクル分のＢＨＲ情報（ＢＨＲ０、ＢＨＲ１、ＢＨＲ２）及びその差分情報を記憶する構成を持つ。
またＢＨＲ情報の更新条件としては様々なものが考えられるが、今回の例では次のような条件で更新されるものとする。
（１）条件分岐命令でＴａｋｅｎと予測→１ｓｈｉｆｔ
（２）条件分岐命令でＮｏｔ−Ｔａｋｅｎと予測→０ｓｈｉｆｔ
（３）分岐命令がない（ｂｒｈｉｓ１３にヒットしない）→そのまま
（４）非条件分岐命令でＴａｋｅｎと予測し、前のｓｌｏｔに条件分岐命令がない場合→そのまま（ｓｌｏｔについては後述する）
（５）非条件分岐命令でＴａｋｅｎと予測し、前のｓｌｏｔに条件分岐がある場合→０ｓｈｉｆｔ
各パイプライン間のＢＨＲ情報の依存関係が複雑になるため、ＢＨＲ１１は、３サイクル分のＢＨＲ情報（ＢＨＲ０、ＢＨＲ１、ＢＨＲ２）を記憶し、フェッチ時に使用するＢＨＲ情報をＢＨＲ０−＞ＢＨＲ１−＞ＢＨＲ２−＞ＢＨＲ０と巡回させて更新し、使用する。また使用するＢＨＲ情報をポインタで示し、フェッチする毎にこのポインタをインクリメントさせる。
また、ＢＨＲ１１は３つのＢＨＲ情報に対して以下のような互いの差分情報ＢＨＲ０＿ＲＥＳＴＯＲＥ、ＢＨＲ１＿ＲＥＳＴＯＲＥ及びＢＨＲ２＿ＲＥＳＴＯＲＥを持ち、ＢＨＲ情報の更新時にはその差分情報も更新される。
ＢＨＲ０＿ＲＥＳＴＯＲＥ［１：０］：ＢＨＲ２［９：０］→ＢＨＲ０［９：０］の差分情報
ＢＨＲ１＿ＲＥＳＴＯＲＥ［１：０］：ＢＨＲ０［９：０］→ＢＨＲ１［９：０］の差分情報
ＢＨＲ２＿ＲＥＳＴＯＲＥ［１：０］：ＢＨＲ１［９：０］→ＢＨＲ２［９：０］の差分情報
各差分情報は２ビットの情報で、以下のような意味を持つ。
‘１１’：１ｓｈｉｆｔ
‘０１’：０ｓｈｉｆｔ
‘ｘ０’：変更なし（ｘは任意）
例えばＢＨＲ０＿ＲＥＳＴＯＲＥが‘１１’の時は、ＢＨＲ０は、ＢＨＲ２を１ｓｈｉｆｔすることによって求まる。
まず分岐予測結果が正しかった場合のＢＨＲ情報の更新動作を説明する。
上記した本実施例のパイプラインの構成の場合、ＢＨＲ情報を使ってＢＨＴ１２を参照してから分岐予測結果が確定するまで２サイクルかかる為に、分岐予測の結果が確定する２サイクル前のＢＨＲ情報を使ってＢＨＴ１２の検索を行なうこととなる。そして、分岐予測の結果がＴａｋｅｎだった場合、次の分岐先アドレスのフェッチを開始する時に２サイクルのバブルが発生する。またＮｏｔ−Ｔａｋｅｎ予測時には、フェッチ時に参照に用いたＢＨＲ情報のみが更新され、分岐時、及び再フェッチ時には全てのＢＨＲ情報が同時に更新される。
図４は、本実施例における情報処理装置でのＢＨＲ情報の変化例を示す図である。同図は、分岐予測が全て正しかった場合を例として示している。尚同図において命令Ｉ１、Ｉ２、Ｉ３は分岐命令で、それぞれの分岐予測結果がＮｏｔ−Ｔａｋｅｎ、Ｎｏｔ−Ｔａｋｅｎ、Ｔａｋｅｎであったものとする。また命令Ｉ１より前にフェッチされた不図示の３命令は分岐命令でなく、これらの命令によってはＢＨＲ情報は更新されなかったものとする。
図４において、まず周期１で分岐命令Ｉ１がフェッチされ、この分岐命令Ｉ１がＢＨＲ０の値０００１によるＢＨＴ１２の参照結果から、周期３でＮｏｔ−Ｔａｋｅｎと予測されたとする。この間、周期２で分岐命令Ｉ２、周期３で分岐命令Ｉ３がフェッチされ、またＢＨＲ１の値０００１とＢＨＲ２の値０００１を用いてＢＨＴ１２が参照される。
分岐予測の結果がＮｏｔ−Ｔａｋｅｎの時には、再フェッチの必要はないので命令Ｉ１及びＩ２の予測結果が確定してもそのまま継続される。しかし、Ｔａｋｅｎ予測の時は、分岐先の命令をフェッチしなければならないので、再フェッチが行われ以降の命令が無効となり、パイプラインバブルが生じる。同図の場合、命令Ｉ３に対する分岐予測結果が、周期４でＴａｋｅｎと確定し、続く命令Ｉ４、Ｉ５部分がパイプラインバブルとなる。
そして、分岐命令Ｉ３の分岐先から命令Ｉ６、Ｉ７、Ｉ８が順にフェッチされるが、この時命令Ｉ６、Ｉ７、Ｉ８に対するＢＨＲ情報は、命令Ｉ３に対するＢＨＲ情報（ＢＨＲ１：０００１）を元にして、命令Ｉ３の予測結果（Ｔａｋｅｎ）からこれを１ｓｈｉｆｔして求める。
このように本実例における情報処理装置では、ＢＨＲ情報を用いるサイクルと分岐予測結果が確定するサイクルが異なっており、分岐予測の結果がＴａｋｅｎとなってもＢＨＲ情報を正確に復元することが出来る。
次に、分岐予測をミスした場合の動作について説明する。
フェッチ時に用いられたＢＨＲ情報は、差分情報等再フェッチ時に必要となる他の情報と共に、命令Ｆｅｔｃｈ制御部１６から命令デコード部１７を経て、分岐命令専用リザベーションステーション１８へ送られる。
分岐命令が参照するコンディションコードレジスタの状態が確定することによって、分岐命令で実際に分岐が行われるかどうかが決まる。分岐命令専用リザベーションステーション１８は、コンディションコードレジスタの状態から分岐予測による分岐方向と実際の分岐方向が一致したかどうかの判断を行ない、一致しなかった場合は、再フェッチ要求と共に、再フェッチ開始アドレス、分岐ヒストリ情報等を命令Ｆｅｔｃｈ制御部１６へ送る。このうち分岐ヒストリ情報は、フェッチ時のＢＨＲ情報を復元するのに使用される。
図５は、Ｎｏｔ−Ｔａｋｅｎと予測した分岐命令が実際にはＴａｋｅｎだった場合の本実施例における情報処理装置でのＢＨＲ情報の変化例を示す図である。
図５において、命令Ｉ１はＮｏｔ−Ｔａｋｅｎと予測されていたが、コンディションコードレジスタの状態から実際はＴａｋｅｎであったとする。
周期１のＡステージでフェッチされた命令Ｉ１は、周期３のＵステージまでに分岐予測が行われる。本例では、Ｎｏｔ−Ｔａｋｅｎと予測しているので、命令Ｉ２、Ｉ３は破棄されずそのまま処理されてゆく。
命令Ｉ１の分岐条件が確定し、コンディションコードレジスタの状態から分岐予測をミスしたのが分かると、分岐命令専用リザベーションステーション１８は、命令Ｆｅｔｃｈ制御部１６及びＢＨＲ再構成部１９に分岐予測ミスを通知し、ＢＨＲ再構成部１９では、分岐ヒストリ情報から命令Ｉ１がＴａｋｅｎと予測したようなＢＨＲ情報を復元して、分岐先の命令Ｉ４、Ｉ５、Ｉ６のフェッチに用いるＢＨＲ情報を生成する。
命令Ｉ４のＢＨＲ情報は、命令Ｉ１で用いられたＢＨＲ情報（ＢＨＲ０：０００１）と差分情報から命令Ｉ２で用いられたＢＨＲ情報（ＢＨＲ１：００１０）を復元し、この命令Ｉ２で用いられたＢＨＲ情報と差分情報から命令Ｉ３で用いられたＢＨＲ情報（ＢＨＲ２：００１０）を復元する。そしてこの命令Ｉ３で用いられたＢＨＲ情報に対して、命令Ｉ１でＴａｋｅｎと予測されたかのように１ｓｈｉｆｔを行ない、命令Ｉ４、Ｉ５、Ｉ６に用いるＢＨＲ情報を生成する。図５では、命令Ｉ１で用いられたＢＨＲ情報（ＢＨＲ０：０００１）に対して差分情報Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１＝ＢＨＲ１＿ＲＥＳＴＯＲＥ＝０１を適用してＢＨＲ１：００１０を復元し、これに差分情報（Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２＝ＢＨＲ２＿ＲＥＳＴＯＲＥ＝００を適用してＢＨＲ２：００１０を復元する。そしてこのＢＨＲ２：００１０に対して、１ｓｈｉｆｔして、命令Ｉ４、Ｉ５、Ｉ６に用いるＢＨＲ情報ＢＨＲ０：０１０１、ＢＨＲ１：０１０１、ＢＨＲ２：０１０１が生成される。尚Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１及びＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２については後述する。
次にＴａｋｅｎと予測した分岐命令が実際にはＮｏｔ−Ｔａｋｅｎだった場合におけるＢＨＲ情報の復元について説明する。
Ｔａｋｅｎと予測して実際にはＮｏｔ−Ｔａｋｅｎだった場合は、キャリーが発生する場合と発生しない場合とで再フェッチを開始する位置が異なる。
本実施例の情報処理装置では、命令コードを特定の数づつ同時にフェッチする。予測の対象となった分岐命令がこのフェッチ単位の最後の命令（対象となっている分岐命令が遅延分岐命令の場合には、遅延分前にずれた命令）であるとき、キャリーが発生し、再フェッチを開始する位置がずれる。従って、ＢＨＲ情報の復元処理もキャリーが発生する場合としない場合とで、場合分けする必要がある。
図６は、ｓｌｏｔ及びキャリーの説明図である。本実施例の情報処理装置は、ｓｌｏｔ単位で命令コードを同時にフェッチする。図６の例では１ｓｌｏｔ＝８としており、同図（ａ）は、キャリーが発生しない場合、同図（ｂ）はキャリーが発生する場合を示している。
図６（ａ）では、命令Ｉ５が分岐予測がＴａｋｅｎと予測して実際にはＮｏｔ−Ｔａｋｅｎだった命令で、この場合にはキャリーは発生せず、命令Ｉ１〜Ｉ８が再フェッチされる。
また同図（ｂ）では、命令Ｉ８が分岐予測がＴａｋｅｎと予測して実際にはＮｏｔ−Ｔａｋｅｎだった命令で、この場合はキャリーが発生し、命令Ｉ８に続く命令Ｉ９〜Ｉ１６が再フェッチされる。尚遅延分岐命令の場合には、その遅延の大きさ分前の命令、同図（ｂ）の場合命令Ｉ７やＩ６が、分岐予測がＴａｋｅｎと予測して実際にはＮｏｔ−Ｔａｋｅｎだった命令の時にキャリーが発生する。
図７は、Ｔａｋｅｎと予測して実際にはＮｏｔ−Ｔａｋｅｎだった場合で、キャリーが発生しない場合のＢＨＲ情報の変化例を示す図である。
同図は、分岐命令Ｉ１でＴａｋｅｎと予測して実際にはＮｏｔ−Ｔａｋｅｎだった場合を例として示している。
命令Ｉ１の分岐条件が確定し、コンディションコードレジスタの状態から分岐予測をミスし、実際はＮｏｔ−Ｔａｋｅｎだったのが分かると、分岐命令専用リザベーションステーション１８は、命令Ｆｅｔｃｈ制御部１６及びＢＨＲ再構成部１９に分岐予測ミスを通知し、命令Ｉ１の部分から再フェッチを行なわせる。
キャリーが発生しない場合、同図の網かけ部分に示したように命令Ｉ１で用いられたＢＨＲ情報から復元するので、分岐命令専用リザベーションステーション１８が予測ミスと判断するとＢＨＲ再構成部１９では、分岐ヒストリ情報内の命令Ｉ１で用いられたＢＨＲ情報ＢＨＲ０：０００１に差分情報Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１＝‘０１’を用いて命令Ｉ２で用いられたＢＨＲ情報ＢＨＲ１：００１０を復元し、これに差分情報Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２＝‘００’を適用して命令Ｉ３で用いられたＢＨＲ情報ＢＨＲ１：００１０を復元する。そして命令Ｉ１の位置から再フェッチが行われまた命令Ｉ１はＴａｋｅｎ予測なので、命令Ｉ３で用いられたＢＨＲ情報ＢＨＲ１：００１０に対して１ｓｈｉｆｔしてＢＨＲ情報０１０１を求め、これを命令Ｉ４、Ｉ５、Ｉ６で用いられるＢＨＲ情報ＢＨＲ０、ＢＨＲ１及びＢＨＲ２にする。
図８は、Ｔａｋｅｎと予測して実際にはＮｏｔ−Ｔａｋｅｎだった場合で、キャリーが発生する場合のＢＨＲ情報の変化例を示す図である。
命令Ｉ１の分岐条件が確定し、コンディションコードレジスタの状態から分岐予測をミスしたのが分かると、分岐命令専用リザベーションステーション１８は、命令Ｆｅｔｃｈ制御部１６及びＢＨＲ再構成部１９に分岐予測ミスを通知し、命令２の部分から再フェッチを行なわせる。
キャリーが発生する場合、同図で網かけで示した命令Ｉ２、Ｉ３、Ｉ４で用いられたＢＨＲ情報を復元する。分岐命令専用リザベーションステーション１８が予測ミスの通知を受けると、ＢＨＲ再構成部１９では、分岐ヒストリ情報内の命令Ｉ１で用いられたＢＨＲ情報ＢＨＲ０：０００１と差分情報Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１＝‘１０’を用いて命令Ｉ２で用いられたＢＨＲ情報ＢＨＲ１：００１０を復元し、これに差分情報Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２＝‘００’を適用して命令Ｉ３で用いられたＢＨＲ情報ＢＨＲ１：００１０を復元する。
そして命令Ｉ３で用いられたＢＨＲ情報ＢＨＲ１：００１０に対してＴａｋｅｎ予測なので１ｓｈｉｆｔしてＢＨＲ情報０１０１を求め、これを命令Ｉ４、Ｉ５、Ｉ６で用いるＢＨＲ情報とする。ただし、命令Ｉ４のＢＨＲ情報は、命令Ｉ１がＮｏｔ−Ｔａｋｅｎだったので命令Ｉ３で用いられたＢＨＲ情報ＢＨＲ１：００１０に差分情報Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１＝‘０１’（固定値）を適用してＢＨＲ０：０１００となる。
図９は、ＢＨＲ１１及びそのの周辺部分の構成例を示すブロック図である。
同図は、ＢＨＲ１１及び分岐予測制御部１５と命令Ｆｅｔｃｈ制御部１６の関連部分を示しており、ＢＨＲ情報記憶レジスタ３１−１〜３１−３、演算器３２−１〜３２−３及び差分情報記憶レジスタ３３−１〜３３−３が図２のＢＨＲ１１に、命令Ｆｅｔｃｈ制御部３６が命令Ｆｅｔｃｈ制御部１６のＢＨＲとの関連部分、他の部分が分岐予測制御部１５のＢＨＲとの関連部分、及びＢＨＴ３８がＢＨＴ１２に対応する。
同図においてＢＨＲ情報記憶レジスタ３１−１〜３１−３は、ＢＨＲ０、ＢＨＲ１及びＢＨＲ２の３つのＢＨＲ情報を記憶する。また差分情報記憶レジスタ３３−１〜３３−３は、上記した差分情報ＢＨＲ０＿ＲＥＳＴＯＲＥ、ＢＨＲ１＿ＲＥＳＴＯＲＥ及びＢＨＲ２＿ＲＥＳＴＯＲＥを記憶する２ビットのレジスタで、これらの値はＢＨＲ情報記憶レジスタ３１内のＢＨＲ情報の値を用いて演算器３２によって求められる。ＢＨＲ情報記憶レジスタ３１−１〜３１−３内のＢＨＲ情報は、命令フェッチ時にＢＨＲ０、ＢＨＲ１、ＢＨＲ２、ＢＨＲ０、・・・と順番に用いられる。
カウンタ３４は、ＢＨＲ０、ＢＨＲ１及びＢＨＲ２の中で、どれが最新の値か、すなわち、現在ＢＨＲ情報記憶レジスタ３１−１〜３１−３のうちどのレジスタに最新のＢＨＲ情報が格納されているかを示すカウンタで、ＢＨＲ情報が更新される度にＢＨＲ０−＞ＢＨＲ１−＞ＢＨＲ２−＞ＢＨＲ０と変化する。カウンタ３５は、次にＢＨＲ０、ＢＨＲ１及びＢＨＲ２のどれを用いてフェッチするかを示すカウンタで、フェッチが行われる度にＢＨＲ０−＞ＢＨＲ１−＞ＢＨＲ２−＞ＢＨＲ０と変化する。
ＢＨＲ更新回路３７は、ＢＨＲ情報が更新される際、最新のＢＨＲ情報から更新されたＢＨＲ情報を生成し、これを対応するＢＨＲ情報記憶レジスタ３１に送る。またセレクタ３９はＢＨＲ情報記憶レジスタ３１−１〜３１−３のうちカウンタ３４が示す最新のＢＨＲ情報を記憶しているものを選択し、保持内容をＢＨＲ更新回路３７に出力する。
セレクタ４０は、ＢＨＲ情報記憶レジスタ３１−１〜３１−３のうちカウンタ３５が示すフェッチに用いるＢＨＲ情報を記憶しているものを選択する。このＢＨＲ情報が用いられてＢＨＴ３８は参照される。
命令Ｆｅｔｃｈ制御部３６内のＩＢＲ  ＢＨＲ３６１は、命令Ｆｅｔｃｈ制御部３６から、命令デコード部１７を介して分岐命令専用リザベーションステーション１８に送られるｉｂｒ＿ｂｈｒ情報を格納するバッファで、ＢＨＴ３８の参照に用いたＢＨＲ情報及び他のＢＨＲ情報との差分情報を保持する。
ｉｂｒ＿ｂｈｒ情報は、分岐命令をフェッチした際、ＢＨＴ１２の参照に用いられたＢＨＲ情報を示すＰ＿ＲＥＦＩＤＣＨ＿ＢＨＲ及びそのＢＨＲ情報と他の２つのＢＨＲ情報との差分情報Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１、Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２及びＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ３から構成されている。Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲと差分情報の関係は、Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１がＰ＿ＲＥＦＩＤＣＨ＿ＢＨＲと次のＢＨＲ情報との差分を示し、Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１が次のＢＨＲ情報とその次のＢＨＲ情報との差分情報を示す。例えばＰ＿ＲＥＦＩＤＣＨ＿ＢＨＲがＢＨＲ１対するものであった時、Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１にはＢＨＲ１とＢＨＲ２との差分を示すＢＨＲ２＿ＲＥＳＴＯＲＥがなり、Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２にはＢＨＲ２とＢＨＲ０との差分を示すＢＨＲ０＿ＲＥＳＴＯＲＥがなる。尚Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ３は、キャリーが発生した場合にのみ用いられるもので、固定値（‘０１’）となっている。
バッファ３６３−１〜３６３−３は、カウンタ３４の値をバッファリングするもので、ＡステージでＢＨＴ３８の参照に用いられたＢＨＲ情報が格納されているＢＨＲ情報記憶レジスタ３１を示すカウンタ値は、バッファ３６３−１〜３６３−３によって、Ｔ、Ｕ、Ｍステージまで保持され、Ｍステージの時セレクタ３６２にＢＨＲ情報記憶レジスタ３１内のＢＨＲ０〜ＢＨＲ２とその差分情報の選択を指示する。
命令がフェッチされ、ＢＨＴ３８の参照に用いられたＢＨＲ情報は、その命令がＭステージに達するとセレクタ３６２によって差分情報と共に選択され、ＩＢＲ  ＢＨＲ３６１に格納される。ＩＢＲ  ＢＨＲ３６１内のｉｂｒ＿ｂｈｒ情報は、命令デコード部１７を介して分岐命令専用リザベーションステーション１８に送られる。分岐命令専用リザベーションステーション１８で、その命令が分岐予測ミスと判断されるとｉｂｒ＿ｂｈｒ情報を含む分岐ヒストリ情報が分岐予測ミスの通知と共にＢＨＲ再構成部１９に送られ、ＢＨＲ再構成部１９では、分岐ヒストリ情報を元にＢＨＲ情報を復元する。
図１０は、ＢＨＲ再構成部１９の概略構成を示す図である。
ＢＨＲ再構成部１９は、分岐ミス種別判定回路４１とＢＨＲ復元マルチプレクサ４２から構成される。
分岐ミス種別判定回路４１は、分岐ヒストリ情報と共に送られてくる分岐命令の種類（条件分岐／非条件分岐等）や予測ミスの種類（分岐方向の予測ミス／分岐アドレスのミス等）を示す分岐命令種別情報から分岐ミスの種別を判別し、ＢＨＲ復元マルチプレクサ４２に通知する。ＢＨＲ復元マルチプレクサ４２は、分岐ミス種別判定回路４１から通知された種別に応じて分岐ヒストリ情報内のＢＨＲ情報や差分情報からＢＨＲ情報を復元する。
図１１は、ＢＨＲ再構成部１９の構成をより詳細に示す図である。
分岐ミス種別判定回路４１に入力される分岐命令種別情報（ｂ）ａには、ｐ＿ｔｉａｒ＿ｍａｔｃｈ、ｐ＿ｐｒｅｄ＿ｔａｋｅｎ、ｐ＿ｔａｋｅｎ、ｐ＿ａｌｗａｙｓ、ｐ＿ｈａｓ＿ｎｏｔ＿ｔａｋｅｎ及びｐ＿ｉａｒ＿ｃａｒｒｙがある。
ｐ＿ｔｉａｒ＿ｍａｔｃｈは、分岐先であるターゲットアドレスが予測どおりだったかどうかを示す情報である。ｐ＿ｐｒｅｄ＿ｔａｋｅｎは、分岐命令に対する分岐予測がＴａｋｅｎだったかどうかを示す情報である。ｐ＿ｔａｋｅｎは、分岐命令が実際にはＴａｋｅｎだったかどうかを示す情報である。ｐ＿ａｌｗａｙｓは、その分岐命令が無条件分岐命令かどうかを示す情報である。ｐ＿ｈａｓ＿ｎｏｔ＿ｔａｋｅｎは、その分岐命令と同じｓｌｏｔ内のその分岐命令より前にＮｏｔ−Ｔａｋｅｎだった分岐命令があるかどうかを示す情報である。ｐ＿ｉａｒ＿ｃａｒｒｙは、再フェッチの際キャリーが発生するかどうかを示す１ビットの情報である。
分岐ミス種別判定回路４１は、これらの情報から分岐ミスの種別を、（１）条件分岐でＴａｋｅｎ予測で実際はＮｏｔ−Ｔａｋｅｎ、（２）非条件分岐で同一ｓｌｏｔ内でその命令より前にＮｏｔ−Ｔａｋｅｎと予測した命令がある、（３）非条件分岐で同一ｓｌｏｔ内でその命令より前にＮｏｔ−Ｔａｋｅｎと予測した命令がない、（４）条件分岐でＮｏｔ−Ｔａｋｅｎ予測で実際はＴａｋｅｎの場合でキャリーが発生する、（５）条件分岐でＮｏｔ−Ｔａｋｅｎ予測で実際はＴａｋｅｎの場合でキャリーが発生しない、の５つに判別する。
上記種別かどうかの判定は、以下の論理式によって行われる。尚下記式で‘＆’はＡＮＤ、‘｜’はＯＲ、‘〜’は否定を意味し、またｐ＿ｔａｋｅｎ＿ｍｉｓｓは（〜ｐ＿ｔｉａｒ＿ｍａｔｃｈ＆ｐ＿ｐｒｅｄ＿ｔａｋｅｎ＆ｐ＿ｔａｋｅｎ）｜（〜ｐ＿ｐｒｅｄ＿ｔａｋｅｎ＆ｐ＿ｔａｋｅｎ）、ｐ＿ｔａｋｅｎ＿ｍｉｓｓはｐ＿ｐｒｅｄ＿ｔａｋｅｎ＆〜ｐ＿ｔａｋｅｎを表す。
（１）ｐ＿ｔａｋｅｎ＿ｍｉｓｓ  ＆〜ｐ＿ａｌｗａｙｓ
（２）ｐ＿ｔａｋｅｎ＿ｍｉｓｓ  ＆ｐ＿ａｌｗａｙｓ＆  ｐ＿ｈａｓ＿ｎｏｔ＿ｔａｋｅｎ
（３）ｐ＿ｔａｋｅｎ＿ｍｉｓｓ  ＆ｐ＿ａｌｗａｙｓ＆  〜ｐ＿ｈａｓ＿ｎｏｔ＿ｔａｋｅｎ
（４）ｐ＿ｔａｋｅｎ＿ｍｉｓｓ  ＆〜ｐ＿ｉａｒ＿ｃａｒｒｙ
（５）ｐ＿ｔａｋｅｎ＿ｍｉｓｓ  ＆  ｐ＿ｉａｒ＿ｃａｒｒｙ
ＢＨＲ復元マルチプレクサ４２は、その命令の分岐予測に用いたＢＨＲ情報を示す１０ビットのＰ＿ＲＥＦＩＤＣＨ＿ＢＨＲ、２ビットの差分情報Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１、Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２及びＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ３を用い、分岐ミス種別判定回路４１からの種別に判定結果に基づいて、ＢＨＲ情報を復元する。
分岐ミス種別判定回路４１から分岐ミスが種別（１）と通知された時は、ＢＨＲ復元マルチプレクサ４２は、Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲ（ｂ）をシフタ４２１によってＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１（ｃ）に基づいてシフトし、これをシフタ４２２によってＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２（ｄ）に基づいてシフトした値を、シフタ４２４で１ｓｈｉｆｔした値をセレクタ４２６で選択し、バッファ５１、５２、５３を介して復元されたＢＨＲ情報Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲ０（Ａ）、Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲ１（Ｂ）及びＰ＿ＲＥＦＩＤＣＨ＿ＢＨＲ２（Ｃ）を出力する。分岐ミス種別判定回路４１から分岐ミスが種別（２）と通知された時は、シフタ４２２の出力をシフタ４２５で０ｓｈｉｆｔした値をセレクタ４２６で選択し、バッファ５１、５２、５３を介して復元されたＢＨＲ情報Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲ０（Ａ）、Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲ１（Ｂ）及びＰ＿ＲＥＦＩＤＣＨ＿ＢＨＲ２（Ｃ）を出力する。また分岐ミスが種別（３）と通知された時は、シフタ４２２の出力をセレクタ４２６で選択して復元されたＢＨＲ情報Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲ０（Ａ）、Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲ１（Ｂ）及びＰ＿ＲＥＦＩＤＣＨ＿ＢＨＲ２（Ｃ）を出力する。
分岐ミス種別判定回路４１から分岐ミスが種別（４）と通知された時は、セレクタ４２７でＰ＿ＲＥＦＩＤＣＨ＿ＢＨＲ（ｂ）を選択して復元されたＢＨＲ情報（ＢＨＲ０）Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲ０（ｄ）として出力し、セレクタ４２８でシフタ４２１の出力を選択して復元されたＢＨＲ情報（ＢＨＲ１）Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲ０（ｅ）として出力し、セレクタ４２９でシフタ４２２の出力を選択して復元されたＢＨＲ情報（ＢＨＲ２）Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲ２（ｆ）として出力する。また分岐ミスが種別（５）と通知された時は、セレクタ４２７でシフタ４２１の出力を選択してＰ＿ＲＥＦＩＤＣＨ＿ＢＨＲ０（ｄ）として出力し、セレクタ４２８でシフタ４２２の出力を選択してＰ＿ＲＥＦＩＤＣＨ＿ＢＨＲ０（ｅ）として出力し、セレクタ４２９でシフタ４２３の出力を選択してＰ＿ＲＥＦＩＤＣＨ＿ＢＨＲ２（ｆ）として出力する。
次に分岐ミスによる再フェッチ時のＢＨＲ情報の復元の仕方について説明する。
再フェッチ時には、分岐ヒストリ情報を用いてＢＨＲ再構成部１９が、ＢＨＲ０、ＢＨＲ１、ＢＨＲ２を復元する。以下に予測がＮｏｔ  Ｔａｋｅｎ、実際がＴａｋｅｎの時と予測がＴａｋｅｎの時と、実際がＮｏｔ  Ｔａｋｅｎの時とに場合分けして説明する。
（１）Ｎｏｔ  Ｔａｋｅｎと予測し実際はＴａｋｅｎだった場合、及びＴａｋｅｎ予測で実際もＴａｋｅｎだったが分岐先アドレスが誤っていた場合
この場合、予測ミスした分岐命令の分岐先から再フェッチを開始する。
（１−１）予測ミスした分岐命令が条件分岐命令の場合（図１１の種別（１）に該当）
ＢＨＴを参照するのに用いたＢＨＲ情報Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲ［９：０］に差分情報Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１［１：０］、Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２［１：０］を順に適用し、さらに１ｓｈｉｆｔを行って生成したＢＨＲをＢＨＲ０、ＢＨＲ１、ＢＨＲ２とする。また差分情報ＢＨＲ０＿ＲＥＳＴＯＲＥ、ＢＨＲ１＿ＲＥＳＴＯＲＥ、ＢＨＲ２＿ＲＥＳＴＯＲＥへは‘００’を書き込む。
（１−２）予測ミスした分岐命令が非条件分岐命令の場合（図１１の種別（２）、（３）に該当）
Ｐ＿ＲＥＦＩＤＣＨ＿ＢＨＲ［９：０］にＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１［１：０］、Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２［１：０］を順に適用する。そしてｐ＿ｈａｓ＿ｎｏｔ＿ｔａｋｅｎが真のとき（ｓｌｏｔ内にその分岐命令より前にＮｏｔ−Ｔａｋｅｎだった分岐命令がある場合）０ｓｈｉｆｔした後そのまま生成したＢＨＲをＢＨＲ０、ＢＨＲ１、ＢＨＲ２とし、ｈａｓ＿ｎｏｔ＿ｔａｋｅｎが真で無い場合はそのまま生成したＢＨＲをＢＨＲ０、ＢＨＲ１、ＢＨＲ２とする。また差分情報ＢＨＲ０＿ＲＥＳＴＯＲＥ、ＢＨＲ１＿ＲＥＳＴＯＲＥ、ＢＨＲ２＿ＲＥＳＴＯＲＥへは‘００’を書き込む。
（２）Ｔａｋｅｎと予測し実際はＮｏｔ  Ｔａｋｅｎだった場合
この場合、予測ミスした分岐命令の次の命令から再フェッチ開始する。
（２−１）予測ミスした分岐命令がフェッチ単位の最後の命令ではなく、キャリーが発生しない場合（図１１の種別（４）に該当）
Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ［９：０］をＢＨＲＸ（その分岐命令が用いていたＢＨＲ（ＢＨＲ０／１／２））へ、Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ［９：０］にＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１［１：０］を適用した値をＢＨＲ（Ｘ＋１）（Ｘ＝２のときはＸ＋１＝０）へ、そのＢＨＲ（Ｘ＋１）にＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２［１：０］を適用した値をＢＨＲ（Ｘ＋２）（Ｘ＝１のときＸ＋２＝０、Ｘ＝２のときＸ＋２＝１）へそれぞれ書き込む。また差分情報ＢＨＲ０＿ＲＥＳＴＯＲＥ、ＢＨＲ１＿ＲＥＳＴＯＲＥ、ＢＨＲ２＿ＲＥＳＴＯＲＥへは‘００’を書き込む。
（２−２）予測ミスした分岐命令アドレスがフェッチ単位の最後であり、キャリーが発生する場合（図１１の種別（５）に該当）
Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ［９：０］にＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１［１：０］を適用した値をＢＨＲＸ（その分岐命令が用いていたＢＨＲ（ＢＨＲ０／１／２））へ、Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲ［９：０］にＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２［１：０］を適用した値をＢＨＲ（Ｘ＋１）（Ｘ＝２のときはＸ＋１＝０）へ、そのＢＨＲ（Ｘ＋１）にＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ３［１：０］を適用した値をＢＨＲ２へそれぞれ書き込む。また差分情報ＢＨＲ０＿ＲＥＳＴＯＲＥ、ＢＨＲ１＿ＲＥＳＴＯＲＥ、ＢＨＲ２＿ＲＥＳＴＯＲＥへは‘００’を書き込む。
図１２及び図１３は、本実施例における情報処理装置でのＢＨＲ情報の更新動作例を示す図である。
図１２は分岐予測が正しかった場合を示しており、（１）で再フェッチにより、フェッチを開始し分岐予測の結果、ＵステージでＮｏｔ−Ｔａｋｅｎと予測したとする。この予測結果に基づいて最新のＢＨＲ情報であるＢＨＲ２を０ｓｈｉｆｔしてＢＨＲ０を更新し、また差分情報ＢＨＲ０＿ＲＥＳＴＯＲＥを‘１０’に書き換える。そして、（１）で用いたＢＨＲ情報であるＢＨＲ０と差分情報ＢＨＲ１＿ＲＥＳＴＯＲＥ及びＢＨＲ２＿ＲＥＳＴＯＲＥは、ｉｂｒ＿ｂｈｒ情報として命令Ｆｅｔｃｈ制御部１６から一次命令キャッシュ１４から命令コードが届くのと同じタイミングで命令デコード部１７へ送られる。
またこの間（２）で（１）の次のアドレスをフェッチし、この命令はＴａｋｅｎと予測したとする。Ｔａｋｅｎ予測の場合には、（２）で用いたＢＨＲ情報であるＢＨＲ１を元に３つ全部のＢＨＲ情報を書き換える。また（２）で用いたＢＨＲ情報であるＢＨＲ１と差分情報ＢＨＲ２＿ＲＥＳＴＯＲＥ及びＢＨＲ０＿ＲＥＳＴＯＲＥが、ｉｂｒ＿ｂｈｒ情報として命令Ｆｅｔｃｈ制御部１６から命令デコード部１７へ送られる。
（２）でＴａｋｅｎと予測するまでの間、（３）、（４）がフェッチされるが、これらは（２）がＴａｋｅｎ予測となった時点で破棄され、ＢＨＲ情報の更新やｉｂｒ＿ｂｈｒ情報の登録は行われない。
（２）の分岐予測の結果に基づいて分岐先の命令（５）がフェッチされる。この（５）のフェッチには、（２）で用いられたＢＨＲ２を１ｓｈｉｆｔしたものが用いられる。
図１３は分岐予測ミスをした場合のＢＨＲ情報の更新動作例を示している。
図１３では、（１）、（２）では分岐予測の結果が判明するまでは、図１２の時と同様に処理が行われる。コンディションコードレジスタの状態から（２）のＴａｋｅｎ予測が外れたことが判明すると、実際の分岐先の（３）’から再フェッチを行なう。
この時ＢＨＲ情報は、（２）で命令デコード部１７に送られたｉｂｒ＿ｂｈｒ情報内のＰ＿ＲＥＩＦＣＨ＿ＢＨＲからＢＨＲ０を復元し、これにＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１（ＢＨＲ１＿ＲＥＳＴＯＲＥ）を適用してＢＨＲ１を復元し、更にこれにＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２（ＢＨＲ０＿ＲＥＳＴＯＲＥ）を適用してＢＨＲ２を復元する。尚キャリーが発生する場合には、Ｐ＿ＲＥＩＦＣＨ＿ＢＨＲにＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ１（ＢＨＲ１＿ＲＥＳＴＯＲＥ）を適用してＢＨＲ０を復元し、これにＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ２（ＢＨＲ０＿ＲＥＳＴＯＲＥ）を適用してＢＨＲ１を復元し、更にこれにＰ＿ＲＥＩＦＣＨ＿ＢＨＲ＿ＲＥＳＴＯＲＥ３（固定値）を適用してＢＨＲ２を復元する。
このように、本実施例の情報処理装置では、分岐予測ミスが生じても正確にＢＨＲ情報を復元することが出来る。その為、精度の高い分岐予測を実現でいる。また複雑な回路構成や制御を用いなくてもＢＨＲ情報の復元を実現することが出来る。
尚本実施例の情報処理装置では、図１に示したようにＢＨＲ情報は、情報処理装置内で分岐予測を行い、この分岐予測結果に対する分岐履歴に基づいたものを用いているが、本発明はこのようなＢＨＲ情報のみに適用されるものではなく、他の形式のもの、例えばＢＨＲ情報が、コンパイル時に分岐予測を行って命令コードにその結果を埋め込む方式において、この埋め込まれた予測内容に対するカウントを行ったものに対しても適用することが出来る。
【産業上の利用可能性】  本発明に拠れば、高クロック化に伴って深いＰｉｐｅｌｉｎｅ構造をとり、分岐予測制御に数サイクル要するような情報処理装置であっても、正確な分岐予測制御を行うことができるため、予測精度を向上することができる。
また制御や構成の簡易さを保ちながら正確な分岐予測制御を実現することが出来る。
【図１】
2004068337.tif 000003
【図２】
2004068337.tif 000004
【図３】
2004068337.tif 000005
【図４】
2004068337.tif 000006
【図５】
2004068337.tif 000007
【図６】
2004068337.tif 000008
【図７】
2004068337.tif 000009
【図８】
2004068337.tif 000010
【図９】
2004068337.tif 000011
【図１０】
2004068337.tif 000012
【図１１】
2004068337.tif 000013
【図１２】
2004068337.tif 000014
【図１３】
2004068337.tif 000015
【国際調査報告】
2004068337.tif 000016
2004068337.tif 000017