DeadStoreElimination.cpp revision df359c264eb717ea69ca8dbda91992d707928af0 
1//===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by Owen Anderson 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/Constants.h"
21#include "llvm/Function.h"
22#include "llvm/Instructions.h"
23#include "llvm/Pass.h"
24#include "llvm/ADT/SetVector.h"
25#include "llvm/ADT/SmallPtrSet.h"
26#include "llvm/ADT/Statistic.h"
27#include "llvm/Analysis/AliasAnalysis.h"
28#include "llvm/Analysis/MemoryDependenceAnalysis.h"
29#include "llvm/Target/TargetData.h"
30#include "llvm/Transforms/Utils/Local.h"
31#include "llvm/Support/Compiler.h"
32using namespace llvm;
33
34STATISTIC(NumFastStores, "Number of stores deleted");
35STATISTIC(NumFastOther , "Number of other instrs removed");
36
37namespace {
38  struct VISIBILITY_HIDDEN DSE : public FunctionPass {
39    static char ID; // Pass identification, replacement for typeid
40    DSE() : FunctionPass((intptr_t)&ID) {}
41
42    virtual bool runOnFunction(Function &F) {
43      bool Changed = false;
44      for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
45        Changed |= runOnBasicBlock(*I);
46      return Changed;
47    }
48
49    bool runOnBasicBlock(BasicBlock &BB);
50    bool handleFreeWithNonTrivialDependency(FreeInst* F,
51                                            Instruction* dependency,
52                                        SetVector<Instruction*>& possiblyDead);
53    bool handleEndBlock(BasicBlock& BB, SetVector<Instruction*>& possiblyDead);
54    bool RemoveUndeadPointers(Value* pointer,
55                              BasicBlock::iterator& BBI,
56                              SmallPtrSet<AllocaInst*, 64>& deadPointers,
57                              SetVector<Instruction*>& possiblyDead);
58    void DeleteDeadInstructionChains(Instruction *I,
59                                     SetVector<Instruction*> &DeadInsts);
60
61    /// Find the base pointer that a pointer came from
62    /// Because this is used to find pointers that originate
63    /// from allocas, it is safe to ignore GEP indices, since
64    /// either the store will be in the alloca, and thus dead,
65    /// or beyond the end of the alloca, and thus undefined.
66    void TranslatePointerBitCasts(Value*& v) {
67      assert(isa<PointerType>(v->getType()) &&
68             "Translating a non-pointer type?");
69      while (true) {
70        if (BitCastInst* C = dyn_cast<BitCastInst>(v))
71          v = C->getOperand(0);
72        else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(v))
73          v = G->getOperand(0);
74        else
75          break;
76      }
77    }
78
79    // getAnalysisUsage - We require post dominance frontiers (aka Control
80    // Dependence Graph)
81    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
82      AU.setPreservesCFG();
83      AU.addRequired<TargetData>();
84      AU.addRequired<AliasAnalysis>();
85      AU.addRequired<MemoryDependenceAnalysis>();
86      AU.addPreserved<AliasAnalysis>();
87      AU.addPreserved<MemoryDependenceAnalysis>();
88    }
89  };
90  char DSE::ID = 0;
91  RegisterPass<DSE> X("dse", "Dead Store Elimination");
92}
93
94FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
95
96bool DSE::runOnBasicBlock(BasicBlock &BB) {
97  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
98
99  // Record the last-seen store to this pointer
100  DenseMap<Value*, StoreInst*> lastStore;
101  // Record instructions possibly made dead by deleting a store
102  SetVector<Instruction*> possiblyDead;
103
104  bool MadeChange = false;
105
106  // Do a top-down walk on the BB
107  for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end();
108       BBI != BBE; ++BBI) {
109    // If we find a store or a free...
110    if (!isa<StoreInst>(BBI) && !isa<FreeInst>(BBI))
111      continue;
112
113    Value* pointer = 0;
114    if (StoreInst* S = dyn_cast<StoreInst>(BBI))
115      pointer = S->getPointerOperand();
116    else
117      pointer = cast<FreeInst>(BBI)->getPointerOperand();
118
119    StoreInst*& last = lastStore[pointer];
120    bool deletedStore = false;
121
122    // ... to a pointer that has been stored to before...
123    if (last) {
124      Instruction* dep = MD.getDependency(BBI);
125
126      // ... and no other memory dependencies are between them....
127      while (dep != MemoryDependenceAnalysis::None &&
128             dep != MemoryDependenceAnalysis::NonLocal &&
129             isa<StoreInst>(dep)) {
130        if (dep != last) {
131          dep = MD.getDependency(BBI, dep);
132          continue;
133        }
134
135        // Remove it!
136        MD.removeInstruction(last);
137
138        // DCE instructions only used to calculate that store
139        if (Instruction* D = dyn_cast<Instruction>(last->getOperand(0)))
140          possiblyDead.insert(D);
141        if (Instruction* D = dyn_cast<Instruction>(last->getOperand(1)))
142          possiblyDead.insert(D);
143
144        last->eraseFromParent();
145        NumFastStores++;
146        deletedStore = true;
147        MadeChange = true;
148
149        break;
150      }
151    }
152
153    // Handle frees whose dependencies are non-trivial.
154    if (FreeInst* F = dyn_cast<FreeInst>(BBI)) {
155      if (!deletedStore)
156        MadeChange |= handleFreeWithNonTrivialDependency(F,
157                                                         MD.getDependency(F),
158                                                         possiblyDead);
159      // No known stores after the free
160      last = 0;
161    } else {
162      // Update our most-recent-store map.
163      last = cast<StoreInst>(BBI);
164    }
165  }
166
167  // If this block ends in a return, unwind, unreachable, and eventually
168  // tailcall, then all allocas are dead at its end.
169  if (BB.getTerminator()->getNumSuccessors() == 0)
170    MadeChange |= handleEndBlock(BB, possiblyDead);
171
172  // Do a trivial DCE
173  while (!possiblyDead.empty()) {
174    Instruction *I = possiblyDead.back();
175    possiblyDead.pop_back();
176    DeleteDeadInstructionChains(I, possiblyDead);
177  }
178
179  return MadeChange;
180}
181
182/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose
183/// dependency is a store to a field of that structure
184bool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, Instruction* dep,
185                                       SetVector<Instruction*>& possiblyDead) {
186  TargetData &TD = getAnalysis<TargetData>();
187  AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
188  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
189
190  if (dep == MemoryDependenceAnalysis::None ||
191      dep == MemoryDependenceAnalysis::NonLocal)
192    return false;
193
194  StoreInst* dependency = dyn_cast<StoreInst>(dep);
195  if (!dependency)
196    return false;
197
198  Value* depPointer = dependency->getPointerOperand();
199  const Type* depType = dependency->getOperand(0)->getType();
200  unsigned depPointerSize = TD.getTypeSize(depType);
201
202  // Check for aliasing
203  AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0UL,
204                                          depPointer, depPointerSize);
205
206  if (A == AliasAnalysis::MustAlias) {
207    // Remove it!
208    MD.removeInstruction(dependency);
209
210    // DCE instructions only used to calculate that store
211    if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(0)))
212      possiblyDead.insert(D);
213    if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(1)))
214      possiblyDead.insert(D);
215
216    dependency->eraseFromParent();
217    NumFastStores++;
218    return true;
219  }
220
221  return false;
222}
223
224/// handleEndBlock - Remove dead stores to stack-allocated locations in the
225/// function end block.  Ex:
226/// %A = alloca i32
227/// ...
228/// store i32 1, i32* %A
229/// ret void
230bool DSE::handleEndBlock(BasicBlock& BB,
231                         SetVector<Instruction*>& possiblyDead) {
232  TargetData &TD = getAnalysis<TargetData>();
233  AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
234  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
235
236  bool MadeChange = false;
237
238  // Pointers alloca'd in this function are dead in the end block
239  SmallPtrSet<AllocaInst*, 64> deadPointers;
240
241  // Find all of the alloca'd pointers in the entry block
242  BasicBlock *Entry = BB.getParent()->begin();
243  for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I)
244    if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
245      deadPointers.insert(AI);
246
247  // Scan the basic block backwards
248  for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
249    --BBI;
250
251    if (deadPointers.empty())
252      break;
253
254    // If we find a store whose pointer is dead...
255    if (StoreInst* S = dyn_cast<StoreInst>(BBI)) {
256      Value* pointerOperand = S->getPointerOperand();
257      // See through pointer-to-pointer bitcasts
258      TranslatePointerBitCasts(pointerOperand);
259
260      if (deadPointers.count(pointerOperand)){
261        // Remove it!
262        MD.removeInstruction(S);
263
264        // DCE instructions only used to calculate that store
265        if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0)))
266          possiblyDead.insert(D);
267        if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1)))
268          possiblyDead.insert(D);
269
270        BBI++;
271        S->eraseFromParent();
272        NumFastStores++;
273        MadeChange = true;
274      }
275
276      continue;
277    }
278
279    Value* killPointer = 0;
280
281    // If we encounter a use of the pointer, it is no longer considered dead
282    if (LoadInst* L = dyn_cast<LoadInst>(BBI)) {
283      killPointer = L->getPointerOperand();
284    } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) {
285      killPointer = V->getOperand(0);
286    } else if (AllocaInst* A = dyn_cast<AllocaInst>(BBI)) {
287      deadPointers.erase(A);
288      continue;
289    } else if (CallSite::get(BBI).getInstruction() != 0) {
290      // If this call does not access memory, it can't
291      // be undeadifying any of our pointers.
292      CallSite CS = CallSite::get(BBI);
293      if (CS.getCalledFunction() &&
294          AA.doesNotAccessMemory(CS.getCalledFunction()))
295        continue;
296
297      // Remove any pointers made undead by the call from the dead set
298      std::vector<Instruction*> dead;
299      for (SmallPtrSet<AllocaInst*, 64>::iterator I = deadPointers.begin(),
300           E = deadPointers.end(); I != E; ++I) {
301        // Get size information for the alloca
302        unsigned pointerSize = ~0UL;
303        if (ConstantInt* C = dyn_cast<ConstantInt>((*I)->getArraySize()))
304          pointerSize = C->getZExtValue() * \
305                        TD.getTypeSize((*I)->getAllocatedType());
306
307        // See if the call site touches it
308        AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize);
309        if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref)
310          dead.push_back(*I);
311      }
312
313      for (std::vector<Instruction*>::iterator I = dead.begin(), E = dead.end();
314           I != E; ++I)
315        deadPointers.erase(*I);
316
317      continue;
318    }
319
320    if (!killPointer)
321      continue;
322
323    // Deal with undead pointers
324    MadeChange |= RemoveUndeadPointers(killPointer, BBI,
325                                       deadPointers, possiblyDead);
326  }
327
328  return MadeChange;
329}
330
331/// RemoveUndeadPointers - takes an instruction and a setvector of
332/// dead instructions.  If I is dead, it is erased, and its operands are
333/// checked for deadness.  If they are dead, they are added to the dead
334/// setvector.
335bool DSE::RemoveUndeadPointers(Value* killPointer,
336                                BasicBlock::iterator& BBI,
337                                SmallPtrSet<AllocaInst*, 64>& deadPointers,
338                                SetVector<Instruction*>& possiblyDead) {
339  TargetData &TD = getAnalysis<TargetData>();
340  AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
341  MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>();
342
343  bool MadeChange = false;
344
345  std::vector<Instruction*> undead;
346
347  for (SmallPtrSet<AllocaInst*, 64>::iterator I = deadPointers.begin(),
348      E = deadPointers.end(); I != E; ++I) {
349    // Get size information for the alloca
350    unsigned pointerSize = ~0UL;
351    if (ConstantInt* C = dyn_cast<ConstantInt>((*I)->getArraySize()))
352      pointerSize = C->getZExtValue() * \
353                    TD.getTypeSize((*I)->getAllocatedType());
354
355    // See if this pointer could alias it
356    AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize,
357                                            killPointer, ~0UL);
358
359    // If it must-alias and a store, we can delete it
360    if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) {
361      StoreInst* S = cast<StoreInst>(BBI);
362
363      // Remove it!
364      MD.removeInstruction(S);
365
366      // DCE instructions only used to calculate that store
367      if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0)))
368        possiblyDead.insert(D);
369      if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1)))
370        possiblyDead.insert(D);
371
372      BBI++;
373      S->eraseFromParent();
374      NumFastStores++;
375      MadeChange = true;
376
377      continue;
378
379      // Otherwise, it is undead
380      } else if (A != AliasAnalysis::NoAlias)
381        undead.push_back(*I);
382  }
383
384  for (std::vector<Instruction*>::iterator I = undead.begin(), E = undead.end();
385       I != E; ++I)
386    deadPointers.erase(*I);
387
388  return MadeChange;
389}
390
391/// DeleteDeadInstructionChains - takes an instruction and a setvector of
392/// dead instructions.  If I is dead, it is erased, and its operands are
393/// checked for deadness.  If they are dead, they are added to the dead
394/// setvector.
395void DSE::DeleteDeadInstructionChains(Instruction *I,
396                                      SetVector<Instruction*> &DeadInsts) {
397  // Instruction must be dead.
398  if (!I->use_empty() || !isInstructionTriviallyDead(I)) return;
399
400  // Let the memory dependence know
401  getAnalysis<MemoryDependenceAnalysis>().removeInstruction(I);
402
403  // See if this made any operands dead.  We do it this way in case the
404  // instruction uses the same operand twice.  We don't want to delete a
405  // value then reference it.
406  for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
407    if (I->getOperand(i)->hasOneUse())
408      if (Instruction* Op = dyn_cast<Instruction>(I->getOperand(i)))
409        DeadInsts.insert(Op);      // Attempt to nuke it later.
410
411    I->setOperand(i, 0);         // Drop from the operand list.
412  }
413
414  I->eraseFromParent();
415  ++NumFastOther;
416}
417