lib/Analysis/MemoryDependenceAnalysis.cpp

   1 //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation  --*- C++ -*-===//
   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 an analysis that determines, for a given memory
  11 // operation, what preceding memory operations it depends on.  It builds on
  12 // alias analysis information, and tries to provide a lazy, caching interface to
  13 // a common kind of alias information query.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #define DEBUG_TYPE "memdep"
  18 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
  19 #include "llvm/Constants.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/Analysis/AliasAnalysis.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include "llvm/ADT/STLExtras.h"
  25 #include "llvm/Support/CFG.h"
  26 #include "llvm/Support/CommandLine.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Target/TargetData.h"
  29 using namespace llvm;
  30
  31 // Control the calculation of non-local dependencies by only examining the
  32 // predecessors if the basic block has less than X amount (50 by default).
  33 static cl::opt<int>
  34 PredLimit("nonlocaldep-threshold", cl::Hidden, cl::init(50),
  35           cl::desc("Control the calculation of non-local"
  36                    "dependencies (default = 50)"));
  37
  38 STATISTIC(NumCacheNonlocal, "Number of cached non-local responses");
  39 STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses");
  40
  41 char MemoryDependenceAnalysis::ID = 0;
  42
  43 // Register this pass...
  44 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
  45                                      "Memory Dependence Analysis", false, true);
  46
  47 /// verifyRemoved - Verify that the specified instruction does not occur
  48 /// in our internal data structures.
  49 void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
  50   for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
  51        E = LocalDeps.end(); I != E; ++I) {
  52     assert(I->first != D && "Inst occurs in data structures");
  53     assert(I->second.getPointer() != D &&
  54            "Inst occurs in data structures");
  55   }
  56
  57   for (nonLocalDepMapType::const_iterator I = depGraphNonLocal.begin(),
  58        E = depGraphNonLocal.end(); I != E; ++I) {
  59     assert(I->first != D && "Inst occurs in data structures");
  60     for (DenseMap<BasicBlock*, DepResultTy>::iterator II = I->second.begin(),
  61          EE = I->second.end(); II  != EE; ++II)
  62       assert(II->second.getPointer() != D && "Inst occurs in data structures");
  63   }
  64
  65   for (reverseDepMapType::const_iterator I = reverseDep.begin(),
  66        E = reverseDep.end(); I != E; ++I)
  67     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
  68          EE = I->second.end(); II != EE; ++II)
  69       assert(*II != D && "Inst occurs in data structures");
  70
  71   for (reverseDepMapType::const_iterator I = reverseDepNonLocal.begin(),
  72        E = reverseDepNonLocal.end();
  73        I != E; ++I)
  74     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
  75          EE = I->second.end(); II != EE; ++II)
  76       assert(*II != D && "Inst occurs in data structures");
  77 }
  78
  79 /// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
  80 ///
  81 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
  82   AU.setPreservesAll();
  83   AU.addRequiredTransitive<AliasAnalysis>();
  84   AU.addRequiredTransitive<TargetData>();
  85 }
  86
  87 /// getCallSiteDependency - Private helper for finding the local dependencies
  88 /// of a call site.
  89 MemDepResult MemoryDependenceAnalysis::
  90 getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt,
  91                       BasicBlock *BB) {
  92   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
  93   TargetData &TD = getAnalysis<TargetData>();
  94
  95   // Walk backwards through the block, looking for dependencies
  96   while (ScanIt != BB->begin()) {
  97     Instruction *Inst = --ScanIt;
  98
  99     // If this inst is a memory op, get the pointer it accessed
 100     Value *Pointer = 0;
 101     uint64_t PointerSize = 0;
 102     if (StoreInst *S = dyn_cast<StoreInst>(Inst)) {
 103       Pointer = S->getPointerOperand();
 104       PointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
 105     } else if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
 106       Pointer = AI;
 107       if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize()))
 108         PointerSize = C->getZExtValue() *
 109                       TD.getTypeStoreSize(AI->getAllocatedType());
 110       else
 111         PointerSize = ~0UL;
 112     } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
 113       Pointer = V->getOperand(0);
 114       PointerSize = TD.getTypeStoreSize(V->getType());
 115     } else if (FreeInst *F = dyn_cast<FreeInst>(Inst)) {
 116       Pointer = F->getPointerOperand();
 117
 118       // FreeInsts erase the entire structure
 119       PointerSize = ~0UL;
 120     } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
 121       if (AA.getModRefBehavior(CallSite::get(Inst)) ==
 122             AliasAnalysis::DoesNotAccessMemory)
 123         continue;
 124       return MemDepResult::get(Inst);
 125     } else
 126       continue;
 127
 128     if (AA.getModRefInfo(C, Pointer, PointerSize) != AliasAnalysis::NoModRef)
 129       return MemDepResult::get(Inst);
 130   }
 131
 132   // No dependence found.
 133   return MemDepResult::getNonLocal();
 134 }
 135
 136 /// nonLocalHelper - Private helper used to calculate non-local dependencies
 137 /// by doing DFS on the predecessors of a block to find its dependencies.
 138 void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
 139                                               BasicBlock* block,
 140                                      DenseMap<BasicBlock*, DepResultTy> &resp) {
 141   // Set of blocks that we've already visited in our DFS
 142   SmallPtrSet<BasicBlock*, 4> visited;
 143   // If we're updating a dirtied cache entry, we don't need to reprocess
 144   // already computed entries.
 145   for (DenseMap<BasicBlock*, DepResultTy>::iterator I = resp.begin(),
 146        E = resp.end(); I != E; ++I)
 147     if (I->second.getInt() != Dirty)
 148       visited.insert(I->first);
 149
 150   // Current stack of the DFS
 151   SmallVector<BasicBlock*, 4> stack;
 152   for (pred_iterator PI = pred_begin(block), PE = pred_end(block);
 153        PI != PE; ++PI)
 154     stack.push_back(*PI);
 155
 156   // Do a basic DFS
 157   while (!stack.empty()) {
 158     BasicBlock* BB = stack.back();
 159
 160     // If we've already visited this block, no need to revist
 161     if (visited.count(BB)) {
 162       stack.pop_back();
 163       continue;
 164     }
 165
 166     // If we find a new block with a local dependency for query,
 167     // then we insert the new dependency and backtrack.
 168     if (BB != block) {
 169       visited.insert(BB);
 170
 171       MemDepResult localDep = getDependencyFrom(query, BB->end(), BB);
 172       if (!localDep.isNonLocal()) {
 173         resp.insert(std::make_pair(BB, ConvFromResult(localDep)));
 174         stack.pop_back();
 175         continue;
 176       }
 177     // If we re-encounter the starting block, we still need to search it
 178     // because there might be a dependency in the starting block AFTER
 179     // the position of the query.  This is necessary to get loops right.
 180     } else if (BB == block) {
 181       visited.insert(BB);
 182
 183       MemDepResult localDep = getDependencyFrom(query, BB->end(), BB);
 184       if (localDep.getInst() != query)
 185         resp.insert(std::make_pair(BB, ConvFromResult(localDep)));
 186
 187       stack.pop_back();
 188       continue;
 189     }
 190
 191     // If we didn't find anything, recurse on the precessors of this block
 192     // Only do this for blocks with a small number of predecessors.
 193     bool predOnStack = false;
 194     bool inserted = false;
 195     if (std::distance(pred_begin(BB), pred_end(BB)) <= PredLimit) {
 196       for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
 197            PI != PE; ++PI)
 198         if (!visited.count(*PI)) {
 199           stack.push_back(*PI);
 200           inserted = true;
 201         } else
 202           predOnStack = true;
 203     }
 204
 205     // If we inserted a new predecessor, then we'll come back to this block
 206     if (inserted)
 207       continue;
 208     // If we didn't insert because we have no predecessors, then this
 209     // query has no dependency at all.
 210     else if (!inserted && !predOnStack) {
 211       resp.insert(std::make_pair(BB, DepResultTy(0, None)));
 212     // If we didn't insert because our predecessors are already on the stack,
 213     // then we might still have a dependency, but it will be discovered during
 214     // backtracking.
 215     } else if (!inserted && predOnStack){
 216       resp.insert(std::make_pair(BB, DepResultTy(0, NonLocal)));
 217     }
 218
 219     stack.pop_back();
 220   }
 221 }
 222
 223 /// getNonLocalDependency - Fills the passed-in map with the non-local
 224 /// dependencies of the queries.  The map will contain NonLocal for
 225 /// blocks between the query and its dependencies.
 226 void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
 227                                     DenseMap<BasicBlock*, MemDepResult> &resp) {
 228   if (depGraphNonLocal.count(query)) {
 229     DenseMap<BasicBlock*, DepResultTy> &cached = depGraphNonLocal[query];
 230     NumCacheNonlocal++;
 231
 232     SmallVector<BasicBlock*, 4> dirtied;
 233     for (DenseMap<BasicBlock*, DepResultTy>::iterator I = cached.begin(),
 234          E = cached.end(); I != E; ++I)
 235       if (I->second.getInt() == Dirty)
 236         dirtied.push_back(I->first);
 237
 238     for (SmallVector<BasicBlock*, 4>::iterator I = dirtied.begin(),
 239          E = dirtied.end(); I != E; ++I) {
 240       MemDepResult localDep = getDependencyFrom(query, (*I)->end(), *I);
 241       if (!localDep.isNonLocal())
 242         cached[*I] = ConvFromResult(localDep);
 243       else {
 244         cached.erase(*I);
 245         nonLocalHelper(query, *I, cached);
 246       }
 247     }
 248
 249     // Update the reverse non-local dependency cache.
 250     for (DenseMap<BasicBlock*, DepResultTy>::iterator I = cached.begin(),
 251          E = cached.end(); I != E; ++I) {
 252       if (Instruction *Inst = I->second.getPointer())
 253         reverseDepNonLocal[Inst].insert(query);
 254       resp[I->first] = ConvToResult(I->second);
 255     }
 256
 257     return;
 258   }
 259
 260   NumUncacheNonlocal++;
 261
 262   // If not, go ahead and search for non-local deps.
 263   DenseMap<BasicBlock*, DepResultTy> &cached = depGraphNonLocal[query];
 264   nonLocalHelper(query, query->getParent(), cached);
 265
 266   // Update the non-local dependency cache
 267   for (DenseMap<BasicBlock*, DepResultTy>::iterator I = cached.begin(),
 268        E = cached.end(); I != E; ++I) {
 269     // FIXME: Merge with the code above!
 270     if (Instruction *Inst = I->second.getPointer())
 271       reverseDepNonLocal[Inst].insert(query);
 272     resp[I->first] = ConvToResult(I->second);
 273   }
 274 }
 275
 276 /// getDependency - Return the instruction on which a memory operation
 277 /// depends.  The local parameter indicates if the query should only
 278 /// evaluate dependencies within the same basic block.
 279 MemDepResult MemoryDependenceAnalysis::
 280 getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt,
 281                   BasicBlock *BB) {
 282   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
 283   TargetData &TD = getAnalysis<TargetData>();
 284
 285   // Get the pointer value for which dependence will be determined
 286   Value *MemPtr = 0;
 287   uint64_t MemSize = 0;
 288   bool MemVolatile = false;
 289
 290   if (StoreInst* S = dyn_cast<StoreInst>(QueryInst)) {
 291     MemPtr = S->getPointerOperand();
 292     MemSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
 293     MemVolatile = S->isVolatile();
 294   } else if (LoadInst* L = dyn_cast<LoadInst>(QueryInst)) {
 295     MemPtr = L->getPointerOperand();
 296     MemSize = TD.getTypeStoreSize(L->getType());
 297     MemVolatile = L->isVolatile();
 298   } else if (VAArgInst* V = dyn_cast<VAArgInst>(QueryInst)) {
 299     MemPtr = V->getOperand(0);
 300     MemSize = TD.getTypeStoreSize(V->getType());
 301   } else if (FreeInst* F = dyn_cast<FreeInst>(QueryInst)) {
 302     MemPtr = F->getPointerOperand();
 303     // FreeInsts erase the entire structure, not just a field.
 304     MemSize = ~0UL;
 305   } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst))
 306     return getCallSiteDependency(CallSite::get(QueryInst), ScanIt, BB);
 307   else  // Non-memory instructions depend on nothing.
 308     return MemDepResult::getNone();
 309
 310   // Walk backwards through the basic block, looking for dependencies
 311   while (ScanIt != BB->begin()) {
 312     Instruction *Inst = --ScanIt;
 313
 314     // If the access is volatile and this is a volatile load/store, return a
 315     // dependence.
 316     if (MemVolatile &&
 317         ((isa<LoadInst>(Inst) && cast<LoadInst>(Inst)->isVolatile()) ||
 318          (isa<StoreInst>(Inst) && cast<StoreInst>(Inst)->isVolatile())))
 319       return MemDepResult::get(Inst);
 320
 321     // MemDep is broken w.r.t. loads: it says that two loads of the same pointer
 322     // depend on each other.  :(
 323     // FIXME: ELIMINATE THIS!
 324     if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
 325       Value *Pointer = L->getPointerOperand();
 326       uint64_t PointerSize = TD.getTypeStoreSize(L->getType());
 327
 328       // If we found a pointer, check if it could be the same as our pointer
 329       AliasAnalysis::AliasResult R =
 330         AA.alias(Pointer, PointerSize, MemPtr, MemSize);
 331
 332       if (R == AliasAnalysis::NoAlias)
 333         continue;
 334
 335       // May-alias loads don't depend on each other without a dependence.
 336       if (isa<LoadInst>(QueryInst) && R == AliasAnalysis::MayAlias)
 337         continue;
 338       return MemDepResult::get(Inst);
 339     }
 340
 341     // FIXME: This claims that an access depends on the allocation.  This may
 342     // make sense, but is dubious at best.  It would be better to fix GVN to
 343     // handle a 'None' Query.
 344     if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
 345       Value *Pointer = AI;
 346       uint64_t PointerSize;
 347       if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize()))
 348         PointerSize = C->getZExtValue() *
 349           TD.getTypeStoreSize(AI->getAllocatedType());
 350       else
 351         PointerSize = ~0UL;
 352
 353       AliasAnalysis::AliasResult R =
 354         AA.alias(Pointer, PointerSize, MemPtr, MemSize);
 355
 356       if (R == AliasAnalysis::NoAlias)
 357         continue;
 358       return MemDepResult::get(Inst);
 359     }
 360
 361
 362     // See if this instruction mod/ref's the pointer.
 363     AliasAnalysis::ModRefResult MRR = AA.getModRefInfo(Inst, MemPtr, MemSize);
 364
 365     if (MRR == AliasAnalysis::NoModRef)
 366       continue;
 367
 368     // Loads don't depend on read-only instructions.
 369     if (isa<LoadInst>(QueryInst) && MRR == AliasAnalysis::Ref)
 370       continue;
 371
 372     // Otherwise, there is a dependence.
 373     return MemDepResult::get(Inst);
 374   }
 375
 376   // If we found nothing, return the non-local flag.
 377   return MemDepResult::getNonLocal();
 378 }
 379
 380 /// getDependency - Return the instruction on which a memory operation
 381 /// depends.
 382 MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
 383   Instruction *ScanPos = QueryInst;
 384
 385   // Check for a cached result
 386   DepResultTy &LocalCache = LocalDeps[QueryInst];
 387
 388   // If the cached entry is non-dirty, just return it.
 389   if (LocalCache.getInt() != Dirty)
 390     return ConvToResult(LocalCache);
 391
 392   // Otherwise, if we have a dirty entry, we know we can start the scan at that
 393   // instruction, which may save us some work.
 394   if (Instruction *Inst = LocalCache.getPointer())
 395     ScanPos = Inst;
 396
 397   // Do the scan.
 398   MemDepResult Res =
 399     getDependencyFrom(QueryInst, ScanPos, QueryInst->getParent());
 400
 401   // Remember the result!
 402   // FIXME: Don't convert back and forth!  Make a shared helper function.
 403   LocalCache = ConvFromResult(Res);
 404   if (Instruction *I = Res.getInst())
 405     reverseDep[I].insert(QueryInst);
 406
 407   return Res;
 408 }
 409
 410
 411 /// dropInstruction - Remove an instruction from the analysis, making
 412 /// absolutely conservative assumptions when updating the cache.  This is
 413 /// useful, for example when an instruction is changed rather than removed.
 414 void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) {
 415   LocalDepMapType::iterator depGraphEntry = LocalDeps.find(drop);
 416   if (depGraphEntry != LocalDeps.end())
 417     if (Instruction *Inst = depGraphEntry->second.getPointer())
 418       reverseDep[Inst].erase(drop);
 419
 420   // Drop dependency information for things that depended on this instr
 421   SmallPtrSet<Instruction*, 4>& set = reverseDep[drop];
 422   for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 423        I != E; ++I)
 424     LocalDeps.erase(*I);
 425
 426   LocalDeps.erase(drop);
 427   reverseDep.erase(drop);
 428
 429   for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
 430          depGraphNonLocal[drop].begin(), DE = depGraphNonLocal[drop].end();
 431        DI != DE; ++DI)
 432     if (Instruction *Inst = DI->second.getPointer())
 433       reverseDepNonLocal[Inst].erase(drop);
 434
 435   if (reverseDepNonLocal.count(drop)) {
 436     SmallPtrSet<Instruction*, 4>& set =
 437       reverseDepNonLocal[drop];
 438     for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 439          I != E; ++I)
 440       for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
 441            depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end();
 442            DI != DE; ++DI)
 443         if (DI->second == DepResultTy(drop, Normal))
 444           // FIXME: Why not remember the old insertion point??
 445           DI->second = DepResultTy(0, Dirty);
 446   }
 447
 448   reverseDepNonLocal.erase(drop);
 449   depGraphNonLocal.erase(drop);
 450 }
 451
 452 /// removeInstruction - Remove an instruction from the dependence analysis,
 453 /// updating the dependence of instructions that previously depended on it.
 454 /// This method attempts to keep the cache coherent using the reverse map.
 455 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
 456   // Walk through the Non-local dependencies, removing this one as the value
 457   // for any cached queries.
 458   for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
 459        depGraphNonLocal[RemInst].begin(), DE = depGraphNonLocal[RemInst].end();
 460        DI != DE; ++DI)
 461     if (Instruction *Inst = DI->second.getPointer())
 462       reverseDepNonLocal[Inst].erase(RemInst);
 463
 464   // Shortly after this, we will look for things that depend on RemInst.  In
 465   // order to update these, we'll need a new dependency to base them on.  We
 466   // could completely delete any entries that depend on this, but it is better
 467   // to make a more accurate approximation where possible.  Compute that better
 468   // approximation if we can.
 469   DepResultTy NewDependency;
 470
 471   // If we have a cached local dependence query for this instruction, remove it.
 472   //
 473   LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
 474   if (LocalDepEntry != LocalDeps.end()) {
 475     DepResultTy LocalDep = LocalDepEntry->second;
 476
 477     // Remove this local dependency info.
 478     LocalDeps.erase(LocalDepEntry);
 479
 480     // Remove us from DepInst's reverse set now that the local dep info is gone.
 481     if (Instruction *Inst = LocalDep.getPointer())
 482       reverseDep[Inst].erase(RemInst);
 483
 484     // If we have unconfirmed info, don't trust it.
 485     if (LocalDep.getInt() != Dirty) {
 486       // If we have a confirmed non-local flag, use it.
 487       if (LocalDep.getInt() == NonLocal || LocalDep.getInt() == None) {
 488         // The only time this dependency is confirmed is if it is non-local.
 489         NewDependency = LocalDep;
 490       } else {
 491         // If we have dep info for RemInst, set them to it.
 492         Instruction *NDI = next(BasicBlock::iterator(LocalDep.getPointer()));
 493         if (NDI != RemInst) // Don't use RemInst for the new dependency!
 494           NewDependency = DepResultTy(NDI, Dirty);
 495       }
 496     }
 497   }
 498
 499   // If we don't already have a local dependency answer for this instruction,
 500   // use the immediate successor of RemInst.  We use the successor because
 501   // getDependence starts by checking the immediate predecessor of what is in
 502   // the cache.
 503   if (NewDependency == DepResultTy(0, Dirty))
 504     NewDependency = DepResultTy(next(BasicBlock::iterator(RemInst)), Dirty);
 505
 506   // Loop over all of the things that depend on the instruction we're removing.
 507   //
 508   reverseDepMapType::iterator ReverseDepIt = reverseDep.find(RemInst);
 509   if (ReverseDepIt != reverseDep.end()) {
 510     SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
 511     for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
 512          E = ReverseDeps.end(); I != E; ++I) {
 513       Instruction *InstDependingOnRemInst = *I;
 514
 515       // If we thought the instruction depended on itself (possible for
 516       // unconfirmed dependencies) ignore the update.
 517       if (InstDependingOnRemInst == RemInst) continue;
 518
 519       // Insert the new dependencies.
 520       LocalDeps[InstDependingOnRemInst] = NewDependency;
 521
 522       // If our NewDependency is an instruction, make sure to remember that new
 523       // things depend on it.
 524       if (Instruction *Inst = NewDependency.getPointer())
 525         reverseDep[Inst].insert(InstDependingOnRemInst);
 526     }
 527     reverseDep.erase(RemInst);
 528   }
 529
 530   ReverseDepIt = reverseDepNonLocal.find(RemInst);
 531   if (ReverseDepIt != reverseDepNonLocal.end()) {
 532     SmallPtrSet<Instruction*, 4>& set = ReverseDepIt->second;
 533     for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 534          I != E; ++I)
 535       for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
 536            depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end();
 537            DI != DE; ++DI)
 538         if (DI->second == DepResultTy(RemInst, Normal))
 539           // FIXME: Why not remember the old insertion point??
 540           DI->second = DepResultTy(0, Dirty);
 541     reverseDepNonLocal.erase(ReverseDepIt);
 542   }
 543
 544   depGraphNonLocal.erase(RemInst);
 545
 546   getAnalysis<AliasAnalysis>().deleteValue(RemInst);
 547
 548   DEBUG(verifyRemoved(RemInst));
 549 }