x86-64 SIMD popcnt

[David Sparks]

On Sunday, 11 October 2026 at 05:39, David Sparks <sparks05 at proton.me> wrote:
> Fun reading!  My detailed comments got lost in a power glitch,
> but while I'm recreating this, I got the following working.

And my comments.  If I left a thought unfinished, it's because I
remember explaining it before the power outage.


In general, it's all tight, well-written code.  There's one redundant
PAND per 2 limbs in the XOP code, and it's possible to remove one
PADDB per loop iteration in the AVS2 and SSSE3 code (16 and 8 limbs,
resp.), but that's it for the inner loops.  My only comments relate
to the loop initialization and finalization.


One area I notice a lot of variety is the final folding & summation of
the SIMD results (2, 4 or 8 64-bit limbs) and transfer to the integer
execution unit.  Obviously, someone (who, me?) should run some benchmarks
to see which is better.

One option is to store 4 limbs to the stack, and then fetch and sum the
limbs from there.  This is complicated by lack of dependable red zone;
the code mostly uses the SYSV ABI, which does guarantee the safety
of temp space down to -128(%rsp), but it runs on Windows, which
is allowed to corrupt data below the stack pointer with no notice.

[Tangent: I wish we could use GCC's __attribute__((sysv_abi)) to avoid
the DOS/Win FUNC_ENTRY crap.  Unfortunately, some x86 asm mpn functions
are part of the exported interface, so it would infect public headers
and cause dynamic linking problems. :-(]

When storing to the stack, I notice two options: aligned (avx3-256b) and
unaligned (avx2).  It hardly seems worth the extra two instructions to
set up the stack (saving and ANDing the stack pointer) to avoid a single
unaligned store.  Also, x86 does very aggressive stack pointer tracking,
and restoring from a register probably messes that up.


The second is to fold in the SSE registers, and then transfer
to integer using MOVQ (and VPEXTRQ if it exists).

Here, again, there's a split.  Folding to 128 bits is an
obvious win, but then there are two choices.  First, fold
to one limb in SSE registers and do a single MOVQ, as is done
in the AVX2 and SSSE3 code:

	pshufd	$14, %xmm8, %xmm0
	paddq	%xmm8, %xmm0
	movq	%xmm0, %rax
	ret

Second, fold to two limbs and do the final addition on the integer
side, as in the avx3-512b code:

	vextracti64x4	$1, %zmm2, %ymm0
	vpaddq		%ymm2, %ymm0, %ymm0
	vextracti64x2	$1, %ymm0, %xmm1
	vpaddq		%xmm1, %xmm0, %xmm0
	vpextrq		$1, %xmm0, %rax
	vmovq		%xmm0, %rdx
	add		%rdx, %rax
	ret

Even if VPEXTRQ isn't available (it's part of SSE4.1), it's an
interesting toss-up between
	pshufd	$14, %xmm8, %xmm0
	paddq	%xmm8, %xmm0
	movq	%xmm0, %rax		
and
	pshufd	$14, %xmm8, %xmm0
	movq	%xmm8, %rax
	movq	%xmm0, %rdx
	add	%rdx, %rax

AMD processors from the relevant era had latency-2 SSE instructions,
so the first sequence has latency 6, while the second has latency 5:
the PSHUFD and first MOVQ overlap, and the integer ADD has latency 1.

Intel processors had latency-1 PADDQ, so it's probably not worth
the extra space.


== popcount-avx2.asm, x64-popcount-avx2.asm (identical files) ==

It's a minor point, mostly applicable to early AVX implementations which
double-pumped a 256-bit ALU but, like "xor %eax, %eax", the fastest way
to clear a ymm register is to xor the low half and let the high-clearing
happen automatically.

- 	vpxor	%ymm5, %ymm5, %ymm5
-	vpxor	%ymm8, %ymm8, %ymm8
+ 	vpxor	%xmm5, %xmm5, %xmm5
+	vpxor	%xmm8, %xmm8, %xmm8

Negligible, but take the free win.  c.f.
https://stackoverflow.com/questions/43713273/is-vxorps-zeroing-on-amd-jaguar-bulldozer-zen-faster-with-xmm-registers-than-ymm
https://web.archive.org/web/20240728102708/https://gcc.gnu.org/bugzilla/show_bug.cgi?id=80636

Likewise, when adding up the results, narrow to 128 bits first:
- 	vpshufd	$14, %ymm8, %ymm0
- 	vpaddq	%ymm8, %ymm0, %ymm0
 	vextracti128	$1, %ymm0, %xmm8
 	vpaddq	%xmm8, %xmm0, %xmm0
+ 	vpshufd	$14, %xmm0, %xmm8
+ 	vpaddq	%xmm8, %xmm0, %xmm0
 	vmovq	%xmm0, %rax

(It's also just plain clearer.)

Or, as mentioned above, do the final summation on the integer side:
	vextracti128	$1, %ymm0, %xmm8
	vpaddq		%xmm8, %xmm0, %xmm0
	vpextrq		$1, %xmm0, %rax
	vmovq		%xmm0, %rdx
	add		%rdx, %rax


A minor optimization point is that VEX2 can encode a 4-bit source1 and
destination register number, but only a 3-bit source2.  The above is
nicely VEX2-encoable (except for opcodes like vextracti128 which aren't
VEX2-codable at all.)

The other summation code (saving to a stack slot) could be simplified
if you knew you had a red zone, but that's not the case. :-(


-	vpsadbw	%ymm5, %ymm4, %ymm10		C sum to 16 x 16-bit counts
-	vpaddq	%ymm10, %ymm8, %ymm8		C sum to 4 x 64-bit counts
+	vpsadbw	%ymm5, %ymm4, %ymm10		C sum to 4 x 16-bit counts
+	vpaddq	%ymm10, %ymm8, %ymm8		C accumulate 4 x 64-bit counts

That first comment is misleading.  There are 4 counts.  Whether you call
them 16 bits or 64 bits is a detail of zero-padding.


You could save one VPADDB intruction in the loop by using two VPSHUFB
lookup tables (one negated) and letting VPSADBW do the addition for you.

You'd need to accumulate the negated lookup results in %ymm5,
then let VPSADBW subtract the two.

It's almost certainly not worth bothering, as one VPADDB per 128 bytes
of input is pretty negligible.  Still, with sufficient perversity,
this would let initialize things as

	vpbroadcastb	(%rdx), %ymm6
	vbroadcasti128	(%rdx), %ymm7	# 15 + [0..4]
	vpaddb	%ymm6,%ymm6,%ymm9
	vpsubb	%ymm7,%ymm9,%ymm9	# 15 - [0..4]

DEF_OBJECT(cnsts,16)
	.byte	15,16,16,17,16,17,17,18,16,17,17,18,17,18,18,19
END_OBJECT(cnsts)

This avoids a stray byte creating alignment padding.


== popcount-ssse3.asm ===

DEF_OBJECT(L(cnsts),16)

Shouldn't that size be 64?

The same save-one-PADDB-per-iteration applies, FWIW.

Also, you could shrink the jump offsets to 16 bits; movswq (REX 0F BF /r)
is only one byte longer than movslq (REX 63 /r).


== popcount-xop.asm ==

I haven't looked hard at this, since XOP is pretty dead.

However, one thing jumps out:

 L(top):	lddqu	(ap), %xmm0
 	vpshlb	%xmm6, %xmm0, %xmm1
 	pand	%xmm9, %xmm0
-	pand	%xmm9, %xmm1
 	vpperm	%xmm0, %xmm7, %xmm7, %xmm2
 	vpperm	%xmm1, %xmm7, %xmm7, %xmm3
 	paddb	%xmm2, %xmm3
 	paddb	%xmm3, %xmm4

Since XOP has true logical byte shifts, the high nibble after shifting
is already zero; there's no need to do an explicit mask as is needed
when you're faking it with PSRLW and need to clear bits 4..7.

(An alternative which avoids the shift-count register is VPROTB,
but then you need the mask again.)

It's a shame the simpler PHADDUBQ instructions are more expensive
than PSADBW.


== x64-popcount-avx3-256b.asm ==

Wow, vpopcntq makes things easy.  And load masks...

I'm surprised that final summation via memory is worth it.

	mov		%rsp, %rax
	sub		$32, %rsp
	and		$-32, %rsp
	vmovdqa64	%ymm2, (%rsp)
	mov		(%rsp), %r8
	add		8(%rsp), %r8
	mov		16(%rsp), %r9
	add		24(%rsp), %r9
	add		%r9, %r8
	mov		%rax, %rsp
	mov		%r8, %rax
	ret

An instruction could be removed by replacing the last four lines
with
	mov		%rax, %rsp
	lea		[%r8+%r9], %rax
	ret
... or just permute the registers so %rsp is spilled
elsewhere and the final result can be directly computed
into %rax.

It's pretty trivial, but I'd do the addition in mov/mov/add/add
order:
	mov		(%rsp), %r8
	mov		8(%rsp), %r9
	add		16(%rsp), %r8
	add		24(%rsp), %r9
	lea		[%r8+%r9], %rax
just because it reduces the amount ot OOO lookahead required.

Again, a red zone would make this so much nicer.

I know x86 can handle multiple pus/pop operations per cycle.
I wonder about:
	pop		%r8
	pop		%r9
	add		(%rsp), %r8
	add		8(%rsp), %r9
	lea		[%r8+%r9], %rax


Two other notes:
- Why use (EVEX-encoded) VMOVDQA64 instead of (VEX) VMOVDQA?
  The only reason to specify the element size is to use a mask,
  and this isn't using one.
- Any use VMOVDQA rather than VMOVDQU like the AVX2 code?
  There are two extra instructions, one on the critical path,
  to get an aligned stack pointer, while an unaligned store
  will probably have a penalty of at most 1 cycle.
  
  The stack *will* be unaligned, because stack pointers are 16-byte
  aligned *before* the call pushes the return address.  But you can
  easily get a chance of an aligned buffer by subtracting 40 from %rsp
  when making space.  (Or 56 if you think there's a better than even
  chance the caller had a 32-byte aligned stack,)


== x64-popcount-avx3-512b.asm ==

Nothing to add.  I like the final summation with MOVQ better.

== x64-popcount-bull.asm ==

See comment to the XOP code about the redundant shift.

According to Agner Fog, VPHADD* is 3 μops, 5-cycle latency, and 2-cycle
reciprocal throughout on Bulldozer.  PSADBW is 2/4/1, so is faster if
the input bytes fit into 7 bits.