|Is register allocation really NP-Complete? email@example.com (1991-03-26)|
|Re: Is register allocation really NP-Complete? firstname.lastname@example.org (1991-03-27)|
|Re: Is register allocation really NP-Complete? email@example.com (1991-03-27)|
|Re: Is register allocation really NP-Complete? firstname.lastname@example.org (1991-03-27)|
|Re: Is register allocation really NP-Complete? email@example.com (1991-03-28)|
|Re: Is register allocation really NP-Complete? firstname.lastname@example.org (1991-03-31)|
|From:||email@example.com (David Callahan)|
|Keywords:||optimization, theory, design|
|Organization:||Tera Computer Co., Seattle WA|
|Date:||27 Mar 91 16:01:36 GMT|
In article <firstname.lastname@example.org> email@example.com (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
Conflict graphs, even coarse ones such as Chow constructs, are not
interval graphs. Consider the fragment:
l: ... = B
... = A
... = C
Note that the live range of B is discontiguous due to the control flow.
These live ranges might be viewed as:
BB CCC B
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 (firstname.lastname@example.org, email@example.com,firstname.lastname@example.org)
Tera Computer Co. 400 North 34th Street Seattle WA, 98103
Return to the
Search the comp.compilers archives again.