[Bug rtl-optimization/19210] New: [4.0 Regression] not using do-loop for some loops

[Bug rtl-optimization/19210] New: [4.0 Regression] not using do-loop for some loops

[pinskia at gcc dot gnu dot org]

Take following loop:
int a[220000];
void 
f (int n)
{
  int k;
  for(k = 3;k <= n;k++) {
    a[k] = k;
  }
}

On the mainline we produce:
L4:
        stw r9,0(r2)
        addi r9,r9,1
        cmpw cr7,r3,r9
        addi r2,r2,4
        bge+ cr7,L4

But with 3.3.2, we use bdnz:
L9:
        slwi r3,r11,2
        stwx r11,r3,r9
        addi r11,r11,1
        bdnz L9

-- 
           Summary: [4.0 Regression] not using do-loop for some loops
           Product: gcc
           Version: 4.0.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: minor
          Priority: P2
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pinskia at gcc dot gnu dot org
                CC: gcc-bugs at gcc dot gnu dot org
GCC target triplet: powerpc-darwin


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at gcc dot gnu dot
                   |                            |org
      Known to fail|                            |4.0.0
      Known to work|                            |3.3.2
   Target Milestone|---                         |4.0.0


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-30 20:47 -------
I should note that this comes from sixtrack (or rather from a fortran to C converted version of sixtrack).

-- 


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[rakdver at gcc dot gnu dot org]

------- Additional Comments From rakdver at gcc dot gnu dot org  2004-12-30 22:28 -------
Doloop optimizer believes that the loop may be infinite.  There are two ways 
how to prove that this is not the case:

1) k is signed, and thus cannot overflow with -fno-wrapv
2) k cannot run out of the bounds of the array

On rtl level 1) is no longer available.  Using 2) would probably be possible, 
but relatively difficult.

The simplest solution seems to be using information about number of iterations 
computed at tree level.  This is however also a nontrivial project requiring 
changes in many parts of gcc (and at least a few weeks of work), and as such 
this solution cannot be used in 4.0.

-- 


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2004-12-31 00:49 -------
Zdenek, I have troubles understanding how such a loop can ever be infinite:

- if wrapv, sooner or later K will reach any N (and thus, surely it will become 
less or equal to any given N).
- if nowrapv, my understanding is that all bets are off: if f() is called with 
N<=3 the loop will terminate, otherwise it's undefined behaviour. In such a 
situation, we can still perform doloop because it's not going to screw the 
program any more than it is already.

What am I missing?

-- 


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-12-31 00:54 -------
(In reply to comment #3)
What I don't understand is why this was fine in 3.3.2 and not in 4.0.0 by the new do-loop.

-- 


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz  2004-12-31 00:56 -------
Subject: Re:  [4.0 Regression] not using do-loop for some loops

> Zdenek, I have troubles understanding how such a loop can ever be infinite:
> 
> - if wrapv, sooner or later K will reach any N (and thus, surely it will become 
> less or equal to any given N).
>
> - if nowrapv, my understanding is that all bets are off: if f() is called with 
> N<=3 the loop will terminate, otherwise it's undefined behaviour. In such a 
> situation, we can still perform doloop because it's not going to screw the 
> program any more than it is already.
> 
> What am I missing?

I am afraid your interpretation of the code does not make much sense to
me.  The loop always terminates except for the case when n == MAX_INT
and -fwrapv.  In case n == MAX_INT and -fno-wrapv the behavior is
undefined.


-- 


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz  2004-12-31 01:29 -------
Subject: Re:  [4.0 Regression] not using do-loop for some loops

> (In reply to comment #3)
> What I don't understand is why this was fine in 3.3.2 and not in 4.0.0 by the new do-loop.

Because the analysis in 3.3.2 is buggy.  Doloop pattern is used even in the
following case (in that there is no problem with undefined behavior):

void
f (unsigned n)
{
  unsigned k;
  for(k = 3;k <= n;k++)
    {
    }
}

Which is a misscompilation in case n == ~0.


-- 


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[dje at gcc dot gnu dot org]

------- Additional Comments From dje at gcc dot gnu dot org  2004-12-31 19:38 -------
Could we use/extend -ffinite-math-only option to cover this case and assert that
the loop will not be infinite?


-- 


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[rakdver at atrey dot karlin dot mff dot cuni dot cz]

------- Additional Comments From rakdver at atrey dot karlin dot mff dot cuni dot cz  2004-12-31 20:36 -------
Subject: Re:  [4.0 Regression] not using do-loop for some loops

> Could we use/extend -ffinite-math-only option to cover this case and assert that
> the loop will not be infinite?

I would not reuse this flag (it controls behavior of floating point arithmetics and
overloading it in this way does not seem a good idea to me).

However I would like having something like -funsafe-loop-opts that would
allow the optimizer to assume all such conditions that are practically
always true (e.g. that induction variables does not overflow, loops with
nontrivial exit condition are not infinite, etc.).


-- 


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[dje at gcc dot gnu dot org]

------- Additional Comments From dje at gcc dot gnu dot org  2004-12-31 23:55 -------
XLC includes the option

          strict_induction
                      Turns off induction variable optimizations
                      that have the potential to alter the semantics of a
                      user's program. The default is "nostrict_induction" at
                      -O2 or higher and "strict_induction" otherwise.
                      "nostrict_induction" is recomended if your program does
                      not have overflows or wrap arounds of loop induction
                      variables.

We probably need something similar in GCC.  Note that XLC enables it when
optimizing.

Most programmers do not expect to be limited by the undefined wrapping behavior.
   They are not using the extremes.

-- 


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-06 23:09 -------
I think we can confirm this now.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
           Priority|P2                          |P3
   Last reconfirmed|0000-00-00 00:00:00         |2005-01-06 23:09:42
               date|                            |


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[bonzini at gcc dot gnu dot org]

------- Additional Comments From bonzini at gcc dot gnu dot org  2005-01-24 08:28 -------
The thread on -funsafe-loop-optimizations extinguished without any result. 
Zdenek, maybe you should propose the patch together with adding
-Wunsafe-loop-optimizations to -Wextra, and without adding
-funsafe-loop-optimizations to -O2 for now (maybe it can be revisited for 4.1,
and the 3.3 behavior would be a point in favor of it).


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bonzini at gcc dot gnu dot
                   |                            |org


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[steven at gcc dot gnu dot org]

------- Additional Comments From steven at gcc dot gnu dot org  2005-02-10 11:06 -------
Is this really a regression if, really, 3.3 was buggy? 

-- 


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

[Bug rtl-optimization/19210] [4.0 Regression] not using do-loop for some loops

[bonzini at gcc dot gnu dot org]

------- Additional Comments From bonzini at gcc dot gnu dot org  2005-02-10 12:50 -------
No, it is not, still I would not close it as WONTFIX.  I'd rather see it
suspended, and even better I'd like to see an approval for Zdenek's unsafe loop
optimization patch.

-- 


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

[Bug rtl-optimization/19210] not using do-loop for some loops

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-02-10 15:40 -------
Ok, lets remove the target milestone and suspend this bug then.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |SUSPENDED
            Summary|[4.0 Regression] not using  |not using do-loop for some
                   |do-loop for some loops      |loops
   Target Milestone|4.0.0                       |---


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

[Bug rtl-optimization/19210] not using do-loop for some loops

[bonzini at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |bonzini at gcc dot gnu dot
                   |dot org                     |org
             Status|SUSPENDED                   |ASSIGNED
   Last reconfirmed|2005-01-06 23:09:42         |2005-05-05 15:03:36
               date|                            |


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

[Bug rtl-optimization/19210] not using do-loop for some loops

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2005-07-21 07:24 -------
Subject: Bug 19210

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	bonzini@gcc.gnu.org	2005-07-21 07:24:35

Modified files:
	gcc            : ChangeLog Makefile.in common.opt loop-iv.c 
	                 predict.c tree-flow.h tree-scalar-evolution.c 
	                 tree-ssa-loop-ivcanon.c tree-ssa-loop-ivopts.c 
	                 tree-ssa-loop-niter.c 
	gcc/doc        : invoke.texi 
	gcc/testsuite  : ChangeLog 
Added files:
	gcc/testsuite/gcc.dg/tree-ssa: pr19210-1.c pr19210-2.c 

Log message:
	gcc:
	2005-07-21  Paolo Bonzini  <bonzini@gnu.org>
	Zdenek Dvorak  <dvorakz@suse.cz>
	
	PR tree-optimization/19210
	* common.opt (Wunsafe-loop-optimizations, funsafe-loop-optimizations):
	New.
	* Makefile.in (tree-ssa-loop-niter.o): Depend intl.o.
	* loop-iv.c (get_simple_loop_desc): If -funsafe-loop-optimizations,
	rely on unproven assumptions.
	* predict.c (predict_loops): Adjust call to number_of_iterations_exit.
	* tree-flow.h (number_of_iterations_exit): Add final parameter.
	* tree-scalar-evolution.c (number_of_iterations_in_loop): Adjust call
	to number_of_iterations_exit.
	* tree-ssa-loop-ivcanon.c (empty_loop_p): Likewise.
	* tree-ssa-loop-ivopts.c (niter_for_exit): Likewise.
	* tree-ssa-loop-niter.c (find_loop_niter,
	estimate_numbers_of_iterations_loop): Likewise.
	(number_of_iterations_exit): Honor the new options.
	* doc/invoke.texi (Wunsafe-loop-optimizations,
	funsafe-loop-optimizations): Document them.
	
	gcc/testsuite:
	2005-07-21  Paolo Bonzini  <bonzini@gnu.org>
	
	* gcc.dg/tree-ssa/pr19210-1.c: New.
	* gcc.dg/tree-ssa/pr19210-2.c: New.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/ChangeLog.diff?cvsroot=gcc&r1=2.9496&r2=2.9497
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/Makefile.in.diff?cvsroot=gcc&r1=1.1525&r2=1.1526
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/common.opt.diff?cvsroot=gcc&r1=1.81&r2=1.82
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/loop-iv.c.diff?cvsroot=gcc&r1=2.34&r2=2.35
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/predict.c.diff?cvsroot=gcc&r1=1.153&r2=1.154
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-flow.h.diff?cvsroot=gcc&r1=2.128&r2=2.129
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-scalar-evolution.c.diff?cvsroot=gcc&r1=2.30&r2=2.31
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-loop-ivcanon.c.diff?cvsroot=gcc&r1=2.17&r2=2.18
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-loop-ivopts.c.diff?cvsroot=gcc&r1=2.84&r2=2.85
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/tree-ssa-loop-niter.c.diff?cvsroot=gcc&r1=2.32&r2=2.33
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/doc/invoke.texi.diff?cvsroot=gcc&r1=1.652&r2=1.653
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/ChangeLog.diff?cvsroot=gcc&r1=1.5791&r2=1.5792
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/pr19210-1.c.diff?cvsroot=gcc&r1=NONE&r2=1.1
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/testsuite/gcc.dg/tree-ssa/pr19210-2.c.diff?cvsroot=gcc&r1=NONE&r2=1.1



-- 


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

[Bug rtl-optimization/19210] not using do-loop for some loops

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-07-21 08:39 -------
Fixed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.1.0


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