Editing Register allocation (section)

==== Drawbacks and further improvements ====
The graph-coloring allocation has three major drawbacks. First, it relies on graph-coloring, which is an [[NP-completeness|NP-complete problem]], to decide which variables are spilled. Finding a minimal coloring graph is indeed an NP-complete problem.{{sfn|Book|1975|p=618–619}} Second, unless live-range splitting is used, evicted variables are spilled everywhere: store instructions are inserted as early as possible, i.e., just after variable definitions; load instructions are respectively inserted late, just before variable use. Third, a variable that is not spilled is kept in the same register throughout its whole lifetime.{{sfn|Colombet|Brandner|Darte|2011|p=1}}

On the other hand, a single register name may appear in multiple register classes, where a class is a set of register names that are interchangeable in a particular role. Then, multiple register names may be aliases for a single hardware register.{{sfn|Smith|Ramsey|Holloway|2004|p=277}} 
Finally, graph coloring is an aggressive technique for allocating registers, but is computationally expensive due to its use of the interference graph, which can have a worst-case size that is [[Time complexity#Table of common time complexities|quadratic]] in the number of live ranges.{{sfn|Cavazos|Moss|O’Boyle|2006|p=124}}
The traditional formulation of graph-coloring register allocation implicitly assumes a single bank of non-overlapping general-purpose registers and does not handle irregular architectural features like overlapping registers pairs, special purpose registers and multiple register banks.{{sfn|Runeson|Nyström|2003|p=240}}

One later improvement of Chaitin-style graph-coloring approach was found by Briggs et al.: it is called conservative coalescing. This improvement adds a criterion to decide when two live ranges can be merged. Mainly, in addition to the non-interfering requirements, two variables can only be coalesced if their merging will not cause further spilling. Briggs et al. introduces a second improvement to Chaitin's works which is biased coloring. Biased coloring tries to assign the same color in the graph-coloring to live range that are copy related.{{sfn|Briggs|Cooper|Torczon|1992|p=316}}