Optimizations documentation

Optimizations documentation

[Константин]

Hi!

I ask you to put optimimizations tips for programmers into your documentation site on www. Sure, there are some texts about program optimimization, but you are the only one, who really understand compilation and execution processes and know how to make program faster.
I read on some site that it would better and quicker to use floats instead of doubles, use unsigned int instead of signed as counters in loops, mark const function parameters when they are and so on. Is it true for GCC (G++)?
Your compiler makes great optimization, but it'd be better if you explain to programmers how to help to compiler optimize program. For example, some time ago I listened that GCC supports vectorization, but still can't find anything about it, how can I use it in my programs.
Your site is the right place for such documentation. PLEASE put it on.
Thank you!

Re: Optimizations documentation

[Tim Prince]

ц╚ц▐ц▌ц⌠ц■ц│ц▌ц■ц┴ц▌ wrote:
> Hi!
>
> I ask you to put optimimizations tips for programmers into your documentation site on www. Sure, there are some texts about program optimimization, but you are the only one, who really understand compilation and execution processes and know how to make program faster.
> I read on some site that it would better and quicker to use floats instead of doubles, use unsigned int instead of signed as counters in loops, mark const function parameters when they are and so on. Is it true for GCC (G++)?
> Your compiler makes great optimization, but it'd be better if you explain to programmers how to help to compiler optimize program. For example, some time ago I listened that GCC supports vectorization, but still can't find anything about it, how can I use it in my programs.
> Your site is the right place for such documentation. PLEASE put it on.
> Thank you!
>   
This topic seems more appropriate to the gcc-help mail list.
The on-line docs show a fair effort, although documentation of 
-ftree-vectorize seems difficult to find in a single search:
http://gcc.gnu.org/onlinedocs/

Superior performance of float over double is more marked for the SSE 
platforms, so you should specify your platform of interest when asking 
such questions.
If you want examples, quite a few of those are available on line.

Re: Optimizations documentation

[Ira Rosen]

Hi,

gcc-owner@gcc.gnu.org wrote on 01/01/2008 22:00:11:

> some time ago I listened that GCC supports vectorization,
> but still can't find anything about it, how can I use it in my programs.

Here is the link to the vectorizer's documentation:
http://gcc.gnu.org/projects/tree-ssa/vectorization.html

Ira

Re: Optimizations documentation

[Tim Prince]

Ira Rosen wrote:
> Here is the link to the vectorizer's documentation:
> http://gcc.gnu.org/projects/tree-ssa/vectorization.html
>
>
>   
Thanks, but I take what it says there with some grains of salt.  Yes, 
-O3 implies -ftree-vectorize on x86_64, but I seem to have to specify 
the option on other targets.  Also, I have not understood the 
limitations of -freassociative-math.
Several gcc vectorization test cases currently throw FAIL on certain 
targets, but not on others.  I don't know if that is a significant issue.
g++-4.3 seems well ahead of other compilers in ability to vectorize STL 
iterators:
http://softwarecommunity.intel.com/Wiki/HighPerformanceComputing/688.htm

Re: Optimizations documentation

[Dorit Nuzman]

> Ira Rosen wrote:
> > Here is the link to the vectorizer's documentation:
> > http://gcc.gnu.org/projects/tree-ssa/vectorization.html
> >
> >
> >
> Thanks, but I take what it says there with some grains of salt.

?? please report any inaccuracies/outdated information you find, I'd like
to fix any such issues.

> Yes,
> -O3 implies -ftree-vectorize on x86_64, but I seem to have to specify
> the option on other targets.

tree-vectorize is enabled under -O3, for all targets. I don't know of any
target that disabled it. There may be however targets that require
additional flags to enable vectorization (like -maltivec for powerpc).
Specifically, on which targets does "-O3" behaves differently than "-O3
-ftree-vectorize"?

> Also, I have not understood the
> limitations of -freassociative-math.

I think this is a typo - should be "-fassociative-math" (I'll fix that;
here's the related thread:
http://gcc.gnu.org/ml/gcc-patches/2007-09/msg00183.html).

> Several gcc vectorization test cases currently throw FAIL on certain
> targets, but not on others.  I don't know if that is a significant issue.

please report specific testcases+targets... (there are already at least a
couple open PRs for failing testcases - 34168 and 34437 are the most recent
ones I think. there may be more).

> g++-4.3 seems well ahead of other compilers in ability to vectorize STL
> iterators:
> http://softwarecommunity.intel.com/Wiki/HighPerformanceComputing/688.htm
>

good to know.
I browsed over the posting above; do you have a summary table where one
could easily see which loops get vectorized by other compilers and not by
gcc (and vice versa)?

thanks,
dorit

Re: Optimizations documentation

[Ira Rosen]

Dorit Nuzman/Haifa/IBM wrote on 18/02/2008 09:40:37:

> Thanks a lot for tracking down / opening the relevant PRs.
>
> about:
>
> > > (6) loop distribution is required to break a dependence. This may
> > > already be handled by Sebastian's loop-distribution pass that will
> > > be incorporated in 4.4.
> > > Here is an example:
> > >  for (i__ = 2; i__ <= i__2; ++i__)
> > >         {
> > >           a[i__] += c__[i__] * d__[i__];
> > >           b[i__] = a[i__] + d__[i__] + b[i__ - 1];
> > >         }
> > > This happens in the loop in line 2136.
> > > Need to check if we need to open a missed optimization PR for this.
> >
> > I don't think that this is a loop distribution issue. The dependence
> > between the store to a[i] and the load from a[i] doesn't prevent
> > vectorization.
>
> right,
>
> > The problematic one is between the store to b[i] and
> > the load from b[i-1] in the second statement.
>
> ...which is exactly why loop distribution could make this loop
> (partially) vectorizable - separating the first and second
> statements into separate loops would allow vectorizing the first of
> the two resulting loops (which is probably what icc does - icc
> reports that this loop is partially vectrizable).

Yes, I see now.
I applied Sebastian's patch (
http://gcc.gnu.org/ml/gcc-patches/2007-12/msg00215.html) and got
"FIXME: Loop 1 not distributed: failed to build the RDG."

Ira

>
> dorit
>

Re: Optimizations documentation

[Dorit Nuzman]

Thanks a lot for tracking down / opening the relevant PRs.

about:

> > (6) loop distribution is required to break a dependence. This may
> > already be handled by Sebastian's loop-distribution pass that will
> > be incorporated in 4.4.
> > Here is an example:
> >  for (i__ = 2; i__ <= i__2; ++i__)
> >         {
> >           a[i__] += c__[i__] * d__[i__];
> >           b[i__] = a[i__] + d__[i__] + b[i__ - 1];
> >         }
> > This happens in the loop in line 2136.
> > Need to check if we need to open a missed optimization PR for this.>
>
> I don't think that this is a loop distribution issue. The dependence
> between the store to a[i] and the load from a[i] doesn't prevent
> vectorization.

right,

> The problematic one is between the store to b[i] and
> the load from b[i-1] in the second statement.

...which is exactly why loop distribution could make this loop (partially)
vectorizable - separating the first and second statements into separate
loops would allow vectorizing the first of the two resulting loops (which
is probably what icc does - icc reports that this loop is partially
vectrizable).

dorit


Ira Rosen/Haifa/IBM wrote on 17/02/2008 11:42:55:

> Hi,
>
> Dorit Nuzman/Haifa/IBM wrote on 14/02/2008 17:02:45:
>
> > This is an old debt: A while back Tim had sent me a detailed report
> > off line showing which C++ tests (originally from the Dongara loops
> > suite) were vectorized by current g++ or icpc, or both, as well as
> > when the vectorization by icpc required a pragma, or was partial. I
> > went over the loops that were reported to be vectorized by icc but
> > not by gcc, to see which features we are missing. There are 23 such
> > loops (out of a total of 77). They fall into the following 7
categories:
> >
> > (1) scalar evolution analysis fails with "evolution of base is
notaffine".
> > This happens in the 3 loops in lines 4267, 4204 and 511.
> > Here an example:
> >  for (i__ = 1; i__ <= i__2; ++i__)
> >         {
> >           a[i__] = (b[i__] + b[im1] + b[im2]) * .333f;
> >           im2 = im1;
> >           im1 = i__;
> >         }
> > Missed optimization PR to be opened.
>
> I opened PR35224.
>
> >
> > (2) Function calls inside a loop. These are calls to the math
> > functions sin/cos, which I expect would be vectorized if the proper
> > simd math lib was available.
> > This happens in the loop in line 6932.
> > I think there's an open PR for this one (at least for
> > powerpc/Altivec?) - need to look/open.
>
> There is PR22226.
>
> >
> > (3) This one is the most dominant missed optimization: if-conversion
> > is failing to if-convert, most likely due to the very limited
> > handling of loads/stores (i.e. load/store hoisting/sinking is
required).
> > This happens in the 13 loops in lines 4085, 4025, 3883, 3818, 3631,
> > 355, 3503, 2942, 877, 6740, 6873, 5191, 7943.
> > There is on going work towards addressing this issue - see http:
> > //gcc.gnu.org/ml/gcc/2007-07/msg00942.html, http://gcc.gnu.
> > org/ml/gcc/2007-09/msg00308.html. (I think Victor Kaplansky is
> > currently working on this).
> >
> > (4) A scalar variable, whose address is taken outside the loop (in
> > an enclosing outer-loop) is analyzed by the data-references
> > analysis, which fails because it is invariant.
> > Here's an example:
> >   for (nl = 1; nl <= i__1; ++nl)
> >     {
> >       sum = 0.f;
> >       for (i__ = 1; i__ <= i__2; ++i__)
> >         {
> >           a[i__] = c__[i__] + d__[i__];
> >           b[i__] = c__[i__] + e[i__];];
> >             sum += a[i__] + b[i__];];];
> >         }
> >       dummy_ (ld, n, &a[1], &b[1], &c__[1], &d__[1], &e[1], &aa
[aa_offset],>
> >               &bb[bb_offset], &cc[cc_offset], &sum);
> >     }
> > (Analysis of 'sum' fails with "FAILED as dr address is invariant".
> > This happens in the 2 loops in lines 5053 and 332.
> > I think there is a missed optimization PR for this one already. need
> > to look/open.
> >
>
> The related PRs are PR33245 and PR33244. Also there is a FIXME
> comment in tree-data-ref.c before the failure with "FAILED as dr
> address is invariant" error:
>
>       /* FIXME -- data dependence analysis does not work correctly
> for objects with
>          invariant addresses.  Let us fail here until the problem
isfixed.  */
>
>
> > (5) Reduction and induction that involve multiplication (i.e. 'prod
> > *= CST' or 'prod *= a[i]') are currently not supported by the
> > vectorizer. It should be trivial to add support for this feature
> > (for reduction, it shouldn't be much more than adding a case for
> > MULT_EXPR in tree-vectorizer.c:reduction_code_for_scalar_code, I
think).
> > This happens in the 2 loops in lines 4921 and 4632.
> > A missed-optimization PR to be opened.
>
> Opened PR35226.
>
> >
> > (6) loop distribution is required to break a dependence. This may
> > already be handled by Sebastian's loop-distribution pass that will
> > be incorporated in 4.4.
> > Here is an example:
> >  for (i__ = 2; i__ <= i__2; ++i__)
> >         {
> >           a[i__] += c__[i__] * d__[i__];
> >           b[i__] = a[i__] + d__[i__] + b[i__ - 1];
> >         }
> > This happens in the loop in line 2136.
> > Need to check if we need to open a missed optimization PR for this.
>
> I don't think that this is a loop distribution issue. The dependence
> between the store to a[i] and the load from a[i] doesn't prevent
> vectorization. The problematic one is between the store to b[i] and
> the load from b[i-1] in the second statement.
>
> >
> > (7) A dependence, similar to such that would be created by
> > predictive commoning (or even PRE), is present in the loop:
> >  for (i__ = 1; i__ <= i__2; ++i__)
> >         {
> >           a[i__] = (b[i__] + x) * .5f;
> >           x = b[i__];
> >         }
> > This happens in the loop in line 3003.
> > The vectorizer needs to be extended to handle such cases.
> > A missed optimization PR to be opened (if doesn't exist already).
>
> I opened a new PR - 35229. (PR33244 is somewhat related).
>
> Ira

Re: Optimizations documentation

[Ira Rosen]

Hi,

Dorit Nuzman/Haifa/IBM wrote on 14/02/2008 17:02:45:

> This is an old debt: A while back Tim had sent me a detailed report
> off line showing which C++ tests (originally from the Dongara loops
> suite) were vectorized by current g++ or icpc, or both, as well as
> when the vectorization by icpc required a pragma, or was partial. I
> went over the loops that were reported to be vectorized by icc but
> not by gcc, to see which features we are missing. There are 23 such
> loops (out of a total of 77). They fall into the following 7 categories:
>
> (1) scalar evolution analysis fails with "evolution of base is not
affine".
> This happens in the 3 loops in lines 4267, 4204 and 511.
> Here an example:
>  for (i__ = 1; i__ <= i__2; ++i__)
>         {
>           a[i__] = (b[i__] + b[im1] + b[im2]) * .333f;
>           im2 = im1;
>           im1 = i__;
>         }
> Missed optimization PR to be opened.

I opened PR35224.

>
> (2) Function calls inside a loop. These are calls to the math
> functions sin/cos, which I expect would be vectorized if the proper
> simd math lib was available.
> This happens in the loop in line 6932.
> I think there's an open PR for this one (at least for
> powerpc/Altivec?) - need to look/open.

There is PR22226.

>
> (3) This one is the most dominant missed optimization: if-conversion
> is failing to if-convert, most likely due to the very limited
> handling of loads/stores (i.e. load/store hoisting/sinking is required).
> This happens in the 13 loops in lines 4085, 4025, 3883, 3818, 3631,
> 355, 3503, 2942, 877, 6740, 6873, 5191, 7943.
> There is on going work towards addressing this issue - see http:
> //gcc.gnu.org/ml/gcc/2007-07/msg00942.html, http://gcc.gnu.
> org/ml/gcc/2007-09/msg00308.html. (I think Victor Kaplansky is
> currently working on this).
>
> (4) A scalar variable, whose address is taken outside the loop (in
> an enclosing outer-loop) is analyzed by the data-references
> analysis, which fails because it is invariant.
> Here's an example:
>   for (nl = 1; nl <= i__1; ++nl)
>     {
>       sum = 0.f;
>       for (i__ = 1; i__ <= i__2; ++i__)
>         {
>           a[i__] = c__[i__] + d__[i__];
>           b[i__] = c__[i__] + e[i__];];
>             sum += a[i__] + b[i__];];];
>         }
>       dummy_ (ld, n, &a[1], &b[1], &c__[1], &d__[1], &e[1], &aa
[aa_offset],
>               &bb[bb_offset], &cc[cc_offset], &sum);
>     }
> (Analysis of 'sum' fails with "FAILED as dr address is invariant".
> This happens in the 2 loops in lines 5053 and 332.
> I think there is a missed optimization PR for this one already. need
> to look/open.
>

The related PRs are PR33245 and PR33244. Also there is a FIXME comment in
tree-data-ref.c before the failure with "FAILED as dr address is invariant"
error:

      /* FIXME -- data dependence analysis does not work correctly for
objects with
         invariant addresses.  Let us fail here until the problem is fixed.
*/


> (5) Reduction and induction that involve multiplication (i.e. 'prod
> *= CST' or 'prod *= a[i]') are currently not supported by the
> vectorizer. It should be trivial to add support for this feature
> (for reduction, it shouldn't be much more than adding a case for
> MULT_EXPR in tree-vectorizer.c:reduction_code_for_scalar_code, I think).
> This happens in the 2 loops in lines 4921 and 4632.
> A missed-optimization PR to be opened.

Opened PR35226.

>
> (6) loop distribution is required to break a dependence. This may
> already be handled by Sebastian's loop-distribution pass that will
> be incorporated in 4.4.
> Here is an example:
>  for (i__ = 2; i__ <= i__2; ++i__)
>         {
>           a[i__] += c__[i__] * d__[i__];
>           b[i__] = a[i__] + d__[i__] + b[i__ - 1];
>         }
> This happens in the loop in line 2136.
> Need to check if we need to open a missed optimization PR for this.

I don't think that this is a loop distribution issue. The dependence
between the store to a[i] and the load from a[i] doesn't prevent
vectorization. The problematic one is between the store to b[i] and the
load from b[i-1] in the second statement.

>
> (7) A dependence, similar to such that would be created by
> predictive commoning (or even PRE), is present in the loop:
>  for (i__ = 1; i__ <= i__2; ++i__)
>         {
>           a[i__] = (b[i__] + x) * .5f;
>           x = b[i__];
>         }
> This happens in the loop in line 3003.
> The vectorizer needs to be extended to handle such cases.
> A missed optimization PR to be opened (if doesn't exist already).

I opened a new PR - 35229. (PR33244 is somewhat related).

Ira

Re: Optimizations documentation

[Dorit Nuzman]

Dorit Nuzman/Haifa/IBM wrote on 03/01/2008 18:53:25:

> > g++-4.3 seems well ahead of other compilers in ability to vectorize STL

> > iterators:
> >
http://softwarecommunity.intel.com/Wiki/HighPerformanceComputing/688.htm
> >

> good to know.
> I browsed over the posting above; do you have a summary table where
> one could easily see which loops get vectorized by other compilers
> and not by gcc (and vice versa)?
>

This is an old debt: A while back Tim had sent me a detailed report off
line showing which C++ tests (originally from the Dongara loops suite) were
vectorized by current g++ or icpc, or both, as well as when the
vectorization by icpc required a pragma, or was partial. I went over the
loops that were reported to be vectorized by icc but not by gcc, to see
which features we are missing. There are 23 such loops (out of a total of
77). They fall into the following 7 categories:

(1) scalar evolution analysis fails with "evolution of base is not affine".
This happens in the 3 loops in lines 4267, 4204 and 511.
Here an example:
 for (i__ = 1; i__ <= i__2; ++i__)
        {
          a[i__] = (b[i__] + b[im1] + b[im2]) * .333f;
          im2 = im1;
          im1 = i__;
        }
Missed optimization PR to be opened.

(2) Function calls inside a loop. These are calls to the math functions
sin/cos, which I expect would be vectorized if the proper simd math lib was
available.
This happens in the loop in line 6932.
I think there's an open PR for this one (at least for powerpc/Altivec?) -
need to look/open.

(3) This one is the most dominant missed optimization: if-conversion is
failing to if-convert, most likely due to the very limited handling of
loads/stores (i.e. load/store hoisting/sinking is required).
This happens in the 13 loops in lines 4085, 4025, 3883, 3818, 3631, 355,
3503, 2942, 877, 6740, 6873, 5191, 7943.
There is on going work towards addressing this issue - see
http://gcc.gnu.org/ml/gcc/2007-07/msg00942.html,
http://gcc.gnu.org/ml/gcc/2007-09/msg00308.html. (I think Victor Kaplansky
is currently working on this).

(4) A scalar variable, whose address is taken outside the loop (in an
enclosing outer-loop) is analyzed by the data-references analysis, which
fails because it is invariant.
Here's an example:
  for (nl = 1; nl <= i__1; ++nl)
    {
      sum = 0.f;
      for (i__ = 1; i__ <= i__2; ++i__)
        {
          a[i__] = c__[i__] + d__[i__];
          b[i__] = c__[i__] + e[i__];];
            sum += a[i__] + b[i__];];];
        }
      dummy_ (ld, n, &a[1], &b[1], &c__[1], &d__[1], &e[1], &aa[aa_offset],
              &bb[bb_offset], &cc[cc_offset], &sum);
    }
(Analysis of 'sum' fails with "FAILED as dr address is invariant".
This happens in the 2 loops in lines 5053 and 332.
I think there is a missed optimization PR for this one already. need to
look/open.

(5) Reduction and induction that involve multiplication (i.e. 'prod *= CST'
or 'prod *= a[i]') are currently not supported by the vectorizer. It should
be trivial to add support for this feature (for reduction, it shouldn't be
much more than adding a case for MULT_EXPR in
tree-vectorizer.c:reduction_code_for_scalar_code, I think).
This happens in the 2 loops in lines 4921 and 4632.
A missed-optimization PR to be opened.

(6) loop distribution is required to break a dependence. This may already
be handled by Sebastian's loop-distribution pass that will be incorporated
in 4.4.
Here is an example:
 for (i__ = 2; i__ <= i__2; ++i__)
        {
          a[i__] += c__[i__] * d__[i__];
          b[i__] = a[i__] + d__[i__] + b[i__ - 1];
        }
This happens in the loop in line 2136.
Need to check if we need to open a missed optimization PR for this.

(7) A dependence, similar to such that would be created by predictive
commoning (or even PRE), is present in the loop:
 for (i__ = 1; i__ <= i__2; ++i__)
        {
          a[i__] = (b[i__] + x) * .5f;
          x = b[i__];
        }
This happens in the loop in line 3003.
The vectorizer needs to be extended to handle such cases.
A missed optimization PR to be opened (if doesn't exist already).


Thanks, Tim, for the helpful report,

dorit

> thanks,
> dorit