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