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