Is this a compiler optimization error or an undefined behavior?

Question

We have an annoying error that I cannot 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 } } 

• This happens in Visual C ++ 2010.
• This happens on both 32-bit and 64-bit strings.
• This only happens in Release versions (with the setting "Maximize speed (/ O2)"
• This happens not only in Release versions with the parameter "Minimize Size (/ O1)"
• This happens in Visual C ++ 2008, only if we have the __forceinline function (by default, VC ++ 2008 did not build this function, but VC ++ 2010)
• This happens on the code snippet below, probably because the massive insert inside the loop
• This does not happen if we delete the cycle and directly set an interesting value (18)

Bonus Information:

1- BenJ commented that the problem does not appear in Visual C ++ 2012, i.e. this may be a compiler error

2- If we add cast to the unsigned char in the Test / Set / ResetBit function, the error will also disappear.

 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 arises:

Does this error happen because our code depends on undefined behavior, or is there some kind of error in the VC ++ 2010 compiler?

The following source is self-contained 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 information: Initially:

• The functions Test / Set / ResetBit were macros.
• constants determined
• indexes were either long or int (they are the same size on a 32-bit version of Windows)

If necessary, I will add some additional information as soon as possible (for example, the generated assembler for both configurations, update the information on how g ++ handles the problem).

Answer 1

This is a code optimizer error. It includes both getData () and SetBit (). The combination is fatal, it loses track of the value 1 <((pos) and 7) and always produces zero.

This error does not occur on VS2012. The workaround is to make one of the functions not enter it. Given the code, you probably want to do this for getData ():

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

Answer 2

Appendix 2 The following is the smallest possible part of the OP code. This snippet results in an optimizer error in VS2010 - it depends on the contents of the built-in extended GetData() . Even if you combine the two returns in GetData() into one, the error is "gone." In addition, this does not lead to an error if you combine bits only in the first byte (for example, char bitmap[1]; - you need two bytes).

The problem does not occur in VS2012. This seems terrible because MS recorded this, 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 error checking:

 #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 checking, you can see that the initialization / zeroing part is not part of this particular problem.

Looked again after eating. This seems to be a char / int error. It can be cured by changing mask functions (as OP discovered):

 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 placing a position of size t pos in size char. This will cause the optimizer in VS2010 to work properly. Maybe someone can comment.