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

[Diego Novillo]

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'.

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.

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.

Could we not examine the arguments to the PHI node in block 1?  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.

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.  Total redundancy elimination would've just replaced 'a_5 + 3'
with b_9.  But don't mind me, I'm only teasing ;)


Diego.