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, 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 (DeadPointers.count(Pointer)) {
 430         // DCE instructions only used to calculate that store.
 431         Instruction *Dead = BBI++;
 432         DeleteDeadInstruction(Dead, &DeadPointers);
 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, &DeadPointers);
 443       ++NumFastOther;
 444       MadeChange = true;
 445       continue;
 446     }
 447
 448     if (AllocaInst *A = dyn_cast<AllocaInst>(BBI)) {
 449       DeadPointers.erase(A);
 450       continue;
 451     }
 452
 453
 454     Value *KillPointer = 0;
 455     uint64_t KillPointerSize = AliasAnalysis::UnknownSize;
 456
 457     // If we encounter a use of the pointer, it is no longer considered dead
 458     if (LoadInst *L = dyn_cast<LoadInst>(BBI)) {
 459       KillPointer = L->getPointerOperand();
 460     } else if (VAArgInst *V = dyn_cast<VAArgInst>(BBI)) {
 461       KillPointer = V->getOperand(0);
 462     } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(BBI)) {
 463       KillPointer = cast<MemTransferInst>(BBI)->getSource();
 464       if (ConstantInt *Len = dyn_cast<ConstantInt>(MTI->getLength()))
 465         KillPointerSize = Len->getZExtValue();
 466     } else if (CallSite CS = cast<Value>(BBI)) {
 467       // If this call does not access memory, it can't be loading any of our
 468       // pointers.
 469       if (AA->doesNotAccessMemory(CS))
 470         continue;
 471
 472       unsigned NumModRef = 0;
 473       unsigned NumOther = 0;
 474
 475       // Remove any pointers made undead by the call from the dead set
 476       std::vector<Value*> dead;
 477       for (SmallPtrSet<Value*, 64>::iterator I = DeadPointers.begin(),
 478            E = DeadPointers.end(); I != E; ++I) {
 479         // HACK: if we detect that our AA is imprecise, it's not
 480         // worth it to scan the rest of the deadPointers set.  Just
 481         // assume that the AA will return ModRef for everything, and
 482         // go ahead and bail.
 483         if (NumModRef >= 16 && NumOther == 0) {
 484           DeadPointers.clear();
 485           return MadeChange;
 486         }
 487
 488         // See if the call site touches it
 489         AliasAnalysis::ModRefResult A =
 490           AA->getModRefInfo(CS, *I, getPointerSize(*I, *AA));
 491
 492         if (A == AliasAnalysis::ModRef)
 493           ++NumModRef;
 494         else
 495           ++NumOther;
 496
 497         if (A == AliasAnalysis::ModRef || A == AliasAnalysis::Ref)
 498           dead.push_back(*I);
 499       }
 500
 501       for (std::vector<Value*>::iterator I = dead.begin(), E = dead.end();
 502            I != E; ++I)
 503         DeadPointers.erase(*I);
 504
 505       continue;
 506     } else {
 507       // Not a loading instruction.
 508       continue;
 509     }
 510
 511     KillPointer = KillPointer->getUnderlyingObject();
 512
 513     // Deal with undead pointers
 514     MadeChange |= RemoveUndeadPointers(KillPointer, KillPointerSize, BBI,
 515                                        DeadPointers);
 516   }
 517
 518   return MadeChange;
 519 }
 520
 521 /// RemoveUndeadPointers - check for uses of a pointer that make it
 522 /// undead when scanning for dead stores to alloca's.
 523 bool DSE::RemoveUndeadPointers(Value *killPointer, uint64_t killPointerSize,
 524                                BasicBlock::iterator &BBI,
 525                                SmallPtrSet<Value*, 64> &DeadPointers) {
 526   // If the kill pointer can be easily reduced to an alloca,
 527   // don't bother doing extraneous AA queries.
 528   if (DeadPointers.count(killPointer)) {
 529     DeadPointers.erase(killPointer);
 530     return false;
 531   }
 532
 533   // A global can't be in the dead pointer set.
 534   if (isa<GlobalValue>(killPointer))
 535     return false;
 536
 537   bool MadeChange = false;
 538
 539   SmallVector<Value*, 16> undead;
 540
 541   for (SmallPtrSet<Value*, 64>::iterator I = DeadPointers.begin(),
 542        E = DeadPointers.end(); I != E; ++I) {
 543     // See if this pointer could alias it
 544     AliasAnalysis::AliasResult A = AA->alias(*I, getPointerSize(*I, *AA),
 545                                              killPointer, killPointerSize);
 546
 547     // If it must-alias and a store, we can delete it
 548     if (isa<StoreInst>(BBI) && A == AliasAnalysis::MustAlias) {
 549       StoreInst *S = cast<StoreInst>(BBI);
 550
 551       // Remove it!
 552       ++BBI;
 553       DeleteDeadInstruction(S, &DeadPointers);
 554       ++NumFastStores;
 555       MadeChange = true;
 556
 557       continue;
 558
 559       // Otherwise, it is undead
 560     } else if (A != AliasAnalysis::NoAlias)
 561       undead.push_back(*I);
 562   }
 563
 564   for (SmallVector<Value*, 16>::iterator I = undead.begin(), E = undead.end();
 565        I != E; ++I)
 566     DeadPointers.erase(*I);
 567
 568   return MadeChange;
 569 }
 570
 571 /// DeleteDeadInstruction - Delete this instruction.  Before we do, go through
 572 /// and zero out all the operands of this instruction.  If any of them become
 573 /// dead, delete them and the computation tree that feeds them.
 574 ///
 575 /// If ValueSet is non-null, remove any deleted instructions from it as well.
 576 ///
 577 void DSE::DeleteDeadInstruction(Instruction *I,
 578                                 SmallPtrSet<Value*, 64> *ValueSet) {
 579   SmallVector<Instruction*, 32> NowDeadInsts;
 580
 581   NowDeadInsts.push_back(I);
 582   --NumFastOther;
 583
 584   // Before we touch this instruction, remove it from memdep!
 585   do {
 586     Instruction *DeadInst = NowDeadInsts.pop_back_val();
 587
 588     ++NumFastOther;
 589
 590     // This instruction is dead, zap it, in stages.  Start by removing it from
 591     // MemDep, which needs to know the operands and needs it to be in the
 592     // function.
 593     MD->removeInstruction(DeadInst);
 594
 595     for (unsigned op = 0, e = DeadInst->getNumOperands(); op != e; ++op) {
 596       Value *Op = DeadInst->getOperand(op);
 597       DeadInst->setOperand(op, 0);
 598
 599       // If this operand just became dead, add it to the NowDeadInsts list.
 600       if (!Op->use_empty()) continue;
 601
 602       if (Instruction *OpI = dyn_cast<Instruction>(Op))
 603         if (isInstructionTriviallyDead(OpI))
 604           NowDeadInsts.push_back(OpI);
 605     }
 606
 607     DeadInst->eraseFromParent();
 608
 609     if (ValueSet) ValueSet->erase(DeadInst);
 610   } while (!NowDeadInsts.empty());
 611 }
 612