Re: Short Graph Coloring Question

If you're trying to understand basic graph coloring you should get a
copy of "Register allocation via coloring" by Chaitin, et al. as well
as the follow-up paper "Register allocation and spilling via graph
coloring.". If you want to know more about register
allocation...well, lets say that there have been a lot of papers
written in the last twenty years that cover a lot of ground.


The basic idea is that as you remove nodes from the graph you push
them on a stack. Everything on the stack is definitely colorable if
you assign registers in the order you'd pop them off the stack (why is
this true - well, think about it for awhile and/or grab those papers
for some insight). As you assign registers you make sure that the
"color" you pick is different than any assigned to neighbors in the
graph that have already been assigned. The rest is just engineering
:).


The second paper mentioned above considers what to do if the graph isn't
colorable with the number of registers available.


A paper by Briggs that came several years later discussed "optimistic"
coloring which modifies the flow-graph in a way where you optimistically
assume that a graph that isn't trivially colorable isn't necessarily
uncolorable (it depends on the actual register assignments). I don't recall
the exact paper, but do recall that it's covered in his Thesis (Preson
Briggs, Rice University).


--
Mark Lacey
mlacey at microsoft dot com
Microsoft Visual C++ Program Management
This posting is provided "AS IS" with no warranties, and confers no rights.




"Stephen Molloy" <chiefwiggum@eircom.net> wrote in message
> 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.

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