blob: 50875bee8de5fea769b6d94e86d402003f5fbd31 [file] [log] [blame]
Owen Andersone3590582007-08-02 18:11:11 +00001//===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===//
Owen Anderson5e72db32007-07-11 00:46:18 +00002//
3// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Owen Anderson5e72db32007-07-11 00:46:18 +00007//
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 Anderson10e52ed2007-08-01 06:36:51 +000018#define DEBUG_TYPE "dse"
Owen Anderson5e72db32007-07-11 00:46:18 +000019#include "llvm/Transforms/Scalar.h"
Owen Anderson32c4a052007-07-12 21:41:30 +000020#include "llvm/Constants.h"
Owen Anderson5e72db32007-07-11 00:46:18 +000021#include "llvm/Function.h"
22#include "llvm/Instructions.h"
Owen Anderson48d37802008-01-29 06:18:36 +000023#include "llvm/IntrinsicInst.h"
Owen Anderson5e72db32007-07-11 00:46:18 +000024#include "llvm/Pass.h"
Owen Anderson5e72db32007-07-11 00:46:18 +000025#include "llvm/ADT/SmallPtrSet.h"
26#include "llvm/ADT/Statistic.h"
Owen Andersonaa071722007-07-11 23:19:17 +000027#include "llvm/Analysis/AliasAnalysis.h"
Owen Anderson3f338972008-07-28 16:14:26 +000028#include "llvm/Analysis/Dominators.h"
Victor Hernandezf390e042009-10-27 20:05:49 +000029#include "llvm/Analysis/MemoryBuiltins.h"
Owen Anderson5e72db32007-07-11 00:46:18 +000030#include "llvm/Analysis/MemoryDependenceAnalysis.h"
Owen Andersonaa071722007-07-11 23:19:17 +000031#include "llvm/Target/TargetData.h"
Owen Anderson5e72db32007-07-11 00:46:18 +000032#include "llvm/Transforms/Utils/Local.h"
Owen Anderson5e72db32007-07-11 00:46:18 +000033using namespace llvm;
34
35STATISTIC(NumFastStores, "Number of stores deleted");
36STATISTIC(NumFastOther , "Number of other instrs removed");
37
38namespace {
Chris Lattner2dd09db2009-09-02 06:11:42 +000039 struct DSE : public FunctionPass {
Owen Anderson5e72db32007-07-11 00:46:18 +000040 static char ID; // Pass identification, replacement for typeid
Owen Anderson6c18d1a2010-10-19 17:21:58 +000041 DSE() : FunctionPass(ID) {
42 initializeDSEPass(*PassRegistry::getPassRegistry());
43 }
Owen Anderson5e72db32007-07-11 00:46:18 +000044
45 virtual bool runOnFunction(Function &F) {
46 bool Changed = false;
Chris Lattnerc053cbb2010-02-11 05:11:54 +000047
48 DominatorTree &DT = getAnalysis<DominatorTree>();
49
Owen Anderson5e72db32007-07-11 00:46:18 +000050 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
Chris Lattnerc053cbb2010-02-11 05:11:54 +000051 // 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 Anderson5e72db32007-07-11 00:46:18 +000055 return Changed;
56 }
Chris Lattnerde04e112008-11-29 01:43:36 +000057
Owen Anderson5e72db32007-07-11 00:46:18 +000058 bool runOnBasicBlock(BasicBlock &BB);
Chris Lattner9d179d92010-11-30 01:28:33 +000059 bool HandleFree(CallInst *F);
Chris Lattner1adb6752008-11-28 00:27:14 +000060 bool handleEndBlock(BasicBlock &BB);
Dan Gohmanf372cf82010-10-19 22:54:46 +000061 bool RemoveUndeadPointers(Value *Ptr, uint64_t killPointerSize,
Nick Lewycky475d3d12010-01-03 04:39:07 +000062 BasicBlock::iterator &BBI,
63 SmallPtrSet<Value*, 64> &deadPointers);
Chris Lattner1adb6752008-11-28 00:27:14 +000064 void DeleteDeadInstruction(Instruction *I,
65 SmallPtrSet<Value*, 64> *deadPointers = 0);
66
Owen Anderson5e72db32007-07-11 00:46:18 +000067
68 // getAnalysisUsage - We require post dominance frontiers (aka Control
69 // Dependence Graph)
70 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
71 AU.setPreservesCFG();
Owen Anderson3f338972008-07-28 16:14:26 +000072 AU.addRequired<DominatorTree>();
Owen Andersonaa071722007-07-11 23:19:17 +000073 AU.addRequired<AliasAnalysis>();
Owen Anderson5e72db32007-07-11 00:46:18 +000074 AU.addRequired<MemoryDependenceAnalysis>();
Owen Anderson3f338972008-07-28 16:14:26 +000075 AU.addPreserved<DominatorTree>();
Owen Anderson5e72db32007-07-11 00:46:18 +000076 AU.addPreserved<MemoryDependenceAnalysis>();
77 }
Nick Lewycky475d3d12010-01-03 04:39:07 +000078
Chris Lattner77d79fa2010-11-30 19:28:23 +000079 uint64_t getPointerSize(Value *V, AliasAnalysis &AA) const;
Owen Anderson5e72db32007-07-11 00:46:18 +000080 };
Owen Anderson5e72db32007-07-11 00:46:18 +000081}
82
Dan Gohmand78c4002008-05-13 00:00:25 +000083char DSE::ID = 0;
Owen Anderson8ac477f2010-10-12 19:48:12 +000084INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false)
85INITIALIZE_PASS_DEPENDENCY(DominatorTree)
86INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
87INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
88INITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false)
Dan Gohmand78c4002008-05-13 00:00:25 +000089
Owen Anderson10e52ed2007-08-01 06:36:51 +000090FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
Owen Anderson5e72db32007-07-11 00:46:18 +000091
Chris Lattner2227a8a2010-11-30 01:37:52 +000092/// hasMemoryWrite - Does this instruction write some memory? This only returns
93/// true for things that we can analyze with other helpers below.
94static bool hasMemoryWrite(Instruction *I) {
Nick Lewycky90271472009-11-10 06:46:40 +000095 if (isa<StoreInst>(I))
96 return true;
97 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
98 switch (II->getIntrinsicID()) {
Chris Lattner2764b4d2009-12-02 06:35:55 +000099 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 Lewycky90271472009-11-10 06:46:40 +0000107 }
108 }
109 return false;
110}
111
Chris Lattner58b779e2010-11-30 07:23:21 +0000112/// getLocForWrite - Return a Location stored to by the specified instruction.
113static AliasAnalysis::Location
114getLocForWrite(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 Lattner3590ef82010-11-30 05:30:45 +0000150/// isRemovable - If the value of this instruction and the memory it writes to
151/// is unused, may we delete this instruction?
152static bool isRemovable(Instruction *I) {
Chris Lattnerb63ba732010-11-30 19:12:10 +0000153 // Don't remove volatile stores.
Nick Lewycky90271472009-11-10 06:46:40 +0000154 if (StoreInst *SI = dyn_cast<StoreInst>(I))
155 return !SI->isVolatile();
Chris Lattnerb63ba732010-11-30 19:12:10 +0000156
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 Lewycky90271472009-11-10 06:46:40 +0000174}
175
Chris Lattner9d179d92010-11-30 01:28:33 +0000176/// getPointerOperand - Return the pointer that is being written to.
Nick Lewycky90271472009-11-10 06:46:40 +0000177static Value *getPointerOperand(Instruction *I) {
Chris Lattner2227a8a2010-11-30 01:37:52 +0000178 assert(hasMemoryWrite(I));
Nick Lewycky90271472009-11-10 06:46:40 +0000179 if (StoreInst *SI = dyn_cast<StoreInst>(I))
180 return SI->getPointerOperand();
181 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
Gabor Greif91f95892010-06-24 12:03:56 +0000182 return MI->getArgOperand(0);
183
184 IntrinsicInst *II = cast<IntrinsicInst>(I);
185 switch (II->getIntrinsicID()) {
Chris Lattner2764b4d2009-12-02 06:35:55 +0000186 default: assert(false && "Unexpected intrinsic!");
187 case Intrinsic::init_trampoline:
Gabor Greif91f95892010-06-24 12:03:56 +0000188 return II->getArgOperand(0);
Eric Christopher7258dcd2010-04-16 23:37:20 +0000189 case Intrinsic::lifetime_end:
Gabor Greif91f95892010-06-24 12:03:56 +0000190 return II->getArgOperand(1);
Duncan Sands1925d3a2009-11-10 13:49:50 +0000191 }
Nick Lewycky90271472009-11-10 06:46:40 +0000192}
193
Chris Lattner58b779e2010-11-30 07:23:21 +0000194/// isCompleteOverwrite - Return true if a store to the 'Later' location
195/// completely overwrites a store to the 'Earlier' location.
196static bool isCompleteOverwrite(const AliasAnalysis::Location &Later,
197 const AliasAnalysis::Location &Earlier,
Chris Lattner77d79fa2010-11-30 19:28:23 +0000198 AliasAnalysis &AA) {
Chris Lattner58b779e2010-11-30 07:23:21 +0000199 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 Lewycky90271472009-11-10 06:46:40 +0000205
Chris Lattner77d79fa2010-11-30 19:28:23 +0000206 // 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 Lattner58b779e2010-11-30 07:23:21 +0000216
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 Lewycky90271472009-11-10 06:46:40 +0000222}
223
Owen Anderson10e52ed2007-08-01 06:36:51 +0000224bool DSE::runOnBasicBlock(BasicBlock &BB) {
Nick Lewycky475d3d12010-01-03 04:39:07 +0000225 MemoryDependenceAnalysis &MD = getAnalysis<MemoryDependenceAnalysis>();
Chris Lattner3590ef82010-11-30 05:30:45 +0000226 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
Owen Anderson2ed651a2007-11-01 05:29:16 +0000227
Owen Anderson5e72db32007-07-11 00:46:18 +0000228 bool MadeChange = false;
229
Chris Lattner49162672009-09-02 06:31:02 +0000230 // Do a top-down walk on the BB.
Chris Lattnerf2a8ba42008-11-28 21:29:52 +0000231 for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
232 Instruction *Inst = BBI++;
233
Chris Lattner9d179d92010-11-30 01:28:33 +0000234 // Handle 'free' calls specially.
235 if (CallInst *F = isFreeCall(Inst)) {
236 MadeChange |= HandleFree(F);
237 continue;
238 }
239
Chris Lattner2227a8a2010-11-30 01:37:52 +0000240 // If we find something that writes memory, get its memory dependence.
241 if (!hasMemoryWrite(Inst))
Owen Anderson0aecf0e2007-08-08 04:52:29 +0000242 continue;
Chris Lattnerd4f10902010-11-30 00:01:19 +0000243
Chris Lattner57e91ea2008-12-06 00:53:22 +0000244 MemDepResult InstDep = MD.getDependency(Inst);
Chris Lattnerf2a8ba42008-11-28 21:29:52 +0000245
Chris Lattnerd4f10902010-11-30 00:01:19 +0000246 // Ignore non-local store liveness.
Chris Lattner57e91ea2008-12-06 00:53:22 +0000247 // FIXME: cross-block DSE would be fun. :)
Chris Lattner58b779e2010-11-30 07:23:21 +0000248 if (InstDep.isNonLocal() ||
249 // Ignore self dependence, which happens in the entry block of the
250 // function.
251 InstDep.getInst() == Inst)
252 continue;
Chris Lattner9d179d92010-11-30 01:28:33 +0000253
Chris Lattner57e91ea2008-12-06 00:53:22 +0000254 // If we're storing the same value back to a pointer that we just
255 // loaded from, then the store can be removed.
Nick Lewycky90271472009-11-10 06:46:40 +0000256 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
257 if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) {
258 if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
Chris Lattnerc3c754f2010-11-30 00:12:39 +0000259 SI->getOperand(0) == DepLoad && !SI->isVolatile()) {
Nick Lewycky90271472009-11-10 06:46:40 +0000260 // 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 Gohmand2d1ae12010-06-22 15:08:57 +0000270 ++NumFastStores;
Nick Lewycky90271472009-11-10 06:46:40 +0000271 MadeChange = true;
272 continue;
273 }
Chris Lattner0e3d6332008-12-05 21:04:20 +0000274 }
Owen Anderson5e72db32007-07-11 00:46:18 +0000275 }
Chris Lattner3590ef82010-11-30 05:30:45 +0000276
Chris Lattner58b779e2010-11-30 07:23:21 +0000277 // 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 Lattner77d79fa2010-11-30 19:28:23 +0000300 if (isRemovable(DepWrite) && isCompleteOverwrite(Loc, DepLoc, AA)) {
Chris Lattner58b779e2010-11-30 07:23:21 +0000301 // 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 Lattnerd4f10902010-11-30 00:01:19 +0000314 // 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 Lattner58b779e2010-11-30 07:23:21 +0000322 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 Lattner3590ef82010-11-30 05:30:45 +0000327
Chris Lattner58b779e2010-11-30 07:23:21 +0000328 InstDep = MD.getPointerDependencyFrom(Loc, false, DepWrite, &BB);
Owen Anderson2b2bd282009-10-28 07:05:35 +0000329 }
Owen Anderson5e72db32007-07-11 00:46:18 +0000330 }
331
Chris Lattnerf2a8ba42008-11-28 21:29:52 +0000332 // 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 Anderson32c4a052007-07-12 21:41:30 +0000334 if (BB.getTerminator()->getNumSuccessors() == 0)
Chris Lattner1adb6752008-11-28 00:27:14 +0000335 MadeChange |= handleEndBlock(BB);
Owen Anderson5e72db32007-07-11 00:46:18 +0000336
337 return MadeChange;
338}
339
Chris Lattner9d179d92010-11-30 01:28:33 +0000340/// HandleFree - Handle frees of entire structures whose dependency is a store
341/// to a field of that structure.
342bool DSE::HandleFree(CallInst *F) {
Owen Andersonaa071722007-07-11 23:19:17 +0000343 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
Dan Gohmand4b7fff2010-11-12 02:19:17 +0000344 MemoryDependenceAnalysis &MD = getAnalysis<MemoryDependenceAnalysis>();
Chris Lattner9d179d92010-11-30 01:28:33 +0000345
346 MemDepResult Dep = MD.getDependency(F);
Dan Gohmand4b7fff2010-11-12 02:19:17 +0000347 do {
Chris Lattner9d179d92010-11-30 01:28:33 +0000348 if (Dep.isNonLocal()) return false;
349
Dan Gohmand4b7fff2010-11-12 02:19:17 +0000350 Instruction *Dependency = Dep.getInst();
Chris Lattner3590ef82010-11-30 05:30:45 +0000351 if (!hasMemoryWrite(Dependency) || !isRemovable(Dependency))
Dan Gohmand4b7fff2010-11-12 02:19:17 +0000352 return false;
Owen Andersond4451de2007-07-12 18:08:51 +0000353
Dan Gohmand4b7fff2010-11-12 02:19:17 +0000354 Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject();
Duncan Sandsfe3bef02008-01-20 10:49:23 +0000355
Dan Gohmand4b7fff2010-11-12 02:19:17 +0000356 // Check for aliasing.
357 if (AA.alias(F->getArgOperand(0), 1, DepPointer, 1) !=
Chris Lattner9d179d92010-11-30 01:28:33 +0000358 AliasAnalysis::MustAlias)
Dan Gohmand4b7fff2010-11-12 02:19:17 +0000359 return false;
Owen Andersonaa071722007-07-11 23:19:17 +0000360
Dan Gohmand4b7fff2010-11-12 02:19:17 +0000361 // 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 Lattner9d179d92010-11-30 01:28:33 +0000370 Dep = MD.getDependency(F);
Dan Gohmand4b7fff2010-11-12 02:19:17 +0000371 } while (!Dep.isNonLocal());
Chris Lattner9d179d92010-11-30 01:28:33 +0000372
Chris Lattner1adb6752008-11-28 00:27:14 +0000373 return true;
Owen Andersonaa071722007-07-11 23:19:17 +0000374}
375
Owen Andersone3590582007-08-02 18:11:11 +0000376/// handleEndBlock - Remove dead stores to stack-allocated locations in the
Owen Anderson52aaabf2007-08-08 17:50:09 +0000377/// function end block. Ex:
378/// %A = alloca i32
379/// ...
380/// store i32 1, i32* %A
381/// ret void
Chris Lattner1adb6752008-11-28 00:27:14 +0000382bool DSE::handleEndBlock(BasicBlock &BB) {
Owen Anderson32c4a052007-07-12 21:41:30 +0000383 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
Owen Anderson32c4a052007-07-12 21:41:30 +0000384
385 bool MadeChange = false;
386
387 // Pointers alloca'd in this function are dead in the end block
Owen Anderson48d37802008-01-29 06:18:36 +0000388 SmallPtrSet<Value*, 64> deadPointers;
Owen Anderson32c4a052007-07-12 21:41:30 +0000389
Chris Lattner1adb6752008-11-28 00:27:14 +0000390 // Find all of the alloca'd pointers in the entry block.
Owen Anderson32c4a052007-07-12 21:41:30 +0000391 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 Lattner1adb6752008-11-28 00:27:14 +0000395
396 // Treat byval arguments the same, stores to them are dead at the end of the
397 // function.
Owen Anderson48d37802008-01-29 06:18:36 +0000398 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 Anderson32c4a052007-07-12 21:41:30 +0000402
403 // Scan the basic block backwards
404 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
405 --BBI;
406
Chris Lattner1adb6752008-11-28 00:27:14 +0000407 // If we find a store whose pointer is dead.
Chris Lattner2227a8a2010-11-30 01:37:52 +0000408 if (hasMemoryWrite(BBI)) {
Chris Lattner3590ef82010-11-30 05:30:45 +0000409 if (isRemovable(BBI)) {
Owen Anderson2b9ec7f2007-08-26 21:14:47 +0000410 // See through pointer-to-pointer bitcasts
Nick Lewycky90271472009-11-10 06:46:40 +0000411 Value *pointerOperand = getPointerOperand(BBI)->getUnderlyingObject();
Duncan Sandsd65a4da2008-10-01 15:25:41 +0000412
Owen Anderson6af19fd2008-01-25 10:10:33 +0000413 // Alloca'd pointers or byval arguments (which are functionally like
414 // alloca's) are valid candidates for removal.
Owen Anderson48d37802008-01-29 06:18:36 +0000415 if (deadPointers.count(pointerOperand)) {
Chris Lattner1adb6752008-11-28 00:27:14 +0000416 // DCE instructions only used to calculate that store.
Nick Lewycky90271472009-11-10 06:46:40 +0000417 Instruction *Dead = BBI;
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000418 ++BBI;
Nick Lewycky90271472009-11-10 06:46:40 +0000419 DeleteDeadInstruction(Dead, &deadPointers);
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000420 ++NumFastStores;
Owen Anderson2b9ec7f2007-08-26 21:14:47 +0000421 MadeChange = true;
Nick Lewycky90271472009-11-10 06:46:40 +0000422 continue;
Owen Anderson2b9ec7f2007-08-26 21:14:47 +0000423 }
Owen Anderson32c4a052007-07-12 21:41:30 +0000424 }
Owen Anderson52aaabf2007-08-08 17:50:09 +0000425
Nick Lewycky90271472009-11-10 06:46:40 +0000426 // 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 Anderson48d37802008-01-29 06:18:36 +0000429 continue;
Owen Anderson52aaabf2007-08-08 17:50:09 +0000430 }
431
Nick Lewycky475d3d12010-01-03 04:39:07 +0000432 Value *killPointer = 0;
Dan Gohmanf372cf82010-10-19 22:54:46 +0000433 uint64_t killPointerSize = AliasAnalysis::UnknownSize;
Owen Anderson32c4a052007-07-12 21:41:30 +0000434
435 // If we encounter a use of the pointer, it is no longer considered dead
Chris Lattner1adb6752008-11-28 00:27:14 +0000436 if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
Nate Begeman53c5c622008-05-13 01:48:26 +0000437 // 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 Gohman8cb19d92008-04-28 19:51:27 +0000439 if (L->use_empty() && !L->isVolatile()) {
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000440 ++BBI;
Chris Lattner1adb6752008-11-28 00:27:14 +0000441 DeleteDeadInstruction(L, &deadPointers);
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000442 ++NumFastOther;
Owen Anderson4e4b1162008-01-30 01:24:47 +0000443 MadeChange = true;
Owen Anderson4e4b1162008-01-30 01:24:47 +0000444 continue;
445 }
446
Owen Anderson32c4a052007-07-12 21:41:30 +0000447 killPointer = L->getPointerOperand();
Nick Lewycky475d3d12010-01-03 04:39:07 +0000448 } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
Owen Anderson32c4a052007-07-12 21:41:30 +0000449 killPointer = V->getOperand(0);
Nick Lewycky90271472009-11-10 06:46:40 +0000450 } else if (isa<MemTransferInst>(BBI) &&
451 isa<ConstantInt>(cast<MemTransferInst>(BBI)->getLength())) {
452 killPointer = cast<MemTransferInst>(BBI)->getSource();
Owen Andersona82c9932008-02-04 04:53:00 +0000453 killPointerSize = cast<ConstantInt>(
Nick Lewycky90271472009-11-10 06:46:40 +0000454 cast<MemTransferInst>(BBI)->getLength())->getZExtValue();
Nick Lewycky475d3d12010-01-03 04:39:07 +0000455 } else if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) {
Owen Anderson32c4a052007-07-12 21:41:30 +0000456 deadPointers.erase(A);
Owen Anderson4e4b1162008-01-30 01:24:47 +0000457
458 // Dead alloca's can be DCE'd when we reach them
Nick Lewycky6b016702008-01-30 08:01:28 +0000459 if (A->use_empty()) {
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000460 ++BBI;
Chris Lattner1adb6752008-11-28 00:27:14 +0000461 DeleteDeadInstruction(A, &deadPointers);
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000462 ++NumFastOther;
Owen Anderson4e4b1162008-01-30 01:24:47 +0000463 MadeChange = true;
Owen Anderson4e4b1162008-01-30 01:24:47 +0000464 }
465
Owen Anderson32c4a052007-07-12 21:41:30 +0000466 continue;
Gabor Greif0a970692010-07-28 14:28:18 +0000467 } else if (CallSite CS = cast<Value>(BBI)) {
Owen Anderson50df9682007-08-08 17:58:56 +0000468 // If this call does not access memory, it can't
469 // be undeadifying any of our pointers.
Duncan Sands68b6f502007-12-01 07:51:45 +0000470 if (AA.doesNotAccessMemory(CS))
Owen Anderson50df9682007-08-08 17:58:56 +0000471 continue;
472
Owen Andersonddf4aee2007-08-08 18:38:28 +0000473 unsigned modRef = 0;
474 unsigned other = 0;
475
Owen Anderson32c4a052007-07-12 21:41:30 +0000476 // Remove any pointers made undead by the call from the dead set
Owen Anderson48d37802008-01-29 06:18:36 +0000477 std::vector<Value*> dead;
478 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(),
Owen Anderson32c4a052007-07-12 21:41:30 +0000479 E = deadPointers.end(); I != E; ++I) {
Owen Andersonddf4aee2007-08-08 18:38:28 +0000480 // 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 Lewycky475d3d12010-01-03 04:39:07 +0000488
Owen Anderson32c4a052007-07-12 21:41:30 +0000489 // See if the call site touches it
Chris Lattner77d79fa2010-11-30 19:28:23 +0000490 AliasAnalysis::ModRefResult A =
491 AA.getModRefInfo(CS, *I, getPointerSize(*I, AA));
Owen Andersonddf4aee2007-08-08 18:38:28 +0000492
493 if (A == AliasAnalysis::ModRef)
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000494 ++modRef;
Owen Andersonddf4aee2007-08-08 18:38:28 +0000495 else
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000496 ++other;
Owen Andersonddf4aee2007-08-08 18:38:28 +0000497
Owen Anderson9c9ef212007-07-13 18:26:26 +0000498 if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref)
Owen Anderson32c4a052007-07-12 21:41:30 +0000499 dead.push_back(*I);
500 }
501
Owen Anderson48d37802008-01-29 06:18:36 +0000502 for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end();
Owen Anderson32c4a052007-07-12 21:41:30 +0000503 I != E; ++I)
Owen Anderson48d37802008-01-29 06:18:36 +0000504 deadPointers.erase(*I);
Owen Anderson32c4a052007-07-12 21:41:30 +0000505
506 continue;
Chris Lattner1adb6752008-11-28 00:27:14 +0000507 } else if (isInstructionTriviallyDead(BBI)) {
Owen Anderson4e4b1162008-01-30 01:24:47 +0000508 // For any non-memory-affecting non-terminators, DCE them as we reach them
Chris Lattner1adb6752008-11-28 00:27:14 +0000509 Instruction *Inst = BBI;
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000510 ++BBI;
Chris Lattner1adb6752008-11-28 00:27:14 +0000511 DeleteDeadInstruction(Inst, &deadPointers);
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000512 ++NumFastOther;
Chris Lattner1adb6752008-11-28 00:27:14 +0000513 MadeChange = true;
514 continue;
Owen Anderson32c4a052007-07-12 21:41:30 +0000515 }
516
517 if (!killPointer)
518 continue;
Duncan Sandsd65a4da2008-10-01 15:25:41 +0000519
520 killPointer = killPointer->getUnderlyingObject();
521
Owen Anderson32c4a052007-07-12 21:41:30 +0000522 // Deal with undead pointers
Owen Andersona82c9932008-02-04 04:53:00 +0000523 MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI,
Chris Lattner1adb6752008-11-28 00:27:14 +0000524 deadPointers);
Owen Anderson32c4a052007-07-12 21:41:30 +0000525 }
526
527 return MadeChange;
528}
529
Owen Andersonddf4aee2007-08-08 18:38:28 +0000530/// RemoveUndeadPointers - check for uses of a pointer that make it
531/// undead when scanning for dead stores to alloca's.
Dan Gohmanf372cf82010-10-19 22:54:46 +0000532bool DSE::RemoveUndeadPointers(Value *killPointer, uint64_t killPointerSize,
Chris Lattner1adb6752008-11-28 00:27:14 +0000533 BasicBlock::iterator &BBI,
Nick Lewycky475d3d12010-01-03 04:39:07 +0000534 SmallPtrSet<Value*, 64> &deadPointers) {
Owen Anderson32c4a052007-07-12 21:41:30 +0000535 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
Nick Lewycky475d3d12010-01-03 04:39:07 +0000536
Owen Andersonddf4aee2007-08-08 18:38:28 +0000537 // If the kill pointer can be easily reduced to an alloca,
Chris Lattner1adb6752008-11-28 00:27:14 +0000538 // don't bother doing extraneous AA queries.
Owen Anderson48d37802008-01-29 06:18:36 +0000539 if (deadPointers.count(killPointer)) {
540 deadPointers.erase(killPointer);
Owen Andersonddf4aee2007-08-08 18:38:28 +0000541 return false;
542 }
543
Chris Lattner1adb6752008-11-28 00:27:14 +0000544 // A global can't be in the dead pointer set.
545 if (isa<GlobalValue>(killPointer))
546 return false;
547
Owen Anderson32c4a052007-07-12 21:41:30 +0000548 bool MadeChange = false;
549
Chris Lattner1adb6752008-11-28 00:27:14 +0000550 SmallVector<Value*, 16> undead;
Nick Lewycky475d3d12010-01-03 04:39:07 +0000551
Owen Anderson48d37802008-01-29 06:18:36 +0000552 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(),
Nick Lewycky475d3d12010-01-03 04:39:07 +0000553 E = deadPointers.end(); I != E; ++I) {
Owen Anderson32c4a052007-07-12 21:41:30 +0000554 // See if this pointer could alias it
Chris Lattner77d79fa2010-11-30 19:28:23 +0000555 AliasAnalysis::AliasResult A = AA.alias(*I, getPointerSize(*I, AA),
Owen Andersona82c9932008-02-04 04:53:00 +0000556 killPointer, killPointerSize);
Owen Anderson32c4a052007-07-12 21:41:30 +0000557
558 // If it must-alias and a store, we can delete it
559 if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) {
Nick Lewycky475d3d12010-01-03 04:39:07 +0000560 StoreInst *S = cast<StoreInst>(BBI);
Owen Anderson32c4a052007-07-12 21:41:30 +0000561
562 // Remove it!
Nick Lewycky475d3d12010-01-03 04:39:07 +0000563 ++BBI;
Chris Lattner1adb6752008-11-28 00:27:14 +0000564 DeleteDeadInstruction(S, &deadPointers);
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000565 ++NumFastStores;
Owen Anderson32c4a052007-07-12 21:41:30 +0000566 MadeChange = true;
567
568 continue;
569
570 // Otherwise, it is undead
Chris Lattner1adb6752008-11-28 00:27:14 +0000571 } else if (A != AliasAnalysis::NoAlias)
572 undead.push_back(*I);
Owen Anderson32c4a052007-07-12 21:41:30 +0000573 }
574
Chris Lattner1adb6752008-11-28 00:27:14 +0000575 for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end();
Owen Anderson32c4a052007-07-12 21:41:30 +0000576 I != E; ++I)
Chris Lattner77d79fa2010-11-30 19:28:23 +0000577 deadPointers.erase(*I);
Owen Anderson32c4a052007-07-12 21:41:30 +0000578
579 return MadeChange;
580}
581
Chris Lattner1adb6752008-11-28 00:27:14 +0000582/// 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///
588void DSE::DeleteDeadInstruction(Instruction *I,
589 SmallPtrSet<Value*, 64> *ValueSet) {
590 SmallVector<Instruction*, 32> NowDeadInsts;
591
592 NowDeadInsts.push_back(I);
593 --NumFastOther;
Owen Anderson5e72db32007-07-11 00:46:18 +0000594
Chris Lattner1adb6752008-11-28 00:27:14 +0000595 // Before we touch this instruction, remove it from memdep!
596 MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>();
Dan Gohman28943872010-01-05 16:27:25 +0000597 do {
598 Instruction *DeadInst = NowDeadInsts.pop_back_val();
Owen Andersonbf971aa2007-07-11 19:03:09 +0000599
Chris Lattner1adb6752008-11-28 00:27:14 +0000600 ++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 Gohman28943872010-01-05 16:27:25 +0000622 } while (!NowDeadInsts.empty());
Owen Anderson5e72db32007-07-11 00:46:18 +0000623}
Nick Lewycky475d3d12010-01-03 04:39:07 +0000624
Chris Lattner77d79fa2010-11-30 19:28:23 +0000625uint64_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 Lewycky475d3d12010-01-03 04:39:07 +0000635 }
Chris Lattner77d79fa2010-11-30 19:28:23 +0000636
637 assert(isa<Argument>(V) && "Expected AllocaInst or Argument!");
638 const PointerType *PT = cast<PointerType>(V->getType());
639 return TD->getTypeAllocSize(PT->getElementType());
Nick Lewycky475d3d12010-01-03 04:39:07 +0000640}