(57)【要約】 【課題】リスト構造を形成し、配列をそのメンバに持つ構造型データの配列要素を処理するループ制御文を高速に実行できるように変形する。【解決手段】多重ループ検出部１４１は、原始プログラム２を解析して、リスト構造の構成要素である構造型データをたどるループ制御文と、そのループ制御文内にある、構造型データのメンバである配列を繰り返し定義、引用するループ制御文からなる多重ループ制御文を検出する。そして、多重ループ変形部１４２は、多重ループ検出部１４１によって検出された多重ループ制御文内の内側のループ制御文を、構造型データのメンバである配列の配列要素のアドレスを取得して作業配列の要素に順次に登録するループ制御文に置換し、内側のループ制御文が行っていた処理を、作業配列に登録されたアドレス先に対して行うようにするループ制御文を、多重ループ制御文の後に作成する。【選択図】図２
2008123249.tif 000002
【特許請求の範囲】
【請求項１】
リスト構造データと要素処理用ループ制御文と配列要素処理用ループ制御文とを含む原始プログラムをコンパイルしてオブジェクトプログラムを生成するコンパイル装置であって、
前記リスト構造データは複数の要素から構成され、各要素は配列を含み、
前記要素処理用ループ制御文は、前記複数の要素を辿りつつ該要素を処理する手順を定義し、
前記配列要素処理用ループ制御文は、前記要素処理用ループ制御文内に位置し、前記各要素に含まれている配列の配列要素を辿りながら辿った配列要素を処理する手順を定義し、
前記コンパイル装置は、
前記原始プログラムを解析して、前記要素処理用ループ制御文を検出する外側ループ検出手段と、
前記原始プログラムを解析して、前記配列要素処理用ループ制御文を検出する内側ループ検出手段と、
作業用の配列を生成する手順を定義した作業配列定義文を、前記原始プログラムに追加する作業配列生成手段と、
前記各要素に含まれている配列の配列要素と、前記作業用の配列の配列要素とを辿りながら前記リスト構造データを構成する各要素に含まれている配列の配列要素のアドレスを前記作業用の配列に順次に登録する手順を定義するアドレス登録用ループ制御文を生成するアドレス登録用ループ制御文生成手段と、
前記内側ループ検出手段で検出した配列要素処理用ループ制御文を、前記アドレス登録用ループ制御文生成手段で生成したアドレス登録用ループ制御文に置換するループ制御文置換手段と、
前記アドレス登録用ループ制御文を実行することにより前記作業用の配列に登録されたアドレスで特定される配列要素を、前記配列要素処理用ループ制御文で処理するための手順を定義する作業配列処理用ループ制御文、を作成する作業配列処理用ループ制御文作成手段と、
前記作業配列処理用ループ制御文作成手段で作成した作業配列処理用ループ制御文を、前記原始プログラムの要素処理用ループ制御文の後ろに追加するループ制御文追加手段と、
前記作業配列定義文と前記作業配列処理用ループ制御文とが追加され、前記配列要素処理用ループ制御文がアドレス登録用ループ制御文に置換された原始プログラムをコンパイルするコンパイル手段と、
を備えることを特徴とするコンパイル装置。
【請求項２】
前記ループ制御文置換手段によって内部に位置する前記配列要素処理用ループ制御文が置換される前の要素処理用ループ制御文を、前記原始プログラムに追加する要素処理用ループ制御文追加手段と、
所定の条件によって、前記ループ制御文置換手段によって内部に位置する前記配列要素処理用ループ制御文が置換された要素処理用ループ制御文と追加された前記作業配列定義文と前記作業配列処理用ループ制御文とによって定義されている手順で処理を実行するのか、前記要素処理用ループ制御文追加手段で追加された要素処理用ループ制御文によって定義されている手順で処理を実行するのかを切り分ける処理を定義する条件制御文を作成し、前記原始プログラムに追加する条件制御文作成手段とをさらに備え、
前記コンパイル手段は、前記作業配列定義文と前記作業配列処理用ループ制御文と前記条件制御文とが追加され、前記配列要素処理用ループ制御文がアドレス登録用ループ制御文に置換された原始プログラムをコンパイルする、
ことを特徴とする、請求項１に記載のコンパイル装置。
【請求項３】
前記所定の条件は、前記リスト構造データ全体に渡る要素に含まれている配列の配列要素の数が、所定の数を超えているか否かである、
ことを特徴とする、請求項２に記載のコンパイル装置。
【請求項４】
リスト構造データと要素処理用ループ制御文と配列要素処理用ループ制御文とを含む原始プログラムをコンピュータが高速に処理できるように変形する、ループの高速化方法であって、
前記リスト構造データは複数の要素から構成され、各要素は配列を含み、
前記要素処理用ループ制御文は、前記複数の要素を辿りつつ該要素を処理する手順を定義し、
前記配列要素処理用ループ制御文は、前記要素処理用ループ制御文内に位置し、前記各要素に含まれている配列の配列要素を辿りながら辿った配列要素を処理する手順を定義し、
前記ループの高速化方法は、
前記原始プログラムを解析して、前記要素処理用ループ制御文を検出する外側ループ検出ステップと、
前記原始プログラムを解析して、前記配列要素処理用ループ制御文を検出する内側ループ検出ステップと、
作業用の配列を生成する手順を定義した作業配列定義文を、前記原始プログラムに追加する作業配列生成ステップと、
前記各要素に含まれている配列の配列要素と、前記作業用の配列の配列要素とを辿りながら前記リスト構造データを構成する各要素に含まれている配列の配列要素のアドレスを前記作業用の配列に順次に登録する手順を定義するアドレス登録用ループ制御文を生成するアドレス登録用ループ制御文生成ステップと、
前記内側ループ検出ステップで検出した配列要素処理用ループ制御文を、前記アドレス登録用ループ制御文生成ステップで生成したアドレス登録用ループ制御文に、置換するループ制御文置換ステップと、
前記アドレス登録用ループ制御文を実行することにより前記作業用の配列に登録されたアドレスで特定される配列要素を、前記配列要素処理用ループ制御文で処理するための手順を定義する作業配列処理用ループ制御文を作成する作業配列処理用ループ制御文作成ステップと、
前記作業配列処理用ループ制御文作成ステップで作成した作業配列処理用ループ制御文を、前記原始プログラムの要素処理用ループ制御文の後ろに追加するループ制御文追加ステップと、
前記作業配列定義文と前記作業配列処理用ループ制御文とが追加され、前記配列要素処理用ループ制御文がアドレス登録用ループ制御文に置換された原始プログラムをコンパイルするコンパイルステップと、
を備えることを特徴とするループの高速化方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンパイル装置、および、ループの高速化方法に関する。
【背景技術】
【０００２】
一般的に、プログラム言語では、異なるデータ型を１つにまとめることが可能な、構造型データを用いることができる。上述の構造型データは、自己と同じ型の構造型データの先頭アドレスを示すポインタを、メンバとして持つことが可能である。よって、そのようなポインタをメンバとして持つ構造型データは、自己のメンバである上述のポインタを参照することで、自己と同じ型である構造型データにアクセスすることができる。そのため、複数のそのような構造型データは、各構造型データのメンバである上述のポインタで各構造型データ同士が連結されたリスト構造を形成することが可能となる。
特許文献１は、リスト構造の構成要素である各構造型データをたどりながら、各構造型データのメンバに対して処理を行うループ制御文が含まれている原始プログラムから、コンピュータが高速に処理を実行することが可能なオブジェクトプログラムを作成するコンパイル装置を開示している。
【０００３】
図３（ａ）は、Ｃ言語で記述された原始プログラムの例を示す図である。文Ａ−１は、構造型データＡのデータ宣言文である。構造型データＡは、メンバに自己と同じデータ型である構造型データＡの先頭アドレスを示すポインタ「ｎｅｘｔ」を有している。また、構造型データＡは、メンバにｉｎｔ型変数ｎおよび、配列ａを持つ。ｉｎｔ型変数ｎの値は、配列ａの要素数を示す。
文Ａ−２は、複数の構造型データＡによって形成されるリスト構造の各構成要素をたどるループ制御文である。ループ制御文Ａ−２に含まれるループ制御文Ａ−３は、構造型データＡのメンバである配列ａの各配列要素を定義、引用するループ制御文である。この多重ループ制御文（Ａ−２、Ａ−３）により、リスト構造の構成要素である全ての構造型データＡに対して、メンバである配列ａの配列要素が定義、引用される。
【０００４】
図３（ｂ）は、図３（ａ）に示す原始プログラムにおける、複数の構造型データＡにより形成されるリスト構造および、該構造型データＡのメンバとの関係を模式的に示した図である。図３（ａ）に示すループ制御文Ａ−２は、複数の構造型データＡが形成するリスト構造の先頭（ｆｉｒｓｔ）から、その終わり（ｌａｓｔ）までの各要素をたどるループ制御文である。図３（ａ）に示すループ制御文Ａ−３は、構造型データＡのメンバである配列ａの先頭の配列要素（ｉ＝０）から、その末尾の配列要素（ｉ＝ｎ−１）までのｎ個の配列要素を定義、引用するループ制御文である。なお、リスト構造の構成要素である各構造型データＡのメンバｎの値（ｎ１、ｎ２、ｎ３・・・）は各自異なっているため、それに対応する配列ａの要素数も各自異なることになる。
【特許文献１】特開２００３−３３７７０７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
特許文献１に開示されているような従来のコンパイル装置では、上述した図３（ａ）に示したような原始プログラムをコンパイルしてオブジェクトプログラムを生成する場合、多重ループ制御文中で構造型データのメンバである配列の配列要素を定義、引用する処理をオーバーラップして処理するような最適化（パイプライニング化）が制限されるという問題を有する。
その理由を図３（ａ）に示す原始プログラムを例に説明すると、ループ制御文Ａ−３で、ある構造型データＡに対して、メンバである配列ａの配列要素を定義、引用する処理中に、ループ制御文Ａ−２で処理されるリスト構造の次の構成要素である構造型データＡのメンバである配列ａの配列要素のアドレスを得ることができないため、異なる構造型データＡの間でそのメンバである配列ａの要素を定義、引用する処理をオーバーラップして処理することができないからである。
【０００６】
また、特許文献１に開示されているような従来のコンパイル装置では、上述した図３（ａ）に示したような原始プログラムをコンパイルしてオブジェクトプログラムを生成する場合、多重ループ制御文中で構造型データのメンバである配列の配列要素を定義、引用する処理を複数の配列要素に対して同時に行うような最適化（並列化）が制限されるという問題を有する。
その理由を図３（ａ）に示す原始プログラムを例に説明すると、ループ制御文Ａ−３で、ある構造型データＡに対して、メンバである配列ａの各要素を定義、引用する処理中に、ループ制御文Ａ−２で処理されるリスト構造の他の構成要素である構造型データＡのメンバである配列ａの配列要素のアドレスを得ることができないため、異なる構造型データＡの間でそのメンバである配列ａの配列要素を定義、引用する処理を並列に処理することができないからである。
【０００７】
また、特許文献１に開示されているような従来のコンパイル装置では、上述した図３（ａ）に示したような原始プログラムをコンパイルしてオブジェクトプログラムを生成する場合、２重ループ制御文中で構造型データのメンバである配列の要素を定義、引用する処理のうち、連続した繰り返し処理をまとめて同時に処理するような最適化（ベクトル化）が制限されるという問題を有する。  その理由を図３（ａ）に示す原始プログラムを例に説明すると、ループ制御文Ａ−３で、ある構造型データＡに対して、メンバである配列ａの配列要素を定義、引用する処理中に、ループ制御文Ａ−２で処理されるリスト構造の次の構成要素である構造型データＡのメンバである配列ａの配列要素のアドレスを得ることができないため、異なる構造型データＡの間でそのメンバである配列ａの要素を定義、引用する処理を連続した繰り返し処理としてまとめて処理することができないからである。
【０００８】
本発明は上述した問題に鑑みてなされたもので、メンバに配列を持つ構造型データを構成要素とするリスト構造型データにおいて、該リスト構造の構成要素である各構造型データをたどるループ制御文中に、該各構造型データのメンバである配列の各配列要素をたどるループ制御文が含まれている構造の２重ループ制御文を含む原始プログラムから、最適化（ソフトウェアパイプライニング化、並列化、ベクトル化）により、より高速に実行することが可能なオブジェクトプログラムを生成することができるコンパイル装置、ループの高速化方法、およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明の第１の観点にかかるコンパイル装置は、リスト構造データと要素処理用ループ制御文と配列要素処理用ループ制御文とを含む原始プログラムをコンパイルしてオブジェクトプログラムを生成するコンパイル装置であって、
前記リスト構造データは複数の要素から構成され、各要素は配列を含み、
前記要素処理用ループ制御文は、前記複数の要素を辿りつつ該要素を処理する手順を定義し、
前記配列要素処理用ループ制御文は、前記要素処理用ループ制御文内に位置し、前記各要素に含まれている配列の配列要素を辿りながら辿った配列要素を処理する手順を定義し、
前記コンパイル装置は、
前記原始プログラムを解析して、前記要素処理用ループ制御文を検出する外側ループ検出手段と、
前記原始プログラムを解析して、前記配列要素処理用ループ制御文を検出する内側ループ検出手段と、
作業用の配列を生成する手順を定義した作業配列定義文を、前記原始プログラムに追加する作業配列生成手段と、
前記各要素に含まれている配列の配列要素と、前記作業用の配列の配列要素とを辿りながら前記リスト構造データを構成する各要素に含まれている配列の配列要素のアドレスを前記作業用の配列に順次に登録する手順を定義するアドレス登録用ループ制御文を生成するアドレス登録用ループ制御文生成手段と、
前記内側ループ検出手段で検出した配列要素処理用ループ制御文を、前記アドレス登録用ループ制御文生成手段で生成したアドレス登録用ループ制御文に置換するループ制御文置換手段と、
前記アドレス登録用ループ制御文を実行することにより前記作業用の配列に登録されたアドレスで特定される配列要素を、前記配列要素処理用ループ制御文で処理するための手順を定義する作業配列処理用ループ制御文、を作成する作業配列処理用ループ制御文作成手段と、
前記作業配列処理用ループ制御文作成手段で作成した作業配列処理用ループ制御文を、前記原始プログラムの要素処理用ループ制御文の後ろに追加するループ制御文追加手段と、
前記作業配列定義文と前記作業配列処理用ループ制御文とが追加され、前記配列要素処理用ループ制御文がアドレス登録用ループ制御文に置換された原始プログラムをコンパイルするコンパイル手段と、
を備えることを特徴とする。
【００１０】
前記ループ制御文置換手段によって内部に位置する前記配列要素処理用ループ制御文が置換される前の要素処理用ループ制御文を、前記原始プログラムに追加する要素処理用ループ制御文追加手段と、
所定の条件によって、前記ループ制御文置換手段によって内部に位置する前記配列要素処理用ループ制御文が置換された要素処理用ループ制御文と追加された前記作業配列定義文と前記作業配列処理用ループ制御文とによって定義されている手順で処理を実行するのか、前記要素処理用ループ制御文追加手段で追加された要素処理用ループ制御文によって定義されている手順で処理を実行するのかを切り分ける処理を定義する条件制御文を作成し、前記原始プログラムに追加する条件制御文作成手段とをさらに備え、
前記コンパイル手段は、前記作業配列定義文と前記作業配列処理用ループ制御文と前記条件制御文とが追加され、前記配列要素処理用ループ制御文がアドレス登録用ループ制御文に置換された原始プログラムをコンパイルしてもよい。
【００１１】
前記所定の条件は、前記リスト構造データ全体に渡る要素に含まれている配列の配列要素の数が、所定の数を超えているか否かであってもよい。
【００１２】
上記目的を達成するため、本発明の第２の観点にかかるループの高速化方法は、
リスト構造データと要素処理用ループ制御文と配列要素処理用ループ制御文とを含む原始プログラムをコンピュータが高速に処理できるように変形する、ループの高速化方法であって、
前記リスト構造データは複数の要素から構成され、各要素は配列を含み、
前記要素処理用ループ制御文は、前記複数の要素を辿りつつ該要素を処理する手順を定義し、
前記配列要素処理用ループ制御文は、前記要素処理用ループ制御文内に位置し、前記各要素に含まれている配列の配列要素を辿りながら辿った配列要素を処理する手順を定義し、
前記ループの高速化方法は、
前記原始プログラムを解析して、前記要素処理用ループ制御文を検出する外側ループ検出ステップと、
前記原始プログラムを解析して、前記配列要素処理用ループ制御文を検出する内側ループ検出ステップと、
作業用の配列を生成する手順を定義した作業配列定義文を、前記原始プログラムに追加する作業配列生成ステップと、
前記各要素に含まれている配列の配列要素と、前記作業用の配列の配列要素とを辿りながら前記リスト構造データを構成する各要素に含まれている配列の配列要素のアドレスを前記作業用の配列に順次に登録する手順を定義するアドレス登録用ループ制御文を生成するアドレス登録用ループ制御文生成ステップと、
前記内側ループ検出ステップで検出した配列要素処理用ループ制御文を、前記アドレス登録用ループ制御文生成ステップで生成したアドレス登録用ループ制御文に、置換するループ制御文置換ステップと、
前記アドレス登録用ループ制御文を実行することにより前記作業用の配列に登録されたアドレスで特定される配列要素を、前記配列要素処理用ループ制御文で処理するための手順を定義する作業配列処理用ループ制御文を作成する作業配列処理用ループ制御文作成ステップと、
前記作業配列処理用ループ制御文作成ステップで作成した作業配列処理用ループ制御文を、前記原始プログラムの要素処理用ループ制御文の後ろに追加するループ制御文追加ステップと、
前記作業配列定義文と前記作業配列処理用ループ制御文とが追加され、前記配列要素処理用ループ制御文がアドレス登録用ループ制御文に置換された原始プログラムをコンパイルするコンパイルステップと、
を備えることを特徴とする。
【発明の効果】
【００１３】
本発明の第１の効果は、構造型データのメンバである配列の配列要素の処理をオーバーラップして処理する最適化（ソフトウェアパイプライニング化）により、コンピュータがより高速に実行することが可能となるオブジェクトプログラムを作成するコンパイル装置等を提供することである。
【００１４】
本発明の第２の効果は、構造型データのメンバである配列の配列要素の処理のうち、連続した繰り返しの処理をまとめて行う最適化（ベクトル化）により、コンピュータがより高速に実行することが可能となるオブジェクトプログラムを作成するコンパイル装置等を提供することである。
【００１５】
本発明の第３の効果は、構造型データのメンバである配列の配列要素の処理のうち、連続した繰り返しの処理をまとめて行う最適化（ベクトル化）により、コンピュータがより高速に実行することが可能となるオブジェクトプログラムを作成するコンパイル装置等を提供することである。
【発明を実施するための最良の形態】
【００１６】
以下、本発明の実施の形態に係るコンパイル装置について図面を用いて詳細に説明する。
【００１７】
本発明の実施の形態に係るコンパイル装置１は、図１に示すように、操作部１１と表示部１２と主記憶部１３と制御部１４と記憶部１５と通信部１６を備える。
【００１８】
操作部１１は、キーボードやマウス等から構成され、様々な情報を入力したりするために使用する。表示部１２は、ディスプレイ等からなり、様々な情報の表示を行う。
【００１９】
主記憶部１３は、ＲＡＭ（Rondom Access Memory）等から構成され、制御部１４が処理を実行する際の作業領域となる。
【００２０】
制御部１４は、ＣＰＵ（Central Processing Unit）等から構成され、記憶部１５に予め記憶されているプログラムを読み出して実行することにより、コンパイル装置１全体の動作を制御する。また、制御部１４は、原始プログラムからオブジェクトプログラムを作成するコンパイル処理を実行する。コンパイル処理の詳細については後述する。
【００２１】
記憶部１５は、ハードディスク装置等から構成され、制御部１４がコンパイル処理を実行するために必要な各種プログラム等を格納する。また、記憶部１５は、コンパイル処理の対象となる原始プログラムおよび、コンパイル処理で生成されるオブジェクトプログラムを格納する。
【００２２】
通信部１６は、例えば、NIC（Network Interface Card）やルータ、モデム、などの通信装置から構成される。通信部１６は、通信ネットワークを介してコンパイル処理の対象となる原始プログラムの受信、又はコンパイル処理で生成されたオブジェクトプログラムの送信等をする。
【００２３】
コンパイル装置１の機能構成図を図２に示す。コンパイル装置１は、原始プログラム２をコンパイルして、オブジェクトプログラム３を生成するものである。コンパイル装置１は、多重ループ検出部１４１と、多重ループ変形部１４２とオブジェクトプログラム生成部１４３とを含んでいる。
【００２４】
多重ループ検出部１４１は、原始プログラム２を解析して、多重ループ変形部１４２で変形することが可能な多重ループ制御文を検出する。
【００２５】
多重ループ変形部１４２は、多重ループ検出部１４１が検出した多重ループ制御文を変形する。
【００２６】
オブジェクトプログラム生成部１４３は、原始プログラム２又は、多重ループ変形部１４２によって変形された原始プログラム２から、オブジェクトプログラム３を生成する。
【００２７】
次に、コンパイル装置１によって実行されるコンパイル処理の動作について説明する。
【００２８】
コンパイル装置１の操作部１１に、所定の原始プログラムに対してコンパイル処理を開始することを示す情報が入力され、該入力情報が制御部１４に送信されると、図６に示すコンパイル処理が開始される。
【００２９】
先ず、制御部１４は、コンパイルの対象となる原始プログラムから、コンピュータが高速に実行することができるオブジェクトプログラムを作成することができるように、原始プログラムに含まれるループ制御文を最適化するループ最適化処理を行う（ステップＳ１００）。
【００３０】
図７にループ最適化処理の詳細を示す。
まず、制御部１４は、コンパイルの対象となる原始プログラムを解析して、リスト構造を形成することが可能で、かつ配列をメンバに持つ構造型データが有るか否かを判別する（ステップＳ１１０）。リスト構造を形成することが可能な構造型データであるか否かの判断は、メンバに、自身と同じ型の構造型データの先頭アドレスを指し示すポインタを持つ構造型データが、原始プログラム内に定義されているか否かで判断する。
そのような構造型データがあると判別した場合（ステップＳ１１０；Ｙｅｓ）、制御部１４は、ステップＳ１２０に処理を移す。そのような構造型データがないと判別した場合（ステップＳ１１０；Ｎｏ）、制御部１４は、ループ最適化処理（ステップＳ１００）を終了して、オブジェクトプログラム作成処理（ステップＳ２００）に処理を移す。
なお、図３（ａ）に示す原始プログラムをループ最適化処理の対象とした場合は、原始プログラム中の構造型データＡの宣言文Ａ−１において、メンバに構造型データＡ自身と同じ型を持つ構造型データの先頭アドレスを指し示すポインタ「ｎｅｘｔ」と、配列ａとを有しているため、上述のステップＳ１１０ではＹｅｓと判断される。
【００３１】
ステップＳ１２０で、制御部１４は、原始プログラムを解析して、ステップＳ１１０でリスト構造を持つことが可能で、メンバに配列を持つと判別した構造型データを構成要素とするリスト構造の各構成要素をたどるループ制御文と、該ループ制御文内に配置されているループ制御文であって、該構造型データのメンバである配列の各配列要素を定義、引用する制御文とから構成される多重ループ制御文があるか否かを判別する。
【００３２】
そのような多重ループ制御文があると判別した場合（ステップＳ１２０；Ｙｅｓ）、制御部１４は、ステップＳ１３０に処理を移す。そのような多重ループ制御文がないと判別した場合（ステップＳ１２０；Ｎｏ）、制御部１４は、ループ最適化処理（ステップＳ１００）を終了して、オブジェクトプログラム作成処理（ステップＳ２００）に処理を移す。
なお、図３（ａ）に示す原始プログラムをループ最適化処理の対象とした場合は、構造型データＡが構成要素となるリスト構造の各構成要素をたどるループ制御文Ａ−２および、そのループ制御文Ａ−２内に構造型データＡのメンバである配列ａの各要素を定義、引用するループ制御文Ａ−３からなる、多重ループ制御文（Ａ−２、Ａ−３）があるために、上述のステップＳ１４０ではＹｅｓと判断される。
【００３３】
ステップＳ１３０で、制御部１４は、ステップＳ１２０で判別した多重ループ制御文を変形する。ステップＳ１３０の処理の動作について、図８のフローチャートを用いて詳細に説明する。なお、図３（ａ）に示す原始プログラムがこの多重ループ変形処理によって変形された場合の原始プログラムを示した図４（ａ）も用いて具体的な変形の例を適宜挙げながら説明する。
【００３４】
まず、多重ループ変形処理が開始されると、制御部１４は、構造型データのメンバである配列の配列要素の該リスト構造全体での総合計数を求めるループ制御文を作成し、作成したループ制御文を図７のステップＳ１２０で判別した多重ループ制御文の直前に挿入する（ステップＳ１３１）。
図４（ａ）に示す原始プログラムにおいては、ループ制御文Ｂ−１が上述のステップＳ１３１によって作成、挿入されたループ制御文に対応する。ループ制御文Ｂ−１は、複数の構造型データＡによって形成されるリスト構造の構成要素をたどり、構造型データＡのメンバである配列ａの配列要素の該リスト構造全体での総合計数を求めるループ制御文である。
【００３５】
次に、制御部１４は、作業配列の宣言文を作成し、ステップＳ１３１で作成したループ制御文の直後に挿入する（ステップＳ１３２）。なお、宣言する作業配列の配列要素の数は、ステップＳ１３２で挿入したループ制御文の実行によって求まる構造型データのメンバである配列の配列要素のリスト構造全体での総合計数と同じ数に設定する。
図４（ａ）に示す原始プログラムにおいては、宣言文Ｂ−２が上述のステップＳ１３１によって作成、挿入された作業配列の宣言文に対応する。宣言文Ｂ−２は、作業配列ｗｏｒｋ＿ａｒｒａｙの宣言文であり、上述したループ制御文Ｂ−１の実行によって求まる配列ａの配列要素のリスト構造全体での総合計数が、作業配列ｗｏｒｋ＿ａｒｒａｙの配列要素数として設定される。
【００３６】
次に、制御部１４は、図７のステップＳ１２０で判別した多重ループ制御文のうちの内側のループ制御文を、構造型データのメンバである配列の配列要素をたどって該配列要素のアドレスを取得し、取得したアドレスを作業配列の各配列要素に登録するループ制御文に置換する（ステップＳ１３３）。
図４（ａ）に示す原始プログラムにおいては、上述のステップＳ１３３の処理により、図３（ａ）に示す原始プログラム内のループ制御文Ａ−３が、図４（ａ）に示す原始プログラム内のループ制御文Ｂ−３に置換される。ループ制御文Ｂ−３は、構造型データＡのメンバである配列ａの配列要素をたどって、配列ａの各配列要素のアドレスを取得し、取得したアドレスを作業配列ｗｏｒｋ＿ａｒｒａｙの各配列要素に登録するループ制御文である。
【００３７】
次に、制御部１４は、作業配列の各配列要素をたどって、作業配列の各配列要素に登録されているアドレスからリスト構造を形成する構造型データのメンバである配列の各配列要素にアクセスし、図７のステップＳ１２０で判別した多重ループ制御文のうちの内側のループ制御文による処理を、アクセスした各配列要素に行うループ制御文を作成し、作成したループ制御文を図７のステップＳ１２０で判別した多重ループ制御文の直後に挿入し（ステップＳ１３４）、多重ループ変形処理（ステップＳ１３０）は終了し、ループ最適化処理（ステップＳ１００）は終了する。
図４（ａ）に示す原始プログラムにおいては、ループ制御文Ｂ−４が上述のステップＳ１３４によって生成されたループ制御文に対応する。ループ制御文Ｂ−４は、作業配列ｗｏｒｋ＿ａｒｒａｙの配列要素をたどり、作業配列ｗｏｒｋ＿ａｒｒａｙの各配列要素に登録されているアドレスから構造型データＡのメンバである配列ａの各配列要素にアクセスし、図３（ａ）に示す原始プログラム内のループ制御文Ａ−３の配列ａの配列要素の定義・引用を行う処理と等価な処理を行うためのループ制御文である。
【００３８】
ここで、多重ループ変形処理（ステップＳ１３０）によって変形された図４（ａ）に記載の原始プログラムにおいて、作業配列ｗｏｒｋ＿ａｒｒａｙと、複数の構造型データＡによって形成されるリスト構造と、構造型データＡのメンバである配列ａとの関係を模式的に表した図を図４（ｂ）に示す。この図より、リスト構造内の構成要素である構造型データＡ同士で不連続であった配列ａの配列要素のアドレスが、作業配列ｗｏｒｋ＿ａｒｒａｙにまとめて格納されることにより、連続したアドレスとなっていることが分かる。
【００３９】
図６に戻り、制御部１４は、原始プログラム又は、前述した多重ループ変形処理（ステップＳ１３０）によって変形された原始プログラムから、オブジェクトプログラムを作成する（ステップＳ２００）。
このオブジェクトプログラムの作成は、公知の手法によって行えばよい。すなわち、制御部１４は、原始プログラムからプリプロセスで中間コードを作成し、中間コードからアセンブリ言語を作成し、アセンブリ言語から機械語で記述されたオブジェクトプログラムを作成する。
以上でコンパイル処理は終了する。
【００４０】
このように、本発明の実施の形態に係るコンパイル装置１は、多重ループ制御文中で参照されるリスト構造の構成要素である構造型データのメンバである配列の配列要素のアドレスを１つの作業配列の各配列要素にまとめて格納する。そして、構造型データのメンバである配列の配列要素に対して行う定義・引用処理を、作業配列に格納されているアドレスにアクセスして行うことができるように原始プログラムを変形する。そして、そのように変形した原始プログラムからオブジェクトプログラムを作成する。
【００４１】
そのため、繰り返し処理をオーバーラップして処理する最適化（ソフトウェアパイプライニング化）において、リスト構造を構成する構造型データの間で、メンバである配列の配列要素を定義、引用する処理をオーバーラップして処理することが可能となる。よって、リスト構造の構成要素である各構造型データごとに行われていた処理の回数を減らせ、またオーバーラップさせて同時に処理する配列の要素を増やすことが可能となり、コンピュータがより高速に実行することが可能となるオブジェクトプログラムを作成することができる。
【００４２】
また、繰り返し処理を並列に処理する最適化（並列化）において、リスト構造を構成する構造型データの間で、メンバである配列の配列要素を定義、引用する処理を並列に処理することが可能となる。よって、リスト構造の構成要素である各構造型データごとに行われていた処理の回数を減らせ、また並列化して同時に処理する配列の要素を増やすことが可能となり、コンピュータがより高速に実行することが可能となるオブジェクトプログラムを作成することができる。
【００４３】
また、連続する繰り返し処理を同時に行う最適化（ベクトル化）において、リスト構造を構成する構造型データの間で、メンバである配列の配列要素を定義、引用する処理を連続する繰り返し処理として同時に処理することが可能となる。よって、リスト構造の構成要素である各構造型データごとに行われていた処理の回数を減らせ、またベクトル化して同時に処理する配列の要素を増やすことが可能となり、コンピュータがより高速に実行することが可能となるオブジェクトプログラムを作成することができる。
【００４４】
なお、本発明は、上記実施の形態で示したものに限定されず、様々な変形および応用が可能である。
【００４５】
例えば、元の原始プログラムに記述されている多重ループ制御文のとおりに処理を行うか、元の原始プログラムを変形した制御文を用いて処理を行うかを、所定の条件によって切り分けるように、元の原始プログラムを変形する処理を備えるコンパイル装置を構成してもよい。以下、このコンパイル装置について説明する。なお、このコンパイル装置によるコンパイル処理の動作は、図７に示すループ最適化処理のフローチャート内の多重ループ変形処理（Ｓ１３０）のみが異なるものであり、他の処理は今まで説明してきたコンパイル装置１と全く同一である。そのため、このコンパイル装置のコンパイル処理については、多重ループ変形処理についてのみ以下に詳細に説明する。
【００４６】
図９は、このコンパイル装置による多重ループ変形処理の動作を示したフローチャートである。図５は、図３（ａ）に示す原始プログラムが、この多重ループ変形処理によって変形された場合の原始プログラムを示す図である。
【００４７】
まず、多重ループ変形処理が開始されると、制御部１４は、図７のステップＳ１２０で判別した多重ループ制御文を、原始プログラムの最後尾にコピーする（ステップＳ２３１）。
図５に示す原始プログラムにおいては、ループ制御文Ｃ−６が上述のステップＳ２３１によってコピーされたループ制御文に対応する。ループ制御文Ｃ−６は、図３（ａ）に示す変形前の原始プログラムにおける多重ループ制御文（Ａ−２、Ａ−３）をコピーしたものである。
【００４８】
次に、制御部１４は、構造型データのメンバである配列の配列要素のリスト構造全体での総合計数を求めるループ制御文を作成し、作成したループ制御文を図７のステップＳ１２０で判別した多重ループ制御文の直前に挿入する（ステップＳ２３２）。なお、この処理は、図８のステップＳ１３１と同等の処理である。
図５に示す原始プログラムにおいては、ループ制御文Ｃ−１が上述のステップＳ１３１によって作成、挿入されたループ制御文に対応する。
【００４９】
次に、制御部１４は、作業配列の宣言文を作成し、ステップＳ２３２で作成したループ制御文の直後に挿入する（ステップＳ２３３）。なお、この処理は、図８のステップＳ１３２と同等の処理である。
図５に示す原始プログラムにおいては、宣言文Ｃ−３が上述のステップＳ２３３によって作成、挿入された作業配列の宣言文に対応する。
【００５０】
次に、制御部１４は、図７のステップＳ１２０で判別した多重ループ制御文のうちの内側のループ制御文を、構造型データのメンバである配列の配列要素をたどって該配列要素のアドレスを取得し、取得したアドレスを作業配列の各配列要素に登録するループ制御文に置換する（ステップＳ２３４）。なお、この処理は、図８のステップＳ１３３と同等の処理である。
図５に示す原始プログラムにおいては、ループ制御文Ｃ−４が、ステップＳ２３４によって置換されたループ制御文に対応する。
【００５１】
次に、制御部１４は、作業配列の各配列要素をたどり、該各配列要素に登録されているアドレスからリスト構造を形成する構造型データのメンバである配列の各配列要素にアクセスし、図７のステップＳ１２０で判別した多重ループ制御文のうちの内側のループ制御文による処理をアクセスした各配列要素に対して行うループ制御文を作成し、作成した挿入用ループ制御文を図７のステップＳ１２０で判別した多重ループ制御文の直後に挿入する（ステップＳ２３５）。なお、この処理は、図８のステップＳ１３４と同等の処理である。
図５に示す原始プログラムにおいては、ループ制御文Ｃ−５が上述のステップＳ１３４によって生成されたループ制御文に対応する。
【００５２】
次に、制御部１４は、配列の要素数の高速化に適した閾値によって、ステップＳ２３１でコピーした元の原始プログラムに記述されている多重ループ制御文のとおりに処理を行うのか、ステップＳ２３２〜Ｓ２３５の処理により元の多重ループ制御文が変形された制御文のとおりに処理を行うのかの分岐処理を行うための制御文を作成し、挿入する（図９、ステップＳ２３６）。以上で、多重ループ変形処理は終了する。
図５に示す原始プログラムにおいては、ステップＳ２３６の処理により、閾値ｔｈｒｅｓｈｏｌｄ−ｖａｌｕｅの値によって、元の原始プログラムに記述されているとおりの多重ループ制御文（Ｃ−６）を実行するのか、元の原始プログラムを変形した制御文（Ｃ−７）の処理を実行するかどうかの分岐制御文（Ｃ−２）が、作成、挿入される。
【００５３】
原始プログラムを以上のように変形する多重ループ変形処理を備えたコンパイル装置を構成した場合には、リスト構造を構成する構造型データのメンバである配列の要素に対する処理を元の原始プログラムの多重ループ制御文で行うのか、又は多重ループ変形部によって変形した多重ループ制御文で行うのかを構造型データのメンバである配列のリスト構造での総配列要素数が閾値より大きいか否かによって切り分けることができる。よって、処理する配列要素の数が少ないため等により、元の原始プログラムを変形したことにより、逆に処理が低速化してしまうような場合は、変形前の多重ループ処理を実行することにより、処理の低速化を回避すること等が可能となる。
また、処理を切り分ける条件として、上記では、配列の総要素数が閾値より大きいか否かを条件としたが、これに限る必要はなく、例えば特定のフラグが立っているか否か等の条件によって、処理を切り分けるようにしてもよい。
【００５４】
また、本発明の実施の形態では、多重ループ検出部１４１及び多重ループ変形部１４２は、コンパイラ装置１に設けられているものとして説明したが、コンパイルの前処理段階を行うプリコンパイラに設けられていてもよい。
【００５５】
また、上述のコンパイル装置のループ最適化処理による原始プログラムの変形作業を、人間が手作業で行ってもよい。
【００５６】
また、本実施の形態では、Ｃ言語で記述された原始プログラムからオブジェクトプログラムを作成するコンパイル装置を例示したが、これに限るものでなく、他のプログラム言語、例えばＦＯＲＴＲＡＮやＪＡＶＡ（登録商標）等で記述された原始プログラムからオブジェクトプログラムを作成するコンパイル装置についても同様に適用可能である。
【図面の簡単な説明】
【００５７】
【図１】本実施の形態に係るコンパイル装置の構成を示すブロック図である。
【図２】図１に示すコンパイル装置の機能構成図である。
【図３】（ａ）は、図１に示すコンパイル装置によるコンパイルの対象となるＣ言語で記述された原始プログラムの例を示した図である。（ｂ）は、図３（ａ）に示された原始プログラム内に記述されているリスト構造と、該リスト構造の構成要素である構造型データと、該構造型データのメンバとの関係を模式的に表した図である。
【図４】（ａ）は、図３（ａ）に示す原始プログラムが、本実施の形態に係るコンパイル装置によって変形された結果の一例を示す図である。（ｂ）は、図４（ａ）に示された原始プログラム内に記述されているリスト構造と、該リスト構造の構成要素である構造型データと、該構造型データのメンバと、作業配列との関係を模式的に表した図である。
【図５】は、図３（ａ）に示す原始プログラムが、本実施の形態に係るコンパイル装置によって変形された結果の一例を示す図である。
【図６】本実施の形態に係るコンパイル装置によるコンパイル処理の動作を示すフローチャートである。
【図７】本実施の形態に係るコンパイル装置によるループ最適化処理の動作を示すフローチャートである。
【図８】本実施の形態に係るコンパイル装置による多重ループ変形処理の動作を示すフローチャートである。
【図９】本実施の形態に係るコンパイル装置による多重ループ変形処理の別例の動作を示すフローチャートである。
【符号の説明】
【００５８】
１      コンパイル装置
１４    制御部
１４１  多重ループ検出部
１４２  多重ループ変形部
１４３  オブジェクトプログラム生成部
２      原始プログラム 
３      オブジェクトプログラム
【図１】
2008123249.tif 000003
【図２】
2008123249.tif 000004
【図３】
2008123249.tif 000005
【図４】
2008123249.tif 000006
【図５】
2008123249.tif 000007
【図６】
2008123249.tif 000008
【図７】
2008123249.tif 000009
【図８】
2008123249.tif 000010
【図９】
2008123249.tif 000011