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