(57)【要約】【解決手段】サブルーチン呼び出しを認識する装置が開示される。装置は、レジスタの内容を受信する第１入力と、プログラムフローにおける非逐次的な変化を受信する第２入力と、前記プログラムフローにおける非逐次的な変化の後の逐次的な次のアドレスを受信する第３入力とを備える回路を含む。前記回路は、前記プログラムフローにおける非逐次的な変化がサブルーチン呼び出しであるかを判断するために、前記逐次的な次のアドレスと、前記レジスタの内容とを比較するように構成されている。【選択図】図５
2010511251.tif 000002
【特許請求の範囲】
【請求項１】
プログラムフローにおける非逐次的な変化を検出することと、
前記プログラムフローにおける前記検出された非逐次的な変化の後の逐次的な次のアドレスを読み出すことと、
前記非逐次的な変化がサブルーチン呼び出しであるかを判断するために、前記逐次的な次のアドレスをレジスタの内容と比較することと
を備えた、サブルーチン呼び出しの認識方法。
【請求項２】
前記プログラムフローにおける非逐次的な変化は、分岐命令である、請求項１記載の方法。
【請求項３】
前記レジスタは、リンクレジスタである、請求項１記載の方法。
【請求項４】
前記プログラムフローにおける非逐次的な変化の後の前記逐次的な次のアドレスを、リンクスタック構造にプッシュすること、
を更に備える請求項１記載の方法。
【請求項５】
前記プログラムフローにおける非逐次的な変化はサブルーチン呼び出しであることを示すこと、
を更に備える請求項１記載の方法。
【請求項６】
前記プログラムフローにおける非逐次的な変化はサブルーチン呼び出しであることを示すことは、
前記プログラムフローにおける非逐次的な変化に関連付けられたフラグを、分岐予測回路に格納すること、を備える、請求項５記載の方法。
【請求項７】
サブルーチン呼び出しを認識するプロセッサにおける装置であって、
回路を備え、前記回路は、
レジスタの内容を受信する第１入力と、
プログラムフローにおける非逐次的な変化を受信する第２入力と、
前記プログラムフローにおける非逐次的な変化の後の逐次的な次のアドレスを受信する第３入力と
を備え、前記回路は、前記プログラムフローにおける非逐次的な変化がサブルーチン呼び出しであるかを判断するために、前記逐次的な次のアドレスと、前記レジスタの内容とを比較するように構成されている、装置。
【請求項８】
前記プログラムフローにおける非逐次的な変化は、分岐命令である、請求項７記載の装置。
【請求項９】
前記レジスタは、リンクレジスタである、請求項７記載の装置。
【請求項１０】
リンクレジスタを更に備え、前記装置は、前記プログラムフローにおける非逐次的な変化の後の前記逐次的な次のアドレスを、前記リンクスタック構造にプッシュするように構成されている、請求項７記載の装置。
【請求項１１】
前記プログラムフローにおける非逐次的な変化がサブルーチン呼び出しであることの表示、を格納するように構成された、分岐予測回路を更に備える、請求項７記載の装置。
【請求項１２】
サブルーチン呼び出しを認識する装置であって、
プログラムフローにおける非逐次的な変化を検出する手段と、
前記プログラムフローにおける検出された非逐次的な変化の後の逐次的な次のアドレスを読み出す手段と、
前記非逐次的な変化がサブルーチン呼び出しであるかを判断するために、前記逐次的な次のアドレスをレジスタの内容と比較する手段と
を備えた、装置。
【請求項１３】
前記プログラムフローにおける非逐次的な変化は、分岐命令である、請求項１２記載の装置。
【請求項１４】
前記レジスタは、リンクレジスタである、請求項１２記載の装置。
【請求項１５】
前記プログラムフローにおける非逐次的な変化の後の前記逐次的な次のアドレスを、リンクスタック構造にプッシュする手段を更に備える、請求項１２記載の装置。
【請求項１６】
前記プログラムフローにおける非逐次的な変化がサブルーチン呼び出しであることを示す手段を更に備える、請求項１２記載の装置。
【請求項１７】
前記プログラムフローにおける非逐次的な変化がサブルーチン呼び出しであることを示す手段は、
前記プログラムフローにおける非逐次的な変化に関連付けられたフラグを、分岐予測回路に格納する手段を備える、請求項１２記載の装置。
【請求項１８】
サブルーチン呼び出しを認識するプロセッサにおける装置であって、
命令を処理するプロセッサパイプラインと、
前記プロセッサパイプラインに結合された回路と
を備え、前記回路は、レジスタの内容と、プログラムフローにおける非逐次的な変化の表示と、前記プログラムフローにおける非逐次的な変化の表示の後の逐次的な次のアドレスと、を受信するように構成され、
前記回路は、前記プログラムフローにおける非逐次的な変化の表示がサブルーチン呼び出しであるかを判断するために、前記逐次的な次のアドレスと、前記リンクレジスタの内容とを比較するように構成されている、装置。
【請求項１９】
リンクスタック構造を更に備え、前記回路は、前記リンクレジスタの前記内容を、前記リンクスタック構造にプッシュするように構成されている、請求項１８記載の装置。
【請求項２０】
分岐予測回路を更に備え、前記回路は、前記プログラムフローにおける非逐次的な変化がサブルーチン呼び出しであることの表示を格納するように構成されている、請求項１８記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、大まかにはパイプライン型のプロセッサの領域に関する。より具体的には、消費電力を削減し、またパイプライン型のプロセッサの稼働率を向上させるために、サブルーチン呼び出しを認識する方法に関する。
【背景技術】
【０００２】
マイクロプロセッサは、多種多様なアプリケーションにおいて計算のタスクを実行する。プロセッサの性能の向上は、高速動作、及び／またはソフトウェアの変更を通じた強化された機能性を可能にするために、ほぼ常に望ましい。ポータブルの電子機器のような多くの組み込みアプリケーションでは、省電力もまた、プロセッサの設計及び実装に重要な目標となる。
【０００３】
多くの現代のプロセッサは、パイプラインアーキテクチャを採用する。パイプラインアーキテクチャでは、プロセッサ全体としてのスループットを向上させるため、逐次的な命令が、実行の際にオーバーラップする。パイプライン全体を通して円滑な実行を維持することは、高い性能の実現に寄与する。最新のプロセッサはまた、最近アクセスされたデータ及び命令のローカルコピーを保持する、高速なオンチップキャッシュメモリを有する、階層化メモリを利用する。
【０００４】
実世界におけるプログラムは間接分岐命令を含み、間接分岐命令では、実行パイプラインの深いところで命令が実際に判断されるまでは、分岐の実際のふるまいは分からない。最新のプロセッサは、パイプステージのデコードやフェッチの期間のようなパイプラインの早期に、間接分岐命令における分岐動作が予測される、分岐予測のいくつかの形態を使用する。分岐予測技術の使用によりプロセッサは、間接分岐命令のターゲットを投機的に（speculatively）フェッチし、また投機的にフェッチされた命令の処理を開始するためにパイプラインをリダイレクト（redirect）する。実際の分岐ターゲットが、実行パイプステージのような後段のパイプステージにおいて判断される際には、もし分岐が予測ミスされた場合、投機的にフェッチされた命令はパイプラインからフラッシュされなければならず、新たな命令が正しいターゲットアドレスからフェッチされる。誤った分岐ターゲット予測に応答したプリフェッチ命令は、プロセッサの性能や消費電力に不利に影響する。
【０００５】
間接分岐命令の一例は、サブルーチンから復帰するために使用される分岐命令を含む。例えば、サブルーチンからの復帰呼び出しは、復帰アドレスがレジスタのコンテンツによって定義された分岐命令を含み得る。復帰アドレスは、このサブルーチンが完了した後にフェッチされる次の命令を定義し、このサブルーチンをそもそも呼び出す分岐命令の後の一般的な命令である。多くの高性能アーキテクチャは、サブルーチン復帰に使用するための、リンクレジスタと一般的に呼ばれる個々の汎用レジスタを指定する。
【０００６】
便宜上、復帰呼び出しはまた、分岐復帰命令とも呼ばれ得る。プロセッサパイプラインが分岐復帰命令につき分岐予測を使用するために、従来のソフトウェアは、復帰アドレスをリンクレジスタに記録するために、分岐及びリンク命令のような直接的（explicit）なサブルーチン呼び出しを含む。多くの高性能実装では、分岐及びリンク命令の処理のデコードステージにリンクスタック構造（link stack structure）が含まれる。リンク戻り値は、このスタック上にプッシュされる。これは、対応するサブルーチンが復帰する際に精密な分岐予測を可能にするためである。従来のリンクスタック構造は、パイプラインを通じて流れる複数のサブルーチン呼び出しをサポートし、またサブルーチン呼び出しの複数のレベルのネスト化をサポートするために、復帰アドレスのリストを含む。続いて、サブルーチン内の分岐復帰命令がデコードされている際、もし他の分岐予測ハードウェアが、プロセッサがパイプラインをリダイレクトすべきと決定した場合、ターゲットアドレスを予測する分岐予測において使用されるリンクスタック構造から、復帰アドレスが読み出される。もし、予測結果がパイプラインのリダイレクトすることを示していれば、パイプラインは、リンクスタック構造から読み出された復帰アドレスからの命令のフェッチを開始する。
【０００７】
しかしながら、サブルーチンの呼び出しの際に、従来の分岐及びリンク命令を生成せずまたは組み込まないような、多くのコンパイラ及びレガシーコードが存在する。従って、そのような状況では、リンクスタック構造は、リンクスタック構造のインテグリティ（integrity）が脅かされる結果、使用されない。例えば、従来の、リンクスタック構造からの復帰アドレスのポップ（popping）は、そもそも復帰アドレスのポップをシミュレートした復帰命令に関連付けられないかもしれない。脅かされたリンクスタック構造の一つの影響には、復帰命令上における予測ミスの増加が含まれる。更に、サブルーチンの読み出しがプログラムセグメントにおいて認識されないそのような状況では、問題は複雑になる。なぜなら、分岐予測ハードウェアが、連続する認識不能なサブルーチン呼び出し上のリンクスタック構造を満たすためには使用されないからである。例として、ARM Ltd. コンパチブルプロセッサ上で実行され得るコードセグメントを含む下記の表を参照する。
【表１】
2010511251.tif 000003
【０００８】
表１のコードセグメントのプログラムフローは、アドレス０ｘ００８９９８０８からスタートしてアドレス０ｘ００８９９８１４までの連続的な順番での命令の処理を含む。アドレス０ｘ００８９９８１４では、分岐命令はプログラムフローを、処理される次の命令がアドレス０ｘ００９９００００（サブルーチンの開始）に位置するように変更する。
【０００９】
リンクレジスタのセット（例えばＬＤＲ ＬＲ、０ｘ００８９９８１８）と分岐命令（例えばＢＲ）の組み合わせは、プロセッサに、その後のサブルーチンへの分岐を準備させる。本例では、呼び出される実際のサブルーチンは、アドレス０ｘ００９９００００で開始し、アドレス０ｘ００９９０００Ｃで終了する。ＬＤＲ、ＬＲ、０ｘ００８９９８１８命令は、アドレス０ｘ００８９９８１８がリンクレジスタ（ＬＲ）にコピーされるべきことを示し、その結果、復帰アドレス（０ｘ００８９９８１８）がリンクレジスタに保持される。サブルーチンの終わりでは、復帰アドレスがリンクレジスタから読み出される。より具体的には、復帰アドレスは、分岐復帰命令であるＢＸ ＬＲの実行時に読み出される。サブルーチン呼び出しを意味するその他のコードセグメントが存在し、リンクレジスタを変形する命令を含む。それは、ＭＯＶ ＬＲ、ＰＣ ＢＲ ［Ａ］命令の連続した組み合わせのようなものである。なお、［Ａ］は、サブルーチンの開始アドレスである。
【発明の概要】
【００１０】
本開示は、そのようなレガシーソフトウェア、サブルーチン呼び出しに対応する２つまたはそれ以上の命令を有するコードセグメントを生成するコンパイラ、及びサブルーチンを呼び出す際に従来の分岐及びリンク命令を使用するためのレガシーソフトウェアの書き換えに必要なコストの拡がりを考慮する。更に本開示は、分岐復帰命令の際に復帰アドレスを効果的に予測し、リンクスタック構造を使用するために、サブルーチン呼び出しを意味する命令列を認識する、今日開発されたマイクロプロセッサの必要性を考慮する。
【００１１】
一形態によれば、サブルーチン呼び出しの認識方法が与えられる。方法は、プログラムフローにおける非逐次的な変化を検出することと、前記プログラムフローにおける前記検出された非逐次的な変化の後の逐次的な次のアドレスを読み出すことと、前記非逐次的な変化がサブルーチン呼び出しであるかを判断するために、前記逐次的な次のアドレスをレジスタの内容と比較することと、を含む。
【００１２】
別の形態は、サブルーチン呼び出しを認識するプロセッサにおける装置に関する。前記装置は、３つの入力を有する回路を含む。第１入力は、レジスタの内容を受信するように構成されている。第２入力は、プログラムフローにおける非逐次的な変化を受信するように構成されている。第３入力は、前記プログラムフローにおける非逐次的な変化の後の逐次的な次のアドレスを受信するように構成されている。前記回路は、前記プログラムフローにおける非逐次的な変化がサブルーチン呼び出しであるかを判断するために、前記逐次的な次のアドレスと、前記レジスタの内容とを比較するように構成されている。
【００１３】
更に別の形態によれば、別の装置が開示される。前記装置は、命令を処理するプロセッサパイプラインと、それに結合された回路とを備える。前記回路は、レジスタの内容と、プログラムフローにおける非逐次的な変化の表示と、前記プログラムフローにおける非逐次的な変化の表示の後の逐次的な次のアドレスとを受信するように構成されている。前記回路はまた、プログラムフローにおける非逐次的な変化の前記表示がサブルーチン呼び出しであるかを判断するために、前記逐次的な次のアドレスと、前記リンクレジスタの内容とを比較するように構成されている。
【００１４】
本発明の他の形態が容易に明らかになるであろうことが、本発明の種々の形態が例として図示され説明される、後述する詳細な説明から、当業者に理解される。理解されるように、本発明は、その他の異なる形態が可能であり、その幾つかの詳細は、本発明から逸脱しない種々のその他の観点から変形されることが出来る。従って、図面及び詳細な説明は、本来、例示的なものとみなされ、限定的なものとしてみなされるべきものでは無い。
【図面の簡単な説明】
【００１５】
【図１】図１は、プロセッサの機能ブロック図。
【図２】図２は、図１に示すパイプラインを通過する命令の典型的な流れに従うタイミング図。
【図３】図３は、分岐ターゲットアドレスキャッシュ（ＢＴＡＣ）の典型的な部分。
【図４Ａ】図４Ａは、図１に示すIsCallロジック回路の典型的な形態。
【図４Ｂ】図４Ｂは、図１に示すIsCallロジック回路の典型的な形態。
【図５】図５は、サブルーチン呼び出しをrecognizeする方法を示すフローチャート。
【発明を実施するための形態】
【００１６】
図１は、本発明の側面が用いられ得るプロセッサ１００の機能ブロック図を示す。プロセッサ１００は、最近処理された命令をキャッシュする命令キャッシュ（I-キャッシュ）１１０と、I-キャッシュで命令が見つからなかった際にメモリ１３８にアクセスするためのメモリインターフェース１３６を含む。メモリ１３８は、プロセッサ１００内または外に配置され得、レイヤ２（Ｌ２）メモリ要素を備え得る。
【００１７】
プロセッサ１００はまた、命令を処理する命令パイプライン１０５と、間接分岐命令についてターゲットアドレスを予測し、ターゲットアドレスを処理するために命令パイプライン１０５をリダイレクトするかを予測する分岐予測回路１３２とを含み得る。もし、分岐予測回路１３２が命令パイプライン１０５のリダイレクトを予測した場合には、間接分岐命令は、「予測成立」したと呼ばれる。もし間接分岐命令が「予測成立」した場合には、分岐予測回路１３２は、分岐予測回路１３２は、間接分岐命令のターゲットアドレスを予測し、このターゲットアドレスにおける命令のフェッチを開始するために、命令パイプライン１０５をリダイレクトする。
【００１８】
プロセッサ１００は、制御ロジック回路１２２に従って、命令パイプライン１０５における命令を処理する。ある形態では、パイプライン１０５は２つまたはそれ以上の並列パイプラインを有するスーパースカラ設計であり得る。パイプライン１０５は、種々のパイプステージを含む。それは、命令フェッチユニット（ＩＦＵ）ステージ１０２、デコード（ＤＣＤ）ステージ１０６、命令キュー（ＩＱ）ステージ１０８、レジスタアクセス（ＲＡＣＣ）ステージ１１２、及び実行ステージ（ＥＸＥ）１２０である。ある形態では、パイプステージは一度に単一の命令を処理し得る。別の形態では、パイプステージは、同時に２つまたはそれ以上の命令を、同時に処理し得る。本開示の範囲に限定されることなく、パイプステージはパイプライン１０５に加えられ、または削除され得ることに注意すべきである。プロセッサ１００はまた、マイクロアーキテクチャラル仕様（microarchitectural convention）を介して、パイプステージ１１２及び１２０によってアクセス可能なレジスタを含む汎用レジスタ（ＧＰＲ）ファイル１１８を含む。
【００１９】
命令フェッチユニット（ＩＦＵ）ステージ１０２は、I-キャッシュ１１０からの命令の読み出しを試みる。もし、命令アドレスがI-キャッシュ１１０内に見つからない場合には、命令フェッチユニット（ＩＦＵ）は、対応する命令をメモリ１３８から取り出す要求を開始する。デコードステージ１０６は、命令を十分にデコードする。更に、デコードステージにおいて実行される従来の機能に加えてデコードステージ１０６は、ARM Inc.の分岐及びリンク命令のような従来のサブルーチン呼び出し命令を認識し、復帰アドレスをリンクスタック構造１３４に書き込む。リンクスタック構造１３４は、サーキュラーバッファとして管理されるレジスタのセットであり得る。復帰アドレスは、サブルーチンの完了時にパイプライン１０５がリダイレクトされる命令のアドレスである。間接分岐命令においてデコードステージ１０６は、分岐命令の投機的なターゲットからパイプライン１０５への命令のフェッチを開始するかを判断するために、分岐予測回路１３２を呼び出す。
【００２０】
命令キューステージ１０８は、実行パイプラインのストールが生じた場合には、その期間、投機的なフェッチを継続するための１つまたはそれ以上の命令をバッファリングする。レジスタアクセスステージ１１２は、命令によって必要とされ得る際に、汎用レジスタ１１８から１つまたはそれ以上のオペランドを読み出す。実行ステージ（ＥＸＥ）は、命令を実行するために、算術論理演算ユニット等の既知の要素を含む。実行ステージ１２０で生成された結果は、ＧＰＲファイル１１８に書き込まれる。実行ステージ１２０の期間に、実際の分岐の解決（resolution）が行われ、デコードステージ１０６で成された分岐予測が正しいかが確認される。もし実際の分岐先が予測された行き先と異なっていれば、分岐は予測ミスされたと言われる。
【００２１】
実行ステージ１２０はまた、IsCall論理回路１１４を呼び出し、分岐命令が間接的（implicit）なサブルーチン呼び出しに対応するかを確認する。IsCall論理回路１１４は、この結果を分岐予測（ＢＰ）回路１３２に記録する。これは、その後の、間接的なサブルーチン呼び出しとして解釈される分岐命令の、ＤＣＤ１０６またはＩＦＵ１０２のような前段のパイプステージの期間における実行のためである。一形態では、記録された結果は、ＢＰ回路１３２に保持され、分岐命令に関連付けられたフラグである。もし分岐命令が間接的なサブルーチン呼び出しであれば、IsCall論理回路１１４は、分岐命令に引き続く命令のアドレスによって、リンクスタック構造１３４をアップデートする。IsCall論理回路１１４は、図４の議論に関連して、更に詳細に説明される。
【００２２】
図１では、IsCall論理回路１１４と結合された実行ステージ（ＥＸＥ）１２０が図示されているが、IsCall論理回路１１４は、代わりにパイプライン１０５のより前段のステージに結合され得る。代わりの形態としては、デコードステージ（ＤＣＤ）１０６が、IsCall論理回路１１４に結合され得る。この形態では、ＢＲ命令がデコードされたと判断するたびに、デコードステージ（ＤＣＤ）１０６がIsCall論理回路１１４を呼び出す。
【００２３】
当業者は、プロセッサ１００の多数の変形例が可能であることを認識するだろう。例えば、プロセッサ１００はI-キャッシュ１１０について、第２レベル（Ｌ２）キャッシュを含んでも良い。更に、プロセッサ１００に示された１つまたはそれ以上の機能ブロックが、特定の形態から省略されても良い。変換索引バッファ（translation lookaside buffer）やデータキャッシュ等のような、プロセッサ１００内に配置し得る他の機能ブロックは、本願の説明に密接に関係するものでは無く、明瞭化のために省略している。
【００２４】
図２は、図１に示すパイプライン１０５を通り抜ける命令の流れを追ったタイミング図２００である。より具体的には、タイミング図２００でトレースされた命令の流れは、表１に示すコードセグメントである。本開示の目的のため、用語「間接的なサブルーチン呼び出し」は、組み合わされた機能が、サブルーチン呼び出しを準備するレジスタのセットと、サブルーチン呼び出しである、２つまたはそれ以上の命令の組み合わせを指す。例えば表１を参照して、２つの命令ＬＤＲ ＬＲ、０ｘ００８９９０８と、ＢＲ ０ｘ００９９００００が、間接的なサブルーチン呼び出しを定義する。この場合、ＬＤＲ命令は、間接的なサブルーチン呼び出しの開始を定義し、ＢＲ命令は、間接的なサブルーチン呼び出しの終了を定義する。
【００２５】
タイミング図２００の列２１０Ａ−２１０Ｅは、パイプライン１０５のステージに相当する。行１−１１は、連続するタイミングサイクルに相当する。説明の目的で、各パイプステージは１サイクルあたり１つの命令を処理する。しかし、本開示の教示は、複数サイクルのパイプステージや、１サイクルあたり複数の命令を処理することが可能なパイプステージに適用出来ることが、当業者によって認識されるべきである。
【００２６】
タイミング図２００の列２１０Ｆは、間接分岐命令の結果がサブルーチン呼び出しであるかを示す、IsCallフラグと呼ばれるフラグの内容に相当する。列２１０Ｇは、リンクレジスタ（ＬＲ）の内容に相当する。列２１０Ｈは、IsCall論理回路１１４の結果としての、リンクスタック構造１３４のようなリンクスタック構造の内容に相当する。
【００２７】
一般的に、命令はＩＦＵステージ２１０Ａに投入されて、次のサイクルで次のステージに伝搬される。サイクル１では、ＬＤＲ ＬＲ、０ｘ００８９９８１８命令がＩＦＵステージ２１０Ａ内にある。命令ＡＤＤ、ＳＵＢ、ＢＲ、及び一般的な（generic）命令ＩＮＳＴＲＡが、順次、ＩＦＵパイプステージ２１０Ａからフェッチされる。サイクル５では、時刻２１５において、デコードステージ２１０ＢがＢＲ命令をデコードし、分岐予測回路１３２のような分岐予測を呼び出す。分岐予測は、ＢＲ命令が取り込まれることを予測し、よってサブルーチン命令ＡＤＤ、ＳＵＢ、ＭＯＶ、及びＢＸを順次フェッチするためにパイプライン１０５がリダイレクトされる。サブルーチンは、表１に示されるＡＤＤ命令から始まってＢＸ命令で終了するまでの全ての命令を備える。パイプライン１０５をリダイレクトする前に、ＩＮＳＴＲＡがパイプライン１０５からフラッシュされる。これは、ＩＮＳＴＲＡが分岐予測の前にフェッチされたからである。ＢＲ命令に引き続くブランクサイクルは、パイプライン１０５において、フラッシュされずに取り込まれた場合のＩＮＳＴＲＡ命令の位置を示す。
【００２８】
サイクル１−５で、ＬＤＲ命令がパイプステージ２１０Ｂ−２１０Ｅを伝搬する。時刻２０５のサイクル５において、実行ステージ２１０ＥはＬＤＲ命令を実行して、復帰アドレス０ｘ００８９９８１８をリンクレジスタ（ＬＲ）にロードする。時刻２２０において、復帰アドレス（ＲＡ）０ｘ００８９９８１８はリンクレジスタに取り込まれる。復帰アドレスは、表１におけるＩＮＳＴＲＡを指す。これは、アドレス０ｘ００９９００００で開始するサブルーチンの実行終了時に、命令実行のフローがアドレス０ｘ００８９９８１８に戻るべきであることを意味する。
【００２９】
時刻２２５において、実行ステージ２１０Ｅは、ＢＲ命令を実行する。実行ステージ２１０Ｅは、ＢＲ命令が取り込まれるべきだったか否かを確認する。実行ステージ２１０ＥはまたIsCall論理回路１１４を呼び出し、ＢＲ命令がサブルーチンへの分岐であるかを判断する。フレーズ「サブルーチンへの分岐」はまたサブルーチン呼び出しとも呼ばれる。IsCall論理回路１１４は、ＩＮＳＴＲＡが先にパイプライン１０５からフラッシュされたにもかかわらず、ＩＮＳＴＲＡのアドレスである、ＢＲ命令に続く次のアドレスを使用する。この次の命令のアドレスはリンクレジスタ（ＬＲ）に保持される復帰アドレスと等しいので、IsCall論理回路１１４は、このＢＲ命令に関連付けられたIsCallフラグ２１０Ｆをセットし、これを分岐予測回路１３２内にＢＲ命令のアドレスと共に保持する。典型的な分岐予測保持要素は、図３に関連して説明される。また、IsCall論理回路１１４は、時刻２３０において、復帰アドレスをリンクスタック構造２１０Ｈにコピーする。
【００３０】
サブルーチンの最後の命令ＢＸは、時刻２３５のサイクル１０でデコードされる。デコードステージ２１０Ｂは、ＢＸ命令を復帰呼び出しとして認識し、従って分岐予測１３２は、復帰アドレス（ＲＡ）をリンクスタック構造２１０Ｈからポップすることにより、プログラムフローを予測する。デコードステージ２１０Ｂは、アドレスが復帰アドレス（ＲＡ）に等しいＩＮＳＴＲＡからのフェッチを開始するため、パイプライン１０５をリダイレクトする（ポイント２４０参照）。またサイクル１１では、ＲＡがポップされたため（例えば、リンクスタック構造から読み出されて削除される）、リンクスタック構造２１０Ｈはもはや、復帰アドレスを保持しない。図１のプロセッサをタイミング図２００に示されるように用いることで、リンクスタック構造に復帰アドレスを保持させることが可能な、ＬＤＲ及びＢＲの組み合わせ命令によって、間接的なサブルーチン呼び出しが定義される。
【００３１】
次回、ＢＲ命令がパイプライン１０５によって処理される際、分岐予測回路１３２は、そこに保持され、ＢＲ命令のアドレスに関連付けられた、セットされたIsCallフラグを使用し得る。そしてこれにより、最初にＢＲ命令がパイプライン１０５によって処理された際よりも速やかに、リンクスタック構造を満たし（populate）得る。
【００３２】
クロックサイクルｎでは、同様のＢＲ命令がパイプライン１０５に、ＩＦＵステージ２１０Ａで投入される。クロックサイクルｎ＋１では、ＩＮＳＴＲＡがＩＦＵステージ２１０Ａに投入され、ＢＲ命令はＤＣＤステージ２１０Ｂでデコードされる。ＤＣＤステージ２１０Ｂの期間、分岐予測回路１３２はＢＲ命令のアドレスを調べ、それが、該ＢＲ命令はサブルーチン呼び出しであることを示す、セットされたIsCallフラグに対応していることを見いだす。従ってＤＣＤステージ２１０Ｂは、参照符号２４５に示されるように、次のアドレス（ＩＮＳＴＲＡのアドレス）をリンクスタック構造２１０Ｈにプッシュする。
【００３３】
図３は、分岐ターゲットアドレスキャッシュ（ＢＴＡＣ）の一部の典型例である。ＢＴＡＣ３００は、分岐予測回路１３２によって適切に使用される。ＢＴＡＣ３００は、少なくとも３つの列、列３１０Ａ、３１０Ｂ、及び３１０Ｎを含む。列３１０Ａは、分岐命令のアドレスを収容する。列３１０Ｂは、分岐ターゲットアドレス、すなわち、対応する分岐命令が分岐する最初のアドレスを収容する。列３１０Ｎは、IsCallフラグの値を収容する。IsCallフラグは、セットされている際には、関連付けられた分岐命令がサブルーチン呼び出しであることを示す。行３０５は、表１においてアドレスが０ｘ００８９９８１４のＢＲ命令に対応し、そのターゲットアドレスはＡＤＤ命令に対応する０ｘ００９９００００であり、そのIsCallフラグはセットされている。
【００３４】
図４Ａ及び４Ｂは、IsCall論理回路の種々の形態を示す。これらの形態は、図１に示される実行パイプステージ１２０、またはより前段のパイプステージに結合され得る。図４Ａは、図１に適切に使用され得るIsCall論理回路４００の典型的な形態である。IsCall論理回路４００は、比較器４４０、２ポートＯＲゲート４４５、及び２ポートＡＮＤゲート４５０を含む。比較器４４０は、２つの入力を受信する。この入力は、リンクレジスタ（ＬＲ）４０５の値を含む入力と、次のアドレス４１０を含む入力である。図２で説明したように、次のアドレスは、ＢＲ命令の後に引き続いてフェッチされる次のアドレスである。比較器４４０の出力は、２ポートＯＲゲート４４５の１ポートに結合される。他のポートは、IsCall論理回路４００が結合されたパイプステージにおける現在の命令が分岐及びリンク命令であるかを示す信号４１５に結合される。ＯＲゲート４４５は任意であり、間接的なサブルーチンと同じように分岐及びリンク命令をサポートするために使用される。ＯＲゲート４４５の出力は、２ポートＡＮＤゲート４２５の１ポートに結合される。他のポートは、分岐予測回路１３２によって生成されたisTakenBranch信号４２０が結合される。分岐予測回路１３２は、IsCall論理回路４００を呼び出したＢＲ命令から、isTakenBranch信号４２０を生成する。投機的でない形態では、ＥＸＥステージ１２０が代わりにisTakenBranch信号４２０を生成し得る。IsCall論理回路４００の出力４２５が正である際には、出力４２５は分岐予測回路１３２においてisCallフラグをセットするために用いられ、またリンクスタック構造に復帰アドレスをコピーするために用いられる。当業者によれば、他のロジック回路が、間接分岐命令がサブルーチン呼び出しに相当することを示しているかを制御し、もしそうならリンクスタック構造を次のアドレスでアップデートするように制御するために、IsCall論理回路４００において使用し得ることを認識するだろう。
【００３５】
図４Ｂは、図１で適切に使用され得るIsCall論理回路４０１の第２の形態である。比較器４４０とその入力と、IsCall論理回路４０１の出力とは、図４Ａに示されたものと同様である。比較器４４０の出力は、入力として、ＡＮＤゲート４５５へ送り込まれる。ＡＮＤゲート４５５はまた、入力としてisBranch信号４３０を受信する。isBranch信号４３０は、IsCall論理回路４０１に結合されたパイプステージによって処理されている現在の命令が分岐命令である際に、アクティブとなる。動作中、もし現在の命令が分岐命令であり、分岐命令の次のアドレスがリンクレジスタに保持されるアドレスと等しければ、出力信号４２５は、isCallフラグを、分岐予測回路１３２内においてこの分岐命令に関連付けるために使用され、リンクスタック構造１３４は次のアドレスによりアップデートされる。この第２の形態によれば、従来の方法によって、IsCall論理回路４０１の外で分岐及びリンク命令を処理可能となる。
【００３６】
図５は、サブルーチンを認識する方法５００を示すフローチャートである。ブロック５１０において、非逐次的（non-sequential）な変化がプログラムフロー内で検出される。例えば、分岐命令である。より具体的には、分岐及びリンク命令では無い分岐命令が検出される。そのような検出は、すでに知られたデコード技術によって実行可能である。ブロック５１５では、方法５００は、プログラムフロー内で検出された非逐次的な変化が、サブルーチン呼び出しとして既に示されているかを判断する。例えば、もし分岐命令が既にパイプライン１０５によって処理されていれば、目下処理された分岐命令がサブルーチン呼び出しとして示されまたは明らかとされていることを示すisCallフラグが、分岐予測回路１３２にセットされただろう。もしそうなら、方法５００は、プログラムフローにおけるこの非逐次的な変化を前に処理しているので、ブロック５５０に進む。
【００３７】
もし、プログラムフローにおいて検出された非逐次的な変化が、以前にサブルーチン呼び出しとして示されていなければ、方法５００はブロック５２０に進む。ブロック５２０において、プログラムフローにおいて検出された非逐次的な変化の後の次の逐次的なアドレスが読み出される（retrieve）。例えば、分岐命令の後の次のアドレスである。次のこのアドレスは、ＩＦＵステージ１０２内の次のプログラムカウンタ（ＰＣ）生成回路や、先行するパイプステージ等を含む、種々の手段によって与えられ得る。ブロック５３０では、逐次的な次のアドレスが、リンクレジスタの内容と比較される。図２に関連して上記説明したように、サブルーチン呼び出しを予想して、リンクレジスタ（ＬＲ）は復帰アドレスを割り当てられる。ブロック５４０では、プログラムフローにおける検出された非逐次的な変化が、サブルーチン呼び出しとして示される。例えば、分岐命令に関連付けられたフラグがセットされ、分岐予測回路１３２に保持され得る。方法５００はその後、ブロック５５０に進む。
【００３８】
ブロック５５０において、リンクレジスタの内容が、リンクスタック構造にプッシュされる。例えば、分岐命令が図２に示すように実行された際、リンクレジスタはリンクスタック構造にコピーされる。同等に、逐次的な次のアドレスが代わりにリンクスタック構造にプッシュされても良い。説明されていないが、プログラムフローにおける非逐次な変化は、パイプラインによって処理されるサブルーチンを読み出す。ブロック５６０において方法５００は、サブルーチンの終了を示す復帰呼び出しを待つ。復帰呼びだしが認識されると、方法５００はブロック５７０に進み、逐次的な次のアドレスがリンクスタック構造からポップされる。ブロック５７０はプロセッサに対して、復帰呼び出しのアドレスにおける命令の処理を開始するために、パイプラインの処理をリダイレクトさせる。
【００３９】
方法５００は、プログラムフローにおける次の非逐次的な変化を待つ、待ちブロック５８０に進む。プログラムフローにおける次の非逐次な変化がパイプラインに達すると、方法５００はブロック５１０に進み、その後ブロック５１５に進む。もし、プログラムフローにおける次の非逐次的な変化が以前に検出されていれば、プログラムフローにおけるこの次の非逐次的なこの変化は、既に表示されているだろうから、よってブロック５１５はブロック５５０に進む。
【００４０】
本明細書で開示された形態に関連して説明された、種々の例示的な論理ブロック、モジュール、回路、素子、及び／または要素は、汎用レジスタ、デジタルシグナルプロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイシグナル（ＦＰＧＡ）またはその他のプログラマブルな論理回路、ディスクリートゲートまたはトランジスタロジック、ディスクリートハードウェア要素、または本明細書で述べられた機能を実行するように設計されたこれらの組み合わせによって、実行または実装され得る。汎用プロセッサは、マイクロプロセッサであり得るが、代わりにプロセッサは従来の任意のプロセッサ、コントローラ、マイクロコントローラ、またはステートマシンであっても良い。プロセッサはまた、ＤＳＰとマイクロプロセッサとの組み合わせなど、演算デバイスの組み合わせ、ＤＳＰコアと接続された１つまたはそれ以上のマイクロプロセッサ、または他のそのような構成として、実装され得る。
【００４１】
本明細書に開示された形態に関連して述べられた方法は、ハードウェア、プロセッサによって実行されるソフトウェアモジュール、またはこれらの２つの組み合わせにおいて、直接的に実施され得る。ソフトウェアモジュールは、ＲＡＭメモリ、フラッシュメモリ、ＲＯＭメモリ、ＥＰＲＯＭメモリ、ＥＥＰＲＯＭメモリ、レジスタ、ハードディスク、リムーバブルディスク、ＣＤ−ＲＯＭ、または技術的に知られたその他の形態の記憶媒体に保持され得る。記憶媒体は、この記憶媒体から情報を読み出し、またこの記憶媒体に情報を書き込むことが出来るプロセッサのようなプロセッサに接続され得る。代わりに、この記憶媒体はプロセッサと一体化されても良い。
【００４２】
本発明は、実施形態に照らして開示されたが、広く種々の実施が、上記の議論と下記に続き特許請求の範囲に一致する当業者によって認識されるだろう。
【図１】
2010511251.tif 000004
【図２】
2010511251.tif 000005
【図３】
2010511251.tif 000006
【図４Ａ】
2010511251.tif 000007
【図４Ｂ】
2010511251.tif 000008
【図５】
2010511251.tif 000009
【国際調査報告】
2010511251.tif 000010
2010511251.tif 000011