DeadStoreElimination.cpp revision 184d1ba73866b688cef5f78a214e3fb964b6d833
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 store liveness. 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 we're storing the same value back to a pointer that we just 221 // loaded from, then the store can be removed. 222 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 223 if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) { 224 if (SI->getPointerOperand() == DepLoad->getPointerOperand() && 225 SI->getOperand(0) == DepLoad && !SI->isVolatile()) { 226 // DeleteDeadInstruction can delete the current instruction. Save BBI 227 // in case we need it. 228 WeakVH NextInst(BBI); 229 230 DeleteDeadInstruction(SI); 231 232 if (NextInst == 0) // Next instruction deleted. 233 BBI = BB.begin(); 234 else if (BBI != BB.begin()) // Revisit this instruction if possible. 235 --BBI; 236 ++NumFastStores; 237 MadeChange = true; 238 continue; 239 } 240 } 241 } 242 243 if (!InstDep.isDef()) { 244 // If this is a may-aliased store that is clobbering the store value, we 245 // can keep searching past it for another must-aliased pointer that stores 246 // to the same location. For example, in: 247 // store -> P 248 // store -> Q 249 // store -> P 250 // we can remove the first store to P even though we don't know if P and Q 251 // alias. 252 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 253 AliasAnalysis::Location Loc = 254 getAnalysis<AliasAnalysis>().getLocation(SI); 255 while (InstDep.isClobber() && isa<StoreInst>(InstDep.getInst()) && 256 InstDep.getInst() != &BB.front()) 257 InstDep = MD.getPointerDependencyFrom(Loc, false, InstDep.getInst(), 258 &BB); 259 } 260 } 261 262 // If this is a store-store dependence, then the previous store is dead so 263 // long as this store is at least as big as it. 264 if (InstDep.isDef() && doesClobberMemory(InstDep.getInst())) { 265 Instruction *DepStore = InstDep.getInst(); 266 if (isStoreAtLeastAsWideAs(Inst, DepStore, TD) && isElidable(DepStore)) { 267 // Delete the store and now-dead instructions that feed it. 268 DeleteDeadInstruction(DepStore); 269 ++NumFastStores; 270 MadeChange = true; 271 272 // DeleteDeadInstruction can delete the current instruction in loop 273 // cases, reset BBI. 274 BBI = Inst; 275 if (BBI != BB.begin()) 276 --BBI; 277 continue; 278 } 279 } 280 } 281 282 // If this block ends in a return, unwind, or unreachable, all allocas are 283 // dead at its end, which means stores to them are also dead. 284 if (BB.getTerminator()->getNumSuccessors() == 0) 285 MadeChange |= handleEndBlock(BB); 286 287 return MadeChange; 288} 289 290/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose 291/// dependency is a store to a field of that structure. 292bool DSE::handleFreeWithNonTrivialDependency(const CallInst *F, 293 Instruction *Inst, 294 MemDepResult Dep) { 295 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 296 MemoryDependenceAnalysis &MD = getAnalysis<MemoryDependenceAnalysis>(); 297 298 do { 299 Instruction *Dependency = Dep.getInst(); 300 if (!Dependency || !doesClobberMemory(Dependency) || !isElidable(Dependency)) 301 return false; 302 303 Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject(); 304 305 // Check for aliasing. 306 if (AA.alias(F->getArgOperand(0), 1, DepPointer, 1) != 307 AliasAnalysis::MustAlias) 308 return false; 309 310 // DCE instructions only used to calculate that store 311 DeleteDeadInstruction(Dependency); 312 ++NumFastStores; 313 314 // Inst's old Dependency is now deleted. Compute the next dependency, 315 // which may also be dead, as in 316 // s[0] = 0; 317 // s[1] = 0; // This has just been deleted. 318 // free(s); 319 Dep = MD.getDependency(Inst); 320 } while (!Dep.isNonLocal()); 321 return true; 322} 323 324/// handleEndBlock - Remove dead stores to stack-allocated locations in the 325/// function end block. Ex: 326/// %A = alloca i32 327/// ... 328/// store i32 1, i32* %A 329/// ret void 330bool DSE::handleEndBlock(BasicBlock &BB) { 331 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 332 333 bool MadeChange = false; 334 335 // Pointers alloca'd in this function are dead in the end block 336 SmallPtrSet<Value*, 64> deadPointers; 337 338 // Find all of the alloca'd pointers in the entry block. 339 BasicBlock *Entry = BB.getParent()->begin(); 340 for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 341 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 342 deadPointers.insert(AI); 343 344 // Treat byval arguments the same, stores to them are dead at the end of the 345 // function. 346 for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 347 AE = BB.getParent()->arg_end(); AI != AE; ++AI) 348 if (AI->hasByValAttr()) 349 deadPointers.insert(AI); 350 351 // Scan the basic block backwards 352 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 353 --BBI; 354 355 // If we find a store whose pointer is dead. 356 if (doesClobberMemory(BBI)) { 357 if (isElidable(BBI)) { 358 // See through pointer-to-pointer bitcasts 359 Value *pointerOperand = getPointerOperand(BBI)->getUnderlyingObject(); 360 361 // Alloca'd pointers or byval arguments (which are functionally like 362 // alloca's) are valid candidates for removal. 363 if (deadPointers.count(pointerOperand)) { 364 // DCE instructions only used to calculate that store. 365 Instruction *Dead = BBI; 366 ++BBI; 367 DeleteDeadInstruction(Dead, &deadPointers); 368 ++NumFastStores; 369 MadeChange = true; 370 continue; 371 } 372 } 373 374 // Because a memcpy or memmove is also a load, we can't skip it if we 375 // didn't remove it. 376 if (!isa<MemTransferInst>(BBI)) 377 continue; 378 } 379 380 Value *killPointer = 0; 381 uint64_t killPointerSize = AliasAnalysis::UnknownSize; 382 383 // If we encounter a use of the pointer, it is no longer considered dead 384 if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { 385 // However, if this load is unused and not volatile, we can go ahead and 386 // remove it, and not have to worry about it making our pointer undead! 387 if (L->use_empty() && !L->isVolatile()) { 388 ++BBI; 389 DeleteDeadInstruction(L, &deadPointers); 390 ++NumFastOther; 391 MadeChange = true; 392 continue; 393 } 394 395 killPointer = L->getPointerOperand(); 396 } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) { 397 killPointer = V->getOperand(0); 398 } else if (isa<MemTransferInst>(BBI) && 399 isa<ConstantInt>(cast<MemTransferInst>(BBI)->getLength())) { 400 killPointer = cast<MemTransferInst>(BBI)->getSource(); 401 killPointerSize = cast<ConstantInt>( 402 cast<MemTransferInst>(BBI)->getLength())->getZExtValue(); 403 } else if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) { 404 deadPointers.erase(A); 405 406 // Dead alloca's can be DCE'd when we reach them 407 if (A->use_empty()) { 408 ++BBI; 409 DeleteDeadInstruction(A, &deadPointers); 410 ++NumFastOther; 411 MadeChange = true; 412 } 413 414 continue; 415 } else if (CallSite CS = cast<Value>(BBI)) { 416 // If this call does not access memory, it can't 417 // be undeadifying any of our pointers. 418 if (AA.doesNotAccessMemory(CS)) 419 continue; 420 421 unsigned modRef = 0; 422 unsigned other = 0; 423 424 // Remove any pointers made undead by the call from the dead set 425 std::vector<Value*> dead; 426 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 427 E = deadPointers.end(); I != E; ++I) { 428 // HACK: if we detect that our AA is imprecise, it's not 429 // worth it to scan the rest of the deadPointers set. Just 430 // assume that the AA will return ModRef for everything, and 431 // go ahead and bail. 432 if (modRef >= 16 && other == 0) { 433 deadPointers.clear(); 434 return MadeChange; 435 } 436 437 // See if the call site touches it 438 AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, 439 getPointerSize(*I)); 440 441 if (A == AliasAnalysis::ModRef) 442 ++modRef; 443 else 444 ++other; 445 446 if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 447 dead.push_back(*I); 448 } 449 450 for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end(); 451 I != E; ++I) 452 deadPointers.erase(*I); 453 454 continue; 455 } else if (isInstructionTriviallyDead(BBI)) { 456 // For any non-memory-affecting non-terminators, DCE them as we reach them 457 Instruction *Inst = BBI; 458 ++BBI; 459 DeleteDeadInstruction(Inst, &deadPointers); 460 ++NumFastOther; 461 MadeChange = true; 462 continue; 463 } 464 465 if (!killPointer) 466 continue; 467 468 killPointer = killPointer->getUnderlyingObject(); 469 470 // Deal with undead pointers 471 MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI, 472 deadPointers); 473 } 474 475 return MadeChange; 476} 477 478/// RemoveUndeadPointers - check for uses of a pointer that make it 479/// undead when scanning for dead stores to alloca's. 480bool DSE::RemoveUndeadPointers(Value *killPointer, uint64_t killPointerSize, 481 BasicBlock::iterator &BBI, 482 SmallPtrSet<Value*, 64> &deadPointers) { 483 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 484 485 // If the kill pointer can be easily reduced to an alloca, 486 // don't bother doing extraneous AA queries. 487 if (deadPointers.count(killPointer)) { 488 deadPointers.erase(killPointer); 489 return false; 490 } 491 492 // A global can't be in the dead pointer set. 493 if (isa<GlobalValue>(killPointer)) 494 return false; 495 496 bool MadeChange = false; 497 498 SmallVector<Value*, 16> undead; 499 500 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 501 E = deadPointers.end(); I != E; ++I) { 502 // See if this pointer could alias it 503 AliasAnalysis::AliasResult A = AA.alias(*I, getPointerSize(*I), 504 killPointer, killPointerSize); 505 506 // If it must-alias and a store, we can delete it 507 if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { 508 StoreInst *S = cast<StoreInst>(BBI); 509 510 // Remove it! 511 ++BBI; 512 DeleteDeadInstruction(S, &deadPointers); 513 ++NumFastStores; 514 MadeChange = true; 515 516 continue; 517 518 // Otherwise, it is undead 519 } else if (A != AliasAnalysis::NoAlias) 520 undead.push_back(*I); 521 } 522 523 for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end(); 524 I != E; ++I) 525 deadPointers.erase(*I); 526 527 return MadeChange; 528} 529 530/// DeleteDeadInstruction - Delete this instruction. Before we do, go through 531/// and zero out all the operands of this instruction. If any of them become 532/// dead, delete them and the computation tree that feeds them. 533/// 534/// If ValueSet is non-null, remove any deleted instructions from it as well. 535/// 536void DSE::DeleteDeadInstruction(Instruction *I, 537 SmallPtrSet<Value*, 64> *ValueSet) { 538 SmallVector<Instruction*, 32> NowDeadInsts; 539 540 NowDeadInsts.push_back(I); 541 --NumFastOther; 542 543 // Before we touch this instruction, remove it from memdep! 544 MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>(); 545 do { 546 Instruction *DeadInst = NowDeadInsts.pop_back_val(); 547 548 ++NumFastOther; 549 550 // This instruction is dead, zap it, in stages. Start by removing it from 551 // MemDep, which needs to know the operands and needs it to be in the 552 // function. 553 MDA.removeInstruction(DeadInst); 554 555 for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 556 Value *Op = DeadInst->getOperand(op); 557 DeadInst->setOperand(op, 0); 558 559 // If this operand just became dead, add it to the NowDeadInsts list. 560 if (!Op->use_empty()) continue; 561 562 if (Instruction *OpI = dyn_cast<Instruction>(Op)) 563 if (isInstructionTriviallyDead(OpI)) 564 NowDeadInsts.push_back(OpI); 565 } 566 567 DeadInst->eraseFromParent(); 568 569 if (ValueSet) ValueSet->erase(DeadInst); 570 } while (!NowDeadInsts.empty()); 571} 572 573uint64_t DSE::getPointerSize(Value *V) const { 574 if (TD) { 575 if (AllocaInst *A = dyn_cast<AllocaInst>(V)) { 576 // Get size information for the alloca 577 if (ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize())) 578 return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType()); 579 } else { 580 assert(isa<Argument>(V) && "Expected AllocaInst or Argument!"); 581 const PointerType *PT = cast<PointerType>(V->getType()); 582 return TD->getTypeAllocSize(PT->getElementType()); 583 } 584 } 585 return AliasAnalysis::UnknownSize; 586} 587