__builtin_ctz(0)或__builtin_clz(0)的未定义程度有多严重？

Question

背景

长期以来，gcc一直提供了许多内置的位操作函数，特别是用于计算前导和末尾0位数的函数（同样适用于带有后缀l和ll的long unsigned和long long unsigned）：

— 内置函数：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 trunk已经将所有这些函数放宽到了C++14 constexpr，这使它们成为了用于SFINAE表达式的候选包装函数模板的函数，这些表达式环绕着3个unsigned、unsigned long和unsigned long long的ctz/clz内建函数。

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 distro是否会返回底层类型的大小？
• ARM/x86平台有什么不同（我无法访问以测试）？
• 上述SFINAE技巧是区分这些平台的明确定义方法吗？

- TemplateRex

---

如果你能够获取到gcc/gmp/glibc中的文件longlong.h，请查找宏COUNT_LEADING_ZEROS_0... - Marc Glisse

Answer 1

很遗憾，即使是x86-64的实现也可能存在差异 - 根据英特尔的指令集参考，BSF和BSR对源操作数为(0)时，目标操作数的值不确定，并设置了ZF（零标志）。

因此，微架构或者说AMD和英特尔之间的行为可能不一致。（我相信AMD会让目标操作数保持不变。）

新的LZCNT和TZCNT指令并不是普及的。它们只在Haswell架构（对于英特尔而言）才有。

- Brett Hale

---

谢谢您的回答。但是，“undefined”是否意味着它依赖于平台，并且至少每个ctz(0)调用在该平台上都是确定性的，并且始终给出相同的答案（即不是未定义行为），以便我的SFINAE hack实际上是有意义的？ - TemplateRex

虽然只有 AMD 的文档指出在源为零时 bsr/bsf 不会修改目标，但我测试过或听说过的所有 Intel 处理器也是这样做的。只是 Intel 没有以这种方式记录它。 - harold

@harold - 这意味着英特尔在未来架构中不受此行为的限制，无论这种更改有多么不可能。对于其他人，请不要使用“未记录”的指令语义捷径。 - Brett Hale

@BrettHale 这种行为已经稳定存在比我活得还长的时间了，它不会改变。像往常一样，英特尔的公共文档只是不完整（或错误、或两者都有）。更可能的是，这实际上是已定义的行为（在一些内部文件中写下来的），AMD 复制了这个行为，但英特尔从未将其放入他们的公共规范中。如果他们真的打算改变它，他们早在制造第一个乱序处理器时就已经这样做了，那个时候他们有机会摆脱这种依赖关系。 - harold

@BrettHale，英特尔的文档确实充满错误。它已经在客观上是错误的，也许在这种情况下不是，但我们怎么知道呢？它是不可信的，肯定不是神的话规格。 - harold

@harold 在这种情况下，“未定义”是最糟糕的事情之一。无论英特尔的文档是否与其产品一致，不同制造商的底层实现仍然不同。据我所知，至少有一个（既不是英特尔也不是AMD）不同意遵循“内部文件”，因为他们认为公共文件更可取。BSF / BSR和LZCNT / TZCNT走不同的路线。 - FrankHB

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

Answer 3

C++20更新： countl_zero，countr_zero，countl_one和countr_one现在已成为标准，并位于中。它们通常会调用与内置函数相同的汇编代码。 因此，一旦您使用C++20，请不要使用内置函数。

- Glenn Teitelbaum