Computer Chess Club Archives


Search

Terms

Messages

Subject: It does have POPCNT

Author: Simon Finn

Date: 07:59:09 08/17/00

Go up one level in this thread


On August 16, 2000 at 13:11:04, Eugene Nalimov wrote:

>On August 15, 2000 at 23:27:46, Larry Griffiths wrote:
>
>>I looked through some literature for the Intel Itanium processor and did not see
>>any Bit Scan Forward or Bit Scan reverse instructions.  Does anyone know for
>>sure if the Itanium has these instructions or something like them.
>>My bitboard move generation would really suck without BSF or BSR.
>>
>>Larry.
>
>No. There are no such instructions. You have to use ifs, shifts, and lookup
>table. Here is the example -- FirstOne()/LastOne() that I wrote for IA-64
>version of Crafty (it is not in the official build yet):

The IA-64 architecture does have POPCNT, so it may be more efficient
to implement one of these (I can't work out which one without thinking
too hard!) by the standard trick of computing

    BITBOARD x = arg1 & (arg1 - 1);

then counting the 1 bits in x (using POPCNT)and adding/subtracting
whatever adjustment is necessary (requires thought again!).

All that should take only 4 sequential instructions.

Simon


>
>int FirstOne(BITBOARD arg1) {
>    unsigned  bias;
>
>    bias = 0;
>    if (arg1>>32)
>      arg1 >>= 32;
>    else
>      bias += 32;
>    if (arg1>>16)
>      arg1 >>= 16;
>    else
>      bias += 16;
>    if (arg1 >> 8)
>      arg1 >>= 8;
>    else
>      bias += 8;
>    return (first_ones_8bit[arg1]+bias);
>}
>
>int LastOne(BITBOARD arg1) {
>    unsigned  bias;
>
>    bias = 0;
>    if ((unsigned) arg1) {
>      arg1 = (unsigned) arg1;
>      bias = 32;
>    }
>    else
>      arg1 >>= 32;
>    if (arg1&65535) {
>      arg1 &= 65535;
>      bias += 16;
>    }
>    else
>      arg1 >>= 16;
>    if (arg1&255) {
>        arg1 &= 255;
>        bias += 8;
>    }
>    else
>        arg1 >>= 8;
>    return (last_ones_8bit[arg1]+bias);
>}
>
>Here is output of 64-bit MSVC for those functions:
>
>// Begin code for function: FirstOne:
>	.proc	FirstOne#
>	.align 32
>FirstOne: 						// COMDAT
> {   .mii  //R-Addr: 0X00
>	mov	r29=r0					    //19.	cc:0
>	shr.u	r30=r32, 32				    //20.	cc:0
>	addl	r31=@ltoff(first_ones_8bit#),gp;;	    //32.	cc:0
> }
> {   .mmi  //R-Addr: 0X010
>	cmp.eq.unc p7,p6=r0, r30;;			    //20.	cc:1
>	ld8	r28=[r31]				    //32.	cc:2
>  (p6)	mov	r32=r30					    //21.	cc:2
> }
> {   .mmi  //R-Addr: 0X020
>  (p7)	mov	r29=32;;				    //23.	cc:2
>	nop.m	 0
>	shr.u	r27=r32, 16;;				    //24.	cc:3
> }
> {   .mmi  //R-Addr: 0X030
>	cmp.eq.unc p9,p8=r0, r27;;			    //24.	cc:4
>  (p8)	mov	r32=r27					    //25.	cc:5
>  (p9)	adds	r29=16, r29;;				    //27.	cc:5
> }
> {   .mii  //R-Addr: 0X040
>	nop.m	 0
>	shr.u	r26=r32, 8;;				    //28.	cc:6
>	cmp.eq.unc p11,p10=r0, r26;;			    //28.	cc:7
> }
> {   .mii  //R-Addr: 0X050
>  (p10)	mov	r32=r26					    //29.	cc:8
>  (p11)	adds	r29=8, r29;;				    //31.	cc:8
>	add	r25=r28, r32;;				    //32.	cc:9
> }
> {   .mmi  //R-Addr: 0X060
>	ld1	r22=[r25];;				    //32.	cc:11
>	add	r8=r22, r29				    //32.	cc:13
>	nop.i	 0
> }
> {   .mfb  //R-Addr: 0X070
>	nop.m	 0
>	nop.f	 0
>	br.ret.sptk.few b0;;				    //33 	cc:13
> }
>
>// Begin code for function: LastOne:
>	.proc	LastOne#
>	.align 32
>LastOne:	 						// COMDAT
>// File c:\crafty\vcinline.h
> {   .mii  //R-Addr: 0X00
>	cmp4.eq.unc p7,p6=r0, r32			    //39.	cc:0
>	mov	r30=65535				    //45.	cc:0 	mov	r29=255					    //51.	cc:0
> }
> {   .mmi  //R-Addr: 0X010
>	mov	r28=r0;;				    //38.	cc:0
>	addl	r31=@ltoff(last_ones_8bit#),gp		    //57.	cc:1
>  (p7)	shr.u	r27=r32, 32				    //44.	cc:1
> }
> {   .mii  //R-Addr: 0X020
>  (p6)	mov	r28=32					    //41.	cc:1
>  (p6)	zxt4	r27=r32;;				    //40.	cc:1
>	and	r25=r30, r27				    //45.	cc:2
> }
> {   .mmi  //R-Addr: 0X030
>	ld8	r26=[r31];;				    //57.	cc:2
>	cmp.eq.unc p9,p8=r0, r25			    //45.	cc:3
>	nop.i	 0;;
> }
> {   .mii  //R-Addr: 0X040
>  (p8)	mov	r22=r25					    //46.	cc:4
>  (p9)	shr.u	r22=r27, 16				    //50.	cc:4
>  (p8)	adds	r28=16, r28;;				    //47.	cc:4
> }
> {   .mmi  //R-Addr: 0X050
>	and	r21=r29, r22;;				    //51.	cc:5
>	cmp.eq.unc p11,p10=r0, r21			    //51.	cc:6
>	nop.i	 0;;
> }
> {   .mii  //R-Addr: 0X060
>  (p10)	mov	r20=r21					    //52.	cc:7
>  (p11)	shr.u	r20=r22, 8				    //56.	cc:7
>  (p10)	adds	r28=8, r28;;				    //53.	cc:7
> }
> {   .mmi  //R-Addr: 0X070
>	add	r19=r26, r20;;				    //57.	cc:8
>	ld1	r18=[r19]				    //57.	cc:9
>	nop.i	 0;;
> }
> {   .mfb  //R-Addr: 0X080
>	add	r8=r18, r28				    //57.	cc:11
>	nop.f	 0
>	br.ret.sptk.few b0;;				    //58 	cc:11
> }
>
>Please notice that there are no branches -- IA-64 allows to use predicated
>instructions instead. So no branch mispredict penalty. Assuming that both
>256-bytes tables are in the L1 cache, FirstOne() is executed in 14 clock cycles,
>LastOne() in 12.
>
>Eugene



This page took 0.07 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.