From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 19888 invoked by alias); 21 Apr 2006 15:56:15 -0000 Received: (qmail 19819 invoked by uid 48); 21 Apr 2006 15:56:09 -0000 Date: Fri, 21 Apr 2006 15:56:00 -0000 Message-ID: <20060421155609.19818.qmail@sourceware.org> X-Bugzilla-Reason: CC References: Subject: [Bug inline-asm/11203] source doesn't compile with -O0 but they compile with -O3 In-Reply-To: Reply-To: gcc-bugzilla@gcc.gnu.org To: gcc-bugs@gcc.gnu.org From: "langer_mann at web dot de" 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 X-SW-Source: 2006-04/txt/msg01765.txt.bz2 List-Id: ------- 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