The reason is dead simple: register allocation is NP-complete, so it is even *theoretically* not possible to write register allocators that always find a coloring.
register allocation in general is NP-complete, yes, but it seems u forget that this is about finding the optimal solution while gcc fails finding any solution which in practice is a matter of assigning the registers beginning from the most constrained operands to the least, and copying a few things on the stack if gcc cant figure out howto access them, sure this method might fail in 0.001% of the practical cases and need a 2nd or 3rd pass where it tries different registers it might also happen that in some intentionally overconstrained cases it ends up searching the whole 5040 possible assignments of 7 registers onto 7 non memory operands but still it wont fail
Just to also point out, it doesn't appear to be NP complete for register interference graphs, because they all seem to be 1-perfect.
Various papers have observed this, and i've actually compiled all of gcc, libstdc++, etc, and every package ever on my computer, and not once has a single non-1-perfect interference graph occurred [my compiler would abort if it was true].
On 1-perfect graphs you can solve this problem in O(time it takes to determine the max clique), and there already exists a polynomial time algorithm for max-clique on perfect graphs.
>
That means any register allocator will always fail on some very constrained asm input.
now that statement is just false, not to mention irrelevant as none of these asm statemets are unreasonably constrained
You are correct, NP completeness does not imply impossiblity. There are only a finite number of possibilities.
And you cannot allow it to run indefinitely until a coloring is found, because then you've turned the graph coloring problem into the halting problem because you can't prove that a coloring exists and that the register allocator algorithm will terminate.
this is ridiculous, the number of possible colorings is finite, u can always try them all in finite time
You are right, he is wrong.
