(57)【要約】【課題】キャッシュメモリ上の必要なデータの上書きを防ぎ、キャッシュの利用効率を向上することを課題とする。【解決手段】コンパイラ装置１０は、ソースプログラムを解析し、アクセスするメモリ領域を所定のブロックに分割するループブロッキングのパターンにソースプログラムが該当するか判定する。そして、コンパイラ装置１０は、ループブロッキングのパターンに該当すると判定された場合には、次に処理するブロックに対してプリフェッチ命令を生成する。【選択図】        図１
2010244208.tif 000002
【特許請求の範囲】
【請求項１】
ソースコードを解析し、アクセスするメモリ領域を所定のブロックに分割するループブロッキングのパターンに前記ソースコードが該当するか判定するソース解析手順と、
前記ソース解析手順によって前記ループブロッキングのパターンに該当すると判定された場合には、次に処理するブロックに対してプリフェッチ命令を生成するプリフェッチ命令生成手順と、
をコンピュータに実行させることを特徴とするプリフェッチ生成プログラム。
【請求項２】
前記ソース解析手順は、前記ソースコードを解析し、当該ソースコードが前記ループブロッキングのパターンに該当するとともに、前記ブロックのサイズが静的に判断できるか判定し、静的に判断できると判定した場合には、キャッシュメモリに前記プリフェッチ命令を生成するだけの余裕があるか判定し、
前記プリフェッチ命令生成手順は、前記ソース解析部によってキャッシュメモリに前記プリフェッチ命令を生成するだけの余裕があると判定された場合には、次に処理するブロックに対してプリフェッチ命令を生成し、前記ソース解析部によってキャッシュメモリに前記プリフェッチ命令を生成するだけの余裕がないと判定された場合には、プリフェッチを抑止することを特徴とする請求項１に記載のプリフェッチ生成プログラム。
【請求項３】
前記ソース解析手順は、ソースコードを解析し、当該ソースコードが前記ループブロッキングのパターンに該当するとともに、前記ブロックのサイズが静的に判断できるか判定し、
前記プリフェッチ命令生成手順は、前記ソース解析部によって静的に判断できないと判定された場合には、プリフェッチ生成ループおよびプリフェッチ未生成ループを生成することを特徴とする請求項１に記載のプリフェッチ生成プログラム。
【請求項４】
ソースコードを解析し、アクセスするメモリ領域を所定のブロックに分割するループブロッキングのパターンに前記ソースコードが該当するか判定するソース解析部と、
前記ソース解析部によって前記ループブロッキングのパターンに該当すると判定された場合には、次に処理するブロックに対してプリフェッチ命令を生成するプリフェッチ命令生成部と、
を備えることを特徴とするコンパイラ装置。
【請求項５】
前記ソース解析部は、ソースコードを解析し、当該ソースコードが前記ループブロッキングのパターンに該当するとともに、前記ブロックのサイズが静的に判断できるか判定し、静的に判断できると判定した場合には、キャッシュメモリに前記プリフェッチ命令を生成するだけの余裕があるか判定し、
前記プリフェッチ命令生成部は、前記ソース解析部によってキャッシュメモリに前記プリフェッチ命令を生成するだけの余裕があると判定された場合には、次に処理するブロックに対してプリフェッチ命令を生成し、前記ソース解析部によってキャッシュメモリに前記プリフェッチ命令を生成するだけの余裕がないと判定された場合には、プリフェッチを抑止することを特徴とする請求項４に記載のコンパイラ装置。
【請求項６】
前記ソース解析部は、ソースコードを解析し、当該ソースコードが前記ループブロッキングのパターンに該当するとともに、前記ブロックのサイズが静的に判断できるか判定し、
前記プリフェッチ命令生成部は、前記ソース解析部によって静的に判断できないと判定された場合には、プリフェッチ生成ループおよびプリフェッチ未生成ループを生成することを特徴とする請求項４に記載のコンパイラ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プリフェッチ命令を生成するプリフェッチ生成プログラムおよびコンパイラ装置に関する。
【背景技術】
【０００２】
従来より、ＣＰＵとメモリの間にメモリよりも高速なキャッシュメモリを用意し、実際のメモリアクセス命令が動く前にあらかじめデータをキャッシュメモリに持つことで、メモリへのアクセスレイテンシを隠蔽する技術が知られている。このようなキャッシュメモリを効率的に利用するために、コンパイラの最適化の技術として、ソフトウェアプリフェッチの最適化とループブロッキングの最適化とが実施されている。
【０００３】
ソフトウェアプリフェッチの最適化とは、図１３に例示するような多重ループに対して、図１４に示すように最内の次元の観点でプリフェッチ命令（図１４の例では、ＩがＸＸ回転後のデータをプリフェッチするプリフェッチ命令）を生成する。プリフェッチ命令とは、あるデータを実際に使用する前にキャッシュメモリにそのデータをあらかじめ持っていき、実際のメモリへのアクセスレイテンシを隠蔽するために用いられる。なお、図１４に示す「ＸＸ回転」は、メモリアクセスレイテンシに依存する。
【０００４】
また、ループブロッキング最適化とは、アクセスするメモリ領域をいくつかのブロックに分け、メモリアクセスに局所性を持たせる技術である。ここで、ソフトウェアプリフェッチの最適化について詳しく説明する前に、メモリアクセスの順とキャッシュメモリの状態について説明する。
【０００５】
例えば、メモリは、図１５に示すように、メモリアクセスを行う順番を配列として割り付けられている。つまり、図１５の例では、「１，１」、「２，１」、「３，１」・・・の順でメモリアクセスが順次行われる。このため、メモリ上ではＡ（１，１）とＡ（２，１）が隣り合って並んでいるが、Ａ（１，１）とＡ（１，２）が離れた位置に割り付けられていることとなる。
【０００６】
ここで、図１６および図１７を用いて、配列Ａ、配列Ｂのメモリアクセスの順とキャッシュメモリの状態をそれぞれ説明する。配列Ａのアクセスでは、（１，１）の後すぐにアクセスする（２，１）〜（４，１）がキャッシュメモリヒットするので、４回に１回のメモリアクセスで済んでいる。
【０００７】
一方、配列Ｂのアクセスでは、（１，１）の後すぐに、Ｉが変化することで飛び飛びのアクセスとなり、キャッシュメモリをすぐに全て使用してしまい、メモリへのアクセス数が多くなってしまう。例えば、図１７に例示するように、Ｂ（１，１）のアクセスをした時にキャッシュメモリが保持するＢ（２，１）について、Ｂ（１，１７）のアクセスをした時に、Ｂ（１，１）のキャッシュメモリのデータを上書きしてしまう。
【０００８】
そして、Ｂ（２，１）のアクセス時には、すでに上書きされてしまった後であるため再びメモリアクセスすることとなる。つまり、配列Ｂのアクセスは全てメモリアクセスとなり、キャッシュメモリの効率化を図れていない。
【０００９】
このため、ループブロッキング最適化を行って、アクセスするメモリ領域をいくつかのブロックに分け、メモリアクセスに局所性を持たせる。つまり、図１８に例示するように、ループを変形することで、配列Ｂのメモリアクセスが局所性を持ちたせる。なお、図１８に示すブロック数は、キャッシュメモリのサイズに依存している。
【００１０】
ここで、図１９および図２０を用いて、「変数ＹＹ＝４」の場合における配列Ａと配列Ｂのメモリアクセス順番と、配列Ｂのキャッシュメモリの状態について説明する。図１９に示すように、メモリ領域がブロック「（１）」、「（２）」、「（３）」・・としてそれぞれ分けられ、「（１）」、「（２）」、「（３）」・・の順番で各ブロックが順次アクセスされる。
【００１１】
その結果、図２０に示すように、配列Ｂ（１，１）のアクセスで載せたＢ（１，１）〜Ｂ（４，１）までのキャッシュメモリのデータを局所的にアクセスするようになり、Ｂ（２，１）、Ｂ（３，１）、Ｂ（４，１）が上書きされる前に使用することができるため図１７の例と比べてメモリへのアクセス数が減り、キャッシュメモリの効率化が図れる。
【００１２】
なお、ソフトウェアプリフェッチの最適化とループブロッキングの最適化とは、それぞれ独立して動作している。つまり、図２１に示すように、両方の最適化を行った場合には、プリフェッチ最適化とループブロッキング最適化の両方がそれぞれ独立して動作するオブジェクトが生成される。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開平８−２８６９１４号公報
【特許文献２】特開平１０−２９３６９２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
ところで、上記したプリフェッチ最適化とループブロッキング最適化とを両方行う技術では、それぞれ独立して動作するので、キャッシュメモリ上の必要なデータが上書きされる結果、キャッシュを効率よく利用できていないという課題があった。
【００１５】
つまり、ソフトウェアプリフェッチ最適化とは、メモリアクセスの連続性が長いレンジで継続することを前提とした最適化である。このため、ループブロッキング最適化とソフトウェアプリフェッチ最適化が両方動作した場合には、プリフェッチしたデータが使用されないばかりか、必要なデータを上書きしてしまう場合がある。
【００１６】
例えば、図２２の例を用いて説明すると、「ＸＸ＝２４」とした場合の配列Ｂに対するプリフェッチ命令は、実際に実行されるロード命令と比べて、２４回転先に使用するデータをキャッシュメモリに載せる。この場合に、図２３に例示するように、ＩＩ＝１、２、３、４と動く時にプリフェッチされるＢ（１，２５）、Ｂ（１，２６）、Ｂ（１，２７）、Ｂ（１，２８）のキャッシュメモリ上の配置は、ｉｉ＝９、１０、１１、１２時のロード命令のＢ（１，９）、Ｂ（１，１０）、Ｂ（１，１１）、Ｂ（１，１２）と競合する。
【００１７】
そのため、ｉｉ＝２５、２６、２７、２８時のロード命令がアクセスするタイミングに、キャッシュメモリ上の必要なデータが上書きされる結果、ロード命令がメモリアクセスになってしてしまい、キャッシュを効率よく利用できていないという問題があった。
【００１８】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、キャッシュメモリ上の必要なデータの上書きを防ぎ、キャッシュメモリの利用効率を向上することを目的とする。
【課題を解決するための手段】
【００１９】
上述した課題を解決し、目的を達成するため、この装置は、ソースコードを解析し、ループブロッキングのパターンに該当するか判定し、ループブロッキングのパターンに該当すると判定された場合には、次に処理するブロックに対してプリフェッチ命令を生成することを要件とする。
【発明の効果】
【００２０】
開示の装置は、ループブロッキングのパターンに該当すると判定された場合には、次に処理するブロックに対してプリフェッチ命令を生成するので、キャッシュメモリ上の必要なデータの上書きを防ぐ結果、キャッシュメモリの利用効率を向上することができるという効果を奏する。
【図面の簡単な説明】
【００２１】
【図１】図１は、実施例１に係るコンパイラ装置の構成を示すブロック図である。
【図２】図２は、ブロック数が静的に分からないケースのプログラムを示す図である。
【図３】図３は、キャッシュメモリにプリフェッチ命令を生成するだけの余裕があるか判定するための計算例を示す図である。
【図４】図４は、ハードウェア情報の一例を示す図である。
【図５】図５は、生成されたオブジェクトの一例を示す図である。
【図６】図６は、ロード命令とプリフェッチ命令との関係を示す図である。
【図７】図７は、生成されたオブジェクトの一例を示す図である。
【図８】図８は、キャッシュメモリのイメージ図である。
【図９】図９は、実施例１に係るコンパイラ装置の処理全体の動作を示すフローチャートである。
【図１０】図１０は、実施例１に係るコンパイラ装置の解析処理の動作を示すフローチャートである。
【図１１】図１１は、実施例１に係るコンパイラ装置の二重生成処理の動作を示すフローチャートである。
【図１２】図１２は、プリフェッチ生成プログラムを実行するコンピュータを示す図である。
【図１３】図１３は、多重ループの説明をするための図である。
【図１４】図１４は、ソフトウェアプリフェッチの最適化の説明をするための図である。
【図１５】図１５は、メモリに割り付けられる順番について説明するための図である。
【図１６】図１６は、メモリアクセスの順番について説明するための図である。
【図１７】図１７は、キャッシュメモリの状態について説明するための図である。
【図１８】図１８は、ループブロッキング最適化について説明するための図である。
【図１９】図１９は、メモリアクセスの順番について説明するための図である。
【図２０】図２０は、キャッシュメモリの状態を説明するための図である。
【図２１】図２１は、プリフェッチ最適化とループブロッキング最適化の両方が動作した状態を説明するための図である。
【図２２】図２２は、ロード命令とプリフェッチ命令との関係を示す図である。
【図２３】図２３は、プリフェッチ最適化とループブロッキング最適化の両方が動作した状態を説明するための図である。
【発明を実施するための形態】
【００２２】
以下に添付図面を参照して、この発明に係るプリフェッチ生成プログラムおよびコンパイラ装置の実施例を詳細に説明する。
【実施例１】
【００２３】
以下の実施例では、実施例１に係るコンパイラ装置の構成および処理の流れを順に説明し、最後に実施例１による効果を説明する。
【００２４】
［コンパイラ装置の構成］
まず最初に、図１を用いて、コンパイラ装置１０の構成を説明する。図１は、実施例１に係るコンパイラ装置１０の構成を示すブロック図である。同図に示すように、このコンパイラ装置１０は、制御部１２を有する。
【００２５】
制御部１２は、各種の処理手順などを規定したプログラムおよび所要データを格納するための内部メモリを有し、これらによって種々の処理を実行するが、特に、ソース解析部１２ａ、最適化部１２ｂ、コード生成部１２ｃを有する。以下にこれらの各部の処理を説明する。
【００２６】
ソース解析部１２ａは、ソースプログラム１１を解析し、ループブロッキングのパターンにソースコードが該当するか判定する。具体的には、ソース解析部１２ａは、ソースプログラム１１を取得し、取得されたソースプログラム１１を解析してループがあるか判定する。例えば、ソース解析部１２ａは、ソースプログラム１１内に「ＤＯ文」があるか解析し、「ＤＯ文」がある場合には、ループがあると判定する。
【００２７】
そして、ソース解析部１２ａは、ループがあると判定した場合には、多重ループであるか判定する。例えば、ソース解析部１２ａは、ソースプログラム１１内に複数の「ＤＯ文」が連続してあるか解析し、「ＤＯ文」が連続してある場合には、多重ループであると判定する。この判定の結果、ソース解析部１２ａは、多重ループがあると判定した場合には、ループブロッキング最適化動作解析処理を行う。
【００２８】
ソース解析部１２ａは、ループブロッキング最適化動作解析処理として、内側ループの初期値が外側ループの誘導変数を使用しているか判定する。その結果、ソース解析部１２ａは、内側ループの初期値が外側ループの誘導変数を使用していると判定した場合には、内側ループの回転数が外側ループの増分値と同じであるか判定する。
【００２９】
この結果、ソース解析部１２ａは、内側ループの回転数が外側ループの増分値と同じであると判定した場合には、ループブロッキングのブロックサイズが静的に分かるか判定する。ブロックサイズが静的に分かるか判定する処理として、ソース解析部１２ａは、ブロックサイズについてソースプログラム内に定義されているか検索し、ブロックサイズについてソースプログラム内に定義されている場合に、ブロックサイズが静的に分かると判定している。
【００３０】
例えば、ソースプログラム内にブロックサイズを示す情報として「ＢＬＯＣＫ＝５」と定義されている場合には、ブロックサイズが静的に分かると判定する。ここで、ループブロッキングのブロックサイズが静的に分かるか否かの判定処理について、図２のソースプログラムの例を用いて説明する。図２は、ブロック数が静的に分からないケースのプログラムを示す図である。図２のソースプログラムの例では、ソース解析部１２ａは、ソースプログラム内にブロックサイズを示す情報が定義されていないので、ブロック数が静的に分からないと判定することとなる。
【００３１】
この判定の結果、ソース解析部１２ａは、ブロック数が静的に分かると判定した場合には、キャッシュメモリにプリフェッチ命令を生成するだけの余裕があるか判定する。例えば、ソース解析部１２ａは、キャッシュメモリにプリフェッチ命令を生成するだけの余裕があるか判定処理として、図３に例示する計算を行って、ループをプリフェッチ対象にするか判断する。
【００３２】
具体的な例を挙げて説明すると、ソース解析部１２ａは、図３に例示するように、最内ループで使用されている配列の数と配列サイズとブロッキング動作ループそれぞれのブロック数を乗算した値の２倍がキャッシュメモリサイズの容量よりも小さいか判定する。この結果、ソース解析部１２ａは、小さいと判定した場合には、ループをプリフェッチ対象と判断する。
【００３３】
ここで、ソース解析部１２ａは、図４に例示するように、上記した計算を行うため、ハードウェア情報の例として、キャッシュメモリの容量を示す「キャッシュメモリサイズ」およびメモリアクセスを一回にした場合にキャッシュメモリへ格納される単位である「キャッシュラインサイズ」を使用している。
【００３４】
この判定の結果、ソース解析部１２ａは、キャッシュメモリにプリフェッチ命令を生成するだけの余裕があると判定した場合には、プリフェッチ命令を生成する旨の指示を最適化部１２ｂに通知する。また、ソース解析部１２ａは、キャッシュメモリにプリフェッチ命令を生成するだけの余裕がないと判定した場合には、ソフトウェアプリフェッチを抑止する旨の指示を最適化部１２ｂに通知する。
【００３５】
また、ソース解析部１２ａは、ブロック数が静的に分からないと判定した場合には、プリフェッチ生成ルートとプリフェッチ未生成ルートの二重生成処理を行う旨の指示を通知する。プリフェッチ生成ルートとプリフェッチ未生成ルートの二重生成処理については、後に図１１を用いて詳述する。
【００３６】
最適化部１２ｂは、ループブロッキングのパターンに該当すると判定された場合には、次に処理するブロックに対してプリフェッチ命令を生成する。具体的には、最適化部１２ｂは、ソース解析部１２ａからプリフェッチ命令を生成する旨の指示を受け付けると、図５に例示するように、次に行うブロックに対してソフトウェアプリフェッチ命令を生成する。また、最適化部１２ｂは、ソフトウェアプリフェッチを抑止する旨の指示を受け付けると、ソフトウェアプリフェッチを抑止する。
【００３７】
また、最適化部１２ｂは、ソース解析部１２ａから二重生成処理を行う旨の指示を受け付けると、オリジナルループのコピーを行う（図７参照）。そして、最適化部１２ｂは、プリフェッチをする余地が残る最大ブロック数を算出する。例えば、最適化部１２ｂは、プリフェッチをする余地が残る最大ブロック数の計算式として、「最大ブロック数＝キャッシュメモリサイズ÷最内ループで使用されている配列の数÷配列サイズ÷２」を算出する。
【００３８】
そして、最適化部１２ｂは、算出された最大ブロック数よりも実際のブロック数が小さいかどうか動的に調べる判定処理を作成し、作成された判定処理において、算出された最大ブロック数よりも小さかったルートのループに対してプリフェッチ命令の生成処理を実施する。つまり、最適化部１２ｂは、ブロック数が静的に判断できないため、図７に例示するように、プリフェッチ生成ルートとプリフェッチ未生成ルートの二重生成を行う。
【００３９】
コード生成部１２ｃは、最適化部１２ｂによって最適化されたソースプログラムをループ単位で処理して、オブジェクトファイル１３を生成する。ここで、最適化されたソースプログラムを動作した時に、「ＩＩ＝１、２、３、４」と変化した時の配列Ｂの実際のロード命令とそのロード命令と同じタイミングで生成されるプリフェッチ命令を図６に示し、その時のキャッシュメモリの状況を図８に示す。
【００４０】
つまり、コンパイラ装置１０では、図６に示すように、ＩＩ＝１、２、３、４と動く時にプリフェッチされるＢ（１，５）、Ｂ（１，６）、Ｂ（１，７）のキャッシュメモリ上の配置は、次に処理されるブロックである。このため、図８に示すように、ブロック（１）をアクセスしているときに、次に処理されるブロックであるブロック（２）をソフトウェアプリフェッチするので、実際のロード命令がブロック（２）を実行するときにはキャッシュメモリミスが起きない。
【００４１】
このように、コンパイラ装置１０では、ループブロッキング最適化動作ループに対して、従来の連続性を意識したソフトウェアプリフェッチ命令を生成するのではなく、次に行うブロックに対してソフトウェアプリフェッチ命令を生成する。その結果、コンパイラ装置１０では、ソフトウェアプリフェッチ命令でキャッシュメモリに載せたデータが従来の技術よりも早くに使用される。さらに、コンパイラ装置１０では、ソフトウェアプリフェッチ命令でキャッシュメモリ上の必要なデータの上書きを防ぐことができる。
【００４２】
［コンパイラ装置による処理］
次に、図９〜図１１を用いて、実施例１に係るコンパイラ装置１０による処理の流れを説明する。図９は、実施例１に係るコンパイラ装置の処理全体の動作を示すフローチャートである。図１０は、実施例１に係るコンパイラ装置の解析処理の動作を示すフローチャートである。図１１は、実施例１に係るコンパイラ装置の二重生成処理の動作を示すフローチャートである。
【００４３】
図９に示すように、コンパイラ装置１０のソース解析部１２ａは、ソースプログラムを取得し、取得されたソースプログラムを解析してループがあるか判定する（ステップＳ１０１）。その結果、ループがないと判定された場合には（ステップＳ１０１否定）、コード生成部１２ｃは、オブジェクトファイル１３を生成して（ステップＳ１０５）、処理を終了する。
【００４４】
一方、ソース解析部１２ａは、ループがあると判定した場合には（ステップＳ１０１肯定）、多重ループであるか判定する（ステップＳ１０２）。その結果、ソース解析部１２ａは、多重ループがないと判定した場合には（ステップＳ１０２否定）、次のループの取り出しを行い（ステップＳ１０４）、Ｓ１０１に戻る。
【００４５】
また、ソース解析部１２ａは、多重ループがあると判定した場合には（ステップＳ１０２肯定）、解析処理（後に、図１０を用いて詳述）を行い（ステップＳ１０３）、その後、次のループの取り出しを行って（ステップＳ１０４）、Ｓ１０１の処理に戻る。
【００４６】
次に、図１０を用いて、実施例１に係るコンパイラ装置１０による解析処理の流れを説明する。図１０に示すように、コンパイラ装置１０のソース解析部１２ａは、内側ループの初期値が外側ループの誘導変数を使用しているか判定する（ステップＳ２０１）。その結果、ソース解析部１２ａは、内側ループの初期値が外側ループの誘導変数を使用していないと判定した場合には（ステップＳ２０１否定）、そのまま解析処理を終了する。
【００４７】
また、ソース解析部１２ａは、内側ループの初期値が外側ループの誘導変数を使用していると判定した場合には（ステップＳ２０１肯定）、内側ループの回転数が外側ループの増分値と同じであるか判定する（ステップＳ２０２）。
【００４８】
この結果、ソース解析部１２ａは、内側ループの回転数が外側ループの増分値と同じでないと判定した場合には（ステップＳ２０２否定）、そのまま解析処理を終了する。また、ソース解析部１２ａは、内側ループの回転数が外側ループの増分値と同じであると判定した場合には（ステップＳ２０２肯定）、ループブロッキングのブロックサイズが静的に分かるか判定する（ステップＳ２０３）。
【００４９】
この結果、ソース解析部１２ａは、ブロック数が静的に分かると判定した場合には（ステップＳ２０３肯定）、キャッシュメモリにプリフェッチ命令を生成するだけの余裕があるか判定する（ステップＳ２０４）。この結果、キャッシュメモリにプリフェッチ命令を生成するだけの余裕があると判定された場合には（ステップＳ２０４肯定）、最適化部１２ｂは、次に行うブロックに対してソフトウェアプリフェッチ命令を生成する（ステップＳ２０５）。
【００５０】
また、キャッシュメモリにプリフェッチ命令を生成するだけの余裕がないと判定された場合には（ステップＳ２０４否定）、最適化部１２ｂは、ソフトウェアプリフェッチを抑止する（ステップＳ２０６）。
【００５１】
ステップＳ２０３の処理に戻って、ブロック数が静的に分からないと判定された場合には（ステップＳ２０３否定）、最適化部１２ｂは、プリフェッチ生成ルートとプリフェッチ未生成ルートの二重生成処理（後に図１１を用いて詳述）を行う（ステップＳ２０７）。
【００５２】
次に、図１１を用いて、実施例１に係るコンパイラ装置１０による二重生成処理の流れを説明する。図１１に示すように、コンパイラ装置１０の最適化部１２ｂは、オリジナルループのコピーを行う（ステップＳ３０１）。そして、最適化部１２ｂは、プリフェッチをする余地が残る最大ブロック数を算出する（ステップＳ３０２）。
【００５３】
そして、最適化部１２ｂは、算出された最大ブロック数よりも実際のブロック数が小さいかどうか動的に調べる判定処理を作成し（ステップＳ３０３）、作成された判定処理において、算出された最大ブロック数よりも小さかったルートのループに対してプリフェッチ命令の生成処理を実施する（ステップＳ３０４）。
【００５４】
[実施例１の効果]
上述してきたように、コンパイラ装置１０は、ソースプログラムを解析し、アクセスするメモリ領域を所定のブロックに分割するループブロッキングのパターンにソースプログラムが該当するか判定する。そして、コンパイラ装置１０は、ループブロッキングのパターンに該当すると判定された場合には、次に処理するブロックに対してプリフェッチ命令を生成する。このため、コンパイラ装置１０では、キャッシュメモリ上の必要なデータの上書きを防ぎ、キャッシュメモリの利用効率を向上することが可能である。
【００５５】
また、実施例１によれば、コンパイラ装置１０は、ソースプログラムを解析し、ループブロッキングのパターンにソースプログラムが該当するとともに、ブロックのサイズが静的に判断できるか判定し、静的に判断できると判定した場合には、キャッシュメモリにプリフェッチ命令を生成するだけの余裕があるか判定する。そして、コンパイラ装置１０は、キャッシュメモリにプリフェッチ命令を生成するだけの余裕があると判定された場合には、次に処理するブロックに対してプリフェッチ命令を生成し、キャッシュメモリにプリフェッチ命令を生成するだけの余裕がないと判定された場合には、プリフェッチを抑止する。このため、キャッシュメモリ上の必要なデータの上書きを防ぎキャッシュメモリの利用効率を向上させる。
【００５６】
また、実施例１によれば、コンパイラ装置１０は、ソースプログラムを解析し、ループブロッキングのパターンにソースプログラムが該当するとともに、ブロックのサイズが静的に判断できるか判定する。そして、コンパイラ装置１０は、静的に判断できないと判定された場合には、ソフトウェアプリフェッチ生成ループおよびソフトウェアプリフェッチ未生成ループを生成する。このため、ブロックのサイズが静的に判断できない場合には、ソフトウェアプリフェッチ生成ループおよびソフトウェアプリフェッチ未生成ループの２ルートを生成し、いずれルートを用いるか動的に判断する。この結果、プリフェッチ命令を生成するか否かを動的に判断して、キャッシュメモリ上の必要なデータの上書きを防ぎ、キャッシュメモリの利用効率を向上することが可能である。
【実施例２】
【００５７】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。そこで、以下では実施例２として本発明に含まれる他の実施例を説明する。
【００５８】
（１）システム構成等
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、ソース解析部１２ａと最適化部１２ｂを統合してもよい。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【００５９】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【００６０】
（２）プログラム
ところで、上記の実施例で説明した各種の処理は、あらかじめ用意されたプログラムをコンピュータで実行することによって実現することができる。そこで、以下では、図１２を用いて、上記の実施例と同様の機能を有するプログラムを実行するコンピュータの一例を説明する。図１２は、プリフェッチ生成プログラムを実行するコンピュータを示す図である。
【００６１】
同図に示すように、コンパイラ装置としてのコンピュータ６００は、ＨＤＤ６１０、ＲＡＭ６２０、ＲＯＭ６３０およびＣＰＵ６４０をバス６５０で接続して構成される。
【００６２】
そして、ＲＯＭ６３０には、上記の実施例と同様の機能を発揮するプリフェッチ生成プログラム、つまり、図１２に示すように、ソース解析プログラム６３１、最適化プログラム６３２、コード生成プログラム６３３が予め記憶されている。なお、プログラム６３１〜６３３については、図１に示したコンパイラ装置の各構成要素と同様、適宜統合または分散してもよい。
【００６３】
そして、ＣＰＵ６４０が、これらのプログラム６３１〜６３３をＲＯＭ６３０から読み出して実行することで、図１２に示すように、各プログラム６３１〜６３３は、ソース解析プロセス６４１、最適化プロセス６４２、コード生成プロセス６４３として機能するようになる。各プロセス６４１〜６４３は、図１に示したソース解析部１２ａ、最適化部１２ｂ、コード生成部１２ｃにそれぞれ対応する。
【符号の説明】
【００６４】
１０  コンパイラ装置
１１  ソースプログラム
１２  制御部
１２ａ  ソース解析部
１２ｂ  最適化部
１２ｃ  コード生成部
１３  オブジェクトファイル
６００  コンパイラ装置
６１０  ＨＤＤ
６２０  ＲＡＭ
６３０  ＲＯＭ
６３１  ソース解析プログラム
６３２  最適化プログラム
６３３  コード生成プログラム
６４０  ＣＰＵ
６４１  ソース解析プロセス
６４２  最適化プロセス
６４３  コード生成プロセス
６５０  バス
【図１】
2010244208.tif 000003
【図２】
2010244208.tif 000004
【図３】
2010244208.tif 000005
【図４】
2010244208.tif 000006
【図５】
2010244208.tif 000007
【図６】
2010244208.tif 000008
【図７】
2010244208.tif 000009
【図８】
2010244208.tif 000010
【図９】
2010244208.tif 000011
【図１０】
2010244208.tif 000012
【図１１】
2010244208.tif 000013
【図１２】
2010244208.tif 000014
【図１３】
2010244208.tif 000015
【図１４】
2010244208.tif 000016
【図１５】
2010244208.tif 000017
【図１６】
2010244208.tif 000018
【図１７】
2010244208.tif 000019
【図１８】
2010244208.tif 000020
【図１９】
2010244208.tif 000021
【図２０】
2010244208.tif 000022
【図２１】
2010244208.tif 000023
【図２２】
2010244208.tif 000024
【図２３】
2010244208.tif 000025