Clang 为 7 次比较生成的代码比为 8 次比较生成的代码更糟糕

Question

我对 clang 将小整数的许多 == 比较转换为一个大 SIMD 指令的能力很感兴趣，但后来我注意到了一些奇怪的事情。 Clang 生成 "worse" 代码（在我的业余评估中）当我有 7 次比较时与我有 8 次比较时的代码相比。

bool f1(short x){
    return (x==-1) | (x == 150) |
           (x==5) | (x==64) | 
           (x==15) | (x==223) | 
           (x==42) | (x==47);
}

bool f2(short x){
    return (x==-1) | (x == 150) |
           (x==5) | (x==64) | 
           (x==15) | (x==223) | 
           (x==42);
}

我的问题是这是一个小的性能错误，或者 clang 有一个很好的理由不想引入虚拟比较（即假设有一个额外的比较与 7 个值之一）并使用一个常量在代码中实现它。

神箭linkhere:

# clang(trunk) -O2 -march=haswell
f1(short):
    vmovd   xmm0, edi
    vpbroadcastw    xmm0, xmm0             # set1(x)
    vpcmpeqw        xmm0, xmm0, xmmword ptr [rip + .LCPI0_0]  # 16 bytes = 8 shorts
    vpacksswb       xmm0, xmm0, xmm0
    vpmovmskb       eax, xmm0
    test    al, al
    setne   al           # booleanize the parallel-compare bitmask
    ret

对比

f2(short):
    cmp     di, -1
    sete    r8b
    cmp     edi, 150
    sete    dl
    cmp     di, 5             # scalar checks of 3 conditions
    vmovd   xmm0, edi
    vpbroadcastw    xmm0, xmm0
    vpcmpeqw        xmm0, xmm0, xmmword ptr [rip + .LCPI1_0]  # low 8 bytes = 4 shorts
    sete    al
    vpmovsxwd       xmm0, xmm0
    vmovmskps       esi, xmm0
    test    sil, sil
    setne   cl                # SIMD check of the other 4
    or      al, r8b
    or      al, dl
    or      al, cl            # and combine.
    ret

quickbench 似乎不起作用，因为 IDK 如何为其提供 -mavx2 标志。（编者注：简单地计算前端成本的 uops 表明这显然对吞吐量更差。还有延迟。）

Answer 1

看起来 clang 的优化器没有考虑复制元素以使其达到 SIMD 方便的比较次数。但你是对的，这比做额外的标量工作要好。 显然错过了优化，应该报告为 clang/LLVM 优化器错误。 https://bugs.llvm.org/

f1() 的 asm 明显优于 f2()：vpacksswb xmm 在主流 Intel 和 AMD CPU 上与 vpmovsxwd xmm 具有相同的成本，就像其他单 uop洗牌。如果任何 vpmovsx -> vmovmskps 可能在整数和 FP 域之间绕过延迟 ¹.

脚注 1：使用 AVX2（Sandybridge 系列）的主流 Intel CPU 可能没有额外的旁路延迟； IIRC，FP 操作之间的整数洗牌通常很好。 (https://agner.org/optimize/)。但是对于 Nehalem 上的 SSE4.1 版本，是的，整数版本可能没有额外的惩罚。

您不需要 AVX2，但是在没有 pshufb 控制向量的情况下在一条指令中进行字广播确实可以提高效率。并且 clang 选择 pshuflw -> pshufd for -march=nehalem

当然，两个版本都不是最优的。 movemask 之前无需 shuffle 压缩比较结果。

而不是 test al, al，可以 select 你想用 test sil, 0b00001010 检查哪些位，例如，检查位 1 和 3 但忽略其他位中的非零位职位。

pcmpeqw 将单词元素内的两个字节设置为相同，因此可以 pmovmskb 结果并获得包含位对的整数。

使用字节寄存器而不是双字寄存器也有零好处：test sil,sil 应避免使用 REX 前缀并使用 test esi,esi.

所以即使没有重复其中一个条件，f2()也可能是：

f2:
    vmovd           xmm0, edi
    vpbroadcastw    xmm0, xmm0             # set1(x)
    vpcmpeqw        xmm0, xmm0, xmmword ptr [rip + .LCPI0_0]
    vpmovmskb       eax, xmm0
    test    eax, 0b011111111111111    # (1<<15) - 1 = low 14 bits set
    setne   al
    ret

即test会根据pmovmksb结果的低14位设置ZF，因为高位在TEST掩码中被清除。 TEST = AND 不写入其输出。通常用于 selecting 部分比较掩码。

但是因为我们首先需要一个 16 字节的内存常量，所以我们应该复制其中一个元素以将其填充到 8 个元素。然后我们就可以像正常人一样使用test eax,eax了。压缩掩码以适应 8 位 AL 完全是浪费时间和代码大小。 test r32, r32 与 test r8,r8 一样快，并且 SIL、DIL 或 BPL 不需要 REX 前缀。

有趣的事实：AVX512VL 让我们使用 vpbroadcastw xmm0, edi 来组合 movd 和广播。

或者只比较 4 个元素，而不是对 movmskps 进行额外的洗牌，我们这里只需要 SSE2。戴口罩真的很有用。

test_4_possibilities_SSE2:
    movd            xmm0, edi
    pshufd          xmm0, xmm0, 0             # set1_epi32(x)
    pcmpeqw         xmm0, [const]             # == set_epi32(a, b, c, d)
    pmovmskb        eax, xmm0
    test    eax, 0b0001000100010001     # the low bit of each group of 4
    setne   al
    ret

我们进行双字广播，忽略每个32位元素高16位的比较结果。为 test 使用掩码可以让我们比任何额外的指令更便宜地做到这一点。

没有 AVX2，使用 pshufd 的 SIMD 双字广播比需要字广播便宜。

另一种选择是 imul 和 0x00010001 将一个字广播到 32 位寄存器中，但它有 3 个周期的延迟，因此它可能比 punpcklwd 更糟糕 -> pshufd

不过，在循环中，值得为 pshufb (SSSE3) 加载控制向量，而不是使用 2 次随机播放或 imul。

Clang 为 7 次比较生成的代码比为 8 次比较生成的代码更糟糕

Clang generates worse code for 7 comparisons than for 8 comparisons

c++

x86

assembly

clang

compiler-optimization