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