レジスタ割り付け
他のコンパイラ最適化技法と同様、レジスタ割り付けは何らかの解析結果に基づいて行われる。特にデータフロー解析における生存変数解析の結果を用いるのが一般的である。
グローバルレジスタ割り付けを行う古典的な技法として、グレゴリー・チャイティンらが発見したグラフ彩色アルゴリズムを使った方法がある。これは以下の2つの工程に分けられる。
無限のレジスタがあるかのように機械語列を生成する。従って、全ての変数に論理番号の付与されたレジスタが対応付けられる。この工程を register variable recognition(レジスタ変数認識)と呼ぶ。
その仮想的なレジスタ群をターゲットマシンの物理レジスタに置換していく。その際、spill コストが最小になるようにする。
工程 2 で、変数をノードとし、2つの変数が同時に生存する場合にそれらノード間にエッジを設定した干渉グラフ(interference graph)を構築する。より正確に言えば、ある変数が生存中に別の変数が定義されれば、それらは干渉すると言える。このグラフの彩色をするというのは、エッジで直接結ばれたノード同士が同じ色にならないように、かつなるべく少ない色数でグラフの全ノードを彩色することに他ならない。このグラフを R 色で彩色できる場合、そのコード部分では変数を格納するのに R 個のレジスタが必要ということになる。これはジョン・コックが指摘した。このグラフ彩色問題はNP困難な問題である。