Bug 36691

Summary: [4.2 Regression] wrong value left in induction variable
Product: gcc Reporter: John Regehr <regehr>
Component: middle-endAssignee: Not yet assigned to anyone <unassigned>
Status: RESOLVED FIXED    
Severity: normal CC: cnstar9988, fang, gcc-bugs, pinskia, rakdver, rguenth, spop
Priority: P1 Keywords: wrong-code
Version: 4.4.0   
Target Milestone: 4.3.2   
Host: i686-pc-linux-gnu Target: i686-pc-linux-gnu
Build: i686-pc-linux-gnu Known to work: 4.1.0 4.3.2 4.4.0
Known to fail: 4.1.1 4.3.1 4.2.5 Last reconfirmed: 2008-07-10 20:26:41

Description John Regehr 2008-07-01 22:39:38 UTC
This is seen using svn 137327 on Ubuntu Feisty.  I believe 0 is the correct result.

[regehr@babel tmp35]$ current-gcc -O0 -fwrapv small.c -o small
[regehr@babel tmp35]$ ./small
0
[regehr@babel tmp35]$ current-gcc -O1 -fwrapv small.c -o small
[regehr@babel tmp35]$ ./small
255

[regehr@babel tmp35]$ current-gcc -v
Using built-in specs.
Target: i686-pc-linux-gnu
Configured with: ../configure --program-prefix=current- --enable-languages=c,c++ --prefix=/home/regehr
Thread model: posix
gcc version 4.4.0 20080701 (experimental) (GCC) 

[regehr@babel tmp35]$ cat small.c

#include <stdio.h>

unsigned char g_5;

void func_1 (void);
void func_1 (void)
{
  for (g_5 = -7; g_5 >= 4; g_5 -= 5);
}

int main (void)
{
  func_1 ();
  printf ("%d\n", g_5);
  return 0;
}
Comment 1 Richard Biener 2008-07-02 09:36:54 UTC
This is SCCP.  And then both ivcanon and ivopts.  Thus,

 -fno-tree-scev-cprop -fno-ivopts -fno-tree-loop-ivcanon

fixes it.

Confirmed with -O.
Comment 2 Joseph S. Myers 2008-07-04 22:42:47 UTC
Closing 4.1 branch.
Comment 3 Richard Biener 2008-07-10 14:29:08 UTC
Sebastian, I think this is one for you ... ;)
Comment 4 Sebastian Pop 2008-07-10 20:26:41 UTC
Okay, I'll have a look at it.  Thanks for pointing me to it.
Comment 5 littlestar 2008-08-04 12:42:34 UTC
ping...
Comment 6 Richard Biener 2008-08-04 13:00:20 UTC
Slightly differently "worded" the testcase is

unsigned int g_5;

void func_1 (void)
{
  for (g_5 = 9; g_5 >= 4; g_5 -= 5)
    ;
}

extern void abort (void);
int main (void)
{
  func_1 ();
  if (g_5 != 0)
    abort ();
  return 0;
}

so the loop wraps once (9, 4, UINT_MAX, ..., 5, 0).

From the scev-cprop dump we see that the number of iterations is wrong:

Analyzing # of iterations of loop 1
  exit condition 3 < [4, + , 4294967291]
  bounds on difference of bases: 1 ... 1
  result:
    # of iterations 1, bounded by 1
  (set_nb_iterations_in_loop = 1))
Comment 7 littlestar 2008-08-04 13:12:40 UTC
confirmed gcc 4.2.4, -O3.

gcc test.c -O3
Comment 8 Richard Biener 2008-08-04 13:36:31 UTC
Because somehow we get into

  /* If we can determine the final value of the control iv exactly, we can
     transform the condition to != comparison.  In particular, this will be
     the case if DELTA is constant.  */
  if (number_of_iterations_lt_to_ne (type, iv0, iv1, niter, &delta, step,
                                     bnds))
    {
      affine_iv zps;

and that figures it can just use [0, 5] - but number_of_iterations_lt_to_ne
didn't add any assumptions...  why does it take the "absolute value of
the step", and why do we compute that (unconditionally) by negating the
step?

It looks like at least

      /* The final value of the iv is iv0->base - MOD, assuming that this
         computation does not overflow, and that
         iv0->base - MOD <= iv1->base. */
      if (!iv0->no_overflow && !integer_zerop (mod))

is wrong, as iv0 is just { 3, 0, true } (mod == 4), so certainly the
assumption computed (if we would compute it) is false.

So, with

Index: tree-ssa-loop-niter.c
===================================================================
--- tree-ssa-loop-niter.c       (revision 138620)
+++ tree-ssa-loop-niter.c       (working copy)
@@ -677,7 +677,7 @@ number_of_iterations_lt_to_ne (tree type
   tree tmod;
   mpz_t mmod;
   tree assumption = boolean_true_node, bound, noloop;
-  bool ret = false;
+  bool no_overflow, ret = false;
   tree type1 = type;
   if (POINTER_TYPE_P (type))
     type1 = sizetype;
@@ -692,12 +692,13 @@ number_of_iterations_lt_to_ne (tree type
   mpz_set_double_int (mmod, tree_to_double_int (mod), true);
   mpz_neg (mmod, mmod);
 
+  no_overflow = iv0->no_overflow && iv1->no_overflow;
   if (integer_nonzerop (iv0->step))
     {
       /* The final value of the iv is iv1->base + MOD, assuming that this
         computation does not overflow, and that
         iv0->base <= iv1->base + MOD.  */
-      if (!iv1->no_overflow && !integer_zerop (mod))
+      if (!no_overflow && !integer_zerop (mod))
        {
          bound = fold_build2 (MINUS_EXPR, type,
                               TYPE_MAX_VALUE (type1), tmod);
@@ -719,7 +720,7 @@ number_of_iterations_lt_to_ne (tree type
       /* The final value of the iv is iv0->base - MOD, assuming that this
         computation does not overflow, and that
         iv0->base - MOD <= iv1->base. */
-      if (!iv0->no_overflow && !integer_zerop (mod))
+      if (!no_overflow && !integer_zerop (mod))
        {
          bound = fold_build2 (PLUS_EXPR, type1,
                               TYPE_MIN_VALUE (type1), tmod);


we make the testcase work.
Comment 9 Richard Biener 2008-08-04 18:30:29 UTC
Subject: Bug 36691

Author: rguenth
Date: Mon Aug  4 18:29:08 2008
New Revision: 138645

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=138645
Log:
2008-08-04  Richard Guenther  <rguenther@suse.de>

	PR middle-end/36691
	* tree-ssa-loop-niter.c (number_of_iterations_lt_to_ne): Correctly
	check for no_overflow.

	* gcc.c-torture/execute/pr36691.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.c-torture/execute/pr36691.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-loop-niter.c

Comment 10 Richard Biener 2008-08-04 18:32:21 UTC
Subject: Bug 36691

Author: rguenth
Date: Mon Aug  4 18:30:59 2008
New Revision: 138646

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=138646
Log:
2008-08-04  Richard Guenther  <rguenther@suse.de>

	PR middle-end/36691
	* tree-ssa-loop-niter.c (number_of_iterations_lt_to_ne): Correctly
	check for no_overflow.

	* gcc.c-torture/execute/pr36691.c: New testcase.

Added:
    branches/gcc-4_3-branch/gcc/testsuite/gcc.c-torture/execute/pr36691.c
Modified:
    branches/gcc-4_3-branch/gcc/ChangeLog
    branches/gcc-4_3-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_3-branch/gcc/tree-ssa-loop-niter.c

Comment 11 Richard Biener 2008-08-04 18:32:23 UTC
Fixed on the trunk and the 4.3 branch.
Comment 12 Joseph S. Myers 2009-03-31 15:43:02 UTC
Closing 4.2 branch, fixed for 4.3.2 and 4.4.