X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FTransforms%2FIPO%2FGlobalDCE.cpp;h=1bb823dde99039645ddcd174f35084fd4026e4e1;hb=e4314ed3154f168cc9324e2e213c2733c2b71761;hp=664381cec684ee50162368ae724d48a754b3ddfe;hpb=f4de63f65fa995e68e3cd268117ab065068be413;p=oota-llvm.git diff --git a/lib/Transforms/IPO/GlobalDCE.cpp b/lib/Transforms/IPO/GlobalDCE.cpp index 664381cec68..1bb823dde99 100644 --- a/lib/Transforms/IPO/GlobalDCE.cpp +++ b/lib/Transforms/IPO/GlobalDCE.cpp @@ -1,53 +1,251 @@ -//===-- GlobalDCE.cpp - DCE unreachable internal methods ---------*- C++ -*--=// +//===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===// // // This transform is designed to eliminate unreachable internal globals +// FIXME: GlobalDCE should update the callgraph, not destroy it! // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/IPO/GlobalDCE.h" -#include "llvm/Analysis/CallGraph.h" +#include "llvm/Transforms/IPO.h" #include "llvm/Module.h" -#include "llvm/Method.h" +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" +#include "llvm/GlobalVariable.h" +#include "llvm/Analysis/CallGraph.h" #include "Support/DepthFirstIterator.h" -#include +#include "Support/StatisticReporter.h" +#include -static bool RemoveUnreachableMethods(Module *M, cfg::CallGraph &CallGraph) { - // Calculate which methods are reachable from the external methods in the call - // graph. +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 + // call graph. // - std::set ReachableNodes(df_begin(&CallGraph), - df_end(&CallGraph)); + std::set ReachableNodes(df_begin(&CallGraph), + df_end(&CallGraph)); - // Loop over the methods in the module twice. The first time is used to drop - // references that methods have to each other before they are deleted. The - // second pass removes the methods that need to be removed. + // Loop over the functions in the module twice. The first time is used to + // drop references that functions have to each other before they are deleted. + // The second pass removes the functions that need to be removed. // - std::vector MethodsToDelete; // Track unused methods - for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) { - cfg::CallGraphNode *N = CallGraph[*I]; + std::vector FunctionsToDelete; // Track unused functions + for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { + CallGraphNode *N = CallGraph[I]; + if (!ReachableNodes.count(N)) { // Not reachable?? - (*I)->dropAllReferences(); - N->removeAllCalledMethods(); - MethodsToDelete.push_back(N); + I->dropAllReferences(); + N->removeAllCalledFunctions(); + FunctionsToDelete.push_back(N); + ++NumFunctions; } } - // Nothing to do if no unreachable methods have been found... - if (MethodsToDelete.empty()) return false; + // Nothing to do if no unreachable functions have been found... + if (FunctionsToDelete.empty()) return false; - // Unreachables methods have been found and should have no references to them, - // delete them now. + // Unreachables functions have been found and should have no references to + // them, delete them now. // - for (std::vector::iterator I = MethodsToDelete.begin(), - E = MethodsToDelete.end(); I != E; ++I) - delete CallGraph.removeMethodFromModule(*I); + for (std::vector::iterator I = FunctionsToDelete.begin(), + E = FunctionsToDelete.end(); I != E; ++I) + delete CallGraph.removeFunctionFromModule(*I); return true; } -bool GlobalDCE::run(Module *M) { - // TODO: FIXME: GET THE CALL GRAPH FROM THE PASS! - // Create a call graph if one is not already available... - cfg::CallGraph CallGraph(M); - return RemoveUnreachableMethods(M, CallGraph); +namespace { + 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) { + return RemoveUnreachableFunctions(M, getAnalysis()) | + RemoveUnreachableGlobalVariables(M); + } + + // getAnalysisUsage - This function works on the call graph of a module. + // It is capable of updating the call graph to reflect the new state of the + // module. + // + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + 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; }