A generalized algorithm for graph-coloring register allocation
Michael D. Smith and Norman Ramsey and Glenn Holloway. In Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pages 277-288. 2004.
グラフの色分けアルゴリズムを用いたレジスタ割り付けは長年研究されているが、それらは全てレジスタがお互いに可換(interchangable)で独立(independent)であることを前提にしている。レジスタがお互いに可換であるとは、ある命令で使われているレジスタを別のどのレジスタに置き換えても良い、ということである。レジスタがお互いに独立であるとは、あるレジスタへの書き込みが他のレジスタの値を変えない、ということである。しかし、現実のアーキテクチャではレジスタセットが可換で独立であることはまずない。多くのアーキテクチャでは固定小数点系と浮動小数点系でレジスタセットは分かれている。x86のMMXレジスタは独立でないレジスタセットの代表例である。したがって、既存のコンパイラはグラフ色分けアルゴリズムを各々のアーキテクチャ向けにアドホックに変更して適用しなければならなかった。
著者らはグラフ色分けアルゴリズムの直感的なわかりやすさを維持しつつ、可換でも独立でもないレジスタセットに適用可能な汎用的なレジスタ割り付けアルゴリズムを開発した。グラフ色分けアルゴリズムでは、全レジスタ数kに対して干渉グラフのノードnの次数degreenがk未満であるならば、nに自明に色を割り当てることができることを利用していた：
degreen < k (1)
それに対して著者らはまず、レジスタの集合として「クラス」を定義する。あるクラス内のレジスタは可換でなければならないが、独立である必要はない。レジスタnが属するクラスをclassnと書く。また、レジスタrに対して独立でないレジスタの集合をalias(r)と定義する。これを任意のレジスタ集合Sに自然に拡張してalias(S)を定義する：alias(S) = ∪r∈Salias(r)。
そこでこれらの定義に基づいて式(1)に対応する新たな制約条件を導入する。まず、ノードnに割り当て可能な色の数は|classn|個である。nの隣接ノードからの干渉のせいでnに割り当てられなくなるclassn中のレジスタの最大個数をsqueeze*nとおくと、
squeeze*n < |classn| (2)
であるならばnに自明に色を割り当てることができる。可換で独立である場合にのみ適用可能な式(1)を、可換でも独立でもない場合に一般化したのが式(2)であると言うことができる。ここでsqueeze*nは
squeeze*n = maxS∈nの隣接ノードへのレジスタの割り当てかた全て|classn∩alias(S)|
となる。このsqueeze*nに対する安全な近似を効率的に求める方法、というのがこの論文の主要部になっている。
確かにこれでうまくいくとは思うのだが、論文を読む限りは実際かなり複雑な手法に見える。コンパイラの最適化アルゴリズムの提案手法が皆に使ってもらえるか否か、というのは実装の複雑さとそれによって得られる性能向上（もしくはアーキテクチャ独立性）を天秤にかけて判断されるものだ。この手法は複雑さという点で少し損をしているかな、とは思う。
