------- Comment #35 from langer_mann at web dot de 2006-04-21 15:59 ------- (In reply to comment #34) > > 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. > > Not at all. If a problem is NP-hard, you can in fact solve it! It is just > quite > likely that your algortihm takes exponentiallly many steps in the size of the > problem. Which, given the few registers of x86 might turn out not to be a > problem. > > > 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. > > Not necessary. The coloring problem is decidable (just enumerate all the > colorings aka. register mappings), whereas the halting problem is not > decidable > (or semi-decidable if you're intrested in that) > > > 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. > > Nope. >
Sorry for the spam. Didn't read up to the end. Have been quite angry with the whole situation.... -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11203
