JPH03260732A - レジスタ割り付け方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明はソースプログラムを解析して実行効率のよい
目的プログラムを生成するコンパイラにおけるレジスタ
割り付け方式に関するものである。

（従来の技術） 第３図は従来のコンパイラの基本的な構成を示すもので
、コンパイラは、ソースプログラム（１）を人力し、構
文解析部（２）によって構文のチエツクを行うとともに
、適切な中間コードに変換し、以下、記憶域の割り当て
部（３）　　最適化部（４）及びレジスタ割り付け部（
５）の処理を経て、コード生成部（６）　によって最終
的な目的プログラム（７）を生成すようになっている。

実行効率のよい目的プログラムを生成するためには、各
種の最適化技術の中でもレジスタ割り付けの最適化が重
要な位置を占めている。コンパイラの作成に関する標準
的な著作であるＡｈｏ等による°’Ｃｏｍｐｉｌｅｒｓ
　Ｐｒ１ｎｃｉｐｌｅｓ、　ｔｅｃｈｎｉｑｕｅｓ、ａ
ｎｄＴｏｏｌｓ　　　　　（八ｄｄｉｓｏｎ−Ｗｅｓｌ
ｅｙ　　Ｐｕｂｌｉｓｈｉｎｇ　　Ｃｏｍｐａｎｙ。

１９８６）では、プログラムを基本ブロックと呼ばれる
連続するステートメントの列に分割し、これらの基本ブ
ロックに対して局所的なレジスタ割り付けを行い、残っ
たレジスタを用いてより広い範囲を対象にした大域的レ
ジスタ割り付けを行う方式を代表的なレジスタ割り付け
方式として述べている。

理論的には、レジスタ割り付けは、割り付けの対象とな
るデータと有限個のレジスタとの間のマツピングを決定
する問題に帰着できるが、最適解を求めることは甚だ困
難であることが知られている。

従って、種々の発見的な手法が従来より開発されている
。大域的なレジスタ割り付けを例にとると、プログラム
中に存在するループ毎にレジスタを割り付けていくのが
典型的な処理である。これはプログラム全体の実行時間
のうち、ループの実行に占める割合が非常に高いという
経験則に基づいている。一つの方法は、ループ中に出現
する頻度か高いデータの順にレジスタを割り付けていく
ことである。この方法では、データとレジスタとのマツ
ピングは一対一である。すなわち、あるデータに一度割
り付けられたレジスタはループの全範囲で固定的にその
データに対応している。

上述の大域的レジスタ割り付け方式は単純なアルゴリズ
ムでわかりゃすいものであるが、レジスタの割り付け効
率という点では不十分なところがある。

ｃｈａｉｔｉｎ等はレジスタの割り付けをグラフの彩色
問題として解析することにより、より効率的な大域的レ
ジスタ割り付け方式を開発した。これは、レジスタの割
り付けの対象となるデータをグラフ上のノードに対応さ
せ、プログラム中の任意の地点で同時に生きているデー
タに関しては、対応するノード間を線で結ぶ。このよう
にして得られたグラフをレジスタの干渉グラフと呼ぶ。

グラフの彩色とは、干渉グラフ上に隣り合うノード（線
で結ばれたノード）には互いに異なる色をぬることであ
り、彩色に用いられる色がレジスタに対応する。ある有
限個の色を使って干渉グラフ上の全てのノードを彩色す
ることができないとぎ、プロフィツトが最も小さいノー
ドを選び、４のノートをグラフ上から除去することによ
って彩色処理を継続するというような手法が提案されて
いる。なお、グラフの彩色を使用したレジスタ割り付け
方式はｃｈａｉｔｉｎ等による”Ｒｅｇｉｓｔｅｒ　Ａ
ｌ−１ｏｃａｔｉｏｎ　Ｖｉａ　Ｃｏｌｏｒｉｎｇ　　
（Ｃｏｍｐｕｔｅｒ　ＬａｎｇｕａｇｅｓＶｏｌ、　６
．１９８１　ｐｐ、４７−５７）及びＣｈａｉｔｉｎに
よる”Ｒｅｇｉｓｔｅｒ　Ａ１１ｏｃａｔｉｏｎ　ａｎ
ｄ　Ｓｐｉｌｌｉｎｇ　Ｖｉａ　ＧｒａｐｈＣｏｌｏｒ
ｉｎｇ　　（Ｐｒｏｃｅｅｄｉｎｇ　５ＩＧＰＬＡＮ８
２．　Ｓｙｍｐｏｓｉｕｍｏｎ　Ｃｏｍｐｉｌｅｒ　Ｃ
ｏｎ５ｔｒｕｃｔｉｏｎ、　５ＩＧＰＬＡＮ　Ｎｏｔｉ
ｃｅｓ。

１９８２、　ｐｐ９８−１０５）に詳細が記述されてい
る。

以上に述べたレジスタ割り付け方式では、いずれの場合
でも、レジスタ割り付けの対象となるデータにレジスタ
が割り付けられた時に、割り付けられなかった場合と比
べてどの程度利益があるかを示すプロフィツトを算出し
、このプロフィツトを評価することがレジスタ割り付け
の処理において重要な役割を果たしている。

（発明が解決しようとする課題） 従来のレジスタ割り付けレテ式では、レジスタ割り付け
の対象となるデータに関してプロフィツトを求めておき
、そのプロフィツトの値を評価して、レジスタを割り付
けるべきデータの集合を決定したり、逆に、割り付けの
候補から除外すべきデータを決定するというようなこと
が行われていた。

しかし、データとレジスタとのマツピングを決定する処
理に先立って一括してプロフィツトを計算するため、上
記のマツピングを決定する処理の進行に伴い、 ・配列要素と当該配列要素のインデックス・ポインタと
当該ポインタによって示されるデータ のように、一方のデータに対するレジスタ割り付けの状
況に応じて、他方のデータのプロフィツトの値が変化す
るようなケースでは、プロフィツトの評価が正確に行わ
れずレジスタ割り付けの効率が低下するという問題点が
あった。

上記の様子を図面を参照しながら説明する。第４図は、
ＦＯＲＴＲＡＮプログラムの一部（８）　を示すもので
あるが、これに対応する中間コードにおいて、ステート
メント（９）から始まるＤＯループに含まれるステート
メント（ｌＯ）〜（１３）に出現するデータの参照回数
が第５図に示すように求められたとする。簡単のために
、上記のプロフィツトをデータの参照回数と考える。３
個のレジスタを使用して、このループに現れるデータに
対してプロフィツトの大きい順に一対−にレジスタを割
り付けると、第６図に示すような結果が得られる。

レジスタが割り付けられたデータ集合（１４）の中に、
添字Ｉの値を評価した結果のインデックス１ｎｄｅｘと
１ｎｄｅｘによって間接参照される配列要素＾（ｉｎｄ
ｅｘ）が共に含まれている。しかし、Ａ　（ｉｎｄｅｘ
）にレジスタが割り付けられた結果、ステートメント（
１０）に現れるＡ　（ｉｎｄｅｘ）の最初の参照を除い
ては、１ｎｄｅｘを用いる必要がなくなる。

従って、１ｎｄｅｘの実質的な参照回数は３だけ減って
３になる。第５図によれば、１ｎｄｅｘの実質的な参照
回数は全体の中で第４番目に位置するので、１ｎｄｅｘ
の代わりに、レジスタが割り付けていないデータ集合（
１５）にに含まれる他のデータＴにレジスタを割り付け
る方が効率のよい目的プログラムとなる。

この発明は上記のような問題点を解消するためになされ
たもので、レジスタ割り付けの過程でプロフィツトの値
が変化することを防ぎ、効率的な目的プログラムが得ら
れるレジスタ割り付け方式を提供することを目的とする
。

〔課題を解決するための手段〕

この発明に係るレジスタ割り付け方式は、レジスタ割り
付けの処理を２つの段階に分け、第１段階で、レジスタ
割り付け処理のために使用可能な物理レジスタの個数以
下の記号レジスタを用いて、配列要素又はポインタによ
って指されるデータのように目的プログラムのレベルで
間接的に参照されるデータを対象に記号レジスタを割り
付け、第２段階で、上記の処理によって記）レジスタが
割り付けられた間接参照データを記号レジスタに置換し
た中間コードに関して、記号レジスタとスカラデータな
対象にして物理レジスタを割り付けるようにしたもので
ある。

〔作用） この発明においては、上記の第１段階の処理によって、
プログラム中の一部のデータに対して記号レジスタが割
り付けられ、その情報を中間コードに反映した後に、第
２段階の処理によって、これらの記号レジスタと第１段
階の処理対象外であるスカラデータに対して最終的な物
理レジスタ割り付けが行なわれ、プログラム中のデータ
に対するレジスタ割り付けが完了する。

（実施例） 以下、この発明の一実施例について説明する。

第１図は本実施例に係るレジスタ割り付け部の構成を示
したものである。第１図において、（１６）は前の処理
部から受は渡された中間コード、（１７）はレジスタ割
り付け情報、（１８）は記号レジスタを含む中間コード
、（１９）は物理レジスタを含む中間コードであり、ま
た、本実施例におけるレジスタ割り付け部（５）は、間
接参照データに対する記号レジスタ割り付け部（５ａ）
と、中間コードの変換部（５ｂ）及び物理レジスタ割り
付け部（５Ｃ）でなる。

上記間接参照データに対する記号レタス４割り付け部（
５ａ）では、中間コード（１６）を入力し、間接参照デ
ータすなわち配列要素又はポインタによって指されるデ
ータだけを対象にして記号レジスタを割り付け、その結
果がレジスタ割り付け情報（１７）として出力される。

レジスタ割り付けの範囲は特に限定しないが、通常はル
ープ毎又はプログラム全体を対象にした大域的な割り付
けを行う。

なお、ここでいう記号レジスタとは、最終的には物理レ
ジスタと一対一に対応するが、特定のレジスタ番号はま
だ決定していない状態のレジスタを意味する。ただし、
特別な場合として物理レジスタそのものであってもよい
。

ループ毎に間接参照データに対する記号レジスタ割り付
けを行う場合のフローチャートを第２図に示す。以下で
は、第２図に沿ってこの処理を説明する。

まず、レジスタ割り付けの対象となるループを探す（ス
テップＳｌ）。多重にネストしたループの場合、最内側
のループの実行回数が最も多いので、レジスタ割り付け
では最内側のループから未処理のループを探していく。

未処理のループが存在しない場合、処理は終了する（ス
テップＳ２）。

そうでなければ、当該ループ中に現れる間接参照データ
の集合■を求める（ステップＳ３）。配列要素の場合、
添字式を解析して、添字が同一の値をもつものは集合Ｖ
中の一つの要素とする。ポインタによって指されるデー
タの場合も同様に、ポインタが同一の値をもつものは集
合Ｖ中の一つの要素とする。

集合■が空（ステップＳ４）、すなわち割り付けの対象
となるデータが存在しない場合、次のループの処理に移
る（ステップＳｌ）。そうでない時、割り付けに使用す
る記号レジスタの集合Ｒを求める（ステップＳ５）。

記号レジスタの数は使用可能な物理レジスタの個数以下
であり、どの程度の個数にするかはループ中に現れる間
接参照データが全データの中でどの程度の割合を占める
か等を調べて決定する。

次に、集合■の各要素についてプロフィツトを算出する
（ステップＳ６）。簡単のために、ここではプロフィツ
トとして参照回数を考える。

次に、集合■の中でプロフィツトが最大のデータｖＩを
探して、これに集合Ｒの中の任意の記号レジスタＲ」を
割り付ける（ステップＳ７）。

その後で、集合■から割り付けの対象となったデータｖ
Ｉを取り除き（ステップＳ８）、集合Ｖが空（ステップ
５９）ならば次のループの処理に移る（ステップＳｌ）
。そうでなければ、集合Ｒから割り付けに使用した記号
レジスタＲ，を取り除く（ステップ５１０　）。集合Ｒ
が空（ステップ５１１）ならば、次のループの処理に移
る（ステップＳＬ）。そうでなければ、次のデータに対
する割り付けに移る（ステップＳ７）。

第１図に戻って説明を続ける。次に、中間コードの変換
部（５ｂ）では、レジスタ割り付け情報（１７）を参照
し、上記の処理によって記号レジスタが割り付けられた
間接参照データに対して、中間コード（１６）上で記号
レジスタに置ぎ換える処理を行う。その結果、記号レジ
スタを含む中間コード（１８）が生成される。

ソースプログラムの表現に近い高位レベルの中間コード
の場合には、配列要素又はポインタによりて指されるデ
ータに関する参照を単純に記号レジスタに置き換えるだ
けでよいが、機械語の表現に近い低位レベルの中間コー
ドの場合には、間接参照データに対する参照が複数のテ
キストによって表わされているので、例えば、当該配列
要素に対するインデックスのロード命令を削除するよう
な処理も合わせて必要になる。

次に、物理レジスタ割り付け部（５Ｃ）では、上記の処
理によって変換された記号レジスタを含む中間コード（
１８）に関して、記号レジスタとスカラデータを対象に
物理レジスタを割り付け、物理レジスタを含む中間コー
ド（１９）が出力される。

間接参照データについては、間接参照データに対する記
号レジスタ割り付け部（５ａ）で既に処理しており、た
とえ未割り付けの間接参照データが存在しても、物理レ
ジスタ割り付けの対象とはしない。

また、記号レジスタに対しては、必ず物理レジスタが割
り付けられなければならないが、記号レジスタの数を物
理レジスタの数置下に制限しているので、これは原理的
に保証される。

間接参照データに対する記号レジスタ割り付け部（５ａ
）と同様に、レジスタ割り付けの範囲は特に限定しない
。ループ毎の割り付けについては、間接参照データに対
する記号レジスタ割り付け部（５ａ）の処理で説明した
のと同様な方法が適用できる。ここで、記号レジスタに
関してはプロフィツトの値を無限大に設定し、スカラデ
ータよりも優先的に割り付けが行われるようにする。

なお、上記実施例では、各段階の処理でループ毎に大域
レジスタ割り付けを行うものとして説明したが、グラフ
彩色法等地の割り付け方式を使用してもかまわない。ま
た、レジスタ割り付け部の内部構成は各処理部が連続し
ているものとして説明したが、中間コードの変換部（５
ｂ）と物理レジスタ割り付け部（５ｃ）は離れていても
よく、例えば最適化処理部が間に入ってもかまわない。

〔発明の効果〕

以上のように、この発明によれば、レジスタ割り付けの
処理を２つの段階に分け、間接参照データに対する割り
付けと通常のスカラデータに対する割り付けを分離した
構成にしたので、間接参照データと間接インデックスの
対に関して、一方のデータに対するレジスタ割り付けの
状況に応じて、他方のデータをプロフィツトが変化する
ということがなくなり、正確なプロフィツトを求めるこ
とができるようになったため、より精度の高いレジスタ
割り付けができ、効率のよい目的プログラムが得られる
という効果がある。

また、マシンアーキテクチャによっては、特定の命令又
は特定のデータ参照方式に対しては使用できるレジスタ
に制限がつくことがあり、第１段階の処理で記号レジス
タを使用することにより、第２段階の処理開始時点では
特定のレジスタ番号は決定していないので、第２段階の
処理で一括してターゲットマシンに依存したより極めの
細かい割り付けができるという効果もある。

【図面の簡単な説明】

第１図はこの発明の一実施例におけるレジスタ割り付け
部の構成図、第２図はこの発明の一実施例におけるレジ
スタ割り付け部の中の間接参照データに対する記号レジ
スタ割り付け部の処理概要を示すフローチャート、第３
図はコンパイラの基本構成図、第４図はこの発明が解決
しようとする課題を説明するためのＦＯＲＴＲＡＮプロ
グラムの一部を示す説明図、第５図は第４図のプログラ
ム−のＤＯループ中におけるデータの参照回数を表す説
明図、第６図は従来の方式でレジスタ割り付けを行った
場合のデータとレジスタとのマツピング関係を示す説明
図である。 図面において、（１）はソースプログラム、（５）はレ
ジスタ割り付け部、（５ａ）は間接参照データに対する
記号レジスタ割り付け部、（５ｂ）は中間コードの変換
部、（５Ｃ）は記号レジスタとスカラデータに対する物
理レジスタ割り付け部、（７）は目的プログラム、（１
６）は中間コード、（１７）はレジスタ割り付け情報、
（１８）は記号レジスタを含む中間コード、（１９）は
物理レジスタを含む中間コードを示す。 なお、各図中、同一符号は同一または相当部分を示す。

Claims (1)

【特許請求の範囲】
1. ソースプログラムを解析し、有限個のレジスタと該レジ
   スタの総容量に比べて十分大きい記憶容量を有し該レジ
   スタよりも遅いアクセス時間を有するメモリに接続され
   るプロセッサに対する目的プログラムを生成するコンパ
   イラにおいて、第１段階として、使用可能な物理レジス
   タの個数以下の記号レジスタを用いて、配列要素又はポ
   インタによって示されるデータのように目的プログラム
   のレベルで間接インデックスによってアクセスされる間
   接参照データを対象に記号レジスタを割り付け、第２段
   階として、上記の処理によって記号レジスタが割り付け
   られたデータを記号レジスタに置換した中間コードに関
   して、記号レジスタとスカラデータを対象に物理レジス
   タ割り付けを行うことを特徴とするレジスタ割り付け方
   式。