X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FGlobalDCE.cpp;h=9b276ed28e2e0e14604c97a78f5608747b4e492d;hp=aa18601b9aecaf8a2cb17315df28332257426b1f;hb=638b75bca2096456dce341ddc159d038c7e94712;hpb=90c579de5a383cee278acc3f7e7b9d0a656e6a35 diff --git a/lib/Transforms/IPO/GlobalDCE.cpp b/lib/Transforms/IPO/GlobalDCE.cpp index aa18601b9ae..9b276ed28e2 100644 --- a/lib/Transforms/IPO/GlobalDCE.cpp +++ b/lib/Transforms/IPO/GlobalDCE.cpp @@ -15,15 +15,20 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "globaldce" #include "llvm/Transforms/IPO.h" -#include "llvm/Constants.h" -#include "llvm/Module.h" -#include "llvm/Pass.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/Statistic.h" +#include "llvm/IR/Constants.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" +#include "llvm/Transforms/Utils/CtorUtils.h" +#include "llvm/Transforms/Utils/GlobalStatus.h" +#include "llvm/Pass.h" +#include using namespace llvm; +#define DEBUG_TYPE "globaldce" + STATISTIC(NumAliases , "Number of global aliases removed"); STATISTIC(NumFunctions, "Number of functions removed"); STATISTIC(NumVariables, "Number of global variables removed"); @@ -31,15 +36,19 @@ STATISTIC(NumVariables, "Number of global variables removed"); namespace { struct GlobalDCE : public ModulePass { static char ID; // Pass identification, replacement for typeid - GlobalDCE() : ModulePass(ID) {} + GlobalDCE() : ModulePass(ID) { + initializeGlobalDCEPass(*PassRegistry::getPassRegistry()); + } // run - Do the GlobalDCE pass on the specified module, optionally updating // the specified callgraph to reflect the changes. // - bool runOnModule(Module &M); + bool runOnModule(Module &M) override; private: SmallPtrSet AliveGlobals; + SmallPtrSet SeenConstants; + std::unordered_multimap ComdatMembers; /// GlobalIsNeeded - mark the specific global value as needed, and /// recursively mark anything that it uses as also needed. @@ -50,40 +59,61 @@ namespace { }; } +/// Returns true if F contains only a single "ret" instruction. +static bool isEmptyFunction(Function *F) { + BasicBlock &Entry = F->getEntryBlock(); + if (Entry.size() != 1 || !isa(Entry.front())) + return false; + ReturnInst &RI = cast(Entry.front()); + return RI.getReturnValue() == nullptr; +} + char GlobalDCE::ID = 0; INITIALIZE_PASS(GlobalDCE, "globaldce", - "Dead Global Elimination", false, false); + "Dead Global Elimination", false, false) ModulePass *llvm::createGlobalDCEPass() { return new GlobalDCE(); } bool GlobalDCE::runOnModule(Module &M) { bool Changed = false; - + + // Remove empty functions from the global ctors list. + Changed |= optimizeGlobalCtorsList(M, isEmptyFunction); + + // Collect the set of members for each comdat. + for (Function &F : M) + if (Comdat *C = F.getComdat()) + ComdatMembers.insert(std::make_pair(C, &F)); + for (GlobalVariable &GV : M.globals()) + if (Comdat *C = GV.getComdat()) + ComdatMembers.insert(std::make_pair(C, &GV)); + for (GlobalAlias &GA : M.aliases()) + if (Comdat *C = GA.getComdat()) + ComdatMembers.insert(std::make_pair(C, &GA)); + // Loop over the module, adding globals which are obviously necessary. - for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { - Changed |= RemoveUnusedGlobalValue(*I); + for (Function &F : M) { + Changed |= RemoveUnusedGlobalValue(F); // Functions with external linkage are needed if they have a body - if (!I->hasLocalLinkage() && !I->hasLinkOnceLinkage() && - !I->isDeclaration() && !I->hasAvailableExternallyLinkage()) - GlobalIsNeeded(I); + if (!F.isDeclaration() && !F.hasAvailableExternallyLinkage()) + if (!F.isDiscardableIfUnused()) + GlobalIsNeeded(&F); } - for (Module::global_iterator I = M.global_begin(), E = M.global_end(); - I != E; ++I) { - Changed |= RemoveUnusedGlobalValue(*I); + for (GlobalVariable &GV : M.globals()) { + Changed |= RemoveUnusedGlobalValue(GV); // Externally visible & appending globals are needed, if they have an // initializer. - if (!I->hasLocalLinkage() && !I->hasLinkOnceLinkage() && - !I->isDeclaration() && !I->hasAvailableExternallyLinkage()) - GlobalIsNeeded(I); + if (!GV.isDeclaration() && !GV.hasAvailableExternallyLinkage()) + if (!GV.isDiscardableIfUnused()) + GlobalIsNeeded(&GV); } - for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); - I != E; ++I) { - Changed |= RemoveUnusedGlobalValue(*I); + for (GlobalAlias &GA : M.aliases()) { + Changed |= RemoveUnusedGlobalValue(GA); // Externally visible aliases are needed. - if (!I->hasLocalLinkage() && !I->hasLinkOnceLinkage()) - GlobalIsNeeded(I); + if (!GA.isDiscardableIfUnused()) + GlobalIsNeeded(&GA); } // Now that all globals which are needed are in the AliveGlobals set, we loop @@ -91,47 +121,50 @@ bool GlobalDCE::runOnModule(Module &M) { // // The first pass is to drop initializers of global variables which are dead. - std::vector DeadGlobalVars; // Keep track of dead globals - for (Module::global_iterator I = M.global_begin(), E = M.global_end(); - I != E; ++I) - if (!AliveGlobals.count(I)) { - DeadGlobalVars.push_back(I); // Keep track of dead globals - I->setInitializer(0); + 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()) { + 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 (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) - if (!AliveGlobals.count(I)) { - DeadFunctions.push_back(I); // Keep track of dead globals - if (!I->isDeclaration()) - I->deleteBody(); + std::vector DeadFunctions; + for (Function &F : M) + if (!AliveGlobals.count(&F)) { + DeadFunctions.push_back(&F); // Keep track of dead globals + if (!F.isDeclaration()) + F.deleteBody(); } // The third pass drops targets of aliases which are dead... std::vector DeadAliases; - for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); I != E; - ++I) - if (!AliveGlobals.count(I)) { - DeadAliases.push_back(I); - I->setAliasee(0); + for (GlobalAlias &GA : M.aliases()) + if (!AliveGlobals.count(&GA)) { + DeadAliases.push_back(&GA); + GA.setAliasee(nullptr); } if (!DeadFunctions.empty()) { // Now that all interferences have been dropped, delete the actual objects // themselves. - for (unsigned i = 0, e = DeadFunctions.size(); i != e; ++i) { - RemoveUnusedGlobalValue(*DeadFunctions[i]); - M.getFunctionList().erase(DeadFunctions[i]); + for (Function *F : DeadFunctions) { + RemoveUnusedGlobalValue(*F); + M.getFunctionList().erase(F); } NumFunctions += DeadFunctions.size(); Changed = true; } if (!DeadGlobalVars.empty()) { - for (unsigned i = 0, e = DeadGlobalVars.size(); i != e; ++i) { - RemoveUnusedGlobalValue(*DeadGlobalVars[i]); - M.getGlobalList().erase(DeadGlobalVars[i]); + for (GlobalVariable *GV : DeadGlobalVars) { + RemoveUnusedGlobalValue(*GV); + M.getGlobalList().erase(GV); } NumVariables += DeadGlobalVars.size(); Changed = true; @@ -139,9 +172,9 @@ bool GlobalDCE::runOnModule(Module &M) { // Now delete any dead aliases. if (!DeadAliases.empty()) { - for (unsigned i = 0, e = DeadAliases.size(); i != e; ++i) { - RemoveUnusedGlobalValue(*DeadAliases[i]); - M.getAliasList().erase(DeadAliases[i]); + for (GlobalAlias *GA : DeadAliases) { + RemoveUnusedGlobalValue(*GA); + M.getAliasList().erase(GA); } NumAliases += DeadAliases.size(); Changed = true; @@ -149,6 +182,8 @@ bool GlobalDCE::runOnModule(Module &M) { // Make sure that all memory is released AliveGlobals.clear(); + SeenConstants.clear(); + ComdatMembers.clear(); return Changed; } @@ -157,9 +192,14 @@ bool GlobalDCE::runOnModule(Module &M) { /// recursively mark anything that it uses as also needed. void GlobalDCE::GlobalIsNeeded(GlobalValue *G) { // If the global is already in the set, no need to reprocess it. - if (!AliveGlobals.insert(G)) + 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. @@ -175,12 +215,15 @@ void GlobalDCE::GlobalIsNeeded(GlobalValue *G) { // any globals used will be marked as needed. Function *F = cast(G); - for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) - for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) - for (User::op_iterator U = I->op_begin(), E = I->op_end(); U != E; ++U) - if (GlobalValue *GV = dyn_cast(*U)) + 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)) + else if (Constant *C = dyn_cast(U)) MarkUsedGlobalsAsNeeded(C); } } @@ -188,12 +231,15 @@ void GlobalDCE::GlobalIsNeeded(GlobalValue *G) { void GlobalDCE::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 (User::op_iterator I = C->op_begin(), E = C->op_end(); I != E; ++I) - if (Constant *OpC = dyn_cast(*I)) - MarkUsedGlobalsAsNeeded(OpC); + 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 @@ -203,7 +249,8 @@ void GlobalDCE::MarkUsedGlobalsAsNeeded(Constant *C) { // might make it deader. // bool GlobalDCE::RemoveUnusedGlobalValue(GlobalValue &GV) { - if (GV.use_empty()) return false; + if (GV.use_empty()) + return false; GV.removeDeadConstantUsers(); return GV.use_empty(); }