DeadStoreElimination.cpp revision a9e2f3d0ab721d6a46dc3a6962d834b3e1c51494 
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"
26using namespace llvm;
27
28namespace {
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
57Pass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
58
59bool 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
128void 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}
150