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