c++ - 避免在bzhi(y,tzcnt(x))中使用不必要的mov ecx,ecx指令

标签 c++ assembly visual-c++ bit-manipulation compiler-optimization

我有一个位位置(永远不会为零),它是通过使用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可能会有所不同。

有什么办法可以避免它,或者这是编译器吗?

最佳答案

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

(而且,GCC在调整Haswell时要小心地打破the output dependency of tzcnt ,以避免通过该虚假依赖关系创建循环承载的依赖链的风险。不幸的是,GCC仍然使用-march=skylake来做到这一点,而tzcnt并没有假的dep,只有popcntbsr/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避免了创建掩码的开销,所以这只是盈亏平衡,模差异,执行端口bzhishrx可以在这些端口上运行。)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)

    关于c++ - 避免在bzhi(y,tzcnt(x))中使用不必要的mov ecx,ecx指令,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61986529/

    相关文章:

    c++ - Qt客户端服务器应用程序 “send image”出现问题

    c++ - 使用jsonCpp库从C++中的文件解析json时出错

    c++ - 头文件中的错误C2719-不使用STL:vector

    c++ - 与此汇编代码混淆

    c - "functions"是 x86 硬件的基本部分吗?

    caching - 直接映射缓存示例

    c++ - MFC 中的非动态文档/ View 架构使用

    c++ - 为什么在GCC/MSVS的stdlib中两次调用此自定义分配器的析构函数

    C++:函数调用错误:标识符 "name"未定义,何时已定义?

    windows - 通过 INPUT 结构发送 Ctrl Alt Del 不起作用?