(57)【要約】      （修正有）【課題】明示的サブルーチンコールの分岐予測動作をエミュレートするための装置を提供する。【解決手段】装置は、命令アドレスおよび第2の入力を受け取るように構成されている第1の入力を含んでいる。第2の入力は、サブルーチンへの黙示的サブルーチンコールに関係するものとして命令アドレスを記述するプリデコード情報を受け取るように構成されている。プリデコード情報に応答して、本装置は、リターンアドレスを定義する前記命令アドレスに一定数を加えるように構成されている加算器も含んでいる。このことにより、本装置は、リターンアドレスを明示的サブルーチンリソースに記憶し、もってリターンコール命令の後続の分岐予測を容易にすることができる。【選択図】図５
2014002769.tif 000002
【特許請求の範囲】
【請求項１】
明示的サブルーチンコールの分岐予測動作をエミュレートする方法であって、
サブルーチンへの黙示的サブルーチンコールを示す命令アドレスを認識すること、
前記命令アドレスからリターンアドレスを計算すること、および
前記リターンアドレスを明示的サブルーチンリソースに記憶すること
を具備する方法。
【請求項２】
前記サブルーチンからのリターンコールを示す分岐命令に応答して、前記明示的サブルーチンリソースから前記リターンアドレスを読み出すこと
をさらに具備する、請求項1に記載の方法。
【請求項３】
プロセッサパイプラインを前記リターンアドレスにリダイレクトすること
をさらに具備する、請求項2に記載の方法。
【請求項４】
前記命令アドレスを認識することは、
プリデコード情報を定義する前記命令アドレスに関連する前記命令をプリデコードすること、および
プリデコード情報が前記黙示的サブルーチンコールの開始として前記命令アドレスを示しているかどうか決定すること
をさらに具備する、請求項１に記載の方法。
【請求項５】
前記命令アドレスから前記リターンアドレスを計算することは、
前記命令アドレスに一定数のオフセットを加えること
を具備する、請求項１に記載の方法。
【請求項６】
前記明示的サブルーチンリソースは、リンクスタック構造である、請求項1に記載の方法。
【請求項７】
命令アドレスを受け取るように構成されている第1の入力、
プリデコード情報を受け取るように構成されている第2の入力、ここにおいて、前記プリデコード情報は、サブルーチンへの黙示的サブルーチンコールに関連するものとして前記命令アドレスを記述するものである、および
前記プリデコード情報に応答して、リターンアドレスを定義する前記命令アドレスにオフセットを加え、その結果前記リターンアドレスが明示的サブルーチンリソースに記憶されるようにするように構成されている加算器
を具備する装置。
【請求項８】
前記明示的サブルーチンリソースは、前記サブルーチンからのリターンコールを示す分岐命令に応答して読まれる、請求項7に記載の装置。
【請求項９】
前記プリデコード情報は、前記黙示的サブルーチンコールの開始として前記命令アドレスをさらに記述する、請求項7に記載の装置。
【請求項１０】
前記プリデコード情報は、前記黙示的サブルーチンコールの終了として前記命令アドレスをさらに記述する、請求項7に記載の装置。
【請求項１１】
前記明示的サブルーチンリソースは、リンクスタック構造である、請求項7に記載の装置。
【請求項１２】
前記命令アドレスとともに第2の命令アドレスを同時に受け取る第3の入力、および
前記命令アドレスまたは前記第2の命令アドレスを前記明示的サブルーチンリソースに送るべきかどうか決定するように構成されている論理
をさらに具備する、請求項7に記載の装置。
【請求項１３】
明示的サブルーチンコールに応答して、前記命令アドレスに第2の一定数のオフセットを加えるように構成されている第2の加算器
をさらに具備する、請求項7に記載の装置。
【請求項１４】
第1および第2の命令アドレスおよび関連するプリデコード情報を同時に受け取るように構成されている第1および第2の入力、
前記第1または第2の命令アドレスがサブルーチンへの黙示的サブルーチンコールに関連していることを示す前記プリデコード情報に応答して、第1および第2の結果を定義する前記第1および第2の命令アドレスに一定のオフセットを加えるように構成されている加算器の第1のセット、および
前記第1および第2の結果のうちの1つからリターンアドレスを選ぶための手段
を具備する装置。
【請求項１５】
明示的サブルーチンリソースに前記リターンアドレスを書き込むための手段
をさらに具備する、請求項14に記載の装置。
【請求項１６】
前記第1または第2の命令アドレスが前記黙示的サブルーチンコールに関連しているかどうかを追跡するように構成されているフラグ設定論理回路
をさらに具備する、請求項14に記載の装置。
【請求項１７】
前記第1または第2の命令アドレスがサブルーチンへの明示的サブルーチンコールに関連することを示す前記プリデコード情報に応答して、前記第1および第2の命令アドレスに第2のオフセットを加える加算器の第2のセット
をさらに具備する請求項14に記載の装置。
【請求項１８】
前記一定数は8であり、および前記第2の一定数は４である、請求項17に記載の装置。
【請求項１９】
前記プリデコード情報は、前記第1または第2の命令アドレスがサブルーチンへの黙示的サブルーチンコールと関連するかどうかを示すビットの組み合わせとして符号化されている、請求項14に記載の装置。
【請求項２０】
前記第1または第2の結果のうちの1つから前記リターンアドレスを選ぶための前記手段は、
書き込みのために前記明示的サブルーチンリソースをイネーブルにするように構成されているセレクト／イネーブル論理回路
をさらに具備する請求項16に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本件発明は、一般にパイプラインプロセッサに関係し、特にパイプラインプロセッサの電力を軽減し、利用性を向上することを目的として、黙示的サブルーチンコール上の明示的サブルーチンコールの分岐予測動作をエミュレートする方法に関係する。
【背景技術】
【０００２】
マイクロプロセッサは、多種多様なアプリケーションにおいて計算タスクを実行する。ソフトウェアの変更によるオペレーションの高速化および／または機能性の向上を可能とするプロセッサのパフォーマンスの改善は、ほとんどつねに好ましいことである。携帯用電子機器のような多くのソフトウェア組み込み型アプリケーションにおいて、消費電力の節約も、プロセッサの設計および実装における重点目標の１つである。 
多くの現代型プロセッサは、パイプラインアーキテクチャを採用している。パイプラインアーキテクチャでは、プロセッサ全体の処理効率を上げるために、順次の命令が実行過程においてオーバーラップさせられる。パイプラインによるスムーズな実行処理を維持することは、高いパフォーマンスを達成する上で死活的に重要である。ほとんどの現代型プロセッサは、最近アクセスされたデータおよび命令のローカルコピーを記憶する高速のオンチップのキャッシュメモリを具備する階層メモリも利用している。
【０００３】
現実世界のプログラムは、間接分岐命令を含んでいるが、その命令の実際の分岐動作は、その命令が実行パイプラインにおいて現実に深く評価されるまでわからない。ほとんどの現代型プロセッサは、ある種の分岐予測を採用していて、そのことによって、間接分岐命令の分岐動作は、パイプライン処理の早い時点で（例えば、フェッチまたはデコードのパイプステージの際に）予測される。分岐予測技術を利用することによって、プロセッサは、間接分岐命令の分岐先を推論的にフェッチし、およびその推論的にフェッチされた命令の処理を始めるためにパイプライン処理をリダイレクトする。実際の分岐先が後のパイプライン処理（例えば、実行パイプステージ）で決定されたとき、もし分岐予測が誤っていたら、推論的にフェッチされた命令は、パイプラインからフラッシュされ、新しい命令が正しい分岐先アドレスからフェッチされなくてはならない。誤った分岐先の予測に応答して命令を事前フェッチすることは、プロセッサのパフォーマンスおよび消費電力に悪い影響をもたらす。
【０００４】
間接分岐命令の1つの例は、サブルーチンから戻るために利用される分岐命令を含んでいる。例えば、サブルーチンからのリターンコールは、リターンアドレスがレジスタの内容によって定義される分岐命令を含んでもよい。リターンアドレスとは、サブルーチンの終了後フェッチされるべき次の命令を定義するものであって、一般にはそのサブルーチンをもともとコールした分岐命令のあとの命令である。多くの高性能アーキテクチャは、サブルーチンのリターンの際の使用のために、特定の汎用目的レジスタ（GPE）を指定する。これは、一般にリンクレジスタと呼ばれている。
【０００５】
便宜上、リターンコールは、分岐リターン命令とも呼ばれる。プロセッサのパイプラインが分岐リターン命令のために分岐予測を利用することができるように、普通のソフトウェアは、リターンアドレスをリンクレジスタに記録するブランチアンドリンク命令（a branch and link instruction）のような明示的サブルーチンコールを含んでいる。多くの高性能実装は、ブランチアンドリンク命令を処理するデコードステージにおけるリンクスタック構造を含んでいる。リンクリターンの値は、対応するサブルーチンがリターンするとき正確な分岐予測を可能とするためにこのスタックの上にプッシュされる。普通のリンクスタック構造は、パイプラインを流れる複数のサブルーチンコールをサポートし、およびサブルーチンコールの複数のレベルのネスティング（入れ子構造化）をサポートするためにリターンアドレスのリストを含んでいる。その後、サブルーチン内の分岐リターン命令がデコードされているとき、他の分岐予測ハードウェアがプロセッサにパイプライン処理をリダイレクトすることを命じたら、リターンアドレスがリンクスタック構造から読み出されて分岐先アドレスを予測する分岐予測において利用される。もしその予測がパイプラインのリダイレクトを示したら、パイプラインは、リンクスタックから読み出されたリターンアドレスから命令をフェッチすることを開始する。
【０００６】
しかしながら、現在のレガシーソフトウェアの中には、サブルーチンをコールするとき普通のブランチアンドリンク命令を組み込んでおらず、それゆえリンクスタック構造を利用することができないものもある。実例として、ARM社の互換性プロセッサ上で動くコードセグメントを含む以下の表を参照せよ。
【表１】
2014002769.tif 000003
【０００７】
MOV LR, PCおよびBR命令の組み合わせは、プロセッサに後続のサブルーチンへの分岐のための準備をさせる。この例において、コールがなされる実際のサブルーチンは、アドレス0x00990000に始まる。MOV LR, PC命令は、プログラムカウンタ(PC)の内容がリンクレジスタ(LR)にコピーされなくてはならないことを示す。ARMのようないくつかの命令アーキテクチャにおいて、プログラムカウンタは、実際には現在の命令アドレス＋8バイトとして定義される。この定義を使用すると、PCの内容をLRに転送することは、リターンアドレス、アドレス0x00899908をリンクレジスタに記憶することに帰着する。リターンアドレスは、サブルーチンの終了時にリンクレジスタから検索される。より詳細には、BX LR、分岐リターン命令を実行するとき、リターンアドレスが検索される。
【０００８】
深いパイプラインを含み、分岐予測を利用する現代型プロセッサにおいて、分岐リターン命令をデコードするときリンクスタックを使用せずにリターンアドレスを予測することは、さまざまな理由から問題である。1つの理由は、マイクロアーキテクチャ規約に関係がある。この規約は、リンクレジスタのような汎用目的レジスタがパイプラインのデコードステージ中にアクセスされることを認めておらず、それゆえ分岐予測時にリンクレジスタの「現在の」値を使用してリターンアドレスを分岐予測することを排除する。たとえこの規約に変形をくわえることができるにせよ、今日の深いパイプラインは、リンクレジスタに含まれるデータを予測目的のためには信頼性の低いものにしてしまう可能性がある。例えば、分岐命令が、リターンアドレスのために予測が行われるデコードパイプステージから、リターンアドレスの実際の決定がなされる実行パイプステージまで流れるのに要する時間の最中に、後続の分岐命令が、パイプラインに入り、リンクレジスタを上書きし、その結果、最初の分岐リターン命令についてのリターンアドレスの実際の決定を予測リターンアドレスと異なるものにしてしまう可能性がある。予測値と実際の決定の間のこのミスマッチは、分岐先の誤予測と呼ばれる。分岐先の誤予測は、時間の損失と電力の損失に帰着する。いずれも、誤った予測パスを推論的に実行したことの結果である。
【０００９】
そのようなレガシーソフトウェアの広範な普及と、サブルーチンをコールするとき普通のブランチアンドリンク命令を利用するためにレガシーソフトウェアを書き換えることに付随するコストのゆえに、レガシーソフトウェアをサポートして、レガシーソフトウェアに分岐リターン命令がデコードパイプステージにあるときリターンアドレスを効果的に予測するためにリンクスタック構造を利用させるために、今日の発展させられたマイクロプロセッサに対するニーズがある。
【発明の概要】
【００１０】
本件開示は、サブルーチンへの黙示的サブルーチンコールを定義する命令パターンを認識し、この認識を利用することによって、分岐予測がサブルーチンのリターンアドレスを予測することを可能とすることを目的として明示的サブルーチンコールリソースを利用する方法および装置を工夫するものである。
【００１１】
1つの態様に準拠して、明示的サブルーチンの分岐予測動作をエミュレートする方法が示される。本方法は、サブルーチンへの黙示的サブルーチンコールを示す命令アドレスを認識すること、前記命令アドレスからリターンアドレスを計算すること、および前記リターンアドレスを明示的サブルーチンリソースに記憶することを含んでいる。
【００１２】
他の態様は、装置に関係する。本装置は、命令アドレスおよび第2の入力を受け取るように構成されている第1の入力を含んでいる。前記第2の入力は、サブルーチンへの黙示的サブルーチンコールに関連する命令アドレスを記述するプリデコード情報を受け取るように構成されている。前記プリデコード情報に応答して、本装置は、リターンアドレスを定義する前記命令アドレスにオフセットを加えるように構成されている加算器も含んでいる。加算器は、リターンコール命令の後続の分岐予測を容易にするために明示的サブルーチンリソースにリターンアドレスを記憶するようにも構成されている。
【００１３】
さらなる他の態様に準拠して、他の装置が示される。本装置は、第1および第2の命令アドレスならびに関連するプリデコード情報を受け取るように構成されている第1および第2の入力を具備している。本装置は、第1または第2の命令アドレスがサブルーチンへの黙示的サブルーチンコールに関連することを示すプリデコード情報に応答して、第1および第2の結果を定義する第1および第2の命令アドレスにオフセットを加えるように構成されている加算器の第1のセットをさらに具備している。本装置は、第1または第2の結果のうちの1つからリターンアドレスを選ぶための手段をさらに具備している。
【００１４】
本発明の他の実施形態は、以下の詳細な説明から当業者に容易に明白であろうということが了解される。なお、以下の説明において、本件発明のさまざまな実施形態は、例示のために示され、説明されるものである。あとで理解されるように、本発明は、他のおよび異なる実施形態のものもあり得、また本発明のいくつかの詳細は、本発明から逸脱することなく、さまざまな他の態様に修正することも可能である。したがって、図面および詳細な記述は、限定的なものとしてではなく、本質的に例示的なものとしてみなされるべきである。
【図面の簡単な説明】
【００１５】
【図１】図1は、プロセッサの機能ブロック図である。
【図２】図2は、図1に例示されているパイプラインによる命令のフローの結果として起こるタイミング図である。
【図３】図3は、単一命令デコードパイプステージの例示的部分である。
【図４】図4は、2命令デコードパイプステージの部分の例示的な第1の態様である。
【図５】図5は、2命令デコードパイプステージの部分の例示的な第2の態様である。
【図６】図6は、黙示的サブルーチンコールを認識するとき明示的サブルーチンの分岐予測動作をエミュレートする方法を例示するフローチャートである。
【図７】図7は、図6におけるブロック610、620および630のさらなる詳細を示すフローチャートである。
【発明を実施するための形態】
【００１６】
図1は、本発明の態様が採用されることができるプロセッサ100の機能ブロック図である。プロセッサ100は、最近処理された命令をキャッシュする命令キャッシュ(I-キャッシュ)110、I-キャッシュに命令がないときメモリ138にアクセスするメモリインタフェース136、メモリ138から検索される１つの命令の限定的デコードを実行するプリデコード論理回路128、およびI-キャッシュ110におけるミスに応答してI-キャッシュ110にプリデコードビットを含む命令データを書き込むフィルバッファ130を含んでいる。プリデコードビットは、メモリから検索される命令に関連し、例えば命令タイプの表示のような命令を記述する属性を含んでいる。メモリ138は、プロセッサ100の上またはその外に置かれてもよく、またレイヤー２(L2)メモリコンポーネントを具備するものであってもよい。
【００１７】
プロセッサ100は、命令を処理する命令パイプライン105、および間接分岐命令についての分岐先アドレスを予測し、かつ当該分岐先アドレスを処理するために命令パイプライン105をリダイレクトするべきかどうかを予測する分岐予測回路132も含んでいる。分岐予測回路132が命令パイプライン105をリダイレクトするべきと予測する場合、間接分岐命令は、「分岐すると予測される」（"predicted taken"）といわれる。間接分岐命令が「分岐すると予測される」場合、分岐予測回路132は、間接分岐命令の分岐先アドレスを予測し、および命令パイプライン105をリダイレクトしてその分岐先アドレスに始まる命令のフェッチを開始する。
【００１８】
プロセッサ100は、コントロール論理回路122にしたがって命令パイプライン105内の命令を処理する。いくつかの実施形態において、パイプライン105は、2つ以上の並列パイプラインを有するスーパースケーラ設計であってもよい。パイプライン105は、次のようなさまざまなパイプステージを含んでいる：命令キャッシュルックアップ(IC)ステージ102、命令データアラインメント(IDA)ステージ104、デコード(DCD)ステージ106、命令キュー(IQ)ステージ108、第1レジスタアクセス(RACC1)ステージ112、第2レジスタアクセス(RACC2)ステージ114、予約ステーション(RSV)ステージ116、および4つの実行ステージ(X1-X4)120A-120D。いくつかの実施形態では、パイプステージは、一度に１つの命令を処理してもよい。他の実施形態では、パイプステージは、同時に2つ以上の命令を処理してもよい。パイプステージの数は、本件開示の範囲を制限することなく、パイプライン105に比べて加算または減算されてもよいことに留意すべきである。プロセッサ100は、マイクロアーキテクチャ規約によりパイプステージ112、114および120A-120Dによってアクセス可能なレジスタを含む汎用目的レジスタ(GPR)ファイル118も含んでいる。
【００１９】
命令キャッシュルックアップ(IC)ステージ102は、I-キャッシュ110からの命令検索を試みる。命令データアラインメントステージ104は、マルチプル命令およびマルチプル命令に関連するプリデコード情報を構文解析する。I-キャッシュ110内に命令アドレスが見つからない場合、命令データアラインメントステージ104は、対応する命令をメモリ138から検索するリクエストを開始する。デコードステージ106は、命令を完全にデコードする。さらに普通の機能にくわえて、デコードステージ106は、明示的サブルーチンコール命令を認識し、リンクスタック構造134の中にリターンアドレスを書き込む。さらにデコードステージ106は、レガシーソフトウェアからの黙示的サブルーチンコールも認識し、リターンアドレスをリンクスタック構造134の中に記憶する。リンクスタック構造134は、巡回バッファとして管理されるレジスタのセットであってもよい。リターンアドレスは、黙示的サブルーチンの終了時にパイプライン105がリダイレクトされるべき命令のアドレスである。デコードステージ106の適切な態様の構造およびオペレーションは、図3-5の議論に関してもっと十分に説明されるだろう。
【００２０】
命令キューステージ108は、推論的フェッチングが実行パイプラインのストール（stalls）の間ずっと続くことが可能となるように1つまたは複数の命令をバッファする。第1および第2のレジスタアクセスステージ112および114は、命令によって必要とされる場合、汎用目的レジスタ118から1つまたは複数のオペランドを検索する。予約ステーションステージ116は、命令がRAW(read-after-write)ハザードおよび同様の解決すべき事項を待ち受けることを可能にする。実行ステージは、算術論理演算ユニットなどのような既知のコンポーネントを含んでいる。実行ステージ120A-120Dは、命令を実行する。実行ステージから生じた結果は、GPRファイル118に書き込まれる。実行ステージ120A-120Dの間に、実際の分岐が決まり、デコードステージ106の間になされた分岐予測が正しいかどうかを決定する。実際の分岐決定が予測された宛て先と異なる場合、分岐は誤予測されたといわれる。
【００２１】
当業者は、プロセッサ100の多数の変形が可能であることを認識するだろう。例えば、プロセッサ100は、I-キャッシュ110のために第2レベル(L2)のキャッシュを含んでもよい。さらに、プロセッサ100に描かれた機能ブロックの1つまたは複数は、特定の実施形態から省略されてもよい。プロセッサ内に存在するかもしれない他の機能ブロック、例えばトランスレーション・ルックアサイド・バッファ、データキャッシュ等々は、本発明の説明に密接な関係がなく、明瞭さのために省略されている。
【００２２】
図2は、図1に例示されたパイプライン105による命令のフローの結果として起きるタイミング図200である。特に、タイミング図200にトレースされている命令フローは、表1に例示されているようなレガシーコードセグメントである。本件開示の目的のために、「黙示的サブルーチンコール」という用語は、2つ以上の命令の組み合わせであって、その組み合わせによる機能がレジスタにサブルーチンコールのための準備をさせることおよびサブルーチンをコールすることである組み合わせをさすものとする。例えば、表1を参照し、MOV LR, PCおよびBRの組み合わせにおける2つの命令は、黙示的サブルーチンコールを定義する。この場合、MOV LR, PC命令は、黙示的サブルーチンコールの開始を定義し、BR命令は、黙示的サブルーチンコールの終了を定義する。
【００２３】
タイミング図200の最初の11行は、パイプライン105のステージに対応する。列210A-210Wは、順次のタイミングサイクルに対応する。説明の目的のために、各パイプステージは、1サイクルごとに1命令を処理するものとする。しかしながら、本件開示の教示は複数のサイクルのパイプステージにも、また1サイクルごとに複数の命令を処理できるパイプステージにも、適用可能であることが当業者に認識されるべきである。
【００２４】
タイミング図200の行211は、図3および4に示されるデコードパイプステージの態様の結果としてのリンクスタック構造314のようなリンクスタック構造の内容に対応する。タイミング図200の行213は、図5に示されるデコードパイプステージの態様の結果としてのリンクスタック構造の内容に対応する。行213は、図5の議論に関してあとで論じる。タイミング図200の行212は、リンクレジスタの内容に対応する。
【００２５】
一般に、命令はICステージ102に入り、次のサイクルに次のステージに伝播する。215において、MOV LR, PC命令は、デコードステージ106にある。その時点において、デコードステージ106は、MOV LR, PCを認識し、リターンアドレス、MOV+8をリンクスタック構造の中に記憶する。記法上、MOV+8は、MOV命令のアドレスに8のオフセットを加えることをいうものとする。リンクスタック構造がBR命令に続く順次の命令のアドレスを含むことになるように、値8は、MOV命令の４バイトおよび後続のBR命令の４バイトを含んでいる。さらに、図3および４の議論に関して議論されるように、本開示の本件教示に準拠するデコードステージは、MOV命令のアドレスに8のオフセットを加える。さらに、図5の議論に関して議論されるように、本開示の本件教示に準拠する代替的デコードステージは、BR命令のアドレスに4のオフセットを加える。記法MOV+8およびBR+4の両方がアドレス0x00899908、リターンアドレスをさすことに留意すべきである。参照220において、リンクスタック構造は、その内容がMOV+8であることを示している。BR命令がデコードステージ106によって処理されるとき、分岐命令の分岐先、サブルーチンの開始が、次のサイクルにパイプラインによって予測され、フェッチされる。参照219において、LDA命令、サブルーチンの開始が、ICステージ102によって処理される。分岐命令の予測によりパイプライン105がLDA命令をフェッチするためにリダイレクトされているので、アドレスBR+4およびBR+8における命令は、パイプラインからフラッシュされる。LDA命令のあとに続く命令は、次にパイプライン105の中にフェッチされる。
【００２６】
参照225において、分岐リターン命令、BXがデコードステージ106によって処理される。デコードステージ106は、リターンアドレスの予測のために、リンクスタック構造の内容で分岐予測回路132を起動する。他の実施形態において、分岐予測回路132は、リンクスタック構造を読む。いずれの場合も、分岐予測回路132は、リターンアドレスの予測のために、リンクスタック構造を利用し、また、参照230において、パイプラインは、リターンアドレス0x00899908における命令をフェッチするようにリダイレクトされる。行211列210JのMOV+8記載項目は、いったん利用されると、リンクスタック構造から除去される。
【００２７】
黙示的サブルーチンコールのためにリンクスタックを使用しない普通のプロセッサでは、サブルーチンリターン命令がDCDステージにあって予測を試みているとき、リンクレジスタ（LR）それ自体の値は、サイクル210Iにおいて使用されるように事前に更新されてはいない可能性がある。図において示されるように、LRはサイクル210Mまで更新されない。それは、DCDステージにおいてこの値を使用するために必要とされるはずのものより4サイクル遅れている。参照235におけるサイクル210M は、分岐リターンアドレスの予測とフェッチが行われるサイクル210Iのあとである。したがって、普通のプロセッサでは、リンクレジスタに記憶された分岐リターン命令についての分岐予測は、信頼性が低い可能性がある。
【００２８】
図3ないし5は、デコードパイプステージ106のようなデコードパイプステージと関係する本発明の代替的態様を例示している。これらの代替的態様は、黙示的サブルーチンコールおよび普通のブランチアンドリンク命令の双方についてリンクステータス構造に書き込むためのパスをアドレスする。その他のパス、例えば命令セットにおける他の命令のパスがデコードパイプステージに含まれるが、本件発明のこの態様とは係わりがないので、図面には描かれていないということに留意すべきである。
【００２９】
図3は、単一命令のデコードパイプステージの例示的な部分300である。単一命令のデコードパイプステージの部分300は、デコードステージ106の中に適切に配置されることができる。単一の命令デコードパイプステージの部分300は、命令アドレス310および命令アドレス310に関連するプリデコードビット315を含んでいる。命令アドレス310のサイズは長さ32ビット、プリデコードビット315のサイズは長さ8ビットである。本件開示の態様はさまざまなサイズの命令アドレスまたはプリデコードビットおよび両者のそれぞれのビット位置を企図するものであることに留意すべきである。命令アドレス310およびプリデコードビット315は、デコードパイプステージの部分300への入力であり、同一のデータレジスタまたは異なるデータレジスタに存在してもよい。
【００３０】
プリデコードビット315は、命令アドレス310に対応する命令に関係する情報を含んでおり、プリデコード論理回路128によって決定される。プリデコードビット315は、対応する命令が、表1にリストされているMOVおよびBRの組み合わせにおけるMOV LR, PCのような黙示的サブルーチンコールの開始であるかどうかを示す。プリデコードビット315は、さまざまなやりかたで符号化されることができる。そのやりかたには、命令アドレス310が黙示的サブルーチンコールの開始または普通のブランチアンドリンク命令のいずれかをさすことを示すためにプリデコードビット315の組み合わせまたは特定のビットを符号化することも含まれる。他の実施形態において、黙示的サブルーチンコールおよび普通のブランチアンドリンク命令を命令セットにおける他の命令と区別するために、命令の演算コード(opcode)が利用されてもよい。
【００３１】
デコードパイプステージの部分300は、加算器/多重化器の組み合わせ330をさらに含んでいる。加算器/多重化器の組み合わせ330は、加算器325A-325B、多重化器320およびリンクスタック構造134を含んでいる。加算器325Aは、命令アドレス310が普通のブランチアンドリンク命令をさす場合、命令アドレスに定数4を加える。加算器325Bは、命令アドレス310が黙示的サブルーチンコールの開始をさす場合、命令アドレスに定数8を加える。多重化器320を通じて、プリデコードビット315は、インクリメントされたアドレスまたはリターンアドレスのどれか（もしあれば）リンクスタック構造314に書き込まれるものを選択する。表1を参照し、8のオフセットは、リターンアドレスの位置がMOV命令の8バイトあとであることを反映するために例示されている。普通のブランチアンドリンク命令において、リターンアドレスは、ブランチアンドリンク命令の4バイトあとである。図には示されていないが、黙示的サブルーチンコールを構成する命令の数、および黙示的サブルーチンコールを構成する命令の各々のサイズに依存して、他の加算器が追加されてもよく、または図3ないし5において例示されている加算器に取って換わってもよい。
【００３２】
図4は、2命令デコードパイプステージの部分400の例示的な第1の態様である。2命令デコードパイプステージの部分400は、デコードステージ106の中に適切に配置されてもよい。2命令デコードパイプステージの部分400は、命令アドレスに対応するプリデコードビット407A-Bと同時に受信される 2つの命令アドレス410A-410B、および2セットの加算器/多重化器の組み合わせ425A-425Bを含んでいる。
【００３３】
命令アドレス410A-410Bおよびプリデコードビット407A-Bは、デコードパイプステージの部分400への入力であって、同一のデータレジスタまたは異なるデータレジスタの中に存在してもよい。
【００３４】
MOV LR, PC命令についてのアドレスのような黙示的サブルーチンコールの開始は、命令アドレス410Aまたは410Bのいずれかの中に見出されることができる。規約により、命令アドレス410AまたはDCD0は、プログラム順で1番目であって、命令アドレス410BまたはDCD1は、プログラム順で2番目である。MOV LR, PC命令のアドレスのような黙示的サブルーチンの開始を定義する命令のアドレスが命令アドレス410Aに置かれるとき、加算器/多重化器425Aの出力が有効であって、このインクリメントされたアドレスは、リンクスタック構造134に書き込まれる。もし黙示的サブルーチンの開始のためのアドレスが命令アドレス410Bであれば、加算器/多重化器425Bの出力が有効であって、このインクリメントされたアドレスまたはリターンアドレスは、リンクスタック構造134に書き込まれる。黙示的サブルーチンが認識されると、図3および4に例示されているデコードパイプステージの態様は、黙示的サブルーチンを定義する始まりの命令のときにリンクスタック構造134に書き込みをする。
【００３５】
図5は、2命令デコードパイプステージの部分500の例示的な第2の態様である。2命令デコードパイプステージの部分500は、デコードステージ106の中に適切に配置されてもよい。2命令デコードパイプステージの部分500は、黙示的サブルーチンコールを定義する最後の命令アドレスを受け取ることに応答して、リンクスタック構造134にリターンアドレスを書き込む。例えば、再び図2を参照し、リンクステータス構造213は、MOVおよびBRの組み合わせの分岐命令のデコードの1サイクル後に、2命令デコードパイプステージの部分500によって参照221において書き込まれる。結果的に、例示のように、BR+4の値は、参照221においてリンクステータス構造213に書き込まれる。
【００３６】
2命令デコードパイプステージの部分500は、2つの命令アドレス510A-510Bを含んでいる。これら２つの命令アドレスは、それぞれのプリデコードビット507A-Bと同時に受け取られる。命令アドレス510A-510B(DCD0およびDCD1)およびそれぞれのプリデコードビット507A-B(PDCD0およびPDCD1)は、デコードパイプステージの部分500への入力であって、同一のデータレジスタまたは異なるデータレジスタに存在してもよい。
【００３７】
デコードパイプステージの部分500は、セレクト/イネーブル論理回路510、フラグ設定論理回路515、加算器525Aおよび525B、および多重化器520を含んでいる。フラグ設定論理回路515は、フラグ530をセットおよびリセットする。フラグ530は、黙示的サブルーチンコールの開始がアドレス510Aまたはアドレス510Bのいずれかの中で認識されたかどうかを追跡する。黙示的サブルーチンコールの開始および終了を示すアドレスの両方が同時に受け取られる場合、フラグ530は利用されない。MOV LR, PCおよびBRの組み合わせによって定義される黙示的サブルーチンの場合、PDCD0およびPDCD1ビットを利用するフラグ設定論理回路515は、命令MOV LR, PCのアドレスが最終の有効デコードスロットに存在するとき、フラグ530をセットする。前記最終の有効デコードスロットは、DCD0(DCD1が無効のとき)またはDCD1のいずれかであることができる。
【００３８】
セレクト/イネーブル論理回路510は、DCD0またはDCD1が黙示的サブルーチンコールの終了のアドレスを含むかどうか決定する。黙示的サブルーチンコールの終了がDCD0内にある場合、加算器525Aは、黙示的サブルーチンコールのためのリターンアドレスを計算するためにDCD0内のアドレスに4を加える。黙示的サブルーチンコールの終了がDCD1内にある場合、加算器525Bは、リターンアドレスを計算するためにDCD1内のアドレスに4を加える。セレクト/イネーブル論理回路510は、もし黙示的サブルーチンコールの終了がDCD0またはDCD1の中にあれば、セレクト信号540を生成し、および、もしそうであれば、インクリメントされた命令アドレス535Aまたは535Bのいずれかリンクスタック構造134に書き込まれるべきほうを選択する。
【００３９】
リンクスタック構造134がムダに書き込まれないことを保証するために、セレクト/イネーブル論理回路510は、入力として、命令アドレスDCD0およびDCD1にそれぞれ対応する分岐予測信号550Aおよび550Bを分岐予測回路132から受け取る。黙示的サブルーチンコールがデータレジスタ505において認識され、および黙示的サブルーチンが分岐予測回路132によって分岐すると予測される場合、セレクト/イネーブル論理回路510は、リンクスタック構造を書き込み可能とするために、リンクスタック構造134への書き込みイネーブル信号545を生成する。黙示的サブルーチンコールが認識されても、分岐すると予測されない場合、セレクト/イネーブル論理回路510は、リンクスタック構造134への書き込みイネーブルを生成しない。このようにして、分岐しないと予測される黙示的サブルーチンコールは、リンクスタック構造134への書き込みに至らない。本件開示は、黙示的サブルーチンコールの認識、およびデコードステージパイプライン中のリンクスタック構造への書き込みについて説明するものであるが、本発明のこれらの態様は、プリデコードビットが決定されて分岐予測がなされるプロセッサパイプラインの任意のステージにおいて実行可能であることが当業者に認識されるであろうということが留意されるべきである。
【００４０】
図6は、黙示的サブルーチンコールを認識するとき明示的サブルーチンの分岐予測動作をエミュレートする方法600を例示するフローチャートである。ブロック610において、サブルーチンへの黙示的サブルーチンコールを示す命令アドレスがプロセッサパイプラインの中で認識される。ブロック620において、命令アドレスからリターンアドレスが計算される。黙示的サブルーチンコールが2つ以上の命令を含む場合、命令アドレスに加えられるオフセットの量は、さまざまなファクタに依存する。そのファクタには、前記認識が黙示的サブルーチンコールの開始または終了時になされるかどうか、および黙示的サブルーチンコールを構成する命令のサイズが含まれる。ブロック630において、リターンアドレスは、リンクスタック構造134のような明示的サブルーチンリソースに記憶される。図3ないし5において説明したように、3-5、ブロック610、620および630は、デコードステージ106の間に生起してもよい。
【００４１】
ブロック640において、プロセッサパイプラインは、コールされたサブルーチンに関連する命令を処理する。例えば、表1を参照し、ブロック640において、命令アドレス0x00990000-0x00990008が処理される。ブロック650において、表1中の0x00990008 BXのようなサブルーチンからのリターンコールを示す分岐命令に応答して、明示的サブルーチンリソースからリターンアドレスが読み出される。さらに、ブロック650において、プロセッサパイプラインは、明示的サブルーチンリソースから読み出されたリターンアドレスにリダイレクトされる。リターンコール命令がデコードステージ106にある間に、リターンアドレスがリンクスタック構造134から検索される。その方法は、普通のブランチアンドリンク命令によってコールされるサブルーチンのためのリターンコールに応答してリターンコールが検索されるときの方法と同じである。いったんリターンアドレスが検索されてリターンコール命令が分岐すると予測されると、リターンアドレスは、プロセッサパイプラインによってフェッチされる。このことは、図2に例示されるようなリターンアドレスのより早いフェッチを都合よく可能にする。
【００４２】
図7は、図6中のブロック610、620および630のさらなる詳細を示すフローチャート700である。ブロック710において、命令アドレスに関連するプリデコードビットが読まれる。ブロック720において、フローチャート700は、プリデコードビットが黙示的サブルーチンコールを示すかどうかを決定する。もしそうであれば、ブロック730は、命令アドレスにオフセットを加える。ブロック740において、インクリメントされたアドレスは、リンクスタック構造に記憶される。ブロック750において、パイプラインプロセスは、普通の方法で命令の処理を続ける。プリデコードビットが黙示的サブルーチンコールを示さない場合、ブロック720は、ブロック750に進み、プロセッサパイプラインは、普通の方法で命令の処理を続ける。
【００４３】
本件明細書において開示された実施形態に関連して説明されたさまざまな例示的論理ブロック、モジュール、回路、素子、および／またはコンポーネントは、汎用目的プロセッサ、デジタル信号プロセサ(DSP)、特定用途向けIC(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)または他のプログラマブル論理コンポーネント、ディスクリートゲートまたはトランジスタ論理、ディスクリートハードウェアコンポーネント、またはこれらのものの組み合わせであって、本件明細書において説明された機能を実行するように設計されたものによって実装または実行されてもよい。汎用目的プロセッサは、マイクロプロセッサであってもよいが、代替的に、当該プロセッサは、任意の普通のプロセッサ、コントローラ、マイクロコントローラまたは状態機械であってもよい。プロセッサはまた、計算コンポーネントの組み合わせ、例えばDSPとマイクロプロセッサの組み合わせ、複数のマイクロプロセッサ、DSPコアと協働する1または複数のマイクロプロセッサまたは他の任意のそのような構成として実装されてもよい。
【００４４】
本件明細書において開示された実施形態に関連して説明された方法は、ハードウェア、プロセッサによって実行されるソフトウェアモジュール、または両者の組み合わせにおいて直接的に具体化されてもよい。ソフトウェアモジュールは、RAMメモリ、フラッシュメモリ、ROMメモリ、EPROMメモリ、EEPROMメモリ、レジスタ、ハードディスク、リムーバブルディスク、CD-ROMまたは本件分野において既知の他の任意の形式の記憶媒体に存在してもよい。記憶媒体は、プロセッサが当該記憶媒体に対する情報の読み出しおよび書き込みを行うことができるようにプロセッサに連結されてもよい。代替的に、記憶媒体は、プロセッサと一体化されてもよい。
【００４５】
本件発明は実施形態の文脈で開示されているものの、上記の議論および下に続く請求項と一致する多種多様の実装が当業者によって採択可能であることが認識されるであろう。
【図１】
2014002769.tif 000004
【図２】
2014002769.tif 000005
【図３】
2014002769.tif 000006
【図４】
2014002769.tif 000007
【図５】
2014002769.tif 000008
【図６】
2014002769.tif 000009
【図７】
2014002769.tif 000010
【手続補正書】
【提出日】平成25年9月2日(2013.9.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１および第２の命令アドレスおよび関連するプリデコード情報を同時に受け取るように構成されている第１および第２の入力、
前記第１または第２の命令アドレスがサブルーチンへの黙示的サブルーチンコールに関連していることを示す前記プリデコード情報に応答して、第１および第２の結果を定義する前記第１および第２の命令アドレスにオフセットを加えるように構成されている加算器の第１のセット、および
前記第１および第２の結果のうちの１つからリターンアドレスを選ぶための手段
を具備する装置。
【請求項２】
明示的サブルーチンリソースに前記リターンアドレスを書き込むための手段
をさらに具備する、請求項１に記載の装置。
【請求項３】
前記第１または第２の結果のうちの１つから前記リターンアドレスを選ぶための前記手段は、
書き込みのために前記明示的サブルーチンリソースをイネーブルにするように構成されているセレクト／イネーブル論理回路
をさらに具備する請求項２に記載の装置。
【請求項４】
前記第１または第２の命令アドレスが前記黙示的サブルーチンコールに関連しているかどうかを追跡するように構成されているフラグ設定論理回路
をさらに具備する、請求項１に記載の装置。
【請求項５】
前記第１または第２の命令アドレスがサブルーチンへの明示的サブルーチンコールに関連することを示す前記プリデコード情報に応答して、前記第１および第２の命令アドレスに第２のオフセットを加える加算器の第２のセット
をさらに具備する請求項１に記載の装置。
【請求項６】
前記プリデコード情報は、前記第１または第２の命令アドレスが前記サブルーチンへの前記黙示的サブルーチンコールと関連するかどうかを示すビットの組み合わせとして符号化されている、請求項１に記載の装置。
【請求項７】
命令アドレスを受け取るように構成されている第１の入力、
プリデコード情報を受け取るように構成されている第２の入力、ここにおいて、前記プリデコード情報は、サブルーチンへの黙示的サブルーチンコールに関連するものとして前記命令アドレスを記述するものである、
前記プリデコード情報に応答して、リターンアドレスを定義する前記命令アドレスにオフセットを加え、その結果前記リターンアドレスが明示的サブルーチンリソースに記憶されるようにするように構成されている加算器、
前記命令アドレスとともに第２の命令アドレスを同時に受け取る第３の入力、および
前記命令アドレスまたは前記第２の命令アドレスを前記明示的サブルーチンリソースに送るべきかどうか決定するように構成されている論理
を具備する装置。
【請求項８】
明示的サブルーチンコールに応答して、前記命令アドレスに第２の一定数のオフセットを加えるように構成されている第２の加算器
をさらに具備する、請求項７に記載の装置。
【請求項９】
前記明示的サブルーチンリソースは、前記サブルーチンからのリターンコールを示す分岐命令に応答して読まれる、請求項７に記載の装置。
【請求項１０】
前記プリデコード情報は、前記黙示的サブルーチンコールの開始として前記命令アドレスをさらに記述する、請求項７に記載の装置。
【請求項１１】
前記プリデコード情報は、前記黙示的サブルーチンコールの終了として前記命令アドレスをさらに記述する、請求項７に記載の装置。
【請求項１２】
前記明示的サブルーチンリソースは、リンクスタック構造である、請求項７に記載の装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００４５
【補正方法】変更
【補正の内容】
【００４５】
本件発明は実施形態の文脈で開示されているものの、上記の議論および下に続く請求項と一致する多種多様の実装が当業者によって採択可能であることが認識されるであろう。
以下に、本願出願の当初の特許請求の範囲に記載された発明を付記する。
［Ｃ１］
明示的サブルーチンコールの分岐予測動作をエミュレートする方法であって、
サブルーチンへの黙示的サブルーチンコールを示す命令アドレスを認識すること、
前記命令アドレスからリターンアドレスを計算すること、および
前記リターンアドレスを明示的サブルーチンリソースに記憶すること
を具備する方法。
［Ｃ２］
前記サブルーチンからのリターンコールを示す分岐命令に応答して、前記明示的サブルーチンリソースから前記リターンアドレスを読み出すこと
をさらに具備する、Ｃ１に記載の方法。
［Ｃ３］
プロセッサパイプラインを前記リターンアドレスにリダイレクトすること
をさらに具備する、Ｃ２に記載の方法。
［Ｃ４］
前記命令アドレスを認識することは、
プリデコード情報を定義する前記命令アドレスに関連する前記命令をプリデコードすること、および
プリデコード情報が前記黙示的サブルーチンコールの開始として前記命令アドレスを示しているかどうか決定すること
をさらに具備する、Ｃ１に記載の方法。
［Ｃ５］
前記命令アドレスから前記リターンアドレスを計算することは、
前記命令アドレスに一定数のオフセットを加えること
を具備する、Ｃ１に記載の方法。
［Ｃ６］
前記明示的サブルーチンリソースは、リンクスタック構造である、Ｃ１に記載の方法。
［Ｃ７］
命令アドレスを受け取るように構成されている第１の入力、
プリデコード情報を受け取るように構成されている第２の入力、ここにおいて、前記プリデコード情報は、サブルーチンへの黙示的サブルーチンコールに関連するものとして前記命令アドレスを記述するものである、および
前記プリデコード情報に応答して、リターンアドレスを定義する前記命令アドレスにオフセットを加え、その結果前記リターンアドレスが明示的サブルーチンリソースに記憶されるようにするように構成されている加算器
を具備する装置。
［Ｃ８］
前記明示的サブルーチンリソースは、前記サブルーチンからのリターンコールを示す分岐命令に応答して読まれる、Ｃ７に記載の装置。
［Ｃ９］
前記プリデコード情報は、前記黙示的サブルーチンコールの開始として前記命令アドレスをさらに記述する、Ｃ７に記載の装置。
［Ｃ１０］
前記プリデコード情報は、前記黙示的サブルーチンコールの終了として前記命令アドレスをさらに記述する、Ｃ７に記載の装置。
［Ｃ１１］
前記明示的サブルーチンリソースは、リンクスタック構造である、Ｃ７に記載の装置。
［Ｃ１２］
前記命令アドレスとともに第２の命令アドレスを同時に受け取る第３の入力、および
前記命令アドレスまたは前記第２の命令アドレスを前記明示的サブルーチンリソースに送るべきかどうか決定するように構成されている論理
をさらに具備する、Ｃ７に記載の装置。
［Ｃ１３］
明示的サブルーチンコールに応答して、前記命令アドレスに第２の一定数のオフセットを加えるように構成されている第２の加算器
をさらに具備する、Ｃ７に記載の装置。
［Ｃ１４］
第１および第２の命令アドレスおよび関連するプリデコード情報を同時に受け取るように構成されている第１および第２の入力、
前記第１または第２の命令アドレスがサブルーチンへの黙示的サブルーチンコールに関連していることを示す前記プリデコード情報に応答して、第１および第２の結果を定義する前記第１および第２の命令アドレスに一定のオフセットを加えるように構成されている加算器の第１のセット、および
前記第１および第２の結果のうちの１つからリターンアドレスを選ぶための手段
を具備する装置。
［Ｃ１５］
明示的サブルーチンリソースに前記リターンアドレスを書き込むための手段
をさらに具備する、Ｃ１４に記載の装置。
［Ｃ１６］
前記第１または第２の命令アドレスが前記黙示的サブルーチンコールに関連しているかどうかを追跡するように構成されているフラグ設定論理回路
をさらに具備する、Ｃ１４に記載の装置。
［Ｃ１７］
前記第１または第２の命令アドレスがサブルーチンへの明示的サブルーチンコールに関連することを示す前記プリデコード情報に応答して、前記第１および第２の命令アドレスに第２のオフセットを加える加算器の第２のセット
をさらに具備するＣ１４に記載の装置。
［Ｃ１８］
前記一定数は８であり、および前記第２の一定数は４である、Ｃ１７に記載の装置。
［Ｃ１９］
前記プリデコード情報は、前記第１または第２の命令アドレスがサブルーチンへの黙示的サブルーチンコールと関連するかどうかを示すビットの組み合わせとして符号化されている、Ｃ１４に記載の装置。
［Ｃ２０］
前記第１または第２の結果のうちの１つから前記リターンアドレスを選ぶための前記手段は、
書き込みのために前記明示的サブルーチンリソースをイネーブルにするように構成されているセレクト／イネーブル論理回路
をさらに具備するＣ１６に記載の装置。
【外国語明細書】
2014002769000001.pdf