JPH04141737A - レジスタ再割付け方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はレジスタ再割付は方式に関し、特にメモリ・レ
ジスタ間のロード／ストア命令をもち、間接分岐命令を
もたないアーキテクチャ上におけるレジスタ再割付は方
式に関する。

〔従来の技術〕

従来、レジスタの割付けは、コンパイラ内部の中間テキ
スト、またはコード生成後のテキストに対して行われて
おり、（レジスタ割付けも含めて）機械語命令の生成完
了後に、再度レジスタの割付けが行われることはなかっ
た。

〔発明が解決しようとする課題〕

上述したコンパイラ内部の中間テキスト、またはコード
生成後のテキストに対して行う従来のレジスタ割付は方
式では、必すしも同値関係（命令実行中のある時点て、
メモリの内容とレジスタの内容とが同じ値である関係）
を考慮したレノスタ割付けが行われているとはかぎらず
、同値関係を有効利用しない不要なロード命令が生成さ
れる場合があり、オブジェクトサイズの増大や実行スピ
ードの低下を招くという問題点があった。

また、コンパイラの構成に依存する中間テキスト、また
はフード生成後のテキストに対してレジスタを割付けて
いたため、コンパイラごとにフッバイラ特有のレジスタ
割付は処理を用意しなければならないという問題点があ
った。

本発明の目的は、オブジェクトサイズを縮小することが
でき、実行速度も向上できるとともに、コンパイラごと
にコンパイラ特有のレジスタ割付は処理を用意する必要
がないレジスタ再割付は方式を提供することにある。

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

第１の発明のレジスタ再割付は方式は、メモリとレジス
タとの間のロード／ストア命令をもち、間接分岐命令を
もたないアーキテクチャ上のレジスタ再割付は方式にお
いて、 （Ａ）命令を格納した媒体から命令の並びを入力してメ
モリ上に展開する命令入力手段、（Ｂ）入力した前記命
令を解析して、分岐命令の直後と分岐先ラベル位置で命
令の並びを分割して命令ブロックを作成し、同時に分割
した前記命令ブロック間の制御の流れを求める命令ブロ
ック分割手段、 （Ｃ）前記分割した命令ブロンク間のレジスタの定義書
参照の依存関係を調査し、前記命令ブロックの入口／出
口で生きているレジスタを求めるプロ、り間レジスタフ
ロー解析手段、（Ｄ）前記分割した命令ブロック内の命
令について、命令実行中のある時点て前記メモリの内容
と前記レジスタの内容とが同じ値の関係をボす同値関係
の状態を解析する同値関係解析手段、 （Ｅ）前記同値関係の付いた前記メモリからの不要なロ
ード命令があれば、矛盾がないように前記レジスタの再
割付けを行って不要なロード命令を削除するレジスタ再
割付は手段、（Ｆ）分割したすべての前記命令ブロック
に関して同値関係解析及びレジスタ再割付けを行った後
、命令を格納してあった前記媒体にレジスタ再割付は済
命令の並びを出力する命令出力手段、 を有して構成されている。

また、第２の発明のレジスタ再割付は方式は、メモリと
レジスタとの間のロード／ストア命令をもち、間接分岐
命令をもたないアーキテクチャ上のレジスタ再割付は方
式において、 （Ａ）命令を格納した媒体から命令の並びを入力してメ
モリ上に展開するステ・ツブ、 （Ｂ）入力した前記命令を解析して、分岐命令の直後と
分岐先ラベル位置で命令の並びを分割して命令ブロック
を作成し、同時に分割した前記命令ブロック間の制御の
流れを求めるステップ） （Ｃ）前記分割した命令ブロック間のレジスタの定義・
参照の依存関係を訳査し、前記命令ブロックの入口／出
口で生きているレジスタを求めるステップ、 （Ｄ）前記分割した命令ブロック内の命令ζこつ（１て
、命令実行中のある時点て前記メモリの内容と前記レジ
スタの内容とが同じ値の関係を示す同値関係の状態を解
析するステ・ツブ、（Ｅ）前記同値関係の付いた前記メ
モリからの不要なロード命令があれば、矛盾かな０よう
番こ前記レジスタの再割付けを行って不要なロード命令
を削除するステ・ツブ、 （Ｆ）分割したすべての前記命令ブロック（こ関して同
値関係解析及びレジスタ再割付けを行った後、命令を格
納してあった前記媒体（こレジスタ再割付は済命令の並
びを出力するステ・ツブ、 を実行するように構成されている。

〔実施例〕

次に、本発明の実施例について図面を参照して説明する
。

第１図は本発明の一実施例のブロック図である。

第１図に示すレジスタ再割付は方式は、命令を格納した
媒体から命令の並びを入力してメモリ上に展開する命令
入力手段１、入力した命令を解析して、分岐命令の直後
と分岐先ラベル位置で命令の並びを分割して命令ブロッ
クを作成し、同時に分割した前記命令ブロック間の制御
の流れを求める命令ブロック分割手段２、分割した命令
ブロック間のレジスタの定義φ参照の依存関係を調査し
、命令ブロックの入口／出口で生きているレジスタを求
めるブロック間レジスタフロー解析手段３、分割した命
令ブロック内の命令について、命令実行中のある時点で
メモリの内容とレジスタの内容とが同じ値の関係を示す
同値関係の状態を解析する同値関係解析手段４、同値関
係の付いたメモリからの不要なロード命令があれば、矛
盾がないようにレジスタの再割付けを行って不要なロー
ド命令を削除するレジスタ再割付は手段５、分割したす
べての命令ブロックに関して同値関係解析及びレジスタ
再割付けを行った後、命令を格納してあった媒体にレジ
スタ再割付は済命令の並びを出力する命令出力手段６、
命令展開メモリ７、ブロックテーブル群８、同値関係表
９、命令格納媒体（ファイルまたはメモリ）１０から構
成されている。

なお、第１図の各ブロック間の処理の流れは、太線の矢
印で示され、データの流れは細線の矢印で示されている
。

次に、動作を説明する。

まず、命令入力手段１により、命令を格納した任意の媒
体（ファイルまたはメモリ）′１０から命令の並びを入
力する。入力は一命令ずつ行い、命令展開メモリ７上に
展開した後、−命令ごとに、命令ブロック分割手段２に
より、命令を解析しながら、制御上入口が一つで出口が
一つ、かつ途中に出口以外の分岐がないような単位（以
降「命令ブロック」または単に「ブロック」と呼ぶ）に
命令の並びを分割していく。

命令ブロック分割手段２の処理の流れは第２図に示す通
りである。分割された命令プロ、ツクは、第４図に示す
ようなブロックテーブルが命令展開メモリ７中のブロッ
クの先頭命令をポイントすることにより表現される。

命令ブロック分割手段２は、命令コードを解析しくステ
ップ１１）、対象命令が分岐命令か否かを判断しくステ
ップ１２）、分岐命令のときのみブロック分割処理を行
う。すなわち、対象命令が分岐命令ならば、まず、分岐
命令の次の命令を指しているブロックテーブルを検索し
くステップ１３）、すでにあれば何もしない。もし、分
岐命令の次の命令を指しているブロックテーブルがなけ
れば、ブロックテーブルを一つ作成しくステップ１４）
、分岐命令の次の命令を、次ブロックの最初の命令とし
て命令へのポインタ（または命令展開メモリ７上の展開
命令内相対オフセット、以降の命令へのポインタも同様
）を設定し、プロ、ツクテーブルが命令のアドレス順に
チェ一二ングされるように、前後のブロックテーブルと
チエ一二ングする（ステップ１５）。そして、さらに分
岐命令が条件分岐命令か否かを判断しくステップ１６）
、条件分岐命令の場合は、ブロックテーブルを新しく作
成しなかった場合も含めて、現ブロックテーブルとの間
を、制御順先行ブロックポインタ及び制御順後続ブロッ
クポインタで互いにチェーニングする（ステップ１７）
。また、分岐命令の分岐相対オフセットから、下方向分
岐か否かを判断しくステップ１８）、下方向分岐ならば
無条件にブロックテーブルを作成しくステップ２０）、
上方向分岐ならば分岐先命令をポイントするブロックテ
ーブルがあるか否かを判断しくステップ１９）、ブロッ
クテーブルがないときのみ、ブロックテーブルを作成し
て（ステップ２０）、前記と同様に命令のアドレス順に
前後のブロックテーブルとチェーニングしくステップ２
１）、さらにブロックテーブルを新しく作成しなかった
場合も含ぬて、前記と同様に制御順に現ブロックテーブ
ルとチェーニングする（ステップ２２）。これで、分岐
命令の直後、及び分岐先ラベル位置でブロックが分割さ
れたことになり、命令入力手段１と命令ブロック分割手
段２とを繰り返し、全命令について前記の処理を行うと
、ブロックテーブル単位の制御フローができあがる。

このブロックテーブルの集りをブロックテーブル群８と
呼ぶ。

次に、ブロック間レジスタフロー解析手段３によって、
ブロック間のレジスタの依存関係（ブロック間にまたが
ってその値が引き継がれるか否かの関係、レジスタ上の
値が引き継がれている間は、そのレジスタは「生きてい
る」という）を調へ、ブロックの入口で生きているレジ
スタ、及びブロックの出口で生きているレジスタを求め
る。

ブロックごとに、含まれる命令列を各レジスタに着目し
て解析し、ブロック内で最初に現われたレジスタアクセ
ス命令がレジスタ参照命令ならば、そのレジスタはブロ
ックの入口で生きていることになる。ブロックテーブル
を、ブロックテーブル起点ポインタからアドレス順チェ
ーンにしたがってたどり、上記のように全ブロックに関
してその入口で生きているレジスタを洗い出し、各ブロ
ックテーブルに設定する。次に、ブロックテーブルを制
御フローの逆順にたどり、ブロックの出口で生きている
レジスタを求め、各ブロックテーブルに設定する。ブロ
ックの出口で生きているレジスタとは、制御移行上の直
後のブロックの出口で生きていて、そのブロックで定義
されていないレジスタと、制御移行上の直後のブロック
の入口で生きているレジスタとの和集合である。

ブロックの入口／出口で生きているレジスタの情報が得
られたならば、次に同値関係解析手段４によって、メモ
リとレジスタとの間の同値関係を解析する（ここでいう
同値関係とは、前述したように命令実行中のある時点て
、メモリの内容とレジスタの内容とが同じ値である関係
のことであり、一般にメモリからレジスタへのロード命
令、及びレジスタからメモリへのストア命令によって付
けられる）。

同値関係解析手段４の処理の流れは第３図に示す通りで
ある。同値関係解析手段４は、第５図に示すような同値
関係表９を使用して、プロ・νり内の命令について、−
命令ずつ命令コードによって以下のような処理をしてい
く。

まず、ロード命令か否かを判断しくステップ３１）、ロ
ード命令の場合は、次にロード先のメモリに対して同値
関係（すなわち、同一アドレス・同一長のメモリに対し
て同値関係表９がすでに設定しである場合）が付いてい
るか否か判断しくステップ３２）、同値関係が付いてい
る場合、後述のようにレジスタの再割付けを試みる（ス
テップ３３）。

ロード先のメモリに対して同値関係が付イテイない場合
（すなわち、同一アドレス・同一長のメモリに対して同
値関係表９がない場合）、新たに同値関係表９にロード
先のメモリのアドレスと長さ（命令によって決まる）、
及びロード先のレジスタを設定する（ステップ３７）。

ステップ３１において、ロード命令でない場合、さらに
ストア命令か否かを判断しくステップ３４）、ストア命
令の場合は、対象メモリの何れかと同値関係の付いたレ
ジスタがあるか否かを判断し、（ステップ３５）、スト
ア先のメモリに対して、一部でも同値関係が伺いている
場合（すなわち、アドレスと長さで示されるメモリのと
こか一部に対してでも、同値関係表９がすてに設定しで
ある場合）、同値関係表９からその情報を削除しくステ
ップ３６）、新たに同値関係表９にストア先のメモリの
アドレスと長さ（命令によって決る）、及びストア元の
レジスタを設定する（ステップ３７）。

また、ストア先のメモリに対して、一部でも同値関係が
付いていない場合（すなわち、アドレスと長さで示され
るメモリのどこか一部に対しても、同値関係表９がない
場合）、新たに同値関係表９にストア先の命令のアドレ
スと長さ（命令によって決る）、及びストア元のレジス
タを設定する（ステップ３７）。

さらに、ステップ３１及びステップ３４で、ロード命令
でもストア命令でもない場合は、何もしないで終了する
。

上記のような解析処理でレジスタの再割付は可能になっ
た場合（同値関係が付いているメモリに対するロード命
令が生成されている場合）のみ、レジスタ再割付は手段
５によって同値関係を引き継いで、不要なロード命令を
削除するようにレジスタの再割付けを行う。

ここで、同値関係を設定した命令を８１同値関係の付い
た対象メモリをＭ１対象レジスタをＲｚ削除しようとす
るＭからのロード命令をり、Ｌのロード先レジスタをＲ
２、ブロックの先頭からしの直前命令までの区間をα、
Ｌの直後の命令からブロックの最後までの区間をβ、α
区間内のＡレジスタの最後の定義命令以降の区間をγ（
Ａ）、β区間内のＡレジスタ参照命令以前の区間の内、
Ａレジスタ定義命令を含まない最大区間をδ（Ａ）とす
る（第６図参照）。

たたし、α区間内にＡレジスタ定義命令がなければ、 γ（Ａ）＝α＋ε とし、β区間内にＡレジスタ定義命令がなく、Ａレジス
タがブロックの出口で生きていれば、δ（Ａ）＝β十ε とし、β区間内にＡレジスタ定義命令があれば、最初の
Ａ定義命令まで、なければブロックの最後までの区間内
にＡレジスタ参照命令がないとき、δ（Ａ）＝０ とする。

まず、Ｌ以降のＲ２レジスタを、同値関係の付いたレジ
スタＲ１に置き換えることにより、Ｌの削除を行う。以
下の条件をすへて満たした場合、δ（Ｒ２）区間内のＲ
２レジスタ参照命令のレジスタをＲ１に変更して、Ｌを
削除する。

（１）Ｌで定義されたＲ２レジスタの寿命はブロック内
で終わる。

［δ（Ｒ２）≦β］ （２）Ｌで定義されたＲ２レジスタが生きている間、Ｒ
＋　レジスタの定義命令がない。

［δ（Ｒ２）　　Ｒ，レジスタ定義命令］Ｒ２レジスタ
→Ｒ１レジスタ置換が不可能たった場合、Ｌの前後の同
値関係の付いたレジスタＲ１を、レジスタＲ２に置き換
えることにより、Ｌの削除を行う。

以下の条件をすべて満たした場合、γ（Ｒｏ）＋６（Ｒ
８）区間内のＲ１レジスタ定義／参照命令のレジスタを
Ｒ２に変更して、Ｌを削除する。

（１）　Ｓで同値関係を設定したＲ１レジスタの寿命は
、ブロック内で始まり、ブロック内で終わる。

［γ　（Ｒ１）≦α　　＆　　δ　（Ｒ，）≦β］（２
）Ｓで同値関係を設定したＲ、レジスタが生きている間
でかつ、して定義したＲ２レジスタが生きている間以外
で、Ｒ２レジスタの定義／参照命令がない。

［γ（Ｒ１）十δ（Ｒ，）−δ（Ｒ２）Ｒ２レジスタ定
義／参照命令コ Ｒ１レジスタ→Ｒ２レジスタ置換も不可能たった場合、
レジスタの再割付けは行わない。

ブロックテーブルをブロックテーブル起点ポインタから
アドレス順チェーンにしたがってたどり、全ブロックに
関して同値関係解析手段４とレジスタ再割付は手段５と
によって最適化を行ったならば、命令出力手段６によっ
て、命令を格納してあった命令格納媒体１０にレジスタ
再割付は済命令の並びを出力する。

このように、線形に制御移行する最大の単位である命令
ブロックに対して、含まれる命令のレジスタに関する依
存関係、及びメモリ番レジスタ間の同値関係状態を調査
して、レジスタの再割付けを行い不要なロード命令を削
除することにより、オブジェクトサイズを縮小すること
ができ、実行速度も向上できる。

また、機械語命令に対して行うことにより、コンパイラ
ごとにコンパイラ特有のレジスタ割付は処理を用意する
必要がなくなり、さらに、コンパイラが出力したオブジ
ェクトに対しても適用可能である。

〔発明の効果〕

以上説明したように、本発明は、線形に制御移行する最
大の単位である命令ブロックに対して、含まれる命令の
レジスタに関する依存関係及びメモリ・レジスタ間の同
値関係状態を調査して、レジスタの再割付けを行い不要
なロード命令を削除することにより、オブジェクトサイ
ズを縮小することができ、実行速度も向上できるという
効果を有する。

また、機械語命令に対して行うことにより、コンパイラ
ごとにフンバイラ特有のレジスタ割付は処理を用意する
必要がなくなるという効果を有する。

【図面の簡単な説明】

第１図は本発明の一実施例のブロック図、第２図は第１
図に示す命令ブロック分割手段の処理の流れを示す流れ
図、第３図は第１図に示す同値関係解析手段の処理の流
れを示す流れ図、第４図は第１図に示すブロックテーブ
ル群の詳細を示す図、第５図は第１図に示す同値関係表
の詳細を示す図、第６図は第１図に示すレジスタ再割付
は手段の処理中におけるブロック内の命令の関連イメー
ジを示す図である。 １・・・・・・命令入力手段、２・・・・・・命令ブロ
ック分割手段、３・・・・・・ブロック間レジスタフロ
ー解析手段、４・・・・・・同値関係解析手段、５・・
・・・・レジスタ再割付は手段、６・・・・・・命令出
力手段、７・・・由命令展開メモ１ハ８・・・・・・ブ
ロックテーブル群、９・・・・・・同値関係表、１０・
・・・・・命令格納媒体。 代理人　弁理士　　内　原　　晋 第 図 第 図

Claims (1)

1. 【特許請求の範囲】 １、メモリとレジスタとの間のロード／ストア命令をも
   ち、間接分岐命令をもたないアーキテクチャ上のレジス
   タ再割付け方式において、 （Ａ）命令を格納した媒体から命令の並びを入力してメ
   モリ上に展開する命令入力手段、（Ｂ）入力した前記命
   令を解析して、分岐命令の直後と分岐先ラベル位置で命
   令の並びを分割して命令ブロックを作成し、同時に分割
   した前記命令ブロック間の制御の流れを求める命令ブロ
   ック分割手段、 （Ｃ）前記分割した命令ブロック間のレジスタの定義・
   参照の依存関係を調査し、前記命令ブロックの入口／出
   口で生きているレジスタを求めるブロック間レジスタフ
   ロー解析手段、 （Ｄ）前記分割した命令ブロック内の命令について、命
   令実行中のある時点で前記メモリの内容と前記レジスタ
   の内容とが同じ値の関係を示す同値関係の状態を解析す
   る同値関係解析手段、 （Ｅ）前記同値関係の付いた前記メモリからの不要なロ
   ード命令があれば、矛盾がないように前記レジスタの再
   割付けを行って不要なロード命令を削除するレジスタ再
   割付け手段、 （Ｆ）分割したすべての前記命令ブロックに関して同値
   関係解析及びレジスタ再割付けを行った後、命令を格納
   してあった前記媒体にレジスタ再割付け済命令の並びを
   出力する命令出力手段、 を有することを特徴とするレジスタ再割付け方式。 ２、メモリとレジスタとの間のロード／ストア命令をも
   ち、間接分岐命令をもたないアーキテクチャ上のレジス
   タ再割付け方式において、 （Ａ）命令を格納した媒体から命令の並びを入力してメ
   モリ上に展開するステップ、 （Ｂ）入力した前記命令を解析して、分岐命令の直後と
   分岐先ラベル位置で命令の並びを分割して命令ブロック
   を作成し、同時に分割した前記命令ブロック間の制御の
   流れを求めるステップ、 （Ｃ）前記分割した命令ブロック間のレジスタの定義・
   参照の依存関係を調査し、前記命令ブロックの入口／出
   口で生きているレジスタを求めるステップ、 （Ｄ）前記分割した命令ブロック内の命令について、命
   令実行中のある時点で前記メモリの内容と前記レジスタ
   の内容とが同じ値の関係を示す同値関係の状態を解析す
   るステップ、 （Ｅ）前記同値関係の付いた前記メモリからの不要なロ
   ード命令があれば、矛盾がないように前記レジスタの再
   割付けを行って不要なロード命令を削除するステップ、 （Ｆ）分割したすべての前記命令ブロックに関して同値
   関係解析及びレジスタ再割付けを行った後、命令を格納
   してあった前記媒体にレジスタ再割付け済命令の並びを
   出力するステップ、 を実行することを特徴とするレジスタ再割付け方式。