behavior when for-loop variable overflow and compiler optimization

Question

While reading http://blog.llvm.org/2011/05/what-every-c-programmer-should-know.html about undefined behavior in c, I get a question on this example.

for (i = 0; i <= N; ++i) { ... }

In this loop, the compiler can assume that the loop will iterate exactly N+1 times if "i" is undefined on overflow, which allows a broad range of loop optimizations to kick in. On the other hand, if the variable is defined to wrap around on overflow, then the compiler must assume that the loop is possibly infinite (which happens if N is INT_MAX) - which then disables these important loop optimizations. This particularly affects 64-bit platforms since so much code uses "int" as induction variables.

This example is to show the C compiler could take advantage of the undefined behavior to make assumption that the execution times would be exact N+1. But I don't understand why this assumption is valid.

I can understand that if the variable is defined to wrap around on overflow and N is INT_MAX, then the for loop will be infinite because i will go from 0 to INT_MAX and overflow to INT_MIN, then loop to INT_MAX and restart from INT_MIN etc. So the compiler could not make this assumption about execution times and can not do optimization on this point.

But what about when i is undefined on overflow? In this case, i loops normally from 0 to INT_MAX, then i will be assigned INT_MAX+1, which would overflow to an undefined value such as between 0 and INT_MAX. If so, the condition i<= INT_MAX is still valid, should the for-loop not continue and also be infinite?

Answer 1

… then i will be assigned INT_MAX+1, which would overflow to an undefined value such as between 0 and INT_MAX.

No, that is not correct. That is written as if the rule were:

• If ++i overflows, then i will be given some int value, although it is not specified which one.

However, the rule is:

• If ++i overflows, the entire behavior of the program is undefined by the C standard.

That is, if ++i overflows, the C standard allows any of these things to happen:

• i stays at INT_MAX.
• i changes to INT_MIN.
• i changes to zero.
• i changes to 37.
• The processor generates a trap, and the operating system terminates your process.
• Some other variable changes value.
• Program control jumps out of the loop, as if it had ended normally.
• Anything.

Now consider this assumption used in optimization by the compiler:

… the compiler can assume that the loop will iterate exactly N+1 times…

If ++i can only set i to some int value, then the loop will not terminate, as you conclude. On the other hand, if the compiler generates code that assumes the loop will iterate exactly N+1 times, then something else will happen in the case when ++i overflows. Exactly what happens depends on the contents of the loop and what the compiler does with them. But it does not matter what: Generating this code is allowed by the C standard because whatever happens when ++i overflows is allowed by the C standard.

Answer 2

Lets consider an actual case:

#include <limits.h>
#include <stdio.h>

unsigned long long test_int(unsigned long long L, int N) {
    for (int i = 0; i <= N; ++i) {
        L++;
    return L;
}

unsigned long long test_unsigned(unsigned long long L, unsigned N) {
    for (unsigned i = 0; i <= N; ++i) {
        L++;
    return L;
}

int main() {
    fprintf(stderr, "int: %llu\n", test_int(0, INT_MAX));
    fprintf(stderr, "unsigned: %llu\n", test_unsigned(0, UINT_MAX));
    return 0;
}

The point of the blog article is the of possible behavior of the compiler for the above code:

• for test_int() the compiler can determine that for argument values from INT_MIN to -1, the function should return L unchanged, for values between 0 and INT_MAX-1, the return value should be L + N + 1 and for INT_MAX the behavior is undefined, so returning L + N + 1 is OK too, hence the code can be simplified as

    unsigned long long test_int(unsigned long long L, int N) {
        if (N >= 0)
            L += N + 1;
        return L;
    }
  

• for test_unsigned(), the same analysis yields: for argument values below UINT_MAX, the return value is L + N + 1 and for UINT_MAX there is an infinite loop:

    unsigned long long test_unsigned(unsigned long long L, unsigned N) {
        if (N != UINT_MAX)
            return L + N + 1;
        for (;;);
    }
  

As can be seen on https://godbolt.org/z/abafdE8P4 both gcc and clang perform this optimisation for test_int, taking advantage of undefined behavior on overflow but generate iterative code for test_unsigned.