[Bug tree-optimization/42108] [4.4/4.5/4.6 Regression] 50% performance regression

[Bug tree-optimization/42108] [4.4/4.5/4.6 Regression] 50% performance regression

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.4.5                       |4.4.6

[Bug tree-optimization/42108] [4.4/4.5/4.6 Regression] 50% performance regression

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2009-11-19 16:49:51         |2011-02-21 16:49:51

--- Comment #51 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-02-21 14:33:16 UTC ---
Re-confirmed.  The PR42131 "fix" didn't improve the situation.

[Bug tree-optimization/42108] [4.4/4.5/4.6/4.7 Regression] 50% performance regression

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.4.6                       |4.4.7

[Bug tree-optimization/42108] [4.5/4.6/4.7/4.8 Regression] 50% performance regression

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.4.7                       |4.5.4

--- Comment #52 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-03-13 12:44:42 UTC ---
4.4 branch is being closed, moving to 4.5.4 target.

[Bug tree-optimization/42108] [4.5/4.6/4.7/4.8 Regression] 50% performance regression

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.4                       |4.6.4

--- Comment #53 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-07-02 10:54:40 UTC ---
The 4.5 branch is being closed, adjusting target milestone.

[Bug tree-optimization/42108] [4.6/4.7/4.8 Regression] 50% performance regression

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

--- Comment #54 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-16 12:36:52 UTC ---
Re-confirmed on trunk.  The initial GFortran IL is still ... awkward.  Apart
from the issue of using a canonicalized IV at all we have

                            D.1910 = i;
                            D.1911 = *nnd;
                            D.1912 = *n;
                            k = D.1910;
                            if (D.1912 > 0)
                              {
                                if (D.1911 < D.1910) goto L.6;
                              }
                            else
                              {
                                if (D.1911 > D.1910) goto L.6;
                              }
                            countm1.6 = (unsigned int) ((D.1911 - D.1910) *
(D.1912 < 0 ? -1 : 1)) / (unsigned int) ((D.1912 < 0 ? -1 : 1) * D.1912);
                            while (1)
                              {
...
                                  do_exit.7 = countm1.6 == 0;
                                  countm1.6 = countm1.6 + 4294967295;
                                  if (do_exit.7) goto L.6;
                                }
                              }
                            L.6:;

in the computation of countm1.6 we have a redundant (D.1912 < 0 ? -1 : 1)
test which ends up complicating the CFG.  It's also redundant again
with a test that was done just above.  In fact it completely cancels out
in the countm1 compute.  (the exit test via a do_exit temporary is
because of a local change in my tree ... eh)

Also note that

      /* Calculate the loop count.  to-from can overflow, so
         we cast to unsigned.  */

but we do

  (unsigned)(to * step_sign - from * step_sign) / (unsigned) (step * step_sign)

that does not avoid overflow of step * step_sign (step == INT_MIN, step_sign ==
-1) nor overflow of to * step_sign - from * step_sign which we fold to
(to - from) * step_sign anyway (signed overflow is undefined, heh).
I believe we need to do

  ((unsigned)to - (unsigned)from) * (unsigned)step_sign / ((unsigned) step *
(unsigned) step_sign)

to avoid these issues.

[Bug tree-optimization/42108] [4.6/4.7/4.8 Regression] 50% performance regression

[burnus at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

Tobias Burnus <burnus at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |burnus at gcc dot gnu.org

--- Comment #55 from Tobias Burnus <burnus at gcc dot gnu.org> 2013-01-17 14:20:06 UTC ---
(In reply to comment #54)
> Re-confirmed on trunk.  The initial GFortran IL is still ... awkward.  Apart
> from the issue of using a canonicalized IV at all we have

This part has been fixed by the patch
http://gcc.gnu.org/ml/fortran/2013-01/msg00136.html (partially undoing
PR42131),

Commit: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=195260

[Bug tree-optimization/42108] [4.6/4.7/4.8 Regression] 50% performance regression

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

--- Comment #56 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-17 14:30:10 UTC ---
4.3 vs. trunk I get 9.5s vs. 12.3s for -O3.  With 4.7 and 4.6 I get the same
result (on Intel CPUs).  Thus basically re-confirmed after the recent
patches.

[Bug tree-optimization/42108] [4.6/4.7/4.8 Regression] 50% performance regression

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

--- Comment #57 from Richard Biener <rguenth at gcc dot gnu.org> 2013-01-17 14:42:11 UTC ---
A proper fix these days (with tuples) is to add new tree codes that carry
the knowledge that

  countm1.6_40 = _38 / _39;

may not trap.  The frontend already knows this (step == _39 == 0 has undefined
behavior according to the language).

This is work in a similar area as no-undefined-overflow or the proposed
changes to make FP rounding modes explicit.

[Bug tree-optimization/42108] [4.7/4.8/4.9 Regression] 50% performance regression

[jakub at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.6.4                       |4.7.4

--- Comment #58 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-04-12 15:15:25 UTC ---
GCC 4.6.4 has been released and the branch has been closed.

[Bug tree-optimization/42108] [4.7/4.8/4.9/4.10 Regression] 50% performance regression

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.7.4                       |4.8.4

--- Comment #59 from Richard Biener <rguenth at gcc dot gnu.org> ---
The 4.7 branch is being closed, moving target milestone to 4.8.4.

[Bug tree-optimization/42108] [4.8/4.9/5 Regression] 50% performance regression

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

--- Comment #61 from Richard Biener <rguenth at gcc dot gnu.org> ---
(In reply to Richard Biener from comment #60)
> Ok, so I have a patch that teaches LIM to move the division by using the
> value-range information we now store.

Which can't be done this way ... (the value-range is only valid in the place
it was computed, not where LIM may move it to)

[Bug tree-optimization/42108] [4.8/4.9/5 Regression] 50% performance regression

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

--- Comment #62 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 34238
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=34238&action=edit
frontend patch

So the issue is that the division is executed conditionally because it is
placed
after the loop entry check.  The frontend generates

      if (step > 0)
        {
         if (to < from)
           goto exit_label;
         countm1 = (to - from) / step;
        }
      else
        {
         if (to > from)
           goto exit_label;
         countm1 = (from - to) / -step;
        }

which ends up optimized to (as step is known to be positive here):

    if (to < from)
     {
       countm1 = (to - from) / step;
       ...loop...

if we instead generate

      if (step > 0)
        {
         countm1 = (to - from) / step;
         if (to < from)
           goto exit_label;
        }
      else
        {
         countm1 = (from - to) / -step;
         if (to > from)
           goto exit_label;
        }

the division can be hoisted out of the outer loop (at the cost of computing
countm1 even when the loop is not entered -- but that would have happened
if the desired transform happened anyway).

Note that if step > 0 cannot be optimized we still have the same issue,
so in theory we could generate

   if (step > 0)
     {
       tem1 = (to - from);
       tem2 = step;
     }
   else
     {
       tem1 = (from - to);
       tem2 = -step;
     }
   countm1 = tem1 / tem2;
   if (step > 0)
    {
      if (to < from)
        goto exit_label;
    }
   else
    {
      if (to > from)
        goto exit_label;
    }

but hoisting the division with conditional computed operands is a lot more
expensive (but possible for exactly two ops, and likely done).  The
runtime overhead from the above is one extra branch.

If we do that then unfortunately jump threading undoes that change creating
the first variant again.

[Bug tree-optimization/42108] [4.8/4.9/5 Regression] 50% performance regression

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

--- Comment #63 from Richard Biener <rguenth at gcc dot gnu.org> ---
Created attachment 34239
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=34239&action=edit
LIM patch

This is a patch to loop invariant motion I was playing with to use range
information to move a stmt up to a place where we can determine the range
information is still correct.  Unfortunately for the testcase this doesn't
allow moving the division at all and we are lucky that we have range
information
at all because of the fortran frontend casting 'n' to unsigned before dividing
by it.

Another possibility is to (finally) teach LIM to hoist code which conditional
execution status needs to be preserved by guarding the hoisted code with that
conditional code.  Thus hoist a / b as either b != 0 ? a / b : 0(?) or
as <execution condition> ? a / b : 0.  Where for this case the condition
of execution is probably more complex than testing the denominator for zero
(thus testing the condition under which we have to preserve execution).
Followup optimizations then eventually can get rid of that condition.

[Bug tree-optimization/42108] [4.8/4.9/5 Regression] 50% performance regression

[rguenther at suse dot de]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

--- Comment #65 from rguenther at suse dot de <rguenther at suse dot de> ---
On Wed, 10 Dec 2014, burnus at gcc dot gnu.org wrote:

> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108
> 
> --- Comment #64 from Tobias Burnus <burnus at gcc dot gnu.org> ---
> (In reply to Richard Biener from comment #63)
> > Unfortunately for the testcase this doesn't allow moving the division at all
> > and we are lucky that we have range information at all because of the fortran
> > frontend casting 'n' to unsigned before dividing by it.
> 
> If it helps and the semantic is preserved, there is no reason not to 
> completely change what tree code the Fortran FE generates for loops.

The attached patch helps, but only sofar as enabling moving the division
out one loop level - if you add another nest the entry condition on it
will prevent moving the division further.

> [I think one reason for the odd way tree code for loops is generated is: The
> current code makes it simple to permit loops which are always run once, as some
> Fortran 66 compilers did. For instance, "DO i = 2, 1" would then be executed
> once. (Such loops are not permitted in F66 - and some compilers executed them
> once others zero times; since F77, such loops are permitted and executed zero
> times. Unsurprisingly, some old code from the 60s relies on the execute once
> feature.)
> 
> g77 and some commercial compilers have a compile flag like "-f66", gfortran
> hasn't and I don't think it ever will.]

I wondered if

  DO i = 1, 1, 0

is valid (a step of zero).  Note that DO i = 2, 1 wouldn't be executed
once with the current generated code, only DO i = 1, 1 is, but with
step == 0 it would divide by zero.

[Bug tree-optimization/42108] [4.8/4.9/5 Regression] 50% performance regression

[sfilippone at uniroma2 dot it]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

--- Comment #66 from Salvatore Filippone <sfilippone at uniroma2 dot it> ---
As far as I remember(In reply to rguenther@suse.de from comment #65)
> On Wed, 10 Dec 2014, burnus at gcc dot gnu.org wrote:
> 
> > Fortran 66 compilers did. For instance, "DO i = 2, 1" would then be executed
> > once. (Such loops are not permitted in F66 - and some compilers executed them
> > once others zero times; since F77, such loops are permitted and executed zero
> > times. Unsurprisingly, some old code from the 60s relies on the execute once
> > feature.)
> > 
> > g77 and some commercial compilers have a compile flag like "-f66", gfortran
> > hasn't and I don't think it ever will.]
> 
> I wondered if
> 
>   DO i = 1, 1, 0
> 
> is valid (a step of zero).  Note that DO i = 2, 1 wouldn't be executed
> once with the current generated code, only DO i = 1, 1 is, but with
> step == 0 it would divide by zero.

Step 0 is not allowed (see e.g. F2003 Handbook, sect. 8.7.2.1.1). 
Salvatore

[Bug tree-optimization/42108] [4.8/4.9 Regression] 50% performance regression

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |5.0
            Summary|[4.8/4.9/5 Regression] 50%  |[4.8/4.9 Regression] 50%
                   |performance regression      |performance regression
      Known to fail|                            |4.3.6

--- Comment #67 from Richard Biener <rguenth at gcc dot gnu.org> ---
Fixed on trunk (sofar).

--- Comment #68 from Richard Biener <rguenth at gcc dot gnu.org> ---
Author: rguenth
Date: Thu Dec 11 15:52:47 2014
New Revision: 218630

URL: https://gcc.gnu.org/viewcvs?rev=218630&root=gcc&view=rev
Log:
2014-12-11  Richard Biener  <rguenther@suse.de>

    PR tree-optimization/42108
    * trans-stmt.c (gfc_trans_do): Execute the division computing
    countm1 before the loop entry check.

    * gfortran.dg/pr42108.f90: Amend.

Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/trans-stmt.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gfortran.dg/pr42108.f90

[Bug tree-optimization/42108] [4.8/4.9 Regression] 50% performance regression

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.4                       |4.8.5

--- Comment #69 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.8.4 has been released.

[Bug tree-optimization/42108] [4.8/4.9 Regression] 50% performance regression

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.8.5                       |4.9.3

--- Comment #70 from Richard Biener <rguenth at gcc dot gnu.org> ---
The gcc-4_8-branch is being closed, re-targeting regressions to 4.9.3.

[Bug tree-optimization/42108] [4.9 Regression] 50% performance regression

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

--- Comment #71 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
GCC 4.9.3 has been released.

[Bug tree-optimization/42108] [4.9 Regression] 50% performance regression

[jakub at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.9.3                       |4.9.4

[Bug tree-optimization/42108] [4.9 Regression] 50% performance regression

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42108
Bug 42108 depends on bug 42436, which changed state.

Bug 42436 Summary: VRP should mark non-trapping integer divisions
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=42436

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |FIXED