1//===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This transform is designed to eliminate unreachable internal globals from the 11// program. It uses an aggressive algorithm, searching out globals that are 12// known to be alive. After it finds all of the globals which are needed, it 13// deletes whatever is left over. This allows it to delete recursive chunks of 14// the program which are unreachable. 15// 16//===----------------------------------------------------------------------===// 17 18#include "llvm/Transforms/IPO.h" 19#include "llvm/ADT/SmallPtrSet.h" 20#include "llvm/ADT/Statistic.h" 21#include "llvm/IR/Constants.h" 22#include "llvm/IR/Instructions.h" 23#include "llvm/IR/Module.h" 24#include "llvm/Transforms/Utils/CtorUtils.h" 25#include "llvm/Transforms/Utils/GlobalStatus.h" 26#include "llvm/Pass.h" 27#include <unordered_map> 28using namespace llvm; 29 30#define DEBUG_TYPE "globaldce" 31 32STATISTIC(NumAliases , "Number of global aliases removed"); 33STATISTIC(NumFunctions, "Number of functions removed"); 34STATISTIC(NumVariables, "Number of global variables removed"); 35 36namespace { 37 struct GlobalDCE : public ModulePass { 38 static char ID; // Pass identification, replacement for typeid 39 GlobalDCE() : ModulePass(ID) { 40 initializeGlobalDCEPass(*PassRegistry::getPassRegistry()); 41 } 42 43 // run - Do the GlobalDCE pass on the specified module, optionally updating 44 // the specified callgraph to reflect the changes. 45 // 46 bool runOnModule(Module &M) override; 47 48 private: 49 SmallPtrSet<GlobalValue*, 32> AliveGlobals; 50 SmallPtrSet<Constant *, 8> SeenConstants; 51 std::unordered_multimap<Comdat *, GlobalValue *> ComdatMembers; 52 53 /// GlobalIsNeeded - mark the specific global value as needed, and 54 /// recursively mark anything that it uses as also needed. 55 void GlobalIsNeeded(GlobalValue *GV); 56 void MarkUsedGlobalsAsNeeded(Constant *C); 57 58 bool RemoveUnusedGlobalValue(GlobalValue &GV); 59 }; 60} 61 62/// Returns true if F contains only a single "ret" instruction. 63static bool isEmptyFunction(Function *F) { 64 BasicBlock &Entry = F->getEntryBlock(); 65 if (Entry.size() != 1 || !isa<ReturnInst>(Entry.front())) 66 return false; 67 ReturnInst &RI = cast<ReturnInst>(Entry.front()); 68 return RI.getReturnValue() == nullptr; 69} 70 71char GlobalDCE::ID = 0; 72INITIALIZE_PASS(GlobalDCE, "globaldce", 73 "Dead Global Elimination", false, false) 74 75ModulePass *llvm::createGlobalDCEPass() { return new GlobalDCE(); } 76 77bool GlobalDCE::runOnModule(Module &M) { 78 bool Changed = false; 79 80 // Remove empty functions from the global ctors list. 81 Changed |= optimizeGlobalCtorsList(M, isEmptyFunction); 82 83 // Collect the set of members for each comdat. 84 for (Function &F : M) 85 if (Comdat *C = F.getComdat()) 86 ComdatMembers.insert(std::make_pair(C, &F)); 87 for (GlobalVariable &GV : M.globals()) 88 if (Comdat *C = GV.getComdat()) 89 ComdatMembers.insert(std::make_pair(C, &GV)); 90 for (GlobalAlias &GA : M.aliases()) 91 if (Comdat *C = GA.getComdat()) 92 ComdatMembers.insert(std::make_pair(C, &GA)); 93 94 // Loop over the module, adding globals which are obviously necessary. 95 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { 96 Changed |= RemoveUnusedGlobalValue(*I); 97 // Functions with external linkage are needed if they have a body 98 if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage()) { 99 if (!I->isDiscardableIfUnused()) 100 GlobalIsNeeded(I); 101 } 102 } 103 104 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 105 I != E; ++I) { 106 Changed |= RemoveUnusedGlobalValue(*I); 107 // Externally visible & appending globals are needed, if they have an 108 // initializer. 109 if (!I->isDeclaration() && !I->hasAvailableExternallyLinkage()) { 110 if (!I->isDiscardableIfUnused()) 111 GlobalIsNeeded(I); 112 } 113 } 114 115 for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); 116 I != E; ++I) { 117 Changed |= RemoveUnusedGlobalValue(*I); 118 // Externally visible aliases are needed. 119 if (!I->isDiscardableIfUnused()) { 120 GlobalIsNeeded(I); 121 } 122 } 123 124 // Now that all globals which are needed are in the AliveGlobals set, we loop 125 // through the program, deleting those which are not alive. 126 // 127 128 // The first pass is to drop initializers of global variables which are dead. 129 std::vector<GlobalVariable*> DeadGlobalVars; // Keep track of dead globals 130 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); 131 I != E; ++I) 132 if (!AliveGlobals.count(I)) { 133 DeadGlobalVars.push_back(I); // Keep track of dead globals 134 if (I->hasInitializer()) { 135 Constant *Init = I->getInitializer(); 136 I->setInitializer(nullptr); 137 if (isSafeToDestroyConstant(Init)) 138 Init->destroyConstant(); 139 } 140 } 141 142 // The second pass drops the bodies of functions which are dead... 143 std::vector<Function*> DeadFunctions; 144 for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 145 if (!AliveGlobals.count(I)) { 146 DeadFunctions.push_back(I); // Keep track of dead globals 147 if (!I->isDeclaration()) 148 I->deleteBody(); 149 } 150 151 // The third pass drops targets of aliases which are dead... 152 std::vector<GlobalAlias*> DeadAliases; 153 for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); I != E; 154 ++I) 155 if (!AliveGlobals.count(I)) { 156 DeadAliases.push_back(I); 157 I->setAliasee(nullptr); 158 } 159 160 if (!DeadFunctions.empty()) { 161 // Now that all interferences have been dropped, delete the actual objects 162 // themselves. 163 for (unsigned i = 0, e = DeadFunctions.size(); i != e; ++i) { 164 RemoveUnusedGlobalValue(*DeadFunctions[i]); 165 M.getFunctionList().erase(DeadFunctions[i]); 166 } 167 NumFunctions += DeadFunctions.size(); 168 Changed = true; 169 } 170 171 if (!DeadGlobalVars.empty()) { 172 for (unsigned i = 0, e = DeadGlobalVars.size(); i != e; ++i) { 173 RemoveUnusedGlobalValue(*DeadGlobalVars[i]); 174 M.getGlobalList().erase(DeadGlobalVars[i]); 175 } 176 NumVariables += DeadGlobalVars.size(); 177 Changed = true; 178 } 179 180 // Now delete any dead aliases. 181 if (!DeadAliases.empty()) { 182 for (unsigned i = 0, e = DeadAliases.size(); i != e; ++i) { 183 RemoveUnusedGlobalValue(*DeadAliases[i]); 184 M.getAliasList().erase(DeadAliases[i]); 185 } 186 NumAliases += DeadAliases.size(); 187 Changed = true; 188 } 189 190 // Make sure that all memory is released 191 AliveGlobals.clear(); 192 SeenConstants.clear(); 193 ComdatMembers.clear(); 194 195 return Changed; 196} 197 198/// GlobalIsNeeded - the specific global value as needed, and 199/// recursively mark anything that it uses as also needed. 200void GlobalDCE::GlobalIsNeeded(GlobalValue *G) { 201 // If the global is already in the set, no need to reprocess it. 202 if (!AliveGlobals.insert(G).second) 203 return; 204 205 if (Comdat *C = G->getComdat()) { 206 for (auto &&CM : make_range(ComdatMembers.equal_range(C))) 207 GlobalIsNeeded(CM.second); 208 } 209 210 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G)) { 211 // If this is a global variable, we must make sure to add any global values 212 // referenced by the initializer to the alive set. 213 if (GV->hasInitializer()) 214 MarkUsedGlobalsAsNeeded(GV->getInitializer()); 215 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(G)) { 216 // The target of a global alias is needed. 217 MarkUsedGlobalsAsNeeded(GA->getAliasee()); 218 } else { 219 // Otherwise this must be a function object. We have to scan the body of 220 // the function looking for constants and global values which are used as 221 // operands. Any operands of these types must be processed to ensure that 222 // any globals used will be marked as needed. 223 Function *F = cast<Function>(G); 224 225 if (F->hasPrefixData()) 226 MarkUsedGlobalsAsNeeded(F->getPrefixData()); 227 228 if (F->hasPrologueData()) 229 MarkUsedGlobalsAsNeeded(F->getPrologueData()); 230 231 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 232 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 233 for (User::op_iterator U = I->op_begin(), E = I->op_end(); U != E; ++U) 234 if (GlobalValue *GV = dyn_cast<GlobalValue>(*U)) 235 GlobalIsNeeded(GV); 236 else if (Constant *C = dyn_cast<Constant>(*U)) 237 MarkUsedGlobalsAsNeeded(C); 238 } 239} 240 241void GlobalDCE::MarkUsedGlobalsAsNeeded(Constant *C) { 242 if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) 243 return GlobalIsNeeded(GV); 244 245 // Loop over all of the operands of the constant, adding any globals they 246 // use to the list of needed globals. 247 for (User::op_iterator I = C->op_begin(), E = C->op_end(); I != E; ++I) { 248 // If we've already processed this constant there's no need to do it again. 249 Constant *Op = dyn_cast<Constant>(*I); 250 if (Op && SeenConstants.insert(Op).second) 251 MarkUsedGlobalsAsNeeded(Op); 252 } 253} 254 255// RemoveUnusedGlobalValue - Loop over all of the uses of the specified 256// GlobalValue, looking for the constant pointer ref that may be pointing to it. 257// If found, check to see if the constant pointer ref is safe to destroy, and if 258// so, nuke it. This will reduce the reference count on the global value, which 259// might make it deader. 260// 261bool GlobalDCE::RemoveUnusedGlobalValue(GlobalValue &GV) { 262 if (GV.use_empty()) return false; 263 GV.removeDeadConstantUsers(); 264 return GV.use_empty(); 265} 266