lib/Transforms/IPO/GlobalDCE.cpp

   1 //===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===//
   2 //
   3 // This transform is designed to eliminate unreachable internal globals
   4 // FIXME: GlobalDCE should update the callgraph, not destroy it!
   5 //
   6 //===----------------------------------------------------------------------===//
   7
   8 #include "llvm/Transforms/IPO/GlobalDCE.h"
   9 #include "llvm/Module.h"
  10 #include "llvm/Function.h"
  11 #include "llvm/GlobalVariable.h"
  12 #include "llvm/Analysis/CallGraph.h"
  13 #include "Support/DepthFirstIterator.h"
  14
  15 static bool RemoveUnreachableFunctions(Module *M, CallGraph &CallGraph) {
  16   // Calculate which functions are reachable from the external functions in the
  17   // call graph.
  18   //
  19   std::set<CallGraphNode*> ReachableNodes(df_begin(&CallGraph),
  20                                           df_end(&CallGraph));
  21
  22   // Loop over the functions in the module twice.  The first time is used to
  23   // drop references that functions have to each other before they are deleted.
  24   // The second pass removes the functions that need to be removed.
  25   //
  26   std::vector<CallGraphNode*> FunctionsToDelete;   // Track unused functions
  27   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) {
  28     CallGraphNode *N = CallGraph[*I];
  29     if (!ReachableNodes.count(N)) {              // Not reachable??
  30       (*I)->dropAllReferences();
  31       N->removeAllCalledMethods();
  32       FunctionsToDelete.push_back(N);
  33     }
  34   }
  35
  36   // Nothing to do if no unreachable functions have been found...
  37   if (FunctionsToDelete.empty()) return false;
  38
  39   // Unreachables functions have been found and should have no references to
  40   // them, delete them now.
  41   //
  42   for (std::vector<CallGraphNode*>::iterator I = FunctionsToDelete.begin(),
  43          E = FunctionsToDelete.end(); I != E; ++I)
  44     delete CallGraph.removeMethodFromModule(*I);
  45
  46   return true;
  47 }
  48
  49 static bool RemoveUnreachableGlobalVariables(Module *M) {
  50   bool Changed = false;
  51   // Eliminate all global variables that are unused, and that are internal, or
  52   // do not have an initializer.
  53   //
  54   for (Module::giterator I = M->gbegin(); I != M->gend(); )
  55     if (!(*I)->use_empty() ||
  56         ((*I)->hasExternalLinkage() && (*I)->hasInitializer()))
  57       ++I;                     // Cannot eliminate global variable
  58     else {
  59       delete M->getGlobalList().remove(I);
  60       Changed = true;
  61     }
  62   return Changed;
  63 }
  64
  65 namespace {
  66   struct GlobalDCE : public Pass {
  67     const char *getPassName() const { return "Dead Global Elimination"; }
  68
  69     // run - Do the GlobalDCE pass on the specified module, optionally updating
  70     // the specified callgraph to reflect the changes.
  71     //
  72     bool run(Module *M) {
  73       return RemoveUnreachableFunctions(M, getAnalysis<CallGraph>()) |
  74              RemoveUnreachableGlobalVariables(M);
  75     }
  76
  77     // getAnalysisUsage - This function works on the call graph of a module.
  78     // It is capable of updating the call graph to reflect the new state of the
  79     // module.
  80     //
  81     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  82       AU.addRequired(CallGraph::ID);
  83     }
  84   };
  85 }
  86
  87 Pass *createGlobalDCEPass() { return new GlobalDCE(); }