DeadStoreElimination.cpp revision e9e973018aaf93dbd21b894b404e4b3a50805479
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/MemoryBuiltins.h" 30#include "llvm/Analysis/MemoryDependenceAnalysis.h" 31#include "llvm/Target/TargetData.h" 32#include "llvm/Transforms/Utils/Local.h" 33using namespace llvm; 34 35STATISTIC(NumFastStores, "Number of stores deleted"); 36STATISTIC(NumFastOther , "Number of other instrs removed"); 37 38namespace { 39 struct DSE : public FunctionPass { 40 TargetData *TD; 41 42 static char ID; // Pass identification, replacement for typeid 43 DSE() : FunctionPass(ID) { 44 initializeDSEPass(*PassRegistry::getPassRegistry()); 45 } 46 47 virtual bool runOnFunction(Function &F) { 48 bool Changed = false; 49 50 DominatorTree &DT = getAnalysis<DominatorTree>(); 51 52 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 53 // Only check non-dead blocks. Dead blocks may have strange pointer 54 // cycles that will confuse alias analysis. 55 if (DT.isReachableFromEntry(I)) 56 Changed |= runOnBasicBlock(*I); 57 return Changed; 58 } 59 60 bool runOnBasicBlock(BasicBlock &BB); 61 bool handleFreeWithNonTrivialDependency(const CallInst *F, 62 Instruction *Inst, 63 MemDepResult Dep); 64 bool handleEndBlock(BasicBlock &BB); 65 bool RemoveUndeadPointers(Value *Ptr, uint64_t killPointerSize, 66 BasicBlock::iterator &BBI, 67 SmallPtrSet<Value*, 64> &deadPointers); 68 void DeleteDeadInstruction(Instruction *I, 69 SmallPtrSet<Value*, 64> *deadPointers = 0); 70 71 72 // getAnalysisUsage - We require post dominance frontiers (aka Control 73 // Dependence Graph) 74 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 75 AU.setPreservesCFG(); 76 AU.addRequired<DominatorTree>(); 77 AU.addRequired<AliasAnalysis>(); 78 AU.addRequired<MemoryDependenceAnalysis>(); 79 AU.addPreserved<DominatorTree>(); 80 AU.addPreserved<MemoryDependenceAnalysis>(); 81 } 82 83 uint64_t getPointerSize(Value *V) const; 84 }; 85} 86 87char DSE::ID = 0; 88INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false) 89INITIALIZE_PASS_DEPENDENCY(DominatorTree) 90INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) 91INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 92INITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false) 93 94FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 95 96/// doesClobberMemory - Does this instruction clobber (write without reading) 97/// some memory? 98static bool doesClobberMemory(Instruction *I) { 99 if (isa<StoreInst>(I)) 100 return true; 101 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 102 switch (II->getIntrinsicID()) { 103 default: 104 return false; 105 case Intrinsic::memset: 106 case Intrinsic::memmove: 107 case Intrinsic::memcpy: 108 case Intrinsic::init_trampoline: 109 case Intrinsic::lifetime_end: 110 return true; 111 } 112 } 113 return false; 114} 115 116/// isElidable - If the value of this instruction and the memory it writes to is 117/// unused, may we delete this instrtction? 118static bool isElidable(Instruction *I) { 119 assert(doesClobberMemory(I)); 120 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 121 return II->getIntrinsicID() != Intrinsic::lifetime_end; 122 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 123 return !SI->isVolatile(); 124 return true; 125} 126 127/// getPointerOperand - Return the pointer that is being clobbered. 128static Value *getPointerOperand(Instruction *I) { 129 assert(doesClobberMemory(I)); 130 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 131 return SI->getPointerOperand(); 132 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) 133 return MI->getArgOperand(0); 134 135 IntrinsicInst *II = cast<IntrinsicInst>(I); 136 switch (II->getIntrinsicID()) { 137 default: assert(false && "Unexpected intrinsic!"); 138 case Intrinsic::init_trampoline: 139 return II->getArgOperand(0); 140 case Intrinsic::lifetime_end: 141 return II->getArgOperand(1); 142 } 143} 144 145/// getStoreSize - Return the length in bytes of the write by the clobbering 146/// instruction. If variable or unknown, returns AliasAnalysis::UnknownSize. 147static uint64_t getStoreSize(Instruction *I, const TargetData *TD) { 148 assert(doesClobberMemory(I)); 149 if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 150 if (!TD) return AliasAnalysis::UnknownSize; 151 return TD->getTypeStoreSize(SI->getOperand(0)->getType()); 152 } 153 154 Value *Len; 155 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) { 156 Len = MI->getLength(); 157 } else { 158 IntrinsicInst *II = cast<IntrinsicInst>(I); 159 switch (II->getIntrinsicID()) { 160 default: assert(false && "Unexpected intrinsic!"); 161 case Intrinsic::init_trampoline: 162 return AliasAnalysis::UnknownSize; 163 case Intrinsic::lifetime_end: 164 Len = II->getArgOperand(0); 165 break; 166 } 167 } 168 if (ConstantInt *LenCI = dyn_cast<ConstantInt>(Len)) 169 if (!LenCI->isAllOnesValue()) 170 return LenCI->getZExtValue(); 171 return AliasAnalysis::UnknownSize; 172} 173 174/// isStoreAtLeastAsWideAs - Return true if the size of the store in I1 is 175/// greater than or equal to the store in I2. This returns false if we don't 176/// know. 177/// 178static bool isStoreAtLeastAsWideAs(Instruction *I1, Instruction *I2, 179 const TargetData *TD) { 180 const Type *I1Ty = getPointerOperand(I1)->getType(); 181 const Type *I2Ty = getPointerOperand(I2)->getType(); 182 183 // Exactly the same type, must have exactly the same size. 184 if (I1Ty == I2Ty) return true; 185 186 uint64_t I1Size = getStoreSize(I1, TD); 187 uint64_t I2Size = getStoreSize(I2, TD); 188 189 return I1Size != AliasAnalysis::UnknownSize && 190 I2Size != AliasAnalysis::UnknownSize && 191 I1Size >= I2Size; 192} 193 194bool DSE::runOnBasicBlock(BasicBlock &BB) { 195 MemoryDependenceAnalysis &MD = getAnalysis<MemoryDependenceAnalysis>(); 196 TD = getAnalysisIfAvailable<TargetData>(); 197 198 bool MadeChange = false; 199 200 // Do a top-down walk on the BB. 201 for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { 202 Instruction *Inst = BBI++; 203 204 // If we find a store or a free, get its memory dependence. 205 if (!doesClobberMemory(Inst) && !isFreeCall(Inst)) 206 continue; 207 208 MemDepResult InstDep = MD.getDependency(Inst); 209 210 // Ignore non-local stores. 211 // FIXME: cross-block DSE would be fun. :) 212 if (InstDep.isNonLocal()) continue; 213 214 // Handle frees whose dependencies are non-trivial. 215 if (const CallInst *F = isFreeCall(Inst)) { 216 MadeChange |= handleFreeWithNonTrivialDependency(F, Inst, InstDep); 217 continue; 218 } 219 220 if (!InstDep.isDef()) { 221 // If this is a may-aliased store that is clobbering the store value, we 222 // can keep searching past it for another must-aliased pointer that stores 223 // to the same location. For example, in: 224 // store -> P 225 // store -> Q 226 // store -> P 227 // we can remove the first store to P even though we don't know if P and Q 228 // alias. 229 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 230 AliasAnalysis::Location Loc = 231 getAnalysis<AliasAnalysis>().getLocation(SI); 232 while (InstDep.isClobber() && isa<StoreInst>(InstDep.getInst()) && 233 InstDep.getInst() != &BB.front()) 234 InstDep = MD.getPointerDependencyFrom(Loc, false, InstDep.getInst(), 235 &BB); 236 } 237 238 // If not a definite must-alias store dependency, ignore it. If this is a 239 // load from the same pointer, we don't want to transform load+store into 240 // a noop. 241 if (!InstDep.isDef() || !isa<StoreInst>(InstDep.getInst())) 242 continue; 243 } 244 245 // If this is a store-store dependence, then the previous store is dead so 246 // long as this store is at least as big as it. 247 if (doesClobberMemory(InstDep.getInst())) { 248 Instruction *DepStore = InstDep.getInst(); 249 if (isStoreAtLeastAsWideAs(Inst, DepStore, TD) && 250 isElidable(DepStore)) { 251 // Delete the store and now-dead instructions that feed it. 252 DeleteDeadInstruction(DepStore); 253 ++NumFastStores; 254 MadeChange = true; 255 256 // DeleteDeadInstruction can delete the current instruction in loop 257 // cases, reset BBI. 258 BBI = Inst; 259 if (BBI != BB.begin()) 260 --BBI; 261 continue; 262 } 263 } 264 265 if (!isElidable(Inst)) 266 continue; 267 268 // If we're storing the same value back to a pointer that we just 269 // loaded from, then the store can be removed. 270 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 271 if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) { 272 if (SI->getPointerOperand() == DepLoad->getPointerOperand() && 273 SI->getOperand(0) == DepLoad) { 274 // DeleteDeadInstruction can delete the current instruction. Save BBI 275 // in case we need it. 276 WeakVH NextInst(BBI); 277 278 DeleteDeadInstruction(SI); 279 280 if (NextInst == 0) // Next instruction deleted. 281 BBI = BB.begin(); 282 else if (BBI != BB.begin()) // Revisit this instruction if possible. 283 --BBI; 284 ++NumFastStores; 285 MadeChange = true; 286 continue; 287 } 288 } 289 } 290 291 // If this is a lifetime end marker, we can throw away the store. 292 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(InstDep.getInst())) { 293 if (II->getIntrinsicID() == Intrinsic::lifetime_end) { 294 // Delete the store and now-dead instructions that feed it. 295 // DeleteDeadInstruction can delete the current instruction. Save BBI 296 // in case we need it. 297 WeakVH NextInst(BBI); 298 299 DeleteDeadInstruction(Inst); 300 301 if (NextInst == 0) // Next instruction deleted. 302 BBI = BB.begin(); 303 else if (BBI != BB.begin()) // Revisit this instruction if possible. 304 --BBI; 305 ++NumFastStores; 306 MadeChange = true; 307 continue; 308 } 309 } 310 } 311 312 // If this block ends in a return, unwind, or unreachable, all allocas are 313 // dead at its end, which means stores to them are also dead. 314 if (BB.getTerminator()->getNumSuccessors() == 0) 315 MadeChange |= handleEndBlock(BB); 316 317 return MadeChange; 318} 319 320/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose 321/// dependency is a store to a field of that structure. 322bool DSE::handleFreeWithNonTrivialDependency(const CallInst *F, 323 Instruction *Inst, 324 MemDepResult Dep) { 325 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 326 MemoryDependenceAnalysis &MD = getAnalysis<MemoryDependenceAnalysis>(); 327 328 do { 329 Instruction *Dependency = Dep.getInst(); 330 if (!Dependency || !doesClobberMemory(Dependency) || !isElidable(Dependency)) 331 return false; 332 333 Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject(); 334 335 // Check for aliasing. 336 if (AA.alias(F->getArgOperand(0), 1, DepPointer, 1) != 337 AliasAnalysis::MustAlias) 338 return false; 339 340 // DCE instructions only used to calculate that store 341 DeleteDeadInstruction(Dependency); 342 ++NumFastStores; 343 344 // Inst's old Dependency is now deleted. Compute the next dependency, 345 // which may also be dead, as in 346 // s[0] = 0; 347 // s[1] = 0; // This has just been deleted. 348 // free(s); 349 Dep = MD.getDependency(Inst); 350 } while (!Dep.isNonLocal()); 351 return true; 352} 353 354/// handleEndBlock - Remove dead stores to stack-allocated locations in the 355/// function end block. Ex: 356/// %A = alloca i32 357/// ... 358/// store i32 1, i32* %A 359/// ret void 360bool DSE::handleEndBlock(BasicBlock &BB) { 361 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 362 363 bool MadeChange = false; 364 365 // Pointers alloca'd in this function are dead in the end block 366 SmallPtrSet<Value*, 64> deadPointers; 367 368 // Find all of the alloca'd pointers in the entry block. 369 BasicBlock *Entry = BB.getParent()->begin(); 370 for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 371 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 372 deadPointers.insert(AI); 373 374 // Treat byval arguments the same, stores to them are dead at the end of the 375 // function. 376 for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 377 AE = BB.getParent()->arg_end(); AI != AE; ++AI) 378 if (AI->hasByValAttr()) 379 deadPointers.insert(AI); 380 381 // Scan the basic block backwards 382 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 383 --BBI; 384 385 // If we find a store whose pointer is dead. 386 if (doesClobberMemory(BBI)) { 387 if (isElidable(BBI)) { 388 // See through pointer-to-pointer bitcasts 389 Value *pointerOperand = getPointerOperand(BBI)->getUnderlyingObject(); 390 391 // Alloca'd pointers or byval arguments (which are functionally like 392 // alloca's) are valid candidates for removal. 393 if (deadPointers.count(pointerOperand)) { 394 // DCE instructions only used to calculate that store. 395 Instruction *Dead = BBI; 396 ++BBI; 397 DeleteDeadInstruction(Dead, &deadPointers); 398 ++NumFastStores; 399 MadeChange = true; 400 continue; 401 } 402 } 403 404 // Because a memcpy or memmove is also a load, we can't skip it if we 405 // didn't remove it. 406 if (!isa<MemTransferInst>(BBI)) 407 continue; 408 } 409 410 Value *killPointer = 0; 411 uint64_t killPointerSize = AliasAnalysis::UnknownSize; 412 413 // If we encounter a use of the pointer, it is no longer considered dead 414 if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { 415 // However, if this load is unused and not volatile, we can go ahead and 416 // remove it, and not have to worry about it making our pointer undead! 417 if (L->use_empty() && !L->isVolatile()) { 418 ++BBI; 419 DeleteDeadInstruction(L, &deadPointers); 420 ++NumFastOther; 421 MadeChange = true; 422 continue; 423 } 424 425 killPointer = L->getPointerOperand(); 426 } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) { 427 killPointer = V->getOperand(0); 428 } else if (isa<MemTransferInst>(BBI) && 429 isa<ConstantInt>(cast<MemTransferInst>(BBI)->getLength())) { 430 killPointer = cast<MemTransferInst>(BBI)->getSource(); 431 killPointerSize = cast<ConstantInt>( 432 cast<MemTransferInst>(BBI)->getLength())->getZExtValue(); 433 } else if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) { 434 deadPointers.erase(A); 435 436 // Dead alloca's can be DCE'd when we reach them 437 if (A->use_empty()) { 438 ++BBI; 439 DeleteDeadInstruction(A, &deadPointers); 440 ++NumFastOther; 441 MadeChange = true; 442 } 443 444 continue; 445 } else if (CallSite CS = cast<Value>(BBI)) { 446 // If this call does not access memory, it can't 447 // be undeadifying any of our pointers. 448 if (AA.doesNotAccessMemory(CS)) 449 continue; 450 451 unsigned modRef = 0; 452 unsigned other = 0; 453 454 // Remove any pointers made undead by the call from the dead set 455 std::vector<Value*> dead; 456 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 457 E = deadPointers.end(); I != E; ++I) { 458 // HACK: if we detect that our AA is imprecise, it's not 459 // worth it to scan the rest of the deadPointers set. Just 460 // assume that the AA will return ModRef for everything, and 461 // go ahead and bail. 462 if (modRef >= 16 && other == 0) { 463 deadPointers.clear(); 464 return MadeChange; 465 } 466 467 // See if the call site touches it 468 AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, 469 getPointerSize(*I)); 470 471 if (A == AliasAnalysis::ModRef) 472 ++modRef; 473 else 474 ++other; 475 476 if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 477 dead.push_back(*I); 478 } 479 480 for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end(); 481 I != E; ++I) 482 deadPointers.erase(*I); 483 484 continue; 485 } else if (isInstructionTriviallyDead(BBI)) { 486 // For any non-memory-affecting non-terminators, DCE them as we reach them 487 Instruction *Inst = BBI; 488 ++BBI; 489 DeleteDeadInstruction(Inst, &deadPointers); 490 ++NumFastOther; 491 MadeChange = true; 492 continue; 493 } 494 495 if (!killPointer) 496 continue; 497 498 killPointer = killPointer->getUnderlyingObject(); 499 500 // Deal with undead pointers 501 MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI, 502 deadPointers); 503 } 504 505 return MadeChange; 506} 507 508/// RemoveUndeadPointers - check for uses of a pointer that make it 509/// undead when scanning for dead stores to alloca's. 510bool DSE::RemoveUndeadPointers(Value *killPointer, uint64_t killPointerSize, 511 BasicBlock::iterator &BBI, 512 SmallPtrSet<Value*, 64> &deadPointers) { 513 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 514 515 // If the kill pointer can be easily reduced to an alloca, 516 // don't bother doing extraneous AA queries. 517 if (deadPointers.count(killPointer)) { 518 deadPointers.erase(killPointer); 519 return false; 520 } 521 522 // A global can't be in the dead pointer set. 523 if (isa<GlobalValue>(killPointer)) 524 return false; 525 526 bool MadeChange = false; 527 528 SmallVector<Value*, 16> undead; 529 530 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 531 E = deadPointers.end(); I != E; ++I) { 532 // See if this pointer could alias it 533 AliasAnalysis::AliasResult A = AA.alias(*I, getPointerSize(*I), 534 killPointer, killPointerSize); 535 536 // If it must-alias and a store, we can delete it 537 if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { 538 StoreInst *S = cast<StoreInst>(BBI); 539 540 // Remove it! 541 ++BBI; 542 DeleteDeadInstruction(S, &deadPointers); 543 ++NumFastStores; 544 MadeChange = true; 545 546 continue; 547 548 // Otherwise, it is undead 549 } else if (A != AliasAnalysis::NoAlias) 550 undead.push_back(*I); 551 } 552 553 for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end(); 554 I != E; ++I) 555 deadPointers.erase(*I); 556 557 return MadeChange; 558} 559 560/// DeleteDeadInstruction - Delete this instruction. Before we do, go through 561/// and zero out all the operands of this instruction. If any of them become 562/// dead, delete them and the computation tree that feeds them. 563/// 564/// If ValueSet is non-null, remove any deleted instructions from it as well. 565/// 566void DSE::DeleteDeadInstruction(Instruction *I, 567 SmallPtrSet<Value*, 64> *ValueSet) { 568 SmallVector<Instruction*, 32> NowDeadInsts; 569 570 NowDeadInsts.push_back(I); 571 --NumFastOther; 572 573 // Before we touch this instruction, remove it from memdep! 574 MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>(); 575 do { 576 Instruction *DeadInst = NowDeadInsts.pop_back_val(); 577 578 ++NumFastOther; 579 580 // This instruction is dead, zap it, in stages. Start by removing it from 581 // MemDep, which needs to know the operands and needs it to be in the 582 // function. 583 MDA.removeInstruction(DeadInst); 584 585 for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 586 Value *Op = DeadInst->getOperand(op); 587 DeadInst->setOperand(op, 0); 588 589 // If this operand just became dead, add it to the NowDeadInsts list. 590 if (!Op->use_empty()) continue; 591 592 if (Instruction *OpI = dyn_cast<Instruction>(Op)) 593 if (isInstructionTriviallyDead(OpI)) 594 NowDeadInsts.push_back(OpI); 595 } 596 597 DeadInst->eraseFromParent(); 598 599 if (ValueSet) ValueSet->erase(DeadInst); 600 } while (!NowDeadInsts.empty()); 601} 602 603uint64_t DSE::getPointerSize(Value *V) const { 604 if (TD) { 605 if (AllocaInst *A = dyn_cast<AllocaInst>(V)) { 606 // Get size information for the alloca 607 if (ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize())) 608 return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType()); 609 } else { 610 assert(isa<Argument>(V) && "Expected AllocaInst or Argument!"); 611 const PointerType *PT = cast<PointerType>(V->getType()); 612 return TD->getTypeAllocSize(PT->getElementType()); 613 } 614 } 615 return AliasAnalysis::UnknownSize; 616} 617