(57)【特許請求の範囲】
【請求項１】
ソーステキストを読み込みコード生成を行うコンピュータシステムにおいて、
予め定められた最適化のレベル、配列記述の配列の次元数、および各次元の配列数に基づき、前記ソーステキストに含まれる配列記述に関する最適化実施文数を求める最適化実施文数決定手段と、
前記最適化実施文数決定手段で求めた最適化実施文数に基づき配列記述の最適化実施範囲を決定する最適化実施範囲決定手段とを備えることを特徴とするコンピュータシステム。
【請求項２】
前記最適化実施範囲決定手段で決定した最適化実施範囲内で、前記配列記述の形状を表現する情報を抽出する配列記述形状情報抽出手段をさらに備えることを特徴とする請求項１記載のコンピュータシステム。
【請求項３】
前記配列記述形状情報抽出手段で抽出した情報から、各配列記述に対し共通の式を検出して該各配列記述に対し共用となる情報を認識する共通式認識手段をさらに備えることを特徴とする請求項２記載のコンピュータシステム。
【請求項４】
前記共通式認識手段により認識した情報をもとに、コード生成時に形状が確定する配列形状に対し、該配列形状を最適なループに変換するためのループ融合をすべきか否かを判定するループ融合判定処理手段をさらに備えることを特徴とする請求項３記載のコンピュータシステム。
【請求項５】
前記配列記述をループに変換する場合に、前記配列記述形状情報抽出手段で抽出した情報をリスト形式で保持する配列リスト保持手段にて保持された情報から、最適なループの形状を選択するループ形状選択手段をさらに備えることを特徴とする請求項３記載のコンピュータシステム。
【請求項６】
ソーステキストを読み込みコード生成を行うコンピュータシステムが、
予め定められた最適化のレベル、配列記述の配列の次元数、および各次元の配列数に基づき、前記ソーステキストに含まれる配列記述に関する最適化実施文数を求める最適化実施文数決定ステップと、
前記最適化実施文数決定ステップで求めた最適化実施文数に基づき配列記述の最適化実施範囲を決定する最適化実施範囲決定ステップとを実行することを特徴とするコード生成最適化制御方法。
【請求項７】
前記コンピュータシステムが、
前記最適化実施範囲決定ステップで決定した最適化実施範囲内で、前記配列記述の形状を表現する情報を抽出する配列記述形状情報抽出ステップをさらに実行することを特徴とする請求項６記載のコード生成最適化制御方法。
【請求項８】
前記コンピュータシステムが、
前記配列記述形状情報抽出ステップで抽出した情報から、各配列記述に対し共通の式を検出して該各配列記述に対し共用となる情報を認識する共通式認識ステップをさらに実行することを特徴とする請求項７記載のコード生成最適化制御方法。
【請求項９】
前記コンピュータシステムが、
前記共通式認識ステップにより認識した情報をもとに、コード生成時に形状が確定する配列形状に対し、該配列形状を最適なループに変換するためのループ融合をすべきか否かを判定するループ融合判定処理ステップをさらに実行することを特徴とする請求項８記載のコード生成最適化制御方法。
【請求項１０】
前記コンピュータシステムが、
前記配列記述をループに変換する場合に、前記配列記述形状情報抽出ステップで抽出した情報をリスト形式で保持する配列リスト形式保持ステップにて保持された情報から、最適なループの形状を選択するループ形状選択ステップをさらに実行することを特徴とする請求項８記載のコード生成最適化制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、JIS X 3001により規定されたFORTRAN 90｛ANSI（American National Standards of Institute）ではX3.198、因みにISO/IEC 1539:1991 もある｝のような新たな言語仕様として追加された配列記述に対して、より最適なコード生成を促進するための配列記述の最適化制御装置および制御方法に関する。通常、ベクトルプロセッサを有していないマシン、例えば、コンピュータシステムにおいては、上記の配列記述は、ソースプログラム（原始プログラム）等の入力としてのテキスト（通常、ソーステキストとよばれる）をオブジェクトプログラム（機械語のプログラム）に変換するためのコンパイラの内部で一つまたは複数のループに展開される。オブジェクトプログラムにおけるループの部分は実行時間の比重が高いため、配列記述に関係する部分のコードを最適な状態に生成することは、実行時間の短縮に大きく貢献することになる。本発明は、種々の分野にわたって広汎に利用するために確立すべき言語仕様として新たに追加された配列記述に対しても、実行時間の短縮を実現するための一方策について言及するものである。
【０００２】
さらに、本発明は、上記のFORTRAN 90に限らず、配列記述が可能な言語仕様をもつ言語全般に対しても有効であることがわかっており、本発明の最適化制御装置および制御方法の有用性を示唆している。
【０００３】
【従来の技術】
下記の数１の式においては、テキストの配列を操作する配列代入文等の複数の文（式）からなる従来の配列記述の一例が示されている。例えば、FORTRAN 90から新たに言語仕様として追加された配列記述では、以下の数１の右側部分に示すように、配列に対する演算や代入操作をＤＯ文等のループ制御文を使用せずに記述することができる。
【０００４】
【数１】
0003695798.tif 000002
【０００５】
前述したように、配列記述はコンパイラ内部でループに変換して実行する。このときに、配列記述からループへの変換を一文ずつ行うと実行性能が悪いため、通常、ループ融合とよばれる最適化制御を実施する。すなわち、下記の数２の右側部分に示すように、同じループにより実行可能な配列記述（数２の左側部分）をまとめることによって特定の配列記述の部分を同じループで実行するように変換することができる。
【０００６】
【数２】
0003695798.tif 000003
【０００７】
しかしながら、従来の最適化制御の手法では、下記の数３の式に示すように、形状を表現する添字式が異なっている配列記述に関しては、配列の形状が一致していないとみなされるため、ループ融合を行うことができなかった。
【０００８】
【数３】
0003695798.tif 000004
【０００９】
【発明が解決しようとする課題】
上記のとおり、従来の最適化制御の手法では、配列記述においてループ融合を可能にするためには、配列の形状が完全に一致している必要がある。すなわち、従来の最適化制御の手法では、前述の数２に示したように、配列の形状が完全に一致することが判定可能であるものしかループ融合をすることができなかった。すなわち、従来の手法では、ループの形状が実行時に確定し、形状が異なる計算式等により最適なコード生成が求められている場合は、ループ融合を実施することができなかった。
【００１０】
また一方で、従来はオプションによって最適化レベルを制御しているが、最適化で必要とする翻訳資源は入力となるソースの複雑さに依存することが多いのに、その情報をコンパイラの最適化レベルの制御に使っていないため翻訳資源を有効に使っていない場合があった。
本発明は、上記問題点に鑑みてなされたものであり、配列記述内の式を複雑にすることなく最適のループ制御を行うことにより、従来のループ融合処理では形状の一致が判定できなかった場合のループ融合処理の問題を解決することが可能な配列記述の最適化制御装置および制御方法を提供することを第１の目的とするものである。
【００１１】
さらに、本発明は、最適化レベルを比較的高く設定した場合に、ループ融合処理を含む配列記述のループ展開に依存する実行時間を従来よりも短縮することが可能な配列記述の最適化制御装置および制御方法を提供すること第２の目的とするものである。
【００１２】
【課題を解決するための手段】
図１は、本発明の原理構成を示すブロック図である。
図１に示すような本発明の配列記述の最適化制御装置においては、上記問題点を解決するために、入力となるテキスト１を読み込み、このテキスト１の配列を操作する文からなる複数の配列記述に対して最適なコード生成を行う場合に、予め定められた最適化のレベル、複数の配列記述の配列の次元数、および各次元の配列数に基づき、複数の配列記述に関する最適化実施範囲を判定する最適化実施範囲判定手段２を備えている。この最適化実施範囲判定手段２により判定された最適化実施範囲内で最適なコード８を出力することが可能になる。この場合、好ましくは、最適化のレベルは最適化レベル情報保持部３に保持されており、複数の配列記述の配列の次元数、および各次元の配列数は、次元数／配列数情報保持部４に保持されている。
【００１３】
さらに、好ましくは、図１に示すように、本発明の配列記述の最適化制御装置においては、上記の最適化実施範囲内で、複数の配列記述の形状を表現する情報を抽出する配列記述形状情報抽出手段５を備えている。この配列記述形状情報抽出手段５により抽出された情報は、リスト形式で保持される。
さらに、好ましくは、図１に示すように、本発明の配列記述の最適化制御装置は、複数の配列記述の形状を表現するためのリスト形式の情報から、各配列記述に対し共通の式を検出して各配列記述に対し共用となる情報を認識するための共通式認識手段６を備えている。
【００１４】
さらに、好ましくは、図１に示すように、本発明の配列記述の最適化制御装置は、共通式認識手段６により検出される結果をもとに、最適なコード生成において、実行時に形状が確定する配列記述に対し、この配列記述を最適なループに変換するためのループ融合をすべきか否かのループ融合判定処理がなされるループ融合判定処理手段７等を備えている。
【００１５】
さらに、好ましくは、本発明の配列記述の最適化制御装置においては、配列記述をループに変換する場合に、上記のリスト形式で保持された情報から、最適なループの形状を選択するように構成される。
また一方で、本発明の配列記述の最適化制御装置等により遂行される最適化制御方法は、予め定められた最適化のレベル、前記配列記述の配列の次元数、および各次元の配列数に基づき、複数の配列記述に関する最適化実施範囲を判定するステップを有し、このステップにより判定された最適化実施範囲内で最適なコードを出力するようにしている。
【００１６】
好ましくは、本発明の配列記述の最適化制御方法においては、上記の最適化実施範囲内で、配列記述の形状を表現する情報を抽出するステップを有し、このステップにより抽出された情報をリスト形式で保持するようにしている。
さらに、好ましくは、本発明の配列記述の最適化制御方法においては、上記のリスト形式で保持された情報から、各配列記述に対し共通の式を検出して各配列記述に対し共用となる情報を認識するステップを有している。
【００１７】
さらに、好ましくは、本発明の配列記述の最適化制御方法では、上記の共通の式を検出した結果をもとに、最適なコード生成において、実行時に形状が確定する配列記述に対し、この配列記述を最適なループに変換するためのループ融合をすべきか否かのループ融合判定処理を遂行するようにしている。
さらに、好ましくは、本発明の配列記述の最適化制御方法においては、配列記述をループに変換する場合に、上記のリスト形式で保持された情報から、最適なループの形状を選択するようにしている。
【００１８】
さらに詳しく説明すると、本発明の配列記述の最適化制御の手法では、ループの形状を判定する際に、FORTRAN 90等の新たな言語仕様からなる配列記述を演算対象とするデータ要素は、配列記述の左辺と右辺が形状適合しなければならないという規定を利用することにより、形状の一致を認識することができる範囲を拡大する。これにより、前述の数３の式に示したような従来の手法ではループ融合ができなかったケースについても、ループ融合の実行が可能になる。
【００１９】
これに加えて、本発明の配列記述の最適化制御の手法では、ループの融合処理の負荷および効果を考慮して、最適化レベルと、配列記述の配列の次元数および各次元の配列数（すなわち、式の複雑さ）をもとに、最適化を実施する範囲を動的に決定するようにしている。このような処理・構成により、最適化レベルに応じた翻訳作業域、翻訳時間、および実行時間を実現することが可能になる。
【００２０】
さらにまた、本発明の配列記述の最適化制御の手法では、配列記述のループ展開後のループの形状（ループの回転数の初期値や終値等）をより単純な形で表現するために、ループ融合の判定の際にも用いた配列の添字式の中から、ループの形状をより単純に表現できる式を選択する。これらの処理により、最適化レベルに依存した最適な配列記述のループ展開が実現される。
【００２１】
【作用】
入力となるテキスト、例えば、前述の数３の式に示したソースプログラムにおいて、配列記述の形状を代入文の左辺から求めた場合、以下のようになる。
数３の(1) の配列代入文の形状は、１次元で要素数がＬ
数３の(2) の配列代入文の形状は、１次元で要素数がＭ−１
数３の(3) の配列代入文の形状は、１次元で要素数がＮ−２
また一方で、配列記述の形状を代入文の右辺から求めた場合、以下のようになる。
【００２２】
数３の(1) の配列代入文の形状は、１次元で要素数がＭ−１
数３の(2) の配列代入文の形状は、１次元で要素数がＮ−２
数３の(3) の配列代入文の形状は、１次元で要素数がＫ
したがって、配列記述の右辺、または左辺だけの情報では、形状の一致を判定することができず、ループ融合は実行することができない。しかしながら、言語仕様の規定によれば、演算対象となるデータは形状適合（すなわち、配列記述の配列の次元数、および各次元の要素数が一致する）の状態にならなくてはならないので、
数３の(1) の配列代入文から、Ｌ＝Ｍ−１
(2) の配列代入文から、Ｍ−１＝Ｎ−２
(3) の配列代入文から、Ｎ−２＝Ｋ
∴Ｌ＝Ｍ−１＝Ｎ−２＝Ｋ
を導くことができるので、数３の(1) 、(2) および(3) の配列記述のループ融合が可能になる。上記の言語仕様を利用した共通式の認識とループ融合の様子は、下記の数４の式に詳しく示すこととする。
【００２３】
【数４】
0003695798.tif 000005
【００２４】
続いて、最適化レベル、および式の複雑さから、最適化を実施する範囲を動的に決定することにより、最適化レベルに応じた翻訳作業域、翻訳時間、および実行時間を実現できるような処理を追加した理由を説明する。なお、ここで説明するような理論をもとに、実際に最適化実施範囲を決定する式は次節の実施例の項で示すこととする）。
【００２５】
一般に、次元数Ｍ、文数Ｌ（Ｌ≧２）、ｉ番目の文i （ｉ＝１、２、…、Ｌ）の配列の個数をＮi （ｉ＝１、２、…、Ｌ）とした場合、文1 と文2 の形状一致判定には、
Ｍ×（Ｎ1 ×Ｎ2 ）（回）
文1 、文2 と文3 との形状一致判定には、
Ｍ×（Ｎ1 ＋Ｎ2 ）×Ｎ3 （回）
同様にして文1 〜文L-1 と文L との形状一致判定には、
Ｍ×（Ｎ1 ＋Ｎ2 ＋…ＮL-1 ）×ＮL ）
回必要となる。文数Ｌの配列記述すべてに対し形状の一致判定を行う場合、必要な形状一致判定の回数は、上記のすべての形状一致判定回数の総和になるので、以下の数５のように表される。
【００２６】
【数５】
0003695798.tif 000006
【００２７】
ここで、文の複雑さがすべて等しい（Ｎ1 ＝Ｎ2 ＝…＝ＮL ＝Ｎ）とすると、必要な形状一致判定の回数は、以下の数６のように表される。
【００２８】
【数６】
0003695798.tif 000007
【００２９】
すなわち、数６の式に示す形状一致判定の回数だけ、一致判定動作を行わなければならない。
このことは、式の複雑さを表すＮ、および解析対象とする配列記述の文数Ｌに対して、翻訳時間が２乗のオーダーで増加することを意味する。上記の数５の式より、翻訳資源、翻訳時間、および翻訳作業域を有効に利用するためには、式の複雑さを判定し、最適化実施範囲を動的に判定する必要があるといえる。また一方で、当然のことながら、より多くの翻訳資源を利用することで、より高度なループ融合が可能となり、実行時間を短縮することができる。しかしながら、実際には翻訳資源が限られているために、上記のように無制限に翻訳資源を利用できる訳ではない。
【００３０】
本発明によれば、ループの形状を判定する際に形状の一致を認識することができる範囲を拡大し、さらに、ループの融合処理の負荷および効果を考慮して、最適化レベル、および式の複雑さをもとに、最適化を実施する範囲を動的に決定するようにしているので、翻訳資源を無駄にしたり配列記述内の式を複雑にすることなく、最適化レベルに応じた翻訳作業域、翻訳時間、および実行時間を実現することが可能になる。
【００３１】
【実施例】
以下、添付図面（図２〜図１１）を参照しながら本発明の配列記述の最適化制御を実現するための実施例について説明する。
図２は、本発明の最適化制御を実現するための実施例の構成を示すブロック図である。ただし、ここでは、ＣＰＵ（Central Processing Unit ：中央処理装置）を備えたコンピュータシステムによって本発明の最適化制御装置を構成する場合を代表して示す。なお、これ以降、前述した構成要素と同様のものについては、同一の参照番号を付して表すこととする。
【００３２】
図２において、前述の図１に示した最適化実施範囲判定手段２、配列記述形状情報抽出手段５、共通式認識手段６、およびループ融合判定処理手段７を含む最適化制御部５０は、コンピュータシステムのＣＰＵ２０により実現される。
さらに、前述の図１に示した最適化レベル情報保持部３および次元数／配列数情報保持部４は、図２のＣＰＵ２０に付設されたＲＡＭやＲＯＭ等の記憶部３０内に予め記憶されている。なお、記憶部３０として、ＣＰＵ２０に内蔵のＲＡＭまたはＲＯＭを用いることもできる。
【００３３】
さらに、図２において、入力部１０より、入力の対象とすべきテキスト１（図１）が読み込まれる。さらに、テキスト１の配列を操作する文からなる複数の配列記述がＣＰＵ２０に入力される。
さらに、図２において、ＣＰＵ２０内でループ融合判定処理を行うことにより最適化制御がなされた最適なコード８（図１）が生成され、出力部８０から出力される。
【００３４】
図２の実施例から明らかなように、本発明の最適化実施範囲の判定、配列記述形状情報の抽出、共通式の認識、およびループ融合の判定等の機能は、現行のコンピュータシステムを利用することによって容易に実現することができる。
図３は、本発明の実施例の概略的な動作を説明するための流れ図である。
図３のステップＳ１（すなわち、第１フェーズ）において、入力の対象とすべきテキストを読み込み、このテキストを構成する配列記述を検出すると共に、最適化実施範囲の見積りを行う。ここでは、テキストのどの部分からどの部分まで最適化処理を行うかが決定される。本発明の最適化処理において入力となるテキストは、プリプロセッサ方式の場合はソースプログラムであり、中間言語を利用するコンパイラにおいては中間コードである。
【００３５】
次に、ステップＳ２において、前述のステップＳ１で求めた最適化実施範囲を選択して取り出す。このようにして取り出された最適化実施範囲は、途中に他の文からの飛び込みや飛び出しがない限り、有効なものとなる。
さらに、上記の最適化実施範囲が有効なものであると判定された場合、ステップＳ３（すなわち、第２フェーズ）において、配列記述の形状を表現する情報の取り出し処理を行う。
【００３６】
さらに、上記の最適化実施範囲が有効なものであると判定された場合、ステップＳ４（すなわち、第３フェーズ）において、前述のステップＳ３にて取り出した情報に対してリストを作成し、登録を行う。これと同時に、同一データの共通化を行い、共通式の認識とループ融合の判定を行う。これらの第１フェーズおよび第３フェーズの処理を実行することにより、配列記述の形状の計算式が同じ式で求められ、形状の一致判定が可能になる。この結果、ステップＳ５において、従来の手法ではループ融合が不可能であったループが融合可能となる。さらに、ループ展開時のループの初期値、最終値、および増分値をより単純な式で表現することも可能になる。上記の第１フェーズ〜第３フェーズに関しては、後述の図４〜図１１に基づいて詳細に説明することとする。
【００３７】
図４および図５は、それぞれ、図３における配列記述の検出と最適化実施範囲の見積りの処理手順の詳細を説明するための流れ図その１およびその２である。ここでは、配列記述の最適化処理の第１フェーズ（図３のステップＳ１）について説明する。
この第１フェーズの処理では、まず、ステップＳ４１において、配列記述の開始位置（例えば、φ）、終了位置（例えば、φ）および文数（例えば、０）を初期設定することにより、最適化制御部（例えば、ＣＰＵ）の初期化を行う。次に、ステップＳ４２において、入力となるテキストを読み込み配列記述を検出する。入力となるテキストは、プリプロセッサ方式の場合はソースプログラムであり、中間言語を利用するコンパイラにおいては中間コードである。
【００３８】
上記の配列記述の検出動作は、ファイルの終了位置（ＥＯＦ）に達するまで続けられる（ステップＳ４３）。
さらに、他の文からの飛び込みや飛び出しがないか否かを検出する（ステップＳ４４）と共に、入力となるテキスト内に配列記述が連続して出現するか否かを確認する（ステップＳ４５）。さらに、最適化レベル、および式の複雑さに基づき、最適化実施文数、すなわち、解析対象とする配列記述の文数を順次計算する（ステップＳ４６）。
【００３９】
さらに、図５のステップＳ４７において、テキストの配列記述の開始位置が未登録であるか否かを確認する。
もし未登録であれば、ステップＳ４８において、配列記述の開始位置の登録、次元数の取り出し、項（例えば、配列の数）のカウント、および最適化実施文数の見積りを行う。
【００４０】
さらに、先程の見積り計算を行った最適化実施文数の範囲内で配列記述の終了位置を更新し（ステップＳ４９およびＳ５０）た後に、配列記述が連続して出現し、かつ、途中に他の文からの飛び込みや飛び出しがない範囲を求める。このようにして求めた範囲が、最終的に、最適化実施範囲として取り出される（ステップＳ５１）。
【００４１】
この場合、上記の最適化実施文数は、以下の数７の式に基づいて計算可能であることが、経験上知られている。
【００４２】
【数７】
0003695798.tif 000008
【００４３】
・上記の数７において、αは翻訳資源係数である。
このαは、最適化レベルあたりの翻訳資源、翻訳時間および翻訳作業域等の使用増加率を表すものである。当値は、経験則に基づいたチューニングによって決定する。
・βは基準次元数である。
【００４４】
このβは、通常の配列記述において最も多く出現する次元数を表す。当値は、コンパイラ等によりFORTRAN を使用した数値計算においては、β＝３であることが経験上知られていることから３としている。
・γは基準配列数である。
このγは、通常の配列記述において最も多く出現する項数を表す。当値もまた、経験則に基づいたチューニングによって決定する。
【００４５】
・ＯＰＴは最適化レベルである。
このＯＰＴは、コンパイラ等が実施する最適化の度合いを１以上の数値で表現したものである。この値が大きいほど、より強い最適化を実施することを意味し、翻訳時間および翻訳作業域を代償として、より高い実行性能が実現され得る。
・ｄｉｍは配列記述の次元数を表す。
【００４６】
このｄｉｍの値が大きいほど、形状の一致判定に時間がかかる。処理時間は当値と比例関係にある。
・ｉｔｅｍは最初に出現した配列記述内の配列の個数である。
このｉｔｅｍの値が大きいほど、形状の一致判定に時間がかかる。本来、配列の個数は文毎に異なるが、式の複雑さは大体等しいという仮定の元に、最初に出現した配列記述からｉｔｅｍの値を求める。
【００４７】
図６および図７は、それぞれ、図３における配列記述の形状を表現する情報の取り出しの処理手順の詳細を説明するための流れ図その１およびその２である。ここでは、配列記述の最適化処理の第２フェーズ（図３のステップＳ３）について説明する。
この第２フェーズの処理は、大きく分けて次のａ）およびｂ）の２つの処理手順から構成されている。
【００４８】
ａ）最適化実施範囲内の配列記述の配列から要素数を表現する情報を取り出す処理
形状適合によって値が等値であるのは、同一配列記述内の同一次元の要素数である。当該処理は、値が等値であるデータを連続して取り出すための３重ループによって構成される。
【００４９】
ｂ）取り出した情報に対してリストを作成し、登録を行う処理（後述の図８参照）
ここでは、リストの作成と同時に、同一データの共通化を行う。当該処理においては、リスト作成時に、既存リストに対する照会を行うことで、同一情報を持つリストの作成が抑止される。さらに、同一情報を有するリストの出現によって、同じ値を表現するリスト同士をマージ（併合）する。
【００５０】
配列記述の最適化処理中の第２フェーズの処理を実行する場合、まず、図６のステップＳ６１において、ｉ＝０に設定して配列記述の初期化を行う。次に、図７のステップＳ７３において、ｉの値を１だけ増加させ、ｉ番目（ｉ＝ｉ＋１）の配列記述があるか否かをチェックする。もし、ｉ番目の配列記述があれば、図６のステップＳ６２において、ｉ番目の配列記述の取り出しを行う（３重ループ中の最初のループ）。
【００５１】
さらに、ステップ６３において、ｊ＝０に設定して配列記述の次元の初期化を行う。さらに、図７のステップＳ７０において、ｊの値を１だけ増加させ（ｊ＝ｊ＋１）、ステップＳ７１において、増加後のｊの値が、配列記述の次元数以下であるか否かをチェックする。もし、ｊの値が、配列記述の次元数以下であれば、図６のステップＳ６４において、ｋ＝０に設定する（３重ループ中の２番目のループ）。
【００５２】
さらに、ステップＳ６８において、ｋの値を１だけ増加させ（ｋ＝ｋ＋１）、図７のステップＳ６９において、ｋ番目の項があるか否かをチェックする。もし、ｋ番目の項があれば、図６のステップＳ６５において、ｋ番目の項を取り出す（３重ループ中の３番目のループ）。さらに、この項が配列の数であることを確認した後に（ステップＳ６６）、取り出した項に相当する情報に対してリストを作成し、登録を行う（ステップＳ６７）。すなわち、本発明では、３重ループの構成を採用することによって、配列記述の形状を表現するための値が等値であるようなデータを連続して取り出すことができる。このようにして取り出され、かつ、配列記述の形状を表現する情報に関するリストの作成および登録の処理は、ｉ、ｊおよびｋが所定の値に達するまで続けることができる。
【００５３】
図８は、図６におけるリストの作成と登録の処理手順の詳細を説明するための流れ図である。
図８のステップＳ８１において、まず、既に同じ情報を持つリストが存在するか否かをチェックする。この種のリストが存在しない場合、新たにリストを作成し（ステップＳ８２）、ｉ番目の配列記述が、ｊ次元目にて最初に作成されたリストに対応する配列記述であるか否かをチェックする（ステップＳ８３）。もし、ｉ番目の配列記述が、ｊ次元目にて最初に作成されたリストに対応する配列記述であれば、このように異なる値を表現するリストとして配列記述を登録する（ステップＳ８４）。
【００５４】
もし、ｉ番目の配列記述が、ｊ次元目にて最初に作成されたリストに対応する配列記述でなければ（ステップＳ８３）、以前に作成したリストと同じ値を表現するリストとして配列記述を登録する（ステップＳ８５）。
また一方で、既に同じ情報を持つリストが存在する場合（ステップＳ８１）、ステップＳ８６において、以前に作成したのと同じ値を表現するリストが存在するか否かをチェックする。もし、以前に作成したのと同じ値を表現するリストが存在するならば、このリストの作成と同時に、同一データの共通化を行う。この場合、リスト作成時に、既存のリストに対する照会を行うことで、同一情報を持つリストの作成が抑止される。さらに、同一情報を有するリストの出現によって、同じ値を表現するリスト同士をマージする（ステップＳ８７）。また一方で、ステップＳ８６において、以前に作成したのと同じ値を表現するリストが存在しない場合、同じ値を表現する既存のリストが存在しないとみなし、連鎖の基点を変更することによって（ステップＳ８８）新たにリストを作成する。
【００５５】
図９は、図８の処理手順により作成または登録されるリスト構造の一例を示す図であり、図１０は、ソーステキスト入力により作成されるリスト構造の一例を示す図である。
図９においては、リスト作成時に使用される３つのポインタが示されている。これらの３つのポインタとして、要素数を表現する情報へのポインタ、同じ値を表現するリストへのポインタ、および、違う値を表現する情報へのポインタが挙げられる。
【００５６】
さらに、図１０に示すように、ソーステキスト入力により作成されるリスト構造においては、上記のポインタが機能する。例えば、要素数Ｌ＝Ｍ−１＝Ｎ−２、Ｉ＝Ｊという関係を表現する場合、図１０のリスト構造から明らかなように、Ｌ、Ｍ−１、および、Ｎ−２は同じ値を表現するリストへのポインタを用いて連鎖状に表示され、ＩおよびＪも、同じ値を表現するリストへのポインタを用いて連鎖状に表示される。また一方で、ＬとＩとは、違う値を表現する情報へのポインタを用いて表示される。
【００５７】
さらに、配列記述の最適化処理の第３フェーズ（図３のステップＳ４）である共通式の認識とループ融合の判定処理について詳細に説明する。この第３フェーズは、以下の(1) 〜(3) の処理手順により遂行される。
(1) 作成したリストから式の値が等しい集合を得る。
(2) この集合の中で、最も簡単な式を選び出し、他の式を置換する。
【００５８】
(3) この結果、配列記述の形状の計算式が同じ式で求められ、形状の一致判定が行うことができる。
このような処理手順により、従来はループ融合不可能であったループが融合可能になる。また、ループ展開時のループの初期値、最終値、および増分値をより単純な式で表現することも可能になる。
【００５９】
図１１は、本発明の最適化制御を実現するための具体的な一例を示すブロック図である。図１１においては、本発明の最適化制御装置を、前述の図２の実施例よりも具体的な構成として開示している。
さらに、図１１において、ＣＰＵは、フロントエンドプロセッサ２１と、オプチマイズ・バックエンドプロセッサ（ＯＢＥ）２３とにより構成される。フロントエンドプロセッサ２１では、主として、構文解析等が実施される。また一方で、最適化制御部２５を含むオプチマイズ・バックエンドプロセッサ２３では、主として、最適化実施範囲内での共通式認識やループ融合判定処理等が行われる。
図１１に示す入力部１１および出力部８１は、それぞれ、前述の図２に示した入力部１０および出力部８０にほぼ対応する。
【００６０】
図１１の最適化制御装置の入力部１１に入力されるようなFORTRAN 90等の言語仕様からなるソーステキストは、プリプロセッサ方式の場合はソースプログラムであり、中間言語を利用する方式の場合は中間コードである。前者のプリプロセッサ方式の場合は、出力部８１から、Ｃ言語、FORTRAN 77等の言語仕様からなるコードが出力される。後者の中間言語を利用する方式の場合は、出力部８１から中間言語からなるコードが出力される。したがって、図１１の本発明の最適化制御装置においては、ソースプログラムおよび中間言語のいずれに対しても、共通式認識やループ融合判定処理等を含む最適化処理を遂行することができる。
【００６１】
【発明の効果】
以上説明したように、本発明の配列記述の最適化制御装置によれば、第１に、複数の配列記述に対して最適なコード生成を行う場合に、予め定められた最適化のレベル、配列の数、および、複数の配列記述の配列の次元数に基づき、複数の配列記述に関する最適化実施範囲を見積るようにしているので、最適化レベルに応じた翻訳時間、翻訳領域、および実行時間を設定することが可能になる。この結果、FORTRAN 90等に固有の配列記述に対して、ユーザが与える最適化レベルに依存した最適コードを生成することが可能になり、コンパイラ等の性能向上に大きく貢献することができる。
【００６２】
さらに、本発明の配列記述の最適化制御装置によれば、第２に、上記の最適化実施範囲内で、複数の配列記述の形状を表現する情報を抽出し、この抽出した情報をリスト形式で保持しているので、この種の情報をもとに形状の一致を認識することができる範囲を拡大することが可能になる。これにより、従来の手法ではループ融合ができなかったケースについても、ループ融合の実行が可能になり、実行時間の短縮が図れる。
【００６３】
さらに、本発明の配列記述の最適化制御装置によれば、第３に、複数の配列記述の形状を表現するためのリスト形式の情報から、各配列記述に対し共通の式を検出して各配列記述に対し共用となる情報を認識するようにしているので、翻訳資源を無駄にしたり配列記述内の式を複雑にすることなく、最適化レベルに応じた翻訳作業域、翻訳時間、および実行時間を実現することが可能になる。
【００６４】
さらに、本発明の配列記述の最適化制御装置によれば、第４に、最適なコード生成において、実行時に形状が確定する配列記述を最適なループに変換するためのループ融合をすべきか否かのループ融合判定処理を行うようにしているので、配列記述のループ展開後のループの形状をより単純な形で表現することが可能になる。この結果、実行時間の短縮が促進される。
【００６５】
さらに、本発明の配列記述の最適化制御装置によれば、第５に、配列記述をループに変換する場合に、上記のリスト形式で保持された情報から、最適なループの形状を選択するようにしているので、ループ融合判定の際にも用いた配列の添字式の中から、ループの形状をより単純に表現できる式が選択され、最適な配列記述のループ展開が実現される。
【００６６】
また一方で、本発明の配列記述の最適化制御方法によれば、第１に、複数の配列記述に対して最適なコード生成を行う場合に、予め定められた最適化のレベル、複数の配列記述の配列の次元数、および各次元の配列数に基づき、複数の配列記述に関する最適化実施範囲を見積っているので、最適化レベルに応じた翻訳時間、翻訳領域、および実行時間を実現することが可能になる。この結果、FORTRAN 90等に固有の配列記述に対して、ユーザが与える最適化レベルに依存した最適コードを生成することができる。
【００６７】
さらに、本発明の配列記述の最適化制御方法によれば、第２に、上記の最適化実施範囲内で、複数の配列記述の形状を表現する情報を抽出し、この抽出した情報をリスト形式で保持しているので、この種の情報をもとに形状の一致を認識することができる範囲を拡大することが可能になる。これにより、従来の方法ではループ融合ができなかった場合についても、ループ融合の実行が可能になり、実行時間の短縮が図れる。
【００６８】
さらに、本発明の配列記述の最適化制御方法によれば、第３に、複数の配列記述の形状を表現するためのリスト形式の情報から、各配列記述に対し共通の式を検出し、各配列記述に対し共用となる情報を認識しているので、翻訳資源を犠牲にしたり配列記述内の式を複雑にすることなく、最適化レベルに応じた翻訳作業域、翻訳時間、および実行時間を実現することが可能になる。
【００６９】
さらに、本発明の配列記述の最適化制御方法によれば、第４に、最適なコード生成において、実行時に形状が確定する配列記述を最適なループに変換するためのループ融合をすべきか否かのループ融合判定をしているので、配列記述のループ展開後のループの形状をより単純な形で表現することが可能になる。この結果、実行時間の短縮が促進される。
【００７０】
さらに、本発明の配列記述の最適化制御方法によれば、第５に、配列記述をループに変換する場合に、上記のリスト形式で保持された情報から、最適なループの形状を選択しているので、ループ融合判定の際にも用いた配列の添字式の中から、ループの形状をより単純に表現できる式が選択され、最適化レベルに依存した最適な配列記述のループ展開が実現される。
【００７１】
要約すれば、本発明では、FORTRAN 90等の新しい言語仕様を利用することにより、従来不可能であったループの融合が可能となる。さらに、最適化オプション、および式の複雑さから動的に最適化実施範囲を決定することにより、最適化レベルに応じた翻訳時間、翻訳領域、および実行時間の実現を可能にしている。さらに、上記のループ融合を施したループの展開時に、初期値、終値、および増分値等に対し、より最適なループの形状設定も可能となる。したがって、FORTRAN 90固有の配列記述に対して、ユーザが与える最適化レベルに依存した最適コードを生成することができる。このため、本発明は、コンパイラ等の性能向上に大きく貢献できる発明となり得る。
【図面の簡単な説明】
【図１】本発明の原理構成を示すブロック図である。
【図２】本発明の最適化制御を実現するための実施例の構成を示すブロック図である。
【図３】本発明の実施例の概略的な動作を説明するための流れ図である。
【図４】図３における配列記述の検出と最適化実施範囲の見積りの処理手順の詳細を説明するための流れ図（その１）である。
【図５】図３における配列記述の検出と最適化実施範囲の見積りの処理手順の詳細を説明するための流れ図（その２）である。
【図６】図３における配列記述の形状を表現する情報の取り出しの処理手順の詳細を説明するための流れ図（その１）である。
【図７】図３における配列記述の形状を表現する情報の取り出しの処理手順の詳細を説明するための流れ図（その２）である。
【図８】図６におけるリストの作成と登録の処理手順の詳細を説明するための流れ図である。
【図９】図８の処理手順により作成または登録されるリスト構造の一例を示す図である。
【図１０】ソーステキスト入力により作成されるリスト構造の一例を示す図である。
【図１１】本発明の最適化制御を実現するための具体的な一例を示すブロック図である。
【符号の説明】
１…テキスト
２…最適化実施範囲判定手段
３…最適化レベル情報保持部
４…次元数／配列数情報保持部
５…配列記述形状情報抽出手段
６…共通式認識手段
７…ループ融合判定処理手段
８…最適なコード
１０…入力部
２０…ＣＰＵ
３０…記憶部
５０…最適化制御部
８０…出力部
【図１】
0003695798.tif 000009
【図２】
0003695798.tif 000010
【図３】
0003695798.tif 000011
【図４】
0003695798.tif 000012
【図５】
0003695798.tif 000013
【図６】
0003695798.tif 000014
【図７】
0003695798.tif 000015
【図８】
0003695798.tif 000016
【図９】
0003695798.tif 000017
【図１０】
0003695798.tif 000018
【図１１】
0003695798.tif 000019