当 -mavx2 开启时，为 __builtin_popcnt 生成了臃肿的代码
Bloated code generated for __builtin_popcnt when -mavx2 is on
对于这样的函数，clang（有时 gcc 在某些我无法最低限度重现的上下文中）似乎在 -mavx2 开关打开时生成臃肿的代码。
unsigned count(uint64_t *f) {
unsigned c = 0;
for (unsigned i = 0; i < 1024; ++i) {
if (sizeof(long) >= 8) {
c += __builtin_popcountl(f[i]);
} else {
c += __builtin_popcountll(f[i]);
}
}
return c;
}
这来自 gcc，非常简单。
count:
lea rcx, [rdi+8192]
xor eax, eax
.L2:
xor edx, edx
add rdi, 8
popcnt rdx, QWORD PTR [rdi-8]
add eax, edx
cmp rcx, rdi
jne .L2
ret
但是 clang 决定在 -mavx2 开启时产生这种巨大的膨胀。 -mpopcnt 也已设置。
.LCPI0_0:
.zero 32,15
.LCPI0_1:
.byte 0 # 0x0
.byte 1 # 0x1
.byte 1 # 0x1
.byte 2 # 0x2
.byte 1 # 0x1
.byte 2 # 0x2
.byte 2 # 0x2
.byte 3 # 0x3
.byte 1 # 0x1
.byte 2 # 0x2
.byte 2 # 0x2
.byte 3 # 0x3
.byte 2 # 0x2
.byte 3 # 0x3
.byte 3 # 0x3
.byte 4 # 0x4
.byte 0 # 0x0
.byte 1 # 0x1
.byte 1 # 0x1
.byte 2 # 0x2
.byte 1 # 0x1
.byte 2 # 0x2
.byte 2 # 0x2
.byte 3 # 0x3
.byte 1 # 0x1
.byte 2 # 0x2
.byte 2 # 0x2
.byte 3 # 0x3
.byte 2 # 0x2
.byte 3 # 0x3
.byte 3 # 0x3
.byte 4 # 0x4
count: # @count
vpxor xmm0, xmm0, xmm0
xor eax, eax
vmovdqa ymm1, ymmword ptr [rip + .LCPI0_0] # ymm1 = [15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15]
vmovdqa ymm2, ymmword ptr [rip + .LCPI0_1] # ymm2 = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
vpxor xmm12, xmm12, xmm12
vpxor xmm4, xmm4, xmm4
vpxor xmm5, xmm5, xmm5
vpxor xmm6, xmm6, xmm6
.LBB0_1: # =>This Inner Loop Header: Depth=1
vmovdqu ymm7, ymmword ptr [rdi + 8*rax]
vmovdqu ymm8, ymmword ptr [rdi + 8*rax + 32]
vmovdqu ymm9, ymmword ptr [rdi + 8*rax + 64]
vmovdqu ymm10, ymmword ptr [rdi + 8*rax + 96]
vpand ymm11, ymm7, ymm1
vpshufb ymm11, ymm2, ymm11
vpsrlw ymm7, ymm7, 4
vpand ymm7, ymm7, ymm1
vpshufb ymm7, ymm2, ymm7
vpaddb ymm7, ymm11, ymm7
vpsadbw ymm7, ymm12, ymm7
vpand ymm11, ymm8, ymm1
vpshufb ymm11, ymm2, ymm11
vpsrlw ymm8, ymm8, 4
vpand ymm8, ymm8, ymm1
vpshufb ymm8, ymm2, ymm8
vpaddb ymm8, ymm8, ymm11
vpsadbw ymm8, ymm8, ymm12
vpand ymm11, ymm9, ymm1
vpshufb ymm11, ymm2, ymm11
vpsrlw ymm9, ymm9, 4
vpand ymm9, ymm9, ymm1
vpshufb ymm9, ymm2, ymm9
vpaddb ymm9, ymm9, ymm11
vpsadbw ymm9, ymm9, ymm12
vpand ymm11, ymm10, ymm1
vpshufb ymm11, ymm2, ymm11
vpsrlw ymm10, ymm10, 4
vpand ymm10, ymm10, ymm1
vpshufb ymm10, ymm2, ymm10
vpaddb ymm10, ymm10, ymm11
vpsadbw ymm10, ymm10, ymm12
vextracti128 xmm3, ymm7, 1
vpackusdw xmm3, xmm7, xmm3
vpaddd xmm0, xmm0, xmm3
vextracti128 xmm3, ymm8, 1
vpackusdw xmm3, xmm8, xmm3
vpaddd xmm4, xmm4, xmm3
vextracti128 xmm3, ymm9, 1
vpackusdw xmm3, xmm9, xmm3
vpaddd xmm5, xmm5, xmm3
vextracti128 xmm3, ymm10, 1
vpackusdw xmm3, xmm10, xmm3
vpaddd xmm6, xmm6, xmm3
add rax, 16
cmp rax, 1024
jne .LBB0_1
vpaddd xmm0, xmm4, xmm0
vpaddd xmm0, xmm5, xmm0
vpaddd xmm0, xmm6, xmm0
vpshufd xmm1, xmm0, 238 # xmm1 = xmm0[2,3,2,3]
vpaddd xmm0, xmm0, xmm1
vpshufd xmm1, xmm0, 85 # xmm1 = xmm0[1,1,1,1]
vpaddd xmm0, xmm0, xmm1
vmovd eax, xmm0
vzeroupper
ret
clang 的代码类似于 gcc 时只有 -mpopcnt 打开，有一点展开。
count: # @count
xor ecx, ecx
xor eax, eax
.LBB0_1: # =>This Inner Loop Header: Depth=1
popcnt rdx, qword ptr [rdi + 8*rcx]
add edx, eax
popcnt rsi, qword ptr [rdi + 8*rcx + 8]
add esi, edx
popcnt rdx, qword ptr [rdi + 8*rcx + 16]
popcnt rax, qword ptr [rdi + 8*rcx + 24]
add edx, esi
add eax, edx
add rcx, 4
cmp rcx, 1024
jne .LBB0_1
ret
根据此文档 (https://www.agner.org/optimize/instruction_tables.pdf)，popcnt 在大多数体系结构上都是非常便宜的指令。那为什么 clang 生成这样的膨胀来替换 popcnt 而我明确允许它与 -mpopcnt 一起使用？优化级别全部设为-O3.
这里有一个 link 神栓 (https://godbolt.org/z/4vWK33a7c).
它是自动矢量化和展开的，这对于大型阵列来说是一个性能上的胜利（或者如果 clang 的开销更少的话），至少在 Intel CPU 上是这样 popcnt 是 1/时钟，所以每个时钟 64 位。 （AMD Zen 有 3 或 4 个/clock popcnt，因此 add 指令占用 4 个标量整数 ALU 端口，它可以维持 2/clock uint64_t popcnt+load并添加。) https://uops.info/
但是 vpshufb 在 Intel 上也是 1/clock（或者在 Ice Lake 上是 2/clock），如果瓶颈是每个时钟 128 位的 popcount 工作。 （对 32 个字节中每个字节的低 4 位进行 table 查找。）但它肯定不会那么好，因为它在循环内进行了所有额外的洗牌。 :/
这种向量化在 Zen1 上失败了，因为 SIMD ALU 只有 256 位宽，但在 Intel 上应该是一个重要的胜利，也许在 Zen2 和更高版本上是一个胜利。
但看起来 clang 在 vpsadbw 的内部循环中扩大到 32 位计数，所以它并没有达到预期的那么好。 1024x uint64_t 是输入数据的 256 __m256i 个向量，clang 展开 4 所以任何一个元素中的最大计数只有 64，不会溢出。
考虑到它所做的工作量，Clang 展开的数量惊人。 vextracti128 和 vpackusdw 对我来说没有多大意义，IDK 为什么它会在循环内这样做。没有溢出风险的矢量化的简单方法只是 vpsadbw -> vpaddq 或 vpaddd，它已经在 8 字节块内使用 vpsadbw 进行水平字节总和。 （更好的方法是将它推迟到字节元素可能溢出之前，所以做一些 vpaddb。就像 How to count character occurrences using SIMD 一样，尽管字节计数器在那里只增加 0 或 1，而不是0 .. 8)
请参阅 , especially Wojciech Muła's big-array popcnt functions: https://github.com/WojciechMula/sse-popcount/ - clang 使用与 popcnt_AVX2_lookup 相同的策略，但使用一种效率低得多的方法来跨迭代累积结果。
对于这样的函数，clang（有时 gcc 在某些我无法最低限度重现的上下文中）似乎在 -mavx2 开关打开时生成臃肿的代码。
unsigned count(uint64_t *f) {
unsigned c = 0;
for (unsigned i = 0; i < 1024; ++i) {
if (sizeof(long) >= 8) {
c += __builtin_popcountl(f[i]);
} else {
c += __builtin_popcountll(f[i]);
}
}
return c;
}
这来自 gcc，非常简单。
count:
lea rcx, [rdi+8192]
xor eax, eax
.L2:
xor edx, edx
add rdi, 8
popcnt rdx, QWORD PTR [rdi-8]
add eax, edx
cmp rcx, rdi
jne .L2
ret
但是 clang 决定在 -mavx2 开启时产生这种巨大的膨胀。 -mpopcnt 也已设置。
.LCPI0_0:
.zero 32,15
.LCPI0_1:
.byte 0 # 0x0
.byte 1 # 0x1
.byte 1 # 0x1
.byte 2 # 0x2
.byte 1 # 0x1
.byte 2 # 0x2
.byte 2 # 0x2
.byte 3 # 0x3
.byte 1 # 0x1
.byte 2 # 0x2
.byte 2 # 0x2
.byte 3 # 0x3
.byte 2 # 0x2
.byte 3 # 0x3
.byte 3 # 0x3
.byte 4 # 0x4
.byte 0 # 0x0
.byte 1 # 0x1
.byte 1 # 0x1
.byte 2 # 0x2
.byte 1 # 0x1
.byte 2 # 0x2
.byte 2 # 0x2
.byte 3 # 0x3
.byte 1 # 0x1
.byte 2 # 0x2
.byte 2 # 0x2
.byte 3 # 0x3
.byte 2 # 0x2
.byte 3 # 0x3
.byte 3 # 0x3
.byte 4 # 0x4
count: # @count
vpxor xmm0, xmm0, xmm0
xor eax, eax
vmovdqa ymm1, ymmword ptr [rip + .LCPI0_0] # ymm1 = [15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15]
vmovdqa ymm2, ymmword ptr [rip + .LCPI0_1] # ymm2 = [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4]
vpxor xmm12, xmm12, xmm12
vpxor xmm4, xmm4, xmm4
vpxor xmm5, xmm5, xmm5
vpxor xmm6, xmm6, xmm6
.LBB0_1: # =>This Inner Loop Header: Depth=1
vmovdqu ymm7, ymmword ptr [rdi + 8*rax]
vmovdqu ymm8, ymmword ptr [rdi + 8*rax + 32]
vmovdqu ymm9, ymmword ptr [rdi + 8*rax + 64]
vmovdqu ymm10, ymmword ptr [rdi + 8*rax + 96]
vpand ymm11, ymm7, ymm1
vpshufb ymm11, ymm2, ymm11
vpsrlw ymm7, ymm7, 4
vpand ymm7, ymm7, ymm1
vpshufb ymm7, ymm2, ymm7
vpaddb ymm7, ymm11, ymm7
vpsadbw ymm7, ymm12, ymm7
vpand ymm11, ymm8, ymm1
vpshufb ymm11, ymm2, ymm11
vpsrlw ymm8, ymm8, 4
vpand ymm8, ymm8, ymm1
vpshufb ymm8, ymm2, ymm8
vpaddb ymm8, ymm8, ymm11
vpsadbw ymm8, ymm8, ymm12
vpand ymm11, ymm9, ymm1
vpshufb ymm11, ymm2, ymm11
vpsrlw ymm9, ymm9, 4
vpand ymm9, ymm9, ymm1
vpshufb ymm9, ymm2, ymm9
vpaddb ymm9, ymm9, ymm11
vpsadbw ymm9, ymm9, ymm12
vpand ymm11, ymm10, ymm1
vpshufb ymm11, ymm2, ymm11
vpsrlw ymm10, ymm10, 4
vpand ymm10, ymm10, ymm1
vpshufb ymm10, ymm2, ymm10
vpaddb ymm10, ymm10, ymm11
vpsadbw ymm10, ymm10, ymm12
vextracti128 xmm3, ymm7, 1
vpackusdw xmm3, xmm7, xmm3
vpaddd xmm0, xmm0, xmm3
vextracti128 xmm3, ymm8, 1
vpackusdw xmm3, xmm8, xmm3
vpaddd xmm4, xmm4, xmm3
vextracti128 xmm3, ymm9, 1
vpackusdw xmm3, xmm9, xmm3
vpaddd xmm5, xmm5, xmm3
vextracti128 xmm3, ymm10, 1
vpackusdw xmm3, xmm10, xmm3
vpaddd xmm6, xmm6, xmm3
add rax, 16
cmp rax, 1024
jne .LBB0_1
vpaddd xmm0, xmm4, xmm0
vpaddd xmm0, xmm5, xmm0
vpaddd xmm0, xmm6, xmm0
vpshufd xmm1, xmm0, 238 # xmm1 = xmm0[2,3,2,3]
vpaddd xmm0, xmm0, xmm1
vpshufd xmm1, xmm0, 85 # xmm1 = xmm0[1,1,1,1]
vpaddd xmm0, xmm0, xmm1
vmovd eax, xmm0
vzeroupper
ret
clang 的代码类似于 gcc 时只有 -mpopcnt 打开，有一点展开。
count: # @count
xor ecx, ecx
xor eax, eax
.LBB0_1: # =>This Inner Loop Header: Depth=1
popcnt rdx, qword ptr [rdi + 8*rcx]
add edx, eax
popcnt rsi, qword ptr [rdi + 8*rcx + 8]
add esi, edx
popcnt rdx, qword ptr [rdi + 8*rcx + 16]
popcnt rax, qword ptr [rdi + 8*rcx + 24]
add edx, esi
add eax, edx
add rcx, 4
cmp rcx, 1024
jne .LBB0_1
ret
根据此文档 (https://www.agner.org/optimize/instruction_tables.pdf)，popcnt 在大多数体系结构上都是非常便宜的指令。那为什么 clang 生成这样的膨胀来替换 popcnt 而我明确允许它与 -mpopcnt 一起使用？优化级别全部设为-O3.
这里有一个 link 神栓 (https://godbolt.org/z/4vWK33a7c).
它是自动矢量化和展开的，这对于大型阵列来说是一个性能上的胜利（或者如果 clang 的开销更少的话），至少在 Intel CPU 上是这样 popcnt 是 1/时钟，所以每个时钟 64 位。 （AMD Zen 有 3 或 4 个/clock popcnt，因此 add 指令占用 4 个标量整数 ALU 端口，它可以维持 2/clock uint64_t popcnt+load并添加。) https://uops.info/
但是 vpshufb 在 Intel 上也是 1/clock（或者在 Ice Lake 上是 2/clock），如果瓶颈是每个时钟 128 位的 popcount 工作。 （对 32 个字节中每个字节的低 4 位进行 table 查找。）但它肯定不会那么好，因为它在循环内进行了所有额外的洗牌。 :/
这种向量化在 Zen1 上失败了，因为 SIMD ALU 只有 256 位宽，但在 Intel 上应该是一个重要的胜利，也许在 Zen2 和更高版本上是一个胜利。
但看起来 clang 在 vpsadbw 的内部循环中扩大到 32 位计数，所以它并没有达到预期的那么好。 1024x uint64_t 是输入数据的 256 __m256i 个向量，clang 展开 4 所以任何一个元素中的最大计数只有 64，不会溢出。
考虑到它所做的工作量，Clang 展开的数量惊人。 vextracti128 和 vpackusdw 对我来说没有多大意义，IDK 为什么它会在循环内这样做。没有溢出风险的矢量化的简单方法只是 vpsadbw -> vpaddq 或 vpaddd，它已经在 8 字节块内使用 vpsadbw 进行水平字节总和。 （更好的方法是将它推迟到字节元素可能溢出之前，所以做一些 vpaddb。就像 How to count character occurrences using SIMD 一样，尽管字节计数器在那里只增加 0 或 1，而不是0 .. 8)
请参阅 popcnt_AVX2_lookup 相同的策略，但使用一种效率低得多的方法来跨迭代累积结果。