From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 22770 invoked by alias); 22 Jan 2005 17:20:56 -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 22581 invoked from network); 22 Jan 2005 17:20:45 -0000 Received: from unknown (HELO dberlin.org) (68.164.203.246) by sourceware.org with SMTP; 22 Jan 2005 17:20:45 -0000 Received: from [127.0.0.1] (HELO dberlin.org) by dberlin.org (CommuniGate Pro SMTP 4.2.8) with ESMTP-TLS id 7667105; Sat, 22 Jan 2005 12:20:45 -0500 Date: Sat, 22 Jan 2005 17:20:00 -0000 From: Daniel Berlin To: michaelni at gmx dot at cc: gcc-bugs@gcc.gnu.org Subject: Re: [Bug inline-asm/11203] source doesn't compile with -O0 but they compile with -O3 In-Reply-To: <20050122171015.16135.qmail@sourceware.org> Message-ID: References: <20030616070732.11203.spigel@olvs.miee.ru> <20050122171015.16135.qmail@sourceware.org> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed X-SW-Source: 2005-01/txt/msg03182.txt.bz2 List-Id: > > >> >> 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.