(57)【特許請求の範囲】
【請求項１】
高級プログラミング言語で書かれたソースプログラムを機械語プログラムやアセンブラプログラム、または高級プログラミング言語で記述されたプログラムに変換するプログラム言語処理系において、配列記述があるループを含むソースプログラムを変換するプログラム変換装置であって、
ループ中に記述されている命令文であって、第１の配列を使用する記述を有する命令文を、該命令文の中の第１の配列を第２の配列に置き換えた命令文に書き換える変数置換部と、
前記変数置換部で置き換えられる前と後のプログラムに対して、文間の依存関係を示す依存情報を算出する依存解析部と、
前記置き換えの前と後のプログラムに対して前記依存解析部で算出された依存情報を比較して、前記変数置換部で置き換えられたプログラムが正当であるか否かを判定する依存性比較部と
を備えていることを特徴とするプログラム変換装置。
【請求項２】
前記依存性比較部は、前記置き換えの前と後のプログラムに対して前記依存解析部で算出された依存情報を比較する際、真依存の増減が発生していないことが判明した場合に、前記変数置換部で置き換えられたプログラムを正当であると判定することを特徴とする請求項１記載のプログラム変換装置。
【請求項３】
前記依存性比較部は、前記置き換えの前と後のプログラムに対して前記依存解析部で算出された依存情報を比較する際、逆依存および出力依存のみの増減が発生していると判明した場合に、前記変数置換部で置き換えられたプログラムを正当であると判定することを特徴とする請求項１記載のプログラム変換装置。
【請求項４】
前記第１の配列及び前記第２の配列のうち少なくとも一方が当該ループ中で定義されていることを特徴とする請求項１から請求項３までのいずれかに記載のプログラム変換装置。
【請求項５】
高級プログラミング言語で書かれたソースプログラムを機械語プログラムやアセンブラプログラム、または高級プログラミング言語で記述されたプログラムに変換するプログラム言語処理系において、配列記述があるループを含むソースプログラムを変換するプログラム変換装置であって、
現在のプログラムを保持する置換前プログラム保持部と、
現在のプログラム中の文間の依存関係を保持する置換前依存情報保持部と、
前記置換前プログラム保持部に保持されているプログラムに対して文間の依存関係を示す依存情報を算出し、結果を前記置換前依存情報保持部に格納する置換前依存解析部と、
ループ中に存在する命令文において使用されている全ての配列の中から２個の相異なる配列を選び出した順列の個数分だけ配列どうしのペアを生成する配列ペア生成部と、
置き換えられたプログラムを保持する置換後プログラム保持部と、
前記配列ペア生成部で生成された、第１の配列と第２の配列とで構成された一つのペアを取り出し、ループ中に記述されている命令文であって、前記第１の配列を使用する記述を有する命令文を、該命令文の中の第１の配列を前記第２の配列に置き換えた命令文に書き換え、置き換えたプログラムを前記置換後プログラム保持部に格納する変数置換部と、
置き換えられたプログラムの文間の依存関係を保持する置換後依存情報保持部と、
前記置換後プログラム保持部に保持されているプログラムに対して文間の依存関係を示す依存情報を算出し、結果を前記置換後依存情報保持部に格納する置換後依存解析部と、
前記置換前依存情報保持部と前記置換後依存情報保持部に格納されている依存情報を比較して、真依存の増減が発生していない場合に、前記置換後プログラム保持部に格納されているプログラムを正当であると判定する依存性比較部と、
前記依存性比較部で正当であると判定した場合に、前記置換前プログラム保持部を前記置換後プログラム保持部に格納されているプログラムで更新し、前記置換前依存情報保持部を前記置換後依存情報保持部に格納されている依存情報で更新する更新部と、
前記配列ペア生成部で生成される全てのペアに対して、前記変数置換部による処理と、前記置換後依存解析部による処理と、前記依存性比較部による処理と、前記更新部による処理とを繰り返し、最終的な置換結果を前記置換前プログラム保持部に格納する制御部と
を備えていることを特徴とするプログラム変換装置。
【請求項６】
前記置換後依存解析部は、置換された文と置換前に依存があった文との依存関係の再算出、および、置換された文において、置換した配列の参照がある場合は、置換した配列を定義している文と置換された文との依存関係の再算出、および、置換された文において、置換した配列の定義がある場合は、置換した配列を使用している文と置換された文との依存関係の再算出を行う機能を備えていることを特徴とする請求項５記載のプログラム変換装置。
【請求項７】
高級プログラミング言語で書かれたソースプログラムを機械語プログラムやアセンブラプログラム、または高級プログラミング言語で記述されたプログラムに変換するプログラム言語処理系において、配列記述があるループを含むソースプログラムを変換するプログラム変換方法であって、
コンピュータに、
変数置換部がループ中に記述されている命令文であって、第１の配列を使用する記述を有する命令文を、該命令文の中の第１の配列を第２の配列に置き換えた命令文に書き換える変数置換ステップと、
依存解析部が前記変数置換ステップで置き換えられる前と後のプログラムに対して、文間の依存関係を示す依存情報を算出する依存解析ステップと、
依存性比較部が前記変数置換ステップによる置き換えの前と後のプログラムに対して前記依存解析ステップで算出された依存情報を比較して、前記変数置換ステップで置き換えられたプログラムが正当であるか否かを判定する依存性比較ステップと、
を実行させることを特徴とするプログラム変換方法。
【請求項８】
高級プログラミング言語で書かれたソースプログラムを機械語プログラムやアセンブラプログラム、または高級プログラミング言語で記述されたプログラムに変換するプログラム言語処理系において、配列記述があるループを含むソースプログラムを変換するプログラムを記録した記録媒体であって、
コンピュータに、
変数置換部がループ中に記述されている命令文であって、第１の配列を使用する記述を有する命令文を、該命令文の中の第１の配列を第２の配列に置き換えた命令文に書き換える変数置換ステップと、
依存解析部が前記変数置換ステップで置き換えられる前と後のプログラムに対して、文間の依存関係を示す依存情報を算出する依存解析ステップと、
依存性比較部が前記変数置換ステップによる置き換えの前と後のプログラムに対して前記依存解析ステップで算出された依存情報を比較して、前記変数置換ステップで置き換えられたプログラムが正当であるか否かを判定する依存性比較ステップと、
を実行させるプログラムを記録したコンピュータ読み取り可能なプログラム変換用の記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、高級プログラミング言語で書かれたソースプログラムを機械語プログラムやアセンブラプログラムなどの目的プログラムに翻訳するプログラム言語処理系において、配列記述があるループを含むソースプログラムを翻訳するプログラム変換装置、プログラム変換方法及び記録媒体に関する。
【０００２】
【従来の技術】
近年のパーソナルコンピュータの例のように、周波数がギガＨｚ単位のマイクロプロセッサと、数千キロバイトから数メガバイトと容量は小さいが高速動作するキャシュメモリと、数百メガバイトと大容量の主記憶を搭載するようになっている。ここで、キャシュメモリの役目はいうまでもなく、プロセッサと主記憶との間に介在し、高速動作のプロセッサと低速動作の主記憶との実行速度のギャップを埋める役目を担い、システム全体の高速実行化を図ることである。特に、プロセッサからキャッシュにアクセスしたときに、キャッシュに主記憶のデータが存在している確率（キャッシュヒット率）を上げることが重要になる。キャッシュヒット率が低いと、キャッシュを介した主記憶へのアクセスのため、かえって実行速度の低下を招いてしまうので、キャッシュヒット率の向上は重要なポイントである。
【０００３】
一方、近年急速に発展している通信、画像、文字、音声処理などのマルチメディア処理では、大量データの高速処理をする必要がある。また、そのようなマルチメディア処理を行うプログラムでは、画像データなどのように、プログラム中では配列データとして表現され、繰り返し処理されることが一般的である。
【０００４】
そこで、マルチメディア処理を高速に実行するには、配列データを可能な限りキャッシュに置き、配列データのキャッシュヒット率を上げることが必要となる。
【０００５】
配列データのキャッシュヒット率を上げる方法としては、後述の文献１の１２．７節に述べられているようなループ変換を行い、データの局所性を増加させる方法がある。
【０００６】
例えば、図１３（１）のＣ言語記述のプログラム１を図１４（１）のプログラム２に変換した場合について説明する。ここで、説明を簡単にするため、Ｎはマクロで与えられる値で、キャッシュの１ライン長、つまり主記憶から１回のアクセスでキャッシュに格納できる長さであり、かつキャッシュのサイズは２ラインとし、キャッシュはＬＲＵ（Ｌeast Ｒecently Ｕsed）方式に則った動作を行うものとする。
【０００７】
図１３（１）のプログラム１では、まず、１番目のループではキャッシュには配列ＣもＡも乗っていない（ミスヒット）ので、図１３（２）（ａ）のようにキャッシュに乗せられ、次に、２番目のループでは配列Ｂがキャッシュに乗っていないので、同図（ｂ）のように配列Ａをキャッシュから追い出し、配列Ｂをキャッシュに乗せ、３番目のループでは配列Ａがキャッシュに乗っていないので、同図（ｃ）のように配列Ｃをキャッシュから追い出し、配列Ａをキャッシュに乗せ、４番目のループでは配列Ｂがキャッシュに乗っている（ヒット）ので、特にキャッシュの状態には変化は起こらない。
【０００８】
一方、図１４（１）のプログラム２の方は、まず１番目のループの最初の文では、キャッシュには配列ＣもＡも乗っていないので、図１４（２）（ａ）のようにキャッシュに乗せられるが、次の文では配列Ａがキャッシュに乗っているのでキャッシュの状態は変化せず、次に、２番目のループでは配列Ｂがキャッシュに乗っていないので、同図（ｂ）のように配列Ａをキャッシュから追い出し、配列Ｂをキャッシュに乗せ、次の文では配列Ｂがキャッシュに乗っているので、キャッシュの状態は変化しない。
【０００９】
以上、プログラム１とプログラム１を変換したプログラム２とについて、変換後のプログラム２の方がミスヒットが少なく、キャシュヒット率が高いプログラムとなっている。
【００１０】
【発明が解決しようとする課題】
上述の方法は、ループ自体の構成を変更することによってデータの局所性を増加させる方法である。
【００１１】
ここでは、ループ自体の構成は変更せずに、変数の置換によって、データの局所性を増加させる方法を考える。
【００１２】
図１５のプログラムを例にして、課題について説明する。同図（２）は同図（１）において配列Ｂを配列Ａに置き換えたプログラムである。
【００１３】
もし、このループの後に配列Ａの参照がなく、さらにこのループの後に、このループで設定した配列Ｂの値の参照もないのであれば、同図（２）の（ａ），（ｂ）では、既に参照済みの配列Ａの要素領域を配列Ｂの代わりに使用することになるので（Ｂ[ｉ−１]→Ａ[ｉ−１]）、プログラム自体の意味を変えないということが判明する。このような変換により、ループ内における配列Ａの局所性はさらに増し、キャッシュヒット率が向上することが容易に予想される。
【００１４】
しかし、どのような条件において、このような変換が可能であるかが不明確であるため、変換できたとしても場当たり的に、ごく限られた特定の場合にしか変換できない。したがって、より適用範囲が広い一般的な変換方法を確立することが望ましい。
【００１５】
そこで本発明の目的は、上述の課題に鑑みて、従来から知られている文の依存関係の情報を利用して、どのような条件を満たす場合に上記変換が可能であるかを明確にし、かつこの変換条件を利用したプログラム変換装置、プログラム変換方法を提供することである。
【００１６】
【課題を解決するための手段】
上記目的を達成するために、本発明は、高級プログラミング言語で書かれたソースプログラムを機械語プログラムやアセンブラプログラム、または高級プログラミング言語で記述されたプログラムに変換するプログラム言語処理系において、配列記述があるループを含むソースプログラムを変換するプログラム変換装置であって、ループ中に記述されている命令文であって、第１の配列を使用する記述を有する命令文を、該命令文の中の第１の配列を第２の配列に置き換えた命令文に書き換える変数置換部と、前記変数置換部で置き換えられる前と後のプログラムに対して、文間の依存関係を示す依存情報を算出する依存解析部と、前記置き換えの前と後のプログラムに対して前記依存解析部で算出された依存情報を比較して、前記変数置換部で置き換えられたプログラムが正当であるか否かを判定する依存性比較部とを備えた構成としている。
【００１７】
この構成によれば、ループ内部の配列が他の配列に置き換えられ、置換前に比較してより少ない配列記述がループ内部に存在することとなる。その結果、置換前と比較してループ中の配列アクセスの局所性が増し、キャッシュヒット率が向上するので、プログラムの実行時間の短縮を図ることができる。
【００１８】
上記において、好ましい態様は、前記依存性比較部が、前記置き換えの前と後のプログラムに対して前記依存解析部で算出された依存情報を比較する際、真依存の増減が発生していないことが判明した場合に、前記変数置換部で置き換えられたプログラムを正当であると判定することである。
【００１９】
文と文との間の実行順序の依存関係の一つである真依存は、変数を具体的数値等で定義するもので、文の実行順序を規定するだけでなく、依存元で定義される変数の値を依存先で参照するというように、依存の原因となる変数が保持する値にも意味を持つ。これに対して、逆依存と出力依存はそのような意味はなく、単に文の実行順序のみを規定するものである。
【００２０】
変数または配列の置換の前後のプログラムの依存において、増減した依存に真依存が存在しないという条件を満たす場合には、その変数・配列の置換は正当（プログラムの意味は不変）であると判定してよい。
【００２１】
また、上記において、好ましい態様は、前記依存性比較部が、前記置き換えの前と後のプログラムに対して前記依存解析部で算出された依存情報を比較する際、逆依存および出力依存のみの増減が発生していると判明した場合に、前記変数置換部で置き換えられたプログラムを正当であると判定することである。
【００２２】
変数または配列の置換の前後のプログラムの依存において、増減した依存が逆依存、出力依存のみであるという条件を満たす場合にも、その変数・配列の置換は正当であると判定してよい。
【００２３】
また、上記において、好ましい態様は、前記第１の配列及び前記第２の配列のうち少なくとも一方が当該ループ中で定義されていることである。
【００２４】
配列をもうひとつの配列と置き換えることにより、キャッシュの推移における配列の切り換えの頻度を低減し、キャッシュヒット率を向上させることができる。
【００２５】
より具体的レベルでの構成について、好ましい態様は、次のようなものである。高級プログラミング言語で書かれたソースプログラムを機械語プログラムやアセンブラプログラム、または高級プログラミング言語で記述されたプログラムに変換するプログラム言語処理系において、配列記述があるループを含むソースプログラムを変換するプログラム変換装置を前提とする。現在のプログラムを保持する置換前プログラム保持部と、現在のプログラム中の文間の依存関係を保持する置換前依存情報保持部と、前記置換前プログラム保持部に保持されているプログラムに対して文間の依存関係を示す依存情報を算出し、結果を前記置換前依存情報保持部に格納する置換前依存解析部を備える。また、ループ中に存在する命令文において使用されている全ての配列の中から２個の相異なる配列を選び出した順列の個数分だけ配列どうしのペアを生成する配列ペア生成部と、置き換えられたプログラムを保持する置換後プログラム保持部と、前記配列ペア生成部で生成された、第１の配列と第２の配列とで構成された一つのペアを取り出し、ループ中に記述されている命令文であって、前記第１の配列を使用する記述を有する命令文を、該命令文の中の第１の配列を前記第２の配列に置き換えた命令文に書き換え、置き換えたプログラムを前記置換後プログラム保持部に格納する変数置換部を備える。前記変数置換部は、ループ中のペアの２番目の配列の記述部分をペアの１番目の配列で置き換えるのでもよい。さらに、置き換えられたプログラムの文間の依存関係を保持する置換後依存情報保持部と、前記置換後プログラム保持部に保持されているプログラムに対して文間の依存関係を示す依存情報を算出し、結果を前記置換後依存情報保持部に格納する置換後依存解析部と、前記置換前依存情報保持部と前記置換後依存情報保持部に格納されている依存情報を比較して、真依存の増減が発生していない場合に、前記置換後プログラム保持部に格納されているプログラムを正当であると判定する依存性比較部とを備える。加えて、前記依存性比較部で正当であると判定した場合に、前記置換前プログラム保持部を前記置換後プログラム保持部に格納されているプログラムで更新し、前記置換前依存情報保持部を前記置換後依存情報保持部に格納されている依存情報で更新する更新部と、前記配列ペア生成部で生成される全てのペアに対して、前記変数置換部による処理と、前記置換後依存解析部による処理と、前記依存性比較部による処理と、前記更新部による処理とを繰り返し、最終的な置換結果を前記置換前プログラム保持部に格納する制御部とを備えている。
【００２６】
尚、ここで上記各構成要素について理解を助けるために、後述する実施の形態での図３のフローチャートと対照すると、置換前依存解析部はステップａ２に相当し、配列ペア生成部はステップａ４に、置換後依存解析部はステップａ６に、更新部はステップａ９にそれぞれ相当する。もっとも、本発明は、このような対照の記述によって後述の実施の形態に限定されるものではない。
【００２７】
この場合、置換前依存解析部、配列ペア生成部、置換後依存解析部、更新部および制御部の連係により、置換の対象として可能性のある配列のペアを網羅的に抽出し置換のシミュレートを行うので、キャッシュヒット率の向上を効果的に進めることができる。
【００２８】
上記において、好ましい態様は、前記置換後依存解析部が、置換された文と置換前に依存があった文との依存関係の再算出、および、置換された文において、置換した配列の参照がある場合は、置換した配列を定義している文と置換された文との依存関係の再算出、および、置換された文において、置換した配列の定義がある場合は、置換した配列を使用している文と置換された文との依存関係の再算出を行う機能を備えていることである。
【００２９】
この場合、上記各再算出によって絞り込みを行うので、処理をより高速に進めることができる。
【００３０】
本発明はまたプログラム変換方法にかかわるものであって、次のような手段を講じることにより、上記の課題を解決する。すなわち、高級プログラミング言語で書かれたソースプログラムを機械語プログラムやアセンブラプログラム、または高級プログラミング言語で記述されたプログラムに変換するプログラム言語処理系において、配列記述があるループを含むソースプログラムを変換するプログラム変換方法であって、コンピュータに、変数置換部がループ中に記述されている命令文であって、第１の配列を使用する記述を有する命令文を、該命令文の中の第１の配列を第２の配列に置き換えた命令文に書き換える変数置換ステップと、依存解析部が前記変数置換ステップで置き換えられる前と後のプログラムに対して、文間の依存関係を示す依存情報を算出する依存解析ステップと、依存性比較部が前記変数置換ステップによる置き換えの前と後のプログラムに対して前記依存解析ステップで算出された依存情報を比較して、前記変数置換ステップで置き換えられたプログラムが正当であるか否かを判定する依存性比較ステップとを実行させる構成となっている。
【００３１】
このプログラム変換方法によれば、ループ内部の配列を他の配列に置き換え、その配列記述を置換前に比較してより少ないものにする。その結果、置換前と比較してループ中の配列アクセスの局所性が増し、キャッシュヒット率を向上させるので、プログラムの実行時間の短縮を図ることができる。
【００３２】
本発明はまたコンピュータ読み取り可能なプログラム変換用の記録媒体にかかわるものであって、高級プログラミング言語で書かれたソースプログラムを機械語プログラムやアセンブラプログラム、または高級プログラミング言語で記述されたプログラムに変換するプログラム言語処理系において、配列記述があるループを含むソースプログラムを変換するプログラムを記録した記録媒体であって、コンピュータに、変数置換部がループ中に記述されている命令文であって、第１の配列を使用する記述を有する命令文を、該命令文の中の第１の配列を第２の配列に置き換えた命令文に書き換える変数置換ステップと、依存解析部が前記変数置換ステップで置き換えられる前と後のプログラムに対して、文間の依存関係を示す依存情報を算出する依存解析ステップと、依存性比較部が前記変数置換ステップによる置き換えの前と後のプログラムに対して前記依存解析ステップで算出された依存情報を比較して、前記変数置換ステップで置き換えられたプログラムが正当であるか否かを判定する依存性比較ステップとを実行させる構成となっている。
【００３３】
この記録媒体を所要のプログラム変換装置にセットしてドライブすることにより、上記同様に、キャッシュヒット率を向上させ、プログラムの実行時間の短縮を図ることができる。
【００３４】
【発明の実施の形態】
本発明の実施の形態の説明の前に先だって、本発明に関連する文献を挙げ、以下で用いる用語について説明しておく。さらに、変数の置き換え条件について明確にする。
【００３５】
＜文献＞
１．中田：”コンパイラの構成と最適化”，  朝倉書店，  １９９９
２．Ａ．Ｖ．Ａｈｏ，  Ｒ．Ｓｅｔｈｉ，  Ｊ．Ｄ．Ｕｌｌｍａｎ：”Ｃｏｍｐｉｌｅｒｓ，Ｐｒｉｎｃｉｐｌｅ，Ｔｅｃｈｎｉｑｕｅｓ，ａｎｄ  Ｔｏｏｌ”，  Ａｄｄｉｓｏｎ  Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  ＣｏｍｐａｎｙＩｎｃ．，１９８６，  （邦訳）  原田賢一：”コンパイラＩ、ＩＩ”，サイエンス社，１９９０
３．Ｈａｎｓ  Ｚｉｍａ、他：”ｓｕｐｅｒｃｏｍｐｉｌｅｒｓ  ｆｏｒ  Ｐａｒａｌｌｅｌ  ａｎｄ  ＶｅｃｔｏｒＣｏｍｐｕｔｅｒｓ”，  Ａｄｄｉｓｏｎ  Ｗｅｓｌｅｙ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏｍｐａｎｙ  Ｉｎｃ．，１９９１、  （邦訳）村岡洋一：”スーパーコンパイラ”,オーム社, １９９５
＜用語の説明＞
・変数の定義、参照
本文では、変数の値を設定（又は更新）することを「定義する」と言い、設定した値を参照することを「参照する」と言う。また、変数を定義または参照している場所でその変数は「使用」されていると言うことにする。
【００３６】
・依存関係
依存関係は、文献３の４章で述べられているような文間の実行順序の依存関係のことである。依存には三種類の依存が存在する。真依存と逆依存と出力依存である。図４（１）のプログラム例を用いて説明する。
【００３７】
文Ｓ２では変数ａの値を参照する。この値は文Ｓ１で変数ａに代入された値１００である。この関係を文Ｓ１から文Ｓ２への「真依存」と呼ぶ。または、文Ｓ２が文Ｓ１に「真に依存する」と言う。文Ｓ１と文Ｓ２の相対的な文の順序関係（実行順序）は維持されなくてはならず、もし文Ｓ２を文Ｓ１に先行して実行すると、文Ｓ２は古い変数ａの値を参照することになってしまう。真依存を符号ｔで表す。
【００３８】
次に、文Ｓ２と文Ｓ３に着目する。文Ｓ２は変数ａのその時点での値を参照するのに対して、文Ｓ３では変数ａを定義する。この関係を文Ｓ２から文Ｓ３への「逆依存」と呼ぶ。もし文Ｓ３を文Ｓ２に先行して実行すると、文Ｓ２では文Ｓ３で定義した間違った値を参照してしまうので、文Ｓ２と文Ｓ３の相対的な文の実行順序は維持されなくてはならい。逆依存を符号ａで表す。
【００３９】
最後に、文Ｓ３と文Ｓ４に着目する。両文とも変数ａを定義する文であり、明らかに、もし文Ｓ４を文Ｓ３に先行して実行すると、文Ｓ３以降の文で間違った変数ａの値を参照してしまう可能性があり、やはり文Ｓ３と文Ｓ４の相対的な文の実行順序は維持されなくてはならい。この関係を文Ｓ３から文Ｓ４への「出力依存」と呼ぶ。出力依存を符号ｏで表す。
【００４０】
また、上記の変数ａのように依存の元となっている変数を「依存の原因となる変数」と呼ぶ。さらに、図４（２）は、同図（１）のプログラムに対して、文を節とし、依存元から依存先へ有向辺で節を結んだグラフであり、このグラフは「依存グラフ」と呼ばれている。
【００４１】
・依存の性質
上述のように、依存は特定の文の間に実行順序が存在することを意味しており、例えば、文Ｓ１から文Ｓ２への依存がある場合は、文Ｓ１は文Ｓ２の実行に先だって実行する必要があることを意味する。
【００４２】
また、三つの依存のうち真依存のみは、文の実行順序を規定するとともに、依存元で定義される変数の値を依存先で参照するというように、依存の原因となる変数が保持する値にも意味を持つ。しかし、逆依存と出力依存はそのような意味はなく、単に文の実行順序のみを規定するものである。
【００４３】
・変数置き換えプログラムの正当性
任意の二つの変数に関して、他方を一方の変数に置き換えたプログラムについて、置換後のプログラムが正当である条件について説明する。尚、ここで「正当」とは、プログラムの意味を変えないということである。
【００４４】
まず、上述の真依存の性質から、
（１）置換前に存在していた真依存が無くなる場合
この場合は、正当な値の参照ができなくなる可能性があるということなので、不当な置換である。
【００４５】
（２）置換後に真依存が増える場合
この場合も、不当な値の参照が発生する可能性があるので、不当な置換である。
【００４６】
次に、上述の逆依存の性質と、置換後のプログラム自体の文の実行順序は、置換前と同じであることから、次のことが言える。出力依存についても同様である。
【００４７】
（１）置換前に存在していた逆依存が無くなる場合
置換後プログラムの実行順序は置換前と同じであり、置換後プログラムでも依存元の文は依存先に先だって実行されるので置換は正当である。
【００４８】
（２）置換後に逆依存が増える場合
置換後プログラムの実行順序は置換前と同じであり、置換後プログラムで新たに発生した逆依存において、置換前と置換後のプログラムのどちらでも、依存元の文は依存先に先だって実行されるので、置換は正当である。
【００４９】
以上から、次の条件を満たす場合には、変数の置換は正当であると言える。
【００５０】
（条件１）
置換前後のプログラムの依存において、増減した依存が逆依存、出力依存のみであること。
【００５１】
または、
（条件２）
置換前後のプログラムの依存において、増減した依存に真依存が存在しないこと。
【００５２】
尚、上記は図４の単純な変数だけでなく、配列要素である変数に対しても同様なことが言える。なぜなら、配列要素自体は単純な変数と同等であるからである。
【００５３】
＜実施形態の説明＞
図２は本実施形態のプログラム変換装置１を含むコンパイラ２の構成図である。コンパイラ２は、ソースプログラムをコンパイラ２が処理しやすい形の中間プログラムに変換する構文解析部２１、中間プログラムから冗長な部分を取り去る最適化部２２、中間プログラム中の変数にレジスタを割り付ける資源割付部２３、変数にレジスタを割り付け済みの中間プログラムをアセンブラプログラムに変換するコード生成部２４の一般的なコンパイラを構成する主要な部分と、最適化部２２内にプログラム中の配列記載部分の置換を行うプログラム変換装置１で構成されている。
【００５４】
次に、本発明に関係のある最適化部２２の主要部分についてのみ説明し、残りの構文解析部２１、資源割付部２３とコード生成部２４に関しては、文献１，２等に示したものと同様であるので説明を省略する。また、プログラム変換装置１に関する説明は後述する。
【００５５】
最適化部２２では各種のプログラム解析を行う。この解析には、制御フロー解析、データフロー解析という作業が含まれている。制御フロー解析とはプログラム中の文の制御の流れを解析することである。データフロー解析とは、それぞれの変数がどこで定義され、どこで参照されているかや、部分式の解析などを行うことである。これらの解析結果を利用して、各種の最適化が実行される。詳細は文献１，２等に記載されているので、ここでは省略する。
【００５６】
次に、図１を用いて、主眼とするプログラム変換装置１について説明する。
【００５７】
図１は、本実施形態のプログラム変換装置１の構成を示すブロック図である。プログラム変換装置１は、プログラム変換装置全体の動作を制御する制御部１１と、命令間の依存を関係を解析する依存解析部１２と、配列の変数名を置換する変数置換部１３と、置換前後の依存の変化を比較する依存性比較部１４と、置換前プログラム保持部１５と、置換後プログラム保持部１６と、置換前依存情報保持部１７と、置換後依存情報保持部１８とにより構成されている。
【００５８】
以下、各部の動作と機能についてフローチャートと例を示しながら説明するが、説明に先だって説明で用いる図５のプログラム例について説明する。
【００５９】
図５は、Ｃ言語プログラムの一例を示している。特に、配列Ａ，Ｄ１，Ｄ２は外部変数、配列Ｂ，Ｃ１，Ｃ２は内部変数として宣言されている。また、各文の右側にある文Ｓ１，文Ｓ２，…は、説明上必要とする文の識別子である。
【００６０】
図３は、制御部１１の動作を示すフローチャートである。
【００６１】
ステップａ１では、置換前プログラム保持部１５にソースプログラムに対応する中間プログラムを格納する。
【００６２】
図５のプログラム例では、Ｃ言語の関数１個分を格納し、図５に記載されているプログラムと等価な中間プログラムが格納される。
【００６３】
ステップａ２では、依存解析部１２を起動して、置換前プログラム保持部１５に格納されているプログラムに対して依存解析処理を施し、結果の依存情報を置換前依存情報保持部１７に格納する。
【００６４】
尚、依存解析とは上述したとおり文間の依存関係を解析することである。依存の原因となる変数としては、単純な変数の他に、配列要素変数（例えばＡ［ｉ］）も考慮した文の依存解析方法が存在しており（例えば、文献３の４章）、ここではこれ以上詳しい説明は省略する。
【００６５】
上記の解析の結果、依存情報である文間の依存関係、依存の種類が求められ、依存グラフを算出することが可能となる。
【００６６】
図５のプログラム例に対しては、図６に示す依存グラフと等価な情報が、置換前依存情報保持部１７に格納される。
【００６７】
図６において、ＥＮＴとＥＸＴは便宜上の架空の文である。ＥＮＴは関数の入口を意味し、外部変数の定義が入口に存在するものとし、ＥＸＴには参照が存在するものとするためである。
【００６８】
例えば図６のＥＮＴ１は配列Ａの定義を示しているし、ＥＸＴ１は配列Ａの参照があることを示している。このようなＥＮＴ、ＥＸＴを設ける意図は、外部変数に関する依存解析処理を単純化することにある。その結果、図６の依存グラフのように、ＥＮＴ１，２，３それぞれに対し、外部変数Ａ，Ｄ１，Ｄ２の定義が存在するものとし、ＥＸＴ１，２，３にはそれぞれ参照が存在するものとして依存グラフが構成されている。例えばＥＮＴ１から文Ｓ４に向かう依存は、配列Ａを原因とする真依存である。
【００６９】
ステップａ３では、置換前プログラム保持部１５に保存されているプログラムから、ループ文またはループを構成する文の集合（つまり、ループを構成するプログラム部分である。以下、簡単化のために単にループと言うことにする）Ｌを一つ取り出し、全てのループに対してステップａ４からステップａ９を繰り返す。尚、ループがネストしている場合は、最内のループから優先して取り出す。また、ループを構成する文の集合を求める方法としては、文献２で述べられている「自然ループ」を求める方法が知られている。図５の例ではプログラムから最初のｆｏｒループが取り出される。
【００７０】
ステップａ４では、ループＬで使用している配列変数のペアを取り出し、全てのペアに対してステップａ５からステップａ９を繰り返す。ここで取り出した配列のペアを（Ｘ，Ｙ）とする。尚、ペア（Ｘ，Ｙ）とペア（Ｙ，Ｘ）は異なるペアとする。つまり、ループＬで使用している配列変数の集合から２個取り出す順列分だけのペアを作ることである。これは後述のステップａ５において、置き換えの方向を一定するためである。図５の例では、まずペア（Ｃ１，Ａ）が取り出される（文Ｓ４参照）。
【００７１】
ステップａ５では、変数置換部１３を起動し、配列Ｙの記述部分を配列Ｘで置き換える。置き換えたプログラムを置換後プログラム保持部１６に格納する。図５の例では図７のように、配列Ａの記述部分を配列Ｃ１に置き換えたプログラムと等価なものが、置換後プログラム保持部１６に格納される（文Ｓ４，Ｓ６参照）。
【００７２】
ステップａ６では、依存解析部１２を起動して、置換後プログラム保持部１６に格納されているプログラムに対して依存解析処理を施し、結果の依存情報を置換後依存情報保持部１８に格納する。図７の例では図８のような依存グラフと等価な依存情報が保持される。
【００７３】
ステップａ７では、依存性比較部１４を起動して、置換前依存情報保持部１７の内容と置換後依存情報保持部１８の内容とを比較して、真依存の増減が発生していないかを検出する。
【００７４】
ステップａ８では、依存性比較部１４で真依存の増減が発生していない場合は、ステップａ９に進み、そうでない場合はステップａ４に戻り、他のペアについて繰り返す。
【００７５】
ステップａ９では、置換後プログラム保持部１６に保持されているプログラムを置換前プログラム保持部１５に格納し、置換前プログラム保持部１５を更新し、さらに、置換後依存情報保持部１８を置換前依存情報保持部１７に格納し、置換前依存情報保持部１７を更新する。
【００７６】
次に、ステップａ４に戻り、他のペアについて繰り返す。
【００７７】
ステップａ１０では、置換前プログラム保持部１５をプログラム変換装置１の結果として出力し、終了する（フローチャート終り）。
【００７８】
引続きステップａ７からステップａ１０までの動作を例について説明する。例では、図６、図８を比較した場合、文ＥＮＴ１から文Ｓ４および文Ｓ５への真依存ｔが無くなっているので、この場合はステップａ８でステップａ４に戻ることになる。すなわち、図５のプログラムから図７のプログラムへの置換は不当ということになる。
【００７９】
次に、他のペア（Ａ，Ｃ１）に関してもステップａ６まで同様に処理され、結果、置換後プログラム保持部１６には図９に相当するプログラムが格納され、置換後依存情報保持部１８には図１０の依存グラフに相当する依存情報が保持される。図５と図９の対照で、文Ｓ４のＣ１［ｉ］がＡ［ｉ］に置換されている。
【００８０】
次に、ステップａ７からステップａ９においては、図６、図１０を比較した場合、文Ｓ４から文Ｓ１１への真依存ｔが無くなり、新たに文Ｓ４から文Ｓ６への真依存ｔが発生するので、この場合もステップａ４に戻ることになる。すなわち、図５のプログラムから図９のプログラムへの置換は不当ということになる。
【００８１】
以下同様に、ペアについて繰り返すことになるが、ここではさらにペア（Ａ，Ｂ）の場合について説明する。
【００８２】
ペア（Ａ，Ｂ）に関しても同様に処理が進められ、結果、置換後プログラム保持部１６には図１１に相当するプログラムが格納され、置換後依存情報保持部１８には図１２に相当する依存情報が保持される。図５と図１１の対照で、文Ｓ５のＢ［ｉ−１］がＡ［ｉ−１］に置換されている。
【００８３】
図６、図１２を比較した場合、新たに文Ｓ４および文Ｓ５への逆依存ａのみが発生しているが、真依存ｔの増減は無いのでステップａ９に進み、置換前プログラム保持部１５および置換前依存情報保持部１７が、図１１および図１２と等価なものに更新される。
【００８４】
以降、他のペアについても同様に処理がなされ、結果的には図１１と等価なプログラムが最初のループに対する置換結果となる。すなわち、図５のプログラムから図１１のプログラムへの置換は正当ということになる。
【００８５】
同様に、次のループに関しても同様な処理が行われるが、いずれのペアに関しても真依存ｔの増減を生じてしまうので置換は行われない。すなわち、不当となる。
【００８６】
よって、図５の例に対するプログラム変換装置１の処理結果は図１１と等価なプログラムとなり、プログラム変換装置１は処理を終了する。
【００８７】
尚、ループ内で参照のみ存在する配列変数を置換した場合は、必ず真依存ｔの増減が生じてしまうことを利用して、ステップａ４においては、参照しかない配列変数のペアは作らないか、または、ステップａ４とステップａ５の間に、後述するようなステップａ２０を置いて、ペアのチェックを行い、ステップａ５以降の処理を省略し、処理の高速化を図ってもよい。
【００８８】
ステップａ２０では、ループＬ内において配列Ｘ，Ｙの参照のみが存在する場合はステップａ４に戻り、そうでなく、配列Ｘ，Ｙの少なくともどちらかがループＬ内に定義が存在する場合には、ステップａ５に進む。
【００８９】
また、ステップａ６において置換したプログラムに対して依存解析を行うが、この際、置換された文に関係する依存関係のみの更新を行うだけでも十分である。具体的には、置換された文と置換前に依存があった文との依存関係の再算出、置換された文において置換した配列変数の参照がある場合は、置換変数を定義している文と文との依存関係の再算出、さらに置換された文において置換した配列変数の定義がある場合は、置換変数を使用している文と文との依存関係の再算出を行うだけでよい。
【００９０】
また、ステップａ８は、依存性比較部１４において、増減する依存が逆依存および出力依存のみである場合にステップａ９に進み、そうでない場合はステップａ４に戻るとしてもよい。
【００９１】
【発明の効果】
以上説明したように、本発明のプログラム変換装置、プログラム変換方法または記録媒体によれば、ループ内部の配列が他の配列に置き換えられ、置換前に比較してより少ない配列記述がループ内部に存在することとなるので、置換前と比較してループ中の配列アクセスの局所性が増し、キャッシュヒット率が向上するので、プログラムの実行時間の短縮を図ることができるという効果がある。
【図面の簡単な説明】
【図１】  本発明の実施の形態におけるプログラム変換装置の構成を示すブロック図
【図２】  本発明の実施の形態におけるプログラム変換装置を含むコンパイラの構成を示すブロック図
【図３】  本発明の実施の形態におけるプログラム変換装置の処理手順を示すフローチャート
【図４】  依存の種類を説明する図
【図５】  本発明の実施の形態において置換前のプログラムの例示図
【図６】  図５の例プログラムに対する依存グラフ
【図７】  本発明の実施の形態において置換後のプログラムの例その１の例示図
【図８】  図７の例プログラムに対する依存グラフ
【図９】  本発明の実施の形態において置換後のプログラムの例その２の例示図
【図１０】  図９の例プログラムに対する依存グラフ
【図１１】  本発明の実施の形態において置換後のプログラムの例その３の例示図
【図１２】  図１１の例プログラムに対する依存グラフ
【図１３】  従来のデータ局所性向上を説明する図
【図１４】  図１３を改善した場合を説明する図
【図１５】  課題となるデータ局所性向上を説明する図
【符号の説明】
１  プログラム変換装置
１１  制御部
１２  依存解析部
１３  変数置換部
１４  依存性比較部
１５  置換前プログラム保持部
１６  置換後プログラム保持部
１７  置換前依存情報保持部
１８  置換後依存情報保持部
２  コンパイラ
２１  構文解析部
２２  最適化部
２３  資源割付部
２４  コード生成部
【図１】
0004158849.tif 000002
【図２】
0004158849.tif 000003
【図３】
0004158849.tif 000004
【図４】
0004158849.tif 000005
【図５】
0004158849.tif 000006
【図６】
0004158849.tif 000007
【図７】
0004158849.tif 000008
【図８】
0004158849.tif 000009
【図９】
0004158849.tif 000010
【図１０】
0004158849.tif 000011
【図１１】
0004158849.tif 000012
【図１２】
0004158849.tif 000013
【図１３】
0004158849.tif 000014
【図１４】
0004158849.tif 000015
【図１５】
0004158849.tif 000016