Owen Anderson | e359058 | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 1 | //===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===// |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | f3ebc3f | 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 | 5e72db3 | 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 | 10e52ed | 2007-08-01 06:36:51 +0000 | [diff] [blame] | 18 | #define DEBUG_TYPE "dse" |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 19 | #include "llvm/Transforms/Scalar.h" |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 20 | #include "llvm/Constants.h" |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 21 | #include "llvm/Function.h" |
| 22 | #include "llvm/Instructions.h" |
Owen Anderson | 48d3780 | 2008-01-29 06:18:36 +0000 | [diff] [blame] | 23 | #include "llvm/IntrinsicInst.h" |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 24 | #include "llvm/Pass.h" |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 25 | #include "llvm/ADT/SmallPtrSet.h" |
| 26 | #include "llvm/ADT/Statistic.h" |
Owen Anderson | aa07172 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 27 | #include "llvm/Analysis/AliasAnalysis.h" |
Owen Anderson | 3f33897 | 2008-07-28 16:14:26 +0000 | [diff] [blame] | 28 | #include "llvm/Analysis/Dominators.h" |
Victor Hernandez | f390e04 | 2009-10-27 20:05:49 +0000 | [diff] [blame] | 29 | #include "llvm/Analysis/MemoryBuiltins.h" |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 30 | #include "llvm/Analysis/MemoryDependenceAnalysis.h" |
Owen Anderson | aa07172 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 31 | #include "llvm/Target/TargetData.h" |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 32 | #include "llvm/Transforms/Utils/Local.h" |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 33 | using namespace llvm; |
| 34 | |
| 35 | STATISTIC(NumFastStores, "Number of stores deleted"); |
| 36 | STATISTIC(NumFastOther , "Number of other instrs removed"); |
| 37 | |
| 38 | namespace { |
Chris Lattner | 2dd09db | 2009-09-02 06:11:42 +0000 | [diff] [blame] | 39 | struct DSE : public FunctionPass { |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 40 | static char ID; // Pass identification, replacement for typeid |
Owen Anderson | 6c18d1a | 2010-10-19 17:21:58 +0000 | [diff] [blame] | 41 | DSE() : FunctionPass(ID) { |
| 42 | initializeDSEPass(*PassRegistry::getPassRegistry()); |
| 43 | } |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 44 | |
| 45 | virtual bool runOnFunction(Function &F) { |
| 46 | bool Changed = false; |
Chris Lattner | c053cbb | 2010-02-11 05:11:54 +0000 | [diff] [blame] | 47 | |
| 48 | DominatorTree &DT = getAnalysis<DominatorTree>(); |
| 49 | |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 50 | for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) |
Chris Lattner | c053cbb | 2010-02-11 05:11:54 +0000 | [diff] [blame] | 51 | // Only check non-dead blocks. Dead blocks may have strange pointer |
| 52 | // cycles that will confuse alias analysis. |
| 53 | if (DT.isReachableFromEntry(I)) |
| 54 | Changed |= runOnBasicBlock(*I); |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 55 | return Changed; |
| 56 | } |
Chris Lattner | de04e11 | 2008-11-29 01:43:36 +0000 | [diff] [blame] | 57 | |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 58 | bool runOnBasicBlock(BasicBlock &BB); |
Chris Lattner | 9d179d9 | 2010-11-30 01:28:33 +0000 | [diff] [blame] | 59 | bool HandleFree(CallInst *F); |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 60 | bool handleEndBlock(BasicBlock &BB); |
Dan Gohman | f372cf8 | 2010-10-19 22:54:46 +0000 | [diff] [blame] | 61 | bool RemoveUndeadPointers(Value *Ptr, uint64_t killPointerSize, |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 62 | BasicBlock::iterator &BBI, |
| 63 | SmallPtrSet<Value*, 64> &deadPointers); |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 64 | void DeleteDeadInstruction(Instruction *I, |
| 65 | SmallPtrSet<Value*, 64> *deadPointers = 0); |
| 66 | |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 67 | |
| 68 | // getAnalysisUsage - We require post dominance frontiers (aka Control |
| 69 | // Dependence Graph) |
| 70 | virtual void getAnalysisUsage(AnalysisUsage &AU) const { |
| 71 | AU.setPreservesCFG(); |
Owen Anderson | 3f33897 | 2008-07-28 16:14:26 +0000 | [diff] [blame] | 72 | AU.addRequired<DominatorTree>(); |
Owen Anderson | aa07172 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 73 | AU.addRequired<AliasAnalysis>(); |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 74 | AU.addRequired<MemoryDependenceAnalysis>(); |
Owen Anderson | 3f33897 | 2008-07-28 16:14:26 +0000 | [diff] [blame] | 75 | AU.addPreserved<DominatorTree>(); |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 76 | AU.addPreserved<MemoryDependenceAnalysis>(); |
| 77 | } |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 78 | |
Chris Lattner | 77d79fa | 2010-11-30 19:28:23 +0000 | [diff] [blame^] | 79 | uint64_t getPointerSize(Value *V, AliasAnalysis &AA) const; |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 80 | }; |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 81 | } |
| 82 | |
Dan Gohman | d78c400 | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 83 | char DSE::ID = 0; |
Owen Anderson | 8ac477f | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 84 | INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false) |
| 85 | INITIALIZE_PASS_DEPENDENCY(DominatorTree) |
| 86 | INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) |
| 87 | INITIALIZE_AG_DEPENDENCY(AliasAnalysis) |
| 88 | INITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false) |
Dan Gohman | d78c400 | 2008-05-13 00:00:25 +0000 | [diff] [blame] | 89 | |
Owen Anderson | 10e52ed | 2007-08-01 06:36:51 +0000 | [diff] [blame] | 90 | FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 91 | |
Chris Lattner | 2227a8a | 2010-11-30 01:37:52 +0000 | [diff] [blame] | 92 | /// hasMemoryWrite - Does this instruction write some memory? This only returns |
| 93 | /// true for things that we can analyze with other helpers below. |
| 94 | static bool hasMemoryWrite(Instruction *I) { |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 95 | if (isa<StoreInst>(I)) |
| 96 | return true; |
| 97 | if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { |
| 98 | switch (II->getIntrinsicID()) { |
Chris Lattner | 2764b4d | 2009-12-02 06:35:55 +0000 | [diff] [blame] | 99 | default: |
| 100 | return false; |
| 101 | case Intrinsic::memset: |
| 102 | case Intrinsic::memmove: |
| 103 | case Intrinsic::memcpy: |
| 104 | case Intrinsic::init_trampoline: |
| 105 | case Intrinsic::lifetime_end: |
| 106 | return true; |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 107 | } |
| 108 | } |
| 109 | return false; |
| 110 | } |
| 111 | |
Chris Lattner | 58b779e | 2010-11-30 07:23:21 +0000 | [diff] [blame] | 112 | /// getLocForWrite - Return a Location stored to by the specified instruction. |
| 113 | static AliasAnalysis::Location |
| 114 | getLocForWrite(Instruction *Inst, AliasAnalysis &AA) { |
| 115 | if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) |
| 116 | return AA.getLocation(SI); |
| 117 | |
| 118 | if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) { |
| 119 | // memcpy/memmove/memset. |
| 120 | AliasAnalysis::Location Loc = AA.getLocationForDest(MI); |
| 121 | // If we don't have target data around, an unknown size in Location means |
| 122 | // that we should use the size of the pointee type. This isn't valid for |
| 123 | // memset/memcpy, which writes more than an i8. |
| 124 | if (Loc.Size == AliasAnalysis::UnknownSize && AA.getTargetData() == 0) |
| 125 | return AliasAnalysis::Location(); |
| 126 | return Loc; |
| 127 | } |
| 128 | |
| 129 | IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst); |
| 130 | if (II == 0) return AliasAnalysis::Location(); |
| 131 | |
| 132 | switch (II->getIntrinsicID()) { |
| 133 | default: return AliasAnalysis::Location(); // Unhandled intrinsic. |
| 134 | case Intrinsic::init_trampoline: |
| 135 | // If we don't have target data around, an unknown size in Location means |
| 136 | // that we should use the size of the pointee type. This isn't valid for |
| 137 | // init.trampoline, which writes more than an i8. |
| 138 | if (AA.getTargetData() == 0) return AliasAnalysis::Location(); |
| 139 | |
| 140 | // FIXME: We don't know the size of the trampoline, so we can't really |
| 141 | // handle it here. |
| 142 | return AliasAnalysis::Location(II->getArgOperand(0)); |
| 143 | case Intrinsic::lifetime_end: { |
| 144 | uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); |
| 145 | return AliasAnalysis::Location(II->getArgOperand(1), Len); |
| 146 | } |
| 147 | } |
| 148 | } |
| 149 | |
Chris Lattner | 3590ef8 | 2010-11-30 05:30:45 +0000 | [diff] [blame] | 150 | /// isRemovable - If the value of this instruction and the memory it writes to |
| 151 | /// is unused, may we delete this instruction? |
| 152 | static bool isRemovable(Instruction *I) { |
Chris Lattner | b63ba73 | 2010-11-30 19:12:10 +0000 | [diff] [blame] | 153 | // Don't remove volatile stores. |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 154 | if (StoreInst *SI = dyn_cast<StoreInst>(I)) |
| 155 | return !SI->isVolatile(); |
Chris Lattner | b63ba73 | 2010-11-30 19:12:10 +0000 | [diff] [blame] | 156 | |
| 157 | IntrinsicInst *II = cast<IntrinsicInst>(I); |
| 158 | switch (II->getIntrinsicID()) { |
| 159 | default: assert(0 && "doesn't pass 'hasMemoryWrite' predicate"); |
| 160 | case Intrinsic::lifetime_end: |
| 161 | // Never remove dead lifetime_end's, e.g. because it is followed by a |
| 162 | // free. |
| 163 | return false; |
| 164 | case Intrinsic::init_trampoline: |
| 165 | // Always safe to remove init_trampoline. |
| 166 | return true; |
| 167 | |
| 168 | case Intrinsic::memset: |
| 169 | case Intrinsic::memmove: |
| 170 | case Intrinsic::memcpy: |
| 171 | // Don't remove volatile memory intrinsics. |
| 172 | return !cast<MemIntrinsic>(II)->isVolatile(); |
| 173 | } |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 174 | } |
| 175 | |
Chris Lattner | 9d179d9 | 2010-11-30 01:28:33 +0000 | [diff] [blame] | 176 | /// getPointerOperand - Return the pointer that is being written to. |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 177 | static Value *getPointerOperand(Instruction *I) { |
Chris Lattner | 2227a8a | 2010-11-30 01:37:52 +0000 | [diff] [blame] | 178 | assert(hasMemoryWrite(I)); |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 179 | if (StoreInst *SI = dyn_cast<StoreInst>(I)) |
| 180 | return SI->getPointerOperand(); |
| 181 | if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) |
Gabor Greif | 91f9589 | 2010-06-24 12:03:56 +0000 | [diff] [blame] | 182 | return MI->getArgOperand(0); |
| 183 | |
| 184 | IntrinsicInst *II = cast<IntrinsicInst>(I); |
| 185 | switch (II->getIntrinsicID()) { |
Chris Lattner | 2764b4d | 2009-12-02 06:35:55 +0000 | [diff] [blame] | 186 | default: assert(false && "Unexpected intrinsic!"); |
| 187 | case Intrinsic::init_trampoline: |
Gabor Greif | 91f9589 | 2010-06-24 12:03:56 +0000 | [diff] [blame] | 188 | return II->getArgOperand(0); |
Eric Christopher | 7258dcd | 2010-04-16 23:37:20 +0000 | [diff] [blame] | 189 | case Intrinsic::lifetime_end: |
Gabor Greif | 91f9589 | 2010-06-24 12:03:56 +0000 | [diff] [blame] | 190 | return II->getArgOperand(1); |
Duncan Sands | 1925d3a | 2009-11-10 13:49:50 +0000 | [diff] [blame] | 191 | } |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 192 | } |
| 193 | |
Chris Lattner | 58b779e | 2010-11-30 07:23:21 +0000 | [diff] [blame] | 194 | /// isCompleteOverwrite - Return true if a store to the 'Later' location |
| 195 | /// completely overwrites a store to the 'Earlier' location. |
| 196 | static bool isCompleteOverwrite(const AliasAnalysis::Location &Later, |
| 197 | const AliasAnalysis::Location &Earlier, |
Chris Lattner | 77d79fa | 2010-11-30 19:28:23 +0000 | [diff] [blame^] | 198 | AliasAnalysis &AA) { |
Chris Lattner | 58b779e | 2010-11-30 07:23:21 +0000 | [diff] [blame] | 199 | const Value *P1 = Later.Ptr->stripPointerCasts(); |
| 200 | const Value *P2 = Earlier.Ptr->stripPointerCasts(); |
| 201 | |
| 202 | // Make sure that the start pointers are the same. |
| 203 | if (P1 != P2) |
| 204 | return false; |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 205 | |
Chris Lattner | 77d79fa | 2010-11-30 19:28:23 +0000 | [diff] [blame^] | 206 | // If we don't know the sizes of either access, then we can't do a comparison. |
| 207 | if (Later.Size == AliasAnalysis::UnknownSize || |
| 208 | Earlier.Size == AliasAnalysis::UnknownSize) { |
| 209 | // If we have no TargetData information around, then the size of the store |
| 210 | // is inferrable from the pointee type. If they are the same type, then we |
| 211 | // know that the store is safe. |
| 212 | if (AA.getTargetData() == 0) |
| 213 | return Later.Ptr->getType() == Earlier.Ptr->getType(); |
| 214 | return false; |
| 215 | } |
Chris Lattner | 58b779e | 2010-11-30 07:23:21 +0000 | [diff] [blame] | 216 | |
| 217 | // Make sure that the Later size is >= the Earlier size. |
| 218 | if (Later.Size < Earlier.Size) |
| 219 | return false; |
| 220 | |
| 221 | return true; |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 222 | } |
| 223 | |
Owen Anderson | 10e52ed | 2007-08-01 06:36:51 +0000 | [diff] [blame] | 224 | bool DSE::runOnBasicBlock(BasicBlock &BB) { |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 225 | MemoryDependenceAnalysis &MD = getAnalysis<MemoryDependenceAnalysis>(); |
Chris Lattner | 3590ef8 | 2010-11-30 05:30:45 +0000 | [diff] [blame] | 226 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
Owen Anderson | 2ed651a | 2007-11-01 05:29:16 +0000 | [diff] [blame] | 227 | |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 228 | bool MadeChange = false; |
| 229 | |
Chris Lattner | 4916267 | 2009-09-02 06:31:02 +0000 | [diff] [blame] | 230 | // Do a top-down walk on the BB. |
Chris Lattner | f2a8ba4 | 2008-11-28 21:29:52 +0000 | [diff] [blame] | 231 | for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { |
| 232 | Instruction *Inst = BBI++; |
| 233 | |
Chris Lattner | 9d179d9 | 2010-11-30 01:28:33 +0000 | [diff] [blame] | 234 | // Handle 'free' calls specially. |
| 235 | if (CallInst *F = isFreeCall(Inst)) { |
| 236 | MadeChange |= HandleFree(F); |
| 237 | continue; |
| 238 | } |
| 239 | |
Chris Lattner | 2227a8a | 2010-11-30 01:37:52 +0000 | [diff] [blame] | 240 | // If we find something that writes memory, get its memory dependence. |
| 241 | if (!hasMemoryWrite(Inst)) |
Owen Anderson | 0aecf0e | 2007-08-08 04:52:29 +0000 | [diff] [blame] | 242 | continue; |
Chris Lattner | d4f1090 | 2010-11-30 00:01:19 +0000 | [diff] [blame] | 243 | |
Chris Lattner | 57e91ea | 2008-12-06 00:53:22 +0000 | [diff] [blame] | 244 | MemDepResult InstDep = MD.getDependency(Inst); |
Chris Lattner | f2a8ba4 | 2008-11-28 21:29:52 +0000 | [diff] [blame] | 245 | |
Chris Lattner | d4f1090 | 2010-11-30 00:01:19 +0000 | [diff] [blame] | 246 | // Ignore non-local store liveness. |
Chris Lattner | 57e91ea | 2008-12-06 00:53:22 +0000 | [diff] [blame] | 247 | // FIXME: cross-block DSE would be fun. :) |
Chris Lattner | 58b779e | 2010-11-30 07:23:21 +0000 | [diff] [blame] | 248 | if (InstDep.isNonLocal() || |
| 249 | // Ignore self dependence, which happens in the entry block of the |
| 250 | // function. |
| 251 | InstDep.getInst() == Inst) |
| 252 | continue; |
Chris Lattner | 9d179d9 | 2010-11-30 01:28:33 +0000 | [diff] [blame] | 253 | |
Chris Lattner | 57e91ea | 2008-12-06 00:53:22 +0000 | [diff] [blame] | 254 | // If we're storing the same value back to a pointer that we just |
| 255 | // loaded from, then the store can be removed. |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 256 | if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { |
| 257 | if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) { |
| 258 | if (SI->getPointerOperand() == DepLoad->getPointerOperand() && |
Chris Lattner | c3c754f | 2010-11-30 00:12:39 +0000 | [diff] [blame] | 259 | SI->getOperand(0) == DepLoad && !SI->isVolatile()) { |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 260 | // DeleteDeadInstruction can delete the current instruction. Save BBI |
| 261 | // in case we need it. |
| 262 | WeakVH NextInst(BBI); |
| 263 | |
| 264 | DeleteDeadInstruction(SI); |
| 265 | |
| 266 | if (NextInst == 0) // Next instruction deleted. |
| 267 | BBI = BB.begin(); |
| 268 | else if (BBI != BB.begin()) // Revisit this instruction if possible. |
| 269 | --BBI; |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 270 | ++NumFastStores; |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 271 | MadeChange = true; |
| 272 | continue; |
| 273 | } |
Chris Lattner | 0e3d633 | 2008-12-05 21:04:20 +0000 | [diff] [blame] | 274 | } |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 275 | } |
Chris Lattner | 3590ef8 | 2010-11-30 05:30:45 +0000 | [diff] [blame] | 276 | |
Chris Lattner | 58b779e | 2010-11-30 07:23:21 +0000 | [diff] [blame] | 277 | // Figure out what location is being stored to. |
| 278 | AliasAnalysis::Location Loc = getLocForWrite(Inst, AA); |
| 279 | |
| 280 | // If we didn't get a useful location, fail. |
| 281 | if (Loc.Ptr == 0) |
| 282 | continue; |
| 283 | |
| 284 | while (!InstDep.isNonLocal()) { |
| 285 | // Get the memory clobbered by the instruction we depend on. MemDep will |
| 286 | // skip any instructions that 'Loc' clearly doesn't interact with. If we |
| 287 | // end up depending on a may- or must-aliased load, then we can't optimize |
| 288 | // away the store and we bail out. However, if we depend on on something |
| 289 | // that overwrites the memory location we *can* potentially optimize it. |
| 290 | // |
| 291 | // Find out what memory location the dependant instruction stores. |
| 292 | Instruction *DepWrite = InstDep.getInst(); |
| 293 | AliasAnalysis::Location DepLoc = getLocForWrite(DepWrite, AA); |
| 294 | // If we didn't get a useful location, or if it isn't a size, bail out. |
| 295 | if (DepLoc.Ptr == 0) |
| 296 | break; |
| 297 | |
| 298 | // If we find a removable write that is completely obliterated by the |
| 299 | // store to 'Loc' then we can remove it. |
Chris Lattner | 77d79fa | 2010-11-30 19:28:23 +0000 | [diff] [blame^] | 300 | if (isRemovable(DepWrite) && isCompleteOverwrite(Loc, DepLoc, AA)) { |
Chris Lattner | 58b779e | 2010-11-30 07:23:21 +0000 | [diff] [blame] | 301 | // Delete the store and now-dead instructions that feed it. |
| 302 | DeleteDeadInstruction(DepWrite); |
| 303 | ++NumFastStores; |
| 304 | MadeChange = true; |
| 305 | |
| 306 | // DeleteDeadInstruction can delete the current instruction in loop |
| 307 | // cases, reset BBI. |
| 308 | BBI = Inst; |
| 309 | if (BBI != BB.begin()) |
| 310 | --BBI; |
| 311 | break; |
| 312 | } |
| 313 | |
Chris Lattner | d4f1090 | 2010-11-30 00:01:19 +0000 | [diff] [blame] | 314 | // If this is a may-aliased store that is clobbering the store value, we |
| 315 | // can keep searching past it for another must-aliased pointer that stores |
| 316 | // to the same location. For example, in: |
| 317 | // store -> P |
| 318 | // store -> Q |
| 319 | // store -> P |
| 320 | // we can remove the first store to P even though we don't know if P and Q |
| 321 | // alias. |
Chris Lattner | 58b779e | 2010-11-30 07:23:21 +0000 | [diff] [blame] | 322 | if (DepWrite == &BB.front()) break; |
| 323 | |
| 324 | // Can't look past this instruction if it might read 'Loc'. |
| 325 | if (AA.getModRefInfo(DepWrite, Loc) & AliasAnalysis::Ref) |
| 326 | break; |
Chris Lattner | 3590ef8 | 2010-11-30 05:30:45 +0000 | [diff] [blame] | 327 | |
Chris Lattner | 58b779e | 2010-11-30 07:23:21 +0000 | [diff] [blame] | 328 | InstDep = MD.getPointerDependencyFrom(Loc, false, DepWrite, &BB); |
Owen Anderson | 2b2bd28 | 2009-10-28 07:05:35 +0000 | [diff] [blame] | 329 | } |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 330 | } |
| 331 | |
Chris Lattner | f2a8ba4 | 2008-11-28 21:29:52 +0000 | [diff] [blame] | 332 | // If this block ends in a return, unwind, or unreachable, all allocas are |
| 333 | // dead at its end, which means stores to them are also dead. |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 334 | if (BB.getTerminator()->getNumSuccessors() == 0) |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 335 | MadeChange |= handleEndBlock(BB); |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 336 | |
| 337 | return MadeChange; |
| 338 | } |
| 339 | |
Chris Lattner | 9d179d9 | 2010-11-30 01:28:33 +0000 | [diff] [blame] | 340 | /// HandleFree - Handle frees of entire structures whose dependency is a store |
| 341 | /// to a field of that structure. |
| 342 | bool DSE::HandleFree(CallInst *F) { |
Owen Anderson | aa07172 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 343 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
Dan Gohman | d4b7fff | 2010-11-12 02:19:17 +0000 | [diff] [blame] | 344 | MemoryDependenceAnalysis &MD = getAnalysis<MemoryDependenceAnalysis>(); |
Chris Lattner | 9d179d9 | 2010-11-30 01:28:33 +0000 | [diff] [blame] | 345 | |
| 346 | MemDepResult Dep = MD.getDependency(F); |
Dan Gohman | d4b7fff | 2010-11-12 02:19:17 +0000 | [diff] [blame] | 347 | do { |
Chris Lattner | 9d179d9 | 2010-11-30 01:28:33 +0000 | [diff] [blame] | 348 | if (Dep.isNonLocal()) return false; |
| 349 | |
Dan Gohman | d4b7fff | 2010-11-12 02:19:17 +0000 | [diff] [blame] | 350 | Instruction *Dependency = Dep.getInst(); |
Chris Lattner | 3590ef8 | 2010-11-30 05:30:45 +0000 | [diff] [blame] | 351 | if (!hasMemoryWrite(Dependency) || !isRemovable(Dependency)) |
Dan Gohman | d4b7fff | 2010-11-12 02:19:17 +0000 | [diff] [blame] | 352 | return false; |
Owen Anderson | d4451de | 2007-07-12 18:08:51 +0000 | [diff] [blame] | 353 | |
Dan Gohman | d4b7fff | 2010-11-12 02:19:17 +0000 | [diff] [blame] | 354 | Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject(); |
Duncan Sands | fe3bef0 | 2008-01-20 10:49:23 +0000 | [diff] [blame] | 355 | |
Dan Gohman | d4b7fff | 2010-11-12 02:19:17 +0000 | [diff] [blame] | 356 | // Check for aliasing. |
| 357 | if (AA.alias(F->getArgOperand(0), 1, DepPointer, 1) != |
Chris Lattner | 9d179d9 | 2010-11-30 01:28:33 +0000 | [diff] [blame] | 358 | AliasAnalysis::MustAlias) |
Dan Gohman | d4b7fff | 2010-11-12 02:19:17 +0000 | [diff] [blame] | 359 | return false; |
Owen Anderson | aa07172 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 360 | |
Dan Gohman | d4b7fff | 2010-11-12 02:19:17 +0000 | [diff] [blame] | 361 | // DCE instructions only used to calculate that store |
| 362 | DeleteDeadInstruction(Dependency); |
| 363 | ++NumFastStores; |
| 364 | |
| 365 | // Inst's old Dependency is now deleted. Compute the next dependency, |
| 366 | // which may also be dead, as in |
| 367 | // s[0] = 0; |
| 368 | // s[1] = 0; // This has just been deleted. |
| 369 | // free(s); |
Chris Lattner | 9d179d9 | 2010-11-30 01:28:33 +0000 | [diff] [blame] | 370 | Dep = MD.getDependency(F); |
Dan Gohman | d4b7fff | 2010-11-12 02:19:17 +0000 | [diff] [blame] | 371 | } while (!Dep.isNonLocal()); |
Chris Lattner | 9d179d9 | 2010-11-30 01:28:33 +0000 | [diff] [blame] | 372 | |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 373 | return true; |
Owen Anderson | aa07172 | 2007-07-11 23:19:17 +0000 | [diff] [blame] | 374 | } |
| 375 | |
Owen Anderson | e359058 | 2007-08-02 18:11:11 +0000 | [diff] [blame] | 376 | /// handleEndBlock - Remove dead stores to stack-allocated locations in the |
Owen Anderson | 52aaabf | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 377 | /// function end block. Ex: |
| 378 | /// %A = alloca i32 |
| 379 | /// ... |
| 380 | /// store i32 1, i32* %A |
| 381 | /// ret void |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 382 | bool DSE::handleEndBlock(BasicBlock &BB) { |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 383 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 384 | |
| 385 | bool MadeChange = false; |
| 386 | |
| 387 | // Pointers alloca'd in this function are dead in the end block |
Owen Anderson | 48d3780 | 2008-01-29 06:18:36 +0000 | [diff] [blame] | 388 | SmallPtrSet<Value*, 64> deadPointers; |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 389 | |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 390 | // Find all of the alloca'd pointers in the entry block. |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 391 | BasicBlock *Entry = BB.getParent()->begin(); |
| 392 | for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) |
| 393 | if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) |
| 394 | deadPointers.insert(AI); |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 395 | |
| 396 | // Treat byval arguments the same, stores to them are dead at the end of the |
| 397 | // function. |
Owen Anderson | 48d3780 | 2008-01-29 06:18:36 +0000 | [diff] [blame] | 398 | for (Function::arg_iterator AI = BB.getParent()->arg_begin(), |
| 399 | AE = BB.getParent()->arg_end(); AI != AE; ++AI) |
| 400 | if (AI->hasByValAttr()) |
| 401 | deadPointers.insert(AI); |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 402 | |
| 403 | // Scan the basic block backwards |
| 404 | for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ |
| 405 | --BBI; |
| 406 | |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 407 | // If we find a store whose pointer is dead. |
Chris Lattner | 2227a8a | 2010-11-30 01:37:52 +0000 | [diff] [blame] | 408 | if (hasMemoryWrite(BBI)) { |
Chris Lattner | 3590ef8 | 2010-11-30 05:30:45 +0000 | [diff] [blame] | 409 | if (isRemovable(BBI)) { |
Owen Anderson | 2b9ec7f | 2007-08-26 21:14:47 +0000 | [diff] [blame] | 410 | // See through pointer-to-pointer bitcasts |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 411 | Value *pointerOperand = getPointerOperand(BBI)->getUnderlyingObject(); |
Duncan Sands | d65a4da | 2008-10-01 15:25:41 +0000 | [diff] [blame] | 412 | |
Owen Anderson | 6af19fd | 2008-01-25 10:10:33 +0000 | [diff] [blame] | 413 | // Alloca'd pointers or byval arguments (which are functionally like |
| 414 | // alloca's) are valid candidates for removal. |
Owen Anderson | 48d3780 | 2008-01-29 06:18:36 +0000 | [diff] [blame] | 415 | if (deadPointers.count(pointerOperand)) { |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 416 | // DCE instructions only used to calculate that store. |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 417 | Instruction *Dead = BBI; |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 418 | ++BBI; |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 419 | DeleteDeadInstruction(Dead, &deadPointers); |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 420 | ++NumFastStores; |
Owen Anderson | 2b9ec7f | 2007-08-26 21:14:47 +0000 | [diff] [blame] | 421 | MadeChange = true; |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 422 | continue; |
Owen Anderson | 2b9ec7f | 2007-08-26 21:14:47 +0000 | [diff] [blame] | 423 | } |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 424 | } |
Owen Anderson | 52aaabf | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 425 | |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 426 | // Because a memcpy or memmove is also a load, we can't skip it if we |
| 427 | // didn't remove it. |
| 428 | if (!isa<MemTransferInst>(BBI)) |
Owen Anderson | 48d3780 | 2008-01-29 06:18:36 +0000 | [diff] [blame] | 429 | continue; |
Owen Anderson | 52aaabf | 2007-08-08 17:50:09 +0000 | [diff] [blame] | 430 | } |
| 431 | |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 432 | Value *killPointer = 0; |
Dan Gohman | f372cf8 | 2010-10-19 22:54:46 +0000 | [diff] [blame] | 433 | uint64_t killPointerSize = AliasAnalysis::UnknownSize; |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 434 | |
| 435 | // If we encounter a use of the pointer, it is no longer considered dead |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 436 | if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { |
Nate Begeman | 53c5c62 | 2008-05-13 01:48:26 +0000 | [diff] [blame] | 437 | // However, if this load is unused and not volatile, we can go ahead and |
| 438 | // remove it, and not have to worry about it making our pointer undead! |
Dan Gohman | 8cb19d9 | 2008-04-28 19:51:27 +0000 | [diff] [blame] | 439 | if (L->use_empty() && !L->isVolatile()) { |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 440 | ++BBI; |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 441 | DeleteDeadInstruction(L, &deadPointers); |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 442 | ++NumFastOther; |
Owen Anderson | 4e4b116 | 2008-01-30 01:24:47 +0000 | [diff] [blame] | 443 | MadeChange = true; |
Owen Anderson | 4e4b116 | 2008-01-30 01:24:47 +0000 | [diff] [blame] | 444 | continue; |
| 445 | } |
| 446 | |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 447 | killPointer = L->getPointerOperand(); |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 448 | } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) { |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 449 | killPointer = V->getOperand(0); |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 450 | } else if (isa<MemTransferInst>(BBI) && |
| 451 | isa<ConstantInt>(cast<MemTransferInst>(BBI)->getLength())) { |
| 452 | killPointer = cast<MemTransferInst>(BBI)->getSource(); |
Owen Anderson | a82c993 | 2008-02-04 04:53:00 +0000 | [diff] [blame] | 453 | killPointerSize = cast<ConstantInt>( |
Nick Lewycky | 9027147 | 2009-11-10 06:46:40 +0000 | [diff] [blame] | 454 | cast<MemTransferInst>(BBI)->getLength())->getZExtValue(); |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 455 | } else if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) { |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 456 | deadPointers.erase(A); |
Owen Anderson | 4e4b116 | 2008-01-30 01:24:47 +0000 | [diff] [blame] | 457 | |
| 458 | // Dead alloca's can be DCE'd when we reach them |
Nick Lewycky | 6b01670 | 2008-01-30 08:01:28 +0000 | [diff] [blame] | 459 | if (A->use_empty()) { |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 460 | ++BBI; |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 461 | DeleteDeadInstruction(A, &deadPointers); |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 462 | ++NumFastOther; |
Owen Anderson | 4e4b116 | 2008-01-30 01:24:47 +0000 | [diff] [blame] | 463 | MadeChange = true; |
Owen Anderson | 4e4b116 | 2008-01-30 01:24:47 +0000 | [diff] [blame] | 464 | } |
| 465 | |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 466 | continue; |
Gabor Greif | 0a97069 | 2010-07-28 14:28:18 +0000 | [diff] [blame] | 467 | } else if (CallSite CS = cast<Value>(BBI)) { |
Owen Anderson | 50df968 | 2007-08-08 17:58:56 +0000 | [diff] [blame] | 468 | // If this call does not access memory, it can't |
| 469 | // be undeadifying any of our pointers. |
Duncan Sands | 68b6f50 | 2007-12-01 07:51:45 +0000 | [diff] [blame] | 470 | if (AA.doesNotAccessMemory(CS)) |
Owen Anderson | 50df968 | 2007-08-08 17:58:56 +0000 | [diff] [blame] | 471 | continue; |
| 472 | |
Owen Anderson | ddf4aee | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 473 | unsigned modRef = 0; |
| 474 | unsigned other = 0; |
| 475 | |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 476 | // Remove any pointers made undead by the call from the dead set |
Owen Anderson | 48d3780 | 2008-01-29 06:18:36 +0000 | [diff] [blame] | 477 | std::vector<Value*> dead; |
| 478 | for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 479 | E = deadPointers.end(); I != E; ++I) { |
Owen Anderson | ddf4aee | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 480 | // HACK: if we detect that our AA is imprecise, it's not |
| 481 | // worth it to scan the rest of the deadPointers set. Just |
| 482 | // assume that the AA will return ModRef for everything, and |
| 483 | // go ahead and bail. |
| 484 | if (modRef >= 16 && other == 0) { |
| 485 | deadPointers.clear(); |
| 486 | return MadeChange; |
| 487 | } |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 488 | |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 489 | // See if the call site touches it |
Chris Lattner | 77d79fa | 2010-11-30 19:28:23 +0000 | [diff] [blame^] | 490 | AliasAnalysis::ModRefResult A = |
| 491 | AA.getModRefInfo(CS, *I, getPointerSize(*I, AA)); |
Owen Anderson | ddf4aee | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 492 | |
| 493 | if (A == AliasAnalysis::ModRef) |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 494 | ++modRef; |
Owen Anderson | ddf4aee | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 495 | else |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 496 | ++other; |
Owen Anderson | ddf4aee | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 497 | |
Owen Anderson | 9c9ef21 | 2007-07-13 18:26:26 +0000 | [diff] [blame] | 498 | if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 499 | dead.push_back(*I); |
| 500 | } |
| 501 | |
Owen Anderson | 48d3780 | 2008-01-29 06:18:36 +0000 | [diff] [blame] | 502 | for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end(); |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 503 | I != E; ++I) |
Owen Anderson | 48d3780 | 2008-01-29 06:18:36 +0000 | [diff] [blame] | 504 | deadPointers.erase(*I); |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 505 | |
| 506 | continue; |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 507 | } else if (isInstructionTriviallyDead(BBI)) { |
Owen Anderson | 4e4b116 | 2008-01-30 01:24:47 +0000 | [diff] [blame] | 508 | // For any non-memory-affecting non-terminators, DCE them as we reach them |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 509 | Instruction *Inst = BBI; |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 510 | ++BBI; |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 511 | DeleteDeadInstruction(Inst, &deadPointers); |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 512 | ++NumFastOther; |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 513 | MadeChange = true; |
| 514 | continue; |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 515 | } |
| 516 | |
| 517 | if (!killPointer) |
| 518 | continue; |
Duncan Sands | d65a4da | 2008-10-01 15:25:41 +0000 | [diff] [blame] | 519 | |
| 520 | killPointer = killPointer->getUnderlyingObject(); |
| 521 | |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 522 | // Deal with undead pointers |
Owen Anderson | a82c993 | 2008-02-04 04:53:00 +0000 | [diff] [blame] | 523 | MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI, |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 524 | deadPointers); |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 525 | } |
| 526 | |
| 527 | return MadeChange; |
| 528 | } |
| 529 | |
Owen Anderson | ddf4aee | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 530 | /// RemoveUndeadPointers - check for uses of a pointer that make it |
| 531 | /// undead when scanning for dead stores to alloca's. |
Dan Gohman | f372cf8 | 2010-10-19 22:54:46 +0000 | [diff] [blame] | 532 | bool DSE::RemoveUndeadPointers(Value *killPointer, uint64_t killPointerSize, |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 533 | BasicBlock::iterator &BBI, |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 534 | SmallPtrSet<Value*, 64> &deadPointers) { |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 535 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 536 | |
Owen Anderson | ddf4aee | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 537 | // If the kill pointer can be easily reduced to an alloca, |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 538 | // don't bother doing extraneous AA queries. |
Owen Anderson | 48d3780 | 2008-01-29 06:18:36 +0000 | [diff] [blame] | 539 | if (deadPointers.count(killPointer)) { |
| 540 | deadPointers.erase(killPointer); |
Owen Anderson | ddf4aee | 2007-08-08 18:38:28 +0000 | [diff] [blame] | 541 | return false; |
| 542 | } |
| 543 | |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 544 | // A global can't be in the dead pointer set. |
| 545 | if (isa<GlobalValue>(killPointer)) |
| 546 | return false; |
| 547 | |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 548 | bool MadeChange = false; |
| 549 | |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 550 | SmallVector<Value*, 16> undead; |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 551 | |
Owen Anderson | 48d3780 | 2008-01-29 06:18:36 +0000 | [diff] [blame] | 552 | for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 553 | E = deadPointers.end(); I != E; ++I) { |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 554 | // See if this pointer could alias it |
Chris Lattner | 77d79fa | 2010-11-30 19:28:23 +0000 | [diff] [blame^] | 555 | AliasAnalysis::AliasResult A = AA.alias(*I, getPointerSize(*I, AA), |
Owen Anderson | a82c993 | 2008-02-04 04:53:00 +0000 | [diff] [blame] | 556 | killPointer, killPointerSize); |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 557 | |
| 558 | // If it must-alias and a store, we can delete it |
| 559 | if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 560 | StoreInst *S = cast<StoreInst>(BBI); |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 561 | |
| 562 | // Remove it! |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 563 | ++BBI; |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 564 | DeleteDeadInstruction(S, &deadPointers); |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 565 | ++NumFastStores; |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 566 | MadeChange = true; |
| 567 | |
| 568 | continue; |
| 569 | |
| 570 | // Otherwise, it is undead |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 571 | } else if (A != AliasAnalysis::NoAlias) |
| 572 | undead.push_back(*I); |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 573 | } |
| 574 | |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 575 | for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end(); |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 576 | I != E; ++I) |
Chris Lattner | 77d79fa | 2010-11-30 19:28:23 +0000 | [diff] [blame^] | 577 | deadPointers.erase(*I); |
Owen Anderson | 32c4a05 | 2007-07-12 21:41:30 +0000 | [diff] [blame] | 578 | |
| 579 | return MadeChange; |
| 580 | } |
| 581 | |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 582 | /// DeleteDeadInstruction - Delete this instruction. Before we do, go through |
| 583 | /// and zero out all the operands of this instruction. If any of them become |
| 584 | /// dead, delete them and the computation tree that feeds them. |
| 585 | /// |
| 586 | /// If ValueSet is non-null, remove any deleted instructions from it as well. |
| 587 | /// |
| 588 | void DSE::DeleteDeadInstruction(Instruction *I, |
| 589 | SmallPtrSet<Value*, 64> *ValueSet) { |
| 590 | SmallVector<Instruction*, 32> NowDeadInsts; |
| 591 | |
| 592 | NowDeadInsts.push_back(I); |
| 593 | --NumFastOther; |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 594 | |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 595 | // Before we touch this instruction, remove it from memdep! |
| 596 | MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>(); |
Dan Gohman | 2894387 | 2010-01-05 16:27:25 +0000 | [diff] [blame] | 597 | do { |
| 598 | Instruction *DeadInst = NowDeadInsts.pop_back_val(); |
Owen Anderson | bf971aa | 2007-07-11 19:03:09 +0000 | [diff] [blame] | 599 | |
Chris Lattner | 1adb675 | 2008-11-28 00:27:14 +0000 | [diff] [blame] | 600 | ++NumFastOther; |
| 601 | |
| 602 | // This instruction is dead, zap it, in stages. Start by removing it from |
| 603 | // MemDep, which needs to know the operands and needs it to be in the |
| 604 | // function. |
| 605 | MDA.removeInstruction(DeadInst); |
| 606 | |
| 607 | for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { |
| 608 | Value *Op = DeadInst->getOperand(op); |
| 609 | DeadInst->setOperand(op, 0); |
| 610 | |
| 611 | // If this operand just became dead, add it to the NowDeadInsts list. |
| 612 | if (!Op->use_empty()) continue; |
| 613 | |
| 614 | if (Instruction *OpI = dyn_cast<Instruction>(Op)) |
| 615 | if (isInstructionTriviallyDead(OpI)) |
| 616 | NowDeadInsts.push_back(OpI); |
| 617 | } |
| 618 | |
| 619 | DeadInst->eraseFromParent(); |
| 620 | |
| 621 | if (ValueSet) ValueSet->erase(DeadInst); |
Dan Gohman | 2894387 | 2010-01-05 16:27:25 +0000 | [diff] [blame] | 622 | } while (!NowDeadInsts.empty()); |
Owen Anderson | 5e72db3 | 2007-07-11 00:46:18 +0000 | [diff] [blame] | 623 | } |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 624 | |
Chris Lattner | 77d79fa | 2010-11-30 19:28:23 +0000 | [diff] [blame^] | 625 | uint64_t DSE::getPointerSize(Value *V, AliasAnalysis &AA) const { |
| 626 | const TargetData *TD = AA.getTargetData(); |
| 627 | if (TD == 0) |
| 628 | return AliasAnalysis::UnknownSize; |
| 629 | |
| 630 | if (AllocaInst *A = dyn_cast<AllocaInst>(V)) { |
| 631 | // Get size information for the alloca |
| 632 | if (ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize())) |
| 633 | return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType()); |
| 634 | return AliasAnalysis::UnknownSize; |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 635 | } |
Chris Lattner | 77d79fa | 2010-11-30 19:28:23 +0000 | [diff] [blame^] | 636 | |
| 637 | assert(isa<Argument>(V) && "Expected AllocaInst or Argument!"); |
| 638 | const PointerType *PT = cast<PointerType>(V->getType()); |
| 639 | return TD->getTypeAllocSize(PT->getElementType()); |
Nick Lewycky | 475d3d1 | 2010-01-03 04:39:07 +0000 | [diff] [blame] | 640 | } |