Why does GCC -O2 and -O3 optimization break this program?

Question

I've written this C code for finding the sum of all integers which are equal to the sum of the factorial of their digits. It takes a minute or so to get the job done without any GCC optimization flags, using -O1 decreased that time by about 15-20 seconds but when I tried it with -O2, -O3 or -Os it gets stuck in an infinite loop.

int main()
{
  int i, j, factorials[10];
  int Result=0;

  for(i=0; i<10; i++)
  {
    factorials[i]=1;
    for(j=i; j>0; j--)
    {
      factorials[i] *= j;
    }
  }

  for(i=3; i>2; i++) //This is the loop the program gets stuck on
  {
    int Sum=0, number=i;

    while(number)
    {
      Sum += factorials[number % 10];
      number /= 10;
    }

    if(Sum == i)
      Result += Sum;
  }

  printf("%d\n", Result);  
  return 0;
}

I've pinpointed that for(i=3; i>2; i++) is the cause of the problem. So obviously i is never less than 2?

Does this have anything to do with the fact that integer overflow behavior is undefined? If so, any more info on what exactly is going on with the program in these cases?

EDIT: I guess I should've mentioned, I am aware of other ways of writing that for loop so that it doesn't use overflowing(I was hoping that INT_MAX+1 would be equal to INT_MIN which is <2) but this was just done as a random test to see what would happen and I posted it here to find out what exactly was going on :)

Once you invoke undefined behavior all bets are off. It is instructive to try this with [godbolt example](http://goo.gl/dzr09I) using `-funsafe-loop-optimizations` and we can see gcc turns it into an infinite loop which does nothing. Also see [this](http://stackoverflow.com/q/24296571/1708801) and [this](http://stackoverflow.com/q/32506643/1708801) — Shafik Yaghmour, Sep 28 '15 at 13:52
It is not gcc which breaks your code, but your code is broken, which might just show up when optimized by gcc. — too honest for this site, Sep 28 '15 at 13:53
@ShafikYaghmour it'd also be quite entitled to remove the infinite loop entirely (infinite loops without a constant controlling expression nor observable behaviour, cause UB), I'm a bit surprised it kept the loop in — M.M, Sep 28 '15 at 13:53
@M.M indeed, since this an effect of optimization there may be a deeper reason why that choice is made. I am not sure though. — Shafik Yaghmour, Sep 28 '15 at 13:55
@ShafikYaghmour I guess it reduces the executable size because there is no need to emit shutdown code ! — M.M, Sep 28 '15 at 13:56
`i` becomes less than 2 when it reaches the maximum positive value, then it (with two complement notation) becomes the maximum absolute value a negative number can represent! — Sir Jo Black, Sep 28 '15 at 14:15
@ShafikYaghmour I've seen the godbolt example(also thanks for showing me the site, it will be used a lot from now on) and it made sense... But I just noticed that If i change the variable i from int to short int, it adds a command that compares the number to 2(and the program does halt). Any ideas as to why it doesn't do the same thing to int? — BojanV03, Sep 28 '15 at 14:55
@BojanV03: With short there is no overflow. `i++` is equivalent to `i = i + 1` and the right-hand side (`i+1`) is computed by promoting `i` to `int` then adding 1. The result is then stored into `i` by a conversion from `int` to `short`. When the value is not representable in `short`, the result of this conversion is *implementation-defined* (not undefined - that's the key point) and thus the program behavior is well-defined (for a given implementation). — R.. GitHub STOP HELPING ICE, Sep 28 '15 at 15:02

score 7 · Accepted Answer · answered Sep 28 '15 at 13:49

The loop is for (i = 3; i > 2; i++) and it has no break statements or other exit condition.

Eventually i will reach INT_MAX and then i++ will cause integer overflow which causes undefined behaviour.

Possibly Sum or Result would also overflow before i did.

When a program is guaranteed to trigger undefined behaviour , the entire behaviour of the program is undefined.

gcc is well known for aggressively optimizing out paths that trigger UB . You could inspect the assembly code to see what exactly happened in your case. Perhaps the -O2 and higher cases removed the loop end condition check , but -O1 left it in there and "relied" on INT_MAX + 1 resulting in INT_MIN.

If you modify my godbolt example above with optimization turned on gcc turns it into an unconditional jmp while w/o optimization it checks the variable. So you are indeed correct. — Shafik Yaghmour, Sep 28 '15 at 13:59

score 1 · Answer 2 · answered Sep 28 '15 at 14:16

The for loop is for(i=3; i>2; i++) and inside this loop i is not modified, nor is there a break or any other way to exit the loop. You are relying on integer overflow to cause the exit condition to occur, but the compiler doesn't take that into consideration.

Instead, the compiler sees that i starts at 3, and i is only ever incremented, and so i>2 is always true. Thus there is no need for i to exist at all in this context, since this must be an infinite loop.

If you change i to be unsigned int and set the condition for the loop exit to match, this "optimization" will no longer occur.

Sir Jo Black · Answer 3 · 2015-09-28T14:37:27.860

I find very strange the differences between the assembler results of the following code compiled without optimization and with -Os optimization.

#include <stdio.h>

int main(){
    int i;

    for(i=3;i>2;i++);

    printf("%d\n",i);

    return 0;
}

Without optimization the code results:

000000000040052d <main>:
  40052d:   55                      push   %rbp
  40052e:   48 89 e5                mov    %rsp,%rbp
  400531:   48 83 ec 10             sub    $0x10,%rsp
  400535:   c7 45 fc 03 00 00 00    movl   $0x3,-0x4(%rbp)
  40053c:   c7 45 fc 03 00 00 00    movl   $0x3,-0x4(%rbp)
  400543:   eb 04                   jmp    400549 <main+0x1c>
  400545:   83 45 fc 01             addl   $0x1,-0x4(%rbp)
  400549:   83 7d fc 02             cmpl   $0x2,-0x4(%rbp)
  40054d:   7f f6                   jg     400545 <main+0x18>
  40054f:   8b 45 fc                mov    -0x4(%rbp),%eax
  400552:   89 c6                   mov    %eax,%esi
  400554:   bf f4 05 40 00          mov    $0x4005f4,%edi
  400559:   b8 00 00 00 00          mov    $0x0,%eax
  40055e:   e8 ad fe ff ff          callq  400410 <printf@plt>
  400563:   b8 00 00 00 00          mov    $0x0,%eax
  400568:   c9                      leaveq 
  400569:   c3                      retq

and the output is: -2147483648 (as I expect on a PC)

With -Os the code results:

0000000000400400 <main>:
  400400:   eb fe                   jmp    400400 <main>

I think the second result is an error!!! I think the compiler should have compiled something corresponding to the code:

printf("%d\n",-2147483648);

The compiler doesn't need to compile the code corresponding to `printf()` because `int` doesn't have defined behavior once it overflows, so `i<2` will never happen and the `for` loop is functionally equivalent to `while(true)`. Since there is no `break` statement inside the loop, the `printf()` function doesn't have a code path leading to it and can be optimized out. — sig_seg_v, May 18 '16 at 19:36

score 0 · Answer 4 · answered Sep 28 '15 at 13:48

As you noticed yourself, signed integer overflow is undefined. The compiler decides to reason about your program assuming that you're smart enough to never cause undefined behavior. So it can conclude that since i is initialized to a number larger than 2 and only gets incremented, it will never be lower or equal to 2, which means that i > 2 can never be false. This in turn means that the loop will never terminate and can be optimized into an infinite loop.

score 0 · Answer 5 · 2015-09-28T13:55:38.610

As you said, it's undefined behavior, so you can't rely on any particular behavior.

The two things you will most likely see are:

The compiler translates more or less directly to machine code, which does whatever it wants to do when the overflow happens (which is usually to roll over to the most negative value) and still includes the test (which, e.g., will fail if the value rolls over)
The compiler observes that the index variable starts at 3 and always increases, and consequently the loop condition always holds, and so it emits an infinite loop that never bothers to test the loop condition

score 0 · Answer 6 · answered Sep 28 '15 at 13:49

I don't know what are you trying, but if you want to handle integer overflow, just include limits.h at your source code and write down this line inside your for loop.

if (i >= INT_MAX) break;

this will make you able to check your variable does not become greater than can it fit in integer.

Why does GCC -O2 and -O3 optimization break this program?

6 Answers6