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

Tue Nov 16 20:44:58 PST 2021

I'm not convinced that this is the way to go either.

The notion of capture is still mostly an implementation detail of LLVM's alias analysis. It boils down to the fact whether the current implementation can keep track of all aliases of the pointer. We do have a section about pointer capture in the LangRef (https://llvm.org/docs/LangRef.html#pointer-capture), but it is specific to nocapture attribute on calls. It is defined by explicitly prohibiting specific operations on the pointer within the function.

I find proposed definition of nocapture_store metadata rather vague. From https://reviews.llvm.org/D93189:
"the pointer stored is not captured in the sense that all uses of the pointer are explicitly marked otherwise and the storing can be ignored during capture analysis".

This definition makes lax use of the term "capture". This term is only defined in the LangRef with respect to pointers and calls.
It refers to "capture analysis" which is an implementation detail of LLVM's alias analysis and not defined anywhere.
It also says "all uses of the pointer are explicitly marked otherwise". The proposed way of marking the uses is the nocapture_use operand bundle. So, essentially, the only way a "nocapture stored" pointer can be used today is in a call (this is because today we can only attach operand bundles to calls and invokes). This is very limiting.

This limitation can be lifted if we introduce operand bundles on arbitrary instructions. Assuming we do that, the definition above suggests that we need to mark *all* uses of the "nocapture stored" pointers. It means every single instruction, including geps, bitcasts, etc. need to bear this operand bundle. This looks verbose and fragile. Every transform now needs to preserve this marking, otherwise risking a miscompile.

Speaking of possible alternatives, we can probably define "nocapture storage" as memory that doesn't outlive the scope of the current function (it should probably have some other name, because it doesn't rely on term capture). Having this property we can extend capture tracking with flow-insensitive analysis to keep track of pointers stored into "nocapture storage".

The other alternative that was suggested previously was to explicitly mark aliasing properties in the IR similarly to (or using) noalias and alias.scope metadata.

Artur

On Nov 8, 2021, at 2:53 PM, Johannes Doerfert via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote:

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

--
───────────────────
∽ Johannes (he/his)

_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20211117/ef452f57/attachment.html>