レジスタ割り付けとは何？わかりやすく解説 Weblio辞書

索引トップ用語の索引ランキングカテゴリー

レジスタ割り付け

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/01 04:36 UTC 版)

レジスタ割り付け（レジスタわりつけ、英: Register allocation）は、プログラム内の多数の変数を少数のCPU レジスタに多重化するコンパイラ最適化技法のひとつである。その目標は、プログラムの実行速度を最大化すべく、なるべく多くのオペランドをレジスタに保持するようにすることである。レジスタ割り付けは基本的なブロックについて行う場合（ローカルレジスタ割り付け）と関数やプロシージャ全体について行う場合（グローバルレジスタ割り付け）がある。レジスタ割り当てとも呼ぶ。

プログラムは、多数の様々なデータを処理することが多い。しかし、CPUの多くはデータを保持するのに使えるレジスタ数は限られている。機械語のオペランドとしてメモリを指定できる場合でも、なるべくレジスタを使った方が高速化される。従って、処理に必要なデータを RAMとレジスタの間で入れ替えてやる必要がある。この操作を spill（スピル、あふれ）と呼ぶ。

レジスタの spill は、マシンが持っているレジスタ数以上の変数が同時に必要とされる場合に発生する。一般にメモリはレジスタよりも遅いため、spill にはコストがかかる。

目標

レジスタ割り付けはNP完全問題である。一般にプログラム内の変数の個数は、プロセッサ上で利用可能なレジスタ数より多い。従って一部の変数の内容は適当なメモリ位置に spill（セーブ）される必要がある。spill のコストを最小化するには、最も利用頻度の低い変数から spill するようにすればよい。しかし、各変数の利用頻度をコンパイル時に知るのは容易ではない。さらに、ハードウェアやオペレーティングシステムがレジスタの利用方法を制限することもある。

グローバルレジスタ割り付け

他のコンパイラ最適化技法と同様、レジスタ割り付けは何らかの解析結果に基づいて行われる。特にデータフロー解析における生存変数解析の結果を用いるのが一般的である。

グローバルレジスタ割り付けを行う古典的な技法として、グレゴリー・チャイティンらが発見したグラフ彩色アルゴリズムを使った方法がある。これは以下の2つの工程に分けられる。

無限のレジスタがあるかのように機械語列を生成する。従って、全ての変数に論理番号の付与されたレジスタが対応付けられる。この工程を register variable recognition（レジスタ変数認識）と呼ぶ。
その仮想的なレジスタ群をターゲットマシンの物理レジスタに置換していく。その際、spill コストが最小になるようにする。

工程 2 で、変数をノードとし、2つの変数が同時に生存する場合にそれらノード間にエッジを設定した干渉グラフ（interference graph）を構築する。より正確に言えば、ある変数が生存中に別の変数が定義されれば、それらは干渉すると言える。このグラフの彩色をするというのは、エッジで直接結ばれたノード同士が同じ色にならないように、かつなるべく少ない色数でグラフの全ノードを彩色することに他ならない。このグラフを R 色で彩色できる場合、そのコード部分では変数を格納するのに R 個のレジスタが必要ということになる。これはジョン・コックが指摘した。このグラフ彩色問題はNP困難な問題である。

チャイティンのアルゴリズムの要点は、次数 < R 規則と呼ばれるものである。すなわち、次数が R より小さいノード N を含むグラフ G があるとき、G が R 色で彩色可能であることと、G からノード N を削除したグラフ G' が R 色で彩色可能であることは同値である。一方向の証明は自明である。G が R 色で彩色可能なら、G' は配色を変えずに彩色可能である。逆方向では、R 色で彩色した G' をまず考える。N の次数は R より小さいので、ノード N に使える色が少なくとも一色は存在するはずである。従って、N 番のノードはその色で彩色可能である。アルゴリズムは次のようになる。

While （G を R 色で彩色できない）
  While （G に R より次数が小さいノード N がある）
    N とそれに付随するエッジ群を G から削除し、N を スタック S にプッシュする
  End While
  If グラフ全体が削除された then グラフは R 色で彩色可能
    While スタック S にノード N がある
      N をグラフ G に加え、R 色の色から一色を選んで割り付ける
    End While
  Else グラフ G は R 色で彩色不可能
  spill 対象を選択し、そのノード N をグラフ G から削除してグラフを単純化する
  (* spill 対象は定義回数と参照回数に基づいて選択する *)
End While

このアルゴリズムは O(n²) である。このアルゴリズムは、実施前に値がコピーされている変数を1つのノードで表すようにすることで改善できる。ただし、それをするとノード数は減るが、統合したノードの次数が増えてしまう可能性がある。これはそれら変数が互いに干渉しない場合のみ、かつ統合によって彩色不能なグラフとならない場合のみ可能である。Preston Briggs はどれを統合して、どれを spill 対象とするかをより安全に決定する方法を研究した。彼の改善策を含めた場合、このアルゴリズムを Chaitin－Briggs algorithm と呼ぶ。ノード統合は時間がかかるため、レジスタ割り付けを素早く行いたい場合は実施しない。

脚注

^ linear scan allocation
^ Kong, Wilken, Precise Register Allocation for Irregular Architectures, [1]

ウィキペディア小見出し辞書

索引トップ用語の索引ランキング