Re: Is register allocation really NP-Complete?

david@cs.washington.edu (David Callahan)27 Mar 91 16:01:36 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: david@cs.washington.edu (David Callahan) Keywords: optimization, theory, design Organization: Tera Computer Co., Seattle WA References: <11422.27ef7017@zeus.unomaha.edu> Date: 27 Mar 91 16:01:36 GMT

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

Post a followup to this message