编译器优化：识别 popcount 模式

人口计数（population count）—— 统计一个整数中被置 1 的位的数量 —— 是数据压缩、加密、国际象棋引擎、稀疏矩阵表示和错误检测中都会用到的基本操作。手写实现足够简单，但现代编译器能识别手写的版本，并在目标架构支持时用一条专门的 CPU 指令完全替换它。

本文是 Matt Godbolt 的《Advent of Compiler Optimisations 2025》系列中的一篇。

这个操作

一个值的 population count 是其中 1 的比特数。例如：

0b11010100 = 十进制 212 → 4 个 1

这也叫作这个值的 Hamming weight。

一段紧凑的 C 实现

不用查找表来数 1 的高效办法之一，是利用一个事实：value & (value - 1) 能清掉最低的那个 1：

int popcount(uint64_t value) {
    int count = 0;
    while (value) {
        value &= value - 1;  // 清除最低位的 1
        count++;
    }
    return count;
}

循环恰好运行”有多少个 1 就跑多少次”。对稀疏值（很少的 1）来说，它比逐位扫描快；对稠密值来说它更慢，但作为通用实现，它清晰、正确。

编译器做了什么

针对基准（较老）目标

在针对较老或通用目标（比如 -march=nocona）编译时，编译器会生成一个直接实现该算法的循环：

.L3:
    lea   rax, [rdi - 1]
    add   edx, 1
    and   rdi, rax
    jne   .L3

这与预期一致：循环体计算 value & (value - 1)、递增计数器，直到 value 为 0。

针对现代目标

在针对包含 POPCNT 指令的架构编译时（Intel CPU 自 Nehalem/Westmere 起，约 2010 年起就有），整个函数坍缩成一条指令：

popcnt rax, rdi

编译器识别出这个循环模式，证明它在计算 population count，把整个函数替换为硬件原语。一个周期取代了 O(n) 次迭代。

这是编译器层面的模式匹配：优化器不仅仅是内联和化简 —— 它认出一种算法模式，用一个语义等价但快得多的硬件操作替换之。

启用这个优化

关键是指定一个包含 POPCNT 的目标架构。在 GCC 和 Clang 中：

-march=westmere    # 或任何足够新的 x86 目标
-mpopcnt           # 只显式启用 POPCNT 指令
-march=native      # 使用构建机所支持的全部指令

没有这些标志时，编译器会保守地生成循环，因为它不能假设硬件有 popcnt。

标准库替代方案

C++20 提供了可移植、能表达意图的替代方案：

#include <bit>
int count = std::popcount(x);

它直接表达了这个操作，并在每个目标上都保证使用最佳的可用实现。在支持 POPCNT 的 x86 上，它编译成同样的一条指令；在 ARM 上使用 cnt 指令（工作在 SIMD 寄存器上）；在 RISC-V 上，当可用时使用 cpop 指令。

对新代码来说，std::popcount 优于手写循环：它更清晰、可移植，编译器也不会错过对它的优化。

一个微架构小坑：假依赖（false dependency）

在某些 Intel CPU 上（特别是 Sandy Bridge 和 Ivy Bridge），popcnt 指令有一个硬件 bug：输出寄存器看起来依赖自身之前的值，尽管它是无条件被写入的。这被称为假依赖，可能导致不必要的流水线停顿。

针对这些架构的编译器会在 popcnt 前插入一条 xor 来打破依赖：

xor   eax, eax    ; 打破对 eax 的假依赖
popcnt eax, edi

这是一次透明的、自动的修复。开发者无需了解这个微架构小坑 —— 编译器针对受影响的 CPU 会自动处理。

小结

编译器的模式识别不只限于代数化简和循环变换，它能扩展到识别众所周知的算法、把它们替换成硬件原语。popcount 这个例子很清晰：一个正确、地道的已知操作实现，在目标硬件支持时会被整体替换为一条指令。

对新代码，优先使用 std::popcount。对已有的使用”清低位”循环的代码，指定合适的 -march 标志，然后在 Compiler Explorer 中验证优化是否触发。如果想在不牺牲性能的前提下获得最大可移植性，交给标准库。