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

[Daniel Berlin <dberlin at dberlin dot org>]

On Thursday, June 5, 2003, at 03:01  PM, Andrew MacLeod 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;
> > }
> >
> > To do this optimally, we do four things:
> >
> > 1. Insert a save at the end of the loop
> > 2. Insert a save before the loop
> > 3. Insert reloads in place of all the redundant expressions.
> > 4. Insert a phi for the two saves we made.
> >
> > So that the end code looks like:
> > <BLOCK 0>
> > pretmp_1 = a_4  + 3;
> > while (1)
> > {
> > <BLOCK 1>
> > 	pretmp_2 = PHI<pretmp_1 (0), pretmp_3 (13)>
> > 	b_9 = pretmp_2;
> > 	.... (uses of a_5 + 3 replaced with pretmp_2)
> > 	<BLOCK 13>
> > 	a_7 = 7;
> > 	pretmp_3 = a_7 + 3;
> > }
> >
> >
> > When we go to generate the save at pretmp_1, the only thing we have to
> > work with is the block we are in.  We don't have a handle to any "a_5 
> > + 3"'s or
> > anything, because none *exist at that point yet*.
>
> I still don't get it... maybe Im dense.  But looking for versions of a_
> seems wrong. You know from the PHI what variables actually reach the
> PHI.

But this isn't relevant to SSAPRE code insertion, only ESSA renaming 
(step 2 of SSAPRE).
We work on expressions, not variables.
The step i am referring to here is generation of regular SSA from the 
results of our ESSA redundancy elimination and whatnot.
Thus, we are generating a *new* phi, and it's *new* operands, for the 
PRE temporary for the *expression* "a_5 + 3".
That's what both the saves are, the new operands.
The only thing that cares about the fact that their is a phi of "a" 
there is the expression SSA renamer that is deciding the versions of 
expression SSA uses/defs.
Thus, the point is irrelevant, and taken care of.

> The PHI doesnt even have to have an a_ in it, it could be
>
>     a_5 = PHI <b_8(0), c_7(3)>
>
> so a_5 + 3 is going to have nothing to do with a_*
I'm not sure what you think this has to do with anything, but i'll note 
we substitute phi args into expressions when deciding on ESSA versions 
in order to get this right.
You keep trying to point out things related to renaming of expression 
SSA, i'm referring to code insertion.

> or there could be an overlapping range of a_ reaching the PHI. Maybe
> your PHI refers to a_4, but there could be a def of a_9 bewteen the PHI
> and the def of a_4..  wouldn't you find the a_9?

Yes, and that would be correct.
We want the current version of the variable as it exists at the end of 
the block.
If this is a_4, we want a_4.
If it's a_9, we want a_9.
Other steps of ESSA take care of making sure this invariant will always 
hold.

> SO I guess I dont understand what you are looking for...   I dont know
> how you can evaluate the expression without know what use of a variable
> is feeding the PHI...
This is taken care of in a different portion of SSAPRE.
At the point i'm referring to, we know everything we need to know.
We know where we need to save, and where we need to reload. We are just 
trying to do it.
This requires generating new expressions.
That requires getting the current versions of the variables in those 
expressions at the point at which they are to be inserted.


I could, technically, record it in other passes, but it seems a waste 
of structure space.

> Andrew