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: david@cs.washington.edu (David Callahan)
Newsgroups: comp.compilers
Subject: Re: Is register allocation really NP-Complete?
Keywords: optimization, theory, design
Message-ID: <15573@june.cs.washington.edu>
Date: 27 Mar 91 16:01:36 GMT
References: <11422.27ef7017@zeus.unomaha.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: david@cs.washington.edu (David Callahan)
Organization: Tera Computer Co., Seattle WA
Lines: 39
Approved: compilers@iecc.cambridge.ma.us

In article <11422.27ef7017@zeus.unomaha.edu> payne@zeus.unomaha.edu (Matt Payne) writes:
>
>So, I'm confused.  [Chow 90] implies that this is a NP-complete problem,
>but how can it be if [Chow 90]'s interference graphs are interval
>graphs?

Conflict graphs, even coarse ones such as Chow constructs, are not
interval graphs. Consider the fragment:

	A = 
        B =
   l:    ...  = B 
	 ... = A 
	C = 
	...
	... = C 
	B = 
	goto l;

	... A 

Note that the live range of B is discontiguous due to the control flow.
These live ranges might be viewed as:

 	 BB  CCC B
	AAAAAAAAAAA

and so we see the conflict graph is not an interval graph.

However, I don't know of a method that shows how to construct a program
whose conflict graph corresponds to some arbitrary graph and so it is
still possible that the restricted coloring problem associated with
conflict graphs is not NP-hard.
-- 
David Callahan  (david@tera.com, david@june.cs.washington.edu,david@rice.edu)
Tera Computer Co. 	400 North 34th Street  		Seattle WA, 98103
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.