__builtin_ctz(0) 或 __builtin_clz(0) 的未定义程度如何？

Question

背景

长期以来， gcc 一直提供 许多内置的位旋转函数，特别是尾随和前导 0 位的数量（也适用于 long unsigned 和 long long unsigned ，它们有后缀 l 和 ll ）：

— 内置函数： int __builtin_clz (unsigned int x)

返回 x 中前导 0 位的数量，从最高有效位位置开始。如果 x 为 0，则结果未定义。

— 内置函数： int __builtin_ctz (unsigned int x)

返回 x 中尾随 0 位的数量，从最低有效位位置开始。如果 x 为 0，则结果未定义。

然而，在我测试的每个在线（免责声明：仅 x64）编译器上，结果是 clz(0) 和 ctz(0) 返回底层内置类型的位数，例如

#include <iostream>
#include <limits>

int main()
{
    // prints 32 32 32 on most systems
    std::cout << std::numeric_limits<unsigned>::digits << " " << __builtin_ctz(0) << " " << __builtin_clz(0);
}

活生生的例子。

尝试的解决方法

std=c++1y 模式中的最新 Clang SVN 主干使所有这些功能都放松了 C++14 constexpr ，这使得它们成为在 SFINAE 表达式中使用围绕 3 的包装函数模板的候选者 ctz / clz for unsigned , unsigned long , and unsigned long long

 template<class T> // wrapper class specialized for u, ul, ull (not shown)
constexpr int ctznz(T x) { return wrapper_class_around_builtin_ctz<T>()(x); }

// overload for platforms where ctznz returns size of underlying type
template<class T>
constexpr auto ctz(T x)
-> typename std::enable_if<ctznz(0) == std::numeric_limits<T>::digits, int>::type
{ return ctznz(x); }

// overload for platforms where ctznz does something else
template<class T>
constexpr auto ctz(T x)
-> typename std::enable_if<ctznz(0) != std::numeric_limits<T>::digits, int>::type
{ return x ? ctznz(x) : std::numeric_limits<T>::digits; }

这个黑客的好处是，为 ctz(0) 提供所需结果的平台可以省略一个额外的条件来测试 x==0 （这似乎是一个微优化，但是当你已经到内置位旋转函数的级别，它可以产生很大的不同）

问题

内置函数系列 clz(0) 和 ctz(0) 的未定义程度如何？

• 他们可以抛出 std::invalid_argument 异常吗？
• 对于 x64，它们对于当前的 gcc 发行版会返回底层类型的大小吗？
• ARM/x86 平台有什么不同吗（我无权测试这些平台）？
• 上述 SFINAE 技巧是分离此类平台的明确方法吗？

原文由 TemplateRex 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

不幸的是，即使 x86-64 实现也可能有所不同 - 来自英特尔的 指令集参考 BSF 和 BSR ，源操作数值为 (0) bced6b9485ee56d0040e73153f57 , 并设置 ZF （零标志）。因此，微架构或 AMD 和 Intel 之间的行为可能不一致。 （我相信 AMD 不会修改目的地。）

较新的 LZCNT 和 TZCNT 指令并不普遍。两者都只存在于 Haswell 架构（对于英特尔）。

原文由 Brett Hale 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

该值未定义的原因是它允许编译器使用结果未定义的处理器指令，而这些指令是获得答案的最快方式。

但重要的是要了解，不仅结果未定义；他们是不确定的。例如，根据英特尔的指令参考，指令返回当前时间的低 7 位是有效的。

这就是它变得有趣/危险的地方：编译器编写者可以利用这种情况来生成更小的代码。考虑一下您的代码的这个非模板专业化版本：

 using std::numeric_limits;
template<class T>
constexpr auto ctz(T x) {
  return ctznz(0) == numeric_limits<T>::digits || x != 0
       ? ctznz(x) : numeric_limits<T>::digits;
}

这适用于决定为 ctznz(0) 返回#bits 的处理器/编译器。但是在决定返回伪随机值的处理器/编译器中，编译器可能会决定“我可以为 ctznz(0) 返回任何我想要的内容，如果我返回#bits，代码会更小，所以我会” .然后代码最终总是调用 ctznz，即使它产生了错误的答案。

换句话说：编译器的未定义结果不能保证与运行程序的未定义结果一样是未定义的。

真的没有办法解决这个问题。如果必须使用 __builtin_clz，源操作数可能为零，则必须始终添加检查。

原文由 jorgbrown 发布，翻译遵循 CC BY-SA 3.0 许可协议