JP2000353097A - 低密回の干渉グラフを生成する方法および装置 - Google Patents

Abstract

(57)【要約】 【課題】 干渉グラフにより記載されるエッジの数を減
少する方法および装置が開示される。 【解決手段】 本発明のある側面によれば、オブジェク
トベースの計算システムにおいてメモリスペースを割り
当てるコンピュータによって実行する方法は、第1変数
と関連するコード・セグメントおよび第2変数と関連す
るコード・セグメントを含むソース・コードの取得を含
む。この方法はまた、第1変数の特定レジスタへの結び
付け、第2変数に対する有効範囲の取得も含む。第2変数
に対する有効範囲が取得されると、レジスタ割り当てが
実行される。レジスタ割り当ての実行は、第2変数の表
現を含むが第1変数の表現を含まない干渉グラフの生成
を含む。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】

【従来の技術】本発明は、ソフトウェア・アプリケーシ
ョンの性能を改良する方法および装置に関するものであ
る。本発明は、特に、干渉グラフにおけるエッジの数を
減少するための方法および装置に関するものである。

【０００２】

【従来の技術】コンピュータ・プログラムの実行に伴う
効率を高めるように、コンピュータ・プログラムの多く
は「最適化」される。コンピュータ・プログラムの最適
化は一般的には、本質的に使用されないコンピュータ・
コードの部分の除去に役立つ。これに加え、コンピュー
タ・プログラムを最適化するコンピュータの運用が、再
構築され、全体的計算が、さらに効率的に行われてコン
ピュータ資源の消費が少なくなる。

【０００３】C++、FORTRAN、Javaバイコードなどのプロ
グラミング言語などで記載されたコンピュータ・プログ
ラムをさらに高速のプログラムへ効率的に変換するよう
に、オプティマイザが配備される。より高速の、もしく
は、最適化されたプログラムは、オリジナルの、もしく
は、事前変換されたコンピュータ・プログラムと同一の
観察可能な動作をほとんどすべて含んでいるのが一般的
である。より厳密には、最適化されたプログラムは、対
応するオリジナル・プログラムと同一の数学上の動作を
示す。しかしながら、最適化されたプログラムは、さら
に少ない回数の計算により同一の数学上の動作を再生成
するのが一般的である。

【０００４】その技術に熟練した当業者であれば理解さ
れるように、オプティマイザは、一般的には、最適化も
しくは、コンパイルされたプログラムの内部表現におけ
るレジスタの使用を制御するように配置されたレジスタ
・アロケータを含んでいる。レジスタ・アロケータは、
プログラムと関連するデータが記憶され得るレジスタス
ペースを割り当てる。レジスタは、コンピュータのプロ
セッサに関連する位置であり、コンピュータと関連して
たとえばスタックもしくは、ヒープスペースなどの「通
常の」メモリスペースにアクセスすることに関連する速
回と比較して相対的に高速にアクセスされ得るものであ
る。

【０００５】多くの場合、レジスタおよびスタック・ス
ロットを割り当てるには、割り当て処理を促進するよう
に干渉グラフが使用される。干渉グラフは、一般的に
は、特定のコード部分と関連する変数もしくは値の々に
対する有効範囲の表現を含んでいる。有効範囲は、一般
的には、コード部分において特定の変数もしくは値が引
き続きアクセス可能かつ使用可能となっていなくてはな
らない範囲である。その技術に熟練した者であれば理解
される如く、干渉グラフ内に表された変数の有効範囲間
の関係を表示するように、干渉グラフには、彩色プロセ
スが用いられる。

【０００６】干渉グラフは、典型的には、ソース・コー
ドのコンパイル処理の間に生成される。図１は、レジス
タ・アロケータを備えたコンパイラを一般的には表示し
たものである。ソース・コード102が、レジスタ・アロ
ケータ110を含むコンパイラ106に対する入力して備えら
れている。コンパイラ106は、最適化コンパイラである
ものとし、ソース・コード102の内部表現120を生成する
ように配置される。示された如く、「CX」に保存された
変数に対する有効範囲132が、「DX」に保存された変数
に対する有効範囲134と重複している。従って、レジス
タ・アロケータ110が有効範囲132、134に対するレジス
タを割り当てるとき、そうしたレジスタはレジスタ間の
干渉を防止する如く割り当てられねばならない。

【０００７】ソース・コード102はサブルーチンに対す
る呼び出し140を含んでいる。一般的には、呼び出し
は、たとえばカリフォルニア州、Palo AltoのSun Micro
systems社により開発されたJava（登録商標）プログラ
ミング言語などで記載されたソース・コードにおいては
比較的普通のものである。呼び出し140は、引数として
変数「CX」および「DX」を含んでいる。より厳密には、
呼び出し140が、引数として「CX」および「DX」の内容
を伴って生成される。典型的には、呼び出し140と関連
する変数の少なくとも幾つかが、割り当てられたレジス
タの間において特定のレジスタに結び付けられる。言い
換えれば、呼び出し140と関連する引数が結び付けられ
たレジスタを他の変数は使用できない。その技術に熟練
した者であれば理解される如く、一定の方法により使用
される入力パラメータもまた特定レジスタに結び付けら
れる。

【０００８】内部表現120で与えられる情報は、ソース
・コード102の干渉グラフを生成するに使用されること
がある。ここで図２を参照しながら、図１のソース・コ
ード102の表現して生成された干渉グラフについて記載
する。干渉グラフ204は、割り当てられたレジスタに関
して有効範囲、有効範囲間の矛盾することを表す目的で
生成される。図１のソース・コード102と関連する全て
の変数は、干渉グラフ204内に表される。ノード208は変
数に対する有効範囲を表す。たとえば、ノード208dは
「CX」に対する有効範囲を示するように配置される一
方、ノード208eは「DX」に対する有効範囲を示するよう
に配置される。特定の実際のレジスタに結び付けられた
「DX」と関連する変数に対する有効範囲が、干渉グラフ
204内に含まれていることを理解すべきである。

【０００９】二つのノード208の間に引かれたエッジ212
は、これらの二つのノード208が干渉することを表す。
すなわち、二つのノード208の間に示されたエッジ212
は、その二つのノード208に関連する変数が、同時に有
効であるべきことから、同一のレジスタ内には保存され
得ない、ということを示している。たとえば、ノード20
8dとノード208eの間のエッジ212dは、「CX」の内容と
「DX」の内容が同時に有効であるべきことから、両者の
内容が互いに干渉する、たとえば、互いに矛盾したりす
ることを示している。

【００１０】レジスタ割り当てを行う間に干渉グラフを
構築するとともに彩色するなどの操作を行うのは、矛盾
することなしにレジスタを変数に割り当てるのを許容す
るためである。一般的には、干渉グラフもしくは、他の
手法を使用することにより干渉なしでレジスタを変数に
割り当てるプロセスは、比較的複雑である。干渉グラフ
が、比較的大規模になることが多く、約10,000のノード
が関与するときには、ビットセットのインプリメンテー
ションに対する約12メガバイト以上のメモリスペースを
要することがある。典型的には、ビットセットのインプ
リメンテーションに対して各エッジは8バイトを要す
る。コンパイラに与えられるソース・コードが、数千個
の変数を含むことも多いので、約10,000個のノードを含
む干渉グラフが生じることはかなり頻繁にある。

【００１１】比較的大量のメモリスペースを占有する干
渉グラフは、そうした比較的大量のメモリスペースを占
有することが無ければ他の目的に使用可能となるような
だけのメモリスペースを占有する傾向がある。これに加
え、干渉グラフの生成および変更は、全体的なコンパイ
ル処理、より厳密には、レジスタ割り当てプロセスの相
当の部分を占めることから、干渉グラフの生成および変
更に伴う複雑さを低減すれば全体的なコンパイル処理が
行われる速回にかなりの影響を与え得る。従って、求め
られるものは、干渉グラフを生成かつ変更する上での効
率を高める方法および装置である。すなわち、必要とさ
れるものは、レジスタ割り当てプロセスの精回を低下さ
せずに干渉グラフに含まれるエッジの数を減少する方法
および装置である。

【００１２】

【課題を解決するための手段】本発明は、レジスタ割り
当てプロセスに対して生成された干渉グラフのエッジの
数を減少する方法に関するものである。本発明のある側
面によれば、オブジェクトベースの計算システムにおい
てレジスタを割り当てるコンピュータによって実行する
方法は、第1変数と関連するコード・セグメントおよび
第2変数と関連するコード・セグメントを含むソース・
コードの取得を含む。この方法は、また、第1変数に対
する有効範囲の取得、第1変数の特定レジスタに対する
結び付け、第2変数に対する有効範囲の取得を含む。次
に、第2変数の表現は、変更され、その潜在的割り当て
選択肢から第1変数に結び付けられた特定レジスタを除
外する。第2変数に対する有効範囲が取得されて変更さ
れると、レジスタ割り当てが実行される。レジスタ割り
当ての実行は、第2変数の表現を含むが第1変数の表現を
含まない、干渉グラフの生成を含む。第2変数の表現
は、第2変数の有効範囲の表現とする。

【００１３】一実施形態においては、第1変数と関連す
るコード・セグメントを含むソース・コードの取得は、
呼び出しにおける引数としての第１変数を含むサブルー
チンに対する呼び出しの取得を含む。別の実施形態にお
いては、ソース・コードの取得は、当第3変数と関連す
る第2有効範囲の取得に加えて第3変数と関連するコード
・セグメントの取得、第2有効範囲を変更することによ
り第1変数に結び付けられた特定レジスタの第3変数に対
する使用可能な選択肢からの除外をさらに含んでいる。
そうした実施形態においては、干渉グラフは第3変数の
表現を含むとともに、レジスタ割り当ての実行は、第1
有効範囲と第2有効範囲が重複するか否かの決定を含
む。有効範囲が重複することが決定されたなら、干渉グ
ラフを使用して彩色プロセスが実行される。そうした彩
色プロセスは、干渉グラフに対し、第1有効範囲と第2有
効範囲が重複することを示す、たとえばエッジなどの表
示を付加する。

【００１４】レジスタに結び付けられた変数の表現を干
渉グラフから排除することにより、干渉グラフと関連す
るエッジの数が減少され得る。エッジの数を少なくする
と、レジスタ割り当てが行われ得る速回が高まる。典型
的には、干渉グラフの構築および操作が、全体的レジス
タ割り当てプロセスの内で最も時間を要する部分の一つ
であることから、たとえば干渉グラフを低密回に維持す
るなどして干渉グラフにおけるエッジの数を減少するこ
とにより、レジスタ割り当てプロセス全体の効率が改善
され得る。

【００１５】本発明のこれらのおよび他の利点は、以下
の詳細な説明を読むとともに添付図面を考察することで
さらに明らかになる。本発明は、添付の図面と関連した
以下の記載事項を参照することによって最もよく理解さ
れ得る。

【００１６】

【発明の実施の形態】レジスタ割り当てプロセスの一部
として干渉グラフが生成されるとともに彩色されること
とし、それにより、矛盾することなしにレジスタおよび
スタック・スロットが適切に変数に対して割り当てられ
得る。干渉グラフは、比較的大規模であることが多く、
干渉グラフのサイズが大きくなるにつれ、干渉グラフを
彩色するために使用される処理の複雑さが増すのが典型
的である。比較的大量のメモリスペースを占有する干渉
グラフは、そうした比較的大量のメモリスペースを占有
することが無ければ他の目的に使用可能となるようなだ
けのメモリスペースを占有する傾向がある。これに加
え、干渉グラフの構築および彩色が、レジスタ割り当て
プロセスの相当の部分を占める。従って、干渉グラフの
構築および彩色に伴う複雑さを低減すれば、コンパイル
処理が行われる速回が高まり得る。

【００１７】一般的には、干渉グラフに含まれるノード
の数およびエッジの数を減少すると、干渉グラフの生成
および操作と関連する速回は高まり得る。干渉グラフか
ら幾つかのエッジを排除するある方法は、レジスタに結
び付けられた変数もしくは値と関連するノードの識別を
含む。その技術に熟練した者であれば理解される如く、
サブルーチンに対する呼び出しと関連する変数などのよ
うにレジスタに結び付けられた変数は、最終的割り当て
において他の変数に干渉することが無い。より厳密に
は、変数の有効範囲、すなわち、特定レジスタに結び付
けられた変数が定義かつ使用される範囲は、彩色を達成
しようとするのであれば、他のどの変数の有効範囲にも
干渉してはならない。ソース・コードはサブルーチンに
対する相当数の呼び出しを含むことが多く、サブルーチ
ンに対する呼び出しと関連する変数は、一般的には、特
定レジスタに結び付けられることから、他の変数に干渉
し得ないそうした変数に対する有効範囲の数は相当なも
のとなり得る。

【００１８】レジスタに結び付けられた変数すなわち
「縛られた」変数は他のどの変数の有効範囲に干渉し得
ないことから、そうした変数の表現を干渉グラフ内に含
むことは不要である。そうした変数の表現を干渉グラフ
に含めず、もしくは、干渉グラフから排除することによ
り、その変数と関連するエッジは一般的には干渉グラフ
から除去され、比較的低密回の干渉グラフに帰着する。
干渉グラフを処理して低密回することにより、たとえば
最適化などの全体的コンパイル処理を行う速回は高まり
得る。

【００１９】図３は、本発明の実施形態に従う、縛られ
た変数の表現を含まない干渉グラフを生成するように配
置されたレジスタ・アロケータを備えたコンパイラを一
般的には表示した図である。ソース・コード302はコン
パイラ306への入力して与えられる。上述した実施形態
においては、コンパイラ306はソース・コード302を最適
化するように配置されたオプティマイザである。コンパ
イラ306は、ソース・コード302の内部表現320を生成す
るように配置されたレジスタ・アロケータ310を含む。
内部表現320は、ソース・コード302と同一の機能性を含
むとともに、ソース・コード302に対する数学計算的等
価物と見做すこととする。

【００２０】ソース・コード302は、サブルーチンに対
する呼び出しを含み、C++プログラミング言語、また
は、カリフォルニア州、Palo AltoのSun Microsystems
社により開発されたJavaプログラミング言語に限定され
るわけではないが、これらを含む適切なコンピュータ用
言語により記載されることとする。サブルーチンにおけ
る呼び出しは、変数「X」および「Y」の和を有効なもの
として含む。その技術に熟練した者であれば理解される
如く、ソース・コード302は、典型的には、サブルーチ
ンに対する多くの呼び出しを含む。

【００２１】一実施形態においては、「DX」は、関連す
る縛られたレジスタを有する変数を表す。「DX」は、変
数「CX」の内容変数「Z」の内容の和を保持する。変数
もしくは値が保存され得るレジスタを識別するように配
置されたレジスタ・マスクは、変数「X」および「Y」の
和、変数「X」、「Y」、「Z」の和をそれぞれが示す仮
想値「V1」および「V2」と関連し得る。レジスタ・マス
クに関しては図５を参照して以下で論ずる。あるレジス
タ・マスクは、V1と関連し得るレジスタセットまたは、
V1と関連する実際のレジスタのいずれかを表示するよう
に使用され得る一方、別のレジスタ・マスクはV2と関連
する実際のレジスタを識別し得る。

【００２２】典型的には、内部表現320で与えられた情
報は、ソース・コード302に対する干渉グラフを生成す
るように使用され得る。次に図４を参照して、図３の内
部表現320の表現として生成された干渉グラフを、本発
明の実施形態に従って記載する。干渉グラフ404は、変
数の有効範囲および有効範囲間の矛盾を表示するように
配置される。図３のソース・コード302において定義か
つ使用される変数は、干渉グラフ404に示すこととす
る。ノード408は、変数に対する有効範囲を表現するよ
うに配置される。

【００２３】図示された如く、干渉グラフ404にはエッ
ジ412が含まれて、有効範囲が干渉することを示してい
る。言い換えれば、二つのノード408間に配置されたエ
ッジ412は、これらの二つのノード408と関連するととも
に同一レジスタ内に保存される可能性を有する二つの変
数が、ほとんど同時に有効であるべきであることから、
同一レジスタに保存されてはならない、ということを示
している。

【００２４】上述された実施形態においては、「DX」と
関連する値の有効範囲の表現420は干渉グラフ404の一部
として含まれるが、その有効範囲420はいずれのエッジ4
12にも関連してはならないものとする。変数「DX」と関
連する値は、図５に示された如く、たとえばレジスタ56
0bなどに結び付けられる。従って、他のいずれの有効範
囲408もレジスタ560bを使用しない。これは、そのレジ
スタが、以下に記載される図５のレジスタ・マスクによ
り例証されているように、他の全ての有効範囲408と関
連する合法的レジスタセットから除去されるからであ
る。他の全ての有効範囲のレジスタ・マスクからレジス
タ560bを排除することにより、いずれかのエッジ412が
有効範囲408と「縛られた」有効範囲420の間に挿入され
るのが防止され、干渉グラフ404が簡略化される。

【００２５】前述の如く、レジスタ・マスクが、特定値
を保存し得る、レジスタセットを識別するように配置す
るものとする。一般的には、二つの異なる変数に対する
レジスタ・マスクは、変数に対する有効範囲が干渉する
か否かを決定するように解析され得る。図５は、本発明
の実施形態に従ったレジスタ・マスクの概略図である。
レジスタ・マスク552は複数のビット560を含んでいる。
ビット560は、レジスタ・マスク552が関連する変数に関
して特定レジスタが有効か否かを表示するように配置さ
れる。ビット560の数は、少なくとも部分的には、特定
のプロセッサと関連するレジスタもしくはスタック・ス
ロットの数に依存する。上述した実施形態においては、
たとえばビット560bなどが「1」の値に配置されたと
き、ビット560bと関連するレジスタが有効なことが示さ
れる。代わりに、たとえばビット560aが「0」の値に配
置されたとき、関連するレジスタが、有効でないことが
示される。一実施形態においては、レジスタ・マスク55
2で多くとも560が1ビットだけセットされる、即ち「1」
に配置される。というのも、ビット560が、整数もしく
はフロートなどの厳密な単一の値を示すからである。別
実施形態においては、たとえばビット560が長い整数を
表すときには、二つのビット560が配置され得る。さら
に別の実施形態においては、幾つかのレジスタの任意の
一つが有効な選択肢であることを示するように配置され
得る。

【００２６】次に図６を参照して、本発明の実施形態に
従い、干渉グラフの構築および操作と関連する工程を記
載する。干渉グラフを生成して操作するプロセス602
が、工程606で開始し、特定の一つのソース・コードと
関連する変数が処理される。変数「i」に対しては、工
程610において有効範囲が決定され,その有効範囲を表す
ノードが干渉グラフに挿入される。変数に対する有効範
囲の決定は、典型的には、その変数に対するあらゆる定
義および使用の識別を含む。変数「i」に対する有効範
囲が決定されるとともにその有効範囲に対応するノード
が干渉グラフ内に挿入されると、処理フローが工程614
に進み、変数「i」が特定レジスタに結び付けられる必
要があるか否かに関して決定が行われる。

【００２７】その技術に熟練した当業者であれば理解さ
れる如く、ほとんど同時に有効である他の有効範囲によ
りレジスタが重複使用されないようにして、一定の変数
が、レジスタに結び付けられるか、レジスタに対して割
り当てられる。たとえば、サブルーチンに対する呼び出
しに含まれた変数は特定レジスタに結び付けられること
が多い。一部の実施形態においては、Intelのx86系統の
プロセッサに対するX86 idiv命令などの単一レジスタの
みを使用する命令により定義された変数同ように、よう
々な方法に対する入力パラメータも特定レジスタに結び
付けられる。

【００２８】変数「i」を特定レジスタに結び付けない
と決定されると、工程618では、有効範囲「i」に対する
干渉グラフにエッジが付加される。より厳密には、上述
した実施形態においては、変数「i」に対する有効範囲
と関連する、割り当てられた合法的レジスタセットが、
干渉グラフに既に挿入されているとともに変数「i」を
伴ってほとんど同時に有効である変数「j」に対する他
の全ての有効範囲の割り当てられた合法的レジスタセッ
ト、と比較される。変数「i」に対する割り当てられた
合法的レジスタセットと重複する割り当てられた合法的
レジスタセットを有することが判明した、変数「j」に
対する有効範囲に対しては、変数「i」を表すノードと
「j」を表すノードの間で干渉グラフにエッジが挿入さ
れる。

【００２９】変数「i」が特定レジスタに結び付けられ
るべきか否かの決定に関するものである工程614に戻る
が、変数「i」が特定レジスタに結び付けられねばなら
ないと決定されると、処理フローが工程622に進み、こ
の工程において、変数「i」に結び付けられたたとえば
図５のレジスタ560bなどの特定レジスタを有する変数
「i」を伴ってほとんど同時に有効である全ての変数
「k」がそれらの割り当てられた合法的レジスタから除
去される。言い換えれば、変数「i」が結び付けられた
特定レジスタは、変数「i」に対する有効範囲と一致す
る、即ち有効範囲「i」に干渉する全ての有効範囲に対
する使用可能なレジスタのリストから除去される。その
技術に熟練した者であれば理解される如く、特定レジス
タに対する変数「i」を結び付けるために使用される方
法は幅広く変化し得る。変数「i」をレジスタに結び付
ける結果、変数「i」に対する有効範囲は他の変数との
矛盾もしくは重複が無くなる。言い換えれば、或るレジ
スタに結び付けられた変数もしくは値は他の変数に干渉
してはならない。従って、上述した実施形態において
は、変数「i」に対する有効範囲が他のどの変数に対す
る有効範囲にも干渉しないことから、変数「i」を表す
ノードに接続されるエッジは干渉グラフ内に存在しな
い。

【００３０】いずれかのエッジが縛られた変数の有効範
囲に関連する可能性を本質的に排除することにより、干
渉グラフが簡略化されることから、干渉グラフを使用す
るレジスタ割り当てプロセスが、さらに高速に、さらに
効率的なよう式で構成され得る。より厳密には、レジス
タ割り当てプロセスが行われる時間が短縮される。

【００３１】工程622において変数「i」が特定レジスタ
に結び付けられるとともに、たとえば図５のレジスタ56
0bなどのこの特定レジスタと関連するレジスタが、プロ
グラム中においてほとんど同時に有効である全ての変数
に対する合法的レジスタセットの選択肢から除去された
後、処理フローが、工程606に戻り、別の変数が処理さ
れる。工程606にて追加の変数が処理されないことが決
定されたき、干渉グラフの構築は完了する。

【００３２】図７は、本発明を実行するのに適した典型
的な汎用コンピュータ・システムを示している。コンピ
ュータ・システム1030は、(典型的には、ランダム・ア
クセス・メモリすなわちRAM)主記憶装置1034および(典
型的には、読出専用メモリすなわちROM)主記憶装置1036
などのメモリ・デバイスに連結された(中央処理ユニッ
すなわちCPUとも称される)任意の数のプロセッサ1032を
含んでいる。

【００３３】その技術に熟練した当業者であれば理解さ
れる如く、コンピュータ・システム1030、すなわちより
厳密には、CPU1032は仮想マシンをサポーするように配
置される。コンピュータ・システム1030上でサポーされ
る仮想マシンの一例を、次に図８を参照して記載する。
この技術においてよく知られているように、ROMが、CPU
1032に対して単一方向的にデータおよび命令を転送する
ように作用する一方、RAMが、典型的には、双方向的に
データおよび命令を転送するように使用される。CPU103
2は、一般的には、任意の数のプロセッサを含み得る。
主記憶装置1034、1036の両者は、任意の適切なコンピュ
ータ可読媒体を含み得る。典型的には、大容量記憶装置
である補助記憶媒体1038もまたCPU1032に双方向的に連
結されて追加的なデータ記憶容量を提供する。補助記憶
媒体1038は、コンピュータ・コード、データなどのプロ
グラムを保存するように使用され得るコンピュータ可読
媒体である。典型的には、大容量記憶装置1038は、主記
憶装置1034、1036よりも一般的には低速の、ハードディ
スクもしくはテープなどの記憶媒体である。大容量記憶
装置1038は、磁気もしくは紙のテープリーダまたは、他
のよく知られたデバイスの形態を取り得る。適切な場合
には、大容量記憶装置1038内に保持された情報は、標準
的なやり方により仮想メモリしてのRAM 1036の一部とし
て組み込まれ得る。CD-ROMなどの特定の主記憶装置1034
もまた、CPU1032に対して単一方向的にデータを渡す。

【００３４】CPU1032は、また単数ないし複数のI/O装置
1040にも連結されるが、I/O装置1040が、ビデオモニ
タ、トラックボール、マウス、キーボード、マイクロフ
ォン、接触ディスプレイ、変換器カードリーダ、磁気も
しくは紙のテープリーダ、タブレット、スタイラス、音
声もしくは手書き文字認識器、または、もちろん他のコ
ンピュータなどのよく知られた入力デバイスを含み得る
が、これらに限定されるわけではない。最後に、CPU103
2が、オプションとして、一般的には1012で示されたネ
ッワーク接続を使用して、ローカル・エリア・ネッワー
ク、インターネット・ネッワーク、イントラネット・ネ
ッワークなどのコンピュータ・ネッワークもしくは、通
信ネッワークに連結され得る。そうしたネッワーク接続
により、前述の方法の工程を実行する上でCPU1032が、
ネッワークから情報を受信するか、情報をネッワークに
出力することが考えられる。CPU1032を使用して実行さ
れるべき一連の命令として表されるそうした情報は、た
とえば搬送波で具体化されたコンピュータ・データ信号
の形態で、ネッワークから受信したり、ネットワークに
出力され得る。前述のデバイスおよび情報は、コンピュ
ータのハードウェア・ソフトウェア技術に熟練した当業
者が、熟知しているであろう。

【００３５】前述の如く、仮想マシンはコンピュータ・
システム1030で実行され得る。図８は、図７のコンピュ
ータ・システム1030によりサポーされるとともに本発明
を実行するのに適した仮想マシンの概略図である。たと
えばカリフォルニア州、PaloAltoのSun Microsystems社
により開発されたJavaプログラミング言語などで記載さ
れたコンピュータ・プログラムが実行されるとき、ソー
ス・コード1110が、コンパイル時の環境1105内でコンパ
イラ1120に与えられる。コンパイラ1120は、ソース・コ
ード1110をバイトコード1130へ翻訳する。一般的には、
ソース・コード1110は、ソース・コード1110がソフトウ
ェア開発業者により生成される時点でバイトコード1130
へ翻訳される。

【００３６】バイトコード1130は、一般的には、たとえ
ば図７のネッワーク1012などを介して再生されるか、ダ
ウンロードされるか、配布されるか、さもなければ、図
７の主記憶装置1034などに保存され得る。上述した実施
形態においては、バイトコード1130はプラットフォーム
独立型である。すなわちバイトコード1130は、適切な仮
想マシン1140を実行するほとんどどのコンピュータ・シ
ステム上でも実行され得る。たとえば、Java環境におい
てバイトコード1130は、Java仮想マシンを実行するコン
ピュータ・システム上で実行され得る。

【００３７】バイトコード1130は、仮想マシン1140を含
むランタイム環境1135に対して与えられる。ランタイム
環境1135は、一般的には、図７のCPU1032などのプロセ
ッサを使用して実行され得る。仮想マシン1140は、コン
パイラ1142、インタプリタ1144、ランタイム・システム
1146を含んでいる。バイトコード1130は、一般的には、
コンパイラ1142またはインタプリタ1144のいずれかに対
して与えられ得る。

【００３８】バイトコード1130がコンパイラ1142に提供
されると、バイトコード1130に含まれた方法が、前述の
如くマシン命令へコンパイルされる。一方、バイトコー
ド1130がインタプリタ1144に対する提供されると、バイ
トコード1130が、１回に１バイトコードずつインタプリ
タ1144へ読み込まれる。各バイトコードがインタプリタ
1144内に読み込まれると、インタプリタ1144がバイトコ
ードにより定義された動作を実行する。一般的には、イ
ンタプリタ1144は、ほとんど連続的にバイトコード1130
を処理するとともにバイトコード1130と関連する動作を
実行する。

【００３９】オペレーティング・システム1160からある
方法が呼び出されると、その方法が解釈された方法とし
て呼び出しび出されることが決定されたのであれば、ラ
ンタイム・システム1146はインタプリタ1144からその方
法を取得し得る。他方、もしその方法がコンパイルされ
た方法として呼び出しび出されることが決定されたので
あれば、ランタイム・システム1146はコンパイラ1142を
起動する。それから、コンパイラ1142がバイトコード11
30からマシン命令を生成し、マシン語命令を実行する。
一般的には、マシン語命令は仮想マシン1140が終了する
ときに廃棄される。

【００４０】本発明の僅かな実施形態のみが記載された
が、本発明が、その精神もしく範囲から逸脱せずに他の
多くの特定形態で具体化され得ることを理解すべきであ
る。たとえば、干渉グラフの生成および操作と関連する
諸々の工程が、再整理され、削除され、付加され得る。
一般的には、本発明の方法に関するものである諸々の工
程は、本発明の精神もしくは範囲から逸脱することなく
再整理され、削除され、付加され得る。

【００４１】特定レジスタに結び付けられる変数もしく
は値が、サブルーチンに対する呼び出しもしくは、一定
の方法に対する入力パラメータと関連するものとして記
載されたが、変数は種々の異なる理由によりレジスタに
結び付けられ得ることを理解すべきである。たとえば、
一部の実施形態においては、ある変数がコンピュータ・
プログラムの実行中にアクセス可能となるように、この
変数をレジスタに結び付け得る。

【００４２】特定レジスタに対する値のバインドがここ
までに記載されてきた。あるプロセッサと関連するレジ
スタの数が固定されていることから、ある場合には、レ
ジスタに結び付けられるのに適した値の数が使用可能な
レジスタの数を超えることがある。そうした場合、値は
レジスタの代わりにスタック・スロットに結び付けられ
得る。そうしたスタック・スロットは、ほとんどどの適
宜の手法を使用しても割り当てられ得る。一実施形態に
おいては、スタック・スロットは、レジスタが割り当て
られるのと同一のよう式でレジスタ・アロケータにより
割り当てられ得る。

【００４３】レジスタ・マスクと関連するビットの数
は、一般的には、たとえばレジスタ・マスクが関連する
プラットフォームによって幅広く変更され得る。本発明
は、Intelプラットフォームで使用されるのに適したも
のとして記載されたが、本発明は、Power PCプラットフ
ォームおよびSparcプラットフォームに限定されるわけ
ではないが、これらを含む、ほとんどどの適宜なプラッ
トフォームでも使用されるように実施され得る。従っ
て、本発明は限定的でなく例示的なものと解釈されるべ
きであり、また本発明は、本明細書中に与えられた詳細
内容に限定されるものでなく、添付の請求の範囲の範囲
内において変更され得るものである。

【図面の簡単な説明】

【図１】ソース・コードのセグメントの内部表現を生成
するように配置されたレジスタ・アロケータを備えたコ
ンパイラの概略図である。

【図２】ソース・コードのセグメントすなわち図１のソ
ース・コード102のセグメント120に対する干渉グラフの
概略図である。

【図３】本発明の実施形態に従った、ソース・コードの
セグメントの簡略な内部表現を生成するように配置され
たレジスタ・アロケータを備えたコンパイラの概略図で
ある。

【図４】本発明の実施形態に従った、ソース・コードの
セグメントすなわち図３のソース・コード302のセグメ
ント320に対する干渉グラフの概略図である。

【図５】本発明の実施形態に従った、レジスタ・マスク
の概略図である。

【図６】本発明の実施形態に従った、干渉グラフの生成
および操作と関連する工程を示す処理フローチャートで
ある。

【図７】本発明を実行するのに適した汎用コンピュータ
・システムの概略図である。

【図８】図７のコンピュータ・システムによりサポート
されるとともに本発明を実行するのに適した仮想マシン
の概略図である。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 クリフォード エヌ． クリック， ジュ ニア アメリカ合衆国， カリフォルニア州， サン ノゼ， ウォーレイス ドライヴ 955 (72)発明者 クリストファー エー． ヴィック アメリカ合衆国， カリフォルニア州， サン ノゼ， リオ グランデ ドライヴ 5290 (72)発明者 マイケル エイチ． パレッツィニィ アメリカ合衆国， カリフォルニア州， サニーヴェイル， アリバ ドライヴ 241 ナンバー 10

Claims (20)

【特許請求の範囲】
1. 【請求項１】 オブジェクトベースの計算システムにお
   いてメモリスペースを割り当てる、コンピュータによっ
   て実行する方法であって、 第1変数と関連するコード・セグメントを含み、さらに
   第2変数と関連するコード・セグメントを含むソース・
   コードを取得し、 第1変数を第1レジスタへ結び付け、 第2変数と関連する第1有効範囲を取得し、 第2変数の表現を含むように配置され、さらに第1変数の
   表現を含まないように配置された干渉グラフの生成を含
   めた、レジスタ割り当てを実行することを含む、コンピ
   ュータによって実行する方法。
2. 【請求項２】 第1変数と関連するコード・セグメント
   を含むソース・コードの取得が、サブルーチンに対する
   呼び出しの取得を含み、サブルーチンに対する呼び出し
   がその呼び出しにおける引数としての第1変数を含む、
   請求項１に記載のコンピュータによって実行する方法。
3. 【請求項３】 第1変数と関連するコード・セグメント
   を含むソース・コードの取得が、第1変数を入力パラメ
   ータして含む関数の取得を含む、前記請求項のいずれか
   に記載のコンピュータによって実行する方法。
4. 【請求項４】 ソース・コードの取得が、さらに第3変
   数と関連するコード・セグメントの取得を含み、このコ
   ンピュータによって実行する方法が、さらに第3変数と
   関連する第2有効範囲の取得を含む、前記請求項のいず
   れかに記載のコンピュータによって実行する方法。
5. 【請求項５】 干渉グラフがさらに第3変数の表現を含
   むように配置され、レジスタ割り当ての実行が、第1有
   効範囲および第2有効範囲が少なくとも部分的に重複す
   るか否かを決定し、第1有効範囲および第2有効範囲が少
   なくとも部分的に重複することが決定されたときに干渉
   グラフに対し、第1有効範囲および第2有効範囲が少なく
   とも部分的に重複するということを表示するように配置
   された表示の付加を有する、干渉グラフでの彩色プロセ
   スを実行することをさらに含む、請求項４に記載のコン
   ピュータによって実行する方法。
6. 【請求項６】 レジスタ割り当ての実行が、第2変数に
   対する第2レジスタの割り当て、第3変数に対する第3レ
   ジスタの割り当てをさらに含み、第2変数に対する第2レ
   ジスタの割り当てが、第3変数に対する使用可能レジス
   タのリストからの第2レジスタの除去を含む、請求項５
   に記載のコンピュータによって実行する方法。
7. 【請求項７】 レジスタ割り当ての実行が、第2変数に
   対する第2レジスタの割り当て、第3変数に対するスタッ
   ク・スロットの割り当てをさらに含み、第2変数に対す
   る第2レジスタの割り当てが、第3変数に対する使用可能
   なレジスタスタック・スロットのリストからの第2レジ
   スタの除去を含む、請求項５に記載のコンピュータによ
   って実行する方法。
8. 【請求項８】 レジスタ割り当ての実行が、第2変数に
   対する第1スタック・スロットの割り当て、第3変数に対
   する第2スタック・スロットの割り当てをさらに含む、
   請求項５に記載のコンピュータによって実行する方法。
9. 【請求項９】 第1変数と関連する第2有効範囲の取得を
   さらに含み、第1有効範囲および第2有効範囲が少なくと
   も部分的に重複する、前記請求項のいずれかに記載のコ
   ンピュータによって実行する方法。
10. 【請求項１０】 メモリスペースを割り当てるように配
    置されたコンピュータ・システムであって、 プロセッサと、 第1変数と関連するコード・セグメントを含むとともに
    第2変数と関連するコード・セグメントをさらに含むソ
    ース・コードを取得するように配置されたソース・コー
    ド入力機構と、 プロセッサと関連する第1レジスタに対する第1変数を結
    び付けるように配置されたバインド機構と、 第2変数と関連する第1有効範囲を取得するように配置さ
    れた有効範囲識別子と、 第2変数の表現を含むように配置されるとともに第1変数
    の表現を含まないように配置された干渉グラフを生成す
    るように配置されたレジスタ・アロケータとを含む、コ
    ンピュータ・システム。
11. 【請求項１１】 ソース・コード入力機構が、さらに、
    サブルーチンに対する呼び出しであって、第1変数と関
    連するコード・セグメントに含まれるとともに引数とし
    て第1変数を含むサブルーチンに対する呼び出しを取得
    するように配置される、請求項１０に記載のコンピュー
    タによって実行する方法。
12. 【請求項１２】 ソース・コード入力機構が、さらに、
    第1変数と関連するコード・セグメントに含まれた関数
    であって入力パラメータとして第1変数を含む関数を取
    得するように配置される、請求項１０および１１の一方
    に記載のコンピュータによって実行する方法。
13. 【請求項１３】 ソース・コード入力機構が、さらに、
    第3変数と関連するコード・セグメントを取得するよう
    に配置され、有効範囲識別子が、さらに、第3変数と関
    連する第2有効範囲を取得するように配置される、請求
    項１０ないし１２のいずれかに記載のコンピュータによ
    って実行する方法。
14. 【請求項１４】 干渉グラフが、さらに、第3変数の表
    現を含むように配置され、レジスタ・アロケータが、第
    1有効範囲および第2有効範囲が少なくとも部分的に重複
    するか否かを決定するように配置された決定手段と、第
    1有効範囲および第2有効範囲が少なくとも部分的に重複
    することが決定されたときに、第1有効範囲および第2有
    効範囲が少なくとも部分的に重複するということを表示
    するように配置された表示を干渉グラフに付加すること
    により干渉グラフでの彩色プロセスを実行するように配
    置された彩色手段とを含む、請求項１３に記載のコンピ
    ュータによって実行する方法。
15. 【請求項１５】 オブジェクトベースの計算システムに
    おいてメモリスペースを割り当てるコンピュータ・プロ
    グラム製品であって、 第1変数と関連するコード・セグメントを含み、さらに
    第2変数と関連するコード・セグメントを含むソース・
    コードを取得するコンピュータ・コードと、 第1変数を第1レジスタに結び付けるコンピュータ・コー
    ドと、 第2変数と関連する第1有効範囲を取得するコンピュータ
    ・コードと、 第2変数の表現を含むように配置され、さらに第1変数の
    表現を含まないように配置された干渉グラフを生成する
    コンピュータ・コードを含むとともに、レジスタ割り当
    てを実行するコンピュータ・コードと、 コンピュータ・コードを保存するコンピュータ可読媒体
    とを含む、コンピュータ・プログラム製品。
16. 【請求項１６】 コンピュータ可読媒体が、搬送波で具
    体化されたデータ信号、フロッピー（登録商標）・ディ
    スク、CD-ROM、テープ・ドライブ、光デバイス、フラッ
    シュ・メモリ、ハードディスク・ドライブからなる群か
    ら選ばれた１種である、請求項１５に記載のコンピュー
    タ・プログラム製品。
17. 【請求項１７】 第1変数と関連するコード・セグメン
    トを含むソース・コードを取得するコンピュータ・コー
    ドが、引数として第1変数を含むサブルーチンに対する
    呼び出しを取得するコンピュータ・コードを含む、請求
    項１５および１６のいずれかに記載のコンピュータ・プ
    ログラム製品。
18. 【請求項１８】 第1変数と関連するコード・セグメン
    トを含むソース・コードを取得するコンピュータ・コー
    ドが、第1変数を入力パラメータとして含む関数を取得
    するコンピュータ・コードを含む、請求項１５ないし１
    ７のいずれかに記載のコンピュータ・プログラム製品。
19. 【請求項１９】 ソース・コードを取得するコンピュー
    タ・コードが、第3変数と関連するコード・セグメント
    を取得するコンピュータ・コードをさらに含み、このコ
    ンピュータ・プログラム製品が、第3変数と関連する第2
    有効範囲を取得するコンピュータ・コードをさらに含
    む、請求項１５ないし１８のいずれかに記載のコンピュ
    ータ・プログラム製品。
20. 【請求項２０】 干渉グラフを生成するコンピュータ・
    コードが、干渉グラフにおいて第3変数の表現を含むよ
    うに配置され、レジスタ割り当てを実行するコンピュー
    タ・コードが、第1有効範囲および第2有効範囲が少なく
    とも部分的に重複するか否かを決定するコンピュータ・
    コードと、第1有効範囲および第2有効範囲が少なくとも
    部分的に重複することが決定されたときに、干渉グラフ
    に対し第1有効範囲および第2有効範囲が少なくとも部分
    的に重複するということを表示するように配置された表
    示を付加するコンピュータ・コードを、干渉グラフでの
    彩色プロセスを実行するコンピュータ・コードが含むよ
    うな、干渉グラフでの彩色プロセスを実行するコンピュ
    ータ・コードとをさらに含む、請求項１９に記載のコン
    ピュータ・プログラム製品。