Editing Register allocation (section)

=== Graph-coloring allocation ===
{{See also|Graph coloring}}
Graph-coloring allocation is the predominant approach to solve register allocation.{{sfn|Eisl|Leopoldseder|Mössenböck|2018|p=1}}{{sfn|Briggs|Cooper|Torczon|1992|p=316}} It was first proposed by Chaitin et al.{{sfn|Chaitin|Auslander|Chandra|Cocke|1981|p=47}}
In this approach, nodes in the [[Graph (discrete mathematics)|graph]] represent live ranges ([[Variable (computer science)|variables]], [[Temporary variable|temporaries]], virtual/symbolic registers) that are candidates for register allocation. Edges connect live ranges that interfere, i.e., live ranges that are simultaneously live at at least one program point. Register allocation then reduces to the [[graph coloring]] problem in which colors (registers) are assigned to the nodes such that two nodes connected by an edge do not receive the same color.{{sfn|Poletto|Sarkar|1999|p=896}}

Using [[Live variable analysis|liveness analysis]], an interference graph can be built. The interference graph, which is an [[Graph (discrete mathematics)#Undirected graph|undirected graph]] where the nodes are the program's variables, is used to model which variables cannot be allocated to the same register.{{sfn|Runeson|Nyström|2003|p=241}}

==== Principle ====
The main phases in a Chaitin-style graph-coloring register allocator are:{{sfn|Briggs|Cooper|Torczon|1992|p=316}}
[[File:Chaitin et al.'s iteravite graph coloring based register allocator.png|thumb|700px|Chaitin et al.'s iterative graph coloring based register allocator]]
# '''Renumber''': discover live range information in the source program.
# '''Build''': build the interference graph.
# '''Coalesce''': merge the live ranges of non-interfering variables related by copy instructions.
# '''Spill cost''': compute the spill cost of each variable. This assesses the impact of mapping a variable to memory on the speed of the final program.
# '''Simplify''': construct an ordering of the nodes in the inferences graph
# '''Spill Code''': insert spill instructions, i.e. loads and stores to commute values between registers and memory.
# '''Select''': assign a register to each variable.

==== 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}}