__builtin_popcountg

Looking at https://en.cppreference.com/cpp/utility/bitset/count, I was intrigued to see popcount mentioned in the “See also” section. Handy.

That made me curious to see how the stdlibs choose to implement it.

Here it is for Clang: libcxx/include/__bit/popcount.h

template <class _Tp>
[[__nodiscard__]] _LIBCPP_CONSTEXPR int __popcount(_Tp __t) _NOEXCEPT {
  return __builtin_popcountg(__t);
}

#if _LIBCPP_STD_VER >= 20

template <__unsigned_integer _Tp>
[[nodiscard]] constexpr int popcount(_Tp __t) noexcept {
  return std::__popcount(__t);
}

#endif

For gcc: libstdc++-v3/include/std/bit

  template<__unsigned_integer _Tp>
    constexpr int
    popcount(_Tp __x) noexcept
    { return std::__popcount(__x); }
...
#if _GLIBCXX_USE_BUILTIN_TRAIT(__builtin_popcountg)
  template<typename _Tp>
    constexpr int
    __popcount(_Tp __x) noexcept
    {
      return __builtin_popcountg(__x);
    }
#else
  template<typename _Tp>
    _GLIBCXX14_CONSTEXPR int
    __popcount(_Tp __x) noexcept
    {
      using __gnu_cxx::__int_traits;
      constexpr auto _Nd = __int_traits<_Tp>::__digits;

      constexpr auto _Nd_ull = __int_traits<unsigned long long>::__digits;
      constexpr auto _Nd_ul = __int_traits<unsigned long>::__digits;
      constexpr auto _Nd_u = __int_traits<unsigned>::__digits;

      if constexpr (_Nd <= _Nd_u)
	return __builtin_popcount(__x);
      else if constexpr (_Nd <= _Nd_ul)
	return __builtin_popcountl(__x);
      else if constexpr (_Nd <= _Nd_ull)
	return __builtin_popcountll(__x);
      else // (_Nd > _Nd_ull)
	{
	  static_assert(_Nd <= (2 * _Nd_ull),
			"Maximum supported integer size is 128-bit");

	  constexpr auto __max_ull = __int_traits<unsigned long long>::__max;
	  unsigned long long __low = __x & __max_ull;
	  unsigned long long __high = __x >> _Nd_ull;
	  return __builtin_popcountll(__low) + __builtin_popcountll(__high);
	}
    }
#endif

So, there’s at least one configuration where they end up both calling something called __builtin_popcountg. What are these __builtin things?

• https://gcc.gnu.org/onlinedocs/gcc/Built-in-Functions.html “GCC provides a very large number of implicitly-declared built-in functions that are typically inlined by the compiler”
• https://clang.llvm.org/docs/LanguageExtensions.html#builtin-functions “Clang supports a number of builtin library functions with the same syntax as GCC, including things like __builtin_nan, …, etc.”

Can we call it directly?

// bits.cc
#include <iostream>
#include <string>

int main(int argc, char** argv) {
  if (argc != 2) {
    return 1;
  }
  std::cout << __builtin_popcountg(std::stoull(argv[1])) << '\n';
}

Compile and run:

% g++ --version
Apple clang version 17.0.0 (clang-1700.6.3.2)
...
% g++ bits.cc
% ./a.out 255
8

That’s fun. Looking at the assembly for a simpler version of this:

// just_the_bits.cc
unsigned long count_int_bits(unsigned int x) {
  return __builtin_popcountg(x);
}

% g++ -S just_the_bits.cc
% cat just_the_bits.s 
	.section	__TEXT,__text,regular,pure_instructions
	.build_version macos, 26, 0	sdk_version 26, 2
	.globl	__Z14count_int_bitsj            ; -- Begin function _Z14count_int_bitsj
	.p2align	2
__Z14count_int_bitsj:                   ; @_Z14count_int_bitsj
	.cfi_startproc

	sub	sp, sp, #16
	.cfi_def_cfa_offset 16
	str	w0, [sp, #12]
	ldr	w8, [sp, #12]
	fmov	s0, w8

	cnt.8b	v0, v0
	uaddlv.8b	h0, v0

	smov.s	x0, v0[0]
	add	sp, sp, #16
	ret
	.cfi_endproc
.subsections_via_symbols

Just going off the name, “cnt.8b” got my attention. Searching for it led to this article about counting bits from Kelly Norton, which has some details on what’s going on here:

The CNT instruction on arm64 is a population count instruction. It is a little strange in that it’s a SIMD instruction so you have to move the value from a general register into a vector register and also sum across the vector register.

https://kellegous.com/j/2023/07/24/counting-bits/

So, I guess “fmov” (Floating-point Move register without conversion) is doing the move to the SIMD register s0, “cnt.8b” (Population Count per byte) counts the bits, “uaddlv.8b” (Unsigned sum long across vector) sums up the count, and “smov.s” (Signed Move vector element to general-purpose register) gets the result back to a non-SIMD register.

Searching for more info on the registers also led me to this article, which I’ll hope to return to sometime: Code in ARM Assembly: Registers explained.