折叠 __mask64 又名 64 位整数值，计算已设置所有位的半字节？

Question

我有__mask64一些 AVX512 操作的结果：

__mmask64 mboth = _kand_mask64(lres, hres);

我想计算其中所有位均已设置的半字节数 ( 0xF)。

简单的解决方案是这样做：

uint64 imask = (uint64)mboth;
while (imask) {
    if (imask & 0xf == 0xf)
        ret++;
    imask = imask >> 4;
} 

我想要更好的东西，但我想出的东西并不优雅：

    //outside the loop
    __m512i b512_1s = _mm512_set1_epi32(0xffffffff);
    __m512i b512_0s = _mm512_set1_epi32(0x00000000);

    //then...
    __m512i vboth = _mm512_mask_set1_epi8(b512_0s, mboth, 0xff);
    __mmask16 bits = _mm512_cmpeq_epi32_mask(b512_1s, vboth);
    ret += __builtin_popcount((unsigned int)fres);

上面将一个0xff字节放入一个向量中，其中掩码中存在 1 位，然后当现在发现bits放大的半字节为' 时，在掩码中获取一个 1 位。0xf0xffffffff int32

我觉得当原始数据存在于 64 位数字中时，两个 512 位操作太过分了。这个替代方案可能要糟糕得多。它的指令太多，而且仍然在 128 位上运行：

    //outside the loop
    __m128i b128_1s = _mm_set1_epi32(0xffffffff);

    //then...
    uint64 maskl = mboth & 0x0f0f0f0f0f0f0f0f;
    uint64 maskh = mboth & 0xf0f0f0f0f0f0f0f0;
    uint64 mask128[2] = { (maskl << 4) | maskl, (maskh >> 4) | maskh };
    __m128i bytes   = _mm_cmpeq_epi8(b128_1s, *(__m128i*)mask128);
    uint bits = _mm_movemask_epi8(bytes);
    ret += __builtin_popcount(bits);

Answer 1

只需一些标量操作，您就可以做到这一点：

imask &= imask << 2;
imask &= imask << 1;
ret += std::popcount(imask & 0x8888888888888888);

对于每个半字节，前两个步骤将该半字节的位的水平与放在该半字节的最高有效位中。半字节的其他部分变成了我们不想要的东西，所以我们只是将它们屏蔽掉。然后对结果进行popcount。

轮班可以向右（如本答案的早期版本所示），也可以轮换，以效果最好的为准。

Clang 从这个版本中实现了高效的 asm，除了之前的异或清零之外，popcnt没有任何浪费的指令，内联应该会消失，因为它popcnt same,same甚至可以在不提前计划的情况下将结果存入 EAX 中以用于调用约定。

GCC 做得不错，但对最后一个重新排序&= mask，因此它是关键路径延迟的一部分，而不是与移位并行，尽管我们尽了最大努力使源代码看起来像单个汇编操作，以尝试将其掌握为更好的汇编。

MSVC 对此很奇怪，它把它变成了右移，并且&= mask像 GCC 一样做最后一个。

// Clang compiles this optimally, hopefully also when inlining
// GCC still does the & mask last, on the critical path
// MSVC mangles this, with two right shifts despite the source going left, and deoptimizes latency like GCC
int count_nibbles(uint64_t imask)
{
    uint64_t mask = 0x2222222222222222;  // movabs, or hoisted out of a loop
    uint64_t shifted = imask << 1;   // LEA dst, [src+src] into a new reg
    shifted &= imask;                // AND
    shifted >>= 2;                   // SHR
    imask &= mask;                   // AND into original reg, in parallel with the shift/AND chain
    shifted &= imask;                // AND
    return std::popcount(shifted);   // POPCNT
}

此版本还可以防止 clang 对移位或旋转进行去优化，其中lea reg, [0 + reg*4]8 字节长且在 Alder Lake / Sapphire Rapids 上有 2 个周期的延迟。（https://uops.info/）。

Godbolt用于此版本和其他几个版本（包括 chtz 的 ADD/ADC 技巧的便携式版本）。在函数中的某个点使用asm("" : "+r"(imask))可以强制 GCC 不要取消优化操作顺序，但这可能会阻止它作为更大循环的一部分对其进行优化。

在同一源代码行上编写多个操作不会对 Clang 造成任何伤害，而且这样做仍然不能阻止 GCC 把它搞砸，但这确实说明了最佳的 asm 应该是什么样子。您可能更愿意将其压缩为更少的 C 语句。

如果可能的话，GCC 将移位和与组合在一起的重新排序通常对于 AArch64 很有用and x1, x0, x0, lsr 2。但即便如此，指令级并行仍然是可能的，同时仍然只使用 3 个 AND 指令，其中两个指令具有移位的操作数。 GCC/Clang/MSVC 错过了该优化。按位指令的 AArch64 重复模式立即数确实允许0x2222222222222222或0x8888888888888888，因此不需要单独的常量设置。