Another mir-opt-level=2 miscompilation

[leonardo-m]

On the last Nightly:

rustc 1.42.0-nightly (c5840f9d2 2020-01-03)
binary: rustc
commit-hash: c5840f9d252c2f5cc16698dbf385a29c5de3ca07
commit-date: 2020-01-03
host: x86_64-pc-windows-gnu
release: 1.42.0-nightly
LLVM version: 9.0

rustc -Z mir-opt-level=1 test.rs   => OK
rustc -Z mir-opt-level=2 test.rs   => Error

fn e220() -> String {
    fn get_displacement(mut distance: i64, generation: i32) -> [i64; 4] {
        if generation == 0 {
            return match distance {
                0 => [0, 1, 0, 0],
                1 => [0, 1, 0, 1],
                _ => panic!("Travel past end")
            }
        }

        let half_len = 1i64 << (generation - 1);
        let second_half = distance > half_len;

        if second_half {
            distance = half_len + half_len - distance;
        }

        let mut ret = get_displacement(distance, generation - 1);
        let (ex, ey) = (ret[0], ret[1]);
        ret[0] = ex + ey;
        ret[1] = ey - ex;

        if second_half {
            let (px, py) = (ret[2], ret[3]);
            ret[2] = ex + ey - py;
            ret[3] = ey - ex + px;
        }

        ret
    }

    let res = get_displacement(1_000_000_000_000, 50);
    format!("{},{}", res[2], res[3])
}

fn main() {
    assert_eq!(e220(), "139776,963904");
}

[bjorn3]

Reduced to:

fn e220() -> (i64, i64) {
    #[inline(never)]
    fn get_displacement() -> [i64; 2] {
        [139776, 963904]
    }

    let res = get_displacement();
    match (&res[0], &res[1]) {
        (arg0, arg1) => (*arg0, *arg1),
    }
}

fn main() {
    assert_eq!(e220(), (139776, 963904));
}

[bjorn3]

Mir of e220 with -Zmir-opt-level=1:

fn  e220::get_displacement() -> [i64; 2] {
    let mut _0: [i64; 2];

    bb0: {
        _0 = [const 139776i64, const 963904i64];
        return;
    }
}

fn  e220() -> (i64, i64) {
    let mut _0: (i64, i64);
    let _1: [i64; 2];
    let mut _2: (&i64, &i64);
    let mut _3: &i64;
    let _4: usize;
    let mut _5: &i64;
    let _6: usize;
    let mut _9: i64;
    let mut _10: i64;
    scope 1 {
        debug res => _1;
        let _7: &i64;
        let _8: &i64;
        scope 2 {
            debug arg0 => _7;
            debug arg1 => _8;
        }
    }

    bb0: {
        StorageLive(_1);
        _1 = const e220::get_displacement() -> bb1;
    }

    bb1: {
        StorageLive(_2);
        StorageLive(_3);
        StorageLive(_4);
        _4 = const 0usize;
        _3 = &_1[_4];
        StorageLive(_5);
        StorageLive(_6);
        _6 = const 1usize;
        _5 = &_1[_6];
        (_2.0: &i64) = move _3;
        (_2.1: &i64) = move _5;
        StorageDead(_5);
        StorageDead(_3);
        StorageLive(_7);
        _7 = (_2.0: &i64);
        StorageLive(_8);
        _8 = (_2.1: &i64);
        StorageLive(_9);
        _9 = (*_7);
        StorageLive(_10);
        _10 = (*_8);
        (_0.0: i64) = move _9;
        (_0.1: i64) = move _10;
        StorageDead(_10);
        StorageDead(_9);
        StorageDead(_8);
        StorageDead(_7);
        StorageDead(_1);
        StorageDead(_6);
        StorageDead(_4);
        StorageDead(_2);
        return;
    }
}

Mir of e220 with -Zmir-opt-level=2:

fn  e220::get_displacement() -> [i64; 2] {
    let mut _0: [i64; 2];

    bb0: {
        _0 = [const 139776i64, const 963904i64];
        return;
    }
}

fn  e220() -> (i64, i64) {
    let mut _0: (i64, i64);
    let _1: [i64; 2];
    let mut _2: (&i64, &i64);
    let mut _3: &i64;
    let _4: usize;
    let mut _5: &i64;
    let _6: usize;
    let mut _9: i64;
    let mut _10: i64;
    scope 1 {
        debug res => _1;
        let _7: &i64;
        let _8: &i64;
        scope 2 {
            debug arg0 => _7;
            debug arg1 => _8;
        }
    }

    bb0: {
        StorageLive(_1);
        _1 = const e220::get_displacement() -> bb1;
    }

    bb1: {
        StorageLive(_2);
        StorageLive(_3);
        _4 = const 0usize;
        _3 = &_1[_4];
        StorageLive(_5);
        StorageLive(_6);
        _6 = const 1usize;
        _5 = &_1[_6];
        (_2.0: &i64) = const Scalar(AllocId(15).0x0) : &i64;
        (_2.1: &i64) = const Scalar(AllocId(15).0x8) : &i64;
        StorageDead(_5);
        StorageDead(_3);
        StorageLive(_7);
        _7 = (_2.0: &i64);
        StorageLive(_8);
        _8 = (_2.1: &i64);
        StorageLive(_9);
        _9 = (*_7);
        StorageLive(_10);
        _10 = (*_8);
        (_0.0: i64) = move _9;
        (_0.1: i64) = move _10;
        StorageDead(_10);
        StorageDead(_9);
        StorageDead(_8);
        StorageDead(_7);
        StorageDead(_1);
        StorageDead(_6);
        StorageDead(_2);
        return;
    }
}

StorageLive(_4); and StorageDead(_4); got removed while _4 is still assigned and used. Also the fields of _2 now get const Scalar(AllocId(15).0x0) and const Scalar(AllocId(15).0x8) assigned.

[Aaron1011]

The are a couple of things going on here:

The immediate cause is the fact that we don't try to propagate operands in TerminatorKind::Call. This means that _1 = const e220::get_displacement() -> bb1; never gets evaluated, leaving _1 uninitialized.

Normally, this would not be a problem - const-prop explicitly bails out when trying to access an uninitialized local, so failing to evaluate _1 = const e220::get_displacement() should just mean that we don't const-propagate anything that relies on _1.

Unfortunately, it's possible for an uninitialized local to be incorrectly marked as initialized. Inside force_allocation, we unconditionally mark a local as LocalValue::Live, even if it was previously uninitialied. When processing an Rvalue::Ref, we call force_allocation on the source, which will incorrectly mark an uninitialized source as initialized.

While implementing const-propagation for TeminatorKind::Call would fix this specific issue, the force_allocation issue means that we risk introducing undefined behavior into valid programs whenever const-propagation doesn't evaluate something that would initialize a local.

I see a few ways different of solving this:

• Change LocalValue::Uninitialized to LocalValue::Uninitialized(Option<MemPlace>). When force_allocation is called on an uninitialized local, we keep the local as a LocalValue::Uninitialized, but would store Some(mplace) in it. This would ensure that force_allocation has no user-visible effect - uninitialized locals will remain uninitialized until actually written to.
• Make force_allocation aware of whether not or not it is being used for 'reading' or 'writing'. When 'reading', we call access_local before overwriting a local with LocalValue::Live, allowing the machine to assert that it is valid. When 'writing', we skip calling access_local, allowing force_allocation to be used when initializing a previously uninitialized local (which does not require that the target local be initialized).

cc @RalfJung

[RalfJung]

Without having digested all the details yet, my first thought is: this is caused by const-prop trying to shoehorn the Miri engine (built for evaluation of whole programs) into an engine for partial evaluation.

The LocalValue::Uninitialized was never meant for tracking things like "unkown value", it is a hack introduced for handling unsized locals as I didn't find a better way to implement them. It's meaning is "a local whose size we don't know yet". force_allocation can determine the size, and thus complete allocation of the local.

uninitialized local

In terms of the Rust Abstract Machine (which the Miri engine models), I don't know what an "uninitialized local" is -- but a local that's marked Live but whose memory is entirely uninitialized should certainly qualify. Thus I would say that force_allocation correctly preserves the uninitialized nature of the local.

The issue is that const-prop is taking the difference between LocalValue::Uninitialized and LocalValue::Live, which is an implementation detail of the engine (but doesn't correspond to anything real, it's basically just an optimization), and tries to assign meaning to it. No wonder this went wrong.

What exactly is it that const-prop needs?

[RalfJung]

Cc @oli-obk @wesleywiser

[oli-obk]

What exactly is it that const-prop needs?

Zero cost uninitialized locals is the base feature we need. Essentially if we decide we don't need a local, reading its memory should yield an uninit value and its memory should not require any heap allocations.

I get the shoehorning, we so are doing this a lot in const prop, mainly to keep the engine modifications minimal. I guess we could add some more machine hooks to get rid of hacks.

[RalfJung]

if we decide we don't need a local, reading its memory should yield an uninit value and its memory should not require any heap allocations.

Even with force_allocation, reading it will yield an uninit value. So not requiring heap allocations is a correctness condition? That's what @Aaron1011's analysis says, basically.

[oli-obk]

Well... it shouldn't be. The ::Live check is actually just a check ensuring we don't ICE for unsized values.

When processing an Rvalue::Ref, we call force_allocation on the source, which will incorrectly mark an uninitialized source as initialized.

This is not worded correctly. The uninitialized local is marked as live its memory is still uninitialized. But that doesn't change the fact that the analysis is spot on. We take references to locals that may never get a value propagated into.

The early bail out in

rust/src/librustc_mir/transform/const_prop.rs

Line 222 in 87540bd

throw_unsup!(ConstPropUnsupported("tried to access an uninitialized local"));

is just so we don't hit the panic in https://doc.rust-lang.org/nightly/nightly-rustc/src/rustc_mir/interpret/eval_context.rs.html#143 it's also not for correctness.

the force_allocation issue means that we risk introducing undefined behavior into valid programs whenever const-propagation doesn't evaluate something that would initialize a local.

Yea, so basically whenever we don't fully propagate into a local, but later take a reference to that local, we end up with a const pointer to an uninitialized const allocation.

Basically unless the local's memory is valid (as per the validation rules for statics), we should not permit taking references to it.

[Aaron1011]

Yea, so basically whenever we don't fully propagate into a local, but later take a reference to that local, we end up with a const pointer to an uninitialized const allocation.

Doesn't this also affect normal uses of an un-propagated local? We'll end up copying data from an uninitialized allocation, which will result in the same issue.

[oli-obk]

Doesn't this also affect normal uses of an un-propagated local? We'll end up copying data from an uninitialized allocation, which will result in the same issue.

Yes, any local that we don't fully propagate into but that is referred to by a local that we marked as "could be propagated".

[RalfJung]

Basically unless the local's memory is valid (as per the validation rules for statics), we should not permit taking references to it.

I'd say it's less about validity and more about whether we actually did all the computation for this local. That's not the same thing.

Basically, const-prop needs a state representing "unknown". This is distinct from "(known to be) uninitialized". And that's not surprising at all, static analyses and optimizations almost always have such a state. This is a first step towards supporting abstract interpretation in Miri.

[oli-obk]

We inverted this by treating any initialized values as "!unknown". The issue here is that taking a reference to a value works even if the value is not fully initialized. We have no concept of fully initialized, and in case the local is of union type, we can't rely on the uninitialized state to signal "maybe unknown".

So yea, the validity check won't work here either. @wesleywiser and I talked about using dataflow for const prop, so we'd mark locals only as known when they have been successfully propagated into instead of relying on the initialization state. Until we do this we should probably just turn off propagating reference taking.

[wesleywiser]

I agree disabling ref propagation makes sense. We have quite a few bugs that I believe would be resolved by that. In addition, I believe there's only 1 or 2 MIR tests that would be affected.

Going forward, perhaps we should try to find some way to get more coverage of mir-opt=2?

[RalfJung]

We inverted this by treating any initialized values as "!unknown". The issue here is that taking a reference to a value works even if the value is not fully initialized.

The other problem is (as you hinted at) that things, at least in theory, might be "partially known", such as in

_5.0 = 15u32;
_5.1 = _1;

where _5 is, say, a pair: now the first field is known but the second is not.

[RalfJung]

A general worry about this is how our const-prop looks not at all like the usual "compiler construction literature const-prop": the usual thing is to do a fixed-point (static) analysis on a domain including all possible values as well as "unknown". That could also handle loops, which I suppose you currently have to carefully avoid. It is certainly possible to implement constant propagation differently, but that means none of the standard intuition about it applies.