1 //===- DeadStoreElimination.cpp - Dead Store Elimination ------------------===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This file implements a trivial dead store elimination that only considers
11 // basic-block local redundant stores.
13 // FIXME: This should eventually be extended to be a post-dominator tree
14 // traversal. Doing so would be pretty trivial.
16 //===----------------------------------------------------------------------===//
18 #define DEBUG_TYPE "dse"
19 #include "llvm/Transforms/Scalar.h"
20 #include "llvm/DerivedTypes.h"
21 #include "llvm/Function.h"
22 #include "llvm/Instructions.h"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/Analysis/AliasSetTracker.h"
25 #include "llvm/Target/TargetData.h"
26 #include "llvm/Transforms/Utils/Local.h"
27 #include "llvm/ADT/SetVector.h"
28 #include "llvm/ADT/Statistic.h"
29 #include "llvm/Support/Compiler.h"
32 STATISTIC(NumStores, "Number of stores deleted");
33 STATISTIC(NumOther , "Number of other instrs removed");
36 struct VISIBILITY_HIDDEN DSE : public FunctionPass {
37 static char ID; // Pass identifcation, replacement for typeid
38 DSE() : FunctionPass((intptr_t)&ID) {}
40 virtual bool runOnFunction(Function &F) {
42 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
43 Changed |= runOnBasicBlock(*I);
47 bool runOnBasicBlock(BasicBlock &BB);
49 void DeleteDeadInstructionChains(Instruction *I,
50 SetVector<Instruction*> &DeadInsts);
52 // getAnalysisUsage - We require post dominance frontiers (aka Control
54 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
56 AU.addRequired<TargetData>();
57 AU.addRequired<AliasAnalysis>();
58 AU.addPreserved<AliasAnalysis>();
62 RegisterPass<DSE> X("dse", "Dead Store Elimination");
65 FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
67 bool DSE::runOnBasicBlock(BasicBlock &BB) {
68 TargetData &TD = getAnalysis<TargetData>();
69 AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
70 AliasSetTracker KillLocs(AA);
72 // If this block ends in a return, unwind, unreachable, and eventually
73 // tailcall, then all allocas are dead at its end.
74 if (BB.getTerminator()->getNumSuccessors() == 0) {
75 BasicBlock *Entry = BB.getParent()->begin();
76 for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I)
77 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) {
79 if (!AI->isArrayAllocation() &&
80 AI->getType()->getElementType()->isSized())
81 Size = (unsigned)TD.getTypeSize(AI->getType()->getElementType());
82 KillLocs.add(AI, Size);
86 // PotentiallyDeadInsts - Deleting dead stores from the program can make other
87 // instructions die if they were only used as operands to stores. Keep track
88 // of the operands to stores so that we can try deleting them at the end of
90 SetVector<Instruction*> PotentiallyDeadInsts;
92 bool MadeChange = false;
93 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ) {
94 Instruction *I = --BBI; // Keep moving iterator backwards
96 // If this is a free instruction, it makes the free'd location dead!
97 if (FreeInst *FI = dyn_cast<FreeInst>(I)) {
98 // Free instructions make any stores to the free'd location dead.
103 if (!isa<StoreInst>(I) || cast<StoreInst>(I)->isVolatile()) {
104 // If this is a vaarg instruction, it reads its operand. We don't model
105 // it correctly, so just conservatively remove all entries.
106 if (isa<VAArgInst>(I)) {
111 // If this is a non-store instruction, it makes everything referenced no
112 // longer killed. Remove anything aliased from the alias set tracker.
117 // If this is a non-volatile store instruction, and if it is already in
118 // the stored location is already in the tracker, then this is a dead
119 // store. We can just delete it here, but while we're at it, we also
120 // delete any trivially dead expression chains.
121 unsigned ValSize = (unsigned)TD.getTypeSize(I->getOperand(0)->getType());
122 Value *Ptr = I->getOperand(1);
124 if (AliasSet *AS = KillLocs.getAliasSetForPointerIfExists(Ptr, ValSize))
125 for (AliasSet::iterator ASI = AS->begin(), E = AS->end(); ASI != E; ++ASI)
126 if (ASI.getSize() >= ValSize && // Overwriting all of this store.
127 AA.alias(ASI.getPointer(), ASI.getSize(), Ptr, ValSize)
128 == AliasAnalysis::MustAlias) {
129 // If we found a must alias in the killed set, then this store really
130 // is dead. Remember that the various operands of the store now have
131 // fewer users. At the end we will see if we can delete any values
132 // that are dead as part of the store becoming dead.
133 if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(0)))
134 PotentiallyDeadInsts.insert(Op);
135 if (Instruction *Op = dyn_cast<Instruction>(Ptr))
136 PotentiallyDeadInsts.insert(Op);
139 ++BBI; // Don't invalidate iterator.
140 BB.getInstList().erase(I); // Nuke the store!
146 // Otherwise, this is a non-dead store just add it to the set of dead
148 KillLocs.add(cast<StoreInst>(I));
152 while (!PotentiallyDeadInsts.empty()) {
153 Instruction *I = PotentiallyDeadInsts.back();
154 PotentiallyDeadInsts.pop_back();
155 DeleteDeadInstructionChains(I, PotentiallyDeadInsts);
160 void DSE::DeleteDeadInstructionChains(Instruction *I,
161 SetVector<Instruction*> &DeadInsts) {
162 // Instruction must be dead.
163 if (!I->use_empty() || !isInstructionTriviallyDead(I)) return;
165 // Let the alias analysis know that we have nuked a value.
166 getAnalysis<AliasAnalysis>().deleteValue(I);
168 // See if this made any operands dead. We do it this way in case the
169 // instruction uses the same operand twice. We don't want to delete a
170 // value then reference it.
171 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) {
172 if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i)))
173 DeadInsts.insert(Op); // Attempt to nuke it later.
174 I->setOperand(i, 0); // Drop from the operand list.
177 I->eraseFromParent();