(57)【特許請求の範囲】
【請求項１】
逐次処理計算機用に記述されたプログラム中に現れる、手続き呼び出し文を含むループを分割するループ分割方法において、最適化可能な最適化可能分割ループと最適化不能な最適化不能分割ループに分割する場合、
（ａ）  該最適化不能分割ループに含まれる手続き呼び出し文の呼び出し先手続きに該最適化可能な最適化可能部分が存在する場合、該最適化可能部分を該最適化可能ループにまで移動可能なものと移動不能なものに分類するステップと、
（ｂ）  該移動可能な最適化可能部分を最適化可能分割ループ中へ移動するステップと
を有することを特徴とするループ分割方法。
【請求項２】
逐次処理計算機用に記述されたプログラム中に現れる、手続き呼び出し文を含むループを分割するループ分割方法において、
（ａ）  該ループに関して、手続きに跨って変数の参照関係を調べる依存解析ステップと、
（ｂ）  該ループを、最適化可能な複数の最適化可能分割ループと、最適化不能な複数の最適化不能分割ループに分割するループ分割ステップと、
（ｃ）  該最適化不能分割ループ中の文、およびその中に手続き呼び出し文があればその呼び出し先手続き中の文を再帰的に調べ、最適化可能な最適化可能文および最適化不能な最適化不能文を検出する文解析ステップと、
（ｄ）  手続きをノードとし、呼び出し元手続きから呼び出し先手続きへエッジをつないで、手続き呼び出し関係を表すコールグラフを作成し、手続きコピーの対象となる手続きを検出する手続きコピー解析ステップと、
（ｅ）  該最適化不能分割ループ中の該最適化可能文のうち、該最適化可能分割ループへ移動可能な文を検出し、移動後も変数間の依存関係を満たすように手続きをコピーし、該移動可能な文を移動するコピー変換ステップと、
（ｆ）  該最適化可能分割ループを最適化する最適化ステップ
を有することを特徴とするループ分割方法。
【請求項３】
逐次処理計算機用に記述されたプログラム中に現れる、手続き呼び出し文を含むループを分割するループ分割方法において、前記最適化として、並列化またはベクトル化を行なうステップを有することを特徴とする請求項２に記載のループ分割方法。
【請求項４】
前記手続きコピー解析ステップは、
（ｄ．１）    該最適化不能分割ループから直接呼び出される直接呼び出し手続き、（ｄ．２）    該最適化可能文を持つ最適化可能手続き、
（ｄ．３）    該コールグラフ上で該直接呼び出し手続きから手続き呼び出し関係に従ってエッジをたどり、該最適化可能手続きに至る間に現れる手続きである中間手続き、
をコピー対象手続きとして検出するステップを有することを特徴とする請求項２に記載のループ分割方法。
【請求項５】
前記コピー変換ステップは、
（ａ）該最適化不能分割ループ中の該最適化可能文に、該最適化不能文から該最適化可能文へのデータ依存を持たない前方最適化可能文がある場合は、
（ａ．１）  該直接呼び出し手続き、該最適化可能手続き、該中間手続きをコピーした、前方直接呼び出しコピー手続き、前方最適化可能コピー手続き、前方中間コピー手続きを作成し、
（ａ．２）  該最適化不能分割ループの直前にある該最適化可能分割ループの最後に、該前方直接呼び出しコピー手続きの手続き呼び出し文を挿入し、
（ａ．３）  該前方直接呼び出しコピー手続き、およびその中に手続き呼び出し文があればその呼び出し先手続きを再帰的に調べ、  該コピー対象手続きの手続き呼び出し文があれば該前方中間コピー手続きまたは該前方最適化可能コピー手続きの手続き呼び出し文に変更し、
（ａ．４）  該前方最適化可能文以外かつ該コピー対象手続き中の手続き呼出し文以外の文を、該前方直接呼び出しコピー手続き、該前方最適化可能コピー手続き、該前方中間コピー手続きから削除する、前方コピー変換ステップと、
（ｂ）  該最適化不能分割ループ中の該最適化可能文に、該最適化可能文から該最適化不能文へのデータ依存を持たない後方最適化可能文がある場合は、
（ｂ．１）  該直接呼び出し手続き、該最適化可能手続き、該中間手続きをコピーした、後方直接呼び出しコピー手続き、後方最適化可能コピー手続き、後方中間コピー手続きを作成し、
（ｂ．２）  該最適化不能分割ループの直後にある該最適化可能分割ループの先頭に、該後方直接呼び出しコピー手続きの手続き呼び出し文を挿入し、
（ｂ．３）  該後方直接呼び出しコピー手続き、およびその中に手続き呼び出し文があればその呼び出し先手続きを再帰的に調べ、該コピー対象手続きの手続き呼び出し文があれば該後方中間コピー手続きまたは該後方最適化可  能コピー手続きの手続き呼び出し文に変更し、
（ｂ．４）  該後方最適化可能文以外かつ該コピー対象手続き中の手続き呼出し文以外の文を、該後方直接呼び出しコピー手続き、該後方最適化可能コピー手続き、該後方中間コピー手続きから削除する後方コピー変換ステップと、
（ｃ）    （ｃ．１）  該直接呼び出し手続き、該最適化可能手続き、該中間手続きをコピーした、オリジナル直接呼び出しコピー手続き、オリジナル最適化可能コピー手続き、オリジナル中間コピー手続きを作成し、
（ｃ．２）  該最適化不能分割ループ中の該直接呼び出し手続きの手続き呼び出し文を、該オリジナル直接呼び出しコピー手続きの手続き呼び出し文に置換し、
（ｃ．３）  該オリジナル直接呼び出しコピー手続き、およびその中に手続き呼び出し文があればその呼び出し先手続きを再帰的に調べ、該コピー対象手続きの手続き呼び出し文があれば該オリジナル中間コピー手続きまたは該  オリジナル最適化可能コピー手続きの手続き呼び出し文に置換し、
（ｃ．４）  該最適化可能文を、該オリジナル直接呼び出しコピー手続き、該オリジナル最適化可能コピー手続き、該オリジナル中間コピー手続きから削除する、オリジナルコピー変換ステップと
を有することを特徴とする請求項２に記載のループ分割方法。
【請求項６】
前記請求項１〜５のいずれかに記載のループ分割方法における各ステップに記載された処理をプログラムに変換し、該プログラムを格納したことを特徴とする記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、計算機用プログラムを実行可能なプログラムに変換する最適化コンパイラに関し、特に、手続き呼び出しを有するループのループボディを、複数のループボディに分割して複数のループを作成するループ分割方法に関する。
【０００２】
【従来の技術】
従来、ループ実行高速化を促進するため、種々のループ構造変換法が利用されている。その中の１つにループ分割（ｌｏｏｐ  ｄｉｓｔｒｉｂｕｔｉｏｎ）がある。ループ分割とは、ループ制御変数を除くループ内変数の定義（変数に値を代入すること）・使用（変数の値を使用すること）の順序関係を保ったまま、１つのループのループボディを複数のループボディに分割して、複数のループを作成する方法である。
これにより、元のループでは不可能だった並列化やベクトル化などの最適化が一部の分割ループでは可能になり、ループ実行性能が向上する場合がある。
最初に、本明細書で用いる用語を説明する。変数の定義・使用の順序関係を依存、定義と使用をまとめて参照と呼ぶ。また、ループの繰り返しに跨った依存
（ある繰り返しで変数を参照し、次回以降の繰り返しで同じ変数を参照する依存）をループ運搬依存、跨らない依存をループ独立依存、定義の後に使用が来る依存をフロー依存、使用の後に定義が来る依存を逆依存、定義の後に定義が来る依存を出力依存と呼ぶ。ループの繰り返しに跨って存在するフロー依存をループ運搬フロー依存、ループの繰り返しに跨らずに存在するフロー依存をループ独立フロー依存、ループの繰り返しに跨らずに存在する逆依存をループ独立逆依存、ループの繰り返しに跨らずに存在する出力依存をループ独立出力依存と呼ぶ。特定の依存関係を持つ変数を含む文をその依存関係がある文、文  Ａ  で参照された変数が文Ｂで参照される場合の依存関係を文  Ａ  から文  Ｂ  への依存、特定の依存関係がある文を含むループをその依存関係があるループと呼ぶ。また、依存サイクルとは、文間の依存関係を文  Ａ  から文  Ｂ、文  Ｂ  から文  Ｃ  とたどっていくと、最終的に出発点の文  Ａ  に戻ってくる場合の依存のことを指す。
【０００３】
まず、ループ分割方法について述べる。ループ分割は、１つの依存サイクルに含まれる文を同じ分割ループに割り当てるよう、元のループを分割する。依存サイクルがある文とない文を別々の分割ループに割り当てることにより、各々の依存関係に応じた最適化を、別々に各分割ループに適用することができる。
次に、ループ中に手続き呼び出し文がある場合のループ分割方法について述べる。手続きに跨って依存関係を調べる手続き間依存解析を行なうと、呼び出し元手続きと呼び出し先手続きの間の依存関係がわかる。ループ中で、呼び出し元手続きと呼び出し先手続きの間に依存サイクルがあった場合、手続き呼び出し文は依存サイクルに含まれると解釈して、前記のループ分割を行なう方法もある。
しかし、この方法は呼び出し先手続きにある依存サイクルに含まれない文も依存サイクルに含まれると拡大解釈してしまう。このような拡大解釈を行なわない方法として、ループ分割の前処理としてインライン展開を行なう方法がある。インライン展開とは、手続き呼び出し文を手続き本体に置き換える処理である。これにより拡大解釈せずに文毎に依存を評価できるようになり、また呼び出し先手続きの文を別々の分割ループに割り当てることが可能になる。
【０００４】
例としてループ  １  を考える。  Ｓ１  〜  Ｓ４，ＳＣ  は文番号である。
0003551352.tif 000002
ループ  １  内に現れる文には、次のような依存関係がある。
−依存関係  （ａ）  文  Ｓ１  から文  Ｓ２  へ、配列  Ａ  に関するループ独立フロー依存
−依存関係  （ｂ）  文  Ｓ２  から文  Ｓ１  へ、配列  Ｂ  に関するループ運搬フロー依存
−依存関係  （ｃ）  文  Ｓ２  から文  Ｓ４  へ、配列  Ｂ  に関するループ独立フロー依存
−依存関係  （ｄ）  文  Ｓ３  から文  Ｓ４  へ、配列  Ｄ  に関するループ独立逆依存
依存関係  （ａ），（ｂ）から、ループ  １  では文  Ｓ１，Ｓ２  が依存サイクルを構成していることがわかる。
【０００５】
一時変数は、手続き呼び出しの実引数と仮引数の対応関係や、呼び出し元手続きと呼び出し先手続きに同名の別変数がある場合、仮引数やローカル変数に別名関係（複数の変数が同じメモリアドレスを指していること）がある場合の変数間の対応関係を保証するために必要である。実引数と仮引数との間の対応を、一時変数を用いてではなくレジスタ渡しで行なう方法もある。しかし、引数の数が多ければレジスタが足りなくなり、一時変数を使わなければならない。更に、実引数と仮引数の間で配列形状が異なった場合、例えば、実引数で２次元配列だが仮引数では１次元配列として受け取るような場合には、レジスタ渡しは適用できず、一時変数を用いた計算が必要となる。
手続き  ｓｕｂ１  を手続き呼び出し文  Ｓｃ  に関してインライン展開すると、下記
のループ  １ａ  が生成される。  ｔｍｐＡ，ｔｍｐＢ，ｔｍｐＣ  はインライン展開のためにコンパイラが生成した一時変数である。また、文  Ｓ２，Ｓ３  は一時変数を用いた文  Ｓ２’，Ｓ３’に変換された。  Ｓ１，Ｓ４，Ｓ２’，Ｓ３’，ＳＴ１  〜  ＳＴ６  は文番号である。
【０００６】
0003551352.tif 000003
このループ  １ａ  に現れる依存関係は以下の通りである。
−依存関係（１）  文  Ｓ１  から文  ＳＴ１  へ、  配列  Ａ  に関するループ独立フロー依存
−依存関係（２）  文  ＳＴ１  から文  ＳＴ５  へ、配列  Ａ  に関するループ独立逆依存
−依存関係（３）  文  Ｓ１  から文  ＳＴ５  へ、  配列  Ａ  に関するループ独立出力依存
−依存関係（４）文ＳＴ１から文Ｓ２’へ、配列  ｔｍｐＡ  に関するループ独立フロー依存
−依存関係（５）文ＳＴ１から文ＳＴ５へ、配列  ｔｍｐＡ  に関するループ独立フロー依存
−依存関係（６）文ＳＴ２から文ＳＴ６へ、配列  Ｂ  に関するループ独立逆依存
−依存関係（７）文ＳＴ６から文Ｓ１へ、配列  Ｂ  に関するループ運搬フロー依存
−依存関係（８）文ＳＴ６から文Ｓ４へ、配列  Ｂ  に関するループ独立フロー依存
−依存関係（９）文ＳＴ２から文Ｓ２’へ、配列  ｔｍｐＢ  に関するループ独立出力依存
−依存関係（１０）文Ｓ２’から文ＳＴ６へ、配列  ｔｍｐＢ  に関するループ独立フロー依存
−依存関係（１１）文ＳＴ３から文ＳＴ７へ、配列  Ｃ  に関するループ独立逆依存
−依存関係（１２）文ＳＴ３から文Ｓ３’へ、配列  ｔｍｐＣ  に関するループ独立出力依存
−依存関係（１３）文Ｓ３’から文ＳＴ７へ、配列  ｔｍｐＣ  に関するループ独立フロー依存
−依存関係（１４）文ＳＴ４から文ＳＴ８へ、配列  Ｄ  に関するループ独立逆依存
−依存関係（１５）文ＳＴ８から文Ｓ４へ、配列  Ｄ  に関するループ独立出力依存
−依存関係（１６）文ＳＴ４から文Ｓ３’へ、配列  ｔｍｐＤ  に関するループ独立フロー依存
−依存関係（１７）文ＳＴ４から文ＳＴ８へ、配列  ｔｍｐＤ  に関するループ独立フロー依存
【０００７】
依存関係  （１），（４），（７），（１０）  により、ループ  １ａ  では文  Ｓ１，ＳＴ１，Ｓ２’，ＳＴ６  が依存サイクルを構成していることがわかる。次に、依存関係を保ったまま、依存サイクルを持つ文と持たない文をできるだけまとまめるように、ループボディ中の文の順番を入れ換ると、次のようなループ  １ａ’  になる。
0003551352.tif 000004
【０００８】
更に、ループ  １ａ’  にループ分割を適用すると、次のようなループ  １ａａ，１ａｂが生成される。
0003551352.tif 000005
【０００９】
このループ分割の結果、文  Ｓ１，Ｓ２’  を分割ループ  １ａａ  に、文  Ｓ４，  文  Ｓ３’  を分割ループ  １ａｂ  に割り当てることになった。
更に、分割後のループを最適化することを考える。分割前のループがある依存を持つために最適化できなかった場合でも、分割後のループの中にはその依存をもたないものがありうるので、その依存を持たないループに対して最適化を適用することができる。例えば、最適化として並列化やベクトル化を例に挙げる。ループが並列化できる条件はループ中にループ運搬フロー依存がないことであり、ループがベクトル化できる条件はループ中に依存サイクルがないことである。
分割前のループ１はどちらの条件も満たさないため、並列化もベクトル化もできなかった。
しかし、分割後のループ  １ａｂ  はループ運搬フロー依存も依存サイクルも持たないので、並列化もベクトル化も可能である。
このようなループ分割やインライン展開は公知技術であり、例えば
Ｍｉｃｈａｅｌ  Ｗｏｌｆｅ（１９９６）  ”Ｈｉｇｈ  Ｐｅｒｆｏｒｍａｎｃｅ  Ｃｏｍｐｉｌｅｒｓ  ｆｏｒ  Ｐａｒａｌｌｅｌ  Ｃｏｍｐｕｔｉｎｇ”，Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏｍｐａｎｙ，  ｐｐ．３２３−ｐｐ．３３０、  ｐｐ．３６０−ｐｐ．３６１  で述べられている。
【００１０】
【発明が解決しようとする課題】
上記従来技術は、そのインライン展開において、多数の一時変数を必要とする。
そのため、ループ分割して一部の分割ループに最適化を適用しても、一時変数の計算に時間がかかって性能がでないという問題点があった。
例えば、従来技術において、ループ  １  で手続き  ｓｕｂ１  をインライン展開したループ  １ａ  では、一時変数  ｔｍｐＡ，ｔｍｐＢ，ｔｍｐＣ  を用いた  ＳＴ１  〜  ＳＴ８という新たな８文が生成された。インライン展開前にはループ中には  ＳＴ１  〜  ＳＴ４  の  ４  文しかなかったが、インライン展開後には  １２  文となり、文数が  ３  倍になった。手続き呼び出しにかかる時間とループ制御にかかる時間を無視できると仮定すると、ループの実行時間は、
0003551352.tif 000006
となる。  Ｔｓｔｍｔａｖは  １文の平均実行時間、Ｎはループ繰り返し回数である。
【００１１】
仮に、並列化やベクトル化等の最適化でループ  １ａｂ  の実行時間がループ  １ａａの実行時間に比べて非常に短くなり、
0003551352.tif 000007
とみなせるようになったとしても、ループ１ａａ＋ループ１ａｂの実行時間はループ  １の実行時間の５／４倍ある。この例の場合は、ループ分割して最適化を行なったならば、逆に性能が悪化してしまった。
本発明の目的は、上記問題を解決し、最適化を促進するために、手続き呼び出しを含むループを、前処理としてインライン展開を行なわずにループ分割し、ループ中から呼び出される呼び出し先手続き内の文のうち、最適化可能文を最適化可能ループに、最適化不能文を最適化不能ループに割り当てることを可能とするループ分割方法を提供することにある。
本発明の他の目的は、ループの実行時間を短縮するプログラムまたはオブジェクトコードを出力することが可能なループ分割方法を提供することにある。
【００１２】
【課題を解決するための手段】
上記課題を解決するため、本発明のループ分割方法は、
（ａ）該ループに関して手続き間依存解析を行なう処理と、
（ｂ）該ループを、複数の最適化可能分割ループと複数の最適化不能分割ループに分割する処理と、
（ｃ）該最適化不能分割ループ中の文を調べて最適化可能な最適化可能文を検出する処理と、
（ｄ）以下の３種の手続き（ｄ．１）該最適化不能分割ループから直接呼び出される直接呼び出し手続き、（ｄ．２）該最適化可能文を持つ最適化可能手続き、（ｄ．３）該コールグラフ上で該直接呼び出し手続きからエッジをたどって該最適化可能手続きに至る間に現れる手続きである中間手続き、をコピー対象手続きとする処理と、
（ｅ）該最適化不能分割ループ中の該最適化可能文に、該最適化不能文から該最適化可能文への依存を持たない前方最適化可能文がある場合は、（ｅ．１）該直接呼び出し手続き、該最適化可能手続き、該中間手続きをコピーした、前方直接呼び出しコピー手続  き、前方最適化可能コピー手続き、前方中間コピー手続きを作成し、（ｅ．２）  該最適化不能分割ループの直前にある該最適化可能分割ループの最後に、該前方直接呼び出しコピー手続きの手続き呼び出し文を挿入し、（ｅ．３）該前方直接呼び出しコピー手続きを調べ、手続き呼び出し文があれば呼び出し先手続きを再帰的に調べ、該コピー対象手続きの手続き呼び出し文があれば該前方中間コピー手続きまたは該前方最適化可能コピー手続きの手続き呼び出し文に変更し、（ｅ．４）該前方最適化可能文以外かつ該手続き呼び出し文以外の文を、該前方直接呼び出しコピー手続き、該前方最適化可能コピー手続き、該前方中間コピー手続きから削除する処理と、
【００１３】
（ｆ）該最適化不能分割ループ中の該最適化可能文に、該最適化可能文から該最適化不能文への依存を持たない後方最適化可能文がある場合は、（ｆ．１）  該直接呼び出し手続き、該最適化可能手続き、該中間手続きをコピーした、後方直接呼び出しコピー手続き、後方最適化可能コピー手続き、後方中間コピー手続きを作成し、（ｆ．２）  該最適化不能分割ループの直後にある該最適化可能分割ループの先頭に、該後方直接呼び出しコピー手続きの手続き呼び出し文を挿入し、（ｆ．３）該後方直接呼び出しコピー手続きを調べ、手続き呼び出し文があれば呼び出し先手続きを再帰的に調べ、該コピー対象手続きの手続き呼び出し文があれば該後方中間コピー手続きまたは該後方最適化可能コピー手続きの手続き呼び出し文に変更し、（ｆ．４）  該後方最適化可能文以外かつ該手続き呼び出し文以外の文を、該後方直接呼び出しコピー手続き、該後方最適化可能コピー手続き、該後方中間コピー手続きから削除する処理と、
（ｇ）  （ｇ．１）該直接呼び出し手続き、該最適化可能手続き、該中間手続きをコピーした、オリジナル直接呼び出しコピー手続き、オリジナル最適化可能コピー手続き、オリジナル中間コピー手続きを作成し、（ｇ．２）該最適化不能分割ループ中の該直接呼び出し手続きの手続き呼び出し文を該オリジナル直接呼び出しコピー手続きの手続き呼び出し文に置換し、（ｇ．３）該オリジナル直接呼び出しコピー手続きを調べ、手続き呼び出し文があれば呼び出し先手続きを再帰的に調べ、該コピー対象手続きの手続き呼び出し文があれば該オリジナル中間コピー手続きまたは該オリジナル最適化可能コピー手続きの手続き呼び出し文に置換し、（ｇ．４）該最適化可能文を、該オリジナル直接呼び出しコピー手続き、該オリジナル最適化可能コピー手続き、該オリジナル中間コピー手続きから削除する手段と、（ｈ）該最適化可能分割ループを最適化する処理、とを有することを特徴とする。
【００１４】
【発明の実施の形態】
以下、本発明の実施例を、図面により詳細に説明する。
まず、本発明の実施例について説明する前に、本発明が適用される逐次処理計算機の構成を説明する。
図１３は、本発明の適用対象である逐次処理計算機の構成の一例を示す図である。
この逐次処理計算機５０は、プロセッサ５１、メモリ５３、プロセッサ５１とメモリ５３を結合するバス５２とから構成される。
この逐次処理計算機５０は、図１に示すような最適化コンパイラの各ステップおよび入力プログラムをメモリ５３に格納しておき、これをプロセッサ５１が順次読み出して実行する。処理中に出力された中間データも、メモリ５３に格納される。
図１は、本発明のループ分割方法を実行するコンパイラの構成を示す図である。
図１に示すように、コンパイラ１０  は、構文解析部  １１、ループ分割部  １３、最適化部  １５、コード生成部１７から構成される。ここで、ループ分割部１３が、本発明で新規に設置された処理手順であって、その他の部分は従来から設置されたものをそのまま利用できる。
構文解析部  １１  は、入力プログラム  ９０  を読み込んで中間語  ９１  を生成する。中間語  ９１  はコンパイラ内部のプログラムの表現であり、その形式は通常のコンパイラの場合と特に変わらないので、ここでは詳細には述べない。
ループ分割部  １３  は、構文解析部  １１  の結果を利用して本発明のループ分割方法が適用可能なループを検出し、本ループ分割方法を適用してループ構造を変換する。ループ分割部  １３  は、依存解析部  １３１、ループ分割解析変換部  １３２、文解析部  １３３、手続きコピー解析部  １３４、手続きコピー変換部  １３５、文変換部  １３６から構成される。依存解析部  １３１  の実行方法は、通常のコンパイラが手続きにまたがって依存解析を行なう手続き間依存解析の場合と特に変わらないので、ここでは詳細には述べない。ステップ１３２〜１３６の説明は後述する。
【００１５】
図２は、図１におけるループ分割解析変換部１３２の実行方法を表したフローチャートである。
本変換部１３２  の実行方法は、ステップ  １３２０１  〜  １３２１０  から構成される。
ステップ  １３２０１  では、依存解析部１３１の手続き間依存解析結果を用いて、ループ中から依存サイクルに含まれる文を見つける。
ステップ  １３２０２  では、依存サイクルに含まれる文は依存サイクルに含まれる文同志で連続して並ぶように、また依存サイクルに含まれない文は依存サイクルに含まれない文同志で連続して並ぶように、依存関係を壊さない範囲でループ中の文の位置を移動して、それぞれをまとめる。
ステップ  １３２０３  では、ループ中の文を先頭から出現順にたどり、ステップ
１３２０４  で文が依存サイクル中に含まれるかを判定する。このとき、手続き呼び出し文があっても呼出先手続きの文はたどらない。もし文が依存サイクル中に含まれれば、ステップ  １３２０７  を実行する。もし文が依存サイクル中に含まれていなければ、ステップ  １３２０６  で次の  文が依存サイクル中に含まれているかどうか判定する。もし含まれていれば、ステップ  １３２０５  で、文の直後でループを分割するようにループ分割点を設置する。もし含まれていなければ、ステップ  １３２０７  を実行する。
【００１６】
ステップ  １３２０７  で、ループ中の最終文であると判定されたならば、ステップ１３２０５  で設置した分割点を用いて、ス  テップ  １３２０８  でループ分割を行なう。最終文でなければ、ステップ  １３２０３  に戻って、次の文に関して処理を続行する。ステップ  １３２０９  では、ステップ  １３２０８  で生成した分割ループが最適化が可能な最適化可能ループか、不可能な最適化不能ループかを判定する。分割ループを並列化する場合は、分割ループ中にループ運搬フロー依存が含まれていなければ最適化可能ループ、含まれていれば最適化不能ループと判定する。分割ループをベクトル化する場合は、分割ループ中に依存サイクルが含まれていなければ最適化可能ループ、含まれていれば最適化不能ループと判定する。
ステップ  １３２１０  では、分割点の前後の分割ループを調べ、前後の分割ループとも最適化可能ループ同志または最適化不能ループ同志である場合には、その分割点でのループ分割をやめ、元に戻す。
以上で、図２を用いたループ分割解析変換部  １３２  の説明を終る。
【００１７】
図３は、図１における文解析部  １３３  の実行方法を表したフローチャートである。
文解析部１３３の実行方法は、ステップ  １３３０１  〜  １３３０８  から構成される。
ステップ  １３３０１  では、ループが最適化不能分割ループであるかを判定する。ループが最適化不能分割ループであった場合は、ステップ  １３３０２  で、最適化不能分割ループ内の文を、手続き呼び出し文があれば呼び出し先手続き内の文も再帰的にたどる。ループが最適化不能分割ループでなかった場合には、ステップ１３３０８  でループ中の文を最適化可能文とする。ループ中の手続き呼び出し文から呼び出される呼び出し先手続き内の文は、この手続き呼び出し文に関して最適化可能文とする。
ステップ  １３３０３  では、文が手続き呼び出し文であるか否かを判定する。文が手続き呼び出し文であった場合は、ステップ  １３３０２  へ戻って次の文に関して処理を続行する。文が手続き呼び出し文でなかった場合は、ステップ  １３３０４  を実  行する。
ステップ  １３３０４  では、文が最適化可能か否かを判定する。最適化として並列化を行なう場合の最適化可能な文の条件は、文がループ運搬フロー依存を持たないことである。最適化としてベクトル化を行なう場合の最適化可能な文の条件は、文が依存サイクルに含まれないことである。最適化可能であれば、ステップ  １３３０５  でその文を最適化可能文とし、最適化可能でなければ、ステップ  １３３０６  でその文を最適化不能文とする。
ステップ  １３３０７  では、文が分割ループ中の最終文かどうか判定する。最終文であれば処理を終了し、最終文でなければ、ステップ  １３３０２  へ戻って次の文に関して処理を続行する。
以上で、図３を用いた文解析部  １３３  の説明を終る。
【００１８】
図４は、図１における手続きコピー解析部  １３４  の実行方法を表したフローチャートである。
手続きコピー解析部１３４の実行方法は、ステップ１３４００〜１３４１２から構成される。
ステップ  １３４００  では、コールグラフを作成する。コールグラフとは、手続きをノードとし、呼び出し元手続きから呼出先手続きへエッジをつないで、手続き呼びだし関係を表した木状グラフのことである。コールグラフの作成方法は、通常のコンパイラがコールグラフを作成する場合と特に変わらないので、ここでは詳細には述べない。
ステップ  １３４０１  では、最適化不能分割ループ内の文を、手続き呼び出し文があれば呼び出し先手続き内の文も再帰的にたどり、ステップ  １３４０２  で今たどっている文である自文が最適化可能文かどうか判定する。もし自文が最適化可能文であれば、ステップ  １３４００  で作成したコールグラフを利用して直接呼び出し手続き、最適化可能手続き、中間手続きを見つけ、それらをコピー対象手続きとし、ステップ  １３４０４  を実行する。もし自文が最適化可能文でなければ、ステップ  １３４１２  を実行する。
ステップ  １３４０４  では、自文と最適化不能分割ループ内の最適化不能文との間に依存関係があるか否かを判定する。もし、依存関係があれば、ステップ  １３４０６を実行する。もし依存関係がなければ、ステップ  １３４０５  を実行する。
【００１９】
ステップ  １３４０５  では、最適化不能分割ループ直前の分割ループと直後の分割ループとの粒度を比較する。なお、粒度とは、ここではループボディの実行コストであると定義する。具体的には、ループボディ中の文の数または命令の数で比較する。
直前の分割ループの粒度の方が小さかった場合は、ステップ１３４０７を実行する。そうでない場合は、ステップ  １３４０８  を実行する。
ステップ  １３４０６  では、自文と最適化不能文との間に存在する依存が、自文から最適化不能文への依存のみかどうか判定する。もし、自文から最適化不能文への依存のみであった場合は、ステップ  １３４０８  を実行する。もし、自文から最適化不能文への依存のみではなかった場合は、ステップ  １３４０９  を実行する。
ステップ  １３４０７  では、直接呼び出しコピー手続きの手続き呼び出し文の挿入位置を、直後の分割ループの先頭とする。
ステップ  １３４０８  では、直接呼び出しコピー手続きの手続き呼び出し文の挿入位置を、直前の分割ループの最後とする。
ステップ  １３４０９  では、自文と最適化不能文との間に存在する依存が、最適化不能文から自文への依存のみかどうかを判定する。もし、最適化不能文から自文への依存のみであった場合は、ステップ  １３４０７  を実行する。もし、最適化不能文から自文への依存のみではなかった場合は、ステップ  １３４１０  を実行する。
ステップ  １３４１０  では、自文を最適化不能文と再設定する。
ステップ  １３４１１  では、最適化不能分割ループ中およびコピー対象手続き中からコピー対象手続きを呼び出す手続き呼び出し文を、コピーした手続きであるコピー手続きの手続き呼び出し文への置換位置とする。
ステップ  １３４１２  では、自文が最適化不能分割ループの最終文であると判定する。もし、最終文であれば処理を終了し、最終文でなければ、ステップ  １３４０１  へ戻って次の文に関して処理を続行する。
以上で、図４を用いたコピー手続き解析部  １３４  の説明を終る。
【００２０】
図５は、図１における手続きコピー変換部  １３５  の実行方法を表したフローチャートである。
手続きコピー変換部１３５の実行方法は、ステップ  １３５０１  〜  １３５０６  から構成される。
ステップ  １３５０１  では、最適化不能分割ループ内の文を、手続き呼び出し文があれば呼び出し先手続き内の文も再  帰的にたどり、ステップ  １３５０２  で今たどっている文が手続き呼び出し文かどうかを判定する。もし、手続き呼び出し文であれば、ステップ  １３５０３  を実行する。手続き呼び出し文でなければ、ステップ  １３５０１  に戻り、次の文に関して処理を続行する。
ステップ  １３５０３  では、呼び出し先手続きがコピー対象手続きかどうか判定する。もしコピー対象手続きならば、ステップ  １３５０４  を実行する。コピー対象手続きでなければ、ステップ  １３５０１  に戻り、次の文に関して処理を続行する。
ステップ  １３５０４  では、コピー対象手続きをコピーして、コピー手続きを作成する。作成するコピー手続きの数は、コピー手続きの手続き呼び出し文を挿入または置換する数と同一である。
ステップ  １３５０５  では、文が最適化不能分割ループの最終文であるか判定する。
もし最終文であれば、ステップ  １３５０６  を実行する。最終文でなければ、ステップ  １３５０１  に戻り、次の文に関して処理を続行する。
ステップ  １３５０６  では、コピー手続きの手続き呼び出し文の全ての挿入位置および置換位置に、コピー手続きの手続き呼び出し文を挿入または置換する。
以上で、図５を用いた手続きコピー変換部１３５の説明を終る。
【００２１】
図６は、文変換部  １３６  の実行方法を表したフローチャートである。
文変換部１３６の実行方法は、ステップ  １３６０１  〜  １３６０９  から構成される。
ステップ  １３６０１  では、分割ループ内の文を、手続き呼び出し文があれば呼び出し先手続き内の文も再帰的にたどり、ステップ  １３６０２  で今たどっている文が最適化可能文かどうか判定する。もし最適化可能文ならば、ステップ  １３６０３  を実行する。最適化可能文でなければ、ステップ  １３６０４  を実行する。
ステップ  １３６０３  では、分割ループが最適化可能分割ループかどうか判定する。
もし最適化可能分割ループならば、  ステップ  １３６０７  を実行する。最適化可能分割ループでなければ、ステップ  １３６０５  を実行する。
ステップ  １３６０４  では、分割ループが最適化可能分割ループかどうかを判定する。もし、最適化可能分割ループならばステップ  １３６０５  を実行する。最適化可能分割ループでなければ、ステップ  １３６０７  を実行する。
ステップ  １３６０５  では、文が手続き呼び出し文かどうかを判定する。もし手続き呼び出し文ならば、ステップ  １３６０７  を  実行する。手続き呼び出し文でなければステップ  １３６０６  を実行する。
ステップ  １３６０６  では、文を削除し、ステップ  １３６０１  に戻って削除した文の次の文に関して処理を続行する。
ステップ  １３６０７  では、文が分割ループ中の最終文であるか否かを判定する。もし、最終文であれば、ステップ  １３６０８  を実行する。最終文でなければ、ステップ  １３６０１  に戻って次の文に関して処理を続行する。
ステップ  １３６０８  では、コピー手続き内で参照されていない変数を、手続きの引数から削除する。
ステップ  １３６０９  では、実行文を含まないコピー手続きとその手続き呼び出し文を削除する。
以上で、図６を用いたコピー手続き解析部  １３６  の説明を終る。
これで、ループ分割部  １３  の説明を終る。
【００２２】
最適化部  １５  は、ループ分割部  １３  の結果を利用してプログラムに対して並列化やベクトル化等の最適化変換を行なう。その構成は、通常の最適化コンパイラの場合と特に変わらないので、ここでは詳細には述べない。
コード生成部  １７  は、中間語  ９１  を読み込んで出力プログラム  ９２  を生成する。これらの処理の内容は通常のコンパ  イラの場合と特に変わらないので、ここでは詳細には述べない。
以上で、本発明によるループ分割方法の説明を終る。
【００２３】
図７の入力プログラム  ９０  は、コンパイラ  １０  のループ分割部  １３  への中間語９１  の入力のソースイメージの一例であり、  図８のプログラム  ９３  は、コンパイラ１０  のループ分割解析変換部  １３２  の中間語  ９１  への出力のソースイメージの一例であり、図９のプログラム  ９４  は、コンパイラ  １０  の手続きコピー変換部  １３５  の中間語  ９１  への出力のソースイメージの一例であり、  図１０  のプログラム  ９５  は、コンパイラ１０  の文変換部  １３６  の中間語  ９１  への出力のソースイメージの一例であり、図１１のプログラム  ９６  は、コンパイラ  １０  が最適化として並列化を行なった場合の、最適化部  １５  からの中間語  ９１  への出力の  ソースイメージの一例であり、図１２のプログラム  ９７  は、コンパイラ  １０  が最適化としてベクトル化をおこなった場合の、  最適化部  １５  からの中間語  ９１  への出力のソースイメージの一例である。プログラム  ９０、  ９２  〜  ９７  を用いて、コンパ  イラ１０  によるループ分割の一例を説明する。
【００２４】
図７の入力プログラム  ９０  で、図の左端にある番号は、理解を助けるために打った行番号である。図の  １  行目は、  整数型の変数  ｉ，  Ｎ  の宣言文、図の  ２  行目は、整数型の変数  Ｎ  の初期化文、図の  ３  行目は、実数型であり  １  〜  Ｎ  のサイズを持つ  １  次元配列  Ａ，Ｂ，Ｃ，Ｄ  と、実数型の変数  Ｘ  の宣言文、図の  ４  〜  ８行目が入力プログラム  ９０  の主処理部、  図の  １０  行目は、主処理部の  ６  行目から呼び出される手続き  ｓｕｂ１  の手続き文、図の  １１  行目は、整数型の変数  ｉ，  Ｎ  の宣言文、図の  １２  行目は、整数型の変数  Ｎ  の初期化文、図の  １３  行目は、実数型であり  １  〜  Ｎ  のサイズを持つ  １  次元  配列  Ａ，Ｂ，Ｃ，Ｄ  の宣言文、図の  １４  〜  １７  行目が入力プログラム  ９０  の手続き  ｓｕｂ１  処理部である。
【００２５】
図８のループ分割解析変換部  １３２  の出力プログラム  ９３  で、図の左端にある番号は、理解を助けるために打った行番号  である。図の  １  行目は、整数型の変数ｉ，  Ｎ  の宣言文、図の  ２  行目は、整数型の変数  Ｎ  の初期化文、図の  ３  行目は、実数型であり  １  〜  Ｎ  のサイズを持つ  １  次元配列  Ａ，Ｂ，Ｃ，Ｄ  と、実数型の変数Ｘの宣言文、図の  ４  〜  １０  行目が出力プ  ログラム  ９３  の主処理部（４〜７行が最適化不能の処理、８〜１０行が最適化可能の処理）、図の  １２  行目は、主処理部の  ６行目から呼び出される手続き  ｓｕｂ１  の手続き文、図の  １３  行  目は、整数型の変数  ｉ，  Ｎ  の宣言文、図の  １４  行目は、整数型の変数  Ｎ  の初期化文、図の  １５  行目は、実数型であり  １  〜  Ｎ  のサイズを持つ  １  次元配列  Ａ，Ｂ，Ｃ，Ｄ  の宣言文、図の  １６  〜  １９  行目が出力プログラム  ９３  の手続き  ｓｕｂ１  処理部である。
【００２６】
図９の手続きコピー変換部  １３５  の出力プログラム  ９４  で、図の左端にある番号は、理解を助けるために打った行番号である。図の  １  行目は、整数型の変数  ｉ，  Ｎ  の宣言文、図の  ２  行目は、整数型の変数  Ｎ  の初期化文、図の  ３  行目  は実数型であり  １  〜  Ｎ  のサイズを持つ  １  次元配列  Ａ，Ｂ，Ｃ，Ｄ  と、実数型の変数  Ｘの宣言文、図の  ４  〜  １１  行目が出  力プログラム  ９４  の主処理部（４〜７行が最適不可能部分、８〜１１行が最適可能部分）、図の  １３  行目は、主処理部の  ６  行目から呼び出されるコピー手続き＿ｃｏｐｙ１＿ｓｕｂ１  の手続  き文、図の  １４  行目は、整数型の変数  ｉ，  Ｎ  の宣言文、図の  １５  行目は、整数型の変数  Ｎ  の初期化文、図の  １６  行目は、  実数型であり  １  〜  Ｎ  のサイズを持つ  １  次元配列  Ａ，Ｂ，Ｃ，Ｄ  の宣言文、図の  １７  〜  ２０  行目が出力プログラム  ９４  の手続  き＿ｃｏｐｙ１＿ｓｕｂ１  処理部である。図の  ２２  行目は、主処理部の  ９  行目から呼び出されるコピー手続き＿ｃｏｐｙ２＿ｓｕｂ１  の手  続き文、図の  ２３  行目は、整数型の変数  ｉ，  Ｎ  の宣言文、図の２４  行目は、整数型の変数  Ｎ  の初期化文、図の  ２５  行目  は、実数型であり  １  〜  Ｎ  のサイズを持つ  １  次元配列  Ａ，Ｂ，Ｃ，Ｄ  の宣言文、図の  ２６  〜  ２９  行目が出力プログラム  ９４  の  手続き＿ｃｏｐｙ２＿ｓｕｂ１  処理部である。
【００２７】
図１０の文変換部  １３６  の出力プログラム  ９５  で、図の左端にある番号は、理解を助けるために打った行番号である。  図の  １  行目は、整数型の変数  ｉ，  Ｎ  の宣言文、図の  ２  行目は、整数型の変数  Ｎ  の初期化文、図の  ３  行目は、実数型で  あり  １  〜  Ｎ  のサイズを持つ  １  次元配列  Ａ，Ｂ，Ｃ，Ｄ  と、実数型の変数  Ｘ  の宣言文、図の  ４  〜  １１  行目が出力プログラム  ９５  の主処理部（４〜７行が最適化不可能部分、８〜１１行が最適化可能部分）、図の  １３  行目は、主処理部の  ６  行目から呼び出されるコピー手続き＿ｃｏｐｙ１＿ｓｕｂ１  の手続き文、図の  １４  行目は、整数型の変数  ｉ，  Ｎ  の宣言文、図の  １５  行目は、整数型の変数  Ｎ  の初期化文、図の  １６  行目は、実数型であり  １  〜  Ｎ  のサイズを持つ  １  次元配列  Ａ，Ｂ  の宣言文、図の１７  〜  １９  行目が出力プログラム  ９５  の手続き＿ｃｏｐｙ１＿ｓｕｂ１  処理部（最適化不可能部分）である。図の  ２１  行目は、主処理部の  ９  行目から呼び出されるコピー手続き＿ｃｏｐｙ２＿ｓｕｂ１  の手続き文、図の  ２２  行目  は、整数型の変数  ｉ，  Ｎ  の宣言文、図の  ２３  行目は、整数型の変数  Ｎ  の初期化文、図の  ２４  行目は、実数型であり  １  〜  Ｎ  のサイズを持つ  １  次元配列  Ｃ，Ｄ  の宣言文、図の  ２５  〜  ２７  行目が出力プログラム  ９５  の手続き＿ｃｏｐｙ２＿ｓｕｂ１  処理部（最適化可能部分）である。
【００２８】
図１１の最適化部  １５  が並列化を行なった場合の出力プログラム  ９６  で、図の左端にある番号は、理解を助けるた  めに打った行番号である。図の  １  行目は、整数型の変数  ｉ，  Ｎ，  プロセッサ台数  Ｎｐｒｏｃ  の宣言文、図の  ２  行目は、整数型の変数  Ｎ  の初期化文、図の  ３  行目は、実数型であり  １  〜  Ｎ  のサイズを持つ  １次元配列  Ａ，Ｂ，Ｃ，Ｄ  と、実数型の変数  Ｘ  の宣言文、図の  ４  〜  １１  行目が出力プログラム  ９６  の主処理部（４〜７行が最適化不可部分、８〜１１行が最適化可能部分）、図の  １３  行目は、主処理部の  ６  行目から呼び出され  るコピー手続き＿ｃｏｐｙ１＿ｓｕｂ１  の手続き文、図の  １４  行目は、整数型の変数  ｉ，  Ｎ  の宣言文、図の  １５  行目は、整数型の変  数  Ｎ  の初期化文、図の  １６  行目は、実数型であり  １  〜  Ｎ  のサイズを持つ  １  次元配列  Ａ，Ｂ  の宣言文、図の  １７  〜  １９  行  目が出力プログラム  ９６  の手続き＿ｃｏｐｙ１＿ｓｕｂ１  処理部（最適化不可能部分）である。図の  ２１  行目は、主処理部の  ９  行目から呼び出されるコ  ピー手続き＿ｃｏｐｙ２＿ｓｕｂ１  の手続き文、図の  ２２  行目は、整数型の変数  ｉ，  Ｎ  の宣言文、図の  ２３  行目は、整数型の変数  Ｎの初期化文、図の  ２４  行目は、実数型であり  １  〜  Ｎ  のサイズを持つ  １  次元配列  Ｃ，Ｄ  の宣言文、図の  ２５  〜  ２７  行目  が出力プログラム  ９６  の手続き＿ｃｏｐｙ２＿ｓｕｂ１  処理部（最適化可能部分）である。
【００２９】
図１２の最適化部  １５  がベクトル化を行なった場合の出力プログラム  ９７  で、図の左端にある番号は、理解を助  けるために打った行番号である。図の  １  行目は、整数型の変数  ｉ，  Ｎ  の宣言文、図の  ２  行目は、整数型の変数  Ｎ  の初  期化文、図の  ３  行目は、実数型であり  １  〜  Ｎ  のサイズを持つ  １  次元配列  Ａ，Ｂ，Ｃ，Ｄと、実数型の変数  Ｘ  の宣言文、  図の  ４  〜  ９  行目が出力プログラム  ９７  の主処理部、図の  １１  行目は、主処理部の  ６  行目から呼び出されるコピー手続  き＿  ｃｏｐｙ１＿ｓｕｂ１  の手続き文、図の  １２  行目は、整数型の変数  ｉ，  Ｎ  の宣言文、図の  １３  行目は、整数型の変数  Ｎ  の初期  化文、図の  １４  行目は、実数型であり  １  〜Ｎ  のサイズを持つ  １  次元配列  Ａ，Ｂ  の宣言文、図の  １５  〜  １７  行目が出力プ  ログラム  ９６  の手続き＿ｃｏｐｙ１＿ｓｕｂ１  処理部である。
【００３０】
図７〜図１２で明らかなように、ループ分割部  １３  は、入力プログラム  ９０  を出力プログラム  ９５  に変換する。そのために、まず、ループ分割解析変換部  １３２が、入力プログラム  ９０  を出力プログラム  ９３  に変換する（図８参照）。入力プログラム  ９０  の  ４  〜  ８  行目のループが、出力プログラム  ９３  の  ４  〜  ７  行目、８  〜  １０  行目のループに分割された。前者のループが最適化不能分割ループ、後者のループが最適化可能分割ループである。
次に、手続きコピー変換部  １３５  が、出力プログラム  ９３  を出力プログラム９４  に変換する（図９参照）。出力プログラム  ９３  の  ６  行目の手続き呼び出し文が手続き  ｓｕｂ１  を呼び出していたのが、出力プログラム  ９４  の  ６  行目の手続き呼び出し文で  は、手続き  ｓｕｂ１  をコピーしたコピー手続き＿ｃｏｐｙ１＿ｓｕｂ１  を呼び出すようになった。また、出力プログラム  ９４  の  ９  行  目に、手続き  ｓｕｂ１  をコピーしたコピー手続き＿ｃｏｐｙ２＿ｓｕｂ１  を呼び出す手続き呼び出し文が追加された。
また、手続き本体も  ｓｕｂ１  から＿ｃｏｐｙ１＿ｓｕｂ１、＿ｃｏｐｙ２＿ｓｕｂ１  の本体に変更された。元の手続き  ｓｕｂ１  の本体はプログラム中から削除されてはいないが、手続きコピー変換部  １３５  によって手続き呼び出し文が削除されてしまったので、出力プログラ  ム  ９４  からは省略した。出力プログラム  ９５  〜  ９７  でも同様の理由で省略した。
【００３１】
次に、文変換部  １３６  が、出力プログラム  ９４  を出力プログラム  ９５  に変換する（図１０参照）。出力プログラム  ９４  の  １８  行目の代  入文が最適化可能文として、  ２６  行目の代入文が最適化不能文として、出力プログラム９５のそれぞれ４  〜  ７  行目の最適化不能分割ループ、  ８  〜  １０  行目の最適化可能分割ループで実行されないように削除された。
次に、最適化部  １５  は、並列化を行なう場合には、出力プログラム  ９５  を出力プログラム  ９６  に変換する（図１１参照）。出力プ  ログラム  ９５  の  ８  〜  １１  行目の最適化可能分割ループが、出力プログラム  ９６  の  ８  〜  １１  行目の並列ループに変換され  た。ループ範囲が  １  〜  Ｎ  より  １  〜  Ｎ＝Ｎｐｒｏｃ  に変更されている。
また、最適化部  １５  は、ベクトル化を行なう場合には、出力プログラム  ９５  を出力プログラム  ９７  に変換する（図１２参照）。出力  プログラム  ９５  の８  〜１１  行目の最適化可能分割ループが、コピー手続き＿ｃｏｐｙ２＿ｓｕｂ１  をインライン展開してからベク  トル化することで、出力プログラム  ９６  の  ８  〜  ９  行目の配列代入文に変換された。配列代入文は、ベクトル化可能なループと同一の意味を表す。以上で、プログラム  ９０、  ９２  〜  ９７  を用いたループ分割の一例の説明を終る。
【００３２】
もし、本ループ分割を実行しなければ、入力プログラム  ９０  の  ４  〜  ８  行目のループは、  ５  〜  ６  行目を実行する最適化不能分割ループと  ７  行目を実行する最適化可能分割ループにしかループ分割できず、  ７  行目の文しか並列化やベクトル化ができない。
しかし、本発明のループ分割によって、呼び出し先手続き  ｓｕｂ１  内の  １４，１５  行目の文も別々の分割ループに割り当てることができ、その結果、  ７  行目の文に加えて  １５  行目の文も最適化可能分割ループに割り当てることができた。その結果、並列化やベクトル化可能な文の数が  １  文から  ２  文に増えた。また、一時変数を使用していないので、余分な文の実行をせずに済み、プログラムの実行がより高速化できる。
【００３３】
【発明の効果】
以上説明したように、本発明によれば、手続き呼び出し先の文も呼び出し元ループにおけるループ分割後の最適化対象となるので、より実行性能の良いプログラムまたはオブジェクトコードが得られる。また、一時変数を導入することなくループ分割が可能になるので、分割前のループに対して実行性能を劣化させることがない。
【図面の簡単な説明】
【図１】本発明の一実施例を示すループ分割方法を実行するコンパイラの構成図である。
【図２】図１におけるループ分割解析変換部の処理フローチャートである。
【図３】図１における文解析部の処理フローチャートである。
【図４】図１における手続きコピー解析部の処理フローチャートである。
【図５】図１における手続きコピー変換部の処理フローチャートである。
【図６】図１における文変換部の処理フローチャートである。
【図７】本発明で使用される入力プログラムの一例図である。
【図８】本発明でループ分割されたプログラムの一例図である。
【図９】本発明により手続きコピー変換されたプログラムの一例図である。
【図１０】本発明により文変換されたプログラムの一例図である。
【図１１】本発明により並列化された出力プログラムの一例図である。
【図１２】本発明によりベクトル化された出力プログラムの一例図である。
【図１３】本発明が適用される逐次処理計算機の構成の一例を示す図である。
【符号の説明】
１０…本発明のコンパイラ、  １１  …構文解析部、  １３…ループ分割部、
１５…最適化部、  １７…コード生成部、５０…逐次処理計算機、５１…プロセッサ、
５２…バス、５３…メモリ、  ９０…入力プログラム、９１…中間語、
９３…ループ分割されたプログラム、９２…出力プログラム、
９４…手続きコピー変換されたプログラム、９５…文変換されたプログラム、
９６…並列化出力プログラム、９７…ベクトル化出力プログラム、
１３１…依存解析部、  １３２…ループ分割解析変換部、１３３…文解析部、
１３４…手続きコピー解析部、１３５…手続きコピー変換部、１３６…文変換部。
【図１】
0003551352.tif 000008
【図２】
0003551352.tif 000009
【図３】
0003551352.tif 000010
【図４】
0003551352.tif 000011
【図５】
0003551352.tif 000012
【図６】
0003551352.tif 000013
【図７】
0003551352.tif 000014
【図８】
0003551352.tif 000015
【図９】
0003551352.tif 000016
【図１０】
0003551352.tif 000017
【図１１】
0003551352.tif 000018
【図１２】
0003551352.tif 000019
【図１３】
0003551352.tif 000020