(57)【特許請求の範囲】
【請求項１】
原始プログラムを変換して記憶した中間テキストに対して、メモリからレジスタへのロード処理命令に対応して先行した実行順序位置に該メモリからデータキャッシュにプリフェッチする命令を挿入して最適化するコンパイル装置であって、
あらかじめ設定された１以上の原始プログラム命令について該原始プログラム命令が変換されて中間テキストに記録される処理名情報の該処理名に対応させて該処理に先行して実行させるプリフェッチ命令を挿入する実行順序位置を中間テキストに記憶された実行経路情報に沿って遡及してカウントして決定する命令数を記憶したプリフェッチ対象処理テーブルと、
上記原始プログラムから変換して記憶した中間テキストの各処理命令について処理名を上記プリフェッチ対象処理テーブルに記憶されたいずれかの処理名との一致を検索し、一致した処理名に対応して該プリフェッチ対象処理テーブルに記憶された遡及する命令数を一時記憶する中間テキスト検索手段と、
上記検索して処理名が一致した中間テキストの処理命令の実行順序位置から上記一時記憶された遡及する命令数に基づいて中間テキストに記憶された実行経路情報に沿ってプログラムの制御の流れをさかのぼり、上記プリフェッチ命令を挿入する実行順序位置を決定するプリフェッチ命令挿入位置最適化手段と、
上記決定した実行順序位置に上記検索して処理名が一致した中間テキストの処理命令がロードするメモリのアドレスを指定したデータキャッシュプリフェッチ命令を挿入するプリフェッチ命令挿入手段と、
を備えることを特徴とするコンパイル装置。
【請求項２】
上記プリフェッチ対象処理テーブルにあらかじめ設定された原始プログラム命令はメモリからレジスタにロードするデータのアドレスを引数として指定するシステム関数であることを特徴とする請求項１記載のコンパイル装置。
【請求項３】
上記プリフェッチ対象処理テーブルにあらかじめ設定された原始プログラム命令はメモリからレジスタにロードするデータのアドレスを引数として指定するユーザ定義関数であることを特徴とする請求項１記載のコンパイル装置。
【請求項４】
上記プリフェッチ対象処理テーブルにあらかじめ設定された原始プログラム命令は手続きおよびユーザ定義関数を記述するプログラムにおけるメモリからレジスタにロードするデータのアドレスを引数として指定するレジスタ復元関数であることを特徴とする請求項１記載のコンパイル装置。
【請求項５】
原始プログラムを変換して記憶した中間テキストに対して、メモリからレジスタへのロード処理命令に対応して先行した実行順序位置に該メモリからデータキャッシュにプリフェッチする命令を挿入して最適化するコンパイル方法であって、
あらかじめ設定された１以上の原始プログラム命令について該原始プログラム命令が変換されて中間テキストに記録される処理名情報の該処理名に対応させて該処理に先行して実行させるプリフェッチ命令を挿入する実行順序位置を中間テキストに記憶された実行経路情報に沿って遡及してカウントして決定する命令数をプリフェッチ対象処理テーブルに記憶手段が記憶するステップ、
上記原始プログラムから変換して記憶した中間テキストの各処理命令について処理名を上記プリフェッチ対象処理テーブルに記憶されたいずれかの処理名との一致を検索手段が検索し、一致した処理名に対応して該プリフェッチ対象処理テーブルに記憶された遡及する命令数を記憶手段が一時記憶する中間テキスト検索ステップ、
上記検索して処理名が一致した中間テキストの処理命令の実行順序位置から上記一時記憶された遡及する命令数に基づいて中間テキストに記憶された実行経路情報に沿ってプログラムの制御の流れをさかのぼり、上記プリフェッチ命令を挿入する実行順序位置を決定手段が決定するプリフェッチ命令挿入位置最適化ステップ、
上記決定した実行順序位置に上記検索して処理名が一致した中間テキストの処理命令がロードするメモリのアドレスを指定したデータキャッシュプリフェッチ命令を挿入手段が挿入するプリフェッチ命令挿入ステップ、
を有するコンパイル方法。
【請求項６】
原始プログラムを変換して記憶した中間テキストに対して、メモリからレジスタへのロード処理命令に対応して先行した実行順序位置に該メモリからデータキャッシュにプリフェッチする命令を挿入して最適化するコンパイラプログラムを記録した記録媒体であって、
コンピュータを、
あらかじめ設定された１以上の原始プログラム命令について該原始プログラム命令が変換されて中間テキストに記録される処理名情報の該処理名に対応させて該処理に先行して実行させるプリフェッチ命令を挿入する実行順序位置を中間テキストに記憶された実行経路情報に沿って遡及してカウントして決定する命令数をプリフェッチ対象処理テーブルに記憶する手段、
上記原始プログラムから変換して記憶した中間テキストの各処理命令について処理名を上記プリフェッチ対象処理テーブルに記憶されたいずれかの処理名との一致を検索し、一致した処理名に対応して該プリフェッチ対象処理テーブルに記憶された遡及する命令数を一時記憶する中間テキスト検索手段、
上記検索して処理名が一致した中間テキストの処理命令の実行順序位置から上記一時記憶された遡及する命令数に基づいて中間テキストに記憶された実行経路情報に沿ってプログラムの制御の流れをさかのぼり、上記プリフェッチ命令を挿入する実行順序位置を決定するプリフェッチ命令挿入位置最適化手段、
上記決定した実行順序位置に上記検索して処理名が一致した中間テキストの処理命令がロードするメモリのアドレスを指定したデータキャッシュプリフェッチ命令を挿入するプリフェッチ命令挿入手段、
として機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は原始プログラムを中間テキストに変換し、変換した中間テキストに対して最適化を行い、機械語を生成するコンパイル装置において、データキャッシュを有効に活用したプログラムを生成して実行時性能を向上するようにしたコンパイル装置に関する。
【０００２】
【従来の技術】
コンピュータの性能は従来より種々の技術的改良により飛躍的に向上してきている。特にその中心であるＣＰＵについても命令実行速度の向上が著しいＲＩＳＣ（Ｒｅｄｕｃｅｄ  Ｉｎｓｔｒｕｃｔｉｏｎ  Ｓｅｔ  Ｃｏｍｐｕｔｅｒ）型アーキテクチャが多く採用されている。一方主記憶装置（メモリ）はＣＰＵに比較してあまり早くなっていない。このような状態のとき、データをメモリからロードしようとすると、メモリから長い時間（ＣＰＵに比べて相対的に）をかけて演算のためのレジスタに格納されるので、その完了を待って短い演算処理時間の後結果が得られることになる。すなわち、高速化されたＣＰＵもメモリにあるデータの処理の大部分をメモリからレジスタへのロード時間待ちのために全体としての性能向上はわずかなものとなってしまうことになる。
【０００３】
このようなＲＩＳＣ型アーキテクチャにおいては、演算に使用されるデータは必ずレジスタに格納されている必要があり、従来の汎用コンピュータのように、演算命令のオペランドにメモリを指定するアドレッシング方法は行われない。また、ＣＰＵ時間とメモリのアクセス時間の比較をしてみると、マシンサイクルをτとするとほとんどの演算命令が１τから数τの程度であるのに比較してメモリの動作時間は数十τ必要である。すなわち、実行時間の大部分はメモリアクセスの待ち時間（レイテンシとも言う）に費やされてしまうことになる。
【０００４】
この遅延時間を減らすことがＲＩＳＣ型アーキテクチャにおける性能向上の要件ということになる。そこで、このために考案されたのがデータキャッシュ機能であり、メモリを階層化してアクセスの早いキャッシュメモリを備えるもので、現在のＣＰＵのほとんどに実装されている。データキャッシュはその名のとおりメモリの内容を一時的にため込んでおいて、繰り返し使用できればアクセスのおそいメモリに対するアクセス回数を減らすことができる。しかし、データキャッシュは大変速く動作する変わりに実装される容量は小さい。
【０００５】
ＣＰＵから近い順に一次キャッシュ、二次キャッシュ、メモリで階層的に構成される場合、ＣＰＵからロード要求があった時の遅延時間の程度を先に述べたマシンサイクル時間τにより例示すると、一次キャッシュにデータが存在している場合は０τ、二次キャッシュにあれば一次キャッシュへのコピーを伴い１０τ、メモリに要求データがあれば一次／二次キャッシュへのコピーを伴い１００τの遅延時間が伴うことになる。このように、ロード命令が実行されるとき目的のデータが上記したＣＰＵに近い階層に存在する場合ほど待ち時間が少なく処理が高速に行われるようになる。
【０００６】
上記のように従来のコンピュータにおいても、メモリを階層化してアクセスの早いキャッシュメモリを備え、繰り返しアクセスされるメモリ上のデータ群についてのアクセスの高速化が実現されていた。また、単に一度アクセスされたメモリ上のデータ群についてのアクセス高速化を期待するだけでなく積極的に実行されるプログラムの命令を解析して後に実行されるはずのメモリアクセスを伴う命令について前以って必要部分を通常のメモリから高速のキャッシュメモリにデータをコピーしておく工夫も開示されている。例えば、特開平８−１６１２２６にはキャッシュメモリを使用するシステムにおけるデータ先読み制御方法として、ロード命令のアクセス対象となるデータの配置パターンに応じたタイプによってロード命令の種類を分けて、この種類をオペレーション・コード等により識別できるようにして、ロード命令が先に発行したロード命令と関係づけられるとき、先行するロード命令の処理時に、ロード命令の種類に応じて後続するロード命令のロードアドレスを予測し、そのデータをキャッシュメモリに先読みする技術が示されている。
【０００７】
従来はこの様にプログラムの実行時にハード的に先読みの効果のある条件を検出してデータキャッシュの活用をすすめていたが、最近ソフト的に命令によりデータキャッシュにメモリの内容を先読みする機能すなわちデータプリフェッチ命令を持ったコンピュータが開発されるようになってきた。このデータプリフェッチ命令を利用したデータキャッシュの活用が期待されている。
【０００８】
【発明が解決しようとする課題】
上記したようにメモリ上のデータをロードするときの待ちによる遅延時間は繰り返しアクセスされるデータ群についてはデータキャッシュにより格段に削減されるが、データキャッシュに存在しないときには効果が無い。上記公知例に示すような条件のとき実行時に先読みで期待される効果を検出して事前にロードされるデータをデータキャッシュに先読みするものもあるが上記ロード命令の条件に合わない場合にはデータキャッシュの高速アクセスを有効に活用できていない。
【０００９】
従来はこの様にプログラムの実行時にハード的に先読みの効果のある条件を検出してデータキャッシュの活用をすすめていたが、実行時に検出できるようなデータキャッシュを有効とするメモリ先読みの条件は限られたものとなり、プログラム作成段階でのデータキャッシュの活用手続きの組み込みが課題でありその解決策が求められていた。
【００１０】
本発明はこのような点にかんがみて、ソースプログラム作成段階あるいはコンパイル段階でプログラムの構造の特徴を解析してロード命令に先立ってデータキャッシュに必要なメモリの内容をコピーしておくようにする手段を提供することを目的とする。
【００１１】
【課題を解決するための手段】
上記の課題は下記の如くに構成されたコンパイル装置によって解決される。
図１は、本発明の構成図である。
【００１２】
図において、１は原始プログラムを中間テキストに変換し、変換した中間テキストに対して最適化を行い、機械語を生成するコンパイル装置において、あらかじめ設定された１以上の原始プログラム命令種類に対応して変換された中間テキストを検索する中間テキスト検索手段であり、２は検索した中間テキストに基づいてデータキャッシュへコピーするメモリのアドレスを算出し、検索した中間テキストより前の実行順序位置に上記算出したアドレスを指定したデータキャッシュプリフェッチ命令を挿入するプリフェッチ命令挿入手段である。（請求項１）
３は上記検索した中間テキストの実行順序位置から、あらかじめ原始プログラム命令種類毎に設定された遡及すべきプログラム実行時間に基づいてプログラムの制御の流れをさかのぼり、上記プリフェッチ命令を挿入する実行順序位置を決定するプリフェッチ命令挿入位置最適化手段である（請求項２）。
【００１３】
また、上記コンパイル装置は複数の単純な命令を複数のスロットに格納して構成するＶＬＩＷ命令を持つＶＬＩＷ型アーキテクチャのコンピュータで実行するプログラムを生成するコンパイル装置であって、プリフェッチ命令挿入手段２は空きスロットにデータキャッシュプリフェッチ命令を生成するものであるとき、４は空きスロットがないときに、データキャッシュプリフェッチ命令の挿入を抑止するか、新たに独立したＶＬＩＷ命令を生成するかを設定するプリフェッチ命令挿入モード設定手段である（請求項７）。
【００１４】
【発明の実施の形態】
図２は本発明の実施の形態の構成図である。
２２はコンパイル装置であり、ソースプログラム２１で示される原始プログラムをソースプログラム解析部２３で中間テキストに変換し、変換した中間テキストに対して最適化実施部２４で最適化を行い、スケジューリング＆コード生成部２５でオブジェクトプログラム２６で示す機械語を生成するものである。本発明の特徴とするデータキャッシュプリフェッチ命令の生成と挿入の制御は上記最適化実施部２４で行うようになっている。コンパイル装置２２はコンピュータ上で動作するものである。
【００１５】
すなわち、本実施の形態においては、パーソナルコンピュータ、ワークステーション等の汎用的な目的で使用される計算機上で実行するコンピュータプログラムにより実現する形態を示す。
【００１６】
本発明のコンパイル装置は、処理装置、主記憶装置、補助記憶装置、入出力装置などから構成される計算機上で、コンピュータプログラムを実行して実現される。また、コンピュータプログラムは、フロッピーディスクやＣＤ−ＲＯＭ等の可搬型媒体やネットワーク接続された他の計算機の主記憶装置や補助記憶装置等に格納されて提供される。本発明の記録媒体は、上記可搬型媒体、主記憶装置、補助記憶装置に該当する。
【００１７】
提供されたコンピュータプログラムは、可搬型媒体から直接計算機の主記憶装置にロードされ、または、可搬型媒体から一旦補助記憶装置にコピーまたはインストール後に、主記憶装置にロードされて実行する。また、ネットワーク接続された他の装置に格納されて提供された場合も、他の装置からネットワークを経由して受信後に、補助記憶装置にコピー、主記憶装置にロードされ実行するものである。
【００１８】
以下にデータプリフェッチ命令の挿入の仕組みと動作について図とフローチャートを参照しながら説明する。
図３はデータプリフェッチ命令の説明図である。図３（ａ）にはメモリ上のデータを処理対象とする関数として「ｓｔｒｃｐｙ」（ｓｔｒｉｎｇ  ｃｏｐｙ、すなわち、文字列をコピーする関数）を例にとり、アドレス「ａｄ２」で示されるメモリ上の位置に文字列「ａ，ｂ，ｃ，ｄ，ｅ」３１があるときＲＥＧ３２を経由してアドレス「ａｄ１」のメモリ３３にコピーするものであることを示している。
【００１９】
図３（ｂ）は上記関数「ｓｔｒｃｐｙ」がコンパイル装置２２のソースプログラム解析部２３で生成された「ＬＯＡＤ命令▲１▼、▲２▼」および関数「ｓｔｒｃｐｙの呼び出し命令：ＣＡＬＬ▲４▼」を示している。すなわち「ＣＡＬＬ」の引数の二つのアドレス、ａｄ１、ａｄ２はそれぞれＲＥＧ１、ＲＥＧ２に格納して渡し、「ｓｔｒｃｐｙ」ルーチンを呼び出すように中間テキストを生成していることを示している。ここで中間テキストはオブジェクトプログラムとしてマシン命令を作り出す中間の命令でおおむねマシン命令に対応するものである。ただし、コンパイル装置の後の処理工程で必要とする情報を合わせて持っている。例えば、最適化のときに必要な情報として、どの中間テキストから制御が渡されるのかを示す「経路情報」などがある。
【００２０】
ここで、▲３▼により示される「ＰＲＥＦＥＴＣＨ  ＲＥＧ２」は「ｓｔｒｃｐｙの呼び出し命令：ＣＡＬＬ▲４▼」の引数としてコピーする元の文字列のアドレスを含むメモリ上のデータの塊を対応するデータキャッシュにコピーすることを示すものである。これは、「ｓｔｒｃｐｙ」でメモリからレジスタに文字データをロードする必要性が分かっているのでロード命令の実行前にアクセスの速いデータキャッシュにコピーする命令を挿入するものである。
【００２１】
すなわち、図３（ｃ）に示すようにＲＥＧ３を用いて「ＬＯＡＤ命令、ＳＴＯＲＥ命令」によりＲＥＧ２で示される文字データをＲＥＧ１で示されるメモリにコピーする。このＬＯＡＤ命令でアクセスするメモリの内容が含まれる部分がＬＯＡＤ命令の実行前にデータキャッシュにコピー完了していることが望ましいが、もしメモリからのコピーが途中の状態であってもＬＯＡＤ命令が発行されたとき全く新たにメモリからデータキャッシュにコピーする動作を開始することに比べれば時間短縮の効果は確実に得られる。つまり、ＬＯＡＤ命令が発行されたときに指定のアドレスのメモリの内容がデータキャッシュに存在すればデータキャッシュからロードされ、もし無ければＬＯＡＤ命令で指定されたアドレスのメモリの内容をまずデータキャッシュに移し完了を待ってレジスタにロードされるようになっている。したがって、事前に発行されたＰＲＥＦＥＴＣＨ命令によりメモリからデータキャッシュにデータの転送が始まっていればその完了を待ってデータキャッシュからレジスタにロードされるので時間短縮の効果が出るのである。
【００２２】
図４には中間テキストの説明図（その１）を示す。ここには、ユーザ関数定義文の例をソースプログラムのイメージで示す。ｆｏｏ（）によりユーザ定義の関数を表し、「・・・（１）・・・」により先頭部分の文を示す。続いてｉｆ文で条件が成り立つ［ｔｈｅｎ」のとき「・・・（２）・・・」の文を実行し、否「ｅｌｓｅ」の場合「・・・（３）・・・」の文を実行し、（２）または（３）の後に「・・・（４）・・・」を実行して終了する関数の定義を行うものである。
【００２３】
図５の中間テキストの説明図（その２）は上記図４のソースプログラムの構造をブロック図として示している。ここで、先頭の５１で入口／退避、最後の５６で出口／復元のように示したものは、定義する関数の中で使用するレジスタの内、グローバルレジスタと呼ばれるレジスタについて、その内容を関数の実行後も保証するために入口でメモリに退避し、出口で退避していた内容をレジスタに復元することを示している。つまり、グローバルレジスタの内容は各関数が呼ばれたときにはある固有の意味を持ったものであり関数の出口で呼び出し元に戻るときにはその内容を元に戻す約束ごとである。これらの「退避」あるいは「復元」も関数として呼び出すようにしている。
【００２４】
図６は中間テキストの説明図（その３）である。上記した図４および図５に対応して生成された中間テキストをアセンブラ命令レベルの構造で示したものである。詳しく図示はしていないが複数のアセンブラ命令をソース命令文の単位にくくった「節」が存在する。「ｔｈｅｎ節」、「ｅｌｓｅ節」などがこれである。また、入口、出口の「退避」、「復元」も同様に一塊の処理であることが処理の種類と制御の流れなどについての情報とともに記録されている。
【００２５】
中間テキスト（命令）を区別して説明するために「＃」により番号を示しているが、そこに示す上向きの矢印は中間テキスト（命令）の制御が渡される元の中間テキスト（命令）を指し示す経路情報である。これはコンパイル装置のソースプログラム解析部が後の工程で必要な情報として記録するものの一つであり、同様に順方向の制御の流れも記録されている。
【００２６】
具体的に対応を見てみると、関数の実行に先立つレジスタの退避（＃１、＃２）、ｉｆ文の分岐（＃３）、ｔｈｅｎ節（＃４、＃５、および＃６で後処理への分岐）、ｅｌｓｅ節（＃７、＃８）、後処理（＃９）、関数の出口での復元（＃１０、＃１１）のように構成されていることがわかる。また、上向き矢印は実行時の制御の流れを溯る方向を示している。＃３には＃４および＃７からの矢印が指し示しているがｉｆ文の条件の判定により二通りに別れることに対応している。同様に＃９では実行時の制御の流れが＃６あるいは＃８から渡されることを意味している。
【００２７】
図７はプリフェッチ対象処理テーブル説明図である。図２に示した最適化実施部２４が図４乃至６に示した中間テキストをソースプログラム解析部２３から受け取り、データプリフェッチ命令を事前に挿入することが効果的であるものを見つけるために、そのキーとなる中間テキストに記録されている処理名情報を一覧としたものでありコンピュータに記憶されている。図７に見るようにタイプがシステム関数であるものとしては、ｓｔｒｃｐｙ（文字列コピー）、ｓｔｒｎｃｐｙ（文字数指定の文字列コピー）、ｓｔｒｌｅｎ（文字列長さ）、ｓｔｒｃｍｐ（文字列比較）、ｍｅｍｃｐｙ（メモリ内容コピー）、ｍｅｍｃｍｐ（メモリ内容比較）等がある。これらは、何れもメモリ上のデータをレジスタにロードした後処理するものであり、処理の前のメモリからのロード待ち時間をいかに短くするかにより実行時間が大きく左右されるシステム関数である。対象とするシステム関数はあらかじめこのテーブルに登録しておくようにしている。
【００２８】
同様にタイプがユーザ定義関数のｆｏｏｘ、ｆｏｏｙ、ｆｏｏｚもメモリ上のデータをレジスタにロードした後処理するユーザ定義関数であり、効果の期待できるものだけをこのテーブルに登録しておく。
【００２９】
タイプがレジスタ復元のものはプログラム開発の部品として復元内容別にいくつかの種類が登録されるもので前記したようにグローバルレジスタとして共通に内容を受け渡すために利用するレジスタを局部的に別の用途に使用するとき自分で退避しておいた内容を復元して処理を呼び出し元に返すものである。すなわち必ずメモリからレジスタへのロードが実行されるのであらかじめアクセスされるアドレスのメモリをプリフェッチしてデータキャッシュにコピーしておくことが望ましいものである。
【００３０】
タイプがユーザ指定プリフェッチとしたものはソースプログラムに記述して、陽にプリフェッチを指示するハード命令を発行するものである。
プリフェッチ対象処理テーブルの各処理名に対応して引数の並びとｌｏａｄ命令の対象引数、遡及命令数が示されている。このｌｏａｄ命令の対象引数に示される引数の位置を引数の並びから探すことにより各処理でロードされるメモリのアドレス、すなわちプリフェッチすべきメモリのアドレスを知ることができる。さらに、遡及命令数は各処理ごとに実行時にその処理の先頭からどの程度処理が進んだ位置にメモリからレジスタへのロード命令が実行されるのかに対応して逆にどれだけ先行してプリフェッチ命令を実行したら良いのかを示すものである。ここに示す数値はこのように溯った位置に命令を挿入するために溯る命令数に見合った数値を記録するようにしている。ただし、各命令毎に若干の命令実行時間、すなわちマシンサイクルを単位とした時間が異なるので溯る命令数は各関数で調整して設定するようにしている。
【００３１】
次に、図８、図９にＶＬＩＷ命令の空きスロットとプリフェッチ命令配置の説明図（その１）および（その２）を示す。これはＶＬＩＷ型アーキテクチャのコンピュータに本発明を実施したときの形態を説明するためのものである。
【００３２】
上記ＶＬＩＷ型アーキテクチャを備えたコンピュータの特徴は、複数の単純な命令を複数のスロットに格納して構成するＶＬＩＷ命令を持つものである。そして当然コンパイル装置もＶＬＩＷ型アーキテクチャのコンピュータで実行するプログラムを生成するコンパイル装置が使用される。
【００３３】
まず図８（ａ）ＶＬＩＷ命令とスロットに示すようにＶＬＩＷ命令は複数のスロット、ここではスロットａ乃至スロットｄの４個のスロットを備えた命令であり、各スロットに格納された命令は同時に実行されるようになる。
【００３４】
図８（ｂ）命令配置の並列化によって一つのＶＬＩＷ命令に一緒に格納可能な命令について説明する。まず通常のコンピュータであれば順番に実行される命令列を▲１▼に示している。これはアドレスＡとアドレスＢのデータをレジスタＲＥＧ１とＲＥＧ２にロードしてＡＤＤ命令で加算してレジスタＲＥＧ３に結果を作り出し、ＳＴＯＲＥ命令でＲＥＧ３の結果をアドレスＣに格納するための命令群である。続いて▲２▼には並列に実行可能なものは横に並べ、順序を必要とする命令は縦方向に並べたものを示す。すなわち、ＲＥＧ１、ＲＥＧ２へのロードは別々のレジスタであり順序性はないので同時に実行可能であり、加算およびその結果を格納する命令はそれぞれ順番に前の命令の完了を待ってはじめて実行できるので順序が必要であることを示す。図８（ｃ）には上記並列に実行可能なＬＯＡＤ命令を一つのＶＬＩＷ命令に収めた例を示している。ここで、スロットｂおよびスロットｄに格納されている「ＮＯＰ」はＮｏ  Ｏｐｅｒａｔｉｏｎを意味する命令であり、並列に実行可能な命令が無く、やむを得ず空きスロットとして残すときに埋める命令コードである。
【００３５】
次に、図９（ｄ）プリフェッチ命令の配置について説明する。図８（ｂ）に示した命令列においてプリフェッチ命令を挿入する位置は▲１▼に示すようにＬＯＡＤ命令の後、ＡＤＤ命令の前となる。これをＶＬＩＷ命令として挿入したものを▲２▼に示す。すなわちＰＲＥＦＥＴＣＨ命令だけのためにＶＬＩＷ命令を一つ挿入しているが上記説明したＮＯＰ命令が多くを占めることになる。そこで、本発明ではＶＬＩＷ命令においては既にＮＯＰ命令つまり空きがあるときにはそこにＰＲＥＦＥＴＣＨ命令を配置して格納するようにする。このように配置したものを図９（ｄ）▲３▼に示す。このようにすることにより命令数の削減、命令実行待ち時間の削減の効果が得られる。逆にループの中などではＶＬＩＷ命令を単純に一つ挿入して追加するときのコストが余分にかかることにもなり、空きスロットがあるときだけプリフェッチ命令を挿入することも可能とする。これは図１のプリフェッチ命令挿入モード設定手段４により実現している。
【００３６】
図１０にはプリフェッチ命令挿入フローチャートを示す。ここには図２のソースプログラム解析部２３の出力である図６に示すような中間テキストを入力としてプリフェッチ命令をその前に挿入する効果のある処理を見つけてプリフェッチすべきメモリ上のデータのアドレスを指定したプリフェッチ命令を生成して最適な位置に挿入する手順を説明する。
【００３７】
ステップＳ１０１ではコンパイルするときにコンパイルモードとして利用者からプリフェッチオプションが指定されていることを確認する。ステップＳ１０２で順番に中間テキストを一つずつ取出す。ステップＳ１０３でまずそれが関数呼び出しの中間テキストかを調べる中間テキストにおいては関数は図３（ｂ）に示すように「ＣＡＬＬ」命令またはここには例示していないが、前記した図７におけるタイプがユーザ指定プリフェッチのとき指定する拡張命令である「ｐｒａｇｍ」命令の引数として関数名を表すのでこれを取出して調べることになる。
【００３８】
ステップＳ１０４では取出した関数名が図７のプリフェッチ対象処理テーブルに登録されている処理名と比較していずれかと一致しているかを調べる。テーブルに登録されていない場合はプリフェッチ命令を挿入しても効果が無いものであるとして何も行わずステップＳ１０７に移り次の中間テキストの処理に移る。
【００３９】
テーブルにあった場合にはステップＳ１０５において見つかった関数の引数並びとｌｏａｄ命令対象引数からプリフェッチ命令に指定するアドレスを調べてＰＲＥＦＥＴＣＨテキストを生成する。生成したＰＲＥＦＥＴＣＨテキストの配置についてはステップＳ１０６において後に別途フローチャートで説明する最適化を行い、挿入位置を決定して上記生成したＰＲＥＦＥＴＣＨテキストを挿入する。あとはステップＳ１０７で終わりを確認して終了する。
【００４０】
最後に図１１と図１２でプリフェッチ命令の配置の最適化を説明する。図１１および図１２にはプリフェッチ命令挿入位置最適化フローチャート（その１）および（その２）を示す。フローチャート（その２）はフローチャート（その１）から呼び出されるもので挿入位置検出プログラムの動作を示す。
【００４１】
プリフェッチ命令挿入位置最適化フローチャート（その１）は上記説明したようにプリフェッチ命令を挿入するべき関数を検出し、挿入すべきＰＲＥＦＥＴＣＨテキストを生成したときにそれを配置するべく呼び出されて起動されるプログラムである。したがってステップＳ１１１では中間テキストの位置、溯って挿入する位置を数えるための初期値０を与えたカウンタおよびその関数に対応する図７のテーブルに示した遡及命令数を引数として設定して、ステップＳ１１２において図１２に示すＰＲＥＦＥＴＣＨテキスト挿入位置検出プログラムを呼び出す。挿入位置は図６で分かるように↑で示される複数の経路情報を溯ってたどるので１以上のプリフェッチ命令の配置が起こり得るのでＰＲＥＦＥＴＣＨテキスト挿入位置検出プログラムからはそれらの１以上の位置情報を返される。
【００４２】
ステップＳ１１３では生成されたＰＲＥＦＥＴＣＨテキストを上記記憶されて返された１以上の挿入位置に配置する。
図１２のフローチャートの説明に入る。これは上記プリフェッチ命令を配置するとき呼び出されるもので、ＰＲＥＦＥＴＣＨテキスト挿入位置検出プログラムの処理手順を示すものである。このプログラムは図６の↑で示す経路情報をたどり引数で示される遡及すべき命令数だけ溯った位置を最適配置位置として記憶するものであり途中で溯る経路情報が複数あるテキストも存在するので溯りながら最も近い複数の経路情報のあった中間テキストの位置に戻って別の経路を溯るようにするため、後で説明するようにステップＳ１２６においては自分自身を呼び出す再起呼び出しの形式をとっている。
【００４３】
ステップＳ１２１では引数として与えられたテキスト位置、カウンタアドレスを受け取る。ステップＳ１２２で、まずテキスト位置を一つ溯りカウンタに１を加える。ステップＳ１２３ではカウンタが遡及命令数に到達していないか、すなわちもっと溯ってプリフェッチ命令を配置すべきかを調べる。到達したときにはステップＳ１２７においてその時点のテキスト位置をＰＲＥＦＥＴＣＨテキストの挿入位置として蓄積して記憶して呼び出し元に返る。
【００４４】
ステップＳ１２４では現在の中間テキストに未処理の経路情報があるかをチェックする。ない場合このプログラムを終了して呼び出し元に帰る。
未処理経路情報がある場合にはステップＳ１２５において未処理経路情報を取出し、ステップＳ１２６において取出した経路について溯るように、現在のテキスト位置と、カウンタを引数として自分自身すなわちＰＲＥＦＥＴＣＨテキスト挿入位置検出プログラムを呼び出す。これにより枝別れした経路を溯ってステップＳ１２３の条件を満足する位置が見つかる度にステップＳ１２７でＰＲＥＦＥＴＣＨテキストの挿入位置として蓄積して記憶する。一つの経路を溯り目的の位置を見つける度に記憶されたＰＲＥＦＥＴＣＨテキスト挿入位置は図１１の最初の呼び出しに対応して戻ったときにステップＳ１１３において取出されプリフェッチ命令がそれに基づいて配置されることになる。ステップＳ１２６での戻りはステップＳ１２４として次の別れた経路を探索するようにしている。
【００４５】
なお、フローチャートには図示していないが中間テキストの経路情報と並んで記録された付加情報によりそれ以上溯れないテキスト、例えば関数定義の先頭とか中間テキストが関数呼び出しである場合にはカウンタが遡及命令数に達したとして扱い、ステップＳ１２３においてステップＳ１２７に制御を移すように処理する。
【００４６】
このようにして中間テキストについてプリフェッチ命令を挿入すべき関数の呼び出し毎に有効なプリフェッチ命令を生成して実行時の経路の可能性を溯ってたどり最適な位置に配置して挿入することができる。
【００４７】
なお、ステップの短いユーザ定義関数などで溯る命令数が図７のテーブルにある遡及命令数を満足する位置とならず最適化の配置が完全なものではなくても、前記したようにロード命令の完了がデータキャッシュへのメモリからのコピー完了待ち時間がより少なくなるという効果が期待できる。極端にいえばプリフェッチ命令を挿入すべき関数の直前に配置したとしても効果は得られるものである。
【００４８】
また、原始プログラム作成段階でプリフェッチ命令をプログラム作成者が原始プログラムの適当な位置に記述して組み込み実行時性能を向上させる効果を得ることは通常の手段であり、上記実施の形態における図７のプリフェッチ対象処理テーブルにおけるユーザ指定プリフェッチによって組み込む方法もある。
【００４９】
【発明の効果】
以上の説明から明らかなように本発明によれば、コンパイル段階でプログラムの構造の特徴を解析してロード命令に先立ってデータキャッシュに必要なメモリの内容をコピーしておくようにすることが可能となり、データキャッシュのヒット率を向上し、あるいはメモリからデータキャッシュへのコピー待ち時間を削減することができることにより、コンピュータの命令実行性能を向上するという著しい工業的効果がある。
【図面の簡単な説明】
【図１】  本発明の構成図
【図２】  本発明の実施の形態の構成図
【図３】  データプリフェッチ命令の説明図
【図４】  中間テキストの説明図（その１）
【図５】  中間テキストの説明図（その２）
【図６】  中間テキストの説明図（その３）
【図７】  プリフェッチ対象処理テーブル説明図
【図８】  ＶＬＩＷ命令の空きスロットとプリフェッチ命令配置の説明図（その１）
【図９】  ＶＬＩＷ命令の空きスロットとプリフェッチ命令配置の説明図（その２）
【図１０】  プリフェッチ命令挿入フローチャート
【図１１】  プリフェッチ命令挿入位置最適化フローチャート（その１）
【図１２】  プリフェッチ命令挿入位置最適化フローチャート（その２）
【符号の説明】
１  中間テキスト検索手段
２  プリフェッチ命令挿入手段
３  プリフェッチ命令挿入位置最適化手段
４  プリフェッチ命令挿入モード設定手段
【図１】
0003918274.tif 000002
【図２】
0003918274.tif 000003
【図３】
0003918274.tif 000004
【図４】
0003918274.tif 000005
【図５】
0003918274.tif 000006
【図６】
0003918274.tif 000007
【図７】
0003918274.tif 000008
【図８】
0003918274.tif 000009
【図９】
0003918274.tif 000010
【図１０】
0003918274.tif 000011
【図１１】
0003918274.tif 000012
【図１２】
0003918274.tif 000013