如何自动向量化循环，其中 1) 修改数组，2) 指示数组最后是否更改？
How to auto-vectorise a loop which 1) modifies an array, 2) indicates whether the array changed or not at the end?
我有这个 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 才可以直接比较不相等；这样做必须在组合成 changed 向量之前反转比较结果。
整个操作可以使用内部函数（或 asm）手动矢量化，几乎与编写的一样，无需任何重大转换，当然除了优化为按位 | OR 而不是实际的短路评估。所以这基本上是一个错过的优化。 但是在自然的 asm 实现中，changed 元素的向量将与数据宽度相同，而不仅仅是 4 bools。（对于 x86这将需要一个额外的 vmovmskpd 来提供一个标量 or 而不仅仅是一个 SIMD vpor，并且大多数 ISA 没有移动掩码操作，所以也许通用矢量化器甚至没有考虑使用它。有趣的事实：clang 非常糟糕地自动矢量化您的原始代码，每次迭代都对标量 bool 进行水平 OR。）
使用 Word changed = 0; 可以相当不错地进行矢量化，使用 changed |= ...，有或没有 OpenMP pragmas（不同的是，还没有弄清楚哪个实际上是每个组合都更好）。编译器是愚蠢的（复杂的机器部件，不是人类的理解）并且通常不会自己弄清楚这样的事情 - 自动矢量化非常困难，他们有时需要一些帮助。
所以诀窍是使 changed 与数组元素的宽度相同。
如果您使用 OpenMP，您需要告诉 OpenMP 矢量化器关于缩减，例如数组与 + 的总和，或者在本例中为 OR。在这种情况下，#pragma omp simd reduction(|:changed)。如果您希望将其矢量化为无分支 SIMD，您应该使用 changed |= stuff 而不是逻辑短路评估。 reduction(|:changed) 实际上似乎在某种程度上覆盖了您的实际代码，因此请注意它是否匹配。
如果您只使用 #pragma omp simd https://godbolt.org/z/bG98Kz，ICC 甚至会破坏您的代码（不会在 SIMD 部分更新更改）。 （也许这给了它忽略串行依赖性的许可，或者至少是减少了，你没有告诉它？无论是那个还是 ICC 错误，我不太了解 OpenMP。）
使用原始 bool changed 而不是 Word，GCC 根本不会自动矢量化，而 clang 做了一个令人讨厌的工作（水平缩减为标量 bool内循环！）
自动矢量化的两个版本：
On 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 的讨论。clang 将使用它自动矢量化，并且使用 AVX 允许 rhs 的内存源操作数因为它只需要一次。https://godbolt.org/z/ex5519。所以这似乎是两全其美。）
对于没有 AVX 的 GCC 10.2，changed |= (old != lhs[i]) ? -1ULL : 0; 在内循环中仍然只有 10 条指令（9 微指令），与 changed |= (~old) & rhs[i]; 相同。但是对于 clang，这会打败自动矢量化！ Clang 将处理 changed |= (old != lhs[i]);（或使用明确的 ? 1 : 0），所以这很奇怪。 -1ULL 避免需要 set1_epi64x(1) 向量常数，所以我使用了它。
使用 == 或 != 的版本将需要 SSE4.1 pcmpeqq 进行 64 位矢量化比较 ==：编译器可能不会足够聪明，可以意识到任何整数元素大小都适合整体。模拟更窄的比较可能不会有利可图。
~old & rhs[i] 方法仅适用于 SSE2。用 SSE4.1 ptest 结束循环而不是洗牌、POR 和 MOVQ 会更有效率，但编译器对这样的事情非常愚蠢。 （并通常处理循环的结尾。
只是对奇数元素进行简单的归约和标量清理，而不是在数组末尾结束的可能重叠的最终向量。 |= 是幂等的，所以在最坏的情况下，如果您没有很好地安排负载，它会导致存储转发停顿。这是您可以通过手动矢量化做得更好的另一件事，但是使用内在函数会强制一个 SIMD 矢量宽度，而 auto-vec 允许编译器在编译 AVX2 CPU 时使用更宽的矢量，例如 -march=haswell 或 -march=znver2.)
AVX-512 之前，只能比较 == （或 >），不能直接比较 !=。要以我们想要的方式减少它，我们需要 unchanged &= (old == updated);。这让 GCC 在循环中节省 1 条指令，将其减少到 9 条指令，8 微指令。它可能 运行 每 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)))。对于不同的 ISA，“Word”在 asm 中有不同的含义，比如在 x86 中是 16 位的，所以它不是你想要的类型的最佳名称，因为机器可以有效地使用它。 unsigned long 通常是这样，但在某些 64 位机器上是 32 位的。 unsigned long long 可能没问题。
我有这个 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 才可以直接比较不相等；这样做必须在组合成 changed 向量之前反转比较结果。
整个操作可以使用内部函数（或 asm）手动矢量化，几乎与编写的一样，无需任何重大转换，当然除了优化为按位 | OR 而不是实际的短路评估。所以这基本上是一个错过的优化。 但是在自然的 asm 实现中，changed 元素的向量将与数据宽度相同，而不仅仅是 4 bools。（对于 x86这将需要一个额外的 vmovmskpd 来提供一个标量 or 而不仅仅是一个 SIMD vpor，并且大多数 ISA 没有移动掩码操作，所以也许通用矢量化器甚至没有考虑使用它。有趣的事实：clang 非常糟糕地自动矢量化您的原始代码，每次迭代都对标量 bool 进行水平 OR。）
使用 Word changed = 0; 可以相当不错地进行矢量化，使用 changed |= ...，有或没有 OpenMP pragmas（不同的是，还没有弄清楚哪个实际上是每个组合都更好）。编译器是愚蠢的（复杂的机器部件，不是人类的理解）并且通常不会自己弄清楚这样的事情 - 自动矢量化非常困难，他们有时需要一些帮助。
所以诀窍是使 changed 与数组元素的宽度相同。
如果您使用 OpenMP，您需要告诉 OpenMP 矢量化器关于缩减，例如数组与 + 的总和，或者在本例中为 OR。在这种情况下，#pragma omp simd reduction(|:changed)。如果您希望将其矢量化为无分支 SIMD，您应该使用 changed |= stuff 而不是逻辑短路评估。 reduction(|:changed) 实际上似乎在某种程度上覆盖了您的实际代码，因此请注意它是否匹配。
如果您只使用 #pragma omp simd https://godbolt.org/z/bG98Kz，ICC 甚至会破坏您的代码（不会在 SIMD 部分更新更改）。 （也许这给了它忽略串行依赖性的许可，或者至少是减少了，你没有告诉它？无论是那个还是 ICC 错误，我不太了解 OpenMP。）
使用原始 bool changed 而不是 Word，GCC 根本不会自动矢量化，而 clang 做了一个令人讨厌的工作（水平缩减为标量 bool内循环！）
自动矢量化的两个版本：
On 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 的讨论。clang 将使用它自动矢量化，并且使用 AVX 允许 rhs 的内存源操作数因为它只需要一次。https://godbolt.org/z/ex5519。所以这似乎是两全其美。）
changed |= (old != lhs[i]) ? -1ULL : 0; 在内循环中仍然只有 10 条指令（9 微指令），与 changed |= (~old) & rhs[i]; 相同。但是对于 clang，这会打败自动矢量化！ Clang 将处理 changed |= (old != lhs[i]);（或使用明确的 ? 1 : 0），所以这很奇怪。 -1ULL 避免需要 set1_epi64x(1) 向量常数，所以我使用了它。
使用 == 或 != 的版本将需要 SSE4.1 pcmpeqq 进行 64 位矢量化比较 ==：编译器可能不会足够聪明，可以意识到任何整数元素大小都适合整体。模拟更窄的比较可能不会有利可图。
~old & rhs[i] 方法仅适用于 SSE2。用 SSE4.1 ptest 结束循环而不是洗牌、POR 和 MOVQ 会更有效率，但编译器对这样的事情非常愚蠢。 （并通常处理循环的结尾。
只是对奇数元素进行简单的归约和标量清理，而不是在数组末尾结束的可能重叠的最终向量。 |= 是幂等的，所以在最坏的情况下，如果您没有很好地安排负载，它会导致存储转发停顿。这是您可以通过手动矢量化做得更好的另一件事，但是使用内在函数会强制一个 SIMD 矢量宽度，而 auto-vec 允许编译器在编译 AVX2 CPU 时使用更宽的矢量，例如 -march=haswell 或 -march=znver2.)
AVX-512 之前，只能比较 == （或 >），不能直接比较 !=。要以我们想要的方式减少它，我们需要 unchanged &= (old == updated);。这让 GCC 在循环中节省 1 条指令，将其减少到 9 条指令，8 微指令。它可能 运行 每 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)))。对于不同的 ISA，“Word”在 asm 中有不同的含义，比如在 x86 中是 16 位的，所以它不是你想要的类型的最佳名称，因为机器可以有效地使用它。 unsigned long 通常是这样，但在某些 64 位机器上是 32 位的。 unsigned long long 可能没问题。