X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=lib%2FAnalysis%2FMemoryDependenceAnalysis.cpp;h=ff78f6e1a94517c5c207e6b3b185b341bb42c0c3;hp=84769cb07d78493940397f9e2e3c9f173f855a09;hb=0ba0118816bb7b1fc361215b382578ac130df23b;hpb=e7122e58a1ce2459c97f07ba499a451d315c8cd5 diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index 84769cb07d7..ff78f6e1a94 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -22,7 +22,9 @@ #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/PHITransAddr.h" +#include "llvm/Analysis/OrderedBasicBlock.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Function.h" @@ -49,7 +51,11 @@ STATISTIC(NumCacheCompleteNonLocalPtr, "Number of block queries that were completely cached"); // Limit for the number of instructions to scan in a block. -static const unsigned int BlockScanLimit = 100; + +static cl::opt BlockScanLimit( + "memdep-block-scan-limit", cl::Hidden, cl::init(100), + cl::desc("The number of instructions to scan in a block in memory " + "dependency analysis (default = 100)")); // Limit on the number of memdep results to process. static const unsigned int NumResultsLimit = 100; @@ -65,7 +71,7 @@ INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep", "Memory Dependence Analysis", false, true) MemoryDependenceAnalysis::MemoryDependenceAnalysis() - : FunctionPass(ID), PredCache() { + : FunctionPass(ID) { initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry()); } MemoryDependenceAnalysis::~MemoryDependenceAnalysis() { @@ -79,7 +85,7 @@ void MemoryDependenceAnalysis::releaseMemory() { ReverseLocalDeps.clear(); ReverseNonLocalDeps.clear(); ReverseNonLocalPtrDeps.clear(); - PredCache->clear(); + PredCache.clear(); } /// getAnalysisUsage - Does not modify anything. It uses Alias Analysis. @@ -88,6 +94,7 @@ void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequired(); AU.addRequiredTransitive(); + AU.addRequiredTransitive(); } bool MemoryDependenceAnalysis::runOnFunction(Function &F) { @@ -96,8 +103,7 @@ bool MemoryDependenceAnalysis::runOnFunction(Function &F) { DominatorTreeWrapperPass *DTWP = getAnalysisIfAvailable(); DT = DTWP ? &DTWP->getDomTree() : nullptr; - if (!PredCache) - PredCache.reset(new PredIteratorCache()); + TLI = &getAnalysis().getTLI(); return false; } @@ -120,45 +126,43 @@ static void RemoveFromReverseMap(DenseMap(Inst)) { if (LI->isUnordered()) { - Loc = AA->getLocation(LI); - return AliasAnalysis::Ref; + Loc = MemoryLocation::get(LI); + return MRI_Ref; } if (LI->getOrdering() == Monotonic) { - Loc = AA->getLocation(LI); - return AliasAnalysis::ModRef; + Loc = MemoryLocation::get(LI); + return MRI_ModRef; } - Loc = AliasAnalysis::Location(); - return AliasAnalysis::ModRef; + Loc = MemoryLocation(); + return MRI_ModRef; } if (const StoreInst *SI = dyn_cast(Inst)) { if (SI->isUnordered()) { - Loc = AA->getLocation(SI); - return AliasAnalysis::Mod; + Loc = MemoryLocation::get(SI); + return MRI_Mod; } if (SI->getOrdering() == Monotonic) { - Loc = AA->getLocation(SI); - return AliasAnalysis::ModRef; + Loc = MemoryLocation::get(SI); + return MRI_ModRef; } - Loc = AliasAnalysis::Location(); - return AliasAnalysis::ModRef; + Loc = MemoryLocation(); + return MRI_ModRef; } if (const VAArgInst *V = dyn_cast(Inst)) { - Loc = AA->getLocation(V); - return AliasAnalysis::ModRef; + Loc = MemoryLocation::get(V); + return MRI_ModRef; } - if (const CallInst *CI = isFreeCall(Inst, AA->getTargetLibraryInfo())) { + if (const CallInst *CI = isFreeCall(Inst, &TLI)) { // calls to free() deallocate the entire structure - Loc = AliasAnalysis::Location(CI->getArgOperand(0)); - return AliasAnalysis::Mod; + Loc = MemoryLocation(CI->getArgOperand(0)); + return MRI_Mod; } if (const IntrinsicInst *II = dyn_cast(Inst)) { @@ -169,20 +173,20 @@ AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst, case Intrinsic::lifetime_end: case Intrinsic::invariant_start: II->getAAMetadata(AAInfo); - Loc = AliasAnalysis::Location(II->getArgOperand(1), - cast(II->getArgOperand(0)) - ->getZExtValue(), AAInfo); + Loc = MemoryLocation( + II->getArgOperand(1), + cast(II->getArgOperand(0))->getZExtValue(), AAInfo); // These intrinsics don't really modify the memory, but returning Mod // will allow them to be handled conservatively. - return AliasAnalysis::Mod; + return MRI_Mod; case Intrinsic::invariant_end: II->getAAMetadata(AAInfo); - Loc = AliasAnalysis::Location(II->getArgOperand(2), - cast(II->getArgOperand(1)) - ->getZExtValue(), AAInfo); + Loc = MemoryLocation( + II->getArgOperand(2), + cast(II->getArgOperand(1))->getZExtValue(), AAInfo); // These intrinsics don't really modify the memory, but returning Mod // will allow them to be handled conservatively. - return AliasAnalysis::Mod; + return MRI_Mod; default: break; } @@ -190,10 +194,10 @@ AliasAnalysis::ModRefResult GetLocation(const Instruction *Inst, // Otherwise, just do the coarse-grained thing that always works. if (Inst->mayWriteToMemory()) - return AliasAnalysis::ModRef; + return MRI_ModRef; if (Inst->mayReadFromMemory()) - return AliasAnalysis::Ref; - return AliasAnalysis::NoModRef; + return MRI_Ref; + return MRI_NoModRef; } /// getCallSiteDependencyFrom - Private helper for finding the local @@ -214,11 +218,11 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, Instruction *Inst = --ScanIt; // If this inst is a memory op, get the pointer it accessed - AliasAnalysis::Location Loc; - AliasAnalysis::ModRefResult MR = GetLocation(Inst, Loc, AA); + MemoryLocation Loc; + ModRefInfo MR = GetLocation(Inst, Loc, *TLI); if (Loc.Ptr) { // A simple instruction. - if (AA->getModRefInfo(CS, Loc) != AliasAnalysis::NoModRef) + if (AA->getModRefInfo(CS, Loc) != MRI_NoModRef) return MemDepResult::getClobber(Inst); continue; } @@ -228,10 +232,10 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, if (isa(Inst)) continue; // If these two calls do not interfere, look past it. switch (AA->getModRefInfo(CS, InstCS)) { - case AliasAnalysis::NoModRef: + case MRI_NoModRef: // 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) && + if (isReadOnlyCall && !(MR & MRI_Mod) && CS.getInstruction()->isIdenticalToWhenDefined(Inst)) return MemDepResult::getDef(Inst); @@ -245,7 +249,7 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, // 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) + if (MR != MRI_NoModRef) return MemDepResult::getClobber(Inst); } @@ -261,9 +265,10 @@ getCallSiteDependencyFrom(CallSite CS, bool isReadOnlyCall, /// /// 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) { +static bool isLoadLoadClobberIfExtendedToFullWidth(const MemoryLocation &MemLoc, + const Value *&MemLocBase, + int64_t &MemLocOffs, + const LoadInst *LI) { const DataLayout &DL = LI->getModule()->getDataLayout(); // If we haven't already computed the base/offset of MemLoc, do so now. @@ -370,10 +375,9 @@ static bool isVolatile(Instruction *Inst) { /// 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(const AliasAnalysis::Location &MemLoc, bool isLoad, - BasicBlock::iterator ScanIt, BasicBlock *BB, - Instruction *QueryInst) { +MemDepResult MemoryDependenceAnalysis::getPointerDependencyFrom( + const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt, + BasicBlock *BB, Instruction *QueryInst) { const Value *MemLocBase = nullptr; int64_t MemLocOffset = 0; @@ -420,6 +424,12 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, const DataLayout &DL = BB->getModule()->getDataLayout(); + // Create a numbered basic block to lazily compute and cache instruction + // positions inside a BB. This is used to provide fast queries for relative + // position between two instructions in a BB and can be used by + // AliasAnalysis::callCapturesBefore. + OrderedBasicBlock OBB(BB); + // Walk backwards through the basic block, looking for dependencies. while (ScanIt != BB->begin()) { Instruction *Inst = --ScanIt; @@ -442,8 +452,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // 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)) + if (AA->isMustAlias(MemoryLocation(II->getArgOperand(1)), MemLoc)) return MemDepResult::getDef(II); continue; } @@ -488,13 +497,13 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, } } - AliasAnalysis::Location LoadLoc = AA->getLocation(LI); + MemoryLocation LoadLoc = MemoryLocation::get(LI); // If we found a pointer, check if it could be the same as our pointer. - AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc); + AliasResult R = AA->alias(LoadLoc, MemLoc); if (isLoad) { - if (R == AliasAnalysis::NoAlias) { + if (R == 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 @@ -511,7 +520,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, } // Must aliased loads are defs of each other. - if (R == AliasAnalysis::MustAlias) + if (R == MustAlias) return MemDepResult::getDef(Inst); #if 0 // FIXME: Temporarily disabled. GVN is cleverly rewriting loads @@ -521,7 +530,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // If we have a partial alias, then return this as a clobber for the // client to handle. - if (R == AliasAnalysis::PartialAlias) + if (R == PartialAlias) return MemDepResult::getClobber(Inst); #endif @@ -531,7 +540,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, } // Stores don't depend on other no-aliased accesses. - if (R == AliasAnalysis::NoAlias) + if (R == NoAlias) continue; // Stores don't alias loads from read-only memory. @@ -572,19 +581,19 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // 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, MemLoc) == AliasAnalysis::NoModRef) + if (AA->getModRefInfo(SI, MemLoc) == MRI_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. - AliasAnalysis::Location StoreLoc = AA->getLocation(SI); + MemoryLocation StoreLoc = MemoryLocation::get(SI); // If we found a pointer, check if it could be the same as our pointer. - AliasAnalysis::AliasResult R = AA->alias(StoreLoc, MemLoc); + AliasResult R = AA->alias(StoreLoc, MemLoc); - if (R == AliasAnalysis::NoAlias) + if (R == NoAlias) continue; - if (R == AliasAnalysis::MustAlias) + if (R == MustAlias) return MemDepResult::getDef(Inst); if (isInvariantLoad) continue; @@ -599,7 +608,6 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, // a subsequent bitcast of the malloc call result. There can be stores to // the malloced memory between the malloc call and its bitcast uses, and we // need to continue scanning until the malloc call. - const TargetLibraryInfo *TLI = AA->getTargetLibraryInfo(); if (isa(Inst) || isNoAliasFn(Inst, TLI)) { const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, DL); @@ -608,7 +616,7 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, if (isInvariantLoad) continue; // Be conservative if the accessed pointer may alias the allocation. - if (AA->alias(Inst, AccessPtr) != AliasAnalysis::NoAlias) + if (AA->alias(Inst, AccessPtr) != NoAlias) return MemDepResult::getClobber(Inst); // If the allocation is not aliased and does not read memory (like // strdup), it is safe to ignore. @@ -621,17 +629,17 @@ getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad, continue; // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer. - AliasAnalysis::ModRefResult MR = AA->getModRefInfo(Inst, MemLoc); + ModRefInfo MR = AA->getModRefInfo(Inst, MemLoc); // If necessary, perform additional analysis. - if (MR == AliasAnalysis::ModRef) - MR = AA->callCapturesBefore(Inst, MemLoc, DT); + if (MR == MRI_ModRef) + MR = AA->callCapturesBefore(Inst, MemLoc, DT, &OBB); switch (MR) { - case AliasAnalysis::NoModRef: + case MRI_NoModRef: // If the call has no effect on the queried pointer, just ignore it. continue; - case AliasAnalysis::Mod: + case MRI_Mod: return MemDepResult::getClobber(Inst); - case AliasAnalysis::Ref: + case MRI_Ref: // If the call is known to never store to the pointer, and if this is a // load query, we can safely ignore it (scan past it). if (isLoad) @@ -681,11 +689,11 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { else LocalCache = MemDepResult::getNonFuncLocal(); } else { - AliasAnalysis::Location MemLoc; - AliasAnalysis::ModRefResult MR = GetLocation(QueryInst, MemLoc, AA); + MemoryLocation MemLoc; + ModRefInfo MR = GetLocation(QueryInst, MemLoc, *TLI); if (MemLoc.Ptr) { // If we can do a pointer scan, make it happen. - bool isLoad = !(MR & AliasAnalysis::Mod); + bool isLoad = !(MR & MRI_Mod); if (IntrinsicInst *II = dyn_cast(QueryInst)) isLoad |= II->getIntrinsicID() == Intrinsic::lifetime_start; @@ -770,8 +778,8 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { } else { // Seed DirtyBlocks with each of the preds of QueryInst's block. BasicBlock *QueryBB = QueryCS.getInstruction()->getParent(); - for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI) - DirtyBlocks.push_back(*PI); + for (BasicBlock *Pred : PredCache.get(QueryBB)) + DirtyBlocks.push_back(Pred); ++NumUncacheNonLocal; } @@ -856,8 +864,8 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { // 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); + for (BasicBlock *Pred : PredCache.get(DirtyBB)) + DirtyBlocks.push_back(Pred); } } @@ -874,7 +882,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { void MemoryDependenceAnalysis:: getNonLocalPointerDependency(Instruction *QueryInst, SmallVectorImpl &Result) { - const AliasAnalysis::Location Loc = AA->getLocation(QueryInst); + const MemoryLocation Loc = MemoryLocation::get(QueryInst); bool isLoad = isa(QueryInst); BasicBlock *FromBB = QueryInst->getParent(); assert(FromBB); @@ -926,11 +934,9 @@ getNonLocalPointerDependency(Instruction *QueryInst, /// Pointer/PointeeSize using either cached information in Cache or by doing a /// lookup (which may use dirty cache info if available). If we do a lookup, /// add the result to the cache. -MemDepResult MemoryDependenceAnalysis:: -GetNonLocalInfoForBlock(Instruction *QueryInst, - const AliasAnalysis::Location &Loc, - bool isLoad, BasicBlock *BB, - NonLocalDepInfo *Cache, unsigned NumSortedEntries) { +MemDepResult MemoryDependenceAnalysis::GetNonLocalInfoForBlock( + Instruction *QueryInst, const MemoryLocation &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. @@ -1042,14 +1048,11 @@ SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, /// This function returns false on success, or true to indicate that it could /// 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(Instruction *QueryInst, - const PHITransAddr &Pointer, - const AliasAnalysis::Location &Loc, - bool isLoad, BasicBlock *StartBB, - SmallVectorImpl &Result, - DenseMap &Visited, - bool SkipFirstBlock) { +bool MemoryDependenceAnalysis::getNonLocalPointerDepFromBB( + Instruction *QueryInst, const PHITransAddr &Pointer, + const MemoryLocation &Loc, bool isLoad, BasicBlock *StartBB, + SmallVectorImpl &Result, + DenseMap &Visited, bool SkipFirstBlock) { // Look up the cached info for Pointer. ValueIsLoadPair CacheKey(Pointer.getAddr(), isLoad); @@ -1232,13 +1235,13 @@ getNonLocalPointerDepFromBB(Instruction *QueryInst, if (!Pointer.NeedsPHITranslationFromBlock(BB)) { SkipFirstBlock = false; SmallVector NewBlocks; - for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { + for (BasicBlock *Pred : PredCache.get(BB)) { // Verify that we haven't looked at this block yet. std::pair::iterator, bool> - InsertRes = Visited.insert(std::make_pair(*PI, Pointer.getAddr())); + InsertRes = Visited.insert(std::make_pair(Pred, Pointer.getAddr())); if (InsertRes.second) { // First time we've looked at *PI. - NewBlocks.push_back(*PI); + NewBlocks.push_back(Pred); continue; } @@ -1274,15 +1277,13 @@ getNonLocalPointerDepFromBB(Instruction *QueryInst, Cache = nullptr; PredList.clear(); - for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) { - BasicBlock *Pred = *PI; + for (BasicBlock *Pred : PredCache.get(BB)) { 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, nullptr); - + PredPointer.PHITranslateValue(BB, Pred, DT, /*MustDominate=*/false); Value *PredPtrVal = PredPointer.getAddr(); // Check to see if we have already visited this pred block with another @@ -1465,7 +1466,7 @@ void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) { /// This needs to be done when the CFG changes, e.g., due to splitting /// critical edges. void MemoryDependenceAnalysis::invalidateCachedPredecessors() { - PredCache->clear(); + PredCache.clear(); } /// removeInstruction - Remove an instruction from the dependence analysis, @@ -1626,7 +1627,6 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { assert(!NonLocalDeps.count(RemInst) && "RemInst got reinserted?"); - AA->deleteValue(RemInst); DEBUG(verifyRemoved(RemInst)); } /// verifyRemoved - Verify that the specified instruction does not occur