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

["langer_mann at web dot de" <gcc-bugzilla@gcc.gnu.org>]

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