llvm dev - Aug 2021 - Conditional references between globals in LLVM IR

On 2021-08-17, Kuba Mracek via llvm-dev wrote:
>I don't see how comdats solve this problem, unless you're suggesting
to extend them somehow beyond how they work today? Or could you try to show how
my example would look like with comdats?
>
>Maybe I'm missing something, but if I put @a, @b and @assoc in a single
comdat then the behavior I get is that if anything references @a or @b, then the
whole group is retained. That's not what I'm looking for -- I need to
somehow be able to drop @assoc if only @a or only @b is referenced, but keep it
if both are referenced.
>
>Also note that in my example, nothing is referencing @assoc -- the only
thing keeping it alive is @llvm.used. So if I put @assoc in a separate comdat,
it's going to be trivially dropped.
>
>Kuba
>
>> On Aug 17, 2021, at 9:51 AM, Reid Kleckner <rnk at google.com>
wrote:
>>
>> Can this be expressed with comdat groups? I believe GlobalDCE should
already handle those in the way that you want: if any member is referenced, the
whole group is retained, if no members are referenced, the whole group is
dropped.
>>
>> There is a slight wrinkle that MachO doesn't support comdats, but
that is the IR feature that we use to express this idea.
>>
>> On Mon, Aug 16, 2021 at 5:27 PM Kuba Mracek via llvm-dev <llvm-dev
at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>> Hi llvm-dev!
>>
>> I'm trying to add dead-stripability of types into the Swift
compiler, and for that I need some new affordance in the LLVM IR to be able to
express the condition that says "this global can be removed if either of
these other globals are removable" -- for a concrete example see below. As
pcc has pointed out to me, we already have a !associated metadata, and what
I'm looking for is basically a generalization of this concept.
>>
>>   @a = internal global i32 1
>>   @b = internal global i32 2
>>   @assoc = internal global [2 x i32*] { i32* @a, i32* @b } !1
>>
>>   ... other code here possibly using or not using @a and @b ...
>>
>>   ; Somehow I want to express that the references from @assoc to @a and
@b are not to be taken into account
>>   ; when doing global liveness analysis, and presence of @assoc in
@llvm.used and @llvm.compiler.used should
>>   ; be ignored as well. Instead the references from @assoc to @a and @b
are conceptually supposed to be "weak"
>>   ; references that will not keep targets alive if there are no
"strong" (regular) references. And if either @a or @b
>>   ; (or both) do get removed, then @assoc should also be removed.
>>   !1 = !{ ... }
>>
>>   ; We need to mention @assoc in @llvm.used or @llvm.compiler.used,
otherwise @assoc is trivially removable.
>>   @llvm.used = appending global [...] { @assoc }
There is an unusual condition: "if either @a or @b (or both) do get
removed, then @assoc should also be removed."

If @assoc is to be retained if either @a or @b is live at link time, this dead
stripping relation can be expressed via Mach-O S_ATTR_LIVE_SUPPORT.

(
The existing !associated can not express many-to-one relationship.
(https://reviews.llvm.org/D97430 is such a (complex) case.)

For ELF, we can use R_*_NONE relocations to express such many-to-one
relationship.
There is no LLVM IR feature expressing this yet.
)

I don't think any linker feature in PE/COFF, ELF, or Mach-O can express the
desiged garbage collection (dead stripping) semantics for the generic case.
>> This example above basically shows the situation of Swift's
Protocol Conformance Records, which don't have any incoming static
references and instead they are scanned and processed by the runtime (by looking
those records up via APIs from the dynamic linker), so they need the @llvm.used
marker to survive into the final binary. They reference two other globals, a
type record and a protocol record, which means that today they actually keep
both the type and the protocol alive transitively, and therefore prohibit
dead-stripping of those. So practically, the @llvm.used marker is necessary but
also too conservative at the same time, and I want to relax removal rules on
these globals -- specifically these Protocol Conformance Records and some other
records in similar situations.
Can you give more information why Swift needs this unusual garbage collection
behavior?

When @a is retained while @b is dropped, what is the @assoc content supposed to
be (a) when the compiler generates the object file and (b) when the linker
performs section based garbage collection (dead stripping)?
>> What I'm looking for is 1) a design for how to represent this in
LLVM IR, 2) and an implementation in GlobalDCE that would actually follow these
rules and remove globals whenever allowed. For the latter, me and Manman have
prepared a patch, see <https://reviews.llvm.org/D104496
<https://reviews.llvm.org/D104496>>, which does the job by adding a new
specially named metadata -- !llvm.used.conditional -- that has a specific
structure that can express these "conditionally used globals". But
mainly I'd like to figure out the former -- what should this look like in
the IR. Should we try to extend the existing !associated metadata? If yes, can
we teach GlobalDCE to optimize based on !associated markers? Should we have a
list like !llvm.used.conditional instead? Should it subsume !associated metadata
and replace it?
>>
>> Thanks ahead for any feedback!
>>
>> Kuba

> On Aug 17, 2021, at 11:32 AM, Fangrui Song <maskray at google.com>
wrote:
> 
> On 2021-08-17, Kuba Mracek via llvm-dev wrote:
>> I don't see how comdats solve this problem, unless you're
suggesting to extend them somehow beyond how they work today? Or could you try
to show how my example would look like with comdats?
>> 
>> Maybe I'm missing something, but if I put @a, @b and @assoc in a
single comdat then the behavior I get is that if anything references @a or @b,
then the whole group is retained. That's not what I'm looking for -- I
need to somehow be able to drop @assoc if only @a or only @b is referenced, but
keep it if both are referenced.
>> 
>> Also note that in my example, nothing is referencing @assoc -- the only
thing keeping it alive is @llvm.used. So if I put @assoc in a separate comdat,
it's going to be trivially dropped.
>> 
>> Kuba
>> 
>>> On Aug 17, 2021, at 9:51 AM, Reid Kleckner <rnk at
google.com> wrote:
>>> 
>>> Can this be expressed with comdat groups? I believe GlobalDCE
should already handle those in the way that you want: if any member is
referenced, the whole group is retained, if no members are referenced, the whole
group is dropped.
>>> 
>>> There is a slight wrinkle that MachO doesn't support comdats,
but that is the IR feature that we use to express this idea.
>>> 
>>> On Mon, Aug 16, 2021 at 5:27 PM Kuba Mracek via llvm-dev
<llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
<mailto:llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>>> wrote:
>>> Hi llvm-dev!
>>> 
>>> I'm trying to add dead-stripability of types into the Swift
compiler, and for that I need some new affordance in the LLVM IR to be able to
express the condition that says "this global can be removed if either of
these other globals are removable" -- for a concrete example see below. As
pcc has pointed out to me, we already have a !associated metadata, and what
I'm looking for is basically a generalization of this concept.
>>> 
>>>  @a = internal global i32 1
>>>  @b = internal global i32 2
>>>  @assoc = internal global [2 x i32*] { i32* @a, i32* @b } !1
>>> 
>>>  ... other code here possibly using or not using @a and @b ...
>>> 
>>>  ; Somehow I want to express that the references from @assoc to @a
and @b are not to be taken into account
>>>  ; when doing global liveness analysis, and presence of @assoc in
@llvm.used and @llvm.compiler.used should
>>>  ; be ignored as well. Instead the references from @assoc to @a and
@b are conceptually supposed to be "weak"
>>>  ; references that will not keep targets alive if there are no
"strong" (regular) references. And if either @a or @b
>>>  ; (or both) do get removed, then @assoc should also be removed.
>>>  !1 = !{ ... }
>>> 
>>>  ; We need to mention @assoc in @llvm.used or @llvm.compiler.used,
otherwise @assoc is trivially removable.
>>>  @llvm.used = appending global [...] { @assoc }
> 
> There is an unusual condition: "if either @a or @b (or both) do get
removed, then @assoc should also be removed."
> 
> If @assoc is to be retained if either @a or @b is live at link time, this
dead
> stripping relation can be expressed via Mach-O S_ATTR_LIVE_SUPPORT.
That I'm afraid is not accurate -- I believe the Mach-O support for
S_ATTR_LIVE_SUPPORT at least in ld64 is limited to a single reference per
global.
> 
> (
> The existing !associated can not express many-to-one relationship.
> (https://reviews.llvm.org/D97430 <https://reviews.llvm.org/D97430> is
such a (complex) case.)
> 
> For ELF, we can use R_*_NONE relocations to express such many-to-one
relationship.
> There is no LLVM IR feature expressing this yet.
> )
> 
> I don't think any linker feature in PE/COFF, ELF, or Mach-O can express
the
> desiged garbage collection (dead stripping) semantics for the generic case.
And I'm fine with that. I don't need this information to survive into
object files, I'm okay to rely on GlobalDCE (on a translation-unit level, or
on an LTO unit with LTO enabled) to do the work only on IR.
> 
>>> This example above basically shows the situation of Swift's
Protocol Conformance Records, which don't have any incoming static
references and instead they are scanned and processed by the runtime (by looking
those records up via APIs from the dynamic linker), so they need the @llvm.used
marker to survive into the final binary. They reference two other globals, a
type record and a protocol record, which means that today they actually keep
both the type and the protocol alive transitively, and therefore prohibit
dead-stripping of those. So practically, the @llvm.used marker is necessary but
also too conservative at the same time, and I want to relax removal rules on
these globals -- specifically these Protocol Conformance Records and some other
records in similar situations.
> 
> Can you give more information why Swift needs this unusual garbage
collection
> behavior?
To allow effective dead stripping: When a particular type/protocol defined in
user's code is not actually used, I want that type/protocol and all the code
that comes with it to be removed / removable by the optimizer. Today, these
Protocol Conformance Records act as liveness roots that prohibit removal of
classes/structs/protocols because they actually reference them.
> When @a is retained while @b is dropped, what is the @assoc content
supposed to
> be (a) when the compiler generates the object file and (b) when the linker
> performs section based garbage collection (dead stripping)?
If @b is dropped, @assoc should be dropped as well.

What should the linker do (or what should its inputs be) is somewhat orthogonal
-- I assume none of the existing object file format can express the semantics,
so we could just be conservative and lower the globals into something that not
going to be efficient but won't eliminate any globals that it shouldn't.
> 
>>> What I'm looking for is 1) a design for how to represent this
in LLVM IR, 2) and an implementation in GlobalDCE that would actually follow
these rules and remove globals whenever allowed. For the latter, me and Manman
have prepared a patch, see <https://reviews.llvm.org/D104496
<https://reviews.llvm.org/D104496><https://reviews.llvm.org/D104496
<https://reviews.llvm.org/D104496>>>, which does the job by adding a
new specially named metadata -- !llvm.used.conditional -- that has a specific
structure that can express these "conditionally used globals". But
mainly I'd like to figure out the former -- what should this look like in
the IR. Should we try to extend the existing !associated metadata? If yes, can
we teach GlobalDCE to optimize based on !associated markers? Should we have a
list like !llvm.used.conditional instead? Should it subsume !associated metadata
and replace it?
>>> 
>>> Thanks ahead for any feedback!
>>> 
>>> Kuba
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20210817/6b59dd06/attachment.html>