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/Analysis/CallGraph.h"
  10 #include "llvm/Module.h"
  11 #include "llvm/Function.h"
  12 #include "Support/DepthFirstIterator.h"
  13
  14 static bool RemoveUnreachableFunctions(Module *M, CallGraph &CallGraph) {
  15   // Calculate which functions are reachable from the external functions in the
  16   // call graph.
  17   //
  18   std::set<CallGraphNode*> ReachableNodes(df_begin(&CallGraph),
  19                                           df_end(&CallGraph));
  20
  21   // Loop over the functions in the module twice.  The first time is used to
  22   // drop references that functions have to each other before they are deleted.
  23   // The second pass removes the functions that need to be removed.
  24   //
  25   std::vector<CallGraphNode*> FunctionsToDelete;   // Track unused functions
  26   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) {
  27     CallGraphNode *N = CallGraph[*I];
  28     if (!ReachableNodes.count(N)) {              // Not reachable??
  29       (*I)->dropAllReferences();
  30       N->removeAllCalledMethods();
  31       FunctionsToDelete.push_back(N);
  32     }
  33   }
  34
  35   // Nothing to do if no unreachable functions have been found...
  36   if (FunctionsToDelete.empty()) return false;
  37
  38   // Unreachables functions have been found and should have no references to
  39   // them, delete them now.
  40   //
  41   for (std::vector<CallGraphNode*>::iterator I = FunctionsToDelete.begin(),
  42          E = FunctionsToDelete.end(); I != E; ++I)
  43     delete CallGraph.removeMethodFromModule(*I);
  44
  45   return true;
  46 }
  47
  48 namespace {
  49   struct GlobalDCE : public Pass {
  50     const char *getPassName() const { return "Dead Global Elimination"; }
  51
  52     // run - Do the GlobalDCE pass on the specified module, optionally updating
  53     // the specified callgraph to reflect the changes.
  54     //
  55     bool run(Module *M) {
  56       return RemoveUnreachableFunctions(M, getAnalysis<CallGraph>());
  57     }
  58
  59     // getAnalysisUsage - This function works on the call graph of a module.
  60     // It is capable of updating the call graph to reflect the new state of the
  61     // module.
  62     //
  63     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  64       AU.addRequired(CallGraph::ID);
  65     }
  66   };
  67 }
  68
  69 Pass *createGlobalDCEPass() { return new GlobalDCE(); }