レジスタ割り付け

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

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

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

目標

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

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

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

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

1. 無限のレジスタがあるかのように機械語列を生成する。従って、全ての変数に論理番号の付与されたレジスタが対応付けられる。この工程を register variable recognition（レジスタ変数認識）と呼ぶ。
2. その仮想的なレジスタ群をターゲットマシンの物理レジスタに置換していく。その際、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 と呼ぶ。ノード統合は時間がかかるため、レジスタ割り付けを素早く行いたい場合は実施しない。

最近の進歩

グラフ彩色によるレジスタ割り付けは効率的なコードを生成するが、割り付けにかかる時間（コンパイル時の時間）は大きい。通常のコンパイラではこれは大きな問題とはならない。しかし、ジャストインタイムコンパイル方式などでは、レジスタ割り付けの高速化が重要となる。そのための効率的な方法として Poletto と Sarkar の linear scan allocation がある。これは、変数の生存区間をワンパスで処理できる。生存区間の短い変数を優先してレジスタに割り付け、長いものを spill 対象とする傾向がある。生成するコードの効率は、グラフ彩色方式に比較して平均で 12% 低下したものとなる。

linear scan algorithm は以下の通りである。

1. データフロー解析により変数の生存区間情報を収集する。生存区間の開始時点の早い順にそれら情報を並べるようにする。
2. リストの先頭からループで見ていく。
   1. 未使用レジスタがあれば、現在見ている変数に割り付ける。現在見ている変数と生存区間が重なっている変数のリスト（アクティブリスト）を更新していく。このリストは生存区間の終了時点の早い順にソートする。これを線形なコストで行うには、平衡2分探索木を使う。生存区間が過ぎた変数はリストから除き、割り付けていたレジスタを未使用レジスタに戻す。
   2. 未使用レジスタが不足した場合、レジスタを割り付けずにアクティブリストに追加する。アクティブリスト内で最も生存区間の終了時点が遅いものからレジスタ割り付けを解除して（その変数は spill 対象）、そのレジスタを現在見ている変数に割り付ける。もし、現在見ている変数が最も生存区間の終了時点が遅いなら、現在見ている変数が spill 対象となる。

さらに最近では、Goodwin と Wilken により、整数計画問題の解法を応用した、より最適なアルゴリズムが開発されている。さらに Kong と Wilken はそれを特殊なアーキテクチャの場合にも適用できるようにした。

最悪時間は指数関数時間だが、実際の適用結果を見てみると平均して $O(n^{2.5})$ （n は制約数）となっている。