ACP: add funnel shifts #642
Description
Problem statement
I want to use funnel shifts, I guess?
Motivating examples or use cases
Funnel shifts are a generalization of bit shifting and bit rotation: they collapse a wide variety of bit twiddling tricks into a simple primitive.
x.rotate_left(k) = x.funnel_shl(x, k)
x.rotate_right(k) = x.funnel_shr(x, k)
x << k = x.funnel_shl(0, k)
x >> k = 0.funnel_shr(x, k)
The shift value is taken modulo T::BITS: there is no possibility of UB (or the need to panic) for shift values equal to or larger than the number of bits in the integer type.
Another way to think about this operation is that it provides a register that is twice as wide for the shifting, so long as you only need half that size of bits at the end.
We already have core::intrinsics::simd::simd_funnel_{shr, shl}, because this primitive provides a flexible way to move bits between lanes.
Using funnel shifts directly can lead to better code generation, for instance in https://godbolt.org/z/dr1b4vMcK where using funnel_shl is lowered to shld. LLVM is not able to recognize this, I suspect because of the potential for overflow in the shifts.
Solution sketch
There is a PR with an implementation at rust-lang/rust#145690.
We'd add the following intrinsics, which for the LLVM backend map directly to llvm.fshl and llvm.fshr respectively. For other backends a fallback using shifts has to be implemented. We don't currently see a way to do that generically, so custom support in each backend is needed.
#[rustc_intrinsic]
#[rustc_nounwind]
#[rustc_const_unstable(feature = "funnel_shifts", issue = "145686")]
#[unstable(feature = "funnel_shifts", issue = "145686")]
pub const fn funnel_shl<T: Copy>(a: T, b: T, shift: u32) -> T;
#[rustc_intrinsic]
#[rustc_nounwind]
#[rustc_const_unstable(feature = "funnel_shifts", issue = "145686")]
#[unstable(feature = "funnel_shifts", issue = "145686")]
pub const fn funnel_shr<T: Copy>(a: T, b: T, shift: u32) -> T;Next we'd add the funnel_shl and funnel_shr methods on the unsigned integers:
impl uN {
pub const fn funnel_shl(self, rhs: Self, n: u32) -> Self {
return intrinsics::funnel_shl(self, rhs, n);
}
pub const fn funnel_shr(self, rhs: Self, n: u32) -> Self {
return intrinsics::funnel_shr(self, rhs, n);
}
}The funnel shifts treat the input as a bag of bits. We could add the methods on signed integers as well, the signedness of the input type has no effect.
Alternatives
Do nothing, or only add the intrinsics, not the methods.
Links and related work
What happens now?
This issue contains an API change proposal (or ACP) and is part of the libs-api team feature lifecycle. Once this issue is filed, the libs-api team will review open proposals as capability becomes available. Current response times do not have a clear estimate, but may be up to several months.
Possible responses
The libs team may respond in various different ways. First, the team will consider the problem (this doesn't require any concrete solution or alternatives to have been proposed):
- We think this problem seems worth solving, and the standard library might be the right place to solve it.
- We think that this probably doesn't belong in the standard library.
Second, if there's a concrete solution:
- We think this specific solution looks roughly right, approved, you or someone else should implement this. (Further review will still happen on the subsequent implementation PR.)
- We're not sure this is the right solution, and the alternatives or other materials don't give us enough information to be sure about that. Here are some questions we have that aren't answered, or rough ideas about alternatives we'd want to see discussed.