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
Return to the
comp.compilers page.
Search the
comp.compilers archives again.