MikeMirzayanov's blog

Severe bug in g++ optimizator (-O2)
By MikeMirzayanov, 11 years ago, translation, In English

Hi!

I think everybody can remember a case when

Probably everyone remembers in practice a case when after implementation of correct algorithm you receive Wrong Answer. In such a situation, sometimes works: to send solution on another compiler.

Gerald and Nerevar have found severe bug, which gives one more argument to use the rule above.

Look closely, now it will be a miracle!   

#include <cstdlib>
#include <iostream>
#include <cstdio>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int x = 0; x <= n; x++) {
        if (n == x + (x + 1) + (x + 2)) {
            cout << x + 2 << " " << x + 1 << " " << x << endl;
            exit(0);
        }
    }
    cout << -1 << endl;
    return 0;
}

Compile it with -O2: g++ -O2 -o a a.cpp

Run and enter 9, you will see -1.

You can try without -O2 or using other compiler, you will get correct answer 4 3 2.

For sure, I've submitted the bug into gnu gcc tracker. Affected g++ versions are: from 4.7.2 to 4.8.2 (at least).

I have three points about it:

  1. We can select ACCEPTED solutions (on g++), rejudge them without -O2 and under valgrind to be sure that they are really OK. And we can do great regression test: after new release of g++ we can rejudge ~10000 such solutions to expect ACCEPTED. If not ACCEPTED, we can file a bug.

  2. Repeatedly Codeforces community have found bugs in g++. There is common opinion that Microsoft compiler is not so good as g++, but: do you remember such bugs in Microsoft C++?

  3. The described bug affects Codeforces. Be careful!

Tags bug, g++
  • Vote: I like it
  • +255
  • Vote: I do not like it

Comments Comments (41)
| Write comment?
»
11 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

It works correctly for me, both with and without -O2. My g++ is old, though.

$ g++ --version
g++ (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3
Copyright (C) 2011 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That's not really surprising if it's a regression in 4.8 or 4.9.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    both work for me too.
    and yeah i'm getting this same message when i check version.

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I remember there is a bug with ST::reverse() with -O2. I rarely use it.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why the result is right when x starts with -1 ? ...

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why the compile command is not "g++ -o a a.cpp -O2" ?

→ Reply
»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I am an active stackoverflow user and every now and then I see some code that demonstrates strange behavior in g++. I remember very clearly a case when compiling with optimizations caused abs(-1) to eval to -1. You can imagine what this could cause to some programs!

I regret so much I could not find that thread to link here.

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

I compile the code with -O2 -S and view the assembly code. I find that the code only simply checks whether n is equal to 3. If yes, the code outputs 2 1 0, else always outputs -1. The assembly code is here, https://gist.github.com/klogk/9994674. If changing the conditional statement into 3*x+3, the code will work fine. I guess that the reason is the wrong optimization for evaluation such bool statements.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    I wonder why it wasn't found before. x+x+x don't work too.

    PS idea about g++ testing by codeforces is awesome. CF is the big storage of compicated combintations of simple syntax-valid instuctions that runs in ~1sec and have testcases from 40-80 tests) I've read somewhere that compiler developers usually checking the results and consider compiler working after passing 95% of them. I think that it will be brilliant to run separate testing) If I were a student of SGU it would be interesting to understand such testing system (or try to contribute) and write several bugreports by simplifying participants solutions.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You may also use -fdump-tree-optimized, as I mentioned in one of the Russian comments. I prints code after optimization, but before translation to assembly.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Great! Yours is much more clear at a glance. New skill gotten!!

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Very useful for me！It's very clear!

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This situation often happens in POJ. G++ got WA,but C++ got ac finally know the reason.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    Well, at least I have known, when output a double variable, people always use "%lf", and it will get AC in C++ but WA in G++. However, if you use "%f" to output a double or float variable, both of them will return AC. But scanf is different, you should use "%lf" to input a double variable and use "%f" to input a float one in both of G++ and C++.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      This has nothing to do with GCC. The C/C++ standards say that %f, and not %lf, shall be used to print a double with printf().

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes, you're right. That's my point actually, but I didn't explain it clear enough:)

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it +6 Vote: I do not like it

          In C89, %lf with printf() is　undefined. But from C99, it is defined as equivalent to %f (more exactly, l on a following f is defined as has no effect). So, I wonder why you got both AC and WA.

          → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I used gdb to debug the program, and the program will always break the for loop if the first n == x + (x + 1) + (x + 2) is false. It seems that if I change the expression into n <= x + (x + 1) + (x + 2), it works fine. The optimizer must have confirmed once n != x + (x + 1) + (x + 2), it would never do. It is not because n will always be greater than the rhs. Instead the it might be resulted from number theory, and the derivation makes some mistakes.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The optimized code is here:

    int main() ()
{
  int n;
  int n.4;
 
  <bb 2>:
  scanf ("%d", &n);
  n.4_16 = n;
  if (n.4_16 >= 0)
    goto <bb 3>;
  else
    goto <bb 5>;
 
  <bb 3>:
  if (n.4_16 == 3)
    goto <bb 4>;
  else
    goto <bb 5>;
 
  <bb 4>:
  printf ("%d %d %d\n", 2, 1, 0);
  exit (0);
 
  <bb 5>:
  __builtin_puts (&"-1"[0]);
  n ={v} {CLOBBER};
  return 0;
 
}
    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Bug also found in shortened version, gcc 4.7.1

#include <stdio.h>
int main() {
    int n, x;
    scanf("%d", &n);
    for (x = 0; x <= n; x++)
        if (n == x + x + x + 3)
            return 0;
    puts("-1");
    return 0;
}

If changed into x * 3 + 3, it would be correct.

→ Reply
»
11 years ago, # |
  Vote: I like it +26 Vote: I do not like it

My gcc version is 4.8.2.

I can get the correct answer when I use g++ -O2 -fno-tree-ch, so I think -ftree-ch option enabled by -O may lead to some wrong optimization.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good job... compile code with -O2 fno-tree-ch seems to be safe for now.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

(maybe) Another bug found in the last year's ICPC Asia Nanjing Regional Contest. I coded a snippet like this, in order to test whether "-O2" in our compiler command line works correctly.

#include <stdio.h>

int main(void)
{
	int x = 0;
	int sum = 0;
	unsigned int i = 0;
	for(i = 0U;i < (1U<<31U);i++)
	{
		x++;
		sum += x;
	}
	printf("%d\n",sum);
	return 0;
}

To my surprise, this code runs for more than 10 seconds without anything outputed. Objdump shows the whole snippet was optimized as a "while(true);". But without -O2 this code works in about 5 seconds.

We tried all g++ versions we have at that time, 3.4.2(carried along with Dev-Cpp 4.9.9.2), 4.4.7, 4.6.3, 4.7.2, 4.8.1 and even 4.9pre. Among them only 3.4.2 works. But obviously we can't use this so-old one on judge workstations.

This fact forced us to double check many suspicious TLE solution during contest.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    And one bug only affects Codeforces. (Among all compiler I tested only GCC 4.7.2 MinGW was affected.)

    4054614 vs 4054535

    Minimized test: http://paste.ubuntu.com/7215859/

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 13   Vote: I like it +50 Vote: I do not like it

    C standart says two things:

    • signed overflow is Undefined Behaviour
    • in case of Undefined Behaviour compiler can do whatever he want with the code.

    Variable sum is signed and overflowed, and it can be predicted at compile time. So, compiler can do absolutely anything with it.

    Solutions are:

    • Using unsigned variable for sum
    • Using special compiler flag

    -fwrapv This option instructs the compiler to assume that signed arithmetic overflow of addition, subtraction and multiplication wraps around using twos-complement representation. This flag enables some optimizations and disables other.`

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks!

      But as sum and x is not related to the for-loop, I assumed "do anything" at least does not contain "convert the whole loop into a while(true);"

      Now I know I'm wrong :)

      Still wonder the logic behind this scene, How can compiler determine that this for-loop is infinite?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +40 Vote: I do not like it

        I agree that it is awful way to "do anything".

        Compilers use UB for optimisations with assumption, that programmer can't cause a UB.

        I see such a chain to get 'while(true)':

        • programmer can't cause UB, so the sum will not be overflowed
        • sum is not overflowed, so x is small enough
        • x is small, so i is small
        • i is small, so for-loop condition is always true
        • condition is always true, we dont need to check it
        • ???
        • fail
        → Reply
»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

The idea to use Codeforces submissions as regression tests is great and would help the open source community a lot! However it's always possible that programs exhibit undefined behaviour without valgrind noticing, so it's probably still a lot of work to manually extract the failing part of the program and verify whether there is indeed a regression or the code is just wrong

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, I am getting a similar kind of problem. My code in g++ in my computer is giving a right answer, however the output from the file compiled on codeforces' server is giving a different, hence wrong answer.

http://mirror.codeforces.com/contest/496/submission/9178052

care to have a look? Is there any solution to it?

Thanks.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it 
    .....
int count[len];
count[0] = -10;

for (int i = 1;i<len-1;i++)
{
	count[i] = arr[i+1] - arr[i-1];
}
bool found = 0;
sort(count,count+len);
for (int i = 1;i<len;i++)
{
	if (count[i]<=maxdif)
        ......

    Take a look at count[len — 1] value. It has unexpected garbage because you initiate an array count inside main. If count is global, it will be 0, for example. Any way, this is a bug for you, as far as I can understand your code.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As zurg pointed out, you are accessing an uninitialized piece of memory.

    Here's an advice: install valgrind and use it to check your memory usage. As an example, here is what valgrind said when running your code on test #4:

    > $ valgrind ./bugged_program                                                                                                                                                                        
[...output...]
3
1 500 1000
==29224== Conditional jump or move depends on uninitialised value(s)
[...output...]
==29224==    by 0x400C89: void std::sort<int*>(int*, int*) (stl_algo.h:4685)
==29224==    by 0x400B4B: main (bugged_program.cpp:44)
==29224== 
==29224== Conditional jump or move depends on uninitialised value(s)
[...output...]
==29224==    by 0x400C89: void std::sort<int*>(int*, int*) (stl_algo.h:4685)
==29224==    by 0x400B4B: main (bugged_program.cpp:44)
==29224== 
==29224== Conditional jump or move depends on uninitialised value(s)
==29224==    at 0x400B6C: main (bugged_program.cpp:48)
==29224== 
999
[...output...]

    You can see that valgrind has detected every access to uninitialized memory, and it gives you the exact line where it happened.

    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

This code is causing bug even without -O2 (tested on GCC 4.8.1):

#include <stdio.h>

// Returns 1 if a*b causes overflow, for a>=0 and b>=0; 0 otherwise
bool mul_overflow(long long a, long long b) {
	//printf("a=%lld\n", a);
	if (a < 0) return true;
	if (b <= 1) return false;
	return (a*b < 0) || mul_overflow(a+a, b/2);
}

int main() {
	printf("%d", mul_overflow(1LL<<33, 1LL<<30));
}
  1. Run it without -O2. The output is correct: 1
  2. Uncomment the printf and run it without -O2. The output is incorrect: despite it prints 1, it should print O(log b) values of a, and it prints just 1: "a=8589934592".
  3. Run it with -O2. The output is incorrect: 0
  4. Uncomment the print and run it with -O2. The output is correct: it prints 1, and all values of a until it gets to the answer.
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

    Isn't signed integer overflow an undefined behavior?

    http://stackoverflow.com/questions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c

    Shortly: if something like this happens, the compiler may do anything — generate a correct code (that is, doing exactly what you want), generate an incorrect code or... format all your drives (because why not).

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Signed integer overflow is undefined behavior. I guess the optimizer removes the (a*b < 0) condition because in a program with well-defined behavior it's always false (since at that point in program a>=0 and b>=0).

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      You are right! I was going to say gcc can't assume a >= 0 and b >= 0, but it actually can, because of the two previous if. I spent so much time trying to understand why gcc was treating this as UB and I didn't even notice that. How stupid >.<...

      It makes sense now.

      Thanks!

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry to post here after 3 months, but I found a very annoying bug somewhere in g++.

My AC code for problem 474E didn't work at home. You can find it easily, it's my last submission.

In fact:

  • it's AC here on Codeforces using g++
  • it's also AC here using Visual C++
  • it works at home with g++ 4.7.1 without options
  • it doesn't work at home with g++ 4.7.1 with options recommended by andreyv (http://mirror.codeforces.com/blog/entry/15547), namely -fdump-tree-optimized -fno-tree-ch -Wall -Wextra -pedantic -std=c++11 -O2 -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op -Wcast-qual -Wcast-align -fwhole-program -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC -lmcheck -D_FORTIFY_SOURCE=2 -fstack-protector

It does random crap at a time, some indexes go to some values like 2123421 rather than 2 without any reason...

I think that there is a problem with an optimization who guesses the value of a variable wrongly. It seemed to be deterministic (the crap variables were always the same) but totally unlogical.

I know that some of you here are g++ experts. Personally, I simply use these options because they're nice for debugging, but I don't know if they're unstable. In fact, I never really try to find out :D

I think the same problem can happen to some of you, because my code is a pretty classical segment tree code.

If you find what the fuck happened, please let me know. Thanks ! :-)

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Looks like you already did a lot of investigation. The obvious next steps are: 1. Get rid of all warnings. 2. If the problem remains, use binary search to find out the offending option.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      I found it !

      The problem is due to the combination of -O2 and -fwhole-program

      When I use them separately, it works, but with both of them I get the error.

      So, to create the problem, you simply need to use "-O2 -fwhole-program"

      That sounds logical, according to https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html :

      -fwhole-program : Assume that the current compilation unit represents the whole program being compiled. All public functions and variables with the exception of main and those merged by attribute externally_visible become static functions and in effect are optimized more aggressively by interprocedural optimizers.

      The mystery seems to be solved :D

      → Reply