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/Analysis/ValueTracking.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/IntrinsicInst.h"
  22 #include "llvm/Function.h"
  23 #include "llvm/LLVMContext.h"
  24 #include "llvm/Analysis/AliasAnalysis.h"
  25 #include "llvm/Analysis/CaptureTracking.h"
  26 #include "llvm/Analysis/Dominators.h"
  27 #include "llvm/Analysis/InstructionSimplify.h"
  28 #include "llvm/Analysis/MemoryBuiltins.h"
  29 #include "llvm/Analysis/PHITransAddr.h"
  30 #include "llvm/Analysis/ValueTracking.h"
  31 #include "llvm/ADT/Statistic.h"
  32 #include "llvm/ADT/STLExtras.h"
  33 #include "llvm/Support/PredIteratorCache.h"
  34 #include "llvm/Support/Debug.h"
  35 #include "llvm/Target/TargetData.h"
  36 using namespace llvm;
  37
  38 STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");
  39 STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");
  40 STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");
  41
  42 STATISTIC(NumCacheNonLocalPtr,
  43           "Number of fully cached non-local ptr responses");
  44 STATISTIC(NumCacheDirtyNonLocalPtr,
  45           "Number of cached, but dirty, non-local ptr responses");
  46 STATISTIC(NumUncacheNonLocalPtr,
  47           "Number of uncached non-local ptr responses");
  48 STATISTIC(NumCacheCompleteNonLocalPtr,
  49           "Number of block queries that were completely cached");
  50
  51 // Limit for the number of instructions to scan in a block.
  52 // FIXME: Figure out what a sane value is for this.
  53 //        (500 is relatively insane.)
  54 static const int BlockScanLimit = 500;
  55
  56 char MemoryDependenceAnalysis::ID = 0;
  57
  58 // Register this pass...
  59 INITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep",
  60                 "Memory Dependence Analysis", false, true)
  61 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
  62 INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep",
  63                       "Memory Dependence Analysis", false, true)
  64
  65 MemoryDependenceAnalysis::MemoryDependenceAnalysis()
  66 : FunctionPass(ID), PredCache(0) {
  67   initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry());
  68 }
  69 MemoryDependenceAnalysis::~MemoryDependenceAnalysis() {
  70 }
  71
  72 /// Clean up memory in between runs
  73 void MemoryDependenceAnalysis::releaseMemory() {
  74   LocalDeps.clear();
  75   NonLocalDeps.clear();
  76   NonLocalPointerDeps.clear();
  77   ReverseLocalDeps.clear();
  78   ReverseNonLocalDeps.clear();
  79   ReverseNonLocalPtrDeps.clear();
  80   PredCache->clear();
  81 }
  82
  83
  84
  85 /// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
  86 ///
  87 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
  88   AU.setPreservesAll();
  89   AU.addRequiredTransitive<AliasAnalysis>();
  90 }
  91
  92 bool MemoryDependenceAnalysis::runOnFunction(Function &) {
  93   AA = &getAnalysis<AliasAnalysis>();
  94   TD = getAnalysisIfAvailable<TargetData>();
  95   DT = getAnalysisIfAvailable<DominatorTree>();
  96   if (PredCache == 0)
  97     PredCache.reset(new PredIteratorCache());
  98   return false;
  99 }
 100
 101 /// RemoveFromReverseMap - This is a helper function that removes Val from
 102 /// 'Inst's set in ReverseMap.  If the set becomes empty, remove Inst's entry.
 103 template <typename KeyTy>
 104 static void RemoveFromReverseMap(DenseMap<Instruction*,
 105                                  SmallPtrSet<KeyTy, 4> > &ReverseMap,
 106                                  Instruction *Inst, KeyTy Val) {
 107   typename DenseMap<Instruction*, SmallPtrSet<KeyTy, 4> >::iterator
 108   InstIt = ReverseMap.find(Inst);
 109   assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
 110   bool Found = InstIt->second.erase(Val);
 111   assert(Found && "Invalid reverse map!"); (void)Found;
 112   if (InstIt->second.empty())
 113     ReverseMap.erase(InstIt);
 114 }
 115
 116 /// GetLocation - If the given instruction references a specific memory
 117 /// location, fill in Loc with the details, otherwise set Loc.Ptr to null.
 118 /// Return a ModRefInfo value describing the general behavior of the
 119 /// instruction.
 120 static
 121 AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst,
 122                                         AliasAnalysis::Location &Loc,
 123                                         AliasAnalysis *AA) {
 124   if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
 125     if (LI->isUnordered()) {
 126       Loc = AA->getLocation(LI);
 127       return AliasAnalysis::Ref;
 128     } else if (LI->getOrdering() == Monotonic) {
 129       Loc = AA->getLocation(LI);
 130       return AliasAnalysis::ModRef;
 131     }
 132     Loc = AliasAnalysis::Location();
 133     return AliasAnalysis::ModRef;
 134   }
 135
 136   if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 137     if (SI->isUnordered()) {
 138       Loc = AA->getLocation(SI);
 139       return AliasAnalysis::Mod;
 140     } else if (SI->getOrdering() == Monotonic) {
 141       Loc = AA->getLocation(SI);
 142       return AliasAnalysis::ModRef;
 143     }
 144     Loc = AliasAnalysis::Location();
 145     return AliasAnalysis::ModRef;
 146   }
 147
 148   if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
 149     Loc = AA->getLocation(V);
 150     return AliasAnalysis::ModRef;
 151   }
 152
 153   if (const CallInst *CI = isFreeCall(Inst)) {
 154     // calls to free() deallocate the entire structure
 155     Loc = AliasAnalysis::Location(CI->getArgOperand(0));
 156     return AliasAnalysis::Mod;
 157   }
 158
 159   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
 160     switch (II->getIntrinsicID()) {
 161     case Intrinsic::lifetime_start:
 162     case Intrinsic::lifetime_end:
 163     case Intrinsic::invariant_start:
 164       Loc = AliasAnalysis::Location(II->getArgOperand(1),
 165                                     cast<ConstantInt>(II->getArgOperand(0))
 166                                       ->getZExtValue(),
 167                                     II->getMetadata(LLVMContext::MD_tbaa));
 168       // These intrinsics don't really modify the memory, but returning Mod
 169       // will allow them to be handled conservatively.
 170       return AliasAnalysis::Mod;
 171     case Intrinsic::invariant_end:
 172       Loc = AliasAnalysis::Location(II->getArgOperand(2),
 173                                     cast<ConstantInt>(II->getArgOperand(1))
 174                                       ->getZExtValue(),
 175                                     II->getMetadata(LLVMContext::MD_tbaa));
 176       // These intrinsics don't really modify the memory, but returning Mod
 177       // will allow them to be handled conservatively.
 178       return AliasAnalysis::Mod;
 179     default:
 180       break;
 181     }
 182
 183   // Otherwise, just do the coarse-grained thing that always works.
 184   if (Inst->mayWriteToMemory())
 185     return AliasAnalysis::ModRef;
 186   if (Inst->mayReadFromMemory())
 187     return AliasAnalysis::Ref;
 188   return AliasAnalysis::NoModRef;
 189 }
 190
 191 /// getCallSiteDependencyFrom - Private helper for finding the local
 192 /// dependencies of a call site.
 193 MemDepResult MemoryDependenceAnalysis::
 194 getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
 195                           BasicBlock::iterator ScanIt, BasicBlock *BB) {
 196   unsigned Limit = BlockScanLimit;
 197
 198   // Walk backwards through the block, looking for dependencies
 199   while (ScanIt != BB->begin()) {
 200     // Limit the amount of scanning we do so we don't end up with quadratic
 201     // running time on extreme testcases.
 202     --Limit;
 203     if (!Limit)
 204       return MemDepResult::getUnknown();
 205
 206     Instruction *Inst = --ScanIt;
 207
 208     // If this inst is a memory op, get the pointer it accessed
 209     AliasAnalysis::Location Loc;
 210     AliasAnalysis::ModRefResult MR = GetLocation(Inst, Loc, AA);
 211     if (Loc.Ptr) {
 212       // A simple instruction.
 213       if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef)
 214         return MemDepResult::getClobber(Inst);
 215       continue;
 216     }
 217
 218     if (CallSite InstCS = cast<Value>(Inst)) {
 219       // Debug intrinsics don't cause dependences.
 220       if (isa<DbgInfoIntrinsic>(Inst)) continue;
 221       // If these two calls do not interfere, look past it.
 222       switch (AA->getModRefInfo(CS, InstCS)) {
 223       case AliasAnalysis::NoModRef:
 224         // If the two calls are the same, return InstCS as a Def, so that
 225         // CS can be found redundant and eliminated.
 226         if (isReadOnlyCall && !(MR & AliasAnalysis::Mod) &&
 227             CS.getInstruction()->isIdenticalToWhenDefined(Inst))
 228           return MemDepResult::getDef(Inst);
 229
 230         // Otherwise if the two calls don't interact (e.g. InstCS is readnone)
 231         // keep scanning.
 232         break;
 233       default:
 234         return MemDepResult::getClobber(Inst);
 235       }
 236     }
 237   }
 238
 239   // No dependence found.  If this is the entry block of the function, it is
 240   // unknown, otherwise it is non-local.
 241   if (BB != &BB->getParent()->getEntryBlock())
 242     return MemDepResult::getNonLocal();
 243   return MemDepResult::getNonFuncLocal();
 244 }
 245
 246 /// isLoadLoadClobberIfExtendedToFullWidth - Return true if LI is a load that
 247 /// would fully overlap MemLoc if done as a wider legal integer load.
 248 ///
 249 /// MemLocBase, MemLocOffset are lazily computed here the first time the
 250 /// base/offs of memloc is needed.
 251 static bool
 252 isLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc,
 253                                        const Value *&MemLocBase,
 254                                        int64_t &MemLocOffs,
 255                                        const LoadInst *LI,
 256                                        const TargetData *TD) {
 257   // If we have no target data, we can't do this.
 258   if (TD == 0) return false;
 259
 260   // If we haven't already computed the base/offset of MemLoc, do so now.
 261   if (MemLocBase == 0)
 262     MemLocBase = GetPointerBaseWithConstantOffset(MemLoc.Ptr, MemLocOffs, *TD);
 263
 264   unsigned Size = MemoryDependenceAnalysis::
 265     getLoadLoadClobberFullWidthSize(MemLocBase, MemLocOffs, MemLoc.Size,
 266                                     LI, *TD);
 267   return Size != 0;
 268 }
 269
 270 /// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that
 271 /// looks at a memory location for a load (specified by MemLocBase, Offs,
 272 /// and Size) and compares it against a load.  If the specified load could
 273 /// be safely widened to a larger integer load that is 1) still efficient,
 274 /// 2) safe for the target, and 3) would provide the specified memory
 275 /// location value, then this function returns the size in bytes of the
 276 /// load width to use.  If not, this returns zero.
 277 unsigned MemoryDependenceAnalysis::
 278 getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs,
 279                                 unsigned MemLocSize, const LoadInst *LI,
 280                                 const TargetData &TD) {
 281   // We can only extend simple integer loads.
 282   if (!isa<IntegerType>(LI->getType()) || !LI->isSimple()) return 0;
 283
 284   // Get the base of this load.
 285   int64_t LIOffs = 0;
 286   const Value *LIBase =
 287     GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, TD);
 288
 289   // If the two pointers are not based on the same pointer, we can't tell that
 290   // they are related.
 291   if (LIBase != MemLocBase) return 0;
 292
 293   // Okay, the two values are based on the same pointer, but returned as
 294   // no-alias.  This happens when we have things like two byte loads at "P+1"
 295   // and "P+3".  Check to see if increasing the size of the "LI" load up to its
 296   // alignment (or the largest native integer type) will allow us to load all
 297   // the bits required by MemLoc.
 298
 299   // If MemLoc is before LI, then no widening of LI will help us out.
 300   if (MemLocOffs < LIOffs) return 0;
 301
 302   // Get the alignment of the load in bytes.  We assume that it is safe to load
 303   // any legal integer up to this size without a problem.  For example, if we're
 304   // looking at an i8 load on x86-32 that is known 1024 byte aligned, we can
 305   // widen it up to an i32 load.  If it is known 2-byte aligned, we can widen it
 306   // to i16.
 307   unsigned LoadAlign = LI->getAlignment();
 308
 309   int64_t MemLocEnd = MemLocOffs+MemLocSize;
 310
 311   // If no amount of rounding up will let MemLoc fit into LI, then bail out.
 312   if (LIOffs+LoadAlign < MemLocEnd) return 0;
 313
 314   // This is the size of the load to try.  Start with the next larger power of
 315   // two.
 316   unsigned NewLoadByteSize = LI->getType()->getPrimitiveSizeInBits()/8U;
 317   NewLoadByteSize = NextPowerOf2(NewLoadByteSize);
 318
 319   while (1) {
 320     // If this load size is bigger than our known alignment or would not fit
 321     // into a native integer register, then we fail.
 322     if (NewLoadByteSize > LoadAlign ||
 323         !TD.fitsInLegalInteger(NewLoadByteSize*8))
 324       return 0;
 325
 326     if (LIOffs+NewLoadByteSize > MemLocEnd &&
 327         LI->getParent()->getParent()->hasFnAttr(Attribute::AddressSafety)) {
 328       // We will be reading past the location accessed by the original program.
 329       // While this is safe in a regular build, Address Safety analysis tools
 330       // may start reporting false warnings. So, don't do widening.
 331       return 0;
 332     }
 333
 334     // If a load of this width would include all of MemLoc, then we succeed.
 335     if (LIOffs+NewLoadByteSize >= MemLocEnd)
 336       return NewLoadByteSize;
 337
 338     NewLoadByteSize <<= 1;
 339   }
 340 }
 341
 342 namespace {
 343   /// Only find pointer captures which happen before the given instruction. Uses
 344   /// the dominator tree to determine whether one instruction is before another.
 345   struct CapturesBefore : public CaptureTracker {
 346     CapturesBefore(const Instruction *I, DominatorTree *DT)
 347       : BeforeHere(I), DT(DT), Captured(false) {}
 348
 349     void tooManyUses() { Captured = true; }
 350
 351     bool shouldExplore(Use *U) {
 352       Instruction *I = cast<Instruction>(U->getUser());
 353       BasicBlock *BB = I->getParent();
 354       if (BeforeHere != I &&
 355           (!DT->isReachableFromEntry(BB) || DT->dominates(BeforeHere, I)))
 356         return false;
 357       return true;
 358     }
 359
 360     bool captured(Use *U) {
 361       Instruction *I = cast<Instruction>(U->getUser());
 362       BasicBlock *BB = I->getParent();
 363       if (BeforeHere != I &&
 364           (!DT->isReachableFromEntry(BB) || DT->dominates(BeforeHere, I)))
 365         return false;
 366       Captured = true;
 367       return true;
 368     }
 369
 370     const Instruction *BeforeHere;
 371     DominatorTree *DT;
 372
 373     bool Captured;
 374   };
 375 }
 376
 377 AliasAnalysis::ModRefResult
 378 MemoryDependenceAnalysis::getModRefInfo(const Instruction *Inst,
 379                                         const AliasAnalysis::Location &MemLoc) {
 380   AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc);
 381   if (MR != AliasAnalysis::ModRef) return MR;
 382
 383   // FIXME: this is really just shoring-up a deficiency in alias analysis.
 384   // BasicAA isn't willing to spend linear time determining whether an alloca
 385   // was captured before or after this particular call, while we are. However,
 386   // with a smarter AA in place, this test is just wasting compile time.
 387   if (!DT) return AliasAnalysis::ModRef;
 388   const Value *Object = GetUnderlyingObject(MemLoc.Ptr, TD);
 389   if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object) ||
 390       isa<Constant>(Object))
 391     return AliasAnalysis::ModRef;
 392
 393   ImmutableCallSite CS(Inst);
 394   if (!CS.getInstruction() || CS.getInstruction() == Object)
 395     return AliasAnalysis::ModRef;
 396
 397   CapturesBefore CB(Inst, DT);
 398   llvm::PointerMayBeCaptured(Object, &CB);
 399   if (CB.Captured)
 400     return AliasAnalysis::ModRef;
 401
 402   unsigned ArgNo = 0;
 403   for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
 404        CI != CE; ++CI, ++ArgNo) {
 405     // Only look at the no-capture or byval pointer arguments.  If this
 406     // pointer were passed to arguments that were neither of these, then it
 407     // couldn't be no-capture.
 408     if (!(*CI)->getType()->isPointerTy() ||
 409         (!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo)))
 410       continue;
 411
 412     // If this is a no-capture pointer argument, see if we can tell that it
 413     // is impossible to alias the pointer we're checking.  If not, we have to
 414     // assume that the call could touch the pointer, even though it doesn't
 415     // escape.
 416     if (!AA->isNoAlias(AliasAnalysis::Location(*CI),
 417                        AliasAnalysis::Location(Object))) {
 418       return AliasAnalysis::ModRef;
 419     }
 420   }
 421   return AliasAnalysis::NoModRef;
 422 }
 423
 424 /// getPointerDependencyFrom - Return the instruction on which a memory
 425 /// location depends.  If isLoad is true, this routine ignores may-aliases with
 426 /// read-only operations.  If isLoad is false, this routine ignores may-aliases
 427 /// with reads from read-only locations.
 428 MemDepResult MemoryDependenceAnalysis::
 429 getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad,
 430                          BasicBlock::iterator ScanIt, BasicBlock *BB) {
 431
 432   const Value *MemLocBase = 0;
 433   int64_t MemLocOffset = 0;
 434
 435   unsigned Limit = BlockScanLimit;
 436
 437   // Walk backwards through the basic block, looking for dependencies.
 438   while (ScanIt != BB->begin()) {
 439     // Limit the amount of scanning we do so we don't end up with quadratic
 440     // running time on extreme testcases.
 441     --Limit;
 442     if (!Limit)
 443       return MemDepResult::getUnknown();
 444
 445     Instruction *Inst = --ScanIt;
 446
 447     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
 448       // Debug intrinsics don't (and can't) cause dependences.
 449       if (isa<DbgInfoIntrinsic>(II)) continue;
 450
 451       // If we reach a lifetime begin or end marker, then the query ends here
 452       // because the value is undefined.
 453       if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
 454         // FIXME: This only considers queries directly on the invariant-tagged
 455         // pointer, not on query pointers that are indexed off of them.  It'd
 456         // be nice to handle that at some point (the right approach is to use
 457         // GetPointerBaseWithConstantOffset).
 458         if (AA->isMustAlias(AliasAnalysis::Location(II->getArgOperand(1)),
 459                             MemLoc))
 460           return MemDepResult::getDef(II);
 461         continue;
 462       }
 463     }
 464
 465     // Values depend on loads if the pointers are must aliased.  This means that
 466     // a load depends on another must aliased load from the same value.
 467     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
 468       // Atomic loads have complications involved.
 469       // FIXME: This is overly conservative.
 470       if (!LI->isUnordered())
 471         return MemDepResult::getClobber(LI);
 472
 473       AliasAnalysis::Location LoadLoc = AA->getLocation(LI);
 474
 475       // If we found a pointer, check if it could be the same as our pointer.
 476       AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc);
 477
 478       if (isLoad) {
 479         if (R == AliasAnalysis::NoAlias) {
 480           // If this is an over-aligned integer load (for example,
 481           // "load i8* %P, align 4") see if it would obviously overlap with the
 482           // queried location if widened to a larger load (e.g. if the queried
 483           // location is 1 byte at P+1).  If so, return it as a load/load
 484           // clobber result, allowing the client to decide to widen the load if
 485           // it wants to.
 486           if (IntegerType *ITy = dyn_cast<IntegerType>(LI->getType()))
 487             if (LI->getAlignment()*8 > ITy->getPrimitiveSizeInBits() &&
 488                 isLoadLoadClobberIfExtendedToFullWidth(MemLoc, MemLocBase,
 489                                                        MemLocOffset, LI, TD))
 490               return MemDepResult::getClobber(Inst);
 491
 492           continue;
 493         }
 494
 495         // Must aliased loads are defs of each other.
 496         if (R == AliasAnalysis::MustAlias)
 497           return MemDepResult::getDef(Inst);
 498
 499 #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads
 500       // in terms of clobbering loads, but since it does this by looking
 501       // at the clobbering load directly, it doesn't know about any
 502       // phi translation that may have happened along the way.
 503
 504         // If we have a partial alias, then return this as a clobber for the
 505         // client to handle.
 506         if (R == AliasAnalysis::PartialAlias)
 507           return MemDepResult::getClobber(Inst);
 508 #endif
 509
 510         // Random may-alias loads don't depend on each other without a
 511         // dependence.
 512         continue;
 513       }
 514
 515       // Stores don't depend on other no-aliased accesses.
 516       if (R == AliasAnalysis::NoAlias)
 517         continue;
 518
 519       // Stores don't alias loads from read-only memory.
 520       if (AA->pointsToConstantMemory(LoadLoc))
 521         continue;
 522
 523       // Stores depend on may/must aliased loads.
 524       return MemDepResult::getDef(Inst);
 525     }
 526
 527     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 528       // Atomic stores have complications involved.
 529       // FIXME: This is overly conservative.
 530       if (!SI->isUnordered())
 531         return MemDepResult::getClobber(SI);
 532
 533       // If alias analysis can tell that this store is guaranteed to not modify
 534       // the query pointer, ignore it.  Use getModRefInfo to handle cases where
 535       // the query pointer points to constant memory etc.
 536       if (AA->getModRefInfo(SI, MemLoc) == AliasAnalysis::NoModRef)
 537         continue;
 538
 539       // Ok, this store might clobber the query pointer.  Check to see if it is
 540       // a must alias: in this case, we want to return this as a def.
 541       AliasAnalysis::Location StoreLoc = AA->getLocation(SI);
 542
 543       // If we found a pointer, check if it could be the same as our pointer.
 544       AliasAnalysis::AliasResult R = AA->alias(StoreLoc, MemLoc);
 545
 546       if (R == AliasAnalysis::NoAlias)
 547         continue;
 548       if (R == AliasAnalysis::MustAlias)
 549         return MemDepResult::getDef(Inst);
 550       return MemDepResult::getClobber(Inst);
 551     }
 552
 553     // If this is an allocation, and if we know that the accessed pointer is to
 554     // the allocation, return Def.  This means that there is no dependence and
 555     // the access can be optimized based on that.  For example, a load could
 556     // turn into undef.
 557     // Note: Only determine this to be a malloc if Inst is the malloc call, not
 558     // a subsequent bitcast of the malloc call result.  There can be stores to
 559     // the malloced memory between the malloc call and its bitcast uses, and we
 560     // need to continue scanning until the malloc call.
 561     if (isa<AllocaInst>(Inst) ||
 562         (isa<CallInst>(Inst) && extractMallocCall(Inst))) {
 563       const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, TD);
 564
 565       if (AccessPtr == Inst || AA->isMustAlias(Inst, AccessPtr))
 566         return MemDepResult::getDef(Inst);
 567       continue;
 568     }
 569
 570     // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
 571     switch (getModRefInfo(Inst, MemLoc)) {
 572     case AliasAnalysis::NoModRef:
 573       // If the call has no effect on the queried pointer, just ignore it.
 574       continue;
 575     case AliasAnalysis::Mod:
 576       return MemDepResult::getClobber(Inst);
 577     case AliasAnalysis::Ref:
 578       // If the call is known to never store to the pointer, and if this is a
 579       // load query, we can safely ignore it (scan past it).
 580       if (isLoad)
 581         continue;
 582     default:
 583       // Otherwise, there is a potential dependence.  Return a clobber.
 584       return MemDepResult::getClobber(Inst);
 585     }
 586   }
 587
 588   // No dependence found.  If this is the entry block of the function, it is
 589   // unknown, otherwise it is non-local.
 590   if (BB != &BB->getParent()->getEntryBlock())
 591     return MemDepResult::getNonLocal();
 592   return MemDepResult::getNonFuncLocal();
 593 }
 594
 595 /// getDependency - Return the instruction on which a memory operation
 596 /// depends.
 597 MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
 598   Instruction *ScanPos = QueryInst;
 599
 600   // Check for a cached result
 601   MemDepResult &LocalCache = LocalDeps[QueryInst];
 602
 603   // If the cached entry is non-dirty, just return it.  Note that this depends
 604   // on MemDepResult's default constructing to 'dirty'.
 605   if (!LocalCache.isDirty())
 606     return LocalCache;
 607
 608   // Otherwise, if we have a dirty entry, we know we can start the scan at that
 609   // instruction, which may save us some work.
 610   if (Instruction *Inst = LocalCache.getInst()) {
 611     ScanPos = Inst;
 612
 613     RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
 614   }
 615
 616   BasicBlock *QueryParent = QueryInst->getParent();
 617
 618   // Do the scan.
 619   if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
 620     // No dependence found.  If this is the entry block of the function, it is
 621     // unknown, otherwise it is non-local.
 622     if (QueryParent != &QueryParent->getParent()->getEntryBlock())
 623       LocalCache = MemDepResult::getNonLocal();
 624     else
 625       LocalCache = MemDepResult::getNonFuncLocal();
 626   } else {
 627     AliasAnalysis::Location MemLoc;
 628     AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA);
 629     if (MemLoc.Ptr) {
 630       // If we can do a pointer scan, make it happen.
 631       bool isLoad = !(MR & AliasAnalysis::Mod);
 632       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst))
 633         isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
 634
 635       LocalCache = getPointerDependencyFrom(MemLoc, isLoad, ScanPos,
 636                                             QueryParent);
 637     } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
 638       CallSite QueryCS(QueryInst);
 639       bool isReadOnly = AA->onlyReadsMemory(QueryCS);
 640       LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos,
 641                                              QueryParent);
 642     } else
 643       // Non-memory instruction.
 644       LocalCache = MemDepResult::getUnknown();
 645   }
 646
 647   // Remember the result!
 648   if (Instruction *I = LocalCache.getInst())
 649     ReverseLocalDeps[I].insert(QueryInst);
 650
 651   return LocalCache;
 652 }
 653
 654 #ifndef NDEBUG
 655 /// AssertSorted - This method is used when -debug is specified to verify that
 656 /// cache arrays are properly kept sorted.
 657 static void AssertSorted(MemoryDependenceAnalysis::NonLocalDepInfo &Cache,
 658                          int Count = -1) {
 659   if (Count == -1) Count = Cache.size();
 660   if (Count == 0) return;
 661
 662   for (unsigned i = 1; i != unsigned(Count); ++i)
 663     assert(!(Cache[i] < Cache[i-1]) && "Cache isn't sorted!");
 664 }
 665 #endif
 666
 667 /// getNonLocalCallDependency - Perform a full dependency query for the
 668 /// specified call, returning the set of blocks that the value is
 669 /// potentially live across.  The returned set of results will include a
 670 /// "NonLocal" result for all blocks where the value is live across.
 671 ///
 672 /// This method assumes the instruction returns a "NonLocal" dependency
 673 /// within its own block.
 674 ///
 675 /// This returns a reference to an internal data structure that may be
 676 /// invalidated on the next non-local query or when an instruction is
 677 /// removed.  Clients must copy this data if they want it around longer than
 678 /// that.
 679 const MemoryDependenceAnalysis::NonLocalDepInfo &
 680 MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) {
 681   assert(getDependency(QueryCS.getInstruction()).isNonLocal() &&
 682  "getNonLocalCallDependency should only be used on calls with non-local deps!");
 683   PerInstNLInfo &CacheP = NonLocalDeps[QueryCS.getInstruction()];
 684   NonLocalDepInfo &Cache = CacheP.first;
 685
 686   /// DirtyBlocks - This is the set of blocks that need to be recomputed.  In
 687   /// the cached case, this can happen due to instructions being deleted etc. In
 688   /// the uncached case, this starts out as the set of predecessors we care
 689   /// about.
 690   SmallVector<BasicBlock*, 32> DirtyBlocks;
 691
 692   if (!Cache.empty()) {
 693     // Okay, we have a cache entry.  If we know it is not dirty, just return it
 694     // with no computation.
 695     if (!CacheP.second) {
 696       ++NumCacheNonLocal;
 697       return Cache;
 698     }
 699
 700     // If we already have a partially computed set of results, scan them to
 701     // determine what is dirty, seeding our initial DirtyBlocks worklist.
 702     for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end();
 703        I != E; ++I)
 704       if (I->getResult().isDirty())
 705         DirtyBlocks.push_back(I->getBB());
 706
 707     // Sort the cache so that we can do fast binary search lookups below.
 708     std::sort(Cache.begin(), Cache.end());
 709
 710     ++NumCacheDirtyNonLocal;
 711     //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
 712     //     << Cache.size() << " cached: " << *QueryInst;
 713   } else {
 714     // Seed DirtyBlocks with each of the preds of QueryInst's block.
 715     BasicBlock *QueryBB = QueryCS.getInstruction()->getParent();
 716     for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI)
 717       DirtyBlocks.push_back(*PI);
 718     ++NumUncacheNonLocal;
 719   }
 720
 721   // isReadonlyCall - If this is a read-only call, we can be more aggressive.
 722   bool isReadonlyCall = AA->onlyReadsMemory(QueryCS);
 723
 724   SmallPtrSet<BasicBlock*, 64> Visited;
 725
 726   unsigned NumSortedEntries = Cache.size();
 727   DEBUG(AssertSorted(Cache));
 728
 729   // Iterate while we still have blocks to update.
 730   while (!DirtyBlocks.empty()) {
 731     BasicBlock *DirtyBB = DirtyBlocks.back();
 732     DirtyBlocks.pop_back();
 733
 734     // Already processed this block?
 735     if (!Visited.insert(DirtyBB))
 736       continue;
 737
 738     // Do a binary search to see if we already have an entry for this block in
 739     // the cache set.  If so, find it.
 740     DEBUG(AssertSorted(Cache, NumSortedEntries));
 741     NonLocalDepInfo::iterator Entry =
 742       std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries,
 743                        NonLocalDepEntry(DirtyBB));
 744     if (Entry != Cache.begin() && prior(Entry)->getBB() == DirtyBB)
 745       --Entry;
 746
 747     NonLocalDepEntry *ExistingResult = 0;
 748     if (Entry != Cache.begin()+NumSortedEntries &&
 749         Entry->getBB() == DirtyBB) {
 750       // If we already have an entry, and if it isn't already dirty, the block
 751       // is done.
 752       if (!Entry->getResult().isDirty())
 753         continue;
 754
 755       // Otherwise, remember this slot so we can update the value.
 756       ExistingResult = &*Entry;
 757     }
 758
 759     // If the dirty entry has a pointer, start scanning from it so we don't have
 760     // to rescan the entire block.
 761     BasicBlock::iterator ScanPos = DirtyBB->end();
 762     if (ExistingResult) {
 763       if (Instruction *Inst = ExistingResult->getResult().getInst()) {
 764         ScanPos = Inst;
 765         // We're removing QueryInst's use of Inst.
 766         RemoveFromReverseMap(ReverseNonLocalDeps, Inst,
 767                              QueryCS.getInstruction());
 768       }
 769     }
 770
 771     // Find out if this block has a local dependency for QueryInst.
 772     MemDepResult Dep;
 773
 774     if (ScanPos != DirtyBB->begin()) {
 775       Dep = getCallSiteDependencyFrom(QueryCS, isReadonlyCall,ScanPos, DirtyBB);
 776     } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) {
 777       // No dependence found.  If this is the entry block of the function, it is
 778       // a clobber, otherwise it is unknown.
 779       Dep = MemDepResult::getNonLocal();
 780     } else {
 781       Dep = MemDepResult::getNonFuncLocal();
 782     }
 783
 784     // If we had a dirty entry for the block, update it.  Otherwise, just add
 785     // a new entry.
 786     if (ExistingResult)
 787       ExistingResult->setResult(Dep);
 788     else
 789       Cache.push_back(NonLocalDepEntry(DirtyBB, Dep));
 790
 791     // If the block has a dependency (i.e. it isn't completely transparent to
 792     // the value), remember the association!
 793     if (!Dep.isNonLocal()) {
 794       // Keep the ReverseNonLocalDeps map up to date so we can efficiently
 795       // update this when we remove instructions.
 796       if (Instruction *Inst = Dep.getInst())
 797         ReverseNonLocalDeps[Inst].insert(QueryCS.getInstruction());
 798     } else {
 799
 800       // If the block *is* completely transparent to the load, we need to check
 801       // the predecessors of this block.  Add them to our worklist.
 802       for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI)
 803         DirtyBlocks.push_back(*PI);
 804     }
 805   }
 806
 807   return Cache;
 808 }
 809
 810 /// getNonLocalPointerDependency - Perform a full dependency query for an
 811 /// access to the specified (non-volatile) memory location, returning the
 812 /// set of instructions that either define or clobber the value.
 813 ///
 814 /// This method assumes the pointer has a "NonLocal" dependency within its
 815 /// own block.
 816 ///
 817 void MemoryDependenceAnalysis::
 818 getNonLocalPointerDependency(const AliasAnalysis::Location &Loc, bool isLoad,
 819                              BasicBlock *FromBB,
 820                              SmallVectorImpl<NonLocalDepResult> &Result) {
 821   assert(Loc.Ptr->getType()->isPointerTy() &&
 822          "Can't get pointer deps of a non-pointer!");
 823   Result.clear();
 824
 825   PHITransAddr Address(const_cast<Value *>(Loc.Ptr), TD);
 826
 827   // This is the set of blocks we've inspected, and the pointer we consider in
 828   // each block.  Because of critical edges, we currently bail out if querying
 829   // a block with multiple different pointers.  This can happen during PHI
 830   // translation.
 831   DenseMap<BasicBlock*, Value*> Visited;
 832   if (!getNonLocalPointerDepFromBB(Address, Loc, isLoad, FromBB,
 833                                    Result, Visited, true))
 834     return;
 835   Result.clear();
 836   Result.push_back(NonLocalDepResult(FromBB,
 837                                      MemDepResult::getUnknown(),
 838                                      const_cast<Value *>(Loc.Ptr)));
 839 }
 840
 841 /// GetNonLocalInfoForBlock - Compute the memdep value for BB with
 842 /// Pointer/PointeeSize using either cached information in Cache or by doing a
 843 /// lookup (which may use dirty cache info if available).  If we do a lookup,
 844 /// add the result to the cache.
 845 MemDepResult MemoryDependenceAnalysis::
 846 GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc,
 847                         bool isLoad, BasicBlock *BB,
 848                         NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
 849
 850   // Do a binary search to see if we already have an entry for this block in
 851   // the cache set.  If so, find it.
 852   NonLocalDepInfo::iterator Entry =
 853     std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
 854                      NonLocalDepEntry(BB));
 855   if (Entry != Cache->begin() && (Entry-1)->getBB() == BB)
 856     --Entry;
 857
 858   NonLocalDepEntry *ExistingResult = 0;
 859   if (Entry != Cache->begin()+NumSortedEntries && Entry->getBB() == BB)
 860     ExistingResult = &*Entry;
 861
 862   // If we have a cached entry, and it is non-dirty, use it as the value for
 863   // this dependency.
 864   if (ExistingResult && !ExistingResult->getResult().isDirty()) {
 865     ++NumCacheNonLocalPtr;
 866     return ExistingResult->getResult();
 867   }
 868
 869   // Otherwise, we have to scan for the value.  If we have a dirty cache
 870   // entry, start scanning from its position, otherwise we scan from the end
 871   // of the block.
 872   BasicBlock::iterator ScanPos = BB->end();
 873   if (ExistingResult && ExistingResult->getResult().getInst()) {
 874     assert(ExistingResult->getResult().getInst()->getParent() == BB &&
 875            "Instruction invalidated?");
 876     ++NumCacheDirtyNonLocalPtr;
 877     ScanPos = ExistingResult->getResult().getInst();
 878
 879     // Eliminating the dirty entry from 'Cache', so update the reverse info.
 880     ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
 881     RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos, CacheKey);
 882   } else {
 883     ++NumUncacheNonLocalPtr;
 884   }
 885
 886   // Scan the block for the dependency.
 887   MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB);
 888
 889   // If we had a dirty entry for the block, update it.  Otherwise, just add
 890   // a new entry.
 891   if (ExistingResult)
 892     ExistingResult->setResult(Dep);
 893   else
 894     Cache->push_back(NonLocalDepEntry(BB, Dep));
 895
 896   // If the block has a dependency (i.e. it isn't completely transparent to
 897   // the value), remember the reverse association because we just added it
 898   // to Cache!
 899   if (!Dep.isDef() && !Dep.isClobber())
 900     return Dep;
 901
 902   // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
 903   // update MemDep when we remove instructions.
 904   Instruction *Inst = Dep.getInst();
 905   assert(Inst && "Didn't depend on anything?");
 906   ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
 907   ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
 908   return Dep;
 909 }
 910
 911 /// SortNonLocalDepInfoCache - Sort the a NonLocalDepInfo cache, given a certain
 912 /// number of elements in the array that are already properly ordered.  This is
 913 /// optimized for the case when only a few entries are added.
 914 static void
 915 SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache,
 916                          unsigned NumSortedEntries) {
 917   switch (Cache.size() - NumSortedEntries) {
 918   case 0:
 919     // done, no new entries.
 920     break;
 921   case 2: {
 922     // Two new entries, insert the last one into place.
 923     NonLocalDepEntry Val = Cache.back();
 924     Cache.pop_back();
 925     MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry =
 926       std::upper_bound(Cache.begin(), Cache.end()-1, Val);
 927     Cache.insert(Entry, Val);
 928     // FALL THROUGH.
 929   }
 930   case 1:
 931     // One new entry, Just insert the new value at the appropriate position.
 932     if (Cache.size() != 1) {
 933       NonLocalDepEntry Val = Cache.back();
 934       Cache.pop_back();
 935       MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry =
 936         std::upper_bound(Cache.begin(), Cache.end(), Val);
 937       Cache.insert(Entry, Val);
 938     }
 939     break;
 940   default:
 941     // Added many values, do a full scale sort.
 942     std::sort(Cache.begin(), Cache.end());
 943     break;
 944   }
 945 }
 946
 947 /// getNonLocalPointerDepFromBB - Perform a dependency query based on
 948 /// pointer/pointeesize starting at the end of StartBB.  Add any clobber/def
 949 /// results to the results vector and keep track of which blocks are visited in
 950 /// 'Visited'.
 951 ///
 952 /// This has special behavior for the first block queries (when SkipFirstBlock
 953 /// is true).  In this special case, it ignores the contents of the specified
 954 /// block and starts returning dependence info for its predecessors.
 955 ///
 956 /// This function returns false on success, or true to indicate that it could
 957 /// not compute dependence information for some reason.  This should be treated
 958 /// as a clobber dependence on the first instruction in the predecessor block.
 959 bool MemoryDependenceAnalysis::
 960 getNonLocalPointerDepFromBB(const PHITransAddr &Pointer,
 961                             const AliasAnalysis::Location &Loc,
 962                             bool isLoad, BasicBlock *StartBB,
 963                             SmallVectorImpl<NonLocalDepResult> &Result,
 964                             DenseMap<BasicBlock*, Value*> &Visited,
 965                             bool SkipFirstBlock) {
 966
 967   // Look up the cached info for Pointer.
 968   ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
 969
 970   // Set up a temporary NLPI value. If the map doesn't yet have an entry for
 971   // CacheKey, this value will be inserted as the associated value. Otherwise,
 972   // it'll be ignored, and we'll have to check to see if the cached size and
 973   // tbaa tag are consistent with the current query.
 974   NonLocalPointerInfo InitialNLPI;
 975   InitialNLPI.Size = Loc.Size;
 976   InitialNLPI.TBAATag = Loc.TBAATag;
 977
 978   // Get the NLPI for CacheKey, inserting one into the map if it doesn't
 979   // already have one.
 980   std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
 981     NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
 982   NonLocalPointerInfo *CacheInfo = &Pair.first->second;
 983
 984   // If we already have a cache entry for this CacheKey, we may need to do some
 985   // work to reconcile the cache entry and the current query.
 986   if (!Pair.second) {
 987     if (CacheInfo->Size < Loc.Size) {
 988       // The query's Size is greater than the cached one. Throw out the
 989       // cached data and procede with the query at the greater size.
 990       CacheInfo->Pair = BBSkipFirstBlockPair();
 991       CacheInfo->Size = Loc.Size;
 992       for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(),
 993            DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI)
 994         if (Instruction *Inst = DI->getResult().getInst())
 995           RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
 996       CacheInfo->NonLocalDeps.clear();
 997     } else if (CacheInfo->Size > Loc.Size) {
 998       // This query's Size is less than the cached one. Conservatively restart
 999       // the query using the greater size.
1000       return getNonLocalPointerDepFromBB(Pointer,
1001                                          Loc.getWithNewSize(CacheInfo->Size),
1002                                          isLoad, StartBB, Result, Visited,
1003                                          SkipFirstBlock);
1004     }
1005
1006     // If the query's TBAATag is inconsistent with the cached one,
1007     // conservatively throw out the cached data and restart the query with
1008     // no tag if needed.
1009     if (CacheInfo->TBAATag != Loc.TBAATag) {
1010       if (CacheInfo->TBAATag) {
1011         CacheInfo->Pair = BBSkipFirstBlockPair();
1012         CacheInfo->TBAATag = 0;
1013         for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(),
1014              DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI)
1015           if (Instruction *Inst = DI->getResult().getInst())
1016             RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
1017         CacheInfo->NonLocalDeps.clear();
1018       }
1019       if (Loc.TBAATag)
1020         return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutTBAATag(),
1021                                            isLoad, StartBB, Result, Visited,
1022                                            SkipFirstBlock);
1023     }
1024   }
1025
1026   NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps;
1027
1028   // If we have valid cached information for exactly the block we are
1029   // investigating, just return it with no recomputation.
1030   if (CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
1031     // We have a fully cached result for this query then we can just return the
1032     // cached results and populate the visited set.  However, we have to verify
1033     // that we don't already have conflicting results for these blocks.  Check
1034     // to ensure that if a block in the results set is in the visited set that
1035     // it was for the same pointer query.
1036     if (!Visited.empty()) {
1037       for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
1038            I != E; ++I) {
1039         DenseMap<BasicBlock*, Value*>::iterator VI = Visited.find(I->getBB());
1040         if (VI == Visited.end() || VI->second == Pointer.getAddr())
1041           continue;
1042
1043         // We have a pointer mismatch in a block.  Just return clobber, saying
1044         // that something was clobbered in this result.  We could also do a
1045         // non-fully cached query, but there is little point in doing this.
1046         return true;
1047       }
1048     }
1049
1050     Value *Addr = Pointer.getAddr();
1051     for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
1052          I != E; ++I) {
1053       Visited.insert(std::make_pair(I->getBB(), Addr));
1054       if (!I->getResult().isNonLocal())
1055         Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr));
1056     }
1057     ++NumCacheCompleteNonLocalPtr;
1058     return false;
1059   }
1060
1061   // Otherwise, either this is a new block, a block with an invalid cache
1062   // pointer or one that we're about to invalidate by putting more info into it
1063   // than its valid cache info.  If empty, the result will be valid cache info,
1064   // otherwise it isn't.
1065   if (Cache->empty())
1066     CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
1067   else
1068     CacheInfo->Pair = BBSkipFirstBlockPair();
1069
1070   SmallVector<BasicBlock*, 32> Worklist;
1071   Worklist.push_back(StartBB);
1072
1073   // PredList used inside loop.
1074   SmallVector<std::pair<BasicBlock*, PHITransAddr>, 16> PredList;
1075
1076   // Keep track of the entries that we know are sorted.  Previously cached
1077   // entries will all be sorted.  The entries we add we only sort on demand (we
1078   // don't insert every element into its sorted position).  We know that we
1079   // won't get any reuse from currently inserted values, because we don't
1080   // revisit blocks after we insert info for them.
1081   unsigned NumSortedEntries = Cache->size();
1082   DEBUG(AssertSorted(*Cache));
1083
1084   while (!Worklist.empty()) {
1085     BasicBlock *BB = Worklist.pop_back_val();
1086
1087     // Skip the first block if we have it.
1088     if (!SkipFirstBlock) {
1089       // Analyze the dependency of *Pointer in FromBB.  See if we already have
1090       // been here.
1091       assert(Visited.count(BB) && "Should check 'visited' before adding to WL");
1092
1093       // Get the dependency info for Pointer in BB.  If we have cached
1094       // information, we will use it, otherwise we compute it.
1095       DEBUG(AssertSorted(*Cache, NumSortedEntries));
1096       MemDepResult Dep = GetNonLocalInfoForBlock(Loc, isLoad, BB, Cache,
1097                                                  NumSortedEntries);
1098
1099       // If we got a Def or Clobber, add this to the list of results.
1100       if (!Dep.isNonLocal()) {
1101         Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));
1102         continue;
1103       }
1104     }
1105
1106     // If 'Pointer' is an instruction defined in this block, then we need to do
1107     // phi translation to change it into a value live in the predecessor block.
1108     // If not, we just add the predecessors to the worklist and scan them with
1109     // the same Pointer.
1110     if (!Pointer.NeedsPHITranslationFromBlock(BB)) {
1111       SkipFirstBlock = false;
1112       SmallVector<BasicBlock*, 16> NewBlocks;
1113       for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
1114         // Verify that we haven't looked at this block yet.
1115         std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
1116           InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr()));
1117         if (InsertRes.second) {
1118           // First time we've looked at *PI.
1119           NewBlocks.push_back(*PI);
1120           continue;
1121         }
1122
1123         // If we have seen this block before, but it was with a different
1124         // pointer then we have a phi translation failure and we have to treat
1125         // this as a clobber.
1126         if (InsertRes.first->second != Pointer.getAddr()) {
1127           // Make sure to clean up the Visited map before continuing on to
1128           // PredTranslationFailure.
1129           for (unsigned i = 0; i < NewBlocks.size(); i++)
1130             Visited.erase(NewBlocks[i]);
1131           goto PredTranslationFailure;
1132         }
1133       }
1134       Worklist.append(NewBlocks.begin(), NewBlocks.end());
1135       continue;
1136     }
1137
1138     // We do need to do phi translation, if we know ahead of time we can't phi
1139     // translate this value, don't even try.
1140     if (!Pointer.IsPotentiallyPHITranslatable())
1141       goto PredTranslationFailure;
1142
1143     // We may have added values to the cache list before this PHI translation.
1144     // If so, we haven't done anything to ensure that the cache remains sorted.
1145     // Sort it now (if needed) so that recursive invocations of
1146     // getNonLocalPointerDepFromBB and other routines that could reuse the cache
1147     // value will only see properly sorted cache arrays.
1148     if (Cache && NumSortedEntries != Cache->size()) {
1149       SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1150       NumSortedEntries = Cache->size();
1151     }
1152     Cache = 0;
1153
1154     PredList.clear();
1155     for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
1156       BasicBlock *Pred = *PI;
1157       PredList.push_back(std::make_pair(Pred, Pointer));
1158
1159       // Get the PHI translated pointer in this predecessor.  This can fail if
1160       // not translatable, in which case the getAddr() returns null.
1161       PHITransAddr &PredPointer = PredList.back().second;
1162       PredPointer.PHITranslateValue(BB, Pred, 0);
1163
1164       Value *PredPtrVal = PredPointer.getAddr();
1165
1166       // Check to see if we have already visited this pred block with another
1167       // pointer.  If so, we can't do this lookup.  This failure can occur
1168       // with PHI translation when a critical edge exists and the PHI node in
1169       // the successor translates to a pointer value different than the
1170       // pointer the block was first analyzed with.
1171       std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
1172         InsertRes = Visited.insert(std::make_pair(Pred, PredPtrVal));
1173
1174       if (!InsertRes.second) {
1175         // We found the pred; take it off the list of preds to visit.
1176         PredList.pop_back();
1177
1178         // If the predecessor was visited with PredPtr, then we already did
1179         // the analysis and can ignore it.
1180         if (InsertRes.first->second == PredPtrVal)
1181           continue;
1182
1183         // Otherwise, the block was previously analyzed with a different
1184         // pointer.  We can't represent the result of this case, so we just
1185         // treat this as a phi translation failure.
1186
1187         // Make sure to clean up the Visited map before continuing on to
1188         // PredTranslationFailure.
1189         for (unsigned i = 0; i < PredList.size(); i++)
1190           Visited.erase(PredList[i].first);
1191
1192         goto PredTranslationFailure;
1193       }
1194     }
1195
1196     // Actually process results here; this need to be a separate loop to avoid
1197     // calling getNonLocalPointerDepFromBB for blocks we don't want to return
1198     // any results for.  (getNonLocalPointerDepFromBB will modify our
1199     // datastructures in ways the code after the PredTranslationFailure label
1200     // doesn't expect.)
1201     for (unsigned i = 0; i < PredList.size(); i++) {
1202       BasicBlock *Pred = PredList[i].first;
1203       PHITransAddr &PredPointer = PredList[i].second;
1204       Value *PredPtrVal = PredPointer.getAddr();
1205
1206       bool CanTranslate = true;
1207       // If PHI translation was unable to find an available pointer in this
1208       // predecessor, then we have to assume that the pointer is clobbered in
1209       // that predecessor.  We can still do PRE of the load, which would insert
1210       // a computation of the pointer in this predecessor.
1211       if (PredPtrVal == 0)
1212         CanTranslate = false;
1213
1214       // FIXME: it is entirely possible that PHI translating will end up with
1215       // the same value.  Consider PHI translating something like:
1216       // X = phi [x, bb1], [y, bb2].  PHI translating for bb1 doesn't *need*
1217       // to recurse here, pedantically speaking.
1218
1219       // If getNonLocalPointerDepFromBB fails here, that means the cached
1220       // result conflicted with the Visited list; we have to conservatively
1221       // assume it is unknown, but this also does not block PRE of the load.
1222       if (!CanTranslate ||
1223           getNonLocalPointerDepFromBB(PredPointer,
1224                                       Loc.getWithNewPtr(PredPtrVal),
1225                                       isLoad, Pred,
1226                                       Result, Visited)) {
1227         // Add the entry to the Result list.
1228         NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal);
1229         Result.push_back(Entry);
1230
1231         // Since we had a phi translation failure, the cache for CacheKey won't
1232         // include all of the entries that we need to immediately satisfy future
1233         // queries.  Mark this in NonLocalPointerDeps by setting the
1234         // BBSkipFirstBlockPair pointer to null.  This requires reuse of the
1235         // cached value to do more work but not miss the phi trans failure.
1236         NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
1237         NLPI.Pair = BBSkipFirstBlockPair();
1238         continue;
1239       }
1240     }
1241
1242     // Refresh the CacheInfo/Cache pointer so that it isn't invalidated.
1243     CacheInfo = &NonLocalPointerDeps[CacheKey];
1244     Cache = &CacheInfo->NonLocalDeps;
1245     NumSortedEntries = Cache->size();
1246
1247     // Since we did phi translation, the "Cache" set won't contain all of the
1248     // results for the query.  This is ok (we can still use it to accelerate
1249     // specific block queries) but we can't do the fastpath "return all
1250     // results from the set"  Clear out the indicator for this.
1251     CacheInfo->Pair = BBSkipFirstBlockPair();
1252     SkipFirstBlock = false;
1253     continue;
1254
1255   PredTranslationFailure:
1256     // The following code is "failure"; we can't produce a sane translation
1257     // for the given block.  It assumes that we haven't modified any of
1258     // our datastructures while processing the current block.
1259
1260     if (Cache == 0) {
1261       // Refresh the CacheInfo/Cache pointer if it got invalidated.
1262       CacheInfo = &NonLocalPointerDeps[CacheKey];
1263       Cache = &CacheInfo->NonLocalDeps;
1264       NumSortedEntries = Cache->size();
1265     }
1266
1267     // Since we failed phi translation, the "Cache" set won't contain all of the
1268     // results for the query.  This is ok (we can still use it to accelerate
1269     // specific block queries) but we can't do the fastpath "return all
1270     // results from the set".  Clear out the indicator for this.
1271     CacheInfo->Pair = BBSkipFirstBlockPair();
1272
1273     // If *nothing* works, mark the pointer as unknown.
1274     //
1275     // If this is the magic first block, return this as a clobber of the whole
1276     // incoming value.  Since we can't phi translate to one of the predecessors,
1277     // we have to bail out.
1278     if (SkipFirstBlock)
1279       return true;
1280
1281     for (NonLocalDepInfo::reverse_iterator I = Cache->rbegin(); ; ++I) {
1282       assert(I != Cache->rend() && "Didn't find current block??");
1283       if (I->getBB() != BB)
1284         continue;
1285
1286       assert(I->getResult().isNonLocal() &&
1287              "Should only be here with transparent block");
1288       I->setResult(MemDepResult::getUnknown());
1289       Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(),
1290                                          Pointer.getAddr()));
1291       break;
1292     }
1293   }
1294
1295   // Okay, we're done now.  If we added new values to the cache, re-sort it.
1296   SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1297   DEBUG(AssertSorted(*Cache));
1298   return false;
1299 }
1300
1301 /// RemoveCachedNonLocalPointerDependencies - If P exists in
1302 /// CachedNonLocalPointerInfo, remove it.
1303 void MemoryDependenceAnalysis::
1304 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) {
1305   CachedNonLocalPointerInfo::iterator It =
1306     NonLocalPointerDeps.find(P);
1307   if (It == NonLocalPointerDeps.end()) return;
1308
1309   // Remove all of the entries in the BB->val map.  This involves removing
1310   // instructions from the reverse map.
1311   NonLocalDepInfo &PInfo = It->second.NonLocalDeps;
1312
1313   for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
1314     Instruction *Target = PInfo[i].getResult().getInst();
1315     if (Target == 0) continue;  // Ignore non-local dep results.
1316     assert(Target->getParent() == PInfo[i].getBB());
1317
1318     // Eliminating the dirty entry from 'Cache', so update the reverse info.
1319     RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P);
1320   }
1321
1322   // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
1323   NonLocalPointerDeps.erase(It);
1324 }
1325
1326
1327 /// invalidateCachedPointerInfo - This method is used to invalidate cached
1328 /// information about the specified pointer, because it may be too
1329 /// conservative in memdep.  This is an optional call that can be used when
1330 /// the client detects an equivalence between the pointer and some other
1331 /// value and replaces the other value with ptr. This can make Ptr available
1332 /// in more places that cached info does not necessarily keep.
1333 void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) {
1334   // If Ptr isn't really a pointer, just ignore it.
1335   if (!Ptr->getType()->isPointerTy()) return;
1336   // Flush store info for the pointer.
1337   RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false));
1338   // Flush load info for the pointer.
1339   RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
1340 }
1341
1342 /// invalidateCachedPredecessors - Clear the PredIteratorCache info.
1343 /// This needs to be done when the CFG changes, e.g., due to splitting
1344 /// critical edges.
1345 void MemoryDependenceAnalysis::invalidateCachedPredecessors() {
1346   PredCache->clear();
1347 }
1348
1349 /// removeInstruction - Remove an instruction from the dependence analysis,
1350 /// updating the dependence of instructions that previously depended on it.
1351 /// This method attempts to keep the cache coherent using the reverse map.
1352 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
1353   // Walk through the Non-local dependencies, removing this one as the value
1354   // for any cached queries.
1355   NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
1356   if (NLDI != NonLocalDeps.end()) {
1357     NonLocalDepInfo &BlockMap = NLDI->second.first;
1358     for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end();
1359          DI != DE; ++DI)
1360       if (Instruction *Inst = DI->getResult().getInst())
1361         RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
1362     NonLocalDeps.erase(NLDI);
1363   }
1364
1365   // If we have a cached local dependence query for this instruction, remove it.
1366   //
1367   LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
1368   if (LocalDepEntry != LocalDeps.end()) {
1369     // Remove us from DepInst's reverse set now that the local dep info is gone.
1370     if (Instruction *Inst = LocalDepEntry->second.getInst())
1371       RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
1372
1373     // Remove this local dependency info.
1374     LocalDeps.erase(LocalDepEntry);
1375   }
1376
1377   // If we have any cached pointer dependencies on this instruction, remove
1378   // them.  If the instruction has non-pointer type, then it can't be a pointer
1379   // base.
1380
1381   // Remove it from both the load info and the store info.  The instruction
1382   // can't be in either of these maps if it is non-pointer.
1383   if (RemInst->getType()->isPointerTy()) {
1384     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
1385     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
1386   }
1387
1388   // Loop over all of the things that depend on the instruction we're removing.
1389   //
1390   SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd;
1391
1392   // If we find RemInst as a clobber or Def in any of the maps for other values,
1393   // we need to replace its entry with a dirty version of the instruction after
1394   // it.  If RemInst is a terminator, we use a null dirty value.
1395   //
1396   // Using a dirty version of the instruction after RemInst saves having to scan
1397   // the entire block to get to this point.
1398   MemDepResult NewDirtyVal;
1399   if (!RemInst->isTerminator())
1400     NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst));
1401
1402   ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
1403   if (ReverseDepIt != ReverseLocalDeps.end()) {
1404     SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
1405     // RemInst can't be the terminator if it has local stuff depending on it.
1406     assert(!ReverseDeps.empty() && !isa<TerminatorInst>(RemInst) &&
1407            "Nothing can locally depend on a terminator");
1408
1409     for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
1410          E = ReverseDeps.end(); I != E; ++I) {
1411       Instruction *InstDependingOnRemInst = *I;
1412       assert(InstDependingOnRemInst != RemInst &&
1413              "Already removed our local dep info");
1414
1415       LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
1416
1417       // Make sure to remember that new things depend on NewDepInst.
1418       assert(NewDirtyVal.getInst() && "There is no way something else can have "
1419              "a local dep on this if it is a terminator!");
1420       ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(),
1421                                                 InstDependingOnRemInst));
1422     }
1423
1424     ReverseLocalDeps.erase(ReverseDepIt);
1425
1426     // Add new reverse deps after scanning the set, to avoid invalidating the
1427     // 'ReverseDeps' reference.
1428     while (!ReverseDepsToAdd.empty()) {
1429       ReverseLocalDeps[ReverseDepsToAdd.back().first]
1430         .insert(ReverseDepsToAdd.back().second);
1431       ReverseDepsToAdd.pop_back();
1432     }
1433   }
1434
1435   ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
1436   if (ReverseDepIt != ReverseNonLocalDeps.end()) {
1437     SmallPtrSet<Instruction*, 4> &Set = ReverseDepIt->second;
1438     for (SmallPtrSet<Instruction*, 4>::iterator I = Set.begin(), E = Set.end();
1439          I != E; ++I) {
1440       assert(*I != RemInst && "Already removed NonLocalDep info for RemInst");
1441
1442       PerInstNLInfo &INLD = NonLocalDeps[*I];
1443       // The information is now dirty!
1444       INLD.second = true;
1445
1446       for (NonLocalDepInfo::iterator DI = INLD.first.begin(),
1447            DE = INLD.first.end(); DI != DE; ++DI) {
1448         if (DI->getResult().getInst() != RemInst) continue;
1449
1450         // Convert to a dirty entry for the subsequent instruction.
1451         DI->setResult(NewDirtyVal);
1452
1453         if (Instruction *NextI = NewDirtyVal.getInst())
1454           ReverseDepsToAdd.push_back(std::make_pair(NextI, *I));
1455       }
1456     }
1457
1458     ReverseNonLocalDeps.erase(ReverseDepIt);
1459
1460     // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
1461     while (!ReverseDepsToAdd.empty()) {
1462       ReverseNonLocalDeps[ReverseDepsToAdd.back().first]
1463         .insert(ReverseDepsToAdd.back().second);
1464       ReverseDepsToAdd.pop_back();
1465     }
1466   }
1467
1468   // If the instruction is in ReverseNonLocalPtrDeps then it appears as a
1469   // value in the NonLocalPointerDeps info.
1470   ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
1471     ReverseNonLocalPtrDeps.find(RemInst);
1472   if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
1473     SmallPtrSet<ValueIsLoadPair, 4> &Set = ReversePtrDepIt->second;
1474     SmallVector<std::pair<Instruction*, ValueIsLoadPair>,8> ReversePtrDepsToAdd;
1475
1476     for (SmallPtrSet<ValueIsLoadPair, 4>::iterator I = Set.begin(),
1477          E = Set.end(); I != E; ++I) {
1478       ValueIsLoadPair P = *I;
1479       assert(P.getPointer() != RemInst &&
1480              "Already removed NonLocalPointerDeps info for RemInst");
1481
1482       NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].NonLocalDeps;
1483
1484       // The cache is not valid for any specific block anymore.
1485       NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair();
1486
1487       // Update any entries for RemInst to use the instruction after it.
1488       for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();
1489            DI != DE; ++DI) {
1490         if (DI->getResult().getInst() != RemInst) continue;
1491
1492         // Convert to a dirty entry for the subsequent instruction.
1493         DI->setResult(NewDirtyVal);
1494
1495         if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
1496           ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
1497       }
1498
1499       // Re-sort the NonLocalDepInfo.  Changing the dirty entry to its
1500       // subsequent value may invalidate the sortedness.
1501       std::sort(NLPDI.begin(), NLPDI.end());
1502     }
1503
1504     ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
1505
1506     while (!ReversePtrDepsToAdd.empty()) {
1507       ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first]
1508         .insert(ReversePtrDepsToAdd.back().second);
1509       ReversePtrDepsToAdd.pop_back();
1510     }
1511   }
1512
1513
1514   assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
1515   AA->deleteValue(RemInst);
1516   DEBUG(verifyRemoved(RemInst));
1517 }
1518 /// verifyRemoved - Verify that the specified instruction does not occur
1519 /// in our internal data structures.
1520 void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
1521   for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
1522        E = LocalDeps.end(); I != E; ++I) {
1523     assert(I->first != D && "Inst occurs in data structures");
1524     assert(I->second.getInst() != D &&
1525            "Inst occurs in data structures");
1526   }
1527
1528   for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(),
1529        E = NonLocalPointerDeps.end(); I != E; ++I) {
1530     assert(I->first.getPointer() != D && "Inst occurs in NLPD map key");
1531     const NonLocalDepInfo &Val = I->second.NonLocalDeps;
1532     for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end();
1533          II != E; ++II)
1534       assert(II->getResult().getInst() != D && "Inst occurs as NLPD value");
1535   }
1536
1537   for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(),
1538        E = NonLocalDeps.end(); I != E; ++I) {
1539     assert(I->first != D && "Inst occurs in data structures");
1540     const PerInstNLInfo &INLD = I->second;
1541     for (NonLocalDepInfo::const_iterator II = INLD.first.begin(),
1542          EE = INLD.first.end(); II  != EE; ++II)
1543       assert(II->getResult().getInst() != D && "Inst occurs in data structures");
1544   }
1545
1546   for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),
1547        E = ReverseLocalDeps.end(); I != E; ++I) {
1548     assert(I->first != D && "Inst occurs in data structures");
1549     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
1550          EE = I->second.end(); II != EE; ++II)
1551       assert(*II != D && "Inst occurs in data structures");
1552   }
1553
1554   for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(),
1555        E = ReverseNonLocalDeps.end();
1556        I != E; ++I) {
1557     assert(I->first != D && "Inst occurs in data structures");
1558     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
1559          EE = I->second.end(); II != EE; ++II)
1560       assert(*II != D && "Inst occurs in data structures");
1561   }
1562
1563   for (ReverseNonLocalPtrDepTy::const_iterator
1564        I = ReverseNonLocalPtrDeps.begin(),
1565        E = ReverseNonLocalPtrDeps.end(); I != E; ++I) {
1566     assert(I->first != D && "Inst occurs in rev NLPD map");
1567
1568     for (SmallPtrSet<ValueIsLoadPair, 4>::const_iterator II = I->second.begin(),
1569          E = I->second.end(); II != E; ++II)
1570       assert(*II != ValueIsLoadPair(D, false) &&
1571              *II != ValueIsLoadPair(D, true) &&
1572              "Inst occurs in ReverseNonLocalPtrDeps map");
1573   }
1574
1575 }