# Bit Manipulation Instruction Set

**URL:** <https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368>\
**Category:** General Usage\
**Tags:** question\
**Created:** [August 14, 2017, 2:49am UTC](https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368 "2017-08-14T02:49:18Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [August 14, 2017, 2:49am UTC](https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368/1 "2017-08-14T02:49:18Z")

</div>

I saw on stackoverflow, there are “Parallel bit deposit and extract” instructions, which are part of BMI2 (Bit Manipulation Instruction Set 2).

Are these instructions (`PDEP` and `PEXT`) available to Julia / LLVM?

[algorithm - Find nth SET bit in an int - Stack Overflow](https://stackoverflow.com/questions/7669057/find-nth-set-bit-in-an-int))

[x86 Bit manipulation instruction set - Wikipedia](https://en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets#Parallel_bit_deposit_and_extract)

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [October 20, 2017, 1:34am UTC](https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368/2 "2017-10-20T01:34:25Z")

</div>

There is an old issue [Support AVX2 and BMI2 instructions](https://github.com/JuliaLang/julia/issues/4418), which is now closed. Does that mean that BMI2 instructions are now supported?

@StefanKarpinski, I saw this old post from google groups, [LLVM: trying to use x86 pext intrinsic](https://groups.google.com/forum/#!topic/julia-dev/GPd5sBnmrEg)  
Did you manage to get it working?

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [October 20, 2017, 2:16am UTC](https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368/3 "2017-10-20T02:16:40Z")

</div>

LLVM has had support for it for a long time and now that [https://github.com/JuliaLang/julia/pull/21849](https://github.com/JuliaLang/julia/pull/21849) is merged the nightly that includes it should be able to use those for JIT. It’s then a matter of what code pattern LLVM recognizes.

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [October 20, 2017, 10:47am UTC](https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368/4 "2017-10-20T10:47:03Z")

</div>

OK thanks for that.

I think I found how to call `PDEP` and `PEXT` explicitly:

```julia
pdep(x::UInt32, y::UInt32) = ccall("llvm.x86.bmi.pdep.32", llvmcall, UInt32, (UInt32, UInt32), x, y)
pdep(x::UInt64, y::UInt64) = ccall("llvm.x86.bmi.pdep.64", llvmcall, UInt64, (UInt64, UInt64), x, y)

pext(x::UInt32, y::UInt32) = ccall("llvm.x86.bmi.pext.32", llvmcall, UInt32, (UInt32, UInt32), x, y)
pext(x::UInt64, y::UInt64) = ccall("llvm.x86.bmi.pext.64", llvmcall, UInt64, (UInt64, UInt64), x, y)

```

**Firstly, is this the right way?**

I modelled this on `pow_fast` found in `fastmath.jl`:

```julia
pow_fast(x::Float32, y::Integer) = ccall("llvm.powi.f32", llvmcall, Float32, (Float32, Int32), x, y)
pow_fast(x::Float64, y::Integer) = ccall("llvm.powi.f64", llvmcall, Float64, (Float64, Int32), x, y)

```

**Secondly, how can determine if a Julia build / hardware supports this instruction?**  
Presumably attempting to execute these instructions on a non-supporting system will crash.  
So I’d like to define some functions using these instructions only if supported, and use an alternative implementation otherwise.

```julia
if `PDEP` instruction supported
   pdep(x::UInt32, y::UInt32) = ccall("llvm.x86.bmi.pdep.32", llvmcall, UInt32, (UInt32, UInt32), x, y)
   pdep(x::UInt64, y::UInt64) = ccall("llvm.x86.bmi.pdep.64", llvmcall, UInt64, (UInt64, UInt64), x, y)
   f(x,y) = pdep(x,y) ...
else
   f(x,y) = # some other implementation
end

```

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [October 20, 2017, 12:05pm UTC](https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368/5 "2017-10-20T12:05:05Z")

</div>

> [@greg\_plowman](#):
>
> Firstly, is this the right way?

A rought search through LLVM code (searching for pdep or PDEP) suggests that LLVM doesn’t have any code that do it automatically so this is likely the right/only way right now.

> [@greg\_plowman](#):
>
> Secondly, how can determine if a Julia build / hardware supports this instruction?

That’ll be the next step for my PR.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [October 20, 2017, 11:04pm UTC](https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368/6 "2017-10-20T23:04:55Z")

</div>

> [@greg\_plowman](#):
>
> @StefanKarpinski, I saw this old post from google groups, LLVM: trying to use x86 pext intrinsic
> 
> Did you manage to get it working?

I did, but only on a machine that supported that instruction set, of course.

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [October 23, 2017, 3:56am UTC](https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368/7 "2017-10-23T03:56:33Z")

</div>

Thanks Yichao.  
In the meantime I can use an environment variable (say `"JULIA_USEBMI2"`) to opt-in to using these instructions.

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [January 12, 2019, 6:32am UTC](https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368/8 "2019-01-12T06:32:11Z")

</div>

> [@yuyichao](#):
>
> > Secondly, how can determine if a Julia build / hardware supports this instruction?
> 
> That’ll be the next step for my PR.

Any update on this?

Is there a way to programmatically determine if an intrinsic instruction (e.g. `PDEP` and `PEXT`) is supported?

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [January 12, 2019, 8:46am UTC](https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368/9 "2019-01-12T08:46:17Z")

</div>

I’ve used this:

```julia
function has_bmi2()
    CPUInfo = zeros(Int32, 4)
    ccall(:jl_cpuidex, Cvoid, (Ptr{Cint}, Cint, Cint), CPUInfo, 7, 0)
    CPUInfo[2] & 0x100 != 0
end

```

Cf. [this post](https://discourse.julialang.org/t/interleaving-bits-z-order-curve-morton-code-transpose-binary-matrix/18458/6). There’s also [CpuId.jl](https://github.com/m-j-w/CpuId.jl).

---

<div class="post-metadata">

**Author:** ![greg\_plowman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/greg_plowman/32/8100_2.png) [@greg\_plowman](https://discourse.julialang.org/u/greg_plowman)\
**Post date:** [January 12, 2019, 12:05pm UTC](https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368/10 "2019-01-12T12:05:21Z")

</div>

Thanks!  
This is exactly what I was looking for.

---

<div class="post-metadata">

**Author:** ![mbauman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mbauman/32/31082_2.png) [@mbauman](https://discourse.julialang.org/u/mbauman)\
**Post date:** [November 6, 2020, 2:37pm UTC](https://discourse.julialang.org/t/bit-manipulation-instruction-set/5368/11 "2020-11-06T14:37:54Z")

</div>

2 posts were split to a new topic: [What’s the fastest CPU execution model?](https://discourse.julialang.org/t/whats-the-fastest-cpu-execution-model/49682)