(57)【特許請求の範囲】
【請求項１】
記憶手段に格納されているソースプログラムをコンピュータに入力し、該コンピュータ上で実行される言語処理プログラムの処理により目的プログラムを生成して記憶手段に格納する際に適用される配列サマリ解析方法であって、前記配列は生成されたプログラムがその後実行される際に記憶手段に格納されるものであり、該配列サマリ解析方法は、該コンピュータにより、
（ａ）記憶手段から読み出したソースプログラムに対して構文解析を行い中間コードを生成して記憶手段に格納する構文解析ステップと、
（ｂ）記憶手段から読み出された該中間コード内の各ループに対して、該ループで値が書き込まれる可能性がある配列部分の集合と、該ループで必ず値が書き込まれる配列部分の集合と、該ループで値が読み出される可能性がある配列部分の集合と、該ループで値が書き込まれる前に読み出される可能性がある配列部分の集合とから構成される配列サマリを生成して記憶手段に格納する配列サマリ解析ステップと、
（ｃ）記憶手段から読み出された該配列サマリを元に、記憶手段から読み出された該中間コード内のループに対して配列プライベート化を行ってから記憶手段に書き込む配列プライベート化ステップと、
（ｄ）前記ステップ（ｃ）の書き換え後の中間コードを記憶手段から読み出し、該中間コード内のループに対して並列化を行って記憶手段に書き込むループ並列化ステップと、
（ｅ）前記ステップ（ｄ）の書き換え後の中間コードに対して目的プログラムを生成して記憶手段に書き込む目的プログラム生成ステップと
を実行するとともに、
前記ステップ（ｂ）が、
（ｆ）ループ飛び出し文およびループ飛び出し時のループ制御変数の値をスカラ変数に設定する文を含むループに対して該スカラ変数の値をループ制御変数の上限として配列サマリを計算するループ飛び出し時制御変数値配列サマリ解析ステップ
を含むことを特徴とする配列サマリ解析方法。
【請求項２】
前記ステップ（ｆ）において、ループ飛び出し文およびループ飛び出し時のループ制御変数の値をスカラ変数に設定する文がループ内に含まれる場合には、該ループの本体の配列サマリにおいて該ループのループ制御変数の上限を該スカラ変数で置き換え、変数消去法で該ループ制御変数を消去した結果を該ループの配列サマリとすることを特徴とする請求項１に記載の配列サマリ解析方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ループ飛び出し文を含むループに対して近似無しで配列サマリ解析を行う方法に関する。
【０００２】
【従来の技術】
並列化コンパイラでは、プログラムの実行性能を向上するために、種々の並列化変換をプログラムに実施する。並列化変換は主にループに対して適用されるが、各ループに任意の並列化変換が適用できるわけではなく、どの並列化変換が適用できるかを判定する必要がある。
【０００３】
並列化変換の適用性判定の核になるのは、ループ内でのデータの参照状況解析である。ループ内で参照されるデータには、スカラ変数と配列がある。スカラ変数の参照では常に同じメモリ領域が参照される。これに対して、配列は、添字の値によって別のメモリ領域が参照されるため、ループ内でどの配列のどの部分がどのように参照されるかを解析する必要がある。
【０００４】
そこで、並列化コンパイラでの並列化変換適用性判定の手段として、ループ内で参照される各配列の配列部分及び参照の性質を解析する配列サマリ解析が開発されている。配列サマリ解析については、文献１「M. Hall, B. Murphy, S. AmarＡＳinghe, S. Liao, M. Lam, Interprocedural analysis for parallelization, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, Springer-Verlag, August 1995.」に示されている。
【０００５】
例として、図４のプログラムで、配列Ａに対して配列プライベート化と呼ばれる並列化変換の適用性を判定する場合の配列サマリ解析について説明する。配列サマリ解析では、最内側ループから外側ループに向かってボトムアップに、また、プログラムの実行順序について逆順に、配列の参照状況を解析し、図８の配列サマリを求める。
【０００６】
ただし、図８において、Ｒは文やループ本体、ループなどのプログラム部分を表す。なお、ループ本体とはループ内の文全体であり、例えば図４のループＬ２の本体は文Ｓ２のみである。以下、ループＬに対してループＬの本体をＬ（ｂｏｄｙ）で表す。ループ本体の配列サマリは、ループの１回のイタレーション(ループの１回分の繰り返し)に対する配列サマリであり、ループの配列サマリは、ループの全イタレーションに対する配列サマリである。
【０００７】
まず文Ｓ２での配列サマリは、図９(a)のようになる。ループＬ２は文Ｓ２しか含まないので、ループＬ２の本体の配列サマリは、Ｓ２の配列サマリそのものとなり、図９(b)のようになる。Fourier-Motzkin変数消去法などの変数消去法を用いてループＬ２の本体の配列サマリからループＬ２のループ制御変数Ｋを消去することにより、ループＬ２の配列サマリは図９(c)のようになる。同様の処理を文Ｓ１及びループＬ１に対して行うことにより、ループＬ１の配列サマリは図９(d)のようになる。次に、ループＬ１とループＬ２の配列サマリからループＬ０の本体の配列サマリを求めると、図９(e)のようになる。
【０００８】
図９(e)において、ループＬ０の本体で配列ＡのＥｘｐｏｓｅｄＲｅａｄが空集合になることから、Ｌ０の各イタレーションで値を読み出される全ての配列部分は、同イタレーション内で予め値を設定済みであることが分かる。よって、ループＬ０の各イタレーションでは、他のイタレーションで設定した配列要素の値を読み出すことが無いことが分かる。そこで、ループＬ０の各イタレーションで別々の配列ＴＡ（１：Ｎ）を用意して配列Ａの代わりに用いることにより、ループＬ０の各イタレーションはお互いに無関係に実行できることが分かる。このような変換を配列プライベート化と呼ぶ。
【０００９】
配列プライベート化を行うことにより、ループＬ０の各繰り返しは独立に実行できるので、図５のように並列化することができる。ただし、ＤＯＡＬＬは並列化ループの始まりを示す。また、文Ｓ０は、配列ＴＡ（１：Ｎ）のメモリ領域をループの各イタレーションで別々に用意することを示す。
【００１０】
【発明が解決しようとする課題】
上記従来技術では、ループ内にループ飛び出しがある場合、近似して配列サマリ解析を行うと記述されている。しかしながら、具体的な近似方法は上記従来技術では示されていなかった。
【００１１】
なお、一般に、参照の可能性を示す集合については、実際の集合を含む集合で近似すればよく、参照の必然性を示す集合については、実際の集合に含まれる集合で近似すれば良いことが知られている。よって、ループに対する配列サマリのうち、値が書き込まれる可能性がある配列部分の集合と、値が読み出される可能性がある配列部分の集合と、値が書き込まれる前に読み出される可能性がある配列部分の集合は、ループ飛び出しが無い場合の配列サマリで近似し、必ず値が書き込まれる配列部分の集合は空集合で近似すれば、ループ飛び出しを含むループに対しても配列サマリ解析が行える。
【００１２】
このように、従来技術の拡張により、ループ飛び出しを含むループに対する配列サマリ解析を行う方法が考えられる。
【００１３】
しかし、上記のような従来技術の拡張では、近似により解析精度が不足し、並列化変換が実際には適用可能であるにもかかわらず、適用不能と判断してしまう場合があるという問題があった。
【００１４】
例えば、図６のプログラムでは、ループＬ１がループ飛び出しを含んでいるため、ループＬ１で必ず値が書き込まれる配列部分の集合ＭｕｓｔＷｒｉｔｅ（Ｌ１）が空集合で近似される。そのため、図１０に示すように、ループＬ０の本体の各イタレーションで値が書き込まれる前に読み出される可能性がある配列部分の集合、即ち、ＥｘｐｏｓｅｄＲｅａｄ（Ｌ０(body)）が空集合にならず、ループＬ０で配列Ａをプライベート化できると判定できなかった。そのために、ループＬ０の並列化も実施できなかった。
【００１５】
本発明の目的は、ループ飛び出し文を含むループに対して配列サマリ解析の精度を向上し、配列プライベート化の適用性を向上することである。
【００１６】
【課題を解決するための手段】
上記課題を解決するため、請求項１に係る発明は、記憶手段に格納されているソースプログラムをコンピュータに入力し、該コンピュータ上で実行される言語処理プログラムの処理により目的プログラムを生成して記憶手段に格納する際に適用される配列サマリ解析方法であって、前記配列は生成されたプログラムがその後実行される際に記憶手段に格納されるものであり、該配列サマリ解析方法は、該コンピュータにより、（ａ）記憶手段から読み出したソースプログラムに対して構文解析を行い中間コードを生成して記憶手段に格納する構文解析ステップと、（ｂ）記憶手段から読み出された該中間コード内の各ループに対して、該ループで値が書き込まれる可能性がある配列部分の集合と、該ループで必ず値が書き込まれる配列部分の集合と、該ループで値が読み出される可能性がある配列部分の集合と、該ループで値が書き込まれる前に読み出される可能性がある配列部分の集合とから構成される配列サマリを生成して記憶手段に格納する配列サマリ解析ステップと、（ｃ）記憶手段から読み出された該配列サマリを元に、記憶手段から読み出された該中間コード内のループに対して配列プライベート化を行ってから記憶手段に書き込む配列プライベート化ステップと、（ｄ）前記ステップ（ｃ）の書き換え後の中間コードを記憶手段から読み出し、該中間コード内のループに対して並列化を行って記憶手段に書き込むループ並列化ステップと、（ｅ）前記ステップ（ｄ）の書き換え後の中間コードに対して目的プログラムを生成して記憶手段に書き込む目的プログラム生成ステップとを実行するとともに、前記ステップ（ｂ）が、（ｆ）ループ飛び出し文およびループ飛び出し時のループ制御変数の値をスカラ変数に設定する文を含むループに対して該スカラ変数の値をループ制御変数の上限として配列サマリを計算するループ飛び出し時制御変数値配列サマリ解析ステップを含むことを特徴とする。
【００１７】
請求項２に係る発明は、請求項１の前記ステップ(f)において、ループ飛び出し文およびループ飛び出し時のループ制御変数の値をスカラ変数に設定する文がループ内に含まれる場合には、該ループの本体の配列サマリにおいて該ループのループ制御変数の上限を該スカラ変数で置き換え、変数消去法で該ループ制御変数を消去した結果を該ループの配列サマリとすることを特徴とする。
【００１８】
以上により、ループ飛び出し文を含むループであっても、ループ飛び出し時のループ制御変数の値をスカラ変数に設定する文がループ内に含まれる場合には、近似なしで配列サマリが計算されるので、配列サマリ解析の精度が向上し、配列プライベート化が適用可能となる。
【００１９】
【発明の実施の形態】
本発明は、ループ飛び出し文を含むループに対して近似無しで配列サマリ解析を行う方法に関するものである。以下では、本発明の１実施形態を図面を用いて説明する。
【００２０】
図１は、本発明実施後の、言語処理系の構成を示す。言語処理系２０は、ソースプログラム１０を入力し、ループ並列化などの最適化を施したうえで、目的プログラム３０を生成する。ソースプログラム１０は、ＦｏｒｔｒａｎやＣなどのプログラミング言語で記述されたプログラムであり、目的プログラム３０は、コンパイラでは機械語命令であり、プリプロセッサではＦｏｒｔｒａｎやＣなどのプログラミング言語である。
【００２１】
以下では、ソースプログラム１０がＦｏｒｔｒａｎで記述されたプログラムであり、目的プログラム３０もＦｏｒｔｒａｎで記述されたプログラムである場合を例にして説明する。すなわち、言語処理系２０がプリプロセッサの場合について説明する。
【００２２】
言語処理系は、２１，２２，２４，２５，２６の各ステップから構成される。これらのうち、ステップ２２では、ステップ２３の処理が追加されているが、他のステップは、公知の技術である。よって、ステップ２２以外については、簡単な説明に止める。
【００２３】
まずステップ２１では、ソースプログラム１０の構文解析を行い中間コード２８を生成する構文解析を行う。
【００２４】
ステップ２２では、中間コード２８の各ループ部分に対して、ループの実行により値が書き込まれる可能性がある配列部分の集合と、ループで必ず値が書き込まれる配列部分の集合と、ループで値が読み出される可能性がある配列部分の集合と、ループで値が書き込まれる前に読み出される可能性がある配列部分の集合から構成される配列サマリ２９を生成する配列サマリ解析を行う。
【００２５】
ステップ２２は、ステップ２３の処理を含んでおり、ステップ２３では、ループ飛び出し文およびループ飛び出し時のループ制御変数の値をスカラ変数に設定する文の両方を含むループに対して、このスカラ変数の値をループ制御変数の上限として近似無しで配列サマリ２９を計算するループ飛び出し時制御変数値配列サマリ解析を行う。なお、ステップ２２およびステップ２３の詳細については、後述する。
【００２６】
ステップ２４では、配列サマリ２９を元に、中間コード２８内のループに対して配列プライベート化を行う。ステップ２５では、ステップ２４の書き換え後の中間コード２８内のループに対してループ並列化を行う。ステップ２６では、ステップ２５の書き換え後の中間コード２８に対して目的プログラム３０を生成する。
【００２７】
上記の構成により、ループ飛び出し文を含むループに対して、そのループがループ飛び出し時のループ制御変数の値をスカラ変数に設定する文を含む場合には、ステップ２３により近似無しで配列サマリ２９が解析されるので、配列プライベート化２４の適用対象が増える。即ち、配列プライベート化２４の適用性が向上する。
【００２８】
図２は、図１のステップ２２およびステップ２３の詳細フローである。なお、図２のステップのうち、２２０，２３０，２３５，２３７が図１のステップ２３の詳細である。なお、図２では、与えられたループＬに対して、配列サマリ２９を計算する。
【００２９】
ステップ２１０では、ループＬの本体の配列サマリ２９（以下、ＡＳと呼ぶ）を求める。ループ本体の配列サマリ２９の解析方法は公知なので詳細は省略するが、ループ本体の配列サマリ２９を解析するに当たって内側ループの配列サマリ２９を求める場合には、図１の処理を再帰的に呼び出す。
【００３０】
ステップ２２０では、ループＬがループ飛び出し文を含むか否か判定する。これが真の場合はステップ２３０を実行し、偽の場合は、ステップ２５０を実行する。
【００３１】
ステップ２３０では、ループ飛び出し時のループＬのループ制御変数の値をスカラ変数に設定する文がループＬに含まれるか判定する。この処理の詳細は、後述するが、この結果が真の場合は２３５を実行し、偽の場合は２４０を実行する。
【００３２】
ステップ２３５では、配列サマリＡＳにおいて、ループＬのループ制御変数に対する上限を前記スカラ変数で置きかえる。ステップ２３７では、ステップ２３５で変更した配列サマリＡＳから、ループＬのループ制御変数を消去し、この結果をＬの配列サマリとする。
【００３３】
ステップ、２２０，２３０，２３５，２３７により、ループ飛び出し文およびループ飛び出し時のループ制御変数の値をスカラ変数に設定する文を含むループに対して、配列サマリ２９を近似無しに計算することが出来る。
【００３４】
ステップ２４０では、ループ飛び出し時のループ制御変数の値をスカラ変数に設定する文が含まれない場合の近似を行う。具体的には、値が必ず書き込まれる配列部分の集合を空集合にする。このステップの後でステップ２５０を実行することにより、ループに対する配列サマリ２９のうち、値が書き込まれる可能性がある配列部分の集合と値が読み出される可能性がある配列部分の集合と値が書き込まれる前に読み出される可能性がある配列部分の集合は、ループ飛び出しがない場合の配列サマリで近似され、必ず値が書き込まれる配列部分の集合は空集合で近似される。
【００３５】
ステップ２５０では、変数消去法により、配列サマリＡＳからループＬのループ制御変数を消去し、この結果をＬの配列サマリとする。
【００３６】
なお、ステップ２３７は図１のステップ２３の処理の一部のため、ステップ２５０と別の処理としたが、これらは同一の処理なので、ステップ２３５の処理の次にステップ２５０を実行しても良い。
【００３７】
図３は、図２のステップ２３０の詳細フローである。まずステップ３１０では、ループＬの本体の先頭の文をＳとする。
【００３８】
ステップ３２０では、Ｓがループ飛び出し文であるか否か判定し、これが真の場合はステップ３３０を実行し、偽の場合はステップ３４０を実行する。ステップ３３０では、ループ飛び出し時のループＬのループ制御変数の値をスカラ変数に設定する文は無いと判定して、処理を終わる。
【００３９】
ステップ３４０では、Ｓが代入文で、かつ、左辺がスカラ変数（以下、Ｖとする）、右辺がループＬのループ制御変数であるか否か判定する。これが真の場合は、ステップ３４２を実行し、偽の場合は、ステップ３６０を実行する。
【００４０】
ステップ３４２では、Ｓがループ飛び出し文を支配するか否か判定する。これが真の場合は、ステップ３４４を実行し、偽の場合はステップ３３０を実行する。なお、文Ｓ１が文Ｓ２を支配するとは、プログラムの先頭からＳ２に至る全てのパスでＳ１が予め実行されることを示す。支配関係の解析は、公知の技術であるので、詳細は省略する。
【００４１】
ステップ３４４では、スカラ変数Ｖへの代入文がループＬ中で１つであるか否か判定する。これが真の場合は、ステップ３５０を実行し、偽の場合は、ステップ３３０を実行する。
【００４２】
ステップ３４０，３４２，３４４により、文Ｓでループ飛び出し時のループ制御変数の値をスカラ変数Ｖに設定していることが判定できる。ステップ３５０では、ループ飛び出し時のループＬのループ制御変数の値をスカラ変数に設定する文はＳであると判定して、処理を終わる。
【００４３】
ステップ３６０では、ループＬ内に文Ｓの次の文が有るか否か判定する。これが真の場合は、ステップ３７０を実行し、Ｌ内のＳの次の文を新たなＳとして設定し、ステップ３２０に制御を移してループする。偽の場合は、ステップ３３０を実行する。
【００４４】
次に、図６のソースプログラム例を用いて、本発明の適用効果を説明する。図１１は、図６のソースプログラム例に対する本発明での配列サマリ２９を示す。なお、図６の例ではループＬ３とループＬ２はループ飛び出し文を含まないので、従来と同様の配列サマリ解析により解析され、図１０(a)および図１０(b)と同じになる。内容が同じなので、図１１ではこれらの配列サマリは省略した。
【００４５】
まずループＬ１はループ飛び出し文Ｓ３を含むので、図２のステップ２２０の判定結果が真となり、ステップ２３０が実行される。ステップ２３０では、図３のフローに従って、ループ飛び出し時のループＬ１のループ制御変数Ｋの値をスカラ変数に設定する文がループＬに含まれるか否か判定する。この結果、文Ｓ１がそのような文であると判定され、ステップ２３５が実行される。
【００４６】
ステップ２３５では、ループＬ１の本体の配列サマリ２９において、ループＬ１のループ制御変数Ｋに対する上限を文Ｓ１の代入先スカラ変数ＫＥで置きかえる。図１１(a)は、ループＬ１の本体の配列サマリ２９であり、図１１(b)は、ループ制御変数Ｋに対する上限を文Ｓ１の代入先スカラ変数ＫＥで置きかえたものである。
【００４７】
図１１(b)からループＬ１のループ制御変数Ｋを消去すると、図１１(c)になり、ループＬ１に対するＥｘｐｏｓｅｄＲｅａｄが近似無しで表現されたことが分かる。
【００４８】
図１１(c)を元にループＬ０に対する配列サマリ２９を計算すると図１１(d)となり、ループＬ０の本体に対するＥｘｐｏｓｅｄＲｅａｄが空集合になることが分かる。よって、ループＬ０内で配列Ａはプライベート化可能であることが分かる。
【００４９】
以上より、図１のステップ２４において、ループＬ０内で配列Ａはプライベート化され、この結果、図１のステップ２５でループＬ０はループ並列化される。よって、ステップ２６での処理により、図７に示す目的プログラム３０が生成される。
【００５０】
【発明の効果】
本発明により、ループ飛び出し文を含むループに対して配列サマリ解析の精度が向上し、配列プライベート化の適用性が向上する。これにより、ループ並列化可能となるループが増大し、プログラムの実行速度が向上する。
【図面の簡単な説明】
【図１】本発明実施後の言語処理系の構成図。
【図２】本発明実施後の配列サマリ解析の処理フロー図。
【図３】ステップ２３０の詳細フロー図。
【図４】従来技術でのソースプログラム例を示す図。
【図５】従来技術での目的プログラム例を示す図。
【図６】本発明でのソースプログラム例を示す図。
【図７】本発明での目的プログラム例を示す図。
【図８】配列サマリを示す図。
【図９】従来技術実施例での配列サマリを示す図。
【図１０】ループ飛び出しを含むループの従来技術配列サマリを示す図。
【図１１】ループ飛び出しを含むループの本発明配列サマリを示す図。
【符号の説明】
１０…ソースプログラム、２０…言語処理系、３０…目的プログラム、２１…構文解析、２２…配列サマリ解析、２３…ループ飛び出し時制御変数値配列サマリ解析、２４…配列プライベート化、２５…ループ並列化、２６…目的プログラム生成、２８…中間コード、２９…配列サマリ。
【図１】
0003539613.tif 000002
【図２】
0003539613.tif 000003
【図３】
0003539613.tif 000004
【図４】
0003539613.tif 000005
【図５】
0003539613.tif 000006
【図６】
0003539613.tif 000007
【図７】
0003539613.tif 000008
【図８】
0003539613.tif 000009
【図９】
0003539613.tif 000010
【図１０】
0003539613.tif 000011
【図１１】
0003539613.tif 000012