X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FMemoryDependenceAnalysis.cpp;h=9872890494556e61a132acce9e0defcd736c29f9;hb=7372a7d5f87bf1ff65d07f25bae037ddc4df994d;hp=21baf427ea456f1c073f62d2fe6e63b1d05051d1;hpb=366429b400c9ec41fbba7c24ed7d0a100e421136;p=oota-llvm.git diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index 21baf427ea4..98728904945 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -19,14 +19,18 @@ #include "llvm/Instructions.h" #include "llvm/IntrinsicInst.h" #include "llvm/Function.h" +#include "llvm/LLVMContext.h" #include "llvm/Analysis/AliasAnalysis.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/DataLayout.h" using namespace llvm; STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses"); @@ -42,14 +46,23 @@ STATISTIC(NumUncacheNonLocalPtr, STATISTIC(NumCacheCompleteNonLocalPtr, "Number of block queries that were completely cached"); +// Limit for the number of instructions to scan in a block. +// FIXME: Figure out what a sane value is for this. +// (500 is relatively insane.) +static const int BlockScanLimit = 500; + char MemoryDependenceAnalysis::ID = 0; // Register this pass... -static RegisterPass X("memdep", - "Memory Dependence Analysis", false, true); +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) { +: FunctionPass(ID), PredCache(0) { + initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry()); } MemoryDependenceAnalysis::~MemoryDependenceAnalysis() { } @@ -76,6 +89,8 @@ void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { bool MemoryDependenceAnalysis::runOnFunction(Function &) { AA = &getAnalysis(); + TD = getAnalysisIfAvailable(); + DT = getAnalysisIfAvailable(); if (PredCache == 0) PredCache.reset(new PredIteratorCache()); return false; @@ -91,180 +106,369 @@ 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->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(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(Inst)) { + Loc = AA->getLocation(V); + return AliasAnalysis::ModRef; + } + + if (const CallInst *CI = isFreeCall(Inst, AA->getTargetLibraryInfo())) { + // 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. MemDepResult MemoryDependenceAnalysis:: getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, BasicBlock::iterator ScanIt, BasicBlock *BB) { + unsigned Limit = BlockScanLimit; + // Walk backwards through the block, looking for dependencies while (ScanIt != BB->begin()) { + // Limit the amount of scanning we do so we don't end up with quadratic + // running time on extreme testcases. + --Limit; + if (!Limit) + return MemDepResult::getUnknown(); + Instruction *Inst = --ScanIt; // If this inst is a memory op, get the pointer it accessed - Value *Pointer = 0; - uint64_t PointerSize = 0; - if (StoreInst *S = dyn_cast(Inst)) { - Pointer = S->getPointerOperand(); - PointerSize = AA->getTypeStoreSize(S->getOperand(0)->getType()); - } else if (VAArgInst *V = dyn_cast(Inst)) { - Pointer = V->getOperand(0); - PointerSize = AA->getTypeStoreSize(V->getType()); - } else if (isFreeCall(Inst)) { - Pointer = Inst->getOperand(1); - // calls to free() erase the entire structure - PointerSize = ~0ULL; - } else if (isa(Inst) || isa(Inst)) { + AliasAnalysis::Location Loc; + 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; - CallSite InstCS = CallSite::get(Inst); // If these two calls do not interfere, look past it. switch (AA->getModRefInfo(CS, InstCS)) { case AliasAnalysis::NoModRef: - // If the two calls don't interact (e.g. InstCS is readnone) keep - // scanning. + // If the two calls are the same, return InstCS as a Def, so that + // CS can be found redundant and eliminated. + 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; - case AliasAnalysis::Ref: - // If the two calls read the same memory locations and CS is a readonly - // function, then we have two cases: 1) the calls may not interfere with - // each other at all. 2) the calls may produce the same value. In case - // #1 we want to ignore the values, in case #2, we want to return Inst - // as a Def dependence. This allows us to CSE in cases like: - // X = strlen(P); - // memchr(...); - // Y = strlen(P); // Y = X - if (isReadOnlyCall) { - if (CS.getCalledFunction() != 0 && - CS.getCalledFunction() == InstCS.getCalledFunction()) - return MemDepResult::getDef(Inst); - // Ignore unrelated read/read call dependences. - continue; - } - // FALL THROUGH default: return MemDepResult::getClobber(Inst); } - } else { - // Non-memory instruction. - continue; } - - if (AA->getModRefInfo(CS, Pointer, PointerSize) != AliasAnalysis::NoModRef) + + // 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 a - // clobber, otherwise it is non-local. + + // 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::getClobber(ScanIt); + return MemDepResult::getNonFuncLocal(); +} + +/// isLoadLoadClobberIfExtendedToFullWidth - Return true if LI is a load that +/// would fully overlap MemLoc if done as a wider legal integer load. +/// +/// MemLocBase, MemLocOffset are lazily computed here the first time the +/// base/offs of memloc is needed. +static bool +isLoadLoadClobberIfExtendedToFullWidth(const AliasAnalysis::Location &MemLoc, + const Value *&MemLocBase, + int64_t &MemLocOffs, + const LoadInst *LI, + const DataLayout *TD) { + // If we have no target data, we can't do this. + if (TD == 0) return false; + + // If we haven't already computed the base/offset of MemLoc, do so now. + if (MemLocBase == 0) + MemLocBase = GetPointerBaseWithConstantOffset(MemLoc.Ptr, MemLocOffs, *TD); + + unsigned Size = MemoryDependenceAnalysis:: + getLoadLoadClobberFullWidthSize(MemLocBase, MemLocOffs, MemLoc.Size, + LI, *TD); + return Size != 0; +} + +/// getLoadLoadClobberFullWidthSize - This is a little bit of analysis that +/// looks at a memory location for a load (specified by MemLocBase, Offs, +/// and Size) and compares it against a load. If the specified load could +/// be safely widened to a larger integer load that is 1) still efficient, +/// 2) safe for the target, and 3) would provide the specified memory +/// location value, then this function returns the size in bytes of the +/// load width to use. If not, this returns zero. +unsigned MemoryDependenceAnalysis:: +getLoadLoadClobberFullWidthSize(const Value *MemLocBase, int64_t MemLocOffs, + unsigned MemLocSize, const LoadInst *LI, + 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; + const Value *LIBase = + GetPointerBaseWithConstantOffset(LI->getPointerOperand(), LIOffs, TD); + + // If the two pointers are not based on the same pointer, we can't tell that + // they are related. + if (LIBase != MemLocBase) return 0; + + // Okay, the two values are based on the same pointer, but returned as + // no-alias. This happens when we have things like two byte loads at "P+1" + // and "P+3". Check to see if increasing the size of the "LI" load up to its + // alignment (or the largest native integer type) will allow us to load all + // the bits required by MemLoc. + + // If MemLoc is before LI, then no widening of LI will help us out. + if (MemLocOffs < LIOffs) return 0; + + // Get the alignment of the load in bytes. We assume that it is safe to load + // any legal integer up to this size without a problem. For example, if we're + // looking at an i8 load on x86-32 that is known 1024 byte aligned, we can + // widen it up to an i32 load. If it is known 2-byte aligned, we can widen it + // to i16. + unsigned LoadAlign = LI->getAlignment(); + + int64_t MemLocEnd = MemLocOffs+MemLocSize; + + // If no amount of rounding up will let MemLoc fit into LI, then bail out. + if (LIOffs+LoadAlign < MemLocEnd) return 0; + + // This is the size of the load to try. Start with the next larger power of + // two. + unsigned NewLoadByteSize = LI->getType()->getPrimitiveSizeInBits()/8U; + NewLoadByteSize = NextPowerOf2(NewLoadByteSize); + + while (1) { + // If this load size is bigger than our known alignment or would not fit + // into a native integer register, then we fail. + if (NewLoadByteSize > LoadAlign || + !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; + } } /// getPointerDependencyFrom - Return the instruction on which a memory -/// location depends. If isLoad is true, this routine ignore may-aliases with -/// read-only operations. +/// location depends. If isLoad is true, this routine ignores may-aliases with +/// read-only operations. If isLoad is false, this routine ignores may-aliases +/// with reads from read-only locations. MemDepResult MemoryDependenceAnalysis:: -getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad, +getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB) { - Value *invariantTag = 0; + const Value *MemLocBase = 0; + int64_t MemLocOffset = 0; + + unsigned Limit = BlockScanLimit; // Walk backwards through the basic block, looking for dependencies. while (ScanIt != BB->begin()) { + // Limit the amount of scanning we do so we don't end up with quadratic + // running time on extreme testcases. + --Limit; + if (!Limit) + return MemDepResult::getUnknown(); + Instruction *Inst = --ScanIt; - // If we're in an invariant region, no dependencies can be found before - // we pass an invariant-begin marker. - if (invariantTag == Inst) { - invariantTag = 0; - continue; - } else if (IntrinsicInst *II = dyn_cast(Inst)) { - // If we pass an invariant-end marker, then we've just entered an - // invariant region and can start ignoring dependencies. - if (II->getIntrinsicID() == Intrinsic::invariant_end) { - uint64_t invariantSize = ~0ULL; - if (ConstantInt *CI = dyn_cast(II->getOperand(2))) - invariantSize = CI->getZExtValue(); - - AliasAnalysis::AliasResult R = - AA->alias(II->getOperand(3), invariantSize, MemPtr, MemSize); - if (R == AliasAnalysis::MustAlias) { - invariantTag = II->getOperand(1); - continue; - } + if (IntrinsicInst *II = dyn_cast(Inst)) { + // Debug intrinsics don't (and can't) cause dependences. + if (isa(II)) continue; // If we reach a lifetime begin or end marker, then the query ends here // because the value is undefined. - } else if (II->getIntrinsicID() == Intrinsic::lifetime_start || - II->getIntrinsicID() == Intrinsic::lifetime_end) { - uint64_t invariantSize = ~0ULL; - if (ConstantInt *CI = dyn_cast(II->getOperand(1))) - invariantSize = CI->getZExtValue(); - - AliasAnalysis::AliasResult R = - AA->alias(II->getOperand(2), invariantSize, MemPtr, MemSize); - if (R == AliasAnalysis::MustAlias) + if (II->getIntrinsicID() == Intrinsic::lifetime_start) { + // FIXME: This only considers queries directly on the invariant-tagged + // pointer, not on query pointers that are indexed off of them. It'd + // be nice to handle that at some point (the right approach is to use + // GetPointerBaseWithConstantOffset). + if (AA->isMustAlias(AliasAnalysis::Location(II->getArgOperand(1)), + MemLoc)) return MemDepResult::getDef(II); + continue; } } - // If we're querying on a load and we're in an invariant region, we're done - // at this point. Nothing a load depends on can live in an invariant region. - if (isLoad && invariantTag) continue; - - // Debug intrinsics don't cause dependences. - if (isa(Inst)) continue; - // 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()); + // 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. - AliasAnalysis::AliasResult R = - AA->alias(Pointer, PointerSize, MemPtr, MemSize); + AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc); + + if (isLoad) { + if (R == AliasAnalysis::NoAlias) { + // If this is an over-aligned integer load (for example, + // "load i8* %P, align 4") see if it would obviously overlap with the + // queried location if widened to a larger load (e.g. if the queried + // location is 1 byte at P+1). If so, return it as a load/load + // clobber result, allowing the client to decide to widen the load if + // it wants to. + if (IntegerType *ITy = dyn_cast(LI->getType())) + if (LI->getAlignment()*8 > ITy->getPrimitiveSizeInBits() && + isLoadLoadClobberIfExtendedToFullWidth(MemLoc, MemLocBase, + MemLocOffset, LI, TD)) + return MemDepResult::getClobber(Inst); + + continue; + } + + // Must aliased loads are defs of each other. + if (R == AliasAnalysis::MustAlias) + return MemDepResult::getDef(Inst); + +#if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads + // in terms of clobbering loads, but since it does this by looking + // at the clobbering load directly, it doesn't know about any + // phi translation that may have happened along the way. + + // If we have a partial alias, then return this as a clobber for the + // client to handle. + if (R == AliasAnalysis::PartialAlias) + return MemDepResult::getClobber(Inst); +#endif + + // Random may-alias loads don't depend on each other without a + // dependence. + continue; + } + + // Stores don't depend on other no-aliased accesses. if (R == AliasAnalysis::NoAlias) continue; - - // May-alias loads don't depend on each other without a dependence. - if (isLoad && R == AliasAnalysis::MayAlias) + + // Stores don't alias loads from read-only memory. + if (AA->pointsToConstantMemory(LoadLoc)) continue; - // Stores depend on may and must aliased loads, loads depend on must-alias - // loads. + + // Stores depend on may/must aliased loads. return MemDepResult::getDef(Inst); } if (StoreInst *SI = dyn_cast(Inst)) { - // There can't be stores to the value we care about inside an - // invariant region. - if (invariantTag) continue; - + // 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. - if (AA->getModRefInfo(SI, MemPtr, MemSize) == AliasAnalysis::NoModRef) + if (AA->getModRefInfo(SI, MemLoc) == AliasAnalysis::NoModRef) continue; // 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()); + 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(Pointer, PointerSize, MemPtr, MemSize); + 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 @@ -275,24 +479,32 @@ getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, 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) || extractMallocCall(Inst)) { - Value *AccessPtr = MemPtr->getUnderlyingObject(); + const TargetLibraryInfo *TLI = AA->getTargetLibraryInfo(); + if (isa(Inst) || isNoAliasFn(Inst, TLI)) { + const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, TD); - if (AccessPtr == Inst || - AA->alias(Inst, 1, AccessPtr, 1) == AliasAnalysis::MustAlias) + 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, MemPtr, MemSize)) { + 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; case AliasAnalysis::Mod: - // If we're in an invariant region, we can ignore calls that ONLY - // modify the pointer. - if (invariantTag) continue; return MemDepResult::getClobber(Inst); case AliasAnalysis::Ref: // If the call is known to never store to the pointer, and if this is a @@ -305,11 +517,11 @@ getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad, } } - // No dependence found. If this is the entry block of the function, it is a - // clobber, otherwise it is non-local. + // 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::getClobber(ScanIt); + return MemDepResult::getNonFuncLocal(); } /// getDependency - Return the instruction on which a memory operation @@ -335,74 +547,33 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { BasicBlock *QueryParent = QueryInst->getParent(); - Value *MemPtr = 0; - uint64_t MemSize = 0; - // Do the scan. if (BasicBlock::iterator(QueryInst) == QueryParent->begin()) { - // No dependence found. If this is the entry block of the function, it is a - // clobber, otherwise it is non-local. + // No dependence found. If this is the entry block of the function, it is + // unknown, otherwise it is non-local. if (QueryParent != &QueryParent->getParent()->getEntryBlock()) 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 { - MemPtr = SI->getPointerOperand(); - MemSize = AA->getTypeStoreSize(SI->getOperand(0)->getType()); - } - } 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 { - MemPtr = LI->getPointerOperand(); - MemSize = AA->getTypeStoreSize(LI->getType()); - } - } else if (isFreeCall(QueryInst)) { - MemPtr = QueryInst->getOperand(1); - // calls to free() erase the entire structure, not just a field. - MemSize = ~0UL; - } else if (isa(QueryInst) || isa(QueryInst)) { - int IntrinsicID = 0; // Intrinsic IDs start at 1. - if (IntrinsicInst *II = dyn_cast(QueryInst)) - IntrinsicID = II->getIntrinsicID(); - - switch (IntrinsicID) { - case Intrinsic::lifetime_start: - case Intrinsic::lifetime_end: - case Intrinsic::invariant_start: - MemPtr = QueryInst->getOperand(2); - MemSize = cast(QueryInst->getOperand(1))->getZExtValue(); - break; - case Intrinsic::invariant_end: - MemPtr = QueryInst->getOperand(3); - MemSize = cast(QueryInst->getOperand(2))->getZExtValue(); - break; - default: - CallSite QueryCS = CallSite::get(QueryInst); - bool isReadOnly = AA->onlyReadsMemory(QueryCS); - LocalCache = getCallSiteDependencyFrom(QueryCS, isReadOnly, ScanPos, - QueryParent); - } + LocalCache = MemDepResult::getNonFuncLocal(); } else { - // Non-memory instruction. - LocalCache = MemDepResult::getClobber(--BasicBlock::iterator(ScanPos)); - } - - // If we need to do a pointer scan, make it happen. - if (MemPtr) { - bool isLoad = !QueryInst->mayWriteToMemory(); - if (IntrinsicInst *II = dyn_cast(QueryInst)) { - isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_end; - } - LocalCache = getPointerDependencyFrom(MemPtr, MemSize, isLoad, ScanPos, - QueryParent); + 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_start; + + 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); + } else + // Non-memory instruction. + LocalCache = MemDepResult::getUnknown(); } // Remember the result! @@ -421,7 +592,7 @@ static void AssertSorted(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, if (Count == 0) return; for (unsigned i = 1; i != unsigned(Count); ++i) - assert(Cache[i-1] <= Cache[i] && "Cache isn't sorted!"); + assert(!(Cache[i] < Cache[i-1]) && "Cache isn't sorted!"); } #endif @@ -454,7 +625,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { // 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; } @@ -462,8 +633,8 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { // determine what is dirty, seeding our initial DirtyBlocks worklist. for (NonLocalDepInfo::iterator I = Cache.begin(), E = Cache.end(); I != E; ++I) - if (I->second.isDirty()) - DirtyBlocks.push_back(I->first); + if (I->getResult().isDirty()) + DirtyBlocks.push_back(I->getBB()); // Sort the cache so that we can do fast binary search lookups below. std::sort(Cache.begin(), Cache.end()); @@ -476,7 +647,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { 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. @@ -501,27 +672,27 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { 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) + NonLocalDepEntry(DirtyBB)); + if (Entry != Cache.begin() && prior(Entry)->getBB() == DirtyBB) --Entry; - MemDepResult *ExistingResult = 0; + NonLocalDepEntry *ExistingResult = 0; if (Entry != Cache.begin()+NumSortedEntries && - Entry->first == DirtyBB) { + Entry->getBB() == DirtyBB) { // If we already have an entry, and if it isn't already dirty, the block // is done. - if (!Entry->second.isDirty()) + if (!Entry->getResult().isDirty()) continue; // Otherwise, remember this slot so we can update the value. - ExistingResult = &Entry->second; + ExistingResult = &*Entry; } // If the dirty entry has a pointer, start scanning from it so we don't have // to rescan the entire block. BasicBlock::iterator ScanPos = DirtyBB->end(); if (ExistingResult) { - if (Instruction *Inst = ExistingResult->getInst()) { + if (Instruction *Inst = ExistingResult->getResult().getInst()) { ScanPos = Inst; // We're removing QueryInst's use of Inst. RemoveFromReverseMap(ReverseNonLocalDeps, Inst, @@ -536,18 +707,18 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { Dep = getCallSiteDependencyFrom(QueryCS, isReadonlyCall,ScanPos, DirtyBB); } else if (DirtyBB != &DirtyBB->getParent()->getEntryBlock()) { // No dependence found. If this is the entry block of the function, it is - // a clobber, otherwise it is non-local. + // a clobber, otherwise it is unknown. Dep = MemDepResult::getNonLocal(); } else { - Dep = MemDepResult::getClobber(ScanPos); + Dep = MemDepResult::getNonFuncLocal(); } // If we had a dirty entry for the block, update it. Otherwise, just add // a new entry. if (ExistingResult) - *ExistingResult = Dep; + ExistingResult->setResult(Dep); else - Cache.push_back(std::make_pair(DirtyBB, Dep)); + Cache.push_back(NonLocalDepEntry(DirtyBB, Dep)); // If the block has a dependency (i.e. it isn't completely transparent to // the value), remember the association! @@ -576,28 +747,27 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { /// own block. /// void MemoryDependenceAnalysis:: -getNonLocalPointerDependency(Value *Pointer, bool isLoad, BasicBlock *FromBB, - SmallVectorImpl &Result) { - assert(isa(Pointer->getType()) && +getNonLocalPointerDependency(const AliasAnalysis::Location &Loc, bool isLoad, + BasicBlock *FromBB, + SmallVectorImpl &Result) { + assert(Loc.Ptr->getType()->isPointerTy() && "Can't get pointer deps of a non-pointer!"); Result.clear(); - // We know that the pointer value is live into FromBB find the def/clobbers - // from presecessors. - const Type *EltTy = cast(Pointer->getType())->getElementType(); - uint64_t PointeeSize = AA->getTypeStoreSize(EltTy); + PHITransAddr Address(const_cast(Loc.Ptr), TD); // This is the set of blocks we've inspected, and the pointer we consider in // each block. Because of critical edges, we currently bail out if querying // a block with multiple different pointers. This can happen during PHI // translation. DenseMap Visited; - if (!getNonLocalPointerDepFromBB(Pointer, PointeeSize, isLoad, FromBB, + if (!getNonLocalPointerDepFromBB(Address, Loc, isLoad, FromBB, Result, Visited, true)) return; Result.clear(); - Result.push_back(std::make_pair(FromBB, - MemDepResult::getClobber(FromBB->begin()))); + Result.push_back(NonLocalDepResult(FromBB, + MemDepResult::getUnknown(), + const_cast(Loc.Ptr))); } /// GetNonLocalInfoForBlock - Compute the memdep value for BB with @@ -605,7 +775,7 @@ getNonLocalPointerDependency(Value *Pointer, bool isLoad, BasicBlock *FromBB, /// lookup (which may use dirty cache info if available). If we do a lookup, /// add the result to the cache. MemDepResult MemoryDependenceAnalysis:: -GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize, +GetNonLocalInfoForBlock(const AliasAnalysis::Location &Loc, bool isLoad, BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries) { @@ -613,60 +783,59 @@ GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize, // the cache set. If so, find it. NonLocalDepInfo::iterator Entry = std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries, - std::make_pair(BB, MemDepResult())); - if (Entry != Cache->begin() && prior(Entry)->first == BB) + NonLocalDepEntry(BB)); + if (Entry != Cache->begin() && (Entry-1)->getBB() == BB) --Entry; - MemDepResult *ExistingResult = 0; - if (Entry != Cache->begin()+NumSortedEntries && Entry->first == BB) - ExistingResult = &Entry->second; + NonLocalDepEntry *ExistingResult = 0; + if (Entry != Cache->begin()+NumSortedEntries && Entry->getBB() == BB) + ExistingResult = &*Entry; // If we have a cached entry, and it is non-dirty, use it as the value for // this dependency. - if (ExistingResult && !ExistingResult->isDirty()) { + if (ExistingResult && !ExistingResult->getResult().isDirty()) { ++NumCacheNonLocalPtr; - return *ExistingResult; + return ExistingResult->getResult(); } // Otherwise, we have to scan for the value. If we have a dirty cache // entry, start scanning from its position, otherwise we scan from the end // of the block. BasicBlock::iterator ScanPos = BB->end(); - if (ExistingResult && ExistingResult->getInst()) { - assert(ExistingResult->getInst()->getParent() == BB && + if (ExistingResult && ExistingResult->getResult().getInst()) { + assert(ExistingResult->getResult().getInst()->getParent() == BB && "Instruction invalidated?"); ++NumCacheDirtyNonLocalPtr; - ScanPos = ExistingResult->getInst(); + ScanPos = ExistingResult->getResult().getInst(); // Eliminating the dirty entry from 'Cache', so update the reverse info. - ValueIsLoadPair CacheKey(Pointer, isLoad); + ValueIsLoadPair CacheKey(Loc.Ptr, isLoad); RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos, CacheKey); } else { ++NumUncacheNonLocalPtr; } // Scan the block for the dependency. - MemDepResult Dep = getPointerDependencyFrom(Pointer, PointeeSize, isLoad, - ScanPos, BB); + MemDepResult Dep = getPointerDependencyFrom(Loc, isLoad, ScanPos, BB); // If we had a dirty entry for the block, update it. Otherwise, just add // a new entry. if (ExistingResult) - *ExistingResult = Dep; + ExistingResult->setResult(Dep); else - Cache->push_back(std::make_pair(BB, Dep)); + Cache->push_back(NonLocalDepEntry(BB, Dep)); // 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()) + if (!Dep.isDef() && !Dep.isClobber()) return Dep; // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently // update MemDep when we remove instructions. Instruction *Inst = Dep.getInst(); assert(Inst && "Didn't depend on anything?"); - ValueIsLoadPair CacheKey(Pointer, isLoad); + ValueIsLoadPair CacheKey(Loc.Ptr, isLoad); ReverseNonLocalPtrDeps[Inst].insert(CacheKey); return Dep; } @@ -683,7 +852,7 @@ SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, break; case 2: { // Two new entries, insert the last one into place. - MemoryDependenceAnalysis::NonLocalDepEntry Val = Cache.back(); + NonLocalDepEntry Val = Cache.back(); Cache.pop_back(); MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry = std::upper_bound(Cache.begin(), Cache.end()-1, Val); @@ -693,7 +862,7 @@ SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, case 1: // One new entry, Just insert the new value at the appropriate position. if (Cache.size() != 1) { - MemoryDependenceAnalysis::NonLocalDepEntry Val = Cache.back(); + NonLocalDepEntry Val = Cache.back(); Cache.pop_back(); MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry = std::upper_bound(Cache.begin(), Cache.end(), Val); @@ -707,275 +876,6 @@ SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, } } -/// isPHITranslatable - Return true if the specified computation is derived from -/// a PHI node in the current block and if it is simple enough for us to handle. -static bool isPHITranslatable(Instruction *Inst) { - if (isa(Inst)) - return true; - - // We can handle bitcast of a PHI, but the PHI needs to be in the same block - // as the bitcast. - if (BitCastInst *BC = dyn_cast(Inst)) { - Instruction *OpI = dyn_cast(BC->getOperand(0)); - if (OpI == 0 || OpI->getParent() != Inst->getParent()) - return true; - return isPHITranslatable(OpI); - } - - // We can translate a GEP if all of its operands defined in this block are phi - // translatable. - if (GetElementPtrInst *GEP = dyn_cast(Inst)) { - for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) { - Instruction *OpI = dyn_cast(GEP->getOperand(i)); - if (OpI == 0 || OpI->getParent() != Inst->getParent()) - continue; - - if (!isPHITranslatable(OpI)) - return false; - } - return true; - } - - if (Inst->getOpcode() == Instruction::Add && - isa(Inst->getOperand(1))) { - Instruction *OpI = dyn_cast(Inst->getOperand(0)); - if (OpI == 0 || OpI->getParent() != Inst->getParent()) - return true; - return isPHITranslatable(OpI); - } - - // cerr << "MEMDEP: Could not PHI translate: " << *Pointer; - // if (isa(PtrInst) || isa(PtrInst)) - // cerr << "OP:\t\t\t\t" << *PtrInst->getOperand(0); - - return false; -} - -/// GetPHITranslatedValue - Given a computation that satisfied the -/// isPHITranslatable predicate, see if we can translate the computation into -/// the specified predecessor block. If so, return that value. -Value *MemoryDependenceAnalysis:: -GetPHITranslatedValue(Value *InVal, BasicBlock *CurBB, BasicBlock *Pred, - const TargetData *TD) const { - // If the input value is not an instruction, or if it is not defined in CurBB, - // then we don't need to phi translate it. - Instruction *Inst = dyn_cast(InVal); - if (Inst == 0 || Inst->getParent() != CurBB) - return InVal; - - if (PHINode *PN = dyn_cast(Inst)) - return PN->getIncomingValueForBlock(Pred); - - // Handle bitcast of PHI. - if (BitCastInst *BC = dyn_cast(Inst)) { - // PHI translate the input operand. - Value *PHIIn = GetPHITranslatedValue(BC->getOperand(0), CurBB, Pred, TD); - if (PHIIn == 0) return 0; - - // Constants are trivial to phi translate. - if (Constant *C = dyn_cast(PHIIn)) - return ConstantExpr::getBitCast(C, BC->getType()); - - // Otherwise we have to see if a bitcasted version of the incoming pointer - // is available. If so, we can use it, otherwise we have to fail. - for (Value::use_iterator UI = PHIIn->use_begin(), E = PHIIn->use_end(); - UI != E; ++UI) { - if (BitCastInst *BCI = dyn_cast(*UI)) - if (BCI->getType() == BC->getType()) - return BCI; - } - return 0; - } - - // Handle getelementptr with at least one PHI translatable operand. - if (GetElementPtrInst *GEP = dyn_cast(Inst)) { - SmallVector GEPOps; - BasicBlock *CurBB = GEP->getParent(); - for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) { - Value *GEPOp = GEP->getOperand(i); - // No PHI translation is needed of operands whose values are live in to - // the predecessor block. - if (!isa(GEPOp) || - cast(GEPOp)->getParent() != CurBB) { - GEPOps.push_back(GEPOp); - continue; - } - - // If the operand is a phi node, do phi translation. - Value *InOp = GetPHITranslatedValue(GEPOp, CurBB, Pred, TD); - if (InOp == 0) return 0; - - GEPOps.push_back(InOp); - } - - // Simplify the GEP to handle 'gep x, 0' -> x etc. - if (Value *V = SimplifyGEPInst(&GEPOps[0], GEPOps.size(), TD)) - return V; - - // Scan to see if we have this GEP available. - Value *APHIOp = GEPOps[0]; - for (Value::use_iterator UI = APHIOp->use_begin(), E = APHIOp->use_end(); - UI != E; ++UI) { - if (GetElementPtrInst *GEPI = dyn_cast(*UI)) - if (GEPI->getType() == GEP->getType() && - GEPI->getNumOperands() == GEPOps.size() && - GEPI->getParent()->getParent() == CurBB->getParent()) { - bool Mismatch = false; - for (unsigned i = 0, e = GEPOps.size(); i != e; ++i) - if (GEPI->getOperand(i) != GEPOps[i]) { - Mismatch = true; - break; - } - if (!Mismatch) - return GEPI; - } - } - return 0; - } - - // Handle add with a constant RHS. - if (Inst->getOpcode() == Instruction::Add && - isa(Inst->getOperand(1))) { - // PHI translate the LHS. - Value *LHS; - Constant *RHS = cast(Inst->getOperand(1)); - Instruction *OpI = dyn_cast(Inst->getOperand(0)); - bool isNSW = cast(Inst)->hasNoSignedWrap(); - bool isNUW = cast(Inst)->hasNoUnsignedWrap(); - - if (OpI == 0 || OpI->getParent() != Inst->getParent()) - LHS = Inst->getOperand(0); - else { - LHS = GetPHITranslatedValue(Inst->getOperand(0), CurBB, Pred, TD); - if (LHS == 0) - return 0; - } - - // If the PHI translated LHS is an add of a constant, fold the immediates. - if (BinaryOperator *BOp = dyn_cast(LHS)) - if (BOp->getOpcode() == Instruction::Add) - if (ConstantInt *CI = dyn_cast(BOp->getOperand(1))) { - LHS = BOp->getOperand(0); - RHS = ConstantExpr::getAdd(RHS, CI); - isNSW = isNUW = false; - } - - // See if the add simplifies away. - if (Value *Res = SimplifyAddInst(LHS, RHS, isNSW, isNUW, TD)) - return Res; - - // Otherwise, see if we have this add available somewhere. - for (Value::use_iterator UI = LHS->use_begin(), E = LHS->use_end(); - UI != E; ++UI) { - if (BinaryOperator *BO = dyn_cast(*UI)) - if (BO->getOperand(0) == LHS && BO->getOperand(1) == RHS && - BO->getParent()->getParent() == CurBB->getParent()) - return BO; - } - - return 0; - } - - return 0; -} - -/// GetAvailablePHITranslatePointer - Return the value computed by -/// PHITranslatePointer if it dominates PredBB, otherwise return null. -Value *MemoryDependenceAnalysis:: -GetAvailablePHITranslatedValue(Value *V, - BasicBlock *CurBB, BasicBlock *PredBB, - const TargetData *TD, - const DominatorTree &DT) const { - // See if PHI translation succeeds. - V = GetPHITranslatedValue(V, CurBB, PredBB, TD); - if (V == 0) return 0; - - // Make sure the value is live in the predecessor. - if (Instruction *Inst = dyn_cast_or_null(V)) - if (!DT.dominates(Inst->getParent(), PredBB)) - return 0; - return V; -} - - -/// InsertPHITranslatedPointer - Insert a computation of the PHI translated -/// version of 'V' for the edge PredBB->CurBB into the end of the PredBB -/// block. All newly created instructions are added to the NewInsts list. -/// -Value *MemoryDependenceAnalysis:: -InsertPHITranslatedPointer(Value *InVal, BasicBlock *CurBB, - BasicBlock *PredBB, const TargetData *TD, - const DominatorTree &DT, - SmallVectorImpl &NewInsts) const { - // See if we have a version of this value already available and dominating - // PredBB. If so, there is no need to insert a new copy. - if (Value *Res = GetAvailablePHITranslatedValue(InVal, CurBB, PredBB, TD, DT)) - return Res; - - // If we don't have an available version of this value, it must be an - // instruction. - Instruction *Inst = cast(InVal); - - // Handle bitcast of PHI translatable value. - if (BitCastInst *BC = dyn_cast(Inst)) { - Value *OpVal = InsertPHITranslatedPointer(BC->getOperand(0), - CurBB, PredBB, TD, DT, NewInsts); - if (OpVal == 0) return 0; - - // Otherwise insert a bitcast at the end of PredBB. - BitCastInst *New = new BitCastInst(OpVal, InVal->getType(), - InVal->getName()+".phi.trans.insert", - PredBB->getTerminator()); - NewInsts.push_back(New); - return New; - } - - // Handle getelementptr with at least one PHI operand. - if (GetElementPtrInst *GEP = dyn_cast(Inst)) { - SmallVector GEPOps; - BasicBlock *CurBB = GEP->getParent(); - for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i) { - Value *OpVal = InsertPHITranslatedPointer(GEP->getOperand(i), - CurBB, PredBB, TD, DT, NewInsts); - if (OpVal == 0) return 0; - GEPOps.push_back(OpVal); - } - - GetElementPtrInst *Result = - GetElementPtrInst::Create(GEPOps[0], GEPOps.begin()+1, GEPOps.end(), - InVal->getName()+".phi.trans.insert", - PredBB->getTerminator()); - Result->setIsInBounds(GEP->isInBounds()); - NewInsts.push_back(Result); - return Result; - } - -#if 0 - // FIXME: This code works, but it is unclear that we actually want to insert - // a big chain of computation in order to make a value available in a block. - // This needs to be evaluated carefully to consider its cost trade offs. - - // Handle add with a constant RHS. - if (Inst->getOpcode() == Instruction::Add && - isa(Inst->getOperand(1))) { - // PHI translate the LHS. - Value *OpVal = InsertPHITranslatedPointer(Inst->getOperand(0), - CurBB, PredBB, TD, DT, NewInsts); - if (OpVal == 0) return 0; - - BinaryOperator *Res = BinaryOperator::CreateAdd(OpVal, Inst->getOperand(1), - InVal->getName()+".phi.trans.insert", - PredBB->getTerminator()); - Res->setHasNoSignedWrap(cast(Inst)->hasNoSignedWrap()); - Res->setHasNoUnsignedWrap(cast(Inst)->hasNoUnsignedWrap()); - NewInsts.push_back(Res); - return Res; - } -#endif - - return 0; -} - /// getNonLocalPointerDepFromBB - Perform a dependency query based on /// pointer/pointeesize starting at the end of StartBB. Add any clobber/def /// results to the results vector and keep track of which blocks are visited in @@ -989,22 +889,77 @@ InsertPHITranslatedPointer(Value *InVal, BasicBlock *CurBB, /// not compute dependence information for some reason. This should be treated /// as a clobber dependence on the first instruction in the predecessor block. bool MemoryDependenceAnalysis:: -getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, +getNonLocalPointerDepFromBB(const PHITransAddr &Pointer, + const AliasAnalysis::Location &Loc, bool isLoad, BasicBlock *StartBB, - SmallVectorImpl &Result, + SmallVectorImpl &Result, DenseMap &Visited, bool SkipFirstBlock) { // Look up the cached info for Pointer. - ValueIsLoadPair CacheKey(Pointer, isLoad); - - std::pair *CacheInfo = - &NonLocalPointerDeps[CacheKey]; - NonLocalDepInfo *Cache = &CacheInfo->second; + ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad); + + // Set up a temporary NLPI value. If the map doesn't yet have an entry for + // CacheKey, this value will be inserted as the associated value. Otherwise, + // it'll be ignored, and we'll have to check to see if the cached size and + // tbaa tag are consistent with the current query. + NonLocalPointerInfo InitialNLPI; + InitialNLPI.Size = Loc.Size; + InitialNLPI.TBAATag = Loc.TBAATag; + + // Get the NLPI for CacheKey, inserting one into the map if it doesn't + // already have one. + std::pair Pair = + 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 (CacheInfo->Size < Loc.Size) { + // The query's Size is greater than the cached one. Throw out the + // 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(), + 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 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) { + 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 we have valid cached information for exactly the block we are // investigating, just return it with no recomputation. - if (CacheInfo->first == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) { + if (CacheInfo->Pair == BBSkipFirstBlockPair(StartBB, SkipFirstBlock)) { // We have a fully cached result for this query then we can just return the // cached results and populate the visited set. However, we have to verify // that we don't already have conflicting results for these blocks. Check @@ -1013,8 +968,9 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, if (!Visited.empty()) { for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end(); I != E; ++I) { - DenseMap::iterator VI = Visited.find(I->first); - if (VI == Visited.end() || VI->second == Pointer) continue; + DenseMap::iterator VI = Visited.find(I->getBB()); + if (VI == Visited.end() || VI->second == Pointer.getAddr()) + continue; // We have a pointer mismatch in a block. Just return clobber, saying // that something was clobbered in this result. We could also do a @@ -1023,11 +979,12 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, } } + Value *Addr = Pointer.getAddr(); 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); + Visited.insert(std::make_pair(I->getBB(), Addr)); + if (!I->getResult().isNonLocal() && DT->isReachableFromEntry(I->getBB())) + Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr)); } ++NumCacheCompleteNonLocalPtr; return false; @@ -1038,13 +995,16 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, // than its valid cache info. If empty, the result will be valid cache info, // otherwise it isn't. if (Cache->empty()) - CacheInfo->first = BBSkipFirstBlockPair(StartBB, SkipFirstBlock); + CacheInfo->Pair = BBSkipFirstBlockPair(StartBB, SkipFirstBlock); else - CacheInfo->first = BBSkipFirstBlockPair(); + CacheInfo->Pair = BBSkipFirstBlockPair(); SmallVector Worklist; Worklist.push_back(StartBB); + // PredList used inside loop. + SmallVector, 16> PredList; + // Keep track of the entries that we know are sorted. Previously cached // entries will all be sorted. The entries we add we only sort on demand (we // don't insert every element into its sorted position). We know that we @@ -1065,49 +1025,53 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, // Get the dependency info for Pointer in BB. If we have cached // information, we will use it, otherwise we compute it. DEBUG(AssertSorted(*Cache, NumSortedEntries)); - MemDepResult Dep = GetNonLocalInfoForBlock(Pointer, PointeeSize, isLoad, - BB, Cache, NumSortedEntries); + MemDepResult Dep = GetNonLocalInfoForBlock(Loc, isLoad, BB, Cache, + NumSortedEntries); // If we got a Def or Clobber, add this to the list of results. - if (!Dep.isNonLocal()) { - Result.push_back(NonLocalDepEntry(BB, Dep)); + if (!Dep.isNonLocal() && DT->isReachableFromEntry(BB)) { + Result.push_back(NonLocalDepResult(BB, Dep, Pointer.getAddr())); continue; } } // If 'Pointer' is an instruction defined in this block, then we need to do // phi translation to change it into a value live in the predecessor block. - // If phi translation fails, then we can't continue dependence analysis. - Instruction *PtrInst = dyn_cast(Pointer); - bool NeedsPHITranslation = PtrInst && PtrInst->getParent() == BB; - - // If no PHI translation is needed, just add all the predecessors of this - // block to scan them as well. - if (!NeedsPHITranslation) { + // If not, we just add the predecessors to the worklist and scan them with + // the same Pointer. + if (!Pointer.NeedsPHITranslationFromBlock(BB)) { SkipFirstBlock = false; + SmallVector NewBlocks; for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { // Verify that we haven't looked at this block yet. std::pair::iterator, bool> - InsertRes = Visited.insert(std::make_pair(*PI, Pointer)); + InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr())); if (InsertRes.second) { // First time we've looked at *PI. - Worklist.push_back(*PI); + NewBlocks.push_back(*PI); continue; } // If we have seen this block before, but it was with a different // pointer then we have a phi translation failure and we have to treat // this as a clobber. - if (InsertRes.first->second != Pointer) + if (InsertRes.first->second != Pointer.getAddr()) { + // Make sure to clean up the Visited map before continuing on to + // PredTranslationFailure. + for (unsigned i = 0; i < NewBlocks.size(); i++) + Visited.erase(NewBlocks[i]); goto PredTranslationFailure; + } } + Worklist.append(NewBlocks.begin(), NewBlocks.end()); continue; } - // If we do need to do phi translation, then there are a bunch of different - // cases, because we have to find a Value* live in the predecessor block. We - // know that PtrInst is defined in this block at least. - + // We do need to do phi translation, if we know ahead of time we can't phi + // translate this value, don't even try. + if (!Pointer.IsPotentiallyPHITranslatable()) + goto PredTranslationFailure; + // We may have added values to the cache list before this PHI translation. // If so, we haven't done anything to ensure that the cache remains sorted. // Sort it now (if needed) so that recursive invocations of @@ -1117,19 +1081,19 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, SortNonLocalDepInfoCache(*Cache, NumSortedEntries); NumSortedEntries = Cache->size(); } - - // If this is a computation derived from a PHI node, use the suitably - // translated incoming values for each pred as the phi translated version. - if (!isPHITranslatable(PtrInst)) - goto PredTranslationFailure; - Cache = 0; - + + PredList.clear(); for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { BasicBlock *Pred = *PI; - // Get the PHI translated pointer in this predecessor. This can fail and - // return null if not translatable. - Value *PredPtr = GetPHITranslatedValue(PtrInst, BB, Pred, TD); + PredList.push_back(std::make_pair(Pred, Pointer)); + + // Get the PHI translated pointer in this predecessor. This can fail if + // not translatable, in which case the getAddr() returns null. + PHITransAddr &PredPointer = PredList.back().second; + PredPointer.PHITranslateValue(BB, Pred, 0); + + Value *PredPtrVal = PredPointer.getAddr(); // Check to see if we have already visited this pred block with another // pointer. If so, we can't do this lookup. This failure can occur @@ -1137,85 +1101,108 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, // the successor translates to a pointer value different than the // pointer the block was first analyzed with. std::pair::iterator, bool> - InsertRes = Visited.insert(std::make_pair(Pred, PredPtr)); + InsertRes = Visited.insert(std::make_pair(Pred, PredPtrVal)); if (!InsertRes.second) { + // We found the pred; take it off the list of preds to visit. + PredList.pop_back(); + // If the predecessor was visited with PredPtr, then we already did // the analysis and can ignore it. - if (InsertRes.first->second == PredPtr) + if (InsertRes.first->second == PredPtrVal) continue; // Otherwise, the block was previously analyzed with a different // pointer. We can't represent the result of this case, so we just // treat this as a phi translation failure. + + // Make sure to clean up the Visited map before continuing on to + // PredTranslationFailure. + for (unsigned i = 0; i < PredList.size(); i++) + Visited.erase(PredList[i].first); + goto PredTranslationFailure; } - + } + + // Actually process results here; this need to be a separate loop to avoid + // calling getNonLocalPointerDepFromBB for blocks we don't want to return + // any results for. (getNonLocalPointerDepFromBB will modify our + // datastructures in ways the code after the PredTranslationFailure label + // doesn't expect.) + 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 PHI translation was unable to find an available pointer in this // predecessor, then we have to assume that the pointer is clobbered in // that predecessor. We can still do PRE of the load, which would insert // a computation of the pointer in this predecessor. - if (PredPtr == 0) { - // Add the entry to the Result list. - NonLocalDepEntry Entry(Pred, - MemDepResult::getClobber(Pred->getTerminator())); - 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); - Cache->insert(It, Entry); - Cache = 0; - - // Add it to the reverse map next. - ReverseNonLocalPtrDeps[Pred->getTerminator()].insert(CacheKey); - continue; - } + if (PredPtrVal == 0) + CanTranslate = false; // FIXME: it is entirely possible that PHI translating will end up with // the same value. Consider PHI translating something like: // X = phi [x, bb1], [y, bb2]. PHI translating for bb1 doesn't *need* // to recurse here, pedantically speaking. - - // If we have a problem phi translating, fall through to the code below - // to handle the failure condition. - if (getNonLocalPointerDepFromBB(PredPtr, PointeeSize, isLoad, Pred, - Result, Visited)) - goto PredTranslationFailure; + + // If getNonLocalPointerDepFromBB fails here, that means the cached + // result conflicted with the Visited list; we have to conservatively + // assume it is unknown, but this also does not block PRE of the load. + if (!CanTranslate || + getNonLocalPointerDepFromBB(PredPointer, + Loc.getWithNewPtr(PredPtrVal), + isLoad, Pred, + Result, Visited)) { + // Add the entry to the Result list. + NonLocalDepResult Entry(Pred, MemDepResult::getUnknown(), PredPtrVal); + Result.push_back(Entry); + + // 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. + NonLocalPointerInfo &NLPI = NonLocalPointerDeps[CacheKey]; + NLPI.Pair = BBSkipFirstBlockPair(); + continue; + } } // Refresh the CacheInfo/Cache pointer so that it isn't invalidated. CacheInfo = &NonLocalPointerDeps[CacheKey]; - Cache = &CacheInfo->second; + Cache = &CacheInfo->NonLocalDeps; NumSortedEntries = Cache->size(); // Since we did 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. - CacheInfo->first = BBSkipFirstBlockPair(); + CacheInfo->Pair = BBSkipFirstBlockPair(); SkipFirstBlock = false; continue; PredTranslationFailure: + // The following code is "failure"; we can't produce a sane translation + // for the given block. It assumes that we haven't modified any of + // our datastructures while processing the current block. if (Cache == 0) { // Refresh the CacheInfo/Cache pointer if it got invalidated. CacheInfo = &NonLocalPointerDeps[CacheKey]; - Cache = &CacheInfo->second; + Cache = &CacheInfo->NonLocalDeps; 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. - CacheInfo->first = BBSkipFirstBlockPair(); + // results from the set". Clear out the indicator for this. + CacheInfo->Pair = BBSkipFirstBlockPair(); - // If *nothing* works, mark the pointer as being clobbered by the first - // instruction in this block. + // If *nothing* works, mark the pointer as unknown. // // If this is the magic first block, return this as a clobber of the whole // incoming value. Since we can't phi translate to one of the predecessors, @@ -1225,14 +1212,14 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, for (NonLocalDepInfo::reverse_iterator I = Cache->rbegin(); ; ++I) { assert(I != Cache->rend() && "Didn't find current block??"); - if (I->first != BB) + if (I->getBB() != BB) continue; - assert(I->second.isNonLocal() && + assert(I->getResult().isNonLocal() && "Should only be here with transparent block"); - I->second = MemDepResult::getClobber(BB->begin()); - ReverseNonLocalPtrDeps[BB->begin()].insert(CacheKey); - Result.push_back(*I); + I->setResult(MemDepResult::getUnknown()); + Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), + Pointer.getAddr())); break; } } @@ -1253,12 +1240,12 @@ RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) { // Remove all of the entries in the BB->val map. This involves removing // instructions from the reverse map. - NonLocalDepInfo &PInfo = It->second.second; + NonLocalDepInfo &PInfo = It->second.NonLocalDeps; for (unsigned i = 0, e = PInfo.size(); i != e; ++i) { - Instruction *Target = PInfo[i].second.getInst(); + Instruction *Target = PInfo[i].getResult().getInst(); if (Target == 0) continue; // Ignore non-local dep results. - assert(Target->getParent() == PInfo[i].first); + assert(Target->getParent() == PInfo[i].getBB()); // Eliminating the dirty entry from 'Cache', so update the reverse info. RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P); @@ -1277,13 +1264,20 @@ RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) { /// 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(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. @@ -1295,7 +1289,7 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { NonLocalDepInfo &BlockMap = NLDI->second.first; for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end(); DI != DE; ++DI) - if (Instruction *Inst = DI->second.getInst()) + if (Instruction *Inst = DI->getResult().getInst()) RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst); NonLocalDeps.erase(NLDI); } @@ -1318,7 +1312,7 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { // 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(RemInst->getType())) { + if (RemInst->getType()->isPointerTy()) { RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, false)); RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(RemInst, true)); } @@ -1383,10 +1377,10 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { for (NonLocalDepInfo::iterator DI = INLD.first.begin(), DE = INLD.first.end(); DI != DE; ++DI) { - if (DI->second.getInst() != RemInst) continue; + if (DI->getResult().getInst() != RemInst) continue; // Convert to a dirty entry for the subsequent instruction. - DI->second = NewDirtyVal; + DI->setResult(NewDirtyVal); if (Instruction *NextI = NewDirtyVal.getInst()) ReverseDepsToAdd.push_back(std::make_pair(NextI, *I)); @@ -1417,18 +1411,18 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { assert(P.getPointer() != RemInst && "Already removed NonLocalPointerDeps info for RemInst"); - NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].second; + NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].NonLocalDeps; // The cache is not valid for any specific block anymore. - NonLocalPointerDeps[P].first = BBSkipFirstBlockPair(); + NonLocalPointerDeps[P].Pair = BBSkipFirstBlockPair(); // Update any entries for RemInst to use the instruction after it. for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end(); DI != DE; ++DI) { - if (DI->second.getInst() != RemInst) continue; + if (DI->getResult().getInst() != RemInst) continue; // Convert to a dirty entry for the subsequent instruction. - DI->second = NewDirtyVal; + DI->setResult(NewDirtyVal); if (Instruction *NewDirtyInst = NewDirtyVal.getInst()) ReversePtrDepsToAdd.push_back(std::make_pair(NewDirtyInst, P)); @@ -1466,10 +1460,10 @@ void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const { 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; + const NonLocalDepInfo &Val = I->second.NonLocalDeps; for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end(); II != E; ++II) - assert(II->second.getInst() != D && "Inst occurs as NLPD value"); + assert(II->getResult().getInst() != D && "Inst occurs as NLPD value"); } for (NonLocalDepMapType::const_iterator I = NonLocalDeps.begin(), @@ -1478,7 +1472,7 @@ void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const { 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"); + assert(II->getResult().getInst() != D && "Inst occurs in data structures"); } for (ReverseDepMapType::const_iterator I = ReverseLocalDeps.begin(),