[Bug tree-optimization/53265] New: Warn when undefined behavior implies smaller iteration count

[Bug tree-optimization/53265] New: Warn when undefined behavior implies smaller iteration count

[amonakov at gcc dot gnu.org]

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

             Bug #: 53265
           Summary: Warn when undefined behavior implies smaller iteration
                    count
    Classification: Unclassified
           Product: gcc
           Version: 4.8.0
            Status: UNCONFIRMED
          Keywords: diagnostic
          Severity: enhancement
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: amonakov@gcc.gnu.org


As requested in PR 53128, this is an enhancement request that asks to produce a
warning when loop bound inferred from undefined behavior may be used to
transform the loop in a surprising way.

Example code:

enum {N=4};
int a[N], pfx[N];
void foo()
{
  int i, accum;
  for (i=0, accum=a[0]; i < N; i++, accum+=a[i])
    pfx[i] = accum;
}

VRP in trunk produces an infinite loop from the above. By the way, with
-fno-tree-vrp one would expect that cunroll unrolls just 3 iterations of the
loop, but in fact it unrolls 4, because nb_iterations is not updated when
nb_iterations_upper_bound is reduced from UB analysis.

Can we simply warn when UB analysis reduces nb_iterations_upper_bound and makes
it statically smaller than symbolic nb_iterations?

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-05-07
     Ever Confirmed|0                           |1

--- Comment #1 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-05-07 14:10:48 UTC ---
Confirmed.

It's not so simple as cases I have seen do not involve a statically constant
nb_interations.  Consider

enum {N=4};
int a[N], pfx[N];
void foo(int n)
{
  int i, accum;
  for (i=0, accum=a[0]; i < n; i++, accum+=a[i])
    pfx[i] = accum;
}

and calling that with n == 4.

I was suggesting to warn about optimizing a loop exit test to never stop
iterating.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-01-29 17:22:34 UTC ---
Other examples from
https://lists.fedoraproject.org/pipermail/devel/2013-January/175876.html
to test the potential warning (requires 32-bit integer and 64-bit long long):

void bar (void *);

void
fn1 (void)
{
  unsigned int a[128];
  int i;

  for (i = 0; i < 128; ++i)
    a[i] = i * 0x02000001;
  bar (a);
}

void
fn2 (void)
{
  unsigned long long a[128];
  int i;

  for (i = 0; i < 128; i++)
    a[i] = (i + 1LL) * 0x0123456789ABCDEFLL;
  bar (a);
}

void
fn3 (void)
{
  unsigned char a[16], b[16], c[16];
  int i;

  bar (b);
  for (i = 0; i < (int) (sizeof (a) / sizeof (a[0])); i++)
    {
      c[i + 8] = b[i];
      a[i + 8] = b[i + 8];
    }
  bar (a);
  bar (c);
}

void
fn4 (void)
{
  unsigned int *a[32], *o, i;

  bar (a);
  for (i = 0; i <= sizeof (a) / sizeof (a[0]); i++)
    {
      o = a[i];
      bar (o);
    }
}

void
fn5 (void)
{
  unsigned short a[23940];
  unsigned int b[1140];
  int j;

  bar (b);
  for (j = 0; j < 1140; j++)
    a[23940 + j - 950] = b[j];
  bar (a);
}

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #3 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-01-31 12:13:24 UTC ---
Another testcase, this time from PR56161 :

void bar (void *);

void
fn6 (void)
{
  double a[4][3], b[12];
  int i;
  bar (b);
  for (i = 0; i < 12; i++)
    a[0][i] = b[i] / 10000.0;
  bar (a);
}

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |ppluzhnikov at google dot
                   |                            |com

--- Comment #4 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-11 10:14:18 UTC ---
*** Bug 56589 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-11 14:14:06 UTC ---
The following avoids the "miscompile" in these obvious cases:

Index: gcc/tree-ssa-loop-niter.c
===================================================================
--- gcc/tree-ssa-loop-niter.c   (revision 196594)
+++ gcc/tree-ssa-loop-niter.c   (working copy)
@@ -3345,6 +3345,18 @@ estimate_numbers_of_iterations_loop (str
       bound = gcov_type_to_double_int (nit);
       record_niter_bound (loop, bound, true, false);
     }
+
+  /* If we know the exact number of iterations of this loop avoid all the
+     work below and most importantly do not break code with undefined
+     behavior by recording smaller maximum number of iterations.  */
+  niter = number_of_latch_executions (loop);
+  if (TREE_CODE (niter) == INTEGER_CST)
+    {
+      if (loop->any_upper_bound
+         && loop->nb_iterations_upper_bound.ucmp
+              (tree_to_double_int (niter)) < 0)
+       loop->nb_iterations_upper_bound = tree_to_double_int (niter);
+    }
 }

 /* Sets NIT to the estimated number of executions of the latch of the

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[rguenth at gcc dot gnu.org]

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

--- Comment #6 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-11 14:16:20 UTC ---
To warn,
1) add a flag to struct loop whether we warned for the loop already
2) in both discover_iteration_bound_by_body_walk and
maybe_lower_iteration_bound
   warn if you run into an estimate we end up using and that lowers the
   max iterations below the value returned by number_of_latch_executions ().

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[rguenth at gcc dot gnu.org]

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

--- Comment #7 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-11 14:17:28 UTC ---
When warnings are disabled the whole function can be skipped and
both estimate and bound be initialized by the result from
number_of_latch_executions (if that returns a constant).

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #8 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-11 15:49:00 UTC ---
Created attachment 29637
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29637
gcc48-pr53265.patch

Untested patch.  Not sure about the warning wording, plus no idea how to call
the warning option (-Wnum-loop-iterations, -Wundefined-behavior-in-loop,
something else?), whether to enable it by default, or just for -Wall.
A bigger issue is that I see multiple warnings for the same stmts, despite the
guard in loop structure, because apparently the same loop is represented by
different loop structures during the optimizations.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[rguenth at gcc dot gnu.org]

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

--- Comment #9 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-11 15:58:41 UTC ---
(In reply to comment #8)
> Created attachment 29637 [details]
> gcc48-pr53265.patch
> 
> Untested patch.  Not sure about the warning wording, plus no idea how to call
> the warning option (-Wnum-loop-iterations, -Wundefined-behavior-in-loop,
> something else?), whether to enable it by default, or just for -Wall.
> A bigger issue is that I see multiple warnings for the same stmts, despite the
> guard in loop structure, because apparently the same loop is represented by
> different loop structures during the optimizations.

Yeah, before the tree loop optimization pipeline loops are not preserved ...
(easy to change, apart from code missing to inline a loop tree).

Eventually use gimple_no_warning on the stmt?  Supposedly not very reliable
either.

I think with your patch you also fail to warn for bounds discovered by
discover_iteration_bound_by_body_walk or maybe_lower_iteration_bound.
That said, I'd expected you warn from within record_niter_bound.  Btw,
after number_of_latch_executions () its return value is cached in
loop->nb_iterations, no need to pass around another value.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[amonakov at gcc dot gnu.org]

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

--- Comment #10 from Alexander Monakov <amonakov at gcc dot gnu.org> 2013-03-11 16:15:36 UTC ---
(In reply to comment #8)
> Not sure about the warning wording

What about (... "iteration %E invokes undefined behavior", max)?

> plus no idea how to call the warning option (-Wnum-loop-iterations, 
> -Wundefined-behavior-in-loop, something else?)

Can it be -Waggressive-loop-optimizations to follow existing pairs of
-{W,fno-}strict-{aliasing,overflow} for the recently added
-fno-aggressive-loop-optimizations?

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[manu at gcc dot gnu.org]

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

Manuel López-Ibáñez <manu at gcc dot gnu.org> changed:

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

--- Comment #11 from Manuel López-Ibáñez <manu at gcc dot gnu.org> 2013-03-11 16:42:00 UTC ---
(In reply to comment #8)
> Untested patch.  Not sure about the warning wording, plus no idea how to call
> the warning option (-Wnum-loop-iterations, -Wundefined-behavior-in-loop,
> something else?), whether to enable it by default, or just for -Wall.

If the rate of false positives is expected to be low, then I would suggest
enabled by default, otherwise, I would say Wall.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[manu at gcc dot gnu.org]

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

--- Comment #12 from Manuel López-Ibáñez <manu at gcc dot gnu.org> 2013-03-11 16:49:25 UTC ---
(In reply to comment #10)
> (In reply to comment #8)
> > Not sure about the warning wording
> 
> What about (... "iteration %E invokes undefined behavior", max)?
> 
> > plus no idea how to call the warning option (-Wnum-loop-iterations, 
> > -Wundefined-behavior-in-loop, something else?)
> 
> Can it be -Waggressive-loop-optimizations to follow existing pairs of
> -{W,fno-}strict-{aliasing,overflow} for the recently added
> -fno-aggressive-loop-optimizations?

I think these two are very good suggestions. Thanks, Alexander.

And if this gets implemented for 4.8, I think it will make the new loop
optimizations much safer to use and, hence, much more useful.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #29637|0                           |1
        is obsolete|                            |

--- Comment #13 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-11 17:10:30 UTC ---
Created attachment 29639
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29639
gcc48-pr53265.patch

Updated version of the patch.  Haven't added docs yet.  The reason for not
warning in discover_iteration_bound_by_body_walk etc. is that I'd say the
undefined behavior warning would then be misleading, those don't detect
undefined behavior, but something else, right?  Can you think of a testcase
where we'd decrease number of iterations in those routines when it has
constant number_of_latch_iterations?
Also, with the estimate_numbers_of_loop_iterations_loop second hunk I'm not
really sure about the warning name - after all, when we warn, we actually don't
aggressively optimize anything, we aggressively optimize only when we actually
don't warn and can't easily warn.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #29639|0                           |1
        is obsolete|                            |

--- Comment #14 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-12 11:25:01 UTC ---
Created attachment 29650
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29650
gcc48-pr53265.patch

The last patch was missing == INTEGER_CST.  Still, this patch doesn't even
bootstrap, I'll attach here various snippets that need investigations.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #15 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-12 11:26:15 UTC ---
Created attachment 29651
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29651
X2

Incremental debugging hack.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #16 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-12 11:30:02 UTC ---
First issue is (with -Werror -O2) error on attribs.c.  Reduced testcase:
const void *a, *b, *c, *d, *e;
const void *f[4];
void
foo (void)
{
  unsigned long i;
  f[0] = a; f[1] = b; f[2] = c; f[3] = d;
  for (i = 0; i < (sizeof (f) / sizeof (f[0])); i++)
    if (f[i] == __null)
      f[i] = e;
}

In function ‘void foo()’:
cc1plus: warning: iteration 3ul invokes undefined behavior
[-Waggressive-loop-optimizations]
/tmp/attribs.ii:8:3: note: containing loop
   for (i = 0; i < (sizeof (f) / sizeof (f[0])); i++)
   ^

We'd better not have false positives on testcases as simple as this.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #17 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-12 11:48:09 UTC ---
Second issue is from caller-save.c (setup_save_areas), again -Werror -O2:

int a, b[53][5], c[53][5];
int bar (void);

void
foo (void)
{
  int i, j, k;
  for (i = 0; i < 53; i++)
    for (j = 16 / (((a & 1) != 0) ? 8 : 4); j > 0; j--)
      {
        int d = 1;
        if (b[i][j] == 0 || c[i][1] != 0)
          continue;
        for (k = 0; k < j; k++)
          if (c[i + k][1])
            {
              d = 0;
              break;
            }
        if (!d)
          continue;
        c[i][j] = bar ();
      }
}

The problem I have in this testcase is that the undefined behavior isn't known
to happen unconditionally, b or c array content upon entry might very well
prevent it from happening.  So, if we want to warn for those, we'd need to have
two levels of the warning, one enabled perhaps by default, that hopefully
shouldn't have any false positives, and one with a different wording, enabled
perhaps by -Wall or even just -Wextra that would just say that iteration N may
trigger undefined behavior.  Haven't tried to find out if any target could have
problems there.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #18 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-12 12:35:59 UTC ---
There is also a problem in unwind-dw2.c, but that looks like something we
should probably fix:
../../../libgcc/unwind-dw2.c: In function ‘execute_cfa_program’:
../../../libgcc/unwind-dw2.c:1133:30: warning: iteration 2ul invokes undefined
behavior [-Waggressive-loop-optimizations]
        fs->regs.reg[reg].how = REG_SAVED_OFFSET;
                              ^
../../../libgcc/unwind-dw2.c:1131:4: note: containing loop
    for (reg = 16; reg < 32; ++reg)
    ^

        case DW_CFA_GNU_window_save:
          /* ??? Hardcoded for SPARC register window configuration.  */
          for (reg = 16; reg < 32; ++reg)
            {
              fs->regs.reg[reg].how = REG_SAVED_OFFSET;
              fs->regs.reg[reg].loc.offset = (reg - 16) * sizeof (void *);
            }
          break;

but DWARF_FRAME_REGISTERS is 17 on x86_64/i386, so reg[17] is still ok, but
reg[18] is undefined behavior.  Of course it doesn't matter much, because
DW_CFA_GNU_window_save isn't used on non-SPARC, but perhaps we could use
for (reg = 16; reg < MIN (32, DWARF_FRAME_REGISTERS + 1); ++reg)
or similar (I think it wouldn't generate worst code on SPARC, because it would
be still constant folded to 32 there, and to 18 on ix86_64 etc.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #19 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-12 12:40:54 UTC ---
On:
int a[18];

void
foo (void)
{
  int i;
  for (i = 16; i < 32; i++)
    a[i] = 26;
}
distilled from unwind-dw2.c, I'm just surprised that at -O2
the http://gcc.gnu.org/bugzilla/show_bug.cgi?id=53265#c15
debugging hack reports that we are in some cases increasing the number of
iterations from 2 to 16, but later on from 1 to 15?  Have we peeled one
iteration or what happened?

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #20 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-12 14:13:56 UTC ---
Ok, based on reading what exactly record_estimate does, I've tried:
--- tree-ssa-loop-niter.c.xx    2013-03-12 13:47:08.000000000 +0100
+++ tree-ssa-loop-niter.c    2013-03-12 15:01:50.498107788 +0100
@@ -2655,7 +2655,10 @@ record_nonwrapping_iv (struct loop *loop
       && warn_aggressive_loop_optimizations
       && (cfun->curr_properties & PROP_loops) != 0
       && !loop->warned_aggressive_loop_optimizations
-      && max.ucmp (tree_to_double_int (loop->nb_iterations)) < 0)
+      && (upper || realistic)
+      && (max + double_int_one).ucmp (tree_to_double_int
(loop->nb_iterations))
+     < 0
+      && dominated_by_p (CDI_DOMINATORS, loop->latch, gimple_bb (stmt)))
     {
       location_t loop_locus = UNKNOWN_LOCATION;
       edge e = single_exit (loop);

incremental patch (for !upper && !realistic it gives up early, for
!dominated_by_p
it records the bounds, but doesn't call record_niter_bound, and
record_nonwrapping_iv calls unconditionally record_estimate with is_exit=false,
for which it adds double_int_one to the bounds.

With this #c16 and #c17 compile without warnings, unfortunately the testcase in
the patch regresses two tests, fn4 and fn7 (the latter is from the SPEC2k6
issue).

max + double_int_one above is unsafe btw, we'd need something that
record_estimate does to check for overflows.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #29650|0                           |1
        is obsolete|                            |

--- Comment #21 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-12 20:09:58 UTC ---
Created attachment 29657
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29657
gcc48-pr53265.patch

Updated patch that actually passed bootstrap/regtest.  Unfortunately, for fn4
and fn7 in the testcase to pass, I had to give up with only warning in
PROP_loops state, because the cunrolli pass optimizes those loops.

While it bootstrapped fine (with unwind-dw2.c fix I'll attach too), there were
some regressions, some -Waggressive-loop-optimizations warnings during
bootstrap/regtest and also with the additional debugging hack in various places
the number of iterations upper bound increased.

The regressions are:
../../gcc/ada/exp_ch7.adb:3540:11: warning: iteration 2147483646 invokes
undefined behavior [-Waggressive-loop-optimizations]
warning during x86_64 Ada build and:

+FAIL: gcc.dg/torture/pr49518.c  -O3 -fomit-frame-pointer  (test for excess
errors)
+FAIL: gcc.dg/torture/pr49518.c  -O3 -fomit-frame-pointer -funroll-loops  (test
for excess errors)
+FAIL: gcc.dg/torture/pr49518.c  -O3 -fomit-frame-pointer -funroll-all-loops
-finline-functions  (test for excess errors)
+FAIL: gcc.dg/torture/pr49518.c  -O3 -g  (test for excess errors)
+FAIL: g++.dg/opt/longbranch2.C -std=gnu++98 (test for excess errors)
+FAIL: g++.dg/opt/longbranch2.C -std=gnu++11 (test for excess errors)
+FAIL: libmudflap.c/fail37-frag.c (-O2) (test for excess errors)
+FAIL: libmudflap.c/fail37-frag.c (-O3) (test for excess errors)

(longbranch2.C only on i686, not on x86_64).  For fail32-frag.c, I believe we
just want to add asm ("" : "+r" (i)); into the loop to hide stuff from the
optimizers.

With the debugging hack, the cases of increasing number of iterations at the
end of estimate_numbers_of_iterations_loop are (except for pr53265.c, which of
course has tons of them):

64 ../../gcc/ada/exp_ch7.adb:3540 7ffffffd 0 ffffffff 0
{32,64} /usr/src/gcc/gcc/testsuite/gcc.dg/torture/pr49518.c:10 2 0 fffffffd 0
32 /usr/src/gcc/gcc/testsuite/g++.dg/opt/longbranch2.C:36 100 0 1ff 0
32 /usr/src/gcc/gcc/testsuite/g++.dg/opt/longbranch2.C:36 ff 0 1fe 0    
{32,64} /usr/src/gcc/gcc/testsuite/gfortran.dg/do_1.f90:10 9 0 a 0   
{32,64} /usr/src/gcc/gcc/testsuite/gfortran.dg/do_1.f90:16 4 0 5 0
{32,64} /usr/src/gcc/gcc/testsuite/gfortran.dg/do_1.f90:21 3 0 4 0
{32,64} /usr/src/gcc/libmudflap/testsuite/libmudflap.c/fail37-frag.c:15 4 0 5 0

In exp_ch7.adb it looks like pass ordering, cunrolli is run on dead code there,
*.copyrename2 has:
  [../../gcc/ada/exp_ch7.adb : 3540:11] ind.127_3 = 1;
  [../../gcc/ada/exp_ch7.adb : 3540:11] if (ind.127_3 > 1)
    goto <bb 3>;
  else
    goto <bb 6>;

  <bb 3>:
  # fent_39 = PHI <[../../gcc/ada/exp_ch7.adb : 3535:7] fent_2(2)>
  # j_40 = PHI <[../../gcc/ada/exp_ch7.adb : 3540:11] 1(2)>

  <bb 4>:
  # fent_6 = PHI <fent_39(3), [../../gcc/ada/exp_ch7.adb : 3541:10] fent_7(5)>
  # j_4 = PHI <j_40(3), [../../gcc/ada/exp_ch7.adb : 3540:11] j_5(5)>
  # DEBUG j => j_4
  # DEBUG fent => fent_6
  [../../gcc/ada/exp_ch7.adb : 3540:11] j_5 = j_4 + 1;
  [../../gcc/ada/exp_ch7.adb : 3540:11] # DEBUG j => j_5
  [../../gcc/ada/exp_ch7.adb : 3541:10] fent_7 = sinfo.next_entity (fent_6);
  [../../gcc/ada/exp_ch7.adb : 3541:10] # DEBUG fent => fent_7
  [../../gcc/ada/exp_ch7.adb : 3540:25] if (ind.127_3 != j_5)
    goto <bb 5>;
  else
    goto <bb 6>;

where both j and ind.127 are signed SImode vars.  number_of_latch_iterations
estimates the bound as 0xffffffff, signed overflow decreases that guess, but it
is really in dead code (something visible only through inlining though).
ccp2 immediately after cunrolli would fix this up, but that is too late.

For pr49518.c, I guess it is reasonable to warn, if the loop invariant
conditions are all such that it keeps looping, then the loop indeed triggers
undefined behavior.

Thoughts?

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #22 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-12 21:47:38 UTC ---
Short C testcase reproducing the exp_ch7.adb issue (for -O2):
void bar (int);

__attribute__((noinline)) static int
foo (int x)
{
  int i = 1;
  if (x > 1)
    do
      bar (i);
    while (++i != x);
}

void
baz (void)
{
  foo (1);
  foo (1);
  foo (1);
}

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #29657|0                           |1
        is obsolete|                            |

--- Comment #23 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-13 10:36:14 UTC ---
Created attachment 29661
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=29661
gcc48-pr53265.patch

Updated patch as per IRC discussions.  Still need to look at longbranch2.C and
do_1.f90, then test it.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[rguenth at gcc dot gnu.org]

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

--- Comment #24 from Richard Biener <rguenth at gcc dot gnu.org> 2013-03-13 11:00:11 UTC ---
(In reply to comment #23)
> Created attachment 29661 [details]
> gcc48-pr53265.patch
> 
> Updated patch as per IRC discussions.  Still need to look at longbranch2.C and
> do_1.f90, then test it.

Looks good.  Few comments:

+  number_of_latch_executions (loop);

add a comment what side-effect you are interested in.

+
+  /* If we know the exact number of iterations of this loop avoid all the
+     work below and most importantly do not break code with undefined
+     behavior by recording smaller maximum number of iterations.  */
+  if (loop->nb_iterations
+      && TREE_CODE (loop->nb_iterations) == INTEGER_CST
+      && loop->any_upper_bound
+      && loop->nb_iterations_upper_bound.ucmp
+          (tree_to_double_int (loop->nb_iterations)) < 0)
+    loop->nb_iterations_upper_bound = tree_to_double_int
(loop->nb_iterations);

We don't avoid any work, so adjust the comment.  I'd also simply do:

   /* If we know the exact number of iterations record that as the
      upper bound as well.  This avoids breaking code with undefined
      behavior by eventually recording a smaller maximum.  */
   if (loop->nb_iterations
       && TREE_CODE (loop->nb_iterations) == INTEGER_CST)
     {
       loop->any_upper_bound = true;
       loop->nb_iterations_upper_bound = tree_to_double_int
(loop->nb_iterations);
     }

that's always correct.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #25 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-14 09:13:45 UTC ---
Author: jakub
Date: Thu Mar 14 09:13:36 2013
New Revision: 196650

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=196650
Log:
    PR tree-optimization/53265
    * common.opt (Waggressive-loop-optimizations): New option.
    * tree-ssa-loop-niter.c: Include tree-pass.h.
    (do_warn_aggressive_loop_optimizations): New function.
    (record_estimate): Call it.  Don't add !is_exit bounds to loop->bounds
    if number_of_latch_executions returned constant.
    (estimate_numbers_of_iterations_loop): Call number_of_latch_executions
    early.  If number_of_latch_executions returned constant, set
    nb_iterations_upper_bound back to it.
    * cfgloop.h (struct loop): Add warned_aggressive_loop_optimizations
    field.
    * Makefile.in (tree-ssa-loop-niter.o): Depend on $(TREE_PASS_H).
    * doc/invoke.texi (-Wno-aggressive-loop-optimizations): Document.

    * gcc.dg/pr53265.c: New test.
    * gcc.dg/torture/pr49518.c: Add -Wno-aggressive-loop-optimizations
    to dg-options.
    * g++.dg/opt/longbranch2.C (EBCOTLut): Double sizes of a2 and a3
    arrays.
    * gcc.dg/tree-ssa/cunroll-10.c (main): Rename to foo.  Add argument
    n, use it as high bound instead of 4.

    * unwind-dw2.c (execute_cfa_program): Avoid
    -Waggressive-array-optimizations warnings for DW_CFA_GNU_window_save
    on targets with DWARF_FRAME_REGISTERS < 32.

    * testsuite/libmudflap.c/fail37-frag.c: Add optimization barrier.

Added:
    trunk/gcc/testsuite/gcc.dg/pr53265.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/Makefile.in
    trunk/gcc/cfgloop.h
    trunk/gcc/common.opt
    trunk/gcc/doc/invoke.texi
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/g++.dg/opt/longbranch2.C
    trunk/gcc/testsuite/gcc.dg/torture/pr49518.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/cunroll-10.c
    trunk/gcc/tree-ssa-loop-niter.c
    trunk/libgcc/ChangeLog
    trunk/libgcc/unwind-dw2.c
    trunk/libmudflap/ChangeLog
    trunk/libmudflap/testsuite/libmudflap.c/fail37-frag.c

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #26 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-03-14 10:54:45 UTC ---
Author: jakub
Date: Thu Mar 14 10:54:38 2013
New Revision: 196655

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=196655
Log:
    PR tree-optimization/53265
    * gcc.dg/graphite/scop-3.c (toto): Increase array size to avoid
    undefined behavior.
    * gcc.dg/graphite/id-6.c (test): Likewise.
    * gcc.dg/graphite/pr35356-2.c: Adjust regexp patterns to only look for
    MIN_EXPR and MAX_EXPR in GIMPLE stmts.

Modified:
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/graphite/id-6.c
    trunk/gcc/testsuite/gcc.dg/graphite/pr35356-2.c
    trunk/gcc/testsuite/gcc.dg/graphite/scop-3.c

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[ppluzhnikov at google dot com]

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

--- Comment #27 from Paul Pluzhnikov <ppluzhnikov at google dot com> 2013-04-29 23:18:29 UTC ---
Here is a reduced test case in which g++ (GCC) 4.9.0 20130426 (experimental)
produces infinite loop with -O2 due to aggressive loop optimization, but
doesn't warn (making the bug in user code hard to find).

g++ -O2 test.cc -Wall && ./a.out
Segmentation fault

g++ -O2 test.cc -Wall -fno-aggressive-loop-optimizations && ./a.out && echo ok
ok


struct Puzzle
{
  int r[9];
  int ignored[18];
} p;

int a, b;
int main()
{
  int c = 0;
  for (b = 0; b < 27; b++)
    {
      if (p.r[b] == 0)
        c |= p.r[a];
      if (c != 0)
        return c;
    }
  return c;
}

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #28 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-04-30 06:07:23 UTC ---
The warning is only printed if the loop has a single exit and known constant
iteration count without the undefined behavior analysis, and when the warning
is printed, we don't apply the aggressive analysis anyway.

It is hard to warn in all cases, but what exactly would be the cases anyway,
the amount of surprise on undefined behavior varies a lot.

The point of the warning was to warn about the easy cases, for the rest applies
what we write in bugs.html - if a suspicious program behaviour goes away with
-fno-aggressive-loop-optimizations, most likely it is a fault of the compiled
code, not the compiler.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jakub at gcc dot gnu.org]

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

--- Comment #29 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-04-30 06:45:54 UTC ---
If you want another testcase which doesn't warn and is optimized based on the
assumption that undefined behavior doesn't occur, then say:
http://blog.regehr.org/archives/918#comment-8646
contains:
int a[4];

__attribute__((noinline, noclone)) int
foo (int x)
{
  int i, r = 0, n = x & 31;
  for (i = 0; i < n; i++)
    r += a[i];
  return r;
}

int
main ()
{
  int x = 255;
  __asm volatile ("" : "+r" (x));
  return foo (x);
}

But in both the testcases warning is questionable, in your testcase, if p.r[0]
is non-zero and any of p.r[1] through p.r[8] is zero, then no undefined
behaviour is triggered and the program is valid, and gcc doesn't break it in
any way.
Similarly with the my testcase above and foo being called with x where the low
5 bits are 0 to 4, again, valid in that case (ignore main and the value 255
being hidden from the compiler there).
What would you like to warn about?  That if the loop is invoked with variables
and data that result in undefined behaviour that the behaviour will be
undefined?
The difference between where we know is there the compiler knows that whenever
you enter the loop construct, you will hit the undefined behavior (unless say
one of the called functions in the body throws or exits), so the level of false
positives is low.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[jackie.rosen at hushmail dot com]

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

Jackie Rosen <jackie.rosen at hushmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jackie.rosen at hushmail dot com

--- Comment #30 from Jackie Rosen <jackie.rosen at hushmail dot com> ---
*** Bug 260998 has been marked as a duplicate of this bug. ***
Seen from the domain http://volichat.com
Page where seen: http://volichat.com/adult-chat-rooms
Marked for reference. Resolved as fixed @bugzilla.

[Bug tree-optimization/53265] Warn when undefined behavior implies smaller iteration count

[pinskia at gcc dot gnu.org]

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

--- Comment #31 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
For the testcase in comment #0 we do warn:
<source>: In function 'void foo()':
<source>:7:47: warning: iteration 3 invokes undefined behavior
[-Waggressive-loop-optimizations]
    7 |   for (i=0, accum=a[0]; i < N; i++, accum+=a[i])
      |                                            ~~~^
<source>:7:27: note: within this loop
    7 |   for (i=0, accum=a[0]; i < N; i++, accum+=a[i])
      |                         ~~^~~

For comment #2:
<source>: In function 'void fn1()':
<source>:11:14: warning: iteration 64 invokes undefined behavior
[-Waggressive-loop-optimizations]
   11 |     a[i] = i * 0x02000001;
      |            ~~^~~~~~~~~~~~
<source>:10:17: note: within this loop
   10 |   for (i = 0; i < 128; ++i)
      |               ~~^~~~~
<source>: In function 'void fn2()':
<source>:22:22: warning: iteration 112 invokes undefined behavior
[-Waggressive-loop-optimizations]
   22 |     a[i] = (i + 1LL) * 0x0123456789ABCDEFLL;
      |            ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
<source>:21:17: note: within this loop
   21 |   for (i = 0; i < 128; i++)
      |               ~~^~~~~
<source>: In function 'void fn3()':
<source>:35:16: warning: iteration 8 invokes undefined behavior
[-Waggressive-loop-optimizations]
   35 |       c[i + 8] = b[i];
      |       ~~~~~~~~~^~~~~~
<source>:33:17: note: within this loop
   33 |   for (i = 0; i < (int) (sizeof (a) / sizeof (a[0])); i++)
      |               ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
<source>: In function 'void fn5()':
<source>:64:24: warning: iteration 950 invokes undefined behavior
[-Waggressive-loop-optimizations]
   64 |     a[23940 + j - 950] = b[j];
      |     ~~~~~~~~~~~~~~~~~~~^~~~~~
<source>:63:17: note: within this loop
   63 |   for (j = 0; j < 1140; j++)
      |               ~~^~~~~~
<source>: In function 'void fn3()':
<source>:35:16: warning: 'void* __builtin_memcpy(void*, const void*, long
unsigned int)' writing 16 bytes into a region of size 8 overflows the
destination [-Wstringop-overflow=]
   35 |       c[i + 8] = b[i];
      |       ~~~~~~~~~^~~~~~
<source>:29:31: note: at offset 8 into destination object 'c' of size 16
   29 |   unsigned char a[16], b[16], c[16];
      |                               ^
<source>:36:16: warning: 'void* __builtin_memcpy(void*, const void*, long
unsigned int)' writing 16 bytes into a region of size 8 overflows the
destination [-Wstringop-overflow=]
   36 |       a[i + 8] = b[i + 8];
      |       ~~~~~~~~~^~~~~~~~~~
<source>:29:17: note: at offset 8 into destination object 'a' of size 16
   29 |   unsigned char a[16], b[16], c[16];
      |                 ^

So this looks partialy fixed. Someone will need to do a summary of what is
fixed and not though.