Graph coloring is a small part of register allocation, and not the hard part.  It&#x27;s also not NP complete on interference graphs built from SSA form, which most modern compilers (though not GCC) use in the backend.   In fact, it&#x27;s linear time optimally solvable if you build ssi form, which can be done in linear time.<p>The optimal spilling and rematerialization problems have not yet shown to be solvable in polynomial time on these forms, but folks are working on it.