6 Apr 2002 23:15:48 -0500

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) |

From: | "Mark Lacey \[MSFT\]" <mlacey@microsoft.com> |

Newsgroups: | comp.compilers |

Date: | 6 Apr 2002 23:15:48 -0500 |

Organization: | Compilers Central |

References: | 02-03-201 |

Keywords: | registers, optimize |

Posted-Date: | 06 Apr 2002 23:15:48 EST |

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.*

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.