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

[Johannes Doerfert via llvm-dev]

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)