[Joker_vD]

There is a wonderful paper "Register Allocation: What Does the NP-Completeness Proof of Chaitin et al. Really Prove?" (2006) by Bouchez, Darte, and Rastello [0]. I'll just quote the abstract in full because there is really nothing much I could add to it:

    Register allocation is one of the most studied problem in compilation. It is
    considered as an NP-complete problem since Chaitin, in 1981, showed that
    assigning temporary variables to k machine registers amounts to color, with
    k colors, the interference graph associated to variables and that this graph
    can be arbitrary, thereby proving the NP-completeness of the problem. However,
    this original proof does not really show where the complexity comes from.
    Recently, the re-discovery that interference graphs of SSA programs can be
    colored in polynomial time raised the question: Can we exploit SSA to perform
    register allocation in polynomial time, without contradicting Chaitin's NP-
    completeness result? To address such a question, we revisit Chaitin's proof
    to better identity the interactions between spilling (load/store insertion),
    coalescing/splitting (moves between registers), critical edges (a property of
    the control-flow graph), and coloring (assignment to registers). In particular,
    we show when it is easy to decide if temporary variables can be assigned to
    k registers or if some spilling is necessary. The real complexity comes from
    critical edges, spilling, and coalescing, which are addressed in our other
    reports.

[0] https://hal-lara.archives-ouvertes.fr/hal-02102286v1/documen...

[ebiederm]

It is worth noting that register coalescing gets a lot of attention in interference graph coloring allocators because they typically have a pre-pass that inserts copies everywhere (because adding copies or spills later is so hard). So instead of worrying about where to insert copies and spills, those allocators worry about what to coalesce instead.

In my own compiler (where I don't add copies in a prepass) I have not yet found a case where any coalescing would be beneficial.