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: preston@ariel.rice.edu (Preston Briggs)
Newsgroups: comp.compilers
Subject: Re: Is register allocation really NP-Complete?
Summary: yep
Keywords: optimization, theory, design
Message-ID: <1991Mar27.150723.27988@rice.edu>
Date: 27 Mar 91 15:07:23 GMT
References: <11422.27ef7017@zeus.unomaha.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: preston@ariel.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Lines: 14
Approved: compilers@iecc.cambridge.ma.us

The interference graph for straight-line code (no branches or loops) will
be an interval graph; otherwise, it's more complex.  Chow is interested in
global allocation (over an entire procedure), and must therefore worry
about such things.

Further, he must worry about spill code.  Even if he has lots of registers
and achieves a minimal coloring, some programs will still require spill
code.

Preston Briggs

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