News for hackers. Stuff that matters.
Re:A very old gcc "bug" by jacquesm on Sunday October 25, 2009 @05:55PM (#902204)
read comment #24:

Martin, you should realize that this problem cannot be solved. Yes, there will perhaps be a time when this particular test case compiles, though I think that is unlikely. But anyway, then there will be other cases that fail.

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. That means any register allocator will always fail on some very constrained asm input. 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.

So really it doesn't matter at all whether or not your specific inline asm compiles or not. When yours does, someone else's will fail.

Re:A very old gcc "bug" by ars on Sunday October 25, 2009 @06:37PM (#902271)
You are not the only one who does not understand the halting problem.

The halting problem only says you can not prove every program will (or won't) halt - the general case.

It says nothing at all about any specific case, and there are plenty of programs where you can prove they halt.

And NP just means the solution does not scale well, not that it can't be done.

And NP-complete is something else entirely. It has to do with being able to interconvert all NP-complete problems (i.e. if you solve one you solve all).

There are many NP problems that are not NP-complete. Proving any particular problem is NP-complete, and not just NP is usually a big deal, so don't just throw that term around.

Re:A very old gcc "bug" by jacquesm on Sunday October 25, 2009 @06:48PM (#902279)
It was a quote from the original thread.

As for your explanation, yes, that's correct. The thing that I didn't get about the way they were sparring on the list was that if there is a solution the problem might not be solved in an elegant way, but with the number of variations involved you could simply brute force it.

Then if a solution exists you'll find it, if it doesn't exist then you can report that. After all, if you say you want to put 12 variables in to 7 registers and there is no possible way then there is no possible way. If there is such a possibility the number of permutations is small enough that it could be found anyway.

GCC contributes to the problem by having some overhead that reserves registers that could be saved on the stack for the duration of this part of the computation.

Re:A very old gcc "bug" by yuvi on Sunday October 25, 2009 @06:12PM (#902230)
You skipped over 26, 27, and 34...
Re:A very old gcc "bug" by jacquesm on Sunday October 25, 2009 @06:18PM (#902239)
You're right, I stopped reading at that point. My bad!