This is an archive of the discontinued LLVM Phabricator instance.

[GlobalDCE] Support of conditionally used global variables
Needs ReviewPublic

Authored by kubamracek on Jun 17 2021, 4:53 PM.

Details

Summary

As part of the optimization work to emit dead-strippable symbols for Swift and enable GlobalDCE to remove those symbols when possible, we need to mark some Swift symbols as conditionally used based on a set of other symbols. Some background info can be found here: https://bugs.swift.org/browse/SR-14509.

We are proposing to add a module-level name metadata llvm.used.conditional. It contains a list of metadata triplets. Each triplet has the following form:

  • The first element is the global variable from llvm.used that we are conditionally mark it as used.
  • The second element is a boolean flag. 1 means when all GVs in the third element are alive, mark the first element as used. 0 means when any GV in the third element is alive, mark the first element as used.
  • The third element is a list of GVs.

One example use case is for Swift protocol conformance data, we want to mark them as conditionally used, depending on the protocol descriptor and the nominal type descriptor. During GlobalDCE, we separate out the entries that are in llvm.used and also in llvm.used.conditional as the first element. We iteratively mark entries in this set as used by checking the GVs in the third element according to the flag in the second element. When one entry is marked as used, it can trigger other entries to be alive.

We are open to other alternatives to express this conditional usage.

The patch is based on initial patch from Kuba + some clean up. Testing cases will be added if this is the right approach to move forward.

Diff Detail

Event Timeline

manmanren created this revision.Jun 17 2021, 4:53 PM
manmanren requested review of this revision.Jun 17 2021, 4:53 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 17 2021, 4:53 PM
manmanren edited the summary of this revision. (Show Details)Jun 17 2021, 5:03 PM
manmanren edited subscribers, added: kubamracek; removed: llvm-commits, hiraditya, ormris.
lebedev.ri retitled this revision from Support of conditionally used global variables to [GlobalDCE] Support of conditionally used global variables.Jun 18 2021, 5:08 AM
lebedev.ri added a subscriber: lebedev.ri.

Tests missing

kubamracek commandeered this revision.Aug 5 2021, 1:12 PM
kubamracek added a reviewer: manmanren.

Commandeering this to upload a new diff with added tests. Manman, feel free to commandeer it back :)

kubamracek updated this revision to Diff 364595.Aug 5 2021, 1:12 PM
kubamracek added a reviewer: yln.

Adding tests that, also they showcase how the llvm.used.conditional works in practice.

kubamracek updated this revision to Diff 365317.Aug 9 2021, 4:50 PM

Adding another test.

pcc added a comment.Aug 9 2021, 5:33 PM

0 means when any GV in the third element is alive, mark the first element as used.

This sounds like !associated metadata.

1 means when all GVs in the third element are alive, mark the first element as used.

Do you have an example of a use case for this?

1 means when all GVs in the third element are alive, mark the first element as used.

Do you have an example of a use case for this?

The example is Swift's "Protocol Conformance Record" — it's a record that is referencing two things, a type and a protocol. We want to allow discarding this record if *either* the type or the protocol can be discarded.

kubamracek added a reviewer: MaskRay.

@MaskRay, @pcc, @fhahn, this is now ready for review. I've simplified/cleaned up the implementation as much as I could, and added a formalization of the !llvm.used.conditional concept into LangRef.

fhahn added inline comments.Oct 4 2021, 12:38 PM
llvm/docs/LangRef.rst
7346

nit: @llvm.used?

Does the global have to be in @llvm.used or could this requirement be dropped?

7358

I'm not sure if we should add any swift-specific mentions here. If you want to add an example, I'd suggest keeping it very generic with respect to the type names. I'd also only focus on the !llvm.used.conditional part.

llvm/lib/Transforms/IPO/GlobalDCE.cpp
382

this makes sense, but the change should also add llvm.used.conditional verification to the IR verifier. Then we can rely on the entries being valid here.

llvm/lib/Transforms/IPO/GlobalOpt.cpp
2318 ↗(On Diff #376716)

this change and compareNames could be moved to a NFC patch to reduce the size of the diff here.

kubamracek updated this revision to Diff 377014.Oct 4 2021, 1:00 PM
kubamracek added inline comments.
llvm/lib/Transforms/IPO/GlobalOpt.cpp
2318 ↗(On Diff #376716)
kubamracek added inline comments.Oct 4 2021, 1:06 PM
llvm/docs/LangRef.rst
7346

Does the global have to be in @llvm.used or could this requirement be dropped?

The way I'm thinking about it, using !llvm.used.conditional *only makes sense* if the target is also listed in @llvm.used, because the effect of the GlobalDCE optimization is that if the conditions are satisfied, the global is *removed* from @llvm.used.

I think I could add something like "If the global is not in llvm.used, then there is no effect". Would that work?

kubamracek updated this revision to Diff 377016.Oct 4 2021, 1:11 PM
kubamracek updated this revision to Diff 377025.Oct 4 2021, 1:37 PM

Added IR Verifier for llvm.used.conditional.

@MaskRay, @pcc friendly ping on the review request :)

fhahn added a comment.Oct 13 2021, 8:56 AM

Thanks for adding the verifier changes! Do we have a test case with a cycle between target & dependencies in the existing tests?

llvm/lib/IR/Verifier.cpp
843 ↗(On Diff #377025)

Is this intentional?

Removed the leftover debug print. Added a test case for a circular dependency.

kubamracek marked 4 inline comments as done.

I think it'd be good to add a test for llvm/lib/Linker to confirm expected output with symbol merging in LTO (e.g., two linkonce_odr symbols, or a weak and a strong symbol).

  • Linking a defined symbol that has this with an external symbol
  • Linking two weak symbols...
    • if they both have this and it's the same
    • if they both have this and it's different
    • if only one has this
llvm/docs/LangRef.rst
7376–7386

Have you considered using a metadata attachment on @record instead of a global array?

Specifically, I think this would be a simpler schema to reason about and update:

@record = internal global [...] {
  @a, @b
} !llvm.used.conditional !1

@llvm.used = appending global [...] [ ..., @record ]

!1 = !{1, !{@a, @b}}

This schema would not have the flexibility to have multiple list-of-implicit-users assigned to the same global, but IIUC that wouldn't be meaningful anyway. It also wouldn't allow referencing external symbols; also not meaningful I think?
(I haven't looked at the verifier code, but if you stick with the existing schema (and I'm right about what's meaningful), please add verifiers for those two cases.).

You might also consider creating a custom metadata type for this, similar to the debug info metadata. It'd be nice if the IR looked like this instead:

@record = internal global [...] {
  @a, @b
} !llvm.used.conditional !MDImplicitUsers(type: All, users: !{@a, @b})

@llvm.used = appending global [...] [ ..., @record ]

(despite the IR example, this is an independent suggestion of whether you change the schema)

ahti added a subscriber: ahti.Oct 18 2021, 1:42 PM