JPH09311792A - レジスタ割り付け方法 - Google Patents

Abstract

(57)【要約】 【課題】既に割り付けられたｃａｌｌｅｅレジスタを有
効利用する。 【解決手段】レジスタの探索を行うときに、ｃａｌｌｅ
ｅレジスタのプロフィット値から関数入口と出口で必要
になる退避・回復コードのコストを引いた値がｃａｌｌ
ｅｒレジスタのプロフィット値よりも大きいかを判定し
（ステップ６０７）、ｃａｌｌｅｅレジスタのプロフィ
ット値から関数入口と出口で必要になる退避・回復コー
ドのコストを引いた値の方が大きい場合に、既に割り付
けられているｃａｌｌｅｅレジスタの中から割り付けら
れるレジスタを探す（ステップ６０８）ようにする。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はコンパイラのレジス
タ割り付け方法に関する。

【０００２】

【従来の技術】ソースプログラムを目的コードに変換す
るコンパイラにおいて、目的コードの実行性能を向上さ
せるための最適化方式は、これまでも数多く開発されて
おり、Ａ．Ｖ．エイホ、Ｒ．セシィ、Ｊ．Ｄ．ウルマン
著「コンパイラ」等で詳しく述べられている。

【０００３】その中の最適化方式の１つとして、ソース
プログラム中で参照されている変数に対し、メモリへの
参照回数を削減し、限られた資源であるレジスタにデー
タを乗せたまま実行を行い、目的コードの実行時間を向
上させるための処理として、レジスタ割り付けと呼ばれ
る処理が存在する。

【０００４】この限られた資源であるレジスタを有効に
割り付けるための様々な方法のうち１つとしてプロフィ
ット値（レジスタを割り付けるときの指標となる）を用
いた割り付け方法がある。

【０００５】プロフィット値を用いた割り付けは、まず
レジスタを２つのクラスに分類することを始める。この
２つの分類により分けられたレジスタの集合をそれぞれ
ｃａｌｌｅｅ退避レジスタ、ｃａｌｌｅｒ退避レジスタ
と呼ぶ。

【０００６】（１）ｃａｌｌｅｅ退避レジスタ レジスタクラスのうち１つであり、呼び出し先の関数で
レジスタの内容を保証しなければならないレジスタのこ
とである。呼び出し先の関数でこのクラスのレジスタを
参照する場合は、関数の入口でレジスタ内容の退避を、
関数の出口でレジスタ内容の回復を行わなければならな
い。したがって、呼び出し元では関数呼び出しを跨って
このクラスのレジスタを割り付けることができる。ｃａ
ｌｌｅｅ退避レジスタを単にｃａｌｌｅｅレジスタと呼
ぶ。

【０００７】（２）ｃａｌｌｅｒ退避レジスタ レジスタクラスのうちの１つであり、呼び出し元の関数
でレジスタの内容を保証しなければならないレジスタの
ことである。つまり、関数呼び出しがある場合呼び出す
直前と呼び出した後にこのクラスのレジスタは内容が変
更されている可能性があるということである。したがっ
て、呼び出し元では関数呼び出しを跨ってこのクラスの
レジスタを割り付けることはできない。関数呼び出しを
跨って生きている変数にこのクラスのレジスタを割り付
けた場合は、関数呼び出しの直前までにレジスタの値を
メモリなどに退避するコードを（この退避を行うことを
セーブすると呼び、セーブを行う参照点をセーブ点と呼
ぶ）、関数呼び出しの直後の値をメモリなどから回復す
るコードを（この回復を行うことをリストアすると呼
び、リストアを行う参照点をリストア点と呼ぶ）生成し
なければならない。ｃａｌｌｅｒ退避レジスタを単にｃ
ａｌｌｅｒレジスタと呼ぶ。

【０００８】この２つのクラスのレジスタ集合に対し
て、変数の参照点で必ずロード・ストア命令を作成する
場合に比べて、レジスタに割り付けることによりどれく
らい得をするかを示すものがプロフィット値である。ｃ
ａｌｌｅｅレジスタに対するプロフィット値をｃａｌｌ
ｅｅプロフィット。ｃａｌｌｅｒレジスタに対するプロ
フィット値をｃａｌｌｅｒプロフィットとそれぞれ呼
ぶ。

【０００９】次に、コストについて説明する。コストと
は、何命令でその処理を完了することができるかを示し
たものである。以下、議論を簡単にするために３つのコ
ストだけを考慮した場合で説明する。

【００１０】（１）ロードコスト あるレジスタにメモリから値を読み込む場合に必要な命
令数。

【００１１】（２）ストアコスト あるレジスタからメモリに値を格納する場合に必要な命
令数。

【００１２】（３）コピーコスト あるレジスタから別のレジスタに値を移動させる場合に
必要な命令数。

【００１３】まず。ｃａｌｌｅｅレジスタを割り付ける
場合のプロフィット値の計算手順について説明する。ｃ
ａｌｌｅｅレジスタは関数呼び出しを跨って参照する場
合、呼び出し先がレジスタの内容を保証しなければなら
ない。したがって、呼び出された先の関数内でこのクラ
スのレジスタを参照する場合は、関数の入口でレジスタ
の内容の退避、つまりメモリへのストア命令を、関数の
出口でレジスタの内容の回復、つまりメモリからのロー
ド命令を生成しなければならない。したがって、ｃａｌ
ｌｅｅレジスタをある関数内で割り付けようとする場合
は、手続きの入口と出口で退避・回復が必要になるの
で、ロードコストとストアコストが必ず必要になる。

【００１４】次に、ｃａｌｌｅｒレジスタを割り付ける
場合のプロフィット値の計算について説明する。ｃａｌ
ｌｅｒレジスタは関数呼び出しを跨って参照する場合、
呼び出し元がレジスタの内容を保証しなければならな
い。したがって、ｃａｌｌｅｅレジスタは呼び出された
関数では、ｃａｌｌｅｅレジスタで必要になる関数入口
と出口での退避・回復は必要ないのでロードコストとス
トアコストは必要ない。しかし、関数呼び出しを跨って
生きている変数に割り付けようとする場合は、レジスタ
のセーブ・リストアが必要になるため、関数の直前の定
義点でセーブのためのストアコストが、関数直後の使用
点でリストアのためのロードコストが必要になる。

【００１５】また、関数の引数や戻り値として参照され
ている場合、それらの参照点では必ず決まったレジスタ
を使わなければならない。このレジスタは通常ｃａｌｌ
ｅｒレジスタになる。したがって、このような文脈で変
数が参照されている場合は、ｃａｌｌｅｅを割り付ける
とこれらの参照点でｃａｌｌｅｅレジスタからｃａｌｌ
ｅｒレジスタへのコピーが必要になるため、コピーコス
トを考慮する必要がある。

【００１６】このようにして、レジスタを割り付ける前
に、各変数が参照されている文脈よりｃａｌｌｅｅプロ
フィットとｃａｌｌｅｒプロフィットを計算しておくこ
とになる。

【００１７】

【発明が解決しようとする課題】上記従来技術では、割
り付け前にｃａｌｌｅｅプロフィットとｃａｌｌｅｒプ
ロフィットを計算しておくため、以下のような問題が発
生する。関数内で既にｃａｌｌｅｅレジスタが割り付け
られた場合は、それ以降に割り付ける変数では関数入口
と出口で必要な退避・回復のコストは、既にｃａｌｌｅ
ｅレジスタが退避・回復されることが決定しているので
考えなくても良いことになる。この点を考慮しないまま
レジスタの割り付けを行うとｃａｌｌｅｅレジスタを割
り付けた方がｃａｌｌｅｒレジスタを割り付けるより良
いような場合でも、ｃａｌｌｅｅプロフィットが関数入
口と出口で必要な退避・回復のコストを含んだままにな
っているので、ｃａｌｌｅｒレジスタが割り付けられる
ことがある。

【００１８】これを図１２を用いて説明する。関数呼び
出し（１２０２）の前後に変数ａの定義（１２０１）と
使用（１２０３）がある場合を例に取る。変数ａは、関
数呼び出しを跨って生きているため、ｃａｌｌｅｒレジ
スタを割り付けた場合には、定義点でストア命令が、使
用点でロード命令が生成されることになる。次に、ｃａ
ｌｌｅｅレジスタを割り付けた場合には、関数の呼出し
先でレジスタの内容が保証されるためメモリの参照をす
ることなく定義点と使用点で値を参照することができ
る。ただし、ｃａｌｌｅｅレジスタがこの関数内で初め
て割り付けられた場合には、関数の入口と出口でレジス
タの値の退避と回復が必要になる。しかし、あるｃａｌ
ｌｅｅレジスタが既に割り付けられており、そのｃａｌ
ｌｅｅレジスタをこの変数に割り付ける場合は、既にそ
のｃａｌｌｅｅレジスタを退避・回復することが決定し
ているので変数ａには、ルモリの参照をすることはなく
値を参照できるｃａｌｌｅｅレジスタを割り付けた方が
よいことになる。

【００１９】上記従来技術の課題は、既に割り付けられ
ているｃａｌｌｅｅレジスタを考慮した割り付けが行え
ないことになる。

【００２０】本発明の目的は、既に割り付けられている
ｃａｌｌｅｅレジスタを考慮した割り付けが行うことに
ある。

【００２１】

【課題を解決するための手段】上記目的は、関数内で割
り付けられたレジスタを記憶しておくテーブルを用意
し、割り付けるレジスタを探すときに、ｃａｌｌｅｅプ
ロフィットから関数入口と出口で必要なコストを引いた
値がｃａｌｌｅｒプロフィットより大きいときに、既に
割り付けられているｃａｌｌｅｅレジスタから割り付け
られるレジスタを探すようにすることで達成することが
できる。

【００２２】

【発明の実施の形態】本発明は、コンパイラにおけるレ
ジスタ割り付け方法に関するものである。

【００２３】以下では、本発明の一実施例を図面を用い
て説明する。なお、これにより本発明が限定されるもの
ではない。

【００２４】図１は、本発明のレジスタ割り付け方法の
一実施例のシステム構成図である。

【００２５】本システムは、ＣＰＵ装置１、メモリ装置
２、入力装置３、表示装置４から構成されている。コン
パイラ１０はＣＰＵ装置１により処理、実行される。コ
ンパイラ１０は、ソースプログラム３０を入力し、幾度
か中間コード４０を生成しながら、最終的に目的コード
５０を生成する。目的コード５０は、実行２０で実行さ
れ結果を表示装置４に表示したり、実行結果６０に結果
を出力する。

【００２６】図２は、コンパイラ１０における処理構成
図である。

【００２７】コンパイラ１０は、中間コード生成部２０
１、中間コード最適化部２０２、レジスタ割り付け部２
０３、目的コード生成部２０７からなる。さらに、レジ
スタ割り付け部２０３は、参照転属性の設定２０４、プ
ロフィットの計算２０５、レジスタ割り付け２０６から
なる。中間コード生成部２０１では、ソースプログラム
を入力し、字句解析と構文解析を行った後中間コード４
０を生成する。中間コード最適化部２０２は、中間コー
ド４０を入力し、いくつかの最適化を行った後中間コー
ド４０を生成する。レジスタ割り付け部２０３は、中間
コード４０を入力し各変数の参照をレジスタの参照また
はメモリからの参照にした中間コード４０を生成する。
目的コード生成部２０７は、中間コード４０を入力しそ
れぞれのマシンで実行させるため目的コード５０を生成
する。

【００２８】レジスタ割り付け部２０３は、参照点属性
の設定２０４、プロフィットの計算２０５、レジスタ割
り付け２０６からなる。

【００２９】図３は、レジスタ割り付け部２０３の処理
の一例を示したものである。

【００３０】ステップ３０１の参照点属性の設定では、
中間コード４０を入力し、各変数に対しそれぞれの参照
点の意味を考慮して参照点属性を設定する。ステップ３
０２では、ステップ３０１の参照点属性の設定で設定さ
れた参照点属性に対してそれぞれの参照点属性に対して
予め設定されているプロフィット値を設定し、各変数ご
とにプロフィットを計算する。ステップ３０３は、ステ
ップ３０２で設定された各変数のプロフィット値をもと
に、よりプロフィットの高い変数からレジスタを割り付
けていく。

【００３１】図４は、参照点属性の設定３０１の処理の
一例を示したものである。

【００３２】参照点属性の設定処理は、ある変数が参照
されている箇所の意味を解析し、それぞれの意味に対し
て属性を設定する。例えば、関数間に跨って参照可能な
変数（以下グローバル変数と呼ぶ）は、関数呼び出しが
ある場合、呼び出した先の関数で参照することが可能な
ので、関数を呼び出す直前までにメモリに現在の値をス
トアしておかなければならない。さらに、関数呼び出し
後にその変数の値を使用する場合は、メモリから現在の
値をロードしなければならない。したがって、ある参照
点が使用点で、その直前の参照点との間に関数呼び出し
が存在する場合、その参照点にロード属性を設定する
（ステップ４０４，４０５，４０６）。ある参照点が定
義点で、その直後の参照点との間に関数呼び出しが存在
する場合、その参照点にストア属性を設定する（ステッ
プ４０８，４０９，４１０）。さて、グローバル変数に
ついては上記のステップロード、ストア属性を設定する
ことになる。グローバル変数に対して、関数内のみで参
照可能な変数（以下ローカル変数と呼ぶ）が、関数を跨
って参照されている場合の処理について説明する。ロー
カル変数呼び出し先の関数で定義されることはないので
関数呼び出しを跨ってレジスタを割り付けても良いこと
になる。しかし、割り付けるレジスタのクラスによって
は、関数呼び出し前後にメモリへの退避・回復コードが
必要になる。ここで、ｃａｌｌｅｒレジスタを割り付け
た場合、ｃａｌｌｅｒレジスタは関数呼び出しを跨って
参照できないので、関数呼び出し前後にメモリへの退避
・回復コードが必要になる。したがって、ローカル変数
に対しては、この退避・回復が必要な参照点を求めて属
性を設定する必要がある（ステップ４０４，４０５，４
０７とステップ４０８，４０９，４１１，４１２）。

【００３３】この他に考慮する参照点としては、変数が
関数呼び出しの引数に使用されている場合や、関数の戻
り値を受け取る場合がある。これはこのような参照点で
は特定のレジスタに値を載せていなければならない（こ
れを関数呼び出しにおけるコンベンションと呼ぶ）から
である。したがって、特定のレジスタ以外のレジスタを
割り付けた場合は、特定レジスタへのコピーコードを生
成しなければならない。このような参照点の属性を引数
・戻り値属性と呼ぶ。

【００３４】この他にも使用するマシンにより考慮しな
ければならない項目もあるのだが、ここでは議論を簡単
にするため以上の３つの参照点についてのみ考慮するこ
とにする。

【００３５】図５は、プロフィット値の計算３０２の処
理の一例を示したものである。

【００３６】プロフィットの計算方法について説明す
る。プロフィットはｃａｌｌｅｅプロフィット、ｃａｌ
ｌｅｒプロフィットの２つがある。それぞれの意味は、
その変数にレジスタが割り付かなかった場合に比べ、そ
のクラスのレジスタを割り付けることでどれだけの得に
なるかを示す値である。この値が大きければ大きいほど
そのクラスのレジスタを割り付けた方がより速く実行で
きることになる。

【００３７】プロフィットは、変数にレジスタが割り付
かなかった場合のコスト（以下、ｂａｓｅ＿ｃｏｓｔと
呼ぶ）からｃａｌｌｅｅまたはｃａｌｌｅｒを割り付け
た場合のコスト（以下、ｃａｌｌｅｅ＿ｃｏｓｔ，ｃａ
ｌｌｅｒ＿ｃｏｓｔと呼ぶ）を引くことにより求める。
ｃａｌｌｅｅ＿ｃｏｓｔとｃａｌｌｅｒ＿ｃｏｓｔは参
照点属性の設定３０１で設定した各参照点の属性を元に
もとめる。

【００３８】ステップ５０１では、ｂａｓｅ＿ｃｏｓ
ｔ，ｃａｌｌｅｅ＿ｃｏｓｔ，ｃａｌｌｅｒ＿ｃｏｓｔ
の初期化を行う。ｃａｌｌｅｅ＿ｃｏｓｔが‘ｌｏａｄ
＿ｃｏｓｔ＋ｓｔｏｒｅ＿ｃｏｓｔ’になっていること
について説明する。ｃａｌｌｅｅレジスタは、自関数で
内容を変更する場合、呼び出し元に対する値の保証をし
なければならないため、関数の入口に退避コードとなる
ストア命令、関数の出口に回復コードとなるロード命令
が必要になる。したがって、ｃａｌｌｅｅ＿ｃｏｓｔは
必ず‘ｌｏａｄ＿ｃｏｓｔ＋ｓｔｏｒｅ＿ｃｏｓｔ’を
初期値として計算を始めなければならない。

【００３９】ステップ５０５，５０６，５０７では、ｂ
ａｓｅ＿ｃｏｓｔを計算する。ｂａｓｅ＿ｃｏｓｔはレ
ジスタが割り付かない場合のコストなので、使用点では
ｌｏａｄ＿ｃｏｓｔを定義点ではｓｔｏｒｅ＿ｃｏｓｔ
をそれぞれ加える。

【００４０】ステップ５０８，５０９では、参照点の属
性がロード属性の場合の処理を行う。ロード属性の場合
は、ｃａｌｌｅｅレジスタｃａｌｌｅｒレジスタのどち
らかのクラスのレジスタを割り付けても必ずロード命令
が必要になるので、ｃａｌｌｅｅ＿ｃｏｓｔとｃａｌｌ
ｅｒ＿ｃｏｓｔにｌｏａｄ＿ｃｏｓｔを加える。

【００４１】ステップ５１０，５１１では、参照点の属
性がストア属性の場合の処理を行う。ロード属性の場合
と同じようにストア属性がある参照点では必ずストア命
令が必要になるので、ｃａｌｌｅｅ＿ｃｏｓｔとｃａｌ
ｌｅｒ＿ｃｏｓｔにｓｔｏｒｅ＿ｃｏｓｔを加える。

【００４２】ステップ５１２，５１３では、参照点の属
性がリストア属性の場合の処理を行う。リストア属性は
ｃａｌｌｅｒレジスタを割り付けた場合のみ必要なコス
トであるので、ｃａｌｌｅｒ＿ｃｏｓｔにのみｌｏａｄ
＿ｃｏｓｔを加える。

【００４３】ステップ５１４，５１５では、参照点の属
性がセーブ属性の場合の処理を行う。セーブ属性はリス
トア属性と同じようにｃａｌｌｅｅレジスタを割り付け
た場合のみ必要なコストであるので、ｃａｌｌｅｒ＿ｃ
ｏｓｔにのみｓｔｏｒｅ＿ｃｏｓｔを加える。

【００４４】ステップ５１６，５１７では、参照点の属
性が引数・戻り値属性の場合の処理を行う。通常、引数
・戻り値として決められているレジスタはｃａｌｌｅｒ
クラスのレジスタなので、ｃａｌｌｅｅクラスのレジス
タを割り付けた場合は、特定のｃａｌｌｅｒレジスタへ
のコピーが必要になる。したがって、この場合はｃａｌ
ｌｅｅ＿ｃｏｓｔにｃｏｐｙ＿ｃｏｓｔを加える。

【００４５】ステップ５１９では、ｂａｓｅ＿ｃｏｓｔ
からｃａｌｌｅｅ＿ｃｏｓｔまたはｃａｌｌｅｒ＿ｃｏ
ｓｔを引いてｃａｌｌｅｅ＿ｐｒｏｆｉｔ，ｃａｌｌｅ
ｒ＿ｐｒｏｆｉｔを求める。この２つの値は、変数情報
テーブル７００の、ｃａｌｌｅｅプロフィットフィール
ドとｃａｌｌｅｒプロフィットフィールドにそれぞれ設
定する。

【００４６】図６は、図５で求めたプロフィットから変
数に割り付けるレジスタを探すためのレジスタ探索処理
の一例を示したものである。

【００４７】図７は、変数情報テーブル７００のテーブ
ル構造を示したものである。このテーブルは、参照点情
報リストを示すポインタフィールド７０１と、ｃａｌｌ
ｅｅプロフィットを記憶するｃａｌｌｅｅプロフィット
フィールド７０２と、ｃａｌｌｅｒプロフィットを記憶
するｃａｌｌｅｒプロフィットフィールドと、変数に割
り付けられたレジスタ番号を記憶する割り付けレジスタ
フィールド７０４と、次の変数情報テーブルを示すポイ
ンタフィールド７０５とからなる。

【００４８】図８は、参照テーブル８００のテーブル構
造を示したものである。このテーブルは、中間コードを
示すポインタフィールド８０１と、参照点の属性を記憶
する参照点の属性フィールド８０２と、次の参照点テー
ブルを示すポインタフィールド８０３とからなる。

【００４９】図９は、変数情報テーブル７００と参照点
テーブル８００の結合状態を示した概念図である。１つ
の変数情報テーブル７００には、複数の参照点テーブル
８００が接続される。さらに、変数情報テーブル７００
は、他の変数情報テーブル７００と接続されている。

【００５０】図１０は、レジスタ情報テーブル１０００
のテーブル構造を示したものである。このテーブルは、
レジスタ番号を示すレジスタ番号フィールドと、レジス
タクラスの種別を示すレジスタ種別フィールドと、関数
内でそのレジスタが割り付けられたかどうかを示す割り
付け済みフラグフィールドからなる。

【００５１】図１１は、コスト情報テーブル１１００の
テーブル構造を示したものである。このテーブルは、コ
ストを考慮する参照点の種別であるコスト種別フィール
ドと、そのコスト種別でのコストを示したコストフィー
ルドからなる。

【００５２】

【発明の効果】既に割り付けられたｃａｌｌｅｅレジス
タを有効利用することで、関数呼び出しを跨って生きて
いる変数にｃａｌｌｅｅレジスタを割り付けることによ
り、ｃａｌｌｅｒを割り付けた場合に生成するメモリへ
のストア命令とロード命令を生成しなくても良いことに
なり、目的コードの実行性能を向上させることができ
る。

【図面の簡単な説明】

【図１】本発明の一実施例のシステム構成図である。

【図２】コンパイラの処理構成図である。

【図３】レジスタ割り付け処理手順を示すフローチャー
ト図である。

【図４】参照点の属性設定処理手順を示すフローチャー
ト図である。

【図５】プロフィットの計算処理手順を示すフローチャ
ート図である。

【図６】レジスタ探索処理手順を示すフローチャート図
である。

【図７】変数情報テーブルの構成図である。

【図８】参照点テーブルの構成図である。

【図９】変数情報テーブルと参照点テーブルの結合状態
を示す概念図。

【図１０】レジスタ情報テーブルの構成図である。

【図１１】コスト情報テーブルの構成図である。

【図１２】ソースプログラム例である。

【符号の説明】

１０…コンパイラ、 ３０…ソースプログラム。
４０…中間コード、５０…目的コード。

Claims (1)

【特許請求の範囲】
1. 【請求項１】呼び出し先で退避回復するレジスタである
   ｃａｌｌｅｅ退避レジスタが、割り付け単位内で割り付
   けられたかを記憶するテーブルと、割り付け時に割り付
   け指標となる値を再計算し、該テーブルから既に割り付
   けられているｃａｌｌｅｅ退避レジスタを探し該ｃａｌ
   ｌｅｅ退避レジスタが割り付けられるかどうかを調べる
   処理とを有するレジスタ割り付け方法。