检查多个比较结果向量中的每一个中至少有 1 个元素为真 - 水平 OR 然后 AND
Check that at least 1 element is true in each of multiple vectors of compare results - horizontal OR then AND
我正在寻找同一向量的分量之间的 SSE 按位或。 （编者按：这可能是一个X-Y问题，真正的比较逻辑见下文。）
我正在从 SPU 内部函数移植一些 SIMD 逻辑。它有一个指令
spu_orx(a)
其中根据docs
spu_orx: OR word across d = spu_orx(a) The four word elements of
vector a are logically Ored. The result is returned in word element 0
of vector d. All other elements (1,2,3) of d are assigned a value of
zero.
如何使用涉及最少指令的 SSE 2 - 4 来做到这一点？ _mm_or_ps 是我得到的。
更新：
这是基于 SPU 的代码的场景：
qword res = spu_orx(spu_or(spu_fcgt(x, y), spu_fcgt(z, w)))
所以它首先对两个 'greater' 比较进行 OR，然后对结果进行 OR。
这些结果的后面几对是 ANDed 以获得最终比较值。
这实际上是 (A||B||C||D||E||F||G||H) && (I||J||K||L||M||N||O||P) && ...，其中 A..D 是 fcgt(x,y) 的 4x 32 位元素，依此类推。
显然 _mm_cmp_ps 的垂直 _mm_or_ps 结果是减少到 1 个向量的好方法，但是那又怎样呢？随机播放 + OR，还是其他？
更新 1
关于 "but then what?"
我执行
qword res = spu_orx(spu_or(spu_fcgt(x, y), spu_fcgt(z, w)))
在 SPU 上是这样的：
qword aRes = si_and(res, res1);
qword aRes1 = si_and(aRes, res2);
qword aRes2 = si_and(aRes1 , res3);
return si_to_uint(aRes2 );
在不同的输入上多次，然后将它们全部合并为一个结果，最终转换为整数 0 或 1（false/true 测试）
SSE4.1 PTESTbool any_nonzero = !_mm_testz_si128(v,v);
这将是一个很好的方法来水平或 + 将向量布尔化为 0/1 整数。它将编译成多条指令，ptest same,same 本身就是 2 微指令。但是一旦你将结果作为标量整数，标量 AND 甚至比任何向量指令都便宜，你可以直接在结果上分支，因为它设置了整数标志。
#include <immintrin.h>
bool any_nonzero_bit(__m128i v) {
return !_mm_testz_si128(v,v);
}
On Godbolt 与 gcc9.1 -O3 -march=nehalem:
any_nonzero(long long __vector(2)):
ptest xmm0, xmm0 # 2 uops
setne al # 1 uop with false dep on old value of RAX
ret
在 Intel 上，对于整数寄存器中的单个位进行水平或运算仅需 3 微指令。 AMD Ryzen ptest 只有 1 uop 所以更好。
这里唯一的风险是如果 gcc 或 clang 在对 AL 执行 setcc 之前通过不 xor-zeroing eax 创建错误的依赖关系。通常 gcc 非常热衷于花费额外的 uops 来打破错误的依赖关系，所以我不知道为什么它不在这里。 （我确实检查了 -march=skylake 和 -mtune=generic 以防它依赖于 Nehalem partial-register 为 -march=nehalem 重命名。即使 -march=znver1 也没有得到 xor-zero Ptest 之前的 EAX。）
如果我们可以避免 _mm_or_ps 并让 PTEST 完成所有工作，那就太好了。但即使我们考虑反转比较，vertical-AND / horizontal-OR 行为也不会让我们检查 2 个向量的所有 8 个元素，或者 any这 8 个元素中的一个。
例如
// NOT USEFUL
// 1 if all the vertical pairs AND to zero.
// but 0 if even one vertical AND result is non-zero
_mm_testz_si128( _mm_castps_si128(_mm_cmpngt_ps(x,y)),
_mm_castps_si128(_mm_cmpngt_ps(z,w)));
我提这个只是为了排除它，省去你考虑这个优化思路的麻烦。 （@chtz 在评论中建议。反转比较是一个好主意，对其他做事方式很有用。）
没有SSE4.1/延迟水平OR
我们或许可以延迟水平 ORing / 布尔化，直到组合多个向量的一些结果。这使得合并成本更高（imul 或其他），但在向量 -> 整数阶段与 PTEST 相比节省了 2 微指令。
x86 有便宜的矢量掩码->整数位图 _mm_movemask_ps。特别是如果您最终想根据结果进行分支，这可能是个好主意。 （但是 x86 也没有 || 指令对其输入进行布尔化，所以你不能只 & movemask 结果）。
你可以做的一件事是整数 乘法 movemask 结果：x * y 是 non-zero 当且仅当两个输入都是 non-zero .不像 x & y 对于 0b0101 &0b1010for example. (Our inputs are 4-bit movemask results andunsigned` 可能是假的是 32 位的，所以我们在溢出之前有一些空间）。 AMD Bulldozer 系列有一个未完全流水线化的整数乘法，因此这可能是旧 AMD CPU 的瓶颈。仅使用 32 位整数也适用于某些 low-power 具有较慢 64 位乘法的 CPU。
如果吞吐量比延迟更成为瓶颈，这可能会很好，尽管 movmskps 只能 运行 在一个端口上。
我不确定是否有更便宜的整数运算可以让我们稍后恢复 logical-AND 结果。添加不起作用；即使只有一个输入是 non-zero，结果也是 non-zero。如果我们最终只测试任何 non-zero 位，那么将位连接在一起（shift+or）当然也类似于 OR。我们不能只是按位 AND 因为 2 & 1 == 0，不像 2 && 1.
将其保持在矢量域中
4个元素的水平或需要多步.
显而易见的方式是_mm_movehl_ps + OR，然后再shuffle + OR。 （参见 Fastest way to do horizontal float vector sum on x86 但将 _mm_add_ps 替换为 _mm_or_ps）
但是由于当我们的输入是比较结果时我们实际上并不需要精确的 bitwise-OR，所以我们只关心是否有任何元素是 non-zero。我们可以而且应该将向量视为整数，并查看像 64 位元素 == 这样的整数指令。一个 64 位元素 covers/aliases 两个 32 位元素。
__m128i cmp = _mm_castps_si128(cmpps_result); // reinterpret: zero instructions
// SSE4.1 pcmpeqq 64-bit integer elements
__m128i cmp64 = _mm_cmpeq_epi64(cmp, _mm_setzero_si128()); // -1 if both elements were zero, otherwise 0
__m128i swap = _mm_shuffle_epi32(cmp64, _MM_SHUFFLE(1,0, 3,2)); // copy and swap, no movdqa instruction needed even without AVX
__m128i bothzero = _mm_and_si128(cmp64, swap); // both halves have the full result
在这个逻辑倒置之后，将多个 bothzero 结果 进行或运算将得到您要查找的多个条件的 AND。
或者，如果任一 qword 为零，SSE4.1 _mm_minpos_epu16(cmp64) (phminposuw) 将在 1 uop（但 5 个周期延迟）内告诉我们。在这种情况下，它将把 0 或 0xFFFF 放在结果的最低字（16 位）中。
如果我们反转原来的比较，我们可以在上面使用 phminposuw（没有 pcmpeqq）来检查是否有零。 所以基本上是水平 AND 横跨整个向量。 （假设它是 0 / -1 的元素）。我认为这对于反向输入来说是一个有用的结果。 （并使我们免于使用 _mm_xor_si128 翻转位）。
pcmpeqq (_mm_cmpeq_epi64) 的替代方法是 SSE2 psadbw 针对零向量得到 0 或 non-zero 结果在每个 64 位的底部元素。不过，它不会是面具，而是 0xFF * 8。不过，它始终是 that 或 0，因此您仍然可以 AND 它。而且它不会反转。
我正在寻找同一向量的分量之间的 SSE 按位或。 （编者按：这可能是一个X-Y问题，真正的比较逻辑见下文。）
我正在从 SPU 内部函数移植一些 SIMD 逻辑。它有一个指令
spu_orx(a)
其中根据docs
spu_orx: OR word across d = spu_orx(a) The four word elements of vector a are logically Ored. The result is returned in word element 0 of vector d. All other elements (1,2,3) of d are assigned a value of zero.
如何使用涉及最少指令的 SSE 2 - 4 来做到这一点？ _mm_or_ps 是我得到的。
更新：
这是基于 SPU 的代码的场景：
qword res = spu_orx(spu_or(spu_fcgt(x, y), spu_fcgt(z, w)))
所以它首先对两个 'greater' 比较进行 OR，然后对结果进行 OR。 这些结果的后面几对是 ANDed 以获得最终比较值。
这实际上是 (A||B||C||D||E||F||G||H) && (I||J||K||L||M||N||O||P) && ...，其中 A..D 是 fcgt(x,y) 的 4x 32 位元素，依此类推。
显然 _mm_cmp_ps 的垂直 _mm_or_ps 结果是减少到 1 个向量的好方法，但是那又怎样呢？随机播放 + OR，还是其他？
更新 1
关于 "but then what?" 我执行
qword res = spu_orx(spu_or(spu_fcgt(x, y), spu_fcgt(z, w)))
在 SPU 上是这样的：
qword aRes = si_and(res, res1);
qword aRes1 = si_and(aRes, res2);
qword aRes2 = si_and(aRes1 , res3);
return si_to_uint(aRes2 );
在不同的输入上多次，然后将它们全部合并为一个结果，最终转换为整数 0 或 1（false/true 测试）
SSE4.1 PTESTbool any_nonzero = !_mm_testz_si128(v,v);
这将是一个很好的方法来水平或 + 将向量布尔化为 0/1 整数。它将编译成多条指令，ptest same,same 本身就是 2 微指令。但是一旦你将结果作为标量整数，标量 AND 甚至比任何向量指令都便宜，你可以直接在结果上分支，因为它设置了整数标志。
#include <immintrin.h>
bool any_nonzero_bit(__m128i v) {
return !_mm_testz_si128(v,v);
}
On Godbolt 与 gcc9.1 -O3 -march=nehalem:
any_nonzero(long long __vector(2)):
ptest xmm0, xmm0 # 2 uops
setne al # 1 uop with false dep on old value of RAX
ret
在 Intel 上，对于整数寄存器中的单个位进行水平或运算仅需 3 微指令。 AMD Ryzen ptest 只有 1 uop 所以更好。
这里唯一的风险是如果 gcc 或 clang 在对 AL 执行 setcc 之前通过不 xor-zeroing eax 创建错误的依赖关系。通常 gcc 非常热衷于花费额外的 uops 来打破错误的依赖关系，所以我不知道为什么它不在这里。 （我确实检查了 -march=skylake 和 -mtune=generic 以防它依赖于 Nehalem partial-register 为 -march=nehalem 重命名。即使 -march=znver1 也没有得到 xor-zero Ptest 之前的 EAX。）
如果我们可以避免 _mm_or_ps 并让 PTEST 完成所有工作，那就太好了。但即使我们考虑反转比较，vertical-AND / horizontal-OR 行为也不会让我们检查 2 个向量的所有 8 个元素，或者 any这 8 个元素中的一个。
例如
// NOT USEFUL
// 1 if all the vertical pairs AND to zero.
// but 0 if even one vertical AND result is non-zero
_mm_testz_si128( _mm_castps_si128(_mm_cmpngt_ps(x,y)),
_mm_castps_si128(_mm_cmpngt_ps(z,w)));
我提这个只是为了排除它，省去你考虑这个优化思路的麻烦。 （@chtz 在评论中建议。反转比较是一个好主意，对其他做事方式很有用。）
没有SSE4.1/延迟水平OR
我们或许可以延迟水平 ORing / 布尔化，直到组合多个向量的一些结果。这使得合并成本更高（imul 或其他），但在向量 -> 整数阶段与 PTEST 相比节省了 2 微指令。
x86 有便宜的矢量掩码->整数位图 _mm_movemask_ps。特别是如果您最终想根据结果进行分支，这可能是个好主意。 （但是 x86 也没有 || 指令对其输入进行布尔化，所以你不能只 & movemask 结果）。
你可以做的一件事是整数 乘法 movemask 结果：x * y 是 non-zero 当且仅当两个输入都是 non-zero .不像 x & y 对于 0b0101 &0b1010for example. (Our inputs are 4-bit movemask results andunsigned` 可能是假的是 32 位的，所以我们在溢出之前有一些空间）。 AMD Bulldozer 系列有一个未完全流水线化的整数乘法，因此这可能是旧 AMD CPU 的瓶颈。仅使用 32 位整数也适用于某些 low-power 具有较慢 64 位乘法的 CPU。
如果吞吐量比延迟更成为瓶颈，这可能会很好，尽管 movmskps 只能 运行 在一个端口上。
我不确定是否有更便宜的整数运算可以让我们稍后恢复 logical-AND 结果。添加不起作用；即使只有一个输入是 non-zero，结果也是 non-zero。如果我们最终只测试任何 non-zero 位，那么将位连接在一起（shift+or）当然也类似于 OR。我们不能只是按位 AND 因为 2 & 1 == 0，不像 2 && 1.
将其保持在矢量域中
4个元素的水平或需要多步.
显而易见的方式是_mm_movehl_ps + OR，然后再shuffle + OR。 （参见 Fastest way to do horizontal float vector sum on x86 但将 _mm_add_ps 替换为 _mm_or_ps）
但是由于当我们的输入是比较结果时我们实际上并不需要精确的 bitwise-OR，所以我们只关心是否有任何元素是 non-zero。我们可以而且应该将向量视为整数，并查看像 64 位元素 == 这样的整数指令。一个 64 位元素 covers/aliases 两个 32 位元素。
__m128i cmp = _mm_castps_si128(cmpps_result); // reinterpret: zero instructions
// SSE4.1 pcmpeqq 64-bit integer elements
__m128i cmp64 = _mm_cmpeq_epi64(cmp, _mm_setzero_si128()); // -1 if both elements were zero, otherwise 0
__m128i swap = _mm_shuffle_epi32(cmp64, _MM_SHUFFLE(1,0, 3,2)); // copy and swap, no movdqa instruction needed even without AVX
__m128i bothzero = _mm_and_si128(cmp64, swap); // both halves have the full result
在这个逻辑倒置之后，将多个 bothzero 结果 进行或运算将得到您要查找的多个条件的 AND。
或者，如果任一 qword 为零，SSE4.1 _mm_minpos_epu16(cmp64) (phminposuw) 将在 1 uop（但 5 个周期延迟）内告诉我们。在这种情况下，它将把 0 或 0xFFFF 放在结果的最低字（16 位）中。
如果我们反转原来的比较，我们可以在上面使用 phminposuw（没有 pcmpeqq）来检查是否有零。 所以基本上是水平 AND 横跨整个向量。 （假设它是 0 / -1 的元素）。我认为这对于反向输入来说是一个有用的结果。 （并使我们免于使用 _mm_xor_si128 翻转位）。
pcmpeqq (_mm_cmpeq_epi64) 的替代方法是 SSE2 psadbw 针对零向量得到 0 或 non-zero 结果在每个 64 位的底部元素。不过，它不会是面具，而是 0xFF * 8。不过，它始终是 that 或 0，因此您仍然可以 AND 它。而且它不会反转。