What optimizations are possible when loop variable is undefined on overflow?

This article features an example snippet of C code which the compiler can optimize thanks to the fact that overflow is undefined for the type of the loop counter.

Here's the snippet with the comment
> c
> 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.

I have quite a few doubts:

• I understand that, if the type of i is undefined on overflow, the compiler can assume that i will not wrap around, but why would this imply that the loop runs N+1 times? Can't it be that i is altered in the body of the loop?
• Even given that assumption, what optimization could it do based on that? If N is not known at compile-time, for instance, the loop can't be unrolled, can it?
• "Broad range of loop optimizations" makes me think I'm missing a lot, here.

> I understand that, if the type of i is undefined on overflow, the compiler can assume that i will not wrap around, but why would this imply that the loop runs N+1 times? Can't it be that i is altered in the body of the loop?

Answering the second question first, the author is taking it, for their example, that i is not altered in the loop and that the loop does not contain a break or other code that would terminate the loop. It is merely a briefly presented example aimed at a knowledgeable audience that is expected to be familiar with these things and to fill in the gaps.

Answering the first question, the fact that i will not wrap does not imply the loop will run N+1 times. The passage does not say that, it says it allows the compiler to assume that. The reasoning is this:

• If N is such that ++i never overflows, the loop runs exactly N+1 times.
• If N is such that ++i overflows at some point, the behavior is not defined, and the language standard allows any behavior. If the program crashes, that conforms to the standard. If N+1 wraps and the test i <= N is always true, and the loop iterates forever, that conforms to the standard. If the loop runs N+1 times, that conforms to the standard. As the compiler implementor, we can choose any of these behaviors, and the resulting behavior will conform to the language standard.

Given a free choice, in this instance we choose to behave as if the loop always runs N+1 times because this is a simplifying assumption: It gives us the same specification for both the non-overflow case and the overflow case.

> - Even given that assumption, what optimization could it do based on that? If N is not known at compile-time, for instance, the loop can't be unrolled, can it?

If the loop is for (int i = 0; i <= N; ++i) { sum += i; }, we can optimize to sum += N*(N+1)/2; (calulated with appropriate regard for possible overflow) and remove the loop entirely. If we were required to behave as if i wrapped upon overflow, we could not remove the loop entirely; we would need a test to see if the value of N were such that the loop exited or continued forever. (Other language in the standard about loops making progress notwithstanding; this is a simplified example.)

> - "Broad range of loop optimizations" makes me think I'm missing a lot, here.

It is a broad claim to make without listing several, so do not worry about that part too much.

> Can't it be that i is altered in the body of the loop?

No, they mean this:

size_t N = getSize();
for (int i = 0; i <= N; ++i) { 
   // i never changed here
}

Assuming a 64-bit platform, N might be too big for the loop to run correctly. (Perhaps the programmer knows that N is never too big, but the compiler doesn't). But if N is too big, i will overflow, and overflow "cannot" happen. So the compiler can assume that N is never too big after all -- even if it sometimes is.

By contrast,

for (unsigned i = 0; i <= N; ++i) {

here, even if N is the maximum representable unsigned, i won't overflow, but rather wrap around, which is completely legal. The compiler no longer can assume that N is never too big, and must deal with a loop that potentially doesn't end.

> what optimization could it do based on that?

Just watch this in awe.

If the compiler know the loop is going to end, it is able to use a (presumably) more efficient set of instructions. The machine code becomes much longer and much more complicated, but who cares if it wins us 3.27 picoseconds per run?

Here is a simple example of code that can be optimized under this assumption, and this version is even simpler because we're using < rather than <=:

int Foo(const std::vector<int> &vec) {
  int count = 0;
  for (int i = 0; i < vec.size(); i++) {
    count++;
  }
  return count;
}

Obviously the normal way to interpret this code would be to omit the loop entirely, and just rewrite it as:

int Foo(const std::vector<int> &vec) {
  return vec.size();
}

If vec.size() <= INT_MAX then everything is normal and there's nothing tricky to think about. But what if vec.size() > INT_MAX? Is the simplified/rewritten version still valid? This is actually important to consider because on most sane 64-bit implementations vec.size() will return a size_t which is a 64-bit unsigned integer.

In the huge-vector case there is a problem after INT_MAX iterations because if i underflows then the behavior is undefined, and this means that we could get things like an infinite loop, meaning our simplified rewritten version is not valid. However, since underflow is UB this means that the compiler can assume this won't happen, and it is permitted to make the simplification we made above.

In real world code this kind of optimization is important because it's extremely common for people to use things like an int loop iteration variable out of habit even though they're actually iterating over a container that can hold size_t elements.