JPH08123692A - レジスタ割り付け方法および装置 - Google Patents

Abstract

(57)【要約】 【目的】 コンパクトで実行効率のよい目的プログラム
を生成するためのレジスタ割り付け方法、および、その
ような機能を持つコンパイラ装置を提供する。 【構成】 まず選択割り付け要求を中間コードのレジス
タ情報に設定し（ステップＳ１）、その中間コードのオ
ペランドレジスタ割り付け処理を行う（ステップＳ
２）。次に上記選択割り付け要求に係るオペランドにレ
ジスタが割り付けられているかどうかを調べ（ステップ
Ｓ３）、レジスタが割り付けられていれば、対応する作
業用レジスタの割り付けを行わない。上記選択割り付け
要求に係るオペランドにレジスタが割り付けられていな
ければ、上記作業用レジスタの割り付けを行う（ステッ
プＳ４）。不必要な作業用レジスタの割り付けを省くこ
とにより、生成される目的プログラムが簡単になる。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明はコンパイラに係り、目的
プログラム（オブジェクト・プログラム）を生成するた
めのレジスタ割り付け方式に関する。

【０００２】

【従来の技術】マイクロプロセッサ等の情報処理装置に
おいて、コンパイラ装置はソースプログラムを解釈し
て、機械語レベルの目的プログラムに翻訳する役割を果
たす。このとき、ソースプログラムを一旦中間言語で記
述された中間コード（中間言）に変換し、中間コードか
ら目的コードを生成することが多い。中間コードから目
的コードを生成する際には、必要に応じてコードの最適
化およびレジスタ割り付けが行われる。

【０００３】コンパイラ装置におけるレジスタ割り付け
処理においては、中間コード毎に作成されるオブジェク
ト展開に必要なレジスタ割り付け要求情報を基にして、
出現した中間コードに対して使用可能なレジスタの種類
と個数を割り付けている。

【０００４】一つの中間コード内において、オブジェク
ト展開に一時的に使用するレジスタ（以後、作業用レジ
スタと呼ぶ）は、オペランドがレジスタに乗った場合に
比べて、乗らなかった場合の方が多く必要とすることが
多々ある。

【０００５】しかし、オペランドがレジスタに乗るか否
かは、実際にレジスタ割り付け処理を行わないと判定で
きない。このため、オペランドがレジスタに乗った場合
と乗らなかった場合の両方を満足する情報が、レジスタ
割り付け要求情報として、オブジェクト展開を行う処理
部に渡されることになる。すなわち、オペランドがレジ
スタに乗らなかった場合に必要となる作業用レジスタの
種類と個数が要求されていた。

【０００６】

【発明が解決しようとする課題】上述のような従来のレ
ジスタ割り付け要求情報に基づくレジスタ割り付け処理
では、オペランドがレジスタに乗った場合でも、乗らな
かった場合と同じだけの数の作業用レジスタが確保され
る。つまり、必要のない作業用レジスタが余分に割り付
けられることになる。

【０００７】割り付け確保されるレジスタの個数が増え
ると、目的プログラムの実行時にレジスタの値をメモリ
上に退避する処理が行われる確率が高くなる。退避処理
の出現回数が多いほど、オブジェクトサイズが増加し、
目的プログラムの実行速度が低下する。

【０００８】したがって、従来のレジスタ割り付け処理
においては、作業用レジスタのレジスタ割り付けに無駄
が多く、最適な目的プログラムが生成されないという問
題がある。

【０００９】本発明は、コンパイラ装置においてコンパ
クトで実行効率のよい目的プログラムを生成するための
レジスタ割り付け方法、および、そのような機能を持つ
コンパイラ装置を提供することを目的とする。より具体
的には、無駄な作業用レジスタの割り付けを行わないこ
とを目的とする。

【００１０】

【課題を解決するための手段】図１は本発明のレジスタ
割り付け処理の原理を示すフローチャートである。図１
において処理が開始されると、まず中間コードのオペラ
ンドと該オペランドに対応する作業用レジスタのうちの
一方にレジスタを割り付ける選択割り付け要求を中間コ
ードのレジスタ情報に設定し（ステップＳ１）、その中
間コードのオペランドレジスタ割り付け処理を行う（ス
テップＳ２）。

【００１１】そして、次に上記選択割り付け要求に係る
オペランドにレジスタが割り付けられているかどうかを
調べ（ステップＳ３）、レジスタが割り付けられていれ
ば、対応する作業用レジスタの割り付けを行わない。上
記選択割り付け要求に係るオペランドにレジスタが割り
付けられていなければ、上記作業用レジスタの割り付け
を行う（ステップＳ４）。

【００１２】上記レジスタ情報とは、例えば中間コード
毎に作成されるレジスタ割り付け要求情報であり、選択
割り付け要求は例えばフラグにより設定される。また、
このとき、作業用レジスタの要求情報として上記選択割
り付け要求に係るオペランドの識別子が設定される。

【００１３】

【作用】オペランドレジスタおよび作業用レジスタに対
してレジスタ割り付けを行う前に、選択割り付け要求が
レジスタ情報に設定され、次にオペランドレジスタ割り
付け処理が行われる。このオペランドレジスタ割り付け
処理において、上記選択割り付け要求に係るオペランド
または選択割り付け要求に関係しないオペランドについ
てのレジスタ割り付け処理が行われる。

【００１４】上記選択割り付け要求に係るオペランドに
レジスタが割り付けば、対応する作業用レジスタにはレ
ジスタを割り付けない。これにより、オペランドにレジ
スタが割り付いたときに作業用レジスタが不要となる中
間コードにおいて、割り付けられるレジスタ数を削減す
ることができる。したがって、レジスタが効率的に利用
され、データの退避処理を減少させることになる。

【００１５】上記選択割り付け要求に係るオペランドに
レジスタが割り付かなければ、対応する作業用レジスタ
にレジスタを割り付ける。つまり、オペランドにレジス
タが割り付いたときに作業用レジスタが不要、レジスタ
が割り付かなかったときに作業用レジスタが必要となる
場合には、結果的にオペランドと作業用レジスタのどち
らか一方にレジスタが割り付けられることになる。

【００１６】

【実施例】以下、図面を参照しながら、本発明の実施例
を詳細に説明する。本実施例のコンパイラ装置は、まず
複数個の実レジスタを備えたマイクロプロセッサ用のソ
ースプログラムの文解釈を行い、それを中間コードに展
開する。次に得られた中間コードにレジスタを割り付
け、目的コード（オブジェクトコード）に展開して、機
械命令で記述された目的プログラムを生成する。

【００１７】図２は、本実施例のコンパイラ装置による
レジスタ割り付け要求情報の作成処理のフローチャート
である。この処理は各中間コード毎に行われる。レジス
タ割り付け要求情報とは、オブジェクト展開に必要なレ
ジスタの種別、個数、およびオペランド情報などであ
り、オペランドの長さ等に応じて中間コードの種類と塊
を指定するオブジェクト・スケルトンから各中間コード
毎に作成される。コンパイラ装置は、作成されたレジス
タ割り付け要求情報に基づいてレジスタ割り付け処理を
行う。

【００１８】図２において処理が開始されると、まず処
理対象の中間コードが要求する作業用レジスタの個数
が、その中間コードのオペランドに対するレジスタ割り
付け結果によって変動するかどうかを判定する（ステッ
プＳ１１）。変動する場合は選択割り付け要求をレジス
タ割り付け要求情報に設定し（ステップＳ１２）、変動
しない場合は選択割り付け要求を設定しない。

【００１９】選択割り付け要求は、ある中間コードのオ
ペランドにレジスタが割り付いたときに作業用レジスタ
が不要、レジスタが割り付かなかったときに作業用レジ
スタが必要になることを表すレジスタ割り付け要求であ
る。言い換えれば、オペランドと作業用レジスタのどち
らか一方にレジスタを割り付ける旨の要求情報である。

【００２０】図３は、ソースプログラムのコンパイル処
理の具体例を示している。図３において、ＣＯＭＰＵＴ
Ｅ Ａ＝Ｂ＋Ｃという演算処理が中間コードＡＤＤに変
換された後、−−ＡＤＤ−−以降に示される一連の目的
コードが生成される。ここで、ＡＤＤはＣＯＭＰＵＴＥ
Ａ＝Ｂ＋Ｃに対応する中間コードのラベルである。

【００２１】生成された中間コードＡＤＤに関するレジ
スタ割り付け要求情報のうち、選択割り付けと要求レジ
スタの情報は、例えば図４のようになる。図４におい
て、ＯＰＤ１は加算の結果を格納するオペランドを表
し、ＯＰＤ２、ＯＰＤ３は加算されるオペランドを表
す。作業用はこの中間コードが要求する作業用レジスタ
を表す。ＯＰＤ１はＲＥＧで示されるレジスタを要求し
ており、ＯＰＤ２、ＯＰＤ３は特定のレジスタを要求し
ていない。また、作業用レジスタとしては８バイトのレ
ジスタが１つ要求されている。

【００２２】フラグは選択割り付け要求が設定されてい
るか否かを表す情報フラグで、例えば、ＯＮのとき選択
割り付け要求であることを表し、ＯＦＦのとき選択割り
付け以外のレジスタ要求であることを表す。

【００２３】ここでは、ＯＰＤ１とＯＰＤ２にレジスタ
が割り付いたかどうかは作業用レジスタの必要性に関係
しないため、これらのフラグはＯＦＦとなっている。こ
れに対して、ＯＰＤ３にレジスタが割り付いたときには
作業用レジスタが不要となり、ＯＰＤ３にレジスタが割
り付かなければ作業用レジスタが必要になる。つまり、
ＯＰＤ３と作業用レジスタのどちらか一方にレジスタを
割り付ければよいので、ＯＰＤ３のフラグにはＯＮが格
納され、作業用レジスタのフラグとしてはＯＰＤ３の識
別番号３が格納される。

【００２４】このように、作業用レジスタの要否を左右
するオペランドのフラグをＯＮにし、その作業用レジス
タのフラグとして上記オペランドの識別子を格納するこ
とにより、選択割り付け要求が設定される。これは図２
のステップＳ１２の処理に対応する。

【００２５】図５は、本実施例のコンパイラ装置による
レジスタ割り付け処理のフローチャートである。この処
理もまた、図２の処理と同様に各中間コード毎に行われ
る。図５において処理が開始されると、まずレジスタ割
り付け要求情報を参照しながら、処理対象の中間コード
の各オペランド毎にオペランドレジスタの割り付け処理
を行い（ステップＳ２１）、次のオペランドがある限り
（ステップＳ２２、ＹＥＳ）、これを繰り返す。

【００２６】次のオペランドがなくなれば（ステップＳ
２２、ＮＯ）、レジスタ割り付け要求情報を参照しなが
ら、各作業用レジスタ毎に作業用レジスタの割り付け処
理を行う（ステップＳ２３）。次の作業用レジスタがあ
る限り（ステップＳ２４、ＹＥＳ）、これを繰り返し、
次の作業用レジスタがなくなれば（ステップＳ２４、Ｎ
Ｏ）、処理を終了する。

【００２７】次に図６および図７を参照しながら、図５
のオペランドレジスタ割り付け処理と作業用レジスタ割
り付け処理を詳しく説明する。図６は、本実施例のオペ
ランドレジスタ割り付け処理のフローチャートである。
オペランドレジスタ割り付け処理においては、まずレジ
スタ状態テーブルを参照して、割り付け処理中のオペラ
ンドの値を保持するレジスタが既に存在するかどうかを
調べる（ステップＳ３１）。

【００２８】レジスタ状態テーブルは現在のレジスタの
割り付け状態を保持するテーブルである。例えば、現在
の処理対象となっている中間コードより前に処理された
中間コードのオペランドに対してあるレジスタが割り付
けられている場合は、そのレジスタの状態は使用状態で
あり、その内容は対応するオペランドの内容であること
がレジスタ状態テーブルに記されている。したがって、
レジスタ状態テーブルを参照することにより、割り付け
処理中のオペランドが既にレジスタ上に存在するか否か
がわかる。

【００２９】そのオペランドの値を保持するレジスタが
存在しているときは、そのレジスタを割り付け処理中の
オペランドに割り付け（ステップＳ３２）、レジスタ割
り付け要求情報においてそのオペランドに選択割り付け
要求が設定されているかどうかを調べる（ステップＳ３
３）。存在しないときは、直ちにステップＳ３３の処理
を行う。

【００３０】割り付け処理中のオペランドに選択割り付
け要求が設定されているときは、そのオペランド（選択
割り付け対象オペランド）の処理結果の情報を作成して
（ステップＳ３４）、処理を終了し、選択割り付け要求
が設定されていないときは、そのまま処理を終了する。
選択割り付け対象オペランドの処理結果の情報は、レジ
スタ状態テーブルに格納してもよい。

【００３１】ステップＳ３１で割り付け処理中のオペラ
ンドの値を保持するレジスタが存在せず、レジスタが割
り付かなかったときは、ステップＳ３４でそのオペラン
ドがレジスタに乗らなかったことにより必要となる作業
用レジスタの割り付けを必ず行う旨の情報を作成する。

【００３２】また、ステップＳ３１で割り付け処理中の
オペランドの値を保持するレジスタが存在し、ステップ
Ｓ３２でレジスタが割り付いたときは、ステップＳ３４
でそのオペランドがレジスタに乗ったことにより不必要
となる作業用レジスタの割り付けを行わない旨の情報を
作成する。

【００３３】例えば、図４のレジスタ割り付け要求情報
の場合は、ＯＰＤ３に選択割り付け要求が設定されてい
るので、ＯＰＤ３の処理においてステップＳ３４の処理
が行われ、作成された情報が次の作業用レジスタ割り付
け処理に渡される。

【００３４】図７は、本実施例の作業用レジスタ割り付
け処理のフローチャートである。作業用レジスタ割り付
け処理では、まずレジスタ割り付け要求情報において、
割り付け処理中の作業用レジスタに選択割り付け要求が
設定されているかどうかを調べる（ステップＳ４１）。

【００３５】選択割り付け要求が設定されている場合
は、次に、オペランドレジスタ割り付け処理で作成され
た対応する選択割り付け対象オペランドの処理結果を参
照して、その選択割り付け対象オペランドにレジスタが
割り付いているかどうかを調べる（ステップＳ４２）。

【００３６】選択割り付け対象オペランドにレジスタが
割り付いておらず、割り付け処理中の作業用レジスタが
必要になった旨を伝えられた場合は（ステップＳ４２、
ＮＯ）、その作業用レジスタにレジスタを割り付け（ス
テップＳ４３）、処理を終了する。

【００３７】選択割り付け対象オペランドにレジスタが
割り付いており、割り付け処理中の作業用レジスタが不
要になった旨を伝えられた場合は（ステップＳ４２、Ｙ
ＥＳ）、その作業用レジスタにはレジスタを割り付けず
に処理を終了する。

【００３８】ステップＳ４１で選択割り付け要求が設定
されていない場合は、選択割り付け要求以外に対するレ
ジスタ割り付け処理を続行する（ステップＳ４４）。選
択割り付け以外の作業用レジスタ割り付け要求は、例え
ば、オペランドにレジスタが割り付いたか否かに依らず
無条件にその作業用レジスタを確保したいときに設定さ
れる。この場合、オペランドの処理結果を参照すること
なしに、その作業用レジスタにレジスタを割り付ける。

【００３９】例えば、図４のレジスタ割り付け要求情報
の場合は、作業用レジスタのフラグに選択割り付け対象
オペランドＯＰＤ３の識別番号３が設定されているの
で、この作業用レジスタに対して選択割り付けの処理が
行われる（ステップＳ４１、ＹＥＳ）。ここで、ＯＰＤ
３の処理結果を参照して（ステップＳ４２）、ＯＰＤ３
にレジスタが割り付けられていればその作業用レジスタ
にレジスタを割り付けず、ＯＰＤ３にレジスタが割り付
けられていなければ、その作業用レジスタにレジスタを
割り付ける（ステップＳ４３）。

【００４０】図４において、作業用レジスタのフラグに
いずれのオペランドの識別番号も格納されておらず、フ
ラグがＯＦＦとなっている場合は、選択割り付け要求が
設定されていないので、例えば無条件にその作業用レジ
スタにレジスタを割り付ける（ステップＳ４４）。

【００４１】このように、レジスタ割り付け要求情報に
特別な情報フラグを設けて選択割り付け要求を設定する
ことにより、選択割り付け要求に係るオペランドと作業
用レジスタのどちらか一方のみにレジスタを割り付ける
ことができる。

【００４２】尚、図４にはレジスタ割り付け要求情報の
一例を示したが、本発明はこれに限られることはなく、
他の構成のレジスタ割り付け要求情報を用いてもよい。
例えば、作業用レジスタのフラグを２つ用意し、１つは
選択割り付け要求が設定されているか否かを表し、もう
１つが対応する選択割り付け対象オペランドの識別番号
を格納するように構成することもできる。

【００４３】

【発明の効果】本発明によれば、コンパイラによる中間
コードのレジスタ割り付け処理において、オペランドと
作業用レジスタのどちらか一方のみに選択的にレジスタ
を割り付けることが可能になる。これにより、割り付け
る作業用レジスタの個数を調整できる。不必要な作業用
レジスタの割り付け処理を省くことによって、目的プロ
グラムのサイズが小さくなり、その実行速度が向上す
る。

【図面の簡単な説明】

【図１】本発明の原理図である。

【図２】本発明の実施例のレジスタ割り付け要求情報作
成処理のフローチャートである。

【図３】コンパイルの一例を示す図である。

【図４】実施例におけるレジスタ割り付け要求情報の一
例を示す図である。

【図５】実施例のレジスタ割り付け処理のフローチャー
トである。

【図６】オペランドレジスタ割り付け処理のフローチャ
ートである。

【図７】作業用レジスタ割り付け処理のフローチャート
である。

【符号の説明】

ＯＰＤ１、ＯＰＤ２、ＯＰＤ３ オペランド

Claims (9)

【特許請求の範囲】
1. 【請求項１】 与えられたソースプログラムを中間コー
   ドに変換し、該中間コードから目的プログラムを生成す
   る過程において、該中間コードにレジスタを割り付ける
   方法であって、 前記中間コードのオペランドと該オペランドに対応する
   作業用レジスタのうちの一方にレジスタを割り付ける選
   択割り付け要求を前記中間コードのレジスタ情報に設定
   し、 前記オペランドにレジスタを割り付けるための処理を行
   い、 前記オペランドにレジスタが割り付けられたかどうかを
   調べ、 前記オペランドにレジスタが割り付けられていれば、前
   記作業用レジスタにレジスタを割り付けないことを特徴
   とするレジスタ割り付け方法。
2. 【請求項２】 前記オペランドにレジスタが割り付けら
   れていなければ、前記作業用レジスタにレジスタを割り
   付けることを特徴とする請求項１記載のレジスタ割り付
   け方法。
3. 【請求項３】 前記選択割り付け要求を設定する処理に
   おいて、 前記レジスタ情報内の前記オペランドに対応する位置に
   選択割り付け要求を表す第１のフラグを格納し、 前記レジスタ情報内の前記作業用レジスタに対応する位
   置に選択割り付け要求を表す第２のフラグを格納するこ
   とを特徴とする請求項１または２記載のレジスタ割り付
   け方法。
4. 【請求項４】 前記第２のフラグとして、前記オペラン
   ドの識別子を格納することを特徴とする請求項３記載の
   レジスタ割り付け方法。
5. 【請求項５】 前記レジスタ割り付け処理の結果を表す
   情報を参照して、前記オペランドにレジスタが割り付け
   られたかどうかを調べることを特徴とする請求項１また
   は２記載のレジスタ割り付け方法。
6. 【請求項６】 前記オペランドにレジスタを割り付ける
   ための処理において、 前記レジスタ情報を参照して、前記オペランドに前記選
   択割り付け要求が設定されているかどうかを調べ、 前記選択割り付け要求が設定されていれば、前記オペラ
   ンドに対するレジスタ割り付け処理の結果を表す情報を
   生成することを特徴とする請求項１記載のレジスタ割り
   付け方法。
7. 【請求項７】 与えられたソースプログラムを中間コー
   ドに変換し、該中間コードから目的プログラムを生成す
   る過程において、該中間コードにレジスタを割り付ける
   方法であって、 前記中間コードに対する選択割り付け要求を該中間コー
   ドのレジスタ情報に設定し、 前記オペランドの状態に応じて、該オペランドと前記作
   業用レジスタのうちの一方にレジスタを割り付けること
   を特徴とするレジスタ割り付け方法。
8. 【請求項８】 与えられたソースプログラムを中間コー
   ドに変換し、該中間コードから目的プログラムを生成す
   る過程において、該中間コードにレジスタを割り付ける
   方法であって、 オペランドがレジスタに乗るか否かによって、一時的に
   使用するレジスタの割り付け数を変動させることを特徴
   とするレジスタ割り付け処理方法。
9. 【請求項９】 与えられたソースプログラムを中間コー
   ドに変換し、該中間コードから目的プログラムを生成す
   る装置において、 前記中間コードに対する選択割り付け要求を該中間コー
   ドのレジスタ情報に設定する手段と、 前記オペランドの状態に応じて、該オペランドと前記作
   業用レジスタのうちの一方にレジスタを割り付ける手段
   とを備えることを特徴とするコンパイラ装置。