[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

17898

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

2593

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

2593

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

2593

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

2593

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

2593

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

17905

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

17905

(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

17884

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)

17898

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

17884

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

17898

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>`, :ref:`ptrtoint <i_ptrtoint>` and
+:ref:`icmp <i_icmp>` return a valid result.
+This explains code motion of these instructions across operations that
+impact the object's lifetime.
+A stack object's lifetime can be explicitly specified using
+:ref:`llvm.lifetime.start <_int_lifestart>` and
+:ref:`llvm.lifetime.end <_int_lifeend>` intrinsic function calls.
+
 .. _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
 to the following rules:
 
 -  A pointer value is associated with the addresses associated with any
    value it is *based* on.
 -  An address of a global variable is associated with the address range
    of the variable's storage.
 -  The result value of an allocation instruction is associated with the

 
 
 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 a stack-allocated object and its offset is zero, the object is
+initially marked as dead.
+After '``llvm.lifetime.start``', the stack object that ``ptr`` points is marked
+as alive and has an uninitialized value.
+The stack object is marked as dead 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.
+The second '``llvm.lifetime.start``' call marks the object as alive, but it
+does not change the address of the object.
+
+If ``ptr`` is a non-stack-allocated object, its offset is non-zero or it is
+a stack object that is already alive, it simply fills all bytes of the object
+with ``poison``.
+
 
 .. _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 a stack-allocated object and its offset is zero, the object is
+dead.
+Calling ``llvm.lifetime.end`` on an already dead alloca is no-op.
+
+If ``ptr`` is a non-stack-allocated object or its offset is non-zero,
+it is equivalent to simply filling all bytes of the object with ``poison``.
+
 
 '``llvm.invariant.start``' Intrinsic
 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
 
 Syntax:
 """""""
 This is an overloaded intrinsic. The memory object can belong to any address space.