Index: llvm/include/llvm/Transforms/Utils/ModuleUtils.h =================================================================== --- llvm/include/llvm/Transforms/Utils/ModuleUtils.h +++ llvm/include/llvm/Transforms/Utils/ModuleUtils.h @@ -13,6 +13,7 @@ #ifndef LLVM_TRANSFORMS_UTILS_MODULEUTILS_H #define LLVM_TRANSFORMS_UTILS_MODULEUTILS_H +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" #include // for std::pair @@ -24,6 +25,7 @@ class Function; class FunctionCallee; class GlobalValue; +class GlobalVariable; class Constant; class Value; class Type; @@ -78,6 +80,10 @@ /// Adds global values to the llvm.compiler.used list. void appendToCompilerUsed(Module &M, ArrayRef Values); +/// Replaces llvm.used or llvm.compiler.used list with a new set of values. +GlobalVariable *setUsedInitializer(GlobalVariable &V, + const SmallPtrSetImpl &Init); + /// Filter out potentially dead comdat functions where other entries keep the /// entire comdat group alive. /// 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; @@ -294,7 +295,7 @@ // 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 - // information through the graph starting from the nodes in L. Nodes note + // information through the graph starting from the nodes in L. Nodes not // marked as alive are discarded. // Remove empty functions from the global ctors list. @@ -315,6 +316,36 @@ // might call, if we have that information. AddVirtualFunctionDependencies(M); + auto *Used = M.getGlobalVariable("llvm.used"); + auto *UsedConditional = M.getNamedMetadata("llvm.used.conditional"); + if (UsedConditional && UsedConditional->getNumOperands() == 0) + UsedConditional = nullptr; + SmallPtrSet NewUsedArray; + if (Used) { + // Construct a set of conditionally used targets. + SmallPtrSet UsedConditionalTargets; + if (UsedConditional) { + for (auto *M : UsedConditional->operands()) { + assert(M->getNumOperands() == 3); + auto *V = mdconst::extract_or_null(M->getOperand(0)); + if (!V) + continue; + UsedConditionalTargets.insert(V); + } + } + + // Strip away all conditionally used targets from @llvm.used. + const ConstantArray *Init = cast(Used->getInitializer()); + for (Value *Op : Init->operands()) { + GlobalValue *G = cast(Op->stripPointerCasts()); + // G is one of the conditional targets, don't mark it as live. + if (UsedConditionalTargets.contains(G)) + continue; + NewUsedArray.insert(G); + } + Used = setUsedInitializer(*Used, NewUsedArray); + } + // Loop over the module, adding globals which are obviously necessary. for (GlobalObject &GO : M.global_objects()) { Changed |= RemoveUnusedGlobalValue(GO); @@ -348,6 +379,82 @@ UpdateGVDependencies(GIF); } + // We need to repeat this, if a conditional used variable is marked alive and + // added to NewUsedArray, we should check if that will enable other + // conditional used variables to become alive. + bool HasUpdateInIteration = true; + while (Used && UsedConditional && HasUpdateInIteration) { + // 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); + } + } + + unsigned OldSize = NewUsedArray.size(); + for (auto *M : UsedConditional->operands()) { + assert(M->getNumOperands() == 3); + auto *V = mdconst::extract_or_null(M->getOperand(0)); + if (!V) + continue; + + auto *T = mdconst::extract_or_null(M->getOperand(1)); + if (!T) + continue; + APInt Type = T->getValue(); + + SmallPtrSet Others; + if (M->getOperand(2) == nullptr) { + Others.insert(nullptr); + } else { + if (auto *SingleOther = + mdconst::dyn_extract_or_null(M->getOperand(2))) { + Others.insert(SingleOther); + } else { + Metadata *MultipleOthers = M->getOperand(2).get(); + MDNode *Node = dyn_cast_or_null(MultipleOthers); + for (auto &X : Node->operands()) { + auto *Y = X.get(); + if (!Y) + continue; + auto *C = mdconst::extract_or_null(Y); + C = C->stripPointerCasts(); + auto *O = cast(C); + Others.insert(O); + } + } + } + + bool AllOthersAlive = true; + bool AnyOtherAlive = false; + for (auto *GV : Others) { + bool Live = AliveGlobals.count(GV) != 0; + if (Live) + AnyOtherAlive = true; + else + AllOthersAlive = false; + } + + if ((Type == 0 && AnyOtherAlive) || (Type == 1 && AllOthersAlive)) { + NewUsedArray.insert(V); + MarkLive(*V); + LLVM_DEBUG(dbgs() << "Mark conditional used GV " << V->getName() + << " to be live.\n"); + } + } + LLVM_DEBUG(dbgs() << "Optimizing UsedConditional iteration end " << OldSize + << ' ' << NewUsedArray.size() << "\n"); + HasUpdateInIteration = NewUsedArray.size() > OldSize; + } + if (Used && UsedConditional) { + Used = setUsedInitializer(*Used, NewUsedArray); + MarkLive(*Used); + } + // Propagate liveness from collected Global Values through the computed // dependencies. SmallVector NewLiveGVs{AliveGlobals.begin(), Index: llvm/lib/Transforms/IPO/GlobalOpt.cpp =================================================================== --- llvm/lib/Transforms/IPO/GlobalOpt.cpp +++ llvm/lib/Transforms/IPO/GlobalOpt.cpp @@ -66,6 +66,7 @@ #include "llvm/Transforms/Utils/Evaluator.h" #include "llvm/Transforms/Utils/GlobalStatus.h" #include "llvm/Transforms/Utils/Local.h" +#include "llvm/Transforms/Utils/ModuleUtils.h" #include #include #include @@ -2304,42 +2305,6 @@ return EvalSuccess; } -static int compareNames(Constant *const *A, Constant *const *B) { - Value *AStripped = (*A)->stripPointerCasts(); - Value *BStripped = (*B)->stripPointerCasts(); - return AStripped->getName().compare(BStripped->getName()); -} - -static void setUsedInitializer(GlobalVariable &V, - const SmallPtrSetImpl &Init) { - if (Init.empty()) { - V.eraseFromParent(); - return; - } - - // Type of pointer to the array of pointers. - PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext(), 0); - - SmallVector UsedArray; - for (GlobalValue *GV : Init) { - Constant *Cast - = ConstantExpr::getPointerBitCastOrAddrSpaceCast(GV, Int8PtrTy); - UsedArray.push_back(Cast); - } - // Sort to get deterministic order. - array_pod_sort(UsedArray.begin(), UsedArray.end(), compareNames); - ArrayType *ATy = ArrayType::get(Int8PtrTy, UsedArray.size()); - - Module *M = V.getParent(); - V.removeFromParent(); - GlobalVariable *NV = - new GlobalVariable(*M, ATy, false, GlobalValue::AppendingLinkage, - ConstantArray::get(ATy, UsedArray), ""); - NV->takeName(&V); - NV->setSection("llvm.metadata"); - delete &V; -} - namespace { /// An easy to access representation of llvm.used and llvm.compiler.used. Index: llvm/lib/Transforms/Utils/ModuleUtils.cpp =================================================================== --- llvm/lib/Transforms/Utils/ModuleUtils.cpp +++ llvm/lib/Transforms/Utils/ModuleUtils.cpp @@ -111,6 +111,43 @@ appendToUsedList(M, "llvm.compiler.used", Values); } +static int compareNames(Constant *const *A, Constant *const *B) { + Value *AStripped = (*A)->stripPointerCasts(); + Value *BStripped = (*B)->stripPointerCasts(); + return AStripped->getName().compare(BStripped->getName()); +} + +GlobalVariable *llvm::setUsedInitializer( + GlobalVariable &V, const SmallPtrSetImpl &Init) { + if (Init.empty()) { + V.eraseFromParent(); + return nullptr; + } + + // Type of pointer to the array of pointers. + PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext(), 0); + + SmallVector UsedArray; + for (GlobalValue *GV : Init) { + Constant *Cast + = ConstantExpr::getPointerBitCastOrAddrSpaceCast(GV, Int8PtrTy); + UsedArray.push_back(Cast); + } + // Sort to get deterministic order. + array_pod_sort(UsedArray.begin(), UsedArray.end(), compareNames); + ArrayType *ATy = ArrayType::get(Int8PtrTy, UsedArray.size()); + + Module *M = V.getParent(); + V.removeFromParent(); + GlobalVariable *NV = + new GlobalVariable(*M, ATy, false, GlobalValue::AppendingLinkage, + ConstantArray::get(ATy, UsedArray), ""); + NV->takeName(&V); + NV->setSection("llvm.metadata"); + delete &V; + return NV; +} + FunctionCallee llvm::declareSanitizerInitFunction(Module &M, StringRef InitName, ArrayRef InitArgTypes) { 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}