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   assert(isa<PointerType>(Pointer->getType()) &&
 458          "Can't get pointer deps of a non-pointer!");
 459   Result.clear();
 460
 461   // We know that the pointer value is live into FromBB find the def/clobbers
 462   // from presecessors.
 463   const Type *EltTy = cast<PointerType>(Pointer->getType())->getElementType();
 464   uint64_t PointeeSize = TD->getTypeStoreSize(EltTy);
 465
 466   // While we have blocks to analyze, get their values.
 467   SmallPtrSet<BasicBlock*, 64> Visited;
 468
 469   for (pred_iterator PI = pred_begin(FromBB), E = pred_end(FromBB); PI != E;
 470        ++PI) {
 471     // TODO: PHI TRANSLATE.
 472     getNonLocalPointerDepInternal(Pointer, PointeeSize, isLoad, *PI,
 473                                   Result, Visited);
 474   }
 475 }
 476
 477 void MemoryDependenceAnalysis::
 478 getNonLocalPointerDepInternal(Value *Pointer, uint64_t PointeeSize,
 479                               bool isLoad, BasicBlock *StartBB,
 480                               SmallVectorImpl<NonLocalDepEntry> &Result,
 481                               SmallPtrSet<BasicBlock*, 64> &Visited) {
 482   SmallVector<BasicBlock*, 32> Worklist;
 483   Worklist.push_back(StartBB);
 484
 485   // Look up the cached info for Pointer.
 486   ValueIsLoadPair CacheKey(Pointer, isLoad);
 487   NonLocalDepInfo *Cache = &NonLocalPointerDeps[CacheKey];
 488
 489   // Keep track of the entries that we know are sorted.  Previously cached
 490   // entries will all be sorted.  The entries we add we only sort on demand (we
 491   // don't insert every element into its sorted position).  We know that we
 492   // won't get any reuse from currently inserted values, because we don't
 493   // revisit blocks after we insert info for them.
 494   unsigned NumSortedEntries = Cache->size();
 495
 496   while (!Worklist.empty()) {
 497     BasicBlock *BB = Worklist.pop_back_val();
 498
 499     // Analyze the dependency of *Pointer in FromBB.  See if we already have
 500     // been here.
 501     if (!Visited.insert(BB))
 502       continue;
 503
 504     // Get the dependency info for Pointer in BB.  If we have cached
 505     // information, we will use it, otherwise we compute it.
 506
 507     // Do a binary search to see if we already have an entry for this block in
 508     // the cache set.  If so, find it.
 509     NonLocalDepInfo::iterator Entry =
 510       std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
 511                        std::make_pair(BB, MemDepResult()));
 512     if (Entry != Cache->begin() && (&*Entry)[-1].first == BB)
 513       --Entry;
 514
 515     MemDepResult *ExistingResult = 0;
 516     if (Entry != Cache->begin()+NumSortedEntries && Entry->first == BB)
 517       ExistingResult = &Entry->second;
 518
 519     // If we have a cached entry, and it is non-dirty, use it as the value for
 520     // this dependency.
 521     MemDepResult Dep;
 522     if (ExistingResult && !ExistingResult->isDirty()) {
 523       Dep = *ExistingResult;
 524       ++NumCacheNonLocalPtr;
 525     } else {
 526       // Otherwise, we have to scan for the value.  If we have a dirty cache
 527       // entry, start scanning from its position, otherwise we scan from the end
 528       // of the block.
 529       BasicBlock::iterator ScanPos = BB->end();
 530       if (ExistingResult && ExistingResult->getInst()) {
 531         assert(ExistingResult->getInst()->getParent() == BB &&
 532                "Instruction invalidated?");
 533         ++NumCacheDirtyNonLocalPtr;
 534         ScanPos = ExistingResult->getInst();
 535
 536         // Eliminating the dirty entry from 'Cache', so update the reverse info.
 537         RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos,
 538                              CacheKey.getOpaqueValue());
 539       } else {
 540         ++NumUncacheNonLocalPtr;
 541       }
 542
 543       // Scan the block for the dependency.
 544       Dep = getPointerDependencyFrom(Pointer, PointeeSize, isLoad, ScanPos, BB);
 545
 546       // If we had a dirty entry for the block, update it.  Otherwise, just add
 547       // a new entry.
 548       if (ExistingResult)
 549         *ExistingResult = Dep;
 550       else
 551         Cache->push_back(std::make_pair(BB, Dep));
 552
 553       // If the block has a dependency (i.e. it isn't completely transparent to
 554       // the value), remember the reverse association because we just added it
 555       // to Cache!
 556       if (!Dep.isNonLocal()) {
 557         // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
 558         // update MemDep when we remove instructions.
 559         Instruction *Inst = Dep.getInst();
 560         assert(Inst && "Didn't depend on anything?");
 561         ReverseNonLocalPtrDeps[Inst].insert(CacheKey.getOpaqueValue());
 562       }
 563     }
 564
 565     // If we got a Def or Clobber, add this to the list of results.
 566     if (!Dep.isNonLocal()) {
 567       Result.push_back(NonLocalDepEntry(BB, Dep));
 568       continue;
 569     }
 570
 571     // Otherwise, we have to process all the predecessors of this block to scan
 572     // them as well.
 573     for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
 574       // TODO: PHI TRANSLATE.
 575       Worklist.push_back(*PI);
 576     }
 577   }
 578
 579   // If we computed new values, re-sort Cache.
 580   if (NumSortedEntries != Cache->size())
 581     std::sort(Cache->begin(), Cache->end());
 582 }
 583
 584 /// RemoveCachedNonLocalPointerDependencies - If P exists in
 585 /// CachedNonLocalPointerInfo, remove it.
 586 void MemoryDependenceAnalysis::
 587 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) {
 588   CachedNonLocalPointerInfo::iterator It =
 589     NonLocalPointerDeps.find(P);
 590   if (It == NonLocalPointerDeps.end()) return;
 591
 592   // Remove all of the entries in the BB->val map.  This involves removing
 593   // instructions from the reverse map.
 594   NonLocalDepInfo &PInfo = It->second;
 595
 596   for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
 597     Instruction *Target = PInfo[i].second.getInst();
 598     if (Target == 0) continue;  // Ignore non-local dep results.
 599     assert(Target->getParent() == PInfo[i].first && Target != P.getPointer());
 600
 601     // Eliminating the dirty entry from 'Cache', so update the reverse info.
 602     RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P.getOpaqueValue());
 603   }
 604
 605   // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
 606   NonLocalPointerDeps.erase(It);
 607 }
 608
 609
 610 /// removeInstruction - Remove an instruction from the dependence analysis,
 611 /// updating the dependence of instructions that previously depended on it.
 612 /// This method attempts to keep the cache coherent using the reverse map.
 613 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
 614   // Walk through the Non-local dependencies, removing this one as the value
 615   // for any cached queries.
 616   NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
 617   if (NLDI != NonLocalDeps.end()) {
 618     NonLocalDepInfo &BlockMap = NLDI->second.first;
 619     for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end();
 620          DI != DE; ++DI)
 621       if (Instruction *Inst = DI->second.getInst())
 622         RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
 623     NonLocalDeps.erase(NLDI);
 624   }
 625
 626   // If we have a cached local dependence query for this instruction, remove it.
 627   //
 628   LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
 629   if (LocalDepEntry != LocalDeps.end()) {
 630     // Remove us from DepInst's reverse set now that the local dep info is gone.
 631     if (Instruction *Inst = LocalDepEntry->second.getInst())
 632       RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
 633
 634     // Remove this local dependency info.
 635     LocalDeps.erase(LocalDepEntry);
 636   }
 637
 638   // If we have any cached pointer dependencies on this instruction, remove
 639   // them.  If the instruction has non-pointer type, then it can't be a pointer
 640   // base.
 641
 642   // Remove it from both the load info and the store info.  The instruction
 643   // can't be in either of these maps if it is non-pointer.
 644   if (isa<PointerType>(RemInst->getType())) {
 645     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
 646     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
 647   }
 648
 649   // Loop over all of the things that depend on the instruction we're removing.
 650   //
 651   SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd;
 652
 653   // If we find RemInst as a clobber or Def in any of the maps for other values,
 654   // we need to replace its entry with a dirty version of the instruction after
 655   // it.  If RemInst is a terminator, we use a null dirty value.
 656   //
 657   // Using a dirty version of the instruction after RemInst saves having to scan
 658   // the entire block to get to this point.
 659   MemDepResult NewDirtyVal;
 660   if (!RemInst->isTerminator())
 661     NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst));
 662
 663   ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
 664   if (ReverseDepIt != ReverseLocalDeps.end()) {
 665     SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
 666     // RemInst can't be the terminator if it has local stuff depending on it.
 667     assert(!ReverseDeps.empty() && !isa<TerminatorInst>(RemInst) &&
 668            "Nothing can locally depend on a terminator");
 669
 670     for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
 671          E = ReverseDeps.end(); I != E; ++I) {
 672       Instruction *InstDependingOnRemInst = *I;
 673       assert(InstDependingOnRemInst != RemInst &&
 674              "Already removed our local dep info");
 675
 676       LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
 677
 678       // Make sure to remember that new things depend on NewDepInst.
 679       assert(NewDirtyVal.getInst() && "There is no way something else can have "
 680              "a local dep on this if it is a terminator!");
 681       ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(),
 682                                                 InstDependingOnRemInst));
 683     }
 684
 685     ReverseLocalDeps.erase(ReverseDepIt);
 686
 687     // Add new reverse deps after scanning the set, to avoid invalidating the
 688     // 'ReverseDeps' reference.
 689     while (!ReverseDepsToAdd.empty()) {
 690       ReverseLocalDeps[ReverseDepsToAdd.back().first]
 691         .insert(ReverseDepsToAdd.back().second);
 692       ReverseDepsToAdd.pop_back();
 693     }
 694   }
 695
 696   ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
 697   if (ReverseDepIt != ReverseNonLocalDeps.end()) {
 698     SmallPtrSet<Instruction*, 4> &Set = ReverseDepIt->second;
 699     for (SmallPtrSet<Instruction*, 4>::iterator I = Set.begin(), E = Set.end();
 700          I != E; ++I) {
 701       assert(*I != RemInst && "Already removed NonLocalDep info for RemInst");
 702
 703       PerInstNLInfo &INLD = NonLocalDeps[*I];
 704       // The information is now dirty!
 705       INLD.second = true;
 706
 707       for (NonLocalDepInfo::iterator DI = INLD.first.begin(),
 708            DE = INLD.first.end(); DI != DE; ++DI) {
 709         if (DI->second.getInst() != RemInst) continue;
 710
 711         // Convert to a dirty entry for the subsequent instruction.
 712         DI->second = NewDirtyVal;
 713
 714         if (Instruction *NextI = NewDirtyVal.getInst())
 715           ReverseDepsToAdd.push_back(std::make_pair(NextI, *I));
 716       }
 717     }
 718
 719     ReverseNonLocalDeps.erase(ReverseDepIt);
 720
 721     // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
 722     while (!ReverseDepsToAdd.empty()) {
 723       ReverseNonLocalDeps[ReverseDepsToAdd.back().first]
 724         .insert(ReverseDepsToAdd.back().second);
 725       ReverseDepsToAdd.pop_back();
 726     }
 727   }
 728
 729   // If the instruction is in ReverseNonLocalPtrDeps then it appears as a
 730   // value in the NonLocalPointerDeps info.
 731   ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
 732     ReverseNonLocalPtrDeps.find(RemInst);
 733   if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
 734     SmallPtrSet<void*, 4> &Set = ReversePtrDepIt->second;
 735     SmallVector<std::pair<Instruction*, ValueIsLoadPair>,8> ReversePtrDepsToAdd;
 736
 737     for (SmallPtrSet<void*, 4>::iterator I = Set.begin(), E = Set.end();
 738          I != E; ++I) {
 739       ValueIsLoadPair P;
 740       P.setFromOpaqueValue(*I);
 741       assert(P.getPointer() != RemInst &&
 742              "Already removed NonLocalPointerDeps info for RemInst");
 743
 744       NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P];
 745
 746       // Update any entries for RemInst to use the instruction after it.
 747       for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();
 748            DI != DE; ++DI) {
 749         if (DI->second.getInst() != RemInst) continue;
 750
 751         // Convert to a dirty entry for the subsequent instruction.
 752         DI->second = NewDirtyVal;
 753
 754         if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
 755           ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
 756       }
 757     }
 758
 759     ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
 760
 761     while (!ReversePtrDepsToAdd.empty()) {
 762       ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first]
 763         .insert(ReversePtrDepsToAdd.back().second.getOpaqueValue());
 764       ReversePtrDepsToAdd.pop_back();
 765     }
 766   }
 767
 768
 769   assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
 770   AA->deleteValue(RemInst);
 771   DEBUG(verifyRemoved(RemInst));
 772 }
 773
 774 /// verifyRemoved - Verify that the specified instruction does not occur
 775 /// in our internal data structures.
 776 void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
 777   for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
 778        E = LocalDeps.end(); I != E; ++I) {
 779     assert(I->first != D && "Inst occurs in data structures");
 780     assert(I->second.getInst() != D &&
 781            "Inst occurs in data structures");
 782   }
 783
 784   for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(),
 785        E = NonLocalPointerDeps.end(); I != E; ++I) {
 786     assert(I->first.getPointer() != D && "Inst occurs in NLPD map key");
 787     const NonLocalDepInfo &Val = I->second;
 788     for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end();
 789          II != E; ++II)
 790       assert(II->second.getInst() != D && "Inst occurs as NLPD value");
 791   }
 792
 793   for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(),
 794        E = NonLocalDeps.end(); I != E; ++I) {
 795     assert(I->first != D && "Inst occurs in data structures");
 796     const PerInstNLInfo &INLD = I->second;
 797     for (NonLocalDepInfo::const_iterator II = INLD.first.begin(),
 798          EE = INLD.first.end(); II  != EE; ++II)
 799       assert(II->second.getInst() != D && "Inst occurs in data structures");
 800   }
 801
 802   for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),
 803        E = ReverseLocalDeps.end(); I != E; ++I) {
 804     assert(I->first != D && "Inst occurs in data structures");
 805     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
 806          EE = I->second.end(); II != EE; ++II)
 807       assert(*II != D && "Inst occurs in data structures");
 808   }
 809
 810   for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(),
 811        E = ReverseNonLocalDeps.end();
 812        I != E; ++I) {
 813     assert(I->first != D && "Inst occurs in data structures");
 814     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
 815          EE = I->second.end(); II != EE; ++II)
 816       assert(*II != D && "Inst occurs in data structures");
 817   }
 818
 819   for (ReverseNonLocalPtrDepTy::const_iterator
 820        I = ReverseNonLocalPtrDeps.begin(),
 821        E = ReverseNonLocalPtrDeps.end(); I != E; ++I) {
 822     assert(I->first != D && "Inst occurs in rev NLPD map");
 823
 824     for (SmallPtrSet<void*, 4>::const_iterator II = I->second.begin(),
 825          E = I->second.end(); II != E; ++II)
 826       assert(*II != ValueIsLoadPair(D, false).getOpaqueValue() &&
 827              *II != ValueIsLoadPair(D, true).getOpaqueValue() &&
 828              "Inst occurs in ReverseNonLocalPtrDeps map");
 829   }
 830
 831 }