MemoryDependenceAnalysis.cpp [plain text]
#define DEBUG_TYPE "memdep"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Function.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/PredIteratorCache.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetData.h"
using namespace llvm;
STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses");
STATISTIC(NumCacheDirtyNonLocal, "Number of dirty cached non-local responses");
STATISTIC(NumUncacheNonLocal, "Number of uncached non-local responses");
STATISTIC(NumCacheNonLocalPtr,
"Number of fully cached non-local ptr responses");
STATISTIC(NumCacheDirtyNonLocalPtr,
"Number of cached, but dirty, non-local ptr responses");
STATISTIC(NumUncacheNonLocalPtr,
"Number of uncached non-local ptr responses");
STATISTIC(NumCacheCompleteNonLocalPtr,
"Number of block queries that were completely cached");
char MemoryDependenceAnalysis::ID = 0;
static RegisterPass<MemoryDependenceAnalysis> X("memdep",
"Memory Dependence Analysis", false, true);
MemoryDependenceAnalysis::MemoryDependenceAnalysis()
: FunctionPass(&ID), PredCache(0) {
}
MemoryDependenceAnalysis::~MemoryDependenceAnalysis() {
}
void MemoryDependenceAnalysis::releaseMemory() {
LocalDeps.clear();
NonLocalDeps.clear();
NonLocalPointerDeps.clear();
ReverseLocalDeps.clear();
ReverseNonLocalDeps.clear();
ReverseNonLocalPtrDeps.clear();
PredCache->clear();
}
void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequiredTransitive<AliasAnalysis>();
AU.addRequiredTransitive<TargetData>();
}
bool MemoryDependenceAnalysis::runOnFunction(Function &) {
AA = &getAnalysis<AliasAnalysis>();
TD = &getAnalysis<TargetData>();
if (PredCache == 0)
PredCache.reset(new PredIteratorCache());
return false;
}
template <typename KeyTy>
static void RemoveFromReverseMap(DenseMap<Instruction*,
SmallPtrSet<KeyTy, 4> > &ReverseMap,
Instruction *Inst, KeyTy Val) {
typename DenseMap<Instruction*, SmallPtrSet<KeyTy, 4> >::iterator
InstIt = ReverseMap.find(Inst);
assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
bool Found = InstIt->second.erase(Val);
assert(Found && "Invalid reverse map!"); Found=Found;
if (InstIt->second.empty())
ReverseMap.erase(InstIt);
}
MemDepResult MemoryDependenceAnalysis::
getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
BasicBlock::iterator ScanIt, BasicBlock *BB) {
while (ScanIt != BB->begin()) {
Instruction *Inst = --ScanIt;
Value *Pointer = 0;
uint64_t PointerSize = 0;
if (StoreInst *S = dyn_cast<StoreInst>(Inst)) {
Pointer = S->getPointerOperand();
PointerSize = TD->getTypeStoreSize(S->getOperand(0)->getType());
} else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
Pointer = V->getOperand(0);
PointerSize = TD->getTypeStoreSize(V->getType());
} else if (FreeInst *F = dyn_cast<FreeInst>(Inst)) {
Pointer = F->getPointerOperand();
PointerSize = ~0ULL;
} else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
if (isa<DbgInfoIntrinsic>(Inst)) continue;
CallSite InstCS = CallSite::get(Inst);
switch (AA->getModRefInfo(CS, InstCS)) {
case AliasAnalysis::NoModRef:
continue;
case AliasAnalysis::Ref:
if (isReadOnlyCall) {
if (CS.getCalledFunction() != 0 &&
CS.getCalledFunction() == InstCS.getCalledFunction())
return MemDepResult::getDef(Inst);
continue;
}
default:
return MemDepResult::getClobber(Inst);
}
} else {
continue;
}
if (AA->getModRefInfo(CS, Pointer, PointerSize) != AliasAnalysis::NoModRef)
return MemDepResult::getClobber(Inst);
}
if (BB != &BB->getParent()->getEntryBlock())
return MemDepResult::getNonLocal();
return MemDepResult::getClobber(ScanIt);
}
MemDepResult MemoryDependenceAnalysis::
getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad,
BasicBlock::iterator ScanIt, BasicBlock *BB) {
while (ScanIt != BB->begin()) {
Instruction *Inst = --ScanIt;
if (isa<DbgInfoIntrinsic>(Inst)) continue;
if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
Value *Pointer = LI->getPointerOperand();
uint64_t PointerSize = TD->getTypeStoreSize(LI->getType());
AliasAnalysis::AliasResult R =
AA->alias(Pointer, PointerSize, MemPtr, MemSize);
if (R == AliasAnalysis::NoAlias)
continue;
if (isLoad && R == AliasAnalysis::MayAlias)
continue;
return MemDepResult::getDef(Inst);
}
if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
Value *Pointer = SI->getPointerOperand();
uint64_t PointerSize = TD->getTypeStoreSize(SI->getOperand(0)->getType());
AliasAnalysis::AliasResult R =
AA->alias(Pointer, PointerSize, MemPtr, MemSize);
if (R == AliasAnalysis::NoAlias)
continue;
if (R == AliasAnalysis::MayAlias)
return MemDepResult::getClobber(Inst);
return MemDepResult::getDef(Inst);
}
if (AllocationInst *AI = dyn_cast<AllocationInst>(Inst)) {
Value *AccessPtr = MemPtr->getUnderlyingObject();
if (AccessPtr == AI ||
AA->alias(AI, 1, AccessPtr, 1) == AliasAnalysis::MustAlias)
return MemDepResult::getDef(AI);
continue;
}
switch (AA->getModRefInfo(Inst, MemPtr, MemSize)) {
case AliasAnalysis::NoModRef:
continue;
case AliasAnalysis::Ref:
if (isLoad)
continue;
default:
return MemDepResult::getClobber(Inst);
}
}
if (BB != &BB->getParent()->getEntryBlock())
return MemDepResult::getNonLocal();
return MemDepResult::getClobber(ScanIt);
}
MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) {
Instruction *ScanPos = QueryInst;
MemDepResult &LocalCache = LocalDeps[QueryInst];
if (!LocalCache.isDirty())
return LocalCache;
if (Instruction *Inst = LocalCache.getInst()) {
ScanPos = Inst;
RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
}
BasicBlock *QueryParent = QueryInst->getParent();
Value *MemPtr = 0;
uint64_t MemSize = 0;
if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
if (QueryParent != &QueryParent->getParent()->getEntryBlock())
LocalCache = MemDepResult::getNonLocal();
else
LocalCache = MemDepResult::getClobber(QueryInst);
} else if (StoreInst *SI = dyn_cast<StoreInst>(QueryInst)) {
if (SI->isVolatile())
LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
else {
MemPtr = SI->getPointerOperand();
MemSize = TD->getTypeStoreSize(SI->getOperand(0)->getType());
}
} else if (LoadInst *LI = dyn_cast<LoadInst>(QueryInst)) {
if (LI->isVolatile())
LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
else {
MemPtr = LI->getPointerOperand();
MemSize = TD->getTypeStoreSize(LI->getType());
}
} else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
CallSite QueryCS = CallSite::get(QueryInst);
bool isReadOnly = AA->onlyReadsMemory(QueryCS);
LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos,
QueryParent);
} else if (FreeInst *FI = dyn_cast<FreeInst>(QueryInst)) {
MemPtr = FI->getPointerOperand();
MemSize = ~0UL;
} else {
LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos));
}
if (MemPtr)
LocalCache = getPointerDependencyFrom(MemPtr, MemSize,
isa<LoadInst>(QueryInst),
ScanPos, QueryParent);
if (Instruction *I = LocalCache.getInst())
ReverseLocalDeps[I].insert(QueryInst);
return LocalCache;
}
#ifndef NDEBUG
static void AssertSorted(MemoryDependenceAnalysis::NonLocalDepInfo &Cache,
int Count = -1) {
if (Count == -1) Count = Cache.size();
if (Count == 0) return;
for (unsigned i = 1; i != unsigned(Count); ++i)
assert(Cache[i-1] <= Cache[i] && "Cache isn't sorted!");
}
#endif
const MemoryDependenceAnalysis::NonLocalDepInfo &
MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) {
assert(getDependency(QueryCS.getInstruction()).isNonLocal() &&
"getNonLocalCallDependency should only be used on calls with non-local deps!");
PerInstNLInfo &CacheP = NonLocalDeps[QueryCS.getInstruction()];
NonLocalDepInfo &Cache = CacheP.first;
SmallVector<BasicBlock*, 32> DirtyBlocks;
if (!Cache.empty()) {
if (!CacheP.second) {
NumCacheNonLocal++;
return Cache;
}
for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end();
I != E; ++I)
if (I->second.isDirty())
DirtyBlocks.push_back(I->first);
std::sort(Cache.begin(), Cache.end());
++NumCacheDirtyNonLocal;
} else {
BasicBlock *QueryBB = QueryCS.getInstruction()->getParent();
for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI)
DirtyBlocks.push_back(*PI);
NumUncacheNonLocal++;
}
bool isReadonlyCall = AA->onlyReadsMemory(QueryCS);
SmallPtrSet<BasicBlock*, 64> Visited;
unsigned NumSortedEntries = Cache.size();
DEBUG(AssertSorted(Cache));
while (!DirtyBlocks.empty()) {
BasicBlock *DirtyBB = DirtyBlocks.back();
DirtyBlocks.pop_back();
if (!Visited.insert(DirtyBB))
continue;
DEBUG(AssertSorted(Cache, NumSortedEntries));
NonLocalDepInfo::iterator Entry =
std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries,
std::make_pair(DirtyBB, MemDepResult()));
if (Entry != Cache.begin() && prior(Entry)->first == DirtyBB)
--Entry;
MemDepResult *ExistingResult = 0;
if (Entry != Cache.begin()+NumSortedEntries &&
Entry->first == DirtyBB) {
if (!Entry->second.isDirty())
continue;
ExistingResult = &Entry->second;
}
BasicBlock::iterator ScanPos = DirtyBB->end();
if (ExistingResult) {
if (Instruction *Inst = ExistingResult->getInst()) {
ScanPos = Inst;
RemoveFromReverseMap(ReverseNonLocalDeps, Inst,
QueryCS.getInstruction());
}
}
MemDepResult Dep;
if (ScanPos != DirtyBB->begin()) {
Dep = getCallSiteDependencyFrom(QueryCS, isReadonlyCall,ScanPos, DirtyBB);
} else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) {
Dep = MemDepResult::getNonLocal();
} else {
Dep = MemDepResult::getClobber(ScanPos);
}
if (ExistingResult)
*ExistingResult = Dep;
else
Cache.push_back(std::make_pair(DirtyBB, Dep));
if (!Dep.isNonLocal()) {
if (Instruction *Inst = Dep.getInst())
ReverseNonLocalDeps[Inst].insert(QueryCS.getInstruction());
} else {
for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI)
DirtyBlocks.push_back(*PI);
}
}
return Cache;
}
void MemoryDependenceAnalysis::
getNonLocalPointerDependency(Value *Pointer, bool isLoad, BasicBlock *FromBB,
SmallVectorImpl<NonLocalDepEntry> &Result) {
assert(isa<PointerType>(Pointer->getType()) &&
"Can't get pointer deps of a non-pointer!");
Result.clear();
const Type *EltTy = cast<PointerType>(Pointer->getType())->getElementType();
uint64_t PointeeSize = TD->getTypeStoreSize(EltTy);
DenseMap<BasicBlock*, Value*> Visited;
if (!getNonLocalPointerDepFromBB(Pointer, PointeeSize, isLoad, FromBB,
Result, Visited, true))
return;
Result.clear();
Result.push_back(std::make_pair(FromBB,
MemDepResult::getClobber(FromBB->begin())));
}
MemDepResult MemoryDependenceAnalysis::
GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize,
bool isLoad, BasicBlock *BB,
NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
NonLocalDepInfo::iterator Entry =
std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
std::make_pair(BB, MemDepResult()));
if (Entry != Cache->begin() && prior(Entry)->first == BB)
--Entry;
MemDepResult *ExistingResult = 0;
if (Entry != Cache->begin()+NumSortedEntries && Entry->first == BB)
ExistingResult = &Entry->second;
if (ExistingResult && !ExistingResult->isDirty()) {
++NumCacheNonLocalPtr;
return *ExistingResult;
}
BasicBlock::iterator ScanPos = BB->end();
if (ExistingResult && ExistingResult->getInst()) {
assert(ExistingResult->getInst()->getParent() == BB &&
"Instruction invalidated?");
++NumCacheDirtyNonLocalPtr;
ScanPos = ExistingResult->getInst();
ValueIsLoadPair CacheKey(Pointer, isLoad);
RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos, CacheKey);
} else {
++NumUncacheNonLocalPtr;
}
MemDepResult Dep = getPointerDependencyFrom(Pointer, PointeeSize, isLoad,
ScanPos, BB);
if (ExistingResult)
*ExistingResult = Dep;
else
Cache->push_back(std::make_pair(BB, Dep));
if (Dep.isNonLocal())
return Dep;
Instruction *Inst = Dep.getInst();
assert(Inst && "Didn't depend on anything?");
ValueIsLoadPair CacheKey(Pointer, isLoad);
ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
return Dep;
}
bool MemoryDependenceAnalysis::
getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize,
bool isLoad, BasicBlock *StartBB,
SmallVectorImpl<NonLocalDepEntry> &Result,
DenseMap<BasicBlock*, Value*> &Visited,
bool SkipFirstBlock) {
ValueIsLoadPair CacheKey(Pointer, isLoad);
std::pair<BBSkipFirstBlockPair, NonLocalDepInfo> *CacheInfo =
&NonLocalPointerDeps[CacheKey];
NonLocalDepInfo *Cache = &CacheInfo->second;
if (CacheInfo->first == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) {
if (!Visited.empty()) {
for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
I != E; ++I) {
DenseMap<BasicBlock*, Value*>::iterator VI = Visited.find(I->first);
if (VI == Visited.end() || VI->second == Pointer) continue;
return true;
}
}
for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
I != E; ++I) {
Visited.insert(std::make_pair(I->first, Pointer));
if (!I->second.isNonLocal())
Result.push_back(*I);
}
++NumCacheCompleteNonLocalPtr;
return false;
}
if (Cache->empty())
CacheInfo->first = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
else
CacheInfo->first = BBSkipFirstBlockPair();
SmallVector<BasicBlock*, 32> Worklist;
Worklist.push_back(StartBB);
unsigned NumSortedEntries = Cache->size();
DEBUG(AssertSorted(*Cache));
while (!Worklist.empty()) {
BasicBlock *BB = Worklist.pop_back_val();
if (!SkipFirstBlock) {
assert(Visited.count(BB) && "Should check 'visited' before adding to WL");
DEBUG(AssertSorted(*Cache, NumSortedEntries));
MemDepResult Dep = GetNonLocalInfoForBlock(Pointer, PointeeSize, isLoad,
BB, Cache, NumSortedEntries);
if (!Dep.isNonLocal()) {
Result.push_back(NonLocalDepEntry(BB, Dep));
continue;
}
}
Instruction *PtrInst = dyn_cast<Instruction>(Pointer);
bool NeedsPHITranslation = PtrInst && PtrInst->getParent() == BB;
if (!NeedsPHITranslation) {
SkipFirstBlock = false;
for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
InsertRes = Visited.insert(std::make_pair(*PI, Pointer));
if (InsertRes.second) {
Worklist.push_back(*PI);
continue;
}
if (InsertRes.first->second != Pointer)
goto PredTranslationFailure;
}
continue;
}
if (PHINode *PtrPHI = dyn_cast<PHINode>(PtrInst)) {
for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
BasicBlock *Pred = *PI;
Value *PredPtr = PtrPHI->getIncomingValueForBlock(Pred);
std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
InsertRes = Visited.insert(std::make_pair(Pred, PredPtr));
if (!InsertRes.second) {
if (InsertRes.first->second == PredPtr)
continue;
goto PredTranslationFailure;
}
if (Cache && NumSortedEntries != Cache->size())
std::sort(Cache->begin(), Cache->end());
Cache = 0;
if (getNonLocalPointerDepFromBB(PredPtr, PointeeSize, isLoad, Pred,
Result, Visited))
goto PredTranslationFailure;
}
CacheInfo = &NonLocalPointerDeps[CacheKey];
Cache = &CacheInfo->second;
NumSortedEntries = Cache->size();
CacheInfo->first = BBSkipFirstBlockPair();
SkipFirstBlock = false;
continue;
}
PredTranslationFailure:
if (Cache == 0) {
CacheInfo = &NonLocalPointerDeps[CacheKey];
Cache = &CacheInfo->second;
NumSortedEntries = Cache->size();
} else if (NumSortedEntries != Cache->size()) {
std::sort(Cache->begin(), Cache->end());
NumSortedEntries = Cache->size();
}
CacheInfo->first = BBSkipFirstBlockPair();
if (SkipFirstBlock)
return true;
for (NonLocalDepInfo::reverse_iterator I = Cache->rbegin(); ; ++I) {
assert(I != Cache->rend() && "Didn't find current block??");
if (I->first != BB)
continue;
assert(I->second.isNonLocal() &&
"Should only be here with transparent block");
I->second = MemDepResult::getClobber(BB->begin());
ReverseNonLocalPtrDeps[BB->begin()].insert(CacheKey);
Result.push_back(*I);
break;
}
}
switch (Cache->size()-NumSortedEntries) {
case 0:
break;
case 2: {
NonLocalDepEntry Val = Cache->back();
Cache->pop_back();
NonLocalDepInfo::iterator Entry =
std::upper_bound(Cache->begin(), Cache->end()-1, Val);
Cache->insert(Entry, Val);
}
case 1:
if (Cache->size() != 1) {
NonLocalDepEntry Val = Cache->back();
Cache->pop_back();
NonLocalDepInfo::iterator Entry =
std::upper_bound(Cache->begin(), Cache->end(), Val);
Cache->insert(Entry, Val);
}
break;
default:
std::sort(Cache->begin(), Cache->end());
}
DEBUG(AssertSorted(*Cache));
return false;
}
void MemoryDependenceAnalysis::
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) {
CachedNonLocalPointerInfo::iterator It =
NonLocalPointerDeps.find(P);
if (It == NonLocalPointerDeps.end()) return;
NonLocalDepInfo &PInfo = It->second.second;
for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
Instruction *Target = PInfo[i].second.getInst();
if (Target == 0) continue; assert(Target->getParent() == PInfo[i].first);
RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P);
}
NonLocalPointerDeps.erase(It);
}
void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) {
if (!isa<PointerType>(Ptr->getType())) return;
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false));
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
}
void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) {
NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst);
if (NLDI != NonLocalDeps.end()) {
NonLocalDepInfo &BlockMap = NLDI->second.first;
for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end();
DI != DE; ++DI)
if (Instruction *Inst = DI->second.getInst())
RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
NonLocalDeps.erase(NLDI);
}
LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
if (LocalDepEntry != LocalDeps.end()) {
if (Instruction *Inst = LocalDepEntry->second.getInst())
RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
LocalDeps.erase(LocalDepEntry);
}
if (isa<PointerType>(RemInst->getType())) {
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
}
SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd;
MemDepResult NewDirtyVal;
if (!RemInst->isTerminator())
NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst));
ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
if (ReverseDepIt != ReverseLocalDeps.end()) {
SmallPtrSet<Instruction*, 4> &ReverseDeps = ReverseDepIt->second;
assert(!ReverseDeps.empty() && !isa<TerminatorInst>(RemInst) &&
"Nothing can locally depend on a terminator");
for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
E = ReverseDeps.end(); I != E; ++I) {
Instruction *InstDependingOnRemInst = *I;
assert(InstDependingOnRemInst != RemInst &&
"Already removed our local dep info");
LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
assert(NewDirtyVal.getInst() && "There is no way something else can have "
"a local dep on this if it is a terminator!");
ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(),
InstDependingOnRemInst));
}
ReverseLocalDeps.erase(ReverseDepIt);
while (!ReverseDepsToAdd.empty()) {
ReverseLocalDeps[ReverseDepsToAdd.back().first]
.insert(ReverseDepsToAdd.back().second);
ReverseDepsToAdd.pop_back();
}
}
ReverseDepIt = ReverseNonLocalDeps.find(RemInst);
if (ReverseDepIt != ReverseNonLocalDeps.end()) {
SmallPtrSet<Instruction*, 4> &Set = ReverseDepIt->second;
for (SmallPtrSet<Instruction*, 4>::iterator I = Set.begin(), E = Set.end();
I != E; ++I) {
assert(*I != RemInst && "Already removed NonLocalDep info for RemInst");
PerInstNLInfo &INLD = NonLocalDeps[*I];
INLD.second = true;
for (NonLocalDepInfo::iterator DI = INLD.first.begin(),
DE = INLD.first.end(); DI != DE; ++DI) {
if (DI->second.getInst() != RemInst) continue;
DI->second = NewDirtyVal;
if (Instruction *NextI = NewDirtyVal.getInst())
ReverseDepsToAdd.push_back(std::make_pair(NextI, *I));
}
}
ReverseNonLocalDeps.erase(ReverseDepIt);
while (!ReverseDepsToAdd.empty()) {
ReverseNonLocalDeps[ReverseDepsToAdd.back().first]
.insert(ReverseDepsToAdd.back().second);
ReverseDepsToAdd.pop_back();
}
}
ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt =
ReverseNonLocalPtrDeps.find(RemInst);
if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) {
SmallPtrSet<ValueIsLoadPair, 4> &Set = ReversePtrDepIt->second;
SmallVector<std::pair<Instruction*, ValueIsLoadPair>,8> ReversePtrDepsToAdd;
for (SmallPtrSet<ValueIsLoadPair, 4>::iterator I = Set.begin(),
E = Set.end(); I != E; ++I) {
ValueIsLoadPair P = *I;
assert(P.getPointer() != RemInst &&
"Already removed NonLocalPointerDeps info for RemInst");
NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].second;
NonLocalPointerDeps[P].first = BBSkipFirstBlockPair();
for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();
DI != DE; ++DI) {
if (DI->second.getInst() != RemInst) continue;
DI->second = NewDirtyVal;
if (Instruction *NewDirtyInst = NewDirtyVal.getInst())
ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P));
}
std::sort(NLPDI.begin(), NLPDI.end());
}
ReverseNonLocalPtrDeps.erase(ReversePtrDepIt);
while (!ReversePtrDepsToAdd.empty()) {
ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first]
.insert(ReversePtrDepsToAdd.back().second);
ReversePtrDepsToAdd.pop_back();
}
}
assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?");
AA->deleteValue(RemInst);
DEBUG(verifyRemoved(RemInst));
}
void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const {
for (LocalDepMapType::const_iterator I = LocalDeps.begin(),
E = LocalDeps.end(); I != E; ++I) {
assert(I->first != D && "Inst occurs in data structures");
assert(I->second.getInst() != D &&
"Inst occurs in data structures");
}
for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(),
E = NonLocalPointerDeps.end(); I != E; ++I) {
assert(I->first.getPointer() != D && "Inst occurs in NLPD map key");
const NonLocalDepInfo &Val = I->second.second;
for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end();
II != E; ++II)
assert(II->second.getInst() != D && "Inst occurs as NLPD value");
}
for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(),
E = NonLocalDeps.end(); I != E; ++I) {
assert(I->first != D && "Inst occurs in data structures");
const PerInstNLInfo &INLD = I->second;
for (NonLocalDepInfo::const_iterator II = INLD.first.begin(),
EE = INLD.first.end(); II != EE; ++II)
assert(II->second.getInst() != D && "Inst occurs in data structures");
}
for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),
E = ReverseLocalDeps.end(); I != E; ++I) {
assert(I->first != D && "Inst occurs in data structures");
for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
EE = I->second.end(); II != EE; ++II)
assert(*II != D && "Inst occurs in data structures");
}
for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(),
E = ReverseNonLocalDeps.end();
I != E; ++I) {
assert(I->first != D && "Inst occurs in data structures");
for (SmallPtrSet<Instruction*, 4>::const_iterator II = I->second.begin(),
EE = I->second.end(); II != EE; ++II)
assert(*II != D && "Inst occurs in data structures");
}
for (ReverseNonLocalPtrDepTy::const_iterator
I = ReverseNonLocalPtrDeps.begin(),
E = ReverseNonLocalPtrDeps.end(); I != E; ++I) {
assert(I->first != D && "Inst occurs in rev NLPD map");
for (SmallPtrSet<ValueIsLoadPair, 4>::const_iterator II = I->second.begin(),
E = I->second.end(); II != E; ++II)
assert(*II != ValueIsLoadPair(D, false) &&
*II != ValueIsLoadPair(D, true) &&
"Inst occurs in ReverseNonLocalPtrDeps map");
}
}