What are the semantics of move operands?

[RalfJung]

This question is tied up in several discussions:

• Semantics of MIR function calls rust#71117
• Semantics of MIR assignments, around aliasing, ordering, and primitives. rust#68364
• What about: use-after-move and (maybe) use-after-drop #188
• MIR: Do we allow accesing a moved place? rust#112564

However it's all somewhat messy and mixed with other questions, making it all a bit hard to follow. Part of the question is where move operands are even allowed and which places they may work on.

rust-lang/rust#112564 has some nice examples demonstrating that move is already meaningful today for function calls, and Miri fails to properly model that. I am not aware of similar examples for other uses of move (in regular MIR assignments). We should at least have a spec explaining today's codegen (and implement it in Miri); I don't know if there are plans for the future here that would require a tighter spec than that.

The function call example lends itself to a semantics like this. At a high level, move would mean "load the value from the given place, and then deallocate the place it came from, before allocating any of the new memory needed for this statement -- that way the old memory may actually be reused for the new allocation".

However this only makes sense for certain place expressions (move(local.field) would have to be disallowed). And how does it look like for MIR assignments?

local2 = Aggregate(... move(local) ...)

could mean "load the MiniRust Value from local, then dealloc local like StorageDead, then StorageLive local2, then store the value in there". But when would that be useful? If local2 was already live before, there's no advantage over just doing

local2 = Aggregate(... copy(local) ...)
StorageDead(local)

so supposedly this should only be used for initializing a value?

Using custom MIR, can we have concrete examples of move in an assignment causing behavior that Miri cannot currently explain? (Specifically, having memory reused instead of doing a memcpy.) If no, could we in principle entirely get rid of move everywhere except for function calls? Cc @bjorn3

[RalfJung]

I guess an alternative would be to combine aliasing tricks with ad-hoc non-determinism: move could completely kill the stack/tree for the old place, and then as a function argument non-deterministicially, we might use the old place as backing store for the argument on the callee side. (This requires created a new stack/tree with a fresh set of tags, which is not an operation that currently exists, but I don't see a fundamental reason why it would not work. It's basically a form of "in-place realloc" that works even for subranges of an allocation.) This has the advantage of working with arbitrary places (including those that cannot be deallocated, like the result of a field projection), but it also feels more ad-hoc than the prior proposal (specifically it requires this very ad-hoc non-determinism). The proposals are also potentially not equivalent: if we observe in the callee that the original location was reused, and we know the caller used a field projection to provide the argument, we can now use offset and go outside the bounds of the argument as long as we stay inside the bounds of the larger caller-side place. (This issue would disappear if we say that offset is UB on overflow but doesn't care about allocation boundaries.)

For assignments, currently my main problem is that we don't even have a good idea of what move is supposed to achieve in terms of optimizations / codegen potential. That makes proposals hard to evaluate.

[bjorn3]

I don't have any objections to removing move operands everywhere except for function calls. Maybe there are borrowck differences though?

[RalfJung]

Here's an example that must be UB, where the contents of a moved-out-of-place are observed:

#![feature(custom_mir, core_intrinsics)]
use std::intrinsics::mir::*;

pub struct S(i32);

#[custom_mir(dialect = "runtime", phase = "optimized")]
fn main() {
    mir! {
        let unit: ();
        {
            let non_copy = S(42);
            // This could change `non_copy` in-place
            Call(unit, after_call, change_arg(Move(non_copy)))
        }
        after_call = {
            // So now we must not be allowed to observe non-copy again.
            let _observe = non_copy.0;
            Return()
        }

    }
}

pub fn change_arg(mut x: S) {
    x.0 = 0;
}

However, just making a moved-out place uninit is not sufficient. We have to also prevent writes to the moved-out-of-place. IOW, the following also must be UB:

#![feature(custom_mir, core_intrinsics)]
use std::intrinsics::mir::*;

pub struct S(i32);

#[custom_mir(dialect = "runtime", phase = "optimized")]
fn main() {
    mir! {
        let unit: ();
        {
            let non_copy = S(42);
            let ptr = std::ptr::addr_of_mut!(non_copy);
            // Inside `callee`, the first argument and `*ptr` are basically
            // aliasing places!
            Call(unit, after_call, callee(Move(*ptr), ptr))
        }
        after_call = {
            Return()
        }

    }
}

pub fn callee(x: S, ptr: *mut S) {
    // With the setup above, if `x` is indeed moved in
    // (i.e. we actually just get a pointer to the underlying storage),
    // then writing to `ptr` will change the value stored in `x`!
    unsafe { ptr.write(S(0)) };
    assert_eq!(x.0, 42);
}

[RalfJung]

rust-lang/rust#113569 implements a possible semantics in Miri that makes the above examples UB. This basically makes Move part of the syntax of function calls (i.e., Move is ignored everywhere except when the operand is an argument for a function call). For such Move arguments (and for the return place as well), after argument passing and before the callee starts running:

• We do a protected retag of the place with the fresh call ID that was just generated for the callee. The new tag we get here is thrown away; the moved-from place is completely inaccessible for the duration of the function call.
• We write Uninit into the place. (This is still needed to make sure that after the callee returns, no observation can be made about the memory that Move arguments came from: if they were passed in-place, then that memory might have changed contents during the call!)

I think this is a reasonably nice semantics and avoids extra non-determinism, but unfortunately it doesn't work entirely -- actually doing in-place argument passing changes the observations made through pointer comparisons in a way that this semantics does not explain. (Specifically, the address of the arguments and return place in the callee is still always distinct from previously created allocations.)

[cbeuw]

removing move operands everywhere except for function calls. Maybe there are borrowck differences though

I suppose we can have a pass before MirPhase::Runtime that changes all non-function call move operands to copy, and forbid move operands in MIR validation

[RalfJung]

What I meant is removing them from the syntax.

[RalfJung]

Watching this Carbon talk, I think that Carbon elegantly avoided the problems around address identity by making function arguments, by default, values rather than places. Values don't have an observable address so the callee cannot tell where they are living.

Unfortunately I don't see a way for Rust to adopt a semantics like that in a backwards-compatible way; it relies on not being able to take the address of a function argument.

[comex]

Link to relevant part of video

To me that sounds more appealing when it comes to borrowed values than owned ones.

For large owned values that are passed on the caller’s stack, we know the value exists in memory and has a stable address as long as the function runs. Not letting the user take advantage of that – or in other words, forcing a copy to a new stack allocation if the user tries to do something that does require an address – seems unnecessarily limiting. Are there optimizations that a no-observable-address approach would allow that aren’t currently viable?

For borrowed arguments, not having address identity would have allowed the compiler to optimize borrows of small types, like &i32 or &Rc<T>, to be passed by value instead of using an actual pointer. LLVM can sometimes do this anyway (when it can determine that the callee doesn’t care about the address), but only in specific conditions and definitely not across compilation unit boundaries.

Of course, the ship has long since sailed on whether references carry address identity, and there were good reasons why they do. But it sounds like Carbon might be able to do better, by allowing arguments to be passed in 'borrowed' form without actually using pointer types, and having the compiler automatically determine whether to pass the data in a pointer or in registers. The cost is that it doesn't seem to have a first-class type representing an immutable borrow at all – or if it does, it's not mentioned in the video and would represent additional language complexity compared to Rust, which has only one way to represent an immutable borrow. If it doesn't have one, then borrows become less composable. Is it possible in Carbon to have an argument of type equivalent to Either<&T, &U>? (I imagine it's at least possible to have an argument of type equivalent to Option<&T>, just because optionals are built into the language.)

[RalfJung]

For large owned values that are passed on the caller’s stack, we know the value exists in memory and has a stable address as long as the function runs. Not letting the user take advantage of that – or in other words, forcing a copy to a new stack allocation if the user tries to do something that does require an address – seems unnecessarily limiting.

Having the semantics depend on "large" and "owned" seems really unappealing. It would be a different matter if we guaranteed that this was always done like that.

For borrowed arguments, not having address identity would have allowed the compiler to optimize borrows of small types, like &i32 or &Rc, to be passed by value instead of using an actual pointer. LLVM can sometimes do this anyway (when it can determine that the callee doesn’t care about the address), but only in specific conditions and definitely not across compilation unit boundaries.

If you are passing an &i32 then they definitely have an address. I was talking about passing an i32. It's not great that those have an observable address.

[comex]

Having the semantics depend on "large" and "owned" seems really unappealing. It would be a different matter if we guaranteed that this was always done like that.

Well, I think it's fine for it to be nondeterministic. I'm more concerned about what optimizations might be ruled out by any particular definition.

If you are passing an &i32 then they definitely have an address. I was talking about passing an i32. It's not great that those have an observable address.

I know, but I'm arguing the opposite of your last sentence. I think arguments having observable addresses is not a big problem, but &i32 arguments having observable addresses for their pointees is a problem (albeit an unfixable one) because it results in inefficiency.

It sounds like what Carbon is doing for its default argument passing mode is somewhere in between Rust's T and &T. It's semantically an immutable reference: the callee cannot mutate or move the value, and passing a large value in this mode is expected to not require an expensive copy (i.e. it should be passed by pointer). But it differs from Rust references in that values passed this way can't have their address taken, hiding the weirdness of address instability from the user (whereas Rust references are expected to be convertible into pointers). Also, due to it being the default mode, it would tend to be used in cases where Rust would pass arguments by value (e.g. non-generic Rust code would usually pass i32 rather than &i32). The generated code will pass the argument either by pointer or in registers depending on the size. At least, that's what I gathered from the part of the video I watched; I could be wrong.

[comex]

By the way, there’s another reason that address stability of references is relevant. Suppose that you could go back in time and change Rust 1.0 to disallow taking the address of function arguments, while keeping references as-is. There would be a usability problem, because what if a function that takes T by value wants to call another function that takes &T? That’s probably the case for most functions, considering how ubiquitous &self is in Rust. If calling some_argument.some_method() (where the method takes &self) was an error, then usability would suffer. If it was allowed, then it would have to implicitly move the value to the caller’s stack, but then there’d be little benefit left in forbidding taking the address in other cases; you might as well just say that taking the address is always allowed. In other words, from an Abstract Machine perspective, functions always move all their arguments to their stacks. But that would defeat the purpose entirely.

In Carbon this (apparently) isn’t a problem because Carbon’s equivalent of &self is the mode that doesn’t allow taking the address.

[RalfJung]

It sounds like what Carbon is doing for its default argument passing mode is somewhere in between Rust's T and &T. It's semantically an immutable reference: the callee cannot mutate or move the value, and passing a large value in this mode is expected to not require an expensive copy (i.e. it should be passed by pointer). But it differs from Rust references in that values passed this way can't have their address taken, hiding the weirdness of address instability from the user (whereas Rust references are expected to be convertible into pointers). Also, due to it being the default mode, it would tend to be used in cases where Rust would pass arguments by value (e.g. non-generic Rust code would usually pass i32 rather than &i32). The generated code will pass the argument either by pointer or in registers depending on the size. At least, that's what I gathered from the part of the video I watched; I could be wrong.

Ah, that's an interesting way to frame this, thanks.

They do compare it with C++ references that also are not quite like ours (though I don't recall if C++ references have an observable address).

By the way, there’s another reason that address stability of references is relevant. [...]

That's a good point.