避免 bzhi(y, tzcnt(x)) 中不必要的 mov ecx, ecx 指令
Avoid unnecessary mov ecx, ecx instruction in bzhi(y, tzcnt(x))
我有一个位位置（它永远不会为零），使用 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 可以直接在 tzcnt 的输出上使用 bzhi 作为您的来源。所有编译器在某些情况下都会错过优化，但 GCC 和 clang 的情况往往比 MSVC 少。
（并且 GCC 在为 Haswell 调优时会小心地打破 the output dependency of tzcnt，以避免通过该错误依赖创建循环携带的依赖链的风险。不幸的是，GCC 仍然使用 -march=skylake 这样做tzcnt 没有假 dep，只有 popcnt 和 bsr/bsf "true" dep。）
英特尔将 _bzhi_u64 的第二个输入记录为 unsigned __int32 index。 （出于某种原因，您使用 static_cast 到 uint32_t 来明确这一点，但是删除显式强制转换没有帮助）。 IDK MSVC 如何定义内在函数或在内部处理它。
IDK 为什么 MSVC 要这样做；我想知道它是否在 MSVC 的 _bzhi_u64 内部逻辑内部零扩展到 64 位，它采用 32 位 C 输入但使用 64 位 asm 寄存器。 （tzcnt 的输出值范围是 0..64，所以这个零扩展在这种情况下是一个空操作）
屏蔽 popcnt：shift yyy 而不是屏蔽它
与 一样，将不需要的位移出而不是就地清零会更有效。 （虽然 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 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 微指令 = 与其他周围代码混合时，整体吞吐量非常好。
后端瓶颈：Intel CPU 上的端口 1（tzcnt 和 popcnt）为 2 微指令。 （端口 0 或端口 6 上的 shrx 运行s，作为单个 uop。启用 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
的低延迟替代方案
（但更多uops，前端吞吐量可能更差。后端执行端口压力收益取决于周围代码。）
BMI1 有一些 bithack 指令来执行诸如隔离最低设置位之类的操作，在 Intel 上所有 1 uop 具有单周期延迟。 （AMD Zen 运行将它们设为 2 微指令，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 微指令。）
最佳选择将取决于周围的代码，吞吐量或延迟是否是瓶颈。
如果您对许多连续存储的不同掩码执行此操作，SIMD 可能会有效。避免 tzcnt 意味着您可以使用需要几条指令的 bithack 来执行最低设置的隔离或掩码。例如blsi 是 (-SRC) bitwiseAND (SRC)，如 Intel 的 asm 手册的操作部分所述。 （查找位图表达式的方便位置。）blsmsk 是 (SRC-1) XOR (SRC)
SIMD popcnt可以用vpshufb在每个字节的两半上做4位并行LUT，你可以vpsadbw水平累加到每个元素的计数中。 （模拟 Ice Lake 的 AVX512 vpopcntq）
这是一个编译器的东西（截至 Visual C++ 2019 00435-60000-00000-AA388）。
MSVC 的 immintrin.h 定义
__int64 _bzhi_u64(unsigned __int64, unsigned int);
遵循英特尔的次优 intrinsic definition that contradicts command documentation（所有 bzhi 参数大小相同）。
clang 在 bmi2intrin.h
unsigned long long _bzhi_u64(unsigned long long __X, unsigned long long __Y)
因此没有必要触及您代码中的 _tzcnt_u64 结果。
我修补了 MSVC 的 immintrin.h - 但无济于事。伤心！因为 Peter 复杂的解决方法不适用于我的情况（lzcnt/bzhi，没有 popcnt）。
我有一个位位置（它永远不会为零），使用 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 可以直接在 tzcnt 的输出上使用 bzhi 作为您的来源。所有编译器在某些情况下都会错过优化，但 GCC 和 clang 的情况往往比 MSVC 少。
（并且 GCC 在为 Haswell 调优时会小心地打破 the output dependency of tzcnt，以避免通过该错误依赖创建循环携带的依赖链的风险。不幸的是，GCC 仍然使用 -march=skylake 这样做tzcnt 没有假 dep，只有 popcnt 和 bsr/bsf "true" dep。）
英特尔将 _bzhi_u64 的第二个输入记录为 unsigned __int32 index。 （出于某种原因，您使用 static_cast 到 uint32_t 来明确这一点，但是删除显式强制转换没有帮助）。 IDK MSVC 如何定义内在函数或在内部处理它。
IDK 为什么 MSVC 要这样做；我想知道它是否在 MSVC 的 _bzhi_u64 内部逻辑内部零扩展到 64 位，它采用 32 位 C 输入但使用 64 位 asm 寄存器。 （tzcnt 的输出值范围是 0..64，所以这个零扩展在这种情况下是一个空操作）
屏蔽 popcnt：shift yyy 而不是屏蔽它
与 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 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 微指令 = 与其他周围代码混合时，整体吞吐量非常好。
后端瓶颈：Intel CPU 上的端口 1（tzcnt 和 popcnt）为 2 微指令。 （端口 0 或端口 6 上的 shrx 运行s，作为单个 uop。启用 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
的低延迟替代方案
（但更多uops，前端吞吐量可能更差。后端执行端口压力收益取决于周围代码。）
BMI1 有一些 bithack 指令来执行诸如隔离最低设置位之类的操作，在 Intel 上所有 1 uop 具有单周期延迟。 （AMD Zen 运行将它们设为 2 微指令，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 微指令。）
最佳选择将取决于周围的代码，吞吐量或延迟是否是瓶颈。
如果您对许多连续存储的不同掩码执行此操作，SIMD 可能会有效。避免 tzcnt 意味着您可以使用需要几条指令的 bithack 来执行最低设置的隔离或掩码。例如blsi 是 (-SRC) bitwiseAND (SRC)，如 Intel 的 asm 手册的操作部分所述。 （查找位图表达式的方便位置。）blsmsk 是 (SRC-1) XOR (SRC)
SIMD popcnt可以用vpshufb在每个字节的两半上做4位并行LUT，你可以vpsadbw水平累加到每个元素的计数中。 （模拟 Ice Lake 的 AVX512 vpopcntq）
这是一个编译器的东西（截至 Visual C++ 2019 00435-60000-00000-AA388）。
MSVC 的 immintrin.h 定义
__int64 _bzhi_u64(unsigned __int64, unsigned int);
遵循英特尔的次优 intrinsic definition that contradicts command documentation（所有 bzhi 参数大小相同）。
clang 在 bmi2intrin.h
unsigned long long _bzhi_u64(unsigned long long __X, unsigned long long __Y)
因此没有必要触及您代码中的 _tzcnt_u64 结果。
我修补了 MSVC 的 immintrin.h - 但无济于事。伤心！因为 Peter 复杂的解决方法不适用于我的情况（lzcnt/bzhi，没有 popcnt）。