RE: possible gcse failure: not able to eliminate redundant loads

RE: possible gcse failure: not able to eliminate redundant loads

[Sanjiv Kumar Gupta, Noida]

>  It is not hoisting some stores
>which it should.  The cases I have seen have not been due to aliasing.

>David

I have an example where gcse fails despite the success of aliasing.
consider,

void func (double *a, double *b, int i)
{
        int j;
 
        b[2] = a[1];
 
        for (j = 0; j < i; j++)
        {
               if (i)
                   b[3] = a[1];
        }
}

GCC -ml -m4 -O2 -fno-argument-alias  generates
_func:
        mov.l   r14,@-r15
        mov     r15,r14
        mov     r5,r1
        add     #16,r1
        add     #8,r4
        fmov.s  @r4+,fr3		--> loading a[1]
        fmov.s  @r4,fr2
        add     #-4,r4
        add     #4,r1
        fmov.s  fr2,@r1
        mov     #0,r2
        cmp/ge  r6,r2
        bt/s    .L10
        fmov.s  fr3,@-r1
        mov     r5,r1
        add     #24,r1
        mov     r6,r2
        tst     r6,r6
.L11:
        bt      .L4
        fmov.s  @r4+,fr3		--> loading a[1] again ??
        fmov.s  @r4,fr2
        add     #-4,r4
        add     #4,r1
        fmov.s  fr2,@r1
        fmov.s  fr3,@-r1
.L4:
        dt      r2
        bf/s    .L11
        tst     r6,r6

--Sanjiv

Re: possible gcse failure: not able to eliminate redundant loads

[Richard Henderson]

On Fri, Dec 13, 2002 at 11:26:34AM +0530, Sanjiv Kumar Gupta, Noida wrote:
>         b[2] = a[1];
>         for (j = 0; j < i; j++)
>         {
>                if (i)
>                    b[3] = a[1];

Yes, this requires more knowledge than is present in loop.

Ignoring the first statement, we cannot hoist a[1] because
it is only conditionally executed and might trap.  But we
don't have any code that knows how to propagate the fact
that we've already loaded from a earlier.

This case needs some form of gcse to work.


r~

Re: possible gcse failure: not able to eliminate redundant loads

[Toon Moene]

Richard Henderson wrote:

> On Fri, Dec 13, 2002 at 11:26:34AM +0530, Sanjiv Kumar Gupta, Noida wrote:
> 
>>        b[2] = a[1];
>>        for (j = 0; j < i; j++)
>>        {
>>               if (i)
>>                   b[3] = a[1];

> Yes, this requires more knowledge than is present in loop.
> 
> Ignoring the first statement, we cannot hoist a[1] because
> it is only conditionally executed and might trap.

Duh ;-)  Can we disable this notion of loads-that-might-trap from a frontend ?
I cannot imagine a valid Fortran program that contains an access to memory that 
"might trap".

[ Silly things to do with your computer on a rainy Sunday afternoon:

   1. Stand out in the rain.

   - with apologies to Monty Python ]

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

Re: possible gcse failure: not able to eliminate redundant loads

[Richard Henderson]

On Fri, Dec 13, 2002 at 09:25:54PM +0100, Toon Moene wrote:
> Can we disable this notion of loads-that-might-trap from a frontend ?

I don't know.

> I cannot imagine a valid Fortran program that contains an access to
> memory that "might trap".

Yeah, I guess there's really no concept of a null pointer is there...



r~

Re: possible gcse failure: not able to eliminate redundant loads

[Andrew Haley]

Richard Henderson writes:
 > On Fri, Dec 13, 2002 at 09:25:54PM +0100, Toon Moene wrote:
 > > Can we disable this notion of loads-that-might-trap from a frontend ?
 > 
 > I don't know.

I wrote a patch that adds a flag to a MEM so that a front end can mark
it as trapping or not trapping and may_trap_p() can deal with it
accordingly.  This is good for Java too.

I'll clean it up and submit it if there's interest.

Andrew.

Re: possible gcse failure: not able to eliminate redundant loads

[Toon Moene]

Richard Henderson wrote:

> On Fri, Dec 13, 2002 at 09:25:54PM +0100, Toon Moene wrote:

>>I cannot imagine a valid Fortran program that contains an access to
>>memory that "might trap".

> Yeah, I guess there's really no concept of a null pointer is there...

Well, certainly not in the language that g77 compiles (a superset of 
Fortran 77), because there is no concept of "pointer" in that language.

However, Fortran 90/95 *do* have pointers, but also there it's not 
legally possible to "dereference" (to use the C-term) pointers that 
point to storage that has not been "defined" (given a value) - to say 
nothing of to point to something that isn't there (i.e., a pointer that 
hasn't been initialised to point to an existing object).

BTW, I wasn't aware it's legal to dereference NULL C pointers.

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

Re: possible gcse failure: not able to eliminate redundant loads

[Richard Henderson]

On Mon, Dec 16, 2002 at 10:04:01PM +0100, Toon Moene wrote:
> BTW, I wasn't aware it's legal to dereference NULL C pointers.

It isn't, of course.  But that's the whole point.  You've
got code that says

	x = (condition ? *p : 0);

i.e. the dereference is protected by a conditional.  Thus
we can't hoist the dereference past the conditional (and
thence out of the loop that started this thread).


r~

Re: possible gcse failure: not able to eliminate redundant loads

[Toon Moene]

Richard Henderson wrote:

> On Mon, Dec 16, 2002 at 10:04:01PM +0100, Toon Moene wrote:
> 
>>BTW, I wasn't aware it's legal to dereference NULL C pointers.

> It isn't, of course.  But that's the whole point.  You've
> got code that says
> 
> 	x = (condition ? *p : 0);
> 
> i.e. the dereference is protected by a conditional.  Thus
> we can't hoist the dereference past the conditional (and
> thence out of the loop that started this thread).

Oh, Fortran is sooooo much easier in this respect than [some other 
languages].  Of course you can [syntactically] express "dereferencing" a 
invalid pointer in Fortran 90/95.  That doesn't mean the resulting 
program has to do something meaningful, however [could start WW III and 
all that]

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

Re: possible gcse failure: not able to eliminate redundant loads

[Toon Moene]

Toon Moene wrote:

> Richard Henderson wrote:
> 
>> On Mon, Dec 16, 2002 at 10:04:01PM +0100, Toon Moene wrote:
>>
>>> BTW, I wasn't aware it's legal to dereference NULL C pointers.

>> It isn't, of course.  But that's the whole point.  You've
>> got code that says
>>
>>     x = (condition ? *p : 0);
>>
>> i.e. the dereference is protected by a conditional.

Oh, wait, I see what you mean:

	x = (p ? *p : 0);

Yes, that's impossible to express in Fortran (90/95/F2K), hence we don't 
have to worry about it.

[ The way to do this in Fortran is to write:

         IF (ASSOCIATED(P)) THEN
             .... USE P
         ELSE
             .... BETTER KEEP YOUR PAWS OFF ....
         ENDIF
]

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

Re: possible gcse failure: not able to eliminate redundant loads

[Richard Henderson]

On Mon, Dec 16, 2002 at 11:46:57PM +0100, Toon Moene wrote:
> Yes, that's impossible to express in Fortran (90/95/F2K), hence we don't 
> have to worry about it.
> 
> [ The way to do this in Fortran is to write:
> 
>         IF (ASSOCIATED(P)) THEN
>             .... USE P
>         ELSE
>             .... BETTER KEEP YOUR PAWS OFF ....
>         ENDIF

Um, isn't this still exactly what I talked about?  The use of P
is protected by a conditional.


r~

Re: possible gcse failure: not able to eliminate redundant loads

[Jan Hubicka]

> Toon Moene wrote:
> 
> >Richard Henderson wrote:
> >
> >>On Mon, Dec 16, 2002 at 10:04:01PM +0100, Toon Moene wrote:
> >>
> >>>BTW, I wasn't aware it's legal to dereference NULL C pointers.
> 
> >>It isn't, of course.  But that's the whole point.  You've
> >>got code that says
> >>
> >>    x = (condition ? *p : 0);
> >>
> >>i.e. the dereference is protected by a conditional.
> 
> Oh, wait, I see what you mean:
> 
> 	x = (p ? *p : 0);
> 
> Yes, that's impossible to express in Fortran (90/95/F2K), hence we don't 
> have to worry about it.

I think you can write the for loop.
The loop computes pointer past the array boundary that is invisible to
fortran but happens in generated code.
GCC beleiving that the memory refrence does not trap would move the load
ahead in unrolled version of the loop causing program to read past the
end.

Honza
> 
> [ The way to do this in Fortran is to write:
> 
>         IF (ASSOCIATED(P)) THEN
>             .... USE P
>         ELSE
>             .... BETTER KEEP YOUR PAWS OFF ....
>         ENDIF
> ]
> 
> -- 
> Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
> Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
> Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
> Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

Re: possible gcse failure: not able to eliminate redundant loads

[Alex Rosenberg]

on 12/16/02 1:12 PM, Richard Henderson at rth@redhat.com wrote:

> On Mon, Dec 16, 2002 at 10:04:01PM +0100, Toon Moene wrote:
>> BTW, I wasn't aware it's legal to dereference NULL C pointers.
> 
> It isn't, of course.  But that's the whole point.  You've
> got code that says
> 
> x = (condition ? *p : 0);
> 
> i.e. the dereference is protected by a conditional.  Thus
> we can't hoist the dereference past the conditional (and
> thence out of the loop that started this thread).

This may be obvious, but... this transformation is legal on some platforms.

AIX maps page 0 as read-only and zero-filled. IBM's xlC compiler will hoist
loads past a conditional with this knowledge. (It doesn't map the high end
of the address space similarly -- one of IBM's countless Java
implementations takes advantage of this discrepancy.)

IA64, Transmeta and other architectures split the job of a load into two
parts to enable exactly this sort of optimization.

+------------------------------------------------------------+
| Alexander M. Rosenberg           <mailto:alexr@_spies.com> |
| Nobody cares what I say. Remove the underscore to mail me. |

Re: possible gcse failure: not able to eliminate redundant loads

[Toon Moene]

Richard Henderson wrote:

> On Mon, Dec 16, 2002 at 11:46:57PM +0100, Toon Moene wrote:
> 
>>Yes, that's impossible to express in Fortran (90/95/F2K), hence we don't 
>>have to worry about it.
>>
>>[ The way to do this in Fortran is to write:
>>
>>        IF (ASSOCIATED(P)) THEN
>>            .... USE P
>>        ELSE
>>            .... BETTER KEEP YOUR PAWS OFF ....
>>        ENDIF

> Um, isn't this still exactly what I talked about?  The use of P
> is protected by a conditional.

Yes, it might well be that I do not understand the purpose of the 
prohibition of this optimization in GCC.  Obviously (he says now :-) I 
expect optimizations to conserve the "correct program" property, i.e. if 
A is a program in Fortran then opt(A) also is a program in Fortran (note 
that this property is - much - weaker than: encodes the same computation).

If we do not conserve this property, then all bets are off:

       DIMENSION A(10), B(11)
       ...
       DO I = 1, 11
          IF (I .GT. 10) THEN
             B(I) = 0.0 ! Default value
          ELSE
             B(I) = A(I)
          ENDIF
       ENDDO
       END

Of course this is not a valid Fortran program if the compiler moved 
B=A(I) out of the IF .. THEN .. ELSE .. ENDIF construct.

-- 
Toon Moene - mailto:toon@moene.indiv.nluug.nl - phoneto: +31 346 214290
Saturnushof 14, 3738 XG  Maartensdijk, The Netherlands
Maintainer, GNU Fortran 77: http://gcc.gnu.org/onlinedocs/g77_news.html
Join GNU Fortran 95: http://g95.sourceforge.net/ (under construction)

Re: possible gcse failure: not able to eliminate redundant loads

[Robert Dewar]

> At the expense of getting nice crashes at points where NULL is
> dereferenced, which often makes it easy to find bugs?  Oh, and there's

umm ... optimization is about favoring fast execution of code over 
debuggability, so yes, exactly that is the trade off. Note that there
is absolutely NOTHING to stop a compiler from generating code that
diagnoses dereferences of null pointers in fully optimized code if
that's what you want (it is for example required in Ada!)

Re: possible gcse failure: not able to eliminate redundant loads

[Alexandre Oliva]

On Dec 18, 2002, dewar@gnat.com (Robert Dewar) wrote:

> it is interesting to note that the IBM compiler group decided that
> ensuring that null could be safetly dereferenced, and hence such
> references can be hoisted etc, was a major win in C code efficiency.

At the expense of getting nice crashes at points where NULL is
dereferenced, which often makes it easy to find bugs?  Oh, and there's
also the issue that pointers with static storage, without an explicit
initializer, are supposed to be zero-initialized, which, I suppose,
means they get a NULL value.  If NULL is a bit pattern that differs
from all zeros, you become unable to place such symbols in sbss or,
worse, you need dynamic initialization in case the address of the NULL
object can only be known at run time (e.g. shared libraries).

Ideally, we'd be able to mark would-trap dereferences hoisted out of
their protecting conditions, and only actually trap should the
condition hold.  IA64 does that, but other platforms would require
supporting code in the kernel or in signal handlers, whose overhead
would probably defeat the performance win of being able to hoist the
dereferences in the first place.

-- 
Alexandre Oliva   Enjoy Guarana', see http://www.ic.unicamp.br/~oliva/
Red Hat GCC Developer                 aoliva@{redhat.com, gcc.gnu.org}
CS PhD student at IC-Unicamp        oliva@{lsd.ic.unicamp.br, gnu.org}
Free Software Evangelist                Professional serial bug killer

Re: possible gcse failure: not able to eliminate redundant loads

[Richard Kenner]

    So the pointer isn't null, it's uninitialized, and the conditional
    protecting its use is true iff it's initialized.  Same problem.

No, because of the common idiom (especially for lists) of testing a
pointer for being null and then dereferencing it if not.  You can do the
load unconditionally in that case.

Re: possible gcse failure: not able to eliminate redundant loads

[Richard Henderson]

On Wed, Dec 18, 2002 at 08:27:54PM -0500, Robert Dewar wrote:
> it is interesting to note that the IBM compiler group decided that
> ensuring that null could be safetly dereferenced, and hence such
> references can be hoisted etc, was a major win in C code efficiency.

So the pointer isn't null, it's uninitialized, and the conditional
protecting its use is true iff it's initialized.  Same problem.


r~

Re: possible gcse failure: not able to eliminate redundant loads

[Robert Dewar]

> i.e. the dereference is protected by a conditional.  Thus
> we can't hoist the dereference past the conditional (and
> thence out of the loop that started this thread).


it is interesting to note that the IBM compiler group decided that
ensuring that null could be safetly dereferenced, and hence such
references can be hoisted etc, was a major win in C code efficiency.

Re: possible gcse failure: not able to eliminate redundant loads

[Richard Henderson]

On Thu, Dec 12, 2002 at 05:58:37PM -0500, Daniel Berlin wrote:
> I remember someone saying that store motion should replace this, since 
> it subsumes it.

Of course.  The next time someone has time to fix store motion.


r~

RE: possible gcse failure: not able to eliminate redundant loads

[Sanjiv Kumar Gupta, Noida]

>It works just fine on SPARC, so it might be something specific to your
>port... 

>        ldd     [%o0+8], %f8
>        cmp     %o2, 2  !  i

We have reg+offset mode for SPARC here. So that's find with alias.c.
mine is SH4. I fear IA64 may probably have the same problem.

--Sanjiv

Re: possible gcse failure: not able to eliminate redundant loads

[Dan Nicolaescu]

"Sanjiv Kumar Gupta, Noida" <sanjivg@noida.hcltech.com> writes:

  >  
  > >> We have the code for it, but alias.c isn't helping.
  > 
  > >It looks like memrefs_conflict_p is supposed to be able to prove that
  > a[2] and a[4] don't alias, I wonder why it's not working?
  > 
  > It can detect different offsets in 'reg+offset' forms of addresses
  > but can not distinguish between two pointer regs. 
  > In this case, the machine (sh4) doesn't support reg+offset addressing
  > for double-precision values.
  > I am working on memrefs_conflict_p to handle this.

It works just fine on SPARC, so it might be something specific to your
port... 

        ldd     [%o0+8], %f8
        cmp     %o2, 2  !  i
        bg      .LL8
        std     %f8, [%o1+16]
        add     %o2, 8, %o2     !  i,  i
.LL10:
        cmp     %o2, 2  !  i
        ble,a   .LL10
        add     %o2, 8, %o2     !  i,  i
        std     %f8, [%o0+32]
.LL8:
        nop
        retl
        nop

RE: possible gcse failure: not able to eliminate redundant loads

[Sanjiv Kumar Gupta, Noida]

 
>> We have the code for it, but alias.c isn't helping.

>It looks like memrefs_conflict_p is supposed to be able to prove that
a[2] and a[4] don't alias, I wonder why it's not working?

It can detect different offsets in 'reg+offset' forms of addresses
but can not distinguish between two pointer regs. 
In this case, the machine (sh4) doesn't support reg+offset addressing
for double-precision values.
I am working on memrefs_conflict_p to handle this.

--Sanjiv

Re: possible gcse failure: not able to eliminate redundant loads

[David Edelsohn]

>>>>> Richard Henderson writes:

Richard> Believe me now?

	We appear to be talking past each other.  I agree that GCC
performs some hoisting optimizations.  It is not hoisting some stores
which it should.  The cases I have seen have not been due to aliasing.

David

Re: possible gcse failure: not able to eliminate redundant loads

[Geoff Keating]

Richard Henderson <rth@redhat.com> writes:

> On Thu, Dec 12, 2002 at 04:02:07PM -0500, David Edelsohn wrote:
> > Richard> Both.  We hoist values read-write when we can.
> > 
> > 	GCC should but it doesn't.
> 
> My point exactly.
> 
> We have the code for it, but alias.c isn't helping.

It looks like memrefs_conflict_p is supposed to be able to prove that
a[2] and a[4] don't alias, I wonder why it's not working?

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: possible gcse failure: not able to eliminate redundant loads

[Daniel Berlin]

On Thursday, December 12, 2002, at 05:42  PM, Richard Henderson wrote:

> On Thu, Dec 12, 2002 at 05:31:39PM -0500, David Edelsohn wrote:
>> 	I do not believe that the code exists, or if the code exists it is
>> disabled because it is broken in other ways, not alias.c.
>
> Yawn.
>
> 	int x;
> 	void foo()
> 	{
> 	  int i;
> 	  for (i = 0; i < 100; i++)
> 	    x += i;
> 	}
>
> foo:
>         movl    x, %eax
>         xorl    %edx, %edx
>         .p2align 4,,15
> .L6:
>         addl    %edx, %eax
>         incl    %edx
>         cmpl    $99, %edx
>         jle     .L6
>         movl    %eax, x
>         ret
>
> And from the .loop dump file,
>
> Loop from 10 to 31: 6 real insns.
> Continue at insn 23.
> Hoisted regno 62 r/w from (mem/f:SI (symbol_ref:SI ("x")) [2 x+0 S4 
> A32])
>
> Believe me now?

I remember someone saying that store motion should replace this, since 
it subsumes it.

>
> r~

Re: possible gcse failure: not able to eliminate redundant loads

[Richard Henderson]

On Thu, Dec 12, 2002 at 05:31:39PM -0500, David Edelsohn wrote:
> 	I do not believe that the code exists, or if the code exists it is
> disabled because it is broken in other ways, not alias.c.

Yawn.

	int x;
	void foo()
	{
	  int i;
	  for (i = 0; i < 100; i++)
	    x += i;
	}

foo:
        movl    x, %eax
        xorl    %edx, %edx
        .p2align 4,,15
.L6:
        addl    %edx, %eax
        incl    %edx
        cmpl    $99, %edx
        jle     .L6
        movl    %eax, x
        ret

And from the .loop dump file,

Loop from 10 to 31: 6 real insns.
Continue at insn 23.
Hoisted regno 62 r/w from (mem/f:SI (symbol_ref:SI ("x")) [2 x+0 S4 A32])

Believe me now?


r~

Re: possible gcse failure: not able to eliminate redundant loads

[David Edelsohn]

>>>>> Richard Henderson writes:

Richard> We have the code for it, but alias.c isn't helping.

	I do not believe that the code exists, or if the code exists it is
disabled because it is broken in other ways, not alias.c.

David

Re: possible gcse failure: not able to eliminate redundant loads

[Richard Henderson]

On Thu, Dec 12, 2002 at 04:02:07PM -0500, David Edelsohn wrote:
> Richard> Both.  We hoist values read-write when we can.
> 
> 	GCC should but it doesn't.

My point exactly.

We have the code for it, but alias.c isn't helping.



r~

Re: possible gcse failure: not able to eliminate redundant loads

[David Edelsohn]

>>>>> Richard Henderson writes:

Richard> Both.  We hoist values read-write when we can.

	GCC should but it doesn't.

David

Re: possible gcse failure: not able to eliminate redundant loads

[Richard Henderson]

On Thu, Dec 12, 2002 at 03:26:44PM -0500, Daniel Berlin wrote:
> >  Not for this
> > simple case.  If these memories are known to not alias, then they
> > should be hoisted out of the loop by load_mems.
> Maybe the load, but not the store.

Both.  We hoist values read-write when we can.


r~

Re: possible gcse failure: not able to eliminate redundant loads

[Daniel Berlin]

On Thu, 12 Dec 2002, Richard Henderson wrote:

> On Wed, Dec 11, 2002 at 08:50:01PM -0500, Daniel Berlin wrote:
> > >>>       for (i ; i < 3; i = i + 8)
> > >>>       {
> > >>>               a[4] = a[1];
> > >>>       }
> [...]
> > Store motion can't handle this right now.
>
> This shouldn't have anything to do with store motion.

a[4] = is a store.
>  Not for this
> simple case.  If these memories are known to not alias, then they
> should be hoisted out of the loop by load_mems.
Maybe the load, but not the store.

>
> To me it's clear that this is an alias.c defect.
>
>
> r~
>

Re: possible gcse failure: not able to eliminate redundant loads

[Richard Henderson]

On Wed, Dec 11, 2002 at 08:50:01PM -0500, Daniel Berlin wrote:
> >>>       for (i ; i < 3; i = i + 8)
> >>>       {
> >>>               a[4] = a[1];
> >>>       }
[...]
> Store motion can't handle this right now.

This shouldn't have anything to do with store motion.  Not for this
simple case.  If these memories are known to not alias, then they
should be hoisted out of the loop by load_mems.

To me it's clear that this is an alias.c defect.


r~

RE: possible gcse failure: not able to eliminate redundant loads

[Daniel Berlin]

On Thu, 12 Dec 2002, Sanjiv Kumar Gupta, Noida wrote:

>
>
> >> But surely it should be smart enough to know they don't alias?
> >It depends on what it looks like at the RTL level.
> the references of a[4] and a[1] appear as two pointer pseudos
> which gcc can not determine that they have been computed with distinct
> offsets from same base. Thus assumes aliasing.
> I am implementing mod-k residue technique in GCC
> (described in "alias analysis of executable code", Debray98 et. al)
> to fix this.
> >> This is still a bug, possibly an important one for performance.
>
> >Store motion can't handle this right now.
> >It was built to handle a certain special case.
> >Improve it so it does more.
> >It's not broken, just not as good as it could be.
>
> Store motion is currently disabled. see gcse.c line 910

Err, you don't know this, but you don't need to tell me.
I know more about the history of store motion than i would ever care to
know.
:)

>
> /* Store motion disabled until it is fixed.  */
>   if (0 && !optimize_size && flag_gcse_sm)
>     store_motion ();
>
> I don't know what's stopping this? I will try to find
> related PRs and have a look into them.

What's stopping is twofold.

1.  in current form, it takes a not
insignificant amount of time, and does nothing (If you look at the mailing list
archives, you'll note i collected stats, and found it applied <10 times in
the bootstrap).
2. There is code where it does apply, and does the wrong thing.

Both are bad.

Feel free to reenable it and watch it do nothing for most stores.

Now i remember what case it handles:
It will only move stores to globals right now, and even then, only in
special cases.

Check find_moveable_store.
:)



>
> --Sanjiv
>

RE: possible gcse failure: not able to eliminate redundant loads

[Sanjiv Kumar Gupta, Noida]

>> But surely it should be smart enough to know they don't alias?
>It depends on what it looks like at the RTL level.
the references of a[4] and a[1] appear as two pointer pseudos
which gcc can not determine that they have been computed with distinct
offsets from same base. Thus assumes aliasing.
I am implementing mod-k residue technique in GCC 
(described in "alias analysis of executable code", Debray98 et. al)
to fix this.
>> This is still a bug, possibly an important one for performance.

>Store motion can't handle this right now.
>It was built to handle a certain special case.
>Improve it so it does more.
>It's not broken, just not as good as it could be.

Store motion is currently disabled. see gcse.c line 910

/* Store motion disabled until it is fixed.  */
  if (0 && !optimize_size && flag_gcse_sm)
    store_motion ();

I don't know what's stopping this? I will try to find
related PRs and have a look into them.

--Sanjiv

RE: possible gcse failure: not able to eliminate redundant loads

[Sanjiv Kumar Gupta, Noida]

>But surely it should be smart enough to know they don't alias?

I am currently working to make the alias analysis more smart. :) 
After that GCC will be able to figure out that a[4] and a[1] do not alias. 


--Sanjiv

Re: possible gcse failure: not able to eliminate redundant loads

[Daniel Berlin]

On Wednesday, December 11, 2002, at 05:24  PM, Dale Johannesen wrote:

>
> On Wednesday, December 11, 2002, at 03:24  AM, Sanjiv Kumar Gupta, 
> Noida wrote:
>>> void func (double *a, double *b, int i)
>>> {
>>>        b[2] = a[1];
>>>
>>>        for (i ; i < 3; i = i + 8)
>>>        {
>>>                a[4] = a[1];
>>>
>>>        }
>>> }
>>
>>> for -O2 -fno-argument-alias, I am getting multiple loads for a[1].
>>
>> Oooops! I realized it just now. Basically GCC is assuming that
>> a[4] and a[1] may alias, hence reloading a[1] in each loop iteration.
>> sorry for the inconvenience caused.
>
> But surely it should be smart enough to know they don't alias?
It depends on what it looks like at the RTL level.
> This is still a bug, possibly an important one for performance.

Store motion can't handle this right now.
It was built to handle a certain special case.
Improve it so it does more.
It's not broken, just not as good as it could be.
--Dan

Re: possible gcse failure: not able to eliminate redundant loads

[Daniel Berlin]

On Wednesday, December 11, 2002, at 05:24  PM, Dale Johannesen wrote:

>
> On Wednesday, December 11, 2002, at 03:24  AM, Sanjiv Kumar Gupta, 
> Noida wrote:
>>> void func (double *a, double *b, int i)
>>> {
>>>        b[2] = a[1];
>>>
>>>        for (i ; i < 3; i = i + 8)
>>>        {
>>>                a[4] = a[1];
>>>
>>>        }
>>> }
>>
>>> for -O2 -fno-argument-alias, I am getting multiple loads for a[1].
>>
>> Oooops! I realized it just now. Basically GCC is assuming that
>> a[4] and a[1] may alias, hence reloading a[1] in each loop iteration.
>> sorry for the inconvenience caused.
>
> But surely it should be smart enough to know they don't alias?
It depends on what it looks like at the RTL level.
> This is still a bug, possibly an important one for performance.

Store motion can't handle this right now.
It was built to handle a certain special case.
Improve it so it does more.
It's not broken, just not as good as it could be.
--Dan

Re: possible gcse failure: not able to eliminate redundant loads

[Dale Johannesen]

On Wednesday, December 11, 2002, at 03:24  AM, Sanjiv Kumar Gupta, 
Noida wrote:
>> void func (double *a, double *b, int i)
>> {
>>        b[2] = a[1];
>>
>>        for (i ; i < 3; i = i + 8)
>>        {
>>                a[4] = a[1];
>>
>>        }
>> }
>
>> for -O2 -fno-argument-alias, I am getting multiple loads for a[1].
>
> Oooops! I realized it just now. Basically GCC is assuming that
> a[4] and a[1] may alias, hence reloading a[1] in each loop iteration.
> sorry for the inconvenience caused.

But surely it should be smart enough to know they don't alias?
This is still a bug, possibly an important one for performance.

RE: possible gcse failure: not able to eliminate redundant loads

[Sanjiv Kumar Gupta, Noida]

>void func (double *a, double *b, int i)
>{
>        b[2] = a[1];
>
>        for (i ; i < 3; i = i + 8)
>        {
>                a[4] = a[1];
>
>        }
>}

>for -O2 -fno-argument-alias, I am getting multiple loads for a[1].

Oooops! I realized it just now. Basically GCC is assuming that
a[4] and a[1] may alias, hence reloading a[1] in each loop iteration.
sorry for the inconvenience caused.

regards
--Sanjiv

possible gcse failure: not able to eliminate redundant loads

[Sanjiv Kumar Gupta, Noida]

Following code snippet demonstrates the problem.

void func (double *a, double *b, int i)
{
        b[2] = a[1];

        for (i ; i < 3; i = i + 8)
        {
                a[4] = a[1];

        }
}

for -O2 -fno-argument-alias, I am getting multiple loads for a[1].

_func:
        mov.l   r14,@-r15
        mov     r15,r14
        add     #16,r5
        mov     r4,r2
        add     #8,r2
        fmov.s  @r2+,fr3		--> loading a[1] here
        fmov.s  @r2,fr2
        add     #-4,r2
        add     #4,r5
        fmov.s  fr2,@r5
        mov     #2,r1
        cmp/gt  r1,r6
        bt/s    .L9
        fmov.s  fr3,@-r5
        add     #32,r4
.L6:
        fmov.s  @r2+,fr3		--> loading a[1] here again //
problem.
        fmov.s  @r2,fr2
        add     #-4,r2
        add     #4,r4
        fmov.s  fr2,@r4
        add     #8,r6
        cmp/gt  r1,r6
        bf/s    .L6
        fmov.s  fr3,@-r4
.L9:
        mov     r14,r15
        rts
        mov.l   @r15+,r14

with -fno-argument-alias GCC knows that b[2] and a[1] do not alias, so
store into b[2] is not invalidating the loaded value of a[1]. Hence
it should have used the previously loaded value of a[1] inside the for loop
instead of reloading it.

The above assembly listing is for sh-elf, but this problem might be there
for other targets too. Enabling store_motion code in gcse.c and 
using -O3 -fgcse-lm -fgcse-sm don't help either.

However, it behaves perfectly fine for following

void func (double *a, double *b, int i)
{
        b[2] = a[1];

        if (i < 3)
        {
                a[4] = a[1];

        }
}

Here, we do not get extra loads for a[1]. 

Can somebody please help me knowing what is happening here?
--Sanjiv