VecDeque is_empty and get(0) together generate unreachable panic.

[bugadani]

https://rust.godbolt.org/z/oe4q69

For some reason, the knowledge that a VecDeque is empty, is not preserved when calling get(0) (or even front) and the compiler generates panics which are unreachable.

[camelid]

Does the compiler have any support for that kind of optimization? I don't think it has special knowledge of VecDeque's methods.

[camelid]

This is the generated MIR (in release mode) by the way:

// WARNING: This output format is intended for human consumers only
// and is subject to change without notice. Knock yourself out.
fn front(_1: &mut VecDeque<usize>) -> () {
    debug v => _1;                       // in scope 0 at src/lib.rs:3:14: 3:15
    let mut _0: ();                      // return place in scope 0 at src/lib.rs:3:39: 3:39
    let mut _2: bool;                    // in scope 0 at src/lib.rs:4:8: 4:21
    let mut _3: bool;                    // in scope 0 at src/lib.rs:4:9: 4:21
    let mut _4: &std::collections::VecDeque<usize>; // in scope 0 at src/lib.rs:4:9: 4:10
    let _5: &usize;                      // in scope 0 at src/lib.rs:5:9: 5:31
    let mut _6: std::option::Option<&usize>; // in scope 0 at src/lib.rs:5:9: 5:17
    let mut _7: &std::collections::VecDeque<usize>; // in scope 0 at src/lib.rs:5:9: 5:10
    let mut _8: &str;                    // in scope 0 at src/lib.rs:5:25: 5:30
    let _9: &str;                        // in scope 0 at src/lib.rs:5:25: 5:30

    bb0: {
        StorageLive(_2);                 // scope 0 at src/lib.rs:4:8: 4:21
        StorageLive(_3);                 // scope 0 at src/lib.rs:4:9: 4:21
        StorageLive(_4);                 // scope 0 at src/lib.rs:4:9: 4:10
        _4 = &(*_1);                     // scope 0 at src/lib.rs:4:9: 4:10
        _3 = VecDeque::<usize>::is_empty(move _4) -> bb1; // scope 0 at src/lib.rs:4:9: 4:21
                                         // mir::Constant
                                         // + span: src/lib.rs:4:11: 4:19
                                         // + literal: Const { ty: for<'r> fn(&'r std::collections::VecDeque<usize>) -> bool {std::collections::VecDeque::<usize>::is_empty}, val: Value(Scalar(<ZST>)) }
    }

    bb1: {
        StorageDead(_4);                 // scope 0 at src/lib.rs:4:20: 4:21
        _2 = Not(move _3);               // scope 0 at src/lib.rs:4:8: 4:21
        StorageDead(_3);                 // scope 0 at src/lib.rs:4:20: 4:21
        switchInt(_2) -> [false: bb2, otherwise: bb3]; // scope 0 at src/lib.rs:4:5: 6:6
    }

    bb2: {
        _0 = const ();                   // scope 0 at src/lib.rs:4:5: 6:6
        goto -> bb6;                     // scope 0 at src/lib.rs:4:5: 6:6
    }

    bb3: {
        StorageLive(_5);                 // scope 0 at src/lib.rs:5:9: 5:31
        StorageLive(_6);                 // scope 0 at src/lib.rs:5:9: 5:17
        StorageLive(_7);                 // scope 0 at src/lib.rs:5:9: 5:10
        _7 = &(*_1);                     // scope 0 at src/lib.rs:5:9: 5:10
        _6 = VecDeque::<usize>::get(move _7, const 0_usize) -> bb4; // scope 0 at src/lib.rs:5:9: 5:17
                                         // mir::Constant
                                         // + span: src/lib.rs:5:11: 5:14
                                         // + literal: Const { ty: for<'r> fn(&'r std::collections::VecDeque<usize>, usize) -> std::option::Option<&'r usize> {std::collections::VecDeque::<usize>::get}, val: Value(Scalar(<ZST>)) }
    }

    bb4: {
        StorageDead(_7);                 // scope 0 at src/lib.rs:5:16: 5:17
        StorageLive(_8);                 // scope 0 at src/lib.rs:5:25: 5:30
        StorageLive(_9);                 // scope 0 at src/lib.rs:5:25: 5:30
        _9 = const "foo";                // scope 0 at src/lib.rs:5:25: 5:30
                                         // ty::Const
                                         // + ty: &str
                                         // + val: Value(Slice { data: Allocation { bytes: [102, 111, 111], relocations: Relocations(SortedMap { data: [] }), init_mask: InitMask { blocks: [7], len: Size { raw: 3 } }, size: Size { raw: 3 }, align: Align { pow2: 0 }, mutability: Not, extra: () }, start: 0, end: 3 })
                                         // mir::Constant
                                         // + span: src/lib.rs:5:25: 5:30
                                         // + literal: Const { ty: &str, val: Value(Slice { data: Allocation { bytes: [102, 111, 111], relocations: Relocations(SortedMap { data: [] }), init_mask: InitMask { blocks: [7], len: Size { raw: 3 } }, size: Size { raw: 3 }, align: Align { pow2: 0 }, mutability: Not, extra: () }, start: 0, end: 3 }) }
        _8 = _9;                         // scope 0 at src/lib.rs:5:25: 5:30
        _5 = Option::<&usize>::expect(move _6, move _8) -> bb5; // scope 0 at src/lib.rs:5:9: 5:31
                                         // mir::Constant
                                         // + span: src/lib.rs:5:18: 5:24
                                         // + literal: Const { ty: for<'r> fn(std::option::Option<&usize>, &'r str) -> &usize {std::option::Option::<&usize>::expect}, val: Value(Scalar(<ZST>)) }
    }

    bb5: {
        StorageDead(_8);                 // scope 0 at src/lib.rs:5:30: 5:31
        StorageDead(_6);                 // scope 0 at src/lib.rs:5:30: 5:31
        StorageDead(_9);                 // scope 0 at src/lib.rs:5:31: 5:32
        StorageDead(_5);                 // scope 0 at src/lib.rs:5:31: 5:32
        _0 = const ();                   // scope 0 at src/lib.rs:4:22: 6:6
        goto -> bb6;                     // scope 0 at src/lib.rs:4:5: 6:6
    }

    bb6: {
        StorageDead(_2);                 // scope 0 at src/lib.rs:7:1: 7:2
        return;                          // scope 0 at src/lib.rs:7:2: 7:2
    }
}

[bugadani]

I don't think special knowledge is necessary. There are some assumptions that are missing, which make the if idx < self.len() check in VecDeque::get() something LLVM can't optimize.

Also, the MIR isn't particularly helpful here as calls aren't inlined, so we just see _6 = VecDeque::<usize>::get(move _7, const 0_usize) -> bb4; in place of the interesting bits :)

[bugadani]

The main problem looks something like this:

if head != tail { // is_empty()
    if idx < head.wrapping_sub(tail) & size { // idx < count()
        return Some();
    } else {
        return None;
    }
}

For whatever reason, even if the compiler knows size > 1 (I added an assume call to test), the compiler can't deduce count() > 0 and so get(0) isn't optimized properly.

The main issue seems to be that the binary and loses information. See here: https://rust.godbolt.org/z/77MaGW - if you delete the & 2, most of the generated code goes away. I can't be sure but I believe some other issues related to this may have already been solved in LLVM so the future update to LLVM 12 may close this issue.

[camelid]

I can't be sure but I believe some other issues related to this may have already been solved in LLVM so the future update to LLVM 12 may close this issue.

That would be nice! :D

[nagisa]

There are two issues here. First is convoluted implementation of VecDeque itself where implementations of len and is_empty are distinct enough that len will check for more things than is_empty, and therefore vec_deque.is_empty() not being equivalent to vec_deque.len() == 0… to LLVM at least, which hasn't the domain specific knowledge to tell that some computation involving head, tail and capacity is equivalent to head == tail.

---

But even if is_empty() is replaced with len() == 0 in the reproducer, another issue remains in that we somehow lose information about Unique<u64> being !nonnull. This then causes code like this:

    Some(&*buf.ptr.as_ptr()).unwrap()

to actually check for buf.ptr == null and panic if it is indeed a null. This happens because of niche optimisation in this case. Not sure how actionable the former is, but it seems like it would be good to fix latter. At very least it seems like we could attach !range metadata to all reference values to tell they aren't null?

[camelid]

I can't be sure but I believe some other issues related to this may have already been solved in LLVM so the future update to LLVM 12 may close this issue.

Doesn't seem like the LLVM update fixed it because the unreachable panic is still present on nightly.

[the8472]

https://rust.godbolt.org/z/oe4q69

Switched to nightly and it now returns:

example::front:
ret

So it seems fixed. Please reopen or file a new issue if there's still an issue.

[ChrisDenton]

Does this need a test to guard against regression?

[the8472]

I don't think VecDeque is hot enough to require a regression test for an optimization. Different story if this were Vec.
But if someone wants to write one it doesn't hurt either.

[ChrisDenton]

Marking this as E-medium. It should not be too hard but you will need to know (or learn!) about codegen tests.

[a-lafrance]

@rustbot claim

Claiming this now that I've put up #116047 to add the codegen test to guard against regression :)

Edit: This can probably be closed now that the PR is merged