LLVM API Documentation
00001 //===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements a trivial dead store elimination that only considers 00011 // basic-block local redundant stores. 00012 // 00013 // FIXME: This should eventually be extended to be a post-dominator tree 00014 // traversal. Doing so would be pretty trivial. 00015 // 00016 //===----------------------------------------------------------------------===// 00017 00018 #define DEBUG_TYPE "dse" 00019 #include "llvm/Transforms/Scalar.h" 00020 #include "llvm/Constants.h" 00021 #include "llvm/Function.h" 00022 #include "llvm/Instructions.h" 00023 #include "llvm/IntrinsicInst.h" 00024 #include "llvm/Pass.h" 00025 #include "llvm/ADT/SmallPtrSet.h" 00026 #include "llvm/ADT/Statistic.h" 00027 #include "llvm/Analysis/AliasAnalysis.h" 00028 #include "llvm/Analysis/Dominators.h" 00029 #include "llvm/Analysis/MemoryDependenceAnalysis.h" 00030 #include "llvm/Target/TargetData.h" 00031 #include "llvm/Transforms/Utils/Local.h" 00032 #include "llvm/Support/Compiler.h" 00033 #include "llvm/Support/ValueHandle.h" 00034 using namespace llvm; 00035 00036 STATISTIC(NumFastStores, "Number of stores deleted"); 00037 STATISTIC(NumFastOther , "Number of other instrs removed"); 00038 00039 namespace { 00040 struct VISIBILITY_HIDDEN DSE : public FunctionPass { 00041 TargetData *TD; 00042 00043 static char ID; // Pass identification, replacement for typeid 00044 DSE() : FunctionPass(&ID) {} 00045 00046 virtual bool runOnFunction(Function &F) { 00047 bool Changed = false; 00048 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 00049 Changed |= runOnBasicBlock(*I); 00050 return Changed; 00051 } 00052 00053 bool runOnBasicBlock(BasicBlock &BB); 00054 bool handleFreeWithNonTrivialDependency(FreeInst *F, MemDepResult Dep); 00055 bool handleEndBlock(BasicBlock &BB); 00056 bool RemoveUndeadPointers(Value* Ptr, uint64_t killPointerSize, 00057 BasicBlock::iterator& BBI, 00058 SmallPtrSet<Value*, 64>& deadPointers); 00059 void DeleteDeadInstruction(Instruction *I, 00060 SmallPtrSet<Value*, 64> *deadPointers = 0); 00061 00062 00063 // getAnalysisUsage - We require post dominance frontiers (aka Control 00064 // Dependence Graph) 00065 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00066 AU.setPreservesCFG(); 00067 AU.addRequired<DominatorTree>(); 00068 AU.addRequired<AliasAnalysis>(); 00069 AU.addRequired<MemoryDependenceAnalysis>(); 00070 AU.addPreserved<DominatorTree>(); 00071 AU.addPreserved<AliasAnalysis>(); 00072 AU.addPreserved<MemoryDependenceAnalysis>(); 00073 } 00074 }; 00075 } 00076 00077 char DSE::ID = 0; 00078 static RegisterPass<DSE> X("dse", "Dead Store Elimination"); 00079 00080 FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 00081 00082 bool DSE::runOnBasicBlock(BasicBlock &BB) { 00083 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 00084 TD = getAnalysisIfAvailable<TargetData>(); 00085 00086 bool MadeChange = false; 00087 00088 // Do a top-down walk on the BB. 00089 for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { 00090 Instruction *Inst = BBI++; 00091 00092 // If we find a store or a free, get its memory dependence. 00093 if (!isa<StoreInst>(Inst) && !isa<FreeInst>(Inst)) 00094 continue; 00095 00096 // Don't molest volatile stores or do queries that will return "clobber". 00097 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) 00098 if (SI->isVolatile()) 00099 continue; 00100 00101 MemDepResult InstDep = MD.getDependency(Inst); 00102 00103 // Ignore non-local stores. 00104 // FIXME: cross-block DSE would be fun. :) 00105 if (InstDep.isNonLocal()) continue; 00106 00107 // Handle frees whose dependencies are non-trivial. 00108 if (FreeInst *FI = dyn_cast<FreeInst>(Inst)) { 00109 MadeChange |= handleFreeWithNonTrivialDependency(FI, InstDep); 00110 continue; 00111 } 00112 00113 StoreInst *SI = cast<StoreInst>(Inst); 00114 00115 // If not a definite must-alias dependency, ignore it. 00116 if (!InstDep.isDef()) 00117 continue; 00118 00119 // If this is a store-store dependence, then the previous store is dead so 00120 // long as this store is at least as big as it. 00121 if (StoreInst *DepStore = dyn_cast<StoreInst>(InstDep.getInst())) 00122 if (TD && 00123 TD->getTypeStoreSize(DepStore->getOperand(0)->getType()) <= 00124 TD->getTypeStoreSize(SI->getOperand(0)->getType())) { 00125 // Delete the store and now-dead instructions that feed it. 00126 DeleteDeadInstruction(DepStore); 00127 NumFastStores++; 00128 MadeChange = true; 00129 00130 // DeleteDeadInstruction can delete the current instruction in loop 00131 // cases, reset BBI. 00132 BBI = Inst; 00133 if (BBI != BB.begin()) 00134 --BBI; 00135 continue; 00136 } 00137 00138 // If we're storing the same value back to a pointer that we just 00139 // loaded from, then the store can be removed. 00140 if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) { 00141 if (SI->getPointerOperand() == DepLoad->getPointerOperand() && 00142 SI->getOperand(0) == DepLoad) { 00143 // DeleteDeadInstruction can delete the current instruction. Save BBI 00144 // in case we need it. 00145 WeakVH NextInst(BBI); 00146 00147 DeleteDeadInstruction(SI); 00148 00149 if (NextInst == 0) // Next instruction deleted. 00150 BBI = BB.begin(); 00151 else if (BBI != BB.begin()) // Revisit this instruction if possible. 00152 --BBI; 00153 NumFastStores++; 00154 MadeChange = true; 00155 continue; 00156 } 00157 } 00158 } 00159 00160 // If this block ends in a return, unwind, or unreachable, all allocas are 00161 // dead at its end, which means stores to them are also dead. 00162 if (BB.getTerminator()->getNumSuccessors() == 0) 00163 MadeChange |= handleEndBlock(BB); 00164 00165 return MadeChange; 00166 } 00167 00168 /// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose 00169 /// dependency is a store to a field of that structure. 00170 bool DSE::handleFreeWithNonTrivialDependency(FreeInst *F, MemDepResult Dep) { 00171 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 00172 00173 StoreInst *Dependency = dyn_cast_or_null<StoreInst>(Dep.getInst()); 00174 if (!Dependency || Dependency->isVolatile()) 00175 return false; 00176 00177 Value *DepPointer = Dependency->getPointerOperand()->getUnderlyingObject(); 00178 00179 // Check for aliasing. 00180 if (AA.alias(F->getPointerOperand(), 1, DepPointer, 1) != 00181 AliasAnalysis::MustAlias) 00182 return false; 00183 00184 // DCE instructions only used to calculate that store 00185 DeleteDeadInstruction(Dependency); 00186 NumFastStores++; 00187 return true; 00188 } 00189 00190 /// handleEndBlock - Remove dead stores to stack-allocated locations in the 00191 /// function end block. Ex: 00192 /// %A = alloca i32 00193 /// ... 00194 /// store i32 1, i32* %A 00195 /// ret void 00196 bool DSE::handleEndBlock(BasicBlock &BB) { 00197 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 00198 00199 bool MadeChange = false; 00200 00201 // Pointers alloca'd in this function are dead in the end block 00202 SmallPtrSet<Value*, 64> deadPointers; 00203 00204 // Find all of the alloca'd pointers in the entry block. 00205 BasicBlock *Entry = BB.getParent()->begin(); 00206 for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 00207 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 00208 deadPointers.insert(AI); 00209 00210 // Treat byval arguments the same, stores to them are dead at the end of the 00211 // function. 00212 for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 00213 AE = BB.getParent()->arg_end(); AI != AE; ++AI) 00214 if (AI->hasByValAttr()) 00215 deadPointers.insert(AI); 00216 00217 // Scan the basic block backwards 00218 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 00219 --BBI; 00220 00221 // If we find a store whose pointer is dead. 00222 if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { 00223 if (!S->isVolatile()) { 00224 // See through pointer-to-pointer bitcasts 00225 Value* pointerOperand = S->getPointerOperand()->getUnderlyingObject(); 00226 00227 // Alloca'd pointers or byval arguments (which are functionally like 00228 // alloca's) are valid candidates for removal. 00229 if (deadPointers.count(pointerOperand)) { 00230 // DCE instructions only used to calculate that store. 00231 BBI++; 00232 DeleteDeadInstruction(S, &deadPointers); 00233 NumFastStores++; 00234 MadeChange = true; 00235 } 00236 } 00237 00238 continue; 00239 } 00240 00241 // We can also remove memcpy's to local variables at the end of a function. 00242 if (MemCpyInst *M = dyn_cast<MemCpyInst>(BBI)) { 00243 Value *dest = M->getDest()->getUnderlyingObject(); 00244 00245 if (deadPointers.count(dest)) { 00246 BBI++; 00247 DeleteDeadInstruction(M, &deadPointers); 00248 NumFastOther++; 00249 MadeChange = true; 00250 continue; 00251 } 00252 00253 // Because a memcpy is also a load, we can't skip it if we didn't remove 00254 // it. 00255 } 00256 00257 Value* killPointer = 0; 00258 uint64_t killPointerSize = ~0UL; 00259 00260 // If we encounter a use of the pointer, it is no longer considered dead 00261 if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { 00262 // However, if this load is unused and not volatile, we can go ahead and 00263 // remove it, and not have to worry about it making our pointer undead! 00264 if (L->use_empty() && !L->isVolatile()) { 00265 BBI++; 00266 DeleteDeadInstruction(L, &deadPointers); 00267 NumFastOther++; 00268 MadeChange = true; 00269 continue; 00270 } 00271 00272 killPointer = L->getPointerOperand(); 00273 } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) { 00274 killPointer = V->getOperand(0); 00275 } else if (isa<MemCpyInst>(BBI) && 00276 isa<ConstantInt>(cast<MemCpyInst>(BBI)->getLength())) { 00277 killPointer = cast<MemCpyInst>(BBI)->getSource(); 00278 killPointerSize = cast<ConstantInt>( 00279 cast<MemCpyInst>(BBI)->getLength())->getZExtValue(); 00280 } else if (AllocaInst* A = dyn_cast<AllocaInst>(BBI)) { 00281 deadPointers.erase(A); 00282 00283 // Dead alloca's can be DCE'd when we reach them 00284 if (A->use_empty()) { 00285 BBI++; 00286 DeleteDeadInstruction(A, &deadPointers); 00287 NumFastOther++; 00288 MadeChange = true; 00289 } 00290 00291 continue; 00292 } else if (CallSite::get(BBI).getInstruction() != 0) { 00293 // If this call does not access memory, it can't 00294 // be undeadifying any of our pointers. 00295 CallSite CS = CallSite::get(BBI); 00296 if (AA.doesNotAccessMemory(CS)) 00297 continue; 00298 00299 unsigned modRef = 0; 00300 unsigned other = 0; 00301 00302 // Remove any pointers made undead by the call from the dead set 00303 std::vector<Value*> dead; 00304 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 00305 E = deadPointers.end(); I != E; ++I) { 00306 // HACK: if we detect that our AA is imprecise, it's not 00307 // worth it to scan the rest of the deadPointers set. Just 00308 // assume that the AA will return ModRef for everything, and 00309 // go ahead and bail. 00310 if (modRef >= 16 && other == 0) { 00311 deadPointers.clear(); 00312 return MadeChange; 00313 } 00314 00315 // Get size information for the alloca 00316 unsigned pointerSize = ~0U; 00317 if (TD) { 00318 if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 00319 if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 00320 pointerSize = C->getZExtValue() * 00321 TD->getTypeAllocSize(A->getAllocatedType()); 00322 } else { 00323 const PointerType* PT = cast<PointerType>( 00324 cast<Argument>(*I)->getType()); 00325 pointerSize = TD->getTypeAllocSize(PT->getElementType()); 00326 } 00327 } 00328 00329 // See if the call site touches it 00330 AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize); 00331 00332 if (A == AliasAnalysis::ModRef) 00333 modRef++; 00334 else 00335 other++; 00336 00337 if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 00338 dead.push_back(*I); 00339 } 00340 00341 for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end(); 00342 I != E; ++I) 00343 deadPointers.erase(*I); 00344 00345 continue; 00346 } else if (isInstructionTriviallyDead(BBI)) { 00347 // For any non-memory-affecting non-terminators, DCE them as we reach them 00348 Instruction *Inst = BBI; 00349 BBI++; 00350 DeleteDeadInstruction(Inst, &deadPointers); 00351 NumFastOther++; 00352 MadeChange = true; 00353 continue; 00354 } 00355 00356 if (!killPointer) 00357 continue; 00358 00359 killPointer = killPointer->getUnderlyingObject(); 00360 00361 // Deal with undead pointers 00362 MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI, 00363 deadPointers); 00364 } 00365 00366 return MadeChange; 00367 } 00368 00369 /// RemoveUndeadPointers - check for uses of a pointer that make it 00370 /// undead when scanning for dead stores to alloca's. 00371 bool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize, 00372 BasicBlock::iterator &BBI, 00373 SmallPtrSet<Value*, 64>& deadPointers) { 00374 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 00375 00376 // If the kill pointer can be easily reduced to an alloca, 00377 // don't bother doing extraneous AA queries. 00378 if (deadPointers.count(killPointer)) { 00379 deadPointers.erase(killPointer); 00380 return false; 00381 } 00382 00383 // A global can't be in the dead pointer set. 00384 if (isa<GlobalValue>(killPointer)) 00385 return false; 00386 00387 bool MadeChange = false; 00388 00389 SmallVector<Value*, 16> undead; 00390 00391 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 00392 E = deadPointers.end(); I != E; ++I) { 00393 // Get size information for the alloca. 00394 unsigned pointerSize = ~0U; 00395 if (TD) { 00396 if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 00397 if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 00398 pointerSize = C->getZExtValue() * 00399 TD->getTypeAllocSize(A->getAllocatedType()); 00400 } else { 00401 const PointerType* PT = cast<PointerType>(cast<Argument>(*I)->getType()); 00402 pointerSize = TD->getTypeAllocSize(PT->getElementType()); 00403 } 00404 } 00405 00406 // See if this pointer could alias it 00407 AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize, 00408 killPointer, killPointerSize); 00409 00410 // If it must-alias and a store, we can delete it 00411 if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { 00412 StoreInst* S = cast<StoreInst>(BBI); 00413 00414 // Remove it! 00415 BBI++; 00416 DeleteDeadInstruction(S, &deadPointers); 00417 NumFastStores++; 00418 MadeChange = true; 00419 00420 continue; 00421 00422 // Otherwise, it is undead 00423 } else if (A != AliasAnalysis::NoAlias) 00424 undead.push_back(*I); 00425 } 00426 00427 for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end(); 00428 I != E; ++I) 00429 deadPointers.erase(*I); 00430 00431 return MadeChange; 00432 } 00433 00434 /// DeleteDeadInstruction - Delete this instruction. Before we do, go through 00435 /// and zero out all the operands of this instruction. If any of them become 00436 /// dead, delete them and the computation tree that feeds them. 00437 /// 00438 /// If ValueSet is non-null, remove any deleted instructions from it as well. 00439 /// 00440 void DSE::DeleteDeadInstruction(Instruction *I, 00441 SmallPtrSet<Value*, 64> *ValueSet) { 00442 SmallVector<Instruction*, 32> NowDeadInsts; 00443 00444 NowDeadInsts.push_back(I); 00445 --NumFastOther; 00446 00447 // Before we touch this instruction, remove it from memdep! 00448 MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>(); 00449 while (!NowDeadInsts.empty()) { 00450 Instruction *DeadInst = NowDeadInsts.back(); 00451 NowDeadInsts.pop_back(); 00452 00453 ++NumFastOther; 00454 00455 // This instruction is dead, zap it, in stages. Start by removing it from 00456 // MemDep, which needs to know the operands and needs it to be in the 00457 // function. 00458 MDA.removeInstruction(DeadInst); 00459 00460 for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 00461 Value *Op = DeadInst->getOperand(op); 00462 DeadInst->setOperand(op, 0); 00463 00464 // If this operand just became dead, add it to the NowDeadInsts list. 00465 if (!Op->use_empty()) continue; 00466 00467 if (Instruction *OpI = dyn_cast<Instruction>(Op)) 00468 if (isInstructionTriviallyDead(OpI)) 00469 NowDeadInsts.push_back(OpI); 00470 } 00471 00472 DeadInst->eraseFromParent(); 00473 00474 if (ValueSet) ValueSet->erase(DeadInst); 00475 } 00476 }