DeadStoreElimination.cpp revision 551ccae044b0ff658fe629dd67edd5ffe75d10e8 
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 "llvm/ADT/SetVector.h"
26#include "llvm/ADT/Statistic.h"
27using namespace llvm;
28
29namespace {
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
59Pass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
60
61bool 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    BasicBlock *Entry = BB.getParent()->begin();
70    for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I)
71      if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
72        KillLocs.add(AI, ~0);
73  }
74
75  // PotentiallyDeadInsts - Deleting dead stores from the program can make other
76  // instructions die if they were only used as operands to stores.  Keep track
77  // of the operands to stores so that we can try deleting them at the end of
78  // the traversal.
79  SetVector<Instruction*> PotentiallyDeadInsts;
80
81  bool MadeChange = false;
82  for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ) {
83    Instruction *I = --BBI;   // Keep moving iterator backwards
84
85    // If this is a free instruction, it makes the free'd location dead!
86    if (FreeInst *FI = dyn_cast<FreeInst>(I)) {
87      // Free instructions make any stores to the free'd location dead.
88      KillLocs.add(FI);
89      continue;
90    }
91
92    if (!isa<StoreInst>(I) || cast<StoreInst>(I)->isVolatile()) {
93      // If this is a non-store instruction, it makes everything referenced no
94      // longer killed.  Remove anything aliased from the alias set tracker.
95      KillLocs.remove(I);
96      continue;
97    }
98
99    // If this is a non-volatile store instruction, and if it is already in
100    // the stored location is already in the tracker, then this is a dead
101    // store.  We can just delete it here, but while we're at it, we also
102    // delete any trivially dead expression chains.
103    unsigned ValSize = TD.getTypeSize(I->getOperand(0)->getType());
104    Value *Ptr = I->getOperand(1);
105
106    if (AliasSet *AS = KillLocs.getAliasSetForPointerIfExists(Ptr, ValSize))
107      for (AliasSet::iterator ASI = AS->begin(), E = AS->end(); ASI != E; ++ASI)
108        if (AA.alias(ASI.getPointer(), ASI.getSize(), Ptr, ValSize)
109               == AliasAnalysis::MustAlias) {
110          // If we found a must alias in the killed set, then this store really
111          // is dead.  Remember that the various operands of the store now have
112          // fewer users.  At the end we will see if we can delete any values
113          // that are dead as part of the store becoming dead.
114          if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(0)))
115            PotentiallyDeadInsts.insert(Op);
116          if (Instruction *Op = dyn_cast<Instruction>(Ptr))
117            PotentiallyDeadInsts.insert(Op);
118
119          // Delete it now.
120          ++BBI;                        // Don't invalidate iterator.
121          BB.getInstList().erase(I);    // Nuke the store!
122          ++NumStores;
123          MadeChange = true;
124          goto BigContinue;
125        }
126
127    // Otherwise, this is a non-dead store just add it to the set of dead
128    // locations.
129    KillLocs.add(cast<StoreInst>(I));
130  BigContinue:;
131  }
132
133  while (!PotentiallyDeadInsts.empty()) {
134    Instruction *I = PotentiallyDeadInsts.back();
135    PotentiallyDeadInsts.pop_back();
136    DeleteDeadInstructionChains(I, PotentiallyDeadInsts);
137  }
138  return MadeChange;
139}
140
141void DSE::DeleteDeadInstructionChains(Instruction *I,
142                                      SetVector<Instruction*> &DeadInsts) {
143  // Instruction must be dead.
144  if (!I->use_empty() || !isInstructionTriviallyDead(I)) return;
145
146  // Let the alias analysis know that we have nuked a value.
147  getAnalysis<AliasAnalysis>().deleteValue(I);
148
149  // See if this made any operands dead.  We do it this way in case the
150  // instruction uses the same operand twice.  We don't want to delete a
151  // value then reference it.
152  while (unsigned NumOps = I->getNumOperands()) {
153    Instruction *Op = dyn_cast<Instruction>(I->getOperand(NumOps-1));
154    I->op_erase(I->op_end()-1);         // Drop from the operand list.
155
156    if (Op) DeadInsts.insert(Op);       // Attempt to nuke it later.
157  }
158
159  I->getParent()->getInstList().erase(I);
160  ++NumOther;
161}
162