Re: Few Doubts about register allocation via Graph colouring [Briggs thesis]

Peter Bergner <bergner@vnet.ibm.com>
Fri, 26 Oct 2007 12:29:27 -0500

          From comp.compilers

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)
| List of all articles for this month |

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

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.