6 Apr 2002 22:52:14 -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: | Daniel Berlin <dan@dberlin.org> |

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.