Index: include/llvm/Transforms/IPO/GlobalDCE.h =================================================================== --- include/llvm/Transforms/IPO/GlobalDCE.h +++ include/llvm/Transforms/IPO/GlobalDCE.h @@ -20,6 +20,8 @@ #include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/ADT/DenseMap.h" #include namespace llvm { @@ -30,15 +32,16 @@ PreservedAnalyses run(Module &M, ModuleAnalysisManager &); private: - SmallPtrSet AliveGlobals; - SmallPtrSet SeenConstants; - 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); + SmallPtrSet LiveGVs_; + DenseMap> GVDependencies_; + std::unordered_map> DependenciesCache_; + std::unordered_multimap ComdatMembers_; + + void UpdateGVDependencies(GlobalValue &GV); + void MarkLive(GlobalValue &GV, SmallVectorImpl* Updates=nullptr); bool RemoveUnusedGlobalValue(GlobalValue &GV); + + void ComputeDependencies(Value *V, SmallPtrSetImpl& U); }; } Index: lib/Transforms/IPO/GlobalDCE.cpp =================================================================== --- lib/Transforms/IPO/GlobalDCE.cpp +++ lib/Transforms/IPO/GlobalDCE.cpp @@ -26,6 +26,7 @@ #include "llvm/Transforms/Utils/CtorUtils.h" #include "llvm/Transforms/Utils/GlobalStatus.h" #include + using namespace llvm; #define DEBUG_TYPE "globaldce" @@ -78,7 +79,57 @@ return RI.getReturnValue() == nullptr; } +// Compute the set of GlobalValue that depends from V +// This repetitive walk is memoized as it can be called a lot for the same value. +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)) { + auto Where = DependenciesCache_.find(CE); + if(Where != DependenciesCache_.end()) { + auto const& K = Where->second; + Deps.insert(K.begin(), K.end()); + } + else { + auto &LocalDeps = DependenciesCache_[CE]; + for(auto* CEUser : CE->users()) + ComputeDependencies(CEUser, LocalDeps); + Deps.insert(LocalDeps.begin(), LocalDeps.end()); + } + } +} + +void GlobalDCEPass::UpdateGVDependencies(GlobalValue& GV) { + SmallPtrSet Deps; + for(auto* User: GV.users()) + ComputeDependencies(User, Deps); + Deps.erase(&GV); // remove self-reference + for(auto* GVU : Deps) { + GVDependencies_[GVU].insert(&GV); + } +} + +// Mark Global value as Live +void GlobalDCEPass::MarkLive(GlobalValue & GV, SmallVectorImpl* Updates) { + auto const Ret = LiveGVs_.insert(&GV); + if(Ret.second) { + LiveGVs_.insert(&GV); + if(Updates) + Updates->push_back(&GV); + if (Comdat *C = GV.getComdat()) { + for (auto &&CM : make_range(ComdatMembers_.equal_range(C))) + MarkLive(*CM.second, Updates); + } + } +} + PreservedAnalyses GlobalDCEPass::run(Module &M, ModuleAnalysisManager &) { + bool Changed = false; // Remove empty functions from the global ctors list. @@ -87,13 +138,13 @@ // Collect the set of members for each comdat. for (Function &F : M) if (Comdat *C = F.getComdat()) - ComdatMembers.insert(std::make_pair(C, &F)); + ComdatMembers_.insert(std::make_pair(C, &F)); for (GlobalVariable &GV : M.globals()) if (Comdat *C = GV.getComdat()) - ComdatMembers.insert(std::make_pair(C, &GV)); + ComdatMembers_.insert(std::make_pair(C, &GV)); for (GlobalAlias &GA : M.aliases()) if (Comdat *C = GA.getComdat()) - ComdatMembers.insert(std::make_pair(C, &GA)); + ComdatMembers_.insert(std::make_pair(C, &GA)); // Loop over the module, adding globals which are obviously necessary. for (GlobalObject &GO : M.global_objects()) { @@ -103,64 +154,89 @@ // 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{LiveGVs_.begin(), LiveGVs_.end()}; + while(!NewLiveGVs.empty()) { + auto * LGV = NewLiveGVs.back(); + NewLiveGVs.pop_back(); + for(auto* GV : GVDependencies_[LGV]) { + MarkLive(*GV, &NewLiveGVs); + } } + // 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 DeadGlobalVars; // Keep track of dead globals - for (GlobalVariable &GV : M.globals()) - if (!AliveGlobals.count(&GV)) { - DeadGlobalVars.push_back(&GV); // Keep track of dead globals - if (GV.hasInitializer()) { + SmallVector DeadGlobalVars; + for(GlobalVariable& GV : M.globals()) { + if(LiveGVs_.count(&GV) == 0) { + DeadGlobalVars.push_back(&GV); + if(GV.hasInitializer()) { Constant *Init = GV.getInitializer(); GV.setInitializer(nullptr); if (isSafeToDestroyConstant(Init)) Init->destroyConstant(); } } + } // The second pass drops the bodies of functions which are dead... - std::vector DeadFunctions; - for (Function &F : M) - if (!AliveGlobals.count(&F)) { - DeadFunctions.push_back(&F); // Keep track of dead globals + SmallVector DeadFunctions; + for(Function& F : M) { + if(LiveGVs_.count(&F) == 0) { + DeadFunctions.push_back(&F); if (!F.isDeclaration()) F.deleteBody(); } + } // The third pass drops targets of aliases which are dead... - std::vector DeadAliases; - for (GlobalAlias &GA : M.aliases()) - if (!AliveGlobals.count(&GA)) { + SmallVector DeadAliases; + for(auto& GA : M.aliases()) { + if(LiveGVs_.count(&GA) == 0) { DeadAliases.push_back(&GA); GA.setAliasee(nullptr); } + } - // The third pass drops targets of ifuncs which are dead... - std::vector DeadIFuncs; - for (GlobalIFunc &GIF : M.ifuncs()) - if (!AliveGlobals.count(&GIF)) { + // The fourth pass drops targets of ifuncs which are dead... + SmallVector DeadIFuncs; + for (GlobalIFunc &GIF : M.ifuncs()) { + if(LiveGVs_.count(&GIF) == 0) { DeadIFuncs.push_back(&GIF); GIF.setResolver(nullptr); } + } + // Now that all interferences have been dropped, delete the actual objects // themselves. @@ -171,85 +247,31 @@ }; NumFunctions += DeadFunctions.size(); - for (Function *F : DeadFunctions) - EraseUnusedGlobalValue(F); + for(auto* DGV : DeadFunctions) + EraseUnusedGlobalValue(DGV); NumVariables += DeadGlobalVars.size(); - for (GlobalVariable *GV : DeadGlobalVars) - EraseUnusedGlobalValue(GV); + for(auto* DGV : DeadGlobalVars) + EraseUnusedGlobalValue(DGV); NumAliases += DeadAliases.size(); - for (GlobalAlias *GA : DeadAliases) - EraseUnusedGlobalValue(GA); + for(auto* DGV : DeadAliases) + EraseUnusedGlobalValue(DGV); NumIFuncs += DeadIFuncs.size(); - for (GlobalIFunc *GIF : DeadIFuncs) - EraseUnusedGlobalValue(GIF); + for(auto* DGV : DeadIFuncs) + EraseUnusedGlobalValue(DGV); - // Make sure that all memory is released - AliveGlobals.clear(); - SeenConstants.clear(); - ComdatMembers.clear(); + LiveGVs_.clear(); + DependenciesCache_.clear(); + GVDependencies_.clear(); + ComdatMembers_.clear(); if (Changed) return PreservedAnalyses::none(); 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