|Short Graph Coloring Question email@example.com (Stephen Molloy) (2002-03-31)|
|Re: Short Graph Coloring Question firstname.lastname@example.org (Daniel Berlin) (2002-04-06)|
|Re: Short Graph Coloring Question email@example.com (Mark Lacey \[MSFT\]) (2002-04-06)|
|Re: Short Graph Coloring Question firstname.lastname@example.org (Amal Banerjee) (2002-04-06)|
|Re: Short Graph Coloring Question Sid-Ahmed-Ali.TOUATI@inria.fr (Sid Ahmed Ali TOUATI) (2002-04-13)|
|From:||Daniel Berlin <email@example.com>|
|Date:||6 Apr 2002 22:52:14 -0500|
|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
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.
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
Return to the
Search the comp.compilers archives again.