避免 bzhi(y, tzcnt(x)) 中不必要的 mov ecx, ecx 指令

Question

我有一个位位置（它永远不会为零），通过使用 tzcnt 计算得出，我想从该位置开始将高位归零。这是 C++ 和反汇编代码（我使用的是 MSVC）：

auto position = _tzcnt_u64(xxx); 
auto masked =_bzhi_u64(yyy, static_cast<uint32_t>(position));

tzcnt       rcx,rdx  
mov         ecx,ecx  
bzhi        rax,rbx,rcx 

BZHI 接受 unsigned int 作为第二个参数，但仅使用 rcx 中的位 [7..0]，因此我认为这个“mov”指令是不必要的。

我用它来稍后计算 popcount，所以我也可以使用类似 <<(64-position) 的东西来代替。

问题是 - 这两个代码具有相同的执行时间，尽管 bzhi 应该比 sub+shlx 执行得更快，所以 mov 可能会产生差异。

有没有办法避免它或者这是编译器的事情？

Answer 1

这是 MSVC 错过的优化。GCC/clang 可以直接在源bzhi的输出上使用。tzcnt所有编译器都会在某些情况下错过优化，但 GCC 和 clang 的情况往往比 MSVC 少。

（并且 GCC 在调整 Haswell 时会小心地打破 的输出依赖性tzcnt，以避免通过该错误依赖性创建循环携带的依赖性链的风险。不幸的是，GCC 仍然这样做，-march=skylake但它没有错误的 dep for tzcnt，只有popcnt。讽刺的是，GCC 并没有打破对任何 CPU 的“真正”依赖bsr/bsf。）

英特尔将第二个输入记录为_bzhi_u64as unsigned __int32 index。（出于某种原因，您使用static_castto uint32_t 进行显式转换，但删除显式转换并没有帮助）。我不知道 MSVC 如何定义内在函数或在内部处理它。

我不知道为什么 MSVC 要这样做；我想知道 MSVC 内在函数的内部逻辑是否零扩展为 64 位，_bzhi_u64它采用 32 位 C 输入，但使用 64 位 asm 寄存器。（tzcnt的输出值范围是 0..64，因此在这种情况下此零扩展是无操作）

Masked popcnt：移位yyy而不是屏蔽它

如对某个位置或更低位置处的设置位进行计数的有效方法是什么？，直接移出不需要的位而不是就地清零可能会更有效。（尽管bzhi避免了创建掩码的成本，因此这只是收支平衡，执行端口bzhi与shlx可以运行的模数差异。） popcnt不关心位在哪里。

（修复：C++ 和 asm 使用右移，这会丢弃低位。我应该使用左移移出高位。 当我写这篇文章时，我可能正在考虑丢弃低位，因为tzcnt在其他输入中计算低位零.左移和右移执行相同的操作，因此我暂时保留答案。）

uint64_t popcnt_shift(uint64_t xxx, uint64_t yyy) {
    auto position = _tzcnt_u64(xxx); 
    auto shifted = yyy >> position;
    return _mm_popcnt_u64(shifted);
}

Godbolt 上的 MSVC

;; MSVC 19.24 -O2 -arch:AVX2  (to enable BMI for andn)
;; also clang10.0 -O3 -march=haswell  makes this asm
unsigned __int64 popcnt_shift(unsigned __int64,unsigned __int64) PROC
        tzcnt   rax, rcx
        shrx    rax, rdx, rax
        popcnt  rax, rax
        ret     0

前端总共 3 个 uop = 与其他周围代码混合时，整体吞吐量非常好。

后端瓶颈：Intel CPU 上的端口 1（tzcnt 和 popcnt）为 2 uops。（shrx 作为单个 uop 在端口 0 或端口 6 上运行。启用 AVX2（这显然为 MSVC 启用了 BMI2）很重要，否则它将使用 3-uop shr rax, cl）关键路径延迟：

• 从yyy到结果：SHRX 为 1，popcnt 为 3 = 4 个周期
• 从xxx到结果：TZCNT 为 3 加上上述 = 7 个周期

不幸的是，GCC 对于打破错误的依赖关系过于谨慎，从而消耗了额外的前端带宽。（但没有额外的后端费用）

# GCC10.1
        xor     eax, eax          # could have just done tzcnt rdi,rdi
        tzcnt   rax, rdi
        shrx    rsi, rsi, rax
        xor     eax, eax          # pointless: RAX was already part of the dep chain leading to this.
        popcnt  rax, rsi          # GCC7.5 shifts into RAX for popcnt rax,rax to avoid this dep-breaking xor.
        ret

更低延迟的替代方案，无需tzcnt

（但是 uop 越多，前端吞吐量可能会更差。后端执行端口压力的好处取决于周围的代码。）

BMI1 有一些 bithack 指令来执行诸如隔离最低设置位之类的操作，所有 1 uop 均具有 Intel 上的单周期延迟。（AMD Zen 以 2 uops、2 个周期延迟运行它们：uops.info）

blsmsk- 使掩码达到（并包括）最低设置位。您的原始版本不包含LSB，xxx因此不幸的是，该掩码无法直接使用。

uint64_t zmask_blsmsk(uint64_t xxx, uint64_t yyy) {
    auto mask = _blsmsk_u64(xxx); 
    auto masked = yyy & ~(mask<<1);
    return masked;
}

;; MSVC -O2 -arch:AVX2  (to enable BMI for andn)
        blsmsk  rax, rcx
        add     rax, rax               ; left shift
        andn    rax, rax, rdx          ; (~stuff) & yyy
        ret     0

或者blsi将隔离最低设置位。 这blsi(xxx) - 1将创建一个直到但不包括它的掩码。（对于xxx=1，我们将得到

uint64_t zmask2(uint64_t xxx, uint64_t yyy) {
    auto setbit = _blsi_u64(xxx); 
    auto masked = yyy & ~(setbit-1);  // yyy & -setbit
    return masked;
}

MSVC 按预期编译，与 clang 相同：

        blsi    rax, rcx
        dec     rax
        andn    rax, rax, rdx
        ret     0

GCC 使用 2 的补码恒等式将其转换为此形式，并使用可以在任何端口上运行的较短指令。（andn只能在 Haswell / Skylake 上的端口 1 或端口 5 上运行）

;; GCC7.5 -O3 -march=haswell.   Later GCC wastes a `mov` instruction
        blsi    rax, rdi
        neg     rax
        and     rax, rsi

这是 3 uop（不包括 popcnt），但从xxx-> 结果只有 3 个周期延迟，低于tzcnt/的 4 个周期延迟shrx。 （所有这些都没有计算 3 个周期的 popcnt 延迟）更重要的是，它不会与popcnt.

blsi（不过，MSVC 将其编译为+ dec+的方式andn对于端口 1 / 端口 5 来说是 2 uops。）

最佳选择将取决于周围的代码，吞吐量或延迟是否是瓶颈。

如果您对连续存储的许多不同掩码执行此操作，SIMD 可能会很有效。避免tzcnt意味着您可以使用需要几个指令的位黑客来执行最低设置的隔离或掩码。例如，blsi如(-SRC) bitwiseAND (SRC)Intel 的 asm 手册的操作部分中所述。（查找位图表达式的方便地方。） blsmsk是(SRC-1) XOR (SRC)

SIMD popcnt 可以vpshufb在每个字节的两半上进行 4 位并行 LUT，并且可以vpsadbw水平累加每个元素的计数。（模拟Ice Lake的AVX512 vpopcntq）