[Bug c/36691] New: wrong value left in induction variable

[Bug c/36691] New: wrong value left in induction variable

[regehr at cs dot utah dot edu]

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;
}


-- 
           Summary: wrong value left in induction variable
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: regehr at cs dot utah dot edu
 GCC build triplet: i686-pc-linux-gnu
  GCC host triplet: i686-pc-linux-gnu
GCC target triplet: i686-pc-linux-gnu


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

[Bug middle-end/36691] [4.1/4.2/4.3/4.4 Regression] wrong value left in induction variable

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2008-07-02 09:36 -------
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.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org, spop at gcc dot gnu dot
                   |                            |org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
           Keywords|                            |wrong-code
      Known to fail|                            |4.1.1 4.3.1
      Known to work|                            |4.1.0
   Last reconfirmed|0000-00-00 00:00:00         |2008-07-02 09:36:54
               date|                            |
            Summary|wrong value left in         |[4.1/4.2/4.3/4.4 Regression]
                   |induction variable          |wrong value left in
                   |                            |induction variable
   Target Milestone|---                         |4.1.3


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

[Bug middle-end/36691] [4.2/4.3/4.4 Regression] wrong value left in induction variable

[jsm28 at gcc dot gnu dot org]

------- Comment #2 from jsm28 at gcc dot gnu dot org  2008-07-04 22:42 -------
Closing 4.1 branch.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.1/4.2/4.3/4.4 Regression]|[4.2/4.3/4.4 Regression]
                   |wrong value left in         |wrong value left in
                   |induction variable          |induction variable
   Target Milestone|4.1.3                       |4.2.5


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

[Bug middle-end/36691] [4.2/4.3/4.4 Regression] wrong value left in induction variable

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2008-07-10 14:29 -------
Sebastian, I think this is one for you ... ;)


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1


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

[Bug middle-end/36691] [4.2/4.3/4.4 Regression] wrong value left in induction variable

[spop at gcc dot gnu dot org]

------- Comment #4 from spop at gcc dot gnu dot org  2008-07-10 20:26 -------
Okay, I'll have a look at it.  Thanks for pointing me to it.


-- 

spop at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |spop at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2008-07-02 09:36:54         |2008-07-10 20:26:41
               date|                            |


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

[Bug middle-end/36691] [4.2/4.3/4.4 Regression] wrong value left in induction variable

[cnstar9988 at gmail dot com]

------- Comment #5 from cnstar9988 at gmail dot com  2008-08-04 12:42 -------
ping...


-- 


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

[Bug middle-end/36691] [4.2/4.3/4.4 Regression] wrong value left in induction variable

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2008-08-04 13:00 -------
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))


-- 


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

[Bug middle-end/36691] [4.2/4.3/4.4 Regression] wrong value left in induction variable

[cnstar9988 at gmail dot com]

------- Comment #7 from cnstar9988 at gmail dot com  2008-08-04 13:12 -------
confirmed gcc 4.2.4, -O3.

gcc test.c -O3


-- 


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

[Bug middle-end/36691] [4.2/4.3/4.4 Regression] wrong value left in induction variable

[rguenth at gcc dot gnu dot org]

------- Comment #8 from rguenth at gcc dot gnu dot org  2008-08-04 13:36 -------
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.


-- 

rguenth at gcc dot gnu dot org changed:

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


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

[Bug middle-end/36691] [4.2/4.3/4.4 Regression] wrong value left in induction variable

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2008-08-04 18:30 -------
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


-- 


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

[Bug middle-end/36691] [4.2 Regression] wrong value left in induction variable

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2008-08-04 18:32 -------
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 from rguenth at gcc dot gnu dot org  2008-08-04 18:32 -------
Fixed on the trunk and the 4.3 branch.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|rguenth at gcc dot gnu dot  |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW
      Known to work|4.1.0                       |4.1.0 4.3.2 4.4.0
            Summary|[4.2/4.3/4.4 Regression]    |[4.2 Regression] wrong value
                   |wrong value left in         |left in induction variable
                   |induction variable          |


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

[Bug middle-end/36691] [4.2/4.3/4.4 Regression] wrong value left in induction variable

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2008-08-04 18:32 -------
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


-- 


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

[Bug middle-end/36691] [4.2 Regression] wrong value left in induction variable

[jsm28 at gcc dot gnu dot org]

------- Comment #12 from jsm28 at gcc dot gnu dot org  2009-03-31 15:43 -------
Closing 4.2 branch, fixed for 4.3.2 and 4.4.


-- 

jsm28 at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
      Known to fail|4.1.1 4.3.1                 |4.1.1 4.3.1 4.2.5
         Resolution|                            |FIXED
   Target Milestone|4.2.5                       |4.3.2


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