lib/Transforms/IPO/GlobalDCE.cpp

   1 //===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===//
   2 //
   3 // This transform is designed to eliminate unreachable internal globals from the
   4 // program.  It uses an aggressive algorithm, searching out globals that are
   5 // known to be alive.  After it finds all of the globals which are needed, it
   6 // deletes whatever is left over.  This allows it to delete recursive chunks of
   7 // the program which are unreachable.
   8 //
   9 //===----------------------------------------------------------------------===//
  10
  11 #include "llvm/Transforms/IPO.h"
  12 #include "llvm/Constants.h"
  13 #include "llvm/Module.h"
  14 #include "llvm/Pass.h"
  15 #include "Support/Statistic.h"
  16 #include <set>
  17
  18 namespace {
  19   Statistic<> NumFunctions("globaldce","Number of functions removed");
  20   Statistic<> NumVariables("globaldce","Number of global variables removed");
  21   Statistic<> NumCPRs("globaldce", "Number of const pointer refs removed");
  22
  23   struct GlobalDCE : public Pass {
  24     // run - Do the GlobalDCE pass on the specified module, optionally updating
  25     // the specified callgraph to reflect the changes.
  26     //
  27     bool run(Module &M);
  28
  29   private:
  30     std::set<GlobalValue*> AliveGlobals;
  31
  32     /// MarkGlobalIsNeeded - the specific global value as needed, and
  33     /// recursively mark anything that it uses as also needed.
  34     void GlobalIsNeeded(GlobalValue *GV);
  35     void MarkUsedGlobalsAsNeeded(Constant *C);
  36
  37     bool RemoveUnusedConstantPointerRef(GlobalValue &GV);
  38     bool SafeToDestroyConstant(Constant *C);
  39   };
  40   RegisterOpt<GlobalDCE> X("globaldce", "Dead Global Elimination");
  41 }
  42
  43 Pass *createGlobalDCEPass() { return new GlobalDCE(); }
  44
  45 bool GlobalDCE::run(Module &M) {
  46   bool Changed = false;
  47   // Loop over the module, adding globals which are obviously necessary.
  48   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
  49     Changed |= RemoveUnusedConstantPointerRef(*I);
  50     // Functions with external linkage are needed if they have a body
  51     if (I->hasExternalLinkage() && !I->isExternal())
  52       GlobalIsNeeded(I);
  53   }
  54
  55   for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I) {
  56     Changed |= RemoveUnusedConstantPointerRef(*I);
  57     // Externally visible globals are needed, if they have an initializer.
  58     if (I->hasExternalLinkage() && !I->isExternal())
  59       GlobalIsNeeded(I);
  60   }
  61
  62
  63   // Now that all globals which are needed are in the AliveGlobals set, we loop
  64   // through the program, deleting those which are not alive.
  65   //
  66
  67   // The first pass is to drop initializers of global variables which are dead.
  68   std::vector<GlobalVariable*> DeadGlobalVars;   // Keep track of dead globals
  69   for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I)
  70     if (!AliveGlobals.count(I)) {
  71       DeadGlobalVars.push_back(I);         // Keep track of dead globals
  72       I->setInitializer(0);
  73     }
  74
  75
  76   // The second pass drops the bodies of functions which are dead...
  77   std::vector<Function*> DeadFunctions;
  78   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  79     if (!AliveGlobals.count(I)) {
  80       DeadFunctions.push_back(I);         // Keep track of dead globals
  81       if (!I->isExternal())
  82         I->deleteBody();
  83     }
  84
  85   if (!DeadFunctions.empty()) {
  86     // Now that all interreferences have been dropped, delete the actual objects
  87     // themselves.
  88     for (unsigned i = 0, e = DeadFunctions.size(); i != e; ++i) {
  89       RemoveUnusedConstantPointerRef(*DeadFunctions[i]);
  90       M.getFunctionList().erase(DeadFunctions[i]);
  91     }
  92     NumFunctions += DeadFunctions.size();
  93     Changed = true;
  94   }
  95
  96   if (!DeadGlobalVars.empty()) {
  97     for (unsigned i = 0, e = DeadGlobalVars.size(); i != e; ++i) {
  98       RemoveUnusedConstantPointerRef(*DeadGlobalVars[i]);
  99       M.getGlobalList().erase(DeadGlobalVars[i]);
 100     }
 101     NumVariables += DeadGlobalVars.size();
 102     Changed = true;
 103   }
 104
 105   // Make sure that all memory is released
 106   AliveGlobals.clear();
 107   return Changed;
 108 }
 109
 110 /// MarkGlobalIsNeeded - the specific global value as needed, and
 111 /// recursively mark anything that it uses as also needed.
 112 void GlobalDCE::GlobalIsNeeded(GlobalValue *G) {
 113   std::set<GlobalValue*>::iterator I = AliveGlobals.lower_bound(G);
 114
 115   // If the global is already in the set, no need to reprocess it.
 116   if (I != AliveGlobals.end() && *I == G) return;
 117
 118   // Otherwise insert it now, so we do not infinitely recurse
 119   AliveGlobals.insert(I, G);
 120
 121   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G)) {
 122     // If this is a global variable, we must make sure to add any global values
 123     // referenced by the initializer to the alive set.
 124     if (GV->hasInitializer())
 125       MarkUsedGlobalsAsNeeded(GV->getInitializer());
 126   } else {
 127     // Otherwise this must be a function object.  We have to scan the body of
 128     // the function looking for constants and global values which are used as
 129     // operands.  Any operands of these types must be processed to ensure that
 130     // any globals used will be marked as needed.
 131     Function *F = cast<Function>(G);
 132     // For all basic blocks...
 133     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
 134       // For all instructions...
 135       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 136         // For all operands...
 137         for (User::op_iterator U = I->op_begin(), E = I->op_end(); U != E; ++U)
 138           if (GlobalValue *GV = dyn_cast<GlobalValue>(*U))
 139             GlobalIsNeeded(GV);
 140           else if (Constant *C = dyn_cast<Constant>(*U))
 141             MarkUsedGlobalsAsNeeded(C);
 142   }
 143 }
 144
 145 void GlobalDCE::MarkUsedGlobalsAsNeeded(Constant *C) {
 146   if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C))
 147     GlobalIsNeeded(CPR->getValue());
 148   else {
 149     // Loop over all of the operands of the constant, adding any globals they
 150     // use to the list of needed globals.
 151     for (User::op_iterator I = C->op_begin(), E = C->op_end(); I != E; ++I)
 152       MarkUsedGlobalsAsNeeded(cast<Constant>(*I));
 153   }
 154 }
 155
 156 // RemoveUnusedConstantPointerRef - Loop over all of the uses of the specified
 157 // GlobalValue, looking for the constant pointer ref that may be pointing to it.
 158 // If found, check to see if the constant pointer ref is safe to destroy, and if
 159 // so, nuke it.  This will reduce the reference count on the global value, which
 160 // might make it deader.
 161 //
 162 bool GlobalDCE::RemoveUnusedConstantPointerRef(GlobalValue &GV) {
 163   for (Value::use_iterator I = GV.use_begin(), E = GV.use_end(); I != E; ++I)
 164     if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(*I))
 165       if (SafeToDestroyConstant(CPR)) {  // Only if unreferenced...
 166         CPR->destroyConstant();
 167         ++NumCPRs;
 168         return true;
 169       }
 170
 171   return false;
 172 }
 173
 174 // SafeToDestroyConstant - It is safe to destroy a constant iff it is only used
 175 // by constants itself.  Note that constants cannot be cyclic, so this test is
 176 // pretty easy to implement recursively.
 177 //
 178 bool GlobalDCE::SafeToDestroyConstant(Constant *C) {
 179   for (Value::use_iterator I = C->use_begin(), E = C->use_end(); I != E; ++I)
 180     if (Constant *User = dyn_cast<Constant>(*I)) {
 181       if (!SafeToDestroyConstant(User)) return false;
 182     } else {
 183       return false;
 184     }
 185
 186   return true;
 187 }