miri: checked_pow: overflowing shift by 64 in `unchecked_shl`

[morrisonlevi]

Code

I tried this code:

fn main() {
    match 2u64.checked_pow(64) {
        Some(n) => println!("2^64: {n}"),
        None => {}
    };
}

I expected that a checked_* operation would specifically not cause UB on overflow.

Instead, this happened (playground):

MIRIFLAGS=-Zmiri-backtrace=full cargo +nightly miri run
Preparing a sysroot for Miri (target: aarch64-apple-darwin)... done
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `/Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/bin/cargo-miri runner target/miri/aarch64-apple-darwin/debug/miri`
error: Undefined Behavior: overflowing shift by 64 in `unchecked_shl`
    --> /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/num/mod.rs:1181:5
     |
1181 | /     uint_impl! {
1182 | |         Self = u64,
1183 | |         ActualT = u64,
1184 | |         SignedT = i64,
...    |
1198 | |         bound_condition = "",
1199 | |     }
     | |_____^ overflowing shift by 64 in `unchecked_shl`
     |
     = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
     = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information

<snip> 

error: aborting due to 1 previous error

Version it worked on

It most recently worked on: cargo 1.77.0-nightly (84976cd69 2024-01-12)

Version with regression

cargo 1.77.0-nightly (7bb7b5395 2024-01-20)

I didn't bisect this, but I believe it started happening with GH PR #119911.

Backtrace

Backtrace

   = note: BACKTRACE:
     = note: inside `core::num::<impl u64>::checked_pow` at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/num/uint_macros.rs:1382:31: 1385:18
note: inside `main`
    --> src/main.rs:2:11
     |
2    |     match 2u64.checked_pow(64) {
     |           ^^^^^^^^^^^^^^^^^^^^
     = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/ops/function.rs:250:5: 250:71
     = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:155:18: 155:21
     = note: inside closure at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/rt.rs:166:18: 166:82
     = note: inside `std::ops::function::impls::<impl std::ops::FnOnce<()> for &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>::call_once` at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/core/src/ops/function.rs:284:13: 284:31
     = note: inside `std::panicking::r#try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/panicking.rs:554:40: 554:43
     = note: inside `std::panicking::r#try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/panicking.rs:518:19: 518:81
     = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/panic.rs:142:14: 142:33
     = note: inside closure at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/rt.rs:148:48: 148:73
     = note: inside `std::panicking::r#try::do_call::<{closure@std::rt::lang_start_internal::{closure#2}}, isize>` at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/panicking.rs:554:40: 554:43
     = note: inside `std::panicking::r#try::<isize, {closure@std::rt::lang_start_internal::{closure#2}}>` at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/panicking.rs:518:19: 518:81
     = note: inside `std::panic::catch_unwind::<{closure@std::rt::lang_start_internal::{closure#2}}, isize>` at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/panic.rs:142:14: 142:33
     = note: inside `std::rt::lang_start_internal` at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/rt.rs:148:20: 148:98
     = note: inside `std::rt::lang_start::<()>` at /Users/levi.morrison/.rustup/toolchains/nightly-aarch64-apple-darwin/lib/rustlib/src/rust/library/std/src/rt.rs:165:17: 170:6
     = note: this error originates in the macro `uint_impl` (in Nightly builds, run with -Z macro-backtrace for more info)

I believe GH PR #119911 is the cause.

[Noratrieb]

@NCGThompson @oli-obk I feel like int macro changes would have best been split out into a separate PR^^

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

@rustbot label -I-prioritize +P-high +T-compiler

[NCGThompson]

    // 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

~~I think the issue here is I needed to use >= rather than >.~~

@rustbot claim

[NCGThompson]

@rustbot assign @oli-obk

It looks like oli-obk already fixed it.

@rustbot release-assignment

[cuviper]

Just to make sure it's not lost -- we also need to handle the case where Self::BITS / power_used rounds down.

https://github.com/rust-lang/rust/pull/120546#issuecomment-1921885531

[NCGThompson]

We want to check if exp * power_used is less than Self::BITS or not. Using algebra, we know that in real life as long as power_used > 0:

exp * power_used ≥ Self::BITS ≡ exp ≥ Self::BITS / power_used

However, we can't use exact division, only floor division (f.d.). Unfortunately,

exp * power_used ≥ Self::BITS ≢ exp ≥ Self::BITS f.d. power_used

and

exp * power_used ≥ Self::BITS ≢ exp > Self::BITS f.d. power_used

Since we are dealing exclusively with non-negative integers, we can say that

exp * power_used ≥ Self::BITS ≡ exp * power_used > Self::BITS - 1 ≡ exp > (Self::BITS - 1) / power_used

, that

exp = (Self::BITS - 1) / power_used implies (Self::BITS - 1) / power_used = (Self::BITS - 1) f.d. power_used

, and that

Self::BITS / power_used - (Self::BITS - 1) f.d. power_used ≤ 1

From there, we can work out that

exp * power_used ≥ Self::BITS ≡ exp > (Self::BITS - 1) f.d. power_used

and exp > (Self::BITS - 1) f.d. power_used can be computed in Rust with

if exp > (Self::BITS - 1) / power_used { return None; }

@oli-obk Now you don't need to go math golfing.

[cuviper]

For signed types, note that 2.pow(BITS - 1) is still an overflow, but (-2).pow(BITS - 1) is its MIN.

[NCGThompson]

For signed types, note that 2.pow(BITS - 1) is still an overflow, but (-2).pow(BITS - 1) is its MIN.

Right. Since overflow on BITS - 1 is dependent on the sign of the base, we use a separate check for that. ~~The optimizer folds the two checks into a single comparison.~~

[cuviper]

Oh, you mean this? Then OK, but that could use a comment.

https://github.com/rust-lang/rust/blob/11f32b73e0dc9287e305b5b9980d24aecdc8c17f/library/core/src/num/int_macros.rs#L1402-L1404

[cuviper]

The revert landed after the branch move, so let's re-open until that's backported.

[cuviper]

Backport was done in #121069.