Optimization

Optimization

[Oskar Enoksson]

Hi! I'm working with computational mathematics using c and c++.

Does g++/gcc have any optimization that brings out constant subexpressions
outside loops? Consider the following:

void sqr(float *x, int *step) {
  int i,j,k;

  for (i=0; i<100; i++)
    for (j=0; j<100; j++)
      for (k=0; k<100; k++)
        *(x+i*step[2]+j*step[1]+k*step[0]) *= 
          *(x+i*step[2]+j*step[1]+k*step[0]);
}

The resulting assembler with egcs 1.0.2 (i686-pc-linux-gnulibc1) is not
very efficient, because the integer expressions are calculated again
and again inside the innermost loop. Can I make the compiler translate the
above code into something like the following:

void sqr(float *x, int *step) {
  int i,j,k; 
  float *xi,*xj;

  for (i=0; i<100; i++) {
    xi=x+i*step[2];
    for (j=0; j<100; j++)  {
      xj=xi+j*step[1];
      for (k=0; k<100; k++)  {
        *(xj+k*step[0]) *=
          *(xj+k*step[0]);
      }
    }
  }
}

If this is impossible with the current version, would it be hard to
add this optimization to the compiler? The resulting assembler is much
more efficient.

/Oskar

Re: Optimization

[John Carr]

The problem is, egcs detects aliases based on size of type, not type.
The stores to the float array kill the values in the integer array.

If you compile with -fargument-noalias you should see the optimization
you want.  Be careful using this flag: it makes an assertion about
pointer behavior which is not valid for some programs.

Re: Optimization

[Oskar Enoksson]

On Tue, 31 Mar 1998, Jim Wilson wrote:

> 	  for (i=0; i<100; i++)
> 	    for (j=0; j<100; j++)
> 	      for (k=0; k<100; k++)
> 	        *(x+i*step[2]+j*step[1]+k*step[0]) *= 
> 	          *(x+i*step[2]+j*step[1]+k*step[0]);
> 
> This is a hard problem.  We can't move the loads from step[] outside
> the loop unless we can know for sure that the stores into *(x+...) won't
> modify any of the values pointed to by step.  Since we have no info about
> where x or step point to, we make the worst case assumption that they
> overlap, and hence the loads from step[] are not loop invariant.

Of cource I have no idea how complicated this would be ...
but it sure would be nice to have something like the following flags:

-fno-alias
  Compiler assumes that no aliases exist.
-fno-typed-alias
  Compiler assumes that different types cannot be aliased.
-fno-float-alias
  Compiler assumes that float/double types don't alias with other
  types.
-fno-pointer-alias
  Compiler assumes that pointer types cannot be aliased with
  non-pointer types.

Am I dreaming? ;-)

I think SGI has something like the first two compiler options.
The KAI C++ compiler has --abstract-float and --abstract-pointer flags
similair to the third and fourth option above.

> It is actually a bit more complicated than that (we have type info to help
> with aliasing), but it is still a complicated problem.
> 
> The ISO C9X restrict keyword would make this optimization easier, because
> this would allow the programmer to tell the compiler that there is no aliasing.

Yes, that would be nice to, and perhaps easier to implement?

Regards.
/Oskar

Re: Optimization

[Jeffrey A Law]

--
Jeff Law (law@cygnus.com)
Cygnus Solutions		EGCS GNU Compiler System
http://www.cygnus.com		http://www.cygnus.com/egcs

  In message <Pine.SGI.3.96.980326123604.8153E-100000@purcell>you write:
  > 
  > Hi! I'm working with computational mathematics using c and c++.
  > 
  > Does g++/gcc have any optimization that brings out constant subexpressions
  > outside loops? Consider the following:
Yes, gcc performs loop invariant code motion.

I don't know why the loop invariants are not being hoisted out of
the loop for your example.  I haven't had the time to look at it.

jeff

Re: Optimization

[Joern Rennecke]

> Does g++/gcc have any optimization that brings out constant subexpressions
> outside loops? Consider the following:
> 
> void sqr(float *x, int *step) {
>   int i,j,k;
> 
>   for (i=0; i<100; i++)
>     for (j=0; j<100; j++)
>       for (k=0; k<100; k++)
>         *(x+i*step[2]+j*step[1]+k*step[0]) *= 
>           *(x+i*step[2]+j*step[1]+k*step[0]);
> }
> 
> The resulting assembler with egcs 1.0.2 (i686-pc-linux-gnulibc1) is not
> very efficient, because the integer expressions are calculated again
> and again inside the innermost loop. Can I make the compiler translate the
> above code into something like the following:
> 
> void sqr(float *x, int *step) {
>   int i,j,k; 
>   float *xi,*xj;
> 
>   for (i=0; i<100; i++) {
>     xi=x+i*step[2];
>     for (j=0; j<100; j++)  {
>       xj=xi+j*step[1];
>       for (k=0; k<100; k++)  {
>         *(xj+k*step[0]) *=
>           *(xj+k*step[0]);
>       }
>     }
>   }
> }
> 
> If this is impossible with the current version, would it be hard to
> add this optimization to the compiler? The resulting assembler is much
> more efficient.

There is loop invariant code motion in loop.c, but it doesn't work in this
case, because the alias analysis can't prove that that step[0] ... step[2]
are not changed by the stores.

Re: Optimization

[Jim Wilson]

	  for (i=0; i<100; i++)
	    for (j=0; j<100; j++)
	      for (k=0; k<100; k++)
	        *(x+i*step[2]+j*step[1]+k*step[0]) *= 
	          *(x+i*step[2]+j*step[1]+k*step[0]);

This is a hard problem.  We can't move the loads from step[] outside
the loop unless we can know for sure that the stores into *(x+...) won't
modify any of the values pointed to by step.  Since we have no info about
where x or step point to, we make the worst case assumption that they
overlap, and hence the loads from step[] are not loop invariant.

It is actually a bit more complicated than that (we have type info to help
with aliasing), but it is still a complicated problem.

The ISO C9X restrict keyword would make this optimization easier, because
this would allow the programmer to tell the compiler that there is no aliasing.

Jim

Re: Optimization

[John Carr]

> -fno-typed-alias
>   Compiler assumes that different types cannot be aliased.

With a few exceptions this describes ANSI C aliasing, which egcs tries to
implement.  Because the back end doesn't have type information alias
detection is based only on size.  On most systems float and int are the
same size.  If the example program used double instead of float you might
see better code.

I have some ideas for better aliasing but haven't had time to implement
them.  I started work on limited support for restrict but haven't had
time to finish that either.  A complete implementation may be a big job.

Re: Optimization

[Jeffrey A Law]

  In message <Pine.SGI.3.96.980326123604.8153E-100000@purcell>you write:
  > 
  > Hi! I'm working with computational mathematics using c and c++.
  > 
  > Does g++/gcc have any optimization that brings out constant subexpressions
  > outside loops? Consider the following:
  > 
  > void sqr(float *x, int *step) {
  >   int i,j,k;
  > 
  >   for (i=0; i<100; i++)
  >     for (j=0; j<100; j++)
  >       for (k=0; k<100; k++)
  >         *(x+i*step[2]+j*step[1]+k*step[0]) *= 
  >           *(x+i*step[2]+j*step[1]+k*step[0]);
  > }
  > 
  > The resulting assembler with egcs 1.0.2 (i686-pc-linux-gnulibc1) is not
  > very efficient, because the integer expressions are calculated again
  > and again inside the innermost loop. Can I make the compiler translate the
  > above code into something like the following:
  > 
  > void sqr(float *x, int *step) {
  >   int i,j,k; 
  >   float *xi,*xj;
  > 
  >   for (i=0; i<100; i++) {
  >     xi=x+i*step[2];
  >     for (j=0; j<100; j++)  {
  >       xj=xi+j*step[1];
  >       for (k=0; k<100; k++)  {
  >         *(xj+k*step[0]) *=
  >           *(xj+k*step[0]);
  >       }
  >     }
  >   }
  > }
  > 
  > If this is impossible with the current version, would it be hard to
  > add this optimization to the compiler? The resulting assembler is much
  > more efficient.
An FYI -- current development snapshots perform this optimization and thus
egcs-1.2 will perform this optimization when released.

This optimization was made possible by Mark Mitchell's type based alias
analysis will allows the compiler to realize that the floating point stores
in the loop can not access the same memory as the integer loads that were
initially in the loop.  This exposes the integer loads to loop invariant
code motion optimizations.


jeff

Re: Optimization

[Jeffrey A Law]

  In message <Pine.SGI.3.96.980326123604.8153E-100000@purcell>you write:
  > 
  > Hi! I'm working with computational mathematics using c and c++.
  > 
  > Does g++/gcc have any optimization that brings out constant subexpressions
  > outside loops? Consider the following:
  > 
  > void sqr(float *x, int *step) {
  >   int i,j,k;
  > 
  >   for (i=0; i<100; i++)
  >     for (j=0; j<100; j++)
  >       for (k=0; k<100; k++)
  >         *(x+i*step[2]+j*step[1]+k*step[0]) *= 
  >           *(x+i*step[2]+j*step[1]+k*step[0]);
  > }
  > 
  > The resulting assembler with egcs 1.0.2 (i686-pc-linux-gnulibc1) is not
  > very efficient, because the integer expressions are calculated again
  > and again inside the innermost loop. Can I make the compiler translate the
  > above code into something like the following:
  > 
  > void sqr(float *x, int *step) {
  >   int i,j,k; 
  >   float *xi,*xj;
  > 
  >   for (i=0; i<100; i++) {
  >     xi=x+i*step[2];
  >     for (j=0; j<100; j++)  {
  >       xj=xi+j*step[1];
  >       for (k=0; k<100; k++)  {
  >         *(xj+k*step[0]) *=
  >           *(xj+k*step[0]);
  >       }
  >     }
  >   }
  > }
  > 
  > If this is impossible with the current version, would it be hard to
  > add this optimization to the compiler? The resulting assembler is much
  > more efficient.
An FYI -- current development snapshots perform this optimization and thus
egcs-1.2 will perform this optimization when released.

This optimization was made possible by Mark Mitchell's type based alias
analysis will allows the compiler to realize that the floating point stores
in the loop can not access the same memory as the integer loads that were
initially in the loop.  This exposes the integer loads to loop invariant
code motion optimizations.


jeff

Re: optimization

[Scott Robert Ladd]

Viktor Przebinda wrote:
> I am interested in doing a long term (1.5 years) project with g++ 
> related to optimization for a masters thesis in computer engineering. 
> More specifically, optimization that would have its greatest impact on 
> scientific code written in C++. Target platform could be either PowerPC 
> or x86. I have already looked at gcc's website on the subject of 
> optimization deficiencies without much luck. These projects either 
> seemed too small or not related to scientific computing applications. If 
> anyone has some ideas please let me know.

I'm working on various ideas in this area; you'll find some of my 
preliminary work at:

     http://www.coyotegulch.com/acovea/index.html

That article will be revised later this week, as soon as my SPARC system 
finishes its evaluations of GCC optimizations.

I'm also rewriting an earlier article I'd written to compare the 
floating-point performance of several languages and compilers for Linux; 
the new "number crunching article" will be out before the end of the 
year, with a half-dozen benchmarks and better analysis.

-- 
Scott Robert Ladd
Coyote Gulch Productions (http://www.coyotegulch.com)
Software Invention for High-Performance Computing

Re: optimization

[Benjamin Kosnik]

> optimization that would have its greatest impact on scientific code written in C++. 

Do you have any specifics? I imagine it would be pretty easy to find
interest for this project. I'd suggest that you come up with a detailed
proposal and post it on this list for comment. You may be interested in
the tree-SSA infrastructure, see:
http://gcc.gnu.org/projects/tree-ssa/

However, if you are just looking for suggestions, there are a number of
C++ scientific libraries that would be interested in increasing
performance, some of which are listed below.

- ginac (symbolic algebra)
  http://www.ginac.de/
- pooma (parallel scientific computation)
  http://www.codesourcery.com/pooma/pooma
- goose (stats)
  http://www.gnu.org/software/goose/goose.html
- itk (algo parts)
  http://www.itk.org

A first step might be doing performance analysis of these libraries,
finding bottlenecks, and then working to resolve these deficiencies.

There are, or have been, issues with performance of C++'s complex type.
Perhaps Joe Buck could give more information on this.

There are people on this list (or gcc developers) that seem to be
interested in this subject. Off the top of my head, these people include
Roger Sayle, Scott Synder, Scott Robert Ladd, Gabriel Dos Reis, etc. I'm
sure there are others.

good luck,
-benjamin

Re: optimization

[Diego Novillo]

On Tue, 2003-12-09 at 11:29, Viktor Przebinda wrote:

> If anyone has some ideas please let me know.
> 
If you're into scientific code, maybe you'll be interested in
vectorization, memory hierarchy and array optimizations for Fortran95
http://gcc.gnu.org/fortran/index.html


Diego.

optimization

[Viktor Przebinda]

I am interested in doing a long term (1.5 years) project with g++ 
related to optimization for a masters thesis in computer engineering. 
More specifically, optimization that would have its greatest impact on 
scientific code written in C++. Target platform could be either PowerPC 
or x86. I have already looked at gcc's website on the subject of 
optimization deficiencies without much luck. These projects either 
seemed too small or not related to scientific computing applications. 
If anyone has some ideas please let me know.

Viktor
viktor.przebinda@colorado.edu 

Re: Optimization

[Richard Henderson]

On Fri, May 02, 2003 at 08:12:07PM -0400, Andrew Pinski wrote:
> I have a PR for it: optimization/10474.

I've modified the class to change-request, since it
was never even claimed that we do this.


r~

Re: Optimization

[Andrew Pinski]

I have a PR for it: optimization/10474.

Thanks,
Andrew Pinski

On Friday, May 2, 2003, at 19:06 US/Eastern, Richard Henderson wrote:

>
>> I see that there's also a greedy stack frame allocator instead
>> of a lazy one. Using the previous example
> [...]
>> when C is short and can be computed using only the scratch
>> registers, i.e. eax, edx and ecx, and D is complex and needs
>> to save/restore the remaining GP registers,
>
> Yes, this is called "shrink-wrapping", and we don't implement it.

Re: Optimization

[Richard Henderson]

On Fri, May 02, 2003 at 01:32:39PM +0200, Piotr Wyderski wrote:
> Why don't you optimize the "jump to ret" construction?

We do, depending on the target, and the epilogue.

	int foo(int p, int *q, int *r)
	{
	  if (p) *q = 1; else *r = 2;
	}

        movl    4(%esp), %eax
        testl   %eax, %eax
        je      .L2
        movl    8(%esp), %eax
        movl    $1, (%eax)
        ret
        .p2align 2,,3
.L2:
        movl    12(%esp), %eax
        movl    $2, (%eax)
        ret

> I see that there's also a greedy stack frame allocator instead
> of a lazy one. Using the previous example
[...]
> when C is short and can be computed using only the scratch
> registers, i.e. eax, edx and ecx, and D is complex and needs
> to save/restore the remaining GP registers,

Yes, this is called "shrink-wrapping", and we don't implement it.


r~

Optimization

[Piotr Wyderski]

Hello,

I've just looked at the binary code produced by the GCC 3.2
C++ compiler and don't understand your new optimizer's
behaviour. Why don't you optimize the "jump to ret" construction?
I mean this:

    if (b)
        C;
    else
        D;

produces:

    cmp/test b
    je    L2
    C
L1:    ret

L2:  D
    jmp L1

instead of:

    cmp/test b
    je     L2
    C
    ret

L2:  D
    ret

I see that there's also a greedy stack frame allocator instead
of a lazy one. Using the previous example

    if (b)
        C;
    else
        D;

when C is short and can be computed using only the scratch
registers, i.e. eax, edx and ecx, and D is complex and needs
to save/restore the remaining GP registers, GCC generates:

    push max_register_usage(C,D);
    test b
    je L2
    C

L1:   pop max_register_usage(C,D);
    ret

L2: D
    jmp L1,

but it could do this:

    test b
    je L2
    C
    ret

L2:    push register_usage(D);
    D
    pop register_usage(D);
    ret

    Best regards
    Piotr Wyderski



Zobacz nasz nowy serwis - wczasy za granicą - http://hoga.travelplanet.pl/
------------------------------------------------------------
Wiosną wirusy rosną bez pamięci!dlatego do pakietów wielostanowiskowych
mks_vir dokładamy Mobile Disks. Sprawdź:
http://www.mks.com.pl/promocja-mobile.html

Re: Optimization

[Jeffrey A Law]

  In message < 4B55904D9AC9D1119BA40000F81E49C703336DFD@emss04m10.ems.lmco.com >y
ou write:
  > Hello,	
  > 	Can you help shed some light as to what exactly -fcombine_statics
  > optimization flag does?
What compiler are you using?  I do not believe -fcombine-statics were ever
in an FSF release.  Partly because it couldn't be made stable with that
generation compiler technology.

jeff

Optimization

[Thomas, Robert S]

Hello,	
	Can you help shed some light as to what exactly -fcombine_statics
optimization flag does?

We are using 2.7.2 and when we compile optimized (-O3) we get an internal
compiler error.  If this flag is removed everything compiled fine.  

We need to justify removing this flag from the compile line however we are
unclear as to what we are actually losing by doing so.

Any insight would be great

Thanks
Rob

robert.s.thomas@lmco.com

Re: Optimization

[Oskar Enoksson]

> An FYI -- current development snapshots perform this optimization and
> thus egcs-1.2 will perform this optimization when released.
> 
> This optimization was made possible by Mark Mitchell's type based alias
> analysis will allows the compiler to realize that the floating point
> stores in the loop can not access the same memory as the integer loads
> that were initially in the loop.  This exposes the integer loads to loop
> invariant code motion optimizations.

Yes, I'm following the development of egcs closely and I'm currently using
different snapshots on SGI Octane, DEC alpha, and a Linux PC-cluster. The
efficiency for numerical computations is very good now, and I'm looking
forward to a version 1.2 stable on all platforms.

Thank you very much for your efforts!

Regards
/Oskar Enoksson

Re: Optimization

[Oskar Enoksson]

> An FYI -- current development snapshots perform this optimization and
> thus egcs-1.2 will perform this optimization when released.
> 
> This optimization was made possible by Mark Mitchell's type based alias
> analysis will allows the compiler to realize that the floating point
> stores in the loop can not access the same memory as the integer loads
> that were initially in the loop.  This exposes the integer loads to loop
> invariant code motion optimizations.

Yes, I'm following the development of egcs closely and I'm currently using
different snapshots on SGI Octane, DEC alpha, and a Linux PC-cluster. The
efficiency for numerical computations is very good now, and I'm looking
forward to a version 1.2 stable on all platforms.

Thank you very much for your efforts!

Regards
/Oskar Enoksson