DeadStoreElimination.cpp revision 772601a8850808a66270372164941e373074493d
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/SetVector.h" 26#include "llvm/ADT/SmallPtrSet.h" 27#include "llvm/ADT/Statistic.h" 28#include "llvm/Analysis/AliasAnalysis.h" 29#include "llvm/Analysis/MemoryDependenceAnalysis.h" 30#include "llvm/Target/TargetData.h" 31#include "llvm/Transforms/Utils/Local.h" 32#include "llvm/Support/Compiler.h" 33using namespace llvm; 34 35STATISTIC(NumFastStores, "Number of stores deleted"); 36STATISTIC(NumFastOther , "Number of other instrs removed"); 37 38namespace { 39 struct VISIBILITY_HIDDEN DSE : public FunctionPass { 40 static char ID; // Pass identification, replacement for typeid 41 DSE() : FunctionPass((intptr_t)&ID) {} 42 43 virtual bool runOnFunction(Function &F) { 44 bool Changed = false; 45 for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) 46 Changed |= runOnBasicBlock(*I); 47 return Changed; 48 } 49 50 bool runOnBasicBlock(BasicBlock &BB); 51 bool handleFreeWithNonTrivialDependency(FreeInst* F, 52 Instruction* dependency, 53 SetVector<Instruction*>& possiblyDead); 54 bool handleEndBlock(BasicBlock& BB, SetVector<Instruction*>& possiblyDead); 55 bool RemoveUndeadPointers(Value* pointer, 56 BasicBlock::iterator& BBI, 57 SmallPtrSet<Value*, 64>& deadPointers, 58 SetVector<Instruction*>& possiblyDead); 59 void DeleteDeadInstructionChains(Instruction *I, 60 SetVector<Instruction*> &DeadInsts); 61 62 /// Find the base pointer that a pointer came from 63 /// Because this is used to find pointers that originate 64 /// from allocas, it is safe to ignore GEP indices, since 65 /// either the store will be in the alloca, and thus dead, 66 /// or beyond the end of the alloca, and thus undefined. 67 void TranslatePointerBitCasts(Value*& v, bool zeroGepsOnly = false) { 68 assert(isa<PointerType>(v->getType()) && 69 "Translating a non-pointer type?"); 70 while (true) { 71 if (BitCastInst* C = dyn_cast<BitCastInst>(v)) 72 v = C->getOperand(0); 73 else if (GetElementPtrInst* G = dyn_cast<GetElementPtrInst>(v)) 74 if (!zeroGepsOnly || G->hasAllZeroIndices()) { 75 v = G->getOperand(0); 76 } else { 77 break; 78 } 79 else 80 break; 81 } 82 } 83 84 // getAnalysisUsage - We require post dominance frontiers (aka Control 85 // Dependence Graph) 86 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 87 AU.setPreservesCFG(); 88 AU.addRequired<TargetData>(); 89 AU.addRequired<AliasAnalysis>(); 90 AU.addRequired<MemoryDependenceAnalysis>(); 91 AU.addPreserved<AliasAnalysis>(); 92 AU.addPreserved<MemoryDependenceAnalysis>(); 93 } 94 }; 95 char DSE::ID = 0; 96 RegisterPass<DSE> X("dse", "Dead Store Elimination"); 97} 98 99FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 100 101bool DSE::runOnBasicBlock(BasicBlock &BB) { 102 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 103 TargetData &TD = getAnalysis<TargetData>(); 104 105 // Record the last-seen store to this pointer 106 DenseMap<Value*, StoreInst*> lastStore; 107 // Record instructions possibly made dead by deleting a store 108 SetVector<Instruction*> possiblyDead; 109 110 bool MadeChange = false; 111 112 // Do a top-down walk on the BB 113 for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); 114 BBI != BBE; ++BBI) { 115 // If we find a store or a free... 116 if (!isa<StoreInst>(BBI) && !isa<FreeInst>(BBI)) 117 continue; 118 119 Value* pointer = 0; 120 if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { 121 if (!S->isVolatile()) 122 pointer = S->getPointerOperand(); 123 else 124 continue; 125 } else 126 pointer = cast<FreeInst>(BBI)->getPointerOperand(); 127 128 TranslatePointerBitCasts(pointer, true); 129 StoreInst*& last = lastStore[pointer]; 130 bool deletedStore = false; 131 132 // ... to a pointer that has been stored to before... 133 if (last) { 134 Instruction* dep = MD.getDependency(BBI); 135 136 // ... and no other memory dependencies are between them.... 137 while (dep != MemoryDependenceAnalysis::None && 138 dep != MemoryDependenceAnalysis::NonLocal && 139 isa<StoreInst>(dep)) { 140 if (dep != last || 141 TD.getTypeStoreSize(last->getOperand(0)->getType()) > 142 TD.getTypeStoreSize(BBI->getOperand(0)->getType())) { 143 dep = MD.getDependency(BBI, dep); 144 continue; 145 } 146 147 // Remove it! 148 MD.removeInstruction(last); 149 150 // DCE instructions only used to calculate that store 151 if (Instruction* D = dyn_cast<Instruction>(last->getOperand(0))) 152 possiblyDead.insert(D); 153 if (Instruction* D = dyn_cast<Instruction>(last->getOperand(1))) 154 possiblyDead.insert(D); 155 156 last->eraseFromParent(); 157 NumFastStores++; 158 deletedStore = true; 159 MadeChange = true; 160 161 break; 162 } 163 } 164 165 // Handle frees whose dependencies are non-trivial. 166 if (FreeInst* F = dyn_cast<FreeInst>(BBI)) { 167 if (!deletedStore) 168 MadeChange |= handleFreeWithNonTrivialDependency(F, 169 MD.getDependency(F), 170 possiblyDead); 171 // No known stores after the free 172 last = 0; 173 } else { 174 // Update our most-recent-store map. 175 last = cast<StoreInst>(BBI); 176 } 177 } 178 179 // If this block ends in a return, unwind, unreachable, and eventually 180 // tailcall, then all allocas are dead at its end. 181 if (BB.getTerminator()->getNumSuccessors() == 0) 182 MadeChange |= handleEndBlock(BB, possiblyDead); 183 184 // Do a trivial DCE 185 while (!possiblyDead.empty()) { 186 Instruction *I = possiblyDead.back(); 187 possiblyDead.pop_back(); 188 DeleteDeadInstructionChains(I, possiblyDead); 189 } 190 191 return MadeChange; 192} 193 194/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose 195/// dependency is a store to a field of that structure 196bool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, Instruction* dep, 197 SetVector<Instruction*>& possiblyDead) { 198 TargetData &TD = getAnalysis<TargetData>(); 199 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 200 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 201 202 if (dep == MemoryDependenceAnalysis::None || 203 dep == MemoryDependenceAnalysis::NonLocal) 204 return false; 205 206 StoreInst* dependency = dyn_cast<StoreInst>(dep); 207 if (!dependency) 208 return false; 209 else if (dependency->isVolatile()) 210 return false; 211 212 Value* depPointer = dependency->getPointerOperand(); 213 const Type* depType = dependency->getOperand(0)->getType(); 214 unsigned depPointerSize = TD.getTypeStoreSize(depType); 215 216 // Check for aliasing 217 AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0U, 218 depPointer, depPointerSize); 219 220 if (A == AliasAnalysis::MustAlias) { 221 // Remove it! 222 MD.removeInstruction(dependency); 223 224 // DCE instructions only used to calculate that store 225 if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(0))) 226 possiblyDead.insert(D); 227 if (Instruction* D = dyn_cast<Instruction>(dependency->getOperand(1))) 228 possiblyDead.insert(D); 229 230 dependency->eraseFromParent(); 231 NumFastStores++; 232 return true; 233 } 234 235 return false; 236} 237 238/// handleEndBlock - Remove dead stores to stack-allocated locations in the 239/// function end block. Ex: 240/// %A = alloca i32 241/// ... 242/// store i32 1, i32* %A 243/// ret void 244bool DSE::handleEndBlock(BasicBlock& BB, 245 SetVector<Instruction*>& possiblyDead) { 246 TargetData &TD = getAnalysis<TargetData>(); 247 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 248 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 249 250 bool MadeChange = false; 251 252 // Pointers alloca'd in this function are dead in the end block 253 SmallPtrSet<Value*, 64> deadPointers; 254 255 // Find all of the alloca'd pointers in the entry block 256 BasicBlock *Entry = BB.getParent()->begin(); 257 for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 258 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 259 deadPointers.insert(AI); 260 for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 261 AE = BB.getParent()->arg_end(); AI != AE; ++AI) 262 if (AI->hasByValAttr()) 263 deadPointers.insert(AI); 264 265 // Scan the basic block backwards 266 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 267 --BBI; 268 269 // If we find a store whose pointer is dead... 270 if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { 271 if (!S->isVolatile()) { 272 Value* pointerOperand = S->getPointerOperand(); 273 // See through pointer-to-pointer bitcasts 274 TranslatePointerBitCasts(pointerOperand); 275 276 // Alloca'd pointers or byval arguments (which are functionally like 277 // alloca's) are valid candidates for removal. 278 if (deadPointers.count(pointerOperand)) { 279 // Remove it! 280 MD.removeInstruction(S); 281 282 // DCE instructions only used to calculate that store 283 if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0))) 284 possiblyDead.insert(D); 285 if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1))) 286 possiblyDead.insert(D); 287 288 BBI++; 289 S->eraseFromParent(); 290 NumFastStores++; 291 MadeChange = true; 292 } 293 } 294 295 continue; 296 297 // We can also remove memcpy's to local variables at the end of a function 298 } else if (MemCpyInst* M = dyn_cast<MemCpyInst>(BBI)) { 299 Value* dest = M->getDest(); 300 TranslatePointerBitCasts(dest); 301 302 if (deadPointers.count(dest)) { 303 MD.removeInstruction(M); 304 305 // DCE instructions only used to calculate that memcpy 306 if (Instruction* D = dyn_cast<Instruction>(M->getRawSource())) 307 possiblyDead.insert(D); 308 if (Instruction* D = dyn_cast<Instruction>(M->getLength())) 309 possiblyDead.insert(D); 310 if (Instruction* D = dyn_cast<Instruction>(M->getRawDest())) 311 possiblyDead.insert(D); 312 313 BBI++; 314 M->eraseFromParent(); 315 NumFastOther++; 316 MadeChange = true; 317 318 continue; 319 } 320 321 // Because a memcpy is also a load, we can't skip it if we didn't remove it 322 } 323 324 Value* killPointer = 0; 325 326 // If we encounter a use of the pointer, it is no longer considered dead 327 if (LoadInst* L = dyn_cast<LoadInst>(BBI)) { 328 // However, if this load is unused, we can go ahead and remove it, and 329 // not have to worry about it making our pointer undead! 330 if (L->getNumUses() == 0) { 331 MD.removeInstruction(L); 332 333 // DCE instructions only used to calculate that load 334 if (Instruction* D = dyn_cast<Instruction>(L->getPointerOperand())) 335 possiblyDead.insert(D); 336 337 BBI++; 338 L->eraseFromParent(); 339 NumFastOther++; 340 MadeChange = true; 341 possiblyDead.remove(L); 342 343 continue; 344 } 345 346 killPointer = L->getPointerOperand(); 347 } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) { 348 killPointer = V->getOperand(0); 349 } else if (AllocaInst* A = dyn_cast<AllocaInst>(BBI)) { 350 deadPointers.erase(A); 351 352 // Dead alloca's can be DCE'd when we reach them 353 if (A->getNumUses() == 0) { 354 MD.removeInstruction(A); 355 356 // DCE instructions only used to calculate that load 357 if (Instruction* D = dyn_cast<Instruction>(A->getArraySize())) 358 possiblyDead.insert(D); 359 360 BBI++; 361 A->eraseFromParent(); 362 NumFastOther++; 363 MadeChange = true; 364 possiblyDead.remove(A); 365 } 366 367 continue; 368 } else if (CallSite::get(BBI).getInstruction() != 0) { 369 // If this call does not access memory, it can't 370 // be undeadifying any of our pointers. 371 CallSite CS = CallSite::get(BBI); 372 if (AA.doesNotAccessMemory(CS)) 373 continue; 374 375 unsigned modRef = 0; 376 unsigned other = 0; 377 378 // Remove any pointers made undead by the call from the dead set 379 std::vector<Value*> dead; 380 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 381 E = deadPointers.end(); I != E; ++I) { 382 // HACK: if we detect that our AA is imprecise, it's not 383 // worth it to scan the rest of the deadPointers set. Just 384 // assume that the AA will return ModRef for everything, and 385 // go ahead and bail. 386 if (modRef >= 16 && other == 0) { 387 deadPointers.clear(); 388 return MadeChange; 389 } 390 391 // Get size information for the alloca 392 unsigned pointerSize = ~0U; 393 if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 394 if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 395 pointerSize = C->getZExtValue() * \ 396 TD.getABITypeSize(A->getAllocatedType()); 397 } else { 398 const PointerType* PT = cast<PointerType>( 399 cast<Argument>(*I)->getType()); 400 pointerSize = TD.getABITypeSize(PT->getElementType()); 401 } 402 403 // See if the call site touches it 404 AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize); 405 406 if (A == AliasAnalysis::ModRef) 407 modRef++; 408 else 409 other++; 410 411 if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 412 dead.push_back(*I); 413 } 414 415 for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end(); 416 I != E; ++I) 417 deadPointers.erase(*I); 418 419 continue; 420 } else { 421 // For any non-memory-affecting non-terminators, DCE them as we reach them 422 Instruction *CI = BBI; 423 if (!CI->isTerminator() && CI->getNumUses() == 0) { 424 425 // DCE instructions only used to calculate that load 426 for (Instruction::op_iterator OI = CI->op_begin(), OE = CI->op_end(); 427 OI != OE; ++OI) 428 if (Instruction* D = dyn_cast<Instruction>(OI)) 429 possiblyDead.insert(D); 430 431 BBI++; 432 CI->eraseFromParent(); 433 NumFastOther++; 434 MadeChange = true; 435 possiblyDead.remove(CI); 436 437 continue; 438 } 439 } 440 441 if (!killPointer) 442 continue; 443 444 TranslatePointerBitCasts(killPointer); 445 446 // Deal with undead pointers 447 MadeChange |= RemoveUndeadPointers(killPointer, BBI, 448 deadPointers, possiblyDead); 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, 457 BasicBlock::iterator& BBI, 458 SmallPtrSet<Value*, 64>& deadPointers, 459 SetVector<Instruction*>& possiblyDead) { 460 TargetData &TD = getAnalysis<TargetData>(); 461 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 462 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 463 464 // If the kill pointer can be easily reduced to an alloca, 465 // don't bother doing extraneous AA queries 466 if (deadPointers.count(killPointer)) { 467 deadPointers.erase(killPointer); 468 return false; 469 } else if (isa<GlobalValue>(killPointer)) { 470 // A global can't be in the dead pointer set 471 return false; 472 } 473 474 bool MadeChange = false; 475 476 std::vector<Value*> undead; 477 478 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 479 E = deadPointers.end(); I != E; ++I) { 480 // Get size information for the alloca 481 unsigned pointerSize = ~0U; 482 if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 483 if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 484 pointerSize = C->getZExtValue() * \ 485 TD.getABITypeSize(A->getAllocatedType()); 486 } else { 487 const PointerType* PT = cast<PointerType>( 488 cast<Argument>(*I)->getType()); 489 pointerSize = TD.getABITypeSize(PT->getElementType()); 490 } 491 492 // See if this pointer could alias it 493 AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize, 494 killPointer, ~0U); 495 496 // If it must-alias and a store, we can delete it 497 if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { 498 StoreInst* S = cast<StoreInst>(BBI); 499 500 // Remove it! 501 MD.removeInstruction(S); 502 503 // DCE instructions only used to calculate that store 504 if (Instruction* D = dyn_cast<Instruction>(S->getOperand(0))) 505 possiblyDead.insert(D); 506 if (Instruction* D = dyn_cast<Instruction>(S->getOperand(1))) 507 possiblyDead.insert(D); 508 509 BBI++; 510 S->eraseFromParent(); 511 NumFastStores++; 512 MadeChange = true; 513 514 continue; 515 516 // Otherwise, it is undead 517 } else if (A != AliasAnalysis::NoAlias) 518 undead.push_back(*I); 519 } 520 521 for (std::vector<Value*>::iterator I = undead.begin(), E = undead.end(); 522 I != E; ++I) 523 deadPointers.erase(*I); 524 525 return MadeChange; 526} 527 528/// DeleteDeadInstructionChains - takes an instruction and a setvector of 529/// dead instructions. If I is dead, it is erased, and its operands are 530/// checked for deadness. If they are dead, they are added to the dead 531/// setvector. 532void DSE::DeleteDeadInstructionChains(Instruction *I, 533 SetVector<Instruction*> &DeadInsts) { 534 // Instruction must be dead. 535 if (!I->use_empty() || !isInstructionTriviallyDead(I)) return; 536 537 // Let the memory dependence know 538 getAnalysis<MemoryDependenceAnalysis>().removeInstruction(I); 539 540 // See if this made any operands dead. We do it this way in case the 541 // instruction uses the same operand twice. We don't want to delete a 542 // value then reference it. 543 for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) { 544 if (I->getOperand(i)->hasOneUse()) 545 if (Instruction* Op = dyn_cast<Instruction>(I->getOperand(i))) 546 DeadInsts.insert(Op); // Attempt to nuke it later. 547 548 I->setOperand(i, 0); // Drop from the operand list. 549 } 550 551 I->eraseFromParent(); 552 ++NumFastOther; 553} 554