(57)【要約】【課題】一般に、命令スケジューリング後に新規命令を配置すると、資源管理状態に変化が生じる。動的資源管理機能を備えている場合は、ＶＬＩＷ等の動的資源管理機能を持たないハードウェアをターゲットとするコンパイラの場合は、大きな問題が生じる。従って、一般的にＶＬＩＷコンパイラにおいては、最終的な命令スケジューリング処理後に、新規命令を挿入するｐｒｅｆｅｔｃｈ命令の挿入が困難である。【解決手段】上記課題を解決するために、コンパイラは、命令スケジューリング処理が生成したスケジューリングの情報を利用する、既スケジュール命令を変更しないｐｒｅｆｅｔｃｈ命令挿入処理を設ける。特に、クラスタ構成ＶＬＩＷアーキテクチャをターゲットとするコンパイラにおいては、命令のクラスタ配置を活用することで、既スケジュール命令を変更しないｐｒｅｆｅｔｃｈ命令挿入処理を容易に実現できる。【選択図】  図３
2004326376.tif 000002
【特許請求の範囲】
【請求項１】
メモリ上のデータをデータキャッシュに転送するプリフェッチ命令を備えるアーキテクチャをターゲットとするコンパイル方法であって、
予め定まっているターゲットアーキテクチャの命令配置制約のもとで、プログラムを構成する命令群を配置する命令スケジューリングステップと、
命令スケジューリング後の命令列に対してプリフェッチ命令を挿入するプリフェッチ挿入ステップを備えるコンパイル方法において、
上記プリフェッチ命令挿入ステップが、上記命令スケジューリングステップの配置した既スケジュール命令を変更することなくプリフェッチ命令を挿入することを特徴とするＶＬＩＷ向けプリフェッチ命令生成方法。
【請求項２】
請求項１のコンパイル方法であって、
上記ターゲットアーキテクチャが、独立した演算手段と記憶手段を備える処理構成単位であるクラスタを有するクラスタ構成アーキテクチャである場合において、
上記命令スケジューリングステップが、命令をクラスタに配分するクラスタリング処理を行うステップを備え、
上記プリフェッチ挿入ステップが命令のクラスタリング結果を利用することを特徴とするＶＬＩＷ向けプリフェッチ命令生成方法。
【請求項３】
請求項２のコンパイル方法であって、
上記プリフェッチ挿入ステップが利用する命令のクラスタリング結果が、命令スケジュールステップが配置したロード命令のクラスタ位置であることを特徴とするＶＬＩＷ向けプリフェッチ命令生成方法。
【請求項４】
請求項３のコンパイル方法であって、
上記プリフェッチ挿入ステップが配置するプリフェッチ命令のクラスタ位置が、命令スケジュールステップが配置したロード命令のクラスタ位置と異なることを特徴とするＶＬＩＷ向けプリフェッチ命令生成方法。
【請求項５】
請求項２のコンパイル方法であって、
上記プリフェッチ挿入ステップがプリフェッチ命令挿入位置を算出する挿入位置算出ステップと、プリフェッチ命令を挿入するステップを備えるとき、挿入位置算出ステップがロード命令に対する最適なプリフェッチサイクル数分のみ先行する位置を挿入候補として選択することを特徴とするＶＬＩＷ向けプリフェッチ命令生成方法。
【請求項６】
請求項５のコンパイル方法であって、
上記プリフェッチ挿入ステップが利用する命令のクラスタリング結果が、命令スケジュールステップが配置したロード命令のクラスタ位置であることを特徴とするＶＬＩＷ向けプリフェッチ命令生成方法。
【請求項７】
請求項５のコンパイル方法であって、
上記プリフェッチ挿入ステップが配置するプリフェッチ命令のクラスタ位置が、命令スケジュールステップが配置したロード命令のクラスタ位置と異なることを特徴とするＶＬＩＷ向けプリフェッチ命令生成方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はコンパイラのコンパイル方法に係わり、特に命令スケジューリング機構を持つコンパイル方法に関する。
【０００２】
【従来の技術】
プログラムを機械命令で実行する際には、機械語を所定の順序に並べ替えて実行するのが一般的である。この命令の並べ替え処理のことを、命令スケジューリングと呼ぶ。高級言語で記述されたプログラムを機械命令に変換するコンパイラにおいても、生成する機械語を所定の順序に並べ替えて生成するのが一般的である。
【０００３】
コンパイラで命令スケジューリングを行うためには、個別の命令が使用するハードウェア資源の使用状況を管理する必要がある。例えば、ロード命令を実行する際にはデータキャッシュにロードするデータが存在するか否かを調べ、存在しない場合はメモリからデータキャッシュへとデータを転送する必要がある。そのため、ロード命令を実行する際にはデータキャッシュや、データキャッシュとメモリの転送経路が（他の命令により）使用中でないことを確かめる必要がある。もし使用中であれば、使用可能になるまで実行を中断する必要があるためである。このようなハードウェア資源の使用状況の管理を、以降では単に資源管理と呼ぶことにする。
【０００４】
ところで、ＲＩＳＣ等においては、ハードウェアが資源管理の機能を備えており、実行時に資源チェック動的資源管理機能を備えている。これにより、実行時に命令の並べ替えを行う動的命令スケジューリングが可能である。ところが、ＶＬＩＷにおいては、一般的にこの動的資源管理を行なっていないか、あるいは極限られた資源管理のみに限定されている。そこで、資源管理を考慮した命令スケジューリングは全てコンパイラが行うこととなる。以降では、このコンパイラが行なう命令スケジューリングを静的命令スケジューリング、あるいは単に命令スケジューリングと呼ぶことにする。
【０００５】
静的命令スケジューリングは、コンパイル時に静的命令の並べ替えを行うものであり、  ＶＬＩＷ等の（一般的には）動的資源管理機能を持たないハードウェアをターゲットとするコンパイラの場合には、必須の機能である。また、ＶＬＩＷコンパイラの静的命令スケジューリングは、資源管理を厳密に行なう必要がある。命令スケジューリングの正当性はコンパイラにまかせられており、コンパイラが静的命令スケジューリング時に資源競合を発生させてしまうスケジュール結果を生成すると、実行時のリカバリが行なわれないため、実行結果が不正となってしまうからである。
【０００６】
なお、動的資源管理機能を備えたハードウェアに対するＲＩＳＣコンパイラでも、処理性能向上のために、静的命令スケジューリングを行うのが一般的である。従って、命令スケジューリング自体はコンパイラにとって一般的な処理である。但し、動的資源管理機能がある場合は、ＶＬＩＷの場合ほどの厳密な資源管理は要求されない。
【０００７】
一般に、命令スケジューリング後に新規命令を配置すると、資源管理状態に変化が生じる。動的資源管理機能を備えている場合は、処理性能のみの問題なので、さほど問題はないが、ＶＬＩＷ等の動的資源管理機能を持たないハードウェアをターゲットとするコンパイラの場合は、大きな問題が生じる。他の既スケジュール命令に影響がある場合には再スケジューリングが必要となる場合もある。従って、一般的にＶＬＩＷコンパイラにおいては、最終的な命令スケジューリング処理後に、新規命令を挿入するのは困難である。
【０００８】
コンパイラにおける最適化処理の一つに、ｐｒｅｆｅｔｃｈ命令の挿入がある。ｐｒｅｆｅｔｃｈ命令は、データを予めメモリからデータキャッシュへと転送するものである。データをキャッシュへと転送するｐｒｅｆｅｔｃｈ命令を実際のｌｏａｄ命令の前に発行するのが、ｐｒｅｆｅｔｃｈ命令の挿入である。メモリからキャッシュへの転送のコストが大きいため、効果的な最適化手法として知られている。
【０００９】
ｐｒｅｆｅｔｃｈ命令挿入の効果は、どのｌｏａｄ命令に対しどこに挿入するかの判断にかかっている。ｐｒｅｆｅｔｃｈ命令も命令を発行する資源を使用するため、むやみに発行すると性能低下を招く。また、ｌｏａｄ命令との距離が離れすぎると、ｐｒｅｆｅｔｃｈ命令からｌｏａｄ命令の間でデータキャッシュの状態が変化する可能性が高くなり、ｐｒｅｆｅｔｃｈの効果が期待できなくなる。このｐｒｅｆｅｔｃｈ命令の挿入を行なうためには、予め最終的なスケジューリングに近い状態でｐｒｅｆｅｔｃｈ挿入の可否やｐｒｅｆｅｔｃｈ場所を判断した方がよい。従って、ｐｒｅｆｅｔｃｈ命令の挿入はスケジューリング処理終了後（終了寸前）に行なうのが一般的である。ところが、このｐｒｅｆｅｔｃｈ命令の挿入により、資源の使用状況が変化してしまう可能性がある。従って、一般的にＶＬＩＷコンパイラにおいては、ｐｒｅｆｅｔｃｈ命令の挿入は困難であった。
【００１０】
ところで、コンパイラのターゲットアーキテクチャには、クラスタと呼ばれる構成を備える場合がある。クラスタとは、演算を行う演算器と、演算すべきデータを保持するレジスタ等を一まとまりとして持つもので、複数のクラスタを並列に配置することで、命令並列度向上とスケーラビリティを確保しようとするものである。各クラスタはシステムバス等により結ばれており、命令語レベルでのデータ転送が可能になっているのが普通である。各クラスタは独立性が高く、データキャッシュをクラスタが共有する場合を除き資源管理上も独立性が高い。このようなクラスタ構成は、ＶＬＩＷアーキテクチャに多くみられ、クラスタ構成ＶＬＩＷアーキテクチャと呼ばれている。
【００１１】
クラスタ構成ＶＬＩＷアーキテクチャをターゲットとするコンパイラは、命令スケジューリング時に、逐次命令列を複数クラスタで実行する命令列へと変換する必要がある。この逐次命令列のクラスタへの分割（及び、分割に伴って必要となるクラスタ間データ転送命令の挿入）を、以降ではクラスタリングと呼ぶことにする。クラスタリングは命令スケジューリングの一部であり、クラスタ構成ＶＬＩＷコンパイラでは、命令スケジューリング時にクラスタリング処理も併せて行うのが一般的である。
【００１２】
クラスタ構成ＶＬＩＷにおける命令スケジューリングに関しては、非特許文献１に詳しい。
【００１３】
また、コンパイラのｐｒｅｆｅｔｃｈ挿入処理に関しては、非特許文献２に詳しい。
【００１４】
【非特許文献１】
Ｅｍｒｅ  Ｏｚｅｒ，  Ｓａｎｊｅｅｖ  Ｂａｎｅｒｊｉａ，  Ｔｈｏｍａｓ  Ｍ．  Ｃｏｎｔｅ  ”Ｕｎｉｆｉｅｄ  Ａｓｓｉｇｎ  ａｎｄ  Ｓｃｈｅｄｕｌｅ：Ａ  Ｎｅｗ  Ａｐｐｒｏａｃｈ  ｔｏ  Ｓｃｈｅｄｕｌｉｎｇ  ｆｏｒ  Ｃｌｕｓｔｅｒｅｄ  Ｒｅｇｉｓｔｅｒ  Ｆｉｌｅ  Ｍｉｃｒｏａｒｃｈｉｔｅｃｔｕｒｅ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ３１ｓｔ  Ａｎｎｕａｌ  ＡＣＭ／ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｍｉｃｒｏａｒｃｈｉｔｅｃｔｕｒｅ，  ｐｐ．３０８−３１５，１９９８．
【非特許文献２】
Ｔｏｄｄ  Ｃ．  Ｍｏｗｒｙ，  Ｍｏｎｉｃａ  Ｓ．  Ｌａｍ  ａｎｄ  Ａｎｏｏｐ  Ｇｕｐｔａ  ”Ｄｅｓｉｇｎ  ａｎｄ  Ｅｖａｌｕａｔｉｏｎ  ｏｆ  ａ  Ｃｏｍｐｉｌｅｒ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｐｒｅｆｅｔｃｈｉｎｇ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｆｉｆｔｈ  Ａｒｃｈｉｔｅｃｔｕａｌ  Ｓｕｐｐｏｒｔ  ｆｏｒ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅｓ  ａｎｄ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍｓ（ＡＳＰＬＯＳ  Ｖ），  ｐｐ６２−７３，１９９２．
【００１５】
【発明が解決しようとする課題】
従来技術の項で述べた通り、従来技術においては、ＶＬＩＷ等の動的資源管理機能をもたないアーキテクチャに対するコンパイラにおいて、ｐｒｅｆｅｔｃｈ命令の挿入は困難であるという課題があった。
【００１６】
【課題を解決するための手段】
ｐｒｅｆｅｔｃｈ命令挿入処理において、既スケジュール結果を変更する必要のない場合にのみｐｒｅｆｅｔｃｈ命令を挿入する、再スケジュール不要ｐｒｅｆｅｔｃｈ挿入処理を設ける。その再スケジュール不要ｐｒｅｆｅｔｃｈ挿入処理の挿入場所検査において、資源管理上に変化のない可能性の高い他クラスタの挿入位置を優先して検査する。
【００１７】
これにより、ＶＬＩＷ等の動的資源管理機能のないアーキテクチャに対するコンパイラに対しても、効率的なｐｒｅｆｅｔｃｈ命令挿入処理が実現でき、オブジェクトプログラムの処理性能の向上に寄与する。
【００１８】
【発明の実施の形態】
本発明は、ＶＬＩＷ等の動的資源管理機能をもたないアーキテクチャに対するコンパイラの命令スケジューリング後のｐｒｅｆｅｔｃｈ命令挿入方式に関するものである。
【００１９】
以下では、本発明の１実施例を図面を用いて説明する。
【００２０】
尚、コンパイラの中間語は、同等な命令語の形式で示す。また、複数クラスタでの並列実行状況を明示するため、クラスタ毎の実行命令を縦にならべた形式で表す。
【００２１】
図１は、本発明のコンパイル方法を実施するコンパイラが動作する計算機システムの構成図である。計算機システムは、ＣＰＵ１０１、ディスプレイ装置１０２、キーボード１０３、主記憶装置１０４、外部記憶装置１０５より構成されている。
【００２２】
キーボード１０３より、ユーザからのコンパイラ起動命令を受け付ける。コンパイラ終了メッセージや、エラーメッセージは、ディスプレイ装置１０２に表示される。外部記憶装置１０５には、ソースプログラム１０６とオブジェクトプログラム１０７が格納される。
【００２３】
主記憶装置１０４には、コンパイラ１０８があり、コンパイル過程で必要となる中間語３、命令配置テーブル５が格納される。コンパイル処理は、ＣＰＵ１０１によって、制御される。
【００２４】
図２に本実施例のコンパイラの処理手順を示す。
【００２５】
構文解析２０１では、ソースプログラム１０６を入力として字句構文解析を行ない、中間語３を出力する。
【００２６】
命令スケジューリング処理４は、中間語３を入力とし、逐次命令列を複数クラスタに配置する命令スケジューリング処理を行い、中間語３を出力する。
【００２７】
ｐｒｅｆｅｔｃｈ命令挿入処理２は中間語３を入力とし、ｐｒｅｆｅｔｃｈ命令を挿入した中間語３を出力する。
【００２８】
コード生成処理２０２は、中間語を最終的なオブジェクトプログラム１０７の形式に変換する。
【００２９】
図３は、本発明における再スケジューリング不要型ｐｒｅｆｅｔｃｈ挿入方法の一実施例を示すフローチャート図であり、図２の命令スケジューリング処理４とｐｒｅｆｅｔｃｈ命令挿入処理２の手順を表している。
【００３０】
命令スケジューリング処理４は、未処理中間語命令ｏｐが存在する限り（ステップ４０１）、そのｏｐの配置クラスタを決定するステップ４０２を行ない、ステップ４０３でｏｐに対する命令スケジューリングの結果を確定させる。
【００３１】
命令スケジューリング処理４の実行後ｐｒｅｆｅｔｃｈ命令挿入処理２を行う。
【００３２】
このｐｒｅｆｅｔｃｈ命令挿入処理２は、未処理ロード命令ｌｄの存在判定を行うステップ３０１、ｌｄがｐｒｅｆｅｔｃｈ命令生成対象ノードか否かを判定するステップ３０２、ｌｄに対するｐｒｅｆｅｔｃｈ命令挿入処理の各処理からなる。
【００３３】
ステップ３０１で中間語を走査し、ｐｒｅｆｅｔｃｈ命令挿入の対象となるロード命令を検出し、さらにロード命令がｐｒｅｆｅｔｃｈ生成対象かどうかをステップ３０２で判定し、Ｙｅｓの場合はステップ３０３以降のｐｒｅｆｅｔｃｈ挿入処理を行なう。
【００３４】
Ｎｏの場合は、ステップ３０１に戻り、次のロード命令の走査を続行し、未処理ロード命令が存在しなくなったら処理を終了する。
【００３５】
ｐｒｅｆｅｔｃｈ命令挿入処理は、ｌｄのクラスタ番号を取得するステップ３０３、ｌｄのｐｒｅｆｅｔｃｈ位置ｐｐを算出するステップ３０４、ｐｐに未処理な命令挿入可能クラスタｐｐｃが存在するか否かを判定するステップ３０５、ステップ３０５で検出したクラスタｐｐｃとステップ３０３で設定したクラスタｌｄｃが一致しないことを判定するステップ３０６、ｐｐのクラスタ位置ｐｐｃにｐｒｅｆｅｔｃｈ命令を挿入するステップ３０７からなる。
【００３６】
ステップ３０３、ステップ３０４の実行後、ステップ３０５でｐｒｅｆｅｔｃｈ挿入位置での挿入可能クラスタを走査し、挿入可能なクラスタが、ステップ３０３で設定したロード命令のクラスタと一致するか否かを判定後、一致しないときのみステップ３０７で実際のｐｒｅｆｅｔｃｈ命令の挿入を行なう。
【００３７】
尚、ステップ３０３で設定しているロード命令のクラスタｌｄｃは、ステップ４０２で決定された配置クラスタにより決定されたものである。
【００３８】
本実施例は、命令のクラスタ分割の結果を利用したｐｒｅｆｅｔｃｈ挿入方法であるので、命令スケジューリング処理との関係が深い。図３で示した処理の流れでは、命令スケジューリングに関しては、クラスタ配置位置を決定しそのクラスタに配置することのみ示したが、ここで若干補足しておく。命令スケジューリングは、全中間語を順にスケジューリングするのではなく、特定の手順で中間語をスケジューリング単位に分割し、そのスケジューリング単位中間語をスケジューリングするのが一般的である。スケジューリング中間語処理単位をどのようにするかは、本発明においては本質的ではないので省略し、単に中間語を逐次走査して処理する形式とした。また、本実施例は分散レジスタファイル型のクラスタ構成をとるＶＬＩＷマシンを対象としており、各クラスタ変数はそれぞれ独立したレジスタに割り当てられるが、スタックポインタＳＰはどのクラスタでも共通して使用可能なものとする。
【００３９】
図４は、図３で示した再スケジューリング不要型ｐｒｅｆｅｔｃｈ挿入処理の入出力となる中間語やテーブル類の関係を示した処理構成図である。
【００４０】
命令スケジューリング処理４は、逐次実行型の中間語であるスケジューリング前中間語３１を入力とし、配置したクラスタの情報含む命令配置テーブル５を生成するとともに、複数クラスタに命令を配置した命令スケジューリング後の並列化中間語３２を生成する。
【００４１】
ｐｒｅｆｅｔｃｈ挿入処理２は、配置されたクラスタ情報を含む命令配置テーブル５と命令スケジューリング後中間語３２と命令配置テーブル５を入力とし、スケジューリング後中間語２２にｐｒｅｆｅｔｃｈ命令を挿入したｐｒｅｆｅｔｃｈ挿入後中間語３３を生成する。
【００４２】
次に、具体的な適用例の説明のため、処理対象たる中間語の例を挙げておく。
【００４３】
本実施例は、複数クラスタを持つアーキテクチャに対するコンパイラであり、その並列化中間語３３は、クラスタを表現できる形式が必要となる。本実施例の説明では、各クラスタに配置された命令が同一サイクルに並列に実行されることを表現するため、実行サイクルを縦軸にとり、そのサイクルで実行する命令（簡単のため、１サイクル当り各クラスタで１命令のみ実行可能とする）を横に配置することにする。また、中間語がクラスタを意識する必要があるのは、命令スケジューリング後中間語３３においてであり、それ以前の中間語（３１、３２）では特に意識する必要はない。
【００４４】
図５は、本発明の一実施例の説明のための中間語構成例であり、全命令が逐次実行を想定した逐次中間語列となっている。
【００４５】
図６は、本発明の一実施例の説明のための中間語構成例であり、各命令が複数クラスタに配置された並列化中間語列となっている。図６は、図５の中間語を命令スケジューリング処理により並列配置した例である。例えば、１０１行では、クラスタ０で命令「ｙ０  ＝  ０」、クラスタ１で命令「ｙ１  ＝  １」をそれぞれ実行することを表している。１０２行のクラスタ２、クラスタ３のように空白になっている個所はなにも命令を実行しないこと（ＮＯＰ）を示している。以降では、これらクラスタに配置された個別命令を示すため、行番号とクラスタ番号を組み合わせて、配置位置を（行番号，クラスタ番号）で示すことにする。例えば、図６の配置位置（１０１，０）には命令「ｙ０＝０」が配置され、配置位置（１０２，２）はＮＯＰである。
【００４６】
図６において、ロード命令は配置位置（１０４，０）、（１０５，０）にある「ｘ１＝ｌｄ（ｓｐ，０）」「ｘ２＝ｌｄ（ｓｐ，４）」である。これらは、スタックポインタＳＰをベースとし、オフセット０からｘ１を、オフセット４からｘ２をロードすることを示している。
【００４７】
図７は、本発明の一実施例の説明のための並列化中間語構成例であり、図６の中間語に対し、ｐｒｅｆｅｔｃｈ命令を挿入した結果のｐｒｅｆｅｔｃｈ挿入後中間語の構成例である。ｐｒｅｆｅｔｃｈ命令は、配置位置（２０２，２）にある「ｐｆ（ｓｐ，４）」であり、これは配置位置（２０５，０）にあるロード命令「ｘ２  ＝  ｌｄ（ｓｐ，４）」に対応したｐｒｅｆｅｔｃｈ命令を示している。
【００４８】
図８は、図５の例に対して求めた命令配置テーブル５の構成例である。
【００４９】
命令配置テーブルは、中間語中に出現する命令ごとに、エントリが作成される。
【００５０】
各エントリは、命令番号欄５１、行番号欄５２、命令種別欄５３、配置位置欄５４、配置クラスタ番号欄５５で構成される。
【００５１】
命令番号欄５１には、命令配置のエントリ番号、行番号欄５２には、対応する命令の行番号が格納される。
【００５２】
命令種別欄５３は、対応する命令の命令種別が格納される。図８の例では、「ｙ０＝０」といった単純代入命令は「＝」、「ｙ０＝ｙ０＋４」といった加算命令は「＋」で示してある。また、ロード命令は「ｌｄ」である。
【００５３】
配置位置欄５４は、命令が配置されたサイクル位置が格納される。サイクル位置はこのスケジュール単位の先頭から何サイクル目に配置されたかを示している。図８は図６の命令スケジューリング後中間語３２に対応した命令配置を示しており、スケジュール単位の先頭は行番号１０１となっている。この行番号１０１から何サイクル後であるかをサイクル数で示している。
【００５４】
配置クラスタ番号欄５５は、当該エントリに対応する命令が配置されたクラスタ番号を格納する。配置位置欄５４と配置クラスタ番号欄５５は、並列化中間語の配置位置を示しており、例えば、エントリ５０１は配置位置（１０１，０）にある命令「ｙ０＝０」に対応している。
【００５５】
ところで、図７は、図８で示した命令配置テーブル５と図６で示した命令スケジューリング後中間語例３２を入力とし、図３のステップ３０１以下の手順により生成したｐｒｅｆｅｔｃ挿入後中間語例となっている。ここで、図３の手順と図７の出力結果の関係を簡単に説明する。図３のステップ３０２でｐｒｅｆｅｔｃｈ対象となるのは、配置位置（１０４，０）  の「ｘ１＝ｌｄ（ｓｐ，０）」と配置位置（１０５，０）の「ｘ２＝ｌｄ（ｓｐ，４）」の２つのロード命令である。
【００５６】
配置位置（１０４，０）ロード命令「ｘ１＝ｌｄ（ｓｐ，０）」に関しては、ステップ３０４のｐｒｅｆｅｔｃｈ挿入位置の算出において、サイクル位置１０１が選ばれる。ところが、サイクル位置１０１は、図６の配置位置（１０１，０）から（１０１，３）に示すように全てのクラスタに命令が配置済みである。ステップ３０５の判定は、サイクル位置１０１の全クラスタで挿入可能ではないと判定される。本実施例は最適なｐｒｅｆｅｔｃｈ位置でのｐｒｅｆｅｔｃｈ挿入のみを試みるものなので、配置位置（１０４，０）のロード命令「ｘ１＝ｌｄ（ｓｐ，０）」に対するｐｒｅｆｅｔｃｈ命令の挿入を行なわず、ステップ３０１に進む。
【００５７】
配置位置（１０５，０）ロード命令「ｘ２＝ｌｄ（ｓｐ，４）」に対してはステップ３０５の判定で、配置位置（１０２，２））に命令が配置されていないため、クラスタ２が選択される。ステップ３０３で設定したロード命令のクラスタｌｄｃ＝クラスタ０、ステップ３０５で選択された命令挿入可能クラスタｐｐｃ＝クラスタ２なので、ステップ３０６の判定をパスし、ステップ３０７で配置位置（２０２，２）にｐｒｅｆｅｔｃｈ命令を挿入する。
【００５８】
以上で本実施例の説明を終え、以下では本実施例の効果について述べる。
【００５９】
図６、図７のような並列中間語は、最終的な機械命令による実行過程を表しており、行の数はそのまま実行サイクル数に対応している。即ち、並列中間語の行数は、オブジェクトプログラムの処理性能を示している。そこで、簡単のため、本実施例では、全ての演算は１サイクルで実行できると仮定することにした。但し、ロード命令に関しては、ロードすべきデータがデータキャッシュに存在した場合は１サイクルで命令が完了するが、存在しない場合はキャッシュにデータが供給されるまで３サイクル要するものとする。キャッシュにデータが存在するか否かはハードウェアが検出し、そのようなロード命令に関してはその３サイクルの間は、全てのプログラム実行が中止される（ストールと呼ぶ）。一方、既にキャッシュにデータが存在した場合は、ストールすることなく１サイクルでロード命令の処理を完了する。ｐｒｅｆｅｔｃｈ命令には３サイクル要するが、３サイクル後にはデータがキャッシュに供給されていることが保障されるので、ストールすることはない。
【００６０】
図６の例では、静的にみた場合は全命令の実行サイクル数は６となるが、実際には（１０４，０）、（１０５，０）のロード命令に対するストールが発生する可能性があり、動的には最大１２（＝６＋３＋３）サイクルかかる可能性がある。
【００６１】
一方、図７の例では、（２０５，０）のロード命令に対しては（２０２，２）でｐｒｅｆｅｔｃｈ命令が発行されているので、ストールすることはない。従って、動的な最大実行サイクル数は９（＝６＋３）サイクルとなり、処理が高速化されていることが分る。このｐｒｅｆｅｔｃｈ命令挿入は再スケジューリングを行なわないため、コンパイル時間の大幅な増大を招くことなく、正確な位置にｐｒｅｆｅｔｃｈ命令を挿入することができる。
【００６２】
本実施例によれば、再スケジュール不要型ｐｒｅｆｅｔｃｈ挿入処理により、実行命令の動的処理速度の向上が可能となり、オブジェクトプログラムの処理性能の向上に寄与する。
【００６３】
【発明の効果】
本発明によれば、コンパイラは、命令スケジューリング処理が生成したスケジューリングの情報をｐｒｅｆｅｔｃｈ命令挿入処理が利用する。ｐｒｅｆｅｔｃｈ命令挿入処理は既スケジュール命令を変更することなくｐｒｅｆｅｔｃｈ命令を挿入するため、コンパイル時間の大幅な増大を招くことなく、正確な位置にｐｒｅｆｅｔｃｈ命令を挿入することができる。
【００６４】
特にクラスタ構成アーキテクチャをターゲットとするコンパイラにおいては、ｐｒｅｆｅｔｃｈ命令挿入処理が利用するスケジューリング情報として、命令のクラスタ配置を活用することで、より効率的なｐｒｅｆｅｃｈ命令挿入が可能となり、オブジェクトプログラムの処理性能の向上に寄与する。
【図面の簡単な説明】
【図１】本発明を実施するコンパイラが稼働する計算機システムの構成図。
【図２】本発明を実施するコンパイラの処理手順を示すフローチャート図。
【図３】コンパイラの命令スケジューリング処理４とｐｒｅｆｅｔｃｈ命令挿入処理２のフローチャート図。
【図４】本発明におけるコンパイラ命令スケジューリング処理４とｐｒｅｆｅｔｃｈ命令挿入処理２の処理構成図。
【図５】中間語の例（命令スケジュール前中間語３１の構成例）。
【図６】中間語の例（命令スケジュール後中間語３２の構成例）。
【図７】中間語の例（ｐｒｅｆｅｔｃｈ命令挿入後中間語３３の構成例）。
【図８】命令配置テーブル５の構成例。
【符号の説明】
…１０１ＣＰＵ、１０２…ディスプレイ装置、１０３…キーボード、１０４…主記憶装置、１０５…外部記憶装置。
【図１】
2004326376.tif 000003
【図２】
2004326376.tif 000004
【図３】
2004326376.tif 000005
【図４】
2004326376.tif 000006
【図５】
2004326376.tif 000007
【図６】
2004326376.tif 000008
【図７】
2004326376.tif 000009
【図８】
2004326376.tif 000010