(57)【特許請求の範囲】
【請求項１】
コンピュータ処理システムにおいてスタック場所に対するメモリ参照をリネームする方法であって、
アーキテクチャ的に定義されたスタック・アクセス方法を使用するスタック参照を検出するステップと、
前記スタック参照をプロセッサ内部レジスタに対する参照に置き換えるステップとを含む方法。
【請求項２】
前記プロセッサ内部レジスタと前記コンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップをさらに含む、請求項１に記載の方法。
【請求項３】
前記同期化ステップが、書込みスタック参照であるすべてのスタック参照のためのイン・オーダ書込み動作を挿入するステップを含む、請求項２に記載の方法。
【請求項４】
アーキテクチャ的に定義されたスタック・アクセス方法を使用しないスタック参照のための整合性維持動作を実行するステップをさらに含む、請求項１に記載の方法。
【請求項５】
整合性維持動作を実行する前記ステップが、値を、所与のプロセッサ内部レジスタから、スタック領域を参照しアーキテクチャ的に定義されたスタック・アクセス方法を使用しないロード動作に、バイパスするステップを含む、請求項４に記載の方法。
【請求項６】
前記プロセッサ内部レジスタと前記コンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップをさらに含み、整合性維持動作を実行する前記ステップが、前記同期化ステップの実行時に前記スタック参照のためのイン・オーダ値を前記メイン・メモリから回復するステップを含む、請求項４に記載の方法。
【請求項７】
前記スタック参照が書込みスタック参照である場合、前記イン・オーダ値が、前記スタック参照に対応する命令を含む命令ストリームに挿入されたイン・オーダ書込み動作によって、前記メイン・メモリに書き込まれる、請求項６に記載の方法。
【請求項８】
アーキテクチャ的に定義された前記スタック・アクセス方法を使用しないロード動作に応答して、前記イン・オーダ値を前記メイン・メモリに書き込むステップをさらに含む、請求項６に記載の方法。
【請求項９】
整合性維持動作を実行する前記ステップが、
前記システムのプロセッサのすべてのアウト・オブ・オーダ状態を廃棄するステップと、
前記プロセッサ内部レジスタと前記コンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップと、
アーキテクチャ的に定義された前記スタック・アクセス方法を使用しないストア動作が行われた後に実行を再開するステップとを含む、請求項４に記載の方法。
【請求項１０】
アーキテクチャ的に定義された前記スタック・アクセス方法が、スタック・ポインタとフレーム・ポインタと引数ポインタとのうちの少なくとも１つを使用するメモリ・アクセスを含む、請求項１に記載の方法。
【請求項１１】
アーキテクチャ的に定義されたスタック・アクセス方法が、プッシュ、ポップ、およびその他のスタック操作動作を含む、請求項１に記載の方法。
【請求項１２】
コンピュータ処理システムにおいてスタック場所に対するメモリ参照をリネームする方法であって、
ロード命令が、スタック場所にアクセスするためにアーキテクチャ的に定義されたレジスタを使用してローカル・スタック内の場所を参照するか否かを判断するステップと、
前記ロード命令がアーキテクチャ的に定義された前記レジスタを使用して前記場所を参照する場合、前記ローカル・スタック内の前記参照された場所のためのリネーム・レジスタが存在するか否かを判断するステップと、
前記リネーム・レジスタが存在する場合、前記場所に対する前記参照を前記リネーム・レジスタに対する参照に置き換えるステップとを含む方法。
【請求項１３】
アーキテクチャ的に定義された前記レジスタがスタック場所にアクセスするためのポインタに対応する、請求項１２に記載の方法。
【請求項１４】
前記スタック場所にアクセスするための前記ポインタが、スタック・ポインタとフレーム・ポインタと引数ポインタとのうちの１つである、請求項１３に記載の方法。
【請求項１５】
アーキテクチャ的に定義された前記スタック・アクセス方法が、プッシュ、ポップ、およびその他のスタック操作動作を含む、請求項１２に記載の方法。
【請求項１６】
前記リネーム・レジスタが存在するか否かを判断する前記ステップが、前記場所のシンボリック・アドレスと実アドレスとのうちの１つを計算するステップを含む、請求項１２に記載の方法。
【請求項１７】
前記リネーム・レジスタが存在するか否かを判断する前記ステップが、デコード段階、アドレス生成段階、およびメモリ・アクセス段階のうちの１つの段階で行われる、請求項１２に記載の方法。
【請求項１８】
前記リネーム・レジスタが存在しない場合、前記システムのメイン・メモリとキャッシュとのうちの１つから前記ロード命令を行うステップをさらに含む、請求項１２に記載の方法。
【請求項１９】
前記ロード命令がアーキテクチャ的に定義された前記レジスタを使用して前記場所を参照しない場合、前記ロード命令が、他のレジスタを使用してローカル・スタックを含むいずれかのスタック内の場所を参照するか否かを判断するステップをさらに含む、請求項１２に記載の方法。
【請求項２０】
前記ロード命令が前記他のレジスタを使用して前記場所を参照するか否かを判断する前記ステップが、前記ロード命令が前記他のレジスタを使用して前記場所を参照する場合に、前記ローカル・スタック内のページの変換索引バッファ（ＴＬＢ）項目を、スタック参照を含むものとしてマークするステップを含む、請求項１９に記載の方法。
【請求項２１】
前記ロード命令が前記他のレジスタを使用して前記場所を参照しない場合、前記システムのメイン・メモリとキャッシュとのうちの１つから前記ロード命令を実行するステップをさらに含む、請求項１９に記載の方法。
【請求項２２】
前記ロード命令が前記他のレジスタを使用して前記場所を参照する場合、整合性維持機構を実行して前記スタック領域から前記ロード命令を実行するステップをさらに含む、請求項１９に記載の方法。
【請求項２３】
前記リネーム・レジスタが存在しない場合、前記場所のためのリネーム・レジスタを割り振るステップをさらに含む、請求項１２に記載の方法。
【請求項２４】
前記リネーム・レジスタの割振り時に、前記システムのプロセッサから前記割り振られたリネーム・レジスタに前記場所をロードする動作を、前記ロード命令を含む命令ストリームに挿入するステップをさらに含む、請求項２３に記載の方法。
【請求項２５】
前記動作の挿入時に、前記場所に対する前記参照を前記割り振られたリネーム・レジスタに対する参照によって置き換えるステップをさらに含む、請求項２４に記載の方法。
【請求項２６】
コンピュータ処理システムにおいてスタック場所に対するメモリ参照をリネームする方法であって、
ストア命令が、スタック場所にアクセスするためにアーキテクチャ的に定義されたレジスタを使用してローカル・スタック内の場所を参照するか否かを判断するステップと、
前記ストア命令がアーキテクチャ的に定義された前記レジスタを使用して前記場所を参照する場合、前記場所のためにリネーム・レジスタを割り振るステップと、
前記場所に対する前記参照を前記リネーム・レジスタに対する参照によって置き換えるステップとを含む方法。
【請求項２７】
前記場所に対する前記参照を前記リネーム・レジスタに対する前記参照に置き換えたときに、前記リネーム・レジスタから前記システムのメイン・メモリに前記場所をストアする動作を、前記ストア命令を含む命令ストリームに挿入するステップをさらに含む、請求項２６に記載の方法。
【請求項２８】
前記ストア命令がアーキテクチャ的に定義された前記レジスタを使用して前記場所を参照しない場合、前記ストア命令が他のレジスタを使用して前記ローカル・スタックを含む任意のスタック内の場所を参照するか否かを判断するステップをさらに含む、請求項２６に記載の方法。
【請求項２９】
前記ストア命令が前記他のレジスタを使用して前記場所を参照しない場合、前記ストア命令を前記システムのメイン・メモリとキャッシュのうちのいずれか１つから実行するステップをさらに含む、請求項２８に記載の方法。
【請求項３０】
前記ストア命令が前記他のレジスタを使用して前記場所を参照する場合、整合性維持機構を実行して前記スタック領域への前記ストア命令を実行するステップをさらに含む、請求項２８に記載の方法。
【請求項３１】
コンピュータ処理システムにおいてスタック場所に対するメモリ参照をリネームする方法ステップを実行する、機械によって実行可能な命令のプログラムを有形に実施する機械可読プログラム記憶装置であって、前記方法ステップは、
アーキテクチャ的に定義されたスタック・アクセス方法を使用するスタック参照を検出するステップと、
前記スタック参照をプロセッサ内部レジスタに対する参照に置き換えるステップとを含むプログラム記憶装置。
【請求項３２】
前記プロセッサ内部レジスタと前記コンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップをさらに含む、請求項３１に記載のプログラム記憶装置。
【請求項３３】
前記同期化ステップが、書込みスタック参照であるすべてのスタック参照のためのイン・オーダ書込み動作を挿入するステップを含む、請求項３２に記載のプログラム記憶装置。
【請求項３４】
アーキテクチャ的に定義されたスタック・アクセス方法を使用しないスタック参照のための整合性維持動作を実行するステップをさらに含む、請求項３１に記載のプログラム記憶装置。
【請求項３５】
整合性維持動作を実行する前記ステップが、所与のプロセッサ内部レジスタから値を、スタック領域を参照し、アーキテクチャ的に定義されたスタック・アクセス方法を使用しないロード動作にバイパスするステップを含む、請求項３４に記載のプログラム記憶装置。
【請求項３６】
前記プロセッサ内部レジスタと前記コンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップをさらに含み、整合性維持動作を実行する前記ステップが、前記同期化ステップの実行時に前記スタック参照のためのイン・オーダ値を前記メイン・メモリから回復するステップを含む、請求項３４に記載のプログラム記憶装置。
【請求項３７】
前記スタック参照が書込みスタック参照である場合、前記イン・オーダ値が前記スタック参照に対応する命令を含む命令ストリームに挿入されたイン・オーダ書込み動作によって前記メイン・メモリに書き込まれる、請求項３６に記載のプログラム記憶装置。
【請求項３８】
アーキテクチャ的に定義された前記スタック・アクセス方法を使用しないロード動作に応答して、前記イン・オーダ値を前記メイン・メモリに書き込むステップをさらに含む、請求項３６に記載のプログラム記憶装置。
【請求項３９】
整合性維持動作を実行する前記ステップが、
前記システムのプロセッサのすべてのアウト・オブ・オーダ状態を廃棄するステップと、
前記プロセッサ内部レジスタと前記コンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップと、
アーキテクチャ的に定義された前記スタック・アクセス方法を使用しないストア動作が行われた後に実行を再開するステップとを含む、請求項３４に記載のプログラム記憶装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般にはコンピュータ処理システムに関し、より詳細には、コンピュータ処理システムにおいてスタック・リファレンスをリネームする方法に関する。
【０００２】
【従来の技術】
メモリは、コンピュータ処理システムにおける情報のリポジトリとして機能する。図１は、従来の技術によるコンピュータ・プログラムのメモリ１００の典型的なレイアウトを示すブロック図である。このレイアウトは、プログラム・テキスト領域１０４、プログラム・データ領域１０６、ヒープ１０８、およびプログラム・スタック１１０を含む、明確に区別されたメモリ領域から成る。プログラム・テキスト領域１０４は、プログラム・テキスト（すなわちコンピュータ命令）を格納するために使用される。プログラム・データ領域１０６は、（静的データ参照用の）プログラム・データを格納するために使用される。ヒープ１０８は、動的割振りオブジェクト（ｄｙｎａｍｉｃａｌｌｙ  ａｌｌｏｃａｔｅｄ  ｏｂｊｅｃｔｓ）のために使用され、プログラム・スタック１１０は、関数のローカル変数のために使用される。
【０００３】
図のように、メモリ１００には、異なるタイプのデータが明確に区別されたメモリ領域に格納される。これらのメモリにアクセスするには、以下の異なる各機構が使用される。
１．プログラム・テキスト領域１０４には、プログラムの内容を記述するコンピュータ命令と、場合によっては、プログラム定数が格納される。プログラム・テキスト領域１０４は、通常読取り専用で、プログラム・カウンタを使用してアクセスされる。
２．プログラム・データ領域１０６には、静的データ参照、たとえばグローバル・プログラム変数が保持される。プログラム・データ領域１０６には、グローバル・データ・ポインタまたは目次データ構造のテーブルを使用してアクセスする。
３．ヒープ１０８には、動的割振りオブジェクトが保持され、いずれかのプロセッサ・レジスタに保持されたポインタを使用してアクセスする。
４．プログラム・スタック１１０には、通常、関数ローカル変数が保持され、スタック・ポインタ（ＳＰ）、フレーム・ポインタ（ＦＰ）、または引数ポインタ（ＡＰ）などの特殊目的レジスタを使用してアクセスする。
【０００４】
通常、すべてのプログラム・メモリには、レジスタに格納されたポインタを使用してアクセスすることができる。しかし、上述のアクセス機構は、典型的なプログラム中の各領域のために一般的に使用される。
【０００５】
一般に、プロセッサは、メモリからの情報にアクセスし、それに対して演算を行い、その結果をメモリに格納し戻す。残念ながら、メモリ・アクセスは、いくつかの犠牲を要する。それらの犠牲の一部を以下に説明する。
【０００６】
メモリ・アクセス動作が最初に検出されると、アクセスするアドレスを解決する必要がある。さらに、アドレス計算に使用されるレジスタが使用可能でなければならない。
【０００７】
プロセッサが他のメモリ動作に関してメモリ読取り動作をリオーダする必要があって、リオーダする時点で読み取られたアドレスが異なっていることを判断することができない場合、メモリ・アドレスの曖昧性の検査を行う必要がある。
【０００８】
さらに、ストア動作によってプロセッサ状態が変更されるため、一般には、ストア動作は順に（イン・オーダ：ｉｎ−ｏｒｄｅｒ）実行しなければならない。このため、同じ記憶場所に複数の活性範囲（ｌｉｖｅ  ｒａｎｇｅ）が割り当てられている場合、逐次化動作によって、達成可能プロセッサ・パフォーマンスがさらに低速化する。したがって、一般には、同じメモリ・アドレスに複数の独立した値が割り当てられている場合、スーパースカラ・プロセッサにおいて行うことができるリオーダの程度が制限される。
【０００９】
さらに、ロード動作およびストア動作は、一般にはキャッシュへのアクセスを必要とする。しかし、キャッシュへのアクセスは、コンピュータ処理システムのメモリ階層内でより上位の層であるプロセッサ・レジスタへのアクセスと比較して低速である。
【００１０】
メモリ参照の逐次化効果の多くは、プログラマによるプログラムの作成方法による。しかし、メモリ参照の逐次化効果は、プログラムをソース・レベル表現から実マシンへの変換方法により生じることもある。そのような場合、プログラム・スタックへの参照が行われる。
【００１１】
プログラム・スタックには、スタック・フレーム、すなわち関数のローカル変数の値を含むレコードと、関数間で受け渡しされるパラメータが格納される。スタック場所は頻繁に再使用され、異なる関数が、同じアドレスを持つ記憶場所を使用して関連性のないオブジェクトを格納する。
【００１２】
Ｃプログラム言語で作成された以下のコード例を考えてみる。
0003564072.tif 000002
【００１３】
このコードをＩｎｔｅｌ  ｘ８６マシン・コードに変換すると、以下の命令が生成される。
１        ｍｕｌｔ３：
２                ｉｍｕｌｌ  ＄３．４（％ｅｓｐ），％ｅａｘ
３                ｒｅｔ
４
５        ｉｎｃ：
６                ｍｏｖｌ  ４（％ｅｓｐ），％ｅａｘ
７                ｉｎｃｌ  ％ｅａｘ
８                ｒｅｔ
９
１０      ｃｏｍｐｕｔｅ：
１１              ｐｕｓｈｌ  ％ｅｓｉ
１２              ｐｕｓｈｌ  ％ｅｂｘ
１３              ｍｏｖｌ  １２（％ｅｓｐ），％ｅａｘ
１４              ｍｏｖｌ  １６（％ｅｓｐ），％ｅｂｘ
１５              ｐｕｓｈ  ％ｅａｘ
１６              ｃａｌｌ  ｍｕｌｔ３
１７              ａｄｄｌ  ＄４，％ｅｓｐ
１８              ｍｏｖｌ  ％ｅａｘ，％ｅｓｉ
１９              ｐｕｓｈｌ  ％ｅｂｘ
２０              ｃａｌｌ  ｉｎｃ
２１              ａｄｄｌ  ＄４，％ｅｓｐ
２２              ａｄｄｌ  ％ｅｓｉ，％ｅａｘ
２３              ｐｏｐｌ  ％ｅｂｘ
２４              ｐｏｐｌ  ％ｅｓｉ
２５              ｒｅｔ
上掲のコードは、以下のようなメモリ内でプロセッサ・スタックを保持する非効率性の例をいくつか示している。
１．レジスタＥＳＩおよびＥＢＸの値が命令１１および１２でスタックに格納され、命令２３および２４でリストアされる。これらの値は、プロセッサ内部レジスタに保持することができたはずである。
２．呼出し関数によってスタックにプッシュされたパラメータａおよびｂを、スタックからプロセッサ・レジスタに読み込み、次に、それぞれ関数ｍｕｌｔ３およびｉｎｃのためにスタックに格納しなければならない。
３．それぞれ関数ｍｕｌｔ３およびｉｎｃのパラメータａおよびｂが同じスタック場所に格納され、したがって、関数ｉｎｃからの動作を関数ｍｕｌｔ３の命令と同時にスケジュールすることはできない。この逐次化は不要である。
【００１４】
ポスティフ（Ｐｏｓｔｉｆｆ）等の「Ｔｈｅ  Ｌｉｍｉｔｓ  ｏｆ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｌｅｖｅｌ  Ｐａｒａｌｌｅｌｉｓｍ  ｉｎ  ＳＰＥＣ９５  Ａｐｐｌｉｃａｔｉｏｎｓ」（Ａｒｃｈｉｔｅｃｔｕｒａｌ  Ｓｕｐｐｏｒｔ  ｆｏｒ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅｓ  ａｎｄ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍｓに関する国際会議  （ＡＳＰＬＯＳ−ＶＩＩＩ）  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｉｎｔｅｒａｃｔｉｏｎ  ｂｅｔｗｅｅｎ  Ｃｏｍｐｉｌｅｒｓ  ａｎｄ  Ｃｏｍｐｕｔｅｒ  Ａｒｃｈｔｅｃｔｕｒｅｓ  （ＩＮＴＥＲＡＣＴ−３）、１９９８年１０月）には、記憶場所の再使用とスタック・ポインタの操作によるスタック参照の逐次化効果について記載されている。ポスティフ等は、さらに、これらの逐次化効果を解決することによって達成可能なパフォーマンス向上について記載している。
【００１５】
【発明が解決しようとする課題】
従来のメモリ・リネームは、一般メモリ参照に基づいており、マルチプロセッサ効果を無視する傾向があったことを理解する必要がある。これらの従来技術の手法のいくつかについて、以下に説明する。
【００１６】
メモリ・リネームは、一般に、データ依存関係の予測を含むことを理解されたい。Ａ．モショフォス（Ｍｏｓｈｏｖｏｓ）およびＧ．ソヒ（Ｓｏｈｉ）による「Ｓｔｒｅａｍｌｉｎｉｎｇ  Ｉｎｔｅｒ−ｏｐｅｒａｔｉｏｎ  Ｍｅｍｏｒｙ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｖｉａ  Ｄａｔａ  Ｄｅｐｅｎｄｅｎｃｅ  Ｐｒｅｄｉｃｔｉｏｎ」（Ｍｉｃｒｏａｒｃｈｉｔｅｃｔｕｒｅ  Ｒｅｓｅａｒｃｈに関する第３０回年次国際会議議事録、米国ノースカロライナ州トライアングル・パーク、１９９７年１２月）には、アドレス計算なしにデータ依存関係を動的に予測する機構について記載されている。依存関係の予測が必要なのは、ロード動作およびストア動作のアドレスは解決されないことがあるためである。予測の正確さを保証するには、最終的にこれらのメモリ動作を実行する必要がある。依存関係を予測する同様の手法については、Ｇ．タイソン（Ｔｙｓｏｎ）およびＴ．オースチン（Ａｕｓｔｉｎ）による「Ｉｍｐｒｏｖｉｎｇ  ｔｈｅ  Ａｃｃｕｒａｃｙ  ａｎｄ  Ｐｅｒｆｏｒｍａｎｃｅ  ｏｆ  Ｍｅｍｏｒｙ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｔｈｒｏｕｇｈ  Ｒｅｎａｍｉｎｇ」（Ｍｉｃｒｏａｒｃｈｉｔｅｃｔｕｒｅ  Ｒｅｓｅａｒｃｈに関する第３０回年次国際シンポジウム議事録、米国ノースカロライナ州トライアングル・パーク、１９９７年１２月）に記載されている。モショフォスおよびソヒと、タイソンおよびオースチンは、メモリへのアクセスをプロセッサ内部レジスタにプロモートする汎用技法を提供する。これは、かなり複雑なハードウェアを必要とする。さらに、命令の実際のデコードほど正確でなく、高くつく修復処置を必要とすることもある予測を使用する。Ｍ．フランクリン（Ｆｒａｎｃｌｉｎ）およびＧ．ソヒ（Ｓｏｈｉ）による「ＡＲＢ：  Ａ  Ｈａｒｄｗａｒｅ  Ｍｅｃｈａｎｉｓｍ  ｆｏｒ  Ｄｙｎａｍｉｃ  Ｒｅｏｒｄｅｒｉｎｇ  ｏｆ  Ｍｅｍｏｒｙ  Ｒｅｆｅｒｅｎｃｅｓ」（ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｐｕｔｅｒｓ，  Ｖｏｌ．４５，  Ｎｏ．５、１９９６年５月）には、メモリ動作の順序外れ（アウト・オブ・オーダ：ｏｕｔ−ｏｆ−ｏｒｄｅｒ）実行とメモリ・リネームをサポートするアドレス解決バッファについて記載されている。このバッファは高価であり、必要なハードウェアが複雑で、バッファはマルチプロセッサ・システムおよびその整合性要件について考慮していないという欠点がある。
【００１７】
米国特許第５９１１０５７号には、メモリおよびレジスタ・オペランドのリネームを一様な方法で行うアーキテクチャが記載されている。メモリ・コヒーレンシは、メモリ要求の「スヌープ」に基づいている。この手法は、マルチプロセッサ・コンピューティング・システムにおけるメモリ動作のイン・オーダ実行には十分であるが、マルチプロセッサ・システムにおけるアウト・オブ・オーダ動作では不正な結果を生じることがある。米国特許第５８３８９４１号には、メモリ参照のシンボリック・リネームについて記載されている。その発明は、あらゆるタイプの等価性を扱い、式と名前の間の等価性を確立するために連想配列のロックアップを要する。その結果、サイクル時間に重大な影響を与える可能性のある複雑なアーキテクチャになる。
【００１８】
したがって、スタック参照によって生じる逐次化効果をなくす方法を設けることが望ましく、きわめて有利であろう。そのような方法がマルチプロセッサ・システムに適用可能であれば、さらに望ましく、有利であろう。
【００１９】
【課題を解決するための手段】
従来技術の上述の問題およびその他の関連する問題は、本発明、すなわちコンピュータ処理システムにおけるスタック参照をリネームする方法によって解決される。
【００２０】
本発明の第１の態様によると、コンピュータ処理システムにおけるスタック場所のメモリ参照をリネームする方法が提供される。この方法は、アーキテクチャ的に定義されたスタック・アクセス方法を使用するスタック参照を検出するステップと、そのスタック参照をプロセッサ内部レジスタに対する参照に置き換えるステップとを含む。
【００２１】
本発明の第２の態様によると、この方法は、プロセッサ内部レジスタとコンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップをさらに含む。
【００２２】
本発明の第３の態様によると、この方法は、書き込みスタック参照であるすべてのスタック参照のためにイン・オーダ書き込み動作を挿入するステップをさらに含む。
【００２３】
本発明の第４の態様によると、アーキテクチャ的に定義されたスタック・アクセス方法を使用しないスタック参照のための整合性維持動作を行うステップをさらに含む。
【００２４】
本発明の第５の態様によると、整合性維持動作を行うステップは、所与のプロセッサ内部レジスタから値を、スタック領域を参照し、アーキテクチャ的に定義されたスタック・アクセス方法を使用しないロード動作にバイパスするステップを含む。
【００２５】
本発明の第６の態様によると、アーキテクチャ的に定義されたスタック・アクセス方法は、スタック・ポインタとフレーム・ポインタと引数ポインタとのうちの一つを使用するメモリ・アクセスを含む。
【００２６】
本発明の第７の態様によると、アーキテクチャ的に定義されたスタック・アクセス方法は、プッシュ、ポップ、およびその他のスタック操作動作を含む。
【００２７】
本発明の第８の態様によると、コンピュータ処理システムにおいてスタック場所のメモリ参照をリネームする方法が提供される。この方法は、ロード命令がスタック場所にアクセスするためにアーキテクチャ的に定義されたレジスタを使用してローカル・スタック内の場所を参照するか否かを判断するステップを含む。ロード命令がアーキテクチャ的に定義されたレジスタを使用してその場所を参照する場合、ローカル・スタック内の参照場所のためにリネーム・レジスタが存在するか否かを判断する。リネーム・レジスタが存在する場合、その場所に対する参照は、リネーム・レジスタに対する参照に置き換えられる。
【００２８】
【発明の実施の形態】
本発明は、コンピュータ処理システムにおいてスタック参照をリネームする方法を対象とする。本発明によると、スタック参照は、プロセッサ内部レジスタにリネームされる。スタック参照のための頻繁なリネーム機会に集中することによって、メモリ参照をリネームする従来技術の手法より、リネーム・アーキテクチャをより効率的に実施することができる。
【００２９】
このような効率は、２つの態様から得られる。第１の態様については、プロセッサ・スタックへの参照が、スタック・ポインタやフレーム・ポインタなどの限られた数のアドレス指定レジスタを使用するため、名前がより判断しやすい。これにより、異なる汎用レジスタを使用して記憶場所をリネームする際に生じる可能性がある曖昧性が低減される。他のレジスタを使用したアクセスも可能であるが、それらは、単純な一義化技法を使用して処理することができるほどまれである。
【００３０】
第２の態様については、スタック参照は通常、ローカル・プロセスからのみ参照されるため、マルチプロセッサ・システムにおいて整合性維持動作を行う必要が大幅に削減される。この場合も、他のプロセッサからの参照が可能であるが、まれにしかないため、単純な技法を使用して解決することができる。
【００３１】
プロセッサ・レジスタに対するスタック参照のリネームによって、スタック参照が、参照のリオーダ、リネームによる逆依存（ａｎｔｉ−ｄｅｐｅｎｄｅｎｃｉｅｓ）の解決、および書込み動作の投機実行など、一般にプロセッサ・レジスタに適用されるいくつかの最適化が適用されるようになることを理解されたい。
【００３２】
本発明を明確に理解しやすいように、本明細書で使用する用語の定義を以下に示す。ロード命令とは、メモリ読取りアクセスと、（任意選択により）ロード値に基づく計算を行うあらゆる命令を指す。したがって、ロード命令には、たとえば、記憶場所内のデータをオペランドとして使用する論理、算術、およびその他の命令が含まれる。ストア命令とは、メモリ書込みアクセスと、任意選択により計算を行うあらゆる命令を指す。アウト・オブ・オーダ実行とは、後で現れる動作に必要な資源が解放されている場合、命令の順次ストリーム内の動作を、後で現れる動作を先に実行するようにリオーダする技法である。したがって、命令を命令シーケンス内の元の位置から命令シーケンスのうちの早い位置に移動させることによって、アウト・オブ・オーダ命令を静的にも動的にも作成することができる。
【００３３】
以下の説明および対応する各例は、（特に明記しない限り）２つの命令に基づいて示す。第１の命令は、イン・オーダ命令と呼ぶ論理的に先行する第２の命令の前に、アウト・オブ・オーダ実行される。したがって、特に明記のない限り、「イン・オーダ」という表記は、論理的に先行するイン・オーダ命令と第１の「アウト・オブ・オーダ」命令との順次関係のみを指す。上記の２つの命令（すなわち、イン・オーダ・ロード命令とアウト・オブ・オーダ・ロード命令の両方）は、第３の命令（およびそれ以降の命令）を基準にしてイン・オーダまたはアウト・オブ・オーダであることに留意されたい。
【００３４】
本発明の概念を紹介するために、本発明について以下に概説する。その後で、本発明の様々な態様について詳述する。
【００３５】
本発明は、（すべてのメモリ参照をリネームするのではなく）メモリ・スタック参照のみをリネームすることによって、メモリ・リネームの問題を簡略化する。このような手法は、少なくとも以下の理由により有利である。
１．スタック参照の逐次化効果によるパフォーマンス低下は、変換プロセスによって人為的に引き起こされ、プログラムに内在するものではない。
２．スタック参照をリネームするだけで、大幅なパフォーマンス向上を達成することができる。
３．（メモリ内の任意の場所を指し得る他のレジスタとは異なり）スタック・ポインタとフレーム・ポインタは明確に定義されたセマンティクスを有するため、スタック・アクセスの「名前」が判断しやすい。
４．スタック参照は、通常、１つのプロセスおよび単一のプロセッサに局在的であり、スタック・ポインタまたはフレーム・ポインタを介して行われるため、マルチプロセッサの整合性の重要度が低くなる。
５．スタックへの参照は通常、スタック・ポインタまたはフレーム・ポインタを介して行われるため、命名等価性の検出が容易である（フレーム・ポインタは通常、スタック・ポインタからの明確に定義された距離にある）。
【００３６】
メモリへの異なる参照間の整合性は、スタック参照が通常、ローカル・プロセッサ・スタックのみに対するものであり、スタック・ポインタ（ＳＰ）やフレーム・ポインタ（ＦＰ）、任意選択の引数ポインタ（ＡＰ）など、そのスタックを管理するように特に指定されたレジスタのみを介するということを遵守することによって、解決することができる。
【００３７】
これらの特に指定されたスタック管理レジスタ以外の手段による１つのプロセッサのスタック領域に対する参照があると、整合性を維持する処置が行われる。そのような参照は容易に検出することができる。たとえば、汎用レジスタ（たとえば、ＳＰ、ＦＰ、ＡＰなどのスタック・レジスタ以外のレジスタ）によるローカル・プロセッサ・スタックへのアクセスは、そのスタックを含むページ・テーブル項目にタグ付けし、メモリ・ユニット内の条件を示すことによって検出することができる。その後、プロセッサはこの状況をハードウェアで処理するか、または例外を起こして例外ハンドラ内でその条件を解決することができる。他の例として、マルチプロセッシングシステムでは、変換索引バッファ（ＴＬＢ）で項目を使用可能にせず、それによって例外をとってソフトウェア内の条件を処理するか、またはページを使用してそのスタックをリモート・プロセッサに格納することをＴＬＢで示すことによって、別のプロセッサのスタックへのアクセスを検出することができる。
【００３８】
図２は、本発明の例示の実施形態による、単一の命令の初期処理を行う方法を示す流れ図である。
【００３９】
命令は、プログラム・メモリ１００からフェッチされる（ステップ２１０）。次に、フェッチした命令がメモリ動作であるか否か（すなわち、フェッチした命令がメモリ１００を参照するか否か）を判断する（ステップ２１２）。メモリ動作である場合、そのメモリ動作が本発明により処理される（ステップ２１４）。この具体的な処理ステップを、読取りアクセスのためにメモリを参照する命令の場合を図３および図４に詳細に示し、書込みアクセスのためにメモリを参照する命令の場合を図５に示す。
【００４０】
フェッチした命令がメモリ動作でない場合、プロセッサ・レジスタに対する参照がリネームされる（ステップ２１６）。ステップ２１６は任意選択であり、したがって、所望であれば省くことができることを理解されたい。次に命令は、実行ユニットの１つにディスパッチするためにディスパッチ・テーブルに入れられ（ステップ２１８）、この方法は終了する。
【００４１】
図３は、本発明の例示の実施形態によるロード動作（たとえば図２のステップ２１４）の処理を示す流れ図である。一般に、メモリ読取り参照のためのリネーム・レジスタが見つかった場合、そのメモリ読取り参照はリネーム・レジスタに対する参照に置き換えられる。見つからなかった場合は、メモリに記憶されているスタック場所からのロードが行われる。
【００４２】
図３の方法によると、ロード命令が、スタック・ポインタＳＰまたはフレーム・ポインタＦＰを使用してローカル・スタック内の場所を参照するか否かを判断する（ステップ３１０）。アーキテクチャによっては、任意選択により、ステップ３１０で、ロード命令が、ＤＥＣ  ＶＡＸアーキテクチャにおける引数ポインタＡＰなど、スタック場所にアクセスするために使用される追加のポインタを参照するか否かを判断することができる。ロード命令は、ＳＰ、ＦＰ、またはＡＰレジスタを明示的に参照する必要はなく、そのようなポインタを少なくとも１つ暗黙的に参照する（たとえばＩｎｔｅｌ  ｘ８６アーキテクチャに見られるような）プッシュやポップなどの命令とすることもできる。
【００４３】
ロード命令がスタック・ポインタＳＰまたはフレーム・ポインタＦＰを使用してローカル・スタック内の場所を参照する場合、この方法はステップ３２０に進む。それ以外の場合は、ロード命令が他のレジスタを使用してスタック内の場所を参照するか否かが判断される（ステップ３１４）。ローカル・スタック場所のみにかかわるステップ３１０で行われる判断とは異なり、ステップ３１４で行われる判断は、ローカルまたはリモートの両方のスタック場所を含む。
【００４４】
ステップ３１４は、デコード、アドレス生成、またはメモリ・アクセス段階のいずれかで行うことができる。本発明の例示の実施形態によると、ステップ３１４の一実施形態は、スタック１１０（図１参照）内のページのＴＬＢ項目を、スタック参照を含むものとしてマークすることを含めることができる。
【００４５】
ロード命令が他のレジスタを使用してスタック内の場所を参照しない場合、通常のロード動作（すなわち、メイン・メモリまたはキャッシュからのロード動作）を行い、その後でこの方法は終了する（ステップ３１６）。しかし、ロード命令が他のレジスタを使用してスタック内の場所を参照する場合、整合性維持機構が実行され、スタック領域からのロード動作が行われる（ステップ３１８）。整合性維持機構は、ハードウェア、ソフトウェア、またはその組合せで実施することができる。整合性維持機構の例示の実施形態については、以下で詳述する。
【００４６】
ステップ３２０で、ローカル・スタック内の参照場所のためのリネーム・レジスタが存在するか否かを判断する。ステップ３２０は、スタック・ポインタからの変位１００を有するメモリ参照のためのシンボリック・アドレス、すなわち「（ＳＰ）＋１００」を使用して、または参照場所のアドレスを実際に計算することによって行うことができる。
【００４７】
ローカル・スタック内の参照場所のためのリネーム・レジスタが存在する場合、スタック場所に対する参照はリネーム・レジスタに対する参照に置き換えられ、この方法は終了する（ステップ３２２）。しかし、ローカル・スタック内の参照場所のためのリネーム・レジスタが存在しない場合、通常のロード命令（すなわち、メイン・メモリまたはキャッシュからのロード命令）が、命令ストリームに挿入され、この方法は終了する。
【００４８】
メモリ・リネームをスタック参照に限定することによって、前述の従来技術の各メモリ・リネーム手法に対して、アドレス解決が簡略化されるという利点が得られる。したがって、前記で引用した「Ｓｔｒｅａｍｌｉｎｉｎｇ  Ｉｎｔｅｒ−Ｏｐｅｒａｔｉｏｎ  Ｍｅｍｏｒｙ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  ｖｉａ  Ｄａｔａ  Ｄｅｐｅｎｄｅｎｃｅ  Ｐｒｅｄｉｃｔｉｏｎ」という標題の論文でＡ．モショフォス（Ｍｏｓｈｏｖｏｓ）およびＧ．ソヒ（Ｓｏｈｉ）が使用したデータ依存関係予測とは異なり、命令をデコードすることによって実際の依存関係を判断することができる。
【００４９】
さらに、他のシンボリック・リネーム技法とは異なり、スタック参照のシンボリック・リネームは、米国特許第５８３８９４１号のように、等価性を判断するための複雑な論理を必要としない。本発明の手法では、すべての参照が、互いからの容易に判断可能なオフセット位置にあるスタック・レジスタの１つを介する。
【００５０】
図３の方法は、スタック・ポインタ値が変更されると（たとえばサブルーチン呼出し時）、参照の調整を必要とすることを理解されたい。しかし、そのような調整は、当業者なら容易に行うことができる。
【００５１】
スタック・ポインタおよびフレーム・ポインタの値は判断しやすく、まれにしか変化しないため、絶対アドレスの使用も簡単になる。具体的には、これらのレジスタに加えられる変更は、単純な算術演算で済み、この算術演算はスタック参照リネーム論理におけるリネームにのみ使用されるシャドウ・スタック・ポインタを使用して投機的に行うことができる。
【００５２】
図４は、本発明の他の例示の実施形態によるロード動作の処理（たとえば図２のステップ２１４）を示す流れ図である。一般に、スタック場所のためのリネーム・レジスタが見つかった場合、メモリ参照はリネーム・レジスタに対する参照に置き換えられる。見つからない場合、新しいリネーム・レジスタが割り振られスタックからリネーム・レジスタに値をロードする命令が命令ストリームに挿入され、記憶場所に対する元の参照が新たに割り振られたリネーム・レジスタに対する参照に置き換えられる。
【００５３】
図４の方法によると、ロード命令がスタック・ポインタＳＰまたはフレーム・ポインタＦＰを使用してローカル・スタック内の場所を参照するか否かが判断される（ステップ４１０）。アーキテクチャによっては、ステップ４１０は、任意選択により、ロード命令が、ＤＥＣ  ＶＡＸアーキテクチャにおける引数ポインタＡＰなど、スタック場所にアクセスするために使用される追加のポインタを参照するか否かを判断することができる。ロード命令は、ＳＰ、ＦＰ、またはＡＰレジスタを明示的に参照する必要はなく、そのようなポインタを少なくとも１つ暗黙的に参照する（たとえばＩｎｔｅｌ  ｘ８６アーキテクチャに見られるような）プッシュやポップなどの命令とすることもできる。
【００５４】
ロード命令がスタック・ポインタＳＰまたはフレーム・ポインタＦＰを使用してローカル・スタック内の場所を参照する場合、この方法はステップ４２０に進む。それ以外の場合は、ロード命令が他のレジスタを使用してスタック内の場所を参照するか否かが判断される（ステップ４１４）。ステップ４１４は、デコード、アドレス生成、またはメモリ・アクセス段階のいずれかで行うことができる。本発明の例示の実施形態によると、ステップ４１４の一実施態様は、スタックメモリ領域（図１参照）内のページのＴＬＢ項目を、スタック参照を含むものとしてマークすることを含めることができる。
【００５５】
ロード命令が、他のレジスタを使用してスタック内の場所を参照しない場合、通常のロード動作（すなわち、メイン・メモリまたはキャッシュからのロード動作）が行われ、この方法は終了する（ステップ４１６）。しかし、ロード命令が他のレジスタを使用してスタック内の場所を参照する場合は、整合性維持機構が実行され、スタック領域からのロード動作が行われる（ステップ４１８）。整合性維持機構は、ハードウェア、ソフトウェア、またはその組合せで実施することができる。整合性維持機構の例示の実施形態については、以下で詳述する。
【００５６】
ステップ４２０で、参照場所のためのリネーム・レジスタが存在するか否かが判断される。この検査は、スタック・ポインタからの変位１００によるメモリ参照のためのシンボリック・アドレス、すなわち「（ＳＰ）＋１００」を使用するか、または参照場所のアドレスを実際に計算することによって行うことができる。メモリ・リネームをスタック参照に限定することにより、図３を参照しながら前述した利点が得られる。
【００５７】
使用する命名技法に関係なく、参照場所のためのリネーム・レジスタが存在する場合、スタック場所に対する参照はリネーム・レジスタに対する参照に置き換えられ、この方法は終了する（ステップ４２２）。しかし、参照場所のためのリネーム・レジスタが存在しない場合は、ロード動作によって参照されたスタック場所のためにリネーム・レジスタが割り振られる（ステップ４２４）。次に、プロセッサから新たに割り振られたリネーム・レジスタに値をロードするロード命令が命令ストリームに挿入され（ステップ４２６）、この方法はステップ４２２に戻る。
【００５８】
図５は、本発明の例示の実施形態による、（たとえば図６のユニット６２０における）ストア動作の処理を示す流れ図である。
【００５９】
ストア命令がスタック・ポインタＳＰまたはフレーム・ポインタＦＰを使用してローカル・スタック内の場所を参照するか否かが判断される（ステップ５１０）。アーキテクチャによっては、任意選択により、ステップ５１０で、ストア命令が、ＤＥＣ  ＶＡＸアーキテクチャにおける引数ポインタＡＰなど、スタック場所にアクセスするために使用される追加のポインタを参照するか否かを判断することができる。ストア命令は、ＳＰ、ＦＰ、またはＡＰレジスタを明示的に参照する必要はなく、そのようなポインタを少なくとも１つ暗黙的に参照する（たとえばＩｎｔｅｌ  ｘ８６アーキテクチャに見られるような）プッシュやポップなどの命令とすることもできる。
【００６０】
ストア命令がスタック・ポインタＳＰまたはフレーム・ポインタＦＰを使用してローカル・スタック内の場所を参照する場合、この方法はステップ５２０に進む。そうでない場合は、ストア命令が他のレジスタを使用してスタック内の場所を参照するか否かが判断される（ステップ５１４）。ステップ５１０で行うローカル・スタック場所のみに関する判断とは異なり、ステップ５１４で行う判断はローカルとリモートの両方のスタック場所を対象とする。ステップ５１４は、デコード、アドレス生成、またはリモート・アクセス段階のいずれかで行うことができる。本発明の例示の実施形態によると、ステップ５１４の一実施態様は、スタック・メモリ領域（図１を参照）内のページのＴＬＢ項目をスタック参照を含むものとしてマークすることを含む。
【００６１】
ストア命令が他のレジスタを使用してスタック内の場所を参照しない場合は、通常のストア動作（すなわちメイン・メモリまたはキャッシュからのストア動作）を行い、この方法は終了する（ステップ５１６）。しかし、命令が他のレジスタを使用してスタック内の場所を参照する場合は、整合性維持機構を実行してスタック領域へのストア動作が行う（ステップ５１８）。整合性維持機構は、ハードウェア、ソフトウェア、またはその組合せで行うことができる。整合性維持機構の例示の実施形態については、以下で詳述する。
【００６２】
ステップ５２０で、ストア動作によって参照されたスタック場所のために新しいリネーム・レジスタが割り振られる。リネーム・レジスタは、スタック・ポインタからの変位１００によるメモリ参照のためのシンボリック・アドレス、すなわち「（ＳＰ）＋１００」を使用するか、または参照場所のアドレスを実際に計算することによって名前指定することができる。メモリ・リネームをスタック参照に限定することにより、上記で図３に関して述べたような利点が得られる。
【００６３】
メモリ参照は新たに割り振られたリネーム・レジスタに対する参照に置き換えられる（ステップ５２２）。リネーム・レジスタからメモリに値を格納する命令が命令ストリームに挿入され（ステップ５２４）、この方法は終了する。ステップ５２４は任意選択であり、したがって所望であれば省くことができることを理解されたい。
【００６４】
命令を動的にスケジュールすることができるプロセッサ（アウト・オブ・オーダ発行プロセッサ）の従来の実施態様には、以下のような機構がある。
１．命令間の依存関係を検出し、命令が使用するレジスタをリネームし、命令が使用する資源が使用可能であるかを検出する機能を備えた、命令をアウト・オブ・オーダ（順序外れ）で発行する機構。
２．命令が（アウト・オブ・オーダ）実行されるときの効果を反映したプロセッサのアウト・オブ・オーダ状態を維持する機構。
３．命令をプログラム順序でリタイアさせ、それと同時に、リタイアされる命令の効果によってイン・オーダ状態を更新する機構。
４．イン・オーダ状態を更新せずに命令をプログラム順序でリタイアさせ（リタイアされる命令の効果を実際上取り消す）、リタイアされる命令から始まるプログラムのイン・オーダ実行を再開する（アウト・オブ・オーダ状態に存在するすべての効果を取り消すことを意味する）機構。
【００６５】
上記のうちの機構３は、リタイヤされる命令の効果が正しい時に命令をリタイヤするために使用される。あるいは、機構４は、リタイヤされる命令の実行、またはある外部の事象から生じる何らかの異常があるか否にかかわらず、使用される。
【００６６】
図６は、本発明を適用することができる（たとえばスーパスカラ・プロセッサを含む）従来のコンピュータ処理システムの機能ブロック図である。図６のシステムは、上記の機構を使用するメモリ動作のリオーダ機能をサポートするが、プログラム・スタックに対する参照をアウト・オブ・オーダでリネームし、実行する機能は含まない。このシステムは、メモリ・サブシステム６０１、データ・キャッシュ６０２、命令キャッシュ６０４、およびプロセッサ・ユニット６００から成る。プロセッサ・ユニット６００は、命令待ち行列６０３、ロード動作およびストア動作を行うためのいくつかのメモリ・ユニット（ＭＵ）６０５、整数演算、論理演算、および浮動小数点演算を行ういくつかの機能ユニット（ＦＵ）６０７、分岐ユニット（ＢＵ）６０９、レジスタ・ファイル６１１、レジスタ・マップ・テーブル６２０、空きレジスタ待ち行列６２２、ディスパッチ・テーブル６２４、リタイア待ち行列６２６、およびイン・オーダ・マップ・テーブル６２８を含む。この例示の構成は、Ｍ．モウドギル（Ｍｏｕｄｇｉｌｌ）、Ｋ．ピンガリ（Ｐｉｎｇａｌｉ）、およびＳ．バシリアディス（Ｖａｓｓｉｌｉａｄｉｓ）による「Ｒｅｇｉｓｔｅｒ  Ｒｅｎａｍｉｎｇ  ａｎｄ  Ｄｙｎａｍｉｃ  Ｓｐｅｃｕｌａｔｉｏｎ：  Ａｎ  Ａｌｔｅｒｎａｔｉｖｅ  Ａｐｐｒｏａｃｈ」（マイクロアーキテクチャに関する第２６回国際シンポジウム議事録ｐｐ．２０２−２１３（１９９３年１２月）に記載されている構成に基づいている。
【００６７】
図６に示すプロセッサでは、命令は、分岐ユニット６０９の制御下で命令キャッシュ６０４から（または、命令が命令キャッシュ６０４にない場合はメモリ・サブシステム６０１から）フェッチされ、命令待ち行列６０３に入れられ、その後、命令待ち行列６０３からディスパッチされる。命令がオペランドを指定するために使用するレジスタ名は、アーキテクテッド・レジスタから物理レジスタへの現行マッピングを指定するレジスタ・マップ・テーブル６２０の内容に従ってリネームされる。命令が結果の宛先を指定するために使用するアーキテクテッド・レジスタ名には、現在プロセッサによって使用されていない物理レジスタの名前が入った空きレジスタ待ち行列６２２から取り出された物理レジスタが割り当てられる。レジスタ・マップ・テーブル６２０は、命令によって指定されたアーキテクテッド宛先レジスタ名への物理レジスタの割当てによって更新される。すべてのレジスタがリネームされた命令は、ディスパッチ・テーブル６２４に入れられる。命令は、アドレス、物理レジスタ名、およびアーキテクテッド・レジスタ名を含めてプログラム順序でリタイア待ち行列６２６にも入れられる。命令は、命令によって使用されるすべての資源が使用可能な場合（物理レジスタに期待のオペランドが割り当てられており、機能ユニットが空いている場合）、ディスパッチ・テーブル６２４からディスパッチされる。命令が使用するオペランドは、レジスタ・ファイル６１１から読み取られる。レジスタ・ファイル６１１は、典型的には、汎用レジスタ（ＧＰＲ）と浮動小数点レジスタ（ＦＰＲ）と条件レジスタ（ＣＲ）とを含む。命令は、対応するメモリ・ユニット６０５，機能ユニット６０７、または分岐ユニット６０９で、場合によってはアウト・オブ・オーダで実行される。実行が完了すると、命令の結果がレジスタ・ファイル６１１に入れられる。実行を完了する命令によって設定される物理レジスタを待っているディスパッチ・テーブル６２４内の命令に通知される。リタイア待ち行列６２６には、例外を起こしたか否かも含めて、命令の実行の完了が通知される。完了した命令は、プログラム順序で（待ち行列の先頭から）リタイア待ち行列６２６から除去される。リタイア時、命令が例外を起こさなかった場合、リタイアされる命令の結果が入ったアーキテクテッド・レジスタ名がレジスタ・ファイル６１１内の物理レジスタを指すようにイン・オーダ・マップ・テーブル６２８が更新され、イン・オーダ・マップ・テーブル６２８内の前のレジスタ名が空きレジスタ待ち行列６２２に返される。
【００６８】
一方、命令が例外を起こした場合、プログラムの制御がリタイア待ち行列６２６からリタイアされる命令のアドレスに設定される。さらに、リタイア待ち行列６２６がクリア（フラッシュ）され、したがって、リタイアされていないすべての命令が取り消される。さらに、レジスタ・マップ・テーブル６２０が、イン・オーダ・マップ・テーブル６２８の内容に設定され、イン・オーダ・マップ・テーブル６２８内にないレジスタは空きレジスタ待ち行列６２２に加えられる。
【００６９】
上記の構成要素に加えて、スーパスカラ・プロセッサは、分岐の結果を予測する分岐履歴テーブルなど、他の構成要素も含むことができる。
【００７０】
本発明によると、（図６に示すような）前のロード命令を基準にしたロード命令のリオーダをサポートする従来のスーパスカラ・プロセッサは、以下の機構によって増強される。
Ａ．ロード動作およびストア動作を検出する第１の機構（明示的ロード動作またはストア動作、またはＣＩＳＣ命令セットに典型的に見られるようにスタック・ポインタまたはフレーム・ポインタを使用してメモリを参照するその他の動作）。
Ｂ．ロード動作またはストア動作を内部レジスタへの参照に変換する第２の機構。
Ｃ．（スタック・ポインタまたはフレーム・ポインタを介してメモリをアドレス指定しない）他のロード命令がプロセッサ・スタックを参照するか否かを検出し、値を命令に供給する第３の機構。
Ｄ．別のプロセッサのスタック領域へのメモリ参照を検出し、値を取り出す第４の機構。
【００７１】
さらに、上記の機構４は、現在リネーム・レジスタに格納されているすべてのスタック参照を強制的にプロセッサ・メモリに入れるように拡張することが好ましい。これは、図５のステップ５２４で、すべてのスタック参照をプロセッサ・メモリにイン・オーダで記録するメモリ書込み命令を命令ストリームに入れれば特に簡単である。
【００７２】
本発明が提供する機構は、図６に示す従来のアウト・オブ・オーダ・プロセッサで使用可能な機構と共に、以下のように使用される。メモリ動作を検出する第１の機構は、レジスタ・マップ・テーブル６２０で実施される。メモリ動作がスタック参照を参照する場合、第２の機構を使用して、リネーム・レジスタに対する参照に変換される。スタック参照のためのリネーム・レジスタは、汎用レジスタに使用されるものと共用するか、または、別個のプロセッサ資源として実施することができる。
【００７３】
第３および第４の機構は、メモリ・ユニット６０５およびハイブリッド構成に従ったシステム・ソフトウェアで実施される。
【００７４】
汎用レジスタ・ベースのメモリ・アクセスとローカル・スタック参照との衝突を検出する第３の機構は、プロセッサ・スタックを参照するＴＬＢ項目をマークすることによって実施されることが好ましい。この実施形態では、汎用レジスタを使用したこのようなページへの参照によって、プロセッサはすべての投機状態を廃棄し、動作をイン・オーダで行う。この実施形態によると、スタック参照のイン・オーダ値は、プログラム順に挿入されたストア命令によってプロセッサ・メモリに格納されている（図５のステップ５２４）。その後、処理は現行の命令に続く命令から続行する。
【００７５】
第４の機構は、リモート・プロセッサ内のプログラム・スタックとして使用される記憶場所のためにページ変換をロードしないことによって実施される。その結果、リモート・プロセッサ上のスタック場所に対する参照が例外を起こし、その時に、システム・ソフトウェアがリモート・プロセッサのスタック領域に対するメモリ読取り要求をそのプロセッサと同期させることができる。
【００７６】
本発明の例示の実施形態によると、これは、ソフトウェアで、リモート・プロセッサ上で実行されているオペレーティング・システム・カーネルに要求を送ることによって行われる。本発明の他の例示の実施形態によると、この要求と、整合性を保証するのに必要な処置は、ハードウェアで行われる。
【００７７】
図３、図４、および図５のそれぞれステップ３１８、４１８、および５１８の整合性維持機構について、以下に簡単に説明する。イン・オーダ・ストア動作は、対応するアドレスからのロード動作を行うことによって（図５の任意選択ステップ５２４で）行うことができる。イン・オーダ・ストア動作をスタック参照のために行わない場合、整合性維持機構の一実施態様は、すべてのスタック・リネーム・レジスタをそれに対応するスタック場所に強制する。これは、別個の機構として、または、アウト・オブ・オーダ動作をすべて廃棄する図６の機構４を起動することによって実施することができ、機構４は、すべてのスタック・リネーム場所をメモリとするように拡張されていることが好ましい。他の実施形態では、ローカル・プロセッサ・スタックに対するロード参照を、リネーム・レジスタから直接バイパスさせることもできる。
【００７８】
複数の値がある場合、現行ロード動作の前に書き込まれた最後の値を図３および図４のそれぞれステップ３１８および４１８で取り出さなければならない。これを行う１つの方法は、現行ロード動作に続くすべての命令を廃棄することである。
【００７９】
ストア動作のための整合性維持機構は、図の機構４を起動することによってすべてのアウト・オブ・オーダ状態を廃棄する処理を含むことができる。機構４は、すべてのアウト・オブ・オーダ動作を廃棄し、すべてのスタック・リネーム場所をメモリにするように拡張することができることが好ましい。実行が再開されると、図３のステップ３１６または図４のステップ４２６によって、変更された値がメモリからロードされる。
【００８０】
スタック・ロードおよびストア動作が異なるサイズのデータ・タイプを参照する場合は特に注意が必要である。ロード動作が、ストア動作によって供給されるデータ・ビットのサブセットを参照する場合、それらのデータ・ビットは単純な方式で取り出すことができる。ロード動作によって参照されるデータが、１つまたは複数のスタック・リネーム・レジスタおよび場合によってはプロセッサ・メイン・メモリに入っている場合、より複雑なデータ収集が必要である。
【００８１】
本発明の一実施形態によると、少なくとも重複するレジスタをすべてメイン・メモリに書き込み、メモリ読取り動作を行う。これは、図５のステップ５２４でメモリ書込み命令を命令ストリームに入れて、すべてのスタック参照をプロセッサ・メモリにイン・オーダで記録すれば特に簡単である。
【００８２】
本発明の他の実施形態によると、プロセッサはすべての投機状態を廃棄し、すべてのスタック参照を強制的にメモリに入れ、メモリ・ロード動作をイン・オーダで行う。この場合も、これは、図５のステップ５２４でメモリ書込み命令を命令ストリームに入れて、すべてのスタック参照をプロセッサ・メモリにイン・オーダで記録すれば特に簡単である。
【００８３】
プロセッサ・リネーム機構がリネーム・レジスタを使い果たした場合、保留命令内に参照がないリネーム・レジスタを再使用し、その内容をプロセッサ・メモリに書き込むことができる。図５のステップ５２４でイン・オーダ・ストアを挿入しなかった場合、これには、リネーム・レジスタによってストアされた値をメモリに書き込む必要がある場合がある。
【００８４】
最適化された実施形態では、予測子を使用して、図４のステップ４２４および図５のステップ５２０で、どのスタック参照をプロセッサ・レジスタにリネームするかを決定し、スタック参照に割り振られるレジスタの数を減らす。プロセッサ・レジスタで割り振られていないスタック参照は、メイン・メモリへのロード命令およびストア命令を使用することによって行われる。
【００８５】
本発明の一実施形態によると、リネーム・レジスタをプロセッサ・レジスタとスタック参照のリネームのために共用することができる。本発明の他の実施形態によると、これらは別個の資源である。
【００８６】
最適化された実施形態によると、スタック参照のリネームを、コピー動作の排除と組み合わせることにより、クリティカル・パスを短縮することができる。
【００８７】
一実施形態によると、「スタックポインタ値＋変位」のためのシンボリック名を使用してスタック参照を名前指定する。この場合、スタック・ポインタの内容が変更されるときに名前の同期化が必要である。また、フレーム・ポインタとスタック・ポインタの間の距離を使用して、ＦＰ関係の参照をＳＰ関係の参照に変換する。
【００８８】
他の実施形態によると、アドレス（たとえば有効アドレス、仮想アドレス、または物理アドレス）を使用して、スタック・ポインタを名前指定する。最適化された実施形態では、スタック・ポインタ（および任意選択によりフレーム・ポインタ、引数ポインタなど）を、リネーム・ユニットでシャドウイングし、フェッチする命令ストリームと同期して投機的に調整する。これにより、レジスタ・ファイルに必要なメモリ・ポートの数が削減され、リネーム時により積極的な投機が可能になる。
【００８９】
一実施形態によると、ローカル・スタックへのアクセスのための整合性維持動作は、ハードウェアで、リネームされた各スタック参照をアドレス情報と関連づけ、リネームされたスタック参照の検索を行って、要求されたデータがリネーム・レジスタと実際の記憶場所のいずれに入っているかを判断することによって実施される。他の実施形態によると、これは、ソフトウェアのみを使用して実施される。すなわち、汎用レジスタを使用するスタック領域に対する参照が例外を生じさせ、リネームされた値をソフトウェアによって現行の要求と同期させる。
【００９０】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００９１】
（１）コンピュータ処理システムにおいてスタック場所に対するメモリ参照をリネームする方法であって、
アーキテクチャ的に定義されたスタック・アクセス方法を使用するスタック参照を検出するステップと、
前記スタック参照をプロセッサ内部レジスタに対する参照に置き換えるステップとを含む方法。
（２）前記プロセッサ内部レジスタと前記コンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップをさらに含む、上記（１）に記載の方法。
（３）前記同期化ステップが、書込みスタック参照であるすべてのスタック参照のためのイン・オーダ書込み動作を挿入するステップを含む、上記（２）に記載の方法。
（４）アーキテクチャ的に定義されたスタック・アクセス方法を使用しないスタック参照のための整合性維持動作を実行するステップをさらに含む、上記（１）に記載の方法。
（５）整合性維持動作を実行する前記ステップが、値を、所与のプロセッサ内部レジスタから、スタック領域を参照しアーキテクチャ的に定義されたスタック・アクセス方法を使用しないロード動作に、バイパスするステップを含む、上記（４）に記載の方法。
（６）前記プロセッサ内部レジスタと前記コンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップをさらに含み、整合性維持動作を実行する前記ステップが、前記同期化ステップの実行時に前記スタック参照のためのイン・オーダ値を前記メイン・メモリから回復するステップを含む、上記（４）に記載の方法。
（７）前記スタック参照が書込みスタック参照である場合、前記イン・オーダ値が、前記スタック参照に対応する命令を含む命令ストリームに挿入されたイン・オーダ書込み動作によって、前記メイン・メモリに書き込まれる、上記（６）に記載の方法。
（８）アーキテクチャ的に定義された前記スタック・アクセス方法を使用しないロード動作に応答して、前記イン・オーダ値を前記メイン・メモリに書き込むステップをさらに含む、上記（６）に記載の方法。
（９）整合性維持動作を実行する前記ステップが、
前記システムのプロセッサのすべてのアウト・オブ・オーダ状態を廃棄するステップと、
前記プロセッサ内部レジスタと前記コンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップと、
アーキテクチャ的に定義された前記スタック・アクセス方法を使用しないストア動作が行われた後に実行を再開するステップとを含む、上記（４）に記載の方法。
（１０）アーキテクチャ的に定義された前記スタック・アクセス方法が、スタック・ポインタとフレーム・ポインタと引数ポインタとのうちの少なくとも１つを使用するメモリ・アクセスを含む、上記（１）に記載の方法。
（１１）アーキテクチャ的に定義されたスタック・アクセス方法が、プッシュ、ポップ、およびその他のスタック操作動作を含む、上記（１）に記載の方法。
（１２）  コンピュータ処理システムにおいてスタック場所に対するメモリ参照をリネームする方法であって、
ロード命令が、スタック場所にアクセスするためにアーキテクチャ的に定義されたレジスタを使用してローカル・スタック内の場所を参照するか否かを判断するステップと、
前記ロード命令がアーキテクチャ的に定義された前記レジスタを使用して前記場所を参照する場合、前記ローカル・スタック内の前記参照された場所のためのリネーム・レジスタが存在するか否かを判断するステップと、
前記リネーム・レジスタが存在する場合、前記場所に対する前記参照を前記リネーム・レジスタに対する参照に置き換えるステップとを含む方法。
（１３）アーキテクチャ的に定義された前記レジスタがスタック場所にアクセスするためのポインタに対応する、上記（１２）に記載の方法。
（１４）前記スタック場所にアクセスするための前記ポインタが、スタック・ポインタとフレーム・ポインタと引数ポインタとのうちの１つである、上記（１３）に記載の方法。
（１５）アーキテクチャ的に定義された前記スタック・アクセス方法が、プッシュ、ポップ、およびその他のスタック操作動作を含む、上記（１２）に記載の方法。
（１６）前記リネーム・レジスタが存在するか否かを判断する前記ステップが、前記場所のシンボリック・アドレスと実アドレスとのうちの１つを計算するステップを含む、上記（１２）に記載の方法。
（１７）前記リネーム・レジスタが存在するか否かを判断する前記ステップが、デコード段階、アドレス生成段階、およびメモリ・アクセス段階のうちの１つの段階で行われる、上記（１２）に記載の方法。
（１８）前記リネーム・レジスタが存在しない場合、前記システムのメイン・メモリとキャッシュとのうちの１つから前記ロード命令を行うステップをさらに含む、上記（１２）に記載の方法。
（１９）前記ロード命令がアーキテクチャ的に定義された前記レジスタを使用して前記場所を参照しない場合、前記ロード命令が、他のレジスタを使用してローカル・スタックを含むいずれかのスタック内の場所を参照するか否かを判断するステップをさらに含む、上記（１２）に記載の方法。
（２０）前記ロード命令が前記他のレジスタを使用して前記場所を参照するか否かを判断する前記ステップが、前記ロード命令が前記他のレジスタを使用して前記場所を参照する場合に、前記ローカル・スタック内のページの変換索引バッファ（ＴＬＢ）項目を、スタック参照を含むものとしてマークするステップを含む、上記（１９）に記載の方法。
（２１）前記ロード命令が前記他のレジスタを使用して前記場所を参照しない場合、前記システムのメイン・メモリとキャッシュとのうちの１つから前記ロード命令を実行するステップをさらに含む、上記（１９）に記載の方法。
（２２）前記ロード命令が前記他のレジスタを使用して前記場所を参照する場合、整合性維持機構を実行して前記スタック領域から前記ロード命令を実行するステップをさらに含む、上記（１９）に記載の方法。
（２３）前記リネーム・レジスタが存在しない場合、前記場所のためのリネーム・レジスタを割り振るステップをさらに含む、上記（１２）に記載の方法。
（２４）前記リネーム・レジスタの割振り時に、前記システムのプロセッサから前記割り振られたリネーム・レジスタに前記場所をロードする動作を、前記ロード命令を含む命令ストリームに挿入するステップをさらに含む、上記（２３）に記載の方法。
（２５）前記動作の挿入時に、前記場所に対する前記参照を前記割り振られたリネーム・レジスタに対する参照によって置き換えるステップをさらに含む、上記（２４）に記載の方法。
（２６）コンピュータ処理システムにおいてスタック場所に対するメモリ参照をリネームする方法であって、
ストア命令が、スタック場所にアクセスするためにアーキテクチャ的に定義されたレジスタを使用してローカル・スタック内の場所を参照するか否かを判断するステップと、
前記ストア命令がアーキテクチャ的に定義された前記レジスタを使用して前記場所を参照する場合、前記場所のためにリネーム・レジスタを割り振るステップと、
前記場所に対する前記参照を前記リネーム・レジスタに対する参照によって置き換えるステップとを含む方法。
（２７）前記場所に対する前記参照を前記リネーム・レジスタに対する前記参照に置き換えたときに、前記リネーム・レジスタから前記システムのメイン・メモリに前記場所をストアする動作を、前記ストア命令を含む命令ストリームに挿入するステップをさらに含む、上記（２６）に記載の方法。
（２８）前記ストア命令がアーキテクチャ的に定義された前記レジスタを使用して前記場所を参照しない場合、前記ストア命令が他のレジスタを使用して前記ローカル・スタックを含む任意のスタック内の場所を参照するか否かを判断するステップをさらに含む、上記（２６）に記載の方法。
（２９）前記ストア命令が前記他のレジスタを使用して前記場所を参照しない場合、前記ストア命令を前記システムのメイン・メモリとキャッシュのうちのいずれか１つから実行するステップをさらに含む、上記（２８）に記載の方法。
（３０）前記ストア命令が前記他のレジスタを使用して前記場所を参照する場合、整合性維持機構を実行して前記スタック領域への前記ストア命令を実行するステップをさらに含む、上記（２８）に記載の方法。
（３１）コンピュータ処理システムにおいてスタック場所に対するメモリ参照をリネームする方法ステップを実行する、機械によって実行可能な命令のプログラムを有形に実施する機械可読プログラム記憶装置であって、前記方法ステップは、
アーキテクチャ的に定義されたスタック・アクセス方法を使用するスタック参照を検出するステップと、
前記スタック参照をプロセッサ内部レジスタに対する参照に置き換えるステップとを含むプログラム記憶装置。
（３２）前記プロセッサ内部レジスタと前記コンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップをさらに含む、上記（３１）に記載のプログラム記憶装置。
（３３）前記同期化ステップが、書込みスタック参照であるすべてのスタック参照のためのイン・オーダ書込み動作を挿入するステップを含む、上記（３２）に記載のプログラム記憶装置。
（３４）アーキテクチャ的に定義されたスタック・アクセス方法を使用しないスタック参照のための整合性維持動作を実行するステップをさらに含む、上記（３１）に記載のプログラム記憶装置。
（３５）整合性維持動作を実行する前記ステップが、所与のプロセッサ内部レジスタから値を、スタック領域を参照し、アーキテクチャ的に定義されたスタック・アクセス方法を使用しないロード動作にバイパスするステップを含む、上記（３４）に記載のプログラム記憶装置。
（３６）前記プロセッサ内部レジスタと前記コンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップをさらに含み、整合性維持動作を実行する前記ステップが、前記同期化ステップの実行時に前記スタック参照のためのイン・オーダ値を前記メイン・メモリから回復するステップを含む、上記（３４）に記載のプログラム記憶装置。
（３７）前記スタック参照が書込みスタック参照である場合、前記イン・オーダ値が前記スタック参照に対応する命令を含む命令ストリームに挿入されたイン・オーダ書込み動作によって前記メイン・メモリに書き込まれる、上記（３６）に記載のプログラム記憶装置。
（３８）アーキテクチャ的に定義された前記スタック・アクセス方法を使用しないロード動作に応答して、前記イン・オーダ値を前記メイン・メモリに書き込むステップをさらに含む、上記（３６）に記載のプログラム記憶装置。
（３９）整合性維持動作を実行する前記ステップが、
前記システムのプロセッサのすべてのアウト・オブ・オーダ状態を廃棄するステップと、
前記プロセッサ内部レジスタと前記コンピュータ処理システムのメイン・メモリとの間のアーキテクテッド状態を同期化するステップと、
アーキテクチャ的に定義された前記スタック・アクセス方法を使用しないストア動作が行われた後に実行を再開するステップとを含む、上記（３４）に記載のプログラム記憶装置。
【図面の簡単な説明】
【図１】従来の技術によるコンピュータ・プログラムの典型的なメモリ・レイアウトを示す図である。
【図２】本発明の例示の実施形態による、単一命令の初期処理を行う方法を示す流れ図である。
【図３】本発明の例示の実施形態による、ロード動作の処理を示す流れ図である。
【図４】本発明の他の例示の実施形態による、ロード動作の処理を示す流れ図である。
【図５】本発明の例示の実施形態によるストア動作の処理を示す流れ図である。
【図６】本発明が適用されるスーパスカラ・アウト・オブ・オーダ・プロセッサを示すブロック図である。
【符号の説明】
６００  プロセッサ・ユニット
６０１  メモリ・サブシステム
６０２  データ・キャッシュ
６０３  命令待ち行列
６０４  命令キャッシュ
６０５  メモリ・ユニット
６０７  機能ユニット
６０９  分岐ユニット
６１１  レジスタ・ファイル
６２０  レジスタ・マップ・テーブル
６２２  空きレジスタ待ち行列
６２４  ディスパッチ・テーブル
６２６  リタイア待ち行列
６２８  イン・オーダ・マップ・テーブル
【図１】
0003564072.tif 000003
【図２】
0003564072.tif 000004
【図３】
0003564072.tif 000005
【図４】
0003564072.tif 000006
【図５】
0003564072.tif 000007
【図６】
0003564072.tif 000008