Index: llvm/trunk/include/llvm/Transforms/IPO/GlobalDCE.h =================================================================== --- llvm/trunk/include/llvm/Transforms/IPO/GlobalDCE.h +++ llvm/trunk/include/llvm/Transforms/IPO/GlobalDCE.h @@ -18,6 +18,8 @@ #ifndef LLVM_TRANSFORMS_IPO_GLOBALDCE_H #define LLVM_TRANSFORMS_IPO_GLOBALDCE_H +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" #include @@ -31,14 +33,23 @@ private: SmallPtrSet AliveGlobals; - SmallPtrSet SeenConstants; + + /// Global -> Global that uses this global. + std::unordered_multimap GVDependencies; + + /// Constant -> Globals that use this global cache. + std::unordered_map> + ConstantDependenciesCache; + + /// Comdat -> Globals in that Comdat section. std::unordered_multimap ComdatMembers; - /// Mark the specific global value as needed, and - /// recursively mark anything that it uses as also needed. - void GlobalIsNeeded(GlobalValue *GV); - void MarkUsedGlobalsAsNeeded(Constant *C); + void UpdateGVDependencies(GlobalValue &GV); + void MarkLive(GlobalValue &GV, + SmallVectorImpl *Updates = nullptr); bool RemoveUnusedGlobalValue(GlobalValue &GV); + + void ComputeDependencies(Value *V, SmallPtrSetImpl &U); }; } Index: llvm/trunk/lib/Transforms/IPO/GlobalDCE.cpp =================================================================== --- llvm/trunk/lib/Transforms/IPO/GlobalDCE.cpp +++ llvm/trunk/lib/Transforms/IPO/GlobalDCE.cpp @@ -25,7 +25,7 @@ #include "llvm/Transforms/IPO.h" #include "llvm/Transforms/Utils/CtorUtils.h" #include "llvm/Transforms/Utils/GlobalStatus.h" -#include + using namespace llvm; #define DEBUG_TYPE "globaldce" @@ -85,9 +85,67 @@ return RI.getReturnValue() == nullptr; } +/// Compute the set of GlobalValue that depends from V. +/// The recursion stops as soon as a GlobalValue is met. +void GlobalDCEPass::ComputeDependencies(Value *V, + SmallPtrSetImpl &Deps) { + if (auto *I = dyn_cast(V)) { + Function *Parent = I->getParent()->getParent(); + Deps.insert(Parent); + } else if (auto *GV = dyn_cast(V)) { + Deps.insert(GV); + } else if (auto *CE = dyn_cast(V)) { + // Avoid walking the whole tree of a big ConstantExprs multiple times. + auto Where = ConstantDependenciesCache.find(CE); + if (Where != ConstantDependenciesCache.end()) { + auto const &K = Where->second; + Deps.insert(K.begin(), K.end()); + } else { + SmallPtrSetImpl &LocalDeps = ConstantDependenciesCache[CE]; + for (User *CEUser : CE->users()) + ComputeDependencies(CEUser, LocalDeps); + Deps.insert(LocalDeps.begin(), LocalDeps.end()); + } + } +} + +void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) { + SmallPtrSet Deps; + for (User *User : GV.users()) + ComputeDependencies(User, Deps); + Deps.erase(&GV); // Remove self-reference. + for (GlobalValue *GVU : Deps) { + GVDependencies.insert(std::make_pair(GVU, &GV)); + } +} + +/// Mark Global value as Live +void GlobalDCEPass::MarkLive(GlobalValue &GV, + SmallVectorImpl *Updates) { + auto const Ret = AliveGlobals.insert(&GV); + if (!Ret.second) + return; + + if (Updates) + Updates->push_back(&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. + } +} + 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 + // information through the graph starting from the nodes in L. Nodes note + // marked as alive are discarded. + // Remove empty functions from the global ctors list. Changed |= optimizeGlobalCtorsList(M, isEmptyFunction); @@ -110,21 +168,39 @@ // initializer. if (!GO.isDeclaration() && !GO.hasAvailableExternallyLinkage()) if (!GO.isDiscardableIfUnused()) - GlobalIsNeeded(&GO); + MarkLive(GO); + + UpdateGVDependencies(GO); } + // Compute direct dependencies of aliases. for (GlobalAlias &GA : M.aliases()) { Changed |= RemoveUnusedGlobalValue(GA); // Externally visible aliases are needed. if (!GA.isDiscardableIfUnused()) - GlobalIsNeeded(&GA); + MarkLive(GA); + + UpdateGVDependencies(GA); } + // Compute direct dependencies of ifuncs. for (GlobalIFunc &GIF : M.ifuncs()) { Changed |= RemoveUnusedGlobalValue(GIF); // Externally visible ifuncs are needed. if (!GIF.isDiscardableIfUnused()) - GlobalIsNeeded(&GIF); + MarkLive(GIF); + + 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 : make_range(GVDependencies.equal_range(LGV))) + MarkLive(*GVD.second, &NewLiveGVs); } // Now that all globals which are needed are in the AliveGlobals set, we loop @@ -161,7 +237,7 @@ GA.setAliasee(nullptr); } - // The third pass drops targets of ifuncs which are dead... + // The fourth pass drops targets of ifuncs which are dead... std::vector DeadIFuncs; for (GlobalIFunc &GIF : M.ifuncs()) if (!AliveGlobals.count(&GIF)) { @@ -195,7 +271,8 @@ // Make sure that all memory is released AliveGlobals.clear(); - SeenConstants.clear(); + ConstantDependenciesCache.clear(); + GVDependencies.clear(); ComdatMembers.clear(); if (Changed) @@ -203,60 +280,6 @@ return PreservedAnalyses::all(); } -/// GlobalIsNeeded - the specific global value as needed, and -/// recursively mark anything that it uses as also needed. -void GlobalDCEPass::GlobalIsNeeded(GlobalValue *G) { - // If the global is already in the set, no need to reprocess it. - if (!AliveGlobals.insert(G).second) - return; - - if (Comdat *C = G->getComdat()) { - for (auto &&CM : make_range(ComdatMembers.equal_range(C))) - GlobalIsNeeded(CM.second); - } - - if (GlobalVariable *GV = dyn_cast(G)) { - // If this is a global variable, we must make sure to add any global values - // referenced by the initializer to the alive set. - if (GV->hasInitializer()) - MarkUsedGlobalsAsNeeded(GV->getInitializer()); - } else if (GlobalIndirectSymbol *GIS = dyn_cast(G)) { - // The target of a global alias or ifunc is needed. - MarkUsedGlobalsAsNeeded(GIS->getIndirectSymbol()); - } else { - // Otherwise this must be a function object. We have to scan the body of - // the function looking for constants and global values which are used as - // operands. Any operands of these types must be processed to ensure that - // any globals used will be marked as needed. - Function *F = cast(G); - - for (Use &U : F->operands()) - MarkUsedGlobalsAsNeeded(cast(U.get())); - - for (BasicBlock &BB : *F) - for (Instruction &I : BB) - for (Use &U : I.operands()) - if (GlobalValue *GV = dyn_cast(U)) - GlobalIsNeeded(GV); - else if (Constant *C = dyn_cast(U)) - MarkUsedGlobalsAsNeeded(C); - } -} - -void GlobalDCEPass::MarkUsedGlobalsAsNeeded(Constant *C) { - if (GlobalValue *GV = dyn_cast(C)) - return GlobalIsNeeded(GV); - - // Loop over all of the operands of the constant, adding any globals they - // use to the list of needed globals. - for (Use &U : C->operands()) { - // If we've already processed this constant there's no need to do it again. - Constant *Op = dyn_cast(U); - if (Op && SeenConstants.insert(Op).second) - MarkUsedGlobalsAsNeeded(Op); - } -} - // RemoveUnusedGlobalValue - Loop over all of the uses of the specified // GlobalValue, looking for the constant pointer ref that may be pointing to it. // If found, check to see if the constant pointer ref is safe to destroy, and if