g++ -O produce wrong result

[wc skya]

I have a program that produces the wrong result when using -O to compile. My system is the latest fedora. "uname -a" output is

Linux pluto 4.15.14-300.fc27.x86_64 #1 SMP Thu Mar 29 16:13:44 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

"g++ -v" output is

Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-redhat-linux/7/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-redhat-linux
Configured with: ../configure --enable-bootstrap --enable-languages=c,c++,objc,obj-c++,fortran,ada,go,lto --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --with-bugurl=http://bugzilla.redhat.com/bugzilla --enable-shared --enable-threads=posix --enable-checking=release --enable-multilib --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-gnu-unique-object --enable-linker-build-id --with-gcc-major-version-only --with-linker-hash-style=gnu --enable-plugin --enable-initfini-array --with-isl --enable-libmpx --enable-offload-targets=nvptx-none --without-cuda-driver --enable-gnu-indirect-function --with-tune=generic --with-arch_32=i686 --build=x86_64-redhat-linux
Thread model: posix
gcc version 7.3.1 20180303 (Red Hat 7.3.1-5) (GCC)

The original program is big, but I have reduced the source code to the following:

#include <cstdio>
namespace {
  int p[48], v;
}
int main() {
  p[32] = 1;
  for (int i = 48; i--;) {
    if (p[i]) {
      printf("diff at %d\n", i);
      if (i > 39 || (i > 7 && (i & 7) > 2)) break;
      if (i < 8) {
        v = 1;
      } else if (!(i & 1)) {
        v = 2;
      } else {
        v = 3;
      }
    }
  }
  printf("v = %d\n", v);
}

p is static so is init to all 0, but p[32] is set to 1. Inside non-zero test where i is 32, the first and second if should test to false, but the else if should be true, so the v should be set to 2. The program runs correctly when compiled with "g++ -Wall test.cc", but when adding either -O, -O2, or -O3, then v is set to 3. Can anyone spot any error in the code? Or is there a gcc bug here?

[lastchance]

Err ...
for (int i = 48; i--; ) {
for ( initialiser; TEST; UPDATE )

Also, where were you expecting it to exit the for loop?

[zaphraud]

Under cygwin, I don't see the v being set to 3 regardless of what optimizer I use. I get the same result - the 2 - regardless...

Totally different version tho.
(edited: removed the output tags because it made the webpage a billion pixels wide)

$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-pc-cygwin/6.4.0/lto-wrapper.exe
Target: x86_64-pc-cygwin
Configured with: /cygdrive/i/szsz/tmpp/gcc/gcc-6.4.0-5.x86_64/src/gcc-6.4.0/configure --srcdir=/cygdrive/i/szsz/tmpp/gcc/gcc-6.4.0-5.x86_64/src/gcc-6.4.0 --prefix=/usr --exec-prefix=/usr --localstatedir=/var --sysconfdir=/etc --docdir=/usr/share/doc/gcc --htmldir=/usr/share/doc/gcc/html -C --build=x86_64-pc-cygwin --host=x86_64-pc-cygwin --target=x86_64-pc-cygwin --without-libiconv-prefix --without-libintl-prefix --libexecdir=/usr/lib --enable-shared --enable-shared-libgcc --enable-static --enable-version-specific-runtime-libs --enable-bootstrap --enable-__cxa_atexit --with-dwarf2 --with-tune=generic --enable-languages=ada,c,c++,fortran,lto,objc,obj-c++ --enable-graphite --enable-threads=posix --enable-libatomic --enable-libcilkrts --enable-libgomp --enable-libitm --enable-libquadmath --enable-libquadmath-support --disable-libssp --enable-libada --disable-symvers --with-gnu-ld --with-gnu-as --with-cloog-include=/usr/include/cloog-isl --without-libiconv-prefix --without-libintl-prefix --with-system-zlib --enable-linker-build-id --with-default-libstdcxx-abi=gcc4-compatible
Thread model: posix
gcc version 6.4.0 (GCC)

[wc skya]

I filed this bug against redhat, https://bugzilla.redhat.com/show_bug.cgi?id=1564841, and someone there forward it to gcc https://gcc.gnu.org/bugzilla/show_bug.cgi?id=85284.

[wc skya]

lastchance, the i--; in the for loop test for non-zero, and decrement i as update too. The loop ends when i is 0.

[lastchance]

I can't reproduce your result with gcc 6. I get the same as @zaphraud.

diff at 32
v = 2

EDIT - You're right! I tried it on
https://wandbox.org/
and it produces the wrong answer for gcc 7 and gcc 8 (but not gcc 6) if optimisation is turned on. It's OK if optimisation is turned off. A closer look produces some truly bizarre results for bitwise &.

[helios]

This is roughly what GCC 7.3 does according to Godbolt:

i = 47;
goto L2;
while (true){
    if (p[i]){
        printf("diff at %d\n", i);
        if (i <= 39){
            if (i <= 7){
                v = 1;
                goto L4;
            }else{
                if ((i & 7) <= 2){
                    if (i != 46)
                        v = 3;
                    else
                        v = 2;
                    goto L4;
                }
            }
        }
        break;
    }
L4:
    if (--i == -1)
        break;
}
printf("v = %d\n", v);
return;

Line 12 in particular is perplexing to me. It seems the static analyzer is being overly aggressive in proving the properties of i after the bitwise AND check and in wanting to eliminate the i < 8 check. Probably best to report this.

[wc skya]

I have already reported it to redhat, and they have reported to gcc. gcc has already fixed the trunk, and redhat is waiting for gcc to either release another version 7 to package, or wait till fedora 28 to upgrade to gcc 8. I have downloaded the latest released gcc 7.3.0, and applied the fix and compiled and installed this instead. The links that I included in my post on Apr 8th had the extra comma or period on the URL, and causing page not found. Delete the extra char to load the pages.

[zaphraud]

It's not as bad as the Intel CPU bug, but that's still very interesting. Good find!

[wc skya]

I think it's worse, since a correct source program compiled to produce the wrong result.

[helios]

I think it's inappropriate to compare them. They're two entirely different classes of bugs with practically nothing in common between them.

[zaphraud]

what's in common is the ability to hide seemingly innocent code that will later offer a concealed entry point to an operating system...

[helios]

If you're smart enough to figure out how to exploit an optimizer bug to write code that appears benign but actually compiles to produce a possible backdoor then you're better off contributing to GCC and Clang and putting the backdoors in the compiler itself.

http://wiki.c2.com/?TheKenThompsonHack

[Repeater]

My congratulations also. By design or by (bad?) luck, you've come across a GCC compiler bug that produces wrong output. If I were in charge, you'd get a little badge for that :)

[wc skya]

It's always by luck. If we could design it, we would have found all bugs by now.

My original code was looping from 0 to 47. Since I break out of the loop when i > 39 || i > 7 && (i & 7 > 2) when test for i fails, I thought looping backward would have break out sooner. So I reversed the loop, but got different result. It took me quite a while to discover that it's a -O bug.

[Repeater]

It's always by luck

ITHare seems to be finding them by design :)

http://ithare.com/c17-compiler-bug-hunt-very-first-results-12-bugs-reported-3-already-fixed/

He's set out to deliberately find bugs in compilers, and he's finding them.