(57)【特許請求の範囲】
【請求項１】
実行パイプライン内のサブルーチンリターン命令のための分岐ターゲット命令キャッシュ(BTIC)エントリを確立する方法であって、前記BTICエントリは、次の命令フェッチアドレスフィールドおよび分岐ターゲット命令フィールドを含み、前記方法は、
実行パイプラインにおいてサブルーチン呼出し命令を検出するステップと、
前記サブルーチン呼出し命令を検出したことに応じて、サブルーチンリターン命令のための前記BTICエントリを確立するステップであって、
前記サブルーチン呼出し命令の次に続くフェッチされた少なくとも1つの順次命令を前記サブルーチンリターン命令のための前記BTICエントリの前記分岐ターゲット命令フィールド内の分岐ターゲット命令として書くことと、
前記実行パイプライン内の前記分岐ターゲット命令に続く次の命令のアドレスに対応する次の命令フェッチアドレスを計算することと、
前記次の命令フェッチアドレスを前記サブルーチンリターン命令のための前記BTICエントリ内の前記次の命令フェッチアドレスフィールドに書き込むこととによって、
確立するステップとを含む、方法。
【請求項２】
前記サブルーチンリターン命令は、前記サブルーチン呼出し命令によって呼び出されたサブルーチンからのリターンを指示する、請求項1に記載の方法。
【請求項３】
前記少なくとも1つの順次命令は非分岐命令であり、
前記次の命令フェッチアドレスを計算するステップは、前記少なくとも1つの順次命令の最後の命令に続く前記次の命令の前記アドレスを計算するステップを含む、または、
前記少なくとも1つの順次命令の最後の命令は分岐命令であり、
前記次の命令フェッチアドレスを計算するステップは、前記分岐命令のターゲット命令のアドレスを計算するステップを含む、請求項1に記載の方法。
【請求項４】
前記少なくとも1つの順次命令の最後の命令に先行する前記少なくとも1つの順次命令のうちの1つまたは複数の命令は分岐命令であり、
前記分岐命令のターゲット命令は非分岐命令であり、
前記次の命令フェッチアドレスを計算するステップは、前記分岐命令の前記ターゲット命令に続く前記次の命令の前記アドレスを計算するステップを含む、請求項1に記載の方法。
【請求項５】
前記BTICエントリを確立するステップは、前記BTICエントリが有効であることを指示するために、前記BTICエントリに対応する有効性指示子を設定するステップをさらに含む、請求項1に記載の方法。
【請求項６】
前記サブルーチン呼出し命令を検出するステップは、前記実行パイプライン内の復号化ステージにおいて前記サブルーチン呼出し命令を検出するステップを含む、請求項1に記載の方法。
【請求項７】
前記実行パイプライン内で前記サブルーチンリターン命令を検出するステップと、
前記サブルーチンリターン命令を検出するのに応じて、
前記サブルーチンリターン命令のためのBTICヒットを検出するステップと、
前記実行パイプラインのフェッチステージに前記サブルーチンリターン命令のための前記BTICエントリ内の前記次の命令フェッチアドレスフィールドから前記次の命令フェッチアドレスを与えるステップと、
前記フェッチステージに続く前記実行パイプラインの後続のステージに前記サブルーチンリターン命令のための前記BTICエントリから前記少なくとも1つの順次命令を与えるステップとをさらに含む、請求項1に記載の方法。
【請求項８】
前記サブルーチンリターン命令のための前記BTICヒットを検出するステップは、前記サブルーチンリターン命令のための前記BTICエントリに対応する有効性指示子に基づいて、前記サブルーチンリターン命令のための前記BTICエントリが有効であることを判断するステップを含む、請求項7に記載の方法。
【請求項９】
前記サブルーチンリターン命令を検出するステップは、前記実行パイプライン内の復号化ステージにおいて前記サブルーチンリターン命令を検出するステップを含む、請求項8に記載の方法。
【請求項１０】
前記次の命令フェッチアドレスは、前記少なくとも1つの順次命令の最後の命令の直後の前記次の命令の前記アドレスを含む、請求項1に記載の方法。
【請求項１１】
前記サブルーチンリターン命令のための前記BTICエントリは、前記サブルーチン呼出し命令のリターンアドレスを記憶するリンクスタックエントリに対応する、請求項1に記載の方法。
【請求項１２】
前記サブルーチン呼出し命令は、前記サブルーチン呼出し命令のリターンアドレスをリンクレジスタ(LR)に入れ、プログラムカウンタをサブルーチンの命令アドレスに設定するように動作する分岐およびリンク(BL)命令を含む、請求項1に記載の方法。
【請求項１３】
前記サブルーチンリターン命令は、プログラムカウンタを前記サブルーチン呼出し命令のリターンアドレスに設定するためのリンクへの分岐(BLR)命令を含む、請求項1に記載の方法。
【請求項１４】
実行パイプラインにおいてサブルーチン呼出し命令を検出するための手段と、
サブルーチンリターン命令のための分岐ターゲット命令キャッシュ(BTIC)エントリを確立するための手段であって、前記BTICエントリは、次の命令フェッチアドレスフィールドおよび分岐ターゲット命令フィールドを含み、前記BTICエントリは、前記サブルーチン呼出し命令を検出したことに応じて確立される、手段とを備え、前記確立するための手段は、
前記サブルーチン呼出し命令の次に続くフェッチされた少なくとも1つの順次命令を前記サブルーチンリターン命令のための前記BTICエントリの前記分岐ターゲット命令フィールド内の分岐ターゲット命令として書くための手段と、
前記実行パイプライン内の前記分岐ターゲット命令に続く次の命令のアドレスに対応する次の命令フェッチアドレスを計算するための手段と、
前記次の命令フェッチアドレスを前記サブルーチンリターン命令のための前記BTICエントリ内の前記次の命令フェッチアドレスフィールドに書き込むための手段とを備える、パイプラインバブル低減回路。
【請求項１５】
プロセッサに、請求項1から13のいずれか一項に記載の方法を実行させるコンピュータ実行可能命令をその上に記憶している、コンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
優先権出願
本出願は、参照によってその全体が本明細書に組み込まれている、2012年11月28日に出願された「ESTABLISHING A BRANCH TARGET INSTRUCTION CACHE (BTIC) ENTRY FOR SUBROUTINE RETURNS TO REDUCE EXECUTION PIPELINE STALLS, AND RELATED SYSTEMS, METHODS, AND COMPUTER-READABLE MEDIA」と題する米国仮特許出願第61/730,717号の優先権を主張する。
【０００２】
本開示の技術は、コンピュータシステムにおける分岐予測に関し、より詳細には、分岐ターゲットバッファ(BTB)および/または分岐ターゲット命令キャッシュ(BTIC)に関する。
【背景技術】
【０００３】
命令のパイプライン化は1つの処理技法であり、それによれば、各命令の取扱いを一連のステップに分割し、それらのステップを複数のステージから構成される実行パイプラインにおいて実行することによって、プロセッサによって実行されるコンピュータ命令のスループットを高めることができる。命令リダイレクションが生じるときに、パイプラインバブルを被ることなく、実行パイプライン内のすべてのステージが命令を同時に処理することができる場合には、最適なプロセッサ性能を達成することができる。実行パイプライン内で処理される命令は分岐命令を含む場合があり、分岐命令は、プログラム制御を指定された分岐ターゲット命令に転送することによって、プログラムの流れをリダイレクトする。分岐命令が条件付きである(すなわち、実行されるまで、分岐が行われるか否かがわからない)場合には、分岐予測ハードウェアを用いて、以前に実行された条件付き分岐命令の解決に基づいて、分岐が行われるか否かを予測することができる。
【０００４】
従来の実行パイプラインでは、分岐命令に続く命令は、分岐命令を復号化するのと同時に、実行パイプラインの中にフェッチされる。したがって、分岐が行われると予測されるとき、分岐命令の次に続くフェッチされた命令(すなわち、分岐が行われなかった場合に実行されることになった命令)はフラッシュされる。その後、正しい分岐ターゲット命令がフェッチされる。このプロセスは通常、命令フェッチリダイレクトと呼ばれる。命令フェッチリダイレクトは、1つまたは複数のクロックサイクルを消費する場合があるので、分岐ターゲット命令がフェッチされる間に、復号化ステージがアイドル状態にある時点で、実行パイプラインの中に1つまたは複数のパイプラインバブルが導入される場合がある。導入されると、パイプラインバブルは、実行パイプラインの後続のステージを通って伝搬する。
【０００５】
パイプラインバブルの頻度を低減するために、分岐ターゲット命令キャッシュ(BTIC)が利用される場合がある。BTICは、1つまたは複数の分岐ターゲット命令(すなわち、分岐が行われるときに、分岐命令がプログラム制御を転送するターゲットアドレスにある命令)のコピーを記憶する。BTICにキャッシュされる分岐ターゲット命令は、部分的に、または完全に復号化される場合がある。また、BTICは、キャッシュされた分岐ターゲット命令後に1つまたは複数の次に続く命令をフェッチするための次の命令フェッチアドレスもキャッシュすることができる。BTICは通常、実行パイプラインのフェッチステージ中に調べられ、命令フェッチリダイレクトの結果として導入されるパイプラインバブルの発生を低減するか、または排除するために、実行パイプラインの1つまたは複数の後続のステージに分岐ターゲット命令を与える。
【０００６】
分岐命令が認識され、その分岐が最初に行われるときに、分岐命令のためのBTICエントリが確立される。その結果、初めて分岐命令に直面するとき、その分岐命令のためのBTICエントリは存在せず、BTICキャッシュミスが生じる。サブルーチンリターン命令(特定のタイプの分岐命令)の特定の事例では、サブルーチンリターン命令に最初に直面するとき、サブルーチンリターン命令は常にBTICキャッシュミスを経験することになる。サブルーチンリターン命令に最初に直面するとき、サブルーチンリターン命令に対応するBTICエントリが正しい分岐ターゲット命令を与えることが望ましい。
【０００７】
さらに、1つのプログラム内の異なる点にある複数の分岐命令からサブルーチンが呼び出される場合があるので、サブルーチンリターン命令のためのBTICエントリは、正しくない分岐ターゲット命令を頻繁に含む場合がある。たとえば、最初の呼出し位置から呼び出されるサブルーチンが戻るとき、最初の呼出し位置の次に続く命令が実行され、サブルーチンリターン命令のためのBTICエントリ内に分岐ターゲット命令として追加される。その後、そのサブルーチンが第2の呼出し位置から呼び出される場合には、サブルーチンリターン後に、第2の呼出し位置の次に続く命令が実行されるべきである。しかしながら、サブルーチンリターン命令のためにBTICエントリ内にキャッシュされる分岐ターゲット命令は、第1の呼出し位置に続く命令であり、第2の呼出し位置に続く命令ではない。したがって、サブルーチンリターン命令のBTICエントリは、第2の呼出し位置のための正しい分岐ターゲット命令を含まない。サブルーチンが異なる呼出し位置から呼び出された後でも、サブルーチンリターン命令のBTICエントリが正しい分岐ターゲット命令を与えることが望ましい。
【発明の概要】
【課題を解決するための手段】
【０００８】
本開示の実施形態は、実行パイプラインバブルを低減するために、サブルーチンリターン命令のための分岐ターゲット命令キャッシュ(BTIC)エントリを確立することを提供する。関連するシステム、方法、およびコンピュータ可読媒体も開示される。従来、行われると予測される分岐命令の検出に応じて、すでにフェッチされている(プログラム順で)その分岐命令の次に続く命令が、実行パイプラインからフラッシュされる。しかしながら、分岐命令がサブルーチン呼出し命令であるとき、それらのフラッシュされた次に続く命令は、サブルーチン呼出し命令によって呼び出されたサブルーチンからプログラム制御を転送して戻すことになる、サブルーチンリターン命令のための分岐ターゲット命令である可能性が高い。したがって、本明細書において開示される実施形態は、サブルーチン呼出し命令を検出するのに応じて、サブルーチンリターン命令のためのBTICエントリを確立することを提供する。このようにして、サブルーチンリターン命令に最初に直面するときに、BTICは、そのサブルーチンリターン命令のための有効なBTICエントリを提供することができる。さらに、サブルーチンが先行する呼出し位置とは異なる呼出し位置から呼び出されるときでも、そのBTICエントリは、サブルーチンリターン命令のための正しい分岐ターゲット命令を与えることができる。
【０００９】
この関連で、一実施形態では、実行パイプラインバブルの発生を低減するために、実行パイプライン内のサブルーチンリターン命令のためのBTICエントリを確立する方法が提供される。その方法は、実行パイプライン内のサブルーチン呼出し命令を検出することを含む。サブルーチン呼出し命令を検出するのに応じて、その方法はさらに、そのサブルーチン呼出し命令の次に続くフェッチされた少なくとも1つの次に続く命令をサブルーチンリターン命令のためのBTICエントリ内の分岐ターゲット命令として書くことによって、サブルーチンリターン命令のためのBTICエントリを確立することを含む。また、その方法は、次の命令フェッチアドレスを計算することも含む。さらに、その方法は、次の命令フェッチアドレスを、サブルーチンリターン命令のためのBTICエントリ内の次の命令フェッチアドレスフィールドに書き込むことを含む。このようにして、BTICは、サブルーチンリターン命令に初めて直面する場合であっても、またはサブルーチンが先行する呼出し位置とは異なる呼出し位置から呼び出される場合であっても、そのサブルーチンリターン命令のための正しい分岐ターゲット命令および次の命令フェッチアドレスデータを与えることができる。
【００１０】
別の実施形態では、パイプラインバブル低減回路が提供される。そのパイプラインバブル低減回路は、実行パイプライン内のサブルーチン呼出し命令を検出するように構成されるサブルーチン呼出し検出回路を含む。パイプラインバブル低減回路はさらに、サブルーチン呼出し検出回路がサブルーチン呼出し命令を検出するのに応じてそのサブルーチン呼出し命令の次に続くフェッチされた少なくとも1つの次に続く命令を、サブルーチンリターン命令のためのBTICエントリ内の分岐ターゲット命令として書くように構成されるBTICエントリ確立回路を含む。BTICエントリ確立回路は、次の命令フェッチアドレスを計算するようにさらに構成される。また、BTICエントリ確立回路は、次の命令フェッチアドレスを、サブルーチンリターン命令のためのBTICエントリ内の次の命令フェッチアドレスフィールドに書き込むように構成される。
【００１１】
さらなる実施形態では、パイプラインバブル低減回路が提供される。パイプラインバブル低減回路は、実行パイプライン内のサブルーチン呼出し命令を検出するための手段を備える。パイプラインバブル低減回路はさらに、サブルーチン呼出し命令を検出するのに応じて、サブルーチンリターン命令のためのBTICエントリを確立するための手段を備える。BTICエントリを確立するための手段は、サブルーチン呼出し検出回路がサブルーチン呼出し命令を検出するのに応じて、そのサブルーチン呼出し命令の次に続くフェッチされた少なくとも1つの次に続く命令を、サブルーチンリターン命令のためのBTICエントリ内の分岐ターゲット命令として書くための手段を備える。また、BTICエントリを確立するための手段は、サブルーチン呼出し命令を検出するのに応じて、次の命令フェッチアドレスを計算するための手段を備える。さらに、BTICエントリを確立するための手段は、サブルーチン呼出し命令を検出するのに応じて、次の命令フェッチアドレスを、サブルーチンリターン命令のためのBTICエントリ内の次の命令フェッチアドレスフィールドに書き込むための手段を備える。
【００１２】
さらなる実施形態では、パイプラインバブルの発生を低減するために実行パイプライン内のサブルーチンリターン命令のためのBTICエントリを確立する方法をプロセッサに実施させるコンピュータ実行可能命令をその上に記憶している非一時的コンピュータ可読媒体が提供される。コンピュータ実施可能命令によって実施される方法は、実行パイプライン内のサブルーチン呼出し命令を検出することを含む。コンピュータ実施可能命令によって実施される方法はさらに、サブルーチン呼出し命令を検出するのに応じて、そのサブルーチン呼出し命令の次に続くフェッチされた少なくとも1つの次に続く命令を、サブルーチンリターン命令のためのBTICエントリ内の分岐ターゲット命令として書くことによって、サブルーチンリターン命令のためのBTICエントリを確立することを含む。また、コンピュータ実施可能命令によって実施される方法は、次の命令フェッチアドレスを計算することを含む。さらに、コンピュータ実施可能命令によって実施される方法は、次の命令フェッチアドレスを、サブルーチンリターン命令のためのBTICエントリ内の次の命令フェッチアドレスフィールドに書き込むことを含む。
【図面の簡単な説明】
【００１３】
【図１】実行パイプラインバブルの発生を低減するためにサブルーチンリターン命令のための分岐ターゲット命令キャッシュ(BTIC)エントリを確立するように構成されるパイプラインバブル低減回路を含む例示的なプロセッサのブロック図である。
【図２】図1の実行パイプラインバブル低減回路によって処理される場合がある例示的な命令シーケンスを与える図である。
【図３】予測後に行われた分岐に直面した結果としてのパイプラインバブルの例示的な発生と、図1のパイプラインバブル低減回路を用いるパイプラインバブルの排除とを示す、BTICを用いて図1の例示的なプロセッサによって処理される、図2の例示的な命令シーケンスを示すタイミング図である。
【図４Ａ】サブルーチンリターン命令に直面することから生じるパイプラインバブルの排除を示す、図1のパイプラインバブル低減回路を用いるプロセッサにおいて処理される、図2の例示的な命令シーケンスを示すタイミング図である。
【図４Ｂ】サブルーチンリターン命令に直面することから生じるパイプラインバブルの排除を示す、図1のパイプラインバブル低減回路を用いるプロセッサにおいて処理される、図2の例示的な命令シーケンスを示すタイミング図である。
【図５】実行パイプラインバブルの発生を低減するためにサブルーチンリターン命令のためのBTICエントリを確立するための例示的な動作を示す流れ図である。
【図６】サブルーチンリターン命令を検出するのに応じて、サブルーチンリターン命令のためのBTICエントリを使用するための例示的な動作を示す流れ図である。
【図７Ａ】パイプラインバブルの発生を低減するためにBTICエントリを確立するための例示的な動作をさらに詳細に示す流れ図である。
【図７Ｂ】パイプラインバブルの発生を低減するためにBTICエントリを使用するための例示的な動作をさらに詳細に示す流れ図である。
【図８】パイプラインバブルの発生を低減するためにサブルーチンリターン命令のためのBTICエントリを確立するように構成される、図1のパイプラインバブル低減回路を含むことができる例示的なプロセッサ利用システムの図である。
【発明を実施するための形態】
【００１４】
ここで図面を参照しながら、本開示のいくつかの例示的な実施形態が説明される。「例示的」という語は、本明細書では「例、実例、または例示としての役割を果たす」ことを意味するために用いられる。「例示的」として本明細書において説明されるいずれの実施形態も、必ずしも他の実施形態よりも好ましいか、または有利であると解釈されるべきではない。
【００１５】
本開示の実施形態は、実行パイプラインバブルを低減するために、サブルーチンリターン命令のための分岐ターゲット命令キャッシュ(BTIC)エントリを確立することを提供する。関連するシステム、方法、およびコンピュータ可読媒体も開示される。従来、行われると予測される分岐命令の検出に応じて、すでにフェッチされている(プログラム順で)その分岐命令の次に続く命令が、実行パイプラインからフラッシュされる。しかしながら、分岐命令がサブルーチン呼出し命令であるとき、それらのフラッシュされた次に続く命令は、サブルーチン呼出し命令によって呼び出されたサブルーチンからプログラム制御を転送して戻すことになる、サブルーチンリターン命令のための分岐ターゲット命令である可能性が高い。したがって、本明細書において開示される実施形態は、サブルーチン呼出し命令を検出するのに応じて、サブルーチンリターン命令のためのBTICエントリを確立することを提供する。このようにして、サブルーチンリターン命令に最初に直面するときに、BTICは、そのサブルーチンリターン命令のための有効なBTICエントリを提供することができる。さらに、サブルーチンが先行する呼出し位置とは異なる呼出し位置から呼び出されるときでも、そのBTICエントリは、サブルーチンリターン命令のための正しい分岐ターゲット命令を与えることができる。
【００１６】
この関連で、一実施形態では、実行パイプラインバブルの発生を低減するために、実行パイプライン内のサブルーチンリターン命令のためのBTICエントリを確立する方法が提供される。その方法は、実行パイプライン内のサブルーチン呼出し命令を検出することを含む。サブルーチン呼出し命令を検出するのに応じて、その方法はさらに、そのサブルーチン呼出し命令の次に続くフェッチされた少なくとも1つの次に続く命令を、サブルーチンリターン命令のためのBTICエントリ内の分岐ターゲット命令として書くことによって、サブルーチンリターン命令のためのBTICエントリを確立することを含む。また、その方法は、次の命令フェッチアドレスを計算することも含む。さらに、その方法は、次の命令フェッチアドレスを、サブルーチンリターン命令のためのBTICエントリ内の次の命令フェッチアドレスフィールドに書き込むことを含む。このようにして、BTICは、サブルーチンリターン命令に初めて直面する場合であっても、またはサブルーチンが先行する呼出し位置とは異なる呼出し位置から呼び出される場合であっても、そのサブルーチンリターン命令のための正しい分岐ターゲット命令および次の命令フェッチアドレスデータを与えることができる。
【００１７】
この関連で、図1は、例示的なプロセッサ10のブロック図である。プロセッサ10は、パイプラインバブルの発生を低減するためにサブルーチンリターン命令のためのBTICエントリ(図示せず)を確立するように構成されるパイプラインバブル低減回路12を含む。プロセッサ10は、数ある素子の中でも、既知のデジタル論理素子、半導体回路、処理コアおよび/またはメモリ構造のいずれか1つ、またはその組合せを含む場合がある。本明細書において記述される実施形態は、要素の任意の特定の構成には限定されず、開示される技法は、半導体ダイまたはパッケージ上の種々の構造またはレイアウトに容易に拡張することができる。プロセッサ10は、入力/出力(I/O)回路14と、命令キャッシュ16と、データキャッシュ18とを含む。プロセッサ10はさらに、フロントエンド回路22、実行ユニット24および完了ユニット26を含む実行パイプライン20を備える。プロセッサ10はさらに、リンクスタック28と、レジスタ30とを含み、レジスタは、1つまたは複数の汎用レジスタ(GPR)32と、プログラムカウンタ34と、リンクレジスタ36とを備える。ARM v7アーキテクチャを利用する実施形態のようないくつかの実施形態では、リンクレジスタ36は、図1に示されるようなGPR32のうちの1つである。代替的には、リンクレジスタ36がGPR32から独立した、PowerPCアーキテクチャを利用する実施形態のようないくつかの実施形態が提供される場合がある(図示せず)。
【００１８】
例示的な動作では、実行パイプライン20のフロントエンド回路22は、命令キャッシュ16から命令をフェッチする。大部分の実施形態では、命令キャッシュ16は、非限定的な例として、オンチップレベル1(L1)キャッシュとすることができる。フェッチされた命令はフロントエンド回路22によって復号化され、実行ユニット24に発行される。実行ユニット24は、発行された命令を実行し、完了ユニット26は、実行された命令をリタイヤさせる。いくつかの実施形態では、完了ユニット26は、1つまたは複数のターゲットファイルレジスタ内に命令結果を記憶するライトバック機構を備えることができる。実行ユニット24および/または完了ユニット26はそれぞれ、1つまたは複数の順次パイプラインステージを備える場合があることは理解されたい。命令は2つ以上の命令からなるグループにおいてフェッチされ、および/または復号化される場合があることをさらに理解されたい。
【００１９】
いくつかの実施形態では、プロセッサ10は分岐予測を用いる場合があり、その例示的な動作がここで説明される。フロントエンド回路22が、順次フェッチ/復号化パイプラインステージ38、40および42(本明細書においてそれぞれFE1、FE2およびFE3と呼ばれる)と、発行/ディスパッチステージ44とを含む、パイプラインステージを備える。パイプラインステージ38、40および42のうちの1つまたは複数は、分岐制御論理(BCL)回路48、分岐ターゲット命令キャッシュ(BTIC)50、分岐ターゲットアドレスキャッシュ(BTAC)52および分岐履歴テーブル(BHT)54を備える分岐予測回路46に関連付けられる。
【００２０】
プロセッサ10のパイプラインバブル低減回路12は、サブルーチン呼出し検出回路56と、BTICエントリ確立回路58と、サブルーチンリターン検出回路60と、BTIC使用回路(BTIC consuming circuit)62とを含む。実行パイプラインバブルを低減するために、サブルーチンリターン命令のためのBTICエントリを確立するためにパイプラインバブル低減回路12のこれらの要素によって実行される動作が、以下にさらに詳細に論じられる。いくつかの実施形態では、BTICエントリ確立回路58および/またはBTIC使用回路62は、BTIC50によって部分的に与えられる論理または機能を利用することができる。
【００２１】
サブルーチンリターン命令のためのBTICエントリを確立するための方法、システムおよびコンピュータ可読媒体が説明される前に、従来のBTICが最初に説明される。以下に論じられる例を簡単にするために、図1の実行パイプライン20によって処理される場合がある典型的な一連の命令を表す例示的な命令シーケンス64が、図2において与えられる。例示的な命令シーケンス64は、Instr0、Instr1、Instr2、Instr3、InstrX、InstrX+1、InstrX+2およびInstrYとそれぞれ呼ばれる命令66、68、70、72、74、76、78および79を含む。先に参照された命令が図2において現れる順序は、それらの命令が、ハードドライブまたはフラッシュメモリのような永続記憶媒体内に記憶される順序を表す。しかしながら、命令がプロセッサ10によって実行されるにつれて、プログラム制御は、分岐命令のような命令によって、1つの位置から別の位置に転送される場合がある。結果として、命令がプロセッサ10によってフェッチされ、実行される実際の順序は、命令が記憶されるシーケンスとは異なる場合がある。
【００２２】
図2において、命令の実行中のプログラム制御の転送が、プログラムフロー80の矢印によって示される。プログラムフロー80によって示されるように、プログラム実行は命令Instr0で開始し、Instr1に進み、Instr1はこの例ではサブルーチン呼出し命令である。いくつかの実施形態では、サブルーチン呼出し命令は、分岐およびリンク(BL)命令を含むことができ、その命令はサブルーチン呼出し命令のリターンアドレスを、図1のリンクレジスタ36のようなリンクレジスタに入れ、図1のプログラムカウンタ34のようなプログラムカウンタをサブルーチンの命令アドレスに設定する。ここで、サブルーチン呼出し命令Instr1によって、プログラム制御は、サブルーチン開始命令であるInstrXに転送される。
【００２３】
次の命令InstrX+1およびInstrX+2は順次にフェッチされ、実行される。命令InstrX+2はサブルーチンリターン命令であり、プログラム制御が、そのサブルーチンを呼び出したサブルーチン呼出し命令の次に続く命令に戻る分岐命令である。いくつかの実施形態は、サブルーチンリターン命令が、図1のプログラムカウンタ34のようなプログラムカウンタをサブルーチン呼出し命令のリターンアドレスに設定するリンクへの分岐(BLR)命令である、と規定し得る。この例では、命令InstrX+2の実行は、プログラム制御を、サブルーチン呼出し命令Instr1を実行した直後の命令である、命令Instr2に転送する。その後、命令の処理は順次に継続し、命令Instr3および任意の後続の命令が順番にフェッチされ、実行される。図2に示されるように、命令InstrYは、次のサブルーチンの開始点を表す。命令InstrYはサブルーチンリターン命令InstrX+2の直後に続くが、命令InstrYおよび後続の命令は、プログラム内の別の分岐命令(図示せず)によって呼び出されない限り、実行されない。
【００２４】
図3は、予測後に行われた分岐に直面した結果としての実行パイプラインバブルの例示的な発生と、パイプラインバブルを排除するためのBTICの使用とをさらに明確に例示すために提供される。図3は、図1のプロセッサ10のような、BTICを利用するプロセッサによって処理されるときの図2の例示的な命令シーケンス64を示すタイミング図である。タイミング図内の列(0、1、2、...8を付される)はそれぞれ単一のプロセッサクロックサイクルを表す。タイミング図内の行(「次のフェッチ」、「FE1」、「FE2」および「FE3」を付される)は、「次のフェッチ」指示子82と、各プロセッサクロックサイクル中の実行パイプラインステージ「FE1」、「FE2」および「FE3」との内容を示す。この例では、「次のフェッチ」指示子82は実行パイプラインステージFE1における次のプロセッサクロックサイクル中にプロセッサによってフェッチされることになる次の命令を示す。このようにして、数クロックサイクルにわたる実行パイプラインステージを通しての命令の進行が示される。
【００２５】
図3は、例示的な命令シーケンス64において検出された分岐命令に対応するエントリを記憶するために用いられる図1のBTIC50をさらに示す。BTIC50は、各BTICエントリの一部として、次の命令フェッチアドレスフィールドおよび分岐ターゲット命令フィールドを含む。分岐ターゲット命令フィールドは、プログラム制御を転送するために、対応する分岐命令が予測される1つまたは複数の命令のコピーを記憶する。次の命令フェッチアドレスフィールドは、分岐ターゲット命令フィールド内の分岐ターゲット命令に続く次の命令のアドレスを記憶する。パイプラインバブルを排除する際の次の命令フェッチアドレスフィールドおよび分岐ターゲット命令フィールドの使用が以下にさらに詳細に論じられる。図3に示される例示的なタイミング図は、サブルーチン呼出し命令Instr1がすでに一度検出されており、結果として、適切な次の命令フェッチアドレスおよび分岐ターゲット命令値を追加された、BTIC50内のBTICエントリ84が確立されていると仮定することは理解されたい。
【００２６】
図3を引き続き参照すると、処理が、図2の例示的な命令シーケンス64内の最初の命令であるInstr0を用いてプロセッサクロックサイクル0において開始する。プロセッサクロックサイクル0において、次のフェッチ指示子82は、命令Instr0が処理するために次にフェッチされることを指示する。プロセッサクロックサイクル1において、命令Instr0は、フェッチするために実行パイプラインステージFE1に進んでいる。次のフェッチ指示子82も、例示的な命令シーケンス64内の命令Instr0の次に続くサブルーチン呼出し命令Instr1が次にフェッチされることを指示するために更新されている。プロセッサクロックサイクル2中に、命令Instr0は実行パイプラインステージFE2において復号化され、一方、命令Instr1は実行パイプラインステージFE1においてフェッチされる。この時点で、命令Instr1は、分岐命令として認識されていない。その結果、次のフェッチ指示子82は、プロセッサクロックサイクル2において、命令Instr1の次に続く命令次の命令(すなわち、命令Instr2)が次にフェッチされることを指示するように更新される。
【００２７】
プロセッサクロックサイクル3において、実行パイプラインバブルが発生する。命令Instr0が実行パイプラインステージFE3に達している。サブルーチン呼出し命令Instr1は実行パイプラインステージFE2において復号化され、そのステージにおいて、予測後に行われた分岐として識別される。任意の誤ってフェッチされた命令を実行パイプラインからフラッシュし、サブルーチン呼出し命令Instr1のための正しい分岐ターゲット命令をフェッチするために、命令フェッチリダイレクトが開始される。サブルーチン呼出し命令Instr1のための正しい分岐ターゲット命令(すなわち、命令InstrX)は、次のプロセッサクロックサイクルまでフェッチできないので、図3において「Instr2(バブル)」として示されるパイプラインバブルが、実行パイプラインステージFE1に導入される。図3において見られるように、FE1にフェッチされる命令Instr2は、プロセッサクロックサイクル3中にパイプラインバブルを占有する。
【００２８】
プロセッサがBTIC50を用いなかった場合には、後続のプロセッサクロックサイクルにわたって、実行パイプラインバブルが実行パイプライン内で伝搬することになり、結果として、プロセッサスループットが低下し、電力消費が非効率的になっていた。しかしながら、この例では、BTIC50は、実行パイプラインバブルを排除するために利用可能である。プロセッサクロックサイクル3中に、BTIC50がアクセスされ、サブルーチン呼出し命令Instr1のために以前に確立されたBTICエントリ84が特定される。BTIC50は、BTICエントリ84のための次の命令フェッチアドレスフィールドの内容を与える。それに応じて、次のフェッチ指示子82は、矢印86によって示されるように、命令InstrX+1(すなわち、分岐ターゲット命令InstrXに続く命令)が次にフェッチされることを指示するように更新される。
【００２９】
引き続き図3を参照すると、プロセッサクロックサイクル4中に、命令Instr0は実行パイプライン88の残りの部分における残りの発行および実行ステージに進み、一方、命令Instr1は実行パイプラインステージFE3に達する。命令InstrX+1は、実行パイプラインステージFE1においてフェッチされる。プロセッサクロックサイクル3において導入された実行パイプラインバブルは依然として存在し、実行パイプラインステージFE2に達していることに留意されたい。しかしながら、プロセッサクロックサイクル5中に実行パイプラインバブルが実行ステージFE3に達するとき、BTIC50は、矢印90によって示されるように、サブルーチン呼出し命令Instr1のためのBTICエントリ84から実行パイプラインステージFE3に分岐ターゲット命令(たとえば、InstrX)を供給する。このようにして、パイプラインバブルは排除され、残りの命令は、プロセッサクロックサイクル6および7中にパイプラインを通って移動する。
【００３０】
他のタイプの分岐命令と同様に、サブルーチンリターン命令に最初に直面するとき、サブルーチンリターン命令は結果として、常にBTICキャッシュミスを生じることになる。さらに、サブルーチンは1つのプログラム内の異なる点にある複数の分岐命令から呼び出される場合があるので、サブルーチンリターン命令のためのBTICエントリは、誤った分岐ターゲット命令を頻繁に含む場合がある。したがって、サブルーチンリターン命令を処理するときに、パイプラインバブルの発生を低減するために、図1のパイプラインバブル低減回路12が設けられる場合がある。
【００３１】
この関連で、図4Aおよび図4Bは、パイプラインバブル低減回路12を用いて図1のプロセッサ10によって処理される、図2の例示的な命令シーケンス64を示すタイミング図である。図4Aは、サブルーチン呼出し命令の検出時のサブルーチンリターン命令のためのBTICエントリの確立を示し、一方、図4Bはパイプラインバブルを排除するために用いられる、確立されたBTICエントリを示す。図3と同様に、図4Aおよび図4Bのタイミング図の列(0、1、2、...8を付される)はそれぞれ単一のプロセッサクロックサイクルを表し、一方、各タイミング図の行は、次のフェッチ指示子82、ならびに各プロセッサクロックサイクル中の実行パイプラインステージFE1、FE2およびFE3の内容を示す。次のフェッチ指示子82は、実行パイプラインステージFE1において次のプロセッサクロックサイクル中にプロセッサによってフェッチされることになる次の命令を示す。また、図4Aおよび図4Bは、パイプラインバブル低減回路12およびBTIC50も示す。明確および簡潔にするために、サブルーチン呼出し命令Instr1のためのBTICエントリの確立は図3において説明されるように行われ、図4Aおよび図4Bとともに再び図示または説明されないと仮定される。図4Aおよび図4Bに示される例は、1つの命令の命令フェッチ幅を用いるが、いくつかの実施形態は、2つ以上の命令の命令フェッチ幅を与える場合があることは理解されたい。
【００３２】
図4Aを参照すると、プロセッサクロックサイクル0において、次のフェッチ指示子82は、命令Instr0(図2の例示的な命令シーケンス64における第1の命令)が処理するために次にフェッチされることを指示する。プロセッサクロックサイクル1において、命令Instr0はフェッチするために実行パイプラインステージFE1に進んでおり、次のフェッチ指示子82は、例示的な命令シーケンス64において命令Instr0の次に続くサブルーチン呼出し命令Instr1が次にフェッチされることを指示するように更新される。プロセッサクロックサイクル2中に、命令Instr0は実行パイプラインステージFE2において復号化され、一方、サブルーチン呼出し命令Instr1は実行パイプラインステージFE1においてフェッチされる。この時点で、サブルーチン呼出し命令Instr1は分岐命令として認識されない。その結果、次のフェッチ指示子82は、プロセッサクロックサイクル2において、命令Instr1の次に続く次の命令(すなわち、命令Instr2)が次にフェッチされることを指示するように更新される。
【００３３】
引き続き図4Aを参照すると、プロセッサクロックサイクル3において、パイプラインバブルが発生する。命令Instr0は実行パイプラインステージFE3に達しており、サブルーチン呼出し命令Instr1は実行パイプラインステージFE2において復号化され、そのステージにおいて、予測後に行われた分岐として識別される。図3に示されるように、任意の誤ってフェッチされた命令(すなわち、命令Instr2)を実行パイプラインからフラッシュし、サブルーチン呼出し命令Instr1のための正しい分岐ターゲット命令をフェッチするために、命令フェッチリダイレクトが開始される。
【００３４】
しかしながら、誤ってフェッチされた命令を処分するよりむしろ、パイプラインバブル低減回路12は、サブルーチン呼出し命令Instr1に直面したときにフェッチされた命令を用いて、サブルーチンリターン命令InstrX+2のためのBTICエントリ92を確立する。詳細には、プロセッサクロックサイクル4において、パイプラインバブル低減回路12は、実行パイプラインのFE2ステージからフェッチされた命令Instr2を検索し(矢印94によって示される)、矢印96によって示されるように、BTICエントリ92内のフェッチされた命令Instr2を分岐ターゲット命令として記憶する。命令Instr2のサイズに基づいて、パイプラインバブル低減回路12は、命令Instr2の次に続く命令Instr3のアドレスを計算し、矢印98によって示されるように、BTICエントリ92内の命令Instr3のアドレスを次の命令フェッチアドレスとして記憶する。その後、図3において先に説明されたのと概ね同じように処理が続き、サブルーチン呼出し命令Instr1に関連付けられるパイプラインバブルがプロセッサクロックサイクル5においてBTIC50を用いて排除される。
【００３５】
ここで図4Bを参照すると、サブルーチンリターン命令InstrX+2に関連付けられるパイプラインバブルを排除するための動作が示される。プロセッサクロックサイクル6において、サブルーチンリターン命令InstrX+2が実行パイプラインステージFE2において復号化され、予測後に行われた分岐として識別されるとき、実行パイプラインステージFE1においてパイプラインバブルが発生し、命令フェッチリダイレクトをトリガする。パイプラインバブル低減回路12がサブルーチンリターン命令InstrX+2を検出するとき、BTIC50がアクセスされ、サブルーチンリターン命令InstrX+2のためのBTICエントリ92が特定される。BTIC50はBTICエントリ92のための次の命令フェッチアドレスフィールドの内容を次のフェッチ指示子82に与え、次のフェッチ指示子は、矢印99によって示されるように、命令Instr3(すなわち、分岐ターゲット命令Instr2に続く命令)が次にフェッチされることを指示するように更新される。2プロセッサクロックサイクル後、プロセッサクロックサイクル8中に、BTIC50は、矢印100によって示されるように、サブルーチンリターン命令InstrX+2のためのBTICエントリ92から実行パイプラインステージFE3に分岐ターゲット命令(たとえば、Instr2)を供給する。このようにして、パイプラインバブルは排除される。
【００３６】
いくつかの実施形態では、パイプラインバブル低減回路12のサブルーチン呼出し検出回路56(図1に示される)は、サブルーチン呼出し命令Instr1を検出するように動作することができる。いくつかの実施形態は、サブルーチンリターン命令InstrX+2のためのBTICエントリ92が、パイプラインバブル低減回路12のBTICエントリ確立回路58によって確立され、追加される場合があることを規定する。いくつかの実施形態は、サブルーチンリターン命令InstrX+2が、パイプラインバブル低減回路12のサブルーチンリターン検出回路60によって検出される、と規定し得る。いくつかの実施形態では、パイプラインバブル低減回路12のBTIC使用回路62が、サブルーチンリターン命令InstrX+2のためのBTICヒットを検出することができ、BTIC50にアクセスして、BTICエントリ92内の次の命令フェッチアドレスフィールドおよび分岐ターゲット命令を検索することができる。
【００３７】
図4Aおよび図4Bに示されるように、サブルーチン呼出し命令の検出は、対応するサブルーチンリターン命令のための、BTICエントリ92のようなBTICエントリの作成をトリガすることができる。作成すると、BTICエントリは、サブルーチンリターン命令アドレスで「タグ付け」される場合があり、それにより、サブルーチンリターン命令に直面するときに、BTICエントリの検索を容易にすることができる。たとえば、いくつかの実施形態では、サブルーチンリターン命令を検出する結果として、タグとしてサブルーチンリターン命令のアドレスを有するBTICエントリがBTIC内に存在するか否かを判断するために、BTICが探索される。
【００３８】
いくつかの実施形態は、サブルーチンリターンアドレスを得るためにBTICエントリを検索するための代替の機構を提供することができる。たとえば、いくつかの実施形態では、BTICは、図1のリンクスタック28のようなリンクスタックにリンクされる場合がある。サブルーチン呼出し命令が検出されるとき、上記のように、そのサブルーチンリターン命令のためのBTICエントリを作成することができる。さらに、リンクスタック内のサブルーチン呼出し命令のためのリンクスタックエントリを、サブルーチンリターン命令のためのBTICエントリが存在することを指示するように更新することができる。サブルーチンリターン命令が検出されると、サブルーチン呼出し命令のためのリンクスタックエントリを調べることによって、適切なBTICエントリを求めることができる。いくつかの実施形態は、所与のリンクスタックエントリが特定のBTICエントリに常に対応するように、リンクスタックエントリが対応するBTICを直接指示する、と規定し得る。いくつかの実施形態では、たとえば、対応するBTICエントリへのポインタを含むことによって、リンクスタックエントリは対応するBTICエントリを間接的に指示することができる。図5は、図1および図2を参照して、パイプラインバブルの発生を低減するために、サブルーチンリターン命令のためのBTICエントリを確立するための、図1のパイプラインバブル低減回路12によって実行される例示的な動作を示す流れ図である。この例におけるプロセスは、パイプラインバブル低減回路12が、サブルーチン呼出し命令が実行パイプライン20において検出されたか否かを判断すること(ブロック102)によって開始する。先に言及したように、いくつかの実施形態は、分岐命令が復号化されるまで、サブルーチン呼出し命令のような分岐命令を検出することができない、と規定し得る。したがって、いくつかの実施形態では、パイプラインバブル低減回路12は、サブルーチン呼出し命令を検出するために、実行パイプラインステージFE2のような実行パイプラインステージと通信することができる。
【００３９】
ブロック102においてサブルーチン呼出し命令が検出されない場合には、命令の処理がブロック104において継続する。しかしながら、実行パイプライン20においてサブルーチン呼出し命令が検出された場合には、パイプラインバブル低減回路12は、検出されたサブルーチン呼出し命令に対応するサブルーチンリターン命令のためのBTICエントリを確立する機会を確認した。サブルーチン呼出し命令が識別された時点で、サブルーチン呼出し命令の次に続く少なくとも1つの次の命令がフェッチされているか、またはフェッチされることに留意されたい。サブルーチンのためのサブルーチンリターン命令は、サブルーチンが実行された後に、プログラム制御を少なくとも1つの次に続く命令に転送して戻すので、少なくとも1つの次に続く命令が、サブルーチンリターン命令のための分岐ターゲット命令としてキャッシュされる場合がある。それゆえ、パイプラインバブル低減回路12は、サブルーチン呼出し命令の次に続くフェッチされた少なくとも1つの次に続く命令を、サブルーチンリターン命令のためのBTICエントリ内の分岐ターゲット命令として書く(ブロック106)。いくつかの実施形態では、少なくとも1つの次に続く命令は、パイプラインバブル低減回路12のBTICエントリ確立回路58のようなBTICエントリ確立回路によって、BTICエントリ内に分岐ターゲット命令として書かれる。
【００４０】
次に、パイプラインバブル低減回路12は、次の命令フェッチアドレスを計算する(ブロック108)。次の命令フェッチアドレスは、サブルーチンリターン命令のための分岐ターゲット命令として記憶された少なくとも1つの次に続く命令後に、フェッチされ、実行されることになる次の命令の位置を指示する。いくつかの実施形態では、次の命令フェッチアドレスを計算するための動作は、少なくとも1つの次に続く命令内の分岐命令の存否によって決まる場合がある。非限定的な例として、少なくとも1つの次に続く命令が非分岐命令のみを含む場合には、パイプラインバブル低減回路12は、少なくとも1つの次に続く命令の最後の命令に続く命令のアドレスを計算することによって、次の命令フェッチアドレスを計算することができる。これは、たとえば、少なくとも1つの次に続く命令の最初の命令の命令アドレスと、少なくとも1つの次に続く命令のバイトサイズに等しいオフセットとの和をとることによって成し遂げることができる。さらなる非限定的な例として、少なくとも1つの次に続く命令の最後の命令が分岐命令である場合には、パイプラインバブル低減回路12は、分岐命令のターゲット命令のアドレスを計算することによって、次の命令フェッチアドレスを計算することができる。さらなる非限定的な例として、少なくとも1つの次に続く命令の最後の命令に先行する少なくとも1つの次に続く命令のうちの1つまたは複数の命令が分岐命令であり、分岐命令のターゲット命令が非分岐命令である場合には、パイプラインバブル低減回路12は、分岐命令のターゲット命令に続く命令のアドレスを計算することによって、次の命令フェッチアドレスを計算することができる。
【００４１】
次の命令フェッチアドレスを計算した後に、パイプラインバブル低減回路12は、次の命令フェッチアドレスを、サブルーチンリターン命令のためのBTICエントリ内の次の命令フェッチアドレスフィールドに書き込む(ブロック110)。その後、サブルーチンリターン命令のためのBTICエントリは、排除しなければ、サブルーチンリターン命令に直面した後に実行パイプラインを通って伝搬する場合があるパイプラインバブルを排除するために利用可能である。その後、処理は、ブロック104において継続する。
【００４２】
図6は、サブルーチンリターン命令を検出するのに応じて、サブルーチンリターン命令のためのBTICエントリを使用するための、図1のパイプラインバブル低減回路12によって実行される例示的な動作を示す流れ図である。最初に、パイプラインバブル低減回路12は、実行パイプライン20において、サブルーチンリターン命令が検出されたか否かを判断する(ブロック112)。いくつかの実施形態は、分岐命令が復号化されるまで、サブルーチンリターン命令のような分岐命令を検出できない、と規定し得る。したがって、いくつかの実施形態では、パイプラインバブル低減回路12は、サブルーチンリターン命令を検出するために、実行パイプラインステージFE2のような実行パイプラインステージと通信することができる。
【００４３】
サブルーチンリターン命令が検出されない場合には、命令の処理がブロック114において継続する。サブルーチンリターン命令が検出された場合には、パイプラインバブル低減回路12は、サブルーチンリターン命令のためのBTICヒットを検出する(ブロック113)。その後、パイプラインバブル低減回路12は、サブルーチンリターン命令のためのBTICエントリを使用する(ブロック116)。いくつかの実施形態では、サブルーチンリターン命令のためのBTICエントリを使用することは、実行パイプラインに次の命令フェッチアドレスおよび分岐ターゲット命令を与えることによって、サブルーチンリターン命令に関連付けられるパイプラインバブルを排除する。その後、処理は、ブロック114において継続する。
【００４４】
パイプラインバブルの発生を低減するために、BTICエントリを確立し、使用するための図1のパイプラインバブル低減回路12によって実行されるさらに詳細な例示的動作が、図7Aおよび図7Bに示される。図7Aは、パイプラインバブルの発生を低減するために、BTICエントリを確立することに関連する例示的な動作を詳述する流れ図であり、一方、図7Bは、実行パイプライン内のパイプラインバブルを排除するために、サブルーチンリターン命令のためのBTICエントリを使用するための例示的な動作を示す流れ図である。
【００４５】
図7Aにおいて、パイプラインバブル低減回路12は、実行パイプライン20内でサブルーチン呼出し命令が検出されたか否かを判断する(ブロック117)。例示的なサブルーチン呼出し命令は分岐およびリンク(BL)命令を含むことができ、その命令はサブルーチン呼出し命令のリターンアドレスをリンクレジスタ36に入れ、プログラム制御34をサブルーチンの命令アドレスに設定する。いくつかの実施形態では、パイプラインバブル低減回路12は、復号化ステージFE2のような実行パイプライン20の復号化ステージ内でサブルーチン呼出し命令を検出することができる。
【００４６】
ブロック117において、サブルーチン呼出し命令が検出されない場合には、処理は図7Bのブロック118において継続する。パイプラインバブル低減回路12がサブルーチン呼出し命令を検出する場合には、BTICエントリを確立するための動作が実行される。いくつかの実施形態では、BTICエントリは、BTIC自体とは別のバッファ内に確立され、その後、BTICの中にコピーされる場合がある。代替的には、いくつかの実施形態は、BTICに直接書き込むことによって、BTICエントリが確立される、と規定し得る。後者の場合、BTICエントリが使用に関してまだ有効でないことを指示するために、BTICエントリに対応する有効性指示子が最初にクリアされる場合がある(ブロック119)。ブロック119の動作は、BTICエントリを確立するために別のバッファを利用する実施形態の場合、不要な場合があることは理解されたい。
【００４７】
次に、サブルーチン呼出し命令の次に続くフェッチされた少なくとも1つの次に続く命令が、サブルーチンリターン命令のための分岐ターゲット命令としてBTICエントリ内に書き込まれる(ブロック120)。いくつかの実施形態では、サブルーチンリターン命令は、サブルーチン呼出し命令によって呼び出されるサブルーチンからのリターンを指示する分岐命令である。いくつかの実施形態は、BTICエントリがサブルーチンリターン命令専用である、と規定し得る。いくつかの実施形態におけるBTICエントリは、サブルーチン呼出し命令のリターンアドレスを記憶するリンクスタック28内のリンクスタックエントリに対応することができる。いくつかの実施形態では、少なくとも1つの次に続く命令は、パイプラインバブル低減回路12のBTICエントリ確立回路58のようなBTICエントリ確立回路によって、BTICエントリ内に分岐ターゲット命令として書かれる。
【００４８】
その後、パイプラインバブル低減回路12は、次の命令フェッチアドレスを計算する(ブロック122)。次の命令フェッチアドレスは、サブルーチンリターン命令のための分岐ターゲット命令として記憶される少なくとも1つの次に続く命令後にフェッチされ、実行されることになる次の命令の位置を指示する。いくつかの実施形態では、次の命令フェッチアドレスを計算するための動作は、少なくとも1つの次に続く命令内の分岐命令の存否によって決まる場合がある。非限定的な例として、少なくとも1つの次に続く命令が非分岐命令のみを含む場合には、パイプラインバブル低減回路12は、少なくとも1つの次に続く命令の最後の命令に続く命令のアドレスを計算することによって、次の命令フェッチアドレスを計算することができる。これは、たとえば、少なくとも1つの次に続く命令の最初の命令の命令アドレスと、少なくとも1つの次に続く命令のバイトサイズに等しいオフセットとの和をとることによって成し遂げることができる。さらなる非限定的な例として、少なくとも1つの次に続く命令の最後の命令が分岐命令である場合には、パイプラインバブル低減回路12は、分岐命令のターゲット命令のアドレスを計算することによって、次の命令フェッチアドレスを計算することができる。さらなる非限定的な例として、少なくとも1つの次に続く命令の最後の命令に先行する少なくとも1つの次に続く命令のうちの1つまたは複数の命令が分岐命令であり、分岐命令のターゲット命令が非分岐命令である場合には、パイプラインバブル低減回路12は、分岐命令のターゲット命令に続く命令のアドレスを計算することによって、次の命令フェッチアドレスを計算することができる。
【００４９】
その後、次の命令フェッチアドレスは、サブルーチンリターン命令のためのBTICエントリ内の次の命令フェッチアドレスフィールドに書き込まれる(ブロック124)。いくつかの実施形態では、次の命令フェッチアドレスは、パイプラインバブル低減回路12のBTICエントリ確立回路58のようなBTICエントリ確立回路によって、BTICエントリ内の次の命令フェッチアドレスフィールドに書き込まれる。パイプラインバブル低減回路12は、BTICエントリが使用に関して有効であることを指示するために、BTICエントリに対応する有効性指示子を設定する(ブロック126)。その後、処理は図7Bのブロック118において継続する。
【００５０】
ここで図7Bを参照すると、パイプラインバブル低減回路12が、実行パイプライン20においてサブルーチンリターン命令が検出されたか否かを判断する(ブロック118)。例示的なサブルーチンリターン命令は、プログラムカウンタ34をサブルーチン呼出し命令のリターンアドレスに設定するためのリンクへの分岐(BLR)命令を含むことができる。いくつかの実施形態は、パイプラインバブル低減回路12が、復号化ステージFE2 40のような、実行パイプライン20の復号化ステージ内でサブルーチンリターン命令を検出する、と規定し得る。サブルーチンリターン命令が検出されない場合には、後にさらに詳細に論じられる、図7Aのブロック117において処理が継続する。パイプラインバブル低減回路12がサブルーチンリターン命令を検出する場合には、パイプラインバブル低減回路12は次に、サブルーチンリターン命令のためのBTICヒット(すなわち、BTIC内のサブルーチンリターン命令のための有効なBTICエントリ)が検出されたか否かを判断する(ブロック130)。いくつかの実施形態では、サブルーチンリターン命令のためのBTICヒットを検出することは、BTICエントリに対応する有効性ビットを評価して、BTICエントリが有効であるか否かを判断することを含むことができる。BTIC内のサブルーチンリターン命令のためのBTICヒットが検出されない場合には、処理が図7Aのブロック117において継続する。
【００５１】
BTICヒットが検出された場合には、パイプラインバブル低減回路12は、次に続くフェッチステージFE1のような実行パイプライン20のフェッチステージにサブルーチンリターン命令のためのBTICエントリの次の命令フェッチアドレスフィールドから次の命令フェッチアドレスを与える(ブロック134)。パイプラインバブル低減回路12は次に、サブルーチンリターンアドレスのためのBTICエントリ内の分岐ターゲット命令として記憶された少なくとも1つの次に続く命令を、FE2ステージ40のような、実行パイプライン20の後続のステージに与える(ブロック136)。このようにして、パイプラインバブル低減回路12は、いくつかの実施形態において、サブルーチンリターン命令に関連付けられるパイプラインバブルを排除するために、少なくとも1つの次に続く命令を実行パイプラインに追加することができる。処理が図7Aのブロック117において継続する。
【００５２】
本明細書において開示される実施形態によるパイプラインバブル低減回路12は任意のプロセッサベースデバイスに設けられるか、または組み込まれる。例として、限定されないが、セットトップボックス、エンターテインメントユニット、ナビゲーションデバイス、通信デバイス、固定ロケーションデータユニット、モバイルロケーションデータユニット、モバイルフォン、セルラーフォン、コンピュータ、ポータブルコンピュータ、デスクトップコンピュータ、携帯情報端末(PDA)、モニタ、コンピュータモニタ、テレビ、チューナ、ラジオ、衛星ラジオ、音楽プレーヤ、デジタル音楽プレーヤ、ポータブル音楽プレーヤ、デジタルビデオプレーヤ、ビデオプレーヤ、デジタルビデオディスク(DVD)プレーヤ、およびポータブルデジタルビデオプレーヤが含まれる。
【００５３】
この関連で、図8は、図1に示されるパイプラインバブル低減回路(PBRC)12を利用することができる、プロセッサベースシステム138の一例を示す。この例では、プロセッサベースシステム138は、1つまたは複数のCPU140を含む。CPU140は1つまたは複数のプロセッサ10を含むことができ、一時的に記憶されたデータに迅速にアクセスのためにプロセッサ10に結合されるキャッシュメモリ142を有することができる。プロセッサ10は、パイプラインバブル低減回路12を備えることができる。CPU140は、システムバス144に結合され、プロセッサベースシステム138中に含まれるマスターデバイスとスレーブデバイスとを相互結合することができる。よく知られているように、CPU140は、システムバス144を介してアドレス情報、制御情報、およびデータ情報を交換することによって、これらの他のデバイスと通信する。たとえば、CPU140は、スレーブデバイスの一例として、メモリコントローラ146にバストランザクション要求を通信することができる。図8に示されていないが、複数のシステムバス144を設けることができる。
【００５４】
他のマスターデバイスおよびスレーブデバイスをシステムバス144に接続することができる。図8に示されるように、これらのデバイスは、例として、メモリシステム148、1つまたは複数の入力デバイス150、1つまたは複数の出力デバイス152、1つまたは複数のネットワークインターフェースデバイス154、ならびに1つまたは複数のディスプレイコントローラ156を含むことができる。入力デバイス150は、限定はしないが、入力キー、スイッチ、音声プロセッサなどを含む任意のタイプの入力デバイスを含むことができる。出力デバイス152は、限定はしないが、オーディオ、ビデオ、他の視覚的指示などを含む、任意のタイプの出力デバイスを含むことができる。ネットワークインターフェースデバイス154は、ネットワーク158との間でデータの交換を可能にするように構成された任意のデバイスとすることができる。ネットワーク158は、限定はしないが、ワイヤードネットワークまたはワイヤレスネットワーク、プライベートネットワークまたは公衆ネットワーク、ローカルエリアネットワーク(LAN)、ワイドローカルエリアネットワーク(WLAN)、およびインターネットを含む、任意のタイプのネットワークとすることができる。ネットワークインターフェースデバイス154は、所望の任意のタイプの通信プロトコルをサポートするように構成することができる。メモリシステム148は、1つまたは複数のメモリユニット160(0〜N)を含むことができる。
【００５５】
CPU140はまた、システムバス144を介してディスプレイコントローラ156にアクセスして、1つまたは複数のディスプレイ162に送られる情報を制御するように構成することもできる。ディスプレイコントローラ156は、1つまたは複数のビデオプロセッサ164を介して表示されることになる情報をディスプレイ162に送り、ビデオプロセッサ164は、表示される情報を、ディスプレイ162に適したフォーマットとなるように処理する。ディスプレイ162は、限定はしないが、陰極線管(CRT)、液晶ディスプレイ(LCD)、プラズマディスプレイなどを含む、任意のタイプのディスプレイを含むことができる。
【００５６】
本明細書において開示される実施形態に関連して説明される種々の例示的な論理ブロック、モジュール、回路、およびアルゴリズムは、電子的なハードウェアとして、またはメモリもしくは別のコンピュータ可読媒体に記憶され、プロセッサもしくは他の処理デバイスにより実行される命令として、またはこれら両方の組合せとして実現される場合があることは、当業者にはさらに理解されよう。本明細書において説明されるマスターデバイスおよびスレーブデバイスは、例として、任意の回路、ハードウェア構成要素、集積回路(IC)、ICチップ、または半導体ダイにおいて利用される場合がある。本明細書において開示されるメモリは、任意のタイプおよびサイズのメモリとすることができ、所望の任意のタイプの情報を記憶するように構成することができる。この互換性を明確に示すために、上記では、種々の例示的な構成要素、ブロック、モジュール、回路、およびステップは全般的に、それらの機能に関して説明されている。そのような機能がいかに実現されるかは、具体的な用途、設計の選択、および/またはシステム全体に課される設計制約によって決まる。当業者は、説明される機能を具体的な応用形態ごとに種々の方法で実現することができるが、そのような実現の決定は、本開示の範囲からの逸脱を生じるものと解釈すべきではない。
【００５７】
本明細書において開示される実施形態に関連して説明される種々の例示的な論理ブロック、モジュール、および回路は、プロセッサ、DSP、特定用途向け集積回路(ASIC)、FPGAもしくは他のプログラマブル論理デバイス、個別ゲートもしくはトランジスタ論理、個別ハードウェア構成要素、または本明細書において説明される機能を実行するように設計されたそれらの任意の組合せで実現または実行することができる。プロセッサはマイクロプロセッサとすることができるが、代替形態として、プロセッサは任意の従来のプロセッサ、コントローラ、マイクロコントローラ、または状態機械とすることもできる。また、プロセッサは、コンピューティングデバイスの組合せ、たとえば、DSPとマイクロプロセッサとの組合せ、複数のマイクロプロセッサ、DSPコアと連携する1つもしくは複数のマイクロプロセッサ、または任意の他のそのような構成として実現することもできる。
【００５８】
本明細書において開示される実施形態は、ハードウェアにおいて、およびハードウェアに記憶される命令において具現化することができ、たとえば、ランダムアクセスメモリ(RAM)、フラッシュメモリ、読取り専用メモリ(ROM)、電気的プログラマブルROM(EPROM)、電気的消去可能プログラマブルROM(EEPROM)、レジスタ、ハードディスク、リムーバブルディスク、CD-ROM、または、当技術分野で知られている任意の他の形態のコンピュータ可読媒体内に存在することができる。例示的な記憶媒体は、プロセッサが記憶媒体から情報を読み取り、かつ記憶媒体に情報を書き込むことができるように、プロセッサに結合される。代替形態では、記憶媒体はプロセッサと一体にすることができる。プロセッサおよび記憶媒体はASIC内に存在することができる。ASICは遠隔局内に存在することができる。代替形態では、プロセッサおよび記憶媒体は、遠隔局、基地局、またはサーバの中に、個別の構成要素として存在することができる。
【００５９】
本明細書の例示的な実施形態のいずれかにおいて説明された動作ステップは、例および考察を提供するために説明されることにも留意されたい。説明された動作は、例示された順序以外の数多くの異なる順序で実行することができる。さらに、単一の動作ステップにおいて説明される動作は、実際には、いくつかの異なるステップにおいて実行される場合もある。さらに、例示的な実施形態において論じられた1つまたは複数の動作ステップは、組み合わせることもできる。流れ図において例示される動作ステップは、当業者に容易に明らかとなるような数多くの異なる変更を受けてもよいことは理解されたい。情報および信号は、多種多様な技術および技法のいずれかを使用して表すことができることも、当業者には理解されよう。たとえば、上記の説明全体にわたって参照される場合があるデータ、命令、コマンド、情報、信号、ビット、シンボル、およびチップは、電圧、電流、電磁波、磁界または磁性粒子、光場または光学粒子、あるいはそれらの任意の組合せによって表すことができる。
【００６０】
本開示の前述の説明は、任意の当業者が本開示を作製または使用できるように提供されている。本開示への種々の変更が当業者には容易に明らかになり、本明細書で規定される一般原理は、本開示の趣旨および範囲を逸脱することなく他の変形形態に適用することができる。したがって、本開示は、本明細書において説明される例および設計に限定されるものではなく、むしろ、本明細書において開示される原理および新規の特徴に一致する最も広い範囲を与えられるべきである。
【符号の説明】
【００６１】
10  プロセッサ
12  パイプラインバブル低減回路
14  入力/出力(I/O)回路
16  命令キャッシュ
18  データキャッシュ
20  実行パイプライン
22  フロントエンド回路
24  実行ユニット
26  完了ユニット
28  リンクスタック
30  レジスタ
32  汎用レジスタ
34  プログラムカウンタ
36  リンクレジスタ
38  順次フェッチ/復号化パイプラインステージ
40  順次フェッチ/復号化パイプラインステージ
42  順次フェッチ/復号化パイプラインステージ
44  発行/ディスパッチステージ
46  分岐予測回路
48  分岐制御論理(BCL)回路
50  分岐ターゲット命令キャッシュ(BTIC)
52  分岐ターゲットアドレスキャッシュ(BTAC)
54  分岐履歴テーブル(BHT)
56  サブルーチン呼出し検出回路
58  BTICエントリ確立回路
60  サブルーチンリターン検出回路
62  BTIC使用回路
64  命令シーケンス
66  命令
68  命令
70  命令
72  命令
74  命令
76  命令
78  命令
79  命令
80  プログラムフロー
82  次のフェッチ指示子
84  BTICエントリ
86  矢印
88  実行パイプライン
90  矢印
92  BTICエントリ
94  矢印
96  矢印
98  矢印
99  矢印
102  ブロック
104  ブロック
106  ブロック
108  ブロック
110  ブロック
112  ブロック
113  ブロック
114  ブロック
116  ブロック
117  ブロック
118  ブロック
119  ブロック
120  ブロック
122  ブロック
124  ブロック
126  ブロック
130  ブロック
134  ブロック
136  ブロック
138  プロセッサベースシステム
140  CPU
142  キャッシュメモリ
144  システムバス
146  メモリコントローラ
148  メモリシステム
150  入力デバイス
152  出力デバイス
154  ネットワークインターフェースデバイス
156  ディスプレイコントローラ
158  ネットワーク
160  メモリユニット
162  ディスプレイ
164  ビデオプロセッサ
【図１】
0006271572.tif 000002
【図２】
0006271572.tif 000003
【図３】
0006271572.tif 000004
【図４Ａ】
0006271572.tif 000005
【図４Ｂ】
0006271572.tif 000006
【図５】
0006271572.tif 000007
【図６】
0006271572.tif 000008
【図７Ａ】
0006271572.tif 000009
【図７Ｂ】
0006271572.tif 000010
【図８】
0006271572.tif 000011