LLVM API Documentation

MemoryDependenceAnalysis.cpp
Go to the documentation of this file.
00001 //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation -------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements an analysis that determines, for a given memory
00011 // operation, what preceding memory operations it depends on.  It builds on
00012 // alias analysis information, and tries to provide a lazy, caching interface to
00013 // a common kind of alias information query.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #define DEBUG_TYPE "memdep"
00018 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
00019 #include "llvm/ADT/STLExtras.h"
00020 #include "llvm/ADT/Statistic.h"
00021 #include "llvm/Analysis/AliasAnalysis.h"
00022 #include "llvm/Analysis/InstructionSimplify.h"
00023 #include "llvm/Analysis/MemoryBuiltins.h"
00024 #include "llvm/Analysis/PHITransAddr.h"
00025 #include "llvm/Analysis/ValueTracking.h"
00026 #include "llvm/IR/DataLayout.h"
00027 #include "llvm/IR/Dominators.h"
00028 #include "llvm/IR/Function.h"
00029 #include "llvm/IR/Instructions.h"
00030 #include "llvm/IR/IntrinsicInst.h"
00031 #include "llvm/IR/LLVMContext.h"
00032 #include "llvm/IR/PredIteratorCache.h"
00033 #include "llvm/Support/Debug.h"
00034 using namespace llvm;
00035 
00036 STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");
00037 STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");
00038 STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");
00039 
00040 STATISTIC(NumCacheNonLocalPtr,
00041           "Number of fully cached non-local ptr responses");
00042 STATISTIC(NumCacheDirtyNonLocalPtr,
00043           "Number of cached, but dirty, non-local ptr responses");
00044 STATISTIC(NumUncacheNonLocalPtr,
00045           "Number of uncached non-local ptr responses");
00046 STATISTIC(NumCacheCompleteNonLocalPtr,
00047           "Number of block queries that were completely cached");
00048 
00049 // Limit for the number of instructions to scan in a block.
00050 static const int BlockScanLimit = 100;
00051 
00052 char MemoryDependenceAnalysis::ID = 0;
00053 
00054 // Register this pass...
00055 INITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep",
00056                 "Memory Dependence Analysis", false, true)
00057 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
00058 INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep",
00059                       "Memory Dependence Analysis", false, true)
00060 
00061 MemoryDependenceAnalysis::MemoryDependenceAnalysis()
00062     : FunctionPass(ID), PredCache() {
00063   initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry());
00064 }
00065 MemoryDependenceAnalysis::~MemoryDependenceAnalysis() {
00066 }
00067 
00068 /// Clean up memory in between runs
00069 void MemoryDependenceAnalysis::releaseMemory() {
00070   LocalDeps.clear();
00071   NonLocalDeps.clear();
00072   NonLocalPointerDeps.clear();
00073   ReverseLocalDeps.clear();
00074   ReverseNonLocalDeps.clear();
00075   ReverseNonLocalPtrDeps.clear();
00076   PredCache->clear();
00077 }
00078 
00079 
00080 
00081 /// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
00082 ///
00083 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
00084   AU.setPreservesAll();
00085   AU.addRequiredTransitive<AliasAnalysis>();
00086 }
00087 
00088 bool MemoryDependenceAnalysis::runOnFunction(Function &) {
00089   AA = &getAnalysis<AliasAnalysis>();
00090   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
00091   DL = DLP ? &DLP->getDataLayout() : nullptr;
00092   DominatorTreeWrapperPass *DTWP =
00093       getAnalysisIfAvailable<DominatorTreeWrapperPass>();
00094   DT = DTWP ? &DTWP->getDomTree() : nullptr;
00095   if (!PredCache)
00096     PredCache.reset(new PredIteratorCache());
00097   return false;
00098 }
00099 
00100 /// RemoveFromReverseMap - This is a helper function that removes Val from
00101 /// 'Inst's set in ReverseMap.  If the set becomes empty, remove Inst's entry.
00102 template <typename KeyTy>
00103 static void RemoveFromReverseMap(DenseMap<Instruction*,
00104                                  SmallPtrSet<KeyTy, 4> > &ReverseMap,
00105                                  Instruction *Inst, KeyTy Val) {
00106   typename DenseMap<Instruction*, SmallPtrSet<KeyTy, 4> >::iterator
00107   InstIt = ReverseMap.find(Inst);
00108   assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
00109   bool Found = InstIt->second.erase(Val);
00110   assert(Found && "Invalid reverse map!"); (void)Found;
00111   if (InstIt->second.empty())
00112     ReverseMap.erase(InstIt);
00113 }
00114 
00115 /// GetLocation - If the given instruction references a specific memory
00116 /// location, fill in Loc with the details, otherwise set Loc.Ptr to null.
00117 /// Return a ModRefInfo value describing the general behavior of the
00118 /// instruction.
00119 static
00120 AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst,
00121                                         AliasAnalysis::Location &Loc,
00122                                         AliasAnalysis *AA) {
00123   if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
00124     if (LI->isUnordered()) {
00125       Loc = AA->getLocation(LI);
00126       return AliasAnalysis::Ref;
00127     }
00128     if (LI->getOrdering() == Monotonic) {
00129       Loc = AA->getLocation(LI);
00130       return AliasAnalysis::ModRef;
00131     }
00132     Loc = AliasAnalysis::Location();
00133     return AliasAnalysis::ModRef;
00134   }
00135 
00136   if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
00137     if (SI->isUnordered()) {
00138       Loc = AA->getLocation(SI);
00139       return AliasAnalysis::Mod;
00140     }
00141     if (SI->getOrdering() == Monotonic) {
00142       Loc = AA->getLocation(SI);
00143       return AliasAnalysis::ModRef;
00144     }
00145     Loc = AliasAnalysis::Location();
00146     return AliasAnalysis::ModRef;
00147   }
00148 
00149   if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
00150     Loc = AA->getLocation(V);
00151     return AliasAnalysis::ModRef;
00152   }
00153 
00154   if (const CallInst *CI = isFreeCall(Inst, AA->getTargetLibraryInfo())) {
00155     // calls to free() deallocate the entire structure
00156     Loc = AliasAnalysis::Location(CI->getArgOperand(0));
00157     return AliasAnalysis::Mod;
00158   }
00159 
00160   if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
00161     switch (II->getIntrinsicID()) {
00162     case Intrinsic::lifetime_start:
00163     case Intrinsic::lifetime_end:
00164     case Intrinsic::invariant_start:
00165       Loc = AliasAnalysis::Location(II->getArgOperand(1),
00166                                     cast<ConstantInt>(II->getArgOperand(0))
00167                                       ->getZExtValue(),
00168                                     II->getMetadata(LLVMContext::MD_tbaa));
00169       // These intrinsics don't really modify the memory, but returning Mod
00170       // will allow them to be handled conservatively.
00171       return AliasAnalysis::Mod;
00172     case Intrinsic::invariant_end:
00173       Loc = AliasAnalysis::Location(II->getArgOperand(2),
00174                                     cast<ConstantInt>(II->getArgOperand(1))
00175                                       ->getZExtValue(),
00176                                     II->getMetadata(LLVMContext::MD_tbaa));
00177       // These intrinsics don't really modify the memory, but returning Mod
00178       // will allow them to be handled conservatively.
00179       return AliasAnalysis::Mod;
00180     default:
00181       break;
00182     }
00183 
00184   // Otherwise, just do the coarse-grained thing that always works.
00185   if (Inst->mayWriteToMemory())
00186     return AliasAnalysis::ModRef;
00187   if (Inst->mayReadFromMemory())
00188     return AliasAnalysis::Ref;
00189   return AliasAnalysis::NoModRef;
00190 }
00191 
00192 /// getCallSiteDependencyFrom - Private helper for finding the local
00193 /// dependencies of a call site.
00194 MemDepResult MemoryDependenceAnalysis::
00195 getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
00196                           BasicBlock::iterator ScanIt, BasicBlock *BB) {
00197   unsigned Limit = BlockScanLimit;
00198 
00199   // Walk backwards through the block, looking for dependencies
00200   while (ScanIt != BB->begin()) {
00201     // Limit the amount of scanning we do so we don't end up with quadratic
00202     // running time on extreme testcases.
00203     --Limit;
00204     if (!Limit)
00205       return MemDepResult::getUnknown();
00206 
00207     Instruction *Inst = --ScanIt;
00208 
00209     // If this inst is a memory op, get the pointer it accessed
00210     AliasAnalysis::Location Loc;
00211     AliasAnalysis::ModRefResult MR = GetLocation(Inst, Loc, AA);
00212     if (Loc.Ptr) {
00213       // A simple instruction.
00214       if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef)
00215         return MemDepResult::getClobber(Inst);
00216       continue;
00217     }
00218 
00219     if (CallSite InstCS = cast<Value>(Inst)) {
00220       // Debug intrinsics don't cause dependences.
00221       if (isa<DbgInfoIntrinsic>(Inst)) continue;
00222       // If these two calls do not interfere, look past it.
00223       switch (AA->getModRefInfo(CS, InstCS)) {
00224       case AliasAnalysis::NoModRef:
00225         // If the two calls are the same, return InstCS as a Def, so that
00226         // CS can be found redundant and eliminated.
00227         if (isReadOnlyCall && !(MR & AliasAnalysis::Mod) &&
00228             CS.getInstruction()->isIdenticalToWhenDefined(Inst))
00229           return MemDepResult::getDef(Inst);
00230 
00231         // Otherwise if the two calls don't interact (e.g. InstCS is readnone)
00232         // keep scanning.
00233         continue;
00234       default:
00235         return MemDepResult::getClobber(Inst);
00236       }
00237     }
00238 
00239     // If we could not obtain a pointer for the instruction and the instruction
00240     // touches memory then assume that this is a dependency.
00241     if (MR != AliasAnalysis::NoModRef)
00242       return MemDepResult::getClobber(Inst);
00243   }
00244 
00245   // No dependence found.  If this is the entry block of the function, it is
00246   // unknown, otherwise it is non-local.
00247   if (BB != &BB->getParent()->getEntryBlock())
00248     return MemDepResult::getNonLocal();
00249   return MemDepResult::getNonFuncLocal();
00250 }
00251 
00252 /// isLoadLoadClobberIfExtendedToFullWidth - Return true if LI is a load that
00253 /// would fully overlap MemLoc if done as a wider legal integer load.
00254 ///
00255 /// MemLocBase, MemLocOffset are lazily computed here the first time the
00256 /// base/offs of memloc is needed.
00257 static bool
00258 isLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc,
00259                                        const Value *&MemLocBase,
00260                                        int64_t &MemLocOffs,
00261                                        const LoadInst *LI,
00262                                        const DataLayout *DL) {
00263   // If we have no target data, we can't do this.
00264   if (!DL) return false;
00265 
00266   // If we haven't already computed the base/offset of MemLoc, do so now.
00267   if (!MemLocBase)
00268     MemLocBase = GetPointerBaseWithConstantOffset(MemLoc.Ptr, MemLocOffs, DL);
00269 
00270   unsigned Size = MemoryDependenceAnalysis::
00271     getLoadLoadClobberFullWidthSize(MemLocBase, MemLocOffs, MemLoc.Size,
00272                                     LI, *DL);
00273   return Size != 0;
00274 }
00275 
00276 /// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that
00277 /// looks at a memory location for a load (specified by MemLocBase, Offs,
00278 /// and Size) and compares it against a load.  If the specified load could
00279 /// be safely widened to a larger integer load that is 1) still efficient,
00280 /// 2) safe for the target, and 3) would provide the specified memory
00281 /// location value, then this function returns the size in bytes of the
00282 /// load width to use.  If not, this returns zero.
00283 unsigned MemoryDependenceAnalysis::
00284 getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs,
00285                                 unsigned MemLocSize, const LoadInst *LI,
00286                                 const DataLayout &DL) {
00287   // We can only extend simple integer loads.
00288   if (!isa<IntegerType>(LI->getType()) || !LI->isSimple()) return 0;
00289 
00290   // Load widening is hostile to ThreadSanitizer: it may cause false positives
00291   // or make the reports more cryptic (access sizes are wrong).
00292   if (LI->getParent()->getParent()->getAttributes().
00293       hasAttribute(AttributeSet::FunctionIndex, Attribute::SanitizeThread))
00294     return 0;
00295 
00296   // Get the base of this load.
00297   int64_t LIOffs = 0;
00298   const Value *LIBase =
00299     GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, &DL);
00300 
00301   // If the two pointers are not based on the same pointer, we can't tell that
00302   // they are related.
00303   if (LIBase != MemLocBase) return 0;
00304 
00305   // Okay, the two values are based on the same pointer, but returned as
00306   // no-alias.  This happens when we have things like two byte loads at "P+1"
00307   // and "P+3".  Check to see if increasing the size of the "LI" load up to its
00308   // alignment (or the largest native integer type) will allow us to load all
00309   // the bits required by MemLoc.
00310 
00311   // If MemLoc is before LI, then no widening of LI will help us out.
00312   if (MemLocOffs < LIOffs) return 0;
00313 
00314   // Get the alignment of the load in bytes.  We assume that it is safe to load
00315   // any legal integer up to this size without a problem.  For example, if we're
00316   // looking at an i8 load on x86-32 that is known 1024 byte aligned, we can
00317   // widen it up to an i32 load.  If it is known 2-byte aligned, we can widen it
00318   // to i16.
00319   unsigned LoadAlign = LI->getAlignment();
00320 
00321   int64_t MemLocEnd = MemLocOffs+MemLocSize;
00322 
00323   // If no amount of rounding up will let MemLoc fit into LI, then bail out.
00324   if (LIOffs+LoadAlign < MemLocEnd) return 0;
00325 
00326   // This is the size of the load to try.  Start with the next larger power of
00327   // two.
00328   unsigned NewLoadByteSize = LI->getType()->getPrimitiveSizeInBits()/8U;
00329   NewLoadByteSize = NextPowerOf2(NewLoadByteSize);
00330 
00331   while (1) {
00332     // If this load size is bigger than our known alignment or would not fit
00333     // into a native integer register, then we fail.
00334     if (NewLoadByteSize > LoadAlign ||
00335         !DL.fitsInLegalInteger(NewLoadByteSize*8))
00336       return 0;
00337 
00338     if (LIOffs+NewLoadByteSize > MemLocEnd &&
00339         LI->getParent()->getParent()->getAttributes().
00340           hasAttribute(AttributeSet::FunctionIndex, Attribute::SanitizeAddress))
00341       // We will be reading past the location accessed by the original program.
00342       // While this is safe in a regular build, Address Safety analysis tools
00343       // may start reporting false warnings. So, don't do widening.
00344       return 0;
00345 
00346     // If a load of this width would include all of MemLoc, then we succeed.
00347     if (LIOffs+NewLoadByteSize >= MemLocEnd)
00348       return NewLoadByteSize;
00349 
00350     NewLoadByteSize <<= 1;
00351   }
00352 }
00353 
00354 /// getPointerDependencyFrom - Return the instruction on which a memory
00355 /// location depends.  If isLoad is true, this routine ignores may-aliases with
00356 /// read-only operations.  If isLoad is false, this routine ignores may-aliases
00357 /// with reads from read-only locations.  If possible, pass the query
00358 /// instruction as well; this function may take advantage of the metadata
00359 /// annotated to the query instruction to refine the result.
00360 MemDepResult MemoryDependenceAnalysis::
00361 getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad,
00362                          BasicBlock::iterator ScanIt, BasicBlock *BB,
00363                          Instruction *QueryInst) {
00364 
00365   const Value *MemLocBase = nullptr;
00366   int64_t MemLocOffset = 0;
00367   unsigned Limit = BlockScanLimit;
00368   bool isInvariantLoad = false;
00369   if (isLoad && QueryInst) {
00370     LoadInst *LI = dyn_cast<LoadInst>(QueryInst);
00371     if (LI && LI->getMetadata(LLVMContext::MD_invariant_load) != nullptr)
00372       isInvariantLoad = true;
00373   }
00374 
00375   // Walk backwards through the basic block, looking for dependencies.
00376   while (ScanIt != BB->begin()) {
00377     Instruction *Inst = --ScanIt;
00378 
00379     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
00380       // Debug intrinsics don't (and can't) cause dependencies.
00381       if (isa<DbgInfoIntrinsic>(II)) continue;
00382 
00383     // Limit the amount of scanning we do so we don't end up with quadratic
00384     // running time on extreme testcases.
00385     --Limit;
00386     if (!Limit)
00387       return MemDepResult::getUnknown();
00388 
00389     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
00390       // If we reach a lifetime begin or end marker, then the query ends here
00391       // because the value is undefined.
00392       if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
00393         // FIXME: This only considers queries directly on the invariant-tagged
00394         // pointer, not on query pointers that are indexed off of them.  It'd
00395         // be nice to handle that at some point (the right approach is to use
00396         // GetPointerBaseWithConstantOffset).
00397         if (AA->isMustAlias(AliasAnalysis::Location(II->getArgOperand(1)),
00398                             MemLoc))
00399           return MemDepResult::getDef(II);
00400         continue;
00401       }
00402     }
00403 
00404     // Values depend on loads if the pointers are must aliased.  This means that
00405     // a load depends on another must aliased load from the same value.
00406     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
00407       // Atomic loads have complications involved.
00408       // FIXME: This is overly conservative.
00409       if (!LI->isUnordered())
00410         return MemDepResult::getClobber(LI);
00411 
00412       AliasAnalysis::Location LoadLoc = AA->getLocation(LI);
00413 
00414       // If we found a pointer, check if it could be the same as our pointer.
00415       AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc);
00416 
00417       if (isLoad) {
00418         if (R == AliasAnalysis::NoAlias) {
00419           // If this is an over-aligned integer load (for example,
00420           // "load i8* %P, align 4") see if it would obviously overlap with the
00421           // queried location if widened to a larger load (e.g. if the queried
00422           // location is 1 byte at P+1).  If so, return it as a load/load
00423           // clobber result, allowing the client to decide to widen the load if
00424           // it wants to.
00425           if (IntegerType *ITy = dyn_cast<IntegerType>(LI->getType()))
00426             if (LI->getAlignment()*8 > ITy->getPrimitiveSizeInBits() &&
00427                 isLoadLoadClobberIfExtendedToFullWidth(MemLoc, MemLocBase,
00428                                                        MemLocOffset, LI, DL))
00429               return MemDepResult::getClobber(Inst);
00430 
00431           continue;
00432         }
00433 
00434         // Must aliased loads are defs of each other.
00435         if (R == AliasAnalysis::MustAlias)
00436           return MemDepResult::getDef(Inst);
00437 
00438 #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads
00439       // in terms of clobbering loads, but since it does this by looking
00440       // at the clobbering load directly, it doesn't know about any
00441       // phi translation that may have happened along the way.
00442 
00443         // If we have a partial alias, then return this as a clobber for the
00444         // client to handle.
00445         if (R == AliasAnalysis::PartialAlias)
00446           return MemDepResult::getClobber(Inst);
00447 #endif
00448 
00449         // Random may-alias loads don't depend on each other without a
00450         // dependence.
00451         continue;
00452       }
00453 
00454       // Stores don't depend on other no-aliased accesses.
00455       if (R == AliasAnalysis::NoAlias)
00456         continue;
00457 
00458       // Stores don't alias loads from read-only memory.
00459       if (AA->pointsToConstantMemory(LoadLoc))
00460         continue;
00461 
00462       // Stores depend on may/must aliased loads.
00463       return MemDepResult::getDef(Inst);
00464     }
00465 
00466     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
00467       // Atomic stores have complications involved.
00468       // FIXME: This is overly conservative.
00469       if (!SI->isUnordered())
00470         return MemDepResult::getClobber(SI);
00471 
00472       // If alias analysis can tell that this store is guaranteed to not modify
00473       // the query pointer, ignore it.  Use getModRefInfo to handle cases where
00474       // the query pointer points to constant memory etc.
00475       if (AA->getModRefInfo(SI, MemLoc) == AliasAnalysis::NoModRef)
00476         continue;
00477 
00478       // Ok, this store might clobber the query pointer.  Check to see if it is
00479       // a must alias: in this case, we want to return this as a def.
00480       AliasAnalysis::Location StoreLoc = AA->getLocation(SI);
00481 
00482       // If we found a pointer, check if it could be the same as our pointer.
00483       AliasAnalysis::AliasResult R = AA->alias(StoreLoc, MemLoc);
00484 
00485       if (R == AliasAnalysis::NoAlias)
00486         continue;
00487       if (R == AliasAnalysis::MustAlias)
00488         return MemDepResult::getDef(Inst);
00489       if (isInvariantLoad)
00490        continue;
00491       return MemDepResult::getClobber(Inst);
00492     }
00493 
00494     // If this is an allocation, and if we know that the accessed pointer is to
00495     // the allocation, return Def.  This means that there is no dependence and
00496     // the access can be optimized based on that.  For example, a load could
00497     // turn into undef.
00498     // Note: Only determine this to be a malloc if Inst is the malloc call, not
00499     // a subsequent bitcast of the malloc call result.  There can be stores to
00500     // the malloced memory between the malloc call and its bitcast uses, and we
00501     // need to continue scanning until the malloc call.
00502     const TargetLibraryInfo *TLI = AA->getTargetLibraryInfo();
00503     if (isa<AllocaInst>(Inst) || isNoAliasFn(Inst, TLI)) {
00504       const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, DL);
00505 
00506       if (AccessPtr == Inst || AA->isMustAlias(Inst, AccessPtr))
00507         return MemDepResult::getDef(Inst);
00508       // Be conservative if the accessed pointer may alias the allocation.
00509       if (AA->alias(Inst, AccessPtr) != AliasAnalysis::NoAlias)
00510         return MemDepResult::getClobber(Inst);
00511       // If the allocation is not aliased and does not read memory (like
00512       // strdup), it is safe to ignore.
00513       if (isa<AllocaInst>(Inst) ||
00514           isMallocLikeFn(Inst, TLI) || isCallocLikeFn(Inst, TLI))
00515         continue;
00516     }
00517 
00518     // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
00519     AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc);
00520     // If necessary, perform additional analysis.
00521     if (MR == AliasAnalysis::ModRef)
00522       MR = AA->callCapturesBefore(Inst, MemLoc, DT);
00523     switch (MR) {
00524     case AliasAnalysis::NoModRef:
00525       // If the call has no effect on the queried pointer, just ignore it.
00526       continue;
00527     case AliasAnalysis::Mod:
00528       return MemDepResult::getClobber(Inst);
00529     case AliasAnalysis::Ref:
00530       // If the call is known to never store to the pointer, and if this is a
00531       // load query, we can safely ignore it (scan past it).
00532       if (isLoad)
00533         continue;
00534     default:
00535       // Otherwise, there is a potential dependence.  Return a clobber.
00536       return MemDepResult::getClobber(Inst);
00537     }
00538   }
00539 
00540   // No dependence found.  If this is the entry block of the function, it is
00541   // unknown, otherwise it is non-local.
00542   if (BB != &BB->getParent()->getEntryBlock())
00543     return MemDepResult::getNonLocal();
00544   return MemDepResult::getNonFuncLocal();
00545 }
00546 
00547 /// getDependency - Return the instruction on which a memory operation
00548 /// depends.
00549 MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
00550   Instruction *ScanPos = QueryInst;
00551 
00552   // Check for a cached result
00553   MemDepResult &LocalCache = LocalDeps[QueryInst];
00554 
00555   // If the cached entry is non-dirty, just return it.  Note that this depends
00556   // on MemDepResult's default constructing to 'dirty'.
00557   if (!LocalCache.isDirty())
00558     return LocalCache;
00559 
00560   // Otherwise, if we have a dirty entry, we know we can start the scan at that
00561   // instruction, which may save us some work.
00562   if (Instruction *Inst = LocalCache.getInst()) {
00563     ScanPos = Inst;
00564 
00565     RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
00566   }
00567 
00568   BasicBlock *QueryParent = QueryInst->getParent();
00569 
00570   // Do the scan.
00571   if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
00572     // No dependence found.  If this is the entry block of the function, it is
00573     // unknown, otherwise it is non-local.
00574     if (QueryParent != &QueryParent->getParent()->getEntryBlock())
00575       LocalCache = MemDepResult::getNonLocal();
00576     else
00577       LocalCache = MemDepResult::getNonFuncLocal();
00578   } else {
00579     AliasAnalysis::Location MemLoc;
00580     AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA);
00581     if (MemLoc.Ptr) {
00582       // If we can do a pointer scan, make it happen.
00583       bool isLoad = !(MR & AliasAnalysis::Mod);
00584       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst))
00585         isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
00586 
00587       LocalCache = getPointerDependencyFrom(MemLoc, isLoad, ScanPos,
00588                                             QueryParent, QueryInst);
00589     } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
00590       CallSite QueryCS(QueryInst);
00591       bool isReadOnly = AA->onlyReadsMemory(QueryCS);
00592       LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos,
00593                                              QueryParent);
00594     } else
00595       // Non-memory instruction.
00596       LocalCache = MemDepResult::getUnknown();
00597   }
00598 
00599   // Remember the result!
00600   if (Instruction *I = LocalCache.getInst())
00601     ReverseLocalDeps[I].insert(QueryInst);
00602 
00603   return LocalCache;
00604 }
00605 
00606 #ifndef NDEBUG
00607 /// AssertSorted - This method is used when -debug is specified to verify that
00608 /// cache arrays are properly kept sorted.
00609 static void AssertSorted(MemoryDependenceAnalysis::NonLocalDepInfo &Cache,
00610                          int Count = -1) {
00611   if (Count == -1) Count = Cache.size();
00612   if (Count == 0) return;
00613 
00614   for (unsigned i = 1; i != unsigned(Count); ++i)
00615     assert(!(Cache[i] < Cache[i-1]) && "Cache isn't sorted!");
00616 }
00617 #endif
00618 
00619 /// getNonLocalCallDependency - Perform a full dependency query for the
00620 /// specified call, returning the set of blocks that the value is
00621 /// potentially live across.  The returned set of results will include a
00622 /// "NonLocal" result for all blocks where the value is live across.
00623 ///
00624 /// This method assumes the instruction returns a "NonLocal" dependency
00625 /// within its own block.
00626 ///
00627 /// This returns a reference to an internal data structure that may be
00628 /// invalidated on the next non-local query or when an instruction is
00629 /// removed.  Clients must copy this data if they want it around longer than
00630 /// that.
00631 const MemoryDependenceAnalysis::NonLocalDepInfo &
00632 MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) {
00633   assert(getDependency(QueryCS.getInstruction()).isNonLocal() &&
00634  "getNonLocalCallDependency should only be used on calls with non-local deps!");
00635   PerInstNLInfo &CacheP = NonLocalDeps[QueryCS.getInstruction()];
00636   NonLocalDepInfo &Cache = CacheP.first;
00637 
00638   /// DirtyBlocks - This is the set of blocks that need to be recomputed.  In
00639   /// the cached case, this can happen due to instructions being deleted etc. In
00640   /// the uncached case, this starts out as the set of predecessors we care
00641   /// about.
00642   SmallVector<BasicBlock*, 32> DirtyBlocks;
00643 
00644   if (!Cache.empty()) {
00645     // Okay, we have a cache entry.  If we know it is not dirty, just return it
00646     // with no computation.
00647     if (!CacheP.second) {
00648       ++NumCacheNonLocal;
00649       return Cache;
00650     }
00651 
00652     // If we already have a partially computed set of results, scan them to
00653     // determine what is dirty, seeding our initial DirtyBlocks worklist.
00654     for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end();
00655        I != E; ++I)
00656       if (I->getResult().isDirty())
00657         DirtyBlocks.push_back(I->getBB());
00658 
00659     // Sort the cache so that we can do fast binary search lookups below.
00660     std::sort(Cache.begin(), Cache.end());
00661 
00662     ++NumCacheDirtyNonLocal;
00663     //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
00664     //     << Cache.size() << " cached: " << *QueryInst;
00665   } else {
00666     // Seed DirtyBlocks with each of the preds of QueryInst's block.
00667     BasicBlock *QueryBB = QueryCS.getInstruction()->getParent();
00668     for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI)
00669       DirtyBlocks.push_back(*PI);
00670     ++NumUncacheNonLocal;
00671   }
00672 
00673   // isReadonlyCall - If this is a read-only call, we can be more aggressive.
00674   bool isReadonlyCall = AA->onlyReadsMemory(QueryCS);
00675 
00676   SmallPtrSet<BasicBlock*, 64> Visited;
00677 
00678   unsigned NumSortedEntries = Cache.size();
00679   DEBUG(AssertSorted(Cache));
00680 
00681   // Iterate while we still have blocks to update.
00682   while (!DirtyBlocks.empty()) {
00683     BasicBlock *DirtyBB = DirtyBlocks.back();
00684     DirtyBlocks.pop_back();
00685 
00686     // Already processed this block?
00687     if (!Visited.insert(DirtyBB))
00688       continue;
00689 
00690     // Do a binary search to see if we already have an entry for this block in
00691     // the cache set.  If so, find it.
00692     DEBUG(AssertSorted(Cache, NumSortedEntries));
00693     NonLocalDepInfo::iterator Entry =
00694       std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries,
00695                        NonLocalDepEntry(DirtyBB));
00696     if (Entry != Cache.begin() && std::prev(Entry)->getBB() == DirtyBB)
00697       --Entry;
00698 
00699     NonLocalDepEntry *ExistingResult = nullptr;
00700     if (Entry != Cache.begin()+NumSortedEntries &&
00701         Entry->getBB() == DirtyBB) {
00702       // If we already have an entry, and if it isn't already dirty, the block
00703       // is done.
00704       if (!Entry->getResult().isDirty())
00705         continue;
00706 
00707       // Otherwise, remember this slot so we can update the value.
00708       ExistingResult = &*Entry;
00709     }
00710 
00711     // If the dirty entry has a pointer, start scanning from it so we don't have
00712     // to rescan the entire block.
00713     BasicBlock::iterator ScanPos = DirtyBB->end();
00714     if (ExistingResult) {
00715       if (Instruction *Inst = ExistingResult->getResult().getInst()) {
00716         ScanPos = Inst;
00717         // We're removing QueryInst's use of Inst.
00718         RemoveFromReverseMap(ReverseNonLocalDeps, Inst,
00719                              QueryCS.getInstruction());
00720       }
00721     }
00722 
00723     // Find out if this block has a local dependency for QueryInst.
00724     MemDepResult Dep;
00725 
00726     if (ScanPos != DirtyBB->begin()) {
00727       Dep = getCallSiteDependencyFrom(QueryCS, isReadonlyCall,ScanPos, DirtyBB);
00728     } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) {
00729       // No dependence found.  If this is the entry block of the function, it is
00730       // a clobber, otherwise it is unknown.
00731       Dep = MemDepResult::getNonLocal();
00732     } else {
00733       Dep = MemDepResult::getNonFuncLocal();
00734     }
00735 
00736     // If we had a dirty entry for the block, update it.  Otherwise, just add
00737     // a new entry.
00738     if (ExistingResult)
00739       ExistingResult->setResult(Dep);
00740     else
00741       Cache.push_back(NonLocalDepEntry(DirtyBB, Dep));
00742 
00743     // If the block has a dependency (i.e. it isn't completely transparent to
00744     // the value), remember the association!
00745     if (!Dep.isNonLocal()) {
00746       // Keep the ReverseNonLocalDeps map up to date so we can efficiently
00747       // update this when we remove instructions.
00748       if (Instruction *Inst = Dep.getInst())
00749         ReverseNonLocalDeps[Inst].insert(QueryCS.getInstruction());
00750     } else {
00751 
00752       // If the block *is* completely transparent to the load, we need to check
00753       // the predecessors of this block.  Add them to our worklist.
00754       for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI)
00755         DirtyBlocks.push_back(*PI);
00756     }
00757   }
00758 
00759   return Cache;
00760 }
00761 
00762 /// getNonLocalPointerDependency - Perform a full dependency query for an
00763 /// access to the specified (non-volatile) memory location, returning the
00764 /// set of instructions that either define or clobber the value.
00765 ///
00766 /// This method assumes the pointer has a "NonLocal" dependency within its
00767 /// own block.
00768 ///
00769 void MemoryDependenceAnalysis::
00770 getNonLocalPointerDependency(const AliasAnalysis::Location &Loc, bool isLoad,
00771                              BasicBlock *FromBB,
00772                              SmallVectorImpl<NonLocalDepResult> &Result) {
00773   assert(Loc.Ptr->getType()->isPointerTy() &&
00774          "Can't get pointer deps of a non-pointer!");
00775   Result.clear();
00776 
00777   PHITransAddr Address(const_cast<Value *>(Loc.Ptr), DL);
00778 
00779   // This is the set of blocks we've inspected, and the pointer we consider in
00780   // each block.  Because of critical edges, we currently bail out if querying
00781   // a block with multiple different pointers.  This can happen during PHI
00782   // translation.
00783   DenseMap<BasicBlock*, Value*> Visited;
00784   if (!getNonLocalPointerDepFromBB(Address, Loc, isLoad, FromBB,
00785                                    Result, Visited, true))
00786     return;
00787   Result.clear();
00788   Result.push_back(NonLocalDepResult(FromBB,
00789                                      MemDepResult::getUnknown(),
00790                                      const_cast<Value *>(Loc.Ptr)));
00791 }
00792 
00793 /// GetNonLocalInfoForBlock - Compute the memdep value for BB with
00794 /// Pointer/PointeeSize using either cached information in Cache or by doing a
00795 /// lookup (which may use dirty cache info if available).  If we do a lookup,
00796 /// add the result to the cache.
00797 MemDepResult MemoryDependenceAnalysis::
00798 GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc,
00799                         bool isLoad, BasicBlock *BB,
00800                         NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
00801 
00802   // Do a binary search to see if we already have an entry for this block in
00803   // the cache set.  If so, find it.
00804   NonLocalDepInfo::iterator Entry =
00805     std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
00806                      NonLocalDepEntry(BB));
00807   if (Entry != Cache->begin() && (Entry-1)->getBB() == BB)
00808     --Entry;
00809 
00810   NonLocalDepEntry *ExistingResult = nullptr;
00811   if (Entry != Cache->begin()+NumSortedEntries && Entry->getBB() == BB)
00812     ExistingResult = &*Entry;
00813 
00814   // If we have a cached entry, and it is non-dirty, use it as the value for
00815   // this dependency.
00816   if (ExistingResult && !ExistingResult->getResult().isDirty()) {
00817     ++NumCacheNonLocalPtr;
00818     return ExistingResult->getResult();
00819   }
00820 
00821   // Otherwise, we have to scan for the value.  If we have a dirty cache
00822   // entry, start scanning from its position, otherwise we scan from the end
00823   // of the block.
00824   BasicBlock::iterator ScanPos = BB->end();
00825   if (ExistingResult && ExistingResult->getResult().getInst()) {
00826     assert(ExistingResult->getResult().getInst()->getParent() == BB &&
00827            "Instruction invalidated?");
00828     ++NumCacheDirtyNonLocalPtr;
00829     ScanPos = ExistingResult->getResult().getInst();
00830 
00831     // Eliminating the dirty entry from 'Cache', so update the reverse info.
00832     ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
00833     RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos, CacheKey);
00834   } else {
00835     ++NumUncacheNonLocalPtr;
00836   }
00837 
00838   // Scan the block for the dependency.
00839   MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB);
00840 
00841   // If we had a dirty entry for the block, update it.  Otherwise, just add
00842   // a new entry.
00843   if (ExistingResult)
00844     ExistingResult->setResult(Dep);
00845   else
00846     Cache->push_back(NonLocalDepEntry(BB, Dep));
00847 
00848   // If the block has a dependency (i.e. it isn't completely transparent to
00849   // the value), remember the reverse association because we just added it
00850   // to Cache!
00851   if (!Dep.isDef() && !Dep.isClobber())
00852     return Dep;
00853 
00854   // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
00855   // update MemDep when we remove instructions.
00856   Instruction *Inst = Dep.getInst();
00857   assert(Inst && "Didn't depend on anything?");
00858   ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
00859   ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
00860   return Dep;
00861 }
00862 
00863 /// SortNonLocalDepInfoCache - Sort the a NonLocalDepInfo cache, given a certain
00864 /// number of elements in the array that are already properly ordered.  This is
00865 /// optimized for the case when only a few entries are added.
00866 static void
00867 SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache,
00868                          unsigned NumSortedEntries) {
00869   switch (Cache.size() - NumSortedEntries) {
00870   case 0:
00871     // done, no new entries.
00872     break;
00873   case 2: {
00874     // Two new entries, insert the last one into place.
00875     NonLocalDepEntry Val = Cache.back();
00876     Cache.pop_back();
00877     MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry =
00878       std::upper_bound(Cache.begin(), Cache.end()-1, Val);
00879     Cache.insert(Entry, Val);
00880     // FALL THROUGH.
00881   }
00882   case 1:
00883     // One new entry, Just insert the new value at the appropriate position.
00884     if (Cache.size() != 1) {
00885       NonLocalDepEntry Val = Cache.back();
00886       Cache.pop_back();
00887       MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry =
00888         std::upper_bound(Cache.begin(), Cache.end(), Val);
00889       Cache.insert(Entry, Val);
00890     }
00891     break;
00892   default:
00893     // Added many values, do a full scale sort.
00894     std::sort(Cache.begin(), Cache.end());
00895     break;
00896   }
00897 }
00898 
00899 /// getNonLocalPointerDepFromBB - Perform a dependency query based on
00900 /// pointer/pointeesize starting at the end of StartBB.  Add any clobber/def
00901 /// results to the results vector and keep track of which blocks are visited in
00902 /// 'Visited'.
00903 ///
00904 /// This has special behavior for the first block queries (when SkipFirstBlock
00905 /// is true).  In this special case, it ignores the contents of the specified
00906 /// block and starts returning dependence info for its predecessors.
00907 ///
00908 /// This function returns false on success, or true to indicate that it could
00909 /// not compute dependence information for some reason.  This should be treated
00910 /// as a clobber dependence on the first instruction in the predecessor block.
00911 bool MemoryDependenceAnalysis::
00912 getNonLocalPointerDepFromBB(const PHITransAddr &Pointer,
00913                             const AliasAnalysis::Location &Loc,
00914                             bool isLoad, BasicBlock *StartBB,
00915                             SmallVectorImpl<NonLocalDepResult> &Result,
00916                             DenseMap<BasicBlock*, Value*> &Visited,
00917                             bool SkipFirstBlock) {
00918   // Look up the cached info for Pointer.
00919   ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
00920 
00921   // Set up a temporary NLPI value. If the map doesn't yet have an entry for
00922   // CacheKey, this value will be inserted as the associated value. Otherwise,
00923   // it'll be ignored, and we'll have to check to see if the cached size and
00924   // tbaa tag are consistent with the current query.
00925   NonLocalPointerInfo InitialNLPI;
00926   InitialNLPI.Size = Loc.Size;
00927   InitialNLPI.TBAATag = Loc.TBAATag;
00928 
00929   // Get the NLPI for CacheKey, inserting one into the map if it doesn't
00930   // already have one.
00931   std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
00932     NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
00933   NonLocalPointerInfo *CacheInfo = &Pair.first->second;
00934 
00935   // If we already have a cache entry for this CacheKey, we may need to do some
00936   // work to reconcile the cache entry and the current query.
00937   if (!Pair.second) {
00938     if (CacheInfo->Size < Loc.Size) {
00939       // The query's Size is greater than the cached one. Throw out the
00940       // cached data and proceed with the query at the greater size.
00941       CacheInfo->Pair = BBSkipFirstBlockPair();
00942       CacheInfo->Size = Loc.Size;
00943       for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(),
00944            DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI)
00945         if (Instruction *Inst = DI->getResult().getInst())
00946           RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
00947       CacheInfo->NonLocalDeps.clear();
00948     } else if (CacheInfo->Size > Loc.Size) {
00949       // This query's Size is less than the cached one. Conservatively restart
00950       // the query using the greater size.
00951       return getNonLocalPointerDepFromBB(Pointer,
00952                                          Loc.getWithNewSize(CacheInfo->Size),
00953                                          isLoad, StartBB, Result, Visited,
00954                                          SkipFirstBlock);
00955     }
00956 
00957     // If the query's TBAATag is inconsistent with the cached one,
00958     // conservatively throw out the cached data and restart the query with
00959     // no tag if needed.
00960     if (CacheInfo->TBAATag != Loc.TBAATag) {
00961       if (CacheInfo->TBAATag) {
00962         CacheInfo->Pair = BBSkipFirstBlockPair();
00963         CacheInfo->TBAATag = nullptr;
00964         for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(),
00965              DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI)
00966           if (Instruction *Inst = DI->getResult().getInst())
00967             RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
00968         CacheInfo->NonLocalDeps.clear();
00969       }
00970       if (Loc.TBAATag)
00971         return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutTBAATag(),
00972                                            isLoad, StartBB, Result, Visited,
00973                                            SkipFirstBlock);
00974     }
00975   }
00976 
00977   NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps;
00978 
00979   // If we have valid cached information for exactly the block we are
00980   // investigating, just return it with no recomputation.
00981   if (CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
00982     // We have a fully cached result for this query then we can just return the
00983     // cached results and populate the visited set.  However, we have to verify
00984     // that we don't already have conflicting results for these blocks.  Check
00985     // to ensure that if a block in the results set is in the visited set that
00986     // it was for the same pointer query.
00987     if (!Visited.empty()) {
00988       for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
00989            I != E; ++I) {
00990         DenseMap<BasicBlock*, Value*>::iterator VI = Visited.find(I->getBB());
00991         if (VI == Visited.end() || VI->second == Pointer.getAddr())
00992           continue;
00993 
00994         // We have a pointer mismatch in a block.  Just return clobber, saying
00995         // that something was clobbered in this result.  We could also do a
00996         // non-fully cached query, but there is little point in doing this.
00997         return true;
00998       }
00999     }
01000 
01001     Value *Addr = Pointer.getAddr();
01002     for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
01003          I != E; ++I) {
01004       Visited.insert(std::make_pair(I->getBB(), Addr));
01005       if (I->getResult().isNonLocal()) {
01006         continue;
01007       }
01008 
01009       if (!DT) {
01010         Result.push_back(NonLocalDepResult(I->getBB(),
01011                                            MemDepResult::getUnknown(),
01012                                            Addr));
01013       } else if (DT->isReachableFromEntry(I->getBB())) {
01014         Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr));
01015       }
01016     }
01017     ++NumCacheCompleteNonLocalPtr;
01018     return false;
01019   }
01020 
01021   // Otherwise, either this is a new block, a block with an invalid cache
01022   // pointer or one that we're about to invalidate by putting more info into it
01023   // than its valid cache info.  If empty, the result will be valid cache info,
01024   // otherwise it isn't.
01025   if (Cache->empty())
01026     CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
01027   else
01028     CacheInfo->Pair = BBSkipFirstBlockPair();
01029 
01030   SmallVector<BasicBlock*, 32> Worklist;
01031   Worklist.push_back(StartBB);
01032 
01033   // PredList used inside loop.
01034   SmallVector<std::pair<BasicBlock*, PHITransAddr>, 16> PredList;
01035 
01036   // Keep track of the entries that we know are sorted.  Previously cached
01037   // entries will all be sorted.  The entries we add we only sort on demand (we
01038   // don't insert every element into its sorted position).  We know that we
01039   // won't get any reuse from currently inserted values, because we don't
01040   // revisit blocks after we insert info for them.
01041   unsigned NumSortedEntries = Cache->size();
01042   DEBUG(AssertSorted(*Cache));
01043 
01044   while (!Worklist.empty()) {
01045     BasicBlock *BB = Worklist.pop_back_val();
01046 
01047     // Skip the first block if we have it.
01048     if (!SkipFirstBlock) {
01049       // Analyze the dependency of *Pointer in FromBB.  See if we already have
01050       // been here.
01051       assert(Visited.count(BB) && "Should check 'visited' before adding to WL");
01052 
01053       // Get the dependency info for Pointer in BB.  If we have cached
01054       // information, we will use it, otherwise we compute it.
01055       DEBUG(AssertSorted(*Cache, NumSortedEntries));
01056       MemDepResult Dep = GetNonLocalInfoForBlock(Loc, isLoad, BB, Cache,
01057                                                  NumSortedEntries);
01058 
01059       // If we got a Def or Clobber, add this to the list of results.
01060       if (!Dep.isNonLocal()) {
01061         if (!DT) {
01062           Result.push_back(NonLocalDepResult(BB,
01063                                              MemDepResult::getUnknown(),
01064                                              Pointer.getAddr()));
01065           continue;
01066         } else if (DT->isReachableFromEntry(BB)) {
01067           Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));
01068           continue;
01069         }
01070       }
01071     }
01072 
01073     // If 'Pointer' is an instruction defined in this block, then we need to do
01074     // phi translation to change it into a value live in the predecessor block.
01075     // If not, we just add the predecessors to the worklist and scan them with
01076     // the same Pointer.
01077     if (!Pointer.NeedsPHITranslationFromBlock(BB)) {
01078       SkipFirstBlock = false;
01079       SmallVector<BasicBlock*, 16> NewBlocks;
01080       for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
01081         // Verify that we haven't looked at this block yet.
01082         std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
01083           InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr()));
01084         if (InsertRes.second) {
01085           // First time we've looked at *PI.
01086           NewBlocks.push_back(*PI);
01087           continue;
01088         }
01089 
01090         // If we have seen this block before, but it was with a different
01091         // pointer then we have a phi translation failure and we have to treat
01092         // this as a clobber.
01093         if (InsertRes.first->second != Pointer.getAddr()) {
01094           // Make sure to clean up the Visited map before continuing on to
01095           // PredTranslationFailure.
01096           for (unsigned i = 0; i < NewBlocks.size(); i++)
01097             Visited.erase(NewBlocks[i]);
01098           goto PredTranslationFailure;
01099         }
01100       }
01101       Worklist.append(NewBlocks.begin(), NewBlocks.end());
01102       continue;
01103     }
01104 
01105     // We do need to do phi translation, if we know ahead of time we can't phi
01106     // translate this value, don't even try.
01107     if (!Pointer.IsPotentiallyPHITranslatable())
01108       goto PredTranslationFailure;
01109 
01110     // We may have added values to the cache list before this PHI translation.
01111     // If so, we haven't done anything to ensure that the cache remains sorted.
01112     // Sort it now (if needed) so that recursive invocations of
01113     // getNonLocalPointerDepFromBB and other routines that could reuse the cache
01114     // value will only see properly sorted cache arrays.
01115     if (Cache && NumSortedEntries != Cache->size()) {
01116       SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
01117       NumSortedEntries = Cache->size();
01118     }
01119     Cache = nullptr;
01120 
01121     PredList.clear();
01122     for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
01123       BasicBlock *Pred = *PI;
01124       PredList.push_back(std::make_pair(Pred, Pointer));
01125 
01126       // Get the PHI translated pointer in this predecessor.  This can fail if
01127       // not translatable, in which case the getAddr() returns null.
01128       PHITransAddr &PredPointer = PredList.back().second;
01129       PredPointer.PHITranslateValue(BB, Pred, nullptr);
01130 
01131       Value *PredPtrVal = PredPointer.getAddr();
01132 
01133       // Check to see if we have already visited this pred block with another
01134       // pointer.  If so, we can't do this lookup.  This failure can occur
01135       // with PHI translation when a critical edge exists and the PHI node in
01136       // the successor translates to a pointer value different than the
01137       // pointer the block was first analyzed with.
01138       std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
01139         InsertRes = Visited.insert(std::make_pair(Pred, PredPtrVal));
01140 
01141       if (!InsertRes.second) {
01142         // We found the pred; take it off the list of preds to visit.
01143         PredList.pop_back();
01144 
01145         // If the predecessor was visited with PredPtr, then we already did
01146         // the analysis and can ignore it.
01147         if (InsertRes.first->second == PredPtrVal)
01148           continue;
01149 
01150         // Otherwise, the block was previously analyzed with a different
01151         // pointer.  We can't represent the result of this case, so we just
01152         // treat this as a phi translation failure.
01153 
01154         // Make sure to clean up the Visited map before continuing on to
01155         // PredTranslationFailure.
01156         for (unsigned i = 0, n = PredList.size(); i < n; ++i)
01157           Visited.erase(PredList[i].first);
01158 
01159         goto PredTranslationFailure;
01160       }
01161     }
01162 
01163     // Actually process results here; this need to be a separate loop to avoid
01164     // calling getNonLocalPointerDepFromBB for blocks we don't want to return
01165     // any results for.  (getNonLocalPointerDepFromBB will modify our
01166     // datastructures in ways the code after the PredTranslationFailure label
01167     // doesn't expect.)
01168     for (unsigned i = 0, n = PredList.size(); i < n; ++i) {
01169       BasicBlock *Pred = PredList[i].first;
01170       PHITransAddr &PredPointer = PredList[i].second;
01171       Value *PredPtrVal = PredPointer.getAddr();
01172 
01173       bool CanTranslate = true;
01174       // If PHI translation was unable to find an available pointer in this
01175       // predecessor, then we have to assume that the pointer is clobbered in
01176       // that predecessor.  We can still do PRE of the load, which would insert
01177       // a computation of the pointer in this predecessor.
01178       if (!PredPtrVal)
01179         CanTranslate = false;
01180 
01181       // FIXME: it is entirely possible that PHI translating will end up with
01182       // the same value.  Consider PHI translating something like:
01183       // X = phi [x, bb1], [y, bb2].  PHI translating for bb1 doesn't *need*
01184       // to recurse here, pedantically speaking.
01185 
01186       // If getNonLocalPointerDepFromBB fails here, that means the cached
01187       // result conflicted with the Visited list; we have to conservatively
01188       // assume it is unknown, but this also does not block PRE of the load.
01189       if (!CanTranslate ||
01190           getNonLocalPointerDepFromBB(PredPointer,
01191                                       Loc.getWithNewPtr(PredPtrVal),
01192                                       isLoad, Pred,
01193                                       Result, Visited)) {
01194         // Add the entry to the Result list.
01195         NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal);
01196         Result.push_back(Entry);
01197 
01198         // Since we had a phi translation failure, the cache for CacheKey won't
01199         // include all of the entries that we need to immediately satisfy future
01200         // queries.  Mark this in NonLocalPointerDeps by setting the
01201         // BBSkipFirstBlockPair pointer to null.  This requires reuse of the
01202         // cached value to do more work but not miss the phi trans failure.
01203         NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
01204         NLPI.Pair = BBSkipFirstBlockPair();
01205         continue;
01206       }
01207     }
01208 
01209     // Refresh the CacheInfo/Cache pointer so that it isn't invalidated.
01210     CacheInfo = &NonLocalPointerDeps[CacheKey];
01211     Cache = &CacheInfo->NonLocalDeps;
01212     NumSortedEntries = Cache->size();
01213 
01214     // Since we did phi translation, the "Cache" set won't contain all of the
01215     // results for the query.  This is ok (we can still use it to accelerate
01216     // specific block queries) but we can't do the fastpath "return all
01217     // results from the set"  Clear out the indicator for this.
01218     CacheInfo->Pair = BBSkipFirstBlockPair();
01219     SkipFirstBlock = false;
01220     continue;
01221 
01222   PredTranslationFailure:
01223     // The following code is "failure"; we can't produce a sane translation
01224     // for the given block.  It assumes that we haven't modified any of
01225     // our datastructures while processing the current block.
01226 
01227     if (!Cache) {
01228       // Refresh the CacheInfo/Cache pointer if it got invalidated.
01229       CacheInfo = &NonLocalPointerDeps[CacheKey];
01230       Cache = &CacheInfo->NonLocalDeps;
01231       NumSortedEntries = Cache->size();
01232     }
01233 
01234     // Since we failed phi translation, the "Cache" set won't contain all of the
01235     // results for the query.  This is ok (we can still use it to accelerate
01236     // specific block queries) but we can't do the fastpath "return all
01237     // results from the set".  Clear out the indicator for this.
01238     CacheInfo->Pair = BBSkipFirstBlockPair();
01239 
01240     // If *nothing* works, mark the pointer as unknown.
01241     //
01242     // If this is the magic first block, return this as a clobber of the whole
01243     // incoming value.  Since we can't phi translate to one of the predecessors,
01244     // we have to bail out.
01245     if (SkipFirstBlock)
01246       return true;
01247 
01248     for (NonLocalDepInfo::reverse_iterator I = Cache->rbegin(); ; ++I) {
01249       assert(I != Cache->rend() && "Didn't find current block??");
01250       if (I->getBB() != BB)
01251         continue;
01252 
01253       assert(I->getResult().isNonLocal() &&
01254              "Should only be here with transparent block");
01255       I->setResult(MemDepResult::getUnknown());
01256       Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(),
01257                                          Pointer.getAddr()));
01258       break;
01259     }
01260   }
01261 
01262   // Okay, we're done now.  If we added new values to the cache, re-sort it.
01263   SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
01264   DEBUG(AssertSorted(*Cache));
01265   return false;
01266 }
01267 
01268 /// RemoveCachedNonLocalPointerDependencies - If P exists in
01269 /// CachedNonLocalPointerInfo, remove it.
01270 void MemoryDependenceAnalysis::
01271 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) {
01272   CachedNonLocalPointerInfo::iterator It =
01273     NonLocalPointerDeps.find(P);
01274   if (It == NonLocalPointerDeps.end()) return;
01275 
01276   // Remove all of the entries in the BB->val map.  This involves removing
01277   // instructions from the reverse map.
01278   NonLocalDepInfo &PInfo = It->second.NonLocalDeps;
01279 
01280   for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
01281     Instruction *Target = PInfo[i].getResult().getInst();
01282     if (!Target) continue;  // Ignore non-local dep results.
01283     assert(Target->getParent() == PInfo[i].getBB());
01284 
01285     // Eliminating the dirty entry from 'Cache', so update the reverse info.
01286     RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P);
01287   }
01288 
01289   // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
01290   NonLocalPointerDeps.erase(It);
01291 }
01292 
01293 
01294 /// invalidateCachedPointerInfo - This method is used to invalidate cached
01295 /// information about the specified pointer, because it may be too
01296 /// conservative in memdep.  This is an optional call that can be used when
01297 /// the client detects an equivalence between the pointer and some other
01298 /// value and replaces the other value with ptr. This can make Ptr available
01299 /// in more places that cached info does not necessarily keep.
01300 void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) {
01301   // If Ptr isn't really a pointer, just ignore it.
01302   if (!Ptr->getType()->isPointerTy()) return;
01303   // Flush store info for the pointer.
01304   RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false));
01305   // Flush load info for the pointer.
01306   RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
01307 }
01308 
01309 /// invalidateCachedPredecessors - Clear the PredIteratorCache info.
01310 /// This needs to be done when the CFG changes, e.g., due to splitting
01311 /// critical edges.
01312 void MemoryDependenceAnalysis::invalidateCachedPredecessors() {
01313   PredCache->clear();
01314 }
01315 
01316 /// removeInstruction - Remove an instruction from the dependence analysis,
01317 /// updating the dependence of instructions that previously depended on it.
01318 /// This method attempts to keep the cache coherent using the reverse map.
01319 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
01320   // Walk through the Non-local dependencies, removing this one as the value
01321   // for any cached queries.
01322   NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
01323   if (NLDI != NonLocalDeps.end()) {
01324     NonLocalDepInfo &BlockMap = NLDI->second.first;
01325     for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end();
01326          DI != DE; ++DI)
01327       if (Instruction *Inst = DI->getResult().getInst())
01328         RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
01329     NonLocalDeps.erase(NLDI);
01330   }
01331 
01332   // If we have a cached local dependence query for this instruction, remove it.
01333   //
01334   LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
01335   if (LocalDepEntry != LocalDeps.end()) {
01336     // Remove us from DepInst's reverse set now that the local dep info is gone.
01337     if (Instruction *Inst = LocalDepEntry->second.getInst())
01338       RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
01339 
01340     // Remove this local dependency info.
01341     LocalDeps.erase(LocalDepEntry);
01342   }
01343 
01344   // If we have any cached pointer dependencies on this instruction, remove
01345   // them.  If the instruction has non-pointer type, then it can't be a pointer
01346   // base.
01347 
01348   // Remove it from both the load info and the store info.  The instruction
01349   // can't be in either of these maps if it is non-pointer.
01350   if (RemInst->getType()->isPointerTy()) {
01351     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
01352     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
01353   }
01354 
01355   // Loop over all of the things that depend on the instruction we're removing.
01356   //
01357   SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd;
01358 
01359   // If we find RemInst as a clobber or Def in any of the maps for other values,
01360   // we need to replace its entry with a dirty version of the instruction after
01361   // it.  If RemInst is a terminator, we use a null dirty value.
01362   //
01363   // Using a dirty version of the instruction after RemInst saves having to scan
01364   // the entire block to get to this point.
01365   MemDepResult NewDirtyVal;
01366   if (!RemInst->isTerminator())
01367     NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst));
01368 
01369   ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
01370   if (ReverseDepIt != ReverseLocalDeps.end()) {
01371     SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
01372     // RemInst can't be the terminator if it has local stuff depending on it.
01373     assert(!ReverseDeps.empty() && !isa<TerminatorInst>(RemInst) &&
01374            "Nothing can locally depend on a terminator");
01375 
01376     for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
01377          E = ReverseDeps.end(); I != E; ++I) {
01378       Instruction *InstDependingOnRemInst = *I;
01379       assert(InstDependingOnRemInst != RemInst &&
01380              "Already removed our local dep info");
01381 
01382       LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
01383 
01384       // Make sure to remember that new things depend on NewDepInst.
01385       assert(NewDirtyVal.getInst() && "There is no way something else can have "
01386              "a local dep on this if it is a terminator!");
01387       ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(),
01388                                                 InstDependingOnRemInst));
01389     }
01390 
01391     ReverseLocalDeps.erase(ReverseDepIt);
01392 
01393     // Add new reverse deps after scanning the set, to avoid invalidating the
01394     // 'ReverseDeps' reference.
01395     while (!ReverseDepsToAdd.empty()) {
01396       ReverseLocalDeps[ReverseDepsToAdd.back().first]
01397         .insert(ReverseDepsToAdd.back().second);
01398       ReverseDepsToAdd.pop_back();
01399     }
01400   }
01401 
01402   ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
01403   if (ReverseDepIt != ReverseNonLocalDeps.end()) {
01404     SmallPtrSet<Instruction*, 4> &Set = ReverseDepIt->second;
01405     for (SmallPtrSet<Instruction*, 4>::iterator I = Set.begin(), E = Set.end();
01406          I != E; ++I) {
01407       assert(*I != RemInst && "Already removed NonLocalDep info for RemInst");
01408 
01409       PerInstNLInfo &INLD = NonLocalDeps[*I];
01410       // The information is now dirty!
01411       INLD.second = true;
01412 
01413       for (NonLocalDepInfo::iterator DI = INLD.first.begin(),
01414            DE = INLD.first.end(); DI != DE; ++DI) {
01415         if (DI->getResult().getInst() != RemInst) continue;
01416 
01417         // Convert to a dirty entry for the subsequent instruction.
01418         DI->setResult(NewDirtyVal);
01419 
01420         if (Instruction *NextI = NewDirtyVal.getInst())
01421           ReverseDepsToAdd.push_back(std::make_pair(NextI, *I));
01422       }
01423     }
01424 
01425     ReverseNonLocalDeps.erase(ReverseDepIt);
01426 
01427     // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
01428     while (!ReverseDepsToAdd.empty()) {
01429       ReverseNonLocalDeps[ReverseDepsToAdd.back().first]
01430         .insert(ReverseDepsToAdd.back().second);
01431       ReverseDepsToAdd.pop_back();
01432     }
01433   }
01434 
01435   // If the instruction is in ReverseNonLocalPtrDeps then it appears as a
01436   // value in the NonLocalPointerDeps info.
01437   ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
01438     ReverseNonLocalPtrDeps.find(RemInst);
01439   if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
01440     SmallPtrSet<ValueIsLoadPair, 4> &Set = ReversePtrDepIt->second;
01441     SmallVector<std::pair<Instruction*, ValueIsLoadPair>,8> ReversePtrDepsToAdd;
01442 
01443     for (SmallPtrSet<ValueIsLoadPair, 4>::iterator I = Set.begin(),
01444          E = Set.end(); I != E; ++I) {
01445       ValueIsLoadPair P = *I;
01446       assert(P.getPointer() != RemInst &&
01447              "Already removed NonLocalPointerDeps info for RemInst");
01448 
01449       NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].NonLocalDeps;
01450 
01451       // The cache is not valid for any specific block anymore.
01452       NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair();
01453 
01454       // Update any entries for RemInst to use the instruction after it.
01455       for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();
01456            DI != DE; ++DI) {
01457         if (DI->getResult().getInst() != RemInst) continue;
01458 
01459         // Convert to a dirty entry for the subsequent instruction.
01460         DI->setResult(NewDirtyVal);
01461 
01462         if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
01463           ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
01464       }
01465 
01466       // Re-sort the NonLocalDepInfo.  Changing the dirty entry to its
01467       // subsequent value may invalidate the sortedness.
01468       std::sort(NLPDI.begin(), NLPDI.end());
01469     }
01470 
01471     ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
01472 
01473     while (!ReversePtrDepsToAdd.empty()) {
01474       ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first]
01475         .insert(ReversePtrDepsToAdd.back().second);
01476       ReversePtrDepsToAdd.pop_back();
01477     }
01478   }
01479 
01480 
01481   assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
01482   AA->deleteValue(RemInst);
01483   DEBUG(verifyRemoved(RemInst));
01484 }
01485 /// verifyRemoved - Verify that the specified instruction does not occur
01486 /// in our internal data structures.
01487 void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
01488   for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
01489        E = LocalDeps.end(); I != E; ++I) {
01490     assert(I->first != D && "Inst occurs in data structures");
01491     assert(I->second.getInst() != D &&
01492            "Inst occurs in data structures");
01493   }
01494 
01495   for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(),
01496        E = NonLocalPointerDeps.end(); I != E; ++I) {
01497     assert(I->first.getPointer() != D && "Inst occurs in NLPD map key");
01498     const NonLocalDepInfo &Val = I->second.NonLocalDeps;
01499     for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end();
01500          II != E; ++II)
01501       assert(II->getResult().getInst() != D && "Inst occurs as NLPD value");
01502   }
01503 
01504   for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(),
01505        E = NonLocalDeps.end(); I != E; ++I) {
01506     assert(I->first != D && "Inst occurs in data structures");
01507     const PerInstNLInfo &INLD = I->second;
01508     for (NonLocalDepInfo::const_iterator II = INLD.first.begin(),
01509          EE = INLD.first.end(); II  != EE; ++II)
01510       assert(II->getResult().getInst() != D && "Inst occurs in data structures");
01511   }
01512 
01513   for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),
01514        E = ReverseLocalDeps.end(); I != E; ++I) {
01515     assert(I->first != D && "Inst occurs in data structures");
01516     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
01517          EE = I->second.end(); II != EE; ++II)
01518       assert(*II != D && "Inst occurs in data structures");
01519   }
01520 
01521   for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(),
01522        E = ReverseNonLocalDeps.end();
01523        I != E; ++I) {
01524     assert(I->first != D && "Inst occurs in data structures");
01525     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
01526          EE = I->second.end(); II != EE; ++II)
01527       assert(*II != D && "Inst occurs in data structures");
01528   }
01529 
01530   for (ReverseNonLocalPtrDepTy::const_iterator
01531        I = ReverseNonLocalPtrDeps.begin(),
01532        E = ReverseNonLocalPtrDeps.end(); I != E; ++I) {
01533     assert(I->first != D && "Inst occurs in rev NLPD map");
01534 
01535     for (SmallPtrSet<ValueIsLoadPair, 4>::const_iterator II = I->second.begin(),
01536          E = I->second.end(); II != E; ++II)
01537       assert(*II != ValueIsLoadPair(D, false) &&
01538              *II != ValueIsLoadPair(D, true) &&
01539              "Inst occurs in ReverseNonLocalPtrDeps map");
01540   }
01541 
01542 }