Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 1 | //===-- GlobalDCE.cpp - DCE unreachable internal functions ----------------===// |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 7 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 8 | //===----------------------------------------------------------------------===// |
Chris Lattner | 30474bb | 2001-11-26 18:42:17 +0000 | [diff] [blame] | 9 | // |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 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. |
Chris Lattner | 30474bb | 2001-11-26 18:42:17 +0000 | [diff] [blame] | 15 | // |
| 16 | //===----------------------------------------------------------------------===// |
| 17 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 18 | #define DEBUG_TYPE "globaldce" |
Chris Lattner | 568ddab | 2002-07-24 17:12:05 +0000 | [diff] [blame] | 19 | #include "llvm/Transforms/IPO.h" |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 20 | #include "llvm/Constants.h" |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 21 | #include "llvm/Module.h" |
| 22 | #include "llvm/Pass.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 23 | #include "llvm/ADT/Statistic.h" |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 24 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 25 | #include <set> |
Chris Lattner | 1e2385b | 2003-11-21 21:54:22 +0000 | [diff] [blame] | 26 | using namespace llvm; |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 27 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 28 | STATISTIC(NumFunctions, "Number of functions removed"); |
| 29 | STATISTIC(NumVariables, "Number of global variables removed"); |
Chris Lattner | a92f696 | 2002-10-01 22:38:41 +0000 | [diff] [blame] | 30 | |
Chris Lattner | 86453c5 | 2006-12-19 22:09:18 +0000 | [diff] [blame] | 31 | namespace { |
Reid Spencer | 9133fe2 | 2007-02-05 23:32:05 +0000 | [diff] [blame] | 32 | struct VISIBILITY_HIDDEN GlobalDCE : public ModulePass { |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame^] | 33 | static char ID; // Pass identifcation, replacement for typeid |
Devang Patel | 794fd75 | 2007-05-01 21:15:47 +0000 | [diff] [blame] | 34 | GlobalDCE() : ModulePass((intptr_t)&ID) {} |
| 35 | |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 36 | // run - Do the GlobalDCE pass on the specified module, optionally updating |
| 37 | // the specified callgraph to reflect the changes. |
| 38 | // |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 39 | bool runOnModule(Module &M); |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 40 | |
| 41 | private: |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 42 | std::set<GlobalValue*> AliveGlobals; |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 43 | |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 44 | /// MarkGlobalIsNeeded - the specific global value as needed, and |
| 45 | /// recursively mark anything that it uses as also needed. |
| 46 | void GlobalIsNeeded(GlobalValue *GV); |
| 47 | void MarkUsedGlobalsAsNeeded(Constant *C); |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 48 | |
Reid Spencer | 0c4a041 | 2004-07-18 00:25:04 +0000 | [diff] [blame] | 49 | bool SafeToDestroyConstant(Constant* C); |
| 50 | bool RemoveUnusedGlobalValue(GlobalValue &GV); |
Chris Lattner | bd0ef77 | 2002-02-26 21:46:54 +0000 | [diff] [blame] | 51 | }; |
Devang Patel | 1997473 | 2007-05-03 01:11:54 +0000 | [diff] [blame^] | 52 | char GlobalDCE::ID = 0; |
Chris Lattner | 7f8897f | 2006-08-27 22:42:52 +0000 | [diff] [blame] | 53 | RegisterPass<GlobalDCE> X("globaldce", "Dead Global Elimination"); |
Chris Lattner | 793c6b8 | 2002-01-31 00:45:11 +0000 | [diff] [blame] | 54 | } |
| 55 | |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 56 | ModulePass *llvm::createGlobalDCEPass() { return new GlobalDCE(); } |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 57 | |
Chris Lattner | b12914b | 2004-09-20 04:48:05 +0000 | [diff] [blame] | 58 | bool GlobalDCE::runOnModule(Module &M) { |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 59 | bool Changed = false; |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 60 | // Loop over the module, adding globals which are obviously necessary. |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 61 | for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) { |
Reid Spencer | 0c4a041 | 2004-07-18 00:25:04 +0000 | [diff] [blame] | 62 | Changed |= RemoveUnusedGlobalValue(*I); |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 63 | // Functions with external linkage are needed if they have a body |
Chris Lattner | a2d51af | 2003-09-20 19:00:50 +0000 | [diff] [blame] | 64 | if ((!I->hasInternalLinkage() && !I->hasLinkOnceLinkage()) && |
Reid Spencer | 5cbf985 | 2007-01-30 20:08:39 +0000 | [diff] [blame] | 65 | !I->isDeclaration()) |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 66 | GlobalIsNeeded(I); |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 67 | } |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 68 | |
Anton Korobeynikov | 8b0a8c8 | 2007-04-25 14:27:10 +0000 | [diff] [blame] | 69 | for (Module::global_iterator I = M.global_begin(), E = M.global_end(); |
| 70 | I != E; ++I) { |
Reid Spencer | 0c4a041 | 2004-07-18 00:25:04 +0000 | [diff] [blame] | 71 | Changed |= RemoveUnusedGlobalValue(*I); |
Chris Lattner | a2d51af | 2003-09-20 19:00:50 +0000 | [diff] [blame] | 72 | // Externally visible & appending globals are needed, if they have an |
| 73 | // initializer. |
| 74 | if ((!I->hasInternalLinkage() && !I->hasLinkOnceLinkage()) && |
Reid Spencer | 5cbf985 | 2007-01-30 20:08:39 +0000 | [diff] [blame] | 75 | !I->isDeclaration()) |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 76 | GlobalIsNeeded(I); |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 77 | } |
| 78 | |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 79 | |
Anton Korobeynikov | 8b0a8c8 | 2007-04-25 14:27:10 +0000 | [diff] [blame] | 80 | for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); |
| 81 | I != E; ++I) { |
Anton Korobeynikov | 8b0a8c8 | 2007-04-25 14:27:10 +0000 | [diff] [blame] | 82 | // Aliases are always needed even if they are not used. |
Anton Korobeynikov | c6c98af | 2007-04-29 18:02:48 +0000 | [diff] [blame] | 83 | MarkUsedGlobalsAsNeeded(I->getAliasee()); |
Anton Korobeynikov | 8b0a8c8 | 2007-04-25 14:27:10 +0000 | [diff] [blame] | 84 | } |
| 85 | |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 86 | // Now that all globals which are needed are in the AliveGlobals set, we loop |
| 87 | // through the program, deleting those which are not alive. |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 88 | // |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 89 | |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 90 | // The first pass is to drop initializers of global variables which are dead. |
| 91 | std::vector<GlobalVariable*> DeadGlobalVars; // Keep track of dead globals |
Chris Lattner | e4d5c44 | 2005-03-15 04:54:21 +0000 | [diff] [blame] | 92 | for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I) |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 93 | if (!AliveGlobals.count(I)) { |
| 94 | DeadGlobalVars.push_back(I); // Keep track of dead globals |
| 95 | I->setInitializer(0); |
| 96 | } |
| 97 | |
| 98 | |
| 99 | // The second pass drops the bodies of functions which are dead... |
| 100 | std::vector<Function*> DeadFunctions; |
| 101 | for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) |
| 102 | if (!AliveGlobals.count(I)) { |
| 103 | DeadFunctions.push_back(I); // Keep track of dead globals |
Reid Spencer | 5cbf985 | 2007-01-30 20:08:39 +0000 | [diff] [blame] | 104 | if (!I->isDeclaration()) |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 105 | I->deleteBody(); |
| 106 | } |
| 107 | |
| 108 | if (!DeadFunctions.empty()) { |
| 109 | // Now that all interreferences have been dropped, delete the actual objects |
| 110 | // themselves. |
| 111 | for (unsigned i = 0, e = DeadFunctions.size(); i != e; ++i) { |
Reid Spencer | 0c4a041 | 2004-07-18 00:25:04 +0000 | [diff] [blame] | 112 | RemoveUnusedGlobalValue(*DeadFunctions[i]); |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 113 | M.getFunctionList().erase(DeadFunctions[i]); |
| 114 | } |
| 115 | NumFunctions += DeadFunctions.size(); |
| 116 | Changed = true; |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 117 | } |
| 118 | |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 119 | if (!DeadGlobalVars.empty()) { |
| 120 | for (unsigned i = 0, e = DeadGlobalVars.size(); i != e; ++i) { |
Reid Spencer | 0c4a041 | 2004-07-18 00:25:04 +0000 | [diff] [blame] | 121 | RemoveUnusedGlobalValue(*DeadGlobalVars[i]); |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 122 | M.getGlobalList().erase(DeadGlobalVars[i]); |
| 123 | } |
| 124 | NumVariables += DeadGlobalVars.size(); |
| 125 | Changed = true; |
| 126 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 127 | |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 128 | // Make sure that all memory is released |
| 129 | AliveGlobals.clear(); |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 130 | return Changed; |
| 131 | } |
| 132 | |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 133 | /// MarkGlobalIsNeeded - the specific global value as needed, and |
| 134 | /// recursively mark anything that it uses as also needed. |
| 135 | void GlobalDCE::GlobalIsNeeded(GlobalValue *G) { |
| 136 | std::set<GlobalValue*>::iterator I = AliveGlobals.lower_bound(G); |
| 137 | |
| 138 | // If the global is already in the set, no need to reprocess it. |
| 139 | if (I != AliveGlobals.end() && *I == G) return; |
| 140 | |
| 141 | // Otherwise insert it now, so we do not infinitely recurse |
| 142 | AliveGlobals.insert(I, G); |
| 143 | |
| 144 | if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G)) { |
| 145 | // If this is a global variable, we must make sure to add any global values |
| 146 | // referenced by the initializer to the alive set. |
| 147 | if (GV->hasInitializer()) |
| 148 | MarkUsedGlobalsAsNeeded(GV->getInitializer()); |
Anton Korobeynikov | a80e118 | 2007-04-28 13:45:00 +0000 | [diff] [blame] | 149 | } else if (!isa<GlobalAlias>(G)) { |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 150 | // Otherwise this must be a function object. We have to scan the body of |
| 151 | // the function looking for constants and global values which are used as |
| 152 | // operands. Any operands of these types must be processed to ensure that |
| 153 | // any globals used will be marked as needed. |
| 154 | Function *F = cast<Function>(G); |
| 155 | // For all basic blocks... |
| 156 | for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) |
| 157 | // For all instructions... |
| 158 | for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) |
| 159 | // For all operands... |
| 160 | for (User::op_iterator U = I->op_begin(), E = I->op_end(); U != E; ++U) |
| 161 | if (GlobalValue *GV = dyn_cast<GlobalValue>(*U)) |
| 162 | GlobalIsNeeded(GV); |
| 163 | else if (Constant *C = dyn_cast<Constant>(*U)) |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 164 | MarkUsedGlobalsAsNeeded(C); |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 165 | } |
| 166 | } |
| 167 | |
| 168 | void GlobalDCE::MarkUsedGlobalsAsNeeded(Constant *C) { |
Reid Spencer | 0c4a041 | 2004-07-18 00:25:04 +0000 | [diff] [blame] | 169 | if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) |
| 170 | GlobalIsNeeded(GV); |
Chris Lattner | 1cbcd0f | 2003-09-16 19:27:31 +0000 | [diff] [blame] | 171 | else { |
| 172 | // Loop over all of the operands of the constant, adding any globals they |
| 173 | // use to the list of needed globals. |
| 174 | for (User::op_iterator I = C->op_begin(), E = C->op_end(); I != E; ++I) |
| 175 | MarkUsedGlobalsAsNeeded(cast<Constant>(*I)); |
| 176 | } |
| 177 | } |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 178 | |
Reid Spencer | 0c4a041 | 2004-07-18 00:25:04 +0000 | [diff] [blame] | 179 | // RemoveUnusedGlobalValue - Loop over all of the uses of the specified |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 180 | // GlobalValue, looking for the constant pointer ref that may be pointing to it. |
| 181 | // If found, check to see if the constant pointer ref is safe to destroy, and if |
| 182 | // so, nuke it. This will reduce the reference count on the global value, which |
| 183 | // might make it deader. |
| 184 | // |
Reid Spencer | 0c4a041 | 2004-07-18 00:25:04 +0000 | [diff] [blame] | 185 | bool GlobalDCE::RemoveUnusedGlobalValue(GlobalValue &GV) { |
Chris Lattner | 25c6d68 | 2004-07-18 07:22:58 +0000 | [diff] [blame] | 186 | if (GV.use_empty()) return false; |
| 187 | GV.removeDeadConstantUsers(); |
| 188 | return GV.use_empty(); |
| 189 | } |
Misha Brukman | fd93908 | 2005-04-21 23:48:37 +0000 | [diff] [blame] | 190 | |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 191 | // SafeToDestroyConstant - It is safe to destroy a constant iff it is only used |
| 192 | // by constants itself. Note that constants cannot be cyclic, so this test is |
| 193 | // pretty easy to implement recursively. |
| 194 | // |
| 195 | bool GlobalDCE::SafeToDestroyConstant(Constant *C) { |
| 196 | for (Value::use_iterator I = C->use_begin(), E = C->use_end(); I != E; ++I) |
| 197 | if (Constant *User = dyn_cast<Constant>(*I)) { |
| 198 | if (!SafeToDestroyConstant(User)) return false; |
| 199 | } else { |
| 200 | return false; |
| 201 | } |
Chris Lattner | 0bfb6ba | 2002-08-18 01:28:30 +0000 | [diff] [blame] | 202 | return true; |
| 203 | } |