(57)【特許請求の範囲】
【請求項１】
ループとその他の部分からなるプログラムを入力して、
前記ループおよびその他の部分に基づいて前記プログラムの各変数に第１の優先度を与
え、第１の優先度の高い順に所定数の前記変数（第１の変数）にグローバルレジスタを、
残りの前記変数（第２の変数）に非グローバルレジスタを割り当てる割り当て（第１の割
り当て）を行い、
前記ループ部分に基づいて各前記変数に第２の優先度を与え、前記第２の変数のうち、
前記第２の優先度が、何れかの前記第１の変数の前記第２の優先度より高い何れかの変数
（第４の変数）に、前記第１の変数のうち、前記第２の優先度が、前記第４の変数の前記
第２の優先度より低い何れかの変数（第３の変数）に割り当てた前記グローバルレジスタ
を割り当て直した割り当て（第２の割り当て）を行い、
前記ループ部分からは前記第２の割り当てに従ったコードを、前記他の部分からは前記
第１の割り当てに従ったコードを生成するレジスタ割り当て部を備えるコンパイル装置。
【請求項２】
前記コードの前記ループ部分の入り口に前記第４の変数のスピル命令を挿入する前記レジ
スタ割り当て部と
前記コードの並べ替えを行うコードスケジューラを備える請求項１のコンパイル装置。
【請求項３】
前記レジスタ割り当て部は、前記ループにおいて、前記変数の定義箇所と参照箇所の間の
呼び出し命令の数が多いほど、高い前記第２の優先度を前記変数に与える請求項１または
２のコンパイル装置。
【請求項４】
前記レジスタ割り当て部は、前記ループにおいて、前記変数の定義または参照がある場合
に無い場合より、高い前記第２の優先度を前記変数に与える請求項１乃至３の何れかのコ
ンパイル装置。
【請求項５】
前記レジスタ割り当て部は、前記第２の変数の定義箇所と参照箇所の間に呼び出し命令が
存在する基本ブロックの入り口で、前記第２の変数のスピル命令を前記コードに挿入する
請求項１乃至４の何れかのコンパイル装置。
【請求項６】
前記レジスタ割り当て部は、前記ループおよびその他の部分において、前記変数の定義箇
所と参照箇所の間の呼び出し命令の数が多いほど、前記変数の定義箇所または参照箇所を
含むループ回数が多いほど、高い前記第１の優先度を前記変数に与える請求項１乃至５の
何れかのコンパイル装置。
【請求項７】
前記プログラムのソースを入力して構文解析を行い、第１の中間言語を出力するフロント
エンドと、
前記第１の中間言語を入力して共通処理削除を行い、第２の中間言語を出力する最適化
部と、
前記第２の中間言語を入力して、第３の中間言語形式プログラムを前記コードとして出
力する前記レジスタ割り当て部と、
前記コードスケジューラと、
前記第３の中間言語形式プログラムを入力してオブジェクトを出力する出力部を備える
、請求項１乃至６の何れかのコンパイル装置。
【請求項８】
コンピュータに、
ループとその他の部分からなるプログラムを入力して、
前記ループおよびその他の部分に基づいて前記プログラムの各変数に第１の優先度を与
え、第１の優先度の高い順に所定数の前記変数（第１の変数）にグローバルレジスタを、残りの前記変数（第２の変数）に非グローバルレジスタを割り当てる割り当て（第１の割
り当て）を行い、
前記ループ部分に基づいて各前記変数に第２の優先度を与え、前記第２の変数のうち、
前記第２の優先度が、何れかの前記第１の変数の前記第２の優先度より高い何れかの変数
（第４の変数）に、前記第１の変数のうち、前記第２の優先度が、前記第４の変数の前記
第２の優先度より低い何れかの変数（第３の変数）に割り当てた前記グローバルレジスタ
を割り当て直した割り当て（第２の割り当て）を行い、
前記ループ部分からは前記第２の割り当てに従ったコードを、前記他の部分からは前記
第１の割り当てに従ったコードを生成するレジスタ割り当てを実行させるコンパイラ。
【請求項９】
前記コンピュータに、
前記コードの前記ループ部分の入り口に前記第４の変数のスピル命令を挿入する前記レ
ジスタ割り当て処理と
前記コードの並べ替えを行うコードスケジュール処理を実行させる請求項８のコンパイ
ラ。
【請求項１０】
前記コンピュータに、
前記ループにおいて、前記変数の定義箇所と参照箇所の間の呼び出し命令の数が多いほ
ど、高い前記第２の優先度を前記変数に与える前記レジスタ割り当て処理を実行させる請
求項８または９のコンパイラ。
【請求項１１】
前記コンピュータに、
前記ループにおいて、前記変数の定義または参照がある場合に無い場合より、高い前記
第２の優先度を前記変数に与える前記レジスタ割り当て処理を実行させる請求項８乃至１
０の何れかのコンパイラ。
【請求項１２】
前記コンピュータに、
前記第２の変数の定義箇所と参照箇所の間に呼び出し命令が存在する基本ブロックの入り
口で、前記第２の変数のスピル命令を前記コードに挿入する前記レジスタ割り当て処理を
実行させる請求項８乃至１１の何れかのコンパイラ。
【請求項１３】
前記コンピュータに、
前記ループおよびその他の部分において、前記変数の定義箇所と参照箇所の間の呼び出し
命令の数が多いほど、前記変数の定義箇所または参照箇所を含むループ回数が多いほど、
高い前記第１の優先度を前記変数に与える前記レジスタ割り当て処理を実行させる請求項
８乃至１２の何れかのコンパイラ。
【請求項１４】
前記コンピュータに、
前記プログラムのソースを入力して構文解析を行い、第１の中間言語を出力するフロン
トエンド処理と、
前記第１の中間言語を入力して共通処理削除を行い、第２の中間言語を出力する最適化
処理と、
前記第２の中間言語を入力して、第３の中間言語形式プログラムを前記コードとして出
力する前記レジスタ割り当て処理と、
前記コードスケジュール処理と、
前記第３の中間言語形式プログラムを入力してオブジェクトを出力する出力処理を実行
させる請求項８乃至１３の何れかのコンパイラ。
【請求項１５】
コンピュータが、
ループとその他の部分からなるプログラムを入力して、  前記ループおよびその他の部分に基づいて前記プログラムの各変数に第１の優先度を与
え、第１の優先度の高い順に所定数の前記変数（第１の変数）にグローバルレジスタを、
残りの前記変数（第２の変数）に非グローバルレジスタを割り当てる割り当て（第１の割
り当て）を行い、
前記ループ部分に基づいて各前記変数に第２の優先度を与え、前記第２の変数のうち、
前記第２の優先度が、何れかの前記第１の変数の前記第２の優先度より高い何れかの変数
（第４の変数）に、前記第１の変数のうち、前記第２の優先度が、前記第４の変数の前記
第２の優先度より低い何れかの変数（第３の変数）に割り当てた前記グローバルレジスタ
を割り当て直した割り当て（第２の割り当て）を行い、
前記ループ部分からは前記第２の割り当てに従ったコードを、前記他の部分からは前記
第１の割り当てに従ったコードを生成するレジスタ割り当て行程を有するコンパイル方法
。
【請求項１６】
前記コンピュータが、
前記コードの前記ループ部分の入り口に前記第４の変数のスピル命令を挿入する前記レ
ジスタ割り当て行程と
前記コードの並べ替えを行うコードスケジュール行程を有する請求項１５のコンパイル
方法。
【請求項１７】
前記コンピュータが、
前記ループにおいて、前記変数の定義箇所と参照箇所の間の呼び出し命令の数が多いほ
ど、高い前記第２の優先度を前記変数に与える前記レジスタ割り当て行程を有する請求項
１５または１６のコンパイル方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンパイル装置、コンパイラ、コンパイル方法に関する。
【背景技術】
【０００２】
特許文献１には、変数に一つの優先度を付与し、当該優先度に基づいて変数をレジスタに割り当てるコンパイラが記載されている。
【０００３】
特許文献２には、ループ内の命令で使用される変数のレジスタ割り当てが終了した後に、ループの入り口及び出口で値の保証が必要な変数へのレジスタ割り当てを、変数の一の優先度に従って行うコンパイラが記載されている。
【０００４】
特許文献３には、状態グラフに基づいて、スピルコード挿入位置を特定するコンパイル装置が記載されている。
【０００５】
特許文献４には、プログラムを所定命令数毎に区間分割し、変数の各区間の出現状態に基づいて各区間の優先度を決定するコンパイル装置が記載されている。このコンパイル装置は、当該優先度に基づいて、当該区間のレジスタ割り当てを決定する。
【０００６】
特許文献５には、レジスタ割り付け後に、命令スケジューリングをするコンパイル処理装置が記載されている。
【０００７】
【特許文献１】特開２００４−２１３３６号公報
【特許文献２】特開２００４−２１３４４号公報
【特許文献３】特開２００４−２２７０２５号公報
【特許文献４】特開平６−２１４８０２号公報
【特許文献５】特開平７−２３４７９２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上述の技術は、ループおよびその他の部分からなるプログラムの変数へのレジスタ割り当てに於いて、「ループおよびその他の部分」（全体）、に基づく変数の優先度に従った割り当てを、「ループ」（局所）に基づく優先度を考慮して変更するものではない。したがって、プログラム全体の最適化と局所的な最適化の調和を取った最適化ができないという課題があった。
【０００９】
本発明の目的は、上述した課題を解決するための、コンパイル装置、コンパイラ、コンパイル方法を提供することにある。
【課題を解決するための手段】
【００１０】
本発明の一実施形態のコンパイル装置は、ループとその他の部分からなるプログラムを入力して、前記ループおよびその他の部分に基づいて前記プログラムの各変数に第１の優先度を与え、第１の優先度の高い順に所定数の前記変数（第１の変数）にグローバルレジスタを、残りの前記変数（第２の変数）に否グローバルレジスタを割り当てる割り当て（第１の割り当て）を行い、前記ループ部分に基づいて各前記変数に第２の優先度を与え、前記第２の変数のうち、前記第２の優先度が、何れかの前記第１の変数の前記第２の優先度より高い何れかの変数（第４の変数）に、前記第１の変数のうち、前記第２の優先度が、前記第４の変数の前記第２の優先度より低い何れかの変数（第３の変数）に割り当てた前記グローバルレジスタを割り当て直した割り当て（第２の割り当て）を行い、前記ループ部分からは前記第２の割り当てに従ったコードを、前記他の部分からは前記第１の割り当てに従ったコードを生成するレジスタ割り当て部を備える。
【００１１】
本発明の一実施形態のコンパイラは、コンピュータに、ループとその他の部分からなるプログラムを入力して、前記ループおよびその他の部分に基づいて前記プログラムの各変数に第１の優先度を与え、第１の優先度の高い順に所定数の前記変数（第１の変数）にグローバルレジスタを、残りの前記変数（第２の変数）に否グローバルレジスタを割り当てる割り当て（第１の割り当て）を行い、前記ループ部分に基づいて各前記変数に第２の優先度を与え、前記第２の変数のうち、前記第２の優先度が、何れかの前記第１の変数の前記第２の優先度より高い何れかの変数（第４の変数）に、前記第１の変数のうち、前記第２の優先度が、前記第４の変数の前記第２の優先度より低い何れかの変数（第３の変数）に割り当てた前記グローバルレジスタを割り当て直した割り当て（第２の割り当て）を行い、前記ループ部分からは前記第２の割り当てに従ったコードを、前記他の部分からは前記第１の割り当てに従ったコードを生成するレジスタ割り当てを実行させる。
【００１２】
本発明の一実施形態のコンパイル方法は、コンピュータが、ループとその他の部分からなるプログラムを入力して、前記ループおよびその他の部分に基づいて前記プログラムの各変数に第１の優先度を与え、第１の優先度の高い順に所定数の前記変数（第１の変数）にグローバルレジスタを、残りの前記変数（第２の変数）に否グローバルレジスタを割り当てる割り当て（第１の割り当て）を行い、前記ループ部分に基づいて各前記変数に第２の優先度を与え、前記第２の変数のうち、前記第２の優先度が、何れかの前記第１の変数の前記第２の優先度より高い何れかの変数（第４の変数）に、前記第１の変数のうち、前記第２の優先度が、前記第４の変数の前記第２の優先度より低い何れかの変数（第３の変数）に割り当てた前記グローバルレジスタを割り当て直した割り当て（第２の割り当て）を行い、前記ループ部分からは前記第２の割り当てに従ったコードを、前記他の部分からは前記第１の割り当てに従ったコードを生成するレジスタ割り当て行程を有するコンパイル方法。
【発明の効果】
【００１３】
本発明は、プログラム全体の最適化と局所的な最適化の調和を取った最適化を行うことが出来る。
【発明を実施するための最良の形態】
【００１４】
図１は、本発明の第１の実施形態にかかるコンパイル装置１０の構成図である。コンパイル装置１０は、フロントエンド１１、最適化部１２、レジスタ割り当て部１３、コードスケジューラ１４、出力部１５を備える。これらは、コンピュータであるコンパイル装置１０の図示しないプロセッサーが、図示しない主記憶装置に格納されているプログラムであるコンパイラ１９を読み込んで実行することで機能する。ハードウェアが、同等な機能を実現していてもよい。
【００１５】
ソース形式プログラム２１、第１の中間言語形式プログラム２２、第２の中間言語形式プログラム２３、コード２４、オブジェクト形式プログラム２５は、コンパイル装置１０に接続された図示しないディスク装置上などにファイルとして設けられる。同様に、変数表３０、パラメータ表４０は、図示しないディスク装置上などにファイルとして設けられる。コード２４は、第３の中間言語形式プログラムとも呼ばれる。コンパイル装置１０の各部（レジスタ割り当て部１３、コードスケジューラ１４等）はこれらを入出力する。
【００１６】
ソース形式プログラム２１は、Ｃ言語などの高級言語のソースコード形式のプログラムを格納する。オブジェクト形式プログラム２５は、機械語形式のプログラムを格納する。コンパイル装置１０は、ソース形式プログラム２１を入力してオブジェクト形式プログラム２５に変換して出力する。第１の中間言語形式プログラム２２、第２の中間言語形式プログラム２３、および、コード２４は、当該変換過程に於ける中間形式のプログラムを格納する。
【００１７】
フロントエンド１１は、ソース形式プログラム２１の構文解析、意味解析などを行い、第１の中間言語形式プログラム２２を出力する。最適化部１２は、第１の中間言語形式プログラム２２から、冗長な命令を省く、ループ内で繰り返し実行される命令をループ外に移動するなどの最適化を行い、第２の中間言語形式プログラム２３を出力する。
【００１８】
レジスタ割り当て部１３は、第２の中間言語形式プログラム２３内の変数にレジスタを割り当ててコード２４を出力する。コードスケジューラ１４は、ＶＬＩＷ（Very Long Instruction Word）計算機などでの並列実行可能正を高める為に、コード２４を並べ替える。コードスケジューラ１４は、例えば、Ｍｉｋｅ Ｊｏｈｎｓｏｎ著、村上和彰監訳、「スーパースカラ・プロセッサ」、日経ＢＰ出版センター、に記載されている技術を使用しても良い。出力部１５は、コード２４を機械語に変換して、オブジェクト形式プログラム２５を出力する。
【００１９】
変数表３０は、レジスタ割り当て部１３からアクセスされて、プログラム内で使用されている変数に関する情報を格納する。図２は、変数表３０の構成を示す。
【００２０】
変数表３０は、各変数の、ＩＤ３１、定義箇所３２、参照箇所３３、第１の優先度３４、第１の割り当てレジスタ番号３５、参照ループデータ３６を包含する。参照ループデータ３６は、ループごとに存在する。ループがネストするときは、例えば、一番外側のループごとに存在するようにしてもよい。
【００２１】
参照ループデータ３６は、範囲３７、第２の優先度３８、第２の割り当てレジスタ番号３９を包含する。範囲３７には、各ループの先頭と最終の箇所が格納される。ここで、箇所とは、命令の位置、例えば、プログラム内での命令番号や相対命令アドレスである。
【００２２】
定義箇所３２、参照箇所３３には、ＩＤ３１で示される変数の定義（値代入）の箇所と参照の箇所が格納される。定義箇所３２は一つ、参照箇所３３は複数の箇所を格納する。本発明における変数は、プログラマが宣言した変数そのものではない。プログラマが宣言した変数に値が確定するたびに、当該変数は本発明に於ける別の変数となる。
【００２３】
図３は、パラメータ表４０の構成を示す。パラメータ表４０は、グローバルレジスタ数４１と否グローバルレジスタ数４２を格納する。
【００２４】
グローバルレジスタと否グローバルレジスタは共に、オブジェクト形式プログラム２５が実行されるコンピュータが備えるレジスタである。グローバルレジスタは、関数やサブルーチンの呼び出しで値が保証される（破壊されない）レジスタである。即ち、グローバルレジスタは、例えば、関数やサブルーチンが、その入り口出口で値を退避回復するレジスタである。
【００２５】
否グローバルレジスタは、関数やサブルーチンの呼び出しで値が保証されないレジスタである。関数やサブルーチンの呼び出しの前後で、否グローバルレジスタの値を保証するためには、呼び出し命令の前後で退避回復が必要になる。
【００２６】
本実施形態のコンパイル装置１０は、先ず、プログラムの全体に基づいて、変数に第１の優先度３４を付与し、それに従ってプログラム全体のレジスタ割り当て（第１の割り当て）を決定する。次に、同装置は、プログラムのループ部分に基づいて、変数に第２の優先度３８を付与し、それに従って、ループ部分について第１の割り当ての一部を変更したレジスタ割り当て（第２の割り当て）をする場合がある。
【００２７】
図４は、レジスタ割り当て部１３の概略フローチャートである。同部はまず、プログラムからグローバル変数を抽出して変数表３０に登録する、変数登録処理を行う（Ｓ１１）。ここで、グローバル変数は、プログラムの基本ブロックを超えて、定義および参照される変数である。定義及び全ての参照が、プログラムの一つの基本ブロック内に閉じている変数は否グローバル変数である。なお、基本ブロックは、一入り口一出口の命令ブロックである。
【００２８】
次に、レジスタ割り当て部１３は、各グローバル変数に第１の優先度３４を付与し、同優先度に基づいてグローバル変数にグローバルレジスタを割り当てる、グローバルレジスタ割り当て処理を行う（Ｓ１２）。引き続き、同部は、グローバルレジスタが割り当てられなかったグローバル変数に、同優先度に基づき否グローバルレジスタを割り当てる、否グローバルレジスタ割り当て処理を行う（Ｓ１３）。この過程で、レジスタ割り当ての変更が発生し得る。
【００２９】
その後、同部は、レジスタ割り当てを反映したコード２４を生成する、コード生成処理（Ｓ１４）を行う。
【００３０】
図５は、レジスタ割り当て部１３の変数登録処理のフローチャートである。レジスタ割り当て部１３は、第２の中間言語形式プログラム２３の先頭から順に一つの命令を取得する（Ｓ２１）。当該命令が変数（変数Ａと仮称）を定義する命令であった（Ｓ２２でＹ）場合、同部は、当該命令を包含する基本ブロックの先頭命令と最終命令の箇所を取得する（Ｓ２３）。
【００３１】
次に、同部は、第２の中間言語形式プログラム２３全体から、変数Ａを参照する全ての命令の箇所を取得して（Ｓ２４）、それらが全て上述の基本ブロック内に入っているか判断する（Ｓ２５）。
【００３２】
それらが全て上述の基本ブロック内に入っていない場合（Ｓ２５でＮ）、変数Ａはグローバル変数である。この場合、同部は、変数ＡのＩＤ３１、定義箇所３２、参照箇所３３を変数表３０に格納する（Ｓ２６）。ここで、変数ＡのＩＤ３１は、例えば、変数Ａの定義命令の変数名に定義通番を付して生成する。
【００３３】
変数Ａを参照する命令の箇所が全て上述の基本ブロック内に入っている場合（Ｓ２５でＹ）、変数Ａは否グローバル変数である。この場合、同部は何もしない。即ち、変数表３０は、グローバル変数のみを格納する。
【００３４】
同部は、第２の中間言語形式プログラム２３の最後（Ｓ２７）まで、この変数登録処理を繰り返す。
【００３５】
図６は、レジスタ割り当て部１３のグローバルレジスタ割り当て処理のフローチャートである。まず、レジスタ割り当て部１３は、変数表３０から変数を一つ取得する（Ｓ３１）。
【００３６】
同部は、第２の中間言語形式プログラム２３全体を走査して、当該変数の定義および参照の間に存在する関数やサブルーチンの呼び出し命令の数（値Ａ）を求める（Ｓ３２）。具体的に、同部は、定義箇所３２と最初の参照箇所３３との間の呼び出し命令の数、各参照箇所３３とその次の参照箇所３３の間の呼び出し命令の数を数えて、その合計値を値Ａとする。
【００３７】
このとき、同部は、プログラム中にループがあれば、当該ループの繰り返し回数を考慮して、値Ａを求めても良い。ループの繰り返し数は、プログラムから静的に決定できればその数とし、実行時にしか決定できなければ所定値（例えば１００）としても良い。
【００３８】
次に、同部は、第２の中間言語形式プログラム２３全体を走査して、当該変数の参照回数（値Ｂ）を求める（Ｓ３３）。例えば、同部は、参照命令の数を数える。このとき、同部は、プログラム中にループがあれば、当該ループの繰り返し回数を考慮して、値Ｂを求めても良い。
【００３９】
同部は、値Ａと値Ｂの合計値を求めて、第１の優先度３４に格納する（Ｓ３４）。即ち、第１の優先度３４は、当該変数の参照が多いほど、かつ、定義/参照間に存在する呼び出し命令が多いほど大きな（高い）ものとなる。
【００４０】
同部は、変数表３０の最後（Ｓ３５）まで、上記の処理を繰り返す。その後（Ｓ３５でＹ）、同部は、第１の優先度３４の高い順に、変数にグローバルレジスタを割り当てて、当該レジスタの番号を第１の割り当てレジスタ番号３５に格納する（Ｓ３６）。
【００４１】
グローバルレジスタが割り当てられた変数は、第１の変数と称される。第１の変数の個数は、グローバルレジスタ数４１である。
【００４２】
一般に、変数の数は当該数以上であるので、この時点では、レジスタが割り当てられていない変数が残存する。（プログラムが極端に小さくて変数の数が少ないときには、そうでない場合がありうる。この場合、コンパイル装置１０は、否グローバル割り当て処理を省略して、直ちにコード生成処理を実行する。）
図７は、レジスタ割り当て部１３の否グローバルレジスタ割り当て処理のフローチャート（１／３）である。図８は、レジスタ割り当て部１３の否グローバルレジスタ割り当て処理のフローチャート（２／３）である。図９は、レジスタ割り当て部１３の否グローバルレジスタ割り当て処理のフローチャート（３／３）である。
【００４３】
レジスタ割り当て部１３は、変数表３０から、レジスタが割り当てられていない変数のうち、第１の優先度３４が最も高い変数（変数Ｘと仮称）を取得する（Ｓ４１）。同部は、どの変数にも割り当てられていない否グローバルレジスタが有ることを確認する（Ｓ４２でＹ）と、変数Ｘに当該否グローバルレジスタを割り当てて、当該レジスタの番号を第１の割り当てレジスタ番号３５に格納する（Ｓ４３）。
【００４４】
このように、否グローバルレジスタが割り当てられた変数は、第２の変数と称される。第２の変数の個数は、否グローバルレジスタ数４２である。このように、第１の優先度３４に従って、第１の変数と第２の変数にレジスタを割り当てることが、第１の割り当てである。
【００４５】
同部は、割り当てられていない否グローバルレジスタが無いことを検出する（Ｓ４２でＮ）と、処理を終了する。同部は、変数Ｘおよび変数Ｘより第１の優先度３４が低い変数にはレジスタの割り当てが出来ないことになる。
【００４６】
このようなレジスタ未割り当ての変数は、メモリ上でのみ演算されても良いし、短期間のみ上述のレジスタとは別の作業用レジスタを使用して演算されても良い。本発明では、レジスタ未割り当ての変数の扱いを特定しない。
【００４７】
なお、プログラムが小さくて変数の数が少ないときには、全ての変数にグローバルレジスタか否グローバルレジスタが割り当てられる場合もある。この場合、同部が、割り当てられていない否グローバルレジスタが無いことを検出する（Ｓ４２でＮ）ことはない。
【００４８】
同部は、第２の中間言語形式プログラム２３全体を走査して、変数Ｘの参照箇所３３がループ内に存在する（Ｓ４４でＹ）場合、当該参照箇所３３を含む一番外側のループの先頭と最終の箇所を抽出して範囲３７に格納する（Ｓ４５）。
【００４９】
なお、変数Ｘの参照箇所３３は複数であり、参照箇所３３を含む一番外側のループは複数存在する可能性があるが、下記説明では、簡単のため、これは一つであると仮定する。複数ある場合、以降の処理が一番外側のループ毎に繰り返される。
【００５０】
レジスタ割り当て部１３は、変数表３０から、変数（変数Ｙと仮称）を取り出して（Ｓ４６）、変数Ｙが当該ループ内で参照されているか（Ｓ４７）を確認する。具体的に、同部は、変数Ｙの参照箇所３３のいずれかが変数Ｘの範囲３７内に入っているかを確認する。
【００５１】
変数Ｙが当該ループ内で参照されている場合（Ｓ４７でＹ）、同部は、当該ループ内で変数Ｙの定義及び参照の間に存在する関数やサブルーチンの呼び出し命令の数（値ａ）を求め、変数Ｙの第２の優先度３８に格納する（Ｓ４８）。具体的に、同部は、当該ループ内の定義箇所３２と最初の参照箇所３３との間の呼び出し命令の数、各参照箇所３３とその次の参照箇所３３の間の呼び出し命令の数を数えて、その合計値を値ａとする。なお、当該ループ内に定義箇所３２がない場合は、参照間の呼び出し命令数を求めて値ａとする。このとき、同部は、当該ループ内にループのネストがあれば、ネストしている当該ループの繰り返し回数を考慮して、値ａを求めても良い。
【００５２】
変数Ｙが当該ループ内で参照されていない場合（Ｓ４７でＮ）、同部は、０を変数Ｙの第２の優先度３８に格納する（Ｓ４９）。
【００５３】
同部は、変数表３０の最後（Ｓ４Ａ）まで、上記Ｓ４６乃至Ｓ４９の処理を繰り返す。
【００５４】
その後（Ｓ４ＡでＹ）、同部は、変数表３０を走査して、グローバルレジスタが割り当てられた変数（第１の変数）のなかで、変数Ｘの第２の優先度３８より低い第２の優先度３８を持つ変数が有るかを検査する（Ｓ５１）。
【００５５】
そのような変数が有る場合（Ｓ５２でＹ）、同部は、当該変数中、最低（最小）の第２の優先度３８を持つ変数（第３の変数）を取得する（Ｓ５３）。最低の第２の優先度３８を持つ変数が複数ある場合、同部は、その中から第１の優先度３４が最低の変数を第３の変数として取得する。
【００５６】
同部は、第３の変数の第１の割り当てレジスタ番号３５を取り出して、変数Ｘ（第４の変数となる）の第２の割り当てレジスタ番号３９に格納する（Ｓ５４）。同部は、第３の変数の退避（スピル）／リストア命令を生成して、当該ループの入り口出口に挿入する（Ｓ５５）。
【００５７】
なお、同部はここで、第１の割り当てに於いて第３の変数に割り当てたグローバルレジスタを、当該ループ内に限って第４の変数に割当直した。このように、第２の優先度３８に従って、当該ループ内に限って第１の割り当てを変更してレジスタを割り当てることが第２の割り当てである。
【００５８】
その後、同部は、変数表３０の最後（Ｓ６８）まで、本否グローバルレジスタ割り当て処理を繰り返す。
【００５９】
第３の変数がない場合（Ｓ５２でＮ）、同部は、変数Ｘの第１の割り当てレジスタ番号３５を取り出して、変数Ｘの第２の割り当てレジスタ番号３９に格納する（Ｓ５６）。即ち、同部は、当該ループ内においても第１の割り当てを変更しない。即ち、変数Ｘには、否グローバルレジスタが割り当てられたままである。
【００６０】
この場合、同部は、所定の基本ブロックの入り口出口に変数Ｘのスピル命令とリストア命令を生成して挿入する。その処理は以下の通りである。
【００６１】
レジスタ割り当て部１３は、第２の中間言語形式プログラム２３の先頭から順に一つの命令を取得する（Ｓ６１）。当該命令が呼び出し命令であれば（Ｓ６２でＹ）、同部は、当該命令を含む基本ブロックの先頭と最終の命令の箇所を取得する（Ｓ６３）。
【００６２】
変数Ｘの定義箇所３２と参照箇所３３が当該ブロックの前後に存在し（Ｓ６４でＹ）、かつ、当該ブロック内に存在しない（Ｓ６５でＹ）場合、同部は、当該基本ブロックの入り口出口に変数Ｘのスピル命令とリストア命令を生成して挿入する（Ｓ６６）。ただし、同部は、既に当該基本ブロックの入り口出口に変数Ｘのスピル命令とリストア命令が挿入されていれば、重ねて挿入することはしない。
【００６３】
Ｓ６２、Ｓ６４、Ｓ６５の何れかでＮとなれば、同部は何もしない。
【００６４】
同部は、第２の中間言語形式プログラム２３の最後（Ｓ６７）までＳ６１乃至Ｓ６６の処理を繰り返す。この終了（Ｓ６７でＹ）の後、当該変数Ｘが変数表３０の最後の変数で無ければ（Ｓ６８でＮ）、次の変数について否グローバル割り当て処理を繰り返す（Ｓ４１に戻る）。
【００６５】
図１０は、レジスタ割り当て部１３のコード生成処理のフローチャートである。なお、本フローチャートでは、レジスタ未割り付けの変数が存在しないことを前提としている。
【００６６】
レジスタ割り当て部１３は、第２の中間言語形式プログラム２３の先頭から順に一つの命令を取得する（Ｓ８１）。当該命令が変数を定義または参照する場合（Ｓ８２でＹ）、同部は、当該命令がループ内に存在するかをチェックする（Ｓ８３）。
【００６７】
当該命令がループ内に存在しなければ（Ｓ８３でＮ）、同部は、当該命令から変数のＩＤ３１を生成して、変数に当該ＩＤ３１に対応する第１の割り当てレジスタ番号３５のレジスタを割り当てたコード２４を生成する（Ｓ８４）。
【００６８】
当該命令がループ内に存在すれば（Ｓ８３でＹ）、同部は、当該命令から変数のＩＤ３１を生成して、変数に当該ＩＤ３１に対応する第２の割り当てレジスタ番号３９のレジスタを割り当てたコード２４を生成する（Ｓ８６）。
【００６９】
なお、プログラムに一番外側のループが複数存在する場合、同部は、当該命令が包含されるループのプログラム先頭からの順番などに基づいて、当該ループに対応する参照ループデータ３６を認識して、その第２の割り当てレジスタ番号３９を参照する。
【００７０】
同部は、第２の中間言語形式プログラム２３の最後（Ｓ８５）まで、このコード生成処理を繰り返す。
【００７１】
本実施形態のコンパイル装置１０は、プログラム全体としての最適化と局所的な最適化の調和を取ったレジスタ割り当てを行うことが出来る（第１の効果）。その理由は、同装置は、先ず、プログラム全体にわたるレジスタ割り当てを、プログラム全体に基づいて行う（第１の割り当て）からである。そして、同装置は、ループ部分について、当該ループ部分のプログラムに基づいて、第１の割り当ての一部を変更したレジスタ割り当て（第２の割り当て）を行うからである。
【００７２】
具体的には、本発明のコンパイル装置１０は、プログラム全体として、メモリアクセスを減らすようなレジスタ割り当てを行いつつも、ループ内で使用していないグローバル変数については、ループの直前にスピル命令を生成し挿入する。同装置は、そのうえで、当該グローバル変数に割り当てられていたグローバルレジスタをループ内の別のグローバル変数に割り当てることで、作成したオブジェクト形式プログラム２５の実行速度を向上させる。ループ内に不要なスピル命令を生成、挿入する必要がなくなるため、実行速度が向上するのである。
【００７３】
第２の割り当てに於いて、第１の割り当てを全て変更するものではないため、この割り当ては、ループ部分にのみ基づいた割り当てと、その他の部分にのみ基づいた割り当てを組み合わせたものとは異なる。
【００７４】
本実施形態のコンパイル装置１０は、レジスタ割り当て部１３が生成したスピル命令も、並列実行可能正を高める為に並べ替えが可能である（第２の効果）。その理由は、レジスタ割り当て部１３がスピル命令挿入したコード２４を対象に、コードスケジューラ１４が命令の並べ替えを行うからである。スピル命令も最適な場所に移動できるため、実行速度が向上する。
【００７５】
図１１は、本発明の第２の実施形態にかかる、レジスタ割り当て部１３のグローバルレジスタ割り当て処理のフローチャートである。本実施形態のコンパイル装置１０は、その他の点では第１の実施形態と同じである。
【００７６】
まず、レジスタ割り当て部１３は、変数表３０から変数を一つ取得する（Ｓ９１）。
【００７７】
同部は、第２の中間言語形式プログラム２３全体を走査して、当該変数の定義および参照の間に存在する関数やサブルーチンの呼び出し命令の数（値Ａ）を求める（Ｓ９２）。具体的に、同部は、定義箇所３２と最初の参照箇所３３との間の呼び出し命令の数、各参照箇所３３とその次の参照箇所３３の間の呼び出し命令の数を数えて、その合計値を値Ａとする。
【００７８】
このとき、同部は、プログラム中にループがあれば、当該ループの繰り返し回数を考慮して、値Ａを求めても良い。ループの数は、プログラムから静的に決定できればその数とし、実行時にしか決定できなければ所定値（例えば１００）としても良い。
【００７９】
次に、同部は、第２の中間言語形式プログラム２３全体を走査して、当該変数の参照回数（値Ｂ）を求める（Ｓ９３）。例えば、同部は、参照命令の数を数える。このとき、同部は、プログラム中にループがあれば、当該ループの繰り返し回数を考慮して、値Ｂを求めても良い。
【００８０】
同部は、値Ｂの高い順に変数を、グローバルレジスタ数４１と否グローバルレジスタ数４２の合計値数分だけ選択する（Ｓ９４）。次に同部は、選択した変数には値Ａの大きな順に大きな第１の優先度３４を付与し、選択されなかった変数には最低（例えば０）の第１の優先度３４を付与する（Ｓ９５）。
【００８１】
同部は、変数表３０の最後（Ｓ９６）まで、上記の処理を繰り返す。その後（Ｓ９６でＹ）、同部は、第１の優先度３４の高い順に、変数にグローバルレジスタを割り当てて、当該レジスタの番号を第１の割り当てレジスタ番号３５に格納する（Ｓ９７）。
【００８２】
本実施例のコンパイル装置１０は、グローバルレジスタの最適な割り当てが可能となる。定義、参照間の呼び出し命令数が多い変数を、確実にグローバルレジスタに割り当てるからである。
【００８３】
図１２は、本発明にかかるコンパイル装置１０の基本的な構成を示す。本発明のコンパイル装置１０は、レジスタ割り当て部１３を備える。
【００８４】
同部は、先ず、ループとその他の部分からなるプログラム２０を入力して、ループおよびその他の部分に基づいてプログラム２０の各変数に第１の優先度３４を与える。同部は更に、第１の優先度３４の高い順に所定数の変数（第１の変数）にグローバルレジスタを、残りの変数（第２の変数）に否グローバルレジスタを割り当てる割り当て（第１の割り当て）を行う。
【００８５】
同部は、次に、ループ部分に基づいて各変数に第２の優先度３８を与える。同部は更に、第２の変数のうち、第２の優先度３８が、何れかの第１の変数の第２の優先度３８より高い何れかの変数（第４の変数）に、第１の変数のうち、第２の優先度３８が、第４の変数の第２の優先度３８より低い何れかの変数（第３の変数）に割り当てた前記グローバルレジスタを割り当て直した割り当て（第２の割り当て）を行う。
【００８６】
そして、同部は、ループ部分からは第２の割り当てに従ったコード２４を、他の部分からは第１の割り当てに従ったコード２４を生成する。
【００８７】
なお、プログラム２０は、第２の中間言語形式プログラム２３であってもよいが、それに限定されない。プログラム２０の変数にレジスタ割り当てが可能な形式であれば良い。例えば、プログラム２０は、レジスタ番号以外はオブジェクト形式プログラム２５と同一形式であっても良い。
【図面の簡単な説明】
【００８８】
【図１】図１は、本発明の第１の実施形態にかかるコンパイル装置１０の構成図である。
【図２】図２は、変数表３０の構成を示す。
【図３】図３は、パラメータ表４０の構成を示す。
【図４】図４は、レジスタ割り当て部１３の概略フローチャートである。
【図５】図５は、レジスタ割り当て部１３の変数登録処理のフローチャートである。
【図６】図６は、レジスタ割り当て部１３のグローバルレジスタ割り当て処理のフローチャートである。
【図７】図７は、レジスタ割り当て部１３の否グローバルレジスタ割り当て処理のフローチャート（１／３）である。
【図８】図８は、レジスタ割り当て部１３の否グローバルレジスタ割り当て処理のフローチャート（２／３）である。
【図９】図９は、レジスタ割り当て部１３の否グローバルレジスタ割り当て処理のフローチャート（３／３）である。
【図１０】図１０は、レジスタ割り当て部１３のコード生成処理のフローチャートである。
【図１１】図１１は、本発明の第２の実施形態にかかる、レジスタ割り当て部１３のグローバルレジスタ割り当て処理のフローチャートである。
【図１２】図１２は、本発明にかかるコンパイル装置１０の基本的な構成を示す。
【符号の説明】
【００８９】
１０    コンパイル装置
１１    フロントエンド
１２    最適化部
１３    レジスタ割り当て部
１４    コードスケジューラ
１５    出力部
１９    コンパイラ
２０    プログラム
２１    ソース形式プログラム
２２    第１の中間言語形式プログラム
２３    第２の中間言語形式プログラム
２４    コード
２５    オブジェクト形式プログラム
３０    変数表
３１    ＩＤ
３２    定義箇所
３３    参照箇所
３４    第１の優先度
３５    第１の割り当てレジスタ番号
３６    参照ループデータ
３７    範囲
３８    第２の優先度
３９    第２の割り当てレジスタ番号
４０    パラメータ表
４１    グローバルレジスタ数
４２    否グローバルレジスタ数
【図１】
0005208589.tif 000002
【図２】
0005208589.tif 000003
【図３】
0005208589.tif 000004
【図４】
0005208589.tif 000005
【図５】
0005208589.tif 000006
【図６】
0005208589.tif 000007
【図７】
0005208589.tif 000008
【図８】
0005208589.tif 000009
【図９】
0005208589.tif 000010
【図１０】
0005208589.tif 000011
【図１１】
0005208589.tif 000012
【図１２】
0005208589.tif 000013