レジスタ割り付け
このリストは生存区間の終了時点の早い順にソートする。これを線形なコストで行うには、平衡2分探索木を使う。生存区間が過ぎた変数はリストから除き、割り付けていたレジスタを未使用レジスタに戻す。 未使用レジスタが不足した場合、レジスタを割り付けずにアクティブリストに追加する。アクティブリスト内で最も生存区間の終了時点が遅いものからレジスタ割り付けを解除して(その変数は spill 対象)、そのレジスタを現在見ている変数に割り付ける。もし、現在見ている変数が最も生存区間の終了時点が遅いなら、現在見ている変数が spill 対象となる。
さらに最近では、Goodwin と Wilken により、整数計画問題の解法を応用した、より最適なアルゴリズムが開発されている。さらに Kong と Wilken はそれを特殊なアーキテクチャの場合にも適用できるようにした。
最悪時間は指数関数時間だが、実際の適用結果を見てみると平均して O ( n 2.5 ) {\displaystyle O(n^{2.5})} (n は制約数)となっている。