Thu, 18 Oct 2007 17:37:49 -0000

Related articles |
---|

Few Doubts about register allocation via Graph colouring [Briggs thesi shafitvm@gmail.com (Mohamed Shafi) (2007-10-15) |

Re: Few Doubts about register allocation via Graph colouring [Briggs t preston.briggs@gmail.com (preston.briggs@gmail.com) (2007-10-15) |

Re: Few Doubts about register allocation via Graph colouring [Briggs t shafitvm@gmail.com (shafi) (2007-10-18) |

Re: Few Doubts about register allocation via Graph colouring [Briggs t preston.briggs@gmail.com (preston.briggs@gmail.com) (2007-10-18) |

Re: Few Doubts about register allocation via Graph colouring [Briggs t bergner@vnet.ibm.com (Peter Bergner) (2007-10-26) |

From: | "preston.briggs@gmail.com" <preston.briggs@gmail.com> |

Newsgroups: | comp.compilers |

Date: | Thu, 18 Oct 2007 17:37:49 -0000 |

Organization: | Compilers Central |

References: | 07-10-04707-10-059 |

Keywords: | registers |

Posted-Date: | 18 Oct 2007 15:19:44 EDT |

On Oct 18, 6:20 am, shafi <shafi...@gmail.com> wrote:

*> I was asking about live ranges with infinite spill cost and "high"*

*> degree. The pseudo code the follows the above description in your*

*> thesis doesn't mention about such live ranges. But still they have to*

*> be pushed. So again since they have to get a register should they be*

*> pushed on to the stack at the end?*

In the English description associated with the pseudocode

(2nd paragraph of section 8.8, near the bottom of page 110),

it says: "Nodes of high degree and infinite spill cost [...] are not

included in either set."

At the top of page 111, I note: "To remove a node m from the graph, we

visit each neighbor n [...] and decrement its degree. If the new

degree of n is k - 1, then n is removed from high and added to low."

This last sentence is key. Perhaps I should have written it like

this: "If the new degree of n is k - 1, then n is added to low and, if

it is present in high, it is removed."

You see, the set high is used to hold nodes we'll want to search

through for spill candidates. Nodes of infinite spill cost are not

spill candidates, so they don't ever get added to high. But any node

whose degree is eventually reduced to less than k is added to the set

low (the only nodes that are never members of low are nodes that are

chosen as spill candidates).

Every node eventually appears on the stack.

Probably my choice of names for "low" and "high" was poor. The

important thing is to remember that the two sets do not partition all

the nodes in the graph. Instead, each of the two sets serves a

particular purpose. Low holds nodes that can be immediately removed

from the graph. High holds nodes that we will search among for spill

candidates.

Hope this helps,

Preston

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.