1 //===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a trivial dead store elimination that only considers
11 // basic-block local redundant stores.
13 // FIXME: This should eventually be extended to be a post-dominator tree
14 // traversal. Doing so would be pretty trivial.
16 //===----------------------------------------------------------------------===//
18 #define DEBUG_TYPE "dse"
19 #include "llvm/Transforms/Scalar.h"
20 #include "llvm/Constants.h"
21 #include "llvm/Function.h"
22 #include "llvm/Instructions.h"
23 #include "llvm/IntrinsicInst.h"
24 #include "llvm/Pass.h"
25 #include "llvm/ADT/SetVector.h"
26 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/ADT/Statistic.h"
28 #include "llvm/Analysis/AliasAnalysis.h"
29 #include "llvm/Analysis/Dominators.h"
30 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
31 #include "llvm/Target/TargetData.h"
32 #include "llvm/Transforms/Utils/Local.h"
33 #include "llvm/Support/Compiler.h"
36 STATISTIC(NumFastStores, "Number of stores deleted");
37 STATISTIC(NumFastOther , "Number of other instrs removed");
40 struct VISIBILITY_HIDDEN DSE : public FunctionPass {
41 static char ID; // Pass identification, replacement for typeid
42 DSE() : FunctionPass((intptr_t)&ID) {}
44 virtual bool runOnFunction(Function &F) {
46 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
47 Changed |= runOnBasicBlock(*I);
51 bool runOnBasicBlock(BasicBlock &BB);
52 bool handleFreeWithNonTrivialDependency(FreeInst* F,
53 Instruction* dependency,
54 SetVector<Instruction*>& possiblyDead);
55 bool handleEndBlock(BasicBlock& BB, SetVector<Instruction*>& possiblyDead);
56 bool RemoveUndeadPointers(Value* pointer, uint64_t killPointerSize,
57 BasicBlock::iterator& BBI,
58 SmallPtrSet<Value*, 64>& deadPointers,
59 SetVector<Instruction*>& possiblyDead);
60 void DeleteDeadInstructionChains(Instruction *I,
61 SetVector<Instruction*> &DeadInsts);
63 /// Find the base pointer that a pointer came from
64 /// Because this is used to find pointers that originate
65 /// from allocas, it is safe to ignore GEP indices, since
66 /// either the store will be in the alloca, and thus dead,
67 /// or beyond the end of the alloca, and thus undefined.
68 void TranslatePointerBitCasts(Value*& v, bool zeroGepsOnly = false) {
69 assert(isa<PointerType>(v->getType()) &&
70 "Translating a non-pointer type?");
72 if (BitCastInst* C = dyn_cast<BitCastInst>(v))
74 else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(v))
75 if (!zeroGepsOnly || G->hasAllZeroIndices()) {
85 // getAnalysisUsage - We require post dominance frontiers (aka Control
87 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
89 AU.addRequired<DominatorTree>();
90 AU.addRequired<TargetData>();
91 AU.addRequired<AliasAnalysis>();
92 AU.addRequired<MemoryDependenceAnalysis>();
93 AU.addPreserved<DominatorTree>();
94 AU.addPreserved<AliasAnalysis>();
95 AU.addPreserved<MemoryDependenceAnalysis>();
101 static RegisterPass<DSE> X("dse", "Dead Store Elimination");
103 FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
105 bool DSE::runOnBasicBlock(BasicBlock &BB) {
106 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
107 TargetData &TD = getAnalysis<TargetData>();
109 // Record the last-seen store to this pointer
110 DenseMap<Value*, StoreInst*> lastStore;
111 // Record instructions possibly made dead by deleting a store
112 SetVector<Instruction*> possiblyDead;
114 bool MadeChange = false;
116 // Do a top-down walk on the BB
117 for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end();
119 // If we find a store or a free...
120 if (!isa<StoreInst>(BBI) && !isa<FreeInst>(BBI))
124 if (StoreInst* S = dyn_cast<StoreInst>(BBI)) {
125 if (!S->isVolatile())
126 pointer = S->getPointerOperand();
130 pointer = cast<FreeInst>(BBI)->getPointerOperand();
132 TranslatePointerBitCasts(pointer, true);
133 StoreInst*& last = lastStore[pointer];
134 bool deletedStore = false;
136 // ... to a pointer that has been stored to before...
138 Instruction* dep = MD.getDependency(BBI);
140 // ... and no other memory dependencies are between them....
141 while (dep != MemoryDependenceAnalysis::None &&
142 dep != MemoryDependenceAnalysis::NonLocal &&
143 isa<StoreInst>(dep)) {
145 TD.getTypeStoreSize(last->getOperand(0)->getType()) >
146 TD.getTypeStoreSize(BBI->getOperand(0)->getType())) {
147 dep = MD.getDependency(BBI, dep);
152 MD.removeInstruction(last);
154 // DCE instructions only used to calculate that store
155 if (Instruction* D = dyn_cast<Instruction>(last->getOperand(0)))
156 possiblyDead.insert(D);
157 if (Instruction* D = dyn_cast<Instruction>(last->getOperand(1)))
158 possiblyDead.insert(D);
160 last->eraseFromParent();
169 // Handle frees whose dependencies are non-trivial.
170 if (FreeInst* F = dyn_cast<FreeInst>(BBI)) {
172 MadeChange |= handleFreeWithNonTrivialDependency(F,
175 // No known stores after the free
178 StoreInst* S = cast<StoreInst>(BBI);
180 // If we're storing the same value back to a pointer that we just
181 // loaded from, then the store can be removed;
182 if (LoadInst* L = dyn_cast<LoadInst>(S->getOperand(0))) {
183 Instruction* dep = MD.getDependency(S);
184 DominatorTree& DT = getAnalysis<DominatorTree>();
186 if (!S->isVolatile() && S->getParent() == L->getParent() &&
187 S->getPointerOperand() == L->getPointerOperand() &&
188 ( dep == MemoryDependenceAnalysis::None ||
189 dep == MemoryDependenceAnalysis::NonLocal ||
190 DT.dominates(dep, L))) {
191 if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0)))
192 possiblyDead.insert(D);
193 if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1)))
194 possiblyDead.insert(D);
196 // Avoid iterator invalidation.
199 MD.removeInstruction(S);
200 S->eraseFromParent();
204 // Update our most-recent-store map.
207 // Update our most-recent-store map.
212 // If this block ends in a return, unwind, unreachable, and eventually
213 // tailcall, then all allocas are dead at its end.
214 if (BB.getTerminator()->getNumSuccessors() == 0)
215 MadeChange |= handleEndBlock(BB, possiblyDead);
218 while (!possiblyDead.empty()) {
219 Instruction *I = possiblyDead.back();
220 possiblyDead.pop_back();
221 DeleteDeadInstructionChains(I, possiblyDead);
227 /// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose
228 /// dependency is a store to a field of that structure
229 bool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, Instruction* dep,
230 SetVector<Instruction*>& possiblyDead) {
231 TargetData &TD = getAnalysis<TargetData>();
232 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
233 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
235 if (dep == MemoryDependenceAnalysis::None ||
236 dep == MemoryDependenceAnalysis::NonLocal)
239 StoreInst* dependency = dyn_cast<StoreInst>(dep);
242 else if (dependency->isVolatile())
245 Value* depPointer = dependency->getPointerOperand();
246 const Type* depType = dependency->getOperand(0)->getType();
247 unsigned depPointerSize = TD.getTypeStoreSize(depType);
249 // Check for aliasing
250 AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0U,
251 depPointer, depPointerSize);
253 if (A == AliasAnalysis::MustAlias) {
255 MD.removeInstruction(dependency);
257 // DCE instructions only used to calculate that store
258 if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(0)))
259 possiblyDead.insert(D);
260 if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(1)))
261 possiblyDead.insert(D);
263 dependency->eraseFromParent();
271 /// handleEndBlock - Remove dead stores to stack-allocated locations in the
272 /// function end block. Ex:
275 /// store i32 1, i32* %A
277 bool DSE::handleEndBlock(BasicBlock& BB,
278 SetVector<Instruction*>& possiblyDead) {
279 TargetData &TD = getAnalysis<TargetData>();
280 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
281 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
283 bool MadeChange = false;
285 // Pointers alloca'd in this function are dead in the end block
286 SmallPtrSet<Value*, 64> deadPointers;
288 // Find all of the alloca'd pointers in the entry block
289 BasicBlock *Entry = BB.getParent()->begin();
290 for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I)
291 if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
292 deadPointers.insert(AI);
293 for (Function::arg_iterator AI = BB.getParent()->arg_begin(),
294 AE = BB.getParent()->arg_end(); AI != AE; ++AI)
295 if (AI->hasByValAttr())
296 deadPointers.insert(AI);
298 // Scan the basic block backwards
299 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
302 // If we find a store whose pointer is dead...
303 if (StoreInst* S = dyn_cast<StoreInst>(BBI)) {
304 if (!S->isVolatile()) {
305 Value* pointerOperand = S->getPointerOperand();
306 // See through pointer-to-pointer bitcasts
307 TranslatePointerBitCasts(pointerOperand);
309 // Alloca'd pointers or byval arguments (which are functionally like
310 // alloca's) are valid candidates for removal.
311 if (deadPointers.count(pointerOperand)) {
313 MD.removeInstruction(S);
315 // DCE instructions only used to calculate that store
316 if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0)))
317 possiblyDead.insert(D);
318 if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1)))
319 possiblyDead.insert(D);
322 MD.removeInstruction(S);
323 S->eraseFromParent();
331 // We can also remove memcpy's to local variables at the end of a function
332 } else if (MemCpyInst* M = dyn_cast<MemCpyInst>(BBI)) {
333 Value* dest = M->getDest();
334 TranslatePointerBitCasts(dest);
336 if (deadPointers.count(dest)) {
337 MD.removeInstruction(M);
339 // DCE instructions only used to calculate that memcpy
340 if (Instruction* D = dyn_cast<Instruction>(M->getRawSource()))
341 possiblyDead.insert(D);
342 if (Instruction* D = dyn_cast<Instruction>(M->getLength()))
343 possiblyDead.insert(D);
344 if (Instruction* D = dyn_cast<Instruction>(M->getRawDest()))
345 possiblyDead.insert(D);
348 M->eraseFromParent();
355 // Because a memcpy is also a load, we can't skip it if we didn't remove it
358 Value* killPointer = 0;
359 uint64_t killPointerSize = ~0UL;
361 // If we encounter a use of the pointer, it is no longer considered dead
362 if (LoadInst* L = dyn_cast<LoadInst>(BBI)) {
363 // However, if this load is unused and not volatile, we can go ahead and
364 // remove it, and not have to worry about it making our pointer undead!
365 if (L->use_empty() && !L->isVolatile()) {
366 MD.removeInstruction(L);
368 // DCE instructions only used to calculate that load
369 if (Instruction* D = dyn_cast<Instruction>(L->getPointerOperand()))
370 possiblyDead.insert(D);
373 L->eraseFromParent();
376 possiblyDead.remove(L);
381 killPointer = L->getPointerOperand();
382 } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) {
383 killPointer = V->getOperand(0);
384 } else if (isa<MemCpyInst>(BBI) &&
385 isa<ConstantInt>(cast<MemCpyInst>(BBI)->getLength())) {
386 killPointer = cast<MemCpyInst>(BBI)->getSource();
387 killPointerSize = cast<ConstantInt>(
388 cast<MemCpyInst>(BBI)->getLength())->getZExtValue();
389 } else if (AllocaInst* A = dyn_cast<AllocaInst>(BBI)) {
390 deadPointers.erase(A);
392 // Dead alloca's can be DCE'd when we reach them
393 if (A->use_empty()) {
394 MD.removeInstruction(A);
396 // DCE instructions only used to calculate that load
397 if (Instruction* D = dyn_cast<Instruction>(A->getArraySize()))
398 possiblyDead.insert(D);
401 A->eraseFromParent();
404 possiblyDead.remove(A);
408 } else if (CallSite::get(BBI).getInstruction() != 0) {
409 // If this call does not access memory, it can't
410 // be undeadifying any of our pointers.
411 CallSite CS = CallSite::get(BBI);
412 if (AA.doesNotAccessMemory(CS))
418 // Remove any pointers made undead by the call from the dead set
419 std::vector<Value*> dead;
420 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(),
421 E = deadPointers.end(); I != E; ++I) {
422 // HACK: if we detect that our AA is imprecise, it's not
423 // worth it to scan the rest of the deadPointers set. Just
424 // assume that the AA will return ModRef for everything, and
425 // go ahead and bail.
426 if (modRef >= 16 && other == 0) {
427 deadPointers.clear();
431 // Get size information for the alloca
432 unsigned pointerSize = ~0U;
433 if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) {
434 if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize()))
435 pointerSize = C->getZExtValue() * \
436 TD.getABITypeSize(A->getAllocatedType());
438 const PointerType* PT = cast<PointerType>(
439 cast<Argument>(*I)->getType());
440 pointerSize = TD.getABITypeSize(PT->getElementType());
443 // See if the call site touches it
444 AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize);
446 if (A == AliasAnalysis::ModRef)
451 if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref)
455 for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end();
457 deadPointers.erase(*I);
461 // For any non-memory-affecting non-terminators, DCE them as we reach them
462 Instruction *CI = BBI;
463 if (!CI->isTerminator() && CI->use_empty() && !isa<FreeInst>(CI)) {
465 // DCE instructions only used to calculate that load
466 for (Instruction::op_iterator OI = CI->op_begin(), OE = CI->op_end();
468 if (Instruction* D = dyn_cast<Instruction>(OI))
469 possiblyDead.insert(D);
472 CI->eraseFromParent();
475 possiblyDead.remove(CI);
484 TranslatePointerBitCasts(killPointer);
486 // Deal with undead pointers
487 MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI,
488 deadPointers, possiblyDead);
494 /// RemoveUndeadPointers - check for uses of a pointer that make it
495 /// undead when scanning for dead stores to alloca's.
496 bool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize,
497 BasicBlock::iterator& BBI,
498 SmallPtrSet<Value*, 64>& deadPointers,
499 SetVector<Instruction*>& possiblyDead) {
500 TargetData &TD = getAnalysis<TargetData>();
501 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
502 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
504 // If the kill pointer can be easily reduced to an alloca,
505 // don't bother doing extraneous AA queries
506 if (deadPointers.count(killPointer)) {
507 deadPointers.erase(killPointer);
509 } else if (isa<GlobalValue>(killPointer)) {
510 // A global can't be in the dead pointer set
514 bool MadeChange = false;
516 std::vector<Value*> undead;
518 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(),
519 E = deadPointers.end(); I != E; ++I) {
520 // Get size information for the alloca
521 unsigned pointerSize = ~0U;
522 if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) {
523 if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize()))
524 pointerSize = C->getZExtValue() * \
525 TD.getABITypeSize(A->getAllocatedType());
527 const PointerType* PT = cast<PointerType>(
528 cast<Argument>(*I)->getType());
529 pointerSize = TD.getABITypeSize(PT->getElementType());
532 // See if this pointer could alias it
533 AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize,
534 killPointer, killPointerSize);
536 // If it must-alias and a store, we can delete it
537 if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) {
538 StoreInst* S = cast<StoreInst>(BBI);
541 MD.removeInstruction(S);
543 // DCE instructions only used to calculate that store
544 if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0)))
545 possiblyDead.insert(D);
546 if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1)))
547 possiblyDead.insert(D);
550 S->eraseFromParent();
556 // Otherwise, it is undead
557 } else if (A != AliasAnalysis::NoAlias)
558 undead.push_back(*I);
561 for (std::vector<Value*>::iterator I = undead.begin(), E = undead.end();
563 deadPointers.erase(*I);
568 /// DeleteDeadInstructionChains - takes an instruction and a setvector of
569 /// dead instructions. If I is dead, it is erased, and its operands are
570 /// checked for deadness. If they are dead, they are added to the dead
572 void DSE::DeleteDeadInstructionChains(Instruction *I,
573 SetVector<Instruction*> &DeadInsts) {
574 // Instruction must be dead.
575 if (!I->use_empty() || !isInstructionTriviallyDead(I)) return;
577 // Let the memory dependence know
578 getAnalysis<MemoryDependenceAnalysis>().removeInstruction(I);
580 // See if this made any operands dead. We do it this way in case the
581 // instruction uses the same operand twice. We don't want to delete a
582 // value then reference it.
583 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
584 if (I->getOperand(i)->hasOneUse())
585 if (Instruction* Op = dyn_cast<Instruction>(I->getOperand(i)))
586 DeadInsts.insert(Op); // Attempt to nuke it later.
588 I->setOperand(i, 0); // Drop from the operand list.
591 I->eraseFromParent();