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 "Support/DepthFirstIterator.h"
  12 #include <set>
  13
  14 static bool RemoveUnreachableMethods(Module *M, cfg::CallGraph &CallGraph) {
  15   // Calculate which methods are reachable from the external methods in the call
  16   // graph.
  17   //
  18   std::set<cfg::CallGraphNode*> ReachableNodes(df_begin(&CallGraph),
  19                                                df_end(&CallGraph));
  20
  21   // Loop over the methods in the module twice.  The first time is used to drop
  22   // references that methods have to each other before they are deleted.  The
  23   // second pass removes the methods that need to be removed.
  24   //
  25   std::vector<cfg::CallGraphNode*> MethodsToDelete;   // Track unused methods
  26   for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) {
  27     cfg::CallGraphNode *N = CallGraph[*I];
  28     if (!ReachableNodes.count(N)) {              // Not reachable??
  29       (*I)->dropAllReferences();
  30       N->removeAllCalledMethods();
  31       MethodsToDelete.push_back(N);
  32     }
  33   }
  34
  35   // Nothing to do if no unreachable methods have been found...
  36   if (MethodsToDelete.empty()) return false;
  37
  38   // Unreachables methods have been found and should have no references to them,
  39   // delete them now.
  40   //
  41   for (std::vector<cfg::CallGraphNode*>::iterator I = MethodsToDelete.begin(),
  42          E = MethodsToDelete.end(); I != E; ++I)
  43     delete CallGraph.removeMethodFromModule(*I);
  44
  45   return true;
  46 }
  47
  48 bool GlobalDCE::run(Module *M) {
  49   return RemoveUnreachableMethods(M, getAnalysis<cfg::CallGraph>());
  50 }
  51
  52 // getAnalysisUsageInfo - This function works on the call graph of a module.
  53 // It is capable of updating the call graph to reflect the new state of the
  54 // module.
  55 //
  56 void GlobalDCE::getAnalysisUsageInfo(Pass::AnalysisSet &Required,
  57                                      Pass::AnalysisSet &Destroyed,
  58                                      Pass::AnalysisSet &Provided) {
  59   Required.push_back(cfg::CallGraph::ID);
  60   // FIXME: This should update the callgraph, not destroy it!
  61   Destroyed.push_back(cfg::CallGraph::ID);
  62 }