Editing Register allocation (section)

=== Coalescing ===
{{See also|Coalescing (computer science)}}
In the context of register allocation, coalescing is the act of merging variable-to-variable move operations by allocating those two variables to the same location. The coalescing operation takes place after the interference graph is built. Once two nodes have been coalesced, they must get the same color and be allocated to the same register, once the copy operation becomes unnecessary.{{sfn|Chaitin|1982|p=90}}

Doing coalescing might have both positive and negative impacts on the colorability of the interference graph.{{sfn|Bouchez|Darte|Rastello|2007b|p=103}} For example, one negative impact that coalescing could have on graph inference colorability is when two nodes are coalesced, as the result node will have a union of the edges of those being coalesced.{{sfn|Bouchez|Darte|Rastello|2007b|p=103}}
A positive impact of coalescing on inference graph colorability is, for example, when a node interferes with both nodes being coalesced, the degree of the node is reduced by one which leads to improving the overall colorability of the interference graph.{{sfn|Ahn|Paek|2009|p=7}}

There are several coalescing heuristics available:{{sfn|Park|Moon|2004|p=736}}

; Aggressive coalescing: It was first introduced in Chaitin's original register allocator. This heuristic aims at coalescing any non-interfering, copy-related nodes.{{sfn|Chaitin|1982|p=99}} From the perspective of copy elimination, this heuristic has the best results.{{sfn|Park|Moon|2004|p=738}} On the other hand, aggressive coalescing could impact the colorability of the inference graph.{{sfn|Ahn|Paek|2009|p=7}}
;Conservative Coalescing: It mainly uses the same heuristic as aggressive coalescing but it merges moves if, and only if, it does not compromise the colorability of the interference graph.{{sfn|Briggs|Cooper|Torczon|1994|p=433}}
;Iterated coalescing: It removes one particular move at the time, while keeping the colorability of the graph.{{sfn|George|Appel|1996|p=212}}
;Optimistic coalescing: It is based on aggressive coalescing, but if the inference graph colorability is compromised, then it gives up as few moves as possible.{{sfn|Park|Moon|2004|p=741}}