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