[Bug inline-asm/11203] source doesn't compile with -O0 but they compile with -O3

[Daniel Berlin]

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