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