(57)【特許請求の範囲】
【請求項１】
コンパイラであって、
（Ａ）分岐インストラクションの分岐統計データに含まれる分岐プロファイル情報及びレジスタ・ダンプ情報を分析して、分岐方向と当該分岐の所定サイクル前のプロセッサのレジスタ内容との相関を識別することによって、分岐インストラクションのための分岐予測関数を構築する分岐統計データ・アナライザと、
（Ｂ）分岐統計データ・アナライザに接続されて、分岐予測関数を実行するための予測インストラクションを少なくとも１つ生成する分岐予測インストラクション・ジェネレータと、
（Ｃ）分岐予測インストラクション・ジェネレータに接続されて、分岐インストラクションの前に予測インストラクションを挿入するための主コンパイル・エンジンと、
を備えるコンパイラ。
【請求項２】
前記分岐予測関数は、少なくとも１つのレジスタ内容と分岐インストラクションの分岐方向とを関連付ける、請求項１に記載のコンパイラ。
【請求項３】
前記分岐予測インストラクション・ジェネレータは、分岐インストラクションの分岐行先アドレスを指定するプリペア・トゥ・ブランチ・インストラクションと、レジスタ内容を分岐予測関数によって指定された閾値と比較するコンペア・インストラクションを発生する、請求項２に記載のコンパイラ。
【請求項４】
前記主コンパイラ・エンジンは、分岐統計データ・アナライザに接続されて、分岐インストラクションをコンパイルする前に、分岐統計データ・アナライザ内で分岐統計データが使用可能かどうかを判断し、分岐統計データ・アナライザにとって分岐統計データは使用可能でないと主コンパイラ・エンジンが判断したときには、前記主コンパイラ・エンジンは、分岐インストラクションを含むソース・コードをコンパイルするときにはいかなるインストラクションも挿入しない、請求項１に記載のコンパイラ。
【請求項５】
挿入される前記予測インストラクションは、前記分岐インストラクションよりも１から６４サイクルだけ手前に置かれる、請求項１に記載のコンパイラ。
【請求項６】
プログラム中の分岐インストラクションを動的に予測する方法であって、
（Ａ）分岐インストラクションについての分岐予測関数を構築するために、分岐インストラクションの分岐統計データに含まれる分岐プロファイル情報及びレジスタ・ダンプ情報を分析して、分岐方向と当該分岐の所定サイクル前のプロセッサのレジスタ内容との相関を識別することによって分岐方向と当該分岐の所定サイクル前のプロセッサのレジスタ内容との相関に基づいた分岐予測関数を生成するステップと、
（Ｂ）分岐予測関数を実行するための予測インストラクションを少なくとも１つ生成するステップ、
（Ｃ）分岐インストラクションの前に予測インストラクションを挿入する挿入するステップ、
を含む方法。
【請求項７】
ステップ（Ａ）は、さらに、
（ａ）各分岐インストラクションの実行よりも所定サイクル前における各レジスタの内容を判別するステップと、
（ｂ）各分岐インストラクションの実行における分岐方向を判別するステップと、
（ｃ）どのレジスタがどういう内容の値のときに分岐インストラクションが分岐するかを判別することによって、分岐方向とレジスタ内容の間の相関を確立するステップと、
を含む請求項６に記載の方法。
【請求項８】
前記生成するステップは、分岐予測関数を実行するコンペア・インストラクションと、分岐予測関数を受け取ったことに応答して分岐インストラクションの行先アドレスを指定するプリペア・トゥ・ブランチ・インストラクションを生成する、請求項６に記載の方法。
【請求項９】
（Ｄ）分岐統計データが分岐統計データ・アナライザ内で使用可能かどうかをステップ（Ｃ）よりも前に判別するステップと、
（Ｅ）分岐統計データが分岐統計データ・アナライザにとって使用可能でないならば、分岐インストラクションを含んだソース・コードをコンパイルするときには、ステップ（Ｃ）を実行しないステップと、
をさらに含む請求項６に記載の方法。
【請求項１０】
（Ａ）分岐インストラクションについての分岐統計データに含まれる分岐プロファイル情報及びレジスタ・ダンプ情報を分析して、分岐方向と当該分岐の所定サイクル前のプロセッサのレジスタ内容との相関を識別することによって分岐方向と当該分岐の所定サイクル前のプロセッサのレジスタ内容との相関に基づいた分岐予測関数を生成する第１の手順と、
（Ｂ）分岐予測関数を実現するための予測インストラクションを少なくとも１つ生成する第２の手順と、
（Ｃ）分岐インストラクションを含んだソース・コードを機械コードにコンパイルするときには、分岐インストラクションの前に予測インストラクションを挿入する第３の手順と、
をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１１】
前記第１の手順は、
（ａ）各分岐インストラクションの実行よりも所定サイクル前における各レジスタの内容を判別し、
（ｂ）各分岐インストラクションの実行における分岐方向を判別し、
（ｃ）どのレジスタがどのような内容の値をとるときに分岐インストラクションが分岐するかを判別することによって、分岐方向とレジスタ内容の間の相関を確立する、
ことにより、分岐インストラクションについての分岐プロファイル情報とレジスタ・ダンプ情報を分析する、請求項１０に記載の記録媒体。
【請求項１２】
前記第２の手順は、分岐予測関数を実現するコンペア・インストラクションと、分岐予測関数を受け取ったことに応答して分岐インストラクションの分岐行先アドレスを指定するプリペア・トゥ・ブランチ・インストラクションを生成する、請求項１０に記載の記録媒体。
【請求項１３】
（Ｄ）分岐インストラクションを含んだソース・コードをコンパイルする前に、分岐統計データ・アナライザ内で分岐統計データが使用可能かどうかを判別する第４の手順と、
（Ｅ）分岐統計データが使用可能でないときには、第３の手順において予測インストラクションを挿入しないようにする第５の手順と、
をさらに備える請求項１０に記載の記録媒体。
【請求項１４】
挿入される前記予測インストラクションは、前記分岐インストラクションよりも１から６４サイクルだけ手前に置かれる請求項１０に記載の記録媒体。
【請求項１５】
実行時間分岐予測シンセサイザであって、
（Ａ）分岐インストラクションの分岐統計データに含まれる前記分岐プロファイル情報及び前記レジスタ・ダンプ情報を分析して、分岐方向と当該分岐の所定サイクル前のプロセッサのレジスタ内容との相関を識別することによって、分岐インストラクションについての分岐予測関数を構築する分岐統計データ・アナライザと、
（Ｂ）分岐統計データ・アナライザに接続されて、分岐予測関数を実現するための予測インストラクションを少なくとも１つ生成する分岐予測インストラクション・ジェネレータと、
（Ｃ）分岐予測インストラクション・ジェネレータに接続されて、予測インストラクションを分岐インストラクションの前に挿入する実行時間コード・マネージャと、
を備える実行時間分岐予測シンセサイザ。
【請求項１６】
前記分岐予測関数は少なくとも１つのレジスタ内容を前記分岐インストラクションの分岐方向と関連付け、前記分岐予測インストラクション・ジェネレータは、前記分岐インストラクションの分岐行先アドレスを指定するプリペア・トゥ・ブランチ・インストラクションと、レジスタ内容を分岐予測関数によって指定された閾値と比較するコンペア・インストラクションとを生成する、請求項１５に記載の実行時間分岐予測シンセサイザ。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータ・システムに関する。より具体的には、本発明はコンピュータ・システムにおける、正確で且つコスト効果のある合成的な動的分岐予測に関する。
【０００２】
【従来の技術】
既に知られているように、典型的なコンピュータ・システムは１つ又はそれ以上の中央演算ユニット（ＣＰＵ）若しくはプロセッサを含んでいる。プロセッサは、典型的には、ソフトウェア・プログラムのインストラクションを実行することによって、コンピュータ・システム上において種々のタスクを遂行するようになっている。ソフトウェア・プログラムのインストラクションは、機械言語形式（すなわちバイナリ形式）である。何故ならば、プロセッサは、機械言語しか理解したり解釈できないからである。機械言語のインストラクションのことを、以下では機械コード若しくはオブジェクト・コードと呼ぶことにする。
【０００３】
機械言語は、書いたり理解するには非常に難しいので、人が読むことができる様式でソフトウェア・プログラムのインストラクションをコード化したり定義するために、高級なソース・プログラミング言語（例えばＣ言語やＦｏｒｔｒａｎ）が開発されてきた。このようなソース・プログラミング言語で記述されたソフトウェア・プログラムは、ソース・コードと呼ばれる。ソース・コードは、プロセッサによって実行する前に、コンパイラ・プログラムによって機械コードに変換若しくは翻訳してやる必要がある。
【０００４】
初期の従来技術であるプロセッサは、典型的には、１インストラクション１データ（single instruction single data：ＳＩＳＤ）型のプロセッサである。ＳＩＳＤ型プロセッサは、典型的には、単一のインストラクション・ストリームと単一のデータ・ストリームを受け取るようになっている。このＳＩＳＤプロセッサは、単一の記憶領域内のデータに従って動作しながら、各インストラクションを順次実行しするようになっている。しかしながら、このようなＳＩＳＤプロセッサのアーキテクチャは、高い処理スループットを実現する上で、ある障害を内包している。
【０００５】
プロセッサの処理スループットを増大させるために、数多くの並列処理アーキテクチャが開発されてきた。かかる並列処理モデルの１つのタイプとして、パイプライン処理が知られている。単一のパイプラインを持つプロセッサでは、パイプラインは、典型的には、幾つかのステージを備えている。これらステージには、例えば、フェッチ（取り出し）・ステージ、デコード（解釈）・ステージ、実行ステージ、及び、ライト・バック（書き戻し）・ステージが含まれる。このようなパイプライン化プロセッサでは、インストラクションは、パイプラインのこれらステージを通して重なり合うようにして、順次実行されるようになっている。
【０００６】
しかしながら、パイプライン化プロセッサのパフォーマンスは、分岐オペレーションを取り扱う効率に強く依存している。分岐オペレーションのことを、以下では分岐と呼ぶことにする。既に知られているように、分岐は、典型的には、プログラム実行中にインストラクション・フローをリダイレクトすることによって、パイプラインを長時間中断させてしまう。これは、典型的には、分岐インストラクションがフェッチされたときには次に実行すべきインストラクションのアドレスは瞬時には分からない、という事実に依拠する。このため、フェッチ・ステージは、機能停止（ストール）を余儀なくされ、分岐の行先が計算されるのを待たねばならない。分岐の行先は、一般的には、実行ステージで求められる。それ故、パイプラインのデコード・ステージ及び実行ステージを経て分岐が進行する間、フェッチ・ユニットは機能停止してしまうのである。分岐インストラクションの実行が完了した後になって、分岐方向が判明して、正しい行先アドレスにおいてインストラクション・フェッチを無事に再開することができる。各分岐毎にインストラクション・フェッチをストールさせると、パイプラインに数多くの空のサイクルを招来してしまう。この空のサイクルはバブルと呼ばれる。これらバブルは、プロセッサ・リソースの利用を制限してしまうので、パイプライン化プロセッサのパフォーマンスを厳に抑制することとなる。パイプラインの深さやプロセッサのインストラクション発行幅が増すにつれ、パフォーマンスの問題は増幅する。ここで、インストラクション発行幅とは、サイクル当りにプロセッサが実行可能なインストラクション数のことである。
【０００７】
分岐インストランションによって生じるパイプラインの破壊を最小限にするために、分岐予測が採用されている。分岐予測は、パイプライン化プロセッサにおける分岐を取り扱うのに効果的な解決手法である。分岐予測は、分岐の行先を推測することによって、分岐の行先を計算している間に実行中のインストラクションを投機的に継続させるものである。予測が正しい場合には、全ての投機的なインストラクションは有益なインストラクションとなり、パイプラインのバブルは完全に除去される。これに対し、正しくない予測は、分岐の行先を解く間はただのパイプラインのバブルになるとともに、不適切に実行された全てのインストラクションを取り除くために余分な遅れを生じさせてしまう。明らかに、分岐予測ストラテジの正確さは、プロセッサのパフォーマンスにとって重要なのである。
【０００８】
伝統的に、分岐予測は、１つ或は２つの方法によってなされている。すなわち、１つはコンパイル時間にコンパイラ解析を通して行う静的予測であり、もう１つは特殊なハードウェア構造によって実行時間に行われる動的予測である。静的分岐予測は、予測を行うために、コンパイル時間に利用可能な情報を利用するものである。一般には、静的分岐予測は、コンパイラが責任を持って行う。最も一般的な静的分岐予測手法は、プロファイル情報を用いることである。図１及び２には、この実施態様を示している。すなわち、図１は分岐インストランションのインストラクション・フォーマットを図示しており、また、図２はプロファイル情報を用いた静的分岐予測手法の処理を図解した状態遷移図である。
【０００９】
図１から分かるように、各分岐インストラクションには予測ビットが１個設けられている。分岐インストラクションに予測ビットをセットするためには、まず、分岐インストラクションを含んでいるソース・コードがコンパイラによって機械コードに変換される（図２のプレ・コンパイル・ステージ２０を参照のこと）。この時点では、分岐インストラクションの予測ビットはセットされていない。次いで、機械コードがサンプル入力データとともに実行されて（図２のコード実行ステージ２１を参照のこと）、分岐インストランションの分岐統計データを得る。分岐統計データとは、分岐が起こる（すなわち分岐する）回数と分岐が起こらない（すなわち分岐しない）回数を示すものである。次いで、コンパイル・ステージ２２においてソース・コードが統計データとともにコンパイルされ、これに従って分岐インストラクションの予測ビットをセットする。もし、大部分の場合に分岐が起こることを統計データが示していれば、コンパイル・ステージ２２においてコンパイラは、分岐インストラクションの予測ビットには「起こる」旨をセットする。そうでなければ、コンパイラは、予測ビットには「起こらない」旨をセットする。静的分岐予測の主要な利点は低コストなことである。他の利点は、ハードウェアの必要なしに予測を実現できることにある。プログラム自身によって予測が明確に指定されるので、コードの実行に際して分岐状態情報は必要でない。
【００１０】
しかしながら、静的分岐予測には幾つかの欠点を伴っている。予測がコンパイル時に固定されてしまうので、プログラム実行中には変更が効かないという欠点である。この結果、静的分岐予測の精度は、本質的にバイアスのない分岐に限定されてしまう。他の欠点は、各分岐インストラクションが予測のために余分な１ビットを必要とすることである。
【００１１】
他方、動的分岐予測は、実行時間の振る舞いを利用して予測を行うものである。一般に、分岐履歴を維持するためのハードウェア構造が設けられる。現在の履歴に基づいて、プログラムの中で出現する各分岐に対して予測が行われる。図３には、従来の動的分岐予測手法を示している。図３から分かるように、複数のエントリを持つ２ビット・カウンタ３１が１個設けられている。プログラム３０の分岐３０ａを実行するとき、分岐３０ａは２ビット・カウンタ３１の対応するエントリ３１ａにハッシングされる。エントリ３１ａに格納された値によって、分岐３０ａが起こるか否かが判断される。もし、分岐３０ａが起こるのであれば、エントリ３１ａに格納されたカウンタ値はインクリメントされる。もし分岐３０ａが起こらないのであれば、エントリ３１ａに格納されたカウンタ値はデクリレントされる。カウンタ３１のエントリのカウンタ値が３に到達したときには、さらにインクリメントすべきときであってもその値は３に維持されたままである。動的分岐予測の主要な利点は、正確さが増すことである。実行時間の情報を利用し、様々の実行フェーズにおいて異なる分岐予測を行う能力を備えることによって、動的分岐予測技術は、静的分岐予測よりも著しく高い精度を享受している。
【００１２】
しかしながら、動的分岐予測が欠点を持たない訳ではない。動的分岐予測技術の主な欠点の１つはコストである。何故ならば、動的分岐予測技術は典型的には比較的大規模なハードウェアを使用するし、目標のサイクル時間に適うために回路設計者に困難な挑戦を強いるからである。
【００１３】
【発明が解決しようとする課題】
本発明の１つの特徴は、分岐予測を行うことによって、分岐インストラクションによって生じるパイプラインの破壊を最小限に抑えることにある。
【００１４】
本発明の他の特徴は、最大限の精度と最小限のコストを以て分岐予測を最適化することである。
【００１５】
本発明の更なる特徴は、コスト効果がありしかも比較的精度のよい合成式動的分岐予測機能を提供することにある。
【００１６】
【課題を解決するための手段】
以下には、分岐インストラクションの分岐統計データを分析して、分岐インストラクションについての分岐予測関数を構築するための分岐統計データ・アナライザを含んだコンパイラが記載されている。分岐予測インストラクション・ジェネレータは、この分岐統計データ・アナライザに接続されて、分岐予測関数を実現するための予測インストラクションを少なくとも１つ生成するようになっている。主コンパイラ・エンジンは、この分岐予測インストラクション・ジェネレータに接続されて、分岐インストラクションの前に予測インストラクションを挿入するようになっている。
【００１７】
さらに、分岐インストランションの分岐予測関数を構築するために分岐インストラクションの分岐統計データを分析する分岐統計データ・アナライザを含んだ実行時間分岐予測シンセサイザも記載されている。分岐予測インストラクション・ジェネレータは、この分岐統計データ・アナライザに接続されて、分岐予測関数を実現するための予測インストラクションを少なくとも１つ生成するようになっている。実行時間コード・マネージャは、この分岐予測インストラクション・ジェネレータに接続されて、分岐インストラクションの前に予測インストラクションを挿入するようになっている。
【００１８】
本発明のさらに他の特徴や利点は、本発明の原理を例示という形態で図解した添付図面に関連した後述する詳細な記述によって明らかになるであろう。
【００１９】
【発明の実施の形態】
本発明の幾つかの実施例についての以下の詳細な記述では、明確化のために特定の用語を使用している。しかしながら、本発明はこれら本明細書中で採用された特定の用語に限定されるものではなく、むしろ、実質的に同様の形態で動作して実質的に同様の作用効果を成し遂げるような技術的等価物の全てを包含するものである。
【００２０】
図４には、分岐予測メカニズムを含んだプロセッサ１０２を備えたコンピュータ・システム１００を図解している。コンピュータ・システム１００は、コンパイラ２００も備えている（図５を参照のこと）。プロセッサ１０２の分岐予測メカニズムによって、コンパイラ２００（図５）は、本発明の１つの実施態様を実現するコンパイラ合成式動的分岐予測機能を含むことができる。コンパイラ２００及びそのコンパイラ合成式動的分岐予測機能については、後により詳しく記述する。
【００２１】
プロセッサ１０２の分岐予測メカニズムの主要な特徴は、プロセッサ１０２のインストラクション・セットにおける分岐予測が可視的な点である。このことによって、コンピュータ・システム１００のコンパイラ２００は、プログラム中の特定の分岐についての予測値を操作するインストラクションを生成することができるのである。コンパイラ２００がインストラクションを生成するに際して、予測値を計算してこれらを適当な予測位置に書き込むための付加的なインストラクションをプログラム中に挿入する能力をコンパイラ２００に与えることによって、新しい予測関数が実現される。さらに、プロセッサ１０２の予測メカニズムによれば、分岐予測位置を分岐自体に関連付けることもできる。このことは、特定の分岐について選択的に予測値を修正するために必要である。
【００２２】
１つの実施態様では、プロセッサ１０２の分岐予測メカニズムは静的予測メカニズムを拡張したものである。他の実施態様では、プロセッサ１０２の分岐予測メカニズムは、ハードウェア・ベースの動的予測メカニズムである。あるいは、プロセッサ１０２は、分岐予測をサポートした他のタイプの分岐アーキテクチャを持つこともできる。拡張型静的分岐予測メカニズムとハードウェア・ベースの動的分岐予測メカニズムのいずれであっても、プロセッサ１０２は、本発明に係るコンパイラ合成式動的分岐予測機能を充分且つ有効にサポートすることができる。
【００２３】
例えば、プロセッサ１０２が拡張型静的予測メカニズムをサポートするときには、プロセッサ１０２は、分岐を複数ステップで実行するようになっている。例えば、条件分岐については３ステップで実行し、非条件分岐については２ステップで実行する。条件分岐に含まれるステップとは以下のようなものである。
【００２４】
１．行先アドレスの指定：
このステップは、プリペア・トゥ・ブランチ（分岐準備）若しくは同様に機能する他のインストラクションによって実行される。プリペア・トゥ・ブランチ（ＰＴＢ）インストラクションは、実行すべき行先アドレスからのインストラクションのプリフェッチ（先取り）を許容することで、分岐点の前に分岐の行先アドレスを指定するようになっている。コンパイラが分岐を進むと信じるような指示を表すために、このステップでは静的予測ビットも設けられている。
【００２５】
２．分岐条件の計算：
コンペア・トゥ・プレディケート（述語比較）若しくは同様に機能する他のインストラクションによって分岐条件を計算することができ、述語レジスタ中に格納される。
【００２６】
３．制御の譲渡：
もし分岐が起こると、制御フローのリダイレクションが実際に生じる。条件的、非条件的、分岐及びリンク、ループ実行をサポートするための特別な分岐など、分岐インストラクションには幾つかのタイプがある。
【００２７】
非条件的な分岐（若しくはジャンプ）は条件の計算を含まず、したがって、最初と最後のステップのみからなる。
【００２８】
分岐処理を実行するために、プリペア・トゥ・ブランチ・インストラクションは、分岐行先レジスタ・セット（ＢＴＲ）（図４には示されていない）の中に、計算された有効行先アドレスと予測ビットを書き込む。上述したように、分岐が起こったときには、プリペア・トゥ・ブランチ・インストラクションは分岐の行先アドレスを指定する。分岐行先レジスタは、プロセッサ１０２の分岐ユニット及びインストラクション・フェッチ・ユニットに行先及び予測情報を伝達するための媒体である。
【００２９】
さらに、プリペア・トゥ・ブランチ・インストラクション中には、述語レジスタ・オペランド・フィールドが設けられている。このため、任意の機械インストラクション・セットによって予測値を計算して、その最終結果をプロセッサ１０２の述語レジスタ（図４には示されていない）中に置くことができる。プリペア・トゥ・ブランチ・インストラクションは、続いて、特定の述語レジスタを読んで、予測値を得る。
【００３０】
コンペア・トゥ・プレディケート・インストラクションは、実際に比較処理を行い、その結果を述語レジスタに格納するようになっている。最終的なインストラクションは、実際の分岐処理を実行する。各分岐は、分岐行先アドレスを格納したソースＢＴＲを指定している。さらに、全ての条件的な分岐は、条件としてソース述語オペランドを指定している。さらに、プリペア・トゥ・ブランチ・インストラクションには新しい１ビット・リテラル（定数）・フィールドが付加されており、該フィールドによって述語オペランドが実際の分岐方向又は単なる予測のいずれであるかが指定される。
【００３１】
コンピュータ・システム１００は、パーソナル・コンピュータ、ノートブック・コンピュータ、パームトップ・コンピュータ、ワークステーション、メインフレーム・コンピュータ又はスーパー・コンピュータのいずれであってもよい。あるいは、コンピュータ・システム１００は他のタイプのコンピュータ・システムであってもよい。例えば、コンピュータ・システム１００は、ネットワーク・サーバ、あるいはビデオ会議システムであってもよい。
【００３２】
コンピュータ・システム１００は、プロセッサ１０２に接続されたバス１０１を含んでいる。メモリ１０４は、バス１０１に接続されており、典型的には、プロセッサ１０２で実行される情報やインストラクションを格納するために用いられる。メモリ１０４は、コンピュータ・システム１００のディスプレイ１２１上に表示するためのビットマップ・イメージのフレームを格納するためのフレーム・バッファ（図４には示していない）を含んでいてもよい。
【００３３】
メモリ１０４は、数タイプのメモリで実装されていてもよい。例えば、メモリ１０４は、ＲＡＭ（ランダム・アクセス・メモリ）及び／又は不揮発性メモリで実装されてもよい。さらに、メモリ１０４は、ＲＡＭ、ＲＯＭ（リード・オンリー・メモリ）、及び／又は電気的に消去可能でプログラム可能な不揮発性メモリとの組み合わせで実装されてもよい。
【００３４】
コンピュータ・システム１００は、バス１０１に接続された大容量記憶装置１０７も含んでいる。大容量記憶装置１０７は、データやその他の情報を格納するようになっている。さらに、大容量記憶装置１０７は、システム・プログラムやアプリケーション・プログラムも格納する。これらプログラムは、プロセッサ１０２によって実行されるが、プロセッサ１０２によって実行される前にメモリ１０４にダウンロードしておく必要がある。
【００３５】
ディスプレイ１２１はバス１０１に接続されている。キーボード若しくはキーパッド式の入力装置１２２も装備され、バス１０１に接続されている。コンピュータ・システム１００の付加的な入力装置として、マウス、トラックボール、トラックパッド、若しくはカーソル方向キーのようなカーソル制御装置１２３が備えられている。コンピュータ・システム１００に装備可能な他の装置として、ハード・コピー装置１２４が挙げられる。ハード・コピー装置１２４は、テキスト情報及び／又はイメージ情報を、紙、フィルム、若しくは同様のタイプの媒体上に印刷するために、コンピュータ・システム１００上で使用される。
【００３６】
コンピュータ・システム１００は、その他の周辺装置１２６も含んでいる。加えて、コンピュータ・システム１００は、上述のコンポーネントのうちの幾つかが無くても機能することができる。図４には、コンピュータ・システム１００の基本コンポーネントのうちの幾つかを示しているが、このことは、これらのコンポーネントに限定したり、あるいは、システム１００における他のコンポーネントやコンポーネント同士の組み合わせを排除することを意味しない。
【００３７】
図５から分かるように、コンパイラ２００は、プロセッサ１０２上で稼働して、ソース・コード２０１を機械コード２０２にコンパイルするようになっている。ソース・コード２０１はインストラクション・セットで構成され、その中には分岐インストラクションも含まれている。機械コード２０２は大容量記憶装置１０７に格納される。機械コード２０２をプロセッサ１０２で実行するときには、機械コード２０２はメモリ１０４に書き込まれる。
【００３８】
上述したように、コンパイラ２００は、ソース・コード２０１に含まれる分岐インストラクションの分岐予測を行うためのコンパイラ合成式動的分岐予測機能を含んでいる。コンパイラ２００によるコンパイラ合成式動的分岐予測機能は、本発明の１つの実施態様である。本発明の１つの実施態様によれば、コンパイラ２００によるコンパイラ合成式動的分岐予測機能は、予測関数を特定の分岐予測にカスタマイズすることによって、分岐予測の精度を増すようになっている。このことは、分岐プロファイル情報以外のプログラムの相関を識別して、精度を増すことによって成し遂げられる。
【００３９】
コンパイラ２００によるコンパイラ合成式動的分岐予測機能はハードウェア・ベースではない。確かに、コンパイラ２００は、各分岐についての予測関数を定義し実現することに完全に責任を負っている。プロセッサ１０２内のレジスタ（図４には示していない）の内容は、分岐を実行するときの分岐の結果についての完全な情報を提供するので、コンパイラ２００によるコンパイラ合成式動的分岐予測機能は、プロセッサ１０２のレジスタ内容を用いることで分岐予測を実現することができる。特に、ソース・レジスタ値の分岐比較を評価することで、分岐を完全に予測することができるであろう。
【００４０】
プロセッサ１０２のレジスタの内容は分岐を予測するためのパスを提供するが、分岐よりも８サイクル又は１６サイクル手前では完全には予測できないかもしれない。やがて分岐から戻るときには、この情報は次第に完全ではなくなっていく。
【００４１】
本発明の１つの実施態様によれば、コンパイラ２００がソース・コード２０１をコンパイルするときには、コンパイラ２００によるコンパイラ合成式動的分岐予測機能は、分岐プロファイル情報とレジスタ・ダンプ情報を使用して各分岐についての分岐予測関数を定義し、次いで、各分岐インストラクションが予測関数を計算するのに先駆けて、分岐毎に１つ又はそれ以上の明確な予測インストラクションをコード中に挿入するようになっている。各分岐の予測関数は、対応する分岐が起こる又は起こらないための条件を定義するものである。次いで、挿入されたインストラクションによって予測関数を計算して、分岐の予測値を得ることができる。例えば、もし、プロセッサ１０２のレジスタ（例えばレジスタｒ26）が値１０よりも大きいときには分岐ｂが常に起こると判断されたならば、当該分岐のための予測関数はｒ26＞１０＝ｔａｋｅｎとなる。
【００４２】
１つの実施態様では、コードがコンパイルされてしまった後に、予測関数を計算せよというインストラクションがコード中に挿入される。他の実施態様では、コードをコンパイルする前若しくはコンパイルの最中に、インストラクションがコード中に挿入される。
【００４３】
これら予測インストラクションの役割は、分岐を計算し動的に予測することにある。コンパイラ合成式動的分岐予測の第１の主要な利点は、予測関数選択の柔軟性にある。コンパイラ２００は、プロセッサ・レジスタ値に関する新しい関数と同様に、標準的なハードウェアによる予測関数（２ビットカウンタのような）を含めて、ほとんど全ての関数を自在に実現することができる。分岐履歴が有効でない場合には、これら新しい予測関数によって、実質的に予測精度を増すだけの能力が付与される。さらに、コストを最小限に且つパフォーマンスを最大限にするように、各分岐毎に特定の予測関数を仕立てることができる。第２の利点は、ハードウェアのオーバーヘッドを低減する点にある。分岐予測状態情報はもはや保管されず、また、特定のハードウェア構造によって操作されるようなことはない。コンパイラ２００は、分岐予測値を計算するために、アーキテクチャ上は可視のレジスタと明確なインストラクションを用いている。図６から１３では、本発明の１つの実施態様に従ったコンパイラ合成式動的分岐予測手法についてより詳細に図解しており、以下これについて記述する。
【００４４】
図６は、コンパイラ２００によるコンパイラ合成式動的分岐予測機能について示している。図６から分かるように、コンパイラ２００は、主コンパイラ・エンジン２２２と、分岐統計データ・アナライザ２２４と、分岐予測インストラクション・ジェネレータ２２６とを含んでいる。主コンパイラ・エンジン２２２は、適用されたソース・コードを機械コードにコンパイルするようになっている。主コンパイラ・エンジン２２２のコンパイル機能は、既知のコンパイル技術のいずれによっても実現可能である。さらに、主コンパイラ・エンジン２２２は、コンパイルされたコードにインストラクションを付加することもできる。このことは、既知のコンパイル技術によっても行うことができる。
【００４５】
主コンパイラ・エンジン２２２は、分岐統計データ・アナライザ２２４と、分岐予測インストラクション・ジェネレータ２２６に接続されている。分岐統計データ・アナライザ２２４は、分岐予測インストラクション・ジェネレータ２２６にも接続されている。分岐統計データ・アナライザ２２４は、分岐統計データを受け取って、データを分析して、分岐のための分岐予測関数を構築するようになっている。
【００４６】
分岐予測インストラクション・ジェネレータ２２６は、分岐統計データ・アナライザ２２４から分岐予測関数を受け取る。次いで、分岐予測インストラクション・ジェネレータ２２６は、各予測関数に対して予測インストラクションを生成する。予測インストラクションは、予測関数を計算して予測値を得る。次いで、予測インストラクションは、この予測値をプロセッサ１０２に伝達する。
【００４７】
分岐予測インストラクション・ジェネレータ２２６は、例えば、予測関数を計算して分岐の予測値を得るための第１の予測インストラクションと、予測値をプロセッサ１０２に伝達するための第２のインストラクションを生成する。第１のインストラクションは、コンペア・トゥ・プレディケート（述語比較）・インストラクションであり、また、第２のインストラクションは、プリペア・トゥ・ブランチ（分岐準備）・インストラクションでよい。あるいは、分岐予測インストラクション・ジェネレータ２２６は、予測関数の計算及びプロセッサ１０２への予測値の伝達の双方を行うための単一のインストラクションを生成するだけでもよい。
【００４８】
分岐予測インストラクション・ジェネレータ２２６が一旦予測インストラクションを生成すると、主コンパイラ・エンジン２２２は、コンパイルされたコード中にこれらインストラクションを挿入することができる。１つの実施態様では、ある分岐についての予測インストラクションは、該分岐の大凡１６サイクルだけ手前に置かれる。他の実施態様では、ある分岐についての予測インストラクションは、該分岐の大凡３２サイクルだけ手前に置かれる。あるいは、分岐の１乃至６４サイクルだけ手前にインストラクションを置いてもよい。
【００４９】
１つの実施態様では、コンパイラ２００によるコンパイラ合成式動的分岐予測は、プログラム中の各々の分岐インストラクションを処理するために用いられる。他の実施態様では、コンパイラ２００によるコンパイラ合成式動的分岐予測は、プログラム中の分岐インストラクションのうちで選択された幾つかのもののみを処理するために用いられる。このことによってプログラムの長さが縮小され、以てプログラムを格納するために必要なメモリ容量を低減することができる。
【００５０】
コンパイラ合成式動的分岐予測に関連したコンパイラ２００の動作特性を、以下に詳細に記述する。動作の間、ソース・コードはまずコンパイラ２００の主コンパイラ・エンジン２２２に適用される。このときには、分岐統計データを全く利用できないので、主コンパイラ・エンジン２２２は、分岐予測関数をデフォルト状態に設定するとともに、ソース・コードを機械コードにコンパイルすることしか行わない。このことをプレ・コンパイルと呼ぶ。プレ・コンパイルの間、主コンパイラ・エンジン２２２は、計測コードをコンパイルされたコード（すなわち機械コード）中に挿入して、サンプル入力データによって機械コードが実行されるときに分岐統計データを収集する。このことは、既知のコンパイル手段を用いて実現可能である。
【００５１】
上述したように、分岐の分岐統計データは、分岐方向情報（すなわち分岐プロファイル情報）と、特定マシン・サイクル数だけ分岐の実行より手前におけるプロセッサ１０２のレジスタ内容を含んでいる。各分岐において、分岐プロファイル情報とは各々の分岐を実行したときの分岐方向の記録のことである。レジスタ・ダンプ情報とは、分岐に対して所定間隔だけ手前におけるレジスタ・ファイルのダンプのことである。これらレジスタ値は、予測を計算する実行時間において利用可能である。
【００５２】
プレ・コンパイルを行った後、サンプル入力データを用いて機械コードを図４のプロセッサ１０２で数回実行して、各分岐についての分岐統計データを収集する。これによって、各分岐について、分岐プロファイル情報とレジスタ・ダンプ情報（すなわち分岐統計データ）が生成される。図１３には、レジスタ・ダンプ情報の例が示されている。但し、図１３は、図解する目的で、２レジスタ式プロセッサについてのレジスタ・ダンプを示しているに過ぎない。
【００５３】
次いで、分岐統計データがアナライザ２２４に適用されて分析され、分岐方向とプロセッサ１０２のレジスタ内容との相関関係が識別される。この分析に基づいて、アナライザ２２４は、各分岐について予測関数を構築する。次いで、全ての分岐についての予測関数が分岐予測インストラクション・ジェネレータ２２６に適用されて、予測関数を計算するための予測インストラクションが生成される。次いで、主コンパイラ・エンジン２２２からの要求に応じて、これらインストラクションが主コンパイラ・エンジン２２２に適用される。
【００５４】
次いで、ソース・コードが再び主コンパイラ・エンジン２２２に適用されてコンパイルされる。このときには、アナライザ２２４は分岐統計データを利用可能となっているので、主コンパイラ・エンジン２２２は、ライン２３０経由で、分岐予測インストラクション・ジェネレータ２２４に対して分岐についての予測インストラクションを問い合わせる。次いで、主コンパイラ・エンジン２２２は、予測関数のための予測インストラクションを、ソース・コードの中間コードに挿入する。次いで、エンジン２２２は、中間コードを再スケジュールして、最終的な機械コードを生成する。
【００５５】
１つの実施態様では、ソース・コードがコンパイルのために再び主コンパイラ・エンジン２２２に適用される前に、分岐統計データが分岐統計データ・アナライザ２２４に適用される。他の実施態様では、ソース・コードがコンパイルのために再び主コンパイラ・エンジン２２２に適用されるときとほとんど同時点に、分岐統計データが分岐統計データ・アナライザ２２４に適用される。
【００５６】
図７は、分岐統計データ・アナライザ２２４によって実行される１つの基本ルーチンを示している。このルーチンは、本発明の１つの実施態様に従って、レジスタ内容を分析して、ある単一の分岐についての分岐予測関数を構築するためのものである。上述したように、分岐についての予測関数は合成されており、プロセッサ１０２のアーキテクチャ・レジスタに格納された値と分岐の方向とを関連付けている。この基本ルーチンは、予測関数が複雑でありえることを前提として、資源無限という環境下に置かれている。図８には、分岐統計データ・アナライザ２２４によって実行される実用的ルーチンを示しているが、このルーチンは、単一の分岐についての分岐予測関数を構築するためにレジスタ内容を分析するものである。実用的ルーチンは、現実のいかなる予測も幾つかのインストラクションだけで構成するように制限されるという事実を考慮に入れて、基本ルーチンを簡素化して実用的なものにしたバージョンである。そうしなければ、予測関数を評価するためのコストが、予測精度の向上によって享受される利益よりも大きくなってしまうであろう。
【００５７】
図７から分かるように、基本ルーチンは、せいぜい２個のレジスタにしか基づかない予測関数を構築するように自らを限定している。該ルーチンでは、予測関数は、分岐の所定サイクル数だけ手前の時点で、２個のレジスタの値を用いて分岐述語を予測するようになっている。ここで、レジスタ数の限定はこのルーチンにとって本質的ではなく、実用主義的な利益にのみ依拠するものである。この限定とは別に、図７に示した基本ルーチンは、リソースの束縛（すなわち、プロセッサ中にはｎ個のレジスタｒ1，ｒ2，…，ｒnがあるということ）について何ら注意を払っていない。このルーチンが分岐ｂを処理し、分岐述語値が分岐レジスタｒb中にあると仮定する。分岐を実行する場合において、ν1，ν2，…，νnは分岐ｂの固定サイクル数だけ前の時点におけるプロセッサ１０２のレジスタ値を表すものとし、また、νbは実行中に評価が終わった時点における分岐述語値を表すものとする。言い換えれば、ν1，ν2，…，νnとνbは、分岐の特定パスについてのレジスタ・ダンプのエントリを構成しており、レジスタｒ1−ｒnについての値ν1−νnが分岐の固定サイクル数だけ手前の時点のものであり、分岐述語レジスタｒbの値νbは分岐直後のものである。
【００５８】
該ルーチンは、整数値アレイを保有している。すなわち、レジスタｒiについてはＣiが用意され、一組のレジスタｒi及びｒjの各々にはＣi,jが用意される。各値ｒiには１つのエントリＣiがあり、また、組み合わせが可能な値ｒi及びｒjの各々には１つのエントリＣi,jがある。これは、実行不可能な要求であるが、単に解説を明確にする目的である。図８には、実用的なルーチンを示しているが、これは実用的なリソースの束縛を勘案して図７に示した基本ルーチンを修正したものである。
【００５９】
アレイ中の全てのエントリはゼロに初期化される。分岐ｂを抜けるパスの各々において、もし分岐述語が真（すなわちνbが値１を持つ）と評価したならば、アレイ・エントリはインクリメントされる。特に、もしレジスタｒiが値νiを持つならば、エントリＣi［νi］はインクリメントされる。同様に、一組のレジスタｉ及びｊの場合には、Ｃi,j［νi］［νj］はインクリメントされる。もし、分岐述語が偽（すなわちνbが値０を持つ）と評価したならば、対応するアレイ・エントリはデクリメントされる。本質的には、アレイ中のエントリは、分岐予測のためにレジスタ値を知ることの有用性を概算するものである。もし、レジスタｒiが所与の値νであることに対して、分岐述語がほとんどの場合に真と評価するならば、アレイ・エントリＣi［ν］は必ずや正数となるであろう。逆に、ほとんどの場合に分岐述語が偽と評価するならば、アレイ・エントリＣi［νz］は必ずや負数となろう。もし分岐述語が真偽の各々に均一に分散しているならば、Ｃi［ν］はゼロに近い値であろう。
【００６０】
分岐を抜ける全てのパスについて処理した後、アレイ・エントリの絶対値が総和される。各レジスタｒiの総和にはスコアＳiが割り当てられ、また、各一組のレジスタｒi及びｒjの総和にはスコアＳi,jが割り当てられる。高いスコアを持つレジスタ若しくは一組のレジスタが、分岐についての最良の予測ということになる。
【００６１】
一旦、最高のスコアを持つレジスタ若しくはレジスタの組み合わせが選び出されると、予測関数の構築に直進する。ここで、ある単一のレジスタｒkが最高のスコアであったと仮定する。ｒkを含む予測関数は、ｒkについての値をνkとして、アレイ・エントリＣk［νk］が正数かどうかをチェックする。もし正数であれば、分岐は"１"と予測され、そうでなければ分岐は"０"と予測される。もし、一組のレジスタｒl及びｒmが最高のスコアを持っていれば、予測関数は同様であろう。もし、Ｃl,m［νl］［νm］が正数であれば、分岐述語は"１"と予測され、そうでなければ"０"と予測される。
【００６２】
図７に示した基本ルーチンの動作を説明するために、ここで、プロセッサ１０２が２個のレジスタｒ1及びｒ2と、１個の分岐レジスタｒbを有する場合について考察してみる。あるプログラムにおけるサンプル実行を想定して、特定の分岐が７回実行された。図１３にはこれら７個のパスについてのレジスタ・ダンプを示しているが、ｒ1及びｒ2の値はｒbよりも１６サイクルだけ手前の時点でのものとする。
【００６３】
基本ルーチンを適用することによって、アレイ・エントリについて以下の値が得られる。
【００６４】
【数１】
Ｃ1［１７］＝３；Ｃ1［１９］＝−２；
Ｃ1［１３］＝１；Ｃ1［１４］＝−１；
Ｃ2［１５］＝０；Ｃ2［１２］＝２；
Ｃ2［０］＝−１；Ｃ2［８］＝０；
Ｃ1,2［１７］［１５］＝１；Ｃ1,2［１７］［１２］＝１；
Ｃ1,2［１９］［１５］＝−１；
Ｃ1,2［１３］［１２］＝１；Ｃ1,2［１４］［０］＝−１；
Ｃ1,2［１９］［８］＝−１；Ｃ1,2［１７］［８］＝１；
【００６５】
上記のアレイ値から、Ｓ1＝７，Ｓ2＝３，及びＳ1,2＝７となる。Ｓ1，Ｓ2，及びＳ1,2の中ではＳ1が最大となるので、図７に示すルーチンによって、図６に示すアナライザ２２４は、ｒ1に基づいた１個のレジスタの予測関数を出力する。予測関数は、以下のように簡単な形式で示される。
【００６６】
【数２】
ｉｆ  ν1＝１７  ｏｒ  ν1＝１３  ｔｈｅｎ  ｐｒｅｄｉｃｔ  １
ｅｌｓｅ  ｐｒｅｄｉｃｔ  ０
【００６７】
図８には、図７に示した基本ルーチンについてレジスタ値のレンジを縮小した実用的ルーチンが示されている。図８に示した実用的ルーチンは、２つの例外を除いては、図７に示した基本ルーチンと全く同様に動作する。まず第１に、量子化されたレジスタ値を用いてアレイＣi及びＣi,jが構築される。第２に、１−比較予測（ｏｎｅ−ｃｏｍｐａｒｅ  ｐｒｅｄｉｃｔｏｒ）によって、スコアＳi及びＳi,jが計算される。とりわけ、図８に示した実用的ルーチンによれば、各アレイＣiについてｒiの値を最適に区分するためのカットポイントν*を見つけだす。但し、ν*未満の全ての値について真（又は偽）であり他の全ての値について偽（又は真）である、という分岐述語を予測することは全てのカットポイントよりも最適であることとする。同様に、各アレイＣi,jについて、該ルーチンは、レジスタｒi及びｒjの値の最適な矩形的区画を生じるカットポイント（ｕ*，ν*）を見つけだす。
【００６８】
図８に示した実用的ルーチンを図１３の例に適用することによって、同様にＣ1，Ｃ2，及びＣ1,2を得ることができる。そして、スコアＳ1，Ｓ2，及びＳ1,2が計算される。ｒ1については、スコアＳ1＝５を生じるν*＝１８が最良のカットポイントである。ｒ2については、スコアＳ2＝３を生じるν*＝１が最良のカットポイントである。一組のレジスタｒ1、ｒ2については、スコアＳ1,2＝７を持つｕ*＝１８及びｖ*＝１が最良のカットポイントである。Ｓ1,2はこれらのスコアのうちで最大なので、アナライザ２２４は、図８に示すルーチンによって、ｒ1とｒ2に基づいた２−レジスタ／−２比較予測関数を出力する。予測関数は、以下のように簡単な形式で示される。
【００６９】
【数３】
Ｔｗｏ−ｒｅｇｉｓｔｅｒ／Ｔｗｏ−ｃｏｍｐａｒｅ  ｐｒｅｄｉｃｔｏｒ
ｂａｓｅｄ  ｏｎ  ｒ1  ，ｒ2
ｉｆ  ν1＜１８，ν2≧１  ｔｈｅｎ  ｐｒｅｄｉｃｔ  "１"
ｅｌｓｅ  ｐｒｅｄｉｃｔ  "０"
【００７０】
図９には、図６に示した分岐予測インストラクション・ジェネレータ２２６の処理に係るフローチャート・ダイアグラムを示している。図９から分かるように、該処理はステップ２６０で始まる。ステップ２６１では、ジェネレータ２２６は、分岐についての分岐予測関数を受け取る。ステップ２６２では、予測関数は、１つ又はそれ以上の予測インストラクションによって表される。これらのインストラクションは、予測関数を計算するのに用いられる。
【００７１】
ステップ２６３は、処理のためにさらに予測関数が必要か否かを決定する判断ステップである。もし答えがイエスであれば、ステップ２６１が繰り返される。もし答えがノーであれば、該処理は２６４で終了する。
【００７２】
図１０には、図６に示した主コンパイラ・エンジン２２２が分岐インストラクションを処理するときのフローチャートを示している。図１０から分かるように、ステップ２８３では、受け取ったインストラクションが分岐インストラクションでないか否かが判断される。もしインストラクションが分岐インストラクションでなければ、該処理はステップ２８１に復帰する。ステップ２８４では、主コンパイラ・エンジン２２２は、予測インストラクションを分岐インストラクションの前に挿入すべきかどうかを、分岐予測インストラクション・ジェネレータ２２６に問い合わせる。ステップ２８５では、エンジン２２２は、分岐についての予測関数を計算するために、これらのインストラクションをプログラム中に挿入する。ステップ２８６では、エンジン２２２は、さらにインストラクションを処理すべきかどうかを判断する。もし、さらに処理すべきならば、該処理はステップ２８２に復帰する。もはや処理すべきでないならば、該処理はステップ２８６で終了する。
【００７３】
本発明の１つの実施態様に従ったコンパイラ合成式動的分岐予測手法の有効性は、図１１及び１２に示してある。図１１乃至１２では、コンパイラ合成式動的分岐予測手法を用いた種々のベンチマーク・コードによる予測誤り発生率が、従来の静的及び動的な分岐予測手法を用いた同種のコードによる場合のそれと比較されている。図１１には、コンパイラ合成式動的分岐予測手法の総体的なパフォーマンスが、他の一般的な分岐予測手法と比較して示されている。コンパイラ合成式動的分岐予測手法は選択された分岐のサブセットにしか適用されておらず、残りの分岐は従来の静的予測によって扱われている、という点に留意すべきである。図１２は図１１と同様であるが、コンパイラ合成式分岐予測手法によって処理された分岐を越えた種々の予測のパフォーマンスを比較したものである。
【００７４】
図１１乃至１２から分かるように、コンパイラ合成式動的分岐予測を用いた全てのコードについての予測誤り発生率は、いかなる従来手法のものよりも低い。
【００７５】
あるいは、上述したコンパイラ合成式動的分岐予測機能は、他の手段によっても実現することができる。例えば、合成式動的分岐予測機能は、ハードウェア及び／又はマイクロコードによって実現することができる。例えば、図１４と１５には、これについての１つの実施態様を示している。図１４から分かるように、機械コード４０１と分岐統計データ４０３は実行時間分岐予測シンセサイザ４００に入力され、ここで修正機械コード４０２が生成され、該コードはプロゼッサ１０２によって実行される。シンセサイザ４００は、ハードウェアによって実装される。図１５は、シンセサイザ４００の構造を示しているが、これは分岐統計データ・アナライザ４２４や分岐予測インストラクション・ジェネレータ４２６に加えて実行時間コード・マネージャ４２２を含んでいる。アナライザ４２４やジェネレータ４２６の機能は、図６で示したアナライザ２２４及びジェネレータ２２６のそれと同一である。実行時間コード・マネージャ４２２は、ジェネレータ４２６から生成された予測インストラクションを挿入するようになっている。
【００７６】
先の明細書では、特定の実施態様を参酌しながら本発明について記述してきた。しかしながら、本発明の要旨や範囲を逸脱したり拡大したりすることなくこの特定の実施態様に対して種々の修正や変更を行えるということは、当業者にとっては明白である。したがって、この明細書や図面等を限定的ではなく解説的な意味で把握すべきである。
【００７７】
本発明は、例として次の実施態様を含む。
１．（Ａ）分岐インストラクションの分岐統計データを分析して分岐インストラクションのための分岐予測関数を構築する分岐統計データ・アナライザと、（Ｂ）分岐統計データ・アナライザに接続されて、分岐予測関数を実現するための予測インストラクションを少なくとも１つ生成する分岐予測インストラクション・ジェネレータと、（Ｃ）分岐予測インストラクション・ジェネレータに接続されて、分岐インストラクションの前に予測インストラクションを挿入するための主コンパイル・エンジンと、を具備するコンパイラ。
２．１のコンパイラにおいて、分岐統計データには分岐プロファイル情報とレジスタ・ダンプ情報が含まれる。
【００７８】
３．上記２のコンパイラにおいて、分岐統計データ・アナライザは、分岐プロファイル情報とレジスタ・ダンプ情報を分析して、分岐方向とレジスタ内容との相関を識別することによって、分岐予測関数を構築してもよい。
【００７９】
４．上記３のコンパイラにおける分岐予測関数は、少なくとも１つのレジスタ内容と分岐インストラクションの分岐方向とを関連付けるものであってもよい。
【００８０】
５．また、上記４のコンパイラにおける分岐予測インストラクション・ジェネレータは、分岐インストラクションの分岐行先アドレスを指定するプリペア・トゥ・ブランチ・インストラクションと、レジスタ内容を分岐予測関数によって指定された閾値と比較するコンペア・インストラクションを発生してもよい。
【００８１】
６．また、上記１のコンパイラにおける主コンパイラ・エンジンは、分岐統計データ・アナライザに接続されて、分岐インストラクションをコンパイルする前に、分岐統計データ・アナライザ内で分岐統計データが使用可能かどうかを判断してもよい。分岐統計データ・アナライザにとって分岐統計データは使用可能でないと主コンパイラ・エンジンが判断したときには、主コンパイラ・エンジンは、分岐インストラクションを含むソース・コードをコンパイルするときにはいかなるインストラクションも挿入しない。
【００８２】
７．また、上記１のコンパイラにおいて、挿入される予測インストラクションは、分岐インストラクションよりも１乃至６４サイクルだけ手前に置かれる。
【００８３】
８．また、本発明の他の実施態様は、プログラム中の分岐インストラクションを動的に予測する方法であって、（Ａ）分岐インストラクションについての分岐予測関数を構築するために、分岐インストラクションの分岐統計データを分析するステップ、（Ｂ）分岐予測関数を実現するための予測インストラクションを少なくとも１つ生成するステップ、（Ｃ）分岐インストラクションの前に予測インストラクションを挿入する挿入するステップ、の各ステップを具備するものである。
【００８４】
９．上記８の方法において、分岐統計データは、分岐プロファイル情報と、レジスタ・ダンプ情報を含んでいてもよい。
【００８５】
１０．また、上記９の方法における分析するステップは、さらに、（ｉ）分岐インストラクションについての分岐プロファイル情報とレジスタ・ダンプ情報を分析して、分岐方向とレジスタ内容との相関を識別するステップ、（ｉｉ）分岐方向とレジスタ内容との相関に基づいた分岐予測関数を発生するステップの各ステップで構成されていてもよい。
【００８６】
１１．また、上記１０において、ステップ（ｉ）は、さらに、（ａ）各分岐インストラクションの実行よりも数回手前における各レジスタの内容を判別するステップ、（ｂ）各分岐インストラクションの実行における分岐方向を判別するステップ、（ｃ）どのレジスタがどういう内容の値のときに分岐インストラクションが分岐するかを判別することによって、分岐方向とレジスタ内容の間の相関を確立するステップ、の各ステップで構成されていてもよい。
【００８７】
１２．また、上記８の方法における生成するステップでは、分岐予測関数を実現するコンペア・インストラクションと、分岐予測関数を受け取ったことに応答して分岐インストラクションの行先アドレスを指定するプリペア・トゥ・ブランチ・インストラクションを生成してもよい。
【００８８】
１３．また、上記８の方法は、さらにステップ（Ｄ）として、ステップ（Ｃ）よりも前に、分岐統計データが分岐統計データ・アナライザ内で使用可能かどうかを判別するステップ、および（Ｅ）分岐統計データが分岐統計データ・アナライザにとって使用可能でないならば、分岐インストラクションを含んだソース・コードをコンパイルするときには、ステップ（Ｃ）を実行しない、の各ステップを具備していてもよい。
【００８９】
１４．また、本発明の他の実施態様は、（Ａ）記憶媒体と、（Ｂ）該記憶媒体に格納された、コンピュータ上で実行可能なコンパイラ・プログラムと、を具備した装置である。このコンピュータ上で実行可能なコンパイラ・プログラムは、さらに、（ａ）分岐インストラクションについての分岐統計データを分析して、分岐インストラクションについての分岐予測関数を得る第１のインストラクション・セットと、（ｂ）分岐予測関数を実現するための予測インストラクションを少なくとも１つ生成する第２のインストラクション・セットと、（ｃ）分岐インストラクションを含んだソース・コードを機械コードにコンパイルするときには、分岐インストラクションの前に予測インストラクションを挿入する第３のインストラクション・セットと、を備えている。
【００９０】
１５．上記１４の装置において、分岐統計データは、分岐プロファイル情報と、レジスタ・ダンプ情報を含んでいてもよい。
【００９１】
１６．また、上記１５の装置において、第１のインストラクション・セットは、さらに、（ｉ）分岐インストラクションについての分岐プロファイル情報とレジスタ・ダンプ情報を分析して、分岐方向とレジスタ内容との相関を識別する第１のインストラクション・サブセットと、（ｉｉ）分岐方向とレジスタ内容との相関に基づいて、分岐予測関数を生成する第２のインストラクション・サブセットと、を備えていてもよい。
【００９２】
１７．また、上記１６の装置において、第１のインストラクション・サブセットは、（ａ）各分岐インストラクションの実行よりも数回手前における各レジスタの内容を判別し、（ｂ）各分岐インストラクションの実行における分岐方向を判別し、（ｃ）どのレジスタがどのような内容の値をとるときに分岐インストラクションが分岐するかを判別することによって、分岐方向とレジスタ内容の間の相関を確立する、ことによって、分岐インストラクションについての分岐プロファイル情報とレジスタ・ダンプ情報を分析してもよい。
【００９３】
１８．また、上記１４の装置において、第２のインストラクション・セットは、分岐予測関数を実現するコンペア・インストラクションと、分岐予測関数を受け取ったことに応答して分岐インストラクションの分岐行先アドレスを指定するプリペア・トゥ・ブランチ・インストラクションを生成してもよい。
【００９４】
１９．また、上記１５の装置は、さらに、（Ｄ）分岐インストラクションを含んだソース・コードをコンパイルする前に、分岐統計データ・アナライザ内で分岐統計データが使用可能かどうかを判別する第４のインストラクション・セットと、（Ｅ）分岐統計データが使用可能でないときには、第３のインストラクション・セットが予測インストラクションを挿入しないようにする第５のインストラクション・セットと、を備えていてもよい。
【００９５】
２０．また、上記１４の装置において、挿入される予測インストラクションは、分岐インストラクションよりも１乃至６４サイクルだけ手前に置かれてもよい。
【００９６】
２１．また、本発明の他の実施態様は、（Ａ）分岐インストラクションの分岐統計データを分析して、分岐インストラクションについての分岐予測関数を構築する分岐統計データ・アナライザと、（Ｂ）分岐統計データ・アナライザに接続されて、分岐予測関数を実現するための予測インストラクションを少なくとも１つ生成する分岐予測インストラクション・ジェネレータと、（Ｃ）分岐予測インストラクション・ジェネレータに接続されて、予測インストラクションを分岐インストラクションの前に挿入する実行時間コード・マネージャと、を具備することを特徴とする実行時間分岐予測シンセサイザである。
【００９７】
２２．上記２１の実行時間分岐予測シンセサイザにおいて、分岐統計データは分岐プロファイル情報とレジスタ・ダンプ情報を含んでもよい。この場合、分岐統計データ・アナライザは、分岐プロファイル情報とレジスタ・ダンプ情報を分析して、分岐方向とレジスタ内容との相関を識別することによって、分岐予測関数を構築してもよい。
【００９８】
２３．また、上記２２の実行時間分岐予測シンセサイザにおいて、分岐予測関数は少なくとも１つのレジスタ内容を分岐インストラクションの分岐方向と関連付けてもよい。この場合、分岐予測インストラクション・ジェネレータは、分岐インストラクションの分岐行先アドレスを指定するプリペア・トゥ・ブランチ・インストラクションと、レジスタ内容を分岐予測関数によって指定された閾値と比較するコンペア・インストラクションを生成してもよい。
【００９９】
【発明の効果】
以上詳記したように本発明によれば、分岐インストラクションによって生じるパイプラインの破壊を最小限に抑えることができる分岐予測を提供することができる。
【０１００】
また、本発明によれば、最大限の精度と最小限のコストを以て分岐予測を最適化することができる。
【０１０１】
また、本発明によれば、コスト効果がありしかも比較的精度のよい合成式動的分岐予測機能を提供することができる。
【図面の簡単な説明】
【図１】  静的分岐予測における分岐インストラクションのインストラクション・フォーマットを示した図である。
【図２】  プロファイル情報を利用した従来技術に係る静的分岐予測手法の処理を図解した状態遷移図である。
【図３】  従来技術に係る動的分岐手法を示した図である。
【図４】  プリペア・トゥ・ブランチ式インストラクションをサポートしたプロセッサを含んだコンピュータ・システムを示した図である。
【図５】  図４に示したコンピュータ・システムのための、本発明の１つの実施態様に従ったコンパイラ合成式の動的分岐予測機能を備えたコンパイラ・プログラムを示した図である。
【図６】  分岐統計データ・アナライザと分岐予測インストラクション・ジェネレータを含んだ図５に示したコンパイラの構造を示した図である。
【図７】  図６に示した分岐統計データ・アナライザによって実行されるルーチンを示した図である。
【図８】  図６に示した分岐統計データ・アナライザによって実行される他のルーチンを示した図である。
【図９】  分岐予測インストラクション・ジェネレータによる処理を示したフローチャート・ダイアグラムである。
【図１０】  図６で示したコンパイラの主コンパイル・エンジンによる処理を示したフローチャート・ダイアグラムである。
【図１１】  静的分岐予測、動的分岐予測、及びコンパイラ合成式動的予測手法における分岐予測誤り発生率の比較表を示した図である。
【図１２】  静的分岐予測、動的分岐予測、及びコンパイラ合成式動的予測手法における分岐予測誤り発生率の比較表を示した他の図である。
【図１３】  分岐の７個のパスについてのレジスタ・ダンプ表を示した図である。
【図１４】  図４に示したコンピュータ・システムのための、本発明の他の実施態様に係る実行時間分岐予測シンセサイザを示した図である。
【図１５】  図５に示した実行時間分岐予測シンセサイザの構造を示した図である。
【符号の説明】
１００…コンピュータ・システム、１０１…バス、１０２…プロセッサ、
１０４…メモリ、１０７…大容量記憶装置、１２１…ディスプレイ、
１２２…キーボード、１２３…ポインティング・デバイス、
１２４…ハード・コピー装置、１２５…その他の周辺機器、
２２２…主コンパイラ・エンジン、２２４…分岐統計データ・アナライザ、
２２６…分岐予測インストラクション・ジェネレータ、
４２２…実行時間コード・マネージャ、
４２４…分岐統計データ・アナライザ、
４２６…分岐予測インストラクション・ジェネレータ
【図１】
0003819572.tif 000002
【図２】
0003819572.tif 000003
【図３】
0003819572.tif 000004
【図４】
0003819572.tif 000005
【図５】
0003819572.tif 000006
【図６】
0003819572.tif 000007
【図７】
0003819572.tif 000008
【図８】
0003819572.tif 000009
【図９】
0003819572.tif 000010
【図１０】
0003819572.tif 000011
【図１１】
0003819572.tif 000012
【図１２】
0003819572.tif 000013
【図１３】
0003819572.tif 000014
【図１４】
0003819572.tif 000015
【図１５】
0003819572.tif 000016