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