1 //===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
15 //===----------------------------------------------------------------------===//
17 #define DEBUG_TYPE "memdep"
18 #include "llvm/Analysis/MemoryDependenceAnalysis.h"
19 #include "llvm/Constants.h"
20 #include "llvm/Instructions.h"
21 #include "llvm/Function.h"
22 #include "llvm/Analysis/AliasAnalysis.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Support/CFG.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Target/TargetData.h"
29 STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");
30 STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");
31 STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");
33 STATISTIC(NumCacheNonLocalPtr,
34 "Number of fully cached non-local ptr responses");
35 STATISTIC(NumCacheDirtyNonLocalPtr,
36 "Number of cached, but dirty, non-local ptr responses");
37 STATISTIC(NumUncacheNonLocalPtr,
38 "Number of uncached non-local ptr responses");
40 char MemoryDependenceAnalysis::ID = 0;
42 // Register this pass...
43 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
44 "Memory Dependence Analysis", false, true);
46 /// getAnalysisUsage - Does not modify anything. It uses Alias Analysis.
48 void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
50 AU.addRequiredTransitive<AliasAnalysis>();
51 AU.addRequiredTransitive<TargetData>();
54 bool MemoryDependenceAnalysis::runOnFunction(Function &) {
55 AA = &getAnalysis<AliasAnalysis>();
56 TD = &getAnalysis<TargetData>();
60 /// RemoveFromReverseMap - This is a helper function that removes Val from
61 /// 'Inst's set in ReverseMap. If the set becomes empty, remove Inst's entry.
62 template <typename KeyTy>
63 static void RemoveFromReverseMap(DenseMap<Instruction*,
64 SmallPtrSet<KeyTy*, 4> > &ReverseMap,
65 Instruction *Inst, KeyTy *Val) {
66 typename DenseMap<Instruction*, SmallPtrSet<KeyTy*, 4> >::iterator
67 InstIt = ReverseMap.find(Inst);
68 assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
69 bool Found = InstIt->second.erase(Val);
70 assert(Found && "Invalid reverse map!"); Found=Found;
71 if (InstIt->second.empty())
72 ReverseMap.erase(InstIt);
76 /// getCallSiteDependencyFrom - Private helper for finding the local
77 /// dependencies of a call site.
78 MemDepResult MemoryDependenceAnalysis::
79 getCallSiteDependencyFrom(CallSite CS, BasicBlock::iterator ScanIt,
81 // Walk backwards through the block, looking for dependencies
82 while (ScanIt != BB->begin()) {
83 Instruction *Inst = --ScanIt;
85 // If this inst is a memory op, get the pointer it accessed
87 uint64_t PointerSize = 0;
88 if (StoreInst *S = dyn_cast<StoreInst>(Inst)) {
89 Pointer = S->getPointerOperand();
90 PointerSize = TD->getTypeStoreSize(S->getOperand(0)->getType());
91 } else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
92 Pointer = V->getOperand(0);
93 PointerSize = TD->getTypeStoreSize(V->getType());
94 } else if (FreeInst *F = dyn_cast<FreeInst>(Inst)) {
95 Pointer = F->getPointerOperand();
97 // FreeInsts erase the entire structure
99 } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
100 CallSite InstCS = CallSite::get(Inst);
101 // If these two calls do not interfere, look past it.
102 if (AA->getModRefInfo(CS, InstCS) == AliasAnalysis::NoModRef)
105 // FIXME: If this is a ref/ref result, we should ignore it!
108 // Z = strlen(P); // Z = X
110 // If they interfere, we generally return clobber. However, if they are
111 // calls to the same read-only functions we return Def.
112 if (!AA->onlyReadsMemory(CS) || CS.getCalledFunction() == 0 ||
113 CS.getCalledFunction() != InstCS.getCalledFunction())
114 return MemDepResult::getClobber(Inst);
115 return MemDepResult::getDef(Inst);
117 // Non-memory instruction.
121 if (AA->getModRefInfo(CS, Pointer, PointerSize) != AliasAnalysis::NoModRef)
122 return MemDepResult::getClobber(Inst);
125 // No dependence found. If this is the entry block of the function, it is a
126 // clobber, otherwise it is non-local.
127 if (BB != &BB->getParent()->getEntryBlock())
128 return MemDepResult::getNonLocal();
129 return MemDepResult::getClobber(ScanIt);
132 /// getPointerDependencyFrom - Return the instruction on which a memory
133 /// location depends. If isLoad is true, this routine ignore may-aliases with
134 /// read-only operations.
135 MemDepResult MemoryDependenceAnalysis::
136 getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad,
137 BasicBlock::iterator ScanIt, BasicBlock *BB) {
139 // Walk backwards through the basic block, looking for dependencies.
140 while (ScanIt != BB->begin()) {
141 Instruction *Inst = --ScanIt;
143 // Values depend on loads if the pointers are must aliased. This means that
144 // a load depends on another must aliased load from the same value.
145 if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
146 Value *Pointer = LI->getPointerOperand();
147 uint64_t PointerSize = TD->getTypeStoreSize(LI->getType());
149 // If we found a pointer, check if it could be the same as our pointer.
150 AliasAnalysis::AliasResult R =
151 AA->alias(Pointer, PointerSize, MemPtr, MemSize);
152 if (R == AliasAnalysis::NoAlias)
155 // May-alias loads don't depend on each other without a dependence.
156 if (isLoad && R == AliasAnalysis::MayAlias)
158 // Stores depend on may and must aliased loads, loads depend on must-alias
160 return MemDepResult::getDef(Inst);
163 if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
164 Value *Pointer = SI->getPointerOperand();
165 uint64_t PointerSize = TD->getTypeStoreSize(SI->getOperand(0)->getType());
167 // If we found a pointer, check if it could be the same as our pointer.
168 AliasAnalysis::AliasResult R =
169 AA->alias(Pointer, PointerSize, MemPtr, MemSize);
171 if (R == AliasAnalysis::NoAlias)
173 if (R == AliasAnalysis::MayAlias)
174 return MemDepResult::getClobber(Inst);
175 return MemDepResult::getDef(Inst);
178 // If this is an allocation, and if we know that the accessed pointer is to
179 // the allocation, return Def. This means that there is no dependence and
180 // the access can be optimized based on that. For example, a load could
182 if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
183 Value *AccessPtr = MemPtr->getUnderlyingObject();
185 if (AccessPtr == AI ||
186 AA->alias(AI, 1, AccessPtr, 1) == AliasAnalysis::MustAlias)
187 return MemDepResult::getDef(AI);
191 // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer.
192 // FIXME: If this is a load, we should ignore readonly calls!
193 if (AA->getModRefInfo(Inst, MemPtr, MemSize) == AliasAnalysis::NoModRef)
196 // Otherwise, there is a dependence.
197 return MemDepResult::getClobber(Inst);
200 // No dependence found. If this is the entry block of the function, it is a
201 // clobber, otherwise it is non-local.
202 if (BB != &BB->getParent()->getEntryBlock())
203 return MemDepResult::getNonLocal();
204 return MemDepResult::getClobber(ScanIt);
207 /// getDependency - Return the instruction on which a memory operation
209 MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
210 Instruction *ScanPos = QueryInst;
212 // Check for a cached result
213 MemDepResult &LocalCache = LocalDeps[QueryInst];
215 // If the cached entry is non-dirty, just return it. Note that this depends
216 // on MemDepResult's default constructing to 'dirty'.
217 if (!LocalCache.isDirty())
220 // Otherwise, if we have a dirty entry, we know we can start the scan at that
221 // instruction, which may save us some work.
222 if (Instruction *Inst = LocalCache.getInst()) {
225 RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
228 BasicBlock *QueryParent = QueryInst->getParent();
231 uint64_t MemSize = 0;
234 if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
235 // No dependence found. If this is the entry block of the function, it is a
236 // clobber, otherwise it is non-local.
237 if (QueryParent != &QueryParent->getParent()->getEntryBlock())
238 LocalCache = MemDepResult::getNonLocal();
240 LocalCache = MemDepResult::getClobber(QueryInst);
241 } else if (StoreInst *SI = dyn_cast<StoreInst>(QueryInst)) {
242 // If this is a volatile store, don't mess around with it. Just return the
243 // previous instruction as a clobber.
244 if (SI->isVolatile())
245 LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
247 MemPtr = SI->getPointerOperand();
248 MemSize = TD->getTypeStoreSize(SI->getOperand(0)->getType());
250 } else if (LoadInst *LI = dyn_cast<LoadInst>(QueryInst)) {
251 // If this is a volatile load, don't mess around with it. Just return the
252 // previous instruction as a clobber.
253 if (LI->isVolatile())
254 LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
256 MemPtr = LI->getPointerOperand();
257 MemSize = TD->getTypeStoreSize(LI->getType());
259 } else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
260 LocalCache = getCallSiteDependencyFrom(CallSite::get(QueryInst), ScanPos,
262 } else if (FreeInst *FI = dyn_cast<FreeInst>(QueryInst)) {
263 MemPtr = FI->getPointerOperand();
264 // FreeInsts erase the entire structure, not just a field.
267 // Non-memory instruction.
268 LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
271 // If we need to do a pointer scan, make it happen.
273 LocalCache = getPointerDependencyFrom(MemPtr, MemSize,
274 isa<LoadInst>(QueryInst),
275 ScanPos, QueryParent);
277 // Remember the result!
278 if (Instruction *I = LocalCache.getInst())
279 ReverseLocalDeps[I].insert(QueryInst);
284 /// getNonLocalDependency - Perform a full dependency query for the
285 /// specified instruction, returning the set of blocks that the value is
286 /// potentially live across. The returned set of results will include a
287 /// "NonLocal" result for all blocks where the value is live across.
289 /// This method assumes the instruction returns a "nonlocal" dependency
290 /// within its own block.
292 const MemoryDependenceAnalysis::NonLocalDepInfo &
293 MemoryDependenceAnalysis::getNonLocalDependency(Instruction *QueryInst) {
294 // FIXME: Make this only be for callsites in the future.
295 assert(isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst) ||
296 isa<LoadInst>(QueryInst) || isa<StoreInst>(QueryInst));
297 assert(getDependency(QueryInst).isNonLocal() &&
298 "getNonLocalDependency should only be used on insts with non-local deps!");
299 PerInstNLInfo &CacheP = NonLocalDeps[QueryInst];
300 NonLocalDepInfo &Cache = CacheP.first;
302 /// DirtyBlocks - This is the set of blocks that need to be recomputed. In
303 /// the cached case, this can happen due to instructions being deleted etc. In
304 /// the uncached case, this starts out as the set of predecessors we care
306 SmallVector<BasicBlock*, 32> DirtyBlocks;
308 if (!Cache.empty()) {
309 // Okay, we have a cache entry. If we know it is not dirty, just return it
310 // with no computation.
311 if (!CacheP.second) {
316 // If we already have a partially computed set of results, scan them to
317 // determine what is dirty, seeding our initial DirtyBlocks worklist.
318 for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end();
320 if (I->second.isDirty())
321 DirtyBlocks.push_back(I->first);
323 // Sort the cache so that we can do fast binary search lookups below.
324 std::sort(Cache.begin(), Cache.end());
326 ++NumCacheDirtyNonLocal;
327 //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: "
328 // << Cache.size() << " cached: " << *QueryInst;
330 // Seed DirtyBlocks with each of the preds of QueryInst's block.
331 BasicBlock *QueryBB = QueryInst->getParent();
332 DirtyBlocks.append(pred_begin(QueryBB), pred_end(QueryBB));
333 NumUncacheNonLocal++;
336 // Visited checked first, vector in sorted order.
337 SmallPtrSet<BasicBlock*, 64> Visited;
339 unsigned NumSortedEntries = Cache.size();
341 // Iterate while we still have blocks to update.
342 while (!DirtyBlocks.empty()) {
343 BasicBlock *DirtyBB = DirtyBlocks.back();
344 DirtyBlocks.pop_back();
346 // Already processed this block?
347 if (!Visited.insert(DirtyBB))
350 // Do a binary search to see if we already have an entry for this block in
351 // the cache set. If so, find it.
352 NonLocalDepInfo::iterator Entry =
353 std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries,
354 std::make_pair(DirtyBB, MemDepResult()));
355 if (Entry != Cache.begin() && (&*Entry)[-1].first == DirtyBB)
358 MemDepResult *ExistingResult = 0;
359 if (Entry != Cache.begin()+NumSortedEntries &&
360 Entry->first == DirtyBB) {
361 // If we already have an entry, and if it isn't already dirty, the block
363 if (!Entry->second.isDirty())
366 // Otherwise, remember this slot so we can update the value.
367 ExistingResult = &Entry->second;
370 // If the dirty entry has a pointer, start scanning from it so we don't have
371 // to rescan the entire block.
372 BasicBlock::iterator ScanPos = DirtyBB->end();
373 if (ExistingResult) {
374 if (Instruction *Inst = ExistingResult->getInst()) {
376 // We're removing QueryInst's use of Inst.
377 RemoveFromReverseMap(ReverseNonLocalDeps, Inst, QueryInst);
381 // Find out if this block has a local dependency for QueryInst.
385 uint64_t MemSize = 0;
387 if (ScanPos == DirtyBB->begin()) {
388 // No dependence found. If this is the entry block of the function, it is a
389 // clobber, otherwise it is non-local.
390 if (DirtyBB != &DirtyBB->getParent()->getEntryBlock())
391 Dep = MemDepResult::getNonLocal();
393 Dep = MemDepResult::getClobber(ScanPos);
394 } else if (StoreInst *SI = dyn_cast<StoreInst>(QueryInst)) {
395 // If this is a volatile store, don't mess around with it. Just return the
396 // previous instruction as a clobber.
397 if (SI->isVolatile())
398 Dep = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
400 MemPtr = SI->getPointerOperand();
401 MemSize = TD->getTypeStoreSize(SI->getOperand(0)->getType());
403 } else if (LoadInst *LI = dyn_cast<LoadInst>(QueryInst)) {
404 // If this is a volatile load, don't mess around with it. Just return the
405 // previous instruction as a clobber.
406 if (LI->isVolatile())
407 Dep = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
409 MemPtr = LI->getPointerOperand();
410 MemSize = TD->getTypeStoreSize(LI->getType());
413 assert(isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst));
414 Dep = getCallSiteDependencyFrom(CallSite::get(QueryInst), ScanPos,
419 Dep = getPointerDependencyFrom(MemPtr, MemSize, isa<LoadInst>(QueryInst),
422 // If we had a dirty entry for the block, update it. Otherwise, just add
425 *ExistingResult = Dep;
427 Cache.push_back(std::make_pair(DirtyBB, Dep));
429 // If the block has a dependency (i.e. it isn't completely transparent to
430 // the value), remember the association!
431 if (!Dep.isNonLocal()) {
432 // Keep the ReverseNonLocalDeps map up to date so we can efficiently
433 // update this when we remove instructions.
434 if (Instruction *Inst = Dep.getInst())
435 ReverseNonLocalDeps[Inst].insert(QueryInst);
438 // If the block *is* completely transparent to the load, we need to check
439 // the predecessors of this block. Add them to our worklist.
440 DirtyBlocks.append(pred_begin(DirtyBB), pred_end(DirtyBB));
447 /// getNonLocalPointerDependency - Perform a full dependency query for an
448 /// access to the specified (non-volatile) memory location, returning the
449 /// set of instructions that either define or clobber the value.
451 /// This method assumes the pointer has a "NonLocal" dependency within its
454 void MemoryDependenceAnalysis::
455 getNonLocalPointerDependency(Value *Pointer, bool isLoad, BasicBlock *FromBB,
456 SmallVectorImpl<NonLocalDepEntry> &Result) {
457 assert(isa<PointerType>(Pointer->getType()) &&
458 "Can't get pointer deps of a non-pointer!");
461 // We know that the pointer value is live into FromBB find the def/clobbers
462 // from presecessors.
463 const Type *EltTy = cast<PointerType>(Pointer->getType())->getElementType();
464 uint64_t PointeeSize = TD->getTypeStoreSize(EltTy);
466 // While we have blocks to analyze, get their values.
467 SmallPtrSet<BasicBlock*, 64> Visited;
469 for (pred_iterator PI = pred_begin(FromBB), E = pred_end(FromBB); PI != E;
471 // TODO: PHI TRANSLATE.
472 getNonLocalPointerDepInternal(Pointer, PointeeSize, isLoad, *PI,
477 void MemoryDependenceAnalysis::
478 getNonLocalPointerDepInternal(Value *Pointer, uint64_t PointeeSize,
479 bool isLoad, BasicBlock *StartBB,
480 SmallVectorImpl<NonLocalDepEntry> &Result,
481 SmallPtrSet<BasicBlock*, 64> &Visited) {
482 SmallVector<BasicBlock*, 32> Worklist;
483 Worklist.push_back(StartBB);
485 // Look up the cached info for Pointer.
486 ValueIsLoadPair CacheKey(Pointer, isLoad);
487 NonLocalDepInfo *Cache = &NonLocalPointerDeps[CacheKey];
489 // Keep track of the entries that we know are sorted. Previously cached
490 // entries will all be sorted. The entries we add we only sort on demand (we
491 // don't insert every element into its sorted position). We know that we
492 // won't get any reuse from currently inserted values, because we don't
493 // revisit blocks after we insert info for them.
494 unsigned NumSortedEntries = Cache->size();
496 while (!Worklist.empty()) {
497 BasicBlock *BB = Worklist.pop_back_val();
499 // Analyze the dependency of *Pointer in FromBB. See if we already have
501 if (!Visited.insert(BB))
504 // Get the dependency info for Pointer in BB. If we have cached
505 // information, we will use it, otherwise we compute it.
507 // Do a binary search to see if we already have an entry for this block in
508 // the cache set. If so, find it.
509 NonLocalDepInfo::iterator Entry =
510 std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
511 std::make_pair(BB, MemDepResult()));
512 if (Entry != Cache->begin() && (&*Entry)[-1].first == BB)
515 MemDepResult *ExistingResult = 0;
516 if (Entry != Cache->begin()+NumSortedEntries && Entry->first == BB)
517 ExistingResult = &Entry->second;
519 // If we have a cached entry, and it is non-dirty, use it as the value for
522 if (ExistingResult && !ExistingResult->isDirty()) {
523 Dep = *ExistingResult;
524 ++NumCacheNonLocalPtr;
526 // Otherwise, we have to scan for the value. If we have a dirty cache
527 // entry, start scanning from its position, otherwise we scan from the end
529 BasicBlock::iterator ScanPos = BB->end();
530 if (ExistingResult && ExistingResult->getInst()) {
531 assert(ExistingResult->getInst()->getParent() == BB &&
532 "Instruction invalidated?");
533 ++NumCacheDirtyNonLocalPtr;
534 ScanPos = ExistingResult->getInst();
536 // Eliminating the dirty entry from 'Cache', so update the reverse info.
537 RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos,
538 CacheKey.getOpaqueValue());
540 ++NumUncacheNonLocalPtr;
543 // Scan the block for the dependency.
544 Dep = getPointerDependencyFrom(Pointer, PointeeSize, isLoad, ScanPos, BB);
546 // If we had a dirty entry for the block, update it. Otherwise, just add
549 *ExistingResult = Dep;
551 Cache->push_back(std::make_pair(BB, Dep));
553 // If the block has a dependency (i.e. it isn't completely transparent to
554 // the value), remember the reverse association because we just added it
556 if (!Dep.isNonLocal()) {
557 // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
558 // update MemDep when we remove instructions.
559 Instruction *Inst = Dep.getInst();
560 assert(Inst && "Didn't depend on anything?");
561 ReverseNonLocalPtrDeps[Inst].insert(CacheKey.getOpaqueValue());
565 // If we got a Def or Clobber, add this to the list of results.
566 if (!Dep.isNonLocal()) {
567 Result.push_back(NonLocalDepEntry(BB, Dep));
571 // Otherwise, we have to process all the predecessors of this block to scan
573 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
574 // TODO: PHI TRANSLATE.
575 Worklist.push_back(*PI);
579 // If we computed new values, re-sort Cache.
580 if (NumSortedEntries != Cache->size())
581 std::sort(Cache->begin(), Cache->end());
584 /// RemoveCachedNonLocalPointerDependencies - If P exists in
585 /// CachedNonLocalPointerInfo, remove it.
586 void MemoryDependenceAnalysis::
587 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) {
588 CachedNonLocalPointerInfo::iterator It =
589 NonLocalPointerDeps.find(P);
590 if (It == NonLocalPointerDeps.end()) return;
592 // Remove all of the entries in the BB->val map. This involves removing
593 // instructions from the reverse map.
594 NonLocalDepInfo &PInfo = It->second;
596 for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
597 Instruction *Target = PInfo[i].second.getInst();
598 if (Target == 0) continue; // Ignore non-local dep results.
599 assert(Target->getParent() == PInfo[i].first && Target != P.getPointer());
601 // Eliminating the dirty entry from 'Cache', so update the reverse info.
602 RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P.getOpaqueValue());
605 // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
606 NonLocalPointerDeps.erase(It);
610 /// removeInstruction - Remove an instruction from the dependence analysis,
611 /// updating the dependence of instructions that previously depended on it.
612 /// This method attempts to keep the cache coherent using the reverse map.
613 void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
614 // Walk through the Non-local dependencies, removing this one as the value
615 // for any cached queries.
616 NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
617 if (NLDI != NonLocalDeps.end()) {
618 NonLocalDepInfo &BlockMap = NLDI->second.first;
619 for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end();
621 if (Instruction *Inst = DI->second.getInst())
622 RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
623 NonLocalDeps.erase(NLDI);
626 // If we have a cached local dependence query for this instruction, remove it.
628 LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
629 if (LocalDepEntry != LocalDeps.end()) {
630 // Remove us from DepInst's reverse set now that the local dep info is gone.
631 if (Instruction *Inst = LocalDepEntry->second.getInst())
632 RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
634 // Remove this local dependency info.
635 LocalDeps.erase(LocalDepEntry);
638 // If we have any cached pointer dependencies on this instruction, remove
639 // them. If the instruction has non-pointer type, then it can't be a pointer
642 // Remove it from both the load info and the store info. The instruction
643 // can't be in either of these maps if it is non-pointer.
644 if (isa<PointerType>(RemInst->getType())) {
645 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
646 RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
649 // Loop over all of the things that depend on the instruction we're removing.
651 SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd;
653 // If we find RemInst as a clobber or Def in any of the maps for other values,
654 // we need to replace its entry with a dirty version of the instruction after
655 // it. If RemInst is a terminator, we use a null dirty value.
657 // Using a dirty version of the instruction after RemInst saves having to scan
658 // the entire block to get to this point.
659 MemDepResult NewDirtyVal;
660 if (!RemInst->isTerminator())
661 NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst));
663 ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
664 if (ReverseDepIt != ReverseLocalDeps.end()) {
665 SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
666 // RemInst can't be the terminator if it has local stuff depending on it.
667 assert(!ReverseDeps.empty() && !isa<TerminatorInst>(RemInst) &&
668 "Nothing can locally depend on a terminator");
670 for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
671 E = ReverseDeps.end(); I != E; ++I) {
672 Instruction *InstDependingOnRemInst = *I;
673 assert(InstDependingOnRemInst != RemInst &&
674 "Already removed our local dep info");
676 LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
678 // Make sure to remember that new things depend on NewDepInst.
679 assert(NewDirtyVal.getInst() && "There is no way something else can have "
680 "a local dep on this if it is a terminator!");
681 ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(),
682 InstDependingOnRemInst));
685 ReverseLocalDeps.erase(ReverseDepIt);
687 // Add new reverse deps after scanning the set, to avoid invalidating the
688 // 'ReverseDeps' reference.
689 while (!ReverseDepsToAdd.empty()) {
690 ReverseLocalDeps[ReverseDepsToAdd.back().first]
691 .insert(ReverseDepsToAdd.back().second);
692 ReverseDepsToAdd.pop_back();
696 ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
697 if (ReverseDepIt != ReverseNonLocalDeps.end()) {
698 SmallPtrSet<Instruction*, 4> &Set = ReverseDepIt->second;
699 for (SmallPtrSet<Instruction*, 4>::iterator I = Set.begin(), E = Set.end();
701 assert(*I != RemInst && "Already removed NonLocalDep info for RemInst");
703 PerInstNLInfo &INLD = NonLocalDeps[*I];
704 // The information is now dirty!
707 for (NonLocalDepInfo::iterator DI = INLD.first.begin(),
708 DE = INLD.first.end(); DI != DE; ++DI) {
709 if (DI->second.getInst() != RemInst) continue;
711 // Convert to a dirty entry for the subsequent instruction.
712 DI->second = NewDirtyVal;
714 if (Instruction *NextI = NewDirtyVal.getInst())
715 ReverseDepsToAdd.push_back(std::make_pair(NextI, *I));
719 ReverseNonLocalDeps.erase(ReverseDepIt);
721 // Add new reverse deps after scanning the set, to avoid invalidating 'Set'
722 while (!ReverseDepsToAdd.empty()) {
723 ReverseNonLocalDeps[ReverseDepsToAdd.back().first]
724 .insert(ReverseDepsToAdd.back().second);
725 ReverseDepsToAdd.pop_back();
729 // If the instruction is in ReverseNonLocalPtrDeps then it appears as a
730 // value in the NonLocalPointerDeps info.
731 ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
732 ReverseNonLocalPtrDeps.find(RemInst);
733 if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
734 SmallPtrSet<void*, 4> &Set = ReversePtrDepIt->second;
735 SmallVector<std::pair<Instruction*, ValueIsLoadPair>,8> ReversePtrDepsToAdd;
737 for (SmallPtrSet<void*, 4>::iterator I = Set.begin(), E = Set.end();
740 P.setFromOpaqueValue(*I);
741 assert(P.getPointer() != RemInst &&
742 "Already removed NonLocalPointerDeps info for RemInst");
744 NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P];
746 // Update any entries for RemInst to use the instruction after it.
747 for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();
749 if (DI->second.getInst() != RemInst) continue;
751 // Convert to a dirty entry for the subsequent instruction.
752 DI->second = NewDirtyVal;
754 if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
755 ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
759 ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
761 while (!ReversePtrDepsToAdd.empty()) {
762 ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first]
763 .insert(ReversePtrDepsToAdd.back().second.getOpaqueValue());
764 ReversePtrDepsToAdd.pop_back();
769 assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
770 AA->deleteValue(RemInst);
771 DEBUG(verifyRemoved(RemInst));
774 /// verifyRemoved - Verify that the specified instruction does not occur
775 /// in our internal data structures.
776 void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
777 for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
778 E = LocalDeps.end(); I != E; ++I) {
779 assert(I->first != D && "Inst occurs in data structures");
780 assert(I->second.getInst() != D &&
781 "Inst occurs in data structures");
784 for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(),
785 E = NonLocalPointerDeps.end(); I != E; ++I) {
786 assert(I->first.getPointer() != D && "Inst occurs in NLPD map key");
787 const NonLocalDepInfo &Val = I->second;
788 for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end();
790 assert(II->second.getInst() != D && "Inst occurs as NLPD value");
793 for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(),
794 E = NonLocalDeps.end(); I != E; ++I) {
795 assert(I->first != D && "Inst occurs in data structures");
796 const PerInstNLInfo &INLD = I->second;
797 for (NonLocalDepInfo::const_iterator II = INLD.first.begin(),
798 EE = INLD.first.end(); II != EE; ++II)
799 assert(II->second.getInst() != D && "Inst occurs in data structures");
802 for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),
803 E = ReverseLocalDeps.end(); I != E; ++I) {
804 assert(I->first != D && "Inst occurs in data structures");
805 for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
806 EE = I->second.end(); II != EE; ++II)
807 assert(*II != D && "Inst occurs in data structures");
810 for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(),
811 E = ReverseNonLocalDeps.end();
813 assert(I->first != D && "Inst occurs in data structures");
814 for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
815 EE = I->second.end(); II != EE; ++II)
816 assert(*II != D && "Inst occurs in data structures");
819 for (ReverseNonLocalPtrDepTy::const_iterator
820 I = ReverseNonLocalPtrDeps.begin(),
821 E = ReverseNonLocalPtrDeps.end(); I != E; ++I) {
822 assert(I->first != D && "Inst occurs in rev NLPD map");
824 for (SmallPtrSet<void*, 4>::const_iterator II = I->second.begin(),
825 E = I->second.end(); II != E; ++II)
826 assert(*II != ValueIsLoadPair(D, false).getOpaqueValue() &&
827 *II != ValueIsLoadPair(D, true).getOpaqueValue() &&
828 "Inst occurs in ReverseNonLocalPtrDeps map");