If AVX2 is available, see is there an inverse instruction to the movemask instruction in intel avx2? instead for more efficient versions using integer SIMD. You could use that idea and split your bitmap into two 4-bit chunks for use with a LUT. That might perform fairly well: vinsertf128 has 1 per clock throughput on Sandybridge, and one per 0.5c on Haswell/Skylake.
A SIMD-integer solution with AVX1 could just do the same work twice for high/low vector halves (2x broadcast the bitmap, 2x mask it, 2x vpcmpeqd xmm), then vinsertf128, but that kinda sucks.
You might consider making an AVX2 version separate from your AVX1-only version, using vpbroadcastd ymm0, mem / vpand ymm0, mask / vpcmpeqd dst, ymm0, mask, because that's very efficient, especially if you're loading the bitmap from memory and you can read a whole dword for the bitmap. (Broadcast-loads of dword or qword don't need an ALU shuffle so it's worth overreading). The mask is set_epi32(1<<7, 1<<6, 1<<5< ..., 1<<0), which you can load with vpmovzxbd ymm, qword [constant] so it only takes 8 bytes of data memory for 8 elements.
Intrinsics version, see below for explanation and asm version. Compiles about how we expect on Godbolt with gcc/clang -march=sandybridge
#include <immintrin.h>
// AVX2 can be significantly more efficient, doing this with integer SIMD
// Especially for the case where the bitmap is in an integer register, not memory
// It's fine if `bitmap` contains high garbage; make sure your C compiler broadcasts from a dword in memory if possible instead of integer load with zero extension.
// e.g. __m256 _mm256_broadcast_ss(float *a); or memcpy to unsigned.
// Store/reload is not a bad strategy vs. movd + 2 shuffles so maybe just do it even if the value might be in a register; it will force some compilers to store/broadcast-load. But it might not be type-punning safe even though it's an intrinsic.
// Low bit -> element 0, etc.
__m256 inverse_movemask_ps_avx1(unsigned bitmap)
{
// if you know DAZ is off: don't OR, just AND/CMPEQ with subnormal bit patterns
// FTZ is irrelevant, we only use bitwise booleans and CMPPS
const __m256 exponent = _mm256_set1_ps(1.0f); // set1_epi32(0x3f800000)
const __m256 bit_select = _mm256_castsi256_ps(
_mm256_set_epi32( // exponent + low significand bits
0x3f800000 + (1<<7), 0x3f800000 + (1<<6),
0x3f800000 + (1<<5), 0x3f800000 + (1<<4),
0x3f800000 + (1<<3), 0x3f800000 + (1<<2),
0x3f800000 + (1<<1), 0x3f800000 + (1<<0)
));
// bitmap |= 0x3f800000; // more efficient to do this scalar, but only if the data was in a register to start with
__m256 bcast = _mm256_castsi256_ps(_mm256_set1_epi32(bitmap));
__m256 ored = _mm256_or_ps(bcast, exponent);
__m256 isolated = _mm256_and_ps(ored, bit_select);
return _mm256_cmp_ps(isolated, bit_select, _CMP_EQ_OQ);
}
If we get creative, we can use AVX1 FP instructions to do the same thing. AVX1 has dword broadcast (vbroadcastss ymm0, mem), and booleans (vandps). That will produce bit patterns that are valid single-precision floats so we could use vcmpeqps, but they're all denormals if we leave the bitmap bits in the bottom of the element. That might actually be fine on Sandybridge: there might be no penalty for comparing denormals. But it will break if your code ever runs with DAZ (denormals-are-zero), so we should avoid this.
We could vpor with something to set an exponent before or after masking, or we could shift the bitmap up into the 8-bit exponent field of the IEEE floating-point format. If your bitmap starts in an integer register, shifting it would be good, because shl eax, 23 before movd is cheap.
But if it starts in memory, that means giving up on using a cheap vbroadcastss load. Or you could broadcast-load to xmm, vpslld xmm0, xmm0, 23 / vinsertf128 ymm0, xmm0, 1. But that's still worse than vbroadcastss / vorps / vandps / vcmpeqps
(Scalar OR before store/reload solves the same problem.)
So:
# untested
# pointer to bitmap in rdi
inverse_movemask:
vbroadcastss ymm0, [rdi]
vorps ymm0, ymm0, [set_exponent] ; or hoist this constant out with a broadcast-load
vmovaps ymm7, [bit_select] ; hoist this out of any loop, too
vandps ymm0, ymm0, ymm7
; ymm0 exponent = 2^0, mantissa = 0 or 1<<i where i = element number
vcmpeqps ymm0, ymm0, ymm7
ret
section .rodata
ALIGN 32
; low bit -> low element. _mm_setr order
bit_select: dd 0x3f800000 + (1<<0), 0x3f800000 + (1<<1)
dd 0x3f800000 + (1<<2), 0x3f800000 + (1<<3)
dd 0x3f800000 + (1<<4), 0x3f800000 + (1<<5)
dd 0x3f800000 + (1<<6), 0x3f800000 + (1<<7)
set_exponent: times 8 dd 0x3f800000 ; 1.0f
; broadcast-load this instead of duplicating it in memory if you're hoisting it.
Instead of broadcast-loading set_exponent, you could instead shuffle bit_select: as long as the 0x3f800000 bits are set, it doesn't matter if element 0 also sets bit 3 or something, just not bit 0. So vpermilps or vshufps to copy-and-shuffle would work.
Or if the bitmap is in an integer register to start with, you can use scalar OR and avoid that vector constant. (And scalar OR runs on more ports.)
# alternate top of the function for input in an integer reg, not pointer.
or edi, 0x3f800000
mov [rsp-4], edi ; red-zone
vbroadcastss ymm0, [rsp-4]
;; skip the vorps
Store/reload might have similar latency to vmovd (1c), vpshufd xmm (1c), vinsertf128 (3c) = 5c total to broadcast from an integer register without AVX2 or AVX512 on Intel SnB-family. And it's fewer fused-domain uops (2 instead of 3), and doesn't hit the shuffle port (3 uops for p5 on SnB-family). Your choice might depend on whether there's there's load/store pressure or port-5 pressure in the surrounding code.
(SnB/IvB have integer-shuffle units on 2 ports, only FP shuffles are limited to 1. Haswell remove the shuffle units outside of p5.
But unless you do dynamic dispatching to avoid using this on AVX2 CPUs, you might want to tune for newer CPUs while still maintaining compat with AVX1-only CPUs.)
If you were going to do an ALU broadcast with shuffles (like clang does), you could borrow clang's trick of doing a vorps xmm to save a uop on AMD CPUs that split 256-bit ops, and to allow a narrower OR constant. But that's pointless: either you had the value in an integer register (where you can use scalar or), or it was in memory where you should have used vbroadcastss ymm. I guess if tuning for AMD before Zen2 you might consider an broadcast XMM load, VPOR XMM, then vinsertf128.
https://www.h-schmidt.net/FloatConverter/IEEE754.html is a useful IEEE754 FP value <-> hex bit pattern converter, in case you want to check what value some FP bit pattern represents.
vcmpeqps has the same latency and throughput as vaddps on all Intel CPUs. (This is not a coincidence; they run on the same execution unit). That means 3 cycle latency o
