C++ while loop optimization not working properly

Question

I have this code segment:

#include <stdio.h>

int main(int argc, const char** argv)
{
    int a = argv[0][0];
    int b = argv[0][1];

    while ((a >= 0) &&
           (a < b))
    {
        printf("a = %d\n", a);
        a++;
    }

    return 0;
}

and I'm compiling it with gcc-4.5 -02 -Wstrict-overflow=5.

The compiler yells at me warning: assuming signed overflow does not occur when changing X +- C1 cmp C2 to X cmp C1 +- C2

What does this mean exactly?

If i am correct, this loop will never cause an overflow, because for a to be incremented, it must be smaller than another integer. If it is bigger, the loop is terminated.

Can anyone explain this behavior to me?

Answer 1

The compiler is making an optimisation to convert a + 1 < b to a < b - 1. However, if b is INT_MIN then this will underflow, which is a change in behaviour. That's what it's warning about.

Of course, you can probably tell that this is impossible, but the compiler has limited resources to work things out and generally won't do in-depth analysis on data paths.

Adding a check that b >= 0 may solve the problem.

Edit: Another possibility is that it's moving a >= 0 to outside the loop, as (assuming no overflow) it can never change. Again, the assumption may not be valid for all inputs (i.e. if b is negative). You would need check the final assembly to see what it actually did.

Answer 2

The C++ standard says that if a signed integer calculation produces a result outside the representable range for the type then the behaviour is undefined. Integer overflow is UB. Once UB has happened, the implementation is free to do whatever it likes.

Many compilers apply optimisations on the explicit assumption that UB does not happen. [Or if it does, the code could be wrong but it's your problem!]

This compiler is notifying you that it is applying such an optimisation to a calculation where it is unable to determine from analysing the code that UB does not happen.

Your choices in general are:

1. Satisfy yourself that UB cannot happen, and ignore the warning.
2. Allow UB to happen and live with the consequences.
3. Rewrite the code so UB really cannot happen and the compiler knows it cannot happen, and the warning should go away.

I would recommend the last option. Simple range tests on a and b should be good enough.

---

My guess is that the compiler emits this error because the loop deals with completely unknown values, and it is unable to analyse the data flow well enough to work out whether UB can happen or not.

We with our superior reasoning power can convince ourselves that UB cannot happen, so we can ignore the error. In fact a careful reading of the error message might leave us asking whether it is relevant at all. Where are these two constant value C1 and C2?

We might also note that a can never go negative, so why is that test in the loop? I would probably rewrite the code to suppress the error, (but from experience that can be a self-defeating exercise). Try this and see what happens (and avoid unneeded parenthetic clutter):

if (a >= 0) {
  while (a < b) {
    ...
    ++a;
  }
}

Answer 3

What the compiler is warning you about is that it is assuming that signed overflow does not take place in the original code.

The warning does not mean "I'm about to write an optimization which potentially introduces overflows."

In other words, if your program depends on overflow (i.e. is not highly portable), then the optimization the compiler is doing may change its behavior. (So please verify for yourself that this code doesn't depend on overflow).

For instance, if you have "a + b > c", and you're depending on this test failing when a + b arithmetic wraps around (typical two's complement behavior), then if this happens to be algebraically transformed to "a > c - b", then it might succeed, because c - b may happen not to overflow, and produce a value smaller than a.

Notes: Only C programs can invoke undefined behavior. When compilers are incorrect, they are "nonconforming". A compiler can only be non-conforming (to the C standard) if it does the wrong thing with (C standard) conforming code. An optimization which alters correct, portable behavior is a nonconforming optimization.