1

The following snippet of C++ code computes Fibonacci numbers. With 32-bit integers, we overflow when n=47 and b becomes negative.

int a=0, b=1, n=2;
do {
   a += b; int c = a; a = b; b = c;
   ++n;
} while ( b>0 and n<50 );
std::cout << "Ended at n=" << n << " b=" << b << std::endl;

Compiling on g++ 4.9.1 all is well; unless I use -O2 or -O3 in which case the loop runs until n=50. Is the compiler perhaps assuming that, as a and b start out positive and only additions are applied, they must stay positive? A look at the assembly output confirms that the condition b>0 isn't even being checked.

Same happens for g++ 4.7.0. So I suspect this is deliberate behaviour...?

Matthew Daws
  • 1,837
  • 1
  • 17
  • 26
  • 2
    It's expected because it's UB according to the standard, use `-fwrapv` if you want to define it. Trying to look up duplicates, but can't find a canonical answer ... – o11c Oct 17 '14 at 20:25
  • Great, many thanks. There is some discussion e.g. http://thiemonagel.de/2010/01/signed-integer-overflow/ – Matthew Daws Oct 17 '14 at 20:31
  • 1
    highest-upvoted potential dup: http://stackoverflow.com/questions/18195715/why-is-unsigned-integer-overflow-defined-behavior-but-signed-integer-overflow-is – o11c Oct 17 '14 at 20:51

1 Answers1

1

First of all: This code invokes undefined behavior according to [expr]/4. Therefore a compiler can deduce that since no negative value can be assigned to b without UB (which case the compiler doesn't consider any further), b can't get negative and thus that condition doesn't need to be checked.

As noted in the comments, the flag -fwrapv 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 others.

With it GCC should produce the same program as with optimization levels lower than O2.

Columbo
  • 60,038
  • 8
  • 155
  • 203