レジスタ割り付け
チャイティンのアルゴリズムの要点は、次数 < R 規則と呼ばれるものである。すなわち、次数が R より小さいノード N を含むグラフ G があるとき、G が R 色で彩色可能であることと、G からノード N を削除したグラフ G' が R 色で彩色可能であることは同値である。一方向の証明は自明である。G が R 色で彩色可能なら、G' は配色を変えずに彩色可能である。逆方向では、R 色で彩色した G' をまず考える。N の次数は R より小さいので、ノード N に使える色が少なくとも一色は存在するはずである。従って、N 番のノードはその色で彩色可能である。アルゴリズムは次のようになる。
このアルゴリズムは O(n) である。このアルゴリズムは、実施前に値がコピーされている変数を1つのノードで表すようにすることで改善できる。ただし、それをするとノード数は減るが、統合したノードの次数が増えてしまう可能性がある。これはそれら変数が互いに干渉しない場合のみ、かつ統合によって彩色不能なグラフとならない場合のみ可能である。Preston Briggs はどれを統合して、どれを spill 対象とするかをより安全に決定する方法を研究した。彼の改善策を含めた場合、このアルゴリズムを Chaitin-Briggs algorithm と呼ぶ。ノード統合は時間がかかるため、レジスタ割り付けを素早く行いたい場合は実施しない。
グラフ彩色によるレジスタ割り付けは効率的なコードを生成するが、割り付けにかかる時間(コンパイル時の時間)は大きい。通常のコンパイラではこれは大きな問題とはならない。しかし、ジャストインタイムコンパイル方式などでは、レジスタ割り付けの高速化が重要となる。そのための効率的な方法として Poletto と Sarkar の linear scan allocation がある。これは、変数の生存区間をワンパスで処理できる。生存区間の短い変数を優先してレジスタに割り付け、長いものを spill 対象とする傾向がある。生成するコードの効率は、グラフ彩色方式に比較して平均で 12% 低下したものとなる。
linear scan algorithm は以下の通りである。
データフロー解析により変数の生存区間情報を収集する。生存区間の開始時点の早い順にそれら情報を並べるようにする。
リストの先頭からループで見ていく。 未使用レジスタがあれば、現在見ている変数に割り付ける。現在見ている変数と生存区間が重なっている変数のリスト(アクティブリスト)を更新していく。