Index: llvm/docs/LangRef.rst =================================================================== --- llvm/docs/LangRef.rst +++ llvm/docs/LangRef.rst @@ -7340,6 +7340,55 @@ 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 Index: llvm/include/llvm/Transforms/IPO/GlobalDCE.h =================================================================== --- llvm/include/llvm/Transforms/IPO/GlobalDCE.h +++ llvm/include/llvm/Transforms/IPO/GlobalDCE.h @@ -54,6 +54,7 @@ void UpdateGVDependencies(GlobalValue &GV); void MarkLive(GlobalValue &GV, SmallVectorImpl *Updates = nullptr); + void PropagateLivenessInGlobalValues(); bool RemoveUnusedGlobalValue(GlobalValue &GV); // Dead virtual function elimination. @@ -63,6 +64,9 @@ void ScanVTableLoad(Function *Caller, Metadata *TypeId, uint64_t CallOffset); void ComputeDependencies(Value *V, SmallPtrSetImpl &U); + + GlobalValue *TargetFromConditionalUsedIfLive(MDNode *M); + void PropagateLivenessToConditionallyUsed(Module &M); }; } Index: llvm/lib/IR/Verifier.cpp =================================================================== --- llvm/lib/IR/Verifier.cpp +++ llvm/lib/IR/Verifier.cpp @@ -837,6 +837,34 @@ visitMDNode(*MD, AreDebugLocsAllowed::Yes); } + + if (NMD.getName() == "llvm.used.conditional") { + for (const MDNode *MD : NMD.operands()) { + Assert(MD->getNumOperands() == 3, "invalid llvm.used.conditional member"); + auto *TargetMD = MD->getOperand(0).get(); + if (TargetMD != nullptr) { + Assert(mdconst::dyn_extract(TargetMD), + "invalid llvm.used.conditional member"); + } + auto *TypeMD = mdconst::extract_or_null(MD->getOperand(1)); + int64_t Type = TypeMD->getValue().getSExtValue(); + Assert(Type == 0 || Type == 1, "invalid llvm.used.conditional member"); + auto *DependenciesMD = dyn_cast(MD->getOperand(2).get()); + Assert(DependenciesMD, "invalid llvm.used.conditional member"); + Assert(DependenciesMD->getNumOperands() > 0, + "invalid llvm.used.conditional member"); + for (auto &DependencyMD : DependenciesMD->operands()) { + auto *Dependency = DependencyMD.get(); + if (!Dependency) + continue; // Allow null, skip. + auto *C = + mdconst::dyn_extract(Dependency)->stripPointerCasts(); + if (dyn_cast(C)) + continue; // Allow undef, skip. + Assert(isa(C), "invalid llvm.used.conditional member"); + } + } + } } void Verifier::visitMDNode(const MDNode &MD, AreDebugLocsAllowed AllowLocs) { Index: llvm/lib/Transforms/IPO/GlobalDCE.cpp =================================================================== --- llvm/lib/Transforms/IPO/GlobalDCE.cpp +++ llvm/lib/Transforms/IPO/GlobalDCE.cpp @@ -28,6 +28,7 @@ #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; @@ -157,6 +158,18 @@ } } +void GlobalDCEPass::PropagateLivenessInGlobalValues() { + // Propagate liveness from collected Global Values through the computed + // dependencies. + SmallVector 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 Types; LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n"); @@ -286,6 +299,135 @@ ); } +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 Targets; + for (auto *M : UsedConditional->operands()) { + assert(M->getNumOperands() == 3); + auto *V = mdconst::extract_or_null(M->getOperand(0)); + if (!V) + continue; + Targets.insert(V); + } + + if (Targets.empty()) + return false; + + // Now remove all targets from @llvm.used. + SmallPtrSet NewUsedArray; + const ConstantArray *UsedList = cast(Used->getInitializer()); + for (Value *Op : UsedList->operands()) { + GlobalValue *G = cast(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(M->getOperand(0)); + if (!Target) + return nullptr; + + auto *DependenciesMD = dyn_cast_or_null(M->getOperand(2).get()); + SmallPtrSet Dependencies; + if (DependenciesMD == nullptr) { + Dependencies.insert(nullptr); + } else { + for (auto &DependencyMD : DependenciesMD->operands()) { + auto *Dependency = DependencyMD.get(); + if (!Dependency) + continue; // Allow null, skip. + auto *C = + mdconst::extract_or_null(Dependency)->stripPointerCasts(); + if (dyn_cast(C)) + continue; // Allow undef, skip. + Dependencies.insert(cast(C)); + } + } + + bool AllDependenciesAlive = Dependencies.empty() ? false : 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(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"); + if (!Used) + return; + auto *UsedConditional = M.getNamedMetadata("llvm.used.conditional"); + if (!UsedConditional) + return; + + SmallPtrSet NewUsedArray; + const ConstantArray *UsedList = cast(Used->getInitializer()); + for (Value *Op : UsedList->operands()) { + NewUsedArray.insert(cast(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; @@ -315,6 +457,11 @@ // 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); @@ -348,16 +495,14 @@ UpdateGVDependencies(GIF); } - // Propagate liveness from collected Global Values through the computed - // dependencies. - SmallVector 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. // Index: llvm/test/Linker/Inputs/merge-used-conditional2.ll =================================================================== --- /dev/null +++ llvm/test/Linker/Inputs/merge-used-conditional2.ll @@ -0,0 +1,9 @@ +@target2 = internal unnamed_addr constant i32 46 +@dep2 = global i32 732 + +@llvm.used = appending global [1 x i8*] [ + i8* bitcast (i32* @target2 to i8*) +], section "llvm.metadata" + +!0 = !{i32* @target2, i32 0, !{i8* bitcast (i32* @dep2 to i8*)}} +!llvm.used.conditional = !{!0} Index: llvm/test/Linker/merge-used-conditional.ll =================================================================== --- /dev/null +++ llvm/test/Linker/merge-used-conditional.ll @@ -0,0 +1,23 @@ +; RUN: llvm-link %s %p/Inputs/merge-used-conditional2.ll -S | FileCheck %s + +@target1 = internal unnamed_addr constant i32 46 +@dep1 = global i32 732 + +@llvm.used = appending global [1 x i8*] [ + i8* bitcast (i32* @target1 to i8*) +], section "llvm.metadata" + +!0 = !{i32* @target1, i32 0, !{i8* bitcast (i32* @dep1 to i8*)}} +!llvm.used.conditional = !{!0} + +; CHECK-DAG: @llvm.used = appending global [2 x i8*] [i8* bitcast (i32* @target1 to i8*), i8* bitcast (i32* @target2 to i8*)], section "llvm.metadata" + +; CHECK-DAG: @target1 = internal unnamed_addr +; CHECK-DAG: @target2 = internal unnamed_addr + +; CHECK-DAG: !llvm.used.conditional = !{!0, !2} + +; CHECK-DAG: !0 = !{i32* @target1, i32 0, !1} +; CHECK-DAG: !1 = !{i8* bitcast (i32* @dep1 to i8*)} +; CHECK-DAG: !2 = !{i32* @target2, i32 0, !3} +; CHECK-DAG: !3 = !{i8* bitcast (i32* @dep2 to i8*)} Index: llvm/test/Transforms/GlobalDCE/used.conditional1.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/GlobalDCE/used.conditional1.ll @@ -0,0 +1,41 @@ +; 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 + +@llvm.used = 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} Index: llvm/test/Transforms/GlobalDCE/used.conditional2.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/GlobalDCE/used.conditional2.ll @@ -0,0 +1,32 @@ +; 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 + +@llvm.used = 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} Index: llvm/test/Transforms/GlobalDCE/used.conditional3.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/GlobalDCE/used.conditional3.ll @@ -0,0 +1,34 @@ +; 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 + +@llvm.used = 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} Index: llvm/test/Transforms/GlobalDCE/used.conditional4.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/GlobalDCE/used.conditional4.ll @@ -0,0 +1,19 @@ +; RUN: opt -S -globaldce < %s | FileCheck %s + +; Test !llvm.used.conditional with circular dependencies + +@globalA = internal unnamed_addr constant i8* bitcast (i8** @globalB to i8*) +@globalB = internal unnamed_addr constant i8* bitcast (i8** @globalA to i8*) + +; All four, and mainly @d need to stay alive: +; CHECK-NOT: @globalA +; CHECK-NOT: @globalB + +@llvm.used = appending global [2 x i8*] [ + i8* bitcast (i8** @globalA to i8*), + i8* bitcast (i8** @globalB to i8*) +], section "llvm.metadata" + +!1 = !{i8** @globalA, i32 0, !{i8** @globalB}} +!2 = !{i8** @globalB, i32 0, !{i8** @globalA}} +!llvm.used.conditional = !{!1, !2} Index: llvm/test/Transforms/GlobalDCE/used.conditional5.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/GlobalDCE/used.conditional5.ll @@ -0,0 +1,17 @@ +; RUN: opt -S -globaldce < %s | FileCheck %s + +@target = internal unnamed_addr constant i32 46 +@dep1 = internal unnamed_addr constant i32 732 + +@llvm.used = appending global [1 x i8*] [ + i8* bitcast (i32* @target to i8*) +], section "llvm.metadata" + +!0 = !{i32* @target, i32 0, !{i8* bitcast (i32* @dep1 to i8*)}} +!llvm.used.conditional = !{!0} + +; CHECK-NOT: @target +; CHECK-NOT: @dep1 +; CHECK: !llvm.used.conditional = !{!0} +; CHECK: !0 = distinct !{null, i32 0, !1} +; CHECK: !1 = !{i8* undef} Index: llvm/test/Verifier/llvm.used.conditional-invalid.ll =================================================================== --- /dev/null +++ llvm/test/Verifier/llvm.used.conditional-invalid.ll @@ -0,0 +1,10 @@ +; RUN: not llvm-as < %s -o /dev/null 2>&1 | FileCheck %s + +@a = global i32 42 +@llvm.used = appending global [1 x i32*] [i32* @a], section "llvm.metadata" + +@cond = global i32 43 +!1 = !{ i32* @cond, i32 1, !{ i32* @a }, i32 8 } +!llvm.used.conditional = !{ !1 } + +; CHECK: invalid llvm.used.conditional member Index: llvm/test/Verifier/llvm.used.conditional-invalid2.ll =================================================================== --- /dev/null +++ llvm/test/Verifier/llvm.used.conditional-invalid2.ll @@ -0,0 +1,10 @@ +; RUN: not llvm-as < %s -o /dev/null 2>&1 | FileCheck %s + +@a = global i32 42 +@llvm.used = appending global [1 x i32*] [i32* @a], section "llvm.metadata" + +@cond = global i32 43 +!1 = !{ i32* @cond, i32 1, i32* @a } +!llvm.used.conditional = !{ !1 } + +; CHECK: invalid llvm.used.conditional member Index: llvm/test/Verifier/llvm.used.conditional-invalid3.ll =================================================================== --- /dev/null +++ llvm/test/Verifier/llvm.used.conditional-invalid3.ll @@ -0,0 +1,10 @@ +; RUN: not llvm-as < %s -o /dev/null 2>&1 | FileCheck %s + +@a = global i32 42 +@llvm.used = appending global [1 x i32*] [i32* @a], section "llvm.metadata" + +@cond = global i32 43 +!1 = !{ i32* @cond, i32 4, !{ i32* @a } } +!llvm.used.conditional = !{ !1 } + +; CHECK: invalid llvm.used.conditional member Index: llvm/test/Verifier/llvm.used.conditional-invalid4.ll =================================================================== --- /dev/null +++ llvm/test/Verifier/llvm.used.conditional-invalid4.ll @@ -0,0 +1,10 @@ +; RUN: not llvm-as < %s -o /dev/null 2>&1 | FileCheck %s + +@a = global i32 42 +@llvm.used = appending global [1 x i32*] [i32* @a], section "llvm.metadata" + +@cond = global i32 43 +!1 = !{ !1, i32 1, !{ i32* @a } } +!llvm.used.conditional = !{ !1 } + +; CHECK: invalid llvm.used.conditional member Index: llvm/test/Verifier/llvm.used.conditional.ll =================================================================== --- /dev/null +++ llvm/test/Verifier/llvm.used.conditional.ll @@ -0,0 +1,9 @@ +; RUN: llvm-as < %s -o /dev/null + +@a = global i32 42 +@llvm.used = appending global [1 x i32*] [i32* @a], section "llvm.metadata" + +@cond = global i32 43 +!1 = !{ i32* @cond, i32 1, !{ i32* @a } } +!2 = !{ null, i32 1, !{ i32* @a } } +!llvm.used.conditional = !{ !1, !2 }