[MaybeUninit::uninit(); N] memsets memory

[SUPERCILEX]

I tried this code (from #93668 (comment)):

let mut p = [MaybeUninit::<u8>::uninit(); 571];
// VS
let mut p = MaybeUninit::<[u8; 571]>::uninit();

Godbolts: https://godbolt.org/z/341fEjqMd, https://godbolt.org/z/K9dMx8Whr

I expected to see this happen: no memset.

Instead, this happened: uninitialized memory is not actually uninitialized.

The docs explicitly say that these two should be equivalent: https://doc.rust-lang.org/stable/std/mem/union.MaybeUninit.html#method.uninit_array

[nikic]

Looks like this literally does a memset(undef): https://godbolt.org/z/9fq7W3q3v

Surprised this is not optimized ... but I'm afraid that adding this optimization now would not be accepted, because it is technically illegal, due to the poison/undef distinction (https://alive2.llvm.org/ce/z/-Uryfw).

[RalfJung]

I've been looking at the assembly of [MaybeUninit::uninit(); N] and I'm pretty sure that ends up memsetting the array whereas MaybeUninit::<[u8; N]>::uninit() doesn't. That seems like a serious bug? Based on these docs, the two should be equivalent: https://doc.rust-lang.org/stable/std/mem/union.MaybeUninit.html#method.uninit_array.

It's not what we want, yeah. But LLVM is way outside my purview, all I can say is that LLVM is allowed to not memset them -- in that sense, they are equivalent. "Equivalent" doesn't mean "generates the same assembly code" (that would be basically impossible to guarantee), it means "has the same observable behavior and the same UB".

@nikic this is new memory though, not memory that could even contain poison. So it would be technically legal to do the optimization we want.

[RalfJung]

Oh wait, that's a different code than in the OP? I was talking about [MaybeUninit::<u8>::uninit(); 571].

[RalfJung]

Though not being able to optimize away "overwriting with undef" is also exceedingly silly. That's an LLVM design flaw. I hope they still plan to fix this by killing undef entirely?

Could we work around this by overwriting with poison instead? Though with poison not being per-byte but per-value that might also not be what we want.

[nikic]

FWIW I put up https://reviews.llvm.org/D124173 to implement the optimization, but I don't know if it will be accepted. It would be silly not to accept it given that we do the same thing for plain stores, but sometimes people get pedantic in weird places :)

Could we work around this by overwriting with poison instead? Though with poison not being per-byte but per-value that might also not be what we want.

I believe the undef here comes from a load from uninitialized memory -- there are plans to switch that to produce poison (llvm/llvm-project#52930), but those are long term plans that will involve a good bit of work.

[Kobzol]

Oh wait, that's a different code than in the OP? I was talking about [MaybeUninit::::uninit(); 571].

Currently it behaves like this:

let mut p = [MaybeUninit::<u8>::uninit(); 571]; // memset
let mut p: [MaybeUninit<u8>; 571] = MaybeUninit::uninit_array(); // no memset
let mut p = MaybeUninit::<[u8; 571]>::uninit(); // no memset

[SUPERCILEX]

Maybe this is a stupid question, but why is rust emitting a memset(undef) in the first place? That seems like a rust bug rather than an llvm bug.

Question about LLVM: @nikic isn't your PR actually invalid? That would depend on undef propagation, i.e. does passing an undef through a parameter require it to materialize or does the undef propagate through allowing every use to take on a different value? If it can take on a different value, then your change is fine. Otherwise, that optimization is invalid because every byte under the memset must be identical (even if it's some random value).

Going back to this begin a rust bug, here's what I mean. Let's compare this to an unconditional branch optimization. Presumably rust emits ir for an if false and lets llvm do the dead code elimination. That approach is valid because emitting dead code is just slow, not wrong. On the other hand, emitting any kind of memset violates the contract of uninit which states that the memory will be uninitialized. memset(undef) initializes that memory, even if it's initialized to garbage. That means fixing the bug on the llvm side is asking llvm to uphold a rust API contract which seems like a no bueno. Unless I'm misunderstanding something?

[nikic]

@SUPERCILEX In [MaybeUninit::<u8>::uninit(); 571] the MaybeUninit::<u8>::uninit() bit is producing uninitialized memory, but then you're taking that and copying it into 571 array elements. That's where the memset and undef come from. I don't think there is any API contract being violated here, though certainly a reasonable optimization expectation is violated. Generally, MaybeUninit in rust is highly dependent on LLVM optimizations to produce decent code.

That would depend on undef propagation, i.e. does passing an undef through a parameter require it to materialize or does the undef propagate through allowing every use to take on a different value? If it can take on a different value, then your change is fine. Otherwise, that optimization is invalid because every byte under the memset must be identical (even if it's some random value).

I don't believe we specify the behavior of memset with undef in that much detail, but generally speaking undef does not need to be materialized at call boundaries, and can take on different values for each use in the called function. Of course, things are a bit tricky when it comes to intrinsics, as we don't have a function implementation to consult in that case.

[SUPERCILEX]

Thanks for all these details! I think I still don't understand uninitialized memory then. 😅 To me, "copies uninitialized memory" is a nonsensical statement — how can you copy something that doesn't exist? Conceptually, I've been thinking about uninitialized memory from the abstract machine perspective as the presence of a box in which to put stuff. You can put undefined stuff in there no problem, but you have to put something in there for it to not be a void (aka uninitialized). Is that just totally wrong? I guess I'm coming at this from the C angle in which uninitialized memory is just a fat pointer.

[RalfJung]

Think of uninit memory like this: every byte of memory either holds an initialized u8, or is not initialized.

enum AbstractByte {
  Init(u8),
  Uninit,
}

We can just copy a list of AbstractByte from one part of memory to another, that is perfectly meaningful -- and it also copies over the "init" state of each byte. (This is also basically the right model for C, btw. Also, it's actually a bit more complicated due to pointer provenance, but let's ignore that for now.)

See this blog post for some more details.

[SUPERCILEX]

Mmmm, I like that enum, thanks. So then the uninit variant is being mapped to llvm's undef?

In that case, [MaybeUninit::<u8>::uninit(); N]; and MaybeUninit::<[u8; N]>::uninit(); have very different semantics that the docs are straight up wrong about. Here's what I think the next steps should be:

1. Fix the docs to clarify the difference between the above code snippets.
2. Stabilize maybe_uninit_uninit_array.
3. Add a clippy lint that tells people to migrate to uninit_array from an inline const expression. It would be great for the memset(undef) to be optimized out, but I don't think most people have understood what [MaybeUninit::<u8>::uninit(); N]; actually means and wouldn't have used it if they did.

This issue should stay open to keep an eye on https://reviews.llvm.org/D124173 while the rest of the discussion can be moved to the uninit_array tracking issue. Does that sound like a plan?