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

[Johannes Doerfert via llvm-dev]

On 11/9/21 11:02, Reid Kleckner wrote:
> 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.

Can you provide an example for this, some small C++ fragment is fine.
I want to play it through and also compare to a new "similar" idea.

~ Johannes


> 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
>>