(57)【特許請求の範囲】
【請求項１】
記憶装置に接続される演算処理装置において、
前記記憶装置から分岐命令を含む命令を命令アドレスに基づいて取得する取得部と、
前記取得部が取得した命令を実行する実行部と、
前記取得部が取得した分岐命令の分岐先アドレスに含まれる所定の上位ビット部分を、複数に区分されたアドレス範囲のいずれかに対応するアドレス範囲識別情報に符号化するとともに、前記実行部が実行した分岐命令の分岐先アドレスが前記複数のアドレス範囲のいずれかに分岐する分岐命令である場合、前記アドレス範囲識別情報と実行された前記分岐命令の種類とに基づいて前記上位ビット部分を復元する制御部と、
前記実行部が実行した分岐命令の分岐先アドレスに対応するアドレス範囲識別情報と前記分岐先アドレスから前記上位ビット部分を除いた下位ビット部分の一部とを含む履歴情報を、前記下位ビット部分から決定される複数の格納先のいずれかに記憶する履歴記憶部と、
前記制御部が復元した前記上位ビット部分を含む命令アドレスに基づいて、前記取得部が次に取得する命令の命令アドレスを算出する算出部と、
前記実行部が過去に実行した命令に対応する履歴情報に基づいて、前記取得部が次に取得する命令の分岐予測を行う分岐命令予測部を有することを特徴とする演算処理装置。
【請求項２】
前記制御部は、前記上位ビット部分を複数のアドレス範囲ごとに区分し、区分された第１のアドレス範囲を識別する第１のアドレス範囲識別情報と前記第１のアドレス範囲以外のアドレス範囲を識別する第２のアドレス範囲識別情報とを生成する手段と、
前記分岐命令の分岐先アドレスが、前記第１のアドレス範囲識別情報で識別される前記第１のアドレス範囲に分岐する分岐命令である場合に、前記第１のアドレス範囲に対応する上位ビット部分を生成する手段と、
前記分岐命令が前記第２のアドレス範囲識別情報で識別されるアドレス範囲に分岐する分岐命令である場合に、分岐命令の種類を識別する信号を前記実行部から受信する分岐種別情報受信部と、
前記分岐命令が前記下位ビット部分の範囲を限界として分岐元アドレスから相対分岐する相対分岐命令である場合に、前記実行部における前記分岐命令の処理において前記下位ビット部分の範囲から正方向または負方向に桁あふれが発生したことを示す桁あふれ情報
を受信する桁あふれ情報受信部と、
前記桁あふれが発生した場合に、分岐元アドレスの上位ビット部分への加減算によって分岐先アドレスの上位ビット部分を取得する算術部と、を有する請求項１に記載の演算処理装置。
【請求項３】
前記制御部は、分岐種別情報受信部が前記相対分岐命令でない場合に、分岐命令の分岐先を算出した前記実行部から分岐先アドレスの上位ビット部分を取得する上位ビット取得部を有する請求項２に記載の演算処理装置。
【請求項４】
記憶装置に接続される演算処理装置の制御方法において、
前記演算処理装置が有する取得部が、前記記憶装置から命令アドレスに基づいて分岐命令を含む命令を取得し、
前記演算処理装置が有する制御部が、前記取得部が取得した分岐命令の分岐先アドレスに含まれる所定の上位ビット部分を、複数に区分されたアドレス範囲のいずれかに対応するアドレス範囲識別情報に符号化し、
前記演算処理装置が有する実行部が、前記取得部が取得した命令を実行し、
前記制御部が、前記実行部が実行した分岐命令の分岐先アドレスが前記複数のアドレス範囲のいずれかに分岐する分岐命令である場合、前記アドレス範囲識別情報と実行された前記分岐命令の種類とに基づいて前記上位ビット部分を復元し、
前記演算処理装置が有する履歴記憶部が、前記実行部が実行した分岐命令の分岐先アドレスに対応するアドレス範囲識別情報と前記分岐先アドレスから前記上位ビット部分を除いた下位ビット部分の一部とを含む履歴情報を、前記下位ビット部分から決定される複数の格納先のいずれかに記憶し、
前記演算処理装置が有する算出部が、前記制御部が復元した前記上位ビット部分を含む命令アドレスに基づいて、前記取得部が次に取得する命令の命令アドレスを算出し、
前記演算処理装置が有する前記分岐命令予測部が、前記実行部が過去に実行した命令に対応する履歴情報に基づいて、前記取得部が次に取得する命令の分岐予測を行うことを特徴とする演算処理装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、特に命令処理装置に関する。
【背景技術】
【０００２】
情報処理装置の分岐予測機構は、過去に実行された命令のメモリ上での記憶アドレス（以下、命令アドレスという）を基に分岐命令の実行履歴を管理することによって、次に分岐命令が実行される場合の分岐先を予測していた（例えば、下記特許文献１参照）。【０００３】
その場合、分岐予測機構は、過去に記憶元から命令を取得（命令をフェッチするという）された分岐命令の命令アドレス（分岐元アドレス）の一部のビット部分からセットアソアシアティブ方式の記憶装置のセットを決定する。そして、分岐予測機構は、分岐元アドレスのさらに他のビット部分をタグにして、当該セット内の１つのウェイに分岐先アドレスを記憶しておく。【０００４】
そして、分岐予測機構は、命令のフェッチ段階で命令アドレスを利用して、上記記憶装置を検索する。そして、過去に実行済みの分岐命令で、その分岐先アドレスが記憶装置に記憶されている場合には、分岐予測機構は、該当するセット内のタグの内容が一致するウェイから分岐先アドレスを入手できる。すなわち、命令のフェッチと並行して、その命令が分岐命令であるか否か（分岐元の命令アドレスの部分をタグにして分岐先アドレスが記憶されているか否か）を判定することができた。【０００５】
すなわち、この技術では、情報処理装置は、現在のフェッチ中の命令のアドレスを取得することにより、命令のフェッチと並行して、その命令が分岐命令であるか否かを判定し、命令が分岐命令であった場合に予測される分岐先アドレスを入手できる。したがって、情報処理装置がパイプライン処理を行っている場合であっても、現在の命令フェッチと並行して、事前に予測される分岐先から次のステージでの命令フェッチを準備することができる。【０００６】
そして、現在フェッチ中の命令から得られた分岐先が予測された分岐先であった場合には、パイプライン処理を止めることなく各ステージを並列動作できる。一方、現在フェッチ中の命令から得られた分岐先が予測された分岐先でなかった場合には、正しい分岐先から命令フェッチを再開することになる。現在フェッチ中の分岐命令の命令アドレスに対応して上記記憶手段に分岐先が記憶されていなかった場合（分岐予測がヒットしなかったが分岐命令が実行された場合）も、分岐予測を利用できず、フェッチ後の分岐命令をデコードして得られた分岐先アドレスから命令フェッチを再開することになる。【０００７】
ところで、従来、情報処理装置において、命令が格納される空間は、３２ビットアドレス空間であった。しかし、処理されるデータ量の増加に対応して、アドレス空間を６４ビットに拡張したものも存在する。そのような情報処理装置では、データ空間のみならず命令空間も６４ビット化された。【０００８】
しかし、実際のプログラムのサイズは４ＧＢよりもかなり小さく（最も大きいプログラムでも数百ＭＢ程度である）、６４ビット分の完全なアドレスすべてを投機的な実行処理部に記憶または処理させるのは、ハードウェア資源の無駄といえる。【０００９】
したがって命令セットアーキテクチャで定義されたやむを得ない部分だけを６４ビット化することが効率的である。そこで、分岐予測により投機的に命令フェッチを制御する制御部などは極力下位３２ビットのアドレスだけを用いて、従来と同様の命令フェッチ等の制御を行ってきた。【００１０】
具体的な方法としては、予め上位３２ビットのアドレスを固定しておき、その固定された上位３２ビットと下位３２ビットの４Ｇバイト空間とを用いて命令フェッチを行う。そして、４Ｇバイト空間を越えれば、上位３２ビットを再定義する、というものが考えられる。【００１１】
つまり、プログラムカウンタの上位３２ビットは通常固定しておく。そして、上位３２ビットを変更するような、分岐命令や例外、割り込みなどでプログラムカウンタの上位３２ビットを変える事象が発生したときには、上位３２ビットを改めて求める。この場合、その上位３２ビットを変更しようとする命令（事象）の完了をもって投機処理中の命令フェッチ／命令実行パイプラインを一旦完全にクリアすることになる。【００１２】
そのため、プログラムカウンタの上位３２ビットを新しい値に書き換えたのちに、その新しいアドレスでもって命令フェッチより再開する。すなわち、上位３２ビットが変更される事象があるときには投機実行の恩恵を全く受けることができない。これでもプログラムサイズが小さい以上問題はないはずであった。ところが、実際のＯＳは、割り付けるべきプログラムサイズが小さい場合でも、６４ビットの命令アドレスの上位３２ビットを複数個所利用する制御をするようになった。【００１３】
この場合には、６４ビットの仮想メモリ空間に、プログラムが散在することもありえないことではない。そうすると、個々のプログラムが小さい場合でも、分岐命令によって３２ビットの４Ｇバイトアドレスを越える分岐が頻繁に発生することもありえる。
【特許文献１】特開２００４−３８３９８号公報
【発明の開示】
【発明が解決しようとする課題】
【００１４】
従来の方法では、３２ビットの４Ｇバイトアドレスを越える度に、上位３２ビットを再定義するまでの期間は投機命令フェッチを失敗するということになる。例えば、4Ｇバイトを越えた分岐命令があったとして、たとえ下位３２ビットが正しく分岐予測機構により予測されたとしても、上位３２ビットは古いままであるために、予測を誤ることになる。【００１５】
投機命令フェッチを失敗するということは、結果として一切の投機実行が失敗するということであり、その損失は計り知れない。これを改善し、より高い性能を求めるためには、すべてにおいて６４ビットアドレスを完全に使用して分岐予測等を行うことが考えられる。しかし、前述の通り、コストやクロックサイクルを考慮すると、これは現実解ではない。本発明の目的は、このような従来の問題点を解決することにある。
【課題を解決するための手段】
【００１６】
本発明は前記課題を解決するために、以下の手段を採用した。すなわち、本発明は、少なくとも命令の記憶元から命令を取得する取得段階と前記命令を処理する実行段階とを含む実行サイクルを繰り返す、そのようなコンピュータの前記取得段階で命令を取得する取得部と、前記取得部が取得する命令の記憶元である命令アドレスを決定するアドレス制御部と、前記コンピュータによって次の命令実行段階で処理される命令が分岐命令であるか否かを過去に処理された命令の履歴情報にしたがって予測する分岐命令予測部と、前記取得された命令の少なくとも１つを前記実行段階で処理する実行部と、を備え、前記アドレス制御部は、前記命令アドレスに含まれる所定の上位ビット部分と下位ビット部分のうち、前記上位ビット部分を圧縮した上位アドレス情報を生成する符号化部と、前記上位アドレス情報から上位ビット部分を復元する復元部とを有し、前記分岐命令予測部は、前記処理された分岐命令の分岐先アドレスに対応する上位アドレス情報と下位ビット部分とを、前記分岐命令の記憶元の命令アドレスに対応する上位アドレス情報と下位ビット部分から決定される複数の格納先のいずれかに前記履歴情報として記憶する履歴記憶部を有する処理装置である。【００１７】
本発明によれば、処理された分岐命令の分岐先アドレスに対応する上位アドレス情報と下位ビット部分とが、分岐命令の記憶元の命令アドレスに対応する上位アドレス情報と下位ビット部分から決定される複数の格納先のいずれかに履歴情報として記憶される。この場合、上位アドレス情報は、上位ビット部分を圧縮した情報である。したがって、命令アドレス長が拡張され、アドレス空間が増加した場合であっても、圧縮された上位アドレス情報と下位ビット部分によって効率的に分岐先アドレスに対応する情報を管理できる。なお、ここで、命令を処理するとは、命令にしたがった所定の処理を実行することをいい、例えば、条件付き分岐命令の場合には、条件の判定と判定結果に基づく分岐先への分岐または分岐しない処理を含む。【００１８】
前記符号化部は、前記上位ビット部分を複数のアドレス範囲ごとに区分し、区分された第１のアドレス範囲を識別する第１の上位アドレス情報と前記第１のアドレス範囲以外のアドレス範囲を識別する第２の上位アドレス情報とを生成し、前記アドレス制御部は、前記分岐命令の分岐先アドレスが、前記第１の上位アドレス情報で識別される前記第１のアドレス範囲に分岐する分岐命令である場合に、前記復元部を通じて前記第１のアドレス範囲に対応する上位ビット部分を生成し、前記分岐命令が前記第２の上位アドレス情報で識別されるアドレス範囲に分岐する分岐命令である場合に前記分岐命令の種類に応じて上位ビット部分を復元するようにしてもよい。【００１９】
本発明によれば、上位ビット部分が複数のアドレス範囲ごとに区分されている。そして、分岐先アドレスが第１の上位アドレス情報で識別される前記第１のアドレス範囲である場合には、その第１のアドレス範囲に対応する上位ビット部分が生成される。一方、分岐先アドレスが前記第２の上位アドレス情報で識別されるアドレス範囲である場合には、分岐命令の種類に応じて上位ビット部分が復元される。このため、例えば、特定のアドレス範囲への分岐命令が頻発する場合には、そのアドレス範囲を第１の上位アドレス情報で識別するように構成することで、効果的に、そのアドレス範囲に対応する上位ビット部分を生成することができる。【００２０】
前記アドレス制御部は、前記分岐命令が前記第２の上位アドレス情報で識別されるアドレス範囲に分岐する分岐命令である場合に、分岐命令の種類を識別する信号を前記実行部から受信する分岐種別情報受信部と、前記分岐命令が前記下位ビット部分の範囲を限界として分岐元アドレスから相対分岐する相対分岐命令である場合に、前記実行部における前記分岐命令の処理において前記下位ビット部分の範囲から正方向または負方向に桁あふれが発生したことを示す桁あふれ情報を受信する桁あふれ情報受信部と、前記桁あふれが発生した場合に、分岐元アドレスの上位ビット部分への加減算によって分岐先アドレスの上位ビット部分を取得する算術部とを有するものでもよい。【００２１】
本発明によれば、分岐命令が前記第２の上位アドレス情報で識別されるアドレス範囲に分岐する分岐命令である場合で、かつ、分岐命令が前記下位ビット部分の範囲を限界として分岐元アドレスから相対分岐する相対分岐命令である場合に、分岐元アドレスの上位ビット部分への加減算によって分岐先アドレスの上位ビット部分を取得することができる。すなわち、下位ビット部分の範囲から正方向または負方向への桁あふれを検知し、その桁あふれ分を上位ビット部分に加減算すればよい。【００２２】
前記アドレス制御部は、分岐種別情報受信部が前記相対分岐命令でない場合に、分岐命令の分岐先を算出した演算部から分岐先アドレスの上位ビット部分を取得する上位ビット取得部を有するものでもよい。【００２３】
本発明によれば、分岐命令が前記第２の上位アドレス情報で識別されるアドレス範囲に分岐する分岐命令である場合で、分岐命令が上記の相対分岐命令でない場合には、もはやあふれ分を上位ビット部分への加減算によっては上位ビット部分を取得できない。この場合には、分岐先を算出した演算部から分岐先アドレスの上位ビット部分を取得することができる。
【発明の効果】
【００２４】
アドレス空間が拡張された場合に、その拡張されたアドレス空間で使用される上位ビットに偏りがある場合には、効率的に分岐予測を実現できる。
【図面の簡単な説明】
【００２５】
【図１】６４ビットのアドレス空間に割り付けられるプロセスのイメージを示す図である。
【図２】上位３２ビット定義コードの定義を示す図である。
【図３】本発明の実施形態に係る処理装置のシステム構成図である。
【図４】分岐履歴記憶装置のセットを構成する各ウェイの構成を説明するための図である。
【図５】処理装置の詳細構成を示す図である。
【図６】上位ビットデコーダの回路構成を示す図である。
【図７】上位ビットエンコーダの構成を示す図である。
【図８】上位ビットエンコーダの処理シーケンスを示す図である。
【図９】上位ビットデコーダの処理シーケンスを示す図である。
【図１０】分岐先復元処理を示す図である。
【図１１】ＰＣ相対分岐命令の分岐先復元処理を示す図である。
【符号の説明】
【００２６】
１００    分岐予測装置
１２２Ａ  プログラムカウンタ制御装置
１２３    命令フェッチ制御ユニット
１２６    分岐リザベーションステーション
１３０    分岐履歴記憶装置
１５０Ａ、１５０Ｂ  上位ビットデコーダ
１５３Ａ、１５Ｂ  上位ビットエンコーダ
１６７    演算器
１６８    相対アドレス演算器
【発明を実施するための最良の形態】
【００２７】
以下、図面を参照して本発明を実施するための最良の形態（以下、実施形態という）に係る処理装置について説明する。以下の実施形態の構成は例示であり、本発明は実施形態の構成に限定されない。【００２８】
《発明の骨子》
６４ビットアドレス空間は、データ空間の６４ビット拡張の都合に合わせて行われたものであるため、現状では空間内で実際に命令列が配置されるアドレスには偏りがある。そこで、これらの偏りを利用して、上位３２ビットを擬似的に少数のビットで表現する。つまり、頻出の上位アドレスを見込んでおき、少数ビットを用いたコードで頻出する上位アドレスを表現する。【００２９】
その少数ビットを下位３２ビットに加えてアドレスとして取り扱い、分岐予測などを行うようにすれば、従来の装置に少しの拡張を加えるだけで、プログラムの６４ビットアドレス空間への割り付け（以下、このようなＯＳによるプロセスのアドレス空間への割り付けを６４ビットアドレスモードという）に対応することができるようになる。すなわち、例えば、ＯＳが６４ビットのアドレス空間を利用する制御を行ったとしても、参照されるアドレスの偏りを利用し、効率的な分岐予測ができる。【００３０】
頻出の上位アドレスは、ＯＳの仕様から予測して固定的に決定してもよいし、またアドレスの頻度カウンタなどを設けて動的に設定することも考えられる。【００３１】
近年のＯＳでは、図１のような６４ビットアドレス空間が定義されている（例えば、参考文献「solarisインターナルカーネル構造のすべて」（ピアソン・エデュケーション）p．138参照）。【００３２】
図１は、６４ビットのアドレス空間に割り付けられるプロセスのイメージを示す図である。図１で、斜線部分は、いずれのプロセスも使用できないアドレスの領域を示している。図１のように、一般的なＯＳの制御では、アドレス空間（仮想ドレレス空間）は、カーネルとユーザプロセスとで、別々に用意されている。【００３３】
例えば、ＯＳのアドレス空間は、カーネルモードのアドレス空間で、０００００００：０００００００１から０００００００：ＦＦＦＦＦＦＦＦの範囲である（ここで、０、１、Ｆ等は１６進数である。以下同様である。ここで、３２ビットごとに：（コロン）で区切って示している）。また、００００００１：００００００００以降の領域は、ヒープ領域およびキャッシュ領域である。【００３４】
また、ユーザの空間のうち、実行形式が格納されるテキストの空間は、０００００００１：０００００００から開始する。また、ＦＦＦＦＦＦＦＦ：７ＦＦＦＣ０００からＦＦＦＦＦＦＦＦ：７Ｆ７Ｆ０００までは、スタックの領域が設けられる。さらに、ＦＦＦＦＦＦＦＦ：７Ｆ７Ｆ０００から、アドレスが小さくなる方向にラリブラリが格納される。【００３５】
この図から以下のことが理解される。
（１）ＯＳカーネルの領域は、上位３２ビットが０ｘ００００００００である。
（２）テキスト（実行形式のプログラム）の領域は、上位３２ビットが０ｘ０００００００１である。
（３）ライブラリが上位３２ビットが０ｘＦＦＦＦＦＦＦＦから始まり、順番に下がっていく。【００３６】
一般的なアプリケーションで使用されるライブラリの数はせいぜい１０程度までであり、かつライブラリ単体のサイズは小さいのであるプログラムで使用されるライブラリをすべて合わせても普通は上位３２ビットの変化しない範囲で収まる。【００３７】
よって、頻出する上位３２ビットのアドレスは、以下の３種類であると考えられる。【００３８】
０ｘ００００００００（１６進数で、０が８個）
０ｘ０００００００１（１６進数で、０が７個と１が１個）
０ｘＦＦＦＦＦＦＦＦ（１６進数で、Ｆが８個）
そこで、上位の３２ビットアドレスに代えて、これら３種類の上位アドレスと「それ以外の上位アドレス」とをそれぞれ識別するコードを導入する。分岐予測装置には、これまでの下位３２ビットアドレスとともに該コードを登録する。予測された分岐先アドレスの命令フェッチ時には該コードから元の上位３２ビットアドレスを生成し、使用する。該コードが頻出する３種類ではなく「それ以外の上位アドレス」であった場合は、上位ビットは不明だから上位ビットを正しく計算するところからやり直せばよい。こうすることでこれまでは「４Ｇ越え＝投機フェッチ失敗」であったのが、少なくとも上記３種類の上位アドレスについては、従来の３２ビット範囲内と同じように投機フェッチ成功の可能性が出てくる。【００３９】
ほとんどの命令が上記３種類のアドレスに含まれること、かつ、それら３つの領域の行き来はそれなりに多くそれ以外に行くことがほとんどないことを考えれば、６４ビットアドレスモードにおいて、性能は飛躍的に向上することが見込まれる。また、従来の３２ビットアプリケーションで性能が損なわれることもない。【００４０】
図２に、コード（以下、上位３２ビット定義コードという）の定義を示す。図２のように、上位３２ビットアドレスが”０ｘ００００００００”の場合、上位３２ビット定義コードを００（ｂ）（ビットデータであることを（ｂ）で示す。以下、同様）とする。また、上位３２ビットアドレスが”０ｘ０００００００１”の場合、上位３２ビット定義コードを０１（ｂ）とする。また、上位３２ビットアドレスが”０ｘＦＦＦＦＦＦＦＦ”の場合、上位３２ビット定義コードを１１（ｂ）とする。さらに、上位３２ビットアドレスが”上記以外の場合に、上位３２ビット定義コードを１０（ｂ）とする。【００４１】
このようにして、本処理装置は、分岐予測処理を下位３２ビットアドレス＋２ビットの上位３２ビット定義コードで処理する。本処理装置では、３２ビットを越える分岐命令が発生しなければ、合計３４ビットの擬似的なアドレスで分岐予測を実行する。【００４２】
さらに、上記上位３２ビット定義コードが００（ｂ）、０１（ｂ）または１１（ｂ）の場合には、上位３２ビットがそれぞれ０ｘ００００００００、０ｘ０００００００１および０ｘＦＦＦＦＦＦＦＦに固定されたものとなる。したがって、この場合の分岐予測は、従来の３２ビットの範囲での分岐予測の手法がそのまま適用され、いわば３４ビットアドレスでの分岐予測が実施される。【００４３】
一方、上位３２ビット定義コードが１０（ｂ）の場合には、分岐先が３２ビットアドレスの範囲を越え、かつ、上位３２ビットが上記３種類のいずれでもないものであることを意味する。その場合には、上位３２ビットアドレスは、不明になる。そこで、分岐予測による上位３２ビット定義コードが１０となったときに現在のＰＣの上位３２ビットをそのまま使うと仮定した動作、つまり３２ビット予測そのものをする。【００４４】
このようにして、本処理装置は、上記３つの領域それぞれの範囲内（上位３２ビットアドレスが上位３２ビット定義コード００（ｂ）、０１（ｂ）、１１（ｂ）によって規定されるアドレスの範囲）、および、上記３つの領域相互間の分岐については、従来の３２ビットでの分岐予測手段を３４ビットアドレス（上位３２ビット定義コード＋下位３２ビットアドレス）に変換して適用することができる。【００４５】
一方、上記３つの領域を越える領域、すなわち、上位３２ビット定義コード１０（ｂ）で規定される上位３２ビットの範囲への分岐が発生した場合には、従来の技術を適用して上位３２ビットを正確に求め直す必要が発生する。【００４６】
しかしながら、プログラム領域（ＯＳ域、テキスト領域、およびライブラリ領域のそれぞれ）が３２ビットアドレスの範囲（４ＧＢ）を越えて使用されることはまれであるので、大半の処理において、３４ビットの範囲で分岐予測を実行できる。【００４７】
図３は、本処理装置のシステム構成図である。本処理装置は、例えば、主記憶装置１２１に格納された命令を読み出して実行する、いわゆるプログラム内蔵方式のコンピュータである。【００４８】
図３のように、この処理装置は、命令を実行する演算ユニット１２０と、演算ユニット１２０で実行される命令および演算ユニット１２０が処理するデータ等を格納する主記憶装置１２１と、演算ユニット１２０が実行すべき命令の主記憶装置１２１上のアドレスを指定するプログラムカウンタ１２２とを有している。このようなプログラムカウンタ１２２の制御に基づく処理装置の制御は周知である。【００４９】
図３では、さらに具体的に、プログラムカウンタ１２２の生成するアドレスに基づいて命令のフェッチを制御する命令フェッチ制御ユニット１２３と、命令キャッシュ１０２を管理し命令フェッチ制御ユニット１２３からの命令フェッチ要求にしたがって命令をフェッチする命令キャッシュ制御ユニット１２４と、命令キャッシュ１０２からフェッチされた命令を保持する命令バッファ１２５と、命令バッファ１２５の命令をデコードするデコーダ１０３と、デコードされた命令の実行タイミングを制御するリザベーションステーション（分岐命令の実行を制御する分岐リザベーションステーション１２６およびレジスタ演算命令、アドレス演算命令の実行を制御するその他リザベーションステーション１２７）と、命令の実行完了を監視する命令完了管理ユニット１２８と、演算ユニット１２０で実行される命令のオペランドを高速に演算ユニット１２０に供給するオペランドキャッシュ１２９と、主記憶装置１２１とオペランドキャッシュ１２９との間でデータの授受を管理するデータキャッシュ制御ユニット１３１とを有している。【００５０】
このうち、分岐予測装置１００は、分岐命令の分岐履歴を記憶する分岐履歴記憶装置１３０を有している（図５参照）。分岐履歴記憶装置１３０は、４ウェイセットアソアシアティブ方式の記憶装置である。【００５１】
図４は、分岐履歴記憶装置１３０のセットを構成する各ウェイの構成を説明するための図である。分岐履歴記憶装置１３０は、ＳＲＡＭ等の比較的高速にアクセス可能な記憶装置である。４ウェイの分岐履歴記憶装置１３０は、１つのセット内に４つのウェイに対応するエントリを有する。図４に示すように、各エントリは、タグ部ＴＧとデータ部ＤＴを含む。タグ部ＴＧは、命令アドレス（の一部）ＴＧ１、バリッドフラグＶ、リプレースフラグＲ、および、その他のフラグＴＧ２からなる。データ部ＤＴは、所定データとしての分岐先アドレスＤＴ１からなる。【００５２】
１つのセットは、アドレス生成ユニット１０１から出力される命令アドレスの一部（例えば＜１５：５＞）によって決定される。本実施形態では４ウェイなので、セットの決定により４つのエントリが指定されることになる。さらに、その４つのエントリのうち、命令アドレスの他の一部によって１つのエントリが決定される。【００５３】
本処理装置では、この１つのエントリを決定するために、命令アドレスＴＧ１には、上位３２ビット定義コード＜１：０＞と命令アドレスの一部（例えば＜３１：１６＞）が格納されている。例えば、登録時に、命令アドレスの一部＜１５：５＞を使ってセットが決定され、残りの部分がセット内のいずれかのエントリ（４つのウェイに対応する４つのエントリのいずれか）のタグ部（命令アドレスＴＧ１を含む）にデータとして格納されるようになっている。なお、命令アドレス＜３１：１６＞との記載は、命令アドレスＴＧ１が命令アドレス（例えば３２ビット）の一部３１ビット目から１６ビット目であることを意味する。【００５４】
したがって、本処理装置では、１つのセット内の４つのエントリを検索するときに使用するタグとして、上位３２ビット定義コード（００（ｂ）、０１（ｂ）、１１（ｂ），および１０（ｂ）のいずれか１つ）と下位３２ビットアドレスの一部＜３１：１６＞が使用される。【００５５】
バリッドフラグは、エントリの有効又は無効を示すフラグである。例えば、バリッドフラグが”１”であればそのバリッドフラグを含むエントリが有効であること、バリッドフラグが”０”であればそのバリッドフラグを含むエントリが無効であることを示す。エントリが有効とは、ウェイに登録されたデータである分岐先アドレスが抹消されていないという意味である。バリッドフラグは、置換対象のウェイを選択するためにも用いられる。【００５６】
リプレースフラグは、置換対象のウェイを選択するために用いられるフラグである。分岐先アドレスには、キャッシュメモリ１０２（または主記憶装置）からフェッチされた分岐命令の分岐先アドレスが格納される。本実施形態では、リプレースフラグおよびバリッドフラグの処理については、詳細を省略する。【００５７】
以下、本処理装置の制御手順を説明する。まず、プログラムカウンタ１２２からの命令アドレス（命令が格納された主記憶装置１２１上のアドレス）が命令フェッチ制御ユニット１２３に送出される。【００５８】
命令フェッチユニット１２３は、命令キャッシュ制御ユニット１２４にその命令アドレスの命令取得を指示するとともに、分岐予測装置１００に対して、分岐予測を指示する。すると命令キャッシュ１０２での命令取得処理と並行して、分岐予測装置１００での分岐履歴記憶装置１３０の検索がなされる。【００５９】
そして、分岐予測装置１００は、現在の命令アドレスで分岐命令がヒットした場合には、その分岐先アドレスを命令フェッチ制御ユニット１２３に送出する。【００６０】
命令フェッチ制御ユニット１２３は、分岐予測装置１００でヒットした分岐命令の分岐先アドレスによって、さらに、次の命令取得を命令キャッシュ制御ユニット１２４に指示する（このような処理は、通常、パイプラインのステージを形成する）。なお、分岐予測がヒットしなかった場合には、分岐しない次の命令アドレスを命令フェッチ制御ユニット１２３の内部に含まれるアドレス加算器１８４で生成し、次の命令取得を命令キャッシュ制御ユニット１２４に指示する。【００６１】
フェッチされ、デコードされた命令は、それが分岐命令でなかった場合には、その他リザベーションステーション１２７によってオペランドの処理等に基づいて、実行の待ち合わせを受ける。そして、オペランドが揃った時点で、各命令が演算ユニット１２０で実行される。【００６２】
一方、分岐命令については、分岐リザベーションステーション１２６によって命令の待ち合わせがなされる。そして、分岐命令の分岐実行によって分岐先アドレスが確定したときに、完了報告が分岐リザベーションステーション１２６から、命令完了管理ユニット１２８および分岐予測装置１００に送出される。【００６３】
このとき、分岐リザベーションステーション１２６は分岐予測が正しかったか否かを判定する。すなわち、（ａ１）その命令アドレスにて分岐予測装置１００によって分岐予測がヒットし（分岐履歴記憶装置１３０に分岐先アドレスが格納されていた）、（ａ２）フェッチされた分岐命令がその分岐先アドレスに分岐した場合に、分岐予測が正しかったことが分かる。あるいは、（b１）その命令アドレスにて分岐予測装置１００がヒットせず、（b２）フェッチされた命令が分岐命令ではなかったかもしくは分岐命令であっても分岐しなかった場合に、分岐予測が正しかったことがわかる。【００６４】
この場合、すでにキャッシュ制御ユニット１２４に依頼済みの命令フェッチは、そのまま続行されることになる。【００６５】
また、分岐予測が正しくなかった場合には、すでに、キャッシュ制御ユニット１２４に依頼済みの命令フェッチおよびその後に続く一連の処理はは、処理が中断されることになる。同時に分岐リザベーションステーション１２６からは、正しい分岐先からの再命令フェッチを行うよう、命令フェッチ制御ユニット１２３に指示が出される。【００６６】
分岐予測装置１００は、セレクタ１３２を介して実行された分岐命令をウェイに格納する。【００６７】
なお、分岐命令は、命令の実行によって分岐先に分岐する場合と、分岐せずに次のアドレスにプログラムカウンタが移動する場合がある。そこで、本実施形態では、命令を実行することを“命令を処理する”と呼ぶ。すなわち、命令を処理するとは、命令にしたがった所定の処理を実行することをいい、例えば、条件付き分岐命令の場合には、条件の判定と判定結果に基づく分岐先への分岐または分岐しない処理を含む。
《実施例》
図５から図１１に図面に基づいて本発明の一実施例に係る処理装置を説明する。図５は、実施例に係る処理装置の詳細構成を示す図である。図５では、本処理装置のうち、特に、プログラムカウンタ制御装置１２２Ａ（本発明のアドレス制御部に相当）、命令フェッチ制御ユニット１２３（本発明の取得部に相当）、分岐リザベーションステーション１２６、分岐予測装置１００（本発明の分岐予測部に相当）、および演算器（相対アドレス演算器１６８、演算器１６７、本発明の実行部に相当）が明示されている。以下、本処理装置の各部の構成要素を説明する。【００６８】
（プログラムカウンタ制御装置１２２Ａ）
プログラムカウンタ制御装置１２２Ａは、プログラムカウンタの現在値ＰＣ１５２（または分岐命令の実行結果）に基づいてプログラムカウンタの次の値ＮＰＣ１５１の算出を制御する。【００６９】
図５では、プログラムカウンタの現在値ＰＣ１５２は、上位３２ビットＰＣ＜６３：３２＞と、下位３２ビットＰＣ＜３１：０＞とに分けて示されている。ただし、ＰＣ１５２というときは、プログラムカウンタの現在値そのもの（全部のビット）をいうこととする。【００７０】
同様に、プログラムカウンタの次の値ＮＰＣ１５１は、上位３２ビットＮＰＣ＜６３：３２＞と、下位３２ビットＮＰＣ＜３１：０＞とに分けて示されている。ただし、ＮＰＣ１５２というときは、プログラムカウンタの次の値そのもの（全部のビット）をいうこととする。【００７１】
図５のように、分岐命令が処理され、分岐先アドレスが確定した場合、分岐リザベーションステーション１２６からプログラムカウンタ制御装置１２２Ａへ、上位３２ビット定義コード、分岐先アドレスの桁あふれ情報、および下位３２ビットアドレスが送出される。ここで、分岐先アドレスの桁あふれ情報（以下、単に桁あふれ情報という）とは、ＰＣ相対分岐命令が分岐した場合に、分岐先までの相対アドレスが下位３２ビットの範囲を超えるか否かを示す情報である。【００７２】
以下、この桁あふれ情報について説明する。本処理装置では、分岐命令は、ＰＣ相対アドレス分岐命令と、レジスタ間接分岐命令とに分類することができる。【００７３】
ＰＣ相対アドレス分岐命令とは、現在のプログラムカウンタの値に対する相対分岐アドレスをオペランドとする分岐命令である。ＰＣ相対アドレス分岐命令の分岐先は、現在のプログラムカウンタの値に相対分岐アドレスが加算されたアドレスとなる。本実施形態の場合、オペランドである相対分岐アドレスは、最大３２ビットで記述できる範囲である。このため、ＰＣ相対アドレス分岐命令が分岐したときの分岐先の上位３２ビットは、最大で＋１（正方向に桁あふれした状態）、最小で−１（負方向に桁あふれした状態）となる。【００７４】
本実施形態では、分岐リザベーションステーション１２６は、正方向に桁あふれした状態を示すビット（＋１ビット）、負方向に桁あふれした状態を示すビット（−１ビット）をプログラムカウンタ制御装置１２２Ａに通知する。この信号を受信するプログラムカウンタ制御装置１２２Ａが本発明の桁あふれ情報受信部に相当する。【００７５】
さらに、ＰＣ相対分岐命令が実行された場合には、その実行を示す信号が相対アドレス演算器１６８からプログラムカウンタ制御装置１２２Ａに通知される（ライン１９１）。この信号を受信するプログラムカウンタ制御装置１２２Ａが本発明の分岐種別情報受信部に相当する。【００７６】
一方、レジスタ間接分岐命令とは、レジスタの番号をオペランドとして指定し、指定したレジスタに格納されたアドレスを分岐先アドレスとする分岐命令である。レジスタ間接分岐命令は、レジスタのビット幅、すなわち、６４ビットの範囲で分岐先アドレスを指定できる。【００７７】
図５のように、プログラムカウンタ制御装置１２２Ａは、上位ビットデコーダ１５０Ａを有している。上位ビットデコーダ１５０Ａは、上位３２ビット定義コードを本来の上位３２ビットアドレスに戻す機能を有する（上位ビットデコーダ１５０Ｂも同様である）。【００７８】
上位ビット定義コードは、分岐リザベーションステーション１２６から入力される。これは、分岐リザベーションステーション１２６において、最終的に次の分岐先が確定するためである。すなわち、分岐リザベーションステーション１２６に示されているバッファＴＧＴ−ＰＣ１７１には、命令がデコードされ、分岐が確定した分岐先アドレスの上位３２ビット定義コードと、下位３２ビットアドレスが格納されている。上位ビットデコーダ１５０Ａには、この確定した分岐先アドレスの上位３２ビット定義コードが入力される。【００７９】
本実施形態のデコーダ１５０Ａは、常時、この上位２ビット定義コードを上位３２ビットアドレスに変換している。さらに、プログラムカウンタの次の値ＮＰＣ１５１には、命令完了管理ユニット１２８（図３参照）から分岐命令の実行完了が確認されたとの通知を受け取ったとき、確定した分岐先アドレスの上位３２ビットが設定される。【００８０】
したがって、分岐命令が発生しても、分岐先アドレスの上位３２ビット定義コードが００（ｂ），０１（ｂ）、または１１（ｂ）の場合には、プログラムカウンタ制御装置１２２Ａは、そのまま上位ビットデコーダ１５０Ａによって上位３２ビット定義コードから上位３２ビットアドレスを生成する。上位３２ビットが上位３２ビット定義コードから一意に確定可能だからである。。【００８１】
また、下位３２ビットアドレスについては、プログラムカウンタ制御装置１２２Ａは、分岐リザベーションステーション１２６から確定した分岐先アドレスの下位３２ビットＴＧＴ＿ＰＣ＜３１：０＞を受け取り、プログラムカウンタの次の値の下位３２ビットＮＰＣ＜３１：０＞に設定する。このようにして、分岐命令が発生しても、分岐先アドレス上位３２ビットが上位３２ビット定義コードで一意に確定可能な場合、プログラムカウンタは、上位３２ビット定義コードからアドレスを復元することで、正しい分岐先アドレスを設定されることになる。【００８２】
一方、上位３２ビット定義コードが１０（ｂ）（その他）の場合には、プログラムカウンタ制御装置１２２Ａは、分岐命令による分岐先が上位３２ビット定義コードで一意に定義されたアドレスの範囲を超えたと仮に判定する（この判定を実行するプログラムカウンタ制御装置１２２Ａが本発明の判定部に相当する）。この場合分岐先アドレスは上位３２ビット定義コードで復元不可能である。本実施形態では、分岐命令の種類に応じて、分岐先アドレスを復元する方法を選択する。【００８３】
以下で、上位３２ビット定義コードから分岐先アドレス上位３２ビットが生成不可能な場合の分岐先アドレス生成方法を記述する。【００８４】
まず、分岐命令がＰＣ相対分岐命令であった場合には、ライン１９１を通じて相対分岐演算器１６８からその旨の信号（例えばＨＩ信号）がプログラムカウンタ制御装置１２２Ａに通知される。その場合、プログラムカウンタ制御装置１２２Ａは、分岐リザベーションステーション１２６から、桁あふれ情報を読み取る。そして、桁あふれ情報を元にプログラムカウンタの現在値ＰＣ１５２の上位３２ビットに変更を加え、分岐先アドレスの上位３２ビットを生成する。【００８５】
図１１にＰＣ相対分岐命令の分岐先復元処理の流れを示す。【００８６】
桁あふれ情報が＋１であった場合には（Ｓ１９２）、プログラムカウンタ制御装置１２２Ａは、プログラムカウンタの現在値の上位３２ビットＰＣ＜６３：３２＞を加減算器１５４を通して１加算した値を分岐先アドレスの上位３２ビットとする（Ｓ１９３）。また、桁あふれ情報が−１であった場合には（Ｓ１９４）、プログラムカウンタ制御装置１２２Ａは、プログラムカウンタの現在値の上位３２ビットＰＣ＜６３：３２＞を加減算器を通して１減算した値を分岐先アドレスの上位３２ビットとする（Ｓ１９５）。また、桁あふれ情報が＋１および−１のいずれでもない場合には、プログラムカウンタ制御装置１２２Ａは、プログラムカウンタの現在値の上位３２ビットＰＣ＜６３：３２＞をそのまま分岐先アドレスの上位３２ビットとする（Ｓ１９６）。この処理を実行する加減算器１５５が本発明の算術部に相当する。【００８７】
一方、分岐先アドレスの下位３２ビットには、分岐リザベーションステーション１２６から送出された値ＴＧＴ＿ＰＣ＜３１：０＞をそのまま設定する。【００８８】
次に、分岐命令がレジスタ間接分岐命令であった場合には、ライン１９１を通じて相対分岐演算器１６８からその旨の信号（例えばＬＯ信号）がプログラムカウンタ制御装置１２２Ａに通知される。その場合には、プログラムカウンタ制御装置１２２Ａは、プログラムカウンタの現在値ＰＣ上位３２ビット＜６３：３２＞からは、分岐先アドレス上位３２ビットを特定できない。【００８９】
この場合には、プログラムカウンタ制御装置１２２Ａには、演算器１６７から、レジスタ間接分岐命令の分岐先アドレスが入力される。ここで、演算器１６７は、レジスタ間接分岐命令の分岐先アドレスを計算する演算器である。そして、プログラムカウンタ制御装置１２２Ａは、レジスタ間接分岐命令の分岐先アドレスを計算した演算器１６７の出力から、そのまま上位３２ビットアドレスを読み取り、分岐先アドレス上位３２ビットとする。【００９０】
一方、分岐先アドレス下位３２ビットには、分岐リザベーションステーション１２６から送出された値ＴＧＴ＿ＰＣ＜３１：０＞をそのまま設定する。【００９１】
プログラムカウンタ制御装置１２２Ａは、上記方法により設定した分岐アドレスから選択回路１５５により１つを選択し、選択した分岐先アドレスをプログラムカウンタの次の値ＮＰＣ１５１に設定する。【００９２】
図１０に分岐先アドレス復元処理の流れを示す。上位３２ビット定義コードが００（ｂ）、０１（ｂ）、または１１（ｂ）の場合（Ｓ２０）、上位３２ビットは分岐リザベーションステーション１２６から入力された上位３２ビット定義コードを上位ビットデコーダ１５０Ａによって復元された値をプログラムカウンタの次の値ＮＰＣ１５１の上位３２ビットに設定する（Ｓ１８）。上位３２ビット定義コードが１０（ｂ）かつ、分岐命令がＰＣ相対分岐命令である旨の信号が通知された場合（Ｓ２１）、上位３２ビットはプログラムカウンタの現在値ＰＣの上位３２ビットを加減算器１５４を通して加減算した値をプログラムカウンタの次の値ＮＰＣ１５１の上位３２ビットに設定する（Ｓ１９）。上位３２ビット定義コードが１０（ｂ）かつ、分岐命令がレジスタ間接分岐命令である旨の信号が通知された場合、レジスタ間接分岐命令の分岐先アドレスを計算した演算器１６７から入力された値をプログラムカウンタの次の値ＮＰＣ１５１の上位３２ビットに設定する（Ｓ２２）。【００９３】
プログラムカウンタの次の値ＮＰＣ１５１の下位３２ビットは分岐命令が実行される場合常に、分岐リザベーションステーション１２６から入力されたＴＧＴ＿ＰＣ＜３１：０＞が設定される。【００９４】
なお、分岐命令が実行されない場合には、プログラムカウンタ制御装置１２２Ａは、プログラムカウンタの次の値ＮＰＣ１５１＜６３：０＞を、同時に完了した命令数分(各命令長の合計)だけ進める。例えば、４命令同時完了でかつ一命令の長さが各々すべて４バイトであれば、４バイト×４命令＝１６バイトである。【００９５】
（命令フェッチ制御ユニット）
命令フェッチ制御ユニット１２３は、アドレスの上位３２ビットを上位３２ビット定義コードに変換する上位ビットエンコーダ１５３Ａ（本発明の符号化部に相当）と、上位ビットエンコーダ１５３Ａの出力と分岐リザベーションステーション１２６からの上位３２ビット定義コードとを選択する選択回路１６１と、選択回路１６１からの信号を保持するバッファＩＡＲＸ１６２と、フェッチ中の命令アドレスが入力されるアドレス加算器１８４と、アドレス加算器１８４の出力を保持するバッファＳＥＱ１６３と、分岐予測装置１００において予測された次の分岐先アドレスを格納するバッファＴＩＡＲ１６４と、バッファＩＡＲＸ１６２、バッファＳＥＱ１６３およびバッファＴＩＡＲ１６４等に保持された複数の命令アドレスデータ（上位３２ビット定義コードおよび下位３２ビットアドレス）のいずれかを選択する選択回路１６５と、選択回路１６５によって選択された命令アドレスデータを保持する命令フェッチアドレス保持回路１６６と、命令フェッチのために上位３２ビット定義コードから上位３２ビットアドレスを生成する上位ビットデコーダ１５０Ｂと、を有している。【００９６】
図５のように、プログラムカウンタの現在値ＰＣ１５２の上位３２ビットＰＣ＜６３：３２＞が上位ビットエンコーダ１５３Ａにて、上位３２ビット定義コードにエンコードされる。エンコードされた上位３２ビット定義コードは、選択回路１６１によって選択され、バッファＩＡＲＸ１６２に設定される。バッファＩＡＲＸ１６２は、プログラムカウンタからのフェッチ要求によって命令フェッチを実行する場合に使用するバッファである。【００９７】
プログラムカウンタからのフェッチ要求があった場合には、選択回路１６５は、バッファＩＡＲＸ１６２から出力される命令アドレスデータ（上位３２ビット定義コードおよび下位３２ビットアドレス）を選択し、その上位３２ビット定義コードを上位ビットデコーダ１５０Ｂ、および分岐予測装置１００に送出する。また、その場合に、選択回路１６５は、バッファＩＡＲＸ１６２から出力される下位３２ビットアドレスを命令フェッチアドレス保持回路１６６、および分岐予測装置１００に送出する。【００９８】
上位ビットデコーダ１５０Ｂは、上位３２ビット定義コードを上位３２ビットアドレスに変換する。この上位３２ビットアドレスは、分岐予測装置１００内を通過した下位３２ビットアドレス（分岐予測装置１００内に、ＩＦ−ＥＡＧ＜３１：０＞で明示された線）に付加され、６４ビットの命令アドレスＩＦ−ＥＡＧ＜６３：０＞として命令フェッチに使用される（矢印１９０）。【００９９】
また、この命令アドレスの下位３２ビットＩＦ−ＥＡＧ＜３１：０＞は、アドレス加算器１８４に入力され、アドレスが１単位インクリメントされてバッファＳＥＱ１６３に格納される。ここで１単位とは、１回のフェッチにおいてメモリ（主記憶装置１２１または命令キャッシュ１０２）から取得される命令数分だけ主記憶装置１２１上のアドレスを進める数である。例えば、３２バイト８命令を１フェッチステージでフェッチする場合には、１単位は３２バイトである。また、現在の上位３２ビット定義コードは、そのままバッファＳＥＱ１６３の上位３２ビット定義コードとして設定される。【０１００】
したがって、分岐命令が実行されなかったことを条件に、選択回路１６５は、バッファＳＥＱ１６３から出力される命令アドレスデータ（上位３２ビット定義コードおよび下位３２ビットアドレス）を選択する。選択されたバッファＳＥＱ１６３からの命令アドレスデータは、上記バッファＩＡＲＸ１６２からの命令アドレスデータと同様に処理される。【０１０１】
また、分岐予測装置において、現在フェッチ中の命令アドレスにおいて分岐命令がヒットし、その分岐先アドレスへの分岐が予測される場合に、分岐予測装置１００から分岐先の命令アドレスデータ（上位３２ビット定義コードおよび下位３２ビットアドレス）が、バッファＴＩＡＲ１６４に送出される。【０１０２】
この場合、分岐予測装置１００が分岐予測を送出したことを条件に、選択回路１６５は、バッファＴＩＡＲ１６４から出力される命令アドレスデータを選択する。バッファＴＩＡＲ１６４からの命令アドレスデータは、上記バッファＩＡＲＸ１６２からの命令アドレスデータと同様に処理される。【０１０３】
（演算器）
演算器１６７は、命令フェッチ制御ユニット１２３の制御によってフェッチされた命令がレジスタ間接分岐命令であった場合に、その分岐先アドレスを計算する。計算された分岐先アドレスは、分岐リザベーションステーション１２６に送出される。このうち、上位３２ビットアドレスは、上位ビットエンコーダ１５３Ｂによって上位３２ビット定義コードに変換される。なお、演算器１６７によって計算された分岐先アドレスの上位３２ビットは、選択回路１６９を介してプログラムカウンタ制御装置１２２Ａに送出される。【０１０４】
相対アドレス演算器１６８は、命令フェッチ制御ユニット１２３の制御によってフェッチされた命令が相対アドレス分岐命令であった場合に、分岐命令の命令アドレスに相当するアドレスを保持する命令フェッチアドレス保持回路１６６の下位３２ビットＰＣ＜３１：０＞を基準にして相対アドレス分だけ変位したアドレスを計算する。計算された分岐先アドレスは、選択回路１６９を通じて分岐リザベーションステーション１２６に送出される。【０１０５】
また、相対アドレス演算器１６８は、プログラムカウンタ値（現在の命令フェッチアドレス）から上記相対アドレスだけ変位したアドレスを計算するときの桁あふれの発生（正方向の桁あふれ：＋１、負方向の桁あふれ：−１）を検知する。検知された桁あふれは、桁あふれ情報（＋１、−１）として、分岐リザベーションステーション１２６を通じて、プログラムカウンタ制御装置１２２Ａに通知される。【０１０６】
さらに、相対アドレス演算器１６８には、命令フェッチアドレス保持回路１６６から現在の上位３２ビット定義コードが入力されている。上記桁あふれが検知されない場合には、命令フェッチアドレス保持回路１６６から入力された上位３２ビット定義コードがそのままバッファ１７１に設定される。また、上記桁あふれが検知された場合には、命令フェッチアドレス保持回路１６６から入力された上位３２ビット定義コードから分岐先アドレスの上位３２ビット定義コードを算出する。正方向の桁あふれが発生した場合は、上位３２ビット定義コードは正の方向に移行し、００（ｂ）−＞０１（ｂ）、０１（ｂ）−＞１０（ｂ）、１０（ｂ）−＞１０（ｂ）、１１（ｂ）−＞００（ｂ）となる。このとき、０１（ｂ）、１０（ｂ）は共に１０（ｂ）へと移行する。負方向の桁あふれが発生した場合は、上位３２ビット定義コードは負の方向に移行し、００（ｂ）−＞１１（ｂ）、０１（ｂ）−＞００（ｂ）、１０（ｂ）−＞１０（ｂ）、１１（ｂ）−＞１０（ｂ）へと移行する。このとき、１１（ｂ）、１０（ｂ）は共に１０（ｂ）へと移行する。【０１０７】
選択回路１６９は、分岐命令が相対アドレス分岐命令か、レジスタ間接分岐命令かに応じて、相対アドレス演算器１６８または演算器１６７のいずれのアドレス計算の結果を選択する。【０１０８】
（分岐リザベーションステーション）
分岐リザベーションステーション１２６は、選択回路１６９、バッファ１７０および、バッファ１７１を有する。分岐リザベーションステーション１２６は、相対アドレス演算器１６８または演算器１６７において算出された分岐先アドレスをバッファ１７０、１７１に保持するとともに、分岐実行のタイミングを調整する。【０１０９】
バッファ１７０には、命令フェッチアドレス保持回路１６６から供給される現在のフェッチ中の命令アドレスデータ（フェッチされる命令が分岐命令の場合には、分岐元アドレス）が格納される。この分岐先アドレスデータは、上位３２ビット定義コードと、下位３２ビットアドレスを含む。【０１１０】
また、バッファ１７１には、選択回路１６９によって選択された分岐先アドレスデータ（演算器１６７によって計算されたアドレスまたは相対アドレス演算器１６８によって計算されたアドレス）が格納される。この分岐先アドレスデータは、上位３２ビット定義コードと、下位３２ビットアドレスを含む。【０１１１】
分岐命令（レジスタ間接分岐命令またはＰＣ相対分岐命令）が演算器１６７または相対アドレス演算器１６８で処理され、分岐先アドレスが確定すると、分岐元アドレスが、バッファ１７０から分岐予測装置１００に送出される。また、このとき、分岐先アドレスがバッファ１７１から分岐予測装置１００に送出される。【０１１２】
（分岐予測装置）
分岐予測装置１００は、分岐リザベーションステーション１２６において分岐実行が確定された分岐命令（ＰＣ相対分岐命令、または、レジスタ間接分岐命令）の分岐先アドレスを分岐履歴として格納する。分岐予測装置装置１００は、分岐履歴記憶装置１３０（本発明の履歴記憶部に相当）と、マッチ回路１８０と、選択回路１８３とを含む。なお、分岐予測装置装置１００は、単に分岐実行が確定された分岐命令を格納する他、複数回の分岐履歴（いわゆるグローバルヒストリ）に基づいて、次回分岐が予測される分岐命令の分岐先アドレスを格納するようにしてもよい。【０１１３】
分岐履歴記憶装置１３０は、セットアソシアティブ方式の記憶装置である。分岐履歴記憶装置１３０のセットは、分岐命令の分岐元アドレスの一部（例えば、＜１５：５＞（第１５ビット目から第５ビット目まで））によって指定される。【０１１４】
セット内のウェイは、タグ部１３０Ａに格納されたタグによって決定される。タグ部１３０Ａには、分岐元アドレスの上位３２ビット定義コードおよび下位３２ビットアドレスの一部（例えば、＜３１：１６＞（第３１ビット目から第１６ビット目まで）が格納される。【０１１５】
一方、そのタグ部に対応するデータ部１３０Ｂには、分岐先アドレスの上位３２ビット定義コードおよび下位３２ビットアドレスが格納される。【０１１６】
また、分岐予測装置１００は、分岐履歴記憶装置１３０の読み出しにおいては、選択回路１６５を通じて現在フェッチ中の命令アドレス（分岐元アドレス）を取得する。そして、分岐予測装置１００は、その命令アドレスによって、該当するセットを決定し、さらにセット内のタグ部１３０Ａを検索する。そして、分岐予測装置１００は、タグ部１３０Ａに格納された上位３２ビット定義コードおよび下位アドレスの一部（例えば、＜３１：１６＞）が、選択回路１６５から取得されたものと一致するか否かをマッチ回路１８０によって確認する。【０１１７】
マッチ回路１８０の一方の入力には、ＦＦ１８２を通じて、上位３２ビット定義コードおよび下位アドレスの一部（例えば、＜３１：１６＞）が、入力されている。マッチ回路１８０の他方の入力には、タグ部１３０Ａに記憶されていたタグ（過去において次回分岐すると予測された分岐命令の分岐元の上位３２ビット定義コードおよび下位アドレスの一部＜３１：１６＞）が入力される。【０１１８】
したがって、現在フェッチ中の命令アドレスに対応する上位３２ビット定義コードおよび下位アドレスの一部＜３１：１６＞がタグ部１３０Ａの内容と一致した場合に、分岐予測がヒットすることになる。【０１１９】
分岐予測がヒットしたことがマッチ回路で検知されると、そのヒットを示した信号が選択回路１８３に送出される。選択回路１８３は、タグ部１３０Ａのヒットしたエントリに対応するデータ部１３０Ｂから分岐先の命令アドレスデータ（上位３２ビット定義コードおよび下位３２ビットアドレス）を命令フェッチ制御ユニットのバッファＴＩＡＲ１６４に送出する。これによって、分岐予測に基づいて次の命令フェッチが実行されることになる。【０１２０】
（上位ビットデコーダ）
図６に、上位ビットデコーダ１５０Ａ（および１５０Ｂ）の回路構成を示す。上位ビットデコーダ１５０Ａ（および１５０Ｂ）は、それぞれ、上位３２ビット定義コードが００（ｂ）、０１（ｂ）、および１１（ｂ）の場合の上位３２ビットアドレスを復元する。【０１２１】
上位ビットデコーダ１５０Ａ、１５０Ｂは、セレクタ３００と、４つのＡＮＤゲートと、インバータの組合せで構成することができる。なお、図６では、インバータは、ＡＮＤゲートの入力端子側の丸印で示されている。ここでは、このような入力側にインバータが組み込まれたものについても、ＡＮＤゲートと呼ぶことにする。【０１２２】
それぞれのＡＮＤゲートには、上位３２ビット定義コード（図６では、ＨＩＧＨ＿３２ＢＩＴ＿ＣＯＤＥ＜１＞および＜０＞で表示）が入力される。”１１”のラベルが付されたＡＮＤは、上位３２ビット定義コード＜１：０＞＝１１（ｂ）の場合に、ＨＩ出力となる。【０１２３】
同様に、”１０”のラベルが付されたＡＮＤは、上位３２ビット定義コード＜１：０＞＝１０（ｂ）の場合に、ＨＩ出力となる。また、’０１’のラベルが付されたＡＮＤは、上位３２ビット定義コード＜１：０＞＝０１（ｂ）の場合に、ＨＩ出力となる。また、”００”のラベルが付されたＡＮＤは、上位３２ビット定義コード＜１：０＞＝００（ｂ）の場合に、ＨＩ出力となる。【０１２４】
一方、セレクタ３００は、それぞれのＡＮＤゲートがオンになると、対応する箇所の入力信号を出力する。セレクタ３００の入力側には、３つの固定のデータのレジスタ（０ｘＦＦＦＦＦＦＦＦ、０ｘ０００００００１、および０ｘ００００００００）と、上位３２ビットアドレスそのもの（ＡＤＤＲＥＳＳ＿ＩＮ＜６３：３２＞）を格納したレジスタが接続される。【０１２５】
すなわち、”１１”のラベルが付されたＡＮＤがオンになることによって、上位３２ビットすべてが１のビットパターン（０ｘＦＦＦＦＦＦＦＦ）が出力される。また、”０１”のラベルが付されたＡＮＤがオンになることによって、上位３２ビットのうち最下位ビットが１で、残りのビットが０のビットパターン（０ｘ０００００００１）が出力される。また、”００”のラベルが付されたＡＮＤがオンになることによって、上位３２ビットすべてが０のビットパターン（０ｘ００００００００）が出力される。また、”１０”のラベルが付されたＡＮＤがオンになることによって、上位３２ビットアドレスそのものが出力される。【０１２６】
（上位ビットエンコーダ）
図７に、上位ビットエンコーダ１５３Ａ（１５３Ｂ）の構成を示す。上位ビットエンコーダは、上位３２ビットアドレス（図７に、ＡＤＤＲＥＳＳ＿ＩＮ＜６３：３２＞と表示）が入力され、上位３２ビット定義コード（図７に、ＨＩＧＨ＿３２ＢＩＴＣＯＤＥ＜１：０＞と表示）を出力する。【０１２７】
図７のように、上位ビットエンコーダ１５３Ａ（１５３Ｂ）は、ビットパターン３２ビットのビットパターン”１１１．．．１１”（全ビット１、すなわち、０ｘＦＦＦＦＦＦＦＦ）、”０００．．．０１”（最下位ビットが１、残りがすべて０、すなわち、０ｘ０００００００１）、”０００．．．００”（全ビット０、すなわち、０ｘ００００００００）に、入力データがマッチするか否かを判定する３つのマッチ回路と、入力データとマッチしたマッチ回路の出力に応じて、”１１”、”１０”、”０１”、または”００”の２ビットを出力するセレクタ３０１とを有している。【０１２８】
（処理シーケンス）
図８から図１１のフローチャートにより、上述の構成要素によって実行される処理シーケンスを説明する。ここでは、処理シーケンスをフローチャートで示すが、この処理シーケンスは、基本的には、ハードウェアの論理回路で実現される。【０１２９】
図８は、上位ビットエンコーダの処理シーケンスを示す。上位ビットエンコーダは、上位３２ビットアドレスが０ｘＦＦＦＦＦＦＦＦ、０ｘ０００００００１、または０ｘ００００００００のいずかにマッチするか否かを判定する（Ｓ１、Ｓ３、Ｓ５）。【０１３０】
上位３２ビットアドレスが０ｘＦＦＦＦＦＦＦＦにマッチする場合、上位ビットエンコーダは、２ビット１１（ｂ）を出力する（Ｓ２）。【０１３１】
また、上位３２ビットアドレスが０ｘ０００００００１にマッチする場合、上位ビットエンコーダは、２ビット０１（ｂ）を出力する（Ｓ４）。【０１３２】
また、上位３２ビットアドレスが０ｘ００００００００にマッチする場合、上位ビットエンコーダは、２ビット００（ｂ）を出力する（Ｓ６）。【０１３３】
そして、上位３２ビットアドレスが０ｘＦＦＦＦＦＦＦＦ、０ｘ０００００００１、または０ｘ００００００００のいずかにもマッチしない場合、上位ビットエンコーダは、２ビット１０（ｂ）を出力する。【０１３４】
図９に上位ビットデコーダの処理シーケンスを示す。上位ビットデコーダは、上位３２ビット定義コード（２ビット）が１１（ｂ）、０１（ｂ）、または００（ｂ）のいずかにマッチするか否かを判定する（Ｓ１１、Ｓ１３、Ｓ１５）。【０１３５】
上位３２ビット定義コードが、１１（ｂ）である場合、上位ビットデコーダは、１．．．１１（全ビット１、すなわち、０ｘＦＦＦＦＦＦＦＦ）を出力する（Ｓ１２）。【０１３６】
上位３２ビット定義コードが、０１（ｂ）である場合、上位ビットデコーダは、０．．．０１（最下位ビット以外０、すなわち、０ｘ０００００００１）を出力する（Ｓ１４）。【０１３７】
上位３２ビット定義コードが、００（ｂ）である場合、上位ビットデコーダは、０．．．００（全ビット０、すなわち、０ｘ００００００００）を出力する（Ｓ１６）。【０１３８】
上位３２ビット定義コードが、以上のいずれでもない場合、上位３２ビット定義コードは、１０（ｂ）となる。この場合、上位ビットデコーダは、入力された３２ビットアドレス、本実施形態ではプログラムカウンタの現在値ＰＣ１５２の上位３２ビットを出力する（Ｓ１７）。【０１３９】
以上述べたように、本実施形態の処理装置によれば、６４ビットアドレス空間のうち、上位３２ビットアドレスを２ビットの上位３２ビット定義コード００（ｂ）、０１（ｂ）、１１（ｂ）、および０１（ｂ）のコードで分類する。そして、上位３２ビット定義コードと下位３２ビットアドレスの組合せによって、分岐命令の履歴を記憶し、分岐予測を実行する。【０１４０】
したがって、６４ビットアドレス空間に、カーネル、ユーザプロセスの実行形式、および、スタック／ライブラリを分散配置するＯＳの制御に対して、上位３２ビットアドレスの使用に偏りがある場合、効率的に分岐予測を実現できる。【０１４１】
すなわち、上位３２ビット定義コードのうち、００（ｂ）、０１（ｂ）、１１（ｂ）を頻繁するアドレスの範囲に割り付け、１０（ｂ）をまれにしか発生しないアドレスの範囲に割り付ける。このような上位３２ビット定義コードの定義により、分岐先アドレスが、下位３２ビットの範囲で収まる場合は、もちろん、分岐先の上位３２ビットが００（ｂ）、０１（ｂ）、１１（ｂ）で分類されるアドレス空間相互で分岐が発生する場合にも、正しい分岐予測結果を得ることができる。したがって、分岐先の上位３２ビットが１０（ｂ）（その他の場合）を除外して、分岐履歴を有効に使用することができる。【０１４２】
また、ＰＣ相対分岐の場合に、プログラムカウンタの現在の値ＰＣ１５２から分岐先アドレスを復元することにより、相対アドレス演算器１６８の演算結果が確定する前に桁あふれが検知された段階で、分岐先アドレスを算出できる。
【図１】
0005136405.tif 000002
【図２】
0005136405.tif 000003
【図３】
0005136405.tif 000004
【図４】
0005136405.tif 000005
【図５】
0005136405.tif 000006
【図６】
0005136405.tif 000007
【図７】
0005136405.tif 000008
【図８】
0005136405.tif 000009
【図９】
0005136405.tif 000010
【図１０】
0005136405.tif 000011
【図１１】
0005136405.tif 000012