Thu, 28 Mar 91 21:42:30 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: | 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.