[LangRef] Make lifetime intrinsic's semantics consistent with StackColoring's comment

[aqjune]

Summary

This patch is an update to LangRef by describing lifetime intrinsics' behavior
by following the description of MIR's LIFETIME_START/LIFETIME_END markers
at StackColoring.cpp (https://github.com/llvm/llvm-project/blob/eb44682d671d66e422b02595a636050582a4d84a/llvm/lib/CodeGen/StackColoring.cpp#L163) and the discussion in llvm-dev.

In order to explicitly define the meaning of an object lifetime, I added 'Object Lifetime' subsection.

[aqjune]

llvm/docs/LangRef.rst

17830

I added this part because I found this:
https://bugs.llvm.org/show_bug.cgi?id=27903
https://reviews.llvm.org/D20739

This is an old bug, so I'm not sure whether this is still valid, but the patch still exists in StackColoring.cpp, so I added this.

[aqjune]

Minor update

[jdoerfert]

I left some comments.

I think I will reply to the email thread because I have more thoughts on this by now.

llvm/docs/LangRef.rst

2570

Is "preserved" the right word here? Maybe "reserved"?

---

_ "allocation instruction"
+ "allocation value"

or something else because globals are not instructions.

---

_ "returns"
+ "return"

---

_ "free-like commands"
+ instructions that deallocate the object or impact it's lifetime

---

Lifetime markers, as of now, still talk about memory regions, not objects. I think that can be changed but should be kept in mind.

---

Why the "representable in integers" part, and "integral address"?

[aqjune]

llvm/docs/LangRef.rst

2570

Thanks.

Why the "representable in integers" part, and "integral address"?

Because it is important (IMO) and related to the lifetime. To be specific this patch, It answers whether two stack allocas with different lifetimes may have overlapping addresses.

[jdoerfert]

llvm/docs/LangRef.rst

2570

I can compare two pointers without converting them to integers, can't I? If so, I don't understand in which situations this special case would be applied. Said differently: When not convertable to integers and not comparable, and why shouldn't lifetime apply then?

[aqjune]

llvm/docs/LangRef.rst

2570

While answering to your mail, I think I understood your point. If the memory block is never observed, it doesn't matter whether it is disjoint or not.
I'll update the text.

[aqjune]

llvm/docs/LangRef.rst

2570

Oh, it was a different story. :/ well, I'll adequately update this part...

[aqjune]

Address comments

[aqjune]

It is memset(undef) in other cases

[aqjune]

Thinking about @jdoerfert 's suggestion again, it still implies that objects may have overlapping addresses regardless of lifetime. Am I understanding correctly?

What about this model I just updated? Would this support interested optimizations for lifetimes with non-allocas?

[RalfJung]

llvm/docs/LangRef.rst

17837

So this means if LLVM becomes smarter, and "what does this point to" changes from "unknown" to "this set of allocas", that could actually introduce UB because "lifetime.start" semantics changes from "memset(undef)" to "the alloca is initially dead and only becomes life at this marker". Did I understand this correctly? If yes, that seems quite problematic from a user perspective -- how can I make sure that my code does not have UB, if that depends on how "smart" LLVM's analysis is?

[aqjune]

llvm/docs/LangRef.rst

17837

(I just found your comment, sorry)
If the argument of lifetime.start/end is to be syntactically restricted (just an assumption, it's still under discussion), the 'right' syntactic pattern should be already defined somehow. It must be a closure of pointer arithmetic operations or no-ops.

[aqjune]

I updated the text to reflect the consensus made in llvm-dev discussion so far.

If lifetime.start/end isn't used with a stack pointer with zero offset, it is equivalent to memset(poison).
Also, the paragraph that describes the disjointness of addresses is removed.

Calling lifetime.start twice on an alive alloca is also updated to memset(poison).
It isn't defined as UB because I couldn't find any LLVM code or comments saying that lifetime may raise UB.
Another choice is to define it as no-op, but https://godbolt.org/z/TqoeqG requires it.

Memory accesses on a dead object should be UB because the comment at StackColoring.cpp specifies that.

I did not mention anything about the size argument of lifetime.start/end because it wasn't clear to me how the argument was used.

[aqjune]

Adding reviewers who work on backends..

[aqjune]

Gently ping, this text is ready to get reviewed. :)

[nlopes]

We've had a several months-long discussion on this topic. I think we've reached quorum to move forward.
The patch looks great, thanks for your work. Please go ahead and commit it!

This semantics documents well the current LLVM behavior and doesn't introduce any regression in applications, which was one of the potential concerns with previous versions. Moreover, it doesn't prevent free movement of instructions, which is a generally nice property to have. This patch also gives a reasonable semantics for heap objects which enables future optimizations like preventing loop-carried dependencies and hoisting allocations out of loops.

[RalfJung]

llvm/docs/LangRef.rst

17816

This sentence here is doing a lot of work. In particular, it makes the behavior of alloca *depend on the future of the current execution*, i.e. behavior depends on whether at some point in the future, a lifetime.start intrinsic is called on the resulting pointer. I think such acausal definitions are a mistake; they make it impossible to write an interpreter that just accurately executes LLVM IR and detects UB.

At the very least, the documentation of alloca should be adjusted to explicitly talk about this. Right now, the documentation of lifetime.start alters the behavior of another instruction, which is really surprising and will easily be missed.

Does LLVM correctly handle code like the following, which should not be UB even though there is an access to an alloca before the lifetime.start? (Imagine this to be LLVM IR code, and without "mustprogress")

x = alloca ...;
*x = 5;
while (true) {}
lifetime.start(x)

17830

So when ptr is a pointer to a stack-allocated object at offset 4, then *all bytes* of the object, including the ones at offset 0-3, will become poison?

[nlopes]

llvm/docs/LangRef.rst

17816

Ralf we already agreed that the current design is suboptimal and that it makes it impossible to write a *precise* interpreter for LLVM IR.
The exact semantics of lifetime.start depends on the pattern matching patterns in the stack coloring algorithm. So this intrinsic cannot be abused. It must be used for the uses it was created for only.
We agree a better design would be to tag allocas with dead so they are initially dead or just to allow allocas in any BB rather than having all them pushed to the first BB (if we assume a basic stack allocation algorithm would run even in fastisel).

So while we can write a billion corner-case examples, by hand, they are not useful for the discussion of this particular patch. We can't go back in time and fix the current design. We can't change the current design without breaking all the frontends out there either.
The way forward, if someone is interested in doing more aggressive optimizations, is to design a new mechanism that would have to live side-by-side with the current one for a couple of years to allow frontends to migrate. Or create an auto-upgrade algorithm to convert the old idiom to the new one.

I agree adding a note to alloca and cross-reference this section makes sense.

[RalfJung]

The exact semantics of lifetime.start depends on the pattern matching patterns in the stack coloring algorithm. So this intrinsic cannot be abused. It must be used for the uses it was created for only.

That's fair, but then shouldn't the docs say that? Usually one would expect the docs to say everything there is to be said; so in this case a dedicated warning might be in order to document the caveats you just mentioned.

[nlopes]

In D94002#2606276, @RalfJung wrote:

The exact semantics of lifetime.start depends on the pattern matching patterns in the stack coloring algorithm. So this intrinsic cannot be abused. It must be used for the uses it was created for only.

That's fair, but then shouldn't the docs say that? Usually one would expect the docs to say everything there is to be said; so in this case a dedicated warning might be in order to document the caveats you just mentioned.

Ok, agreed! Let's make that explicit in the document.

[aqjune]

In D94002#2606307, @nlopes wrote:

In D94002#2606276, @RalfJung wrote:

The exact semantics of lifetime.start depends on the pattern matching patterns in the stack coloring algorithm. So this intrinsic cannot be abused. It must be used for the uses it was created for only.

That's fair, but then shouldn't the docs say that? Usually one would expect the docs to say everything there is to be said; so in this case a dedicated warning might be in order to document the caveats you just mentioned.

Ok, agreed! Let's make that explicit in the document.

I'll make a super small patch that adds this sentence. :)

llvm/docs/LangRef.rst

17830

Yes, it was chosen to make all bytes poison; the first argument wasn't used because the description is saying it is the size of the *object*.

llvm/docs/LangRef.rst

::
 
     ARCHITECTURE-VENDOR-OPERATING_SYSTEM
     ARCHITECTURE-VENDOR-OPERATING_SYSTEM-ENVIRONMENT
 
 This information is passed along to the backend so that it generates
 code for the proper architecture. It's possible to override this on the
 command line with the ``-mtriple`` command line option.
 
+.. _objectlifetime:
+
+Object Lifetime
+----------------------
+
+A memory object, or simply object, is a region of a memory space that is
+reserved by a memory allocation such as :ref:`alloca <i_alloca>`, heap
+allocation calls, and global variable definitions.
+Once it is allocated, the bytes stored in the region can only be read or written
+through a pointer that is :ref:`based on <_pointeraliasing>` the allocation
+value.
+If a pointer that is not based on the object tries to read or write to the
+object, it is undefined behavior.
+
+A lifetime of a memory object is a property that decides its accessibility.
+Unless stated otherwise, a memory object is alive since its allocation, and
+dead after its deallocation.
+It is undefined behavior to access a memory object that isn't alive, but
+operations that don't dereference it such as
+:ref:`getelementptr <i_getelementptr>` or :ref:`ptrtoint <i_ptrtoint>` return
+a valid result.
+This explains code motion of these instructions across instructions that
+deallocate the object or impact it's lifetime.
+A memory object's lifetime can be explicitly specified using
+:ref:`llvm.lifetime.start <_int_lifestart>` and
+:ref:`llvm.lifetime.end <_int_lifeend>` intrinsic function calls.
+
+Two memory objects that are both alive at some program execution point have
+addresses that don't overlap.
+If their addresses can be represented in integers, two integer ranges
+``[a1, a1+sz1)`` and ``[a2, a2+sz2)`` where a1/sz1 is the begin address/size of
+the first object and a2/sz2 is the size of the second object respectively
+are disjoint.
+It is allowed for the two objects to be adjacent and share the same integral
+address at the beginning of one object and at the end of another object.
+A dead memory object can overlap any other memory object, unless stated
+otherwise.
+
 .. _pointeraliasing:
 
 Pointer Aliasing Rules
 ----------------------
 
 Any memory access must be done through a pointer value associated with
 an address range of the memory access, otherwise the behavior is
 undefined. Pointer values are associated with address ranges according

 
 
 Other targets may support this intrinsic differently, for example, by lowering it into a sequence of branches that guard scalar store operations.
 
 
 Memory Use Markers
 ------------------
 
-This class of intrinsics provides information about the lifetime of
-memory objects and ranges where variables are immutable.
+This class of intrinsics provides information about the
+:ref:`lifetime of memory objects <_objectlifetime>` and ranges where variables
+are immutable.
 
 .. _int_lifestart:
 
 '``llvm.lifetime.start``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
       declare void @llvm.lifetime.start(i64 <size>, i8* nocapture <ptr>)
 
 Overview:
 """""""""
 
-The '``llvm.lifetime.start``' intrinsic specifies the start of a memory
-object's lifetime.
+The '``llvm.lifetime.start``' intrinsic specifies the start of
+:ref:`a memory object's lifetime <_objectlifetime>`.
 
 Arguments:
 """"""""""
 
 The first argument is a constant integer representing the size of the
 object, or -1 if it is variable sized. The second argument is a pointer
 to the object.
 
 Semantics:
 """"""""""
 
-This intrinsic indicates that before this point in the code, the value
-of the memory pointed to by ``ptr`` is dead. This means that it is known
-to never be used and has an undefined value. A load from the pointer
-that precedes this intrinsic can be replaced with ``'undef'``.
+If ``ptr`` is syntactically pointing to a stack-allocated object, the object is
+initially marked as dead. The syntactic use is determined by following use-def
+chains of operations. If ``ptr`` syntactically points to more than one
+stack-allocated object via e.g., ``phi``, all of those are dead. This explains
+merging multiple ``lifetime.start`` calls into one.
+
+After '``llvm.lifetime.start``', the stack object that ``ptr`` points to in
+runtime is marked as alive and it is initialized with '``undef``'.
+The stack object is dead again when either
+:ref:`llvm.lifetime.end <int_lifeend>` to the alloca is executed or the
+function returns.
+
+After :ref:`llvm.lifetime.end <int_lifeend>` is called,
+'``llvm.lifetime.start``' on the stack object can be called again.
+In this case, the stack object has multiple lifetimes.
+The second '``llvm.lifetime.start``' call does not relocate the object.
+
+The behavior of calling '``llvm.lifetime.start``' after another
+'``llvm.lifetime.start``' to the same alive stack object is
+implementation-defined and depends on the backend that is enabled.
+
+If ``ptr`` is syntactically pointing to at least one non-stack-allocated object,
+or the object it points to is unknown, it is equivalent to
+'``memset(ptr, undef, size)``'. If ``size`` is -1, it is equivalent to
+memset undef from the begin to the end of the object.
 
 .. _int_lifeend:
 
 '``llvm.lifetime.end``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 
 ::
 
       declare void @llvm.lifetime.end(i64 <size>, i8* nocapture <ptr>)
 
 Overview:
 """""""""
 
-The '``llvm.lifetime.end``' intrinsic specifies the end of a memory
-object's lifetime.
+The '``llvm.lifetime.end``' intrinsic specifies the end of
+:ref:`a memory object's lifetime <_objectlifetime>`.
 
 Arguments:
 """"""""""
 
 The first argument is a constant integer representing the size of the
 object, or -1 if it is variable sized. The second argument is a pointer
 to the object.
 
 Semantics:
 """"""""""
 
-This intrinsic indicates that after this point in the code, the value of
-the memory pointed to by ``ptr`` is dead. This means that it is known to
-never be used and has an undefined value. Any stores into the memory
-object following this intrinsic may be removed as dead.
+If ``ptr`` is syntactically pointing to a stack-allocated object(s),
+the object that ``ptr`` points to is dead. See
+:ref:`lifetime.start <int_lifestart>` for the rules for syntactically finding
+the object(s).
+Calling ``llvm.lifetime.end`` on a dead alloca is no-op.
+
+If ``ptr`` is syntactically pointing to at least one non-stack-allocated object,
+or the object it points to is unknown, it is equivalent to
+'``memset(ptr, undef, size)``'. If ``size`` is -1, it is equivalent to
+memset undef from the begin to the end of the object.
 
 '``llvm.invariant.start``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 This is an overloaded intrinsic. The memory object can belong to any address space.