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