如何计算 mac M1 和 x86-64 上的前导零？

Question

最初我尝试了 lzcnt，但在 mac 上似乎不起作用。我正在与使用苹果 M1 CPU 的人一起工作，它是 ARM64v8.4

在这个 arm document 列表中，似乎 clz 支持使用 0

的 ARM 8

CLZ Xd, Xm
Count Leading Zeros (64-bit): sets Xd to the number of binary zeros at the most significant end of Xm. The result will be in the range 0 to 64 inclusive.

我们最初支持的CPU是x86-64，它有_lzcnt_u64

如果值为 0，两条指令都显示为 return64。具体来说，ARM 上的“0 到 64 inclusive”和 intel site 也建议这样做（并通过我的代码确认）

但是 GCC 表示如下

Built-in Function: int __builtin_clzll (unsigned long long)

Similar to __builtin_clz, except the argument type is unsigned long long.

我可以安全地使用 0 还是这个内置函数使用不同的指令？我尝试了 clang 和消毒剂停止程序并告诉我这是一个令我惊讶的问题。

如果我像这两条指令一样传入0，我想得到64时应该如何得到前导零计数

Answer 1

如果 C++20 功能可用，std::countl_zero<T> solves the problem, and it's up to compiler devs to implement it in a way that compiles efficiently even for an input of zero. (In which case it's required to return the number of value-bits in the integer type you passed, unlike __builtin_clzll)

这在理论上很棒，但不幸的是，他们在使用实际内置函数时遇到了同样的问题。 libstdc++ 只是或多或少地使用 x ? __builtin_clzll(x) : 64，GCC 不会优化它，即使有可用的硬件指令为 0 的输入生成 64。（参见下面的 C++ 和 asm 代码块。）

所以在实践中 std::countl_zero<uint64_t> 总是使用 GCC 编译成多条指令，即使在像 ARM64 或 x86-64 这样的机器上，即使 lzcnt 在编译时已知可用（-mlzcnt 或 -mbmi）。 clang 确实优化了三元。

__builtin_clzll 将在 x86 上编译为 63-bsr(x) 如果您不使用包含 BMI1 的 -march= 选项（或者对于某些 AMD，至少是没有 BMI1 其余部分的 LZCNT ).对于输入 0，BSR 保留其目的地不变，不产生 -1 或其他东西。 https://www.felixcloutier.com/x86/bsr（这可能是以这种方式定义内置函数的很大一部分动机，因此它可以编译为单个 BSR 或 BSF 指令，而无需条件分支或 x86 上的 cmov 早在 lzcnt 存在之前。一些用例不需要将它与零一起使用。）

这里的目标是什么，可移植的 GNU C++？或者针对具有特定选项的几个编译目标完美优化的 asm？

您可以尝试 x ? __builtin_clzll(x) : 64 并希望 GCC 在可用时将其优化为 x86-64 lzcnt。 clang 做这个优化，但不幸的是 GCC11 没有。 (Godbolt)

unsigned clz(unsigned long long x) {
    return x ? __builtin_clzll(x) : 64;
}

顺便说一句，libstdc++ 的 std::countl_zero 编译方式相同，大概是因为它或多或少是这样写的。（可能有一些 std::numeric_limits<T> 的东西而不是硬编码的 64）。

# x86-64  clang 13 -O3 -march=haswell
clz(unsigned long long):
        lzcnt   rax, rdi
        ret

x86-64 GCC 11.2 -O3 -march=haswell
clz(unsigned long long):
        xor     edx, edx          # break output dependency for lzcnt on Intel pre-SKL
        mov     eax, 64
        lzcnt   rdx, rdi
        test    rdi, rdi
        cmovne  eax, edx          # actually do the ternary
        ret

ARM64 的情况相同：clang 将冗余选择操作优化为 clz，GCC 没有：

# ARM64 gcc11.2 -O3 -march=cortex-a53
clz(unsigned long long):
        cmp     x0, 0
        clz     x0, x0
        mov     w1, 64
        csel    w0, w0, w1, ne
        ret

在可用时明确使用 lzcnt：

#ifdef __BMI__
#include <immintrin.h>
unsigned clz_lzcnt(unsigned long long x) {
    return _lzcnt_u64(x);
}
#endif

# x86-64 GCC11 -O3 -march=haswell
clz_lzcnt(unsigned long long):
        xor     eax, eax
        lzcnt   rax, rdi
        ret

（所以你真的想在 #ifdef 另一个函数中使用这个 ，并使用 #else 使用三元作为后备。）

如何计算 mac M1 和 x86-64 上的前导零？

How do I count leading zeros on both mac M1 and x86-64?

c++

bit-manipulation

x86-64

arm64

apple-m1

在可用时明确使用 lzcnt：