Is this a compiler optimisation bug, or an undefined behaviour?

Question

We have an annoying bug I can't explain around this piece of code:

unsigned char bitmap[K_BITMAP_SIZE] = {0} ;
SetBit(bitmap, K_18); // Sets the bit #18 to 1

for(size_t i = 0; i < K_END; ++i)
{
    if(TestBit(bitmap, i)) // true for 18
    {
        size_t i2 = getData(i); // for 18, will return 15
        SetBit(bitmap, i2); // BUG: IS SUPPOSED TO set the bit #15 to 1
    }
}

1. It happens on Visual C++ 2010
2. It happens both on 32-bit and 64-bit builds
3. It happens only on Release builds (with "Maximize Speed (/O2)" set
4. It does not happen only on Release builds with "Minimize Size (/O1)" set
5. It happens on Visual C++ 2008 only if we __forceinline the getData function (by default, VC++2008 does not inline that function, while VC++2010 does)
6. It happens on the piece of code given below, probably because massive inlining inside the loop
7. It doesn't happen if we remove the loop, and directly set the interesting value (18)

Bonus info:

1- BenJ commented the issue does not appear on Visual C++ 2012, meaning this could well be a bug in the compiler

2- If we add a cast to unsigned char in the Test/Set/ResetBit functions, the bug disappears, too

size_t TestBit(const unsigned char * bits, size_t pos) { return (((bits)[(pos) >> 3]) &   (1 << (unsigned char)((pos) & 7))) ; }
size_t SetBit(unsigned char * bits, size_t pos)        { return (((bits)[(pos) >> 3]) |=  (1 << (unsigned char)((pos) & 7))) ; }
size_t ResetBit(unsigned char * bits, size_t pos)      { return (((bits)[(pos) >> 3]) &= ~(1 << (unsigned char)((pos) & 7))) ; }

The question is:

Does this bug happens because our code relies on undefined behaviour, or is there some bug in the VC++2010 compiler?

The following source is self-sufficient, and can be compiled as such on your favorite compiler:

#include <iostream>


const size_t K_UNKNOWN              = (-1) ;
const size_t K_START                = (0) ;
const size_t K_12                   = (K_START + 12) ;
const size_t K_13                   = (K_START + 13) ;
const size_t K_15                   = (K_START + 15) ;
const size_t K_18                   = (K_START + 18) ;
const size_t K_26                   = (K_START + 26) ;
const size_t K_27                   = (K_START + 27) ;
const size_t K_107                  = (K_START + 107) ;
const size_t K_128                  = (K_START + 128) ;
const size_t K_END                  = (K_START + 208) ;
const size_t K_BITMAP_SIZE          = ((K_END/8) + 1) ;


size_t TestBit(const unsigned char * bits, size_t pos) { return (((bits)[(pos) >> 3]) &   (1 << ((pos) & 7))) ; }
size_t SetBit(unsigned char * bits, size_t pos)        { return (((bits)[(pos) >> 3]) |=  (1 << ((pos) & 7))) ; }
size_t ResetBit(unsigned char * bits, size_t pos)      { return (((bits)[(pos) >> 3]) &= ~(1 << ((pos) & 7))) ; }


size_t getData(size_t p_value)
{
    size_t value = K_UNKNOWN;

    switch(p_value)
    {
        case K_13:      value = K_12;        break;
        case K_18:      value = K_15;        break;
        case K_107:     value = K_15;        break;
        case K_27:      value = K_26;        break;
        case K_128:     value = K_12;        break;
        default:        value = p_value;     break;
    }

    return value;
}


void testBug(const unsigned char * p_bitmap)
{
    const size_t byte = p_bitmap[1] ;
    const size_t bit  = 1 << 7 ;
    const size_t value = byte & bit ;

    if(value == 0)
    {
        std::cout << "ERROR : The bit 15 should NOT be 0" << std::endl ;
    }
    else
    {
        std::cout << "Ok : The bit 15 is 1" << std::endl ;
    }
}


int main(int argc, char * argv[])
{
    unsigned char bitmap[K_BITMAP_SIZE] = {0} ;
    SetBit(bitmap, K_18);

    for(size_t i = 0; i < K_END; ++i)
    {
        if(TestBit(bitmap, i))
        {
            size_t i2 = getData(i);
            SetBit(bitmap, i2);
        }
    }

    testBug(bitmap) ;

    return 0;
}

Some background info: Initially:

1. the Test/Set/ResetBit functions were macros.
2. the constants were defines
3. the indices were either long or int (on Windows 32-bit, they have the same size)

If needed, I'll add a few more info (e.g. the generated assembler for both configurations, update on how g++ handle the problem), as soon as possible.

Answer 1

This is a code optimizer bug. It inlines both getData() and SetBit(). The combination appears to be fatal, it loses track of the value of 1 << ((pos) & 7) and always produces zero.

This bug does not occur on VS2012. A workaround is to force one of the functions to not get inlined. Given the code, you probably want to do that for getData():

__declspec(noinline)
size_t getData(size_t p_value)
{ 
    // etc..
}

Answer 2

Addendum 2 The smallest possible part of the OP's code is given below. This snippet leads to the said optimizer bug in VS2010 - dependend on the contents of inline-expanded GetData(). Even if one combines the two returns in GetData() into one the bug is "gone". Also, it does not lead to a bug if you combine bits in only the first byte (like char bitmap[1]; - you need two bytes).

The problem does not occur under VS2012. This feels horrible because MS fixed that obviously in 2012 but not in 2010. WTF?

BTW:

• g++ 4.6.2 x64 (-O3) -- ok
• icpc 12.1.0 x64 (-O3) -- ok

VS2010 optimizer bug verification:

#include <iostream>
const size_t B_5=5, B_9=9;

size_t GetBit(unsigned char * b, size_t p) { return b[p>>3]  & (1 << (p & 7)); }
void   SetBit(unsigned char * b, size_t p) {        b[p>>3] |= (1 << (p & 7)); }

size_t GetData(size_t p) {
   if (p == B_5) return B_9;
   return 0;
}
/* SetBit-invocation will fail (write 0) 
   if inline-expanded in the vicinity of the GetData function, VS2010 */

 int main(int argc, char * argv[])
{
 unsigned char bitmap[2] = { 0, 0 };
 SetBit(bitmap, B_5);

 for(size_t i=0; i<2*8; ++i) {
    if( GetBit(bitmap, i) )         // no difference if temporary variable used,
        SetBit(bitmap, GetData(i)); // the optimizer will drop it anyway
 }

 const size_t byte=bitmap[1], bit=1<<1, value=byte & bit;
 std::cout << (value == 0 ? "ERROR: The bit 9 should NOT be 0" 
                          : "Ok: The bit 9 is 1") << std::endl;
 return 0;
}

---

After some inspection one can see that the initialization/zeroing part is not part of this specific problem.

Looked again after the meal. Seems to be a char/int propagation error. Can be cured by changing the mask functions (as has been already found out by the OP) to:

size_t TestBit  (const unsigned char * bits, size_t pos) { 
 return (bits)[pos >> 3] &   (1 << ( char(pos) & 7) ) ; 
}
size_t SetBit   (unsigned char * bits, size_t pos)       { 
 return (bits)[pos >> 3] |=  (1 << ( char(pos) & 7) ) ; 
}
size_t ResetBit (unsigned char * bits, size_t pos)       { 
 return (bits)[pos >> 3] &= ~(1 << ( char(pos) & 7) ) ; 
}

by casting the int-sized position pos to a char-size. This will lead the optimizer in VS2010 to do the right thing. Maybe somebody can comment.