------- Additional Comments From dberlin at gcc dot gnu dot org 2005-01-22 17:21 ------- Subject: Re: source doesn't compile with -O0 but they compile with -O3
> > >> >> 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. -- http://gcc.gnu.org/bugzilla/show_bug.cgi?id=11203
