[Bug rtl-optimization/23361] New: Can't eliminate empty loops with power of two step and variable bounds

[Bug rtl-optimization/23361] New: Can't eliminate empty loops with power of two step and variable bounds

[chris at bubblescope dot net]

This may be related to bug 19001 (loops with power of two step and variable bounds not unrolled)

Neither of the following empty loops is eliminated:

void foo(int a, int b)
{ for(;a!=b;a+=4); }

void foo(int a, int b)
{ for(;a<b;a+=4); }

Similarily to 19001, these loops come about because of iterating over an range of pointers doing 
something for each element (for example deleting them) which for some types turns out to be a null 
operation. Fixing this will allow a large number of workarounds in libstdc++ to be removed.

-- 
           Summary: Can't eliminate empty loops with power of two step and
                    variable bounds
           Product: gcc
           Version: 4.1.0
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P2
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: chris at bubblescope dot net
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-12 18:57 -------
With -funsafe-loop-optimizations we remove them.

Using -Wunsafe-loop-optimizations, we get:
t.c:2: warning: cannot optimize loop, the loop counter may overflow


I mentioned this before to transform the loops such that we know if they overflow or not and Zdenek 
said it was not useful which I feel is still wrong.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
          Component|rtl-optimization            |tree-optimization


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

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[chris at bubblescope dot net]

------- Additional Comments From chris at bubblescope dot net  2005-08-12 18:58 -------
*** Bug 23362 has been marked as a duplicate of this bug. ***

-- 


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

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-12 19:10 -------
See http://gcc.gnu.org/ml/gcc-patches/2005-06/msg02275.html which is the email I was talking 
about.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-08-12 19:10:31
               date|                            |


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

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-08-12 23:43 -------
Subject: Re:  Can't eliminate empty loops with
	power of two step and variable bounds

On Fri, 2005-08-12 at 19:10 +0000, pinskia at gcc dot gnu dot org wrote:
> ------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-12 19:10 -------

Personally, i think -funsafe-loop-optimizations should be on by default
in -O3, with a warning for when we rely on it.

It's *incredibly* rare that a user actually intends for a loop counter
to be able to overflow.




-- 


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

Re: [Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[Daniel Berlin]

On Fri, 2005-08-12 at 19:10 +0000, pinskia at gcc dot gnu dot org wrote:
> ------- Additional Comments From pinskia at gcc dot gnu dot org  2005-08-12 19:10 -------

Personally, i think -funsafe-loop-optimizations should be on by default
in -O3, with a warning for when we rely on it.

It's *incredibly* rare that a user actually intends for a loop counter
to be able to overflow.

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[giovannibajo at libero dot it]

------- Additional Comments From giovannibajo at libero dot it  2005-08-13 10:01 -------
One thing is that if 'a' and 'b' are originally pointers of the same type, it 
should be clear the the loop can be removed. When they are lowered to integers, 
instead, we lose the precious alignment information. Can't the empty loop be 
removed before the pointers are lowered?
Or am I missing something?

-- 


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

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[bonzini at gcc dot gnu dot org]

------- Additional Comments From bonzini at gcc dot gnu dot org  2005-09-15 13:46 -------
if these ints are signed, you should be able to remove these loops.

-- 


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

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[chris at bubblescope dot net]

------- Additional Comments From chris at bubblescope dot net  2005-09-15 14:02 -------
Expanding slightly, I tried the following 4 functions. All were removed by -funsafe-loop-optimisations, 
but only foo3 was removed by -O3 without -funsafe-loop-optimisations. I can't see a good reason to 
remove foo3 but not remove foo4?

void foo(int a, int b)
{ for(;a!=b;a+=4); }


void foo2(int a, int b)
{ for(;a<b;a+=4); }

void foo3(int*a, int* b)
{ for(;a<b;a++); }

void foo4(int*a, int*b)
{ for(;a!=b;a++); }

-- 


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

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[rguenth at gcc dot gnu dot org]

------- Comment #13 from rguenth at gcc dot gnu dot org  2007-02-09 14:19 -------
Fixed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
           Keywords|patch                       |missed-optimization
         Resolution|                            |FIXED
   Target Milestone|---                         |4.3.0


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

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[rguenth at gcc dot gnu dot org]

------- Comment #12 from rguenth at gcc dot gnu dot org  2007-02-09 13:29 -------
Subject: Bug 23361

Author: rguenth
Date: Fri Feb  9 13:29:11 2007
New Revision: 121742

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=121742
Log:
2007-02-09  Zdenek Dvorak  <dvorakz@suse.cz>
        Richard Guenther  <rguenther@suse.de>

        PR middle-end/23361
        * fold-const.c (fold_comparison): Handle obfuscated comparisons
        against INT_MIN/INT_MAX.
        * tree-ssa-loop-ivcanon.c (remove_empty_loop): Print to dump
        file if a loop is removed.

        * gcc.dg/fold-compare-3.c: New testcase.
        * gcc.dg/tree-ssa/loop-24.c: Likewise.

Added:
    trunk/gcc/testsuite/gcc.dg/fold-compare-3.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/loop-24.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/fold-const.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-loop-ivcanon.c


-- 


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

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[rakdver at gcc dot gnu dot org]

------- Comment #11 from rakdver at gcc dot gnu dot org  2007-02-08 14:38 -------
Patch:

http://gcc.gnu.org/ml/gcc-patches/2007-02/msg00704.html


-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                URL|                            |http://gcc.gnu.org/ml/gcc-
                   |                            |patches/2007-
                   |                            |02/msg00704.html
           Keywords|                            |patch


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

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[rakdver at gcc dot gnu dot org]

------- Comment #10 from rakdver at gcc dot gnu dot org  2007-02-05 21:45 -------
Hello,

(In reply to comment #8)
> (In reply to comment #1)
> > With -funsafe-loop-optimizations we remove them.
> > Using -Wunsafe-loop-optimizations, we get:
> > t.c:2: warning: cannot optimize loop, the loop counter may overflow
> 
> If the loop counter will overflow for signed types, that is undefined and
> we should do it no matter what unless -fwrapv is turned on.

actually, the warning is missleading here.  The problem is that
the number of iterations of this loop is
((unsigned) b - (unsigned) a + 3) / 4
but this formula does not work if (unsigned) b - (unsigned) a + 3 overflows,
which is what we fail to verify.

The obvious-looking solution is to use formula 1 + ((unsigned) b - (unsigned) a
-1) / 4 that does not suffer from this problem.  I tried that, there are some
problems with this as well (but I forgot what the problems are, so I will need
to check again).


-- 

rakdver at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rakdver at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2005-08-12 19:10:31         |2007-02-05 21:45:12
               date|                            |


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

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[pcarlini at suse dot de]

------- Comment #9 from pcarlini at suse dot de  2007-02-05 18:53 -------
Referring to Comment #7, currently in mainline, 4_2-branch and even 4.1.1 the
only loop not eliminated at -O2 is foo2 - actually, that is pretty good for the
library: very nice that we don't need special code to avoid foo4. Anyway,
should we eliminate foo2 too?


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rakdver at atrey dot karlin
                   |                            |dot mff dot cuni dot cz,
                   |                            |pcarlini at suse dot de


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

[Bug tree-optimization/23361] Can't eliminate empty loops with power of two step and variable bounds

[pinskia at gcc dot gnu dot org]

------- Comment #8 from pinskia at gcc dot gnu dot org  2005-11-09 03:09 -------
(In reply to comment #1)
> With -funsafe-loop-optimizations we remove them.
> Using -Wunsafe-loop-optimizations, we get:
> t.c:2: warning: cannot optimize loop, the loop counter may overflow

If the loop counter will overflow for signed types, that is undefined and
we should do it no matter what unless -fwrapv is turned on.


-- 


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