Re: old register allocators by coloring

thp@cs.ucr.edu
15 Dec 2001 00:36:08 -0500

          From comp.compilers

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)
| List of all articles for this month |

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.