DeadStoreElimination.cpp revision 3a76be584b6d5f85b2a5dadd21247063c0a24c30
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/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(&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, MemDepResult Dep); 52 bool handleEndBlock(BasicBlock &BB); 53 bool RemoveUndeadPointers(Value* pointer, uint64_t killPointerSize, 54 BasicBlock::iterator& BBI, 55 SmallPtrSet<Value*, 64>& deadPointers); 56 void DeleteDeadInstruction(Instruction *I, 57 SmallPtrSet<Value*, 64> *deadPointers = 0); 58 59 60 // getAnalysisUsage - We require post dominance frontiers (aka Control 61 // Dependence Graph) 62 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 63 AU.setPreservesCFG(); 64 AU.addRequired<DominatorTree>(); 65 AU.addRequired<TargetData>(); 66 AU.addRequired<AliasAnalysis>(); 67 AU.addRequired<MemoryDependenceAnalysis>(); 68 AU.addPreserved<DominatorTree>(); 69 AU.addPreserved<AliasAnalysis>(); 70 AU.addPreserved<MemoryDependenceAnalysis>(); 71 } 72 }; 73} 74 75char DSE::ID = 0; 76static RegisterPass<DSE> X("dse", "Dead Store Elimination"); 77 78FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } 79 80bool DSE::runOnBasicBlock(BasicBlock &BB) { 81 MemoryDependenceAnalysis& MD = getAnalysis<MemoryDependenceAnalysis>(); 82 TargetData &TD = getAnalysis<TargetData>(); 83 84 // Record the last-seen store to this pointer 85 DenseMap<Value*, StoreInst*> lastStore; 86 87 bool MadeChange = false; 88 89 // Do a top-down walk on the BB 90 for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) { 91 Instruction *Inst = BBI++; 92 93 // If we find a store or a free... 94 if (!isa<StoreInst>(Inst) && !isa<FreeInst>(Inst)) 95 continue; 96 97 Value* pointer = 0; 98 if (StoreInst* S = dyn_cast<StoreInst>(Inst)) { 99 if (S->isVolatile()) 100 continue; 101 pointer = S->getPointerOperand(); 102 } else { 103 pointer = cast<FreeInst>(Inst)->getPointerOperand(); 104 } 105 106 pointer = pointer->stripPointerCasts(); 107 StoreInst *&last = lastStore[pointer]; 108 109 // ... to a pointer that has been stored to before... 110 if (last) { 111 MemDepResult dep = MD.getDependency(Inst); 112 bool deletedStore = false; 113 114 // ... and no other memory dependencies are between them.... 115 while (StoreInst *DepStore = dyn_cast_or_null<StoreInst>(dep.getInst())) { 116 if (DepStore != last || 117 TD.getTypeStoreSize(last->getOperand(0)->getType()) > 118 TD.getTypeStoreSize(Inst->getOperand(0)->getType())) { 119 dep = MD.getDependencyFrom(Inst, DepStore, DepStore->getParent()); 120 continue; 121 } 122 123 // Delete the store and now-dead instructions that feed it. 124 DeleteDeadInstruction(last); 125 NumFastStores++; 126 deletedStore = true; 127 MadeChange = true; 128 break; 129 } 130 131 // If we deleted a store, reinvestigate this instruction. 132 if (deletedStore) { 133 if (BBI != BB.begin()) 134 --BBI; 135 continue; 136 } 137 } 138 139 // Handle frees whose dependencies are non-trivial. 140 if (FreeInst* F = dyn_cast<FreeInst>(Inst)) { 141 MadeChange |= handleFreeWithNonTrivialDependency(F, MD.getDependency(F)); 142 143 // No known stores after the free. 144 last = 0; 145 } else { 146 StoreInst* S = cast<StoreInst>(Inst); 147 148 // If we're storing the same value back to a pointer that we just 149 // loaded from, then the store can be removed; 150 if (LoadInst* L = dyn_cast<LoadInst>(S->getOperand(0))) { 151 // FIXME: Don't do dep query if Parents don't match and other stuff! 152 MemDepResult dep = MD.getDependency(S); 153 DominatorTree& DT = getAnalysis<DominatorTree>(); 154 155 if (!S->isVolatile() && S->getParent() == L->getParent() && 156 S->getPointerOperand() == L->getPointerOperand() && 157 (!dep.isNormal() || DT.dominates(dep.getInst(), L))) { 158 159 DeleteDeadInstruction(S); 160 if (BBI != BB.begin()) 161 --BBI; 162 NumFastStores++; 163 MadeChange = true; 164 } else 165 // Update our most-recent-store map. 166 last = S; 167 } else 168 // Update our most-recent-store map. 169 last = S; 170 } 171 } 172 173 // If this block ends in a return, unwind, or unreachable, all allocas are 174 // dead at its end, which means stores to them are also dead. 175 if (BB.getTerminator()->getNumSuccessors() == 0) 176 MadeChange |= handleEndBlock(BB); 177 178 return MadeChange; 179} 180 181/// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose 182/// dependency is a store to a field of that structure. 183bool DSE::handleFreeWithNonTrivialDependency(FreeInst* F, MemDepResult dep) { 184 TargetData &TD = getAnalysis<TargetData>(); 185 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 186 187 StoreInst* dependency = dyn_cast_or_null<StoreInst>(dep.getInst()); 188 if (!dependency) 189 return false; 190 else if (dependency->isVolatile()) 191 return false; 192 193 Value* depPointer = dependency->getPointerOperand(); 194 const Type* depType = dependency->getOperand(0)->getType(); 195 unsigned depPointerSize = TD.getTypeStoreSize(depType); 196 197 // Check for aliasing 198 AliasAnalysis::AliasResult A = AA.alias(F->getPointerOperand(), ~0U, 199 depPointer, depPointerSize); 200 201 if (A != AliasAnalysis::MustAlias) 202 return false; 203 204 // DCE instructions only used to calculate that store 205 DeleteDeadInstruction(dependency); 206 NumFastStores++; 207 return true; 208} 209 210/// handleEndBlock - Remove dead stores to stack-allocated locations in the 211/// function end block. Ex: 212/// %A = alloca i32 213/// ... 214/// store i32 1, i32* %A 215/// ret void 216bool DSE::handleEndBlock(BasicBlock &BB) { 217 TargetData &TD = getAnalysis<TargetData>(); 218 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 219 220 bool MadeChange = false; 221 222 // Pointers alloca'd in this function are dead in the end block 223 SmallPtrSet<Value*, 64> deadPointers; 224 225 // Find all of the alloca'd pointers in the entry block. 226 BasicBlock *Entry = BB.getParent()->begin(); 227 for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I) 228 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 229 deadPointers.insert(AI); 230 231 // Treat byval arguments the same, stores to them are dead at the end of the 232 // function. 233 for (Function::arg_iterator AI = BB.getParent()->arg_begin(), 234 AE = BB.getParent()->arg_end(); AI != AE; ++AI) 235 if (AI->hasByValAttr()) 236 deadPointers.insert(AI); 237 238 // Scan the basic block backwards 239 for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){ 240 --BBI; 241 242 // If we find a store whose pointer is dead. 243 if (StoreInst* S = dyn_cast<StoreInst>(BBI)) { 244 if (!S->isVolatile()) { 245 // See through pointer-to-pointer bitcasts 246 Value* pointerOperand = S->getPointerOperand()->getUnderlyingObject(); 247 248 // Alloca'd pointers or byval arguments (which are functionally like 249 // alloca's) are valid candidates for removal. 250 if (deadPointers.count(pointerOperand)) { 251 // DCE instructions only used to calculate that store. 252 BBI++; 253 DeleteDeadInstruction(S, &deadPointers); 254 NumFastStores++; 255 MadeChange = true; 256 } 257 } 258 259 continue; 260 } 261 262 // We can also remove memcpy's to local variables at the end of a function. 263 if (MemCpyInst *M = dyn_cast<MemCpyInst>(BBI)) { 264 Value *dest = M->getDest()->getUnderlyingObject(); 265 266 if (deadPointers.count(dest)) { 267 BBI++; 268 DeleteDeadInstruction(M, &deadPointers); 269 NumFastOther++; 270 MadeChange = true; 271 continue; 272 } 273 274 // Because a memcpy is also a load, we can't skip it if we didn't remove 275 // it. 276 } 277 278 Value* killPointer = 0; 279 uint64_t killPointerSize = ~0UL; 280 281 // If we encounter a use of the pointer, it is no longer considered dead 282 if (LoadInst *L = dyn_cast<LoadInst>(BBI)) { 283 // However, if this load is unused and not volatile, we can go ahead and 284 // remove it, and not have to worry about it making our pointer undead! 285 if (L->use_empty() && !L->isVolatile()) { 286 BBI++; 287 DeleteDeadInstruction(L, &deadPointers); 288 NumFastOther++; 289 MadeChange = true; 290 continue; 291 } 292 293 killPointer = L->getPointerOperand(); 294 } else if (VAArgInst* V = dyn_cast<VAArgInst>(BBI)) { 295 killPointer = V->getOperand(0); 296 } else if (isa<MemCpyInst>(BBI) && 297 isa<ConstantInt>(cast<MemCpyInst>(BBI)->getLength())) { 298 killPointer = cast<MemCpyInst>(BBI)->getSource(); 299 killPointerSize = cast<ConstantInt>( 300 cast<MemCpyInst>(BBI)->getLength())->getZExtValue(); 301 } else if (AllocaInst* A = dyn_cast<AllocaInst>(BBI)) { 302 deadPointers.erase(A); 303 304 // Dead alloca's can be DCE'd when we reach them 305 if (A->use_empty()) { 306 BBI++; 307 DeleteDeadInstruction(A, &deadPointers); 308 NumFastOther++; 309 MadeChange = true; 310 } 311 312 continue; 313 } else if (CallSite::get(BBI).getInstruction() != 0) { 314 // If this call does not access memory, it can't 315 // be undeadifying any of our pointers. 316 CallSite CS = CallSite::get(BBI); 317 if (AA.doesNotAccessMemory(CS)) 318 continue; 319 320 unsigned modRef = 0; 321 unsigned other = 0; 322 323 // Remove any pointers made undead by the call from the dead set 324 std::vector<Value*> dead; 325 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 326 E = deadPointers.end(); I != E; ++I) { 327 // HACK: if we detect that our AA is imprecise, it's not 328 // worth it to scan the rest of the deadPointers set. Just 329 // assume that the AA will return ModRef for everything, and 330 // go ahead and bail. 331 if (modRef >= 16 && other == 0) { 332 deadPointers.clear(); 333 return MadeChange; 334 } 335 336 // Get size information for the alloca 337 unsigned pointerSize = ~0U; 338 if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 339 if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 340 pointerSize = C->getZExtValue() * 341 TD.getABITypeSize(A->getAllocatedType()); 342 } else { 343 const PointerType* PT = cast<PointerType>( 344 cast<Argument>(*I)->getType()); 345 pointerSize = TD.getABITypeSize(PT->getElementType()); 346 } 347 348 // See if the call site touches it 349 AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize); 350 351 if (A == AliasAnalysis::ModRef) 352 modRef++; 353 else 354 other++; 355 356 if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref) 357 dead.push_back(*I); 358 } 359 360 for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end(); 361 I != E; ++I) 362 deadPointers.erase(*I); 363 364 continue; 365 } else if (isInstructionTriviallyDead(BBI)) { 366 // For any non-memory-affecting non-terminators, DCE them as we reach them 367 Instruction *Inst = BBI; 368 BBI++; 369 DeleteDeadInstruction(Inst, &deadPointers); 370 NumFastOther++; 371 MadeChange = true; 372 continue; 373 } 374 375 if (!killPointer) 376 continue; 377 378 killPointer = killPointer->getUnderlyingObject(); 379 380 // Deal with undead pointers 381 MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI, 382 deadPointers); 383 } 384 385 return MadeChange; 386} 387 388/// RemoveUndeadPointers - check for uses of a pointer that make it 389/// undead when scanning for dead stores to alloca's. 390bool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize, 391 BasicBlock::iterator &BBI, 392 SmallPtrSet<Value*, 64>& deadPointers) { 393 TargetData &TD = getAnalysis<TargetData>(); 394 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 395 396 // If the kill pointer can be easily reduced to an alloca, 397 // don't bother doing extraneous AA queries. 398 if (deadPointers.count(killPointer)) { 399 deadPointers.erase(killPointer); 400 return false; 401 } 402 403 // A global can't be in the dead pointer set. 404 if (isa<GlobalValue>(killPointer)) 405 return false; 406 407 bool MadeChange = false; 408 409 SmallVector<Value*, 16> undead; 410 411 for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(), 412 E = deadPointers.end(); I != E; ++I) { 413 // Get size information for the alloca. 414 unsigned pointerSize = ~0U; 415 if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) { 416 if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize())) 417 pointerSize = C->getZExtValue() * 418 TD.getABITypeSize(A->getAllocatedType()); 419 } else { 420 const PointerType* PT = cast<PointerType>(cast<Argument>(*I)->getType()); 421 pointerSize = TD.getABITypeSize(PT->getElementType()); 422 } 423 424 // See if this pointer could alias it 425 AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize, 426 killPointer, killPointerSize); 427 428 // If it must-alias and a store, we can delete it 429 if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) { 430 StoreInst* S = cast<StoreInst>(BBI); 431 432 // Remove it! 433 BBI++; 434 DeleteDeadInstruction(S, &deadPointers); 435 NumFastStores++; 436 MadeChange = true; 437 438 continue; 439 440 // Otherwise, it is undead 441 } else if (A != AliasAnalysis::NoAlias) 442 undead.push_back(*I); 443 } 444 445 for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end(); 446 I != E; ++I) 447 deadPointers.erase(*I); 448 449 return MadeChange; 450} 451 452/// DeleteDeadInstruction - Delete this instruction. Before we do, go through 453/// and zero out all the operands of this instruction. If any of them become 454/// dead, delete them and the computation tree that feeds them. 455/// 456/// If ValueSet is non-null, remove any deleted instructions from it as well. 457/// 458void DSE::DeleteDeadInstruction(Instruction *I, 459 SmallPtrSet<Value*, 64> *ValueSet) { 460 SmallVector<Instruction*, 32> NowDeadInsts; 461 462 NowDeadInsts.push_back(I); 463 --NumFastOther; 464 465 // Before we touch this instruction, remove it from memdep! 466 MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>(); 467 while (!NowDeadInsts.empty()) { 468 Instruction *DeadInst = NowDeadInsts.back(); 469 NowDeadInsts.pop_back(); 470 471 ++NumFastOther; 472 473 // This instruction is dead, zap it, in stages. Start by removing it from 474 // MemDep, which needs to know the operands and needs it to be in the 475 // function. 476 MDA.removeInstruction(DeadInst); 477 478 for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) { 479 Value *Op = DeadInst->getOperand(op); 480 DeadInst->setOperand(op, 0); 481 482 // If this operand just became dead, add it to the NowDeadInsts list. 483 if (!Op->use_empty()) continue; 484 485 if (Instruction *OpI = dyn_cast<Instruction>(Op)) 486 if (isInstructionTriviallyDead(OpI)) 487 NowDeadInsts.push_back(OpI); 488 } 489 490 DeadInst->eraseFromParent(); 491 492 if (ValueSet) ValueSet->erase(DeadInst); 493 } 494} 495