Missed optimization opportunity when Vec::push follows Vec::pop

[krtab]

The following code

pub fn noop(v: &mut Vec<u8>) {
    if let Some(x) = v.pop() {
        v.push(x)
    }
}

should be optimized to a no-op afaict, but instead gives:

example::noop:
        push    rbp
        push    rbx
        push    rax
        mov     rcx, qword ptr [rdi + 16]
        test    rcx, rcx
        je      .LBB2_4
        mov     rbx, rdi
        lea     rsi, [rcx - 1]
        mov     qword ptr [rdi + 16], rsi
        mov     rax, qword ptr [rdi]
        movzx   ebp, byte ptr [rax + rcx - 1]
        cmp     rsi, qword ptr [rdi + 8]
        jne     .LBB2_3
        mov     rdi, rbx
        call    alloc::raw_vec::RawVec<T,A>::reserve_for_push
        mov     rax, qword ptr [rbx]
        mov     rsi, qword ptr [rbx + 16]
.LBB2_3:
        mov     byte ptr [rax + rsi], bpl
        inc     rsi
        mov     qword ptr [rbx + 16], rsi
.LBB2_4:
        add     rsp, 8
        pop     rbx
        pop     rbp
        ret

(this is true on stable, beta and nightly).

I think a blocking point here is that rustc/LLVM do not manage to infer the invariant:

pub fn noop(v: &mut Vec<u8>) {
     // v.len <= v.capacity
     if let Some(x) = v.pop() {
        // v.len < v.capacity
        v.push(x)
    }
}

Note that the version with added asserts for this invariant removes the useless conditional call to reserve_for_push but instead gets useless calls to assert failure code.

pub fn noop(v: &mut Vec<u8>) {
    assert!(v.len() <= v.capacity());
    if let Some(x) = v.pop() {
        assert!(v.len() < v.capacity());
        v.push(x)
    }
}

example::noop:
        push    rax
        mov     rcx, qword ptr [rdi + 8]
        mov     rax, qword ptr [rdi + 16]
        cmp     rax, rcx
        ja      .LBB0_6
        test    rax, rax
        je      .LBB0_4
        lea     rdx, [rax - 1]
        mov     qword ptr [rdi + 16], rdx
        cmp     rdx, rcx
        jae     .LBB0_5
        mov     qword ptr [rdi + 16], rax
.LBB0_4:
        pop     rax
        ret
.LBB0_6:
        lea     rdi, [rip + .L__unnamed_1]
        lea     rdx, [rip + .L__unnamed_2]
        mov     esi, 41
        call    qword ptr [rip + core::panicking::panic@GOTPCREL]
        ud2
.LBB0_5:
        lea     rdi, [rip + .L__unnamed_3]
        lea     rdx, [rip + .L__unnamed_4]
        mov     esi, 40
        call    qword ptr [rip + core::panicking::panic@GOTPCREL]
        ud2

.L__unnamed_3:
        .ascii  "assertion failed: v.len() < v.capacity()"

.L__unnamed_5:
        .ascii  "/app/example.rs"

.L__unnamed_4:
        .quad   .L__unnamed_5
        .asciz  "\017\000\000\000\000\000\000\000\025\000\000\000\t\000\000"

.L__unnamed_1:
        .ascii  "assertion failed: v.len() <= v.capacity()"

.L__unnamed_2:
        .quad   .L__unnamed_5
        .asciz  "\017\000\000\000\000\000\000\000\023\000\000\000\005\000\000"

[cynecx]

I think there are two issues here:

• the invariant self.len <= self.cap isn't encoded anywhere inside the push and pop methods
• llvm's constraint elimination pass (in llvm 16) isn't smart enough to figure these things out (even with the assumes)

The first issue can be fixed by adding assume(self.len <= self.cap)s to push and pop. The second one is somewhat tricky, however we are fortunate that this has been improved somewhat already in upstream llvm:

https://godbolt.org/z/b5sc6T7ze (c++ reproducer, so it's not directly visible that the constraint elimination pass got improved)
https://godbolt.org/z/eq69G11xf (llvm-ir)

[krtab]

Thanks for investigating!

Unfortunately your code is equivalent to this Rust code which gets correctly optimized (https://godbolt.org/z/s4ansTsaG):

pub fn noop(v: &mut Vec<()>) {
    if let Some(x) = v.pop() {
        v.push(x)
    }
}

I'm not proficient in C++ but I'll try to find an example closer to Rust.

[krtab]

This gets correctly optimized, I'll try a PR to add the assume to Vec::pop and see how it does on benchmarks.

#![feature(core_intrinsics)]

use std::intrinsics::assume;


fn pop<T>(v: &mut Vec<T>) -> Option<T> {
    let res = v.pop();
    if res.is_some() {
        unsafe {assume(v.len() < v.capacity());}
    }
    res
}

pub fn noop(v: &mut Vec<u8>) {
    let tmp = pop(v);
    match tmp {
        Some(x) => v.push(x),
        None => ()
    }
}

[SUPERCILEX]

Just ran into #105156 which seems similar

[SUPERCILEX]

Also #82801