Owen Anderson | 666f6fe | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 1 | //===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===// |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
| 10 | // This file implements a trivial dead store elimination that only considers |
| 11 | // basic-block local redundant stores. |
| 12 | // |
| 13 | // FIXME: This should eventually be extended to be a post-dominator tree |
| 14 | // traversal. Doing so would be pretty trivial. |
| 15 | // |
| 16 | //===----------------------------------------------------------------------===// |
| 17 | |
Owen Anderson | f6a05f9 | 2007-08-01 06:36:51 +0000 | [diff] [blame] | 18 | #define DEBUG_TYPE "dse" |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 19 | #include "llvm/Transforms/Scalar.h" |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 20 | #include "llvm/Constants.h" |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 21 | #include "llvm/Function.h" |
| 22 | #include "llvm/Instructions.h" |
| 23 | #include "llvm/Pass.h" |
| 24 | #include "llvm/ADT/SetVector.h" |
| 25 | #include "llvm/ADT/SmallPtrSet.h" |
| 26 | #include "llvm/ADT/Statistic.h" |
Owen Anderson | a96c1f6 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 27 | #include "llvm/Analysis/AliasAnalysis.h" |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 28 | #include "llvm/Analysis/MemoryDependenceAnalysis.h" |
Owen Anderson | a96c1f6 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 29 | #include "llvm/Target/TargetData.h" |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 30 | #include "llvm/Transforms/Utils/Local.h" |
| 31 | #include "llvm/Support/Compiler.h" |
| 32 | using namespace llvm; |
| 33 | |
| 34 | STATISTIC(NumFastStores, "Number of stores deleted"); |
| 35 | STATISTIC(NumFastOther , "Number of other instrs removed"); |
| 36 | |
| 37 | namespace { |
Owen Anderson | f6a05f9 | 2007-08-01 06:36:51 +0000 | [diff] [blame] | 38 | struct VISIBILITY_HIDDEN DSE : public FunctionPass { |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 39 | static char ID; // Pass identification, replacement for typeid |
Owen Anderson | f6a05f9 | 2007-08-01 06:36:51 +0000 | [diff] [blame] | 40 | DSE() : FunctionPass((intptr_t)&ID) {} |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 41 | |
| 42 | virtual bool runOnFunction(Function &F) { |
| 43 | bool Changed = false; |
| 44 | for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) |
| 45 | Changed |= runOnBasicBlock(*I); |
| 46 | return Changed; |
| 47 | } |
| 48 | |
| 49 | bool runOnBasicBlock(BasicBlock &BB); |
Owen Anderson | 666f6fe | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 50 | bool handleFreeWithNonTrivialDependency(FreeInst* F, |
| 51 | Instruction* dependency, |
| 52 | SetVector<Instruction*>& possiblyDead); |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 53 | bool handleEndBlock(BasicBlock& BB, SetVector<Instruction*>& possiblyDead); |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 54 | bool RemoveUndeadPointers(Value* pointer, |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 55 | BasicBlock::iterator& BBI, |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 56 | SmallPtrSet<AllocaInst*, 64>& deadPointers, |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 57 | SetVector<Instruction*>& possiblyDead); |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 58 | void DeleteDeadInstructionChains(Instruction *I, |
| 59 | SetVector<Instruction*> &DeadInsts); |
Owen Anderson | 6ca4cb3 | 2007-08-08 04:52:29 +0000 | [diff] [blame] | 60 | |
Owen Anderson | c182f17 | 2007-08-08 06:06:02 +0000 | [diff] [blame] | 61 | /// Find the base pointer that a pointer came from |
| 62 | /// Because this is used to find pointers that originate |
| 63 | /// from allocas, it is safe to ignore GEP indices, since |
| 64 | /// either the store will be in the alloca, and thus dead, |
| 65 | /// or beyond the end of the alloca, and thus undefined. |
Owen Anderson | 7ebba51 | 2007-11-01 05:29:16 +0000 | [diff] [blame] | 66 | void TranslatePointerBitCasts(Value*& v, bool zeroGepsOnly = false) { |
Owen Anderson | 666f6fe | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 67 | assert(isa<PointerType>(v->getType()) && |
| 68 | "Translating a non-pointer type?"); |
Owen Anderson | 6ca4cb3 | 2007-08-08 04:52:29 +0000 | [diff] [blame] | 69 | while (true) { |
Owen Anderson | ce17b1c | 2007-07-16 23:34:39 +0000 | [diff] [blame] | 70 | if (BitCastInst* C = dyn_cast<BitCastInst>(v)) |
| 71 | v = C->getOperand(0); |
| 72 | else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(v)) |
Owen Anderson | 7ebba51 | 2007-11-01 05:29:16 +0000 | [diff] [blame] | 73 | if (!zeroGepsOnly || G->hasAllZeroIndices()) { |
| 74 | v = G->getOperand(0); |
| 75 | } else { |
| 76 | break; |
| 77 | } |
Owen Anderson | 6ca4cb3 | 2007-08-08 04:52:29 +0000 | [diff] [blame] | 78 | else |
| 79 | break; |
| 80 | } |
Owen Anderson | 3e8d001 | 2007-07-13 18:26:26 +0000 | [diff] [blame] | 81 | } |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 82 | |
| 83 | // getAnalysisUsage - We require post dominance frontiers (aka Control |
| 84 | // Dependence Graph) |
| 85 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 86 | AU.setPreservesCFG(); |
Owen Anderson | a96c1f6 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 87 | AU.addRequired<TargetData>(); |
| 88 | AU.addRequired<AliasAnalysis>(); |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 89 | AU.addRequired<MemoryDependenceAnalysis>(); |
Owen Anderson | a96c1f6 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 90 | AU.addPreserved<AliasAnalysis>(); |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 91 | AU.addPreserved<MemoryDependenceAnalysis>(); |
| 92 | } |
| 93 | }; |
Owen Anderson | f6a05f9 | 2007-08-01 06:36:51 +0000 | [diff] [blame] | 94 | char DSE::ID = 0; |
| 95 | RegisterPass<DSE> X("dse", "Dead Store Elimination"); |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 96 | } |
| 97 | |
Owen Anderson | f6a05f9 | 2007-08-01 06:36:51 +0000 | [diff] [blame] | 98 | FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 99 | |
Owen Anderson | f6a05f9 | 2007-08-01 06:36:51 +0000 | [diff] [blame] | 100 | bool DSE::runOnBasicBlock(BasicBlock &BB) { |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 101 | MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); |
Owen Anderson | 7ebba51 | 2007-11-01 05:29:16 +0000 | [diff] [blame] | 102 | TargetData &TD = getAnalysis<TargetData>(); |
| 103 | |
Owen Anderson | bfbfb3c | 2007-07-11 19:03:09 +0000 | [diff] [blame] | 104 | // Record the last-seen store to this pointer |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 105 | DenseMap<Value*, StoreInst*> lastStore; |
Owen Anderson | bfbfb3c | 2007-07-11 19:03:09 +0000 | [diff] [blame] | 106 | // Record instructions possibly made dead by deleting a store |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 107 | SetVector<Instruction*> possiblyDead; |
| 108 | |
| 109 | bool MadeChange = false; |
| 110 | |
| 111 | // Do a top-down walk on the BB |
Owen Anderson | 666f6fe | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 112 | for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); |
| 113 | BBI != BBE; ++BBI) { |
Owen Anderson | 6f46d65 | 2007-07-11 21:06:56 +0000 | [diff] [blame] | 114 | // If we find a store or a free... |
Owen Anderson | 6ca4cb3 | 2007-08-08 04:52:29 +0000 | [diff] [blame] | 115 | if (!isa<StoreInst>(BBI) && !isa<FreeInst>(BBI)) |
| 116 | continue; |
Owen Anderson | 3e8d001 | 2007-07-13 18:26:26 +0000 | [diff] [blame] | 117 | |
Owen Anderson | 6ca4cb3 | 2007-08-08 04:52:29 +0000 | [diff] [blame] | 118 | Value* pointer = 0; |
Owen Anderson | 5dfcf43 | 2007-08-26 21:14:47 +0000 | [diff] [blame] | 119 | if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { |
| 120 | if (!S->isVolatile()) |
| 121 | pointer = S->getPointerOperand(); |
| 122 | else |
| 123 | continue; |
| 124 | } else |
Owen Anderson | c182f17 | 2007-08-08 06:06:02 +0000 | [diff] [blame] | 125 | pointer = cast<FreeInst>(BBI)->getPointerOperand(); |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 126 | |
Owen Anderson | 7ebba51 | 2007-11-01 05:29:16 +0000 | [diff] [blame] | 127 | TranslatePointerBitCasts(pointer, true); |
Owen Anderson | 6ca4cb3 | 2007-08-08 04:52:29 +0000 | [diff] [blame] | 128 | StoreInst*& last = lastStore[pointer]; |
| 129 | bool deletedStore = false; |
| 130 | |
| 131 | // ... to a pointer that has been stored to before... |
| 132 | if (last) { |
Owen Anderson | 9528f11 | 2007-08-09 04:42:44 +0000 | [diff] [blame] | 133 | Instruction* dep = MD.getDependency(BBI); |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 134 | |
Owen Anderson | 6ca4cb3 | 2007-08-08 04:52:29 +0000 | [diff] [blame] | 135 | // ... and no other memory dependencies are between them.... |
| 136 | while (dep != MemoryDependenceAnalysis::None && |
| 137 | dep != MemoryDependenceAnalysis::NonLocal && |
| 138 | isa<StoreInst>(dep)) { |
Owen Anderson | 7ebba51 | 2007-11-01 05:29:16 +0000 | [diff] [blame] | 139 | if (dep != last || |
Duncan Sands | 514ab34 | 2007-11-01 20:53:16 +0000 | [diff] [blame] | 140 | TD.getTypeStoreSize(last->getOperand(0)->getType()) > |
| 141 | TD.getTypeStoreSize(BBI->getOperand(0)->getType())) { |
Owen Anderson | 9528f11 | 2007-08-09 04:42:44 +0000 | [diff] [blame] | 142 | dep = MD.getDependency(BBI, dep); |
Owen Anderson | 6ca4cb3 | 2007-08-08 04:52:29 +0000 | [diff] [blame] | 143 | continue; |
Owen Anderson | dd61c2b | 2007-07-12 18:08:51 +0000 | [diff] [blame] | 144 | } |
Owen Anderson | 6ca4cb3 | 2007-08-08 04:52:29 +0000 | [diff] [blame] | 145 | |
| 146 | // Remove it! |
| 147 | MD.removeInstruction(last); |
| 148 | |
| 149 | // DCE instructions only used to calculate that store |
| 150 | if (Instruction* D = dyn_cast<Instruction>(last->getOperand(0))) |
| 151 | possiblyDead.insert(D); |
| 152 | if (Instruction* D = dyn_cast<Instruction>(last->getOperand(1))) |
| 153 | possiblyDead.insert(D); |
| 154 | |
| 155 | last->eraseFromParent(); |
| 156 | NumFastStores++; |
| 157 | deletedStore = true; |
| 158 | MadeChange = true; |
| 159 | |
| 160 | break; |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 161 | } |
Owen Anderson | 6ca4cb3 | 2007-08-08 04:52:29 +0000 | [diff] [blame] | 162 | } |
| 163 | |
| 164 | // Handle frees whose dependencies are non-trivial. |
| 165 | if (FreeInst* F = dyn_cast<FreeInst>(BBI)) { |
| 166 | if (!deletedStore) |
| 167 | MadeChange |= handleFreeWithNonTrivialDependency(F, |
Owen Anderson | 9528f11 | 2007-08-09 04:42:44 +0000 | [diff] [blame] | 168 | MD.getDependency(F), |
Owen Anderson | 6ca4cb3 | 2007-08-08 04:52:29 +0000 | [diff] [blame] | 169 | possiblyDead); |
| 170 | // No known stores after the free |
| 171 | last = 0; |
| 172 | } else { |
| 173 | // Update our most-recent-store map. |
| 174 | last = cast<StoreInst>(BBI); |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 175 | } |
| 176 | } |
| 177 | |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 178 | // If this block ends in a return, unwind, unreachable, and eventually |
| 179 | // tailcall, then all allocas are dead at its end. |
| 180 | if (BB.getTerminator()->getNumSuccessors() == 0) |
| 181 | MadeChange |= handleEndBlock(BB, possiblyDead); |
| 182 | |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 183 | // Do a trivial DCE |
| 184 | while (!possiblyDead.empty()) { |
| 185 | Instruction *I = possiblyDead.back(); |
| 186 | possiblyDead.pop_back(); |
| 187 | DeleteDeadInstructionChains(I, possiblyDead); |
| 188 | } |
| 189 | |
| 190 | return MadeChange; |
| 191 | } |
| 192 | |
Owen Anderson | a96c1f6 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 193 | /// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose |
| 194 | /// dependency is a store to a field of that structure |
Owen Anderson | f6a05f9 | 2007-08-01 06:36:51 +0000 | [diff] [blame] | 195 | bool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, Instruction* dep, |
Owen Anderson | 666f6fe | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 196 | SetVector<Instruction*>& possiblyDead) { |
Owen Anderson | a96c1f6 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 197 | TargetData &TD = getAnalysis<TargetData>(); |
| 198 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
| 199 | MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); |
| 200 | |
Owen Anderson | dd61c2b | 2007-07-12 18:08:51 +0000 | [diff] [blame] | 201 | if (dep == MemoryDependenceAnalysis::None || |
| 202 | dep == MemoryDependenceAnalysis::NonLocal) |
| 203 | return false; |
| 204 | |
| 205 | StoreInst* dependency = dyn_cast<StoreInst>(dep); |
| 206 | if (!dependency) |
| 207 | return false; |
Owen Anderson | 5dfcf43 | 2007-08-26 21:14:47 +0000 | [diff] [blame] | 208 | else if (dependency->isVolatile()) |
| 209 | return false; |
Owen Anderson | dd61c2b | 2007-07-12 18:08:51 +0000 | [diff] [blame] | 210 | |
Owen Anderson | a96c1f6 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 211 | Value* depPointer = dependency->getPointerOperand(); |
Owen Anderson | 666f6fe | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 212 | const Type* depType = dependency->getOperand(0)->getType(); |
Duncan Sands | 514ab34 | 2007-11-01 20:53:16 +0000 | [diff] [blame] | 213 | unsigned depPointerSize = TD.getTypeStoreSize(depType); |
Owen Anderson | 3e8d001 | 2007-07-13 18:26:26 +0000 | [diff] [blame] | 214 | |
Owen Anderson | a96c1f6 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 215 | // Check for aliasing |
| 216 | AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0UL, |
| 217 | depPointer, depPointerSize); |
| 218 | |
| 219 | if (A == AliasAnalysis::MustAlias) { |
| 220 | // Remove it! |
| 221 | MD.removeInstruction(dependency); |
Owen Anderson | a96c1f6 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 222 | |
| 223 | // DCE instructions only used to calculate that store |
| 224 | if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(0))) |
| 225 | possiblyDead.insert(D); |
Owen Anderson | 3e8d001 | 2007-07-13 18:26:26 +0000 | [diff] [blame] | 226 | if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(1))) |
| 227 | possiblyDead.insert(D); |
Owen Anderson | a96c1f6 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 228 | |
| 229 | dependency->eraseFromParent(); |
| 230 | NumFastStores++; |
| 231 | return true; |
| 232 | } |
| 233 | |
| 234 | return false; |
| 235 | } |
| 236 | |
Owen Anderson | 666f6fe | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 237 | /// handleEndBlock - Remove dead stores to stack-allocated locations in the |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 238 | /// function end block. Ex: |
| 239 | /// %A = alloca i32 |
| 240 | /// ... |
| 241 | /// store i32 1, i32* %A |
| 242 | /// ret void |
Owen Anderson | 666f6fe | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 243 | bool DSE::handleEndBlock(BasicBlock& BB, |
| 244 | SetVector<Instruction*>& possiblyDead) { |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 245 | TargetData &TD = getAnalysis<TargetData>(); |
| 246 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
| 247 | MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); |
| 248 | |
| 249 | bool MadeChange = false; |
| 250 | |
| 251 | // Pointers alloca'd in this function are dead in the end block |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 252 | SmallPtrSet<AllocaInst*, 64> deadPointers; |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 253 | |
| 254 | // Find all of the alloca'd pointers in the entry block |
| 255 | BasicBlock *Entry = BB.getParent()->begin(); |
| 256 | for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) |
| 257 | if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) |
| 258 | deadPointers.insert(AI); |
| 259 | |
| 260 | // Scan the basic block backwards |
| 261 | for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ |
| 262 | --BBI; |
| 263 | |
| 264 | if (deadPointers.empty()) |
| 265 | break; |
| 266 | |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 267 | // If we find a store whose pointer is dead... |
| 268 | if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { |
Owen Anderson | 5dfcf43 | 2007-08-26 21:14:47 +0000 | [diff] [blame] | 269 | if (!S->isVolatile()) { |
| 270 | Value* pointerOperand = S->getPointerOperand(); |
| 271 | // See through pointer-to-pointer bitcasts |
| 272 | TranslatePointerBitCasts(pointerOperand); |
Owen Anderson | 3e8d001 | 2007-07-13 18:26:26 +0000 | [diff] [blame] | 273 | |
Chris Lattner | 6390ae0 | 2007-11-06 22:07:22 +0000 | [diff] [blame] | 274 | if (isa<AllocaInst>(pointerOperand) && |
| 275 | deadPointers.count(cast<AllocaInst>(pointerOperand))) { |
Owen Anderson | 5dfcf43 | 2007-08-26 21:14:47 +0000 | [diff] [blame] | 276 | // Remove it! |
| 277 | MD.removeInstruction(S); |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 278 | |
Owen Anderson | 5dfcf43 | 2007-08-26 21:14:47 +0000 | [diff] [blame] | 279 | // DCE instructions only used to calculate that store |
| 280 | if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0))) |
| 281 | possiblyDead.insert(D); |
| 282 | if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1))) |
| 283 | possiblyDead.insert(D); |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 284 | |
Owen Anderson | 5dfcf43 | 2007-08-26 21:14:47 +0000 | [diff] [blame] | 285 | BBI++; |
| 286 | S->eraseFromParent(); |
| 287 | NumFastStores++; |
| 288 | MadeChange = true; |
| 289 | } |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 290 | } |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 291 | |
| 292 | continue; |
| 293 | } |
| 294 | |
| 295 | Value* killPointer = 0; |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 296 | |
| 297 | // If we encounter a use of the pointer, it is no longer considered dead |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 298 | if (LoadInst* L = dyn_cast<LoadInst>(BBI)) { |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 299 | killPointer = L->getPointerOperand(); |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 300 | } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) { |
| 301 | killPointer = V->getOperand(0); |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 302 | } else if (AllocaInst* A = dyn_cast<AllocaInst>(BBI)) { |
| 303 | deadPointers.erase(A); |
| 304 | continue; |
| 305 | } else if (CallSite::get(BBI).getInstruction() != 0) { |
Owen Anderson | df359c2 | 2007-08-08 17:58:56 +0000 | [diff] [blame] | 306 | // If this call does not access memory, it can't |
| 307 | // be undeadifying any of our pointers. |
| 308 | CallSite CS = CallSite::get(BBI); |
Duncan Sands | dff6710 | 2007-12-01 07:51:45 +0000 | [diff] [blame] | 309 | if (AA.doesNotAccessMemory(CS)) |
Owen Anderson | df359c2 | 2007-08-08 17:58:56 +0000 | [diff] [blame] | 310 | continue; |
| 311 | |
Owen Anderson | 362bb52 | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 312 | unsigned modRef = 0; |
| 313 | unsigned other = 0; |
| 314 | |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 315 | // Remove any pointers made undead by the call from the dead set |
| 316 | std::vector<Instruction*> dead; |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 317 | for (SmallPtrSet<AllocaInst*, 64>::iterator I = deadPointers.begin(), |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 318 | E = deadPointers.end(); I != E; ++I) { |
Owen Anderson | 362bb52 | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 319 | // HACK: if we detect that our AA is imprecise, it's not |
| 320 | // worth it to scan the rest of the deadPointers set. Just |
| 321 | // assume that the AA will return ModRef for everything, and |
| 322 | // go ahead and bail. |
| 323 | if (modRef >= 16 && other == 0) { |
| 324 | deadPointers.clear(); |
| 325 | return MadeChange; |
| 326 | } |
| 327 | |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 328 | // Get size information for the alloca |
| 329 | unsigned pointerSize = ~0UL; |
| 330 | if (ConstantInt* C = dyn_cast<ConstantInt>((*I)->getArraySize())) |
Owen Anderson | 666f6fe | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 331 | pointerSize = C->getZExtValue() * \ |
Duncan Sands | 514ab34 | 2007-11-01 20:53:16 +0000 | [diff] [blame] | 332 | TD.getABITypeSize((*I)->getAllocatedType()); |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 333 | |
| 334 | // See if the call site touches it |
Owen Anderson | df359c2 | 2007-08-08 17:58:56 +0000 | [diff] [blame] | 335 | AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize); |
Owen Anderson | 362bb52 | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 336 | |
| 337 | if (A == AliasAnalysis::ModRef) |
| 338 | modRef++; |
| 339 | else |
| 340 | other++; |
| 341 | |
Owen Anderson | 3e8d001 | 2007-07-13 18:26:26 +0000 | [diff] [blame] | 342 | if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 343 | dead.push_back(*I); |
| 344 | } |
| 345 | |
| 346 | for (std::vector<Instruction*>::iterator I = dead.begin(), E = dead.end(); |
| 347 | I != E; ++I) |
Chris Lattner | 6390ae0 | 2007-11-06 22:07:22 +0000 | [diff] [blame] | 348 | if (AllocaInst *AI = dyn_cast<AllocaInst>(*I)) |
| 349 | deadPointers.erase(AI); |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 350 | |
| 351 | continue; |
| 352 | } |
| 353 | |
| 354 | if (!killPointer) |
| 355 | continue; |
| 356 | |
Owen Anderson | 362bb52 | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 357 | TranslatePointerBitCasts(killPointer); |
| 358 | |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 359 | // Deal with undead pointers |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 360 | MadeChange |= RemoveUndeadPointers(killPointer, BBI, |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 361 | deadPointers, possiblyDead); |
| 362 | } |
| 363 | |
| 364 | return MadeChange; |
| 365 | } |
| 366 | |
Owen Anderson | 362bb52 | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 367 | /// RemoveUndeadPointers - check for uses of a pointer that make it |
| 368 | /// undead when scanning for dead stores to alloca's. |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 369 | bool DSE::RemoveUndeadPointers(Value* killPointer, |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 370 | BasicBlock::iterator& BBI, |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 371 | SmallPtrSet<AllocaInst*, 64>& deadPointers, |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 372 | SetVector<Instruction*>& possiblyDead) { |
| 373 | TargetData &TD = getAnalysis<TargetData>(); |
| 374 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
| 375 | MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); |
| 376 | |
Owen Anderson | 362bb52 | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 377 | // If the kill pointer can be easily reduced to an alloca, |
| 378 | // don't bother doing extraneous AA queries |
| 379 | if (AllocaInst* A = dyn_cast<AllocaInst>(killPointer)) { |
| 380 | if (deadPointers.count(A)) |
| 381 | deadPointers.erase(A); |
| 382 | return false; |
Owen Anderson | 838014e | 2007-08-08 19:12:31 +0000 | [diff] [blame] | 383 | } else if (isa<GlobalValue>(killPointer)) { |
| 384 | // A global can't be in the dead pointer set |
| 385 | return false; |
Owen Anderson | 362bb52 | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 386 | } |
| 387 | |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 388 | bool MadeChange = false; |
| 389 | |
| 390 | std::vector<Instruction*> undead; |
| 391 | |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 392 | for (SmallPtrSet<AllocaInst*, 64>::iterator I = deadPointers.begin(), |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 393 | E = deadPointers.end(); I != E; ++I) { |
| 394 | // Get size information for the alloca |
| 395 | unsigned pointerSize = ~0UL; |
| 396 | if (ConstantInt* C = dyn_cast<ConstantInt>((*I)->getArraySize())) |
Owen Anderson | 666f6fe | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 397 | pointerSize = C->getZExtValue() * \ |
Duncan Sands | 514ab34 | 2007-11-01 20:53:16 +0000 | [diff] [blame] | 398 | TD.getABITypeSize((*I)->getAllocatedType()); |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 399 | |
| 400 | // See if this pointer could alias it |
Owen Anderson | 666f6fe | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 401 | AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize, |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 402 | killPointer, ~0UL); |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 403 | |
| 404 | // If it must-alias and a store, we can delete it |
| 405 | if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { |
| 406 | StoreInst* S = cast<StoreInst>(BBI); |
| 407 | |
| 408 | // Remove it! |
| 409 | MD.removeInstruction(S); |
| 410 | |
| 411 | // DCE instructions only used to calculate that store |
| 412 | if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0))) |
| 413 | possiblyDead.insert(D); |
Owen Anderson | 3e8d001 | 2007-07-13 18:26:26 +0000 | [diff] [blame] | 414 | if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1))) |
| 415 | possiblyDead.insert(D); |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 416 | |
| 417 | BBI++; |
| 418 | S->eraseFromParent(); |
| 419 | NumFastStores++; |
| 420 | MadeChange = true; |
| 421 | |
| 422 | continue; |
| 423 | |
| 424 | // Otherwise, it is undead |
| 425 | } else if (A != AliasAnalysis::NoAlias) |
| 426 | undead.push_back(*I); |
| 427 | } |
| 428 | |
| 429 | for (std::vector<Instruction*>::iterator I = undead.begin(), E = undead.end(); |
| 430 | I != E; ++I) |
Chris Lattner | 6390ae0 | 2007-11-06 22:07:22 +0000 | [diff] [blame] | 431 | if (AllocaInst *AI = dyn_cast<AllocaInst>(*I)) |
| 432 | deadPointers.erase(AI); |
Owen Anderson | 43b2676 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 433 | |
| 434 | return MadeChange; |
| 435 | } |
| 436 | |
Owen Anderson | bb3abf4 | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 437 | /// DeleteDeadInstructionChains - takes an instruction and a setvector of |
| 438 | /// dead instructions. If I is dead, it is erased, and its operands are |
| 439 | /// checked for deadness. If they are dead, they are added to the dead |
| 440 | /// setvector. |
Owen Anderson | f6a05f9 | 2007-08-01 06:36:51 +0000 | [diff] [blame] | 441 | void DSE::DeleteDeadInstructionChains(Instruction *I, |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 442 | SetVector<Instruction*> &DeadInsts) { |
| 443 | // Instruction must be dead. |
| 444 | if (!I->use_empty() || !isInstructionTriviallyDead(I)) return; |
| 445 | |
| 446 | // Let the memory dependence know |
| 447 | getAnalysis<MemoryDependenceAnalysis>().removeInstruction(I); |
| 448 | |
| 449 | // See if this made any operands dead. We do it this way in case the |
| 450 | // instruction uses the same operand twice. We don't want to delete a |
| 451 | // value then reference it. |
| 452 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { |
Owen Anderson | bfbfb3c | 2007-07-11 19:03:09 +0000 | [diff] [blame] | 453 | if (I->getOperand(i)->hasOneUse()) |
| 454 | if (Instruction* Op = dyn_cast<Instruction>(I->getOperand(i))) |
| 455 | DeadInsts.insert(Op); // Attempt to nuke it later. |
| 456 | |
Owen Anderson | b77c457 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 457 | I->setOperand(i, 0); // Drop from the operand list. |
| 458 | } |
| 459 | |
| 460 | I->eraseFromParent(); |
| 461 | ++NumFastOther; |
| 462 | } |