lib/Analysis/MemoryDependenceAnalysis.cpp

   1 //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation  --*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements an analysis that determines, for a given memory
  11 // operation, what preceding memory operations it depends on.  It builds on
  12 // alias analysis information, and tries to provide a lazy, caching interface to
  13 // a common kind of alias information query.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #define DEBUG_TYPE "memdep"
  18 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
  19 #include "llvm/Constants.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/Analysis/AliasAnalysis.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include "llvm/Support/PredIteratorCache.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Target/TargetData.h"
  27 using namespace llvm;
  28
  29 STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");
  30 STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");
  31 STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");
  32
  33 STATISTIC(NumCacheNonLocalPtr,
  34           "Number of fully cached non-local ptr responses");
  35 STATISTIC(NumCacheDirtyNonLocalPtr,
  36           "Number of cached, but dirty, non-local ptr responses");
  37 STATISTIC(NumUncacheNonLocalPtr,
  38           "Number of uncached non-local ptr responses");
  39 STATISTIC(NumCacheCompleteNonLocalPtr,
  40           "Number of block queries that were completely cached");
  41
  42 char MemoryDependenceAnalysis::ID = 0;
  43
  44 // Register this pass...
  45 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
  46                                      "Memory Dependence Analysis", false, true);
  47
  48 MemoryDependenceAnalysis::MemoryDependenceAnalysis()
  49 : FunctionPass(&ID), PredCache(0) {
  50 }
  51 MemoryDependenceAnalysis::~MemoryDependenceAnalysis() {
  52 }
  53
  54 /// Clean up memory in between runs
  55 void MemoryDependenceAnalysis::releaseMemory() {
  56   LocalDeps.clear();
  57   NonLocalDeps.clear();
  58   NonLocalPointerDeps.clear();
  59   ReverseLocalDeps.clear();
  60   ReverseNonLocalDeps.clear();
  61   ReverseNonLocalPtrDeps.clear();
  62   PredCache->clear();
  63 }
  64
  65
  66
  67 /// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
  68 ///
  69 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
  70   AU.setPreservesAll();
  71   AU.addRequiredTransitive<AliasAnalysis>();
  72   AU.addRequiredTransitive<TargetData>();
  73 }
  74
  75 bool MemoryDependenceAnalysis::runOnFunction(Function &) {
  76   AA = &getAnalysis<AliasAnalysis>();
  77   TD = &getAnalysis<TargetData>();
  78   if (PredCache == 0)
  79     PredCache.reset(new PredIteratorCache());
  80   return false;
  81 }
  82
  83 /// RemoveFromReverseMap - This is a helper function that removes Val from
  84 /// 'Inst's set in ReverseMap.  If the set becomes empty, remove Inst's entry.
  85 template <typename KeyTy>
  86 static void RemoveFromReverseMap(DenseMap<Instruction*,
  87                                  SmallPtrSet<KeyTy*, 4> > &ReverseMap,
  88                                  Instruction *Inst, KeyTy *Val) {
  89   typename DenseMap<Instruction*, SmallPtrSet<KeyTy*, 4> >::iterator
  90   InstIt = ReverseMap.find(Inst);
  91   assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
  92   bool Found = InstIt->second.erase(Val);
  93   assert(Found && "Invalid reverse map!"); Found=Found;
  94   if (InstIt->second.empty())
  95     ReverseMap.erase(InstIt);
  96 }
  97
  98
  99 /// getCallSiteDependencyFrom - Private helper for finding the local
 100 /// dependencies of a call site.
 101 MemDepResult MemoryDependenceAnalysis::
 102 getCallSiteDependencyFrom(CallSite CS, BasicBlock::iterator ScanIt,
 103                           BasicBlock *BB) {
 104   // Walk backwards through the block, looking for dependencies
 105   while (ScanIt != BB->begin()) {
 106     Instruction *Inst = --ScanIt;
 107
 108     // If this inst is a memory op, get the pointer it accessed
 109     Value *Pointer = 0;
 110     uint64_t PointerSize = 0;
 111     if (StoreInst *S = dyn_cast<StoreInst>(Inst)) {
 112       Pointer = S->getPointerOperand();
 113       PointerSize = TD->getTypeStoreSize(S->getOperand(0)->getType());
 114     } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
 115       Pointer = V->getOperand(0);
 116       PointerSize = TD->getTypeStoreSize(V->getType());
 117     } else if (FreeInst *F = dyn_cast<FreeInst>(Inst)) {
 118       Pointer = F->getPointerOperand();
 119
 120       // FreeInsts erase the entire structure
 121       PointerSize = ~0ULL;
 122     } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
 123       CallSite InstCS = CallSite::get(Inst);
 124       // If these two calls do not interfere, look past it.
 125       if (AA->getModRefInfo(CS, InstCS) == AliasAnalysis::NoModRef)
 126         continue;
 127
 128       // FIXME: If this is a ref/ref result, we should ignore it!
 129       //  X = strlen(P);
 130       //  Y = strlen(Q);
 131       //  Z = strlen(P);  // Z = X
 132
 133       // If they interfere, we generally return clobber.  However, if they are
 134       // calls to the same read-only functions we return Def.
 135       if (!AA->onlyReadsMemory(CS) || CS.getCalledFunction() == 0 ||
 136           CS.getCalledFunction() != InstCS.getCalledFunction())
 137         return MemDepResult::getClobber(Inst);
 138       return MemDepResult::getDef(Inst);
 139     } else {
 140       // Non-memory instruction.
 141       continue;
 142     }
 143
 144     if (AA->getModRefInfo(CS, Pointer, PointerSize) != AliasAnalysis::NoModRef)
 145       return MemDepResult::getClobber(Inst);
 146   }
 147
 148   // No dependence found.  If this is the entry block of the function, it is a
 149   // clobber, otherwise it is non-local.
 150   if (BB != &BB->getParent()->getEntryBlock())
 151     return MemDepResult::getNonLocal();
 152   return MemDepResult::getClobber(ScanIt);
 153 }
 154
 155 /// getPointerDependencyFrom - Return the instruction on which a memory
 156 /// location depends.  If isLoad is true, this routine ignore may-aliases with
 157 /// read-only operations.
 158 MemDepResult MemoryDependenceAnalysis::
 159 getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad,
 160                          BasicBlock::iterator ScanIt, BasicBlock *BB) {
 161
 162   // Walk backwards through the basic block, looking for dependencies.
 163   while (ScanIt != BB->begin()) {
 164     Instruction *Inst = --ScanIt;
 165
 166     // Values depend on loads if the pointers are must aliased.  This means that
 167     // a load depends on another must aliased load from the same value.
 168     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
 169       Value *Pointer = LI->getPointerOperand();
 170       uint64_t PointerSize = TD->getTypeStoreSize(LI->getType());
 171
 172       // If we found a pointer, check if it could be the same as our pointer.
 173       AliasAnalysis::AliasResult R =
 174         AA->alias(Pointer, PointerSize, MemPtr, MemSize);
 175       if (R == AliasAnalysis::NoAlias)
 176         continue;
 177
 178       // May-alias loads don't depend on each other without a dependence.
 179       if (isLoad && R == AliasAnalysis::MayAlias)
 180         continue;
 181       // Stores depend on may and must aliased loads, loads depend on must-alias
 182       // loads.
 183       return MemDepResult::getDef(Inst);
 184     }
 185
 186     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 187       Value *Pointer = SI->getPointerOperand();
 188       uint64_t PointerSize = TD->getTypeStoreSize(SI->getOperand(0)->getType());
 189
 190       // If we found a pointer, check if it could be the same as our pointer.
 191       AliasAnalysis::AliasResult R =
 192         AA->alias(Pointer, PointerSize, MemPtr, MemSize);
 193
 194       if (R == AliasAnalysis::NoAlias)
 195         continue;
 196       if (R == AliasAnalysis::MayAlias)
 197         return MemDepResult::getClobber(Inst);
 198       return MemDepResult::getDef(Inst);
 199     }
 200
 201     // If this is an allocation, and if we know that the accessed pointer is to
 202     // the allocation, return Def.  This means that there is no dependence and
 203     // the access can be optimized based on that.  For example, a load could
 204     // turn into undef.
 205     if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
 206       Value *AccessPtr = MemPtr->getUnderlyingObject();
 207
 208       if (AccessPtr == AI ||
 209           AA->alias(AI, 1, AccessPtr, 1) == AliasAnalysis::MustAlias)
 210         return MemDepResult::getDef(AI);
 211       continue;
 212     }
 213
 214     // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
 215     // FIXME: If this is a load, we should ignore readonly calls!
 216     if (AA->getModRefInfo(Inst, MemPtr, MemSize) == AliasAnalysis::NoModRef)
 217       continue;
 218
 219     // Otherwise, there is a dependence.
 220     return MemDepResult::getClobber(Inst);
 221   }
 222
 223   // No dependence found.  If this is the entry block of the function, it is a
 224   // clobber, otherwise it is non-local.
 225   if (BB != &BB->getParent()->getEntryBlock())
 226     return MemDepResult::getNonLocal();
 227   return MemDepResult::getClobber(ScanIt);
 228 }
 229
 230 /// getDependency - Return the instruction on which a memory operation
 231 /// depends.
 232 MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
 233   Instruction *ScanPos = QueryInst;
 234
 235   // Check for a cached result
 236   MemDepResult &LocalCache = LocalDeps[QueryInst];
 237
 238   // If the cached entry is non-dirty, just return it.  Note that this depends
 239   // on MemDepResult's default constructing to 'dirty'.
 240   if (!LocalCache.isDirty())
 241     return LocalCache;
 242
 243   // Otherwise, if we have a dirty entry, we know we can start the scan at that
 244   // instruction, which may save us some work.
 245   if (Instruction *Inst = LocalCache.getInst()) {
 246     ScanPos = Inst;
 247
 248     RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
 249   }
 250
 251   BasicBlock *QueryParent = QueryInst->getParent();
 252
 253   Value *MemPtr = 0;
 254   uint64_t MemSize = 0;
 255
 256   // Do the scan.
 257   if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
 258     // No dependence found.  If this is the entry block of the function, it is a
 259     // clobber, otherwise it is non-local.
 260     if (QueryParent != &QueryParent->getParent()->getEntryBlock())
 261       LocalCache = MemDepResult::getNonLocal();
 262     else
 263       LocalCache = MemDepResult::getClobber(QueryInst);
 264   } else if (StoreInst *SI = dyn_cast<StoreInst>(QueryInst)) {
 265     // If this is a volatile store, don't mess around with it.  Just return the
 266     // previous instruction as a clobber.
 267     if (SI->isVolatile())
 268       LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
 269     else {
 270       MemPtr = SI->getPointerOperand();
 271       MemSize = TD->getTypeStoreSize(SI->getOperand(0)->getType());
 272     }
 273   } else if (LoadInst *LI = dyn_cast<LoadInst>(QueryInst)) {
 274     // If this is a volatile load, don't mess around with it.  Just return the
 275     // previous instruction as a clobber.
 276     if (LI->isVolatile())
 277       LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
 278     else {
 279       MemPtr = LI->getPointerOperand();
 280       MemSize = TD->getTypeStoreSize(LI->getType());
 281     }
 282   } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
 283     LocalCache = getCallSiteDependencyFrom(CallSite::get(QueryInst), ScanPos,
 284                                            QueryParent);
 285   } else if (FreeInst *FI = dyn_cast<FreeInst>(QueryInst)) {
 286     MemPtr = FI->getPointerOperand();
 287     // FreeInsts erase the entire structure, not just a field.
 288     MemSize = ~0UL;
 289   } else {
 290     // Non-memory instruction.
 291     LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
 292   }
 293
 294   // If we need to do a pointer scan, make it happen.
 295   if (MemPtr)
 296     LocalCache = getPointerDependencyFrom(MemPtr, MemSize,
 297                                           isa<LoadInst>(QueryInst),
 298                                           ScanPos, QueryParent);
 299
 300   // Remember the result!
 301   if (Instruction *I = LocalCache.getInst())
 302     ReverseLocalDeps[I].insert(QueryInst);
 303
 304   return LocalCache;
 305 }
 306
 307 /// getNonLocalDependency - Perform a full dependency query for the
 308 /// specified instruction, returning the set of blocks that the value is
 309 /// potentially live across.  The returned set of results will include a
 310 /// "NonLocal" result for all blocks where the value is live across.
 311 ///
 312 /// This method assumes the instruction returns a "nonlocal" dependency
 313 /// within its own block.
 314 ///
 315 const MemoryDependenceAnalysis::NonLocalDepInfo &
 316 MemoryDependenceAnalysis::getNonLocalDependency(Instruction *QueryInst) {
 317   // FIXME: Make this only be for callsites in the future.
 318   assert(isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst) ||
 319          isa<LoadInst>(QueryInst) || isa<StoreInst>(QueryInst));
 320   assert(getDependency(QueryInst).isNonLocal() &&
 321      "getNonLocalDependency should only be used on insts with non-local deps!");
 322   PerInstNLInfo &CacheP = NonLocalDeps[QueryInst];
 323   NonLocalDepInfo &Cache = CacheP.first;
 324
 325   /// DirtyBlocks - This is the set of blocks that need to be recomputed.  In
 326   /// the cached case, this can happen due to instructions being deleted etc. In
 327   /// the uncached case, this starts out as the set of predecessors we care
 328   /// about.
 329   SmallVector<BasicBlock*, 32> DirtyBlocks;
 330
 331   if (!Cache.empty()) {
 332     // Okay, we have a cache entry.  If we know it is not dirty, just return it
 333     // with no computation.
 334     if (!CacheP.second) {
 335       NumCacheNonLocal++;
 336       return Cache;
 337     }
 338
 339     // If we already have a partially computed set of results, scan them to
 340     // determine what is dirty, seeding our initial DirtyBlocks worklist.
 341     for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end();
 342        I != E; ++I)
 343       if (I->second.isDirty())
 344         DirtyBlocks.push_back(I->first);
 345
 346     // Sort the cache so that we can do fast binary search lookups below.
 347     std::sort(Cache.begin(), Cache.end());
 348
 349     ++NumCacheDirtyNonLocal;
 350     //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
 351     //     << Cache.size() << " cached: " << *QueryInst;
 352   } else {
 353     // Seed DirtyBlocks with each of the preds of QueryInst's block.
 354     BasicBlock *QueryBB = QueryInst->getParent();
 355     for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI)
 356       DirtyBlocks.push_back(*PI);
 357     NumUncacheNonLocal++;
 358   }
 359
 360   // Visited checked first, vector in sorted order.
 361   SmallPtrSet<BasicBlock*, 64> Visited;
 362
 363   unsigned NumSortedEntries = Cache.size();
 364
 365   // Iterate while we still have blocks to update.
 366   while (!DirtyBlocks.empty()) {
 367     BasicBlock *DirtyBB = DirtyBlocks.back();
 368     DirtyBlocks.pop_back();
 369
 370     // Already processed this block?
 371     if (!Visited.insert(DirtyBB))
 372       continue;
 373
 374     // Do a binary search to see if we already have an entry for this block in
 375     // the cache set.  If so, find it.
 376     NonLocalDepInfo::iterator Entry =
 377       std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries,
 378                        std::make_pair(DirtyBB, MemDepResult()));
 379     if (Entry != Cache.begin() && (&*Entry)[-1].first == DirtyBB)
 380       --Entry;
 381
 382     MemDepResult *ExistingResult = 0;
 383     if (Entry != Cache.begin()+NumSortedEntries &&
 384         Entry->first == DirtyBB) {
 385       // If we already have an entry, and if it isn't already dirty, the block
 386       // is done.
 387       if (!Entry->second.isDirty())
 388         continue;
 389
 390       // Otherwise, remember this slot so we can update the value.
 391       ExistingResult = &Entry->second;
 392     }
 393
 394     // If the dirty entry has a pointer, start scanning from it so we don't have
 395     // to rescan the entire block.
 396     BasicBlock::iterator ScanPos = DirtyBB->end();
 397     if (ExistingResult) {
 398       if (Instruction *Inst = ExistingResult->getInst()) {
 399         ScanPos = Inst;
 400         // We're removing QueryInst's use of Inst.
 401         RemoveFromReverseMap(ReverseNonLocalDeps, Inst, QueryInst);
 402       }
 403     }
 404
 405     // Find out if this block has a local dependency for QueryInst.
 406     MemDepResult Dep;
 407
 408     Value *MemPtr = 0;
 409     uint64_t MemSize = 0;
 410
 411     if (ScanPos == DirtyBB->begin()) {
 412       // No dependence found.  If this is the entry block of the function, it is a
 413       // clobber, otherwise it is non-local.
 414       if (DirtyBB != &DirtyBB->getParent()->getEntryBlock())
 415         Dep = MemDepResult::getNonLocal();
 416       else
 417         Dep = MemDepResult::getClobber(ScanPos);
 418     } else if (StoreInst *SI = dyn_cast<StoreInst>(QueryInst)) {
 419       // If this is a volatile store, don't mess around with it.  Just return the
 420       // previous instruction as a clobber.
 421       if (SI->isVolatile())
 422         Dep = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
 423       else {
 424         MemPtr = SI->getPointerOperand();
 425         MemSize = TD->getTypeStoreSize(SI->getOperand(0)->getType());
 426       }
 427     } else if (LoadInst *LI = dyn_cast<LoadInst>(QueryInst)) {
 428       // If this is a volatile load, don't mess around with it.  Just return the
 429       // previous instruction as a clobber.
 430       if (LI->isVolatile())
 431         Dep = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
 432       else {
 433         MemPtr = LI->getPointerOperand();
 434         MemSize = TD->getTypeStoreSize(LI->getType());
 435       }
 436     } else {
 437       assert(isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst));
 438       Dep = getCallSiteDependencyFrom(CallSite::get(QueryInst), ScanPos,
 439                                       DirtyBB);
 440     }
 441
 442     if (MemPtr)
 443       Dep = getPointerDependencyFrom(MemPtr, MemSize, isa<LoadInst>(QueryInst),
 444                                      ScanPos, DirtyBB);
 445
 446     // If we had a dirty entry for the block, update it.  Otherwise, just add
 447     // a new entry.
 448     if (ExistingResult)
 449       *ExistingResult = Dep;
 450     else
 451       Cache.push_back(std::make_pair(DirtyBB, Dep));
 452
 453     // If the block has a dependency (i.e. it isn't completely transparent to
 454     // the value), remember the association!
 455     if (!Dep.isNonLocal()) {
 456       // Keep the ReverseNonLocalDeps map up to date so we can efficiently
 457       // update this when we remove instructions.
 458       if (Instruction *Inst = Dep.getInst())
 459         ReverseNonLocalDeps[Inst].insert(QueryInst);
 460     } else {
 461
 462       // If the block *is* completely transparent to the load, we need to check
 463       // the predecessors of this block.  Add them to our worklist.
 464       for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI)
 465         DirtyBlocks.push_back(*PI);
 466     }
 467   }
 468
 469   return Cache;
 470 }
 471
 472 /// getNonLocalPointerDependency - Perform a full dependency query for an
 473 /// access to the specified (non-volatile) memory location, returning the
 474 /// set of instructions that either define or clobber the value.
 475 ///
 476 /// This method assumes the pointer has a "NonLocal" dependency within its
 477 /// own block.
 478 ///
 479 void MemoryDependenceAnalysis::
 480 getNonLocalPointerDependency(Value *Pointer, bool isLoad, BasicBlock *FromBB,
 481                              SmallVectorImpl<NonLocalDepEntry> &Result) {
 482   assert(isa<PointerType>(Pointer->getType()) &&
 483          "Can't get pointer deps of a non-pointer!");
 484   Result.clear();
 485
 486   // We know that the pointer value is live into FromBB find the def/clobbers
 487   // from presecessors.
 488   const Type *EltTy = cast<PointerType>(Pointer->getType())->getElementType();
 489   uint64_t PointeeSize = TD->getTypeStoreSize(EltTy);
 490
 491   // While we have blocks to analyze, get their values.
 492   SmallPtrSet<BasicBlock*, 64> Visited;
 493   getNonLocalPointerDepFromBB(Pointer, PointeeSize, isLoad, FromBB,
 494                               Result, Visited);
 495 }
 496
 497 /// GetNonLocalInfoForBlock - Compute the memdep value for BB with
 498 /// Pointer/PointeeSize using either cached information in Cache or by doing a
 499 /// lookup (which may use dirty cache info if available).  If we do a lookup,
 500 /// add the result to the cache.
 501 MemDepResult MemoryDependenceAnalysis::
 502 GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize,
 503                         bool isLoad, BasicBlock *BB,
 504                         NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
 505
 506   // Do a binary search to see if we already have an entry for this block in
 507   // the cache set.  If so, find it.
 508   NonLocalDepInfo::iterator Entry =
 509     std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
 510                      std::make_pair(BB, MemDepResult()));
 511   if (Entry != Cache->begin() && (&*Entry)[-1].first == BB)
 512     --Entry;
 513
 514   MemDepResult *ExistingResult = 0;
 515   if (Entry != Cache->begin()+NumSortedEntries && Entry->first == BB)
 516     ExistingResult = &Entry->second;
 517
 518   // If we have a cached entry, and it is non-dirty, use it as the value for
 519   // this dependency.
 520   if (ExistingResult && !ExistingResult->isDirty()) {
 521     ++NumCacheNonLocalPtr;
 522     return *ExistingResult;
 523   }
 524
 525   // Otherwise, we have to scan for the value.  If we have a dirty cache
 526   // entry, start scanning from its position, otherwise we scan from the end
 527   // of the block.
 528   BasicBlock::iterator ScanPos = BB->end();
 529   if (ExistingResult && ExistingResult->getInst()) {
 530     assert(ExistingResult->getInst()->getParent() == BB &&
 531            "Instruction invalidated?");
 532     ++NumCacheDirtyNonLocalPtr;
 533     ScanPos = ExistingResult->getInst();
 534
 535     // Eliminating the dirty entry from 'Cache', so update the reverse info.
 536     ValueIsLoadPair CacheKey(Pointer, isLoad);
 537     RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos,
 538                          CacheKey.getOpaqueValue());
 539   } else {
 540     ++NumUncacheNonLocalPtr;
 541   }
 542
 543   // Scan the block for the dependency.
 544   MemDepResult Dep = getPointerDependencyFrom(Pointer, PointeeSize, isLoad,
 545                                               ScanPos, BB);
 546
 547   // If we had a dirty entry for the block, update it.  Otherwise, just add
 548   // a new entry.
 549   if (ExistingResult)
 550     *ExistingResult = Dep;
 551   else
 552     Cache->push_back(std::make_pair(BB, Dep));
 553
 554   // If the block has a dependency (i.e. it isn't completely transparent to
 555   // the value), remember the reverse association because we just added it
 556   // to Cache!
 557   if (Dep.isNonLocal())
 558     return Dep;
 559
 560   // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
 561   // update MemDep when we remove instructions.
 562   Instruction *Inst = Dep.getInst();
 563   assert(Inst && "Didn't depend on anything?");
 564   ValueIsLoadPair CacheKey(Pointer, isLoad);
 565   ReverseNonLocalPtrDeps[Inst].insert(CacheKey.getOpaqueValue());
 566   return Dep;
 567 }
 568
 569
 570 /// getNonLocalPointerDepFromBB -
 571 void MemoryDependenceAnalysis::
 572 getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize,
 573                             bool isLoad, BasicBlock *StartBB,
 574                             SmallVectorImpl<NonLocalDepEntry> &Result,
 575                             SmallPtrSet<BasicBlock*, 64> &Visited) {
 576   // Look up the cached info for Pointer.
 577   ValueIsLoadPair CacheKey(Pointer, isLoad);
 578
 579   std::pair<BasicBlock*, NonLocalDepInfo> &CacheInfo =
 580     NonLocalPointerDeps[CacheKey];
 581   NonLocalDepInfo *Cache = &CacheInfo.second;
 582
 583   // If we have valid cached information for exactly the block we are
 584   // investigating, just return it with no recomputation.
 585   if (CacheInfo.first == StartBB) {
 586     for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
 587          I != E; ++I)
 588       if (!I->second.isNonLocal())
 589         Result.push_back(*I);
 590     ++NumCacheCompleteNonLocalPtr;
 591     return;
 592   }
 593
 594   // Otherwise, either this is a new block, a block with an invalid cache
 595   // pointer or one that we're about to invalidate by putting more info into it
 596   // than its valid cache info.  If empty, the result will be valid cache info,
 597   // otherwise it isn't.
 598   CacheInfo.first = Cache->empty() ? StartBB : 0;
 599
 600   SmallVector<BasicBlock*, 32> Worklist;
 601   Worklist.push_back(StartBB);
 602
 603   // Keep track of the entries that we know are sorted.  Previously cached
 604   // entries will all be sorted.  The entries we add we only sort on demand (we
 605   // don't insert every element into its sorted position).  We know that we
 606   // won't get any reuse from currently inserted values, because we don't
 607   // revisit blocks after we insert info for them.
 608   unsigned NumSortedEntries = Cache->size();
 609
 610   // SkipFirstBlock - If this is the very first block that we're processing, we
 611   // don't want to scan or think about its body, because the client was supposed
 612   // to do a local dependence query.  Instead, just start processing it by
 613   // adding its predecessors to the worklist and iterating.
 614   bool SkipFirstBlock = Visited.empty();
 615
 616   while (!Worklist.empty()) {
 617     BasicBlock *BB = Worklist.pop_back_val();
 618
 619     // Skip the first block if we have it.
 620     if (SkipFirstBlock) {
 621       SkipFirstBlock = false;
 622     } else {
 623       // Analyze the dependency of *Pointer in FromBB.  See if we already have
 624       // been here.
 625       if (!Visited.insert(BB))
 626         continue;
 627
 628       // Get the dependency info for Pointer in BB.  If we have cached
 629       // information, we will use it, otherwise we compute it.
 630       MemDepResult Dep = GetNonLocalInfoForBlock(Pointer, PointeeSize, isLoad,
 631                                                  BB, Cache, NumSortedEntries);
 632
 633       // If we got a Def or Clobber, add this to the list of results.
 634       if (!Dep.isNonLocal()) {
 635         Result.push_back(NonLocalDepEntry(BB, Dep));
 636         continue;
 637       }
 638     }
 639
 640     // Otherwise, we have to process all the predecessors of this block to scan
 641     // them as well.
 642     for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
 643       // TODO: PHI TRANSLATE.
 644       Worklist.push_back(*PI);
 645     }
 646   }
 647
 648   // Okay, we're done now.  If we added new values to the cache, re-sort it.
 649   switch (Cache->size()-NumSortedEntries) {
 650   case 0:
 651     // done, no new entries.
 652     break;
 653   case 2: {
 654     // Two new entries, insert the last one into place.
 655     NonLocalDepEntry Val = Cache->back();
 656     Cache->pop_back();
 657     NonLocalDepInfo::iterator Entry =
 658     std::upper_bound(Cache->begin(), Cache->end()-1, Val);
 659     Cache->insert(Entry, Val);
 660     // FALL THROUGH.
 661   }
 662   case 1: {
 663     // One new entry, Just insert the new value at the appropriate position.
 664     NonLocalDepEntry Val = Cache->back();
 665     Cache->pop_back();
 666     NonLocalDepInfo::iterator Entry =
 667       std::upper_bound(Cache->begin(), Cache->end(), Val);
 668     Cache->insert(Entry, Val);
 669     break;
 670   }
 671   default:
 672     // Added many values, do a full scale sort.
 673     std::sort(Cache->begin(), Cache->end());
 674   }
 675 }
 676
 677 /// RemoveCachedNonLocalPointerDependencies - If P exists in
 678 /// CachedNonLocalPointerInfo, remove it.
 679 void MemoryDependenceAnalysis::
 680 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) {
 681   CachedNonLocalPointerInfo::iterator It =
 682     NonLocalPointerDeps.find(P);
 683   if (It == NonLocalPointerDeps.end()) return;
 684
 685   // Remove all of the entries in the BB->val map.  This involves removing
 686   // instructions from the reverse map.
 687   NonLocalDepInfo &PInfo = It->second.second;
 688
 689   for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
 690     Instruction *Target = PInfo[i].second.getInst();
 691     if (Target == 0) continue;  // Ignore non-local dep results.
 692     assert(Target->getParent() == PInfo[i].first && Target != P.getPointer());
 693
 694     // Eliminating the dirty entry from 'Cache', so update the reverse info.
 695     RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P.getOpaqueValue());
 696   }
 697
 698   // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
 699   NonLocalPointerDeps.erase(It);
 700 }
 701
 702
 703 /// removeInstruction - Remove an instruction from the dependence analysis,
 704 /// updating the dependence of instructions that previously depended on it.
 705 /// This method attempts to keep the cache coherent using the reverse map.
 706 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
 707   // Walk through the Non-local dependencies, removing this one as the value
 708   // for any cached queries.
 709   NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
 710   if (NLDI != NonLocalDeps.end()) {
 711     NonLocalDepInfo &BlockMap = NLDI->second.first;
 712     for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end();
 713          DI != DE; ++DI)
 714       if (Instruction *Inst = DI->second.getInst())
 715         RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
 716     NonLocalDeps.erase(NLDI);
 717   }
 718
 719   // If we have a cached local dependence query for this instruction, remove it.
 720   //
 721   LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
 722   if (LocalDepEntry != LocalDeps.end()) {
 723     // Remove us from DepInst's reverse set now that the local dep info is gone.
 724     if (Instruction *Inst = LocalDepEntry->second.getInst())
 725       RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
 726
 727     // Remove this local dependency info.
 728     LocalDeps.erase(LocalDepEntry);
 729   }
 730
 731   // If we have any cached pointer dependencies on this instruction, remove
 732   // them.  If the instruction has non-pointer type, then it can't be a pointer
 733   // base.
 734
 735   // Remove it from both the load info and the store info.  The instruction
 736   // can't be in either of these maps if it is non-pointer.
 737   if (isa<PointerType>(RemInst->getType())) {
 738     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
 739     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
 740   }
 741
 742   // Loop over all of the things that depend on the instruction we're removing.
 743   //
 744   SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd;
 745
 746   // If we find RemInst as a clobber or Def in any of the maps for other values,
 747   // we need to replace its entry with a dirty version of the instruction after
 748   // it.  If RemInst is a terminator, we use a null dirty value.
 749   //
 750   // Using a dirty version of the instruction after RemInst saves having to scan
 751   // the entire block to get to this point.
 752   MemDepResult NewDirtyVal;
 753   if (!RemInst->isTerminator())
 754     NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst));
 755
 756   ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
 757   if (ReverseDepIt != ReverseLocalDeps.end()) {
 758     SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
 759     // RemInst can't be the terminator if it has local stuff depending on it.
 760     assert(!ReverseDeps.empty() && !isa<TerminatorInst>(RemInst) &&
 761            "Nothing can locally depend on a terminator");
 762
 763     for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
 764          E = ReverseDeps.end(); I != E; ++I) {
 765       Instruction *InstDependingOnRemInst = *I;
 766       assert(InstDependingOnRemInst != RemInst &&
 767              "Already removed our local dep info");
 768
 769       LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
 770
 771       // Make sure to remember that new things depend on NewDepInst.
 772       assert(NewDirtyVal.getInst() && "There is no way something else can have "
 773              "a local dep on this if it is a terminator!");
 774       ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(),
 775                                                 InstDependingOnRemInst));
 776     }
 777
 778     ReverseLocalDeps.erase(ReverseDepIt);
 779
 780     // Add new reverse deps after scanning the set, to avoid invalidating the
 781     // 'ReverseDeps' reference.
 782     while (!ReverseDepsToAdd.empty()) {
 783       ReverseLocalDeps[ReverseDepsToAdd.back().first]
 784         .insert(ReverseDepsToAdd.back().second);
 785       ReverseDepsToAdd.pop_back();
 786     }
 787   }
 788
 789   ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
 790   if (ReverseDepIt != ReverseNonLocalDeps.end()) {
 791     SmallPtrSet<Instruction*, 4> &Set = ReverseDepIt->second;
 792     for (SmallPtrSet<Instruction*, 4>::iterator I = Set.begin(), E = Set.end();
 793          I != E; ++I) {
 794       assert(*I != RemInst && "Already removed NonLocalDep info for RemInst");
 795
 796       PerInstNLInfo &INLD = NonLocalDeps[*I];
 797       // The information is now dirty!
 798       INLD.second = true;
 799
 800       for (NonLocalDepInfo::iterator DI = INLD.first.begin(),
 801            DE = INLD.first.end(); DI != DE; ++DI) {
 802         if (DI->second.getInst() != RemInst) continue;
 803
 804         // Convert to a dirty entry for the subsequent instruction.
 805         DI->second = NewDirtyVal;
 806
 807         if (Instruction *NextI = NewDirtyVal.getInst())
 808           ReverseDepsToAdd.push_back(std::make_pair(NextI, *I));
 809       }
 810     }
 811
 812     ReverseNonLocalDeps.erase(ReverseDepIt);
 813
 814     // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
 815     while (!ReverseDepsToAdd.empty()) {
 816       ReverseNonLocalDeps[ReverseDepsToAdd.back().first]
 817         .insert(ReverseDepsToAdd.back().second);
 818       ReverseDepsToAdd.pop_back();
 819     }
 820   }
 821
 822   // If the instruction is in ReverseNonLocalPtrDeps then it appears as a
 823   // value in the NonLocalPointerDeps info.
 824   ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
 825     ReverseNonLocalPtrDeps.find(RemInst);
 826   if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
 827     SmallPtrSet<void*, 4> &Set = ReversePtrDepIt->second;
 828     SmallVector<std::pair<Instruction*, ValueIsLoadPair>,8> ReversePtrDepsToAdd;
 829
 830     for (SmallPtrSet<void*, 4>::iterator I = Set.begin(), E = Set.end();
 831          I != E; ++I) {
 832       ValueIsLoadPair P;
 833       P.setFromOpaqueValue(*I);
 834       assert(P.getPointer() != RemInst &&
 835              "Already removed NonLocalPointerDeps info for RemInst");
 836
 837       NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].second;
 838
 839       // The cache is not valid for any specific block anymore.
 840       NonLocalPointerDeps[P].first = 0;
 841
 842       // Update any entries for RemInst to use the instruction after it.
 843       for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();
 844            DI != DE; ++DI) {
 845         if (DI->second.getInst() != RemInst) continue;
 846
 847         // Convert to a dirty entry for the subsequent instruction.
 848         DI->second = NewDirtyVal;
 849
 850         if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
 851           ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
 852       }
 853     }
 854
 855     ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
 856
 857     while (!ReversePtrDepsToAdd.empty()) {
 858       ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first]
 859         .insert(ReversePtrDepsToAdd.back().second.getOpaqueValue());
 860       ReversePtrDepsToAdd.pop_back();
 861     }
 862   }
 863
 864
 865   assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
 866   AA->deleteValue(RemInst);
 867   DEBUG(verifyRemoved(RemInst));
 868 }
 869
 870 /// verifyRemoved - Verify that the specified instruction does not occur
 871 /// in our internal data structures.
 872 void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
 873   for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
 874        E = LocalDeps.end(); I != E; ++I) {
 875     assert(I->first != D && "Inst occurs in data structures");
 876     assert(I->second.getInst() != D &&
 877            "Inst occurs in data structures");
 878   }
 879
 880   for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(),
 881        E = NonLocalPointerDeps.end(); I != E; ++I) {
 882     assert(I->first.getPointer() != D && "Inst occurs in NLPD map key");
 883     const NonLocalDepInfo &Val = I->second.second;
 884     for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end();
 885          II != E; ++II)
 886       assert(II->second.getInst() != D && "Inst occurs as NLPD value");
 887   }
 888
 889   for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(),
 890        E = NonLocalDeps.end(); I != E; ++I) {
 891     assert(I->first != D && "Inst occurs in data structures");
 892     const PerInstNLInfo &INLD = I->second;
 893     for (NonLocalDepInfo::const_iterator II = INLD.first.begin(),
 894          EE = INLD.first.end(); II  != EE; ++II)
 895       assert(II->second.getInst() != D && "Inst occurs in data structures");
 896   }
 897
 898   for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),
 899        E = ReverseLocalDeps.end(); I != E; ++I) {
 900     assert(I->first != D && "Inst occurs in data structures");
 901     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
 902          EE = I->second.end(); II != EE; ++II)
 903       assert(*II != D && "Inst occurs in data structures");
 904   }
 905
 906   for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(),
 907        E = ReverseNonLocalDeps.end();
 908        I != E; ++I) {
 909     assert(I->first != D && "Inst occurs in data structures");
 910     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
 911          EE = I->second.end(); II != EE; ++II)
 912       assert(*II != D && "Inst occurs in data structures");
 913   }
 914
 915   for (ReverseNonLocalPtrDepTy::const_iterator
 916        I = ReverseNonLocalPtrDeps.begin(),
 917        E = ReverseNonLocalPtrDeps.end(); I != E; ++I) {
 918     assert(I->first != D && "Inst occurs in rev NLPD map");
 919
 920     for (SmallPtrSet<void*, 4>::const_iterator II = I->second.begin(),
 921          E = I->second.end(); II != E; ++II)
 922       assert(*II != ValueIsLoadPair(D, false).getOpaqueValue() &&
 923              *II != ValueIsLoadPair(D, true).getOpaqueValue() &&
 924              "Inst occurs in ReverseNonLocalPtrDeps map");
 925   }
 926
 927 }