未定义的是__builtin_ctz(0)还是__builtin_clz(0)？

Question

背景

很长一段时间,gcc一直在提供许多内置的bit-twiddling函数,特别是尾随和前导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,则结果未定义.

在每一个在线(免责声明:仅64位)编译器,我测试,然而,结果是,无论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);    
}

实例.

尝试过的解决方法

在最新的锵SVN主干std=c++1y模式取得了所有这些功能放宽C++ 14 constexpr,这使得它们的候选在SFINAE表达式以用于围绕3包装函数模板ctz/ clz对建宏unsigned,unsigned long和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; }

这个hack的好处是,提供所需结果的平台ctz(0)可以省略额外的条件来测试x==0(这可能看起来像是一个微优化,但是当你已经达到了内置的bit-twiddling函数的水平时,它可以使一个很大的区别)

问题

如何undefined是内置函数的家人clz(0)和ctz(0)？

• 他们会抛出std::invalid_argument异常吗？
• 对于x64,它们是否会为当前的gcc发行版返回底层类型的大小？
• ARM/x86平台是否有任何不同(我无权访问它们)？
• 上面的SFINAE技巧是一种明确定义这种平台的方法吗？

Answer 1

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

但重要的是要理解不仅结果不确定; 他们是不确定的.例如,在给出Intel的指令参考时,它对于返回当前时间的低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,源操作数可能为零,则必须始终添加检查.

Answer 2

不幸的是,即使x86-64实现也可能与英特尔的指令集引用不同,BSF并且BSR,如果源操作数值为(0),则保留目标未定义,并设置ZF(零标志).因此,微架构或AMD和英特尔之间的行为可能不一致.(我相信AMD不会修改目的地.)

新的LZCNT和TZCNT指示并不是无处不在.两者都只出现在Haswell架构中(针对英特尔).

Answer 3

C++20 更新：countl_zero、countr_zero、countl_one 和 countr_one 现在已成为标准，并且在<bit>. 他们通常会调用与内在函数相同的汇编语言。

因此，一旦您使用 C++20，就不要使用内部函数。