[Bug tree-optimization/53501] New: incorrect loop optimization with -O2

[Bug tree-optimization/53501] New: incorrect loop optimization with -O2

[misof at gcc dot ksp.sk]

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

             Bug #: 53501
           Summary: incorrect loop optimization with -O2
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: misof@gcc.ksp.sk


Created attachment 27509
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=27509
preprocessed file for which the bug manifests

Sorry if this is a duplicate or if I miscategorized it (my first bug report
here, I did search for this and found nothing similar enough).

This bug appears both in gcc and g++, my best guess is that it has to do with
incorrect optimization of a loop. Bug present at amd64, gcc versions 4.6.3
(Ubuntu) and 4.7.0 (compiled), details follow:

$ gcc -v
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.6/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro
4.6.3-1ubuntu5' --with-bugurl=file:///usr/share/doc/gcc-4.6/README.Bugs
--enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr
--program-suffix=-4.6 --enable-shared --enable-linker-build-id
--with-system-zlib --libexecdir=/usr/lib --without-included-gettext
--enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.6
--libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu
--enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object
--enable-plugin --enable-objc-gc --disable-werror --with-arch-32=i686
--with-tune=generic --enable-checking=release --build=x86_64-linux-gnu
--host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5) 

$ ./gcc -v # my build of 4.7.0
Using built-in specs.
COLLECT_GCC=./gcc
COLLECT_LTO_WRAPPER=/home/misof/Desktop/newgcc/libexec/gcc/x86_64-unknown-linux-gnu/4.7.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with: ./configure --prefix=/home/misof/Desktop/newgcc/
--disable-multilib
Thread model: posix
gcc version 4.7.0 (GCC) 

Here is the offending source code:
$ cat bug.c
#include <stdio.h>

int e[100], n;

void foo(void) {
    int i, k = 0;
    for (i = 0; i < n; ++i) { e[k] = 10; ++k; e[k] = 10; ++k; }
    for (i = 0; i < k; ++i) printf("%d\n",e[i]);
    printf("k=%d\n",k);
}

int main(void) {
    n = 10;
    foo();
    return 0;
}

Up to my best knowledge this should be valid C code. When compiled without
optimizations or with -O1, everything works as expected:

$ gcc -Wall -Wextra bug.c && ./a.out
10
10
10
10
k=4

However, once -O2 or more is used, the second for-cycle seems to be incorrectly
optimized away:
$ gcc -Wall -Wextra -O2 bug.c && ./a.out
k=4

Interestingly, -fwrapv does make a difference, even though there seem to be no
integer overflows in the code:
$ gcc -Wall -Wextra -O2 -fwrapv bug.c && ./a.out 
10
10
10
10
k=4

Below is the complete stdout of
$ gcc -v -save-temps -Wall -Wextra -O2 bug.c 
Using built-in specs.
COLLECT_GCC=gcc
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.6/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro
4.6.3-1ubuntu5' --with-bugurl=file:///usr/share/doc/gcc-4.6/README.Bugs
--enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr
--program-suffix=-4.6 --enable-shared --enable-linker-build-id
--with-system-zlib --libexecdir=/usr/lib --without-included-gettext
--enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.6
--libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu
--enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object
--enable-plugin --enable-objc-gc --disable-werror --with-arch-32=i686
--with-tune=generic --enable-checking=release --build=x86_64-linux-gnu
--host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5) 
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-Wall' '-Wextra' '-O2' '-mtune=generic'
'-march=x86-64'
 /usr/lib/gcc/x86_64-linux-gnu/4.6/cc1 -E -quiet -v -imultilib . -imultiarch
x86_64-linux-gnu bug.c -mtune=generic -march=x86-64 -Wall -Wextra -O2
-fpch-preprocess -fstack-protector -o bug.i
ignoring nonexistent directory "/usr/local/include/x86_64-linux-gnu"
ignoring nonexistent directory
"/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../../x86_64-linux-gnu/include"
ignoring duplicate directory "/usr/include/x86_64-linux-gnu"
#include "..." search starts here:
#include <...> search starts here:
 /usr/include/x86_64-linux-gnu
 /usr/lib/gcc/x86_64-linux-gnu/4.6/include
 /usr/local/include
 /usr/lib/gcc/x86_64-linux-gnu/4.6/include-fixed
 /usr/include
End of search list.
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-Wall' '-Wextra' '-O2' '-mtune=generic'
'-march=x86-64'
 /usr/lib/gcc/x86_64-linux-gnu/4.6/cc1 -fpreprocessed bug.i -quiet -dumpbase
bug.c -mtune=generic -march=x86-64 -auxbase bug -O2 -Wall -Wextra -version
-fstack-protector -o bug.s
GNU C (Ubuntu/Linaro 4.6.3-1ubuntu5) version 4.6.3 (x86_64-linux-gnu)
        compiled by GNU C version 4.6.3, GMP version 5.0.2, MPFR version
3.1.0-p3, MPC version 0.9
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
GNU C (Ubuntu/Linaro 4.6.3-1ubuntu5) version 4.6.3 (x86_64-linux-gnu)
        compiled by GNU C version 4.6.3, GMP version 5.0.2, MPFR version
3.1.0-p3, MPC version 0.9
GGC heuristics: --param ggc-min-expand=100 --param ggc-min-heapsize=131072
Compiler executable checksum: 75e879ed14f91af504f4150eadeaa0e6
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-Wall' '-Wextra' '-O2' '-mtune=generic'
'-march=x86-64'
 as --64 -o bug.o bug.s
COMPILER_PATH=/usr/lib/gcc/x86_64-linux-gnu/4.6/:/usr/lib/gcc/x86_64-linux-gnu/4.6/:/usr/lib/gcc/x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/4.6/:/usr/lib/gcc/x86_64-linux-gnu/
LIBRARY_PATH=/usr/lib/gcc/x86_64-linux-gnu/4.6/:/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../../lib/:/lib/x86_64-linux-gnu/:/lib/../lib/:/usr/lib/x86_64-linux-gnu/:/usr/lib/../lib/:/usr/lib/x86_64-linux-gnu/:/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../:/lib/:/usr/lib/
COLLECT_GCC_OPTIONS='-v' '-save-temps' '-Wall' '-Wextra' '-O2' '-mtune=generic'
'-march=x86-64'
 /usr/lib/gcc/x86_64-linux-gnu/4.6/collect2 --sysroot=/ --build-id
--no-add-needed --as-needed --eh-frame-hdr -m elf_x86_64 --hash-style=gnu
-dynamic-linker /lib64/ld-linux-x86-64.so.2 -z relro
/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../x86_64-linux-gnu/crt1.o
/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../x86_64-linux-gnu/crti.o
/usr/lib/gcc/x86_64-linux-gnu/4.6/crtbegin.o
-L/usr/lib/gcc/x86_64-linux-gnu/4.6
-L/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../x86_64-linux-gnu
-L/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../../lib -L/lib/x86_64-linux-gnu
-L/lib/../lib -L/usr/lib/x86_64-linux-gnu -L/usr/lib/../lib
-L/usr/lib/x86_64-linux-gnu -L/usr/lib/gcc/x86_64-linux-gnu/4.6/../../.. bug.o
-lgcc --as-needed -lgcc_s --no-as-needed -lc -lgcc --as-needed -lgcc_s
--no-as-needed /usr/lib/gcc/x86_64-linux-gnu/4.6/crtend.o
/usr/lib/gcc/x86_64-linux-gnu/4.6/../../../x86_64-linux-gnu/crtn.o

Attached is the resulting bug.i file.

[Bug tree-optimization/53501] [4.5/4.6/4.7/4.8 Regression] scev introduces signed overflow

[amonakov at gcc dot gnu.org]

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

Alexander Monakov <amonakov at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2012-05-29
                 CC|                            |amonakov at gcc dot gnu.org
      Known to work|                            |4.3.2
            Summary|incorrect loop optimization |[4.5/4.6/4.7/4.8
                   |with -O2                    |Regression] scev introduces
                   |                            |signed overflow
     Ever Confirmed|0                           |1

--- Comment #1 from Alexander Monakov <amonakov at gcc dot gnu.org> 2012-05-29 16:00:01 UTC ---
Confirmed, thanks for the report.

This is a regression relative to 4.3 on all active branches (I haven't tested
latest trunk though).

GCC optimizes out the second loop when VRP proves that its upper bound k is
negative.  This is due to scev-cprop performing final value replacement, which
obtains the final value of k after the first loop based on scalar evolution {2,
+, 2} for n-1 latch executions as:

((int) ((unsigned int) n.0_28 + 2147483647) + 1) * 2

(which is a very roundabout way to get n*2, but that's beside the point ;) )
AFAICT forcing the signed type happens in chrec-apply:
          /* "{a, +, b} (x)"  ->  "a + b*x".  */
          x = chrec_convert_rhs (type, x, NULL);
          res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
          res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);

Apropos, I find it quite strange that fold-const folds (n+0xffffffff)*2 to
(n+0x7fffffff)*2, as opposed to n*2+0xfffffffe.

Stopping my investigation here.

[Bug tree-optimization/53501] [4.5/4.6/4.7/4.8 Regression] scev introduces signed overflow

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |wrong-code
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |
   Target Milestone|---                         |4.5.4

--- Comment #2 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-05-30 09:56:21 UTC ---
Confirmed, mine.

[Bug tree-optimization/53501] [4.5/4.6/4.7/4.8 Regression] scev introduces signed overflow

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-05-30 10:34:50 UTC ---
It's my very best friend extract_muldiv that transforms
(int)((unsigned int) n.0_26 + 4294967295) * 2
to (int)(((unsigned int) n.0_26 + 2147483647) * 2) 

It is the folding of (int) (((unsigned int) n.0_26 + 2147483647) * 2) + 2
which is wrong and done by fold_plusminus_mult_expr.  Patch:

Index: gcc/fold-const.c
===================================================================
--- gcc/fold-const.c    (revision 188004)
+++ gcc/fold-const.c    (working copy)
@@ -10045,12 +10045,12 @@ fold_binary_loc (location_t loc,
       /* Handle (A1 * C1) + (A2 * C2) with A1, A2 or C1, C2 being the
         same or one.  Make sure type is not saturating.
         fold_plusminus_mult_expr will re-associate.  */
-      if ((TREE_CODE (arg0) == MULT_EXPR
-          || TREE_CODE (arg1) == MULT_EXPR)
+      if ((TREE_CODE (op0) == MULT_EXPR
+          || TREE_CODE (op1) == MULT_EXPR)
          && !TYPE_SATURATING (type)
          && (!FLOAT_TYPE_P (type) || flag_associative_math))
         {
-         tree tem = fold_plusminus_mult_expr (loc, code, type, arg0, arg1);
+         tree tem = fold_plusminus_mult_expr (loc, code, type, op0, op1);
          if (tem)
            return tem;
        }

that will leave the expression unsimplified.

[Bug tree-optimization/53501] [4.5/4.6/4.7/4.8 Regression] scev introduces signed overflow

[rguenth at gcc dot gnu.org]

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

--- Comment #4 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-05-30 12:29:31 UTC ---
Author: rguenth
Date: Wed May 30 12:29:26 2012
New Revision: 188009

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=188009
Log:
2012-05-30  Richard Guenther  <rguenther@suse.de>

    PR middle-end/53501
    * fold-const.c (fold_binary_loc): Make sure to call
    fold_plusminus_mult_expr with the original sign of operands.

    * gcc.dg/torture/pr53501.c: New testcase.
    * c-c++-common/restrict-2.c: Adjust.

Added:
    trunk/gcc/testsuite/gcc.dg/torture/pr53501.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/fold-const.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/c-c++-common/restrict-2.c

[Bug tree-optimization/53501] [4.5/4.6 Regression] scev introduces signed overflow

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
      Known to work|                            |4.7.1, 4.8.0
            Summary|[4.5/4.6/4.7/4.8            |[4.5/4.6 Regression] scev
                   |Regression] scev introduces |introduces signed overflow
                   |signed overflow             |
      Known to fail|                            |4.7.0

--- Comment #6 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-05-30 12:34:22 UTC ---
Fixed on the trunk and the 4.7 branch for now.

[Bug tree-optimization/53501] [4.5/4.6/4.7/4.8 Regression] scev introduces signed overflow

[rguenth at gcc dot gnu.org]

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

--- Comment #5 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-05-30 12:32:17 UTC ---
Author: rguenth
Date: Wed May 30 12:32:10 2012
New Revision: 188010

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=188010
Log:
2012-05-30  Richard Guenther  <rguenther@suse.de>

    PR middle-end/53501
    * fold-const.c (fold_binary_loc): Make sure to call
    fold_plusminus_mult_expr with the original sign of operands.

    * gcc.dg/torture/pr53501.c: New testcase.
    * c-c++-common/restrict-2.c: Adjust.

Added:
    branches/gcc-4_7-branch/gcc/testsuite/gcc.dg/torture/pr53501.c
Modified:
    branches/gcc-4_7-branch/gcc/ChangeLog
    branches/gcc-4_7-branch/gcc/fold-const.c
    branches/gcc-4_7-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_7-branch/gcc/testsuite/c-c++-common/restrict-2.c

[Bug tree-optimization/53501] [4.5/4.6 Regression] scev introduces signed overflow

[ebotcazou at gcc dot gnu.org]

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

--- Comment #7 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2012-06-01 17:01:22 UTC ---
Author: ebotcazou
Date: Fri Jun  1 17:01:17 2012
New Revision: 188118

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=188118
Log:
    PR middle-end/53501
    * fold-const.c (fold_binary_loc): Refine previous change.
testsuite/
    * c-c++-common/restrict-2.c: Revert previous change.

Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/fold-const.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/c-c++-common/restrict-2.c

[Bug tree-optimization/53501] [4.5/4.6 Regression] scev introduces signed overflow

[ebotcazou at gcc dot gnu.org]

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

--- Comment #8 from Eric Botcazou <ebotcazou at gcc dot gnu.org> 2012-06-01 17:03:27 UTC ---
Author: ebotcazou
Date: Fri Jun  1 17:03:19 2012
New Revision: 188119

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=188119
Log:
    PR middle-end/53501
    * fold-const.c (fold_binary_loc): Refine previous change.
testsuite/
    * c-c++-common/restrict-2.c: Revert previous change.

Modified:
    branches/gcc-4_7-branch/gcc/ChangeLog
    branches/gcc-4_7-branch/gcc/fold-const.c
    branches/gcc-4_7-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_7-branch/gcc/testsuite/c-c++-common/restrict-2.c

[Bug tree-optimization/53501] [4.5/4.6 Regression] scev introduces signed overflow

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2

[Bug tree-optimization/53501] [4.5/4.6 Regression] scev introduces signed overflow

[rguenth at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.5.4                       |4.6.4

--- Comment #9 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-07-02 10:56:44 UTC ---
The 4.5 branch is being closed, adjusting target milestone.

[Bug tree-optimization/53501] [4.6 Regression] scev introduces signed overflow

[jakub at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|4.6.4                       |4.7.1

--- Comment #10 from Jakub Jelinek <jakub at gcc dot gnu.org> 2013-04-12 16:25:39 UTC ---
The 4.6 branch has been closed, fixed in GCC 4.7.1.