(57)【要約】プロセッサ内のリンク・スタックが、プロシージャ・リターン・アドレス誤予測誤りに応じて修復される。一例において、プロセッサで使用されるリンク・スタックは、リンク・スタックから取得されたプロシージャ・リターン・アドレス値における誤りを検出し、かつ、この誤りを検出することに応答して、リンク・スタックから現在取得待ちのプロシージャ・リターン・アドレス値をスキップすることによって修復される。１または複数の実施形態では、リンク・スタック回路が、リンク・スタックおよびリンク・スタック・ポインタを備える。リンク・スタックは、複数のプロシージャ・リターン・アドレス値を格納するように構成される。リンク・スタック・ポインタは、リンク・スタックから以前に取得したプロシージャ・リターン・アドレス値で検出された誤りに応答して、リンク・スタックから現在取得待ちのプロシージャ・リターン・アドレス値をスキップするように構成されている。
2009528637.tif 000002
【特許請求の範囲】
【請求項１】
プロセッサで使用されるリンク・スタックを修復する方法であって、
前記リンク・スタックから取得されたプロシージャ・リターン・アドレス値における誤りを検出することと、
前記誤りを検出することに応答して、前記リンク・スタックから現在取得待ちのプロシージャ・リターン・アドレス値をスキップすることと
を備える方法。
【請求項２】
前記現在取得待ちのプロシージャ・リターン・アドレス値をスキップすることは、
前記誤りを検出することに応答して、前記現在取得待ちのプロシージャ・リターン・アドレス値をスキップするために、リンク・スタック・ポインタを修正することを備える請求項１に記載の方法。
【請求項３】
前記現在取得待ちのプロシージャ・リターン・アドレス値をスキップするために、リンク・スタック・ポインタを修正することは、
前記誤りを引き起こしたプロシージャ・リターン・アドレス値に対応するリンク・スタック・ポインタ・インデクスを保存することと、
前記誤りを検出することに応答して、現在のリンク・スタック・ポインタ・インデクスを、２リンク・スタック・エントリ位置オフセットした前記保存されたリンク・スタック・ポインタ・インデクスと交換することと
を備える請求項２に記載の方法。
【請求項４】
前記リンク・スタック・ポインタ・インデクスを保存することは、
前記誤りを引き起こしたプロシージャ・リターン・アドレス値を、前記リンク・スタックからポップすることとともに、前記リンク・スタック・ポインタ・インデクスを保存することを備える請求項３に記載の方法。
【請求項５】
前記保存されたリンク・スタック・ポインタ・インデクスを、前記保存されたリンク・スタック・ポインタ・インデクスに対応する分岐命令情報に関連付けることを更に備える請求項３に記載の方法。
【請求項６】
前記現在取得待ちのプロシージャ・リターン・アドレス値をスキップすることは、
前記誤りを引き起こしたプロシージャ・リターン・アドレス値の直後にキューされたプロシージャ・リターン・アドレス値を前記リンク・スタックからポップすることと、
前記ポップされたプロシージャ・リターン・アドレス値の直後にキューされたプロシージャ・リターン・アドレス値を前記リンク・スタックからポップすることと
を備える請求項１に記載の方法。
【請求項７】
前記リンク・スタックから取得されたプロシージャ・リターン・アドレス値における誤りを検出することは、
リンク・スタック・オーバフローまたはスキップされたプログラム・リターンを検出することを備える請求項１に記載の方法。
【請求項８】
複数のプロシージャ・リターン・アドレス値を格納するように構成されたリンク・スタックと、
前記リンク・スタックから以前に取得されたプロシージャ・リターン・アドレス値で検出された誤りに応答して、前記リンク・スタックから現在取得待ちのプロシージャ・リターン・アドレス値をスキップするように構成された命令取得ロジックと
を備えるプロセッサ。
【請求項９】
前記リンク・スタックは、サーキュラ・バッファを備える請求項８に記載のプロセッサ。
【請求項１０】
前記命令取得ロジックは、前記検出された誤りに応答して、前記現在取得待ちのプロシージャ・リターン・アドレス値をスキップするために、リンク・スタック・ポインタを修正することによって、前記現在取得待ちのプロシージャ・リターン・アドレス値をスキップするように構成された請求項９に記載のプロセッサ。
【請求項１１】
前記命令取得ロジックは、前記誤りを引き起こしたプロシージャ・リターン・アドレス値に対応するリンク・スタック・ポインタ・インデクスを保存し、前記誤りを検出することに応答して、現在のリンク・スタック・ポインタ・インデクスを、２リンク・スタック・エントリ位置オフセットした前記保存されたリンク・スタック・ポインタ・インデクスと交換することによって、前記リンク・スタック・ポインタを修正し、前記現在取得待ちのプロシージャ・リターン・アドレス値をスキップするように構成された請求項１０に記載のプロセッサ。
【請求項１２】
前記保存されたリンク・スタック・ポインタ・インデクスに対応する命令情報を格納し、前記格納された命令情報を、前記保存されたリンク・スタック・ポインタ・インデクスに関連付けるように構成されたキューを更に備える請求項１１に記載のプロセッサ。
【請求項１３】
前記リンク・スタックは、プッシュ−ポップ・バッファを備える請求項８に記載のプロセッサ。
【請求項１４】
前記命令取得ロジックは、前記誤りを引き起こしたプロシージャ・リターン・アドレス値の直後にキューされたプロシージャ・リターン・アドレス値を前記プッシュ−ポップ・バッファからポップし、前記ポップされたプロシージャ・リターン・アドレス値の直後にキューされたプロシージャ・リターン・アドレス値を前記プッシュ−ポップ・バッファからポップすることによって、前記現在取得待ちのプロシージャ・リターン・アドレス値をスキップするように構成された請求項１３に記載のプロセッサ。
【請求項１５】
前記検出された誤りは、リンク・スタック・オーバフローまたはスキップされたプログラム・リターンを備える請求項８に記載のプロセッサ。
【請求項１６】
プロセッサで使用されるリンク・スタック回路であって、
複数のプロシージャ・リターン・アドレス値を格納するように構成されたリンク・スタックと、
前記リンク・スタックから以前に取得されたプロシージャ・リターン・アドレス値で検出された誤りに応答して、前記リンク・スタックから現在取得待ちのプロシージャ・リターン・アドレス値をスキップするように構成されたリンク・スタック・ポインタと
を備えるリンク・スタック回路。
【請求項１７】
前記リンク・スタックは、サーキュラ・バッファを備える請求項１６に記載のリンク・スタック回路。
【請求項１８】
前記リンク・スタック・ポインタは、前記検出された誤りに応答して、前記現在取得待ちのプロシージャ・リターン・アドレス値の直後に格納されたプロシージャ・リターン・アドレス値に対応するリンク・スタック内のエントリを示すことによって、前記現在取得待ちのプロシージャ・リターン・アドレス値をスキップするように構成された請求項１６に記載のリンク・スタック回路。
【請求項１９】
前記リンク・スタック・ポインタは、前記検出された誤りに応答して、現在のリンク・スタック・ポインタ・インデクスを、２リンク・スタック・エントリ位置オフセットした保存されたリンク・スタック・ポインタ・インデクスと交換することによって、前記現在取得待ちのプロシージャ・リターン・アドレス値の直後に格納されたプロシージャ・リターン・アドレス値に対応するリンク・スタック内のエントリを示すように構成された請求項１８に記載のリンク・スタック回路。
【請求項２０】
前記検出された誤りは、リンク・スタック・オーバフローまたはスキップされたプログラム・リターンを備える請求項１８に記載のリンク・スタック回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、一般に、プロセッサに関し、特に、プロセッサにおけるリンク・スタック・リターン誤りを修復することに関する。
【背景技術】
【０００２】
従来のプロセッサは、性能を改善するために、命令事前取得と推測的命令実行とを導入している。推測的命令取得は、命令パイプラインの初期に分岐命令の方向および目標アドレスを予測する技術を利用する分岐予測メカニズムによって可能とされる。分岐命令の結果を予測することによって、プロセッサ・リソースは、分岐判定が後の命令パイプラインについて解決されるまで無駄に過ごす（あるいは、単に予め定めたパスを取得する）ことなく、命令を推測的に取得することができる。そのため、分岐が正確に予測される場合、プロセッサの性能が改善される場合がある。
【０００３】
プロシージャ・コールおよびリターンに関連する分岐命令の場合、従来のプロセッサは、予測されたリターン・アドレス値を格納するためのリンク・スタックを保持する。格納されたリターン・アドレス値は、コールされたプロシージャがプログラム制御を譲った後に取得される次の命令のメモリ位置に対応する。そのため、従来のプロセッサは、分岐命令がプロシージャ・コールになると予測すると、コールされたプロシージャが戻った場合に、予測されたリターン命令を取得できるように、リンク・スタックへリターン・アドレス値を格納すなわち「プッシュ」する。プロセッサが、プロシージャ・コールからのリターンを検出し、そのリターンが採用されるであろうと予測すると、リンク・スタックから現在取得待ちのリターン・アドレス値を取得すなわち「ポップ」する。その後、ポップされたリターン・アドレス値に関連付けられた命令が、プロセッサによって、メモリから取得される。従って、リンク・スタックは、リンク・スタックに格納されたリターン・アドレス値を用いることによってプロシージャ・リターン自身が実行される前に、プロシージャ・リターンに従うと予測された命令がプロセッサによって推測的に取得されるメカニズムを提供する。
【０００４】
しかしながら、分岐は必ずしも正確に予測されるとは限らない。分岐誤予測がなされると、プロセッサは、顕著な性能ペナルティを招きうる。一般に、分岐命令は、命令パイプラインの終了近くにおいて、予測された分岐が、実際の分岐判定と一致しているかを解き、分岐が正確に予測されている場合、命令取得は、予測されたパスに沿って続けられる。しかしながら、分岐が誤予測されると、推測的に取得された命令とその結果が、プロセッサ・パイプラインからフラッシュされ、正しいアドレスを用いて、命令取得が再指示される。
【０００５】
プロシージャ・リターン命令は、多くの方法で誤予測されうる。例えば、リンク・スタック・オーバフローによって、リターン・アドレス値は、スタックから消される。そのため、１または複数の有効なリターン・アドレス値が、スタックから失われ、関連するプロシージャ・リターンが、リンク・スタックからその値をポップすることを試みた場合、誤予測を引き起こす。また、条件付のプロシージャ・リターンが、その分岐方向を誤予測するかもしれない。更に、プロシージャ・リターンは、ソフトウェアによって故意にスキップされるかもしれない。すなわち、プロシージャは、ネストされたプロシージャ・コールのように、別のプロシージャをコールするかもしれない。特定のネスト・プロシージャは、制御が戻された場合に実行する更なる命令を持たず、コールしたプロシージャにリンクを戻すのではない。そのため、ソフトウェアは、そのようなプロシージャ・リターンをスキップし、これらプロシージャへのみ直接的にリンクを戻す。これらプロシージャは、戻されると実行される実質的な命令をもっており、もって、コードの性能を改善する。そのような最適化されたコードがプロセッサによって実行される場合、１または複数のネスト・プロシージャがスキップされうる。しかしながら、従来のハードウェア・リンク・スタックは、リンク・スタックに格納されたリターン・アドレス値をスキップしない。そのため、予測されたリターン・アドレス値は、プロシージャ・リターンが、介在する分岐およびリンク命令のない、スキップされたプロシージャ・リターン命令に従うリンク・スタックをポップした場合、従来のハードウェア・リンク・スタックを用いて誤予測されるだろう。ポップされた値は、後のリターンではなく、スキップされたリターンに関連付けられる。
【０００６】
誤予測されたプロシージャ・リターンを訂正するための従来技術は、幾つかのプロセッサ・サイクルを無駄に使う。例えば、ハードウェア・リンク・スタックからポップされたリターン・アドレス値が、解かれたアドレスと一致しない場合、プロセッサによって訂正シーケンスが実行される。誤予測訂正は、従来、パイプラインから推論的に取得された命令をフラッシュすることと、正しい命令ストリームを取得することとを含む。しかしながら、ハードウェア・リンク・スタックは、スキップされたリターンについて訂正されない。そのため、ポップされた次のハードウェア・リンク・スタック・エントリは、常に、正しいエントリから、少なくとも１ポジション（スキップされたリターンの数）離れている。その結果、スキップされたリターンの前に確立されたリンク・スタック・エントリに関連付けられたその後のプロシージャ・リターンは、更なる誤予測を招くだろう。従って、従来のプロセッサは、これらの誤予測の各々について訂正シーケンスを実行しなければならない。正しくないリターン・アドレスがハードウェア・リンク・スタックからポップされる毎に分岐訂正シーケンスを実行することは、プロセッサ性能を低下し、電力消費量を増加する。
【発明の開示】
【発明の概要】
【０００７】
本明細書で教示された方法および装置に従って、プロセッサ内のリンク・スタックが、プロシージャ・リターン・アドレス誤予測誤りに応答して修復される。１または複数の実施形態では、リンク・スタック回路が、リンク・スタックおよびリンク・スタック・ポインタを含む。リンク・スタックは、複数のプロシージャ・リターン・アドレス値を格納するように構成される。リンク・スタック・ポインタは、リンク・スタックから以前に取得されたプロシージャ・リターン・アドレス値で検出された誤りに応答して、リンク・スタックから現在取得待ちのプロシージャ・リターン・アドレス値をスキップするように構成される。
【０００８】
従って、少なくとも１つの実施形態では、プロセッサで使用されるリンク・スタックは、リンク・スタックから取得したプロシージャ・リターン・アドレス値における誤りを検出し、この誤りを検出することに応答して、リンク・スタックから現在取得待ちのプロシージャ・リターン・アドレス値をスキップすることによって修復される。一例において、現在取得待ちのプロシージャ・リターン・アドレスをスキップすることは、誤りを検出することに応答して、現在取得待ちのプロシージャ・リターン・アドレス値をスキップするようにリンク・スタック・ポインタを修正することを備える。リンク・スタック・ポインタは、誤りを引き起こしたプロシージャ・リターン・アドレス値に対応したリンク・スタック・ポインタ・インデクスを保存し、現在のリンク・スタック・ポインタ・インデクスを、２リンク・スタック・エントリ位置オフセットされた保存されたリンク・スタック・ポインタ・インデクスと交換することによって修正される。別の例では、現在取得待ちのプロシージャ・リターン・アドレス値をスキップすることは、誤りを引き起こしたプロシージャ・リターン・アドレス値の直後にキューされたプロシージャ・リターン・アドレス値をリンク・スタックからポップすることと、ポップされたプロシージャ・リターン・アドレスの直後にキューされたプロシージャ・リターン・アドレス値をリンク・スタックからポップすることとを備える。
【０００９】
上記の装置および方法に対応する相補的なプロセッサは、リンク・スタックと、命令取得ロジックとを備える。リンク・スタックは、複数のプロシージャ・リターン・アドレス値を格納するように構成される。命令取得ロジックは、リンク・スタックから以前に取得されたプロシージャ・リターン・アドレスで検出された誤りに応答して、リンク・スタックから現在取得待ちのプロシージャ・リターン・アドレス値をスキップするように構成される。１つの実施形態において、リンク・スタックは、サーキュラ・バッファを備える。命令取得ロジックは、取得待ちのプロシージャ・リターン・アドレス値をスキップするために、リンク・スタック・ポインタを修正することによって、サーキュラ・バッファから現在取得待ちのプロシージャ・リターン・アドレス値をスキップするように構成される。別の実施形態では、リンク・スタックは、プッシュ−ポップ・バッファを備える。命令取得ロジックは、誤りを引き起こしたプロシージャ・リターン・アドレス値の直後にキューされたプロシージャ・リターン・アドレス値を、プッシュ−ポップ・バッファからポップし、ポップされたプロシージャ・リターン・アドレス値の直後にキューされたプロシージャ・リターン・アドレス値を、プッシュ−ポップ・バッファからポップすることによって、現在取得待ちのプロシージャ・リターン・アドレス値をスキップするように構成されている。
【００１０】
もちろん、本開示は、上記の特徴に限定されない。当業者であれば、詳細説明を読み、添付図面を見ることによって、更なる特徴を認識するだろう。
【詳細な説明】
【００１１】
図１は、予測されたリターン・アドレス値、すなわち、プロシージャ・リターンに従うと予測または予期される命令が格納されるメモリ位置を指示または表示するアドレス値を格納するリンク・スタック１２を含むプロセッサ１０の実施形態を例示する。プロセッサ１０は、例えば、サーバ、デスクトップ・コンピュータ、あるいは、ポータブル・コンピュータ、モバイル電話、パーソナル・デジタル・アシスタント等のようなモバイル・デバイスである計算システム（図示せず）内の中央処理ユニットまたはメイン処理ユニットとして動作する。プロセッサ１０は、恐らくは分岐予測および推論的命令取得を含む一定の動作をプロセッサ１０に対して講じさせる命令の集合を実行する。リンク・スタック１２は、多くの場合、以下に詳述するように、リンク・スタック１２から現在取得待ちのリターン・アドレス値をスキップすることによって、リターン・アドレス誤予測誤りに応じて修復される。
【００１２】
プロセッサ１０は更に、命令ユニット１４、複数の実行ユニット１６、完了ユニット１８、バス・インタフェース・ユニット２０、命令キャッシュ２２、データ・キャッシュ２４、および、汎用レジスタ（４０）とスタック・ポインタ・レジスタ（４２）とを含む複数のシステム・レジスタ２６を備える。命令ユニット１４は、集中化された命令フローの制御を、実行ユニット１６に供給する。１または複数のロード／ストア・ユニット（図示せず）、浮動小数点ユニット（図示せず）、および整数ユニット（図示せず）を含みうる実行ユニット１６は、多くの命令を並行して実行することができる。そのため、プロセッサ１０は、スーパスカラ化されるか、スーパパイプライン化されうる。更に、実行ユニット１６のうちの１または複数は、予測された分岐を解決することができる。完了ユニット１８は、実行中、ディスパッチからの命令を追う。バス・インタフェース・ユニット２０は、プロセッサ１０との間で、データ、アドレス、および制御信号を転送するためのメカニズムを提供する。命令キャッシュ２２およびデータ・キャッシュ２４は、システム・レジスタ２６と実行ユニット１６とが、命令およびデータに迅速にアクセスすることを可能にする。更に、実行ユニット１６や、例えばロード／ストア・ユニット（図示せず）のうちの１つを経由して、データ・キャッシュ２４とシステム・レジスタ２６との間でデータを移動することができる。
【００１３】
更に詳しくは、命令ユニット１４は、命令取得ロジック２８、分岐予測ユニット（ＢＰＵ）３０、命令キュー３２、命令ディスパッチ・ロジック３４、および分岐情報キュー３６を含んでいる。リンク・スタック１２およびリンク・スタック・ポインタ３８は、命令ユニット１４内に含まれているか、または関連付けられている。命令取得ロジック２８は、命令キャッシュ２２から命令を取得し、それらを復号し、復号された命令を命令キュー３２へロードする。命令ディスパッチ・ロジック３４は、キューされた命令を、適切な実行ユニット１６へディスパッチする。検出された分岐のタイプによって、ＢＰＵ３０は、例えば、分岐目標アドレスの予測、および／または、特定の分岐がなされるか否かの予測を行うような、様々な分岐予測メカニズムを実行する。更に、ＢＰＵ３０は、分岐命令に関連する情報を含む分岐情報キュー３６を保持する。例えば、分岐情報キュー３６は、特定の分岐が無条件で採用されるかに関する表示、予測された目標アドレス、予測された分岐方向等を含む。分岐情報キュー３６は、分岐が正しく予測されたか、もしそうでない場合には、どこで命令取得を開始し、分岐履歴テーブル（図示せず）をどのようにして更新するかを決定するために、プロセッサ１０によって使用される。例えば、プロセッサ１０は、分岐が正しく予測されたかを判定するために、実行ユニット１６の１または複数によって決定された実際の結果を、分岐情報キュー３６に格納された予測結果と比較する。
【００１４】
本明細書で「分岐およびリンク命令」と称されるプロシージャ・コールに関連する分岐命令を命令取得ロジック２８が取得する場合、命令取得ロジック２８は、分岐およびリンク命令に従う連続する命令のアドレスを、リンク・スタック１２にプッシュする。次の連続する命令アドレスは、通常、プロシージャ・リターン命令のためのリターン・アドレスとして使用される。分岐およびリンク命令が、命令取得ロジック２８によって検出され予測される毎に、対応するリターン・アドレス値が、リンク・スタック１２にプッシュされる。そのため、リンク・スタック１２は、チェーン状またはリンクされた一連のプロシージャに関連付けられた予測リターン・アドレスのチェーンを含む。リンク・スタック１２が、サーキュラ・バッファとして実現される場合、命令取得ロジック２８は更に、リンク・スタック１２に最も直近にプッシュされたリターン・アドレス値に対応するリンク・スタック１２内のエントリを示すインデクス値を用いてリンク・スタック・ポインタ３８を更新する。そのため、リンク・スタック・ポインタ３８は、現在取得待ちのリンク・エントリを示す。一例において、リンク・スタック・ポインタ３８は、リンク・スタック１２上にプッシュされた新たなアドレス値に応答して、ポインタ・インデクスを、１リンク・スタック・エントリ位置に等しい分ずつインクリメントすることによって更新される。
【００１５】
本明細書で「分岐からリンクへの命令」と称されるプロシージャ・リターンに関連する分岐命令を命令取得ロジック２８が取得する場合、命令取得ロジック２８は、リンク・スタック１２から現在取得待ちのリターン・アドレスをポップする。特に、リンク・スタック・ポインタ３８に現在示されているリターン・アドレス値が、リンク・スタック１２からポップされ、予測されたリターン・アドレスに位置する命令が、ポップされたアドレス値によって示されたメモリ位置から取得される。例えば、予測されたリターン・アドレスに位置する命令は、命令キャッシュ２２、あるいは、ポップされたリターン・アドレス値に対応する外部メモリ内の位置から取得される。アドレス値がリンク・スタック１２からポップされた後、リンク・スタック・ポインタ３８内のポインタ・インデクスは、リンク・スタック１２内にキューされた次のリターン・アドレス値を示すようにデクリメントされる。
【００１６】
リンク・スタック・ポインタ３８は、命令ユニット１４内に含まれているか、あるいは、命令ユニット１４に関連付けられうる。リンク・スタック・ポインタ３８に含まれている現在のポインタ・インデクスは、ＢＰＵ３０によって、リンク・スタック１２から対応するリターン・アドレス値をポップすることとともに、例えば分岐情報キュー３６に格納される。格納されたポインタ・インデクスは次に、以下に詳細に説明するように、リターン・アドレス誤予測誤りが生じた後に、リンク・スタック１２を修復するために使用される。一例において、格納されたポインタ・インデクスは、パイプラインを通って、分岐命令とともに移動する。別の例において、現在のポインタ・インデクスは、例えば、予測された分岐情報または命令に関連する適切な情報のような命令情報とともに、ポインタ・インデクスを分岐情報キュー３６内に格納することによって、対応する予測分岐命令に関連付けられる。
【００１７】
他の実施形態では、リンク・スタック１２が、本当のプッシュ−ポップ・バッファ（図示せず）として実現される。ここでは、新たなアドレス値がリンク・スタック１２にプッシュされた場合、保存されたリターン・アドレス値がそれぞれ１スポット、シフトダウンされ、アドレス値がリンク・スタック１２からポップされた場合、１スポット、シフトアップされる。そのため、リンク・スタック・ポインタ３８は必要ではない。代わりに、分岐およびリンク命令に応答して、リターン・アドレス値が単にプッシュされ、分岐からリンクへの命令に応答して、リンク・スタック１２からポップされる。
【００１８】
図２のステップ１００に示すように、プロセッサ１０がリターン・アドレス誤予測誤りを検出した場合、プロセッサ１０は、訂正シーケンスを実行する。プロセッサ１０は、例えばソフトウェア・コードによってスキップされたプロシージャ・リターンおよびリンク・スタック・オーバフローのようなリターン・アドレス誤予測誤りを検出することができる。誤予測訂正は従来、パイプラインから推測的に取得された命令をフラッシュすることと、正しい命令ストリームを取得することとを含む。プロセッサ１０が、リターン・アドレス誤予測誤りを検出することに応答して、命令取得ロジック２８は、図２のステップ１０２に例示するように、リンク・スタック１２に、現在取得待ちのリターン・アドレス値をスキップさせることによって、リンク・スタック１２を修復する。ソフトウェアが、プロシージャ・リターンをスキップした場合、リンク・スタック１２からの現在取得待ちのリターン・アドレス値がスキップされないのであれば、リターン・アドレス誤予測誤りが自動的に生じ、どの介在する分岐およびリンク命令も、リンク・スタック１２上に値をプッシュさせないのであれば、次回、アドレスは、リンク・スタック１２からポップされる。リンク・スタック１２から現在取得待ちのアドレス値は、スキップされたプロシージャ・リターン命令に対応するので、誤りが発生する。そのため、ハードウェア・リンク・スタック１２から現在取得待ちのリターン・アドレス値をスキップすることは、リンク・スタックを、プロシージャ・コールおよびリターンのソフトウェア・チェーンに再同期させることによって、次のリンク・スタック・ポップ中にアドレス誤予測が発生する可能性を低減する。
【００１９】
図３は、サーキュラ・バッファを備えるリンク・スタック１２に対して現在取得待ちのリターン・アドレス値をスキップさせるプログラム・ロジックの１つの実施形態を例示する。リターン・アドレス値がリンク・スタック１２からポップされるごとに、ポップされたアドレス値に関連付けられたリンク・スタック・ポインタ・インデクス３８が、以前に説明したように保存される（ステップ１０４）。従って、ポップされたリターン・アドレス値に関連付けられたリンク・スタック・ポインタ・インデクスは、もし要求されれば、リンク・スタックを修復するために利用することができる。プロセッサ１０が、リターン・アドレス誤予測誤りを検出することに応答して、誤予測されたリターン・アドレスに関連付けられた保存されたポインタ・インデクスは、リンク・スタック１２に対して現在取得待ちのリターン・アドレス値をスキップさせることによってリンク・スタック１２を修復するために、命令取得ロジック２８によって使用される。特に、命令取得ロジック２８は、リンク・スタック・ポインタ３８内に含まれた現在のポインタ・インデスクを、２リンク・スタック・エントリ位置オフセットされた保存されたポインタ・インデクスと交換する（ステップ１０６）。１例において、命令取得ロジック２８は、保存されたリンク・スタック・ポインタ・インデクスを２リンク・スタック・エントリ位置、デクリメントすることができる、例えば算術倫理ユニット（図示せず）または加算回路（図示せず）のような論理回路に対するアクセスを含むかまたは有している。その結果、誤予測誤りを引き起こしたアドレス値から２エントリ位置離れている格納されたリターン・アドレス値が、リンク・スタック１２から現在取得待ちとなり、もって、次のプロシージャ・リターン・アドレス誤予測誤りの可能性を低減する。
【００２０】
図４は、プッシュ−ポップ・バッファを備えるリンク・スタック１２に対し、現在取得待ちのリターン・アドレス値をスキップさせるプログラム・ロジックの別の実施形態を例示する。プロセッサ１０が、誤予測されたリターン・アドレス値を検出することに応答して、命令取得ロジック２８は、リンク・スタック１２に対して、現在キューされているリンク・スタック・エントリ、すなわち、誤りを引き起こしたリターン・アドレス値の直後にキューされたエントリをポップさせることによって、リンク・スタック１２を修復する（ステップ１０８）。そして、命令取得ロジック２８は、リンク・スタック１２に対して、すぐ次のリターン・アドレス値をポップさせる。そのように、リンク・スタック１２は、２つの連続したポップを実行し、もって、誤予測されたアドレス値の直後に取得待ちになっているリターン・アドレス値をスキップする。特定のリンク・スタック実装にかかわらず、リンク・スタックに対して、誤予測されたアドレス値の直後の取得待ちのリターン・アドレス値をスキップさせることによって、分岐訂正シーケンスのうちの少なくとも１つの反復が回避される。
【００２１】
図５は、幾つかのチェーンされたまたはリンクされたリターン・アドレス値を、リンク・スタック１２上にプッシュさせ、それに従ってリンク・スタック・ポインタ３８が更新されるようにする一連の典型的なプログラム命令を例示する。例示するプログラム・フローに従って、プロシージャＡは、分岐およびリンク命令（ｂ１  ｐｒｏｃ＿ｂ）を用いてプロシージャＢを呼び出す。同様に、プロシージャＢは、プロシージャＣ（ｂ１  ｐｒｏｃ＿ｃ）を呼び出し、プロシージャＣはプロシージャＤ（ｂｌ  ｐｒｏｃ＿ｄ）を呼び出し、プロシージャＤはプロシージャＥ（ｂｌ  ｐｒｏｃ＿ｅ）を呼び出す。全体で、ネストされプロシージャＡにチェーンされた４つのプロシージャ・コールが存在する。そのため、予測されているか、または採用されることが知られた分岐およびリンク命令が検出される毎に、例えばａｄｄｒ＿ａ、ａｄｄｒ＿ｂのようなリターン・アドレス予測を可能とするために、対応するリターン・アドレス値がリンク・スタック１２上にプッシュされる。リンク・スタック１２上にプッシュされた各リターン・アドレスは、呼び出されたプロシージャが、例えばｒｅｔｕｒｎ＿ａ、ｒｅｔｕｒｎ＿ｂのようなプログラム制御を譲った後に取得される次の命令のメモリ位置に対応するメモリ・アドレスを特定する。リンク・スタック・ポインタ３８は、予測されたか知られている、採用された分岐およびリンク命令のそれぞれに応じて更新され、最も直近にプッシュされたスタック・エントリが、リンク・スタック・ポインタ３８によって示されるようになる。そのため、プロシージャ・リターン命令のチェーンに関連付けられた一連のアドレスが、リンク・スタック・ポインタ３８を用いて、プログラム命令に従ってリンク・スタック１２内に確立される。
【００２２】
この特定の例では、プロシージャＤがプロシージャＥを呼び出した後、プロシージャＤはもはや、分岐からリンクへの命令を除いて、いかなる実行命令も含まない。ここで、ｒｅｔｕｒｎ＿ｄは、分岐からリンクへの命令を示す。分岐からリンクへの命令は単に、プログラム制御をプロシージャＣへ戻す。そのため、プロシージャＥにおける最適化されたソフトウェア・コードは、この分岐からリンクへの命令（ｒｅｔｕｒｎ＿ｄ）をスキップし、プログラム制御をプロシージャＣ（ｒｅｔｕｒｎ＿ｃ）に直接的に戻す。従って、プロシージャＥに関連付けられた分岐からリンクへの命令が解決される場合、プログラム制御は、プロシージャＤには戻されず、プロシージャＣに直接的に戻される。これによって、プロシージャＤに関連付けられたプロシージャ・リターン命令が、プロシージャＥにおいて、最適化されたコードによってスキップされるようになる。しかしながら、リンク・スタック１２は、プロシージャ・リターンがスキップされたことに気づかない。その結果、リンク・スタック１２は、次のリターン（ａｄｄｒ＿ｃ）に関連付けられたアドレスの代わりに、スキップされたリターン（ａｄｄｒ＿ｄ）に関連付けられたアドレスを配信する。ここで、ソフトウェアは、プログラム・フローを変更している。従って、リンク・スタック・ポインタ３８が、プロシージャＤ（ａｄｄｒ＿ｄ）に関連付けられたリターン・アドレス値を、リンク・スタック１２からポップさせ、推論的に取得されるようにした場合に、リターン・アドレス誤予測誤りが引き起こるだろう。
【００２３】
図６は、図５に例示された典型的なプログラム命令に従ってリンク・スタック１２上に以前にプッシュされたリターン・アドレス値を、リンク・スタック１２からポップさせ、もって、誤予測誤りを引き起こす一連の典型的なプログラム命令を例示する。図６では、最適化されたコードによって決定された実際のプログラム・リターン・パスが、実線で示され、リンク・スタック１２と連携するリンク・スタック・ポインタ３８によって予測されたリターン・パスが、破線で示される。プロシージャＥの終わりにおいて分岐からリンクへの命令に遭遇すると、リンク・スタック・ポインタ３８が、プロシージャＤ（ａｄｄｒ＿ｄ）に関連付けられたリターン・アドレス値を指す。そのため、ａｄｄｒ＿ｄがリンク・スタック１２からポップされ、対応する命令（ｒｅｔｕｒｎ＿ｄ）が取得される。しかしながら、プロシージャＤ（ａｄｄｒ＿ｄ）に関連付けられたリターン・アドレス値を使用することは、アドレス誤予測誤りを引き起こす。なぜなら、実際のアドレスは、プロシージャＥにおいて最適化されたコードによって示されるように、プロシージャＣ（ａｄｄｒ＿ｃ）に関連付けられたリターン・アドレス値だからである。
【００２４】
アドレス誤予測に応答して、前述したように、プロセッサ１０によって訂正シーケンスが実行される。従来のプロセッサに含まれた従来式のリンク・スタックは、アドレス誤予測に応じて修復されないと注目するのが適切である。そのため、最初のアドレス誤予測が生じた後、リターン・アドレス値が従来式のリンク・スタックからポップされる毎に、訂正シーケンスが実行される。すなわち、従来のリンク・スタック・ポインタは、最初のアドレス誤予測が生じた後、従来式のリンク・スタックから引き続きエントリがポップされる毎に、誤ったリターン・アドレスを示すだろう。なぜなら、従来のリンク・スタックは、アドレス誤予測誤りに応じた修正がなされないからである。そのため、最初のアドレス誤予測の後、従来式のリンク・スタックから次にポップされた各リターン・アドレス値は、従来式のプロセッサに対して、訂正シーケンスを実行させる。なぜなら、従来式のリンク・スタック・ポインタは、正しいエントリから少なくとも１リンク・スタック・エントリ離れたものを指すからである。
【００２５】
再び図６に示すように、命令取得ロジック２８は、リターン・アドレス誤予測誤りを持つ分岐からリンクへの命令に関連付けられた保存されたリンク・スタック・ポインタ・インデクスを取得する。そして、命令取得ロジック２８は、リンク・スタック・ポインタ３８に含まれる現在のリンク・スタック・ポインタ・インデクスを、２リンク・スタック・エントリ位置オフセットされた保存されたリンク・スタック・ポインタ・インデクスと交換することによって、リンク・スタック１２を修復する。そのため、プロシージャＣが、最終的にプロシージャＢに制御を返す場合、リンク・スタック・ポインタ３８は、プロシージャＣ（ａｄｄｒ＿ｃ）に関連付けられたリターン・アドレス値を指さず、代わりに、プロシージャＢ（ａｄｄｒ＿ｂ）に関連付けられたリターン・アドレス値を指すだろう。したがって、図６に図示された例において、その後のリターン・アドレス誤予測誤りが阻止される。
【００２６】
上記変形および応用の範囲を念頭におき、本開示は、上述の説明に限定されるのでも、添付図面にも限定されないことが理解されるべきである。その代わり、本開示は、特許請求の範囲と、その法的な均等物によってのみ限定される。
【図面の簡単な説明】
【００２７】
【図１】図１は、修復可能なリンク・スタックを含むプロセッサの実施形態を図示するブロック図である。
【図２】図２は、プロセッサに含まれたリンク・スタックを修復するプログラム・ロジックの実施形態を図示するロジック・フロー図である。
【図３】図３は、プロセッサに含まれたリンク・スタックを修復するプログラム・ロジックの別の実施形態を図示するロジック・フロー図である。
【図４】図４は、プロセッサに含まれたリンク・スタックの修復するプログラム・ロジックの更に別の実施形態を図示するロジック・フロー図である。
【図５】図５は、修復可能なリンク・スタックを用いてリンクされる一連のネスト・プロシージャ・リターンを図示するプログラム命令フロー図である。
【図６】図６は、修復可能なリンク・スタックを使用して、図５に例示されたネスト・プロシージャ・リターンのデリンクを例示するプログラム命令フロー図である。
【図１】
2009528637.tif 000003
【図２】
2009528637.tif 000004
【図３】
2009528637.tif 000005
【図４】
2009528637.tif 000006
【図５】
2009528637.tif 000007
【図６】
2009528637.tif 000008
【国際調査報告】
2009528637.tif 000009
2009528637.tif 000010