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, MemDepResult Dep);
  52     bool handleEndBlock(BasicBlock &BB);
  53     bool RemoveUndeadPointers(Value* Ptr, 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   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 it's 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.getTypeStoreSize(DepStore->getOperand(0)->getType()) <=
 121           TD.getTypeStoreSize(SI->getOperand(0)->getType())) {
 122         // Delete the store and now-dead instructions that feed it.
 123         DeleteDeadInstruction(DepStore);
 124         NumFastStores++;
 125         MadeChange = true;
 126
 127         if (BBI != BB.begin())
 128           --BBI;
 129         continue;
 130       }
 131
 132     // If we're storing the same value back to a pointer that we just
 133     // loaded from, then the store can be removed.
 134     if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) {
 135       if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
 136           SI->getOperand(0) == DepLoad) {
 137         DeleteDeadInstruction(SI);
 138         if (BBI != BB.begin())
 139           --BBI;
 140         NumFastStores++;
 141         MadeChange = true;
 142         continue;
 143       }
 144     }
 145   }
 146
 147   // If this block ends in a return, unwind, or unreachable, all allocas are
 148   // dead at its end, which means stores to them are also dead.
 149   if (BB.getTerminator()->getNumSuccessors() == 0)
 150     MadeChange |= handleEndBlock(BB);
 151
 152   return MadeChange;
 153 }
 154
 155 /// handleFreeWithNonTrivialDependency - Handle frees of entire structures whose
 156 /// dependency is a store to a field of that structure.
 157 bool DSE::handleFreeWithNonTrivialDependency(FreeInst *F, MemDepResult Dep) {
 158   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
 159
 160   StoreInst *Dependency = dyn_cast_or_null<StoreInst>(Dep.getInst());
 161   if (!Dependency || Dependency->isVolatile())
 162     return false;
 163
 164   Value *DepPointer = Dependency->getPointerOperand()->getUnderlyingObject();
 165
 166   // Check for aliasing.
 167   if (AA.alias(F->getPointerOperand(), 1, DepPointer, 1) !=
 168          AliasAnalysis::MustAlias)
 169     return false;
 170
 171   // DCE instructions only used to calculate that store
 172   DeleteDeadInstruction(Dependency);
 173   NumFastStores++;
 174   return true;
 175 }
 176
 177 /// handleEndBlock - Remove dead stores to stack-allocated locations in the
 178 /// function end block.  Ex:
 179 /// %A = alloca i32
 180 /// ...
 181 /// store i32 1, i32* %A
 182 /// ret void
 183 bool DSE::handleEndBlock(BasicBlock &BB) {
 184   TargetData &TD = getAnalysis<TargetData>();
 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 (AllocaInst* A = dyn_cast<AllocaInst>(*I)) {
 306           if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize()))
 307             pointerSize = C->getZExtValue() *
 308                           TD.getTypeAllocSize(A->getAllocatedType());
 309         } else {
 310           const PointerType* PT = cast<PointerType>(
 311                                                  cast<Argument>(*I)->getType());
 312           pointerSize = TD.getTypeAllocSize(PT->getElementType());
 313         }
 314
 315         // See if the call site touches it
 316         AliasAnalysis::ModRefResult A = AA.getModRefInfo(CS, *I, pointerSize);
 317
 318         if (A == AliasAnalysis::ModRef)
 319           modRef++;
 320         else
 321           other++;
 322
 323         if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref)
 324           dead.push_back(*I);
 325       }
 326
 327       for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end();
 328            I != E; ++I)
 329         deadPointers.erase(*I);
 330
 331       continue;
 332     } else if (isInstructionTriviallyDead(BBI)) {
 333       // For any non-memory-affecting non-terminators, DCE them as we reach them
 334       Instruction *Inst = BBI;
 335       BBI++;
 336       DeleteDeadInstruction(Inst, &deadPointers);
 337       NumFastOther++;
 338       MadeChange = true;
 339       continue;
 340     }
 341
 342     if (!killPointer)
 343       continue;
 344
 345     killPointer = killPointer->getUnderlyingObject();
 346
 347     // Deal with undead pointers
 348     MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI,
 349                                        deadPointers);
 350   }
 351
 352   return MadeChange;
 353 }
 354
 355 /// RemoveUndeadPointers - check for uses of a pointer that make it
 356 /// undead when scanning for dead stores to alloca's.
 357 bool DSE::RemoveUndeadPointers(Value* killPointer, uint64_t killPointerSize,
 358                                BasicBlock::iterator &BBI,
 359                                SmallPtrSet<Value*, 64>& deadPointers) {
 360   TargetData &TD = getAnalysis<TargetData>();
 361   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
 362
 363   // If the kill pointer can be easily reduced to an alloca,
 364   // don't bother doing extraneous AA queries.
 365   if (deadPointers.count(killPointer)) {
 366     deadPointers.erase(killPointer);
 367     return false;
 368   }
 369
 370   // A global can't be in the dead pointer set.
 371   if (isa<GlobalValue>(killPointer))
 372     return false;
 373
 374   bool MadeChange = false;
 375
 376   SmallVector<Value*, 16> undead;
 377
 378   for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(),
 379       E = deadPointers.end(); I != E; ++I) {
 380     // Get size information for the alloca.
 381     unsigned pointerSize = ~0U;
 382     if (AllocaInst* A = dyn_cast<AllocaInst>(*I)) {
 383       if (ConstantInt* C = dyn_cast<ConstantInt>(A->getArraySize()))
 384         pointerSize = C->getZExtValue() *
 385                       TD.getTypeAllocSize(A->getAllocatedType());
 386     } else {
 387       const PointerType* PT = cast<PointerType>(cast<Argument>(*I)->getType());
 388       pointerSize = TD.getTypeAllocSize(PT->getElementType());
 389     }
 390
 391     // See if this pointer could alias it
 392     AliasAnalysis::AliasResult A = AA.alias(*I, pointerSize,
 393                                             killPointer, killPointerSize);
 394
 395     // If it must-alias and a store, we can delete it
 396     if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) {
 397       StoreInst* S = cast<StoreInst>(BBI);
 398
 399       // Remove it!
 400       BBI++;
 401       DeleteDeadInstruction(S, &deadPointers);
 402       NumFastStores++;
 403       MadeChange = true;
 404
 405       continue;
 406
 407       // Otherwise, it is undead
 408     } else if (A != AliasAnalysis::NoAlias)
 409       undead.push_back(*I);
 410   }
 411
 412   for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end();
 413        I != E; ++I)
 414       deadPointers.erase(*I);
 415
 416   return MadeChange;
 417 }
 418
 419 /// DeleteDeadInstruction - Delete this instruction.  Before we do, go through
 420 /// and zero out all the operands of this instruction.  If any of them become
 421 /// dead, delete them and the computation tree that feeds them.
 422 ///
 423 /// If ValueSet is non-null, remove any deleted instructions from it as well.
 424 ///
 425 void DSE::DeleteDeadInstruction(Instruction *I,
 426                                 SmallPtrSet<Value*, 64> *ValueSet) {
 427   SmallVector<Instruction*, 32> NowDeadInsts;
 428
 429   NowDeadInsts.push_back(I);
 430   --NumFastOther;
 431
 432   // Before we touch this instruction, remove it from memdep!
 433   MemoryDependenceAnalysis &MDA = getAnalysis<MemoryDependenceAnalysis>();
 434   while (!NowDeadInsts.empty()) {
 435     Instruction *DeadInst = NowDeadInsts.back();
 436     NowDeadInsts.pop_back();
 437
 438     ++NumFastOther;
 439
 440     // This instruction is dead, zap it, in stages.  Start by removing it from
 441     // MemDep, which needs to know the operands and needs it to be in the
 442     // function.
 443     MDA.removeInstruction(DeadInst);
 444
 445     for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
 446       Value *Op = DeadInst->getOperand(op);
 447       DeadInst->setOperand(op, 0);
 448
 449       // If this operand just became dead, add it to the NowDeadInsts list.
 450       if (!Op->use_empty()) continue;
 451
 452       if (Instruction *OpI = dyn_cast<Instruction>(Op))
 453         if (isInstructionTriviallyDead(OpI))
 454           NowDeadInsts.push_back(OpI);
 455     }
 456
 457     DeadInst->eraseFromParent();
 458
 459     if (ValueSet) ValueSet->erase(DeadInst);
 460   }
 461 }