X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FMemoryDependenceAnalysis.cpp;h=fe1c8743a44f559d78500bd16254da18f737f224;hb=c143c7573bfd0d55cf283cc2676dbd852f939c87;hp=b5069ecbc9267f3dad70f2d5facc8825178b172f;hpb=f58e86d762ac469df7c7267a54cf556badc56031;p=oota-llvm.git diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index b5069ecbc92..fe1c8743a44 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -1,4 +1,4 @@ -//===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation --*- C++ -*-===// +//===- MemoryDependenceAnalysis.cpp - Mem Deps Implementation -------------===// // // The LLVM Compiler Infrastructure // @@ -8,7 +8,7 @@ //===----------------------------------------------------------------------===// // // This file implements an analysis that determines, for a given memory -// operation, what preceding memory operations it depends on. It builds on +// operation, what preceding memory operations it depends on. It builds on // alias analysis information, and tries to provide a lazy, caching interface to // a common kind of alias information query. // @@ -16,17 +16,21 @@ #define DEBUG_TYPE "memdep" #include "llvm/Analysis/MemoryDependenceAnalysis.h" -#include "llvm/Instructions.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/Function.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/Dominators.h" #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/MemoryBuiltins.h" -#include "llvm/ADT/Statistic.h" -#include "llvm/ADT/STLExtras.h" -#include "llvm/Support/PredIteratorCache.h" +#include "llvm/Analysis/PHITransAddr.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/IR/LLVMContext.h" #include "llvm/Support/Debug.h" +#include "llvm/Support/PredIteratorCache.h" using namespace llvm; STATISTIC(NumCacheNonLocal, "Number of fully cached non-local responses"); @@ -42,14 +46,21 @@ STATISTIC(NumUncacheNonLocalPtr, STATISTIC(NumCacheCompleteNonLocalPtr, "Number of block queries that were completely cached"); +// Limit for the number of instructions to scan in a block. +static const int BlockScanLimit = 100; + 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,7 +87,9 @@ void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { bool MemoryDependenceAnalysis::runOnFunction(Function &) { AA = &getAnalysis(); - if (PredCache == 0) + TD = getAnalysisIfAvailable(); + DT = getAnalysisIfAvailable(); + if (!PredCache) PredCache.reset(new PredIteratorCache()); return false; } @@ -84,187 +97,394 @@ bool MemoryDependenceAnalysis::runOnFunction(Function &) { /// RemoveFromReverseMap - This is a helper function that removes Val from /// 'Inst's set in ReverseMap. If the set becomes empty, remove Inst's entry. template -static void RemoveFromReverseMap(DenseMap > &ReverseMap, Instruction *Inst, KeyTy Val) { typename DenseMap >::iterator InstIt = ReverseMap.find(Inst); assert(InstIt != ReverseMap.end() && "Reverse map out of sync?"); bool Found = InstIt->second.erase(Val); - assert(Found && "Invalid reverse map!"); 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; + } + 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; + } + 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; + + // Load widening is hostile to ThreadSanitizer: it may cause false positives + // or make the reports more cryptic (access sizes are wrong). + if (LI->getParent()->getParent()->getAttributes(). + hasAttribute(AttributeSet::FunctionIndex, Attribute::SanitizeThread)) + 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()->getAttributes(). + hasAttribute(AttributeSet::FunctionIndex, Attribute::SanitizeAddress)) + // 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. If possible, pass the query +/// instruction as well; this function may take advantage of the metadata +/// annotated to the query instruction to refine the result. MemDepResult MemoryDependenceAnalysis:: -getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad, - BasicBlock::iterator ScanIt, BasicBlock *BB) { +getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, + BasicBlock::iterator ScanIt, BasicBlock *BB, + Instruction *QueryInst) { - Value *invariantTag = 0; + const Value *MemLocBase = 0; + int64_t MemLocOffset = 0; + unsigned Limit = BlockScanLimit; + bool isInvariantLoad = false; + if (isLoad && QueryInst) { + LoadInst *LI = dyn_cast(QueryInst); + if (LI && LI->getMetadata(LLVMContext::MD_invariant_load) != 0) + isInvariantLoad = true; + } // 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); + if (isInvariantLoad) + continue; + return MemDepResult::getClobber(Inst); } // If this is an allocation, and if we know that the accessed pointer is to @@ -275,24 +495,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(); - - if (AccessPtr == Inst || - AA->alias(Inst, 1, AccessPtr, 1) == AliasAnalysis::MustAlias) + 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, 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 @@ -304,111 +532,70 @@ getPointerDependencyFrom(Value *MemPtr, uint64_t MemSize, bool isLoad, 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(); } /// getDependency - Return the instruction on which a memory operation /// depends. MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { Instruction *ScanPos = QueryInst; - + // Check for a cached result MemDepResult &LocalCache = LocalDeps[QueryInst]; - + // If the cached entry is non-dirty, just return it. Note that this depends // on MemDepResult's default constructing to 'dirty'. if (!LocalCache.isDirty()) return LocalCache; - + // Otherwise, if we have a dirty entry, we know we can start the scan at that // instruction, which may save us some work. if (Instruction *Inst = LocalCache.getInst()) { ScanPos = Inst; - + RemoveFromReverseMap(ReverseLocalDeps, Inst, 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, QueryInst); + } 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! if (Instruction *I = LocalCache.getInst()) ReverseLocalDeps[I].insert(QueryInst); - + return LocalCache; } @@ -421,7 +608,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 @@ -449,25 +636,25 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { /// the uncached case, this starts out as the set of predecessors we care /// about. SmallVector DirtyBlocks; - + if (!Cache.empty()) { // 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; } - + // If we already have a partially computed set of results, scan them to // 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()); - + ++NumCacheDirtyNonLocal; //cerr << "CACHED CASE: " << DirtyBlocks.size() << " dirty: " // << Cache.size() << " cached: " << *QueryInst; @@ -476,79 +663,79 @@ 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. bool isReadonlyCall = AA->onlyReadsMemory(QueryCS); SmallPtrSet Visited; - + unsigned NumSortedEntries = Cache.size(); DEBUG(AssertSorted(Cache)); - + // Iterate while we still have blocks to update. while (!DirtyBlocks.empty()) { BasicBlock *DirtyBB = DirtyBlocks.back(); DirtyBlocks.pop_back(); - + // Already processed this block? if (!Visited.insert(DirtyBB)) continue; - + // Do a binary search to see if we already have an entry for this block in // the cache set. If so, find it. DEBUG(AssertSorted(Cache, NumSortedEntries)); - NonLocalDepInfo::iterator Entry = + 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; - if (Entry != Cache.begin()+NumSortedEntries && - Entry->first == DirtyBB) { + + NonLocalDepEntry *ExistingResult = 0; + if (Entry != Cache.begin()+NumSortedEntries && + 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, QueryCS.getInstruction()); } } - + // Find out if this block has a local dependency for QueryInst. MemDepResult Dep; - + if (ScanPos != DirtyBB->begin()) { 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! if (!Dep.isNonLocal()) { @@ -557,14 +744,14 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { if (Instruction *Inst = Dep.getInst()) ReverseNonLocalDeps[Inst].insert(QueryCS.getInstruction()); } else { - + // If the block *is* completely transparent to the load, we need to check // the predecessors of this block. Add them to our worklist. for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI) DirtyBlocks.push_back(*PI); } } - + return Cache; } @@ -576,28 +763,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,68 +791,67 @@ 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) { - + // Do a binary search to see if we already have an entry for this block in // 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; } @@ -674,7 +859,7 @@ GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize, /// SortNonLocalDepInfoCache - Sort the a NonLocalDepInfo cache, given a certain /// number of elements in the array that are already properly ordered. This is /// optimized for the case when only a few entries are added. -static void +static void SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, unsigned NumSortedEntries) { switch (Cache.size() - NumSortedEntries) { @@ -683,7 +868,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 +878,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 +892,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 +905,76 @@ 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,38 +983,52 @@ 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 // non-fully cached query, but there is little point in doing this. return true; } } - + + 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()) { + continue; + } + + if (!DT) { + Result.push_back(NonLocalDepResult(I->getBB(), + MemDepResult::getUnknown(), + Addr)); + } else if (DT->isReachableFromEntry(I->getBB())) { + Result.push_back(NonLocalDepResult(I->getBB(), I->getResult(), Addr)); + } } ++NumCacheCompleteNonLocalPtr; return false; } - + // Otherwise, either this is a new block, a block with an invalid cache // pointer or one that we're about to invalidate by putting more info into it // 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 @@ -1052,10 +1036,10 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, // revisit blocks after we insert info for them. unsigned NumSortedEntries = Cache->size(); DEBUG(AssertSorted(*Cache)); - + while (!Worklist.empty()) { BasicBlock *BB = Worklist.pop_back_val(); - + // Skip the first block if we have it. if (!SkipFirstBlock) { // Analyze the dependency of *Pointer in FromBB. See if we already have @@ -1065,48 +1049,59 @@ 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)); - continue; + if (!DT) { + Result.push_back(NonLocalDepResult(BB, + MemDepResult::getUnknown(), + Pointer.getAddr())); + continue; + } else if (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. @@ -1117,109 +1112,145 @@ 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 // with PHI translation when a critical edge exists and the PHI node in // 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, n = PredList.size(); i < n; ++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, n = PredList.size(); i < n; ++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) { - Result.push_back(NonLocalDepEntry(Pred, - MemDepResult::getClobber(Pred->getTerminator()))); - 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(); - - // If *nothing* works, mark the pointer as being clobbered by the first - // instruction in this block. + // results from the set". Clear out the indicator for this. + CacheInfo->Pair = BBSkipFirstBlockPair(); + + // 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, // we have to bail out. if (SkipFirstBlock) return true; - + 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; } } @@ -1234,23 +1265,23 @@ getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize, /// CachedNonLocalPointerInfo, remove it. void MemoryDependenceAnalysis:: RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair P) { - CachedNonLocalPointerInfo::iterator It = + CachedNonLocalPointerInfo::iterator It = NonLocalPointerDeps.find(P); if (It == NonLocalPointerDeps.end()) return; - + // 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); } - + // Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo). NonLocalPointerDeps.erase(It); } @@ -1264,13 +1295,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. @@ -1282,7 +1320,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); } @@ -1298,20 +1336,20 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { // Remove this local dependency info. LocalDeps.erase(LocalDepEntry); } - + // If we have any cached pointer dependencies on this instruction, remove // them. If the instruction has non-pointer type, then it can't be a pointer // base. - + // 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)); } - + // Loop over all of the things that depend on the instruction we're removing. - // + // SmallVector, 8> ReverseDepsToAdd; // If we find RemInst as a clobber or Def in any of the maps for other values, @@ -1323,29 +1361,29 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { MemDepResult NewDirtyVal; if (!RemInst->isTerminator()) NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst)); - + ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst); if (ReverseDepIt != ReverseLocalDeps.end()) { SmallPtrSet &ReverseDeps = ReverseDepIt->second; // RemInst can't be the terminator if it has local stuff depending on it. assert(!ReverseDeps.empty() && !isa(RemInst) && "Nothing can locally depend on a terminator"); - + for (SmallPtrSet::iterator I = ReverseDeps.begin(), E = ReverseDeps.end(); I != E; ++I) { Instruction *InstDependingOnRemInst = *I; assert(InstDependingOnRemInst != RemInst && "Already removed our local dep info"); - + LocalDeps[InstDependingOnRemInst] = NewDirtyVal; - + // Make sure to remember that new things depend on NewDepInst. assert(NewDirtyVal.getInst() && "There is no way something else can have " "a local dep on this if it is a terminator!"); - ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(), + ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(), InstDependingOnRemInst)); } - + ReverseLocalDeps.erase(ReverseDepIt); // Add new reverse deps after scanning the set, to avoid invalidating the @@ -1356,25 +1394,25 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { ReverseDepsToAdd.pop_back(); } } - + ReverseDepIt = ReverseNonLocalDeps.find(RemInst); if (ReverseDepIt != ReverseNonLocalDeps.end()) { SmallPtrSet &Set = ReverseDepIt->second; for (SmallPtrSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) { assert(*I != RemInst && "Already removed NonLocalDep info for RemInst"); - + PerInstNLInfo &INLD = NonLocalDeps[*I]; // The information is now dirty! INLD.second = true; - - for (NonLocalDepInfo::iterator DI = INLD.first.begin(), + + 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)); } @@ -1389,7 +1427,7 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { ReverseDepsToAdd.pop_back(); } } - + // If the instruction is in ReverseNonLocalPtrDeps then it appears as a // value in the NonLocalPointerDeps info. ReverseNonLocalPtrDepTy::iterator ReversePtrDepIt = @@ -1397,45 +1435,45 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { if (ReversePtrDepIt != ReverseNonLocalPtrDeps.end()) { SmallPtrSet &Set = ReversePtrDepIt->second; SmallVector,8> ReversePtrDepsToAdd; - + for (SmallPtrSet::iterator I = Set.begin(), E = Set.end(); I != E; ++I) { ValueIsLoadPair P = *I; assert(P.getPointer() != RemInst && "Already removed NonLocalPointerDeps info for RemInst"); - - NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].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)); } - + // Re-sort the NonLocalDepInfo. Changing the dirty entry to its // subsequent value may invalidate the sortedness. std::sort(NLPDI.begin(), NLPDI.end()); } - + ReverseNonLocalPtrDeps.erase(ReversePtrDepIt); - + while (!ReversePtrDepsToAdd.empty()) { ReverseNonLocalPtrDeps[ReversePtrDepsToAdd.back().first] .insert(ReversePtrDepsToAdd.back().second); ReversePtrDepsToAdd.pop_back(); } } - - + + assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?"); AA->deleteValue(RemInst); DEBUG(verifyRemoved(RemInst)); @@ -1449,25 +1487,25 @@ void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const { assert(I->second.getInst() != D && "Inst occurs in data structures"); } - + for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(), E = NonLocalPointerDeps.end(); I != E; ++I) { assert(I->first.getPointer() != D && "Inst occurs in NLPD map key"); - const NonLocalDepInfo &Val = I->second.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(), E = NonLocalDeps.end(); I != E; ++I) { assert(I->first != D && "Inst occurs in data structures"); const PerInstNLInfo &INLD = I->second; for (NonLocalDepInfo::const_iterator II = INLD.first.begin(), EE = INLD.first.end(); II != EE; ++II) - assert(II->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(), E = ReverseLocalDeps.end(); I != E; ++I) { assert(I->first != D && "Inst occurs in data structures"); @@ -1475,7 +1513,7 @@ void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const { EE = I->second.end(); II != EE; ++II) assert(*II != D && "Inst occurs in data structures"); } - + for (ReverseDepMapType::const_iterator I = ReverseNonLocalDeps.begin(), E = ReverseNonLocalDeps.end(); I != E; ++I) { @@ -1484,17 +1522,17 @@ void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const { EE = I->second.end(); II != EE; ++II) assert(*II != D && "Inst occurs in data structures"); } - + for (ReverseNonLocalPtrDepTy::const_iterator I = ReverseNonLocalPtrDeps.begin(), E = ReverseNonLocalPtrDeps.end(); I != E; ++I) { assert(I->first != D && "Inst occurs in rev NLPD map"); - + for (SmallPtrSet::const_iterator II = I->second.begin(), E = I->second.end(); II != E; ++II) assert(*II != ValueIsLoadPair(D, false) && *II != ValueIsLoadPair(D, true) && "Inst occurs in ReverseNonLocalPtrDeps map"); } - + }