(57)【特許請求の範囲】
【請求項１】
復帰スタックを管理する方法であって、
プロセッサにより、プロシージャ呼出しの連鎖系列中のプロシージャ呼出しの数をカウントすることにより、復帰命令に関連する復帰レベルの数を決定すること、
前記プロセッサにより、その数の復帰アドレスを前記復帰スタックからポップすること、および
前記プロセッサにより、前記復帰スタックから最後にポップされた復帰アドレスを、命令プリフェッチングのための予測復帰アドレスとして命令プリフェッチユニットに与えることを含む、方法。
【請求項２】
復帰命令に関連する復帰レベルの数を決定することが、前記復帰命令に関連する復帰レベル標識値を読み取ることを含む、請求項１に記載の方法。
【請求項３】
前記復帰命令に関連する復帰レベル標識値を読み取ることが、前記復帰命令に埋め込まれた値を読み取ることを含む、請求項１に記載の方法。
【請求項４】
復帰命令に関連する復帰レベルの数を決定することが、埋込み復帰レベル標識を復帰命令が有しているかどうかを判定することを含み、有している場合は、前記復帰レベル標識を読み取ることによって復帰レベルの数を決定することを含み、そうでない場合は、前記復帰スタックのデフォルト復帰レベル設定に基づき復帰レベル標識の数を決定することを含む、請求項１に記載の方法。
【請求項５】
前記復帰スタックが、埋込み復帰レベル標識を欠いている復帰命令に対しては前記復帰スタックから１つの復帰アドレスをポップするように、また、埋込み復帰レベル標識を有する復帰アドレスに対しては前記復帰スタックから標識で示される数の復帰アドレスをポップするように、前記プロセッサにより、前記復帰スタックの前記デフォルト復帰レベル設定を１に設定することをさらに含む、請求項４に記載の方法。
【請求項６】
復帰命令に関連する復帰レベルの数を決定することが、連鎖プロシージャ呼出しを検出すること、所与の一連のプロシージャ呼出しのネスティング深さをトラッキングすること、および前記ネスティング深さに応じて前記所与の一連のプロシージャ呼出し中の最後の復帰命令に対する復帰レベルの数を設定することを含む、請求項１に記載の方法。
【請求項７】
複数の復帰アドレスを記憶するように構成された復帰スタックと、
復帰アドレスを前記復帰スタックに順次プッシュし、復帰アドレスを前記復帰スタックから順次ポップするように構成され、プロシージャ呼出しの連鎖系列中のプロシージャ呼出しの数をカウントすることによって所与の復帰命令に関連する復帰レベルの数を決定し、その数の復帰アドレスを前記復帰スタックからポップするように構成され、前記復帰スタックから最後にポップされた復帰アドレスを命令プリフェッチングのための予測復帰アドレスとして命令プリフェッチユニットに与えるように構成された復帰スタックコントローラとを含む、復帰スタック回路。
【請求項８】
前記復帰スタックコントローラが、前記所与の復帰命令に関連する復帰レベル標識値を読み取ることによって復帰命令に関連する復帰レベルの数を決定するように構成された、請求項７に記載の復帰スタック回路。
【請求項９】
前記復帰スタックコントローラが、前記所与の復帰命令に埋め込まれた値を前記復帰レベル標識として読み取るように構成された、請求項７に記載の復帰スタック回路。
【請求項１０】
前記復帰スタックコントローラが、埋込み復帰レベル標識を前記所与の復帰命令が有しているかどうかを判定することによって、前記所与の復帰命令に関連する復帰レベルの数を決定し、
埋込み復帰レベル標識を前記所与の復帰命令が有している場合は、前記復帰レベル標識を読み取ることによって復帰レベルの数を決定し、
埋込み復帰レベル標識を前記所与の復帰命令が有してない場合は、前記復帰スタックのデフォルト復帰レベル設定に基づき復帰レベル標識の数を決定するように構成された、請求項７に記載の復帰スタック回路。
【請求項１１】
前記復帰スタックが、埋込み復帰レベル標識を欠いている復帰命令に対しては前記復帰スタックから１つの復帰アドレスをポップするように、また、埋込み復帰レベル標識を有する復帰命令に対しては前記復帰スタックから標識で示される数の復帰アドレスをポップするように、前記復帰スタックコントローラが前記復帰スタックの前記デフォルト復帰レベル設定を１に設定するようにさらに構成された、請求項１０に記載の復帰スタック回路。
【請求項１２】
前記復帰スタックコントローラが、連鎖プロシージャ呼出しを検出すること、所与の一連のプロシージャ呼出しのネスティング深さをトラッキングすること、および前記ネスティング深さに応じて前記所与の一連のプロシージャ呼出し中の最後の復帰命令に対する復帰レベルの数を設定することによって、前記所与の復帰命令に関連する復帰レベルの数を決定するように構成された、請求項７に記載の復帰スタック回路。
【請求項１３】
プロシージャ呼出しの連鎖系列中のプロシージャ呼出しの数をカウントすることにより、復帰命令に関連する復帰レベルの数を決定し、復帰命令に関連する復帰レベルの数を決定することが、連鎖プロシージャ呼出しを検出すること、所与の一連のプロシージャ呼出しのネスティング深さをトラッキングすること、および前記ネスティング深さに応じて前記所与の一連のプロシージャ呼出し中の最後の復帰命令に対する復帰レベルの数を設定することを含み、および
その数に対応する値に、前記復帰命令に関連する復帰レベル標識を設定することを含む、コンピュータプログラムコンパイルの方法。
【請求項１４】
前記その数に対応する値に、前記復帰命令に関連する復帰レベル標識を設定することが、前記復帰命令に埋め込まれた値に設定することを含む、請求項１３に記載の方法。
【請求項１５】
プロシージャ呼出しの連鎖系列に対する命令プリフェッチングのための復帰アドレスを予測する方法であって、
プロセッサにより、プロシージャ呼出しの連鎖系列中のプロシージャ呼出しの数をカウントすることと、
前記プロセッサにより、前記カウントされたプロシージャ呼出しの連鎖系列中のプロシージャ呼出しの数を使用することにより、プロシージャ呼出しの前記連鎖系列中の最後のプロシージャ呼出しの復帰アドレスの代わりに、プロシージャ呼出しの前記連鎖系列中の第１のプロシージャ呼出しの復帰アドレスを代用することと、
前記プロセッサにより、前記代用の復帰アドレスを命令プリフェッチングに与えることとを含む、方法。
【請求項１６】
所与の現在のプログラムプロシージャに関し、次のプログラムプロシージャへの呼出しが現在のプロシージャの復帰命令より前の最後の命令であることを認識することによってプロシージャ呼出しの連鎖系列を検出することをさらに含む、請求項１５に記載の方法。
【請求項１７】
前記プロセッサにより、プログラムコンパイル中にプロシージャ呼出しの連鎖系列を検出することをさらに含む、請求項１５に記載の方法。
【請求項１８】
前記プロセッサにより、プログラム実行中にプロシージャ呼出しの連鎖系列を検出することをさらに含む、請求項１５に記載の方法。
【請求項１９】
プロシージャ呼出しの前記連鎖系列中の最後のプロシージャ呼出しの復帰アドレスの代わりに、プロシージャ呼出しの前記連鎖系列中の第１のプロシージャ呼出しの復帰アドレスを代用することが、プロシージャ呼出しの前記連鎖系列中の連続したプロシージャ呼出しに対する復帰スタックに復帰アドレスを順次プッシュすること、および前記最後のプロシージャ呼出しに対する復帰命令に応答して、前記第１のプロシージャ呼出しの前記復帰アドレスを得るのに必要な回数だけ前記復帰スタックをポップすることを含む、請求項１５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にマイクロプロセッサに関し、詳細には、プロシージャ呼出しからの復帰を速めるために、いくつかのタイプのマイクロプロセッサによって使用されるハードウェア復帰スタックを管理することに関する。
【背景技術】
【０００２】
高度な機能性を必要とする多くの増え続ける用途にマイクロプロセッサが導入されるので、マイクロプロセッサの実行速度を増大させることが望ましい。加えて、バッテリ電力が限定された携帯型電子機器などの組込み型応用例では、マイクロプロセッサの電力消費を低減させることが望ましい。しかし、マイクロプロセッサのクロック速度を単に増大させるだけでは、様々な入力／出力のボトルネックがマイクロプロセッサの実際の性能に制約を課すので、望まれるシステム性能の向上を得ることができない。例えば、オフチップメモリアクセスは一般に、オンチップメモリアクセスよりも実行が遅く、そのため命令技法およびデータキャッシング技法が使用される。縮小命令セットコンピュータ（ＲＩＳＣ）は、一般にクロックサイクルごとに１つまたは複数の命令を出し、また、性能を向上させるために、しばしば命令キャッシングを使用する。パイプラインＲＩＳＣプロセッサは、クロックサイクルごとに複数の命令を出すことができ、一般にデータおよび命令キャッシングを頻繁に使用する。
【０００３】
命令キャッシング（「プリフェッチング」）は未来の命令を予測し、その命令を実行するマイクロプロセッサより前に、それをオンチップ命令キャッシュに入れる。正しい命令がプリフェッチされた場合、プリフェッチングは、オフチップ命令メモリが遅いことに伴う遅延の多くを除去することができる。ほとんどの命令は順次に実行され、信頼性のあるプリフェッチをすることができる。条件ブランチ命令は、通常、パイプラインの深くでのみ評価されるブランチ条件に応じて、ブランチを「取る」ことができたりできなかったりする。この評価を待つ際の遅延を回避するために、ブランチ命令の動作はしばしばパイプライン内で早期に予測され、命令は、予測されたブランチ先アドレスからプリフェッチされる。命令プリフェッチ法は、静的および動的な命令プリフェッチングを両方含む。
【０００４】
動的命令プリフェッチングは、命令実行履歴に依拠し、例えば所与の数の最も最近の条件ブランチ命令に対して用いられた、または用いられなかった以前の予測の精度をトラッキングすることを含めてよい。静的プリフェッチングは、一般に実行履歴に依拠せず、例えば、初めて条件ブランチに出会ったときに使用することができる。静的プリフェッチングが性能優位性を示すブランチ命令の１つのタイプは、呼び出されたプロシージャからの復帰命令であり、プロシージャの復帰アドレスが予測されて、その予測された復帰アドレスから始まる命令のプリフェッチングをサポートする。
【０００５】
「復帰スタック」は、プロシージャ呼出し復帰命令に対する復帰アドレスの静的予測をサポートするために使用することができる。典型的な復帰スタックは、多重レベルバッファを含む。プロシージャ呼出し命令が予測または認識された場合に、対応する復帰アドレスをマイクロプロセッサの命令パイプラインの実行段階から取り出し、復帰スタックにプッシュすることができる。逆に、プロシージャ復帰命令が予測または認識された場合には、復帰スタックの最上部に現在ある復帰アドレスがそのスタックからポップされ、命令プリフェッチングのための予測復帰アドレスとして使用される。
【０００６】
したがって、復帰スタックを管理する従来の手法では、対応する予測復帰アドレスは、プロシージャ呼出しが発生したときに復帰スタックに順次プッシュされる。逆に復帰アドレスは、プロシージャ復帰命令が発生したときにスタックから順次ポップされる。この従来の手法では、多重レベルプロシージャ呼出しにおいて、プロシージャ復帰アドレスを誤って予測し、その場合、連鎖中の連続する各プロシージャ呼出しの復帰命令が前のプロシージャ呼出しの復帰命令に戻るように指すという点で、連続したプロシージャ呼出しが一緒に「連鎖される」。
【０００７】
最適には、連鎖中の最後のプロシージャの復帰命令に対して予測されるべき復帰アドレスは、連鎖中の最初のプロシージャ呼出しに対応する復帰アドレスである。しかし、連続したプロシージャ呼出しは、ネストされた各プロシージャ呼出しの復帰アドレスを復帰スタックに順次プッシュすることになるので、最後のプロシージャ呼出しの復帰命令に対してポップされる復帰アドレスは、連鎖中の直前の呼出プロシージャの復帰アドレスである。プリフェッチングがそのアドレスから続く場合、フェッチされる次の命令は、復帰スタックを再びポップする別の復帰になる。このように復帰スタックを連続してポップすることは、不必要にプロセッサの性能を低下させ、電力を浪費する。
【発明の概要】
【０００８】
本発明は、多重レベルプロシージャ呼出しにおいて、最初のトップレベル呼出プロシージャの復帰アドレスをマイクロプロセッサが正しく予測できるようにする方法および装置を含む。このような多重レベルプロシージャ呼出しは、一連の連続した２つ以上のプロシージャ呼出しを含み、連続する各プロシージャの復帰アドレスが、直前のプロシージャの復帰命令に戻るように指している。連鎖中の呼び出された最後のプロシージャにおける復帰命令の目標として最後にプッシュされた復帰アドレスを与える代わりに、本発明の１つまたは複数の実施形態による復帰スタック回路は、引き続いて呼び出されたプロシージャの連鎖中の復帰レベルの数に等しい数の復帰アドレスをスタックから順次ポップする。そうする際、復帰スタック回路は、最初の呼出プロシージャの復帰アドレスを検索し、これを命令プリフェッチユニットに命令プリフェッチングの目標として与えることができる。
【０００９】
したがって、一実施形態では、本発明は、復帰命令に関連する復帰レベルの数を決定し、その数の復帰アドレスを復帰スタックからポップすることに基づき復帰スタックを管理する方法を含む。最後にポップされたアドレスは、命令プリフェッチングの目標アドレスとして命令プリフェッチユニットに与えることができる。所与の復帰命令に対する予測復帰アドレスを得るためにスタックからポップされるべき復帰アドレスの数は、復帰命令に関連する静的レベル標識値から読み出すことができ、あるいは、プログラム実行中にオンザフライで（ｏｎ  ｔｈｅ  ｆｌｙ）決定することができる。
【００１０】
一実施形態では、レベル標識は、復帰命令に埋め込まれたフィールドまたはタグを含むことができ、その値はコンパイル時に決定されている。したがって、本発明は、コンパイラ論理が、復帰命令に関連する復帰レベルの数を決定し、その数に対応する値に復帰命令と関連する復帰レベル標識を設定する、プログラムコンパイルの方法を含む。復帰レベルの数を決定するために、コンパイラは、プロシージャ呼出しの連鎖系列中のプロシージャ呼出しの数をカウントすることができる。一般に、コンパイラは、連鎖プロシージャ呼出しを検出し、プロシージャ呼出しの所与の連鎖のネスティング深さをトラッキングし、そのネスティング深さに応じてプロシージャ呼出しの所与の連鎖中の最後の復帰命令に対する復帰レベルの数を設定することによって、復帰命令に関連する復帰レベルの数を決定する。
【００１１】
別の実施形態では、マイクロプロセッサ内の復帰スタック回路または他のサポート論理が、所与の復帰命令に関連する復帰レベルの数を実行時に動的に決定する。この構成では、コンパイル時に復帰レベル標識を記憶する必要がない。実行時の復帰レベルの決定は、コンパイル時の実施形態に使用されるものと同様な方法に基づくことができる。例えば、サポート論理は、プロシージャ呼出しの連鎖系列中のプロシージャ呼出しの数をカウントし、そのカウントに基づき最後に呼び出されたプロシージャの復帰命令に対する復帰レベル値を設定することができる。より一般には、動的な実行時トラッキングは、連鎖プロシージャ呼出しを検出すること、プロシージャ呼出しの所与の一連のネスティング深さをトラッキングすること、およびそのネスティング深さに応じて所与の一連のプロシージャ呼出しの最後の復帰命令に対する復帰レベルの数を設定することを含む。
【図面の簡単な説明】
【００１２】
【図１】マイクロプロセッサを示すブロック図である。
【図２】図１のマイクロプロセッサに使用されている復帰スタックを示すブロック図である。
【図３】連続した連鎖プロシージャ呼出しを含む多重レベルプロシージャ呼出しを示す、プログラム命令の流れ図である。
【図４】所与の多重レベルプロシージャ呼出し中の復帰レベルの数にしたがって復帰スタックをポップするプロセスを示す論理流れ図である。
【図５】埋込み復帰レベル標識を含む、コンパイラ生成復帰命令のブロック図である。
【図６】所与の復帰命令に埋め込まれた、あるいは付随したレベル標識によって示される回数だけ復帰スタックをポップするプロセスを示す論理流れ図である。
【図７】多重レベルプロシージャ呼出しを検出し、そのような多重レベルプロシージャ呼出し内の呼出ネスティング深さをトラッキングし、かつそのトラッキングされた深さに基づき復帰レベルを設定するためのプロセスを示す論理流れ図である。
【発明を実施するための形態】
【００１３】
図１は、プロセッサコア１２、命令プリフェッチユニット１４、命令キャッシュ１６、命令キャッシュコントローラ１８、ロード／記憶ユニット２０、データキャッシュ２２、データキャッシュコントローラ２４、および主トランスレーションルックアサイドバッファ（ｔｒａｎｓｌａｔｉｏｎ  ｌｏｏｋａｓｉｄｅ  ｂｕｆｆｅｒ）２６を含む、マイクロプロセッサ１０を少なくとも部分的に示す。非限定的な例として、マイクロプロセッサ１０は、縮小命令セットコンピュータ（ＲＩＳＣ）アーキテクチャに基づくパイプラインプロセッサとすることができる。
【００１４】
１つまたは複数の実施形態では、コア１２は、１つまたは複数の多段命令パイプラインを備える命令実行ユニット（図示せず）を含む。動作の際、コア１２はプログラム命令を実行し、また対応するロード／記憶データ操作を実行する。トランスレーションルックアサイドバッファ２６は、コア１２からの入力を受け入れ、コア１２に出力を与える。より具体的には、トランスレーションルックアサイドバッファ２６は、命令キャッシュ１６およびデータキャッシュ２２それぞれとコア１２のインターフェースをとる。命令キャッシュ１６およびデータキャッシュ２２は高速のオンボードメモリを含み、マイクロプロセッサ１０は、次に必要な命令およびデータでキャッシュを満たしておくために、命令キャッシュコントローラ１８およびデータキャッシュコントローラ２４を介して命令およびデータプリフェッチングを使用する。
【００１５】
特に、マイクロプロセッサ１０の命令プリフェッチング動作は、呼び出されたプロシージャからの復帰についての命令ストリームの予測を含む。プロシージャ復帰のアドレスを予測すると、プロシージャが完了した後に最も必要とされそうな命令のプリフェッチをマイクロプロセッサ１０が開始できるようになることによって、性能が向上する。
【００１６】
図２は、プロシージャ復帰命令の目標アドレスを予測するためにコア１２によって使用される復帰スタック回路３０の一実施例を示す。図示の復帰スタック回路３０は、復帰スタック３２、および付随する復帰スタックコントローラ３４を含む。一時記憶レジスタを復帰スタックコントローラ３４の制御のもとで論理的に一緒にリンクさせて、復帰スタック３２を形成することができる。様々なバッファ構成を実施することができるが、一実施形態では、復帰スタック３２は後入れ先出しメモリスタックとして構成される。
【００１７】
コアの命令パイプライン（図示せず）中の命令実行ユニットがプロシージャ呼出しを予測またはその他の方法で認識したとき、復帰スタックコントローラ３４は、対応する復帰アドレスを受け取り、それを復帰スタック３２にプッシュする。すなわち、復帰スタックコントローラ３４は、プロシージャ呼出しが予測されると１度に１つずつプロシージャ復帰アドレスを復帰スタック３２に順次プッシュする。プロシージャ復帰命令が発生または予測されると、復帰スタックコントローラ３４は通常、そのプロシージャ復帰アドレスをポップして、それを命令プリフェッチユニット１４に与える。
【００１８】
しかし、従来の復帰スタック管理方法に反して、復帰スタックコントローラ３４は、復帰スタック３２から１度に１つだけの復帰アドレスをポップすることによって命令プリフェッチングのための復帰アドレスを常に得るのではない。実際のところ、復帰スタックコントローラ３４は一般に、復帰アドレスを復帰スタック３２に順次プッシュするように、また、復帰アドレスを復帰スタック３２から順次ポップするように構成されるが、特に、所与の復帰命令に関連する復帰レベルの数を決定するように、また、その数の復帰アドレスを復帰スタック３２からポップするように構成される。次いで、最後にポップされた復帰アドレスが予測プロシージャ復帰アドレスとしてプリフェッチユニット１４に与えられる。
【００１９】
複数のアドレスを１度に復帰スタック３２からポップできることにより、復帰スタックコントローラ３４は、多重レベルプロシージャ呼出し中の最初のトップレベル呼出プロシージャの復帰アドレスを正しく予測することができる。このような多重レベルプロシージャ呼出しは、一連の連続した２つ以上のプロシージャ呼出しを含み、連続する各プロシージャの復帰アドレスが、直前のプロシージャの復帰命令に戻るように指している。
【００２０】
図３は、多重レベルプロシージャ呼出しを含むいくつかのプロシージャ呼出しを有する、一連のプログラム命令を示す。図示のプログラム流れによれば、「主」プログラムは、「ｐｒｏｃ１」と呼ばれるプロシージャへの呼出しを含む。ｐｒｏｃ１のプロシージャは、「ｐｒｏｃ２」と呼ばれるプロシージャへの呼出しを含む。ｐｒｏｃ２のプロシージャは、「ｐｒｏｃ３」と呼ばれるプロシージャへの呼出しを含む。
【００２１】
したがってｐｒｏｃ１は、連続したプロシージャ呼出しのリンク連鎖中の最初のトップレベルプロシージャを含む。プロシージャ連鎖は、連続して呼び出された各プロシージャ中の復帰命令に対する復帰アドレスが、直前のプロシージャの復帰命令に戻るように「指す」ことを特徴とする。つまり、ｐｒｏｃ３の復帰命令に対する復帰アドレスは、ｐｒｏｃ２の復帰命令のアドレスであり、ｐｒｏｃ２の復帰命令に対する復帰アドレスは、最初の呼出プロシージャであるｐｒｏｃ１の後の次の命令のアドレスである。
【００２２】
図４は、図３のプログラム流れに対する復帰スタックコントローラ３４の動作を示す。主プログラムは、アドレス「ｂ１」にプロシージャｐｒｏｃ１への呼出命令を含み、したがって、復帰スタックコントローラ３４は、復帰アドレスｂ１＋１を復帰スタック３２にプッシュする（ステップ１００）。次にプロシージャｐｒｏｃ１は、アドレス「ｂ２」にプロシージャｐｒｏｃ２への呼出命令を含み、したがって、復帰スタックコントローラ３４は、復帰アドレスｂ２＋１を復帰スタック３２にプッシュする（ステップ１０２）。最後に、プロシージャｐｒｏｃ２は、アドレスｂ３にプロシージャｐｒｏｃ３への呼出命令を含み、したがって、復帰スタックコントローラ３４は、復帰アドレスｂ３＋１を復帰スタック３２にプッシュする（ステップ１０４）。この順番のプッシュにより、復帰アドレスｂ３＋１、ｂ２＋１、およびｂ１＋１を保持する復帰スタック３２が得られ、ｂ３＋１は復帰スタック３２の先頭に保持されている。
【００２３】
ｐｒｏｃ３の復帰命令の場合、復帰スタック管理の従来の方法では、一番上のスタック値であるｂ３＋１をポップし、それを命令プリフェッチングのための予測復帰アドレスとして使用する。こうするとｐｒｏｃ２の復帰命令がフェッチされ、それにより復帰スタック３２がアドレスｂ２＋１をポップすることになり、このためｐｒｏｃ１の復帰命令がフェッチされ、それにより復帰スタック３２がｂ１＋１をポップすることになる。この連続した復帰スタックポッピングおよび命令プリフェッチングは、電力もプロセッサ実行時間も浪費して、性能に悪影響を及ぼす。連続したプロシージャ呼出しの連鎖性質のために、実際の復帰アドレス位置は、最初のトップレベル呼出プロシージャであるｐｒｏｃ１中のｂ１＋１である。したがって、復帰スタックコントローラ３４は、それが復帰スタック３２からポップしなければならないレベルの数を決定することによって性能を最適化して、ｐｒｏｃ３の復帰命令に対する正しいトップレベル復帰アドレスを得る（ステップ１０６）。
【００２４】
復帰スタックコントローラ３４は、その数の復帰アドレスを復帰スタック３２からポップし（ステップ１０８）、最後にポップされた復帰アドレス（ここではｂ１＋１）をプリフェッチユニット（ＰＦＵ）１４の予測復帰アドレスとして使用する（ステップ１１０）。この論議では、復帰アドレスを復帰スタック３２にプッシュし、また復帰スタック３２からポップする観点で動作説明を構成しているが、このような動作は、スタックポインタを必要に応じ論理的に移動させることに基づくものとしてよく、それによって復帰スタック３２中の指示値が命令プリフェッチングのために使用される復帰アドレスを表すようになることを理解されたい。
【００２５】
図４は、復帰スタックコントローラの能力の非限定的な例であり、復帰スタック３２に記憶された中間の復帰アドレスを飛び越すことができ、また、一連の連続したプロシージャ呼出し中の最初のトップレベルプロシージャに対応する復帰アドレスを、その連鎖中の最後のプロシージャの復帰命令を予測することにより、あるいは別な方法でその復帰命令に出会うことにより与えることができる。より一般的には、復帰スタックコントローラ３４は、所与の復帰命令に関連する復帰レベルの数を決定し、対応する回数だけ復帰スタック３２をポップして命令プリフェッチングのための復帰アドレスを得るように構成される。
【００２６】
図５は、任意の所与の復帰命令に関連する復帰レベルの数を決定するための１つの機構を示し、この復帰命令は、復帰レベルの数をその値が示す復帰レベル標識を含み、あるいはそれと関連している。すなわち、１つまたは複数の実施形態では、マイクロプロセッサ１０によって認識され使用される命令セットは、復帰操作符号（「操作符号（ｏｐｃｏｄｅ）」）と、操作符号と共に埋め込まれた、または別な方法でそれとリンクされた復帰レベル標識フィールドまたは復帰レベル標識タグとを備える復帰命令を含む。したがって、図６に示されるように、任意の所与の復帰命令に関連する復帰レベルの数を決定することは、命令の復帰レベルフィールドまたは復帰レベルタグを読み取ることを含む。
【００２７】
復帰スタックコントローラ３４は、図６の論理の処理を実施するように構成することができ、所与の復帰命令が復帰レベル標識を含んでいるか、あるいはそれと関連しているかどうかを判定する（ステップ１２０）。含んでいる、あるいは関連している場合は（ステップ１２２）、復帰スタックコントローラ３４は、対応する回数だけ復帰スタック３２をポップして（ステップ１２４）、命令プリフェッチングのための復帰アドレスを得る。そうでない場合は（ステップ１２２）、復帰スタックコントローラ３４は、デフォルト回数だけ復帰スタック３２をポップして（ステップ１２６）、命令プリフェッチングのための復帰アドレスを得る。デフォルト回数は、例えば１回とすることができる。
【００２８】
一実施形態では、プログラムコンパイラは、復帰命令ごとに復帰レベル標識を生成するように構成することもでき、したがって、復帰スタックコントローラ３４は常に、復帰命令ごとに対応する復帰レベル標識値を読み取り、それに応じて復帰スタックポッピングを制御するように構成することができる。しかし、図６に示されるように、プログラムコンパイラは、復帰レベルの数が省略値の１を超える場合だけ復帰レベル標識を生成してもよい。言い換えると、第１のタイプの復帰命令は復帰レベル標識を含まず、復帰スタックコントローラ３４は、このことを復帰スタック３２が１度ポップされるべきという暗黙の標識として認識するように構成される。第２のタイプの復帰命令は復帰レベル標識を含み、復帰スタックコントローラは、その復帰レベル標識の値を使用してスタックポッピングを制御するように構成される。
【００２９】
プログラムコンパイラの１つまたは複数の実施形態は、図７に示された処理論理にしたがって復帰命令の復帰レベル標識を生成するように構成されてもよい。コンパイラは、連続した２つ以上のプロシージャ呼出しが多重レベルプロシージャ呼出しとして一緒に連鎖されているかどうかを判定するように構成することができる（ステップ１３０）。コンパイラは、例えば、呼び出されたプロシージャの復帰命令が呼出プロシージャの復帰命令に戻るように指しているかどうかを判定することによって、多重レベルプロシージャ呼出しを認識することができる。
【００３０】
所与のプロシージャ呼出しが多重レベルプロシージャ呼出し連鎖の一部ではない場合、コンパイラは、呼出レベルカウンタなどの復帰レベルトラッキング情報をクリアし（ステップ１３２）、通常のコンパイル動作を必要に応じ継続することができる。しかし、コンパイラが多重レベルプロシージャ呼出しを検出した場合、コンパイラは、多重レベルプロシージャ呼出しのネスティング（呼出）深さをトラッキングする。ネスティング深さをトラッキングする１つの方法は、連続して連鎖したプロシージャ呼出しをカウントすることを含む（ステップ１３４）。したがってコンパイラは、多重レベルプロシージャの呼出深さを累算するためのカウンタを保持することがある。
【００３１】
連鎖中の最後のプロシージャの復帰命令を検出すると（ステップ１３６）、コンパイラは、トラッキングされたカウントに基づいて、その命令に対する復帰レベル標識を設定する（ステップ１３８）。すなわち、上記で説明したように、コンパイラは、累算されたカウントに基づき、その最後のプロシージャの復帰命令に対する復帰レベル標識の値を設定することができる。したがって、コンパイル時にこの値を設定すると、実行時に、すなわちコンパイルされたプログラムコードをマイクロプロセッサ１０が実行しているときに、復帰スタックコントローラ３４が多重レベル復帰アドレス予測を実行できるようになる。
【００３２】
図７の処理論理が、復帰スタックコントローラ３４によって、またはマイクロプロセッサ１０内の他のサポート論理によって実行される、動的な実行時処理として実施されてよいことも理解されたい。例えば、復帰スタックコントローラ３４は、多重レベルプロシージャを検出するための実行時処理中にコアの命令実行ユニットまたは他の論理回路と協働するように構成することができ、それらのプロシージャの呼出深さをトラッキングするように構成することができ、またトップレベル復帰アドレスを予測するための適切な復帰レベル標識を生成するように構成することができる。したがって、復帰スタックコントローラ３４、またはコア１２内の他の回路は、必要な論理回路と、連鎖プロシージャ呼出しの認識、連鎖プロシージャ呼出しの呼出深さのトラッキング／カウント、および復帰アドレス予測を制御するための対応する復帰レベル標識値の生成のために必要なメモリ回路要素とを用いて構成することができる。
【００３３】
一般に、復帰レベルの数は、コンパイル時または実行時に決定することができる。どちらの場合でも、所与の命令に関連する復帰レベルの数は、連鎖系列中のプロシージャ呼出しをカウントすることによって、その連鎖中の最後のプロシージャの復帰命令に対して予測される復帰アドレスが、連鎖中の直前のプロシージャのアドレスではなくトップレベルの最初の呼出プロシージャの復帰アドレスになるように決定することができる。
【００３４】
どんな場合でも、マイクロプロセッサ１０は、プロシージャ呼出しの連鎖系列中の最後のプロシージャ呼出しの復帰アドレスの代わりに、プロシージャ呼出しの連鎖系列中の第１のプロシージャ呼出しの復帰アドレスを代用すること、およびその代用の復帰アドレスを命令プリフェッチングに与えることに基づいて、プロシージャ呼出しの連鎖系列に対する命令プリフェッチングのための復帰アドレスを予測する方法を実施する。連鎖プロシージャ呼出しは、所与の現在のプログラムプロシージャに関し、次のプログラムプロシージャへの呼出しが現在のプロシージャの復帰命令より前の最後の命令であることを認識することによって検出することができる。このようにして、マイクロプロセッサ１０の性能は、不必要な中間復帰命令がマイクロプロセッサの命令パイプラインにフェッチされ実行されることがないので、連鎖プロシージャ呼出しの実行に際して最適化される。
【００３５】
１つまたは複数の実施形態についての上述の議論は本発明を限定せず、添付の図もまた限定しないことを当業者は理解されよう。正しくは、本発明は添付の特許請求の範囲、およびそれらの法的等価物によってのみ限定される。
【図１】
0005579694.tif 000002
【図２】
0005579694.tif 000003
【図３】
0005579694.tif 000004
【図４】
0005579694.tif 000005
【図５】
0005579694.tif 000006
【図６】
0005579694.tif 000007
【図７】
0005579694.tif 000008