lib/Transforms/IPO/GlobalDCE.cpp

   1 //===-- GlobalDCE.cpp - DCE unreachable internal methods ---------*- C++ -*--=//
   2 //
   3 // This transform is designed to eliminate unreachable internal globals
   4 //
   5 //===----------------------------------------------------------------------===//
   6
   7 #include "llvm/Transforms/IPO/GlobalDCE.h"
   8 #include "llvm/Analysis/CallGraph.h"
   9 #include "llvm/Module.h"
  10 #include "llvm/Method.h"
  11 #include "llvm/Pass.h"
  12 #include "Support/DepthFirstIterator.h"
  13 #include <set>
  14
  15 static bool RemoveUnreachableMethods(Module *M, CallGraph &CallGraph) {
  16   // Calculate which methods are reachable from the external methods in the call
  17   // graph.
  18   //
  19   std::set<CallGraphNode*> ReachableNodes(df_begin(&CallGraph),
  20                                           df_end(&CallGraph));
  21
  22   // Loop over the methods in the module twice.  The first time is used to drop
  23   // references that methods have to each other before they are deleted.  The
  24   // second pass removes the methods that need to be removed.
  25   //
  26   std::vector<CallGraphNode*> MethodsToDelete;   // Track unused methods
  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       MethodsToDelete.push_back(N);
  33     }
  34   }
  35
  36   // Nothing to do if no unreachable methods have been found...
  37   if (MethodsToDelete.empty()) return false;
  38
  39   // Unreachables methods have been found and should have no references to them,
  40   // delete them now.
  41   //
  42   for (std::vector<CallGraphNode*>::iterator I = MethodsToDelete.begin(),
  43          E = MethodsToDelete.end(); I != E; ++I)
  44     delete CallGraph.removeMethodFromModule(*I);
  45
  46   return true;
  47 }
  48
  49 namespace {
  50   struct GlobalDCE : public Pass {
  51     // run - Do the GlobalDCE pass on the specified module, optionally updating
  52     // the specified callgraph to reflect the changes.
  53     //
  54     bool run(Module *M) {
  55       return RemoveUnreachableMethods(M, getAnalysis<CallGraph>());
  56     }
  57
  58     // getAnalysisUsageInfo - This function works on the call graph of a module.
  59     // It is capable of updating the call graph to reflect the new state of the
  60     // module.
  61     //
  62     virtual void getAnalysisUsageInfo(Pass::AnalysisSet &Required,
  63                                       Pass::AnalysisSet &Destroyed,
  64                                       Pass::AnalysisSet &Provided) {
  65       Required.push_back(CallGraph::ID);
  66       // FIXME: This should update the callgraph, not destroy it!
  67       Destroyed.push_back(CallGraph::ID);
  68     }
  69   };
  70 }
  71
  72 Pass *createGlobalDCEPass() { return new GlobalDCE(); }