LLVM API Documentation

DeadStoreElimination.cpp

Go to the documentation of this file.
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 }