[GlobalDCE] Support of conditionally used global variables

[kubamracek]

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.

[lebedev.ri]

Tests missing

[kubamracek]

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

[kubamracek]

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

[kubamracek]

Adding another test.

[pcc]

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?

[kubamracek]

In D104496#2935794, @pcc wrote:

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]

https://lists.llvm.org/pipermail/llvm-dev/2021-August/152183.html

[kubamracek]

https://lists.llvm.org/pipermail/llvm-dev/2021-September/152654.html
https://lists.llvm.org/pipermail/llvm-dev/2021-September/152655.html
https://lists.llvm.org/pipermail/llvm-dev/2021-September/152656.html

[kubamracek]

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

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]

llvm/lib/Transforms/IPO/GlobalOpt.cpp

2318 ↗

(On Diff #376716)

https://reviews.llvm.org/D111096

[kubamracek]

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]

Added IR Verifier for llvm.used.conditional.

[kubamracek]

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

[fhahn]

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?

[kubamracek]

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

[dexonsmith]

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)

llvm/docs/LangRef.rst

 
     !0 = !{!"a library specifier"}
     !1 = !{!"another library specifier"}
     !llvm.dependent-libraries = !{ !0, !1 }
 
 Each library specifier will be handled independently by the consuming linker.
 The effect of the library specifiers are defined by the consuming linker.
 
+.. _llvm_used_conditional:
+
+Conditionally Used Globals
+==========================
+
+When a global variable is mentioned in the `@llvm.used` list, it's always going
+to be retained, but sometimes it's desirable to allow such a global variable to
+still be discardable by optimization passes. Using the `!llvm.used.conditional`
+named metadata allows expressing *when* it is legal to discard a global (from
+the `@llvm.used` list) in terms of liveness of other globals.
+
+If `!llvm.used.conditional` named metadata is present in IR of a module, it's
+expected to be a list of metadata triplets. Each triplet has the following form:
+
+1. The first element is the "target", the global variable from `@llvm.used` that
+   we are allowing removal of. If the global variable is not present in the
+   `@llvm.used` list, then there is no effect from using a entry in
+   `!llvm.used.conditional` for it.
+2. The second element is a "type", a boolean flag expressing what behavior do
+   we want if the list of "dependencies" (third element) contains more than one
+   element. `0` means if *any dependency* in the list is alive, the target symbol
+   must stay alive, otherwise removal is allowed (in other words: if all globals
+   from the dependency list are removed, the target can be removed too). `1`
+   means if *all dependencies* in the list are alive, the target must stay
+   alive, otherwise removal is allowed (in other words: if any global from the
+   dependency list is removed, the target can be removed too).
+3. The third element is a list of "dependencies", a list of globals.
+
+The following example expresses that the global `@record` (which is listed in
+`@llvm.used` otherwise it would be trivially discarded as nothing references it)
+is allowed to be optimized away, if *either of* `@a` or `@b` globals are
+themselves removable::
+
+    @record = internal global [...] {
+        @a, @b
+    }
+    @llvm.used = appending global [...] [ ..., @record ]
+
+    !1 = !{
+        @record,     ; target
+        1,           ; type
+        !{ @a, @b }  ; dependencies
+    }
+    !llvm.used.conditional = !{ !1 }
+
+The semantics of `!llvm.used.conditional` are only *allowing an optimization*,
+and are not requiring optimizations to follow them --- it is correct for any
+optimization/transformation to ignore `!llvm.used.conditional` or even drop it.
+
 .. _summary:
 
 ThinLTO Summary
 ===============
 
 Compiling with `ThinLTO <https://clang.llvm.org/docs/ThinLTO.html>`_
 causes the building of a compact summary of the module that is emitted into
 the bitcode. The summary is emitted into the LLVM assembly and identified

llvm/include/llvm/Transforms/IPO/GlobalDCE.h

private:
 
   // Global variables which are vtables, and which we have enough information
   // about to safely do dead virtual function elimination.
   SmallPtrSet<GlobalValue *, 32> VFESafeVTables;
 
   void UpdateGVDependencies(GlobalValue &GV);
   void MarkLive(GlobalValue &GV,
                 SmallVectorImpl<GlobalValue *> *Updates = nullptr);
+  void PropagateLivenessInGlobalValues();
   bool RemoveUnusedGlobalValue(GlobalValue &GV);
 
   // Dead virtual function elimination.
   void AddVirtualFunctionDependencies(Module &M);
   void ScanVTables(Module &M);
   void ScanTypeCheckedLoadIntrinsics(Module &M);
   void ScanVTableLoad(Function *Caller, Metadata *TypeId, uint64_t CallOffset);
 
   void ComputeDependencies(Value *V, SmallPtrSetImpl<GlobalValue *> &U);
+
+  GlobalValue *TargetFromConditionalUsedIfLive(MDNode *M);
+  void PropagateLivenessToConditionallyUsed(Module &M);
 };
 
 }
 
 #endif // LLVM_TRANSFORMS_IPO_GLOBALDCE_H

llvm/lib/Transforms/IPO/GlobalDCE.cpp

 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Utils/CtorUtils.h"
 #include "llvm/Transforms/Utils/GlobalStatus.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "globaldce"
 
 static cl::opt<bool>
     ClEnableVFE("enable-vfe", cl::Hidden, cl::init(true), cl::ZeroOrMore,
                 cl::desc("Enable virtual function elimination"));
void GlobalDCEPass::MarkLive(GlobalValue &GV,
   if (Comdat *C = GV.getComdat()) {
     for (auto &&CM : make_range(ComdatMembers.equal_range(C))) {
       MarkLive(*CM.second, Updates); // Recursion depth is only two because only
                                      // globals in the same comdat are visited.
     }
   }
 }
 
+void GlobalDCEPass::PropagateLivenessInGlobalValues() {
+  // Propagate liveness from collected Global Values through the computed
+  // dependencies.
+  SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(),
+                                           AliveGlobals.end()};
+  while (!NewLiveGVs.empty()) {
+    GlobalValue *LGV = NewLiveGVs.pop_back_val();
+    for (auto *GVD : GVDependencies[LGV])
+      MarkLive(*GVD, &NewLiveGVs);
+  }
+}
+
 void GlobalDCEPass::ScanVTables(Module &M) {
   SmallVector<MDNode *, 2> Types;
   LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n");
 
   auto *LTOPostLinkMD =
       cast_or_null<ConstantAsMetadata>(M.getModuleFlag("LTOPostLink"));
   bool LTOPostLink =
       LTOPostLinkMD &&
void GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) {
 
   LLVM_DEBUG(
     dbgs() << "VFE safe vtables:\n";
     for (auto *VTable : VFESafeVTables)
       dbgs() << "  " << VTable->getName() << "\n";
   );
 }
 
+static bool RemoveConditionalTargetsFromUsedList(Module &M) {
+  auto *Used = M.getGlobalVariable("llvm.used");
+  if (!Used)
+    return false;
+
+  auto *UsedConditional = M.getNamedMetadata("llvm.used.conditional");
+  if (!UsedConditional)
+    return false;
+  if (UsedConditional->getNumOperands() == 0)
+    return false;
+
+  // Construct a set of conditionally used targets.
+  SmallPtrSet<GlobalValue *, 8> Targets;
+  for (auto *M : UsedConditional->operands()) {
+    assert(M->getNumOperands() == 3);
+    auto *V = mdconst::extract_or_null<GlobalValue>(M->getOperand(0));
+    if (!V)
+      continue;
+    Targets.insert(V);
+  }
+
+  if (Targets.empty())
+    return false;
+
+  // Now remove all targets from @llvm.used.
+  SmallPtrSet<GlobalValue *, 8> NewUsedArray;
+  const ConstantArray *UsedList = cast<ConstantArray>(Used->getInitializer());
+  for (Value *Op : UsedList->operands()) {
+    GlobalValue *G = cast<GlobalValue>(Op->stripPointerCasts());
+    if (Targets.contains(G))
+      continue;
+    NewUsedArray.insert(G);
+  }
+  Used = setUsedInitializer(*Used, NewUsedArray);
+  return true;
+}
+
+// Parse one entry from !llvm.used.conditional list as a triplet of
+// { target, type, dependencies } and evaluate the conditional dependency, i.e.
+// check liveness of all dependencies and based on type conclude whether the
+// target is supposed to be declared alive. If yes, return the target, otherwise
+// return nullptr.
+GlobalValue *GlobalDCEPass::TargetFromConditionalUsedIfLive(MDNode *M) {
+  assert(M->getNumOperands() == 3);
+  auto *Target = mdconst::extract_or_null<GlobalValue>(M->getOperand(0));
+  if (!Target)
+    return nullptr;
+
+  auto *DependenciesMD = dyn_cast_or_null<MDNode>(M->getOperand(2).get());
+  SmallPtrSet<GlobalValue *, 8> Dependencies;
+  if (DependenciesMD == nullptr) {
+    Dependencies.insert(nullptr);
+  } else {
+    for (auto &DependencyMD : DependenciesMD->operands()) {
+      auto *Dependency = DependencyMD.get();
+      if (!Dependency)
+        continue;
+      auto *C =
+          mdconst::extract_or_null<Constant>(Dependency)->stripPointerCasts();
+      Dependencies.insert(cast<GlobalValue>(C));
+    }
+  }
+
+  bool AllDependenciesAlive = true;
+  bool AnyDependencyAlive = false;
+  for (auto *Dep : Dependencies) {
+    bool Live = AliveGlobals.count(Dep) != 0;
+    if (Live)
+      AnyDependencyAlive = true;
+    else
+      AllDependenciesAlive = false;
+  }
+
+  auto *Type = mdconst::extract_or_null<ConstantInt>(M->getOperand(1));
+  switch (Type->getValue().getSExtValue()) {
+  case 0:
+    return AnyDependencyAlive ? Target : nullptr;
+  case 1:
+    return AllDependenciesAlive ? Target : nullptr;
+  default:
+    llvm_unreachable("bad !llvm.used.conditional type");
+  }
+}
+
+void GlobalDCEPass::PropagateLivenessToConditionallyUsed(Module &M) {
+  auto *Used = M.getGlobalVariable("llvm.used");
+  auto *UsedConditional = M.getNamedMetadata("llvm.used.conditional");
+
+  SmallPtrSet<GlobalValue *, 8> NewUsedArray;
+  const ConstantArray *UsedList = cast<ConstantArray>(Used->getInitializer());
+  for (Value *Op : UsedList->operands()) {
+    NewUsedArray.insert(cast<GlobalValue>(Op->stripPointerCasts()));
+  }
+
+  // Repeat the liveness propagation iteraticely, one iteration might force
+  // other conditionally used globals to become alive.
+  while (true) {
+    PropagateLivenessInGlobalValues();
+
+    unsigned OldSize = NewUsedArray.size();
+    for (auto *M : UsedConditional->operands()) {
+      auto *Target = TargetFromConditionalUsedIfLive(M);
+      if (!Target) continue;
+
+      NewUsedArray.insert(Target);
+      MarkLive(*Target);
+      LLVM_DEBUG(dbgs() << "Conditionally used target alive: "
+                        << Target->getName() << "\n");
+    }
+
+    unsigned NewSize = NewUsedArray.size();
+    LLVM_DEBUG(dbgs() << "Conditionally used iteration end, old size: "
+                      << OldSize << " new size: " << NewSize << "\n");
+
+    // Stop the iteration once we reach a steady state (no new additions to
+    // @llvm.used).
+    if (NewSize == OldSize) break;
+  }
+
+  Used = setUsedInitializer(*Used, NewUsedArray);
+  MarkLive(*Used);
+}
+
 PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
   bool Changed = false;
 
   // The algorithm first computes the set L of global variables that are
   // trivially live.  Then it walks the initialization of these variables to
   // compute the globals used to initialize them, which effectively builds a
   // directed graph where nodes are global variables, and an edge from A to B
   // means B is used to initialize A.  Finally, it propagates the liveness
PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &MAM) {
   for (GlobalAlias &GA : M.aliases())
     if (Comdat *C = GA.getComdat())
       ComdatMembers.insert(std::make_pair(C, &GA));
 
   // Add dependencies between virtual call sites and the virtual functions they
   // might call, if we have that information.
   AddVirtualFunctionDependencies(M);
 
+  // Process the !llvm.used.conditional list and (temporarily, see below)
+  // remove all "targets" from @llvm.used. No effect if `!llvm.used.conditional`
+  // is not present in the module.
+  bool UsedConditionalPresent = RemoveConditionalTargetsFromUsedList(M);
+
   // Loop over the module, adding globals which are obviously necessary.
   for (GlobalObject &GO : M.global_objects()) {
     Changed |= RemoveUnusedGlobalValue(GO);
     // Functions with external linkage are needed if they have a body.
     // Externally visible & appending globals are needed, if they have an
     // initializer.
     if (!GO.isDeclaration())
       if (!GO.isDiscardableIfUnused())
for (GlobalIFunc &GIF : M.ifuncs()) {
     Changed |= RemoveUnusedGlobalValue(GIF);
     // Externally visible ifuncs are needed.
     if (!GIF.isDiscardableIfUnused())
       MarkLive(GIF);
 
     UpdateGVDependencies(GIF);
   }
 
-  // Propagate liveness from collected Global Values through the computed
-  // dependencies.
-  SmallVector<GlobalValue *, 8> NewLiveGVs{AliveGlobals.begin(),
-                                           AliveGlobals.end()};
-  while (!NewLiveGVs.empty()) {
-    GlobalValue *LGV = NewLiveGVs.pop_back_val();
-    for (auto *GVD : GVDependencies[LGV])
-      MarkLive(*GVD, &NewLiveGVs);
+  // Step 2 of !llvm.used.conditional processing: If any conditionally used
+  // "targets" are alive, put them back into @llvm.used.
+  if (UsedConditionalPresent) {
+    PropagateLivenessToConditionallyUsed(M);
   }
 
+  PropagateLivenessInGlobalValues();
+
   // Now that all globals which are needed are in the AliveGlobals set, we loop
   // through the program, deleting those which are not alive.
   //
 
   // The first pass is to drop initializers of global variables which are dead.
   std::vector<GlobalVariable *> DeadGlobalVars; // Keep track of dead globals
   for (GlobalVariable &GV : M.globals())
     if (!AliveGlobals.count(&GV)) {

llvm/test/Transforms/GlobalDCE/used.conditional1.ll

+; RUN: opt -S -globaldce < %s | FileCheck %s
+
+;
+; (1) a regular dead global referenced in @llvm.used is kept alive
+;
+define internal void @func_marked_as_used() {
+  ; CHECK: @func_marked_as_used
+  ret void
+}
+
+;
+; (2) a dead global referenced in @llvm.used, but marked as conditionally used
+; in !llvm.used.conditional where the condition is alive, is kept alive
+;
+define internal void @func_conditionally_used_and_live() {
+  ; CHECK: @func_conditionally_used_and_live
+  ret void
+}
+
+;
+; (3) a dead global referenced in @llvm.used, but marked as conditionally used
+; in !llvm.used.conditional where the condition is dead, is eliminated
+;
+define internal void @func_conditionally_used_and_dead() {
+  ; CHECK-NOT: @func_conditionally_used_and_dead
+  ret void
+}
+
+@condition_live = internal unnamed_addr constant i64 42
+@condition_dead = internal unnamed_addr constant i64 42
+
[e-mail] = appending global [4 x i8*] [
+   i8* bitcast (void ()* @func_marked_as_used to i8*),
+   i8* bitcast (i64* @condition_live to i8*),
+   i8* bitcast (void ()* @func_conditionally_used_and_live to i8*),
+   i8* bitcast (void ()* @func_conditionally_used_and_dead to i8*)
+], section "llvm.metadata"
+
+!1 = !{void ()* @func_conditionally_used_and_live, i32 0, !{i64* @condition_live}}
+!2 = !{void ()* @func_conditionally_used_and_dead, i32 0, !{i64* @condition_dead}}
+!llvm.used.conditional = !{!1, !2}

llvm/test/Transforms/GlobalDCE/used.conditional2.ll

+; RUN: opt -S -globaldce < %s | FileCheck %s
+
+;
+; (1) a dead global referenced in @llvm.used, but marked as conditionally used
+; by both @condition_live and @condition_dead, with an *ANY* type, is alive
+;
+define internal void @func_conditionally_by_two_conditions_any() {
+  ; CHECK: @func_conditionally_by_two_conditions_any
+  ret void
+}
+
+;
+; (2) a dead global referenced in @llvm.used, but marked as conditionally used
+; by both @condition_live and @condition_dead, with an *ALL* type, is removed
+;
+define internal void @func_conditionally_by_two_conditions_all() {
+  ; CHECK-NOT: @func_conditionally_by_two_conditions_all
+  ret void
+}
+
+@condition_live = internal unnamed_addr constant i64 42
+@condition_dead = internal unnamed_addr constant i64 42
+
[e-mail] = appending global [3 x i8*] [
+   i8* bitcast (i64* @condition_live to i8*),
+   i8* bitcast (void ()* @func_conditionally_by_two_conditions_any to i8*),
+   i8* bitcast (void ()* @func_conditionally_by_two_conditions_all to i8*)
+], section "llvm.metadata"
+
+!1 = !{void ()* @func_conditionally_by_two_conditions_any, i32 0, !{ i64* @condition_live, i64* @condition_dead } }
+!2 = !{void ()* @func_conditionally_by_two_conditions_all, i32 1, !{ i64* @condition_live, i64* @condition_dead } }
+!llvm.used.conditional = !{!1, !2}

llvm/test/Transforms/GlobalDCE/used.conditional3.ll

+; RUN: opt -S -globaldce < %s | FileCheck %s
+
+; Test that when performing llvm.used.conditional removals, we discover globals
+; that might trigger other llvm.used.conditional liveness. See the following
+; diagram of dependencies between the globals:
+;
+; @a -\
+;      \ (conditional, see !1, satisfied)
+;       \-> @b -\
+;                \ (regular usage)
+;                 \-> @c -\
+;                          \ (conditional, see !2, satisfied)
+;                           \-> @d
+
+@a = internal unnamed_addr constant i64 42
+@b = internal unnamed_addr constant i64* @c
+@c = internal unnamed_addr constant i64 42
+@d = internal unnamed_addr constant i64 42
+
+; All four, and mainly @d need to stay alive:
+; CHECK: @a = internal unnamed_addr constant i64 42
+; CHECK: @b = internal unnamed_addr constant i64* @c
+; CHECK: @c = internal unnamed_addr constant i64 42
+; CHECK: @d = internal unnamed_addr constant i64 42
+
[e-mail] = appending global [3 x i8*] [
+  i8* bitcast (i64* @a to i8*),
+  i8* bitcast (i64** @b to i8*),
+  i8* bitcast (i64* @d to i8*)
+], section "llvm.metadata"
+
+!1 = !{i64** @b, i32 0, !{i64* @a}}
+!2 = !{i64* @d, i32 0, !{i64* @c}}
+!llvm.used.conditional = !{!1, !2}