JP5165969B2 - プログラムのコンパイルのために変数にレジスタを割り付ける技術 - Google Patents

Description

本発明は、プログラムのコンパイルに関する。特に本発明は、プログラムのコンパイルのために変数にレジスタを割り付ける技術に関する。

コンパイラは、プログラム内で用いられる変数の値をレジスタに保持させることで、プログラムの実行を効率化する。コンパイラが各変数の値をどのレジスタに保持させるかを決定する技術は、レジスタ割付と呼ばれる。レジスタ割付において、プログラムで使用されるある変数の値をあるレジスタに一貫して保持させると、そのプログラムのうちその変数をあまり使用しない部分においても、その変数のためにそのレジスタが占有される。このため、そのレジスタを他の用途に使用できず、プログラムの実行の効率を全体として低下させてしまう場合がある。
非特許文献１−５については後述する。

P. Briggs, K. D. Cooper, and L. Torczon. Improvements to Graph Coloring Register Allocation. ACM TOPLAS, Vol.16, No.3, pp.428-455, 1994. L. George and A. W. Appel. Iterated Register Coalescing. ACM TOPLAS, Vol.18, No.3, pp.300-324, 1996. G. J. Chaitin. Register Allocation & Spilling via Graph Coloring. ACM SIGPLAN Notices, Vol.17, No.6, pp.98-105, 1982. J. Park and S. Moon. Optimistic Register Coalescing. ACM TOPLAS, Vol.26, No.4, pp.735-765, 2004. P. Briggs. Register Allocation via Graph Coloring. Ph. D Thesis, Rice University, 1992.

これに対し、コンパイラは、変数を、例えばプログラムの部分ごとに新たな複数の変数に分割してもよい。そして、コンパイラは、それら複数の変数のそれぞれに対しレジスタを割り付けるか否かを選択的に決定する。これにより、変数をあまり使用しない部分においてはレジスタを他の用途に使用することができ、プログラムの実行効率を向上できる。一方、変数を新たな複数の変数に分割すると、分割の境界において変数値を代入する処理が必要となる。この代入する処理が多すぎると、やはり、プログラムの実行効率が低下する。従って、プログラム全体としての実行効率を高めるためには、変数を適度に分割することが好ましい。

変数を適度に分割するためには、変数をノードとして表しかつ変数同士の干渉関係をエッジで表したグラフ上でノードを融合（ｃｏａｌｅｓｃｉｎｇ）する技術を応用できるとも考えられる（非特許文献１−４を参照。）。非特許文献１には、保守的融合（ｃｏｎｓｅｒｖａｔｉｖｅ ｃｏａｌｅｓｃｉｎｇ）という技術が開示され、非特許文献２には、繰り返し融合（ｉｎｔｅｒａｔｅｄ ｃｏａｌｅｓｃｉｎｇ）という技術が開示される。非特許文献３には、積極的融合（ａｇｒｅｓｓｉｖｅ ｃｏａｌｅｓｃｉｎｇ）という技術が開示され、非特許文献４には、楽観的融合（ｏｐｔｉｍｉｓｔｉｃ ｃｏａｌｅｓｃｉｎｇ）という技術が開示される。しかしながら、非特許文献１または２に記載の技術では、融合が不充分ゆえ多くの代入命令が生成される場合がある。また、非特許文献３または４に記載の技術では、融合し過ぎて変数分割による効果が充分でない場合がある。

そこで本発明は、上記の課題を解決することのできるコンパイラ装置、コンパイル方法およびプログラムを提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。

上記課題を解決するために、本発明の一側面においては、コンパイルの対象となるプログラムの中で使用される変数にレジスタを割り付けるコンパイラ装置であって、前記プログラムの中で使用されるある変数と他の変数とが前記プログラムの実行中の何れかの時点において同時に有効な値を保持している関係である干渉関係にあるかどうかを示す干渉情報、および、前記プログラム中の代入命令の代入元の変数を代入先の変数に対応付けた代入情報を記憶している記憶装置と、前記プログラムの中で使用されるそれぞれの変数に、前記干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において、予め定められた基準数以上のレジスタの中から予め定められた手順に従ってレジスタを選択して割り付ける第１割付部と、複数の前記変数に、前記第１割付部により同一のレジスタが割り付けられ、かつ、当該複数の変数が前記代入情報において互いに対応付けられていることを条件に、当該複数の変数を新たな変数に置換すると共に、当該複数の変数のそれぞれについての前記干渉関係を前記記憶装置から読み出して併合して、当該新たな変数についての干渉関係を生成し、生成した当該干渉関係により前記干渉情報を更新する更新部と、当該複数の変数に代えて当該新たな変数を使用する前記プログラム中の各変数に、更新した前記干渉情報に基づく干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において、前記第１割付部と同一の前記手順に従って前記基準数のレジスタの中からレジスタを選択して割り付ける第２割付部と、前記第２割付部が変数にレジスタを割り付けた前記プログラムを出力する出力部とを備えるコンパイラ装置を提供する。
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。

以下、発明の実施の形態を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。

図１は、本実施形態に係るコンパイラ装置１０の全体構成を示す。コンパイラ装置１０は、入力したプログラムを機械語プログラムに変換して出力する。このほかに、コンパイラ装置１０は、機械語プログラムを効率的に実行させるための最適化をする。具体的には、コンパイラ装置１０は、第１最適化部１００と、レジスタ割付部１１０と、記憶装置１２０と、第２最適化部１３０とを備える。

第１最適化部１００は、コンパイルの対象となるプログラムを受け取る。このプログラムを入力プログラムと呼ぶ。そして、第１最適化部１００は、その入力プログラムに対し、最適化のための各種の処理を行う。例えば、第１最適化部１００は、入力プログラム内で使用される各変数の生存区間を解析してもよい。ある変数が互いに連続しない複数の生存区間を有する場合には、第１最適化部１００は、その変数を、生存区間ごとにその変数の値を保持する複数の変数に変換してもよい。第１最適化部１００により各種の処理が行われたプログラムを対象プログラム２２とする。

レジスタ割付部１１０は、対象プログラム２２の中で使用される変数にレジスタを割り付ける。このように、レジスタ割付の対象となるプログラムは、コンパイラ装置１０に入力されたプログラムそのもののみならず、そのプログラムに対し所定の処理を行った後のプログラムであってよい。同様に、レジスタ割付の対象となる変数は、コンパイラ装置１０に入力されたプログラム中の変数のみならず、そのプログラムに対し所定の処理を行った結果生成された変数をも含む。

レジスタ割付のために、レジスタ割付部１１０は、対象プログラム２２を解析して各種の情報を生成し、記憶装置１２０に格納してもよい。そして、レジスタ割付部１１０は、記憶装置１２０に記憶されているこれらの情報を参照して変数にレジスタを割り付ける。記憶装置１２０に記憶される情報は、例えば、変数の干渉関係を示す干渉情報、変数の代入先および代入元の関係を示す代入情報、および、変数毎のレジスタ割付の優先度を示す優先度、などである。

レジスタ割付部１１０は、変数にレジスタを割り付けたプログラム（これを結果プログラム６９と呼ぶ）を生成して出力する。レジスタ割付部１１０は、この結果プログラム６９を更に入力してもよい。この場合、レジスタ割付部１１０は、結果プログラム６９に含まれる各レジスタを変数とみなして、さらにその変数にレジスタを割り付けてもよい。レジスタ割付部１１０は、以上の処理を、所定の条件が成立するまで繰り返してよい。

第２最適化部１３０は、この結果プログラム６９に対し各種の処理を行う。例えば、第２最適化部１３０は、代入元および代入先のそれぞれが同一のレジスタである代入命令を、結果プログラム６９から削除してもよい。各種の処理が行われた結果プログラム６９は、出力プログラム２４としてレジスタ割付部１１０の外部に出力される。外部の装置は、出力プログラム２４を実行することで、入力プログラムの作成者の意図に従った各種の処理を行うことができる。

図２は、ある対象プログラム２２の中で使用される各変数の使用状況を示す。図左側に示すように、対象プログラム２２は、最適化の早い段階において、例えば基本ブロックと呼ばれる単位によって、複数の部分に分割される場合が多い。それぞれの基本ブロックは、連続して実行される少なくとも１つの命令を含む。そして、それぞれの基本ブロックは、その先頭および末尾を除き、条件分岐命令の分岐元または分岐先とはならない。

第１の基本ブロックは、変数ａに値を代入する命令、および、変数ａを参照する命令を含む。記号「＝」は右辺を参照して左辺に代入する命令を示す。記号「−＞」は、ポインタ演算子であり、記号の左側の変数の値をアドレスとする記憶領域のうち、記号の右側により定められる領域のデータを読み出す演算を示す。したがって、「ａ−＞…」により、変数ａの値がアドレスとして参照される。

以降同様に、第２の基本ブロックは、変数ｂに値を代入する命令、および、変数ｂの値を参照する２つの命令を含む。第３の基本ブロックは、変数ｃに値を代入する命令、変数ｂの値を参照する２つの命令、および、変数ｃの値を参照する３つの命令を含む。第４の基本ブロックは、変数ａの値を参照する３つの命令、変数ｂの値を参照する命令、および、変数ｃの値を参照する命令を含む。

図右側に示すように、変数の生存区間は、変数にある値を最初に代入してからその値を最後に使用するまでである。使用とは、例えば、その変数の値を参照することをいう。図では、変数を囲う丸印が代入を示し、変数の伴わない丸印が使用を示す。各丸印を接続する直線が、変数の生存区間を示す。変数ａについて例示すれば、第１の基本ブロックの第１命令によって最初に代入され、以降３度の使用を経て、第４の基本ブロックの第３命令により最後に使用される。以降の説明においても、生存区間を直感的に認識し易くするため、連続する生存区間については、この図のような連続する直線として表す。

なお、実際には、コンパイル前およびコンパイル後のプログラムを比較すると、数値、文字列および記号を含む文が、オペレータ、レジスタ、アドレスおよび定数値を含む命令に変換される。そして、コンパイルの途中段階においては、オペレータの抽象概念である中間コードが用いられることもある。一方で、コンパイルのどの段階であっても、プログラムに表現されている各種操作は機能的には略同一である。従って、当該技術分野においてはよくあることだが、本実施形態においても、命令、代入、参照、ロードまたストアなどの本来はコンパイル前または後の一方のみで用いることが適切な用語群を、コンパイルの何れの段階にあるプログラムにおいても共通して使用する。

図３は、各変数の値を特定のレジスタが一貫して保持する場合におけるレジスタの割付結果の一例を示す。この例において、対象プログラム２２の実行に使用可能なレジスタの数は２である。そして、変数ｃにはレジスタｒ１が割り付けられ、変数ｂにはレジスタｒ２が割り付けられる。レジスタｒ１は、変数ｃの値を一貫して保持している。レジスタｒ２は、変数ｂの値を一貫して保持している。一方、変数ａにはレジスタが割り付けられていない。この結果、変数ａの値はメモリに格納されて、参照の毎にメモリから読み出される（これをスピルと呼ぶ）。この例では参照が４回なので、変数ａの値は４回読み出され、読出しの都度使用完了後には破棄される。

図４は、各変数を複数の変数に変換したうえでレジスタを割り付ける場合におけるレジスタの割付結果の第１例を示す。図左には、各変数の生存区間を示す。この図は図２右側の図と同一である。レジスタ割付部１１０は、変数ａおよび変数ｂのそれぞれを複数の変数に変換する。変数ｂは変数ｂ１および変数ｂ２に、変数ａは変数ａ１、変数ａ２および変数ａ３に、それぞれ変換される。また、変数ｂ２に変数ｂ１の値を代入する命令、変数ａ２に変数ａ１を代入する命令、および、変数ａ３に変数ａ２を代入する命令が生成される。

レジスタ割付部１１０は、変換後のそれぞれの変数に、レジスタを割り付ける。例えば、レジスタ割付部１１０は、変数ａ１にレジスタｒ２を割り付け、変数ｂ１にレジスタｒ２を割り付け、変数ａ３にレジスタｒ２を割り付け、そして、変数ｃにレジスタｒ１を割り付ける。

変数ａ２および変数ｂ２はレジスタに割り付けられない。したがって、これらの変数の値は一旦メモリに格納されて、使用の毎にメモリから読み出される。この結果、メモリからの値の読出しの処理は、それぞれ変数ａ２およびｂ２のための２回となる。この例によれば、図３と比較して、スピルによる値の読出しの回数を減らすことができる。また、一旦生成された代入命令も不要となる。

図５は、各変数を複数の変数に変換したうえでレジスタを割り付ける場合におけるレジスタの割付結果の第２例を示す。図左には、各変数の生存区間を示す。この図は図２右側の図と同一である。レジスタ割付部１１０は、変数ａ−ｃのそれぞれを複数の変数に変換する。変数ｂは変数ｂ１、変数ｂ２、変数ｂ３、変数ｂ４および変数ｂ５に、変数ａは変数ａ１、変数ａ２、変数ａ３および変数ａ４に、それぞれ変換される。変数ｃは、変数ｃ１、変数ｃ２、変数ｃ３および変数ｃ４に、それぞれ変換される。

また、この変換により、下記の代入命令が生成される。変数ｃ１から変数ｃ２、変数ｃ２から変数ｃ３、変数ｃ３から変数ｃ４、変数ｂ１から変数ｂ２、変数ｂ２から変数ｂ３、変数ｂ３から変数ｂ４、変数ｂ４から変数ｂ５、変数ａ１から変数ａ２、変数ａ２から変数ａ３、および、変数ａ３から変数ａ４への代入命令である。

レジスタ割付部１１０は、変換後のそれぞれの変数に、レジスタを割り付ける。例えば、レジスタ割付部１１０は、変数ａ１にレジスタｒ２を割り付け、変数ａ３−４にレジスタｒ２を割り付ける。また、レジスタ割付部１１０は、変数ｂ１−４にレジスタｒ１を割り付ける。また、レジスタ割付部１１０は、変数ｃ１−３にレジスタｒ２を割り付け、変数ｃ４にレジスタｒ１を割り付ける。

図４の例と同様、変数ａ２および変数ｂ５はレジスタに割り付けられない。したがって、これらの変数の値は一旦メモリに格納されて、使用の毎にメモリから読み出される。この結果、メモリからの値の読出しの処理は、それぞれ変数ａ２およびｂ５のための２回となる。

但し、図４の例と異なり、変数ｃ１−３と変数ｃ４とには異なるレジスタが割り付けられる。従って、変数ｃ１−３の値を保持するレジスタｒ２から、変数ｃ４の値を保持するレジスタｒ１への代入命令が必要となる。このように、変数を分割し過ぎると、レジスタ間の代入命令が必要となって、プログラムの実行効率が低下する場合がある。

これに対し、本実施形態に係るコンパイラ装置１０は、変数を適度に分割することで、分割によるスピル低減と、分割により生じる代入命令の削減とをバランスし、プログラムを全体として効率的に動作させることができる。以下、具体的に説明する。

図６は、本実施形態に係るレジスタ割付部１１０の機能構成の一例を示す。レジスタ割付部１１０は、変数変換部６００と、代入命令生成部６１０と、情報生成部６２０と、第１割付部６３０と、更新部６４０と、第２割付部６５０と、スピル生成部６６０と、出力部６７０とを備える。変数変換部６００は、対象プログラム２２内の各変数を複数の変数に変換する。この変換は、例えば、変数変換部６００が、ある変数の生存区間を分割して、分割した生存区間ごとにその変数の値を保持する複数の変数を生成することで実現されてよい。

具体的には、変数変換部６００は、変数の生存区間を、対象プログラム２２中の各部の実行頻度、または、その変数の使用頻度に応じて分割してよい。より詳細には、変数変換部６００は、ある変数の生存区間を、対象プログラム２２のうちの実行頻度が基準よりも高い部分に対応する生存区間と、対象プログラム２２のうちの実行頻度が基準よりも低い部分に対応する生存区間と、に分割してよい。また、変数変換部６００は、ある変数の生存区間を、その変数の代入または参照を境界として分割してもよい。

代入命令生成部６１０は、変換した当該複数の変数のうちのある変数から他の変数への代入命令を対象プログラム２２中に生成する。例えば、変数ａが変数ａ１および変数ａ２に変換された場合、代入命令生成部６１０は、変数ａ１から変数ａ２に値を代入する命令を生成する。このように、代入命令生成部６１０は、それぞれの生存区間が互いに連続する変数の組について、生存区間の境界に代入命令を生成してよい。変数が変換され、かつ、代入命令が生成されたプログラムを、プログラム６０とする。図７にその一例を示す。

図７は、本実施形態に係るプログラム６０の一例を示す。変数ｃは、変数ｃ１−４のそれぞれに変換される。変数ｂは、変数ｂ１−５のそれぞれに変換される。変数ａは、変数ａ１−４のそれぞれに変換される。また、変数ｃ１から変数ｃ２への代入命令、変数ｃ２から変数ｃ３への代入命令、および、変数ｃ３から変数ｃ４への代入命令が生成される。

また、変数ｂ１から変数ｂ２への代入命令、変数ｂ２から変数ｂ３への代入命令、変数ｂ３から変数ｂ４への代入命令、および、変数ｂ４から変数ｂ５への代入命令が生成される。また、変数ａ１から変数ａ２への代入命令、変数ａ２から変数ａ３への代入命令、および、変数ａ３から変数ａ４への代入命令が生成される。

図６の説明に戻る。情報生成部６２０は、対象プログラム２２中で使用される複数の変数についての干渉関係を示す情報を、干渉情報６２Ａとして生成して記憶装置１２０に格納する。ここでいう対象プログラム２２中で使用される複数の変数には、変数変換部６００による変換前の変数は含まれず、変数変換部６００による変換後の変数が含まれる。また、干渉関係とは、ある変数と他の変数とが対象プログラム２２の実行中の何れかの時点において同時に有効な値を保持している関係を示す。ここでいう「有効な」値とは、その変数の最初の代入から最後の使用までの間にその変数に格納されている値をいう。図８に干渉情報６２Ａの一例を示す。

図８は、本実施形態に係る干渉情報６２Ａの一例を示す。干渉情報６２Ａは、干渉グラフと呼ばれるグラフ形式のデータ構造を有してよい。干渉グラフとは、プログラム６０により使用される各変数をノードとし、互いに干渉関係にある変数の組を示すノードの組を、エッジで連結したグラフである。

この図の例で、例えば変数ａ２は、変数ｃ１−４および変数ｂ１−５の何れとの間でも干渉関係にある。従って、変数ａ２を示すノードは、変数ｃ１−４および変数ｂ１−５の何れを示すノードとの間でもエッジで直接接続される。また、変数ｂ５は、変数ｃ１−４および変数ａ２−４の何れとの間でも干渉関係にある。従って、変数ｂ５を示すノードは、変数ｃ１−４および変数ａ２−４の何れを示すノードとの間でもエッジで直接接続される。

また、変数ｃ４は、変数ａ２−３および変数ｂ５の何れとの間でも干渉関係にある。従って、変数ｃ４を示すノードは、変数ａ２−３および変数ｂ５の何れを示すノードとの間でもエッジで直接接続される。また、変数ｃ１は、変数ｂ３−５および変数ａ２の何れとの間でも干渉関係にある。従って、変数ｃ１を示すノードは、変数ｂ３−５および変数ａ２の何れを示すノードとの間でもエッジで直接接続される。一方で、変数ａ１は何れの変数との間でも干渉関係にないので、変数ａ１を示すノードは何れのノードともエッジで直接接続されない。図６の説明に戻る。

また、情報生成部６２０は、代入命令生成部６１０が生成した代入命令の代入元および代入先となる変数の組を示す代入情報６４Ａを生成して、記憶装置１２０に格納する。この代入情報は、たとえば、対象プログラム２２を走査して対象プログラム２２から変数の代入命令を検出することによって取得されてもよい。代入情報６４Ａの一例を図９に示す。

図９は、本実施形態に係る代入情報６４Ａの一例を示す。代入情報６４Ａは、プログラム６０の中で使用される各変数を行方向および列方向にそれぞれ配列した行列状のデータ構造を有してよい。そして、代入情報６４Ａにおいて、代入命令の代入元および代入先の関係にある変数の組には数値１が対応付けられており、そのような関係にない変数の組に対応付けて数値０が対応付けられている。

例えば、図７に示したように、変数ａ２は変数ａ１を代入元とする代入命令の代入先であり、さらに、変数ａ３を代入先とする代入命令の代入元である。従って、代入情報６４Ａにおいて、変数ａ２および変数ａ１の組には数値１が対応付けられている。そして、変数ａ２および変数ａ３の組にも数値１が対応付けられている。

変数ａ２は、その他の変数との間では代入命令の代入元および代入先の関係に無い。従って、変数ａ２とその他の変数との組には、数値０が対応付けられている。他の変数についても同様である。具体的には、変数ａ４および変数ａ３の組には数値１が対応付けられ、変数ｂ２および変数ｂ１ならびに変数ｂ２および変数ｂ３の組には数値１が対応付けられる。また、変数ｂ４および変数ｂ３の組ならびに変数ｂ４および変数ｂ５の組には数値１が対応付けられる。

また、変数ｃ２および変数ｃ１の組ならびに変数ｃ２および変数ｃ３の組には数値１が対応付けられる。また、変数ｃ３および変数ｃ４の組には数値１が対応付けられる。以上に例示した代入情報６４Ａによれば、プログラム６０を改めて走査しなくとも、何れの変数が他の何れの変数との間で変数値を代入される関係にあるかを迅速に判別できる。

図６の説明に戻る。さらに、情報生成部６２０は、それぞれの変数についてその変数にレジスタを割り付ける優先度６５Ａを生成し、記憶装置１２０に格納してもよい。図１０にその一例を示す。

図１０は、本実施形態に係る優先度６５Ａの一例を示す。優先度６５Ａは、プログラム６０の中で用いられるそれぞれの変数に、その変数にレジスタを割り付けることで得られる利得、その変数と干渉関係にある他の変数の数（次数）、および、その変数をスピルすることで蒙る損失のコストを対応付けている。このコストが、本発明にかかる優先度の一例である。コストが高い程、レジスタ割り付けの優先度が高い。

ある変数の利得は、例えば、プログラム６０の中でその変数を使用する回数に基づく。使用回数の多い変数ほど、レジスタを割り付けると実行効率が向上するからである。コストは、例えば、利得（ｘ）を次数（ｙ）で割り算することによって算出される。次数（ｙ）が大きい変数ほど、その変数をスピルすることで他の変数をレジスタに割り付けやすくなり、即ち、そのスピルにより蒙る損失は小さくなるからである。

具体的には、情報生成部６２０は、プログラム６０を走査して、それぞれの変数を参照する命令を検出する。そして、情報生成部６２０は、その命令の数を変数ごとに集計する。そして、情報生成部６２０は、変数ごとに集計したその命令の数を、変数ごとの利得として記憶装置１２０に格納する。具体的には、変数ａ１−４、変数ｂ１−５、および、変数ｃ１−４の何れについても、その使用回数は１回なので、利得は１である。

また、情報生成部６２０は、記憶装置１２０に記憶された干渉情報６２Ａを走査して、それぞれの変数に接続されたエッジの数を算出する。そして、情報生成部６２０は、算出したその数を次数として記憶装置１２０に格納する。そして、情報生成部６２０は、それぞれの変数について、その変数の利得を次数で割り算することによりコストを算出し、記憶装置１２０に格納する。

図６の説明に戻る。第１割付部６３０は、プログラム６０の中で使用されるそれぞれの変数に、予め定められた基準数以上のレジスタの中から予め定められた手順に従ってレジスタを選択して割り付ける。この割り付けの処理は、干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において行われる。仮に干渉関係にある変数の組に同一のレジスタを割り付けてしまうと、あるレジスタが同時に複数の変数の値を保持することとなって、プログラムが正常動作しないからである。

構成の具体例として、第１割付部６３０は、シンプリファイ部６３２およびセレクト部６３５を有する。詳細は後述するが、概要は概ね以下の通りである。シンプリファイ部６３２は、所定の基準に従って変数を選択してスタックにプッシュすると共に、プッシュしたその変数についての干渉関係を干渉情報６２Ａから除外する処理、を、割り付けるべき全ての変数をプッシュするまで繰り返す。

ここでいうスタックは、例えば、記憶装置１２０内に一時的に設けた作業用領域により実現される。そして、スタックは、ここでは、例えば、単にＬＩＦＯ（Ｌａｓｔ Ｉｎ Ｆｉｒｓｔ Ｏｕｔ）型の操作が可能なデータ構造を有する記憶領域をさす。また、予め定められた基準数とは、プログラム６０の実行に使用することのできるレジスタである物理レジスタの上限数を示す。

そして次に、セレクト部６３５は、そのスタックから変数をポップし、ポップしたその変数に、その変数と干渉関係にある他の変数に既に割り付けられているレジスタとは異なるレジスタを割り付ける処理、を、そのスタックが空になるまで繰り返す。この処理は、バイアス彩色と呼ばれる、非特許文献１に記載の技術に基づいて行われることが好ましい。これに代えて、この処理は、他の如何なるレジスタ割付アルゴリズムに基づいてもよい。

また、セレクト部６３５は、上記基準数の物理レジスタに、プログラム６０の実行には使用することのできない仮想的なレジスタである仮想レジスタを少なくとも１つ加えたレジスタの集合の中から、割り付けるべきレジスタを選択してもよい。なお、基準数、および、割付可能な物理レジスタについては、記憶装置１２０にあらかじめ記憶されていてもよい。また、コンパイラ装置１０の動作時に与えるパラメータに基づいて、コンパイラ装置１０が決定してもよい。例えば、コンパイル結果のプログラムをどの機種のコンピュータで動作させるかによって、使用するべき物理レジスタの数が定められてもよい。

この割り付け結果を割付結果６６とする。その一例を図１１に示す。
図１１は、本実施形態に係る割付結果６６の一例を示す。変数ａ１には物理レジスタｒ１が割り付けられる。変数ａ３−４のそれぞれには物理レジスタｒ１が割り付けられる。変数ｂ１−４のそれぞれには物理レジスタｒ２が割り付けられる。変数ｃ１−３のそれぞれには物理レジスタｒ１が割り付けられる。変数ｃ４には物理レジスタｒ２が割り付けられる。一方、変数ａ２には仮想レジスタｒ４が割り付けられ、変数ｂ５には仮想レジスタｒ３が割り付けられる。

なお、同一のレジスタが割り付けられ、かつ、代入命令の代入先および代入元の関係にある変数の組を、後の説明のためにグループ化して示す。具体的には、変数ａ３および変数ａ４はグループ化され、変数ｃ１−３はグループ化され、変数ｂ１−４はグループ化されている。

図６の説明に戻る。更新部６４０は、複数の変数に、第１割付部６３０により同一のレジスタが割り付けられ、かつ、当該複数の変数が代入情報６４Ａにおいて相互に対応付けられていることを条件に、当該複数の変数を新たな変数に置換する。例えば、更新部６４０は、プログラム６０の内容を書き換えてもよい。そして、更新部６４０は、当該複数の変数のそれぞれについての干渉関係を記憶装置１２０の干渉情報６２Ａから読み出して併合する。併合したその干渉関係は、当該新たな変数についての干渉関係となる。そして、更新部６４０は、生成したその干渉関係により干渉情報６２Ａを更新する。更新された干渉情報を干渉情報６２Ｂとする。これに加えて、更新部６４０は、代入情報６４Ａおよび優先度６５Ａを更新し、代入情報６４Ｂおよび優先度６５Ｂとして記憶装置１２０に格納してもよい。

図１２−１４にこれらの一例を示す。
図１２は、本実施形態に係る干渉情報６２Ｂの一例を示す。更新部６４０は、図１１において同一グループに分類された複数の変数を、新たな１つの変数に置換する。例えば、更新部６４０は、変数ｃ１−３を、変数ｃ１´に置換し、変数ａ３−４を、変数ａ３´に置換し、変数ｂ１−４を、変数ｂ１´に置換する。

これに伴い、更新部６４０は、置換する当該複数の変数を干渉グラフにおいて表している複数のノードを新たな１つのノードに置換する。そして、更新部６４０は、干渉グラフにおける当該複数のノードのそれぞれと他のそれぞれのノードとの間のエッジを、当該新たな１つのノードと当該他のそれぞれのノードとの間のエッジに置換する。

具体的には、置換前の変数ｃ１は変数ａ２、ｂ３、ｂ４およびｂ５のそれぞれと干渉関係にある。また、置換前の変数ｃ２は、変数ａ２およびｂ５のそれぞれと干渉関係にある。また、置換前の変数ｃ３は、変数ａ２およびｂ５のそれぞれと干渉関係にある。更新部６４０は、変数ｃ１−３のそれぞれとの間で干渉関係にある変数の和集合を算出する。この結果、変数ａ２、ｂ３、ｂ４およびｂ５が和集合として算出される。

そして、更新部６４０は、置換後の変数ｃ１´と、この和集合に含まれる各変数との間の干渉関係を、干渉情報６２Ｂに含めて生成する。但し、変数ｂ３および変数ｂ４もまた、新たな変数ｂ１´に変換される。従って、変数ｂ３および変数ｂ４についての干渉関係も、新たな変数ｂ１´についての干渉関係に置換される。この結果、更新部６４０は、変数ｃ１´を、変数ａ２、ｂ１´およびｂ５のそれぞれと干渉することを示す干渉関係を、干渉情報６２Ｂに含めて生成する。

図１３は、本実施形態に係る代入情報６４Ｂの一例を示す。更新部６４０は、置換前の当該複数の変数の間で相互に値を代入する命令をプログラム６０から削除する。また、更新部６４０は、プログラム６０において、置換前の当該複数の変数の何れかと他の変数との間の代入命令を、置換後の当該新たな１つの変数と当該他の変数との間の代入命令に置換する。

例えば、置換前の変数ｃ１−３の間で相互に値を代入する命令、例えば変数ｃ１から変数ｃ２に値を代入する命令は削除される。そして、変数ｃ１−３のうちの変数ｃ３から、変数ｃ４へ値を代入する命令は、置換後の変数ｃ１´から変数ｃ４へ値を代入する命令に置換される。

そして、更新部６４０は、代入命令を置換または削除したプログラム６０を走査して、改めて代入命令を検出して、その検出結果に基づいて代入情報６４Ｂを生成する。例えば、更新部６４０は、変数ｃ１´および変数ｃ４が代入命令の代入先および代入元の関係にあることを示す情報を、代入情報６４Ｂに含めて生成してよい。

図１４は、本実施形態に係る優先度６５Ｂの一例を示す。更新部６４０は、置換前の当該複数の変数のそれぞれに対応する利得を合計して、置換後の当該新たな１つの変数に対応する利得とする。また、更新部６４０は、干渉情報６２Ｂに基づいて、置換後の当該新たな１つの変数を干渉グラフにおいて表すノードの次数を算出する。

置換前の変数ｃ１−３のそれぞれには、利得１が対応付けられている。従って、更新部６４０は、それらの利得を合計した利得を置換後の変数ｃ１´に対応付けて算出し、優先度６５Ｂに含めて記憶装置１２０に格納する。また、置換後の変数ｃ１´を干渉グラフ上で表すノードの次数は、干渉情報６２Ｂにおいて３である。従って、更新部６４０は、次数３を変数ｃ１´に対応付けて算出し、優先度６５Ｂに含めて記憶装置１２０に格納する。

このように算出された利得および次数に基づいて、更新部６４０は、各変数をスピルすることによって蒙る損失を算出して、代入情報６４Ｂに含めて記憶装置１２０に格納してもよい。図６の説明に戻る。

第１割付部６３０によるレジスタ割付および更新部６４０による情報の更新が予め定められた回数行われたかどうかなど、所定の終了条件が成立したかどうかを判断する。終了条件が成立しない場合には、変数の置換後のプログラムについて、第１割付部６３０が再度レジスタ割付を行う。

その場合には、更新部６４０は、干渉情報６２Ｂを更新して干渉情報６２Ｃを生成し、代入情報６４Ｂを更新して代入情報６４Ｃを生成し、優先度６５Ｂを更新して優先度６５Ｃを生成する。このように、繰り返しの回数に応じて各種情報が順次更新されていく。なお、以降の説明ではここで繰り返しは無いものとし、更新部６４０により最終的に生成される情報は干渉情報６２Ｂ、代入情報６４Ｂ、および、優先度６５Ｂとする。

第２割付部６５０は、第１割付部６３０により同一のレジスタが割り付けられた当該複数の変数に代えて当該新たな変数を使用するプログラム６０中の各変数に、第１割付部６３０による上記予め定められた手順と同一の手順に従って上記基準数と同数の物理レジスタの中からレジスタを選択して割り付ける。この割り付けは、第１割付部６３０による割付の結果とは無関係に、何れの変数にもレジスタをまだ割り付けていない状態から行われる。また、この割り付けは、更新した干渉情報６２Ｂに基づく干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において行われる。そのような割付ができない場合には、第２割付部６５０は、所定の基準に従ってある変数をスピルすると決定する。

構成の具体例は概ね第１割付部６３０と同一である。第２割付部６５０は、シンプリファイ部６５２およびセレクト部６５５を有する。これらの詳細については後述する。第２割付部６５０による割り付けの結果を割付結果６８とする。その一例を図１５に示す。

図１５は、本実施形態に係る割付結果６８の一例を示す。第２割付部６５０は、変数ａ１、変数ｃ１´、および変数ｃ４のそれぞれにレジスタｒ１を割り付ける。また、第２割付部６５０は、変数ａ３´および変数ｂ１´のそれぞれに、レジスタｒ２を割り付ける。また、第２割付部６５０は、変数ａ２および変数ｂ５をスピルすると決定する。図６の説明に戻る。

スピル生成部６６０は、第２割付部６５０がある第１変数をスピルすると決定したことを条件に、その第１変数に関するスピル用の各種命令をプログラム６０中に生成する。例えば、スピル生成部６６０は、その第１変数に対する変数値の代入命令を、当該変数値を格納したレジスタの値をメモリ上の領域に格納する命令に変換する。また、スピル生成部６６０は、当該第１変数の変数値を参照する命令を、当該変数値をメモリ上の領域から読み出してレジスタに格納し、当該レジスタの値を参照する命令に変換する。

出力部６７０は、第２割付部６５０が変数にレジスタを割り付け、かつ、スピル生成部６６０がスピルのための命令を生成したプログラムを、結果プログラム６９として第２最適化部１３０などに対し出力する。スピルのための命令とは、例えば、変数値の定義の毎に、当該変数値を一時的に格納したレジスタからメモリへ当該変数値を書込む命令と、その変数値の使用の毎にその領域からレジスタに値を読み出す命令である。そして、その後、変数変換部６００は、この結果プログラム６９中に含まれる各レジスタを変数とみなして、上記と同様の処理を繰り返してもよい。

図１６は、本実施形態に係る出力プログラム２４の一例を示す。まず、変数ａ１はレジスタｒ１に割り付けられている。このため、コンパイラ装置１０は、変数ａ１に値を代入する命令を、例えば、レジスタｒ１にメモリから値を読み出すロード命令にコンパイルする。

なお、図１６に示すＬＯＡＤ命令は、第２オペランドから第１オペランドに値を読み出す命令を示す。また、［………］はアドレス演算子であり、メモリ中の………によって示されるアドレスからデータを読み出す演算を示す。

また、コンパイラ装置１０は、変数ａ１を参照する命令を、レジスタｒ１を参照する命令にコンパイルする。この命令は、例えば、レジスタｒ１の内容をアドレスとして、メモリ中のそのアドレスから値を読み出す命令である。

一方で、変数ａ２はスピルすることが決定されている。従って、スピル生成部６６０は、その変数ａ２に対し変数ａ１から変数値を代入する代入命令を、当該変数値を格納したレジスタｒ２の値をメモリ上の領域［ｍｅｍＡ］に格納するストア命令に変換する。なお、図１６に示すＳＴＯＲＥ命令は、第１オペランドから第２オペランドが示す領域に対し値を書込む命令を示す。

この領域は、変数ａの値を格納するために予め確保される領域である。この変数がメソッドまたは関数の局所変数の場合において、この領域は例えばスタック中に確保されてもよい。即ち、コンパイラ装置１０がこのような領域を確保するための命令を各メソッドまたは各関数の先頭部分に生成してよい。

次に、変数ｂ１−４はレジスタｒ２に割り付けられている。このため、コンパイラ装置１０は、変数ｂ１に値を代入する命令を、例えば、レジスタｒ２にメモリから値を読み出すロード命令にコンパイルする。

また、第２割付部６５０は、その他に変数ｂ１−４を参照する命令を、レジスタｒ２を参照する命令に置換する。例えば、レジスタｒ２の内容をアドレスとしてメモリ中のそのアドレスから値を読み出す命令が生成されてもよい。

この結果、変数ｂ１から変数ｂ２に変数値を代入する命令は、レジスタｒ２からレジスタｒ２に値を代入する命令に置換される。第２最適化部１３０は、このような代入先および代入元を同一とする代入命令をプログラム６０から削除する。この結果、出力プログラム２４においては、変数ｂを参照する本来の命令のみが残り、変数間の代入命令は除外されている。

同様に、変数ｂ２から変数ｂ３への代入命令、変数ｂ３から変数ｂ４への代入命令、変数ａ３から変数ａ４への代入命令、変数ｃ１から変数ｃ２への代入命令、変数ｃ２から変数ｃ３への代入命令、および、変数ｃ３から変数ｃ４への代入命令も削除される。

一方で、変数ｂ５はスピルすることが決定されている。従って、スピル生成部６６０は、その変数ｂ５に対し変数ｂ４から変数値を代入する代入命令を、当該変数値を格納したレジスタｒ２の値をメモリ上の領域［ｍｅｍＢ］に格納するストア命令に変換する。

また、変数ｃ１−４はレジスタｒ１に割り付けられている。このため、コンパイラ装置１０は、変数ｃ１に値を代入する命令を、例えば、レジスタｒ１にメモリから値を読み出すロード命令にコンパイルする。

そして、コンパイラ装置１０は、変数ｃ１−４を参照する命令を、レジスタｒ１を参照する命令にコンパイルする。この命令は、例えば、レジスタｒ１の内容をアドレスとして、メモリ中のそのアドレスから値を読み出す命令である。

変数ａ２は、上述のようにスピルすることが決定されている。そして、変数ａ２に対する変数値の代入命令はストア命令にコンパイルされている。この場合において、スピル生成部６６０は、変数ａ２の変数値を参照する命令を、当該変数値をメモリ上の領域から読み出してレジスタに格納し、当該レジスタの値を参照する命令に変換する。例えば、メモリ上の領域［ｍｅｍＡ］から値を読み出してレジスタｒ２に格納するロード命令、および、そのレジスタｒ２の内容をアドレスとしてメモリ上のそのアドレスから値を読み出すロード命令が生成される。

同様に、変数ｂ５は、上述のようにスピルすることが決定されている。そして、変数ｂ５に対する変数値の代入命令はストア命令にコンパイルされている。この場合において、スピル生成部６６０は、変数ｂ５の変数値を参照する命令を、当該変数値をメモリ上の領域から読み出してレジスタに格納し、当該レジスタの値を参照する命令に変換する。例えば、メモリ上の領域［ｍｅｍＢ］から値を読み出してレジスタｒ２に格納するロード命令、および、そのレジスタｒ２の内容をアドレスとしてメモリ上のそのアドレスから値を読み出すロード命令が生成される。

以上のように、変数の代入・参照はレジスタのロード・ストアなどの各種命令に変換される。但し、スピルされたことが決定された変数について、その変数に値を代入する命令は、メモリにデータをストアする命令に変換される。また、その変数の値を参照する命令はメモリからデータをロードする命令に変換される。また、プログラム６０により生成された代入命令は、生存区間の連続する複数の変数に同一のレジスタが割り付けられていることを条件に削除される。

以上、図１−１６を参照して説明したように、本実施形態に係るコンパイラ装置１０によれば、一旦は細かく分割した変数を、一度目のレジスタ割付の結果を利用して部分的に融合する。そして、コンパイラ装置１０は、融合した変数について改めてレジスタ割付を行う。このため、結果として適度に分割した変数をレジスタ割付の対象とすることができる。これにより、コンパイラ装置１０は、変数を分割することによるスピル低減と、変数を融合することによるレジスタ間コピーの削減とをバランス良く達成して、プログラムの効率を全体として向上できる。

より詳細には、第２割付部６５０が第１割付部６３０と同一の手順に従ってレジスタ割付を行うことで、上記の適度な分割が実現される。その理由の概略を説明する。いま、第１割付部６３０および第２割付部６５０の間に行われる変数の置換および情報の併合（まとめて変数の融合と呼ぶ）により、可能性として下記の利点および欠点が生じる場合がある。

［利点］変数ｘ１と変数ｘ２を融合すると、変数ｘ１および変数ｘ２の双方と干渉関係にある変数ｙの次数が１減少する。したがって、変数ｙをレジスタに割り付け易くなる
［欠点］変数ｘ１と変数ｘ２を融合すると、融合後の変数ｘと干渉関係にある他の変数の数は、融合前の変数ｘ１および変数ｘ２の何れかの次数と等しいかそれより多くなる。従って、変数ｘをレジスタに割り付けにくくなる。

但し、変数の融合は、第１割付部６３０により同一のレジスタを割り付けたことを条件に行われる。第２割付部６５０が第１割付部６３０と同一の手順・基準でレジスタを割り付けると、多くの場合、融合前の各変数ｘ１およびｘ２に割り付けたレジスタが、融合後の変数ｘにも割り付けられることが期待される。また、変数ｘ１および変数ｘ２のそれぞれと干渉関係にある他の変数にも融合前後で同一のレジスタが割り付けられることが期待される。

従って、たとえ融合後の変数ｘの次数が見かけ上増加したとしても、変数ｘ１−２およびそれと干渉関係にある他の変数は、第１割付部６３０によりレジスタに割り付けられていたのであるから、第２割付部６５０によってもレジスタに割り付けられることが期待される。即ち、上記［欠点］は、見かけ上の次数の増加はもたらすものの、多くの場合、融合後の変数ｘにレジスタが割り当てられるかどうかは、融合の前後で変化しないことが期待される。一方、上記［利点］に関して、次数が減少することは、レジスタ割り付けの自由度を向上させて、効率向上のための様々な機会を提供できる。

次に、図１７から図２０を参照して、本実施形態におけるレジスタ割付のより詳しい処理の流れを説明する。なお、図１７から図２０に示す処理は、ベースとなるレジスタ割付手順として非特許文献５に記載された技術を利用しているが、レジスタ割付手順はこれに限られない。

図１７は、本実施形態に係るレジスタ割付部１１０が変数にレジスタを割り付ける処理の流れを示す。変数変換部６００は、対象プログラム２２内の各変数を複数の変数に変換する（Ｓ１７００）。この変換は、例えば、変数変換部６００が、ある変数の生存区間を分割して、分割した生存区間ごとにその変数の値を保持する複数の変数を生成することで実現されてよい。

代入命令生成部６１０は、変換した当該複数の変数のうちのある変数から他の変数への代入命令を対象プログラム２２中に生成する（Ｓ１７１０）。例えば、変数ａが変数ａ１および変数ａ２に変換された場合、代入命令生成部６１０は、変数ａ１から変数ａ２に値を代入する命令を生成する。このように、代入命令生成部６１０は、それぞれの生存区間が互いに連続する変数の組について、生存区間の境界に代入命令を生成してよい。

情報生成部６２０は、対象プログラム２２中で使用される複数の変数についての干渉情報６２Ａ、代入情報６４Ａおよび優先度６５Ａを生成して、記憶装置１２０に格納する（Ｓ１７２０）。そして、第１割付部６３０は、プログラム６０の中で使用されるそれぞれの変数に、予め定められた基準数の物理レジスタ、および、仮想レジスタの中から予め定められた手順に従ってレジスタを選択して割り付ける（Ｓ１７３０）。

具体的には、第１割付部６３０は、レジスタ割付の候補となる第１の変数について、当該第１の変数を代入元とした代入先の第２の変数、または、当該第１の変数を代入先とした代入元の第２の変数を、代入情報６４Ａに基づいて選択する。そして、第１割付部６３０は、干渉情報６２Ａに基づく干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において当該第１の変数に割付可能なレジスタのうち、選択した当該第２の変数に既に割り付けたレジスタと同一のレジスタを、当該第１の変数に割り付ける。

処理段階の具体例として、シンプリファイ部６３２は、シンプリファイ処理を行う（Ｓ１７３２）。また、セレクト部６３５は、セレクト処理を行う（Ｓ１７３５）。これらの処理の詳細は後述する。

更新部６４０は、第１割付部６３０により同一のレジスタが割り付けられ、かつ、代入情報６４Ａにおいて互いに対応付けられた複数の変数を干渉グラフ上で融合する（Ｓ１７４０）。この融合の処理は、主に、変数の置換、および、各種情報の更新、によって実現される。具体的には、まず、更新部６４０は、第１割付部６３０により仮想レジスタを含め同一のレジスタが割り付けられ、かつ、代入情報６４Ａにおいて互いに対応付けられたた複数の変数を新たな変数に置換する。例えば、更新部６４０は、プログラム６０の内容を書き換えてもよい。

そして、更新部６４０は、当該複数の変数のそれぞれについての干渉関係を記憶装置１２０の干渉情報６２Ａから読み出して併合する。例えば、更新部６４０は、当該複数の変数の少なくとも何れか１つとの間で干渉関係にある他の変数を、記憶装置１２０に記憶された干渉情報に基づき検索し、当該干渉関係を、当該複数の変数に代わる新たな変数と当該他の変数との間の干渉関係に変更する。

併合したその干渉関係は、当該新たな変数についての干渉関係となる。そして、更新部６４０は、生成したその干渉関係により干渉情報６２Ａを更新する。さらに、更新部６４０は、干渉関係を併合する当該複数の変数については、当該複数の変数についての代入情報を併合して記憶装置１２０の代入情報６４Ａを更新してよい。

次に、第２割付部６５０は、更新部６４０が、その更新の処理を予め定められた回数行ったか否かを、第１のレジスタ割付の終了条件として判断する（Ｓ１７５０）。この回数は、例えば１回などの極めて少ない回数でよい。予め定められた回数行っていない場合には（Ｓ１７５０：ＮＯ）、第１割付部６３０は、変数の置換されたプログラム６０および更新された干渉情報６２Ｂ等に基づいて、既に割り付けた結果に関わらず、何れの変数にもレジスタを割り付けていない状態からレジスタ割付を行う。

これに代えて、第２割付部６５０は、更新の処理の回数が２回以上の場合においては、第１割付部６３０によるレジスタ割り付けの結果が、第１割付部６３０による以前のレジスタ割り付けの結果と等しいかどうかを判断してよい。この場合、等しい場合には、第２割付部６５０は、終了条件が成立したものとしてＳ１７６０に処理を進める。異なる場合には、第１割付部６３０はレジスタ割付を再び行う。このように、第１割付部６３０は、情報の更新の毎にレジスタ割付を行い、更新部６４０は、レジスタ割付の毎に情報を更新するというように、第１割付部６３０および更新部６４０は相互に処理を繰り返してもよい。これにより繰り返しの毎に徐々にプログラムの効率を向上させることができる。

終了条件が成立したことを条件に（Ｓ１７５０：ＹＥＳ）、第２割付部６５０は、第１割付部６３０により同一のレジスタが割り付けられた当該複数の変数に代えて当該新たな変数を使用するプログラム６０中の各変数に、第１割付部６３０と同一の手順に従って上記基準数のレジスタの中からレジスタを選択して割り付ける（Ｓ１７６０）。この割り付けは、第１割付部６３０による割付の結果とは無関係に、何れの変数にもレジスタをまだ割り付けていない状態から行われる。そのような割付ができない場合には、第２割付部６５０は、所定の基準に従ってある変数をスピルすると決定する。

具体的には、第２割付部６５０は、レジスタ割付の候補となる第１の変数について、当該第１の変数を代入元とした代入先の第２の変数、または、当該第１の変数を代入先とした代入元の第２の変数を、更新後の代入情報６４Ｂに基づいて選択する。そして、第２割付部６５０は、干渉情報６２Ｂに基づく干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において当該第１の変数に割付可能なレジスタのうち、選択した当該第２の変数に既に割り付けたレジスタと同一のレジスタを、当該第１の変数に割り付ける。

処理段階の具体例として、シンプリファイ部６５２は、シンプリファイ処理を行う（Ｓ１７６２）。また、セレクト部６５５は、セレクト処理を行う（Ｓ１７６５）。これらの処理の詳細は後述する。

スピル生成部６６０は、第２割付部６５０がある第１変数をスピルすると決定したことを条件に、その第１変数に関するスピル用の各種命令をプログラム６０中に生成する（Ｓ１７７０）。例えば、スピル生成部６６０は、その第１変数に対する変数値の代入命令を、当該変数値を格納したレジスタの値をメモリ上の領域に格納する命令に変換する。また、スピル生成部６６０は、当該第１変数の変数値を参照する命令を、当該変数値をメモリ上の領域から読み出してレジスタに格納し、当該レジスタの値を参照する命令に変換する。

出力部６７０は、予め定められた終了条件が成立したか否かを判断する（Ｓ１７８０）。この終了条件は、第２割付部６５０が何れの変数もスピルしなかったことであってよい。即ちこれにより、レジスタを割り付けるべき変数の生存区間が、繰り返しの毎に短くなってゆき、変数にレジスタを割り付けやすくなってゆく。そして、何れかの繰り返しの時点において全ての変数にレジスタを割り付けられるようになり、この終了条件が成立する。これに代えて、コンパイラ装置１０が、スピルのためのレジスタを予め確保している場合には、ここの終了条件は常に成立する。即ち、上記Ｓ１７００からＳ１７７０は１度だけ処理される。終了条件が成立したことを条件に（Ｓ１７８０：ＹＥＳ）、出力部６７０は、変数にレジスタを割り付けたプログラムを出力して、図１７の処理を終了する。

終了条件が成立していなければ（Ｓ１７８０：ＮＯ）、出力部６７０はＳ１７００に処理を戻す。この場合には、レジスタ割付部１１０は、割り付けたレジスタをあたかも変数であるかのようにみなして、上記の処理を繰り返す。

図１８は、Ｓ１７３２およびＳ１７６２における処理の流れの詳細を示す。シンプリファイ部６３２は、干渉関係にある変数の数が、プログラム６０の実行に使用可能なレジスタの上限数として予め定められた上記基準数未満の変数を干渉情報６２Ａに基づいて検索する（Ｓ１８００）。そして、シンプリファイ部６３２は、そのような変数が検索されなければ（Ｓ１８１０：ＮＯ）、優先度６５Ａに基づく優先度の最も低い変数を選択する（Ｓ１８２０）。

そして、シンプリファイ部６３２は、当該選択した変数をスタックにプッシュする（Ｓ１８３０）。また、シンプリファイ部６３２は、当該選択した変数についての干渉関係を干渉情報６２Ａから除外する（Ｓ１８４０）。シンプリファイ部６３２は、割り付けるべき全ての変数がプッシュされていなければ（Ｓ１８５０：ＮＯ）、Ｓ１８００に処理を戻して、割り付けるべき全ての変数がプッシュされるまで上記処理を繰り返す。
なお、シンプリファイ部６５２がＳ１７６２として行う処理も、上記干渉情報６２Ａに代えて干渉情報６２Ｂに基づき、上記優先度６５Ａに代えて優先度６５Ｂに基づくことの他は、図１８に示す処理と略同一であるから説明を省略する。

なお、スタックに変数をプッシュする、とは、その変数を識別するデータをスタック型のデータ構造を有する記憶領域に記憶することをいう。また、スタックから変数をポップする、とは、その変数を識別するデータをスタック型のデータ構造を有する記憶領域から読み出すことをいう。

図１９は、Ｓ１７３５における処理の流れの詳細を示す。セレクト部６３５は、スタックが空か否かを判断する（Ｓ１９００）。スタックが空でなければ（Ｓ１９００：ＮＯ）、セレクト部６３５は、スタックから変数をポップする（Ｓ１９１０）。そして、セレクト部６３５は、ポップしたその変数と干渉関係にある他の変数にはまだ割り当てられていない物理レジスタである未割当レジスタを検索する（Ｓ１９２０）。

これは、例えば以下のように実現される。セレクト部６３５は、ポップしたその変数を干渉グラフにおいて表すノードに直接連結された他の全てのノードを干渉情報６２Ａから検索する。そして、セレクト部６３５は、検索した他の全てのノードに既に割り当てたレジスタの集合を、例えば記憶装置１２０などに記憶した割り付け結果を示す情報に基づき選択する。そして、セレクト部６３５は、予め定められた上記基準数のレジスタから、選択した当該レジスタの集合を除外した残りのレジスタを未割当レジスタとして検索する。

次に、セレクト部６３５は、ポップしたその変数を代入元とする代入先の変数、または、ポップしたその変数を代入先とする代入元の変数を、代入情報６４Ａに基づいて選択する（Ｓ１９３０）。これは、例えば代入情報６４Ａから、ポップしたその変数との間の代入関係が数値１である他の変数を検索することによって実現される。

次に、セレクト部６３５は、未割当レジスタのうち、選択した当該変数に既に割り付けられたレジスタがあるかどうか判断する（Ｓ１９４０）。そのようなレジスタがあれば（Ｓ１９４０：ＹＥＳ）、セレクト部６３５は、そのレジスタを選択して、ポップしたその変数に割りつける（Ｓ１９９０）。

一方、選択した当該変数に既に割り付けられたレジスタが未割当レジスタの中に無ければ（Ｓ１９４０：ＮＯ）、セレクト部６３５は、他の未割当レジスタがあるかどうか判断する（Ｓ１９５０）。他の未割当レジスタがあれば（Ｓ１９５０：ＹＥＳ）、セレクト部６３５は、そのレジスタを選択して、ポップしたその変数に割り付ける（Ｓ１９９０）。

未割当レジスタがなければ（Ｓ１９５０：ＮＯ）、セレクト部６３５は、ポップした当該変数と干渉関係にある他の変数にまだ割り当てられていない仮想レジスタである未割当仮想レジスタのうち、ポップした当該変数と代入情報６４Ａにおいて対応付けられた他の変数（即ち、ポップした当該変数を代入先とする代入元の変数またはポップした当該変数を代入元とする代入先の変数）に既に割り当てられた仮想レジスタがあるかどうかを判断する（Ｓ１９６０）。

そのような仮想レジスタがあれば（Ｓ１９６０：ＹＥＳ）、セレクト部６３５は、その仮想レジスタを選択して、ポップしたその変数に割り付ける（Ｓ１９９０）。そのような仮想レジスタがなければ（Ｓ１９６０：ＮＯ）、セレクト部６３５は、ポップした当該変数と干渉関係にある他の変数にまだ割り当てられておらず、かつ、さらに他の変数に既に割り付けた仮想レジスタがあるかどうかを判断する（Ｓ１９７０）。

ポップしたその変数と干渉関係にある他の変数にはまだ割り付けられていないレジスタが仮想レジスタも含め存在しなければ（Ｓ１９７０：ＹＥＳ）、セレクト部６３５は、新たに仮想レジスタを１つ生成する（Ｓ１９８０）。そして、セレクト部６３５は、生成したその仮想レジスタを、ポップしたその変数に割り付ける（Ｓ１９９０）。以上の処理を、セレクト部６３５は、スタックが空になるまで（Ｓ１９００：ＹＥＳ）繰り返す。

図２０は、Ｓ１７６５における処理の流れの詳細を示す。セレクト部６５５は、スタックが空か否かを判断する（Ｓ２０００）。スタックが空でなければ（Ｓ２０００：ＮＯ）、セレクト部６５５は、スタックから変数をポップする（Ｓ２０１０）。そして、セレクト部６５５は、ポップしたその変数と干渉関係にある他の変数にはまだ割り当てられていない物理レジスタである未割当レジスタを検索する（Ｓ２０２０）。

これは、例えば以下のように実現される。セレクト部６５５は、ポップしたその変数を干渉グラフにおいて表すノードに直接連結された他の全てのノードを干渉情報６２Ｂから検索する。そして、セレクト部６５５は、検索した他の全てのノードに既に割り当てたレジスタの集合を、例えば記憶装置１２０などに記憶した割り付け結果を示す情報に基づき選択する。そして、セレクト部６５５は、予め定められた上記基準数のレジスタから、選択した当該レジスタの集合を除外した残りのレジスタを未割当レジスタとして検索する。

次に、セレクト部６５５は、ポップしたその変数を代入元とする代入先の変数、または、ポップしたその変数を代入先とする代入元の変数を、代入情報６４Ｂに基づいて選択する（Ｓ２０３０）。これは、例えば代入情報６４Ｂから、ポップしたその変数との間の代入関係が数値１である他の変数を検索することによって実現される。

次に、セレクト部６５５は、未割当レジスタのうち、選択した当該変数に既に割り付けられたレジスタがあるかどうか判断する（Ｓ２０４０）。そのようなレジスタがあれば（Ｓ２０４０：ＹＥＳ）、セレクト部６５５は、そのレジスタを選択して、ポップしたその変数に割りつける（Ｓ２０７０）。

一方、選択した当該変数に既に割り付けられたレジスタが未割当レジスタの中に無ければ（Ｓ２０４０：ＮＯ）、セレクト部６５５は、他の未割当レジスタがあるかどうか判断する（Ｓ２０５０）。他の未割当レジスタがあれば（Ｓ２０５０：ＹＥＳ）、セレクト部６５５は、そのレジスタを選択して、ポップしたその変数に割り付ける（Ｓ２０７０）。

一方、未割当レジスタを選択できなければ（Ｓ２０５０：ＮＯ）、セレクト部６５５は、ポップしたその変数をスピルすると決定する（Ｓ２０６０）。以上の処理を、セレクト部６５５は、スタックが空になるまで（Ｓ２０００：ＹＥＳ）繰り返す。

次に、図２１から図３２を参照して、コンパイルの対象とする他のプログラムについて、変数にレジスタを割り付ける具体例を示す。
図２１は、本実施形態に係るコンパイラ装置１０がコンパイルの対象とする他のプログラムについて、変数の干渉関係及び優先度の一例を示す。

（ａ）に示すように、変数変換の結果、プログラムは変数ｐ１およびｐ２、変数ｑ１およびｑ２、変数ｒ１およびｒ２ならびに変数ｓを含む。そして、変数ｐ１は変数ｑ１、変数ｑ２、変数ｒ１、変数ｒ２および変数ｓとの間でそれぞれ干渉関係にある。また、変数ｐ２は、変数ｑ１、変数ｑ２、変数ｒ１、変数ｒ２および変数ｓとの間でそれぞれ干渉関係にある。さらに、変数ｑ１は変数ｒ２と干渉関係にあり、変数ｑ２は変数ｒ１および変数ｓとそれぞれ干渉関係にある。

また、アルファベット部分が等しい変数の組は、代入命令の代入元および代入先となっている。例えば変数ｐ１および変数ｐ２の一方を代入先とする代入命令は、変数ｐ１および変数ｐ２の他方を代入元としている。この代入命令は、図７の例のようにある変数を変換した結果として生成された代入命令であってもよいが、入力プログラムに元々記述されていた代入命令であってもよい。

何れの変数もプログラム中で１回参照されるので、いずれの変数についても利得（ｘ）は１である。また、変数ｐ１、ｐ２、ｑ１、ｑ２、ｒ１、ｒ２およびｓのそれぞれの次数（ｙ）は、５、５、３、４、４、３および４である。従って、それぞれの変数について、その変数をスピルすることによって蒙る損失のコスト（ｘ／ｙ）は、それぞれ、０．２、０．２、０．３３３３、０．２５、０．２５、０．３３３３および０．２５である。また、レジスタ割り付け前においてスタックは空である。

図２２は、シンプリファイ処理（Ｓ１７３２）によってある干渉関係が干渉情報から除外される処理の第１手順を示す。この例において、プログラムの実行に使用することができる物理レジスタの上限数は３個である。図２１の干渉グラフを参照すると、何れの変数の次数も３以上である。従って、シンプリファイ部６３２は、レジスタに割り付ける優先度の最も低い変数を選択する。

優先度が最も低いということは、スピルによって蒙る損失が最も小さいということである。この例では変数ｐ１およびｐ２のコストが０．２で最も小さい。従って、シンプリファイ部６３２は、そのうち任意の一方、例えば変数ｐ１を選択して、スタックにプッシュする。

変数ｐ１のプッシュに応じて、シンプリファイ部６３２は、干渉情報および優先度を更新する。この結果、変数ｑ１、変数ｑ２、変数ｒ１、変数ｒ２および変数ｓの次数はそれぞれ１減少して、減少後の次数は２、３、３、２および３となる。また、コストはこの次数を用いて再計算される。

図２３は、シンプリファイ処理（Ｓ１７３２）によって次の干渉関係が干渉情報から除外される処理の第２手順を示す。図２２の干渉グラフを参照すると、変数ｑ１およびｒ２の次数が基準数である３未満である。従って、シンプリファイ部６３２は、これらの変数を選択してスタックにプッシュする。これらの変数の間でプッシュされる順序は何れかに限定されなくてよい。そして、シンプリファイ部６３２は、選択したこれらの変数についての干渉関係を干渉情報から除外する。

この結果、スタックには、底側から順に変数ｐ１、ｑ１およびｒ２が格納される。変数ｑ１およびｒ２のプッシュに応じて、シンプリファイ部６３２は、干渉情報および優先度を更新する。この結果、変数ｐ２の次数が２減少して３となる。また、コストはこの次数を用いて再計算される。

図２４は、シンプリファイ処理（Ｓ１７３２）によって更に次の干渉関係が干渉情報から除外される処理の第３手順を示す。図２３のグラフを参照すると、何れの変数の次数も基準数３である。従って、シンプリファイ部６３２は、レジスタに割り付ける優先度の最も低い変数を選択する。

この例では何れの変数のコストも同じである。そのような場合、シンプリファイ部６３２は、任意の変数を選択してプッシュしてもよい。これに代えて、シンプリファイ部６３２は、代入情報に基づいて、既にプッシュした変数を代入元とする代入先の変数、または、既にプッシュした変数を代入先とする代入元の変数を選択し、その変数をプッシュしてよい。例えば、変数ｐ２が選択されてプッシュされる。

この結果、スタックには、底側から順に変数ｐ１、ｑ１、ｒ２およびｐ２が格納される。変数ｐ２のプッシュに応じて、シンプリファイ部６３２は、干渉情報および優先度を更新する。この結果、変数ｑ２、ｒ１およびｓの次数がそれぞれ１減少して２となる。また、コストはこの次数を用いて再計算される。

図２５は、シンプリファイ処理（Ｓ１７３２）によって更に次の干渉関係が干渉情報から除外される処理の第４手順を示す。図２４のグラフを参照すると、何れの変数の次数も基準数３未満である。従って、シンプリファイ部６３２は、これらの変数を任意の順序で選択してスタックにプッシュする。この結果、スタックには、底側から順に変数ｐ１、ｑ１、ｒ２、ｐ２、ｑ２、ｒ１およびｓが格納される。

図２６は、セレクト処理（Ｓ１７３５）によって変数にレジスタが割り付けられる処理の第１手順を示す。セレクト部６３５は、グラフを再構築しながら、変数をスタックから順次ポップして、ポップした変数にレジスタを割り付ける。割り付けは、干渉関係にある変数の組に同一のレジスタを割り付けないという条件の下行われる。また、この割り付けは、各レジスタを色彩とし、干渉グラフの各ノードを、互いにエッジで直接連結されたノードの組を同一の色彩で彩色しない範囲内で各色彩で彩色する問題に置き換えることができる。

具体的には、セレクト部６３５は、まず変数ｓをポップすると、干渉グラフからは何れの干渉関係も除外されているので、変数ｓを示すノードを任意の色彩で彩色する。そして次に、セレクト部６３５は、変数ｒ１をポップすると、その変数ｒ１と、既にポップされた変数ｓとの間の干渉関係を干渉情報に追加する。

そして、セレクト部６３５は、追加したその干渉関係に基づき、変数ｒ１を、それと干渉関係にある変数ｓに既に彩色した色彩とは異なる色彩に彩色する。そして次に、セレクト部６３５は、変数ｑ２をポップすると、その変数ｑ２と、既にポップされた変数ｒ１およびｓとの間の干渉関係を干渉情報に追加する。セレクト部６３５は、変数ｑ２に、既にポップされた変数ｒ１およびｓに既に彩色されたいずれの色彩とも異なる色彩を彩色する。

この結果、変数ｑ２は、第１レジスタを示す色彩「黄色」で彩色され、変数ｒ１は、第２レジスタを示す色彩「緑」で彩色され、変数ｓは、第３レジスタを示す色彩「青」で彩色される。スタックからは、変数ｑ２、変数ｒ２および変数ｓが取り除かれる。

なお、このような処理を実現可能とするためには、干渉情報の取り扱いとして下記の点に注意することが望ましい。まず、干渉グラフは一旦削除された後に、当初の干渉関係に基づいて、当初の干渉グラフとして再構築される。従って、当初の干渉グラフそれ自体を削除してしまうと、当初の干渉グラフを再構築することはできない。

このため、シンプリファイ部６３２は、シンプリファイ処理の前に、元の干渉グラフを複写して作業用の干渉グラフを生成して記憶装置１２０に格納することが望ましい。そして、シンプリファイ部６３２は、その作業用の干渉グラフを更新することで、その干渉グラフから干渉関係を徐々に取り除く。一方、セレクト部６３５は、その作業用の干渉グラフではなく元の干渉グラフを参照して変数間の干渉関係を判断したうえで、作業用の干渉グラフを再構築する。これにより、当初の干渉グラフを適切に再構築できる。

図２７は、セレクト処理（Ｓ１７３５）によって変数にレジスタが割り付けられる処理の第２手順を示す。次に、セレクト部６３５は、変数ｐ２をスタックからポップする。セレクト部６３５は、変数ｐ２と、既にポップされた変数ｑ２、ｒ１およびｓとの間の干渉関係を再構築する。

そして、セレクト部６３５は、ポップされた変数ｐ２を示すノードを彩色するべく、変数ｐ２と干渉関係にある他の変数に既に彩色された色彩とは異なる色彩を検索する。しかしながら、変数ｐ２と干渉関係にある他の変数には、既に基準数の色彩が彩色されている。そこで、セレクト部６３５は、変数ｐ２に仮想レジスタを割り付ける。ここではその仮想レジスタを＊と記す。この結果、スタックには変数ｐ、変数ｑ１および変数ｒ２が残る。

図２８は、セレクト処理（Ｓ１７３５）によって変数にレジスタが割り付けられる処理の第３手順を示す。上記と同様の処理によって、セレクト部６３５は、変数ｒ２および変数ｑ１を順次ポップする。その結果、変数ｒ２を示すノードは「緑」に、変数ｑ１を示すノードは「黄色」に、それぞれ彩色される。

しかしながら、セレクト部６３５は、最後にポップされる変数ｐ１を示すノードを、物理レジスタを示す色彩で彩色することができない。従って、セレクト部６３５は、変数ｐ１を示すノードを、例えば仮想レジスタを示す「＊」で彩色する。

ここで、この彩色結果をそのまま利用してレジスタ割付の結果とする場合には、変数ｐ１およびｐ２がスピルの対象となる。そしてその場合、変数ｐ１およびｐ２にレジスタを割り付けることによって得られる利得、即ち利得１に利得１を加えた利得２が得られない。具体的には、変数ｐ１の値を参照する命令１回について、メモリから値をロードする命令が実行され、変数ｐ２の値を参照する命令１回について、メモリから値をロードする命令が実行される。

続いて、この割り付け結果に基づいてノード融合することで、この損失を低減する処理の具体例を示す。
図２９は、変数の融合（Ｓ１７４０）によって変数の干渉情報および優先度が併合される処理の一例を示す。

更新部６４０は、第１割付部６３０により同一のレジスタが割り付けられ、かつ代入情報６４Ａにおいて相互に対応付けられた複数の変数を新たな変数に置換する。図２８を参照すると、変数ｑ１およびｑ２は同一のレジスタに割り付けられている。また、変数ｒ１およびｒ２は同一のレジスタに割り付けられている。また、変数ｐ１およびｐ２は共に同一の仮想レジスタに割り付けられている。

したがって、更新部６４０は、変数ｐ１およびｐ２を新たな変数ｐに置換する。また、更新部６４０は、変数ｑ１およびｑ２を新たな変数ｑに置換する。また、更新部６４０は、変数ｒ１およびｒ２を新たな変数ｒに置換する。

この結果得られた各種の情報を（ａ）および（ｂ）に示す。変数ｐは変数ｑ、ｒおよびｓとそれぞれ干渉関係にある。変数ｑは変数ｒおよびｓとそれぞれ干渉関係にある。変数ｒは変数ｓと干渉関係にある。また、変数ｐの参照回数は２回であり、変数ｑの参照回数は２回であり、変数ｒの参照回数は２回であり、変数ｓの参照回数は１回であるから、各変数の利得はそれぞれ２、２、２および１である。次数およびコストは図示の通りである。

図３０は、シンプリファイ処理（Ｓ１７６２）によって干渉関係が干渉情報から除外される処理の第１手順を示す。図２９を参照すると、次数が基準数３未満の変数は無い。従って、シンプリファイ部６５２は、優先度の最も低い変数ｓを選択してスタックにプッシュする。この結果、変数ｐ、ｑおよびｒの次数は３から２に減少する。また、スタックには変数ｓが格納される。

図３１は、シンプリファイ処理（Ｓ１７６２）によって干渉関係が干渉情報から除外される処理の第２手順を示す。図３０を参照すると、変数ｐ、ｑおよびｒの次数はそれぞれ２であり、基準数３未満である。したがって、シンプリファイ部６５２は、変数ｐ、ｑおよびｒをスタックにプッシュする。プッシュの順序は問わない。この結果、全ての変数がスタックに格納される。

図３２は、セレクト処理（Ｓ１７６５）によって変数にレジスタが割り付けられる処理の一例を示す。セレクト部６５５は、干渉グラフを再構築しながら変数ｒ、ｑおよびｐを順次ポップする。そして、セレクト部６５５は、ポップした当該変数に、当該変数と干渉関係にある既にポップした変数とは異なるレジスタを割り付ける。この結果、例えば変数ｐは「青色」に彩色され、変数ｒは「緑色」に彩色され、変数ｑは「黄色」に彩色される。変数「ｓ」はスピルされることが決定される。

ここで、図２８において第１割付部６３０のみがレジスタを割り付けた場合と比較して、図３２の例では、変数ｐ１およびｐ２に代えて変数ｓがスピルされている。変数ｐ１およびｐ２の利得の合計は２であるのに対し、変数ｓの利得は１である。従って、第１割付部６３０に加えて更新部６４０がレジスタ割付を行うことで、失われる利得が１減少している。具体的には、例えば変数の値をメモリからレジスタに読み出す処理を１回減少させることができる。

図３３は、本実施形態に係るコンパイラ装置１０として機能するコンピュータ５００のハードウェア構成の一例を示す。コンピュータ５００は、ホストコントローラ１０８２により相互に接続されるＣＰＵ１０００、ＲＡＭ１０２０、及びグラフィックコントローラ１０７５を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホストコントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＢＩＯＳ１０１０、フレキシブルディスクドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。

ホストコントローラ１０８２は、ＲＡＭ１０２０と、高い転送レートでＲＡＭ１０２０をアクセスするＣＰＵ１０００及びグラフィックコントローラ１０７５とを接続する。ＣＰＵ１０００は、ＢＩＯＳ１０１０及びＲＡＭ１０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ１０７５は、ＣＰＵ１０００等がＲＡＭ１０２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィックコントローラ１０７５は、ＣＰＵ１０００等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。

入出力コントローラ１０８４は、ホストコントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ネットワークを介して外部の装置と通信する。ハードディスクドライブ１０４０は、コンピュータ５００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からプログラム又はデータを読み取り、ＲＡＭ１０２０又はハードディスクドライブ１０４０に提供する。

また、入出力コントローラ１０８４には、ＢＩＯＳ１０１０と、フレキシブルディスクドライブ１０５０や入出力チップ１０７０等の比較的低速な入出力装置とが接続される。ＢＩＯＳ１０１０は、コンピュータ５００の起動時にＣＰＵ１０００が実行するブートプログラムや、コンピュータ５００のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ１０５０は、フレキシブルディスク１０９０からプログラム又はデータを読み取り、入出力チップ１０７０を介してＲＡＭ１０２０またはハードディスクドライブ１０４０に提供する。入出力チップ１０７０は、フレキシブルディスク１０９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。

コンピュータ５００に提供されるプログラムは、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、入出力チップ１０７０及び/又は入出力コントローラ１０８４を介して、記録媒体から読み出されコンピュータ５００にインストールされて実行される。プログラムがコンピュータ５００等に働きかけて行わせる動作は、図１から図３２において説明したコンパイラ装置１０における動作と同一であるから、説明を省略する。

以上に示したプログラムは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムをコンピュータ５００に提供してもよい。

以上、図１から図３３を参照して説明したように、本実施形態に係るコンパイラ装置１０によれば、一度目のレジスタ割付により同一のレジスタに割り付けられ、かつ、相互に代入関係にある変数を融合して、融合後の干渉関係について二度目のレジスタ割付を行う。そして、二度目のレジスタ割付は一度目のレジスタ割付と同一の手順に従う。これにより、融合前後で同一の割当が行われやすいことを利用して融合により生じる不利益を軽減しつつ、融合により各変数の次数を減少させて、レジスタ割当の自由度を向上させることができる。この結果、例えば、図２１から図３２に示したように、スピルにより追加的に必要な処理を減少させるなどして、プログラムの実行効率を向上させることができる。

以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることのできることが当業者にとって明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。

図１は、本実施形態に係るコンパイラ装置１０の全体構成を示す。 図２は、ある対象プログラム２２の中で使用される各変数の使用状況を示す。 図３は、各変数の値を特定のレジスタが一貫して保持する場合におけるレジスタの割付結果の一例を示す。 図４は、各変数を複数の変数に変換したうえでレジスタを割り付ける場合におけるレジスタの割付結果の第１例を示す。 図５は、各変数を複数の変数に変換したうえでレジスタを割り付ける場合におけるレジスタの割付結果の第２例を示す。 図６は、本実施形態に係るレジスタ割付部１１０の機能構成の一例を示す。 図７は、本実施形態に係るプログラム６０の一例を示す。 図８は、本実施形態に係る干渉情報６２Ａの一例を示す。 図９は、本実施形態に係る代入情報６４Ａの一例を示す。 図１０は、本実施形態に係る優先度６５Ａの一例を示す。 図１１は、本実施形態に係る割付結果６６の一例を示す。 図１２は、本実施形態に係る干渉情報６２Ｂの一例を示す。 図１３は、本実施形態に係る代入情報６４Ｂの一例を示す。 図１４は、本実施形態に係る優先度６５Ｂの一例を示す。 図１５は、本実施形態に係る割付結果６８の一例を示す。 図１６は、本実施形態に係る出力プログラム２４の一例を示す。 図１７は、本実施形態に係るレジスタ割付部１１０が変数にレジスタを割り付ける処理の流れを示す。 図１８は、Ｓ１７３２およびＳ１７６２における処理の流れの詳細を示す。 図１９は、Ｓ１７３５における処理の流れの詳細を示す。 図２０は、Ｓ１７６５における処理の流れの詳細を示す。 図２１は、本実施形態に係るコンパイラ装置１０がコンパイルの対象とする他のプログラムについて、変数の干渉関係及び優先度の一例を示す。 図２２は、シンプリファイ処理（Ｓ１７３２）によってある干渉関係が干渉情報から除外される処理の第１手順を示す。 図２３は、シンプリファイ処理（Ｓ１７３２）によって次の干渉関係が干渉情報から除外される処理の第２手順を示す。 図２４は、シンプリファイ処理（Ｓ１７３２）によって更に次の干渉関係が干渉情報から除外される処理の第３手順を示す。 図２５は、シンプリファイ処理（Ｓ１７３２）によって更に次の干渉関係が干渉情報から除外される処理の第４手順を示す。 図２６は、セレクト処理（Ｓ１７３５）によって変数にレジスタが割り付けられる処理の第１手順を示す。 図２７は、セレクト処理（Ｓ１７３５）によって変数にレジスタが割り付けられる処理の第２手順を示す。 図２８は、セレクト処理（Ｓ１７３５）によって変数にレジスタが割り付けられる処理の第３手順を示す。 図２９は、変数の融合（Ｓ１７４０）によって変数の干渉情報および優先度が併合される処理の一例を示す。 図３０は、シンプリファイ処理（Ｓ１７６２）によって干渉関係が干渉情報から除外される処理の第１手順を示す。 図３１は、シンプリファイ処理（Ｓ１７６２）によって干渉関係が干渉情報から除外される処理の第２手順を示す。 図３２は、セレクト処理（Ｓ１７６５）によって変数にレジスタが割り付けられる処理の一例を示す。 図３３は、本実施形態に係るコンパイラ装置１０として機能するコンピュータ５００のハードウェア構成の一例を示す。

符号の説明

１０ コンパイラ装置
２２ 対象プログラム
２４ 出力プログラム
６０ プログラム
６２ 干渉情報
６４ 代入情報
６５ 優先度
６６ 割付結果
６８ 割付結果
６９ 結果プログラム
１００ 第１最適化部
１１０ レジスタ割付部
１２０ 記憶装置
１３０ 第２最適化部
５００ コンピュータ
６００ 変数変換部
６１０ 代入命令生成部
６２０ 情報生成部
６３０ 第１割付部
６３２ シンプリファイ部
６３５ セレクト部
６４０ 更新部
６５０ 第２割付部
６５２ シンプリファイ部
６５５ セレクト部
６６０ スピル生成部
６７０ 出力部

Claims (12)

1. コンパイルの対象となるプログラムの中で使用される変数にレジスタを割り付けるコンパイラ装置であって、
   前記プログラムの中で使用されるある変数と他の変数とが前記プログラムの実行中の何れかの時点において同時に有効な値を保持している関係である干渉関係にあるかどうかを示す干渉情報、および、前記プログラム中の代入命令の代入元の変数を代入先の変数に対応付けた代入情報を記憶している記憶装置と、
   前記プログラムの中で使用されるそれぞれの変数に、前記干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において、予め定められた基準数以上のレジスタの中から予め定められた手順に従ってレジスタを選択して割り付ける第１割付部と、
   複数の前記変数に、前記第１割付部により同一のレジスタが割り付けられ、かつ、当該複数の変数が前記代入情報において互いに対応付けられていることを条件に、当該複数の変数を新たな変数に置換すると共に、当該複数の変数のそれぞれについての前記干渉関係を前記記憶装置から読み出して併合して、当該新たな変数についての干渉関係を生成し、生成した当該干渉関係により前記干渉情報を更新する更新部と、
   当該複数の変数に代えて当該新たな変数を使用する前記プログラム中の各変数に、更新した前記干渉情報に基づく干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において、前記第１割付部と同一の前記手順に従って前記基準数のレジスタの中からレジスタを選択して割り付ける第２割付部と、
   前記第２割付部が変数にレジスタを割り付けた前記プログラムを出力する出力部と
   を備えるコンパイラ装置。
2. 前記予め定められた基準数は、前記プログラムの実行に使用することのできるレジスタである物理レジスタの上限数として予め定められた数であり、
   前記第１割付部は、前記基準数の物理レジスタに、前記プログラムの実行には使用することのできない仮想的なレジスタである仮想レジスタを少なくとも１つ加えたレジスタの集合の中から、前記予め定められた手順に従ってレジスタを選択して各変数に割り付け、
   前記第２割付部は、当該新たな変数を使用する前記プログラム中の各変数に、前記基準数と同数の物理レジスタの中から前記予め定められた手順に従ってレジスタを選択して割り付ける、請求項１に記載のコンパイラ装置。
3. 前記第１割付部は、レジスタ割付の候補となる第１の変数について、当該第１の変数を代入元とした代入先の第２の変数、または、当該第１の変数を代入先とした代入元の第２の変数を、前記代入情報に基づいて選択すると共に、更新前の前記干渉情報に基づく干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において当該第１の変数に割付可能なレジスタのうち、選択した当該第２の変数に既に割り付けたレジスタと同一のレジスタを、当該第１の変数に割り付け、
   前記更新部は、干渉関係を併合する当該複数の変数については、さらに、前記代入情報を併合して前記記憶装置の代入情報を更新し、
   前記第２割付部は、レジスタ割付の候補となる第１の変数について、当該第１の変数を代入元とした代入先の第２の変数、または、当該第１の変数を代入先とした代入元の第２の変数を、前記代入情報に基づいて選択すると共に、更新後の前記干渉情報に基づく干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において当該第１の変数に割付可能なレジスタのうち、選択した当該第２の変数に既に割り付けたレジスタと同一のレジスタを、当該第１の変数に割り付ける、
   請求項２に記載のコンパイラ装置。
4. 前記記憶装置は、さらに、それぞれの変数について当該変数にレジスタを割り付ける優先度を記憶しており、また、スタックを実現するための記憶領域を有し、
   前記第１割付部は、
   干渉関係にある変数の数が前記基準数未満の変数を前記干渉情報に基づいて検索し、検索されれば当該変数を選択し、検索されなければ前記優先度の最も低い変数を選択して、当該選択した変数を前記スタックにプッシュすると共に、当該選択した変数についての干渉関係を前記干渉情報から除外する処理、を、割り付けるべき全ての変数をプッシュするまで繰り返すシンプリファイ部と、
   前記スタックから変数をポップし、ポップした当該変数を代入元とする代入先の変数、または、ポップした当該変数を代入先とする代入元の変数を前記代入情報に基づいて選択し、ポップした当該変数と干渉関係にある他の変数にはまだ割り付けられていない物理レジスタである未割当レジスタのうち、選択した当該変数に既に割り付けられたレジスタがあれば当該レジスタを選択し、選択した当該変数に既に割り付けられた当該レジスタが前記未割当レジスタの中に無ければ他の未割当レジスタを選択し、未割当レジスタが無ければポップした当該変数と干渉関係にある他の変数にはまだ割り付けられていない仮想的なレジスタである未割当仮想レジスタのうち、選択した当該変数に既に割り付けられた仮想レジスタがあれば当該レジスタを選択して、ポップした当該変数に選択した当該レジスタを割り付ける、処理を、前記スタックが空になるまで繰り返すセレクト部と
   を有し、
   前記更新部は、複数の前記変数に、前記仮想的なレジスタを含め同一のレジスタが割り付けられており、かつ、前記代入情報において互いに対応付けられていることを条件に、当該複数の変数の少なくとも何れか１つとの間で干渉関係にある他の変数を、前記記憶装置に記憶された前記干渉情報に基づき検索し、当該干渉関係を、当該複数の変数に代わる新たな変数と当該他の変数との間の干渉関係に変更し、
   前記第２割付部は、
   干渉関係の併合された前記干渉情報に基づいて、干渉関係にある変数の数が前記基準数未満の変数を検索し、検索されれば当該変数を選択し、検索されなければ前記優先度の最も低い変数を選択して、当該選択した変数を前記スタックにプッシュすると共に、当該選択した変数についての干渉関係を前記干渉情報から除外する処理、を、割り付けるべき全ての変数をプッシュするまで繰り返すシンプリファイ部と、
   前記スタックから変数をポップし、ポップした当該変数を代入元とする代入先の変数、または、ポップした当該変数を代入先とする代入元の変数を前記代入情報に基づいて選択し、ポップした当該変数と干渉関係にある他の変数にはまだ割り付けられていない物理レジスタである未割当レジスタのうち、選択した当該変数に既に割り付けられたレジスタがあれば当該レジスタを選択し、選択した当該変数に既に割り付けられたレジスタが前記未割当レジスタの中に無ければ他の未割当レジスタを選択し、選択した当該未割当レジスタをポップした当該変数に割り付け、未割当レジスタを選択できなければポップした当該変数をスピルすると決定する、処理を、前記スタックが空になるまで繰り返すセレクト部と
   を有し、
   前記出力部は、コンパイルした前記プログラムに、スピルすると決定した変数の値については使用の毎にメモリからレジスタに読み出す命令、および、変数値の定義の毎にレジスタからメモリへ当該変数値を書込む命令を含めて出力する、請求項３に記載のコンパイラ装置。
5. 前記第１割付部における前記セレクト部は、ポップした当該変数と干渉関係にある他の変数にはまだ割り付けられていない仮想レジスタである未割当仮想レジスタのうち、ポップした当該変数と前記代入情報において対応付けられている他の変数に既に割り付けられた仮想レジスタが存在しなくても、ポップした当該変数と干渉関係にある他の変数にはまだ割り付けられていない、既に他の変数に割り付けた前記仮想レジスタがあれば、ポップした当該変数に当該仮想レジスタを割り付け、ポップした当該変数と干渉関係にある他の変数にはまだ割り付けられていないレジスタが、当該仮想レジスタを含めて存在しなければ、新たに前記仮想レジスタを生成してポップした当該変数に割り付ける、請求項４に記載のコンパイラ装置。
6. 前記記憶装置は、前記プログラムにより使用される各変数をノードとし、互いに干渉関係にある変数の組を示すノードの組を、エッジで連結したグラフである干渉グラフを、前記干渉情報として記憶しており、
   前記第１割付部および前記第２割付部は、各レジスタを色彩とし、前記干渉グラフの各ノードを、互いにエッジで直接連結されたノードの組を同一の色彩で彩色しない範囲内で、各色彩で彩色することで、変数に割り付けるレジスタを決定し、
   前記更新部は、前記第１割付部により同一のレジスタが割り付けられ、かつ、前記代入情報において互いに対応付けられた複数の変数について、前記干渉グラフにおける当該複数の変数を表す複数のノードを新たな１つのノードに置換すると共に、前記干渉グラフにおける当該複数のノードのそれぞれと他のそれぞれのノードとの間のエッジを、当該新たな１つのノードと当該他のそれぞれのノードとの間のエッジに置換する、請求項１に記載のコンパイラ装置。
7. ある変数を、その変数の生存区間を分割して、分割した生存区間ごとにその変数の値を保持する複数の変数を生成することで、当該複数の変数に変換する変数変換部と、
   変換した当該複数の変数のうちのある変数から他の変数への代入命令を前記プログラム中に生成する代入命令生成部と、
   変換後の当該複数の変数を含む、前記プログラム中で使用される複数の変数についての干渉関係を示す情報を、前記干渉情報として生成して前記記憶装置に格納すると共に、生成した前記代入命令の代入元および代入先となる変数の組を示す代入情報を生成して前記記憶装置に格納する情報生成部と
   を更に備え、
   前記第１割付部は、前記記憶装置に格納された前記干渉情報及び前記代入情報に基づいて変数にレジスタを割り付け、
   前記更新部は、前記記憶装置に格納された前記代入情報に基づいて、前記記憶装置に格納された前記干渉情報を更新する、請求項３に記載のコンパイラ装置。
8. 前記第２割付部がある第１変数をスピルすると決定したことを条件に、当該第１変数に対する変数値の代入命令を、当該変数値を格納するレジスタの値をメモリ上の領域に格納する命令に変換すると共に、当該第１変数の変数値を参照する命令を、当該変数値をメモリ上の領域から読み出してレジスタに格納し、当該レジスタの値を参照する命令に変換する、スピル生成部と、
   前記第１割付部は、さらに、前記スピル生成部および前記第２割付部が生成したレジスタを変数とみなして、それぞれの変数にレジスタを割り付ける
   請求項３に記載のコンパイラ装置。
9. 前記第１割付部は、前記更新部が前記干渉情報を更新する毎に、前記プログラムの中で使用されるそれぞれの変数に、前記更新部が更新した前記干渉情報に基づき前記干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において、前記基準数以上のレジスタの中から前記手順に従ってレジスタを選択して割り付ける処理、を行い、
   前記更新部は、前記第１割付部がレジスタを割り付ける毎に、同一のレジスタを割り付け、かつ、前記代入情報において相互に対応付けられた複数の変数のそれぞれについての前記干渉関係を前記記憶装置から読み出して併合することで、当該複数の変数に代わる新たな変数についての干渉関係を生成し、生成した当該干渉関係により前記干渉情報を更新する処理、を行い、
   前記第２割付部は、前記更新部が前記更新する処理を予め定められた回数行ったことを条件に、更新後の前記干渉情報に基づいて変数にレジスタを割り付ける
   請求項１に記載のコンパイラ装置。
10. 前記第１割付部は、レジスタ割付の候補となる第１の変数について、当該第１の変数を代入元とした代入先の第２の変数、または、当該第１の変数を代入先とした代入元の第２の変数を、前記代入情報に基づいて選択すると共に、更新前の前記干渉情報に基づく干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において当該第１の変数に割付可能なレジスタのうち、選択した当該第２の変数に既に割り付けたレジスタと同一のレジスタを、当該第１の変数に割り付け、
    前記更新部は、干渉関係を併合する当該複数の変数については、さらに、前記代入情報を併合して前記記憶装置の代入情報を更新し、
    前記第２割付部は、レジスタ割付の候補となる第１の変数について、当該第１の変数を代入元とした代入先の第２の変数、または、当該第１の変数を代入先とした代入元の第２の変数を、前記代入情報に基づいて選択すると共に、更新後の前記干渉情報に基づく干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において当該第１の変数に割付可能なレジスタのうち、選択した当該第２の変数に既に割り付けたレジスタと同一のレジスタを、当該第１の変数に割り付ける、
    請求項１に記載のコンパイラ装置。
11. コンパイルの対象となるプログラムの中で使用される変数に、コンピュータによってレジスタを割り付けるコンパイル方法であって、 前記コンピュータは、 前記プログラムの中で使用されるある変数と他の変数とが前記プログラムの実行中の何れかの時点において同時に有効な値を保持している関係である干渉関係にあるかどうかを示す干渉情報、および、前記プログラム中の代入命令の代入元の変数を代入先の変数に対応付けた代入情報を記憶している記憶装置を有し、 前記プログラムの中で使用されるそれぞれの変数に、前記干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において、予め定められた基準数以上のレジスタの中から予め定められた手順に従ってレジスタを選択して割り付けるステップと、 複数の前記変数に、前記割り付けるステップにおいて同一のレジスタが割り付けられ、かつ、当該複数の変数が前記代入情報において互いに対応付けられていることを条件に、当該複数の変数を新たな変数に置換すると共に、当該複数の変数のそれぞれについての前記干渉関係を前記記憶装置から読み出して併合して、当該新たな変数についての干渉関係を生成し、生成した当該干渉関係により前記干渉情報を更新するステップと、 当該複数の変数に代えて当該新たな変数を使用する前記プログラム中の各変数に、更新した前記干渉情報に基づく干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において、前記割り付けるステップと同一の前記手順に従って前記基準数のレジスタの中からレジスタを選択して割り付けるステップと、 後段の前記割り付けるステップにおいてレジスタに割り付けられた変数を含む前記プログラムを出力するステップと を実行する、コンパイル方法。
    
12. コンパイルの対象となるプログラムの中で使用される変数にレジスタを割り付けるコンパイラ装置として、コンピュータを機能させるプログラムであって、
    前記コンピュータは、
    前記プログラムの中で使用されるある変数と他の変数とが前記プログラムの実行中の何れかの時点において同時に有効な値を保持している関係である干渉関係にあるかどうかを示す干渉情報、および、前記プログラム中の代入命令の代入元の変数を代入先の変数に対応付けた代入情報を記憶している記憶装置を有し、
    前記コンピュータを、
    前記プログラムの中で使用されるそれぞれの変数に、前記干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において、予め定められた基準数以上のレジスタの中から予め定められた手順に従ってレジスタを選択して割り付ける第１割付部と、
    複数の前記変数に、前記第１割付部により同一のレジスタが割り付けられ、かつ、当該複数の変数が前記代入情報において互いに対応付けられていることを条件に、当該複数の変数を新たな変数に置換すると共に、当該複数の変数のそれぞれについての前記干渉関係を前記記憶装置から読み出して併合して、当該新たな変数についての干渉関係を生成し、生成した当該干渉関係により前記干渉情報を更新する更新部と、
    当該複数の変数に代えて当該新たな変数を使用する前記プログラム中の各変数に、更新した前記干渉情報に基づく干渉関係にある変数の組に同一のレジスタを割り付けない範囲内において、前記第１割付部と同一の前記手順に従って前記基準数のレジスタの中からレジスタを選択して割り付ける第２割付部と、
    前記第２割付部が変数にレジスタを割り付けた前記プログラムを出力する出力部
    として機能させるプログラム。

Images