JPH04178738A - レジスタアロケーション方式 - Google Patents
レジスタアロケーション方式Info
- Publication number
- JPH04178738A JPH04178738A JP30679790A JP30679790A JPH04178738A JP H04178738 A JPH04178738 A JP H04178738A JP 30679790 A JP30679790 A JP 30679790A JP 30679790 A JP30679790 A JP 30679790A JP H04178738 A JPH04178738 A JP H04178738A
- Authority
- JP
- Japan
- Prior art keywords
- register
- pointer
- registers
- general
- variable
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
［発明の目的］
（産業上の利用分野）
本発明は、電子計算機の高級プログラム言語に対する翻
訳の際のレジスタアロケーション方式（従来の技術） 電子計算機の高級プログラム言語によるソースプログラ
ムを機械語に翻訳する際、プログラムの各変数を、その
マシンのどのレジスタに割り当てるか決定することをレ
ジスタアロケーションと呼ぶ。レジスタアロケーション
は、オブジェクト（翻訳された機械語の列）の実行性能
に少なからず影響を与えるため、多くのアルゴリズムが
考案されている。
訳の際のレジスタアロケーション方式（従来の技術） 電子計算機の高級プログラム言語によるソースプログラ
ムを機械語に翻訳する際、プログラムの各変数を、その
マシンのどのレジスタに割り当てるか決定することをレ
ジスタアロケーションと呼ぶ。レジスタアロケーション
は、オブジェクト（翻訳された機械語の列）の実行性能
に少なからず影響を与えるため、多くのアルゴリズムが
考案されている。
レジスタの種類が（浮動少数点レジスタ等の特殊なもの
を除いて）汎用レジスタのみからなるプロセッサを対象
としたレジスタアロケーションは、どの変数をどのレジ
スタにアロケートするか決定することである。
を除いて）汎用レジスタのみからなるプロセッサを対象
としたレジスタアロケーションは、どの変数をどのレジ
スタにアロケートするか決定することである。
これに対して、汎用レジスタ以外にアドレスを格納する
アドレスレジスタ等の複数種類のレジスタをもつマシン
に対しては、各変数にどの種類のレジスタを割り当てる
かという決定問題が生じる。
アドレスレジスタ等の複数種類のレジスタをもつマシン
に対しては、各変数にどの種類のレジスタを割り当てる
かという決定問題が生じる。
さて、多くの高級プログラミング言語では、ポインタ型
と呼ばれるデータ型がある。ポインタ型では、変数をプ
ログラマによって定義することができる。また、ポイン
タ型は、メモリ参照するためのアドレス形式をとる。こ
のようなポインタ型のデータ型の場合、ポインタに対し
て常に汎用レジスタ、またはアドレスレジスタの何れか
をアロケートしている。
と呼ばれるデータ型がある。ポインタ型では、変数をプ
ログラマによって定義することができる。また、ポイン
タ型は、メモリ参照するためのアドレス形式をとる。こ
のようなポインタ型のデータ型の場合、ポインタに対し
て常に汎用レジスタ、またはアドレスレジスタの何れか
をアロケートしている。
（発明が解決しようとする課題）
このように、従来では、汎用レジスタとアドレスレジス
タというレジスタクラスのあるプロセッサに対して、汎
用レジスタ、またはアドレスレジスタの何れかをアロケ
ートしていた。このため、ポインタに対して汎用レジス
ータをアロケートする場合、ポインタを介してメモリを
参照する際に、汎用レジスタの内容をその都度アドレス
レジスタにコピーしなければならなくなる。また、ポイ
ンタに対してアドレスレジスタをアロケートする場合、
ポインタに対する（加減等の）算術演算を行なう際に、
アドレスレジスタの内容を汎用レジスタにコピーしなけ
ればならなくなる。したがって、ポインタ変数に関する
オブジェクトコードの命令数が多くなり、実行効率を低
下させていた。
タというレジスタクラスのあるプロセッサに対して、汎
用レジスタ、またはアドレスレジスタの何れかをアロケ
ートしていた。このため、ポインタに対して汎用レジス
ータをアロケートする場合、ポインタを介してメモリを
参照する際に、汎用レジスタの内容をその都度アドレス
レジスタにコピーしなければならなくなる。また、ポイ
ンタに対してアドレスレジスタをアロケートする場合、
ポインタに対する（加減等の）算術演算を行なう際に、
アドレスレジスタの内容を汎用レジスタにコピーしなけ
ればならなくなる。したがって、ポインタ変数に関する
オブジェクトコードの命令数が多くなり、実行効率を低
下させていた。
本発明は前記のような点に鑑みてなされたもので、汎用
レジスタ及びアドレスレジスタの両方を備えたプロセッ
サにおいて、オブジェクトコートの命令数を少なくする
ことか可能なレジスタアロケーション方式を提供するこ
とを目的とする。
レジスタ及びアドレスレジスタの両方を備えたプロセッ
サにおいて、オブジェクトコートの命令数を少なくする
ことか可能なレジスタアロケーション方式を提供するこ
とを目的とする。
［発明の構成コ
（課題を解決するための手段）
本発明は、算術演算可能な第１レジスタ及び算術演算で
きない第２レジスタを有するプロセッサに対し、データ
型としてポインタ型を有するプログラム言語によるソー
スプログラムのポインタ変数ヲ、ソースプログラムの内
容に基づいて前記第１レジスタ、または第２レジスタの
何れかに割り当てることを特徴とする。
きない第２レジスタを有するプロセッサに対し、データ
型としてポインタ型を有するプログラム言語によるソー
スプログラムのポインタ変数ヲ、ソースプログラムの内
容に基づいて前記第１レジスタ、または第２レジスタの
何れかに割り当てることを特徴とする。
（作 用）
このような方式によれば、ポインタ変数を割り当てるレ
ジスタを、ソースプログラムの内容（ポインタ変数の生
存区間内の内容）に基づいて、第１レジスタ（汎用レジ
スタ）または第２レジスタ（アドレスレジスタ）の何れ
か好適な方を選択することができるので、非効率な命令
か省かれてオブジェクトプログラムの命令数を少なくす
ることができる。
ジスタを、ソースプログラムの内容（ポインタ変数の生
存区間内の内容）に基づいて、第１レジスタ（汎用レジ
スタ）または第２レジスタ（アドレスレジスタ）の何れ
か好適な方を選択することができるので、非効率な命令
か省かれてオブジェクトプログラムの命令数を少なくす
ることができる。
（実施例）
以下、図面を参照して本発明の一実施例を説明する。第
２図は同実施例に係わるレジスタアロケーション方式を
適用するシステムの構成を示すブロック図である。第２
図において、１０はプロセッサであり、ソースプログラ
ムを機械語に翻訳するコンパイラ１２を実行する。ソー
スプログラムファイル１４は、コンパイラ１２の翻訳対
象とするソースプログラムを格納するものである。オブ
ジェクトプログラムファイル１６は、コンパイラ１２に
よる翻訳結果の出力となる機械語の列を含むオブジェク
トプログラムを格納するものである。プロセッサ１８は
、コンパイラ１２が出力する機械語（オブジェクトプロ
グラム）を実行するものである。なお、プロセッサ１０
とプロセッサ１８は、別々ではなく一つのプロセッサと
しても良い。このプロセッサには、汎用レジスタ及びア
ドレスレジスタの両方が設けられているものとする。
２図は同実施例に係わるレジスタアロケーション方式を
適用するシステムの構成を示すブロック図である。第２
図において、１０はプロセッサであり、ソースプログラ
ムを機械語に翻訳するコンパイラ１２を実行する。ソー
スプログラムファイル１４は、コンパイラ１２の翻訳対
象とするソースプログラムを格納するものである。オブ
ジェクトプログラムファイル１６は、コンパイラ１２に
よる翻訳結果の出力となる機械語の列を含むオブジェク
トプログラムを格納するものである。プロセッサ１８は
、コンパイラ１２が出力する機械語（オブジェクトプロ
グラム）を実行するものである。なお、プロセッサ１０
とプロセッサ１８は、別々ではなく一つのプロセッサと
しても良い。このプロセッサには、汎用レジスタ及びア
ドレスレジスタの両方が設けられているものとする。
次に、同実施例の動作について説明する。プログラマに
よって書かれたプログラム（ソースプログラム１４）は
、プロセッサ１０上で動くコンノくイラ１２により、プ
ロセッサ１８によって実行される機械語列に翻訳され、
オブジェクトプログラム１６となる。オブジェクトプロ
グラムファイル１６は、プロセッサ１８にロードされ実
行される。
よって書かれたプログラム（ソースプログラム１４）は
、プロセッサ１０上で動くコンノくイラ１２により、プ
ロセッサ１８によって実行される機械語列に翻訳され、
オブジェクトプログラム１６となる。オブジェクトプロ
グラムファイル１６は、プロセッサ１８にロードされ実
行される。
次に、本発明の中心であるレジスタアロケーション部、
すなわちコンパイラ１２の動作の内容について、第１図
にフローチャートを参照しながら説明する。
すなわちコンパイラ１２の動作の内容について、第１図
にフローチャートを参照しながら説明する。
まず、プログラマによって書かれたソースプログラム中
の変数が、ポインタ型でない場合には、汎用レジスタを
選択するものとする（ステップＳｌ、Ｓ２）。
の変数が、ポインタ型でない場合には、汎用レジスタを
選択するものとする（ステップＳｌ、Ｓ２）。
一方、変数がポインタ型の場合には、レジスタアロケー
ションを次のようにする。
ションを次のようにする。
すなわち、アロケーションの対象となるプログラム範囲
（ポインタ変数の生存区間）内で、ポインタに対する算
術演算が“重い“ （処理速度が遅くなる状態）と判断
されるときは、汎用レジスタからレジスタを選択する。
（ポインタ変数の生存区間）内で、ポインタに対する算
術演算が“重い“ （処理速度が遅くなる状態）と判断
されるときは、汎用レジスタからレジスタを選択する。
そうでなければ、アドレスレジスタからレジスタを選択
する。“重い”か否かの判断は、ポインタ変数に対する
演算の回数をα、ポインタによるメモリ参照の回数をβ
として評価関数ｆ（α、β）の値に基づいて行なう（ス
テップＳ３）。つまり、 ｆ （α、β）〉０ であれば汎用レジスタを選択しくステップＳ４）、ｆ（
α１ β）≦Ｏ であればアドレスレジスタを選択するものとする（ステ
ップＳ５）。
する。“重い”か否かの判断は、ポインタ変数に対する
演算の回数をα、ポインタによるメモリ参照の回数をβ
として評価関数ｆ（α、β）の値に基づいて行なう（ス
テップＳ３）。つまり、 ｆ （α、β）〉０ であれば汎用レジスタを選択しくステップＳ４）、ｆ（
α１ β）≦Ｏ であればアドレスレジスタを選択するものとする（ステ
ップＳ５）。
評価関数ｆは、例えばＣをプロセッサに応じて決定され
る定数とすると、 ｆ （α、β）−α−Ｃ＊β （＊は乗算を示す）とし
て表される。定数Ｃの値は、算術演算と比較してプロセ
ッサのポインタ処理の負担が重いときは大きい値をとる
ようにする。通常では、ｃ−０として、評価関数を ｆ（α、β）−α とすることもてきる。この場合、ポインタに対する算術
演算が一度でもあれば汎用レジスタを選択し、そうでな
ければアドレスレジスタを選択することになる。
る定数とすると、 ｆ （α、β）−α−Ｃ＊β （＊は乗算を示す）とし
て表される。定数Ｃの値は、算術演算と比較してプロセ
ッサのポインタ処理の負担が重いときは大きい値をとる
ようにする。通常では、ｃ−０として、評価関数を ｆ（α、β）−α とすることもてきる。この場合、ポインタに対する算術
演算が一度でもあれば汎用レジスタを選択し、そうでな
ければアドレスレジスタを選択することになる。
こうして、汎用レジスタとアドレスレジスタの何れを選
択するか決定された後は（ステップＳ２゜Ｓ４．Ｓ５）
、公知の方法によりレジスタアロケーションを行なう（
ステップＳ６）。
択するか決定された後は（ステップＳ２゜Ｓ４．Ｓ５）
、公知の方法によりレジスタアロケーションを行なう（
ステップＳ６）。
次に、具体的な例を用いて説明する。
以下、第３図に示すＣ言語プログラムを用いて説明する
。なお、説明を簡単にするために、浮動小数点や浮動小
数点レジスタ等については考えないものとする。
。なお、説明を簡単にするために、浮動小数点や浮動小
数点レジスタ等については考えないものとする。
また、オブジェクトプログラムを実行するプロセッサの
モデルを次のように仮定する。プロセッサのレジスタと
しては、汎用レジスタ（ｇｏ）（ｇｌ）、アドレスレジ
スタ（ａ Ｏ） （ａ １）が設けられているものと
し、各レジスタ間のデータ転送はどの組み合わせでも可
能とする。
モデルを次のように仮定する。プロセッサのレジスタと
しては、汎用レジスタ（ｇｏ）（ｇｌ）、アドレスレジ
スタ（ａ Ｏ） （ａ １）が設けられているものと
し、各レジスタ間のデータ転送はどの組み合わせでも可
能とする。
さらに、プロセッサの命令として、次のものを仮定する
。
。
“１ｏａｄ 汎用レジスタ、即値°・・・汎用レジス
タに即値を入れる。
タに即値を入れる。
“５ｔｏｒｅ汎用レジスタ、 （アドレスレジスタ）１
・・・レジスタの値をアドレスレジスタで示されるメモ
リに格納する。
・・・レジスタの値をアドレスレジスタで示されるメモ
リに格納する。
“■ｏｖｅ レジスタ、レジスタ“・・・レジスタ間
のデータ転送を行なう。
のデータ転送を行なう。
“ａｄｄ 汎用レジスタ、即値゛・・・汎用レジスタ
に即値を加える。
に即値を加える。
各命令のコスト（実行にかかる時間）は、同じと仮定す
る。以下、記法（ＶＡＲｒｅｇ）は、変数ＶＡＩ？をｒ
ｅｇにアロケートすることを示す。
る。以下、記法（ＶＡＲｒｅｇ）は、変数ＶＡＩ？をｒ
ｅｇにアロケートすることを示す。
第３図に示すプログラム例では、ポインタに対する算術
演算がないため、ポインタ変数にアドレスレジスタをア
ロケートする方が、汎用レジスタをアロケートするより
命令数を少なくすることができる。汎用レジスタをアロ
ケートした場合の翻訳結果を第４図に示し、アドレスレ
ジスタをアロケートした場合の翻訳結果を第５図に示し
ている。
演算がないため、ポインタ変数にアドレスレジスタをア
ロケートする方が、汎用レジスタをアロケートするより
命令数を少なくすることができる。汎用レジスタをアロ
ケートした場合の翻訳結果を第４図に示し、アドレスレ
ジスタをアロケートした場合の翻訳結果を第５図に示し
ている。
第４図及び第５図から分かるように、アドレスレジスタ
をアロケートした場合の方が命令数が少なくなっている
。
をアロケートした場合の方が命令数が少なくなっている
。
次に、第６図に示すプログラム例では、ポインタに対す
る算術演算があるため、ポインタ変数に汎用レジスタを
アロケートする方が、アドレスレジスタをアロケートす
るより命令数を少なくすることができる。汎用レジスタ
をアロケートした場合の翻訳結果を第７図に示し、アド
レスレジスタをアロケートした場合の翻訳結果を第８図
に示している。第７図及び第８図から分かるように、ア
ドレスレジスタをアロケートした場合の方が命令数が少
なくなっている。
る算術演算があるため、ポインタ変数に汎用レジスタを
アロケートする方が、アドレスレジスタをアロケートす
るより命令数を少なくすることができる。汎用レジスタ
をアロケートした場合の翻訳結果を第７図に示し、アド
レスレジスタをアロケートした場合の翻訳結果を第８図
に示している。第７図及び第８図から分かるように、ア
ドレスレジスタをアロケートした場合の方が命令数が少
なくなっている。
このようにして、汎用レジスタ、アドレスレジスタの両
方を備えたプロセッサに対して、ソースプログラムの変
数がデータ型である場合に、何れか適したレジスタを選
択するので、ポインタ変数に関するオブジェクトコード
の命令数を不必要に多くなることを防ぐことができる。
方を備えたプロセッサに対して、ソースプログラムの変
数がデータ型である場合に、何れか適したレジスタを選
択するので、ポインタ変数に関するオブジェクトコード
の命令数を不必要に多くなることを防ぐことができる。
なお、前記実施例においては、Ｃ言語によるプログラム
を用いて具体例について説明したが、他の言語において
もポインタ変数に相当するものかあれば、本発明を適用
することができる。
を用いて具体例について説明したが、他の言語において
もポインタ変数に相当するものかあれば、本発明を適用
することができる。
［発明の効果コ
以上のように本発明によれば、汎用レジスタ及びアドレ
スレジスタの両方を備えたプロセッサに対して、ソース
プログラム中のポインタ変数の生存区間内の内容に応じ
て、汎用レジスタ、アドレスレジスタの何れか好適な方
が選択されるので、結果的にオブジェクトコードの命令
数を少なくすることかでき、実行効率を向上させること
が可能となるものである。
スレジスタの両方を備えたプロセッサに対して、ソース
プログラム中のポインタ変数の生存区間内の内容に応じ
て、汎用レジスタ、アドレスレジスタの何れか好適な方
が選択されるので、結果的にオブジェクトコードの命令
数を少なくすることかでき、実行効率を向上させること
が可能となるものである。
第１図は本発明の一実施例に係わるレジスタアロケーシ
ョン方式の動作を示すフローチャート、第２図は同実施
例におけるレジスタアロケーション方式を適用するシス
テムの構成を示すブロック図、第３図及び第６図は処理
対象とするソースプログラム例を示す図、第４図及び第
５図は第３図に示すソースプログラムに対応するオブジ
ェクトプログラム例を示す図、第７図及び第８図はＭ６
図に示すソースプログラムに対応するオブジェクトプロ
グラム例を示す図である。 １０．１８・・・プロセッサ、１２・・・コンパイラ、
１４・・ソースプログラムファイル、１６・・・オブジ
ェクトプログラムファイル。 出願人代理人 弁理士 鈴江武彦 第１図 第２１！！
ョン方式の動作を示すフローチャート、第２図は同実施
例におけるレジスタアロケーション方式を適用するシス
テムの構成を示すブロック図、第３図及び第６図は処理
対象とするソースプログラム例を示す図、第４図及び第
５図は第３図に示すソースプログラムに対応するオブジ
ェクトプログラム例を示す図、第７図及び第８図はＭ６
図に示すソースプログラムに対応するオブジェクトプロ
グラム例を示す図である。 １０．１８・・・プロセッサ、１２・・・コンパイラ、
１４・・ソースプログラムファイル、１６・・・オブジ
ェクトプログラムファイル。 出願人代理人 弁理士 鈴江武彦 第１図 第２１！！
Claims (1)
- 算術演算可能な第１レジスタ及び算術演算できない第
２レジスタを有するプロセッサに対し、データ型として
ポインタ型を有するプログラム言語によるソースプログ
ラムのポインタ変数を、ソースプログラムの内容に基づ
いて前記第１レジスタ、または第２レジスタの何れかに
割り当てることを特徴とするレジスタアロケーション方
式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP30679790A JPH04178738A (ja) | 1990-11-13 | 1990-11-13 | レジスタアロケーション方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP30679790A JPH04178738A (ja) | 1990-11-13 | 1990-11-13 | レジスタアロケーション方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH04178738A true JPH04178738A (ja) | 1992-06-25 |
Family
ID=17961370
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP30679790A Pending JPH04178738A (ja) | 1990-11-13 | 1990-11-13 | レジスタアロケーション方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH04178738A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US11202723B2 (en) | 2016-07-01 | 2021-12-21 | The Procter & Gamble Company | Absorbent articles with improved topsheet dryness |
-
1990
- 1990-11-13 JP JP30679790A patent/JPH04178738A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US11202723B2 (en) | 2016-07-01 | 2021-12-21 | The Procter & Gamble Company | Absorbent articles with improved topsheet dryness |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5367703A (en) | Method and system for enhanced branch history prediction accuracy in a superscalar processor system | |
| EP0855058B1 (en) | Programmable branch prediction system and method for computer systems | |
| US5504901A (en) | Position independent code location system | |
| US6161217A (en) | Accurate method for inlining virtual calls | |
| US4843545A (en) | Compile method using copy propagation of a variable | |
| JP2000347876A (ja) | スタック・スロット割当て方法および装置 | |
| US5978905A (en) | Program translating apparatus and a processor which achieve high-speed execution of subroutine branch instructions | |
| US7032230B2 (en) | Efficient virtual function calls for compiled/interpreted environments | |
| US20030079210A1 (en) | Integrated register allocator in a compiler | |
| Lang et al. | Reduced register saving/restoring in single-window register files | |
| US10496433B2 (en) | Modification of context saving functions | |
| US5930495A (en) | Method and system for processing a first instruction in a first processing environment in response to intiating processing of a second instruction in a emulation environment | |
| JPH04178738A (ja) | レジスタアロケーション方式 | |
| JP2620505B2 (ja) | スーパースカラ・プロセッサ・システムの同期化効率を向上させる方法およびシステム | |
| US7231509B2 (en) | Extended register bank allocation based on status mask bits set by allocation instruction for respective code block | |
| Sugino et al. | Improved code optimization method utilizing memory addressing operation and its application to DSP compiler | |
| JPH0666052B2 (ja) | メモリ内容を機械レジスタに自動的に写像する計算機 | |
| CA2018182C (en) | Data processor for high-speed access to stack area data | |
| JP2722493B2 (ja) | レジスタ割り付け処理方法 | |
| Kowaltowski | Parameter passing mechanisms and run time data structures | |
| JPH07129408A (ja) | 言語処理プログラムの実行方式 | |
| JPH11212789A (ja) | プログラム翻訳装置、プロセッサ及びプログラム翻訳装置に適用されるプログラムを記録した記録媒体 | |
| HK40065117A (en) | A streaming compiler for automatic adjoint differentiation | |
| JPH09231135A (ja) | アドレシング装置 | |
| KR19990026795A (ko) | 마이크로프로세서 |