Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!swrinde!elroy.jpl.nasa.gov!decwrl!world!iecc!compilers-sender
From: larus@cs.wisc.edu
Newsgroups: comp.compilers
Subject: Re: Is register allocation really NP-Complete?
Keywords: optimization, theory, design
Message-ID: <1991Mar27.142019.23329@spool.cs.wisc.edu>
Date: 27 Mar 91 14:20:19 GMT
References: <11422.27ef7017@zeus.unomaha.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: larus@cs.wisc.edu
Organization: U of Wisconsin CS Dept
Lines: 17
Approved: compilers@iecc.cambridge.ma.us

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

-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.