JPH04241630A - グラフ色塗りによるレジスタ割り付け最適化方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、与えられたソースプロ
グラムから目的プログラムを生成するコンパイラにおけ
る最適化方式に関し、特に並列に動作する複数の演算部
を持ち各演算部で実行される命令が目的プログラムの生
成時点で確定していることを前提とするプロセッサに対
するコンパイラにおける最適化方式に関し、とりわけ目
的プログラムの生成過程でソースプログラムの展開によ
り生成された中間コード列を対象としてレジスタを効率
良く割り付けるためにグラフ色塗りの手法を採用するグ
ラフ色塗りによるレジスタ割り付け最適化方式に関する
。

【０００２】

【従来の技術】単一の演算部からなりその演算部で実行
される命令が目的プログラムの生成時点で確定している
ことを前提とするプロセッサに対するコンパイラで、中
間コード列中の変数に対してレジスタを割り付ける方式
として、グラフ色塗りの手法を用いる方式が知られてい
る。

【０００３】この方式では、次のような手順で処理が行
われる。

【０００４】■　　各変数が有効なデータを保持してい
る区間をグラフのノードとして表す。

【０００５】■　　２つの区間に重複があることにより
対象となっている２個の変数に同一のレジスタを割り付
けることが不可能な場合には、対応する２個のノードを
グラフの辺で結ぶ。

【０００６】■　　以上の方法を用いて全ての区間につ
いて重複を解析し、その結果得られたグラフにおいて、
互いに辺で結ばれたノードが同一の色とならないように
色を割り当てる。

【０００７】■　　同一の色が割り当てられた複数のノ
ードに対応する複数の変数に対して１本のレジスタを割
り付ける。

【０００８】なお、上述の方式において、ノードにあら
かじめ優先度を与えることにより、上述のレジスタ割り
付けの効果をさらに高める方式がある。この方式では、
あるノードの優先度としてそのノードに対応する変数が
ソースプログラム中で使用される頻度が用いられ、上述
の手順■においてレジスタが割り付けられる段階で優先
度の高いノードから順にレジスタが割り付けてられてい
る（このように従来技術における「優先度」はノードに
対して付与されるものであった）。

【０００９】並列に動作する複数の演算部を持ち各演算
部で実行される命令が目的プログラムの生成時点で確定
していることを前提とするプロセッサに対するコンパイ
ラにおいても、従来のグラフ色塗りによるレジスタ割り
付け最適化方式は、単一の演算部からなるプロセッサに
対するコンパイラにおける上述の方式がそのまま適用さ
れて実現されていた。

【００１０】

【発明が解決しようとする課題】複数の演算部を持つプ
ロセッサに対するコンパイラにおける従来のグラフ色塗
りによるレジスタ割り付け最適化方式では、単一の演算
部からなるプロセッサに対するコンパイラにおける上述
の方式がそのまま適用されており、２つの区間に重複が
ない限りノードを結ぶ辺は作成されないので、ソースプ
ログラム上での位置が近接している２つの変数であって
もそれらの変数に対応する２つの区間に重複がなければ
同一のレジスタが割り付けられ得る。

【００１１】ところで、複数の演算部を持つコンパイラ
における命令の並列化処理では、ソースプログラム上で
の位置が近接している命令は可能な限り並列に実行する
ような配置が試みられる。このときに、これらの命令に
含まれる変数に同一のレジスタが割り付けられると、こ
れらの変数を使用している命令を並列に実行できない。

【００１２】したがって、上述した従来のグラフ色塗り
によるレジスタ割り付け最適化方式では、その方式が適
用されるコンパイラにより生成される目的プログラムの
実行性能が悪くなるという問題点があった。

【００１３】本発明の目的は、上述の点に鑑み、高い実
行性能を有する目的プログラムを生成することができる
グラフ色塗りによるレジスタ割り付け最適化方式を提供
することにある。

【００１４】

【課題を解決するための手段】本発明のグラフ色塗りに
よるレジスタ割り付け最適化方式は、並列に動作する複
数の演算部を持ち各演算部で実行される命令が目的プロ
グラムの生成時点で確定していることを前提とするプロ
セッサに対する目的プログラムの生成過程で中間コード
列に対してグラフ色塗りの手法を用いてレジスタ割り付
けの最適化を行うコンパイラにおいて、中間コード列中
の「変数が有効なデータを保持している区間」に関して
重複の有無および同一のレジスタを割り付けることによ
り命令の並列化を損なう可能性を判断し重複の有無およ
び並列化を損なう可能性の高さに応じて評価値を算出す
るデータコンフリクト解析手段と、このデータコンフリ
クト解析手段による解析に基づいて「変数が有効なデー
タを保持している区間」に対応するノードを辺で結びそ
の辺に評価値を付加してグラフを作成するグラフ作成手
段と、このグラフ作成手段により辺で結ばれたノードに
利用可能なレジスタ数に応じた数の別の色を割り当てる
グラフ色塗り手段と、このグラフ色塗り手段により同一
の色が割り当てられたノードに対応する変数に同一のレ
ジスタを割り付けるレジスタ割り付け手段とを有する。

【００１５】

【作用】本発明のグラフ色塗りによるレジスタ割り付け
最適化方式では、データコンフリクト解析手段が中間コ
ード列中の「変数が有効なデータを保持している区間」
に関して重複の有無および同一のレジスタを割り付ける
ことにより命令の並列化を損なう可能性を判断し重複の
有無および並列化を損なう可能性の高さに応じて評価値
を算出し、グラフ作成手段がデータコンフリクト解析手
段による解析に基づいて「変数が有効なデータを保持し
ている区間」に対応するノードを辺で結びその辺に評価
値を付加してグラフを作成し、グラフ色塗り手段がグラ
フ作成手段により辺で結ばれたノードに利用可能なレジ
スタ数に応じた数の別の色を割り当て、レジスタ割り付
け手段がグラフ色塗り手段により同一の色が割り当てら
れたノードに対応する変数に同一のレジスタを割り付け
る。

【００１６】

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

【００１７】図１は、本発明のグラフ色塗りによるレジ
スタ割り付け最適化方式の一実施例の構成を示すブロッ
ク図である。本実施例のグラフ色塗りによるレジスタ割
り付け最適化方式は、二次記憶装置（図示せず）に格納
されているソースプログラム１と、コンパイラ２と、コ
ンパイルされて二次記憶装置に格納される目的プログラ
ム３とを含んで構成されている。

【００１８】コンパイラ２は、二次記憶装置からソース
プログラム１を取り込み構文解析および意味解析を行い
解析結果を中間コード列５（図２参照）に展開するソー
スプログラム解釈部２１と、その中間コード列５に対し
てコード短縮等のための最適化処理を施す最適化部２２
と、複数の演算部の各演算部で実行される全ての命令を
一列に並べた形の直列アセンブリ命令列を生成する直列
アセンブリ命令列生成部２３と、直列アセンブリ命令列
の並列化を行い目的プログラム３となる並列アセンブリ
命令列を生成する並列アセンブリ命令列生成部２４と、
目的プログラム３を二次記憶装置に出力する目的プログ
ラム出力部２５とを含んで構成されている。

【００１９】最適化部２２内のレジスタ割り付け処理部
４は、データコンフリクト解析手段４１と、グラフ作成
手段４２と、グラフ色塗り手段４３と、レジスタ割り付
け手段４４とを含んで構成されている。このレジスタ割
り付け処理部４によって、本実施例のグラフ色塗りによ
るレジスタ割り付け最適化方式の中枢の処理が実現され
る。

【００２０】図２および図３はレジスタ割り付け処理部
４の処理を説明するための図であり、図２は中間コード
列５の一例を示す図であり、図３はグラフ作成手段４２
により作成されグラフ色塗り手段４３による「グラフ色
塗り」の対象となるグラフ６の一例を示す図である。

【００２１】次に、このように構成された本実施例のグ
ラフ色塗りによるレジスタ割り付け最適化方式の動作に
ついて説明する。

【００２２】レジスタ割付け処理部４では、次のような
処理が行われる。

【００２３】データコンフリクト解析手段４１は、中間
コード列５を参照して各変数が有効なデータを保持して
いる区間を検出し、これらの区間相互に重複があるか否
かを解析する。重複がある場合には、その重複を示す評
価値として無限大を算出する。さらに、このような重複
がなくても、後のレジスタ割り付けでこれらの区間に対
応する変数に同一のレジスタが割り付けられると並列性
を損なう可能性があるか否かを解析し、その可能性があ
る場合にはその可能性の大きさに応じた評価値を算出す
る。

【００２４】グラフ作成手段４２は、次のようにしてグ
ラフ６を作成する。すなわち、データコンフリクト解析
手段４１によって解析された「変数が有効なデータを保
持している区間」に対してグラフ６のノードを割り当て
る。また、データコンフリクト解析手段４１によって「
相互に重複がある」と解析された２つの区間に対応する
２つのノードを辺で結び、データコンフリクト解析手段
４１により算出された評価値である無限大（重複を示す
評価値。図３中では「ｉｎｆ」で示す）をその辺に付加
する。また、相互に重複がない２つの区間であっても、
同一のレジスタが割り付けられると並列性を損なう可能
性がある２つの区間に対応する２つのノードを辺で結び
、データコンフリクト解析手段４１により算出された評
価値（並列性を損なう可能性に応じた評価値）をその辺
に付加する。

【００２５】グラフ色塗り手段４３は、グラフ作成手段
４２によって作成されたグラフ６の辺に付加された評価
値を優先度として用い、以下のようにグラフ６に対して
グラフ色塗りを行う。最初に、全ての辺を用いてグラフ
色塗りを行い（辺で結ばれたノードに別の色を割り当て
ることを全ての辺について行う）、必要な色の数が利用
可能なレジスタ数以下であるか否かを判断する。必要な
色の数が利用可能なレジスタ数以下である場合には、グ
ラフ色塗りを完了する。必要な色の数が利用可能なレジ
スタ数以下でない場合には、評価値の小さい（優先度の
低い）順に辺をグラフ６から除去して残りの辺を用いて
グラフ色塗りを行い、必要な色の数が利用可能なレジス
タ数以下になるまで以上の処理を繰り返す。

【００２６】レジスタ割り付け手段４４は、グラフ色塗
り手段４３によるグラフ色塗りの結果として同一の色が
与えられたノードに同一のレジスタを対応させることに
より、各変数にレジスタを割り付ける。

【００２７】次に、レジスタ割り付け処理部４によるレ
ジスタ割り付け処理を具体例を用いて説明する（図２お
よび図３参照）。

【００２８】図２に示す中間コード列５に対して、グラ
フ作成手段４２は、図３に示すようなグラフ６を作成す
る（図３では、簡単のために、変数Ａ，ＸおよびＹに関
する部分のみを示す）。グラフ６中のノード６１は変数
Ａが有効なデータを保持している区間５１（図２参照）
に対応するノードであり、ノード６２は変数Ｘが有効な
データを保持している区間５２に対応するノードであり
、ノード６３は変数Ｙが有効なデータを保持している区
間５３に対応するノードである。

【００２９】中間コード列５において、変数Ａが有効な
データを保持している区間５１と変数Ｘが有効なデータ
を保持している区間５２とには重複がある。そこで、グ
ラフ作成手段４２は、ノード６１とノード６２とを辺６
４で結び、データコンフリクト解析手段４１により算出
された評価値（重複を示す評価値）である無限大（ｉｎ
ｆ）を辺６４に付加する。

【００３０】変数Ａが有効なデータを保持している区間
５１と変数Ｙが有効なデータを保持している区間５３と
についても重複があるので、ノード６１とノード６３と
は辺６６で結ばれ、辺６６には評価値として無限大（ｉ
ｎｆ）が付加される。

【００３１】変数Ｘが有効なデータを保持している区間
５２と変数Ｙが有効なデータを保持している区間５３と
には重複はないが、中間コード命令列５（したがって、
ソースプログラム１でも）において近接しているので、
同一のレジスタを割り付けると並列性を損なう可能性が
高い。したがって、データコンフリクト解析手段４１は
その可能性の高さに応じた評価値（ここでは「２」とす
る）を与える。この結果、グラフ作成手段４２は、ノー
ド６２とノード６３とを辺６５で結び、辺６５に評価値
として２を付加する。

【００３２】グラフ色塗り手段４３およびレジスタ割り
付け手段４４は、次のようにグラフ色塗りおよびレジス
タ割り付けを行う（図４参照）。

【００３３】グラフ６の構成に基づき、グラフ色塗り手
段４３は、辺６４〜６６で結ばれているノード６１〜６
３には全て別の色を割り当てる。したがって、レジスタ
割り付け手段４４はレジスタが３本以上利用可能な場合
には各ノード６１〜６３に別々のレジスタを割り付ける
。

【００３４】しかし、利用可能なレジスタが２本しかな
い場合には、グラフ色塗り手段４３は、付加された評価
値の小さい辺６５をグラフ６から除去し、ノード６２と
ノード６３とに同一の色を割り当て、さらにこれとは別
の色をノード６１に割り当てる。この場合には、レジス
タ割り付け手段４４はノード６２とノード６３とに同一
のレジスタを割り付ける（これにより、並列性を損なう
可能性が生じるが、利用可能なレジスタ数の制限からや
むをえない）。

【００３５】以上の処理により、利用可能なレジスタ数
に余裕がある範囲で、並列性を生かしたレジスタ割り付
けを行うことができる。

【００３６】

【発明の効果】以上説明したように本発明は、２つのノ
ードに同一のレジスタを割り付けることによって命令の
並列化処理が妨げられる可能性がある場合に、ノードに
対応する区間に重複がない場合でもこれらのノードを辺
で結ぶことにより、アセンブリ命令列（目的プログラム
）の並列性を高めることができる。また、グラフの辺に
優先度を持たせることにより、利用可能なレジスタ数が
不足する場合にも対処することができる。

【００３７】以上のことにより、単純なグラフ色塗りの
手法によるレジスタ割付け（単一の演算部からなるプロ
セッサに対するコンパイラにおけるグラフ色塗りの手法
を複数の演算部からなるプロセッサに対してそのまま適
用した場合のグラフ色塗りによるレジスタ割り付け）に
よって生成される目的プログラムの実行性能以上の実行
性能を有する目的プログラムを生成することができると
いう効果がある。

【図面の簡単な説明】

【図１】本発明の一実施例の構成を示すブロック図であ
る。

【図２】図１中のソースプログラム解釈部により生成さ
れる中間コード列の一例を示す図である。

【図３】図１中のグラフ作成手段により作成されるグラ
フの一例を示す図である。

【符号の説明】

１　　ソースプログラム ２　　コンパイラ ３　　目的プログラム ４　　レジスタ割り付け処理部 ５　　中間コード列 ６　　グラフ ２１　　ソースプログラム解釈部 ２２　　最適化部 ２３　　直列アセンブリ命令列生成部 ２４　　並列アセンブリ命令列生成部 ２５　　目的プログラム出力部 ４１　　データコンフリクト解析手段 ４２　　グラフ作成手段 ４３　　グラフ色塗り手段 ４４　　レジスタ割り付け手段 ５１〜５３　　区間 ６１〜６３　　ノード ６４〜６６　　辺

Claims (1)

【特許請求の範囲】
1. 【請求項１】　　並列に動作する複数の演算部を持ち各
   演算部で実行される命令が目的プログラムの生成時点で
   確定していることを前提とするプロセッサに対する目的
   プログラムの生成過程で中間コード列に対してグラフ色
   塗りの手法を用いてレジスタ割り付けの最適化を行うコ
   ンパイラにおいて、中間コード列中の「変数が有効なデ
   ータを保持している区間」に関して重複の有無および同
   一のレジスタを割り付けることにより命令の並列化を損
   なう可能性を判断し、重複の有無および並列化を損なう
   可能性の高さに応じて評価値を算出するデータコンフリ
   クト解析手段と、このデータコンフリクト解析手段によ
   る解析に基づいて「変数が有効なデータを保持している
   区間」に対応するノードを辺で結びその辺に評価値を付
   加してグラフを作成するグラフ作成手段と、このグラフ
   作成手段により辺で結ばれたノードに利用可能なレジス
   タ数に応じた数の別の色を割り当てるグラフ色塗り手段
   と、このグラフ色塗り手段により同一の色が割り当てら
   れたノードに対応する変数に同一のレジスタを割り付け
   るレジスタ割り付け手段とを有することを特徴とするグ
   ラフ色塗りによるレジスタ割り付け最適化方式。