(57)【特許請求の範囲】
【請求項１】
ループ回数の特定されている条件分岐命令を探索して挿入されたループ終了判定条件分岐命令及びその他の条件分岐命令の次に実行される命令を予測してその命令を予め読み込む分岐予測装置において、前記ループ終了判定条件分岐命令及びその他の条件分岐命令のアドレス及びその分岐先が記録されている分岐先アドレステーブルと、前記その他の条件分岐命令が以前の実行の際に分岐を行ったかどうかを示す履歴が記録されている分岐履歴テーブルと、前記ループ終了判定条件分岐命令が実行されたときにループカウンタレジスタの値からヒントを取得するヒント取得手段と、前記ヒント取得手段により取得したヒントを格納するヒント格納手段と、前記ループ終了判定条件分岐命令のアドレスが出力された場合には、前記ヒント格納手段から出力されるヒントと前記分岐先アドレステーブルから出力される分岐先アドレスに従ってループ終了判定条件分岐命令の次に実行が予測される命令を読み込み、前記その他の条件分岐命令のアドレスが出力された場合には、分岐履歴テーブルから出力される履歴と前記分岐先アドレステーブルから出力される分岐先アドレスに従って条件分岐命令の次に実行が予測される命令を読み込む命令読み込み手段とを備えることを特徴とする分岐予測装置。
【請求項２】
ループ終了判定条件分岐命令の実行時にヒントを取得するか否かを制御する情報を条件分岐命令形式で保持することを特徴とする請求項１に記載された分岐予測装置。
【請求項３】
前記ヒント取得手段は、ループ終了判定条件分岐命令を実行する際にループ終了の１回前かどうかを調べることにより次の繰り返しでループを終了するかどうかを判定することを特徴とする請求項１または請求項２のいずれかに記載された分岐予測装置。
【請求項４】
前記ヒント取得手段は、ループ繰り返し回数を格納したレジスタの値を調べることによりループを終了するかどうかを判定することを特徴とする請求項１乃至請求項３のいずれか１項に記載された分岐予測装置。
【請求項５】
前記ヒント格納手段は、ループ終了を判定する各条件分岐命令に対応するヒントビットフィールドを有し、前記ヒントビットフィールドに当該条件分岐命令の実行により分岐が行われるかどうかを示すヒントを格納することを特徴とする請求項１乃至請求項４のいずれか１項に記載された分岐予測装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、分岐命令の分岐の有無を予測する分岐予測装置に関し、特に、ループ処理を繰り返すかどうかを判定する条件分岐命令で分岐が行われるかどうかを予測する分岐予測装置に適用して有効な技術に関するものである。
【０００２】
【従来の技術】
近年のマイクロプロセッサの速度向上には目覚しいものがあり、これらのマイクロプロセッサでは、深いパイプライン実行、ｏｕｔ  ｏｆ  ｏｒｄｅｒ  実行、キャッシュメモリを採用することが一般的になっている。これらの技術は効果的であるが、以下の様な場合に性能が低下する。
【０００３】
すなわち、パイプライン、ｏｕｔ  ｏｆ  ｏｒｄｅｒ  実行は、連続した命令列の実行を行う場合には有効であるが、条件分岐命令によって連続性が失われた場合に大きなペナルティを課せられるものが多くなっている。よって、条件分岐命令により分岐が発生した場合には性能が低下する。
【０００４】
また、キャッシュメモリによる高速化は、プログラム内でキャッシュメモリ内に含まれない命令への参照が起こった場合、インストラクションキャッシュミスが発生し、速度低下の原因となる。
【０００５】
この為、最近では条件分岐命令によって分岐を行うかどうかを予測する機構を持つことが主流となっている。なかでも「Ｔｓｅ−Ｙｕ  Ｙｅｈ  ａｎｄ  Ｙａｌｅ  Ｎ．  Ｐａｔｔ  ”Ｔｗｏ−Ｌｅｖｅｌ  Ａｄａｐｔｉｖｅ  Ｔｒａｉｎｉｎｇ  Ｂｒａｎｃｈ  Ｐｒｅｄｉｃｔｉｏｎ”、  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２４ｔｈ  Ａｎｎｕａｌ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｍｉｃｒｏａｒｃｈｉｔｅｃｔｕｒｅ、  １９９１、  ｐｐ．５１−６１」に示される様な、条件分岐命令毎に分岐を行ったかどうかを記録する分岐情報テーブルを持ち（以降、過去の分岐を行ったかどうかを示す記録のことを、分岐履歴情報と呼ぶ）、その記録に基づいて次回その条件分岐命令を実行した時に分岐を行うかどうかを予測する方法が、その予測の正確さから多く用いられている。
【０００６】
【発明が解決しようとする課題】
前記論文に示される方法では、分岐履歴情報には高々数回前までの履歴しか記録されていない為、何回かある分岐先アドレスに分岐した後、１回だけ分岐せずに次の命令を実行するという動作をする条件分岐命令の実行結果の予測を行うのは困難であるという問題がある。
【０００７】
この様な動作は、プログラム中に含まれるループの部分においてループを繰り返すかどうかを判定する条件分岐命令に多く見られ、この様な条件分岐命令では、ループを繰り返した後に終了する際の分岐が予測困難な分岐にあたり、ループを終了する場合の予測は常に外れてしまう。
【０００８】
本発明の目的は、上記問題を解決し、ループ終了判定を行う条件分岐命令のループ終了時の分岐を正確に予測することが可能な技術を提供することにある。
【０００９】
【課題を解決するための手段】
本発明は、条件分岐命令の次に実行される命令を予測してその命令を予め読み込む分岐予測装置において、ループ終了を判定する条件分岐命令の実行により分岐が行われるかどうかを示すヒントの取得して、そのヒントに従って条件分岐命令の次に実行が予測される命令を読み込むものである。
【００１０】
本発明では通常の分岐履歴情報による分岐予測機構以外に、ループ終了を判定する条件分岐命令の実行により分岐が行われるかどうかを示すヒントの取得を制御するヒント取得制御手段と、あるレジスタ、例えばループカウンタレジスタ（以後ＣＴＲと呼ぶ）の値によって分岐を行うかどうかを示すヒントを取得するヒント取得手段と、前記ヒントを格納するヒント格納手段と、前記ヒントに従って条件分岐命令の次に実行が予測される命令を読み込む命令読み込み手段とを用意し、これらを用いることによりループ終了判定を行う条件分岐命令で分岐を行うかどうかの予測を正確に行う。
【００１１】
ヒント取得制御手段は、条件分岐命令が分岐を行うかどうかの予測として、前記ヒントの値を用いるか若しくは通常の分岐履歴情報による分岐予測機構による予測結果を利用するかをコンパイル時に決定して指定するものであり、この指定により、ループ終了判定を行う条件分岐命令によってループ終了時の分岐を行うかどうかの予測を正確に行う。
【００１２】
ＣＴＲは、プログラム中のループ開始時に特定の値に設定され、ループの繰り返し動作中にその値が更新されるものとし、ＣＴＲが特定の条件を満たす値になった場合にループを終了するものとする。
【００１３】
ヒント取得手段は、ループ終了判定を行う条件分岐命令で分岐を行うかどうかの予測をＣＴＲの値によって行い、予測の結果をヒント格納手段である分岐ヒントテーブルにヒントビットとして記録しておく。
【００１４】
ループ回数がループ開始時に判っているループの場合、例えばループ開始時にＣＴＲにループ回数の値が設定され、ループする為の条件分岐命令を実行する度にＣＴＲの値が減じられてゆき、ループ終了時にはＣＴＲが０となる場合を考える。
【００１５】
この時、例えば以下の様なＣＴＲの値の変化に注目して予測を行い、ヒントビットの値を決定することができる。
【００１６】
・ＣＴＲの値が１より大きかった場合、次回ループ終了判定条件分岐命令の実行時にはＣＴＲが０にならない為、ループを繰り返す命令アドレスへ制御が移ると予測することができる。
【００１７】
・ＣＴＲの値が１であった場合、次回ループ終了判定条件分岐命令の実行時にはＣＴＲが０になりループを終了する命令アドレスへ制御が移ると予測することができる。
【００１８】
この例でＣＴＲの値が１であった場合、ヒント取得手段は、次回ループ終了判定条件分岐命令の実行時にはループを終了する命令アドレスへ制御が移ると予測して、分岐ヒントテーブルのヒントビットにループを終了することを示すヒントを記録する。
【００１９】
命令読み込み手段は、分岐ヒントテーブルのヒントビットの値に従って、ループ終了判定を行う条件分岐命令の次に実行される命令を読み込む。
【００２０】
前記の様に、ループ終了判定を行う条件分岐命令で分岐が行われるかどうかを予測することにより、例えばループ終了時に必ず生じていた分岐予測ミスによるパイプラインストールによる遅延を削減することができ、これにより計算機プログラムの実行を高速化させることが可能である。
【００２１】
以上の様に、本発明の分岐予測装置によれば、ループ繰り返し回数の値によりループ終了判定を行う条件分岐命令で分岐を行うかどうかを予測するので、ループ終了判定を行う条件分岐命令のループ終了時の分岐を正確に予測することが可能である。
【００２２】
【発明の実施の形態】
以下に、ループ繰り返し回数に応じてループ終了を判定する条件分岐命令で分岐を行うかどうかを予測する一実施形態の分岐予測装置について説明する。
【００２３】
図１は、本実施形態の分岐予測装置を備える計算機装置の処理概要を示す図である。図１に示す様に本実施形態の分岐予測装置を備える計算機装置は、ソースプログラム４０１を最適化コンパイラ４０２によってコンパイルし、分岐予測を正確に行うことによって高速実行が可能なオブジェクトコード４０３を生成し、実行結果４０５を出力する。
【００２４】
最適化コンパイラ４０２は、ループ終了を判定する条件分岐命令であるループ終了判定条件分岐命令の実行により分岐が行われるかどうかを示すヒントの取得を制御するヒント取得制御手段を備えている。
【００２５】
計算機装置４０４は、特定の命令が実行されたときに前記ヒントを取得するヒント取得手段と、前記ヒント取得手段により取得したヒントを格納するヒント格納手段と、前記ヒント格納手段に格納されたヒントに従って条件分岐命令の次に実行が予測される命令を読み込む命令読み込み手段とを備えている。
【００２６】
以降、本実施形態の分岐予測装置により追加された分岐ヒントテーブル中のヒントビットの値によって分岐を行うかどうかが予測される特別な条件分岐命令であり、ループ終了を判定する条件分岐命令をループ終了判定条件分岐命令と呼ぶ。
【００２７】
図２は、本実施形態の計算機装置４０４の概略構成を示す図である。図２に示す様に本実施形態の計算機装置４０４は、高速実行が可能であるオブジェクトコード４０３を記憶する主記憶装置１１５と、オブジェクトコード４０３を実行する中央演算装置１０１とを有しており、分岐ユニット１０７は、ループ終了判定条件分岐命令で分岐が行われるかどうかを示すヒントを取得するヒント取得手段に相当し、分岐ヒントテーブル１１０は、前記ヒントを格納するヒント格納手段に相当し、命令フェッチユニット１０９は、前記ヒントに従って条件分岐命令の次に実行が予測される命令を読み込む命令読み込み手段に相当している。
【００２８】
中央演算装置１０１は、命令を読み込み、その種類毎に各ユニットに割り振る命令フローユニット１０２と、整数演算を行い、その結果をレジスタ１０４に格納する整数演算ユニット１０３と、レジスタ１０４のデータの読み込み及び書き込みを行うロードストアユニット１０５と、分岐命令の処理、次実行命令の要求及び出力を行う命令プロセッシングユニット１０６と、命令の実行により参照するデータの記憶、主記憶装置１１５との読み込み及び書き込み処理を行うデータキャッシュユニット１１４とを有しており、各ユニットは電子回路により構成されている。
【００２９】
命令プロセッシングユニット１０６は、分岐が生じ得る命令の実行処理を行い、処理結果に応じて分岐先アドレス、分岐結果信号、ループカウンタ更新値、分岐ヒント更新値の中の幾つかを出力する分岐ユニット１０７と、始めにループ回数を記録し、ループの繰り返し毎のその値がデクリメントされ、ループ終了時に「０」となるループカウンタレジスタ１０８とを有している。
【００３０】
また、命令プロセッシングユニット１０６は、次に実行する命令のアドレスを生成する命令フェッチユニット１０９と、条件分岐命令の存在するアドレスと以前の実行の際に分岐を行ったかどうかを示す履歴が記録されている分岐履歴テーブル１１１と、分岐命令のアドレス及びその分岐先アドレスが記録されている分岐先アドレステーブル１１２と、実行する命令の記憶、主記憶装置１１５との読み込み及び書き込みを行う命令キャッシュユニット１１３とを有している。
【００３１】
更に、命令プロセッシングユニット１０６は、本実施形態の分岐予測装置における特徴的な機構である、実行したのアドレスと、次回にそのループ終了判定条件分岐命令を実行した時の分岐を行うかどうかの予測を示すヒントを記録し、アドレスを入力すると対応するヒントを読み出すことのできる分岐ヒントテーブル１１０とを有している。
【００３２】
尚、分岐ヒントテーブル１１０は、ループ終了判定条件分岐命令のアドレスと、そのアドレスのループ終了判定条件分岐命令が次に実行されたときに分岐が行われるかどうかを示す情報を格納するヒントビットフィールドとを有するテーブルであり、特定のループ終了判定条件分岐命令のアドレスが入力されると、対応するヒントビットフィールドの値を出力するものとする。
【００３３】
図３は、本実施形態の命令フェッチユニット１０９の詳細を示す図である。図３に示す様に本実施形態の命令フェッチユニット１０９は、分岐履歴情報から分岐発生の有無を予測する分岐予測ユニット２０１と、本実施形態の分岐予測装置における特徴的な機構である、分岐ヒントテーブル１１０に記録されている分岐発生の有無に関するヒントに応じた分岐予測信号を出力するループ終了判定条件分岐予測ユニット２０２とを有している。
【００３４】
また、命令フェッチユニット１０９は、分岐予測ユニット２０１及びループ終了判定条件分岐予測ユニット２０２からの出力の内、信号が送られてきた側の出力を選択して出力する信号選択手段２０３と、分岐予測結果が実際の実行時の動作と等しいものであったかどうかを検証する為に分岐予測結果を記憶しておく分岐予測結果保持手段２０４と、分岐予測結果から次フェッチ命令のアドレスを分岐先アドレスとするか、プログラムカウンタ２０７の示す実行中の命令のアドレスに連続する次の命令のアドレスであり、加算器２０８により１命令分の命令長の「４」だけ増やしたアドレスとするかを選択するアドレス選択手段２０９とを有している。
【００３５】
更に、命令フェッチユニット１０９は、分岐予測が外れた場合の為に、フェッチ命令アドレスとして選択されなかったアドレスを記憶しておくアドレス保持手段２１０と、分岐予測が当たっていたか否かを検証する比較手段２０５と、比較結果からプログラムカウンタ２０７を更新する為のアドレスを、アドレス保持手段２１０に記憶されているアドレスから得るか、アドレス選択手段２０９によって選ばれたアドレスを用いるかを選択するアドレス選択手段２０６を有している。
【００３６】
図４は、本実施形態の分岐ユニット１０７の詳細を示す図である。図４に示す様に本実施形態の分岐ユニット１０７は、無条件分岐命令、条件分岐命令、ループ終了判定条件分岐命令及びループカウンタ設定命令の処理を行う。
【００３７】
分岐ユニット１０７は、命令フローユニット１０２から送られてきた、これらの命令の種類の識別を行う無条件分岐命令識別手段３０１、条件分岐命令識別手段３０２、ループ終了判定条件分岐命令識別手段３０３及びループカウンタ設定命令識別手段３０４とを有している。
【００３８】
また、分岐ユニット１０７は、送られてきた無条件分岐命令を調べ、命令中若しくは整数演算ユニット１０３から送られてきたレジスタ１０４の値から分岐先アドレスを得て、分岐が発生したことを示す分岐結果信号と同時に出力する無条件分岐命令処理手段３０５と、送られてきた条件分岐命令を調べ、演算ユニットから送られてきたレジスタ１０４の値が条件を満たすかどうかを調べ、条件を満たす場合には命令若しくは整数演算ユニット１０３から送られたレジスタ１０４の値から得られた分岐先アドレス及び分岐が発生したことを示す分岐結果信号を出力し、条件を満たさない場合には分岐が発生しなかったことを示す分岐結果信号を出力する条件分岐命令処理手段３０６とを有している。
【００３９】
更に、分岐ユニット１０７は、本実施形態の分岐予測装置の特徴的な機構である、ループカウンタレジスタ１０８の値から分岐発生の有無を調べ、命令若しくは整数演算ユニット１０３から送られたレジスタ１０４の値から得られた分岐先アドレス及び分岐が発生したことを示す分岐結果信号を出力し、分岐しなかった場合には分岐が発生しなかったことを示す分岐結果信号を出力するループ終了判定条件分岐命令処理手段３０７と、同じく本実施形態の分岐予測装置の特徴的な機構である、ループ終了判定条件分岐命令の動作及びループカウンタ設定命令によってループカウンタレジスタ１０８の保持する値の更新を行うループカウンタ設定命令処理手段３１２を有している。
【００４０】
ループ終了判定条件分岐命令処理手段３０７は、命令若しくは整数演算ユニット１０３から送られてくるレジスタ１０４の値から分岐先アドレスを得る分岐先アドレス抽出手段３０８と、ループカウンタレジスタ１０８の値が「０」以上であるかどうかを判定し、判定の結果が真であった場合には分岐が行われることを表す信号を出力する条件判定手段３０９と、条件判定手段３０９の判定結果の真偽により、分岐先アドレス抽出手段３０８が出力する分岐先アドレスを出力するか否かを制御する信号制御手段３１０と、条件判定手段３０９の判定結果の真偽により、分岐発生または分岐非発生を意味する分岐結果信号の生成を行う分岐結果信号生成手段３１１とを有している。
【００４１】
ループカウンタ設定命令処理手段３１２は、ループカウンタレジスタ１０８の値をループの繰り返しが起こる度に１つづつ減算する減算器３１３と、命令若しくは整数演算ユニット１０３から送られてくるレジスタ１０４の値からループカウンタに設定する値を得るカウンタ設定値抽出手段３１４と、ループ終了判定条件分岐命令が実行され、かつ分岐が発生した場合にのみ減算器３１３の出力を出力する信号制御手段３１５とを有している。
【００４２】
また、ループカウンタ設定命令処理手段３１２は、ループ終了判定条件分岐命令によって分岐が発生した場合には信号制御手段３１５の出力する値を、そうでない場合にはカウンタ設定値抽出手段３１４によって得られた値を出力するループカウンタ更新値選択手段３１６と、選択された値にループカウンタレジスタ１０８の値を更新するループカウンタ更新手段３１７とを有している。
【００４３】
更に、ループカウンタ設定命令処理手段３１２は、信号制御手段３１５の出力する値が「１」であるかどうかを判定し、判定結果が真であった場合には、次にこのループ終了判定条件分岐命令を実行する時には分岐しないことを意味する分岐ヒントテーブル更新値を、判定結果が偽であった場合には、次にこのループ終了判定条件分岐命令を実行する時には分岐することを意味する分岐ヒントテーブル更新値を出力する条件判定手段３１８とを有している。
【００４４】
図５は、本実施形態の最適化コンパイラ４０２の構成例を示す図である。図５に示す様に本実施形態の最適化コンパイラ４０２は、プログラムの構造を調べ、命令生成、最適化に必要な各種の情報を収集して記録する解析部５０１と、解析部５０１で収集した情報を元に、命令生成、最適化処理を行う命令生成・最適化処理部５０６とを有している。
【００４５】
ループ終了判定条件分岐命令適用可能ループ探索部５０４及びループ終了判定条件分岐命令挿入部５０７は、ループ終了判定条件分岐命令の実行により分岐が行われるかどうかを示すヒントの取得を制御するヒント取得制御手段に相当しており、前記ヒント取得制御手段として計算機装置４０４を機能させる為のプログラムである最適化コンパイラ４０２は、ハードディスクや磁気テープ等の記録媒体に記録され、主記憶装置１１５にロードされた後、計算機装置４０４により実行される。
【００４６】
解析部５０１において、本実施形態の分岐予測装置を適用するにあたり必要となる情報は、制御依存解析部５０２及びデータ依存解析部５０３において収集される。
【００４７】
制御依存解析部５０２においては制御依存解析によるプログラム中のループ箇所の識別を、データ依存解析部５０３においてはデータ依存解析によるループ回数の特定等の解析を行い、解析結果をループ情報リスト５０５に記録する。
【００４８】
これらの解析手法としては、例えば「Ｍｉｃｈａｅｌ  Ｗｏｌｆｅ、”ＨＩＧＨ  ＰＥＲＦＯＲＭＡＮＣＥ  ＣＯＭＰＵＴＥＲＳ  ＦＯＲ  ＰＡＲＡＬＬＥＬＣＯＭＰＵＴＩＮＧ”，ｐ．２００−２０１，  Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏｍｐａｎｙ  １９９６、  ＩＳＢＮ  ０−８０５３−２７３０−４」に示されている公知技術が用いられる。
【００４９】
また、コンパイラバックエンド内の特徴的な処理部であるループ終了判定条件分岐命令適用可能ループ探索部５０４は、ループ情報リスト５０５の記録されている各々のループに関する情報を順に辿り、ループ終了判定条件分岐命令を用いることにより高速化が可能なループを解析して識別を行い、その結果をループ情報リスト５０５に記録する。
【００５０】
命令生成・最適化処理部５０６は、解析部５０１で得られた情報から最適化処理を行い、高速実行可能なオブジェクトコード４０３を生成する。
【００５１】
この中で本実施形態の分岐予測装置を適用するにあたり特徴的な処理部であるループ終了判定条件分岐命令挿入部５０７は、ループ情報リスト５０５に記録されているループ終了判定条件分岐命令適用可能ループに対して、ループカウンタレジスタ１０８へループ回数を設定するＣＴＲ設定命令及びループ終了判定条件分岐命令の挿入を行う。
【００５２】
以下では図１の流れに従い、高速実行可能なオブジェクトコード４０３の生成及びその実行時の予測動作例について説明する。
【００５３】
図６は、本実施形態のソースプログラム４０１の一例を示す図である。図６に示す様に本実施形態のソースプログラム４０１は、プログラム片６０１に繰り返し１０回実行されるループを含んでおり、以下ではこのプログラム片６０１を例として説明を行う。
【００５４】
最適化コンパイラ４０２は、まず制御依存解析部５０２でソースプログラム４０１のデータ依存解析を行い、ループ情報リスト５０５を生成する。
【００５５】
図７は、本実施形態のループ情報リスト５０５のデータ構造例を示す図である。図７に示す様に本実施形態のループ情報リスト５０５は、ループ情報エントリ７０１をノードとするリスト構造を持っており、ループ情報エントリ７０１は、ループ先頭命令へのポインタフィールド７０２、ループ末尾命令へのポインタフィールド７０３、ループ回数フィールド７０４、ループ終了判定条件分岐命令が適用可能なループであるかどうかを示すループ終了判定条件分岐命令適用可能性フラグ７０５、次ループ情報エントリへのポインタ７０６を各々情報として持っている。
【００５６】
ループ先頭命令へのポインタフィールド７０２及びループ末尾命令へのポインタフィールド７０３は、例えばプログラム片６０１の矢印で指し示す部分の命令へのポインタを保持している。
【００５７】
この情報からループ終了判定条件分岐命令適用可能ループ探索部５０４は、ループ終了判定条件分岐命令を用いることによる高速実行が可能であるループの探索を、ループ情報リスト５０５に含まれる各ループ情報エントリ７０１を順に辿り、ループ回数情報が登録されているかどうかを調べることにより行う。
【００５８】
図８は、本実施形態のループ終了判定条件分岐命令適用可能ループ探索部５０４の処理手順を示すフローチャートである。図８に示す様に本実施形態のループ終了判定条件分岐命令適用可能ループ探索部５０４は、まずステップ８０１において、ループ情報リスト５０５の中に、まだ適用可能かどうかの判定を行っていないループがあるかどうかを調べ、未調査のループが残っていなかった場合には処理を終了する。
【００５９】
もしまだ未調査のループが残っている場合は、ステップ８０２において、未調査のループのループ情報エントリ７０１をループ情報リスト５０５から取り出す。
【００６０】
次に、ステップ８０３において、前記取り出したループ情報エントリ７０１のループ回数フィールド７０４にループ回数が記録されているかどうかを調べ、ループ回数の値が特定できているかどうかを調べる。
【００６１】
ループ回数が特定できている場合には、ループ終了判定条件分岐命令が適用可能であると判断され、ステップ８０５において、ループ情報エントリ７０１内のループ終了判定条件分岐命令適用可能性フラグ７０５を立て、ステップ８０１に戻る。
【００６２】
もしループ回数が特定できていない場合には、ループ終了判定条件分岐命令が適用不可能であると判断され、ステップ８０４において、ループ情報エントリ７０１内のループ終了判定条件分岐命令適用可能性フラグ７０５をリセットし、ステップ８０１に戻る。
【００６３】
ループ終了判定条件分岐命令適用可能ループ探索部５０４において、ループ情報リスト５０５に含まれる全てのループ情報エントリ７０１についての処理が終了した後、命令生成・最適化処理部５０６のループ終了判定条件分岐命令挿入部５０７は、ループ情報リスト５０５の中に含まれる全てのループ情報エントリ７０１を調べ、ループ終了判定条件分岐命令適用可能ループに対して、ループ先頭にＣＴＲ設定命令を挿入し、ループ末尾へループ終了判定条件分岐命令の挿入を行う。
【００６４】
図９は、本実施形態のループ終了判定条件分岐命令挿入部５０７の処理手順を示すフローチャートである。図９に示す様に本実施形態のループ終了判定条件分岐命令挿入部５０７は、まずステップ９０１において、ループ終了判定条件分岐命令が挿入されていないループを探し、その様なループが存在しない場合は処理を終了する。
【００６５】
ループ終了判定条件分岐命令が挿入されていないループが存在する場合には、ステップ９０２において、ループ情報リスト５０５から対応するループ情報エントリ７０１を選ぶ。
【００６６】
ステップ９０３において、前記選ばれたループ情報エントリ７０１を調べ、ループ終了判定条件分岐命令適用可能性フラグ７０５が立っている場合には、ステップ９０４で、ループ先頭命令へのポインタフィールド７０２に格納されているポインタの指す位置にＣＴＲ設定命令を挿入し、次にステップ９０５において、ループ末尾命令へのポインタフィールド７０３に格納されたポインタの指す位置にループ終了判定条件分岐命令を挿入する。
【００６７】
ステップ９０３においてループ情報エントリ７０１を調べた結果、ループ終了判定条件分岐命令適用可能性フラグ７０５が立っていない場合には、ステップ９０１に戻る。
【００６８】
図１０は、本実施形態のオブジェクトコード４０３の一例を示す図である。図１０に示す様に本実施形態のオブジェクトコード４０３は、プログラム片６０１に対応するオブジェクトコード片１００１を含んでおり、オブジェクトコード片１００１には、ＣＴＲ設定命令１００２及びループ終了判定条件分岐命令１００３が挿入されている。
【００６９】
ここで、ループ終了判定条件分岐命令挿入部５０７により挿入されたループ終了判定条件分岐命令１００３は、条件分岐命令の実行時にヒントを取得することを示す情報が保持された形式の条件分岐命令である。すなわち、オブジェクトコード４０３中に挿入されたループ終了判定条件分岐命令１００３は、分岐ユニット１０７での実行時に、次の実行時に分岐が行われるかどうかを示すヒントが取得される条件分岐命令であることを示している。
【００７０】
次に、オブジェクトコード片１００１を計算機装置４０４で実行する場合の動作例について説明する。特に主記憶装置１１５に格納されたオブジェクトコード片１００１に含まれる、ＣＴＲ設定命令１００２及びループ終了判定条件分岐命令１００３を実行する場合の動作例について説明する。
【００７１】
実行する命令のアドレスとしてＣＴＲ設定命令１００２のアドレスが命令フェッチユニット１０９から命令キャッシュユニット１１３へ送られると、ＣＴＲ設定命令１００２が主記憶装置１１５から命令キャッシュユニット１１３にまだ読み込まれていない場合は読み込んでから、既にキャッシュユニット内に読み込まれている場合は、命令キャッシュユニット１１３内に存在するＣＴＲ設定命令１００２が命令フローユニット１０２送られる。尚、主記憶装置１１５から命令フローユニット１０２までの流れは、全ての命令の実行において同様である。
【００７２】
まず、図１０に示したＣＴＲ設定命令１００２の実行について考えてみる。ここでＣＴＲ設定命令１００２は、ループカウンタレジスタ１０８に「１０」を設定することを示している。
【００７３】
命令フローユニット１０２において、命令プロセッシングユニット１０６内にある分岐ユニット１０７にＣＴＲ設定命令１００２の実行処理が割り当てられる。
【００７４】
分岐ユニット１０７内ではループカウンタ設定命令識別手段３０４によって、ＣＴＲ設定命令１００２であることが識別され、カウンタ設定値抽出手段３１４によってカウンタ設定値である「１０」が取得される。
【００７５】
取得されたカウンタ設定値はループカウンタ更新値選択手段３１６に送られる。ここで減算器３１３からのカウンタ設定値との選択が行われるが、カウンタ設定値抽出手段３１４から値が送られてきた場合は、その値が優先的に選択されるものとする。
【００７６】
選択された値はループカウンタ更新手段３１７に送られ、ループカウンタレジスタ１０８の保持する値が更新される。
【００７７】
命令プロセッシングユニット１０６での処理とオーバーラップして、命令フェッチユニット１０９は、次に実行する命令のアドレス生成の処理を行う。
【００７８】
ＣＴＲ設定命令１００２は分岐が発生しない命令である為、そのアドレスが命令フェッチユニット１０９から出力されても、分岐ヒントテーブル１１０及び分岐先アドレステーブル１１２から命令フェッチユニット１０９への入力は何もない。
【００７９】
よって信号選択手段２０３は、分岐が発生しないことを示す信号を出力し、その結果アドレス選択手段２０９においては、プログラムカウンタ２０７の保持する現在実行中の命令のアドレスに、加算器２０８により１命令分の命令長を加算したアドレスのみが入力として与えられ、これが次命令アドレスとして出力される。
【００８０】
次に、ＣＴＲ設定命令１００２を実行した後、ループ本体が実行され、ループ繰り返し時にループ終了判定条件分岐命令１００３を実行する場合について考える。尚、ループ終了判定条件分岐命令１００３実行後、少なくとも２回はループが繰り返されるものとし、ループ終了判定条件分岐命令１００３は、既に命令フローユニット１０２まで送られているものとする。
【００８１】
ループ終了判定条件分岐命令１００３は、命令フローユニット１０２を介して、命令プロセッシングユニット１０６に割り当てられ、その内部の分岐ユニット１０７に送られる。
【００８２】
分岐ユニット１０７の内部では、ループ終了判定条件分岐命令識別手段３０３によってループ終了判定条件分岐命令１００３であることが識別され、分岐先アドレス抽出手段３０８へ送られた後、命令若しくは整数演算ユニット１０３から送られてきた信号から分岐先のアドレスを得る。また同時に信号制御手段３１０に対して、その出力を行うよう指示を出す信号を送る。
【００８３】
同時に条件判定手段３０９は、ループカウンタレジスタ１０８の値を読み込み、その値が「０」より大きいかどうかの判定を行う。ループ繰り返し時にはループカウンタレジスタ１０８の値は「０」より大きく必ず条件が成立する為、条件が成立したことを示す信号が信号制御手段３１０、分岐結果信号生成手段３１１及び信号制御手段３１５へ送る。
【００８４】
条件成立の信号を受けとると、信号制御手段３１０は分岐先アドレスを出力し、分岐結果信号生成手段３１１は、命令フェッチユニット１０９へ分岐結果信号として、分岐が発生したことを示す信号を出力する。
【００８５】
信号制御手段３１５は、ループ終了判定条件分岐命令識別手段３０３からの出力要求信号と、条件判定手段３０９からの条件成立の信号を受けとると、減算器３１３からの出力である、ループカウンタレジスタ１０８の値から「１」引いた値を出力する。
【００８６】
この値を受けとったループカウンタ更新値選択手段３１６は、ループカウンタレジスタ１０８の更新値として受けとった値をループカウンタ更新手段３１７へ送り、その結果ループカウンタレジスタ１０８の値が更新される。
【００８７】
また、信号制御手段３１５からの出力は条件判定手段３１８へも送られ、条件判定手段３１８は、信号制御手段３１５の出力する値が「１」であるかどうかを判定する。このあと少なくとも２回はループが繰り返されるものと仮定しているので、条件判定手段３１８の条件判定の結果は必ず偽となり、条件判定手段３１８は、次回このループ終了判定条件分岐命令１００３を実行した場合には分岐が発生することを意味するヒントの値を分岐ヒントテーブル１１０へ出力する。
【００８８】
分岐ヒントの更新値を受けとった分岐ヒントテーブル１１０は、テーブル内の対応するループ終了判定条件分岐命令１００３の情報と受けとった分岐ヒントの更新値とのマッチングを、ループ終了判定条件分岐命令１００３のアドレスによってとり、対応する分岐ヒントテーブル１１０内の値を更新する。
【００８９】
命令プロセッシングユニット１０６での処理とオーバーラップして、命令フェッチユニット１０９は、次に実行する命令のアドレス生成の処理を行う。
【００９０】
ループ終了判定条件分岐命令１００３のアドレスが命令フェッチユニット１０９から出力されると、そのアドレスに対応する情報が存在する場合に限り、分岐ヒントテーブル１１０から分岐ヒントが、分岐先アドレステーブル１１２から分岐先命令のアドレスが命令フェッチユニット１０９に送られる。
【００９１】
尚、分岐履歴テーブル１１１には、条件分岐命令の動作履歴のみ記録されており、ループ終了判定条件分岐命令１００３のエントリは存在しない為、命令フェッチユニット１０９からループ終了判定条件分岐命令１００３のアドレスを送られても何も値を返さないものとする。
【００９２】
ループ繰り返し動作中は、分岐ヒントテーブル１１０から、はじめの１回を除き必ず分岐動作を行うことを示す分岐ヒント信号が送られてくる。分岐ヒント信号を受けとったループ終了判定条件分岐予測ユニット２０２は分岐動作を行うことを示す分岐予測信号を出力する。
【００９３】
出力された分岐予測信号は、信号選択手段２０３において分岐予測ユニット２０１の出力との選択が行われるが、分岐予測ユニット２０１からの出力は無い為、信号選択手段２０３への入力がそのまま出力される。
【００９４】
信号選択手段２０３からの出力は、分岐予測結果保持手段２０４においてその結果が保持され、またアドレス選択手段２０９にも送られる。
【００９５】
アドレス選択手段２０９は、入力である分岐先アドレステーブル１１２から送られてきた分岐先アドレスと、ループ終了判定条件分岐命令１００３に連続する命令のアドレスであって、プログラムカウンタ２０７の保持する現在実行中の命令のアドレスに１命令分の命令長を足したアドレスの２つから、分岐が行われた場合の後続命令のアドレスである分岐先アドレステーブル１１２から送られてきた分岐先アドレスを選択する。
【００９６】
前記選択された分岐先アドレスは、命令フェッチユニット１０９のアドレス選択手段２０６へプログラムカウンタ２０７更新の為に出力され、プログラムカウンタ２０７の更新が行われる。
【００９７】
また、アドレス選択手段２０９によって選択されなかったアドレスは、アドレス保持手段２１０に送られ、分岐予測が外れた場合に備えて記憶される。
【００９８】
次に、ループ終了時の１回前にループ終了判定条件分岐命令１００３を実行する場合について考える。
【００９９】
ループ繰り返し時と異なるのは条件判定手段３１８の判定結果であり、その条件判定の結果は真となり、条件判定手段３１８は、次回このループ終了判定条件分岐命令１００３を実行した場合には分岐が発生しないことを意味するヒントの値を分岐ヒントテーブル１１０へ出力する。
【０１００】
分岐ヒントの更新値を受けとった分岐ヒントテーブル１１０は、テーブル内の対応するループ終了判定条件分岐命令１００３の情報と受けとった分岐ヒントの更新値とのマッチングを、ループ終了判定条件分岐命令１００３のアドレスによってとり、対応する分岐ヒントテーブル１１０内の値を更新する。
【０１０１】
次に、ループ終了時にループ終了判定条件分岐命令１００３を実行する場合について考える。
【０１０２】
ループ繰り返し時と異なるのは、命令フェッチユニット１０９において、ループ終了判定条件分岐命令１００３のアドレスを生成後、その後続命令のアドレスを生成する際に、分岐ヒントテーブル１１０から送られてくるヒントが分岐しないことを意味するヒントになっている点である。これはループ終了時の１回前の繰り返し時に分岐しないことを意味するヒントが分岐ヒントテーブル１１０に書き込まれているからである。
【０１０３】
その結果またアドレス選択手段２０９の出力として、プログラムカウンタ２０７の保持するアドレスに加算器２０８により１命令分の命令長を加算したアドレスが選択される。よって、正しい後続命令のフェッチが可能となり、ループ終了時の分岐予測が正しく行うことができる様になる。
【０１０４】
尚、分岐予測が外れた場合は、分岐ユニット１０７から送られてくる分岐結果信号と、分岐予測結果保持手段２０４に保持された予測結果を比較手段２０５において比較することによって予測が外れたことが検出され、アドレス選択手段２０６からの出力が、アドレス保持手段２１０に保持されている分岐予測により選択されなかったアドレスとなって、プログラムカウンタ２０７の値を分岐直後の状態に戻すことができる。
【０１０５】
以上説明した様に、本実施形態の分岐予測装置によれば、ループ繰り返し回数の値によりループ終了判定を行う条件分岐命令で分岐を行うかどうかを予測するので、ループ終了判定を行う条件分岐命令のループ終了時の分岐を正確に予測することが可能である。
【０１０６】
以上、本発明を前記実施形態に基づき具体的に説明したが、本発明は、前記実施形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【０１０７】
【発明の効果】
本発明によれば、ループ繰り返し回数の値によりループ終了判定を行う条件分岐命令で分岐を行うかどうかを予測するので、ループ終了判定を行う条件分岐命令のループ終了時の分岐を正確に予測することが可能である。
【図面の簡単な説明】
【図１】本実施形態の分岐予測装置を備える計算機装置の処理概要を示す図である。
【図２】本実施形態の計算機装置４０４の概略構成を示す図である。
【図３】本実施形態の命令フェッチユニット１０９の詳細を示す図である。
【図４】本実施形態の分岐ユニット１０７の詳細を示す図である。
【図５】本実施形態の最適化コンパイラ４０２の構成例を示す図である。
【図６】本実施形態のソースプログラム４０１の一例を示す図である。
【図７】本実施形態のループ情報リスト５０５のデータ構造例を示す図である。
【図８】本実施形態のループ終了判定条件分岐命令適用可能ループ探索部５０４の処理手順を示すフローチャートである。
【図９】本実施形態のループ終了判定条件分岐命令挿入部５０７の処理手順を示すフローチャートである。
【図１０】本実施形態のオブジェクトコード４０３の一例を示す図である。
【符号の説明】
４０１…ソースプログラム、４０２…最適化コンパイラ、４０３…オブジェクトコード、４０４…計算機装置、４０５…実行結果、１０１…中央演算装置、１０２…命令フローユニット、１０３…整数演算ユニット、１０４…レジスタ、１０５…ロードストアユニット、１０６…命令プロセッシングユニット、１０７…分岐ユニット、１０８…ループカウンタレジスタ、１０９…命令フェッチユニット、１１０…分岐ヒントテーブル、１１１…分岐履歴テーブル、１１２…分岐先アドレステーブル、１１３…命令キャッシュユニット、１１４…データキャッシュユニット、１１５…主記憶装置、２０１…分岐予測ユニット、２０２…ループ終了判定条件分岐予測ユニット、２０３…信号選択手段、２０４…分岐予測結果保持手段、２０５…比較手段、２０６…アドレス選択手段、２０７…プログラムカウンタ、２０８…加算器、２０９…アドレス選択手段、２１０…アドレス保持手段、３０１…無条件分岐命令識別手段、３０２…条件分岐命令識別手段、３０３…ループ終了判定条件分岐命令識別手段、３０４…ループカウンタ設定命令識別手段、３０５…無条件分岐命令処理手段、３０６…条件分岐命令処理手段、３０７…ループ終了判定条件分岐命令処理手段、３０８…分岐先アドレス抽出手段、３０９…条件判定手段、３１０…信号制御手段、３１１…分岐結果信号生成手段、３１２…ループカウンタ設定命令処理手段、３１３…減算器、３１４…カウンタ設定値抽出手段、３１５…信号制御手段、３１６…ループカウンタ更新値選択手段、３１７…ループカウンタ更新手段、３１８…条件判定手段、５０１…解析部、５０２…制御依存解析部、５０３…データ依存解析部、５０４…ループ終了判定条件分岐命令適用可能ループ探索部、５０５…ループ情報リスト、５０６…命令生成・最適化処理部、５０７…ループ終了判定条件分岐命令挿入部、６０１…プログラム片、７０１…ループ情報エントリ、７０２…ループ先頭命令へのポインタフィールド、７０３…ループ末尾命令へのポインタフィールド、７０４…ループ回数フィールド、７０５…ループ終了判定条件分岐命令適用可能性フラグ、７０６…次ループ情報エントリへのポインタ、１００１…オブジェクトコード片、１００２…ＣＴＲ設定命令、１００３…ループ終了判定条件分岐命令。
【図１】
0003570855.tif 000002
【図２】
0003570855.tif 000003
【図３】
0003570855.tif 000004
【図４】
0003570855.tif 000005
【図５】
0003570855.tif 000006
【図６】
0003570855.tif 000007
【図７】
0003570855.tif 000008
【図８】
0003570855.tif 000009
【図９】
0003570855.tif 000010
【図１０】
0003570855.tif 000011