Allocations cannot shrink? Or alive fails to model extern function calls?

[RalfJung]

During a Rust discussion, the following interesting example came up:

----------------------------------------
define i32 @src() {
%0:
  %mem = call ptr @malloc(noundef i64 160) nofree noundef nothrow noalias willreturn dereferenceable_or_null(160) alloc-family(malloc) allockind(alloc, uninitialized) allocsize(0) memory(inaccessiblemem: readwrite)
  call void @bar(noundef ptr %mem)
  %arrayidx = gep inbounds ptr %mem, 4 x i64 0
  %1 = load i32, ptr %arrayidx, align 4 // load from `mem[0]`
  ret i32 %1
}
=>
define i32 @tgt() {
%0:
  %mem = call ptr @malloc(noundef i64 160) nofree noundef nothrow noalias willreturn dereferenceable_or_null(160) alloc-family(malloc) allockind(alloc, uninitialized) allocsize(0) memory(inaccessiblemem: readwrite)
  call void @bar(noundef ptr %mem)
  %arrayidx = gep inbounds ptr %mem, 4 x i64 39
  %1 = load i32, ptr %arrayidx, align 4 // load from `mem[39]`
  ret i32 %1
}
Transformation seems to be correct!

I am struggling to interpret this. As a transformation I would say this is definitely incorrect since bar could have initialized this memory, and then the tgt program can return a different value than the src program. Maybe that is some systematic Alive limitation that I am not understanding, but then it is hard to say what this actually says about the intended LLVM semantics.

In particular, what if there was an operation that can shrink an allocation in-place? In Rust we are considering adding such an operation. Then even though loading at offset 0 is still fine after bar, loading from offset 39 might not be fine any more. Maybe the fact that Alive accepts this transformation is a sign that LLVM assumes that allocations can never shrink (which would be a bummer), or maybe this is just Alive not properly modeling all the things bar could do -- we could use some help to interpret these results. :)

[nunoplopes]

The current LLVM memory model doesn't allow changing the size of objects in place.

So, either bar does realloc on the pointer, which is equivalent to freeing it, and thus the load would be UB. Or it doesn't touch the pointer and the load is all fine.

C and C++ don't have object resizing. Or at least not to a point where we may need to model in the IR.
If Rust needs something along these lines, then we need to change LLVM IR's semantics and its optimizations. LLVM is not correct per the semantics you want.

The easiest way would be for Rust to hide the resizing in some function that returns a new pointer, so LLVM can think it's a new object. If that isn't viable (for some reason), then there's a ton of work to be done on LLVM. The Alive2 side is easy FWIW.

[RalfJung]

The current LLVM memory model doesn't allow changing the size of objects in place.

Thanks! That's what we wanted to find out. Is this written down anywhere?

The easiest way would be for Rust to hide the resizing in some function that returns a new pointer, so LLVM can think it's a new object

That doesn't work, since the entire point of this is to allow old pointers to still be used with the resized allocation. Otherwise we could just use realloc.

[nunoplopes]

The current LLVM memory model doesn't allow changing the size of objects in place.

Thanks! That's what we wanted to find out. Is this written down anywhere?

I don't recall, but I don't think so. But I can guarantee you that optimizations follow that semantics. And Alive2 too, and these days it is kind of the oracle.

[RalfJung]

What about the other question -- isn't the example an Alive bug since bar might initialize mem[0] to some value and then the source would return that value, but the target would return poison/undef since memory is uninit?

[nunoplopes]

What about the other question -- isn't the example an Alive bug since bar might initialize mem[0] to some value and then the source would return that value, but the target would return poison/undef since memory is uninit?

It's a bug, yes.
It's a know problem: Alive2 doesn't havoc local memory blocks on function calls. This requires aligning the allocations in the src & tgt programs, and that stuff isn't implemented yet.

[RalfJung]

I have submitted a PR to LLVM that would permit allocations to grow: llvm/llvm-project#141338.