(57)【要約】インターロックを引き起こす可能性のある命令を無駄に発行せずに、プログラム実行時の処理速度を向上させるコンパイラは、実行時にインターロックを起こす可能性のある命令を備えたプロセッサ向けのコンパイラであって、入力プログラムに対し、ループ回数がｘ回のループをループ回数がｙ回のループに分割し、前記ループ回数がｙ回のループを内側ループとし、ループ回数がｘ／ｙ回のループを外側ループとする二重ループ変換を行うループ構造変換部（１８６）と、前記二重ループ変換後のプログラムに対して、インターロックを起こす可能性のある命令の配置を行う命令最適配置部（１８７）としてコンピュータを機能させることを特徴とする。【特許請求の範囲】
【請求項１】
実行時に外部からの所定の応答を待つ命令を含む命令セットを備えたプロセッサ向けのプログラム変換装置であって、
入力プログラムに含まれる繰返し回数がｘ回のループを、繰返し回数がｙ回のループを内側ループとし、繰返し回数がｘ／ｙ回のループを外側ループとするネスト構造への変換である二重ループ変換を行うループ構造変換手段と、
前記内側ループの外部の位置に、前記命令を配置することにより、当該命令を含む出力プログラムに変換する命令配置手段と
を備えることを特徴とするプログラム変換装置。
【請求項２】
前記ループ構造変換手段は、
前記入力プログラムに含まれるループを検出するループ検出部と、
前記ループの繰返し回数を検出する繰返し回数検出部と、
前記命令実行時の前記所定の応答を待つサイクル数である応答待ちサイクル数を検出する応答待ちサイクル数検出部と、
前記ループの１回の繰り返し処理に要する１シーケンスサイクル数を検出する１シーケンスサイクル数検出部と、
前記ループを、繰返し回数が（前記応答待ちサイクル数／前記１シーケンスサイクル数）回であるループに分割するループ分割部と、
繰返し回数が（前記応答待ちサイクル数／前記１シーケンスサイクル数）回のループを内側ループとし、繰返し回数が（前記ループの繰返し回数／前記内側ループの繰返し回数）回をループの外側ループとするネスト構造への変換である二重ループ変換を行う二重ループ変換部と
を有することを特徴とする請求項１に記載のプログラム変換装置。
【請求項３】
さらに、最適化に関する最適化指示情報を受け取る最適化指定情報受け取り手段を備える
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項４】
前記最適化指定情報受け取り手段は、前記入力プログラムに含まれるループの最低繰り返し回数を受け取り、
前記ループ構造変換手段は、ループの実行回数が不定な場合は、前記最低繰り返し回数に基づいて、前記最低繰り返し回数の繰り返し処理を前記ループより取り出し、取り出したループの繰り返し処理に対して二重ループ変換を行う
ことを特徴とする請求項３に記載のプログラム変換装置。
【請求項５】
前記命令は、インターロックを発生させる可能性のある命令である
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項６】
前記インターロックを発生させる可能性のある命令は、主記憶装置からキャッシュへのデータのプリフェッチ命令である
ことを特徴とする請求項５に記載のプログラム変換装置。
【請求項７】
さらに、命令のスケジューリングを行うスケジューリング手段を備え、
前記ループ構造変換手段は、
前記繰り返し回数がｘ回のループを、前記スケジューリング手段により得られた結果から、前記プリフェッチを実行するのに必要なサイクル数分だけ実行されるような繰り返し回数がｙ回のループに分割し、繰り返し回数がｙ回のループを内側ループ、繰り返し回数がｘ／ｙ回のループを外側ループとするネスト構造への変換である二重ループ変換を行う
ことを特徴とする請求項６に記載のプログラム変換装置。
【請求項８】
前記命令は、実行後に、所定の資源が参照可能状態になるまでに複数サイクルを要する命令である
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項９】
前記複数を要する命令は、主記憶装置またはキャッシュをアクセスする命令である
ことを特徴とする請求項８に記載のプログラム変換装置。
【請求項１０】
前記ループ構造変換手段は、
前記繰り返し回数がｘ回のループを、当該ループ内で参照される配列のアドレスがキャッシュのラインサイズ進む分だけ実行されるような繰り返し回数がｙ回のループに分割し、繰り返し回数がｙ回のループを内側ループ、繰り返し回数がｘ／ｙ回のループを外側ループとする二重ループ変換を行う
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項１１】
前記ループ構造変換手段は、前記配列が複数存在する場合に、二重ループ変換を行った前記繰り返し回数がｙ回のループを、さらに、前記配列の数に基づいて案分する案分変換を行う
ことを特徴とする請求項１０に記載のプログラム変換装置。
【請求項１２】
前記案分変換は、複数の前記配列について、その配列要素のサイズが異なるときには、前記サイズ比に応じて前記繰り返し回数がｙ回のループを案分する
ことを特徴とする請求項１１に記載のプログラム変換装置。
【請求項１３】
前記案分変換は、複数の前記配列について、ループの繰り返し処理を１回を行うのに進むアドレスであるストライドが異なるときに、前記ストライド比に応じて前記繰り返し回数がｙ回のループを案分する
ことを特徴とする請求項１１記載のプログラム変換装置。
【請求項１４】
前記案分変換は、内側ループを変換する際に、配分された各ループに対応する条件文を生成して、配分された各ループを同一の内側ループで実行されるように案分変換を行う
ことを特徴とする請求項１１に記載のプログラム変換装置。
【請求項１５】
前記ループ構造変換手段は、
前記繰り返し回数がｘ回のループを、前記繰り返し回数がｙ回のループに分割する際に、ｘ／ｙを演算した際の余りｚが０でなければ、ｚ回の繰り返し処理に対してピーリング処理を行ない、二重ループ変換を行う
ことを特徴とする請求項１０に記載のプログラム変換装置。
【請求項１６】
前記ループ構造変換手段は、
前記余りｚが０でなければ、内側ループのループ回数がｙ回であるか２回であるかを判定する判定する条件文を生成し、二重ループ変換を行う
ことを特徴とする請求項１５記載のプログラム変換装置。
【請求項１７】
前記ループ構造変換手段は、ループの実行回数が不定な場合は、前記ループの実行回数を実行時に判定し、判定結果に基づいて繰り返し回数を動的に変化させるような二重ループ変換を行う
ことを特徴とする請求項１０に記載のプログラム変換装置
【請求項１８】
さらに、配列がキャッシュのラインサイズにアラインされているという情報を受け取る受け取り手段を備え、
前記命令配置手段は、前記繰り返し回数がｘ回のループに対して、当該ループにおけるｘ回の繰り返し処理で参照されるデータよりも一つ先のキャッシュのラインに記憶されるデータをプリフェッチするプリフェッチ命令を配置する
ことを特徴とする請求項１０に記載のプログラム変換装置
【請求項１９】
前記最適化指定情報受け取り手段は、配列がキャッシュのラインのどの相対位置からアクセスを開始するかという情報を受け、
前記ループ構造変換手段は、当該情報に基づいて前記に二重ループ変換を行う
ことを特徴とする請求項１０に記載のプログラム変換装置。
【請求項２０】
前記命令配置手段は、前記配列がキャッシュのラインサイズにアラインされていない場合には、前記繰り返し回数がｘ回のループに対して、当該ループにおけるｘ回の繰り返し処理で参照されるデータよりも二つ先のキャッシュのラインに記憶されるデータをプリフェッチするプリフェッチ命令を配置する
ことを特徴とする請求項１０に記載のプログラム変換装置。
【請求項２１】
前記ループ構造変換手段は、前記配列がキャッシュのラインサイズにアラインされていない場合には、前記配列がキャッシュのラインのどの相対位置からアクセスを開始するかを判定し、判定結果に応じて二重ループ構造変換を行う
ことを特徴とする請求項１０に記載のプログラム変換装置。
【請求項２２】
さらに、着目する配列に関する情報を受け取る受け取り手段を備え、
前記ループ構造変換手段は、当該配列に対してのみ着目し、二重ループ変換を行う
ことを特徴とする請求項１０に記載のプログラム変換装置。
【請求項２３】
前記ループ構造変換手段は、最内ループを１つのかたまりとみなして、外側のループに対してさらに二重ループ変換を行う
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項２４】
実行時に外部からの所定の応答を待つ命令を含む命令セットを備えたプロセッサ向けのプログラム変換方法であって、
入力プログラムに含まれる繰返し回数がｘ回のループを、繰返し回数がｙ回であるループを内側ループとし、繰返し回数がｘ／ｙ回のループを外側ループとするネスト構造への変換である二重ループ変換を行うステップと、
前記内側ループの外部の位置に、前記命令を配置し、当該命令を含む出力プログラムに変換するステップと
を含むことを特徴とするプログラム変換方法。
【請求項２５】
実行時に外部からの所定の応答を待つ命令を含む命令セットを備えたプロセッサ向けのプログラム変換方法のプログラムであって、
入力プログラムに含まれる繰返し回数がｘ回のループを、繰返し回数がｙ回であるループを内側ループとし、繰返し回数がｘ／ｙ回のループを外側ループとするネスト構造への変換である二重ループ変換を行うステップと、
前記内側ループの外部の位置に、前記命令を配置し、当該命令を含む出力プログラムに変換するステップと
をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】  本発明はプログラム変換装置に関し、特に実行時に外部からの所定の応答を待つ命令を含む命令セットを備えたプロセッサ向けのプログラム変換装置に関する。
【背景技術】
【０００２】  近年、プロセッサの処理速度は急激に向上しているが、それに比べてメインメモリのアクセス速度向上は小さく、両者の速度差は年々大きくなっている。このため、情報処理装置の高速処理においてメモリアクセスがボトルネックとなることが従来指摘されている。【０００３】  この問題を解消するために、記憶階層の考え方からキャッシュ機構が用いられている。キャッシュ機構では、プロセッサで必要とされるデータを主記憶から高速なキャッシュへ予め転送（プリフェッチ）しておく。これにより、プロセッサからのメモリアクセスに高速に対応することが可能である。【０００４】  しかし、プロセッサがキャッシュ上に無いデータにアクセスした場合にはキャッシュミスが発生してしまう。このため、主記憶からキャッシュへのデータの転送時間がかかってしまうという問題がある。【０００５】  ユーザがキャッシュを意識することなくプログラミングを行い、そのプログラムが実行されれば、このようなキャッシュミスが頻発することが想定される。その結果、キャッシュミスによるペナルティがプロセッサの性能を大きく劣化させることになる。そのため、コンパイラがキャッシュを考慮した最適化を行う必要がある。【０００６】  キャッシュ最適化の技術の一つとしてプリフェッチ命令の挿入が挙げられる。プリフェッチ命令とは、あるメモリアドレスの参照が起こる前に、そのアドレスのデータを前もって主記憶からキャッシュへ転送しておくものである。プリフェッチ命令の挿入による最適化では、当該メモリアドレスの参照が起こる少し前のサイクルにプリフェッチ命令の挿入をおこなうものである。【０００７】  例えば、図１（ａ）に示すようなループ処理に対しては、図１（ｂ）に示すようにデータが参照されるまでのレイテンシを考慮し、数イタレーション先で参照されるデータをプリフェッチするようにプリフェッチ命令（ｄｐｒｅｆ（））がループ内に挿入される。なお、ここでは、ｉｎｔ型の配列ａの要素は４バイト、キャッシュのラインサイズを１２８バイトとする。
【発明の開示】
【発明が解決しようとする課題】
【０００８】  しかし、図１（ｂ）に示すコードでは、１イタレーションにつき配列ａの参照とプリフェッチとがそれぞれ行われているが、参照は４ｂｙｔｅずつしか行われないのに対して、プリフェッチは１ライン（１２８ｂｙｔｅ）単位で行われる。【０００９】  よって、１回のプリフェッチで３２回分の参照に対応できるため、残り３１回は無駄にプリフェッチが行われていることになる。すなわち、同じラインのプリフェッチ命令を連続発行してしまっている。【００１０】  また、プロセッサによっては、ｄｐｒｅｆ命令によるデータ転送中に、次のｄｐｒｅｆ命令を実行しようとすると、前のｄｐｒｅｆ命令による主記憶からキャッシュへのデータ転送が終了していないにもかかわらず、次のｄｐｒｅｆ命令が発行されてしまい、本来インターロックを解消するためにｄｐｒｅｆ命令を挿入したにも関わらず、インターロックが起こってしまう。【００１１】  よって、上記のようにループの１イタレーションが短く、２つのｄｐｒｅｆ命令の間隔が短いと、ｄｐｒｅｆ命令による主記憶からキャッシュへのデータ転送にかかる時間（レイテンシ）が顕在化し、かえって性能を悪化させてしまう。【００１２】  また、ｄｐｒｅｆ命令の実行時以外であっても、メモリアクセス命令などのように、命令発行後に何らかの応答待ちが発生するような命令の場合であっても、インターロックを起こす可能性がある。【００１３】  本発明は、上述の課題を解決するためになされたもので、インターロックを引き起こす可能性のある命令を無駄に発行せずに、プログラム実行時の処理速度を向上させるプログラム変換装置およびプログラム変換方法を提供することを目的とする。【００１４】  また、命令発行後に何らかの応答待ちが発生する命令を無駄に発行せずに、プログラム実行時の処理速度を向上させるプログラム変換装置およびプログラム変換方法を提供することを目的とする。【００１５】  また、プログラム実行時にインターロックを引き起こさないプログラム変換装置およびプログラム変換方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】  上記目的を達成するために、本発明に係るプログラム変換装置は、実行時に外部からの所定の応答を待つ命令を含む命令セットを備えたプロセッサ向けのプログラム変換装置であって、入力プログラムに含まれる繰返し回数がｘ回のループを、繰返し回数がｙ回のループを内側ループとし、繰返し回数がｘ／ｙ回のループを外側ループとするネスト構造への変換である二重ループ変換を行うループ構造変換手段と、前記内側ループの外部の位置に、前記命令を配置することにより、当該命令を含む出力プログラムに変換する命令配置手段とを備えることを特徴とする。【００１７】  これにより、例えば図２に示すように、図１（ａ）に示すようなループ処理を二重ループ化し、最内ループの外側にプリフェッチ命令を挿入することができる。これにより、無駄なプリフェッチ実行がなくなる。よって、処理速度が向上する。また、あるｄｐｒｅｆ命令が実行されてから次のｄｐｒｅｆ命令が実行されるまでの間に、主記憶からキャッシュへのデータ転送にかかるレイテンシを隠蔽することが可能になり、インターロックが生じにくくなる。【００１８】  すなわち、本発明によると、ループを二重化することにより、内側ループの外側でインターロックを起こす可能性のある命令を実行するようにすれば、当該命令を無駄に発行せずに、プログラム実行時の処理速度を向上させることができる。【００１９】  また、ループを二重化することにより、インターロックを起こす可能性のある命令を発行してから次のインターロックを起こす可能性のある命令までの間のサイクル数を確保することができる。このため、プログラム実行時にインターロックを引き起こしにくくなる。【００２０】  なお、プログラム変換装置は、コンパイラ、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）、またはＣＰＵ等の集積回路として実現可能である。【００２１】  応答待ち命令には、上述したｄｐｒｅｆ命令のようにインターロックを起こす可能性のある命令や、命令実行時に外部からの所定の応答を待つ命令の他に、応答を待つ場合と待たない場合とがある命令も含む。【００２２】  なお、本発明は、このような特徴的な手段を備えるプログラム変換装置として実現することができるだけでなく、プログラム変換装置が備える特徴的な手段をステップとするプログラム変換方法として実現したり、プログラム変換装置としてコンピュータを機能させるプログラムとして実現したりすることもできる。そして、このようなプログラムは、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）等の記録媒体やインターネット等の伝送媒体を介して流通させることができるのは言うまでもない。
【発明の効果】
【００２３】  本発明によると、プログラム実行時の処理速度を向上させることができる。
また、プログラム実行時にインターロックを引き起こしにくくなる。
【図面の簡単な説明】
【００２４】［図１］図１は、従来の最適化技術の問題点を説明するための図である。
［図２］図２は、本発明によるループ処理の構造変換を説明するための図である。
［図３］図３は、本実施の形態に係るコンパイラシステムの構成を示す図である。
［図４］図４は、コンパイラの構成を示す図である。
［図５］図５は、コンパイラが実行する処理のフローチャートである。
［図６］図６は、ループ構造変換処理の詳細を説明するための図である。
［図７］図７は、コピー型内側ループ分割処理の詳細を示すフローチャートである。
［図８］図８は、条件型内側ループ分割処理の詳細を示すフローチャートである。
［図９］図９は、プリフェッチ命令配置処理の詳細を示すフローチャートである。
［図１０］図１０は、プリフェッチ命令挿入処理の詳細を示すフローチャートである。
［図１１］図１１は、ピーリングが必要ない場合のシンプルループ分割処理について説明するための図である。
［図１２］図１２は、ピーリングが必要のない場合のソースプログラムの一例を示す図である。
［図１３］図１３は、図１２に示したソースプログラムに対応する中間言語のプログラムを示す図である。
［図１４］図１４は、図１３に示された中間言語のプログラムを二重ループに構造変換した後の中間言語のプログラムを示す図である。
［図１５］図１５は、図１４に示された中間言語のプログラムにプリフェッチ命令を挿入した後の中間言語のプログラムを示す図である。
［図１６］図１６は、ピーリングが必要な場合のシンプルループ分割処理について説明するための図である。
［図１７］図１７は、ループ内に複数の配列アクセスが存在する場合のループ分割処理について説明するための図である。
［図１８］図１８は、ループ内に複数の配列アクセスが存在する場合のループ分割処理について説明するための図である。
［図１９］図１９は、ループ内に複数の配列アクセスが存在し、かつ配列の要素のサイズがすべて同じではない場合のループ分割処理について説明するための図である。
［図２０］図２０は、ループ内に複数の配列アクセスが存在し、かつ配列の要素のサイズがすべて同じではない場合のループ分割処理について説明するための図である。
［図２１］図２１は、ループ内にストライドが異なる複数の配列アクセスが存在する場合のループ分割処理について説明するための図である。
［図２２］図２２は、ループ回数が不定なループ処理のループ分割処理を説明するための図である。
［図２３］図２３は、ループ回数が不定なループ処理のループ分割処理を説明するための他の図である。
［図２４］図２４は、ループ分割が不要な場合の最適化処理を説明するための図である。
［図２５］図２５は、ループ内でアクセスされる要素が主記憶上で適切にアラインされていない場合のループ分割処理を説明するための図である。
［図２６］図２６は、ループ内でアクセスされる要素が主記憶上で適切にアラインされていない場合のループ分割処理を説明するための図である。
［図２７］図２７は、アラインされていない配列要素を動的に特定して、ループ処理の最適化を行う処理について説明するための図である。
［図２８］図２８は、アラインされていない配列要素を説明するための図である。
［図２９］図２９は、アラインされていない配列要素をプロファイル情報を用いて特定し、ループ処理の最適化を行う処理について説明するための図である。
［図３０］図３０は、最内ループ以外のループに対する構造変換について説明するための図である。
［図３１］図３１は、プラグマ「＃ｐｒａｇｍａ＿ｌｏｏｐ＿ｔｉｌｉｎｇ＿ｄｐｒｅｆ変数名［，変数名］」により変数が指定された場合の最適化処理について説明するための図である。
［図３２］図３２は、ＰｒｅＴｏｕｃｈ命令挿入時におけるピーリングが必要ない場合のシンプルループ分割処理について説明するための図である。
［図３３］図３３は、ＰｒｅＴｏｕｃｈ命令挿入時におけるピーリングが必要な場合のシンプルループ分割処理について説明するための図である。
［図３４］図３４は、アラインされていない配列要素を動的に特定して、ループ処理の最適化を行う処理について説明するための図である。
【符号の説明】
【００２５】    １４１  ソースプログラム
１４２  キャッシュパラメータ
１４３  アセンブラファイル
１４４  オブジェクトファイル
１４５  実行プログラム
１４６  実行ログデータ
１４７  プロファイルデータ
１４８  コンパイラシステム
１４９  コンパイラ
１５０  アセンブラ
１５１  リンカ
１５２  シミュレータ
１５３  プロファイラ
１８１  最適化補助情報
１８２  構文解析部
１８３  最適化情報解析部
１８４  −般最適化部
１８５  命令スケジューリング部
１８６  ループ構造変換部
１８７  命令最適配置部
１８８  コード出力部
【発明を実施するための最良の形態】
【００２６】［システム構成］
図３は、本実施の形態に係るコンパイラシステムの構成を示す図である。コンパイラシステム１４８は、Ｃ言語等の高級言語で記述されたソースプログラム１４１を機械語の実行プログラム１４５に変換するソフトウェアシステムであり、コンパイラ１４９と、アセンブラ１５０と、リンカ１５１とを含む。【００２７】  コンパイラ１４９は、キャッシュを備えるコンピュータのＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）をターゲットプロセッサとし、ソースプログラム１４１をアセンブラ言語で記述されたアセンブラファイル１４３に変換するプログラムである。コンパイラ１４９は、ソースプログラム１４１をアセンブラファイル１４３に変換する際に、キャッシュのラインサイズやレイテンシサイクル等に関する情報であるキャッシュパラメータ１４２や、後述するプロファイルデータ１４７に基づいて、最適化処理を行い、アセンブラファイル１４３を出力する。【００２８】  アセンブラ１５０は、アセンブラ言語で記述されたアセンブラファイル１４３を機械語で記述されたオブジェクトファイル１４４に変換するプログラムである。リンカ１５１は、複数のオブジェクトファイル１４４を結合し、実行プログラム１４５を生成するプログラムである。【００２９】  実行プログラム１４５の開発ツールとして、シミュレータ１５２およびプロファイラ１５３が用意されている。シミュレータ１５２は、実行プログラム１４５をシミュレートし、実行時の各種実行ログデータ１４６を出力するプログラムである。プロファイラ１５３は実行ログデータ１４６を解析し、プログラムの実行順序等を解析したプロファイルデータ１４７を出力するプログラムである。【００３０】［コンパイラの構成］
図４は、コンパイラの構成を示す図である。コンパイラ１４９は、構文解析部１８２と、最適化情報解析部１８３と、一般最適化部１８４と、命令スケジューリング部１８５と、ループ構造変換部１８６と、命令最適配置部１８７と、コード出力部１８８とを含む。各構成処理部は、プログラムとして実現される。【００３１】  構文解析部１８２は、ソースプログラム１４１を入力として受け、構文解析処理を行った後、中間言語のプログラムを出力する処理部である。【００３２】  最適化情報解析部１８３は、キャッシュパラメータ１４２、プロファイルデータ１４７、コンパイルオプションおよびプラグマなどの中間言語の最適化処理に必要な情報を読み込み、解析する処理部である。一般最適化部１８４は、中間コードに一般的な最適化処理を施す処理部である。命令スケジューリング部１８５は、命令の並びを最適化し、命令スケジューリングを行う処理部である。コンパイルオプションおよびプラグマはいずれもコンパイラに対する指示である。【００３３】  ループ構造変換部１８６は、一重ループを二重ループに変換する処理部である。命令最適配置部１８７は、変換された二重ループ内にプリフェッチ命令を配置する処理部である。コード出力部１８８は、最適化された中間言語仕様のプログラムをアセンブラ言語で記述されたプログラムに変換してアセンブラファイル１４３を出力する処理部である。【００３４】［処理の流れ］
次に、コンパイラ１４９の実行する処理の流れについて説明する。図５は、コンパイラ１４９が実行する処理のフローチャートである。【００３５】  構文解析部１８２は、ソースプログラム１４１の構文解析を行い、中間コードを生成する（Ｓ１）。最適化情報解析部１８３は、キャッシュパラメータ１４２、プロファイルデータ１４７、コンパイルオプションおよびプラグマなどを解析する（Ｓ２）。一般最適化部１８４は、最適化情報解析部１８３における解析結果に従い、一般的な中間コードの最適化を行う（Ｓ３）。命令スケジューリング部１８５は、命令のスケジューリングを行う（Ｓ４）。ループ構造変換部１８６は、中間コードに含まれるループ構造に着目し、必要であれば一重ループ構造を二重ループ構造に変換する（Ｓ５）。命令最適配置部１８７は、ループ構造内で参照されるデータをプリフェッチする命令を中間コードに挿入する（Ｓ６）。コード出力部１８８は、中間コードをアセンブラコードに変換し、アセンブラファイル１４３として出力する（Ｓ７）。【００３６】  構文解析処理（Ｓ１）、最適化情報解析処理（Ｓ２）、一般的な最適化処理（Ｓ３）、命令スケジューリング処理（Ｓ４）およびアセンブラコード出力処理（Ｓ７）は、一般的な処理と同様であるため、その詳細な説明はここでは繰返さない。【００３７】  以下、ループ構造変換処理（Ｓ５）およびプリフェッチ命令配置処理（Ｓ６）について詳細に説明する。【００３８】  図６は、ループ構造変換処理（図５のＳ６）の詳細を説明するための図である。ループ構造変換部１８６は、ループ回数が即値で与えられており算出可能であるか、それ以外の変数等で与えられており算出不可能であるかを判断する（Ｓ１１）。すなわち、ループ回数が固定であるか不定であるかを判断する。【００３９】  ループ回数が不定の場合には（Ｓ１１でＮＯ）、プラグマまたはコンパイルオプションにより最低のループ回数の指定があるかまたはプログラム実行時に動的にループ回数を判定し、ループ分割をする旨の指定があるかについて判断する（Ｓ１２）。【００４０】  いずれかの指定がある場合（Ｓ１２でＹＥＳ）またはループ回数が固定値の場合には（Ｓ１１でＹＥＳ）、ループ内で参照されている配列の添え字が解析可能か否かについて調べる（Ｓ１３）。すなわち、ループカウンタがある規則性を持って変化している場合には解析可能であると判断される。例えば、ループカウンタの値がイタレーション内で書換えられるような場合には、解析不可能であると判断される。【００４１】  添え字が解析可能である場合には（Ｓ１３でＹＥＳ）、ループ処理内で参照される各配列について１イタレーションで参照される要素のバイト数を求め、そのうち最小の値ＬＢを導出する（Ｓ１４）。【００４２】  次に、キャッシュのラインサイズＣＳを値ＬＢで割った値が１よりも大きいか否か判断する（Ｓ１５）。ＣＳ／ＬＢの値が１よりも大きい場合には（Ｓ１５でＹＥＳ）、ループ処理の配列がアラインされているか否かを調べる（Ｓ１６）。配列がアラインされているか否かの判断は、プラグマやコンパイルオプション等によりアラインされているとの指示があるか否かにより判断される。【００４３】  配列がアラインされていない場合には（Ｓ１７でＮＯ）、「ＬＢ＊ＬＣ／ＩＣ」がＣＳよりも大きいか否かについて判断する（Ｓ１６）。ここで、ＬＣは、レイテンシのサイクル数を示し、ＩＣは１イタレーションあたりのサイクル数を示す。「ＬＣ／ＩＣ」は、ループを複数の最内ループに分割した場合の各ループのループ回数を示しており、「ＬＢ＊ＬＣ／ＩＣ」は、各ループでのアクセス容量を示している。【００４４】  「ＬＢ＊ＬＣ／ＩＣ」がラインサイズＣＳよりも大きい場合には、（Ｓ１６でＹＥＳ）、分割後の各ループ処理では１ラインサイズ以上の要素の参照が行われる。このため、分割要因をサイクルとし、各ループ処理を二重ループ化した際の最内ループのループ回数ＤＴを次式（１）に従い導出する（Ｓ１８）。【００４５】
2005078579.tif 000002
「ＬＢ＊ＬＣ／ＩＣ」がラインサイズＣＳ以下の場合（Ｓ１６でＮＯ）または配列がアラインされている場合には（Ｓ１７でＹＥＳ）、分割要因をサイズとし、各ループ処理を二重ループ化した際の最内ループのループ回数ＤＴを次式（２）に従い導出する（Ｓ１９）。【００４６】
2005078579.tif 000003
最内ループのループ回数ＤＴが導出処理（Ｓ１８またはＳ１９）後、最内ループのループ回数ＤＴが１よりも大きいか否か判断される（Ｓ２０）。ＤＴが１の場合には（Ｓ２０でＮＯ）、最内ループのループ回数ＤＴが１回であるため、ループを二重ループに構造変換する必要がない。このため、ループ構造変換処理（Ｓ５）を終了させる。【００４７】  最内ループのループ回数ＤＴが２以上の場合には（Ｓ２０でＹＥＳ）、ループを二重ループに構造変換した場合の外側のループ構造が作成される（Ｓ２１）。外側ループ構造を生成する際に、ピーリング処理が必要か否かを判断する（Ｓ２２）。ピーリング処理およびピーリング処理が必要か否かの判断方法については後述する。【００４８】  ピーリング処理が必要な場合には（Ｓ２２でＮＯ）、ピーリング処理を行い、ピーリングコードを生成する（Ｓ２４）。その後、コンパイルオプション「−Ｏ」または「−Ｏｓ」による指定があるか否かを調べる（Ｓ２５）。ここで、コンパイルオプション「−Ｏ」は、プログラムサイズおよび実行処理速度ともに平均的なアセンブラコードをコンパイラに出力させるための指示である。コンパイルオプション「−Ｏｓ」は、プログラムサイズ抑制を重視したアセンブラコードをコンパイラに出力させるための指示である。【００４９】  ピーリング処理する必要がないか（Ｓ２２でＹＥＳ）またはコンパイルオプション「−Ｏ」または「−Ｏｓ」の指定がない場合には（Ｓ２５でＮＯ）、内側ループ（最内ループ）のループ回数の条件式を生成する（Ｓ２３）。【００５０】  コンパイルオプション「−Ｏ」または「−Ｏｓ」の指定がある場合には（Ｓ２５でＹＥＳ）、ピーリングされたループ処理を二重ループに畳み込み、最内ループのループ回数の条件式を生成する（Ｓ２６）。【００５１】  最内ループのループ回数条件生成処理（Ｓ２３、Ｓ２６）の後、最内ループにおける参照の対象配列は１つであるか否か調べられる（Ｓ２７）。最内ループにおける参照の対象配列が１つの場合には、（Ｓ２７でＹＥＳ）、ループ構造変換処理（Ｓ５）を終了する。【００５２】  最内ループにおける参照の対象配列が２つ以上ある場合には（Ｓ２７でＮＯ）、最内ループの分割個数を導出し、分割後の各最内ループのループ回数の比率を決定する（Ｓ２８）。その後、分割後の最内ループ回数ＤＴを分割個数で割った値が１よりも大きいか否か判断する（Ｓ２９）。すなわち、当該値が１以下の場合には（Ｓ２９でＮＯ）、分割後の各ループ回数が１回以下であるため、分割する意味がない。このため、ループ構造変換処理（Ｓ５）を終了させる。【００５３】  当該値が１よりも大きい場合には（Ｓ２９でＹＥＳ）、分割後の各ループ回数が２回以上である。この場合には、コンパイルオプション「−Ｏ」または「−Ｏｔ」による指定があるか否かを調べる（Ｓ３０）。コンパイルオプション「−Ｏｔ」は、実行処理速度向上を重視したアセンブラコードをコンパイラに出力させるための指示である。【００５４】  コンパイルオプション「−Ｏ」または「−Ｏｓ」による指定がある場合には（Ｓ３０でＹＥＳ）、後述する実行処理速度向上を重視したコピー型内側ループ分割処理（Ｓ３１）を実行し、ループ構造変換処理（Ｓ５）を��了する。【００５５】  コンパイルオプション「−Ｏ」または「−Ｏｓ」による指定がない場合には（Ｓ３０でＮＯ）、後述するプログラムサイズ抑制を重視した条件型内側ループ分割処理（Ｓ３２）を実行し、ループ構造変換処理（Ｓ５）を終了する。【００５６】  図７は、コピー型内側ループ分割処理（図６のＳ３１）の詳細を示すフローチャートである。【００５７】  最内ループのループ回数ＤＴを分割個数で割った値を細分割後内側ループ回数とする（Ｓ４１）。次に、内側ループを分割個数分だけ複製し、生成する（Ｓ４２）。その後、細分割後の各内側ループ回数を細分割後内側ループ回数に修正する（Ｓ４３）。さらに、ＤＴを分割個数で割った剰余を細分割後の先頭ループのループ回数に加算し（Ｓ４４）、コピー型内側ループ分割処理を終了する。【００５８】  図８は、条件型内側ループ分割処理（図６のＳ３２）の詳細を示すフローチャートである。【００５９】  最内ループのループ回数ＤＴを分割個数で割った値を細分割後内側ループ回数とする（Ｓ５１）。次に、内側ループ回数条件の切換えｓｗｉｔｃｈテーブルを生成する（Ｓ５２）。すなわち、内側ループ回数を順次切り替えるように、Ｃ言語で言うところのｓｗｉｔｃｈ文を生成する。なお、ｉｆ文であってもよい。【００６０】  テーブル生成後、細分割後の各内側ループ回数条件を細分割後の内側ループ回数に修正する（Ｓ５３）。その後、ＤＴを分割個数で割った剰余を細分割後の先頭ループの回数条件に加算し（Ｓ５４）、条件型内側ループ分割処理を終了する。【００６１】  図９は、プリフェッチ命令配置処理（図５のＳ６）の詳細を示すフローチャートである。【００６２】  プリフェッチ命令配置処理では、すべてのループについて以下の処理を繰返す（ループＡ）。まず、着目しているループが命令挿入対象のループであるか否かを調べる（Ｓ６１）。命令挿入対象のループであるか否かの情報は、ループ構造変換部１８６の解析結果より取得される。【００６３】  命令挿入対象のループの場合には（Ｓ６１でＹＥＳ）、そのループに対して条件型ループ分割が行われているか否かを調べる（Ｓ６２）。条件型ループ分割が行われていれば、各条件文における命令挿入位置を解析し（Ｓ６３）、プリフェッチ命令を挿入する（Ｓ６４）。命令挿入対象のループに対して条件型ループ分割が行われていなければ（Ｓ６２でＮＯ）、そのループに対してコピー型ループ分割が行われているか否かを調べる（Ｓ６５）。コピー型ループ分割が行われていれば（Ｓ６５でＹＥＳ）、そのループの手前の命令挿入位置を解析する（Ｓ６６）。その後、プリフェッチ命令が挿入される（Ｓ６７）。ピーリングされたループの場合には（Ｓ６８でＹＥＳ）、当該ループの手前に命令挿入するように命令挿入位置が解析され（Ｓ６９）、その位置にプリフェッチ命令が挿入される（Ｓ７０）。【００６４】  図１０は、プリフェッチ命令挿入処理（図９のＳ６４、Ｓ６７およびＳ７０）の詳細を示すフローチャートである。【００６５】  命令挿入処理では、挿入命令、挿入位置、挿入アドレス等からなる情報リストがすべて空になるまで以下を繰返す（ループＢ）。【００６６】  プリフェッチ命令を挿入しようとしている配列要素がアライ��済みであるか否かを判断する（Ｓ７２）。アラインされていなければ（Ｓ７２でＮＯ）、サイクル要因に従ってループ分割されたものであるのか、サイズ要因に従ってループ分割されたものであるのかを調べる（Ｓ７３）。【００６７】  アライン済みであるか（Ｓ７２でＹＥＳ）またはサイクル要因でループ分割されたものであれば（Ｓ７３でＹＥＳ）、１ライン先のデータをプリフェッチする命令を挿入する（Ｓ７４）。アラインされておらず、かつサイズ要因でループ分割されたものであれば（Ｓ７３でＮＯ）、２ライン先のデータをプリフェッチする命令を挿入する（Ｓ７５）。最後に、解析済みの情報を情報リストから削除する（Ｓ７６）。【００６８】［コンパイルオプション］
コンパイラシステム１４８では、コンパイラに対するコンパイルオプションとして、オプション「−ｆｎｏ−ｌｏｏｐ−ｔｉｌｉｎｇ−ｄｐｒｅｆ」が用意される。このオプションが指定されれば、プラグマの指定に関わらず、ループに対する構造変換は行わない。本オプションの指定がなければ、構造変換の実施はプラグマ指定の有無に従う。【００６９】［プラグマ指定］
本指定は、直後のループに対するものである。【００７０】  プラグマ「＃ｐｒａｇｍａ＿ｌｏｏｐ＿ｔｉｌｉｎｇ＿ｄｐｒｅｆ変数名［，変数名］」により変数が指定された場合には、プラグマ指定された変数のみに着目してループ分割を行う。指定する変数は、配列でも、ポインタでもよい。【００７１】  プラグマ「＃ｐｒａｇｍａ＿ｌｏｏｐ＿ｔｉｌｉｎｇ＿ｄｐｒｅｆ＿ａｌｌ」によりループが指定された場合には、ループ内で参照される配列の全てに着目して構造変換が行われる。【００７２】  以下、いくつかの具体的曲面におけるループ分割処理について説明する。なお、以降の処理では、説明の簡単化のためＣ言語によるプログラム記述を行っているが、実際には中間言語による最適化処理が行われる。【００７３】［シンプルループ分割］
図１１は、ピーリングが必要ない場合のシンプルループ分割処理について説明するための図である。【００７４】  図１１（ａ）に示すようなソースプログラム２８２が入力された場合について考える。このソースプログラム２８２では、配列Ａの要素が順次参照され、変数ｓｕｍに加算される。ここで、配列Ａの各要素のサイズは４バイトであるものとし、キャッシュの１ラインサイズは１２８バイト（以降の説明でも、キャッシュのラインサイズは１２８バイトであるものとする。）であるものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。また、ソースプログラム２８２に含まれるループのイテレーションの回数１２８回は、３２の整数倍である。このため、ソースプログラム２８２は、図１１（ｂ）のプログラム２８４に示すように、二重ループに構造変換することができる。すなわち、最内ループでは３２回の繰り返し処理を行い、その外のループでは、最内ループを４回繰返すループ処理を行う。最内ループ処理ではキャッシュの１ライン分のデータが参照される。その後、図１１（ｃ）のプログラム２８６に示されるように、最内ループの実行前に、プリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））が挿入される。プリフェッチ命令を挿入することにより、最内ループ実行時には、当該ループで参照される配列Ａの要素がキャッシュに乗っていることになる。【００７５】  図１２〜図１５は、ピーリングが不要なシンプルループ分割処理における中間言語の推移を説明するための図である。【００７６】  図１２は、図１１（ａ）と同様に、ピーリングが必要のない場合のソースプログラムの一例を示す図である。図１３は、図１２に示したソースプログラム２４０に対応する中間言語のプログラムである。［ＢＧＮＢＢＬＫ］と［ＥＮＤＢＢＬＫ］とで挟まれた内部の命令列が１つの基本ブロックに対応しており、［ＢＧＮＢＢＬＫ］Ｂ１で始まる基本ブロックがｆｏｒループの直前までの処理を示しており、［ＢＧＮＢＢＬＫ］Ｂ２で始まる基本ブロックがｆｏｒループを示しており、［ＢＧＮＢＢＬＫ］Ｂ３で始まる基本ブロックがｆｏｒループの後の処理を示している。【００７７】  図１４は、図１３に示された中間言語のプログラムを二重ループに構造変換した後の中間言語のプログラムを示している。［ＢＧＮＢＢＬＫ］Ｂ２で始まる基本ブロックが最内ループに対応しており、［ＢＧＮＢＢＬＫ］Ｂ４および［ＢＧＮＢＢＬＫ］Ｂ５で始まるループがその外側のループに対応している。【００７８】  図１５は、図１４に示された中間言語のプログラムにプリフェッチ命令を挿入した後の中間言語のプログラムを示している。プログラム２７０では、［ＢＧＮＢＢＬＫ］Ｂ４で始まる基本ブロックの内部にプリフェッチ命令（ｄｐｒｅｆ）が新たに挿入されている。【００７９】  図１６は、ピーリングが必要な場合のシンプルループ分割処理について説明するための図である。【００８０】  図１６（ａ）に示すようなソースプログラム２９２が入力された場合について考える。このソースプログラム２９２では、配列Ａの要素が順次参照され、変数ｓｕｍに加算される。ここで、配列Ａの各要素のサイズは４バイトであるものとする。すなわち、キャッシュ���１ラインには配列Ａの要素が３２個記憶される。また、ソースプログラム２９２に含まれるループのイテレーションの回数は１４０回であるものとする。すなわち、１ラインに記憶される配列Ａの要素数３２で割った場合に余りが出る数である。【００８１】  このような場合には、図１６（ｂ）に示すプログラム２９４のように、１４０を３２で割った余りのループ回数をピーリングし、それ以外の部分を図１１（ｂ）と同様に二重ループ構造に構造変換する。その後、ピーリングされた部分を二重ループ構造に含ませるためのピーリング畳み込み処理を行い、図１６（ｃ）に示すようなプログラム２９６が得られる。すなわち、通常状態では最内ループで３２回の繰り返し処理が行われ、最後に最内ループが実行される場合には、残りの１２（＝１４０−１２８）回の繰り返し処理が行われる。その後、図１６（ｄ）のプログラム２９８に示されるように、最内ループの実行前に、プリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））が挿入される。【００８２】［複数配列アクセスが存在する場合（ピーリング必要なし）］
図１７は、ループ内に複数の配列アクセスが存在する場合のループ分割処理について説明するための図である。【００８３】  図１７（ａ）に示すようなソースプログラム３０１が入力された場合について考える。このソースプログラム３０１では、配列Ａおよび配列Ｂの要素が順次参照され、当該要素同士の積が変数ｓｕｍに加算される。ここで、配列Ａおよび配列Ｂの各要素はそれぞれ４バイトであるものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。または、配列Ｂの要素が３２個記憶される。すなわち、１ラインに格納される要素数は配列Ａと配列Ｂとで同じである。また、ソースプログラム３０１に含まれるループのイテレーションの回数１２８回は、３２の整数倍である。このため、ソースプログラム３０１は、図１７（ｂ）のプログラム３０２に示すように、ピーリングをすることなく二重ループに構造変換することができる。【００８４】  複数配列アクセスが存在する場合の二重ループ構造は、コピー型と呼ばれる実行処理速度を向上させるための最適化と、条件型と呼ばれるプログラムサイズを小さくするための最適化との二種類がある。【００８５】  まず、コピー型の最適化について説明する。プログラム３０２に含まれる最内ループのループ回数を配列Ａと配列Ｂとの要素の大きさの比で分割する。ここでは、配列Ａと配列Ｂとはともに同じ要素の大きさである。したがって、図１７（ｃ）に示すプログラム３０３のように最内ループを二等分し、ループ回数が１６回の最内ループ２つに分割する。次に、図１７（ｄ）のプログラム３０４に示すように、各最内ループの直前にプリフェッチ命令を挿入する。最初の最内ループの直前には、１ライン分の配列Ａの要素をプリフェッチするためのプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））が挿入され、２番目の最内ループの直前には、１ライン分の配列Ｂの要素をプリフェッチするためのプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＋３２］））が挿入される。【００８６】  このようにプリフェッチ命令間にループ処理を挿入させることにより、異なる配列に対するプリフェッチ命令が連続することが無くなり、プリフェッチ命令実行によるレイテンシを隠蔽することができる。このため、実行処理速度を向上させることができる。【００８７】  次に、条件型の最適化について説明する。条件型の場合も、コピー型の場合と同様にして最内ループのループ回数を配列Ａと配列Ｂとの要素の大きさの比で分割する。ただし、プログラム３０３のように最内ループを２つ並べるのではなく、図１７（ｅ）に示すプログラム３０５のように最内ループの個数は１つであり、そのループ回数を条件分岐させるようにしている。すなわち、変数Ｋ＝１の場合と、Ｋ＝０の場合とで最内ループのループ回数Ｎを変えるようにしている。ただし、この例では変数Ｋの値に関係なく最内ループの回数Ｎは１６回となっている。次に、図１７（ｆ）に示すプログラム３０６のように、Ｋ＝１の場合には配列Ａの要素を１ライン分プリフェッチし、Ｋ＝０の場合には配列Ｂの要素を１ライン分プリフェッチするように条件分岐式およびプリフェッチ命令の挿入が行われる。なお、ここでは、最適化によりループ回数Ｎは即値１６に置��換えられている。【００８８】  このように、最内ループの個数を１つにし、条件分岐式で最内ループのループ回数およびプリフェッチ命令を変えるようにすることにより、最終的に生成される機械語命令のプログラムサイズを小さくすることができる。ただし、条件分岐処理があるため、コピー型に比べて処理速度が多少遅くなる可能性がある。【００８９】［複数配列アクセスが存在する場合（ピーリング必要）］
図１８は、ループ内に複数の配列アクセスが存在する場合のループ分割処理について説明するための図である。【００９０】  図１８（ａ）に示すようなソースプログラム３１１が入力された場合について考える。このソースプログラム３１１では、配列Ａおよび配列Ｂの要素が順次参照され、当該要素同士の積が変数ｓｕｍに加算される。ここで、配列Ａおよび配列Ｂの各要素はそれぞれ４バイトであるものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。または、配列Ｂの要素が３２個記憶される。すなわち、１ラインに格納される要素数は配列Ａと配列Ｂとで同じである。また、ソースプログラム３１１に含まれるループのイタレーションの回数は１４０回であるものとする。【００９１】  したがって、ソースプログラム３１１を二重ループに構造変換する場合には、図１６（ｂ）に示したプログラム２９４と同様、図１８（ｂ）に示すようにピーリング処理されたプログラム３１２が生成される。【００９２】  コピー型の最適化を行う際には、配列Ａと配列Ｂとの要素の大きさの比で最内ループを分割する。すると、図１８（ｃ）に示すプログラム３１３が生成される。次に、図１８（ｄ）のプログラム３１４に示すように、最初の最内ループの直前には、１ライン分の配列Ａの要素をプリフェッチするためのプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））が挿入され、２番目の最内ループの直前には、１ライン分の配列Ｂの要素をプリフェッチするためのプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＋３２］））が挿入される。なお、ピーリング処理された最終ループの直前にはプリフェッチ命令は挿入されない。これは、その前の二重ループ処理におけるプリフェッチ命令実行により所望のデータがキャッシュにプリフェッチされているからである。【００９３】  条件型の最適化を行う際には、プログラム３１２に対してピーリング畳み込み処理を行い、図１８（ｅ）に示されるようなプログラム３１５を得る。ピーリング畳み込み処理は、図１６を参照して説明したものと同様である。次に、最内ループのループ回数を配列Ａと配列Ｂとの要素の大きさの比で分割し、当該ループ回数を条件分岐させるように図１８（ｆ）に示すプログラム３１６を作成する。プログラム３１６においては、変数Ｋの値を交互に変更させ、変数Ｋの値に対応するようにループカウンタＮの値を変化させる。次に、図１８（ｇ）のプログラム３１７に示すように、Ｋの値の変化に伴い、配列Ａおよび配列Ｂの要素を１ライン分ずつ交互にプリフェッチするように、条件分岐式中にプリフェッチ命令を挿入する。【００９４】  このように、ピーリングが必要な場合であっても、コピー型の場合にはピーリングの部分を二重ループとは別のループにし、条件型の場合には、条件分岐式によりピーリングの場合のループカウンタの回数を変えるようにすることにより、ループ内に複数の配列アクセスがあり、かつピーリングが必要な場合であっても、プリフェッチによるレイテンシを考慮した最適化を行うことができる。【００９５】［サイズが異なる複数配列アクセスが存在する場合（ピーリング必要なし）］
図１９は、ループ内に複数の配列アクセスが存在し、かつ配列の要素のサイズがすべて同じではない場合のループ分割処理について説明するための図である。【００９６】  図１９（ａ）に示すようなソースプログラム３２１が入力された場合を考える。ここで、配列Ａの要素は４バイト、配列Ｂの要素は２バイトとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個、配列Ｂの要素が６４個記憶される。【００９７】  この場合、要素サイズの小さい配列Ｂに着目し、配列Ｂの要素に応じたループの構造変換を行う。すなわち、図１９（ｂ）のプログラム３２２のように、最内ループのループ回数を１ラインに収まるキャッシュＢの要素数６４にし、二重ループに構造変換する。最内ループでは、配列Ｂに関しては１ライン分の要素が消費されるが、配列Ａに関しては２ライン分の要素が消費されることになる。このため、最内ループ処理を実行するためには合計３ライン分のデータが必要になる。【００９８】  このため、コピー型の最適化を行う際には、図１９（ｃ）のプログラム３２３に示すように、最内ループを３つに分割し、図１９（ｄ）のプログラム３２４に示すように、各最内ループの直前にプリフェッチ命令を挿入する。ここでは、１番目の最内ループの直前には、２ライン先の配列Ａの要素をプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋６４］））を挿入し、２番目の最内ループの直前には３ライン先の配列Ａの要素をプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋９６］））を挿入し、３番目の最内ループの直前には１ライン先の配列Ｂの要素をプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＋６４］））を挿入している。また、３つの最内ループのループ回数を処理順に２２、２１および２１としている。これは、最外ループの条件分岐判断が３番目の最内ループ実行後に行われるため、３番目の最内ループのループ回数を少なくすることにより、全体としての処理速度を向上させるためである。【００９９】  また、条件型の最適化を行う際には、図１９（ｅ）のプログラム３２５に示すように、１回の最内ループ処理につき、変数Ｋの値を０から２までの範囲内で更新させ、変数Ｋの値による条件分岐処理により最内ループのループ回数Ｎを２２、２１および２１のうちのいずれかに設定する。その後、ループ回数Ｎの最内ループを実行させる。次に、図１９（ｆ）のプログラム３２６に示すように、変数Ｋの値が０の場合にはプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋６４］））を実行させ、変数Ｋの値が１の場合にはプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋９６］））を実行させ、変数Ｋの値が２の場合にはプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＋６４］））を実行させるように最適化を行う。【０１００】［サイズが異なる複数配列アクセスが存在する場合（ピーリング必要）］
図２０は、ループ内に複数の配列アクセスが存在し、かつ配列の要素のサイズがすべて同じではない場合のループ分割処理について説明するための図である。【０１０１】  図２０（ａ）に示すソースプログラム３３１は、図１９（ａ）に示したソースプログラム３２１とループ回数が異なるのみである。したがって、ソースプログラム３２１と同様、配列Ａの要素は４バイト、配列Ｂの要素は２バイトである。図２０（ｂ）に示すように、ソースプログラム３２１のループを二重ループに構造変換し、ループ回数１４０を配列Ｂの１ライン分の要素数６４で割った余りをピーリング処理すると、プログラム３２２が得られる。コピー型の最適化処理を行う場合には、図１９（ｃ）および図１９（ｄ）を参照して説明したように、二重ループの最内ループを３分割し、プリフェッチ命令を挿入することにより、図２０（ｃ）に示すプログラム３３３が得られる。条件型の最適化処理を行う場合には、図１９（ｅ）および図１９（ｆ）を参照して説明したように、条件分岐式によりループ回数およびプリフェッチ命令を制御し、最終的に図２０（ｅ）に示すプログラム３３５が得られる。【０１０２】［ストライドが異なる複数配列アクセスが存在する場合］
図２１は、ループ内にストライドが異なる複数の配列アクセスが存在する場合のループ分割処理について説明するための図である。【０１０３】  ストライドとは、ループ処理における配列要素の増分値（アクセス幅）のことを示す。図２１（ａ）に示すようなソースプログラム３４１が入力された場合を考える。ここで、配列Ａの要素および配列Ｂの要素はともに４バイトであるものとする。ソースプログラム３４１では、ループのイタレーションごとに、配列Ａの要素は１ずつ増加するのに対し、配列Ｂの要素は２ずつ増加する。すなわち、配列Ｂのアクセス幅は配列Ａのアクセス幅の２倍である。最小アクセス幅の配列Ａに着目すると、１ラインには配列Ａの要素が３２個収まる。このため、最内ループのループ回数を３２回とした二重ループへの構造変換を行うと、図２１（ｂ）に示すプログラム３４２が得られる。最内ループでは、配列Ａに関しては１ライン分の要素が消費されるが、配列Ｂに関しては２ライン分の要素が消費されることになる。このため、最内ループ処理を実行するためには合計３ライン分のデータが必要になる。【０１０４】  よって、コピー型の最適化を行う際には、図２１（ｃ）のプログラム３４３に示すように、最内ループを３つに分割し、図２１（ｄ）のプログラム３４４に示すように、各最内ループの直前にプリフェッチ命令を挿入する。ここでは、１番目の最内ループの直前には、１ライン先の配列Ａの要素をプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を挿入し、２番目の最内ループの直前には２ライン先の配列Ｂの要素をプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＊２＋６４］））を挿入し、３番目の最内ループの直前には３ライン先の配列Ｂの要素をプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＊２＋９６］））を挿入している。【０１０５】  また、条件型の最適化を行う際には、図２１（ｅ）のプログラム３４５に示すように、１回の最内ループ処理につき、変数Ｋの値を０から２までの範囲内で更新させ、変数Ｋの値による条件分岐処理により最内ループのループ回数Ｎを１１、１１および１０のうちのいずれかに設定する。その後、ループ回数Ｎの最内ループを実行させる。次に、図２１（ｆ）のプログラム３４６に示すように、変数Ｋの値が０の場合にはプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を実行させ、変数Ｋの値が１の場合にはプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＊２＋６４］））を実行させ、変数Ｋの値が２の場合にはプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＊２＋９６］））を実行させるように最適化を行う。【０１０６】［ループ回数が不定な場合］
図２２は、ループ回数が不定なループ処理のループ分割処理を説明するための図である。【０１０７】  図２２（ａ）に示すソースプログラム３５１が入力された場合を考える。ソースプログラム３５１に含まれるループ回数は変数Ｖａｌにより特定され、コンパイル時には不定である。しかし、最低１２８回は繰り返し処理が行われることがプラグマ指定「＃ｐｒａｇｍａ＿ｍｉｎ＿ｉｔｅｒａｔｉｏｎ＝１２８」により、保証されている。ここで、配列Ａは４バイトであるものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。【０１０８】  プラグマ指定に従い、ループ処理を最初の１２８回のループ処理と、それ以降の変数Ｖａｌで特定されるループ回数のループ処理とに分割し、それぞれをシンプルループの場合と同様に二重ループ化すると図２２（ｂ）に示すプログラム３５２が得られる。【０１０９】  コピー型の最適化処理を行う場合には、プログラム３５２の最内ループの直前に１ライン先の配列Ａの要素をプリフェッチするためのプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を挿入することにより、図２２（ｃ）に示すプログラム３５３が得られる。【０１１０】  条件型の最適化処理を行う場合には、後半のループ処理をピーリング畳み込みし、最外ループ回数が１２８回になるまでは、最内ループの回数を３２回にし、それ以降は最内ループの回数を（Ｖａｌ−１２８）回に設定する分岐命令を挿入する。すると、図２２（ｄ）に示すようなプログラム３５４が得られる。【０１１１】  最後に、最内ループの実行前にプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を挿入することにより図２２（ｅ）に示すようなプログラム３５５が得られる。【０１１２】  図２３は、ループ回数が不定なループ処理のループ分割処理を説明するための他の図である。【０１１３】  図２３（ａ）に示すソースプログラム３６１が入力された場合を考える。ソースプログラム３６１に含まれるループ回数は変数Ｎにより特定され、コンパイル時には不定である。また、ソースプログラム３６１は、ソースプログラム３５１と異なり、最低のループ回数を示すプラグマ指定がない。【０１１４】  ループ回数が小さなループ処理に対してループの構造変換を行い、最適化を行ったとしても、最適化の効果が表れにくい。このため、このような場合には、最適化の効果を高めるために、ループ回数があるしきい値よりも大きければ最適化されたループ処理を実行し、それ以外の場合には通常のループ処理を実行するようにする。例えば、あるしきい値を１０２４とした場合には、図２３（ｂ）のプログラム３６２に示されるように、ループ回数Ｎが１０２４を超える場合には、最初の１０２４回のループ処理については二重ループを実行し、残りの回数のループ処理については、ピーリングされたループ処理を行うようにする。また、ループ回数Ｎが１０２４以下の場合には、二重ループは実行せずに、ピーリングされたループ処理を実行するようにする。その後、二重ループの最内ループの直前にプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を挿入することにより図２３（ｃ）に示すような最適化されたプログラム３６３が生成される。【０１１５】［ループ分割が��要な場合］
図２４は、ループ分割が不要な場合の最適化処理を説明するための図である。図２４（ａ）に示すソースプログラム３７１が入力された場合には、ループ中で１ライン分のデータ（Ａ［ｉ］〜Ａ［ｉ＋３１］）を完全に使い切ってしまう。このような場合には、二重ループ化する必要はない。このため、図２４（ｂ）に示すプログラム３７２ようにループの先頭にループ内で使用されるデータの１ライン先のデータをプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を挿入することにより最適化が行われる。【０１１６】  また、ループ内の処理サイクル数がプリフェッチ命令で必要とされる処理サイクル数よりも大きいような場合にも、ループを二重化する必要はなく、ループの先頭にプリフェッチ命令を挿入してもプリフェッチ命令のレイテンシは隠蔽することができる。【０１１７】［ループ内でアクセスされる要素がアラインされていない場合］
図２５および図２６は、ループ内でアクセスされる要素が主記憶上で適切にアラインされていない場合のループ分割処理を説明するための図である。これまでの説明では、ループ内でアクセスされる要素が主記憶上で適切にアラインされている場合を想定して話を進めてきた。アラインされていることが予めプラグマや、コンパイルオプションの指定によりわかっている場合には、上述の例で説明したような最適化が行われる。【０１１８】  しかし、一般的にはコンパイラは、それらの要素がアラインされているか否かは実行時まではわからない。このため、コンパイラは、ループ内アクセス要素が主記憶上で適切にアラインされていないことを前提として最適化を行う必要がある。【０１１９】  すなわち、図２５（ａ）に示すようなソースプログラム３８１が与えられた場合に、配列Ａの要素サイズを４バイトとすると、図１１を参照して説明したシンプルループ分割と同様にして、最適化が行われる。ただし、要素がアラインされていないことを前提としているため、最内ループの前に挿入されるプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋６４］））は２ライン先の配列Ａの要素をプリフェッチ指定している。また、ループ処理に先立って、ループ内でアクセスされる配列の要素Ａ［０］〜Ａ［６３］を確保するために、プリフェッチ命令（ｄｐｒｅｆ（＆Ａ［０］）およびｄｐｒｅｆ（＆Ａ［３２］））がプリフェッチのレイテンシを十分隠蔽できる位置に挿入され、図２５（ｂ）に示すようなプログラム３８２が生成される。【０１２０】  また、図２６（ａ）に示されるようなソースプログラム３９１が与えられた場合には、図１６と同様にして、ピーリング処理された部分のループを畳み込んだ後に、２ライン先の配列Ａの要素をプリフェッチする命令（ｄｐｒｅｆ（＆Ａ［ｉ＋６４］））が挿入される。また、プログラム３８２と同様にプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［０］）およびｄｐｒｅｆ（＆Ａ［３２］））が挿入され、図２６（ｂ）に示すような最適化されたプログラム３９２が生成される。【０１２１】［動的アライン解析コードの挿入による構造変換分割］
図２７は、アラインされていない配列要素を動的に特定して、ループ処理の最適化を行う処理について説明するための図である。図２７（ａ）に示すソースプログラム４０１が入力された場合を考える。ここで、配列Ａの要素は４バイトであるものとする。【０１２２】  配列Ａの先頭アドレス（要素Ａ［０］のアドレス）の所定のビットがキャッシュのラインを示しており、そのビット内のさらにあるビットは、ラインの先頭からのオフセットを示している。したがって、「Ａ＆Ｍａｓｋ」というビット同士の論理演算を行うことにより、ラインの先頭からのオフセットを取り出すことができる。ここで、マスク値Ｍａｓｋはあらかじめ定められた値である。配列Ａの先頭アドレスから取り出されたオフセット値を予め定められた補正値Ｃｏｒだけ右シフトすることにより、配列Ａの先頭要素Ａ［０］が１ライン内で先頭から何番目に位置しているかがわかる。よって、次式（３）にしたがって、ライン上でアラインされていない要素の数ｎを求めることができる。【０１２３】
2005078579.tif 000004
すなわち、図２８に示すように、キャッシュ４３１にフェッチした場合に、アラインされない配列Ａの要素（Ａ［０］〜Ａ［ｎ−１］）とアラインされる配列Ａの要素とが区別されることになる。【０１２４】  したがって、図２７（ｂ）のプログラム４０２に示すように、式（３）に従いアラインされていない配列Ａの要素数ｎを求める。次に、要素数ｎに従って、アラインされていない配列Ａの要素（Ａ［０］〜Ａ［ｎ−１］）についてのループ処理を行う。その後、アラインされている配列Ａの要素（Ａ［ｎ］以降の要素）については、図１１に示したシンプルループ分割の場合と同様に二重ループ化を行う。【０１２５】  その後、ピーリングされているループ４０５について、畳み込み処理を行うと、図２７（ｃ）に示すようなプログラム４０３が生成される。また、図２７（ｄ）に示すように、プリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を挿入することにより、最適化されたプログラム４０４が得られる。【０１２６】［プロファイル情報を用いた構造変換分割］
図２９は、アラインされていない配列要素をプロファイル情報を用いて特定し、ループ処理の最適化を行う処理について説明するための図である。アラインされていない配列の要素数を図２７のように計算から求めるのではなく、プロファイル情報から取得する。取得したアラインされていない配列の要素数Ｎに基づいて、図２７に示したのと同様の処理を行い、図２９（ａ）に示すソースプログラム４１１を図２９（ｂ）に示すプログラム４１２のように変換する。その後、ピーリングされたループ部分を畳み込み、図２９（ｃ）に示すプログラム４１３を得る。最後に、図２９（ｄ）に示すプリフェッチ命令を挿入することにより最適化されたプログラム４１４を得る。【０１２７】［最内ループ以外のループに対する構造変換］
図３０は、最内ループ以外のループに対する構造変換について説明するための図である。【０１２８】  図３０（ａ）に示すソースプログラム４２１が与えられた場合を考える。ソースプログラム４２１では、二重ループ処理が行われており、最内ループ処理４２４で参照される配列Ａの要素は１バイトであるものとする。最内ループ処理４２４のループ回数は４回であるため、最内ループ処理４２４では配列Ａの要素が４バイト分参照される。したがって、最内ループ処理４２４で参照される要素のバイト数が小さいため、このような場合には、最内ループ処理４２４を１つの固まりとして考え、最外ループを、図３０（ｂ）に示すプログラム４２２のように、二重ループに構造変換する。その後、２番目のループ処理の実行前にキャッシュの１ライン分の配列Ａの要素をプリフェッチする命令（ｄｐｒｅｆ（＆Ａ［ｊ＋１２８］））が挿入され、図３０（ｃ）に示すような最適化されたプログラム４２３が得られる。【０１２９】［プラグマ「＃ｐｒａｇｍａ＿ｌｏｏｐ＿ｔｉｌｉｎｇ＿ｄｐｒｅｆ変数名［，変数名］」による変数指定］
図３１は、プラグマ「＃ｐｒａｇｍａ＿ｌｏｏｐ＿ｔｉｌｉｎｇ＿ｄｐｒｅｆ変数名［，変数名］」により変数が指定された場合の最適化処理について説明するための図である。図３１（ａ）に示すように、プラグマ「＃ｐｒａｇｍａ＿ｌｏｏｐ＿ｔｉｌｉｎｇ＿ｄｐｒｅｆ  ｂ」との指定がソースプログラム中に含まれる場合には、ループ内の配列ｂのみに着目して構造変換が行われ、配列ａは無視される。従って、図３１（ｂ）に示すような二重ループ化が実行され、配列ｂをプリフェッチする命令のみが挿入される。【０１３０】  以上説明したように、本実施の形態に係るコンパイラシステムによると、ループ処理を二重化し、最内ループの外側でプリフェッチ命令を実行するようにしている。このため、無駄なプリフェッチ命令の発行を防ぐことができ、プログラム実行時の処理速度を向上させることができる。また、ループ処理を二重化することにより、プリフェッチ命令を実行してから次のプリフェッチ命令を実行するまでのサイクル数を確保することができる。このため、レイテンシを隠蔽し、インターロックを防ぐことができる。【０１３１】  以上、本発明の実施の形態に係るコンパイルシステムについて、実施の形態に基づいて説明したが、本発明は、この実施の形態に限定されるものではない。【０１３２】  例えば、命令最適配置部１８７で配置される命令は、プリフェッチ命令に限られず、通常のメモリアクセス命令や外部処理を起動してその処理結果を待つ命令などのような応答待ち命令、実行した結果、結果的にインターロックを起こす可能性のある命令、実行後に所定の資源が参照可能になるまでに複数サイクルを要する命令などであってもよい。応答待ち命令には、常に応答を待つ命令の他に、応答を待つ場合と待たない場合とがある命令も含む。【０１３３】  また、キャッシュを備えないコンピュータのＣＰＵをターゲットプロセッサとして、各種処理のレイテンシを隠蔽し、インターロックを防ぐようなコードを出力するコンパイルシステムであってもよい。【０１３４】  さらに、ＣＰＵで実行させる機械語命令列を逐次解釈しながら、本実施の形態で説明したループ構造変換等の処理を実行するＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）として実現してもよい。【０１３５】  また、以下に示すようなＰｒｅＴｏｕｃｈ命令のように、インターロックを起こす可能性のない命令に対しても本発明は適用可能である。ＰｒｅＴｏｕｃｈ命令とは、引数で指定される変数を記憶するための領域をキャッシュ上に事前に確保するのみの処理を行う命令である。以下に、ループの構造変換を行い、ＰｒｅＴｏｕｃｈ命令を挿入する処理について説明する。【０１３６】［シンプルループ分割］
図３２は、ＰｒｅＴｏｕｃｈ命令挿入時において、対象領域がキャッシュサイズでアラインされており、ピーリングが必要ない場合のシンプルループ分割処理について説明するための図である。【０１３７】  図３２（ａ）に示すようなソースプログラム５０２が入力された場合について考える。このソースプログラム５０２では、ループ回数ｉと変数ｖａｌとの演算結果（乗算結果）を配列Ａの要素に順次代入する処理を定義している。ここで、配列Ａの各要素のサイズは４バイトであるものとし、キャッシュの１ラインサイズは１２８バイト（以降の説明でも、キャッシュのラインサイズは１２８バイトであるものとする。）であるものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。また、ソースプログラム５０２に含まれるループのイテレーションの回数１２８回は、３２の整数倍である。【０１３８】  このため、ソースプログラム５０２は、図３２（ｂ）のプログラム５０４に示すように、二重ループに構造変換することができる。すなわち、最内ループでは３２回の繰り返し処理を行い、その外のループでは、最内ループを４回繰返すループ処理を行う。最内ループ処理ではキャッシュの１ライン分のデータが配列Ａに代入される。その後、図３２（ｃ）のプログラム５０６に示されるように、最内ループの実行前に、キャッシュ領域確保命令（ＰｒｅＴｏｕｃｈ（＆Ａ［ｉ］））が挿入される。ＰｒｅＴｏｕｃｈ命令を挿入することにより、最内ループ実行時には、当該ループで定義される配列Ａの要素がキャッシュ領域に確保されていることになる。これにより、不要なメインメモリからのデータ転送を引き起こすことがなくなり、バス占有率を軽減することができるようになる。【０１３９】  図３３は、ＰｒｅＴｏｕｃｈ命令挿入時におけるピーリングが必要な場合のシンプルループ分割処理について説明するための図である。【０１４０】  図３３（ａ）に示すようなソースプログラム５１２が入力された場合について考える。このソースプログラム５１２では、ループ回数ｉと変数ｖａｌとの演算結果（乗算結果）が配列Ａの要素に順次代入する処理を定義している。ここで、配列Ａの各要素のサイズは４バイトでキャッシュサイズにアラインされているものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。また、ソースプログラム５１２に含まれるループのイテレーションの回数は１４０回であるものとする。すなわち、１ラインに記憶される配列Ａの要素数３２で割った場合に余りが出る数である。【０１４１】  このような場合には、図３３（ｂ）に示すプログラム５１４のように、１４０を３２で割った余りのループ回数をピーリングし、それ以外の部分を図３２（ｂ）と同様に二重ループ構造に構造変換する。その後、ピーリングされた部分を二重ループ構造に含ませるためのピーリング畳み込み処理を行い、図３３（ｃ）に示すようなプログラム５１６が得られる。すなわち、通常状態では最内ループで３２回の繰り返し処理が行われ、最後に最内ループが実行される場合には、残りの１２（＝１４０−１２８）回の繰り返し処理が行われる。その後、図３３（ｄ）のプログラム５１８に示されるように、最内ループの実行前に��キャッシュ領域確保命令（ＰｒｅＴｏｕｃｈ（＆Ａ［ｉ］））が挿入される。ただし、領域確保処理は、１ライン単位で行なわれる。このため、オブジェクトＡ以外の領域を確保する可能性がある最後の最内ループ実行時には、ＰｒｅＴｏｕｃｈ命令を発行しないようにし、オブジェクトＡ以外の領域を確保しないようにする。【０１４２】［動的アライン解析コードの挿入による構造変換分割］
図３４は、アラインされていない配列要素を動的に特定して、ループ処理の最適化を行う処理について説明するための図である。図３４（ａ）に示すソースプログラム５２２が入力された場合を考える。ここで、配列Ａの要素は４バイトであるものとする。【０１４３】  配列Ａの先頭アドレス（要素Ａ［０］のアドレス）の所定のビットがキャッシュのラインを示しており、そのビット内のさらにあるビットは、ラインの先頭からのオフセットを示している。したがって、「Ａ＆Ｍａｓｋ」というビット同士の論理演算を行うことにより、ラインの先頭からのオフセットを取り出すことができる。ここで、マスク値Ｍａｓｋはあらかじめ定められた値である。ここでは、［Ｍａｓｋ＝０ｘ７Ｆ］としている。ループ初回にアクセスされる配列Ａの要素のアドレスから取り出されたオフセット値を、マスク値Ｍａｓｋから減算を行い、予め定められた補正値Ｃｏｒだけ右シフトすることにより、配列Ａの要素Ａ［Ｘ］が１ライン内で先頭から何番目に位置しているかがわかる。よって、次式（４）にしたがって、ライン上でアラインされていない要素の数ＰＲＬＧを求めることができる。【０１４４】
2005078579.tif 000005
さらに、ループの最後に参照される配列Ａの要素（Ａ［Ｙ−１］）の次の要素（Ａ［Ｙ］）が１ライン内で先頭から何番目に位置しているかを、次式（５）に従って求めることにより、１ラインを満たしきれていない要素の数ＥＰＬＧで求めることができる。【０１４５】
2005078579.tif 000006
さらに、１ライン分の処理を余ることなく行うループ回数ＫＲＮＬを次式（６）に従って求めることができる。【０１４６】
2005078579.tif 000007
すなわち、図３４（ｂ）のプログラム５２４に示すように、キャッシュの領域に配列Ａが割当てられる場合に、アラインされない配列Ａの要素（Ａ［Ｘ］〜Ａ［Ｘ＋ＰＲＬＧ−１］）と、アラインされかつ１ラインの倍数のサイズとなる配列Ａの要素（Ａ［Ｘ＋ＰＲＬＧ］〜Ａ［Ｘ＋ＰＲＬＧ＋ＫＲＮＬ−１］）と、アラインされているが１ラインのサイズを満たさない配列Ａの要素（Ａ［Ｘ＋ＰＲＬＧ＋ＫＲＮＬ］〜Ａ［Ｘ＋ＰＲＬＧ＋ＫＲＮＬ＋ＥＲＬＧ−１］）とが区別されることになる。【０１４７】  したがって、図３４（ｂ）のプログラム５２４に示すように、式（４）に従ったアラインされていない配列Ａの要素数ＰＲＬＧを求める処理等が行なわれる。次に、要素数ＰＲＬＧに従って、アラインされていない配列Ａの要素（Ａ［Ｘ］〜Ａ［Ｘ＋ＰＲＬＧ−１］）についてのループ処理を行う。その後、アラインされている配列Ａの要素（Ａ［Ｘ＋ＰＲＬＧ］〜Ａ［Ｘ＋ＰＲＬＧ＋ＫＲＮＬ−１］の要素）については、図３２（ｂ）に示したシンプルループ分割の場合と同様に二重ループ化を行う。さらに、ＥＰＬＧ＞０であるならば、ピーリング処理が必要となる為、図３３（ｂ）に示したピーリング必要時の場合と同様にピーリング処理を行う。【０１４８】  その後、ピーリングされているループについて、畳み込み処理を行うと、図３４（ｃ）に示すようなプログラム５２６が生成される。また、図３４（ｄ）に示すように、キャッシュ領域確保命令（ＰｒｅＴｏｕｃｈ（＆Ａ［ｉ］））が挿入することにより、最適化されたプログラム５２８が得られる。【０１４９】  ただし、領域確保命令を挿入するのは、アラインされている領域でかつキャッシュの１ライン全てを使用する最内ループに対してのみである。
【産業上の利用可能性】
【０１５０】  本発明はインターロックを起こす可能性のある命令の発行を制御するコンパイラ、ＯＳ、プロセッサで実行されるプロセス等に適用できる。
【図１】
2005078579.tif 000008
【図２】
2005078579.tif 000009
【図３】
2005078579.tif 000010
【図４】
2005078579.tif 000011
【図５】
2005078579.tif 000012
【図６】
2005078579.tif 000013
【図７】
2005078579.tif 000014
【図８】
2005078579.tif 000015
【図９】
2005078579.tif 000016
【図１０】
2005078579.tif 000017
【図１１】
2005078579.tif 000018
【図１２】
2005078579.tif 000019
【図１３】
2005078579.tif 000020
【図１４】
2005078579.tif 000021
【図１５】
2005078579.tif 000022
【図１６】
2005078579.tif 000023
【図１７】
2005078579.tif 000024
【図１８】
2005078579.tif 000025
【図１９】
2005078579.tif 000026
【図２０】
2005078579.tif 000027
【図２１】
2005078579.tif 000028
【図２２】
2005078579.tif 000029
【図２３】
2005078579.tif 000030
【図２４】
2005078579.tif 000031
【図２５】
2005078579.tif 000032
【図２６】
2005078579.tif 000033
【図２７】
2005078579.tif 000034
【図２８】
2005078579.tif 000035
【図２９】
2005078579.tif 000036
【図３０】
2005078579.tif 000037
【図３１】
2005078579.tif 000038
【図３２】
2005078579.tif 000039
【図３３】
2005078579.tif 000040
【図３４】
2005078579.tif 000041
【手続補正書】
【提出日】平成17年6月20日(2005.6.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
実行時に外部からの所定の応答を待つ命令を含む命令セットを備えたプロセッサ向けのプログラム変換装置であって、
入力プログラムに含まれる繰返し回数がｘ回のループを、繰返し回数がｙ回のループを内側ループとし、繰返し回数がｘ／ｙ回のループを外側ループとするネスト構造への変換である二重ループ変換を行うループ構造変換手段と、
前記内側ループの外部の位置に、前記命令を配置することにより、当該命令を含む出力プログラムに変換する命令配置手段と
を備えることを特徴とするプログラム変換装置。
【請求項２】
前記ループ構造変換手段は、
前記入力プログラムに含まれるループを検出するループ検出部と、
前記ループの繰返し回数を検出する繰返し回数検出部と、
前記命令実行時の前記所定の応答を待つサイクル数である応答待ちサイクル数を検出する応答待ちサイクル数検出部と、
前記ループの１回の繰り返し処理に要する１シーケンスサイクル数を検出する１シーケンスサイクル数検出部と、
前記ループを、繰返し回数が（前記応答待ちサイクル数／前記1シーケンスサイクル数）回であるループに分割するループ分割部と、
繰返し回数が（前記応答待ちサイクル数／前記1シーケンスサイクル数）回のループを内側ループとし、繰返し回数が（前記ループの繰返し回数／前記内側ループの繰返し回数）回をループの外側ループとするネスト構造への変換である二重ループ変換を行う二重ループ変換部と
を有することを特徴とする請求項１に記載のプログラム変換装置。
【請求項３】
さらに、最適化に関する最適化指示情報を受け取る最適化指定情報受け取り手段を備える
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項４】
前記最適化指定情報受け取り手段は、前記入力プログラムに含まれるループの最低繰り返し回数を受け取り、
前記ループ構造変換手段は、ループの実行回数が不定な場合は、前記最低繰り返し回数に基づいて、前記最低繰り返し回数の繰り返し処理を前記ループより取り出し、取り出したループの繰り返し処理に対して二重ループ変換を行う
ことを特徴とする請求項３に記載のプログラム変換装置。
【請求項５】
前記命令は、インターロックを発生させる可能性のある命令である
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項６】
前記インターロックを発生させる可能性のある命令は、主記憶装置からキャッシュへのデータのプリフェッチ命令である
ことを特徴とする請求項５に記載のプログラム変換装置。
【請求項７】
さらに、命令のスケジューリングを行うスケジューリング手段を備え、
前記ループ構造変換手段は、
前記繰り返し回数がｘ回のループを、前記スケジューリング手段により得られた結果から、前記プリフェッチを実行するのに必要なサイクル数分だけ実行されるような繰り返し回数がｙ回のループに分割し、繰り返し回数がｙ回のループを内側ループ、繰り返し回数がｘ／ｙ回のループを外側ループとするネスト構造への変換である二重ループ変換を行う
ことを特徴とする請求項６に記載のプログラム変換装置。
【請求項８】
前記命令は、実行後に、所定の資源が参照可能状態になるまでに複数サイクルを要する命令である
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項９】
前記複数を要する命令は、主記憶装置またはキャッシュをアクセスする命令である
ことを特徴とする請求項８に記載のプログラム変換装置。
【請求項１０】
前記ループ構造変換手段は、
前記繰り返し回数がｘ回のループを、当該ループ内で参照される配列のアドレスがキャッシュのラインサイズ進む分だけ実行されるような繰り返し回数がｙ回のループに分割し、繰り返し回数がｙ回のループを内側ループ、繰り返し回数がｘ／ｙ回のループを外側ループとする二重ループ変換を行う
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項１１】
前記ループ構造変換手段は、前記配列が複数存在する場合に、二重ループ変換を行った前記繰り返し回数がｙ回のループを、さらに、前記配列の数に基づいて案分する案分変換を行う
ことを特徴とする請求項１０に記載のプログラム変換装置。
【請求項１２】
前記案分変換は、複数の前記配列について、その配列要素のサイズが異なるときには、前記サイズ比に応じて前記繰り返し回数がｙ回のループを案分する
ことを特徴とする請求項１１に記載のプログラム変換装置。
【請求項１３】
前記案分変換は、複数の前記配列について、ループの繰り返し処理を１回を行うのに進むアドレスであるストライドが異なるときに、前記ストライド比に応じて前記繰り返し回数がｙ回のループを案分する
ことを特徴とする請求項１１記載のプログラム変換装置。
【請求項１４】
前記案分変換は、内側ループを変換する際に、配分された各ループに対応する条件文を生成して、配分された各ループを同一の内側ループで実行されるように案分変換を行う
ことを特徴とする請求項１１に記載のプログラム変換装置。
【請求項１５】
前記ループ構造変換手段は、
前記繰り返し回数がｘ回のループを、前記繰り返し回数がｙ回のループに分割する際に、ｘ／ｙを演算した際の余りｚが０でなければ、ｚ回の繰り返し処理に対してピーリング処理を行ない、二重ループ変換を行う
ことを特徴とする請求項１０に記載のプログラム変換装置。
【請求項１６】
前記ループ構造変換手段は、
前記余りｚが０でなければ、内側ループのループ回数がｙ回であるかｚ回であるかを判定する判定する条件文を生成し、二重ループ変換を行う
ことを特徴とする請求項１５記載のプログラム変換装置。
【請求項１７】
前記ループ構造変換手段は、ループの実行回数が不定な場合は、前記ループの実行回数を実行時に判定し、判定結果に基づいて繰り返し回数を動的に変化させるような二重ループ変換を行う
ことを特徴とする請求項１０に記載のプログラム変換装置
【請求項１８】
さらに、配列がキャッシュのラインサイズにアラインされているという情報を受け取る受け取り手段を備え、
前記命令配置手段は、前記繰り返し回数がｘ回のループに対して、当該ループにおけるｘ回の繰り返し処理で参照されるデータよりも一つ先のキャッシュのラインに記憶されるデータをプリフェッチするプリフェッチ命令を配置する
ことを特徴とする請求項１０に記載のプログラム変換装置
【請求項１９】
前記最適化指定情報受け取り手段は、配列がキャッシュのラインのどの相対位置からアクセスを開始するかという情報を受け、
前記ループ構造変換手段は、当該情報に基づいて前記に二重ループ変換を行う
ことを特徴とする請求項１０に記載のプログラム変換装置。
【請求項２０】
前記命令配置手段は、前記配列がキャッシュのラインサイズにアラインされていない場合には、前記繰り返し回数がｘ回のループに対して、当該ループにおけるｘ回の繰り返し処理で参照されるデータよりも二つ先のキャッシュのラインに記憶されるデータをプリフェッチするプリフェッチ命令を配置する
ことを特徴とする請求項１０に記載のプログラム変換装置。
【請求項２１】
前記ループ構造変換手段は、前記配列がキャッシュのラインサイズにアラインされていない場合には、前記配列がキャッシュのラインのどの相対位置からアクセスを開始するかを判定し、判定結果に応じて二重ループ構造変換を行う
ことを特徴とする請求項１０に記載のプログラム変換装置。
【請求項２２】
さらに、着目する配列に関する情報を受け取る受け取り手段を備え、
前記ループ構造変換手段は、当該配列に対してのみ着目し、二重ループ変換を行う
ことを特徴とする請求項１０に記載のプログラム変換装置。
【請求項２３】
前記ループ構造変換手段は、最内ループを１つのかたまりとみなして、外側のループに対してさらに二重ループ変換を行う
ことを特徴とする請求項１に記載のプログラム変換装置。
【請求項２４】
実行時に外部からの所定の応答を待つ命令を含む命令セットを備えたプロセッサ向けのプログラム変換方法であって、
入力プログラムに含まれる繰返し回数がｘ回のループを、繰返し回数がｙ回であるループを内側ループとし、繰返し回数がｘ／ｙ回のループを外側ループとするネスト構造への変換である二重ループ変換を行うステップと、
前記内側ループの外部の位置に、前記命令を配置し、当該命令を含む出力プログラムに変換するステップと
を含むことを特徴とするプログラム変換方法。
【請求項２５】
実行時に外部からの所定の応答を待つ命令を含む命令セットを備えたプロセッサ向けのプログラム変換方法のプログラムであって、
入力プログラムに含まれる繰返し回数がｘ回のループを、繰返し回数がｙ回であるループを内側ループとし、繰返し回数がｘ／ｙ回のループを外側ループとするネスト構造への変換である二重ループ変換を行うステップと、
前記内側ループの外部の位置に、前記命令を配置し、当該命令を含む出力プログラムに変換するステップと
をコンピュータに実行させることを特徴とするプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はプログラム変換装置に関し、特に実行時に外部からの所定の応答を待つ命令を含む命令セットを備えたプロセッサ向けのプログラム変換装置に関する。
【背景技術】
【０００２】
近年、プロセッサの処理速度は急激に向上しているが、それに比べてメインメモリのアクセス速度向上は小さく、両者の速度差は年々大きくなっている。このため、情報処理装置の高速処理においてメモリアクセスがボトルネックとなることが従来指摘されている。
【０００３】
この問題を解消するために、記憶階層の考え方からキャッシュ機構が用いられている。キャッシュ機構では、プロセッサで必要とされるデータを主記憶から高速なキャッシュへ予め転送（プリフェッチ）しておく。これにより、プロセッサからのメモリアクセスに高速に対応することが可能である。
【０００４】
しかし、プロセッサがキャッシュ上に無いデータにアクセスした場合にはキャッシュミスが発生してしまう。このため、主記憶からキャッシュへのデータの転送時間がかかってしまうという問題がある。
【０００５】
ユーザがキャッシュを意識することなくプログラミングを行い、そのプログラムが実行されれば、このようなキャッシュミスが頻発することが想定される。その結果、キャッシュミスによるペナルティがプロセッサの性能を大きく劣化させることになる。そのため、コンパイラがキャッシュを考慮した最適化を行う必要がある。
【０００６】
キャッシュ最適化の技術の一つとしてプリフェッチ命令の挿入が挙げられる。プリフェッチ命令とは、あるメモリアドレスの参照が起こる前に、そのアドレスのデータを前もって主記憶からキャッシュへ転送しておくものである。プリフェッチ命令の挿入による最適化では、当該メモリアドレスの参照が起こる少し前のサイクルにプリフェッチ命令の挿入をおこなうものである。
【０００７】
例えば、図１（ａ）に示すようなループ処理に対しては、図１（ｂ）に示すようにデータが参照されるまでのレイテンシを考慮し、数イタレーション先で参照されるデータをプリフェッチするようにプリフェッチ命令（ｄｐｒｅｆ（））がループ内に挿入される。なお、ここでは、ｉｎｔ型の配列ａの要素は４バイト、キャッシュのラインサイズを１２８バイトとする。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかし、図１（ｂ）に示すコードでは、１イタレーションにつき配列ａの参照とプリフェッチとがそれぞれ行われているが、参照は４ｂｙｔｅずつしか行われないのに対して、プリフェッチは１ライン（１２８ｂｙｔｅ）単位で行われる。
【０００９】
よって、１回のプリフェッチで３２回分の参照に対応できるため、残り３１回は無駄にプリフェッチが行われていることになる。すなわち、同じラインのプリフェッチ命令を連続発行してしまっている。
【００１０】
また、プロセッサによっては、ｄｐｒｅｆ命令によるデータ転送中に、次のｄｐｒｅｆ命令を実行しようとすると、前のｄｐｒｅｆ命令による主記憶からキャッシュへのデータ転送が終了していないにもかかわらず、次のｄｐｒｅｆ命令が発行されてしまい、本来インターロックを解消するためにｄｐｒｅｆ命令を挿入したにも関わらず、インターロックが起こってしまう。
【００１１】
よって、上記のようにループの１イタレーションが短く、２つのｄｐｒｅｆ命令の間隔が短いと、ｄｐｒｅｆ命令による主記憶からキャッシュへのデータ転送にかかる時間（レイテンシ）が顕在化し、かえって性能を悪化させてしまう。
【００１２】
また、ｄｐｒｅｆ命令の実行時以外であっても、メモリアクセス命令などのように、命令発行後に何らかの応答待ちが発生するような命令の場合であっても、インターロックを起こす可能性がある。
【００１３】
本発明は、上述の課題を解決するためになされたもので、インターロックを引き起こす可能性のある命令を無駄に発行せずに、プログラム実行時の処理速度を向上させるプログラム変換装置およびプログラム変換方法を提供することを目的とする。
【００１４】
また、命令発行後に何らかの応答待ちが発生する命令を無駄に発行せずに、プログラム実行時の処理速度を向上させるプログラム変換装置およびプログラム変換方法を提供することを目的とする。
【００１５】
また、プログラム実行時にインターロックを引き起こさないプログラム変換装置およびプログラム変換方法を提供することを目的とする。
【課題を解決するための手段】
【００１６】
上記目的を達成するために、本発明に係るプログラム変換装置は、実行時に外部からの所定の応答を待つ命令を含む命令セットを備えたプロセッサ向けのプログラム変換装置であって、入力プログラムに含まれる繰返し回数がｘ回のループを、繰返し回数がｙ回のループを内側ループとし、繰返し回数がｘ／ｙ回のループを外側ループとするネスト構造への変換である二重ループ変換を行うループ構造変換手段と、前記内側ループの外部の位置に、前記命令を配置することにより、当該命令を含む出力プログラムに変換する命令配置手段とを備えることを特徴とする。
【００１７】
これにより、例えば図２に示すように、図１（ａ）に示すようなループ処理を二重ループ化し、最内ループの外側にプリフェッチ命令を挿入することができる。これにより、無駄なプリフェッチ実行がなくなる。よって、処理速度が向上する。また、あるｄｐｒｅｆ命令が実行されてから次のｄｐｒｅｆ命令が実行されるまでの間に、主記憶からキャッシュへのデータ転送にかかるレイテンシを隠蔽することが可能になり、インターロックが生じにくくなる。
【００１８】
すなわち、本発明によると、ループを二重化することにより、内側ループの外側でインターロックを起こす可能性のある命令を実行するようにすれば、当該命令を無駄に発行せずに、プログラム実行時の処理速度を向上させることができる。
【００１９】
また、ループを二重化することにより、インターロックを起こす可能性のある命令を発行してから次のインターロックを起こす可能性のある命令までの間のサイクル数を確保することができる。このため、プログラム実行時にインターロックを引き起こしにくくなる。
【００２０】
なお、プログラム変換装置は、コンパイラ、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）、またはＣＰＵ等の集積回路として実現可能である。
【００２１】
応答待ち命令には、上述したｄｐｒｅｆ命令のようにインターロックを起こす可能性のある命令や、命令実行時に外部からの所定の応答を待つ命令の他に、応答を待つ場合と待たない場合とがある命令も含む。
【００２２】
なお、本発明は、このような特徴的な手段を備えるプログラム変換装置として実現することができるだけでなく、プログラム変換装置が備える特徴的な手段をステップとするプログラム変換方法として実現したり、プログラム変換装置としてコンピュータを機能させるプログラムとして実現したりすることもできる。そして、このようなプログラムは、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）等の記録媒体やインターネット等の伝送媒体を介して流通させることができるのは言うまでもない。
【発明の効果】
【００２３】
本発明によると、プログラム実行時の処理速度を向上させることができる。
また、プログラム実行時にインターロックを引き起こしにくくなる。
【発明を実施するための最良の形態】
【００２４】
［システム構成］
図３は、本実施の形態に係るコンパイラシステムの構成を示す図である。コンパイラシステム１４８は、Ｃ言語等の高級言語で記述されたソースプログラム１４１を機械語の実行プログラム１４５に変換するソフトウェアシステムであり、コンパイラ１４９と、アセンブラ１５０と、リンカ１５１とを含む。
【００２５】
コンパイラ１４９は、キャッシュを備えるコンピュータのＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）をターゲットプロセッサとし、ソースプログラム１４１をアセンブラ言語で記述されたアセンブラファイル１４３に変換するプログラムである。コンパイラ１４９は、ソースプログラム１４１をアセンブラファイル１４３に変換する際に、キャッシュのラインサイズやレイテンシサイクル等に関する情報であるキャッシュパラメータ１４２や、後述するプロファイルデータ１４７に基づいて、最適化処理を行い、アセンブラファイル１４３を出力する。
【００２６】
アセンブラ１５０は、アセンブラ言語で記述されたアセンブラファイル１４３を機械語で記述されたオブジェクトファイル１４４に変換するプログラムである。リンカ１５１は、複数のオブジェクトファイル１４４を結合し、実行プログラム１４５を生成するプログラムである。
【００２７】
実行プログラム１４５の開発ツールとして、シミュレータ１５２およびプロファイラ１５３が用意されている。シミュレータ１５２は、実行プログラム１４５をシミュレートし、実行時の各種実行ログデータ１４６を出力するプログラムである。プロファイラ１５３は実行ログデータ１４６を解析し、プログラムの実行順序等を解析したプロファイルデータ１４７を出力するプログラムである。
【００２８】
［コンパイラの構成］
図４は、コンパイラの構成を示す図である。コンパイラ１４９は、構文解析部１８２と、最適化情報解析部１８３と、一般最適化部１８４と、命令スケジューリング部１８５と、ループ構造変換部１８６と、命令最適配置部１８７と、コード出力部１８８とを含む。各構成処理部は、プログラムとして実現される。
【００２９】
構文解析部１８２は、ソースプログラム１４１を入力として受け、構文解析処理を行った後、中間言語のプログラムを出力する処理部である。
【００３０】
最適化情報解析部１８３は、キャッシュパラメータ１４２、プロファイルデータ１４７、コンパイルオプションおよびプラグマなどの中間言語の最適化処理に必要な情報を読み込み、解析する処理部である。一般最適化部１８４は、中間コードに一般的な最適化処理を施す処理部である。命令スケジューリング部１８５は、命令の並びを最適化し、命令スケジューリングを行う処理部である。コンパイルオプションおよびプラグマはいずれもコンパイラに対する指示である。
【００３１】
ループ構造変換部１８６は、一重ループを二重ループに変換する処理部である。命令最適配置部１８７は、変換された二重ループ内にプリフェッチ命令を配置する処理部である。コード出力部１８８は、最適化された中間言語仕様のプログラムをアセンブラ言語で記述されたプログラムに変換してアセンブラファイル１４３を出力する処理部である。
【００３２】
［処理の流れ］
次に、コンパイラ１４９の実行する処理の流れについて説明する。図５は、コンパイラ１４９が実行する処理のフローチャートである。
【００３３】
構文解析部１８２は、ソースプログラム１４１の構文解析を行い、中間コードを生成する（Ｓ１）。最適化情報解析部１８３は、キャッシュパラメータ１４２、プロファイルデータ１４７、コンパイルオプションおよびプラグマなどを解析する（Ｓ２）。一般最適化部１８４は、最適化情報解析部１８３における解析結果に従い、一般的な中間コードの最適化を行う（Ｓ３）。命令スケジューリング部１８５は、命令のスケジューリングを行う（Ｓ４）。ループ構造変換部１８６は、中間コードに含まれるループ構造に着目し、必要であれば一重ループ構造を二重ループ構造に変換する（Ｓ５）。命令最適配置部１８７は、ループ構造内で参照されるデータをプリフェッチする命令を中間コードに挿入する（Ｓ６）。コード出力部１８８は、中間コードをアセンブラコードに変換し、アセンブラファイル１４３として出力する（Ｓ７）。
【００３４】
構文解析処理（Ｓ１）、最適化情報解析処理（Ｓ２）、一般的な最適化処理（Ｓ３）、命令スケジューリング処理（Ｓ４）およびアセンブラコード出力処理（Ｓ７）は、一般的な処理と同様であるため、その詳細な説明はここでは繰返さない。
【００３５】
以下、ループ構造変換処理（Ｓ５）およびプリフェッチ命令配置処理（Ｓ６）について詳細に説明する。
【００３６】
図６は、ループ構造変換処理（図５のＳ６）の詳細を説明するための図である。ループ構造変換部１８６は、ループ回数が即値で与えられており算出可能であるか、それ以外の変数等で与えられており算出不可能であるかを判断する（Ｓ１１）。すなわち、ループ回数が固定であるか不定であるかを判断する。
【００３７】
ループ回数が不定の場合には（Ｓ１１でＮＯ）、プラグマまたはコンパイルオプションにより最低のループ回数の指定があるかまたはプログラム実行時に動的にループ回数を判定し、ループ分割をする旨の指定があるかについて判断する（Ｓ１２）。
【００３８】
いずれかの指定がある場合（Ｓ１２でＹＥＳ）またはループ回数が固定値の場合には（Ｓ１１でＹＥＳ）、ループ内で参照されている配列の添え字が解析可能か否かについて調べる（Ｓ１３）。すなわち、ループカウンタがある規則性を持って変化している場合には解析可能であると判断される。例えば、ループカウンタの値がイタレーション内で書換えられるような場合には、解析不可能であると判断される。
【００３９】
添え字が解析可能である場合には（Ｓ１３でＹＥＳ）、ループ処理内で参照される各配列について１イタレーションで参照される要素のバイト数を求め、そのうち最小の値ＬＢを導出する（Ｓ１４）。
【００４０】
次に、キャッシュのラインサイズＣＳを値ＬＢで割った値が１よりも大きいか否か判断する（Ｓ１５）。ＣＳ／ＬＢの値が１よりも大きい場合には（Ｓ１５でＹＥＳ）、ループ処理の配列がアラインされているか否かを調べる（Ｓ１６）。配列がアラインされているか否かの判断は、プラグマやコンパイルオプション等によりアラインされているとの指示があるか否かにより判断される。
【００４１】
配列がアラインされていない場合には（Ｓ１７でＮＯ）、「ＬＢ＊ＬＣ／ＩＣ」がＣＳよりも大きいか否かについて判断する（Ｓ１６）。ここで、ＬＣは、レイテンシのサイクル数を示し、ＩＣは１イタレーションあたりのサイクル数を示す。「ＬＣ／ＩＣ」は、ループを複数の最内ループに分割した場合の各ループのループ回数を示しており、「ＬＢ＊ＬＣ／ＩＣ」は、各ループでのアクセス容量を示している。
【００４２】
「ＬＢ＊ＬＣ／ＩＣ」がラインサイズＣＳよりも大きい場合には、（Ｓ１６でＹＥＳ）、分割後の各ループ処理では１ラインサイズ以上の要素の参照が行われる。このため、分割要因をサイクルとし、各ループ処理を二重ループ化した際の最内ループのループ回数ＤＴを次式（１）に従い導出する（Ｓ１８）。
【００４３】
ＤＴ＝（ＬＣ−１）／ＩＣ＋１                              …（１）
「ＬＢ＊ＬＣ／ＩＣ」がラインサイズＣＳ以下の場合（Ｓ１６でＮＯ）または配列がアラインされている場合には（Ｓ１７でＹＥＳ）、分割要因をサイズとし、各ループ処理を二重ループ化した際の最内ループのループ回数ＤＴを次式（２）に従い導出する（Ｓ１９）。
【００４４】
ＤＴ＝（ＣＳ−１）／ＬＢ＋１                              …（２）
最内ループのループ回数ＤＴが導出処理（Ｓ１８またはＳ１９）後、最内ループのループ回数ＤＴが１よりも大きいか否か判断される（Ｓ２０）。ＤＴが１の場合には（Ｓ２０でＮＯ）、最内ループのループ回数ＤＴが１回であるため、ループを二重ループに構造変換する必要がない。このため、ループ構造変換処理（Ｓ５）を終了させる。
【００４５】
最内ループのループ回数ＤＴが２以上の場合には（Ｓ２０でＹＥＳ）、ループを二重ループに構造変換した場合の外側のループ構造が作成される（Ｓ２１）。外側ループ構造を生成する際に、ピーリング処理が必要か否かを判断する（Ｓ２２）。ピーリング処理およびピーリング処理が必要か否かの判断方法については後述する。
【００４６】
ピーリング処理が必要な場合には（Ｓ２２でＮＯ）、ピーリング処理を行い、ピーリングコードを生成する（Ｓ２４）。その後、コンパイルオプション「−Ｏ」または「−Ｏｓ」による指定があるか否かを調べる（Ｓ２５）。ここで、コンパイルオプション「−Ｏ」は、プログラムサイズおよび実行処理速度ともに平均的なアセンブラコードをコンパイラに出力させるための指示である。コンパイルオプション「−Ｏｓ」は、プログラムサイズ抑制を重視したアセンブラコードをコンパイラに出力させるための指示である。
【００４７】
ピーリング処理する必要がないか（Ｓ２２でＹＥＳ）またはコンパイルオプション「−Ｏ」または「−Ｏｓ」の指定がない場合には（Ｓ２５でＮＯ）、内側ループ（最内ループ）のループ回数の条件式を生成する（Ｓ２３）。
【００４８】
コンパイルオプション「−Ｏ」または「−Ｏｓ」の指定がある場合には（Ｓ２５でＹＥＳ）、ピーリングされたループ処理を二重ループに畳み込み、最内ループのループ回数の条件式を生成する（Ｓ２６）。
【００４９】
最内ループのループ回数条件生成処理（Ｓ２３、Ｓ２６）の後、最内ループにおける参照の対象配列は１つであるか否か調べられる（Ｓ２７）。最内ループにおける参照の対象配列が１つの場合には、（Ｓ２７でＹＥＳ）、ループ構造変換処理（Ｓ５）を終了する。
【００５０】
最内ループにおける参照の対象配列が２つ以上ある場合には（Ｓ２７でＮＯ）、最内ループの分割個数を導出し、分割後の各最内ループのループ回数の比率を決定する（Ｓ２８）。その後、分割後の最内ループ回数ＤＴを分割個数で割った値が１よりも大きいか否か判断する（Ｓ２９）。すなわち、当該値が１以下の場合には（Ｓ２９でＮＯ）、分割後の各ループ回数が１回以下であるため、分割する意味がない。このため、ループ構造変換処理（Ｓ５）を終了させる。
【００５１】
当該値が１よりも大きい場合には（Ｓ２９でＹＥＳ）、分割後の各ループ回数が２回以上である。この場合には、コンパイルオプション「−Ｏ」または「−Ｏｔ」による指定があるか否かを調べる（Ｓ３０）。コンパイルオプション「−Ｏｔ」は、実行処理速度向上を重視したアセンブラコードをコンパイラに出力させるための指示である。
【００５２】
コンパイルオプション「−Ｏ」または「−Ｏｓ」による指定がある場合には（Ｓ３０でＹＥＳ）、後述する実行処理速度向上を重視したコピー型内側ループ分割処理（Ｓ３１）を実行し、ループ構造変換処理（Ｓ５）を終了する。
【００５３】
コンパイルオプション「−Ｏ」または「−Ｏｓ」による指定がない場合には（Ｓ３０でＮＯ）、後述するプログラムサイズ抑制を重視した条件型内側ループ分割処理（Ｓ３２）を実行し、ループ構造変換処理（Ｓ５）を終了する。
【００５４】
図７は、コピー型内側ループ分割処理（図６のＳ３１）の詳細を示すフローチャートである。
【００５５】
最内ループのループ回数ＤＴを分割個数で割った値を細分割後内側ループ回数とする（Ｓ４１）。次に、内側ループを分割個数分だけ複製し、生成する（Ｓ４２）。その後、細分割後の各内側ループ回数を細分割後内側ループ回数に修正する（Ｓ４３）。さらに、ＤＴを分割個数で割った剰余を細分割後の先頭ループのループ回数に加算し（Ｓ４４）、コピー型内側ループ分割処理を終了する。
【００５６】
図８は、条件型内側ループ分割処理（図６のＳ３２）の詳細を示すフローチャートである。
【００５７】
最内ループのループ回数ＤＴを分割個数で割った値を細分割後内側ループ回数とする（Ｓ５１）。次に、内側ループ回数条件の切換えｓｗｉｔｃｈテーブルを生成する（Ｓ５２）。すなわち、内側ループ回数を順次切り替えるように、Ｃ言語で言うところのｓｗｉｔｃｈ文を生成する。なお、ｉｆ文であってもよい。
【００５８】
テーブル生成後、細分割後の各内側ループ回数条件を細分割後の内側ループ回数に修正する（Ｓ５３）。その後、ＤＴを分割個数で割った剰余を細分割後の先頭ループの回数条件に加算し（Ｓ５４）、条件型内側ループ分割処理を終了する。
【００５９】
図９は、プリフェッチ命令配置処理（図５のＳ６）の詳細を示すフローチャートである。
【００６０】
プリフェッチ命令配置処理では、すべてのループについて以下の処理を繰返す（ループＡ）。まず、着目しているループが命令挿入対象のループであるか否かを調べる（Ｓ６１）。命令挿入対象のループであるか否かの情報は、ループ構造変換部１８６の解析結果より取得される。
【００６１】
命令挿入対象のループの場合には（Ｓ６１でＹＥＳ）、そのループに対して条件型ループ分割が行われているか否かを調べる（Ｓ６２）。条件型ループ分割が行われていれば、各条件文における命令挿入位置を解析し（Ｓ６３）、プリフェッチ命令を挿入する（Ｓ６４）。命令挿入対象のループに対して条件型ループ分割が行われていなければ（Ｓ６２でＮＯ）、そのループに対してコピー型ループ分割が行われているか否かを調べる（Ｓ６５）。コピー型ループ分割が行われていれば（Ｓ６５でＹＥＳ）、そのループの手前の命令挿入位置を解析する（Ｓ６６）。その後、プリフェッチ命令が挿入される（Ｓ６７）。ピーリングされたループの場合には（Ｓ６８でＹＥＳ）、当該ループの手前に命令挿入するように命令挿入位置が解析され（Ｓ６９）、その位置にプリフェッチ命令が挿入される（Ｓ７０）。
【００６２】
図１０は、プリフェッチ命令挿入処理（図９のＳ６４、Ｓ６７およびＳ７０）の詳細を示すフローチャートである。
【００６３】
命令挿入処理では、挿入命令、挿入位置、挿入アドレス等からなる情報リストがすべて空になるまで以下を繰返す（ループＢ）。
【００６４】
プリフェッチ命令を挿入しようとしている配列要素がアライン済みであるか否かを判断する（Ｓ７２）。アラインされていなければ（Ｓ７２でＮＯ）、サイクル要因に従ってループ分割されたものであるのか、サイズ要因に従ってループ分割されたものであるのかを調べる（Ｓ７３）。
【００６５】
アライン済みであるか（Ｓ７２でＹＥＳ）またはサイクル要因でループ分割されたものであれば（Ｓ７３でＹＥＳ）、１ライン先のデータをプリフェッチする命令を挿入する（Ｓ７４）。アラインされておらず、かつサイズ要因でループ分割されたものであれば（Ｓ７３でＮＯ）、２ライン先のデータをプリフェッチする命令を挿入する（Ｓ７５）。最後に、解析済みの情報を情報リストから削除する（Ｓ７６）。
【００６６】
［コンパイルオプション］
コンパイラシステム１４８では、コンパイラに対するコンパイルオプションとして、オプション「−ｆｎｏ−ｌｏｏｐ−ｔｉｌｉｎｇ−ｄｐｒｅｆ」が用意される。このオプションが指定されれば、プラグマの指定に関わらず、ループに対する構造変換は行わない。本オプションの指定がなければ、構造変換の実施はプラグマ指定の有無に従う。
【００６７】
［プラグマ指定］
本指定は、直後のループに対するものである。
【００６８】
プラグマ「＃ｐｒａｇｍａ  ＿ｌｏｏｐ＿ｔｉｌｉｎｇ＿ｄｐｒｅｆ  変数名［，変数名］」により変数が指定された場合には、プラグマ指定された変数のみに着目してループ分割を行う。指定する変数は、配列でも、ポインタでもよい。
【００６９】
プラグマ「＃ｐｒａｇｍａ  ＿ｌｏｏｐ＿ｔｉｌｉｎｇ＿ｄｐｒｅｆ＿ａｌｌ」によりループが指定された場合には、ループ内で参照される配列の全てに着目して構造変換が行われる。
【００７０】
以下、いくつかの具体的曲面におけるループ分割処理について説明する。なお、以降の処理では、説明の簡単化のためＣ言語によるプログラム記述を行っているが、実際には中間言語による最適化処理が行われる。
【００７１】
［シンプルループ分割］
図１１は、ピーリングが必要ない場合のシンプルループ分割処理について説明するための図である。
【００７２】
図１１（ａ）に示すようなソースプログラム２８２が入力された場合について考える。このソースプログラム２８２では、配列Ａの要素が順次参照され、変数ｓｕｍに加算される。ここで、配列Ａの各要素のサイズは４バイトであるものとし、キャッシュの１ラインサイズは１２８バイト（以降の説明でも、キャッシュのラインサイズは１２８バイトであるものとする。）であるものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。また、ソースプログラム２８２に含まれるループのイテレーションの回数１２８回は、３２の整数倍である。このため、ソースプログラム２８２は、図１１（ｂ）のプログラム２８４に示すように、二重ループに構造変換することができる。すなわち、最内ループでは３２回の繰り返し処理を行い、その外のループでは、最内ループを４回繰返すループ処理を行う。最内ループ処理ではキャッシュの１ライン分のデータが参照される。その後、図１１（ｃ）のプログラム２８６に示されるように、最内ループの実行前に、プリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））が挿入される。プリフェッチ命令を挿入することにより、最内ループ実行時には、当該ループで参照される配列Ａの要素がキャッシュに乗っていることになる。
【００７３】
図１２〜図１５は、ピーリングが不要なシンプルループ分割処理における中間言語の推移を説明するための図である。
【００７４】
図１２は、図１１（ａ）と同様に、ピーリングが必要のない場合のソースプログラムの一例を示す図である。図１３は、図１２に示したソースプログラム２４０に対応する中間言語のプログラムである。［ＢＧＮＢＢＬＫ］と［ＥＮＤＢＢＬＫ］とで挟まれた内部の命令列が１つの基本ブロックに対応しており、［ＢＧＮＢＢＬＫ］Ｂ１で始まる基本ブロックがｆｏｒループの直前までの処理を示しており、［ＢＧＮＢＢＬＫ］Ｂ２で始まる基本ブロックがｆｏｒループを示しており、［ＢＧＮＢＢＬＫ］Ｂ３で始まる基本ブロックがｆｏｒループの後の処理を示している。
【００７５】
図１４は、図１３に示された中間言語のプログラムを二重ループに構造変換した後の中間言語のプログラムを示している。［ＢＧＮＢＢＬＫ］Ｂ２で始まる基本ブロックが最内ループに対応しており、［ＢＧＮＢＢＬＫ］Ｂ４および［ＢＧＮＢＢＬＫ］Ｂ５で始まるループがその外側のループに対応している。
【００７６】
図１５は、図１４に示された中間言語のプログラムにプリフェッチ命令を挿入した後の中間言語のプログラムを示している。プログラム２７０では、［ＢＧＮＢＢＬＫ］Ｂ４で始まる基本ブロックの内部にプリフェッチ命令（ｄｐｒｅｆ）が新たに挿入されている。
【００７７】
図１６は、ピーリングが必要な場合のシンプルループ分割処理について説明するための図である。
【００７８】
図１６（ａ）に示すようなソースプログラム２９２が入力された場合について考える。このソースプログラム２９２では、配列Ａの要素が順次参照され、変数ｓｕｍに加算される。ここで、配列Ａの各要素のサイズは４バイトであるものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。また、ソースプログラム２９２に含まれるループのイテレーションの回数は１４０回であるものとする。すなわち、１ラインに記憶される配列Ａの要素数３２で割った場合に余りが出る数である。
【００７９】
このような場合には、図１６（ｂ）に示すプログラム２９４のように、１４０を３２で割った余りのループ回数をピーリングし、それ以外の部分を図１１（ｂ）と同様に二重ループ構造に構造変換する。その後、ピーリングされた部分を二重ループ構造に含ませるためのピーリング畳み込み処理を行い、図１６（ｃ）に示すようなプログラム２９６が得られる。すなわち、通常状態では最内ループで３２回の繰り返し処理が行われ、最後に最内ループが実行される場合には、残りの１２（＝１４０−１２８）回の繰り返し処理が行われる。その後、図１６（ｄ）のプログラム２９８に示されるように、最内ループの実行前に、プリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））が挿入される。
【００８０】
［複数配列アクセスが存在する場合（ピーリング必要なし）］
図１７は、ループ内に複数の配列アクセスが存在する場合のループ分割処理について説明するための図である。
【００８１】
図１７（ａ）に示すようなソースプログラム３０１が入力された場合について考える。このソースプログラム３０１では、配列Ａおよび配列Ｂの要素が順次参照され、当該要素同士の積が変数ｓｕｍに加算される。ここで、配列Ａおよび配列Ｂの各要素はそれぞれ４バイトであるものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。または、配列Ｂの要素が３２個記憶される。すなわち、１ラインに格納される要素数は配列Ａと配列Ｂとで同じである。また、ソースプログラム３０１に含まれるループのイテレーションの回数１２８回は、３２の整数倍である。このため、ソースプログラム３０１は、図１７（ｂ）のプログラム３０２に示すように、ピーリングをすることなく二重ループに構造変換することができる。
【００８２】
複数配列アクセスが存在する場合の二重ループ構造は、コピー型と呼ばれる実行処理速度を向上させるための最適化と、条件型と呼ばれるプログラムサイズを小さくするための最適化との二種類がある。
【００８３】
まず、コピー型の最適化について説明する。プログラム３０２に含まれる最内ループのループ回数を配列Ａと配列Ｂとの要素の大きさの比で分割する。ここでは、配列Ａと配列Ｂとはともに同じ要素の大きさである。したがって、図１７（ｃ）に示すプログラム３０３のように最内ループを二等分し、ループ回数が１６回の最内ループ２つに分割する。次に、図１７（ｄ）のプログラム３０４に示すように、各最内ループの直前にプリフェッチ命令を挿入する。最初の最内ループの直前には、１ライン分の配列Ａの要素をプリフェッチするためのプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））が挿入され、２番目の最内ループの直前には、１ライン分の配列Ｂの要素をプリフェッチするためのプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＋３２］））が挿入される。
【００８４】
このようにプリフェッチ命令間にループ処理を挿入させることにより、異なる配列に対するプリフェッチ命令が連続することが無くなり、プリフェッチ命令実行によるレイテンシを隠蔽することができる。このため、実行処理速度を向上させることができる。
【００８５】
次に、条件型の最適化について説明する。条件型の場合も、コピー型の場合と同様にして最内ループのループ回数を配列Ａと配列Ｂとの要素の大きさの比で分割する。ただし、プログラム３０３のように最内ループを２つ並べるのではなく、図１７（ｅ）に示すプログラム３０５のように最内ループの個数は１つであり、そのループ回数を条件分岐させるようにしている。すなわち、変数Ｋ＝１の場合と、Ｋ＝０の場合とで最内ループのループ回数Ｎを変えるようにしている。ただし、この例では変数Ｋの値に関係なく最内ループの回数Ｎは１６回となっている。次に、図１７（ｆ）に示すプログラム３０６のように、Ｋ＝１の場合には配列Ａの要素を１ライン分プリフェッチし、Ｋ＝０の場合には配列Ｂの要素を１ライン分プリフェッチするように条件分岐式およびプリフェッチ命令の挿入が行われる。なお、ここでは、最適化によりループ回数Ｎは即値１６に置き換えられている。
【００８６】
このように、最内ループの個数を１つにし、条件分岐式で最内ループのループ回数およびプリフェッチ命令を変えるようにすることにより、最終的に生成される機械語命令のプログラムサイズを小さくすることができる。ただし、条件分岐処理があるため、コピー型に比べて処理速度が多少遅くなる可能性がある。
【００８７】
［複数配列アクセスが存在する場合（ピーリング必要）］
図１８は、ループ内に複数の配列アクセスが存在する場合のループ分割処理について説明するための図である。
【００８８】
図１８（ａ）に示すようなソースプログラム３１１が入力された場合について考える。このソースプログラム３１１では、配列Ａおよび配列Ｂの要素が順次参照され、当該要素同士の積が変数ｓｕｍに加算される。ここで、配列Ａおよび配列Ｂの各要素はそれぞれ４バイトであるものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。または、配列Ｂの要素が３２個記憶される。すなわち、１ラインに格納される要素数は配列Ａと配列Ｂとで同じである。また、ソースプログラム３１１に含まれるループのイタレーションの回数は１４０回であるものとする。
【００８９】
したがって、ソースプログラム３１１を二重ループに構造変換する場合には、図１６（ｂ）に示したプログラム２９４と同様、図１８（ｂ）に示すようにピーリング処理されたプログラム３１２が生成される。
【００９０】
コピー型の最適化を行う際には、配列Ａと配列Ｂとの要素の大きさの比で最内ループを分割する。すると、図１８（ｃ）に示すプログラム３１３が生成される。次に、図１８（ｄ）のプログラム３１４に示すように、最初の最内ループの直前には、１ライン分の配列Ａの要素をプリフェッチするためのプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））が挿入され、２番目の最内ループの直前には、１ライン分の配列Ｂの要素をプリフェッチするためのプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＋３２］））が挿入される。なお、ピーリング処理された最終ループの直前にはプリフェッチ命令は挿入されない。これは、その前の二重ループ処理におけるプリフェッチ命令実行により所望のデータがキャッシュにプリフェッチされているからである。
【００９１】
条件型の最適化を行う際には、プログラム３１２に対してピーリング畳み込み処理を行い、図１８（ｅ）に示されるようなプログラム３１５を得る。ピーリング畳み込み処理は、図１６を参照して説明したものと同様である。次に、最内ループのループ回数を配列Ａと配列Ｂとの要素の大きさの比で分割し、当該ループ回数を条件分岐させるように図１８（ｆ）に示すプログラム３１６を作成する。プログラム３１６においては、変数Ｋの値を交互に変更させ、変数Ｋの値に対応するようにループカウンタＮの値を変化させる。次に、図１８（ｇ）のプログラム３１７に示すように、Ｋの値の変化に伴い、配列Ａおよび配列Ｂの要素を１ライン分ずつ交互にプリフェッチするように、条件分岐式中にプリフェッチ命令を挿入する。
【００９２】
このように、ピーリングが必要な場合であっても、コピー型の場合にはピーリングの部分を二重ループとは別のループにし、条件型の場合には、条件分岐式によりピーリングの場合のループカウンタの回数を変えるようにすることにより、ループ内に複数の配列アクセスがあり、かつピーリングが必要な場合であっても、プリフェッチによるレイテンシを考慮した最適化を行うことができる。
【００９３】
［サイズが異なる複数配列アクセスが存在する場合（ピーリング必要なし）］
図１９は、ループ内に複数の配列アクセスが存在し、かつ配列の要素のサイズがすべて同じではない場合のループ分割処理について説明するための図である。
【００９４】
図１９（ａ）に示すようなソースプログラム３２１が入力された場合を考える。ここで、配列Ａの要素は４バイト、配列Ｂの要素は２バイトとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個、配列Ｂの要素が６４個記憶される。
【００９５】
この場合、要素サイズの小さい配列Ｂに着目し、配列Ｂの要素に応じたループの構造変換を行う。すなわち、図１９（ｂ）のプログラム３２２のように、最内ループのループ回数を１ラインに収まるキャッシュＢの要素数６４にし、二重ループに構造変換する。最内ループでは、配列Ｂに関しては１ライン分の要素が消費されるが、配列Ａに関しては２ライン分の要素が消費されることになる。このため、最内ループ処理を実行するためには合計３ライン分のデータが必要になる。
【００９６】
このため、コピー型の最適化を行う際には、図１９（ｃ）のプログラム３２３に示すように、最内ループを３つに分割し、図１９（ｄ）のプログラム３２４に示すように、各最内ループの直前にプリフェッチ命令を挿入する。ここでは、１番目の最内ループの直前には、２ライン先の配列Ａの要素をプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋６４］））を挿入し、２番目の最内ループの直前には３ライン先の配列Ａの要素をプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋９６］））を挿入し、３番目の最内ループの直前には１ライン先の配列Ｂの要素をプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＋６４］））を挿入している。また、３つの最内ループのループ回数を処理順に２２、２１および２１としている。これは、最外ループの条件分岐判断が３番目の最内ループ実行後に行われるため、３番目の最内ループのループ回数を少なくすることにより、全体としての処理速度を向上させるためである。
【００９７】
また、条件型の最適化を行う際には、図１９（ｅ）のプログラム３２５に示すように、１回の最内ループ処理につき、変数Ｋの値を０から２までの範囲内で更新させ、変数Ｋの値による条件分岐処理により最内ループのループ回数Ｎを２２、２１および２１のうちのいずれかに設定する。その後、ループ回数Ｎの最内ループを実行させる。次に、図１９（ｆ）のプログラム３２６に示すように、変数Ｋの値が０の場合にはプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋６４］））を実行させ、変数Ｋの値が１の場合にはプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋９６］））を実行させ、変数Ｋの値が２の場合にはプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＋６４］））を実行させるように最適化を行う。
【００９８】
［サイズが異なる複数配列アクセスが存在する場合（ピーリング必要）］
図２０は、ループ内に複数の配列アクセスが存在し、かつ配列の要素のサイズがすべて同じではない場合のループ分割処理について説明するための図である。
【００９９】
図２０（ａ）に示すソースプログラム３３１は、図１９（ａ）に示したソースプログラム３２１とループ回数が異なるのみである。したがって、ソースプログラム３２１と同様、配列Ａの要素は４バイト、配列Ｂの要素は２バイトである。図２０（ｂ）に示すように、ソースプログラム３２１のループを二重ループに構造変換し、ループ回数１４０を配列Ｂの１ライン分の要素数６４で割った余りをピーリング処理すると、プログラム３２２が得られる。コピー型の最適化処理を行う場合には、図１９（ｃ）および図１９（ｄ）を参照して説明したように、二重ループの最内ループを３分割し、プリフェッチ命令を挿入することにより、図２０（ｃ）に示すプログラム３３３が得られる。条件型の最適化処理を行う場合には、図１９（ｅ）および図１９（ｆ）を参照して説明したように、条件分岐式によりループ回数およびプリフェッチ命令を制御し、最終的に図２０（ｅ）に示すプログラム３３５が得られる。
【０１００】
［ストライドが異なる複数配列アクセスが存在する場合］
図２１は、ループ内にストライドが異なる複数の配列アクセスが存在する場合のループ分割処理について説明するための図である。
【０１０１】
ストライドとは、ループ処理における配列要素の増分値（アクセス幅）のことを示す。図２１（ａ）に示すようなソースプログラム３４１が入力された場合を考える。ここで、配列Ａの要素および配列Ｂの要素はともに４バイトであるものとする。ソースプログラム３４１では、ループのイタレーションごとに、配列Ａの要素は１ずつ増加するのに対し、配列Ｂの要素は２ずつ増加する。すなわち、配列Ｂのアクセス幅は配列Ａのアクセス幅の２倍である。最小アクセス幅の配列Ａに着目すると、１ラインには配列Ａの要素が３２個収まる。このため、最内ループのループ回数を３２回とした二重ループへの構造変換を行うと、図２１（ｂ）に示すプログラム３４２が得られる。最内ループでは、配列Ａに関しては１ライン分の要素が消費されるが、配列Ｂに関しては２ライン分の要素が消費されることになる。このため、最内ループ処理を実行するためには合計３ライン分のデータが必要になる。
【０１０２】
よって、コピー型の最適化を行う際には、図２１（ｃ）のプログラム３４３に示すように、最内ループを３つに分割し、図２１（ｄ）のプログラム３４４に示すように、各最内ループの直前にプリフェッチ命令を挿入する。ここでは、１番目の最内ループの直前には、１ライン先の配列Ａの要素をプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を挿入し、２番目の最内ループの直前には２ライン先の配列Ｂの要素をプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＊２＋６４］））を挿入し、３番目の最内ループの直前には３ライン先の配列Ｂの要素をプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＊２＋９６］））を挿入している。
【０１０３】
また、条件型の最適化を行う際には、図２１（ｅ）のプログラム３４５に示すように、１回の最内ループ処理につき、変数Ｋの値を０から２までの範囲内で更新させ、変数Ｋの値による条件分岐処理により最内ループのループ回数Ｎを１１、１１および１０のうちのいずれかに設定する。その後、ループ回数Ｎの最内ループを実行させる。次に、図２１（ｆ）のプログラム３４６に示すように、変数Ｋの値が０の場合にはプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を実行させ、変数Ｋの値が１の場合にはプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＊２＋６４］））を実行させ、変数Ｋの値が２の場合にはプリフェッチ命令（ｄｐｒｅｆ（＆Ｂ［ｉ＊２＋９６］））を実行させるように最適化を行う。
【０１０４】
［ループ回数が不定な場合］
図２２は、ループ回数が不定なループ処理のループ分割処理を説明するための図である。
【０１０５】
図２２（ａ）に示すソースプログラム３５１が入力された場合を考える。ソースプログラム３５１に含まれるループ回数は変数Ｖａｌにより特定され、コンパイル時には不定である。しかし、最低１２８回は繰り返し処理が行われることがプラグマ指定「＃ｐｒａｇｍａ  ＿ｍｉｎ＿ｉｔｅｒａｔｉｏｎ＝１２８」により、保証されている。ここで、配列Ａは４バイトであるものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。
【０１０６】
プラグマ指定に従い、ループ処理を最初の１２８回のループ処理と、それ以降の変数Ｖａｌで特定されるループ回数のループ処理とに分割し、それぞれをシンプルループの場合と同様に二重ループ化すると図２２（ｂ）に示すプログラム３５２が得られる。
【０１０７】
コピー型の最適化処理を行う場合には、プログラム３５２の最内ループの直前に１ライン先の配列Ａの要素をプリフェッチするためのプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を挿入することにより、図２２（ｃ）に示すプログラム３５３が得られる。
【０１０８】
条件型の最適化処理を行う場合には、後半のループ処理をピーリング畳み込みし、最外ループ回数が１２８回になるまでは、最内ループの回数を３２回にし、それ以降は最内ループの回数を（Ｖａｌ−１２８）回に設定する分岐命令を挿入する。すると、図２２（ｄ）に示すようなプログラム３５４が得られる。
【０１０９】
最後に、最内ループの実行前にプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を挿入することにより図２２（ｅ）に示すようなプログラム３５５が得られる。
【０１１０】
図２３は、ループ回数が不定なループ処理のループ分割処理を説明するための他の図である。
【０１１１】
図２３（ａ）に示すソースプログラム３６１が入力された場合を考える。ソースプログラム３６１に含まれるループ回数は変数Ｎにより特定され、コンパイル時には不定である。また、ソースプログラム３６１は、ソースプログラム３５１と異なり、最低のループ回数を示すプラグマ指定がない。
【０１１２】
ループ回数が小さなループ処理に対してループの構造変換を行い、最適化を行ったとしても、最適化の効果が表れにくい。このため、このような場合には、最適化の効果を高めるために、ループ回数があるしきい値よりも大きければ最適化されたループ処理を実行し、それ以外の場合には通常のループ処理を実行するようにする。例えば、あるしきい値を１０２４とした場合には、図２３（ｂ）のプログラム３６２に示されるように、ループ回数Ｎが１０２４を超える場合には、最初の１０２４回のループ処理については二重ループを実行し、残りの回数のループ処理については、ピーリングされたループ処理を行うようにする。また、ループ回数Ｎが１０２４以下の場合には、二重ループは実行せずに、ピーリングされたループ処理を実行するようにする。その後、二重ループの最内ループの直前にプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を挿入することにより図２３（ｃ）に示すような最適化されたプログラム３６３が生成される。
【０１１３】
［ループ分割が不要な場合］
図２４は、ループ分割が不要な場合の最適化処理を説明するための図である。図２４（ａ）に示すソースプログラム３７１が入力された場合には、ループ中で１ライン分のデータ（Ａ［ｉ］〜Ａ［ｉ＋３１］）を完全に使い切ってしまう。このような場合には、二重ループ化する必要はない。このため、図２４（ｂ）に示すプログラム３７２ようにループの先頭にループ内で使用されるデータの１ライン先のデータをプリフェッチするプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を挿入することにより最適化が行われる。
【０１１４】
また、ループ内の処理サイクル数がプリフェッチ命令で必要とされる処理サイクル数よりも大きいような場合にも、ループを二重化する必要はなく、ループの先頭にプリフェッチ命令を挿入してもプリフェッチ命令のレイテンシは隠蔽することができる。
【０１１５】
［ループ内でアクセスされる要素がアラインされていない場合］
図２５および図２６は、ループ内でアクセスされる要素が主記憶上で適切にアラインされていない場合のループ分割処理を説明するための図である。これまでの説明では、ループ内でアクセスされる要素が主記憶上で適切にアラインされている場合を想定して話を進めてきた。アラインされていることが予めプラグマや、コンパイルオプションの指定によりわかっている場合には、上述の例で説明したような最適化が行われる。
【０１１６】
しかし、一般的にはコンパイラは、それらの要素がアラインされているか否かは実行時まではわからない。このため、コンパイラは、ループ内アクセス要素が主記憶上で適切にアラインされていないことを前提として最適化を行う必要がある。
【０１１７】
すなわち、図２５（ａ）に示すようなソースプログラム３８１が与えられた場合に、配列Ａの要素サイズを４バイトとすると、図１１を参照して説明したシンプルループ分割と同様にして、最適化が行われる。ただし、要素がアラインされていないことを前提としているため、最内ループの前に挿入されるプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋６４］））は２ライン先の配列Ａの要素をプリフェッチ指定している。また、ループ処理に先立って、ループ内でアクセスされる配列の要素Ａ［０］〜Ａ［６３］を確保するために、プリフェッチ命令（ｄｐｒｅｆ（＆Ａ［０］）およびｄｐｒｅｆ（＆Ａ［３２］））がプリフェッチのレイテンシを十分隠蔽できる位置に挿入され、図２５（ｂ）に示すようなプログラム３８２が生成される。
【０１１８】
また、図２６（ａ）に示されるようなソースプログラム３９１が与えられた場合には、図１６と同様にして、ピーリング処理された部分のループを畳み込んだ後に、２ライン先の配列Ａの要素をプリフェッチする命令（ｄｐｒｅｆ（＆Ａ［ｉ＋６４］））が挿入される。また、プログラム３８２と同様にプリフェッチ命令（ｄｐｒｅｆ（＆Ａ［０］）およびｄｐｒｅｆ（＆Ａ［３２］））が挿入され、図２６（ｂ）に示すような最適化されたプログラム３９２が生成される。
【０１１９】
［動的アライン解析コードの挿入による構造変換分割］
図２７は、アラインされていない配列要素を動的に特定して、ループ処理の最適化を行う処理について説明するための図である。図２７（ａ）に示すソースプログラム４０１が入力された場合を考える。ここで、配列Ａの要素は４バイトであるものとする。
【０１２０】
配列Ａの先頭アドレス（要素Ａ［０］のアドレス）の所定のビットがキャッシュのラインを示しており、そのビット内のさらにあるビットは、ラインの先頭からのオフセットを示している。したがって、「Ａ＆Ｍａｓｋ」というビット同士の論理演算を行うことにより、ラインの先頭からのオフセットを取り出すことができる。ここで、マスク値Ｍａｓｋはあらかじめ定められた値である。配列Ａの先頭アドレスから取り出されたオフセット値を予め定められた補正値Ｃｏｒだけ右シフトすることにより、配列Ａの先頭要素Ａ［０］が１ライン内で先頭から何番目に位置しているかがわかる。よって、次式（３）にしたがって、ライン上でアラインされていない要素の数ｎを求めることができる。
【０１２１】
ｎ＝３２−（Ａ＆Ｍａｓｋ）＞＞Ｃｏｒ                  …（３）
すなわち、図２８に示すように、キャッシュ４３１にフェッチした場合に、アラインされない配列Ａの要素（Ａ［０］〜Ａ［ｎ−１］）とアラインされる配列Ａの要素とが区別されることになる。
【０１２２】
したがって、図２７（ｂ）のプログラム４０２に示すように、式（３）に従いアラインされていない配列Ａの要素数ｎを求める。次に、要素数ｎに従って、アラインされていない配列Ａの要素（Ａ［０］〜Ａ［ｎ−１］）についてのループ処理を行う。その後、アラインされている配列Ａの要素（Ａ［ｎ］以降の要素）については、図１１に示したシンプルループ分割の場合と同様に二重ループ化を行う。
【０１２３】
その後、ピーリングされているループ４０５について、畳み込み処理を行うと、図２７（ｃ）に示すようなプログラム４０３が生成される。また、図２７（ｄ）に示すように、プリフェッチ命令（ｄｐｒｅｆ（＆Ａ［ｉ＋３２］））を挿入することにより、最適化されたプログラム４０４が得られる。
【０１２４】
［プロファイル情報を用いた構造変換分割］
図２９は、アラインされていない配列要素をプロファイル情報を用いて特定し、ループ処理の最適化を行う処理について説明するための図である。アラインされていない配列の要素数を図２７のように計算から求めるのではなく、プロファイル情報から取得する。取得したアラインされていない配列の要素数Ｎに基づいて、図２７に示したのと同様の処理を行い、図２９（ａ）に示すソースプログラム４１１を図２９（ｂ）に示すプログラム４１２のように変換する。その後、ピーリングされたループ部分を畳み込み、図２９（ｃ）に示すプログラム４１３を得る。最後に、図２９（ｄ）に示すプリフェッチ命令を挿入することにより最適化されたプログラム４１４を得る。
【０１２５】
［最内ループ以外のループに対する構造変換］
図３０は、最内ループ以外のループに対する構造変換について説明するための図である。
【０１２６】
図３０（ａ）に示すソースプログラム４２１が与えられた場合を考える。ソースプログラム４２１では、二重ループ処理が行われており、最内ループ処理４２４で参照される配列Ａの要素は１バイトであるものとする。最内ループ処理４２４のループ回数は４回であるため、最内ループ処理４２４では配列Ａの要素が４バイト分参照される。したがって、最内ループ処理４２４で参照される要素のバイト数が小さいため、このような場合には、最内ループ処理４２４を１つの固まりとして考え、最外ループを、図３０（ｂ）に示すプログラム４２２のように、二重ループに構造変換する。その後、２番目のループ処理の実行前にキャッシュの１ライン分の配列Ａの要素をプリフェッチする命令（ｄｐｒｅｆ（＆Ａ［ｊ＋１２８］））が挿入され、図３０（ｃ）に示すような最適化されたプログラム４２３が得られる。
【０１２７】
［プラグマ「＃ｐｒａｇｍａ  ＿ｌｏｏｐ＿ｔｉｌｉｎｇ＿ｄｐｒｅｆ  変数名［，変数名］」による変数指定］
図３１は、プラグマ「＃ｐｒａｇｍａ  ＿ｌｏｏｐ＿ｔｉｌｉｎｇ＿ｄｐｒｅｆ  変数名［，変数名］」により変数が指定された場合の最適化処理について説明するための図である。図３１（ａ）に示すように、プラグマ「＃ｐｒａｇｍａ  ＿ｌｏｏｐ＿ｔｉｌｉｎｇ＿ｄｐｒｅｆ  ｂ」との指定がソースプログラム中に含まれる場合には、ループ内の配列ｂのみに着目して構造変換が行われ、配列ａは無視される。従って、図３１（ｂ）に示すような二重ループ化が実行され、配列ｂをプリフェッチする命令のみが挿入される。
【０１２８】
以上説明したように、本実施の形態に係るコンパイラシステムによると、ループ処理を二重化し、最内ループの外側でプリフェッチ命令を実行するようにしている。このため、無駄なプリフェッチ命令の発行を防ぐことができ、プログラム実行時の処理速度を向上させることができる。また、ループ処理を二重化することにより、プリフェッチ命令を実行してから次のプリフェッチ命令を実行するまでのサイクル数を確保することができる。このため、レイテンシを隠蔽し、インターロックを防ぐことができる。
【０１２９】
以上、本発明の実施の形態に係るコンパイルシステムについて、実施の形態に基づいて説明したが、本発明は、この実施の形態に限定されるものではない。
【０１３０】
例えば、命令最適配置部１８７で配置される命令は、プリフェッチ命令に限られず、通常のメモリアクセス命令や外部処理を起動してその処理結果を待つ命令などのような応答待ち命令、実行した結果、結果的にインターロックを起こす可能性のある命令、実行後に所定の資源が参照可能になるまでに複数サイクルを要する命令などであってもよい。応答待ち命令には、常に応答を待つ命令の他に、応答を待つ場合と待たない場合とがある命令も含む。
【０１３１】
また、キャッシュを備えないコンピュータのＣＰＵをターゲットプロセッサとして、各種処理のレイテンシを隠蔽し、インターロックを防ぐようなコードを出力するコンパイルシステムであってもよい。
【０１３２】
さらに、ＣＰＵで実行させる機械語命令列を逐次解釈しながら、本実施の形態で説明したループ構造変換等の処理を実行するＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）として実現してもよい。
【０１３３】
また、以下に示すようなＰｒｅＴｏｕｃｈ命令のように、インターロックを起こす可能性のない命令に対しても本発明は適用可能である。ＰｒｅＴｏｕｃｈ命令とは、引数で指定される変数を記憶するための領域をキャッシュ上に事前に確保するのみの処理を行う命令である。以下に、ループの構造変換を行い、ＰｒｅＴｏｕｃｈ命令を挿入する処理について説明する。
【０１３４】
［シンプルループ分割］
図３２は、ＰｒｅＴｏｕｃｈ命令挿入時において、対象領域がキャッシュサイズでアラインされており、ピーリングが必要ない場合のシンプルループ分割処理について説明するための図である。
【０１３５】
図３２（ａ）に示すようなソースプログラム５０２が入力された場合について考える。このソースプログラム５０２では、ループ回数ｉと変数ｖａｌとの演算結果（乗算結果）を配列Ａの要素に順次代入する処理を定義している。ここで、配列Ａの各要素のサイズは４バイトであるものとし、キャッシュの１ラインサイズは１２８バイト（以降の説明でも、キャッシュのラインサイズは１２８バイトであるものとする。）であるものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。また、ソースプログラム５０２に含まれるループのイテレーションの回数１２８回は、３２の整数倍である。
【０１３６】
このため、ソースプログラム５０２は、図３２（ｂ）のプログラム５０４に示すように、二重ループに構造変換することができる。すなわち、最内ループでは３２回の繰り返し処理を行い、その外のループでは、最内ループを４回繰返すループ処理を行う。最内ループ処理ではキャッシュの１ライン分のデータが配列Ａに代入される。その後、図３２（ｃ）のプログラム５０６に示されるように、最内ループの実行前に、キャッシュ領域確保命令（ＰｒｅＴｏｕｃｈ（＆Ａ［ｉ］））が挿入される。ＰｒｅＴｏｕｃｈ命令を挿入することにより、最内ループ実行時には、当該ループで定義される配列Ａの要素がキャッシュ領域に確保されていることになる。これにより、不要なメインメモリからのデータ転送を引き起こすことがなくなり、バス占有率を軽減することができるようになる。
【０１３７】
図３３は、ＰｒｅＴｏｕｃｈ命令挿入時におけるピーリングが必要な場合のシンプルループ分割処理について説明するための図である。
【０１３８】
図３３（ａ）に示すようなソースプログラム５１２が入力された場合について考える。このソースプログラム５１２では、ループ回数ｉと変数ｖａｌとの演算結果（乗算結果）が配列Ａの要素に順次代入する処理を定義している。ここで、配列Ａの各要素のサイズは４バイトでキャッシュサイズにアラインされているものとする。すなわち、キャッシュの１ラインには配列Ａの要素が３２個記憶される。また、ソースプログラム５１２に含まれるループのイテレーションの回数は１４０回であるものとする。すなわち、１ラインに記憶される配列Ａの要素数３２で割った場合に余りが出る数である。
【０１３９】
このような場合には、図３３（ｂ）に示すプログラム５１４のように、１４０を３２で割った余りのループ回数をピーリングし、それ以外の部分を図３２（ｂ）と同様に二重ループ構造に構造変換する。その後、ピーリングされた部分を二重ループ構造に含ませるためのピーリング畳み込み処理を行い、図３３（ｃ）に示すようなプログラム５１６が得られる。すなわち、通常状態では最内ループで３２回の繰り返し処理が行われ、最後に最内ループが実行される場合には、残りの１２（＝１４０−１２８）回の繰り返し処理が行われる。その後、図３３（ｄ）のプログラム５１８に示されるように、最内ループの実行前に、キャッシュ領域確保命令（ＰｒｅＴｏｕｃｈ（＆Ａ［ｉ］））が挿入される。ただし、領域確保処理は、１ライン単位で行なわれる。このため、オブジェクトＡ以外の領域を確保する可能性がある最後の最内ループ実行時には、ＰｒｅＴｏｕｃｈ命令を発行しないようにし、オブジェクトＡ以外の領域を確保しないようにする。
【０１４０】
［動的アライン解析コードの挿入による構造変換分割］
図３４は、アラインされていない配列要素を動的に特定して、ループ処理の最適化を行う処理について説明するための図である。図３４（ａ）に示すソースプログラム５２２が入力された場合を考える。ここで、配列Ａの要素は４バイトであるものとする。
【０１４１】
配列Ａの先頭アドレス（要素Ａ［０］のアドレス）の所定のビットがキャッシュのラインを示しており、そのビット内のさらにあるビットは、ラインの先頭からのオフセットを示している。したがって、「Ａ＆Ｍａｓｋ」というビット同士の論理演算を行うことにより、ラインの先頭からのオフセットを取り出すことができる。ここで、マスク値Ｍａｓｋはあらかじめ定められた値である。ここでは、［Ｍａｓｋ＝０ｘ７Ｆ］としている。ループ初回にアクセスされる配列Ａの要素のアドレスから取り出されたオフセット値を、マスク値Ｍａｓｋから減算を行い、予め定められた補正値Ｃｏｒだけ右シフトすることにより、配列Ａの要素Ａ［Ｘ］が１ライン内で先頭から何番目に位置しているかがわかる。よって、次式（４）にしたがって、ライン上でアラインされていない要素の数ＰＲＬＧを求めることができる。
【０１４２】
ＰＲＬＧ  ＝（Ｍａｓｋ  −  (＆Ａ［Ｘ］) ＆ Ｍａｓｋ）＞＞Ｃｏｒ    …（４）
さらに、ループの最後に参照される配列Ａの要素（Ａ［Ｙ−１］）の次の要素（Ａ［Ｙ］）が１ライン内で先頭から何番目に位置しているかを、次式（５）に従って求めることにより、１ラインを満たしきれていない要素の数ＥＰＬＧで求めることができる。
【０１４３】
ＥＰＬＧ  ＝ （＆Ａ［Ｙ］) ＆ Ｍａｓｋ）＞＞Ｃｏｒ                  …（５）
さらに、１ライン分の処理を余ることなく行うループ回数ＫＲＮＬを次式（６）に従って求めることができる。
【０１４４】
ＫＮＲＬ ＝  （Ｙ−Ｘ）−（ＰＲＬＧ＋ＥＰＬＧ)                    …（６）
すなわち、図３４（ｂ）のプログラム５２４に示すように、キャッシュの領域に配列Ａが割当てられる場合に、アラインされない配列Ａの要素（Ａ［Ｘ］〜Ａ［Ｘ＋ＰＲＬＧ−１］）と、アラインされかつ１ラインの倍数のサイズとなる配列Ａの要素（Ａ［Ｘ＋ＰＲＬＧ］〜Ａ［Ｘ＋ＰＲＬＧ＋ＫＲＮＬ−１］）と、アラインされているが１ラインのサイズを満たさない配列Ａの要素（Ａ［Ｘ＋ＰＲＬＧ＋ＫＲＮＬ］〜Ａ［Ｘ＋ＰＲＬＧ＋ＫＲＮＬ＋ＥＲＬＧ−１］）とが区別されることになる。
【０１４５】
したがって、図３４（ｂ）のプログラム５２４に示すように、式（４）に従ったアラインされていない配列Ａの要素数ＰＲＬＧを求める処理等が行なわれる。次に、要素数ＰＲＬＧに従って、アラインされていない配列Ａの要素（Ａ［Ｘ］〜Ａ［Ｘ＋ＰＲＬＧ−１］）についてのループ処理を行う。その後、アラインされている配列Ａの要素（Ａ［Ｘ＋ＰＲＬＧ］〜Ａ［Ｘ＋ＰＲＬＧ＋ＫＲＮＬ−１］の要素）については、図３２（ｂ）に示したシンプルループ分割の場合と同様に二重ループ化を行う。さらに、ＥＰＬＧ＞０であるならば、ピーリング処理が必要となる為、図３３（ｂ）に示したピーリング必要時の場合と同様にピーリング処理を行う。
【０１４６】
その後、ピーリングされているループについて、畳み込み処理を行うと、図３４（ｃ）に示すようなプログラム５２６が生成される。また、図３４（ｄ）に示すように、キャッシュ領域確保命令（ＰｒｅＴｏｕｃｈ（＆Ａ［ｉ］））が挿入することにより、最適化されたプログラム５２８が得られる。
【０１４７】
ただし、領域確保命令を挿入するのは、アラインされている領域でかつキャッシュの１ライン全てを使用する最内ループに対してのみである。
【産業上の利用可能性】
【０１４８】
本発明はインターロックを起こす可能性のある命令の発行を制御するコンパイラ、ＯＳ、プロセッサで実行されるプロセス等に適用できる。
【図面の簡単な説明】
【０１４９】
【図１】図１は、従来の最適化技術の問題点を説明するための図である。
【図２】図２は、本発明によるループ処理の構造変換を説明するための図である。
【図３】図３は、本実施の形態に係るコンパイラシステムの構成を示す図である。
【図４】図４は、コンパイラの構成を示す図である。
【図５】図５は、コンパイラが実行する処理のフローチャートである。
【図６】図６は、ループ構造変換処理の詳細を説明するための図である。
【図７】図７は、コピー型内側ループ分割処理の詳細を示すフローチャートである。
【図８】図８は、条件型内側ループ分割処理の詳細を示すフローチャートである。
【図９】図９は、プリフェッチ命令配置処理の詳細を示すフローチャートである。
【図１０】図１０は、プリフェッチ命令挿入処理の詳細を示すフローチャートである。
【図１１】図１１は、ピーリングが必要ない場合のシンプルループ分割処理について説明するための図である。
【図１２】図１２は、ピーリングが必要のない場合のソースプログラムの一例を示す図である。
【図１３】図１３は、図１２に示したソースプログラムに対応する中間言語のプログラムを示す図である。
【図１４】図１４は、図１３に示された中間言語のプログラムを二重ループに構造変換した後の中間言語のプログラムを示す図である。
【図１５】図１５は、図１４に示された中間言語のプログラムにプリフェッチ命令を挿入した後の中間言語のプログラムを示す図である。
【図１６】図１６は、ピーリングが必要な場合のシンプルループ分割処理について説明するための図である。
【図１７】図１７は、ループ内に複数の配列アクセスが存在する場合のループ分割処理について説明するための図である。
【図１８】図１８は、ループ内に複数の配列アクセスが存在する場合のループ分割処理について説明するための図である。
【図１９】図１９は、ループ内に複数の配列アクセスが存在し、かつ配列の要素のサイズがすべて同じではない場合のループ分割処理について説明するための図である。
【図２０】図２０は、ループ内に複数の配列アクセスが存在し、かつ配列の要素のサイズがすべて同じではない場合のループ分割処理について説明するための図である。
【図２１】図２１は、ループ内にストライドが異なる複数の配列アクセスが存在する場合のループ分割処理について説明するための図である。
【図２２】図２２は、ループ回数が不定なループ処理のループ分割処理を説明するための図である。
【図２３】図２３は、ループ回数が不定なループ処理のループ分割処理を説明するための他の図である。
【図２４】図２４は、ループ分割が不要な場合の最適化処理を説明するための図である。
【図２５】図２５は、ループ内でアクセスされる要素が主記憶上で適切にアラインされていない場合のループ分割処理を説明するための図である。
【図２６】図２６は、ループ内でアクセスされる要素が主記憶上で適切にアラインされていない場合のループ分割処理を説明するための図である。
【図２７】図２７は、アラインされていない配列要素を動的に特定して、ループ処理の最適化を行う処理について説明するための図である。
【図２８】図２８は、アラインされていない配列要素を説明するための図である。
【図２９】図２９は、アラインされていない配列要素をプロファイル情報を用いて特定し、ループ処理の最適化を行う処理について説明するための図である。
【図３０】図３０は、最内ループ以外のループに対する構造変換について説明するための図である。
【図３１】図３１は、プラグマ「＃ｐｒａｇｍａ  ＿ｌｏｏｐ＿ｔｉｌｉｎｇ＿ｄｐｒｅｆ  変数名［，変数名］」により変数が指定された場合の最適化処理について説明するための図である。
【図３２】図３２は、ＰｒｅＴｏｕｃｈ命令挿入時におけるピーリングが必要ない場合のシンプルループ分割処理について説明するための図である。
【図３３】図３３は、ＰｒｅＴｏｕｃｈ命令挿入時におけるピーリングが必要な場合のシンプルループ分割処理について説明するための図である。
【図３４】図３４は、アラインされていない配列要素を動的に特定して、ループ処理の最適化を行う処理について説明するための図である。
【符号の説明】
【０１５０】
１４１  ソースプログラム
１４２  キャッシュパラメータ
１４３  アセンブラファイル
１４４  オブジェクトファイル
１４５  実行プログラム
１４６  実行ログデータ
１４７  プロファイルデータ
１４８  コンパイラシステム
１４９  コンパイラ
１５０  アセンブラ
１５１  リンカ
１５２  シミュレータ
１５３  プロファイラ
１８１  最適化補助情報
１８２  構文解析部
１８３  最適化情報解析部
１８４  一般最適化部
１８５  命令スケジューリング部
１８６  ループ構造変換部
１８７  命令最適配置部
１８８  コード出力部
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2005078579.tif 000042
【図２】
2005078579.tif 000043
【図３】
2005078579.tif 000044
【図４】
2005078579.tif 000045
【図５】
2005078579.tif 000046
【図６】
2005078579.tif 000047
【図７】
2005078579.tif 000048
【図８】
2005078579.tif 000049
【図９】
2005078579.tif 000050
【図１０】
2005078579.tif 000051
【図１１】
2005078579.tif 000052
【図１２】
2005078579.tif 000053
【図１３】
2005078579.tif 000054
【図１４】
2005078579.tif 000055
【図１５】
2005078579.tif 000056
【図１６】
2005078579.tif 000057
【図１７】
2005078579.tif 000058
【図１８】
2005078579.tif 000059
【図１９】
2005078579.tif 000060
【図２０】
2005078579.tif 000061
【図２１】
2005078579.tif 000062
【図２２】
2005078579.tif 000063
【図２３】
2005078579.tif 000064
【図２４】
2005078579.tif 000065
【図２５】
2005078579.tif 000066
【図２６】
2005078579.tif 000067
【図２７】
2005078579.tif 000068
【図２８】
2005078579.tif 000069
【図２９】
2005078579.tif 000070
【図３０】
2005078579.tif 000071
【図３１】
2005078579.tif 000072
【図３２】
2005078579.tif 000073
【図３３】
2005078579.tif 000074
【図３４】
2005078579.tif 000075
【国際調査報告】
2005078579.tif 000076
2005078579.tif 000077
2005078579.tif 000078
2005078579.tif 000079