GVN transformation regarding lifetime.start

[aqjune]

https://godbolt.org/z/8D-TvV

define i8 @src() {
entry:
    %p = alloca i8
    call void @llvm.lifetime.start.p0i8(i64 1, i8* %p)
    store i8 1, i8* %p
    call void @llvm.lifetime.start.p0i8(i64 1, i8* %p)
    %v = load i8, i8* %p
    call void @llvm.lifetime.end.p0i8(i64 1, i8* %p)
    ret i8 %v
}

define i8 @tgt() {
  %p = alloca i8, align 1
  call void @llvm.lifetime.start.p0i8(i64 1, i8* %p)
  store i8 1, i8* %p, align 1
  call void @llvm.lifetime.start.p0i8(i64 1, i8* %p)
  call void @llvm.lifetime.end.p0i8(i64 1, i8* %p)
  ret i8 undef
}

LangRef says A load from the pointer that precedes this intrinsic can be replaced with 'undef'.

[aqjune]

ping @RalfJung

[RalfJung]

Via email you wrote

but the problem here is that we cannot determine which lifetime.start precedes another one in compile time. :/

My personal operational interpretation is that during execution, we keep track of which locals are alive and which are not. When marking a local as alive, if the local is already live, then this is UB (or at least the value of the local gets reset to undef). Would that explain the behavior you are seeing?

[aqjune]

Okay, to revisit this issue:

https://github.com/llvm/llvm-project/blob/eb44682d671d66e422b02595a636050582a4d84a/llvm/lib/CodeGen/StackColoring.cpp#L163 states this:

//   L2) on a `lifetime.start`, a stack slot is marked as *in-scope* and
//   the stack slot is overwritten with `undef`. << important

A relevant thread: rust-lang/rust#42371 (comment)

I think we can encode this precise semantics by resetting the corresponding local_block_val element. @nunoplopes What do you think?

[aqjune]

FWIW: Rust's MIR interpreter assumes that redundant StorageLive is UB, so refinement holds.

[nunoplopes]

Duplicated lifetime.start are not important. They never happen.
These intrinsics are meant to be used by the inliner, and are never added by users. llc doesn't seem to care about duplicated starts: https://godbolt.org/z/qbx8qK
Starts can show up multiple times automatically, but only if preceded by a lifetime.end. This happens, for example, when inlining a function call inside a loop.
With the evidence we have so far, I see two easy semantics:

• Make lifetime.start memset the respective block to poison (I think this is what you suggested)
• Trigger UB on start/end mistmatches

Setting it to poison seems the easiest. so I agree with you @aqjune. Just don't touch memory.cpp this month 😀

[RalfJung]

Duplicated lifetime.start are not important. They never happen.

They certainly used to happen in the LLVM IR that rustc generated. Is that a bug, i.e., is it UB to mark an already live local as live?

Make lifetime.start memset the respective block to poison (I think this is what you suggested)

This would mean that the memory stays at the same location, so pointers created to this local earlier will remain valid.

[nunoplopes]

Duplicated lifetime.start are not important. They never happen.

They certainly used to happen in the LLVM IR that rustc generated. Is that a bug, i.e., is it UB to mark an already live local as live?

I don't know if it's UB, but it's a bug for sure. Doesn't make sense to have 2 starts given that these start/end intrinsics are used for the stack allocator. They are used to compute the lifetime of an alloca, so I can't find a meaning for starting the lifetime twice (without ending it beforehand).

Make lifetime.start memset the respective block to poison (I think this is what you suggested)

This would mean that the memory stays at the same location, so pointers created to this local earlier will remain valid.

That's ok I guess. llc doesn't seem to do anything fancy with duplicated starts.

[RalfJung]

I don't know if it's UB, but it's a bug for sure.

If that is the consensus, it would be good to have that documented in the LangRef, and maybe have debug assertions catching this. For the people writing the Rust side of this, it was far from clear that this is considered buggy by LLVM.

[aqjune]

It seems a transformation may introduce unpaired lifetime.start and such one should be fixed as well.
This link (link) has:

; 'p = alloca' omitted
lifetime.start(p)
....
lifetime.end(p)

  => (optzns like loop versioning)

if (cond) {
  // optimized code, has no lifetime.start
} else {
  lifetime.start(p)
  ....
}
lifetime.end(p)

[nunoplopes]

The link you posted is about Polly. That isn't included in LLVM mainline. The replies in that thread also go in the direction of requiring paired lifetime start/end intrinsics.
So the previous conclusion still holds: triggering UB or memset poison are fine semantics. But memset poison seems easier, so I think we can go with that one.

[RalfJung]

Btw, rustc still emits redundant StorageEnd which translate to lifetime.end. I have not investigated the details as I cannot imagine this causing problems. What are your thoughts on that @nunoplopes?

[nunoplopes]

Btw, rustc still emits redundant StorageEnd which translate to lifetime.end. I have not investigated the details as I cannot imagine this causing problems. What are your thoughts on that @nunoplopes?

That should be fine. The first one wins. As long as there's no use after any StorageEnd.

[aqjune]

Okay.. I wrote a specification of lifetime.start/end. What do you think Nuno and Ralf?

for each lifetime.start S of alloca A, there should exist lifetime.end E of A s.t.

• S dominates E /\ E postdominates S (there is no path that can visit only S or E)
• Lifetimes of A cannot overlap: for any path from S to E, lifetime.start and lifetime.end of A other than S and E shouldn't exist.

Then, alloca A is live between the lifetime.start/end pairs. Accessing the alloca out of the lifetime is UB. lifetime.start initializes the bytes as undef.
If there is no lifetime.start/end of A in the function, A's lifetime starts from its declaration and ends when the function returns.

One additional concern is that it might be a good idea to syntactically restrict the pointer argument given to lifetime.start/end. It won't be meaningful if it was loaded from the memory, such as %p = load i8** %q; lifetime.start(%p).

[nunoplopes]

Two comments:

• I would replace undef with poison.
• Another way of ending lifetime is with function termination, e.g., a noreturn call, return, etc. There's no need for a lifetime.end beforehand (didn't check if the inliner inserts lifetime.end before all noreturn calls, but likely not)

Then the question is about multiple syntactic start/end pairs for the same alloca. I assume pointers may become invalid between these as in theory the allocator can change the alloca'ed object to a different address. Should we use lifetime.start as an allocation site and lifetime.end as free?
If start/end show up inside a loop and are executed multiple times, they are guaranteed to go to the same location I guess as memory allocation is done statically, so we may want to optimize that case.

The syntactic check makes sense. I hope LLVM's verifier is enforcing that. 😅

[aqjune]

Another way of ending lifetime is with function termination, e.g., a noreturn call, return, etc. There's no need for a lifetime.end beforehand (didn't check if the inliner inserts lifetime.end before all noreturn calls, but likely not)

Oh, I've never thought about this. I'll experiment with a few cases.

Should we use lifetime.start as an allocation site and lifetime.end as free?

I think this is tricky. We'd like to assume that ptrtoint can be freely hoisted/sinked across lifetime intrinsic (or change LLVM to forbid that?)

I would replace undef with poison.

I'd like to do so, but would people like this change to be accompanied with lifetime? It is about the value of uninitialized storage.