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