Wed, 27 Mar 91 14:20:19 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: | larus@cs.wisc.edu |

Keywords: | optimization, theory, design |

Organization: | U of Wisconsin CS Dept |

References: | <11422.27ef7017@zeus.unomaha.edu> |

Date: | Wed, 27 Mar 91 14:20:19 GMT |

Graph coloring for general graphs is NP-complete. There may be special

cases (such as interval graphs and circular-arc graphs) for which

efficient algorithms exists, but no one has shown their relevance for

register allocation (hint, hint). NB, a register allocator has an

additional constraint beyond a graph colorer. The allocator cannot throw

up its hands and quit when a graph is not 16 or 32 colorable.

And, yes both Chaitin's and Chow's algorithms are heuristics. There is no

guarantee that they achieve optimal colorings. The only promise is that

they can color all graphs (which they may modify in the process by

introducing spill code).

/Jim

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.