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 STATISTIC(NumCacheNonLocal, "Number of cached non-local responses");
  32 STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");
  33
  34 char MemoryDependenceAnalysis::ID = 0;
  35
  36 // Register this pass...
  37 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
  38                                      "Memory Dependence Analysis", false, true);
  39
  40 /// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
  41 ///
  42 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
  43   AU.setPreservesAll();
  44   AU.addRequiredTransitive<AliasAnalysis>();
  45   AU.addRequiredTransitive<TargetData>();
  46 }
  47
  48 /// getCallSiteDependency - Private helper for finding the local dependencies
  49 /// of a call site.
  50 MemDepResult MemoryDependenceAnalysis::
  51 getCallSiteDependency(CallSite C, BasicBlock::iterator ScanIt,
  52                       BasicBlock *BB) {
  53   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
  54   TargetData &TD = getAnalysis<TargetData>();
  55
  56   // Walk backwards through the block, looking for dependencies
  57   while (ScanIt != BB->begin()) {
  58     Instruction *Inst = --ScanIt;
  59
  60     // If this inst is a memory op, get the pointer it accessed
  61     Value *Pointer = 0;
  62     uint64_t PointerSize = 0;
  63     if (StoreInst *S = dyn_cast<StoreInst>(Inst)) {
  64       Pointer = S->getPointerOperand();
  65       PointerSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
  66     } else if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
  67       Pointer = AI;
  68       if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize()))
  69         // Use ABI size (size between elements), not store size (size of one
  70         // element without padding).
  71         PointerSize = C->getZExtValue() *
  72                       TD.getABITypeSize(AI->getAllocatedType());
  73       else
  74         PointerSize = ~0UL;
  75     } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
  76       Pointer = V->getOperand(0);
  77       PointerSize = TD.getTypeStoreSize(V->getType());
  78     } else if (FreeInst *F = dyn_cast<FreeInst>(Inst)) {
  79       Pointer = F->getPointerOperand();
  80
  81       // FreeInsts erase the entire structure
  82       PointerSize = ~0UL;
  83     } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
  84       if (AA.getModRefBehavior(CallSite::get(Inst)) ==
  85             AliasAnalysis::DoesNotAccessMemory)
  86         continue;
  87       return MemDepResult::get(Inst);
  88     } else
  89       continue;
  90
  91     if (AA.getModRefInfo(C, Pointer, PointerSize) != AliasAnalysis::NoModRef)
  92       return MemDepResult::get(Inst);
  93   }
  94
  95   // No dependence found.
  96   return MemDepResult::getNonLocal();
  97 }
  98
  99 /// getNonLocalDependency - Perform a full dependency query for the
 100 /// specified instruction, returning the set of blocks that the value is
 101 /// potentially live across.  The returned set of results will include a
 102 /// "NonLocal" result for all blocks where the value is live across.
 103 ///
 104 /// This method assumes the instruction returns a "nonlocal" dependency
 105 /// within its own block.
 106 ///
 107 void MemoryDependenceAnalysis::
 108 getNonLocalDependency(Instruction *QueryInst,
 109                       SmallVectorImpl<std::pair<BasicBlock*,
 110                                                       MemDepResult> > &Result) {
 111   assert(getDependency(QueryInst).isNonLocal() &&
 112      "getNonLocalDependency should only be used on insts with non-local deps!");
 113   DenseMap<BasicBlock*, DepResultTy> &Cache = NonLocalDeps[QueryInst];
 114
 115   /// DirtyBlocks - This is the set of blocks that need to be recomputed.  In
 116   /// the cached case, this can happen due to instructions being deleted etc. In
 117   /// the uncached case, this starts out as the set of predecessors we care
 118   /// about.
 119   SmallVector<BasicBlock*, 32> DirtyBlocks;
 120
 121   if (!Cache.empty()) {
 122     // If we already have a partially computed set of results, scan them to
 123     // determine what is dirty, seeding our initial DirtyBlocks worklist.
 124     // FIXME: In the "don't need to be updated" case, this is expensive, why not
 125     // have a per-"cache" flag saying it is undirty?
 126     for (DenseMap<BasicBlock*, DepResultTy>::iterator I = Cache.begin(),
 127          E = Cache.end(); I != E; ++I)
 128       if (I->second.getInt() == Dirty)
 129         DirtyBlocks.push_back(I->first);
 130
 131     NumCacheNonLocal++;
 132
 133     //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
 134     //     << Cache.size() << " cached: " << *QueryInst;
 135   } else {
 136     // Seed DirtyBlocks with each of the preds of QueryInst's block.
 137     BasicBlock *QueryBB = QueryInst->getParent();
 138     DirtyBlocks.append(pred_begin(QueryBB), pred_end(QueryBB));
 139     NumUncacheNonLocal++;
 140   }
 141
 142   // Iterate while we still have blocks to update.
 143   while (!DirtyBlocks.empty()) {
 144     BasicBlock *DirtyBB = DirtyBlocks.back();
 145     DirtyBlocks.pop_back();
 146
 147     // Get the entry for this block.  Note that this relies on DepResultTy
 148     // default initializing to Dirty.
 149     DepResultTy &DirtyBBEntry = Cache[DirtyBB];
 150
 151     // If DirtyBBEntry isn't dirty, it ended up on the worklist multiple times.
 152     if (DirtyBBEntry.getInt() != Dirty) continue;
 153
 154     // Find out if this block has a local dependency for QueryInst.
 155     // FIXME: If the dirty entry has an instruction pointer, scan from it!
 156     // FIXME: Don't convert back and forth for MemDepResult <-> DepResultTy.
 157
 158     // If the dirty entry has a pointer, start scanning from it so we don't have
 159     // to rescan the entire block.
 160     BasicBlock::iterator ScanPos = DirtyBB->end();
 161     if (Instruction *Inst = DirtyBBEntry.getPointer())
 162       ScanPos = Inst;
 163
 164     DirtyBBEntry = ConvFromResult(getDependencyFrom(QueryInst, ScanPos,
 165                                                     DirtyBB));
 166
 167     // If the block has a dependency (i.e. it isn't completely transparent to
 168     // the value), remember it!
 169     if (DirtyBBEntry.getInt() != NonLocal) {
 170       // Keep the ReverseNonLocalDeps map up to date so we can efficiently
 171       // update this when we remove  instructions.
 172       if (Instruction *Inst = DirtyBBEntry.getPointer())
 173         ReverseNonLocalDeps[Inst].insert(QueryInst);
 174       continue;
 175     }
 176
 177     // If the block *is* completely transparent to the load, we need to check
 178     // the predecessors of this block.  Add them to our worklist.
 179     for (pred_iterator I = pred_begin(DirtyBB), E = pred_end(DirtyBB);
 180          I != E; ++I)
 181       DirtyBlocks.push_back(*I);
 182   }
 183
 184   // Copy the result into the output set.
 185   for (DenseMap<BasicBlock*, DepResultTy>::iterator I = Cache.begin(),
 186        E = Cache.end(); I != E; ++I)
 187     Result.push_back(std::make_pair(I->first, ConvToResult(I->second)));
 188 }
 189
 190 /// getDependency - Return the instruction on which a memory operation
 191 /// depends.  The local parameter indicates if the query should only
 192 /// evaluate dependencies within the same basic block.
 193 MemDepResult MemoryDependenceAnalysis::
 194 getDependencyFrom(Instruction *QueryInst, BasicBlock::iterator ScanIt,
 195                   BasicBlock *BB) {
 196   AliasAnalysis &AA = getAnalysis<AliasAnalysis>();
 197   TargetData &TD = getAnalysis<TargetData>();
 198
 199   // Get the pointer value for which dependence will be determined
 200   Value *MemPtr = 0;
 201   uint64_t MemSize = 0;
 202   bool MemVolatile = false;
 203
 204   if (StoreInst* S = dyn_cast<StoreInst>(QueryInst)) {
 205     MemPtr = S->getPointerOperand();
 206     MemSize = TD.getTypeStoreSize(S->getOperand(0)->getType());
 207     MemVolatile = S->isVolatile();
 208   } else if (LoadInst* L = dyn_cast<LoadInst>(QueryInst)) {
 209     MemPtr = L->getPointerOperand();
 210     MemSize = TD.getTypeStoreSize(L->getType());
 211     MemVolatile = L->isVolatile();
 212   } else if (VAArgInst* V = dyn_cast<VAArgInst>(QueryInst)) {
 213     MemPtr = V->getOperand(0);
 214     MemSize = TD.getTypeStoreSize(V->getType());
 215   } else if (FreeInst* F = dyn_cast<FreeInst>(QueryInst)) {
 216     MemPtr = F->getPointerOperand();
 217     // FreeInsts erase the entire structure, not just a field.
 218     MemSize = ~0UL;
 219   } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst))
 220     return getCallSiteDependency(CallSite::get(QueryInst), ScanIt, BB);
 221   else  // Non-memory instructions depend on nothing.
 222     return MemDepResult::getNone();
 223
 224   // Walk backwards through the basic block, looking for dependencies
 225   while (ScanIt != BB->begin()) {
 226     Instruction *Inst = --ScanIt;
 227
 228     // If the access is volatile and this is a volatile load/store, return a
 229     // dependence.
 230     if (MemVolatile &&
 231         ((isa<LoadInst>(Inst) && cast<LoadInst>(Inst)->isVolatile()) ||
 232          (isa<StoreInst>(Inst) && cast<StoreInst>(Inst)->isVolatile())))
 233       return MemDepResult::get(Inst);
 234
 235     // MemDep is broken w.r.t. loads: it says that two loads of the same pointer
 236     // depend on each other.  :(
 237     // FIXME: ELIMINATE THIS!
 238     if (LoadInst *L = dyn_cast<LoadInst>(Inst)) {
 239       Value *Pointer = L->getPointerOperand();
 240       uint64_t PointerSize = TD.getTypeStoreSize(L->getType());
 241
 242       // If we found a pointer, check if it could be the same as our pointer
 243       AliasAnalysis::AliasResult R =
 244         AA.alias(Pointer, PointerSize, MemPtr, MemSize);
 245
 246       if (R == AliasAnalysis::NoAlias)
 247         continue;
 248
 249       // May-alias loads don't depend on each other without a dependence.
 250       if (isa<LoadInst>(QueryInst) && R == AliasAnalysis::MayAlias)
 251         continue;
 252       return MemDepResult::get(Inst);
 253     }
 254
 255     // FIXME: This claims that an access depends on the allocation.  This may
 256     // make sense, but is dubious at best.  It would be better to fix GVN to
 257     // handle a 'None' Query.
 258     if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
 259       Value *Pointer = AI;
 260       uint64_t PointerSize;
 261       if (ConstantInt *C = dyn_cast<ConstantInt>(AI->getArraySize()))
 262         // Use ABI size (size between elements), not store size (size of one
 263         // element without padding).
 264         PointerSize = C->getZExtValue() *
 265           TD.getABITypeSize(AI->getAllocatedType());
 266       else
 267         PointerSize = ~0UL;
 268
 269       AliasAnalysis::AliasResult R =
 270         AA.alias(Pointer, PointerSize, MemPtr, MemSize);
 271
 272       if (R == AliasAnalysis::NoAlias)
 273         continue;
 274       return MemDepResult::get(Inst);
 275     }
 276
 277
 278     // See if this instruction mod/ref's the pointer.
 279     AliasAnalysis::ModRefResult MRR = AA.getModRefInfo(Inst, MemPtr, MemSize);
 280
 281     if (MRR == AliasAnalysis::NoModRef)
 282       continue;
 283
 284     // Loads don't depend on read-only instructions.
 285     if (isa<LoadInst>(QueryInst) && MRR == AliasAnalysis::Ref)
 286       continue;
 287
 288     // Otherwise, there is a dependence.
 289     return MemDepResult::get(Inst);
 290   }
 291
 292   // If we found nothing, return the non-local flag.
 293   return MemDepResult::getNonLocal();
 294 }
 295
 296 /// getDependency - Return the instruction on which a memory operation
 297 /// depends.
 298 MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
 299   Instruction *ScanPos = QueryInst;
 300
 301   // Check for a cached result
 302   DepResultTy &LocalCache = LocalDeps[QueryInst];
 303
 304   // If the cached entry is non-dirty, just return it.  Note that this depends
 305   // on DepResultTy's default constructing to 'dirty'.
 306   if (LocalCache.getInt() != Dirty)
 307     return ConvToResult(LocalCache);
 308
 309   // Otherwise, if we have a dirty entry, we know we can start the scan at that
 310   // instruction, which may save us some work.
 311   if (Instruction *Inst = LocalCache.getPointer())
 312     ScanPos = Inst;
 313
 314   // Do the scan.
 315   MemDepResult Res =
 316     getDependencyFrom(QueryInst, ScanPos, QueryInst->getParent());
 317
 318   // Remember the result!
 319   // FIXME: Don't convert back and forth!  Make a shared helper function.
 320   LocalCache = ConvFromResult(Res);
 321   if (Instruction *I = Res.getInst())
 322     ReverseLocalDeps[I].insert(QueryInst);
 323
 324   return Res;
 325 }
 326
 327
 328 /// dropInstruction - Remove an instruction from the analysis, making
 329 /// absolutely conservative assumptions when updating the cache.  This is
 330 /// useful, for example when an instruction is changed rather than removed.
 331 void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) {
 332   LocalDepMapType::iterator depGraphEntry = LocalDeps.find(drop);
 333   if (depGraphEntry != LocalDeps.end())
 334     if (Instruction *Inst = depGraphEntry->second.getPointer())
 335       ReverseLocalDeps[Inst].erase(drop);
 336
 337   // Drop dependency information for things that depended on this instr
 338   SmallPtrSet<Instruction*, 4>& set = ReverseLocalDeps[drop];
 339   for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 340        I != E; ++I)
 341     LocalDeps.erase(*I);
 342
 343   LocalDeps.erase(drop);
 344   ReverseLocalDeps.erase(drop);
 345
 346   for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
 347          NonLocalDeps[drop].begin(), DE = NonLocalDeps[drop].end();
 348        DI != DE; ++DI)
 349     if (Instruction *Inst = DI->second.getPointer())
 350       ReverseNonLocalDeps[Inst].erase(drop);
 351
 352   if (ReverseNonLocalDeps.count(drop)) {
 353     SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd;
 354
 355     SmallPtrSet<Instruction*, 4>& set =
 356       ReverseNonLocalDeps[drop];
 357     for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 358          I != E; ++I)
 359       for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
 360            NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end();
 361            DI != DE; ++DI)
 362         if (DI->second.getPointer() == drop) {
 363           // Convert to a dirty entry for the subsequent instruction.
 364           DI->second.setInt(Dirty);
 365           if (drop->isTerminator())
 366             DI->second.setPointer(0);
 367           else {
 368             Instruction *NextI = next(BasicBlock::iterator(drop));
 369             DI->second.setPointer(NextI);
 370             ReverseDepsToAdd.push_back(std::make_pair(NextI, *I));
 371           }
 372         }
 373
 374     // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
 375     while (!ReverseDepsToAdd.empty()) {
 376       ReverseNonLocalDeps[ReverseDepsToAdd.back().first]
 377         .insert(ReverseDepsToAdd.back().second);
 378       ReverseDepsToAdd.pop_back();
 379     }
 380   }
 381
 382   ReverseNonLocalDeps.erase(drop);
 383   NonLocalDeps.erase(drop);
 384 }
 385
 386 /// removeInstruction - Remove an instruction from the dependence analysis,
 387 /// updating the dependence of instructions that previously depended on it.
 388 /// This method attempts to keep the cache coherent using the reverse map.
 389 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
 390   // Walk through the Non-local dependencies, removing this one as the value
 391   // for any cached queries.
 392   for (DenseMap<BasicBlock*, DepResultTy>::iterator DI =
 393        NonLocalDeps[RemInst].begin(), DE = NonLocalDeps[RemInst].end();
 394        DI != DE; ++DI)
 395     if (Instruction *Inst = DI->second.getPointer())
 396       ReverseNonLocalDeps[Inst].erase(RemInst);
 397
 398   // Shortly after this, we will look for things that depend on RemInst.  In
 399   // order to update these, we'll need a new dependency to base them on.  We
 400   // could completely delete any entries that depend on this, but it is better
 401   // to make a more accurate approximation where possible.  Compute that better
 402   // approximation if we can.
 403   DepResultTy NewDependency;
 404
 405   // If we have a cached local dependence query for this instruction, remove it.
 406   //
 407   LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
 408   if (LocalDepEntry != LocalDeps.end()) {
 409     DepResultTy LocalDep = LocalDepEntry->second;
 410
 411     // Remove this local dependency info.
 412     LocalDeps.erase(LocalDepEntry);
 413
 414     // Remove us from DepInst's reverse set now that the local dep info is gone.
 415     if (Instruction *Inst = LocalDep.getPointer())
 416       ReverseLocalDeps[Inst].erase(RemInst);
 417
 418     // If we have unconfirmed info, don't trust it.
 419     if (LocalDep.getInt() != Dirty) {
 420       // If we have a confirmed non-local flag, use it.
 421       if (LocalDep.getInt() == NonLocal || LocalDep.getInt() == None) {
 422         // The only time this dependency is confirmed is if it is non-local.
 423         NewDependency = LocalDep;
 424       } else {
 425         // If we have dep info for RemInst, set them to it.
 426         Instruction *NDI = next(BasicBlock::iterator(LocalDep.getPointer()));
 427         if (NDI != RemInst) // Don't use RemInst for the new dependency!
 428           NewDependency = DepResultTy(NDI, Dirty);
 429       }
 430     }
 431   }
 432
 433   // If we don't already have a local dependency answer for this instruction,
 434   // use the immediate successor of RemInst.  We use the successor because
 435   // getDependence starts by checking the immediate predecessor of what is in
 436   // the cache.
 437   if (NewDependency == DepResultTy(0, Dirty))
 438     NewDependency = DepResultTy(next(BasicBlock::iterator(RemInst)), Dirty);
 439
 440   // Loop over all of the things that depend on the instruction we're removing.
 441   //
 442   ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
 443   if (ReverseDepIt != ReverseLocalDeps.end()) {
 444     SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
 445     for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
 446          E = ReverseDeps.end(); I != E; ++I) {
 447       Instruction *InstDependingOnRemInst = *I;
 448
 449       // If we thought the instruction depended on itself (possible for
 450       // unconfirmed dependencies) ignore the update.
 451       if (InstDependingOnRemInst == RemInst) continue;
 452
 453       // Insert the new dependencies.
 454       LocalDeps[InstDependingOnRemInst] = NewDependency;
 455
 456       // If our NewDependency is an instruction, make sure to remember that new
 457       // things depend on it.
 458       if (Instruction *Inst = NewDependency.getPointer())
 459         ReverseLocalDeps[Inst].insert(InstDependingOnRemInst);
 460     }
 461     ReverseLocalDeps.erase(RemInst);
 462   }
 463
 464   ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
 465   if (ReverseDepIt != ReverseNonLocalDeps.end()) {
 466     SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd;
 467
 468     SmallPtrSet<Instruction*, 4>& set = ReverseDepIt->second;
 469     for (SmallPtrSet<Instruction*, 4>::iterator I = set.begin(), E = set.end();
 470          I != E; ++I)
 471       for (DenseMap<BasicBlock*, DepResultTy>::iterator
 472            DI = NonLocalDeps[*I].begin(), DE = NonLocalDeps[*I].end();
 473            DI != DE; ++DI)
 474         if (DI->second.getPointer() == RemInst) {
 475           // Convert to a dirty entry for the subsequent instruction.
 476           DI->second.setInt(Dirty);
 477           if (RemInst->isTerminator())
 478             DI->second.setPointer(0);
 479           else {
 480             Instruction *NextI = next(BasicBlock::iterator(RemInst));
 481             DI->second.setPointer(NextI);
 482             ReverseDepsToAdd.push_back(std::make_pair(NextI, *I));
 483           }
 484         }
 485
 486     // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
 487     while (!ReverseDepsToAdd.empty()) {
 488       ReverseNonLocalDeps[ReverseDepsToAdd.back().first]
 489         .insert(ReverseDepsToAdd.back().second);
 490       ReverseDepsToAdd.pop_back();
 491     }
 492
 493     ReverseNonLocalDeps.erase(ReverseDepIt);
 494   }
 495
 496   NonLocalDeps.erase(RemInst);
 497
 498   getAnalysis<AliasAnalysis>().deleteValue(RemInst);
 499
 500   DEBUG(verifyRemoved(RemInst));
 501 }
 502
 503 /// verifyRemoved - Verify that the specified instruction does not occur
 504 /// in our internal data structures.
 505 void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
 506   for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
 507        E = LocalDeps.end(); I != E; ++I) {
 508     assert(I->first != D && "Inst occurs in data structures");
 509     assert(I->second.getPointer() != D &&
 510            "Inst occurs in data structures");
 511   }
 512
 513   for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(),
 514        E = NonLocalDeps.end(); I != E; ++I) {
 515     assert(I->first != D && "Inst occurs in data structures");
 516     for (DenseMap<BasicBlock*, DepResultTy>::iterator II = I->second.begin(),
 517          EE = I->second.end(); II  != EE; ++II)
 518       assert(II->second.getPointer() != D && "Inst occurs in data structures");
 519   }
 520
 521   for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),
 522        E = ReverseLocalDeps.end(); I != E; ++I)
 523     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
 524          EE = I->second.end(); II != EE; ++II)
 525       assert(*II != D && "Inst occurs in data structures");
 526
 527   for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(),
 528        E = ReverseNonLocalDeps.end();
 529        I != E; ++I)
 530     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
 531          EE = I->second.end(); II != EE; ++II)
 532       assert(*II != D && "Inst occurs in data structures");
 533 }