Bit Manipulation Instruction Sets
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).[1]
In the description of a patch to the GNU binutils package, AMD explicitly revealed that the first iteration of "Zen", its third-generation x86-64 architecture, will not support TBM, XOP and LWP instructions developed specifically for the "Bulldozer" microarchitecture.[2]
Contents
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).[3]
| Instruction | Description[4] |
|---|---|
POPCNT |
Population count |
LZCNT |
Leading zeros count |
LZCNT is almost identical 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 OF, and produces a defined result (the source operand size in bits) if the source operand is zero.
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.[3] BMI1 is available in AMD's Jaguar,[5] Piledriver[6] and newer processors, and in Intel's Haswell[7] and newer processors.
| Instruction | Description[3] | Equivalent C expression[8] |
|---|---|---|
ANDN |
Logical and not | ~x & y |
BEXTR |
Bit field extract (with register) | (src >> start) & ((1 << len)-1)[9] |
BLSI |
Extract lowest set isolated bit | x & -x |
BLSMSK |
Get mask up to lowest set bit | x ^ (x - 1) |
BLSR |
Reset lowest set bit | x & (x - 1) |
TZCNT |
Count the number of trailing zero bits | N/A |
BMI2 (Bit Manipulation Instruction Set 2)
Intel introduced BMI2 together with BMI1 in its line of Haswell processors. Only AMD has produced processors supporting only BMI1 without BMI2; BMI2 is supported by AMDs newest Excavator architecture.[10]
| Instruction | Description |
|---|---|
BZHI |
Zero high bits starting with specified bit position |
MULX |
Unsigned multiply without affecting flags, and arbitrary destination registers |
PDEP |
Parallel bits deposit |
PEXT |
Parallel bits extract |
RORX |
Rotate right logical without affecting flags |
SARX |
Shift arithmetic right without affecting flags |
SHRX |
Shift logical right without affecting flags |
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 a bit level gather-scatter SIMD instructions, PDEP and PEXT instructions (like the rest of the BMI instruction sets) operate on general-purpose registers.[11][12]
Below are a few 8-bit examples of these operations:[citation needed]
| Input | Selector example | Parallel bit extract | Parallel bit deposit |
|---|---|---|---|
| abcd'efgh | 1111'0000 | 0000'abcd | efgh'0000 |
| abcd'efgh | 1111'1100 | 00ab'cdef | cdef'gh00 |
| abcd'efgh | 0101'0101 | 0000'bdfh | 0e0f'0g0h |
| abcd'efgh | 1101'1101 | 00ab'defh | cd0e'fg0h |
| abcd'efgh | 0001'1111 | 000d'efgh | 000d'efgh |
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.[13] AMD introduced TBM together with BMI1 in its Piledriver[6] line of processors; AMD Jaguar and upcoming Zen processors do not support TBM.[5]
| Instruction | Description[4] | Equivalent C expression[14] |
|---|---|---|
BEXTR |
Bit field extract (with immediate) | (src >> start) & ((1 << len)-1) |
BLCFILL |
Fill from lowest clear bit | x & (x + 1) |
BLCI |
Isolate lowest clear bit | x | ~(x + 1) |
BLCIC |
Isolate lowest clear bit and complement | ~x & (x + 1) |
BLCMASK |
Mask from lowest clear bit | x ^ (x + 1) |
BLCS |
Set lowest clear bit | x | (x + 1) |
BLSFILL |
Fill from lowest set bit | x | (x - 1) |
BLSIC |
Isolate lowest set bit and complement | ~x | (x - 1) |
T1MSKC |
Inverse mask from trailing ones | ~x | (x + 1) |
TZMSK |
Mask from trailing zeros | ~x & (x - 1) |
Supporting CPUs
- Intel
- Intel Nehalem processors and newer (like Sandy Bridge, Ivy Bridge) (POPCNT supported)
- Intel Silvermont processors (POPCNT supported)
- Intel Haswell processors and newer (like Skylake, Broadwell) (ABM, BMI1 and BMI2 supported)[7]
- AMD
- AMD Barcelona-based processors and newer (ABM supported)
- AMD Piledriver-based processors (ABM, BMI1 and TBM supported)[1]
- AMD Steamroller-based processors (ABM, BMI1 and TBM supported)
- AMD Excavator-based processors (ABM, BMI1, BMI2 and TBM supported)[10]
- AMD Bobcat-based processors (ABM supported)[15]
- AMD Jaguar- and Puma-based processors (ABM and BMI1 supported)[5]
- AMD Zen-based processors (ABM, BMI1 and BMI2 supported)
See also
.gif){kind=small}
<templatestyles src="Div col/styles.css"/>
References
- ↑ 1.0 1.1 Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ 3.0 3.1 3.2 Lua error in package.lua at line 80: module 'strict' not found.
- ↑ 4.0 4.1 Lua error in package.lua at line 80: module 'strict' not found.
- ↑ 5.0 5.1 5.2 Lua error in package.lua at line 80: module 'strict' not found.
- ↑ 6.0 6.1 Lua error in package.lua at line 80: module 'strict' not found.
- ↑ 7.0 7.1 Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ 10.0 10.1 Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
