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