LLVM API Documentation
00001 //===- DeadStoreElimination.cpp - Dead Store Elimination ------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements a trivial dead store elimination that only considers 00011 // basic-block local redundant stores. 00012 // 00013 // FIXME: This should eventually be extended to be a post-dominator tree 00014 // traversal. Doing so would be pretty trivial. 00015 // 00016 //===----------------------------------------------------------------------===// 00017 00018 #include "llvm/Transforms/Scalar.h" 00019 #include "llvm/DerivedTypes.h" 00020 #include "llvm/Function.h" 00021 #include "llvm/Instructions.h" 00022 #include "llvm/Analysis/AliasAnalysis.h" 00023 #include "llvm/Analysis/AliasSetTracker.h" 00024 #include "llvm/Target/TargetData.h" 00025 #include "llvm/Transforms/Utils/Local.h" 00026 #include "llvm/ADT/SetVector.h" 00027 #include "llvm/ADT/Statistic.h" 00028 using namespace llvm; 00029 00030 namespace { 00031 Statistic<> NumStores("dse", "Number of stores deleted"); 00032 Statistic<> NumOther ("dse", "Number of other instrs removed"); 00033 00034 struct DSE : public FunctionPass { 00035 00036 virtual bool runOnFunction(Function &F) { 00037 bool Changed = false; 00038 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00039 Changed |= runOnBasicBlock(*I); 00040 return Changed; 00041 } 00042 00043 bool runOnBasicBlock(BasicBlock &BB); 00044 00045 void DeleteDeadInstructionChains(Instruction *I, 00046 SetVector<Instruction*> &DeadInsts); 00047 00048 // getAnalysisUsage - We require post dominance frontiers (aka Control 00049 // Dependence Graph) 00050 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00051 AU.setPreservesCFG(); 00052 AU.addRequired<TargetData>(); 00053 AU.addRequired<AliasAnalysis>(); 00054 AU.addPreserved<AliasAnalysis>(); 00055 } 00056 }; 00057 RegisterOpt<DSE> X("dse", "Dead Store Elimination"); 00058 } 00059 00060 FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 00061 00062 bool DSE::runOnBasicBlock(BasicBlock &BB) { 00063 TargetData &TD = getAnalysis<TargetData>(); 00064 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 00065 AliasSetTracker KillLocs(AA); 00066 00067 // If this block ends in a return, unwind, unreachable, and eventually 00068 // tailcall, then all allocas are dead at its end. 00069 if (BB.getTerminator()->getNumSuccessors() == 0) { 00070 BasicBlock *Entry = BB.getParent()->begin(); 00071 for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 00072 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) { 00073 unsigned Size = ~0U; 00074 if (!AI->isArrayAllocation() && 00075 AI->getType()->getElementType()->isSized()) 00076 Size = TD.getTypeSize(AI->getType()->getElementType()); 00077 KillLocs.add(AI, Size); 00078 } 00079 } 00080 00081 // PotentiallyDeadInsts - Deleting dead stores from the program can make other 00082 // instructions die if they were only used as operands to stores. Keep track 00083 // of the operands to stores so that we can try deleting them at the end of 00084 // the traversal. 00085 SetVector<Instruction*> PotentiallyDeadInsts; 00086 00087 bool MadeChange = false; 00088 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ) { 00089 Instruction *I = --BBI; // Keep moving iterator backwards 00090 00091 // If this is a free instruction, it makes the free'd location dead! 00092 if (FreeInst *FI = dyn_cast<FreeInst>(I)) { 00093 // Free instructions make any stores to the free'd location dead. 00094 KillLocs.add(FI); 00095 continue; 00096 } 00097 00098 if (!isa<StoreInst>(I) || cast<StoreInst>(I)->isVolatile()) { 00099 // If this is a non-store instruction, it makes everything referenced no 00100 // longer killed. Remove anything aliased from the alias set tracker. 00101 KillLocs.remove(I); 00102 continue; 00103 } 00104 00105 // If this is a non-volatile store instruction, and if it is already in 00106 // the stored location is already in the tracker, then this is a dead 00107 // store. We can just delete it here, but while we're at it, we also 00108 // delete any trivially dead expression chains. 00109 unsigned ValSize = TD.getTypeSize(I->getOperand(0)->getType()); 00110 Value *Ptr = I->getOperand(1); 00111 00112 if (AliasSet *AS = KillLocs.getAliasSetForPointerIfExists(Ptr, ValSize)) 00113 for (AliasSet::iterator ASI = AS->begin(), E = AS->end(); ASI != E; ++ASI) 00114 if (AA.alias(ASI.getPointer(), ASI.getSize(), Ptr, ValSize) 00115 == AliasAnalysis::MustAlias) { 00116 // If we found a must alias in the killed set, then this store really 00117 // is dead. Remember that the various operands of the store now have 00118 // fewer users. At the end we will see if we can delete any values 00119 // that are dead as part of the store becoming dead. 00120 if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(0))) 00121 PotentiallyDeadInsts.insert(Op); 00122 if (Instruction *Op = dyn_cast<Instruction>(Ptr)) 00123 PotentiallyDeadInsts.insert(Op); 00124 00125 // Delete it now. 00126 ++BBI; // Don't invalidate iterator. 00127 BB.getInstList().erase(I); // Nuke the store! 00128 ++NumStores; 00129 MadeChange = true; 00130 goto BigContinue; 00131 } 00132 00133 // Otherwise, this is a non-dead store just add it to the set of dead 00134 // locations. 00135 KillLocs.add(cast<StoreInst>(I)); 00136 BigContinue:; 00137 } 00138 00139 while (!PotentiallyDeadInsts.empty()) { 00140 Instruction *I = PotentiallyDeadInsts.back(); 00141 PotentiallyDeadInsts.pop_back(); 00142 DeleteDeadInstructionChains(I, PotentiallyDeadInsts); 00143 } 00144 return MadeChange; 00145 } 00146 00147 void DSE::DeleteDeadInstructionChains(Instruction *I, 00148 SetVector<Instruction*> &DeadInsts) { 00149 // Instruction must be dead. 00150 if (!I->use_empty() || !isInstructionTriviallyDead(I)) return; 00151 00152 // Let the alias analysis know that we have nuked a value. 00153 getAnalysis<AliasAnalysis>().deleteValue(I); 00154 00155 // See if this made any operands dead. We do it this way in case the 00156 // instruction uses the same operand twice. We don't want to delete a 00157 // value then reference it. 00158 while (unsigned NumOps = I->getNumOperands()) { 00159 Instruction *Op = dyn_cast<Instruction>(I->getOperand(NumOps-1)); 00160 I->op_erase(I->op_end()-1); // Drop from the operand list. 00161 00162 if (Op) DeadInsts.insert(Op); // Attempt to nuke it later. 00163 } 00164 00165 I->getParent()->getInstList().erase(I); 00166 ++NumOther; 00167 }