char MemoryDependenceAnalysis::ID = 0;
// Register this pass...
-static RegisterPass<MemoryDependenceAnalysis> X("memdep",
- "Memory Dependence Analysis", false, true);
+INITIALIZE_PASS(MemoryDependenceAnalysis, "memdep",
+ "Memory Dependence Analysis", false, true);
MemoryDependenceAnalysis::MemoryDependenceAnalysis()
: FunctionPass(&ID), PredCache(0) {
} else if (VAArgInst *V = dyn_cast<VAArgInst>(Inst)) {
Pointer = V->getOperand(0);
PointerSize = AA->getTypeStoreSize(V->getType());
- } else if (isFreeCall(Inst)) {
- Pointer = Inst->getOperand(1);
+ } else if (const CallInst *CI = isFreeCall(Inst)) {
+ Pointer = CI->getArgOperand(0);
// calls to free() erase the entire structure
PointerSize = ~0ULL;
- } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
+ } else if (CallSite InstCS = cast<Value>(Inst)) {
// Debug intrinsics don't cause dependences.
if (isa<DbgInfoIntrinsic>(Inst)) continue;
- CallSite InstCS = CallSite::get(Inst);
// If these two calls do not interfere, look past it.
switch (AA->getModRefInfo(CS, InstCS)) {
case AliasAnalysis::NoModRef:
// pointer, not on query pointers that are indexed off of them. It'd
// be nice to handle that at some point.
AliasAnalysis::AliasResult R =
- AA->alias(II->getOperand(3), ~0U, MemPtr, ~0U);
+ AA->alias(II->getArgOperand(2), ~0U, MemPtr, ~0U);
if (R == AliasAnalysis::MustAlias) {
- InvariantTag = II->getOperand(1);
+ InvariantTag = II->getArgOperand(0);
continue;
}
// pointer, not on query pointers that are indexed off of them. It'd
// be nice to handle that at some point.
AliasAnalysis::AliasResult R =
- AA->alias(II->getOperand(2), ~0U, MemPtr, ~0U);
+ AA->alias(II->getArgOperand(1), ~0U, MemPtr, ~0U);
if (R == AliasAnalysis::MustAlias)
return MemDepResult::getDef(II);
}
// a subsequent bitcast of the malloc call result. There can be stores to
// the malloced memory between the malloc call and its bitcast uses, and we
// need to continue scanning until the malloc call.
- if (isa<AllocaInst>(Inst) || extractMallocCall(Inst)) {
+ if (isa<AllocaInst>(Inst) ||
+ (isa<CallInst>(Inst) && extractMallocCall(Inst))) {
Value *AccessPtr = MemPtr->getUnderlyingObject();
if (AccessPtr == Inst ||
MemPtr = LI->getPointerOperand();
MemSize = AA->getTypeStoreSize(LI->getType());
}
- } else if (isFreeCall(QueryInst)) {
- MemPtr = QueryInst->getOperand(1);
+ } else if (const CallInst *CI = isFreeCall(QueryInst)) {
+ MemPtr = CI->getArgOperand(0);
// calls to free() erase the entire structure, not just a field.
MemSize = ~0UL;
} else if (isa<CallInst>(QueryInst) || isa<InvokeInst>(QueryInst)) {
int IntrinsicID = 0; // Intrinsic IDs start at 1.
- if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst))
+ IntrinsicInst *II = dyn_cast<IntrinsicInst>(QueryInst);
+ if (II)
IntrinsicID = II->getIntrinsicID();
switch (IntrinsicID) {
case Intrinsic::lifetime_start:
case Intrinsic::lifetime_end:
case Intrinsic::invariant_start:
- MemPtr = QueryInst->getOperand(2);
- MemSize = cast<ConstantInt>(QueryInst->getOperand(1))->getZExtValue();
+ MemPtr = II->getArgOperand(1);
+ MemSize = cast<ConstantInt>(II->getArgOperand(0))->getZExtValue();
break;
case Intrinsic::invariant_end:
- MemPtr = QueryInst->getOperand(3);
- MemSize = cast<ConstantInt>(QueryInst->getOperand(2))->getZExtValue();
+ MemPtr = II->getArgOperand(2);
+ MemSize = cast<ConstantInt>(II->getArgOperand(1))->getZExtValue();
break;
default:
- CallSite QueryCS = CallSite::get(QueryInst);
+ CallSite QueryCS(QueryInst);
bool isReadOnly = AA->onlyReadsMemory(QueryCS);
LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos,
QueryParent);
// Okay, we have a cache entry. If we know it is not dirty, just return it
// with no computation.
if (!CacheP.second) {
- NumCacheNonLocal++;
+ ++NumCacheNonLocal;
return Cache;
}
BasicBlock *QueryBB = QueryCS.getInstruction()->getParent();
for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI)
DirtyBlocks.push_back(*PI);
- NumUncacheNonLocal++;
+ ++NumUncacheNonLocal;
}
// isReadonlyCall - If this is a read-only call, we can be more aggressive.
DEBUG(AssertSorted(Cache, NumSortedEntries));
NonLocalDepInfo::iterator Entry =
std::upper_bound(Cache.begin(), Cache.begin()+NumSortedEntries,
- NonLocalDepEntry(DirtyBB, MemDepResult()));
+ NonLocalDepEntry(DirtyBB));
if (Entry != Cache.begin() && prior(Entry)->getBB() == DirtyBB)
--Entry;
///
void MemoryDependenceAnalysis::
getNonLocalPointerDependency(Value *Pointer, bool isLoad, BasicBlock *FromBB,
- SmallVectorImpl<NonLocalDepEntry> &Result) {
- assert(isa<PointerType>(Pointer->getType()) &&
+ SmallVectorImpl<NonLocalDepResult> &Result) {
+ assert(Pointer->getType()->isPointerTy() &&
"Can't get pointer deps of a non-pointer!");
Result.clear();
Result, Visited, true))
return;
Result.clear();
- Result.push_back(NonLocalDepEntry(FromBB,
- MemDepResult::getClobber(FromBB->begin())));
+ Result.push_back(NonLocalDepResult(FromBB,
+ MemDepResult::getClobber(FromBB->begin()),
+ Pointer));
}
/// GetNonLocalInfoForBlock - Compute the memdep value for BB with
// the cache set. If so, find it.
NonLocalDepInfo::iterator Entry =
std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
- NonLocalDepEntry(BB, MemDepResult()));
+ NonLocalDepEntry(BB));
if (Entry != Cache->begin() && (Entry-1)->getBB() == BB)
--Entry;
bool MemoryDependenceAnalysis::
getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, uint64_t PointeeSize,
bool isLoad, BasicBlock *StartBB,
- SmallVectorImpl<NonLocalDepEntry> &Result,
+ SmallVectorImpl<NonLocalDepResult> &Result,
DenseMap<BasicBlock*, Value*> &Visited,
bool SkipFirstBlock) {
}
}
+ Value *Addr = Pointer.getAddr();
for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
I != E; ++I) {
- Visited.insert(std::make_pair(I->getBB(), Pointer.getAddr()));
+ Visited.insert(std::make_pair(I->getBB(), Addr));
if (!I->getResult().isNonLocal())
- Result.push_back(*I);
+ Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr));
}
++NumCacheCompleteNonLocalPtr;
return false;
// If we got a Def or Clobber, add this to the list of results.
if (!Dep.isNonLocal()) {
- Result.push_back(NonLocalDepEntry(BB, Dep));
+ Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr()));
continue;
}
}
// Get the PHI translated pointer in this predecessor. This can fail if
// not translatable, in which case the getAddr() returns null.
PHITransAddr PredPointer(Pointer);
- PredPointer.PHITranslateValue(BB, Pred);
+ PredPointer.PHITranslateValue(BB, Pred, 0);
Value *PredPtrVal = PredPointer.getAddr();
// a computation of the pointer in this predecessor.
if (PredPtrVal == 0) {
// Add the entry to the Result list.
- NonLocalDepEntry Entry(Pred,
- MemDepResult::getClobber(Pred->getTerminator()));
+ NonLocalDepResult Entry(Pred,
+ MemDepResult::getClobber(Pred->getTerminator()),
+ PredPtrVal);
Result.push_back(Entry);
- // Add it to the cache for this CacheKey so that subsequent queries get
- // this result.
- Cache = &NonLocalPointerDeps[CacheKey].second;
- MemoryDependenceAnalysis::NonLocalDepInfo::iterator It =
- std::upper_bound(Cache->begin(), Cache->end(), Entry);
-
- if (It != Cache->begin() && (It-1)->getBB() == Pred)
- --It;
-
- if (It == Cache->end() || It->getBB() != Pred) {
- Cache->insert(It, Entry);
- // Add it to the reverse map.
- ReverseNonLocalPtrDeps[Pred->getTerminator()].insert(CacheKey);
- } else if (!It->getResult().isDirty()) {
- // noop
- } else if (It->getResult().getInst() == Pred->getTerminator()) {
- // Same instruction, clear the dirty marker.
- It->setResult(Entry.getResult());
- } else if (It->getResult().getInst() == 0) {
- // Dirty, with no instruction, just add this.
- It->setResult(Entry.getResult());
- ReverseNonLocalPtrDeps[Pred->getTerminator()].insert(CacheKey);
- } else {
- // Otherwise, dirty with a different instruction.
- RemoveFromReverseMap(ReverseNonLocalPtrDeps,
- It->getResult().getInst(), CacheKey);
- It->setResult(Entry.getResult());
- ReverseNonLocalPtrDeps[Pred->getTerminator()].insert(CacheKey);
- }
- Cache = 0;
+ // Since we had a phi translation failure, the cache for CacheKey won't
+ // include all of the entries that we need to immediately satisfy future
+ // queries. Mark this in NonLocalPointerDeps by setting the
+ // BBSkipFirstBlockPair pointer to null. This requires reuse of the
+ // cached value to do more work but not miss the phi trans failure.
+ NonLocalPointerDeps[CacheKey].first = BBSkipFirstBlockPair();
continue;
}
NumSortedEntries = Cache->size();
}
- // Since we did phi translation, the "Cache" set won't contain all of the
+ // Since we failed phi translation, the "Cache" set won't contain all of the
// results for the query. This is ok (we can still use it to accelerate
// specific block queries) but we can't do the fastpath "return all
- // results from the set" Clear out the indicator for this.
+ // results from the set". Clear out the indicator for this.
CacheInfo->first = BBSkipFirstBlockPair();
// If *nothing* works, mark the pointer as being clobbered by the first
"Should only be here with transparent block");
I->setResult(MemDepResult::getClobber(BB->begin()));
ReverseNonLocalPtrDeps[BB->begin()].insert(CacheKey);
- Result.push_back(*I);
+ Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(),
+ Pointer.getAddr()));
break;
}
}
/// in more places that cached info does not necessarily keep.
void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) {
// If Ptr isn't really a pointer, just ignore it.
- if (!isa<PointerType>(Ptr->getType())) return;
+ if (!Ptr->getType()->isPointerTy()) return;
// Flush store info for the pointer.
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, false));
// Flush load info for the pointer.
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true));
}
+/// invalidateCachedPredecessors - Clear the PredIteratorCache info.
+/// This needs to be done when the CFG changes, e.g., due to splitting
+/// critical edges.
+void MemoryDependenceAnalysis::invalidateCachedPredecessors() {
+ PredCache->clear();
+}
+
/// removeInstruction - Remove an instruction from the dependence analysis,
/// updating the dependence of instructions that previously depended on it.
/// This method attempts to keep the cache coherent using the reverse map.
// Remove it from both the load info and the store info. The instruction
// can't be in either of these maps if it is non-pointer.
- if (isa<PointerType>(RemInst->getType())) {
+ if (RemInst->getType()->isPointerTy()) {
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false));
RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true));
}