# Re: Short Graph Coloring Question

## Daniel Berlin <dan@dberlin.org>6 Apr 2002 22:52:14 -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: Daniel Berlin Newsgroups: comp.compilers Date: 6 Apr 2002 22:52:14 -0500 Organization: Compilers Central References: 02-03-201 Keywords: registers, optimize Posted-Date: 06 Apr 2002 22:52:13 EST

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.

They are one and the same.
Reducing the graph *is* allocating into registers.

As you reduce the graph, place the node you remove into a register. Mark
that register as used. No neighbors (ie if there is an edge between
them in the graph) can share the same register at the same time.
So if they aren't neighbors, they can be assigned the same
register.

So, for your example, let's say we have three registers, 1, 2, and 3

1. remove e (e->1)
2. remove d (d->1, doesn't interfere with e)
3. remove b (b->2, interferes with e)
4. remove a (a->3, interferes with e and b and d)
5. remove c (c->whoops, out of registers, it conflicts with d, b, a)

Okay, well, that didn't work, we'd have to spill a register.

Let's try it again, assigning slightly different registers.

1. e->1
2. d->2
3. b->2
4. a->3
5. c->1

That works.

Don't ask how a smart register allocator would know to do it in this
order. There are all kinds of complex strategies, based on splitting and
coalescing nodes.

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.