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/MemoryBuiltins.h"
  30 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
  31 #include "llvm/Target/TargetData.h"
  32 #include "llvm/Transforms/Utils/Local.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 DSE : public FunctionPass {
  40     AliasAnalysis *AA;
  41     MemoryDependenceAnalysis *MD;
  42
  43     static char ID; // Pass identification, replacement for typeid
  44     DSE() : FunctionPass(ID), AA(0), MD(0) {
  45       initializeDSEPass(*PassRegistry::getPassRegistry());
  46     }
  47
  48     virtual bool runOnFunction(Function &F) {
  49       AA = &getAnalysis<AliasAnalysis>();
  50       MD = &getAnalysis<MemoryDependenceAnalysis>();
  51       DominatorTree &DT = getAnalysis<DominatorTree>();
  52
  53       bool Changed = false;
  54       for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
  55         // Only check non-dead blocks.  Dead blocks may have strange pointer
  56         // cycles that will confuse alias analysis.
  57         if (DT.isReachableFromEntry(I))
  58           Changed |= runOnBasicBlock(*I);
  59
  60       AA = 0; MD = 0;
  61       return Changed;
  62     }
  63
  64     bool runOnBasicBlock(BasicBlock &BB);
  65     bool HandleFree(CallInst *F);
  66     bool handleEndBlock(BasicBlock &BB);
  67     bool RemoveUndeadPointers(Value *Ptr, uint64_t killPointerSize,
  68                               BasicBlock::iterator &BBI,
  69                               SmallPtrSet<Value*, 64> &deadPointers);
  70     void DeleteDeadInstruction(Instruction *I,
  71                                SmallPtrSet<Value*, 64> *deadPointers = 0);
  72
  73
  74     // getAnalysisUsage - We require post dominance frontiers (aka Control
  75     // Dependence Graph)
  76     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  77       AU.setPreservesCFG();
  78       AU.addRequired<DominatorTree>();
  79       AU.addRequired<AliasAnalysis>();
  80       AU.addRequired<MemoryDependenceAnalysis>();
  81       AU.addPreserved<AliasAnalysis>();
  82       AU.addPreserved<DominatorTree>();
  83       AU.addPreserved<MemoryDependenceAnalysis>();
  84     }
  85   };
  86 }
  87
  88 char DSE::ID = 0;
  89 INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false)
  90 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
  91 INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis)
  92 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
  93 INITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false)
  94
  95 FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); }
  96
  97 /// hasMemoryWrite - Does this instruction write some memory?  This only returns
  98 /// true for things that we can analyze with other helpers below.
  99 static bool hasMemoryWrite(Instruction *I) {
 100   if (isa<StoreInst>(I))
 101     return true;
 102   if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
 103     switch (II->getIntrinsicID()) {
 104     default:
 105       return false;
 106     case Intrinsic::memset:
 107     case Intrinsic::memmove:
 108     case Intrinsic::memcpy:
 109     case Intrinsic::init_trampoline:
 110     case Intrinsic::lifetime_end:
 111       return true;
 112     }
 113   }
 114   return false;
 115 }
 116
 117 /// getLocForWrite - Return a Location stored to by the specified instruction.
 118 static AliasAnalysis::Location
 119 getLocForWrite(Instruction *Inst, AliasAnalysis &AA) {
 120   if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
 121     return AA.getLocation(SI);
 122
 123   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Inst)) {
 124     // memcpy/memmove/memset.
 125     AliasAnalysis::Location Loc = AA.getLocationForDest(MI);
 126     // If we don't have target data around, an unknown size in Location means
 127     // that we should use the size of the pointee type.  This isn't valid for
 128     // memset/memcpy, which writes more than an i8.
 129     if (Loc.Size == AliasAnalysis::UnknownSize && AA.getTargetData() == 0)
 130       return AliasAnalysis::Location();
 131     return Loc;
 132   }
 133
 134   IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst);
 135   if (II == 0) return AliasAnalysis::Location();
 136
 137   switch (II->getIntrinsicID()) {
 138   default: return AliasAnalysis::Location(); // Unhandled intrinsic.
 139   case Intrinsic::init_trampoline:
 140     // If we don't have target data around, an unknown size in Location means
 141     // that we should use the size of the pointee type.  This isn't valid for
 142     // init.trampoline, which writes more than an i8.
 143     if (AA.getTargetData() == 0) return AliasAnalysis::Location();
 144
 145     // FIXME: We don't know the size of the trampoline, so we can't really
 146     // handle it here.
 147     return AliasAnalysis::Location(II->getArgOperand(0));
 148   case Intrinsic::lifetime_end: {
 149     uint64_t Len = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
 150     return AliasAnalysis::Location(II->getArgOperand(1), Len);
 151   }
 152   }
 153 }
 154
 155 /// isRemovable - If the value of this instruction and the memory it writes to
 156 /// is unused, may we delete this instruction?
 157 static bool isRemovable(Instruction *I) {
 158   // Don't remove volatile stores.
 159   if (StoreInst *SI = dyn_cast<StoreInst>(I))
 160     return !SI->isVolatile();
 161
 162   IntrinsicInst *II = cast<IntrinsicInst>(I);
 163   switch (II->getIntrinsicID()) {
 164   default: assert(0 && "doesn't pass 'hasMemoryWrite' predicate");
 165   case Intrinsic::lifetime_end:
 166     // Never remove dead lifetime_end's, e.g. because it is followed by a
 167     // free.
 168     return false;
 169   case Intrinsic::init_trampoline:
 170     // Always safe to remove init_trampoline.
 171     return true;
 172
 173   case Intrinsic::memset:
 174   case Intrinsic::memmove:
 175   case Intrinsic::memcpy:
 176     // Don't remove volatile memory intrinsics.
 177     return !cast<MemIntrinsic>(II)->isVolatile();
 178   }
 179 }
 180
 181 /// getPointerOperand - Return the pointer that is being written to.
 182 static Value *getPointerOperand(Instruction *I) {
 183   assert(hasMemoryWrite(I));
 184   if (StoreInst *SI = dyn_cast<StoreInst>(I))
 185     return SI->getPointerOperand();
 186   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
 187     return MI->getArgOperand(0);
 188
 189   IntrinsicInst *II = cast<IntrinsicInst>(I);
 190   switch (II->getIntrinsicID()) {
 191   default: assert(false && "Unexpected intrinsic!");
 192   case Intrinsic::init_trampoline:
 193     return II->getArgOperand(0);
 194   case Intrinsic::lifetime_end:
 195     return II->getArgOperand(1);
 196   }
 197 }
 198
 199 static uint64_t getPointerSize(Value *V, AliasAnalysis &AA) {
 200   const TargetData *TD = AA.getTargetData();
 201   if (TD == 0)
 202     return AliasAnalysis::UnknownSize;
 203
 204   if (AllocaInst *A = dyn_cast<AllocaInst>(V)) {
 205     // Get size information for the alloca
 206     if (ConstantInt *C = dyn_cast<ConstantInt>(A->getArraySize()))
 207       return C->getZExtValue() * TD->getTypeAllocSize(A->getAllocatedType());
 208     return AliasAnalysis::UnknownSize;
 209   }
 210
 211   assert(isa<Argument>(V) && "Expected AllocaInst or Argument!");
 212   const PointerType *PT = cast<PointerType>(V->getType());
 213   return TD->getTypeAllocSize(PT->getElementType());
 214 }
 215
 216
 217 /// isCompleteOverwrite - Return true if a store to the 'Later' location
 218 /// completely overwrites a store to the 'Earlier' location.
 219 static bool isCompleteOverwrite(const AliasAnalysis::Location &Later,
 220                                 const AliasAnalysis::Location &Earlier,
 221                                 AliasAnalysis &AA) {
 222   const Value *P1 = Later.Ptr->stripPointerCasts();
 223   const Value *P2 = Earlier.Ptr->stripPointerCasts();
 224
 225   // Make sure that the start pointers are the same.
 226   if (P1 != P2)
 227     return false;
 228
 229   // If we don't know the sizes of either access, then we can't do a comparison.
 230   if (Later.Size == AliasAnalysis::UnknownSize ||
 231       Earlier.Size == AliasAnalysis::UnknownSize) {
 232     // If we have no TargetData information around, then the size of the store
 233     // is inferrable from the pointee type.  If they are the same type, then we
 234     // know that the store is safe.
 235     if (AA.getTargetData() == 0)
 236       return Later.Ptr->getType() == Earlier.Ptr->getType();
 237     return false;
 238   }
 239
 240   // Make sure that the Later size is >= the Earlier size.
 241   if (Later.Size < Earlier.Size)
 242     return false;
 243
 244   return true;
 245 }
 246
 247 bool DSE::runOnBasicBlock(BasicBlock &BB) {
 248   bool MadeChange = false;
 249
 250   // Do a top-down walk on the BB.
 251   for (BasicBlock::iterator BBI = BB.begin(), BBE = BB.end(); BBI != BBE; ) {
 252     Instruction *Inst = BBI++;
 253
 254     // Handle 'free' calls specially.
 255     if (CallInst *F = isFreeCall(Inst)) {
 256       MadeChange |= HandleFree(F);
 257       continue;
 258     }
 259
 260     // If we find something that writes memory, get its memory dependence.
 261     if (!hasMemoryWrite(Inst))
 262       continue;
 263
 264     MemDepResult InstDep = MD->getDependency(Inst);
 265
 266     // Ignore non-local store liveness.
 267     // FIXME: cross-block DSE would be fun. :)
 268     if (InstDep.isNonLocal() ||
 269         // Ignore self dependence, which happens in the entry block of the
 270         // function.
 271         InstDep.getInst() == Inst)
 272       continue;
 273
 274     // If we're storing the same value back to a pointer that we just
 275     // loaded from, then the store can be removed.
 276     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 277       if (LoadInst *DepLoad = dyn_cast<LoadInst>(InstDep.getInst())) {
 278         if (SI->getPointerOperand() == DepLoad->getPointerOperand() &&
 279             SI->getOperand(0) == DepLoad && !SI->isVolatile()) {
 280           // DeleteDeadInstruction can delete the current instruction.  Save BBI
 281           // in case we need it.
 282           WeakVH NextInst(BBI);
 283
 284           DeleteDeadInstruction(SI);
 285
 286           if (NextInst == 0)  // Next instruction deleted.
 287             BBI = BB.begin();
 288           else if (BBI != BB.begin())  // Revisit this instruction if possible.
 289             --BBI;
 290           ++NumFastStores;
 291           MadeChange = true;
 292           continue;
 293         }
 294       }
 295     }
 296
 297     // Figure out what location is being stored to.
 298     AliasAnalysis::Location Loc = getLocForWrite(Inst, *AA);
 299
 300     // If we didn't get a useful location, fail.
 301     if (Loc.Ptr == 0)
 302       continue;
 303
 304     while (!InstDep.isNonLocal()) {
 305       // Get the memory clobbered by the instruction we depend on.  MemDep will
 306       // skip any instructions that 'Loc' clearly doesn't interact with.  If we
 307       // end up depending on a may- or must-aliased load, then we can't optimize
 308       // away the store and we bail out.  However, if we depend on on something
 309       // that overwrites the memory location we *can* potentially optimize it.
 310       //
 311       // Find out what memory location the dependant instruction stores.
 312       Instruction *DepWrite = InstDep.getInst();
 313       AliasAnalysis::Location DepLoc = getLocForWrite(DepWrite, *AA);
 314       // If we didn't get a useful location, or if it isn't a size, bail out.
 315       if (DepLoc.Ptr == 0)
 316         break;
 317
 318       // If we find a removable write that is completely obliterated by the
 319       // store to 'Loc' then we can remove it.
 320       if (isRemovable(DepWrite) && isCompleteOverwrite(Loc, DepLoc, *AA)) {
 321         // Delete the store and now-dead instructions that feed it.
 322         DeleteDeadInstruction(DepWrite);
 323         ++NumFastStores;
 324         MadeChange = true;
 325
 326         // DeleteDeadInstruction can delete the current instruction in loop
 327         // cases, reset BBI.
 328         BBI = Inst;
 329         if (BBI != BB.begin())
 330           --BBI;
 331         break;
 332       }
 333
 334       // If this is a may-aliased store that is clobbering the store value, we
 335       // can keep searching past it for another must-aliased pointer that stores
 336       // to the same location.  For example, in:
 337       //   store -> P
 338       //   store -> Q
 339       //   store -> P
 340       // we can remove the first store to P even though we don't know if P and Q
 341       // alias.
 342       if (DepWrite == &BB.front()) break;
 343
 344       // Can't look past this instruction if it might read 'Loc'.
 345       if (AA->getModRefInfo(DepWrite, Loc) & AliasAnalysis::Ref)
 346         break;
 347
 348       InstDep = MD->getPointerDependencyFrom(Loc, false, DepWrite, &BB);
 349     }
 350   }
 351
 352   // If this block ends in a return, unwind, or unreachable, all allocas are
 353   // dead at its end, which means stores to them are also dead.
 354   if (BB.getTerminator()->getNumSuccessors() == 0)
 355     MadeChange |= handleEndBlock(BB);
 356
 357   return MadeChange;
 358 }
 359
 360 /// HandleFree - Handle frees of entire structures whose dependency is a store
 361 /// to a field of that structure.
 362 bool DSE::HandleFree(CallInst *F) {
 363   MemDepResult Dep = MD->getDependency(F);
 364   do {
 365     if (Dep.isNonLocal()) return false;
 366
 367     Instruction *Dependency = Dep.getInst();
 368     if (!hasMemoryWrite(Dependency) || !isRemovable(Dependency))
 369       return false;
 370
 371     Value *DepPointer = getPointerOperand(Dependency)->getUnderlyingObject();
 372
 373     // Check for aliasing.
 374     if (AA->alias(F->getArgOperand(0), 1, DepPointer, 1) !=
 375           AliasAnalysis::MustAlias)
 376       return false;
 377
 378     // DCE instructions only used to calculate that store
 379     DeleteDeadInstruction(Dependency);
 380     ++NumFastStores;
 381
 382     // Inst's old Dependency is now deleted. Compute the next dependency,
 383     // which may also be dead, as in
 384     //    s[0] = 0;
 385     //    s[1] = 0; // This has just been deleted.
 386     //    free(s);
 387     Dep = MD->getDependency(F);
 388   } while (!Dep.isNonLocal());
 389
 390   return true;
 391 }
 392
 393 /// handleEndBlock - Remove dead stores to stack-allocated locations in the
 394 /// function end block.  Ex:
 395 /// %A = alloca i32
 396 /// ...
 397 /// store i32 1, i32* %A
 398 /// ret void
 399 bool DSE::handleEndBlock(BasicBlock &BB) {
 400   bool MadeChange = false;
 401
 402   // Pointers alloca'd in this function are dead in the end block
 403   SmallPtrSet<Value*, 64> deadPointers;
 404
 405   // Find all of the alloca'd pointers in the entry block.
 406   BasicBlock *Entry = BB.getParent()->begin();
 407   for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I)
 408     if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
 409       deadPointers.insert(AI);
 410
 411   // Treat byval arguments the same, stores to them are dead at the end of the
 412   // function.
 413   for (Function::arg_iterator AI = BB.getParent()->arg_begin(),
 414        AE = BB.getParent()->arg_end(); AI != AE; ++AI)
 415     if (AI->hasByValAttr())
 416       deadPointers.insert(AI);
 417
 418   // Scan the basic block backwards
 419   for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
 420     --BBI;
 421
 422     // If we find a store whose pointer is dead.
 423     if (hasMemoryWrite(BBI)) {
 424       if (isRemovable(BBI)) {
 425         // See through pointer-to-pointer bitcasts
 426         Value *pointerOperand = getPointerOperand(BBI)->getUnderlyingObject();
 427
 428         // Alloca'd pointers or byval arguments (which are functionally like
 429         // alloca's) are valid candidates for removal.
 430         if (deadPointers.count(pointerOperand)) {
 431           // DCE instructions only used to calculate that store.
 432           Instruction *Dead = BBI;
 433           ++BBI;
 434           DeleteDeadInstruction(Dead, &deadPointers);
 435           ++NumFastStores;
 436           MadeChange = true;
 437           continue;
 438         }
 439       }
 440
 441       // Because a memcpy or memmove is also a load, we can't skip it if we
 442       // didn't remove it.
 443       if (!isa<MemTransferInst>(BBI))
 444         continue;
 445     }
 446
 447     Value *killPointer = 0;
 448     uint64_t killPointerSize = AliasAnalysis::UnknownSize;
 449
 450     // If we encounter a use of the pointer, it is no longer considered dead
 451     if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
 452       // However, if this load is unused and not volatile, we can go ahead and
 453       // remove it, and not have to worry about it making our pointer undead!
 454       if (L->use_empty() && !L->isVolatile()) {
 455         ++BBI;
 456         DeleteDeadInstruction(L, &deadPointers);
 457         ++NumFastOther;
 458         MadeChange = true;
 459         continue;
 460       }
 461
 462       killPointer = L->getPointerOperand();
 463     } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
 464       killPointer = V->getOperand(0);
 465     } else if (isa<MemTransferInst>(BBI) &&
 466                isa<ConstantInt>(cast<MemTransferInst>(BBI)->getLength())) {
 467       killPointer = cast<MemTransferInst>(BBI)->getSource();
 468       killPointerSize = cast<ConstantInt>(
 469                        cast<MemTransferInst>(BBI)->getLength())->getZExtValue();
 470     } else if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) {
 471       deadPointers.erase(A);
 472
 473       // Dead alloca's can be DCE'd when we reach them
 474       if (A->use_empty()) {
 475         ++BBI;
 476         DeleteDeadInstruction(A, &deadPointers);
 477         ++NumFastOther;
 478         MadeChange = true;
 479       }
 480
 481       continue;
 482     } else if (CallSite CS = cast<Value>(BBI)) {
 483       // If this call does not access memory, it can't
 484       // be undeadifying any of our pointers.
 485       if (AA->doesNotAccessMemory(CS))
 486         continue;
 487
 488       unsigned modRef = 0;
 489       unsigned other = 0;
 490
 491       // Remove any pointers made undead by the call from the dead set
 492       std::vector<Value*> dead;
 493       for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(),
 494            E = deadPointers.end(); I != E; ++I) {
 495         // HACK: if we detect that our AA is imprecise, it's not
 496         // worth it to scan the rest of the deadPointers set.  Just
 497         // assume that the AA will return ModRef for everything, and
 498         // go ahead and bail.
 499         if (modRef >= 16 && other == 0) {
 500           deadPointers.clear();
 501           return MadeChange;
 502         }
 503
 504         // See if the call site touches it
 505         AliasAnalysis::ModRefResult A =
 506           AA->getModRefInfo(CS, *I, getPointerSize(*I, *AA));
 507
 508         if (A == AliasAnalysis::ModRef)
 509           ++modRef;
 510         else
 511           ++other;
 512
 513         if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref)
 514           dead.push_back(*I);
 515       }
 516
 517       for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end();
 518            I != E; ++I)
 519         deadPointers.erase(*I);
 520
 521       continue;
 522     } else if (isInstructionTriviallyDead(BBI)) {
 523       // For any non-memory-affecting non-terminators, DCE them as we reach them
 524       Instruction *Inst = BBI;
 525       ++BBI;
 526       DeleteDeadInstruction(Inst, &deadPointers);
 527       ++NumFastOther;
 528       MadeChange = true;
 529       continue;
 530     }
 531
 532     if (!killPointer)
 533       continue;
 534
 535     killPointer = killPointer->getUnderlyingObject();
 536
 537     // Deal with undead pointers
 538     MadeChange |= RemoveUndeadPointers(killPointer, killPointerSize, BBI,
 539                                        deadPointers);
 540   }
 541
 542   return MadeChange;
 543 }
 544
 545 /// RemoveUndeadPointers - check for uses of a pointer that make it
 546 /// undead when scanning for dead stores to alloca's.
 547 bool DSE::RemoveUndeadPointers(Value *killPointer, uint64_t killPointerSize,
 548                                BasicBlock::iterator &BBI,
 549                                SmallPtrSet<Value*, 64> &deadPointers) {
 550   // If the kill pointer can be easily reduced to an alloca,
 551   // don't bother doing extraneous AA queries.
 552   if (deadPointers.count(killPointer)) {
 553     deadPointers.erase(killPointer);
 554     return false;
 555   }
 556
 557   // A global can't be in the dead pointer set.
 558   if (isa<GlobalValue>(killPointer))
 559     return false;
 560
 561   bool MadeChange = false;
 562
 563   SmallVector<Value*, 16> undead;
 564
 565   for (SmallPtrSet<Value*, 64>::iterator I = deadPointers.begin(),
 566        E = deadPointers.end(); I != E; ++I) {
 567     // See if this pointer could alias it
 568     AliasAnalysis::AliasResult A = AA->alias(*I, getPointerSize(*I, *AA),
 569                                              killPointer, killPointerSize);
 570
 571     // If it must-alias and a store, we can delete it
 572     if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) {
 573       StoreInst *S = cast<StoreInst>(BBI);
 574
 575       // Remove it!
 576       ++BBI;
 577       DeleteDeadInstruction(S, &deadPointers);
 578       ++NumFastStores;
 579       MadeChange = true;
 580
 581       continue;
 582
 583       // Otherwise, it is undead
 584     } else if (A != AliasAnalysis::NoAlias)
 585       undead.push_back(*I);
 586   }
 587
 588   for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end();
 589        I != E; ++I)
 590     deadPointers.erase(*I);
 591
 592   return MadeChange;
 593 }
 594
 595 /// DeleteDeadInstruction - Delete this instruction.  Before we do, go through
 596 /// and zero out all the operands of this instruction.  If any of them become
 597 /// dead, delete them and the computation tree that feeds them.
 598 ///
 599 /// If ValueSet is non-null, remove any deleted instructions from it as well.
 600 ///
 601 void DSE::DeleteDeadInstruction(Instruction *I,
 602                                 SmallPtrSet<Value*, 64> *ValueSet) {
 603   SmallVector<Instruction*, 32> NowDeadInsts;
 604
 605   NowDeadInsts.push_back(I);
 606   --NumFastOther;
 607
 608   // Before we touch this instruction, remove it from memdep!
 609   do {
 610     Instruction *DeadInst = NowDeadInsts.pop_back_val();
 611
 612     ++NumFastOther;
 613
 614     // This instruction is dead, zap it, in stages.  Start by removing it from
 615     // MemDep, which needs to know the operands and needs it to be in the
 616     // function.
 617     MD->removeInstruction(DeadInst);
 618
 619     for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
 620       Value *Op = DeadInst->getOperand(op);
 621       DeadInst->setOperand(op, 0);
 622
 623       // If this operand just became dead, add it to the NowDeadInsts list.
 624       if (!Op->use_empty()) continue;
 625
 626       if (Instruction *OpI = dyn_cast<Instruction>(Op))
 627         if (isInstructionTriviallyDead(OpI))
 628           NowDeadInsts.push_back(OpI);
 629     }
 630
 631     DeadInst->eraseFromParent();
 632
 633     if (ValueSet) ValueSet->erase(DeadInst);
 634   } while (!NowDeadInsts.empty());
 635 }
 636