JPH03150637A

JPH03150637A - パイプライン対応のレジスタ割付け方式

Info

Publication number: JPH03150637A
Application number: JP1288702A
Authority: JP
Inventors: Yoshikazu Sato; 嘉一佐藤
Original assignee: Oki Electric Industry Co Ltd
Current assignee: Oki Electric Industry Co Ltd
Priority date: 1989-11-08
Filing date: 1989-11-08
Publication date: 1991-06-27
Also published as: US5261062A

Abstract

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

Description

【発明の詳細な説明】（産業上の利用分野）本発明は、プログラムミンク用高位言語で書かれたプロ
グラムの翻訳を行ないパイプライン対応の機械語を出力
するコンパイラの、各命令にレジスタを割り付けるパイ
プライン対応のレジスタ割付は方式に関する。

（従来の技術）プログラミング高位言語で書かれたプログラム（ソース
プログラム）を翻訳し、実行可能な機械語（実行形式プ
ログラム）を得るためにコンパイラが利用される。

コンパイラは、ソースプログラムを一旦中間形式プログ
ラムに翻訳した後に、この中間形式プログラムを実行形
式プログラムへと翻訳する処理を行なう。

さて１．中間形式プログラムは、擬似コードから構成さ
れている。この擬似コードは、レジスタ数に制限の無い
仮想的な機械命令である。この擬似コードで表わされた
命令のオペランドとして用いられるレジスタは仮想レジ
スタと呼ばれている。

中間形式プログラムから実行形式プログラムへと翻訳す
る場合、仮想レジスタを実際に存在する実レジスタに割
付けるレジスタ割付は処理を行なう必要がある。このレ
ジスタ割付は処理は、コンパイラのバックエンド処理（
中間形式プログラムから実行形式プログラムへの翻訳処
理）の一つとして設けられている。

ところで、レジスタ割付は処理の際、使用する実レジス
タはなるべく節約する方向でその処理が進められる。こ
れは、実レジスタが有限であることなどに依存している
。

一方、最近のＣＰＵ　（プロセッサ）では、その処理高
速化のためにパイプライン制御を行なっている。パイプ
ライン制御とは、１つの命令をさらに細かいステップに
分割し、１つの命令のあるステップを実行中、他の命令
のあるステップを実行するといったものである。これに
より、本来１つの命令しか実行できない単位時間中に、
複数の命令を実行することができ、全体として処理速度
を上げることができる。

ところで、ある命令の実行結果を別の命令が使用するよ
うな場合、前の命令の実行が終了するまで後の命令の実
行が待たされることがある。これらの命令はパイプライ
ン制御として並行処理することはできず、このような事
象をパイプの乱れと呼んでいる。

このパイプの乱れをできる限り少なくするため、コンパ
イラは一旦生成した実行形式プログラムの命令列を並べ
換える、いわゆるパイプライン対応命令再配置の最適化
処理を行なう。

（発明が解決しようとする課題）さて、従来のコンパイラは、レジスタ割付は処理と、パ
イプライン対応命令再配置の最適化処理（以下、単に最
適化処理と称す）は、それぞれ何等関係を持たずに独立
に行なっていた。

第２図に、従来のコンパイラの動作説明図を示す。

図において（ア）のようなソースプログラムが、（イ）
のような擬似コードに翻訳されたものとする。擬似コー
ド（１）では、ｂの値が仮想レジスタＶＲＩに格納され
る。擬似コード（２）では、仮想レジスタＶＲＩの値が
ａに格納される。擬似コード（３）〜（６）についても
同様の内容である。

以上のような擬似コードに実レジスタを割付けるレジス
タ割付は処理を施すと、（つ）のような機械語の実行形
式プログラムが生成される。即ち、機械語（１）では、
ｂの値が実レジスタｒ０に格納される０機械語（２）で
は、実レジスタｒ０の値がａに格納される０機械語（３
）〜（６）についても同様の内容である。

機械語相互の関係は（１）が実行された後でなければ（
２）を実行することができない、また（３）が実行され
た後でなければ（４）を実行することができない、さら
に（５）が実行された後でなければ（６）を実行するこ
とができない、言換えれば、機械語（２）　、　　（４
）が実行された後には、それぞれ実レジスタｒ０の値は
必要なくなる。このため、レジスタ割付は処理の際に、
機械語（１）〜（６）の全てに実レジスタｒ０を割付け
ることができ、またそれが最も実レジスタを効率的に使
用することになる。

ところで、（つ）に示した機械語に対して最適化を施し
た場合、各機械語の並びは換わることがない、これは、
全ての機械語（命令）に対して実レジスタｒ０が割り付
けられているため、並行してその実行を行なうことがで
きないためである。

従って、機械語（１）〜（２）　、　（３）〜（４）　
、　（５）〜（６）の間で発生するパイプの乱れを解消
することができないといった問題が生じていた。

本発明は以上の点に着目してなされたもので、パイプラ
イン対応命令再配置の最適化の効果を向上させ、パイプ
の乱れを減少させることのできるパイプライン対応のレ
ジスタ割付は方式を提供することを目的とするものであ
る。

（課題を解決するための手段）本発明のパイプライン対応のレジスタ割付は方式は、プ
ログラムの命令に使用されるレジスタを割り付けた後に
、パイプライン対応のために前記命令の再配置を行ない
、前記複数命令を並行に実行させて演算処理する場合に
おいて、前記演算処理中の所定のタイミングで、前記命
令により同時に使用されるレジスタの数を示す干渉数が
、前記レジスタの全数以下のとき、並行に実行される前
記各命令に対して個別の前記レジスタを割付けるもので
ある。

（作用）以上の方式は、前記演算処理中の所定のタイミングで、
複数の命令により同時に使用されるレジスタの数を示す
干渉数の検索を行ない、この干渉数が前記レジスタの全
数以下のとき、並行に実行される前記各命令に対して個
別の前記レジスタを割付けるものである。これにより、
複数の命令を同時に実行しても、そのレジスタが重なる
といったことを回避することができ、パイプの乱れが減
少する。

（実施例）第１図に、本発明に係るコンパイラの動作説明図を示す
。

図は、バイブライン対応命令再配置の最適化処理（最適
化処理）の前後の実行形式プログラム（機械語）を示し
ている。即ち、コンパイラにかけられるソースプログラ
ム、翻訳された中間形式プログラム（擬似コード）は、
先に第２図において説明したものと同一である。

即ち、本発明のパイプライン対応のレジスタ割付は方式
によると、（ア）に示すように実レジスタｒ　Ｏ＋　ｒ
　ｌ　＋　　ｆ”　２の３つの実レジスタが仮想レジス
タに対して割り付けられる。即ち、機械語（１１）、　
　（１２）には、実レジスタｒ０が割付けられる。同様
に機械語（１３）、　（１４）及び機械語（１５）。

（１６）には、それぞれ実レジスタｒ”ｔ　＊　ｒａが
割付けられる。

以上の状態で最適化処理を施すと、（イ）に示すように
、機械語（１１）、　　（１３）、　（１５）及び機械
語（１２）、　（ｔ４）、　（１６，）の順にその並び
が換わり、バイブの乱れを防止することができる。

さて、第３図以降を参照しながら本発明の詳細について
説明を行なう。

第３図は、本発明の方式の動作を示すフローチャートで
ある。また、第４図は、本発明に係る動作説明図である
。この第４図は、擬似コード（命令）に含まれる仮想レ
ジスタの使用状況の一覧である。

さて、第３図においてレジスタ割付は処理を行なう場合
、中間形式プログラムを構成する各擬似コードを読込み
仮想レジスタの使用状況を把握する（ステップＳ１）、
具体的には、各仮想レジスタ毎に、それを定義（ＬＯＡ
Ｄ命令等）した擬似コードや使用（ＳＴＯＲＥ命令等）
の把握を行なう（第４図の黒丸）、その後、仮想レジス
タのライブ（ｌｉｖｅ）解析を行なう（ステップＳ２）
、具体的には、各仮想レジスタの生存期間（定義から使
用迄）の把握を行なう（第４図の実線）、その後、干渉
グラフの作成を行なう（ステップＳ３）、この干渉グラ
フは、各仮想レジスタの生存期間が他の仮想レジスタと
重なっていれば干渉あり、重なりがなければ干渉なしと
して、干渉している仮想レジスタ（ノード）同志をエツ
ジで結ぶグラフを作成する。第４図の（ア）の場合には
干渉なしである。（イ）の場合には干渉がある。即ち、
仮想レジスタＶＲＩは仮想レジスタＶＲ２゜ＶＨ２と、
仮想レジスタＶＲ２は、仮想レジスタＶＲＩ、ＶＲ３、
仮想レジスタＶＲ３は、仮想レジスタＶＲＩ、ＶＲ２と
干渉しているため、各ノードがエツジで結ばれる。

次に、ステップＳ４においては、干渉グラフの縮退が行
なわれる。ここでは、先ず実レジスタの全数をＮ個であ
るものとする。干渉グラフの縮退は、各ノードから出て
いるエツジの数がＮ未満であれば、干渉グラフからその
ノード及びエツジを取り去る。この処理をエツジの数が
Ｎ未満のノートがなくなるまで繰返し行なう、このステ
ップＳ４の処理により、干渉グラフが空になれば、各ノ
ードをＮ色に色分けすることが可能である。

従って、ステップＳ５の結、果はＹＥＳとなる。ステッ
プＳ４の結果、ノードが残ればＮ色の色分けは不可能と
なり、ステップＳ５の結果がＮＯとなりステップＳ６に
移る。ステップＳ６では、スピル（Ｓｐｉｌｌ　）コー
ドの挿入処理を行なう、この挿入処理は、スピルコード
、即ち、仮想レジスタの内容をメモリ等に退避させ、さ
らに復帰させる命令を各命令の間に挿入するもので、仮
想レジスタの生存期間の短縮を目的として行なわれる。

さて、ステップＳ５の結果がＹＥＳの場合、実際に擬似
コード中の仮想レジスタに実レジスタを割付ける割付は
処理（実レジスタ冗長割付け）を行なう（ステップＳ７
）。

このステップＳ７の処理について、第５図を参照しなが
ら説明を行なう。

第５図は、実レジスタ冗長割付けの詳細なフローチャー
トである。

先ず、干渉グラフ上の仮想レジスタを１つ取出す（ステ
ップ５ｌｌ）、そして、割付は候補とする実レジスタ（
候補レジスタ）として初期レジスタ（割付けのために用
意された実レジスタの何れか）を用意する（ステップ５
１２）、そして、ステップ３１１で取出された仮想レジ
スタを、候補レジスタで色分けできるか否かの判断を行
なう。

この色分けは、この仮想レジスタにエツジで結ばれた他
の仮想レジスタの色が当該候補レジスタの色でなければ
可能である。この結果ＹＥＳで色分け（実レジスタの割
付け）が可能であった場合には、その実レジスタの割付
けを行ない、初期レジスタを他の割付は候補の実レジス
タに更新する（ステップ５１４）、そして、干渉グラフ
上に実レジスタの割付けを行なうべき他の仮想レジスタ
があるか否かの判断を行なう（ステップ５１５）。この
結果ＮＯの場合、割付けの処理を終了する。また、結果
がＹＥＳの場合にはステップＳｌｌに戻る。

ステップＳ１３の結果がＮＯの場合には、実レジスタに
他の候補があるか否かの判断を行なう（ステップ５１６
）、この結果がＹＥＳの場合には、候補レジスタを更新
して他の実レジスタの設定を行ない（ステップ・５１７
）　　ステップＳ１３に戻る。また、ステップＳ１６の
結果がＮＯの場合には、割付は失敗であるとして処理を
終了する。

以上のような手順により、実レジスタの割付は処理を行
なう。

さて、再び第３図に戻り、ステップＳ７が終了すると、
即ち第５図において説明した処理が終了すると、各仮想
レジスタの色付け、即ち実レジスタの割付けができたか
否かの判断を行なう（ステップＳ８）。第５図において
、ステップＳ１５の結果、処理を終了した場合には、ス
テップＳ８の結果はＹＥＳとなり、レジスタ割付は処理
を終了する。また、第５図において、ステップＳ１６の
結果、処理を終了した場合には、ステップＳ８の結果は
ＮＯとなり、従来同様の実レジスタを節約した実レジス
タ割付けの処理を行ない（ステップＳ９）、処理を終了
する。

ここで、ステップＳ８における判断の必要性について説
明を行なう。

第６図に、色付けに係る説明図を示す。

先ず、ここでは、２つの実レジスタが割付は用として用
意されているものとする。そして、仮想レジスタが３つ
、即ちノードＡ、Ｂ、Ｃが存在し、ノードＡ、Ｂ、ノー
ドＡ、Ｃが干渉している（エツジで結ばれている）もの
とする。

以上のような状態で（ア）に示すように、例えば、ノー
ドＢ、Ｃ，，Ａの順番で色付けを行なったものとする。

ノードＢは第１の実レジスタ（色１）で色付けを、ノー
ドＣは冗長に第２の実レジスタ（色２）で色付けを行な
ったものとする。この場合、ノードＡに色付けを行なお
うとした場合、第３のレジスタが必要となる。即ち、ノ
ードＡには、色１．２の何れでも色付けを行なうことが
できないためである。このような色付けの失敗に対処す
るためにステップＳ８が設けられている。

ちなみに、（イ）に示すように、ノードＢ。

Ｃ，Ａの順番で色付けを行なう場合、ノードＢに色ｌ、
ノードＣに従来同様節約して色１を色付けた場合、ノー
ドＡは色２で色付けすることができる。この場合は、色
付は成功である。

さて１．第１図に戻って、以上説明したように実レジス
タの割付けを行なうことにより、実レジスタｒｏ　、ｒ
ｌ　ｌ　ｒ２の３つが各仮想レジスタに割付けられる。

そして、この機械語に最適化処理を施すと、（イ）に示
すように命令の並び換えを行なうことができ、パイプの
乱れを解消することができる。

第７図に、実レジスタの構成説明図を示す。

実レジスタが３２本存在し、この３２本がその用途によ
り４つに区分けされているものとする。

そして、割付は候補として用いることのできる実レジス
タは実レジスタｒ０〜ｒ２１１の２９本であるものとす
る。実レジスタｒ２９〜ｒ３１は特殊レジスタで、その
使用目的が限定されているものである。実レジスタｒｏ
”ｒａａの内訳は、そのコストにより３つに分類される
。先ずコストの高い実レジスタｒ４〜ｒ＋ｓ、コストの
中程度の実レジスタｒ　ｏ　”　ｒ　ｓそしてコストの
安い実レジスタｒ’ｌｌｌ〜ｒｉｇである。

本発明では、コストの安い実レジスタから順に割付けを
行なうものとする。即ち、実レジスタｒ　　１６．　ｆ
”１７＋　　”’　　ｒ　２ａ＋　　ｒ　ｓ　　、　　
・・・　ｒｏ　　、　　ｒａ　　、　　・・・ｒ＋ｓの
順である。

以上のような順序で、実レジスタを割付ける訳だが、各
仮想レジスタに割付けを行なう場合、毎回実レジスタｒ
’＋ｓを候補として上げるのでなく。

１回目の割付けは実レジスタｆ”ｔａ、２回目は実レジ
スタｒａｔ、そして４回目は実レジスタｒ１９を初めに
候補として上げ、５回目以降は再び実レジスタｒ１６に
戻るといった繰返しを行なう、この場合は冗長度４（４
回繰返すと元に戻る）の場合で、これは適宜変更するこ
とができる。

なお、１回目の割付けはｒ１８＋　・・・ｒ２１１１ｒ
３・・・　２回目の割付けはｒ’　＋７１・・・ｒ”ｚ
ａ、ｒ＋ａ＋ｒ、、＊＊＊　　３回目はｒ’　＋８．”
’　ｒ　２８．ｒ’　＋８＋　ｒ’　ｌ？＋ｒ　ｓ　ｐ
　・・・といった順番となる。

（発明の効果）以上説明した本発明のバイブライン対応の実レジスタ割
付は方式は、実レジスタを極端に節約して仮想レジスタ
に割付けるといったことがないため、パイプライン対応
命令再配置の最適化処理を行なった場合、命令が並び換
わる確率が高くなる。このため、パイプの乱れ等の発生
を極力防止することができ、高速で実行することのでき
る実行形式プログラムを生成することができる。

【図面の簡単な説明】

第１図は本発明に係るコンパイラの動作説明図、第２図
は従来のコンパイラの動作説明図、第３図は本発明の方
式の動作を説明するフローチャート、第４図は擬似コー
ドに含まれる仮想レジスタの使用状況の一覧、第５図は
実レジスタ冗長割付けの詳細なフローチャート、第６図
は色付けに係る説明図、第７図は実レジスタの構成説明
図である。ｒ０〜ｒ３１・・・実レジスタ、ＶＲＩ−ＶＨ２−・・仮想レジスタ。第３図

Claims

【特許請求の範囲】

プログラムの命令に使用されるレジスタを割り付けた後
に、パイプライン対応のために前記命令の再配置を行な
い、前記複数命令を並行に実行させて演算処理する場合
において、前記演算処理中の所定のタイミングで、前記
複数の命令により同時に使用されるレジスタの数を示す
干渉数が、前記レジスタの全数以下のとき、並行に実行
される前記各命令に対して個別の前記レジスタを割付け
ることを特徴とするパイプライン対応のレジスタ割付け
方式。