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