Re: Short Graph Coloring Question

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.

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