Expose LLVM's or disjoint instruction on ints

[alion02]

Proposal

Problem statement

When writing heavy bit-manipulating code you sometimes need to combine integers bitwise according to the following truth table:

a	b	combine(a, b)
0	0	0
0	1	1
1	0	1
1	1	never happens

The above truth table can be implemented using any of the following:

• bitor
• bitxor
• add and friends

Which one you choose can have an impact on the performance of downstream code. Occasionally, you might want to exercise properties of more than one of these operations at the same time.

Motivating examples or use cases

Consider the construction of a mask like so: let c = combine(a, b << 2);. This comes up fairly often when dealing with packed data, for instance. Using + for combine can result in a single instruction on x86: lea c, [a + b * 4]. On the other hand, using | allows LLVM to apply bitwise optimizations, such as remembering more known bits or tracking tighter bounds on the range of c.

In projects which commonly utilize this operation, it would be beneficial to have a canonical way to write it. Due to the above concerns, however, this isn't always feasible, and a user attempting to maximize performance must take into account the tradeoffs every time.

Solution sketch

Expose LLVM's or disjoint instruction, which is the canonical way to write the above truth table. This takes the optimization burden off the programmer and shoves it onto LLVM, which is much better equipped to handle it.

1. Add the function core::intrinsics::disjoint_or, following the example of core::intrinsics::unchecked_add and friends.
2. Expose a function on all signed and unsigned (and NonZero?) integers, like so:

/// Unchecked bitwise merging of disjoint sets of set bits. This operation is equivalent to
/// `self | rhs`, `self ^ rhs`, and `self + rhs`, and assumes that all of those operations
/// produce the same result; that is, that there are no pairs of merged bits where both
/// bits are set.
/// 
/// This function frequently allows the optimizer to better reason about the operation than
/// any of the other operations which can be used to emulate it do.
/// 
/// The safe alternatives are the aforementioned operators.
/// 
/// # Safety
/// 
/// This results in undefined behavior if any pair of merged bits has both bits set.
#[must_use]
#[inline(always)]
pub const unsafe fn unchecked_bitmerge(self, rhs: Self) -> Self {
    // SAFETY: the caller must uphold the safety contract for `unchecked_bitmerge`.
    unsafe { intrinsics::disjoint_or(self, rhs) }
}

Alternatives

• Do nothing. The lack of a canonical operation continues. Some of the performance benefits can be gained manually using already available tools through repetitive and tedious labor. Performance characteristics are different between architectures and possibly even microarchitectures, which makes this an exceedingly poor cost-benefit effort.
• Improve LLVM to the point that this function can be perfectly expressed in user code with the help of unreachable_unchecked. LLVM does not recognize this right now. I assumed this is a very complicated problem - if it's not, then perhaps this is a better choice. I'm surprised this wasn't brought up in the unchecked math stabilization PR.

Links and related work

Internals thread. Blog post about the introduction of the feature to LLVM.

[joshtriplett]

Discussed in today's libs-api meeting. Approved, but please use disjoint_bitor for the intrinsic and unchecked_disjoint_bitor for the non-intrinsic function.

[joboet]

unchecked_disjoint_bitor conflicts with the API guidelines. Could I suggest naming it disjoint_bitor_unchecked instead?

[programmerjake]

tbh that naming seems kinda backwards to me, I prefer bitor_disjoint_unckecked

[RustyYato]

But unchecked first makes it consistent with the recently stabilized unchecked_{add,sub,mul} methods on integers. Which seems more valuable

[Amanieu]

Closing since this ACP has been approved, discussion should move to the PR/tracking issue.

[scottmcm]

Saving an example of a place where I hit something that could be or disjoint : rust-lang/rust#85532 (comment)