Why does integer overflow on x86 with GCC cause an infinite loop?

Question

The following code goes into an infinite loop on GCC:

#include <iostream>
using namespace std;

int main(){
    int i = 0x10000000;

    int c = 0;
    do{
        c++;
        i += i;
        cout << i << endl;
    }while (i > 0);

    cout << c << endl;
    return 0;
}

So here's the deal: Signed integer overflow is technically undefined behavior. But GCC on x86 implements integer arithmetic using x86 integer instructions - which wrap on overflow.

Therefore, I would have expected it to wrap on overflow - despite the fact that it is undefined behavior. But that's clearly not the case. So what did I miss?

I compiled this using:

~/Desktop$ g++ main.cpp -O2

GCC Output:

~/Desktop$ ./a.out
536870912
1073741824
-2147483648
0
0
0

... (infinite loop)

With optimizations disabled, there is no infinite loop and the output is correct. Visual Studio also correctly compiles this and gives the following result:

Correct Output:

~/Desktop$ g++ main.cpp
~/Desktop$ ./a.out
536870912
1073741824
-2147483648
3

Here are some other variations:

i *= 2;   //  Also fails and goes into infinite loop.
i <<= 1;  //  This seems okay. It does not enter infinite loop.

Here's all the relevant version information:

~/Desktop$ g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/x86_64-linux-gnu/gcc/x86_64-linux-gnu/4.5.2/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ..

...

Thread model: posix
gcc version 4.5.2 (Ubuntu/Linaro 4.5.2-8ubuntu4) 
~/Desktop$ 

So the question is: Is this a bug in GCC? Or did I misunderstand something about how GCC handles integer arithmetic?

*I'm tagging this C as well, because I assume this bug will reproduce in C. (I haven't verified it yet.)

EDIT:

Here's the assembly of the loop: (if I recognized it properly)

.L5:
addl    %ebp, %ebp
movl    $_ZSt4cout, %edi
movl    %ebp, %esi
.cfi_offset 3, -40
call    _ZNSolsEi
movq    %rax, %rbx
movq    (%rax), %rax
movq    -24(%rax), %rax
movq    240(%rbx,%rax), %r13
testq   %r13, %r13
je  .L10
cmpb    $0, 56(%r13)
je  .L3
movzbl  67(%r13), %eax
.L4:
movsbl  %al, %esi
movq    %rbx, %rdi
addl    $1, %r12d
call    _ZNSo3putEc
movq    %rax, %rdi
call    _ZNSo5flushEv
cmpl    $3, %r12d
jne .L5

Solution 1

When the standard says it's undefined behavior, it means it. Anything can happen. "Anything" includes "usually integers wrap around, but on occasion weird stuff happens".

Yes, on x86 CPUs, integers usually wrap the way you expect. This is one of those exceptions. The compiler assumes you won't cause undefined behavior, and optimizes away the loop test. If you really want wraparound, pass -fwrapv to g++ or gcc when compiling; this gives you well-defined (twos-complement) overflow semantics, but can hurt performance.

Solution 2

It's simple: Undefined behaviour - especially with optimization (-O2) turned on - means anything can happen.

Your code behaves as (you) expected without the -O2 switch.

It's works quite fine with icl and tcc by the way, but you can't rely on stuff like that...

According to this, gcc optimization actually exploits signed integer overflow. This would mean that the "bug" is by design.

Solution 3

The important thing to note here is that C++ programs are written for the C++ abstract machine (which is usually emulated through hardware instructions). The fact that you are compiling for x86 is totally irrelevant to the fact that this has undefined behaviour.

The compiler is free to use the existence of undefined behaviour to improve its optimisations, (by removing a conditional from a loop, as in this example). There is no guaranteed, or even useful, mapping between C++ level constructs and x86 level machine code constructs apart from the requirement that the machine code will, when executed, produce the result demanded by the C++ abstract machine.

Solution 4

i += i;

// the overflow is undefined.

With -fwrapv it is correct. -fwrapv

Solution 5

Please people, undefined behaviour is exactly that, undefined. It means that anything could happen. In practice (as in this case), the compiler is free to assume it won't be called upon, and do whatever it pleases if that could make the code faster/smaller. What happens with code that should't run is anybody's guess. It will depend on the surrounding code (depending on that, the compiler could well generate different code), variables/constants used, compiler flags, ... Oh, and the compiler could get updated and write the same code differently, or you could get another compiler with a different view on code generation. Or just get a different machine, even another model in the same architecture line could very well have it's own undefined behaviour (look up undefined opcodes, some enterprising programmers found out that on some of those early machines sometimes did do useful stuff...). There is no "the compiler gives a definite behaviour on undefined behaviour". There are areas that are implementation-defined, and there you should be able to count on the compiler behaving consistently.

View more solutions

Comments

[Mysticial]

I guess i <<= 1 seems to be the more logical approach to this. Now that I take another look at the rest of the code, it looks like this loop is merely counting the # of leading zero bits in i to be used later on.

[bdonlan]

@Mysticial, or just use unsigned ints, where overflow behavior is perfectly well-defined always. Using <<= may happen to work now, but there is no guarentee that will be the case in future versions of gcc.

[Mysticial]

I was asking that question myself too. But I think it was written this way because it's (supposed) to work on any integer size assuming twos-complement. The trivial way to check if an integer has the highest bit set is to make it signed and compare against 0.

[R.. GitHub STOP HELPING ICE]

@Mysticial: i<<=1 will also invoke UB on overflow, but gcc might ignore this fact and treat it as well-defined anyway. Definitely some versions of gcc respect that it's UB though. Actually some broken autoconf tests in gnulib go into an infinite loop because of this issue on gcc 3.x...

[Mysticial]

@R..: So if I make i unsigned. Then change the test to (int)i < (int)0. Would that be defined? (assuming two-complement) I'm wondering if it's possible to do this without knowing the size of the integer type. (In the actual code, i is a typedefed type - sometimes to 32-bit integer, and sometimes to 64-bit integer. I obviously stripped it down naked before I asked it here.)

[R.. GitHub STOP HELPING ICE]

The conversion from unsigned to signed int is implementation-defined when the value is outside the range of int. There is absolutely no portable way to determine the width of signed int. This is because, given an implementation where INT_MAX is 0x7fffffff and INT_MIN is -0x7fffffff-1, redefining them to 0x3fffffff and -0x3fffffff-1 yields a new conformant implementation without any changes to the actual compiler.

[R.. GitHub STOP HELPING ICE]

(Actually I lied, but only very slightly. You also have to change the compiler so that struct { int foo:32; } generates a compiler error as required (since 32 is now greater than the width of int).)

[Mysticial]

@R..: The code requires that the typedef'ed integer types are powers-of-two in bit-length anyway. So the latter case you mentioned won't be a problem. So the only uncertainty left is the signed->unsigned cast which I'll hope will stay as a bit-wise reinterpret to twos-complement.

[Inverse]

It kinda sucks that a compiler would opt for an infinite loop of all things for undefined behavior.

[Dennis]

@Inverse: I disagree. If you're have coded something with undefined behavior, pray for an infinite loop. Makes it easier to detect...

[Inverse]

I mean if the compiler is actively looking for UB, why not insert an exception instead of trying to hyper-optimize broken code?

[Dennis]

@Inverse: The compiler isn't actively looking for undefined behavior, it assumes that it doesn't occur. This allows the compiler to optimize the code. For example, instead of computing for (j = i; j < i + 10; ++j) ++k;, it will just set k = 10, since this will always be true if no signed overflow occurs.

[Jeff Burdges]

Is there a warning option that attempts to notice accidental infinite loops?

[bdonlan]

@JeffBurdges, not sure, try opening another question about this?

[Jeff Burdges]

I found -Wunsafe-loop-optimizations mentioned here : stackoverflow.com/questions/2982507/…

[Cheers and hth. - Alf]

since g++ has numeric_limits<int>::is_modulo true, at least in Windows, either its optimization assumption of non-wrapping is incorrect, or its numeric_limits is incorrect (also in this)

[Cheers and hth. - Alf]

-1 "Yes, on x86 CPUs, integers usually wrap the way you expect." that's wrong. but it's subtle. as i recall it's possible to make them trap on overflow, but that's not what we're talking about here, and i've never seen it done. other than that, and disregarding x86 bcd operations (not permitted representation in C++) x86 integer ops always wrap, because they're two's complement. you're mistaking g++ faulty (or extremely impractical and nonsense) optimization for a property of x86 integer ops.

[bdonlan]

@Cheersandhth.-Alf, by 'on x86 CPUs' I mean 'when you're developing for x86 CPUs using a C compiler'. Do I really need to spell it out? Obviously all my talk about compilers and GCC is irrelevant if you're developing in assembler, in which case the semantics for integer overflow are very well-defined indeed.

[Mysticial]

Yes, I know very well what undefined behavior is. But when you know how certain aspects of the language is implemented for a particular environment, you can expect to see certain types of UB and not others. I know that GCC implements integer arithmetic as x86 integer arithmetic - which wraps on overflow. So I assumed the behavior as such. What I didn't expect was GCC to do something else as bdonlan has answered.

[vonbrand]

Wrong. What happens is that GCC is allowed to assume you won't invoke undefined behaviour, so it just emits code as if it couldn't happen. If it does happen, the instructions to do what you ask for with no undefined behaviour get executed, and the result is whatever the CPU does. I.e., on x86 is does x86 stuff. If it is another processor, it could do something totally different. Or the compiler could be smart enough to figure out that you are calling on undefined behaviour and start nethack (yes, some ancient versions of gcc did exactly that).

[Mysticial]

I believe you misread my comment. I said: "What I didn't expect" - which is why I asked the question in the first place. I didn't expect GCC to pull any tricks.

[Lightness Races in Orbit]

@Inverse The compiler didn't "opt" for anything. You wrote the loop in your code. The compiler didn't invent it.

[supercat]

@Inverse: What's shown here mild by comparison with hyper-modern compilers. Behaviors like what's shown here could occur "naturally" on platforms where integer types may get processed using registers that are larger than the variable size (e.g. on x64 platforms with 32-bit int). By contrast, hyper-modern compilers will sometimes assume code reaches a point where something would have to occur to avoid UB, that something will occur, even if there would be no other basis for that assumption.

[supercat]

@Cheersandhth.-Alf: There can be considerable optimization advantages to allowing compilers to behave as though signed integers are sometimes promoted to larger types--even in cases where there would seemingly be no room for all the bits. Note, however, that integer overflow on gcc can have side-effects which affect other aspects of execution, even in case where the actual result of the overflowed computation would ultimately get ignored anyway.

[Cheers and hth. - Alf]

@supercat: There's not room enough to discuss "can be considerable optimization advantages" here. There are some blog postings that try to go into the issue. Usually they're written to make just that point, but I've always found that the assertions and conclusions generally don't hold, that it's a fan-boy blindness thing, mostly. The impression I'm left with it is that here are some (a few) slight optimization opportunities. But that these opportunities, while enabled by a general assumption of UB on signed overflow, do not actually REQUIRE that as a general assumption.

[supercat]

@Cheersandhth.-Alf: I agree with your last statement 100%, but would regard the code at issue as being an example. If a compiler were to store i using a 128-bit integer type, there would be no overflows but the program would exhibit the behavior being complained about. Given that code outputs the value of "i" within the loop I would regard the optimizations as rather high on an aggressiveness scale (since the value output would reflect that i had wrapped but the comparison would say it hadn't), but that's not nearly as bad as having overflows affect other aspects of program behavior...

[supercat]

...even in cases where the results of the overflowed computations end up being totally ignored.