27 Mar 91 16:01:36 GMT

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

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.