X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FGlobalDCE.cpp;h=cdad155a0b3f3b9deec13a97d717589ab4a2f6ff;hp=e025813fd07cccdefb4e4a85a37aed7c3369a5b7;hb=5b55a47e94e28fbb56d0cd5d72c3db9105c15b4c;hpb=25c6d68029dc0e45dce5f6aa08c5e868b8a923fa diff --git a/lib/Transforms/IPO/GlobalDCE.cpp b/lib/Transforms/IPO/GlobalDCE.cpp index e025813fd07..cdad155a0b3 100644 --- a/lib/Transforms/IPO/GlobalDCE.cpp +++ b/lib/Transforms/IPO/GlobalDCE.cpp @@ -1,10 +1,10 @@ //===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===// -// +// // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// //===----------------------------------------------------------------------===// // // This transform is designed to eliminate unreachable internal globals from the @@ -16,59 +16,125 @@ //===----------------------------------------------------------------------===// #include "llvm/Transforms/IPO.h" -#include "llvm/Constants.h" -#include "llvm/Module.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/Pass.h" -#include "Support/Statistic.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"); + namespace { - Statistic<> NumFunctions("globaldce","Number of functions removed"); - Statistic<> NumVariables("globaldce","Number of global variables removed"); + struct GlobalDCE : public ModulePass { + static char ID; // Pass identification, replacement for typeid + GlobalDCE() : ModulePass(ID) { + initializeGlobalDCEPass(*PassRegistry::getPassRegistry()); + } - struct GlobalDCE : public Pass { // run - Do the GlobalDCE pass on the specified module, optionally updating // the specified callgraph to reflect the changes. // - bool run(Module &M); + bool runOnModule(Module &M) override; private: - std::set AliveGlobals; + SmallPtrSet AliveGlobals; + SmallPtrSet SeenConstants; + SmallPtrSet DiscardableGlobalInitializers; - /// MarkGlobalIsNeeded - the specific global value as needed, and + /// GlobalIsNeeded - 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); - bool SafeToDestroyConstant(Constant* C); + /// \brief Checks if C is alive or is a ConstantExpr that refers to an alive + /// value. + bool ContainsUsedGlobal(Constant *C); + bool RemoveUnusedGlobalValue(GlobalValue &GV); }; - RegisterOpt X("globaldce", "Dead Global Elimination"); } -Pass *llvm::createGlobalDCEPass() { return new GlobalDCE(); } +/// 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) + +ModulePass *llvm::createGlobalDCEPass() { return new GlobalDCE(); } -bool GlobalDCE::run(Module &M) { +bool GlobalDCE::runOnModule(Module &M) { bool Changed = false; + + // Remove empty functions from the global ctors list. + Changed |= optimizeGlobalCtorsList(M, isEmptyFunction); + + typedef std::multimap ComdatGVPairsTy; + ComdatGVPairsTy ComdatGVPairs; + // 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); // Functions with external linkage are needed if they have a body - if ((!I->hasInternalLinkage() && !I->hasLinkOnceLinkage()) && - !I->isExternal()) - GlobalIsNeeded(I); + if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage()) { + if (!I->isDiscardableIfUnused()) + GlobalIsNeeded(I); + else if (const Comdat *C = I->getComdat()) + ComdatGVPairs.insert(std::make_pair(C, I)); + } } - for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I) { + for (Module::global_iterator I = M.global_begin(), E = M.global_end(); + I != E; ++I) { Changed |= RemoveUnusedGlobalValue(*I); // Externally visible & appending globals are needed, if they have an // initializer. - if ((!I->hasInternalLinkage() && !I->hasLinkOnceLinkage()) && - !I->isExternal()) + if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage()) { + if (!I->isDiscardableIfUnused()) + GlobalIsNeeded(I); + else if (const Comdat *C = I->getComdat()) + ComdatGVPairs.insert(std::make_pair(C, I)); + } + } + + for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); + I != E; ++I) { + Changed |= RemoveUnusedGlobalValue(*I); + // Externally visible aliases are needed. + if (!I->isDiscardableIfUnused()) { GlobalIsNeeded(I); + } else if (const Comdat *C = I->getComdat()) { + ComdatGVPairs.insert(std::make_pair(C, I)); + } } + for (ComdatGVPairsTy::iterator I = ComdatGVPairs.begin(), + E = ComdatGVPairs.end(); + I != E;) { + ComdatGVPairsTy::iterator UB = ComdatGVPairs.upper_bound(I->first); + bool CanDiscard = std::all_of(I, UB, [](ComdatGVPairsTy::value_type Pair) { + return Pair.second->isDiscardableIfUnused(); + }); + if (!CanDiscard) { + std::for_each(I, UB, [this](ComdatGVPairsTy::value_type Pair) { + GlobalIsNeeded(Pair.second); + }); + } + I = UB; + } // Now that all globals which are needed are in the AliveGlobals set, we loop // through the program, deleting those which are not alive. @@ -76,24 +142,46 @@ bool GlobalDCE::run(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::giterator I = M.gbegin(), E = M.gend(); I != E; ++I) + 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); + I->setInitializer(nullptr); } - // 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->isExternal()) + if (!I->isDeclaration()) I->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(nullptr); + } + + // Look for available externally constants that we can turn into normal + // externals by deleting their initalizers. This allows us to remove other + // globals that are referenced by the initializer. + if (!DiscardableGlobalInitializers.empty()) { + for (GlobalVariable *GV : DiscardableGlobalInitializers) { + if (!ContainsUsedGlobal(GV->getInitializer())) { + GV->setInitializer(nullptr); + GV->setLinkage(GlobalValue::ExternalLinkage); + Changed = true; + } + } + } + if (!DeadFunctions.empty()) { - // Now that all interreferences have been dropped, delete the actual objects + // 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]); @@ -111,56 +199,90 @@ bool GlobalDCE::run(Module &M) { NumVariables += DeadGlobalVars.size(); Changed = true; } - + + // 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]); + } + NumAliases += DeadAliases.size(); + Changed = true; + } + // Make sure that all memory is released AliveGlobals.clear(); + SeenConstants.clear(); + return Changed; } -/// MarkGlobalIsNeeded - the specific global value as needed, and +/// GlobalIsNeeded - the specific global value as needed, and /// recursively mark anything that it uses as also needed. void GlobalDCE::GlobalIsNeeded(GlobalValue *G) { - std::set::iterator I = AliveGlobals.lower_bound(G); - // If the global is already in the set, no need to reprocess it. - if (I != AliveGlobals.end() && *I == G) return; - - // Otherwise insert it now, so we do not infinitely recurse - AliveGlobals.insert(I, G); - + if (!AliveGlobals.insert(G)) + return; + 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()); + if (GV->hasInitializer()) { + if (GV->hasAvailableExternallyLinkage()) + DiscardableGlobalInitializers.insert(GV); + else + MarkUsedGlobalsAsNeeded(GV->getInitializer()); + } + } else if (GlobalAlias *GA = dyn_cast(G)) { + // The target of a global alias is needed. + MarkUsedGlobalsAsNeeded(GA->getAliasee()); } 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 all basic blocks... + + if (F->hasPrefixData()) + MarkUsedGlobalsAsNeeded(F->getPrefixData()); + for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) - // For all instructions... for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) - // For all operands... for (User::op_iterator U = I->op_begin(), E = I->op_end(); U != E; ++U) if (GlobalValue *GV = dyn_cast(*U)) GlobalIsNeeded(GV); else if (Constant *C = dyn_cast(*U)) - MarkUsedGlobalsAsNeeded(C); + MarkUsedGlobalsAsNeeded(C); } } void GlobalDCE::MarkUsedGlobalsAsNeeded(Constant *C) { if (GlobalValue *GV = dyn_cast(C)) - GlobalIsNeeded(GV); - else { - // 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) - MarkUsedGlobalsAsNeeded(cast(*I)); + 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 we've already processed this constant there's no need to do it again. + Constant *Op = dyn_cast(*I); + if (Op && SeenConstants.insert(Op)) + MarkUsedGlobalsAsNeeded(Op); + } +} + +bool GlobalDCE::ContainsUsedGlobal(Constant *C) { + // C contains a used global If C is alive or we visited it while marking + // values alive. + if (AliveGlobals.count(C) || SeenConstants.count(C)) + return true; + + // Now check all operands of a ConstantExpr. + for (User::op_iterator I = C->op_begin(), E = C->op_end(); I != E; ++I) { + Constant *Op = dyn_cast(*I); + if (Op && ContainsUsedGlobal(Op)) + return true; } + return false; } // RemoveUnusedGlobalValue - Loop over all of the uses of the specified @@ -174,17 +296,3 @@ bool GlobalDCE::RemoveUnusedGlobalValue(GlobalValue &GV) { GV.removeDeadConstantUsers(); return GV.use_empty(); } - -// SafeToDestroyConstant - It is safe to destroy a constant iff it is only used -// by constants itself. Note that constants cannot be cyclic, so this test is -// pretty easy to implement recursively. -// -bool GlobalDCE::SafeToDestroyConstant(Constant *C) { - for (Value::use_iterator I = C->use_begin(), E = C->use_end(); I != E; ++I) - if (Constant *User = dyn_cast(*I)) { - if (!SafeToDestroyConstant(User)) return false; - } else { - return false; - } - return true; -}