# Re: Short Graph Coloring Question

## Amal Banerjee <dakupoto@ece.utexas.edu>6 Apr 2002 23:41:32 -0500

From comp.compilers

Related articles
Short Graph Coloring Question chiefwiggum@eircom.net (Stephen Molloy) (2002-03-31)
Re: Short Graph Coloring Question dan@dberlin.org (Daniel Berlin) (2002-04-06)
Re: Short Graph Coloring Question mlacey@microsoft.com (Mark Lacey \[MSFT\]) (2002-04-06)
Re: Short Graph Coloring Question dakupoto@ece.utexas.edu (Amal Banerjee) (2002-04-06)
Re: Short Graph Coloring Question Sid-Ahmed-Ali.TOUATI@inria.fr (Sid Ahmed Ali TOUATI) (2002-04-13)
| List of all articles for this month |

 From: Amal Banerjee Newsgroups: comp.compilers Date: 6 Apr 2002 23:41:32 -0500 Organization: The University of Texas at Austin; Austin, Texas References: 02-03-201 Keywords: registers, optimize Posted-Date: 06 Apr 2002 23:41:32 EST

Well,
It looks like you have all the nodes on the stack. So, by
Chaitin's algorithm, pop them off the stack and color them.

On 31 Mar 2002, Stephen Molloy wrote:

> Graph Coloring Short Question
>
> Interference Information
>
> Variable | Interferes With
> a | b,c,d,e
> b | a,c,e
> c | a,b,d
> d | a,c
> e | a,b
>
> Show with graph coloring how we can put them in three registers?
>
> Remove any node with less than K edges (K=3)
>
> 1. remove e
> 2. remove d
> 3. remove b
> 4. remove a
> 5. remove c
>
> How do we get from here to register allocation?
>
> I'm looking for the method not the answer, just a part of the method
> I'm looking for - the bit where you go from reducing the graph to
> allocating into registers.

Post a followup to this message