Very strange Bug

[Gerd Isenberg]

@Michael: I would also propose to remove this line:

Code: Select all

#pragma warning (disable: 4146)

which points again to the "-(ui64_t) 1"

For this reason I also don't think the compiler is "buggy" here. With the warning C4146, given that you don't suppress it, it announces that something unexpected can happen.

Which data type is returned by bsr64()? In case of "unsigned char", this might be part of the problem, if the compiler truncates the left operand of the << operator in the "optimized" version due to the "unsigned char" type of the right operand.

Sven

Hi Sven,

I think the type determing the 32/64-bit shift should be the const ui64_t allBitsSet = 0xffffffffffffffffULL and not the type of the shift amount in a 0..63 range, see Visual Studio 2008 - Shift Operators: >> and <<:

The type of the result is the same as the type of the left operand. The value of a right-shift expression x >> y is x / 2y, and the value of a left-shift expression x << y is x * 2y. The result is undefined if the right operand of a shift expression is negative or if the right operand is greater than or equal to the number of bits in the (promoted) left operand.

With the source below, without a warning C4146 due to 0xffffffffffffffffULL instead of unary minus, but still producing the errornous byte-wise shift instructions for (attackLine.. & 32), implies a compiler bug.

Code: Select all

static __inline ui64_t attackLine(linemask_t *lmsk,ui64_t occ)
{
  const ui64_t allBitsSet = 0xffffffffffffffffULL;
  ui64_t lo = allBitsSet << bsr64&#40;&#40;lmsk->lineLo & occ&#41;|1&#41;; 
  ui64_t hi = lmsk->lineHi & occ;
  return&#40;lmsk->lineEx & &#40;2*&#40;hi&-hi&#41;-lo&#41;);
&#125; 

Code: Select all

   mov   edx, 255 
   mov   eax, edx
   shl   al, cl    ; shl rax, cl required since cl might be >= 32 < 64

See also Microsoft Visual Studio Express:

True integration of 64-bit compilers to the Visual C++ 2008 Express Edition is possible, but remains cumbersome ...

Gerd

[Gerd Isenberg]

ok, my solution.

Code: Select all

extern __inline ui64_t bitMask(sq_t sq) {return(bMask[sq]);}

Code: Select all

static __inline ui64_t attackLine(linemask_t *lmsk,ui64_t occ)
{
 ui64_t lo = bitMask(bsr64((lmsk->lineLo & occ)|1));
 ui64_t hi = lmsk->lineHi & occ;
 return(lmsk->lineEx & (2*(hi&-hi)-lo));
}

1: avoiding unintended shift operations
===============================

This is fine and may also reduce register pressure a bit, since x86 variable shifts are restricted to the byte register cl. Anyway, the VC2008 Express lost some credit ...

Gerd

[adamh]

Wow Gerd I am impressed I guess I did not pay enough attention to the fine print of the the your assembly findings...

Code: Select all

shl   al, cl 

Wow that is only an 8-bit operation no ?

Could it be that the optimizer makes false assumptions about the return value of bsr64(...)?

What assembly do you get if if you try:

Code: Select all

static __inline ui64_t get33(){ return 33 };

static __inline ui64_t attackLine(linemask_t *lmsk,ui64_t occ)
{
  const ui64_t allBitsSet = 0xffffffffffffffffULL;

  ui64_t lo = allBitsSet << get33&#40;); // this
  ui64_t lo = allBitsSet << 33; // or simpy this 

  ui64_t hi = lmsk->lineHi & occ;
  return&#40;lmsk->lineEx & &#40;2*&#40;hi&-hi&#41;-lo&#41;);
&#125;

I would try it myself but I only have 2010 and my 64-bit SDK is ****ed.
THX

[Gerd Isenberg]

Code: Select all

shl   al, cl 

Wow that is only an 8-bit operation no ?

Yes, the shift is a byte instruction, but you may clear the byte register either by shifting left 8, or even 31. But shifting left 32 does nothing, and leaves the initial 255, while 33 is like shifting left 1, which gives 254 or -2 as signed char.

Could it be that the optimizer makes false assumptions about the return value of bsr64(...)?

What assembly do you get if if you try:

Code: Select all

static __inline ui64_t get33(){ return 33 };

static __inline ui64_t attackLine(linemask_t *lmsk,ui64_t occ)
{
  const ui64_t allBitsSet = 0xffffffffffffffffULL;

  ui64_t lo = allBitsSet << get33&#40;); // this
  ui64_t lo = allBitsSet << 33; // or simpy this 

  ui64_t hi = lmsk->lineHi & occ;
  return&#40;lmsk->lineEx & &#40;2*&#40;hi&-hi&#41;-lo&#41;);
&#125;

I would try it myself but I only have 2010 and my 64-bit SDK is ****ed.
THX

As mentioned in the reply to Sven, the type of the shift amount should not care, but the type of the value to shift.

I don't own the VC2008 Express compiler. And the optimization bug seems only to occur, if the low byte of the attack is needed. Your sample stuff with allBitsSet << 33 is computed a compile time anyway and results in lo = 0xFFFFFFFE00000000ULL.

Otherwise the assembly would look like

Code: Select all

mov  rax, FFFFFFFFFFFFFFFFH
shl  rax, 33
...

If only the low byte is needed

Code: Select all

mov  eax, 255
shl  rax, 33 ; rax = 1FE00000000H, eax = ax = al = 0

would also work, leaving al clear. But not the "undefined"

Code: Select all

mov  eax, 255
shl  eax, 33  ; eax, ax = 510, al = 254

or the mentioned

Code: Select all

mov  eax, 255
shl  al, 33  ; eax = ax = al = 254

Gerd

[Desperado]

Wow Gerd I am impressed I guess I did not pay enough attention to the fine print of the the your assembly findings...

Code: Select all

shl   al, cl 

Wow that is only an 8-bit operation no ?

Could it be that the optimizer makes false assumptions about the return value of bsr64(...)?

What assembly do you get if if you try:

Code: Select all

static __inline ui64_t get33(){ return 33 };

static __inline ui64_t attackLine(linemask_t *lmsk,ui64_t occ)
{
  const ui64_t allBitsSet = 0xffffffffffffffffULL;

  ui64_t lo = allBitsSet << get33&#40;); // this
  ui64_t lo = allBitsSet << 33; // or simpy this 

  ui64_t hi = lmsk->lineHi & occ;
  return&#40;lmsk->lineEx & &#40;2*&#40;hi&-hi&#41;-lo&#41;);
&#125;

I would try it myself but I only have 2010 and my 64-bit SDK is ****ed.
THX

Hello Adam,

was reading your post a few minutes ago, and i thought i do you the favour.

The "standalone" assembly is using the rax register.
looks like the exceptions may only occur , if inlined (mixed with other code) and finally "optimized" by the compiler.

Code: Select all

const 33

	mov	r8, QWORD PTR [rcx+8]
	and	r8, rdx
	mov	rdx, -8589934592			; fffffffe00000000H
	mov	rax, r8
	neg	rax
	and	rax, r8
	lea	rax, QWORD PTR [rdx+rax*2]
	and	rax, QWORD PTR [rcx+16]
	ret	0

==============================================

the original with 0xffffffffffffffffULL

	mov	rax, QWORD PTR [rcx]
	mov	r8, rcx
	and	rax, rdx
	or	rax, 1
	bsr	rcx, rax
	mov	rax, QWORD PTR [r8+8]
	and	rax, rdx
	mov	rdx, rax
	neg	rdx
	and	rdx, rax
	or	rax, -1
	shl	rax, cl
	lea	rax, QWORD PTR [rax+rdx*2]
	and	rax, QWORD PTR [r8+16]
	ret	0

Oherwise i would be suprised that my perft collection always got the
right results.

Michael

[Desperado]

... if inlined (mixed with other code) and finally "optimized" by the compiler...

excactly like gerd explained above.

@Adam: By the way, when do we meet for some beer ?

cheers Michael

[adamh]

Well Michael...
you have won yourself 10 beers and (even if you won it by conspiring against me together with Bill [Gates] ) I will seriously not deny this fact. The next time you come to Stockholm you will not need to open your wallet for the first 10 cold ones. I am not sure about your location but if I go to Germany it will be Bremen (-ish).