Re: [tree-ssa]: Easy way to get default def of a variable?

[Daniel Berlin <dberlin at dberlin dot org>]

On Thu, 5 Jun 2003, Diego Novillo wrote:

> On Thu, 2003-06-05 at 14:27, Daniel Berlin wrote:
>
> > The code is a bit complicated, so i'll simplify it.
> > Given:
> > <BLOCK 0>
> >
> > while (1)
> > {
> > 	<BLOCK 1>
> > 	a_5 = PHI <a_4 (0) <<<<< The default def, a_7 (13)>
> >         b_9 = a_5 + 3;
> > 	... (More uses of a_5 + 3)
> > 	<BLOCK 13>
> > 	a_7 = 7;
> > }
> >
> I think I'm starting to understand.  Let me reiterate to see if I'm on
> the right track.  It's been a few years since I read about PRE:
>
> We are creating an expression variable 'pretmp' for a_X + 3 with the
> intent of replacing uses of a_X + 3 with 'pretmp' and reduce the number
> of times we compute new values for 'pretmp'.
Right.

>
> So, we need to have an initial definition for 'pretmp' that we place as
> early as possible, I guess.  At this point we need to emit 'pretmp_i =
> a_j + 3'.  That 'a_j' is the one you need to find.

Right.

>
> In this case, we want the very first computation of 'pretmp_i = a_j + 3'
> to happen outside the loop.  Since 'a_5' is not created until we are
> inside the loop, we cannot use it, and so we start looking up in the
> dominator tree until we find a version of 'a' that we can use.  In this
> case you will find nothing because 'a_4' appears out of thin air (it's a
> default definition).  And that's why you want a table that for each
> variable tells you which is its default definition.

Exactly!
>
> Could we not examine the arguments to the PHI node in block 1?

Well, not until it finds nothing (since we start in block 0, where we
want to insert, we'll never hit block 1 walking the dom tree), then we
could start anywhere we know a definition exists when trying to find the
default def.


>  Find the
> argument that comes out of the loop and use that.  I guess not.  IIRC
> the insertion points in PRE was all generic code that didn't have a lot
> of context.
Right.

>
> The other insertions of 'pretmp_i = a_j + 3' need to happen at points
> where new versions of 'a_j' are created.  So, if no new versions of 'a'
> are created inside the loop (i.e., if 'a_7 = 7' didn't exist), PRE has
> effectively removed loop invariant code outside its body.  Cool.
>
> In this case, I'll just play devil's advocate and point out that since
> 'a' was indeed changed inside the loop, all PRE did was generate more
> code.

Actually, it did remove the *other* computations of a_5 + 3 that did
occur (Note that line "more uses of a_5 + 3").
:)
It also allowed it to be computed once outside the loop (for the first
iteration), which may help.


> Total redundancy elimination would've just replaced 'a_5 + 3'
> with b_9.  But don't mind me, I'm only teasing ;)

:P


>
>
> Diego.
>
>