(57)【特許請求の範囲】
【請求項１】
ソフトウェアのプログラムコードのうち、ネスト構造の複数のループ文とループ本体とを用いて、第１変数に対して縮約演算する第１式についての計算を繰り返す処理の内容が記述されたループ記述箇所を特定し、
前記ループ記述箇所内にある第３変数に対して縮約演算する第４式のうち、前記第１式のうちの部分式との間で、少なくとも、インデックスに使用される変数に代入される値が共通であり、かつ、インデックスに使用される変数間の関係が同一である他の部分式を特定し、
前記第１式のうちの部分式を第２変数に対して縮約演算する第２式についての計算を繰り返す第１コード、および、前記第１式のうちの前記部分式が前記第２変数に置換された第３式についての計算を繰り返し、かつ、前記第４式のうちの前記他の部分式が前記第２変数に置換された第５式についての計算を繰り返す第２コードを生成し、
前記プログラムコードのうちの前記ループ記述箇所を前記第１コードおよび前記第２コードに変換したプログラムコードを出力する、
制御部を有することを特徴とする情報処理装置。
【請求項２】
前記制御部は、
前記第１式のうちの各部分式について、当該部分式を縮約演算する前記第２式についての計算の種類および繰り返し回数と、当該部分式が置換された前記第３式についての計算の種類および繰り返し回数とを特定し、
特定した前記種類および前記繰り返し回数に基づいて、前記第１式のうちの各部分式について、当該部分式を縮約演算する前記第２式についての計算を繰り返す演算量、および、当該部分式が置換された前記第３式についての計算を繰り返す演算量の合計と、前記ループ記述箇所の演算量との差分を算出し、
算出した前記差分に基づいて、前記第１式のうちのいずれかの部分式を選択し、
選択した前記いずれかの部分式について前記第１コードおよび前記第２コードを生成する、
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記制御部は、
前記第１式のうちの各部分式について、当該部分式を縮約演算する前記第２式についての計算の繰り返し条件に使用する変数および繰り返し回数と、当該部分式が置換された前記第３式についての計算の繰り返し条件に使用する変数および繰り返し回数とを特定し、
特定した前記変数および前記繰り返し回数に基づいて、ループ文を用いて前記第１コードを生成し、ループ文を用いて前記第２コードを生成する、
ことを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
コンピュータが、
ソフトウェアのプログラムコードのうち、ネスト構造の複数のループ文とループ本体とを用いて、第１変数に対して縮約演算する第１式についての計算を繰り返す処理の内容が記述されたループ記述箇所を特定し、
前記ループ記述箇所内にある第３変数に対して縮約演算する第４式のうち、前記第１式のうちの部分式との間で、少なくとも、インデックスに使用される変数に代入される値が共通であり、かつ、インデックスに使用される変数間の関係が同一である他の部分式を特定し、
前記第１式のうちの部分式を第２変数に対して縮約演算する第２式についての計算を繰り返す第１コード、および、前記第１式のうちの前記部分式が前記第２変数に置換された第３式についての計算を繰り返し、かつ、前記第４式のうちの前記他の部分式が前記第２変数に置換された第５式についての計算を繰り返す第２コードを生成し、
前記プログラムコードのうちの前記ループ記述箇所を前記第１コードおよび前記第２コードに変換したプログラムコードを出力する、
処理を実行することを特徴とするコンパイル方法。
【請求項５】
コンピュータに、
ソフトウェアのプログラムコードのうち、ネスト構造の複数のループ文とループ本体とを用いて、第１変数に対して縮約演算する第１式についての計算を繰り返す処理の内容が記述されたループ記述箇所を特定し、
前記ループ記述箇所内にある第３変数に対して縮約演算する第４式のうち、前記第１式のうちの部分式との間で、少なくとも、インデックスに使用される変数に代入される値が共通であり、かつ、インデックスに使用される変数間の関係が同一である他の部分式を特定し、
前記第１式のうちの部分式を第２変数に対して縮約演算する第２式についての計算を繰り返す第１コード、および、前記第１式のうちの前記部分式が前記第２変数に置換された第３式についての計算を繰り返し、かつ、前記第４式のうちの前記他の部分式が前記第２変数に置換された第５式についての計算を繰り返す第２コードを生成し、
前記プログラムコードのうちの前記ループ記述箇所を前記第１コードおよび前記第２コードに変換したプログラムコードを出力する、
処理を実行させることを特徴とするコンパイルプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、コンパイル方法、およびコンパイルプログラムに関する。
【背景技術】
【０００２】
従来、プログラミング言語を用いてソフトウェアの処理内容が記述されたソースコードに基づいて、コンピュータが実行可能な形式のオブジェクトコードを生成するコンパイルの技術がある。また、ソフトウェアの処理時間が短縮されるように、ソースコードに規定された機能が変更されない範囲で、ソースコードに記述された処理内容を変更して、演算量を低減する最適化の技術がある。
【０００３】
先行技術としては、例えば、多重ループ中における非線形添え字を持つ配列の参照を最適化するためのものがある。また、例えば、ループ中に重複定義される配列要素の解析を行い、ループ中で配列要素の重複定義を解消するための技術がある。また、例えば、逐次プログラムを分散記憶型並列機向けに変換する場合に、実行性能が高くなるようなデータの分割方法を与えるための技術がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平５−１４３３５８号公報
【特許文献２】特開平４−２５９４２号公報
【特許文献３】特開平７−２５３９５５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した従来技術では、ソフトウェアの演算量を低減させて最適化することが難しい場合がある。例えば、縮約演算を行う式が含まれる多重ループについては、処理内容をどのように変更すれば演算量が低減されるか分からず、ソフトウェアの処理時間を短縮することができない場合がある。
【０００６】
１つの側面では、本発明は、ソフトウェアの演算量を低減させて最適化することができる情報処理装置、コンパイル方法、およびコンパイルプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の一側面によれば、ソフトウェアのプログラムコードのうち、第１変数に対して縮約演算する第１式についての計算を繰り返すループ箇所を特定し、前記第１式のうちの部分式を第２変数に対して縮約演算する第２式についての計算を繰り返す第１コード、および、前記第１式のうちの前記部分式が前記第２変数に置換された第３式についての計算を繰り返す第２コードを生成し、前記プログラムコードのうちの前記ループ箇所を前記第１コードおよび前記第２コードに変換したプログラムコードを出力する情報処理装置、コンパイル方法、およびコンパイルプログラムが提案される。
【発明の効果】
【０００８】
本発明の一態様によれば、ソフトウェアの演算量を低減させて最適化することができるという効果を奏する。
【図面の簡単な説明】
【０００９】
【図１】図１は、実施の形態１にかかるコンパイル方法の一実施例を示す説明図である。
【図２】図２は、実施の形態１にかかる情報処理装置１００のハードウェア構成例を示すブロック図である。
【図３】図３は、実施の形態１にかかる情報処理装置１００の機能的構成例を示すブロック図である。
【図４】図４は、ソースコード４００の一例を示す説明図である。
【図５】図５は、多重ループを検出する一例を示す説明図である。
【図６】図６は、アドレスを割り当てる一例を示す説明図である。
【図７】図７は、縮約演算ループ箇所を検出する一例を示す説明図（その１）である。
【図８】図８は、縮約演算ループ箇所を検出する一例を示す説明図（その２）である。
【図９】図９は、部分式を抽出する一例を示す説明図（その１）である。
【図１０】図１０は、部分式を抽出する一例を示す説明図（その２）である。
【図１１】図１１は、部分式を抽出する一例を示す説明図（その３）である。
【図１２】図１２は、部分式を抽出する一例を示す説明図（その４）である。
【図１３】図１３は、部分式を抽出する一例を示す説明図（その５）である。
【図１４】図１４は、部分式を抽出する一例を示す説明図（その６）である。
【図１５】図１５は、スカラー変数を分類する一例を示す説明図である。
【図１６】図１６は、削減される演算量を算出する一例を示す説明図（その１）である。
【図１７】図１７は、削減される演算量を算出する一例を示す説明図（その２）である。
【図１８】図１８は、ソースコード４００を最適化する一例を示す説明図である。
【図１９】図１９は、コンパイル処理手順の一例を示すフローチャートである。
【図２０】図２０は、ループ分割処理手順の一例を示すフローチャートである。
【図２１】図２１は、部分式抽出処理手順の一例を示すフローチャートである。
【図２２】図２２は、抽出コア処理手順の一例を示すフローチャート（その１）である。
【図２３】図２３は、抽出コア処理手順の一例を示すフローチャート（その２）である。
【図２４】図２４は、抽出コア処理手順の一例を示すフローチャート（その３）である。
【図２５】図２５は、抽出サブ処理手順の一例を示すフローチャートである。
【図２６】図２６は、分割部分式生成処理手順の一例を示すフローチャートである。
【図２７】図２７は、変数分類処理手順の一例を示すフローチャート（その１）である。
【図２８】図２８は、変数分類処理手順の一例を示すフローチャート（その２）である。
【図２９】図２９は、第１パラメータ抽出処理手順の一例を示すフローチャートである。
【図３０】図３０は、第２パラメータ抽出処理手順の一例を示すフローチャートである。
【図３１】図３１は、第３パラメータ抽出処理手順の一例を示すフローチャートである。
【図３２】図３２は、縮約可能変数抽出処理手順の一例を示すフローチャートである。
【図３３】図３３は、削減量算出処理手順の一例を示すフローチャートである。
【図３４】図３４は、算出サブ処理手順の一例を示すフローチャート（その１）である。
【図３５】図３５は、算出サブ処理手順の一例を示すフローチャート（その２）である。
【図３６】図３６は、算出サブ処理手順の一例を示すフローチャート（その３）である。
【図３７】図３７は、最適化対象決定処理手順の一例を示すフローチャートである。
【図３８】図３８は、ＡＳＴ変形処理手順の一例を示すフローチャートである。
【図３９】図３９は、縮約演算式挿入処理手順の一例を示すフローチャートである。
【図４０】図４０は、変形サブ処理手順の一例を示すフローチャートである。
【図４１】図４１は、実施の形態２にかかるコンパイル方法の一実施例を示す説明図である。
【図４２】図４２は、実施の形態２にかかるソースコード４２００の一例を示す説明図である。
【図４３】図４３は、部分式を正準化する一例を示す説明図（その１）である。
【図４４】図４４は、部分式を正準化する一例を示す説明図（その２）である。
【図４５】図４５は、部分式を正準化する一例を示す説明図（その３）である。
【図４６】図４６は、共通する部分式を特定する一例を示す説明図である。
【図４７】図４７は、ソースコード４２００を最適化する一例を示す説明図である。
【図４８】図４８は、実施の形態２にかかる削減量算出処理手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００１０】
以下、図面を参照して、本発明にかかる情報処理装置、コンパイル方法、およびコンパイルプログラムの実施の形態を詳細に説明する。
【００１１】
（実施の形態１にかかるコンパイル方法の一実施例）
図１は、実施の形態１にかかるコンパイル方法の一実施例を示す説明図である。図１において、情報処理装置１００は、プログラムコードに規定された機能が変更されない範囲で、プログラムコードに記述された処理内容を変更して、ソフトウェアの実行時の演算量を低減させるコンピュータである。プログラムコードは、例えば、ソースコード１０１である。
【００１２】
ここで、コンパイルの際に、ソフトウェアについての所定の性能が向上するようにプログラムコードを変換する最適化の技術がある。所定の性能とは、例えば、ソフトウェアの実行時の処理時間、メモリ使用量、または消費電力などである。最適化の技術には、例えば、ループ処理の演算量を低減することにより、ソフトウェアの実行時の演算量を低減させて、ソフトウェアの実行時の処理時間の短縮化を図るものがある。ループ処理とは、繰り返し条件にしたがって、ループ本体内の処理を繰り返し実行する処理である。最適化の技術には、具体的には、１つのループ処理において定数として扱うことが可能な式がループ本体内にあれば、ループ処理外で当該式の計算を行っておき、ループ処理においては計算結果で当該式を置き換えるものがある。
【００１３】
しかしながら、縮約演算する式が含まれるネスト構造の多重ループ処理のうちの複数のループ処理を通して計算される式の集まりのうちに、定数として扱うことが可能な式が含まれても、上述した最適化の技術を適用することができない。このため、縮約演算する式が含まれる多重ループ処理については、処理内容をどのように変更すれば演算量が低減されるか分からず、ソフトウェアの処理時間を短縮することができない場合がある。
【００１４】
そこで、本実施の形態では、縮約演算する式が含まれる多重ループ処理について処理内容を変更して、ソフトウェアの実行時の演算量を低減させることにより、ソフトウェアの処理時間の短縮化を図るコンパイル方法について説明する。縮約演算とは、複数のデータ値を１つのデータ値に縮約する計算である。縮約演算は、例えば、加算、乗算、最大値の計算、または最小値の計算などである。
【００１５】
図１の例では、プログラムコードとして、式１１０「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｊ）＊ｂ（ｋ，ｉ）」についての計算を繰り返すループ箇所が記述されたソースコード１０１を例に挙げて、情報処理装置１００の動作について説明する。
【００１６】
式１１０は、変数「ａ（ｉ，ｊ）」や変数「ｂ（ｋ，ｉ）」を第１変数「ｓ（ｉ，ｊ）」に対して縮約演算する式である。また、「＝」は代入演算子である。ここで、例えば、ｎ＝２とした場合には、ループ箇所において式１１０についての計算を繰り返すという第１処理内容は、符号１２０に示す下記式（１）〜（４）について計算を行うという第２処理内容と等価である。
【００１７】
ｓ（１，１）＝ｓ（１，１）＋ａ（１，１）＊ｂ（１，１）＋ａ（１，１）＊ｂ（２，１）                                                                ・・・（１）
ｓ（１，２）＝ｓ（１，２）＋ａ（１，２）＊ｂ（１，１）＋ａ（１，２）＊ｂ（２，１）                                                                ・・・（２）
ｓ（２，１）＝ｓ（２，１）＋ａ（２，１）＊ｂ（１，２）＋ａ（２，１）＊ｂ（２，２）                                                                ・・・（３）
ｓ（２，２）＝ｓ（２，２）＋ａ（２，２）＊ｂ（１，２）＋ａ（２，２）＊ｂ（２，２）                                                                ・・・（４）
【００１８】
そして、上述した第２処理内容は、四則演算の交換法則、分配法則、および結合法則などにしたがえば、機能を変更せずに、符号１３０に示す下記式（５）〜式（８）についての計算を行うという第３処理内容に変更することが可能である。これにより、第３処理内容では、第２処理内容よりも演算子の数が減るため、演算量が低減される。
【００１９】
ｓ（１，１）＝ｓ（１，１）＋ａ（１，１）＊｛ｂ（１，１）＋ｂ（２，１）｝
・・・（５）
ｓ（１，２）＝ｓ（１，２）＋ａ（１，２）＊｛ｂ（１，１）＋ｂ（２，１）｝
・・・（６）
ｓ（２，１）＝ｓ（２，１）＋ａ（２，１）＊｛ｂ（１，２）＋ｂ（２，２）｝
・・・（７）
ｓ（２，２）＝ｓ（２，２）＋ａ（２，２）＊｛ｂ（１，２）＋ｂ（２，２）｝
・・・（８）
【００２０】
さらに、上述した第３処理内容は、機能を変更せずに、定数として扱うことが可能な、同一内容の式についての計算を行ってから、当該計算で得られた結果を利用して式（５）〜（８）について計算を行うという第４処理内容に変更することが可能である。例えば、式「ｂ（１，１）＋ｂ（２，１）」や式「ｂ（１，１）＋ｂ（２，２）」についての計算が行われた後に、当該計算で得られた結果を利用して式（５）〜（８）についての計算が行われる。これにより、第４処理内容では、定数として扱うことが可能な、同一内容の式についての計算を複数回行わなくてもよくなるため、演算量が低減される。
【００２１】
このように、複数のループ処理を通して計算される式の集まりのうちに、定数として扱うことが可能な式が含まれる場合には、ソースコード１０１に記述された処理内容を変更すれば、演算量を低減することが可能である。このため、情報処理装置１００は、上述した処理内容の変更による演算量の低減化が実現されるように、ソースコード１０１のループ箇所を変換して、変換後のソースコード１０２を出力することになる。
【００２２】
図１の例では、（１−１）情報処理装置１００は、ソースコード１０１を取得する。次に、情報処理装置１００は、ソースコード１０１に対して字句解析や文法解析を行い、ソースコード１０１に対応する抽象構文木を作成する。そして、情報処理装置１００は、抽象構文木に基づいて、ソースコード１０１に記述された、式１１０「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｊ）＊ｂ（ｋ，ｉ）」についての計算を繰り返すループ箇所を特定する。
【００２３】
（１−２）情報処理装置１００は、式１１０のうちの部分式「ｂ（ｋ，ｉ）」を第２変数「ｔ（ｉ）」に対して縮約演算する式１４０「ｔ（ｉ）＝ｔ（ｉ）＋ｂ（ｋ，ｉ）」についての計算を繰り返す第１コードを生成する。第１コードは、上述した式「ｂ（１，１）＋ｂ（２，１）」や式「ｂ（１，１）＋ｂ（２，２）」についての計算を行うという処理内容に対応するコードである。第２変数は、一時的に演算結果を記憶するための変数である。
【００２４】
また、情報処理装置１００は、式１１０のうちの部分式が第２変数に置換された式１５０「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｊ）＊ｔ（ｉ）」についての計算を繰り返す第２コードを生成する。第２コードは、式「ｂ（１，１）＋ｂ（２，１）」や式「ｂ（１，１）＋ｂ（２，２）」についての計算で得られた結果を利用して、式（５）〜（８）についての計算を行うという処理内容に対応するコードである。
【００２５】
（１−３）情報処理装置１００は、ソースコード１０１のうちのループ箇所を第１コードおよび第２コードに変換する。そして、情報処理装置１００は、変換後のソースコード１０２を、表示装置に出力し、他のコンピュータに送信し、または記憶装置に記憶する。結果として、情報処理装置１００、または他のコンピュータが、ソースコード１０２をコンパイルして、オブジェクトコードを作成可能になる。
【００２６】
このように、情報処理装置１００によれば、式１１０の部分式を第２変数に縮約演算する式１４０を含むループ処理を示す第１コードと、第２変数で部分式を置換した式１５０を含むループ処理を示す第２コードとを生成することができる。そして、情報処理装置１００によれば、縮約演算する式１１０を含むループ箇所を、第１コードと第２コードとに変換することができる。これにより、情報処理装置１００は、複数のループ処理を通して計算される式の集まりに含まれる、定数として扱うことが可能な式を用いて式１４０を作成し、式１４０についての計算が予め行われるように、ソースコード１０１を変換することができる。
【００２７】
結果として、情報処理装置１００は、ソフトウェアの実行時の演算量を低減して、ソフトウェアの処理時間の短縮化を図ることができる。例えば、ソースコード１０１では、加算「＋」と乗算「＊」とが、「ｎ＾３」回繰り返して実行されるため、演算量は「２ｎ＾３」である。これに対し、変換後のソースコード１０２では、加算「＋」が「ｎ＾２」回実行され、加算「＋」と乗算「＊」とが「ｎ＾２」回実行されるため、演算量は「ｎ＾２＋２ｎ＾２」である。結果として、変換後のソースコード１０２では、ｎ＞２であれば、演算量が低減される。
【００２８】
ここでは、情報処理装置１００が、抽象構文木に基づいてループ箇所を特定する場合について説明したが、これに限らない。例えば、情報処理装置１００は、抽象構文木を作成せずにソースコード１０１からループ箇所を特定してもよい。また、ここでは、情報処理装置１００が、ソースコード１０１を変換する場合について説明したが、これに限らない。例えば、情報処理装置１００は、ソースコード１０１に対応する抽象構文木を、ソースコード１０２に対応する抽象構文木に変換して、出力してもよい。
【００２９】
（実施の形態１にかかる情報処理装置１００のハードウェア構成例）
次に、図２を用いて、実施の形態１にかかる情報処理装置１００のハードウェア構成例について説明する。
【００３０】
図２は、実施の形態１にかかる情報処理装置１００のハードウェア構成例を示すブロック図である。図２において、情報処理装置１００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）２０１と、メモリ２０２と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）２０３と、ディスクドライブ２０４と、ディスク２０５と、を有する。また、各構成部は、バス２００によってそれぞれ接続される。
【００３１】
ここで、ＣＰＵ２０１は、情報処理装置１００の全体の制御を司る。メモリ２０２は、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）およびフラッシュＲＯＭなどを有する。具体的には、例えば、フラッシュＲＯＭやＲＯＭが各種プログラムを記憶し、ＲＡＭがＣＰＵ２０１のワークエリアとして使用される。メモリ２０２に記憶されるプログラムは、ＣＰＵ２０１にロードされることで、コーディングされている処理をＣＰＵ２０１に実行させる。
【００３２】
Ｉ／Ｆ２０３は、通信回線を通じてネットワーク２１０に接続され、ネットワーク２１０を介して他のコンピュータに接続される。そして、Ｉ／Ｆ２０３は、ネットワーク２１０と内部のインターフェースを司り、他のコンピュータからのデータの入出力を制御する。Ｉ／Ｆ２０３には、例えば、モデムやＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）アダプタなどを採用することができる。
【００３３】
ディスクドライブ２０４は、ＣＰＵ２０１の制御にしたがってディスク２０５に対するデータのリード／ライトを制御する。ディスクドライブ２０４は、例えば、磁気ディスクドライブである。ディスク２０５は、ディスクドライブ２０４の制御で書き込まれたデータを記憶する不揮発メモリである。ディスク２０５は、例えば、磁気ディスク、光ディスクなどである。
【００３４】
情報処理装置１００は、上述した構成部のほか、例えば、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｒｉｖｅ）、半導体メモリ、キーボード、マウス、ディスプレイなどを有することにしてもよい。また、情報処理装置１００は、ディスクドライブ２０４およびディスク２０５の代わりに、ＳＳＤおよび半導体メモリなどを有していてもよい。
【００３５】
（実施の形態１にかかる情報処理装置１００の機能的構成例）
次に、図３を用いて、実施の形態１にかかる情報処理装置１００の機能的構成例について説明する。
【００３６】
図３は、実施の形態１にかかる情報処理装置１００の機能的構成例を示すブロック図である。情報処理装置１００は、特定部３０１と、分類部３０２と、算出部３０３と、選択部３０４と、生成部３０５と、出力部３０６とを含む。
【００３７】
特定部３０１〜出力部３０６は、制御部となる機能であり、例えば、図２に示したメモリ２０２、ディスク２０５に記憶されたプログラムをＣＰＵ２０１に実行させることにより、または、Ｉ／Ｆ２０３により、その機能を実現する。各機能部の処理結果は、例えば、図２に示したメモリ２０２、ディスク２０５などの記憶装置に記憶される。
【００３８】
特定部３０１は、ソフトウェアのプログラムコードのうち、第１変数に対して縮約演算する第１式についての計算を繰り返すループ箇所を特定する。プログラムコードとは、ソフトウェアの処理内容が記述されたコードである。プログラムコードは、例えば、ソースコードである。プログラムコードは、抽象構文木を示すコードであってもよい。第１式は、第１演算子により、複数の項や因数を第１変数に対して縮約演算する式である。ループ箇所は、例えば、ネスト構造の複数のループ文と、ループ本体とが記述された箇所である。
【００３９】
特定部３０１は、例えば、ソースコードのうち、第１変数「ｓ（ｉ，ｊ）」に対して縮約演算する第１式「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｊ）＊ｂ（ｋ，ｉ）」についての計算を繰り返すループ箇所を特定する。これにより、特定部３０１は、ソフトウェアの実行時の演算量を低減させることができる可能性があるループ箇所を特定することができる。
【００４０】
分類部３０２は、第１式についての計算を繰り返す条件に使用される変数を、第１式のうちの各部分式における第１種別の変数と、第１種別の変数とは異なる第２種別の変数とに分類する。部分式は、第１変数に対して縮約演算される単位部分式の一部である。単位部分式の一部は、単位部分式を「１＊単位部分式」として扱う場合には、単位部分式自体であってもよい。
【００４１】
第１種別の変数は、第１変数のインデックスに使用される変数、第１変数の初期化を行う式についての計算を繰り返す条件に使用される変数および部分式と単位部分式の残余の部分式とに共通してインデックスに使用される変数のいずれかと一致する変数である。以下の説明では、第１種別の変数を「パラメータ」と表記する場合がある。また、以下の説明では、第２種別の変数を「縮約可能変数」と表記する場合がある。
【００４２】
分類部３０２は、例えば、第１式についての計算を繰り返す条件に使用される変数「ｉ，ｊ，ｋ」を、第１式のうちの部分式「ｂ（ｋ，ｉ）」におけるパラメータと縮約可能変数とに分類する。分類部３０２は、具体的には、第１変数「ｓ（ｉ，ｊ）」のインデックスｉ、ｊを特定する。また、分類部３０２は、第１変数「ｓ（ｉ，ｊ）」の初期化を行う式についての計算を繰り返す条件に使用される変数ｉ，ｊを特定する。また、分類部３０２は、第１式のうちの部分式「ｂ（ｋ，ｉ）」と、第１式に対して縮約演算される単位部分式「ａ（ｉ，ｊ）＊ｂ（ｋ，ｉ）」の残余の部分式「ａ（ｉ，ｊ）」とに共通してインデックスに使用される変数ｉを特定する。
【００４３】
そして、分類部３０２は、特定した変数ｉ，ｊを、パラメータに分類する。また、分類部３０２は、特定されなかった変数ｋを、縮約可能変数に分類する。これにより、分類部３０２は、第１式のうちの部分式を基に、特定部３０１が特定したループ箇所を変換した場合に削減される演算量を算出する際に用いる情報を得ることができる。
【００４４】
算出部３０３は、第１式のうちの各部分式について、当該部分式を第２変数に対して縮約演算する第２式についての計算の種類および繰り返し回数を特定する。第２式は、部分式を第１演算子により第２変数に対して縮約演算する式である。また、算出部３０３は、第１式のうちの当該部分式が第２変数に置換された第３式についての計算の種類および繰り返し回数を特定する。そして、算出部３０３は、特定した種類および繰り返し回数に基づいて、第２式についての計算を繰り返す演算量、および、第３式についての計算を繰り返す演算量の合計と、ループ箇所の演算量との差分を算出する。
【００４５】
算出部３０３は、例えば、分類した第１種別の変数および第２種別の変数に基づいて、第１式のうちの各部分式について、当該部分式を第２変数に対して縮約演算する第２式についての計算の種類および繰り返し回数を特定する。また、算出部３０３は、分類した第１種別の変数および第２種別の変数に基づいて、第１式のうちの各部分式について、第１式のうちの当該部分式が第２変数に置換された第３式についての計算の種類および繰り返し回数を特定する。
【００４６】
そして、算出部３０３は、第２式について特定した種類ごとの演算子の数と、繰り返し回数とを乗算した値を、第２式についての計算を繰り返す演算量として算出する。また、算出部３０３は、第３式について特定した種類ごとの演算子の数と、繰り返し回数とを乗算した値を、第３式についての計算を繰り返す演算量として算出する。そして、算出部３０３は、第２式についての計算を繰り返す演算量および第３式についての計算を繰り返す演算量の合計と、ループ箇所の演算量との差分を算出する。
【００４７】
算出部３０３は、具体的には、パラメータ「ｉ，ｊ」と縮約可能変数「ｋ」のうち、第１式のうちの部分式「ｂ（ｋ，ｉ）」のインデックスになる変数「ｋ，ｉ」を特定する。次に、算出部３０３は、ループ箇所における変数「ｋ，ｉ」についての繰り返し回数を乗算した値「ｎ＾２」を、第２式についての繰り返し回数「ｎ＾２」として算出する。
【００４８】
また、算出部３０３は、縮約可能変数「ｋ」が、第１式のうちの部分式「ｂ（ｋ，ｉ）」のインデックスになる変数「ｋ，ｉ」に含まれれば、第２式についての計算の種類「＋」を特定する。次に、算出部３０３は、第１式のうちの部分式「ｂ（ｋ，ｉ）」に演算子が含まれれば当該演算子を第２式についての計算の種類として特定し、演算子が含まれなければ第２式についての計算の種類を特定しない。
【００４９】
また、算出部３０３は、パラメータ「ｉ，ｊ」と縮約可能変数「ｋ」のうち、残余の部分式「ａ（ｉ，ｊ）」のインデックスになる変数「ｉ，ｊ」を特定する。次に、算出部３０３は、ループ箇所における変数「ｉ，ｊ」についての繰り返し回数を乗算した値「ｎ＾２」を、第３式についての繰り返し回数「ｎ＾２」として算出する。
【００５０】
また、算出部３０３は、残余の部分式「ａ（ｉ，ｊ）」に演算子が含まれれば当該演算子を第３式についての計算の種類として特定し、演算子が含まれなければ第３式についての計算の種類を特定しない。また、算出部３０３は、第２変数と残余の部分式「ａ（ｉ，ｊ）」を結合する際に用いられる演算子「＊」を特定する。また、算出部３０３は、結合した結果を縮約演算する際に用いられる演算子「＋」を特定する。
【００５１】
そして、算出部３０３は、第２式について特定した種類ごとの演算子の数「１」と、繰り返し回数とを乗算した値「ｎ＾２」を、第２式についての計算を繰り返す演算量「ｎ＾２」として算出する。また、算出部３０３は、第３式について特定した種類ごとの演算子の数「２」と、繰り返し回数とを乗算した値「２ｎ＾２」を、第３式についての計算を繰り返す演算量として算出する。
【００５２】
そして、算出部３０３は、ループ箇所の演算量「２ｎ＾３」を算出して、第２式についての計算を繰り返す演算量および第３式についての計算を繰り返す演算量の合計と、ループ箇所の演算量との差分「２ｎ＾３−３ｎ＾２」を算出する。これにより、算出部３０３は、プログラムコードを変換した場合に削減される演算量を算出することができる。
【００５３】
ここでは、演算子の種類が「＋」でも「＊」でも演算量が同一である場合について説明したが、これに限らない。例えば、算出部３０３は、演算子の種類によって演算量が異なる場合には、演算子の種類に応じて重み付けを行って演算量を算出してもよい。また、算出部３０３は、上述した算出方法以外を用いて、プログラムコードを変換した場合に削減される演算量を算出してもよい。また、算出部３０３は、削減される演算量の代わりに、削減される演算量と関連する指標値を算出してもよい。
【００５４】
選択部３０４は、算出部３０３が算出した差分に基づいて、第１式のうちのいずれかの部分式を選択する。選択部３０４は、例えば、算出部３０３が算出した差分が最も大きい部分式を選択する。これにより、選択部３０４は、ソフトウェアの実行時の演算量が最も低減されるように、プログラムコードを変換する場合に用いる部分式を選択することができる。
【００５５】
生成部３０５は、第１式のうちの部分式を第２変数に対して縮約演算する第２式についての計算を繰り返す第１コード、および、第１式のうちの部分式が第２変数に置換された第３式についての計算を繰り返す第２コードを生成する。生成部３０５は、例えば、選択したいずれかの部分式について第１コードおよび第２コードを生成する。
【００５６】
生成部３０５は、具体的には、第１式のうちの各部分式について、当該部分式を縮約演算する第２式についての計算の繰り返し条件に使用する変数および繰り返し回数を特定する。また、生成部３０５は、当該部分式が置換された第３式についての計算の繰り返し条件に使用する変数および繰り返し回数を特定する。生成部３０５は、特定した変数および繰り返し回数に基づいて、ループ文を用いて第１コードを生成し、ループ文を用いて第２コードを生成する。
【００５７】
生成部３０５は、より具体的には、分類した第１種別の変数および第２種別の変数に基づいて、第１式のうちの各部分式について、当該部分式を縮約演算する第２式についての計算の繰り返し条件に使用する変数および繰り返し回数を特定する。また、生成部３０５は、当該部分式が置換された第３式についての計算の繰り返し条件に使用する変数および繰り返し回数を特定する。生成部３０５は、特定した変数および繰り返し回数に基づいて、ループ文を用いて第１コードを生成し、ループ文を用いて第２コードを生成する。これにより、生成部３０５は、ソフトウェアの実行時の演算量を低減させることができるプログラムコードを生成することができる。
【００５８】
出力部３０６は、プログラムコードのうちのループ箇所を第１コードおよび第２コードに変換した変換後のプログラムコードを出力する。出力部３０６は、例えば、変換後のプログラムコードを、ディスプレイに表示し、プリンタに印刷出力し、Ｉ／Ｆ２０３によって外部装置へ送信し、または、メモリ２０２やディスク２０５などの記憶領域に記憶する。これにより、出力部３０６は、コンパイラに、変換後のプログラムコードを提供することができる。
【００５９】
以下、図４〜図１８を用いて、実施の形態１にかかる情報処理装置１００の動作例について説明する。
【００６０】
（ソースコード４００の一例）
図４は、ソースコード４００の一例を示す説明図である。ソースコード４００は、例えば、ＦＯＲＴＲＡＮ、Ｃ、ＢＡＳＩＣなどのプログラミング言語を用いて、コンピュータに実行させる処理の内容が記述されたテキストデータである。
【００６１】
図４の例では、ソースコード４００の１，１２行目には、ループ文「ＤＯ  ｉ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード４００の２〜１１行目には、ループ文「ＤＯ  ｉ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード４００の１〜１２行目には、変数ｉを１から開始して変数ｉがｎになるまでループ本体内の処理を繰り返し実行するループ処理の内容が記述される。
【００６２】
ソースコード４００の２，１１行目には、ループ文「ＤＯ  ｊ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード４００の３〜１０行目には、ループ文「ＤＯ  ｊ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード４００の２〜１１行目には、変数ｊを１から開始して変数ｊがｎになるまでループ本体内の処理を繰り返し実行するループ処理の内容が記述される。
【００６３】
ソースコード４００の３行目には、代入文「ｓ（ｉ，ｊ）＝０」が記述される。これにより、ソースコード４００の３行目には、配列変数ｓ（ｉ，ｊ）の値に、数値「０」を代入する初期化処理の内容が記述される。
【００６４】
ソースコード４００の４，１０行目には、ループ文「ＤＯ  ｋ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード４００の５〜９行目には、ループ文「ＤＯ  ｋ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード４００の４〜１０行目には、変数ｋを１から開始して変数ｋがｎになるまでループ本体内の処理を繰り返し実行するループ処理の内容が記述される。
【００６５】
ソースコード４００の５，９行目には、ループ文「ＤＯ  ｌ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード４００の６〜８行目には、ループ文「ＤＯ  ｌ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード４００の５〜９行目には、変数ｌを１から開始して変数ｌがｎになるまでループ本体内の処理を繰り返し実行するループ処理が記述される。
【００６６】
ソースコード４００の６，８行目には、ループ文「ＤＯ  ｍ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード４００の７行目には、ループ文「ＤＯ  ｍ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード４００の６〜８行目には、変数ｍを１から開始して変数ｍがｎになるまでループ本体内の処理を繰り返し実行するループ処理が記述される。
【００６７】
ソースコード４００の７行目には、代入文「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」が記述される。これにより、ソースコード４００の７行目には、配列変数ｓ（ｉ，ｊ）の値に、配列変数ｓ（ｉ，ｊ）＋配列変数ａ（ｉ，ｋ，ｍ，ｌ）＊配列変数ｗ（ｋ，ｌ）＊配列変数ｖ（ｊ，ｍ）の値を代入する代入処理が記述される。
【００６８】
このように、ソースコード４００の１〜１２行目は、入れ子構造になった複数のループ文の集まりが記述された多重ループ箇所である。また、ソースコード４００の１〜３，１１，１２行目は、変数ｉ，ｊを変化させ、縮約演算が行われる配列変数ｓ（ｉ，ｊ）を切り替え、切り替えた配列変数ｓ（ｉ，ｊ）を初期化する、入れ子構造になったループ文の集まりが記述されたループ箇所である。以下の説明では、縮約演算が行われる配列変数を切り替えて初期化するループ箇所を「初期化ループ箇所」と表記する場合がある。
【００６９】
また、ソースコード４００の４〜１０行目は、初期化された配列変数ｓ（ｉ，ｊ）に対する代入演算を繰り返すことによって、初期化された配列変数ｓ（ｉ，ｊ）に対する縮約演算を行う、入れ子構造になったループ文の集まりが記述されたループ箇所である。以下の説明では、縮約演算を行うループ箇所を「縮約演算ループ箇所」と表記する場合がある。
【００７０】
（多重ループを検出する一例）
図５は、多重ループを検出する一例を示す説明図である。図５において、情報処理装置１００は、ソースコード４００に基づいて抽象構文木（Ａｂｓｔｒａｃｔ  Ｓｙｎｔａｘ  Ｔｒｅｅ）、変数表、関数表などを生成する。そして、情報処理装置１００は、生成した抽象構文木に基づいて、多重ループ箇所を検出する。以下の説明では、抽象構文木を「ＡＳＴ」と表記する場合がある。
【００７１】
情報処理装置１００は、例えば、ソースコード４００内の関数や制御構文、関数や制御構文の引数、関数内の命令文、制御構文の分岐先の命令文、命令文内の変数や演算子などを属性とするノードを生成する。ノードには、例えば、ループ本体（Ｂｏｄｙ）を属性とし、ループ本体内の命令文を属性とする子ノードが接続されたノードがある。また、ノードには、例えば、ループ文の繰り返し条件（ｃｏｎｄ）を属性とし、繰り返し条件に使用される変数を属性とする子ノードが接続されたノードがある。図５の例では、説明の簡略化のため、ｃｏｎｄの子ノードや、変数のインデックスを属性とするノードなどについて、図示を省略する。
【００７２】
次に、情報処理装置１００は、ソースコード４００に記述された処理の内容にしたがって、生成したノード間の接続関係を特定して、生成したノード間を接続することにより、抽象構文木を生成する。そして、情報処理装置１００は、ループ文を属性とするノードから、ループ本体を属性とするノードを経由して、ループ文を属性とするノードを検索することにより、多重ループ箇所を検出する。
【００７３】
（アドレスを割り当てる一例）
図６は、アドレスを割り当てる一例を示す説明図である。図６において、情報処理装置１００は、検出した多重ループ箇所に含まれる命令文や演算子などに対応するＡＳＴのノードに、多重ループ箇所の複数のループ文の入れ子構造に対応する階層構造のアドレスを対応付けて記憶する。
【００７４】
情報処理装置１００は、例えば、ソースコード４００の１行目に記述されたループ文「ＤＯ  ｉ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」に対応するノードに、アドレス（１）を対応付けて記憶する。また、情報処理装置１００は、ソースコード４００の２行目に記述されたループ文「ＤＯ  ｊ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」に対応するノードに、アドレス（１，１）を対応付けて記憶する。また、情報処理装置１００は、３行目に記述された代入文「ｓ（ｉ，ｊ）＝０」に対応するノードに、アドレス（１，１）（１）を対応付けて記憶する。
【００７５】
また、情報処理装置１００は、７行目に用いられた演算子「＝」に対応するノードに、アドレス（１，１，１，１，１）（１，１）を対応付ける。また、情報処理装置１００は、７行目に用いられた演算子「＋」に対応するノードに、アドレス（１，１，１，１，１）（１，１，２）を対応付ける。同様に、情報処理装置１００は、ソースコード４００に記述された命令文や演算子などに対応するＡＳＴのノードに、アドレスを対応付けて記憶する。
【００７６】
（縮約演算ループ箇所を検出する一例）
図７および図８は、縮約演算ループ箇所を検出する一例を示す説明図である。図７において、情報処理装置１００は、代入文を記憶するリスト１を生成する。そして、情報処理装置１００は、検出した多重ループ箇所に含まれる代入文を抽出して、抽出した代入文を左辺の変数ごとに分類してリスト１に追加することにより、リスト１を更新する。
【００７７】
次に、情報処理装置１００は、縮約演算を行う式に対応する代入文を記憶するリスト２を生成し、抽出した代入文のうち、縮約演算の形式「ｒ＝ｒ＋（ｒを含まない式）」に対応する代入文を特定して、特定した代入文をリスト２に追加して、リスト２を更新する。以下の説明では、縮約演算を行う式を「縮約演算式」と表記する場合がある。
【００７８】
そして、情報処理装置１００は、初期化を行う式に対応する代入文を記憶するリスト３を生成して、リスト１に含まれ、かつリスト２に含まれない代入文をリスト３に追加して、リスト３を更新する。以下の説明では、初期化を行う式を「初期化式」と表記する場合がある。
【００７９】
情報処理装置１００は、例えば、アドレス（１，１）（１）が対応付けられた代入文「ｓ（ｉ，ｊ）＝０」をリスト１に追加する。また、情報処理装置１００は、アドレス（１，１，１，１，１）（１）が対応付けられた代入文「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」をリスト１に追加する。
【００８０】
次に、情報処理装置１００は、アドレス（１，１，１，１，１）（１）が対応付けられた代入文「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」をリスト２に追加する。そして、情報処理装置１００は、アドレス（１，１）（１）が対応付けられた代入文「ｓ（ｉ，ｊ）＝０」をリスト３に追加する。
【００８１】
図８において、情報処理装置１００は、同一の変数に対する初期化式と縮約演算式とを対応付けて記憶するリスト４を生成し、リスト２とリスト３との要素を対応付けて追加して、リスト４を更新する。次に、情報処理装置１００は、リスト４に記憶された、リスト２のアドレスのうちで、リスト３のアドレスに一致する要素および一致しない要素を特定する。そして、情報処理装置１００は、特定した要素に基づいて、多重ループ箇所のうちで１つのスカラー変数に対する縮約演算が行われる縮約演算ループ箇所を特定する。
【００８２】
情報処理装置１００は、例えば、リスト２のアドレス（１，１，１，１，１）のうちでリスト３のアドレス（１，１）に一致する要素が、リスト２のアドレスの１番目と２番目の要素であることを特定する。そして、情報処理装置１００は、リスト２のアドレスの１番目と２番目の要素に対応するループ文が、縮約演算が行われるスカラー変数を切り替えるループ文の集まりであって、スカラー変数を初期化する初期化ループ箇所であると特定する。
【００８３】
一方で、情報処理装置１００は、リスト２のアドレス（１，１，１，１，１）のうちでリスト３のアドレス（１，１）に一致しない要素が、リスト２のアドレスの３〜５番目の要素であることを特定する。そして、情報処理装置１００は、リスト２のアドレスの３〜５番目の要素に対応するループ文が、初期化されたスカラー変数に対する縮約演算が行われるループ文の集まりであって、縮約演算が行われる縮約演算ループ箇所であると特定する。
【００８４】
（部分式を抽出する一例）
図９〜図１４は、部分式を抽出する一例を示す説明図である。図９において、情報処理装置１００は、代入文に対応付けられたアドレスと、代入文に含まれる部分式とを対応付けて記憶する、部分式のリスト５を生成する。
【００８５】
（９−１）情報処理装置１００は、抽象構文木のうち、縮約演算に用いられる代入文「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」に対応する部分木を抽出する。
【００８６】
（９−２）情報処理装置１００は、抽出した部分木の根ノードを参照する。情報処理装置１００は、根ノードの属性となる演算子が「＝」であるため、縮約演算式の右辺に対応する子ノードを参照する。情報処理装置１００は、子ノードの属性となる演算子が「＋」であるため、対象演算子として演算子「＋」を設定する。
【００８７】
（９−３）情報処理装置１００は、縮約演算式の右辺「ｓ（ｉ，ｊ）＋ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」を対象部分式として設定する。情報処理装置１００は、縮約演算式の左辺「ｓ（ｉ，ｊ）」を足し込み先部分式として設定する。
【００８８】
（９−４）情報処理装置１００は、対象部分式に対応する部分木の根ノードを参照する。情報処理装置１００は、根ノードの属性となる演算子が「＋」であって対象演算子「＋」と一致するため、いずれか一方の子ノードを選択する。情報処理装置１００は、選択した子ノードが根となる部分木に対応する式「ｓ（ｉ，ｊ）」を対象部分式として設定する。
【００８９】
（９−５）情報処理装置１００は、対象部分式「ｓ（ｉ，ｊ）」が、足し込み先部分式と一致するため、（９−４）で未選択の他方の子ノードを選択する。情報処理装置１００は、選択した子ノードが根となる部分木に対応する式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」を対象部分式として設定する。
【００９０】
（９−６）情報処理装置１００は、対象部分式に対応する部分木の根ノードを参照する。情報処理装置１００は、根ノードの属性となる演算子が「＊」であって対象演算子「＋」と一致せず、かつ、対象部分式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」が足し込み先部分式と一致しないため、リスト５に対象部分式を追加する。
【００９１】
図１０のように、リスト５は、例えば、対象部分式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」と、縮約演算式に対応するアドレス（１，１，１，１，１）（１）とを対応付けたレコード５−１を記憶する。
【００９２】
図１１において、情報処理装置１００は、代入文に対応付けられたアドレスと、代入文に含まれる部分式を２つの部分式にさらに分割して得られた分割部分式の組み合わせとを対応付けて記憶する、分割部分式のリスト６を生成して、リスト６を更新する。リスト６の記憶内容は、図１４に後述する。
【００９３】
（１１−１）情報処理装置１００は、リスト５から部分式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」を抽出して、現在の部分式として設定する。情報処理装置１００は、現在の部分式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」と数値「１」との組み合わせをリスト６に追加して、リスト６を更新する。
【００９４】
ここで、情報処理装置１００は、代入文に対応付けられたアドレスと、代入文に含まれる部分式とを対応付けて記憶する、部分式のリスト５’を生成する。
【００９５】
（１１−２）情報処理装置１００は、現在の部分式に対応する部分木の根ノードを参照する。情報処理装置１００は、根ノードの属性となる演算子が２項演算子「＊」であるため、対象演算子として演算子「＊」を設定する。
【００９６】
（１１−３）情報処理装置１００は、現在の部分式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」を対象部分式として設定する。情報処理装置１００は、「ＮＵＬＬ」を足し込み先部分式として設定する。
【００９７】
（１１−４）情報処理装置１００は、対象部分式に対応する部分木の根ノードを参照する。情報処理装置１００は、根ノードの属性となる演算子が「＊」であって対象演算子「＊」と一致するため、いずれか一方の子ノードを選択する。情報処理装置１００は、選択した子ノードが根となる部分木に対応する式「ａ（ｉ，ｋ，ｍ，ｌ）」を対象部分式として設定する。
【００９８】
（１１−５）情報処理装置１００は、対象部分式「ａ（ｉ，ｋ，ｍ，ｌ）」に対応する部分木の根ノードを参照する。情報処理装置１００は、根ノードの属性が演算子ではなく、かつ、対象部分式「ａ（ｉ，ｋ，ｍ，ｌ）」が足し込み先部分式と一致しないため、リスト５’に対象部分式を追加する。
【００９９】
（１１−６）情報処理装置１００は、（１１−４）で未選択の他方の子ノードを選択する。情報処理装置１００は、選択した子ノードが根となる部分木に対応する式「ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」を対象部分式として設定する。
【０１００】
（１１−７）情報処理装置１００は、対象部分式に対応する部分木の根ノードを参照する。情報処理装置１００は、根ノードの属性となる演算子が「＊」であって対象演算子「＊」と一致するため、いずれか一方の子ノードを選択する。情報処理装置１００は、選択した子ノードが根となる部分木に対応する式「ｗ（ｋ，ｌ）」を対象部分式として設定する。
【０１０１】
（１１−８）情報処理装置１００は、対象部分式に対応する部分木の根ノードを参照する。情報処理装置１００は、根ノードの属性が演算子ではなく、かつ、対象部分式「ｗ（ｋ，ｌ）」が足し込み先部分式と一致しないため、リスト５’に対象部分式を追加する。
【０１０２】
（１１−９）情報処理装置１００は、（１１−７）で未選択の他方の子ノードを選択する。情報処理装置１００は、選択した子ノードが根となる部分木に対応する式「ｖ（ｊ，ｍ）」を対象部分式として設定する。
【０１０３】
（１１−１０）情報処理装置１００は、対象部分式に対応する部分木の根ノードを参照する。情報処理装置１００は、根ノードの属性が演算子ではなく、かつ、対象部分式「ｖ（ｊ，ｍ）」が足し込み先部分式と一致しないため、リスト５’に対象部分式を追加する。
【０１０４】
図１２のように、リスト５’は、例えば、縮約演算式に対応するアドレス（１，１，１，１，１）（１）と、部分式「ａ（ｉ，ｋ，ｍ，ｌ）」とを対応付けたレコード５’−１を記憶する。また、リスト５’は、縮約演算式に対応するアドレス（１，１，１，１，１）（１）と、部分式「ｗ（ｋ，ｌ）」とを対応付けたレコード５’−２を記憶する。リスト５’は、縮約演算式に対応するアドレス（１，１，１，１，１）（１）と、部分式「ｖ（ｊ，ｍ）」とを対応付けたレコード５’−３を記憶する。
【０１０５】
図１３において、情報処理装置１００は、リスト５に記憶した部分式を２つに分割して得られる分割部分式を、リスト５’に記憶した部分式を組み合わせることにより生成して、生成した分割部分式をリスト６に追加して、リスト６を更新する。以下の説明では、部分式を２つに分割して得られる分割部分式を「分割部分式Ａおよび分割部分式Ｂ」と表記する場合がある。
【０１０６】
（１３−１）情報処理装置１００は、リスト５’に記憶した部分式を組み合わせるパターンを示す変数ｂを用意し、変数ｂに「１（０ｂ０００００００１）」を設定する。括弧内は２進数８ビットでの表記である。変数ｂの末尾からのビットの番号は、リスト５’の先頭からのレコードの番号に対応する。例えば、変数ｂの末尾から１番目のビットは、リスト５’の先頭から１番目のレコードに対応する。
【０１０７】
情報処理装置１００は、変数ｂのうちのビット「０」に対応するレコードから、部分式「ｗ（ｋ，ｌ）」と部分式「ｖ（ｊ，ｍ）」とを抽出する。情報処理装置１００は、抽出した部分式「ｗ（ｋ，ｌ）」と部分式「ｖ（ｊ，ｍ）」とを対象演算子「＊」で接続した部分式「ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」を、一方の分割部分式として生成する。
【０１０８】
また、情報処理装置１００は、変数ｂのうちのビット「１」に対応するレコードから、部分式「ａ（ｉ，ｋ，ｍ，ｌ）」を抽出する。情報処理装置１００は、抽出した部分式「ａ（ｉ，ｋ，ｍ，ｌ）」を、他方の分割部分式「ａ（ｉ，ｋ，ｍ，ｌ）」として生成する。情報処理装置１００は、生成した一方の分割部分式と他方の分割部分式との組み合わせを、リスト６に追加して、リスト６を更新する。
【０１０９】
（１３−２）情報処理装置１００は、ｂをインクリメントし、ｂに「２（０ｂ００００００１０）」を設定する。情報処理装置１００は、変数ｂのうちのビット「０」に対応するレコードから、部分式「ａ（ｉ，ｋ，ｍ，ｌ）」と部分式「ｖ（ｊ，ｍ）」とを抽出する。情報処理装置１００は、抽出した部分式「ａ（ｉ，ｋ，ｍ，ｌ）」と部分式「ｖ（ｊ，ｍ）」とを対象演算子「＊」で接続した部分式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｖ（ｊ，ｍ）」を、一方の分割部分式として生成する。
【０１１０】
また、情報処理装置１００は、変数ｂのうちのビット「１」に対応するレコードから、部分式「ｗ（ｋ，ｌ）」を抽出する。情報処理装置１００は、抽出した部分式「ｗ（ｋ，ｌ）」を、他方の分割部分式「ｗ（ｋ，ｌ）」として生成する。情報処理装置１００は、生成した一方の分割部分式と他方の分割部分式との組み合わせを、リスト６に追加して、リスト６を更新する。
【０１１１】
（１３−３）情報処理装置１００は、ｂをインクリメントし、ｂに「３（０ｂ００００００１１）」を設定する。情報処理装置１００は、変数ｂのうちのビット「０」に対応するレコードから、部分式「ｖ（ｊ，ｍ）」を抽出する。情報処理装置１００は、抽出した部分式「ｖ（ｊ，ｍ）」を、一方の分割部分式として生成する。
【０１１２】
また、情報処理装置１００は、変数ｂのうちのビット「１」に対応するレコードから、部分式「ａ（ｉ，ｋ，ｍ，ｌ）」と部分式「ｗ（ｋ，ｌ）」とを抽出する。情報処理装置１００は、抽出した部分式「ａ（ｉ，ｋ，ｍ，ｌ）」と部分式「ｗ（ｋ，ｌ）」とを対象演算子「＊」で接続した部分式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）」を他方の分割部分式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）」として生成する。情報処理装置１００は、生成した一方の分割部分式と他方の分割部分式との組み合わせを、リスト６に追加して、リスト６を更新する。
【０１１３】
図１４のように、リスト６は、例えば、アドレス（１，１，１，１，１）（１）と、分割部分式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」および「１」の組み合わせと、組み合わせのＩＤ「０」とを対応付けたレコード６−１を記憶する。また、リスト６は、アドレス（１，１，１，１，１）（１）と、分割部分式「ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」および「ａ（ｉ，ｋ，ｍ，ｌ）」の組み合わせと、組み合わせのＩＤ「１」とを対応付けたレコード６−２を記憶する。
【０１１４】
また、リスト６は、アドレス（１，１，１，１，１）（１）と、分割部分式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｖ（ｊ，ｍ）」および分割部分式「ｗ（ｋ，ｌ）」の組み合わせと、組み合わせのＩＤ「２」とを対応付けたレコード６−３を記憶する。また、リスト６は、アドレス（１，１，１，１，１）（１）と、分割部分式「ｖ（ｊ，ｍ）」および分割部分式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）」の組み合わせと、組み合わせのＩＤ「３」とを対応付けたレコード６−４を記憶する。
【０１１５】
（スカラー変数を分類する一例）
図１５は、スカラー変数を分類する一例を示す説明図である。図１５において、情報処理装置１００は、リスト６のレコードごとに、縮約演算式においてインデックスに使用されるスカラー変数を、パラメータと縮約可能変数とに分類して、分類結果をリスト７に記憶する。
【０１１６】
情報処理装置１００は、例えば、縮約演算式の左辺が配列変数であれば、左辺の配列変数のインデックスに使用されるスカラー変数を、パラメータとして設定する。情報処理装置１００は、スカラー変数を初期化する初期化ループ箇所におけるループ文に使用されるスカラー変数を、パラメータとして設定する。
【０１１７】
情報処理装置１００は、リスト６のレコードの分割部分式の組み合わせの両方において共通してインデックスに使用されるスカラー変数を、パラメータとして設定する。情報処理装置１００は、リスト６のレコードの分割部分式の組み合わせにおいてインデックスに使用されるスカラー変数のうち、パラメータに設定されていないスカラー変数を、縮約可能変数に設定する。
【０１１８】
情報処理装置１００は、レコード６−１について、スカラー変数ｉ，ｊをパラメータとして設定する。情報処理装置１００は、レコード６−１について、スカラー変数ｋ，ｌ，ｍを、縮約可能変数として設定する。情報処理装置１００は、レコード６−１の記憶内容と、パラメータと、縮約可能変数とを対応付けたレコード７−１を生成して、リスト７に追加して、リスト７を更新する。
【０１１９】
情報処理装置１００は、レコード６−２について、スカラー変数ｉ，ｊ，ｍをパラメータとして設定する。情報処理装置１００は、レコード６−２について、スカラー変数ｋ，ｌを、縮約可能変数として設定する。情報処理装置１００は、レコード６−２の記憶内容と、パラメータと、縮約可能変数とを対応付けたレコード７−２を生成して、リスト７に追加して、リスト７を更新する。
【０１２０】
情報処理装置１００は、レコード６−３について、スカラー変数ｉ，ｊ，ｋ，ｌ，ｍをパラメータとして設定する。情報処理装置１００は、レコード６−３について、縮約可能変数を設定しない。情報処理装置１００は、レコード６−３の記憶内容と、パラメータを対応付けたレコード７−３を生成して、リスト７に追加して、リスト７を更新する。
【０１２１】
情報処理装置１００は、レコード６−４について、スカラー変数ｉ，ｊ，ｋ，ｌをパラメータとして設定する。情報処理装置１００は、レコード６−４について、スカラー変数ｍを、縮約可能変数として設定する。情報処理装置１００は、レコード６−４の記憶内容と、パラメータと、縮約可能変数とを対応付けたレコード７−４を生成して、リスト７に追加して、リスト７を更新する。
【０１２２】
図１５のように、リスト７は、例えば、リスト６のレコード６−１の記憶内容と、パラメータ「ｉ，ｊ」と、縮約可能変数「ｋ，ｌ，ｍ」とを対応付けたレコード７−１を記憶する。また、リスト７は、リスト６のレコード６−２の記憶内容と、パラメータ「ｉ，ｊ，ｍ」と、縮約可能変数「ｋ，ｌ」とを対応付けたレコード７−２を記憶する。
【０１２３】
また、リスト７は、リスト６のレコード６−３の記憶内容と、パラメータ「ｉ，ｊ，ｋ，ｌ，ｍ」と、縮約可能変数「なし」とを対応付けたレコード７−３を記憶する。また、リスト７は、リスト６のレコード６−４の記憶内容と、パラメータ「ｉ，ｊ，ｋ，ｌ」と、縮約可能変数「ｍ」とを対応付けたレコード７−４を記憶する。
【０１２４】
（削減される演算量を算出する一例）
図１６および図１７は、削減される演算量を算出する一例を示す説明図である。図１６において、情報処理装置１００は、それぞれの分割部分式を別々に計算した場合に、ループ処理全体として削減される演算量を算出して、リスト８に記憶する。以下の説明では、ループ処理全体として削減される演算量を「削減量」と表記する場合がある。
【０１２５】
情報処理装置１００は、例えば、縮約演算式の演算を多重ループ箇所において行う場合にかかる演算量を算出する。以下の説明では、多重ループ箇所において行う場合にかかる演算量を「元の演算量」と表記する場合がある。
【０１２６】
そして、情報処理装置１００は、リスト７のレコードごとに、縮約演算式から分割部分式を抽出し、抽出した分割部分式の演算と、抽出した分割部分式の演算結果を用いた縮約演算式の演算とを、別々のループ箇所において行う場合にかかる演算量を算出する。以下の説明では、別々のループ箇所において行う場合にかかる演算量を「ループ分割後の演算量」と表記する場合がある。最後に、情報処理装置１００は、元の演算量からループ分割後の演算量を減算した差分を、削減量として算出する。
【０１２７】
図１６において、情報処理装置１００は、リスト７のレコード７−１から、分割部分式「ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」を抽出して、対象分割部分式として設定する。情報処理装置１００は、対象分割部分式に縮約可能変数が含まれるため、対象分割部分式についての縮約演算に使用される演算子「＋」を対象演算子に追加して、演算子「＋」の数として「１」を設定する。また、情報処理装置１００は、対象分割部分式に含まれる演算子「＊」を対象演算子に追加して、演算子「＊」の数として「２」を設定する。
【０１２８】
情報処理装置１００は、繰り返し総数に１を設定する。情報処理装置１００は、縮約演算式においてインデックスに使用されるスカラー変数「ｉ，ｊ，ｋ，ｌ，ｍ」のうちで、対象分割部分式に使用されるスカラー変数「ｉ，ｊ，ｋ，ｌ，ｍ」を特定する。情報処理装置１００は、繰り返し総数に、スカラー変数「ｉ，ｊ，ｋ，ｌ，ｍ」のそれぞれのスカラー変数の繰り返し回数を乗算することにより、繰り返し総数に「ｎ＾５」を設定する。
【０１２９】
情報処理装置１００は、「繰り返し総数＝ｎ＾５」を、演算単位として設定する。情報処理装置１００は、それぞれの対象演算子の数に演算単位を乗算した値「３ｎ＾５」を、ループ分割後の演算量のうちの対象分割部分式についての演算量として設定する。
【０１３０】
情報処理装置１００は、リスト７のレコード７−１から、分割部分式「１」を抽出して、対象分割部分式として設定する。対象分割部分式に縮約可能変数が含まれず、対象分割部分式についての縮約演算に使用される演算子がないため、対象演算子の数はカウントされない。対象分割部分式に含まれる演算子がないため、対象演算子の数はカウントされない。
【０１３１】
情報処理装置１００は、繰り返し総数に１を設定する。情報処理装置１００は、対象分割部分式に使用されるスカラー変数がないため、繰り返し総数を「１」のままにする。情報処理装置１００は、「繰り返し総数＝１」を、演算単位として設定する。情報処理装置１００は、それぞれの対象演算子の数に演算単位を乗算した値「０」を、ループ分割後の演算量のうちの対象分割部分式についての演算量として設定する。
【０１３２】
情報処理装置１００は、リスト７のレコード７−１の分割部分式の組み合わせを結合し、縮約演算式を実現する際に使用される演算子を特定し、演算子の種類ごとに演算子の数をカウントする。ここで、情報処理装置１００は、分割部分式の組み合わせを結合する演算子「＊」の数として「１」を設定する。また、情報処理装置１００は、結合した対象分割部分式についての縮約演算に使用される演算子「＋」の数として「１」を設定する。
【０１３３】
情報処理装置１００は、結合単位に１を設定する。情報処理装置１００は、リスト７のレコード７−１のパラメータ「ｉ，ｊ」を特定する。情報処理装置１００は、結合単位に、パラメータ「ｉ，ｊ」のそれぞれのパラメータの繰り返し回数を乗算することにより、結合単位に「ｎ＾２」を設定する。
【０１３４】
情報処理装置１００は、それぞれの演算子の数に結合単位を乗算した値「２ｎ＾２」を、ループ分割後の演算量のうち、分割部分式の組み合わせの結合と、結合した結果についての縮約演算とにかかる演算量として設定する。以下の説明では、分割部分式の組み合わせの結合と、結合した結果についての縮約演算とにかかる演算量をまとめて「結合についての演算量」と表記する場合がある。また、情報処理装置１００は、スカラー変数「ｉ，ｊ，ｋ，ｌ，ｍ」のそれぞれのスカラー変数の繰り返し回数を乗算することにより、元の演算量として「ｎ＾５」を設定する。
【０１３５】
図１７において、情報処理装置１００は、元の演算量から、リスト８の各レコードの分割部分式についてのループ分割後の演算量を減算した差分を算出する。ループ分割後の演算量は、対象分割部分式についての演算量と、結合についての演算量との合計である。次に、情報処理装置１００は、算出した差分を、削減量としてリスト９に記憶する。そして、情報処理装置１００は、リスト９のレコードのうちで削減量が最大のレコードを取得する。その後、情報処理装置１００は、取得したレコードに記憶された分割部分式の組み合わせを、ループ最適化する部分式として決定する。
【０１３６】
（ソースコード４００を最適化する一例）
図１８は、ソースコード４００を最適化する一例を示す説明図である。図１８の例は、ソースコード４００を最適化して得られたソースコード１８００の一例である。
【０１３７】
図１８の例では、ソースコード１８００の１，１０行目には、ループ文「ＤＯ  ｉ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード１８００の２〜９行目には、ループ文「ＤＯ  ｉ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード１８００の１〜１０行目には、変数ｉを１から開始して変数ｉがｎになるまでループ本体内の処理を繰り返し実行するループ処理の内容が記述される。
【０１３８】
ソースコード１８００の２，９行目には、ループ文「ＤＯ  ｍ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード１８００の３〜８行目には、ループ文「ＤＯ  ｍ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード１８００の２〜９行目には、変数ｍを１から開始して変数ｍがｎになるまでループ本体内の処理を繰り返し実行するループ処理の内容が記述される。
【０１３９】
ソースコード１８００の３行目には、代入文「ｔ（ｉ，ｍ）＝０」が記述される。これにより、ソースコード１８００の３行目には、配列変数ｔ（ｉ，ｍ）の値に、数値「０」を代入する初期化処理の内容が記述される。
【０１４０】
ソースコード１８００の４，８行目には、ループ文「ＤＯ  ｋ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード１８００の５〜７行目には、ループ文「ＤＯ  ｋ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード１８００の４〜８行目には、変数ｋを１から開始して変数ｋがｎになるまでループ本体内の処理を繰り返し実行するループ処理の内容が記述される。
【０１４１】
ソースコード１８００の５，７行目には、ループ文「ＤＯ  ｌ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード１８００の６行目には、ループ文「ＤＯ  ｌ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード１８００の５〜７行目には、変数ｌを１から開始して変数ｌがｎになるまでループ本体内の処理を繰り返し実行するループ処理が記述される。
【０１４２】
ソースコード１８００の６行目には、代入文「ｔ（ｉ，ｍ）＝ｔ（ｉ，ｍ）＋ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）」が記述される。これにより、ソースコード１８００の６行目には、配列変数ｔ（ｉ，ｍ）の値に、配列変数ｔ（ｉ，ｍ）＋配列変数ａ（ｉ，ｋ，ｍ，ｌ）＊配列変数ｗ（ｋ，ｌ）の値を代入する代入処理が記述される。
【０１４３】
このように、ソースコード１８００の１〜１０行目は、入れ子構造になった複数のループ文の集まりが記述された多重ループ箇所である。また、ソースコード１８００の１〜３，９，１０行目は、変数ｉ，ｍを変化させ、縮約演算が行われる配列変数ｔ（ｉ，ｍ）を切り替え、切り替えた配列変数ｔ（ｉ，ｍ）を初期化する、入れ子構造になったループ文の集まりが記述された初期化ループ箇所である。また、ソースコード１８００の４〜８行目は、初期化された配列変数ｔ（ｉ，ｍ）に対する代入演算を繰り返すことによって、配列変数ｔ（ｉ，ｍ）に対する縮約演算を行う、入れ子構造になったループ文の集まりが記述された縮約演算ループ箇所である。
【０１４４】
ソースコード１８００の１１，１８行目には、ループ文「ＤＯ  ｉ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード１８００の１２〜１７行目には、ループ文「ＤＯ  ｉ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード１８００の１１〜１８行目には、変数ｉを１から開始して変数ｉがｎになるまでループ本体内の処理を繰り返し実行するループ処理の内容が記述される。
【０１４５】
ソースコード１８００の１２，１７行目には、ループ文「ＤＯ  ｊ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード１８００の１３〜１６行目には、ループ文「ＤＯ  ｊ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード１８００の１２〜１７行目には、変数ｊを１から開始して変数ｊがｎになるまでループ本体内の処理を繰り返し実行するループ処理の内容が記述される。
【０１４６】
ソースコード１８００の１３行目には、代入文「ｓ（ｉ，ｊ）＝０」が記述される。これにより、ソースコード１８００の１３行目には、配列変数ｓ（ｉ，ｊ）の値に、数値「０」を代入する初期化処理の内容が記述される。
【０１４７】
ソースコード１８００の１４，１６行目には、ループ文「ＤＯ  ｍ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード１８００の１５行目には、ループ文「ＤＯ  ｍ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード１８００の１４〜１６行目には、変数ｍを１から開始して変数ｍがｎになるまでループ本体内の処理を繰り返し実行するループ処理が記述される。
【０１４８】
ソースコード１８００の１５行目には、代入文「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ｔ（ｉ，ｍ）＊ｖ（ｊ，ｍ）」が記述される。これにより、ソースコード１８００の１５行目には、配列変数ｓ（ｉ，ｊ）の値に、配列変数ｓ（ｉ，ｊ）＋配列変数ｔ（ｉ，ｍ）＊配列変数ｖ（ｊ，ｍ）の値を代入する代入処理が記述される。
【０１４９】
このように、ソースコード１８００の１１〜１８行目は、入れ子構造になった複数のループ文の集まりが記述された多重ループ箇所である。また、ソースコード１８００の１１〜１３，１７，１８行目は、変数ｉ，ｊを変化させ、縮約演算が行われる配列変数ｓ（ｉ，ｊ）を切り替え、配列変数ｓ（ｉ，ｊ）を初期化する、入れ子構造になったループ文の集まりが記述された初期化ループ箇所である。また、ソースコード１８００の１４〜１６行目は、初期化された配列変数ｓ（ｉ，ｊ）に対する代入演算を繰り返すことによって、配列変数ｓ（ｉ，ｊ）に対する縮約演算を行う、入れ子構造になったループ文の集まりが記述された縮約演算ループ箇所である。
【０１５０】
（コンパイル処理手順の一例）
次に、図１９を用いて、コンパイル処理手順の一例について説明する。
【０１５１】
図１９は、コンパイル処理手順の一例を示すフローチャートである。図１９において、情報処理装置１００は、ソースコードを取得し、ＡＳＴ、変数表、および関数表を生成する、フロントエンド処理を実行する（ステップＳ１９０１）。次に、情報処理装置１００は、図２０に後述するループ分割処理を実行する（ステップＳ１９０２）。そして、情報処理装置１００は、最適化処理を実行する（ステップＳ１９０３）。
【０１５２】
次に、情報処理装置１００は、最適化後のＡＳＴや変数表などに基づいて、オブジェクトコードを生成するバックエンド処理を実行する（ステップＳ１９０４）。そして、情報処理装置１００は、コンパイル処理を終了する。これにより、情報処理装置１００は、ソフトウェアの実行時の演算量を低減させて最適化が行われたオブジェクトコードを生成することができる。
【０１５３】
（ループ分割処理手順の一例）
次に、図２０を用いて、図１９のステップＳ１９０２に示したループ分割処理手順の一例について説明する。
【０１５４】
図２０は、ループ分割処理手順の一例を示すフローチャートである。図２０において、情報処理装置１００は、ＡＳＴに基づいて、多重ループ箇所を検出する（ステップＳ２００１）。次に、情報処理装置１００は、ＡＳＴのノードにアドレスを割り当てる（ステップＳ２００２）。そして、情報処理装置１００は、変数の依存関係を特定する（ステップＳ２００３）。
【０１５５】
次に、情報処理装置１００は、ＡＳＴのうち、検出した多重ループ箇所に含まれる縮約演算式に対応する部分木を抽出する（ステップＳ２００４）。そして、情報処理装置１００は、図２１に後述する部分式抽出処理を実行する（ステップＳ２００５）。次に、情報処理装置１００は、図２７に後述する変数分類処理を実行する（ステップＳ２００６）。そして、情報処理装置１００は、図３３に後述する削減量算出処理を実行する（ステップＳ２００７）。
【０１５６】
次に、情報処理装置１００は、図３７に後述する最適化対象決定処理を実行する（ステップＳ２００８）。そして、情報処理装置１００は、図３８に後述するＡＳＴ変形処理を実行する（ステップＳ２００９）。その後、情報処理装置１００は、ループ分割処理手順を終了する。これにより、情報処理装置１００は、ソフトウェアの実行時の演算量を低減させて、最適化を行うことができる。
【０１５７】
（部分式抽出処理手順の一例）
次に、図２１を用いて、図２０のステップＳ２００５に示した部分式抽出処理手順の一例について説明する。
【０１５８】
図２１は、部分式抽出処理手順の一例を示すフローチャートである。図２１において、情報処理装置１００は、いずれかの縮約演算式を選択する（ステップＳ２１０１）。次に、情報処理装置１００は、選択した縮約演算式に対して、図２２および図２３に後述する抽出コア処理を実行する（ステップＳ２１０２）。
【０１５９】
そして、情報処理装置１００は、すべての縮約演算式を選択したか否かを判定する（ステップＳ２１０３）。ここで、未選択の縮約演算式がある場合（ステップＳ２１０３：Ｎｏ）、情報処理装置１００は、ステップＳ２１０１の処理に戻る。
【０１６０】
一方で、すべての縮約演算式を選択した場合（ステップＳ２１０３：Ｙｅｓ）、情報処理装置１００は、部分式抽出処理を終了する。これにより、情報処理装置１００は、ソフトウェアの実行時の演算量を低減させる際に用いられる部分式の候補となる、縮約演算式内の部分式を抽出することができる。
【０１６１】
（抽出コア処理手順の一例）
次に、図２２〜図２４を用いて、抽出コア処理手順の一例について説明する。
【０１６２】
図２２〜図２４は、抽出コア処理手順の一例を示すフローチャートである。図２２において、情報処理装置１００は、縮約演算式に対応する部分木の根ノードを参照して、根ノードの属性となる演算子が「＋＝」であるか否かを判定する（ステップＳ２２０１）。
【０１６３】
ここで、演算子が「＋＝」である場合（ステップＳ２２０１：Ｙｅｓ）、情報処理装置１００は、対象演算子として演算子「＋」を設定して（ステップＳ２２０２）、ステップＳ２２０４の処理に移行する。
【０１６４】
一方で、演算子が「＝」である場合（ステップＳ２２０１：Ｎｏ）、情報処理装置１００は、縮約演算式の右辺に対応する子ノードを参照して、対象演算子として子ノードの属性となる演算子を設定する（ステップＳ２２０３）。そして、情報処理装置１００は、ステップＳ２２０４の処理に移行する。
【０１６５】
ステップＳ２２０４において、情報処理装置１００は、縮約演算式の右辺を対象部分式として設定する（ステップＳ２２０４）。次に、情報処理装置１００は、縮約演算式の左辺を足し込み先部分式として設定する（ステップＳ２２０５）。そして、情報処理装置１００は、部分式のリストを空に設定する（ステップＳ２２０６）。
【０１６６】
次に、情報処理装置１００は、図２５に後述する抽出サブ処理を実行する（ステップＳ２２０７）。そして、情報処理装置１００は、変数ｎに０を設定する（ステップＳ２２０８）。その後、情報処理装置１００は、図２３のステップＳ２３０１の処理に移行する。
【０１６７】
図２３において、情報処理装置１００は、変数ｎが、部分式のリストの長さよりも小さいか否かを判定する（ステップＳ２３０１）。ここで、部分式のリストの長さ以上である場合（ステップＳ２３０１：Ｎｏ）、情報処理装置１００は、抽出コア処理を終了する。
【０１６８】
一方で、部分式のリストの長さよりも小さい場合（ステップＳ２３０１：Ｙｅｓ）、情報処理装置１００は、分割部分式のリストを空に設定する（ステップＳ２３０２）。次に、情報処理装置１００は、ｎにｎ＋１を設定する（ステップＳ２３０３）。そして、情報処理装置１００は、現在の部分式に、部分式のリストのｎ番目の部分式を設定する（ステップＳ２３０４）。
【０１６９】
次に、情報処理装置１００は、分割部分式のリストに、現在の部分式と「１」との組み合わせを、分割部分式の組み合わせとして追加する（ステップＳ２３０５）。そして、情報処理装置１００は、現在の部分式に対応する部分木の根ノードを参照して、根ノードの属性となる演算子が２項演算子であるか否かを判定する（ステップＳ２３０６）。ここで、２項演算子ではない場合（ステップＳ２３０６：Ｎｏ）、情報処理装置１００は、抽出コア処理を終了する。
【０１７０】
一方で、２項演算子である場合（ステップＳ２３０６：Ｙｅｓ）、情報処理装置１００は、現在の部分式を対象部分式として設定する（ステップＳ２３０７）。次に、情報処理装置１００は、根ノードの属性となる２項演算子を対象演算子として設定する（ステップＳ２３０８）。そして、情報処理装置１００は、「ＮＵＬＬ」を足し込み先部分式として設定する（ステップＳ２３０９）。次に、情報処理装置１００は、部分式のリストを、部分式のリストのセーブにコピーする（ステップＳ２３１０）。そして、情報処理装置１００は、図２４のステップＳ２４０１の処理に移行する。
【０１７１】
図２４において、情報処理装置１００は、部分式のリストを空に設定する（ステップＳ２４０１）。次に、情報処理装置１００は、図２５に後述する抽出サブ処理を実行する（ステップＳ２４０２）。そして、情報処理装置１００は、変数ｂに１を設定する（ステップＳ２４０３）。
【０１７２】
次に、情報処理装置１００は、変数ｂが、２＾（部分式のリストの長さ−１）以下であるか否かを判定する（ステップＳ２４０４）。ここで、２＾（部分式のリストの長さ−１）より大きい場合（ステップＳ２４０４：Ｎｏ）、情報処理装置１００は、ステップＳ２４０８の処理に移行する。
【０１７３】
一方で、２＾（部分式のリストの長さ−１）以下である場合（ステップＳ２４０４：Ｙｅｓ）、情報処理装置１００は、図２６に後述する分割部分式生成処理を実行する（ステップＳ２４０５）。次に、情報処理装置１００は、分割部分式のリストに、分割部分式の組み合わせを追加する（ステップＳ２４０６）。そして、情報処理装置１００は、変数ｂに変数ｂ＋１を設定して（ステップＳ２４０７）、ステップＳ２４０４の処理に戻る。
【０１７４】
ステップＳ２４０８において、情報処理装置１００は、部分式のリストのセーブを、部分式のリストにコピーする（ステップＳ２４０８）。次に、情報処理装置１００は、部分式のリストのｎ番目に、部分式のアドレスと、分割部分式のリストとを追加する（ステップＳ２４０９）。そして、情報処理装置１００は、図２３のステップＳ２３０１の処理に戻る。これにより、情報処理装置１００は、縮約演算式内の部分式を抽出することができる。
【０１７５】
（抽出サブ処理手順の一例）
次に、図２５を用いて、図２２のステップＳ２２０７や図２４のステップＳ２４０２に示した抽出サブ処理手順の一例について説明する。
【０１７６】
図２５は、抽出サブ処理手順の一例を示すフローチャートである。図２５において、情報処理装置１００は、対象部分式に対応する部分木の根ノードを参照して、根ノードの属性となる演算子が対象演算子と一致するか否かを判定する（ステップＳ２５０１）。ここで、一致する場合（ステップＳ２５０１：Ｙｅｓ）、情報処理装置１００は、対象部分式をＸとして設定する（ステップＳ２５０２）。
【０１７７】
次に、情報処理装置１００は、Ｘに対応する部分木のいずれか一方の子ノードを選択し、選択した子ノードが根となる部分木に対応する式を、対象部分式として設定する（ステップＳ２５０３）。そして、情報処理装置１００は、対象部分式に対して抽出サブ処理を実行する（ステップＳ２５０４）。
【０１７８】
次に、情報処理装置１００は、Ｘに対応する部分木の他方の子ノードを選択し、選択した子ノードが根となる部分木に対応する式を、対象部分式として設定する（ステップＳ２５０５）。そして、情報処理装置１００は、対象部分式に対して抽出サブ処理を実行する（ステップＳ２５０６）。その後、情報処理装置１００は、抽出サブ処理を終了する。
【０１７９】
一方で、一致しない場合（ステップＳ２５０１：Ｎｏ）、情報処理装置１００は、対象部分式が、足し込み先部分式と一致するか否かを判定する（ステップＳ２５０７）。ここで、一致しない場合（ステップＳ２５０７：Ｎｏ）、情報処理装置１００は、部分式のリストに、対象部分式を追加する（ステップＳ２５０８）。そして、情報処理装置１００は、抽出サブ処理を終了する。
【０１８０】
一方で、一致する場合（ステップＳ２５０７：Ｙｅｓ）、情報処理装置１００は、抽出サブ処理を終了する。これにより、情報処理装置１００は、縮約演算式内の部分式を抽出することができる。
【０１８１】
（分割部分式生成処理手順の一例）
次に、図２６を用いて、分割部分式生成処理手順の一例について説明する。
【０１８２】
図２６は、分割部分式生成処理手順の一例を示すフローチャートである。図２６において、情報処理装置１００は、分割部分式１と分割部分式２とに「ＮＵＬＬ」を設定する（ステップＳ２６０１）。
【０１８３】
次に、情報処理装置１００は、変数ｍに０を設定する（ステップＳ２６０２）。そして、情報処理装置１００は、ｍが、部分式のリストの長さよりも小さいか否かを判定する（ステップＳ２６０３）。ここで、大きい場合（ステップＳ２６０３：Ｎｏ）、情報処理装置１００は、分割部分式生成処理を終了する。
【０１８４】
一方で、小さい場合（ステップＳ２６０３：Ｙｅｓ）、情報処理装置１００は、変数ｂのｍビット目が１であるか否かを判定する（ステップＳ２６０４）。ここで、０である場合（ステップＳ２６０４：Ｎｏ）、情報処理装置１００は、ステップＳ２６０８の処理に移行する。
【０１８５】
一方で、１である場合（ステップＳ２６０４：Ｙｅｓ）、情報処理装置１００は、分割部分式２がＮＵＬＬであるか否かを判定する（ステップＳ２６０５）。ここで、ＮＵＬＬである場合（ステップＳ２６０５：Ｙｅｓ）、情報処理装置１００は、分割部分式２に部分式のリストのｍ＋１番目のレコードの部分式を設定して（ステップＳ２６０６）、ステップＳ２６１１の処理に移行する。
【０１８６】
一方で、ＮＵＬＬではない場合（ステップＳ２６０５：Ｎｏ）、情報処理装置１００は、分割部分式２に、分割部分式２と部分式のリストのｍ＋１番目のレコードの部分式とを対象演算子で接続した部分式を設定する（ステップＳ２６０７）。そして、情報処理装置１００は、ステップＳ２６１１の処理に移行する。
【０１８７】
ステップＳ２６０８において、情報処理装置１００は、分割部分式１がＮＵＬＬであるか否かを判定する（ステップＳ２６０８）。ここで、ＮＵＬＬである場合（ステップＳ２６０８：Ｙｅｓ）、情報処理装置１００は、分割部分式１に部分式のリストのｍ＋１番目のレコードの部分式を設定して（ステップＳ２６０９）、ステップＳ２６１１の処理に移行する。
【０１８８】
一方で、ＮＵＬＬではない場合（ステップＳ２６０８：Ｎｏ）、情報処理装置１００は、分割部分式１に、分割部分式１と部分式のリストのｍ＋１番目のレコードの部分式とを対象演算子で接続した部分式を設定する（ステップＳ２６１０）。そして、情報処理装置１００は、ステップＳ２６１１の処理に移行する。
【０１８９】
ステップＳ２６１１において、情報処理装置１００は、ｍにｍ＋１を設定して（ステップＳ２６１１）、ステップＳ２６０３の処理に戻る。これにより、情報処理装置１００は、縮約演算式内の部分式をさらに分割して得られる、ソフトウェアの実行時の演算量を低減させる際に用いられる部分式の候補となる、分割部分式を生成することができる。
【０１９０】
（変数分類処理手順の一例）
次に、図２７および図２８を用いて、図２０のステップＳ２００６に示した変数分類処理手順の一例について説明する。
【０１９１】
図２７および図２８は、変数分類処理手順の一例を示すフローチャートである。図２７において、情報処理装置１００は、分割部分式のリストのいずれかのレコードを選択する（ステップＳ２７０１）。次に、対象分割部分式に、選択したレコードに記憶された分割部分式の組み合わせを設定する（ステップＳ２７０２）。そして、情報処理装置１００は、パラメータのリストを空に設定する（ステップＳ２７０３）。
【０１９２】
次に、情報処理装置１００は、図２９に後述する第１パラメータ抽出処理を実行する（ステップＳ２７０４）。そして、情報処理装置１００は、図３０に後述する第２パラメータ抽出処理を実行する（ステップＳ２７０５）。次に、情報処理装置１００は、図３１に後述する第３パラメータ抽出処理を実行する（ステップＳ２７０６）。そして、情報処理装置１００は、図２８のステップＳ２８０１の処理に移行する。
【０１９３】
図２８において、情報処理装置１００は、選択したレコードに記憶された一方の分割部分式についての縮約可能変数のリストを空に設定する（ステップＳ２８０１）。次に、情報処理装置１００は、対象分割部分式に、選択したレコードに記憶された一方の分割部分式を設定する（ステップＳ２８０２）。そして、情報処理装置１００は、図３２に後述する縮約可能変数抽出処理を実行する（ステップＳ２８０３）。その後、情報処理装置１００は、一方の分割部分式の縮約可能変数のリストに、抽出された縮約可能変数を設定する（ステップＳ２８０４）。
【０１９４】
次に、情報処理装置１００は、選択したレコードに記憶された他方の分割部分式についての縮約可能変数のリストを空に設定する（ステップＳ２８０５）。次に、情報処理装置１００は、対象分割部分式に、選択したレコードに記憶された他方の分割部分式を設定する（ステップＳ２８０６）。そして、情報処理装置１００は、図３２に後述する縮約可能変数抽出処理を実行する（ステップＳ２８０７）。その後、情報処理装置１００は、他方の分割部分式の縮約可能変数のリストに、抽出された縮約可能変数を設定する（ステップＳ２８０８）。
【０１９５】
次に、情報処理装置１００は、すべてのレコードを選択したか否かを判定する（ステップＳ２８０９）。ここで、未選択のレコードがある場合（ステップＳ２８０９：Ｎｏ）、情報処理装置１００は、図２７のステップＳ２７０１の処理に戻る。
【０１９６】
一方で、すべてのレコードを選択した場合（ステップＳ２８０９：Ｙｅｓ）、情報処理装置１００は、変数分類処理を終了する。これにより、情報処理装置１００は、削減される演算量の算出およびＡＳＴの変形の際に用いられる、パラメータおよび縮約可能変数を分類した結果を得ることができる。
【０１９７】
（第１パラメータ抽出処理手順の一例）
次に、図２９を用いて、図２７のステップＳ２７０４に示した第１パラメータ抽出処理手順の一例について説明する。
【０１９８】
図２９は、第１パラメータ抽出処理手順の一例を示すフローチャートである。図２９において、情報処理装置１００は、対象分割部分式が含まれる縮約演算式のうちの足し込み先部分式に対応する部分木の根ノードをＳとする（ステップＳ２９０１）。
【０１９９】
次に、情報処理装置１００は、Ｓの属性となる変数の種類が、配列変数であるか否かを判定する（ステップＳ２９０２）。ここで、スカラー変数である場合（ステップＳ２９０２：Ｎｏ）、情報処理装置１００は、第１パラメータ抽出処理を終了する。
【０２００】
一方で、配列変数である場合（ステップＳ２９０２：Ｙｅｓ）、情報処理装置１００は、Ｓの子ノードのうち、属性がインデックスである子ノードを選択する（ステップＳ２９０３）。次に、情報処理装置１００は、選択した子ノードをＡとする（ステップＳ２９０４）。そして、情報処理装置１００は、Ａの属性となるインデックスを、対象分割部分式のパラメータのリストに追加する（ステップＳ２９０５）。
【０２０１】
次に、情報処理装置１００は、属性がインデックスである子ノードをすべて選択したか否かを判定する（ステップＳ２９０６）。ここで、未選択の子ノードがある場合（ステップＳ２９０６：Ｎｏ）、情報処理装置１００は、ステップＳ２９０３の処理に戻る。
【０２０２】
一方で、子ノードをすべて選択した場合（ステップＳ２９０６：Ｙｅｓ）、情報処理装置１００は、第１パラメータ抽出処理を終了する。これにより、情報処理装置１００は、パラメータを抽出することができる。
【０２０３】
（第２パラメータ抽出処理手順の一例）
次に、図３０を用いて、図２７のステップＳ２７０５に示した第２パラメータ抽出処理手順の一例について説明する。
【０２０４】
図３０は、第２パラメータ抽出処理手順の一例を示すフローチャートである。図３０において、情報処理装置１００は、対象分割部分式が含まれる縮約演算式のうちの足し込み先部分式に対応する部分木の根ノードをＳとする（ステップＳ３００１）。
【０２０５】
次に、情報処理装置１００は、縮約演算を行うループ箇所の最も外側のループ文をＡとする（ステップＳ３００２）。そして、情報処理装置１００は、Ａよりも外側のループ文を選択する（ステップＳ３００３）。
【０２０６】
次に、情報処理装置１００は、選択したループ文の繰り返し回数を規定するインデックスを、対象分割部分式のパラメータのリストに追加する（ステップＳ３００４）。そして、情報処理装置１００は、Ａよりも外側にあるすべてのループ文を選択したか否かを判定する（ステップＳ３００５）。ここで、未選択のループ文がある場合（ステップＳ３００５：Ｎｏ）、情報処理装置１００は、ステップＳ３００３の処理に戻る。
【０２０７】
一方で、すべてのループ文を選択した場合（ステップＳ３００５：Ｙｅｓ）、情報処理装置１００は、第２パラメータ抽出処理を終了する。これにより、情報処理装置１００は、パラメータを抽出することができる。
【０２０８】
（第３パラメータ抽出処理手順の一例）
次に、図３１を用いて、図２７のステップＳ２７０６に示した第３パラメータ抽出処理手順の一例について説明する。
【０２０９】
図３１は、第３パラメータ抽出処理手順の一例を示すフローチャートである。図３１において、情報処理装置１００は、対象分割部分式のうちの一方の分割部分式をＡとする（ステップＳ３１０１）。次に、情報処理装置１００は、対象分割部分式のうちの他方の分割部分式をＢとする（ステップＳ３１０２）。そして、情報処理装置１００は、Ａについての変数のリストを空にする（ステップＳ３１０３）。
【０２１０】
次に、情報処理装置１００は、Ａの子孫ノードを走査し、Ａの子孫ノードを選択する（ステップＳ３１０４）。そして、情報処理装置１００は、選択したノードの属性がインデックスであれば、選択したノードの属性となるインデックスを、Ａについての変数のリストに追加する（ステップＳ３１０５）。
【０２１１】
その後、情報処理装置１００は、子孫ノードの走査が終了したか否かを判定する（ステップＳ３１０６）。ここで、走査が終了していない場合（ステップＳ３１０６：Ｎｏ）、情報処理装置１００は、ステップＳ３１０４の処理に戻る。
【０２１２】
一方で、走査が終了した場合（ステップＳ３１０６：Ｙｅｓ）、情報処理装置１００は、Ｂの子孫ノードを走査し、Ｂの子孫ノードを選択する（ステップＳ３１０７）。そして、情報処理装置１００は、選択したノードの属性がインデックスであり、Ａについての変数のリストにもあれば、選択したノードの属性となるインデックスを対象分割部分式のパラメータのリストに追加する（ステップＳ３１０８）。
【０２１３】
その後、情報処理装置１００は、子孫ノードの走査が終了したか否かを判定する（ステップＳ３１０９）。ここで、走査が終了していない場合（ステップＳ３１０９：Ｎｏ）、情報処理装置１００は、ステップＳ３１０７の処理に戻る。
【０２１４】
一方で、走査が終了した場合（ステップＳ３１０９：Ｙｅｓ）、情報処理装置１００は、第３パラメータ抽出処理を終了する。これにより、情報処理装置１００は、パラメータを抽出することができる。
【０２１５】
（縮約可能変数抽出処理手順の一例）
次に、図３２を用いて、図２８のステップＳ２８０３に示した縮約可能変数抽出処理手順の一例について説明する。
【０２１６】
図３２は、縮約可能変数抽出処理手順の一例を示すフローチャートである。図３２において、情報処理装置１００は、縮約可能変数のリストを空にする（ステップＳ３２０１）。次に、情報処理装置１００は、縮約演算式に対応する抽象構文木を走査し、縮約演算式に含まれる変数のリストを生成する（ステップＳ３２０２）。
【０２１７】
そして、情報処理装置１００は、変数のリストのうち、パラメータのリストに含まれない変数を、縮約可能変数のリストに追加する（ステップＳ３２０３）。その後、情報処理装置１００は、縮約可能変数抽出処理を終了する。これにより、情報処理装置１００は、縮約可能変数を抽出することができる。
【０２１８】
（削減量算出処理手順の一例）
次に、図３３を用いて、図２０のステップＳ２００７に示した削減量算出処理手順の一例について説明する。
【０２１９】
図３３は、削減量算出処理手順の一例を示すフローチャートである。図３３において、情報処理装置１００は、分割部分式のリストのいずれかのレコードを選択する（ステップＳ３３０１）。次に、情報処理装置１００は、選択したレコードの一方の分割部分式を、対象分割部分式に設定する（ステップＳ３３０２）。そして、情報処理装置１００は、図３４に後述する算出サブ処理を実行する（ステップＳ３３０３）。その後、情報処理装置１００は、一方の分割部分式の演算量に、算出サブ処理によって算出した合計演算量を設定する（ステップＳ３３０４）。
【０２２０】
次に、情報処理装置１００は、選択したレコードの他方の分割部分式を、対象分割部分式に設定する（ステップＳ３３０５）。そして、情報処理装置１００は、図３４に後述する算出サブ処理を実行する（ステップＳ３３０６）。その後、情報処理装置１００は、一方の分割部分式の演算量に、算出サブ処理によって算出した合計演算量を設定する（ステップＳ３３０７）。
【０２２１】
次に、情報処理装置１００は、パラメータについての繰り返し回数に基づいて、分割部分式同士の結合についての演算量を算出する（ステップＳ３３０８）。そして、情報処理装置１００は、すべてのレコードを選択したか否かを判定する（ステップＳ３３０９）。ここで、未選択のレコードがある場合（ステップＳ３３０９：Ｎｏ）、情報処理装置１００は、ステップＳ３３０１の処理に戻る。
【０２２２】
一方で、すべてのレコードを選択した場合（ステップＳ３３０９：Ｙｅｓ）、情報処理装置１００は、削減量算出処理を終了する。これにより、情報処理装置１００は、ループ分割後の演算量のうち、それぞれの部分式についての演算量を算出することができる。
【０２２３】
（算出サブ処理手順の一例）
次に、図３４〜図３６を用いて、図３３のステップＳ３３０３やステップＳ３３０６に示した算出サブ処理手順の一例について説明する。
【０２２４】
図３４〜図３６は、算出サブ処理手順の一例を示すフローチャートである。図３４において、情報処理装置１００は、演算量のリストを空にする（ステップＳ３４０１）。また、情報処理装置１００は、対象分割部分式に対応する部分木を走査して、対象分割部分式が縮約可能変数を含めば、縮約演算にかかる演算子と、カウント「１」を対応付けたレコードを、演算量のリストに追加する（ステップＳ３４０２）。
【０２２５】
次に、情報処理装置１００は、対象分割部分式に対応する部分木を走査して、属性が演算子であるノードを選択する（ステップＳ３４０３）。そして、情報処理装置１００は、選択したノードの属性が演算量のリストに記憶されていない演算子であれば、選択したノードの属性となる演算子と、カウント「０」とを対応付けたレコードを、演算量のリストに追加する（ステップＳ３４０４）。
【０２２６】
次に、情報処理装置１００は、演算量のリストにおける、選択したノードの属性となる演算子に対応するカウントをインクリメントする（ステップＳ３４０５）。そして、情報処理装置１００は、走査が終了したか否かを判定する（ステップＳ３４０６）。ここで、走査が終了していない場合（ステップＳ３４０６：Ｎｏ）、情報処理装置１００は、ステップＳ３４０２の処理に戻る。
【０２２７】
一方で、走査が終了した場合（ステップＳ３４０６：Ｙｅｓ）、情報処理装置１００は、繰り返し総数に１を設定する（ステップＳ３４０７）。そして、情報処理装置１００は、図３５のステップＳ３５０１の処理に移行する。
【０２２８】
図３５において、情報処理装置１００は、ループ文の繰り返し回数を規定するループ変数のいずれかの変数を選択する（ステップＳ３５０１）。次に、情報処理装置１００は、選択したループ変数に対応するループ処理をＬとする（ステップＳ３５０２）。そして、情報処理装置１００は、Ｌの開始値、終了値、増分の少なくともいずれかに、未定値があるか否かを判定する（ステップＳ３５０３）。ここで、未定値がない場合（ステップＳ３５０３：Ｎｏ）、情報処理装置１００は、ステップＳ３５０６の処理に移行する。
【０２２９】
一方で、未定値がある場合（ステップＳ３５０３：Ｙｅｓ）、情報処理装置１００は、Ｌの開始値、終了値、増分にヒントとして値が設定されていれば、当該値をＬの開始値、終了値、増分に使用する（ステップＳ３５０４）。次に、情報処理装置１００は、ヒントとして値が設定されていなければ、システムのデフォルト値をＬの開始値、終了値、増分に使用する（ステップＳ３５０５）。
【０２３０】
そして、情報処理装置１００は、選択した変数が、対象分割部分式に含まれるパラメータまたは縮約可能変数と一致するか否かを判定する（ステップＳ３５０６）。ここで、一致する場合（ステップＳ３５０６：Ｙｅｓ）、情報処理装置１００は、繰り返し総数に、繰り返し総数＊Ｌの繰り返し回数を設定して（ステップＳ３５０７）、ステップＳ３５０８の処理に移行する。
【０２３１】
一方で、一致しない場合（ステップＳ３５０６：Ｎｏ）、情報処理装置１００は、すべての変数を選択したか否かを判定する（ステップＳ３５０８）。ここで、未選択の変数がある場合（ステップＳ３５０８：Ｎｏ）、情報処理装置１００は、ステップＳ３５０１の処理に戻る。一方で、すべての変数を選択した場合（ステップＳ３５０８：Ｙｅｓ）、情報処理装置１００は、図３６のステップＳ３６０１の処理に移行する。
【０２３２】
図３６において、情報処理装置１００は、繰り返し総数を、演算単位として設定する（ステップＳ３６０１）。次に、情報処理装置１００は、合計演算量に０を設定する（ステップＳ３６０２）。そして、情報処理装置１００は、演算量のリストのレコードを選択する（ステップＳ３６０３）。
【０２３３】
次に、情報処理装置１００は、選択したレコードに記憶されたカウントに、カウント＊演算単位を設定する（ステップＳ３６０４）。そして、情報処理装置１００は、合計演算量に、合計演算量＋カウント＊演算の重みを設定する（ステップＳ３６０５）。次に、情報処理装置１００は、すべてのレコードを選択したか否かを判定する（ステップＳ３６０６）。ここで、未選択のレコードがある場合（ステップＳ３６０６：Ｎｏ）、情報処理装置１００は、ステップＳ３６０３の処理に戻る。
【０２３４】
一方で、すべてのレコードを選択した場合（ステップＳ３６０６：Ｙｅｓ）、情報処理装置１００は、算出サブ処理を終了する。これにより、情報処理装置１００は、ループ分割後の演算量のうち、対象分割部分式についての演算量を算出することができる。
【０２３５】
（最適化対象決定処理手順の一例）
次に、図３７を用いて、図２０のステップＳ２００８に示した最適化対象決定処理手順の一例について説明する。
【０２３６】
図３７は、最適化対象決定処理手順の一例を示すフローチャートである。図３７において、情報処理装置１００は、元の演算量を算出する（ステップＳ３７０１）。次に、情報処理装置１００は、部分式のリストのいずれかの部分式を選択する（ステップＳ３７０２）。そして、情報処理装置１００は、部分式に対応する分割部分式の組み合わせのうち、元の演算量から分割部分式の演算量と結合についての演算量とを減算した差分が最大の組み合わせを最適化対象に決定し、最適化対象のリストに追加する（ステップＳ３７０３）。
【０２３７】
次に、情報処理装置１００は、すべての部分式を選択したか否かを判定する（ステップＳ３７０４）。ここで、未選択の部分式がある場合（ステップＳ３７０４：Ｎｏ）、情報処理装置１００は、ステップＳ３７０２の処理に戻る。一方で、すべての部分式を選択した場合（ステップＳ３７０４：Ｙｅｓ）、情報処理装置１００は、最適化対象決定処理を終了する。これにより、情報処理装置１００は、最も削減量が大きい部分式を用いて、最適化を行うことができる。
【０２３８】
（ＡＳＴ変形処理手順の一例）
次に、図３８を用いて、図２０のステップＳ２００９に示したＡＳＴ変形処理手順の一例について説明する。
【０２３９】
図３８は、ＡＳＴ変形処理手順の一例を示すフローチャートである。図３８において、情報処理装置１００は、最適化対象のリストのいずれかの分割部分式の組み合わせを、対象要素として選択する（ステップＳ３８０１）。次に、情報処理装置１００は、選択した対象要素について、図３９に後述する縮約演算式挿入処理を実行する（ステップＳ３８０２）。そして、情報処理装置１００は、ループ分割処理を実行する（ステップＳ３８０３）。
【０２４０】
次に、情報処理装置１００は、対象分割部分式に、対象要素のうちの一方の分割部分式を設定する（ステップＳ３８０４）。そして、情報処理装置１００は、対象分割部分式について、図４０に後述する変形サブ処理を実行する（ステップＳ３８０５）。
【０２４１】
次に、情報処理装置１００は、対象分割部分式に、対象要素のうちの他方の分割部分式を設定する（ステップＳ３８０６）。そして、情報処理装置１００は、対象分割部分式について、図４０に後述する変形サブ処理を実行する（ステップＳ３８０７）。
【０２４２】
次に、情報処理装置１００は、すべての組み合わせを選択したか否かを判定する（ステップＳ３８０８）。ここで、未選択の組み合わせがある場合（ステップＳ３８０８：Ｎｏ）、情報処理装置１００は、ステップＳ３８０１の処理に戻る。
【０２４３】
一方で、すべての組み合わせを選択した場合（ステップＳ３８０８：Ｙｅｓ）、情報処理装置１００は、ＡＳＴ変形処理を終了する。これにより、情報処理装置１００は、ソフトウェアの実行時の演算量を低減させることができる。
【０２４４】
（縮約演算式挿入処理手順の一例）
次に、図３９を用いて、図３８のステップＳ３８０２に示した縮約演算式挿入処理手順の一例について説明する。
【０２４５】
図３９は、縮約演算式挿入処理手順の一例を示すフローチャートである。図３９において、情報処理装置１００は、対象要素に対応する部分木の親ノードの属性が、演算子「＋＝」であるか否かを判定する（ステップＳ３９０１）。ここで、演算子「＋＝」である場合（ステップＳ３９０１：Ｙｅｓ）、情報処理装置１００は、縮約演算式挿入処理を終了する。
【０２４６】
一方で、演算子「＋＝」ではない場合（ステップＳ３９０１：Ｎｏ）、情報処理装置１００は、対象要素に対応する部分木の親ノードの属性が、演算子「＝」であるか否かを判定する（ステップＳ３９０２）。ここで、演算子「＋」である場合（ステップＳ３９０２：Ｙｅｓ）、情報処理装置１００は、縮約演算式挿入処理を終了する。
【０２４７】
一方で、演算子「＋」ではない場合（ステップＳ３９０２：Ｎｏ）、情報処理装置１００は、対象要素が含まれる縮約演算式と並列した、対象要素を縮約演算する縮約演算式に対応する部分木を生成する（ステップＳ３９０３）。そして、情報処理装置１００は、縮約演算式挿入処理を終了する。これにより、情報処理装置１００は、ソフトウェアの実行時の演算量を低減させるように、ＡＳＴを変形する準備として、縮約演算式を挿入することができる。
【０２４８】
（変形サブ処理手順の一例）
次に、図４０を用いて、図３８のステップＳ３８０５やステップＳ３８０７に示した変形サブ処理手順の一例について説明する。
【０２４９】
図４０は、変形サブ処理手順の一例を示すフローチャートである。図４０において、情報処理装置１００は、対象分割部分式の削減量が０より大きいか否かを判定する（ステップＳ４００１）。ここで、０以下である場合（ステップＳ４００１：Ｎｏ）、情報処理装置１００は、変形サブ処理を終了する。
【０２５０】
一方で、０より大きい場合（ステップＳ４００１：Ｙｅｓ）、情報処理装置１００は、対象要素が含まれる縮約演算式の多重ループの直前に、対象分割部分式のパラメータをループ変数とする多重ループに対応する部分木を生成する（ステップＳ４００２）。次に、情報処理装置１００は、多重ループの一番内側に、対象分割部分式のインデックス、かつ、パラメータである変数をインデックスにした配列変数の初期化式に対応する部分木を生成する（ステップＳ４００３）。
【０２５１】
そして、情報処理装置１００は、初期化式の直後に、縮約可能変数をループ変数とする多重ループに対応する部分木を生成する（ステップＳ４００４）。次に、情報処理装置１００は、多重ループの一番内側に、初期化した配列変数に対象分割部分式を縮約演算する縮約演算式に対応する部分木を生成する（ステップＳ４００５）。そして、情報処理装置１００は、対象分割部分式が元々含まれていた縮約演算式のうちの対象部分式を配列変数に置換する（ステップＳ４００６）。
【０２５２】
次に、情報処理装置１００は、対象分割部分式が元々含まれていた縮約演算式についての多重ループのうちの、縮約可能変数をループ変数とするループ文に対応する部分木を削除する（ステップＳ４００７）。そして、情報処理装置１００は、変形サブ処理を終了する。これにより、情報処理装置１００は、ソフトウェアの実行時の演算量を低減させるように、ＡＳＴを変形することができる。
【０２５３】
以上説明したように、情報処理装置１００によれば、プログラムコードのうち、第１変数に対して縮約演算する第１式についての計算を繰り返すループ箇所を特定することができる。次に、情報処理装置１００によれば、第１式のうちの部分式を第２変数に対して縮約演算する第２式についての計算を繰り返す第１コード、および、第１式のうちの部分式が第２変数に置換された第３式についての計算を繰り返す第２コードを生成することができる。そして、情報処理装置１００によれば、プログラムコードのうちのループ箇所を第１コードおよび第２コードに変換したプログラムコードを出力することができる。これにより、情報処理装置１００は、ソフトウェアの実行時の演算量を低減させて、ソフトウェアの処理時間の短縮化を図ることができる。
【０２５４】
情報処理装置１００によれば、第１式のうちの各部分式について、第２式についての計算の種類および繰り返し回数と、第３式についての計算の種類および繰り返し回数とを特定することができる。次に、情報処理装置１００によれば、特定した結果に基づいて、第１式のうちの各部分式について、第２式についての計算を繰り返す演算量および第３式についての計算を繰り返す演算量の合計と、ループ箇所の演算量との差分を算出することができる。そして、情報処理装置１００によれば、算出した差分に基づいて、第１式のうちのいずれかの部分式を選択し、選択したいずれかの部分式について第１コードおよび第２コードを生成することができる。これにより、情報処理装置１００は、プログラムコードを変換した場合に、削減される演算量を算出することができる。そして、情報処理装置１００は、ソフトウェアの実行時の演算量が最も低減されるようにプログラムコードを変換する場合に、第２式において使用する部分式を選択することができる。
【０２５５】
情報処理装置１００によれば、第１式についての計算を繰り返す条件に使用される変数を、第１種別の変数と、第１種別の変数とは異なる第２種別の変数とに分類することができる。そして、情報処理装置１００によれば、分類した結果に基づいて、第１式のうちの各部分式について、第２式についての計算の種類および繰り返し回数と、第３式についての計算の種類および繰り返し回数とを特定することができる。これにより、情報処理装置１００は、第１コードや第２コードを生成しなくても、ループ箇所を第１コードや第２コードに変換した場合に削減される演算量を算出することができる。
【０２５６】
情報処理装置１００によれば、第１式のうちの各部分式について、第２式についての計算の繰り返し条件に使用する変数および繰り返し回数と、第３式についての計算の繰り返し条件に使用する変数および繰り返し回数とを特定することができる。そして、情報処理装置１００によれば、特定した変数および繰り返し回数に基づいて、ループ文を用いて第１コードを生成し、ループ文を用いて第２コードを生成することができる。これにより、情報処理装置１００は、用いなくてもよいループ文を含まない第１コードや第２コードを生成することができる。
【０２５７】
情報処理装置１００によれば、第１式についての計算を繰り返す条件に使用される変数を、第１種別の変数と、第１種別の変数とは異なる第２種別の変数とに分類することができる。そして、情報処理装置１００によれば、分類した結果に基づいて、第１式のうちの各部分式について、第２式についての計算の繰り返し条件に使用する変数および繰り返し回数を特定することができる。また、情報処理装置１００によれば、分類した結果に基づいて、第１式のうちの各部分式について、第３式についての計算の繰り返し条件に使用する変数および繰り返し回数を特定することができる。これにより、情報処理装置１００は、第１コードや第２コードに、どのループ文を用いるかを判定する際に用いる情報を得ることができる。
【０２５８】
情報処理装置１００によれば、第１式が「第１演算子」により第１変数に対して縮約演算する式であれば、部分式を同一の演算子である「第１演算子」により第２変数に対して縮約演算する式を第２式として採用することができる。これにより、情報処理装置１００は、第１式のうちの部分式と置換可能な定数が、第２変数の値として算出されるように、第２式を生成することができる。
【０２５９】
（実施の形態２にかかるコンパイル方法の一実施例）
図４１は、実施の形態２にかかるコンパイル方法の一実施例を示す説明図である。図４１において、情報処理装置１００は、プログラムコードに規定された機能が変更されない範囲で、プログラムコードに記述された処理内容を変更して、ソフトウェアの処理時間の短縮化を図る。
【０２６０】
ここで、最適化の技術には、例えば、１つのループ処理において、ループ本体内の複数箇所に同一内容の式があれば、当該式についての計算を１箇所で１回行っておき、当該式の計算結果で複数箇所の当該式を置き換える技術がある。
【０２６１】
しかしながら、縮約演算する式が含まれるネスト構造の多重ループ処理のうちの複数のループ処理を通して計算される式の集まりが複数ある場合に、それぞれの集まりに同一内容の式が含まれても、上述した最適化の技術を適用することができない。このため、縮約演算する式が含まれる多重ループ処理については、処理内容をどのように変更すれば演算量が低減されるか分からず、ソフトウェアの処理時間を短縮することができない場合がある。
【０２６２】
そこで、本実施の形態では、縮約演算する式が含まれる多重ループ処理について処理内容を変更して、ソフトウェアの実行時の演算量の低減化を図ることにより、ソフトウェアの処理時間の短縮化を図るコンパイル方法について説明する。
【０２６３】
図４１の例では、プログラムコードとして、式４１１０についての計算、および式４１２０についての計算を繰り返すループ箇所が記述されたソースコード４１０１を例に挙げて、情報処理装置１００の動作について説明する。
【０２６４】
式４１１０は、「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｊ）＊ｂ（ｌ，ｉ）＊ｃ（ｋ）」である。式４１１０は、変数「ａ（ｉ，ｊ）」や変数「ｂ（ｌ，ｉ）」や変数「ｃ（ｋ）」を第１変数「ｓ（ｉ，ｊ）」に対して縮約演算する式である。式４１２０は、「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｊ）＊ｂ（ｋ，ｉ）」である。式４１２０は、変数「ａ（ｉ，ｊ）」や変数「ｂ（ｋ，ｉ）」を第１変数「ｓ（ｉ，ｊ）」に対して縮約演算する式である。
【０２６５】
ここで、例えば、ｎ＝２とした場合には、ループ箇所において式４１１０についての計算を繰り返すという第１処理内容は、機能を変更せずに、符号４１４０に示す下記式（９）〜式（１２）についての計算を行うという第２処理内容に変更することが可能である。これにより、第２処理内容では、第１処理内容よりも演算子の数が減るため、演算量が低減される。
【０２６６】
ｓ（１，１）＝ｓ（１，１）＋ａ（１，１）＊｛ｂ（１，１）＋ｂ（２，１）｝
・・・（９）
ｓ（１，２）＝ｓ（１，２）＋ａ（１，２）＊｛ｂ（１，１）＋ｂ（２，１）｝
・・・（１０）
ｓ（２，１）＝ｓ（２，１）＋ａ（２，１）＊｛ｂ（１，２）＋ｂ（２，２）｝
・・・（１１）
ｓ（２，２）＝ｓ（２，２）＋ａ（２，２）＊｛ｂ（１，２）＋ｂ（２，２）｝
・・・（１２）
【０２６７】
また、例えば、ｎ＝２とした場合には、ループ箇所において式４１２０についての計算を繰り返すという第３処理内容は、機能を変更せずに、符号４１５０に示す下記式（１３）〜式（１６）についての計算を行うという第４処理内容に変更することが可能である。これにより、第４処理内容では、第３処理内容よりも演算子の数が減るため、演算量が低減される。
【０２６８】
ｓ（１，１）＝ｓ（１，１）＋ａ（１，１）＊｛ｂ（１，１）＋ｂ（２，１）｝＊ｃ（１）＋ａ（１，１）＊｛ｂ（１，１）＋ｂ（２，１）｝＊ｃ（２）      ・・・（１３）
ｓ（１，２）＝ｓ（１，２）＋ａ（１，２）＊｛ｂ（１，１）＋ｂ（２，１）｝＊ｃ（１）＋ａ（１，２）＊｛ｂ（１，１）＋ｂ（２，１）｝＊ｃ（２）      ・・・（１４）
ｓ（２，１）＝ｓ（２，１）＋ａ（２，１）＊｛ｂ（１，２）＋ｂ（２，２）｝＊ｃ（１）＋ａ（２，１）＊｛ｂ（１，２）＋ｂ（２，２）｝＊ｃ（２）      ・・・（１５）
ｓ（２，２）＝ｓ（２，２）＋ａ（２，２）＊｛ｂ（１，２）＋ｂ（２，２）｝＊ｃ（１）＋ａ（２，２）＊｛ｂ（１，２）＋ｂ（２，２）｝＊ｃ（２）      ・・・（１６）
【０２６９】
さらに、上述した第２処理内容および第４処理内容は、定数として扱うことが可能な、複数の式に共通する同一内容の式が含まれる。このため、第２処理内容および第４処理内容は、機能を変更せずに、共通する同一内容の式についての計算を行ってから、当該計算で得られた結果を利用して式（９）〜（１６）について計算を行うという第５処理内容に変更することが可能である。
【０２７０】
例えば、式「ｂ（１，１）＋ｂ（２，１）」や式「ｂ（１，１）＋ｂ（２，２）」についての計算が行われた後に、当該計算で得られた結果を利用して式（９）〜（１６）についての計算が行われる。これにより、第５処理内容では、定数として扱うことが可能な、複数の式に共通する同一内容の式についての計算を複数回ずつ行わなくてもよくなるため、演算量が低減される。
【０２７１】
このように、複数のループ処理を通して計算される式の集まりが複数ある場合に、それぞれの集まりに共通して、定数として扱うことが可能な式が含まれる場合には、ソースコード４１０１に記述された処理内容を変更すれば、演算量を低減することが可能である。このため、情報処理装置１００は、上述した処理内容の変更による演算量の低減化が実現されるように、ソースコード４１０１のループ箇所を変換して、変換後のソースコード４１０２を出力することになる。
【０２７２】
図４１の例では、（４１−１）情報処理装置１００は、ソースコード４１０１を取得する。次に、情報処理装置１００は、ソースコード４１０１に対して字句解析や文法解析を行い、ソースコード４１０１に対応する抽象構文木を作成する。そして、情報処理装置１００は、抽象構文木に基づいて、ソースコード４１０１に記述された、式４１１０「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｊ）＊ｂ（ｌ，ｉ）＊ｃ（ｋ）」についての計算を繰り返すループ箇所を特定する。また、情報処理装置１００は、式４１１０のうちの部分式「ｂ（ｌ，ｉ）」を特定する。
【０２７３】
（４１−２）情報処理装置１００は、特定したループ箇所内にある、式４１１０とは異なる式４１２０「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｊ）＊ｂ（ｋ，ｉ）」を特定する。そして、情報処理装置１００は、式４１２０のうち、式４１１０のうちの部分式「ｂ（ｌ，ｉ）」と少なくとも変数および変数間の関係が同一である他の部分式「ｂ（ｋ，ｉ）」を特定する。
【０２７４】
（４１−３）情報処理装置１００は、特定した他の部分式「ｂ（ｋ，ｉ）」を第２変数「ｔ（ｉ）」に対して縮約演算する式４１６０「ｔ（ｉ）＝ｔ（ｉ）＋ｂ（ｋ，ｉ）」についての計算を繰り返す第１コードを生成する。式４１６０は、式４１１０のうちの部分式「ｂ（ｌ，ｉ）」を第２変数「ｔ（ｉ）」に対して縮約演算する式「ｔ（ｉ）＝ｔ（ｉ）＋ｂ（ｌ，ｉ）」と等価である。第１コードは、上述した式「ｂ（１，１）＋ｂ（２，１）」や式「ｂ（１，１）＋ｂ（２，２）」についての計算を行うという処理内容に対応するコードである。第２変数は、式４１１０のうちの部分式および式４１２０のうちの他の部分式のそれぞれと置換可能な変数である。
【０２７５】
また、情報処理装置１００は、式４１１０のうちの部分式が第２変数に置換された式４１７０「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｊ）＊ｔ（ｉ）＊ｃ（ｋ）」を特定する。また、情報処理装置１００は、式４１２０のうちの他の部分式が第２変数に置換された式４１８０「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｊ）＊ｔ（ｉ）」を特定する。そして、情報処理装置１００は、式４１７０および式４１８０についての計算を繰り返す第２コードを生成する。第２コードは、式「ｂ（１，１）＋ｂ（２，１）」や式「ｂ（１，１）＋ｂ（２，２）」についての計算で得られた結果を利用して、式（９）〜（１６）についての計算を行うという処理内容に対応するコードである。
【０２７６】
（４１−４）情報処理装置１００は、ソースコード４１０１のうちのループ箇所を第１コードおよび第２コードに変換する。そして、情報処理装置１００は、変換後のソースコード４１０２を、表示装置に出力し、他のコンピュータに送信し、または記憶装置に記憶する。
【０２７７】
このように、情報処理装置１００によれば、縮約演算する式４１１０の部分式、および縮約演算する式４１２０の他の部分式のそれぞれを縮約演算した場合の演算結果を、一度にまとめて算出する式４１６０を含む第１コードを生成することができる。そして、情報処理装置１００によれば、ソースコード４１０１のうちのループ箇所を、第１コードと、演算結果を利用した式４１７０および式４１８０を含むループ処理を示す第２コードとに変換することができる。これにより、情報処理装置１００は、複数のループ処理を通して計算される複数の式の集まりに共通して、定数として扱うことが可能な式について式４１６０を作成し、式４１６０についての計算を予め行うように、ソースコード４１０１を変換することができる。
【０２７８】
結果として、情報処理装置１００は、ソフトウェアの実行時の演算量を低減して、ソフトウェアの処理時間の短縮化を図ることができる。例えば、ソースコード４１０１では、加算「＋」と乗算「＊」とが、「ｎ＾３」回繰り返して実行され、加算「＋」と２回分の乗算「＊」とが、「ｎ＾４」回繰り返して実行される。このため、ソースコード４１０１では、演算量は「２ｎ＾３＋３ｎ＾４」である。
【０２７９】
これに対し、変換後のソースコード４１０２では、加算「＋」が「ｎ＾２」回実行され、加算「＋」と乗算「＊」とが「ｎ＾２」回実行され、加算「＋」と２回分の乗算「＊」とが「ｎ＾３」回実行される。このため、変換後のソースコード４１０２では、演算量は「ｎ＾２＋２ｎ＾２＋３ｎ＾３」である。結果として、変換後のソースコード４１０２では、ｎ＞２であれば、演算量が低減される。
【０２８０】
ここでは、式４１７０と式４１８０とがまとめて１つのループ処理に含まれる場合について説明したが、これに限らない。例えば、情報処理装置１００は、第２コードの代わりに、式４１７０を含むループ処理を示すコードと、式４１８０を含むループ処理を示すコードとの組み合わせを採用してもよい。
【０２８１】
（実施の形態２にかかる情報処理装置１００のハードウェア構成例）
次に、情報処理装置１００のハードウェア構成例について説明する。情報処理装置１００のハードウェア構成例は、図２に示したハードウェア構成例と同様であるため、説明を省略する。
【０２８２】
（実施の形態２にかかる情報処理装置１００の機能的構成例）
次に、情報処理装置１００の機能的構成例について説明する。情報処理装置１００は、図３に示したように、特定部３０１と、分類部３０２と、算出部３０３と、選択部３０４と、生成部３０５と、出力部３０６とを含む。
【０２８３】
特定部３０１は、実施の形態１と同様に、ソフトウェアのプログラムコードのうち、第１変数に対して縮約演算する第１式についての計算を繰り返すループ箇所を特定する。そして、特定部３０１は、第１式のうちの部分式を特定する。特定部３０１は、さらに、特定したループ箇所内にある、第３変数に縮約演算する第４式のうち、第１式のうちの部分式と少なくとも変数および変数間の関係が同一である他の部分式を特定する。
【０２８４】
特定部３０１は、例えば、第１式「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｊ）＊ｂ（ｌ，ｉ）＊ｃ（ｋ）」についての計算を繰り返すループ箇所を特定する。そして、特定部３０１は、第１式のうちの部分式「ｂ（ｌ，ｉ）」などを特定する。特定部３０１は、さらに、ループ箇所内にある、第４式「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｊ）＊ｂ（ｋ，ｉ）」を特定する。そして、特定部３０１は、第１式のうちの部分式「ｂ（ｌ，ｉ）」との間で、インデックスが異なっていても、変数および変数間の関係が同一である、第４式のうちの部分式「ｂ（ｋ，ｉ）」を特定する。これにより、特定部３０１は、ソフトウェアの実行時の演算量を低減させることができる可能性があるループ箇所を特定することができる。
【０２８５】
分類部３０２は、実施の形態１と同様に、第１式についての計算を繰り返す条件に使用される変数を、第１式のうちの各部分式における第１種別の変数と、第１種別の変数とは異なる第２種別の変数とに分類する。分類部３０２は、さらに、第４式についての計算を繰り返す条件に使用される変数を、第４式のうちの各部分式における第１種別の変数と、第１種別の変数とは異なる第２種別の変数とに分類する。これにより、分類部３０２は、第１式のうちの部分式および第４式のうちの部分式の組み合わせを基にループ箇所を変換した場合に削減される演算量を算出する際に用いる情報を得ることができる。
【０２８６】
算出部３０３は、第４式のうちで特定した各部分式について、当該部分式を第２変数に対して縮約演算する第２式についての計算の種類および繰り返し回数を特定する。ここで、第２変数は、第１式のうちの部分式、および第４式のうちの部分式と置換可能な変数である。また、算出部３０３は、第１式のうちの当該部分式が第２変数に置換された第３式についての計算の種類および繰り返し回数を特定する。また、算出部３０３は、第４式のうちの部分式が第２変数に置換された第５式についての計算の種類および繰り返し回数を特定する。
【０２８７】
そして、算出部３０３は、特定した種類および繰り返し回数に基づいて、第２式についての計算を繰り返す演算量、第３式についての計算を繰り返す演算量、および第５式についての計算を繰り返す演算量の合計と、ループ箇所の演算量との差分を算出する。
【０２８８】
算出部３０３は、例えば、分類した結果に基づいて、第４式のうちで特定した各部分式について、当該部分式を第２変数に対して縮約演算する第２式についての計算の種類および繰り返し回数を特定する。また、算出部３０３は、分類した結果に基づいて、第１式のうちの各部分式について、第１式のうちの当該部分式が第２変数に置換された第３式についての計算の種類および繰り返し回数を特定する。また、算出部３０３は、分類した結果に基づいて、第４式のうちの各部分式について、第４式のうちの当該部分式が第２変数に置換された第５式についての計算の種類および繰り返し回数を特定する。
【０２８９】
そして、算出部３０３は、第２式について特定した種類ごとの演算子の数と、繰り返し回数とを乗算した値を、第２式についての計算を繰り返す演算量として算出する。また、算出部３０３は、第３式について特定した種類ごとの演算子の数と、繰り返し回数とを乗算した値を、第３式についての計算を繰り返す演算量として算出する。また、算出部３０３は、第５式について特定した種類ごとの演算子の数と、繰り返し回数とを乗算した値を、第３式についての計算を繰り返す演算量として算出する。
【０２９０】
そして、算出部３０３は、第２式についての計算を繰り返す演算量、第５式についての計算を繰り返す演算量および第３式についての計算を繰り返す演算量の合計とループ箇所の演算量との差分を算出する。これにより、算出部３０３は、プログラムコードを変換した場合に削減される演算量を特定することができる。
【０２９１】
選択部３０４は、算出部３０３が算出した差分に基づいて、第４式のうちの部分式を選択する。選択部３０４は、例えば、算出部３０３が算出した差分が最も大きい、第４式のうちの部分式との組み合わせを選択する。これにより、選択部３０４は、ソフトウェアの実行時の演算量が最も低減されるように、プログラムコードを変換する場合に用いる部分式を選択することができる。
【０２９２】
生成部３０５は、選択した第４式のうちの部分式を第２変数に対して縮約演算する第２式についての計算を繰り返す第１コードを生成する。また、生成部３０５は、選択した第４式のうちの部分式と、当該部分式との間で変数および変数間の関係が同一の、第１式のうちの部分式を特定する。次に、生成部３０５は、第１式のうちの部分式が第２変数に置換された第３式についての計算を繰り返し、かつ、第４式のうちの他の部分式が第２変数に置換された第５式についての計算を繰り返す第２コードを生成する。生成部３０５は、例えば、選択した部分式の組み合わせについて第１コードおよび第２コードを生成する。
【０２９３】
生成部３０５は、具体的には、第４式のうちで特定した各部分式について、当該部分式を縮約演算する第２式についての計算の繰り返し条件に使用する変数および繰り返し回数を特定する。また、生成部３０５は、第１式のうちの部分式が第２変数に置換された第３式についての計算の繰り返し条件に使用する変数および繰り返し回数を特定する。また、生成部３０５は、第４式のうちの部分式が第２変数に置換された第５式についての計算の繰り返し条件に使用する変数および繰り返し回数を特定する。そして、生成部３０５は、特定した変数および繰り返し回数に基づいて、ループ文を用いて第１コードを生成し、ループ文を用いて第２コードを生成する。
【０２９４】
生成部３０５は、より具体的には、分類した結果に基づいて、上述した変数および繰り返し回数を特定する。そして、生成部３０５は、特定した変数および繰り返し回数に基づいて、ループ文を用いて第１コードを生成し、ループ文を用いて第２コードを生成する。これにより、生成部３０５は、ソフトウェアの実行時の演算量を低減させることができるプログラムコードを生成することができる。
【０２９５】
出力部３０６は、実施の形態１と同様に、プログラムコードのうちのループ箇所を第１コードおよび第２コードに変換した変換後のプログラムコードを出力する。これにより、出力部３０６は、コンパイラに、変換後のプログラムコードを提供することができる。
【０２９６】
次に、図４２〜図４６を用いて、実施の形態２にかかる情報処理装置１００の動作例について説明する。
【０２９７】
（実施の形態２にかかるソースコード４２００の一例）
図４２は、実施の形態２にかかるソースコード４２００の一例を示す説明図である。図４２の例では、ソースコード４２００の１，１３行目には、ループ文「ＤＯ  ｉ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード４２００の２〜１２行目には、ループ文「ＤＯ  ｉ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード４２００の１〜１３行目には、変数ｉを１から開始して変数ｉがｎになるまでループ本体内の処理を繰り返し実行するループ処理の内容が記述される。
【０２９８】
ソースコード４２００の２，１２行目には、ループ文「ＤＯ  ｊ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード４２００の３〜１１行目には、ループ文「ＤＯ  ｊ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード４２００の２〜１２行目には、変数ｊを１から開始して変数ｊがｎになるまでループ本体内の処理を繰り返し実行するループ処理の内容が記述される。
【０２９９】
ソースコード４２００の３行目には、代入文「ｓ（ｉ，ｊ）＝０」が記述される。これにより、ソースコード４２００の３行目には、配列変数ｓ（ｉ，ｊ）の値に、数値「０」を代入する初期化処理の内容が記述される。
【０３００】
ソースコード４２００の４，１１行目には、ループ文「ＤＯ  ｋ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード４２００の５〜１０行目には、ループ文「ＤＯ  ｋ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード４２００の４〜１１行目には、変数ｋを１から開始して変数ｋがｎになるまでループ本体内の処理を繰り返し実行するループ処理の内容が記述される。
【０３０１】
ソースコード４２００の５，１０行目には、ループ文「ＤＯ  ｌ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード４２００の６〜９行目には、ループ文「ＤＯ  ｌ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード４２００の５〜１０行目には、変数ｌを１から開始して変数ｌがｎになるまでループ本体内の処理を繰り返し実行するループ処理が記述される。
【０３０２】
ソースコード４２００の６行目には、代入文「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｋ，ｊ，ｌ）＊ｗ（ｋ，ｌ）」が記述される。これにより、ソースコード４２００の６行目には、配列変数ｓ（ｉ，ｊ）の値に、配列変数ｓ（ｉ，ｊ）＋配列変数ａ（ｉ，ｋ，ｊ，ｌ）＊配列変数ｗ（ｋ，ｌ）の値を代入する代入処理が記述される。
【０３０３】
ソースコード４２００の７，９行目には、ループ文「ＤＯ  ｍ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」が記述される。ソースコード４２００の８行目には、ループ文「ＤＯ  ｍ＝１，ｎ  （ループ本体）  ＥＮＤＤＯ」によって繰り返し実行されるループ本体が記述される。これにより、ソースコード４２００の７〜９行目には、変数ｍを１から開始して変数ｍがｎになるまでループ本体内の処理を繰り返し実行するループ処理が記述される。
【０３０４】
ソースコード４２００の８行目には、代入文「ｓ（ｉ，ｊ）＝ｓ（ｉ，ｊ）＋ａ（ｉ，ｋ，ｍ，ｌ）＊ｗ（ｋ，ｌ）＊ｖ（ｊ，ｍ）」が記述される。これにより、ソースコード４２００の８行目には、配列変数ｓ（ｉ，ｊ）の値に、配列変数ｓ（ｉ，ｊ）＋配列変数ａ（ｉ，ｋ，ｍ，ｌ）＊配列変数ｗ（ｋ，ｌ）＊配列変数ｖ（ｊ，ｍ）の値を代入する代入処理が記述される。
【０３０５】
このように、ソースコード４２００の１〜１３行目は、入れ子構造になった複数のループ文の集まりが記述された多重ループ箇所である。また、ソースコード４２００の１〜３，１２，１３行目は、変数ｉ，ｊを変化させ、縮約演算が行われる配列変数ｓ（ｉ，ｊ）を切り替え、切り替えた配列変数ｓ（ｉ，ｊ）を初期化する、入れ子構造になったループ文の集まりが記述された初期化ループ箇所である。
【０３０６】
また、ソースコード４２００の４〜１１行目は、初期化された配列変数ｓ（ｉ，ｊ）に対する代入演算を繰り返すことによって、配列変数ｓ（ｉ，ｊ）に対する縮約演算を行う、入れ子構造になったループ文の集まりが記述された縮約演算ループ箇所である。
【０３０７】
（部分式を正準化する一例）
図４３〜図４５は、部分式を正準化する一例を示す説明図である。情報処理装置１００は、実施の形態１と同様にして部分式を抽出した後に、部分式内の項を並べ替えて、部分式内の変数に番号を割り当てて、部分式を正準化する。
【０３０８】
図４３において、情報処理装置１００は、例えば、部分式内の項を並べ替えた結果を記憶するリスト１０を生成する。次に、情報処理装置１００は、部分式のリストから部分式を抽出する。
【０３０９】
そして、情報処理装置１００は、部分式の項を、ＡＳＴにおける演算子を属性とするノードの深さが浅い順に並べ替える。また、情報処理装置１００は、深さが同じ部分式の項であれば、演算子の優先度の高い順に並べ替える。また、情報処理装置１００は、優先度が同じ部分式の項であれば、参照される変数にコンパイラが割り当てた番号、またはアルファベットの順に並べ替える。
【０３１０】
情報処理装置１００は、並べ替えた順序にしたがって、各変数に番号を割り当てる。情報処理装置１００は、例えば、変数ａ（ｉ，ｋ，ｊ，ｌ）に番号１を割り当てる。情報処理装置１００は、変数ｗ（ｋ，ｌ）に番号２を割り当てる。情報処理装置１００は、変数ｖ（ｋ，ｌ）に番号３を割り当てる。ここで、情報処理装置１００は、部分式のうちに定数があれば、変数と同様に扱い、番号を割り当て、変数よりも前に並べる。
【０３１１】
図４４において、情報処理装置１００は、ループ変数について、部分式の先頭から出現した順番にしたがって、番号を割り当てる。このとき、情報処理装置１００は、交換可能な演算子の列で結合された同一の配列変数のインデックスについては、出現したとして扱わない。ここで、ループ変数については、部分式ごとに出現した順番にしたがって割り当てるため、異なる部分式において同じ番号が割り当てられた変数であっても、異なる変数である場合がある。
【０３１２】
さらに、情報処理装置１００は、ループ変数に番号を割り当てた後に、再度、部分式の項を並べ替える。そして、情報処理装置１００は、番号を割り当てていないループ変数があれば、番号を割り当てる。情報処理装置１００は、番号を割り当てた結果を、リスト１１に記憶する。
【０３１３】
図４５において、情報処理装置１００は、実施の形態１と同様に、分割部分式のリストを生成する。情報処理装置１００は、分割部分式のリスト、およびリスト１１に基づいて、番号が割り当てられた分割部分式のリスト１２を生成する。
【０３１４】
（共通する部分式を特定する一例）
図４６は、共通する部分式を特定する一例を示す説明図である。情報処理装置１００は、実施の形態１と同様にしてスカラー変数を分類した後に、共通する部分式を特定する。
【０３１５】
図４６において、情報処理装置１００は、少なくとも変数および変数間の関係が同一である部分式の組み合わせを記憶するリスト１３を生成する。ここでは、説明の簡略化のため、組み合わせ可能な部分式が３つ以上ある場合には、２つの部分式の組み合わせを記憶するレコードを複数用いて実現することにする。
【０３１６】
情報処理装置１００は、リスト１２の分割部分式のうち、異なるアドレスに対応付けられた分割部分式の組み合わせであって、少なくとも変数および変数間の関係が同一である部分式の組み合わせを抽出して、リスト１３に追加する。また、情報処理装置１００は、リスト１２の分割部分式のうち、同じレコードに記憶された分割部分式の組み合わせであって、少なくとも変数および変数間の関係が同一である部分式の組み合わせを抽出して、リスト１３に追加する。
【０３１７】
その後、情報処理装置１００は、実施の形態１と同様に、削減量を算出する。このとき、情報処理装置１００は、変数および変数間の関係が同一である分割部分式の組み合わせのそれぞれを縮約演算した場合の演算結果を一度にまとめて算出する場合については、組み合わせの一方の演算量を０として扱う。さらに、情報処理装置１００は、実施の形態１と同様に、ループ最適化する部分式を決定して、ソースコード４２００を最適化する。
【０３１８】
（ソースコード４２００を最適化する一例）
図４７は、ソースコード４２００を最適化する一例を示す説明図である。図４７の例は、ソースコード４２００を最適化して得られたソースコード４７００の一例である。
【０３１９】
図４７の例では、ソースコード４７００の１〜１０行目は、図１８に示したソースコード１８００の１〜１０行目と同様の処理内容が記述された箇所であるため、説明を省略する。このように、ソースコード４７００の１〜１０行目は、ソースコード内の複数の箇所の部分式と置換可能な変数「ｔ（ｉ，ｊ）」についての計算を行う、入れ子構造になったループ文の集まりが記述された縮約演算ループ箇所である。
【０３２０】
ソースコード４７００の１１〜１５行目は、初期化処理に対応する箇所を除いて、図１８に示したソースコード１８００の１１〜１８行目と同様の処理内容が記述された箇所であるため、説明を省略する。このように、ソースコード４７００の１１〜１５行目には、配列変数ｓ（ｉ，ｊ）に対する縮約演算を行う、入れ子構造になったループ文の集まりが記述された縮約演算ループ箇所である。
【０３２１】
ソースコード４７００の１６〜２２行目は、初期化処理に対応する箇所を除いて、図１８に示したソースコード１８００の１１〜１８行目と同様の処理内容が記述された箇所であるため、説明を省略する。このように、ソースコード４７００の１６〜２２行目には、配列変数ｓ（ｉ，ｊ）に対する縮約演算を行う、入れ子構造になったループ文の集まりが記述された縮約演算ループ箇所である。
【０３２２】
（実施の形態２にかかるコンパイル処理手順の一例）
実施の形態２にかかるコンパイル処理手順の一例は、図１９に示した実施の形態１にかかるコンパイル処理手順の一例と同様であるため、説明を省略する。また、コンパイル処理手順によって呼び出される各種処理手順は、削減量算出処理手順および最適化対象決定処理手順を除いて、図２１〜図４０に示した実施の形態１にかかる各種処理手順と同様であるため、説明を省略する。
【０３２３】
（実施の形態２にかかる削減量算出処理手順の一例）
次に、図４８を用いて、実施の形態２にかかる削減量算出処理手順の一例について説明する。
【０３２４】
図４８は、実施の形態２にかかる削減量算出処理手順の一例を示すフローチャートである。図４８において、情報処理装置１００は、分割部分式のリストに基づいて、正準化された分割部分式のリストを生成する（ステップＳ４８０１）。
【０３２５】
次に、情報処理装置１００は、正準化された分割部分式のリストに基づいて、変数および変数間の関係が同一である分割部分式の組み合わせのリストを生成する（ステップＳ４８０２）。そして、情報処理装置１００は、正準化された分割部分式のリストのレコードの組み合わせを選択する（ステップＳ４８０３）。
【０３２６】
次に、情報処理装置１００は、選択したレコードの組み合わせから分割部分式を抽出する（ステップＳ４８０４）。そして、情報処理装置１００は、抽出した分割部分式のうち、変数および変数間の関係が同一である分割部分式の組み合わせがあれば、いずれかの分割部分式を残して、他の分割部分式を削除する（ステップＳ４８０５）。
【０３２７】
次に、情報処理装置１００は、残った分割部分式のうちのいずれかの分割部分式を選択して、対象分割部分式に設定する（ステップＳ４８０６）。そして、情報処理装置１００は、算出サブ処理を実行する（ステップＳ４８０７）。
【０３２８】
次に、情報処理装置１００は、選択した分割部分式の演算量に、算出サブ処理によって算出した合計演算量を設定する（ステップＳ４８０８）。そして、情報処理装置１００は、すべての分割部分式を選択したか否かを判定する（ステップＳ４８０９）。ここで、未選択の分割部分式がある場合（ステップＳ４８０９：Ｎｏ）、情報処理装置１００は、ステップＳ４８０６の処理に戻る。
【０３２９】
一方で、すべての分割部分式を選択した場合（ステップＳ４８０９：Ｙｅｓ）、情報処理装置１００は、すべてのレコードの組み合わせを選択したか否かを判定する（ステップＳ４８１０）。ここで、未選択のレコードがある場合（ステップＳ４８１０：Ｎｏ）、情報処理装置１００は、ステップＳ４８０３の処理に戻る。
【０３３０】
一方で、すべてのレコードの組み合わせを選択した場合（ステップＳ４８１０：Ｙｅｓ）、情報処理装置１００は、削減量算出処理を終了する。これにより、情報処理装置１００は、削減量を算出することができる。
【０３３１】
（実施の形態２にかかる最適化対象決定処理手順の一例）
次に、実施の形態２にかかる最適化対象決定処理手順の一例について説明する。情報処理装置１００は、正準化された分割部分式のリストのレコードの組み合わせのうち、元の演算量から、算出された分割部分式の演算量の合計を減算した差分が最大の組み合わせを、最適化対象に決定する。
【０３３２】
以上説明したように、情報処理装置１００によれば、ループ箇所内にある第３変数に縮約演算する第４式のうち、第１式のうちの部分式と少なくとも変数および変数間の関係が同一である他の部分式を特定することができる。そして、情報処理装置１００によれば、第１コード、第１式のうちの部分式が第２変数に置換された第３式についての計算を繰り返し、かつ、第４式のうちの他の部分式が第２変数に置換された第５式についての計算を繰り返す第２コードを生成することができる。
【０３３３】
これにより、情報処理装置１００は、縮約演算する第１式の部分式、および縮約演算する第４式の他の部分式のそれぞれを縮約演算した場合の演算結果を、一度にまとめて算出することができる第２式を含むループ処理を示す第１コードを生成することができる。そして、情報処理装置１００によれば、ソースコードのうちのループ箇所を、第１コードと、第１コードでの演算結果を利用した第１式を含むループ処理および第１コードでの演算結果を利用した第４式を含むループ処理を示す第２コードとに変換することができる。これにより、情報処理装置１００は、複数のループ処理を通して計算される複数の式の集まりに共通して定数として扱うことが可能な式について、縮約演算をまとめて行うことができ、ソフトウェアの実行時の演算量を低減させることができる。
【０３３４】
なお、本実施の形態で説明したコンパイル方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本コンパイルプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本コンパイルプログラムは、インターネット等のネットワークを介して配布してもよい。
【０３３５】
上述した各実施の形態に関し、さらに以下の付記を開示する。
【０３３６】
（付記１）ソフトウェアのプログラムコードのうち、第１変数に対して縮約演算する第１式についての計算を繰り返すループ箇所を特定し、
前記第１式のうちの部分式を第２変数に対して縮約演算する第２式についての計算を繰り返す第１コード、および、前記第１式のうちの前記部分式が前記第２変数に置換された第３式についての計算を繰り返す第２コードを生成し、
前記プログラムコードのうちの前記ループ箇所を前記第１コードおよび前記第２コードに変換したプログラムコードを出力する、
制御部を有することを特徴とする情報処理装置。
【０３３７】
（付記２）前記制御部は、
前記ループ箇所内にある第３変数に縮約演算する第４式のうち、前記部分式と少なくとも変数および変数間の関係が同一である他の部分式を特定し、
前記第１コード、前記第１式のうちの前記部分式が前記第２変数に置換された前記第３式についての計算を繰り返し、かつ、前記第４式のうちの前記他の部分式が前記第２変数に置換された第５式についての計算を繰り返す前記第２コードを生成する、
ことを特徴とする付記１に記載の情報処理装置。
【０３３８】
（付記３）前記制御部は、
前記第１式のうちの各部分式について、当該部分式を縮約演算する前記第２式についての計算の種類および繰り返し回数と、当該部分式が置換された前記第３式についての計算の種類および繰り返し回数とを特定し、
特定した前記種類および前記繰り返し回数に基づいて、前記第１式のうちの各部分式について、当該部分式を縮約演算する前記第２式についての計算を繰り返す演算量、および、当該部分式が置換された前記第３式についての計算を繰り返す演算量の合計と、前記ループ箇所の演算量との差分を算出し、
算出した前記差分に基づいて、前記第１式のうちのいずれかの部分式を選択し、
選択した前記いずれかの部分式について前記第１コードおよび前記第２コードを生成する、
ことを特徴とする付記１または２に記載の情報処理装置。
【０３３９】
（付記４）前記部分式は、前記第１変数に縮約演算する単位部分式の一部であって、
前記制御部は、
前記第１式についての計算を繰り返す条件に使用される変数を、少なくとも前記第１変数のインデックスに使用される変数、前記第１変数の初期化式についての計算を繰り返す条件に使用される変数、および前記部分式と前記単位部分式の残余の部分式とに共通してインデックスに使用される変数のいずれかと一致する第１種別の変数と、前記第１種別の変数とは異なる第２種別の変数とに分類し、
分類した前記第１種別の変数および前記第２種別の変数に基づいて、前記第１式のうちの各部分式について、当該部分式を縮約演算する前記第２式についての計算の種類および繰り返し回数と、当該部分式が置換された前記第３式についての計算の種類および繰り返し回数とを特定する、
ことを特徴とする付記３に記載の情報処理装置。
【０３４０】
（付記５）前記制御部は、
前記第１式のうちの各部分式について、当該部分式を縮約演算する前記第２式についての計算の繰り返し条件に使用する変数および繰り返し回数と、当該部分式が置換された前記第３式についての計算の繰り返し条件に使用する変数および繰り返し回数とを特定し、
特定した前記変数および前記繰り返し回数に基づいて、ループ文を用いて前記第１コードを生成し、ループ文を用いて前記第２コードを生成する、
ことを特徴とする付記１〜４のいずれか一つに記載の情報処理装置。
【０３４１】
（付記６）前記部分式は、前記第１変数に縮約演算する単位部分式の一部であって、
前記制御部は、
前記第１式についての計算を繰り返す条件に使用される変数を、少なくとも前記第１変数のインデックスに使用される変数、前記第１変数の初期化式についての計算を繰り返す条件に使用される変数、および前記部分式と前記単位部分式の残余の部分式とに共通してインデックスに使用される変数のいずれかと一致する第１種別の変数と、前記第１種別の変数とは異なる第２種別の変数とに分類し、
分類した前記第１種別の変数および前記第２種別の変数に基づいて、前記第１式のうちの各部分式について、当該部分式を縮約演算する前記第２式についての計算の繰り返し条件に使用する変数および繰り返し回数と、当該部分式が置換された前記第３式についての計算の繰り返し条件に使用する変数および繰り返し回数とを特定する、
ことを特徴とする付記５に記載の情報処理装置。
【０３４２】
（付記７）前記第１式は、第１演算子により前記第１変数に対して縮約演算する式であって、
前記第２式は、前記部分式を前記第１演算子により前記第２変数に対して縮約演算する式である、
ことを特徴とする付記１〜４のいずれか一つに記載の情報処理装置。
【０３４３】
（付記８）コンピュータが、
ソフトウェアのプログラムコードのうち、第１変数に対して縮約演算する第１式についての計算を繰り返すループ箇所を特定し、
前記第１式のうちの部分式を第２変数に対して縮約演算する第２式についての計算を繰り返す第１コード、および、前記第１式のうちの前記部分式が前記第２変数に置換された第３式についての計算を繰り返す第２コードを生成し、
前記プログラムコードのうちの前記ループ箇所を前記第１コードおよび前記第２コードに変換したプログラムコードを出力する、
処理を実行することを特徴とするコンパイル方法。
【０３４４】
（付記９）コンピュータに、
ソフトウェアのプログラムコードのうち、第１変数に対して縮約演算する第１式についての計算を繰り返すループ箇所を特定し、
前記第１式のうちの部分式を第２変数に対して縮約演算する第２式についての計算を繰り返す第１コード、および、前記第１式のうちの前記部分式が前記第２変数に置換された第３式についての計算を繰り返す第２コードを生成し、
前記プログラムコードのうちの前記ループ箇所を前記第１コードおよび前記第２コードに変換したプログラムコードを出力する、
処理を実行させることを特徴とするコンパイルプログラム。
【符号の説明】
【０３４５】
１〜１３  リスト
１００  情報処理装置
１０１，１０２，４００，１８００，４１０１，４１０２，４２００，４７００  ソースコード
２００  バス
２０１  ＣＰＵ
２０２  メモリ
２０３  Ｉ／Ｆ
２０４  ディスクドライブ
２０５  ディスク
２１０  ネットワーク
３０１  特定部
３０２  分類部
３０３  算出部
３０４  選択部
３０５  生成部
３０６  出力部
【図１】
0006554959.tif 000002
【図２】
0006554959.tif 000003
【図３】
0006554959.tif 000004
【図４】
0006554959.tif 000005
【図５】
0006554959.tif 000006
【図６】
0006554959.tif 000007
【図７】
0006554959.tif 000008
【図８】
0006554959.tif 000009
【図９】
0006554959.tif 000010
【図１０】
0006554959.tif 000011
【図１１】
0006554959.tif 000012
【図１２】
0006554959.tif 000013
【図１３】
0006554959.tif 000014
【図１４】
0006554959.tif 000015
【図１５】
0006554959.tif 000016
【図１６】
0006554959.tif 000017
【図１７】
0006554959.tif 000018
【図１８】
0006554959.tif 000019
【図１９】
0006554959.tif 000020
【図２０】
0006554959.tif 000021
【図２１】
0006554959.tif 000022
【図２２】
0006554959.tif 000023
【図２３】
0006554959.tif 000024
【図２４】
0006554959.tif 000025
【図２５】
0006554959.tif 000026
【図２６】
0006554959.tif 000027
【図２７】
0006554959.tif 000028
【図２８】
0006554959.tif 000029
【図２９】
0006554959.tif 000030
【図３０】
0006554959.tif 000031
【図３１】
0006554959.tif 000032
【図３２】
0006554959.tif 000033
【図３３】
0006554959.tif 000034
【図３４】
0006554959.tif 000035
【図３５】
0006554959.tif 000036
【図３６】
0006554959.tif 000037
【図３７】
0006554959.tif 000038
【図３８】
0006554959.tif 000039
【図３９】
0006554959.tif 000040
【図４０】
0006554959.tif 000041
【図４１】
0006554959.tif 000042
【図４２】
0006554959.tif 000043
【図４３】
0006554959.tif 000044
【図４４】
0006554959.tif 000045
【図４５】
0006554959.tif 000046
【図４６】
0006554959.tif 000047
【図４７】
0006554959.tif 000048
【図４８】
0006554959.tif 000049