From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 23389 invoked by alias); 22 Jan 2005 17:21:21 -0000 Mailing-List: contact gcc-bugs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-bugs-owner@gcc.gnu.org Received: (qmail 23151 invoked by alias); 22 Jan 2005 17:21:05 -0000 Date: Sat, 22 Jan 2005 17:21:00 -0000 Message-ID: <20050122172105.23150.qmail@sourceware.org> From: "dberlin at dberlin dot org" To: gcc-bugs@gcc.gnu.org In-Reply-To: <20030616070732.11203.spigel@olvs.miee.ru> References: <20030616070732.11203.spigel@olvs.miee.ru> Reply-To: gcc-bugzilla@gcc.gnu.org Subject: [Bug inline-asm/11203] source doesn't compile with -O0 but they compile with -O3 X-Bugzilla-Reason: CC X-SW-Source: 2005-01/txt/msg03183.txt.bz2 List-Id: ------- 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