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

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 }

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.

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

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

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> 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 }
>
> 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.
>
> 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>, 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
>
> _______________________________________________
> 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/20210817/c1f2d5f6/attachment.html>