------- Comment #34 from langer_mann at web dot de 2006-04-21 15:56 -------
> 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.
--
langer_mann at web dot de changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |langer_mann at web dot de
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11203
