(57)【特許請求の範囲】
【請求項１】
分岐予測機構（１４）であって、
フェッチアドレスを受けるように結合された分岐予測記憶部（９０）を含み、前記フェッチアドレスは命令キャッシュ（１６）からフェッチされる連続する命令バイトの群（５０）に対応し、前記連続する命令バイトの群（５０）は複数のバイト範囲を含むことを特徴とし、前記分岐予測記憶部（９０）は前記連続する命令バイトの群（５０）に対応する複数の分岐セレクタ（７０，１９０）を記憶するように構成され、前記複数の分岐セレクタ（７０，１９０）の各々は前記複数のバイト範囲の別のものと対応し、前記複数の分岐セレクタ（７０，１９０）の各々は分岐予測（１３２，１３４，１１０，１１２）を特定し、特定のバイト範囲に含まれる最大数のバイトは、変位を含む最短の分岐命令内の多数のバイトであり、少なくとも１つの他の命令は、前記変位を含む前記最短の分岐命令よりも少ないバイトを含み、
前記複数の分岐セレクタ（７０，１９０）のうち１つを選択するように構成された選択装置（９４，１０４）を含み、前記複数の分岐セレクタ（７０，１９０）の前記１つは前記フェッチアドレスによって特定されたバイトを含む前記複数のバイト範囲の１つに対応する、分岐予測機構（１４）。
【請求項２】
前記複数のバイト範囲の特定のものは、前記連続する命令バイトの群（５０）の最初のものを含む、請求項１に記載の分岐予測機構（１４）。
【請求項３】
前記複数のバイト範囲の前記特定のものは、前記命令バイトの群（５０）の前記最初のもののみを含む、請求項２に記載の分岐予測機構（１４）。
【請求項４】
前記複数の分岐セレクタ（７０，１９０）の前記１つによって特定される前記分岐予測（１３２，１３４）は、前記連続する命令バイトの群（５０）内の分岐命令に対応する、請求項１に記載の分岐予測機構（１４）。
【請求項５】
前記分岐命令に先行し、かつ前記フェッチアドレスによって特定された前記バイトに後続する前記連続する命令バイトの群（５０）内の命令は、他のテイクン予測された分岐命令を除く、請求項４に記載の分岐予測機構（１４）。
【請求項６】
請求項１から５のいずれか１つに記載の分岐予測機構（１４）と、
前記フェッチアドレスを受け、かつ前記フェッチアドレスに応答して前記連続する命令バイトの群（５０）を与えるように結合された前記命令キャッシュ（１６）とを含む、
マイクロプロセッサ（１０）。
【請求項７】
分岐予測を行なうための方法であって、
フェッチアドレスを用いて命令キャッシュ（１６）から連続する命令バイトの群（５０）をフェッチするステップを含み、
前記連続する命令バイトの群（５０）に対応する複数の分岐セレクタ（７０，１９０）を記憶するステップを含み、前記複数の分岐セレクタ（７０，１９０）の各々は前記連続する命令バイトの群（５０）内の別のバイト範囲に対応し、かつ前記別のバイト範囲内のバイトがフェッチされると選択すべき分岐予測（１３２，１３４，１１０，１１２）を特定し、前記別のバイト範囲の最大のものが、変位を含む最短の分岐命令内の多数のバイトを含み、少なくとも１つの他の命令が前記変位を含む前記最短の分岐命令より少ないバイトを含み、
前記フェッチアドレスに応答して前記複数の分岐セレクタ（７０，１９０）の１つを選択するステップを含み、前記フェッチアドレスは、前記複数の分岐セレクタ（７０，１９０）の前記１つに対応するあるバイト範囲内のバイトを特定し、
前記複数の分岐セレクタ（７０，１９０）の前記１つによって特定された前記分岐予測（１３２，１３４，１１０，１１２）を選択するステップを含むことを特徴とする、方法。
【請求項８】
前記別々のバイト範囲の各々が、前記連続する命令バイトの群（５０）の最初のバイトを含む最初のバイト範囲および第２のバイト範囲以外の前記別のバイト範囲の前記最大のものの中に前記多数のバイトを含む、請求項７に記載の方法。
【請求項９】
前記最初のバイト範囲が前記最初のバイトのみを含む、請求項８に記載の方法。
【請求項１０】
前記第２の範囲が、前記連続する命令バイトの群（５０）内の前記最初のバイトに続くバイトを含む、請求項８に記載の方法。
【請求項１１】
前記第２の範囲が、前記連続する命令バイトの群（５０）内の最終バイトを含む、請求項８に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はマイクロプロセッサの分野に関し、より特定的には、マイクロプロセッサ内の分岐予測機構に関する。
【０００２】
【関連技術の説明】
スーパースカラマイクロプロセッサは、１クロックサイクルあたり複数の命令を実行すること、および設計と整合した可能な限り最短のクロックサイクルを選択することにより、高性能を達成する。ここでは、用語「クロックサイクル」は、マイクロプロセッサ内の命令処理パイプラインの種々の段階に与えられた時間のインターバルを表わすものとして用いられる。記憶装置（たとえばレジスタおよびアレイ）はクロックサイクルに従ってそれらの値を取込む。たとえば、記憶装置はクロックサイクルを規定するクロック信号の立上がりエッジまたは立下がりエッジに従って値を取込むであろう。この記憶装置はその後、それぞれクロック信号の後続の立上がりエッジまたは立下がりエッジまで、その値を記憶する。用語「命令処理パイプライン」はここでは、パイプライン形式で命令を処理するために採用された論理回路を示すのに用いられる。このパイプラインは、命令処理の部分が行なわれるいかなる数の段階に分けられてもよいが、命令処理は通常、命令のフェッチ、命令のデコード、命令の実行、およびその実行の結果の、命令によって特定された宛先をへの格納を含む。
【０００３】
スーパースカラマイクロプロセッサ（およびスーパーパイプラインマイクロプロセッサ）の重要な特徴は、その分岐予測機構である。分岐予測機構は分岐命令に対して予測された方向（テイクンまたはノットテイクン）を示し、分岐予測によって示された予測命令ストリーム内で後続の命令のフェッチを続けることを可能にする。分岐命令は少なくとも２つのアドレス（分岐命令に直接続く命令で始まる命令ストリームを特定する順次アドレス、およびメモリ内の任意の場所で始まる命令ストリームを特定するターゲットアドレス）のうちの１つから、後続の命令をフェッチさせる命令である。無条件分岐命令は常にターゲットアドレスへ分岐するのに対し、条件付き分岐命令は先行の命令の出力に基づいて順次アドレスかターゲットアドレスかのいずれかを選択し得る。予測命令ストリームからの命令は、分岐命令の実行に先行して投機的に実行されてもよく、またいかなる場合も、分岐命令の実行に先行して命令処理パイプラインに置かれる。予測命令ストリームが正しい場合、クロックサイクルごとに実行される命令の数が増加するという効果を奏する。しかしながら、予測命令ストリームが正しくない場合（すなわち１つ以上の分岐命令が誤って予測された場合）、誤って予測された命令ストリームからの命令は命令処理パイプラインから廃棄され、クロックサイクルごとに実行される命令の数は減少する。
【０００４】
効果を発揮するためには、分岐予測機構は予測命令ストリームができる限り高い頻度で正しくなるように非常に正確でなければならない。典型的には、分岐予測機構の正確さを増すには、分岐予測機構の複雑さを増すとよい。たとえば、分岐予測が命令キャッシュ内の命令バイトの特定のキャッシュラインに対応して記憶されるという、キャッシュラインベースの分岐予測スキームを採用してもよい。キャッシュラインとは、キャッシュ内の記憶スペースを割当および割当解除する際の単位として扱われる、多数の連続するバイトである。命令キャッシュラインがフェッチされると、対応する分岐予測もまたフェッチされる。さらに、特定のキャッシュラインが廃棄されると、対応する分岐予測も同様に廃棄される。キャッシュラインはメモリ内で整列される。キャッシュラインベースの分岐予測スキームは、各キャッシュラインに対してより多数の分岐予測を記憶することによりさらに正確にされ得る。所与のキャッシュラインは複数の分岐命令を含み、それらの各々は異なる分岐予測によって表わされ得る。したがって、キャッシュラインにより多くの分岐予測を割当てると、より多くの分岐命令が分岐予測機構によって表わされかつ予測されることが可能になる。分岐予測機構内に代理を持たない分岐命令は予測されず、後に分岐がテイクンであるとわかると「予測誤り」が検出され得る。しかしながら、追加された分岐予測の中から選択する必要があることによって分岐予測機構の複雑さが増大する。ここでは「分岐予測」は、分岐命令がテイクンまたはノットテイクンであるか否かの予測として、分岐予測機構によって解釈され得る値として用いられる。さらに、分岐予測はターゲットアドレスを含み得る。キャッシュラインベースの分岐予測機構に関しては、フェッチされているキャッシュラインに対するシーケンシャルなラインの予測とは、キャッシュラインからフェッチされている命令内に分岐命令が全くない場合の分岐予測である。
【０００５】
分岐予測機構の複雑さを増すことに関する問題は、複雑さが増すと、通常、分岐予測を形成するのにかかる所要時間も増す必要があるということである。たとえば、複数の分岐予測間での選択はかなりの時間を要し得る。フェッチアドレスのオフセットは、キャッシュライン内のフェッチされている先頭バイトを特定する。すなわち、オフセットに先行する分岐命令の分岐予測は選択すべきではない。いずれの分岐予測を用いるかを決定するために、キャッシュライン内のフェッチアドレスのオフセットをキャッシュラインに対して記憶された分岐予測によって表わされる分岐命令のオフセットと比較する必要があり得る。フェッチアドレスのオフセットの後に続き、かつフェッチアドレスのオフセットに後続する他の分岐命令と比べてフェッチアドレスのオフセットにより近い、分岐命令に対応する分岐予測が選択されるべきである。分岐予測の数が増大すると、選択論理の複雑さ（および所要時間）も増大する。フェッチアドレスに対する分岐予測を形成するための所要時間がマイクロプロセッサのクロックサイクル時間を超えると、マイクロプロセッサの性能は低減し得る。分岐予測を単一クロックサイクルで形成することはできないので、前のフェッチアドレスに対応する分岐予測がないことにより、命令をフェッチすることができないクロックサイクル中に「バブル」が命令処理パイプラインに入り込む。このバブルは、後続のクロックサイクル中にも命令処理パイプラインのさまざまな段階を占め、バブルは命令を含まないのでバブルを含む段階ではいかなる処理も行なわれない。したがって、マイクロプロセッサの性能は低減し得る。
複数の命令に同時にアクセス可能なスーパスカラプロセッサシステムを開示するＥＰ６０５，８７６号が参照される。複数命令アクセス内の可能な命令フェッチ位置の各々に対する予測フィールドを含む分岐履歴表が確立される。
また、Young H.C.ら，ＥＰ３９４７１１号（東京芝浦電気株式会社）、ＷＯ９３／１７３８５号（インテル・コーポレイション）およびＵＳ４，８６０，１９７号（Langendorf Brian Kら）も参照される。
【０００６】
【発明の概要】
上述した問題の大部分は、本発明に従った分岐予測ユニットによって解決される。分岐予測ユニットは、命令キャッシュに記憶された連続する命令バイトの群の各々に対応する１組の分岐セレクタを記憶する。各分岐セレクタは、分岐セレクタに対応するフェッチアドレスが提示されると、選択すべき分岐予測を特定する。フェッチアドレスのオフセットと分岐命令のオフセットとの、時間のかかる比較は省いてもよいという効果がある。よって、より複雑な分岐予測機構が、以前に達成可能であったかもしれないものよりさらに高い周波数でサポートされ得る。
【０００７】
連続する命令バイトの群について記憶された分岐セレクタの数を最小にするために、この群は複数のバイト範囲に分けられる。最大のバイト範囲は、命令セット内の（復帰命令を除く）最短の分岐命令を含む、複数のバイトを含み得る。たとえば、最短の分岐命令は一実施例では２バイトであり得る。したがって、この例では最大のバイト範囲は２バイトである。群としての分岐セレクタは、テイクン予測された分岐命令のエンドバイトにおいてのみ、値を変える（すなわち異なる分岐命令を示す）ので、その群内のバイト数より少ない分岐セレクタが記憶され得る。分岐予測記憶部の大きさは、分岐セレクタが各バイトについて記憶されるときよりも、より小さくなり得るという効果がある。より小さい分岐予測記憶部はより速いアクセス時間を示すだろうし、分岐予測機構を用いて達成可能なクロックサイクル時間を向上させることができる。さらに、分岐予測記憶部が占める基板領域エリアも減少するので、費用も減じられ得る。
【０００８】
概して、本発明は、分岐予測記憶部および選択装置を含む分岐予測機構を企図する。命令キャッシュからフェッチされる連続する命令バイトの群に対応するフェッチアドレスを受けるように結合されて、分岐予測記憶部は、複数の分岐セレクタを記憶するように構成される。連続する命令バイトの群は複数のバイト範囲を含み、複数の分岐セレクタの各々が複数のバイト範囲の別の１つに対応する。さらに、複数の分岐セレクタの各々は分岐予測を特定する。また、特定のバイト範囲に含まれる最大バイト数は、変位を含む最短の分岐命令内のバイト数であり、少なくとも１つの他の命令はこの変位を含む上記の最短の分岐命令より少ないバイトを含む。選択装置は複数の分岐セレクタの選択された１つを選択するように構成される。複数の分岐セレクタの選択された１つは複数のバイト範囲の選択された１つに対応する。複数のバイト範囲の選択された１つはフェッチアドレスによって特定されたバイトを含む。
【０００９】
本発明はさらに、分岐予測を行なうための方法を企図する。連続する命令バイトの群に対応する複数の分岐セレクタが記憶される。複数の分岐セレクタの各々は連続する命令バイトの群内の別のバイト範囲に対応し、そのバイト範囲内のバイトがフェッチされると選択される分岐予測を特定する。また、上記の別のバイト範囲の最大のものは、変位を含む最短の分岐命令内のバイト数を含み、少なくとも１つの他の命令はこの変位を含む上記の最短の分岐命令より少ないバイトを含む。連続する命令バイトの群の１つ以上が、フェッチアドレスを用いて命令キャッシュからフェッチされる。フェッチアドレスに応答して、複数の分岐セレクタの１つが選択される。続いて、複数の分岐セレクタの１つによって特定された分岐予測が選択される。
【００１０】
さらに、本発明は命令キャッシュおよび分岐予測ユニットを含むマイクロプロセッサを企図する。命令キャッシュは、フェッチアドレスを受けるために、かつそのフェッチアドレスに応答して連続する命令バイトの群を与えるために、結合される。命令キャッシュと同時にフェッチアドレスを受けるように結合されて、分岐予測ユニットは、複数の分岐セレクタを記憶するように構成される。複数の分岐セレクタは、連続する命令バイトの群に対応する。さらに、複数の分岐セレクタの各々は、連続する命令バイトの群内の複数のバイト範囲のうち対応するそれぞれに対応する。分岐予測ユニットは、フェッチアドレスに応答して複数の分岐セレクタの１つを選択するように構成され、複数の分岐セレクタの１つによって特定される分岐予測を用いて後続のフェッチアドレスを予測するようにさらに構成される。
【００１１】
本発明のその他の目的および利点は次の詳細な説明を読むことにより、また添付の図面を参照することにより、明らかになるであろう。
【００１２】
本発明は種々の変形および代替の形態が可能であるが、それらの特定の実施例を例として図示し、ここに詳細に述べる。しかしながら、当然、図面およびその詳細な説明は本発明を開示した特定の形態に限定することを意図するのではなく、逆に、前掲の請求項に規定された本発明の精神および範囲内にあるすべての変形例、等価物および代替例を包含することを意図するものである。
【００１３】
【詳細な説明】
ここで図１を参照して、マイクロプロセッサ１０の一実施例のブロック図が示される。マイクロプロセッサ１０はプリフェッチ／プリデコードユニット１２、分岐予測ユニット１４、命令キャッシュ１６、命令整列ユニット１８、複数のデコードユニット２０Ａ−２０Ｃ、複数の予約ステーション２２Ａ−２２Ｃ、複数の機能ユニット２４Ａ−２４Ｃ、ロード／ストアユニット２６、データキャッシュ２８、レジスタファイル３０、リオーダバッファ３２、およびＭＲＯＭユニット３４を含む。ここで特定の参照番号に続いてアルファベットを付して示した要素は、その参照番号単独でまとめて示す。たとえば、デコードユニット２０Ａから２０Ｃは、まとめてデコードユニット２０と示す。
【００１４】
プリフェッチ／プリデコードユニット１２はメインメモリサブシステム（図示せず）からの命令を受けるように結合され、さらに命令キャッシュ１６および分岐予測ユニット１４に結合される。同様に、分岐予測ユニット１４は命令キャッシュ１６に結合される。またさらに、分岐予測ユニット１４はデコードユニット２０および機能ユニット２４に結合される。命令キャッシュ１６はさらに、ＭＲＯＭユニット３４および命令整列ユニット１８に結合される。命令整列ユニット１８は次いでデコードユニット２０に結合される。デコードユニット２０Ａ−２０Ｃの各々はロード／ストアユニット２６、およびそれぞれの予約ステーション２２Ａ−２２Ｃに結合される。予約ステーション２２Ａ−２２Ｃはそれぞれの機能ユニット２４Ａ−２４Ｃにさらに結合される。また、デコードユニット２０および予約ステーション２２はレジスタファイル３０およびリオーダバッファ３２に結合される。機能ユニット２４は、ロード／ストアユニット２６、レジスタファイル３０、およびリオーダバッファ３２にも同様に結合される。データキャッシュ２８は、ロード／ストアユニット２６およびメインメモリサブシステムに結合される。最後に、ＭＲＯＭユニット３４はデコードユニット２０に結合される。
【００１５】
一般に、分岐予測ユニット１４は分岐命令を予測するためにキャッシュラインベースの分岐予測機構を採用する。各キャッシュラインに対して複数の分岐予測が記憶され得る。さらに、キャッシュラインは複数のバイト範囲に分けられ、キャッシュライン内の各バイト範囲について分岐セレクタが記憶される。特定のバイト範囲の分岐セレクタは、キャッシュラインに関して記憶され得る分岐予測のうち、特定のバイト範囲内のあるバイトをフェッチする命令フェッチアドレスに適切な分岐予測がどれであるかを示す。ここでは、バイト範囲は、キャッシュライン（または以下に述べるように命令キャッシュ１６の出力で全キャッシュラインに満たないものが与えられた場合はその一部）内の１つ以上の連続するバイトとして用いられる。適切な分岐予測とは、特定のバイトに後続するキャッシュライン内にある第１のテイクン予測された分岐命令に対する分岐予測である。ここで用いる用語「後続の」および「先行の」はキャッシュライン内のバイトの順序を示す。第２のバイトが記憶されるメモリアドレスより数の小さいメモリアドレスに記憶されたバイトは、第２のバイトに先行するという。逆に、第２のバイトのメモリアドレスより数が大きいメモリアドレスに記憶されたバイトは、第２のバイトに後続する、という。同様に、プログラムを形成する命令のシーケンスの中を一度に１ずつ進むと、第１の命令が第２の命令の前にある場合、プログラム順で第１の命令が第２の命令に先行する、という。
【００１６】
一実施例では、マイクロプロセッサ１０は、命令セットが可変バイト長命令セットであるマイクロプロセッサ・アーキテクチャ（たとえばｘ８６マイクロプロセッサ・アーキテクチャ）を採用する。可変バイト長命令セットが採用される場合、キャッシュライン内のどのバイトでも、所与のフェッチアドレスによってフェッチされる先頭バイトとして特定されることがあり得る。たとえば、分岐命令はキャッシュライン内のバイト位置２にターゲットアドレスを有し得る。このような場合、バイト位置０およびバイト位置１のバイトは現在のキャッシュアクセス中にはフェッチされていない。さらに、テイクン予測された分岐（第１のバイトに後続するもの）に後続するバイトは、現在のキャッシュアクセス中にはフェッチされない。テイクン予測された分岐に対する分岐予測は、キャッシュラインからフェッチされる第１のバイトを含むバイト範囲に対応する分岐セレクタを選択することにより見つけることができる。分岐セレクタは、後に命令キャッシュ１６の命令フェッチ論理に与えられる適切な分岐予測を選択するために用いられる。続いて起こるクロックサイクル中、分岐予測はフェッチアドレスとして用いられる。フェッチされる第１のバイトのバイト位置と、テイクン予測された分岐命令のバイト位置とを比較する処理を、フェッチアドレスに応答する分岐予測の生成から省くことができるという効果がある。分岐予測を形成するための所要時間もこれに従って減少し、分岐予測機構は、単一サイクル分岐予測を与えながらも、より高いクロック周波数（すなわちより短いクロックサイクル）で動作することが可能になる。
【００１７】
これまでの論述で「キャッシュライン」という用語が用いられてきたが、命令キャッシュ１６のいくつかの実施例は、所与のクロックサイクル中にその出力にキャッシュライン全体を与えない場合もあることを述べておく。たとえば、ある実施例では、命令キャッシュ１６は３２バイトのキャッシュラインで構成される。しかしながら、所与のクロックサイクル（キャッシュラインの上半分または下半分のいずれか）において１６バイトしかフェッチされない。分岐予測記憶場所および分岐セレクタは、フェッチされているキャッシュラインの部分に割当てられる。ここでは、「連続する命令バイトの群」という用語は、フェッチアドレスに応答して特定のクロックサイクルにおける命令キャッシュによって与えられる、命令バイトを示すのに用いられる。連続する命令バイトの群は、さまざまな実施例によれば、キャッシュラインの一部、またはキャッシュライン全体であり得る。連続する命令バイトの群がキャッシュラインの一部である場合でも、それは依然としてキャッシュラインの整列されている部分である。たとえば、連続する命令バイトの群がキャッシュラインの半分である場合、それはそのキャッシュラインの上半分またはそのキャッシュラインの下半分のいずれかである。多数の分岐予測記憶場所が連続する命令バイトの群の各々に割当てられ、分岐セレクタはその群に関連する分岐予測記憶場所の１つを示す。さらに、分岐セレクタは復帰スタック構造からの復帰スタックアドレス、または、連続する命令バイトの群における対応のバイトと、最後のバイトとの間に分岐命令が全くない場合はシーケンシャルアドレスを示し得る。
【００１８】
命令キャッシュ１６は命令を記憶するために設けられる高速キャッシュメモリである。命令は命令キャッシュ１６からフェッチされ、デコードユニット２０へディスパッチされる。ある実施例では、命令キャッシュ１６は、３２バイトのライン（１バイトは８バイナリビットを含む）を有する４ウェイ・セットアソシアティブ構造で６４キロバイトの命令まで記憶するように構成される。代替的には、２ウェイ・セットアソシアティビティおよび他の何らかの望ましいアソシアティビティを採用してもよい。命令キャッシュ１６はさらに、命令キャッシュへのアクセス時間を速めるためにウェイ予測スキームを採用してもよい。命令の各ラインを特定するタグにアクセスし、それらのタグをフェッチアドレスと比較してウェイを選択する代わりに、命令キャッシュ１６はアクセスされるウェイを予測する。この方法で、ウェイは命令記憶部へのアクセスの前に選択される。命令キャッシュ１６のアクセス時間はダイレクトマップされたキャッシュと同様であり得る。タグ比較が行なわれ、ウェイ予測が正しくない場合、正しい命令がフェッチされ、正しくない命令は廃棄される。なお、命令キャッシュ１６はフルアソシアティブ、セットアソシアティブ、またはダイレクトマップされた構成として実現され得る。
【００１９】
命令はメインメモリからフェッチされ、プリフェッチ／プリデコードユニット１２によって命令キャッシュ１６内へ記憶される。命令はその要求前に、命令キャッシュ１６からプリフェッチスキームに従ってプリフェッチされ得る。さまざまなプリフェッチスキームがプリフェッチ／プリデコードユニット１２によって採用され得る。プリフェッチ／プリデコードユニット１２がメインメモリから命令キャッシュ１６へ命令を転送すると、プリフェッチ／プリデコードユニット１２はそれらの命令の各々のバイトについて３つのプリデコードビット（スタートビット、エンドビット、および機能ビット）を生成する。プリデコードビットは各命令のバウンダリを示すタグを形成する。プリデコードタグはまた、以下に詳細に述べるように、所与の命令がデコードユニット２０によって直接デコードされ得るか否か、またはその命令がＭＲＯＭユニット３４によって制御されるマイクロコード手続きを呼出すことによって実行されるか否かなどの追加情報も伝達し得る。またさらに、プリフェッチ／プリデコードユニット１２は、分岐命令を検出し、かつその分岐命令に対応する分岐予測情報を分岐予測ユニット１４内へ記憶するように構成され得る。
【００２０】
次に、可変バイト長命令セットを採用するマイクロプロセッサ１０の実施例に対するプリデコードタグのエンコーディングの一例について述べる。可変バイト長命令セットとは、種々の命令が種々のバイト数を占め得る命令セットである。マイクロプロセッサ１０の一実施例によって採用される可変バイト長命令セットの例は、ｘ８６命令セットである。
【００２１】
このエンコーディングの例では、所与のバイトが命令の最初のバイトである場合、そのバイトに対してスタートビットがセットされる。このバイトが命令の最後のバイトである場合、そのバイトに対してエンドビットがセットされる。デコードユニット２０によって直接デコードできる命令は「ファストパス」命令と呼ばれる。残りのｘ８６命令は一実施例ではＭＲＯＭ命令と呼ばれる。ファストパス命令に対して、機能ビットは、命令に含まれるプレフィックスバイトの各々についてはセットされ、他のバイトについてはクリアされる。これに代えて、ＭＲＯＭ命令に対しては、機能ビットは各プレフィックスバイトについてはクリアされ、他のバイトについてはセットされる。命令のタイプは、エンドバイトに対応する機能ビットを調べることにより決定され得る。機能ビットがクリアされている場合、命令はファストパス命令である。逆に、機能ビットがセットされている場合、命令はＭＲＯＭ命令である。命令のオペコードは、したがって、デコードユニット２０によって直接デコードできる命令内では、その命令内の第１のクリア機能ビットと関連するバイトとして見つけることができる。たとえば、２つのプレフィックスバイト、Ｍｏｄ  Ｒ／Ｍバイト、および即値バイトを含むファストパス命令はスタートビット、エンドビット、および機能ビットを次のとおり有するであろう。
【００２２】
スタートビット          １００００
エンドビット            ００００１
機能ビット              １００００
ある特定の実施例に従うと、スケール−インデックス−基底（ＳＩＢ）バイトを含む命令を早期に特定することは、ＭＲＯＭユニット３４については有利である。このような実施例については、命令がオペコードバイトの後に少なくとも２バイトを含む場合、Ｍｏｄ  Ｒ／Ｍバイトに対する機能ビットはＳＩＢバイトの存在を示す。Ｍｏｄ  Ｒ／Ｍバイトに対する機能ビットがセットされている場合、ＳＩＢバイトが存在する。これに代えて、Ｍｏｄ  Ｒ／Ｍバイトに対する機能ビットがクリアされている場合、ＳＩＢバイトは存在しない。
【００２３】
ＭＲＯＭ命令は、デコードユニット２０によってデコードするには複雑すぎると判断される命令である。ＭＲＯＭ命令は、ＭＲＯＭユニット３４を呼出すことにより実行される。より具体的には、ＭＲＯＭ命令に出会うと、ＭＲＯＭユニット３４はその命令を解析して、定められたファストパス命令のサブセットとして発行し、所望の動作を実行する。ＭＲＯＭユニット３４はファストパス命令のサブセットをデコードユニット２０へディスパッチする。ファストパス命令としてカテゴリ化されるｘ８６命令の例のリストは、後に示す。
【００２４】
マイクロプロセッサ１０は条件付き分岐命令に後続する命令を投機的にフェッチするために分岐予測を採用する。分岐予測動作を行なうために分岐予測ユニット１４が含まれる。一実施例では、命令キャッシュ１６内の各キャッシュラインの１６バイト部分の各々に対して２つまでの分岐ターゲットアドレスが記憶される。プリフェッチ／プリデコードユニット１２は、特定のラインがプリデコードされると初期分岐ターゲットを決定する。キャッシュラインに対応する分岐ターゲットの後続する更新が、キャッシュライン内の命令の実行によって起こり得る。命令キャッシュ１６はフェッチされる命令アドレスを示すので、分岐予測ユニット１４は分岐予測を形成するためにいずれの分岐ターゲットアドレスを選択するかを判断し得る。デコードユニット２０および機能ユニット２４は分岐予測ユニット１４に更新情報を与える。分岐予測ユニット１４はキャッシュラインの１６バイト部分ごとに２つのターゲットを記憶するので、ライン内の分岐命令のいくつかは分岐予測ユニット１４内に記憶されない場合もある。デコードユニット２０は分岐予測ユニット１４によって予測されなかった分岐命令を検出する。機能ユニット２４は分岐命令を実行し、予測された分岐方向が誤りであるかを判断する。この分岐方向は、後続の命令が分岐命令のターゲットアドレスからフェッチされる「テイクン」であり得る。逆に、この分岐方向は、後続の命令が分岐命令に連続するメモリ場所からフェッチされる「ノットテイクン」でもあり得る。予測誤りのあった分岐命令が検出されると、予測誤りのあった分岐に続く命令がマイクロプロセッサ１０のさまざまなユニットから廃棄される。種々の適切な分岐予測アルゴリズムが、分岐予測ユニット１４によって採用され得る。
【００２５】
命令キャッシュ１６からフェッチされた命令は、命令整列ユニット１８に与えられる。命令が命令キャッシュ１６からフェッチされると、対応するプリデコードデータが走査され、フェッチされている命令に関する情報を命令整列ユニット１８（およびＭＲＯＭユニット３４）に与える。命令整列ユニット１８は、走査データを用いて命令をデコードユニット２０の各々と整列する。一実施例では、命令整列ユニット１８はデコードユニット２０の８つの命令バイトの３つのセットからの命令を整列する。命令は８命令バイトの各組から互いに独立して予備発行位置に選択される。この予備発行位置はこの後、デコードユニット２０に対応する１組の整列された発行位置にマージされ、よって整列された発行位置は、プログラム順において予備発行位置内の他の命令に先行する３つの命令を含む。デコードユニット２０Ａは、デコードユニット２０Ｂおよび２０Ｃによって（プログラム順において）同時に受けられた命令に先行する命令を受ける。同様に、デコードユニット２０Ｂはデコードユニット２０Ｃによって同時に受けられた命令にプログラム順において先行する命令を受ける。
【００２６】
デコードユニット２０は、命令整列ユニット１８から受けた命令をデコードするように構成される。レジスタオペランド情報が検出され、レジスタファイル３０およびリオーダバッファ３２に送られる。さらに、命令が１つ以上のメモリ演算を行なうことを要する場合、デコードユニット２０はメモリ演算をロード／ストアユニット２６にディスパッチする。各命令は機能ユニット２４に対する１組の制御値にデコードされ、これらの制御値はオペランドアドレス情報および命令に含まれ得る変位または即値データとともに、予約ステーション２２にディスパッチされる。
【００２７】
マイクロプロセッサ１０はアウトオブオーダ実行をサポートし、したがってリオーダバッファ３２を採用してレジスタ読出および書込動作についての元のプログラムシーケンスの記録を取り、レジスタ・リネーミングを実現し、投機的な命令の実行および分岐予測誤りのリカバリを可能にし、かつ精密に例外を発生することを容易にする。レジスタの更新を伴う命令のデコード時にリオーダバッファ３２内の一時記憶場所が、投機的レジスタ状態を記憶するために予約される。分岐予測が正しくない場合には、誤予測された経路に沿って投機的に実行された命令の結果を、レジスタファイル３０へ書込む前にバッファ内で無効にすることができる。同様に、特定の命令が例外を生じる場合、その特定の命令に後続する命令は廃棄できる。この態様では、例外は「精密」である（すなわち例外を引起こす特定の命令に後続する命令が例外に先行して完了されることはない）。なお、特定の命令がプログラム順で特定の命令に先行する命令の前に実行される場合、その特定の命令は投機的に実行される、といわれる。先行する命令は分岐命令または例外を引起こす命令であるかもしれず、その場合、投機的結果はリオーダバッファ３２によって廃棄され得る。
【００２８】
命令制御値およびデコードユニット２０の出力に与えられた即値または変位データは、それぞれの予約ステーション２２へ直接送られる。一実施例では、各予約ステーション２２は命令情報（すなわち命令制御値、オペランド値、オペランドタグおよび／または即値データ）を、対応の機能ユニットへの発行を待っているペンディング中の命令３つまでについて保持することが可能である。なお、図１の実施例では、各予約ステーション２２は専用機能ユニット２４に関連づけられる。したがって、３つの専用「発行位置」が、予約ステーション２２および機能ユニット２４によって形成される。すなわち、発行位置０は予約ステーション２２Ａおよび機能ユニット２４Ａによって形成される。予約ステーション２２Ａに整列されかつディスパッチされた命令は、機能ユニット２４Ａによって実行される。同様に、発行位置１は予約ステーション２２Ｂおよび機能ユニット２４Ｂによって形成され、発行位置２は予約ステーション２２Ｃおよび機能ユニット２４Ｃによって形成される。
【００２９】
特定の命令のデコード時に、必要なオペランドがレジスタ場所である場合、レジスタアドレス情報はリオーダバッファ３２およびレジスタファイル３０に同時に送られる。当業者は、ｘ８６レジスタファイルが８つの３２ビットリアルレジスタ（典型的にはＥＡＸ、ＥＢＸ，ＥＣＸ、ＥＤＸ、ＥＢＰ、ＥＳＩ、ＥＤＩおよびＥＳＰと呼ばれる）を含むということがわかるであろう。ｘ８６マイクロプロセッサアーキテクチャを採用するマイクロプロセッサ１０の実施例では、レジスタファイル３０は３２ビットリアルレジスタの各々についての記憶場所を含む。ＭＲＯＭユニット３４が用いるために、さらなる記憶場所がレジスタファイル３０内に含まれ得る。リオーダバッファ３２は、これらのレジスタの内容を変更するような結果に対する一時記憶場所を含み、それによりアウトオブオーダ実行が可能になる。リオーダバッファ３２の一時記憶場所が、リアルレジスタの１つの内容を修正するとデコード時に判定された各命令について予約される。したがって、特定のプログラムの実行中のさまざまな点で、リオーダバッファ３２は所与のレジスタの投機的に実行された内容を含む１つ以上の場所を有し得る。所与の命令のデコードに続いて、リオーダバッファ３２が所与の命令内のオペランドとして用いられるレジスタに割当てられた先行の場所を有すると判断された場合、リオーダバッファ３２は、１）最も最近割当られた場所の値、または２）最終的に先行の命令を実行する機能ユニットによってその値がまだ生成されていない場合は最も最近割当てられた場所に対するタグ、のいずれかを、対応の予約ステーションに送る。リオーダバッファ３２が所与のレジスタのために予約された場所を有する場合、オペランド値（またはリオーダバッファタグ）はレジスタファイル３０からではなくリオーダバッファ３２から与えられる。リオーダバッファ３２内に必要なレジスタのために予約された場所がない場合は、その値はレジスタファイル３０から直接取られる。オペランドがメモリ場所に対応する場合、オペランド値はロード／ストアユニット２６を通って予約ステーションへ与えられる。
【００３０】
ある特定の実施例では、リオーダバッファ３２は同時にデコードされた命令を１つの単位として記憶し操作するように構成される。この構成はここでは「ライン指向」と呼ばれる。複数の命令をともに走査することにより、リオーダバッファ３２内に採用されるハードウェアは単純化され得る。たとえば、この実施例に含まれるライン指向リオーダバッファは、デコードユニット２０によって１つ以上の命令がディスパッチされると常に、３つの命令（各デコードユニット２０から１つずつ）に関する命令情報に対して十分な記憶部を割当てる。対照的に、従来のリオーダバッファにおいては、実際にディスパッチされる命令の数に依存して可変量の記憶部が割当てられる。可変量の記憶部を割当てるには、比較的大きな数の論理ゲートが要求され得る。同時にデコードされる命令の各々が実行されると、この命令結果はレジスタファイル３０に同時に記憶される。この記憶部はその後、同時にデコードされた命令の別の組に割当てるために解放される。さらに、１命令あたり使用された制御論理回路の量は、制御論理が複数の同時にデコードされた命令にわたって共用されるので、減少する。特定の命令を特定するリオーダバッファタグは２つのフィールド（ラインタグおよびオフセットタグ）に分けられる。ラインタグは特定の命令を含む同時にデコードされた命令の組を特定し、オフセットタグはその組内のどの命令が特定の命令に対応するかを特定する。なお、命令結果をレジスタファイル３０へ記憶し、対応する記憶部を解放することは、命令を「リタイアする」と呼ばれる。さらに、マイクロプロセッサ１０のさまざまな実施例においていかなるリオーダバッファ構成を採用してもよい。
【００３１】
前に述べたように、予約ステーション２２は、命令が対応の機能ユニット２４によって実行されるまで命令を記憶する。命令は、（ｉ）命令のオペランドが与えられる場合、および（ii）同じ予約ステーション２２Ａ〜２２Ｃ内にありかつプログラム順においてその命令に先行する命令に、オペランドがまだ与えられていない場合、実行のために選択される。ある命令が機能ユニット２４の１つによって実行されると、その命令の結果は、結果が更新リオーダバッファ３２に伝達されるのと同時に、その結果を待っている予約ステーション２２の全てへも直接伝達される（この技術は通常「結果フォワーディング」と呼ばれる）。命令は実行のために選択され、関連の結果がフォワーディングされるクロックサイクル中に機能ユニット２４Ａ−２４Ｃへと伝達され得る。予約ステーション２２はこのフォワーディングされた結果をこの場合は機能ユニット２４へ送る。
【００３２】
一実施例では、機能ユニット２４の各々は整数の加算および減算などの算術演算、シフト、ローテート、論理演算、ならびに分岐演算を行なうように構成される。これらの演算は、デコードユニット２０によって特定の命令についてデコードされた制御値に応答して行なわれる。浮動小数点ユニット（図示せず）もまた浮動小数点演算に対処するために採用され得る。浮動小数点ユニットはコプロセッサとして動作し、ＭＲＯＭユニット３４から命令を受け、その後リオーダバッファ３２と通信して命令を完了し得る。さらに、機能ユニット２４は、ロード／ストアユニット２６によって行なわれたロードおよびストアメモリ演算に対してアドレス生成を行なうように構成され得る。
【００３３】
機能ユニット２４の各々はまた、条件付き分岐命令の実行に関する情報を分岐予測ユニット１４に与える。分岐予測が正しくなかった場合、分岐予測ユニット１４は命令処理パイプラインに入った予測誤りのあった分岐に続く命令をフラッシュし、必要な命令を命令キャッシュ１６またはメインメモリからフェッチさせる。そのような状況では、誤予測された分岐命令の後に起こる元のプログラムシーケンスの命令結果は廃棄され、これは投機的に実行されたものと、ロード／ストアユニット２６およびリオーダバッファ３２で一時的に記憶されたものとを含む。
【００３４】
機能ユニット２４によって出された結果は、レジスタ値が更新されるべき場合リオーダバッファ３２に送られ、メモリ場所の内容が変更される場合ロード／ストアユニット２６に送られる。この結果がレジスタに記憶される場合、リオーダバッファ３２は命令がデコードされるとレジスタの値に対して予約された場所に結果を記憶する。機能ユニット２４およびロード／ストアユニット２６からの結果のフォワーデイングのために、複数の結果バス３８が含まれる。結果バス３８は生成された結果、および実行中の命令を特定するリオーダバッファタグを伝達する。
【００３５】
ロード／ストアユニット２６は機能ユニット２４とデータキャッシュ２８との間にインターフェイスを設ける。一実施例では、ロード／ストアユニット２６は、データのための８つの記憶場所およびペンディングのロードまたはストアについてのアドレス情報を有するロード／ストアバッファを備えて構成される。デコードユニット２０はロード／ストアユニット２６へのアクセスを調停する。バッファがフルになると、デコードユニットは、ロード／ストアユニット２６がペンディングのロードまたはストア要求情報のための空きを有するまで、待機しなければならない。ロード／ストアユニット２６はまた、ペンディングのストアメモリ演算に対するロードメモリ演算についての従属性検査を行ない、データのコヒーレンシが確実に維持されるようにする。メモリ演算とは、マイクロプロセッサ１０とメインメモリサブシステムとの間でのデータの転送である。メモリ演算は、メモリに記憶されたオペランドを用いる命令の結果、またはデータ転送を生じるが他の動作は全く生じないロード／ストア命令の結果であり得る。さらに、ロード／ストアユニット２６は、ｘ８６マイクロプロセッサアーキテクチャによって規定されるアドレス変換機構に関するセグメントレジスタおよび他のレジスタなどの特殊レジスタのための特殊レジスタ記憶部を含み得る。
【００３６】
一実施例では、ロード／ストアユニット２６はロードメモリ演算を投機的に行なうように構成される。ストアメモリ演算はプログラム順に行なわれるが、予測されたウェイへ投機的に記憶されてもよい。予測されたウェイが正しくない場合、ストアメモリ演算に先行するデータは、後に、予測されたウェイにストアし直され、ストアメモリ演算は正しいウェイに対して行なわれる。別の実施例でも同様に、ストアは投機的に実行され得る。投機的に実行されたストアは、更新前のキャッシュラインのコピーとともにストアバッファ内に位置付けられる。投機的に実行されたストアは分岐予測誤りまたは例外が原因で後に廃棄され、キャッシュラインはバッファに記憶された値へとストアし直され得る。ロード／ストアユニット２６はいかなる量の投機的実行でも（投機的実行が全くない場合も含む）行なうように構成され得る。
【００３７】
データキャッシュ２８はロード／ストアユニット２６とメインメモリサブシステムとの間で転送されているデータを一時的に記憶するように設けられた高速キャッシュメモリである。一実施例では、データキャッシュ２８は８ウェイ・セットアソシアティブ構造で１６キロバイトのデータまで記憶できる容量を有する。命令キャッシュ１６と同様、データキャッシュ２８もウェイ予測機構を採用し得る。当然、データキャッシュ２８は、セットアソシアティブ構成を含むさまざまな特殊メモリ構成で実現され得る。
【００３８】
ｘ８６マイクロプロセッサアーキテクチャを採用するマイクロプロセッサ１０のある特定の実施例では、命令キャッシュ１６およびデータキャッシュ２８はリニアにアドレスされる。このリニアアドレスは、命令によって特定されたオフセットおよびｘ８６アドレス変換機構のセグメント部分によって特定された基底アドレスから形成される。リニアアドレスはまた、必要であれば、メインメモリにアクセスするために物理アドレスへ変換され得る。リニアから物理への変換は、ｘ８６アドレス変換機構のページング部分によって特定される。リニアにアドレスされたキャッシュがリニアアドレスタグを記憶することも注目される。リニアアドレスを物理アドレスへマッピングするために、また変換エイリアスを検出するために、１組の物理タグ（図示せず）が採用され得る。さらに、物理タグブロックはリニアから物理へのアドレス変換を行なうこともできる。
【００３９】
次に図２を参照して、デコードユニット２０Ｂおよび２０Ｃの一実施例のブロック図が示される。各デコードユニット２０は命令整列ユニット１８から命令を受ける。さらに、ＭＲＯＭユニット３４は各デコードユニット２０に結合されて特定のＭＲＯＭ命令に対応するファストパス命令をディスパッチする。デコードユニット２０Ｂは初期デコードユニット４０Ｂ、マルチプレクサ４２Ｂ、およびオペコードデコードユニット４４Ｂを含む。同様に、デコードユニット２０Ｃは、初期デコードユニット４０Ｃ、マルチプレクサ４２Ｃ、およびオペコードデコードユニット４４Ｃを含む。
【００４０】
ｘ８６命令セット中の特定の命令は、かなり複雑でありしかも頻繁に用いられるものである。マイクロプロセッサ１０の一実施例では、このような命令は、特定の機能ユニット２４Ａ−２４Ｃ内に含まれるハードウェアが実行するように構成されているものよりも複雑な演算を含む。このような命令は「二重ディスパッチ」命令と呼ばれる特殊タイプのＭＲＯＭ命令として分類される。これらの命令は１対のオペコードデコードユニット４４にディスパッチされる。なお、オペコードデコードユニット４４はそれぞれの予約ステーション２２に結合される。オペコードデコードユニット４４Ａ−４４Ｃの各々は、対応の予約ステーション２２Ａ−２２Ｃおよび機能ユニット２４Ａ−２４Ｃとともに発行位置を形成する。命令はオペコードデコードユニット４４から対応の予約ステーション２２へ伝達され、さらに対応の機能ユニット２４へ伝達される。
【００４１】
ＭＲＯＭユニット３４によって与えられた命令と初期デコードユニット４０Ｂによって与えられた命令との間で選択を行なうためにマルチプレクサ４２Ｂが含まれる。ＭＲＯＭユニット３４が命令をディスパッチしているときには、マルチプレクサ４２ＢはＭＲＯＭユニット３４によって与えられた命令を選択する。その他のときは、マルチプレクサ４２Ｂは初期デコードユニット４０Ｂによって与えられた命令を選択する。同様に、マルチプレクサ４２ＣはＭＲＯＭユニット３４によって与えられた命令と、初期デコードユニット４０Ｂによって与えられた命令と、初期デコードユニット４０Ｃによって与えられた命令との間で選択する。ＭＲＯＭユニット３４からの命令は、ＭＲＯＭユニット３４が命令をディスパッチしているときに選択される。デコードユニット２０Ａ（図示せず）内の初期デコードユニットが二重ディスパッチ命令を検出するときには、初期デコードユニット４０Ｂからの命令がマルチプレクサ４２Ｃによって選択される。それ以外は、初期デコードユニット４０Ｃからの命令が選択される。初期デコードユニット４０Ｂからオペコードデコードユニット４４Ｃへの命令を選択することにより、デコードユニット２０Ａによってデコードされる二重ディスパッチ命令と同時に、デコードユニット２０Ｂによってデコードされるファストパス命令もディスパッチすることが可能になる。
【００４２】
ｘ８６命令セットを採用する一実施例によれば、初期デコードユニット４０は以下の動作を行なう。
【００４３】
（ｉ）  命令のプレフィックスバイトをエンコードされたプレフィックスバイトにマージする。
【００４４】
（ii）  分岐予測中に検出されなかった無条件分岐命令（無条件ジャンプ、ＣＡＬＬ、およびＲＥＴＵＲＮも含み得る）をデコードする。
【００４５】
（iii）  ソースフラグおよび宛先フラグをデコードする。
（iv）  レジスタオペランドであるソースおよび宛先オペランドをデコードし、オペランドサイズ情報を生成する。
【００４６】
（ｖ）  変位および即値データがオペコードデコードユニットへ送られ得るように変位および／または即値サイズを決定する。
【００４７】
オペコードデコードユニット４４は命令のオペコードをデコードするように構成され、機能ユニット２４の制御値を生じる。変位および即値データは制御値とともに予約ステーション２２へ送られる。
【００４８】
初期デコードユニット４０がオペランドを検出するので、マルチプレクサ４２の出力はレジスタファイル３０およびリオーダバッファ３２へ送られる。オペランド値またはタグはこれによって予約ステーション２２へ送られ得る。さらに、メモリオペランドは初期デコードユニット４０によって検出される。したがって、マルチプレクサ４２の出力はロード／ストアユニット２６へ送られる。メモリオペランドを有する命令に対応するメモリ演算は、ロード／ストアユニット２６によって記憶される。
【００４９】
次に図３を参照して、連続する命令バイト５０の群の例および対応するブランチセレクタ５２の組の図が表される。図３では、命令内の各バイトは短い垂直線（たとえば参照番号５４）で示される。さらに、群５０において命令を分離する垂直線はバイトを区分する（たとえば参照番号５６）。図３に示す命令は可変長であり、したがって図３に示す命令を含む命令セットは可変バイト長命令セットである。言い換えれば、可変バイト長命令セット内の第１の命令は、その命令セット内の第２の命令が占める第２のバイト数とは異なる第１のバイト数を占め得る。その他の命令セットは固定長であってもよく、その場合には命令セット内の各命令は他の命令の各々と同じバイト数を占める。
【００５０】
図３に示すように、群５０は非分岐命令ＩＮ０−ＩＮ５を含む。命令ＩＮ０、ＩＮ３、ＩＮ４およびＩＮ５は２バイト命令である。命令ＩＮ１は１バイト命令であり、命令ＩＮ２は３バイト命令である。２つのテイクン予測された分岐命令ＰＢ０およびＰＢ１も同様に図示され、各々２バイトを占めるように表わされる。なお、非分岐および分岐の両方の命令ともさまざまなバイト数を占めることができる。
【００５１】
テイクン予測された分岐ＰＢ０およびＰＢ１の各々のエンドバイトは群５０を３つの領域（第１の領域５８、第２の領域６０、および第３の領域６２）に分別する。群５０を特定するフェッチアドレスが提示されると、このグループ内のフェッチアドレスのオフセットは第１の領域５８内のバイト位置を特定し、その後出会う第１のテイクン予測された分岐命令はＰＢ０であり、したがってＰＢ０の分岐予測が分岐予測機構によって選択される。同様に、フェッチアドレスのオフセットが第２の領域６０内のバイトを特定すると、適切な分岐予測はＰＢ１の分岐予測となる。最後に、フェッチアドレスのオフセットが第３の領域６２内のバイトを特定すると、命令バイトの群内にありかつ特定されたバイトに後続する、テイクン予測された分岐命令は存在しない。したがって、第３の領域６２の分岐予測はシーケンシャルである。このシーケンシャルアドレスはメインメモリ内の群５０の直後に続く命令バイトの群を特定する。
【００５２】
ここでは、アドレスのオフセットはそのアドレスの下位の複数ビットを含むものとして用いられている。この数は、オフセットに関連するバイト群内の各バイトについて異なるビットのエンコーディングを与える。たとえば、群５０は１６バイトである。したがって、その群内のアドレスの下位４ビットがそのアドレスのオフセットを形成する。そのアドレスの残りのビットは、メインメモリ内の連続する命令バイトの他の群から群５０を特定する。さらに、残りのビットの下位複数ビットは、群５０を記憶するのに適した一列の記憶場所を選択するために、命令キャッシュ１６によって用いられるインデックスを形成する。
【００５３】
セット５２は群５０の分岐セレクタのセットの例である。群５０内の各バイトに対して１つの分岐セレクタが含まれる。セット５２内の分岐セレクタは図１２に示すエンコーディングを用いる。この例では、ＰＢ０に対する分岐予測は群５０に関連する２つの分岐予測のうちの２番目のもの（分岐セレクタ値「３」で示す）として記憶される。したがって、第１の領域５８内の各バイトに対する分岐セレクタは「３」にセットされる。同様に、ＰＢ１に対する分岐予測は、これらの分岐予測のうち第１のもの（分岐セレクタ値「２」と示す）として記憶される。したがって、第２の領域６０内の各バイトに対する分岐セレクタは「２」にセットされる。最後に、シーケンシャル分岐予測は、第３の領域６２内のバイトに対する分岐セレクタによって、分岐セレクタエンコーディング「０」で示される。
【００５４】
ｘ８６命令セットの可変バイト長の性質により、分岐命令は連続する命令バイトのある群内で開始し、連続する命令バイトの第２の群内で終了し得ることがわかる。そのような場合、分岐命令の分岐予測は連続する命令バイトの第２の群とともに記憶される。とりわけ、連続する命令バイトの第２の群内に記憶される分岐命令のバイトはフェッチされかつディスパッチされる必要がある。連続する命令バイトの第１の群における分岐予測を形成することにより、命令バイトの第２の群内に存在する分岐命令のバイトはフェッチされないであろう。
【００５５】
セット５２のような分岐セレクタのセットを採用することにより、予測されたフェッチアドレスの迅速な決定が（フェッチアドレスのオフセット部分をデコードすることにより、またセット５２から対応のセレクタを選択することにより）が可能になる。しかしながら、多数の分岐セレクタが（すなわち各バイトに対し１つ）記憶される。分岐セレクタを記憶するために採用された分岐予測記憶部の量も対応して増加するであろう。またさらに、フェッチアドレスのオフセットに応答して分岐セレクタを選択するためには、比較的幅の広い選択装置（たとえばＭＵＸなど）が必要となる。一般に、選択装置の幅が広ければ広いほど、その選択装置（たとえば選択された分岐セレクタ）を通じて選択された値の伝搬における遅延も、より大きくなる。
【００５６】
図３は、１つの領域内の各バイトに対する分岐セレクタは同じであり、領域は分岐命令（より具体的にはテイクン予測された分岐命令）によって区分されるということを示す。分岐命令は一般に、少なくともオペコード（マイクロプロセッサ１０によって採用された命令セット内の分岐命令を特定する）および分岐命令のアドレス（またはその分岐命令の直後の命令のアドレス）に加算されて分岐ターゲットアドレスを形成する変位を含むであろう。したがって、分岐命令は少なくとも２バイトを占める。この事実を利用することにより、連続する命令バイトの群に対して記憶された分岐セレクタの数を減じることができる。
【００５７】
これ以降の記述については、ｘ８６マイクロプロセッサアーキテクチャが例として用いられる。しかしながら、ここで述べる分岐セレクタ技術はいかなるマイクロプロセッサアーキテクチャ内で採用されてもよく、またそのような実施例も企図される。なお、ｘ８６マイクロプロセッサアーキテクチャにおいては、サブルーチン復帰命令（たとえばＲＥＴ命令）が規定されている。サブルーチン復帰命令は、その分岐ターゲットアドレスがＥＳＰレジスタによって示されるスタックのトップから引出されることを特定する。したがって、ＲＥＴ命令は単一バイト（すなわちオペコードバイト）である。この単一バイトＲＥＴ命令を、１つの分岐命令ごとに少なくとも２つのバイトという一般規則を利用して、分岐セレクタで操作することが、より詳細に以下に示される。
【００５８】
次に図４を参照して、群５０、領域５８、６０および６２、ならびに１組の分岐セレクタ７０の一実施例を表わす図が示される。セット７０内の分岐セレクタは群５０内に規定されたバイト範囲に対応する。図４に示す例では、１６の連続する命令バイトの群に対して９の分岐セレクタが用いられる。セット７０はしたがって、図３に示すセット５２が占めるものより少ない記憶部を分岐予測記憶部内で占め、この分岐予測記憶部をより小さくすることを可能にする。さらに、フェッチアドレスに応答して分岐セレクタを選択するためにより幅の狭い選択装置が用いられ得る。この選択された分岐セレクタはより迅速に与えられ、よって予測されたフェッチアドレスが各クロックサイクルに与えられる、高周波数の実現をもたらす。
【００５９】
通常、所与の分岐セレクタに対して規定された最大のバイト範囲は、最短の分岐命令（以下により詳細に述べる復帰命令を除く）と等しくされ得る。バイト範囲の大部分は最大サイズになるように選択される。しかしながら、特定の状況に対応するために、図４に示す実施例は最大サイズより小さい２つのバイト範囲を採用する。特に、群５０の初期バイトは単一バイトを有するバイト範囲（図６に関して以下により詳細に説明する）を形成する。群５０は偶数のバイトであるので、初期バイトに対応するバイト範囲は初期バイトのみを含み、最大バイト範囲はこの例では２バイトであり、別のバイト範囲は同様に単一バイトを有すると規定される。セット７０については、初期バイトに連続する群５０内のバイトが単一バイト範囲として選択される。この選択により、図５に示すようにフェッチアドレスのオフセットを比較的簡単にデコードして分岐セレクタを選択することが可能になる。
【００６０】
これらのバイト範囲は最短の分岐命令より大きくならないように選択されるので、分岐命令はあるバイト範囲で開始し、後続のバイト範囲で終了し得る。しかしながら、連続する命令バイトの特定の群内で分岐命令が連続する場合でも、最大で１つの分岐命令が特定のバイト範囲で終了する。特定のバイト範囲のエンドではなくそのバイト範囲内で終了する分岐命令の場合については、そのバイト範囲に対する分岐セレクタは分岐命令に後続する命令バイトに対応する分岐セレクタとして選択される。たとえば、バイト範囲７２（バイト３〜４を含み、初期バイトがバイト０の番号を付される）に対する分岐セレクタは、予測された分岐ＰＢ１に対応する分岐予測を示す。バイト範囲内のフェッチアドレスが分岐命令（先行するバイト範囲で開始する）をフェッチしていないので、上記の法則が用いられる。したがって、正しい分岐予測は後続の分岐に対する予測である。
【００６１】
一方、分岐命令がバイト範囲内の最後のバイトで終了する場合、バイト範囲についての分岐セレクタは分岐命令（たとえばバイト範囲７４）に対応する分岐セレクタである。したがって、フェッチアドレスが予測された分岐ＰＢ１を特定する（すなわちオフセットがバイト範囲７４内にある）場合、そのフェッチに用いられる分岐予測は分岐ＰＢ１に対応する分岐予測である。
【００６２】
ここで図５を参照して、図４の例に示す分岐セレクタについてのバイト範囲の選択に対応する表７６が示される。表７６の「バイト位置」と記された列は、各バイト範囲に対応する群５０内のバイト位置（各バイト範囲内にある各バイトのアドレスのオフセット部分）をリストする。「分岐選択位置」と記された列は、各バイト範囲に対応する分岐セレクタのセット７０内の分岐セレクタ位置を表わす。「読出アドレス」と記された列は、（後続のクロックサイクルに対して予測されたフェッチアドレスを形成するために）対応のバイト範囲内の分岐セレクタを選択するようにデコードされるフェッチアドレスオフセットを（バイナリで）リストする。読出アドレス中の「ｘ」は、ドントケア位置を示す。最後に、「エンコーディングアドレス」と記された列は、そこで分岐命令が終了でき、かつその分岐命令に対応する分岐予測を示すバイト範囲に対する分岐セレクタをまだ有しているフェッチアドレスのオフセットを（バイナリで）リストする。たとえば、分岐セレクタ位置２は、バイト位置３または４のいずれかで終了する分岐命令に対する分岐予測を示し得る。より具体的には、バイト位置２で終了する分岐命令は、分岐セレクタ位置２の分岐セレクタでは表わされない（これは、分岐命令が、分岐選択位置２に関連するものとは異なったバイト範囲で開始し、したがってフェッチアドレスのオフセットが、分岐セレクタ位置２に関連するバイト範囲内にある場合、フェッチされないからである）。
【００６３】
表７６の「読出アドレス」列は、フェッチアドレスオフセットの比較的簡単なデコーディングを用いて、そのフェッチアドレスに適切な分岐セレクタを選択し得ることを示す。分岐セレクタ位置０および１のデコーディングは、フェッチアドレスオフセットビットの各々を含むが、残りの位置のデコーディングは（ドントケアであるため）最下位ビットを除くこともある。図４に示すバイト範囲の割当てを用いて、迅速なデコードおよび分岐セレクタの選択を達成することができる。
【００６４】
ここで図６を参照して、図４および５に示すバイト範囲の分岐セレクタの第１の例８０が示される。例８０は連続する命令バイトの群のバイト０のみを含むバイト範囲の使用を表わす。例８０は、連続する命令バイトの第１の群のバイト「Ｅ」で終了する命令ＩＮ０と、第１の群のバイト「Ｆ」から第１の群に続く連続する命令バイトの第２の群のバイト０へと延びる予測分岐ＰＢ０と、第２の群のバイト「１」で開始する命令ＩＮ１とを示す。
【００６５】
分岐命令ＰＢ０は第２の群のバイト０まで終了しないので、第２の群は命令キャッシュ１６からフェッチされる必要がある。したがって、第１の群のバイト「Ｅ」および「Ｆ」に対応する分岐セレクタはシーケンシャルを示し、それによって第２の群がフェッチされる。シーケンシャルなフェッチアドレスは（第１の群の最後のバイトの直後のバイトがフェッチされるので）０にセットされたオフセット部分を含む。したがって、第２の群のバイト「０」に対応する分岐セレクタが選択される。この分岐セレクタは、分岐命令ＰＢ０に対応する分岐予測を選択するようにコード化される。
【００６６】
第２の群のバイト０および１が、図４および５に示す他のバイト範囲と同様のバイト範囲を形成した場合、分岐命令ＰＢ０は予測不可能となるであろう。命令バイトの複数の群にわたって延びる分岐の予測を可能にするために、この実施例では、バイト範囲はバイト「０」を含むバイト範囲を含むように規定される。
【００６７】
次に図７を参照して、図４および５に示すバイト範囲の分岐セレクタの第２の例８２が示される。例８２は、予測された分岐命令ＰＢ０の後に復帰命令ＲＥＴが続く状況を表わす。分岐命令ＰＢ０はバイト「４」で終了し、これは分岐セレクタ位置３に対応するバイト範囲内にある（すなわちバイト「４」はバイト範囲の最後のバイトではない）。したがって、分岐セレクタ位置３の分岐セレクタは、バイト範囲内で終了する分岐命令に関して上述したように、ＰＢ０に対する分岐予測を選択しない。ＲＥＴ命令はバイト範囲の最後のバイトで終了する。したがって、分岐セレクタ位置３に対する分岐セレクタは、復帰命令（すなわち例８２のエンコーディング「１」）を示す。
【００６８】
一方、図８は復帰命令が予測されない例８４を表わす。例８４は、予測された分岐命令ＰＢ０、復帰命令ＲＥＴ、および命令ＩＮ１を含む。分岐命令ＰＢ０は分岐セレクタ位置２に対応するバイト範囲の最後のバイトで終了し、したがって対応する分岐セレクタは分岐命令ＰＢ０に対応する分岐予測を選択するようにエンコードされる。この復帰命令は分岐セレクタ位置３に対応するバイト範囲内で終了し、したがってこれに対応する分岐セレクタは復帰命令を示さない。この態様において、命令ＩＮ０がフェッチアドレスによって示されると、復帰命令は分岐セレクタ位置３の分岐セレクタによって誤って予測されることはないであろう。しかしながら、この復帰命令がフェッチアドレスによって示されるバイトである場合、誤った予測を生じる結果となる。
【００６９】
なお、例８４に示すコードシーケンスは通常のものとは異なり得る。なぜなら、ほとんどの場合、一時変数が復帰命令の実行の直前にスタックからポップされるからである。したがって、テイクン予測された分岐が復帰命令の直前にあることは珍しい。
【００７０】
図９は復帰命令が誤予測され得る例８６を示す。例８６では、復帰命令の直後に予測された分岐命令ＰＢ０が続く。分岐命令ＰＢ０を実行する唯一の方法がコードシーケンスの他の場所からこの命令に直接分岐することであるので、このコードシーケンスもまた稀なものであり得る。また、復帰命令は、例８６では直接分岐された場合のみ誤予測される。命令ＩＮ０がフェッチされ実行されると、復帰命令は正しく予測される。
【００７１】
ここで図１０を参照して、分岐予測ユニット１４の一実施例の一部分が示される。分岐予測ユニット１４および図１０に示す部分の他の実施例が企図される。図１０に示すように、分岐予測ユニット１４は分岐予測記憶部９０、ウェイマルチプレクサ９２、分岐セレクタマルチプレクサ９４、分岐予測マルチプレクサ９６、シーケンシャル／復帰マルチプレクサ９８、最終予測マルチプレクサ１００、更新論理ブロック１０２、およびデコーダ１０４を含む。分岐予測記憶部９０およびデコーダ１０４は、命令キャッシュ１６からフェッチアドレスバス１０６に結合される。命令キャッシュ１６に同時に与えられたフェッチアドレスは、フェッチアドレスバス１０６上に伝えられる。デコーダブロック１０４は分岐セレクタマルチプレクサ９４に選択制御を与える。ウェイマルチプレクサ９２の予測制御は、命令キャッシュ１６からウェイ選択バス１０８を介して与えられる。ウェイ選択バス１０８はフェッチアドレスバス１０６に与えられたフェッチアドレスに対応するキャッシュラインを記憶する命令キャッシュ１６のウェイを与える。さらに、選択制御はキャッシュラインのどの部分がフェッチされているかに基づいて、デコーダ１０４によって与えられる。ウェイマルチプレクサ９２はフェッチアドレスバス１０６上のフェッチアドレスによって指された、分岐予測記憶部９０の列内の各記憶場所の内容を受けるように結合される。さらに、分岐セレクタマルチプレクサ９４の出力はマルチプレクサ９６、９８および１００に選択制御を与える。シーケンシャル／復帰マルチプレクサ９８は、命令キャッシュ１６からシーケンシャルアドレスバス１１０上に与えられたシーケンシャルアドレスと、復帰スタックから復帰アドレスバス１１２上に与えられた復帰アドレスとの間で、選択を行なう。マルチプレクサ９６および９８の出力は最終予測マルチプレクサ１００に与えられ、これは分岐予測バス１１４を命令キャッシュ１６に与える。命令キャッシュ１６は分岐予測バス１１４上に与えられた分岐予測を、後続のクロックサイクルのフェッチアドレスとして用いる。更新論理ブロック１０２は、そこに記憶された分岐予測情報を更新するのに用いられる更新バス１１６を介して分岐予測記憶部９０に結合される。更新論理ブロック１０２は予測誤りバス１１８を介して、機能ユニット２４およびデコードユニット２０から信号を与えられた予測誤りに応答して、更新を行なう。さらに、更新論理ブロック１０２は、プリデコードバス１２０上のプリフェッチ／プリデコードユニット１２によって示された新たにプリデコードされた命令に応答して更新を行なう。
【００７２】
この実施例では、分岐予測記憶部９０は命令キャッシュ１６のウェイの数と等しいウェイの数で配置される。各ウェイに対して、キャッシュライン内に存在する連続する命令バイトの各群について分岐予測エントリが記憶される。図１０の実施例では、命令バイトの２つの群が各キャッシュラインに含まれる。したがって、分岐予測エントリＰ00は、第１のウェイにおける連続する命令バイトの第１の群に対応する分岐予測エントリであり、分岐予測エントリＰ01は、第１のウェイにおける連続する命令バイトの第２の群に対応する分岐予測エントリである。同様に、分岐予測エントリＰ10は、第２のウェイにおける連続する命令バイトの第１の群に対応する分岐予測エントリであり、分岐予測エントリＰ11は、第２のウェイにおける連続する命令バイトの第２の群に対応する分岐予測エントリである点などである。指標付けされた行内の分岐予測エントリＰ00からＰ31の各々は、分岐予測記憶部９０の出力として、したがってウェイマルチプレクサ９２の入力として、与えられる。この指標づけされた行はキャッシュへの指標づけと同様である。すなわちフェッチアドレスのオフセット部分に含まれない多数のビットを用いて分岐予測記憶部９０の列のうち１つを選択する。なお、分岐予測記憶部９０は、命令キャッシュ１６より少ない列で構成され得る。たとえば、分岐予測記憶部９０は命令キャッシュ１６の列数の１／４を含み得る。そのような場合、命令キャッシュ１６のインデックスビットであるが分岐予測記憶部９０のインデックスビットではないアドレスビットが、分岐予測情報とともに記憶され、フェッチアドレスの対応するビットに対して照合されて、分岐予測情報がアクセスされている命令キャッシュ１６の列と関連していることを確認する。
【００７３】
ウェイマルチプレクサ９２は、命令キャッシュ１６から与えられたウェイ選択およびフェッチアドレスにより参照される命令バイトの群に基づいて、分岐予測情報Ｐ00からＰ31の組のうち１つを選択する。ここに示す実施例では、たとえば、３２バイトのキャッシュラインは２つの１６バイトの群に分けられる。したがって、フェッチアドレスの最下位から５番目のビットが用いられ、２つの群のいずれがフェッチアドレスを含むかを選択する。下位５ビットが０である場合、連続する命令バイトの第１の群が選択される。下位５ビットが１である場合、連続する命令バイトの第２の群が選択される。なお、ウェイ選択バス１０８上に与えられるウェイ選択は、一実施例に従うと、前のクロックサイクルからの分岐予測によってもたらされたウェイ予測であり得る。これに代えて、ウェイ選択は、フェッチアドレスと命令キャッシュの各ウェイに記憶されるキャッシュラインを特定するアドレスタグとのタグ比較を介して生成され得る。なお、アドレスタグはアドレス中の、キャッシュライン内のオフセットでも命令キャッシュへのインデックスでもない部分である。
【００７４】
ウェイマルチプレクサ９２によって選択された分岐予測エントリは、連続する命令バイトの群に対応する１組の分岐セレクタと、分岐予測ＢＰ１およびＢＰ２とを含む。分岐セレクタは分岐セレクタマルチプレクサ９４に与えられ、これはデコーダ１０４によって与えられた選択制御に基づいて分岐セレクタの１つを選択する。デコーダ１０４はフェッチアドレスのオフセットを連続する命令バイトの群へとデコードし、対応の分岐セレクタを（たとえば一実施例では表７６の「読出アドレス」の列に従って）選択する。たとえば、連続する命令バイトの群が１６バイトである場合、デコーダ１０４はフェッチアドレスの下位４ビットをデコードする。この態様で、分岐セレクタは選択される。
【００７５】
分岐予測マルチプレクサ９６、シーケンシャル／復帰マルチプレクサ９８、および最終予測マルチプレクサ１００に選択制御を与えるために選択された分岐セレクタが用いられる。一実施例では、分岐セレクタのエンコーディングを直接マルチプレクサ選択制御として用いることができる。他の実施例では、分岐セレクタマルチプレクサ９４とマルチプレクサ９６、９８および１００との間に論理ブロックが挿入され得る。ここに示す実施例では、分岐セレクタは２ビットを含む。選択された分岐セレクタのうち１ビットは予測マルチプレクサ９６およびシーケンシャル／復帰マルチプレクサ９８に選択制御を与える。他のビットは最終予測マルチプレクサ１００に対して選択制御を与える。したがって分岐予測は、フェッチされる連続する命令バイトの群に対応する分岐予測記憶部９０に記憶された複数の分岐予測と、フェッチされる連続する命令バイトの群にシーケンシャルな連続する命令バイトの群のシーケンシャルアドレスと、復帰スタック構造からの復帰スタックアドレスとから選択される。なお、マルチプレクサ９６、９８および１００は単一の４ｔｏ１マルチプレクサへ結合されてもよく、選択された分岐セレクタはこれに選択制御を与えて分岐予測記憶部９０からの２つの分岐予測、シーケンシャルアドレス、および復帰アドレスの中から選択する。
【００７６】
復帰スタック構造（図示せず）が、マイクロプロセッサ１０によって前にフェッチされたサブルーチン呼出命令に対応する復帰アドレスを記憶する。一実施例では、分岐予測記憶部９０によって記憶される分岐予測はサブルーチン呼出命令に対応する分岐予測の表示を含む。サブルーチン呼出命令は、命令ストリームをサブルーチン呼出命令のターゲットアドレスにリダイレクトすることに加えてシーケンシャル命令のアドレス（復帰アドレス）を保存する、分岐命令のサブセットである。たとえば、ｘ８６マイクロプロセッサアーキテクチャでは、サブルーチン呼出命令（ＣＡＬＬ）は復帰アドレスをＥＳＰレジスタによって示されるスタック上にプッシュする。
【００７７】
サブルーチン復帰命令は分岐命令の別のサブセットである。サブルーチン復帰命令は、最も最近実行されたサブルーチン呼出命令によって保存された復帰アドレスをターゲットアドレスとして用いる。したがって、分岐予測がその分岐予測がサブルーチン呼出命令に対応するという表示を含むと、サブルーチン呼出命令へのシーケンシャルアドレスは復帰スタックのトップに位置づけられる。サブルーチン復帰命令が（特定の分岐セレクタエンコーディングによって示したように）存在すると、復帰スタックのトップに最も近い、前に予測として用いられていないアドレスをアドレスの予測として用いる。復帰スタックのトップに最も近い、前に予測として用いられていないアドレスは、復帰スタックによって復帰アドレスバス１１２上に（ウェイ選択バス１０８上に与えられるのと同様に復帰スタックに与えられる復帰アドレスの予測されたウェイとともに）伝達される。分岐予測ユニット１４は復帰アドレスが予測として選択されると復帰スタックに知らせる。復帰スタック構造の例に関しては、１９９５年１０月３０日にMahalingaiahらにより出願され「スーパースカラマイクロプロセッサのための同期的復帰アドレス予測ユニット（Speculative Return Address Prediction Unit for a Superscalar Microprocessor）」と題された、同一譲受人に譲渡された同時係属中の特許出願（出願番号０８／５５０，２９６号）により詳細に記載される。
【００７８】
シーケンシャルアドレスは命令キャッシュ１６によって与えられる。シーケンシャルアドレスは、メインメモリ内の連続する命令バイトの次の群をフェッチアドレスバス１０６上のフェッチアドレスによって示された命令バイトの群として特定する。なお、一実施例に従うと、ウェイ予測はシーケンシャルアドレスが選択されるとシーケンシャルアドレスに供給される。ウェイ予測はフェッチアドレスについて選択されるウェイと同じになるように選択され得る。これに代えて、シーケンシャルアドレスのウェイ予測は分岐予測記憶部９０内に記憶され得る。
【００７９】
上述したように、更新論理ブロック１０２は分岐予測誤りの検出時または分岐命令の検出時に分岐予測エントリを更新し、かつプリフェッチ／プリデコードユニット１２で連続する命令バイトの対応する群をプリデコードするように構成される。各分岐予測に対応する分岐予測エントリは予測が実行されると更新論理ブロック１０２に記憶され得る。分岐タグはフェッチされる命令とともに（分岐タグバス１２２を介して）伝達されるので、プリデコーディング中に予測誤りが検出されるかまたは分岐命令が検出されると、対応の分岐予測エントリが分岐タグを介して特定され得る。一実施例では、図１１に示す分岐予測エントリは、フェッチすべき分岐予測エントリを生じたフェッチアドレスのインデックスおよび分岐予測エントリが記憶されるウェイと同様に、記憶される。
【００８０】
分岐予測誤りが検出されると、分岐命令を実行する機能ユニット２４またはデコードユニット２０のいずれかから予測誤りバス１１８上に対応の分岐タグが与えられる。デコードユニット２０が分岐タグを与えると、予測誤りは前に検出されなかったタイプのものとなる（たとえば、群内に対応の分岐予測を用いて予測できる以上の分岐命令がある）。デコードユニット２０は無条件分岐命令（すなわち常にターゲットアドレスを選択する分岐命令）の予測誤りを検出する。機能ユニット２４は前に検出されなかった条件付き分岐命令による、または誤ったテイクン／ノットテイクン予測による、予測誤りを検出し得る。更新論理１０２は上述の記憶部から対応の分岐予測エントリを選択する。前に検出されなかった分岐命令の場合は、分岐予測エントリ内の分岐予測の１つが前に検出されなかった分岐命令に割当てられる。一実施例に従うと、前に検出されなかった分岐命令に対する分岐予測を記憶するために分岐予測の１つを選択するアルゴリズムは次のとおりである。分岐命令がサブルーチン復帰命令である場合、その命令の分岐セレクタは復帰スタックを示す値になるように選択される。それ以外は、現在ノットテイクンと予測されている分岐予測が選択される。分岐予測の各々が現在テイクン予測である場合、分岐予測はランダムに選択される。
【００８１】
新たに検出された分岐命令の分岐セレクタは、選択された分岐予測を示すようにセットされる。さらに、新たに検出された分岐命令に先行する第１の分岐命令と新たに検出された分岐命令との間のバイト範囲に対応する分岐セレクタが、新たな予測に対応する分岐セレクタとしてセットされる。図１４を参照して、分岐セレクタを更新するためのある方法を以下に示す。予測をノットテイクン予測としてしまう誤予測がされたテイクン予測に対しては、予測誤りのあった予測に対応する分岐セレクタが、予測誤りのあった分岐命令に続くバイトに対応する分岐セレクタとしてセットされる。この方法では、命令が後のクロックサイクルで再びフェッチされると、後続の分岐命令の予測が用いられるであろう。
【００８２】
プリフェッチ／プリデコードユニット１２が分岐命令を検出し、かつ連続する命令バイトの群をプリデコードすると、プリフェッチ／プリデコードユニット１２は、キャッシュラインの命令キャッシュに無効なプリデコード情報が記憶されるので、プリデコーディングが行なわれると連続する命令バイトの群に分岐タグを与える。（例（ｉ））。これに代えて、キャッシュラインがメインメモリサブシステムからフェッチされるときにプリデコーディングが行なわれる場合、プリフェッチ／プリデコードユニット１２はプリデコードされている連続する命令バイトの群のアドレスと、その群内の分岐命令のエンドバイトのオフセットと、その群を記憶するように選択された命令キャッシュのウェイとを与える（例（ｉｉ））。例（ｉ）では、上記の分岐予測誤りの場合と同様に更新が行なわれる。例（ｉｉ）では、命令の群に対する分岐予測記憶部９０に記憶された有効な分岐予測エントリはまだない。この場合、更新論理ブロック１０２は、検出された分岐に先行する分岐セレクタを、検出された分岐のために選択された分岐セレクタに初期化する。さらに、検出された分岐に続く分岐セレクタはシーケンシャル値に初期化される。これに代えて、分岐セレクタの各々は、命令キャッシュ１６の対応するキャッシュラインが割当てられるとシーケンシャルに初期化されてもよく、プリデコード中に分岐命令の検出によって例（ｉ）と同様の方法で後に更新されてもよい。
【００８３】
更新の発生時、更新論理ブロック１０２は更新された分岐予測エントリをフェッチアドレスインデックスおよび対応するウェイとともに更新バス１１６上に与え、分岐予測記憶部９０に記憶する。なお、分岐予測記憶部９０は、分岐予測記憶部９０を単一ポートの記憶部として維持するために分岐保持レジスタを採用し得る。更新された予測情報は分岐保持レジスタ内に記憶され、フェッチアドレスバス１０６におけるアイドルサイクル時に分岐予測記憶部へと更新される。キャッシュ保持レジスタ構造の例は、１９９５年６月７日にTranらにより出願され「アレイのための遅延更新レージング（Delayed Update Pegister for an Array）」と題された同一譲受人の同時係属特許（出願出願番号０８／４８１，９１４号）に記載される。
【００８４】
なお、正しく予測された分岐命令の結果、対応の分岐予測も同様に更新され得る。分岐命令の前の実行を示すカウンタ（分岐命令のテイクン／ノットテイクン予測を形成するのに用いられる）は、たとえば増分または減分される必要があるかもしれない。このような更新は、対応の分岐予測のリタイア時に実行される。リタイアはリオーダバッファ３２からリタイアタグバス１２４上の分岐タグを介して示される。
【００８５】
図１０の構造は、予測された分岐セレクタを用いることにより、さらに加速され得ることがわかる。予測された分岐セレクタは各分岐予測エントリとともに記憶され、連続する命令バイトの対応する群の前のフェッチにおいて選択された分岐セレクタとしてセットされる。予測された分岐セレクタは分岐予測を選択するのに用いられ、分岐セレクタマルチプレクサ９４を分岐予測発生経路から取除く。しかしながら、選択された分岐セレクタが予測された分岐セレクタと等しいことを確認するために、分岐セレクタマルチプレクサ９４がなおも採用される。選択された分岐セレクタと予測された分岐セレクタが等しくない場合、選択された分岐セレクタが用いられ、後続のクロックサイクル中に正しい分岐予測を与え、正しくない分岐予測のフェッチは取り消される。
【００８６】
ここで図１１を参照して、図１０に示す分岐予測ユニット１４の一実施例によって採用された分岐予測エントリ１３０の例が示される。分岐予測エントリ１３０は、１組の分岐セレクタ１３６、第１の分岐予測（ＢＰ１）１３２、および第２の分岐予測（ＢＰ２）１３４を含む。分岐セレクタ１３６の組は、分岐予測エントリ１３０に対応する連続する命令バイトの群の各バイト範囲について分岐セレクタを含む。
【００８７】
第１の分岐予測１３２は図１１に分解図で示される。第２の分岐予測１３４も同様に構成され得る。第１の分岐予測１３２はターゲットアドレスに対応する命令バイトを含むキャッシュラインに対するインデックス１４０、およびキャッシュラインに対するウェイ選択部１４４を含む。一実施例に従うと、インデックス１４０はターゲットアドレスおよびインデックスのオフセット部分を含む。インデックス１４０はウェイ選択部１４４によって示されるウェイのタグと連結されて分岐ターゲットアドレスを形成する。これに代えて、分岐ターゲットアドレス全体がインデックスフィールド１４０に記憶されてもよい。分岐ターゲットアドレス全体に加えてウェイ予測が与えられるか、またはは命令キャッシュ１６の指標づけされた行内のタグに対してタグ比較を用いてウェイ選択が行なわれ得る。
【００８８】
さらに、プレディクタ１４６が各分岐予測について記憶される。プレディクタ１４６は、対応する分岐命令が実行されテイクンである毎に増分され、対応する分岐命令が実行されてノットテイクンである毎に減分される。プレディクタ１４６の最上位ビットはテイクン／ノットテイクン予測として用いられる。最上位ビットがセットされると、分岐命令はテイクンとして予測される。逆に、最上位ビットがクリアであると、分岐命令はノットテイクンとして予測される。一実施例では、予測カウンタは２ビットの飽和カウンタである。このカウンタは、バイナリ「１１」で増分されると飽和し、またバイナリ「０１」で減分されると飽和する。別の実施例では、このプレディクタは強い（バイナリ１）または弱い（バイナリ０）テイクン予測を示す単一ビットである。強いテイクン予測が誤って予測されると、それは弱いテイクン予測となる。弱いテイクン予測が誤って予測されると、分岐はノットテイクンと予測されることになり、分岐セレクタが更新される（すなわち誤予測されノットテイクンとなる分岐の場合）。最後に、呼出ビット１４８が第１の分岐予測１３２に含まれる。呼出ビット１４８は、セット時には対応の分岐命令がサブルーチン呼出命令であることを示す。呼出ビット１４８がセットされると、現在のフェッチアドレスおよびウェイは上述の復帰スタック構造内へ記憶される。
【００８９】
次に図１２を参照して、分岐セレクタエンコーディングの例を表す表１３８が示される。分岐セレクタが対応する値でエンコードされたときに選択された分岐予測に続いて、バイナリエンコーディングがリストされる（はじめに最上位ビット）。表１３８が表すように、分岐セレクタの最下位ビットは、分岐予測マルチプレクサ９６およびシーケンシャル／復帰マルチプレクサ９８に対する選択制御として用いられ得る。最下位ビットがクリアされると、第１の分岐予測は分岐予測マルチプレクサ９６によって選択され、シーケンシャルアドレスはシーケンシャル／復帰マルチプレクサ９８によって選択される。一方、第２の分岐予測は、最下位ビットがクリアされると、分岐予測マルチプレクサ９６によって選択され、復帰アドレスはシーケンシャル／復帰マルチプレクサ９８によって選択される。さらに、分岐セレクタの最上位ビットは最終予測マルチプレクサ１００に対する選択制御として用いられ得る。最上位ビットがセットされると、分岐予測マルチプレクサ９６の出力が選択される。最上位ビットがクリアされると、シーケンシャル／復帰マルチプレクサ９８の出力が選択される。
【００９０】
次に図１３を参照して、図４および５で規定されたバイト範囲に従って、命令キャッシュ１６からフェッチされた連続する命令バイトの群に対する有効マスクの生成を表すフローチャートが示される。この有効マスクは群内の各命令バイトについて１ビットを含み、これはこのバイトが予測された命令ストリームの部分であるか否かを示す。マスク内の有効ビットはフェッチアドレスのオフセット部分によって選択されるバイトと、選択された分岐予測によって予測される分岐命令との間にセットされる。これらのバイトは、命令キャッシュ１６から読出される連続する命令バイトの群からフェッチされる命令を含む。フェッチアドレスのオフセットより前のバイトはフェッチされず、テイクン予測された分岐命令に後続するバイトもまたフェッチされない。分岐命令のエンドは、対応の分岐セレクタの最後の例によってほぼ位置づけられる。しかしながら、分岐命令がバイト範囲内で終了する場合には、分岐命令の最終バイトを包含するように調整がなされ得る。
【００９１】
現在の分岐セレクタ（すなわちフェッチアドレスをデコードすることで分岐予測ユニット１４によって選択された分岐セレクタ）は、連続する命令バイトの群に対応する分岐セレクタで排他的ＮＯＲされ（ステップ１５０）、よってバイト範囲ごとに１ビットを含む予備的マスクを作り出す。現在の分岐セレクタに等しい分岐セレクタに対応するバイト範囲の各々はこの予備的マスクにおけるビットがセットされていることによって表され、現在の分岐セレクタと異なる分岐セレクタを含むバイト範囲は予備的マスク内のクリアビットによって表される。第１のマスクは、１バイトより大きいバイト（本実施例では２バイト）を有するバイト範囲に対応する予備的マスクにおける各ビットを複製することにより予備的マスクから作成される（ステップ１５２）。一般に、このビットはバイト範囲を表すビットの総数がバイト範囲内のビット数と等しくなるまでコピーされる。さらに、第２のマスクは第１のマスクを右にシフトさせることにより作成される（ステップ１５４）。
【００９２】
テイクン予測された分岐命令が（バイト範囲のエンドではなく）バイト範囲内で終了する場合、有効マスクが第１のマスクと第２のマスクとを論理和することにより作成される（判断ブロック１５６およびステップ１５８）。この様にして、分岐命令が終了するバイト範囲内にあり分岐命令の一部であるバイトの有効が確認される。一方、分岐命令がバイト範囲のエンドで終了する場合、そのバイト範囲に対する分岐セレクタは分岐命令を示す。この場合、第１のマスクが第２のマスクを用いて修正しなくても正しい。したがって、第１のマスクが有効マスクとして選択される（ステップ１６０）。
【００９３】
ここで図１４を参照して、誤って予測された分岐命令に応答して連続する命令バイトの群の分岐セレクタを更新するように採用されたステップを表すフローチャートが示される。プリデコーディング中に発見された分岐命令に起因する更新も同様に行なわれ得る。この予測誤りは、予測情報が分岐予測記憶部９０に記憶されていない分岐命令を検出した結果であるか、または対応のプレディクタにノットテイクンであると示させる誤ったテイクン／ノットテイクン予測の結果であり得る。
【００９４】
予測誤りが検出されると、分岐予測ユニット１４は「エンドポインタ」、すなわち連続する命令バイトの対応する群内の誤予測された分岐命令のエンドバイトのオフセット、を用いる。さらに、予測誤りに応答して受取った分岐タグを用いて、更新するための分岐予測エントリが選択される。分岐予測ユニット１４はエンドポインタを更新マスクへデコードする（ステップ１７０）。更新マスクは、連続する命令バイトの群内の各バイト範囲に対して１ビットを含む。分岐命令のエンドバイトを含むバイト範囲の前のバイト範囲に対応するビットがセットされ（エンドバイトがバイト範囲内の最終バイトであれば、分岐命令のエンドバイトを含むバイト範囲に対応するビットがセットされる）、残りのビットはクリアされる。したがって更新マスクは、分岐命令に先行しかつ分岐命令を含むバイト範囲の各々を特定する。
【００９５】
分岐予測ユニット１４は現在の分岐セレクタを特定する。誤って予測されたテイクン／ノットテイクン予測については、現在の分岐セレクタは誤って予測された分岐命令に対応する分岐セレクタである。検出されなかった分岐による予測誤りに関しては、現在の分岐セレクタは検出されなかった分岐命令のエンドバイトを含むバイト範囲に対応する分岐セレクタである。現在の分岐セレクタは分岐セレクタの各々で排他的ＮＯＲされて分岐マスクを作成する（ステップ１７２）。分岐マスクは、現在の分岐セレクタに適合する分岐セレクタを有する各バイト範囲についてセットされるビットと、現在の分岐セレクタに適合しない分岐セレクタを有する各バイト範囲についてクリアされるビットとを含む。
【００９６】
ステップ１７０で作成された更新マスクとステップ１７２で作成された分岐マスクとは後に論理積が行なわれ、最終更新マスクを生成する（ステップ１７４）。最終更新マスクは、新たな分岐セレクタへ更新すべき連続する命令バイトの群の各バイト範囲についてセットされるビットを含む。誤ってテイクン予測された分岐については、新たな分岐セレクタは、誤ってテイクン予測された分岐命令に後続するバイト範囲の分岐セレクタである。検出されなかった分岐に対しては、新たな分岐セレクタは、更新論理ブロック１０２によって前に検出されなかった分岐に割当てられた分岐予測記憶部を示す分岐セレクタである。
【００９７】
拡張マスクもまた生成される（ステップ１７６および１７８）。この拡張マスクは、分岐セレクタに対応する分岐予測が新たに発見された分岐命令に再び割当てられていること、または分岐予測がここでノットテイクンを示すことから、いずれの分岐セレクタが消去されるべきかを示す。拡張マスクは、まず第２の分岐マスクを作成し、これは現在の分岐セレクタの代わりに新たな分岐セレクタを用いること以外は分岐マスクと同様である（すなわちこのマスクは連続する命令バイトの群に対応する分岐セレクタを新たな分岐セレクタで排他的ＮＯＲすることにより作成される（ステップ１７６））。結果として生じるマスクはその後、最終更新マスクの反転と論理積され、拡張マスクを作成する（ステップ１７８）。拡張マスク内のセットされているビットに対応する分岐セレクタは、拡張マスクのビットがセットされている対応する最終バイト範囲の直後のバイト範囲の分岐セレクタを示すように更新される。この態様で、分岐セレクタによって前に示されていた分岐予測は消去され、次の分岐セレクタで置換される。ステップ１８０で、分岐セレクタは最終更新マスクおよび拡張マスクに応答して更新される。
【００９８】
次に図１５を参照して、命令バイト５０、領域５８、６０および６２、ならびに１組の分岐セレクタ１９０の別の実施例の図が表される。セット１９０は最初のバイト範囲と最後のバイト範囲とが各々単一バイトを含み、他の範囲が２バイトを含む、１組のバイト範囲に対応する。セット１９０は図４で割当てられたバイト範囲に対する代替のバイト範囲の割当てとして用いられ得る。多くの他のバイト範囲の割当ても可能であり、さまざまな実施例において企図される。図１６は表７６と同様の表１９２である。表１９２は、図１５に表すバイト範囲についてのバイト位置、分岐セレクタ位置、読出アドレスおよびエンコーディングアドレスを表す。
【００９９】
ここで図１７を参照して、マイクロプロセッサ１０を含むコンピュータシステム２００が示される。コンピュータシステム２００は、バスブリッジ２０２、メインメモリ２０４、および複数の入力／出力（Ｉ／Ｏ）装置２０６Ａ−２０６Ｎをさらに含む。複数のＩ／Ｏ装置２０６Ａ−２０６Ｎを、まとめてＩ／Ｏ装置２０６と呼ぶことにする。マイクロプロセッサ１０、バスブリッジ２０２、およびメインメモリ２０４はシステムバス２０８に結合される。Ｉ／Ｏ装置２０６はバスブリッジ２０２と通信するためにＩ／Ｏバス２１０に結合される。
【０１００】
バスブリッジ２０２は、Ｉ／Ｏ装置２０６とシステムバス２０８に結合された装置との間の通信を補助するために設けられる。Ｉ／Ｏ装置２０６は典型的にはマイクロプロセッサ１０およびシステムバス２０８に結合された他の装置よりも長いバスクロックサイクルを要求する。したがって、バスブリッジ２０２はシステムバス２０８と入力／出力バス２１０との間にバッファを設ける。さらに、バスブリッジ２０２はトランザクションをあるバスプロトコルから別のものへと変換する。一実施例では、入力／出力バス２１０はＥＩＳＡ（Enhanced Industry Standard Architecture）バスであり、バスブリッジ２０２はシステムバスプロトコルからＥＩＳＡバスプロトコルへ変換する。別の実施例では、入力／出力バス２１０はＰＣＩ（Peripheral Component Imterconnect）バスであり、バスブリッジ２０２はシステムバスプロトコルをＰＣＩバスプロトコルへ変換する。なお、システムバスプロトコルには多くの変形例が存在する。マイクロプロセッサ１０は適切であればいかなるシステムバスプロトコルを採用してもよい。
【０１０１】
Ｉ／Ｏ装置２０６はコンピュータシステム２００とコンピュータシステム外部の他の装置との間にインタフェースを設ける。Ｉ／Ｏ装置の例はモデム、シリアルまたはパラレルポート、およびサウンドカードなどである。Ｉ／Ｏ装置２０６もまた周辺装置と呼ばれ得る。メインメモリ２０４はマイクロプロセッサ１０が用いるためのデータおよび命令を記憶する。一実施例では、メインメモリ２０４は少なくとも１つのダイナミック・ランダム・アクセス・メモリ（ＤＲＡＭ）およびＤＲＡＭメモリコントローラを含む。
【０１０２】
図１７に示すコンピュータシステム２００は１つのバスブリッジ２０２を含むが、コンピュータシステム２００の他の実施例は、複数の異なるまたは同様のＩ／Ｏバスプロトコルに変換するために複数のバスブリッジ２０２を含み得る。またさらに、マイクロプロセッサ１０によって参照される命令およびデータをより高速のメモリ記憶部に記憶することによりコンピュータシステム２００の性能を向上させるためのキャッシュメモリも含まれ得る。このキャッシュメモリは、マイクロプロセッサ１０とシステムバス２０８との間に挿入されるか、またはシステムバス２０８上に「ルックアサイド」構成で存在し得る。さらに注目されることは、バスブリッジ２０２、メインメモリ２０４、およびキャッシュメモリの機能はマイクロプロセッサ１０にインタフェースするチップセット内に集積され得ることである。
【０１０３】
またさらに、ここでの議論は、さまざまな信号のアサートに言及する。ここでは、信号は特定の状態を示す値を伝達すると「アサートされる」という。逆に、特定の状況がないことを示す値を伝達すると信号が「デアサート」されるという。信号は、それが論理値０を伝達するとき、または逆に論理値１を伝達するときに、アサートされるというふうに定義できる。さらに、上記の議論においてはさまざまな値が廃棄されているとして述べられている。値は多くの態様で廃棄され得るが、通常はその値を受ける論理回路によって無視されるような値に変更することを含む。たとえば、ある値がビットを含むとき、その値を廃棄するためにはその論理状態を反転するようにしてもよい。値がｎビット値である場合、ｎビットエンコーディングのうちの１つが、その値が無効であることを示すようにしてもよい。値を無効のエンコーディングにセットすることにより、その値は廃棄される。さらに、ｎビット値が、セットされるとそのｎビット値が有効であることを示すような有効ビットを含んでもよい。有効ビットをリセットすることにより値の廃棄がされる。値を廃棄するための他の方法を用いてもよい。
【０１０４】
以下の表１は、ｘ８６命令セットを採用するマイクロプロセッサ１０の一実施例に関するファストパス、二重ディスパッチ、およびＭＲＯＭ命令を示す。
【０１０５】
【表１】
0003794917.tif 000002
【０１０６】
【表２】
0003794917.tif 000003
【０１０７】
【表３】
0003794917.tif 000004
【０１０８】
【表４】
0003794917.tif 000005
【０１０９】
上記の開示に従って、分岐セレクタを用いて後続のフェッチアドレスを作成する際に用いる分岐予測を選択するマイクロプロセッサについて述べてきた。分岐セレクタの迅速な選択を提供するためには、各分岐セレクタはバイト範囲と関連づけられており、最大のバイト範囲は最短の分岐命令と等しい（一実施例）。したがって、高度に正確かつ迅速な分岐予測をなおも提供しつつ、相対的に最小数の分岐セレクタが設けられる。
【０１１０】
上記の開示を完全に認識すると当業者には多くの変形例および修正例が明らかになるであろう。
【図面の簡単な説明】
【図１】  スーパースカラマイクロプロセッサの一実施例のブロック図である。
【図２】  図１に示す１対のデコードユニットの一実施例のブロック図である。
【図３】  図１に示すマイクロプロセッサの分岐予測機構の一実施例に従った、連続する命令バイトの群および対応する組の分岐セレクタのブロック図である。
【図４】  図１に示すマイクロプロセッサの分岐予測機構の別の実施例に従った、連続する命令バイトの群および対応する組の分岐セレクタのブロック図である。
【図５】  １組の連続する命令バイト内のバイト範囲の一実施例を表す表である。
【図６】  第１の組の命令の例に対する分岐セレクタの第１の例である。
【図７】  第２の組の命令の例に対する分岐セレクタの第２の例である。
【図８】  第３の組の命令の例に対する分岐セレクタの第３の例である。
【図９】  第４の命令セットの例に対する分岐セレクタの第４の例である。
【図１０】  図１に示す分岐予測ユニットの一実施例のブロック図である。
【図１１】  連続する命令バイトの群に対応する分岐予測記憶部エントリの一実施例のブロック図である。
【図１２】  図１に示す分岐予測ユニットの一実施例に対する分岐セレクタエンコーディングの例を示す表である。
【図１３】  図１に示すマイクロプロセッサの一実施例に従ったマスク生成を表すフローチャートである。
【図１４】  分岐セレクタ更新の一実施例を表すフローチャートである。
【図１５】  図１に示すマイクロプロセッサの分岐予測機構のさらに別の実施例に従った、連続する命令バイトの群および対応する組の分岐セレクタのブロック図である。
【図１６】  １組の連続する命令バイト内のバイト範囲の別の実施例を示す表である。
【図１７】  図１に示すマイクロプロセッサを含むコンピュータシステムの一実施例のブロック図である。
【図１】
0003794917.tif 000006
【図２】
0003794917.tif 000007
【図３】
0003794917.tif 000008
【図４】
0003794917.tif 000009
【図５】
0003794917.tif 000010
【図６】
0003794917.tif 000011
【図７】
0003794917.tif 000012
【図８】
0003794917.tif 000013
【図９】
0003794917.tif 000014
【図１０】
0003794917.tif 000015
【図１１】
0003794917.tif 000016
【図１２】
0003794917.tif 000017
【図１３】
0003794917.tif 000018
【図１４】
0003794917.tif 000019
【図１５】
0003794917.tif 000020
【図１６】
0003794917.tif 000021
【図１７】
0003794917.tif 000022