レジスタ割り当て数の決定方法

トップ :: G 物理学 :: G06 計算;計数

【発明の名称】	レジスタ割り当て数の決定方法
【発明者】	【氏名】太田智也
【要約】	【課題】レジスタスタックを持つアーキテクチャにおいて、関数呼び出しの末端関数実行時に余るレジスタを有効に活用する。【解決手段】従来のレジスタ割り当て処理の実行後に、関数の呼び出し関係と必要レジスタ数を調べ、未使用レジスタスがある場合は、それらのレジスタを、他の関数実行時レジスタ不足が起らない範囲で、再割り当てを行なう。

【特許請求の範囲】
【請求項１】最適化コンパイラにおいてレジスタ割り当て数を決定する処理方法であって、a) 各部分プログラムに対して、必要レジスタ数が最小になるようにレジスタを割り当てるステップとb) コールグラフを作成するステップとc) コールグラフのある経路で未使用レジスタがある場合に、未使用レジスタの再割り当てを行なうステップ、からなるレジスタ割り当て数の決定方法。
【請求項２】請求項１のレジスタ割り当て数の決定方法であって、ステップc)での未使用レジスタの管理に、レジスタの集合を利用するレジスタ割り当て数の決定方法。
【請求項３】プログラムの部分に対して利用可能なレジスタを制限できる機能を有するアーキテクチャ向けの最適化コンパイラにおいてレジスタ割り当て数を決定する処理方法であって、請求項目1の各ステップからなるレジスタ割り当て数の決定方法であって、レジスタ数の管理にプログラム部分が利用可能なレジスタ数を利用するレジスタ割り当て数の決定方法。
【請求項４】請求項１のレジスタ割り当て数の決定方法を利用して処理を行なうコンパイラ。
【請求項５】請求項１のレジスタ割り当て数の決定方法の実装を格納したメディア。

【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は最適化コンパイラにおけるレジスタ割り当ての適用方法に関し、特に、コンパイラにおける他の最適化処理の適用向上を目的としたレジスタ割り当て数の決定方法に関するものである。
【０００２】
【従来の技術】近年の多くのコンピュータアーキテクチャは、大量のレジスタを装備しているものがある。また、そのうちのいくつかのアーキテクチャでは、レジスタをスタックとして利用するレジスタスタックを備えている。インテル社製のプロセッサでは、一部のレジスタに対してレジスタスタックを備えている。このレジスタスタックの構成は、「Intel、IA－64 Application Developer's Architecutre Guide、1999」の4.1節に記載されており、その部分を参照して、本明細書の一部とする。
【０００３】コンパイラのレジスタ割り当て技術は、主に、レジスタスタック機能を備えないアーキテクチャを対象に発展してきた。レジスタ割り当て手法は、大きく２つに分類できる。その一つが、プログラムのある決まった範囲、例えば、手続きやループ等に対して、できるだけ少ない数のレジスタを割り当てることを目的とした手法(手法A)である。この様な手法は、「中田育男、コンパイラの構成と最適化、朝倉書店、1999」の12.5節で論じられている。その部分を参照して本明細の一部とする。これらの手法では、レジスタ割り付け単位に対して効率のよい割り付けを行なえるが、必ずしもプログラム全体などより大きな単位で最適である保証はない。また、レジスタ割り付け対象部分間でのレジスタ割り付け情報の受け渡しがないため、プログラムを実行するアーキテクチャで利用できるレジスタを最大に利用すること難しい。
【０００４】一方で、「Vatsa Santhanam他、Register allocation across procedure andmodule boundaries.、SIGPLAN90 」などでは、レジスタ割り当て前に手続き間解析を行ない、その情報を元に、手続きを越えた大きな単位でレジスタ割り当てを行なう手法(手法B)が提案されている。この方法では、プログラム全体での変数の情報を収集した上でレジスタ割り付けを行なうため、各手続きに対して、効率善くレジスタを割り付けることが可能となる。
【０００５】コンパイラで利用されるプログラム解析情報の一つとして、関数あるいは手続き間の呼び出し関係の情報がある。そして、この情報の表現技術の一つとして、コールグラフがある。コールグラフとは、各関数をグラフのノードとし、関数の呼び出し元から、呼び出し先へエッジをつなげたグラフ構造である。コールグラフに関しては、「D.F.Jerding et. al、Visualizing interactions in programexecutins.、ICSE97」で詳しく述べられている。その部分を参照して本明細の一部とする。
【０００６】
【発明が解決しようとする課題】従来のレジスタ割り付け手法Aでは、プログラム全体のレジスタ割り当て終了時点で、物理レジスタが余ることがある。しかし、プログラムに対しより多くのレジスタを割り当てた方が、他の最適化の適用を促進し、プログラムの実行性能が向上する可能性がある。
【０００７】また、あらかじめ必要レジスタ数に加えて最適化用のレジスタを割り当ててしまう方法を取ると、残りのプログラム部分に対するレジスタ割り当て時に、レジスタ不足が生じ、レジスタの内容の退避・復帰コードが作成され、却ってプログラムの実行性能を悪化させる場合が発生する。
【０００８】従来のレジスタ割り付け手法Bでは、レジスタ割り付けに先立ち、プログラムの各変数のライブ情報などを手続き間に跨って行なう必要があり、解析にかなりの時間を要する。
【０００９】本発明の目的は、プログラム全体で必要となるレジスタ数が全レジスタ数より少なくなる場合に、余りのレジスタをプログラムの各部に再割り当てすることで、手続き間の解析に要する時間を低くおさえながら、レジスタを有効利用する方法を提供することである。
【００１０】
【課題を解決するための手段】上記の目的は、従来のレジスタ割り付け処理の適用後に、利用可能レジスタに余りがある場合に、それらのレジスタの再割り当て処理を行なうことで達成される。
(1) プログラムの処理単位に対してレジスタ割り当てを行なう。
(2) 未割り当てのレジスタが残っている場合のみ、以下の処理を行なう。
(3) プログラム中の手続きの依存関係を表すコールグラフを作成する。
(4) 未割り当てレジスタを、再割り当てする。
(5) 必要ならば、処理(4)を繰り返す。
【００１１】この処理により、未割り当てのレジスタ数を最小にできるため、他の最適化処理の適用を促進させ、プログラムの高速な実行が可能となる。
【００１２】
【発明の実施の形態】以下、本発明の1実施例を図面を用いて説明する。
【００１３】なお、以下の説明により、本発明の適用が限定されるものではない。
【００１４】図１は、本発明の適用対象である計算機システムを表す概略構成図である。本発明であるレジスタ割り当て数の決定方法は、最適化コンパイラに実装され、主記憶102もしくはディスク装置103に格納され、CPU101で実行される。
【００１５】図２は、本発明が実装される最適化コンパイラの構成を示している。プログラム201は、最適化コンパイラ202へ入力され、例えば図１で示される計算機で実行されるオブジェクトコード206に変換される。最適化コンパイラ202は、入力されたプログラム201に対して、構文解析203などの前処理を行ない、中間語204を生成する。その後、中間語204に対して、最適化処理205を行ない、オブジェクトコード206を生成する。
【００１６】図３は、最適化処理部205内のレジスタ割り当て部301の構成を示したものである。
【００１７】レジスタ初期割り当て部302では、入力プログラム305をレジスタ割り当て単位にプログラム片に区切り、そのプログラム片に対してレジスタ割り当てを行なう。これにより、各関数での最小必要レジスタ数等のレジスタ割り当て情報306を求める。
【００１８】コールグラフ作成部303では、プログラム全体に対する関数の呼び出し関係を表すコールグラフ307を作成する。
【００１９】レジスタ再割り当て部304では、レジスタ割り当て情報306、コールグラフ307を用いて、未使用レジスタを適当な関数に割り当てる。なお、処理302、303で行なう各処理は、すべて既存の技術をそのまま利用する。
【００２０】以下では、本発明における特徴的な処理である、レジスタ再割り当て部304について説明する。
【００２１】図４は、図３におけるレジスタ再割り当て部304の動作をフローチャートを用いて表したものである。レジスタ再割り当て部への入力は図３における、レジスタ割り当て情報306およびコールグラフ307である。以下の説明では、コールグラフのノードのうち呼び出し元関数のノードがないノードをルートノード、呼び出し先関数のノードがないノードをリーフノードと呼ぶ。
【００２２】処理401では、末尾ノード集合とその経路での未使用レジスタ数の合計を求める。なお、末尾ノードとは、リーフノードであり、かつ、ルートノードからそのリーフノードまでに循環路がないノードのことである。
【００２３】処理402では、処理401で求めた未使用レジスタを割り当てる候補となる関数の集合である再割り当て対象関数集合を求める。
【００２４】処理403では、処理401で求めた未使用レジスタを処理402で求めた候補関数に再割り当てを行ない、新たなレジスタ割り当て数を求める。
【００２５】処理404では、上記の処理を、レジスタの割り当て数が変化しなくなるまで繰り返す。ただし、この繰り返しは、コンパイル時間などの要因によっても打ち切ることができる。
【００２６】図５は、処理401の処理の1例を示すフローチャートである。
【００２７】処理501により、各リーフノードに対して、処理502から処理505の処理を適用する。
【００２８】処理502では、ルートノードから、処理対象のリーフノードに至る経路に循環路がある場合、その経路を処理対象からはずしている。これは、コールグラフに循環路が現れた場合、リーフノードの関数の実行時における必要レジスタ数を特定できないためである。
【００２９】処理503では、リーフノード実行時における未使用レジスタ数を求める。これは、ルートノードからリーフノードまでの経路上のノード(関数)の必要レジスタ数の合計を、全レジスタ数から引くことで求めることができる。ただし、0以下の場合は、0とする。
【００３０】処理504では、未使用レジスタが無い場合は、その経路を処理の対象からはずしている。
【００３１】処理505では、未使用レジスタがある場合に、その経路を覚えておくために、処理中のリーフノードを、末尾ノード集合に登録する。処理506、処理507では、そのノードがレジスタ再割り当て対象か否かを判別するために、処理507であらかじめすべてのノードに印をつけておき、条件を満たさないものを、処理506で除いている。
【００３２】図６は、処理402の処理の1例を示すフローチャートである。処理601により、各関数について、処理602、処理603が適用される。処理602では、処理対象の関数に対応するすべてのノードに、処理505でつけた印があるか確認する。もし、1つでも印のないノードがあった場合、その関数は、再割り当て対象からはずすため、処理603で、その関数に対応するすべてのノードにおける印を取り除く。また、処理604、605で、印を取り除くノードが末尾ノード集合に含まれる場合は、そのノードを集合から取り除く。もし、すべての対応するノードに印があった場合は、処理606で、再割り当て対象関数集合に登録する。
【００３３】図７は、処理403の処理の1例を示すフローチャートである。
【００３４】処理701、702では、すべての末尾ノードについて、ルートノードからそのノードまでの経路上にある再割り当て対象ノードに対して、その経路に対応する未使用レジスタを、割り振る。なお、ここでは、未使用レジスタを再割り当て対象ノードに均等に割り振るが、プロファイル情報等が利用でき、関数に対して実行頻度等で優先度をつけることが可能な場合は、その優先度の割合にしたがって割り振り数を設定することも可能である。
【００３５】処理703、704では、すべての再割り当て候補関数に対して、新たなレジスタ割当数を求める。
【００３６】もし、対応するコールグラフのノードが複数ある場合は、本実施例では、それそれのノードの割り振り値の最小値を選択する。これにより、複数の呼び出し点がある関数に対する割り当てに対しても、割り当て数が全レジスタ数を越えることを防ぐことが可能となる。また、本処理は、コールグラフの特定の経路を優先させたい場合は、その経路に含まれるノードの値を選択することなどが可能である。最後に、割り振り値と、現在のレジスタの割り当て数を足したものを新たなレジスタ割り当て数とする。
【００３７】以上のレジスタ割り当て数決定方法を簡単な例題に適用して、その機能と効果を確認する。
【００３８】図８に示す関数をもつプログラムを例とする。列801は、関数の名称である。ここでは、AからHまでの8個の関数が定義されているとする。列802は、関数が呼び出す関数の集合である。例えば、関数A は、関数B、D、F、G を呼び出す。これらのプログラムに対して、処理302により、レジスタ割り当てを行なった結果、各関数に対するレジスタ割当数が列803に示す数となるとする。なお、このプログラムが実行される計算機にはレジスタが100個あるものとする。
【００３９】処理303により作成される、このプログラムに対するコールグラフを図9に示す。このコールグラフでは、ルートノードは、901、リーフノードは、903、905、908、912である。
【００４０】以下に、レジスタ再割り当て処理部305の処理例を示す。まず、処理401が適用される。そのため、各リーフノードに対して、処理502から処理505が適用される。リーフノード903の処理では、ルートノード901との経路上に循環路がなく、また、ノード903の関数の実行時に必要なレジスタ数は85(50+30+5)であるため、未使用レジスタが15個ある。そのため、ノード903は、末尾ノード集合に登録さる。リーフノード(911の処理では、経路上にノード909(関数G)の呼び出しの循環路があるため、経路上のすべてのノードから再割り当て対象関数の印を取り除く。同様にして、他のリーフノードに対して適用した結果を図10に示す。なお、図中のノードの右肩にある＊印は、再割り当て対象関数のマークを示し、括弧の中の数字はそのリーフノードに至る経路での未使用レジスタ数を示している。また、この時点での末尾ノード集合には、ノード1003、1005、1008が登録されている。
【００４１】次に、図１０で示される結果に対して、図６で示される処理が適用される。関数Dに対するノードは、ノード1004と1011の2個所有り、ノード911は印を持たないため、1004の印も除かれる。関数Cでは、対応するノード1003、1008に共に印がついているので、再割り当て対象関数集合に加えられる。同様に、他の関数に対する処理を行なうと、図１１の結果が得られる。また、作成される再割り当て対象関数集合には、関数B、C、Fが登録される。
【００４２】次に、図１１の結果に対して、図７で示される処理が適用される。図５で示した処理により、末尾ノード集合として、ノード1103、1108が求められている。ノード1103の処理では、未使用レジスタが15個あり、経路上の再割り当てマークがついているのは、ノード1102、1103なので、ノード1102に7個、ノード1103に8が割り振られる。同様にノード1108の処理では、ノード1106に3、ノード1107に3、ノード1108に4が割り振られる。次に、処理703、704により、再割り当て候補関数の最終的な再割り当て値を求める。処理704より、関数Bの最終的な割り振り値は、最小値の3となり、新たな割当数は、33となる。また、関数Cに対する割当数は9、関数fに対する割当数は8となる。
【００４３】以上で、処理401から処理403が終了する。処理404によりこの処理を繰り返すと、2度目は割当て数に変化が起らないので、これで処理が終了する。
【００４４】図１２は、この例題に対する最終的結果を示している。列1203は、本処理の適用により得られるレジスタの割当数を示している。この結果は、適用前に使用レジスタ数が全レジスタ数より少なかった経路についてはそれを保障し、また、使用レジスタ数が全レジスタ数より多かった経路についても、処理前の必要最小値を保証している。
【００４５】
【発明の効果】本発明によれば、従来のレジスタ割り付け処理では、未使用となるレジスタを適当な関数に割り当てることができき、それにより、他の最適化の適用が促進され、より多くの最適化が適用可能となる。これにより、計算機プログラムの実行時間を短縮できる。

【出願人】	【識別番号】０００００５１０８【氏名又は名称】株式会社日立製作所
【出願日】	平成１３年４月１８日（２００１．４．１８）
【代理人】	【識別番号】１０００７５０９６【弁理士】【氏名又は名称】作田康夫
【公開番号】	特開２００２－３１２１７９（Ｐ２００２－３１２１７９Ａ）
【公開日】	平成１４年１０月２５日（２００２．１０．２５）
【出願番号】	特願２００１－１１９０２１（Ｐ２００１－１１９０２１）