[llvm-dev] [RFC] Introduce non-capturing stores [second try]

Mon Nov 29 08:14:12 PST 2021

On 11/22/21 04:58, Nuno Lopes wrote:
> Let me  copy the motivation example given in the previous RFC email:
> ```
> struct Payload {
>     int *a;
>     double *b;
> };
>
> void fn(void *v) {
>     Payload *p = (Payload*)(v);
>     // Load the pointers from the payload and then dereference them,
>     // this will not capture the pointers.
>     int *a = p->a;
>     double *b = p->b;
>     *a = use(*b);
> }
>
> void foo(int *a, double *b) {
>     Payload p = {a, b};
>     pthread_create(..., &fn, &p);
> }
> ```
>
> Makes sense that a & b don't escape.
> Right now they do, but not during the store to p; they only escape at the pthread_create call site. Storing a pointer to an unescaped alloca buffer doesn't escape anything as that memory is not externally observable.
>
> I think this hints at establishing the property you want at call sites, not at allocas or stores. The nocapture attribute is only for the given pointer, while it seems you need a 2-level nocapture (or just recursive, to simplify?).
>
> Unless you have other examples where annotating calls doesn't work, I would go that route instead.

I have examples, basically we can encode what the Attributor can 
determine when it comes to memory.
Examples that involve heap memory, stack memory, and global memory can 
be found here
   https://reviews.llvm.org/D109170#C2805579NL3377
While those mostly show how we can look through memory, when we fail to 
propagate the value we could mark the stores as non-capture (assuming 
they are).

There are two main benefit of marking stores rather than call sites:
   1) If we have call sites we need to first go to the storage from the 
store, which might not be in the same function and therefore really hard 
for non-IPO analysis.
      Once at the storage location we need to traverse all uses again 
until we verify the storage is used only in a certain way. And, which 
plays into this,
   2) We want a system that composes, e.g., store into a local 
allocation which is stored into a heap allocation which is stored into a 
global, but all in all - nothing escapes.

The Attributor can deal with both points above just fine, annotating the 
stores would make the information trivially available to later passes 
and for frontends it would
not make an obvious difference if they annotate stores or call sites (in 
the domain knowledge case).

~ Johannes

>
> Nuno
>
>
> -----Original Message-----
> From: Johannes Doerfert
> Sent: 08 November 2021 22:54
> To: llvm-dev at lists.llvm.org
> Subject: [llvm-dev] [RFC] Introduce non-capturing stores [second try]
>
> NOTE: This was originally send in January 2021 [0]. The rational is still the same,
>         there are two different proposed solutions based on the conversations back then.
>
> TL;DR: A pointer stored in memory is not necessarily captured, let's add a way to express this in IR.
>
>
> --- Rational (copied mostly from [0]) ---
>
> This would solve PR48475.
>
> Runtime functions, as well as regular functions, might require a pointer
> to be passed in memory even though the memory is simply a means to pass
> (multiple) arguments. That is, the indirection through memory is only
> used on the call edge and not otherwise relevant. However, such pointers
> are currently assumed to escape as soon as they are stored in memory
> even if the callee only reloads them and use them in a "non-escaping" way.
> Generally, storing a pointer might not cause it to escape if all "uses of
> the memory" it is stored to all have the "nocapture" property. While the
> Attributor is aware of this and tries to determine all "copies" that the
> store created, other passes are not and frontends cannot provide this
> information for known APIs.
>
> To allow optimizations in the presence of pointers stored to memory we
> introduce *two* IR extensions:
>    Option A) `!nocapture_store` metadata and `"nocapture_use"` operand
>                bundle tags.
>    Option B) `!nocapture_storage` metadata and `"nocapture_use"` operand
>                bundle tags.
> Option A) is what was proposed in [0]. Option B) is slightly different and
> based on the discussions from [0] as well as a prototype patch [2].
>
> Semantics Option A)
> If a store of a pointer is tagged with `!nocapture_store` it guarantees that
> the pointer is not captured by this store. To ensure we still "account" for the
> uses of the pointer once it is reloaded we add the `"nocapture_use"` operand
> bundle tag with the pointer as argument to callees that will interact with the
> pointer loaded from memory.
>
> Semantics Option B)
> If a memory allocation is tagged with `!nocapture_storage` it guarantees that
> stores of a pointer to that memory are not capturing the pointer. To ensure
> we still "account" for the uses of the pointer once it is reloaded we add the
> `"nocapture_use"` operand bundle tag with the pointer as argument to callees
> that will interact with the pointer loaded from memory.
> The difference to Option B) is that we do not tag stores but allocations.
>
>
> --- Previous Discussion ---
>
> The discussion as part of [0] did evolve around a way to handle yet another use case,
> basically what happens if the reloads of the stored away pointer are (partially)
> exposed rather than hidden behind a runtime function interface. The short answer is:
> That is not supported by this RFC alone. The longer answer contains different possible
> extensions to this RFC that would allow us to support such use cases. That said, the
> runtime use case seems relevant enough to be handled first, especially since there is
> no frontend/pass right now (in LLVM) that would rely on any of the extended use cases.
>
>
> --- Proposal ---
>
> Resurrect [1], or make [2] into a proper patch.
> I still think [1] is the way to go as it is more generic and has less lookup cost.
>
> ---
>
> ~ Johannes
>
>
> [0] https://lists.llvm.org/pipermail/llvm-dev/2021-January/147664.html
> [1] https://reviews.llvm.org/D93189
> [2] https://reviews.llvm.org/D109749#3078176
>
>