(57)【要約】【課題】ループ内の配列参照についてループ前に検査できる事項を増やす。【解決手段】記憶部１１は、インデックスによって参照される配列とループ変数とパラメータとを用いて記述されたループ処理を含むソースコード１３を記憶する。演算部１２は、ループ変数およびパラメータを用いて、配列のインデックスが所定の条件を満たすことを示す条件式１５を生成する。演算部１２は、数式処理によって条件式１５からループ変数を消去することで、パラメータについての判定情報１６を生成し、判定情報１６に応じてソースコード１３に対応するオブジェクトコード１４を生成する。【選択図】図１
2015094960.tif 000002
【特許請求の範囲】
【請求項１】
インデックスによって参照される配列とループ変数と前記ループ変数以外のパラメータとを用いて記述されたループ処理を含むソースコードを記憶する記憶部と、
前記ループ変数および前記パラメータを用いて前記配列のインデックスが所定の条件を満たすことを示す条件式を生成し、数式処理によって前記条件式から前記ループ変数を消去することで前記パラメータについての判定情報を生成し、前記判定情報に応じて前記ソースコードに対応するオブジェクトコードを生成する演算部、
を有する情報処理装置。
【請求項２】
前記判定情報は、前記条件式が成立するときの前記パラメータの値の範囲を示し、
前記演算部は、実行時の前記パラメータの値が前記範囲に属するか検査する検査コードを、前記オブジェクトコードにおける前記ループ処理の前に挿入する、
請求項１記載の情報処理装置。
【請求項３】
前記演算部は、前記ループ処理に対して前記判定情報に加えて他の条件式に対応する他の判定情報を生成した場合、前記判定情報が示す判定式と前記他の判定情報が示す判定式とを合成し、合成した判定式に基づいて前記検査コードを生成する、
請求項２記載の情報処理装置。
【請求項４】
前記判定情報が、前記パラメータの値にかかわらず前記条件式が成立することまたは成立しないことを示している場合、前記演算部は警告情報を生成する、
請求項１乃至３の何れか一項に記載の情報処理装置。
【請求項５】
前記条件式には、前記ループ変数の値の制限を示す複数の第１の線形式と前記配列のインデックスが前記所定の条件を満たすことを示す第２の線形式とが含まれる、
請求項１乃至４の何れか一項に記載の情報処理装置。
【請求項６】
前記所定の条件には、前記インデックスの値が定義域に収まっているか否かおよび前記配列の参照を並列化可能か否かの少なくとも一方についての条件が含まれる、
請求項１乃至５の何れか一項に記載の情報処理装置。
【請求項７】
コンピュータが実行するコンパイル方法において、
前記コンピュータが、
インデックスによって参照される配列とループ変数と前記ループ変数以外のパラメータとを用いて記述されたループ処理を含むソースコードを取得し、
前記ループ変数および前記パラメータを用いて、前記配列のインデックスが所定の条件を満たすことを示す条件式を生成し、
数式処理によって前記条件式から前記ループ変数を消去することで、前記パラメータについての判定情報を生成し、
前記判定情報に応じて前記ソースコードに対応するオブジェクトコードを生成する、
コンパイル方法。
【請求項８】
コンピュータが実行するコンパイラプログラムにおいて、
前記コンピュータに、
インデックスによって参照される配列とループ変数と前記ループ変数以外のパラメータとを用いて記述されたループ処理を含むソースコードを取得させ、
前記ループ変数および前記パラメータを用いて、前記配列のインデックスが所定の条件を満たすことを示す条件式を生成させ、
数式処理によって前記条件式から前記ループ変数を消去することで、前記パラメータについての判定情報を生成させ、
前記判定情報に応じて前記ソースコードに対応するオブジェクトコードを生成させる、
コンパイラプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報処理装置、コンパイル方法およびコンパイラプログラムに関する。
【背景技術】
【０００２】
コンピュータソフトウェアを開発する場合、開発者はプログラミング言語としてＣ言語などの高級言語を使用することが多い。高級言語を用いて記述されたソースコードは、コンパイラによって、プロセッサが実行可能なオブジェクトコードに変換することができる。コンパイラは、ソースコードの文法的な誤りを検査するだけでなく、メモリアクセス違反などの不適切な動作につながる意味的な誤りを検査する機能を有していることがある。
【０００３】
意味的な誤りは、配列の参照に関連して生じることがある。配列は複数のデータ要素を格納できるデータ構造であり、配列全体は１つの変数（配列変数）によって特定され、配列の中の各データ要素はインデックス（添字）によって特定される。配列は、複数のデータ要素に対して同様の演算を行うループ処理の中で使われることがある。配列の参照に関連した意味的な誤りの例として、宣言された範囲を超えたインデックスの値を用いて配列を参照することで、不適切なメモリ領域にアクセスすることが挙げられる。また、他の例として、あるインデックスの値を指定してデータ要素を格納する処理と、同じインデックスの値を指定してデータ要素を取得する処理とを並列化したとき、両者の処理の順序が調整されないために意図した処理結果が得られないことが挙げられる。
【０００４】
コンパイラは、ある配列の参照が不適切な動作を生じさせることがソースコードから明らかである場合、エラーメッセージを表示することがあり、オブジェクトコードを生成せずにコンパイルを停止することもある（コンパイル時の静的検査）。一方、コンパイラは、配列の参照が実行時に決まるパラメータの値に依存している場合など、不適切な動作を生じさせるとコンパイル時に断定できない場合、オブジェクトコードに検査コードを埋め込むことがある。検査コードは、不適切な動作が発生する前に（例えば、宣言された範囲を超えたインデックスの値を用いて配列を参照する前に）、実行時のパラメータの値などに基づいて、処理を進めてよいか検査する（実行時の動的検査）。
【０００５】
一例として、インデックスの不正使用の検査方法が提案されている。この検査方法では、コンパイラは、ループの繰り返し回数を制御するためのループ変数Ｉが初期値Ｍから終了値Ｎまで変化し、ループ内においてインデックスＩ×４−３を用いて配列Ａを参照しているソースコードを取得する。初期値Ｍおよび終了値Ｎは、実行時にその値が決まるパラメータである。すると、コンパイラは、ループ変数Ｉ＝初期値Ｍのときのインデックスの値とループ変数Ｉ＝終了値Ｎのときのインデックスの値とが、宣言された範囲に収まっているか検査するサブルーチンを生成する。そして、コンパイラは、ループ直前にこのサブルーチンが呼び出されるようなオブジェクトコードを生成する。
【０００６】
また、一例として、コンパイラによる最適化方法が提案されている。この最適化方法では、コンパイラは、２つの処理が独立しているか（一方の処理が他方の処理の結果を利用していないか）確認し、独立していることが確認できた場合は２つの処理を並列化することを試みる。独立性の確認において、コンパイラは、配列Ｘとループ変数Ｊと定数ａ１，ａ２，ｂ１，ｂ２を用いて記述されたループを検出する。このループ内において、インデックスａ１×Ｊ＋ｂ１を用いた配列Ｘの参照とインデックスａ２×Ｊ＋ｂ２を用いた配列Ｘの参照とが近接しているとする。すると、コンパイラは、任意のループ変数Ｊについて（ａ１−ａ２）×Ｊ＋（ｂ１−ｂ２）＝０となることがあるか計算することで、上記の２つのインデックスが同じデータ要素を指す可能性を検査する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平２−１４８３３０号公報
【特許文献２】特開平５−１９７５６３号公報
【非特許文献】
【０００８】
【非特許文献１】Alexander Schrijver, "Theory of Linear and Integer Programming", John Wiley & Sons, pp.155-157, 1998年6月4日
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、特許文献１，２に記載の方法は、ループ変数の初期値と終了値がそれぞれ定数または１つのパラメータによって表現され、配列のインデックスが１つのループ変数の一次式として表現された比較的単純な配列参照を検査対象としている。多重ループにより複数のループ変数が現れる場合やループ変数の変動範囲の定義が複雑な場合など、比較的複雑な配列参照については、特許文献１，２に記載の方法を適用することは難しい。すなわち、インデックスの不正使用や並列化可能性などの検査を任意のループに対して行えるわけではなく、ループ処理の実行前に検証できる事項が限定され得るという問題がある。
【００１０】
１つの側面では、本発明は、ループ内の配列参照についてループ前に検査できる事項を増やすことができる情報処理装置、コンパイル方法およびコンパイラプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１１】
１つの態様では、記憶部と演算部とを有する情報処理装置が提供される。記憶部は、インデックスによって参照される配列とループ変数とループ変数以外のパラメータとを用いて記述されたループ処理を含むソースコードを記憶する。演算部は、ループ変数およびパラメータを用いて配列のインデックスが所定の条件を満たすことを示す条件式を生成する。演算部は、数式処理によって条件式からループ変数を消去することでパラメータについての判定情報を生成する。演算部は、判定情報に応じてソースコードに対応するオブジェクトコードを生成する。
【００１２】
また、１つの態様では、コンピュータが実行するコンパイル方法が提供される。また、１つの態様では、コンピュータが実行するコンパイラプログラムが提供される。
【発明の効果】
【００１３】
１つの側面では、ループ内の配列参照についてループ前に検査できる事項が増える。
【図面の簡単な説明】
【００１４】
【図１】第１の実施の形態の情報処理装置を示す図である。
【図２】情報処理装置のハードウェア例を示すブロック図である。
【図３】実行時のインデックス検査の例を示す図である。
【図４】インデックス検査のための判定式の算出方法の例を示す図である。
【図５】実行時の並列化検査の例を示す図である。
【図６】並列化検査のための判定式の算出方法の例を示す図である。
【図７】判定式の最適化の例を示す図である。
【図８】情報処理装置で動作するソフトウェア例を示すブロック図である。
【図９】コンパイルの手順例を示すフローチャートである。
【図１０】インデックス分析の手順例を示すフローチャートである。
【図１１】並列化分析の手順例を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の情報処理装置を示す図である。
【００１６】
第１の実施の形態の情報処理装置１０は、ソースコード１３をコンパイルしてオブジェクトコード１４を生成する。情報処理装置１０は、ユーザが操作する端末装置であってもよいし、端末装置からネットワーク経由でアクセスされるサーバ装置であってもよい。情報処理装置１０は、「コンピュータ」と呼ばれてもよい。
【００１７】
情報処理装置１０は、記憶部１１および演算部１２を有する。記憶部１１は、ＲＡＭ（Random Access Memory）などの揮発性の記憶装置でもよいし、ＨＤＤ（Hard Disk Drive）などの不揮発性の記憶装置でもよい。演算部１２は、例えば、プロセッサである。プロセッサは、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）であってもよく、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの集積回路を含んでもよい。プロセッサは、例えば、ＲＡＭに記憶されたプログラムを実行する。後述するコンパイル処理を実現するためのプログラムを、コンパイラプログラムと呼んでもよい。また、「プロセッサ」は、２以上のプロセッサの集合（マルチプロセッサ）であってもよい。
【００１８】
記憶部１１は、ソースコード１３を記憶する。ソースコード１３は、ユーザから情報処理装置１０に入力されたものでもよいし、情報処理装置１０が他の情報処理装置から受信したものでもよい。ソースコード１３には、ループ処理のコードが含まれる。
【００１９】
このループ処理は、インデックスによって参照される配列Ａとループ変数ｉとパラメータＭとを用いて記述されている。配列Ａの参照は、配列Ａへのデータ要素の格納と配列Ａからのデータ要素の取得の何れでもよい。配列Ａのデータ要素数は、ソースコード１３において配列Ａを定義するときに宣言されている。ループ変数ｉは、ループ処理の繰り返し回数を制御するための変数である。ループ処理が入れ子になっている場合、複数のループ変数が使用されることもある。パラメータＭは、その値が静的（コンパイル時）には決まらず動的（実行時）に決まる変数である。パラメータＭの値は、ループ処理の直前までには算出されており、ループ処理中は変化しない。配列Ａのインデックスは、例えば、定数でなく、２ｉ＋Ｍのようにループ変数の線形式として表される。パラメータＭは、ループ変数の値の範囲およびインデックスの少なくとも一方を表すために用いられ得る。
【００２０】
演算部１２は、記憶部１１からソースコード１３を取得し、オブジェクトコード１４を生成する。このとき、演算部１２は、ループ変数ｉおよびパラメータＭを用いて、配列Ａのインデックスが所定の条件を満たすことを示す条件式１５を生成する。条件式１５には、例えば、ループ変数の変動範囲（ループ変数の値の制限）を示す１または２以上の第１の式と、所定の条件についての第２の式とが含まれる。第１の式は、パラメータＭを含んでもよく、ループ変数ｉについての線形不等式であってもよい。第２の式は、ループ変数ｉについての線形等式または線形不等式であってもよい。
【００２１】
所定の条件は、例えば、配列Ａのインデックスの値が定義域に収まっていること、または、定義域に収まっていないことである。インデックスの定義域は、配列Ａの定義時に確保されたメモリ領域の内を指すインデックスの値の範囲である。定義域に収まっていないインデックスの値は、配列Ａ用のメモリ領域の外を指すことを意味し、不正なメモリアクセスを引き起こす。また、所定の条件は、例えば、異なるループ変数ｉの値（ｉ＝ｉ０とｉ＝ｉ１）に対応する処理を並列化可能であること、または、並列化不可であることである。ｉ＝ｉ０のときに用いるインデックスの値とｉ＝ｉ１のときに用いるインデックスの値とが同じになる可能性があり、ｉ＝ｉ０のときの配列Ａの参照とｉ＝ｉ１のときの配列Ａの参照の少なくとも一方がデータ要素の格納である場合、並列化不可となる。
【００２２】
条件式１５が生成されると、演算部１２は、数式処理によって条件式１５からループ変数を消去することで、パラメータＭについての判定情報１６を生成する。判定情報１６は、条件式１５が成立するときのパラメータＭの値の範囲を示すことがある。実行時に決まるパラメータＭの値がこの範囲に属していれば、配列Ａのインデックスが所定の条件を満たすことになる。ただし、パラメータＭの値に依存せず条件式１５が常に成立するまたは常に成立しない場合、判定情報１６は、パラメータＭの値の範囲を示さないこともある。
【００２３】
数式処理として、「射影」と呼ばれる操作を用いることができる。射影は、高次元の情報を低次元の情報へと変換する操作である。射影では、ループ変数およびパラメータを含むｎ個の変数の関係をｎ次元空間に表現し、ある変数に対応する軸方向から光を当ててｎ−１次元空間に影を映し出すことで、ある変数を消去することができる。射影を実現するアルゴリズムの一例として、フーリエ・モツキン（Fourier-Motzkin）の消去法が挙げられる。例えば、非特許文献１（Alexander Schrijver, "Theory of Linear and Integer Programming", John Wiley & Sons, pp.155-157, 1998年6月4日）に、そのアルゴリズムが記載されている。
【００２４】
判定情報１６が生成されると、演算部１２は、判定情報１６に応じて、ソースコード１３に対応するオブジェクトコード１４を生成する。例えば、判定情報１６がパラメータＭの値の範囲を示している場合、演算部１２は、実行時のパラメータＭの値がその範囲に属するか検査する検査コード１４ａを生成し、オブジェクトコード１４におけるループ処理の前（例えば、ループ処理の直前）に挿入する。これにより、ループ処理において不適切な動作が発生する前に、オブジェクトコード１４の実行を停止するなどエラー処理を行うことが可能となる。また、例えば、判定情報１６が、条件式１５が常に成立する（または常に成立しない）ことを示している場合、演算部１２は、コンパイルエラーを示す警告情報を出力する。このとき、オブジェクトコード１４は生成しなくてもよい。
【００２５】
第１の実施の形態の情報処理装置１０によれば、ループ内における配列Ａの参照が所定の条件を満たすことが、ループ変数ｉと実行時にその値が決まるパラメータＭとを用いて条件式１５として表現される。そして、射影などの数式処理を用いて、条件式１５からループ変数ｉが消去されて、パラメータＭについての判定情報１６が生成される。この判定情報１６に基づいて、例えば、ループ処理の前にパラメータＭの値を検査するオブジェクトコード１４が生成される。これにより、ループ変数ｉの変動範囲や配列Ａのインデックスなどのループ定義が複雑であっても、数式処理を用いてパラメータＭの条件を算出することができ、ループ処理の前に検査できる事項を増やすことができる。
【００２６】
［第２の実施の形態］
第２の実施の形態の情報処理装置は、コンパイラおよびリンカを用いて、Ｃ言語などの高級言語で記述されたソースコードから実行コードを生成する。
【００２７】
図２は、情報処理装置のハードウェア例を示すブロック図である。
情報処理装置１００は、ＣＰＵ１０１，１０２、ＲＡＭ１０３、ＨＤＤ１０４、画像信号処理部１０５、入力信号処理部１０６、媒体リーダ１０７および通信インタフェース１０８を有する。これらのハードウェアユニットは、情報処理装置１００内でバスに接続されている。ＣＰＵ１０１，１０２は、第１の実施の形態の演算部１２の一例であり、ＲＡＭ１０３またはＨＤＤ１０４は、第１の実施の形態の記憶部１１の一例である。
【００２８】
ＣＰＵ１０１，１０２は、プログラムの命令を実行する１または２以上のコアを含むプロセッサである。例えば、ＣＰＵ１０１は、コア１０１ａ，１０１ｂを含む。同一または異なるＣＰＵに属する複数のコアは、互いに並列に命令を実行できる。ＣＰＵ１０１，１０２は、ＨＤＤ１０４に記憶されているプログラムやデータの少なくとも一部をＲＡＭ１０３にロードし、プログラムを実行する。なお、各コアを「プロセッサ」と呼んでもよいし、複数のプロセッサの集合を「プロセッサ」（マルチプロセッサ）と呼んでもよい。
【００２９】
ＲＡＭ１０３は、ＣＰＵ１０１，１０２が実行するプログラムやＣＰＵ１０１，１０２が演算に用いるデータを一時的に記憶する揮発性メモリである。なお、情報処理装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えてもよい。
【００３０】
ＨＤＤ１０４は、ＯＳ（Operating System）やアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性の記憶装置である。なお、情報処理装置１００は、フラッシュメモリやＳＳＤ（Solid State Drive）などの他の種類の記憶装置を備えてもよく、複数の不揮発性の記憶装置を備えてもよい。
【００３１】
画像信号処理部１０５は、ＣＰＵ１０１，１０２からの命令に従って、情報処理装置１００に接続されたディスプレイ２１に画像を出力する。ディスプレイ２１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、プラズマディスプレイ（ＰＤＰ：Plasma Display Panel）、有機ＥＬ（ＯＥＬ：Organic Electro-Luminescence）ディスプレイなどを用いることができる。
【００３２】
入力信号処理部１０６は、情報処理装置１００に接続された入力デバイス２２から入力信号を取得し、少なくとも１つのＣＰＵに出力する。入力デバイス２２としては、マウスやタッチパネルやタッチパッドやトラックボールなどのポインティングデバイス、キーボード、リモートコントローラ、ボタンスイッチなどを用いることができる。また、情報処理装置１００に、複数の種類の入力デバイスが接続されていてもよい。
【００３３】
媒体リーダ１０７は、記録媒体２３に記録されたプログラムやデータを読み取る読み取り装置である。記録媒体２３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）、半導体メモリなどを使用できる。媒体リーダ１０７は、例えば、記録媒体２３から読み取ったプログラムやデータをＲＡＭ１０３またはＨＤＤ１０４に格納する。
【００３４】
通信インタフェース１０８は、ネットワーク２４に接続され、ネットワーク２４を介して他の情報処理装置と通信を行うインタフェースである。通信インタフェース１０８は、スイッチなどの通信装置とケーブルで接続される有線通信インタフェースでもよいし、基地局と無線リンクで接続される無線通信インタフェースでもよい。
【００３５】
なお、情報処理装置１００が備えるＣＰＵの数は１個であってもよい。また、情報処理装置１００は、媒体リーダ１０７を備えていなくてもよい。また、情報処理装置１００は、ユーザが操作する端末装置からネットワーク２４経由で制御される場合には、画像信号処理部１０５や入力信号処理部１０６を備えていなくてもよい。また、情報処理装置１００は、通信インタフェース１０８を備えていなくてもよい。また、ディスプレイ２１や入力デバイス２２が、情報処理装置１００の筐体と一体に形成されていてもよい。
【００３６】
次に、第２の実施の形態のコンパイラの検査機能について説明する。
図３は、実行時のインデックス検査の例を示す図である。
ここでは、情報処理装置１００が次のようなソースコードをコンパイルする場合を考える。このソースコードには、データ要素数が１００の配列Ａと、ループ前にその値が動的に決定されループ内でその値が変わらないパラメータＭと、ループ変数ｉ，ｊとが定義されている。配列Ａのインデックスの正常範囲は０〜９９である。
【００３７】
ループは二重構造（入れ子）になっており、外側ループの繰り返し回数を制御するためにループ変数ｉが使用され、内側ループの繰り返し回数を制御するためにループ変数ｊが使用される。外側ループについて、ループ変数ｉの初期値は定数０であり、ループ変数ｉの終了値は定数３であり、ループ変数ｉの増加幅は定数１である。内側ループについて、ループ変数ｊの初期値はｉであり、ループ変数ｊの終了値は−ｉ＋７とｉ＋３の何れか小さい方であり、ループ変数ｊの増加幅は定数１である。すなわち、内側ループのループ変数ｊの初期値と終了値は、外側ループのループ変数ｉの値に依存している。内側ループの中では、インデックスｉ−２ｊ＋Ｍが指す配列Ａのデータ要素が更新される。すなわち、配列Ａの参照は、ループ変数ｉ，ｊとパラメータＭに依存している。
【００３８】
このループ処理を実行したときにメモリアクセス違反が発生しないためには、インデックスｉ−２ｊ＋Ｍの値が０〜９９の範囲に収まっていることを要する。一方、パラメータＭの値は実行時に決まるため、メモリアクセス違反が発生するか否かをコンパイル時に静的に検査することは難しい。そこで、情報処理装置１００は、メモリアクセス違反が発生するか否かを実行時に動的に検査する検査コードを、実行コードに挿入する。
【００３９】
第１の検査方法として、内側ループにおいて配列Ａが参照される直前に、ｉ−２ｊ＋Ｍの値が１００以上であるかまたは−１以下であるという判定式を用いて、インデックスを検査する方法が考えられる。この判定式が満たされる場合、配列Ａの参照によりメモリアクセス違反が生じるため、プログラムを強制終了するなどのエラー処理を行うようにする。ただし、第１の検査方法では、ループの繰り返し回数だけ検査コードが実行されるため、ループ処理のオーバヘッドが大きくなりプログラムの実行効率が低下しやすい。
【００４０】
第２の検査方法として、外側ループが開始される直前に、パラメータＭの値が１００以上であるかまたは７以下であるという判定式を用いて、インデックスを検査する方法が考えられる。この判定式は、ループ変数ｉ，ｊの値が変動したときにインデックスｉ−２ｊ＋Ｍの値が０〜９９の範囲を超えるようなパラメータＭの条件を示している。この判定式が満たされる場合、プログラムを強制終了するなどのエラー処理を行うようにする。この判定式にはループ変数ｉ，ｊが含まれていないため、インデックスｉ−２ｊ＋Ｍの値が０〜９９の範囲を超えるか否か、外側ループが開始される前に検査することができる。すなわち、第２の検査方法では、第１の検査方法と比べて検査コードの実行回数を削減でき、ループ処理のオーバヘッドが小さくなりプログラムの実行効率の低下を抑制できる。情報処理装置１００は、第２の検査方法に基づく実行コードを生成することとする。
【００４１】
なお、図３の検査コードでは、インデックスｉ−２ｊ＋Ｍの値が０〜９９の範囲を超えることを示す判定式を使用し、判定式が満たされる場合にエラー処理を行うこととしている。
【００４２】
図４は、インデックス検査のための判定式の算出方法の例を示す図である。
上記の図３で説明したパラメータＭの判定式（パラメータＭの値が１００以上であるかまたは７以下である）は、図４に示すような条件式から数式処理によって導出することができる。条件式は、ループ変数ｉ，ｊの変動範囲を制限するループ変数条件と、インデックスｉ−２ｊ＋Ｍの値がメモリアクセス違反を生じさせることを示すエラー条件を含む。
【００４３】
ループ変数条件は、ソースコードに記述されたループ定義に基づいて、次のように定義される。ループ変数ｉの値は定数０以上かつ定数３以下である。ループ変数ｊの値は、ループ変数ｉの値以上である。ループ変数ｊの値は、−ｉ＋７の値以下かつｉ＋３の値以下である。このループ変数ｉ，ｊの変動範囲は、ループ変数ｉ，ｊに対応する軸をもつ２次元空間の領域として表現できる。図４に示すように、ループ変数ｉ，ｊの値は５角形の領域の内側で変動する。具体的には、（ｉ，ｊ）の値は、（０，０），（０，１），（０，２），（０，３），（１，１），（１，２），（１，３），（１，４），（２，２），（２，３），（２，４），（２，５），（３，３），（３，４）の１４通りある。
【００４４】
エラー条件は、ソースコードに記述された配列定義および配列参照に基づいて、次のように定義される。インデックスｉ−２ｊ＋Ｍの値は、１００以上または−１以下である。
このような条件式から、情報処理装置１００は、数式処理によってループ変数ｉ，ｊを消去してパラメータＭについての判定式を生成することができる。数式処理として、フーリエ・モツキンの消去法などの「射影」と呼ばれるアルゴリズムを用いることができる。ループ変数ｉ，ｊおよびパラメータＭに対応する軸をもつ３次元空間に、上記の条件式を満たす領域を形成することを考える。射影は、ループ変数ｉ，ｊそれぞれに対応する軸方向から光を当ててパラメータＭに対応する空間に影を映し出すことを意味し、ループ変数ｉ，ｊを消去してパラメータＭの値の取り得る範囲を求めることができる。
【００４５】
フーリエ・モツキンの消去法によれば、例えば、次のような計算手順で射影が実現される。ループ変数やパラメータを含むｎ個の変数ｘ１，ｘ２，…，ｘｎを用いて表されたｎ次元連立不等式が存在するとする。そして、射影によってｎ次元連立不等式から、ｍ番目の変数ｘｍを消去したｎ−１次元連立不等式を算出することを考える。
【００４６】
まず、ｎ次元連立不等式の中から、変数ｘｍの値の上限および下限の少なくとも一方を定める不等式を抽出し、上限を定める不等式と下限を定める不等式の全ての組み合わせについて、変数ｘｍを含まない新たな不等式を生成する。例えば、上限を定める不等式の１つをａ×ｘｍ＜＝Ｕ（ａは定数、Ｕは変数ｘｍを含まない線形式）とし、下限を定める不等式の１つをＬ＜＝ｂ×ｘｍ（Ｌは変数ｘｍを含まない線形式、ｂは定数）とする。すると、ａ×Ｌ＜＝ａ×ｂ×ｘｍ＜＝ｂ×Ｕが成立するため、この２つの不等式の組み合わせから新たな不等式ａ×Ｌ＜＝ｂ×Ｕを生成することができる。新たに生成された不等式と、元のｎ次元連立不等式のうち変数ｘｍを含まない不等式とを合わせることで、変数ｘｍを消去したｎ−１次元連立不等式を得ることができる。
【００４７】
なお、第２の実施の形態では、射影によって条件式から判定式を容易に算出できるように、ｎ次元空間上に形成される領域が凸多面体となる場合を想定する。凸多面体は、有限個の線形不等式によって形成される領域であり、全ての面が凸多角形（全ての頂点の内角が１８０度未満である多角形）になっている多面体である。ループ変数の初期値と終了値が外側ループのループ変数とパラメータと定数の線形式で表現され、ループ変数の増加幅が定数であり、インデックスがループ変数とパラメータと定数の線形式で表現されている場合、ｎ次元空間上に形成される領域は凸多面体になる。よって、情報処理装置１００は、ループ変数およびインデックスがこのような条件を満たすループについて、ループ内の配列参照を検査する検査コードを、射影を用いて生成することができる。
【００４８】
図５は、実行時の並列化検査の例を示す図である。
ここでは、情報処理装置１００が、図３と異なる次のようなソースコードをコンパイルする場合を考える。このソースコードには、データ要素数が１００×１００の二次元配列である配列Ｂと、ループ前にその値が動的に決定されループ内でその値が変わらないパラメータＮ，Ｘ，Ｙと、ループ変数ｉ，ｊとが定義されている。
【００４９】
ループは入れ子になっており、外側ループの繰り返し回数を制御するためにループ変数ｉが使用され、内側ループの繰り返し回数を制御するためにループ変数ｊが使用される。外側ループについて、ループ変数ｉの初期値は定数０であり、ループ変数ｉの終了値はＮ−１であり、ループ変数ｉの増加幅は定数１である。内側ループについて、ループ変数ｊの初期値は定数０であり、ループ変数ｊの終了値はＮ−１であり、ループ変数ｊの増加幅は定数１である。内側ループの中では、インデックスｉ，ｊ＋Ｙが指す配列Ｂのデータ要素が取得され、インデックスｉ，ｊ＋Ｘが指す配列Ｂのデータ要素が更新される。すなわち、配列Ｂの参照は、ループ変数ｉ，ｊとパラメータＸ，Ｙに依存している。
【００５０】
また、内側ループには、並列化指示文（！ｏｃｌ  ｐａｒａｌｌｅｌ）が付加されている。並列化指示文の後の命令は、複数のＣＰＵ（例えば、ＣＰＵ１０１，１０２）または複数のコア（例えば、コア１０１ａ，１０１ｂ）を用いて並列実行されることになる。ユーザは、コンパイラの自動最適化によっては並列化されにくい命令について、並列化指示文を付加することで強制的に並列化することができる。図５で内側ループに付加された並列化指示文は、ループ変数ｊの異なる値に対応する処理を並列化することを意味する。
【００５１】
ただし、ループ内の配列参照は、並列化することで不適切な動作が発生することがある。例えば、パラメータＮの値が２以上であり、パラメータＸ，Ｙの値がＸ＝Ｙ＋１の関係を有しているとする。この場合、Ｂ［０，Ｙ］の値に基づいてＢ［０，１＋Ｙ］の値が算出され、Ｂ［０，１＋Ｙ］の値に基づいてＢ［０，２＋Ｙ］の値が算出されることになる。すなわち、ｊ＝０の処理結果を利用してｊ＝１の処理が行われることになり、ｊ＝０の処理とｊ＝１の処理の間に依存関係が発生する。そして、依存関係がある処理を並列化してしまうと、実行順序が保証されないために不適切な動作が発生し得る。
【００５２】
第２の実施の形態では、ループ変数ｊの異なる値に対応する処理の間に依存関係がある場合、そのループ処理は並列化不可であると判断する。依存関係は、同じ配列に対するデータ要素の書き込みと読み出しの間、および、同じ配列に対するデータ要素の書き込みと書き込みの間で発生し得る。一方、並列化可否は、実行時にその値が決まるパラメータＮ，Ｘ，Ｙに依存するため、コンパイル時に静的に検査することは難しい。そこで、情報処理装置１００は、並列化指示文が付加されたループについて、そのループを並列化してよいか実行時に動的に検査する検査コードを、実行コードに挿入する。
【００５３】
例えば、内側ループが開始される直前に、Ｘ−Ｙが１以上かつＮ−１以下であるか、または、Ｘ−Ｙが１−Ｎ以上かつ−１以下であるという判定式を用いて、並列化可否を検査する方法が考えられる。この判定式は、ループ変数ｉ，ｊの値が変動したときにインデックスｉ，ｊ＋Ｘの値の範囲とインデックスｉ，ｊ＋Ｙの値の範囲とが重複するようなパラメータＮ，Ｘ，Ｙの条件を示している。この判定式が満たされる場合、プログラムを強制終了するなどのエラー処理を行うようにする。この判定式にはループ変数ｉ，ｊが含まれていないため、並列化の可否を内側ループが開始される前に検査することができる。
【００５４】
なお、図５の検査コードでは、並列化不可であることを示す判定式を使用し、判定式が満たされる場合にエラー処理を行うこととしている。
図６は、並列化検査のための判定式の算出方法の例を示す図である。
【００５５】
並列化の一例として、ｉ＝ｉ０のときに、内側ループの偶数番目の処理（ｊ＝０，２，…）をコア１０１ａが実行し、内側ループの奇数番目の処理（ｊ＝１，３，…）をコア１０１ｂがコア１０１ａと並列に実行することが考えられる。コア１０１ａは、Ｂ［ｉ０，０＋Ｙ］のデータ要素を取得してＢ［ｉ０，０＋Ｘ］のデータ要素を更新し、また、Ｂ［ｉ０，２＋Ｙ］のデータ要素を取得してＢ［ｉ０，２＋Ｘ］のデータ要素を更新する。コア１０１ｂは、Ｂ［ｉ０，１＋Ｙ］のデータ要素を取得してＢ［ｉ０，１＋Ｘ］のデータ要素を更新し、また、Ｂ［ｉ０，３＋Ｙ］のデータ要素を取得してＢ［ｉ０，３＋Ｘ］のデータ要素を更新する。コア１０１ａが行う偶数番目の処理とコア１０１ｂが行う奇数番目の処理との間では、実行順序が保証されない。すなわち、コア１０１ｂのｊ＝１の処理の後にコア１０１ａのｊ＝２の処理が行われるとは限らない。
【００５６】
ここで、ｉ＝ｉ０のときに内側ループのｊ＝ｊ０の処理をコア１０１ａが実行し、ｉ＝ｉ１＝ｉ０のときに内側ループのｊ＝ｊ１の処理をコア１０１ｂが実行するとする。ｉ０，ｉ１はループ変数ｉの取り得る任意の値であり、ｊ０，ｊ１はループ変数ｊの取り得る任意の値である。内側ループが並列化可能であるには、ｉ＝ｉ０，ｊ＝ｊ０のときのインデックスｉ，ｊ＋Ｘの値（ｉ０，ｊ０＋Ｘ）が、ｉ＝ｉ１＝ｉ０，ｊ＝ｊ１のときのインデックスｉ，ｊ＋Ｙの値（ｉ１，ｊ１＋Ｙ）と一致することがないことを要する。
【００５７】
そこで、上記の図５で説明したパラメータＮ，Ｘ，Ｙの判定式は、図６に示すような条件式から数式処理によって導出することができる。条件式は、ｉ０，ｉ１，ｊ０，ｊ１の範囲を示すループ変数条件と、並列化不可であることを示すエラー条件を含む。ループ変数条件は、ソースコードに記述されたループ定義に基づいて、次のように定義される。ｉ０，ｉ１，ｊ０，ｊ１は定数０以上かつＮ−１以下である。ｉ０はｉ１と一致し、ｊ０はｊ１と異なる。エラー条件は、ソースコードに記述された配列参照に基づいて、次のように定義される。ｊ０＋Ｘはｊ１＋Ｙと一致する。
【００５８】
このような条件式から、情報処理装置１００は、数式処理によってｉ０，ｉ１，ｊ０，ｊ１を消去してパラメータＮ，Ｘ，Ｙについての判定式を生成することができる。数式処理として、フーリエ・モツキンの消去法などの「射影」を用いることができる。なお、前述のように、第２の実施の形態では、ループ変数の初期値と終了値が外側ループのループ変数とパラメータと定数の線形式で表現され、ループ変数の増加幅が定数であり、インデックスがループ変数とパラメータと定数の線形式で表現されているものとする。
【００５９】
図７は、判定式の最適化の例を示す図である。
上記ではメモリアクセス検査のための判定式と並列化可否検査のための判定式の例を挙げたが、同じループに対してこの２つの目的の判定式が共に生成されることがある。この２つの判定式は、同じパラメータを含むことが多く、その一部の論理式が共通していることがある。そこで、情報処理装置１００は、共通の論理式を抽出して、判定ステップが少なくなるように判定式を最適化する。これにより、プログラムの実行効率が向上する。
【００６０】
例えば、図３，４に示したような方法で、パラメータＬ，Ｚに依存するループについて、１＜＝ＺかつＬ＜＝Ｚという判定式が生成されたとする。また、同じループについて、図５，６に示したような方法で、１＜＝ＺかつＬ−１＜＝２Ｚという判定式が生成されたとする。２つの判定式には共通の論理式１＜＝Ｚが含まれる。そこで、情報処理装置１００は、まず論理式１＜＝Ｚを評価し、論理式１＜＝Ｚを満たす場合のみ、論理式Ｌ＜＝Ｚおよび論理式Ｌ−１＜＝２Ｚを評価するような検査コードを生成する。論理式１＜＝Ｚの評価を共通化することで、判定ステップを少なくすることができる。
【００６１】
次に、情報処理装置１００の構成およびコンパイル手順について説明する。
図８は、情報処理装置で動作するソフトウェア例を示すブロック図である。
情報処理装置１００は、ファイル記憶部１１０、コンパイラ１２０およびリンカ１３０を有する。ファイル記憶部１１０は、例えば、ＲＡＭ１０３またはＨＤＤ１０４に確保した記憶領域として実装される。コンパイラ１２０およびリンカ１３０は、例えば、ＣＰＵ１０１，１０２が実行するソフトウェアのモジュールとして実装される。
【００６２】
ファイル記憶部１１０は、ソースファイル１１１、オブジェクトファイル１１２および実行ファイル１１３を記憶する。ソースファイル１１１は、Ｃ言語などの高級言語を用いて記述されたソースコードを含むファイルである。ソースファイル１１１は、ユーザが入力デバイス２２を用いて作成したものでもよいし、他の情報処理装置からネットワーク２４経由で情報処理装置１００に送信されたものでもよい。オブジェクトファイル１１２は、ＣＰＵが直接理解できる機械語を用いて記述されたオブジェクトコードを含むファイルである。オブジェクトコードは、ソースコードをコンパイルすることで生成される。実行ファイル１１３は、実行可能形式のプログラムモジュールであり、オブジェクトファイル１１２から生成される。実行ファイル１１３は、情報処理装置１００で実行されてもよいし、他の情報処理装置に送信されて当該他の情報処理装置で実行されてもよい。
【００６３】
コンパイラ１２０は、ファイル記憶部１１０からソースファイル１１１を取得し、ソースファイル１１１に含まれるソースコードをコンパイルする。そして、コンパイラ１２０は、ソースコードに対応するオブジェクトコードを生成し、生成したオブジェクトコードを含むオブジェクトファイル１１２をファイル記憶部１１０に格納する。コンパイラ１２０は、ソースコード解析部１２１、インデックス分析部１２２、並列化分析部１２３、最適化部１２４およびオブジェクト生成部１２５を有する。
【００６４】
ソースコード解析部１２１は、ソースコードを解析し、ソースコードに表された演算命令および演算命令の実行順序を示す制御構造を認識する。制御構造には、ループ、無条件分岐、条件分岐、サブルーチンコールなどが含まれる。ソースコード解析部１２１が行う解析には、例えば、字句解析、構文解析、意味解析などが含まれる。
【００６５】
インデックス分析部１２２は、ソースコード解析部１２１で認識されたループについて、配列のインデックスの値が定義域に収まるか分析する。インデックス分析部１２２は、インデックスの値が定義域を超えると静的に判断される場合、コンパイルエラーと判断する。一方、インデックス分析部１２２は、インデックスの値が定義域を超えるか否か静的には不明である場合、実行ファイル１１３の実行時にこれを動的に検査するための判定式を出力する。なお、インデックス分析部１２２は、インデックスの値が定義域に収まると静的に判断される場合、判定式を出力しなくてもよい。
【００６６】
並列化分析部１２３は、ソースコード解析部１２１で認識されたループのうち並列化指示文が付加されたものについて、配列参照を並列化可能か分析する。並列化分析部１２３は、並列化不可と静的に判断される場合、コンパイルエラーと判断する。一方、並列化分析部１２３は、並列化可能か否か静的には不明である場合、実行ファイル１１３の実行時にこれを動的に検査するための判定式を出力する。なお、並列化分析部１２３は、並列化可能と静的に判断される場合、判定式を出力しなくてもよい。
【００６７】
最適化部１２４は、インデックス分析部１２２および並列化分析部１２３が出力した判定式を用いて、ループ毎に、ループの直前に挿入される検査コードを生成する。あるループについてインデックス分析部１２２と並列化分析部１２３の一方のみが判定式を出力した場合、最適化部１２４は、判定式が満たされるときにエラー処理を行う検査コードを生成する。一方、同じループについてインデックス分析部１２２と並列化分析部１２３の両方が判定式を出力した場合、最適化部１２４は、２つの判定式に共通の論理式が含まれているか確認し、判定式が小さくなるように最適化する。そして、最適化部１２４は、最適化した判定式が満たされるときにエラー処理を行う検査コードを生成する。
【００６８】
オブジェクト生成部１２５は、ソースコード解析部１２１の解析結果に基づいて、ソースコードに対応するオブジェクトコードを生成する。このとき、オブジェクト生成部１２５は、最適化部１２４が生成した検査コードをループの直前に挿入する。
【００６９】
リンカ１３０は、ファイル記憶部１１０からオブジェクトファイル１１２を取得し、オブジェクトファイル１１２に含まれるオブジェクトコードから参照される他のオブジェクトファイルやライブラリを検索する。そして、リンカ１３０は、オブジェクトファイル１１２と他のオブジェクトファイルやライブラリとを結合し、実行ファイル１１３を生成する。なお、リンカ１３０の機能をコンパイラ１２０が有していてもよい。
【００７０】
図９は、コンパイルの手順例を示すフローチャートである。
（Ｓ１）ソースコード解析部１２１は、ソースファイル１１１に含まれるソースコードを解析する。ここで、ソースコードに記述されたループが認識される。
【００７１】
（Ｓ２）インデックス分析部１２２は、ステップＳ１で認識されたループそれぞれについてインデックス分析を行う。インデックス分析により、ステップＳ１で認識されたループの一部または全部について、ループ内の配列参照がメモリアクセス違反になるパラメータ条件を示す判定式が生成されることがある。インデックス分析の詳細は後述する。
【００７２】
（Ｓ３）インデックス分析部１２２は、ステップＳ２で生成した判定式の少なくとも１つが、静的なインデックスエラーを示しているか判断する。インデックス分析部１２２は、生成した判定式を最適化部１２４に出力する。静的なインデックスエラーを示している場合はステップＳ８に処理が進む。それ以外の場合はステップＳ４に処理が進む。
【００７３】
（Ｓ４）並列化分析部１２３は、ステップＳ１で認識されたループのうち並列化指示文が付加されたものについて並列化分析を行う。並列化分析により、並列化指示文が付加されたループの一部または全部について、ループ内の配列参照を並列化できるパラメータ条件を示す判定式が生成されることがある。並列化分析の詳細は後述する。
【００７４】
（Ｓ５）並列化分析部１２３は、ステップＳ４で生成した判定式の少なくとも１つが、静的な並列化エラーを示しているか判断する。並列化分析部１２３は、生成した判定式を最適化部１２４に出力する。静的な並列化エラーを示している場合はステップＳ９に処理が進む。それ以外の場合はステップＳ６に処理が進む。なお、ステップＳ２，Ｓ３，Ｓ８とステップＳ４，Ｓ５，Ｓ９とは、上記手順と逆順に実行してもよいし並行して実行してもよい。
【００７５】
（Ｓ６）最適化部１２４は、ステップＳ３で出力された判定式とステップＳ５で出力された判定式とをループ単位に分類し、最適化する。同じループについてインデックス分析部１２２と並列化分析部１２３の両方が判定式を出力した場合、最適化部１２４は、２つの判定式に共通に含まれる論理式を検索する。共通の論理式がない場合、最適化部１２４は、判定式を変更しなくてよい。一方、共通の論理式がある場合、最適化部１２４は、共通の論理式を１回だけ評価すればよいように判定式に含まれる論理式を組み替える。
【００７６】
（Ｓ７）最適化部１２４は、ステップＳ１で認識されたループの一部または全部について、ステップＳ６で最適化した判定式を含む検査コードを生成する。オブジェクト生成部１２５は、ループの直前で検査コードが実行されるようなオブジェクトコードを生成する。オブジェクト生成部１２５は、生成したオブジェクトコードを含むオブジェクトファイル１１２をファイル記憶部１１０に格納する。これにより、コンパイルが終了する。
【００７７】
（Ｓ８）インデックス分析部１２２は、コンパイルエラーを示すメッセージを出力する。例えば、インデックス分析部１２２は、コンパイルエラーのメッセージをディスプレイ２１に表示する。そして、ステップＳ４に処理が進む。
【００７８】
（Ｓ９）並列化分析部１２３は、コンパイルエラーを示すメッセージを出力する。例えば、並列化分析部１２３は、コンパイルエラーのメッセージをディスプレイ２１に表示する。そして、ステップＳ６に処理が進む。
【００７９】
図１０は、インデックス分析の手順例を示すフローチャートである。
このフローチャートが示す処理は、上記のステップＳ２において実行される。
（Ｓ２０）インデックス分析部１２２は、ループを１つ選択する。
【００８０】
（Ｓ２１）インデックス分析部１２２は、ステップＳ２０で選択したループがインデックス分析を行えるものか判断する。インデックス分析を行えるループは、ループ変数およびパラメータの変動範囲を示すｎ次元空間上の領域が凸多面体になるものである。ループ変数の初期値と終了値が外側ループのループ変数とパラメータと定数の線形式で表現され、ループ変数の増加幅が定数であり、インデックスがループ変数とパラメータと定数の線形式で表現されるループは、インデックス分析を行える。インデックス分析を行える場合はステップＳ２２に処理が進み、それ以外の場合はステップＳ２５に処理が進む。
【００８１】
（Ｓ２２）インデックス分析部１２２は、ソースコードの記述に基づいて、インデックスエラーが発生することを示す条件式を生成する。条件式には、図４に示したようなループ変数条件とエラー条件とが含まれる。エラー条件は、インデックスの値が配列定義時に宣言された定義域を超えることを示す。ループ変数条件およびエラー条件は、ループ変数およびパラメータを用いた線形不等式として表現され得る。
【００８２】
（Ｓ２３）インデックス分析部１２２は、数式処理によってステップＳ２２で生成した条件式からループ変数を除去し、条件式が成立するときのパラメータの値の範囲を示す判定式を生成する。ただし、前述のように、パラメータの値にかかわらず条件式が常に成立する場合は、条件式にパラメータが含まれないこともある。数式処理としては、フーリエ・モツキンの消去法などの射影のアルゴリズムを使用する。
【００８３】
（Ｓ２４）インデックス分析部１２２は、ステップＳ２３で生成した判定式が、パラメータの値にかかわらず条件式が常に成立することを示しているか判断する。判定式が常に成立する場合、判定式の中にパラメータが現れないこともある。条件を満たす場合はステップＳ２６に処理が進み、それ以外の場合はステップＳ２５に処理が進む。
【００８４】
（Ｓ２５）インデックス分析部１２２は、ステップＳ２０で未選択のループが残っているか判断する。未選択のループがある場合はステップＳ２０に処理が進み、全てのループを選択した場合はインデックス分析の処理を終了する。
【００８５】
（Ｓ２６）インデックス分析部１２２は、判定式が常に成立することは、ループ内の配列参照が必ずメモリアクセス違反になることを示すため、ループに静的なインデックスエラーが存在すると判断する。そして、ステップＳ２５に処理が進む。
【００８６】
図１１は、並列化分析の手順例を示すフローチャートである。
このフローチャートが示す処理は、上記のステップＳ４において実行される。
（Ｓ４０）並列化分析部１２３は、並列化指示文が付加されたループを１つ選択する。
【００８７】
（Ｓ４１）並列化分析部１２３は、ステップＳ４０で選択したループが並列化分析を行えるものか判断する。並列化分析を行えるループは、インデックス分析と同様、ループ変数およびパラメータの変動範囲を示すｎ次元空間上の領域が凸多面体になるものである。ループ変数の初期値と終了値が外側ループのループ変数とパラメータと定数の線形式で表現され、ループ変数の増加幅が定数であり、インデックスがループ変数とパラメータと定数の線形式で表現されるループは、並列化分析を行える。並列化分析を行える場合はステップＳ４２に処理が進み、それ以外の場合はステップＳ４５に処理が進む。
【００８８】
（Ｓ４２）並列化分析部１２３は、ソースコードの記述に基づいて、並列化エラーが発生することを示す条件式を生成する。条件式には、図６に示したようなループ変数条件とエラー条件とが含まれる。エラー条件は、並列化するｊ０番目の処理とｊ１番目の処理とにおいて、同じインデックスの値を用いて同じ配列が参照されることを示す。ただし、ｊ０番目の処理における配列参照とｊ１番目の処理における配列参照の少なくとも一方は、データ要素の更新を含む。ループ変数条件およびエラー条件は、ループ変数およびパラメータを用いた線形不等式（線形等式である場合を含む）として表現され得る。
【００８９】
（Ｓ４３）並列化分析部１２３は、数式処理によってステップＳ４２で生成した条件式からループ変数を除去し、条件式が成立するときのパラメータの値の範囲を示す判定式を生成する。ただし、前述のように、パラメータの値にかかわらず条件式が常に成立する場合は、条件式にパラメータが含まれないこともある。数式処理としては、フーリエ・モツキンの消去法などの射影のアルゴリズムを使用する。
【００９０】
（Ｓ４４）並列化分析部１２３は、ステップＳ４３で生成した判定式が、パラメータの値にかかわらず条件式が常に成立することを示しているか判断する。判定式が常に成立する場合、判定式の中にパラメータが現れないこともある。条件を満たす場合はステップＳ４６に処理が進み、それ以外の場合はステップＳ４５に処理が進む。
【００９１】
（Ｓ４５）並列化分析部１２３は、ステップＳ４０で未選択のループが残っているか判断する。未選択のループがある場合はステップＳ４０に処理が進み、全てのループを選択した場合は並列化分析の処理を終了する。
【００９２】
（Ｓ４６）並列化分析部１２３は、判定式が常に成立することは、ループ内の配列参照が必ず並列化不可であることを示すため、ループへの並列化指示文の付加が不適切でありループに静的な並列化エラーが存在すると判断する。そして、ステップＳ４５に処理が進む。
【００９３】
第２の実施の形態の情報処理装置１００によれば、ループ変数の変動範囲を示す１または２以上の線形式と、配列のインデックスの値が定義域を超えることを示す線形式とを含む条件式が生成される。この条件式から射影によってループ変数が消去され、パラメータの値の範囲を示す判定式が生成される。この判定式に基づいて、ループを実行してよいかループ直前に検査される。よって、ループ内で検査する場合と比べて検査コードの実行回数を減らすことができ、検査のオーバヘッドを小さくしてプログラムの実行効率を向上させることができる。また、複数のループ変数が使用される多重ループなど、ループ定義が複雑であるループについても、パラメータの判定式を生成できる。
【００９４】
また、情報処理装置１００によれば、ループ変数の変動範囲を示す１または２以上の線形式と、並列化される処理が同じデータ要素を使用することを示す線形式とを含む条件式が生成される。この条件式から射影によってループ変数が消去され、パラメータの値の範囲を示す判定式が生成される。この判定式に基づいて、ループを並列実行してよいかループ直前に検査される。よって、複数のループ変数が使用される多重ループなど、ループ定義が複雑であるループについても、パラメータの判定式を生成できる。
【００９５】
なお、前述のように、第１の実施の形態の情報処理は、情報処理装置１０にプログラムを実行させることで実現することができる。また、第２の実施の形態の情報処理は、情報処理装置１００にプログラムを実行させることで実現することができる。
【００９６】
プログラムは、コンピュータ読み取り可能な記録媒体（例えば、記録媒体２３）に記録しておくことができる。記録媒体としては、例えば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。プログラムは、可搬型の記録媒体に記録されて配布されることがある。その場合、可搬型の記録媒体からＨＤＤなどの他の記録媒体（例えば、ＨＤＤ１０４）にプログラムを複製して（インストールして）実行してもよい。
【符号の説明】
【００９７】
１０  情報処理装置
１１  記憶部
１２  演算部
１３  ソースコード
１４  オブジェクトコード
１４ａ  検査コード
１５  条件式
１６  判定情報
【図１】
2015094960.tif 000003
【図２】
2015094960.tif 000004
【図３】
2015094960.tif 000005
【図４】
2015094960.tif 000006
【図５】
2015094960.tif 000007
【図６】
2015094960.tif 000008
【図７】
2015094960.tif 000009
【図８】
2015094960.tif 000010
【図９】
2015094960.tif 000011
【図１０】
2015094960.tif 000012
【図１１】
2015094960.tif 000013