From 61440d225b0869aa1c82a0d76e6311eccf7307bc Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Thu, 10 Mar 2016 00:55:30 +0000 Subject: [PATCH] [PM] Port memdep to the new pass manager. This is a fairly straightforward port to the new pass manager with one exception. It removes a very questionable use of releaseMemory() in the old pass to invalidate its caches between runs on a function. I don't think this is really guaranteed to be safe. I've just used the more direct port to the new PM to address this by nuking the results object each time the pass runs. While this could cause some minor malloc traffic increase, I don't expect the compile time performance hit to be noticable, and it makes the correctness and other aspects of the pass much easier to reason about. In some cases, it may make things faster by making the sets and maps smaller with better locality. Indeed, the measurements collected by Bruno (thanks!!!) show mostly compile time improvements. There is sadly very limited testing at this point as there are only two tests of memdep, and both rely on GVN. I'll be porting GVN next and that will exercise this heavily though. Differential Revision: http://reviews.llvm.org/D17962 llvm-svn: 263082 --- .../llvm/Analysis/MemoryDependenceAnalysis.h | 70 ++++++--- llvm/include/llvm/InitializePasses.h | 2 +- .../llvm/Transforms/Utils/BasicBlockUtils.h | 6 +- llvm/lib/Analysis/Analysis.cpp | 2 +- llvm/lib/Analysis/MemDepPrinter.cpp | 10 +- llvm/lib/Analysis/MemoryDependenceAnalysis.cpp | 162 +++++++++++---------- llvm/lib/CodeGen/MachineFunctionPass.cpp | 2 +- llvm/lib/Passes/PassBuilder.cpp | 1 + llvm/lib/Passes/PassRegistry.def | 1 + .../lib/Transforms/Scalar/DeadStoreElimination.cpp | 12 +- llvm/lib/Transforms/Scalar/GVN.cpp | 18 +-- llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp | 10 +- .../Transforms/Scalar/MergedLoadStoreMotion.cpp | 9 +- llvm/lib/Transforms/Utils/BasicBlockUtils.cpp | 4 +- llvm/test/Other/new-pass-manager.ll | 8 + 15 files changed, 177 insertions(+), 140 deletions(-) diff --git a/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h b/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h index c4b0aac..38d8db5 100644 --- a/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h +++ b/llvm/include/llvm/Analysis/MemoryDependenceAnalysis.h @@ -20,6 +20,7 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/IR/BasicBlock.h" +#include "llvm/IR/PassManager.h" #include "llvm/IR/PredIteratorCache.h" #include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" @@ -30,7 +31,7 @@ class FunctionPass; class Instruction; class CallSite; class AssumptionCache; -class MemoryDependenceAnalysis; +class MemoryDependenceResults; class PredIteratorCache; class DominatorTree; class PHITransAddr; @@ -184,7 +185,7 @@ public: bool operator>(const MemDepResult &M) const { return Value > M.Value; } private: - friend class MemoryDependenceAnalysis; + friend class MemoryDependenceResults; /// Tests if this is a MemDepResult in its dirty/invalid. state. bool isDirty() const { return Value.is(); } @@ -251,11 +252,8 @@ public: Value *getAddress() const { return Address; } }; -/// Determines, for a given memory 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. +/// Provides a lazy, caching interface for making common memory aliasing +/// information queries, backed by LLVM's alias analysis passes. /// /// The dependency information returned is somewhat unusual, but is pragmatic. /// If queried about a store or call that might modify memory, the analysis @@ -266,7 +264,7 @@ public: /// b) they load from *must-aliased* pointers. Returning a dependence on /// must-alias'd pointers instead of all pointers interacts well with the /// internal caching mechanism. -class MemoryDependenceAnalysis : public FunctionPass { +class MemoryDependenceResults { // A map from instructions to their dependency. typedef DenseMap LocalDepMapType; LocalDepMapType LocalDeps; @@ -340,25 +338,17 @@ private: ReverseDepMapType ReverseNonLocalDeps; /// Current AA implementation, just a cache. - AliasAnalysis *AA; + AliasAnalysis &AA; + AssumptionCache ∾ + const TargetLibraryInfo &TLI; DominatorTree *DT; - AssumptionCache *AC; - const TargetLibraryInfo *TLI; PredIteratorCache PredCache; public: - MemoryDependenceAnalysis(); - ~MemoryDependenceAnalysis() override; - static char ID; - - /// Pass Implementation stuff. This doesn't do any analysis eagerly. - bool runOnFunction(Function &) override; - - /// Clean up memory in between runs - void releaseMemory() override; - - /// Does not modify anything. It uses Value Numbering and Alias Analysis. - void getAnalysisUsage(AnalysisUsage &AU) const override; + MemoryDependenceResults(AliasAnalysis &AA, AssumptionCache &AC, + const TargetLibraryInfo &TLI, + DominatorTree *DT = nullptr) + : AA(AA), AC(AC), TLI(TLI), DT(DT) {} /// Returns the instruction on which a memory operation depends. /// @@ -453,6 +443,9 @@ public: unsigned MemLocSize, const LoadInst *LI); + /// Release memory in caches. + void releaseMemory(); + private: MemDepResult getCallSiteDependencyFrom(CallSite C, bool isReadOnlyCall, BasicBlock::iterator ScanIt, @@ -474,6 +467,37 @@ private: void verifyRemoved(Instruction *Inst) const; }; +/// An analysis that produces \c MemoryDependenceResults for a function. +/// +/// This is essentially a no-op because the results are computed entirely +/// lazily. +struct MemoryDependenceAnalysis : AnalysisBase { + typedef MemoryDependenceResults Result; + + MemoryDependenceResults run(Function &F, AnalysisManager *AM); +}; + +/// A wrapper analysis pass for the legacy pass manager that exposes a \c +/// MemoryDepnedenceResults instance. +class MemoryDependenceWrapperPass : public FunctionPass { + Optional MemDep; +public: + MemoryDependenceWrapperPass(); + ~MemoryDependenceWrapperPass() override; + static char ID; + + /// Pass Implementation stuff. This doesn't do any analysis eagerly. + bool runOnFunction(Function &) override; + + /// Clean up memory in between runs + void releaseMemory() override; + + /// Does not modify anything. It uses Value Numbering and Alias Analysis. + void getAnalysisUsage(AnalysisUsage &AU) const override; + + MemoryDependenceResults &getMemDep() { return *MemDep; } +}; + } // End llvm namespace #endif diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h index 58d2b87..96cf31e 100644 --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -211,7 +211,7 @@ void initializeMachineVerifierPassPass(PassRegistry&); void initializeMemCpyOptPass(PassRegistry&); void initializeMemDepPrinterPass(PassRegistry&); void initializeMemDerefPrinterPass(PassRegistry&); -void initializeMemoryDependenceAnalysisPass(PassRegistry&); +void initializeMemoryDependenceWrapperPassPass(PassRegistry&); void initializeMemorySSALazyPass(PassRegistry&); void initializeMemorySSAPrinterPassPass(PassRegistry&); void initializeMergedLoadStoreMotionPass(PassRegistry &); diff --git a/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h b/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h index 13c856d..b0fa6e5 100644 --- a/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h +++ b/llvm/include/llvm/Transforms/Utils/BasicBlockUtils.h @@ -22,7 +22,7 @@ namespace llvm { -class MemoryDependenceAnalysis; +class MemoryDependenceResults; class DominatorTree; class LoopInfo; class Instruction; @@ -40,7 +40,7 @@ void DeleteDeadBlock(BasicBlock *BB); /// when all entries to the PHI nodes in a block are guaranteed equal, such as /// when the block has exactly one predecessor. void FoldSingleEntryPHINodes(BasicBlock *BB, - MemoryDependenceAnalysis *MemDep = nullptr); + MemoryDependenceResults *MemDep = nullptr); /// DeleteDeadPHIs - Examine each PHI in the given block and delete it if it /// is dead. Also recursively delete any operands that become dead as @@ -53,7 +53,7 @@ bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI = nullptr); /// if possible. The return value indicates success or failure. bool MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT = nullptr, LoopInfo *LI = nullptr, - MemoryDependenceAnalysis *MemDep = nullptr); + MemoryDependenceResults *MemDep = nullptr); // ReplaceInstWithValue - Replace all uses of an instruction (specified by BI) // with a value, then remove and delete the original instruction. diff --git a/llvm/lib/Analysis/Analysis.cpp b/llvm/lib/Analysis/Analysis.cpp index b9c97c0..cf13dad 100644 --- a/llvm/lib/Analysis/Analysis.cpp +++ b/llvm/lib/Analysis/Analysis.cpp @@ -57,7 +57,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializeLoopInfoWrapperPassPass(Registry); initializeMemDepPrinterPass(Registry); initializeMemDerefPrinterPass(Registry); - initializeMemoryDependenceAnalysisPass(Registry); + initializeMemoryDependenceWrapperPassPass(Registry); initializeModuleDebugInfoPrinterPass(Registry); initializeObjCARCAAWrapperPassPass(Registry); initializePostDominatorTreeWrapperPassPass(Registry); diff --git a/llvm/lib/Analysis/MemDepPrinter.cpp b/llvm/lib/Analysis/MemDepPrinter.cpp index 078cefe..9116b82 100644 --- a/llvm/lib/Analysis/MemDepPrinter.cpp +++ b/llvm/lib/Analysis/MemDepPrinter.cpp @@ -50,7 +50,7 @@ namespace { void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequiredTransitive(); - AU.addRequiredTransitive(); + AU.addRequiredTransitive(); AU.setPreservesAll(); } @@ -79,7 +79,7 @@ namespace { char MemDepPrinter::ID = 0; INITIALIZE_PASS_BEGIN(MemDepPrinter, "print-memdeps", "Print MemDeps of function", false, true) -INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) +INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) INITIALIZE_PASS_END(MemDepPrinter, "print-memdeps", "Print MemDeps of function", false, true) @@ -92,7 +92,7 @@ const char *const MemDepPrinter::DepTypeStr[] bool MemDepPrinter::runOnFunction(Function &F) { this->F = &F; - MemoryDependenceAnalysis &MDA = getAnalysis(); + MemoryDependenceResults &MDA = getAnalysis().getMemDep(); // All this code uses non-const interfaces because MemDep is not // const-friendly, though nothing is actually modified. @@ -107,11 +107,11 @@ bool MemDepPrinter::runOnFunction(Function &F) { Deps[Inst].insert(std::make_pair(getInstTypePair(Res), static_cast(nullptr))); } else if (auto CS = CallSite(Inst)) { - const MemoryDependenceAnalysis::NonLocalDepInfo &NLDI = + const MemoryDependenceResults::NonLocalDepInfo &NLDI = MDA.getNonLocalCallDependency(CS); DepSet &InstDeps = Deps[Inst]; - for (MemoryDependenceAnalysis::NonLocalDepInfo::const_iterator + for (MemoryDependenceResults::NonLocalDepInfo::const_iterator I = NLDI.begin(), E = NLDI.end(); I != E; ++I) { const MemDepResult &Res = I->getResult(); InstDeps.insert(std::make_pair(getInstTypePair(Res), I->getBB())); diff --git a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp index 457b9e3..bdb845c 100644 --- a/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/llvm/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -64,49 +64,6 @@ static cl::opt // Limit on the number of memdep results to process. static const unsigned int NumResultsLimit = 100; -char MemoryDependenceAnalysis::ID = 0; - -INITIALIZE_PASS_BEGIN(MemoryDependenceAnalysis, "memdep", - "Memory Dependence Analysis", false, true) -INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) -INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) -INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) -INITIALIZE_PASS_END(MemoryDependenceAnalysis, "memdep", - "Memory Dependence Analysis", false, true) - -MemoryDependenceAnalysis::MemoryDependenceAnalysis() : FunctionPass(ID) { - initializeMemoryDependenceAnalysisPass(*PassRegistry::getPassRegistry()); -} -MemoryDependenceAnalysis::~MemoryDependenceAnalysis() {} - -/// Clean up memory in between runs -void MemoryDependenceAnalysis::releaseMemory() { - LocalDeps.clear(); - NonLocalDeps.clear(); - NonLocalPointerDeps.clear(); - ReverseLocalDeps.clear(); - ReverseNonLocalDeps.clear(); - ReverseNonLocalPtrDeps.clear(); - PredCache.clear(); -} - -void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { - AU.setPreservesAll(); - AU.addRequired(); - AU.addRequiredTransitive(); - AU.addRequiredTransitive(); -} - -bool MemoryDependenceAnalysis::runOnFunction(Function &F) { - AA = &getAnalysis().getAAResults(); - AC = &getAnalysis().getAssumptionCache(F); - DominatorTreeWrapperPass *DTWP = - getAnalysisIfAvailable(); - DT = DTWP ? &DTWP->getDomTree() : nullptr; - TLI = &getAnalysis().getTLI(); - return false; -} - /// This is a helper function that removes Val from 'Inst's set in ReverseMap. /// /// If the set becomes empty, remove Inst's entry. @@ -204,7 +161,7 @@ static ModRefInfo GetLocation(const Instruction *Inst, MemoryLocation &Loc, } /// Private helper for finding the local dependencies of a call site. -MemDepResult MemoryDependenceAnalysis::getCallSiteDependencyFrom( +MemDepResult MemoryDependenceResults::getCallSiteDependencyFrom( CallSite CS, bool isReadOnlyCall, BasicBlock::iterator ScanIt, BasicBlock *BB) { unsigned Limit = BlockScanLimit; @@ -221,10 +178,10 @@ MemDepResult MemoryDependenceAnalysis::getCallSiteDependencyFrom( // If this inst is a memory op, get the pointer it accessed MemoryLocation Loc; - ModRefInfo MR = GetLocation(Inst, Loc, *TLI); + ModRefInfo MR = GetLocation(Inst, Loc, TLI); if (Loc.Ptr) { // A simple instruction. - if (AA->getModRefInfo(CS, Loc) != MRI_NoModRef) + if (AA.getModRefInfo(CS, Loc) != MRI_NoModRef) return MemDepResult::getClobber(Inst); continue; } @@ -234,7 +191,7 @@ MemDepResult MemoryDependenceAnalysis::getCallSiteDependencyFrom( if (isa(Inst)) continue; // If these two calls do not interfere, look past it. - switch (AA->getModRefInfo(CS, InstCS)) { + switch (AA.getModRefInfo(CS, InstCS)) { case MRI_NoModRef: // If the two calls are the same, return InstCS as a Def, so that // CS can be found redundant and eliminated. @@ -278,12 +235,12 @@ static bool isLoadLoadClobberIfExtendedToFullWidth(const MemoryLocation &MemLoc, if (!MemLocBase) MemLocBase = GetPointerBaseWithConstantOffset(MemLoc.Ptr, MemLocOffs, DL); - unsigned Size = MemoryDependenceAnalysis::getLoadLoadClobberFullWidthSize( + unsigned Size = MemoryDependenceResults::getLoadLoadClobberFullWidthSize( MemLocBase, MemLocOffs, MemLoc.Size, LI); return Size != 0; } -unsigned MemoryDependenceAnalysis::getLoadLoadClobberFullWidthSize( +unsigned MemoryDependenceResults::getLoadLoadClobberFullWidthSize( const Value *MemLocBase, int64_t MemLocOffs, unsigned MemLocSize, const LoadInst *LI) { // We can only extend simple integer loads. @@ -368,7 +325,7 @@ static bool isVolatile(Instruction *Inst) { return false; } -MemDepResult MemoryDependenceAnalysis::getPointerDependencyFrom( +MemDepResult MemoryDependenceResults::getPointerDependencyFrom( const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst) { @@ -385,7 +342,7 @@ MemDepResult MemoryDependenceAnalysis::getPointerDependencyFrom( } MemDepResult -MemoryDependenceAnalysis::getInvariantGroupPointerDependency(LoadInst *LI, +MemoryDependenceResults::getInvariantGroupPointerDependency(LoadInst *LI, BasicBlock *BB) { Value *LoadOperand = LI->getPointerOperand(); // It's is not safe to walk the use list of global value, because function @@ -437,7 +394,7 @@ MemoryDependenceAnalysis::getInvariantGroupPointerDependency(LoadInst *LI, return Result; } -MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom( +MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom( const MemoryLocation &MemLoc, bool isLoad, BasicBlock::iterator ScanIt, BasicBlock *BB, Instruction *QueryInst) { @@ -531,7 +488,7 @@ MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom( // 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(MemoryLocation(II->getArgOperand(1)), MemLoc)) + if (AA.isMustAlias(MemoryLocation(II->getArgOperand(1)), MemLoc)) return MemDepResult::getDef(II); continue; } @@ -572,7 +529,7 @@ MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom( MemoryLocation LoadLoc = MemoryLocation::get(LI); // If we found a pointer, check if it could be the same as our pointer. - AliasResult R = AA->alias(LoadLoc, MemLoc); + AliasResult R = AA.alias(LoadLoc, MemLoc); if (isLoad) { if (R == NoAlias) { @@ -616,7 +573,7 @@ MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom( continue; // Stores don't alias loads from read-only memory. - if (AA->pointsToConstantMemory(LoadLoc)) + if (AA.pointsToConstantMemory(LoadLoc)) continue; // Stores depend on may/must aliased loads. @@ -647,7 +604,7 @@ MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom( // 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) == MRI_NoModRef) + if (AA.getModRefInfo(SI, MemLoc) == MRI_NoModRef) continue; // Ok, this store might clobber the query pointer. Check to see if it is @@ -655,7 +612,7 @@ MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom( MemoryLocation StoreLoc = MemoryLocation::get(SI); // If we found a pointer, check if it could be the same as our pointer. - AliasResult R = AA->alias(StoreLoc, MemLoc); + AliasResult R = AA.alias(StoreLoc, MemLoc); if (R == NoAlias) continue; @@ -672,9 +629,9 @@ MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom( // turn into undef. Note that we can bypass the allocation itself when // looking for a clobber in many cases; that's an alias property and is // handled by BasicAA. - if (isa(Inst) || isNoAliasFn(Inst, TLI)) { + if (isa(Inst) || isNoAliasFn(Inst, &TLI)) { const Value *AccessPtr = GetUnderlyingObject(MemLoc.Ptr, DL); - if (AccessPtr == Inst || AA->isMustAlias(Inst, AccessPtr)) + if (AccessPtr == Inst || AA.isMustAlias(Inst, AccessPtr)) return MemDepResult::getDef(Inst); } @@ -682,10 +639,10 @@ MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom( continue; // See if this instruction (e.g. a call or vaarg) mod/ref's the pointer. - ModRefInfo MR = AA->getModRefInfo(Inst, MemLoc); + ModRefInfo MR = AA.getModRefInfo(Inst, MemLoc); // If necessary, perform additional analysis. if (MR == MRI_ModRef) - MR = AA->callCapturesBefore(Inst, MemLoc, DT, &OBB); + MR = AA.callCapturesBefore(Inst, MemLoc, DT, &OBB); switch (MR) { case MRI_NoModRef: // If the call has no effect on the queried pointer, just ignore it. @@ -710,7 +667,7 @@ MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom( return MemDepResult::getNonFuncLocal(); } -MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { +MemDepResult MemoryDependenceResults::getDependency(Instruction *QueryInst) { Instruction *ScanPos = QueryInst; // Check for a cached result @@ -741,7 +698,7 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { LocalCache = MemDepResult::getNonFuncLocal(); } else { MemoryLocation MemLoc; - ModRefInfo MR = GetLocation(QueryInst, MemLoc, *TLI); + ModRefInfo MR = GetLocation(QueryInst, MemLoc, TLI); if (MemLoc.Ptr) { // If we can do a pointer scan, make it happen. bool isLoad = !(MR & MRI_Mod); @@ -752,7 +709,7 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { MemLoc, isLoad, ScanPos->getIterator(), QueryParent, QueryInst); } else if (isa(QueryInst) || isa(QueryInst)) { CallSite QueryCS(QueryInst); - bool isReadOnly = AA->onlyReadsMemory(QueryCS); + bool isReadOnly = AA.onlyReadsMemory(QueryCS); LocalCache = getCallSiteDependencyFrom( QueryCS, isReadOnly, ScanPos->getIterator(), QueryParent); } else @@ -770,7 +727,7 @@ MemDepResult MemoryDependenceAnalysis::getDependency(Instruction *QueryInst) { #ifndef NDEBUG /// This method is used when -debug is specified to verify that cache arrays /// are properly kept sorted. -static void AssertSorted(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, +static void AssertSorted(MemoryDependenceResults::NonLocalDepInfo &Cache, int Count = -1) { if (Count == -1) Count = Cache.size(); @@ -779,8 +736,8 @@ static void AssertSorted(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, } #endif -const MemoryDependenceAnalysis::NonLocalDepInfo & -MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { +const MemoryDependenceResults::NonLocalDepInfo & +MemoryDependenceResults::getNonLocalCallDependency(CallSite QueryCS) { assert(getDependency(QueryCS.getInstruction()).isNonLocal() && "getNonLocalCallDependency should only be used on calls with " "non-local deps!"); @@ -821,7 +778,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { } // isReadonlyCall - If this is a read-only call, we can be more aggressive. - bool isReadonlyCall = AA->onlyReadsMemory(QueryCS); + bool isReadonlyCall = AA.onlyReadsMemory(QueryCS); SmallPtrSet Visited; @@ -910,7 +867,7 @@ MemoryDependenceAnalysis::getNonLocalCallDependency(CallSite QueryCS) { return Cache; } -void MemoryDependenceAnalysis::getNonLocalPointerDependency( +void MemoryDependenceResults::getNonLocalPointerDependency( Instruction *QueryInst, SmallVectorImpl &Result) { const MemoryLocation Loc = MemoryLocation::get(QueryInst); bool isLoad = isa(QueryInst); @@ -943,7 +900,7 @@ void MemoryDependenceAnalysis::getNonLocalPointerDependency( return; } const DataLayout &DL = FromBB->getModule()->getDataLayout(); - PHITransAddr Address(const_cast(Loc.Ptr), DL, AC); + PHITransAddr Address(const_cast(Loc.Ptr), DL, &AC); // 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 @@ -963,7 +920,7 @@ void MemoryDependenceAnalysis::getNonLocalPointerDependency( /// info if available). /// /// If we do a lookup, add the result to the cache. -MemDepResult MemoryDependenceAnalysis::GetNonLocalInfoForBlock( +MemDepResult MemoryDependenceResults::GetNonLocalInfoForBlock( Instruction *QueryInst, const MemoryLocation &Loc, bool isLoad, BasicBlock *BB, NonLocalDepInfo *Cache, unsigned NumSortedEntries) { @@ -1033,7 +990,7 @@ MemDepResult MemoryDependenceAnalysis::GetNonLocalInfoForBlock( /// /// This is optimized for the case when only a few entries are added. static void -SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, +SortNonLocalDepInfoCache(MemoryDependenceResults::NonLocalDepInfo &Cache, unsigned NumSortedEntries) { switch (Cache.size() - NumSortedEntries) { case 0: @@ -1043,7 +1000,7 @@ SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, // Two new entries, insert the last one into place. NonLocalDepEntry Val = Cache.back(); Cache.pop_back(); - MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry = + MemoryDependenceResults::NonLocalDepInfo::iterator Entry = std::upper_bound(Cache.begin(), Cache.end() - 1, Val); Cache.insert(Entry, Val); // FALL THROUGH. @@ -1053,7 +1010,7 @@ SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, if (Cache.size() != 1) { NonLocalDepEntry Val = Cache.back(); Cache.pop_back(); - MemoryDependenceAnalysis::NonLocalDepInfo::iterator Entry = + MemoryDependenceResults::NonLocalDepInfo::iterator Entry = std::upper_bound(Cache.begin(), Cache.end(), Val); Cache.insert(Entry, Val); } @@ -1078,7 +1035,7 @@ SortNonLocalDepInfoCache(MemoryDependenceAnalysis::NonLocalDepInfo &Cache, /// This function returns true on success, or false 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( +bool MemoryDependenceResults::getNonLocalPointerDepFromBB( Instruction *QueryInst, const PHITransAddr &Pointer, const MemoryLocation &Loc, bool isLoad, BasicBlock *StartBB, SmallVectorImpl &Result, @@ -1459,7 +1416,7 @@ bool MemoryDependenceAnalysis::getNonLocalPointerDepFromBB( } /// If P exists in CachedNonLocalPointerInfo, remove it. -void MemoryDependenceAnalysis::RemoveCachedNonLocalPointerDependencies( +void MemoryDependenceResults::RemoveCachedNonLocalPointerDependencies( ValueIsLoadPair P) { CachedNonLocalPointerInfo::iterator It = NonLocalPointerDeps.find(P); if (It == NonLocalPointerDeps.end()) @@ -1483,7 +1440,7 @@ void MemoryDependenceAnalysis::RemoveCachedNonLocalPointerDependencies( NonLocalPointerDeps.erase(It); } -void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) { +void MemoryDependenceResults::invalidateCachedPointerInfo(Value *Ptr) { // If Ptr isn't really a pointer, just ignore it. if (!Ptr->getType()->isPointerTy()) return; @@ -1493,11 +1450,11 @@ void MemoryDependenceAnalysis::invalidateCachedPointerInfo(Value *Ptr) { RemoveCachedNonLocalPointerDependencies(ValueIsLoadPair(Ptr, true)); } -void MemoryDependenceAnalysis::invalidateCachedPredecessors() { +void MemoryDependenceResults::invalidateCachedPredecessors() { PredCache.clear(); } -void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { +void MemoryDependenceResults::removeInstruction(Instruction *RemInst) { // Walk through the Non-local dependencies, removing this one as the value // for any cached queries. NonLocalDepMapType::iterator NLDI = NonLocalDeps.find(RemInst); @@ -1659,7 +1616,7 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction *RemInst) { /// structures. /// /// This function verifies by asserting in debug builds. -void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const { +void MemoryDependenceResults::verifyRemoved(Instruction *D) const { #ifndef NDEBUG for (const auto &DepKV : LocalDeps) { assert(DepKV.first != D && "Inst occurs in data structures"); @@ -1701,3 +1658,48 @@ void MemoryDependenceAnalysis::verifyRemoved(Instruction *D) const { } #endif } + +MemoryDependenceResults +MemoryDependenceAnalysis::run(Function &F, AnalysisManager *AM) { + auto &AA = AM->getResult(F); + auto &AC = AM->getResult(F); + auto &TLI = AM->getResult(F); + auto *DT = AM->getCachedResult(F); + return MemoryDependenceResults(AA, AC, TLI, DT); +} + +char MemoryDependenceWrapperPass::ID = 0; + +INITIALIZE_PASS_BEGIN(MemoryDependenceWrapperPass, "memdep", + "Memory Dependence Analysis", false, true) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_END(MemoryDependenceWrapperPass, "memdep", + "Memory Dependence Analysis", false, true) + +MemoryDependenceWrapperPass::MemoryDependenceWrapperPass() : FunctionPass(ID) { + initializeMemoryDependenceWrapperPassPass(*PassRegistry::getPassRegistry()); +} +MemoryDependenceWrapperPass::~MemoryDependenceWrapperPass() {} + +void MemoryDependenceWrapperPass::releaseMemory() { + MemDep.reset(); +} + +void MemoryDependenceWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); + AU.addRequiredTransitive(); + AU.addRequiredTransitive(); +} + +bool MemoryDependenceWrapperPass::runOnFunction(Function &F) { + auto &AA = getAnalysis().getAAResults(); + auto &AC = getAnalysis().getAssumptionCache(F); + auto &TLI = getAnalysis().getTLI(); + auto *DTWP = getAnalysisIfAvailable(); + MemDep.emplace(AA, AC, TLI, DTWP ? &DTWP->getDomTree() : nullptr); + return false; +} + diff --git a/llvm/lib/CodeGen/MachineFunctionPass.cpp b/llvm/lib/CodeGen/MachineFunctionPass.cpp index 5ca41be..1913d99 100644 --- a/llvm/lib/CodeGen/MachineFunctionPass.cpp +++ b/llvm/lib/CodeGen/MachineFunctionPass.cpp @@ -59,7 +59,7 @@ void MachineFunctionPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp index eab4eda..38e1dd0 100644 --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -26,6 +26,7 @@ #include "llvm/Analysis/DominanceFrontier.h" #include "llvm/Analysis/LazyCallGraph.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/MemoryDependenceAnalysis.h" #include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/RegionInfo.h" #include "llvm/Analysis/ScalarEvolution.h" diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def index a7e2b90..51c7ff6 100644 --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -60,6 +60,7 @@ FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis()) FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis()) FUNCTION_ANALYSIS("domfrontier", DominanceFrontierAnalysis()) FUNCTION_ANALYSIS("loops", LoopAnalysis()) +FUNCTION_ANALYSIS("memdep", MemoryDependenceAnalysis()) FUNCTION_ANALYSIS("regions", RegionInfoAnalysis()) FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis()) FUNCTION_ANALYSIS("scalar-evolution", ScalarEvolutionAnalysis()) diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp index 36ad0a5..61bbdf0 100644 --- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -48,7 +48,7 @@ STATISTIC(NumFastOther , "Number of other instrs removed"); namespace { struct DSE : public FunctionPass { AliasAnalysis *AA; - MemoryDependenceAnalysis *MD; + MemoryDependenceResults *MD; DominatorTree *DT; const TargetLibraryInfo *TLI; @@ -62,7 +62,7 @@ namespace { return false; AA = &getAnalysis().getAAResults(); - MD = &getAnalysis(); + MD = &getAnalysis().getMemDep(); DT = &getAnalysis().getDomTree(); TLI = &getAnalysis().getTLI(); @@ -89,11 +89,11 @@ namespace { AU.setPreservesCFG(); AU.addRequired(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addPreserved(); AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); } }; } @@ -103,7 +103,7 @@ INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) -INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) +INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false) @@ -120,7 +120,7 @@ FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } /// If ValueSet is non-null, remove any deleted instructions from it as well. /// static void DeleteDeadInstruction(Instruction *I, - MemoryDependenceAnalysis &MD, + MemoryDependenceResults &MD, const TargetLibraryInfo &TLI, SmallSetVector *ValueSet = nullptr) { SmallVector NowDeadInsts; diff --git a/llvm/lib/Transforms/Scalar/GVN.cpp b/llvm/lib/Transforms/Scalar/GVN.cpp index ca9db8d..6db5e34 100644 --- a/llvm/lib/Transforms/Scalar/GVN.cpp +++ b/llvm/lib/Transforms/Scalar/GVN.cpp @@ -112,7 +112,7 @@ namespace { DenseMap valueNumbering; DenseMap expressionNumbering; AliasAnalysis *AA; - MemoryDependenceAnalysis *MD; + MemoryDependenceResults *MD; DominatorTree *DT; uint32_t nextValueNumber; @@ -135,7 +135,7 @@ namespace { void erase(Value *v); void setAliasAnalysis(AliasAnalysis* A) { AA = A; } AliasAnalysis *getAliasAnalysis() const { return AA; } - void setMemDep(MemoryDependenceAnalysis* M) { MD = M; } + void setMemDep(MemoryDependenceResults* M) { MD = M; } void setDomTree(DominatorTree* D) { DT = D; } uint32_t getNextUnusedValueNumber() { return nextValueNumber; } void verifyRemoved(const Value *) const; @@ -332,7 +332,7 @@ uint32_t ValueTable::lookup_or_add_call(CallInst *C) { } // Non-local case. - const MemoryDependenceAnalysis::NonLocalDepInfo &deps = + const MemoryDependenceResults::NonLocalDepInfo &deps = MD->getNonLocalCallDependency(CallSite(C)); // FIXME: Move the checking logic to MemDep! CallInst* cdep = nullptr; @@ -625,7 +625,7 @@ namespace { class GVN : public FunctionPass { bool NoLoads; - MemoryDependenceAnalysis *MD; + MemoryDependenceResults *MD; DominatorTree *DT; const TargetLibraryInfo *TLI; AssumptionCache *AC; @@ -671,7 +671,7 @@ namespace { DominatorTree &getDominatorTree() const { return *DT; } AliasAnalysis *getAliasAnalysis() const { return VN.getAliasAnalysis(); } - MemoryDependenceAnalysis &getMemDep() const { return *MD; } + MemoryDependenceResults &getMemDep() const { return *MD; } private: /// Push a new Value to the LeaderTable onto the list for its value number. void addToLeaderTable(uint32_t N, Value *V, const BasicBlock *BB) { @@ -727,7 +727,7 @@ namespace { AU.addRequired(); AU.addRequired(); if (!NoLoads) - AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addPreserved(); @@ -785,7 +785,7 @@ FunctionPass *llvm::createGVNPass(bool NoLoads) { INITIALIZE_PASS_BEGIN(GVN, "gvn", "Global Value Numbering", false, false) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) -INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) +INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) @@ -1105,7 +1105,7 @@ static int AnalyzeLoadFromClobberingLoad(Type *LoadTy, Value *LoadPtr, GetPointerBaseWithConstantOffset(LoadPtr, LoadOffs, DL); unsigned LoadSize = DL.getTypeStoreSize(LoadTy); - unsigned Size = MemoryDependenceAnalysis::getLoadLoadClobberFullWidthSize( + unsigned Size = MemoryDependenceResults::getLoadLoadClobberFullWidthSize( LoadBase, LoadOffs, LoadSize, DepLI); if (Size == 0) return -1; @@ -2358,7 +2358,7 @@ bool GVN::runOnFunction(Function& F) { return false; if (!NoLoads) - MD = &getAnalysis(); + MD = &getAnalysis().getMemDep(); DT = &getAnalysis().getDomTree(); AC = &getAnalysis().getAssumptionCache(F); TLI = &getAnalysis().getTLI(); diff --git a/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp b/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp index 6b43b0f..3d84c3c 100644 --- a/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp +++ b/llvm/lib/Transforms/Scalar/MemCpyOptimizer.cpp @@ -306,7 +306,7 @@ void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr, namespace { class MemCpyOpt : public FunctionPass { - MemoryDependenceAnalysis *MD; + MemoryDependenceResults *MD; TargetLibraryInfo *TLI; public: static char ID; // Pass identification, replacement for typeid @@ -324,11 +324,11 @@ namespace { AU.setPreservesCFG(); AU.addRequired(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addRequired(); AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); } // Helper functions @@ -358,7 +358,7 @@ INITIALIZE_PASS_BEGIN(MemCpyOpt, "memcpyopt", "MemCpy Optimization", false, false) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) +INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) @@ -1284,7 +1284,7 @@ bool MemCpyOpt::runOnFunction(Function &F) { return false; bool MadeChange = false; - MD = &getAnalysis(); + MD = &getAnalysis().getMemDep(); TLI = &getAnalysis().getTLI(); // If we don't have at least memset and memcpy, there is little point of doing diff --git a/llvm/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp b/llvm/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp index c812d61..56942158d 100644 --- a/llvm/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp +++ b/llvm/lib/Transforms/Scalar/MergedLoadStoreMotion.cpp @@ -104,7 +104,7 @@ using namespace llvm; namespace { class MergedLoadStoreMotion : public FunctionPass { AliasAnalysis *AA; - MemoryDependenceAnalysis *MD; + MemoryDependenceResults *MD; public: static char ID; // Pass identification, replacement for typeid @@ -122,7 +122,7 @@ private: AU.addRequired(); AU.addRequired(); AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); } // Helper routines @@ -170,7 +170,7 @@ FunctionPass *llvm::createMergedLoadStoreMotionPass() { INITIALIZE_PASS_BEGIN(MergedLoadStoreMotion, "mldst-motion", "MergedLoadStoreMotion", false, false) -INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) +INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) @@ -565,7 +565,8 @@ bool MergedLoadStoreMotion::mergeStores(BasicBlock *T) { /// \brief Run the transformation for each function /// bool MergedLoadStoreMotion::runOnFunction(Function &F) { - MD = getAnalysisIfAvailable(); + auto *MDWP = getAnalysisIfAvailable(); + MD = MDWP ? &MDWP->getMemDep() : nullptr; AA = &getAnalysis().getAAResults(); bool Changed = false; diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp index 72db980..bb11a98 100644 --- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -66,7 +66,7 @@ void llvm::DeleteDeadBlock(BasicBlock *BB) { /// when all entries to the PHI nodes in a block are guaranteed equal, such as /// when the block has exactly one predecessor. void llvm::FoldSingleEntryPHINodes(BasicBlock *BB, - MemoryDependenceAnalysis *MemDep) { + MemoryDependenceResults *MemDep) { if (!isa(BB->begin())) return; while (PHINode *PN = dyn_cast(BB->begin())) { @@ -107,7 +107,7 @@ bool llvm::DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI) { /// if possible. The return value indicates success or failure. bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DominatorTree *DT, LoopInfo *LI, - MemoryDependenceAnalysis *MemDep) { + MemoryDependenceResults *MemDep) { // Don't merge away blocks who have their address taken. if (BB->hasAddressTaken()) return false; diff --git a/llvm/test/Other/new-pass-manager.ll b/llvm/test/Other/new-pass-manager.ll index 9c31f1d..67a6672 100644 --- a/llvm/test/Other/new-pass-manager.ll +++ b/llvm/test/Other/new-pass-manager.ll @@ -315,6 +315,14 @@ ; CHECK-AA: Running analysis: BasicAA ; CHECK-AA: Finished llvm::Module pass manager run +; RUN: opt -disable-output -disable-verify -debug-pass-manager %s 2>&1 \ +; RUN: -passes='require' \ +; RUN: | FileCheck %s --check-prefix=CHECK-MEMDEP +; CHECK-MEMDEP: Starting llvm::Module pass manager run +; CHECK-MEMDEP: Running pass: RequireAnalysisPass +; CHECK-MEMDEP: Running analysis: MemoryDependenceAnalysis +; CHECK-MEMDEP: Finished llvm::Module pass manager run + ; RUN: opt -disable-output -disable-verify -debug-pass-manager \ ; RUN: -passes='default' %s 2>&1 \ ; RUN: | FileCheck %s --check-prefix=CHECK-O2 -- 2.7.4