LLVM API Documentation

GlobalDCE.cpp

Go to the documentation of this file.
00001 //===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This transform is designed to eliminate unreachable internal globals from the
00011 // program.  It uses an aggressive algorithm, searching out globals that are
00012 // known to be alive.  After it finds all of the globals which are needed, it
00013 // deletes whatever is left over.  This allows it to delete recursive chunks of
00014 // the program which are unreachable.
00015 //
00016 //===----------------------------------------------------------------------===//
00017 
00018 #include "llvm/Transforms/IPO.h"
00019 #include "llvm/Constants.h"
00020 #include "llvm/Module.h"
00021 #include "llvm/Pass.h"
00022 #include "llvm/ADT/Statistic.h"
00023 #include <set>
00024 using namespace llvm;
00025 
00026 namespace {
00027   Statistic<> NumFunctions("globaldce","Number of functions removed");
00028   Statistic<> NumVariables("globaldce","Number of global variables removed");
00029 
00030   struct GlobalDCE : public ModulePass {
00031     // run - Do the GlobalDCE pass on the specified module, optionally updating
00032     // the specified callgraph to reflect the changes.
00033     //
00034     bool runOnModule(Module &M);
00035 
00036   private:
00037     std::set<GlobalValue*> AliveGlobals;
00038 
00039     /// MarkGlobalIsNeeded - the specific global value as needed, and
00040     /// recursively mark anything that it uses as also needed.
00041     void GlobalIsNeeded(GlobalValue *GV);
00042     void MarkUsedGlobalsAsNeeded(Constant *C);
00043 
00044     bool SafeToDestroyConstant(Constant* C);
00045     bool RemoveUnusedGlobalValue(GlobalValue &GV);
00046   };
00047   RegisterOpt<GlobalDCE> X("globaldce", "Dead Global Elimination");
00048 }
00049 
00050 ModulePass *llvm::createGlobalDCEPass() { return new GlobalDCE(); }
00051 
00052 bool GlobalDCE::runOnModule(Module &M) {
00053   bool Changed = false;
00054   // Loop over the module, adding globals which are obviously necessary.
00055   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
00056     Changed |= RemoveUnusedGlobalValue(*I);
00057     // Functions with external linkage are needed if they have a body
00058     if ((!I->hasInternalLinkage() && !I->hasLinkOnceLinkage()) &&
00059         !I->isExternal())
00060       GlobalIsNeeded(I);
00061   }
00062 
00063   for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I) {
00064     Changed |= RemoveUnusedGlobalValue(*I);
00065     // Externally visible & appending globals are needed, if they have an
00066     // initializer.
00067     if ((!I->hasInternalLinkage() && !I->hasLinkOnceLinkage()) &&
00068         !I->isExternal())
00069       GlobalIsNeeded(I);
00070   }
00071 
00072 
00073   // Now that all globals which are needed are in the AliveGlobals set, we loop
00074   // through the program, deleting those which are not alive.
00075   //
00076 
00077   // The first pass is to drop initializers of global variables which are dead.
00078   std::vector<GlobalVariable*> DeadGlobalVars;   // Keep track of dead globals
00079   for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I)
00080     if (!AliveGlobals.count(I)) {
00081       DeadGlobalVars.push_back(I);         // Keep track of dead globals
00082       I->setInitializer(0);
00083     }
00084 
00085 
00086   // The second pass drops the bodies of functions which are dead...
00087   std::vector<Function*> DeadFunctions;
00088   for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
00089     if (!AliveGlobals.count(I)) {
00090       DeadFunctions.push_back(I);         // Keep track of dead globals
00091       if (!I->isExternal())
00092         I->deleteBody();
00093     }
00094 
00095   if (!DeadFunctions.empty()) {
00096     // Now that all interreferences have been dropped, delete the actual objects
00097     // themselves.
00098     for (unsigned i = 0, e = DeadFunctions.size(); i != e; ++i) {
00099       RemoveUnusedGlobalValue(*DeadFunctions[i]);
00100       M.getFunctionList().erase(DeadFunctions[i]);
00101     }
00102     NumFunctions += DeadFunctions.size();
00103     Changed = true;
00104   }
00105 
00106   if (!DeadGlobalVars.empty()) {
00107     for (unsigned i = 0, e = DeadGlobalVars.size(); i != e; ++i) {
00108       RemoveUnusedGlobalValue(*DeadGlobalVars[i]);
00109       M.getGlobalList().erase(DeadGlobalVars[i]);
00110     }
00111     NumVariables += DeadGlobalVars.size();
00112     Changed = true;
00113   }
00114 
00115   // Make sure that all memory is released
00116   AliveGlobals.clear();
00117   return Changed;
00118 }
00119 
00120 /// MarkGlobalIsNeeded - the specific global value as needed, and
00121 /// recursively mark anything that it uses as also needed.
00122 void GlobalDCE::GlobalIsNeeded(GlobalValue *G) {
00123   std::set<GlobalValue*>::iterator I = AliveGlobals.lower_bound(G);
00124 
00125   // If the global is already in the set, no need to reprocess it.
00126   if (I != AliveGlobals.end() && *I == G) return;
00127 
00128   // Otherwise insert it now, so we do not infinitely recurse
00129   AliveGlobals.insert(I, G);
00130 
00131   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G)) {
00132     // If this is a global variable, we must make sure to add any global values
00133     // referenced by the initializer to the alive set.
00134     if (GV->hasInitializer())
00135       MarkUsedGlobalsAsNeeded(GV->getInitializer());
00136   } else {
00137     // Otherwise this must be a function object.  We have to scan the body of
00138     // the function looking for constants and global values which are used as
00139     // operands.  Any operands of these types must be processed to ensure that
00140     // any globals used will be marked as needed.
00141     Function *F = cast<Function>(G);
00142     // For all basic blocks...
00143     for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
00144       // For all instructions...
00145       for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
00146         // For all operands...
00147         for (User::op_iterator U = I->op_begin(), E = I->op_end(); U != E; ++U)
00148           if (GlobalValue *GV = dyn_cast<GlobalValue>(*U))
00149             GlobalIsNeeded(GV);
00150           else if (Constant *C = dyn_cast<Constant>(*U))
00151             MarkUsedGlobalsAsNeeded(C);
00152   }
00153 }
00154 
00155 void GlobalDCE::MarkUsedGlobalsAsNeeded(Constant *C) {
00156   if (GlobalValue *GV = dyn_cast<GlobalValue>(C))
00157     GlobalIsNeeded(GV);
00158   else {
00159     // Loop over all of the operands of the constant, adding any globals they
00160     // use to the list of needed globals.
00161     for (User::op_iterator I = C->op_begin(), E = C->op_end(); I != E; ++I)
00162       MarkUsedGlobalsAsNeeded(cast<Constant>(*I));
00163   }
00164 }
00165 
00166 // RemoveUnusedGlobalValue - Loop over all of the uses of the specified
00167 // GlobalValue, looking for the constant pointer ref that may be pointing to it.
00168 // If found, check to see if the constant pointer ref is safe to destroy, and if
00169 // so, nuke it.  This will reduce the reference count on the global value, which
00170 // might make it deader.
00171 //
00172 bool GlobalDCE::RemoveUnusedGlobalValue(GlobalValue &GV) {
00173   if (GV.use_empty()) return false;
00174   GV.removeDeadConstantUsers();
00175   return GV.use_empty();
00176 }
00177 
00178 // SafeToDestroyConstant - It is safe to destroy a constant iff it is only used
00179 // by constants itself.  Note that constants cannot be cyclic, so this test is
00180 // pretty easy to implement recursively.
00181 //
00182 bool GlobalDCE::SafeToDestroyConstant(Constant *C) {
00183   for (Value::use_iterator I = C->use_begin(), E = C->use_end(); I != E; ++I)
00184     if (Constant *User = dyn_cast<Constant>(*I)) {
00185       if (!SafeToDestroyConstant(User)) return false;
00186     } else {
00187       return false;
00188     }
00189   return true;
00190 }