Page MenuHomePhabricator

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

Authored by aqjune on Jan 3 2021, 5:07 PM.

Details

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.

Diff Detail

Event Timeline

aqjune requested review of this revision.Jan 3 2021, 5:07 PM
aqjune created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptJan 3 2021, 5:07 PM
aqjune added inline comments.Jan 3 2021, 5:11 PM
llvm/docs/LangRef.rst
17885

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 updated this revision to Diff 314308.Jan 3 2021, 5:12 PM

Minor update

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
2580

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 added inline comments.Jan 4 2021, 5:53 PM
llvm/docs/LangRef.rst
2580

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 added inline comments.Jan 5 2021, 8:00 AM
llvm/docs/LangRef.rst
2580

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 added inline comments.Jan 5 2021, 6:11 PM
llvm/docs/LangRef.rst
2580

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 added inline comments.Jan 5 2021, 6:15 PM
llvm/docs/LangRef.rst
2580

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

aqjune updated this revision to Diff 314768.Jan 5 2021, 6:40 PM

Address comments

aqjune updated this revision to Diff 315295.Jan 7 2021, 9:19 PM

It is memset(undef) in other cases

aqjune added a comment.Jan 7 2021, 9:24 PM

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 added inline comments.Jan 11 2021, 4:12 AM
llvm/docs/LangRef.rst
17892

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 added inline comments.Feb 9 2021, 10:28 PM
llvm/docs/LangRef.rst
17892

(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 updated this revision to Diff 325805.Feb 23 2021, 8:43 AM

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 edited the summary of this revision. (Show Details)Feb 23 2021, 8:44 AM

Adding reviewers who work on backends..

aqjune added a comment.Mar 1 2021, 5:59 AM

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

nlopes accepted this revision.Mar 2 2021, 10:15 AM

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.

This revision is now accepted and ready to land.Mar 2 2021, 10:15 AM
RalfJung added inline comments.Mar 5 2021, 2:57 AM
llvm/docs/LangRef.rst
17871

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)
17885

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 added inline comments.Mar 5 2021, 4:16 AM
llvm/docs/LangRef.rst
17871

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.

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 added a comment.Mar 5 2021, 4:39 AM

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.

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
17885

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*.