LLVM API Documentation
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::giterator I = M.gbegin(), E = M.gend(); 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::giterator I = M.gbegin(), E = M.gend(); 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 }