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

[Daniel Berlin <dberlin at dberlin dot org>]

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