JP5169322B2 - 変数最適化装置、変数最適化プログラム、コンパイラ、変数最適化方法、及びコンパイル方法 - Google Patents

Description

本発明は、コンパイラ、及び、変数最適化装置に関し、更に詳しくは、ソースプログラムから中間コードを生成し、中間コードからオブジェクトプログラムを生成するコンパイラ、及び、そのようなコンパイラに用いられる変数最適化装置に関する。また、本発明は、コンパイル方法、変数最適化方法、及び、プログラムに関する。

近年、ＣＰＵ（プロセッサ）の動作速度は、ハードウェアの改善などにより、高速化が進んでいる。一方で、メモリアクセスの性能は、ＣＰＵの速度の高速化に比べて改善が進んでいない。このため、メモリアクセスの少ないプログラムでは、性能を大きく改善することができるものの、メモリアクセスの多いプログラムは、性能改善の幅が小さい。プログラムの生成に際しては、メモリアクセスが多いプログラムの性能をいかに改善するかが課題となっている。

メモリアクセス回数は、ループ融合などのループ変形を行い、共通式の削除により、複数のループに存在している同一メモリへのアクセスを１つにまとめることで、削減可能である。コンパイラにて、このような処理を行い、実行プログラムにおけるメモリアクセスの回数を減らすことで、ソフトウェア的に、性能改善を図ることができる。

Ｆｏｒｔｒａｎなどのプログラムでは、配列式で参照される配列の下限／上限が変数を用いて宣言されることがある。その場合、配列の形状を翻訳時には決定できないので、配列式に対して十分な最適化が行われないことがあった。変数を定数に置き換えてコンパイルする技術の一例が、特許文献１に記載されている。特許文献１では、変数の定義が一度のものを選択して、変数から定数への置換を行っている。
特開平２−１１８７３２号公報

ところで、科学技術計算で広く使われているＦｏｒｔｒａｎなどのプログラミング言語では、配列と配列の演算や、演算結果を代入する式を１つの文中に記述することで、配列の要素ごとに演算が可能な配列式が定義されている。図２３に、ソースプログラムの一例を示す。式１−１のａ（ｍ１：ｍ２）は、配列ａの要素ａ（ｍ１）からａ（ｍ２）を含む配列の一部である部分配列を表す。ｍ１は下限、ｍ２は上限と呼ばれている。配列の寸法は、アクセスする配列の要素の数を表す。例えば、ａ（１：５）の場合、ａ（１）、ａ（２）、ａ（３）、ａ（４）、ａ（５）の５つの要素を含むので、配列の寸法は５となる。式１−１は、ｍ１からｍ２までの要素について、ａ（ｍ１）＝ｂ（ｍ１）＋ｃ（ｍ１）、ａ（ｍ１＋１）＝ｂ（ｍ１＋１）＋ｃ（ｍ１＋１）のように、配列ｂと配列ｃとの要素ごとの加算結果を配列ａの各要素に代入することを表す。配列の要素ごとに演算するので、１つの配列式では同じ形状の配列のみを記述するのが通常である。一方、式１−３は、全配列である。式１−３は、ｘの各要素に、ｃの部分配列の各要素を代入することを表す。

コンパイラは、配列式に対し、その配列式に現れる配列の下限と上限とに基づいて計算した初期値と終値とを持つループを内部的に生成する。コンパイラは、生成したループに対して最適化処理を行い、同じループ回数のループを融合し、共通式を削除することでループ内にある同じ配列要素へのアクセスを削減し、プログラムの高速化を図る。この最適化処理にて、複数のループを融合するためには、翻訳時に、ループの初期値と終値とを元に計算するループの繰り返し回数が同じである必要がある。しかし、Ｆｏｒｔｒａｎなどのプログラムでは、配列式で参照される配列の下限と上限とが変数を用いて宣言されることがあり、その場合、配列の形状を翻訳時に決定できないために、配列式に対して十分に最適化が行えないことがあった。以下、これについて説明する。

図２４に、図２３のソースプログラムから生成される中間コードを示す。図２３のソースプログラムに含まれる式１−１〜式１−３、式１−５の配列式は、中間コード生成部により、図２４に含まれる４つのループ（do〜enddoまで）に変換される。ループへの変換では、配列が全配列であれば、宣言式における下限と上限とに基づいてループの初期値と終値とを決定し、部分配列の場合は、参照箇所の下限と上限とに基づいて、初期値と終値とを決定する。例えば、配列式１−１は、部分配列（ｍ１：ｍ２）の演算であり、寸法はｍ２−ｍ１＋１であるので、また、配列式１−３は、部分配列ｃ（ｍ１：ｍ２）を含むので、ループの初期値は０に、終値ｍ２−ｍ１に設定される。

従来方式では、一つの配列式で参照する全ての配列の次元数と寸法とが同じであることを利用し、その配列式で参照される一つの配列の下限と上限とを元に、ループの初期値と終値を決定していた。例えば、配列式１−３について、配列式１−３で参照する配列の次元数と寸法のみに着目して、ループ回数をｍ２−ｍ１＋１に決定していた。このように、従来方式では、配列式で参照する全ての配列の下限／上限の情報を元にループの初期値と終値を決定していないので、配列の下限や上限が異なる変数や式で定義される場合は、複数の配列式間複数の配列式のループを融合することはできなかった。その結果、共通式削除によってループ内の同じ配列要素へのアクセスまとめることができず、メモリアクセスを削減できなかった。

例えば、図２４では、配列式１−１、１−３のループ回数はｍ２−ｍ１＋１回に、配列式１−２のループ回数はｎ２−ｎ１＋１回に設定される。ここで、配列式１−３に着目すれば、全配列ｘの寸法と部分配列ｃ（ｍ１：ｍ２）の寸法が同じことから、ｎ２−ｎ１とｍ２−ｍ１とは等しいことがわかる。この情報を、他の配列式に適用することができれば、配列式１−２のループ回数ｎ２−ｎ１＋１は、ｍ２−ｍ１＋１に置き換えることが可能となり、３つのループを１つにまとめることが可能である。しかし、従来技術では、このような解析は行わないので、コンパイラは、ｍ２−ｍ１とｎ２−ｎ１とが同じ値になることを認識できず、ループをまとめることができなかった。

変数の定数への置換に関し、特許文献１では、変数の定義が一度のものを選択して、変数から定数への置換を行っている。しかし、特許文献１では、手続き内に定義がない変数を定数に置換することはできない。また、変数を定数に置き換えることのみを行っており、変数同士や式を解析してはいない。このため、ループ回数が、異なる変数や式を用いて定義された場合に、ループ回数が同じであることを認識して、ループの融合を行うことはできない。

本発明は、上記従来技術の問題点を解消し、ループ回数が、異なる変数や式を用いて定義された場合でも、ループ融合が可能なコンパイラ、変数最適化装置、方法、及び、プログラムを提供することを目的とする。

本発明の変数最適化装置は、
複数の配列を演算する配列式を含む中間コードを読み出し、前記中間コードから、配列式を複数検出する配列式検出部と、
前記配列式検出部で検出された複数の配列式でそれぞれ演算される複数の配列のそれぞれについて、配列の寸法を表す寸法式を当該配列の上限を表す変数と下限を表す変数とを用いて計算し、第１の変数を用いて寸法式が計算された第１の配列の寸法と、第２の変数を用いて寸法式が計算された第２の配列の寸法と、は、前記第１の配列と前記第２の配列とが同じ配列式で演算される場合に、同じ寸法である、という関係を表す関係式を決定する変数関係確定部と、
前記第１の配列と前記第２の配列とを演算する配列式が前記中間コードから検出された配列式検出位置よりも前の位置で、前記第１の変数若しくは前記第２の変数の値を定義する前定義式を検出し、前記配列式検出位置よりも後の位置で、前記第１の変数若しくは前記第２の変数の値を定義する後定義式を検出する変数定義検出部と、
前記変数関係確定部で決定された関係式に基づいて、前記複数の配列式でそれぞれ演算される複数の配列の寸法式の内で、前記変数定義検出部で前定義式が検出された位置から、前記変数定義検出部で後定義式が検出された位置までの位置で検出された配列式で演算される配列の寸法式であって前記第１の変数を用いて計算された寸法式を、前記第２の変数を用いて計算された寸法式に置換する寸法式置換部と、
前記寸法式置換部で置換された寸法式と同じ寸法式で表される寸法の配列を演算する複数の配列式にそれぞれ従って、繰り返し実行される複数のループ処理から当該複数のループ処理に共通した共通演算式を削除し、かつ当該複数のループ処理を融合させるループ最適化を行う最適化部と、
を備えることを特徴とする。

本発明のコンパイラは、
コンピュータを、
複数の配列を演算する配列式を含む中間コードを読み出し、前記中間コードから、配列式を複数検出する配列式検出部、
前記配列式検出部で検出された複数の配列式でそれぞれ演算される複数の配列のそれぞれについて、配列の寸法を表す寸法式を当該配列の上限を表す変数と下限を表す変数とを用いて計算し、第１の変数を用いて寸法式が計算された第１の配列の寸法と、第２の変数を用いて寸法式が計算された第２の配列の寸法と、は、前記第１の配列と前記第２の配列とが同じ配列式で演算される場合に、同じ寸法である、という関係を表す関係式を決定する変数関係確定部、
前記第１の配列と前記第２の配列とを演算する配列式が前記中間コードから検出された配列式検出位置よりも前の位置で、前記第１の変数若しくは前記第２の変数の値を定義する前定義式を検出し、前記配列式検出位置よりも後の位置で、前記第１の変数若しくは前記第２の変数の値を定義する後定義式を検出する変数定義検出部、
前記変数関係確定部で決定された関係式に基づいて、前記複数の配列式でそれぞれ演算される複数の配列の寸法式の内で、前記変数定義検出部で前定義式が検出された位置から、前記変数定義検出部で後定義式が検出された位置までの位置で検出された配列式で演算される配列の寸法式であって前記第１の変数を用いて計算された寸法式を、前記第２の変数を用いて計算された寸法式に置換する寸法式置換部、
前記寸法式置換部で置換された寸法式と同じ寸法式で表される寸法の配列を演算する複数の配列式にそれぞれ従って、繰り返し実行される複数のループ処理から当該複数のループ処理に共通した共通演算式を削除し、かつ当該複数のループ処理を融合させるループ最適化を行う最適化部、
前記最適化部でループ最適化された中間コードに基づいて、オブジェクトプログラムを生成するコード生成部、
として機能させることを特徴とする。

本発明の変数最適化方法は、
コンピュータが、複数の配列を演算する配列式を含む中間コードを読み出し、前記中間コードから、配列式を複数検出する配列式検出ステップと、
前記コンピュータが、前記配列式検出ステップで検出された複数の配列式でそれぞれ演算される複数の配列のそれぞれについて、配列の寸法を表す寸法式を当該配列の上限を表す変数と下限を表す変数とを用いて計算し、第１の変数を用いて寸法式が計算された第１の配列の寸法と、第２の変数を用いて寸法式が計算された第２の配列の寸法と、は、前記第１の配列と前記第２の配列とが同じ配列式で演算される場合に、同じ寸法である、という関係を表す関係式を決定する変数関係確定ステップと、
前記コンピュータが、前記第１の配列と前記第２の配列とを演算する配列式が前記中間コードから検出された配列式検出位置よりも前の位置で、前記第１の変数若しくは前記第２の変数の値を定義する前定義式を検出し、前記配列式検出位置よりも後の位置で、前記第１の変数若しくは前記第２の変数の値を定義する後定義式を検出する変数定義検出ステップと、
前記コンピュータが、前記変数関係確定ステップで決定された関係式に基づいて、前記複数の配列式でそれぞれ演算される複数の配列の寸法式の内で、前記変数定義検出ステップで前定義式が検出された位置から、前記変数定義検出ステップで後定義式が検出された位置までの位置で検出された配列式で演算される配列の寸法式であって前記第１の変数を用いて計算された寸法式を、前記第２の変数を用いて計算された寸法式に置換する寸法式置換ステップと、
前記コンピュータが、前記寸法式置換ステップで置換された寸法式と同じ寸法式で表される寸法の配列を演算する複数の配列式にそれぞれ従って、繰り返し実行される複数のループ処理から当該複数のループ処理に共通した共通演算式を削除し、かつ当該複数のループ処理を融合させるループ最適化を行う最適化ステップと、
を有することを特徴とする。

本発明のコンパイル方法は、
コンピュータが、複数の配列を演算する配列式を含む中間コードを読み出し、前記中間コードから、配列式を複数検出する配列式検出ステップと、
前記コンピュータが、前記配列式検出ステップで検出された複数の配列式でそれぞれ演算される複数の配列のそれぞれについて、配列の寸法を表す寸法式を当該配列の上限を表す変数と下限を表す変数とを用いて計算し、第１の変数を用いて寸法式が計算された第１の配列の寸法と、第２の変数を用いて寸法式が計算された第２の配列の寸法と、は、前記第１の配列と前記第２の配列とが同じ配列式で演算される場合に、同じ寸法である、という関係を表す関係式を決定する変数関係確定ステップと、
前記コンピュータが、前記第１の配列と前記第２の配列とを演算する配列式が前記中間コードから検出された配列式検出位置よりも前の位置で、前記第１の変数若しくは前記第２の変数の値を定義する前定義式を検出し、前記配列式検出位置よりも後の位置で、前記第１の変数若しくは前記第２の変数の値を定義する後定義式を検出する変数定義検出ステップと、
前記コンピュータが、前記変数関係確定ステップで決定された関係式に基づいて、前記複数の配列式でそれぞれ演算される複数の配列の寸法式の内で、前記変数定義検出ステップで前定義式が検出された位置から、前記変数定義検出ステップで後定義式が検出された位置までの位置で検出された配列式で演算される配列の寸法式であって前記第１の変数を用いて計算された寸法式を、前記第２の変数を用いて計算された寸法式に置換する寸法式置換ステップと、
前記コンピュータが、前記寸法式置換ステップで置換された寸法式と同じ寸法式で表される寸法の配列を演算する複数の配列式にそれぞれ従って、繰り返し実行される複数のループ処理から当該複数のループ処理に共通した共通演算式を削除し、かつ当該複数のループ処理を融合させるループ最適化を行う最適化ステップと、
前記コンピュータが、前記最適化ステップでループ最適化された中間コードに基づいて、オブジェクトプログラムを生成するコード生成ステップと、
を有することを特徴とする。

本発明の変数最適化プログラムは、
コンピュータを、
複数の配列を演算する配列式を含む中間コードを読み出し、前記中間コードから、配列式を複数検出する配列式検出部、
前記配列式検出部で検出された複数の配列式でそれぞれ演算される複数の配列のそれぞれについて、配列の寸法を表す寸法式を当該配列の上限を表す変数と下限を表す変数とを用いて計算し、第１の変数を用いて寸法式が計算された第１の配列の寸法と、第２の変数を用いて寸法式が計算された第２の配列の寸法と、は、前記第１の配列と前記第２の配列とが同じ配列式で演算される場合に、同じ寸法である、という関係を表す関係式を決定する変数関係確定部、
前記第１の配列と前記第２の配列とを演算する配列式が前記中間コードから検出された配列式検出位置よりも前の位置で、前記第１の変数若しくは前記第２の変数の値を定義する前定義式を検出し、前記配列式検出位置よりも後の位置で、前記第１の変数若しくは前記第２の変数の値を定義する後定義式を検出する変数定義検出部、
前記変数関係確定部で決定された関係式に基づいて、前記複数の配列式でそれぞれ演算される複数の配列の寸法式の内で、前記変数定義検出部で前定義式が検出された位置から、前記変数定義検出部で後定義式が検出された位置までの位置で検出された配列式で演算される配列の寸法式であって前記第１の変数を用いて計算された寸法式を、前記第２の変数を用いて計算された寸法式に置換する寸法式置換部、
前記寸法式置換部で置換された寸法式と同じ寸法式で表される寸法の配列を演算する複数の配列式にそれぞれ従って、繰り返し実行される複数のループ処理から当該複数のループ処理に共通した共通演算式を削除し、かつ当該複数のループ処理を融合させるループ最適化を行う最適化部、
として機能させることを特徴とする。

本発明のコンパイラ、変数最適化装置、方法、及び、プログラムでは、ループ回数が、異なる変数や式を用いて定義された場合でも、ループ融合が可能である。

以下、図面を参照し、本発明の実施の形態を詳細に説明する。図１は、本発明の第１実施形態のコンパイラを示している。コンパイラ１０は、中間コード生成部１１、変数最適化部１２、最適化部１３、及び、コード生成部１４を有する。コンパイラは、Ｆｏｒｔｒａｎなどのプログラムを翻訳しロードモジュールを生成する。コンパイラの各部の機能は、コンピュータ上で所定プログラムを実行することで、実現できる。

ソースプログラム３１は、Ｆｏｒｔｒａｎなどの所定のプログラミング言語で記述されたプログラムのソースである。ソースプログラム３１は、メモリなどに記憶されている。中間コード生成部１１は、ソースプログラム３１を読み出し、ソースプログラム３１に基づいて中間コード３２を生成する。生成した中間コード３２は、メモリなどに記憶する。

変数最適化部１２は、中間コード３２を読み出し、中間コード３２における変数の最適化処理を行い、中間コード３６を生成する。生成した中間コード３６は、メモリなどに記憶する。最適化部１３は、中間コード３６に対して、ベクトル化や、並列化、ループ最適化、共通式の削除などを行う。最適化部１３が行う処理は、少なくとも同一ループ回数のループをまとめるループ最適化と、共通式の削除を含むものとする。最適化部１３は、ループ最適化などを行った結果の中間コード３７を、メモリなどに記憶する。

コード生成部１４は、最適化部１３により最適化された中間コード３７を読み出し、中間コード３７に基づいて、オブジェクトプログラム３８を生成する。生成したオブジェクトプログラム３８は、メモリや保持記憶装置などに記憶する。中間コード生成部１１、最適化部１３、及び、コード生成部１４には、それぞれ既存の中間コード生成手段、最適化手段、コード生成手段を用いることができる。

変数最適化部１２は、宣言情報・配列式検出手段２１、参照配列検出手段２２、変数関係確定手段２３、変数定義検出手段２４、及び、変数置換手段２５を有する。宣言情報・配列式検出手段２１は、中間コード３２を検索して、配列の宣言情報と配列式とを検出し、宣言情報テーブル、配列式テーブル３３に登録する。参照配列検出手段２２は、配列式テーブルに登録されている配列式に対し、各配列式で参照している配列を調べ、各配列について、配列の種類（全配列／部分配列）、配列の下限及び上限を、参照配列テーブル３４に登録する。配列の上限及び下限は、配列が全配列であれば、宣言情報テーブルに登録されている下限及び上限であり、配列が部分配列であれば、参照箇所における下限及び上限である。

変数関係確定手段２３は、参照配列テーブル３４を参照して、配列の下限及び上限に基づいて配列の寸法を計算し、同一配列式内の配列の各次元の寸法が同じであることを利用して、寸法の計算に用いる変数や式の値を決定する。値が決定しない場合には、他の変数や式との関係を決定する。例えば、下限／上限がｎ１／ｎ２である配列と、下限／上限がｍ１／ｍ２である配列とが同一配列式で参照される場合には、双方の寸法が同じであることを利用して、両者の関係式をｎ２−ｎ１＝ｍ２−ｍ１と決定する。変数関係確定手段２３は、決定した値又は関係を表す関係式と、その関係を決定した配列式である決定式とを、確定変数テーブル３５に登録する。

変数定義検出手段２４は、確定変数テーブル３５に登録されている決定式を起点に、前後の中間コード３２を検索し、確定変数テーブル３５に登録される関係式が、部分配列の下限又は上限に表れる変数を参照しているか否かを調べる。参照している場合は、決定式の前後で、関係式で参照する変数を定義する式を検索し、決定式よりも前で変数を定義する式（前定義式）と、後ろで変数を定義する式（後定義式）とを検出する。変数定義検出手段２４は、検出した前定義式及び後定義式を、確定変数テーブル３５に登録する。前定義式及び後定義式がそれぞれ複数検出される場合は、実行経路において決定式の最も近くで実行される可能性がある式を登録する。定義する式が存在しない場合は、確定変数テーブル３５の前定義式又は後定義式に、ＮＵＬＬを登録する。全配列の宣言式で使用する変数のみ参照する場合は、確定変数テーブル３５の前定義式及び後定義式にＮＵＬＬを登録する。

変数置換手段２５は、中間コード３２を検索し、前定義式と後定義式との間で、確定変数テーブル３５に登録された関係式の右辺又は左辺（以下では、左辺として説明する）を参照する箇所を検出し、これを、関係式の右辺で置換する。検索では、前定義式がＮＵＬＬの場合には先頭から後定義式との間を検索し、後定義式がＮＵＬＬの場合は前定義式から最後までを検索する。例えば、関係式がｎ２−ｎ１＝ｍ２−ｍ１であれば、中間コード３２にて、前定義式と後定義式との間に、ｎ２−ｎ１が存在すれば、これを、ｍ２−ｍ１に置換する。変数置換手段２５は、置換した結果を、中間コード３６として出力する。

変数最適化部１２が生成した中間コード３６は、最適化部１３にて、ループの最適化や共通式の削除などの最適化が適用され、中間コード３６に比して、メモリアクセスが削減された中間コード３７が得られる。コード生成部１４にて、中間コード３７からオブジェクトプログラム３８を生成することで、中間コード生成部１１が生成した中間コード３２に対して最適化部１３にて最適化を行った中間コードからオブジェクトプログラムを生成した場合に比して、メモリアクセスが削減されたプログラムが得られる。

図２に、変数最適化部１２の動作手順を示す。宣言情報・配列式検出手段２１は、中間コード３２を検索し、配列の宣言情報と、配列式とを検出して、これらを、宣言情報テーブル、配列式テーブル３３に登録する（ステップＳ１）。図３及び図４に、それぞれ、宣言情報テーブル及び配列式テーブルのデータ例を示す。図２３に示すソースプログラム３１に対応する中間コード３２から、配列の宣言情報を検出することで、配列ａ、ｂ、ｃ、ｄ、ｅ、ｘ、ｙ、ｚが宣言情報テーブルに登録される（図３）。また、中間コード３２から、配列式を検出することで、図２３の配列式１−１〜１−３、１−５に対応する配列式が配列式テーブルに登録される（図４）。

参照配列検出手段２２は、配列式テーブルに登録されている各配列式に対して、参照配列テーブル３４を作成し、各参照配列テーブルに、各配列式で参照している配列の配列名、配列の形状、配列の種別（全配列／部分配列）を登録する（ステップＳ２）。形状（下限：上限）については、配列が全配列であれば、宣言情報テーブルに登録されている下限と上限を登録し、部分配列であれば、参照箇所における下限と上限を登録する。図５（ａ）〜（ｄ）に、参照配列テーブルのデータ例を示す。図４に示す配列式テーブルを参照すると、中間コード３２には４つの配列式（配列式１−１〜１−３、１−５）があるので、これらに対応して、参照配列テーブルを作成する（図５（ａ）〜（ｄ））。

ステップＳ２では、式１−１に対しては配列ａ、ｂ、ｃを（図５（ａ））、式１−２に対しては配列ｃ、ｄ、ｅを（図５（ｂ））、式１−３に対してはｃ、ｘを（図５（ｃ））、式１−５に対してはｙ、ｚを（図５（ｄ））、それぞれ参照配列テーブルに登録する。また、式１−３の配列ｘに対しては全配列である旨を登録し、それ以外の配列に対しては、部分配列である旨を登録する。全配列であるｘについては、宣言情報テーブルに登録されている形状（ｎ１：ｎ２）を参照配列テーブル３４に登録し、その他の配列については、参照箇所の形状を参照配列テーブル３４に登録する。例えば、図２３を参照すると、式１−１の配列ａの参照箇所はｍ１からｍ２であるので、式１−１に対する参照配列テーブルには、配列ａの形状として、（ｍ１：ｍ２）を登録する。

変数関係確定手段２３は、参照配列テーブル３４を参照して、各配列式における配列の下限と上限とから寸法を計算し、同一配列式内では配列の各次元の寸法が同じであることを利用して、寸法の計算で参照する変数や式の値を決定する。例えば、同一参照配列テーブル内にて、形状が２つの変数で定められる配列と、２つの定数で定められる配列とが存在するときは、配列の寸法が同じであることを利用して、両者の関係から変数の定数化が可能である。値が決定しないときは、他の変数や式との関係を決定する。例えば、同一参照配列テーブル内で、形状が２つの変数で定められる配列と、これとは異なる２つの変数で定められる別の配列とがあるときは、両者の寸法が同じであることを利用して、４つの変数間の関係式を導き出すことができる。変数関係確定手段２３は、決定した値又は関係を表す関係式と、その関係を決定した配列式である決定式とを、確定変数テーブル３５に登録する（ステップＳ３）。

図６に、確定変数テーブル３５のデータ例を示す。式１−１、１−２、１−５に対応する参照配列テーブル（図５（ａ）、（ｂ）、（ｄ））を参照すると、これらでは、形状が同じ変数（ｍ１、ｍ２又はｎ１、ｎ２）で定義されるので、これらから決定できる値又は関係式はない。式１−３に対応する参照配列テーブル（図５（ｃ））を参照すると、配列ｘの形状は（ｎ１：ｎ２）で、配列ｃの形状（参照箇所）は（ｍ１：ｍ２）となっている。両者の形状が等しいことを利用すると、ｎ１−ｎ２＝ｍ１−ｍ２という関係式が得られる。変数関係確定手段２３は、得られた関係式「ｎ１−ｎ２＝ｍ１−ｍ２」と、関係式を決定した配列式「１−３」とを、確定変数テーブル３５に登録する。

変数定義検出手段２４は、確定変数テーブル３５に登録されている決定式の前後の中間コード３２を検索し、決定式によって決定される関係式が、部分配列の下限／上限に表れる変数を参照しているか否かを判断する。参照している場合は、決定式の前後で、関係式で参照する変数を定義する式を検索する。変数定義検出手段２４は、検索により得られた、決定式の前で変数を定義する式を前定義式として確定変数テーブル３５に登録し、決定式の後ろで変数を定義する式を後定義式として確定変数テーブル３５に登録する（ステップＳ４）。検索にて、前定義式又は後定義式が複数検索された場合は、実行経路において決定式の最も近くで実行される可能性がある式を登録する。前定義式及び後定義式がない場合は、確定変数テーブル３５にＮＵＬＬを登録する。また、決定式によって決定される関係式が、部分配列の下限／上限に現れる変数を参照していない場合は、確定変数テーブル３５にＮＵＬＬを登録する。

図２３に示すソースプログラムにて、決定式「１−３」によって決定される関係式「ｎ２−ｎ１＝ｍ２−ｍ１」が、部分配列の下限／上限に現れる変数を参照しているか否かを調べると、配列式１−１、１−２、１−５で、関係式が、部分配列の下限／上限に現れる変数を参照している。決定式の前後で、関係式で参照する変数を定義する式を検索すると、決定式よりも後の式１−４で、ｎ２の値を定義している。決定式の前で定義する存在していない。従って、変数定義検出手段２４は確定変数テーブル３５の後定義式に式１−４を登録し、前定義式にＮＵＬＬを登録する。

決定式よりも前に、関係式の変数を定義する式がある場合、前定義式よりも前では、関係式で定義される関係をそのまま用いることができるかどうかは不明である。同様に、決定式よりも後ろに、関係式の変数を定義する式がある場合は、その後定義式以降で、関係式で定義される関係を適用可能かどうかは不明である。従って、関係式を用いることができる範囲は、中間コード３２において、前定義式と後定義式とに挟まれた範囲となる。図２３では、配列式１−１、１−２、１−５で、関係式が、部分配列の下限／上限に現れる変数を参照しているが、これらのうち、配列式１−５は、後定義式よりも後なので、関係式を適用可能なのは、配列式１−１、１−２ということになる。

変数置換手段２５は、確定変数テーブル３５と参照配列テーブル３４とを参照しながら中間コード３２を検索し、前定義式と後定義式との間で、確定変数テーブル３５に登録された関係式の左辺に該当する部分を検出し、その部分を、右辺で置換する（ステップＳ５）。値が決定しているときは、その値で置換する。検索は、前定義式がＮＵＬＬであれば、中間コードの先頭から後定義式までの範囲で行い、後定義式がＮＵＬＬであれば、前定義式から中間コードの最後までの範囲で行う。変数置換手段２５は、置換後、中間コード３６を出力する。

図７に、変数最適化部１２で変数最適化を行った後の中間コード３６を示す。変数最適化前の中間コード３２は、図２４に示す通りであり、配列式１−１〜１−３がそれぞれ独立したループとなっている。それぞれのループ回数は、ｍ２−ｍ１＋１回、ｎ２−ｎ１＋１回、ｍ２−ｍ１＋１回である。ステップＳ５では、関係式「ｎ２−ｎ１＝ｍ２−ｍ１」を用いて、中間コード３２にて先頭から式１−４までの範囲で、ｎ２−ｎ１で表される部分を、ｍ２−ｍ１で置き換える。これにより、図７に示す中間コード３６が得られる。

図８に、上記中間コード３６に対してループ最適化や共通式の削除を行った中間コード３７を示す。図７に示す中間コード３６に対して、最適化部１３にてループ最適化や共通式の削除を行うことで、メモリアクセスが削減された中間コード３７が得られる（図８）。すなわち、配列式１−１〜１−３が、１つのループの中に記述された中間コード３７が得られる。その後、中間コード３７に対して、コード生成部１４にてオブジェクトプログラム３８を生成することで、メモリアクセスが削減され、高速化されたプログラムが得られる。

図９に、実行されるメモリアクセスと演算とを示す。また、比較例として、図１０に、図２４に示す中間コードからオブジェクトプログラムを生成した場合に実行されるメモリアクセスと演算とを示す。図９及び図１０において、矢印で表される部分がメモリアクセスを表している。図２４の中間コードからオブジェクトプログラムを生成した場合、メモリアクセス回数は、５（ｍ２−ｍ１＋１）＋３（ｎ２−ｎ１＋１）＋２（１０−ｎ１＋１）回となる。これは、ｍ２−ｍ１＝ｎ２−ｎ１なので、８（ｍ２−ｍ１＋１）＋２（１０−ｎ１＋１）と書き直すことができる。これに対し、図８に示す中間コードからオブジェクトプログラムを生成した場合のメモリアクセス回数は、７（ｍ２−ｍ１＋１）＋２（１０−ｎ１＋１）回となる。従って、変数最適化処理を行うことで、メモリアクセス回数を（ｍ２−ｍ１＋１）回減らすことができ、その分だけ、プログラム実行を高速化できる。

本実施形態では、変数関係確定手段２３にて、同一配列式を構成する配列の各次元の寸法が同じであることを利用して、配列式で参照される各配列の下限／上限を定義する変数又は式の値を決定し、又は、変数間の関係式を決定する。値が決定する場合、全配列であれば手続内の配列宣言で使用する変数の値を決定でき、部分配列であれば参照箇所を決定する変数や式の値を決定できる。値が決定しないときは、他の変数や式との関係を決定する。部分配列に対しては、決定した値又は関係が他の式で変更されるか否かを解析し、決定した値又は関係が適用可能な範囲を求めておく。その後、変数置換手段２５にて、決定した値により、変数や式を定数化する。また、決定した関係式を用いて、変数や式を、同じ変数又は同じ式に置換する。

コンパイラは、配列式に対して、その配列式に現れる配列の下限と上限とを基に計算した初期値と終値とを持つループを内部的に生成する。変数置換手段２５にて、変数の置換を行い、変数の定数化や変数の統一を行うことで、異なる変数で初期値と終値とが定義されるためにループ回数が同じであるか否かが不明であった複数のループのループ回数が、同じループ回数であると判定できるようになる。その結果、ループ融合が可能となり、共通式の削除が可能となる。共通式を削除し、ループ内にある同じ配列要素へのアクセスをまとめることで、メモリアクセス回数を削減するができる。これにより、プログラム実行時間を短縮できる。

次に、本発明の第２実施形態について説明する。図１１は、本発明の第２実施形態のコンパイラを示している。本実施形態のコンパイラ１０ａでは、変数最適化部１５は、宣言情報・配列式検出手段２１、参照配列・連続出現配列式検出手段２６、寸法比較手段２７、及び、分岐追加手段２８を有する。第１実施形態では、変数最適化部１２(図１)にて、翻訳時に各次元の寸法の計算で参照されている変数や式の値、同じ値を持つ変数又は式が決定したときに、決定した変数又は式で元の式を置き換えた。本実施形態では、翻訳時に各次元の寸法の計算で参照されている変数や式の値、同じ値を持つ変数又は式が決定しない場合に、実行時に実行するコードを選択するコードを生成する。

宣言情報・配列式検出手段２１は、中間コード３２を検索し、配列宣言の上限と下限、及び、配列式を検出し、宣言情報テーブル、配列式テーブル３３に登録する。参照配列・連続出現配列式検出手段２６は、配列式テーブルに登録されている配列式に対し、各配列式で参照している配列、配列の種類（全配列／部分配列）、配列の下限及び上限を調べ、参照配列テーブル３９に登録する。また、配列式の直前及び直後に配列式が続くか否かを調べ、直前又は直後に配列式が続くときは、その配列式を参照配列テーブル３９に登録する。

寸法比較手段２７は、参照配列テーブル３９を参照して、連続する配列式で参照する配列の寸法が、翻訳時に同一であると判断できるか否かを調べる。翻訳時に寸法が同じであると判断できない連続した配列式がある場合、その配列式を、最適化候補配列式リスト４０に登録する。分岐追加手段２８は、最適化候補配列式リスト４０に登録された配列式について、寸法が同じである場合と、同じでない場合とを選択するコードを、中間コード３２に追加した中間コード３６を生成する。寸法が同じである場合に実行されるコードについては、先頭の配列式に対して生成されるループの初期値及び終値で、他のループの初期値及び終値を置き換える。

図１２に、本実施形態の変数最適化部１５の動作手順を示す。宣言情報・配列式検出手段２１は、中間コード３２を検索し、配列の宣言情報と、配列式とを検出して、これらを、宣言情報テーブル、配列式テーブル３３に登録する（ステップＳ１１）。図１３に、ソースプログラム例を示す。また、図１４及び図１５に、宣言情報テーブル、配列式テーブル３３のデータ例を示す。図１３に示すソースプログラム３１に対応する中間コード３２から、配列の宣言情報を検出することで、配列ａ、ｂ、ｃ、ｄ、ｅ、ｘが宣言情報テーブルに登録される（図１４）。また、中間コード３２から、配列式を検出することで、図１３の配列式９−１〜９−３に対応する配列式が、配列式テーブルに登録される（図１５）。

参照配列・連続出現配列式検出手段２６は、配列式テーブルに登録されている各配列式に対して参照配列テーブル３９を作成し、各参照配列テーブルに、各配列式で参照している配列の配列名、配列の形状、配列の種別（全配列／部分配列）を登録する。また、各配列式について、当該配列式の直前又は直後に配列式があるときは、その配列式を直前又は直後の配列式として参照配列テーブル３９に登録する（ステップＳ１２）。配列の形状（下限：上限）の登録に際しては、配列が全配列であれば、宣言情報テーブルに登録されている下限と上限を登録し、部分配列であれば、参照箇所における下限と上限を登録する。

図１６（ａ）〜（ｃ）に、参照配列テーブルのデータ例を示す。図１５に示す配列式テーブルを参照すると、中間コードには３つの配列式（配列式９−１〜９−３）があるので、参照配列・連続出現配列式検出手段２６は、これらに対応して、参照配列テーブルを作成する（図１６（ａ）〜（ｃ））。その後、９−１に対しては配列ａ、ｂ、ｃを（図１６（ａ））、式９−２対しては配列ｃ、ｄ、ｅを（図１６（ｂ））、式９−３に対してはｃ、ｘを（図１６（ｃ））、それぞれ参照配列テーブルに登録する。配列の種別は、全て部分配列である。形状には、各配列の参照箇所の形状を参照配列テーブル３９に登録する。例えば、図１３を参照すると、式９−１の配列ａの参照箇所はｍ１からｍ２であるので、式９−１に対する参照配列テーブルには、配列ａの形状として、（ｍ１：ｍ２）を登録する。

図１３を参照すると、配列式９−１の直前に他の配列式はなく、直後には配列式９−２が続く。参照配列・連続出現配列式検出手段２６は、配列式９−１に対応する参照配列テーブルの「直前」に、配列式がないことを示すｎｏｎｅを登録し、「直後」に、配列式９−２を登録する。配列式９−２については、直前に配列式９−１があり、直後には配列式９−３があるので、参照配列テーブルの「直前」に配列式９−１を登録し、「直後」に配列式９−３を登録する。配列式９−３は、直前に配列式９−２があり、直後には配列式がないので、参照配列テーブルの「直前」に配列式９−２を登録し、「直後」にはｎｏｎｅを登録する。

寸法比較手段２７は、参照配列テーブル３９を参照して、配列式が連続する箇所を検出する。その後、連続する配列式について、これら配列式で参照する配列の寸法が、翻訳時に同一であると判断できるか否かを調べる。翻訳時に寸法が同じであると判断できない連続した配列式がある場合は、その配列式を、最適化候補配列式リスト４０に登録する（ステップＳ１３）。図１６（ａ）〜（ｃ）を参照し、各配列式の「直前」、「直後」を調べることで、配列式９−１〜９−３が連続する配列式であると検出される。連続する配列式の検出後、参照配列テーブル３９の各配列の形状を参照して、連続する配列式９−１〜９−３で参照する配列の寸法が同じであると判断できるか否かを調べる。

図１７に、最適化候補配列式リスト４０のデータ例を示す。図１６（ａ）を参照すると、配列式９−１で参照する配列の寸法は、ｍ２−ｍ１＋１である。図１６（ｂ）を参照すると、配列式９−２で参照する配列の寸法は、ｎ２−ｎ１＋１である。この場合、配列式９−１と配列式９−２とで、参照する配列の寸法が同じであるか否かは不明であるので、寸法比較手段２７は、最適化候補配列式リスト４０に、配列式９−１、９−２を登録する（図１７）。同様に、配列式９−２と配列式９−３とで、参照する配列の寸法が同じであると判断できるか否かを調べると、配列式９−３で参照する配列の寸法はｍ２−ｍ１＋１であるので、同じであると判断できない。寸法比較手段２７は、最適化候補配列式リスト４０に、配列式９−３を追加登録する。

分岐追加手段２８は、最適化候補配列式リスト４０に登録された配列式について、寸法が同じである場合と、同じでない場合とを実行時に選択するコードを、中間コード３２に追加した中間コード３６を生成する（ステップＳ１４）。分岐追加手段２８が生成した中間コード３６が、変数最適化部１５が出力する中間コードとなる。図１８及び図１９に、分岐追加手段２８による追加前後の中間コードのデータ例を示す。図１８に示す中間コード３２は、中間コード生成部１１にて生成された、図１３に示すソースプログラムに対応した中間コードである。分岐追加手段２８は、中間コード３２から、配列式９−１〜９−３で参照する配列の寸法が同じ、すなわち、ｍ２−ｍ１＝ｎ２−ｎ１が成立するときに実行されるコードを生成し、これを追加した中間コード３６を生成する（図１９）。

図１９に示す中間コード３６は、ｍ２−ｍ１＝ｎ２−ｎ１が成立するときに実行されるコード部分（ｉｆ〜ｅｌｓｅの間）と、成立しないときに実行されるコード部分（ｅｌｓｅ〜ｅｎｄｉｆの間）とを有する。寸法が同じときに実行されるコード部分は、生成元となる中間コード３２（図１８）における各配列式に対応するループの初期値及び終値を、先頭の配列式である配列式９−１に対応するループの初期値及び終値で置き換えたものである。つまり、図１８では初期値＝０、終値ｎ２−ｎ１であった配列式９-２に対応するループの初期値及び終値が、それぞれ配列式９−１に対応するループの初期値及び終値である０、ｍ２−ｍ１で置き換えられたものである。寸法が同じではないときに実行されるコード部分の内容は、図１８に示す内容と同じである。

最適化部１３は、変数最適化部１５が出力する中間コード３６（図１９）に対して、最適化を行う。図２０に、最適化後の中間コード３７を示す。最適化後の中間コード３７では、ｍ２−ｍ１＝ｎ２−ｎ１が成立するときに実行されるコード部分にて、ループが１つにまとめられる。一方、ｍ２−ｍ１＝ｎ２−ｎ１が成立しないときに実行されるコード部分は、ループ融合ができないので、図１８に示す中間コード３２と同じままである。

図２１に、図２０に示す中間コードを実行したときのメモリアクセスと演算とを示す。最適化された中間コード３７に基づいて生成されたオブジェクトプログラムを実行すると、実行時にｍ２−ｍ１＝ｎ２−ｎ１が成立するときのメモリアクセス回数は、７（ｍ２−ｍ１＋１）回となる。また、実行時にｍ２−ｍ１＝ｎ２−ｎ１が成立しないときのメモリアクセス回数は、５（ｍ２−ｍ１＋１）＋３（ｎ２−ｎ１＋１）回となる。

図１８に示す中間コード３２を、変数最適化部１５を経ずに最適化部１３にて最適化した場合は、中間コード３６におけるｍ２−ｍ１＝ｎ２−ｎ１が成立しないときに実行されるコード部分と同様に、ループが融合される箇所はない。従って、中間コード３２に基づいて生成されたオブジェクトプログラムを実行したときの、メモリアクセス回数は５（ｍ２−ｍ１＋１）＋３（ｎ２−ｎ１＋１）回となる。ｍ２−ｍ１とｎ２−ｎ１の値が等しいとすると、メモリアクセス回数は、８（ｍ２−ｍ１＋１）回と表すことができる。

図２２に、メモリアクセス回数の比較表を示す。中間コード３６に基づくオブジェクトプログラムを実行した場合のメモリアクセス回数は、寸法が同じ、つまり、ｍ２−ｍ１＝ｎ２−ｎ１が成立する場合で７（ｍ２−ｍ１＋１）回、寸法が異なる、つまり、ｍ２−ｍ１＝ｎ２−ｎ１が成立しない場合で５（ｍ２−ｍ１＋１）＋３（ｎ２−ｎ１＋１）となる。一方、中間コード３２に基づくオブジェクトプログラムを実行した場合のメモリアクセス回数は、ｍ２−ｍ１＝ｎ２−ｎ１が成立する場合で、８（ｍ２−ｍ１＋１）、ｍ２−ｍ１＝ｎ２−ｎ１が成立しない場合で５（ｍ２−ｍ１＋１）＋３（ｎ２−ｎ１＋１）回となる。このように、変数最適化部１５で、連続する配列式が参照する配列の寸法が同じ場合に実行されるコードを追加することにより、実行時に寸法が同じときのメモリアクセス回数を（ｍ２−ｍ１＋１）回削減することができる。

本実施形態では、連続して現れる配列式の形状が、翻訳時に一致するか否かが不明であるとき、寸法が同じときに実行されるコードを中間コードに追加し、実行時に、寸法が等しいか否かを判断して、寸法が同じときに実行されるコードと、寸法が異なるときに実行するコードを呼び分ける。寸法が同じであるときに実行されるコード部分は、最適化部１３にて、ループ融合、共通式の削除が可能である。従って、実行時に、連続する配列式の寸法が等しいときのメモリアクセス回数を削減することができ、プログラムの実行速度を向上させることができる。

以上、本発明をその好適な実施形態に基づいて説明したが、本発明のコンパイラ、変数最適化装置、方法、及び、プログラムは、上記実施形態にのみ限定されるものではなく、上記実施形態の構成から種々の修正及び変更を施したものも、本発明の範囲に含まれる。

本発明の第１実施形態のコンパイラを示すブロック図。 変数最適化部の動作手順を示すフローチャート。 宣言情報テーブルのデータ例を示す図。 配列式テーブルのデータ例を示す図。 （ａ）〜（ｄ）は、参照配列テーブルのデータ例を示す図。 確定変数テーブルのデータ例を示す図。 変数最適化部による最適化後の中間コードを示す図。 最適化部による最適化後の中間コードを示す図。 図８に示す中間コードにおけるメモリアクセスを示す図。 変数最適化部による最適化を経ない中間コードにおけるメモリアクセスを示す図。 本発明の第２実施形態のコンパイラを示すブロック図。 第２実施形態における変数最適化部の動作手順を示すフローチャート。 ソースプログラム例を示す図。 宣言情報テーブルのデータ例を示す図。 配列式テーブルのデータ例を示す図。 （ａ）〜（ｃ）は、参照配列テーブルのデータ例を示す図。 最適化候補配列式リストのデータ例を示す図。 図１３に示すソースプログラムに対応する中間コードを示す図。 変数最適化部による最適化後の中間コードを示す図。 最適化部による最適化後の中間コードを示す図。 図２０に示す中間コードにおけるメモリアクセスを示す図。 変数最適化前後でのメモリアクセス回数を示す図。 ソースプログラムの一例を示す図。 図２３のソースプログラムから生成される中間コードを示す図。

符号の説明

１０：コンパイラ
１１：中間コード生成部
１２、１５：変数最適化部
１３：最適化部
１４：コード生成部
２１：宣言情報・配列式検出手段
２２：参照配列検出手段
２３：変数関係確定手段
２４：変数定義検出手段
２５：変数置換手段
２６：参照配列・連続出現配列式検出手段
２７：寸法比較手段
２８：分岐追加手段
３１：ソースプログラム
３２、３６、３７：中間コード
３３：宣言情報テーブル、配列式テーブル
３４、３９：参照配列テーブル
３５：確定変数テーブル
３８：オブジェクトプログラム
４０：最適化候補配列式リスト

Claims (6)

1. 複数の配列を演算する配列式を含む中間コードを読み出し、前記中間コードから、配列式を複数検出する配列式検出部と、
   前記配列式検出部で検出された複数の配列式でそれぞれ演算される複数の配列のそれぞれについて、配列の寸法を表す寸法式を当該配列の上限を表す変数と下限を表す変数とを用いて計算し、第１の変数を用いて寸法式が計算された第１の配列の寸法と、第２の変数を用いて寸法式が計算された第２の配列の寸法と、は、前記第１の配列と前記第２の配列とが同じ配列式で演算される場合に、同じ寸法である、という関係を表す関係式を決定する変数関係確定部と、
   前記第１の配列と前記第２の配列とを演算する配列式が前記中間コードから検出された配列式検出位置よりも前の位置で、前記第１の変数若しくは前記第２の変数の値を定義する前定義式を検出し、前記配列式検出位置よりも後の位置で、前記第１の変数若しくは前記第２の変数の値を定義する後定義式を検出する変数定義検出部と、
   前記変数関係確定部で決定された関係式に基づいて、前記複数の配列式でそれぞれ演算される複数の配列の寸法式の内で、前記変数定義検出部で前定義式が検出された位置から、前記変数定義検出部で後定義式が検出された位置までの位置で検出された配列式で演算される配列の寸法式であって前記第１の変数を用いて計算された寸法式を、前記第２の変数を用いて計算された寸法式に置換する寸法式置換部と、
   前記寸法式置換部で置換された寸法式と同じ寸法式で表される寸法の配列を演算する複数の配列式にそれぞれ従って、繰り返し実行される複数のループ処理から当該複数のループ処理に共通した共通演算式を削除し、かつ当該複数のループ処理を融合させるループ最適化を行う最適化部と、
   を備える変数最適化装置。
2. 前記配列式検出部で検出された複数の配列式の内で、連続して処理される複数の配列式のそれぞれで演算される複数の配列の寸法が翻訳時にそれぞれ同一であると確定しているか否かを、前記変数関係確定部で計算された寸法式に基づいて判別する寸法判別部と、
   前記変数関係確定部で前記複数の配列の寸法がそれぞれ同一であると翻訳時には確定していないと判別されると、実行時に前記複数の配列の寸法がそれぞれ同じ場合に実行される寸法同一時処理と、前記複数の配列の寸法がそれぞれ同じでない場合に実行される寸法非同一時処理と、に処理を分岐する処理を追加する分岐追加部と、をさらに備え、
   前記最適化部は、前記連続して処理される複数の配列式にそれぞれ従って、繰り返し実行される複数のループ処理をループ最適化した処理を前記寸法同一時処理とする、
   ことを特徴とする請求項１に記載の変数最適化装置。
3. コンピュータを、
   複数の配列を演算する配列式を含む中間コードを読み出し、前記中間コードから、配列式を複数検出する配列式検出部、
   前記配列式検出部で検出された複数の配列式でそれぞれ演算される複数の配列のそれぞれについて、配列の寸法を表す寸法式を当該配列の上限を表す変数と下限を表す変数とを用いて計算し、第１の変数を用いて寸法式が計算された第１の配列の寸法と、第２の変数を用いて寸法式が計算された第２の配列の寸法と、は、前記第１の配列と前記第２の配列とが同じ配列式で演算される場合に、同じ寸法である、という関係を表す関係式を決定する変数関係確定部、
   前記第１の配列と前記第２の配列とを演算する配列式が前記中間コードから検出された配列式検出位置よりも前の位置で、前記第１の変数若しくは前記第２の変数の値を定義する前定義式を検出し、前記配列式検出位置よりも後の位置で、前記第１の変数若しくは前記第２の変数の値を定義する後定義式を検出する変数定義検出部、
   前記変数関係確定部で決定された関係式に基づいて、前記複数の配列式でそれぞれ演算される複数の配列の寸法式の内で、前記変数定義検出部で前定義式が検出された位置から、前記変数定義検出部で後定義式が検出された位置までの位置で検出された配列式で演算される配列の寸法式であって前記第１の変数を用いて計算された寸法式を、前記第２の変数を用いて計算された寸法式に置換する寸法式置換部、
   前記寸法式置換部で置換された寸法式と同じ寸法式で表される寸法の配列を演算する複数の配列式にそれぞれ従って、繰り返し実行される複数のループ処理から当該複数のループ処理に共通した共通演算式を削除し、かつ当該複数のループ処理を融合させるループ最適化を行う最適化部、
   として機能させるための変数最適化プログラム。
4. コンピュータが、複数の配列を演算する配列式を含む中間コードを読み出し、前記中間コードから、配列式を複数検出する配列式検出ステップと、
   前記コンピュータが、前記配列式検出ステップで検出された複数の配列式でそれぞれ演算される複数の配列のそれぞれについて、配列の寸法を表す寸法式を当該配列の上限を表す変数と下限を表す変数とを用いて計算し、第１の変数を用いて寸法式が計算された第１の配列の寸法と、第２の変数を用いて寸法式が計算された第２の配列の寸法と、は、前記第１の配列と前記第２の配列とが同じ配列式で演算される場合に、同じ寸法である、という関係を表す関係式を決定する変数関係確定ステップと、
   前記コンピュータが、前記第１の配列と前記第２の配列とを演算する配列式が前記中間コードから検出された配列式検出位置よりも前の位置で、前記第１の変数若しくは前記第２の変数の値を定義する前定義式を検出し、前記配列式検出位置よりも後の位置で、前記第１の変数若しくは前記第２の変数の値を定義する後定義式を検出する変数定義検出ステップと、
   前記コンピュータが、前記変数関係確定ステップで決定された関係式に基づいて、前記複数の配列式でそれぞれ演算される複数の配列の寸法式の内で、前記変数定義検出ステップで前定義式が検出された位置から、前記変数定義検出ステップで後定義式が検出された位置までの位置で検出された配列式で演算される配列の寸法式であって前記第１の変数を用いて計算された寸法式を、前記第２の変数を用いて計算された寸法式に置換する寸法式置換ステップと、
   前記コンピュータが、前記寸法式置換ステップで置換された寸法式と同じ寸法式で表される寸法の配列を演算する複数の配列式にそれぞれ従って、繰り返し実行される複数のループ処理から当該複数のループ処理に共通した共通演算式を削除し、かつ当該複数のループ処理を融合させるループ最適化を行う最適化ステップと、
   を有する変数最適化方法。
5. コンピュータを、
   複数の配列を演算する配列式を含む中間コードを読み出し、前記中間コードから、配列式を複数検出する配列式検出部、
   前記配列式検出部で検出された複数の配列式でそれぞれ演算される複数の配列のそれぞれについて、配列の寸法を表す寸法式を当該配列の上限を表す変数と下限を表す変数とを用いて計算し、第１の変数を用いて寸法式が計算された第１の配列の寸法と、第２の変数を用いて寸法式が計算された第２の配列の寸法と、は、前記第１の配列と前記第２の配列とが同じ配列式で演算される場合に、同じ寸法である、という関係を表す関係式を決定する変数関係確定部、
   前記第１の配列と前記第２の配列とを演算する配列式が前記中間コードから検出された配列式検出位置よりも前の位置で、前記第１の変数若しくは前記第２の変数の値を定義する前定義式を検出し、前記配列式検出位置よりも後の位置で、前記第１の変数若しくは前記第２の変数の値を定義する後定義式を検出する変数定義検出部、
   前記変数関係確定部で決定された関係式に基づいて、前記複数の配列式でそれぞれ演算される複数の配列の寸法式の内で、前記変数定義検出部で前定義式が検出された位置から、前記変数定義検出部で後定義式が検出された位置までの位置で検出された配列式で演算される配列の寸法式であって前記第１の変数を用いて計算された寸法式を、前記第２の変数を用いて計算された寸法式に置換する寸法式置換部、
   前記寸法式置換部で置換された寸法式と同じ寸法式で表される寸法の配列を演算する複数の配列式にそれぞれ従って、繰り返し実行される複数のループ処理から当該複数のループ処理に共通した共通演算式を削除し、かつ当該複数のループ処理を融合させるループ最適化を行う最適化部、
   前記最適化部でループ最適化された中間コードに基づいて、オブジェクトプログラムを生成するコード生成部、
   として機能させるためのコンパイラ。
6. コンピュータが、複数の配列を演算する配列式を含む中間コードを読み出し、前記中間コードから、配列式を複数検出する配列式検出ステップと、
   前記コンピュータが、前記配列式検出ステップで検出された複数の配列式でそれぞれ演算される複数の配列のそれぞれについて、配列の寸法を表す寸法式を当該配列の上限を表す変数と下限を表す変数とを用いて計算し、第１の変数を用いて寸法式が計算された第１の配列の寸法と、第２の変数を用いて寸法式が計算された第２の配列の寸法と、は、前記第１の配列と前記第２の配列とが同じ配列式で演算される場合に、同じ寸法である、という関係を表す関係式を決定する変数関係確定ステップと、
   前記コンピュータが、前記第１の配列と前記第２の配列とを演算する配列式が前記中間コードから検出された配列式検出位置よりも前の位置で、前記第１の変数若しくは前記第２の変数の値を定義する前定義式を検出し、前記配列式検出位置よりも後の位置で、前記第１の変数若しくは前記第２の変数の値を定義する後定義式を検出する変数定義検出ステップと、
   前記コンピュータが、前記変数関係確定ステップで決定された関係式に基づいて、前記複数の配列式でそれぞれ演算される複数の配列の寸法式の内で、前記変数定義検出ステップで前定義式が検出された位置から、前記変数定義検出ステップで後定義式が検出された位置までの位置で検出された配列式で演算される配列の寸法式であって前記第１の変数を用いて計算された寸法式を、前記第２の変数を用いて計算された寸法式に置換する寸法式置換ステップと、
   前記コンピュータが、前記寸法式置換ステップで置換された寸法式と同じ寸法式で表される寸法の配列を演算する複数の配列式にそれぞれ従って、繰り返し実行される複数のループ処理から当該複数のループ処理に共通した共通演算式を削除し、かつ当該複数のループ処理を融合させるループ最適化を行う最適化ステップと、
   前記コンピュータが、前記最適化ステップでループ最適化された中間コードに基づいて、オブジェクトプログラムを生成するコード生成ステップと、
   を有するコンパイル方法。

Images