Re: Bug 14562 : copyrename & PRE

[Daniel Berlin <dberlin at dberlin dot org>]

On Mon, 15 Mar 2004, Andrew MacLeod wrote:

> On Mon, 2004-03-15 at 12:58, Daniel Berlin wrote:
> > > >
> > > > It probably wouldn't take long for you to see what wrong. Either its
> > > > something I did about PARM_DECLs, or an assumption PRE is making, Im not
> > > > sure which.
> > >
> > > I'll check it out
> > >
> >
> > It looks like we have two occurrences of the expression with copyrename,
> > and one without it.
> >
> >  EUSE (k_29 * 4) [class:1 phiop:0 bb:1 ]
> >  EUSE (k_29 * 4) [class:2 phiop:0 bb:1 ]
> >  EUSE () [class:-1 phiop:1 bb:6 ]
> >  EUSE () [class:-1 phiop:1 bb:5 ]
> >
> > without copyrename:
> >
> >  EUSE (T.1_29 * 4) [class:2 phiop:0 bb:1 ]
> >  EUSE () [class:-1 phiop:1 bb:4 ]
> >  EUSE () [class:-1 phiop:1 bb:3 ]
> >
> >
> > PRE is not value based (right now, i'm working on a GVN-PRE algorithm), so
> > this is why it picks it up when you have k, but not T (because in one case
> > you have one k * 4 expression, and one t * 4 expression, and in the other
> > case you have two k * 4 expressions)
> >
> > The results of PRE look fine given the code in both cases (in one case,
> > the expression we are looking at is modified in between the phi and the
> > use, and in the other case, it isn't, because we are picking up the extra
> > expression, and that's the one getting optimized).
> >
> > Do you see something actually wrong with the code PRE is producing?
> >
>
> No, I was wondering why it triggers. There shouldn't be any more uses of
> k_29 than there were of T.1_29. copyrename simply replaces T.1_29 with
> k_29. Why do you get two occurrences after the transformation?

Because our current PRE (and all PRE's except the one that i'm working
on now, AFAIK, and a weird one based on a Value Name Graph) are
based on lexical equivalence, not value based equivalence.

IE a_50 * b_30 and a_30 * b_50 are considered "lexically equivalent"

a_50 * b_30 and c_30 * b_50 are not, even if you had c_30 = a_30 right
before every use of c_30.  (IE even if they had the same value).


Before the transformation, you have:
  T.6<D1061>_13 = k<D1047>_26 * 4;
...
  T.2<D1056>_42 = T.1<D1055>_41 * 4;

one lexical occurrence of k * 4, one lexical occurrence of T.1 * 4.

after, you have
<L0>:;
  T.6<D1061>_13 = k<D1047>_26 * 4;
...
  T.2<D1056>_42 = k<D1047>_41 * 4;

two lexical occurrences of k * 4.

> whats the 'class' thing?

ESSA version.

>There seems to be a class 1 use of k_29 that
> doesnt exist when its T.1_29.
That's my point.
PRE sees another lexical occurrence when you give the variables new names.

This is one of the problems with the current SSAPRE algorithm, and most
PRE algorithms, and the reason there is work to unify global value
numbering and PRE - many more optimization opportunities.

 >
> -fno-tree-pre makes it work, for what thats worth, so I figured it might
> have something to do with the extra stuff PRE is doing...
>
So does -fno-tree-dominator-opts, etc.
:)

I looked at the code PRE generates for optimizing that expression by eye,
and it looks okay to me.