DeadStoreElimination.cpp revision 0fb56afab16a224dcae97528be1e386d0f3a0c64
1//===- DeadStoreElimination.cpp - Dead Store Elimination ------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source License. See LICENSE.TXT for details. 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 18#include "llvm/Transforms/Scalar.h" 19#include "llvm/Function.h" 20#include "llvm/Instructions.h" 21#include "llvm/Analysis/AliasAnalysis.h" 22#include "llvm/Analysis/AliasSetTracker.h" 23#include "llvm/Target/TargetData.h" 24#include "llvm/Transforms/Utils/Local.h" 25#include "Support/Statistic.h" 26using namespace llvm; 27 28namespace { 29 Statistic<> NumStores("dse", "Number of stores deleted"); 30 Statistic<> NumOther ("dse", "Number of other instrs removed"); 31 32 struct DSE : public FunctionPass { 33 34 virtual bool runOnFunction(Function &F) { 35 bool Changed = false; 36 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 37 Changed |= runOnBasicBlock(*I); 38 return Changed; 39 } 40 41 bool runOnBasicBlock(BasicBlock &BB); 42 43 void DeleteDeadValueChains(Value *V, AliasSetTracker &AST); 44 45 // getAnalysisUsage - We require post dominance frontiers (aka Control 46 // Dependence Graph) 47 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 48 AU.addRequired<TargetData>(); 49 AU.addRequired<AliasAnalysis>(); 50 AU.addPreserved<AliasAnalysis>(); 51 } 52 }; 53 RegisterOpt<DSE> X("dse", "Dead Store Elimination"); 54} 55 56Pass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 57 58bool DSE::runOnBasicBlock(BasicBlock &BB) { 59 TargetData &TD = getAnalysis<TargetData>(); 60 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 61 AliasSetTracker KillLocs(AA); 62 63 // If this block ends in a return, unwind, and eventually tailcall/barrier, 64 // then all allocas are dead at its end. 65 if (BB.getTerminator()->getNumSuccessors() == 0) { 66 67 } 68 69 bool MadeChange = false; 70 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ) { 71 Instruction *I = --BBI; // Keep moving iterator backwards 72 73#if 0 74 // AST doesn't support malloc/free/alloca??? 75 if (isa<FreeInst>(I)) { 76 // Free instructions make any stores to the free'd location dead. 77 KillLocs.insert(I); 78 } 79#endif 80 81 if (!isa<StoreInst>(I) || cast<StoreInst>(I)->isVolatile()) { 82 // If this is a non-store instruction, it makes everything referenced no 83 // longer killed. Remove anything aliased from the alias set tracker. 84 KillLocs.remove(I); 85 continue; 86 } 87 88 // If this is a non-volatile store instruction, and if it is already in 89 // the stored location is already in the tracker, then this is a dead 90 // store. We can just delete it here, but while we're at it, we also 91 // delete any trivially dead expression chains. 92 unsigned ValSize = TD.getTypeSize(I->getOperand(0)->getType()); 93 Value *Ptr = I->getOperand(1); 94 if (AliasSet *AS = KillLocs.getAliasSetForPointerIfExists(Ptr, ValSize)) 95 for (AliasSet::iterator ASI = AS->begin(), E = AS->end(); ASI != E; ++ASI) 96 if (AA.alias(ASI.getPointer(), ASI.getSize(), Ptr, ValSize) 97 == AliasAnalysis::MustAlias) { 98 // If we found a must alias in the killed set, then this store really 99 // is dead. Delete it now. 100 ++BBI; // Don't invalidate iterator. 101 Value *Val = I->getOperand(0); 102 BB.getInstList().erase(I); // Nuke the store! 103 ++NumStores; 104 DeleteDeadValueChains(Val, KillLocs); // Delete any now-dead instrs 105 DeleteDeadValueChains(Ptr, KillLocs); // Delete any now-dead instrs 106 MadeChange = true; 107 goto BigContinue; 108 } 109 110 // Otherwise, this is a non-dead store just add it to the set of dead 111 // locations. 112 KillLocs.add(cast<StoreInst>(I)); 113 BigContinue:; 114 } 115 return MadeChange; 116} 117 118void DSE::DeleteDeadValueChains(Value *V, AliasSetTracker &AST) { 119 // Value must be dead. 120 if (!V->use_empty()) return; 121 122 if (Instruction *I = dyn_cast<Instruction>(V)) 123 if (isInstructionTriviallyDead(I)) { 124 AST.deleteValue(I); 125 getAnalysis<AliasAnalysis>().deleteValue(I); 126 127 // See if this made any operands dead. We do it this way in case the 128 // instruction uses the same operand twice. We don't want to delete a 129 // value then reference it. 130 while (unsigned NumOps = I->getNumOperands()) { 131 Value *Op = I->getOperand(NumOps-1); 132 I->op_erase(I->op_end()-1); // Drop from the operand list. 133 DeleteDeadValueChains(Op, AST); // Attempt to nuke it. 134 } 135 136 I->getParent()->getInstList().erase(I); 137 ++NumOther; 138 } 139} 140