View source for Bit Manipulation Instruction Sets

'''Bit Manipulation Instructions Sets''' ('''BMI sets''') are extensions to the [[X86|x86]] [[Instruction set architecture|instruction set architecture]] for [[Engineering:Microprocessor|microprocessor]]s from Intel and [[Company:Advanced Micro Devices|AMD]].  The purpose of these instruction sets is to improve the speed of [[Bit manipulation|bit manipulation]]. All the instructions in these sets are non-[[SIMD]] and operate only on general-purpose [[Processor register|registers]].
There are two sets published by Intel: BMI (here referred to as BMI1) and BMI2; they were both introduced with the [[Haswell (microarchitecture)|Haswell]] microarchitecture.  Another two sets were published by AMD: ABM (''Advanced Bit Manipulation'', which is also a subset of [[SSE4#SSE4a|SSE4a]] implemented by Intel as part of [[SSE4#SSE4.2|SSE4.2]] and BMI1), and TBM (''Trailing Bit Manipulation'', an extension introduced with [[Engineering:Piledriver (microarchitecture)|Piledriver]]-based processors as an extension to BMI1, but dropped again in [[Engineering:Zen (microarchitecture)|Zen]]-based processors).<ref name=piledriverinstructions>{{cite web|url=http://developer.amd.com/wordpress/media/2012/10/New-Bulldozer-and-Piledriver-Instructions.pdf|title=New "Bulldozer" and "Piledriver" Instructions|accessdate=2014-01-03}}</ref>

=={{anchor|ABM}}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 <code>POPCNT</code> as part of SSE4.2, and <code>LZCNT</code> as part of BMI1. <code>POPCNT</code> has a separate [[CPUID]] flag; however, Intel uses AMD's <code>ABM</code> flag to indicate <code>LZCNT</code> support (since <code>LZCNT</code> completes the ABM).<ref name="intelavx">{{cite web |url=http://software.intel.com/file/36945 |title=Intel Advanced Vector Extensions Programming Reference |date=June 2011 |accessdate=2014-01-03 |publisher=[[Company:Intel|Intel]] |work=intel.com |format=PDF}}</ref>

{| class="wikitable"
|-
! Instruction
! Description<ref name=amd64apiv3>{{cite web|url=http://support.amd.com/TechDocs/24594.pdf|title=AMD64 Architecture Programmer's Manual, Volume 3: General-Purpose and System Instructions|date=October 2013 |accessdate=2014-01-02 |publisher=[[Engineering:AMD|AMD]] |work=amd.com|format=PDF}}</ref>
|-
| <code>POPCNT</code>
| [[Hamming weight|Population count]]
|-
| <code>LZCNT</code>
| [[Find first set|Leading zeros count]]
|}

<code>LZCNT</code> is related to the Bit Scan Reverse (<code>BSR</code>) 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. For a non-zero argument, sum of <code>LZCNT</code> and <code>BSR</code> results is argument bit width minus 1 (for example, if 32-bit argument is  <code>0x000f0000</code>, LZCNT gives 12, and BSR gives 19).

=={{anchor|BMI1}}BMI1 (Bit Manipulation Instruction Set 1)==
The instructions below are those enabled by the <code>BMI</code> bit in CPUID. Intel officially considers <code>LZCNT</code> as part of BMI, but advertises <code>LZCNT</code> support using the <code>ABM</code> CPUID feature flag.<ref name=intelavx /> BMI1 is available in AMD's [[Engineering:Jaguar (microarchitecture)|Jaguar]],<ref name=fam16hsheet /> Piledriver<ref name=piledriver-ins>{{cite web|last1=Hollingsworth|first1=Brent|title=New "Bulldozer" and "Piledriver" instructions|url=http://amd-dev.wpengine.netdna-cdn.com/wordpress/media/2012/10/New-Bulldozer-and-Piledriver-Instructions.pdf|publisher=Advanced Micro Devices, Inc.|accessdate=11 December 2014|format=pdf}}</ref> and newer processors, and in Intel's [[Haswell (microarchitecture)|Haswell]]<ref name=Haswell-ins>{{cite web|last1=Locktyukhin|first1=Max|title=How to detect New Instruction support in the 4th generation Intel® Core™ processor family|url=https://software.intel.com/en-us/articles/how-to-detect-new-instruction-support-in-the-4th-generation-intel-core-processor-family|website=www.intel.com|publisher=[[Company:Intel|Intel]]|accessdate=11 December 2014}}</ref> and newer processors.

{| class="wikitable"
|-
! Instruction
! Description<ref name=intelavx />
! Equivalent C expression<ref>{{cite web|url=https://gcc.gnu.org/viewcvs/gcc/branches/gcc-4_8-branch/gcc/config/i386/bmiintrin.h?revision=201047&view=markup|title=bmiintrin.h from GCC 4.8|accessdate=2014-03-17}}</ref>
|-
| <code>ANDN</code>
| Logical and not
| <tt>~x & y</tt>
|-
| <code>BEXTR</code>
| Bit field extract (with register)
| <tt>(src >> start) & ((1 << len) - 1)</tt>
|-
| <code>BLSI</code>
| Extract lowest set isolated bit
| <tt>x & -x</tt>
|-
| <code>BLSMSK</code>
| Get mask up to lowest set bit
| <tt>x ^ (x - 1)</tt>
|-
| <code>BLSR</code>
| Reset lowest set bit
| <tt>x & (x - 1)</tt>
|-
| <code>TZCNT</code>
| Count the number of trailing zero bits 
| {{N/A}}
|-
|}

<code>TZCNT</code> is almost identical to the Bit Scan Forward (<code>BSF</code>) instruction, but sets the ZF (if the result is zero) and CF (if the source is zero) flags rather than OF. For a non-zero argument, result of <code>TZCNT</code> and <code>BSF</code> is equal.


=={{anchor|BMI2}}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 [[Engineering:Excavator (microarchitecture)|Excavator]] architecture and newer.<ref name=excavatorinstructions>{{cite web |url=http://www.xbitlabs.com/news/cpu/display/20131018224745_AMD_Excavator_Core_May_Dramatic_Performance_Increases.html |title=AMD Excavator Core May Bring Dramatic Performance Increases |publisher=X-bit labs |date=October 18, 2013 |accessdate=November 24, 2013 |url-status=dead |archiveurl=https://web.archive.org/web/20131023074809/http://www.xbitlabs.com/news/cpu/display/20131018224745_AMD_Excavator_Core_May_Dramatic_Performance_Increases.html |archivedate=October 23, 2013 }}</ref>

{| class="wikitable"
|-
! Instruction
! Description
|-
| <code>BZHI</code>
| Zero high bits starting with specified bit position  [src & (1 << inx)-1];
|-
| <code>MULX</code>
| Unsigned multiply without affecting flags, and arbitrary destination registers
|-
| <code>PDEP</code>
| Parallel bits deposit
|-
| <code>PEXT</code>
| Parallel bits extract
|-
| <code>RORX</code>
| Rotate right logical without affecting flags
|-
| <code>SARX</code>
| Shift arithmetic right without affecting flags
|-
| <code>SHRX</code>
| Shift logical right without affecting flags
|-
| <code>SHLX</code>
| Shift logical left without affecting flags
|}

=== Parallel bit deposit and extract ===
The <code>PDEP</code> and <code>PEXT</code> 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.  <code>PEXT</code> copies selected bits from the source to contiguous low-order bits of the destination; higher-order destination bits are cleared.  <code>PDEP</code> 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 (vector addressing)|gather-scatter]] SIMD instructions, <code>PDEP</code> and <code>PEXT</code> instructions (like the rest of the BMI instruction sets) operate on general-purpose registers.<ref>{{Cite web
 | url = http://palms.princeton.edu/system/files/IEEE_TC09_NewBasisForShifters.pdf
 | title = A New Basis for Shifters in General-Purpose Processors for Existing and Advanced Bit Manipulations
 | date = August 2009 | accessdate = 2014-02-10
 | author1 = Yedidya Hilewitz | author2 = Ruby B. Lee
 | publisher = IEEE Transactions on Computers | work = palms.princeton.edu
 | volume = 58 | number = 8 | pages = 1035&ndash;1048
 | format = PDF
}}</ref>

The instructions are available in 32-bit and 64-bit versions.  An example using arbitrary source and selector in 32-bit mode is:
{| class="wikitable"
|-
! Instruction || Selector mask || Source || Destination
|-
| <code>PEXT</code> || <tt>0xff00fff0</tt> || <tt>0x12345678</tt> || <tt>0x00012567</tt>
|-
| <code>PDEP</code> || <tt>0xff00fff0</tt> || <tt>0x00012567</tt> || <tt>0x12005670</tt>
|-
|}

=={{anchor|TBM}}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<ref name=piledriver-ins /> line of processors; later AMD Jaguar and Zen-based processors do not support TBM.<ref name=fam16hsheet>{{cite web |url=http://support.amd.com/TechDocs/52169_KB_A_Series_Mobile.pdf |title=Family 16h AMD A-Series Data Sheet |date=October 2013 |accessdate=2014-01-02 |publisher=[[Engineering:AMD|AMD]] |work=amd.com |format=PDF}}</ref>  No Intel processors (at least through Coffee Lake) support TBM.

{| class="wikitable"
|-
! Instruction
! Description<ref name="amd64apiv3" />
! Equivalent C expression<ref>{{cite web|url=https://gcc.gnu.org/viewcvs/gcc/branches/gcc-4_8-branch/gcc/config/i386/tbmintrin.h?revision=196696&view=markup|title=tbmintrin.h from GCC 4.8|accessdate=2014-03-17}}</ref>
|-
| <code>BEXTR</code>
| Bit field extract (with immediate)
|  <tt>(src >> start) & ((1 << len) - 1)</tt>
|-
| <code>BLCFILL</code>
| Fill from lowest clear bit
| <tt>x & (x + 1)</tt>
|-
| <code>BLCI</code>
| Isolate lowest clear bit
| <tt>x &#124; ~(x + 1)</tt>
|-
| <code>BLCIC</code>
| Isolate lowest clear bit and complement
| <tt>~x & (x + 1)</tt>
|-
| <code>BLCMSK</code>
| Mask from lowest clear bit
| <tt>x ^ (x + 1)</tt>
|-
| <code>BLCS</code>
| Set lowest clear bit
| <tt>x &#124; (x + 1)</tt>
|-
| <code>BLSFILL</code>
| Fill from lowest set bit
| <tt>x &#124; (x - 1)</tt>
|-
| <code>BLSIC</code>
| Isolate lowest set bit and complement
| <tt>~x &#124; (x - 1)</tt>
|-
| <code>T1MSKC</code>
| Inverse mask from trailing ones
| <tt>~x &#124; (x + 1)</tt>
|-
| <code>TZMSK</code>
| Mask from trailing zeros
| <tt>~x & (x - 1)</tt>
|}

==Supporting CPUs==
* Intel
** Intel [[Engineering:Nehalem (microarchitecture)|Nehalem]] processors and newer (like [[Engineering:Sandy Bridge|Sandy Bridge]], Ivy Bridge) (POPCNT supported)
** Intel [[Engineering:Silvermont|Silvermont]] processors (POPCNT supported)
** Intel [[Haswell (microarchitecture)|Haswell]] processors and newer (like [[Skylake (microarchitecture)|Skylake]], [[Broadwell (microarchitecture)|Broadwell]]) (ABM, BMI1 and BMI2 supported)<ref name=Haswell-ins />
* [[Company:Advanced Micro Devices|AMD]]
** [[Engineering:AMD 10h|K10-based]] processors (ABM supported)
** "Cat" low-power processors
*** Bobcat-based processors (ABM supported)<ref>{{cite web|url=http://developer.amd.com/wordpress/media/2012/10/43170_14h_Mod_00h-0Fh_BKDG.pdf|title=BIOS and Kernel Developer's Guide for AMD Family 14h|accessdate=2014-01-03}}</ref>
*** [[Engineering:Jaguar (microarchitecture)|Jaguar-based]] processors and newer (ABM and BMI1 supported)<ref name="fam16hsheet" />
*** [[Engineering:Puma (microarchitecture)|Puma-based]] processors and newer (ABM and BMI1 supported)<ref name="fam16hsheet" />
** "Heavy Equipment" processors 
*** [[Engineering:Bulldozer (microarchitecture)|Bulldozer-based]] processors (ABM supported)
*** [[Engineering:Piledriver (microarchitecture)|Piledriver-based]] processors (ABM, BMI1 and TBM supported)<ref name="piledriverinstructions" />
*** [[Engineering:Steamroller (microarchitecture)|Steamroller-based]] processors (ABM, BMI1 and TBM supported)
*** [[Engineering:Excavator (microarchitecture)|Excavator-based]] processors and newer (ABM, BMI1, BMI2 and TBM supported)<ref name="excavatorinstructions" />
** [[Engineering:Zen (microarchitecture)|Zen-based]] processors (ABM, BMI1 and BMI2 supported)
** Zen+-based processors (ABM, BMI1 and BMI2 supported)
** [[Engineering:Zen 2|Zen 2]] processors (ABM, BMI1 and BMI2 supported)

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 Zen, Zen+ and 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<ref>{{Cite web|url=https://dolphin-emu.org/blog/2020/02/07/dolphin-progress-report-dec-2019-and-jan-2020/|title=Dolphin Emulator|website=Dolphin Emulator|language=en-us|access-date=2020-02-07}}</ref>. 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 ==

{{Div col|colwidth=20em}}
* [[Advanced Vector Extensions]] (AVX)
* [[AES instruction set]]
* [[CLMUL instruction set]]
* [[F16C]]
* [[FMA instruction set]]
* [[Intel ADX]]
* [[XOP instruction set]]
* [[Intel BCD opcodes]] (also used for advanced bit manipulation techniques)
{{Div col end}}

==References==
{{Reflist|30em}}

==Further reading==
* {{Cite book |title=[[Hacker's Delight]] |first=Henry S. |last=Warren Jr. |date=2013 |edition=2 |publisher=Addison Wesley - Pearson Education, Inc. |isbn=978-0-321-84268-8}}

== External links ==
* [https://software.intel.com/sites/landingpage/IntrinsicsGuide/ Intel Intrinsics Guide]

{{AMD technology}}
{{Intel technology}}
{{Multimedia extensions}}

[[Category:X86 instructions]]

{{Sourceattribution|Bit Manipulation Instruction Sets|1}}