Bug 55481

Created attachment 28784 [details]
zip containing preprocessed source of reduced examples and multiple binaries. only gcc48-O2 exhibits the bug.

I bet there is an access out of bounds in the loop that produces the infinite loop.

Actually, the same problem happens at -O3 with const int SIZE > 20. base_iterations can be very high; it's just SIZE that's the problem.

Infinite loops are a sign for out-of-bound array accesses, 4.8 now very
aggressively exploits undefined behavior that this triggers.

Btw, it also happens when I declare data8 as

int8_t data8[SIZE*2 ];

so it does look like genuine bug in GCC.  It loops in

#0  0x00000000004009cc in test_constant<signed char, custom_or_constants<signed char> > (count=13, label=0x4012da "int8_t or constants", 
    first=0x6020d0 <data8> '\001' <repeats 13 times>)
    at benchmark_shared_tests.h:661

btw.

Created attachment 28790 [details]
reduced testcase

Reduced testcase attached.

More reduced testcase, fails when compiled at -O2 with the C++ frontend,
passes compiled with the C frontend ...

typedef signed char int8_t;
extern void abort (void);

#define SIZE 13
double init_value = 1.0;
int8_t data8[SIZE];

static inline int8_t __attribute__((always_inline))
do_shift(int8_t input) { return ((int8_t)(23) | (int8_t)(10)); }

int main(int argc, char** argv)
{
  int8_t *first = data8;
  int8_t *last = data8+SIZE;
  while (first != last) *first++ = (int8_t)(init_value);
  first = data8;
  int i;
  for(i = 0; i < 1000; ++i)
    {
      int8_t result = 0;
      int n;
      for (n = 0; n < SIZE; ++n)
        result += do_shift( first[n] );
      int8_t temp = (int8_t)SIZE * do_shift((int8_t)init_value);
      if (result != temp)
        abort ();
    }
  return 0;
}

Note that the frontends warn with

lucky13x.c: In function 'int main(int, char**)':
lucky13x.c:24:64: warning: overflow in implicit constant conversion [-Woverflow]
       int8_t temp = (int8_t)SIZE * ((int8_t)(23) | (int8_t)(10));

when manually inlining do_shift at the checking point:

      int8_t temp = (int8_t)SIZE * ((int8_t)(23) | (int8_t)(10));
      if (result != temp)
        abort ();

this computes 13 * 31 which is 403 so the warning is correct.  Fixed with
an extra cast.  This also means that

      for (n = 0; n < SIZE; ++n)
        result += do_shift( first[n] );

triggers the bug about doing the addition in the wrong type and the bug
is fixed by rewriting this as

        result = result + do_shift (first[n]);

that is, self-modify is not correctly doing the addition in 'int'.  And thus
this is a dup of PR35634 I believe (-fwrapv also fixes this).

The following even more reduced testcase is not fixed by the patch pending
for PR35634.

typedef signed char int8_t;

#define SIZE 13

static inline int8_t do_shift() { return 31; }

int main(int argc, char** argv)
{
  int i;
  for(i = 0; i < 1000; ++i)
    {
      int8_t result = 0;
      int n;
      for (n = 0; n < SIZE; ++n)
        result += do_shift();
      int8_t temp = (int8_t)((int8_t)SIZE * ((int8_t)(23) | (int8_t)(10)));
      if (result != temp)
        __builtin_abort ();
    }
  return 0;
}


With the C++ frontend we correctly do

        D.2194 = do_shift ();
        D.2207 = (int) result;
        D.2208 = (int) D.2194;
        D.2209 = D.2207 + D.2208;
        result = (int8_t) D.2209;

anyway, but then IVOPTs comes around and changes it:

   <bb 4>:
   # result_17 = PHI <result_8(3), 0(7)>
-  # n_18 = PHI <n_9(3), 0(7)>
-  # ivtmp_12 = PHI <ivtmp_13(3), 13(7)>
   _6 = (int) result_17;
   _7 = _6 + 31;
-  result_8 = (int8_t) _7;
-  n_9 = n_18 + 1;
-  ivtmp_13 = ivtmp_12 - 1;
-  if (ivtmp_13 != 0)
+  _1 = result_17 + 31;
+  result_8 = _1;
+  if (result_8 != -109)
     goto <bb 3>;

performing the computation in int8_t again which causes VRP to "miscompile"
the test.

Testcase that fails (infinite loop) with both the C and the C++ frontend at -O2:

int main()
{
  signed char result = 0;
  int n;
  for (n = 0; n < 13; ++n)
    {
      int tem = result;
      tem = tem + 31;
      result = tem;
    }
  if (result != -109)
    __builtin_abort ();
  return 0;
}

Caused by

2012-06-27  Richard Guenther  <rguenther@suse.de>

        PR middle-end/53676
        * tree-chrec.c (chrec_convert_1): Represent truncation to
        a type with undefined overflow as truncation to an unsigned
        type converted to the type with undefined overflow.
        * tree-scalar-evolution.c (interpret_rhs_expr): For computing
        the scalar evolution of a truncated widened operation avoid
        looking at the non-existing evolution of the widened operation
        result.

Mine.

We have

@@ -15,22 +15,11 @@
   (scalar = result_11)
 (get_scalar_evolution 
   (scalar = result_11)
-  (scalar_evolution = result_11))
+  (scalar_evolution = (signed char) {0, +, 31}_1))

that isn't wrong.  But IVOPTs happily uses STRIP_NOPs which also strips
sign-conversions.  simple_iv returns true for result_11 in

  signed char result;

  <bb 3>:
  # result_11 = PHI <result_5(4), 0(2)>
  # ivtmp_10 = PHI <ivtmp_9(4), 13(2)>
  tem_3 = (int) result_11;
  tem_4 = tem_3 + 31;
  result_5 = (signed char) tem_4;
  ivtmp_9 = ivtmp_10 - 1;
  if (ivtmp_9 != 0)
    goto <bb 4>;
  else
    goto <bb 5>;

  <bb 4>:
  goto <bb 3>;

now, but iv->no_overflow is false (and IVOPTs nowhere uses that flag ...).

I can fix this for example with

Index: tree-ssa-loop-ivopts.c
===================================================================
--- tree-ssa-loop-ivopts.c      (revision 193887)
+++ tree-ssa-loop-ivopts.c      (working copy)
@@ -982,6 +982,9 @@ determine_biv_step (gimple phi)
   if (!simple_iv (loop, loop, name, &iv, true))
     return NULL_TREE;
 
+  if (!iv.no_overflow)
+    return NULL_TREE;
+
   return integer_zerop (iv.step) ? NULL_TREE : iv.step;
 }
 
but I'm not sure what invariants should hold for BIVs and if the overflow
check should happen in a different place instead.  Zdenek?

> now, but iv->no_overflow is false (and IVOPTs nowhere uses that flag ...).
> 
> I can fix this for example with
> 
> Index: tree-ssa-loop-ivopts.c
> ===================================================================
> --- tree-ssa-loop-ivopts.c      (revision 193887)
> +++ tree-ssa-loop-ivopts.c      (working copy)
> @@ -982,6 +982,9 @@ determine_biv_step (gimple phi)
>    if (!simple_iv (loop, loop, name, &iv, true))
>      return NULL_TREE;
> 
> +  if (!iv.no_overflow)
> +    return NULL_TREE;
> +
>    return integer_zerop (iv.step) ? NULL_TREE : iv.step;
>  }
> 
> but I'm not sure what invariants should hold for BIVs and if the overflow
> check should happen in a different place instead.  Zdenek?

Ivopts transformations are intended to work even with wrapping induction variables;
so this does not seem to be the right place to fix the problem.  I will have
to have a closer look to see what goes wrong.

This is a problem in rewrite_use_nonlinear_expr, which should leave the statement defining the biv untouched (as suggested in the comment at its beginning) but does not.  Investigating further...

Created attachment 28928 [details]
A proposed patch

This patch fixes the error (and also makes the code more clearly match what is described in the comments).  Long story: we try to avoid rewriting computations that define bivs, as that is usually unnecessary.  However, there is a special case where rewriting is still needed; e.g.,

loop
{
  tmp = biv + 1;
  use (tmp);
  biv = tmp + 1;   (*)
}

Ivopts may decide to eliminate the temporary variable tmp by expressing its use in some other way (based on a different biv, etc.).  So, if we did not rewrite (*), it would refer to a variable that is no longer defined.

And in this case, we used a wrong way of expressing the biv computation that may cause signed overflows.  The patch makes us instead to fall back to the general rewriting case, which does not have this problem.  Untested (beyond the single testcase + C-only bootstrap).

Thanks Zdenek - I'll give the patch further testing.

Author: rguenth
Date: Wed Dec 12 13:07:19 2012
New Revision: 194444

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=194444
Log:
2012-12-12  Zdenek Dvorak  <ook@ucw.cz>

	PR tree-optimization/55481
	* tree-ssa-loop-ivopts.c (rewrite_use_nonlinear_expr): Fall
	back to general rewriting if we cannot leave an original biv
	definition alone.

	* gcc.dg/torture/pr55481.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr55481.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-loop-ivopts.c

Fixed.

*** Bug 56488 has been marked as a duplicate of this bug. ***

Author: rguenth
Date: Fri Mar  1 12:29:39 2013
New Revision: 196377

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=196377
Log:
2013-03-01  Richard Biener  <rguenther@suse.de>

	PR tree-optimization/55481
	* gcc.dg/torture/pr56488.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr56488.c
Modified:
    trunk/gcc/testsuite/ChangeLog

Fixed for 4.7.3 as well.

Author: rguenth
Date: Fri Mar  1 13:55:11 2013
New Revision: 196379

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=196379
Log:
2013-03-01  Richard Biener  <rguenther@suse.de>

	Backport from mainline
	2012-12-12  Zdenek Dvorak  <ook@ucw.cz>

	PR tree-optimization/55481
	* tree-ssa-loop-ivopts.c (rewrite_use_nonlinear_expr): Fall
	back to general rewriting if we cannot leave an original biv
	definition alone.

	* gcc.dg/torture/pr55481.c: New testcase.
	* gcc.dg/torture/pr56488.c: Likewise.

Added:
    branches/gcc-4_7-branch/gcc/testsuite/gcc.dg/torture/pr55481.c
    branches/gcc-4_7-branch/gcc/testsuite/gcc.dg/torture/pr56488.c
Modified:
    branches/gcc-4_7-branch/gcc/ChangeLog
    branches/gcc-4_7-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_7-branch/gcc/tree-ssa-loop-ivopts.c