避免在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'指令。

我使用它来稍后计算弹出计数，因此我也可以使用类似<<

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

有没有办法避免这种情况，或者这是编译器吗？

Answer 1

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

（（GCC在调整Haswell时要小心打破the output dependency of tzcnt，以避免通过该错误的依赖关系创建循环承载的依赖关系链的风险。不幸的是，GCC仍然使用tzcnt来做到这一点，它没有错误的后备对于-march=skylake，仅tzcnt，对于popcnt为“ true”。）

Intel将bsr/bsf的第二个输入记录为_bzhi_u64。 （出于某种原因，您要使用uint32_t的unsigned __int32 index对此进行显式显示，但是删除显式转换无济于事）。 IDK MSVC如何定义内在函数或在内部处理它。

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

---

屏蔽的popcnt：移位tzcnt而不是对其进行屏蔽

与yyy中一样，仅移出不需要的位，而不是就位将其清零会更有效。 （尽管What is the efficient way to count set bits at a position or lower?避免了创建掩码的开销，所以这只是盈亏平衡，模数差异，执行端口bzhi与bzhi可以在其中运行。）shrx不在乎这些位在何处。

popcnt

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

MSVC on Godbolt

前端总共3个ouop =与其他周围的代码混合使用时，对整体吞吐量非常有用。

后端瓶颈：Intel CPU上的端口1（tzcnt和popcnt）的2微克。 （shrx作为单个uop在端口0或端口6上运行。启用AVX2（显然为MSVC启用BMI2很重要，否则，它将使用3-uop

;; 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

）关键路径延迟：

• [从shr rax, cl到结果：SHRX为1，popcnt = 4个周期为3
• 从yyy到结果：TZCNT为3，加上上述= 7个周期

不幸的是，GCC对于打破错误的依赖关系过于谨慎，这会花费额外的前端带宽。 （但没有额外的后端成本）

xxx

没有

# 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

的较低延迟替代方案

BMI1具有一些bithack指令来执行诸如隔离最低置位比特之类的工作，所有这些1 uop都具有Intel的单周期延迟。 （AMD Zen将它们以2 uops，2个周期的延迟运行：tzcnt）

uops.info-获取掩码，直到（包括）最低设置位。您的原件是[[not，包括blsmsk中的LSB，因此很抱歉，此遮罩无法直接使用。

blsmskxxx

或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，我们将得到

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

blsi(xxx) - 1

GCC使用可以在任何端口上运行的较短指令，使用2的补码身份将其转换为此字符。 （xxx=1只能在Haswell / Skylake的端口1或端口5上运行）
uint64_t zmask2(uint64_t xxx, uint64_t yyy) {
    auto setbit = _blsi_u64(xxx); 
    auto masked = yyy & ~(setbit-1);  // yyy & -setbit
    return masked;
}

这是3 oups（不包括popcnt），但从        blsi    rax, rcx
        dec     rax
        andn    rax, rax, rdx
        ret     0
开始到结果只有3个周期延迟->从andn / ;; GCC7.5 -O3 -march=haswell.   Later GCC wastes a `mov` instruction
        blsi    rax, rdi
        neg     rax
        and     rax, rsi
的4个周期降低。（所有这些都不包括3个周期popcnt延迟），更重要的是，
它不与xxx竞争端口1。
（但是，端口1 /端口5的MSVC编译为tzcnt +shrx+ popcnt的方式是2 oups。]
最佳选择取决于周围的代码，是吞吐量还是延迟是瓶颈。如果您要对连续存储的许多不同蒙版进行此操作，则SIMD可能有效。避免使用blsi意味着您可以通过采取一些说明的bithack来进行最低设置的隔离或屏蔽。例如dec为andn，如Intel的asm手册的“操作”部分所述。 （方便查找位图表达式的地方。）tzcnt是blsi
SIMD popcnt可以用(-SRC) bitwiseAND (SRC)完成，以便在每个字节的两半上进行4位并行LUT，并且您可以blsmsk在每个元素的水平计数中进行累加。 （模拟冰湖的AVX512 (SRC-1) XOR (SRC)）