Branch elimination not performed on dead store / failure to introduce a spurious store

[SUPERCILEX]

I tried this code:

pub fn bar(count: &mut usize, n: usize) {
    for i in 0..n {
        *count = count.wrapping_add(1);
    }
}

I expected to see this happen:

example::bar:
        add     qword ptr [rdi], rsi
        ret

Instead, this happened:

example::bar:
        test    rsi, rsi
        je      .LBB1_2
        add     qword ptr [rdi], rsi
.LBB1_2:
        ret

The missed branch is going to be much more expansive than throwing something in a store buffer. Maybe you could argue the compiler thinks n=0 is going to be common, but I find that unlikely.

I'm pretty sure Rust's ownership system allows inserting stores that didn't exist because an &mut can't be used on another thread.

[erikdesjardins]

I think this may be legal, but we currently don't have any way to tell LLVM about it. The dereferenceable attribute allows introducing reads, but there is no equivalent for writes.

Coincidentally, @nikic just submitted a patch today for a writable attribute...

[SUPERCILEX]

Sweet!

cc @RalfJung I assume you've already thought about this case, but I noticed that the PR says tree borrows won't allow this optimization which is a bit of a bummer.

[RalfJung]

I'm pretty sure Rust's ownership system allows inserting stores that didn't exist because an &mut can't be used on another thread.

That's far from clear. Allowing the compiler to introduce such stores has major negative consequences and makes tons of code UB. For instance:

    let mut array = [0, 0];
    std::ptr::copy(array.as_ptr(), array.as_mut_ptr().add(1), 1);

Note that as_mut_ptr takes an &mut rereference. A spurious store to element 0 would make the code UB since it violates immutability of the as_ptr() pointer (which comes from a shared reference, and that's where it gets its immutability from).

We really don't want that code to be UB, so I think we have to disallow spurious stores.

[SUPERCILEX]

Ok, the number of issues does seem unpleasant. Do we know what the performance loss is? And is there any way to get it back? I.e. maybe enable stacked borrows locally for some function (with the safety assumption that all code executed within the enabled context must adhere to stacked borrows).

Though this specific issue's optimization is a spurious store which writes the same value that's already there. I agree that the general case where you can write whatever and then undo it as long as that's not visible won't work, but why can't we allow writing the same value as before. Granted, that class of optimizations probably isn't that useful.

[RalfJung]

In the AM, i.e. in MIR, and even in LLVM IR, this does not just store the value that's already there: if the memory is partially uninit/poison, then the "plus 0" leads to UB (in MIR) or to a fully poison value (on LLVM). I didn't try to define an aliasing model where storing the value that is already there does not count as mutation for shared references. The aliasing model is much easier to reason about when values don't matter. Also LLVM noalias does not let us ignore the values.