如何在没有 openCL 或内在函数的情况下使用 g++ 自动矢量化访问步幅为 2 的循环
How to autovectorize a loop with access stride 2 with g++ without openCL or intrinsics
我正在尝试将函数从使用内部函数的实现转换为标准 C++（以简化维护、可移植性等）。一切正常，除了步幅为 2 的循环，其中奇数位置的字节被收集到一个位置，奇数位置的字节被收集到另一个位置。
相关问题已使用 opencl 或内在函数解决，但我想坚持使用标准 c++。
我尝试自动矢量化的一个最小示例如下所示：
void f(const unsigned char *input, const unsigned size, unsigned char *output) {
constexpr unsigned MAX_SIZE = 2000;
unsigned char odd[MAX_SIZE / 2];
unsigned char even[MAX_SIZE / 2];
for (unsigned i = 0; size > i; ++i) {
if (0 == i % 2) {even[i/2] = input[i];}
else {odd[i/2] = input[i];}
}
//for (unsigned i = 0; size > i; i+=2) {
// even[i/2] = input[i];
// odd[i/2] = input[i+1];
//}
for (unsigned i = 0; size / 2 > i; ++i)
{
output[i] = (even[i] << 4) | odd[i];
}
}
用g++-11.2编译，-fopt-info-vec-missed输出为：
minimal.cpp:6:29: missed: couldn't vectorize loop
minimal.cpp:6:29: missed: not vectorized: control flow in loop.
如果我将实现更改为代码中注释掉的实现，g++ 将无法向量化，因为：
minimal.cpp:11:29: missed: couldn't vectorize loop
minimal.cpp:13:24: missed: not vectorized: not suitable for gather load _13 = *_11;
考虑到用打包随机字节指令实现这个很简单，我很惊讶 g++ 不能做到这一点。
有没有办法重写循环以便 g++ 能够对其进行矢量化？
哦，我找到了@Peter Cordes 的评论并结合了我最初的回答：
https://gcc.godbolt.org/z/bxzsfxPGx
和-fopt-info-vec-missed没有对我说什么
void f(const unsigned char *input, const unsigned size, unsigned char *output) {
constexpr unsigned MAX_SIZE = 2000;
unsigned char odd[MAX_SIZE / 2];
unsigned char even[MAX_SIZE / 2];
for (unsigned i = 0, j = 0; size > i; i += 2, ++j) {
even[j] = input[i];
odd[j] = input[i + 1];
}
for (unsigned i = 0; size / 2 > i; ++i) {
output[i] = (even[i] << 4) | odd[i];
}
}
GCC 似乎不喜欢 i<size ; i += 2 这样的东西。相反，它喜欢 i<size/2 ; i++。 GCC 和 clang 无法自动矢量化无法提前确定行程计数的循环。也许 GCC 对此有问题，因为您使用了 unsigned，因此 i+=2 可以回绕到 0 而无需点击 size，因此 i<size 可能永久为假，即 编译器无法证明你的循环不是无限的，因为 size = UINT_MAX 是可能的。（这会禁用编译器喜欢做的一些优化，尽管至少它是无符号的，所以我们不必重做符号扩展。）
Clang 无论如何都设法矢量化了（很差：https://godbolt.org/z/b4G4jojn1）；可能它意识到 evens[i] 如果大于常量 MAX_SIZE 就是 UB，否则它根本不在乎。
临时数组似乎没有必要；我认为您只是使用它们来尝试为 GCC 提供多个更简单的问题以进行矢量化？
// __restrict is optional; it promises the compiler input and output won't overlap
// it still vectorizes without it, but does a check for overlap
void g(const unsigned char *__restrict input, const unsigned size, unsigned char *__restrict output)
{
for (unsigned i = 0 ; size/2 > i; i++) {
output[i] = (input[2*i] << 4) | input[2*i+1];
}
}
没有 __restrict，在重叠时它会退回到标量循环。在 input = output 的情况下，矢量版本仍然是安全的。在那种情况下，我没有测试或反向工程重叠检查以查看它是否使用矢量化版本。 （不过，将它与 input=output 和 __restrict 一起使用是 C++ UB。）
GCC11.2 -O3 -march=haswell 相当合理地自动矢量化它 (Godbolt)；一些错过的优化但没有单独循环那么糟糕，当然也避免了接触新的堆栈内存。主要的内部循环如下所示：
# GCC11 -O3 -march=haswell
# before loop, YMM3 = _mm256_set1_epi16(0x00FF)
.L4: # do{
vpand ymm1, ymm3, YMMWORD PTR [rcx+32+rax*2] # why not reuse the load results for both odd/even? fortunately modern CPUs have good L1d bandwidth
vpand ymm0, ymm3, YMMWORD PTR [rcx+rax*2] # evens: load input[2*(i+0..31)] and AND away the high bytes for pack
vmovdqu ymm4, YMMWORD PTR [rcx+rax*2] # load 2 vectors of input data
vmovdqu ymm5, YMMWORD PTR [rcx+32+rax*2]
vpackuswb ymm0, ymm0, ymm1 # evens: pack evens down to single bytes.
vpsrlw ymm2, ymm5, 8 # odds: shift down to line up with evens
vpsrlw ymm1, ymm4, 8
vpermq ymm0, ymm0, 216 # evens: lane-crossing fixup
vpaddb ymm0, ymm0, ymm0 # evens <<= 1 byte shift (x86 SIMD lacks a vpsllb, even with AVX-512)
vpackuswb ymm1, ymm1, ymm2 # odds: pack
vpaddb ymm0, ymm0, ymm0 # evens <<= 1
vpermq ymm1, ymm1, 216 # odds: lane-crossing fixup
vpaddb ymm0, ymm0, ymm0 # evens <<= 1
vpaddb ymm0, ymm0, ymm0 # evens <<= 1
vpor ymm0, ymm0, ymm1 # (evens<<4) | odds
vmovdqu YMMWORD PTR [rdi+rax], ymm0 # store to output
add rax, 32 # advance output position by 32 bytes. (Input positions scale by 2)
cmp rdx, rax
jne .L4 # } while(i != size/2)
如果 GCC 在打包之前选择使用 0x000F 而不是 0x00FF 进行屏蔽会更快，因此打包后的偶数可以使用 vpsllw 而不是 4x 左移vpaddb 而不会将任何非零位溢出到下一个字节。或者只是转移和再次;这是模拟不存在的 vpsllb.
的标准方法
或者甚至更好，在每个单词 之前 将高位和低位一起进行 OR 压缩到字节。
# manually vectorized; what GCC could have done in theory
# if using intrinsics, this strategy is probably good.
vmovdqu ymm0, [mem]
vmovdqu ymm1, [mem+32]
vpsllw ymm2, ymm0, 12 # evens: line up with odds, and do the <<4
vpsllw ymm3, ymm1, 12
vpor ymm0, ymm0, ymm2 # odds |= (evens<<4) in the high byte of each word
vpor ymm1, ymm1, ymm3
vpsrlw ymm0, ymm0, 8 # shift merged to bottom of word
vpsrlw ymm1, ymm1, 8
vpackuswb ymm0, ymm0, ymm1 # and pack
vpermq ymm0, ymm0, 0xDB # same 216
vmovdqu [mem], ymm0
.. pointer increment / loop condition
注意我们避免了 AND 常量；无论如何，两半都需要移动（即使是因为 <<4，在正确的位置放置背包也很奇怪）。打包后移位意味着要移位的数据量减半，但在移位后需要屏蔽，因此它会中断，除了带有移位单元的 ALU 端口上的后端端口压力。 (https://agner.org/optimize/ ; https://uops.info/)。但是在打包之前合并可以节省洗牌，这是英特尔 CPU 上更大的吞吐量瓶颈。
如果我们可以添加而不是 OR（因为我们知道没有重叠位所以它是等价的），我们可以使用带符号的（第二个）操作数作为 2x vpmaddubsw（_mm256_maddubs_epi16） _mm256_set1_epi16(0x0110) 和无符号（第一个）输入保存数组中的数据以在每个字节对中执行 input[2*i+1] + (input[2*i] * 16)。然后 AND 和 VPACKUSWB / VPERMQ 从单词向下到字节元素并存储。
我正在尝试将函数从使用内部函数的实现转换为标准 C++（以简化维护、可移植性等）。一切正常，除了步幅为 2 的循环，其中奇数位置的字节被收集到一个位置，奇数位置的字节被收集到另一个位置。
相关问题已使用 opencl 或内在函数解决，但我想坚持使用标准 c++。
我尝试自动矢量化的一个最小示例如下所示：
void f(const unsigned char *input, const unsigned size, unsigned char *output) {
constexpr unsigned MAX_SIZE = 2000;
unsigned char odd[MAX_SIZE / 2];
unsigned char even[MAX_SIZE / 2];
for (unsigned i = 0; size > i; ++i) {
if (0 == i % 2) {even[i/2] = input[i];}
else {odd[i/2] = input[i];}
}
//for (unsigned i = 0; size > i; i+=2) {
// even[i/2] = input[i];
// odd[i/2] = input[i+1];
//}
for (unsigned i = 0; size / 2 > i; ++i)
{
output[i] = (even[i] << 4) | odd[i];
}
}
用g++-11.2编译，-fopt-info-vec-missed输出为：
minimal.cpp:6:29: missed: couldn't vectorize loop
minimal.cpp:6:29: missed: not vectorized: control flow in loop.
如果我将实现更改为代码中注释掉的实现，g++ 将无法向量化，因为：
minimal.cpp:11:29: missed: couldn't vectorize loop
minimal.cpp:13:24: missed: not vectorized: not suitable for gather load _13 = *_11;
考虑到用打包随机字节指令实现这个很简单，我很惊讶 g++ 不能做到这一点。
有没有办法重写循环以便 g++ 能够对其进行矢量化？
哦，我找到了@Peter Cordes 的评论并结合了我最初的回答：
https://gcc.godbolt.org/z/bxzsfxPGx
和-fopt-info-vec-missed没有对我说什么
void f(const unsigned char *input, const unsigned size, unsigned char *output) {
constexpr unsigned MAX_SIZE = 2000;
unsigned char odd[MAX_SIZE / 2];
unsigned char even[MAX_SIZE / 2];
for (unsigned i = 0, j = 0; size > i; i += 2, ++j) {
even[j] = input[i];
odd[j] = input[i + 1];
}
for (unsigned i = 0; size / 2 > i; ++i) {
output[i] = (even[i] << 4) | odd[i];
}
}
GCC 似乎不喜欢 i<size ; i += 2 这样的东西。相反，它喜欢 i<size/2 ; i++。 GCC 和 clang 无法自动矢量化无法提前确定行程计数的循环。也许 GCC 对此有问题，因为您使用了 unsigned，因此 i+=2 可以回绕到 0 而无需点击 size，因此 i<size 可能永久为假，即 编译器无法证明你的循环不是无限的，因为 size = UINT_MAX 是可能的。（这会禁用编译器喜欢做的一些优化，尽管至少它是无符号的，所以我们不必重做符号扩展。）
Clang 无论如何都设法矢量化了（很差：https://godbolt.org/z/b4G4jojn1）；可能它意识到 evens[i] 如果大于常量 MAX_SIZE 就是 UB，否则它根本不在乎。
临时数组似乎没有必要；我认为您只是使用它们来尝试为 GCC 提供多个更简单的问题以进行矢量化？
// __restrict is optional; it promises the compiler input and output won't overlap
// it still vectorizes without it, but does a check for overlap
void g(const unsigned char *__restrict input, const unsigned size, unsigned char *__restrict output)
{
for (unsigned i = 0 ; size/2 > i; i++) {
output[i] = (input[2*i] << 4) | input[2*i+1];
}
}
没有 __restrict，在重叠时它会退回到标量循环。在 input = output 的情况下，矢量版本仍然是安全的。在那种情况下，我没有测试或反向工程重叠检查以查看它是否使用矢量化版本。 （不过，将它与 input=output 和 __restrict 一起使用是 C++ UB。）
GCC11.2 -O3 -march=haswell 相当合理地自动矢量化它 (Godbolt)；一些错过的优化但没有单独循环那么糟糕，当然也避免了接触新的堆栈内存。主要的内部循环如下所示：
# GCC11 -O3 -march=haswell
# before loop, YMM3 = _mm256_set1_epi16(0x00FF)
.L4: # do{
vpand ymm1, ymm3, YMMWORD PTR [rcx+32+rax*2] # why not reuse the load results for both odd/even? fortunately modern CPUs have good L1d bandwidth
vpand ymm0, ymm3, YMMWORD PTR [rcx+rax*2] # evens: load input[2*(i+0..31)] and AND away the high bytes for pack
vmovdqu ymm4, YMMWORD PTR [rcx+rax*2] # load 2 vectors of input data
vmovdqu ymm5, YMMWORD PTR [rcx+32+rax*2]
vpackuswb ymm0, ymm0, ymm1 # evens: pack evens down to single bytes.
vpsrlw ymm2, ymm5, 8 # odds: shift down to line up with evens
vpsrlw ymm1, ymm4, 8
vpermq ymm0, ymm0, 216 # evens: lane-crossing fixup
vpaddb ymm0, ymm0, ymm0 # evens <<= 1 byte shift (x86 SIMD lacks a vpsllb, even with AVX-512)
vpackuswb ymm1, ymm1, ymm2 # odds: pack
vpaddb ymm0, ymm0, ymm0 # evens <<= 1
vpermq ymm1, ymm1, 216 # odds: lane-crossing fixup
vpaddb ymm0, ymm0, ymm0 # evens <<= 1
vpaddb ymm0, ymm0, ymm0 # evens <<= 1
vpor ymm0, ymm0, ymm1 # (evens<<4) | odds
vmovdqu YMMWORD PTR [rdi+rax], ymm0 # store to output
add rax, 32 # advance output position by 32 bytes. (Input positions scale by 2)
cmp rdx, rax
jne .L4 # } while(i != size/2)
如果 GCC 在打包之前选择使用 0x000F 而不是 0x00FF 进行屏蔽会更快，因此打包后的偶数可以使用 vpsllw 而不是 4x 左移vpaddb 而不会将任何非零位溢出到下一个字节。或者只是转移和再次;这是模拟不存在的 vpsllb.
或者甚至更好，在每个单词 之前 将高位和低位一起进行 OR 压缩到字节。
# manually vectorized; what GCC could have done in theory
# if using intrinsics, this strategy is probably good.
vmovdqu ymm0, [mem]
vmovdqu ymm1, [mem+32]
vpsllw ymm2, ymm0, 12 # evens: line up with odds, and do the <<4
vpsllw ymm3, ymm1, 12
vpor ymm0, ymm0, ymm2 # odds |= (evens<<4) in the high byte of each word
vpor ymm1, ymm1, ymm3
vpsrlw ymm0, ymm0, 8 # shift merged to bottom of word
vpsrlw ymm1, ymm1, 8
vpackuswb ymm0, ymm0, ymm1 # and pack
vpermq ymm0, ymm0, 0xDB # same 216
vmovdqu [mem], ymm0
.. pointer increment / loop condition
注意我们避免了 AND 常量；无论如何，两半都需要移动（即使是因为 <<4，在正确的位置放置背包也很奇怪）。打包后移位意味着要移位的数据量减半，但在移位后需要屏蔽，因此它会中断，除了带有移位单元的 ALU 端口上的后端端口压力。 (https://agner.org/optimize/ ; https://uops.info/)。但是在打包之前合并可以节省洗牌，这是英特尔 CPU 上更大的吞吐量瓶颈。
如果我们可以添加而不是 OR（因为我们知道没有重叠位所以它是等价的），我们可以使用带符号的（第二个）操作数作为 2x vpmaddubsw（_mm256_maddubs_epi16） _mm256_set1_epi16(0x0110) 和无符号（第一个）输入保存数组中的数据以在每个字节对中执行 input[2*i+1] + (input[2*i] * 16)。然后 AND 和 VPACKUSWB / VPERMQ 从单词向下到字节元素并存储。