JP4778286B2 - コンパイラ装置 - Google Patents

Description

本発明は、高級言語で記述されたソースプログラムを機械語プログラムに変換するコンパイラ装置に関し、特に、ループ処理に対して最適化を施すコンパイラ装置に関する。

近年、マルチメディア機器に搭載されるアプリケーションプログラムには、非常に高速な処理を要求されるメディア処理を多く含んでいる。このようなメディア処理中には、多数のループ処理を含み、そのループ処理は、他の処理に比べて実行時間に占める割合が大きい。そのため、そのループ処理の実行速度が、メディア処理の実行速度を左右することになる。

そのため、コンパイラの分野において、ループ処理の実行速度を向上させるために、多数のループ処理最適化技術が存在している。そのうちの一つとして「ループ不変式移動による最適化技術」が知られている（例えば、非特許文献１参照。）。

ループ不変式移動による最適化とは、ループ処理の各イタレーションの実行に全く関わらない命令を、ループ処理の外へ移動させることにより、ループ処理に含まれる命令数を減少させる最適化手法である。

例えば、ループ処理中の各イタレーションにおいて、同じレジスタへの同じ値の定義（例えば、同じレジスタへの同じ値の代入）のみを繰り返し、実質的にループ処理全体を通して、そのレジスタの値が変化しないような場合には、その命令をループ処理外へ移動させ、ループ処理全体を通して、その定義した値が保存されるような状況を作り出せばよいことになる。
中田育男著，「コンパイラの構成と最適化」，株式会社朝倉書店，１９９９年９月１５日，ｐ．２４２−２４３およびｐ．２８４−２８７

しかし、ループ処理の外に位置する命令により定義された値を、ループ処理全体を通して保持するためには、あるレジスタをループ処理全体を通じて占有しなければならない。例えば、図１（ａ）に示すような中間プログラムで記述された中間プログラム１０を考える。ここで、命令１０ａ（ｍｏｖ ｖｒ２０，５０００）は、定数５０００を仮想レジスタｖｒ２０に代入するという命令であり、命令１０ｂ（ａｄｄ ｖｒ１，ｖｒ０，ｖｒ２０）は、仮想レジスタｖｒ０に保持された値と仮想レジスタｖｒ２０に保持された値とを加算し、仮想レジスタｖｒ１に代入する命令である。

すなわち、中間プログラム１０において、命令１０ａで仮想レジスタｖｒ２０を定義して、命令１０ｂで仮想レジスタｖｒ２０を参照しているが、仮想レジスタｖｒ２０はループ処理全体を通して値５０００を保持する必要がある。このようにループ処理外で定義した値をループ処理内で参照のみを行うと、ループ処理外で定義した値をループ処理全体で保持するレジスタが必要となってくる。

図１（ｂ）は、３命令を並列実行可能なプロセッサをターゲットプロセッサとした場合に、図１（ａ）に示した中間プログラム１０に対して命令スケジューリングを行なった結果生成される中間プログラム１２を示している。また、図１（ｂ）には、中間プログラム１２と合わせて、中間プログラム１２中で使用される仮想レジスタの生存区間を示した生存区間表１４とが示されている。ここで、「生存区間」とは、仮想レジスタが定義されてから最後に参照されるまでの区間を示している。生存区間表１４に示されるように、仮想レジスタｖｒ２０は、ループ処理全体を通じて生存していることがわかる。生存区間表１４より、中間プログラム１２において必要とされるレジスタの最大数は６個であることが分かる。

命令１０ａおよび命令１０ｂのような定義および参照の位置関係が多数存在すると、ループ処理全体を通して占有されるレジスタが増加し、ループ処理中で使用できるレジスタが減少する。このため、レジスタスピル（レジスタが足りないために、演算結果を一時的にメモリに退避する処理）が発生する可能性が高くなる。また、レジスタスピルが起こらなかったとしても、保証レジスタを使用してしまうと当該保証レジスタをある関数内で利用してしまうと、その関数の最初と最後において保証レジスタが保持する値をスタックに退避／復帰させるコードを生成する。

すなわち、ループ不変式移動を行なうと、ループ処理中にレジスタスピルが発生したり、保証レジスタが保持する値をスタックに退避／復帰させるコードを実行したりするような状況を助長する傾向にある。このため、ループ処理の性能向上のために、ループ不変式移動を行なったにも関わらず、かえってレジスタスピルを発生させたり、退避／復帰コードを実行したりして性能を悪化させてしまう可能性があるという問題がある。

本発明は、上述の課題を解決するためになされたものであり、ループ処理の性能を向上させるコンパイラ装置を提供することを目的とする。

上記目的を達成するために、本発明に係るコンパイラ装置は、ループ処理を含む第１のプログラムを第２のプログラムに変換するコンパイラ装置であって、前記第１のプログラムに含まれる前記ループ処理外に位置する命令で使用される変数の生存区間の状況に基づいて、当該命令を前記ループ処理内に移動可能か否かを判定する移動判定手段と、前記移動判定手段で移動可能と判断された命令を前記ループ処理内に移動させ、中間プログラムを生成する移動実行手段と、前記中間プログラムを前記第２のプログラムに変換する変換手段とを備えることを特徴とする。

この構成によるとループ処理外に存在する命令をループ処理内に移動させることができる。このため、ループ不変式移動による最適化とは異なり、レジスタの生存区間の長さを短くすることができる。よって、ループ処理で必要とされるレジスタ数を削減することができる可能性がある。すなわち、ループ処理実行時に、ループ処理実行時に使用可能なレジスタ数を増加させることができる。よって、レジスタスピルが生じる確率を低下させることができる。また、保証レジスタを利用する確率が少なくなり、保証レジスタが保持する値をスタックに退避／復帰させるコードを実行する確率を低下させることができる。したがって、無駄にレジスタスピルを発生させたり、退避／復帰コードを実行したりしてループ処理の性能を悪化させてしまう可能性がなくなる。よって、ループ処理の性能を向上させることができる。

具体的には、前記移動判定手段は、命令を移動させた後に必要とされるレジスタ数が前記命令を移動させる前に必要とされるレジスタ数未満の場合に、前記命令を前記ループ処理内に移動可能であると判定することを特徴とする。また、前記移動判定手段は、命令を移動させた後に発生するレジスタスピルの回数が前記命令を移動させる前に発生するレジスタスピルの回数未満の場合に、前記命令を前記ループ処理内に移動可能であると判定することを特徴としてもよい。

好ましくは、前記移動判定手段は、さらに、前記ループ処理内に移動可能であると判定された命令とデータ依存関係を有する前記ループ処理外の命令に対して、当該命令を前記ループ処理内に移動可能であるか否かを判定することを特徴とする。

ループ処理中へ移動させた命令と依存関係を有する命令に対しても、再帰的にループ処理中への移動判定を行なうことができる。このため、上述のコンパイラ装置に比べ、さらにループ処理で必要とされるレジスタ数を削減できる可能性がある。よって、さらにループ処理の性能を向上させることができる。

本発明の他の局面に係るコンパイラ装置は、ループ処理を含む第１のプログラムを第２のプログラムに変換するコンパイラ装置であって、前記第１のプログラムに含まれる前記ループ処理内に位置する命令で使用される変数の生存区間の状況に応じて、当該命令に対してループ不変式移動による最適化を選択的に実行し、中間プログラムを生成するループ不変式移動手段と、前記中間プログラムを第２のプログラムに変換する変換手段とを備えることを特徴とする。好ましくは、前記ループ不変式移動手段は、命令を移動させた後に必要とされるレジスタ数が前記命令を移動させる前に必要とされるレジスタ数未満の場合に、前記命令に対してループ不変式移動による最適化を実行することを特徴とする。

ループ不変式移動を行なう際に、レジスタの必要数が少なくなるような場合にだけ、ループ不変式の移動を行なうことができる。このため、上述のコンパイラ装置と同様に、ループ処理の性能を向上させることができる。

なお、本発明は、このような特徴的な手段を備えるコンパイラ装置として実現することができるだけでなく、コンパイラ装置に含まれる特徴的な手段をステップとするコンパイル方法として実現したり、コンパイル方法に含まれる特徴的なステップをコンピュータに実行させるコンパイラとして実現したりすることもできる。そして、そのようなプログラムは、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ Ｄｉｓｃ−Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）等の記録媒体やインターネット等の通信ネットワークを介して流通させることができるのは言うまでもない。

本発明によると、ループ処理の性能を向上させるコンパイラ装置を提供することができる。

（実施の形態１）
以下、図面を参照しながら本発明の実施の形態１に係るコンパイラについて説明する。

図２は、コンパイラの構成を機能的に示したブロック図である。コンパイラ２０は、３命令を並列実行可能なプロセッサをターゲットプロセッサとし、高級言語で記述されたソースプログラムを機械語プログラムに変換するコンピュータソフトウェアであり、機能的に、構文解析部２４、一般最適化部２６、移動判定部２８、移動実行部３０、命令スケジューリング部３２、レジスタ割付部３４および出力部３６から構成される。

構文解析部２４は、入力されたＣ言語で記述されたプログラム（以下「Ｃプログラム」という。）２２の構文を一般的な手法を用いて解析し、コンパイラ２０内部で取り扱いやすい中間コードで記述された中間プログラムに変換する処理部である。

一般最適化部２６は、構文解析部２４より出力される中間プログラムに対して、従来から存在する一般的な最適化を施す処理部である。例えば、誘導変数最適化、共通部分式削除、不要コード削除およびコピー伝搬等が一般的な最適化に相当する。これらの最適化は、本願の主眼ではないため、その詳細な説明はここでは繰り返さない。

移動判定部２８は、ループ処理の外側に位置する命令をループ処理の内部に移動可能か否かを判定する処理部である。移動判定部２８の実行する処理の詳細については後述する。

移動実行部３０は、移動判定部２８において、移動可能と判断された命令をループ処理の内部に移動させる処理部である。移動実行部３０の実行する処理の詳細については後述する。

命令スケジューリング部３２は、リストスケジューリングなどの通常の並列化のための命令スケジューリング処理を実行する処理部である。

レジスタ割付部３４は、中間プログラム中の仮想レジスタのうち生存区間が互いに重なり合う仮想レジスタに対しては異なるレジスタが割り付けられるように考慮しながら、仮想レジスタを実レジスタに割り付ける処理部である。

出力部３６は、実レジスタが割り付けられた中間プログラムを機械語プログラム３８に変換して出力する処理部である。

次に、移動判定部２８が実行する処理について詳細に説明する。図３は、移動判定部２８が実行する処理のフローチャートである。

なお、上述したように、この時点で実レジスタの割付は行われておらず、無限のレジスタ資源を想定した仮想レジスタが各命令のオペランドには割り当てられているものとする。

まず、移動判定部２８は、移動を行わない現状のままの中間プログラムに対して、命令スケジューリングを行ない、この命令スケジューリング結果を結果Ａとする（Ｓ２）。

次に、移動判定部２８は、ループ処理のプリヘッダ中のすべての命令に対して、移動判定処理を繰り返す。ここで、「ループ処理のプリヘッダ」とは、ループ処理を開始する直前に実行されるループ処理外の基本ブロックで唯一のものを指している。このループ処理外の基本ブロックが複数存在する場合には、ループ処理のプリヘッダが存在しないことになるので、この移動判定処理の繰り返しは行われない。

移動判定処理においては、移動判定部２８は、まず、着目する命令をループ処理中へ移動させたとしても、プログラムの論理に矛盾を起こすことがないかをチェックする（Ｓ４）。これは、次の移動可能条件（ＭＣ）をチェックすることに相当する。

− その命令で定義される仮想レジスタはループ処理内でのみ参照されている
− その定義は唯一の定義である
− その命令は無条件実行命令である

この移動可能条件（ＭＣ）に適合しなければ（Ｓ４でＮＯ）、移動判定部２８は、その命令に対する移動判定処理を終了させる。

この移動可能条件（ＭＣ）に適合すれば（Ｓ４でＹＥＳ）、移動判定処理は継続される。すなわち、移動判定部２８は、着目する命令をループ処理中の先頭に移動させる（Ｓ６）。さらに、移動判定部２８は、命令移動後の中間プログラムに対して、命令スケジューリングを行い、その結果を結果Ｂとする（Ｓ８）。

移動判定部２８は、結果Ａおよび結果Ｂの各々について、仮想レジスタの生存区間を解析して、ループ処理内で必要なレジスタ数を算出する。その結果、必要レジスタ数について、結果Ｂの方が少なくなる場合には（Ｓ１０でＹＥＳ）、移動判定部２８は、この命令を移動可能と判定する（Ｓ１２）。ループ処理外で定義された値に対して、ループ処理内で参照のみを行う場合には、参照は、ループ処理の最終回まで行われるので、生存区間にはループ処理の全体が含まれることになる。

命令を移動可能と判定した後（Ｓ１２）または結果Ｂにおけるレジスタ必要数が結果Ａにおけるレジスタ必要数以上の場合には（Ｓ１０でＮＯ）、移動判定部２８は、命令移動処理（Ｓ６）で移動させた命令を元の位置に戻す（Ｓ１４）。移動判定部２８は、以上の移動判定処理をループ処理のプリヘッダ中のすべての命令に対して、繰返し行なう。

次に、移動実行部３０が実行する処理について詳細に説明する。図４は、移動実行部３０が実行する処理のフローチャートである。

移動実行部３０は、ループのプリヘッダ中の各命令について以下の処理を繰り返す。すなわち、移動実行部３０は、着目する命令が上述の移動判定部２８において移動可能であると判断されていれば（Ｓ２２でＹＥＳ）、ループ処理の先頭に、その着目する命令を移動させる（Ｓ２４）。移動可能であると判断されてなければ（Ｓ２２でＮＯ）、移動実行部３０は、何も処理を行わない。

次に、Ｃプログラム２２の具体例を用いて、コンパイラ２０の実行する処理について具体的に説明する。本実施の形態においては、移動判定部２８および移動実行部３０の実行する処理が特徴的な部分であるため、その部分を中心に説明を行なう。

図５は、コンパイラ２０に入力されるＣプログラム２２の一例を示す図である。構文解析部２４は、Ｃプログラム２２に対して構文解析を行ない、中間プログラムを出力する。また、一般最適化部２６は、構文解析部２４より出力された中間プログラムに対して一般的な最適化を施し、最適化後の中間プログラムを出力する。図１（ａ）は、最適化後の中間プログラム１０の一例を示す図である。

移動判定部２８は、中間プログラム１０に対して、命令スケジューリングを行なう（図３のＳ２）。図１（ｂ）の中間プログラム１２は、命令スケジューリングの結果Ａである。次に、移動判定部２８は、中間プログラム１０のループ処理のプリヘッダの各命令に対して、移動の可能性を判定する（図４のＳ４〜Ｓ１４）。すなわち、中間プログラム１０の命令１０ｃおよび命令１０ｄでそれぞれ定義されている仮想レジスタｖｒ１０および仮想レジスタｖｒ１１は、いずれもループ処理中でも定義されている。そのため、移動可能条件（ＭＣ）に適合しない。

一方、命令１０ａについては、移動可能条件（ＭＣ）に適合するので、移動判定部２８は、ループ処理中に命令１０ａを移動させる（図３のＳ６）。図６（ａ）は、命令１０ａの移動後の中間プログラム４０を示す図である。また、図６（ｂ）の中間プログラム４２は、移動判定部２８が、中間プログラム４０に対して、命令スケジューリングを行なった結果Ｂを示している（図３のＳ８）。

次に、移動判定部２８は、結果Ａ（中間プログラム１２）および結果Ｂ（中間プログラム４２）の各々について、最大レジスタ必要数を算出する（図３のＳ１０）。図１（ｂ）および図６（ｂ）に、中間プログラム１２および４２についての生存区間の解析結果である生存区間表１４および４４をそれぞれ示している。生存区間表１４によると、結果Ａにおける最大レジスタ必要数は６であるのに対して、生存区間表４４によると、結果Ｂにおける最大レジスタ必要数は５であり、結果Ｂにおいて最大レジスタ必要数が１つ削減されている。このため、移動判定部２８は、この命令１０ａを移動可能と判定する（図３のＳ１０でＹＥＳ、Ｓ１２）。

移動実行部３０においては、ループ処理のプリヘッダ中で命令１０ａのみが移動可能と判定されているため、その命令のみをループ処理先頭へ移動させる（図４のＳ２２でＹＥＳ、Ｓ２４）。その後、命令スケジューリング部３２が、命令スケジューリングを実行し、レジスタ割付部３４が、実レジスタの割り付けを行なう。最後に、出力部３６が、実レジスタが割り付けられた中間プログラムを機械語プログラム３８に変換して出力する。

その結果、図７に示すような機械語プログラム３８が生成される。なお、理解の容易のため、図７では機械語プログラム３８に対応するアセンブラプログラムを示している。図６（ｂ）の中間プログラム４２および生存区間表４４に示したように、仮想レジスタｖｒ２０と仮想レジスタｖｒ１とは生存区間の重なりがない。このため、機械語プログラム３８では、仮想レジスタｖｒ２０およびｖｒ１に共通の実レジスタｒ３が割り当てられており、機械語プログラム３８で使用されるレジスタがレジスタｒ０からレジスタｒ４までの５個で済んでいることがわかる。すなわち、ループ処理内に命令１０ａを移動させることにより、レジスタ必要数を１つ削減できていることがわかる。

以上説明したように、本実施の形態に係るコンパイラによると、ループ処理で必要とされるレジスタ数を削減することができる。このため、ループ処理実行時に、ループ処理実行時に使用可能なレジスタ数を増加させることができる。よって、レジスタスピルが生じる確率を低下させることができる。また、ループ処理の内部に命令を移動させることにより、レジスタの生存区間の長さを短くすることができる。このため、保証レジスタを利用する確率が少なくなり、保証レジスタが保持する値をスタックに退避／復帰させるコードを実行する確率を低下させることができる。したがって、無駄にレジスタスピルを発生させたり、退避／復帰コードを実行したりしてループ処理の性能を悪化させてしまう可能性がなくなる。よって、ループ処理の性能を向上させることができる。

（実施の形態２）
次に、本発明の実施の形態２に係るコンパイラについて説明する。

実施の形態２に係るコンパイラは、命令をループ処理の内部に移動可能か否かの判定方法が実施の形態１に係るコンパイラと異なる。すなわち、実施の形態１では、レジスタの必要数に基づいて、命令の移動可能性を判断していたのに対し、実施の形態２では、レジスタスピルの発生回数に基づいて、命令の移動可能性を判断している点が異なる。

コンパイラの機能的な構成は、図２に示したものと同様である。また、移動判定部２８以外の各処理部が実行する処理は、実施の形態１と同様である。このため、その詳細な説明はここでは繰り返さない。

図８は、移動判定部２８が実行する処理のフローチャートである。実施の形態２に係る移動判定部２８が実行する処理は、図３を参照して説明した実施の形態１に係る移動判定部２８が実行する処理において、Ｓ１０の処理の代わりに、Ｓ４０の処理を実行する。すなわち、移動判定部２８は、結果Ａにおいて発生するレジスタスピルの回数と、結果Ｂにおいて発生するレジスタスピルの回数とを比較する。結果Ｂにおいて発生するレジスタスピルの回数の方が小さい場合には（Ｓ４０でＹＥＳ）、移動判定部２８は、命令をループ処理内に移動させることによりレジスタスピルの発生回数を削減させることができると判断し、この命令をループ処理の内部に移動可能であるとの判定を行なう（Ｓ１２）。

その他の移動判定部２８が実行する処理については、実施の形態１で説明したものと同様であるため、その詳細な説明はここでは繰り返さない。

例えば、図５に示すＣプログラム２２をコンパイラ２０への入力とした場合について考える。また、ループ処理中で使用することができるレジスタの数は４個であると想定する。

図９は、命令１０ａをループ処理の内部に入れる前の中間プログラム５２（結果Ａ）および中間プログラム５２で使用されるレジスタの生存区間表５４を示している。また、図１０は、命令１０ａをループ処理の内部に入れた後の中間プログラム６２（結果Ｂ）および中間プログラム６２で使用されるレジスタの生存区間表６４を示している。

図９の生存区間表５４に示されるように、レジスタスピルが発生する生存区間を破線で示している。生存区間表５４より、結果Ａでは、ループ処理の１イタレーションあたり合計４回のレジスタスピルが発生していることがわかる。

一方、図１０の生存区間表６４に示されるように、結果Ｂでは、ループ処理の１イタレーションあたり合計２回のレジスタスピルが発生している。このように、結果Ｂにおいてレジスタスピルの発生回数が削減されているため（図８のＳ４０）、移動判定部２８は、命令１０ａを移動可能と判定する（図８のＳ１２）。

以上説明したように、本実施の形態に係るコンパイラ２０によると、レジスタスピルの発生回数を減少させることができる。したがって、無駄にレジスタスピルを発生させることにより、ループ処理の性能を悪化させてしまう可能性がなくなる。よって、ループ処理の性能を向上させることができる。

（実施の形態３）
次に、本発明の実施の形態３に係るコンパイラについて説明する。

実施の形態３に係るコンパイラは、実施の形態１と同様に、ループ処理を実行する際のレジスタの最大必要数に基づいて命令をループ処理の内部に移動可能か否かを判定するが、それに加えて、内部に移動させた命令とデータ依存関係を有する命令に関しても、さらにループ処理の内部に移動可能か否かを判定する点が実施の形態１と異なる。

コンパイラの機能的な構成は、図２に示したものと同様である。また、移動判定部２８以外の各処理部が実行する処理は、実施の形態１と同様である。このため、その詳細な説明はここでは繰り返さない。

図１１は、移動判定部２８が実行する処理のフローチャートである。実施の形態３に係る移動判定部２８が実行する処理は、図３を参照して説明した実施の形態１に係る移動判定部２８が実行する処理に加えて、Ｓ５２およびＳ５４の処理が加わったものである。

すなわち、移動判定部２８は、移動可能と判定された命令とデータ依存関係を有する命令が中間プログラム中にあるか否かを調べる（Ｓ５２）。その結果、移動判定部２８は、データ依存関係がある命令に対し、Ｓ４以降の処理（図１１の処理Ｘ）を再帰的に実行する。

また、移動判定部２８は、実施の形態１と異なり、結果Ａにおけるレジスタ必要数と結果Ｂにおけるレジスタ必要数とが等しい場合においても、命令を移動可能と判定する（Ｓ５０でＹＥＳ、Ｓ１２）。これは、現在着目している命令を移動させたとしても、必要レジスタ数削減しないものの、その命令とデータ依存関係にある命令を移動させることにより、必要レジスタ数を削減できる可能性もあるためである。

次に、実際のプログラム例を用いて、本実施の形態における命令の移動処理について説明する。図１２〜図１４は、命令の移動処理について説明するための図である。図１２（ａ）は、一般最適化部２６より出力される中間プログラム７０の一例を示す図である。また、図１２（ｂ）は、この中間プログラム７０に対して、移動判定部２８が命令スケジューリング処理（図１１のＳ２）を行なった結果である中間プログラム７２（結果Ａ）および生存区間表７４を示す図である。

この時点では、レジスタの最大必要数は６個である。次に、移動判定部２８が命令７０ａを移動させる。（図１１のＳ６）。図１３（ａ）は、移動後の中間プログラム８０を示す図であり、命令７０ａがループ処理の内部に移動していることが分かる。また、移動判定部２８は、中間プログラム８０に対して、スケジューリング処理を行なう（図１１のＳ８）。図１３（ｂ）は、スケジューリング処理の結果Ｂを示す中間プログラム８２および生存区間表８４を示す図である。中間プログラム８２では、生存区間表８４に示されるように、レジスタの最大必要数は中間プログラム７２におけるレジスタの最大必要数と同数の６個であるが（Ｓ５０でＹＥＳ）、移動判定部２８は、命令７０ａを移動可能と判定する。

また、移動判定部２８は、命令７０ａとデータ依存関係にある命令７０ｂに対して、同様の移動判定処理（処理Ｘ）を実行する（Ｓ５２でＹＥＳ、Ｓ５４）。図１４は、当該処理を説明するための図である。その結果、移動判定部２８は、移動可能条件ＭＣを満たす７０ｂをループ処理の先頭に移動させる（Ｓ４でＹＥＳ、Ｓ６）。図１４（ａ）は、命令７０ｂを移動させた後の中間プログラム９０を示す図である。移動判定部２８は、中間プログラム９０に対して命令スケジューリング処理を行ない、図１４（ｂ）に示す中間プログラム９２（結果Ｂ）を生成する（Ｓ８）。図１４（ｂ）に示す中間プログラム９２の生存区間表９４によると、中間プログラム９２におけるレジスタ必要数は５個であり、命令７０ｂの移動前に比べて一つ減っている（Ｓ５０でＹＥＳ）。このため、移動判定部２８は、命令７０ａとともに命令７０ｂも移動可能であるとの判定を行なう（Ｓ１２）。

以上説明したように、本実施の形態に係るコンパイラ２０によると、実施の形態１に記載の作用に加えて、ループ処理中へ移動させた命令と依存関係を有する命令に対しても、再帰的にループ処理中への移動判定を行なっている。このため、実施の形態１よりもさらにループ処理で必要とされるレジスタ数を削減できる可能性がある。よって、実施の形態１と同様に、ループ処理の性能を向上させることができる。

（実施の形態４）
次に、本発明の実施の形態４に係るコンパイラについて説明する。

実施の形態４に係るコンパイラは、命令をループ処理の内部に移動可能か否かの判定方法が上述の実施の形態と異なる。すなわち、本実施の形態では、着目する命令自体に基づいて生成されるパラメータによって、移動判定を行なう。

コンパイラの機能的な構成は、図２に示したものと同様である。また、移動判定部２８以外の各処理部が実行する処理は、実施の形態１と同様である。このため、その詳細な説明はここでは繰り返さない。

移動判定部２８が実行する処理について説明する前に、命令の「生存開始数」および「生存終了数」という言葉を定義し、それらの定義について説明する。また、命令の移動に伴う最大レジスタ必要数の変化についても説明する。

命令は、ある変数を定義し、ある変数を参照する。その命令がある変数の最初の定義を行なうものであれば、その命令から当該変数の生存区間が開始し、その命令がある変数の最後の参照を行なうものであれば、その命令で当該変数の生存区間が終了する。

すなわち、命令は、生存区間を開始させる存在、または生存区間を終了させる存在である。そこで、その命令により開始される変数の生存区間の数を「生存開始数」、終了される変数の生存区間の数を「生存終了数」と定義する。

例えば、図１５に示されるような中間プログラム１００において、ａｄｄ命令が仮想レジスタｖｒ０の最初の定義を行ない、仮想レジスタｖｒ１の最後の定義を行なうものとする。この場合、ａｄｄ命令に対する生存開始数および生存終了数はともに１となる。このように、「生存開始数＝生存終了数」なる関係を有する場合には、命令を移動させたとしても最大レジスタ必要数に影響を与えない。

次に、図１６に示すような中間プログラム１１０において、ａｄｄ命令が仮想レジスタｖｒ０の最初の定義を行ない、仮想レジスタｖｒ１およびｖｒ２の最後の定義を行なうものとする。この場合、ａｄｄ命令に対する生存開始数は１であり、生存終了数は２となる。このように、「生存開始数＜生存終了数」なる関係を有する場合には、命令をなるべく上方（図中のＩｎｓｔＢ、ＩｎｓｔＡ方向）へ移動させることにより、最大レジスタ必要数を減らせる可能性がある。ただし、厳密には、ＩｎｓｔＡおよびＩｎｓｔＢにおける生存開始数および生存終了数も考慮する必要がある。

次に、図１７に示すような中間プログラム１２０において、ａｄｄ命令が仮想レジスタｖｒ０の最初の定義のみを行ない、仮想レジスタｖｒ１については最初の定義および最後の参照のいずれをも行なわないものとする。この場合、ａｄｄ命令に対する生存開始数は１であり、生存終了数は０である。このように、「生存開始数＞生存終了数」なる関係を有する場合には、命令をなるべく下方（図中のＩｎｓｔＣ、ＩｎｓｔＤの方向）へ移動させることにより、最大レジスタ必要数を減らせる可能性がある。ただし、厳密には、ＩｎｓｔＣおよびＩｎｓｔＤの生存開始数および生存終了数も考慮する必要がある。

以上説明したように、ある命令に対する生存開始数と生存終了数とが異なる場合には、その命令を移動させることにより、最大レジスタ必要数を減らせる可能性がある。ただし、このような場合であっても、命令の移動先の位置によっては、それ以上最大レジスタ必要数を減らすことができない場合がある。

図１８を参照して、この現象について説明する。同図の中間プログラム１３０において、仮想レジスタｖｒ０はａｄｄ命令で最初に定義され、仮想レジスタｖｒ１はｓｕｂ命令で最後に参照されるものとする。このため、ａｄｄ命令に対する生存開始数は１であり、生存開始数は０であるものとする。また、ｓｕｂ命令に対する生存開始数は０であり、生存終了数は１であるものとする。このように、ａｄｄ命令に対しては「生存開始数＞生存終了数」なる関係を有する。このため、ａｄｄ命令を下方へ移動させることにより最大レジスタ必要数を減らせる可能性がある。

しかし、図１９の中間プログラム１４０に示すように、ａｄｄ命令がｓｕｂ命令よりも下方へ配置されると、仮想レジスタｖｒ１の生存区間の終了地点は、元々ｓｕｂ命令であったものがａｄｄ命令自身となる。これにより、ａｄｄ命令に対する生存開始数と生存終了数とは１となり、「生存開始数＝生存終了数」なる関係を有することとなる。

したがって、ａｄｄ命令をｓｕｂ命令よりも下方に移動させることは、最大レジスタ必要数に影響を与えないことに注意する必要がある。

図２０は、本実施の形態に係る移動判定部２８が実行する処理のフローチャートである。

移動判定部２８は、ループ処理のプリヘッダ中のすべての命令に対して、上述した移動可能条件（ＭＣ）を満たすか否かを判定し（Ｓ４でＹＥＳ）、移動可能条件（ＭＣ）を満たす命令に関して、移動判定部２８は、生存開始数を生存終了数とを算出する（Ｓ６２）。移動判定部２８は、当該命令に対して「生存開始数＞生存終了数」なる関係を有するか否かを判定し（Ｓ６４でＹＥＳ）、この関係を有する場合には、当該命令を下方に移動させることにより最大レジスタ必要数を減らせる可能性があるため、移動判定部２８は、当該命令を移動可能と判定する（Ｓ１２）。

以上のような命令の移動判定処理を行ない、生存開始数が多い命令をループ処理中に移動させることにより、ループ処理全体で生存する仮想レジスタを減らせる可能性がある。例えば、図１（ａ）の中間プログラム１０について考えると、命令１０ａに対しては、仮想レジスタｖｒ２０の生存区間を開始させるが、仮想レジスタｖｒ２０の生存区間を終了させるものは何もない。このため、命令１０ａに関しては、生存開始数＝１、生存終了数＝０となり、「生存開始数＞生存終了数」という関係を満たすため（Ｓ６４でＹＥＳ）、移動判定部２８は、この命令を移動可能と判定する（Ｓ１２）。

以上説明したように、本実施の形態に係るコンパイラ２０によると、生存開始数が生存終了数よりも大きい命令をループ処理内に移動させることにより、ループ処理で必要とされるレジスタ数を削減することができる。このため、ループ処理実行時に使用可能なレジスタ数を増加させることができる。よって、レジスタスピルが生じる確率を低下させることができる。また、ループ処理の内部に命令を移動させることにより、レジスタの生存区間の長さを短くすることができる。このため、保証レジスタを利用する確率が少なくなり、保証レジスタが保持する値をスタックに退避／復帰させるコードを実行する確率を低下させることができる。したがって、無駄にレジスタスピルを発生させたり、退避／復帰コードを実行したりしてループ処理の性能を悪化させてしまう可能性がなくなる。よって、ループ処理の性能を向上させることができる。

なお、本実施の形態では、移動判定部２８は、命令に対する生存開始数および生存終了数に基づいて、当該命令をループ処理内に移動可能か否かを判定していたが、命令に対する生存開始数および生存終了数の完全な解析が困難である場合には、各命令において定義されているレジスタの数および参照されているレジスタの数を比較することにより、近似的に生存開始数と生存終了数との比較を行うようにしてもよい。

（実施の形態５）
次に、本発明の実施の形態５に係るコンパイラについて説明する。

上述の実施の形態１〜４に係るコンパイラにおいては、命令の移動判定処理および移動実行処理を行なった後に、命令スケジューリング処理およびレジスタ割り付け処理を行なっているが、本実施の形態に係るコンパイラにおいては、命令スケジューリング処理を行なった後であって、命令スケジューリング処理を行なう前に移動判定処理および移動実行処理を行なう点が、上述の実施の形態１〜４に係るコンパイラとは異なる。

図２１は、本実施の形態に係るコンパイラの構成を機能的に示したブロック図である。コンパイラ１５０は、３命令を並列実行可能なプロセッサをターゲットプロセッサとし、高級言語で記述されたソースプログラムを機械語プログラムに変換するコンピュータソフトウェアであり、機能的に、構文解析部２４、一般最適化部２６、命令スケジューリング部３２、移動判定部１５２、移動実行部１５４、レジスタ割付部３４および出力部３６から構成される。

移動判定部１５２および移動実行部１５４以外の処理部については、実施の形態１で説明したものと同様である。このため、その詳細な説明はここでは繰り返さない。

移動判定部１５２は、命令スケジューリング部３２において命令スケジューリングが終了した中間プログラムを入力とし、ループ処理の外側に位置する命令をループ処理の内部に移動可能か否かを判定する処理部である。移動判定部１５２の実行する処理の詳細については後述する。

移動実行部１５４は、命令スケジューリング部３２において命令スケジューリングが終了した中間プログラムに含まれる命令のうち、移動判定部１５２において移動可能と判断された命令をループ処理の内部に移動させる処理部である。移動実行部１５４の実行する処理の詳細については後述する。

図２２は、移動判定部１５２が実行する処理のフローチャートである。移動判定部１５２が処理を行なう時点では、命令スケジューリング部３２による命令スケジューリング処理が終了している。このため、移動判定部２８においては、命令スケジューリング処理は行われない。すなわち、移動判定部１５２は、命令スケジューリング処理が中間プログラムのうち、ループ処理のプリヘッダ中の移動可能条件（ＭＣ）を満たす命令をループ処理中の先頭に移動させた場合に（Ｓ４、Ｓ６）、当該命令を移動させたときの最大レジスタ必要数と、移動させないときのレジスタ必要数とを比較する（Ｓ７２）。移動させたときのレジスタ必要数のほうが、移動させないときのレジスタ必要数よりも小さい場合には（Ｓ７２でＹＥＳ）、移動判定部１５２は、この命令を移動可能と判定する（Ｓ１２）。

命令を移動可能と判定した後（Ｓ１２）、または移動させたときのレジスタ必要数が移動させないときのレジスタ必要数以上の場合には（Ｓ７２でＮＯ）、移動判定部１５２は、命令移動処理（Ｓ６）で移動させた命令を元の位置に戻す（Ｓ１４）。移動判定部２８は、以上の移動判定処理をループ処理のプリヘッダ中のすべての命令に対して、繰返し行なう。

図２３は、移動実行部１５４が実行する処理のフローチャートである。移動実行部１５４が処理を行なう時点では、命令スケジューリング部３２により命令スケジューリング処理が終了している。このため、命令スケジューリング部３２は、移動可能と判断された命令を移動する際に（Ｓ８２でＹＥＳ）、当該命令とデータ依存関係を有する命令との位置を調整しながらスケジューリングを行う（Ｓ８４）。すなわち、移動実行部１５４は、データ依存関係を壊さないように、命令をループ処理内に移動させる。

以上説明したように、本実施の形態に係るコンパイラよると、命令のスケジューリングを行なった後であっても、移動可能な命令のデータ依存関係を壊さないように、当該命令をループ処理内に移動させることにより、上述の実施の形態と同様、ループ処理で必要とされるレジスタ数を削減することができる。このため、ループ処理実行時に、ループ処理実行時に使用可能なレジスタ数を増加させることができる。よって、レジスタスピルが生じる確率を低下させることができる。また、ループ処理の内部に命令を移動させることにより、レジスタの生存区間の長さを短くすることができる。このため、保証レジスタを利用する確率が少なくなり、保証レジスタが保持する値をスタックに退避／復帰させるコードを実行する確率を低下させることができる。したがって、無駄にレジスタスピルを発生させたり、退避／復帰コードを実行したりしてループ処理の性能を悪化させてしまう可能性がなくなる。よって、ループ処理の性能を向上させることができる。

（実施の形態６）
次に、本発明の実施の形態６に係るコンパイラについて説明する。

本実施の形態に係るコンパイラにおいては、命令スケジューリング処理およびレジスタ割り付け処理を行なった後に、移動判定処理および移動実行処理を行なう点が、上述の実施の形態１〜５に係るコンパイラとは異なる。

図２４は、本実施の形態に係るコンパイラの構成を機能的に示したブロック図である。コンパイラ１６０は、３命令を並列実行可能なプロセッサをターゲットプロセッサとし、高級言語で記述されたソースプログラムを機械語プログラムに変換するコンピュータソフトウェアであり、機能的に、構文解析部２４、一般最適化部２６、命令スケジューリング部３２、レジスタ割付部３４、移動判定部１５２、移動実行部１６４および出力部３６から構成される。

移動判定部１５２および移動実行部１６４以外の処理部については、実施の形態１で説明したものと同様である。また、移動実行部１５４については、実施の形態５で説明したものと同様である。このため、これらの処理部についての詳細な説明はここでは繰り返さない。

移動実行部１６４は、命令スケジューリング処理およびレジスタ割り付け処理が終了した中間プログラムに含まれる命令のうち、移動判定部１５２において移動可能と判断された命令をループ処理の内部に移動させる処理部である。以下、移動実行部１６４の実行する処理について説明する。

図２５は、移動実行部１６４の実行する処理のフローチャートである。移動実行部１６４は、ループ処理のプリヘッダに含まれる命令のうち、移動判定部１５２においてループ処理内に移動可能であると判断された命令が存在するか否かを調べる（Ｓ９２）。ループ処理内に移動可能な命令が存在する場合には（Ｓ９２でＹＥＳ）、移動実行部１６４は、当該命令をループ処理内に移動させる（Ｓ９４）。また、移動実行部１６４は、命令の移動を行なうことにより、生存区間の重なりが解消されたレジスタについて、再度レジスタ割付を行う（Ｓ９６）。この処理により、移動実行部１６４は、使用されるレジスタの数を減少させる（Ｓ９６）。

図２６は、移動に伴うレジスタ数の減少について説明するための図である。図２６（ａ）は、移動実行部１６４による処理が実行される前の中間プログラム１７０の一例を示す図であり、図２６（ｂ）は、移動実行部１６４による処理が実行された後の中間プログラム１７６の一例を示す図である。

図２６では、中間プログラム１７０に含まれるｍｏｖ命令１７２をループ処理内に移動させる場合を示しているが、中間プログラム１７０においては、レジスタｒ３とレジスタｒ５との生存区間の重なりがあるが、ｍｏｖ命令１７２をループ処理内に移動させることにより、レジスタｒ３とレジスタｒ５との生存区間の重なりが解消する。そのため、レジスタｒ５をレジスタｒ３に最割付することができる。すなわち、中間プログラム１７０のｍｏｖ命令１７２とａｄｄ命令１７４とが、それぞれ中間プログラム１７６のｍｏｖ命令１７８とａｄｄ命令１８０とに変更されており、レジスタを１つ減らすことができる。

以上説明したように、本実施の形態に係るコンパイラよると、命令スケジューリング処理およびレジスタ割り付け処理が終了した後であっても、命令をループ処理内に移動させることにより、上述の実施の形態と同様、ループ処理で必要とされるレジスタ数を削減することができる。また、レジスタの生存区間の重なりが解消された場合にも、使用されるレジスタ数を削減することができる。

このため、ループ処理実行時に、ループ処理実行時に使用可能なレジスタ数を増加させることができる。よって、レジスタスピルが生じる確率を低下させることができる。また、ループ処理の内部に命令を移動させることにより、レジスタの生存区間の長さを短くすることができる。このため、保証レジスタを利用する確率が少なくなり、保証レジスタが保持する値をスタックに退避／復帰させるコードを実行する確率を低下させることができる。したがって、無駄にレジスタスピルを発生させたり、退避／復帰コードを実行したりしてループ処理の性能を悪化させてしまう可能性がなくなる。よって、ループ処理の性能を向上させることができる。

以上、本発明の実施の形態に係るコンパイラについて説明したが、本発明は、これらの実施の形態に限定されるものではない。

例えば、実施の形態３の移動判定部２８は、ループ内部に移動させた命令とデータ依存関係を有する命令について、レジスタの必要数に基づいて命令がループ処理内に移動可能か否かを判定したが、他の実施の形態で説明した命令の移動判定方法に従い命令がループ処理内に移動可能か否かを再帰的に判定するようにしてもよい。

また、上述の実施の形態では、命令スケジューリング部３２が命令スケジューリング処理を実行した後に、レジスタ割付部３４がレジスタ割り付け処理を実行しているが、レジスタ割り付け処理を行なった後に、命令スケジューリング処理を行うようにしてもよい。また、命令スケジューリング処理またはレジスタ割り付け処理が複数回行なわれてもよい。

また、ループ処理中でソフトウェアパイプライニングなど、複数のイタレーション実行が重なるような最適化が行われていても、同様に命令の移動判定処理および移動実行処理が可能である。

さらに、移動判定時に命令を探索する場所は、ループ処理のプリヘッダに限られず、当該ループ処理へ到達する定義が唯一であればその命令をループ処理の移動判定対象となりうる。

さらにまた、複数にネストしたループ処理に対しては、なるべく内側のループ処理、好ましくは最内ループ処理にまで到達できるように、命令の移動判定処理および移動実行処理を繰り返し実行してもよい。図２７は、ネストとしたループ処理に対する命令の移動判定処理および移動実行処理について説明するための図である。図２７（ａ）に示すように２重にネストしたループ処理を含む中間プログラム１９０について考える。すなわち、中間プログラム１９０では、最外ループ処理（ラベルＬ００００２で示されたループ処理）に最内ループ処理（ラベルＬ００００１で示されたループ処理）がネストした２重ループ構造を有する。コンパイラは、この中間プログラム１９０において、最外ループ処理のプリヘッダとなっているｍｏｖ命令１９２が、最外ループ処理の内部に移動可能か否かを判定し、移動可能な場合には、最外ループ処理の内部であって、最内ループ処理の外部に移動させる。さらに、コンパイラは、ｍｏｖ命令１９２を最大ループ処理の内部に移動可能か否かを判定し、移動可能な場合には、最内ループ処理の内部に移動させる。図２７（ｂ）は、ｍｏｖ命令１９２を最内ループ処理の内部に移動させた後の中間プログラム１９４の一例を示した図である。

また、コンパイラは、移動可能条件（ＭＣ）を以下のように拡張してもよい。すなわち、命令における定義が唯一でなくても、他の定義が、当該命令のプリヘッダ以降に存在するか、ループ処理内に存在しない場合には、その定義は唯一の定義であるとみなして移動可能条件（ＭＣ）を拡張してもよい。

さらにまた、上述の実施の形態においては、レジスタ資源に着目して、命令の移動判定処理を行なったが、条件フラグのような記憶資源に基づいて、命令の移動判定処理を行うようにしてもよい。

また、上述の実施の形態で説明した最適化処理は、ユーザによるコンパイラに対する指示に基づいて実施されるようにしてもよい。すなわち、コンパイラオプションやプラグマを用いて、コンパイラに対して最適化処理の指示を行なうことができる。

図２８は、コンパイラに対する最適化処理の指示について説明するための図である。
図２８（ａ）は、コンパイラに対して、命令移動によるループ処理の最適化処理を実行するように指示するプラグマ「#pragma invariant_reverse」を含むソースプログラムの一例を示す図である。コンパイラは、ソースプログラム２００において、プラグマ「#pragma invariant_reverse」で指定されるｆｏｒループを対象として、上述した命令移動によるループ処理の最適化処理を実行する。

図２８（ｂ）は、コンパイラに対して、命令移動によるループ処理の最適化処理を実行しないように指示するプラグマ「#pragma invariant_reverse_off」を含むソースプログラムの一例を示す図である。コンパイラは、ソースプログラム２０２において、プラグマ「#pragma invariant_reverse_off」で指定されるｆｏｒループに対しては、上述した命令移動によるループ処理の最適化処理は実行しない。

図２８（ｃ）は、コンパイラに対して、命令移動によるループ処理の最適化処理を実行するように指示するコンパイルオプション「-invariant_reverse」を示す図である。すなわち、ユーザは、ソースプログラムのコンパイル時に、コマンドライン上でコンパイラを起動させるための命令「cc」と、ソースプログラムのファイル名「test.c」とを入力するが、それと合わせてコンパイルオプション「-invariant_reverse」を入力することができる。これにより、コンパイラは、ファイル名「test.c」のソースプログラムに含まれるループ処理を対象として、上述した命令移動によるループ処理の最適化処理を実行する。

図２８（ｄ）は、コンパイラに対して、命令移動によるループ処理の最適化処理を実行しないように指示するコンパイルオプション「-invariant_reverse_off」を示す図である。すなわち、ユーザは、ソースプログラムのコンパイル時に、コマンドライン上でコンパイラを起動させるための命令「cc」と、ソースプログラムのファイル名「test.c」とを入力するが、それと合わせてコンパイルオプション「-invariant_reverse_off」を入力することができる。これにより、コンパイラは、ファイル名「test.c」のソースプログラムに含まれるループ処理に対しては、上述した命令移動によるループ処理の最適化処理を実行しない。

図２８（ａ）に示したプラグマまたは図２８（ｃ）に示したコンパイルオプションを使用することにより、コンパイラは、レジスタ数を削減することができるような機械語プログラムを生成することができる。

一方、図２８（ｂ）に示したプラグマまたは図２８（ｄ）に示したコンパイルオプションを使用することにより、コンパイラは、ループ処理中で実行する命令の数を減少させた機械語プログラムを生成することができる。このため、このようなコンパイラに対する指示は、機械語プログラム実行時の低消費電力化の要望がある場合に有効である。

なお、図２８（ｅ）は、コンパイラに対して、低消費電力実行可能な機械語プログラムを生成するよう指示するコンパイルオプション「-low_power_mode」を示す図である。すなわち、ユーザは、ソースプログラムのコンパイル時に、コマンドライン上でコンパイラを起動させるための命令「cc」と、ソースプログラムのファイル名「test.c」とを入力するが、それと合わせてコンパイルオプション「-low_power_mode」を入力することができる。これにより、コンパイラは、図２８（ｄ）のコンパイルオプションによる指定が行なわれた場合と同様、命令移動によるループ処理の最適化を行なわない。このように、図２８（ａ）〜図２８（ｄ）に示すように、コンパイラに対して直接的にループ処理の最適化を指示したり指示しなかったりするのではなく、図２８（ｅ）に示すように、コンパイラに対して間接的にループ処理の最適化を指示したり指示しなかったりすることもできる。

また、移動判定部２８は、命令をループ処理の内部に入れる前の命令スケジューリング後の中間プログラム（上述の結果Ａ）のループ処理の実行サイクル数と命令をループ処理の内部に入れた後の中間プログラム（上述の結果Ｂ）のループ処理の実行サイクル数とを比較することにより、命令をループ処理内に移動可能か否かを判定するようにしてもよい。

さらに、通常のループ不変式のループ処理外への移動の最適化の際に、上述の実施の形態で説明したように、レジスタ（仮想レジスタを含む）の生存区間の状況に応じて、移動判断を行うようにしてもよい。

図２９は、ループ不変式移動による最適化を行なうコンパイラの構成の一例を機能的に示すブロック図である。コンパイラ２１０は、高級言語で記述されたソースプログラムを機械語プログラムに変換するコンピュータソフトウェアであり、機能的に、構文解析部２４、一般最適化部２６、ループ不変式移動部２１２、命令スケジューリング部３２、レジスタ割付部３４および出力部３６から構成される。

ループ不変式移動部２１２以外の処理部については、実施の形態１で説明したものと同様である。このため、それらの処理部については説明を繰り返さない。ループ不変式移動部２１２は、中間プログラムに対して、ループ不変式移動による最適化を行なう処理部である。

図３０は、ループ不変式移動部２１２の実行する処理のフローチャートである。
ループ不変式移動部２１２は、入力された中間プログラムに対して命令スケジューリングを行ない、このスケジューリング結果を結果Ａとする（Ｓ２）。次に、ループ不変式移動部２１２はループ処理中に含まれるすべての命令に対して以下の処理を繰り返す。すなわち、ループ不変式移動部２１２は、着目している命令がループ処理外への移動可能条件を満たしているか否かについて判断する（Ｓ１０２）。この移動可能条件は、周知の技術であるため、ここでは、その詳細な説明は繰り返さない。移動可能条件を満たす場合には（Ｓ１０２でＹＥＳ）、ループ不変式移動部２１２は、当該命令をループ処理の外に移動させる（Ｓ１０４）。次に、ループ不変式移動部２１２は、命令を移動させた後の中間プログラムに対して命令スケジューリングを行ない、この命令スケジューリング結果を結果Ｂとする（Ｓ８）。その後、ループ不変式移動部２１２は、結果Ｂで必要とされるレジスタ数が結果Ａで必要とされるレジスタ数以上の場合には（Ｓ１０６でＮＯ）、命令をループ処理外へ移動させたとしても、必要レジスタ数が減少しない。このため、ループ不変式移動部２１２は、命令移動処理（Ｓ１０４）において、ループ外に移動させた命令を元の位置に戻す（Ｓ１４）。

以上のような処理を行なうことにより、ループ不変式移動を行なう際に、レジスタの必要数が少なくなるような場合にだけ、ループ不変式の移動を行なうことができる。なお、ループ不変式移動を行なうか否かの判断は、レジスタ必要数の比較に限られず、上述の実施の形態で説明したような方法、例えばレジスタスピルの比較等により行ってもよい。

さらにまた、上述の様々なコンパイラの入力プログラムは、Ｃプログラムに限られず、他の高級言語で記述されたプログラムであってもよいし、アセンブラプログラムそのものを入力とするものであってもよい。

また、コンパイラの出力は機械語プログラムに限られず、アセンブラプログラムを出力するものであってもよい。

また、本説明の実施の形態では、コンパイラ関する説明のみを行ったが、もちろん、アセンブラやリンカとの結合ツールとして使用されてもよい。

本発明は、コンパイラ等に適用でき、特にループ処理を含むプログラムを入力とするコンパイラ等に適用できる。

中間プログラムおよび仮想レジスタの生存区間の一例を示す図である。 本発明の実施の形態１に係るコンパイラの構成を機能的に示したブロック図である。 移動判定部が実行する処理のフローチャートである。 移動実行部が実行する処理のフローチャートである。 コンパイラに入力されるＣプログラムの一例を示す図である。 （ａ）はループ処理外の命令をループ処理内に移動させた後の中間プログラムを示す図であり、（ｂ）は、（ａ）の中間プログラムに対して命令スケジューリングを行なった結果と仮想レジスタの生存区間とを示す図である。 コンパイラにより生成される機械語プログラムに対応するアセンブラプログラムを示す図である。 実施の形態２に係る移動判定部が実行する処理のフローチャートである。 命令をループ処理の内部に入れる前の中間プログラムおよび中間プログラムで使用されるレジスタの生存区間表の一例を示す図である。 命令をループ処理の内部に入れた後の中間プログラムおよび中間プログラムで使用されるレジスタの生存区間表の一例を示す図である。 実施の形態３に係る移動判定部が実行する処理のフローチャートである。 命令の移動処理について説明するための図である。 命令の移動処理について説明するための図である。 命令の移動処理について説明するための図である。 生存開始数および生存終了数について説明するための図である。 生存開始数および生存終了数について説明するための図である。 生存開始数および生存終了数について説明するための図である。 生存開始数および生存終了数について説明するための図である。 生存開始数および生存終了数について説明するための図である。 実施の形態４に係る移動判定部が実行する処理のフローチャートである。 実施の形態５に係るコンパイラの構成を機能的に示したブロック図である。 実施の形態５に係る移動判定部が実行する処理のフローチャートである。 実施の形態５に係る移動実行部が実行する処理のフローチャートである。 実施の形態６に係るコンパイラの構成を機能的に示したブロック図である。 実施の形態６に係る移動実行部の実行する処理のフローチャートである。 移動に伴うレジスタ数の減少について説明するための図である。 ネストとしたループ処理に対する命令の移動判定処理および移動実行処理について説明するための図である。 コンパイラに対する最適化処理の指示について説明するための図である。 ループ不変式移動による最適化を行なうコンパイラの構成の一例を機能的に示すブロック図である。 ループ不変式移動部の実行する処理のフローチャートである。

符号の説明

２０，１５０，１６０，２１０ コンパイラ
２２ Ｃプログラム
２４ 構文解析部
２６ 一般最適化部
２８，１５２ 移動判定部
３０，１５４，１６４ 移動実行部
３２ 命令スケジューリング部
３４ レジスタ割付部
３６ 出力部
３８ 機械語プログラム

Claims (10)

1. ループ処理を含む第１のプログラムを第２のプログラムに変換するコンパイラ装置であって、
   前記第１のプログラムに含まれる前記ループ処理外に位置する命令で使用される変数の生存区間を解析し、命令により生存区間が開始する変数の数である生存開始数が前記命令により生存区間が終了する変数の数である生存終了数よりも大きい場合に当該命令を前記ループ処理内に移動可能であると判定する移動判定手段と、
   前記移動判定手段で移動可能と判断された命令を前記ループ処理内に移動させ、中間プログラムを生成する移動実行手段と、
   前記中間プログラムを前記第２のプログラムに変換する変換手段と
   を備えることを特徴とするコンパイラ装置。
2. 前記移動実行手段は、さらに、前記移動判定手段で移動可能と判断された第１の命令を前記ループ処理内に移動させるに際し、当該第１の命令とデータ依存関係にある第２の命令を前記データ依存関係を壊さない位置に移動させる
   ことを特徴とする請求項１に記載のコンパイラ装置。
3. 前記移動実行手段は、さらに、前記移動判定手段で移動可能と判断された命令を前記ループ処理内に移動させた後に、当該命令で使用されている第１のレジスタとの生存区間の重なりが解消された第２のレジスタが存在する場合には、当該第２のレジスタを他のレジスタに再割付する
   ことを特徴とする請求項１に記載のコンパイラ装置。
4. さらに、命令の移動を行なうか否かに関する指示を取得する指示取得手段を備え、
   前記移動判定手段は、さらに、前記指示取得手段が前記命令の移動を行なわないとする指示を取得した場合には、命令をループ処理内に移動可能か否かの判定を行なわない
   ことを特徴とする請求項１〜３のいずれか１項に記載のコンパイラ装置。
5. さらに、命令の移動を行なうか否かに関する指示を取得する指示取得手段を備え、
   前記移動判定手段は、さらに、前記指示取得手段が前記命令の移動を行なうとする指示を取得した場合には、命令をループ処理内に移動可能か否かの判定を行なう
   ことを特徴とする請求項１〜３のいずれか１項に記載のコンパイラ装置。
6. さらに、低消費電力向けの第２のプログラムに変換するか否かに関する指示を取得する指示取得手段を備え、
   前記移動判定手段は、さらに、前記指示取得手段が低消費電力向けの第２のプログラムに変換するとする指示を取得した場合には、命令をループ処理内に移動可能か否かの判定を行なわない
   ことを特徴とする請求項１〜３のいずれか１項に記載のコンパイラ装置。
7. 前記指示は、自身の起動時に与えられるコンパイルオプションである
   ことを特徴とする請求項４〜６のいずれか１項に記載のコンパイラ装置。
8. 前記指示は、前記第１のプログラム中に記述されているプラグマ記述である
   ことを特徴とする請求項４〜６のいずれか１項に記載のコンパイラ装置。
9. ループ処理を含む第１のプログラムを第２のプログラムに変換するコンパイル方法であって、
   前記第１のプログラムに含まれる前記ループ処理外に位置する命令で使用される変数の生存区間を解析し、命令により生存区間が開始する変数の数である生存開始数が前記命令により生存区間が終了する変数の数である生存終了数よりも大きい場合に当該命令を前記ループ処理内に移動可能であると判定する移動判定ステップと、
   前記移動判定ステップで移動可能と判断された命令を前記ループ処理内に移動させ、中間プログラムを生成する移動実行ステップと、
   前記中間プログラムを前記第２のプログラムに変換する変換ステップと
   を含むことを特徴とするコンパイル方法。
10. ループ処理を含む第１のプログラムを第２のプログラムに変換するコンパイラであって、
    前記第１のプログラムに含まれる前記ループ処理外に位置する命令で使用される変数の生存区間を解析し、命令により生存区間が開始する変数の数である生存開始数が前記命令により生存区間が終了する変数の数である生存終了数よりも大きい場合に当該命令を前記ループ処理内に移動可能であると判定する移動判定ステップと、
    前記移動判定ステップで移動可能と判断された命令を前記ループ処理内に移動させ、中間プログラムを生成する移動実行ステップと、
    前記中間プログラムを前記第２のプログラムに変換する変換ステップとをコンピュータに実行させる
    ことを特徴とするコンパイラ。

Images