Incorrect MIR optimizations at level 3: local incorrectly marked dead

[RalfJung]

The following program runs fine in Miri on mir-opt-levels 0-2, but in level 3 it errors:

fn main() {
    use std::fmt::Debug;

    fn test<T : Copy + Debug + PartialEq>(x : T) {
        let v : &[T] = &[x, x, x];
        match v {
            [ref v1, ref v2, ref v3] => [v1 as *const _, v2 as *const _, v3 as *const _],
            _ => unreachable!()
        };
    }

    test(0u32);
}

The error is:

error: Undefined Behavior: accessing a dead local variable
  --> tests/run-pass/slices.rs:9:13
   |
9  |             [ref v1, ref v2, ref v3] => [v1 as *const _, v2 as *const _, v3 as *const _],
   |             ^^^^^^^^^^^^^^^^^^^^^^^^ accessing a dead local variable
   |
   = 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
           
   = note: inside `main::test::<u32>` at tests/run-pass/slices.rs:9:13
note: inside `main` at tests/run-pass/slices.rs:14:5
  --> tests/run-pass/slices.rs:14:5
   |
14 |     test(0u32);
   |     ^^^^^^^^^^
   = note: inside `<fn() as std::ops::FnOnce<()>>::call_once - shim(fn())` at /home/r/.rustup/toolchains/miri/lib/rustlib/src/rust/library/core/src/ops/function.rs:227:5
   = note: inside `std::sys_common::backtrace::__rust_begin_short_backtrace::<fn(), ()>` at /home/r/.rustup/toolchains/miri/lib/rustlib/src/rust/library/std/src/sys_common/backtrace.rs:137:18
   = note: inside closure at /home/r/.rustup/toolchains/miri/lib/rustlib/src/rust/library/std/src/rt.rs:66:18
   = 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 /home/r/.rustup/toolchains/miri/lib/rustlib/src/rust/library/core/src/ops/function.rs:259:13
   = note: inside `std::panicking::try::do_call::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/r/.rustup/toolchains/miri/lib/rustlib/src/rust/library/std/src/panicking.rs:381:40
   = note: inside `std::panicking::try::<i32, &dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe>` at /home/r/.rustup/toolchains/miri/lib/rustlib/src/rust/library/std/src/panicking.rs:345:19
   = note: inside `std::panic::catch_unwind::<&dyn std::ops::Fn() -> i32 + std::marker::Sync + std::panic::RefUnwindSafe, i32>` at /home/r/.rustup/toolchains/miri/lib/rustlib/src/rust/library/std/src/panic.rs:382:14
   = note: inside `std::rt::lang_start_internal` at /home/r/.rustup/toolchains/miri/lib/rustlib/src/rust/library/std/src/rt.rs:51:25
   = note: inside `std::rt::lang_start::<()>` at /home/r/.rustup/toolchains/miri/lib/rustlib/src/rust/library/std/src/rt.rs:65:5

Looks like something changes the liveness ranges of locals and it does so incorrectly.

Cc @rust-lang/wg-mir-opt

[tmiasko]

Could you describe affected rustc version and reproduction steps?

[RalfJung]

The rustc version is commit e114d62, but most likely a nightly will also do it.

To reproduce, run this in a Miri checkout:

./miri run tests/run-pass/slices.rs -Zmir-opt-level=3

[tmiasko]

The SimplifyComparisonIntegral introduces StorageDead for a local which didn't have any markers before. Currently this also makes the local dead on the entry to the function.

Related to the issue #42371 about semantics of StorageLive without matching StorageDead (this would be the reverse).

[RalfJung]

The LLVM docs for their version of StorageDead (which the Rust thing translates to) say

This intrinsic indicates that before this point in the code, the value of the memory pointed to by ptr is dead. This means that it is known to never be used and has an undefined value. A load from the pointer that precedes this intrinsic can be replaced with 'undef'.

So just introducing a StorageDead without also having appropriate StorageLive is pretty clearly wrong, I would say.

[bjorn3]

That is the doc for llvm.lifetime.start, not llvm.lifetime.end. The doc for llvm.lifetime.end is:

This intrinsic indicates that after this point in the code, the value of the memory pointed to by ptr is dead. This means that it is known to never be used and has an undefined value. Any stores into the memory object following this intrinsic may be removed as dead.

[RalfJung]

oops sorry, yeah.

We'd have to check the MIR here to see if it makes any sense at all; however, currently I think not just Miri but also our dataflow framework assumes that variables with any liveness annotations are initially dead.

[jumbatm]

Diff for this case before/after SimplifyComparisonIntegral:

--- dead.main-test.005-004.SimplifyComparisonIntegral.before.mir 
+++ dead.main-test.005-004.SimplifyComparisonIntegral.after.mir
@@ -1,4 +1,4 @@
-// MIR for `test` before SimplifyComparisonIntegral
+// MIR for `test` after SimplifyComparisonIntegral
 
 fn test(_1: T) -> () {
     debug x => _1;                       // in scope 0 at dead.rs:4:43: 4:44
@@ -56,11 +56,12 @@
         StorageLive(_9);                 // scope 1 at dead.rs:6:9: 9:10
         _10 = Len((*_2));                // scope 1 at dead.rs:7:13: 7:37
         _11 = const 3_usize;             // scope 1 at dead.rs:7:13: 7:37
-        _12 = Eq(move _10, const 3_usize); // scope 1 at dead.rs:7:13: 7:37
-        switchInt(move _12) -> [false: bb1, otherwise: bb2]; // scope 1 at dead.rs:7:13: 7:37
+        nop;                             // scope 1 at dead.rs:7:13: 7:37
+        switchInt(move _10) -> [3_usize: bb2, otherwise: bb1]; // scope 1 at dead.rs:7:13: 7:37
     }
 
     bb1: {
+        StorageDead(_10);                // scope 1 at dead.rs:7:13: 7:37
         StorageLive(_22);                // scope 1 at /rust/library/std/src/macros.rs:13:23: 13:52
         begin_panic::<&str>(const "internal error: entered unreachable code"); // scope 1 at /rust/library/std/src/macros.rs:13:23: 13:52
                                          // mir::Constant
@@ -75,6 +76,7 @@
     }
 
     bb2: {
+        StorageDead(_10);                // scope 1 at dead.rs:7:13: 7:37
         StorageLive(_13);                // scope 1 at dead.rs:7:14: 7:20
         _13 = &(*_2)[0 of 3];            // scope 1 at dead.rs:7:14: 7:20
         StorageLive(_14);                // scope 1 at dead.rs:7:22: 7:28

Note the StorageDead(_10) placed in both successors of the switchInt, when there was no StorageLive(_10) to begin with.

cc @simonvandel -- along the lines of #75370 (comment), you could leave the switchInt as a copy in this case for later optimisation passes to clean up. This is definitely a case I can cover for #75993.

[RalfJung]

Does this analysis ensure that _10 is not used any more afterwards? As in, would it be sufficient to add a StorageLive in the start block? (I am not saying that that's a good fix, just trying to feel out the design space here.)

I guess I am also surprised that an "integral comparison simplification" pass touches storage liveness.

[oli-obk]

That part is my fault. I incorrectly assumed that there's a storagedead before the switch. Maybe there is one in some situations, idk, if there is, we should probably just not do the optimization instead of rewriting the storage markers.