Comment by 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...