Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!usc!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?
Keywords: optimization, theory, design
Message-ID: <1991Mar28.214230.24386@rice.edu>
Date: 28 Mar 91 21:42:30 GMT
References: <11422.27ef7017@zeus.unomaha.edu> <15573@june.cs.washington.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: preston@ariel.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Lines: 21
Approved: compilers@iecc.cambridge.ma.us

david@cs.washington.edu (David Callahan) writes:

>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.

In Appendix 2 of

	Register Allocation via Graph Coloring
	Chaitin, Auslander, Chandra, Cocke, Hopkins, Markstein
	Computer Languages 6 (1981)

they give a proof that all graphs can arise in register allocation.
I won't repeat the proof, but in essence they show a systematic
way to construct a program with any desired interference graph.

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