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->hasInternalLinkage() && !I->hasLinkOnceLinkage()) &&
  52         !I->isExternal())
  53       GlobalIsNeeded(I);
  54   }
  55
  56   for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I) {
  57     Changed |= RemoveUnusedConstantPointerRef(*I);
  58     // Externally visible & appending globals are needed, if they have an
  59     // initializer.
  60     if ((!I->hasInternalLinkage() && !I->hasLinkOnceLinkage()) &&
  61         !I->isExternal())
  62       GlobalIsNeeded(I);
  63   }
  64
  65
  66   // Now that all globals which are needed are in the AliveGlobals set, we loop
  67   // through the program, deleting those which are not alive.
  68   //
  69
  70   // The first pass is to drop initializers of global variables which are dead.
  71   std::vector<GlobalVariable*> DeadGlobalVars;   // Keep track of dead globals
  72   for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I)
  73     if (!AliveGlobals.count(I)) {
  74       DeadGlobalVars.push_back(I);         // Keep track of dead globals
  75       I->setInitializer(0);
  76     }
  77
  78
  79   // The second pass drops the bodies of functions which are dead...
  80   std::vector<Function*> DeadFunctions;
  81   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
  82     if (!AliveGlobals.count(I)) {
  83       DeadFunctions.push_back(I);         // Keep track of dead globals
  84       if (!I->isExternal())
  85         I->deleteBody();
  86     }
  87
  88   if (!DeadFunctions.empty()) {
  89     // Now that all interreferences have been dropped, delete the actual objects
  90     // themselves.
  91     for (unsigned i = 0, e = DeadFunctions.size(); i != e; ++i) {
  92       RemoveUnusedConstantPointerRef(*DeadFunctions[i]);
  93       M.getFunctionList().erase(DeadFunctions[i]);
  94     }
  95     NumFunctions += DeadFunctions.size();
  96     Changed = true;
  97   }
  98
  99   if (!DeadGlobalVars.empty()) {
 100     for (unsigned i = 0, e = DeadGlobalVars.size(); i != e; ++i) {
 101       RemoveUnusedConstantPointerRef(*DeadGlobalVars[i]);
 102       M.getGlobalList().erase(DeadGlobalVars[i]);
 103     }
 104     NumVariables += DeadGlobalVars.size();
 105     Changed = true;
 106   }
 107
 108   // Make sure that all memory is released
 109   AliveGlobals.clear();
 110   return Changed;
 111 }
 112
 113 /// MarkGlobalIsNeeded - the specific global value as needed, and
 114 /// recursively mark anything that it uses as also needed.
 115 void GlobalDCE::GlobalIsNeeded(GlobalValue *G) {
 116   std::set<GlobalValue*>::iterator I = AliveGlobals.lower_bound(G);
 117
 118   // If the global is already in the set, no need to reprocess it.
 119   if (I != AliveGlobals.end() && *I == G) return;
 120
 121   // Otherwise insert it now, so we do not infinitely recurse
 122   AliveGlobals.insert(I, G);
 123
 124   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G)) {
 125     // If this is a global variable, we must make sure to add any global values
 126     // referenced by the initializer to the alive set.
 127     if (GV->hasInitializer())
 128       MarkUsedGlobalsAsNeeded(GV->getInitializer());
 129   } else {
 130     // Otherwise this must be a function object.  We have to scan the body of
 131     // the function looking for constants and global values which are used as
 132     // operands.  Any operands of these types must be processed to ensure that
 133     // any globals used will be marked as needed.
 134     Function *F = cast<Function>(G);
 135     // For all basic blocks...
 136     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
 137       // For all instructions...
 138       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 139         // For all operands...
 140         for (User::op_iterator U = I->op_begin(), E = I->op_end(); U != E; ++U)
 141           if (GlobalValue *GV = dyn_cast<GlobalValue>(*U))
 142             GlobalIsNeeded(GV);
 143           else if (Constant *C = dyn_cast<Constant>(*U))
 144             MarkUsedGlobalsAsNeeded(C);
 145   }
 146 }
 147
 148 void GlobalDCE::MarkUsedGlobalsAsNeeded(Constant *C) {
 149   if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(C))
 150     GlobalIsNeeded(CPR->getValue());
 151   else {
 152     // Loop over all of the operands of the constant, adding any globals they
 153     // use to the list of needed globals.
 154     for (User::op_iterator I = C->op_begin(), E = C->op_end(); I != E; ++I)
 155       MarkUsedGlobalsAsNeeded(cast<Constant>(*I));
 156   }
 157 }
 158
 159 // RemoveUnusedConstantPointerRef - Loop over all of the uses of the specified
 160 // GlobalValue, looking for the constant pointer ref that may be pointing to it.
 161 // If found, check to see if the constant pointer ref is safe to destroy, and if
 162 // so, nuke it.  This will reduce the reference count on the global value, which
 163 // might make it deader.
 164 //
 165 bool GlobalDCE::RemoveUnusedConstantPointerRef(GlobalValue &GV) {
 166   for (Value::use_iterator I = GV.use_begin(), E = GV.use_end(); I != E; ++I)
 167     if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(*I))
 168       if (SafeToDestroyConstant(CPR)) {  // Only if unreferenced...
 169         CPR->destroyConstant();
 170         ++NumCPRs;
 171         return true;
 172       }
 173
 174   return false;
 175 }
 176
 177 // SafeToDestroyConstant - It is safe to destroy a constant iff it is only used
 178 // by constants itself.  Note that constants cannot be cyclic, so this test is
 179 // pretty easy to implement recursively.
 180 //
 181 bool GlobalDCE::SafeToDestroyConstant(Constant *C) {
 182   for (Value::use_iterator I = C->use_begin(), E = C->use_end(); I != E; ++I)
 183     if (Constant *User = dyn_cast<Constant>(*I)) {
 184       if (!SafeToDestroyConstant(User)) return false;
 185     } else {
 186       return false;
 187     }
 188
 189   return true;
 190 }