Re: Is register allocation really NP-Complete?

preston@ariel.rice.edu (Preston Briggs)
Thu, 28 Mar 91 21:42:30 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: preston@ariel.rice.edu (Preston Briggs)
Keywords: optimization, theory, design
Organization: Rice University, Houston
References: <11422.27ef7017@zeus.unomaha.edu> <15573@june.cs.washington.edu>
Date: Thu, 28 Mar 91 21:42:30 GMT

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

Post a followup to this message

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