如何自动矢量化循环，其中1)修改数组，2)指示数组最后是否更改？

html5 • 2022年12月4日 pm11:34 • 问答

我有这个 C++ 函数：

#include <stddef.h>

typedef unsigned long long Word;

bool fun(Word *lhs, const Word *rhs, size_t s)
{
    bool changed = false;
    #pragma omp simd
    for (size_t i = 0; i < s; ++i) {
        const Word old = lhs[i];
        lhs[i] |= rhs[i];
        changed = changed || old != lhs[i];
    }

    return changed;
}

本质上，它是位向量 ( lhs |= rhs)的按位或实现。我对编写具有 SIMD 意识的代码很陌生，我无法弄清楚如何让编译器在不引入额外开销的情况下对其进行矢量化（例如，创建changed一个数组然后循环遍历它）。移除这changed = ...条线可以让一切都很好地进行矢量化。

我试过有omp simd没有。我不认为这是相关的，但我想保持它，因为lhs和rhs从来没有重叠，我想补充的align最终条款。

目前，我正在使用 GCC，但我希望最终能够与 GCC 和 Clang 一起工作。

回答

TL:DR：使用Word unchanged = -1ULL;并更新它，unchanged &= (old == lhs[i]) ? -1ULL : 0;因此这自然映射到 SIMD 比较相等和 SIMD AND。

或者甚至更好，changed |= old ^ lhs[i];使用 GCC 和 clang 很好地矢量化，对于Word changed = 0;. 使用 clang，它提供了最佳的 asm。使用 GCC，第一种方法更好，因为 GCC 悲观地changed |= (~old) & rhs[i]; // find RHS bits that weren't already set花费额外的 movdqa 寄存器副本，或者 AVX 删除了将未对齐的加载折叠到内存源中的能力vpor（因为它需要两个操作数两次，一次用于此，一次用于主要|）。

在 AVX-512 之前，Compare-for-unequal 不能直接使用；这样做必须在组合成changed向量之前反转比较结果。

整个操作可以像编写的那样使用内在函数（或 asm）手动矢量化，无需任何重大转换，当然优化为按位|OR 而不是实际的短路评估。所以这基本上是一个错过的优化。 但是在自然的 asm 实现中，您的changed元素向量将与数据具有相同的宽度，而不仅仅是 4bool秒。 （对于 x86，需要额外vmovmskpd提供标量or而不是 SIMD vpor，而且大多数 ISA 没有 movemask 操作，所以可能通用矢量化器甚至没有考虑使用它。有趣的事实：clang 自动矢量化您的原始代码真的很糟糕，bool每次迭代都做一个水平 OR 到一个标量。）

UsingWord changed = 0;让这个矢量化相当体面，有changed |= ...，有或没有 OpenMP pragma（不同的是，还没有整理出对于每个组合来说哪个实际上更好）。编译器是愚蠢的（复杂的机器部件，不是人类理解的）并且通常不会为自己弄清楚这样的事情 - 自动矢量化非常困难，他们有时需要一些手动操作。

所以诀窍是制作changed与数组元素相同的宽度。

如果您使用 OpenMP，您需要告诉 OpenMP 向量化器有关减少的信息，例如使用+或在本例中为 OR的数组之和。在这种情况下，#pragma omp simd reduction(|:changed)。changed |= stuff如果您希望将其矢量化为无分支 SIMD，则无论如何您都应该使用逻辑短路 eval 代替。 reduction(|:changed)实际上似乎在某种程度上覆盖了您的实际代码，所以要小心它匹配。

如果您只使用#pragma omp simd https://godbolt.org/z/bG98Kz ， ICC 甚至会破坏您的代码（不会在 SIMD 部分更新更改）。（也许这允许它忽略串行依赖项，或者至少是减少，你没有告诉它？无论是那个还是 ICC 错误，我不太了解 OpenMP。）

使用原始bool changed而不是Word，GCC 根本不会自动矢量化，并且 clang 做了一件令人讨厌的工作（bool在内部循环中水平减少到标量！）

自动矢量化的两个版本：

在 Godbolt上-O3 -march=nehalem -mtune=skylake -fopenmp（所以使用 SSE4.1 / 4.2，但不使用 AVX 或 BMI1/BMI2）。我还没有详细研究哪个最终的清理代码不那么笨拙。

#include <stddef.h>
typedef unsigned long long Word;

bool fun_v1(Word *lhs, const Word *rhs, size_t s)
{
    Word changed = 0;
    #pragma omp simd reduction(|:changed)  // optional, some asm differences with/without
    for (size_t i = 0; i < s; ++i) {
        const Word old = lhs[i];
        changed |= (~old) & rhs[i];   // find RHS bits that weren't already set. pure bitwise, no 64-bit-element SIMD == needed.  Do this before storing so compiler doesn't have to worry about lhs/rhs overlap.
        lhs[i] |= rhs[i];
        //changed |= (old != lhs[i]) ? -1ULL : 0;    // requires inverting the cmpeq result, but can fold a memory operand with AVX unlike the bitwise version

        //changed = changed || (old != lhs[i]);    // short circuit eval is weird for SIMD, compiles inefficiently.
    }

    return changed;
}

（更新：changed |= old ^ lhs[i];在不等于上获得非零值似乎更好。它只使用交换操作，不需要==/ pcmpeqq。@chtz 在评论中建议了这一点，我没有重写其余的答案切出糟糕optoins的讨论。铛会自动向量化它，并与AVX允许的内存源操作数为RHS，因为它只需要做一次。https://godbolt.org/z/ex5519。所以这似乎是最好的两个世界。）

changed |= (old != lhs[i]) ? -1ULL : 0;changed |= (~old) & rhs[i];对于没有 AVX 的 GCC 10.2，内循环中也仍然只有 10 条指令（9 uop），与相同。但是对于 clang，这会打败自动矢量化！Clang 将处理changed |= (old != lhs[i]); （或使用显式? 1 : 0），所以这很奇怪。 -1ULL避免需要set1_epi64x(1)向量常数，所以我使用了它。

使用==或!=将需要 SSE4.1 的版本pcmpeqq用于 64 位比较的矢量化==：编译器可能不够聪明，无法意识到任何整数元素大小都适用于整体。并且模拟更窄的比较可能看起来不会有利可图。

该~old & rhs[i]方式仅适用于 SSE2。用 SSE4.1ptest而不是 shuffles 和 POR 和 MOVQ结束循环会更有效，但编译器对这样的东西非常愚蠢。（并且一般处理循环的结尾。只是简单的减少和对奇数元素的标量清理，而不是在数组末尾结束的可能重叠的最终向量。 |=是幂等的，所以在最坏的情况下它会导致存储转发停顿如果你不安排您的负载良好，这是另一回事，你可以用手动矢量做的更好，但是当你编译一个AVX2 CPU喜欢使用内联函数会迫使一个SIMD矢量宽度，而自动VEC让编译器使用更广泛的载体-march=haswell或-march=znver2.)

在 AVX-512 之前，只有比较==可用（或>），而不是!=直接比较。为了按照我们想要的方式减少这种情况，我们需要unchanged &= (old == updated);. 这让 GCC 在循环中保存 1 条指令，将其降低到 9 条指令，8 uop。它可能每 2 个周期运行 1 次迭代。

但是由于某种原因，clang 根本不会自动矢量化它。显然，clang 不喜欢? -1 : 0这里或其他版本中的三元，也许没有意识到这就是 SIMD 比较产生的。

bool fun_v2(Word *lhs, const Word *rhs, size_t s)
{
    Word unchanged = -1ULL;
// clang fails to vectorize?!?  GCC works as expected with/without pragma
    #pragma omp simd reduction(&:unchanged)
    for (size_t i = 0; i < s; ++i) {
        const Word old = lhs[i];
        lhs[i] |= rhs[i];
        unchanged &= (old == lhs[i]) ? -1ULL : 0;
    }
    return !unchanged;
}

有了 AVX，vpor如果编译器不使用愚蠢的索引寻址模式，内存源操作数将是有效的，迫使它在 Intel Sandybridge 系列（但不是在 AMD）上取消层压。

请注意，如果您正在考虑将其Word用作宽类型以在其他类型的任意数据上使用它，请注意严格别名规则和未定义行为。手动矢量化可能是一个不错的选择，因为_mm_loadu_si128((const __m128*)int_ptr);它完全严格别名安全：矢量指针（和加载/存储内部函数）就像char*它们可以别名任何东西一样。对于便携式版本，请使用 memcpy 或 GNU C typedef unsigned long unaligned_aliasing_chunk __attribute__((may_alias,aligned(1)))。“Word”在 asm 中对于不同的 ISA 具有不同的含义，例如在 x86 中为 16 位，因此对于您想要的类型而言，它不是最好的名称，因为机器可以有效地使用它。 unsigned long通常是这样，但在某些 64 位机器上是 32 位的。 unsigned long long可能没问题。