C++ compilation bug?

Question

I have the following code:

#include <iostream>
#include <complex>
using namespace std;

int main() {
    complex<int> delta;
    complex<int> mc[4] = {0};

    for(int di = 0; di < 4; di++, delta = mc[di]) {
        cout << di << endl;
    }

    return 0;
}

I expect it to output "0, 1, 2, 3" and stop, but it outputs an endless series of "0, 1, 2, 3, 4, 5, ....."

It looks like the comparison di<4 doesn't work well and always returns true.

If I just comment out ,delta=mc[di], I get "0, 1, 2, 3" as normal. What's the problem with the innocent assignment?

I am using Ideone.com g++ C++14 with -O2 option.

Answer 1

This is due to undefined behavior, you are accessing the array mc out of bounds on the last iteration of your loop. Some compilers may perform aggressive loop optimization around the assumptions of no undefined behavior. The logic would be similar to the following:

• Accessing mc out of bounds is undefined behavior
• Assume no undefined behavior
• Therefore di < 4 is always true since otherwise mc[di] would invoke undefined behavior

gcc with optimization turned on and using the -fno-aggressive-loop-optimizations flag causes the infinite loop behavior to disappear(see it live). While a live example with optimization but without -fno-aggressive-loop-optimizations exhibits the infinite loop behavior you observe.

A godbolt live example of the code shows the di < 4 check is removed and replaced with and unconditional jmp:

jmp .L6

This is almost identical to the case outlined in GCC pre-4.8 Breaks Broken SPEC 2006 Benchmarks. The comments to this article are excellent and well worth the read. It notes that clang caught the case in the article using -fsanitize=undefined which I can not reproduce for this case but gcc using -fsanitize=undefined does (see it live). Probably the most infamous bug around an optimizer making an inference around undefined behavior is the Linux kernel null pointer check removal.

Although this is an aggressive optimizations, it is important to note that as the C++ standard says undefined behavior is:

behavior for which this International Standard imposes no requirements

Which essentially means anything is possible and it notes (emphasis mine):

[...]Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message).[...]

In order to get a warning from gcc we need to move the cout outside the loop and then we see the following warning (see it live):

warning: iteration 3u invokes undefined behavior [-Waggressive-loop-optimizations]
     for(di=0; di<4;di++,delta=mc[di]){ }
     ^

which would have likely been sufficient to provide the OP with enough information to figure out what was going on. Inconsistency like this are typical of the types of behavior we can see with undefined behavior. To get a better understanding of why such waring can be inconsitent in the face of undefined behavior Why can't you warn when optimizing based on undefined behavior? is a good read.

Note, -fno-aggressive-loop-optimizations is documented in the gcc 4.8 release notes.

Answer 2

Since you are incrementing di before you use it to index mc, the fourth time through the loop your will be referencing mc[4], which is past the end of your array, which could in turn lead to troublesome behavior.

Answer 3

You have this:

for(int di=0; di<4; di++, delta=mc[di]) {
  cout<<di<<endl;
}

Try this instead:

for(int di=0; di<4; delta=mc[di++]) {
   cout<<di<<endl;
}

EDIT:

To clarify what is going on Lets Break Down The Iteration Of Your For Loop:

1st iteration: Initially di is set to 0. Comparison check: Is di less than 4? Yes okay proceed. Increment di by 1. Now di = 1. Grab the "nth" element of mc[] and set it to be delta. This time we are grabbing the 2nd element since this indexed value is 1 and not 0. Finally perform the code block/s inside the for loop.

2nd iteration: Now di is set to 1. Comparison check: Is di less than 4? Yes and proceed. Increment di by 1. Now di = 2. Grab the "nth" element of mc[] and set it to be delta. This time we are grabbing the 3rd element since this indexed value is 2. Finally perform the code block/s inside the for loop.

3rd iteration: Now di is set to 2. Comparison check: Is di less than 4? Yes and proceed. Increment di by 1. Now di = 3. Grab the "nth" element of mc[] and set it to be delta. This time we are grabbing the 4th element since this indexed value is 3. Finally perform the code block/s inside the for loop.

4th iteration: Now di is set to 3. Comparison check: Is di less than 4? Yes and proceed. Increment di by 1. Now di = 4. (Can you see where this is going?) Grab the "nth" element of mc[] and set it to be delta. This time we are grabbing the 5th element since this indexed value is 4. Uh Oh we have a problem; our array size is only 4. Delta now has garbage and this is undefined behavior or corruption. Finally perform the code block/s inside the for loop using "garbage delta".

5th iteration. Now di is set to 4. Comparison check: Is di less than 4? No, break out of loop.

Corruption by exceeding bounds of contiguous memory (array).

Answer 4

It's because di++ is executed on the last run of the loop.

For example;

int di = 0;
for(; di < 4; di++);
// after the loop di == 4
// (inside the loop we see 0,1,2,3)
// (inside the for statement, after di++, we see 1,2,3,4)

You are accessing mc[] when di == 4, so it's an out of bounds problem, potentially destroying part of the stack and corrupting variable di.

a solution would be:

for(int di = 0; di < 4; di++) {
    cout << di << endl;
    delta = mc[di];
}