DeadStoreElimination.cpp revision b401e3bd16c3d648464606d5e5b496dd61d12afc
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/GlobalVariable.h" 23#include "llvm/Instructions.h" 24#include "llvm/IntrinsicInst.h" 25#include "llvm/Pass.h" 26#include "llvm/Analysis/AliasAnalysis.h" 27#include "llvm/Analysis/CaptureTracking.h" 28#include "llvm/Analysis/Dominators.h" 29#include "llvm/Analysis/MemoryBuiltins.h" 30#include "llvm/Analysis/MemoryDependenceAnalysis.h" 31#include "llvm/Analysis/ValueTracking.h" 32#include "llvm/Target/TargetData.h" 33#include "llvm/Transforms/Utils/Local.h" 34#include "llvm/Support/Debug.h" 35#include "llvm/ADT/SmallPtrSet.h" 36#include "llvm/ADT/Statistic.h" 37#include "llvm/ADT/STLExtras.h" 38using namespace llvm; 39 40STATISTIC(NumFastStores, "Number of stores deleted"); 41STATISTIC(NumFastOther , "Number of other instrs removed"); 42 43namespace { 44 struct DSE : public FunctionPass { 45 AliasAnalysis *AA; 46 MemoryDependenceAnalysis *MD; 47 DominatorTree *DT; 48 49 static char ID; // Pass identification, replacement for typeid 50 DSE() : FunctionPass(ID), AA(0), MD(0), DT(0) { 51 initializeDSEPass(*PassRegistry::getPassRegistry()); 52 } 53 54 virtual bool runOnFunction(Function &F) { 55 AA = &getAnalysis<AliasAnalysis>(); 56 MD = &getAnalysis<MemoryDependenceAnalysis>(); 57 DT = &getAnalysis<DominatorTree>(); 58 59 bool Changed = false; 60 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 61 // Only check non-dead blocks. Dead blocks may have strange pointer 62 // cycles that will confuse alias analysis. 63 if (DT->isReachableFromEntry(I)) 64 Changed |= runOnBasicBlock(*I); 65 66 AA = 0; MD = 0; DT = 0; 67 return Changed; 68 } 69 70 bool runOnBasicBlock(BasicBlock &BB); 71 bool HandleFree(CallInst *F); 72 bool handleEndBlock(BasicBlock &BB); 73 void RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc, 74 SmallPtrSet<Value*, 16> &DeadStackObjects); 75 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//===----------------------------------------------------------------------===// 98// Helper functions 99//===----------------------------------------------------------------------===// 100 101/// DeleteDeadInstruction - Delete this instruction. Before we do, go through 102/// and zero out all the operands of this instruction. If any of them become 103/// dead, delete them and the computation tree that feeds them. 104/// 105/// If ValueSet is non-null, remove any deleted instructions from it as well. 106/// 107static void DeleteDeadInstruction(Instruction *I, 108 MemoryDependenceAnalysis &MD, 109 SmallPtrSet<Value*, 16> *ValueSet = 0) { 110 SmallVector<Instruction*, 32> NowDeadInsts; 111 112 NowDeadInsts.push_back(I); 113 --NumFastOther; 114 115 // Before we touch this instruction, remove it from memdep! 116 do { 117 Instruction *DeadInst = NowDeadInsts.pop_back_val(); 118 ++NumFastOther; 119 120 // This instruction is dead, zap it, in stages. Start by removing it from 121 // MemDep, which needs to know the operands and needs it to be in the 122 // function. 123 MD.removeInstruction(DeadInst); 124 125 for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 126 Value *Op = DeadInst->getOperand(op); 127 DeadInst->setOperand(op, 0); 128 129 // If this operand just became dead, add it to the NowDeadInsts list. 130 if (!Op->use_empty()) continue; 131 132 if (Instruction *OpI = dyn_cast<Instruction>(Op)) 133 if (isInstructionTriviallyDead(OpI)) 134 NowDeadInsts.push_back(OpI); 135 } 136 137 DeadInst->eraseFromParent(); 138 139 if (ValueSet) ValueSet->erase(DeadInst); 140 } while (!NowDeadInsts.empty()); 141} 142 143 144/// hasMemoryWrite - Does this instruction write some memory? This only returns 145/// true for things that we can analyze with other helpers below. 146static bool hasMemoryWrite(Instruction *I) { 147 if (isa<StoreInst>(I)) 148 return true; 149 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { 150 switch (II->getIntrinsicID()) { 151 default: 152 return false; 153 case Intrinsic::memset: 154 case Intrinsic::memmove: 155 case Intrinsic::memcpy: 156 case Intrinsic::init_trampoline: 157 case Intrinsic::lifetime_end: 158 return true; 159 } 160 } 161 return false; 162} 163 164/// getLocForWrite - Return a Location stored to by the specified instruction. 165/// If isRemovable returns true, this function and getLocForRead completely 166/// describe the memory operations for this instruction. 167static AliasAnalysis::Location 168getLocForWrite(Instruction *Inst, AliasAnalysis &AA) { 169 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) 170 return AA.getLocation(SI); 171 172 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) { 173 // memcpy/memmove/memset. 174 AliasAnalysis::Location Loc = AA.getLocationForDest(MI); 175 // If we don't have target data around, an unknown size in Location means 176 // that we should use the size of the pointee type. This isn't valid for 177 // memset/memcpy, which writes more than an i8. 178 if (Loc.Size == AliasAnalysis::UnknownSize && AA.getTargetData() == 0) 179 return AliasAnalysis::Location(); 180 return Loc; 181 } 182 183 IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst); 184 if (II == 0) return AliasAnalysis::Location(); 185 186 switch (II->getIntrinsicID()) { 187 default: return AliasAnalysis::Location(); // Unhandled intrinsic. 188 case Intrinsic::init_trampoline: 189 // If we don't have target data around, an unknown size in Location means 190 // that we should use the size of the pointee type. This isn't valid for 191 // init.trampoline, which writes more than an i8. 192 if (AA.getTargetData() == 0) return AliasAnalysis::Location(); 193 194 // FIXME: We don't know the size of the trampoline, so we can't really 195 // handle it here. 196 return AliasAnalysis::Location(II->getArgOperand(0)); 197 case Intrinsic::lifetime_end: { 198 uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue(); 199 return AliasAnalysis::Location(II->getArgOperand(1), Len); 200 } 201 } 202} 203 204/// getLocForRead - Return the location read by the specified "hasMemoryWrite" 205/// instruction if any. 206static AliasAnalysis::Location 207getLocForRead(Instruction *Inst, AliasAnalysis &AA) { 208 assert(hasMemoryWrite(Inst) && "Unknown instruction case"); 209 210 // The only instructions that both read and write are the mem transfer 211 // instructions (memcpy/memmove). 212 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(Inst)) 213 return AA.getLocationForSource(MTI); 214 return AliasAnalysis::Location(); 215} 216 217 218/// isRemovable - If the value of this instruction and the memory it writes to 219/// is unused, may we delete this instruction? 220static bool isRemovable(Instruction *I) { 221 // Don't remove volatile/atomic stores. 222 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 223 return SI->isUnordered(); 224 225 IntrinsicInst *II = cast<IntrinsicInst>(I); 226 switch (II->getIntrinsicID()) { 227 default: llvm_unreachable("doesn't pass 'hasMemoryWrite' predicate"); 228 case Intrinsic::lifetime_end: 229 // Never remove dead lifetime_end's, e.g. because it is followed by a 230 // free. 231 return false; 232 case Intrinsic::init_trampoline: 233 // Always safe to remove init_trampoline. 234 return true; 235 236 case Intrinsic::memset: 237 case Intrinsic::memmove: 238 case Intrinsic::memcpy: 239 // Don't remove volatile memory intrinsics. 240 return !cast<MemIntrinsic>(II)->isVolatile(); 241 } 242} 243 244 245/// isShortenable - Returns true if this instruction can be safely shortened in 246/// length. 247static bool isShortenable(Instruction *I) { 248 // Don't shorten stores for now 249 if (isa<StoreInst>(I)) 250 return false; 251 252 IntrinsicInst *II = cast<IntrinsicInst>(I); 253 switch (II->getIntrinsicID()) { 254 default: return false; 255 case Intrinsic::memset: 256 case Intrinsic::memcpy: 257 // Do shorten memory intrinsics. 258 return true; 259 } 260} 261 262/// getStoredPointerOperand - Return the pointer that is being written to. 263static Value *getStoredPointerOperand(Instruction *I) { 264 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 265 return SI->getPointerOperand(); 266 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) 267 return MI->getDest(); 268 269 IntrinsicInst *II = cast<IntrinsicInst>(I); 270 switch (II->getIntrinsicID()) { 271 default: llvm_unreachable("Unexpected intrinsic!"); 272 case Intrinsic::init_trampoline: 273 return II->getArgOperand(0); 274 } 275} 276 277static uint64_t getPointerSize(const Value *V, AliasAnalysis &AA) { 278 const TargetData *TD = AA.getTargetData(); 279 280 if (const CallInst *CI = extractMallocCall(V)) { 281 if (const ConstantInt *C = dyn_cast<ConstantInt>(CI->getArgOperand(0))) 282 return C->getZExtValue(); 283 } 284 285 if (const CallInst *CI = extractCallocCall(V)) { 286 if (const ConstantInt *C1 = dyn_cast<ConstantInt>(CI->getArgOperand(0))) 287 if (const ConstantInt *C2 = dyn_cast<ConstantInt>(CI->getArgOperand(1))) 288 return (C1->getValue() * C2->getValue()).getZExtValue(); 289 } 290 291 if (TD == 0) 292 return AliasAnalysis::UnknownSize; 293 294 if (const AllocaInst *A = dyn_cast<AllocaInst>(V)) { 295 // Get size information for the alloca 296 if (const ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize())) 297 return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType()); 298 } 299 300 if (const Argument *A = dyn_cast<Argument>(V)) { 301 if (A->hasByValAttr()) 302 if (PointerType *PT = dyn_cast<PointerType>(A->getType())) 303 return TD->getTypeAllocSize(PT->getElementType()); 304 } 305 306 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 307 if (!GV->mayBeOverridden()) 308 return TD->getTypeAllocSize(GV->getType()->getElementType()); 309 } 310 311 return AliasAnalysis::UnknownSize; 312} 313 314namespace { 315 enum OverwriteResult 316 { 317 OverwriteComplete, 318 OverwriteEnd, 319 OverwriteUnknown 320 }; 321} 322 323/// isOverwrite - Return 'OverwriteComplete' if a store to the 'Later' location 324/// completely overwrites a store to the 'Earlier' location. 325/// 'OverwriteEnd' if the end of the 'Earlier' location is completely 326/// overwritten by 'Later', or 'OverwriteUnknown' if nothing can be determined 327static OverwriteResult isOverwrite(const AliasAnalysis::Location &Later, 328 const AliasAnalysis::Location &Earlier, 329 AliasAnalysis &AA, 330 int64_t &EarlierOff, 331 int64_t &LaterOff) { 332 const Value *P1 = Earlier.Ptr->stripPointerCasts(); 333 const Value *P2 = Later.Ptr->stripPointerCasts(); 334 335 // If the start pointers are the same, we just have to compare sizes to see if 336 // the later store was larger than the earlier store. 337 if (P1 == P2) { 338 // If we don't know the sizes of either access, then we can't do a 339 // comparison. 340 if (Later.Size == AliasAnalysis::UnknownSize || 341 Earlier.Size == AliasAnalysis::UnknownSize) { 342 // If we have no TargetData information around, then the size of the store 343 // is inferrable from the pointee type. If they are the same type, then 344 // we know that the store is safe. 345 if (AA.getTargetData() == 0 && 346 Later.Ptr->getType() == Earlier.Ptr->getType()) 347 return OverwriteComplete; 348 349 return OverwriteUnknown; 350 } 351 352 // Make sure that the Later size is >= the Earlier size. 353 if (Later.Size >= Earlier.Size) 354 return OverwriteComplete; 355 } 356 357 // Otherwise, we have to have size information, and the later store has to be 358 // larger than the earlier one. 359 if (Later.Size == AliasAnalysis::UnknownSize || 360 Earlier.Size == AliasAnalysis::UnknownSize || 361 AA.getTargetData() == 0) 362 return OverwriteUnknown; 363 364 // Check to see if the later store is to the entire object (either a global, 365 // an alloca, or a byval argument). If so, then it clearly overwrites any 366 // other store to the same object. 367 const TargetData &TD = *AA.getTargetData(); 368 369 const Value *UO1 = GetUnderlyingObject(P1, &TD), 370 *UO2 = GetUnderlyingObject(P2, &TD); 371 372 // If we can't resolve the same pointers to the same object, then we can't 373 // analyze them at all. 374 if (UO1 != UO2) 375 return OverwriteUnknown; 376 377 // If the "Later" store is to a recognizable object, get its size. 378 uint64_t ObjectSize = getPointerSize(UO2, AA); 379 if (ObjectSize != AliasAnalysis::UnknownSize) 380 if (ObjectSize == Later.Size && ObjectSize >= Earlier.Size) 381 return OverwriteComplete; 382 383 // Okay, we have stores to two completely different pointers. Try to 384 // decompose the pointer into a "base + constant_offset" form. If the base 385 // pointers are equal, then we can reason about the two stores. 386 EarlierOff = 0; 387 LaterOff = 0; 388 const Value *BP1 = GetPointerBaseWithConstantOffset(P1, EarlierOff, TD); 389 const Value *BP2 = GetPointerBaseWithConstantOffset(P2, LaterOff, TD); 390 391 // If the base pointers still differ, we have two completely different stores. 392 if (BP1 != BP2) 393 return OverwriteUnknown; 394 395 // The later store completely overlaps the earlier store if: 396 // 397 // 1. Both start at the same offset and the later one's size is greater than 398 // or equal to the earlier one's, or 399 // 400 // |--earlier--| 401 // |-- later --| 402 // 403 // 2. The earlier store has an offset greater than the later offset, but which 404 // still lies completely within the later store. 405 // 406 // |--earlier--| 407 // |----- later ------| 408 // 409 // We have to be careful here as *Off is signed while *.Size is unsigned. 410 if (EarlierOff >= LaterOff && 411 Later.Size > Earlier.Size && 412 uint64_t(EarlierOff - LaterOff) + Earlier.Size <= Later.Size) 413 return OverwriteComplete; 414 415 // The other interesting case is if the later store overwrites the end of 416 // the earlier store 417 // 418 // |--earlier--| 419 // |-- later --| 420 // 421 // In this case we may want to trim the size of earlier to avoid generating 422 // writes to addresses which will definitely be overwritten later 423 if (LaterOff > EarlierOff && 424 LaterOff < int64_t(EarlierOff + Earlier.Size) && 425 int64_t(LaterOff + Later.Size) >= int64_t(EarlierOff + Earlier.Size)) 426 return OverwriteEnd; 427 428 // Otherwise, they don't completely overlap. 429 return OverwriteUnknown; 430} 431 432/// isPossibleSelfRead - If 'Inst' might be a self read (i.e. a noop copy of a 433/// memory region into an identical pointer) then it doesn't actually make its 434/// input dead in the traditional sense. Consider this case: 435/// 436/// memcpy(A <- B) 437/// memcpy(A <- A) 438/// 439/// In this case, the second store to A does not make the first store to A dead. 440/// The usual situation isn't an explicit A<-A store like this (which can be 441/// trivially removed) but a case where two pointers may alias. 442/// 443/// This function detects when it is unsafe to remove a dependent instruction 444/// because the DSE inducing instruction may be a self-read. 445static bool isPossibleSelfRead(Instruction *Inst, 446 const AliasAnalysis::Location &InstStoreLoc, 447 Instruction *DepWrite, AliasAnalysis &AA) { 448 // Self reads can only happen for instructions that read memory. Get the 449 // location read. 450 AliasAnalysis::Location InstReadLoc = getLocForRead(Inst, AA); 451 if (InstReadLoc.Ptr == 0) return false; // Not a reading instruction. 452 453 // If the read and written loc obviously don't alias, it isn't a read. 454 if (AA.isNoAlias(InstReadLoc, InstStoreLoc)) return false; 455 456 // Okay, 'Inst' may copy over itself. However, we can still remove a the 457 // DepWrite instruction if we can prove that it reads from the same location 458 // as Inst. This handles useful cases like: 459 // memcpy(A <- B) 460 // memcpy(A <- B) 461 // Here we don't know if A/B may alias, but we do know that B/B are must 462 // aliases, so removing the first memcpy is safe (assuming it writes <= # 463 // bytes as the second one. 464 AliasAnalysis::Location DepReadLoc = getLocForRead(DepWrite, AA); 465 466 if (DepReadLoc.Ptr && AA.isMustAlias(InstReadLoc.Ptr, DepReadLoc.Ptr)) 467 return false; 468 469 // If DepWrite doesn't read memory or if we can't prove it is a must alias, 470 // then it can't be considered dead. 471 return true; 472} 473 474 475//===----------------------------------------------------------------------===// 476// DSE Pass 477//===----------------------------------------------------------------------===// 478 479bool DSE::runOnBasicBlock(BasicBlock &BB) { 480 bool MadeChange = false; 481 482 // Do a top-down walk on the BB. 483 for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { 484 Instruction *Inst = BBI++; 485 486 // Handle 'free' calls specially. 487 if (CallInst *F = isFreeCall(Inst)) { 488 MadeChange |= HandleFree(F); 489 continue; 490 } 491 492 // If we find something that writes memory, get its memory dependence. 493 if (!hasMemoryWrite(Inst)) 494 continue; 495 496 MemDepResult InstDep = MD->getDependency(Inst); 497 498 // Ignore any store where we can't find a local dependence. 499 // FIXME: cross-block DSE would be fun. :) 500 if (!InstDep.isDef() && !InstDep.isClobber()) 501 continue; 502 503 // If we're storing the same value back to a pointer that we just 504 // loaded from, then the store can be removed. 505 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { 506 if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) { 507 if (SI->getPointerOperand() == DepLoad->getPointerOperand() && 508 SI->getOperand(0) == DepLoad && isRemovable(SI)) { 509 DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n " 510 << "LOAD: " << *DepLoad << "\n STORE: " << *SI << '\n'); 511 512 // DeleteDeadInstruction can delete the current instruction. Save BBI 513 // in case we need it. 514 WeakVH NextInst(BBI); 515 516 DeleteDeadInstruction(SI, *MD); 517 518 if (NextInst == 0) // Next instruction deleted. 519 BBI = BB.begin(); 520 else if (BBI != BB.begin()) // Revisit this instruction if possible. 521 --BBI; 522 ++NumFastStores; 523 MadeChange = true; 524 continue; 525 } 526 } 527 } 528 529 // Figure out what location is being stored to. 530 AliasAnalysis::Location Loc = getLocForWrite(Inst, *AA); 531 532 // If we didn't get a useful location, fail. 533 if (Loc.Ptr == 0) 534 continue; 535 536 while (InstDep.isDef() || InstDep.isClobber()) { 537 // Get the memory clobbered by the instruction we depend on. MemDep will 538 // skip any instructions that 'Loc' clearly doesn't interact with. If we 539 // end up depending on a may- or must-aliased load, then we can't optimize 540 // away the store and we bail out. However, if we depend on on something 541 // that overwrites the memory location we *can* potentially optimize it. 542 // 543 // Find out what memory location the dependent instruction stores. 544 Instruction *DepWrite = InstDep.getInst(); 545 AliasAnalysis::Location DepLoc = getLocForWrite(DepWrite, *AA); 546 // If we didn't get a useful location, or if it isn't a size, bail out. 547 if (DepLoc.Ptr == 0) 548 break; 549 550 // If we find a write that is a) removable (i.e., non-volatile), b) is 551 // completely obliterated by the store to 'Loc', and c) which we know that 552 // 'Inst' doesn't load from, then we can remove it. 553 if (isRemovable(DepWrite) && 554 !isPossibleSelfRead(Inst, Loc, DepWrite, *AA)) { 555 int64_t InstWriteOffset, DepWriteOffset; 556 OverwriteResult OR = isOverwrite(Loc, DepLoc, *AA, 557 DepWriteOffset, InstWriteOffset); 558 if (OR == OverwriteComplete) { 559 DEBUG(dbgs() << "DSE: Remove Dead Store:\n DEAD: " 560 << *DepWrite << "\n KILLER: " << *Inst << '\n'); 561 562 // Delete the store and now-dead instructions that feed it. 563 DeleteDeadInstruction(DepWrite, *MD); 564 ++NumFastStores; 565 MadeChange = true; 566 567 // DeleteDeadInstruction can delete the current instruction in loop 568 // cases, reset BBI. 569 BBI = Inst; 570 if (BBI != BB.begin()) 571 --BBI; 572 break; 573 } else if (OR == OverwriteEnd && isShortenable(DepWrite)) { 574 // TODO: base this on the target vector size so that if the earlier 575 // store was too small to get vector writes anyway then its likely 576 // a good idea to shorten it 577 // Power of 2 vector writes are probably always a bad idea to optimize 578 // as any store/memset/memcpy is likely using vector instructions so 579 // shortening it to not vector size is likely to be slower 580 MemIntrinsic* DepIntrinsic = cast<MemIntrinsic>(DepWrite); 581 unsigned DepWriteAlign = DepIntrinsic->getAlignment(); 582 if (llvm::isPowerOf2_64(InstWriteOffset) || 583 ((DepWriteAlign != 0) && InstWriteOffset % DepWriteAlign == 0)) { 584 585 DEBUG(dbgs() << "DSE: Remove Dead Store:\n OW END: " 586 << *DepWrite << "\n KILLER (offset " 587 << InstWriteOffset << ", " 588 << DepLoc.Size << ")" 589 << *Inst << '\n'); 590 591 Value* DepWriteLength = DepIntrinsic->getLength(); 592 Value* TrimmedLength = ConstantInt::get(DepWriteLength->getType(), 593 InstWriteOffset - 594 DepWriteOffset); 595 DepIntrinsic->setLength(TrimmedLength); 596 MadeChange = true; 597 } 598 } 599 } 600 601 // If this is a may-aliased store that is clobbering the store value, we 602 // can keep searching past it for another must-aliased pointer that stores 603 // to the same location. For example, in: 604 // store -> P 605 // store -> Q 606 // store -> P 607 // we can remove the first store to P even though we don't know if P and Q 608 // alias. 609 if (DepWrite == &BB.front()) break; 610 611 // Can't look past this instruction if it might read 'Loc'. 612 if (AA->getModRefInfo(DepWrite, Loc) & AliasAnalysis::Ref) 613 break; 614 615 InstDep = MD->getPointerDependencyFrom(Loc, false, DepWrite, &BB); 616 } 617 } 618 619 // If this block ends in a return, unwind, or unreachable, all allocas are 620 // dead at its end, which means stores to them are also dead. 621 if (BB.getTerminator()->getNumSuccessors() == 0) 622 MadeChange |= handleEndBlock(BB); 623 624 return MadeChange; 625} 626 627/// Find all blocks that will unconditionally lead to the block BB and append 628/// them to F. 629static void FindUnconditionalPreds(SmallVectorImpl<BasicBlock *> &Blocks, 630 BasicBlock *BB, DominatorTree *DT) { 631 for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I) { 632 BasicBlock *Pred = *I; 633 if (Pred == BB) continue; 634 TerminatorInst *PredTI = Pred->getTerminator(); 635 if (PredTI->getNumSuccessors() != 1) 636 continue; 637 638 if (DT->isReachableFromEntry(Pred)) 639 Blocks.push_back(Pred); 640 } 641} 642 643/// HandleFree - Handle frees of entire structures whose dependency is a store 644/// to a field of that structure. 645bool DSE::HandleFree(CallInst *F) { 646 bool MadeChange = false; 647 648 AliasAnalysis::Location Loc = AliasAnalysis::Location(F->getOperand(0)); 649 SmallVector<BasicBlock *, 16> Blocks; 650 Blocks.push_back(F->getParent()); 651 652 while (!Blocks.empty()) { 653 BasicBlock *BB = Blocks.pop_back_val(); 654 Instruction *InstPt = BB->getTerminator(); 655 if (BB == F->getParent()) InstPt = F; 656 657 MemDepResult Dep = MD->getPointerDependencyFrom(Loc, false, InstPt, BB); 658 while (Dep.isDef() || Dep.isClobber()) { 659 Instruction *Dependency = Dep.getInst(); 660 if (!hasMemoryWrite(Dependency) || !isRemovable(Dependency)) 661 break; 662 663 Value *DepPointer = 664 GetUnderlyingObject(getStoredPointerOperand(Dependency)); 665 666 // Check for aliasing. 667 if (!AA->isMustAlias(F->getArgOperand(0), DepPointer)) 668 break; 669 670 Instruction *Next = llvm::next(BasicBlock::iterator(Dependency)); 671 672 // DCE instructions only used to calculate that store 673 DeleteDeadInstruction(Dependency, *MD); 674 ++NumFastStores; 675 MadeChange = true; 676 677 // Inst's old Dependency is now deleted. Compute the next dependency, 678 // which may also be dead, as in 679 // s[0] = 0; 680 // s[1] = 0; // This has just been deleted. 681 // free(s); 682 Dep = MD->getPointerDependencyFrom(Loc, false, Next, BB); 683 } 684 685 if (Dep.isNonLocal()) 686 FindUnconditionalPreds(Blocks, BB, DT); 687 } 688 689 return MadeChange; 690} 691 692/// handleEndBlock - Remove dead stores to stack-allocated locations in the 693/// function end block. Ex: 694/// %A = alloca i32 695/// ... 696/// store i32 1, i32* %A 697/// ret void 698bool DSE::handleEndBlock(BasicBlock &BB) { 699 bool MadeChange = false; 700 701 // Keep track of all of the stack objects that are dead at the end of the 702 // function. 703 SmallPtrSet<Value*, 16> DeadStackObjects; 704 705 // Find all of the alloca'd pointers in the entry block. 706 BasicBlock *Entry = BB.getParent()->begin(); 707 for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) { 708 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 709 DeadStackObjects.insert(AI); 710 711 // Okay, so these are dead heap objects, but if the pointer never escapes 712 // then it's leaked by this function anyways. 713 CallInst *CI = extractMallocCall(I); 714 if (!CI) 715 CI = extractCallocCall(I); 716 if (CI && !PointerMayBeCaptured(CI, true, true)) 717 DeadStackObjects.insert(CI); 718 } 719 720 // Treat byval arguments the same, stores to them are dead at the end of the 721 // function. 722 for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 723 AE = BB.getParent()->arg_end(); AI != AE; ++AI) 724 if (AI->hasByValAttr()) 725 DeadStackObjects.insert(AI); 726 727 // Scan the basic block backwards 728 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 729 --BBI; 730 731 // If we find a store, check to see if it points into a dead stack value. 732 if (hasMemoryWrite(BBI) && isRemovable(BBI)) { 733 // See through pointer-to-pointer bitcasts 734 SmallVector<Value *, 4> Pointers; 735 GetUnderlyingObjects(getStoredPointerOperand(BBI), Pointers); 736 737 // Stores to stack values are valid candidates for removal. 738 bool AllDead = true; 739 for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(), 740 E = Pointers.end(); I != E; ++I) 741 if (!DeadStackObjects.count(*I)) { 742 AllDead = false; 743 break; 744 } 745 746 if (AllDead) { 747 Instruction *Dead = BBI++; 748 749 DEBUG(dbgs() << "DSE: Dead Store at End of Block:\n DEAD: " 750 << *Dead << "\n Objects: "; 751 for (SmallVectorImpl<Value *>::iterator I = Pointers.begin(), 752 E = Pointers.end(); I != E; ++I) { 753 dbgs() << **I; 754 if (llvm::next(I) != E) 755 dbgs() << ", "; 756 } 757 dbgs() << '\n'); 758 759 // DCE instructions only used to calculate that store. 760 DeleteDeadInstruction(Dead, *MD, &DeadStackObjects); 761 ++NumFastStores; 762 MadeChange = true; 763 continue; 764 } 765 } 766 767 // Remove any dead non-memory-mutating instructions. 768 if (isInstructionTriviallyDead(BBI)) { 769 Instruction *Inst = BBI++; 770 DeleteDeadInstruction(Inst, *MD, &DeadStackObjects); 771 ++NumFastOther; 772 MadeChange = true; 773 continue; 774 } 775 776 if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) { 777 DeadStackObjects.erase(A); 778 continue; 779 } 780 781 if (CallInst *CI = extractMallocCall(BBI)) { 782 DeadStackObjects.erase(CI); 783 continue; 784 } 785 786 if (CallInst *CI = extractCallocCall(BBI)) { 787 DeadStackObjects.erase(CI); 788 continue; 789 } 790 791 if (CallSite CS = cast<Value>(BBI)) { 792 // If this call does not access memory, it can't be loading any of our 793 // pointers. 794 if (AA->doesNotAccessMemory(CS)) 795 continue; 796 797 // If the call might load from any of our allocas, then any store above 798 // the call is live. 799 SmallVector<Value*, 8> LiveAllocas; 800 for (SmallPtrSet<Value*, 16>::iterator I = DeadStackObjects.begin(), 801 E = DeadStackObjects.end(); I != E; ++I) { 802 // See if the call site touches it. 803 AliasAnalysis::ModRefResult A = 804 AA->getModRefInfo(CS, *I, getPointerSize(*I, *AA)); 805 806 if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 807 LiveAllocas.push_back(*I); 808 } 809 810 for (SmallVector<Value*, 8>::iterator I = LiveAllocas.begin(), 811 E = LiveAllocas.end(); I != E; ++I) 812 DeadStackObjects.erase(*I); 813 814 // If all of the allocas were clobbered by the call then we're not going 815 // to find anything else to process. 816 if (DeadStackObjects.empty()) 817 return MadeChange; 818 819 continue; 820 } 821 822 AliasAnalysis::Location LoadedLoc; 823 824 // If we encounter a use of the pointer, it is no longer considered dead 825 if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { 826 if (!L->isUnordered()) // Be conservative with atomic/volatile load 827 break; 828 LoadedLoc = AA->getLocation(L); 829 } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) { 830 LoadedLoc = AA->getLocation(V); 831 } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) { 832 LoadedLoc = AA->getLocationForSource(MTI); 833 } else if (!BBI->mayReadFromMemory()) { 834 // Instruction doesn't read memory. Note that stores that weren't removed 835 // above will hit this case. 836 continue; 837 } else { 838 // Unknown inst; assume it clobbers everything. 839 break; 840 } 841 842 // Remove any allocas from the DeadPointer set that are loaded, as this 843 // makes any stores above the access live. 844 RemoveAccessedObjects(LoadedLoc, DeadStackObjects); 845 846 // If all of the allocas were clobbered by the access then we're not going 847 // to find anything else to process. 848 if (DeadStackObjects.empty()) 849 break; 850 } 851 852 return MadeChange; 853} 854 855/// RemoveAccessedObjects - Check to see if the specified location may alias any 856/// of the stack objects in the DeadStackObjects set. If so, they become live 857/// because the location is being loaded. 858void DSE::RemoveAccessedObjects(const AliasAnalysis::Location &LoadedLoc, 859 SmallPtrSet<Value*, 16> &DeadStackObjects) { 860 const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr); 861 862 // A constant can't be in the dead pointer set. 863 if (isa<Constant>(UnderlyingPointer)) 864 return; 865 866 // If the kill pointer can be easily reduced to an alloca, don't bother doing 867 // extraneous AA queries. 868 if (isa<AllocaInst>(UnderlyingPointer) || isa<Argument>(UnderlyingPointer)) { 869 DeadStackObjects.erase(const_cast<Value*>(UnderlyingPointer)); 870 return; 871 } 872 873 SmallVector<Value*, 16> NowLive; 874 for (SmallPtrSet<Value*, 16>::iterator I = DeadStackObjects.begin(), 875 E = DeadStackObjects.end(); I != E; ++I) { 876 // See if the loaded location could alias the stack location. 877 AliasAnalysis::Location StackLoc(*I, getPointerSize(*I, *AA)); 878 if (!AA->isNoAlias(StackLoc, LoadedLoc)) 879 NowLive.push_back(*I); 880 } 881 882 for (SmallVector<Value*, 16>::iterator I = NowLive.begin(), E = NowLive.end(); 883 I != E; ++I) 884 DeadStackObjects.erase(*I); 885} 886