assembly - PEXT 之类的汇编指令实际用于什么用途？

Question

我在 Top 10 Craziest Assembly Language Instructions 上观看了一个 youtube 视频其中一些说明对我没有明显的应用。 PEXT 之类的东西有什么意义，它只取第二个参数中与第一个参数中 1 的索引匹配的位？编译器如何知道何时使用该指令？关于无进位乘法的相同/相似问题。

免责声明:我对汇编语言知之甚少。也许我应该读一读!

我希望这个问题适合 stackoverflow。

Answer 1

您可以在论文中找到一些关于 PDEP/PEXT 硬件单元的应用程序

There are many emerging applications, such as cryptography, imaging and biometrics, where more advanced bit manipulation operations are needed. While these can be built from the simpler logical and shift operations, the applications using these advanced bit manipulation operations are significantly sped up if the processor can support more powerful bit manipulation instructions. Such operations include arbitrary bit permutations, performing multiple bit-field extract operations in parallel, and performing multiple bit-field deposit operations in parallel. We call these permutation (perm), parallel extract (pex) or bit gather, and parallel deposit (pdep) or bit scatter operations, respectively.

Performing Advanced Bit Manipulations Efficiently in General-Purpose Processors

位置换在 bitboards 中极为常见，例如反向字节/字或镜像位数组。有lots of algorithms在其中需要大量位操作，人们不得不 get creative to do that在 PEXT/PDEP 时代之前。后来许多纸牌游戏引擎也使用这种技术来处理一个或几个寄存器中的单个游戏集

PDEP/PEXT 还用于极大地提高比特交织性能，这在 Morton code 等算法中很常见.这方面的一些例子:

• How to de-interleave bits (UnMortonizing?)
• How to do bit striping on pixel data?
• What's a fast way to space-out bits within a word?
• How to create a byte out of 8 bool values (and vice versa)?

为位板发明的乘法技术也常用于 Bit Twiddling Hacks 中的许多算法中，例如 interleave bits with 64-bit multiply .当 PDEP/PEXT 可用时，不再需要此技术

您可以在 Bit permutations 中找到更多详细信息和 Hacker's Delight

PDEP/PEXT 的另一个用途是提取/组合位不在连续位置的字段，例如反汇编 RISC-V 指令，其中 immediates scatter around至make hardware design simpler但也使得在没有 PDEP/PEXT 的软件上工作有点困惑

其他一些应用:

I think the pext / pdep instructions have HUGE implications to 4-coloring problem, 3-SAT, Constraint Solvers, etc. etc. More researchers probably should look into those two instructions.

Just look at Binary Decision Diagrams, and other such combinatorial data structures, and you can definitely see the potential uses of PEXT / PDEP all over the place.

https://news.ycombinator.com/item?id=19137260

---

How would the compiler know when to use this instruction?

编译器可以识别常见模式并优化指令序列，但对于此类高级操作，程序员通常需要从高级代码中显式调用内部函数