Re: Is register allocation really NP-Complete?

larus@cs.wisc.edu
Wed, 27 Mar 91 14:20:19 GMT

          From comp.compilers

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)
| List of all articles for this month |

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


--


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.