X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FMemoryDependenceAnalysis.cpp;h=9872890494556e61a132acce9e0defcd736c29f9;hb=8dbac7b529cfb73bcd0ceef514e5c1d247cf3baa;hp=34ba92509e57c8e1b4591670e3f28a918f38bacd;hpb=db125cfaf57cc83e7dd7453de2d509bc8efd0e5e;p=oota-llvm.git diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index 34ba92509e5..98728904945 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -16,7 +16,6 @@ #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" @@ -31,7 +30,7 @@ #include "llvm/ADT/STLExtras.h" #include "llvm/Support/PredIteratorCache.h" #include "llvm/Support/Debug.h" -#include "llvm/Target/TargetData.h" +#include "llvm/DataLayout.h" using namespace llvm; STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses"); @@ -90,7 +89,8 @@ void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { bool MemoryDependenceAnalysis::runOnFunction(Function &) { AA = &getAnalysis(); - TD = getAnalysisIfAvailable(); + TD = getAnalysisIfAvailable(); + DT = getAnalysisIfAvailable(); if (PredCache == 0) PredCache.reset(new PredIteratorCache()); return false; @@ -120,21 +120,27 @@ AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst, AliasAnalysis::Location &Loc, AliasAnalysis *AA) { if (const LoadInst *LI = dyn_cast(Inst)) { - if (LI->isVolatile()) { - Loc = AliasAnalysis::Location(); + if (LI->isUnordered()) { + Loc = AA->getLocation(LI); + return AliasAnalysis::Ref; + } else if (LI->getOrdering() == Monotonic) { + Loc = AA->getLocation(LI); return AliasAnalysis::ModRef; } - Loc = AA->getLocation(LI); - return AliasAnalysis::Ref; + Loc = AliasAnalysis::Location(); + return AliasAnalysis::ModRef; } if (const StoreInst *SI = dyn_cast(Inst)) { - if (SI->isVolatile()) { - Loc = AliasAnalysis::Location(); + if (SI->isUnordered()) { + Loc = AA->getLocation(SI); + return AliasAnalysis::Mod; + } else if (SI->getOrdering() == Monotonic) { + Loc = AA->getLocation(SI); return AliasAnalysis::ModRef; } - Loc = AA->getLocation(SI); - return AliasAnalysis::Mod; + Loc = AliasAnalysis::Location(); + return AliasAnalysis::ModRef; } if (const VAArgInst *V = dyn_cast(Inst)) { @@ -142,7 +148,7 @@ AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst, return AliasAnalysis::ModRef; } - if (const CallInst *CI = isFreeCall(Inst)) { + if (const CallInst *CI = isFreeCall(Inst, AA->getTargetLibraryInfo())) { // calls to free() deallocate the entire structure Loc = AliasAnalysis::Location(CI->getArgOperand(0)); return AliasAnalysis::Mod; @@ -221,18 +227,23 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, // Otherwise if the two calls don't interact (e.g. InstCS is readnone) // keep scanning. - break; + continue; default: return MemDepResult::getClobber(Inst); } } + + // If we could not obtain a pointer for the instruction and the instruction + // touches memory then assume that this is a dependency. + if (MR != AliasAnalysis::NoModRef) + return MemDepResult::getClobber(Inst); } - + // No dependence found. If this is the entry block of the function, it is // unknown, otherwise it is non-local. if (BB != &BB->getParent()->getEntryBlock()) return MemDepResult::getNonLocal(); - return MemDepResult::getUnknown(); + return MemDepResult::getNonFuncLocal(); } /// isLoadLoadClobberIfExtendedToFullWidth - Return true if LI is a load that @@ -245,7 +256,7 @@ isLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc, const Value *&MemLocBase, int64_t &MemLocOffs, const LoadInst *LI, - const TargetData *TD) { + const DataLayout *TD) { // If we have no target data, we can't do this. if (TD == 0) return false; @@ -269,9 +280,9 @@ isLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc, unsigned MemoryDependenceAnalysis:: getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs, unsigned MemLocSize, const LoadInst *LI, - const TargetData &TD) { - // We can only extend non-volatile integer loads. - if (!isa(LI->getType()) || LI->isVolatile()) return 0; + const DataLayout &TD) { + // We can only extend simple integer loads. + if (!isa(LI->getType()) || !LI->isSimple()) return 0; // Get the base of this load. int64_t LIOffs = 0; @@ -315,14 +326,20 @@ getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs, !TD.fitsInLegalInteger(NewLoadByteSize*8)) return 0; + if (LIOffs+NewLoadByteSize > MemLocEnd && + LI->getParent()->getParent()->getFnAttributes(). + hasAttribute(Attributes::AddressSafety)) + // We will be reading past the location accessed by the original program. + // While this is safe in a regular build, Address Safety analysis tools + // may start reporting false warnings. So, don't do widening. + return 0; + // If a load of this width would include all of MemLoc, then we succeed. if (LIOffs+NewLoadByteSize >= MemLocEnd) return NewLoadByteSize; NewLoadByteSize <<= 1; } - - return 0; } /// getPointerDependencyFrom - Return the instruction on which a memory @@ -369,6 +386,11 @@ 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)) { + // Atomic loads have complications involved. + // FIXME: This is overly conservative. + if (!LI->isUnordered()) + return MemDepResult::getClobber(LI); + AliasAnalysis::Location LoadLoc = AA->getLocation(LI); // If we found a pointer, check if it could be the same as our pointer. @@ -424,6 +446,11 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, } if (StoreInst *SI = dyn_cast(Inst)) { + // Atomic stores have complications involved. + // FIXME: This is overly conservative. + if (!SI->isUnordered()) + return MemDepResult::getClobber(SI); + // If alias analysis can tell that this store is guaranteed to not modify // the query pointer, ignore it. Use getModRefInfo to handle cases where // the query pointer points to constant memory etc. @@ -452,17 +479,28 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // 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(Inst) || - (isa(Inst) && extractMallocCall(Inst))) { + const TargetLibraryInfo *TLI = AA->getTargetLibraryInfo(); + if (isa(Inst) || isNoAliasFn(Inst, TLI)) { const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, TD); if (AccessPtr == Inst || AA->isMustAlias(Inst, AccessPtr)) return MemDepResult::getDef(Inst); - continue; + // Be conservative if the accessed pointer may alias the allocation. + if (AA->alias(Inst, AccessPtr) != AliasAnalysis::NoAlias) + return MemDepResult::getClobber(Inst); + // If the allocation is not aliased and does not read memory (like + // strdup), it is safe to ignore. + if (isa(Inst) || + isMallocLikeFn(Inst, TLI) || isCallocLikeFn(Inst, TLI)) + continue; } // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer. - switch (AA->getModRefInfo(Inst, MemLoc)) { + AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc); + // If necessary, perform additional analysis. + if (MR == AliasAnalysis::ModRef) + MR = AA->callCapturesBefore(Inst, MemLoc, DT); + switch (MR) { case AliasAnalysis::NoModRef: // If the call has no effect on the queried pointer, just ignore it. continue; @@ -483,7 +521,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // unknown, otherwise it is non-local. if (BB != &BB->getParent()->getEntryBlock()) return MemDepResult::getNonLocal(); - return MemDepResult::getUnknown(); + return MemDepResult::getNonFuncLocal(); } /// getDependency - Return the instruction on which a memory operation @@ -516,7 +554,7 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { if (QueryParent != &QueryParent->getParent()->getEntryBlock()) LocalCache = MemDepResult::getNonLocal(); else - LocalCache = MemDepResult::getUnknown(); + LocalCache = MemDepResult::getNonFuncLocal(); } else { AliasAnalysis::Location MemLoc; AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA); @@ -672,7 +710,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { // a clobber, otherwise it is unknown. Dep = MemDepResult::getNonLocal(); } else { - Dep = MemDepResult::getUnknown(); + Dep = MemDepResult::getNonFuncLocal(); } // If we had a dirty entry for the block, update it. Otherwise, just add @@ -790,7 +828,7 @@ GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc, // If the block has a dependency (i.e. it isn't completely transparent to // the value), remember the reverse association because we just added it // to Cache! - if (Dep.isNonLocal() || Dep.isUnknown()) + if (!Dep.isDef() && !Dep.isClobber()) return Dep; // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently @@ -880,7 +918,7 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, if (!Pair.second) { 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. + // cached data and proceed with the query at the greater size. CacheInfo->Pair = BBSkipFirstBlockPair(); CacheInfo->Size = Loc.Size; for (NonLocalDepInfo::iterator DI = CacheInfo->NonLocalDeps.begin(), @@ -945,7 +983,7 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end(); I != E; ++I) { Visited.insert(std::make_pair(I->getBB(), Addr)); - if (!I->getResult().isNonLocal()) + if (!I->getResult().isNonLocal() && DT->isReachableFromEntry(I->getBB())) Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr)); } ++NumCacheCompleteNonLocalPtr; @@ -991,7 +1029,7 @@ getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, NumSortedEntries); // If we got a Def or Clobber, add this to the list of results. - if (!Dep.isNonLocal()) { + if (!Dep.isNonLocal() && DT->isReachableFromEntry(BB)) { Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr())); continue; }