x86 - 英特尔avx2中的movemask指令是否有反指令？

Question

movemask指令使用__m256i并返回int32，其中每个位（前4位，8位或全部32位，取决于输入矢量元素的类型）是相应矢量元素的最高有效位。

我想反过来：取一个32（只有4、8或32个最低有效位才有意义），然后得到一个__m256i，其中每个int8，int32或int64大小的块的最高有效位都设置为原始一点。

基本上，我想从压缩的位掩码转到可以被其他AVX2指令（例如maskstore，maskload，mask_gather）用作掩码的位掩码。

我无法快速找到执行该指令的指令，所以我在这里问。
如果没有一个具有该功能的指令，那么您能想到的巧妙的技巧可以在很少的指令中实现这一目标吗？

我当前的方法是使用256个元素的查找表。
我想在没有太多其他事情发生的循环中使用此操作，以加快速度。注意，我对长的多指令序列或实现此操作的小循环不太感兴趣。

Answer 1

在AVX2或更早的版本中没有单一指令。 （AVX512可以以位图形式使用掩码，并具有将其扩展为矢量的指令）。


YMM寄存器中的4位-> 4个qwords：此答案：LUT很好，ALU也很好
YMM寄存器中的8位-> 8个双字：此答案（或this without AVX2）。 ALU。
16位-> 16个字：vpbroadcastw / vpand / vpcmpeqw的答案
32位-> 32字节：
How to perform the inverse of _mm256_movemask_epi8 (VPMOVMSKB)?
也是Fastest way to unpack 32 bits to a 32 byte SIMD vector。


如果要从内存中加载位图，则应将其直接加载到用于ALU策略的向量寄存器中。

如果将位图作为计算结果，则它将位于整数寄存器中，可以在其中轻松地将其用作LUT索引，因此，如果您针对64位元素，这是一个不错的选择。否则，对于32位或更小的元素，仍可能会使用ALU，而不是使用大型LUT或执行多个块。



我们必须等待AVX-512的掩码寄存器，然后才能进行从整数位掩码到矢量掩码的廉价转换。 （对于kmovw k1, r/m16，编译器将为int => __mmask16隐式生成该代码）。有一个AVX512 insn可以从掩码（VPMOVM2D zmm1, k1，_mm512_movm_epi8/16/32/64，以及其他版本的元素大小不同的其他版本）设置向量，但是您通常不需要它，因为以前所有用于掩码向量的东西现在都使用掩码寄存器。也许您是否想计算满足比较条件的元素？ （您将使用pcmpeqd / psubd生成并累积0或-1个元素的向量）。但是掩码结果上的标量popcnt是更好的选择。

但是请注意，vpmovm2d要求掩码必须位于AVX512 k0..7掩码寄存器中。除非它来自矢量比较结果，否则将获得额外的指令，并且移入掩码寄存器的指令需要Intel Skylake-X和类似CPU上端口5的uop，因此这可能成为瓶颈（尤其是如果您进行了任何改组） ）。特别是如果它从内存中开始（加载位图）并且您只需要每个元素的高位，即使有256位和512位AVX512指令可用，广播负载+可变移位也可能会更好。



对于64位元素，掩码仅具有4位，因此查找表是合理的。您可以通过加载VPMOVSXBQ ymm1, xmm2/m32. (_mm256_cvtepi8_epi64)来压缩LUT。这使您的LUT大小为（1 << 4）= 16 * 4字节= 64B = 1个缓存行。不幸的是，pmovsx is inconvenient to use as a narrow load with intrinsics。

特别是如果您已经将位图保存在一个整数寄存器（而不是内存）中，则vpmovsxbq LUT在用于64位元素的内部循环内应该是出色的。或者，如果指令吞吐量或混洗吞吐量成为瓶颈，请使用未压缩的LUT。这可以让您（或编译器）将掩码向量用作其他内容的内存操作数，而不需要单独的指令来加载它。



适用于32位元素的LUT：可能不是最佳选择，但是这是您可以做到的

对于32位元素，一个8位掩码可为您提供256个可能的向量，每个向量长8个元素。 256 * 8B = 2048字节，即使对于压缩版本（使用vpmovsxbd ymm, m64加载），这也是相当大的缓存占用空间。

要解决此问题，您可以将LUT分成4位块。将一个8位整数分成两个4位整数（mov/and/shr）需要大约3个整数指令。然后使用未压缩的128b向量的LUT（对于32位元素大小），vmovdqa下半部分和vinserti128高下半部分。您仍然可以压缩LUT，但我不建议这样做，因为您需要vmovd / vpinsrd / vpmovsxbd，这是2个混洗（因此您可能会限制uop吞吐量）。

或者在Intel上2x vpmovsxbd xmm, [lut + rsi*4] + vinserti128可能更糟。



ALU替代：适用于16/32/64位元素

当整个位图适合每个元素时：广播它，并使用选择器掩码与AND进行广播，并针对相同的常量进行VPCMPEQ（可以在循环中多次使用时保留在寄存器中）。

vpbroadcastd  ymm0,  dword [mask]
vpand         ymm0, ymm0,  setr_epi32(1<<0, 1<<1, 1<<2, 1<<3, ..., 1<<7)
vpcmpeqd      ymm0, ymm0,  [same constant]
      ; ymm0 =  (mask & bit) == bit
      ; where bit = 1<<element_number

掩码可以来自带有vmovd + vpbroadcastd的整数寄存器，但是如果广播负载已经存在于内存中，则它的广播负载很便宜，例如从遮罩数组应用于元素数组。实际上，我们只关心该dword的低8位，因为8x 32位元素= 32字节。 （例如，您来自vmovmaskps）。对于16x 16位元素，使用16位掩码时，您需要vpbroadcastw。要从16位整数向量中首先获得这样的掩码，可以将vpacksswb两个向量放在一起（保留每个元素的符号位），vpermq将元素在车道内包装后按顺序排列，然后是vpmovmskb。

对于8位元素，您需要vpshufb vpbroadcastd结果才能将相关位放入每个字节。请参见How to perform the inverse of _mm256_movemask_epi8 (VPMOVMSKB)?。但是对于16位及更宽的元素，元素的数量<=元素的宽度，因此广播负载是免费提供的。 （与完全在加载端口中处理的32位和64位广播负载不同，16位广播负载的确会花费微融合的ALU shuffle uop。）

vpbroadcastd/q甚至不花费任何ALU运算符，它是在加载端口中完成的。 （b和w是load + shuffle）。即使将您的掩码打包在一起（对于32或64位元素，每个字节占用一个字节），对于vpbroadcastd而不是vpbroadcastb来说，效率可能更高。 x & mask == mask检查不在乎广播后每个元素的高字节中的垃圾。唯一担心的是缓存行/页面拆分。



如果只需要符号位，则进行可变移位（在Skylake上更便宜）

可变混合和蒙版加载/存储仅关心蒙版元素的符号位。

一旦将8位掩码广播到dword元素，则只有1 uop（在Skylake上）。

vpbroadcastd  ymm0, dword [mask]

vpsllvd       ymm0, ymm0, [vec of 24, 25, 26, 27, 28, 29, 30, 31]  ; high bit of each element = corresponding bit of the mask

;vpsrad        ymm0, ymm0, 31                          ; broadcast the sign bit of each element to the whole element
;vpsllvd + vpsrad has no advantage over vpand / vpcmpeqb, so don't use this if you need all the bits set.

vpbroadcastd与从内存加载一样便宜（在Intel CPU和Ryzen上根本没有ALU uop）。 （较窄的广播，例如vpbroadcastb y,mem在Intel上采用ALU随机播放，但在Ryzen上则不行。）

可变移位在Haswell / Broadwell上稍微贵一点（3 oups，有限的执行端口），但与Skylake的即时计数移位一样便宜！ （在端口0或1上为1 uop。）在Ryzen上，它们也仅为2 uops（任何256b操作的最小值），但是具有3c延迟和每4c吞吐量一个。

有关性能信息，请参见x86标记Wiki，尤其是Agner Fog's insn tables。

对于64位元素，请注意，算术右移仅在16位和32位元素大小中可用。如果希望将整个元素设置为4位-> 64位元素的全零/全1，则使用不同的策略。

具有内在函数：

__m256i bitmap2vecmask(int m) {
    const __m256i vshift_count = _mm256_set_epi32(24, 25, 26, 27, 28, 29, 30, 31);
    __m256i bcast = _mm256_set1_epi32(m);
    __m256i shifted = _mm256_sllv_epi32(bcast, vshift_count);  // high bit of each element = corresponding bit of the mask
    return shifted;

    // use _mm256_and and _mm256_cmpeq if you need all bits set.
    //return _mm256_srai_epi32(shifted, 31);             // broadcast the sign bit to the whole element
}

在循环内部，根据循环中的指令组合，LUT可能值得缓存占用空间。尤其是对于64位元素的大小（缓存占用不多），甚至对于32位也是如此。



替代变量移位的另一种方法是，使用BMI2将每个位解压缩为一个字节，并将掩码元素放在高位，然后vpmovsx：

; 8bit mask bitmap in eax, constant in rdi

pdep      rax, rax, rdi   ; rdi = 0b1000000010000000... repeating
vmovq     xmm0, rax
vpmovsxbd ymm0, xmm0      ; each element = 0xffffff80 or 0

; optional
;vpsrad    ymm0, ymm0, 8   ; arithmetic shift to get -1 or 0

如果整数寄存器中已经有掩码（无论如何都必须分别vmovq / vpbroadcastd），那么即使在变量计数移位便宜的Skylake上，这种方法也可能更好。

如果您的掩码从内存中开始，则另一种ALU方法（直接将vpbroadcastd转换为向量）可能会更好，因为广播负载非常便宜。

请注意，pdep是Ryzen上的6个相关联的uop（18c延迟，18c吞吐量），因此即使您的掩码确实以整数regs开始，此方法在Ryzen上也是可怕的。

（未来的读者可以随时使用此函数的内在版本进行编辑。编写asm会更容易，因为它的键入要少得多，并且asm助记符也更易于阅读（到处都不会出现愚蠢的_mm256_）。）