JPH04344536A - レジスタ割当て方式 - Google Patents
レジスタ割当て方式Info
- Publication number
- JPH04344536A JPH04344536A JP14413491A JP14413491A JPH04344536A JP H04344536 A JPH04344536 A JP H04344536A JP 14413491 A JP14413491 A JP 14413491A JP 14413491 A JP14413491 A JP 14413491A JP H04344536 A JPH04344536 A JP H04344536A
- Authority
- JP
- Japan
- Prior art keywords
- procedure
- register
- register allocation
- program
- call
- 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
- 238000000034 method Methods 0.000 claims abstract description 114
- 238000010586 diagram Methods 0.000 description 8
- 101100301524 Drosophila melanogaster Reg-5 gene Proteins 0.000 description 2
- 102100023882 Endoribonuclease ZC3H12A Human genes 0.000 description 2
- 101710112715 Endoribonuclease ZC3H12A Proteins 0.000 description 2
- 101100412401 Rattus norvegicus Reg3a gene Proteins 0.000 description 1
- 238000005457 optimization Methods 0.000 description 1
Landscapes
- Devices For Executing Special Programs (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【０００１】
【産業上の利用分野】本発明は、コンパイラの目的プロ
グラム生成方式に関し、特に手続きの呼び出し関係を考
慮したレジスタ割当て方式に関する。
グラム生成方式に関し、特に手続きの呼び出し関係を考
慮したレジスタ割当て方式に関する。
【０００２】
【従来の技術】従来、コンパイラのレジスタ割当てにお
いては、コンパイル単位、例えばサブルーチンや関数と
いった手続き単位では目的プログラムの最適化の一環と
してレジスタ割当ての最適化も行なわれている。
いては、コンパイル単位、例えばサブルーチンや関数と
いった手続き単位では目的プログラムの最適化の一環と
してレジスタ割当ての最適化も行なわれている。
【０００３】
【発明が解決しようとする課題】上述した従来のレジス
タ割当ては、処理中の手続きから呼び出される他の手続
きにおけるレジスタ割当て状況を考慮しないため、呼び
出しの前後にて定義／参照されるレジスタの内容を保証
するために、手続きの呼び出し前にそのレジスタ内容を
退避しておき呼び出し後にその内容を復元するか、手続
きの入口において所定のレジスタを退避し、出口におい
て復元するといったような命令列を生成しているので、
レジスタの不要な退避／復元が発生するという問題や、
必要なレジスタ数が少ない場合でも他の手続きのレジス
タ割当て状況が不明のため必ず使用するレジスタの退避
／復元が必要となるという課題があった。
タ割当ては、処理中の手続きから呼び出される他の手続
きにおけるレジスタ割当て状況を考慮しないため、呼び
出しの前後にて定義／参照されるレジスタの内容を保証
するために、手続きの呼び出し前にそのレジスタ内容を
退避しておき呼び出し後にその内容を復元するか、手続
きの入口において所定のレジスタを退避し、出口におい
て復元するといったような命令列を生成しているので、
レジスタの不要な退避／復元が発生するという問題や、
必要なレジスタ数が少ない場合でも他の手続きのレジス
タ割当て状況が不明のため必ず使用するレジスタの退避
／復元が必要となるという課題があった。
【０００４】本発明は上述の課題を解決したもので、そ
の目的は、手続き呼び出しに伴なう不要なレジスタの退
避／復元を削減することができるレジスタ割当て方式を
提供することにある。
の目的は、手続き呼び出しに伴なう不要なレジスタの退
避／復元を削減することができるレジスタ割当て方式を
提供することにある。
【０００５】
【課題を解決するための手段】本発明のレジスタ割当て
方式は、上記目的を達成するために、ソースプログラム
を翻訳して目的プログラムを生成するコンパイラにおい
て、ソースプログラムを解析して手続き呼び出しの関係
を調べ、他の手続きを呼び出していない手続きを１番目
、この１番目の手続きを呼び出している手続きを２番目
、この２番目の手続きを呼び出している手続きを３番目
といったような順序を付け、その順序を格納したコンパ
イル順序表を生成するプログラム構造解析手段と、該コ
ンパイル順序表に従ってソースプログラム中の手続きを
順番に読み込む手続き読み込み手段と、読み込まれた手
続きを解析して中間テキストを生成する構文解析手段と
、前記中間テキストを入力してレジスタを割当てる際に
、処理中の手続きが他の手続きを呼び出していない場合
には通常のレジスタ割当てを行ない、その割当て状況を
レジスタ割当て状況表に格納し、また、処理中の手続き
が他の手続きを呼び出している場合にはレジスタ割当て
状況表を参照し、呼び出している手続きで使用している
レジスタをその呼び出しの前後にまたがって使用しない
ようにレジスタを割当て、その状況をレジスタ割当て状
況表に格納するレジスタ割当て手段と、前記中間テキス
トから目的プログラムを生成する目的プログラム生成手
段とを有している。
方式は、上記目的を達成するために、ソースプログラム
を翻訳して目的プログラムを生成するコンパイラにおい
て、ソースプログラムを解析して手続き呼び出しの関係
を調べ、他の手続きを呼び出していない手続きを１番目
、この１番目の手続きを呼び出している手続きを２番目
、この２番目の手続きを呼び出している手続きを３番目
といったような順序を付け、その順序を格納したコンパ
イル順序表を生成するプログラム構造解析手段と、該コ
ンパイル順序表に従ってソースプログラム中の手続きを
順番に読み込む手続き読み込み手段と、読み込まれた手
続きを解析して中間テキストを生成する構文解析手段と
、前記中間テキストを入力してレジスタを割当てる際に
、処理中の手続きが他の手続きを呼び出していない場合
には通常のレジスタ割当てを行ない、その割当て状況を
レジスタ割当て状況表に格納し、また、処理中の手続き
が他の手続きを呼び出している場合にはレジスタ割当て
状況表を参照し、呼び出している手続きで使用している
レジスタをその呼び出しの前後にまたがって使用しない
ようにレジスタを割当て、その状況をレジスタ割当て状
況表に格納するレジスタ割当て手段と、前記中間テキス
トから目的プログラムを生成する目的プログラム生成手
段とを有している。
【０００６】
【作用】本発明のレジスタ割当て方式においては、プロ
グラム構造解析手段がソースプログラムを解析して手続
き呼び出しの関係を調べてその手続き呼び出し順序に応
じたコンパイル順序表を生成し、手続き読み込み手段は
生成されたコンパイル順序表に従って手続きを順番に読
み込み、構文解析手段によって、中間テキストを生成し
たのち、レジスタ割当て手段が生成された中間テキスト
を入力して処理中の手続きが他の手続きを呼び出してい
ない場合は通常のレジスタ割当てを行ない、処理中の手
続きが他の手続きを呼び出している場合はレジスタ割当
て状況表を参照して、呼び出している手続きで使用して
いるレジスタをその呼び出しの前後にまたがって使用し
ないようにレジスタを割当て、どちらの場合もその状況
をレジスタ割当て状況表に格納するので、手続き呼び出
し関係を考慮したレジスタ割当てができる。
グラム構造解析手段がソースプログラムを解析して手続
き呼び出しの関係を調べてその手続き呼び出し順序に応
じたコンパイル順序表を生成し、手続き読み込み手段は
生成されたコンパイル順序表に従って手続きを順番に読
み込み、構文解析手段によって、中間テキストを生成し
たのち、レジスタ割当て手段が生成された中間テキスト
を入力して処理中の手続きが他の手続きを呼び出してい
ない場合は通常のレジスタ割当てを行ない、処理中の手
続きが他の手続きを呼び出している場合はレジスタ割当
て状況表を参照して、呼び出している手続きで使用して
いるレジスタをその呼び出しの前後にまたがって使用し
ないようにレジスタを割当て、どちらの場合もその状況
をレジスタ割当て状況表に格納するので、手続き呼び出
し関係を考慮したレジスタ割当てができる。
【０００７】
【実施例】次に、本発明の一実施例について図面を参照
して説明する。
して説明する。
【０００８】図１は本発明の一実施例であるレジスタ割
当て方式の構成を表わす図である。
当て方式の構成を表わす図である。
【０００９】図１において、コンパイラ２はソースプロ
グラム１を読み込み目的プログラム３を生成する。コン
パイラ２のプログラム構造解析手段２１はソースプログ
ラム１を手続き呼び出し解析部２１１によって解析し、
手続きの呼び出し関係すなわち、どの手続きからどの手
続きを呼び出しているか、あるいはある手続きがどの手
続きから呼び出されているかを決定する。また、その解
析結果をもとに、コンパイル順序決定部２１２によって
他の手続きを呼び出していない手続き（手続き１とする
）を１番目、手続き１を呼び出している手続き（手続き
２とする）を２番目、手続き２を呼び出している手続き
を３番目といったような順序付けを行ない、その順序を
コンパイル順序表２６に格納する。
グラム１を読み込み目的プログラム３を生成する。コン
パイラ２のプログラム構造解析手段２１はソースプログ
ラム１を手続き呼び出し解析部２１１によって解析し、
手続きの呼び出し関係すなわち、どの手続きからどの手
続きを呼び出しているか、あるいはある手続きがどの手
続きから呼び出されているかを決定する。また、その解
析結果をもとに、コンパイル順序決定部２１２によって
他の手続きを呼び出していない手続き（手続き１とする
）を１番目、手続き１を呼び出している手続き（手続き
２とする）を２番目、手続き２を呼び出している手続き
を３番目といったような順序付けを行ない、その順序を
コンパイル順序表２６に格納する。
【００１０】手続き読み込み手段２２は、コンパイル順
序表２６に従ってソースプログラム１中の手続きを読み
込む。構文解析手段２３は読み込まれた手続きを解析し
て中間テキスト２７を生成する。レジスタ割当て手段２
４は、中間テキスト２７を入力してレジスタを割当てる
が、その際に、処理している手続きが他の手続きを呼び
出していない場合には、通常のレジスタ割当てを行ない
、その割当て状況をレジスタ割当て状況表２８に格納す
る。また処理している手続きが他の手続きを呼び出して
いる場合には、レジスタ割当て状況表２８を参照し呼び
出している手続きで使用しているレジスタをその手続き
の呼び出しの前後にまたがって使用しないようにレジス
タを割当て、その割当て状況をレジスタ割当て状況表２
８に格納する。目的プログラム生成手段２５は中間テキ
スト２７を入力して目的プログラム３を生成する。ある
手続きに対する目的プログラム生成が終了した後には再
び手続き読み込み手段２２に戻り翻訳対象がつきるまで
翻訳処理を続ける。
序表２６に従ってソースプログラム１中の手続きを読み
込む。構文解析手段２３は読み込まれた手続きを解析し
て中間テキスト２７を生成する。レジスタ割当て手段２
４は、中間テキスト２７を入力してレジスタを割当てる
が、その際に、処理している手続きが他の手続きを呼び
出していない場合には、通常のレジスタ割当てを行ない
、その割当て状況をレジスタ割当て状況表２８に格納す
る。また処理している手続きが他の手続きを呼び出して
いる場合には、レジスタ割当て状況表２８を参照し呼び
出している手続きで使用しているレジスタをその手続き
の呼び出しの前後にまたがって使用しないようにレジス
タを割当て、その割当て状況をレジスタ割当て状況表２
８に格納する。目的プログラム生成手段２５は中間テキ
スト２７を入力して目的プログラム３を生成する。ある
手続きに対する目的プログラム生成が終了した後には再
び手続き読み込み手段２２に戻り翻訳対象がつきるまで
翻訳処理を続ける。
【００１１】図２は、本発明に適用されるソースプログ
ラムの例を示す図である。図において手続きＡは手続き
Ｂを呼び出すプログラムであり、手続きＢはプログラム
Ａから呼び出されて手続きＣおよびＤを呼び出すサブル
ーチンである、手続きＣはサブルーチン、手続きＤは関
数を表わす。
ラムの例を示す図である。図において手続きＡは手続き
Ｂを呼び出すプログラムであり、手続きＢはプログラム
Ａから呼び出されて手続きＣおよびＤを呼び出すサブル
ーチンである、手続きＣはサブルーチン、手続きＤは関
数を表わす。
【００１２】図３は、本発明のコンパイル順序表の例を
示す図である。
示す図である。
【００１３】図４は、本発明のレジスタ割当て状況表の
例を示す図である。
例を示す図である。
【００１４】次に、本発明の動作を説明する。
【００１５】図２はＦＯＲＴＲＡＮのプログラムの例で
あり、プログラムＡからサブルーチンＢを呼び出し、サ
ブルーチンＢからサブルーチンＣ及び関数Ｄを呼び出し
ている。サブルーチンＢ及び関数Ｄは他のサブルーチン
や関数を呼び出していない。
あり、プログラムＡからサブルーチンＢを呼び出し、サ
ブルーチンＢからサブルーチンＣ及び関数Ｄを呼び出し
ている。サブルーチンＢ及び関数Ｄは他のサブルーチン
や関数を呼び出していない。
【００１６】図１のコンパイラ２のプログラム構造解析
手段２１は図２のＦＯＲＴＲＡＮプログラムを解析し、
図３に示すようなコンパイル順序表２６を作成する。図
３において手続きＣ及びＤは他の手続きを呼び出してい
ないためコンパイル順序が１番となり、手続きＢは手続
きＣやＤを呼び出しているため順序が２番となり、Ｂを
呼び出しているＡが最後のコンパイル順序３番となる。 コンパイラ２の手続き読み込み手段２２は図３のコンパ
イル順序表２６に従いサブルーチンＣをまず読み込む。 構文解析手段２３により中間テキスト２７を生成した後
レジスタ割当て手段２４はレジスタ割当て後例えば図４
のレジスタ割当て状況表２８に示すように手続きＣで使
用したレジスタがＲｅｇ１〜Ｒｅｇ５であったと記憶し
た後、目的プログラム生成手段２５によって目的プログ
ラム３を生成する。
手段２１は図２のＦＯＲＴＲＡＮプログラムを解析し、
図３に示すようなコンパイル順序表２６を作成する。図
３において手続きＣ及びＤは他の手続きを呼び出してい
ないためコンパイル順序が１番となり、手続きＢは手続
きＣやＤを呼び出しているため順序が２番となり、Ｂを
呼び出しているＡが最後のコンパイル順序３番となる。 コンパイラ２の手続き読み込み手段２２は図３のコンパ
イル順序表２６に従いサブルーチンＣをまず読み込む。 構文解析手段２３により中間テキスト２７を生成した後
レジスタ割当て手段２４はレジスタ割当て後例えば図４
のレジスタ割当て状況表２８に示すように手続きＣで使
用したレジスタがＲｅｇ１〜Ｒｅｇ５であったと記憶し
た後、目的プログラム生成手段２５によって目的プログ
ラム３を生成する。
【００１７】次に、手続き読み込み手段２２に戻り、図
３のコンパイル順序表２６により関数Ｄを読み込み同様
の処理を行なう。このときＤにて使用するレジスタはＲ
ｅｇ１〜Ｒｅｇ３とする。
３のコンパイル順序表２６により関数Ｄを読み込み同様
の処理を行なう。このときＤにて使用するレジスタはＲ
ｅｇ１〜Ｒｅｇ３とする。
【００１８】再び手続き読み込み手段２２に戻り、図３
のコンパイル順序表２６によりサブルーチンＢの処理を
行なう。このときレジスタ割当て手段２４において、Ｂ
がＣ及びＤを呼び出しているので図４のレジスタ割当て
状況表２８を参照し、Ｃで使用しているレジスタＲｅｇ
１〜Ｒｅｇ５をＣの呼び出しの前後で定義／参照しない
ように、また、Ｄで使用しているレジスタＲｅｇ１〜Ｒ
ｅｇ３をＤの呼び出しの前後で定義／参照しないように
レジスタを割当てる。レジスタ割当て結果はレジスタ割
当て状況表２８に記録するが、このときＢから呼び出し
ているＣとＤで使用しているレジスタもＢで使用してい
るものとして記録する。以後プログラムＡまで同様に処
理する。
のコンパイル順序表２６によりサブルーチンＢの処理を
行なう。このときレジスタ割当て手段２４において、Ｂ
がＣ及びＤを呼び出しているので図４のレジスタ割当て
状況表２８を参照し、Ｃで使用しているレジスタＲｅｇ
１〜Ｒｅｇ５をＣの呼び出しの前後で定義／参照しない
ように、また、Ｄで使用しているレジスタＲｅｇ１〜Ｒ
ｅｇ３をＤの呼び出しの前後で定義／参照しないように
レジスタを割当てる。レジスタ割当て結果はレジスタ割
当て状況表２８に記録するが、このときＢから呼び出し
ているＣとＤで使用しているレジスタもＢで使用してい
るものとして記録する。以後プログラムＡまで同様に処
理する。
【００１９】
【発明の効果】以上説明したように本発明は、手続きの
呼び出し関係を考慮したレジスタ割当てを行なうことに
より、手続き呼び出しに伴う不要なレジスタの退避／復
元を削減することができ、プログラムの実行時性能を向
上できる効果がある。
呼び出し関係を考慮したレジスタ割当てを行なうことに
より、手続き呼び出しに伴う不要なレジスタの退避／復
元を削減することができ、プログラムの実行時性能を向
上できる効果がある。
【図１】本発明の一実施例であるレジスタ割当て方式の
構成図である。
構成図である。
【図２】本発明が適用されるソースプログラムの例を示
す図である。
す図である。
【図３】本発明のコンパイル順序表の例を示す図である
。
。
【図４】本発明のレジスタ割当て状況表の例を示す図で
ある。
ある。
１ ソースプログラム
２ コンパイラ
３ 目的プログラム
２１ プログラム構造解析手段
２２ 手続き読み込み手段
２３ 構文解析手段
２４ レジスタ割当て手段
２５ 目的プログラム生成手段
２６ コンパイル順序表
２７ 中間テキスト
２８ レジスタ割当て状況表
Claims (1)
- 【請求項１】 ソースプログラムを翻訳して目的プロ
グラムを生成するコンパイラにおいて、前記ソースプロ
グラムを解析して手続き呼び出しの関係を調べ、他の手
続きを呼び出していない手続きを１番目、この１番目の
手続きを呼び出している手続きを２番目、この２番目の
手続きを呼び出している手続きを３番目といったような
順序を付け、その順序を格納したコンパイル順序表を生
成するプログラム構造解析手段と、該コンパイル順序表
に従ってソースプログラム中の手続きを順番に読み込む
手続き読み込み手段と、読み込まれた手続きを解析して
中間テキストを生成する構文解析手段と、前記中間テキ
ストを入力してレジスタを割当てる際に、処理中の手続
きが他の手続きを呼び出していない場合には、通常のレ
ジスタ割当てを行ないその割当て状況をレジスタ割当て
状況表に格納し、また処理中の手続きが他の手続きを呼
び出している場合には、レジスタ割当て状況表を参照し
て呼び出している手続きで使用しているレジスタをその
呼び出しの前後にまたがって使用しないようにレジスタ
を割当て、その状況をレジスタ割当て状況表に格納する
レジスタ割当て手段と、前記中間テキストから目的プロ
グラムを生成する目的プログラム生成手段とを備えたこ
とを特徴とするレジスタ割当て方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP14413491A JPH04344536A (ja) | 1991-05-21 | 1991-05-21 | レジスタ割当て方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP14413491A JPH04344536A (ja) | 1991-05-21 | 1991-05-21 | レジスタ割当て方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH04344536A true JPH04344536A (ja) | 1992-12-01 |
Family
ID=15355012
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP14413491A Pending JPH04344536A (ja) | 1991-05-21 | 1991-05-21 | レジスタ割当て方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH04344536A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06242963A (ja) * | 1993-02-16 | 1994-09-02 | Nec Corp | レジスタ割付け方式 |
-
1991
- 1991-05-21 JP JP14413491A patent/JPH04344536A/ja active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06242963A (ja) * | 1993-02-16 | 1994-09-02 | Nec Corp | レジスタ割付け方式 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5768596A (en) | System and method to efficiently represent aliases and indirect memory operations in static single assignment form during compilation | |
| US6173444B1 (en) | Optimizing compilation of pointer variables in the presence of indirect function calls | |
| EP0651327A2 (en) | Recompilation of computer programs for enhanced optimization | |
| US7784039B2 (en) | Compiler, compilation method, and compilation program | |
| EP0933706B1 (en) | Language processing system and language processing method enabling reduction of memory region and overhead in profile information collection of computer | |
| JPS6325733A (ja) | コンパイラ処理方式 | |
| JP2002366366A (ja) | コンパイル方法、コード生成方法、スタックレジスタ使用方法、コンパイラ、これらを実現するプログラム及び記憶媒体 | |
| US6625806B1 (en) | Language processing method and language processing system improving use efficiency of cache memory | |
| JPH04344536A (ja) | レジスタ割当て方式 | |
| JP2919302B2 (ja) | Ｃｐｕシミュレーション方法 | |
| US5815716A (en) | Method for supporting multiple call interface conventions for computer programs using directives | |
| JP3871312B2 (ja) | プログラム変換方法、これを用いたデータ処理装置及びプログラム | |
| JPH01277934A (ja) | パラメータリスト参照方法の切換え方式 | |
| JPH06110702A (ja) | 手続き呼出し翻訳装置 | |
| JPH11272473A (ja) | プログラム言語処理装置のコード最適化方式 | |
| JP3566602B2 (ja) | コンパイル方法、および、コンパイル用プログラムを記録した記録媒体 | |
| JPH0520091A (ja) | レジスタ割り当て方式 | |
| JPH04149738A (ja) | プログラム最適化装置 | |
| JPH02105224A (ja) | コンパイラにおけるデータ割付け方式 | |
| JPH04216140A (ja) | 再帰的手続き翻訳方式 | |
| JPH09311792A (ja) | レジスタ割り付け方法 | |
| JPH0991151A (ja) | コンパイル装置及びプロセッサ装置 | |
| JPH0566949A (ja) | 関数定義コンパイルドコード呼出し方式 | |
| JPS5960641A (ja) | 呼出し関係解析方法 | |
| JPH04153736A (ja) | 行番号情報付加方式 |