33

Background

For a long time, gcc has been providing a number of builtin bit-twiddling functions, in particular the number of trailing and leading 0-bits (also for long unsigned and long long unsigned, which have suffixes l and ll):

— Built-in Function: int __builtin_clz (unsigned int x)

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

— Built-in Function: int __builtin_ctz (unsigned int x)

Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.

On every online (disclaimer: only x64) compiler I tested, however, the result has been that both clz(0) and ctz(0) return the number of bits of the underlying builtin type, e.g.

#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);    
}

Live Example.

Attempted workaround

The latest Clang SVN trunk in std=c++1y mode has made all these functions relaxed C++14 constexpr, which makes them candidates to use in a SFINAE expression for a wrapper function template around the 3 ctz / clz builtins 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; }

The gain from this hack is that platforms that give the required result for ctz(0) can omit an extra conditional to test for x==0 (which might seem a micro-optimization, but when you are already down to the level of builtin bit-twiddling functions, it can make a big difference)

Questions

How undefined is the family of builtin functions clz(0) and ctz(0)?

  • can they throw an std::invalid_argument exception?
  • for x64, will they for the current gcc distro return the size of the underyling type?
  • are the ARM/x86 platforms any different (I have no access to that to test those)?
  • is the above SFINAE trick a well-defined way to separate such platforms?
1
  • 1
    If you can get your hands on the file longlong.h in gcc/gmp/glibc, look for the macro COUNT_LEADING_ZEROS_0... Commented Nov 7, 2014 at 20:19

3 Answers 3

21

Unfortunately, even x86-64 implementations can differ - from Intel's instruction set reference,BSF and BSR, with a source operand value of (0), leaves the destination undefined, and sets the ZF (zero flag). So the behaviour may not be consistent between micro-architectures or, say, AMD and Intel. (I believe AMD leaves the destination unmodified.)

The newer LZCNT and TZCNT instructions are not ubiquitous. Both are present only as of the Haswell architecture (for Intel).

6
  • Tnx for this answer. But does "undefined" mean that it is platform-dependent, and that at least every ctz(0) call is deterministic and always gives the same answer on that platform (i.e. not undefined behavior) so that my SFINAE hack actually makes sense? Commented Oct 23, 2013 at 9:41
  • 3
    While only AMD documents bsr/bsf with a zero source as not modifying the dest, every Intel processor I've ever been able to test (or hear about) also does that. Intel just doesn't document it that way.
    – user555045
    Commented Oct 24, 2013 at 19:32
  • 2
    @harold - which means Intel is not bound by this behaviour in future architectures - no matter how unlikely such a change may be. For others - please don't take shortcuts with 'undocumented' instruction semantics.
    – Brett Hale
    Commented Mar 26, 2015 at 2:06
  • 3
    @BrettHale This behaviour has been stable for literally longer than I've been alive. It's not going to change. Intel's public documentation is just incomplete (or wrong, or both), as usual. More likely, it is actually the defined behaviour (as written down in some internal documents) which AMD copied, but Intel just never put it in their public spec. If they were actually going to change it, they would have done so back when they made their first OoO processor, when they had the opportunity to get rid of a dependency.
    – user555045
    Commented Mar 26, 2015 at 6:04
  • 1
    @BrettHale Intels documentation really is full of errors though, it is objectively wrong already, just maybe not in this case - but how are we to know? It cannot be trusted, and it certainly isn't the Word of God kind of spec.
    – user555045
    Commented Mar 26, 2015 at 15:53
18

The reason the value is undefined is that it allows the compiler to use processor instructions for which the result is undefined, when those instructions are the fastest way to get an answer.

But it's important to understand that not only are the results undefined; they are undeterministic. It's valid, given Intel's instruction reference, for the instruction to return the low 7 bits of the current time, for example.

And here's where it gets interesting/dangerous: the compiler writer can take advantage of this situation, to produce smaller code. Consider this non-template-specialization version of your code:

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;
}

This works well on a processor/compiler that have decided to return #bits for ctznz(0). But un a processor/compiler that decide to return pseudo-random values, the compiler may decide "I'm allowed to return whatever I want for ctznz(0), and the code is smaller if I return #bits, so I will". Then the code ends up calling ctznz all the time, even though it produces the wrong answer.

To put it another way: the compiler's undefined results are not guaranteed to be undefined in the same way that the running program's undefined results are.

There really is no way around this. If you must use __builtin_clz, with a source operand that might be zero, you have to add the check, all the time.

6

C++20 update: countl_zero, countr_zero, countl_one, and countr_one are now standard, and in <bit>. They will generally call the same asm as the intrinsic.

So, once you are on C++20, don't use the intrinsics.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.