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