c++ - 避免在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时要小心地打破the output dependency of tzcnt ，以避免通过该虚假依赖关系创建循环承载的依赖链的风险。不幸的是，GCC仍然使用-march=skylake来做到这一点，而tzcnt并没有假的dep，只有popcnt和bsr/bsf的“真实”说明。)

英特尔将_bzhi_u64的第二个输入记录为unsigned __int32 index。 (出于某种原因，您使用static_cast到uint32_t对此进行了显式显示，但是删除显式转换无济于事)。 IDK MSVC如何定义内在函数或在内部处理它。

IDK为什么MSVC要这样做？我想知道在MSVC的_bzhi_u64内部函数的内部逻辑中是否将其零扩展到64位，该内部逻辑接受32位C输入但使用64位asm寄存器。 (tzcnt的输出值范围是0..64，因此在这种情况下，此零扩展名是空操作)

Masked popcnt:转移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

;; 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 =与其他周围的代码混合使用时，对于整体吞吐量来说非常好。

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

从yyy到结果:1用于SHRX，3用于popcnt = 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的低延迟替代方案

(但是，更多的操作可能会导致前端吞吐量下降。后端执行端口压力的提高取决于周围的代码。)

BMI1具有一些bithack指令来执行操作，例如隔离最低设置位，所有1 uop以及Intel的单周期延迟。 (AMD Zen将它们以2 uops，2个周期的延迟运行:uops.info)

blsmsk -获取掩码最高(包括最低设置位)。您的原件不包含xxx中的LSB，因此很遗憾，此掩码不能直接使用。

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微秒(不包括popcnt)，但是从xxx->结果仅具有3个周期的延迟，从tzcnt / shrx的4个周期降低。 (所有这些都不计算3个周期的popcnt延迟)，更重要的是，不能与popcnt争用端口1。

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

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

如果您要对连续存储的许多不同蒙版进行此操作，则SIMD可能会有效。避免使用tzcnt意味着您可以使用带有一些说明的bithack来进行最低设置的隔离或屏蔽。例如blsi是(-SRC) bitwiseAND (SRC)，如英特尔的asm手册的“操作”部分所述。 (在方便的地方查找位图表达式。)blsmsk是(SRC-1) XOR (SRC)
SIMD popcnt可以使用vpshufb在每个字节的两半上执行4位并行LUT，并且可以vpsadbw在水平方向上累加成每个元素的计数。 (模拟Ice Lake的AVX512 vpopcntq)