X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FMemoryDependenceAnalysis.cpp;h=35043bddfaf6c541904d329f61fc31e36d680eb9;hb=a704bc9354d8b03fd98da9bd7de5ae1dc49af961;hp=b4c6d09e4c2165cfd6c9145bdf37dc1af0082d23;hpb=075fb5d68fcb55d26e44c48f07dfdbbfa21ccb2a;p=oota-llvm.git diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index b4c6d09e4c2..35043bddfaf 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -25,10 +25,12 @@ #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"); @@ -82,6 +84,7 @@ void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { bool MemoryDependenceAnalysis::runOnFunction(Function &) { AA = &getAnalysis(); + TD = getAnalysisIfAvailable(); if (PredCache == 0) PredCache.reset(new PredIteratorCache()); return false; @@ -97,11 +100,79 @@ static void RemoveFromReverseMap(DenseMapsecond.erase(Val); - assert(Found && "Invalid reverse map!"); Found=Found; + assert(Found && "Invalid reverse map!"); (void)Found; if (InstIt->second.empty()) ReverseMap.erase(InstIt); } +/// GetLocation - If the given instruction references a specific memory +/// location, fill in Loc with the details, otherwise set Loc.Ptr to null. +/// Return a ModRefInfo value describing the general behavior of the +/// instruction. +static +AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst, + AliasAnalysis::Location &Loc, + AliasAnalysis *AA) { + if (const LoadInst *LI = dyn_cast(Inst)) { + if (LI->isVolatile()) { + Loc = AliasAnalysis::Location(); + return AliasAnalysis::ModRef; + } + Loc = AA->getLocation(LI); + return AliasAnalysis::Ref; + } + + if (const StoreInst *SI = dyn_cast(Inst)) { + if (SI->isVolatile()) { + Loc = AliasAnalysis::Location(); + return AliasAnalysis::ModRef; + } + Loc = AA->getLocation(SI); + return AliasAnalysis::Mod; + } + + if (const VAArgInst *V = dyn_cast(Inst)) { + Loc = AA->getLocation(V); + return AliasAnalysis::ModRef; + } + + if (const CallInst *CI = isFreeCall(Inst)) { + // calls to free() deallocate the entire structure + Loc = AliasAnalysis::Location(CI->getArgOperand(0)); + return AliasAnalysis::Mod; + } + + if (const IntrinsicInst *II = dyn_cast(Inst)) + switch (II->getIntrinsicID()) { + case Intrinsic::lifetime_start: + case Intrinsic::lifetime_end: + case Intrinsic::invariant_start: + Loc = AliasAnalysis::Location(II->getArgOperand(1), + cast(II->getArgOperand(0)) + ->getZExtValue(), + II->getMetadata(LLVMContext::MD_tbaa)); + // These intrinsics don't really modify the memory, but returning Mod + // will allow them to be handled conservatively. + return AliasAnalysis::Mod; + case Intrinsic::invariant_end: + Loc = AliasAnalysis::Location(II->getArgOperand(2), + cast(II->getArgOperand(1)) + ->getZExtValue(), + II->getMetadata(LLVMContext::MD_tbaa)); + // These intrinsics don't really modify the memory, but returning Mod + // will allow them to be handled conservatively. + return AliasAnalysis::Mod; + default: + break; + } + + // Otherwise, just do the coarse-grained thing that always works. + if (Inst->mayWriteToMemory()) + return AliasAnalysis::ModRef; + if (Inst->mayReadFromMemory()) + return AliasAnalysis::Ref; + return AliasAnalysis::NoModRef; +} /// getCallSiteDependencyFrom - Private helper for finding the local /// dependencies of a call site. @@ -114,19 +185,15 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, // If this inst is a memory op, get the pointer it accessed AliasAnalysis::Location Loc; - if (StoreInst *S = dyn_cast(Inst)) { - Loc = AliasAnalysis::Location(S->getPointerOperand(), - AA->getTypeStoreSize(S->getValueOperand() - ->getType()), - S->getMetadata(LLVMContext::MD_tbaa)); - } else if (VAArgInst *V = dyn_cast(Inst)) { - Loc = AliasAnalysis::Location(V->getPointerOperand(), - AA->getTypeStoreSize(V->getType()), - V->getMetadata(LLVMContext::MD_tbaa)); - } else if (const CallInst *CI = isFreeCall(Inst)) { - // calls to free() erase the entire structure - Loc = AliasAnalysis::Location(CI->getArgOperand(0)); - } else if (CallSite InstCS = cast(Inst)) { + AliasAnalysis::ModRefResult MR = GetLocation(Inst, Loc, AA); + if (Loc.Ptr) { + // A simple instruction. + if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef) + return MemDepResult::getClobber(Inst); + continue; + } + + if (CallSite InstCS = cast(Inst)) { // Debug intrinsics don't cause dependences. if (isa(Inst)) continue; // If these two calls do not interfere, look past it. @@ -134,23 +201,17 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, case AliasAnalysis::NoModRef: // If the two calls are the same, return InstCS as a Def, so that // CS can be found redundant and eliminated. - if (isReadOnlyCall && InstCS.onlyReadsMemory() && + if (isReadOnlyCall && !(MR & AliasAnalysis::Mod) && CS.getInstruction()->isIdenticalToWhenDefined(Inst)) return MemDepResult::getDef(Inst); // Otherwise if the two calls don't interact (e.g. InstCS is readnone) // keep scanning. - continue; + break; default: return MemDepResult::getClobber(Inst); } - } else { - // Non-memory instruction. - continue; } - - if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef) - return MemDepResult::getClobber(Inst); } // No dependence found. If this is the entry block of the function, it is a @@ -223,10 +284,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // Values depend on loads if the pointers are must aliased. This means that // a load depends on another must aliased load from the same value. if (LoadInst *LI = dyn_cast(Inst)) { - Value *Pointer = LI->getPointerOperand(); - uint64_t PointerSize = AA->getTypeStoreSize(LI->getType()); - MDNode *TBAATag = LI->getMetadata(LLVMContext::MD_tbaa); - AliasAnalysis::Location LoadLoc(Pointer, PointerSize, TBAATag); + AliasAnalysis::Location LoadLoc = AA->getLocation(LI); // If we found a pointer, check if it could be the same as our pointer. AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc); @@ -234,7 +292,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, continue; // May-alias loads don't depend on each other without a dependence. - if (isLoad && R == AliasAnalysis::MayAlias) + if (isLoad && R != AliasAnalysis::MustAlias) continue; // Stores don't alias loads from read-only memory. @@ -259,20 +317,16 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // Ok, this store might clobber the query pointer. Check to see if it is // a must alias: in this case, we want to return this as a def. - Value *Pointer = SI->getPointerOperand(); - uint64_t PointerSize = AA->getTypeStoreSize(SI->getOperand(0)->getType()); - MDNode *TBAATag = SI->getMetadata(LLVMContext::MD_tbaa); + AliasAnalysis::Location StoreLoc = AA->getLocation(SI); // If we found a pointer, check if it could be the same as our pointer. - AliasAnalysis::AliasResult R = - AA->alias(AliasAnalysis::Location(Pointer, PointerSize, TBAATag), - MemLoc); + AliasAnalysis::AliasResult R = AA->alias(StoreLoc, MemLoc); if (R == AliasAnalysis::NoAlias) continue; - if (R == AliasAnalysis::MayAlias) - return MemDepResult::getClobber(Inst); - return MemDepResult::getDef(Inst); + if (R == AliasAnalysis::MustAlias) + return MemDepResult::getDef(Inst); + return MemDepResult::getClobber(Inst); } // If this is an allocation, and if we know that the accessed pointer is to @@ -285,7 +339,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // need to continue scanning until the malloc call. if (isa(Inst) || (isa(Inst) && extractMallocCall(Inst))) { - const Value *AccessPtr = MemLoc.Ptr->getUnderlyingObject(); + const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, TD); if (AccessPtr == Inst || AA->alias(Inst, 1, AccessPtr, 1) == AliasAnalysis::MustAlias) @@ -344,8 +398,6 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { BasicBlock *QueryParent = QueryInst->getParent(); - AliasAnalysis::Location MemLoc; - // Do the scan. if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) { // No dependence found. If this is the entry block of the function, it is a @@ -354,69 +406,25 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { LocalCache = MemDepResult::getNonLocal(); else LocalCache = MemDepResult::getClobber(QueryInst); - } else if (StoreInst *SI = dyn_cast(QueryInst)) { - // If this is a volatile store, don't mess around with it. Just return the - // previous instruction as a clobber. - if (SI->isVolatile()) - LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos)); - else - MemLoc = AliasAnalysis::Location(SI->getPointerOperand(), - AA->getTypeStoreSize(SI->getOperand(0) - ->getType()), - SI->getMetadata(LLVMContext::MD_tbaa)); - } else if (LoadInst *LI = dyn_cast(QueryInst)) { - // If this is a volatile load, don't mess around with it. Just return the - // previous instruction as a clobber. - if (LI->isVolatile()) - LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos)); - else - MemLoc = AliasAnalysis::Location(LI->getPointerOperand(), - AA->getTypeStoreSize(LI->getType()), - LI->getMetadata(LLVMContext::MD_tbaa)); - } else if (const CallInst *CI = isFreeCall(QueryInst)) { - // calls to free() erase the entire structure, not just a field. - MemLoc = AliasAnalysis::Location(CI->getArgOperand(0)); - } else if (isa(QueryInst) || isa(QueryInst)) { - int IntrinsicID = 0; // Intrinsic IDs start at 1. - IntrinsicInst *II = dyn_cast(QueryInst); - if (II) - IntrinsicID = II->getIntrinsicID(); - - switch (IntrinsicID) { - case Intrinsic::lifetime_start: - case Intrinsic::lifetime_end: - case Intrinsic::invariant_start: - MemLoc = AliasAnalysis::Location(II->getArgOperand(1), - cast(II->getArgOperand(0)) - ->getZExtValue(), - II->getMetadata(LLVMContext::MD_tbaa)); - break; - case Intrinsic::invariant_end: - MemLoc = AliasAnalysis::Location(II->getArgOperand(2), - cast(II->getArgOperand(1)) - ->getZExtValue(), - II->getMetadata(LLVMContext::MD_tbaa)); - break; - default: + } else { + AliasAnalysis::Location MemLoc; + AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA); + if (MemLoc.Ptr) { + // If we can do a pointer scan, make it happen. + bool isLoad = !(MR & AliasAnalysis::Mod); + if (IntrinsicInst *II = dyn_cast(QueryInst)) + isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_end; + + LocalCache = getPointerDependencyFrom(MemLoc, isLoad, ScanPos, + QueryParent); + } else if (isa(QueryInst) || isa(QueryInst)) { CallSite QueryCS(QueryInst); bool isReadOnly = AA->onlyReadsMemory(QueryCS); LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos, QueryParent); - break; - } - } else { - // Non-memory instruction. - LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos)); - } - - // If we need to do a pointer scan, make it happen. - if (MemLoc.Ptr) { - bool isLoad = !QueryInst->mayWriteToMemory(); - if (IntrinsicInst *II = dyn_cast(QueryInst)) { - isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_end; - } - LocalCache = getPointerDependencyFrom(MemLoc, isLoad, ScanPos, - QueryParent); + } else + // Non-memory instruction. + LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos)); } // Remember the result! @@ -756,24 +764,45 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, NonLocalPointerDeps.insert(std::make_pair(CacheKey, InitialNLPI)); NonLocalPointerInfo *CacheInfo = &Pair.first->second; + // If we already have a cache entry for this CacheKey, we may need to do some + // work to reconcile the cache entry and the current query. if (!Pair.second) { - // If this query's Size is inconsistent with the cached one, take the - // maximum size and restart the query. - if (CacheInfo->Size != Loc.Size) { - CacheInfo->Size = std::max(CacheInfo->Size, Loc.Size); + if (CacheInfo->Size < Loc.Size) { + // The query's Size is greater than the cached one. Throw out the + // cached data and procede with the query at the greater 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) { + // This query's Size is less than the cached one. Conservatively restart + // the query using the greater size. return getNonLocalPointerDepFromBB(Pointer, Loc.getWithNewSize(CacheInfo->Size), isLoad, StartBB, Result, Visited, SkipFirstBlock); } - // If this query's TBAATag is inconsistent with the cached one, discard the - // tag and restart the query. + // If the query's TBAATag is inconsistent with the cached one, + // conservatively throw out the cached data and restart the query with + // no tag if needed. if (CacheInfo->TBAATag != Loc.TBAATag) { - CacheInfo->TBAATag = 0; - return getNonLocalPointerDepFromBB(Pointer, Loc.getWithoutTBAATag(), - isLoad, StartBB, Result, Visited, - SkipFirstBlock); + 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); } } @@ -818,11 +847,8 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, // otherwise it isn't. if (Cache->empty()) CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock); - else { + else CacheInfo->Pair = BBSkipFirstBlockPair(); - CacheInfo->Size = 0; - CacheInfo->TBAATag = 0; - } SmallVector Worklist; Worklist.push_back(StartBB); @@ -946,8 +972,6 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, // cached value to do more work but not miss the phi trans failure. NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey]; NLPI.Pair = BBSkipFirstBlockPair(); - NLPI.Size = 0; - NLPI.TBAATag = 0; continue; } @@ -975,8 +999,6 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, // specific block queries) but we can't do the fastpath "return all // results from the set" Clear out the indicator for this. CacheInfo->Pair = BBSkipFirstBlockPair(); - CacheInfo->Size = 0; - CacheInfo->TBAATag = 0; SkipFirstBlock = false; continue; @@ -994,8 +1016,6 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, // specific block queries) but we can't do the fastpath "return all // results from the set". Clear out the indicator for this. CacheInfo->Pair = BBSkipFirstBlockPair(); - CacheInfo->Size = 0; - CacheInfo->TBAATag = 0; // If *nothing* works, mark the pointer as being clobbered by the first // instruction in this block. @@ -1212,8 +1232,6 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { // The cache is not valid for any specific block anymore. NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair(); - NonLocalPointerDeps[P].Size = 0; - NonLocalPointerDeps[P].TBAATag = 0; // Update any entries for RemInst to use the instruction after it. for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();