Compiler optimization causing program to run slower

Question

I have the following piece of code that I wrote in C. Its fairly simple as it just right bit-shifts x for every loop of for.

int main() {
   int x = 1;
   for (int i = 0; i > -2; i++) {
      x >> 2;
   }
}

Now the strange thing that is happening is that when I just compile it without any optimizations or with first level optimization (-O), it runs just fine (I am timing the executable and its about 1.4s with -O and 5.4s without any optimizations.

Now when I add -O2 or -O3 switch for compilation and time the resulting executable, it doesn't stop (I have tested for up to 60s).

Any ideas on what might be causing this?

How is your loop supposed to stop when `i` will always be greater than -2 — GWW, Aug 19 '11 at 15:46
`i` is an int so -2 is actually `INT_MAX -1` and notice the `i > -2` instead of `i < -2`. — mmtauqir, Aug 19 '11 at 15:47
Oh I see what you are doing then. I just wasn't sure if that was intentional — GWW, Aug 19 '11 at 15:47
Overflow is technically Undefined Behaviour, so anything may happen (regardless of optimizations setting). — pmg, Aug 19 '11 at 15:47
Yeah instead of typing the maximum value of `int - 1`, I just did this :p — mmtauqir, Aug 19 '11 at 15:48
@pmg Yeah I know what you mean, but this should technically work...its C after all and this is the kind of stuff you do in C :D — mmtauqir, Aug 19 '11 at 15:49
Actually pmg is right. And no, Undefined Behavior is not the thing you do in C. And "technically" *it shouldn't work* — cnicutar, Aug 19 '11 at 15:51
@mtahmed: as you noticed, the result can be different for different optimization settings. It can also be different for different compilers on different architectures, or for different moon phases ... :) — pmg, Aug 19 '11 at 15:51
@mtahmed, does the same thing happen if you change the `for` condition so you don't have that UD? — Eran, Aug 19 '11 at 15:53
I think that the agressive levels of optimizations are changing the loop in some whay (maybe by a while( true )). You should try to include the "volatile" modifier for "i" and "x" and see what happens. Also, the condition in the loop is a problem - you're relying on an overflow, and that's undefined behaviour, as @pmg pointed out. — Baltasarq, Aug 19 '11 at 15:53
@eran No I just tested with `(int i = 0; i < INT_MAX - 1; i++)` and its fine with that. So yeah compiler is making it an infinite loop. — mmtauqir, Aug 19 '11 at 15:59
What exactly is `x >> 2;` supposed to achieve? You throw away the result, and it has no effect. — fredoverflow, Jan 26 '12 at 22:33
Compiler was plain stupid here... I would have simply thrown the loop out and issued a warning that the entire loop had no effect. — Calmarius, Apr 03 '13 at 15:23
Relevant: https://www.usenix.org/conference/atc14/technical-sessions/presentation/towards-optimization-safe-systems-analyzing-impact — user, Jan 27 '15 at 00:24

Joe · Accepted Answer · 2011-08-19T16:59:15.807

18

The optimized loop is producing an infinite loop which is a result of you depending on signed integer overflow. Signed integer overflow is undefined behavior in C and should not be depended on. Not only can it confuse developers it may also be optimized out by the compiler.

Assembly (no optimizations): gcc -std=c99 -S -O0 main.c

_main:
LFB2:
    pushq   %rbp
LCFI0:
    movq    %rsp, %rbp
LCFI1:
    movl    $1, -4(%rbp)
    movl    $0, -8(%rbp)
    jmp L2
L3:
    incl    -8(%rbp)
L2:
    cmpl    $-2, -8(%rbp)
    jg  L3
    movl    $0, %eax
    leave
    ret

Assembly (optimized level 3): gcc -std=c99 -S -O3 main.c

_main:
LFB2:
    pushq   %rbp
LCFI0:
    movq    %rsp, %rbp
LCFI1:
L2:
    jmp L2  #<- infinite loop

edited Aug 19 '11 at 16:59

answered Aug 19 '11 at 15:55

Joe

56,979
9
128
135

Out of curiosity, is the behavior of integer overflow undefined in C? – tskuzzy Aug 19 '11 at 16:22
3

@tskuzzy, *signed* integer overflow is UB. `unsigned` integers behave well and just wrap around. So OP's loop would work quite well when transposed to an `unsigned` setting. – Jens Gustedt Aug 19 '11 at 16:48

score 7 · Answer 2 · answered Aug 19 '11 at 15:54

You will get the definitive answer by looking at the binary that's produced (using objdump or something).

But as others have noted, this is probably because you're relying on undefined behaviour. One possible explanation is that the compiler is free to assume that i will never be less than -2, and so will eliminate the conditional entirely, and convert this into an infinite loop.

Also, your code has no observable side effects, so the compiler is also free to optimise the entire program away to nothing, if it likes.

score 2 · Answer 3 · answered Aug 19 '11 at 16:07

2

Additional information about why integer overflows are undefined can be found here:

http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html

Search for the paragraph "Signed integer overflow".

answered Aug 19 '11 at 16:07

Tobias Schlegel

3,970
18
22

There are also two more blogposts: http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html and http://blog.llvm.org/2011/05/what-every-c-programmer-should-know_21.html – Tobias Schlegel Aug 19 '11 at 18:45
I really can't say enough how good those articles are. Among other things, the articles really made clear and concrete exactly why certain mysterious optimizations might remove code that appears to be necessary. The reasons for and consequences of UB are not very well understood in the C community, and those articles are about the best reading on the subject I can recall. Thanks again! – Michael Burr Aug 21 '11 at 21:26

Compiler optimization causing program to run slower

3 Answers3

Linked