lib/Transforms/Scalar/DeadStoreElimination.cpp

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