Heisen-misoptimisation on x86_64

[cbeuw]

Fuzzer generated code, minimised and rewritten into surface Rust. Miri reports no UB under either aliasing models. The only unsafe here are for mutating the static mut hasher and a pointer write on a not-taken branch (the pointer happens to be dangling, so it would've been UB had the branch been taken).

#![feature(const_hash)]
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
use std::ptr;
static mut H: DefaultHasher = DefaultHasher::new();

fn dump_var<T: Hash, U: Hash, V: Hash, W: Hash>(val0: T, val1: U, val2: V, val3: W) {
    unsafe {
        val0.hash(&mut H);
        val1.hash(&mut H);
        val2.hash(&mut H);
        val3.hash(&mut H);
    }
}
pub fn fn0(mut _2: [isize; 7], mut _3: usize, mut _4: i32, mut _5: u64) -> [isize; 2] {
    let mut _13: ([bool; 1],) = ([false; 1],);
    let mut _14: [isize; 6] = [0; 6];
    let mut _29: [isize; 6] = [0; 6];
    let ret: [isize; 2] = [13; 2];
    let _6 = fn1(_2);
    fn5(ret, _2, _3, _2, _2, _4, _6);
    dump_var(_4, _5, 0, 0);
    dump_var([-112; 6], _13.0, 0, (4, 10));
    _14 = [(-9223372036854775808_isize); 6];
    dump_var((), (), _29, _14);
    return ret;
}

pub fn fn1(mut _10: [isize; 7]) -> *mut isize {
    let arr = [0; 3];
    let mut _21: (u8, u128, [u64; 3], isize, i16) = (0, 0, arr, 0, 0);
    let mut _24: (u8, u128, [u64; 3], isize, i16) = (0, 0, arr, 0, 0);
    dump_var(_10, _10, 0, 0);
    unsafe {
        _24.hash(&mut H);
        _21.hash(&mut H);
    }
    return core::ptr::addr_of_mut!(_21.3);
}
fn fn5(
    mut _2: [isize; 2],
    mut _6: [isize; 7],
    mut _7: usize,
    mut _9: [isize; 7],
    mut _10: [isize; 7],
    mut _12: i32,
    mut _16: *mut isize,
) {
    let mut _23: (
        *const usize,
        (usize, u8),
        (char, i32, (i64,), u64),
        char,
        (
            (f64, i64, i8),
            [f32; 1],
            (usize, u8),
            i8,
            (isize, i64),
            [f32; 1],
        ),
        *const u8,
    ) = (
        ptr::null(),
        (0, 0),
        ('a', 0, (0,), 0),
        'a',
        ((0., 0, 0), [0.; 1], (0, 0), 0, (0, 0), [0.; 1]),
        ptr::null(),
    );
    let mut _27: ((f64, i64, i8),) = Default::default();
    loop {
        _9 = _6;
        let mut _20 = (-9223372036854775808_isize) as i128;
        let mut _21 = (0,);
        loop {
            _23.0 = core::ptr::addr_of!(_23.1 .0);
            _23.4 .0 = (f64::NAN, (-1102345069964335552_i64), 9_i8);
            dump_var(0, 0, _6, _27.0 .1);
            _27.0 = _23.4 .0;
            match _27.0 .2 {
                9 => {
                    dump_var(_9, _21, _20, _12);
                    dump_var(_2, _10, _6, _7);
                    return;
                }
                1 => break,
                _ => unsafe {
                    (*_16) = 88_isize;
                },
            }
        }
    }
}
pub fn main() {
    println!(
        "{:?}",
        fn0(
            [(-56_isize); 7],
            15609822513776909592_usize,
            -652623562_i32,
            18399139786288871729_u64
        )
    );
    unsafe {
        println!("hash: {}", H.finish());
    }
}

The correct hash should be 12326103344558250442, which Miri agrees

$ rustc -Zmir-opt-level=3 -Copt-level=1 repro.rs && ./repro
[13, 13]
hash: 12326103344558250442

With -Zmir-opt-level>=3 and -Copt-level>=2, it prints something different

$ rustc -Zmir-opt-level=3 -Copt-level=2 repro.rs && ./repro
[13, 13]
hash: 5661618040229725087

I'm fairly certain that the bug is in LLVM, because in this alternative version where fn5 is written in custom MIR, the miscompilation can be triggered with -Zmir-opt-level=0

$ rustc -Zmir-opt-level=0 -Copt-level=1 repro-alt.rs && ./repro-alt
[13, 13]
hash: 17317577282543711276 # right
$ rustc -Zmir-opt-level=0 -Copt-level=2 repro-alt.rs && ./repro-alt
[13, 13]
hash: 469181360651188025 # wrong

repro-alt.rs

#![feature(const_hash)]
#![feature(custom_mir, core_intrinsics)]
extern crate core;
use core::intrinsics::mir::*;
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
static mut H: DefaultHasher = DefaultHasher::new();
fn dump_var<T: Hash, U: Hash, V: Hash, W: Hash>(val0: T, val1: U, val2: V, val3: W) {
    unsafe {
        val0.hash(&mut H);
        val1.hash(&mut H);
        val2.hash(&mut H);
        val3.hash(&mut H);
    }
}
pub fn fn0(mut _2: [isize; 7], mut _3: usize, mut _4: i32, mut _5: u64) -> [isize; 2] {
    let mut _13: ([bool; 1],) = ([false; 1],);
    let mut _14: [isize; 6] = [0; 6];
    let mut _29: [isize; 6] = [0; 6];
    let ret: [isize; 2] = [13; 2];
    let _6 = fn1(_2);
    fn5(ret, _2, _3, _2, _2, _4, _6);
    dump_var(_4, _5, 0, 0);
    dump_var([-112; 6], _13.0, 0, (4, 10));
    _14 = [(-9223372036854775808_isize); 6];
    _29 = [9223372036854775807_isize; 6];
    dump_var((), (), _29, _14);
    return ret;
}
pub fn fn1(mut _10: [isize; 7]) -> *mut isize {
    let arr = [0; 3];
    let mut _21: (u8, u128, [u64; 3], isize, i16) = (0, 0, arr, 0, 0);
    let mut _24: (u8, u128, [u64; 3], isize, i16) = (0, 0, arr, 0, 0);
    dump_var(_10, _10, 0, 0);
    unsafe {
        _24.hash(&mut H);
        _21.hash(&mut H);
    }
    return core::ptr::addr_of_mut!(_21.3);
}
#[custom_mir(dialect = "runtime", phase = "initial")]
fn fn5(
    mut _2: [isize; 2],
    mut _6: [isize; 7],
    mut _7: usize,
    mut _9: [isize; 7],
    mut _10: [isize; 7],
    mut _12: i32,
    mut _16: *mut isize,
) {
    mir! {
    let _20: i128;
    let _21: (i64,);
    let _23: (*const usize, (usize, u8), (char, i32, (i64,), u64), char, ((f64, i64, i8), [f32; 1], (usize, u8), i8, (isize, i64), [f32; 1]), *const u8);
    let _27: ((f64, i64, i8), [f32; 1], (usize, u8), i8, (isize, i64), [f32; 1]);
    let _36: ();
    {
    Goto(bb7)
    }
    bb7 = {
    _9 = _6;
    _20 = (-9223372036854775808_isize) as i128;
    _21 = (0,);
    Goto(bb9)
    }
    bb9 = {
    _23.0 = core::ptr::addr_of!(_23.1.0);
    _23.4.0 = (f64::NAN, (-1102345069964335552_i64), 9_i8);
    _27.0.1 = _7 as i64;
    Call(_36, bb11, dump_var(0,0, _6, _27.0.1))
    }
    bb11 = {
    _27.0 = _23.4.0;
    match _27.0.2 {
    1 => bb7,
    9 => bb17,
    _ => bb15
    }
    }
    bb15 = {
    (*_16) = 88_isize;
    Goto(bb9)
    }
    bb17 = {
    Call(_36, bb18, dump_var(Move(_9), Move(_21), Move(_20), Move(_12)))
    }
    bb18 = {
    Call(_36, bb19, dump_var(Move(_2), Move(_10), Move(_6), Move(_7)))
    }
    bb19 = {
    Return()
    }
    }
}
pub fn main() {
    println!(
        "{:?}",
        fn0(
            std::hint::black_box([(-56_isize); 7]),
            std::hint::black_box(15609822513776909592_usize),
            std::hint::black_box(-652623562_i32),
            std::hint::black_box(18399139786288871729_u64)
        )
    );
    unsafe {
        println!("hash: {}", H.finish());
    }
}

Unfortunately this is a Heisenbug: if you replace dump_var to something that debug-prints its arguments, the misoptimisation goes away, so I don't know which variable got the wrong value

Recent LLVM miscompilation fixes (llvm/llvm-project@e506bfa and llvm/llvm-project@97f0e7b) do not fix this.

I can only reproduce this on x86_64 Linux, not Apple Silicon

cc @nikic

[cbeuw]

Likely an LTO bug:

$ rustc -Zmir-opt-level=3 -Copt-level=2 repro.rs && ./repro
[13, 13]
hash: 5661618040229725087 # wrong
$ rustc -Zmir-opt-level=3 -Copt-level=2 -Clto=no repro.rs && ./repro
[13, 13]
hash: 12326103344558250442 # right

[cbeuw]

Here's another reproduction of (likely) the same bug. It's more fun as you get a different result on each run!

$ rustc -Zmir-opt-level=0 -Copt-level=3 repro2.rs
$ ./repro2
hash: 14905355177934920681
$ ./repro2
hash: 13629682358592290610
$ ./repro2
hash: 13245799623560635658
$ ./repro2
hash: 15182593564984594047
$ ./repro2
hash: 3483992431494662826
$ ./repro2
hash: 4159847884629394433
$ ./repro2
hash: 8572745853356908632
$ ./repro2
hash: 13937078852316743297

repro2.rs

#![feature(custom_mir, core_intrinsics, const_hash)]
extern crate core;
use core::intrinsics::mir::*;
use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};
static mut H: DefaultHasher = DefaultHasher::new();
#[inline(always)]
fn dump_var<V: Hash, W: Hash>(val2: V, val3: W) {
    unsafe {
        val2.hash(&mut H);
        val3.hash(&mut H);
    }
}


#[custom_mir(dialect = "runtime", phase = "initial")]
pub fn fn4(mut _2: f64) {
    mir! {
    let _6: *mut f64;
    let _9: [f32; 3];
    let _25: ();
                {
    _6 = core::ptr::addr_of_mut!(_2);
    _9 = [(-0.000000000000000000000000000000000000009221304800323425_f32); 3];
    Call(_25, bb3, fn5(_6, _9))
                }
                bb3 = {
    Call(_25, bb9, dump_var(0, 0))
                }
                bb9 = {
    Return()
                }
                }
}


#[custom_mir(dialect = "runtime", phase = "initial")]
pub fn fn5(mut _1: *mut f64, mut _2: [f32; 3]) {
    mir! {
    let _3: [f32; 3];
    let _4: [i32; 4];
    let _9: *mut f64;
    let _11: *mut f64;
    let _16: ([u16; 1], (i8, *mut f64, (bool,), [i16; 2], *const *const u128), [f32; 3], *mut i8);
    let _17: [u64; 7];
    let _21: f64;
    let _26: [u64; 7];
    let _29: i16;
    let _39: ();
    let _40: ();
                {
    Call(_3, bb1, fn6(_1, _2, _2, _2))
                }
                bb1 = {
    _2 = [0_f32; 3];
    _4 = [(-1483160251_i32); 4];
    _2 = [0.0000000000000000000000000000000000000020787534043057212_f32; 3];
    _4 = [1973982264_i32; 4];
    _9 = core::ptr::addr_of_mut!((*_1));
    _16.1.2.0 = false;
    _16.0 = [9294_u16; 1];
    _16.1.1 = core::ptr::addr_of_mut!((*_9));
    _17 = [5001048735949462793_u64; 7];
    _16.3 = core::ptr::addr_of_mut!(_16.1.0);
    _11 = core::ptr::addr_of_mut!((*_9));
    _21 = (*_11) * (*_11);
    Call(*_1, bb10, core::intrinsics::fmaf64(_21, _21, _21))
                }
                bb10 = {
    _29 = -(-19748_i16);
    _26 = _17;
    Goto(bb17)
                }
                bb17 = {
    Call(_39, bb18, dump_var(Move(_4), Move(_26)))
                }
                bb18 = {
    Call(_39, bb19, dump_var(Move(_29), _40))
                }
                bb19 = {
    Return()
                }
                }
}
#[custom_mir(dialect = "runtime", phase = "initial")]
pub fn fn6(mut _2: *mut f64, mut _4: [f32; 3], mut _5: [f32; 3], mut _6: [f32; 3]) -> [f32; 3] {
    mir! {
    let _10: u32;
    let _11: [i16; 2];
    let _12: *mut isize;
    let _13: [i16; 7];
    let _15: [isize; 4];
    let _16: bool;
    let _23: ([i32; 4],);
    let _31: isize;
    let _37: i32;
    let _38: [i64; 5];
    let _43: ();
                {
    _11 = [(-18485_i16); 2];
    _15 = [9223372036854775807_isize; 4];
    _16 = false;
    _10 = !1230305785_u32;
    Call(_12, bb4, fn7(_15,  _2))
                }
                bb4 = {
    Call(_4, bb5, fn11( _12,  _2,_10, _16))
                }
                bb5 = {
    _4 = [0_f32; 3];
    RET = [(-0.000000000000000000000000000000000000003748211349256057_f32); 3];
    _4 = [0.0000000000000000000000000000000000000010648046640864987_f32; 3];
    _5 = [f32::INFINITY; 3];
    _6 = [(-0.0000000000000000000000000000000000000013810286820383586_f32); 3];
    _13 = [(-29169_i16); 7];
    _23.0 = [(-1918054914_i32); 4];
    _23.0 = [(-1642913830_i32); 4];
    _12 = core::ptr::addr_of_mut!(_31);
    _6 = [f32::INFINITY; 3];
    (*_12) = 126_isize;
    _38 = [(-8631804439889020709_i64); 5];
    _38 = [5202988555816050374_i64; 5];
    _37 = -651249272_i32;
    _13 = [(-24577_i16); 7];
    Goto(bb18)
                }
                bb18 = {
    Call(_43, bb19, dump_var(Move(_13), Move(_31)))
                }
                bb19 = {
    Call(_43, bb20, dump_var(Move(_23), Move(_38)))
                }
                bb20 = {
    Call(_43, bb21, dump_var(Move(_11), Move(_37)))
                }
                bb21 = {
    Return()
                }
                }
}

#[custom_mir(dialect = "runtime", phase = "initial")]
pub fn fn7(mut _2: [isize; 4], mut _8: *mut f64) -> *mut isize {
    mir! {
    let _20: usize;
    let _45: isize;
    let unit: ();
                {
    _20 = (-3309986483480899206_i64) as usize;
    Call(unit, bb7, fn8(_2,  _20))
                }
                bb7 = {
    RET = core::ptr::addr_of_mut!(_45);
    Return()
                }
                }
}
#[custom_mir(dialect = "runtime", phase = "initial")]
pub fn fn8(mut _1: [isize; 4], mut _4: usize) {
    mir! {
    let _10: usize;
    let _12: ([f32; 3], u64, *const u128);
    let _13: [u16; 1];
    let _15: [i16; 7];
    let _16: (f64, i16, usize);
    let _17: *mut [i16; 7];
    let _18: *const *const u128;
    let _22: ([u16; 1], (i8, *mut f64, (bool,), [i16; 2], *const *const u128), [f32; 3], *mut i8);
    let _32: ();
                {
    _10 = _4;
    _13 = [37642_u16; 1];
    _18 = core::ptr::addr_of!(_12.2);
    _17 = core::ptr::addr_of_mut!(_15);
    (*_17) = [(-1781_i16); 7];
    _22.1.1 = core::ptr::addr_of_mut!(_16.0);
    _22.3 = core::ptr::addr_of_mut!(_22.1.0);
    _22.1.4 = core::ptr::addr_of!((*_18));
    Call(_32, bb16, dump_var(Move(_13), Move(_1)))
                }
                bb16 = {
    Call(_32, bb17, dump_var( Move(_10), Move(_15)))
                }
                bb17 = {
    Return()
                }
                }
}
#[custom_mir(dialect = "runtime", phase = "initial")]
pub fn fn11(mut _4: *mut isize, mut _7: *mut f64, mut _12: u32, mut _13: bool) -> [f32; 3] {
    mir! {
    let _16: [i16; 7];
    let _19: [isize; 4];
    let _26: ([u16; 1], (i8, *mut f64, (bool,), [i16; 2], *const *const u128), [f32; 3], *mut i8);
    let _31: [u16; 1];
    let _50: ();
                {
    _19 = [9223372036854775807_isize; 4];
    Call(_50, bb1, fn12(_12, _19, _13,  _4,  *_7))
                }
                bb1 = {
    RET = [f32::NAN; 3];
    _19 = [(-9223372036854775808_isize); 4];
    _16 = [(-20005_i16); 7];
    _26.3 = core::ptr::addr_of_mut!(_26.1.0);
    _31 = [62780_u16; 1];
    Goto(bb13)
                }
                bb13 = {
    Call(_50, bb16, dump_var(Move(_12), Move(_19)))
                }
                bb16 = {
    Call(_50, bb17, dump_var(Move(_31), Move(_16)))
                }
                bb17 = {
    Return()
                }
                }
}
#[custom_mir(dialect = "runtime", phase = "initial")]
fn fn12(mut _2: u32, mut _3: [isize; 4], mut _4: bool, mut _10: *mut isize, mut _13: f64) {
    mir! {
    let unit:();
                {
    Call(unit, bb8, fn13( _2,  _10, _3,  _3))
                }
                bb8 = {
    Return()
                }
                }
}
#[custom_mir(dialect = "runtime", phase = "initial")]
pub fn fn13(mut _2: u32, mut _10: *mut isize, mut _11: [isize; 4], mut _13: [isize; 4]) {
    mir! {
    let _15: [i64; 8];
    let _40: ();
                {
    _15 = [4118273133457677146_i64; 8];
    Call(_40, bb1, fn14(_13, _13, _10, _2, _13, _11))
                }
                bb1 = {
    Call(_40, bb16, dump_var(Move(_15), Move(_13)))
                }
                bb16 = {
    Return()
                }
                }
}


#[custom_mir(dialect = "runtime", phase = "initial")]
pub fn fn14(
    mut _1: [isize; 4],
    mut _2: [isize; 4],
    mut _3: *mut isize,
    mut _4: u32,
    mut _5: [isize; 4],
    mut _7: [isize; 4],
) {
    mir! {
    let _6: *mut isize;
    let _8: isize;
    let _10: (f64, i16, usize);
    let _11: [i64; 4];
    let _12: *mut f64;
    let _14: u8;
    let _16: ((i8, *mut f64, (bool,), [i16; 2], *const *const u128), [f32; 3], *mut i8);
    let _19: char;
    let _22: isize;
    let _44: ();
                {
    _6 = core::ptr::addr_of_mut!(_8);
    Goto(bb1)
                }
                bb1 = {
    (*_6) = -56_isize;
    _12 = core::ptr::addr_of_mut!(_10.0);
    _11 = [4486183091144317299_i64; 4];
    _14 = 235_u8 & 166_u8;
    _16.0.1 = _12;
    _16.2 = core::ptr::addr_of_mut!(_16.0.0);
    _6 = _3;
    _10 = ((-0.), 15670_i16, 7382361910770452361_usize);
    Goto(bb5)
                }
                bb5 = {
    _19 = '\u{4eea4}';
    _22 = 100356123358884611103422675654027290509_u128 as isize;
    Call(_2, bb6, fn16( _8))
                }
                bb6 = {
                match _10.1 {
    0 => bb1,
    5 => bb8,
    15670 => bb10,
    _ => bb18
                }
                }
                bb8 = {
    (*_6) = 72_isize;
    Goto(bb5)
                }
                bb10 = {
    Call(_44, bb11, fn18(_7, _1,  _16.2, _14, _2 ))
                }
                bb11 = {
    Call(_44, bb16, dump_var(Move(_19), Move(_22)))
                }
                bb16 = {
    Call(_44, bb17, dump_var(Move(_1), Move(_8)))
                }
                bb17 = {
    Call(_44, bb18, dump_var(Move(_4), Move(_11)))
                }
                bb18 = {
    Return()
                }
                }
}

#[custom_mir(dialect = "runtime", phase = "initial")]
pub fn fn16(mut _6: isize) -> [isize; 4] {
    mir! {
    let _16: isize;
    let _17: [i32; 4];
    let _18: [i16; 2];
    let _36: u64;
    let _45: ();
            {
    _18 = [(-27262_i16); 2];
    _16 = -_6;
    _17 = [(-360909236_i32); 4];
    _36 = 6056721437219179684_u64;
    Call(_45, bb20, dump_var(Move(_17), Move(_18)))
            }
            bb20 = {
    Call(_45, bb21, dump_var(Move(_16), Move(_36)))
            }
            bb21 = {
    RET = [(-9223372036854775808_isize); 4];
    Return()
            }
            }
}

#[custom_mir(dialect = "runtime", phase = "initial")]
pub fn fn18(
    mut _1: [isize; 4],
    mut _5: [isize; 4],
    mut _13: *mut i8,
    mut _14: u8,
    mut _15: [isize; 4],
) {
    mir! {
    let _19: [i64; 4];
    let _22: *mut i8;
    let _39: ();
            {
    _19 = [(-5833719222891370151_i64); 4];
    _22 = _13;
    Call(_39, bb17, dump_var(0, Move(_5)))
            }
            bb17 = {
    Call(_39, bb18, dump_var(Move(_1), Move(_15)))
            }
            bb18 = {
    Call(_39, bb19, dump_var(Move(_19), 0))
            }
            bb19 = {
    Return()
            }
            }
}
pub fn main() {
    fn4(0.);
    unsafe {
        println!("hash: {}", H.finish());
    }
}

[apiraino]

WG-prioritization assigning priority (Zulip discussion).

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

[nikic]

This is due to llvm/llvm-project#51838. Works with -Cllvm-args=-protect-from-escaped-allocas=true. It's a known issue that we don't have a good answer for, or even a consensus on what the underlying IR semantics are.

I'm downgrading this to P-medium because this can only happen in fuzzer-generated code.

[cbeuw]

My reading of the discussion in llvm/llvm-project#51838 is that a load from a dead stack object may happen after optimisations. The load itself can be "fine", but the loaded value should not be used and influence the program behaviour, which is what's happening here. Is there perhaps a subsequent bug that caused the poisoned load to pollute others?

[nikic]

The problematic part is the store to the dead stack object, not the load.

[RalfJung]

this can only happen in fuzzer-generated code.

"can only happen" seems very strong -- it's totally possible for this to happen in real code, isn't it? We just haven't observed it?