lib/Transforms/Scalar/DeadStoreElimination.cpp

   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/SetVector.h"
  26 #include "Support/Statistic.h"
  27 using namespace llvm;
  28
  29 namespace {
  30   Statistic<> NumStores("dse", "Number of stores deleted");
  31   Statistic<> NumOther ("dse", "Number of other instrs removed");
  32
  33   struct DSE : public FunctionPass {
  34
  35     virtual bool runOnFunction(Function &F) {
  36       bool Changed = false;
  37       for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
  38         Changed |= runOnBasicBlock(*I);
  39       return Changed;
  40     }
  41
  42     bool runOnBasicBlock(BasicBlock &BB);
  43
  44     void DeleteDeadInstructionChains(Instruction *I,
  45                                      SetVector<Instruction*> &DeadInsts);
  46
  47     // getAnalysisUsage - We require post dominance frontiers (aka Control
  48     // Dependence Graph)
  49     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  50       AU.setPreservesCFG();
  51       AU.addRequired<TargetData>();
  52       AU.addRequired<AliasAnalysis>();
  53       AU.addPreserved<AliasAnalysis>();
  54     }
  55   };
  56   RegisterOpt<DSE> X("dse", "Dead Store Elimination");
  57 }
  58
  59 Pass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
  60
  61 bool DSE::runOnBasicBlock(BasicBlock &BB) {
  62   TargetData &TD = getAnalysis<TargetData>();
  63   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
  64   AliasSetTracker KillLocs(AA);
  65
  66   // If this block ends in a return, unwind, and eventually tailcall/barrier,
  67   // then all allocas are dead at its end.
  68   if (BB.getTerminator()->getNumSuccessors() == 0) {
  69
  70   }
  71
  72   // PotentiallyDeadInsts - Deleting dead stores from the program can make other
  73   // instructions die if they were only used as operands to stores.  Keep track
  74   // of the operands to stores so that we can try deleting them at the end of
  75   // the traversal.
  76   SetVector<Instruction*> PotentiallyDeadInsts;
  77
  78   bool MadeChange = false;
  79   for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ) {
  80     Instruction *I = --BBI;   // Keep moving iterator backwards
  81
  82     // If this is a free instruction, it makes the free'd location dead!
  83     if (FreeInst *FI = dyn_cast<FreeInst>(I)) {
  84       // Free instructions make any stores to the free'd location dead.
  85       KillLocs.add(FI);
  86       continue;
  87     }
  88
  89     if (!isa<StoreInst>(I) || cast<StoreInst>(I)->isVolatile()) {
  90       // If this is a non-store instruction, it makes everything referenced no
  91       // longer killed.  Remove anything aliased from the alias set tracker.
  92       KillLocs.remove(I);
  93       continue;
  94     }
  95
  96     // If this is a non-volatile store instruction, and if it is already in
  97     // the stored location is already in the tracker, then this is a dead
  98     // store.  We can just delete it here, but while we're at it, we also
  99     // delete any trivially dead expression chains.
 100     unsigned ValSize = TD.getTypeSize(I->getOperand(0)->getType());
 101     Value *Ptr = I->getOperand(1);
 102
 103     if (AliasSet *AS = KillLocs.getAliasSetForPointerIfExists(Ptr, ValSize))
 104       for (AliasSet::iterator ASI = AS->begin(), E = AS->end(); ASI != E; ++ASI)
 105         if (AA.alias(ASI.getPointer(), ASI.getSize(), Ptr, ValSize)
 106                == AliasAnalysis::MustAlias) {
 107           // If we found a must alias in the killed set, then this store really
 108           // is dead.  Remember that the various operands of the store now have
 109           // fewer users.  At the end we will see if we can delete any values
 110           // that are dead as part of the store becoming dead.
 111           if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(0)))
 112             PotentiallyDeadInsts.insert(Op);
 113           if (Instruction *Op = dyn_cast<Instruction>(Ptr))
 114             PotentiallyDeadInsts.insert(Op);
 115
 116           // Delete it now.
 117           ++BBI;                        // Don't invalidate iterator.
 118           BB.getInstList().erase(I);    // Nuke the store!
 119           ++NumStores;
 120           MadeChange = true;
 121           goto BigContinue;
 122         }
 123
 124     // Otherwise, this is a non-dead store just add it to the set of dead
 125     // locations.
 126     KillLocs.add(cast<StoreInst>(I));
 127   BigContinue:;
 128   }
 129
 130   while (!PotentiallyDeadInsts.empty()) {
 131     Instruction *I = PotentiallyDeadInsts.back();
 132     PotentiallyDeadInsts.pop_back();
 133     DeleteDeadInstructionChains(I, PotentiallyDeadInsts);
 134   }
 135   return MadeChange;
 136 }
 137
 138 void DSE::DeleteDeadInstructionChains(Instruction *I,
 139                                       SetVector<Instruction*> &DeadInsts) {
 140   // Instruction must be dead.
 141   if (!I->use_empty() || !isInstructionTriviallyDead(I)) return;
 142
 143   // Let the alias analysis know that we have nuked a value.
 144   getAnalysis<AliasAnalysis>().deleteValue(I);
 145
 146   // See if this made any operands dead.  We do it this way in case the
 147   // instruction uses the same operand twice.  We don't want to delete a
 148   // value then reference it.
 149   while (unsigned NumOps = I->getNumOperands()) {
 150     Instruction *Op = dyn_cast<Instruction>(I->getOperand(NumOps-1));
 151     I->op_erase(I->op_end()-1);         // Drop from the operand list.
 152
 153     if (Op) DeadInsts.insert(Op);       // Attempt to nuke it later.
 154   }
 155
 156   I->getParent()->getInstList().erase(I);
 157   ++NumOther;
 158 }