Bug 14562 : copyrename & PRE

Bug 14562 : copyrename & PRE

[Andrew MacLeod]

copyrename doesnt *appear* to be doing anything wrong. 

The original program had:

  T.1<D1071>_29 = k<D1063>_2 - h<D1062>_5;
  T.2<D1072>_30 = T.1<D1071>_29 * 4;

and copy rename decided that version _29 would be better off as a 'k',
so it produces:

  k<D1063>_29 = k<D1063>_2 - h<D1062>_5;
  T.2<D1072>_30 = k<D1063>_29 * 4;

and PRE decides that worth doing something with:

  k<D1063>_29 = k<D1063>_2 - h<D1062>_5;
  pretmp.18<D1129>_50 = k<D1063>_29 * 4;
  T.2<D1072>_30 = pretmp.18<D1129>_50;

In the -fno-tree-copyrename version, PRE doesn't touch T.1_29... but it
does when it becomes 'k'.
 
Do we have magic rules about PARMs where they aren't allowed to be
assign to? 'k' is a PARM, and PRE appears to be make an assumption about
it. Up until now we haven't really been seeing a DEF of a PARM, its
always been into a temp variable.

Is there something about PARMs that I ought not allow a rename on the
LHS to a PARM, or is PRE making a bad assumption?

Andrew

Re: Bug 14562 : copyrename & PRE

[Daniel Berlin]

 On Mar 15, 2004, at 10:36 AM, Andrew MacLeod wrote:

 >
 > copyrename doesnt *appear* to be doing anything wrong.
 >
 > The original program had:
 >
 >   T.1<D1071>_29 = k<D1063>_2 - h<D1062>_5;
 >   T.2<D1072>_30 = T.1<D1071>_29 * 4;
 >
 > and copy rename decided that version _29 would be better off as a 'k',
 > so it produces:>
 >
 >   k<D1063>_29 = k<D1063>_2 - h<D1062>_5;
 >   T.2<D1072>_30 = k<D1063>_29 * 4;
 >
 > and PRE decides that worth doing something with:
 >
 >   k<D1063>_29 = k<D1063>_2 - h<D1062>_5;
 >   pretmp.18<D1129>_50 = k<D1063>_29 * 4;
 >   T.2<D1072>_30 = pretmp.18<D1129>_50;
 >
 > In the -fno-tree-copyrename version, PRE doesn't touch T.1_29... but it
 > does when it becomes 'k'.
 >
 Because PARM_DECL's don't have a bb_for_stmt(SSA_NAME_DEF_STMT
 (PARM_DECL)), we special case them in PRE when it comes to seeing if
 they are actually undefined or not.

 In reality, they should have a bb_for_stmt (SSA_NAME_DEF_STMT
 (parm_decl)) of ENTRY_BLOCK_PTR for those live on entry, and proper
 bb_for_stmt (SSA_NAME_DEF_STMT (parm_decl)) for others.

 People seemed to agree with this (Richard and Jeff, IIRC), i just never
 got around to it.

 The code in question that treats PARM_DECL special is:


    /* This guards against moving around undefined variables.
     However, PARM_DECL is special because it *IS* live on entry,
     so it's not really undefined.  */
        if (!defbb && TREE_CODE (SSA_NAME_VAR (use)) != PARM_DECL)
    return true;
        else if (!defbb && TREE_CODE (SSA_NAME_VAR (use)) == PARM_DECL)
          return false;
        if (dominated_by_p (CDI_DOMINATORS, bb, defbb))
    return false;


 Does copyrename make this no longer true somehow?
 If so, we probably should just make the bb_for_stmt (SSA_NAME_DEF_STMT
 (PARM_DECL)) be ENTRY_BLOCK_PTR when it is approriate, and stop special
 casing them, which is probably causing this bug.

 This is the only place we special case PARM_DECL in all of PRE.

 There is a test in the tree-ssa testsuite to make sure we perform
 SSAPRE PARM_DECL's properly that was committed when the above
 workaround was committed.

 > Do we have magic rules about PARMs where they aren't allowed to be
 > assign to? 'k' is a PARM, and PRE appears to be make an assumption
 > about
 > it. Up until now we haven't really been seeing a DEF of a PARM, its
 > always been into a temp variable.
 >
 > Is there something about PARMs that I ought not allow a rename on the
 > LHS to a PARM, or is PRE making a bad assumption?
 >
 > Andrew
 >

Re: Bug 14562 : copyrename & PRE

[Andrew MacLeod]

On Mon, 2004-03-15 at 11:17, Daniel Berlin wrote:
>  On Mar 15, 2004, at 10:36 AM, Andrew MacLeod wrote:

>  Because PARM_DECL's don't have a bb_for_stmt(SSA_NAME_DEF_STMT
>  (PARM_DECL)), we special case them in PRE when it comes to seeing if
>  they are actually undefined or not.
> 
>  In reality, they should have a bb_for_stmt (SSA_NAME_DEF_STMT
>  (parm_decl)) of ENTRY_BLOCK_PTR for those live on entry, and proper
>  bb_for_stmt (SSA_NAME_DEF_STMT (parm_decl)) for others.
> 
>  People seemed to agree with this (Richard and Jeff, IIRC), i just never
>  got around to it.
> 

Yes, I agree it ought to be this way. 
>  The code in question that treats PARM_DECL special is:
> 
> 
>     /* This guards against moving around undefined variables.
>      However, PARM_DECL is special because it *IS* live on entry,
>      so it's not really undefined.  */
>         if (!defbb && TREE_CODE (SSA_NAME_VAR (use)) != PARM_DECL)
>     return true;
>         else if (!defbb && TREE_CODE (SSA_NAME_VAR (use)) == PARM_DECL)
>           return false;
>         if (dominated_by_p (CDI_DOMINATORS, bb, defbb))
>     return false;
> 
> 
>  Does copyrename make this no longer true somehow?
Did you ever make adjustments when default_def() was introduced? We have
a situation here where some versions of 'k' have default_dfef() set
because they are the incoming default value, and are live on entry.

Copy rename has in this case added a new defintion of 'k', k_29, which
although the base variable is a PARM, it does have a defined block.
>  If so, we probably should just make the bb_for_stmt (SSA_NAME_DEF_STMT
>  (PARM_DECL)) be ENTRY_BLOCK_PTR when it is approriate, and stop special
>  casing them, which is probably causing this bug.
> 

Maybe... I dont think thats this problem. But maybe it is :-)

>  This is the only place we special case PARM_DECL in all of PRE.
> 

Well, dont you try to reconstruct expressions based on the base variable
or something at some point?

We have a case where we have a PARM_DECL 'k', and there are 2 PHI nodes
in one block for K
# k<D1063>_1 = PHI <k<D1063>_29(0), k<D1063>_41(1)>;
# k<D1063>_26 = PHI <k<D1063>_2(0), k<D1063>_39(1)>;

and PRE makes one of them go away... Maybe you ought to take a quick
look at the test case, its not a very big one, and you understand PRE
far better than I.
The only transformation difference that matters (I think :-), is that
copyrename has renamed T.1_29 to be k_29.  It changed the base variable
for version 29 to 'k'. And PRE decided it should do something to it, and
appears to do something wrong.

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.


Maybe pre has done things OK, and someone later is screwing it up, but
that fact the PRE looks at this expression now, and it didnt before
makes me suspicious :-)

Thanks

Andrew

Re: Bug 14562 : copyrename & PRE

[Daniel Berlin]

> >  People seemed to agree with this (Richard and Jeff, IIRC), i just never
> >  got around to it.
> >
>
> Yes, I agree it ought to be this way.
> >  Does copyrename make this no longer true somehow?
> Did you ever make adjustments when default_def() was introduced?

Not that i'm aware of :)
> We have
> a situation here where some versions of 'k' have default_dfef() set
> because they are the incoming default value, and are live on entry.

Ah.
This might be the problem then.

> Maybe... I dont think thats this problem. But maybe it is :-)

It's the only reason PRE would touch the PARM_DECL now and not touch it
before.

> >  This is the only place we special case PARM_DECL in all of PRE.
> >
>
> Well, dont you try to reconstruct expressions based on the base variable
> or something at some point?
We translate through PHIs, but this won't be affected by PARM_DECL at all.

>
> We have a case where we have a PARM_DECL 'k', and there are 2 PHI nodes
> in one block for K
> # k<D1063>_1 = PHI <k<D1063>_29(0), k<D1063>_41(1)>;
> # k<D1063>_26 = PHI <k<D1063>_2(0), k<D1063>_39(1)>;
>
> and PRE makes one of them go away... Maybe you ought to take a quick
> look at the test case, its not a very big one, and you understand PRE
> far better than I.

Sure.

> The only transformation difference that matters (I think :-), is that
> copyrename has renamed T.1_29 to be k_29.  It changed the base variable
> for version 29 to 'k'. And PRE decided it should do something to it, and
> appears to do something wrong.
>
> 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

Re: Bug 14562 : copyrename & PRE

[Daniel Berlin]

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

Re: Bug 14562 : copyrename & PRE

[Andrew MacLeod]

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?

whats the 'class' thing? There seems to be a class 1 use of k_29 that
doesnt exist when its T.1_29.

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

Andrew

Re: Bug 14562 : copyrename & PRE

[Daniel Berlin]

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.

Re: Bug 14562 : copyrename & PRE

[Andrew MacLeod]

On Mon, 2004-03-15 at 13:27, Daniel Berlin wrote:
> 
> 

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

even tho k_41 has absolutely nothing to do with the 'k' in k_26 eh.

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

OK, I'll see if I can see anyone else doing something bad then. someone
is getting confused :-)

Thanks.

Andrew

Re: Bug 14562 : copyrename & PRE

[Daniel Berlin]

On Mon, 15 Mar 2004, Andrew MacLeod wrote:

> On Mon, 2004-03-15 at 13:27, Daniel Berlin wrote:
> >
> >
>
> >
> > 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.
> >
>
> even tho k_41 has absolutely nothing to do with the 'k' in k_26 eh.

yes.
Braindead, i know.

This isn't as big a problem in other compilers because they don't have as
many different named temporaries for variables.

IE copyrename should improve PRE effectiveness in a lot of cases, at least
until we have GVN-PRE.

> > I looked at the code PRE generates for optimizing that expression by eye,
> > and it looks okay to me.
>
> OK, I'll see if I can see anyone else doing something bad then. someone
> is getting confused :-)

:P
It still could be PRE, and i'm just missing it.
But i traced the replacements it made by hand, and looked at the resulting
code, and it looks like it should be okay.

Re: Bug 14562 : copyrename & PRE

[Andrew MacLeod]

On Mon, 2004-03-15 at 13:52, Daniel Berlin wrote:
> 
> 
> On Mon, 15 Mar 2004, Andrew MacLeod wrote:
> 

> 
> IE copyrename should improve PRE effectiveness in a lot of cases, at least
> until we have GVN-PRE.
> 
Yeah, I noticed in the new version it made things better. TOo bad we're
doing something wrong :-)

> > > I looked at the code PRE generates for optimizing that expression by eye,
> > > and it looks okay to me.
> >
> > OK, I'll see if I can see anyone else doing something bad then. someone
> > is getting confused :-)
> 
> :P
> It still could be PRE, and i'm just missing it.
> But i traced the replacements it made by hand, and looked at the resulting
> code, and it looks like it should be okay.
> 
OK, I think I have it.

THe incoming definition is:


  k<D1063>_29 = k<D1063>_2 - h<D1062>_5;
  T.2<D1072>_30 = k<D1063>_29 * 4;
 <...>
  # T.3<D1073>_23 = PHI <T.3<D1073>_31(0), T.3<D1073>_43(1)>;
  # k<D1063>_1 = PHI <k<D1063>_29(0), k<D1063>_41(1)>;
  # k<D1063>_26 = PHI <k<D1063>_2(0), k<D1063>_1(1)>;
<L0>:;
  T.6<D1077>_13 = k<D1063>_26 * 4;
  


The problem is T.6_13... PRE changes this to:

  k<D1063>_29 = k<D1063>_2 - h<D1062>_5;
  pretmp.18<D1129>_50 = k<D1063>_29 * 4;
  T.2<D1072>_30 = pretmp.18<D1129>_50;
 <...>
  # T.3<D1073>_23 = PHI <T.3<D1073>_31(3), T.3<D1073>_43(6)>;
  # k<D1063>_1 = PHI <k<D1063>_29(3), k<D1063>_41(6)>;
  # k<D1063>_26 = PHI <k<D1063>_2(3), k<D1063>_1(6)>;
  # pretmp.18<D1129>_48 = PHI <pretmp.18<D1129>_50(3),
pretmp.18<D1129>_51(6)>;
  # pretmp.19<D1130>_52 = PHI <pretmp.19<D1130>_54(3),
pretmp.19<D1130>_55(6)>;
<L0>:;
  T.6<D1077>_13 = pretmp.18<D1129>_48;

I think the problem is the entry into the loop from block 0 (or BB 3
iafter PRE)

the original stmt:
T.6_13 = k<D1063>_26 * 4;

k_26 is defined as k_2 coming in from block 0 in the original program,
so T.6_13 would be k_2 * 4.

Perhaps its because k_29 is defined in block 0, that PRE somehows thinks
thats the reaching definition of 'k', but PRE will calculate this the
first time  as pretmp.18_48, which is defined as pretmp.18_50 on the
initial path, which has a value of 
pretmp.18_50 = k_29 * 4
which is actually:
pretmp.18_50 = (k_2 - h_5) * 4

So we are getting the wrong value the first time into the loop. we're
using the wrong k...

Andrew

Am I reading that correctly?

Andrew
 

Coming in from 

Re: Bug 14562 : copyrename & PRE

[Daniel Berlin]

> >
>
> >
> > IE copyrename should improve PRE effectiveness in a lot of cases, at least
> > until we have GVN-PRE.
> >
> Yeah, I noticed in the new version it made things better. TOo bad we're
> doing something wrong :-)
>
> > > > I looked at the code PRE generates for optimizing that expression by eye,
> > > > and it looks okay to me.
> > >
> > > OK, I'll see if I can see anyone else doing something bad then. someone
> > > is getting confused :-)
> >
> > :P
> > It still could be PRE, and i'm just missing it.
> > But i traced the replacements it made by hand, and looked at the resulting
> > code, and it looks like it should be okay.
> >
> OK, I think I have it.
>
> THe incoming definition is:
>
>
>   k<D1063>_29 = k<D1063>_2 - h<D1062>_5;
>   T.2<D1072>_30 = k<D1063>_29 * 4;
>  <...>
>   # T.3<D1073>_23 = PHI <T.3<D1073>_31(0), T.3<D1073>_43(1)>;
>   # k<D1063>_1 = PHI <k<D1063>_29(0), k<D1063>_41(1)>;
>   # k<D1063>_26 = PHI <k<D1063>_2(0), k<D1063>_1(1)>;
> <L0>:;
>   T.6<D1077>_13 = k<D1063>_26 * 4;
>
>
>
> The problem is T.6_13... PRE changes this to:
>
>   k<D1063>_29 = k<D1063>_2 - h<D1062>_5;
>   pretmp.18<D1129>_50 = k<D1063>_29 * 4;
>   T.2<D1072>_30 = pretmp.18<D1129>_50;
>  <...>
>   # T.3<D1073>_23 = PHI <T.3<D1073>_31(3), T.3<D1073>_43(6)>;
>   # k<D1063>_1 = PHI <k<D1063>_29(3), k<D1063>_41(6)>;
>   # k<D1063>_26 = PHI <k<D1063>_2(3), k<D1063>_1(6)>;
>   # pretmp.18<D1129>_48 = PHI <pretmp.18<D1129>_50(3),
> pretmp.18<D1129>_51(6)>;
>   # pretmp.19<D1130>_52 = PHI <pretmp.19<D1130>_54(3),
> pretmp.19<D1130>_55(6)>;
> <L0>:;
>   T.6<D1077>_13 = pretmp.18<D1129>_48;
>
> I think the problem is the entry into the loop from block 0 (or BB 3
> iafter PRE)
>
> the original stmt:
> T.6_13 = k<D1063>_26 * 4;
>
> k_26 is defined as k_2 coming in from block 0 in the original program,
> so T.6_13 would be k_2 * 4.

> So we are getting the wrong value the first time into the loop. we're
> using the wrong k...
>
> Andrew
>
> Am I reading that correctly?

Probably.
That means we didn't translate through the phi properly.
I bet we don't expect two phis for the same variable name in the loop
somewhere.
THat was actually my gut feeling when i first saw what you were doing to
k, but i didn't want to say it and look stupid.
Not that it helped :).

Ah.
Search for

    if (names_match_p (PHI_RESULT (phi), v))

in tree-ssa-pre.c
This is probably the cause.

Try if (PHI_RESULT (phi) == v) instead.

I bet we pick the wrong phi to translate through.
It looked right because of all the damn ks :)

Re: Bug 14562 : copyrename & PRE

[Andrew MacLeod]

On Mon, 2004-03-15 at 14:59, Daniel Berlin wrote:

> > Am I reading that correctly?
> 
> Probably.
> That means we didn't translate through the phi properly.
> I bet we don't expect two phis for the same variable name in the loop
> somewhere.
> THat was actually my gut feeling when i first saw what you were doing to
> k, but i didn't want to say it and look stupid.
> Not that it helped :).
> 
> Ah.
> Search for
> 
>     if (names_match_p (PHI_RESULT (phi), v))
> 
> in tree-ssa-pre.c
> This is probably the cause.
> 
> Try if (PHI_RESULT (phi) == v) instead.
> 
> I bet we pick the wrong phi to translate through.
> It looked right because of all the damn ks :)
> 

Yeah, that does seem to fix it. We aren't going to run into similar
problems anywhere else are we? I see other places where names_match_p()
is used that its not clear to me won't result in similar things. but
then, i dont know PRE very well.

THis also showed one of the potential pitfalls of copyrenaming. In this
particular case, it worked out worse for us because there were 2 k's
live in the loop dependant on each other, so we ended up with an extra
copy due to SSA->normal:
<L8>:;
  k.22<D1133> = k.21<D1132>;
  k.21<D1132> = k<D1063>;
  k<D1063> = k.22<D1133>;
  goto <bb 1> (<L0>);

instead of the original:

<L8>:;
  k<D1063> = T.1<D1071>;
  T.1<D1071> = T.20<D1131>;
  goto <bb 1> (<L0>);

blah. Well, we win more than we lose. 

I was wondering if I ought to stash away the "original" variable, and
then undo the copyrename if it is found to be unprofitable during
SSA->normal. Determining that its unprofitable is the trick now isn't
it. Hmm. perhaps its unlikely to be profitable if it results in more
than one PHI node the same variable as a RESULT... that should almost
always cause a new temproary to be created anyway.  Perhaps I'll fool
with that for a bit.

Anyway, yeah, it looks like that the PRE problem in this bug.


Andrew

Re: Bug 14562 : copyrename & PRE

[Daniel Berlin]

>
> Yeah, that does seem to fix it. We aren't going to run into similar
> problems anywhere else are we? I see other places where names_match_p()
> is used that its not clear to me won't result in similar things. but
> then, i dont know PRE very well.

There's one function named reaching_def that probably has the problem, but
it isn't used and i'm going to remove it.  The rest of the uses of
names_match_p are lexical equivalence uses or unused (part of strength
reduction that probably isn't worth it to implement since i'm working on
changing algorithms), so they should be correct.

GVN-PRE won't use any of these functions (It's conceptually much
simpler), or need to match names at all, since it's value based.
I just have some speed and memory concerns about the algorithm, but i
seriously doubt it could be *slower* than PRE is now.
:)

The local PRE tree on my laptop has some speedup changes, so if you could
commit that fix, i'd much appreciate it, so that i didn't have to copy a
new tree.

I can also do it later tonight when i get home if you aren't in a rush.

Re: Bug 14562 : copyrename & PRE

[Andrew MacLeod]

On Mon, 2004-03-15 at 15:45, Daniel Berlin wrote:
> >
> > Yeah, that does seem to fix it. We aren't going to run into similar
> > problems anywhere else are we? I see other places where names_match_p()
> > is used that its not clear to me won't result in similar things. but
> > then, i dont know PRE very well.
> 
> There's one function named reaching_def that probably has the problem, but
> it isn't used and i'm going to remove it.  The rest of the uses of
> names_match_p are lexical equivalence uses or unused (part of strength
> reduction that probably isn't worth it to implement since i'm working on
> changing algorithms), so they should be correct.
> 
> GVN-PRE won't use any of these functions (It's conceptually much
> simpler), or need to match names at all, since it's value based.
> I just have some speed and memory concerns about the algorithm, but i
> seriously doubt it could be *slower* than PRE is now.
> :)
> 
> The local PRE tree on my laptop has some speedup changes, so if you could
> commit that fix, i'd much appreciate it, so that i didn't have to copy a
> new tree.
> 
> I can also do it later tonight when i get home if you aren't in a rush.
> 

no rush, I dont have a tree in great condition at the moment either :-)
I wouldnt want to check it in without a bootstrap run :-)

Andrew