Reordering test condition in for-loop: compiler bug?

Question

I've got a tree stored in an array, and i'm trying to find a particular node:

std::vector<Node> nodes = ...
const unsigned short sentinel = -1;
unsigned short index = 0;
for (Node* node = &nodes[index]; // root node
     index != sentinel;
     node = &nodes[index])
{
    if (foo(*node)) {
       index = node->left;
    } else {
       index = node->right;
    }
}

Nothing special, in other words. However, MSVC 2012 fails with an attempt to access nodes[sentinel] which is out of range. It turns out that it first calculates &nodes[index], then tests index. (Debug mode, no optimizations).

To me, this looks like a code generation bug, but I haven't seen such bugs in at least a decade. It's plain unoptimized code. Sure, even with the rearrangement, node isn't actually used before index is tested, and it's not terribly unsafe on x86 to have such an out-of-bounds pointer, but MSVC's vector<> rightfully asserts on that illegal index.

Did a clean build and checked the assembly again; it's repeatable. The tree isn't empty either, there's always a root node.

Am I overlooking something or is this really a serious compiler bug?

Answer 1

If you have a for-loop like this:

for (init; cond; step) { body; }

Then this is the order in which the expressions/statements are executed:

1. init
2. cond; stop on false, otherwise
3. body
4. step
5. cond; stop on false, otherwise
6. body
7. step
8. ...

In other words, it's a synonym for this:

{
  init;
  while (cond) {
    body;
    step;
  }
}

In your case, it can happen that body sets index to sentinel. You then expect cond to execute and break the loop, but notice that after every body execution, step executes before cond. This means that node = &nodes[index] will indeed be executed, with the new value of index, which is sentinel. So VS is producing what it should.

Your loop seems quite different from a traditional for loop; I think it would make more sense to turn it into an explicit while loop. If I were doing a code review of your code, I would definitely request that.

Answer 2

Your code rewritten to a while loop is like

Node* node = &nodes[index]; // root node
while(index != sentinel)
{
    {
        if (foo(*node)) {
           index = node->left;
        } else {
           index = node->right;
        }
    }

    node = &nodes[index];
}

The last line might be an access to nodes[-1].

I'ld rewrite your loop to

unsigned short index = 0;
do
{
    Node* node = &nodes[index];
    if (foo(*node)) {
       index = node->left;
    } else {
       index = node->right;
    }
} while(index != sentinel);

Answer 3

"select" Isn't Broken. ;-)

See how the loop is executed.

1. Initialise Node* node = &nodes[index]

2. Check index index != sentinel. Exit?

3. Loop body. This changes index!

4. node = &nodes[index]

5. Back to 2.

When after step 3 index == -1, you get your out of range access on step 4.