X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FGlobalDCE.cpp;h=1bb823dde99039645ddcd174f35084fd4026e4e1;hb=e4314ed3154f168cc9324e2e213c2733c2b71761;hp=4edfb3950eafab1efda33435056e3a915e018c16;hpb=f0cd4722bfb8fe9ac105f4fed54441b054781573;p=oota-llvm.git diff --git a/lib/Transforms/IPO/GlobalDCE.cpp b/lib/Transforms/IPO/GlobalDCE.cpp index 4edfb3950ea..1bb823dde99 100644 --- a/lib/Transforms/IPO/GlobalDCE.cpp +++ b/lib/Transforms/IPO/GlobalDCE.cpp @@ -5,15 +5,20 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/IPO/GlobalDCE.h" +#include "llvm/Transforms/IPO.h" #include "llvm/Module.h" -#include "llvm/Function.h" +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" #include "llvm/GlobalVariable.h" #include "llvm/Analysis/CallGraph.h" #include "Support/DepthFirstIterator.h" #include "Support/StatisticReporter.h" +#include -static Statistic<> NumRemoved("globaldce\t- Number of global values removed"); +static Statistic<> NumFunctions("globaldce\t- Number of functions removed"); +static Statistic<> NumVariables("globaldce\t- Number of global variables removed"); +static Statistic<> NumCPRs("globaldce\t- Number of const pointer refs removed"); +static Statistic<> NumConsts("globaldce\t- Number of init constants removed"); static bool RemoveUnreachableFunctions(Module &M, CallGraph &CallGraph) { // Calculate which functions are reachable from the external functions in the @@ -34,7 +39,7 @@ static bool RemoveUnreachableFunctions(Module &M, CallGraph &CallGraph) { I->dropAllReferences(); N->removeAllCalledFunctions(); FunctionsToDelete.push_back(N); - ++NumRemoved; + ++NumFunctions; } } @@ -51,26 +56,8 @@ static bool RemoveUnreachableFunctions(Module &M, CallGraph &CallGraph) { return true; } -static bool RemoveUnreachableGlobalVariables(Module &M) { - bool Changed = false; - // Eliminate all global variables that are unused, and that are internal, or - // do not have an initializer. - // - for (Module::giterator I = M.gbegin(); I != M.gend(); ) - if (!I->use_empty() || (I->hasExternalLinkage() && I->hasInitializer())) - ++I; // Cannot eliminate global variable - else { - I = M.getGlobalList().erase(I); - ++NumRemoved; - Changed = true; - } - return Changed; -} - namespace { struct GlobalDCE : public Pass { - const char *getPassName() const { return "Dead Global Elimination"; } - // run - Do the GlobalDCE pass on the specified module, optionally updating // the specified callgraph to reflect the changes. // @@ -84,9 +71,181 @@ namespace { // module. // virtual void getAnalysisUsage(AnalysisUsage &AU) const { - AU.addRequired(CallGraph::ID); + AU.addRequired(); } + + private: + std::vector WorkList; + + inline bool RemoveIfDead(GlobalValue *GV); + void DestroyInitializer(Constant *C); + + bool RemoveUnreachableGlobalVariables(Module &M); + bool RemoveUnusedConstantPointerRef(GlobalValue &GV); + bool SafeToDestroyConstant(Constant *C); }; + RegisterOpt X("globaldce", "Dead Global Elimination"); } Pass *createGlobalDCEPass() { return new GlobalDCE(); } + + +// RemoveIfDead - If this global value is dead, remove it from the current +// module and return true. +// +bool GlobalDCE::RemoveIfDead(GlobalValue *GV) { + // If there is only one use of the global value, it might be a + // ConstantPointerRef... which means that this global might actually be + // dead. + if (GV->use_size() == 1) + RemoveUnusedConstantPointerRef(*GV); + + if (!GV->use_empty()) return false; + + if (GlobalVariable *GVar = dyn_cast(GV)) { + // Eliminate all global variables that are unused, and that are internal, or + // do not have an initializer. + // + if (!GVar->hasExternalLinkage() || !GVar->hasInitializer()) { + Constant *Init = GVar->hasInitializer() ? GVar->getInitializer() : 0; + GV->getParent()->getGlobalList().erase(GVar); + ++NumVariables; + + // If there was an initializer for the global variable, try to destroy it + // now. + if (Init) DestroyInitializer(Init); + + // If the global variable is still on the worklist, remove it now. + std::vector::iterator I = std::find(WorkList.begin(), + WorkList.end(), GV); + while (I != WorkList.end()) + I = std::find(WorkList.erase(I), WorkList.end(), GV); + + return true; + } + } else { + Function *F = cast(GV); + // FIXME: TODO + + } + return false; +} + +// DestroyInitializer - A global variable was just destroyed and C is its +// initializer. If we can, destroy C and all of the constants it refers to. +// +void GlobalDCE::DestroyInitializer(Constant *C) { + // Cannot destroy constants still being used, and cannot destroy primitive + // types. + if (!C->use_empty() || C->getType()->isPrimitiveType()) return; + + // If this is a CPR, the global value referred to may be dead now! Add it to + // the worklist. + // + if (ConstantPointerRef *CPR = dyn_cast(C)) { + WorkList.push_back(CPR->getValue()); + C->destroyConstant(); + ++NumCPRs; + } else { + bool DestroyContents = true; + + // As an optimization to the GlobalDCE algorithm, do attempt to destroy the + // contents of an array of primitive types, because we know that this will + // never succeed, and there could be a lot of them. + // + if (ConstantArray *CA = dyn_cast(C)) + if (CA->getType()->getElementType()->isPrimitiveType()) + DestroyContents = false; // Nothing we can do with the subcontents + + // All other constants refer to other constants. Destroy them if possible + // as well. + // + std::vector SubConstants; + if (DestroyContents) SubConstants.insert(SubConstants.end(), + C->op_begin(), C->op_end()); + + // Destroy the actual constant... + C->destroyConstant(); + ++NumConsts; + + if (DestroyContents) { + // Remove duplicates from SubConstants, so that we do not call + // DestroyInitializer on the same constant twice (the first call might + // delete it, so this would be bad) + // + std::sort(SubConstants.begin(), SubConstants.end()); + SubConstants.erase(std::unique(SubConstants.begin(), SubConstants.end()), + SubConstants.end()); + + // Loop over the subconstants, destroying them as well. + for (unsigned i = 0, e = SubConstants.size(); i != e; ++i) + DestroyInitializer(cast(SubConstants[i])); + } + } +} + +bool GlobalDCE::RemoveUnreachableGlobalVariables(Module &M) { + bool Changed = false; + WorkList.reserve(M.gsize()); + + // Insert all of the globals into the WorkList, making sure to run + // RemoveUnusedConstantPointerRef at least once on all globals... + // + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { + Changed |= RemoveUnusedConstantPointerRef(*I); + WorkList.push_back(I); + } + for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I) { + Changed |= RemoveUnusedConstantPointerRef(*I); + WorkList.push_back(I); + } + + // Loop over the worklist, deleting global objects that we can. Whenever we + // delete something that might make something else dead, it gets added to the + // worklist. + // + while (!WorkList.empty()) { + GlobalValue *GV = WorkList.back(); + WorkList.pop_back(); + + Changed |= RemoveIfDead(GV); + } + + // Make sure that all memory is free'd from the worklist... + std::vector().swap(WorkList); + return Changed; +} + + +// RemoveUnusedConstantPointerRef - 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 +// so, nuke it. This will reduce the reference count on the global value, which +// might make it deader. +// +bool GlobalDCE::RemoveUnusedConstantPointerRef(GlobalValue &GV) { + for (Value::use_iterator I = GV.use_begin(), E = GV.use_end(); I != E; ++I) + if (ConstantPointerRef *CPR = dyn_cast(*I)) + if (SafeToDestroyConstant(CPR)) { // Only if unreferenced... + CPR->destroyConstant(); + ++NumCPRs; + return true; + } + + return false; +} + +// 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; +}