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 RemoveAccessedObjects(Value *Ptr, uint64_t killPointerSize,
  68                                BasicBlock::iterator &BBI,
  69                                SmallPtrSet<Value*, 16> &deadPointers);
  70     void DeleteDeadInstruction(Instruction *I,
  71                                SmallPtrSet<Value*, 16> *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   // Keep track of all of the stack objects that are dead at the end of the
 403   // function.
 404   SmallPtrSet<Value*, 16> DeadStackObjects;
 405
 406   // Find all of the alloca'd pointers in the entry block.
 407   BasicBlock *Entry = BB.getParent()->begin();
 408   for (BasicBlock::iterator I = Entry->begin(), E = Entry->end(); I != E; ++I)
 409     if (AllocaInst *AI = dyn_cast<AllocaInst>(I))
 410       DeadStackObjects.insert(AI);
 411
 412   // Treat byval arguments the same, stores to them are dead at the end of the
 413   // function.
 414   for (Function::arg_iterator AI = BB.getParent()->arg_begin(),
 415        AE = BB.getParent()->arg_end(); AI != AE; ++AI)
 416     if (AI->hasByValAttr())
 417       DeadStackObjects.insert(AI);
 418
 419   // Scan the basic block backwards
 420   for (BasicBlock::iterator BBI = BB.end(); BBI != BB.begin(); ){
 421     --BBI;
 422
 423     // If we find a store, check to see if it points into a dead stack value.
 424     if (hasMemoryWrite(BBI) && isRemovable(BBI)) {
 425       // See through pointer-to-pointer bitcasts
 426       Value *Pointer = 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 (DeadStackObjects.count(Pointer)) {
 431         // DCE instructions only used to calculate that store.
 432         Instruction *Dead = BBI++;
 433         DeleteDeadInstruction(Dead, &DeadStackObjects);
 434         ++NumFastStores;
 435         MadeChange = true;
 436         continue;
 437       }
 438     }
 439
 440     // Remove any dead non-memory-mutating instructions.
 441     if (isInstructionTriviallyDead(BBI)) {
 442       Instruction *Inst = BBI++;
 443       DeleteDeadInstruction(Inst, &DeadStackObjects);
 444       ++NumFastOther;
 445       MadeChange = true;
 446       continue;
 447     }
 448
 449     if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) {
 450       DeadStackObjects.erase(A);
 451       continue;
 452     }
 453
 454     if (CallSite CS = cast<Value>(BBI)) {
 455       // If this call does not access memory, it can't be loading any of our
 456       // pointers.
 457       if (AA->doesNotAccessMemory(CS))
 458         continue;
 459
 460       unsigned NumModRef = 0, NumOther = 0;
 461
 462       // If the call might load from any of our allocas, then any store above
 463       // the call is live.
 464       SmallVector<Value*, 8> LiveAllocas;
 465       for (SmallPtrSet<Value*, 16>::iterator I = DeadStackObjects.begin(),
 466            E = DeadStackObjects.end(); I != E; ++I) {
 467         // If we detect that our AA is imprecise, it's not worth it to scan the
 468         // rest of the DeadPointers set.  Just assume that the AA will return
 469         // ModRef for everything, and go ahead and bail out.
 470         if (NumModRef >= 16 && NumOther == 0)
 471           return MadeChange;
 472
 473         // See if the call site touches it.
 474         AliasAnalysis::ModRefResult A =
 475           AA->getModRefInfo(CS, *I, getPointerSize(*I, *AA));
 476
 477         if (A == AliasAnalysis::ModRef)
 478           ++NumModRef;
 479         else
 480           ++NumOther;
 481
 482         if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref)
 483           LiveAllocas.push_back(*I);
 484       }
 485
 486       for (SmallVector<Value*, 8>::iterator I = LiveAllocas.begin(),
 487            E = LiveAllocas.end(); I != E; ++I)
 488         DeadStackObjects.erase(*I);
 489
 490       // If all of the allocas were clobbered by the call then we're not going
 491       // to find anything else to process.
 492       if (DeadStackObjects.empty())
 493         return MadeChange;
 494
 495       continue;
 496     }
 497
 498     Value *KillPointer = 0;
 499     uint64_t KillPointerSize = AliasAnalysis::UnknownSize;
 500
 501     // If we encounter a use of the pointer, it is no longer considered dead
 502     if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
 503       KillPointer = L->getPointerOperand();
 504     } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
 505       KillPointer = V->getOperand(0);
 506     } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) {
 507       KillPointer = cast<MemTransferInst>(BBI)->getSource();
 508       if (ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength()))
 509         KillPointerSize = Len->getZExtValue();
 510     } else {
 511       // Not a loading instruction.
 512       continue;
 513     }
 514
 515     // Remove any allocas from the DeadPointer set that are loaded, as this
 516     // makes any stores above the access live.
 517     MadeChange |= RemoveAccessedObjects(KillPointer, KillPointerSize, BBI,
 518                                         DeadStackObjects);
 519
 520     // If all of the allocas were clobbered by the access then we're not going
 521     // to find anything else to process.
 522     if (DeadStackObjects.empty())
 523       break;
 524   }
 525
 526   return MadeChange;
 527 }
 528
 529 /// RemoveAccessedObjects - Check to see if the specified location may alias any
 530 /// of the stack objects in the DeadStackObjects set.  If so, they become live
 531 /// because the location is being loaded.
 532 bool DSE::RemoveAccessedObjects(Value *KillPointer, uint64_t KillPointerSize,
 533                                 BasicBlock::iterator &BBI,
 534                                 SmallPtrSet<Value*, 16> &DeadStackObjects) {
 535   Value *UnderlyingPointer = KillPointer->getUnderlyingObject();
 536
 537   // A constant can't be in the dead pointer set.
 538   if (isa<Constant>(UnderlyingPointer))
 539     return false;
 540
 541   // If the kill pointer can be easily reduced to an alloca, don't bother doing
 542   // extraneous AA queries.
 543   if (DeadStackObjects.count(UnderlyingPointer)) {
 544     DeadStackObjects.erase(UnderlyingPointer);
 545     return false;
 546   }
 547
 548   bool MadeChange = false;
 549   SmallVector<Value*, 16> NowLive;
 550
 551   for (SmallPtrSet<Value*, 16>::iterator I = DeadStackObjects.begin(),
 552        E = DeadStackObjects.end(); I != E; ++I) {
 553     // See if this pointer could alias it
 554     AliasAnalysis::AliasResult A = AA->alias(*I, getPointerSize(*I, *AA),
 555                                              KillPointer, KillPointerSize);
 556
 557     // If it must-alias and a store, we can delete it
 558     if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) {
 559       StoreInst *S = cast<StoreInst>(BBI);
 560
 561       // Remove it!
 562       ++BBI;
 563       DeleteDeadInstruction(S, &DeadStackObjects);
 564       ++NumFastStores;
 565       MadeChange = true;
 566
 567       continue;
 568
 569       // Otherwise, it is undead
 570     } else if (A != AliasAnalysis::NoAlias)
 571       NowLive.push_back(*I);
 572   }
 573
 574   for (SmallVector<Value*, 16>::iterator I = NowLive.begin(), E = NowLive.end();
 575        I != E; ++I)
 576     DeadStackObjects.erase(*I);
 577
 578   return MadeChange;
 579 }
 580
 581 /// DeleteDeadInstruction - Delete this instruction.  Before we do, go through
 582 /// and zero out all the operands of this instruction.  If any of them become
 583 /// dead, delete them and the computation tree that feeds them.
 584 ///
 585 /// If ValueSet is non-null, remove any deleted instructions from it as well.
 586 ///
 587 void DSE::DeleteDeadInstruction(Instruction *I,
 588                                 SmallPtrSet<Value*, 16> *ValueSet) {
 589   SmallVector<Instruction*, 32> NowDeadInsts;
 590
 591   NowDeadInsts.push_back(I);
 592   --NumFastOther;
 593
 594   // Before we touch this instruction, remove it from memdep!
 595   do {
 596     Instruction *DeadInst = NowDeadInsts.pop_back_val();
 597
 598     ++NumFastOther;
 599
 600     // This instruction is dead, zap it, in stages.  Start by removing it from
 601     // MemDep, which needs to know the operands and needs it to be in the
 602     // function.
 603     MD->removeInstruction(DeadInst);
 604
 605     for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
 606       Value *Op = DeadInst->getOperand(op);
 607       DeadInst->setOperand(op, 0);
 608
 609       // If this operand just became dead, add it to the NowDeadInsts list.
 610       if (!Op->use_empty()) continue;
 611
 612       if (Instruction *OpI = dyn_cast<Instruction>(Op))
 613         if (isInstructionTriviallyDead(OpI))
 614           NowDeadInsts.push_back(OpI);
 615     }
 616
 617     DeadInst->eraseFromParent();
 618
 619     if (ValueSet) ValueSet->erase(DeadInst);
 620   } while (!NowDeadInsts.empty());
 621 }
 622