inline-asm popcnt in SplitList.h raises SIGILL on CPUs without POPCNT #287

Summary

Since TreeTools 2.2.0, count_bits() in inst/include/TreeTools/SplitList.h executes the x86 popcnt instruction through inline assembly on every x86-64 build:

// Hardware POPCNT: available on all x86-64 since 2008 (Nehalem / Barcelona).
// Inline asm emits the instruction directly, without requiring -mpopcnt.
#if (defined(__GNUC__) || defined(__clang__)) && defined(__x86_64__)
  inline int32 count_bits(splitbit x) {
    uint64_t result;
    __asm__ ("popcnt %1, %0" : "=r" (result) : "r" (x));
    return static_cast<int32>(result);
  }

On a CPU that does not advertise POPCNT the instruction faults, and R reports

*** caught illegal operation ***

and aborts the session. Because the header is also pulled in via LinkingTo: TreeTools, the same crash appears in packages that include SplitList.h, currently TreeDist, TreeSearch and ConsTree. TreeDist additionally carries its own copy of the same asm in src/hmi.cpp.

Where this arises

POPCNT is not part of baseline x86-64; it belongs to the x86-64-v2 level together with SSE4.2. That is why GCC and Clang won't emit it without -mpopcnt or -march=x86-64-v2: the default target doesn't promise it. The inline asm bypasses that check rather than satisfying it.

Physical CPUs without POPCNT are rare now (Intel Core 2 and Penryn, and Atom before Silvermont in 2013), but virtual CPUs without it are common, because hypervisors expose a generic CPU model unless told otherwise. QEMU's default x86-64 model, qemu64, is a case in point: it advertises SSE3 but neither SSE4.2 nor POPCNT, whatever the host supports. A guest started with

qemu-system-x86_64 -cpu qemu64 ...

shows no popcnt flag in /proc/cpuinfo, and any code that executes the instruction dies with SIGILL. This is the same reason RHEL 9 and its derivatives, which require x86-64-v2, refuse to boot under qemu64. Build farms, CI runners and check servers that run as VMs with a default or conservative CPU model are therefore exposed, even on modern hardware. CRAN's own check machines pass the affected packages, so the instruction is fine wherever POPCNT exists; the Rcpp project's reverse-dependency runners, which are VMs, started failing TreeTools with this signal with the 2.2.0 release and fail TreeDist, TreeSearch and ConsTree the same way.

Suggested fix

Keep the fast path but dispatch on the CPU at runtime, which GCC and Clang support without extra flags:

#if (defined(__GNUC__) || defined(__clang__)) && defined(__x86_64__)
  // POPCNT is not part of baseline x86-64, so the compiler will only emit the
  // instruction for code it has been told may use it. The two functions below
  // call the same builtin; what differs is the target the compiler assumes
  // when it translates each one.

  // Compiled with POPCNT enabled: __builtin_popcountll becomes the single
  // POPCNT instruction (the same code the inline asm produced). Only call
  // this when the CPU has been checked to support it.
  __attribute__((target("popcnt")))
  inline int32 count_bits_hw(splitbit x) {
    return static_cast<int32>(__builtin_popcountll(x));
  }

  // Compiled for baseline x86-64: the same builtin becomes a portable
  // bit-counting sequence (or a libgcc call) that runs on any CPU.
  inline int32 count_bits_sw(splitbit x) {
    return static_cast<int32>(__builtin_popcountll(x));
  }

  // Runtime check of the CPUID feature flag. __builtin_cpu_init() is cheap
  // and makes the check safe regardless of when it is first called.
  inline bool cpu_has_popcnt() {
    __builtin_cpu_init();
    return __builtin_cpu_supports("popcnt");
  }

  // Dispatch once per process, then take the fast path on CPUs that have it.
  inline int32 count_bits(splitbit x) {
    static const bool has_popcnt = cpu_has_popcnt();
    return has_popcnt ? count_bits_hw(x) : count_bits_sw(x);
  }

Under target("popcnt") the builtin compiles to the single instruction, exactly as the asm did; without it, GCC emits a call to libgcc's __popcountdi2 and Clang inlines a bit-twiddling sequence. If the per-call branch is a concern in the hot loops, the flag can be hoisted into the SplitList constructor or a function pointer selected once. Alternatively, __builtin_popcountll alone would restore the pre-2.2.0 behaviour (which was std::popcount and had the same fallback), at the cost of the hardware instruction on default builds.

This needs no platform-specific handling: R on Windows builds with Rtools (mingw-w64 GCC), which takes the same __GNUC__ && __x86_64__ branch and supports both target("popcnt") and __builtin_cpu_supports. The _MSC_VER branch is never reached by R builds; for completeness, Microsoft documents __popcnt64 as faulting on CPUs without POPCNT as well.

A PR implementing the dispatch is at #288. Happy to do the same for hmi.cpp in TreeDist, or to switch to whichever approach you prefer.