[LangRef] clarify the semantics of nocapture

[aqjune]

Summary

This patch clarifies the semantics of nocapture attribute.

A 'Pointer Capture' subsection is added to describe the semantics of pointer capture first.

For the nocapture example with two same pointer arguments, it is consistent with the semantics that Alive2 used to run lit tests.

[aqjune]

Minor updates

[jdoerfert]

I would not interchange "capture" and "escape" in the text, it doesn't help. Stick with capture.

The volatile stuff should go in the pointer capture section.

llvm/docs/LangRef.rst

2674

I don't really like this text too much. Storing is only one way and I'm not sure why we need to talk about non-integral pointers at all.

@reames and me recently started a write up to define "capture", maybe we should share that.

2679

The first thing is not true, e.g., it ignores ptr2int.

2685

I honestly don't understand this. For me, the beginning reads like: "If the pointer is nocapture it is captured when ...." which is at least odd. I assume you want to say that nocapture applies to the use and not the value, if so, let's do that more explicitly.

[reames]

Johannes, Artur, and I have recently spent quite a bit of time discussing the definition of capture offline. I haven't yet read your proposed text - I will shortly - but I wanted to share our progress.

The most recent version of my draft proposal can be found at https://github.com/preames/public-notes/blob/master/defining-capture.rst. This writeup is based on discussion w/Johannes and Artur, but I haven't yet had a chance to get their input on the draft. As such, all mistakes are mine. :)

This is our second major attempt. The previous version, which can be found at https://github.com/preames/public-notes/blob/master/defining-escape.rst, ended up not working out and we had to go back to the drawing board.

[reames]

Now having read the text, and responding to the review.

The definition you're using appears to be in terms of the set of locations which can possibly refer to the object. The problem is that if any element of that set is itself captured, then your object is captured. This is the root confusion which made me realize we need to have a global definition of capture which isn't purely set based.

Reading through your definition, there's a subtlety to the nocapture argument attribute which is tricky. The attribute doesn't simply state that the callee doesn't contain a capturing operation (using the candidate definitions from previously linked document), it also says that pointer isn't propagated into any non-capturing, but unknown to the caller additional location. That's an important detail, and not one we want to loose.

I think we can combine the global definition of capture (as per the previously linked document) and your set based formalism. Let me take a shot.

If we have an object which has not yet been captured passed to a nocapture argument of a function, we know that the object remains uncaptured after the call. Additionally, we also know that the callee hasn't increased the number of locations in which references to the object can be observed after the call. Thus, if the caller can precisely enumerate said set before the call, that said remains precise after the call completes.

What do you think?

(Anyone reading along is probably better off look at https://github.com/preames/public-notes/blob/master/defining-capture.rst#nocapture-argument-attribute. That incorporates a couple of fixes I noticed after first posting this.)

[nlopes]

If we have an object which has not yet been captured passed to a nocapture argument of a function, we know that the object remains uncaptured after the call. Additionally, we also know that the callee hasn't increased the number of locations in which references to the object can be observed after the call. Thus, if the caller can precisely enumerate said set before the call, that said remains precise after the call completes.

You are hinting at a more dynamic semantics, while we're proposing a more syntactic one.
Consider this example:

f(nocapture p) {
  p2 = load glb
  ret p2
}

According to your definition, this functions triggers UB if p2 == p, because it increases the number of observations of p. It's counter-intuitive to me that a function that doesn't touch its nocapture argument captures that argument.

Another case is this:

f(nocapture p, q) {
  glb = g
}

Similarly, this function would trigger UB if p == q. This contrasts with how other attributes work. For example, if a pointer is readonly we can't write through it, but we can still write to the object provided we have another non-readonly pointer to it.

We've been thinking along these lines:

• a function cannot return a pointer tagged as nocapture
• on return, the memory cannot have any nocapture-tagged pointer stored in captured objects, global objects, or objects passed as arguments

It's a more syntactic view than what you are proposing, but I think it's more in line with the other attributes.

[jdoerfert]

I think we have to stick to a pointer-based definition not an object one. However, we should describe it holistically, which this patch does in parts.

The key idea is, IMO, that if I have a pointer p and I pass it as an argument to a function f, will any bits of p become "public knowledge" through the call.
That is, if I pick random bits for p (thereby eliminating aliases), would they be available after the call (to the executing thread or another thread).

This definition is born out of the use cases I know of for nocapture which basically ask if I can freely change the bits of the pointer without disturbing anything, e.g., move heap to stack.
One note: Most of the time, nocapture is really only interesting if you have a "noalias" (or function identified) pointer, that means, it is often useful at the call site, not inside the callee.

What I want to avoid (not to say this patch doesn't!) is to define temporary storage necessarily captures. For me "capturing" is making the bits available after the call, not the fact of storing it.
So if you have some memory not accessible by others, put your pointer in there, and then you take it out before you return, all is good. Some examples: https://clang.godbolt.org/z/P1d7rG

[nlopes]

In D97924#2607361, @jdoerfert wrote:

// G is only used in this function and always written first, no leakage!
static int *G;
void noescape1(int *p) {
    int q;
    G = cond() ? p : &q;
    *G = 3;
}

I agree with all your examples except this one. The remaining examples are easy to justify because they store pointers to local memory that is not escaped, so those pointers don't escape either.
This example I think is better handled in two separate phases: one that removes global variables (your example's global variable can be removed easily). Then we have a cheap escape analysis that shouldn't worry with those "fake" escapes because they've been removed already.
We just need a definition of capture that is precise enough for the kind of escape analysis we want to implement. The case above seems a bit artificial.

[reames]

In D97924#2607261, @nlopes wrote:

If we have an object which has not yet been captured passed to a nocapture argument of a function, we know that the object remains uncaptured after the call. Additionally, we also know that the callee hasn't increased the number of locations in which references to the object can be observed after the call. Thus, if the caller can precisely enumerate said set before the call, that said remains precise after the call completes.

You are hinting at a more dynamic semantics, while we're proposing a more syntactic one.

Yes I am, and I think that's important. Its worth noting that every syntactic definition has a corresponding dynamic version, but having the dynamic one be simple and easy to understand is important.

Key reasons:

1. I personally have a hard time understanding syntactic definitions. Normally, I'd hesitate to insert my personal preferences so strongly, but as one of the people who has historical fixed bugs in this area, this actually an important point.
2. My experience is that the dynamic definitions are easier to explain.
3. Dynamic definitions are easier to test. In particular, the map themselves well to a collection of test cases and even sanitizers. I think the last point (sanitizers) is actually quite important because as we become more aggressive about optimizing based on capture semantics I expect we'll find existing frontend bugs in usage.

Consider this example:

f(nocapture p) {
  p2 = load glb
  ret p2
}

According to your definition, this functions triggers UB if p2 == p, because it increases the number of observations of p. It's counter-intuitive to me that a function that doesn't touch its nocapture argument captures that argument.

I agree, this is slightly counter intuitive. I think it's also fundamentally necessary.

One of the key optimization properties we want is that a nocapture *and trackable* pointer remains nocapture *and trackable* after being passed to a nocapture argument. Given we don't have a way to describe in current langref the newly created copy, we must consider this a violation of the existing nocapture parameter property.

Note the distinction in my wording between nocapture and "trackable". The existing nocapture attribute mixes two related, but distinct, properties.

Another case is this:

f(nocapture p, q) {
  glb = g
}

Similarly, this function would trigger UB if p == q. This contrasts with how other attributes work. For example, if a pointer is readonly we can't write through it, but we can still write to the object provided we have another non-readonly pointer to it.

I think for this example, you're looking at the stale wording from the review rather than the updated version in the linked to document. I agree we want pointer properties, not object ones, and attempted to address that in the wording. Does the new wording match what you'd expect?

The "trackability" part my current definition for the argument attribute does seem more object based, and I agree that needs some word smithing. I'm not arguing in favor of an object semantics here, it simply happens to be the way my brain processes this stuff and it tends to slide into my wording if I'm not careful.

We've been thinking along these lines:

• a function cannot return a pointer tagged as nocapture
• on return, the memory cannot have any nocapture-tagged pointer stored in captured objects, global objects, or objects passed as arguments

It's a more syntactic view than what you are proposing, but I think it's more in line with the other attributes.

I'll just point out that with this definition, we still need to define what a captured object is. That's the root point I'm trying to get defined, everything else builds on top.

[reames]

JFYI, updated my candidate text for nocapture parameter attribute to try to clarify points raised in last round of response. (https://github.com/preames/public-notes/blob/master/defining-capture.rst#nocapture-argument-attribute)

[jdoerfert]

In D97924#2611088, @nlopes wrote:

We just need a definition of capture that is precise enough for the kind of escape analysis we want to implement. The case above seems a bit artificial.

Artificial, sure. Though, OpenMP GPU runtime as very similar situations, e.g., internal globals we see all uses.
That said, I agree with your statement we want to "optimize" this in two steps, nevertheless, conceptually I'd hope we would not define this a capture even if the global is not demoted to stack.

Some thoughts on other topics discussed here:

dynamic vs static semantic

I doubt we can explain the examples I presented reasonably in a purely static manner. It's a dynamic property for me.

nocapture & trackable

 f(nocapture p) {
 p2 = load glb
 ret p2
}

I do not think the example should cause UB if p == p2. The argument that we want to keep "track of" p and nocapture is a way to ensure we can is in principle valid, however, if p2 can be p, we either lost track of it already or we should have tracked the uses of glb. Either way, nocapture helps us to keep track of the argument without the UB requirement here while it is up to the caller to keep track of the value being passed before the call. Said differently, nocapture uses do not require you to track additional value/location but nocapture is not an object property and other uses/locations have to be tracked separately.

[nlopes]

In D97924#2611453, @reames wrote:

In D97924#2607261, @nlopes wrote:

Consider this example:

f(nocapture p) {
  p2 = load glb
  ret p2
}

According to your definition, this functions triggers UB if p2 == p, because it increases the number of observations of p. It's counter-intuitive to me that a function that doesn't touch its nocapture argument captures that argument.

I agree, this is slightly counter intuitive. I think it's also fundamentally necessary.

Can you expand why you think this is fundamental?
This semantics makes it very hard for an analysis to tag a parameter as nocapture. if a function stores a pointer to memory or returns a pointer it may be capturing any of the parameters, who knows.

More fundamentally, for optimization I think we only care about 2 cases:

• An object hasn't escaped
• An object escaped

The number of references to an escaped object doesn't matter. What we care about is when it flips from non-escaped to escaped.

What are the uses of nocapture information? It's used when traversing a function and analyze call sites. We want to know if a given locally-allocated object can be modified by a callee. If not, we can do all sorts of store forwarding, know that the object is still alive, etc.
So if a pointer is already escaped, we gain no information about the existence of further escapes. What we want is the flip. Hence I don't see how the semantics above are useful for this purpose.

If we have a function with 2 arguments;

 f(p, q) {
    g = p
}

We want to be able to say that q doesn't escape regardless of whether p=q or not. Otherwise I feel we will never be able to infer this noescape attribute.

[nlopes]

@aqjune ping: there are a few sentences that need tweaking.

llvm/docs/LangRef.rst

2674

agreed. this non-integral pointer text isn't very readable to me either.

[aqjune]

Address comments, add a few examples

[aqjune]

I updated this patch to address comments & added a few examples that I concern.
The examples and added sentences are mainly to represent this, because I also agree with this interpretation:

The key idea is, IMO, that if I have a pointer p and I pass it as an argument to a function f, will any bits of p become "public knowledge" through the call.
That is, if I pick random bits for p (thereby eliminating aliases), would they be available after the call (to the executing thread or another thread).

I hope this helps check whether my understanding about pointer capture is correct.

llvm/docs/LangRef.rst

1206

I moved the volatile thing to the new section.

2679

Thank you. For correctness & clarity, I removed the paragraph.

2685

Yes, your understanding is right. I added a relevant example with nocapture at the nocapture paragraph.

[nlopes]

llvm/docs/LangRef.rst

2673

let's make it explicit the pointer only escapes if that information is readable by the caller after the function exits. To account for the fact that information can be overwritten.
Maybe complement the example below to have something like:

store i32 %j, i32* @glb ; escapes %a
store i32 0, i32* @glb ; %a is not escaped anymore

[reames]

Minor comments, this looks like it's evolved into a reasonable step forward. As things stand, I think this should go in with some minor stuff fixed, and we can iterate on details in further patches. This is already better than what we have now. :)

llvm/docs/LangRef.rst

1206

I suggest tweaking this wording slightly. Specifically:

"This attribute applies only to the particular copy of the pointer passed in this argument. A caller could pass two copies of the same pointer with one being annotated nocapture and the other not, and the callee could validly capture through the non annotated parameter.

(Great example btw.)

2673

JFYI, this example is very subtle and possibly misleading. It's only correct since both stores are non-atomic.

If there was another threading reading from @glb, then it could capture the value of %a between the two stores.

However, that would require a race which would be UB (since the stores aren't atomic) and thus we can ignore it.

Importantly, if there was any ordering operation between the two stores it might capture, even with non-atomic stores.

2702

Looks like this should be 3).

2735

You should add an item about the inspection by another thread case.

(This case gets subtle and complicated fast. I'd suggest using deliberately hand wavy wording to start with and refining that in a follow up patch.)

[aqjune]

Address comments, updates

[aqjune]

Here are updates:

1. I found from this document that pointer escape is different from pointer capture; pointer capture subsumes pointer escape. I chose pointer capture because we're talking about general cases regardless of dereferenceability. I also adopted this expression from the link: A pointer value is captured if the function makes a copy of any part of the pointer that outlives the call This naturally addressed Nuno's concern.
2. An example that uses an atomic operation is added.
3. Updated wordings, added numbering to the volatile case

[aqjune]

replace remaining escape with capture

[aqjune]

llvm/docs/LangRef.rst

2691

To clarify the case when @f calls another function, I added this.
If @g does not capture pointer (e.g. readnone & willreturn), calling @g is fine.
Does this make sense & is consistent with people's understanding?

[nlopes]

It looks great to me!

@reames any further comments/suggestions?

[reames]

Looks good to me as well.

[aqjune]

Thank you all for reviewing this!

[jdoerfert]

llvm/docs/LangRef.rst

2675

It is not the caller that needs to be able to read the bits, but any thread. This is a difference.

Also, I'm still not happy about "storing". We should at least clarify that there doesn't need to be a store instruction of any kind. The important point is that no bit is communicated from inside the function to the outside or another thread.

2698

This is arguably a capture but not a store.

2726

exit is probably not perfect, maybe just set a flag.

[aqjune]

llvm/docs/LangRef.rst

2675

Hi,

It is not the caller that needs to be able to read the bits, but any thread. This is a difference.

I think the second item in the text addresses this issue. :)

Also, I'm still not happy about "storing". We should at least clarify that there doesn't need to be a store instruction of any kind.

I was thinking the information can be stored to either a register or a memory location which are encompassed in the word 'place'.
Do you have any suggestion for other word?

2726

I'll update this in the post-review commit.

llvm/docs/LangRef.rst

``noalias``
     For function return values, C99's ``restrict`` is not meaningful,
     while LLVM's ``noalias`` is. Furthermore, the semantics of the ``noalias``
     attribute on return values are stronger than the semantics of the attribute
     when used on function arguments. On function return values, the ``noalias``
     attribute indicates that the function acts like a system memory allocation
     function, returning a pointer to allocated storage disjoint from the
     storage for any other object accessible to the caller.
 
+.. _nocapture:
+
 ``nocapture``
-    This indicates that the callee does not make any copies of the
-    pointer that outlive the callee itself in any form such as a pointer stored
-    in the memory or as a return value. This is not a valid
-    attribute for return values.  Addresses used in volatile operations
-    are considered to be captured.
+    This indicates that the callee does not :ref:`capture <pointerescape>` the
+    pointer. This is not a valid attribute for return values.
+    This attribute applies only to the particular copy of the pointer passed in
+    this argument. A caller could pass two copies of the same pointer with one
+    being annotated nocapture and the other not, and the callee could validly
+    capture through the non annotated parameter.
+
+.. code-block:: llvm
+
+    define void @f(i8* nocapture %a, i8* %b) {
+      ; (escape %b)
+    }
+
+    call void @f(i8* @glb, i8* @glb) ; well-defined
 
 ``nofree``
     This indicates that callee does not free the pointer argument. This is not
     a valid attribute for return values.
 
 .. _nest:
 
 ``nest``

 alignment of the store.
 
 Consequently, type-based alias analysis, aka TBAA, aka
 ``-fstrict-aliasing``, is not applicable to general unadorned LLVM IR.
 :ref:`Metadata <metadata>` may be used to encode additional information
 which specialized optimization passes may use to implement type-based
 alias analysis.
 
+.. _pointerescape:
+
+Pointer Capture
+---------------
+
+Given a function call and a pointer that is passed as an argument or stored in
+the memory before the call, a pointer is *captured* by the call if it makes a
+copy of any part of the pointer that outlives the call.
+To be precise, a pointer is captured if one or more of the following conditions
+hold:
+
+1. The call stores any bit of the pointer carrying information into a place,
+and the stored bits can be read from the place by the caller after this call
+exits.
+
+.. code-block:: llvm
+
+    @glb  = global i8* null
+    @glb2 = global i8* null
+    @glb3 = global i8* null
+    @glbi = global i32 0
+
+    define i8* @f(i8* %a, i8* %b, i8* %c, i8* %d, i8* %e) {
+      store i8* %a, i8** @glb ; %a is captured by this call
+
+      store i8* %b,   i8** @glb2 ; %b isn't captured because the stored value is overwritten by the store below
+      store i8* null, i8** @glb2
+
+      store i8* %c,   i8** @glb3
+      call void @g() ; If @g makes a copy of %c that outlives this call (@f), %c is captured
+      store i8* null, i8** @glb3
+
+      %i = ptrtoint i8* %d to i64
+      %j = trunc i64 %i to i32
+      store i32 %j, i32* @glbi ; %d is captured
+
+      ret i8* %e ; %e is captured
+    }
+
+2. The call stores any bit of the pointer carrying information into a place,
+and the stored bits can be safely read from the place by another thread via
+synchronization.
+
+.. code-block:: llvm
+
+    @lock = global i1 true
+
+    define void @f(i8* %a) {
+      store i8* %a, i8** @glb
+      store atomic i1 false, i1* @lock release ; %a is captured because another
+thread can safely read @glb
+      store i8* null, i8** @glb
+      ret void
+    }
+
+3. The call's behavior depends on any bit of the pointer carrying information.
+
+.. code-block:: llvm
+
+    @glb  = global i8 0
+    define void @f(i8* %a) {
+      %c = icmp eq i8* %a, @glb
+      br i1 %c, BB_EXIT, BB_CONTINUE ; escapes %a
+    BB_EXIT:
+      call void exit()
+      unreachable
+    BB_CONTINUE:
+      ret void
+    }
+
+4. The pointer is used in a volatile access as its address.
+
+
 .. _volatile:
 
 Volatile Memory Accesses
 ------------------------
 
 Certain memory accesses, such as :ref:`load <i_load>`'s,
 :ref:`store <i_store>`'s, and :ref:`llvm.memcpy <int_memcpy>`'s may be
 marked ``volatile``. The optimizers must not change the number of
 volatile operations or change their order of execution relative to other