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     switch (AA->getModRefInfo(Inst, MemPtr, MemSize)) {
 217     case AliasAnalysis::NoModRef:
 218       // If the call has no effect on the queried pointer, just ignore it.
 219       continue;
 220     case AliasAnalysis::Ref:
 221       // If the call is known to never store to the pointer, and if this is a
 222       // load query, we can safely ignore it (scan past it).
 223       if (isLoad)
 224         continue;
 225       // FALL THROUGH.
 226     default:
 227       // Otherwise, there is a potential dependence.  Return a clobber.
 228       return MemDepResult::getClobber(Inst);
 229     }
 230   }
 231
 232   // No dependence found.  If this is the entry block of the function, it is a
 233   // clobber, otherwise it is non-local.
 234   if (BB != &BB->getParent()->getEntryBlock())
 235     return MemDepResult::getNonLocal();
 236   return MemDepResult::getClobber(ScanIt);
 237 }
 238
 239 /// getDependency - Return the instruction on which a memory operation
 240 /// depends.
 241 MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
 242   Instruction *ScanPos = QueryInst;
 243
 244   // Check for a cached result
 245   MemDepResult &LocalCache = LocalDeps[QueryInst];
 246
 247   // If the cached entry is non-dirty, just return it.  Note that this depends
 248   // on MemDepResult's default constructing to 'dirty'.
 249   if (!LocalCache.isDirty())
 250     return LocalCache;
 251
 252   // Otherwise, if we have a dirty entry, we know we can start the scan at that
 253   // instruction, which may save us some work.
 254   if (Instruction *Inst = LocalCache.getInst()) {
 255     ScanPos = Inst;
 256
 257     RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
 258   }
 259
 260   BasicBlock *QueryParent = QueryInst->getParent();
 261
 262   Value *MemPtr = 0;
 263   uint64_t MemSize = 0;
 264
 265   // Do the scan.
 266   if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
 267     // No dependence found.  If this is the entry block of the function, it is a
 268     // clobber, otherwise it is non-local.
 269     if (QueryParent != &QueryParent->getParent()->getEntryBlock())
 270       LocalCache = MemDepResult::getNonLocal();
 271     else
 272       LocalCache = MemDepResult::getClobber(QueryInst);
 273   } else if (StoreInst *SI = dyn_cast<StoreInst>(QueryInst)) {
 274     // If this is a volatile store, don't mess around with it.  Just return the
 275     // previous instruction as a clobber.
 276     if (SI->isVolatile())
 277       LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
 278     else {
 279       MemPtr = SI->getPointerOperand();
 280       MemSize = TD->getTypeStoreSize(SI->getOperand(0)->getType());
 281     }
 282   } else if (LoadInst *LI = dyn_cast<LoadInst>(QueryInst)) {
 283     // If this is a volatile load, don't mess around with it.  Just return the
 284     // previous instruction as a clobber.
 285     if (LI->isVolatile())
 286       LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
 287     else {
 288       MemPtr = LI->getPointerOperand();
 289       MemSize = TD->getTypeStoreSize(LI->getType());
 290     }
 291   } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
 292     LocalCache = getCallSiteDependencyFrom(CallSite::get(QueryInst), ScanPos,
 293                                            QueryParent);
 294   } else if (FreeInst *FI = dyn_cast<FreeInst>(QueryInst)) {
 295     MemPtr = FI->getPointerOperand();
 296     // FreeInsts erase the entire structure, not just a field.
 297     MemSize = ~0UL;
 298   } else {
 299     // Non-memory instruction.
 300     LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
 301   }
 302
 303   // If we need to do a pointer scan, make it happen.
 304   if (MemPtr)
 305     LocalCache = getPointerDependencyFrom(MemPtr, MemSize,
 306                                           isa<LoadInst>(QueryInst),
 307                                           ScanPos, QueryParent);
 308
 309   // Remember the result!
 310   if (Instruction *I = LocalCache.getInst())
 311     ReverseLocalDeps[I].insert(QueryInst);
 312
 313   return LocalCache;
 314 }
 315
 316 /// getNonLocalCallDependency - Perform a full dependency query for the
 317 /// specified call, returning the set of blocks that the value is
 318 /// potentially live across.  The returned set of results will include a
 319 /// "NonLocal" result for all blocks where the value is live across.
 320 ///
 321 /// This method assumes the instruction returns a "NonLocal" dependency
 322 /// within its own block.
 323 ///
 324 /// This returns a reference to an internal data structure that may be
 325 /// invalidated on the next non-local query or when an instruction is
 326 /// removed.  Clients must copy this data if they want it around longer than
 327 /// that.
 328 const MemoryDependenceAnalysis::NonLocalDepInfo &
 329 MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) {
 330   assert(getDependency(QueryCS.getInstruction()).isNonLocal() &&
 331  "getNonLocalCallDependency should only be used on calls with non-local deps!");
 332   PerInstNLInfo &CacheP = NonLocalDeps[QueryCS.getInstruction()];
 333   NonLocalDepInfo &Cache = CacheP.first;
 334
 335   /// DirtyBlocks - This is the set of blocks that need to be recomputed.  In
 336   /// the cached case, this can happen due to instructions being deleted etc. In
 337   /// the uncached case, this starts out as the set of predecessors we care
 338   /// about.
 339   SmallVector<BasicBlock*, 32> DirtyBlocks;
 340
 341   if (!Cache.empty()) {
 342     // Okay, we have a cache entry.  If we know it is not dirty, just return it
 343     // with no computation.
 344     if (!CacheP.second) {
 345       NumCacheNonLocal++;
 346       return Cache;
 347     }
 348
 349     // If we already have a partially computed set of results, scan them to
 350     // determine what is dirty, seeding our initial DirtyBlocks worklist.
 351     for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end();
 352        I != E; ++I)
 353       if (I->second.isDirty())
 354         DirtyBlocks.push_back(I->first);
 355
 356     // Sort the cache so that we can do fast binary search lookups below.
 357     std::sort(Cache.begin(), Cache.end());
 358
 359     ++NumCacheDirtyNonLocal;
 360     //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
 361     //     << Cache.size() << " cached: " << *QueryInst;
 362   } else {
 363     // Seed DirtyBlocks with each of the preds of QueryInst's block.
 364     BasicBlock *QueryBB = QueryCS.getInstruction()->getParent();
 365     for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI)
 366       DirtyBlocks.push_back(*PI);
 367     NumUncacheNonLocal++;
 368   }
 369
 370   // Visited checked first, vector in sorted order.
 371   SmallPtrSet<BasicBlock*, 64> Visited;
 372
 373   unsigned NumSortedEntries = Cache.size();
 374
 375   // Iterate while we still have blocks to update.
 376   while (!DirtyBlocks.empty()) {
 377     BasicBlock *DirtyBB = DirtyBlocks.back();
 378     DirtyBlocks.pop_back();
 379
 380     // Already processed this block?
 381     if (!Visited.insert(DirtyBB))
 382       continue;
 383
 384     // Do a binary search to see if we already have an entry for this block in
 385     // the cache set.  If so, find it.
 386     NonLocalDepInfo::iterator Entry =
 387       std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries,
 388                        std::make_pair(DirtyBB, MemDepResult()));
 389     if (Entry != Cache.begin() && (&*Entry)[-1].first == DirtyBB)
 390       --Entry;
 391
 392     MemDepResult *ExistingResult = 0;
 393     if (Entry != Cache.begin()+NumSortedEntries &&
 394         Entry->first == DirtyBB) {
 395       // If we already have an entry, and if it isn't already dirty, the block
 396       // is done.
 397       if (!Entry->second.isDirty())
 398         continue;
 399
 400       // Otherwise, remember this slot so we can update the value.
 401       ExistingResult = &Entry->second;
 402     }
 403
 404     // If the dirty entry has a pointer, start scanning from it so we don't have
 405     // to rescan the entire block.
 406     BasicBlock::iterator ScanPos = DirtyBB->end();
 407     if (ExistingResult) {
 408       if (Instruction *Inst = ExistingResult->getInst()) {
 409         ScanPos = Inst;
 410         // We're removing QueryInst's use of Inst.
 411         RemoveFromReverseMap(ReverseNonLocalDeps, Inst,
 412                              QueryCS.getInstruction());
 413       }
 414     }
 415
 416     // Find out if this block has a local dependency for QueryInst.
 417     MemDepResult Dep;
 418
 419     if (ScanPos != DirtyBB->begin()) {
 420       Dep = getCallSiteDependencyFrom(QueryCS, ScanPos, DirtyBB);
 421     } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) {
 422       // No dependence found.  If this is the entry block of the function, it is
 423       // a clobber, otherwise it is non-local.
 424       Dep = MemDepResult::getNonLocal();
 425     } else {
 426       Dep = MemDepResult::getClobber(ScanPos);
 427     }
 428
 429     // If we had a dirty entry for the block, update it.  Otherwise, just add
 430     // a new entry.
 431     if (ExistingResult)
 432       *ExistingResult = Dep;
 433     else
 434       Cache.push_back(std::make_pair(DirtyBB, Dep));
 435
 436     // If the block has a dependency (i.e. it isn't completely transparent to
 437     // the value), remember the association!
 438     if (!Dep.isNonLocal()) {
 439       // Keep the ReverseNonLocalDeps map up to date so we can efficiently
 440       // update this when we remove instructions.
 441       if (Instruction *Inst = Dep.getInst())
 442         ReverseNonLocalDeps[Inst].insert(QueryCS.getInstruction());
 443     } else {
 444
 445       // If the block *is* completely transparent to the load, we need to check
 446       // the predecessors of this block.  Add them to our worklist.
 447       for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI)
 448         DirtyBlocks.push_back(*PI);
 449     }
 450   }
 451
 452   return Cache;
 453 }
 454
 455 /// getNonLocalPointerDependency - Perform a full dependency query for an
 456 /// access to the specified (non-volatile) memory location, returning the
 457 /// set of instructions that either define or clobber the value.
 458 ///
 459 /// This method assumes the pointer has a "NonLocal" dependency within its
 460 /// own block.
 461 ///
 462 void MemoryDependenceAnalysis::
 463 getNonLocalPointerDependency(Value *Pointer, bool isLoad, BasicBlock *FromBB,
 464                              SmallVectorImpl<NonLocalDepEntry> &Result) {
 465   assert(isa<PointerType>(Pointer->getType()) &&
 466          "Can't get pointer deps of a non-pointer!");
 467   Result.clear();
 468
 469   // We know that the pointer value is live into FromBB find the def/clobbers
 470   // from presecessors.
 471   const Type *EltTy = cast<PointerType>(Pointer->getType())->getElementType();
 472   uint64_t PointeeSize = TD->getTypeStoreSize(EltTy);
 473
 474   // While we have blocks to analyze, get their values.
 475   SmallPtrSet<BasicBlock*, 64> Visited;
 476   getNonLocalPointerDepFromBB(Pointer, PointeeSize, isLoad, FromBB,
 477                               Result, Visited);
 478 }
 479
 480 /// GetNonLocalInfoForBlock - Compute the memdep value for BB with
 481 /// Pointer/PointeeSize using either cached information in Cache or by doing a
 482 /// lookup (which may use dirty cache info if available).  If we do a lookup,
 483 /// add the result to the cache.
 484 MemDepResult MemoryDependenceAnalysis::
 485 GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize,
 486                         bool isLoad, BasicBlock *BB,
 487                         NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
 488
 489   // Do a binary search to see if we already have an entry for this block in
 490   // the cache set.  If so, find it.
 491   NonLocalDepInfo::iterator Entry =
 492     std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
 493                      std::make_pair(BB, MemDepResult()));
 494   if (Entry != Cache->begin() && (&*Entry)[-1].first == BB)
 495     --Entry;
 496
 497   MemDepResult *ExistingResult = 0;
 498   if (Entry != Cache->begin()+NumSortedEntries && Entry->first == BB)
 499     ExistingResult = &Entry->second;
 500
 501   // If we have a cached entry, and it is non-dirty, use it as the value for
 502   // this dependency.
 503   if (ExistingResult && !ExistingResult->isDirty()) {
 504     ++NumCacheNonLocalPtr;
 505     return *ExistingResult;
 506   }
 507
 508   // Otherwise, we have to scan for the value.  If we have a dirty cache
 509   // entry, start scanning from its position, otherwise we scan from the end
 510   // of the block.
 511   BasicBlock::iterator ScanPos = BB->end();
 512   if (ExistingResult && ExistingResult->getInst()) {
 513     assert(ExistingResult->getInst()->getParent() == BB &&
 514            "Instruction invalidated?");
 515     ++NumCacheDirtyNonLocalPtr;
 516     ScanPos = ExistingResult->getInst();
 517
 518     // Eliminating the dirty entry from 'Cache', so update the reverse info.
 519     ValueIsLoadPair CacheKey(Pointer, isLoad);
 520     RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos,
 521                          CacheKey.getOpaqueValue());
 522   } else {
 523     ++NumUncacheNonLocalPtr;
 524   }
 525
 526   // Scan the block for the dependency.
 527   MemDepResult Dep = getPointerDependencyFrom(Pointer, PointeeSize, isLoad,
 528                                               ScanPos, BB);
 529
 530   // If we had a dirty entry for the block, update it.  Otherwise, just add
 531   // a new entry.
 532   if (ExistingResult)
 533     *ExistingResult = Dep;
 534   else
 535     Cache->push_back(std::make_pair(BB, Dep));
 536
 537   // If the block has a dependency (i.e. it isn't completely transparent to
 538   // the value), remember the reverse association because we just added it
 539   // to Cache!
 540   if (Dep.isNonLocal())
 541     return Dep;
 542
 543   // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
 544   // update MemDep when we remove instructions.
 545   Instruction *Inst = Dep.getInst();
 546   assert(Inst && "Didn't depend on anything?");
 547   ValueIsLoadPair CacheKey(Pointer, isLoad);
 548   ReverseNonLocalPtrDeps[Inst].insert(CacheKey.getOpaqueValue());
 549   return Dep;
 550 }
 551
 552
 553 /// getNonLocalPointerDepFromBB -
 554 void MemoryDependenceAnalysis::
 555 getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize,
 556                             bool isLoad, BasicBlock *StartBB,
 557                             SmallVectorImpl<NonLocalDepEntry> &Result,
 558                             SmallPtrSet<BasicBlock*, 64> &Visited) {
 559   // Look up the cached info for Pointer.
 560   ValueIsLoadPair CacheKey(Pointer, isLoad);
 561
 562   std::pair<BasicBlock*, NonLocalDepInfo> &CacheInfo =
 563     NonLocalPointerDeps[CacheKey];
 564   NonLocalDepInfo *Cache = &CacheInfo.second;
 565
 566   // If we have valid cached information for exactly the block we are
 567   // investigating, just return it with no recomputation.
 568   if (CacheInfo.first == StartBB) {
 569     for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
 570          I != E; ++I)
 571       if (!I->second.isNonLocal())
 572         Result.push_back(*I);
 573     ++NumCacheCompleteNonLocalPtr;
 574     return;
 575   }
 576
 577   // Otherwise, either this is a new block, a block with an invalid cache
 578   // pointer or one that we're about to invalidate by putting more info into it
 579   // than its valid cache info.  If empty, the result will be valid cache info,
 580   // otherwise it isn't.
 581   CacheInfo.first = Cache->empty() ? StartBB : 0;
 582
 583   SmallVector<BasicBlock*, 32> Worklist;
 584   Worklist.push_back(StartBB);
 585
 586   // Keep track of the entries that we know are sorted.  Previously cached
 587   // entries will all be sorted.  The entries we add we only sort on demand (we
 588   // don't insert every element into its sorted position).  We know that we
 589   // won't get any reuse from currently inserted values, because we don't
 590   // revisit blocks after we insert info for them.
 591   unsigned NumSortedEntries = Cache->size();
 592
 593   // SkipFirstBlock - If this is the very first block that we're processing, we
 594   // don't want to scan or think about its body, because the client was supposed
 595   // to do a local dependence query.  Instead, just start processing it by
 596   // adding its predecessors to the worklist and iterating.
 597   bool SkipFirstBlock = Visited.empty();
 598
 599   while (!Worklist.empty()) {
 600     BasicBlock *BB = Worklist.pop_back_val();
 601
 602     // Skip the first block if we have it.
 603     if (SkipFirstBlock) {
 604       SkipFirstBlock = false;
 605     } else {
 606       // Analyze the dependency of *Pointer in FromBB.  See if we already have
 607       // been here.
 608       if (!Visited.insert(BB))
 609         continue;
 610
 611       // Get the dependency info for Pointer in BB.  If we have cached
 612       // information, we will use it, otherwise we compute it.
 613       MemDepResult Dep = GetNonLocalInfoForBlock(Pointer, PointeeSize, isLoad,
 614                                                  BB, Cache, NumSortedEntries);
 615
 616       // If we got a Def or Clobber, add this to the list of results.
 617       if (!Dep.isNonLocal()) {
 618         Result.push_back(NonLocalDepEntry(BB, Dep));
 619         continue;
 620       }
 621     }
 622
 623     // Otherwise, we have to process all the predecessors of this block to scan
 624     // them as well.
 625     for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
 626       // TODO: PHI TRANSLATE.
 627       Worklist.push_back(*PI);
 628     }
 629   }
 630
 631   // Okay, we're done now.  If we added new values to the cache, re-sort it.
 632   switch (Cache->size()-NumSortedEntries) {
 633   case 0:
 634     // done, no new entries.
 635     break;
 636   case 2: {
 637     // Two new entries, insert the last one into place.
 638     NonLocalDepEntry Val = Cache->back();
 639     Cache->pop_back();
 640     NonLocalDepInfo::iterator Entry =
 641     std::upper_bound(Cache->begin(), Cache->end()-1, Val);
 642     Cache->insert(Entry, Val);
 643     // FALL THROUGH.
 644   }
 645   case 1: {
 646     // One new entry, Just insert the new value at the appropriate position.
 647     NonLocalDepEntry Val = Cache->back();
 648     Cache->pop_back();
 649     NonLocalDepInfo::iterator Entry =
 650       std::upper_bound(Cache->begin(), Cache->end(), Val);
 651     Cache->insert(Entry, Val);
 652     break;
 653   }
 654   default:
 655     // Added many values, do a full scale sort.
 656     std::sort(Cache->begin(), Cache->end());
 657   }
 658 }
 659
 660 /// RemoveCachedNonLocalPointerDependencies - If P exists in
 661 /// CachedNonLocalPointerInfo, remove it.
 662 void MemoryDependenceAnalysis::
 663 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) {
 664   CachedNonLocalPointerInfo::iterator It =
 665     NonLocalPointerDeps.find(P);
 666   if (It == NonLocalPointerDeps.end()) return;
 667
 668   // Remove all of the entries in the BB->val map.  This involves removing
 669   // instructions from the reverse map.
 670   NonLocalDepInfo &PInfo = It->second.second;
 671
 672   for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
 673     Instruction *Target = PInfo[i].second.getInst();
 674     if (Target == 0) continue;  // Ignore non-local dep results.
 675     assert(Target->getParent() == PInfo[i].first && Target != P.getPointer());
 676
 677     // Eliminating the dirty entry from 'Cache', so update the reverse info.
 678     RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P.getOpaqueValue());
 679   }
 680
 681   // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
 682   NonLocalPointerDeps.erase(It);
 683 }
 684
 685
 686 /// removeInstruction - Remove an instruction from the dependence analysis,
 687 /// updating the dependence of instructions that previously depended on it.
 688 /// This method attempts to keep the cache coherent using the reverse map.
 689 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
 690   // Walk through the Non-local dependencies, removing this one as the value
 691   // for any cached queries.
 692   NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
 693   if (NLDI != NonLocalDeps.end()) {
 694     NonLocalDepInfo &BlockMap = NLDI->second.first;
 695     for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end();
 696          DI != DE; ++DI)
 697       if (Instruction *Inst = DI->second.getInst())
 698         RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
 699     NonLocalDeps.erase(NLDI);
 700   }
 701
 702   // If we have a cached local dependence query for this instruction, remove it.
 703   //
 704   LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
 705   if (LocalDepEntry != LocalDeps.end()) {
 706     // Remove us from DepInst's reverse set now that the local dep info is gone.
 707     if (Instruction *Inst = LocalDepEntry->second.getInst())
 708       RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
 709
 710     // Remove this local dependency info.
 711     LocalDeps.erase(LocalDepEntry);
 712   }
 713
 714   // If we have any cached pointer dependencies on this instruction, remove
 715   // them.  If the instruction has non-pointer type, then it can't be a pointer
 716   // base.
 717
 718   // Remove it from both the load info and the store info.  The instruction
 719   // can't be in either of these maps if it is non-pointer.
 720   if (isa<PointerType>(RemInst->getType())) {
 721     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
 722     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
 723   }
 724
 725   // Loop over all of the things that depend on the instruction we're removing.
 726   //
 727   SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd;
 728
 729   // If we find RemInst as a clobber or Def in any of the maps for other values,
 730   // we need to replace its entry with a dirty version of the instruction after
 731   // it.  If RemInst is a terminator, we use a null dirty value.
 732   //
 733   // Using a dirty version of the instruction after RemInst saves having to scan
 734   // the entire block to get to this point.
 735   MemDepResult NewDirtyVal;
 736   if (!RemInst->isTerminator())
 737     NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst));
 738
 739   ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
 740   if (ReverseDepIt != ReverseLocalDeps.end()) {
 741     SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
 742     // RemInst can't be the terminator if it has local stuff depending on it.
 743     assert(!ReverseDeps.empty() && !isa<TerminatorInst>(RemInst) &&
 744            "Nothing can locally depend on a terminator");
 745
 746     for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
 747          E = ReverseDeps.end(); I != E; ++I) {
 748       Instruction *InstDependingOnRemInst = *I;
 749       assert(InstDependingOnRemInst != RemInst &&
 750              "Already removed our local dep info");
 751
 752       LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
 753
 754       // Make sure to remember that new things depend on NewDepInst.
 755       assert(NewDirtyVal.getInst() && "There is no way something else can have "
 756              "a local dep on this if it is a terminator!");
 757       ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(),
 758                                                 InstDependingOnRemInst));
 759     }
 760
 761     ReverseLocalDeps.erase(ReverseDepIt);
 762
 763     // Add new reverse deps after scanning the set, to avoid invalidating the
 764     // 'ReverseDeps' reference.
 765     while (!ReverseDepsToAdd.empty()) {
 766       ReverseLocalDeps[ReverseDepsToAdd.back().first]
 767         .insert(ReverseDepsToAdd.back().second);
 768       ReverseDepsToAdd.pop_back();
 769     }
 770   }
 771
 772   ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
 773   if (ReverseDepIt != ReverseNonLocalDeps.end()) {
 774     SmallPtrSet<Instruction*, 4> &Set = ReverseDepIt->second;
 775     for (SmallPtrSet<Instruction*, 4>::iterator I = Set.begin(), E = Set.end();
 776          I != E; ++I) {
 777       assert(*I != RemInst && "Already removed NonLocalDep info for RemInst");
 778
 779       PerInstNLInfo &INLD = NonLocalDeps[*I];
 780       // The information is now dirty!
 781       INLD.second = true;
 782
 783       for (NonLocalDepInfo::iterator DI = INLD.first.begin(),
 784            DE = INLD.first.end(); DI != DE; ++DI) {
 785         if (DI->second.getInst() != RemInst) continue;
 786
 787         // Convert to a dirty entry for the subsequent instruction.
 788         DI->second = NewDirtyVal;
 789
 790         if (Instruction *NextI = NewDirtyVal.getInst())
 791           ReverseDepsToAdd.push_back(std::make_pair(NextI, *I));
 792       }
 793     }
 794
 795     ReverseNonLocalDeps.erase(ReverseDepIt);
 796
 797     // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
 798     while (!ReverseDepsToAdd.empty()) {
 799       ReverseNonLocalDeps[ReverseDepsToAdd.back().first]
 800         .insert(ReverseDepsToAdd.back().second);
 801       ReverseDepsToAdd.pop_back();
 802     }
 803   }
 804
 805   // If the instruction is in ReverseNonLocalPtrDeps then it appears as a
 806   // value in the NonLocalPointerDeps info.
 807   ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
 808     ReverseNonLocalPtrDeps.find(RemInst);
 809   if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
 810     SmallPtrSet<void*, 4> &Set = ReversePtrDepIt->second;
 811     SmallVector<std::pair<Instruction*, ValueIsLoadPair>,8> ReversePtrDepsToAdd;
 812
 813     for (SmallPtrSet<void*, 4>::iterator I = Set.begin(), E = Set.end();
 814          I != E; ++I) {
 815       ValueIsLoadPair P;
 816       P.setFromOpaqueValue(*I);
 817       assert(P.getPointer() != RemInst &&
 818              "Already removed NonLocalPointerDeps info for RemInst");
 819
 820       NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].second;
 821
 822       // The cache is not valid for any specific block anymore.
 823       NonLocalPointerDeps[P].first = 0;
 824
 825       // Update any entries for RemInst to use the instruction after it.
 826       for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();
 827            DI != DE; ++DI) {
 828         if (DI->second.getInst() != RemInst) continue;
 829
 830         // Convert to a dirty entry for the subsequent instruction.
 831         DI->second = NewDirtyVal;
 832
 833         if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
 834           ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
 835       }
 836     }
 837
 838     ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
 839
 840     while (!ReversePtrDepsToAdd.empty()) {
 841       ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first]
 842         .insert(ReversePtrDepsToAdd.back().second.getOpaqueValue());
 843       ReversePtrDepsToAdd.pop_back();
 844     }
 845   }
 846
 847
 848   assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
 849   AA->deleteValue(RemInst);
 850   DEBUG(verifyRemoved(RemInst));
 851 }
 852
 853 /// verifyRemoved - Verify that the specified instruction does not occur
 854 /// in our internal data structures.
 855 void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
 856   for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
 857        E = LocalDeps.end(); I != E; ++I) {
 858     assert(I->first != D && "Inst occurs in data structures");
 859     assert(I->second.getInst() != D &&
 860            "Inst occurs in data structures");
 861   }
 862
 863   for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(),
 864        E = NonLocalPointerDeps.end(); I != E; ++I) {
 865     assert(I->first.getPointer() != D && "Inst occurs in NLPD map key");
 866     const NonLocalDepInfo &Val = I->second.second;
 867     for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end();
 868          II != E; ++II)
 869       assert(II->second.getInst() != D && "Inst occurs as NLPD value");
 870   }
 871
 872   for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(),
 873        E = NonLocalDeps.end(); I != E; ++I) {
 874     assert(I->first != D && "Inst occurs in data structures");
 875     const PerInstNLInfo &INLD = I->second;
 876     for (NonLocalDepInfo::const_iterator II = INLD.first.begin(),
 877          EE = INLD.first.end(); II  != EE; ++II)
 878       assert(II->second.getInst() != D && "Inst occurs in data structures");
 879   }
 880
 881   for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),
 882        E = ReverseLocalDeps.end(); I != E; ++I) {
 883     assert(I->first != D && "Inst occurs in data structures");
 884     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
 885          EE = I->second.end(); II != EE; ++II)
 886       assert(*II != D && "Inst occurs in data structures");
 887   }
 888
 889   for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(),
 890        E = ReverseNonLocalDeps.end();
 891        I != E; ++I) {
 892     assert(I->first != D && "Inst occurs in data structures");
 893     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
 894          EE = I->second.end(); II != EE; ++II)
 895       assert(*II != D && "Inst occurs in data structures");
 896   }
 897
 898   for (ReverseNonLocalPtrDepTy::const_iterator
 899        I = ReverseNonLocalPtrDeps.begin(),
 900        E = ReverseNonLocalPtrDeps.end(); I != E; ++I) {
 901     assert(I->first != D && "Inst occurs in rev NLPD map");
 902
 903     for (SmallPtrSet<void*, 4>::const_iterator II = I->second.begin(),
 904          E = I->second.end(); II != E; ++II)
 905       assert(*II != ValueIsLoadPair(D, false).getOpaqueValue() &&
 906              *II != ValueIsLoadPair(D, true).getOpaqueValue() &&
 907              "Inst occurs in ReverseNonLocalPtrDeps map");
 908   }
 909
 910 }