MemoryDependenceAnalysis.cpp [plain text]
#define DEBUG_TYPE "memdep"
#include "llvm/Analysis/MemoryDependenceAnalysis.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/Instructions.h"
#include "llvm/IntrinsicInst.h"
#include "llvm/Function.h"
#include "llvm/LLVMContext.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/CaptureTracking.h"
#include "llvm/Analysis/Dominators.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/PHITransAddr.h"
#include "llvm/Analysis/ValueTracking.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");
static const int BlockScanLimit = 500;
char MemoryDependenceAnalysis::ID = 0;
INITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep",
"Memory Dependence Analysis", false, true)
INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep",
"Memory Dependence Analysis", false, true)
MemoryDependenceAnalysis::MemoryDependenceAnalysis()
: FunctionPass(ID), PredCache(0) {
initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry());
}
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>();
}
bool MemoryDependenceAnalysis::runOnFunction(Function &) {
AA = &getAnalysis<AliasAnalysis>();
TD = getAnalysisIfAvailable<TargetData>();
DT = getAnalysisIfAvailable<DominatorTree>();
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!"); (void)Found;
if (InstIt->second.empty())
ReverseMap.erase(InstIt);
}
static
AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst,
AliasAnalysis::Location &Loc,
AliasAnalysis *AA) {
if (const LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
if (LI->isUnordered()) {
Loc = AA->getLocation(LI);
return AliasAnalysis::Ref;
} else if (LI->getOrdering() == Monotonic) {
Loc = AA->getLocation(LI);
return AliasAnalysis::ModRef;
}
Loc = AliasAnalysis::Location();
return AliasAnalysis::ModRef;
}
if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
if (SI->isUnordered()) {
Loc = AA->getLocation(SI);
return AliasAnalysis::Mod;
} else if (SI->getOrdering() == Monotonic) {
Loc = AA->getLocation(SI);
return AliasAnalysis::ModRef;
}
Loc = AliasAnalysis::Location();
return AliasAnalysis::ModRef;
}
if (const VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
Loc = AA->getLocation(V);
return AliasAnalysis::ModRef;
}
if (const CallInst *CI = isFreeCall(Inst)) {
Loc = AliasAnalysis::Location(CI->getArgOperand(0));
return AliasAnalysis::Mod;
}
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
switch (II->getIntrinsicID()) {
case Intrinsic::lifetime_start:
case Intrinsic::lifetime_end:
case Intrinsic::invariant_start:
Loc = AliasAnalysis::Location(II->getArgOperand(1),
cast<ConstantInt>(II->getArgOperand(0))
->getZExtValue(),
II->getMetadata(LLVMContext::MD_tbaa));
return AliasAnalysis::Mod;
case Intrinsic::invariant_end:
Loc = AliasAnalysis::Location(II->getArgOperand(2),
cast<ConstantInt>(II->getArgOperand(1))
->getZExtValue(),
II->getMetadata(LLVMContext::MD_tbaa));
return AliasAnalysis::Mod;
default:
break;
}
if (Inst->mayWriteToMemory())
return AliasAnalysis::ModRef;
if (Inst->mayReadFromMemory())
return AliasAnalysis::Ref;
return AliasAnalysis::NoModRef;
}
MemDepResult MemoryDependenceAnalysis::
getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall,
BasicBlock::iterator ScanIt, BasicBlock *BB) {
unsigned Limit = BlockScanLimit;
while (ScanIt != BB->begin()) {
--Limit;
if (!Limit)
return MemDepResult::getUnknown();
Instruction *Inst = --ScanIt;
AliasAnalysis::Location Loc;
AliasAnalysis::ModRefResult MR = GetLocation(Inst, Loc, AA);
if (Loc.Ptr) {
if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef)
return MemDepResult::getClobber(Inst);
continue;
}
if (CallSite InstCS = cast<Value>(Inst)) {
if (isa<DbgInfoIntrinsic>(Inst)) continue;
switch (AA->getModRefInfo(CS, InstCS)) {
case AliasAnalysis::NoModRef:
if (isReadOnlyCall && !(MR & AliasAnalysis::Mod) &&
CS.getInstruction()->isIdenticalToWhenDefined(Inst))
return MemDepResult::getDef(Inst);
break;
default:
return MemDepResult::getClobber(Inst);
}
}
}
if (BB != &BB->getParent()->getEntryBlock())
return MemDepResult::getNonLocal();
return MemDepResult::getNonFuncLocal();
}
static bool
isLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc,
const Value *&MemLocBase,
int64_t &MemLocOffs,
const LoadInst *LI,
const TargetData *TD) {
if (TD == 0) return false;
if (MemLocBase == 0)
MemLocBase = GetPointerBaseWithConstantOffset(MemLoc.Ptr, MemLocOffs, *TD);
unsigned Size = MemoryDependenceAnalysis::
getLoadLoadClobberFullWidthSize(MemLocBase, MemLocOffs, MemLoc.Size,
LI, *TD);
return Size != 0;
}
unsigned MemoryDependenceAnalysis::
getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs,
unsigned MemLocSize, const LoadInst *LI,
const TargetData &TD) {
if (!isa<IntegerType>(LI->getType()) || !LI->isSimple()) return 0;
int64_t LIOffs = 0;
const Value *LIBase =
GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, TD);
if (LIBase != MemLocBase) return 0;
if (MemLocOffs < LIOffs) return 0;
unsigned LoadAlign = LI->getAlignment();
int64_t MemLocEnd = MemLocOffs+MemLocSize;
if (LIOffs+LoadAlign < MemLocEnd) return 0;
unsigned NewLoadByteSize = LI->getType()->getPrimitiveSizeInBits()/8U;
NewLoadByteSize = NextPowerOf2(NewLoadByteSize);
while (1) {
if (NewLoadByteSize > LoadAlign ||
!TD.fitsInLegalInteger(NewLoadByteSize*8))
return 0;
if (LIOffs+NewLoadByteSize >= MemLocEnd)
return NewLoadByteSize;
NewLoadByteSize <<= 1;
}
return 0;
}
namespace {
struct CapturesBefore : public CaptureTracker {
CapturesBefore(const Instruction *I, DominatorTree *DT)
: BeforeHere(I), DT(DT), Captured(false) {}
void tooManyUses() { Captured = true; }
bool shouldExplore(Use *U) {
Instruction *I = cast<Instruction>(U->getUser());
if (BeforeHere != I && DT->dominates(BeforeHere, I))
return false;
return true;
}
bool captured(Instruction *I) {
if (BeforeHere != I && DT->dominates(BeforeHere, I))
return false;
Captured = true;
return true;
}
const Instruction *BeforeHere;
DominatorTree *DT;
bool Captured;
};
}
AliasAnalysis::ModRefResult
MemoryDependenceAnalysis::getModRefInfo(const Instruction *Inst,
const AliasAnalysis::Location &MemLoc) {
AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc);
if (MR != AliasAnalysis::ModRef) return MR;
if (!DT) return AliasAnalysis::ModRef;
const Value *Object = GetUnderlyingObject(MemLoc.Ptr, TD);
if (!isIdentifiedObject(Object) || isa<GlobalValue>(Object))
return AliasAnalysis::ModRef;
ImmutableCallSite CS(Inst);
if (!CS.getInstruction()) return AliasAnalysis::ModRef;
CapturesBefore CB(Inst, DT);
llvm::PointerMayBeCaptured(Object, &CB);
if (isa<Constant>(Object) || CS.getInstruction() == Object || CB.Captured)
return AliasAnalysis::ModRef;
unsigned ArgNo = 0;
for (ImmutableCallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end();
CI != CE; ++CI, ++ArgNo) {
if (!(*CI)->getType()->isPointerTy() ||
(!CS.doesNotCapture(ArgNo) && !CS.isByValArgument(ArgNo)))
continue;
if (!AA->isNoAlias(AliasAnalysis::Location(*CI),
AliasAnalysis::Location(Object))) {
return AliasAnalysis::ModRef;
}
}
return AliasAnalysis::NoModRef;
}
MemDepResult MemoryDependenceAnalysis::
getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad,
BasicBlock::iterator ScanIt, BasicBlock *BB) {
const Value *MemLocBase = 0;
int64_t MemLocOffset = 0;
unsigned Limit = BlockScanLimit;
while (ScanIt != BB->begin()) {
--Limit;
if (!Limit)
return MemDepResult::getUnknown();
Instruction *Inst = --ScanIt;
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst)) {
if (isa<DbgInfoIntrinsic>(II)) continue;
if (II->getIntrinsicID() == Intrinsic::lifetime_start) {
if (AA->isMustAlias(AliasAnalysis::Location(II->getArgOperand(1)),
MemLoc))
return MemDepResult::getDef(II);
continue;
}
}
if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
if (!LI->isUnordered())
return MemDepResult::getClobber(LI);
AliasAnalysis::Location LoadLoc = AA->getLocation(LI);
AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc);
if (isLoad) {
if (R == AliasAnalysis::NoAlias) {
if (IntegerType *ITy = dyn_cast<IntegerType>(LI->getType()))
if (LI->getAlignment()*8 > ITy->getPrimitiveSizeInBits() &&
isLoadLoadClobberIfExtendedToFullWidth(MemLoc, MemLocBase,
MemLocOffset, LI, TD))
return MemDepResult::getClobber(Inst);
continue;
}
if (R == AliasAnalysis::MustAlias)
return MemDepResult::getDef(Inst);
#if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads
if (R == AliasAnalysis::PartialAlias)
return MemDepResult::getClobber(Inst);
#endif
continue;
}
if (R == AliasAnalysis::NoAlias)
continue;
if (AA->pointsToConstantMemory(LoadLoc))
continue;
return MemDepResult::getDef(Inst);
}
if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
if (!SI->isUnordered())
return MemDepResult::getClobber(SI);
if (AA->getModRefInfo(SI, MemLoc) == AliasAnalysis::NoModRef)
continue;
AliasAnalysis::Location StoreLoc = AA->getLocation(SI);
AliasAnalysis::AliasResult R = AA->alias(StoreLoc, MemLoc);
if (R == AliasAnalysis::NoAlias)
continue;
if (R == AliasAnalysis::MustAlias)
return MemDepResult::getDef(Inst);
return MemDepResult::getClobber(Inst);
}
if (isa<AllocaInst>(Inst) ||
(isa<CallInst>(Inst) && extractMallocCall(Inst))) {
const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, TD);
if (AccessPtr == Inst || AA->isMustAlias(Inst, AccessPtr))
return MemDepResult::getDef(Inst);
continue;
}
switch (getModRefInfo(Inst, MemLoc)) {
case AliasAnalysis::NoModRef:
continue;
case AliasAnalysis::Mod:
return MemDepResult::getClobber(Inst);
case AliasAnalysis::Ref:
if (isLoad)
continue;
default:
return MemDepResult::getClobber(Inst);
}
}
if (BB != &BB->getParent()->getEntryBlock())
return MemDepResult::getNonLocal();
return MemDepResult::getNonFuncLocal();
}
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();
if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) {
if (QueryParent != &QueryParent->getParent()->getEntryBlock())
LocalCache = MemDepResult::getNonLocal();
else
LocalCache = MemDepResult::getNonFuncLocal();
} else {
AliasAnalysis::Location MemLoc;
AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA);
if (MemLoc.Ptr) {
bool isLoad = !(MR & AliasAnalysis::Mod);
if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst))
isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start;
LocalCache = getPointerDependencyFrom(MemLoc, isLoad, ScanPos,
QueryParent);
} else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
CallSite QueryCS(QueryInst);
bool isReadOnly = AA->onlyReadsMemory(QueryCS);
LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos,
QueryParent);
} else
LocalCache = MemDepResult::getUnknown();
}
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] < Cache[i-1]) && "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->getResult().isDirty())
DirtyBlocks.push_back(I->getBB());
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,
NonLocalDepEntry(DirtyBB));
if (Entry != Cache.begin() && prior(Entry)->getBB() == DirtyBB)
--Entry;
NonLocalDepEntry *ExistingResult = 0;
if (Entry != Cache.begin()+NumSortedEntries &&
Entry->getBB() == DirtyBB) {
if (!Entry->getResult().isDirty())
continue;
ExistingResult = &*Entry;
}
BasicBlock::iterator ScanPos = DirtyBB->end();
if (ExistingResult) {
if (Instruction *Inst = ExistingResult->getResult().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::getNonFuncLocal();
}
if (ExistingResult)
ExistingResult->setResult(Dep);
else
Cache.push_back(NonLocalDepEntry(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(const AliasAnalysis::Location &Loc, bool isLoad,
BasicBlock *FromBB,
SmallVectorImpl<NonLocalDepResult> &Result) {
assert(Loc.Ptr->getType()->isPointerTy() &&
"Can't get pointer deps of a non-pointer!");
Result.clear();
PHITransAddr Address(const_cast<Value *>(Loc.Ptr), TD);
DenseMap<BasicBlock*, Value*> Visited;
if (!getNonLocalPointerDepFromBB(Address, Loc, isLoad, FromBB,
Result, Visited, true))
return;
Result.clear();
Result.push_back(NonLocalDepResult(FromBB,
MemDepResult::getUnknown(),
const_cast<Value *>(Loc.Ptr)));
}
MemDepResult MemoryDependenceAnalysis::
GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc,
bool isLoad, BasicBlock *BB,
NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
NonLocalDepInfo::iterator Entry =
std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
NonLocalDepEntry(BB));
if (Entry != Cache->begin() && (Entry-1)->getBB() == BB)
--Entry;
NonLocalDepEntry *ExistingResult = 0;
if (Entry != Cache->begin()+NumSortedEntries && Entry->getBB() == BB)
ExistingResult = &*Entry;
if (ExistingResult && !ExistingResult->getResult().isDirty()) {
++NumCacheNonLocalPtr;
return ExistingResult->getResult();
}
BasicBlock::iterator ScanPos = BB->end();
if (ExistingResult && ExistingResult->getResult().getInst()) {
assert(ExistingResult->getResult().getInst()->getParent() == BB &&
"Instruction invalidated?");
++NumCacheDirtyNonLocalPtr;
ScanPos = ExistingResult->getResult().getInst();
ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos, CacheKey);
} else {
++NumUncacheNonLocalPtr;
}
MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB);
if (ExistingResult)
ExistingResult->setResult(Dep);
else
Cache->push_back(NonLocalDepEntry(BB, Dep));
if (!Dep.isDef() && !Dep.isClobber())
return Dep;
Instruction *Inst = Dep.getInst();
assert(Inst && "Didn't depend on anything?");
ValueIsLoadPair CacheKey(Loc.Ptr, isLoad);
ReverseNonLocalPtrDeps[Inst].insert(CacheKey);
return Dep;
}
static void
SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache,
unsigned NumSortedEntries) {
switch (Cache.size() - NumSortedEntries) {
case 0:
break;
case 2: {
NonLocalDepEntry Val = Cache.back();
Cache.pop_back();
MemoryDependenceAnalysis::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();
MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry =
std::upper_bound(Cache.begin(), Cache.end(), Val);
Cache.insert(Entry, Val);
}
break;
default:
std::sort(Cache.begin(), Cache.end());
break;
}
}
bool MemoryDependenceAnalysis::
getNonLocalPointerDepFromBB(const PHITransAddr &Pointer,
const AliasAnalysis::Location &Loc,
bool isLoad, BasicBlock *StartBB,
SmallVectorImpl<NonLocalDepResult> &Result,
DenseMap<BasicBlock*, Value*> &Visited,
bool SkipFirstBlock) {
ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad);
NonLocalPointerInfo InitialNLPI;
InitialNLPI.Size = Loc.Size;
InitialNLPI.TBAATag = Loc.TBAATag;
std::pair<CachedNonLocalPointerInfo::iterator, bool> Pair =
NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI));
NonLocalPointerInfo *CacheInfo = &Pair.first->second;
if (!Pair.second) {
if (CacheInfo->Size < Loc.Size) {
CacheInfo->Pair = BBSkipFirstBlockPair();
CacheInfo->Size = Loc.Size;
for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(),
DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI)
if (Instruction *Inst = DI->getResult().getInst())
RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
CacheInfo->NonLocalDeps.clear();
} else if (CacheInfo->Size > Loc.Size) {
return getNonLocalPointerDepFromBB(Pointer,
Loc.getWithNewSize(CacheInfo->Size),
isLoad, StartBB, Result, Visited,
SkipFirstBlock);
}
if (CacheInfo->TBAATag != Loc.TBAATag) {
if (CacheInfo->TBAATag) {
CacheInfo->Pair = BBSkipFirstBlockPair();
CacheInfo->TBAATag = 0;
for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(),
DE = CacheInfo->NonLocalDeps.end(); DI != DE; ++DI)
if (Instruction *Inst = DI->getResult().getInst())
RemoveFromReverseMap(ReverseNonLocalPtrDeps, Inst, CacheKey);
CacheInfo->NonLocalDeps.clear();
}
if (Loc.TBAATag)
return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutTBAATag(),
isLoad, StartBB, Result, Visited,
SkipFirstBlock);
}
}
NonLocalDepInfo *Cache = &CacheInfo->NonLocalDeps;
if (CacheInfo->Pair == 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->getBB());
if (VI == Visited.end() || VI->second == Pointer.getAddr())
continue;
return true;
}
}
Value *Addr = Pointer.getAddr();
for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
I != E; ++I) {
Visited.insert(std::make_pair(I->getBB(), Addr));
if (!I->getResult().isNonLocal())
Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr));
}
++NumCacheCompleteNonLocalPtr;
return false;
}
if (Cache->empty())
CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock);
else
CacheInfo->Pair = BBSkipFirstBlockPair();
SmallVector<BasicBlock*, 32> Worklist;
Worklist.push_back(StartBB);
SmallVector<std::pair<BasicBlock*, PHITransAddr>, 16> PredList;
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(Loc, isLoad, BB, Cache,
NumSortedEntries);
if (!Dep.isNonLocal()) {
Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));
continue;
}
}
if (!Pointer.NeedsPHITranslationFromBlock(BB)) {
SkipFirstBlock = false;
SmallVector<BasicBlock*, 16> NewBlocks;
for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr()));
if (InsertRes.second) {
NewBlocks.push_back(*PI);
continue;
}
if (InsertRes.first->second != Pointer.getAddr()) {
for (unsigned i = 0; i < NewBlocks.size(); i++)
Visited.erase(NewBlocks[i]);
goto PredTranslationFailure;
}
}
Worklist.append(NewBlocks.begin(), NewBlocks.end());
continue;
}
if (!Pointer.IsPotentiallyPHITranslatable())
goto PredTranslationFailure;
if (Cache && NumSortedEntries != Cache->size()) {
SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
NumSortedEntries = Cache->size();
}
Cache = 0;
PredList.clear();
for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
BasicBlock *Pred = *PI;
PredList.push_back(std::make_pair(Pred, Pointer));
PHITransAddr &PredPointer = PredList.back().second;
PredPointer.PHITranslateValue(BB, Pred, 0);
Value *PredPtrVal = PredPointer.getAddr();
std::pair<DenseMap<BasicBlock*,Value*>::iterator, bool>
InsertRes = Visited.insert(std::make_pair(Pred, PredPtrVal));
if (!InsertRes.second) {
PredList.pop_back();
if (InsertRes.first->second == PredPtrVal)
continue;
for (unsigned i = 0; i < PredList.size(); i++)
Visited.erase(PredList[i].first);
goto PredTranslationFailure;
}
}
for (unsigned i = 0; i < PredList.size(); i++) {
BasicBlock *Pred = PredList[i].first;
PHITransAddr &PredPointer = PredList[i].second;
Value *PredPtrVal = PredPointer.getAddr();
bool CanTranslate = true;
if (PredPtrVal == 0)
CanTranslate = false;
if (!CanTranslate ||
getNonLocalPointerDepFromBB(PredPointer,
Loc.getWithNewPtr(PredPtrVal),
isLoad, Pred,
Result, Visited)) {
NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal);
Result.push_back(Entry);
NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey];
NLPI.Pair = BBSkipFirstBlockPair();
continue;
}
}
CacheInfo = &NonLocalPointerDeps[CacheKey];
Cache = &CacheInfo->NonLocalDeps;
NumSortedEntries = Cache->size();
CacheInfo->Pair = BBSkipFirstBlockPair();
SkipFirstBlock = false;
continue;
PredTranslationFailure:
if (Cache == 0) {
CacheInfo = &NonLocalPointerDeps[CacheKey];
Cache = &CacheInfo->NonLocalDeps;
NumSortedEntries = Cache->size();
}
CacheInfo->Pair = BBSkipFirstBlockPair();
if (SkipFirstBlock)
return true;
for (NonLocalDepInfo::reverse_iterator I = Cache->rbegin(); ; ++I) {
assert(I != Cache->rend() && "Didn't find current block??");
if (I->getBB() != BB)
continue;
assert(I->getResult().isNonLocal() &&
"Should only be here with transparent block");
I->setResult(MemDepResult::getUnknown());
Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(),
Pointer.getAddr()));
break;
}
}
SortNonLocalDepInfoCache(*Cache, NumSortedEntries);
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.NonLocalDeps;
for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
Instruction *Target = PInfo[i].getResult().getInst();
if (Target == 0) continue; assert(Target->getParent() == PInfo[i].getBB());
RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P);
}
NonLocalPointerDeps.erase(It);
}
void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) {
if (!Ptr->getType()->isPointerTy()) return;
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false));
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
}
void MemoryDependenceAnalysis::invalidateCachedPredecessors() {
PredCache->clear();
}
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->getResult().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 (RemInst->getType()->isPointerTy()) {
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->getResult().getInst() != RemInst) continue;
DI->setResult(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].NonLocalDeps;
NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair();
for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();
DI != DE; ++DI) {
if (DI->getResult().getInst() != RemInst) continue;
DI->setResult(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.NonLocalDeps;
for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end();
II != E; ++II)
assert(II->getResult().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->getResult().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");
}
}