Johannes Doerfert via llvm-dev
2021-Nov-08 22:53 UTC
[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
--
───────────────────
∽ Johannes (he/his)
Reid Kleckner via llvm-dev
2021-Nov-09 17:02 UTC
[llvm-dev] [RFC] Introduce non-capturing stores [second try]
This seems like a useful feature. I read the comments on the review, and I think the reviewers have a lot more context than I do, but with the limited information I have, tagging stores as in proposal A seems more general. I have previously discussed the problem of how to make SROA work for C++ objects, in particular, std::vector, and I think that's a use case worth considering in your design. The problem with C++ objects is that there is often some out-of-line method (think grow) that blocks SROA by taking the address of the object. Other optimizations such as GVN may do some work to reduce loads and stores to the vector object, but we could probably do more optimizations if a vector looked like three pointers (begin, end, capacity) to the optimizer, rather than a struct in memory. Trying to solve this problem would tend to lead in the direction of option B, where we have a "blessed" alloca that can be used to spill SSA values back to memory in the ABI-expected struct layout when there is register pressure. This is definitely beyond the scope of what you have described here, since `grow` updates vector fields, and they then have to be reloaded as new SSA values. The vector storage can even be captured by special members of the stored object, so "nocapture" is not a good name for this extended feature. The idea is more along the lines of, "here is a pointer SSA value, I have to store it in this ABI-prescribed struct layout, but I'm passing it on the side in a bundle using appropriate aliasing annotations to inform optimizations". I think there is something to this idea, but please don't let me derail your proposal by increasing the scope too much. On Mon, Nov 8, 2021 at 2:53 PM Johannes Doerfert via llvm-dev < 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 > 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/20211109/33a911dd/attachment.html>
Philip Reames via llvm-dev
2021-Nov-15 16:37 UTC
[llvm-dev] [RFC] Introduce non-capturing stores [second try]
Johannes, JFYI, I'm still not convinced of this approach, but also don't have the cycles to engage with this and likely wont for a while. Mentioning this just so you know not to expect feedback from me, and to remove any implicit blockage. Philip On 11/8/21 2:53 PM, Johannes Doerfert via llvm-dev 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 > >
Artur Pilipenko via llvm-dev
2021-Nov-17 04:44 UTC
[llvm-dev] [RFC] Introduce non-capturing stores [second try]
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>
Nuno Lopes via llvm-dev
2021-Nov-22 10:58 UTC
[llvm-dev] [RFC] Introduce non-capturing stores [second try]
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.
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
--
───────────────────
∽ Johannes (he/his)
_______________________________________________
LLVM Developers mailing list
llvm-dev at lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev