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