Intel AVX2是否有movemask指令的反向指令？

Question

Intel AVX2是否有movemask指令的反向指令？

x86intrinsicsavxavx2icc

12

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

我想做相反的操作：取一个32位整数（其中只有4、8或32位的最低有效位是有意义的），并获取一个__m256i，其中每个int8、int32或int64大小块的最高有效位都设置为原始位。

基本上，我想从压缩的位掩码转换为可由其他AVX2指令（如maskstore、maskload、mask_gather）使用的掩码。

我找不到快速的实现方法，所以在这里询问。如果没有具备该功能的单个指令，您能否想到一种聪明的技巧，在非常少的指令中实现这一点？

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

- orm

1

可能是重复的问题如何执行 _mm256_movemask_epi8 (VPMOVMSKB) 的反操作? - Peter Cordes

那个潜在的重复问题上有很多好答案，但它们大多考虑了8位元素情况。我在这里的答案只涵盖了32位元素情况。(因为变量移位对于较窄的元素不存在) - Peter Cordes

只是好奇，为什么你没有接受任何答案？ - aepot

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter Cordes · Accepted Answer

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

4位 -> 4个qwords在一个YMM寄存器中：这个答案是：查找表（LUT）很好，算术逻辑单元（ALU）也很好。
8位 -> 8个dwords在一个YMM寄存器中：这个答案（或者没有AVX2的情况下）。ALU。
16位 -> 16个words：这个答案使用vpbroadcastw / vpand / vpcmpeqw。
32位 -> 32个bytes：
如何执行_mm256_movemask_epi8（VPMOVMSKB）的逆操作？
还有将32位展开为32字节SIMD向量的最快方法。

8位 -> 8字节或者没有AVX2的字（word）：如何高效地将8位位图转换为0/1整数数组，使用x86 SIMD非常便宜，尽管没有SSSE3的8位或16位掩码广播可能会导致多次洗牌。

请注意使用_mm_min_epu8(v, _mm_set1_epi8(1))这个技巧
而不是使用_mm_cmpeq_epi8来获得0/1而不是0/FF。

16位 -> 使用SSE2或SSSE3转换为16字节，或者AVX-512：将16位掩码转换为16字节掩码。
（还有用于unsigned __int128的BMI2，纯C++乘法位操作技巧，以及用于获得0/1而不是0/-1的AVX-512示例）

8位 -> 8字节：如果您只需要每次处理8位，那么标量乘法技巧可能更好：如何通过8个布尔值创建一个字节（反之亦然）。

对于您的情况，如果您从内存中加载位图，则直接将其加载到矢量寄存器中以进行ALU策略应该效果很好，即使是4位掩码也可以。

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

我们将不得不等待AVX-512的掩码寄存器，才能实现从整数位屏蔽转换为矢量屏蔽的廉价方法。（使用kmovw k1, r/m16，编译器会隐式为int => __mmask16生成）。有一个AVX512指令可以根据掩码设置矢量（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指令可用，使用广播加载+可变移位仍然更好。

另外，还有一种可能性（对于0/1的结果而不是0/-1），可以从常量进行零掩码加载，例如_mm_maskz_mov_epi8(mask16, _mm_set1_epi8(1))。https://godbolt.org/z/1sM8hY8Tj

对于64位元素，掩码只有4位，所以使用查找表是合理的。您可以通过使用`VPMOVSXBQ ymm1, xmm2/m32`（`_mm256_cvtepi8_epi64`）来压缩LUT。这将使LUT的大小为(1<<4) = 16 * 4字节 = 64B = 1个缓存行。不幸的是，`pmovsx`在使用内部函数时不方便使用窄加载。

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

32位元素的查找表（LUT）：可能不是最优解，但以下是你可以实现的方法。

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

为了解决这个问题，你可以将LUT分成4位块。将一个8位整数拆分成两个4位整数需要大约3条整数指令（mov/and/shr）。然后，对于128位向量的未压缩LUT（适用于32位元素大小），使用vmovdqa加载低半部分，再使用vinserti128加载高半部分。你仍然可以压缩LUT，但我不建议这样做，因为你将需要vmovd / vpinsrd / vpmovsxbd，这涉及2次洗牌操作（所以你可能会受到uop吞吐量的限制）。

或者2倍 vpmovsxbd xmm, [lut + rsi*4] + vinserti128 在英特尔上可能更糟糕。

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

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

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

掩码可以来自带有vmovd + vpbroadcastd的整数寄存器，但如果它已经在内存中，广播加载是廉价的，例如从一个掩码数组应用于一个元素数组。实际上，我们只关心该双字的低8位，因为8个32位元素= 32字节（例如，您从vmovmaskps获得的）。对于16个16位元素的16位掩码，您需要vpbroadcastw。要首先从16位整数向量获取这样的掩码，您可以将两个向量一起vpacksswb（保留每个元素的符号位），然后vpermq将元素放入顺序后的in-lane pack，然后vpmovmskb。

对于8位元素，您需要使用vpshufb将vpbroadcastd的结果进行重排，以便将相关位放入每个字节中。请参阅如何执行_mm256_movemask_epi8（VPMOVMSKB）的逆操作？。但是对于16位及更宽的元素，元素数量≤元素宽度，因此广播加载可以免费完成。（与32位和64位广播加载完全在加载端口中处理不同，16位广播加载会产生一个微融合ALU洗牌微操作成本。）

vpbroadcastd/q甚至不需要任何ALU uops, 它直接在加载端口完成。 (b和w是加载+洗牌)。即使您的掩码紧凑地放在一起(每个字节对应32位或64位元素)，与其使用vpbroadcastb，使用vpbroadcastd可能更高效。在广播之后，x & mask == mask检查不关心每个元素高字节中的垃圾数据。唯一需要担心的是缓存行/页面分割。

变量位移（Skylake 上更便宜），如果只需要符号位

变量混合和掩码加载/存储只关心掩码元素的符号位。

一旦将 8 位掩码广播到双字元素，这只是 1 个微操作（在 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洗牌uop，但可能不需要在Ryzen上。

变量移位在Haswell/Broadwell上稍微昂贵（3个uop，受限执行端口），但在Skylake上与立即数移位一样廉价！（在端口0或1上的1个uop。）在Zen 3之前的AMD上，它们不会额外消耗uop，但速度较慢（3周期延迟，吞吐量为正常移位uop的四分之一）。在Zen 1上，这是额外糟糕的，因为256位操作通常作为2个uop运行。但这并不是灾难，尤其是如果其他uop可以在它们占用额外周期时使用同一端口上的其他执行单元（我不知道是否可能）。在Zen 3及更高版本上，它们的性能与Skylake相当，1个周期延迟，0.5个周期吞吐量。

请参阅x86标签维基以获取性能信息，尤其是Agner Fog的指令表和https://uops.info/。

对于64位元素，请注意算术右移仅适用于16位和32位元素大小。如果您希望将整个元素集设置为全零/全一以进行4位-> 64位元素的操作，请使用不同的策略。

使用内部函数：

// AVX2, most efficient on Skylake and Zen 3 and later
// if you just need the MSBs set.  Otherwise still use and/cmpeq
__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, not two shifts.
    // would work but not worth it: 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到向量中）可能更好，因为广播加载非常便宜。

请注意，在Zen 1和Zen 2上，pdep是6个相关的微操作（18个周期延迟，18个周期吞吐量，或者取决于位数而更差），因此即使您的掩码确实起始于整数寄存器，这种方法在Ryzen上效果很差。 Zen 3及更高版本具有专用的pext / pdep硬件，并将它们像Intel一样高效地执行，作为单个微操作。

（未来的读者可以随意编辑这个版本的内部函数。使用汇编语言编写更容易，因为打字较少，汇编助记符更易读（不会在各处弄乱_mm256_之类的愚蠢字符）。）