DeadStoreElimination.cpp revision b51deb929ca95ce62e622b0475a05d83f26ab04d
1//===- DeadStoreElimination.cpp - Fast Dead Store Elimination -------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// 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/IntrinsicInst.h" 24#include "llvm/Pass.h" 25#include "llvm/ADT/SmallPtrSet.h" 26#include "llvm/ADT/Statistic.h" 27#include "llvm/Analysis/AliasAnalysis.h" 28#include "llvm/Analysis/Dominators.h" 29#include "llvm/Analysis/MemoryDependenceAnalysis.h" 30#include "llvm/Target/TargetData.h" 31#include "llvm/Transforms/Utils/Local.h" 32#include "llvm/Support/Compiler.h" 33using namespace llvm; 34 35STATISTIC(NumFastStores, "Number of stores deleted"); 36STATISTIC(NumFastOther , "Number of other instrs removed"); 37 38namespace { 39 struct VISIBILITY_HIDDEN DSE : public FunctionPass { 40 static char ID; // Pass identification, replacement for typeid 41 DSE() : FunctionPass(&ID) {} 42 43 virtual bool runOnFunction(Function &F) { 44 bool Changed = false; 45 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 46 Changed |= runOnBasicBlock(*I); 47 return Changed; 48 } 49 50 bool runOnBasicBlock(BasicBlock &BB); 51 bool handleFreeWithNonTrivialDependency(FreeInst *F, MemDepResult Dep); 52 bool handleEndBlock(BasicBlock &BB); 53 bool RemoveUndeadPointers(Value* pointer, uint64_t killPointerSize, 54 BasicBlock::iterator& BBI, 55 SmallPtrSet<Value*, 64>& deadPointers); 56 void DeleteDeadInstruction(Instruction *I, 57 SmallPtrSet<Value*, 64> *deadPointers = 0); 58 59 60 // getAnalysisUsage - We require post dominance frontiers (aka Control 61 // Dependence Graph) 62 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 63 AU.setPreservesCFG(); 64 AU.addRequired<DominatorTree>(); 65 AU.addRequired<TargetData>(); 66 AU.addRequired<AliasAnalysis>(); 67 AU.addRequired<MemoryDependenceAnalysis>(); 68 AU.addPreserved<DominatorTree>(); 69 AU.addPreserved<AliasAnalysis>(); 70 AU.addPreserved<MemoryDependenceAnalysis>(); 71 } 72 }; 73} 74 75char DSE::ID = 0; 76static RegisterPass<DSE> X("dse", "Dead Store Elimination"); 77 78FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 79 80bool DSE::runOnBasicBlock(BasicBlock &BB) { 81 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 82 TargetData &TD = getAnalysis<TargetData>(); 83 84 // Record the last-seen store to this pointer 85 DenseMap<Value*, StoreInst*> lastStore; 86 87 bool MadeChange = false; 88 89 // Do a top-down walk on the BB 90 for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { 91 Instruction *Inst = BBI++; 92 93 // If we find a store or a free... 94 if (!isa<StoreInst>(Inst) && !isa<FreeInst>(Inst)) 95 continue; 96 97 Value* pointer = 0; 98 if (StoreInst* S = dyn_cast<StoreInst>(Inst)) { 99 if (S->isVolatile()) 100 continue; 101 pointer = S->getPointerOperand(); 102 } else { 103 pointer = cast<FreeInst>(Inst)->getPointerOperand(); 104 } 105 106 pointer = pointer->stripPointerCasts(); 107 StoreInst *&last = lastStore[pointer]; 108 109 // ... to a pointer that has been stored to before... 110 if (last) { 111 MemDepResult dep = MD.getDependency(Inst); 112 bool deletedStore = false; 113 114 // ... and no other memory dependencies are between them.... 115 while (StoreInst *DepStore = dyn_cast_or_null<StoreInst>(dep.getInst())) { 116 if (DepStore != last || 117 TD.getTypeStoreSize(last->getOperand(0)->getType()) > 118 TD.getTypeStoreSize(Inst->getOperand(0)->getType())) { 119 dep = MD.getDependencyFrom(Inst, DepStore, DepStore->getParent()); 120 continue; 121 } 122 123 // Delete the store and now-dead instructions that feed it. 124 DeleteDeadInstruction(last); 125 NumFastStores++; 126 deletedStore = true; 127 MadeChange = true; 128 break; 129 } 130 131 // If we deleted a store, reinvestigate this instruction. 132 if (deletedStore) { 133 if (BBI != BB.begin()) 134 --BBI; 135 continue; 136 } 137 } 138 139 // Handle frees whose dependencies are non-trivial. 140 if (FreeInst* F = dyn_cast<FreeInst>(Inst)) { 141 MadeChange |= handleFreeWithNonTrivialDependency(F, MD.getDependency(F)); 142 143 // No known stores after the free. 144 last = 0; 145 } else { 146 StoreInst* S = cast<StoreInst>(Inst); 147 148 // If we're storing the same value back to a pointer that we just 149 // loaded from, then the store can be removed; 150 if (LoadInst* L = dyn_cast<LoadInst>(S->getOperand(0))) { 151 if (!S->isVolatile() && S->getParent() == L->getParent() && 152 S->getPointerOperand() == L->getPointerOperand()) { 153 MemDepResult dep = MD.getDependency(S); 154 if (dep.isDef() && dep.getInst() == L) { 155 DeleteDeadInstruction(S); 156 if (BBI != BB.begin()) 157 --BBI; 158 NumFastStores++; 159 MadeChange = true; 160 } else { 161 // Update our most-recent-store map. 162 last = S; 163 } 164 } else { 165 // Update our most-recent-store map. 166 last = S; 167 } 168 } else { 169 // Update our most-recent-store map. 170 last = S; 171 } 172 } 173 } 174 175 // If this block ends in a return, unwind, or unreachable, all allocas are 176 // dead at its end, which means stores to them are also dead. 177 if (BB.getTerminator()->getNumSuccessors() == 0) 178 MadeChange |= handleEndBlock(BB); 179 180 return MadeChange; 181} 182 183/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose 184/// dependency is a store to a field of that structure. 185bool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, MemDepResult dep) { 186 TargetData &TD = getAnalysis<TargetData>(); 187 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 188 189 StoreInst* dependency = dyn_cast_or_null<StoreInst>(dep.getInst()); 190 if (!dependency) 191 return false; 192 else if (dependency->isVolatile()) 193 return false; 194 195 Value* depPointer = dependency->getPointerOperand(); 196 const Type* depType = dependency->getOperand(0)->getType(); 197 unsigned depPointerSize = TD.getTypeStoreSize(depType); 198 199 // Check for aliasing 200 AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0U, 201 depPointer, depPointerSize); 202 203 if (A != AliasAnalysis::MustAlias) 204 return false; 205 206 // DCE instructions only used to calculate that store 207 DeleteDeadInstruction(dependency); 208 NumFastStores++; 209 return true; 210} 211 212/// handleEndBlock - Remove dead stores to stack-allocated locations in the 213/// function end block. Ex: 214/// %A = alloca i32 215/// ... 216/// store i32 1, i32* %A 217/// ret void 218bool DSE::handleEndBlock(BasicBlock &BB) { 219 TargetData &TD = getAnalysis<TargetData>(); 220 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 221 222 bool MadeChange = false; 223 224 // Pointers alloca'd in this function are dead in the end block 225 SmallPtrSet<Value*, 64> deadPointers; 226 227 // Find all of the alloca'd pointers in the entry block. 228 BasicBlock *Entry = BB.getParent()->begin(); 229 for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 230 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 231 deadPointers.insert(AI); 232 233 // Treat byval arguments the same, stores to them are dead at the end of the 234 // function. 235 for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 236 AE = BB.getParent()->arg_end(); AI != AE; ++AI) 237 if (AI->hasByValAttr()) 238 deadPointers.insert(AI); 239 240 // Scan the basic block backwards 241 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 242 --BBI; 243 244 // If we find a store whose pointer is dead. 245 if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { 246 if (!S->isVolatile()) { 247 // See through pointer-to-pointer bitcasts 248 Value* pointerOperand = S->getPointerOperand()->getUnderlyingObject(); 249 250 // Alloca'd pointers or byval arguments (which are functionally like 251 // alloca's) are valid candidates for removal. 252 if (deadPointers.count(pointerOperand)) { 253 // DCE instructions only used to calculate that store. 254 BBI++; 255 DeleteDeadInstruction(S, &deadPointers); 256 NumFastStores++; 257 MadeChange = true; 258 } 259 } 260 261 continue; 262 } 263 264 // We can also remove memcpy's to local variables at the end of a function. 265 if (MemCpyInst *M = dyn_cast<MemCpyInst>(BBI)) { 266 Value *dest = M->getDest()->getUnderlyingObject(); 267 268 if (deadPointers.count(dest)) { 269 BBI++; 270 DeleteDeadInstruction(M, &deadPointers); 271 NumFastOther++; 272 MadeChange = true; 273 continue; 274 } 275 276 // Because a memcpy is also a load, we can't skip it if we didn't remove 277 // it. 278 } 279 280 Value* killPointer = 0; 281 uint64_t killPointerSize = ~0UL; 282 283 // If we encounter a use of the pointer, it is no longer considered dead 284 if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { 285 // However, if this load is unused and not volatile, we can go ahead and 286 // remove it, and not have to worry about it making our pointer undead! 287 if (L->use_empty() && !L->isVolatile()) { 288 BBI++; 289 DeleteDeadInstruction(L, &deadPointers); 290 NumFastOther++; 291 MadeChange = true; 292 continue; 293 } 294 295 killPointer = L->getPointerOperand(); 296 } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) { 297 killPointer = V->getOperand(0); 298 } else if (isa<MemCpyInst>(BBI) && 299 isa<ConstantInt>(cast<MemCpyInst>(BBI)->getLength())) { 300 killPointer = cast<MemCpyInst>(BBI)->getSource(); 301 killPointerSize = cast<ConstantInt>( 302 cast<MemCpyInst>(BBI)->getLength())->getZExtValue(); 303 } else if (AllocaInst* A = dyn_cast<AllocaInst>(BBI)) { 304 deadPointers.erase(A); 305 306 // Dead alloca's can be DCE'd when we reach them 307 if (A->use_empty()) { 308 BBI++; 309 DeleteDeadInstruction(A, &deadPointers); 310 NumFastOther++; 311 MadeChange = true; 312 } 313 314 continue; 315 } else if (CallSite::get(BBI).getInstruction() != 0) { 316 // If this call does not access memory, it can't 317 // be undeadifying any of our pointers. 318 CallSite CS = CallSite::get(BBI); 319 if (AA.doesNotAccessMemory(CS)) 320 continue; 321 322 unsigned modRef = 0; 323 unsigned other = 0; 324 325 // Remove any pointers made undead by the call from the dead set 326 std::vector<Value*> dead; 327 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 328 E = deadPointers.end(); I != E; ++I) { 329 // HACK: if we detect that our AA is imprecise, it's not 330 // worth it to scan the rest of the deadPointers set. Just 331 // assume that the AA will return ModRef for everything, and 332 // go ahead and bail. 333 if (modRef >= 16 && other == 0) { 334 deadPointers.clear(); 335 return MadeChange; 336 } 337 338 // Get size information for the alloca 339 unsigned pointerSize = ~0U; 340 if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 341 if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 342 pointerSize = C->getZExtValue() * 343 TD.getABITypeSize(A->getAllocatedType()); 344 } else { 345 const PointerType* PT = cast<PointerType>( 346 cast<Argument>(*I)->getType()); 347 pointerSize = TD.getABITypeSize(PT->getElementType()); 348 } 349 350 // See if the call site touches it 351 AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize); 352 353 if (A == AliasAnalysis::ModRef) 354 modRef++; 355 else 356 other++; 357 358 if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 359 dead.push_back(*I); 360 } 361 362 for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end(); 363 I != E; ++I) 364 deadPointers.erase(*I); 365 366 continue; 367 } else if (isInstructionTriviallyDead(BBI)) { 368 // For any non-memory-affecting non-terminators, DCE them as we reach them 369 Instruction *Inst = BBI; 370 BBI++; 371 DeleteDeadInstruction(Inst, &deadPointers); 372 NumFastOther++; 373 MadeChange = true; 374 continue; 375 } 376 377 if (!killPointer) 378 continue; 379 380 killPointer = killPointer->getUnderlyingObject(); 381 382 // Deal with undead pointers 383 MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI, 384 deadPointers); 385 } 386 387 return MadeChange; 388} 389 390/// RemoveUndeadPointers - check for uses of a pointer that make it 391/// undead when scanning for dead stores to alloca's. 392bool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize, 393 BasicBlock::iterator &BBI, 394 SmallPtrSet<Value*, 64>& deadPointers) { 395 TargetData &TD = getAnalysis<TargetData>(); 396 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 397 398 // If the kill pointer can be easily reduced to an alloca, 399 // don't bother doing extraneous AA queries. 400 if (deadPointers.count(killPointer)) { 401 deadPointers.erase(killPointer); 402 return false; 403 } 404 405 // A global can't be in the dead pointer set. 406 if (isa<GlobalValue>(killPointer)) 407 return false; 408 409 bool MadeChange = false; 410 411 SmallVector<Value*, 16> undead; 412 413 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 414 E = deadPointers.end(); I != E; ++I) { 415 // Get size information for the alloca. 416 unsigned pointerSize = ~0U; 417 if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 418 if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 419 pointerSize = C->getZExtValue() * 420 TD.getABITypeSize(A->getAllocatedType()); 421 } else { 422 const PointerType* PT = cast<PointerType>(cast<Argument>(*I)->getType()); 423 pointerSize = TD.getABITypeSize(PT->getElementType()); 424 } 425 426 // See if this pointer could alias it 427 AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize, 428 killPointer, killPointerSize); 429 430 // If it must-alias and a store, we can delete it 431 if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { 432 StoreInst* S = cast<StoreInst>(BBI); 433 434 // Remove it! 435 BBI++; 436 DeleteDeadInstruction(S, &deadPointers); 437 NumFastStores++; 438 MadeChange = true; 439 440 continue; 441 442 // Otherwise, it is undead 443 } else if (A != AliasAnalysis::NoAlias) 444 undead.push_back(*I); 445 } 446 447 for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end(); 448 I != E; ++I) 449 deadPointers.erase(*I); 450 451 return MadeChange; 452} 453 454/// DeleteDeadInstruction - Delete this instruction. Before we do, go through 455/// and zero out all the operands of this instruction. If any of them become 456/// dead, delete them and the computation tree that feeds them. 457/// 458/// If ValueSet is non-null, remove any deleted instructions from it as well. 459/// 460void DSE::DeleteDeadInstruction(Instruction *I, 461 SmallPtrSet<Value*, 64> *ValueSet) { 462 SmallVector<Instruction*, 32> NowDeadInsts; 463 464 NowDeadInsts.push_back(I); 465 --NumFastOther; 466 467 // Before we touch this instruction, remove it from memdep! 468 MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>(); 469 while (!NowDeadInsts.empty()) { 470 Instruction *DeadInst = NowDeadInsts.back(); 471 NowDeadInsts.pop_back(); 472 473 ++NumFastOther; 474 475 // This instruction is dead, zap it, in stages. Start by removing it from 476 // MemDep, which needs to know the operands and needs it to be in the 477 // function. 478 MDA.removeInstruction(DeadInst); 479 480 for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 481 Value *Op = DeadInst->getOperand(op); 482 DeadInst->setOperand(op, 0); 483 484 // If this operand just became dead, add it to the NowDeadInsts list. 485 if (!Op->use_empty()) continue; 486 487 if (Instruction *OpI = dyn_cast<Instruction>(Op)) 488 if (isInstructionTriviallyDead(OpI)) 489 NowDeadInsts.push_back(OpI); 490 } 491 492 DeadInst->eraseFromParent(); 493 494 if (ValueSet) ValueSet->erase(DeadInst); 495 } 496} 497