[tree-ssa]: Constant propagation into PHI's screws up IVR and PRE

[tree-ssa]: Constant propagation into PHI's screws up IVR and PRE

[Daniel Berlin]

As the subject says, constprop into phi's screws up both PRE and IVR.

Let me give an IVR example:

for (i = 0; i < 50; i++)

now becomes

i_4 = 0;
   while (1)
     {
       #   i_1 = PHI <0(0), i_7(10)>;


because of the propagated 0 in the phi, we can't properly detect i as 
an induction variable.
Why?
Trivial induction variables in SSA have the following property:
a phi of arity 2 in the loop body with one value coming from the same 
variable name in the loop pre-header, and one value coming from the 
same variable name in the loop latch.

We have no idea what variable caused that 0 to be propagated into the 
PHI. It's not necessarily "i".
So we can't call this an induction variable, because it might not 
really be one.
PRE has similar problems when trying to perform code motion and ESSA 
renaming.
I'm trying to extend PRE to handle it, but Open64 and the various 
SSAPRE papers just don't deal with it at all, because it never occurs 
for them.
--Dan

Re: [tree-ssa]: Constant propagation into PHI's screws up IVR and PRE

[Andrew MacLeod]

On Wed, 2003-07-30 at 11:29, Daniel Berlin wrote:
> As the subject says, constprop into phi's screws up both PRE and IVR.
> 
> Let me give an IVR example:
> 
> for (i = 0; i < 50; i++)
> 
> now becomes
> 
> i_4 = 0;
>    while (1)
>      {
>        #   i_1 = PHI <0(0), i_7(10)>;
> 
> 
> because of the propagated 0 in the phi, we can't properly detect i as 
> an induction variable.
> Why?
> Trivial induction variables in SSA have the following property:
> a phi of arity 2 in the loop body with one value coming from the same 
> variable name in the loop pre-header, and one value coming from the 
> same variable name in the loop latch.
> 
> We have no idea what variable caused that 0 to be propagated into the 
> PHI. It's not necessarily "i".

So does that mean if I have :

for (i = b; i< lim; i++)
  {
  }

where I have a PHI:


i_6 = a_3
..
i_9 = PHI <i_6(2), i_8(6)>

and we copy prop this, we end up with:

i_9 = PHI <a_3(2), i_8(6)>

So you wouldn't recognize that as an induction variable either?

I would think you ought to be able to tell that the edge from 2 is the
initialization edge, and it doesn't matter what value is there. The
important thing is you have an 'i' coming in from the back edge...

This kind of thing seems like it ought not be hard to detect, and its
really limiting not to be able to do so.   You are having the net effect
of saying "we cant do many optimization before IVR or PRE, or we cant
find anything"  And thats the opposite of what we're looking for.

Once we've done any kind of loop analysis, dont we mark that back edge
as a latch or something, and I presume that means we'd know that the
block the PHI is in is the top of loop, so it doesnt seem like it would
be very hard to detect that this is indeed an induction variable.

Andrew

Re: [tree-ssa]: Constant propagation into PHI's screws up IVR and PRE

[Daniel Berlin]

On Wednesday, July 30, 2003, at 12:36 PM, Andrew MacLeod wrote:

> On Wed, 2003-07-30 at 11:29, Daniel Berlin wrote:
>> As the subject says, constprop into phi's screws up both PRE and IVR.
>>
>> Let me give an IVR example:
>>
>> for (i = 0; i < 50; i++)
>>
>> now becomes
>>
>> i_4 = 0;
>>    while (1)
>>      {
>>        #   i_1 = PHI <0(0), i_7(10)>;
>>
>>
>> because of the propagated 0 in the phi, we can't properly detect i as
>> an induction variable.
>> Why?
>> Trivial induction variables in SSA have the following property:
>> a phi of arity 2 in the loop body with one value coming from the same
>> variable name in the loop pre-header, and one value coming from the
>> same variable name in the loop latch.
>>
>> We have no idea what variable caused that 0 to be propagated into the
>> PHI. It's not necessarily "i".
>
> So does that mean if I have :
>
> for (i = b; i< lim; i++)
>   {
>   }
>
> where I have a PHI:
>
>
> i_6 = a_3
> ..
> i_9 = PHI <i_6(2), i_8(6)>
>
> and we copy prop this, we end up with:
>
> i_9 = PHI <a_3(2), i_8(6)>
>
> So you wouldn't recognize that as an induction variable either?

Right.

>
> I would think you ought to be able to tell that the edge from 2 is the
> initialization edge, and it doesn't matter what value is there.
You can't, without knowing the original variable before propagation.
Otherwise you risk calling things that *aren't* induction variables, 
induction variables.
Which we can't get, since DCE will remove the original set now that 
it's useless.
In the i = 0 case, the set of i = 0 will be completely removed, so we 
have *zero* way of telling what the original variable was.


> The
> important thing is you have an 'i' coming in from the back edge...

This is a necessary, but not sufficient condition to detect induction 
variables.

See Michael Wolfe's paper on induction variable detection in SSA form.

> This kind of thing seems like it ought not be hard to detect, and its
> really limiting not to be able to do so.   You are having the net 
> effect
> of saying "we cant do many optimization before IVR or PRE, or we cant
> find anything"

No, we can record what the variable in the phi was before const/copy 
prop, and that would solve the problem.
>

Re: [tree-ssa]: Constant propagation into PHI's screws up IVR and PRE

[Pop Sébastian]

On Wed, Jul 30, 2003 at 12:47:41PM -0400, Daniel Berlin wrote:
> >
> >I would think you ought to be able to tell that the edge from 2 is the
> >initialization edge, and it doesn't matter what value is there.
> You can't, without knowing the original variable before propagation.
> Otherwise you risk calling things that *aren't* induction variables, 
> induction variables.
I don't think so.  Do you have an example?

One of the values comes from a nesting level less than that of the loop's
phi-node, and this is the initial value of the IV.  The other value comes
from a nesting level greater or equal to the loops phi node, and this is 
the evolution part.  The initial condition is the only argument that 
could contain a constant (after CCP), the other argument points to the 
update assignment in the current loop nest.

> Which we can't get, since DCE will remove the original set now that 
> it's useless.
> In the i = 0 case, the set of i = 0 will be completely removed, so we 
> have *zero* way of telling what the original variable was.
> 
???
The phi node does contain the initial condition for the variable i:

   #   i_1 = PHI <0(0), i_7(10)>;
initial condition ^^^^

The other pointer (i_7) is necessarily nested in the current loop.

Re: [tree-ssa]: Constant propagation into PHI's screws up IVR and PRE

[Daniel Berlin]

On Wednesday, July 30, 2003, at 2:20 PM, Pop Sébastian wrote:

> On Wed, Jul 30, 2003 at 12:47:41PM -0400, Daniel Berlin wrote:
>>>
>>> I would think you ought to be able to tell that the edge from 2 is 
>>> the
>>> initialization edge, and it doesn't matter what value is there.
>> You can't, without knowing the original variable before propagation.
>> Otherwise you risk calling things that *aren't* induction variables,
>> induction variables.
> I don't think so.  Do you have an example?

Somewhere.
>
> One of the values comes from a nesting level less than that of the 
> loop's
> phi-node, and this is the initial value of the IV.  The other value 
> comes
> from a nesting level greater or equal to the loops phi node, and this 
> is
> the evolution part.  The initial condition is the only argument that
> could contain a constant (after CCP),

If you are positive about this, it's good enough for me.
I'll change the test I was using to account for it.

> the other argument points to the
> update assignment in the current loop nest.
>
>> Which we can't get, since DCE will remove the original set now that
>> it's useless.
>> In the i = 0 case, the set of i = 0 will be completely removed, so we
>> have *zero* way of telling what the original variable was.
>>
> ???
> The phi node does contain the initial condition for the variable i:
>
>    #   i_1 = PHI <0(0), i_7(10)>;
> initial condition ^^^^


> The other pointer (i_7) is necessarily nested in the current loop.

Re: [tree-ssa]: Constant propagation into PHI's screws up IVR and PRE

[Pop Sébastian]

On Wed, Jul 30, 2003 at 02:33:57PM -0400, Daniel Berlin wrote:
> 
> >the evolution part.  The initial condition is the only argument that
> >could contain a constant (after CCP),
> 
> If you are positive about this, it's good enough for me.
Yes.  

This even simplifies the work of the IV analyzer.
The IVA has to follow the branch out of the loop for computing the 
initial condition.  But in my opinion this is not to the IVA to approximate
the initial conditions, but this has to be computed by a classic constant 
propagation slightly adapted to propagate intervals instead of just constants.
(call it CCPI for example).

If the initial condition is not computable, or hard to compute, then 
the CCPI approximates it with the unknown element of the lattice ie. [-oo, +oo].