Does while(i--) s+= a[i]; contain undefined behavior in C and C++?

Question

Consider simple code:

#include "stdio.h"

#define N 10U

int main() {
    int a[N] = {0};
    unsigned int i = N;
    int s = 0;

    // Fill a

    while(i--)
        s += a[i];

    printf("Sum is %d\n", s);

    return 0;
}

Does while loop contain undefined behavior because of integer underflow? Do compilers have right to assume that while loop condition is always true because of that and end up with endless loop?

What if i is signed int? Doesn't it contain pitfalls related to array access?

Update

I run this and similar code many times and it worked fine. Moreover, it's popular way to iterate over arrays and vectors backwards. I'm asking this question to make sure that this way is OK from point of view of standard.

At glance, it's obviously not infinite. On other hand, sometimes compiler can "optimize" away some conditions and code assuming that code contains no undefined behavior. It can lead to infinite loops and other unwanted consequences. See this.

Answer 1

This code doesn't invoke undefined behavior. The loop will be terminated once i becomes 0.

For unsigned int, there is no integer over/underflow. The effect will be same with i as signed except there will no wrapping in this case.

Answer 2

Does while loop contain undefined behavior because of integer underflow?

No, overflow/underflow is only undefined behavior in case of signed integers.

Do compilers have right to assume that while loop condition is always true because of that and end up with endless loop?

No, because the expression will eventually turn out to be zero.

What if i is signed int? Doesn't it contain pitfalls related to array access?

If it is signed and over/underflows, you invoke undefined behavior.

Answer 3

The loop does not yield undefined behaviour for the following reasons.

i is initialised to 10, and decremented in the loop. When i has a value of zero, decrementing it produces a value equal to UINT_MAX - the largest value an unsigned can represent, but the loop will terminate. a[i] will only ever be accessed (within the loop) for values of i between N-1 (i.e. 9) and 0. Those are all valid indices in array a.

s and all the elements of a are initialized to zero. So all the additions add 0 to 0. That will never overflow nor underflow an int, so can never result in undefined behaviour.

If i is changed to signed int, the decrementing never underflows, and i will have a negative value when the loop terminates. The only net change is in the value that i has after the loop.

Answer 4

i will wrap around to ~0 (0XFFFFFFFF for 32 bits) but the loop will terminate so there is no UB.

Answer 5

Your code is well-behaved and contains no undefined behavior for any value of N ≥ 0.

Let us focus on the while-loop, and trace through an execution example with N = 2.

// Initialization
#define N 2U
unsigned int i = N;  // i = 2

// First iteration
while(i--)  // condition = i = 2 = true; i post-decremented to 1
    s += a[i];  // i = 1 is in bounds

// Second iteration
while(i--)  // condition = i = 1 = true; i post-decremented to 0
    s += a[i];  // i = 0 is in bounds

// Third iteration
while(i--)  // condition = i = 0 = false; i post-decremented to 0xFFFFFFFF
// Loop terminated

We can see from this trace that a[i] is always in bounds, and i experiences an unsigned wraparound when decrementing from 0, which is perfectly well-defined.

To answer your second question, if we changed the type of i to signed int, the only behavior that changes in the example trace is that the loop terminates at the same place but i gets decremented to -1, which is also perfectly well-defined.

Thus in conclusion, your code is well-behaved assuming that N ≥ 0, whether i is unsigned int or signed int. (If N is negative and i is signed int, then the loop will keep decrementing until undefined behavior happens at INT_MIN.)

Answer 6

Does while loop contain undefined behavior because of integer underflow?

First off this is a Boolean Conversion:

A prvalue of integral, floating-point, unscoped enumeration, pointer, and pointer-to-member types can be converted to a prvalue of type bool.

The value zero (for integral, floating-point, and unscoped enumeration) and the null pointer and the null pointer-to-member values become false. All other values become true.

So there will be no integer underflow if i is properly initialized, it will reach 0U and that will be cast to a false value.

So what the compiler is effectively doing here is: while(static_cast<bool>(i--))

Do compilers have right to assume that while loop condition is always true because of that and end up with endless loop?

The key reason this isn't an endless loop is that the postfix decrement operator returns the value of the decremented variable. It's defined as T operator--(T&, int) And as discussed in previously the compiler is going to evaluate whether that value is 0U as part of the conversion to bool.

What the compiler is effectively doing here is: while(0 != operator--(i, 1))

In your update you cite this code as a motivation for your question:

void fn(void)
{
    /* write something after this comment so that the program output is 10 */
    int a[1] = {0};
    int j = 0;
    while(a[j] != 5) ++j;  /* Search stack until you find 5 */
    a[j] = 10;             /* Overwrite it with 10 */
    /* write something before this comment */
}

Upon inspection, that entire program has undefined behavior there is only 1 element of a and it's initialized to 0. So for any index other than 0, a[j] is looking off the end of the array. The will continue till a 5 is found or until the OS errors because the program has read from protected memory. This is unlike your loops condition which will exit when the postfix decrement operator returns a value of 0, so there can't be an assumption that this is always true, or that the loop will go on infinitely.

What if i is signed int?

Both of the above conversions are built-in to C++. And they are both defined for all integral types, signed and unsigned. So ultimately this expands to:

while(static_cast<bool>(operator--(i, 1)))

Doesn't it contain pitfalls related to array access?

Again this is calling a built-in operator, the subscript operator: T& operator[](T*, std::ptrdiff_t)

So a[i] is the equivalent of calling operator(a, static_cast<ptrdiff_t>(i))

So the obvious followup question is what's a ptrdiff_t? It's a implementation defined integer, but as such each implementation of the standard is responsible for defining conversions to and from this type, so i will cast correctly.