(57)【特許請求の範囲】
【請求項１】
１つ以上の命令文からなるブロックを繰り返しＮ回（Ｎ≧２）処理するループ処理であって、ｉ（１≦ｉ＜Ｎ）回目の実行に係る前記ブロック内の命令文で定義された変数が、ｊ（ｉ＜ｊ≦Ｎ）回目の実行に係る前記ブロック内の命令文で参照される依存関係にあるループ処理を含む対象ソースプログラムを参照することにより、新たなプログラムを生成するプログラム生成装置であって、
ｉ回目の実行に係る前記ブロックと、ｉ回目以外の実行に係る１以上の前記ブロックとを対象ブロックとして、当該対象ブロック内の命令文に基づいて、当該対象ブロックに含まれる等価な複数の変数表記を示す等価関係情報の生成を行う算出手段と、
前記算出手段が生成した等価関係情報に基づいて、前記変数のうち、前記依存関係にある全ての対象変数の表記について、当該対象変数の表記と等価な前記依存関係のない他の変数の表記を特定する特定処理を行う特定手段と、
前記ループ処理のＭ回分（Ｍ≦Ｎ）の処理を行うための、前記対象変数の表記に代えて、前記特定手段が特定した他の変数の表記を含んだ命令文を含み、前記依存関係が解消されたプログラムを生成する生成手段とを備える
ことを特徴とするプログラム生成装置。
【請求項２】
前記特定手段が特定する前記対象変数の表記と等価な前記依存関係のない他の変数の表記は、いずれの対象変数の表記とも異なる変数の表記である
ことを特徴とする請求項１記載のプログラム生成装置。
【請求項３】
前記算出手段は、
ｉ回目の実行に係る前記ブロックと、ｉ＋１回目の実行に係る前記ブロックとを前記対象ブロックとして前記等価関係情報の生成を行い、
前記特定手段は、
前記算出手段が前記等価関係情報の生成を行う毎に、生成済みの等価関係情報に基づいて、全ての対象変数の表記について、当該対象変数の表記と等価な前記依存関係のない他の変数の表記であって、いずれの対象変数の表記とも異なる変数の表記を特定できるか否かの判定を行い、
当該判定の結果が否定的である間、ｉを１ずつ増加させながら、前記算出手段に前記等価関係情報の生成を繰り返し行わせる
ことを特徴とする請求項２記載のプログラム生成装置。
【請求項４】
前記プログラム生成装置が参照するプログラムは、単一のプロセッサで実行するためのプログラムであり、
前記生成手段が生成するプログラムは、複数のプロセッサで並列実行するためのプログラムである
ことを特徴とする請求項２記載のプログラム生成装置。
【請求項５】
前記生成手段は、
Ｍ＜Ｎの場合に、生成したプログラムを前記ループ処理のＮ−Ｍ回分の処理をも行うように変更し、変更後のプログラムの処理と、前記対象ソースプログラムの処理とが、等価になるか否かを判定し、等価になる場合には、前記生成したプログラムを、当該変更後のプログラムに置き換える
ことを特徴とする請求項２記載のプログラム生成装置。
【請求項６】
１つ以上の命令文からなるブロックを繰り返しＮ回（Ｎ≧２）処理するループ処理であって、ｉ（１≦ｉ＜Ｎ）回目の実行に係る前記ブロック内の命令文で定義された変数が、ｊ（ｉ＜ｊ≦Ｎ）回目の実行に係る前記ブロック内の命令文で参照される依存関係にあるループ処理を含む対象ソースプログラムを参照することにより、新たなプログラムを生成するプログラム生成装置におけるプログラム生成方法であって、
前記プログラム生成装置は、算出手段と、特定手段と、生成手段とを備え、
前記プログラム生成方法は、
前記算出手段が、ｉ回目の実行に係る前記ブロックと、ｉ回目以外の実行に係る１以上の前記ブロックとを対象ブロックとして、当該対象ブロック内の命令文に基づいて、当該対象ブロックに含まれる等価な複数の変数表記を示す等価関係情報の生成を行う算出ステップと、
前記特定手段が、前記算出手段により前記算出ステップで生成された等価関係情報に基づいて、前記変数のうち、前記依存関係にある全ての対象変数の表記について、当該対象変数の表記と等価な前記依存関係のない他の変数の表記を特定する特定処理を行う特定ステップと、
前記生成手段が、前記ループ処理のＭ回分（Ｍ≦Ｎ）の処理を行うための、前記対象変数の表記に代えて、前記特定手段により前記特定ステップで特定された他の変数の表記を含んだ命令文を含み、前記依存関係が解消されたプログラムを生成する生成ステップとを含む
ことを特徴とするプログラム生成方法。
【請求項７】
１つ以上の命令文からなるブロックを繰り返しＮ回（Ｎ≧２）処理するループ処理であって、ｉ（１≦ｉ＜Ｎ）回目の実行に係る前記ブロック内の命令文で定義された変数が、ｊ（ｉ＜ｊ≦Ｎ）回目の実行に係る前記ブロック内の命令文で参照される依存関係にあるループ処理を含む対象ソースプログラムを参照することにより、新たなプログラムを生成するプログラム生成装置におけるプロセッサに、プログラム生成処理を行わせるためのプログラムであって、
前記プログラム生成処理は、
ｉ回目の実行に係る前記ブロックと、ｉ回目以外の実行に係る１以上の前記ブロックとを対象ブロックとして、当該対象ブロック内の命令文に基づいて、当該対象ブロックに含まれる等価な複数の変数表記を示す等価関係情報の生成を行う算出ステップと、
前記算出ステップで生成された等価関係情報に基づいて、前記変数のうち、前記依存関係にある全ての対象変数の表記について、当該対象変数の表記と等価な前記依存関係のない他の変数の表記を特定する特定処理を行う特定ステップと、
前記ループ処理のＭ回分（Ｍ≦Ｎ）の処理を行うための、前記対象変数の表記に代えて、前記特定ステップで特定された他の変数の表記を含んだ命令文を含み、前記依存関係が解消されたプログラムを生成する生成ステップとを含む
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ループ処理を含むソースプログラムを参照して、新たなプログラムを生成する技術に関する。
【背景技術】
【０００２】
ループ処理を含むソースプログラムを参照して、そのループ処理により実現される所定処理を複数のプロセッサにより分担して実行させるための新たなプログラムを生成するコンパイラ等が知られている（例えば、特許文献１）。【０００３】
ここで、ループ処理とは、１以上の命令文からなるブロックを繰り返しＮ（Ｎ≧２）回処理するものである。【０００４】
特許文献１の技術によれば、例えば、Ｎ回分のループ処理を、Ｎ／２回分ずつ処理する２個の部分ループ処理に分割し、２個のプロセッサで独立して並列実行させるよう構成した新たなプログラムを生成することができる。従って、特許文献１の技術によれば、Ｎ回のループ処理を高速に実行することができるようになる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】日本国特許第３０２８８２１号
【特許文献２】日本国特許第３２３４５５２号
【非特許文献】
【０００６】
【非特許文献１】Ｈａｎｓ  Ｚｉｍａ、他：“Ｓｕｐｅｒｃｏｍｐｉｌｅｒｓ  ｆｏｒ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｖｅｃｔｏｒ Ｃｏｍｐｕｔｅｒｓ”，Ａｄｄｉｓｏｎ  Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏｍｐａｎｙ  Ｉｎｃ．，１９９１、（邦訳）村岡洋一：“スーパーコンパイラ”，オーム社，１９９５
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、ソースプログラムに含まれるループ処理において、ｉ（１≦ｉ＜Ｎ）回目の実行に係るブロック内の命令文で定義された変数を、ｊ（ｉ＜ｊ≦Ｎ）回目の実行に係るブロック内の命令文で参照するような依存関係が存在する場合には、特許文献１の方法では対応できない。つまり、特許文献１の方法では、このような依存関係を有するループ処理を含むソースプログラムからは、複数のプロセッサを用いてループ処理を高速に実行するためのプログラムを生成することはできない。【０００８】
そこで、本発明は係る問題に鑑みてなされたものであり、上記依存関係を有するループ処理を含むソースプログラムを参照することにより、複数のプロセッサを用いてループ処理を高速に実行するためのプログラムの生成に有用なプログラム生成装置を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記課題を解決するために、本発明に係るプログラム生成装置は、１つ以上の命令文からなるブロックを繰り返しＮ回（Ｎ≧２）処理するループ処理であって、ｉ（１≦ｉ＜Ｎ）回目の実行に係る前記ブロック内の命令文で定義された変数が、ｊ（ｉ＜ｊ≦Ｎ）回目の実行に係る前記ブロック内の命令文で参照される依存関係にあるループ処理を含む対象ソースプログラムを参照することにより、新たなプログラムを生成するプログラム生成装置であって、ｉ回目の実行に係る前記ブロックと、ｉ回目以外の実行に係る１以上の前記ブロックとを対象ブロックとして、当該対象ブロックにおける変数表記の等価関係を算出する算出処理を行う算出手段と、前記算出手段が算出した変数表記の等価関係に基づいて、前記変数のうち、前記依存関係にある全ての対象変数の表記について、当該対象変数の表記と等価な前記依存関係のない他の変数の表記を特定する特定処理を行う特定手段と、前記ループ処理のＭ回分（Ｍ≦Ｎ）の処理を行うための、前記特定手段が特定した他の変数の表記を含んだ命令文を含むプログラムを生成する生成手段とを備えることを特徴とする。
【発明の効果】
【００１０】
上記構成を備える本発明に係るプログラム生成装置は、上記依存関係を有するループ処理を含むソースプログラムを参照することにより、複数のプロセッサを用いてループ処理を高速に実行するためのプログラムを生成し得る。
【図面の簡単な説明】
【００１１】
【図１】実施の形態に係るプログラム生成装置１００を含むコンパイラシステム１０００の構成を示すブロック図である。
【図２】ループ処理Ｒ１を含む部分プログラムＰ１及びループ処理Ｒ４を含む部分プログラムＰ４を示す図である。
【図３】データの依存関係を説明するための図である。
【図４】ループ処理Ｒ１におけるデータの依存関係を説明するための図である。
【図５】プログラム生成装置１００によるプログラム生成処理を示すフローチャートであり、図６へ続く。
【図６】プログラム生成装置１００によるプログラム生成処理を示すフローチャートであり、図５から続き、図７へ続く。
【図７】プログラム生成装置１００によるプログラム生成処理を示すフローチャートであり、図６から続く。
【図８】ループ処理Ｒ１におけるイタレーションｉ及びイタレーションｉ＋１を示す図である。
【図９】みせかけ依存を削除したイタレーションｉ及びイタレーションｉ＋１を示す図である。
【図１０】みせかけ依存を削除したイタレーションｉ及びイタレーションｉ＋１の各命令文についての変数表記の等価関係を算出した結果を示す図である。
【図１１】みせかけ依存を削除したイタレーションｉ＋２及びみせかけ依存を削除したイタレーションｉ＋２の各命令文についての変数表記の等価関係を算出した結果を示す図である。
【図１２】みせかけ依存を削除したイタレーションｉ＋３及びみせかけ依存を削除したイタレーションｉ＋３の各命令文についての変数表記の等価関係を算出した結果を示す図である。
【図１３】全ての真依存を削除したイタレーションｉ＋３及びイタレーション変形候補を示す図である。
【図１４】ループ処理Ｒ１におけるイタレーション０〜２及びみせかけ依存を削除したイタレーション０〜２を示す図である。
【図１５】みせかけ依存を削除したイタレーション０及び１の各命令文についての変数表記の等価関係を算出した結果を示す図である。
【図１６】みせかけ依存を削除したイタレーション２の各命令文についての変数表記の等価関係を算出した結果を示す図である。
【図１７】真依存を削除したイタレーション０〜２及び部分プログラムＰ２を示す図である。
【図１８】部分プログラムＰ３を示す図である。
【図１９】ループ処理Ｒ５〜Ｒ８を示す図である。
【図２０】変数表記の等価関係の算出を行う他の方法の例を説明するための図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００１３】
≪実施の形態≫
＜概要＞
図２は、処理完了時において、配列ｂ［ｋ］（０≦ｋ≦９９）について、同一の処理結果を得ることが可能な等価な部分プログラムＰ１とＰ４とを示す図である。
【００１４】
実施の形態に係るプログラム生成装置は、従来のコンパイラを改良したものであり、従来のコンパイラが、プログラマにより予め生成された、図２（ｂ）に示す部分プログラムＰ４を含むソースプログラムを参照することにより生成し得たアセンブラプログラムと同様のアセンブラプログラムを、図２（ａ）に示す部分プログラムＰ１を含むソースプログラムを参照することにより生成するものである。
【００１５】
ここで、部分プログラムＰ１は、真依存の関係を有するループ処理Ｒ１を含むものである。真依存の関係については、後に詳細に説明するが、ループ制御変数ｋがｉ（０≦ｉ＜９９）である場合に実行されるブロックＢ１内の命令文で定義された変数が、ループ制御変数ｋがｉ＋１である場合に実行されるブロックＢ１内の命令文で参照されるような関係をいう。
【００１６】
真依存の関係を有する命令文間の実行順序が、本来の実行順序と逆転してしまうと、正しい結果が得られないことになるため、このループ処理Ｒ１は、ループ制御変数ｋを１ずつ増加させながら、逐次実行されるのが一般的である。
【００１７】
一方、部分プログラムＰ４に含まれるループ処理Ｒ４は、上述のような真依存の関係を有しないものである。従って、複数のプロセッサを用いて実行することが可能になる。例えば、ループ処理Ｒ４を、ループ制御変数ｋが０から４９までの部分ループ処理と、ループ制御変数ｋが５０から９９までの部分ループ処理とに分けて、２つのプロセッサに独立して並列実行させることが可能である。これにより、１つのプロセッサでループ制御変数ｋが０から９９までについてのループ処理Ｒ１を逐次実行する場合と比較し、より高速にループ処理を実行することができる。
【００１８】
上述のように、実施の形態に係るプログラム生成装置は、図２（ａ）に示す部分プログラムＰ１を含むソースプログラムを参照することにより、従来のコンパイラが、図２（ｂ）に示す部分プログラムＰ４を含むソースプログラムを参照することにより生成し得たアセンブラプログラムと同様のアセンブラプログラムを生成できる。
【００１９】
従って、部分プログラムＰ１のように、真依存の関係を有するループ処理を含むソースプログラムが既に生成されている場合に、部分プログラムＰ４のように、真依存の関係を有しないループ処理を含むソースプログラムを生成しなおすことなく、並列実行に適したアセンブラプログラムを生成することができる点で、実施の形態に係るプログラム生成装置は有効である。
【００２０】
なお、部分プログラムＰ１は、上述のように真依存の関係を有するループ処理Ｒ１を含むものの、以下説明する理由から、部分プログラムＰ４と比べて、単一のプロセッサでの高速実行に適したプログラムであるといえる。
【００２１】
ここで、プログラム内の変数をなるべくレジスタに割り当てるようにすることで、プログラムをより高速に実行できることが一般的に知られている。これは、メモリと比較し、レジスタへのアクセスは、きわめて高速に行えるためである。
【００２２】
一般的なコンパイラにおいては、部分プログラムＰ１に含まれるａ０、ａ１、ａ２のような単純変数には、特定のレジスタが割り当てられる可能性が高い。従って、部分プログラムＰ１を実行する場合には、部分プログラムＰ４を実行する場合より、メモリへのアクセス回数を減らすことができる。つまり、単一のプロセッサを用いた場合、部分プログラムＰ１は、部分プログラムＰ４より高速に実行することができる。
【００２３】
＜データの依存関係＞
上記真依存をはじめとするデータの依存関係について、図３を用いて説明する。
【００２４】
図３は、データの依存関係を説明するための図である。
【００２５】
同図に示すように、命令文ＳＴ１００で定義された変数ａは、この命令文ＳＴ１００より後に実行される命令文ＳＴ２００で参照される関係にある。このような関係にある場合に、命令文ＳＴ１００から命令文ＳＴ２００への「真依存」があるという。
【００２６】
また、同図に示すように、命令文ＳＴ２００で参照された変数ａは、この命令文ＳＴ２００より後に実行される命令文ＳＴ３００で定義される関係にある。このような関係にある場合に、命令文ＳＴ２００から命令文ＳＴ３００への「逆依存」があるという。
【００２７】
また、同図に示すように、命令文ＳＴ１００で定義された変数ａは、命令文ＳＴ３００で再定義される関係にある。このような関係にある場合に、命令文ＳＴ１００から命令文ＳＴ３００への「出力依存」があるという。
【００２８】
また、以下では、真依存、逆依存及び出力依存の発生原因となっている変数を「依存の原因となる変数」という。図３では、変数ａが、「依存の原因となる変数」である。
【００２９】
なお、「逆依存」と「出力依存」については、依存関係にある各命令文において、依存の原因となる変数の表記を、相互に異なるものに置き換えることで、その依存が削除できることが知られている（例えば、非特許文献１の１２０ページ参照）。そのため、「逆依存」及び「出力依存」は、「みせかけ依存」と呼ばれることがある。
【００３０】
上記部分プログラムＰ１におけるループ処理Ｒ１を例に、データの依存関係を具体的に説明する。
【００３１】
図４は、図２（ａ）に示すループ処理Ｒ１におけるデータの依存関係を説明するための図である。
【００３２】
以下では、ループ制御変数がｍ（ｍはループ制御変数が取りうる任意の値）である場合に実行されるループ内のブロックのことを、「イタレーションｍ」といい、イタレーションｍを生成することを、「ｍについてのイタレーション展開」といい、このｍのことを、「イタレーション番号」という。
【００３３】
図４（ａ）は、図２（ａ）に示すループ処理Ｒ１におけるループ制御変数ｋが０である場合に実行されるブロックＢ１、つまり、イタレーション０を、図４（ｂ）は、イタレーション１を示している。
【００３４】
ここで、図４（ａ）に示すイタレーション０の命令文ＳＴ１２、ＳＴ１３、ＳＴ１４でそれぞれ定義されている変数ａ０、ａ１、ａ２は、図４（ｂ）に示すイタレーション１の命令文ＳＴ２１で参照される関係にある。
【００３５】
また、図４（ａ）に示すイタレーション０の命令文ＳＴ１３、ＳＴ１４でそれぞれ定義されている変数ａ１、ａ２は、図４（ｂ）に示すイタレーション１の命令文ＳＴ２２、ＳＴ２３で参照される関係にある。
【００３６】
即ち、変数ａ０を依存の原因とした、命令文ＳＴ１２からＳＴ２１への真依存がある。また、変数ａ１を依存の原因とした、命令文ＳＴ１３からＳＴ２１への真依存及び命令文ＳＴ１３からＳＴ２２への真依存がある。また、変数ａ２を依存の原因とした、命令文ＳＴ１４からＳＴ２１への真依存及び命令文ＳＴ１４からＳＴ２３への真依存がある。
【００３７】
また、図４（ａ）に示すイタレーション０の命令文ＳＴ１２で定義された変数ａ０は、図４（ｂ）に示すイタレーション１の命令文ＳＴ２２で再定義される関係にある。
【００３８】
即ち、変数ａ０を依存の原因とした、命令文ＳＴ１２からＳＴ２２への出力依存がある。同様に、変数ａ１を依存の原因とした、命令文ＳＴ１３からＳＴ２３への出力依存があり、変数ａ２を依存の原因とした、命令文ＳＴ１４からＳＴ２４への出力依存がある。
【００３９】
また、図４（ｂ）に示すイタレーション１の命令文ＳＴ２１で参照された変数ａ０、ａ１、ａ２は、命令文ＳＴ２２〜ＳＴ２４でそれぞれ定義される関係にある。即ち、変数ａ０を依存の原因とした、命令文ＳＴ２１からＳＴ２２への逆依存があり、変数ａ１を依存の原因とした、命令文ＳＴ２１からＳＴ２３への逆依存があり、変数ａ２を依存の原因とした、命令文ＳＴ２１からＳＴ２４への逆依存がある。
【００４０】
また、イタレーション０においても同様に、変数ａ０、変数ａ１、変数ａ２を依存の原因とした逆依存がある。
【００４１】
なお、以下では、ループ処理における、あるイタレーション内の命令文から他のイタレーション内の命令文への依存があることを、「イタレーション間に依存関係を有する」ともいう。
【００４２】
＜構成＞
図１は、実施の形態に係るプログラム生成装置１００を含むコンパイラシステム１０００の構成を示すブロック図である。
【００４３】
コンパイラシステム１０００は、上記部分プログラムＰ１のように、イタレーション間に真依存の関係を有するループ処理を含むソースプログラム１１を参照することにより、複数のプロセッサによるループ処理の並列実行が可能な目的プログラム１４を生成するものである。
【００４４】
コンパイラシステム１０００は、プロセッサ（不図示）と、メモリ（不図示）と、ハードディスク等の記憶装置１０とを含むコンピュータ（例えば、ＰＣ（Personal Computer））により実現される。
【００４５】
コンパイラシステム１０００は、同図に示すように、記憶装置１０と、プログラム生成装置１００と、アセンブラ２１０と、リンカ２２０とを含んで構成される。なお、プログラム生成装置１００、アセンブラ２１０及びリンカ２２０の各機能は、上記プロセッサが、記憶装置１０に記憶されている図示しないプログラムを上記メモリに読み込み、読み込んだプログラムを実行することによって実現される。
【００４６】
ここで、プログラム生成装置１００は、従来のコンパイラを改良したものであり、記憶装置１０に記憶されている、Ｃ言語やＣ＋＋言語等の高級言語で記述されたソースプログラム１１を参照して、アセンブラプログラム１２を生成する機能を有する。プログラム生成装置１００は、生成したアセンブラプログラム１２を記憶装置１０へ格納する。
【００４７】
即ち、プログラム生成装置１００は、イタレーション間に真依存の関係を有するループ処理を含むソースプログラム１１を参照することにより、この真依存の関係が解消されたループ処理を実行するためのアセンブラプログラム１２を生成する。
【００４８】
また、アセンブラ２１０は、プログラム生成装置１００により記憶装置１０へ格納されたアセンブラプログラム１２を参照して、機械語で記述された再配置可能バイナリプログラム１３を生成する機能を有する。アセンブラ２１０は、生成した再配置可能バイナリプログラム１３を記憶装置１０へ格納する。
【００４９】
また、リンカ２２０は、アセンブラ２１０により記憶装置１０へ格納された再配置可能バイナリプログラム１３において未解決なデータのアドレス配置等を決定し、必要なライブラリ等と連結することで、コンピュータが実行可能な目的プログラム１４を生成する機能を有する。リンカ２２０は、生成した目的プログラム１４を記憶装置１０へ格納する。
【００５０】
以下では、プログラム生成装置１００の構成について、図１を用いて、より詳しく説明する。
【００５１】
同図に示すように、プログラム生成装置１００は、記憶部１１０と、取得部１２０と、算出部１３０と、特定部１４０と、生成部１５０とを備える。
【００５２】
ここで、記憶部１１０は、ソースプログラム１１や、算出部１３０、特定部１４０及び生成部１５０による処理結果を格納するためのメモリ領域である。
【００５３】
即ち、以下では特に明記しないが、算出部１３０、特定部１４０及び生成部１５０間における処理結果のやり取りは、記憶部１１０を介して行われることとする。
【００５４】
また、取得部１２０は、記憶装置１０からソースプログラム１１を読み出し、記憶部１１０に格納する機能を有する。
【００５５】
算出部１３０は、取得部１２０により記憶部１１０に格納されたソースプログラム１１に含まれているループ処理における、あるイタレーション及び他の１以上のイタレーションについての変数表記の等価関係を算出する機能を有する。算出部１３０は、イタレーション展開部１３１と、みせかけ依存削除部１３２と、等価関係算出部１３３とを含む。
【００５６】
ここで、イタレーション展開部１３１は、ソースプログラム１１に含まれているループ処理に基づいて、イタレーション展開を行う機能を有する。
【００５７】
みせかけ依存削除部１３２は、イタレーション展開部１３１がイタレーション展開を行った、イタレーション番号が連続する２つのイタレーション間に存在するみせかけ依存（即ち出力依存及び逆依存）を削除する機能を有する。
【００５８】
ここでは、依存関係にある２つの命令文における依存の原因となる変数の表記を相互に異なるものに置き換えるという従来から行われている方法と同様の方法を用いて、みせかけ依存の削除を行うこととする。
【００５９】
等価関係算出部１３３は、みせかけ依存削除部１３２によりみせかけ依存が削除された後の上記２つのイタレーションの各命令文についての変数表記の等価関係を算出する機能を有する。ここでは、特許文献２において説明されている方法と同様の方法を用いて、変数表記の等価関係の算出を行うこととする。
【００６０】
また、特定部１４０は、等価関係算出部１３３が算出した変数表記の等価関係に基づいて、上記２つのイタレーション間に存在する真依存の原因となる全ての変数を、等価な依存関係のない他の変数や式に置き換えることで、全ての真依存を削除できるか否かを判定する機能を有する。
【００６１】
また、この判定結果に基づいて、特定部１４０は、算出部１３０による変数表記の等価関係の算出の実行を制御する機能及び以下説明する判定を行う機能を有する。即ち、この判定は、ソースプログラム１１に含まれているループ処理内のブロックを、以下説明する生成部１５０により生成されたイタレーション変形候補で置き換えることができるか否かを判定するものである。
【００６２】
生成部１５０は、特定部１４０が上記２つのイタレーション間に存在する全ての真依存を削除できると判定した際に、全ての真依存を削除したイタレーションに基づいて、イタレーション変形候補を生成する機能を有する。
【００６３】
詳しくは後述するが（図１３（ａ）及び（ｂ）参照）、イタレーション変形候補は、上記全ての真依存を削除したイタレーションを、そのイタレーション番号以降のイタレーションにも適用できるように一般化したものである。
【００６４】
また、生成部１５０は、特定部１４０がソースプログラム１１に含まれているループ処理内のブロックをイタレーション変形候補で置き換えることができると判定した際に、アセンブラプログラム１２を生成する機能を有する。このアセンブラプログラム１２は、ソースプログラム１１に含まれているループ処理内のブロックを、イタレーション変形候補で置き換えたソースプログラムに基づくものである。
【００６５】
＜動作＞
以下では、プログラム生成装置１００の動作を説明する。
【００６６】
図５〜７は、プログラム生成装置１００によるプログラム生成処理を示すフローチャートである。
【００６７】
プログラム生成装置１００の取得部１２０が、記憶装置１０からソースプログラム１１を読み出し、記憶部１１０に格納する。算出部１３０のイタレーション展開部１３１は、ソースプログラム１１に含まれるループ処理におけるループ制御変数の任意の値を示すｉと、ｉ＋１とについてのイタレーション展開を行う（図５のステップＳ１）。
【００６８】
算出部１３０のみせかけ依存削除部１３２は、イタレーションｉ及びイタレーションｉ＋１の各命令文間の依存関係を特定する（ステップＳ２）。また、みせかけ依存削除部１３２は、みせかけ依存（即ち、出力依存と逆依存）の原因となる変数の表記を変更することで、みせかけ依存を削除する（ステップＳ３）。
【００６９】
算出部１３０の等価関係算出部１３３は、みせかけ依存を削除したイタレーションｉ及びイタレーションｉ＋１の各命令文についての変数表記の等価関係を算出する（ステップＳ４）。
【００７０】
この変数表記の等価関係の算出方法は、上述のように、特許文献２において説明されている方法と同様の方法であるため、以下、簡単に説明するが、結果として、図１０に示すような等価式集合が得られることになる。
【００７１】
ここで、図１０（ａ）及び（ｂ）に示す“｛”と“｝”とで括られたものを「等価式集合」といい、等価式集合の中に記載されている“（”と“）”とで括られたものを「等価式」という。また、等価式の中に記載されている“,”で区切られた各要素は等価であることを示していることとする。
【００７２】
まず、等価関係算出部１３３は、イタレーションｉ及びイタレーションｉ＋１の各命令文を１つずつ順に処理対象として、以下の処理を行う。
【００７３】
即ち、等価関係算出部１３３は、処理対象である命令文の右辺又は左辺に記述されている変数や式を含む等価式が、既に等価式集合に含まれているかを判定する。
【００７４】
該当の等価式が等価式集合に含まれていないと判定した場合には、処理対象である命令文についての新たな等価式を等価式集合に追加する。
【００７５】
また、処理対象である命令文の右辺に記述されている変数や式を含む等価式が、既に等価式集合に含まれていると判定した場合には、その等価式の要素として、その処理対象である命令文の左辺に記述されている変数や式を追加する。
【００７６】
また、処理対象である命令文の左辺に記述されている変数や式を含む等価式が、既に等価式集合に含まれていると判定した場合には、その等価式に代えて、処理対象である命令文についての新たな等価式を等価式集合に追加する。
【００７７】
プログラム生成処理の続きを説明する（図５参照）。
【００７８】
ステップＳ４の処理が完了すると、特定部１４０は、等価関係算出部１３３が算出した変数表記の等価関係に基づいて、全ての真依存を削除することができるか否かを判定する（ステップＳ５）。
【００７９】
より詳細には、真依存の原因となる全ての変数の表記を、ステップＳ４で算出した変数表記の等価関係に基づいて、ステップＳ２で特定した依存の原因となる変数及びステップＳ３でみせかけ依存を削除するために導入した変数以外の等価な変数や式の表記に置き換えることができる場合には、全ての真依存を削除することができると判定する（ステップＳ５：ＹＥＳ）。
【００８０】
ここで、ステップＳ２で特定した依存の原因となる変数及びステップＳ３でみせかけ依存を削除するために導入した変数の表記に置き換えないのは、このような変数は、他のイタレーションにおいて新たな依存の原因となる可能性があるためである。即ち、このような変数の表記に置き換えても、結局のところ、イタレーション間の依存を削除することにならない可能性があるためである。
【００８１】
全ての真依存を削除することができると判定した場合には（ステップＳ５：ＹＥＳ）、全ての真依存が削除できたイタレーションｉ＋ｍにおけるｍの値として、「１」を設定し（ステップＳ６）、図６のステップＳ１５の処理に進む。
【００８２】
また、全ての真依存を削除することができないと判定した場合には（ステップＳ５：ＮＯ）、特定部１４０は、上記ｍの値を「２」に設定する（図６のステップＳ７）。
【００８３】
また、特定部１４０は、ｍの値が、ソースプログラム１１に含まれるループ制御変数が取り得る最大値（以下、「ｋｍａｘ」と表記する）から、そのループ制御変数が取り得る最小値（以下、「ｋｍｉｎ」と表記する）を引いた値より小さいか否かを判定する（ステップＳ８）。
【００８４】
ｍの値がｋｍａｘからｋｍｉｎを引いた値以上である場合には（ステップＳ８：ＮＯ）、真依存が削除できなかったものとして、プログラム生成装置１００は、プログラム生成処理を終了する（図７参照）。
【００８５】
一方、ｍの値がｋｍａｘからｋｍｉｎを引いた値より小さい場合には（ステップＳ８：ＹＥＳ）、特定部１４０は、ｍの値を通知することで、算出部１３０に処理を指示する。処理を指示された算出部１３０のイタレーション展開部１３１は、ステップＳ１の処理と同様に、ｉ＋ｍについてのイタレーション展開を行う（ステップＳ９）。
【００８６】
また、みせかけ依存削除部１３２は、ステップＳ２の処理と同様に、イタレーションｉ＋ｍ−１及びイタレーションｉ＋ｍの各命令文間の依存関係を特定し（ステップＳ１０）、ステップＳ３の処理と同様に、みせかけ依存を削除する（ステップＳ１１）。
【００８７】
また、等価関係算出部１３３は、ステップＳ４の処理と同様に、みせかけ依存を削除したイタレーションｉ＋ｍ−１及びイタレーションｉ＋ｍの各命令文についての変数表記の等価関係を算出する（ステップＳ１２）。
【００８８】
続いて、特定部１４０は、ステップＳ５の処理と同様に、ステップＳ１２で等価関係算出部１３３が算出した変数表記の等価関係に基づいて、全ての真依存を削除することができるか否かを判定する（ステップＳ１３）。
【００８９】
ここで、特定部１４０は、ステップＳ５で説明したものと同様の理由により、ステップＳ２及びＳ１０で特定した依存の原因となる変数及びステップＳ３及びＳ１１でみせかけ依存を削除するために導入した変数の表記を、置き換えに用いない。
【００９０】
全ての真依存を削除することができないと判定した場合には（ステップＳ１３：ＮＯ）、特定部１４０は、ｍの値を１つ増加させて（ステップＳ１４）、再びステップＳ８から処理を行う。
【００９１】
一方、特定部１４０が、全ての真依存を削除することができると判定した場合には（ステップＳ１３：ＹＥＳ）、生成部１５０は、全ての真依存を削除したイタレーションｉ＋ｍに基づいてイタレーション変形候補を生成する（ステップＳ１５）。
【００９２】
ここで、ｉは、ソースプログラム１１に含まれるループ処理におけるループ制御変数の任意の値を示す。従って、イタレーションｉ＋ｍにおいて、全ての真依存が削除できるということは、イタレーションｋｍｉｎ＋ｍ以降のイタレーションで全ての真依存を削除できることを意味する。
【００９３】
そこで、生成部１５０は、イタレーション番号が、ｋｍｉｎ＋ｍからｋｍａｘまでのイタレーションにも適用できるように一般化したイタレーション変形候補を生成する。
【００９４】
続いて、特定部１４０は、ｋｍｉｎ及びｍ−１の値を通知することで、算出部１３０に処理を指示する。処理を指示された算出部１３０のイタレーション展開部１３１は、ステップＳ１の処理と同様に、ｋｍｉｎからｍ−１までそれぞれについてのイタレーション展開を行う（図７のステップＳ１６）。
【００９５】
また、みせかけ依存削除部１３２は、イタレーションｋｍｉｎからイタレーションｍ−１までのそれぞれについて、ステップＳ２の処理と同様に、各命令文間の依存関係を特定し（ステップＳ１７）、ステップＳ３の処理と同様に、みせかけ依存を削除する（ステップＳ１８）。
【００９６】
また、等価関係算出部１３３は、ステップＳ４の処理と同様に、みせかけ依存を削除したイタレーションｋｍｉｎからイタレーションｍ−１までのそれぞれの各命令文についての変数表記の等価関係を算出する（ステップＳ１９）。
【００９７】
続いて、特定部１４０は、ステップＳ５の処理と同様に、ステップＳ１９で等価関係算出部１３３が算出した変数表記の等価関係に基づいて、全ての真依存を削除することができるか否かを判定する（ステップＳ２０）。
【００９８】
特定部１４０が、全ての真依存を削除することができないと判定した場合には（ステップＳ２０：ＮＯ）、ループ制御変数が、ｋｍｉｎからｍ−１の範囲では、真依存を削除できなかったものとして、プログラム生成装置１００は、プログラム生成処理を終了する。
【００９９】
また、特定部１４０が、全ての真依存を削除することができると判定した場合には（ステップＳ２０：ＹＥＳ）、全ての真依存を削除したイタレーションｋｍｉｎからイタレーションｍ−１が、ステップＳ１５で生成したイタレーション変形候補におけるイタレーションｋｍｉｎからイタレーションｍ−１と同形であるか否かを判定する（ステップＳ２１）。
【０１００】
特定部１４０が、同形でないと判定した場合には（ステップＳ２１：ＮＯ）、プログラム生成装置１００は、プログラム生成処理を終了する。この場合、ループ制御変数がｋｍｉｎからｍ−１までの範囲に適用可能な真依存を削除したループ処理と、ループ制御変数がｍからｋｍａｘまでの範囲に適用可能な真依存を削除したループ処理とを１つのループ処理にまとめることはできないためである。
【０１０１】
一方、特定部１４０が、イタレーション変形候補におけるイタレーションｋｍｉｎからイタレーションｍ−１までと同形であると判定した場合には（ステップＳ２１：ＹＥＳ）、生成部１５０は、以下のようにしてアセンブラプログラム１２を生成する（ステップＳ２２）。即ち、生成部１５０は、ソースプログラム１１のループ処理内のブロックを、イタレーション変形候補に置き換えたプログラムに、最適化や並列化を行った上で、アセンブラプログラム１２を生成する。
【０１０２】
なお、最適化や並列化は、従来から行われている方法で実現できるため、ここでは、詳細な説明は省略し、最適化や並列化が行われた後のプログラムの具体例について後述する（図１８参照）。
【０１０３】
生成部１５０は、生成したアセンブラプログラム１２を、記憶装置１０に格納し、プログラム生成装置１００は、プログラム生成処理を終了する。
【０１０４】
＜具体例＞
以下では、ソースプログラム１１を、図２（ａ）に示す部分プログラムＰ１を含むものとした場合を例に、プログラム生成装置１００の動作を、図５〜７に示すフローチャートに即して説明する。
【０１０５】
プログラム生成装置１００の取得部１２０が、記憶装置１０からソースプログラム１１を読み出し、記憶部１１０に格納する。算出部１３０のイタレーション展開部１３１は、ソースプログラム１１に含まれるループ処理（この例では、Ｒ１）におけるループ制御変数（この例では、ｋ）の任意の値を示すｉと、ｉ＋１とについてのイタレーション展開を行う（図５のステップＳ１）。
【０１０６】
図８（ａ）は、図２（ａ）に示すループ処理Ｒ１におけるイタレーションｉを示す図であり、図８（ｂ）は、イタレーションｉ＋１を示す図である。
【０１０７】
算出部１３０のみせかけ依存削除部１３２は、イタレーションｉ及びイタレーションｉ＋１の各命令文間の依存関係を特定する（ステップＳ２）。また、みせかけ依存削除部１３２は、みせかけ依存（即ち、出力依存と逆依存）の原因となる変数の表記を変更することで、みせかけ依存を削除する（ステップＳ３）。
【０１０８】
図８（ａ）及び（ｂ）に示す例では、変数ａ０を依存の原因として、命令文ＳＴ４２から命令文ＳＴ５１への真依存と、命令文ＳＴ４２から命令文ＳＴ５２への出力依存と、命令文ＳＴ４１から命令文ＳＴ４２への逆依存と、命令文ＳＴ５１からＳＴ５２への逆依存とが存在する。
【０１０９】
また、変数ａ１を依存の原因として、命令文ＳＴ４３から命令文ＳＴ５１への真依存と、命令文ＳＴ４３から命令文ＳＴ５３への出力依存と、命令文ＳＴ４１から命令文ＳＴ４３への逆依存と、命令文ＳＴ５１からＳＴ５３への逆依存とが存在する。
【０１１０】
また、変数ａ２を依存の原因として、命令文ＳＴ４４から命令文ＳＴ５１への真依存と、命令文ＳＴ４４から命令文ＳＴ５４への出力依存と、命令文ＳＴ４１から命令文ＳＴ４４への逆依存と、命令文ＳＴ５１からＳＴ５４への逆依存が存在する。
【０１１１】
命令文ＳＴ４２における変数ａ０の表記を「ａ０＿ｉ」に変更し、命令文ＳＴ５２における変数ａ０の表記を「ａ０＿ｉ１」に変更することで、変数ａ０を依存の原因としたみせかけ依存を削除することができる。
【０１１２】
また、変数ａ０の場合と同様に、命令文ＳＴ４３における変数ａ１の表記を「ａ１＿ｉ」に変更し、命令文ＳＴ５３における変数ａ１の表記を「ａ１＿ｉ１」に変更することで、変数ａ１を依存の原因としたみせかけ依存を削除することができる。また、命令文ＳＴ４４における変数ａ２の表記を「ａ２＿ｉ」に変更し、命令文ＳＴ５４における変数ａ２の表記を「ａ２＿ｉ１」に変更することで、変数ａ２を依存の原因としたみせかけ依存を削除することができる。
【０１１３】
図９（ａ）は、図８（ａ）に示すイタレーションｉからみせかけ依存を削除したイタレーションｉを示す図であり、図９（ｂ）は、図８（ｂ）に示すイタレーションｉ＋１からみせかけ依存を削除したイタレーションｉ＋１を示す図である。
【０１１４】
なお、ステップＳ３の処理では、みせかけ依存を削除しただけなので、真依存は引き続き存在することになる。即ち、図９（ａ）及び（ｂ）に示す例では、命令文ＳＴ４６、ＳＴ４７、ＳＴ４８から命令文ＳＴ５５への変数ａ０＿ｉ、ａ１＿ｉ、ａ２＿ｉを依存の原因とした真依存と、命令文ＳＴ４７、ＳＴ４８から命令文ＳＴ５６、ＳＴ５７への変数ａ１＿ｉ、ａ２＿ｉを依存の原因とした真依存が存在することになる。
【０１１５】
算出部１３０の等価関係算出部１３３は、みせかけ依存を削除したイタレーションｉ及びイタレーションｉ＋１の各命令文についての変数表記の等価関係を算出する（ステップＳ４）。
【０１１６】
図９（ａ）及び（ｂ）に示すみせかけ依存を削除したイタレーションｉ及びイタレーションｉ＋１の各命令文（ＳＴ４５〜ＳＴ４８、ＳＴ５５〜ＳＴ５８）について、変数表記の等価関係を算出すると以下のようになる。
【０１１７】
なお、以下の説明開始時点において、等価式集合にはいずれの等価式も含まれていないとする。
【０１１８】
まず、図９（ａ）に示す命令文ＳＴ４５を処理対象とした場合には、命令文ＳＴ４５の右辺及び左辺に記述されている変数や式を含む等価式が、等価式集合に含まれていないので、図１０（ａ）に示す等価式集合Ｅ４５のように、命令文ＳＴ４５についての等価式が等価式集合に追加される。
【０１１９】
即ち、等価式集合Ｅ４５は、命令文ＳＴ４５が実行された直後では、変数「ｂ［ｉ］」と式「ａ０＋ａ１＋ａ２」が等価な関係にあることを示している。
【０１２０】
図９（ａ）に示す命令文ＳＴ４６〜ＳＴ４８及び図９（ｂ）の命令文ＳＴ５５を処理対象とした場合にも、命令文ＳＴ４５の場合と同様に処理される（図１０（ａ）の等価式集合Ｅ４６〜Ｅ４８及び図１０（ｂ）の等価式集合Ｅ５５参照）。
【０１２１】
また、図９（ｂ）に示す命令文ＳＴ５６を処理対象とした場合には、命令文ＳＴ５６の右辺に記述されている変数（この例では「ａ１＿ｉ」）を含む等価式（この例では、（ａ１＿ｉ,ａ２））が、既に等価式集合Ｅ５５に含まれている。従って、その等価式に、命令文ＳＴ５６の左辺に記述されている変数（この例では、「ａ０＿ｉ１」）が追加される（図１０（ｂ）の等価式集合Ｅ５６参照）。
【０１２２】
図９（ｂ）に示す命令文ＳＴ５７を処理対象とした場合も、命令文ＳＴ５６の場合と同様に処理される（図１０（ｂ）の等価式集合Ｅ５７参照）。
【０１２３】
また、図９（ｂ）に示す命令文ＳＴ５８を処理対象とした場合には、命令文ＳＴ４５の場合と同様に、命令文ＳＴ５８についての等価式が、等価式集合Ｅ５７に追加される（図１０（ｂ）の等価式集合Ｅ５８参照）。
【０１２４】
続いて、特定部１４０は、ステップＳ４で等価関係算出部１３３が算出した変数表記の等価関係に基づいて、全ての真依存を削除することができるか否かを判定する（ステップＳ５）。
【０１２５】
上述のように、図９（ａ）及び（ｂ）に示す例では、変数ａ０＿ｉ、ａ１＿ｉ、ａ２＿ｉを依存の原因とした真依存が存在する。
【０１２６】
図１０（ａ）に示す等価式集合Ｅ４８によれば、真依存の原因となる変数「ａ２＿ｉ」は、変数「ａ［ｉ＋３］」と等価である。また、この変数「ａ［ｉ＋３］」は、ステップＳ２で特定した依存の原因となる変数及びステップＳ３でみせかけ依存を削除するために導入した変数ではない。従って、変数「ａ２＿ｉ」の表記を、変数「ａ［ｉ＋３］」の表記に置き換えることができる。
【０１２７】
また、等価式集合Ｅ４８によれば、真依存の原因となる変数「ａ０＿ｉ」は、変数「ａ１」と等価であり、真依存の原因となる変数「ａ１＿ｉ」は、変数「ａ２」と等価である。しかしながら、変数「ａ１」及び変数「ａ２」は、ステップＳ２で特定した依存の原因となる変数であるため、真依存の原因となる変数「ａ０＿ｉ」及び変数「ａ１＿ｉ」の各表記の置き換えはできない。
【０１２８】
従って、特定部１４０は、全ての真依存を削除することができないと判定する（ステップＳ５：ＮＯ）。
【０１２９】
特定部１４０は、ｍの値を「２」に設定し（図６のステップＳ７）、この例では、ｍの値がｋｍａｘ（この例では「９９」）からｋｍｉｎ（この例では「０」）を引いた値より小さいので（ステップＳ８：ＹＥＳ）、ｍの値（この例では「２」）を通知し、算出部１３０に処理を指示する。
【０１３０】
イタレーション展開部１３１は、ステップＳ１の処理と同様に、ｉ＋ｍ（この例では「ｉ＋２」）についてのイタレーション展開を行う（ステップＳ９）。
【０１３１】
また、算出部１３０のみせかけ依存削除部１３２は、イタレーションｉ＋ｍ−１（この例では「ｉ＋１」）と、イタレーションｉ＋ｍとについて、ステップＳ３の処理と同様に、みせかけ依存を削除する（ステップＳ１１）。
【０１３２】
また、算出部１３０の等価関係算出部１３３は、ステップＳ４の処理と同様に、みせかけ依存を削除したイタレーションｉ＋ｍ−１及びイタレーションｉ＋ｍの各命令文についての変数表記の等価関係を算出する（ステップＳ１２）。
【０１３３】
図１１（ａ）は、みせかけ依存を削除したイタレーションｉ＋２を示す図であり、図１１（ｂ）は、みせかけ依存を削除したイタレーションｉ＋２の各命令文についての変数表記の等価関係を算出した結果を示す図である。
【０１３４】
ここで、図１１（ｂ）に示す等価式集合Ｅ６５は、図１１（ａ）に示す命令文ＳＴ６５に基づいて、等価式「（ｂ［ｉ＋２］，ａ０＿ｉ１＋ａ１＿ｉ１＋ａ２＿ｉ１）」を、図１０（ｂ）に示す等価式集合Ｅ５８に追加したものになっている。
【０１３５】
特定部１４０は、ステップＳ５の処理と同様に、ステップＳ１２で等価関係算出部１３３が算出した変数表記の等価関係に基づいて、全ての真依存を削除することができるか否かを判定する（ステップＳ１３）。
【０１３６】
図９（ｂ）及び図１１（ａ）に示す例では、変数ａ０＿ｉ１、ａ１＿ｉ１、ａ２＿ｉ１を依存の原因とした真依存が存在することになる。
【０１３７】
図１０（ｂ）に示す等価式集合Ｅ５８によれば、真依存の原因となる変数「ａ２＿ｉ１」は、変数「ａ［ｉ＋４］」と等価であり、真依存の原因となる変数「ａ１＿ｉ１」は、変数「ａ［ｉ＋３］」と等価である。また、変数「ａ［ｉ＋４］」及び変数「ａ［ｉ＋３］」は、ステップＳ２及びＳ１０で特定した依存の原因となる変数及びステップＳ３及びＳ７でみせかけ依存を削除するために導入した変数ではない。
【０１３８】
従って、変数「ａ２＿ｉ１」の表記を変数「ａ［ｉ＋４］」の表記に、変数「ａ１＿ｉ１」の表記を変数「ａ［ｉ＋３］」の表記に置き換えることができる。
【０１３９】
また、等価式集合Ｅ５８によれば、真依存の原因となる変数「ａ０＿ｉ１」は、変数「ａ１＿ｉ」及び変数「ａ２」と等価である。しかしながら、変数「ａ１＿ｉ」は、ステップＳ３でみせかけ依存を削除するために用いた変数であり、変数「ａ２」は、ステップＳ２で特定した依存の原因となる変数である。従って、真依存の原因となる変数「ａ０＿ｉ１」の表記の置き換えはできない。よって、特定部１４０は、全ての真依存を削除することができないと判定する（ステップＳ１３：ＮＯ）。
【０１４０】
この例では、特定部１４０は、ｍの値を１つ増加させて「３」とし（ステップＳ１４）、ｍの値がｋｍａｘ（この例では、「９９」）からｋｍｉｎ（この例では、「０」）を引いた値より小さいので（ステップＳ８：ＹＥＳ）、ｍの値を通知して算出部１３０に処理を指示する。処理を指示された算出部１３０は、上記同様、ステップＳ９〜ステップＳ１２の処理を行う。
【０１４１】
図１２（ａ）は、みせかけ依存を削除したイタレーションｉ＋３を示す図であり、図１２（ｂ）は、みせかけ依存を削除したイタレーションｉ＋３の各命令文についての変数表記の等価関係を算出した結果を示す図である。
【０１４２】
図１１（ａ）及び図１２（ａ）に示す例では、変数ａ０＿ｉ２、ａ１＿ｉ２、ａ２＿ｉ２を依存の原因とした真依存が存在することになる。
【０１４３】
図１１（ｂ）に示す等価式集合Ｅ６８によれば、真依存の原因となる変数「ａ２＿ｉ２」は、変数「ａ［ｉ＋５］」と等価であり、真依存の原因となる変数「ａ１＿ｉ２」は、変数「ａ［ｉ＋４］」と等価であり、真依存の原因となる変数「ａ０＿ｉ２」は、変数「ａ［ｉ＋３］」と等価である。また、変数「ａ［ｉ＋５］」、変数「ａ［ｉ＋４］」及び変数「ａ［ｉ＋３］」は、ステップＳ２及びＳ１０で特定した依存の原因となる変数及びステップＳ３及びＳ７でみせかけ依存を削除するために導入した変数ではない。
【０１４４】
従って、変数「ａ２＿ｉ２」の表記を変数「ａ［ｉ＋５］」の表記に、変数「ａ１＿ｉ２」の表記を変数「ａ［ｉ＋４］」の表記に、変数「ａ０＿ｉ２」の表記を変数「ａ［ｉ＋３］」の表記に置き換えることができる。
【０１４５】
よって、特定部１４０は、全ての真依存を削除することができると判定し（ステップＳ１３：ＹＥＳ）、生成部１５０は、全ての真依存が削除できたイタレーションｉ＋ｍ（この例では「ｉ＋３」）に基づいてイタレーション変形候補を生成する（ステップＳ１５）。
【０１４６】
図１３（ａ）は、全ての真依存を削除したイタレーションｉ＋３を示す図である。
【０１４７】
図１３（ａ）に示す例では、生成部１５０は、「ｉ＋３」をｋとおいて、変数「ａ０＿ｉ３」の表記を変数「ａ０＿ｋ」の表記に、変数「ａ１＿ｉ３」の表記を変数「ａ１＿ｋ」の表記に、変数「ａ２＿ｉ３」の表記を変数「ａ２＿ｋ」の表記に置き換えたイタレーション変形候補を生成する。
【０１４８】
図１３（ｂ）は、生成部１５０が生成したイタレーション変形候補を示す図である。
【０１４９】
このイタレーション変形候補は、ｋが、ｋｍｉｎ＋ｍ（この例では「３」）からｋｍａｘ（この例では「９９」）までのイタレーションに適用できるものである。即ち、少なくとも３≦ｋ＜ｋｍａｘの範囲においては、図２（ａ）に示すループ処理Ｒ１のブロックＢ１を、イタレーション間に依存がない等価なブロックに置き換えることができることになる。
【０１５０】
続いて、特定部１４０は、ｋｍｉｎ（この例では「０」）及びｍ−１（この例では「２」）の値を通知して、算出部１３０に処理を指示する。処理を指示された算出部１３０のイタレーション展開部１３１は、ステップＳ１の処理と同様に、ｋｍｉｎからｍ−１までそれぞれについてのイタレーション展開を行う（図７のステップＳ１６）。
【０１５１】
また、みせかけ依存削除部１３２は、イタレーションｋｍｉｎからイタレーションｍ−１について、ステップＳ２と同様に、各命令文間の依存関係を特定し（図７のステップＳ１７）、ステップＳ３の処理と同様に、みせかけ依存を削除する（ステップＳ１８）。
【０１５２】
図１４（ａ）に示すイタレーションＩ１〜Ｉ３は、図２（ａ）に示すループ処理Ｒ１におけるイタレーション０〜２を示している。
【０１５３】
また、図１４（ｂ）に示すイタレーションＩ１０〜Ｉ３０は、図１４（ａ）に示すイタレーション０〜２からみせかけ依存を削除したイタレーション０〜２を示している。また、図１４（ｂ）に示す命令文ＳＴ１〜ＳＴ３は、図２（ａ）に示すループ処理Ｒ１の直前にある命令文ＳＴ１〜ＳＴ３である。
【０１５４】
等価関係算出部１３３は、ステップＳ４の処理と同様に、みせかけ依存を削除したイタレーションｋｍｉｎからイタレーションｍ−１までのそれぞれの各命令文についての変数表記の等価関係を算出する（ステップＳ１９）。
【０１５５】
図１５は、図１４（ｂ）に示す命令文ＳＴ１〜ＳＴ３及びみせかけ依存を削除したイタレーション０〜１の各命令文についての変数表記の等価関係を算出した結果を示す図である。
【０１５６】
また、図１６は、図１４（ｂ）に示すみせかけ依存を削除したイタレーション２の各命令文についての変数表記の等価関係を算出した結果を示す図である。
【０１５７】
続いて、特定部１４０は、ステップＳ５の処理と同様に、ステップＳ１９で等価関係算出部１３３が算出した変数表記の等価関係に基づいて、全ての真依存を削除することができるか否かを判定する（ステップＳ２０）。
【０１５８】
図１５に示す等価式集合Ｅ３によれば、真依存の原因となる変数「ａ０」は、変数「ａ［０］」と等価であり、真依存の原因となる変数「ａ１」は、変数「ａ［１］」と等価であり、真依存の原因となる変数「ａ２」は、変数「ａ［２］」と等価である。また、変数「ａ［０］」、変数「ａ「１」」及び変数「ａ［２］」は、ステップＳ１７で特定した依存の原因となる変数及びステップＳ１８でみせかけ依存を削除するために導入した変数ではない。
【０１５９】
従って、図１４（ｂ）に示す命令文ＳＴ１５の変数「ａ０」の表記を変数「ａ［０］」の表記に、変数「ａ１」の表記を変数「ａ［１］」の表記に、変数「ａ２」の表記を変数「ａ［２］」の表記に置き換えることができる。
【０１６０】
同様にして、図１５に示す等価式集合Ｅ１５に基づいて、図１４（ｂ）に示す命令文ＳＴ１６の変数「ａ１」の表記を変数「ａ［１］」の表記に置き換えることができる。また、図１５に示す等価式集合Ｅ１６に基づいて、図１４（ｂ）に示す命令文ＳＴ１７の変数「ａ２」の表記を変数「ａ［２］」の表記に置き換えることができる。
【０１６１】
同様にして、図１５に示す等価式集合Ｅ１８〜Ｅ２６に基づいて、図１４（ｂ）に示す命令文ＳＴ２５〜ＳＴ２７の変数「ａ０＿０」、変数「ａ１＿０」及び変数「ａ２＿０」の表記を置き換えることができる。また、図１５に示す等価式集合Ｅ２８及び図１６に示す等価式集合Ｅ３５、Ｅ３６に基づいて、命令文ＳＴ３５〜ＳＴ３７の変数「ａ０＿１」、変数「ａ１＿１」及び変数「ａ２＿１」の表記を置き換えることができる。
【０１６２】
従って、特定部１４０は、全ての真依存を削除することができると判定し（ステップＳ２０：ＹＥＳ）、全ての真依存を削除したイタレーションｋｍｉｎ（この例では「０」）からイタレーションｍ−１（この例では「２」）が、ステップＳ１５で生成したイタレーション変形候補におけるイタレーションｋｍｉｎからイタレーションｍ−１と同形であるか否かを判定する（ステップＳ２１）。
【０１６３】
図１７（ａ）に示すイタレーションＩ１１、Ｉ２１、Ｉ３１は、図１４（ｂ）に示すみせかけ依存を削除したイタレーション０〜２（Ｉ１０、Ｉ２０、Ｉ３０）から真依存を削除したイタレーションを示している。
【０１６４】
図１３（ｂ）に示すイタレーション変形候補についてのイタレーション０、イタレーション１、イタレーション３は、図１７（ａ）に示すイタレーションＩ１１、Ｉ２１、Ｉ３１と一致する。従って、この例では、特定部１４０は、同形であると判定し（ステップＳ２１：ＹＥＳ）、生成部１５０は、ソースプログラム１１のループ処理Ｒ１のブロックＢ１を、イタレーション変形候補に置き換えて最適化や並列化したプログラムに基づくアセンブラプログラム１２を生成する（ステップＳ２２）。
【０１６５】
図１７（ｂ）は、図２（ａ）に示す部分プログラムＰ１のブロックＢ１を、図１３（ｂ）に示すイタレーション変形候補に置き換えた部分プログラムＰ２を示している。
【０１６６】
この部分プログラムＰ２において、命令文ＳＴ１〜ＳＴ３で定義される変数「ａ０」、変数「ａ１」及び変数「ａ２」と、命令文ＳＴ９２〜ＳＴ９４で定義される変数「ａ０＿ｋ」、変数「ａ１＿ｋ」及び変数「ａ２＿ｋ」は、部分プログラムＰ２内の命令文では参照されない。従って、ソースプログラム１１における、部分プログラムＰ２以外の部分でもこれらの変数が参照されないことを条件に、命令文ＳＴ１〜ＳＴ３と、変数「ａ０」、変数「ａ１」及び変数「ａ２」を宣言する命令文ＳＴ４と、命令文ＳＴ９２〜ＳＴ９４とを削除した最適化された部分プログラムＰ３（図１８参照）を生成することができる。
【０１６７】
また、生成部１５０は、部分プログラムＰ３を並列化した部分プログラムＰ４（図２（ｂ）参照）を生成する。また、生成部１５０は、この部分プログラムＰ４を含むソースプログラムに基づいて生成したアセンブラプログラム１２を、記憶装置１０に格納し、プログラム生成装置１００は、プログラム生成処理を終了する。
【０１６８】
なお、図２（ｂ）に示す部分プログラムＰ４における並列化を指示するための記述は、ＯｐｅｎＭＰの記述形式に沿ったものである。
【０１６９】
≪補足≫
以上、本発明に係るプログラム生成装置を、実施の形態に基づいて説明したが、以下のように変形することも可能であり、本発明は上述した実施の形態で示した通りのプログラム生成装置に限られないことは勿論である。
【０１７０】
（１）実施の形態に係るプログラム生成装置１００は、イタレーション番号が連続する２つのイタレーション間に真依存の関係を有するループ処理を含むソースプログラム１１からアセンブラプログラム１２を生成する場合を例に説明した。しかしながら、イタレーション番号が連続しない２つのイタレーション間に真依存の関係を有するループ処理（例えば、図１９（ａ）に示すループ処理Ｒ５や、図１９（ｃ）に示すループ処理Ｒ７）を含むソースプログラム１１からアセンブラプログラム１２を生成するようにしてもよい。なお、図１９（ｂ）は、ループ処理Ｒ５と等価な上記真依存の関係を有しないループ処理Ｒ６を示している。また、図１９（ｄ）は、ループ処理Ｒ７と等価な上記真依存の関係を有しないループ処理Ｒ８を示している。
【０１７１】
そのためには、図５のステップＳ２の処理で依存関係を特定した結果、真依存の関係が存在しない場合には、真依存の関係を有する２つのイタレーションを特定する処理を行う。
【０１７２】
即ち、イタレーション番号ｓ（ｉ＋２≦ｓ＜Ｎ）についてイタレーション展開を行い、イタレーションｉ及びイタレーションｓの各命令文間の依存関係を特定する。真依存の関係が存在しない場合には、ｓを１つずつ増やしながら、上記イタレーション展開及び依存関係の特定を繰り返し、真依存の関係が存在する場合には、ステップＳ３、Ｓ４におけるイタレーションｉ＋１を、イタレーションｓに置き換えて、ステップＳ３、Ｓ４の処理を行う。
【０１７３】
また、ステップＳ６のｍをｓに設定するように変更し、図６のステップＳ７のｍをｓ＋１に設定するように変更し、ステップＳ８以降は、実施の形態で説明したのと同様に処理できる。
【０１７４】
このように、この変形に係るプログラム生成装置によれば、例えば、図１９（ａ）に示すループ処理Ｒ５や、図１９（ｃ）に示すループ処理Ｒ７を含むソースプログラムを参照することにより、従来のコンパイラが、図１９（ｂ）に示すループ処理Ｒ６や図１９（ｄ）に示すループ処理Ｒ８を含むソースプログラムを参照することにより生成し得たアセンブラプログラムと同様のアセンブラプログラムを生成できる。
【０１７５】
（２）実施の形態に係るプログラム生成装置１００は、図７のステップＳ２１において、全ての真依存を削除したイタレーションｋｍｉｎからイタレーションｍ−１が、図６のステップＳ１５で生成したイタレーション変形候補におけるイタレーションｋｍｉｎからイタレーションｍ−１と同形でない場合には（ステップＳ２１：ＮＯ）、アセンブラプログラム１２を生成せずプログラム生成処理を終了するものとして説明した。しかしながら、ループ処理を、ループ制御変数がｋｍｉｎからｍ−１までの範囲の部分ループ処理Ｘと、ループ制御変数がｍからｋｍａｘまでの範囲の部分ループ処理Ｙとに分けて、ループ処理Ｙを複数のプロセッサにより並列実行可能に構成したアセンブラプログラム１２を生成するようにしてもよい。
【０１７６】
（３）実施の形態に係るプログラム生成装置１００は、ソースプログラム１１を参照することにより、アセンブラプログラム１２を生成するものとして説明した。しかしながら、プログラム生成装置が、アセンブラ２１０及びリンカ２２０を備えるように変形し、この変形に係るプログラム生成装置は、ソースプログラム１１を参照することにより、目的プログラム１４を生成するようにしてもよい。
【０１７７】
また、実施の形態に係るリンカ２２０は、未解決なデータのアドレス配置等を決定した再配置可能バイナリプログラム１３と、必要なライブラリ等を連結するものとして説明したが、当然、複数の再配置可能バイナリプログラム１３同士を連結するようにしてもよい。
【０１７８】
（４）実施の形態に係るプログラム生成装置１００における算出部１３０の等価関係算出部１３３は、特許文献２において説明されている方法と同様の方法を用いて、変数表記の等価関係の算出を行うものとして説明したが、これは一例であり、他の方法により算出するようにしてもよい。
【０１７９】
例えば、命令文「ｘ＝ｙ」における、ｘにｙと同じ値が格納されているという関係、つまり、ｘとｙとが等価であるという関係を利用して、命令文の表記を置き換えていくこと（以下、「コピー伝播」という）を繰り返し行う方法により算出するようにしてもよい。
【０１８０】
以下、この方法を簡単に説明する。
【０１８１】
例えば、図８（ａ）に示すイタレーションｉの命令文ＳＴ４４「ａ２＝ａ［ｉ＋３］」についてコピー伝播を行うことで、図８（ｂ）に示すイタレーションｉ＋１の命令文ＳＴ５１の表記は「ｂ［ｉ＋１］＝ａ０＋ａ１＋ａ［ｉ＋３］」に、命令文ＳＴ５３の表記は「ａ１＝ａ［ｉ＋３］」に置き換えられる。
【０１８２】
また、この置き換えた後の命令文ＳＴ５３と、命令文ＳＴ５４とについてコピー伝播を行うことで、図２０（ａ）に示すイタレーションｉ＋２の命令文ＳＴ６１の表記は「ｂ［ｉ＋２］＝ａ０＋ａ［ｉ＋３］＋ａ［ｉ＋４］」に置き換えられる。また、命令文ＳＴ６２の表記は「ａ０＝ａ［ｉ＋３］」に、命令文ＳＴ６３の表記は「ａ１＝ａ［ｉ＋４］」に置き換えられる。
【０１８３】
また、この置き換えた後の命令文ＳＴ６２及びＳＴ６３と、命令文ＳＴ６４とについてコピー伝播を行うことで、図２０（ｂ）に示すイタレーションｉ＋３の命令文ＳＴ７１の表記は「ｂ［ｉ＋３］＝ａ［ｉ＋３］＋ａ［ｉ＋４］＋ａ［ｉ＋５］」、命令文ＳＴ７２の表記は「ａ０＝ａ［ｉ＋４］」に、命令文ＳＴ７３の表記は「ａ１＝ａ［ｉ＋５］」に置き換えられる（図２０（ｃ）参照）。
【０１８４】
（５）実施の形態において説明したプログラム生成処理（図５〜７参照）をプロセッサに実行させるためのプログラムを、記録媒体に記録し又は各種通信路等を介して、流通させ頒布することもできる。このような記録媒体には、ＩＣカード、光ディスク、フレキシブルディスク、ＲＯＭ、フラッシュメモリ等がある。流通、頒布されたプログラムは、機器におけるプロセッサで読み取り可能なメモリ等に格納されることにより利用に供され、そのプロセッサがそのプログラムを実行することにより実施の形態で示したプログラム生成装置の各機能が実現される。
【０１８５】
（６）実施の形態に係るプログラム生成装置１００に、上記（１）〜（５）の一部又は全部の変形を組み合わせて適用してもよい。
【０１８６】
（７）以下、更に本発明の一実施形態に係るプログラム生成装置の構成及びその変形例と各効果について説明する。
【０１８７】
（ａ）本発明の一実施形態に係るプログラム生成装置は、１つ以上の命令文からなるブロックを繰り返しＮ回（Ｎ≧２）処理するループ処理であって、ｉ（１≦ｉ＜Ｎ）回目の実行に係る前記ブロック内の命令文で定義された変数が、ｊ（ｉ＜ｊ≦Ｎ）回目の実行に係る前記ブロック内の命令文で参照される依存関係にあるループ処理を含む対象ソースプログラムを参照することにより、新たなプログラムを生成するプログラム生成装置であって、ｉ回目の実行に係る前記ブロックと、ｉ回目以外の実行に係る１以上の前記ブロックとを対象ブロックとして、当該対象ブロックにおける変数表記の等価関係を算出する算出処理を行う算出手段と、前記算出手段が算出した変数表記の等価関係に基づいて、前記変数のうち、前記依存関係にある全ての対象変数の表記について、当該対象変数の表記と等価な前記依存関係のない他の変数の表記を特定する特定処理を行う特定手段と、前記ループ処理のＭ回分（Ｍ≦Ｎ）の処理を行うための、前記特定手段が特定した他の変数の表記を含んだ命令文を含むプログラムを生成する生成手段とを備える。
【０１８８】
上記構成を備える本発明の一実施形態に係るプログラム生成装置によれば、ｉ回目の実行に係るブロック内の命令文と、ｊ回目の実行に係るブロック内の命令文との間に、いわゆる真依存の関係を有するループ処理を含む対象ソースプログラムを参照することにより、そのループ処理のＭ回分の処理を行うための、真依存の関係にある全ての対象変数の表記について、当該対象変数の表記と等価な真依存の関係のない他の変数の表記を含んだ命令文を含むプログラムを生成できる。
【０１８９】
この生成したプログラムによれば、ループ処理のＭ回分の処理を、複数のプロセッサにより独立して並列実行し、ループ処理を高速に実行し得る。
【０１９０】
従って、このプログラム生成装置は、真依存の関係を有するループ処理を含むソースプログラムを参照することにより、複数のプロセッサを用いてループ処理を高速に実行するためのプログラムの生成に有用である。
【０１９１】
（ｂ）また、前記特定手段が特定する前記対象変数の表記と等価な前記依存関係のない他の変数の表記は、いずれの対象変数の表記とも異なる変数の表記であることとしてもよい。
【０１９２】
このプログラム生成装置によれば、真依存の関係を有するループ処理を含む対象ソースプログラムを参照することにより、そのループ処理のＭ回分の処理を行うための、真依存の関係にある全ての対象変数の表記と等価な真依存の関係のない他の変数の表記を含んだ命令文を含むプログラムを生成できる。
【０１９３】
つまり、このプログラム生成装置は、真依存の関係を有するループ処理を含む対象ソースプログラムを参照することにより、ループ処理のＭ回分の処理を、複数のプロセッサで独立して並列実行することで高速に実行することが可能なプログラムを生成できる。
【０１９４】
（ｃ）また、前記算出手段は、ｉ回目の実行に係る前記ブロックと、ｉ＋１回目の実行に係る前記ブロックとを前記対象ブロックとして前記算出処理を行い、前記特定手段は、前記算出手段が前記算出処理を行う毎に、算出済みの各変数表記の等価関係に基づいて、全ての対象変数の表記について、当該対象変数の表記と等価な前記依存関係のない他の変数の表記であって、いずれの対象変数の表記とも異なる変数の表記を特定できるか否かの判定を行い、当該判定処理の結果が否定的である間、ｉを１ずつ増加させながら、前記算出手段に前記算出処理を繰り返し行わせることとしてもよい。
【０１９５】
このプログラム生成装置によれば、ｉがｎ（ｎ＜Ｎ）である場合に、真依存の関係にある全ての対象変数の表記について、当該対象変数の表記と等価な真依存の関係のない他の変数の表記を特定できた場合には、少なくともｎからＮまでのＮ−ｎ回分のループ処理を行うための、真依存の関係にある全ての対象変数の表記と等価な真依存の関係のない他の変数の表記を含んだ命令文を含むプログラムを生成できる。
【０１９６】
従って、少なくとも、このＮ−ｎ回分のループ処理を、複数のプロセッサで独立して並列実行することで高速に実行することが可能になる。
【０１９７】
（ｄ）また、前記プログラム生成装置が参照するプログラムは、単一のプロセッサで実行するためのプログラムであり、前記生成手段が生成するプログラムは、複数のプロセッサで並列実行するためのプログラムであることとしてもよい。
【０１９８】
このプログラム生成装置によれば、単一のプロセッサで実行するためのプログラムを参照することで、複数のプロセッサで並列実行するためのプログラムを生成できる。従って、例えばプログラマが作成した、単一のプロセッサで実行するためのプログラムが既にある場合に、わざわざ複数のプロセッサで並列実行するためのプログラムを作成しなおさなくてもよい。よって、プログラムを作成するための手間を省くことができる。
【０１９９】
（ｅ）また、前記生成手段は、Ｍ＜Ｎの場合に、生成したプログラムを前記ループ処理のＮ−Ｍ回分の処理をも行うように変更し、変更後のプログラムの処理と、前記対象ソースプログラムの処理とが、等価になるか否かを判定し、等価になる場合には、前記生成したプログラムを、当該変更後のプログラムに置き換えることとしてもよい。
【０２００】
このプログラム生成装置によれば、一旦生成した、ループ処理のＭ（Ｍ＜Ｎ）回分の処理を行うためのプログラムを、ループ処理のＮ回分の処理を行うプログラムに変更しても、その処理が、対象ソースプログラムの処理と等価であることを条件に、最終的に、ループ処理のＮ回分の処理を行うためのプログラムを生成する。
【０２０１】
このループ処理のＮ回分の処理を行うためのプログラムは、真依存の関係にある全ての対象変数の表記について、当該対象変数の表記と等価な真依存の関係のない他の変数の表記を含んだ命令文を含むプログラムである。従って、Ｎ回分のループ処理を、複数のプロセッサで独立して並列実行することで高速に実行することが可能になる。
【産業上の利用可能性】
【０２０２】
本発明に係るプログラム生成装置は、いわゆる真依存の関係を有するループ処理を含むソースプログラムを参照して、そのループ処理により実現される所定処理を複数のプロセッサで分担して並列実行するための新たなプログラムを生成するために利用される。
【符号の説明】
【０２０３】
１０    記憶装置
１１    ソースプログラム
１２    アセンブラプログラム
１３    再配置可能バイナリプログラム
１４    目的プログラム
１００    プログラム生成装置
１１０    記憶部
１２０    取得部
１３０    算出部
１３１    イタレーション展開部
１３２    みせかけ依存削除部
１３３    等価関係算出部
１４０    特定部
１５０    生成部
２１０    アセンブラ
２２０    リンカ
１０００    コンパイラシステム
【図１】
0005580416.tif 000002
【図２】
0005580416.tif 000003
【図３】
0005580416.tif 000004
【図４】
0005580416.tif 000005
【図５】
0005580416.tif 000006
【図６】
0005580416.tif 000007
【図７】
0005580416.tif 000008
【図８】
0005580416.tif 000009
【図９】
0005580416.tif 000010
【図１０】
0005580416.tif 000011
【図１１】
0005580416.tif 000012
【図１２】
0005580416.tif 000013
【図１３】
0005580416.tif 000014
【図１４】
0005580416.tif 000015
【図１５】
0005580416.tif 000016
【図１６】
0005580416.tif 000017
【図１７】
0005580416.tif 000018
【図１８】
0005580416.tif 000019
【図１９】
0005580416.tif 000020
【図２０】
0005580416.tif 000021