(57)【要約】【課題】キャッシュを有効的に利用することによりプログラムの実行性能を向上すること。  【解決手段】ループ構造解析部３１、配列解析部３２およびアクセスパターン解析部３３は、ソースプログラムの各ループの前後関係、各ループにて利用される配列データおよびデータのアクセスパターンを解析し、依存関係解析部３４は、アクセスパターンから、前後のループにおいて処理されるデータの依存関係を解析する。部分キャッシュ指示部３５は、依存関係に基づいて、前のループにおいて処理されたデータの格納先をメモリまたはキャッシュのいずれかに割り振るように決定し、最適化部３６は、格納先が決定された前のループを、キャッシュ利用のループおよびブロックストア命令のループに置き換えた新規ソースプログラムを生成し、オブジェクトファイル生成部３７は、新規ソースプログラムからオブジェクトファイルを生成する。【選択図】図２
2010244204.tif 000002
【特許請求の範囲】
【請求項１】
ソースプログラムにおける各ループのデータへのアクセスパターンを解析するアクセスパターン解析手順と、
前記アクセスパターン解析手順によって解析された前記アクセスパターンから、現ループにおいて処理されるデータと次ループにおいて処理されるデータとの依存関係を解析する依存関係解析手順と、
前記依存関係解析手順によって解析された前記依存関係に基づいて、前記現ループにおいて処理されたデータの格納先をメモリまたはキャッシュのいずれかに割り振るように決定する格納先決定手順と、
前記格納先決定手順によって格納先が決定された現ループを、前記メモリに処理済みデータを格納するための第一ループおよび前記キャッシュに処理済みデータを格納するための第二ループに置き換えることにより、前記ソースプログラムから新規ソースプログラムを生成する新規ソースプログラム生成手順と、
前記新規ソースプログラム生成手順によって生成された前記新規ソースプログラムからオブジェクトファイルを生成するオブジェクトファイル生成手順と、
をコンピュータに実行させることを特徴とするコンパイラプログラム。
【請求項２】
前記依存関係解析手順は、前記依存関係として、前記現ループにおいて処理されるデータの順番と、当該現ループの処理済みデータが前記次ループにおいて処理される順番とが順方向であるか逆方向であるかを解析し、
前記格納先決定手順は、前記依存関係解析手順によって解析された前記依存関係が順方向である場合、前記現ループの処理済みデータのうちキャッシュ容量に相当する前半部分を前記キャッシュに格納すると決定し、前記依存関係解析手順によって解析された前記依存関係が逆方向である場合、前記現ループの処理済みデータのうちキャッシュ容量に相当する後半部分を前記キャッシュに格納すると決定することを特徴とする請求項１に記載のコンパイラプログラム。
【請求項３】
前記格納先決定手順は、前記第一ループの次に前記第二ループを実行する新規ソースプログラムを生成するように、前記新規ソースプログラム生成手順を指示することを特徴とする請求項２に記載のコンパイラプログラム。
【請求項４】
前記オブジェクトファイルを実行する情報処理装置のハードウェア情報を収集して、当該情報処理装置が逆方向ハードウェアプリフェッチ処理実行可能であるか否かを判定する判定手順をさらにコンピュータに実行させ、
前記格納先決定手順は、前記判定手順により前記情報処理装置が逆方向ハードウェアプリフェッチ処理実行可能であるとして判定された場合、前記第二ループにおけるデータの処理順番を、前記現ループにおける処理順番に対して逆にしたうえで前記新規ソースプログラムを生成し、前記判定手順により前記情報処理装置が逆方向ハードウェアプリフェッチ処理実行不可として判定された場合、前記第二ループにおけるデータの処理順番を、前記現ループにおける処理順番と同一にしたうえで前記新規ソースプログラムを生成するように、前記新規ソースプログラム生成手順を指示することを特徴とする請求項３に記載のコンパイラプログラム。
【請求項５】
ソースプログラムにおける各ループのデータへのアクセスパターンを解析するアクセスパターン解析部と、
前記アクセスパターン解析部によって解析された前記アクセスパターンから、現ループにおいて処理されるデータと次ループにおいて処理されるデータとの依存関係を解析する依存関係解析部と、
前記依存関係解析部によって解析された前記依存関係に基づいて、前記現ループにおいて処理されたデータの格納先をメモリまたはキャッシュのいずれかに割り振るように決定する格納先決定部と、
前記格納先決定部によって格納先が決定された現ループを、前記メモリに処理済みデータを格納するための第一ループおよび前記キャッシュに処理済みデータを格納するための第二ループに置き換えた新規ソースプログラムを生成する新規ソースプログラム生成部と、
前記新規ソースプログラム生成部によって生成された前記新規ソースプログラムからオブジェクトファイルを生成するオブジェクトファイル生成部と、
を有することを特徴とするコンパイラ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、コンパイラプログラムおよびコンパイラ装置に関する。
【背景技術】
【０００２】
従来より、グリッドコンピューティングや企業間で構築される業務システムでは、ソースプログラムからコンパイラによって生成されたアプリケーションプログラムが、様々なハードウェア構成のシステム上で動作することで科学演算や業務に利用されている。ここで、科学演算や業務に利用されるアプリケーションプログラムに対しては、高速に処理を実行することが要求される。
【０００３】
処理速度を向上させるための方法としては、一般的には、ＣＰＵ（Central  Processing  Unit）とメモリとの間に高速アクセスが可能である小容量のキャッシュを配置し、キャッシュに保存したデータを用いることが行なわれている。
【０００４】
しかし、近年、アプリケーションプログラムの処理対象となるデータは、例えば、動画配信などのストリームデータのように、キャッシュのサイズに収まらない大量のデータである場合が増えてきている。このため、キャッシュ上にデータが保存された場合でも、ＣＰＵのアクセス時にキャッシュヒットする確率は、非常に低い。
【０００５】
ここで、ＣＰＵが、プログラムにしたがって、ストリームデータを繰り返してアクセスする場合のキャッシュの状況について、図２６を用いて説明する。なお、図２６は、ストリームデータを繰り返してアクセスする場合のキャッシュの状況について説明するための図である。
【０００６】
例えば、ＣＰＵは、プログラムにしたがって、メモリからレジスタにストリームデータを順次読み出して所定の処理を実行し、処理後のストリームデータをキャッシュに格納したのちメモリにストアする。この場合、ＣＰＵは、図２６の（Ａ）に示すように、処理後のストリームデータ１をキャッシュに格納したのちにメモリにストアし、さらに、処理後のストリームデータ２〜ストリームデータｎを、順次、キャッシュに上書きしたのちにメモリにストアする。
【０００７】
しかし、ＣＰＵが、プログラムにしたがって、次の処理においてストリームデータのロードを実行する場合、キャッシュが保存しているデータは、図２６の（Ｂ）に示すように、前の処理における最終部分のデータ（ストリームデータｎ）となる。したがって、ＣＰＵが次の処理において最初にストリームデータ１のロードを実行する場合においては、図２６の（Ｂ）に示すように、キャッシュミスが発生する。
【０００８】
このように、ストリームデータなど、プログラムの処理対象となるデータサイズがキャッシュのサイズに収まらない場合では、データの再アクセス時に、キャッシュヒットが期待できず、キャッシュを用いたデータの再利用性が低くなり、プログラムの実行性能が低下してしまう。
【０００９】
このため、プログラムの実行性能を向上させる解決策の１つとして、プリフェッチ命令を利用した方法がある（例えば、特許文献１および２参照）。具体的には、処理に用いられるデータを先読みしてプリフェッチ命令をソースプログラム内に挿入することにより、処理に用いられるデータを予めメモリからキャッシュに格納してキャッシュミスを軽減させる方法である。
【００１０】
しかし、ストリームデータのように連続性のあるデータにおいては、再利用されるデータをプリフェッチ命令で精度よくキャッシュに取り込むのは難しい。このため、プログラムの実行性能を向上させる解決策の別の方法として、ブロックストア命令を用いた方法がある。
【００１１】
ブロックストア命令とは、図２７に示すように、キャッシュへの保存を行わず、データ（ストリームデータ１、ストリームデータ２、〜、ストリームデータｎ）を直接メモリに書き込むことで、転送時間を短縮し、プログラムの実行性能を向上させる方法である。ブロックストア命令を利用することで、プリフェッチ命令をプログラム内に挿入するといった複雑な計算を実行することなく、プログラムの実行性能を向上させることができる。なお、図２７は、ブロックストア命令を説明するための図である。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開平１０−２８３１９２号公報
【特許文献２】特開２００６−３３０８１３号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
ところで、上記した従来の技術は、キャッシュを有効的に利用することができないため、プログラムの実行性能が低下してしまう場合があるという課題があった。例えば、上記した従来の技術により、ストリームデータに対する全てのストア命令をブロックストア命令に置き換えた場合、ＣＰＵは、ロード命令の実行時にキャッシュが全く利用できなくなってしまい、その結果、ロードの実行性能が著しく低下する。特に、ストリームデータに対し、プログラムが繰り返して更新処理を実行する場合、ブロックストア命令を用いることでキャッシュを活用できないと、プログラムの実行性能が低下してしまう。
【００１４】
なお、上記では、ストリームデータが処理対象である場合に、キャッシュを有効的に利用することができないため、プログラムの実行性能が低下してしまう場合があるという課題があったことを説明した。しかし、キャッシュのサイズに収まらない大容量の連続したデータが処理対象であるならば、上記した従来の技術を用いても、同様の課題があった。
【００１５】
そこで、開示の技術は、上述した従来技術の課題を解決するためになされたものであり、キャッシュを有効的に利用することによりプログラムの実行性能を向上することが可能となるコンパイラプログラムおよびコンパイラ装置を提供することを目的とする。
【課題を解決するための手段】
【００１６】
上述した課題を解決し、目的を達成するため、このプログラムは、ソースプログラムにおける各ループのデータへのアクセスパターンを解析するアクセスパターン解析手順と、
前記アクセスパターン解析手順によって解析された前記アクセスパターンから、現ループにおいて処理されるデータと次ループにおいて処理されるデータとの依存関係を解析する依存関係解析手順と、前記依存関係解析手順によって解析された前記依存関係に基づいて、前記現ループにおいて処理されたデータの格納先をメモリまたはキャッシュのいずれかに割り振るように決定する格納先決定手順と、前記格納先決定手順によって格納先が決定された現ループを、前記メモリに処理済みデータを格納するための第一ループおよび前記キャッシュに処理済みデータを格納するための第二ループに置き換えることにより、前記ソースプログラムから新規ソースプログラムを生成する新規ソースプログラム生成手順と、前記新規ソースプログラム生成手順によって生成された前記新規ソースプログラムからオブジェクトファイルを生成するオブジェクトファイル生成手順と、をコンピュータに実行させることを要件とする。
【発明の効果】
【００１７】
開示のプログラムによれば、キャッシュを有効的に利用することによりプログラムの実行性能を向上することが可能となる。
【図面の簡単な説明】
【００１８】
【図１】図１は、本実施例におけるコンパイラ装置による処理の概念を説明するための図である。
【図２】図２は、本実施例におけるコンパイラ装置の構成を示すブロック図である。
【図３】図３は、ループ構造解析部を説明するための図である。
【図４】図４は、ループデータ記憶部を説明するための図である。
【図５】図５は、ループ構造解析部による処理を説明するためのフローチャートである。
【図６】図６は、ループの種類を説明するための図である。
【図７】図７は、配列解析部を説明するための図である。
【図８】図８は、配列解析部による処理後におけるループデータ記憶部および配列データ記憶部を説明するための図である。
【図９】図９は、配列解析部による処理を説明するためのフローチャートである。
【図１０】図１０は、アクセスパターン解析部を説明するための図である。
【図１１】図１１は、アクセスパターン解析部による処理後における配列データ記憶部を説明するための図である。
【図１２】図１２は、アクセスパターン解析部による処理を説明するためのフローチャートである。
【図１３】図１３は、依存関係解析部を説明するための図である。
【図１４】図１４は、依存関係解析部による処理後における配列データ記憶部を説明するための図である。
【図１５】図１５は、依存関係解析部による方向性の判断処理を説明するためのフローチャートである。
【図１６】図１６は、ハードウェア情報記憶部を説明するための図である。
【図１７】図１７は、部分キャッシュ指示部による処理を説明するためのフローチャートである。
【図１８】図１８は、パターン１〜４のループ変形指示の概要を説明するための図である。
【図１９】図１９は、パターン１のループ変形指示を説明するための図である。
【図２０】図２０は、パターン２のループ変形指示を説明するための図である。
【図２１】図２１は、パターン３のループ変形指示を説明するための図である。
【図２２】図２２は、パターン４のループ変形指示を説明するための図である。
【図２３】図２３は、本実施例におけるコンパイラ装置の処理を説明するためのフローチャートである。
【図２４】図２４は、部分キャッシュ指示部による処理の変形例を説明するためのフローチャートである。
【図２５】図２５は、本実施例のコンパイラプログラムを実行するコンピュータを示す図である。
【図２６】図２６は、ストリームデータを繰り返してアクセスする場合のキャッシュの状況について説明するための図である。
【図２７】図２７は、ブロックストア命令を説明するための図である。
【発明を実施するための形態】
【００１９】
以下に添付図面を参照して、本願の開示するコンパイラプログラムおよびコンパイラ装置の実施例を詳細に説明する。なお、以下では、本願の開示するコンパイラプログラムを実行するコンパイラ装置を実施例として説明する。
【実施例】
【００２０】
まず、本実施例におけるコンパイラ装置による処理の概念について説明する。図１は、本実施例におけるコンパイラ装置による処理の概念を説明するための図である。
【００２１】
本実施例におけるコンパイラ装置は、ソースプログラムに記述されているループ単位の処理の間で、「前のループ」がストアしたデータを「後のループ」がロードする場合はキャッシュが有効に活用できると判断する。そして、本実施例におけるコンパイラ装置は、「後のループ」にて実行される処理の先頭で要求されるデータ（ロードするデータ）については、「前のループ」にて実行される処理の最後にアクセスし、かつ、キャッシュにストアするように、「前のループ」を変形する。「前のループ」の変形処理を行なったソースプログラムを実行する場合、「後のループ」にて実行される処理の先頭にてロードされるデータは、キャッシュヒットとなる。
【００２２】
例えば、本実施例におけるコンパイラ装置は、図１の（Ａ）に示すように、「後のループ」の先頭にて処理されるストリームデータ１を「前のループ」の最後にて処理し、かつ、ストリームデータ１のみキャッシュに格納されるように「前のループ」を変形する。また、本実施例におけるコンパイラ装置は、例えば、図１の（Ａ）に示すように、「前のループ」にて処理されるストリームデータ１以外のストリームデータ２〜ｎについては、直接メモリに格納するブロックストア命令を利用するように「前のループ」を変形する。これにより、図１の（Ａ）に示すように、「後のループ」における処理の先頭にロードされるストリームデータ１は、キャッシュヒットとなる。
【００２３】
図１の（Ｂ）に示すソースプログラムの具体例を用いて上述した処理をより具体的に説明する。図１の（Ｂ）に示すようなソースプログラムを実行する場合、ループＸにおいて、配列ａ、配列ｂおよび配列ｃのデータが初期設定され、ループＹにおいて、配列ａのデータが確定され、ループＺにおいて、配列ａのデータが参照される。ここで、配列ａ、配列ｂおよび配列ｃのデータがキャッシュに収まらないストリームデータであるとすると、通常のストア命令によりキャッシュを利用した場合、配列ａのデータは、「ａ（ｎ−キャッシュサイズ）からａ（ｎ）」の範囲でキャッシュに保存される。しかし、次に実行されるループＺでは、配列ａをデータの先頭からロードするため、キャッシュのデータを利用することはできない。一方、ブロックストア命令を利用した場合、配列ａのデータは、キャッシュには保存されていないので、キャッシュを有効的に用いることができない。
【００２４】
そこで、本実施例におけるコンパイラ装置は、ソースプログラムにおける前後のループ間におけるデータのアクセスパターンの依存関係を解析し、例えば、図１の（Ｂ）に示すソースプログラムのループＺにおいて、ループＹにて処理された配列ａのデータが参照されると判定する。そして、本実施例におけるコンパイラ装置は、図１の（Ｂ）に示すように、ループＹとループＺとの間で、キャッシュを部分利用すると決定する。そして、本実施例におけるコンパイラ装置は、ループＹを、キャッシュストア命令が書き込まれたループと、ブロックストア命令が書き込まれたループとの２つのループに変形する。
【００２５】
そして、本実施例におけるコンパイラ装置は、ループ変形されたソースプログラムを最適化処理したのちにオブジェクトファイルを生成する。これにより、本実施例におけるコンパイラ装置から出力されたオブジェクトファイルを実行する情報処理装置においては、部分的ではあるがキャッシュを有効的に利用することにより、ストリームデータに対するアクセスが効率化され、プログラムの実行性能を向上することが可能となる。
【００２６】
次に、本実施例におけるコンパイラ装置の構成について、図２を用いて説明する。図２は、本実施例におけるコンパイラ装置の構成を示すブロック図である。
【００２７】
図２に示すように、本実施例におけるコンパイラ装置１０は、ソースプログラム入力部１１と、オブジェクトファイル出力部１２と、通信部１３と、入出力制御Ｉ／Ｆ部１４と、記憶部２０と、処理部３０とを有する。また、本実施例におけるコンパイラ装置１０は、図２に示すように、情報処理装置４０と接続される。
【００２８】
情報処理装置４０は、コンパイラ装置１０から出力されたオブジェクトファイルを実行するＰＣ（Personal computer）などの装置である。なお、本実施例では、コンパイラ装置１０と情報処理装置４０とが独立した装置である場合について説明するが、本実施例はこれに限定されるものではなく、コンパイラ装置１０が情報処理装置４０に組み込まれている場合であってもよい。
【００２９】
ソースプログラム入力部１１は、プログラマが作成したソースプログラムを受け付け、オブジェクトファイル出力部１２は、処理部３０により生成されたオブジェクトファイルを、情報処理装置４０に出力する。通信部１３は、情報処理装置４０から後述するハードウェア情報を受信する。
【００３０】
通信部１３は、情報処理装置４０から後述するハードウェア情報を受信する。
【００３１】
入出力制御Ｉ／Ｆ部１４は、ソースプログラム入力部１１、オブジェクトファイル出力部１２および通信部１３と、記憶部２０および処理部３０との間におけるデータ転送を制御する。
【００３２】
記憶部２０は、ソースプログラム入力部１１が受け付けたソースプログラムや後述する処理部３０による各種処理結果を記憶する。ここで、記憶部２０は、特に本実施例に密接に関連するものとして、図２に示すように、ソースプログラム記憶部２１と、ループデータ記憶部２２と、配列データ記憶部２３と、ハードウェア情報記憶部２４と、新規ソースプログラム記憶部２５とを有する。
【００３３】
ソースプログラム記憶部２１は、ソースプログラム入力部１１が受け付けたソースプログラムを記憶する。例えば、ソースプログラム記憶部２１は、図１の（Ｂ）に示すようなソースプログラムを記憶する。
【００３４】
なお、ループデータ記憶部２２と、配列データ記憶部２３と、ハードウェア情報記憶部２４と、新規ソースプログラム記憶部２５とについては、処理部３０を説明する際に、詳述する。
【００３５】
処理部３０は、入出力制御Ｉ／Ｆ部１４から転送されたソースプログラムがソースプログラム記憶部２１に格納された際に、各種処理を実行する。ここで、処理部３０は、特に本実施例に密接に関連するものとして、図２に示すように、ループ構造解析部３１と、配列解析部３２と、アクセスパターン解析部３３と、依存関係解析部３４と、部分キャッシュ指示部３５とを有する。さらに、処理部３０は、特に本実施例に密接に関連するものとして、図２に示すように、最適化部３６と、オブジェクトファイル生成部３７とを有する。なお、ループ構造解析部３１、配列解析部３２、アクセスパターン解析部３３、依存関係解析部３４および部分キャッシュ指示部３５は、ソースプログラムの解析処理を分散して実行する処理部である。
【００３６】
ループ構造解析部３１は、ソースプログラム記憶部２１が記憶するソースプログラムにおけるループ構造を解析する。具体的には、ループ構造解析部３１は、ソースプログラムにおけるＤＯループやＦＯＲループなどを抽出し、抽出したループ間の処理の大まかな流れを解析する。ここで、ループ構造解析部３１は、抽出したループが多重ループである場合、データ配列の演算が記載されているループの中で、最も内側にあるループ（最内のループ）を、後続する処理の対象であるループ（対象ループ）とする。なお、多重ループである場合の処理については、後に詳述する。
【００３７】
例えば、ループ構造解析部３１は、図１の（Ｂ）に示すソースプログラムを解析し、最内のループである「ループＸ（do j）」、「ループＹ（do j）」および「ループＺ（do j）」を抽出する。そして、ループ構造解析部３１は、図３に示すように、図１の（Ｂ）に示すソースプログラムが、「ループＸ」から「ループＹ」へ、「ループＹ」から「ループＺ」へと処理が進行するループ構造であると解析する。なお、図３は、ループ構造解析部を説明するための図である。
【００３８】
そして、ループ構造解析部３１は、解析結果に基づいて、ループデータ記憶部２２にて記憶されるループデータの初期設定を行なう。例えば、ループ構造解析部３１は、図４に示すように、「ループＸ」、「ループＹ」および「ループＺ」それぞれのループデータを初期設定する。なお、図４は、ループデータ記憶部を説明するための図である。
【００３９】
すなわち、ループ構造解析部３１は、ループデータ記憶部２２において、図４に示すように、「ループ名：Ｘ」、「ループ名：Ｙ」および「ループ名：Ｚ」となる３つのループデータを初期設定する。ここで、ループデータには、ループ構造解析部３１の解析結果として、ループ間処理の流れを示す「ｐｒｅｖ」および「ｎｅｘｔ」の項目が用意される。「ｐｒｅｖ」および「ｎｅｘｔ」の項目が設定されることにより、各ループデータには、ループ間の連鎖に関する情報が格納されることとなる。
【００４０】
例えば、「ループ名：Ｘ」のループデータには、「ループＸ」の前に実行されるループが無いことから「ｐｒｅｖ：ＮＵＬＬ」が格納される。また、「ループ名：Ｘ」のループデータには、「ループＸ」の後に実行されるループが「ループＹ」であることから「ｎｅｘｔ：＊Ｙ」が格納される。
【００４１】
また、「ループ名：Ｙ」のループデータには、「ｐｒｅｖ：＊Ｘ」および「ｎｅｘｔ：＊Ｚ」が格納され、「ループ名：Ｚ」のループデータには、「ｐｒｅｖ：＊Ｙ」および「ｎｅｘｔ：ＮＵＬＬ」が格納される。
【００４２】
なお、ループデータにおいて、図４に示す「配列データ」に格納されるデータは、後述する処理により決定されるため、ループ構造解析部３１による初期設定時では、すべて「ＮＵＬＬ」となる。
【００４３】
ここで、ループ構造解析部３１による詳細な処理の手順について、図５および図６を用いて説明する。なお、図５は、ループ構造解析部による処理を説明するためのフローチャートであり、図６は、ループの種類を説明するための図である。
【００４４】
図５に示すように、ループ構造解析部３１は、ソースプログラムが入力されると（ステップＳ１０１肯定）、ソースプログラム記憶部２１からソースプログラムを読み出して、関数内の外側ループを検索する（ステップＳ１０２）。すなわち、ループ構造解析部３１は、ソースプログラムにおいて、関数の直下のスコープにあるループをソースプログラムから検索する。
【００４５】
そして、ループ構造解析部３１は、検索した外側ループが多重ループであるか否かを解析する（ステップＳ１０３）。なお、ループ構造解析部３１は、ソースプログラムにおける出現順に、検索した外側ループを処理する。
【００４６】
ここで、検索した外側ループが多重ループでない場合（ステップＳ１０３否定）、ループ構造解析部３１は、検索したループ（外側ループ）を対象ループに含め（ステップＳ１０４）、ループデータの作成を実行する（ステップＳ１０７）。具体的には、ループ構造解析部３１は、対象ループのループ名が設定されたループデータを作成する。
【００４７】
一方、検索した外側ループが多重ループである場合（ステップＳ１０３肯定）、ループ構造解析部３１は、多重ループがタイトリループであるか否かを解析する（ステップＳ１０５）。
【００４８】
ここで、タイトリループ（タイトリなループ）とは、ループとループとの間で処理がないループのことである。例えば、図６の（Ａ）の左側に示す外側ループ「ループＸ」は、「Ａ＝Ａ＋Ｂ」を実行する「ループＹ」を含む多重ループであるが、「ループＸ」と「ループＹ」との間で実行される処理がないため、タイトリなループとなる。一方、図６の（Ａ）の右側に示す外側ループ「ループＸ」は、「Ａ＝Ａ＋Ｂ」を実行する「ループＹ」を含む多重ループであるが、「ループＸ」において「Ｃ＝Ｃ＋Ｄ」の処理が実行されるため、タイトリでないループとなる。
【００４９】
図５に戻って、ループ構造解析部３１は、検索した外側ループが多重ループであるが、タイトリループでない場合（ステップＳ１０５否定）、検索した外側ループを後続処理の対象外であるとし、検索した外側ループをすべて処理したか否かを判定する（ステップＳ１０８）。例えば、図６の（Ｂ）の右側に示す「ループＸ」は、対象外とされる。
【００５０】
一方、ループ構造解析部３１は、検索した外側ループが多重ループであり、タイトリループである場合（ステップＳ１０５肯定）、タイトリループの最内のループを対象ループに含め（ステップＳ１０６）、ループデータの作成を実行する（ステップＳ１０７）。そして、ループ構造解析部３１は、検索した外側ループをすべて処理したか否かを判定する（ステップＳ１０８）。
【００５１】
例えば、図６の（Ａ）の左側に示す外側「ループＸ」においては、「ループＹ」が対象ループとされる。また、タイトリループ内のループが兄弟ループである場合、対象ループが複数となる。例えば、図６の（Ｂ）の左側に示すように、同一階層にある「ループＡ」および「ループＢ」は、兄弟ループとなり、ループ構造解析部３１は、「ループＡ」および「ループＢ」を対象ループとする。一方、図６の（Ｂ）の右側に示すように、同一階層にない「ループＡ」および「ループＢ」は、兄弟ループではなく、ループ構造解析部３１は、「ループＢ」より内側にある「ループＡ」を対象ループとする。
【００５２】
図５に戻って、ループ構造解析部３１は、未処理の外側ループがある場合（ステップＳ１０８否定）、ステップＳ１０３に戻って、次の外側ループに対する処理を実行する。
【００５３】
一方、ループ構造解析部３１は、検索した外側ループをすべて処理した場合（ステップＳ１０８肯定）、処理を終了する。なお、ループ構造解析部３１は、対象ループのループ名が設定された順に応じて、ループデータの「ｐｒｅｖ」および「ｎｅｘｔ」に、前後にあるループのループ名を設定する。
【００５４】
図２に戻って、配列解析部３２は、ループ構造解析部３１による解析の結果、ループデータに設定された対象ループを再解析し、対象ループで利用されているデータの配列（以下、配列と記す）を列挙する。
【００５５】
例えば、配列解析部３２は、図１の（Ｂ）に示すソースプログラムを解析し、図７に示すように、「ループＸ」において利用されている配列が「配列ａ、配列ｂ、配列ｃ」の３つの配列であると列挙する。また、配列解析部３２は、図１の（Ｂ）に示すソースプログラムを解析し、図７に示すように、「ループＹ」において利用されている配列が「配列ａ、配列ｂ、配列ｃ」の３つの配列であると列挙する。また、配列解析部３２は、図１の（Ｂ）に示すソースプログラムを解析し、図７に示すように、「ループＺ」において利用されている配列が「配列ａ」の１つの配列であると列挙する。なお、図７は、配列解析部を説明するための図である。
【００５６】
そして、配列解析部３２は、解析結果を、ループデータ記憶部２２のループデータに設定するとともに、配列データ記憶部２３において配列データを初期設定する。
【００５７】
例えば、配列解析部３２は、図８に示すように、「ループ名：ループＸ」のループデータにおける項目「配列データ」に利用されている配列数が３つであることを示す「ａｒｒａｙ[３]」を設定する。同様に、配列解析部３２は、図８に示すように、「ループ名：ループＹ」のループデータにおける項目「配列データ」に「ａｒｒａｙ[３]」を設定し、「ループ名：ループＺ」のループデータにおける項目「配列データ」に「ａｒｒａｙ[１]」を設定する。なお、図８は、配列解析部による処理後におけるループデータ記憶部および配列データ記憶部を説明するための図である。
【００５８】
さらに、配列解析部３２は、図８に示すように、「ループ名：Ｘ」のループデータに連鎖して、「配列名」が『「ａ」、「ｂ」、「ｃ」』からなる配列データを初期設定する。同様に、配列解析部３２は、図８に示すように、「ループ名：Ｙ」のループデータに連鎖して、「配列名」が『「ａ」、「ｂ」、「ｃ」』からなる配列データを初期設定し、「ループ名：ループＺ」のループデータに連鎖して、「配列名」が「ａ」からなる配列データを初期設定する。
【００５９】
なお、図８に示すように、配列データには、「初期値」、「終値」および「増分値」からなる項目がある。「初期値」、「終値」および「増分値」の項目は、後述するアクセスパターン解析部３３の処理により設定されるため、配列解析部３２による配列データの初期設定時においては、すべて「ＮＵＬＬ」と設定される。
【００６０】
ここで、配列解析部３２による詳細な処理の手順について、図９を用いて説明する。なお、図９は、配列解析部による処理を説明するためのフローチャートである。
【００６１】
図９に示すように、配列解析部３２は、ループ構造解析部３１により対象ループが抽出されると（ステップＳ２０１肯定）、対象ループに記載されている配列名から配列データの設定処理を開始する（ステップＳ２０２）。すなわち、配列解析部３２は、抽出された対象ループごとに以下の処理を開始する。
【００６２】
そして、配列解析部３２は、配列の１次元目の添え字に利用されている変数名を抽出し（ステップＳ２０３）、抽出した変数名の変数が対象ループの制御変数であるか否かを判定する（ステップＳ２０４）。例えば、配列解析部３２は、図１の（Ｂ）に示すソースプログラムにおいて、対象ループである「ループＸ（do j）」において、「配列ａ」の制御変数に「変数名：j」が登場するか否かを判定する。
【００６３】
ここで、変数が対象ループの制御変数でない場合（ステップＳ２０４否定）、配列解析部３２は、対象ループをループデータの連鎖から削除する（ステップＳ２０６）。
【００６４】
一方、変数が対象ループの制御変数である場合（ステップＳ２０４肯定）、配列解析部３２は、ループデータと連鎖した配列データを設定する（ステップ２０５）。例えば、配列解析部３２は、図１の（Ｂ）に示すソースプログラムにおいて、対象ループである「ループＸ（do j）」において、「配列ａ〜ｃ」の制御変数に「変数名：j」が登場すると判定する。これにより、配列解析部３２は、「ループ名：ループＸ」のループデータに連鎖して、「配列名」が『「ａ」、「ｂ」、「ｃ」』からなる配列データを初期設定する。
【００６５】
ステップＳ２０５およびステップＳ２０６の処理ののち、配列解析部３２は、対象ループをすべて処理したか否かを判定する（ステップＳ２０７）。
【００６６】
未処理の対象ループがある場合（ステップＳ２０７否定）、配列解析部３２は、ステップＳ２０２に戻って、次の対象ループに対する処理を開始する。
【００６７】
一方、配列解析部３２は、対象ループをすべて処理した場合（ステップＳ２０７肯定）、処理を終了する。
【００６８】
図２に戻って、アクセスパターン解析部３３は、配列データが設定された対象ループの配列におけるデータのアクセスパターンを解析する。例えば、アクセスパターン解析部３３は、「配列名：ａ」の配列データが設定された図１の（Ｂ）に示すソースプログラムの「ループＸ（do j）」における「配列ａ」のアクセスパターンを解析する。
【００６９】
そして、アクセスパターン解析部３３は、図１０に示すように、「ループＸ」における「配列ａ」の制御変数「j」が「１」から「ｎ」に１ずつ増分して変化するパターンであると解析する。同様に、アクセスパターン解析部３３は、「ループＸ」における「配列ｂ、ｃ」と、「ループＹ」における「配列ａ、ｂ、ｃ」と、「ループＺ」における「配列ａ」との制御変数「j」それぞれが「１」から「ｎ」に１ずつ増分して変化するパターンであると解析する。なお、図１０は、アクセスパターン解析部を説明するための図である。
【００７０】
そして、アクセスパターン解析部３３は、図１１の（Ａ）に示すように、例えば、「ループ名：ループＸ」のループデータと連鎖して配列データ記憶部２３に格納されている配列データに、「初期値：１」、「終値：ｎ」および「増分値：１」を設定する。なお、図１１は、アクセスパターン解析部による処理後における配列データ記憶部を説明するための図である。
【００７１】
また、配列名が異なっていても領域が同じである場合に対処するために、アクセスパターン解析部３３は、配列データ記憶部２３において、配列データとは別に、アドレス変換テーブルを格納する。なお、アクセスパターン解析部３３は、領域を特定するためのメモリ上にアドレスを、ソースプログラムを解析することにより獲得する。これにより、アクセスパターン解析部３３は、例えば、図１１の（Ｂ）に示すように、「配列名：ａ」のアドレスが「0xaaaaaaa」であり、「配列名：ｂ」のアドレスが「0xbbbbbbb」であり、「配列名：ｃ」のアドレスが「0xcccccccc」であることを獲得する。そして、アクセスパターン解析部３３は、取得したアドレスを配列名に対応付けたアドレス変換テーブルとして配列データ記憶部２３に格納する。なお、アクセスパターン解析部３３は、アドレスが獲得されなかった場合、配列名に対応付けて「アドレス：ＮＵＬＬ」をアドレス変換テーブルに格納する。
【００７２】
なお、対象ループ内で同一配列に対するデータのアクセスパターンが複数存在する場合、アクセスパターン解析部３３は、同一配列名の配列データを、アクセスパターンごとに設定する。例えば、ループ内で「配列名：ａ」に対して、制御変数が「１」から「ｎ」に１ずつ増分して変化するパターン、制御変数が「ｎ」から「１」に１ずつ減少して変化するパターンおよび制御変数が「２」から「ｎ」に１ずつ増分して変化するパターンがあるとする。この場合、アクセスパターン解析部３３は、図１１の（Ｃ）に示すように、「配列名：ａ」において、「初期値：１、終値：ｎ、増分値：１」、「初期値：ｎ、終値：１、増分値：−１」および「初期値：２、終値：ｎ、増分値：１」の３つの配列データを設定する。
【００７３】
ここで、アクセスパターン解析部３３による詳細な処理の手順について、図１２を用いて説明する。なお、図１２は、アクセスパターン解析部による処理を説明するためのフローチャートである。
【００７４】
図１２に示すように、アクセスパターン解析部３３は、配列解析部３２により配列データが設定されると（ステップＳ３０１肯定）、配列データごとに処理を開始する。
【００７５】
まず、アクセスパターン解析部３３は、配列名からアドレスを獲得し、アドレス変換テーブルを配列データ記憶部２３に構築する（ステップＳ３０２）。
【００７６】
そして、アクセスパターン解析部３３は、配列ごとに制御変数の初期値、終値および増分値を取得し、配列データを更新する（ステップＳ３０３）。なお、対象ループ内で同一配列に対するデータのアクセスパターンが複数存在する場合、アクセスパターン解析部３３は、同一配列名の配列データを、アクセスパターンごとに設定して更新する。
【００７７】
そののち、アクセスパターン解析部３３は、配列解析部３２により設定された配列データをすべて更新処理したか否かを判定する（ステップＳ３０４）。
【００７８】
ここで、未処理の配列データがあった場合（ステップＳ３０４否定）、アクセスパターン解析部３３は、ステップＳ３０２に戻って、次の配列データに対する処理を開始する。
【００７９】
一方、配列データをすべて更新処理した場合（ステップＳ３０４肯定）、アクセスパターン解析部３３は、処理を終了する。
【００８０】
図２に戻って、依存関係解析部３４は、アクセスパターン解析部３３が解析した対象ループの配列におけるデータのアクセスパターンから、前後のループ間で処理される配列のデータにおける依存関係を解析する。例えば、アクセスパターン解析部３３は、図１の（Ｂ）に示すソースプログラムの「配列ａ」におけるループ間の依存関係を解析する。
【００８１】
すなわち、依存関係解析部３４は、図１３の（Ａ）に示すように、ループＸとループＹとの間において、ループＸにて１からｎの順に処理された「配列ａ」のデータが、ループＹにて１からｎの順に処理される依存関係であると解析する。また、依存関係解析部３４は、図１３の（Ａ）に示すように、ループＹとループＺとの間において、ループＹにて１からｎの順に処理された「配列ａ」のデータが、ループＺにて１からｎの順に処理される依存関係であると解析する。なお、図１３は、依存関係解析部を説明するための図である。
【００８２】
具体的には、依存関係解析部３４は、前後のループそれぞれにおいて設定されたループデータと、ループデータと連鎖している配列データと、アドレス変換テーブルとを参照して、同一配列のデータにおけるループ間の依存関係を解析する。
【００８３】
例えば、依存関係解析部３４は、図１３の（Ｂ）に示すように、「ループ名：Ｘ」および「ループ名：Ｙ」のループデータと、「ループ名：Ｘ」のループデータと連鎖する「配列名：ａ」の配列データおよび「ループ名：Ｙ」のループデータと連鎖する「配列名：ａ」の配列データと、アドレス変換テーブルとを読み出す。そして、依存関係解析部３４は、図１３の（Ｂ）に示すように、アドレス変換テーブルを参照してアドレスから配列の一致を判断したうえで、配列データを比較する。
【００８４】
この際、依存関係解析部３４は、各配列データの増分値を参照し、図１３の（Ｂ）に示すように、アクセス方向がそれぞれ増分する「＋」であると判断し、ループＸおよびループＹのアクセス方向が一致する順方向であると解析する。そして、依存関係解析部３４は、図１３の（Ｂ）に示すように、「ループ名：Ｘ」のループデータと連鎖した「配列ａ」の配列データに、新たに「次ループ：順方向」を設定する。
【００８５】
図１３の（Ｂ）を用いて説明した処理により、依存関係解析部３４は、ループＸ、ＹおよびＺのループデータと連鎖する「配列ａ」の配列データに新たに「次ループ」の項目を設定する。例えば、依存関係解析部３４は、図１４に示すように、ループＸのループデータと連鎖する「配列ａ」の配列データに「次ループ：順方向」を設定し、ループＹのループデータと連鎖する「配列ａ」の配列データに「次ループ：順方向」を設定する。また、依存関係解析部３４は、図１４に示すように、ループＺのループデータと連鎖する「配列ａ」の配列データに「次ループ：なし」を設定する。なお、図１４は、依存関係解析部による処理後における配列データ記憶部を説明するための図である。
【００８６】
なお、依存関係解析部３４は、複数のアクセスパターンがあるために同一配列に対して複数の配列データが存在する場合、アクセスパターンが同一のものを検索して比較することで、順方向または逆方向の方向性を決定する。初期値、終値および増分値に関しては、変数であったとしても、変数のアドレスで比較するために、同一性を確保できる。
【００８７】
ここで、依存関係解析部３４による詳細な方向性の判断処理の手順について、図１５を用いて説明する。なお、図１５は、依存関係解析部による方向性の判断処理を説明するためのフローチャートである。
【００８８】
図１５に示すように、依存関係解析部３４は、アクセスパターン解析部３３により、すべての配列データにおいて、初期値、終値および増分値が更新されると（ステップＳ４０１肯定）、カウンタにおける順方向および逆方向の値を初期化する（ステップＳ４０２）。この際、依存関係解析部３４は、処理対象とするループ（以下、自ループと記す）のループデータと連鎖する配列データを配列データ記憶部２３から抽出したうえで、カウンタにおける順方向および逆方向の値を初期化する。
【００８９】
そして、依存関係解析部３４は、自ループの次にあるループである次ループと連鎖する配列データに同一配列名があるか否かを判定する（ステップＳ４０３）。
【００９０】
ここで、次ループに同一配列名がある場合（ステップＳ４０３肯定）、依存関係解析部３４は、次ループにおける同一配列名の配列データのアクセス方向は、順方向であるか否かを判定する（ステップＳ４０４）。なお、ステップＳ４０４以降の処理は、同一配列名の配列データ一つずつに対して、順次実行される。
【００９１】
順方向であり（ステップＳ４０４肯定）、自ループの初期値と次ループの初期値とが同じであるならば（ステップＳ４０５肯定）、依存関係解析部３４は、順方向カウンタの値をインクリメントする（ステップＳ４０６）。
【００９２】
また、逆方向であり（ステップＳ４０４否定）、自ループの初期値と次ループの初期値とが同じであるならば（ステップＳ４０７肯定）、依存関係解析部３４は、逆方向カウンタの値をインクリメントする（ステップＳ４０８）。
【００９３】
ここで、「順方向であり（ステップＳ４０４肯定）、自ループの初期値と次ループの初期値とが異なる場合（ステップＳ４０５否定）」、依存関係解析部３４は、ステップＳ４０３に戻って、次ループに未処理の同一配列名の配列データがあるか否かを判定する。
【００９４】
また、依存関係解析部３４は、「逆方向であり（ステップＳ４０４否定）、自ループの初期値と次ループの初期値とが異なる場合（ステップＳ４０７否定）」も、ステップＳ４０３に戻って、次ループに未処理の同一配列名の配列データがあるか否かを判定する。
【００９５】
また、依存関係解析部３４は、「ステップＳ４０６の処理を終了した場合」および「ステップＳ４０８の処理を終了した場合も、ステップＳ４０３に戻って、次ループに未処理の同一配列名の配列データがあるか否かを判定する。
【００９６】
一方、次ループに未処理の同一配列名の配列データがない場合（ステップＳ４０３否定）、依存関係解析部３４は、順方向および逆方向のカウンタの値がともに「０」であるか否かを判定する（ステップＳ４０９）。
【００９７】
順方向および逆方向のカウンタの値がともに「０」である場合（ステップＳ４０９肯定）、依存関係解析部３４は、配列データにおける次ループの項目を「なし」として更新し（ステップＳ４１０）、処理を終了する。
【００９８】
また、順方向および逆方向のカウンタの値のいずれか一方が「０」でない場合（ステップＳ４０９否定）、順方向のカウンタの値が、逆方向の値以上であるか否かを判定する（ステップＳ４１１）。
【００９９】
ここで、順方向のカウンタの値が、逆方向の値以上である場合（ステップＳ４１１肯定）、依存関係解析部３４は、配列データにおける次ループの項目を「順方向」として更新し（ステップＳ４１２）、処理を終了する。
【０１００】
一方、順方向のカウンタの値が、逆方向の値未満である場合（ステップＳ４１１否定）、依存関係解析部３４は、配列データにおける次ループの項目を「逆方向」として更新し（ステップＳ４１３）、処理を終了する。
【０１０１】
図２に戻って、ハードウェア情報記憶部２４は、通信部１３が受信した情報処理装置４０のハードウェア情報を記憶する。ここで、ハードウェア情報は、コンパイラ装置１０の起動時、初期化処理の延長で、通信部１３が、情報処理装置４０のＯＳに問い合わせることで、ハードウェア情報記憶部２４に格納される。
【０１０２】
例えば、ハードウェア情報記憶部２４は、図１６に示すように、情報処理装置４０に搭載されているキャッシュの容量（キャッシュサイズ）が「ｃａｓｈｅ」とするハードウェア情報を記憶する。なお、図１６は、ハードウェア情報記憶部を説明するための図である。
【０１０３】
また、ハードウェア情報記憶部２４は、図１６に示すように、情報処理装置４０のＣＰＵが逆方向ハードウェアプリフェッチを実行可能であるか不可能であるかの情報として「可」または「不可」とするハードウェア情報を記憶する。なお、逆方向ハードウェアプリフェッチとは、ハードウェアプリフェッチにおいて、アドレスを減算する方向でデータアクセスが可能である機能のことである。
【０１０４】
図２に戻って、部分キャッシュ指示部３５は、依存関係解析部３４による依存関係の解析結果から、自ループにおいて処理されたデータの格納先をメモリまたはキャッシュのいずれかに割り振るように決定する。すなわち、部分キャッシュ指示部３５は、依存関係の解析結果から、キャッシュサイズを考慮したアクセスパターンにループを変形するように後述する最適化部３６に指示する。具体的には、部分キャッシュ指示部３５は、次ループの方向性と、キャッシュサイズと、逆方向ハードウェアプリフェッチ機能の有無から変形する形を決定する。
【０１０５】
ここで、部分キャッシュ指示部３５について、図１７〜図２２を用いて詳細に説明する。なお、図１７は、部分キャッシュ指示部による処理を説明するためのフローチャートであり、図１８は、パターン１〜４のループ変形指示の概要を説明するための図である。また、図１９は、パターン１のループ変形指示を説明するための図であり、図２０は、パターン２のループ変形指示を説明するための図である。また、図２１は、パターン３のループ変形指示を説明するための図であり、図２２は、パターン４のループ変形指示を説明するための図である。
【０１０６】
図１７に示すように、部分キャッシュ指示部３５は、配列データの依存関係（項目：次ループ）が更新されると（ステップＳ５０１肯定）、処理対象となる配列データにて更新された次ループの方向性が順方向であるか否かを判定する（ステップＳ５０２）。
【０１０７】
次ループの方向性が順方向である場合（ステップＳ５０２肯定）、部分キャッシュ指示部３５は、ハードウェア情報を参照して、情報処理装置４０が逆方向ハードウェアプリフェッチ処理可であるか否かを判定する（ステップＳ５０３）。
【０１０８】
逆方向ハードウェアプリフェッチ処理可である場合（ステップＳ５０３肯定）、部分キャッシュ指示部３５は、パターン１のループ変形処理を最適化部３６に指示して（ステップＳ５０４）、処理を終了する。
【０１０９】
また、逆方向ハードウェアプリフェッチ処理不可である場合（ステップＳ５０３否定）、部分キャッシュ指示部３５は、パターン２のループ変形処理を最適化部３６に指示して（ステップＳ５０５）、処理を終了する。
【０１１０】
一方、次ループの方向性が逆方向である場合（ステップＳ５０２否定）、部分キャッシュ指示部３５は、ハードウェア情報を参照して、情報処理装置４０が逆方向ハードウェアプリフェッチ処理可であるか否かを判定する（ステップＳ５０６）。
【０１１１】
逆方向ハードウェアプリフェッチ処理可である場合（ステップＳ５０６肯定）、部分キャッシュ指示部３５は、パターン３のループ変形処理を最適化部３６に指示して（ステップＳ５０７）、処理を終了する。
【０１１２】
また、逆方向ハードウェアプリフェッチ処理不可である場合（ステップＳ５０６否定）、部分キャッシュ指示部３５は、パターン４のループ変形処理を最適化部３６に指示して（ステップＳ５０８）、処理を終了する。
【０１１３】
パターン１〜４のループ変形指示の概要について、図１８を用いて説明する。なお、図１８において、「Ａ」は、変形するループの初期値であり、「Ｂ」は、変形するループの初期値にキャッシュサイズ（ｃａｓｈｅ）分の値を加算した値である。また、図１８において、「Ｃ」は、変形するループの終値からキャッシュサイズ（ｃａｓｈｅ）分の値を減算した値であり、「Ｄ」は、変形するループの終値である。なお、図１８では、変形されるループにて作成される「キャッシュ利用を実行する新たなループ」を「別ループ」として記載してある。
【０１１４】
次ループが順方向であり、逆方向ハードウェアプリフェッチ可である場合に実行されるパターン１のループ変形指示においては、図１８に示すように、別ループの作成位置が「先頭」とされる。具体的には、パターン１のループ変形指示においては、変形されるループにて処理されるデータのキャッシュサイズに対応する前半部分がキャッシュ利用のループにより処理されるように指示される。また、パターン１のループ変形指示においては、別ループの初期値が「Ｂ」、別ループの終値が「Ａ」とされ、逆方向ハードウェアプリフェッチ機能を有することから、別ループの制御変数の回転の方向性が「逆方向」となる。
【０１１５】
パターン１のループ変形指示の具体例を、図１９を用いて説明する。入力されたソースプログラムが図１９の（Ａ）の左側に示すように記述されていた場合、後ループにて処理される配列ａの方向性は、前ループと順方向である。ここで、配列ａのデータサイズがキャッシュサイズに収まらない場合、図１９の（Ｂ）の左側に示すように、前ループの処理のあとキャッシュの最後尾にあるデータの制御変数は、「ｅｊ」である。すなわち、後ループの処理の先頭において処理される制御変数「ｓｊ」のデータは、キャッシュから落ちており、キャッシュミスが発生する。したがって、従来では、キャッシュ不用として、ブロックストア命令を用いていた。
【０１１６】
そこで、パターン１のループ変形指示では、図１９の（Ａ）の右側に示すように、前ループの先頭（前半部分）においてキャッシュサイズに相当するデータをキャッシュ利用とし、かつ、制御変数を１つずつ減算（−１）とする新ループを作成する。また、キャッシュサイズに相当する前半部分以外の後半部分のデータに関しては、前ループにおいて、ブロックストア命令とする。
【０１１７】
また、部分キャッシュ指示部３５は、ブロックストアのループがキャッシュ利用の新ループの前に実行されるように指示する。
【０１１８】
これにより、図１９の（Ｂ）の右側に示すように、プログラム実行時においては、最初に、前ループにてキャッシュサイズに相当する前半部分以外の後半部分のデータが処理されて、キャッシュ不使用のブロックストアで、メモリに直接格納される。そして、次に、逆方向回転の新ループにてキャッシュサイズに相当する前半部分のデータが処理されてキャッシュに格納される。これにより、前ループによって処理された初期値のデータがキャッシュの最後に格納され、後ループにおいて確実にキャッシュヒットとなる。また、キャッシュ不使用のデータに関しては、メモリに直接アクセスすることでデータをロードすることができるので、処理が高速化される。
【０１１９】
図１８に戻って、次ループが順方向であり、逆方向ハードウェアプリフェッチ不可である場合に実行されるパターン２のループ変形指示においては、パターン１と同様に、別ループの作成位置が「先頭」とされる。すなわち、パターン２のループ変形指示においても、パターン１と同様に、変形されるループにて処理されるデータのキャッシュサイズに対応する前半部分がキャッシュ利用のループにより処理されるように指示される。また、パターン２のループ変形指示においては、別ループの初期値が「Ａ」、別ループの終値が「Ｂ」とされ、逆方向ハードウェアプリフェッチ機能がないことから、別ループの制御変数の回転の方向性が「順方向」となる。
【０１２０】
パターン２のループ変形指示の具体例を、図２０を用いて説明する。なお、図２０の（Ａ）の左側に示すソースプログラムは、図１９の（Ａ）の左側に示すソースプログラムと同じであるので、説明を省略する。また、図２０の（Ｂ）の左側では、図２０の（Ａ）の左側に示すソースプログラムを実行した場合、キャッシュを利用すると後ループにてキャッシュミスが発生することを示しているが、図１９の（Ｂ）の左側を用いて説明した内容と同じであるので、説明を省略する。
【０１２１】
そこで、パターン１と逆方向ハードウェアプリフェッチ機能がない点が異なるパターン２のループ変形指示では、図２０の（Ａ）の右側に示すように、前ループの先頭（前半部分）においてキャッシュサイズに相当するデータをキャッシュ利用とし、かつ、制御変数を１つずつ増分する新ループを作成する。また、キャッシュサイズに相当する前半部分以外の後半部分のデータに関しては、前ループにおいて、ブロックストア命令とする。
【０１２２】
また、パターン１と同様に、部分キャッシュ指示部３５は、ブロックストアのループがキャッシュ利用の新ループの前に実行されるように指示する。
【０１２３】
これにより、図２０の（Ｂ）の右側に示すように、プログラム実行時においては、最初に、前ループにてキャッシュサイズに相当する前半部分以外の後半部分のデータが処理されて、キャッシュ不使用のブロックストアで、メモリに直接格納される。そして、次に、順方向回転の新ループにてキャッシュサイズに相当する前半部分のデータが処理されてキャッシュに格納される。これにより、前ループによって処理された初期値のデータがキャッシュにて最初に格納されたとしても、キャッシュから落ちることが防止され、後ループにおいて確実にキャッシュヒットとなる。また、キャッシュ不使用のデータに関しては、メモリに直接アクセスすることでデータをロードすることができるので、処理が高速化される。
【０１２４】
図１８に戻って、次ループが逆方向であり、逆方向ハードウェアプリフェッチ可である場合に実行されるパターン３のループ変形指示においては、別ループの作成位置が「最終」とされる。具体的には、パターン１のループ変形指示においては、変形されるループにて処理されるデータのキャッシュサイズに対応する後半部分がキャッシュ利用のループにより処理されるように指示される。また、パターン３のループ変形指示においては、別ループの初期値が「Ｄ」、別ループの終値が「Ｃ」とされ、逆方向ハードウェアプリフェッチ機能を有することから、別ループの制御変数の回転の方向性が「逆方向」となる。
【０１２５】
パターン３のループ変形指示の具体例を、図２１を用いて説明する。入力されたソースプログラムが図２１の（Ａ）の左側に示すように記述されていた場合、後ループにて処理される配列ａの方向性は、前ループと逆方向である。ここで、配列ａのデータサイズがキャッシュサイズに収まらない場合、図２１の（Ｂ）の左側に示すように、前ループの処理のあとキャッシュの最後尾にあるデータの制御変数は、「ｅｊ」である。すなわち、後ループの処理の先頭において処理される制御変数「ｅｊ」のデータは、キャッシュヒットとなるが、前ループにて処理されるデータのキャッシュサイズに対応する後半部分以外のデータに関しては、キャッシュヒットが期待できない。従来では、キャッシュ不用として、ブロックストア命令を用いていた。
【０１２６】
そこで、パターン３のループ変形指示では、図２１の（Ａ）の右側に示すように、前ループの最終（後半部分）においてキャッシュサイズに相当するデータをキャッシュ利用とし、かつ、制御変数を１つずつ減算（−１）とする新ループを作成する。また、キャッシュサイズに相当する後半部分以外の前半部分のデータに関しては、前ループにおいて、ブロックストア命令とする。
【０１２７】
また、部分キャッシュ指示部３５は、パターン１および２と同様に、ブロックストアのループがキャッシュ利用の新ループの前に実行されるように指示する。
【０１２８】
これにより、図２１の（Ｂ）の右側に示すように、プログラム実行時においては、最初に、前ループにてキャッシュサイズに相当する後半部分以外の前半部分のデータが処理されて、キャッシュ不使用のブロックストアで、メモリに直接格納される。そして、次に、逆方向回転の新ループにてキャッシュサイズに相当する後半部分のデータが処理されてキャッシュに格納される。これにより、前ループによって処理された終値のデータがキャッシュの最後に格納され、後ループにおいて確実にキャッシュヒットとなる。また、キャッシュ不使用のデータに関しては、メモリに直接アクセスすることでデータをロードすることができるので、処理が高速化される。
【０１２９】
図１８に戻って、次ループが逆方向であり、逆方向ハードウェアプリフェッチ不可である場合に実行されるパターン４のループ変形指示においては、パターン３と同様に、別ループの作成位置が「最終」とされる。すなわち、パターン４のループ変形指示においても、パターン３と同様に、変形されるループにて処理されるデータのキャッシュサイズに対応する後半部分がキャッシュ利用のループにより処理されるように指示される。また、パターン４のループ変形指示においては、別ループの初期値が「Ｃ」、別ループの終値が「Ｄ」とされ、逆方向ハードウェアプリフェッチ機能がないことから、別ループの制御変数の回転の方向性が「順方向」となる。
【０１３０】
パターン４のループ変形指示の具体例を、図２２を用いて説明する。なお、図２２の（Ａ）の左側に示すソースプログラムは、図２１の（Ａ）の左側に示すソースプログラムと同じであるので、説明を省略する。また、図２２の（Ｂ）の左側では、図２１の（Ｂ）の左側で説明したように、図２２の（Ａ）の左側に示すソースプログラムを実行した場合、キャッシュを利用すると後ループにてキャッシュヒットするものの、前ループにて処理されるデータのキャッシュサイズに対応する後半部分以外のデータに関しては、キャッシュヒットが期待できないことを示している。
【０１３１】
そこで、パターン３と逆方向ハードウェアプリフェッチ機能がない点が異なるパターン４のループ変形指示では、図２２の（Ａ）の右側に示すように、前ループの最終（後半部分）においてキャッシュサイズに相当するデータをキャッシュ利用とし、かつ、制御変数を１つずつ増分する新ループを作成する。また、キャッシュサイズに相当する後半部分以外の前半部分のデータに関しては、前ループにおいて、ブロックストア命令とする。
【０１３２】
また、パターン１〜３と同様に、部分キャッシュ指示部３５は、ブロックストアのループがキャッシュ利用の新ループの前に実行されるように指示する。
【０１３３】
これにより、図２２の（Ｂ）の右側に示すように、プログラム実行時においては、最初に、前ループにてキャッシュサイズに相当する後半部分以外の前半部分のデータが処理されて、キャッシュ不使用のブロックストアで、メモリに直接格納される。そして、次に、順方向回転の新ループにてキャッシュサイズに相当する後半部分のデータが処理されてキャッシュに格納される。これにより、前ループによって処理された終値のデータがキャッシュにて最初に格納されたとしても、キャッシュから落ちることが防止され、後ループにおいて確実にキャッシュヒットとなる。また、キャッシュ不使用のデータに関しては、メモリに直接アクセスすることでデータをロードすることができるので、処理が高速化される。
【０１３４】
図２に戻って、最適化部３６は、部分キャッシュ指示部３５によるループ変形指示にしたがって、ソースプログラムに新ループを挿入したソースプログラムを生成する。そして、最適化部３６は、新ループを挿入したソースプログラムに対して、ソフトウェアプリフェッチなどの従来の最適化処理を実行することで、新規ソースプログラムを生成し、生成した新規ソースプログラムを新規ソースプログラム記憶部２５に格納する。
【０１３５】
オブジェクトファイル生成部３７は、新規ソースプログラム記憶部２５が記憶する新規ソースプログラムからオブジェクトファイルを生成し、生成したオブジェクトファイルを、オブジェクトファイル出力部１２に対して出力する。
【０１３６】
続いて、本実施例におけるコンパイル装置１０の処理の流れについて、図２３を用いて説明する。なお、図２３は、本実施例におけるコンパイラ装置の処理を説明するためのフローチャートである。
【０１３７】
図２３に示すように、本実施例におけるコンパイラ装置１０は、ソースプログラム入力部１１からソースプログラムが入力されると（ステップＳ６０１肯定）、ループ構造解析部３１は、対象ループを抽出し、ループデータを設定する（ステップＳ６０２）。なお、コンパイラ装置１０は、自装置の起動時などに、情報処理装置４０から、ハードウェア情報を獲得する。
【０１３８】
そして、配列解析部３２は、対象ループを解析して、対象ループで利用されているデータの配列を列挙することで、ループデータと連鎖する配列データを設定する（ステップＳ６０３）。
【０１３９】
そののち、アクセスパターン解析部３３は、設定された配列データの配列名に基づいて、アドレス変換テーブルの構築と、配列データの初期値、終値および増分値の更新を行なう（ステップＳ６０４）。
【０１４０】
さらに、依存関係解析部３４は、設定されたループデータと、ループデータと連鎖している配列データと、アドレス変換テーブルとを参照して、ループ間の同一配列名を有する配列データの依存関係（次ループの項目）を更新する（ステップＳ６０５）。
【０１４１】
そして、部分キャッシュ指示部３５は、配列データの依存関係と、キャッシュサイズと、逆方向ハードウェアプリフェッチ機能とに応じてループ変形指示を行なう（ステップＳ６０６）。
【０１４２】
そののち、最適化部３６は、ループ変形指示にしたがって、新ループをソースプログラムに挿入して最適化処理を行なって、新規ソースプログラムを生成する（ステップＳ６０７）。
【０１４３】
さらに、オブジェクトファイル生成部３７は、新規ソースプログラムからオブジェクトファイルを生成し（ステップＳ６０８）、処理を終了する。
【０１４４】
上述してきたように、本実施例によれば、ループ構造解析部３１、配列解析部３２およびアクセスパターン解析部３３は、ソースプログラムの各ループの前後関係、各ループにて利用される配列およびデータのアクセスパターンを解析し、依存関係解析部３４は、アクセスパターンから、前のループにおいて処理されるデータと次ループにおいて処理されるデータとの依存関係を解析する。そして、部分キャッシュ指示部３５は、依存関係に基づいて、前のループにおいて処理されたデータの格納先をメモリまたはキャッシュのいずれかに割り振るように決定し、最適化部３６は、格納先が決定された前のループを、キャッシュ利用のループおよびブロックストア命令のループに置き換えた新規ソースプログラムを生成し、オブジェクトファイル生成部３７は、新規ソースプログラムからオブジェクトファイルを生成する。
【０１４５】
したがって、プログラム実行時において、キャッシュを利用すべきデータと、メモリに直接格納したほうがよいデータとを同一ループ内で分割することができ、キャッシュを有効的に利用することによりプログラムの実行性能を向上することが可能となる。
【０１４６】
また、本実施例では、依存関係解析部３４は、依存関係として、前ループにおいて処理されるデータの順番と、前ループの処理済みデータが次ループにおいて処理される順番とが順方向であるか逆方向であるかを解析し、部分キャッシュ指示部３５は、依存関係が順方向である場合、前ループの処理済みデータのうちキャッシュ容量に相当する前半部分をキャッシュ利用として決定し、依存関係が逆方向である場合、前ループの処理済みデータのうちキャッシュ容量に相当する後半部分をキャッシュ利用として決定する。
【０１４７】
したがって、プログラム実行時において、キャッシュに格納されたデータが次ループにおいて確実にキャッシュヒットとなり、プログラムの実行性能をより向上することが可能となる。
【０１４８】
また、本実施例では、部分キャッシュ指示部３５は、ブロックストアのループの次に、キャッシュのループを入れるように最適化部３６を指示するので、キャッシュに格納されたデータが次ループにおいてより確実にキャッシュヒットとなり、プログラムの実行性能をより向上することが可能となる。
【０１４９】
また、本実施例では、部分キャッシュ指示部３５は、逆方向ハードウェアプリフェッチ処理実行可能ならば、キャッシュ利用のループにおけるデータの処理順番を逆にするように指示する。また、部分キャッシュ指示部３５は、逆方向ハードウェアプリフェッチ処理実行不可ならば、キャッシュ利用のループにおけるデータの処理順番を同一とするように指示する。
【０１５０】
したがって、プログラムを実行する装置の機能に応じて、キャッシュに格納されたデータが次ループにおいて確実にキャッシュヒットとなるキャッシュ利用のループを作成することができ、プログラムの実行性能を適切に向上することが可能となる。
【０１５１】
なお、上記では、ループ変形指示が、配列データの依存関係と、キャッシュサイズと、逆方向ハードウェアプリフェッチ機能と応じてキャッシュ利用の新ループにおける回転の方向性を順方向または逆方向に設定する場合について説明した。しかし、本実施例はこれに限定されるものではなく、例えば、動画などのストリームデータのように、処理する順番が順方向となることが望ましいならば、異なる基準にてループ変形指示が実行される場合であってもよい。これについて、図２４を用いて説明する。なお、図２４は、部分キャッシュ指示部による処理の変形例を説明するためのフローチャートである。
【０１５２】
図２４に示すように、変形例における部分キャッシュ指示部３５は、配列データの依存関係が更新されると（ステップＳ７０１肯定）、配列データのデータが、順次アクセスのパターンを保証する必要があるか否かを判定する（ステップＳ７０２）。
【０１５３】
ここで、順次アクセスのパターンを保証する必要がない場合（ステップＳ７０２否定）、部分キャッシュ指示部３５は、図１７を用いて説明したステップＳ５０２以降の処理を実行し、処理を終了する。
【０１５４】
一方、順次アクセスのパターンを保証する必要がある場合（ステップＳ７０２肯定）、部分キャッシュ指示部３５は、変形指示を行なう対象ループにおいて、キャッシュ利用のループの初期値、終値および増分値の設定を行なう（ステップＳ７０４）。すなわち、部分キャッシュ指示部３５は、順次アクセスのパターンを保証するように、キャッシュ利用のループの初期値、終値および増分値の設定を行なう。
【０１５５】
そして、部分キャッシュ指示部３５は、ループインデックス計算の補正を行い（ステップＳ７０５）、対象ループから新規で作成したキャッシュ利用のループ分の回転を除外する（ステップＳ７０６）。
【０１５６】
そののち、部分キャッシュ指示部３５は、キャッシュ利用のループにて処理されるデータ以外のデータを処理する対象ループのストアをブロックストアに変更し（ステップＳ７０７）、処理を終了する。
【０１５７】
これにより、再利用されるストリームデータにおいて、順次アクセスのパターンを保証する必要がある場合であっても、キャッシュを有効利用して、プログラムの実行処理を向上することが可能となる。
【０１５８】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的に行なうこともできる（例えば、ハードウェア情報を、プログラマが手動で入力するなど）。あるいは、本実施例において説明した各処理のうち、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０１５９】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、ループ構造解析部３１、配列解析部３２、アクセスパターン解析部３３および依存関係解析部３４を統合して、ソースプログラム解析部としてもよい。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１６０】
ところで上記の実施例では、ハードウェアロジックによって各種の処理を実現する場合を説明したが、本発明はこれに限定されるものではなく、あらかじめ用意されたプログラムをコンピュータで実行するようにしてもよい。そこで以下では、図２５を用いて、上記の実施例に示したコンパイラ装置１０と同様の機能を有するコンパイラプログラムを実行するコンピュータの一例を説明する。図２５は、本実施例のコンパイラプログラムを実行するコンピュータを示す図である。
【０１６１】
図２５に示すように、情報処理装置としてのコンピュータ１００は、キーボード１０１、ディスプレイ１０２、ＣＰＵ１０３、ＲＯＭ１０４、ＨＤＤ１０５、ＲＡＭ１０６を有する。そして、キーボード１０１、ディスプレイ１０２、ＣＰＵ１０３、ＲＯＭ１０４、ＨＤＤ１０５およびＲＡＭ１０６は、バス１０７などで接続される。また、コンピュータ１００は、情報処理装置４０と接続される。
【０１６２】
ＲＯＭ１０４には、上記の実施例に示したコンパイラ装置１０と同様の機能を発揮するコンパイラプログラム、つまり、図２５に示すように、ループ構造解析プログラム１０４ａ、配列解析プログラム１０４ｂが予め記憶されている。また、ＲＯＭ１０４には、アクセスパターン解析プログラム１０４ｃ、依存関係解析プログラム１０４ｄ、部分キャッシュ指示プログラム１０４ｅが予め記憶されている。また、ＲＯＭ１０４には、最適化プログラム１０４ｆ、オブジェクトファイル生成プログラム１０４ｇが予め記憶されている。なお、これらのプログラム１０４ａ〜１０４ｇについては、図２に示したコンパイラ装置１０の各構成要素と同様、適宜統合または分散してもよい。
【０１６３】
そして、ＣＰＵ１０３が、これらのプログラム１０４ａ〜１０４ｇをＲＯＭ１０４から読み出して実行する。これにより、図２５に示すように、プログラム１０４ａおよびプログラム１０４ｂは、ループ構造解析プロセス１０３ａおよび配列解析プロセス１０３ｂとして機能するようになる。また、プログラム１０４ｃ〜１０４ｅは、アクセスパターン解析プロセス１０３ｃ、依存関係解析プロセス１０３ｄ、部分キャッシュ指示プロセス１０３ｅとして機能するようになる。また、プログラム１０４ｆおよびプログラム１０４ｇは、最適化プロセス１０３ｆおよびオブジェクトファイル生成プロセス１０３ｇとして機能するようになる。なお、各プロセス１０３ａ〜１０３ｇは、図２に示した、ループ構造解析部３１、配列解析部３２、アクセスパターン解析部３３、依存関係解析部３４、部分キャッシュ指示部３５、最適化部３６、オブジェクトファイル生成部３７にそれぞれ対応する。
【０１６４】
また、ＨＤＤ１０５には、図２５に示すように、ソースプログラムデータ１０５ａ、ループデータ１０５ｂ、配列データ１０５ｃ、ハードウェア情報データ１０５ｄ、新規ソースプログラムデータ１０５ｅが設けられる。各データ１０５ａ〜１０５ｅは、図２に用いたソースプログラム記憶部２１、ループデータ記憶部２２、配列データ記憶部２３、ハードウェア情報記憶部２４、新規ソースプログラム記憶部２５にそれぞれ対応する。そしてＣＰＵ１０３は、ソースプログラムデータ１０６ａをソースプログラムデータ１０５ａに対して登録し、ループデータ１０６ｂをループデータ１０５ｂに対して登録し、配列データ１０６ｃを配列データ１０５ｃに対して登録する。また、ＣＰＵ１０３は、ハードウェア情報データ１０６ｄをハードウェア情報データ１０５ｄに対して登録し、新規ソースプログラムデータ１０６ｅを新規ソースプログラムデータ１０５ｅに対して登録する。そして、ＣＰＵ１０３は、登録したデータを読み出してＲＡＭ１０６に格納し、ＲＡＭ１０６に格納されたソースプログラムデータ１０６ａ、ループデータ１０６ｂ、配列データ１０６ｃ、ハードウェア情報データ１０６ｄおよび新規ソースプログラムデータ１０６ｅに基づいてコンパイル処理を実行する。
【０１６５】
なお、上記した各プログラム１０４ａ〜１０４ｇについては、必ずしも最初からＲＯＭ１０４に記憶させておく必要はなく、例えばコンピュータ１００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＭＯディスク、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」、または、コンピュータ１００の内外に備えられるＨＤＤなどの「固定用物理媒体」、さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ１００に接続される「他のコンピュータ（またはサーバ）」などに各プログラムを記憶させておき、コンピュータ１００がこれらから各プログラムを読み出して実行するようにしてもよい。
【０１６６】
以上の各実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１６７】
（付記１）ソースプログラムにおける各ループのデータへのアクセスパターンを解析するアクセスパターン解析手順と、
前記アクセスパターン解析手順によって解析された前記アクセスパターンから、現ループにおいて処理されるデータと次ループにおいて処理されるデータとの依存関係を解析する依存関係解析手順と、
前記依存関係解析手順によって解析された前記依存関係に基づいて、前記現ループにおいて処理されたデータの格納先をメモリまたはキャッシュのいずれかに割り振るように決定する格納先決定手順と、
前記格納先決定手順によって格納先が決定された現ループを、前記メモリに処理済みデータを格納するための第一ループおよび前記キャッシュに処理済みデータを格納するための第二ループに置き換えることにより、前記ソースプログラムから新規ソースプログラムを生成する新規ソースプログラム生成手順と、
前記新規ソースプログラム生成手順によって生成された前記新規ソースプログラムからオブジェクトファイルを生成するオブジェクトファイル生成手順と、
をコンピュータに実行させることを特徴とするコンパイラプログラム。
【０１６８】
（付記２）前記依存関係解析手順は、前記依存関係として、前記現ループにおいて処理されるデータの順番と、当該現ループの処理済みデータが前記次ループにおいて処理される順番とが順方向であるか逆方向であるかを解析し、
前記格納先決定手順は、前記依存関係解析手順によって解析された前記依存関係が順方向である場合、前記現ループの処理済みデータのうちキャッシュ容量に相当する前半部分を前記キャッシュに格納すると決定し、前記依存関係解析手順によって解析された前記依存関係が逆方向である場合、前記現ループの処理済みデータのうちキャッシュ容量に相当する後半部分を前記キャッシュに格納すると決定することを特徴とする付記１に記載のコンパイラプログラム。
【０１６９】
（付記３）前記格納先決定手順は、前記第一ループの次に前記第二ループを実行する新規ソースプログラムを生成するように、前記新規ソースプログラム生成手順を指示することを特徴とする付記２に記載のコンパイラプログラム。
【０１７０】
（付記４）前記オブジェクトファイルを実行する情報処理装置のハードウェア情報を収集して、当該情報処理装置が逆方向ハードウェアプリフェッチ処理実行可能であるか否かを判定する判定手順をさらにコンピュータに実行させ、
前記格納先決定手順は、前記判定手順により前記情報処理装置が逆方向ハードウェアプリフェッチ処理実行可能であるとして判定された場合、前記第二のループにおけるデータの処理順番を、前記現ループにおける処理順番に対して逆にしたうえで前記新規ソースプログラムを生成し、前記判定手順により前記情報処理装置が逆方向ハードウェアプリフェッチ処理実行不可として判定された場合、前記第二のループにおけるデータの処理順番を、前記現ループにおける処理順番と同一にしたうえで前記新規ソースプログラムを生成するように、前記新規ソースプログラム生成手順を指示することを特徴とする付記３に記載のコンパイラプログラム。
【０１７１】
（付記５）ソースプログラムにおける各ループのデータへのアクセスパターンを解析するアクセスパターン解析部と、
前記アクセスパターン解析部によって解析された前記アクセスパターンから、現ループにおいて処理されるデータと次ループにおいて処理されるデータとの依存関係を解析する依存関係解析部と、
前記依存関係解析部によって解析された前記依存関係に基づいて、前記現ループにおいて処理されたデータの格納先をメモリまたはキャッシュのいずれかに割り振るように決定する格納先決定部と、
前記格納先決定部によって格納先が決定された現ループを、前記メモリに処理済みデータを格納するための第一ループおよび前記キャッシュに処理済みデータを格納するための第二ループに置き換えた新規ソースプログラムを生成する新規ソースプログラム生成部と、
前記新規ソースプログラム生成部によって生成された前記新規ソースプログラムからオブジェクトファイルを生成するオブジェクトファイル生成部と、
を有することを特徴とするコンパイラ装置。
【０１７２】
（付記６）前記依存関係解析部は、前記依存関係として、前記現ループにおいて処理されるデータの順番と、当該現ループの処理済みデータが前記次ループにおいて処理される順番とが順方向であるか逆方向であるかを解析し、
前記格納先決定部は、前記依存関係解析部によって解析された前記依存関係が順方向である場合、前記現ループの処理済みデータのうちキャッシュ容量に相当する前半部分を前記キャッシュに格納すると決定し、前記依存関係解析部によって解析された前記依存関係が逆方向である場合、前記現ループの処理済みデータのうちキャッシュ容量に相当する後半部分を前記キャッシュに格納すると決定することを特徴とする付記５に記載のコンパイラ装置。
【０１７３】
（付記７）前記格納先決定部は、前記第一ループの次に前記第二ループを実行する新規ソースプログラムを生成するように、前記新規ソースプログラム生成部を指示することを特徴とする付記６に記載のコンパイラ装置。
【０１７４】
（付記８）前記オブジェクトファイルを実行する情報処理装置のハードウェア情報を収集して、当該情報処理装置が逆方向ハードウェアプリフェッチ処理実行可能であるか否かを判定する判定部をさらに有し、
前記格納先決定部は、前記判定部により前記情報処理装置が逆方向ハードウェアプリフェッチ処理実行可能であるとして判定された場合、前記第二ループにおけるデータの処理順番を、前記現ループにおける処理順番に対して逆にしたうえで前記新規ソースプログラムを生成し、前記判定部により前記情報処理装置が逆方向ハードウェアプリフェッチ処理実行不可として判定された場合、前記第二ループにおけるデータの処理順番を、前記現ループにおける処理順番と同一にしたうえで前記新規ソースプログラムを生成するように、前記新規ソースプログラム生成部を指示することを特徴とする付記７に記載のコンパイラ装置。
【符号の説明】
【０１７５】
１０  コンパイラ装置
１１  ソースプログラム入力部
１２  オブジェクトファイル出力部
１３  通信部
１４  入出力制御Ｉ／Ｆ部
２０  記憶部
２１  ソースプログラム記憶部
２２  ループデータ記憶部
２３  配列データ記憶部
２４  ハードウェア情報記憶部
２５  新規ソースプログラム記憶部
３０  処理部
３１  ループ構造解析部
３２  配列解析部
３３  アクセスパターン解析部
３４  依存関係解析部
３５  部分キャッシュ指示部
３６  最適化部
３７  オブジェクトファイル生成部
４０  情報処理装置
【図１】
2010244204.tif 000003
【図２】
2010244204.tif 000004
【図３】
2010244204.tif 000005
【図４】
2010244204.tif 000006
【図５】
2010244204.tif 000007
【図６】
2010244204.tif 000008
【図７】
2010244204.tif 000009
【図８】
2010244204.tif 000010
【図９】
2010244204.tif 000011
【図１０】
2010244204.tif 000012
【図１１】
2010244204.tif 000013
【図１２】
2010244204.tif 000014
【図１３】
2010244204.tif 000015
【図１４】
2010244204.tif 000016
【図１５】
2010244204.tif 000017
【図１６】
2010244204.tif 000018
【図１７】
2010244204.tif 000019
【図１８】
2010244204.tif 000020
【図１９】
2010244204.tif 000021
【図２０】
2010244204.tif 000022
【図２１】
2010244204.tif 000023
【図２２】
2010244204.tif 000024
【図２３】
2010244204.tif 000025
【図２４】
2010244204.tif 000026
【図２５】
2010244204.tif 000027
【図２６】
2010244204.tif 000028
【図２７】
2010244204.tif 000029