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

Abstract

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

Description

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

〔従来の技術〕

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

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

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

また、コンパイラの構成に依存する中間テキストまたは
コード生成後のテキストに対してレジスタを割り付けて
いたので、コンパイラごとにコンパイラ特有のレジスタ
割付は処理を用意する必要があるという欠点がある。

本発明の目的は、上述の点に鑑み、命令列の制御移行に
沿って命令列を解析し命令のレジスタに関する依存関係
およびメモリ・レジスタ間の同値関係の状態を調査して
レジスタの再割付けを行い不要なロード命令を削除する
ことにより、オブジェクトプログラムのサイズの縮小お
よび実行スピードの向上を図るようにしたレジスタ再割
付は方式を提供することにある。

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

本発明のレジスタ再割付は方式は、メモリ・レジスタ間
のロード／ストア命令をもち間接分岐命令をもたないア
ーキテクチャ上において、命令格納媒体から命令の並び
を入力してメモリ上に展開する命令入力手段と、この命
令入力手段によりメモリ上に展開された命令を解析し分
岐命令の直後と分岐先ラベル位置とで命令の並びを分割
して命令ブロックを作成するとともに分割した命令ブロ
ック間の制御の流れを求めて同値関係解析対象の命令ブ
ロックを限定する命令ブロック分割手段と、この命令ブ
ロック分割手段により分割された命令ブロック間のレジ
スタの依存関係を調査し命令ブロックの入口および出口
で生きているレジスタを求めるブロック間レジスタフロ
ー解析手段と、前記命令ブロック分割手段により限定さ
れた同値関係解析対象の命令ブロックについて制御フロ
ーに沿って命令の同値関係の状態を解析する同値関係解
析手段と、この同値関係解析手段により同値関係が解析
されたメモリからの不要なロード命令があれば矛盾がな
いようにレジスタの再割付けを行って不要なロード命令
を削除するレジスタ再割付は手段と、このレジスタ再割
付は手段によるレジスタ再割付は済みの命令の並びを命
令格納媒体に出力する命令出力手段とを有する。

〔作用〕

本発明のレジスタ再割付は方式では、命令入力手段が命
令格納媒体から命令の並びを入力してメモリ上に展開し
、命令ブロック分割手段が命令入力手段によりメモリ上
に展開された命令を解析し分岐命令の直後と分岐先ラベ
ル位置とで命令の並びを分割して命令ブロックを作成す
るとともに分割した命令ブロック間の制御の流れを求め
て同値関係解析対象の命令ブロックを限定し、ブロック
間レジスタフロー解析手段が命令ブロック分割手段によ
り分割された命令ブロック間のレジスタの依存関係を調
査し命令ブロックの入口および出口で生きているレジス
タを求め、同値関係解析手段が命令ブロック分割手段に
より限定された同値関係解析対象の命令ブロックについ
て制御フローに沿って命令の同値関係の状態を解析し、
レジスタ再割付は手段が同値関係解析手段により同値関
係が解析されたメモリからの不要なロード命令があれば
矛盾がないようにレジスタの再割付けを行って不要なロ
ード命令を削除し、命令出力手段がレジスタ再割付は手
段によるレジスタ再割付は済みの命令の並びを命令格納
媒体に出力する。

〔実施例〕

次に、本発明について図面を参照して詳細に説明する。

第１図は、本発明の一実施例に係るレジスタ再割付は方
式の構成を示すブロック図である。本実施例のレジスタ
再割付は方式は、命令人力手段１と、命令ブロック分割
手段２と、ブロック間レジスタフロー解析手段３と、同
値関係解析手段４と、レジスタ再割付は手段５と、命令
出力手段６と、命令展開メモリ７と、複数のブロックテ
ーブル８と、複数の同値関係表９と、ファイル、メモリ
等でなり機械語命令（以下、単に命令という）を格納す
る命令格納媒体１０とから構成されている。

第２図を参照すると、各ブロックテーブル８は、アドレ
ス順次チェーンと、アドレス順前チェーンと、命令ポイ
ンタと、入口で生きているレジスタと、出口で生きてい
るレジスタと、直先行ブロック数（Ｐ）と、直後続ブロ
ンク数（Ｓ）と、直先行ブロック数（ｐ＞の直先行ブロ
ックポインタと、直後続ブロック数（Ｓ）の直後続ブロ
ックポインタと、同値関係表ポインタと、非対象ブロッ
クフラグと、同価関係解析処理済みフラグとから構成さ
れている。各ブロックテーブル８は、ブロックテーブル
起点ポインタからアドレス順にアドレス順次チェーンお
よびアドレス順前チェーンによってチェーニングされて
いる。命令ポインタは、命令展開メモリ７上の命令のア
ドレスまたは命令展開メモリ７上の展開命令内相対オフ
セットでなり、命令展開メモリ７上に展開された命令中
の対応する命令ブロック（以下、単にブロックという）
の先頭命令をポイントしている。直先行ブロックポイン
タは、当該ブロックテーブル８のブロックに制御フロー
上で直先行するブロックのブロックテーブル８をポイン
トしている。直後続ブロックポインタは、当該フ゛ロソ
クテーフ゛ル８のフ゛ロックに制御フロー上で直後続す
るブロックのブロックテーブル８をポイントしている。

同値関係表ポインタは、当該ブロックテーブル８のブロ
ックが同値関係解析対象のブロック（以下、同値関係解
析対象ブロックという）である場合に同値関係表９をポ
イントしている。非対象ブロックフラグは、同値関係解
析対象外のプロ、りを識別するためのフラグである。同
値関係解析処理済みフラグは、同値関係解析対象ブロッ
クを処理したかどうかを識別するためのフラグである。

同しく、第２図を参照すると、同値関係表９は、同値レ
ジスタと、同値メモリのアドレス（例えば、ペースレジ
スタＢ２基準）および長さとからなる複数の同値関係情
報で構成されている。

次に、このように構成された本実施例のレジスタ再割付
は方式の動作について説明する。

まず、命令入力手段１は、命令格納媒体１０から１命令
ずつ命令を入力し、命令展開メモリ７上に展開した後、
命令ブロック分割手段２を呼び出す。

命令ブロック分割手段２は、命令コードを解析し、命令
が分岐命令のときにのみブロック分割処理を行う。ブロ
ックとは、命令の並びの中で制御上入口が１つで出口が
１つ、かつ途中に出口以外の分岐がないような単位をい
い、分割されたブロックは、第２図に示すように、ブロ
ックテーブル８が命令ポインタにより命令展開メモリ７
中のブロックの先頭命令をポイントすることによって指
示される。命令ブロック分割手段２は、ブロック分割処
理では、以下の処理２，１〜２．４により分岐命令の直
後と分岐先ラヘル位置とでブロックを分割し、処理２．
５により同値関係解析対象ブロックを限定する。

処虐λユ」電分岐命令の直後の命令を命令ポインタによ
ってポイントするプロ・７クテーブル８をサーチし、す
でにあれば何もしない。なければ、ブロックテーブル８
を１つ作成し、分岐命令の直後の命令をブロックの最初
の命令として命令ポインタを設定し、作成したブロック
テーブル８を命令のアドレス順にアドレス順次チェーン
およびアドレス順前チェーンによって直前および直後の
ブロックテーブル８とチェーニングする。

カニ１ユ１：分岐命令が条件分岐命令の場合、条件分岐
命令を含むブロックの先頭命令をポイントするブロック
テーブル８と条件分岐命令の直後の命令をポイントする
ブロックテーブル８とを直先行ブロックポインタおよび
直後続プロ・ツクポインタによって互いにチェーニング
する。ここで、直先行ブロックとは制御フロー上の直前
のブロックをい堕直後続ブロンクとは制御フロー上の直
後のブロックをいう。

処理Ｉ−１：分岐命令の分岐相対オフセントから下方向
への分岐ならば無条件にブロックテーブル８を作成し、
処理２．１と同様に作成したブロックテーブル８を命令
のアドレス順にアドレス順次チェーンおよびアドレス順
向チェーンによって直前および直後のブロックテーブル
８とチェーニングし、さらに処理２．２と同様に分岐命
令を含むブロックの先頭命令をポイントするブロックテ
ーブル８を制御フロー順に直先行ブロンクポインタおよ
び直後線ブロックポインタによって直先行ブロックおよ
び直後線ブロックのブロンクチ−プル８とチェーニング
する。

ｎ↓工土：分岐命令の分岐相対オフセントから上方向へ
の分岐ならば分岐先命令をポイントするブロックテーブ
ル８がないときにのみプロ、クチ−プル８を作成して、
処理２．１と同様に作成したブロックテーブル８を命令
のアドレス順にアドレス順次チェーンおよびアドレス順
向チェーンによって直前および直後のブロック九−ブル
８とチェーニングし、さらにブロックテーブル８を新し
く作成しなかった場合も含めて、処理２．２と同様に分
岐命令を含むブロックの先頭命令をポイントするブロッ
クテーブル８を制御フロー順に直先行ブロックポインタ
および直後線ブロックポインタによって直先行ブロック
および直後線ブロックのプロンクチ−プル８とチェーニ
ングする。

！！Ｉ！ＪＬＬ−ｉ：分岐命令の分岐相対オフセントか
ら上方向への分岐ならば、ループとなる可能性があるの
で、分岐命令を含むブロックからアドレスの逆順にブロ
ックをたどり、分岐先のブロックまでの全ブロックを同
値関係解析対象外のブロックとして、各ブロックテーブ
ル８に非対象ブロックフラグを立てる。

命令入力手段１と命令ブロック分割手段２との処理を繰
り返し、全命令について処理を行うと、ブロックテーブ
ル８単位の制御フローができあがり、同時に制御フロー
上でループに含まれない同値関係解析対象ブロックが非
対象ブロックフラグにより認識可能となる。

次に、ブロック間レジスクフロー解析手段３は、ブロッ
ク間のレジスタの依存関係（ブロック間にまたがってそ
の値が引き継がれるか否かの関係、レジスタ上の値が引
き継がれている間そのレジスタは「生きている」という
）を調べ、ブロック間のレジスタフローを表すために、
全ブロックに対して各ブロックの入口で生きているレジ
スタおよび各ブロックの出口で生きているレジスタをブ
ロックテーブル８に設定する。詳しくは、ブロック間レ
ジスタフロー解析手段３は、処理３．１を行った後、制
御フローの逆順に処理３．２〜３．３を繰り返す。

処理１エエ：制御フロー上の最後のブロックのブロック
テーブル８に、ブロックの出口で生きているレジスタを
設定する。

ｍユ１：以下の条件■および■のいずれがを満たすレジ
スタを、ブロックの入口で生きているレジスタとして、
ブロックテーブル８に設定する。

■　ブロックの出口で生きていて、そのプロ７りで定義
されていない。

■　ブロック内で最初に現れたレジスタアクセス命令が
レジスタ参照命令である。

処皿主−主：以下の条件■を満たすレジスタを、ブロッ
クの出口で住きているレジスタとして、ブロックテーブ
ル８に設定する。

■　直後続ブロンクの入口で生きている。

次に、同値間係解析手段４は、第２図に示すようにブロ
ックテーブル８から同値関係表ポインタによってチェー
ニングされた同値関係表９を使って、制御フロー上にメ
モリとレジスタとの間の同値関係を解析する（ここでい
う同値関係とは、命令実行中のある時点でメモリの内容
とレジスタの内容とが同じ値である関係のことであり、
一般にメモリからレジスタへのロード命令およびレジス
タからメモリへのストア命令によって関係付けられる）
。詳しくは、同値関係解析手段４は、ブロックテーブル
起点ポインタから制御フロー順にブロックテーブル８を
たどり、制御フロー上で−固まりになった同値関係解析
対象ブロックの集合の１つずつに対して、処理４．１を
実行した後、処理４．４でブロックＢが見つからなくな
るまで、処理４．２〜４．４を繰り返し実行する。

処理（工上：制御フロー順にブロックテーブル８をたど
り、以下の条件■および■のいずれかを満たすブロック
Ｂをさがし、同値関係表９を生成して初期化し、ブロッ
クテーブル８から同値関係表ポインタによってチェーニ
ングする。

■　直先行ブロックがない（直先行プロ・ツク数が０）
。

■　すべての直先行ブロックが同値関係解析対象外のブ
ロック（非対象ブロックフラグが立っている）または同
値関係解析処理済みのブロック（同値関係解析処理済み
フラグが立っている）である。

１Ｌ４ｆｆ工：ブロソクＢ内の全命令に対し、制御順に
各命令の種別によって以下の■、■および■のいずれか
の処理を行う。

１　ロードｔ　の　人 ロード元のメモリのアドレスおよび長さ（命令によって
決まる）が同値関係表９に設定されている場合（＝ロー
ド元のメモリに対して同値関係が付いている場合）、レ
ジスタ再割付は手段５を呼び出す。それ以外の場合、同
値関係表９にロード元のメモリのアドレス、長さおよび
ロード先のレジスタを設定する。

■　ストアｔ　の８人 ストア先のアドレスおよび長さで示されるメモリのどこ
か一部に対してでも同値関係表９に設定されている場合
（＝ストア先のメモリに対して一部でも同値関係が付い
ている場合）、同値関係表９からその同値関係情報を削
除する。さらに、同値関係表９にストア先のメモリのア
ドレス、長さおよびストア元のレジスタを設定する。

■　ロード　　でもストア　　でもない　４何もしない
。

文す！」よ−」−ニブロックＢの直後続ブロックのうち
の同値関係解析対象ブロックに、以下のように同値関係
情報を引き継く。

■　ブロックＢの直後続ブロックのブロックテーブル８
の同値関係表ポインタが空ポインタならば、同値関係表
９を生成してブロックテーブル８から同値関係表ポイン
タによってチェーニングし、ブロックＢの同値関係表９
をコピーする。

■　フロックＢの直後続ブロックのブロックテーブル８
の同値関係表ポインタが空ポインタでなければ、その同
値関係表９の同値関係情報のうちのフロックＢの同値関
係表９の内容と異なる同値関係情報は削除する。

■　同値関係解析処理済みフラグを立てる。

処理↓２工：ブロソクＢの直後続ブロックのうちの以下
の条件■および■をすべて満たすブロックをブロックＢ
とする。

■　すべての直先行ブロンクが同値関係解析対象外のブ
ロックまたは同値関係解析処理済みのブロックである。

■　同値関係解析対象ブロックである。

条件■および■を満たすブロックがなければ、ブロック
Ｂの直後続ブロックの直先行ブロックから、以上の条件
■および■に加えて以下の条件■および■を満たすブロ
ックをブロックＢとする。

■　フロックＢでない。

■　同値関係解析未処理のブロックである。

ブロックＢの直後続ブロックの直先行ブロックに条件■
〜■を満たすブロックがなければ、さらに条件■〜■を
満たすブロックの直先行ブロックをたどって、条件■〜
■を満たすブロックをさがし、ブロックＢとする。この
結果、ブロックＢの直先行ブロックに１つでも同値関係
解析対象外のフロックがあった場合、フロックＢのブロ
ックテーブル８の同値関係表ポインタが空ポインタなら
ば、同値関係表９を生成して初期化し、ブロックテーブ
ル８から同値関係表ポインタによってチェニングする。

ブロックＢのブロックテーブル８の同値関係表ポインタ
が空ポインタでなければ、その同値関係表９を初期化す
る。

レジスタ再割付は手段５は、同値関係解析手段４から呼
び出されると、同値関係を引き継いで不要なロード命令
を削除するために、以下の処理５１〜５．３により、レ
ジスタの再割付けを試みる。ここで、現在処理中のブロ
ックをＢとし、メモリＭとレジスタＲ１とに同値関係が
付いているとする。また、メモリＭからレジスタＲ２へ
のロード命令をし、メモリＭとレジスタＲ１との同値関
係を付けた命令をＳｉ　　（ｉ＝１．・・・、ｎｕｎ≧
１）、ブロックＢの先頭からロード命令しの直前の命令
までの区間をα、ロード命令しの直後の命令からブロッ
クＢの最後までの区間をβとする。

さらに、ロード命令しで参照可能なレジスタＲに対し、
ロード命令し以前でレジスタＲの生きている区間γ　（
Ｒ）とロード命令し以降でレジスタＲの生きている区間
δ　（Ｒ）とは、それぞれ以下のように求められる（た
だし、区間γ　（Ｒ）および区間δ（Ｒ）は同値関係解
析対象ブロックの範囲内とする）。

ＩＩＴ　（Ｒ）のン゛め ■　区間α内にレジスタＲの定義命令（ロード命令、演
算命令等）があれば、区間α内の最後のレジスタＲの定
義命令以降の区間のうちの最後のレジスタＲの参照命令
までの区間を区間γ　（Ｒ）とする。区間α内の最後の
レジスタＲの定義命令以降の区間にレジスタＲの参照命
令がなければ、レジスタＲの定義命令のみを区間γ　（
Ｒ）とする。

■　区間α内にレジスタＲの定義命令がなければ、ブロ
ックＢの直先行ブロックＰＢｉ　　（ｉ＝１゜・・・、
ｎ）内の命令を制御の逆順にたどり、最初に見つかった
レジスタＲの定義命令以降のロード命令りまでの区間の
うちの最後のレジスタＲの参照命令までの区間をそれぞ
れγｉ　　（Ｒ）とすると、区間γ１　　（Ｒ）から区
間ｙｎ（Ｒ）までのすべての区間を合わせた区間をγ　
（Ｒ）とする。それぞれレジスタＲの参照命令がない場
合は■と同様である。直先行ブロックＰＢｉにレジスタ
Ｒの定義命令がなければ、さらに直先行ブロックＰＢｉ
の直先行ブロックをたどって同様に求める。

日δ（Ｒ）の）゛め ■　区間β内にレジスタＲの定義命令があれば、区間β
内の最初のレジスタＲの定義命令以前の区間のうちの最
後のレジスタＲの参照命令までの区間をδ　（Ｒ）とす
る。区間β内の最初のレジスタＲの定義命令以前にレジ
スタＲの参照命令がなければ、δ（Ｒ）＝φ（空）とす
る。

■　区間β内にレジスタＲの定義命令がなく、ブロック
Ｂの出口でレジスタＲが生きていなければ、区間β内の
最後のレジスタＲの参照命令までの区間を６　（Ｒ）と
する。区間β内にレジスタＲの参照命令がなければ、δ
（Ｒ）＝φとする。

■　区間β内にレジスタＲの定義命令がなく、ブロック
Ｂの出口でレジスタＲが生きていれば、ブロックＢの直
後続ブロックのうちの同値関係解析対象ブロックＳＢｊ
　　（ｊ＝１．　・＝、ｍ：ｍ≧１）内の命令を制御順
にたどり、ロード命令りから最初に見つかったレジスタ
Ｒの定義命令までの区間のうちの最後のレジスタＲの参
照命令までの区間をそれぞれδｊ　　（Ｒ）とすると、
区間δ１　　（Ｒ）から区間δｍ　（Ｒ）までのすべて
の区間を合わせた区間をδ　（Ｒ）とする。それぞれレ
ジスタＲの参照命令がない場合は、δｊ　　（Ｒ）　＝
φとする。

同値関係解析対象ブロックＳＢｊにレジスタＲの定義命
令がなく同値関係解析対象ブロックＳＢｊの出口でレジ
スタＲが生きていれば、さらに同値関係解析対象ブロッ
クＳＢｊの直後続ブロックのうちの同値関係解析対象ブ
ロックをたどって同様に求める。同値関係解析対象ブロ
ックＳＢｊの出口でレジスタＲが生きていなければ、同
値関係解析対象ブロックＳＢｊ内の最後のレジスタＲの
参照命令までの区間をδｊ　　（Ｒ）とする。

ｍユ」工：ロード命令しで定義したレジスタＲ２をレジ
スタＲ１に置き換えることによって、ロード命令りを削
除しようと試みる。以下の条件■を満たした場合、区間
δ（Ｒ２）内のレジスタＲ２の参照命令におけるレジス
タＲ２をレジスタＲ１に変更して、ロード命令りを削除
する。

■　ロード命令して定義されたレジスタＲ２が生きてい
る間、レジスタＲ１の定義命令がない。

すなわち、 ［δ（Ｒ２）幹レジスタＲ１の定義命令コ条件■を満た
してロード命令りを削除した場合、区間δ（Ｒ２）がブ
ロックＢ以外のブロックにまたがっている場合は、また
がったブロックとの間のレジスタの依存関係を調査し直
して、各プロ。

りの入口および出口で生きているレジスタの情報を各ブ
ロックテーブル８に再設定する。

ｍユ主：処理５．１のレジスタＲ２からレジスタＲ１へ
の置換によるロード命令しの削除が不可能だった場合、
ロード命令して同値関係が付いているレジスタＲ１をレ
ジスタＲ２に置き換えることによって、ロード命令りを
削除しようと試みる。以下の条件■を満たした場合、区
間（γ　（Ｒ１）＋δ（Ｒ１）ｌ内のレジスタＲ１の定
義／参照命令のレジスタＲ１をレジスタＲ２に変更して
、ロード命令りを削除する。

■　命令Ｓｉで同値関係を付けたレジスタＲ１が生きて
いる間で、かつロード命令りで定義したレジスタＲ２が
生きている間取外で、レジスタＲ２の定義／参照命令が
ない。すなわち、［γ（Ｒ１）＋δ　（Ｒ１）−δ　（
Ｒ２）幹しジスクＲ２の定義／参照命令〕 条件■を満たしてロード命令りを削除した場合、区間（
γ　（Ｒ１）＋δ（Ｒ１）ｌがブロックＢ以外のブロッ
クにまたがっている場合は、またがったブロックとの間
のレジスタの依存関係を調査し直して、各ブロックの入
口および出口で生きているレジスタの情報を各ブロック
テーブル８に再設定する。

火星】ユニ：処理５．２のレジスタＲ１からレジスタＲ
２への置換によるロード命令しの削除も不可能だった場
合、レジスタの再割付けは行わない。

命令出力手段６は、同値関係解析対象の全ブロックに関
して同値関係解析手段４とレジスタ再割付は手段５とに
よって最適化を行った後、命令を格納してあった任意の
命令格納媒体１０にレジスタ再割付は済みの命令の並び
を出力する。

〔発明の効果〕

以上説明したように本発明は、命令列の側御移行に沿っ
て命令列を解析し、命令のレジスタに関する依存関係お
よびメモリ・レジスタ間の同値関係の状態を調査してレ
ジスタの再割付けを行い、不要なロード命令を削除する
こと乙こより、オブジェクトプログラムのサイズを縮小
でき、実行スピードも向上させることができるという効
果がある。

また、機械語命令に対して適用されるので、同一アーキ
テクチャ上のコンパイラに対して汎用的に適用すること
が可能であり、さらにコンパイラが出力したオブジェク
トプログラムに対しても適用可能になるという効果があ
る。

【図面の簡単な説明】

第１図は本発明の一実施例に係るレジスタ再割付は方式
の構成を示す回、 第２図は第１図中の命令展開メモリ、ブロックテーブル
および同値関係表の内容を示す図である。 図において、 １・・・命令入力手段、 ２・・・命令ブロック分割手段、 ３・・・ブロック間レジスタフロー解析手段、４・・・
同値関係解析手段、 ５・・・レジスタ再割付は手段、 ６・・・命令出力手段、 ７・・・命令展開メモリ、 ８・・・ブロックテーブル、 ９・・・同値関係表、 １０・・命令格納媒体である。

Claims (1)

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