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 = (unsigned)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 vaarg instruction, it reads its operand. We don't model 00100 // it correctly, so just conservatively remove all entries. 00101 if (isa<VAArgInst>(I)) { 00102 KillLocs.clear(); 00103 continue; 00104 } 00105 00106 // If this is a non-store instruction, it makes everything referenced no 00107 // longer killed. Remove anything aliased from the alias set tracker. 00108 KillLocs.remove(I); 00109 continue; 00110 } 00111 00112 // If this is a non-volatile store instruction, and if it is already in 00113 // the stored location is already in the tracker, then this is a dead 00114 // store. We can just delete it here, but while we're at it, we also 00115 // delete any trivially dead expression chains. 00116 unsigned ValSize = (unsigned)TD.getTypeSize(I->getOperand(0)->getType()); 00117 Value *Ptr = I->getOperand(1); 00118 00119 if (AliasSet *AS = KillLocs.getAliasSetForPointerIfExists(Ptr, ValSize)) 00120 for (AliasSet::iterator ASI = AS->begin(), E = AS->end(); ASI != E; ++ASI) 00121 if (ASI.getSize() >= ValSize && // Overwriting all of this store. 00122 AA.alias(ASI.getPointer(), ASI.getSize(), Ptr, ValSize) 00123 == AliasAnalysis::MustAlias) { 00124 // If we found a must alias in the killed set, then this store really 00125 // is dead. Remember that the various operands of the store now have 00126 // fewer users. At the end we will see if we can delete any values 00127 // that are dead as part of the store becoming dead. 00128 if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(0))) 00129 PotentiallyDeadInsts.insert(Op); 00130 if (Instruction *Op = dyn_cast<Instruction>(Ptr)) 00131 PotentiallyDeadInsts.insert(Op); 00132 00133 // Delete it now. 00134 ++BBI; // Don't invalidate iterator. 00135 BB.getInstList().erase(I); // Nuke the store! 00136 ++NumStores; 00137 MadeChange = true; 00138 goto BigContinue; 00139 } 00140 00141 // Otherwise, this is a non-dead store just add it to the set of dead 00142 // locations. 00143 KillLocs.add(cast<StoreInst>(I)); 00144 BigContinue:; 00145 } 00146 00147 while (!PotentiallyDeadInsts.empty()) { 00148 Instruction *I = PotentiallyDeadInsts.back(); 00149 PotentiallyDeadInsts.pop_back(); 00150 DeleteDeadInstructionChains(I, PotentiallyDeadInsts); 00151 } 00152 return MadeChange; 00153 } 00154 00155 void DSE::DeleteDeadInstructionChains(Instruction *I, 00156 SetVector<Instruction*> &DeadInsts) { 00157 // Instruction must be dead. 00158 if (!I->use_empty() || !isInstructionTriviallyDead(I)) return; 00159 00160 // Let the alias analysis know that we have nuked a value. 00161 getAnalysis<AliasAnalysis>().deleteValue(I); 00162 00163 // See if this made any operands dead. We do it this way in case the 00164 // instruction uses the same operand twice. We don't want to delete a 00165 // value then reference it. 00166 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 00167 if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i))) 00168 DeadInsts.insert(Op); // Attempt to nuke it later. 00169 I->setOperand(i, 0); // Drop from the operand list. 00170 } 00171 00172 I->eraseFromParent(); 00173 ++NumOther; 00174 }