Related articles |
---|
Is register allocation really NP-Complete? payne@zeus.unomaha.edu (1991-03-26) |
Re: Is register allocation really NP-Complete? larus@cs.wisc.edu (1991-03-27) |
Re: Is register allocation really NP-Complete? preston@ariel.rice.edu (1991-03-27) |
Re: Is register allocation really NP-Complete? david@cs.washington.edu (1991-03-27) |
Re: Is register allocation really NP-Complete? preston@ariel.rice.edu (1991-03-28) |
Re: Is register allocation really NP-Complete? spencert@cs.rpi.edu (1991-03-31) |
Newsgroups: | comp.compilers |
From: | larus@cs.wisc.edu |
Keywords: | optimization, theory, design |
Organization: | U of Wisconsin CS Dept |
References: | <11422.27ef7017@zeus.unomaha.edu> |
Date: | Wed, 27 Mar 91 14:20:19 GMT |
Graph coloring for general graphs is NP-complete. There may be special
cases (such as interval graphs and circular-arc graphs) for which
efficient algorithms exists, but no one has shown their relevance for
register allocation (hint, hint). NB, a register allocator has an
additional constraint beyond a graph colorer. The allocator cannot throw
up its hands and quit when a graph is not 16 or 32 colorable.
And, yes both Chaitin's and Chow's algorithms are heuristics. There is no
guarantee that they achieve optimal colorings. The only promise is that
they can color all graphs (which they may modify in the process by
introducing spill code).
/Jim
--
Return to the
comp.compilers page.
Search the
comp.compilers archives again.