Enhance GVN to do more precise alias queries for non-local memory
[oota-llvm.git] / 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/Instructions.h"
20 #include "llvm/IntrinsicInst.h"
21 #include "llvm/Function.h"
22 #include "llvm/LLVMContext.h"
23 #include "llvm/Analysis/AliasAnalysis.h"
24 #include "llvm/Analysis/Dominators.h"
25 #include "llvm/Analysis/InstructionSimplify.h"
26 #include "llvm/Analysis/MemoryBuiltins.h"
27 #include "llvm/Analysis/PHITransAddr.h"
28 #include "llvm/ADT/Statistic.h"
29 #include "llvm/ADT/STLExtras.h"
30 #include "llvm/Support/PredIteratorCache.h"
31 #include "llvm/Support/Debug.h"
32 using namespace llvm;
33
34 STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");
35 STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");
36 STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");
37
38 STATISTIC(NumCacheNonLocalPtr,
39           "Number of fully cached non-local ptr responses");
40 STATISTIC(NumCacheDirtyNonLocalPtr,
41           "Number of cached, but dirty, non-local ptr responses");
42 STATISTIC(NumUncacheNonLocalPtr,
43           "Number of uncached non-local ptr responses");
44 STATISTIC(NumCacheCompleteNonLocalPtr,
45           "Number of block queries that were completely cached");
46
47 char MemoryDependenceAnalysis::ID = 0;
48   
49 // Register this pass...
50 INITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep",
51                 "Memory Dependence Analysis", false, true)
52 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
53 INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep",
54                       "Memory Dependence Analysis", false, true)
55
56 MemoryDependenceAnalysis::MemoryDependenceAnalysis()
57 : FunctionPass(ID), PredCache(0) {
58   initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry());
59 }
60 MemoryDependenceAnalysis::~MemoryDependenceAnalysis() {
61 }
62
63 /// Clean up memory in between runs
64 void MemoryDependenceAnalysis::releaseMemory() {
65   LocalDeps.clear();
66   NonLocalDeps.clear();
67   NonLocalPointerDeps.clear();
68   ReverseLocalDeps.clear();
69   ReverseNonLocalDeps.clear();
70   ReverseNonLocalPtrDeps.clear();
71   PredCache->clear();
72 }
73
74
75
76 /// getAnalysisUsage - Does not modify anything.  It uses Alias Analysis.
77 ///
78 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
79   AU.setPreservesAll();
80   AU.addRequiredTransitive<AliasAnalysis>();
81 }
82
83 bool MemoryDependenceAnalysis::runOnFunction(Function &) {
84   AA = &getAnalysis<AliasAnalysis>();
85   if (PredCache == 0)
86     PredCache.reset(new PredIteratorCache());
87   return false;
88 }
89
90 /// RemoveFromReverseMap - This is a helper function that removes Val from
91 /// 'Inst's set in ReverseMap.  If the set becomes empty, remove Inst's entry.
92 template <typename KeyTy>
93 static void RemoveFromReverseMap(DenseMap<Instruction*, 
94                                  SmallPtrSet<KeyTy, 4> > &ReverseMap,
95                                  Instruction *Inst, KeyTy Val) {
96   typename DenseMap<Instruction*, SmallPtrSet<KeyTy, 4> >::iterator
97   InstIt = ReverseMap.find(Inst);
98   assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
99   bool Found = InstIt->second.erase(Val);
100   assert(Found && "Invalid reverse map!"); Found=Found;
101   if (InstIt->second.empty())
102     ReverseMap.erase(InstIt);
103 }
104
105
106 /// getCallSiteDependencyFrom - Private helper for finding the local
107 /// dependencies of a call site.
108 MemDepResult MemoryDependenceAnalysis::
109 getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
110                           BasicBlock::iterator ScanIt, BasicBlock *BB) {
111   // Walk backwards through the block, looking for dependencies
112   while (ScanIt != BB->begin()) {
113     Instruction *Inst = --ScanIt;
114     
115     // If this inst is a memory op, get the pointer it accessed
116     AliasAnalysis::Location Loc;
117     if (StoreInst *S = dyn_cast<StoreInst>(Inst)) {
118       Loc = AliasAnalysis::Location(S->getPointerOperand(),
119                                     AA->getTypeStoreSize(S->getValueOperand()
120                                                            ->getType()),
121                                     S->getMetadata(LLVMContext::MD_tbaa));
122     } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
123       Loc = AliasAnalysis::Location(V->getPointerOperand(),
124                                     AA->getTypeStoreSize(V->getType()),
125                                     V->getMetadata(LLVMContext::MD_tbaa));
126     } else if (const CallInst *CI = isFreeCall(Inst)) {
127       // calls to free() erase the entire structure
128       Loc = AliasAnalysis::Location(CI->getArgOperand(0));
129     } else if (CallSite InstCS = cast<Value>(Inst)) {
130       // Debug intrinsics don't cause dependences.
131       if (isa<DbgInfoIntrinsic>(Inst)) continue;
132       // If these two calls do not interfere, look past it.
133       switch (AA->getModRefInfo(CS, InstCS)) {
134       case AliasAnalysis::NoModRef:
135         // If the two calls are the same, return InstCS as a Def, so that
136         // CS can be found redundant and eliminated.
137         if (isReadOnlyCall && InstCS.onlyReadsMemory() &&
138             CS.getInstruction()->isIdenticalToWhenDefined(Inst))
139           return MemDepResult::getDef(Inst);
140
141         // Otherwise if the two calls don't interact (e.g. InstCS is readnone)
142         // keep scanning.
143         continue;
144       default:
145         return MemDepResult::getClobber(Inst);
146       }
147     } else {
148       // Non-memory instruction.
149       continue;
150     }
151     
152     if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef)
153       return MemDepResult::getClobber(Inst);
154   }
155   
156   // No dependence found.  If this is the entry block of the function, it is a
157   // clobber, otherwise it is non-local.
158   if (BB != &BB->getParent()->getEntryBlock())
159     return MemDepResult::getNonLocal();
160   return MemDepResult::getClobber(ScanIt);
161 }
162
163 /// getPointerDependencyFrom - Return the instruction on which a memory
164 /// location depends.  If isLoad is true, this routine ignores may-aliases with
165 /// read-only operations.  If isLoad is false, this routine ignores may-aliases
166 /// with reads from read-only locations.
167 MemDepResult MemoryDependenceAnalysis::
168 getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, 
169                          BasicBlock::iterator ScanIt, BasicBlock *BB) {
170
171   Value *InvariantTag = 0;
172
173   // Walk backwards through the basic block, looking for dependencies.
174   while (ScanIt != BB->begin()) {
175     Instruction *Inst = --ScanIt;
176
177     // If we're in an invariant region, no dependencies can be found before
178     // we pass an invariant-begin marker.
179     if (InvariantTag == Inst) {
180       InvariantTag = 0;
181       continue;
182     }
183     
184     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
185       // Debug intrinsics don't (and can't) cause dependences.
186       if (isa<DbgInfoIntrinsic>(II)) continue;
187       
188       // If we pass an invariant-end marker, then we've just entered an
189       // invariant region and can start ignoring dependencies.
190       if (II->getIntrinsicID() == Intrinsic::invariant_end) {
191         // FIXME: This only considers queries directly on the invariant-tagged
192         // pointer, not on query pointers that are indexed off of them.  It'd
193         // be nice to handle that at some point.
194         AliasAnalysis::AliasResult R =
195           AA->alias(AliasAnalysis::Location(II->getArgOperand(2)), MemLoc);
196         if (R == AliasAnalysis::MustAlias)
197           InvariantTag = II->getArgOperand(0);
198
199         continue;
200       }
201
202       // If we reach a lifetime begin or end marker, then the query ends here
203       // because the value is undefined.
204       if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
205         // FIXME: This only considers queries directly on the invariant-tagged
206         // pointer, not on query pointers that are indexed off of them.  It'd
207         // be nice to handle that at some point.
208         AliasAnalysis::AliasResult R =
209           AA->alias(AliasAnalysis::Location(II->getArgOperand(1)), MemLoc);
210         if (R == AliasAnalysis::MustAlias)
211           return MemDepResult::getDef(II);
212         continue;
213       }
214     }
215
216     // If we're querying on a load and we're in an invariant region, we're done
217     // at this point. Nothing a load depends on can live in an invariant region.
218     //
219     // FIXME: this will prevent us from returning load/load must-aliases, so GVN
220     // won't remove redundant loads.
221     if (isLoad && InvariantTag) continue;
222
223     // Values depend on loads if the pointers are must aliased.  This means that
224     // a load depends on another must aliased load from the same value.
225     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
226       Value *Pointer = LI->getPointerOperand();
227       uint64_t PointerSize = AA->getTypeStoreSize(LI->getType());
228       MDNode *TBAATag = LI->getMetadata(LLVMContext::MD_tbaa);
229       AliasAnalysis::Location LoadLoc(Pointer, PointerSize, TBAATag);
230       
231       // If we found a pointer, check if it could be the same as our pointer.
232       AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc);
233       if (R == AliasAnalysis::NoAlias)
234         continue;
235       
236       // May-alias loads don't depend on each other without a dependence.
237       if (isLoad && R == AliasAnalysis::MayAlias)
238         continue;
239
240       // Stores don't alias loads from read-only memory.
241       if (!isLoad && AA->pointsToConstantMemory(LoadLoc))
242         continue;
243
244       // Stores depend on may and must aliased loads, loads depend on must-alias
245       // loads.
246       return MemDepResult::getDef(Inst);
247     }
248     
249     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
250       // There can't be stores to the value we care about inside an 
251       // invariant region.
252       if (InvariantTag) continue;
253       
254       // If alias analysis can tell that this store is guaranteed to not modify
255       // the query pointer, ignore it.  Use getModRefInfo to handle cases where
256       // the query pointer points to constant memory etc.
257       if (AA->getModRefInfo(SI, MemLoc) == AliasAnalysis::NoModRef)
258         continue;
259
260       // Ok, this store might clobber the query pointer.  Check to see if it is
261       // a must alias: in this case, we want to return this as a def.
262       Value *Pointer = SI->getPointerOperand();
263       uint64_t PointerSize = AA->getTypeStoreSize(SI->getOperand(0)->getType());
264       MDNode *TBAATag = SI->getMetadata(LLVMContext::MD_tbaa);
265       
266       // If we found a pointer, check if it could be the same as our pointer.
267       AliasAnalysis::AliasResult R =
268         AA->alias(AliasAnalysis::Location(Pointer, PointerSize, TBAATag),
269                   MemLoc);
270       
271       if (R == AliasAnalysis::NoAlias)
272         continue;
273       if (R == AliasAnalysis::MayAlias)
274         return MemDepResult::getClobber(Inst);
275       return MemDepResult::getDef(Inst);
276     }
277
278     // If this is an allocation, and if we know that the accessed pointer is to
279     // the allocation, return Def.  This means that there is no dependence and
280     // the access can be optimized based on that.  For example, a load could
281     // turn into undef.
282     // Note: Only determine this to be a malloc if Inst is the malloc call, not
283     // a subsequent bitcast of the malloc call result.  There can be stores to
284     // the malloced memory between the malloc call and its bitcast uses, and we
285     // need to continue scanning until the malloc call.
286     if (isa<AllocaInst>(Inst) ||
287         (isa<CallInst>(Inst) && extractMallocCall(Inst))) {
288       const Value *AccessPtr = MemLoc.Ptr->getUnderlyingObject();
289       
290       if (AccessPtr == Inst ||
291           AA->alias(Inst, 1, AccessPtr, 1) == AliasAnalysis::MustAlias)
292         return MemDepResult::getDef(Inst);
293       continue;
294     }
295
296     // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
297     switch (AA->getModRefInfo(Inst, MemLoc)) {
298     case AliasAnalysis::NoModRef:
299       // If the call has no effect on the queried pointer, just ignore it.
300       continue;
301     case AliasAnalysis::Mod:
302       // If we're in an invariant region, we can ignore calls that ONLY
303       // modify the pointer.
304       if (InvariantTag) continue;
305       return MemDepResult::getClobber(Inst);
306     case AliasAnalysis::Ref:
307       // If the call is known to never store to the pointer, and if this is a
308       // load query, we can safely ignore it (scan past it).
309       if (isLoad)
310         continue;
311     default:
312       // Otherwise, there is a potential dependence.  Return a clobber.
313       return MemDepResult::getClobber(Inst);
314     }
315   }
316   
317   // No dependence found.  If this is the entry block of the function, it is a
318   // clobber, otherwise it is non-local.
319   if (BB != &BB->getParent()->getEntryBlock())
320     return MemDepResult::getNonLocal();
321   return MemDepResult::getClobber(ScanIt);
322 }
323
324 /// getDependency - Return the instruction on which a memory operation
325 /// depends.
326 MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
327   Instruction *ScanPos = QueryInst;
328   
329   // Check for a cached result
330   MemDepResult &LocalCache = LocalDeps[QueryInst];
331   
332   // If the cached entry is non-dirty, just return it.  Note that this depends
333   // on MemDepResult's default constructing to 'dirty'.
334   if (!LocalCache.isDirty())
335     return LocalCache;
336     
337   // Otherwise, if we have a dirty entry, we know we can start the scan at that
338   // instruction, which may save us some work.
339   if (Instruction *Inst = LocalCache.getInst()) {
340     ScanPos = Inst;
341    
342     RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
343   }
344   
345   BasicBlock *QueryParent = QueryInst->getParent();
346   
347   AliasAnalysis::Location MemLoc;
348   
349   // Do the scan.
350   if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
351     // No dependence found.  If this is the entry block of the function, it is a
352     // clobber, otherwise it is non-local.
353     if (QueryParent != &QueryParent->getParent()->getEntryBlock())
354       LocalCache = MemDepResult::getNonLocal();
355     else
356       LocalCache = MemDepResult::getClobber(QueryInst);
357   } else if (StoreInst *SI = dyn_cast<StoreInst>(QueryInst)) {
358     // If this is a volatile store, don't mess around with it.  Just return the
359     // previous instruction as a clobber.
360     if (SI->isVolatile())
361       LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
362     else
363       MemLoc = AliasAnalysis::Location(SI->getPointerOperand(),
364                                        AA->getTypeStoreSize(SI->getOperand(0)
365                                                               ->getType()),
366                                        SI->getMetadata(LLVMContext::MD_tbaa));
367   } else if (LoadInst *LI = dyn_cast<LoadInst>(QueryInst)) {
368     // If this is a volatile load, don't mess around with it.  Just return the
369     // previous instruction as a clobber.
370     if (LI->isVolatile())
371       LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
372     else
373       MemLoc = AliasAnalysis::Location(LI->getPointerOperand(),
374                                        AA->getTypeStoreSize(LI->getType()),
375                                        LI->getMetadata(LLVMContext::MD_tbaa));
376   } else if (const CallInst *CI = isFreeCall(QueryInst)) {
377     // calls to free() erase the entire structure, not just a field.
378     MemLoc = AliasAnalysis::Location(CI->getArgOperand(0));
379   } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
380     int IntrinsicID = 0;  // Intrinsic IDs start at 1.
381     IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst);
382     if (II)
383       IntrinsicID = II->getIntrinsicID();
384
385     switch (IntrinsicID) {
386     case Intrinsic::lifetime_start:
387     case Intrinsic::lifetime_end:
388     case Intrinsic::invariant_start:
389       MemLoc = AliasAnalysis::Location(II->getArgOperand(1),
390                                        cast<ConstantInt>(II->getArgOperand(0))
391                                          ->getZExtValue(),
392                                        II->getMetadata(LLVMContext::MD_tbaa));
393       break;
394     case Intrinsic::invariant_end:
395       MemLoc = AliasAnalysis::Location(II->getArgOperand(2),
396                                        cast<ConstantInt>(II->getArgOperand(1))
397                                          ->getZExtValue(),
398                                        II->getMetadata(LLVMContext::MD_tbaa));
399       break;
400     default:
401       CallSite QueryCS(QueryInst);
402       bool isReadOnly = AA->onlyReadsMemory(QueryCS);
403       LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos,
404                                              QueryParent);
405       break;
406     }
407   } else {
408     // Non-memory instruction.
409     LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
410   }
411   
412   // If we need to do a pointer scan, make it happen.
413   if (MemLoc.Ptr) {
414     bool isLoad = !QueryInst->mayWriteToMemory();
415     if (IntrinsicInst *II = dyn_cast<MemoryUseIntrinsic>(QueryInst)) {
416       isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_end;
417     }
418     LocalCache = getPointerDependencyFrom(MemLoc, isLoad, ScanPos,
419                                           QueryParent);
420   }
421   
422   // Remember the result!
423   if (Instruction *I = LocalCache.getInst())
424     ReverseLocalDeps[I].insert(QueryInst);
425   
426   return LocalCache;
427 }
428
429 #ifndef NDEBUG
430 /// AssertSorted - This method is used when -debug is specified to verify that
431 /// cache arrays are properly kept sorted.
432 static void AssertSorted(MemoryDependenceAnalysis::NonLocalDepInfo &Cache,
433                          int Count = -1) {
434   if (Count == -1) Count = Cache.size();
435   if (Count == 0) return;
436
437   for (unsigned i = 1; i != unsigned(Count); ++i)
438     assert(!(Cache[i] < Cache[i-1]) && "Cache isn't sorted!");
439 }
440 #endif
441
442 /// getNonLocalCallDependency - Perform a full dependency query for the
443 /// specified call, returning the set of blocks that the value is
444 /// potentially live across.  The returned set of results will include a
445 /// "NonLocal" result for all blocks where the value is live across.
446 ///
447 /// This method assumes the instruction returns a "NonLocal" dependency
448 /// within its own block.
449 ///
450 /// This returns a reference to an internal data structure that may be
451 /// invalidated on the next non-local query or when an instruction is
452 /// removed.  Clients must copy this data if they want it around longer than
453 /// that.
454 const MemoryDependenceAnalysis::NonLocalDepInfo &
455 MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) {
456   assert(getDependency(QueryCS.getInstruction()).isNonLocal() &&
457  "getNonLocalCallDependency should only be used on calls with non-local deps!");
458   PerInstNLInfo &CacheP = NonLocalDeps[QueryCS.getInstruction()];
459   NonLocalDepInfo &Cache = CacheP.first;
460
461   /// DirtyBlocks - This is the set of blocks that need to be recomputed.  In
462   /// the cached case, this can happen due to instructions being deleted etc. In
463   /// the uncached case, this starts out as the set of predecessors we care
464   /// about.
465   SmallVector<BasicBlock*, 32> DirtyBlocks;
466   
467   if (!Cache.empty()) {
468     // Okay, we have a cache entry.  If we know it is not dirty, just return it
469     // with no computation.
470     if (!CacheP.second) {
471       ++NumCacheNonLocal;
472       return Cache;
473     }
474     
475     // If we already have a partially computed set of results, scan them to
476     // determine what is dirty, seeding our initial DirtyBlocks worklist.
477     for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end();
478        I != E; ++I)
479       if (I->getResult().isDirty())
480         DirtyBlocks.push_back(I->getBB());
481     
482     // Sort the cache so that we can do fast binary search lookups below.
483     std::sort(Cache.begin(), Cache.end());
484     
485     ++NumCacheDirtyNonLocal;
486     //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
487     //     << Cache.size() << " cached: " << *QueryInst;
488   } else {
489     // Seed DirtyBlocks with each of the preds of QueryInst's block.
490     BasicBlock *QueryBB = QueryCS.getInstruction()->getParent();
491     for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI)
492       DirtyBlocks.push_back(*PI);
493     ++NumUncacheNonLocal;
494   }
495   
496   // isReadonlyCall - If this is a read-only call, we can be more aggressive.
497   bool isReadonlyCall = AA->onlyReadsMemory(QueryCS);
498
499   SmallPtrSet<BasicBlock*, 64> Visited;
500   
501   unsigned NumSortedEntries = Cache.size();
502   DEBUG(AssertSorted(Cache));
503   
504   // Iterate while we still have blocks to update.
505   while (!DirtyBlocks.empty()) {
506     BasicBlock *DirtyBB = DirtyBlocks.back();
507     DirtyBlocks.pop_back();
508     
509     // Already processed this block?
510     if (!Visited.insert(DirtyBB))
511       continue;
512     
513     // Do a binary search to see if we already have an entry for this block in
514     // the cache set.  If so, find it.
515     DEBUG(AssertSorted(Cache, NumSortedEntries));
516     NonLocalDepInfo::iterator Entry = 
517       std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries,
518                        NonLocalDepEntry(DirtyBB));
519     if (Entry != Cache.begin() && prior(Entry)->getBB() == DirtyBB)
520       --Entry;
521     
522     NonLocalDepEntry *ExistingResult = 0;
523     if (Entry != Cache.begin()+NumSortedEntries && 
524         Entry->getBB() == DirtyBB) {
525       // If we already have an entry, and if it isn't already dirty, the block
526       // is done.
527       if (!Entry->getResult().isDirty())
528         continue;
529       
530       // Otherwise, remember this slot so we can update the value.
531       ExistingResult = &*Entry;
532     }
533     
534     // If the dirty entry has a pointer, start scanning from it so we don't have
535     // to rescan the entire block.
536     BasicBlock::iterator ScanPos = DirtyBB->end();
537     if (ExistingResult) {
538       if (Instruction *Inst = ExistingResult->getResult().getInst()) {
539         ScanPos = Inst;
540         // We're removing QueryInst's use of Inst.
541         RemoveFromReverseMap(ReverseNonLocalDeps, Inst,
542                              QueryCS.getInstruction());
543       }
544     }
545     
546     // Find out if this block has a local dependency for QueryInst.
547     MemDepResult Dep;
548     
549     if (ScanPos != DirtyBB->begin()) {
550       Dep = getCallSiteDependencyFrom(QueryCS, isReadonlyCall,ScanPos, DirtyBB);
551     } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) {
552       // No dependence found.  If this is the entry block of the function, it is
553       // a clobber, otherwise it is non-local.
554       Dep = MemDepResult::getNonLocal();
555     } else {
556       Dep = MemDepResult::getClobber(ScanPos);
557     }
558     
559     // If we had a dirty entry for the block, update it.  Otherwise, just add
560     // a new entry.
561     if (ExistingResult)
562       ExistingResult->setResult(Dep);
563     else
564       Cache.push_back(NonLocalDepEntry(DirtyBB, Dep));
565     
566     // If the block has a dependency (i.e. it isn't completely transparent to
567     // the value), remember the association!
568     if (!Dep.isNonLocal()) {
569       // Keep the ReverseNonLocalDeps map up to date so we can efficiently
570       // update this when we remove instructions.
571       if (Instruction *Inst = Dep.getInst())
572         ReverseNonLocalDeps[Inst].insert(QueryCS.getInstruction());
573     } else {
574     
575       // If the block *is* completely transparent to the load, we need to check
576       // the predecessors of this block.  Add them to our worklist.
577       for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI)
578         DirtyBlocks.push_back(*PI);
579     }
580   }
581   
582   return Cache;
583 }
584
585 /// getNonLocalPointerDependency - Perform a full dependency query for an
586 /// access to the specified (non-volatile) memory location, returning the
587 /// set of instructions that either define or clobber the value.
588 ///
589 /// This method assumes the pointer has a "NonLocal" dependency within its
590 /// own block.
591 ///
592 void MemoryDependenceAnalysis::
593 getNonLocalPointerDependency(const AliasAnalysis::Location &Loc, bool isLoad,
594                              BasicBlock *FromBB,
595                              SmallVectorImpl<NonLocalDepResult> &Result) {
596   assert(Loc.Ptr->getType()->isPointerTy() &&
597          "Can't get pointer deps of a non-pointer!");
598   Result.clear();
599   
600   PHITransAddr Address(const_cast<Value *>(Loc.Ptr), TD);
601   
602   // This is the set of blocks we've inspected, and the pointer we consider in
603   // each block.  Because of critical edges, we currently bail out if querying
604   // a block with multiple different pointers.  This can happen during PHI
605   // translation.
606   DenseMap<BasicBlock*, Value*> Visited;
607   if (!getNonLocalPointerDepFromBB(Address, Loc, isLoad, FromBB,
608                                    Result, Visited, true))
609     return;
610   Result.clear();
611   Result.push_back(NonLocalDepResult(FromBB,
612                                      MemDepResult::getClobber(FromBB->begin()),
613                                      const_cast<Value *>(Loc.Ptr)));
614 }
615
616 /// GetNonLocalInfoForBlock - Compute the memdep value for BB with
617 /// Pointer/PointeeSize using either cached information in Cache or by doing a
618 /// lookup (which may use dirty cache info if available).  If we do a lookup,
619 /// add the result to the cache.
620 MemDepResult MemoryDependenceAnalysis::
621 GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc,
622                         bool isLoad, BasicBlock *BB,
623                         NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
624   
625   // Do a binary search to see if we already have an entry for this block in
626   // the cache set.  If so, find it.
627   NonLocalDepInfo::iterator Entry =
628     std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
629                      NonLocalDepEntry(BB));
630   if (Entry != Cache->begin() && (Entry-1)->getBB() == BB)
631     --Entry;
632   
633   NonLocalDepEntry *ExistingResult = 0;
634   if (Entry != Cache->begin()+NumSortedEntries && Entry->getBB() == BB)
635     ExistingResult = &*Entry;
636   
637   // If we have a cached entry, and it is non-dirty, use it as the value for
638   // this dependency.
639   if (ExistingResult && !ExistingResult->getResult().isDirty()) {
640     ++NumCacheNonLocalPtr;
641     return ExistingResult->getResult();
642   }    
643   
644   // Otherwise, we have to scan for the value.  If we have a dirty cache
645   // entry, start scanning from its position, otherwise we scan from the end
646   // of the block.
647   BasicBlock::iterator ScanPos = BB->end();
648   if (ExistingResult && ExistingResult->getResult().getInst()) {
649     assert(ExistingResult->getResult().getInst()->getParent() == BB &&
650            "Instruction invalidated?");
651     ++NumCacheDirtyNonLocalPtr;
652     ScanPos = ExistingResult->getResult().getInst();
653     
654     // Eliminating the dirty entry from 'Cache', so update the reverse info.
655     ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
656     RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos, CacheKey);
657   } else {
658     ++NumUncacheNonLocalPtr;
659   }
660   
661   // Scan the block for the dependency.
662   MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB);
663   
664   // If we had a dirty entry for the block, update it.  Otherwise, just add
665   // a new entry.
666   if (ExistingResult)
667     ExistingResult->setResult(Dep);
668   else
669     Cache->push_back(NonLocalDepEntry(BB, Dep));
670   
671   // If the block has a dependency (i.e. it isn't completely transparent to
672   // the value), remember the reverse association because we just added it
673   // to Cache!
674   if (Dep.isNonLocal())
675     return Dep;
676   
677   // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
678   // update MemDep when we remove instructions.
679   Instruction *Inst = Dep.getInst();
680   assert(Inst && "Didn't depend on anything?");
681   ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
682   ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
683   return Dep;
684 }
685
686 /// SortNonLocalDepInfoCache - Sort the a NonLocalDepInfo cache, given a certain
687 /// number of elements in the array that are already properly ordered.  This is
688 /// optimized for the case when only a few entries are added.
689 static void 
690 SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache,
691                          unsigned NumSortedEntries) {
692   switch (Cache.size() - NumSortedEntries) {
693   case 0:
694     // done, no new entries.
695     break;
696   case 2: {
697     // Two new entries, insert the last one into place.
698     NonLocalDepEntry Val = Cache.back();
699     Cache.pop_back();
700     MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry =
701       std::upper_bound(Cache.begin(), Cache.end()-1, Val);
702     Cache.insert(Entry, Val);
703     // FALL THROUGH.
704   }
705   case 1:
706     // One new entry, Just insert the new value at the appropriate position.
707     if (Cache.size() != 1) {
708       NonLocalDepEntry Val = Cache.back();
709       Cache.pop_back();
710       MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry =
711         std::upper_bound(Cache.begin(), Cache.end(), Val);
712       Cache.insert(Entry, Val);
713     }
714     break;
715   default:
716     // Added many values, do a full scale sort.
717     std::sort(Cache.begin(), Cache.end());
718     break;
719   }
720 }
721
722 /// getNonLocalPointerDepFromBB - Perform a dependency query based on
723 /// pointer/pointeesize starting at the end of StartBB.  Add any clobber/def
724 /// results to the results vector and keep track of which blocks are visited in
725 /// 'Visited'.
726 ///
727 /// This has special behavior for the first block queries (when SkipFirstBlock
728 /// is true).  In this special case, it ignores the contents of the specified
729 /// block and starts returning dependence info for its predecessors.
730 ///
731 /// This function returns false on success, or true to indicate that it could
732 /// not compute dependence information for some reason.  This should be treated
733 /// as a clobber dependence on the first instruction in the predecessor block.
734 bool MemoryDependenceAnalysis::
735 getNonLocalPointerDepFromBB(const PHITransAddr &Pointer,
736                             const AliasAnalysis::Location &Loc,
737                             bool isLoad, BasicBlock *StartBB,
738                             SmallVectorImpl<NonLocalDepResult> &Result,
739                             DenseMap<BasicBlock*, Value*> &Visited,
740                             bool SkipFirstBlock) {
741   
742   // Look up the cached info for Pointer.
743   ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
744
745   // Set up a temporary NLPI value. If the map doesn't yet have an entry for
746   // CacheKey, this value will be inserted as the associated value. Otherwise,
747   // it'll be ignored, and we'll have to check to see if the cached size and
748   // tbaa tag are consistent with the current query.
749   NonLocalPointerInfo InitialNLPI;
750   InitialNLPI.Size = Loc.Size;
751   InitialNLPI.TBAATag = Loc.TBAATag;
752
753   // Get the NLPI for CacheKey, inserting one into the map if it doesn't
754   // already have one.
755   std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair = 
756     NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
757   NonLocalPointerInfo *CacheInfo = &Pair.first->second;
758
759   if (!Pair.second) {
760     // If this query's Size is inconsistent with the cached one, take the
761     // maximum size and restart the query.
762     if (CacheInfo->Size != Loc.Size) {
763       CacheInfo->Size = std::max(CacheInfo->Size, Loc.Size);
764       return getNonLocalPointerDepFromBB(Pointer,
765                                          Loc.getWithNewSize(CacheInfo->Size),
766                                          isLoad, StartBB, Result, Visited,
767                                          SkipFirstBlock);
768     }
769
770     // If this query's TBAATag is inconsistent with the cached one, discard the
771     // tag and restart the query.
772     if (CacheInfo->TBAATag != Loc.TBAATag) {
773       CacheInfo->TBAATag = 0;
774       return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutTBAATag(),
775                                          isLoad, StartBB, Result, Visited,
776                                          SkipFirstBlock);
777     }
778   }
779
780   NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps;
781
782   // If we have valid cached information for exactly the block we are
783   // investigating, just return it with no recomputation.
784   if (CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
785     // We have a fully cached result for this query then we can just return the
786     // cached results and populate the visited set.  However, we have to verify
787     // that we don't already have conflicting results for these blocks.  Check
788     // to ensure that if a block in the results set is in the visited set that
789     // it was for the same pointer query.
790     if (!Visited.empty()) {
791       for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
792            I != E; ++I) {
793         DenseMap<BasicBlock*, Value*>::iterator VI = Visited.find(I->getBB());
794         if (VI == Visited.end() || VI->second == Pointer.getAddr())
795           continue;
796         
797         // We have a pointer mismatch in a block.  Just return clobber, saying
798         // that something was clobbered in this result.  We could also do a
799         // non-fully cached query, but there is little point in doing this.
800         return true;
801       }
802     }
803     
804     Value *Addr = Pointer.getAddr();
805     for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
806          I != E; ++I) {
807       Visited.insert(std::make_pair(I->getBB(), Addr));
808       if (!I->getResult().isNonLocal())
809         Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr));
810     }
811     ++NumCacheCompleteNonLocalPtr;
812     return false;
813   }
814   
815   // Otherwise, either this is a new block, a block with an invalid cache
816   // pointer or one that we're about to invalidate by putting more info into it
817   // than its valid cache info.  If empty, the result will be valid cache info,
818   // otherwise it isn't.
819   if (Cache->empty())
820     CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
821   else {
822     CacheInfo->Pair = BBSkipFirstBlockPair();
823     CacheInfo->Size = 0;
824     CacheInfo->TBAATag = 0;
825   }
826   
827   SmallVector<BasicBlock*, 32> Worklist;
828   Worklist.push_back(StartBB);
829   
830   // Keep track of the entries that we know are sorted.  Previously cached
831   // entries will all be sorted.  The entries we add we only sort on demand (we
832   // don't insert every element into its sorted position).  We know that we
833   // won't get any reuse from currently inserted values, because we don't
834   // revisit blocks after we insert info for them.
835   unsigned NumSortedEntries = Cache->size();
836   DEBUG(AssertSorted(*Cache));
837   
838   while (!Worklist.empty()) {
839     BasicBlock *BB = Worklist.pop_back_val();
840     
841     // Skip the first block if we have it.
842     if (!SkipFirstBlock) {
843       // Analyze the dependency of *Pointer in FromBB.  See if we already have
844       // been here.
845       assert(Visited.count(BB) && "Should check 'visited' before adding to WL");
846
847       // Get the dependency info for Pointer in BB.  If we have cached
848       // information, we will use it, otherwise we compute it.
849       DEBUG(AssertSorted(*Cache, NumSortedEntries));
850       MemDepResult Dep = GetNonLocalInfoForBlock(Loc, isLoad, BB, Cache,
851                                                  NumSortedEntries);
852       
853       // If we got a Def or Clobber, add this to the list of results.
854       if (!Dep.isNonLocal()) {
855         Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));
856         continue;
857       }
858     }
859     
860     // If 'Pointer' is an instruction defined in this block, then we need to do
861     // phi translation to change it into a value live in the predecessor block.
862     // If not, we just add the predecessors to the worklist and scan them with
863     // the same Pointer.
864     if (!Pointer.NeedsPHITranslationFromBlock(BB)) {
865       SkipFirstBlock = false;
866       for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
867         // Verify that we haven't looked at this block yet.
868         std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
869           InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr()));
870         if (InsertRes.second) {
871           // First time we've looked at *PI.
872           Worklist.push_back(*PI);
873           continue;
874         }
875         
876         // If we have seen this block before, but it was with a different
877         // pointer then we have a phi translation failure and we have to treat
878         // this as a clobber.
879         if (InsertRes.first->second != Pointer.getAddr())
880           goto PredTranslationFailure;
881       }
882       continue;
883     }
884     
885     // We do need to do phi translation, if we know ahead of time we can't phi
886     // translate this value, don't even try.
887     if (!Pointer.IsPotentiallyPHITranslatable())
888       goto PredTranslationFailure;
889     
890     // We may have added values to the cache list before this PHI translation.
891     // If so, we haven't done anything to ensure that the cache remains sorted.
892     // Sort it now (if needed) so that recursive invocations of
893     // getNonLocalPointerDepFromBB and other routines that could reuse the cache
894     // value will only see properly sorted cache arrays.
895     if (Cache && NumSortedEntries != Cache->size()) {
896       SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
897       NumSortedEntries = Cache->size();
898     }
899     Cache = 0;
900     
901     for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
902       BasicBlock *Pred = *PI;
903       
904       // Get the PHI translated pointer in this predecessor.  This can fail if
905       // not translatable, in which case the getAddr() returns null.
906       PHITransAddr PredPointer(Pointer);
907       PredPointer.PHITranslateValue(BB, Pred, 0);
908
909       Value *PredPtrVal = PredPointer.getAddr();
910       
911       // Check to see if we have already visited this pred block with another
912       // pointer.  If so, we can't do this lookup.  This failure can occur
913       // with PHI translation when a critical edge exists and the PHI node in
914       // the successor translates to a pointer value different than the
915       // pointer the block was first analyzed with.
916       std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
917         InsertRes = Visited.insert(std::make_pair(Pred, PredPtrVal));
918
919       if (!InsertRes.second) {
920         // If the predecessor was visited with PredPtr, then we already did
921         // the analysis and can ignore it.
922         if (InsertRes.first->second == PredPtrVal)
923           continue;
924         
925         // Otherwise, the block was previously analyzed with a different
926         // pointer.  We can't represent the result of this case, so we just
927         // treat this as a phi translation failure.
928         goto PredTranslationFailure;
929       }
930       
931       // If PHI translation was unable to find an available pointer in this
932       // predecessor, then we have to assume that the pointer is clobbered in
933       // that predecessor.  We can still do PRE of the load, which would insert
934       // a computation of the pointer in this predecessor.
935       if (PredPtrVal == 0) {
936         // Add the entry to the Result list.
937         NonLocalDepResult Entry(Pred,
938                                 MemDepResult::getClobber(Pred->getTerminator()),
939                                 PredPtrVal);
940         Result.push_back(Entry);
941
942         // Since we had a phi translation failure, the cache for CacheKey won't
943         // include all of the entries that we need to immediately satisfy future
944         // queries.  Mark this in NonLocalPointerDeps by setting the
945         // BBSkipFirstBlockPair pointer to null.  This requires reuse of the
946         // cached value to do more work but not miss the phi trans failure.
947         NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
948         NLPI.Pair = BBSkipFirstBlockPair();
949         NLPI.Size = 0;
950         NLPI.TBAATag = 0;
951         continue;
952       }
953
954       // FIXME: it is entirely possible that PHI translating will end up with
955       // the same value.  Consider PHI translating something like:
956       // X = phi [x, bb1], [y, bb2].  PHI translating for bb1 doesn't *need*
957       // to recurse here, pedantically speaking.
958       
959       // If we have a problem phi translating, fall through to the code below
960       // to handle the failure condition.
961       if (getNonLocalPointerDepFromBB(PredPointer,
962                                       Loc.getWithNewPtr(PredPointer.getAddr()),
963                                       isLoad, Pred,
964                                       Result, Visited))
965         goto PredTranslationFailure;
966     }
967     
968     // Refresh the CacheInfo/Cache pointer so that it isn't invalidated.
969     CacheInfo = &NonLocalPointerDeps[CacheKey];
970     Cache = &CacheInfo->NonLocalDeps;
971     NumSortedEntries = Cache->size();
972     
973     // Since we did phi translation, the "Cache" set won't contain all of the
974     // results for the query.  This is ok (we can still use it to accelerate
975     // specific block queries) but we can't do the fastpath "return all
976     // results from the set"  Clear out the indicator for this.
977     CacheInfo->Pair = BBSkipFirstBlockPair();
978     CacheInfo->Size = 0;
979     CacheInfo->TBAATag = 0;
980     SkipFirstBlock = false;
981     continue;
982
983   PredTranslationFailure:
984     
985     if (Cache == 0) {
986       // Refresh the CacheInfo/Cache pointer if it got invalidated.
987       CacheInfo = &NonLocalPointerDeps[CacheKey];
988       Cache = &CacheInfo->NonLocalDeps;
989       NumSortedEntries = Cache->size();
990     }
991     
992     // Since we failed phi translation, the "Cache" set won't contain all of the
993     // results for the query.  This is ok (we can still use it to accelerate
994     // specific block queries) but we can't do the fastpath "return all
995     // results from the set".  Clear out the indicator for this.
996     CacheInfo->Pair = BBSkipFirstBlockPair();
997     CacheInfo->Size = 0;
998     CacheInfo->TBAATag = 0;
999     
1000     // If *nothing* works, mark the pointer as being clobbered by the first
1001     // instruction in this block.
1002     //
1003     // If this is the magic first block, return this as a clobber of the whole
1004     // incoming value.  Since we can't phi translate to one of the predecessors,
1005     // we have to bail out.
1006     if (SkipFirstBlock)
1007       return true;
1008     
1009     for (NonLocalDepInfo::reverse_iterator I = Cache->rbegin(); ; ++I) {
1010       assert(I != Cache->rend() && "Didn't find current block??");
1011       if (I->getBB() != BB)
1012         continue;
1013       
1014       assert(I->getResult().isNonLocal() &&
1015              "Should only be here with transparent block");
1016       I->setResult(MemDepResult::getClobber(BB->begin()));
1017       ReverseNonLocalPtrDeps[BB->begin()].insert(CacheKey);
1018       Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(),
1019                                          Pointer.getAddr()));
1020       break;
1021     }
1022   }
1023
1024   // Okay, we're done now.  If we added new values to the cache, re-sort it.
1025   SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
1026   DEBUG(AssertSorted(*Cache));
1027   return false;
1028 }
1029
1030 /// RemoveCachedNonLocalPointerDependencies - If P exists in
1031 /// CachedNonLocalPointerInfo, remove it.
1032 void MemoryDependenceAnalysis::
1033 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) {
1034   CachedNonLocalPointerInfo::iterator It = 
1035     NonLocalPointerDeps.find(P);
1036   if (It == NonLocalPointerDeps.end()) return;
1037   
1038   // Remove all of the entries in the BB->val map.  This involves removing
1039   // instructions from the reverse map.
1040   NonLocalDepInfo &PInfo = It->second.NonLocalDeps;
1041   
1042   for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
1043     Instruction *Target = PInfo[i].getResult().getInst();
1044     if (Target == 0) continue;  // Ignore non-local dep results.
1045     assert(Target->getParent() == PInfo[i].getBB());
1046     
1047     // Eliminating the dirty entry from 'Cache', so update the reverse info.
1048     RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P);
1049   }
1050   
1051   // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
1052   NonLocalPointerDeps.erase(It);
1053 }
1054
1055
1056 /// invalidateCachedPointerInfo - This method is used to invalidate cached
1057 /// information about the specified pointer, because it may be too
1058 /// conservative in memdep.  This is an optional call that can be used when
1059 /// the client detects an equivalence between the pointer and some other
1060 /// value and replaces the other value with ptr. This can make Ptr available
1061 /// in more places that cached info does not necessarily keep.
1062 void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) {
1063   // If Ptr isn't really a pointer, just ignore it.
1064   if (!Ptr->getType()->isPointerTy()) return;
1065   // Flush store info for the pointer.
1066   RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false));
1067   // Flush load info for the pointer.
1068   RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
1069 }
1070
1071 /// invalidateCachedPredecessors - Clear the PredIteratorCache info.
1072 /// This needs to be done when the CFG changes, e.g., due to splitting
1073 /// critical edges.
1074 void MemoryDependenceAnalysis::invalidateCachedPredecessors() {
1075   PredCache->clear();
1076 }
1077
1078 /// removeInstruction - Remove an instruction from the dependence analysis,
1079 /// updating the dependence of instructions that previously depended on it.
1080 /// This method attempts to keep the cache coherent using the reverse map.
1081 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
1082   // Walk through the Non-local dependencies, removing this one as the value
1083   // for any cached queries.
1084   NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
1085   if (NLDI != NonLocalDeps.end()) {
1086     NonLocalDepInfo &BlockMap = NLDI->second.first;
1087     for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end();
1088          DI != DE; ++DI)
1089       if (Instruction *Inst = DI->getResult().getInst())
1090         RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
1091     NonLocalDeps.erase(NLDI);
1092   }
1093
1094   // If we have a cached local dependence query for this instruction, remove it.
1095   //
1096   LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
1097   if (LocalDepEntry != LocalDeps.end()) {
1098     // Remove us from DepInst's reverse set now that the local dep info is gone.
1099     if (Instruction *Inst = LocalDepEntry->second.getInst())
1100       RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
1101
1102     // Remove this local dependency info.
1103     LocalDeps.erase(LocalDepEntry);
1104   }
1105   
1106   // If we have any cached pointer dependencies on this instruction, remove
1107   // them.  If the instruction has non-pointer type, then it can't be a pointer
1108   // base.
1109   
1110   // Remove it from both the load info and the store info.  The instruction
1111   // can't be in either of these maps if it is non-pointer.
1112   if (RemInst->getType()->isPointerTy()) {
1113     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
1114     RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
1115   }
1116   
1117   // Loop over all of the things that depend on the instruction we're removing.
1118   // 
1119   SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd;
1120
1121   // If we find RemInst as a clobber or Def in any of the maps for other values,
1122   // we need to replace its entry with a dirty version of the instruction after
1123   // it.  If RemInst is a terminator, we use a null dirty value.
1124   //
1125   // Using a dirty version of the instruction after RemInst saves having to scan
1126   // the entire block to get to this point.
1127   MemDepResult NewDirtyVal;
1128   if (!RemInst->isTerminator())
1129     NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst));
1130   
1131   ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
1132   if (ReverseDepIt != ReverseLocalDeps.end()) {
1133     SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
1134     // RemInst can't be the terminator if it has local stuff depending on it.
1135     assert(!ReverseDeps.empty() && !isa<TerminatorInst>(RemInst) &&
1136            "Nothing can locally depend on a terminator");
1137     
1138     for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
1139          E = ReverseDeps.end(); I != E; ++I) {
1140       Instruction *InstDependingOnRemInst = *I;
1141       assert(InstDependingOnRemInst != RemInst &&
1142              "Already removed our local dep info");
1143                         
1144       LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
1145       
1146       // Make sure to remember that new things depend on NewDepInst.
1147       assert(NewDirtyVal.getInst() && "There is no way something else can have "
1148              "a local dep on this if it is a terminator!");
1149       ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(), 
1150                                                 InstDependingOnRemInst));
1151     }
1152     
1153     ReverseLocalDeps.erase(ReverseDepIt);
1154
1155     // Add new reverse deps after scanning the set, to avoid invalidating the
1156     // 'ReverseDeps' reference.
1157     while (!ReverseDepsToAdd.empty()) {
1158       ReverseLocalDeps[ReverseDepsToAdd.back().first]
1159         .insert(ReverseDepsToAdd.back().second);
1160       ReverseDepsToAdd.pop_back();
1161     }
1162   }
1163   
1164   ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
1165   if (ReverseDepIt != ReverseNonLocalDeps.end()) {
1166     SmallPtrSet<Instruction*, 4> &Set = ReverseDepIt->second;
1167     for (SmallPtrSet<Instruction*, 4>::iterator I = Set.begin(), E = Set.end();
1168          I != E; ++I) {
1169       assert(*I != RemInst && "Already removed NonLocalDep info for RemInst");
1170       
1171       PerInstNLInfo &INLD = NonLocalDeps[*I];
1172       // The information is now dirty!
1173       INLD.second = true;
1174       
1175       for (NonLocalDepInfo::iterator DI = INLD.first.begin(), 
1176            DE = INLD.first.end(); DI != DE; ++DI) {
1177         if (DI->getResult().getInst() != RemInst) continue;
1178         
1179         // Convert to a dirty entry for the subsequent instruction.
1180         DI->setResult(NewDirtyVal);
1181         
1182         if (Instruction *NextI = NewDirtyVal.getInst())
1183           ReverseDepsToAdd.push_back(std::make_pair(NextI, *I));
1184       }
1185     }
1186
1187     ReverseNonLocalDeps.erase(ReverseDepIt);
1188
1189     // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
1190     while (!ReverseDepsToAdd.empty()) {
1191       ReverseNonLocalDeps[ReverseDepsToAdd.back().first]
1192         .insert(ReverseDepsToAdd.back().second);
1193       ReverseDepsToAdd.pop_back();
1194     }
1195   }
1196   
1197   // If the instruction is in ReverseNonLocalPtrDeps then it appears as a
1198   // value in the NonLocalPointerDeps info.
1199   ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
1200     ReverseNonLocalPtrDeps.find(RemInst);
1201   if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
1202     SmallPtrSet<ValueIsLoadPair, 4> &Set = ReversePtrDepIt->second;
1203     SmallVector<std::pair<Instruction*, ValueIsLoadPair>,8> ReversePtrDepsToAdd;
1204     
1205     for (SmallPtrSet<ValueIsLoadPair, 4>::iterator I = Set.begin(),
1206          E = Set.end(); I != E; ++I) {
1207       ValueIsLoadPair P = *I;
1208       assert(P.getPointer() != RemInst &&
1209              "Already removed NonLocalPointerDeps info for RemInst");
1210       
1211       NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].NonLocalDeps;
1212       
1213       // The cache is not valid for any specific block anymore.
1214       NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair();
1215       NonLocalPointerDeps[P].Size = 0;
1216       NonLocalPointerDeps[P].TBAATag = 0;
1217       
1218       // Update any entries for RemInst to use the instruction after it.
1219       for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();
1220            DI != DE; ++DI) {
1221         if (DI->getResult().getInst() != RemInst) continue;
1222         
1223         // Convert to a dirty entry for the subsequent instruction.
1224         DI->setResult(NewDirtyVal);
1225         
1226         if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
1227           ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
1228       }
1229       
1230       // Re-sort the NonLocalDepInfo.  Changing the dirty entry to its
1231       // subsequent value may invalidate the sortedness.
1232       std::sort(NLPDI.begin(), NLPDI.end());
1233     }
1234     
1235     ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
1236     
1237     while (!ReversePtrDepsToAdd.empty()) {
1238       ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first]
1239         .insert(ReversePtrDepsToAdd.back().second);
1240       ReversePtrDepsToAdd.pop_back();
1241     }
1242   }
1243   
1244   
1245   assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
1246   AA->deleteValue(RemInst);
1247   DEBUG(verifyRemoved(RemInst));
1248 }
1249 /// verifyRemoved - Verify that the specified instruction does not occur
1250 /// in our internal data structures.
1251 void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
1252   for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
1253        E = LocalDeps.end(); I != E; ++I) {
1254     assert(I->first != D && "Inst occurs in data structures");
1255     assert(I->second.getInst() != D &&
1256            "Inst occurs in data structures");
1257   }
1258   
1259   for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(),
1260        E = NonLocalPointerDeps.end(); I != E; ++I) {
1261     assert(I->first.getPointer() != D && "Inst occurs in NLPD map key");
1262     const NonLocalDepInfo &Val = I->second.NonLocalDeps;
1263     for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end();
1264          II != E; ++II)
1265       assert(II->getResult().getInst() != D && "Inst occurs as NLPD value");
1266   }
1267   
1268   for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(),
1269        E = NonLocalDeps.end(); I != E; ++I) {
1270     assert(I->first != D && "Inst occurs in data structures");
1271     const PerInstNLInfo &INLD = I->second;
1272     for (NonLocalDepInfo::const_iterator II = INLD.first.begin(),
1273          EE = INLD.first.end(); II  != EE; ++II)
1274       assert(II->getResult().getInst() != D && "Inst occurs in data structures");
1275   }
1276   
1277   for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),
1278        E = ReverseLocalDeps.end(); I != E; ++I) {
1279     assert(I->first != D && "Inst occurs in data structures");
1280     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
1281          EE = I->second.end(); II != EE; ++II)
1282       assert(*II != D && "Inst occurs in data structures");
1283   }
1284   
1285   for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(),
1286        E = ReverseNonLocalDeps.end();
1287        I != E; ++I) {
1288     assert(I->first != D && "Inst occurs in data structures");
1289     for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
1290          EE = I->second.end(); II != EE; ++II)
1291       assert(*II != D && "Inst occurs in data structures");
1292   }
1293   
1294   for (ReverseNonLocalPtrDepTy::const_iterator
1295        I = ReverseNonLocalPtrDeps.begin(),
1296        E = ReverseNonLocalPtrDeps.end(); I != E; ++I) {
1297     assert(I->first != D && "Inst occurs in rev NLPD map");
1298     
1299     for (SmallPtrSet<ValueIsLoadPair, 4>::const_iterator II = I->second.begin(),
1300          E = I->second.end(); II != E; ++II)
1301       assert(*II != ValueIsLoadPair(D, false) &&
1302              *II != ValueIsLoadPair(D, true) &&
1303              "Inst occurs in ReverseNonLocalPtrDeps map");
1304   }
1305   
1306 }