15 Dec 2001 00:36:08 -0500

Related articles |
---|

old register allocators by coloring Sid-Ahmed-Ali.TOUATI@inria.fr (Sid Ahmed Ali TOUATI) (2001-11-25) |

Re: old register allocators by coloring thp@cs.ucr.edu (2001-12-15) |

From: | thp@cs.ucr.edu |

Newsgroups: | comp.compilers |

Date: | 15 Dec 2001 00:36:08 -0500 |

Organization: | University of California, Riverside |

References: | 01-11-108 |

Keywords: | registers, optimize |

Posted-Date: | 15 Dec 2001 00:36:08 EST |

Sid Ahmed Ali TOUATI <Sid-Ahmed-Ali.TOUATI@inria.fr> wrote:

[...]

*: My question is about the coloring methods (Chaitin, Chow, etc...) for*

*: register allocation. They generally make at first a live range*

*: analysis step to build an interference graph. After, they try to color*

*: it with some heuristics. I don't understand why they use heuristics*

*: here : if we assume some live range schemes, so we have live*

*: intervals. We can buid an interval graph : looking for a maximal*

*: clique is not NP-complete in such a graph (and hence the dual coloring*

*: problem is also easy). Why do they use heuristics here ?*

In general, the problem of telling whether or not a graph contains a

k-node clique is NP-complete. Finding a maximal clique solves the

problem of telling whether there is a k-clique, so finding a maximal

clique is as hard. (I think this is covered in the book by Gary and

Johnson.)

Tom Payne

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.