Auto merge of #3280 - rust-lang:rustup-2024-01-26, r=RalfJung

Automatic Rustup

12 files changed, 625 insertions, 162 deletions

diff --git a/library/core/src/intrinsics.rs b/library/core/src/intrinsics.rs
index 5d917dc6fbb..76a53a9366a 100644
--- a/library/core/src/intrinsics.rs
+++ b/library/core/src/intrinsics.rs
@@ -2517,6 +2517,66 @@ extern "rust-intrinsic" {
     where
         G: FnOnce<ARG, Output = RET>,
         F: FnOnce<ARG, Output = RET>;
+
+    /// Returns whether the argument's value is statically known at
+    /// compile-time.
+    ///
+    /// This is useful when there is a way of writing the code that will
+    /// be *faster* when some variables have known values, but *slower*
+    /// in the general case: an `if is_val_statically_known(var)` can be used
+    /// to select between these two variants. The `if` will be optimized away
+    /// and only the desired branch remains.
+    ///
+    /// Formally speaking, this function non-deterministically returns `true`
+    /// or `false`, and the caller has to ensure sound behavior for both cases.
+    /// In other words, the following code has *Undefined Behavior*:
+    ///
+    /// ```
+    /// #![feature(is_val_statically_known)]
+    /// #![feature(core_intrinsics)]
+    /// # #![allow(internal_features)]
+    /// use std::hint::unreachable_unchecked;
+    /// use std::intrinsics::is_val_statically_known;
+    ///
+    /// unsafe {
+    ///    if !is_val_statically_known(0) { unreachable_unchecked(); }
+    /// }
+    /// ```
+    ///
+    /// This also means that the following code's behavior is unspecified; it
+    /// may panic, or it may not:
+    ///
+    /// ```no_run
+    /// #![feature(is_val_statically_known)]
+    /// #![feature(core_intrinsics)]
+    /// # #![allow(internal_features)]
+    /// use std::intrinsics::is_val_statically_known;
+    ///
+    /// unsafe {
+    ///     assert_eq!(is_val_statically_known(0), is_val_statically_known(0));
+    /// }
+    /// ```
+    ///
+    /// Unsafe code may not rely on `is_val_statically_known` returning any
+    /// particular value, ever. However, the compiler will generally make it
+    /// return `true` only if the value of the argument is actually known.
+    ///
+    /// When calling this in a `const fn`, both paths must be semantically
+    /// equivalent, that is, the result of the `true` branch and the `false`
+    /// branch must return the same value and have the same side-effects *no
+    /// matter what*.
+    #[rustc_const_unstable(feature = "is_val_statically_known", issue = "none")]
+    #[rustc_nounwind]
+    #[cfg(not(bootstrap))]
+    pub fn is_val_statically_known<T: Copy>(arg: T) -> bool;
+}
+
+// FIXME: Seems using `unstable` here completely ignores `rustc_allow_const_fn_unstable`
+// and thus compiling stage0 core doesn't work.
+#[rustc_const_stable(feature = "is_val_statically_known", since = "0.0.0")]
+#[cfg(bootstrap)]
+pub const unsafe fn is_val_statically_known<T: Copy>(_arg: T) -> bool {
+    false
 }
 
 // Some functions are defined here because they accidentally got made
diff --git a/library/core/src/lib.rs b/library/core/src/lib.rs
index ead8cbe0e2f..2af242d4b50 100644
--- a/library/core/src/lib.rs
+++ b/library/core/src/lib.rs
@@ -200,6 +200,7 @@
 //
 // Language features:
 // tidy-alphabetical-start
+#![cfg_attr(not(bootstrap), feature(is_val_statically_known))]
 #![feature(abi_unadjusted)]
 #![feature(adt_const_params)]
 #![feature(allow_internal_unsafe)]
diff --git a/library/core/src/marker.rs b/library/core/src/marker.rs
index 561f8ef36ff..d6e0e1895cd 100644
--- a/library/core/src/marker.rs
+++ b/library/core/src/marker.rs
@@ -187,7 +187,7 @@ pub trait Unsize<T: ?Sized> {
 /// Required trait for constants used in pattern matches.
 ///
 /// Any type that derives `PartialEq` automatically implements this trait,
-/// *regardless* of whether its type-parameters implement `Eq`.
+/// *regardless* of whether its type-parameters implement `PartialEq`.
 ///
 /// If a `const` item contains some type that does not implement this trait,
 /// then that type either (1.) does not implement `PartialEq` (which means the
@@ -200,7 +200,7 @@ pub trait Unsize<T: ?Sized> {
 /// a pattern match.
 ///
 /// See also the [structural match RFC][RFC1445], and [issue 63438] which
-/// motivated migrating from attribute-based design to this trait.
+/// motivated migrating from an attribute-based design to this trait.
 ///
 /// [RFC1445]: https://github.com/rust-lang/rfcs/blob/master/text/1445-restrict-constants-in-patterns.md
 /// [issue 63438]: https://github.com/rust-lang/rust/issues/63438
@@ -218,7 +218,7 @@ marker_impls! {
         isize, i8, i16, i32, i64, i128,
         bool,
         char,
-        str /* Technically requires `[u8]: StructuralEq` */,
+        str /* Technically requires `[u8]: StructuralPartialEq` */,
         (),
         {T, const N: usize} [T; N],
         {T} [T],
@@ -275,6 +275,7 @@ marker_impls! {
 #[unstable(feature = "structural_match", issue = "31434")]
 #[diagnostic::on_unimplemented(message = "the type `{Self}` does not `#[derive(Eq)]`")]
 #[lang = "structural_teq"]
+#[cfg(bootstrap)]
 pub trait StructuralEq {
     // Empty.
 }
@@ -282,6 +283,7 @@ pub trait StructuralEq {
 // FIXME: Remove special cases of these types from the compiler pattern checking code and always check `T: StructuralEq` instead
 marker_impls! {
     #[unstable(feature = "structural_match", issue = "31434")]
+    #[cfg(bootstrap)]
     StructuralEq for
         usize, u8, u16, u32, u64, u128,
         isize, i8, i16, i32, i64, i128,
@@ -859,6 +861,7 @@ impl<T: ?Sized> Default for PhantomData<T> {
 impl<T: ?Sized> StructuralPartialEq for PhantomData<T> {}
 
 #[unstable(feature = "structural_match", issue = "31434")]
+#[cfg(bootstrap)]
 impl<T: ?Sized> StructuralEq for PhantomData<T> {}
 
 /// Compiler-internal trait used to indicate the type of enum discriminants.
@@ -1038,6 +1041,20 @@ pub trait PointerLike {}
 #[unstable(feature = "adt_const_params", issue = "95174")]
 #[diagnostic::on_unimplemented(message = "`{Self}` can't be used as a const parameter type")]
 #[allow(multiple_supertrait_upcastable)]
+#[cfg(not(bootstrap))]
+pub trait ConstParamTy: StructuralPartialEq + Eq {}
+
+/// A marker for types which can be used as types of `const` generic parameters.
+///
+/// These types must have a proper equivalence relation (`Eq`) and it must be automatically
+/// derived (`StructuralPartialEq`). There's a hard-coded check in the compiler ensuring
+/// that all fields are also `ConstParamTy`, which implies that recursively, all fields
+/// are `StructuralPartialEq`.
+#[lang = "const_param_ty"]
+#[unstable(feature = "adt_const_params", issue = "95174")]
+#[rustc_on_unimplemented(message = "`{Self}` can't be used as a const parameter type")]
+#[allow(multiple_supertrait_upcastable)]
+#[cfg(bootstrap)]
 pub trait ConstParamTy: StructuralEq + StructuralPartialEq + Eq {}
 
 /// Derive macro generating an impl of the trait `ConstParamTy`.
diff --git a/library/core/src/num/int_macros.rs b/library/core/src/num/int_macros.rs
index d052dcc3e6e..bb35b6128ea 100644
--- a/library/core/src/num/int_macros.rs
+++ b/library/core/src/num/int_macros.rs
@@ -1374,26 +1374,59 @@ macro_rules! int_impl {
         #[rustc_const_stable(feature = "const_int_pow", since = "1.50.0")]
         #[must_use = "this returns the result of the operation, \
                       without modifying the original"]
+        #[rustc_allow_const_fn_unstable(is_val_statically_known, const_int_unchecked_arith)]
         #[inline]
         pub const fn checked_pow(self, mut exp: u32) -> Option<Self> {
-            if exp == 0 {
-                return Some(1);
-            }
-            let mut base = self;
-            let mut acc: Self = 1;
-
-            while exp > 1 {
-                if (exp & 1) == 1 {
-                    acc = try_opt!(acc.checked_mul(base));
+            // SAFETY: This path has the same behavior as the other.
+            if unsafe { intrinsics::is_val_statically_known(self) }
+                && self.unsigned_abs().is_power_of_two()
+            {
+                if self == 1 { // Avoid divide by zero
+                    return Some(1);
                 }
-                exp /= 2;
-                base = try_opt!(base.checked_mul(base));
+                if self == -1 { // Avoid divide by zero
+                    return Some(if exp & 1 != 0 { -1 } else { 1 });
+                }
+                // SAFETY: We just checked this is a power of two. and above zero.
+                let power_used = unsafe { intrinsics::cttz_nonzero(self.wrapping_abs()) as u32 };
+                if exp > Self::BITS / power_used { return None; } // Division of constants is free
+
+                // SAFETY: exp <= Self::BITS / power_used
+                let res = unsafe { intrinsics::unchecked_shl(
+                    1 as Self,
+                    intrinsics::unchecked_mul(power_used, exp) as Self
+                )};
+                // LLVM doesn't always optimize out the checks
+                // at the ir level.
+
+                let sign = self.is_negative() && exp & 1 != 0;
+                if !sign && res == Self::MIN  {
+                    None
+                } else if sign {
+                    Some(res.wrapping_neg())
+                } else {
+                    Some(res)
+                }
+            } else {
+                if exp == 0 {
+                    return Some(1);
+                }
+                let mut base = self;
+                let mut acc: Self = 1;
+
+                while exp > 1 {
+                    if (exp & 1) == 1 {
+                        acc = try_opt!(acc.checked_mul(base));
+                    }
+                    exp /= 2;
+                    base = try_opt!(base.checked_mul(base));
+                }
+                // since exp!=0, finally the exp must be 1.
+                // Deal with the final bit of the exponent separately, since
+                // squaring the base afterwards is not necessary and may cause a
+                // needless overflow.
+                acc.checked_mul(base)
             }
-            // since exp!=0, finally the exp must be 1.
-            // Deal with the final bit of the exponent separately, since
-            // squaring the base afterwards is not necessary and may cause a
-            // needless overflow.
-            acc.checked_mul(base)
         }
 
         /// Strict exponentiation. Computes `self.pow(exp)`, panicking if
@@ -2058,27 +2091,58 @@ macro_rules! int_impl {
         #[rustc_const_stable(feature = "const_int_pow", since = "1.50.0")]
         #[must_use = "this returns the result of the operation, \
                       without modifying the original"]
+        #[rustc_allow_const_fn_unstable(is_val_statically_known, const_int_unchecked_arith)]
         #[inline]
         pub const fn wrapping_pow(self, mut exp: u32) -> Self {
-            if exp == 0 {
-                return 1;
-            }
-            let mut base = self;
-            let mut acc: Self = 1;
-
-            while exp > 1 {
-                if (exp & 1) == 1 {
-                    acc = acc.wrapping_mul(base);
+            // SAFETY: This path has the same behavior as the other.
+            if unsafe { intrinsics::is_val_statically_known(self) }
+                && self.unsigned_abs().is_power_of_two()
+            {
+                if self == 1 { // Avoid divide by zero
+                    return 1;
+                }
+                if self == -1 { // Avoid divide by zero
+                    return if exp & 1 != 0 { -1 } else { 1 };
+                }
+                // SAFETY: We just checked this is a power of two. and above zero.
+                let power_used = unsafe { intrinsics::cttz_nonzero(self.wrapping_abs()) as u32 };
+                if exp > Self::BITS / power_used { return 0; } // Division of constants is free
+
+                // SAFETY: exp <= Self::BITS / power_used
+                let res = unsafe { intrinsics::unchecked_shl(
+                    1 as Self,
+                    intrinsics::unchecked_mul(power_used, exp) as Self
+                )};
+                // LLVM doesn't always optimize out the checks
+                // at the ir level.
+
+                let sign = self.is_negative() && exp & 1 != 0;
+                if sign {
+                    res.wrapping_neg()
+                } else {
+                    res
+                }
+            } else {
+                if exp == 0 {
+                    return 1;
+                }
+                let mut base = self;
+                let mut acc: Self = 1;
+
+                while exp > 1 {
+                    if (exp & 1) == 1 {
+                        acc = acc.wrapping_mul(base);
+                    }
+                    exp /= 2;
+                    base = base.wrapping_mul(base);
                 }
-                exp /= 2;
-                base = base.wrapping_mul(base);
-            }
 
-            // since exp!=0, finally the exp must be 1.
-            // Deal with the final bit of the exponent separately, since
-            // squaring the base afterwards is not necessary and may cause a
-            // needless overflow.
-            acc.wrapping_mul(base)
+                // since exp!=0, finally the exp must be 1.
+                // Deal with the final bit of the exponent separately, since
+                // squaring the base afterwards is not necessary and may cause a
+                // needless overflow.
+                acc.wrapping_mul(base)
+            }
         }
 
         /// Calculates `self` + `rhs`
@@ -2561,36 +2625,68 @@ macro_rules! int_impl {
         #[rustc_const_stable(feature = "const_int_pow", since = "1.50.0")]
         #[must_use = "this returns the result of the operation, \
                       without modifying the original"]
+        #[rustc_allow_const_fn_unstable(is_val_statically_known, const_int_unchecked_arith)]
         #[inline]
         pub const fn overflowing_pow(self, mut exp: u32) -> (Self, bool) {
-            if exp == 0 {
-                return (1,false);
-            }
-            let mut base = self;
-            let mut acc: Self = 1;
-            let mut overflown = false;
-            // Scratch space for storing results of overflowing_mul.
-            let mut r;
-
-            while exp > 1 {
-                if (exp & 1) == 1 {
-                    r = acc.overflowing_mul(base);
-                    acc = r.0;
+            // SAFETY: This path has the same behavior as the other.
+            if unsafe { intrinsics::is_val_statically_known(self) }
+                && self.unsigned_abs().is_power_of_two()
+            {
+                if self == 1 { // Avoid divide by zero
+                    return (1, false);
+                }
+                if self == -1 { // Avoid divide by zero
+                    return (if exp & 1 != 0 { -1 } else { 1 }, false);
+                }
+                // SAFETY: We just checked this is a power of two. and above zero.
+                let power_used = unsafe { intrinsics::cttz_nonzero(self.wrapping_abs()) as u32 };
+                if exp > Self::BITS / power_used { return (0, true); } // Division of constants is free
+
+                // SAFETY: exp <= Self::BITS / power_used
+                let res = unsafe { intrinsics::unchecked_shl(
+                    1 as Self,
+                    intrinsics::unchecked_mul(power_used, exp) as Self
+                )};
+                // LLVM doesn't always optimize out the checks
+                // at the ir level.
+
+                let sign = self.is_negative() && exp & 1 != 0;
+                let overflow = res == Self::MIN;
+                if sign {
+                    (res.wrapping_neg(), overflow)
+                } else {
+                    (res, overflow)
+                }
+            } else {
+                if exp == 0 {
+                    return (1,false);
+                }
+                let mut base = self;
+                let mut acc: Self = 1;
+                let mut overflown = false;
+                // Scratch space for storing results of overflowing_mul.
+                let mut r;
+
+                while exp > 1 {
+                    if (exp & 1) == 1 {
+                        r = acc.overflowing_mul(base);
+                        acc = r.0;
+                        overflown |= r.1;
+                    }
+                    exp /= 2;
+                    r = base.overflowing_mul(base);
+                    base = r.0;
                     overflown |= r.1;
                 }
-                exp /= 2;
-                r = base.overflowing_mul(base);
-                base = r.0;
-                overflown |= r.1;
-            }
 
-            // since exp!=0, finally the exp must be 1.
-            // Deal with the final bit of the exponent separately, since
-            // squaring the base afterwards is not necessary and may cause a
-            // needless overflow.
-            r = acc.overflowing_mul(base);
-            r.1 |= overflown;
-            r
+                // since exp!=0, finally the exp must be 1.
+                // Deal with the final bit of the exponent separately, since
+                // squaring the base afterwards is not necessary and may cause a
+                // needless overflow.
+                r = acc.overflowing_mul(base);
+                r.1 |= overflown;
+                r
+            }
         }
 
         /// Raises self to the power of `exp`, using exponentiation by squaring.
@@ -2608,28 +2704,68 @@ macro_rules! int_impl {
         #[rustc_const_stable(feature = "const_int_pow", since = "1.50.0")]
         #[must_use = "this returns the result of the operation, \
                       without modifying the original"]
+        #[rustc_allow_const_fn_unstable(is_val_statically_known, const_int_unchecked_arith)]
         #[inline]
         #[rustc_inherit_overflow_checks]
+        #[track_caller] // Hides the hackish overflow check for powers of two.
         pub const fn pow(self, mut exp: u32) -> Self {
-            if exp == 0 {
-                return 1;
-            }
-            let mut base = self;
-            let mut acc = 1;
+            // SAFETY: This path has the same behavior as the other.
+            if unsafe { intrinsics::is_val_statically_known(self) }
+                && self.unsigned_abs().is_power_of_two()
+            {
+                if self == 1 { // Avoid divide by zero
+                    return 1;
+                }
+                if self == -1 { // Avoid divide by zero
+                    return if exp & 1 != 0 { -1 } else { 1 };
+                }
+                // SAFETY: We just checked this is a power of two. and above zero.
+                let power_used = unsafe { intrinsics::cttz_nonzero(self.wrapping_abs()) as u32 };
+                if exp > Self::BITS / power_used { // Division of constants is free
+                    #[allow(arithmetic_overflow)]
+                    return Self::MAX * Self::MAX * 0;
+                }
 
-            while exp > 1 {
-                if (exp & 1) == 1 {
-                    acc = acc * base;
+                // SAFETY: exp <= Self::BITS / power_used
+                let res = unsafe { intrinsics::unchecked_shl(
+                    1 as Self,
+                    intrinsics::unchecked_mul(power_used, exp) as Self
+                )};
+                // LLVM doesn't always optimize out the checks
+                // at the ir level.
+
+                let sign = self.is_negative() && exp & 1 != 0;
+                #[allow(arithmetic_overflow)]
+                if !sign && res == Self::MIN  {
+                    // So it panics.
+                    _ = Self::MAX * Self::MAX;
+                }
+                if sign {
+                    res.wrapping_neg()
+                } else {
+                    res
+                }
+            } else {
+                if exp == 0 {
+                    return 1;
+                }
+                let mut base = self;
+                let mut acc = 1;
+
+                while exp > 1 {
+                    if (exp & 1) == 1 {
+                        acc = acc * base;
+                    }
+                    exp /= 2;
+                    base = base * base;
                 }
-                exp /= 2;
-                base = base * base;
-            }
 
-            // since exp!=0, finally the exp must be 1.
-            // Deal with the final bit of the exponent separately, since
-            // squaring the base afterwards is not necessary and may cause a
-            // needless overflow.
-            acc * base
+                // since exp!=0, finally the exp must be 1.
+                // Deal with the final bit of the exponent separately, since
+                // squaring the base afterwards is not necessary and may cause a
+                // needless overflow.
+                acc * base
+            }
         }
 
         /// Returns the square root of the number, rounded down.
diff --git a/library/core/src/num/nonzero.rs b/library/core/src/num/nonzero.rs
index 640f1e3fa85..45ac544ceaa 100644
--- a/library/core/src/num/nonzero.rs
+++ b/library/core/src/num/nonzero.rs
@@ -288,6 +288,43 @@ macro_rules! nonzero_integer {
                 unsafe { intrinsics::cttz_nonzero(self.get() as $UnsignedPrimitive) as u32 }
             }
 
+            /// Returns the number of ones in the binary representation of `self`.
+            ///
+            /// # Examples
+            ///
+            /// Basic usage:
+            ///
+            /// ```
+            /// #![feature(non_zero_count_ones)]
+            /// # fn main() { test().unwrap(); }
+            /// # fn test() -> Option<()> {
+            #[doc = concat!("# use std::num::{self, ", stringify!($Ty), "};")]
+            ///
+            /// let one = num::NonZeroU32::new(1)?;
+            /// let three = num::NonZeroU32::new(3)?;
+            #[doc = concat!("let a = ", stringify!($Ty), "::new(0b100_0000)?;")]
+            #[doc = concat!("let b = ", stringify!($Ty), "::new(0b100_0011)?;")]
+            ///
+            /// assert_eq!(a.count_ones(), one);
+            /// assert_eq!(b.count_ones(), three);
+            /// # Some(())
+            /// # }
+            /// ```
+            ///
+            #[unstable(feature = "non_zero_count_ones", issue = "120287")]
+            #[rustc_const_unstable(feature = "non_zero_count_ones", issue = "120287")]
+            #[doc(alias = "popcount")]
+            #[doc(alias = "popcnt")]
+            #[must_use = "this returns the result of the operation, \
+                        without modifying the original"]
+            #[inline(always)]
+            pub const fn count_ones(self) -> NonZeroU32 {
+                // SAFETY:
+                // `self` is non-zero, which means it has at least one bit set, which means
+                // that the result of `count_ones` is non-zero.
+                unsafe { NonZeroU32::new_unchecked(self.get().count_ones()) }
+            }
+
             nonzero_integer_signedness_dependent_methods! {
                 Self = $Ty,
                 Primitive = $signedness $Int,
diff --git a/library/core/src/num/uint_macros.rs b/library/core/src/num/uint_macros.rs
index a217c2e259d..d450c68a5b2 100644
--- a/library/core/src/num/uint_macros.rs
+++ b/library/core/src/num/uint_macros.rs
@@ -1364,28 +1364,49 @@ macro_rules! uint_impl {
         #[rustc_const_stable(feature = "const_int_pow", since = "1.50.0")]
         #[must_use = "this returns the result of the operation, \
                       without modifying the original"]
+        #[rustc_allow_const_fn_unstable(is_val_statically_known, const_int_unchecked_arith)]
         #[inline]
         pub const fn checked_pow(self, mut exp: u32) -> Option<Self> {
-            if exp == 0 {
-                return Some(1);
-            }
-            let mut base = self;
-            let mut acc: Self = 1;
-
-            while exp > 1 {
-                if (exp & 1) == 1 {
-                    acc = try_opt!(acc.checked_mul(base));
+            // SAFETY: This path has the same behavior as the other.
+            if unsafe { intrinsics::is_val_statically_known(self) }
+                && self.is_power_of_two()
+            {
+                if self == 1 { // Avoid divide by zero
+                    return Some(1);
+                }
+                // SAFETY: We just checked this is a power of two. and above zero.
+                let power_used = unsafe { intrinsics::cttz_nonzero(self) as u32 };
+                if exp > Self::BITS / power_used { return None; } // Division of constants is free
+
+                // SAFETY: exp <= Self::BITS / power_used
+                unsafe { Some(intrinsics::unchecked_shl(
+                    1 as Self,
+                    intrinsics::unchecked_mul(power_used, exp) as Self
+                )) }
+                // LLVM doesn't always optimize out the checks
+                // at the ir level.
+            } else {
+                if exp == 0 {
+                    return Some(1);
+                }
+                let mut base = self;
+                let mut acc: Self = 1;
+
+                while exp > 1 {
+                    if (exp & 1) == 1 {
+                        acc = try_opt!(acc.checked_mul(base));
+                    }
+                    exp /= 2;
+                    base = try_opt!(base.checked_mul(base));
                 }
-                exp /= 2;
-                base = try_opt!(base.checked_mul(base));
-            }
 
-            // since exp!=0, finally the exp must be 1.
-            // Deal with the final bit of the exponent separately, since
-            // squaring the base afterwards is not necessary and may cause a
-            // needless overflow.
+                // since exp!=0, finally the exp must be 1.
+                // Deal with the final bit of the exponent separately, since
+                // squaring the base afterwards is not necessary and may cause a
+                // needless overflow.
 
-            acc.checked_mul(base)
+                acc.checked_mul(base)
+            }
         }
 
         /// Strict exponentiation. Computes `self.pow(exp)`, panicking if
@@ -1887,27 +1908,48 @@ macro_rules! uint_impl {
         #[rustc_const_stable(feature = "const_int_pow", since = "1.50.0")]
         #[must_use = "this returns the result of the operation, \
                       without modifying the original"]
+        #[rustc_allow_const_fn_unstable(is_val_statically_known, const_int_unchecked_arith)]
         #[inline]
         pub const fn wrapping_pow(self, mut exp: u32) -> Self {
-            if exp == 0 {
-                return 1;
-            }
-            let mut base = self;
-            let mut acc: Self = 1;
-
-            while exp > 1 {
-                if (exp & 1) == 1 {
-                    acc = acc.wrapping_mul(base);
+            // SAFETY: This path has the same behavior as the other.
+            if unsafe { intrinsics::is_val_statically_known(self) }
+                && self.is_power_of_two()
+            {
+                if self == 1 { // Avoid divide by zero
+                    return 1;
+                }
+                // SAFETY: We just checked this is a power of two. and above zero.
+                let power_used = unsafe { intrinsics::cttz_nonzero(self) as u32 };
+                if exp > Self::BITS / power_used {  return 0; } // Division of constants is free
+
+                // SAFETY: exp <= Self::BITS / power_used
+                unsafe { intrinsics::unchecked_shl(
+                    1 as Self,
+                    intrinsics::unchecked_mul(power_used, exp) as Self
+                )}
+                // LLVM doesn't always optimize out the checks
+                // at the ir level.
+            } else {
+                if exp == 0 {
+                    return 1;
+                }
+                let mut base = self;
+                let mut acc: Self = 1;
+
+                while exp > 1 {
+                    if (exp & 1) == 1 {
+                        acc = acc.wrapping_mul(base);
+                    }
+                    exp /= 2;
+                    base = base.wrapping_mul(base);
                 }
-                exp /= 2;
-                base = base.wrapping_mul(base);
-            }
 
-            // since exp!=0, finally the exp must be 1.
-            // Deal with the final bit of the exponent separately, since
-            // squaring the base afterwards is not necessary and may cause a
-            // needless overflow.
-            acc.wrapping_mul(base)
+                // since exp!=0, finally the exp must be 1.
+                // Deal with the final bit of the exponent separately, since
+                // squaring the base afterwards is not necessary and may cause a
+                // needless overflow.
+                acc.wrapping_mul(base)
+            }
         }
 
         /// Calculates `self` + `rhs`
@@ -2341,37 +2383,58 @@ macro_rules! uint_impl {
         #[rustc_const_stable(feature = "const_int_pow", since = "1.50.0")]
         #[must_use = "this returns the result of the operation, \
                       without modifying the original"]
+        #[rustc_allow_const_fn_unstable(is_val_statically_known, const_int_unchecked_arith)]
         #[inline]
         pub const fn overflowing_pow(self, mut exp: u32) -> (Self, bool) {
-            if exp == 0{
-                return (1,false);
-            }
-            let mut base = self;
-            let mut acc: Self = 1;
-            let mut overflown = false;
-            // Scratch space for storing results of overflowing_mul.
-            let mut r;
-
-            while exp > 1 {
-                if (exp & 1) == 1 {
-                    r = acc.overflowing_mul(base);
-                    acc = r.0;
+            // SAFETY: This path has the same behavior as the other.
+            if unsafe { intrinsics::is_val_statically_known(self) }
+                && self.is_power_of_two()
+            {
+                if self == 1 { // Avoid divide by zero
+                    return (1, false);
+                }
+                // SAFETY: We just checked this is a power of two. and above zero.
+                let power_used = unsafe { intrinsics::cttz_nonzero(self) as u32 };
+                if exp > Self::BITS / power_used {  return (0, true); } // Division of constants is free
+
+                // SAFETY: exp <= Self::BITS / power_used
+                unsafe { (intrinsics::unchecked_shl(
+                    1 as Self,
+                    intrinsics::unchecked_mul(power_used, exp) as Self
+                ), false) }
+                // LLVM doesn't always optimize out the checks
+                // at the ir level.
+            } else {
+                if exp == 0{
+                    return (1,false);
+                }
+                let mut base = self;
+                let mut acc: Self = 1;
+                let mut overflown = false;
+                // Scratch space for storing results of overflowing_mul.
+                let mut r;
+
+                while exp > 1 {
+                    if (exp & 1) == 1 {
+                        r = acc.overflowing_mul(base);
+                        acc = r.0;
+                        overflown |= r.1;
+                    }
+                    exp /= 2;
+                    r = base.overflowing_mul(base);
+                    base = r.0;
                     overflown |= r.1;
                 }
-                exp /= 2;
-                r = base.overflowing_mul(base);
-                base = r.0;
-                overflown |= r.1;
-            }
 
-            // since exp!=0, finally the exp must be 1.
-            // Deal with the final bit of the exponent separately, since
-            // squaring the base afterwards is not necessary and may cause a
-            // needless overflow.
-            r = acc.overflowing_mul(base);
-            r.1 |= overflown;
+                // since exp!=0, finally the exp must be 1.
+                // Deal with the final bit of the exponent separately, since
+                // squaring the base afterwards is not necessary and may cause a
+                // needless overflow.
+                r = acc.overflowing_mul(base);
+                r.1 |= overflown;
 
-            r
+                r
+            }
         }
 
         /// Raises self to the power of `exp`, using exponentiation by squaring.
@@ -2387,28 +2450,64 @@ macro_rules! uint_impl {
         #[rustc_const_stable(feature = "const_int_pow", since = "1.50.0")]
         #[must_use = "this returns the result of the operation, \
                       without modifying the original"]
+        #[rustc_allow_const_fn_unstable(is_val_statically_known, const_int_unchecked_arith)]
         #[inline]
         #[rustc_inherit_overflow_checks]
+        #[track_caller] // Hides the hackish overflow check for powers of two.
         pub const fn pow(self, mut exp: u32) -> Self {
-            if exp == 0 {
-                return 1;
-            }
-            let mut base = self;
-            let mut acc = 1;
+            // LLVM now knows that `self` is a constant value, but not a
+            // constant in Rust. This allows us to compute the power used at
+            // compile-time.
+            //
+            // This will likely add a branch in debug builds, but this should
+            // be ok.
+            //
+            // This is a massive performance boost in release builds as you can
+            // get the power of a power of two and the exponent through a `shl`
+            // instruction, but we must add a couple more checks for parity with
+            // our own `pow`.
+            // SAFETY: This path has the same behavior as the other.
+            if unsafe { intrinsics::is_val_statically_known(self) }
+                && self.is_power_of_two()
+            {
+                if self == 1 { // Avoid divide by zero
+                    return 1;
+                }
+                // SAFETY: We just checked this is a power of two. and above zero.
+                let power_used = unsafe { intrinsics::cttz_nonzero(self) as u32 };
+                if exp > Self::BITS / power_used { // Division of constants is free
+                    #[allow(arithmetic_overflow)]
+                    return Self::MAX * Self::MAX * 0;
+                }
 
-            while exp > 1 {
-                if (exp & 1) == 1 {
-                    acc = acc * base;
+                // SAFETY: exp <= Self::BITS / power_used
+                unsafe { intrinsics::unchecked_shl(
+                    1 as Self,
+                    intrinsics::unchecked_mul(power_used, exp) as Self
+                )}
+                // LLVM doesn't always optimize out the checks
+                // at the ir level.
+            } else {
+                if exp == 0 {
+                    return 1;
+                }
+                let mut base = self;
+                let mut acc = 1;
+
+                while exp > 1 {
+                    if (exp & 1) == 1 {
+                        acc = acc * base;
+                    }
+                    exp /= 2;
+                    base = base * base;
                 }
-                exp /= 2;
-                base = base * base;
-            }
 
-            // since exp!=0, finally the exp must be 1.
-            // Deal with the final bit of the exponent separately, since
-            // squaring the base afterwards is not necessary and may cause a
-            // needless overflow.
-            acc * base
+                // since exp!=0, finally the exp must be 1.
+                // Deal with the final bit of the exponent separately, since
+                // squaring the base afterwards is not necessary and may cause a
+                // needless overflow.
+                acc * base
+            }
         }
 
         /// Returns the square root of the number, rounded down.
diff --git a/library/core/src/ops/async_function.rs b/library/core/src/ops/async_function.rs
new file mode 100644
index 00000000000..965873f163e
--- /dev/null
+++ b/library/core/src/ops/async_function.rs
@@ -0,0 +1,108 @@
+use crate::future::Future;
+use crate::marker::Tuple;
+
+/// An async-aware version of the [`Fn`](crate::ops::Fn) trait.
+///
+/// All `async fn` and functions returning futures implement this trait.
+#[unstable(feature = "async_fn_traits", issue = "none")]
+#[rustc_paren_sugar]
+#[fundamental]
+#[must_use = "async closures are lazy and do nothing unless called"]
+#[cfg_attr(not(bootstrap), lang = "async_fn")]
+pub trait AsyncFn<Args: Tuple>: AsyncFnMut<Args> {
+    /// Future returned by [`AsyncFn::async_call`].
+    #[unstable(feature = "async_fn_traits", issue = "none")]
+    type CallFuture<'a>: Future<Output = Self::Output>
+    where
+        Self: 'a;
+
+    /// Call the [`AsyncFn`], returning a future which may borrow from the called closure.
+    #[unstable(feature = "async_fn_traits", issue = "none")]
+    extern "rust-call" fn async_call(&self, args: Args) -> Self::CallFuture<'_>;
+}
+
+/// An async-aware version of the [`FnMut`](crate::ops::FnMut) trait.
+///
+/// All `async fn` and functions returning futures implement this trait.
+#[unstable(feature = "async_fn_traits", issue = "none")]
+#[rustc_paren_sugar]
+#[fundamental]
+#[must_use = "async closures are lazy and do nothing unless called"]
+#[cfg_attr(not(bootstrap), lang = "async_fn_mut")]
+pub trait AsyncFnMut<Args: Tuple>: AsyncFnOnce<Args> {
+    /// Future returned by [`AsyncFnMut::async_call_mut`].
+    #[unstable(feature = "async_fn_traits", issue = "none")]
+    type CallMutFuture<'a>: Future<Output = Self::Output>
+    where
+        Self: 'a;
+
+    /// Call the [`AsyncFnMut`], returning a future which may borrow from the called closure.
+    #[unstable(feature = "async_fn_traits", issue = "none")]
+    extern "rust-call" fn async_call_mut(&mut self, args: Args) -> Self::CallMutFuture<'_>;
+}
+
+/// An async-aware version of the [`FnOnce`](crate::ops::FnOnce) trait.
+///
+/// All `async fn` and functions returning futures implement this trait.
+#[unstable(feature = "async_fn_traits", issue = "none")]
+#[rustc_paren_sugar]
+#[fundamental]
+#[must_use = "async closures are lazy and do nothing unless called"]
+#[cfg_attr(not(bootstrap), lang = "async_fn_once")]
+pub trait AsyncFnOnce<Args: Tuple> {
+    /// Future returned by [`AsyncFnOnce::async_call_once`].
+    #[unstable(feature = "async_fn_traits", issue = "none")]
+    type CallOnceFuture: Future<Output = Self::Output>;
+
+    /// Output type of the called closure's future.
+    #[unstable(feature = "async_fn_traits", issue = "none")]
+    type Output;
+
+    /// Call the [`AsyncFnOnce`], returning a future which may move out of the called closure.
+    #[unstable(feature = "async_fn_traits", issue = "none")]
+    extern "rust-call" fn async_call_once(self, args: Args) -> Self::CallOnceFuture;
+}
+
+mod impls {
+    use super::{AsyncFn, AsyncFnMut, AsyncFnOnce};
+    use crate::future::Future;
+    use crate::marker::Tuple;
+
+    #[unstable(feature = "async_fn_traits", issue = "none")]
+    impl<F: Fn<A>, A: Tuple> AsyncFn<A> for F
+    where
+        <F as FnOnce<A>>::Output: Future,
+    {
+        type CallFuture<'a> = <F as FnOnce<A>>::Output where Self: 'a;
+
+        extern "rust-call" fn async_call(&self, args: A) -> Self::CallFuture<'_> {
+            self.call(args)
+        }
+    }
+
+    #[unstable(feature = "async_fn_traits", issue = "none")]
+    impl<F: FnMut<A>, A: Tuple> AsyncFnMut<A> for F
+    where
+        <F as FnOnce<A>>::Output: Future,
+    {
+        type CallMutFuture<'a> = <F as FnOnce<A>>::Output where Self: 'a;
+
+        extern "rust-call" fn async_call_mut(&mut self, args: A) -> Self::CallMutFuture<'_> {
+            self.call_mut(args)
+        }
+    }
+
+    #[unstable(feature = "async_fn_traits", issue = "none")]
+    impl<F: FnOnce<A>, A: Tuple> AsyncFnOnce<A> for F
+    where
+        <F as FnOnce<A>>::Output: Future,
+    {
+        type CallOnceFuture = <F as FnOnce<A>>::Output;
+
+        type Output = <<F as FnOnce<A>>::Output as Future>::Output;
+
+        extern "rust-call" fn async_call_once(self, args: A) -> Self::CallOnceFuture {
+            self.call_once(args)
+        }
+    }
+}
diff --git a/library/core/src/ops/mod.rs b/library/core/src/ops/mod.rs
index 35654d0b853..4289a86f89b 100644
--- a/library/core/src/ops/mod.rs
+++ b/library/core/src/ops/mod.rs
@@ -139,6 +139,7 @@
 #![stable(feature = "rust1", since = "1.0.0")]
 
 mod arith;
+mod async_function;
 mod bit;
 mod control_flow;
 mod coroutine;
@@ -173,6 +174,9 @@ pub use self::drop::Drop;
 #[stable(feature = "rust1", since = "1.0.0")]
 pub use self::function::{Fn, FnMut, FnOnce};
 
+#[unstable(feature = "async_fn_traits", issue = "none")]
+pub use self::async_function::{AsyncFn, AsyncFnMut, AsyncFnOnce};
+
 #[stable(feature = "rust1", since = "1.0.0")]
 pub use self::index::{Index, IndexMut};
 
diff --git a/library/core/src/ptr/const_ptr.rs b/library/core/src/ptr/const_ptr.rs
index 12ff64de879..5ce9ddeb676 100644
--- a/library/core/src/ptr/const_ptr.rs
+++ b/library/core/src/ptr/const_ptr.rs
@@ -220,7 +220,7 @@ impl<T: ?Sized> *const T {
     /// provenance. (Reconstructing address space information, if required, is your responsibility.)
     ///
     /// Using this method means that code is *not* following [Strict
-    /// Provenance][../index.html#strict-provenance] rules. Supporting
+    /// Provenance][super#strict-provenance] rules. Supporting
     /// [`from_exposed_addr`][] complicates specification and reasoning and may not be supported by
     /// tools that help you to stay conformant with the Rust memory model, so it is recommended to
     /// use [`addr`][pointer::addr] wherever possible.
@@ -232,7 +232,7 @@ impl<T: ?Sized> *const T {
     /// available.
     ///
     /// It is unclear whether this method can be given a satisfying unambiguous specification. This
-    /// API and its claimed semantics are part of [Exposed Provenance][../index.html#exposed-provenance].
+    /// API and its claimed semantics are part of [Exposed Provenance][super#exposed-provenance].
     ///
     /// [`from_exposed_addr`]: from_exposed_addr
     #[must_use]
diff --git a/library/core/src/ptr/mod.rs b/library/core/src/ptr/mod.rs
index a9078854125..dce7e035fc7 100644
--- a/library/core/src/ptr/mod.rs
+++ b/library/core/src/ptr/mod.rs
@@ -649,7 +649,7 @@ pub const fn invalid_mut<T>(addr: usize) -> *mut T {
 /// address makes sense in the address space that this pointer will be used with.
 ///
 /// Using this function means that code is *not* following [Strict
-/// Provenance][../index.html#strict-provenance] rules. "Guessing" a
+/// Provenance][self#strict-provenance] rules. "Guessing" a
 /// suitable provenance complicates specification and reasoning and may not be supported by
 /// tools that help you to stay conformant with the Rust memory model, so it is recommended to
 /// use [`with_addr`][pointer::with_addr] wherever possible.
@@ -660,7 +660,7 @@ pub const fn invalid_mut<T>(addr: usize) -> *mut T {
 /// pointer has to pick up.
 ///
 /// It is unclear whether this function can be given a satisfying unambiguous specification. This
-/// API and its claimed semantics are part of [Exposed Provenance][../index.html#exposed-provenance].
+/// API and its claimed semantics are part of [Exposed Provenance][self#exposed-provenance].
 #[must_use]
 #[inline(always)]
 #[unstable(feature = "exposed_provenance", issue = "95228")]
@@ -689,7 +689,7 @@ where
 /// address makes sense in the address space that this pointer will be used with.
 ///
 /// Using this function means that code is *not* following [Strict
-/// Provenance][../index.html#strict-provenance] rules. "Guessing" a
+/// Provenance][self#strict-provenance] rules. "Guessing" a
 /// suitable provenance complicates specification and reasoning and may not be supported by
 /// tools that help you to stay conformant with the Rust memory model, so it is recommended to
 /// use [`with_addr`][pointer::with_addr] wherever possible.
@@ -700,7 +700,7 @@ where
 /// pointer has to pick up.
 ///
 /// It is unclear whether this function can be given a satisfying unambiguous specification. This
-/// API and its claimed semantics are part of [Exposed Provenance][../index.html#exposed-provenance].
+/// API and its claimed semantics are part of [Exposed Provenance][self#exposed-provenance].
 #[must_use]
 #[inline(always)]
 #[unstable(feature = "exposed_provenance", issue = "95228")]
diff --git a/library/core/src/ptr/mut_ptr.rs b/library/core/src/ptr/mut_ptr.rs
index 4f5fca4367d..3e5678a7d91 100644
--- a/library/core/src/ptr/mut_ptr.rs
+++ b/library/core/src/ptr/mut_ptr.rs
@@ -227,7 +227,7 @@ impl<T: ?Sized> *mut T {
     /// provenance. (Reconstructing address space information, if required, is your responsibility.)
     ///
     /// Using this method means that code is *not* following [Strict
-    /// Provenance][../index.html#strict-provenance] rules. Supporting
+    /// Provenance][super#strict-provenance] rules. Supporting
     /// [`from_exposed_addr_mut`][] complicates specification and reasoning and may not be supported
     /// by tools that help you to stay conformant with the Rust memory model, so it is recommended
     /// to use [`addr`][pointer::addr] wherever possible.
@@ -239,7 +239,7 @@ impl<T: ?Sized> *mut T {
     /// available.
     ///
     /// It is unclear whether this method can be given a satisfying unambiguous specification. This
-    /// API and its claimed semantics are part of [Exposed Provenance][../index.html#exposed-provenance].
+    /// API and its claimed semantics are part of [Exposed Provenance][super#exposed-provenance].
     ///
     /// [`from_exposed_addr_mut`]: from_exposed_addr_mut
     #[must_use]
diff --git a/library/core/src/tuple.rs b/library/core/src/tuple.rs
index e1b77e34f21..47e27bdc735 100644
--- a/library/core/src/tuple.rs
+++ b/library/core/src/tuple.rs
@@ -2,7 +2,7 @@
 
 use crate::cmp::Ordering::{self, *};
 use crate::marker::ConstParamTy;
-use crate::marker::{StructuralEq, StructuralPartialEq};
+use crate::marker::StructuralPartialEq;
 
 // Recursive macro for implementing n-ary tuple functions and operations
 //
@@ -64,7 +64,8 @@ macro_rules! tuple_impls {
         maybe_tuple_doc! {
             $($T)+ @
             #[unstable(feature = "structural_match", issue = "31434")]
-            impl<$($T),+> StructuralEq for ($($T,)+)
+            #[cfg(bootstrap)]
+            impl<$($T),+> crate::marker::StructuralEq for ($($T,)+)
             {}
         }