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