Fri, 26 Oct 2007 12:29:27 -0500

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: | Peter Bergner <bergner@vnet.ibm.com> |

Newsgroups: | comp.compilers |

Date: | Fri, 26 Oct 2007 12:29:27 -0500 |

Organization: | Compilers Central |

References: | 07-10-047 |

Keywords: | registers |

Posted-Date: | 26 Oct 2007 23:28:44 EDT |

On Mon, 2007-10-15 at 14:37 +0530, Mohamed Shafi wrote:

*> 3. While calculating the spill cost, in the thesis Briggs has written*

*> the following*

*> for (r = k; r < ranges; r++) {*

*> ......*

*> ......*

*> range[r].cost - = range[r].copies;*

*> }*

*>*

*> What is the function of the variable range[r].copies ? i.e what*

*> exactly is this variable?*

I know Preston answered your question about what range[r].copies represents,

but I thought I'd comment on why he is subtracting it from the live range's

spill costs. This is due to a comment by Chaitin, that if you spill the

destination and/or source of a copy (eg, A = B), you can delete the copy.

So rather than generating:

/* Spilling B */ /* Spilling A */

load B, @<B's stack slot> A = B

A = B store A, @<A's stack slot>

... ...

we can generate the following instead:

/* Spilling B */ /* Spilling A */

load A, @<B's stack slot> store B, @<A's stack slot>

... ...

Having said that, there are some copies whose destination or source operands

have been spilled that cannot be eliminated this way (Chaitin never mentioned

this). The copies you cannot delete are the copies who have "close" uses that

follow the copy. If we attempt to delete the copy, then the following "close"

use of the spilled live range will use an uninitialized/random value.

Now this doesn't actually change the spill cost computation you showed above,

you still subtract range[r].copies from range[r].costs. What changes is when

you increment range[r].copies (I don't think Preston's thesis showed code for

updating range[r].copies). Instead of incrementing it for all copies that

mention the live range "r", you only increment it for copies that mention "r"

such that there is no following "close" use of "r". In Preston's pseudo code,

that is equivalent to testing that "r" is not in his neadLoad set, like so:

/* Handle definitions (Preston's thesis page 109). */

for (p=0; p<ik->defs; p++) {

r = i->parm[p];

if (i->kind == REG_COPY && !member(neadLoad, r))

range[r].copies += b->depth;

if (member(needLoad, r)) {

deleteMember(neadLoad, r));

if (!member(mustSpill, r)) range[r].infinite = TRUE;

}

range[r].stores += b->depth;

deleteMember(live, r);

}

Ditto similar code for uses.

Peter

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.