PDEP Visualization PEXT Visualization
Here is an overview of which ISA's support these instructions:
- BESM Soviet mainframes:
- x86-64:
- arm64 / aarch64:
- PowerPC:
- RISC-V:
- Zbe => attempted to add
bcompress/bdecompress, but did not get ratified into theBinstruction set
- Zbe => attempted to add
- IBM Z mainframe:
- z17 => BDEPG and BEXTG were added via "miscellaneous-instruction-extensions facility 4" (MI4)
x86-64 performs these operations on general purpose registers, whereas ARM performs these on vector registers. PowerPC supports the operations on both general purpose and vector registers. The jury is still out on RISC-V. The IBM z17 operates on general purpose registers.
The RISC-V B instruction set discussions indicate that the 'P' in 'PDEP' and 'PEXT', meaning parallel, refers to a property of the internal implementation of those operations (typically implemented via a "butterfly network"). I used to accept this framing, and now I do not. The "parallel" does, in fact, describe what the operations do. If I pext with a mask of 0b100010001 then I am extracting 3 bits at the specified positions in parallel. The problem with the bext terminology is that "bit extract" is a highly ambiguous and overloaded term. On RISC-V, their bext operation extracts a single bit. On x86-64, bextr extracts some contiguous bits. LLVM is introducing bitinsert and bitextract operations that operate on contiguous groups of bits. I also think pdep and pext are the "traditional" names for these operations and you can find materials about them online. The bdep and bext names are thus an unwelcome break from over a decade of precedent and future projects should not adopt such terminology.
- succinct "select", i.e. find k'th set bit in a bitstring
- unset k 1 bits
- on x86, one day, I imagine that under certain circumstances a compiler would want to convert some vector logic into SWAR logic, to overcome the latency of moving between vector and general purpose registers. If that ever were to occur, PDEP could fill in code like this:
(I also think I could have used a per-element vector shift, but in context, I used
const byte_indices = comptime switch (builtin.cpu.arch.endian()) { .little => @as(@Vector(8, u8), @splat(1)) << std.simd.iota(u3, 8), .big => @as(@Vector(8, u8), @splat(0x80)) >> std.simd.iota(u3, 8), }; const splatted = @as(@Vector(8, u8), @splat(x)); const selector = (splatted & byte_indices) != byte_indices; const splatted_lsbs: u64 = @bitCast(@select(u8, selector, @splat(1), @splat(0))); // all of the above is equivalent to: pdep(x, 0x0101010101010101)
selectoragain for something else, so it made sense in my real code)
- bit-reversing a byte
- concentrating bits to the least-significant bit position that are not contiguous
I also have a little bit of ongoing work on some pext-emulation for when the mask is known at compile time. It's still pretty rudimentary, but it's better than nothing.
https://gist.github.com/Validark/40d2df74b87692fe135bbeac14eed50d
I have a few emulation routines, and have plans to add at least one more. It checks the number of bitgroups, and if sufficiently low, it might lower to regular shifts. I also have one where we use multiplication to concentrate the bits into the upper 64-bits, and then move it back to the LSb. I plan on adding another multiplication routine that would use an extra addition to try to move bits into locations where they are far enough away from other bits that a multiplication would be sufficient (if it was not before). E.g. pext(x, 0x8040201008040201) would become (((x & 0x8040201008040201) + (0x8080808080808080 - 0x8040201008040201)) * 0x0002040810204081) >> 56
More:
As of z17, IBM Z mainframe supports these operations on general purpose registers with BDEPG and BEXTG instructions.