Bit manipulation instruction set

Bit manipulation instructions sets (BMI sets) are extensions to the x86 instruction set architecture for microprocessors from Intel and AMD. The purpose of these instruction sets is to improve the speed of bit manipulation. All the instructions in these sets are non-SIMD and operate only on general-purpose registers.

There are two sets published by Intel: BMI (here referred to as BMI1) and BMI2; they were both introduced with the Haswell microarchitecture. Another two sets were published by AMD: ABM (Advanced Bit Manipulation, which is also a subset of SSE4a implemented by Intel as part of SSE4.2 and BMI1), and TBM (Trailing Bit Manipulation, an extension introduced with Piledriver-based processors as an extension to BMI1, but dropped again in Zen-based processors).[1]

ABM (Advanced Bit Manipulation)

ABM is only implemented as a single instruction set by AMD; all AMD processors support both instructions or neither. Intel considers POPCNT as part of SSE4.2, and LZCNT as part of BMI1. POPCNT has a separate CPUID flag; however, Intel uses AMD's ABM flag to indicate LZCNT support (since LZCNT completes the ABM).[2]

Encoding Instruction Description[3]
F3 0F B8 /r POPCNT Population count
F3 0F BD /r LZCNT Leading zeros count

LZCNT is related to the Bit Scan Reverse (BSR) instruction, but sets the ZF (if the result is zero) and CF (if the source is zero) flags rather than setting the ZF (if the source is zero). Also, it produces a defined result (the source operand size in bits) if the source operand is zero. For a non-zero argument, sum of LZCNT and BSR results is argument bit width minus 1 (for example, if 32-bit argument is 0x000f0000, LZCNT gives 12, and BSR gives 19).

BMI1 (Bit Manipulation Instruction Set 1)

The instructions below are those enabled by the BMI bit in CPUID. Intel officially considers LZCNT as part of BMI, but advertises LZCNT support using the ABM CPUID feature flag.[2] BMI1 is available in AMD's Jaguar,[4] Piledriver[5] and newer processors, and in Intel's Haswell[6] and newer processors.

Encoding Instruction Description[2] Equivalent C expression[7][8]
VEX.LZ.0F38 F2 /r ANDN Logical and not ~x & y
VEX.LZ.0F38 F7 /r BEXTR Bit field extract (with register) (src >> start) & ((1 << len) - 1)
VEX.LZ.0F38 F3 /3 BLSI Extract lowest set isolated bit x & -x
VEX.LZ.0F38 F3 /2 BLSMSK Get mask up to lowest set bit x ^ (x - 1)
VEX.LZ.0F38 F3 /1 BLSR Reset lowest set bit x & (x - 1)
F3 0F BC /r TZCNT Count the number of trailing zero bits 31 + (!x)
  - (((x & -x) & 0x0000FFFF) ? 16 : 0)
  - (((x & -x) & 0x00FF00FF) ? 8 : 0)
  - (((x & -x) & 0x0F0F0F0F) ? 4 : 0)
  - (((x & -x) & 0x33333333) ? 2 : 0)
  - (((x & -x) & 0x55555555) ? 1 : 0)

TZCNT is almost identical to the Bit Scan Forward (BSF) instruction, but sets the ZF (if the result is zero) and CF (if the source is zero) flags rather than setting the ZF (if the source is zero). For a non-zero argument, the result of TZCNT and BSF is equal. Furthermore, the encodings are chosen such that a processor that does not implement ABM1 executes TZCNT as BSF. Likewise, a processor that does not implement TBM executes LZCNT as BSR.

BMI2 (Bit Manipulation Instruction Set 2)

Intel introduced BMI2 together with BMI1 in its line of Haswell processors. Only AMD has produced processors supporting BMI1 without BMI2; BMI2 is supported by AMDs Excavator architecture and newer.[9]

Encoding Instruction Description
VEX.LZ.0F38 F5 /r BZHI Zero high bits starting with specified bit position [src & (1 << inx)-1];
VEX.LZ.F2.0F38 F6 /r MULX Unsigned multiply without affecting flags, and arbitrary destination registers
VEX.LZ.F2.0F38 F5 /r PDEP Parallel bits deposit
VEX.LZ.F3.0F38 F5 /r PEXT Parallel bits extract
VEX.LZ.F2.0F3A F0 /r ib RORX Rotate right logical without affecting flags
VEX.LZ.F3.0F38 F7 /r SARX Shift arithmetic right without affecting flags
VEX.LZ.F2.0F38 F7 /r SHRX Shift logical right without affecting flags
VEX.LZ.66.0F38 F7 /r SHLX Shift logical left without affecting flags

Parallel bit deposit and extract

The PDEP and PEXT instructions are new generalized bit-level compress and expand instructions. They take two inputs; one is a source, and the other is a selector. The selector is a bitmap selecting the bits that are to be packed or unpacked. PEXT copies selected bits from the source to contiguous low-order bits of the destination; higher-order destination bits are cleared. PDEP does the opposite for the selected bits: contiguous low-order bits are copied to selected bits of the destination; other destination bits are cleared. This can be used to extract any bitfield of the input, and even do a lot of bit-level shuffling that previously would have been expensive. While what these instructions do is similar to bit level gather-scatter SIMD instructions, PDEP and PEXT instructions (like the rest of the BMI instruction sets) operate on general-purpose registers.[10]

The instructions are available in 32-bit and 64-bit versions. An example using arbitrary source and selector in 32-bit mode is:

InstructionSelector maskSourceDestination
PEXT0xff00fff00x123456780x00012567
PDEP0xff00fff00x000125670x12005670

AMD processors before Zen 3[11] that implement PDEP and PEXT do so in microcode, with a latency of 18 cycles[12] rather than a single cycle. As a result, if the mask is known, it is often faster to use other instructions on AMD.

TBM (Trailing Bit Manipulation)

TBM consists of instructions complementary to the instruction set started by BMI1; their complementary nature means they do not necessarily need to be used directly but can be generated by an optimizing compiler when supported. AMD introduced TBM together with BMI1 in its Piledriver[5] line of processors; later AMD Jaguar and Zen-based processors do not support TBM.[4] No Intel processors (at least through Coffee Lake) support TBM.

Encoding Instruction Description[3] Equivalent C expression[13]
XOP.LZ.0A 10 /r id BEXTR Bit field extract (with immediate) (src >> start) & ((1 << len) - 1)
XOP.LZ.09 01 /1 BLCFILL Fill from lowest clear bit x & (x + 1)
XOP.LZ.09 02 /6 BLCI Isolate lowest clear bit ~(x + 1)
XOP.LZ.09 01 /5 BLCIC Isolate lowest clear bit and complement ~x & (x + 1)
XOP.LZ.09 02 /1 BLCMSK Mask from lowest clear bit x ^ (x + 1)
XOP.LZ.09 01 /3 BLCS Set lowest clear bit (x + 1)
XOP.LZ.09 01 /2 BLSFILL Fill from lowest set bit (x - 1)
XOP.LZ.09 01 /6 BLSIC Isolate lowest set bit and complement (x - 1)
XOP.LZ.09 01 /7 T1MSKC Inverse mask from trailing ones (x + 1)
XOP.LZ.09 01 /4 TZMSK Mask from trailing zeros ~x & (x - 1)

Supporting CPUs

Note that instruction extension support means the processor is capable of executing the supported instructions for software compatibility purposes. The processor might not perform well doing so. For example, Excavator through Zen 2 processors implement PEXT and PDEP instructions using microcode resulting in the instructions executing significantly slower than the same behaviour recreated using other instructions.[15] (A software method called "zp7" is, in fact, faster on these machines.)[16] For optimum performance it is recommended that compiler developers choose to use individual instructions in the extensions based on architecture specific performance profiles rather than on extension availability.

See also

References
  1. "New "Bulldozer" and "Piledriver" Instructions" (PDF). Retrieved 2014-01-03.
  2. "Intel Advanced Vector Extensions Programming Reference" (PDF). intel.com. Intel. June 2011. Retrieved 2014-01-03.
  3. "AMD64 Architecture Programmer's Manual, Volume 3: General-Purpose and System Instructions" (PDF). amd.com. AMD. October 2013. Retrieved 2014-01-02.
  4. "Family 16h AMD A-Series Data Sheet" (PDF). amd.com. AMD. October 2013. Retrieved 2014-01-02.
  5. Hollingsworth, Brent. "New "Bulldozer" and "Piledriver" instructions" (pdf). Advanced Micro Devices, Inc. Retrieved 11 December 2014.
  6. Locktyukhin, Max. "How to detect New Instruction support in the 4th generation Intel® Core™ processor family". www.intel.com. Intel. Retrieved 11 December 2014.
  7. "bmiintrin.h from GCC 4.8". Retrieved 2014-03-17.
  8. https://github.com/abseil/abseil-cpp/blob/ce4bc927755fdf0ed03d679d9c7fa041175bb3cb/absl/base/internal/bits.h#L188
  9. "AMD Excavator Core May Bring Dramatic Performance Increases". X-bit labs. October 18, 2013. Archived from the original on October 23, 2013. Retrieved November 24, 2013.
  10. Yedidya Hilewitz; Ruby B. Lee (August 2009). "A New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations" (PDF). palms.princeton.edu. IEEE Transactions on Computers. pp. 1035–1048. Retrieved 2014-02-10.
  11. https://en.wikichip.org/wiki/amd/microarchitectures/zen_3#Key_changes_from_Zen_2
  12. https://www.agner.org/optimize/instruction_tables.pdf
  13. "tbmintrin.h from GCC 4.8". Retrieved 2014-03-17.
  14. "BIOS and Kernel Developer's Guide for AMD Family 14h" (PDF). Retrieved 2014-01-03.
  15. "Dolphin Emulator". Dolphin Emulator. Retrieved 2020-02-07.
  16. Wegner, Zach (4 November 2020). "zwegner/zp7".

Further reading
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.