Implement rotate using funnel shift on LLVM >= 7

Implement the rotate_left and rotate_right operations using
llvm.fshl and llvm.fshr if they are available (LLVM >= 7).

Originally I wanted to expose the funnel_shift_left and
funnel_shift_right intrinsics and implement rotate_left and
rotate_right on top of them. However, emulation of funnel
shifts requires emitting a conditional to check for zero shift
amount, which is not necessary for rotates. I was uncomfortable
doing that here, as I don't want to rely on LLVM to optimize
away that conditional (and for variable rotates, I'm not sure it
can). We should revisit that question when we raise our minimum
version requirement to LLVM 7 and don't need emulation code
anymore.

2 files changed, 26 insertions, 2 deletions

diff --git a/src/libcore/intrinsics.rs b/src/libcore/intrinsics.rs
index cceae9249e4..7ed6e4a8f51 100644
--- a/src/libcore/intrinsics.rs
+++ b/src/libcore/intrinsics.rs
@@ -1465,6 +1465,20 @@ extern "rust-intrinsic" {
     /// y < 0 or y >= N, where N is the width of T in bits.
     pub fn unchecked_shr<T>(x: T, y: T) -> T;
 
+    /// Performs rotate left.
+    /// The stabilized versions of this intrinsic are available on the integer
+    /// primitives via the `rotate_left` method. For example,
+    /// [`std::u32::rotate_left`](../../std/primitive.u32.html#method.rotate_left)
+    #[cfg(not(stage0))]
+    pub fn rotate_left<T>(x: T, y: T) -> T;
+
+    /// Performs rotate right.
+    /// The stabilized versions of this intrinsic are available on the integer
+    /// primitives via the `rotate_right` method. For example,
+    /// [`std::u32::rotate_right`](../../std/primitive.u32.html#method.rotate_right)
+    #[cfg(not(stage0))]
+    pub fn rotate_right<T>(x: T, y: T) -> T;
+
     /// Returns (a + b) mod 2<sup>N</sup>, where N is the width of T in bits.
     /// The stabilized versions of this intrinsic are available on the integer
     /// primitives via the `wrapping_add` method. For example,
diff --git a/src/libcore/num/mod.rs b/src/libcore/num/mod.rs
index c6cbeea5a0e..090147c9fe4 100644
--- a/src/libcore/num/mod.rs
+++ b/src/libcore/num/mod.rs
@@ -2301,7 +2301,12 @@ assert_eq!(n.rotate_left(", $rot, "), m);
             #[rustc_const_unstable(feature = "const_int_rotate")]
             #[inline]
             pub const fn rotate_left(self, n: u32) -> Self {
-                (self << (n % $BITS)) | (self >> (($BITS - (n % $BITS)) % $BITS))
+                #[cfg(not(stage0))] {
+                    unsafe { intrinsics::rotate_left(self, n as $SelfT) }
+                }
+                #[cfg(stage0)] {
+                    (self << (n % $BITS)) | (self >> (($BITS - (n % $BITS)) % $BITS))
+                }
             }
         }
 
@@ -2326,7 +2331,12 @@ assert_eq!(n.rotate_right(", $rot, "), m);
             #[rustc_const_unstable(feature = "const_int_rotate")]
             #[inline]
             pub const fn rotate_right(self, n: u32) -> Self {
-                (self >> (n % $BITS)) | (self << (($BITS - (n % $BITS)) % $BITS))
+                #[cfg(not(stage0))] {
+                    unsafe { intrinsics::rotate_right(self, n as $SelfT) }
+                }
+                #[cfg(stage0)] {
+                    (self >> (n % $BITS)) | (self << (($BITS - (n % $BITS)) % $BITS))
+                }
             }
         }