Semantics of MIR assignments, around aliasing, ordering, and primitives.

[eddyb]

In today's MIR, an indirect assignment like *p = *q; is similar to, but not exactly the same as:

tmp = *q;
*p = tmp;

The differences are:

• performance: they only produce the same codegen for primitives
  • this is assuming tmp isn't used elsewhere, allowing codegen to treat it like an SSA value, resulting in store(p, load(q)), which is also what *p = *q codegens to
  • for non-primitives, the amount of data being copied doubles, as tmp must be in memory
• correctness: only *p = *q; is UB (AFAIK) if p..p+size overlaps q..q+size
  • this also likely only affects non-primitives, which have to copy data in memory, but we could decide to ignore the type and always make it UB when they overlap

---

For the purposes of this discussion, a primitive is:

• scalar (bool, char, integer, float, or pointer/reference)
• vector (SIMD-enabled array of scalars)

Scalar pairs likely also should/need to be included, due to how easy they are to support in any code that already handles scalars, and also due to their use in wide pointers/references.

---

What's interesting about primitives, though, is that some kinds of Rvalues (the RHS of the assignment) always produce primitive values, because they're primitive operations.

The Rvalue variants which are always primitive, today, are:

• Ref (&T / &mut T - may become dependent on custom DSTs in the future)
• AddressOf (*const T / *mut T - may become dependent on custom DSTs in the future)
• Len (usize)
• Cast, other than unsizing (scalar)
• BinaryOp, UnaryOp (scalar, or maybe also vector)
• CheckedBinaryOp (pair of integer and bool - only if we consider scalar pairs to be primitive)
• NullaryOp(SizeOf) (usize)
• NullaryOp(Box) (Box<T>)
• Discriminant (integer)

Which leaves these variants as potentially relying on memory operations to write the result:

• Use (any type, one copy)
• Repeat ([T; N], N copies)
• Cast, specifically unsizing (any type implementing CoerceUnsized, per-field copies)
• Aggregate (any ADT, per-field copies)

If we want to remain conservative, we could ignore types for the latter, and just assume that the destination of the assignment cannot overlap any memory read in the Operands of the Rvalue.

We could even cement the distinction by moving the always-primitive operations into a new PrimOp enum, and/or move the other Rvalues to their own statements (e.g. introduce Copy(*p, *q)), but that's more aesthetic than anything for the time being.

At the very least, we should probably document these differences, and make sure that miri only allows overlaps in the cases we don't consider UB (either abstractly, or due to our choice of codegen).

---

Another interesting aspect of the always-primitive ops is that they're "pure functions" of their operands (other than NullaryOp(Box), I suppose, but that could be replaced with a call to a lang item returning a Box<MaybeUninit<T>>, instead).

This means that if we wanted to, we could replace some of the intermediary locals with an PrimOp DAG, a bit like SSA but without φ (phi) nodes or a strict instruction stream.
All of the necessary ordering would still happen at the statement level (so this is nowhere near as complex as VSDG), but we might see some benefits in scalar-heavy code.

---

Asides aside, cc @RalfJung @rust-lang/wg-mir-opt

---

The latest proposal is here

[nikomatsakis]

@eddyb I can't quite tell if there is a proposal here. I think you're proposing that we alter MIR construction for some kinds of rvalues to avoid the temporary?

[eddyb]

@nikomatsakis Sorry, I didn't know how to phrase it but...
I don't think the current (implicit) semantics are clearly defined, and there is some amount of implicitly relying on whatever LLVM does.

The only immediate proposal here in terms of changing the MIR would be that split of Rvalue into "produces some primitive" vs "shuffles data around".

But the discussion I want to start is on the actual semantics, maybe also diving into how explicit we can make the purity, ordering, etc. of various MIR concepts.

EDIT: maybe I should've focused more on how Operand behaves like a Place in some situations, which complicates its semantics (i.e. it's only not Place-like for primitive types, because those can be eagerly loaded).

[RalfJung]

correctness: only *p = *q; is UB (AFAIK) if p..p+size overlaps q..q+size

I agree. We should make sure Miri actually correctly catches this in all cases. We are doing the right thing for "big" copies, but Miri has some optimizations for scalars where we might fail to check things properly. There even is a FIXME for that. ;)

maybe I should've focused more on how Operand behaves like a Place in some situations, which complicates its semantics (i.e. it's only not Place-like for primitive types, because those can be eagerly loaded).

That's just an optimization in Miri though, not part of the spec.

MIR values, the simple way

Let us ignore types for a minute. Conceptually, if I were to formally specify MIR, I'd say that an Rvalue (or I should probably rather say, a Value) is a sequence of bytes (Rust bytes -- so, they track initializedness and pointer provenance). p = q; is specified as first evaluating p to a Place, then evaluating q to a Value (this reads from memory!), and then storing the latter into the former (with a check to make sure there is no overlap). At least I think that is the evaluation order...

In the special case you considered, *p = *q, we should be careful to remember that *q is a place that needs to be coerced to a value to actually appear on the RHS of an assignment. If we call that coercion load (because it has the effect of loading a sequence of bytes from memory), the assignment should really be written *p = load(*q). The load is responsible for the "read" part of this, the assignment itself only performs a write.

In Miri, we don't want to carry around these temporary sequences of bytes, that's why Miri's Operand has a "lazy" case that delays the load until the time the bytes are actually stored into some place. But that is supposed to be an implementation detail of the interpreter, not anything that actually shows up in the spec -- and thus not something that anyone outside of the interpreter should be concerned with.

typed MIR values

Reality is more complex than that, though -- for example, the spec above fails to explain that padding gets "reset" to Undef on a copy. So, I think the proper way to specify this is to say that a MIR Value is something like the enum Value from this document.

When evaluating a Value like the RHS of an assignment, we load the (Rust) bytes from memory, then perform the conversion of that byte sequence to a Value according to the representation relation of the type that is used for this assignment. When storing a Value into a place, we consult the representation relation again to figure out how to represent this Value as a byte sequence.

[eddyb]

That's just an optimization in Miri though, not part of the spec.

Eagerly loading is unavoidable in codegen, and I wasn't thinking of miri when I wrote that.

In Miri, we don't want to carry around these temporary sequences of bytes, that's why Miri's Operand has a "lazy" case that delays the load until the time the bytes are actually stored into some place. But that is supposed to be an implementation detail of the interpreter, not anything that actually shows up in the spec -- and thus not something that anyone outside of the interpreter should be concerned with.

This is the same in codegen, for anything you can't eagerly load.
There's no real alternative short of introducing copies and temporaries which aren't in MIR, AFAIK.

When evaluating a Value like the RHS of an assignment, we load the (Rust) bytes from memory, then perform the conversion of that byte sequence to a Value according to the representation relation of the type that is used for this assignment. When storing a Value into a place, we consult the representation relation again to figure out how to represent this Value as a byte sequence.

But... there is no place to keep an arbitrary sequence of bytes other than memory.
If there was, almost none of what I wrote would be relevant.

[RalfJung]

codegen should then better make sure that what it does is indistinguishable from the spec I proposed. :) I think it would be a big bad mess to have to deal with that distinction of "small" and "big" values in the spec.

And I think that indeed this is indistinguishable for UB-free programs, because of the requirement that the two regions of memory must not overlap. If this wasn't the case, it would not be correct for Miri to perform this internal optimization.

But... there is no place to keep an arbitrary sequence of bytes other than memory.

We are writing a spec. Math has all the space we could want. :D

[eddyb]

But... there is no place to keep an arbitrary sequence of bytes other than memory.

We are writing a spec. Math has all the space we could want. :D

Sure, but it sounded like an argument for not requiring "no overlap", because if you can read all of the Operands in the RHS before writing anything to the LHS Place, an overlap wouldn't cause any issues.

What you want spec-wise, IMO, if you're going down that route, is that Rvalue is computing "into" the destination Place and so can begin writing before reading any Operands.

[RalfJung]

Sure, but it sounded like an argument for not requiring "no overlap", because if you can read all of the Operands in the RHS before writing anything to the LHS Place, an overlap wouldn't cause any issues.

The argument for not allowing overlap is to give implementations (codegen, Miri) more freedom. But at the same time the spec should be as simple as possible to make reasoning as simple as we can make it.

What you want spec-wise, IMO, if you're going down that route, is that Rvalue is computing "into" the destination Place and so can begin writing before reading any Operands.

I am not sure what you have in mind, but it sounds a lot more complicated than even what I proposed.^^ I'd rather separate concerns. There is no reason that Value computation has to even mention Places.

[eddyb]

The argument for not allowing overlap is to give implementations (codegen, Miri) more freedom. But at the same time the spec should be as simple as possible to make reasoning as simple as we can make it.

The spec is not realistically implementable without that "freedom", so I can't think of it as "a nice thing on top".
I also can't think of "overlaps disallowed" as "simple" if it doesn't arise from the definition of assignment.

Alright, "value computation" doesn't have to mention Place, but maybe Assign can be defined to "lock/invalidate the destination" before computing the value?

---

In terms of being able to reason about possible optimizations/lowerings of MIR constructs, I highly dislike the possibility of more than one Place being interacted with where some of the Places are in Operands.

Ignoring unsizing coercions (which we could make its own statement or rely on a shim etc.), the only situations which ever need to require non-overlap, involve bulk copying of data, either to create an aggregate, or just between two Places.

And in my experience, optimizing away bulk copies, even if only ones between locals (let alone anything involving alias analysis), is fundamentally much harder than anything SSA-like over primitives, because there is no way to reason about any one past value, without reintroducing more of the bulk copies you're trying to remove.

I mean, it's literally graph coloring, heh.

So you can see why I don't want that kind of NP "conflict reasoning" where avoidable.

---

Or maybe MIR suffers from the LLVM problem of being too high-level for its own good, just at a different level, and/or I shouldn't care about non-Place optimizations on it.

[eddyb]

Alright, talking to @RalfJung in PM a bit made me realize there is a path forward in terms of making MIR more optimization-friendly without complicating the spec.

In terms of having "two MIRs", there's more than one way:

• "borrowck MIR" and "optimization MIR", both inside the compiler
  • this is the only path I saw at first, for dealing with irreconcilable differences
  • there are a lot of downsides (and a few upsides) to actually doing this, but we don't even need to discuss them, because it's entirely unnecessary!
• "spec MIR" and "rustc MIR", the latter expanding to the former
  • that is, "rustc MIR" would have "sugar" or "compact representations" on top on the "spec MIR" concepts, but they would remain semantically compatible
  • we can optimize "spec MIR" for simplicity, and "rustc MIR" for optimizations, as long as there is a simple mapping from the latter to the former
  • "rustc MIR" could distinguish between these while using @RalfJung's spec:
    • non-primitives, where it needs to rely on the non-overlap rule (for codegen that doesn't introduce unnecessary copies)
    • primitives, where it can just use the value computation directly, because the byte sequences are small enough

So for example, if we wanted to start using DAGs for pure operations involving primitives, we might have something like this in "rustc MIR":

  x     y
╭─┴─╮ ╭─┴─╮
╰(*)╯ ╰(*)╯
  ╰─(+)─╯
 z = ╯

(I could name the nodes, but I wanted to emphasize the DAG nature instead)

That would expand (or "serialize") into this "spec MIR":

tmp0 = x
tmp1 = Mul(tmp0, tmp0)
tmp2 = y
tmp3 = Mul(tmp2, tmp2)
tmp4 = Add(tmp1, tmp3)
z = tmp4

(6 Assigns with the semantics @RalfJung described earlier, trivially no conflicts)

Note that even if you had rustc use MIR that looked like this (which I think it actually does today, or only in some situations), it would produce the same codegen, because of all the tmp{0,1,2,3,4} locals would be deemed SSA-like.
So the DAG version would just be an optimized representation, avoiding explicit MIR locals when they would fit a certain subset of SSA.

Am I understanding your position on this correctly, @RalfJung?

[nikomatsakis]

Let me see if I can rephrase things to make sure I'm following.

First, @eddyb was saying that they wish to be sure that they can copy bytes from the source to the destination without any intermediates in codegen if necessary (i.e., for non-scaler values). One way to do that would be to define the "spec" to carry around a "destination".

But @RalfJung proposed instead that we impose the rule that the source/destination cannot overlap and define the spec in terms of loading a value, and then show that this permits the implementation the freedom to do the more optimal thing.

Next the question was raised whether we want more than one internal MIR, or if we just want to have "rustc MIR" so long as it has a canonical conversion to "spec MIR". It seems like the latter is a pretty standard construct and quite reasonable.

One caveat is that I could also imagine that we might want to have MIR construction generate things (e.g., the false edges that borrowck relies on) that we eventually strip out or compile down to simpler things (but perhaps after borrowck). We already do this for DROP terminators, for example, which effectively change their semantics after drop elaboration. This also seems relevant to the discussion we've been having about how to represent more complex places. So basically we already have "pre-optimization" and "post-optimization" IRs, in my opinion, even if they share rustc data structures.

If those things wind up being important to "spec MIR", of course, and we wish for miri to view them, then we either have to retain them throughout optimizations or to execute miri on "pre-optimization" code.

[RalfJung]

@eddyb

So you can see why I don't want that kind of NP "conflict reasoning" where avoidable.

Not really... I am not saying the compiler has to make any analysis like that, all I am saying is that we should give it the freedom to do so.

I think it is a mistake to make the spec "maximally tight" wrt any given implementation. We should leave more freedom where it makes sense so that we can adjust our implementation strategy in the future, or add more optimizations.

I highly dislike the possibility of more than one Place being interacted with where some of the Places are in Operands.

There are no Places in Operands -- as I (think I) said, that's just a Miri implementation detail.
In a "proper" reference interpreter, Operand would be defined as Vec<MiriByte>, with MiriByte being something like the Byte enum from this document.

Well, actually, in a "really proper" interpreter Operand would be replaced by the Value type from this document.

---

The spec is not realistically implementable without that "freedom", so I can't think of it as "a nice thing on top".
I also can't think of "overlaps disallowed" as "simple" if it doesn't arise from the definition of assignment.

These are good points. I agree that adding the "overlap" rule as something like an afterthought is ugly, and I would prefer if it would arise more naturally. I just have not found a way to do that, given my constraints of also keeping the evaluation of places and values independent of each other.

Alright, "value computation" doesn't have to mention Place, but maybe Assign can be defined to "lock/invalidate the destination" before computing the value?

So, basically "C-style sequencing points"-light? I am not sure if that's really less ugly than the "overlap" rule...

---

that is, "rustc MIR" would have "sugar" or "compact representations" on top on the "spec MIR" concepts, but they would remain semantically compatible

Yes that sounds very reasonable.

we can optimize "spec MIR" for simplicity, and "rustc MIR" for optimizations, as long as there is a simple mapping from the latter to the former

Agreed. :)

Am I understanding your position on this correctly, @RalfJung?

I... think so. I am not entirely sure what your proposed lowering from "rustc MIR" to "spec MIR" is relative to the "overlap" rule, but I agree with your high-level statements and that is always a good start. :D

[RalfJung]

@eddyb as a follow-up to "it would be better for non-overlap to arise naturally":

One alternative I thought of is to define Operand/Value as "something that can be stored in memory", so basically a "thunked computation" that, when given a location (the result of computing a place), puts all its stuff into it. That corresponds slightly better to what Miri actually does than the Vec<MiriByte> (the "indirect" Operand variant basically represents such a thunk, remembering where to copy from when the final destination location is known). I think this is close to what you meant when you said "Rvalue is computing into the destination Place". Somehow I missed that before and just realized it right now when re-reading your posts.

But as far as I can see this does not naturally give rise to a non-overlap rule either, and it fails to explain why padding is "lost" on typed copies and why copying value that violate the validity invariant is UB, so I ditched this in favor of the simpler, first-order approach of directly representing the value.

You seem to think that this "destination-passing style" solves the overlap problem, could you explain how? The evaluation of places and operands would still perform a particular sequence of memory operations in a particular order, there is no UB if any of these operations overlap.