Misoptimisation of complex control flow only under low `mir-opt-level`

[cbeuw]

Apologies for the not-very-readable reproduction. It was generated by a fuzzer and this is the best I can minimise it to.

use std::ptr;
pub fn print_var(v: u8) {
    println!("{v}");
}
pub unsafe fn fn12_rs() -> ([u128; 7], *mut i8, *mut bool) {
    let mut v2: bool = false;
    let mut v8: u64 = 0;
    let mut v9: usize = 0;
    let mut v12: *mut u8 = ptr::null_mut();
    let mut v17: *mut bool = ptr::null_mut();
    let mut v20: [u8; 8] = Default::default();
    let mut v21: [u8; 8] = Default::default();
    let mut v31: (bool, u8, usize, f32) = Default::default();
    let mut v33: ([u128; 7], *mut i8, *mut bool) = ([0; 7], ptr::null_mut(), ptr::null_mut());
    let mut v39: (usize, [u128; 7], ([u32; 6], usize, *mut [u32; 6]), [u32; 2]) =
        (0, [0; 7], ([0; 6], 0, ptr::null_mut()), [0; 2]);
    let mut ret: ([u128; 7], *mut i8, *mut bool) = ([0; 7], ptr::null_mut(), ptr::null_mut());
    ret.2 = core::ptr::addr_of_mut!(v2);
    'l0: loop {
        v12 = core::ptr::addr_of_mut!(v20[v9]);
        v20 = [197_u8; 8];
        v9 = 2_usize;
        'l1: loop {
            match *v12 {
                197 => {
                    // Taken
                    v8 = 13978819448286864680_u64;
                    v33.2 = ret.2;
                    match v39.0 {
                        0 => {
                            // Taken
                            'l2: loop {
                                v20 = [11_u8; 8]; // What LLVM with low mir-opt prints
                                (*v12) = 22; // What Miri prints
                                'l3: loop {
                                    v21 = v20;
                                    match v8 {
                                        13978819448286864680 => {
                                            // Taken
                                            v39.2 .0 = [2262110980_u32; 6];
                                            v8 = !13152832795211590855_u64;
                                            v39.0 = 6;
                                            v17 = v33.2;
                                            v33.2 = core::ptr::addr_of_mut!(v31.0);
                                            v31.1 = *v12;
                                            (*v17) = true;
                                            v20 = v21;
                                            match v39.0 {
                                                6 => {
                                                    // Taken
                                                    print_var(v31.1);
                                                }
                                                0 => continue 'l2,
                                                _ => return ret,
                                            }
                                        }
                                        _ => continue 'l0,
                                    }
                                }
                            }
                        }
                        _ => return ret,
                    }
                }
                4 => {
                    v12 = core::ptr::addr_of_mut!(v20[v9]);
                }
                _ => return ret,
            }
        }
    }
}
pub fn main() {
    unsafe {
        fn12_rs();
    }
}

The program has no UB under -Zmiri-tree-borrows, and Miri prints 22, this is also the result with -Zmir-opt-level>=2 -Copt-level=3

% rustc -Zmir-opt-level=2 -Copt-level=3 minimised.rs && ./minimised
22

Very strangely, if you drop mir-opt-level to 0 or 1, the result becomes 11 which is wrong.

% rustc -Zmir-opt-level=1 -Copt-level=3 minimised.rs && ./minimised
11

Reproducible on both Apple Silicon macOS and x86_64 Linux

rustc 1.71.0-nightly (a2b1646c5 2023-05-25)
binary: rustc
commit-hash: a2b1646c597329d0a25efa3889b66650f65de1de
commit-date: 2023-05-25
host: aarch64-apple-darwin
release: 1.71.0-nightly
LLVM version: 16.0.4

rustc 1.71.0-nightly (a2b1646c5 2023-05-25)
binary: rustc
commit-hash: a2b1646c597329d0a25efa3889b66650f65de1de
commit-date: 2023-05-25
host: x86_64-unknown-linux-gnu
release: 1.71.0-nightly
LLVM version: 16.0.4

cc @RalfJung @nikic

[Urgau]

The program has no UB under -Zmiri-tree-borrows, and Miri prints 22, this is also the result with -Zmir-opt-level>=2 -Copt-level=3

Executing the program trough cargo-miri in the playground reveals that under Stacked Borrows there is UB:

error: Undefined Behavior: attempting a read access using <2756> at alloc1466[0x0], but that tag does not exist in the borrow stack for this location
  --> src/main.rs:24:13
   |
24 |             match *v12 {
   |             ^^^^^^^^^^
   |             |
   |             attempting a read access using <2756> at alloc1466[0x0], but that tag does not exist in the borrow stack for this location
   |             this error occurs as part of an access at alloc1466[0x0..0x1]
   |
   = help: this indicates a potential bug in the program: it performed an invalid operation, but the Stacked Borrows rules it violated are still experimental
   = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md for further information
help: <2756> was created by a SharedReadWrite retag at offsets [0x0..0x1]
  --> src/main.rs:20:15
   |
20 |         v12 = core::ptr::addr_of_mut!(v20[v9]);
   |               ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: <2756> was later invalidated at offsets [0x0..0x1] by a write access
  --> src/main.rs:21:9
   |
21 |         v20 = [197_u8; 8];
   |         ^^^^^^^^^^^^^^^^^
   = note: BACKTRACE (of the first span):
   = note: inside `fn12_rs` at src/main.rs:24:13: 24:23
note: inside `main`
  --> src/main.rs:75:9
   |
75 |         fn12_rs();
   |         ^^^^^^^^^
   = note: this error originates in the macro `core::ptr::addr_of_mut` (in Nightly builds, run with -Z macro-backtrace for more info)

[cbeuw]

under Stacked Borrows there is UB

It does, and since the UB involves v12 and v20 which carry the wrong and right results (11 and 22), the miscompilation is likely due to an assumption that was valid under SB but not under TB. Though this bug probably isn't in mir-opt as a low mir-opt-level gives the wrong result. It could be in IR gen or LLVM itself

[saethlin]

(defensively labeled this as unsound because that seems more likely than not)

[saethlin]

ConstProp is relevant:

$ rustc +nightly -Zmir-opt-level=0 -Zmir-enable-passes=+ConstProp -Copt-level=3 main.rs && ./main
22

$ rustc +nightly -Zmir-opt-level=0 -Copt-level=3 main.rs && ./main
11

[saethlin]

Here's the diff that ConstProp produces. Does this look relevant?

diff --git a/mir_dump/main.fn12_rs.005-002.ConstProp.before.mir b/mir_dump/main.fn12_rs.005-002.ConstProp.after.mir
index 038b484..44ab18e 100644
--- a/mir_dump/main.fn12_rs.005-002.ConstProp.before.mir
+++ b/mir_dump/main.fn12_rs.005-002.ConstProp.after.mir
@@ -1,4 +1,4 @@
-// MIR for `fn12_rs` before ConstProp
+// MIR for `fn12_rs` after ConstProp
 
 fn fn12_rs() -> ([u128; 7], *mut i8, *mut bool) {
     let mut _0: ([u128; 7], *mut i8, *mut bool); // return place in scope 0 at main.rs:5:28: 5:59
@@ -213,7 +213,7 @@ fn fn12_rs() -> ([u128; 7], *mut i8, *mut bool) {
         StorageLive(_26);                // scope 11 at /rustc/1c53407e8c7cc922d718bde61ca34f47b6d2120f/library/core/src/ptr/mod.rs:2034:5: 2034:20
         StorageLive(_27);                // scope 11 at main.rs:20:43: 20:45
         _27 = _3;                        // scope 11 at main.rs:20:43: 20:45
-        _28 = Len(_6);                   // scope 11 at main.rs:20:39: 20:46
+        _28 = const 8_usize;             // scope 11 at main.rs:20:39: 20:46
         _29 = Lt(_27, _28);              // scope 11 at main.rs:20:39: 20:46
         assert(move _29, "index out of bounds: the length is {} but the index is {}", move _28, _27) -> bb12; // scope 11 at main.rs:20:39: 20:46
     }
@@ -274,7 +274,7 @@ fn fn12_rs() -> ([u128; 7], *mut i8, *mut bool) {
 
     bb20: {
         ((_13.2: ([u32; 6], usize, *mut [u32; 6])).0: [u32; 6]) = [const 2262110980_u32; 6]; // scope 11 at main.rs:40:45: 40:75
-        _2 = Not(const 13152832795211590855_u64); // scope 11 at main.rs:41:45: 41:75
+        _2 = const 5293911278497960760_u64; // scope 11 at main.rs:41:45: 41:75
         (_13.0: usize) = const 6_usize;  // scope 11 at main.rs:42:45: 42:54
         StorageLive(_35);                // scope 11 at main.rs:43:51: 43:56
         _35 = (_9.2: *mut bool);         // scope 11 at main.rs:43:51: 43:56
@@ -293,7 +293,7 @@ fn fn12_rs() -> ([u128; 7], *mut i8, *mut bool) {
         _38 = _7;                        // scope 11 at main.rs:47:51: 47:54
         _6 = move _38;                   // scope 11 at main.rs:47:45: 47:54
         StorageDead(_38);                // scope 11 at main.rs:47:53: 47:54
-        switchInt((_13.0: usize)) -> [6: bb22, 0: bb24, otherwise: bb21]; // scope 11 at main.rs:48:45: 48:56
+        switchInt(const 6_usize) -> [6: bb22, 0: bb24, otherwise: bb21]; // scope 11 at main.rs:48:45: 48:56
     }
 
     bb21: {
@@ -329,7 +329,7 @@ fn fn12_rs() -> ([u128; 7], *mut i8, *mut bool) {
         StorageLive(_45);                // scope 11 at /rustc/1c53407e8c7cc922d718bde61ca34f47b6d2120f/library/core/src/ptr/mod.rs:2034:5: 2034:20
         StorageLive(_46);                // scope 11 at main.rs:66:55: 66:57
         _46 = _3;                        // scope 11 at main.rs:66:55: 66:57
-        _47 = Len(_6);                   // scope 11 at main.rs:66:51: 66:58
+        _47 = const 8_usize;             // scope 11 at main.rs:66:51: 66:58
         _48 = Lt(_46, _47);              // scope 11 at main.rs:66:51: 66:58
         assert(move _48, "index out of bounds: the length is {} but the index is {}", move _47, _46) -> bb26; // scope 11 at main.rs:66:51: 66:58
     }

Relevant stuff is buried down in the pile of scopes ugh. The relevant diff smells like

-        switchInt((_13.0: usize)) -> [6: bb22, 0: bb24, otherwise: bb21]; // scope 11 at main.rs:48:45: 48:56
+        switchInt(const 6_usize) -> [6: bb22, 0: bb24, otherwise: bb21]; // scope 11 at main.rs:48:45: 48:56

[cbeuw]

-        switchInt((_13.0: usize)) -> [6: bb22, 0: bb24, otherwise: bb21]; // scope 11 at main.rs:48:45: 48:56
+        switchInt(const 6_usize) -> [6: bb22, 0: bb24, otherwise: bb21]; // scope 11 at main.rs:48:45: 48:56

This is the relevant diff, but ConstProp is correct here: _13.0 (v39.0 in the original source) is not aliased by anything, 6 can be propagated. Indeed the result with ConstProp is right and without is wrong, it actually mitigated a bug further down the pipeline

[cbeuw]

Slightly edited to make the executed control flow simpler: no loop is taken more than once except for 'l3, which executes one line v21 = v20; and then returns on the second iteration.

See

use std::ptr;
pub fn print_var(v: u8) {
    println!("{v}");
}
pub unsafe fn fn12_rs() -> ([u128; 7], *mut i8, *mut bool) {
    let mut v2: bool = false;
    let mut v8: u64 = 0;
    let mut v9: usize = 0;
    let mut v12: *mut u8 = ptr::null_mut();
    let mut v17: *mut bool = ptr::null_mut();
    let mut v20: [u8; 8] = Default::default();
    let mut v21: [u8; 8] = Default::default();
    let mut v31: (bool, u8, usize, f32) = Default::default();
    let mut v33: ([u128; 7], *mut i8, *mut bool) = ([0; 7], ptr::null_mut(), ptr::null_mut());
    let mut v39: (usize, [u128; 7], ([u32; 6], usize, *mut [u32; 6]), [u32; 2]) =
        (0, [0; 7], ([0; 6], 0, ptr::null_mut()), [0; 2]);
    let mut ret: ([u128; 7], *mut i8, *mut bool) = ([0; 7], ptr::null_mut(), ptr::null_mut());
    ret.2 = core::ptr::addr_of_mut!(v2);
    'l0: loop {
        v12 = core::ptr::addr_of_mut!(v20[v9]);
        v20 = [197_u8; 8];
        v9 = 2_usize;
        'l1: loop {
            match *v12 {
                197 => {
                    // Taken
                    v8 = 13978819448286864680_u64;
                    v33.2 = ret.2;
                    match v39.0 {
                        0 => {
                            // Taken
                            'l2: loop {
                                v20 = [11_u8; 8]; // What LLVM with low mir-opt prints
                                (*v12) = 22; // What Miri prints
                                'l3: loop {
                                    v21 = v20;
                                    match v8 {
                                        13978819448286864680 => {
                                            // Taken
                                            v39.2 .0 = [2262110980_u32; 6];
                                            v8 = 2;
                                            v39.0 = 6;
                                            v17 = v33.2;
                                            v33.2 = core::ptr::addr_of_mut!(v31.0);
                                            v31.1 = *v12;
                                            (*v17) = true;
                                            v20 = v21;
                                            match v39.0 {
                                                6 => {
                                                    // Taken
                                                    print_var(v31.1);
                                                    // Loop on 'l3, then since v8 == 2 we return
                                                }
                                                0 => continue 'l2,
                                                _ => return ret,
                                            }
                                        }
                                        2 => return ret,
                                        _ => continue 'l0,
                                    }
                                }
                            }
                        }
                        _ => return ret,
                    }
                }
                4 => {
                    v12 = core::ptr::addr_of_mut!(v20[v9]);
                }
                _ => return ret,
            }
        }
    }
}
pub fn main() {
    unsafe {
        fn12_rs();
    }
}

[saethlin]

I put this together to look through what LLVM is doing with and without ConstProp enabled: https://godbolt.org/z/4ohsGae5z

[matthiaskrgr]

Regression in nightly-2022-08-13
which was when we did the llvm 15 upgrade

found 8 bors merge commits in the specified range
  commit[0] 2022-08-11: Auto merge of #100416 - Dylan-DPC:rollup-m344lh1, r=Dylan-DPC
  commit[1] 2022-08-11: Auto merge of #100426 - matthiaskrgr:rollup-0ks4dou, r=matthiaskrgr
  commit[2] 2022-08-12: Auto merge of #100419 - flip1995:clippyup, r=Manishearth
  commit[3] 2022-08-12: Auto merge of #99464 - nikic:llvm-15, r=cuviper
  commit[4] 2022-08-12: Auto merge of #100435 - ehuss:update-cargo, r=ehuss
  commit[5] 2022-08-12: Auto merge of #99624 - vincenzopalazzo:macros/unix_error, r=Amanieu
  commit[6] 2022-08-12: Auto merge of #100328 - davidtwco:perf-implications, r=nnethercote
  commit[7] 2022-08-12: Auto merge of #100456 - Dylan-DPC:rollup-fn17z9f, r=Dylan-DPC
```

[apiraino]

WG-prioritization assigning priority (Zulip discussion). Provisionally assigning a P-high priority, will be discussed in the next compiler meeting.

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