Program behaving strangely on online IDEs

Question

I have come across the below C++ program (source):

#include <iostream>
int main()
{
    for (int i = 0; i < 300; i++)
        std::cout << i << " " << i * 12345678 << std::endl;
}

It looks like a simple program and gives the correct output on my local machine i.e. something like:

0 0
1 12345678
2 24691356
...
297 -628300930
298 -615955252
299 -603609574

But, on online IDEs like codechef, it gives the following output:

0 0
1 12345678
2 24691356
...
4167 -95167326
4168 -82821648
4169 -7047597

Why doesn't the for loop terminate at 300? Also this program always terminates on 4169. Why 4169 and not some other value?

Answer 1

I'm going to assume that the online compilers use GCC or compatible compiler. Of course, any other compiler is also allowed to do the same optimization, but GCC documentation explains well what it does:

-faggressive-loop-optimizations

This option tells the loop optimizer to use language constraints to derive bounds for the number of iterations of a loop. This assumes that loop code does not invoke undefined behavior by for example causing signed integer overflows or out-of-bound array accesses. The bounds for the number of iterations of a loop are used to guide loop unrolling and peeling and loop exit test optimizations. This option is enabled by default.

This option merely allows making assumptions based on cases where UB is proven. To take advantage of those assumptions, other optimizations may need to be enabled, such as constant folding.

---

Signed integer overflow has undefined behaviour. The optimizer was able to prove that any value of i greater than 173 would cause UB, and because it can assume that there is no UB, it can also assume that i is never greater than 173. It can then further prove that i < 300 is always true, and so the loop condition can be optimized away.

Why 4169 and not some other value?

Those sites probably limit the number of output lines (or characters or bytes) they show and happen to share the same limit.

Answer 2

"Undefined behaviour is undefined." (c)

A compiler used on codechef seems to use following logic:

1. Undefined behaviour can't happen.
2. i * 12345678 overflows and results in UB if i > 173 (assuming 32 bit ints).
3. Thus, i can never exceed 173.
4. Thus i < 300 is superfluous and can be replaced with true.

The loop itself appears to be infinite. Apparently, codechef just stops the program after a specific amount of time or truncates the output.

Answer 3

You are invoking undefined behavior probably on 174th iteration inside your for loop as the max int value probably is 2147483647 yet 174 * 123456789 expression evaluates to 2148147972 which is undefined behavior as there is no signed integer overflow. So you are observing effects of UB, particularly with the GCC compiler with optimization flags set in your case. It is likely the compiler would have warned you about this by issuing the following warning:

warning: iteration 174 invokes undefined behavior [-Waggressive-loop-optimizations]

Remove the (-O2) optimization flags to observe different results.