diff --git a/clang/lib/CodeGen/BackendUtil.cpp b/clang/lib/CodeGen/BackendUtil.cpp --- a/clang/lib/CodeGen/BackendUtil.cpp +++ b/clang/lib/CodeGen/BackendUtil.cpp @@ -1174,6 +1174,7 @@ #include "llvm/Support/Extension.def" LoopAnalysisManager LAM(CodeGenOpts.DebugPassManager); + LoopNestAnalysisManager LNAM(LAM); FunctionAnalysisManager FAM(CodeGenOpts.DebugPassManager); CGSCCAnalysisManager CGAM(CodeGenOpts.DebugPassManager); ModuleAnalysisManager MAM(CodeGenOpts.DebugPassManager); @@ -1193,7 +1194,8 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); ModulePassManager MPM(CodeGenOpts.DebugPassManager); diff --git a/llvm/include/llvm/Analysis/LoopNestAnalysis.h b/llvm/include/llvm/Analysis/LoopNestAnalysis.h --- a/llvm/include/llvm/Analysis/LoopNestAnalysis.h +++ b/llvm/include/llvm/Analysis/LoopNestAnalysis.h @@ -16,6 +16,7 @@ #include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" namespace llvm { @@ -128,8 +129,18 @@ [](const Loop *L) { return L->isLoopSimplifyForm(); }); } + StringRef getName() const { + // FIXME: Choose a better name for loop nests so that they are + // distinguishable from the loops' names. + Loop &Root = getOutermostLoop(); + return Root.getName(); + } + + /// Reconstruct the loop nest inplace. + void reconstructInplace(ScalarEvolution &SE); + protected: - const unsigned MaxPerfectDepth; // maximum perfect nesting depth level. + unsigned MaxPerfectDepth; // maximum perfect nesting depth level. LoopVectorTy Loops; // the loops in the nest (in breadth first order). }; diff --git a/llvm/include/llvm/Analysis/LoopNestAnalysisManager.h b/llvm/include/llvm/Analysis/LoopNestAnalysisManager.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Analysis/LoopNestAnalysisManager.h @@ -0,0 +1,217 @@ +//===- LoopNestAnalysisManager.h - LoopNest analysis management ---------*- C++ +//-*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_LOOPNESTANALYSISMANAGER_H +#define LLVM_ANALYSIS_LOOPNESTANALYSISMANAGER_H + +#include "llvm/Analysis/LoopNestAnalysis.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +class LNPMUpdater; + +/// The loop nest analysis manager. +/// +/// The loop nest analyses should run on \Loop instead of LoopNests since +/// \c LoopNest are constantly invalidated by both loop nest passes and loop +/// passes. Generally speaking, the passes should update the analysis results +/// dynamically when possible, and running on Loops prevent the analyses from +/// being invalidated when the loop structures change. +/// +/// \c LoopNestAnalysisManager is a wrapper around \c LoopAnalysisManager and +/// provide all the public APIs that \c AnalysisManager has so that is seems to +/// be operating on \c LoopNest. \c LoopNestAnalysisManager also provides the +/// ability to construct \c LoopNest from the top-level \c Loop. The loop nest +/// analyses can also obtain the \c LoopNest object from the \c +/// LoopAnalysisManager. +/// +/// The \c LoopNest object will be invalidated after the loop nest passes unless +/// \c LoopNestAnalysis is explicitly marked as preserved. +template <> class AnalysisManager { +public: + class Invalidator { + public: + /// The following methods should never be called because the + /// invalidation in \c LoopNestAnalysisManager will be passed to the + /// internal \c LoopAnalysisManager. The only purpose of these methods is to + /// satisfy the requirements of being an \c AnalysisManager. + template + bool invalidate(LoopNest &, const PreservedAnalyses &) { + assert(false && "This method should never be called."); + return false; + } + + bool invalidate(AnalysisKey *, LoopNest &, const PreservedAnalyses &) { + assert(false && "This method should never be called."); + return false; + } + }; + + AnalysisManager(LoopAnalysisManager &LAM) : InternalLAM(LAM) {} + + bool empty() const { return InternalLAM.empty(); }; + + void clear(LoopNest &LN, llvm::StringRef Name) { + InternalLAM.clear(LN.getOutermostLoop(), Name); + } + void clear(Loop &L, llvm::StringRef Name) { InternalLAM.clear(L, Name); } + void clear() { InternalLAM.clear(); } + + LoopNest &getLoopNest(Loop &Root, LoopStandardAnalysisResults &LAR) { + return InternalLAM.getResult(Root, LAR); + } + + /// Get the result of an analysis pass for a given LoopNest. + /// + /// Runs the analysis if a cached result is not available. + template + typename PassT::Result &getResult(LoopNest &LN, + LoopStandardAnalysisResults &LAR) { + return InternalLAM.getResult(LN.getOutermostLoop(), LAR); + } + template + typename PassT::Result &getResult(Loop &L, LoopStandardAnalysisResults &LAR) { + return InternalLAM.getResult(L, LAR); + } + + /// Get the cached result of an analysis pass for a given LoopNest. + /// + /// This method never runs the analysis. + /// + /// \returns null if there is no cached result. + template + typename PassT::Result *getCachedResult(LoopNest &LN) const { + return InternalLAM.getCachedResult(LN.getOutermostLoop()); + } + template + typename PassT::Result *getCachedResult(Loop &L) const { + return InternalLAM.getCachedResult(L); + } + + template + void verifyNotInvalidated(LoopNest &LN, + typename PassT::Result *Result) const { + InternalLAM.verifyNotInvalidated(LN.getOutermostLoop(), Result); + } + template + void verifyNotInvalidated(Loop &L, typename PassT::Result *Result) const { + InternalLAM.verifyNotInvalidated(L, Result); + } + + template + bool registerPass(PassBuilderT &&PassBuilder) { + return InternalLAM.registerPass(std::forward(PassBuilder)); + } + + /// Invalidate the analysis results. Aside from the loop nest analyses of the + /// root loop, we have to invalidate the loop analyses of all the subtree as + /// well. + void invalidate(LoopNest &LN, const PreservedAnalyses &PA) { + invalidateSubLoopAnalyses(LN.getOutermostLoop(), PA); + InternalLAM.invalidate(LN.getOutermostLoop(), PA); + } + void invalidate(Loop &L, const PreservedAnalyses &PA) { + invalidateSubLoopAnalyses(L, PA); + InternalLAM.invalidate(L, PA); + } + + LoopAnalysisManager &getLoopAnalysisManager() { return InternalLAM; } + +private: + LoopAnalysisManager &InternalLAM; + friend class InnerAnalysisManagerProxy< + AnalysisManager, Function>; + + /// Invalidate the loop analyses of loops in the subtree rooted at \p L + /// (excluding \p L). + void invalidateSubLoopAnalyses(Loop &L, const PreservedAnalyses &PA); +}; + +using LoopNestAnalysisManager = + AnalysisManager; +using LoopNestAnalysisManagerFunctionProxy = + InnerAnalysisManagerProxy; + +/// A specialized result for the \c LoopNestAnalysisManagerFunctionProxy which +/// retains a \c LoopInfo reference. +/// +/// This allows it to collect loop nest objects for which analysis results may +/// be cached in the \c LoopNestAnalysisManager. +template <> class LoopNestAnalysisManagerFunctionProxy::Result { +public: + explicit Result(LoopNestAnalysisManager &InnerAM, LoopInfo &LI) + : InnerAM(&InnerAM), LI(&LI), MSSAUsed(false) {} + Result(Result &&Arg) + : InnerAM(std::move(Arg.InnerAM)), LI(Arg.LI), MSSAUsed(Arg.MSSAUsed) { + // We have to null out the analysis manager in the moved-from state + // because we are taking ownership of the responsibilty to clear the + // analysis state. + Arg.InnerAM = nullptr; + } + Result &operator=(Result &&RHS) { + InnerAM = RHS.InnerAM; + LI = RHS.LI; + MSSAUsed = RHS.MSSAUsed; + // We have to null out the analysis manager in the moved-from state + // because we are taking ownership of the responsibilty to clear the + // analysis state. + RHS.InnerAM = nullptr; + return *this; + } + ~Result() { + // InnerAM is cleared in a moved from state where there is nothing to do. + if (!InnerAM) + return; + + // Clear out the analysis manager if we're being destroyed -- it means we + // didn't even see an invalidate call when we got invalidated. + InnerAM->clear(); + } + + /// Mark MemorySSA as used so we can invalidate self if MSSA is invalidated. + void markMSSAUsed() { MSSAUsed = true; } + + /// Accessor for the analysis manager. + LoopNestAnalysisManager &getManager() { return *InnerAM; } + + /// Handler for invalidation of the proxy for a particular function. + /// + /// If the proxy, \c LoopInfo, and associated analyses are preserved, this + /// will merely forward the invalidation event to any cached loop analysis + /// results for loops within this function. + /// + /// If the necessary loop infrastructure is not preserved, this will forcibly + /// clear all of the cached analysis results that are keyed on the \c + /// LoopInfo for this function. + bool invalidate(Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv); + +private: + LoopNestAnalysisManager *InnerAM; + LoopInfo *LI; + bool MSSAUsed; +}; + +template <> +LoopNestAnalysisManagerFunctionProxy::Result +LoopNestAnalysisManagerFunctionProxy::run(Function &F, + FunctionAnalysisManager &AM); + +extern template class InnerAnalysisManagerProxy; +extern template class OuterAnalysisManagerProxy; +using FunctionAnalysisManagerLoopNestProxy = + OuterAnalysisManagerProxy; + +} // namespace llvm + +#endif // LLVM_ANALYSIS_LOOPNESTANALYSISMANAGER_H diff --git a/llvm/include/llvm/Passes/PassBuilder.h b/llvm/include/llvm/Passes/PassBuilder.h --- a/llvm/include/llvm/Passes/PassBuilder.h +++ b/llvm/include/llvm/Passes/PassBuilder.h @@ -17,10 +17,12 @@ #include "llvm/ADT/Optional.h" #include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/LoopNestAnalysisManager.h" #include "llvm/IR/PassManager.h" #include "llvm/Support/Error.h" #include "llvm/Transforms/IPO/Inliner.h" #include "llvm/Transforms/Instrumentation.h" +#include "llvm/Transforms/Scalar/LoopNestPassManager.h" #include "llvm/Transforms/Scalar/LoopPassManager.h" #include @@ -270,6 +272,7 @@ /// This is an interface that can be used to cross register each /// AnalysisManager with all the others analysis managers. void crossRegisterProxies(LoopAnalysisManager &LAM, + LoopNestAnalysisManager &LNAM, FunctionAnalysisManager &FAM, CGSCCAnalysisManager &CGAM, ModuleAnalysisManager &MAM); @@ -305,6 +308,13 @@ /// additional analyses. void registerLoopAnalyses(LoopAnalysisManager &LAM); + /// Registers all available loop nest analysis passes. + /// + /// This is an interface that can be used to populate a \c + /// LoopNestAnalysisManager with all registered loop nest analyses. Callers + /// can still manually register any additional analyses. + void registerLoopNestAnalyses(LoopNestAnalysisManager &LNAM); + /// Construct the core LLVM function canonicalization and simplification /// pipeline. /// @@ -507,6 +517,9 @@ Error parsePassPipeline(LoopPassManager &LPM, StringRef PipelineText, bool VerifyEachPass = true, bool DebugLogging = false); + Error parsePassPipeline(LoopNestPassManager &LNPM, StringRef PipelineText, + bool &UseMemorySSA, bool VerifyEachPass = true, + bool DebugLogging = false); /// @}} /// Parse a textual alias analysis pipeline into the provided AA manager. @@ -643,6 +656,10 @@ const std::function &C) { LoopAnalysisRegistrationCallbacks.push_back(C); } + void registerAnalysisRegistrationCallback( + const std::function &C) { + LoopNestAnalysisRegistrationCallbacks.push_back(C); + } void registerAnalysisRegistrationCallback( const std::function &C) { ModuleAnalysisRegistrationCallbacks.push_back(C); @@ -668,6 +685,11 @@ ArrayRef)> &C) { LoopPipelineParsingCallbacks.push_back(C); } + void registerPipelineParsingCallback( + const std::function)> &C) { + LoopNestPipelineParsingCallbacks.push_back(C); + } void registerPipelineParsingCallback( const std::function)> &C) { @@ -715,11 +737,18 @@ bool VerifyEachPass, bool DebugLogging); Error parseLoopPass(LoopPassManager &LPM, const PipelineElement &E, bool VerifyEachPass, bool DebugLogging); + Error parseLoopNestPass(LoopNestPassManager &LNPM, const PipelineElement &E, + bool &UseMemorySSA, bool VerifyEachPass, + bool DebugLogging); bool parseAAPassName(AAManager &AA, StringRef Name); Error parseLoopPassPipeline(LoopPassManager &LPM, ArrayRef Pipeline, bool VerifyEachPass, bool DebugLogging); + Error parseLoopNestPassPipeline(LoopNestPassManager &LNPM, + ArrayRef Pipeline, + bool &UseMemorySSA, bool VerifyEachPass, + bool DebugLogging); Error parseFunctionPassPipeline(FunctionPassManager &FPM, ArrayRef Pipeline, bool VerifyEachPass, bool DebugLogging); @@ -785,6 +814,13 @@ ArrayRef)>, 2> LoopPipelineParsingCallbacks; + // LoopNest callbacks + SmallVector, 2> + LoopNestAnalysisRegistrationCallbacks; + SmallVector)>, + 2> + LoopNestPipelineParsingCallbacks; // AA callbacks SmallVector, 2> AAParsingCallbacks; diff --git a/llvm/include/llvm/Transforms/Scalar/LoopNestPassManager.h b/llvm/include/llvm/Transforms/Scalar/LoopNestPassManager.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Transforms/Scalar/LoopNestPassManager.h @@ -0,0 +1,359 @@ +//===- LoopNestPassManager.h - Loop nest pass management -----------------*- C++ +//-*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_LOOPNESTPASSMANAGER_H +#define LLVM_TRANSFORMS_SCALAR_LOOPNESTPASSMANAGER_H + +#include "llvm/ADT/PriorityWorklist.h" +#include "llvm/Analysis/LoopNestAnalysis.h" +#include "llvm/Analysis/LoopNestAnalysisManager.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +namespace llvm { + +class LNPMUpdater; + +template <> +PreservedAnalyses +PassManager::run(LoopNest &LN, LoopNestAnalysisManager &AM, + LoopStandardAnalysisResults &AR, + LNPMUpdater &U); + +extern template class PassManager; + +using LoopNestPassManager = + PassManager; + +/// A partial specialization of the require analysis template pass for loop +/// nests to forward the extra parameters from a transformation's run method to +/// the AnalysisManager's getResult. +template +struct RequireAnalysisPass + : PassInfoMixin< + RequireAnalysisPass> { + PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LNPMUpdater &) { + (void)AM.template getResult(LN, AR); + return PreservedAnalyses::all(); + } +}; + +template +using RequireAnalysisLoopNestPass = + RequireAnalysisPass; + +/// This class provides an interface for updating the loop nest pass manager +/// based on mutations to the loop nest. +/// +/// A reference to an instance of this class is passed as an argument to each +/// LoopNest pass, and LoopNest passes should use it to update LNPM +/// infrastructure if they modify the loop nest structure. +class LNPMUpdater { +public: + /// This can be queried by loop nest passes which run other loop nest passes + /// (like pass managers) to know whether the loop nest needs to be skipped due + /// to updates to the loop nest. + /// + /// If this returns true, the loop nest object may have been deleted, so + /// passes should take care not to touch the object. + bool skipCurrentLoopNest() const { return SkipCurrentLoopNest; } + + void markLoopNestAsDeleted(LoopNest &LN, llvm::StringRef Name) { + LNAM.clear(LN, Name); + assert(&LN.getOutermostLoop() == CurrentLoopNest && + "Cannot delete loop nests other than the current one"); + SkipCurrentLoopNest = true; + } + + /// Loop nest passes should use this method to indicate they have added new + /// loop nests to the current function. + /// + /// \p NewLoopNests must only contain top-level loops. + void addNewLoopNests(ArrayRef NewLoopNests) { + for (Loop *NewL : NewLoopNests) { +#ifndef NDEBUG + assert(!NewL->getParentLoop() && + "All of the new loops must be top-level!"); +#endif + Worklist.insert(NewL); + } + } + + void revisitCurrentLoopNest() { + SkipCurrentLoopNest = true; + Worklist.insert(CurrentLoopNest); + } + +private: + template friend class FunctionToLoopNestPassAdaptor; + + LNPMUpdater(SmallPriorityWorklist &Worklist, + LoopNestAnalysisManager &LNAM) + : Worklist(Worklist), LNAM(LNAM) {} + + /// The \c FunctionToLoopNestPassAdaptor's worklist of loops to process. + SmallPriorityWorklist &Worklist; + + /// The analysis manager for use in the current loop nest; + LoopNestAnalysisManager &LNAM; + + Loop *CurrentLoopNest; + bool SkipCurrentLoopNest; +}; + +/// Adaptor that maps from a function to its loop nests. +/// +/// Designed to allow composition of a LoopNestPass(Manager) and a +/// FunctionPassManager. Note that if this pass is constructed with a \c +/// FunctionAnalysisManager it will run the \c +/// LoopNestAnalysisManagerFunctionProxy analysis prior to running the loop +/// passes over the function to enable a \c LoopNestAnalysisManager to be used +/// within this run safely. +template +class FunctionToLoopNestPassAdaptor + : public PassInfoMixin> { +public: + explicit FunctionToLoopNestPassAdaptor(LoopNestPassT Pass, + bool UseMemorySSA = false, + bool DebugLogging = false) + : Pass(std::move(Pass)), UseMemorySSA(UseMemorySSA), + LoopCanonicalizationFPM( + detail::getLoopCanonicalizationPasses(DebugLogging)) {} + + PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { + PassInstrumentation PI = AM.getResult(F); + + PreservedAnalyses PA = PreservedAnalyses::all(); + // Before we even compute any loop nest analyses, first run a miniature + // function pass pipeline to put loops into their canonical form. Note that + // we can directly build up function analyses after this as the function + // pass manager handles all the invalidation at that layer. + if (PI.runBeforePass(LoopCanonicalizationFPM, F)) { + PA = LoopCanonicalizationFPM.run(F, AM); + PI.runAfterPass(LoopCanonicalizationFPM, F); + } + + // Get the loop structure for this function. + LoopInfo &LI = AM.getResult(F); + + // If there are no loops, there is nothing to do here. + if (LI.empty()) + return PA; + + // Get the analysis results needed by loop nest passes. + LoopStandardAnalysisResults LAR = + detail::getLoopStandardAnalysisResults(F, AM, UseMemorySSA); + + // Setup the loop nest analysis manager from its proxy. It is important that + // this is only done when there are loops to process and we have built the + // LoopStandardAnalysisResults object. The loop nest analyses cached in this + // manager have access to those analysis results and so it must invalidate + // itself when they go away. + auto &LNAMFP = AM.getResult(F); + if (UseMemorySSA) + LNAMFP.markMSSAUsed(); + LoopNestAnalysisManager &LNAM = LNAMFP.getManager(); + + // The worklist of loop nests in the function. The loop nests are + // represented by their root loops and the actual LoopNest object will be + // constructed lazily when needed. + SmallPriorityWorklist Worklist; + LNPMUpdater Updater(Worklist, LNAM); + + // Append all outer-most loops in the function into the worklist. + for (Loop *L : LI.getTopLevelLoops()) + Worklist.insert(L); + + do { + Loop *L = Worklist.pop_back_val(); + + // Reset the update structure for this loop nest. + Updater.CurrentLoopNest = L; + Updater.SkipCurrentLoopNest = false; + + // Construct the actual LoopNest object from the analysis manager. + LoopNest &LN = LNAM.getLoopNest(*L, LAR); + // Check the PassInstrumentation's BeforePass callbacks before running the + // pass, skip its execution completely if asked to (callback returns + // false). + if (!PI.runBeforePass(Pass, LN)) + continue; + + PreservedAnalyses PassPA; + { + TimeTraceScope TimeScope(Pass.name()); + PassPA = Pass.run(LN, LNAM, LAR, Updater); + } + + // Do not pass deleted LoopNest into the instrumentation. + if (Updater.skipCurrentLoopNest()) + PI.runAfterPassInvalidated(Pass); + else + PI.runAfterPass(Pass, LN); + + if (!Updater.skipCurrentLoopNest()) + // We know that the loop nest pass couldn't have invalidated any other + // loop nest's analyses (that's the contract of a loop nest pass), so + // directly handle the loop nest analysis manager's invalidation here. + LNAM.invalidate(LN, PassPA); + + // Then intersect the preserved set so that invalidation of loop nest + // analyses will eventually occur when the loop nest pass completes. + PA.intersect(std::move(PassPA)); + } while (!Worklist.empty()); + + // By definition we preserve the proxy. We also preserve all analyses on + // LoopNests. This precludes *any* invalidation of loop nest analyses by the + // proxy, but that's OK because we've taken care to invalidate analyses in + // the loop nest analysis manager incrementally above. + PA.preserveSet>(); + PA.preserve(); + // We also preserve the set of standard analyses. + detail::preserveLoopStandardAnalysisResults(PA, UseMemorySSA); + detail::preserveAACategory(PA); + return PA; + } + +private: + LoopNestPassT Pass; + bool UseMemorySSA; + FunctionPassManager LoopCanonicalizationFPM; +}; + +/// A function to deduce a loop nest pass type and wrap it in the templated +/// adaptor. +template +FunctionToLoopNestPassAdaptor +createFunctionToLoopNestPassAdaptor(LoopNestPassT Pass, + bool UseMemorySSA = false, + bool DebugLogging = false) { + return FunctionToLoopNestPassAdaptor( + std::move(Pass), UseMemorySSA, DebugLogging); +} + +/// Pass for printing a loop nest's property. This is similar to +/// \c LoopNestPrinterPass in \file LoopNestAnalysis.h but implemented as a +/// LoopNestPass. +class PrintLoopNestPass : public PassInfoMixin { + raw_ostream &OS; + std::string Banner; + +public: + PrintLoopNestPass(); + explicit PrintLoopNestPass(raw_ostream &OS, const std::string &Banner = ""); + + PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &, + LoopStandardAnalysisResults &, LNPMUpdater &U); +}; + +/// Adaptor that maps from a loop nest to its loops. +template +class LoopNestToLoopPassAdaptor + : public PassInfoMixin> { +public: + explicit LoopNestToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) {} + + PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LNPMUpdater &U) { + PassInstrumentation PI = AM.getResult(LN, AR); + PreservedAnalyses PA = PreservedAnalyses::all(); + + // Get the loop analysis manager from the loop nest analysis manager. No + // need to set up proxy here since currently the latter is simply a wrapper + // around the former. + LoopAnalysisManager &LAM = AM.getLoopAnalysisManager(); + + SmallPriorityWorklist Worklist; + LPMUpdater Updater(Worklist, LAM); + appendLoopNestToWorklist(LN.getOutermostLoop(), Worklist); + + assert(!Worklist.empty() && + "Worklist should be non-empty since we're running on a LoopNest"); + + // Save a copy of the root loop and its name here in case they are + // invalidated later. + const Loop *Root = &LN.getOutermostLoop(); + const std::string LoopNestName = std::string(LN.getName()); + + do { + Loop *L = Worklist.pop_back_val(); + Updater.CurrentL = L; + Updater.SkipCurrentLoop = false; + +#ifndef NDEBUG + // Save a parent loop pointer for asserts. + Updater.ParentL = L->getParentLoop(); + + // Verify the loop structure and LCSSA form. + L->verifyLoop(); + assert(L->isRecursivelyLCSSAForm(AR.DT, AR.LI) && + "Loops must remain in LCSSA form!"); +#endif + + // Check the PassInstrumentation's BeforePass callbacks before running the + // loop pass. + if (!PI.runBeforePass(Pass, *L)) + continue; + + PreservedAnalyses PassPA; + { + TimeTraceScope TimeScope(Pass.name()); + PassPA = Pass.run(*L, LAM, AR, Updater); + } + + // Do not pass deleted Loop into the instrumentation. + if (Updater.skipCurrentLoop()) + PI.runAfterPassInvalidated(Pass); + else + PI.runAfterPass(Pass, *L); + + if (!Updater.SkipCurrentLoop) + // Invalidate the loop analysis results here. + LAM.invalidate(*L, PassPA); + + PA.intersect(std::move(PassPA)); + } while (!Worklist.empty()); + + // Since the loops are processed in post-order, at this point CurrentL in + // Updater should points to the root loop. If the root loop is marked as + // deleted, we should also delete the loop nest from the function. + assert(Updater.CurrentL == Root && "CurrentL should point to the root loop " + "after traversing the loop nest."); + if (Updater.skipCurrentLoop()) + U.markLoopNestAsDeleted(LN, LoopNestName); + + // We don't have to explicitly mark the loop standard analysis results as + // preserved here since this will eventually be handled by the \c + // FunctionToLoopNestPassAdaptor. + PA.preserveSet>(); + return PA; + } + +private: + LoopPassT Pass; +}; + +/// A function to deduce a loop pass type and wrap it in the templated +/// adaptor that converts it to a loop nest pass. +template +LoopNestToLoopPassAdaptor +createLoopNestToLoopPassAdaptor(LoopPassT Pass) { + return LoopNestToLoopPassAdaptor(std::move(Pass)); +} + +} // namespace llvm + +#endif // LLVM_TRANSFORMS_SCALAR_LOOPNESTPASSMANAGER_H diff --git a/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h b/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h --- a/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h +++ b/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h @@ -104,6 +104,7 @@ LoopStandardAnalysisResults &, LPMUpdater &>; template class FunctionToLoopPassAdaptor; +template class LoopNestToLoopPassAdaptor; /// This class provides an interface for updating the loop pass manager based /// on mutations to the loop nest. @@ -199,6 +200,7 @@ private: template friend class llvm::FunctionToLoopPassAdaptor; + template friend class llvm::LoopNestToLoopPassAdaptor; /// The \c FunctionToLoopPassAdaptor's worklist of loops to process. SmallPriorityWorklist &Worklist; @@ -220,6 +222,59 @@ : Worklist(Worklist), LAM(LAM) {} }; +// Collections of helper functions that are used by both loop pass manager and +// loop nest pass manager. +namespace detail { + +/// Helper function for preserving the standard analyses on loops. +inline void preserveLoopStandardAnalysisResults(PreservedAnalyses &PA, + bool UseMemorySSA) { + PA.preserve(); + PA.preserve(); + PA.preserve(); + if (UseMemorySSA) + PA.preserve(); +} + +/// Helper function for preserving AA category. +inline void preserveAACategory(PreservedAnalyses &PA) { + // FIXME: What we really want to do here is preserve an AA category, but + // that concept doesn't exist yet. + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); +} + +/// Helper function for getting the analysis results needed by loop and loop +/// nest passes. +inline LoopStandardAnalysisResults +getLoopStandardAnalysisResults(Function &F, FunctionAnalysisManager &AM, + bool UseMemorySSA) { + MemorySSA *MSSA = + UseMemorySSA ? (&AM.getResult(F).getMSSA()) : nullptr; + LoopStandardAnalysisResults LAR = {AM.getResult(F), + AM.getResult(F), + AM.getResult(F), + AM.getResult(F), + AM.getResult(F), + AM.getResult(F), + AM.getResult(F), + MSSA}; + return LAR; +} + +/// Helper function for constructing loop canonicalization passes for loop pass +/// manager and loop nest pass manager. +inline FunctionPassManager getLoopCanonicalizationPasses(bool DebugLogging) { + FunctionPassManager FPM(DebugLogging); + FPM.addPass(LoopSimplifyPass()); + FPM.addPass(LCSSAPass()); + return FPM; +} + +} // namespace detail + /// Adaptor that maps from a function to its loops. /// /// Designed to allow composition of a LoopPass(Manager) and a @@ -233,11 +288,10 @@ public: explicit FunctionToLoopPassAdaptor(LoopPassT Pass, bool UseMemorySSA = false, bool DebugLogging = false) - : Pass(std::move(Pass)), LoopCanonicalizationFPM(DebugLogging), - UseMemorySSA(UseMemorySSA) { - LoopCanonicalizationFPM.addPass(LoopSimplifyPass()); - LoopCanonicalizationFPM.addPass(LCSSAPass()); - } + : Pass(std::move(Pass)), + LoopCanonicalizationFPM( + detail::getLoopCanonicalizationPasses(DebugLogging)), + UseMemorySSA(UseMemorySSA) {} /// Runs the loop passes across every loop in the function. PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) { @@ -262,18 +316,9 @@ if (LI.empty()) return PA; - // Get the analysis results needed by loop passes. - MemorySSA *MSSA = UseMemorySSA - ? (&AM.getResult(F).getMSSA()) - : nullptr; - LoopStandardAnalysisResults LAR = {AM.getResult(F), - AM.getResult(F), - AM.getResult(F), - AM.getResult(F), - AM.getResult(F), - AM.getResult(F), - AM.getResult(F), - MSSA}; + // Get the analysis results needed by loop nest passes. + LoopStandardAnalysisResults LAR = + detail::getLoopStandardAnalysisResults(F, AM, UseMemorySSA); // Setup the loop analysis manager from its proxy. It is important that // this is only done when there are loops to process and we have built the @@ -352,17 +397,8 @@ PA.preserveSet>(); PA.preserve(); // We also preserve the set of standard analyses. - PA.preserve(); - PA.preserve(); - PA.preserve(); - if (UseMemorySSA) - PA.preserve(); - // FIXME: What we really want to do here is preserve an AA category, but - // that concept doesn't exist yet. - PA.preserve(); - PA.preserve(); - PA.preserve(); - PA.preserve(); + detail::preserveLoopStandardAnalysisResults(PA, UseMemorySSA); + detail::preserveAACategory(PA); return PA; } diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h --- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -432,6 +432,12 @@ /// FIXME: Consider changing the order in LoopInfo. void appendLoopsToWorklist(LoopInfo &, SmallPriorityWorklist &); +/// Utility that implements appending of all loops in a loop nest (rooted at \p +/// Root) onto a worklist. Since appendLoopsToWorklist(Loop &) only pushes +/// subloops, the root loop will be pushed into the worklist first in this +/// function. +void appendLoopNestToWorklist(Loop &Root, SmallPriorityWorklist &); + /// Recursively clone the specified loop and all of its children, /// mapping the blocks with the specified map. Loop *cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -75,6 +75,7 @@ LoopAnalysisManager.cpp LoopCacheAnalysis.cpp LoopNestAnalysis.cpp + LoopNestAnalysisManager.cpp LoopUnrollAnalyzer.cpp LoopInfo.cpp LoopPass.cpp diff --git a/llvm/lib/Analysis/LoopNestAnalysis.cpp b/llvm/lib/Analysis/LoopNestAnalysis.cpp --- a/llvm/lib/Analysis/LoopNestAnalysis.cpp +++ b/llvm/lib/Analysis/LoopNestAnalysis.cpp @@ -206,6 +206,15 @@ return CurrentDepth; } +void LoopNest::reconstructInplace(ScalarEvolution &SE) { + assert(!Loops.empty() && "Loop nest should contain the root loop."); + Loop *Root = Loops[0]; + MaxPerfectDepth = getMaxPerfectDepth(*Root, SE); + Loops.clear(); + for (Loop *L : breadth_first(Root)) + Loops.push_back(L); +} + static bool checkLoopsStructure(const Loop &OuterLoop, const Loop &InnerLoop, ScalarEvolution &SE) { // The inner loop must be the only outer loop's child. @@ -282,6 +291,13 @@ return OS; } +AnalysisKey LoopNestAnalysis::Key; + +LoopNest LoopNestAnalysis::run(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR) { + return LoopNest(L, AR.SE); +} + //===----------------------------------------------------------------------===// // LoopNestPrinterPass implementation // diff --git a/llvm/lib/Analysis/LoopNestAnalysisManager.cpp b/llvm/lib/Analysis/LoopNestAnalysisManager.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Analysis/LoopNestAnalysisManager.cpp @@ -0,0 +1,143 @@ +//===- LoopNestAnalysisManager.cpp - LoopNest analysis management ---------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/LoopNestAnalysisManager.h" +#include "llvm/Analysis/BasicAliasAnalysis.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/MemorySSA.h" +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/PassManagerImpl.h" + +using namespace llvm; + +namespace llvm { + +template class AnalysisManager; +template class InnerAnalysisManagerProxy; +template class InnerAnalysisManagerProxy; +template class OuterAnalysisManagerProxy; + +bool LoopNestAnalysisManagerFunctionProxy::Result::invalidate( + Function &F, const PreservedAnalyses &PA, + FunctionAnalysisManager::Invalidator &Inv) { + // If literally everything is preserved, we're done. + if (PA.areAllPreserved()) + return false; // This is still a valid proxy. + + std::vector TopLevelLoops = LI->getTopLevelLoops(); + SmallVector PreOrderLoops = LI->getLoopsInReverseSiblingPreorder(); + + auto PAC = PA.getChecker(); + bool InvalidateMemorySSAAnalysis = false; + if (MSSAUsed) + InvalidateMemorySSAAnalysis = Inv.invalidate(F, PA); + if (!(PAC.preserved() || PAC.preservedSet>()) || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA) || + Inv.invalidate(F, PA) || + InvalidateMemorySSAAnalysis) { + // Note that the LoopInfo may be stale at this point, however the loop + // objects themselves remain the only viable keys that could be in the + // analysis manager's cache. So we just walk the keys and forcibly clear + // those results. Note that the order doesn't matter here as this will + // just directly destroy the results without calling methods on them. + // + // Though we're dealing with loop nests here, the analysis results can + // still be cleared via the root loops. + // + // Note that not only do we invalidate loop nest analyses on the root + // loops, the loop anlayses on the subloops should also be cleared because + // they depend on the standard analysis results as well. + dbgs() << "OK" << "\n"; + for (Loop *L : PreOrderLoops) + InnerAM->clear(*L, ""); + InnerAM = nullptr; + return true; + } + + // Directly check if the relevant set is preserved. + bool AreLoopNestAnalysesPreserved = + PA.allAnalysesInSetPreserved>(); + + // getTopLevelLoops() returns loops in "reversed" order. Reverse the list + // again for correctness. + for (Loop *L : reverse(TopLevelLoops)) { + Optional LoopNestPA; + + // Check to see whether the preserved set needs to be pruned based on + // function-level analysis invalidation that triggers deferred invalidation + // registered with the outer analysis manager proxy for this loop nest. + if (auto *OuterProxy = + InnerAM->getCachedResult( + *L)) { + for (const auto &OuterInvalidationPair : + OuterProxy->getOuterInvalidations()) { + AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first; + const auto &InnerAnalysisIDs = OuterInvalidationPair.second; + if (Inv.invalidate(OuterAnalysisID, F, PA)) { + if (!LoopNestPA) + LoopNestPA = PA; + for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs) + LoopNestPA->abandon(InnerAnalysisID); + } + } + } + + // Check if we needed a custom PA set, and if so we'll need to run the + // inner invalidation. + if (LoopNestPA) { + InnerAM->invalidate(*L, *LoopNestPA); + continue; + } + + // Otherwise we only need to do invalidation if the original PA set didn't + // preserve all loop nest analyses. + if (!AreLoopNestAnalysesPreserved) + InnerAM->invalidate(*L, PA); + } + + // Return false to indicate that this result is still a valid proxy. + return false; +} + +void LoopNestAnalysisManager::invalidateSubLoopAnalyses( + Loop &Root, const PreservedAnalyses &PA) { + // We can return immediately if all the loop analyses are preserved. + if (PA.areAllPreserved() || + PA.allAnalysesInSetPreserved>()) + return; + + // Collect the loops in the subtree in post-order by performing DFS without + // recursion using a stack. + SmallVector Stack(Root.begin(), Root.end()), SubLoops; + while (!Stack.empty()) { + Loop *L = Stack.pop_back_val(); + SubLoops.push_back(L); + Stack.append(L->begin(), L->end()); + } + + // Visit the loops in reversed post-order and invalidate them. + for (Loop *L : reverse(SubLoops)) { + InternalLAM.invalidate(*L, PA); + } +} + +template <> +LoopNestAnalysisManagerFunctionProxy::Result +LoopNestAnalysisManagerFunctionProxy::run(Function &F, + FunctionAnalysisManager &AM) { + return Result(*InnerAM, AM.getResult(F)); +} + +} // namespace llvm diff --git a/llvm/lib/LTO/LTOBackend.cpp b/llvm/lib/LTO/LTOBackend.cpp --- a/llvm/lib/LTO/LTOBackend.cpp +++ b/llvm/lib/LTO/LTOBackend.cpp @@ -16,6 +16,7 @@ #include "llvm/LTO/LTOBackend.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/LoopNestAnalysisManager.h" #include "llvm/Analysis/ModuleSummaryAnalysis.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" @@ -209,6 +210,7 @@ RegisterPassPlugins(Conf.PassPlugins, PB); LoopAnalysisManager LAM(Conf.DebugPassManager); + LoopNestAnalysisManager LNAM(LAM); FunctionAnalysisManager FAM(Conf.DebugPassManager); CGSCCAnalysisManager CGAM(Conf.DebugPassManager); ModuleAnalysisManager MAM(Conf.DebugPassManager); @@ -221,7 +223,8 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); ModulePassManager MPM(Conf.DebugPassManager); // FIXME (davide): verify the input. @@ -271,6 +274,7 @@ RegisterPassPlugins(Conf.PassPlugins, PB); LoopAnalysisManager LAM; + LoopNestAnalysisManager LNAM(LAM); FunctionAnalysisManager FAM; CGSCCAnalysisManager CGAM; ModuleAnalysisManager MAM; @@ -283,7 +287,8 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); ModulePassManager MPM; diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/lib/Passes/PassBuilder.cpp @@ -143,6 +143,7 @@ #include "llvm/Transforms/Scalar/LoopIdiomRecognize.h" #include "llvm/Transforms/Scalar/LoopInstSimplify.h" #include "llvm/Transforms/Scalar/LoopLoadElimination.h" +#include "llvm/Transforms/Scalar/LoopNestPassManager.h" #include "llvm/Transforms/Scalar/LoopPassManager.h" #include "llvm/Transforms/Scalar/LoopPredication.h" #include "llvm/Transforms/Scalar/LoopRotation.h" @@ -386,9 +387,32 @@ static StringRef name() { return "NoOpLoopAnalysis"; } }; +/// No-op loop nest pass which does nothing. +struct NoOpLoopNestPass : PassInfoMixin { + PreservedAnalyses run(LoopNest &LN, LoopNestAnalysisManager &, + LoopStandardAnalysisResults &, LNPMUpdater &) { + return PreservedAnalyses::all(); + } + static StringRef name() { return "NoOpLoopNestPass"; } +}; + +/// No-op loop nest analysis. +class NoOpLoopNestAnalysis : public AnalysisInfoMixin { + friend AnalysisInfoMixin; + static AnalysisKey Key; + +public: + struct Result {}; + Result run(Loop &, LoopAnalysisManager &, LoopStandardAnalysisResults &) { + return Result(); + } + static StringRef name() { return "NoOpLoopNestAnalysis"; } +}; + AnalysisKey NoOpModuleAnalysis::Key; AnalysisKey NoOpCGSCCAnalysis::Key; AnalysisKey NoOpFunctionAnalysis::Key; +AnalysisKey NoOpLoopNestAnalysis::Key; AnalysisKey NoOpLoopAnalysis::Key; } // namespace @@ -435,6 +459,15 @@ C(LAM); } +void PassBuilder::registerLoopNestAnalyses(LoopNestAnalysisManager &LNAM) { +#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS) \ + LNAM.registerPass([&] { return CREATE_PASS; }); +#include "PassRegistry.def" + + for (auto &C : LoopNestAnalysisRegistrationCallbacks) + C(LNAM); +} + // TODO: Investigate the cost/benefit of tail call elimination on debugging. FunctionPassManager PassBuilder::buildO1FunctionSimplificationPipeline( OptimizationLevel Level, ThinLTOPhase Phase, bool DebugLogging) { @@ -2006,6 +2039,30 @@ return callbacksAcceptPassName(Name, Callbacks); } +template +static bool isLoopNestPassName(StringRef Name, CallbacksT &Callbacks) { + // Explicitly handle pass manager names. + if (Name == "loop-nest" || Name == "loop-nest-mssa") + return true; + + // Explicitly handle custom-parsed pass names. + if (parseRepeatPassName(Name)) + return true; + +#define LOOP_NEST_PASS(NAME, CREATE_PASS) \ + if (Name == NAME) \ + return true; +#define LOOP_NEST_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER) \ + if (checkParametrizedPassName(Name, NAME)) \ + return true; +#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS) \ + if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">") \ + return true; +#include "PassRegistry.def" + + return callbacksAcceptPassName(Name, Callbacks); +} + template static bool isLoopPassName(StringRef Name, CallbacksT &Callbacks) { // Explicitly handle pass manager names. @@ -2398,6 +2455,22 @@ FPM.addPass(std::move(NestedFPM)); return Error::success(); } + if (Name == "loop-nest" || Name == "loop-nest-mssa") { + LoopNestPassManager LNPM(DebugLogging); + // Because the LoopStandardAnalysisResults can only be constructed at + // FunctionToLoopNestPassAdaptor but not at LoopNestToLoopPassAdaptor, + // UseMemorySSA should depends on the loop passes as well. + // Memory SSA is needed true if either the loop nest explicitly requires + // it or at least one of the loop passes wrapped inside the loop nest pass + // requires it. + bool UseMemorySSA = (Name == "loop-nest-mssa"); + if (auto Err = parseLoopNestPassPipeline( + LNPM, InnerPipeline, UseMemorySSA, VerifyEachPass, DebugLogging)) + return Err; + FPM.addPass(createFunctionToLoopNestPassAdaptor( + std::move(LNPM), UseMemorySSA, DebugLogging)); + return Error::success(); + } if (Name == "loop" || Name == "loop-mssa") { LoopPassManager LPM(DebugLogging); if (auto Err = parseLoopPassPipeline(LPM, InnerPipeline, VerifyEachPass, @@ -2473,6 +2546,21 @@ false, DebugLogging)); \ return Error::success(); \ } +#define LOOP_NEST_PASS(NAME, CREATE_PASS) \ + if (Name == NAME) { \ + FPM.addPass(createFunctionToLoopNestPassAdaptor(CREATE_PASS, false, \ + DebugLogging)); \ + return Error::success(); \ + } +#define LOOP_NEST_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER) \ + if (checkParametrizedPassName(Name, NAME)) { \ + auto Params = parsePassParameters(PARSER, Name, NAME); \ + if (!Params) \ + return Params.takeError(); \ + FPM.addPass(createFunctionToLoopNestPassAdaptor(CREATE_PASS(Params.get()), \ + false, DebugLogging)); \ + return Error::success(); \ + } #include "PassRegistry.def" for (auto &C : FunctionPipelineParsingCallbacks) @@ -2483,6 +2571,94 @@ inconvertibleErrorCode()); } +Error PassBuilder::parseLoopNestPass(LoopNestPassManager &LNPM, + const PipelineElement &E, + bool &UseMemorySSA, bool VerifyEachPass, + bool DebugLogging) { + StringRef Name = E.Name; + const auto &InnerPipeline = E.InnerPipeline; + + // First handle complex passes like the pass managers which carry pipelines. + if (!InnerPipeline.empty()) { + if (Name == "loop-nest") { + LoopNestPassManager NestedLNPM(DebugLogging); + if (auto Err = + parseLoopNestPassPipeline(NestedLNPM, InnerPipeline, UseMemorySSA, + VerifyEachPass, DebugLogging)) + return Err; + // Add the nested pass manager with the appropriate adaptor. + LNPM.addPass(std::move(NestedLNPM)); + return Error::success(); + } + // Loop passes can be wrapped in a loop nest pass via \c + // LoopNestToLoopPassAdaptor. + if (Name == "loop" || Name == "loop-mssa") { + LoopPassManager LPM(DebugLogging); + if (auto Err = parseLoopPassPipeline(LPM, InnerPipeline, VerifyEachPass, + DebugLogging)) + return Err; + // If the loop pass requires MemorySSA, the loop nest pass does as well. + UseMemorySSA |= (Name == "loop-mssa"); + LNPM.addPass(createLoopNestToLoopPassAdaptor(std::move(LPM))); + return Error::success(); + } + if (auto Count = parseRepeatPassName(Name)) { + LoopNestPassManager NestedLNPM(DebugLogging); + if (auto Err = + parseLoopNestPassPipeline(NestedLNPM, InnerPipeline, UseMemorySSA, + VerifyEachPass, DebugLogging)) + return Err; + LNPM.addPass(createRepeatedPass(*Count, std::move(NestedLNPM))); + return Error::success(); + } + + for (auto &C : LoopNestPipelineParsingCallbacks) + if (C(Name, LNPM, InnerPipeline)) + return Error::success(); + + // Normal passes can't have pipelines. + return make_error( + formatv("invalid use of '{0}' pass as loop pipeline", Name).str(), + inconvertibleErrorCode()); + } + +// Now expand the basic registered passes from the .inc file. +#define LOOP_NEST_PASS(NAME, CREATE_PASS) \ + if (Name == NAME) { \ + LNPM.addPass(CREATE_PASS); \ + return Error::success(); \ + } +#define LOOP_NEST_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER) \ + if (checkParametrizedPassName(Name, NAME)) { \ + auto Params = parsePassParameters(PARSER, Name, NAME); \ + if (!Params) \ + return Params.takeError(); \ + LNPM.addPass(CREATE_PASS(Params.get())); \ + return Error::success(); \ + } +#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS) \ + if (Name == "require<" NAME ">") { \ + LNPM.addPass(RequireAnalysisPass< \ + std::remove_reference::type, LoopNest, \ + LoopNestAnalysisManager, LoopStandardAnalysisResults &, \ + LNPMUpdater &>()); \ + return Error::success(); \ + } \ + if (Name == "invalidate<" NAME ">") { \ + LNPM.addPass(InvalidateAnalysisPass< \ + std::remove_reference::type>()); \ + return Error::success(); \ + } +#include "PassRegistry.def" + + for (auto &C : LoopNestPipelineParsingCallbacks) + if (C(Name, LNPM, InnerPipeline)) + return Error::success(); + return make_error( + formatv("unknown loop nest pass '{0}'", Name).str(), + inconvertibleErrorCode()); +} + Error PassBuilder::parseLoopPass(LoopPassManager &LPM, const PipelineElement &E, bool VerifyEachPass, bool DebugLogging) { StringRef Name = E.Name; @@ -2575,6 +2751,20 @@ return false; } +Error PassBuilder::parseLoopNestPassPipeline(LoopNestPassManager &LNPM, + ArrayRef Pipeline, + bool &UseMemorySSA, + bool VerifyEachPass, + bool DebugLogging) { + for (const auto &Element : Pipeline) { + if (auto Err = parseLoopNestPass(LNPM, Element, UseMemorySSA, + VerifyEachPass, DebugLogging)) + return Err; + // FIXME: No verifier support for LoopNest passes! + } + return Error::success(); +} + Error PassBuilder::parseLoopPassPipeline(LoopPassManager &LPM, ArrayRef Pipeline, bool VerifyEachPass, @@ -2614,6 +2804,7 @@ } void PassBuilder::crossRegisterProxies(LoopAnalysisManager &LAM, + LoopNestAnalysisManager &LNAM, FunctionAnalysisManager &FAM, CGSCCAnalysisManager &CGAM, ModuleAnalysisManager &MAM) { @@ -2622,6 +2813,8 @@ CGAM.registerPass([&] { return ModuleAnalysisManagerCGSCCProxy(MAM); }); FAM.registerPass([&] { return CGSCCAnalysisManagerFunctionProxy(CGAM); }); FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); }); + FAM.registerPass([&] { return LoopNestAnalysisManagerFunctionProxy(LNAM); }); + LNAM.registerPass([&] { return FunctionAnalysisManagerLoopNestProxy(FAM); }); FAM.registerPass([&] { return LoopAnalysisManagerFunctionProxy(LAM); }); LAM.registerPass([&] { return FunctionAnalysisManagerLoopProxy(FAM); }); } @@ -2661,6 +2854,9 @@ } else if (isFunctionPassName(FirstName, FunctionPipelineParsingCallbacks)) { Pipeline = {{"function", std::move(*Pipeline)}}; + } else if (isLoopNestPassName(FirstName, + LoopNestPipelineParsingCallbacks)) { + Pipeline = {{"function", {{"loop-nest", std::move(*Pipeline)}}}}; } else if (isLoopPassName(FirstName, LoopPipelineParsingCallbacks)) { Pipeline = {{"function", {{"loop", std::move(*Pipeline)}}}}; } else { @@ -2733,6 +2929,29 @@ return Error::success(); } +Error PassBuilder::parsePassPipeline(LoopNestPassManager &LNPM, + StringRef PipelineText, bool &UseMemorySSA, + bool VerifyEachPass, bool DebugLogging) { + auto Pipeline = parsePipelineText(PipelineText); + if (!Pipeline || Pipeline->empty()) + return make_error( + formatv("invalid pipeline '{0}'", PipelineText).str(), + inconvertibleErrorCode()); + + StringRef FirstName = Pipeline->front().Name; + if (!isLoopNestPassName(FirstName, LoopNestPipelineParsingCallbacks)) + return make_error( + formatv("unknown loop nest pass '{0}' in pipeline '{1}'", FirstName, + PipelineText) + .str(), + inconvertibleErrorCode()); + + if (auto Err = parseLoopNestPassPipeline(LNPM, *Pipeline, UseMemorySSA, + VerifyEachPass, DebugLogging)) + return Err; + return Error::success(); +} + // Primary pass pipeline description parsing routine for a \c LoopPassManager Error PassBuilder::parsePassPipeline(LoopPassManager &CGPM, StringRef PipelineText, @@ -2788,6 +3007,9 @@ #define LOOP_ANALYSIS(NAME, CREATE_PASS) \ if (PassName == NAME) \ return true; +#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS) \ + if (PassName == NAME) \ + return true; #define CGSSC_ANALYSIS(NAME, CREATE_PASS) \ if (PassName == NAME) \ return true; diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -321,6 +321,7 @@ LOOP_ANALYSIS("access-info", LoopAccessAnalysis()) LOOP_ANALYSIS("ddg", DDGAnalysis()) LOOP_ANALYSIS("iv-users", IVUsersAnalysis()) +LOOP_ANALYSIS("loop-nest", LoopNestAnalysis()) LOOP_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC)) #undef LOOP_ANALYSIS @@ -359,3 +360,22 @@ }, parseLoopUnswitchOptions) #undef LOOP_PASS_WITH_PARAMS + +#ifndef LOOP_NEST_ANALYSIS +#define LOOP_NEST_ANALYSIS(NAME, CREATE_PASS) +#endif +LOOP_NEST_ANALYSIS("no-op-loop-nest", NoOpLoopNestAnalysis()) +LOOP_NEST_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC)) +#undef LOOP_NEST_ANALYSIS + +#ifndef LOOP_NEST_PASS +#define LOOP_NEST_PASS(NAME, CREATE_PASS) +#endif +LOOP_NEST_PASS("no-op-loop-nest", NoOpLoopNestPass()) +LOOP_NEST_PASS("print", PrintLoopNestPass()) +#undef LOOP_NEST_PASS + +#ifndef LOOP_NEST_PASS_WITH_PARAMS +#define LOOP_NEST_PASS_WITH_PARAMS(NAME, CREATE_PASS) +#endif +#undef LOOP_NEST_PASS_WITH_PARAMS diff --git a/llvm/lib/Transforms/Scalar/CMakeLists.txt b/llvm/lib/Transforms/Scalar/CMakeLists.txt --- a/llvm/lib/Transforms/Scalar/CMakeLists.txt +++ b/llvm/lib/Transforms/Scalar/CMakeLists.txt @@ -33,6 +33,7 @@ LoopInstSimplify.cpp LoopInterchange.cpp LoopLoadElimination.cpp + LoopNestPassManager.cpp LoopPassManager.cpp LoopPredication.cpp LoopRerollPass.cpp diff --git a/llvm/lib/Transforms/Scalar/LoopNestPassManager.cpp b/llvm/lib/Transforms/Scalar/LoopNestPassManager.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/Scalar/LoopNestPassManager.cpp @@ -0,0 +1,107 @@ +//===- LoopNestPassManager.cpp - Loop nest pass management ----------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar/LoopNestPassManager.h" + +namespace llvm { + +template <> +PreservedAnalyses +PassManager::run(LoopNest &LN, LoopNestAnalysisManager &AM, + LoopStandardAnalysisResults &AR, + LNPMUpdater &U) { + PreservedAnalyses PA = PreservedAnalyses::all(); + + // Request PassInstrumentation from analysis manager, will use it to run + // instrumenting callbacks for the passes later. + PassInstrumentation PI = AM.getResult(LN, AR); + + if (DebugLogging) + dbgs() << "Starting LoopNest pass manager run.\n"; + + for (unsigned I = 0, E = Passes.size(); I != E; ++I) { + auto *Pass = Passes[I].get(); + + // Check the PassInstrumentation's BeforePass callbacks before running the + // pass, skip its execution completely if asked to (callback returns + // false). + if (!PI.runBeforePass(*Pass, LN)) + continue; + + PreservedAnalyses PassPA; + { + TimeTraceScope TimeScope(Pass->name(), LN.getName()); + PassPA = Pass->run(LN, AM, AR, U); + } + + // Do not pass deleted LoopNest into the instrumentation + if (U.skipCurrentLoopNest()) + PI.runAfterPassInvalidated(*Pass); + else + PI.runAfterPass(*Pass, LN); + + if (U.skipCurrentLoopNest()) { + PA.intersect(std::move(PassPA)); + break; + } + + // We shouldn't allow invalidating LoopNestAnalysis in AM since otherwise + // LN will be dangling. Currently the loop nest passes cannot explicitly + // update the LoopNest structure, so we must first check whether + // LoopNestAnalysis is preserved, and mark it as preserved + // regardlessly afterward. If the analysis is not preserved in the first + // place, we would have to manually reconstruct the LoopNest. + // FIXME: This is quite inefficient. Consider reimplementing LoopNest to + // allow dynamic modifications by the loop nest passes to avoid + // reconstructing it every time. + bool IsLoopNestPreserved = + PassPA.getChecker().preserved(); + + // No need to invalidate other loop nest analyses since they are running on + // Loop and hence can be updated dynamically. + PassPA.preserve(); + AM.invalidate(LN, PassPA); + + if (!IsLoopNestPreserved) + // The LoopNest structure had been altered, reconstruct it here. + LN.reconstructInplace(AR.SE); + PA.intersect(std::move(PassPA)); + } + + // Invalidation for the current loop nest should be handled above, and other + // loop nest analysis results shouldn't be impacted by runs over this loop + // nest. Therefore, the remaining analysis results in the AnalysisManager are + // preserved. We mark this with a set so that we don't need to inspect each + // one individually. + PA.preserveSet>(); + // All analyses on Loops are preserved as well. + PA.preserveSet>(); + + if (DebugLogging) + dbgs() << "Finished LoopNest pass manager run.\n"; + + return PA; +} + +template class PassManager; + +PrintLoopNestPass::PrintLoopNestPass() : OS(dbgs()) {} +PrintLoopNestPass::PrintLoopNestPass(raw_ostream &OS, const std::string &Banner) + : OS(OS), Banner(Banner) {} + +PreservedAnalyses PrintLoopNestPass::run(LoopNest &LN, + LoopNestAnalysisManager &, + LoopStandardAnalysisResults &, + LNPMUpdater &) { + OS << LN << "\n"; + return PreservedAnalyses::all(); +} + +} // namespace llvm diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp --- a/llvm/lib/Transforms/Utils/LoopUtils.cpp +++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -1537,6 +1537,12 @@ appendReversedLoopsToWorklist(LI, Worklist); } +void llvm::appendLoopNestToWorklist( + Loop &Root, SmallPriorityWorklist &Worklist) { + Worklist.insert(&Root); + appendLoopsToWorklist(Root, Worklist); +} + Loop *llvm::cloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM) { Loop &New = *LI->AllocateLoop(); diff --git a/llvm/test/Transforms/LICM/assume.ll b/llvm/test/Transforms/LICM/assume.ll --- a/llvm/test/Transforms/LICM/assume.ll +++ b/llvm/test/Transforms/LICM/assume.ll @@ -1,5 +1,6 @@ ; RUN: opt -licm -basic-aa < %s -S | FileCheck %s ; RUN: opt -aa-pipeline=basic-aa -passes='require,require,require,require,loop(licm)' < %s -S | FileCheck %s +; RUN: opt -aa-pipeline=basic-aa -passes='require,require,require,require,loop-nest(loop(licm))' < %s -S | FileCheck %s define void @f_0(i1 %p) nounwind ssp { ; CHECK-LABEL: @f_0( diff --git a/llvm/test/Transforms/LoopDeletion/invalidation.ll b/llvm/test/Transforms/LoopDeletion/invalidation.ll --- a/llvm/test/Transforms/LoopDeletion/invalidation.ll +++ b/llvm/test/Transforms/LoopDeletion/invalidation.ll @@ -4,8 +4,12 @@ ; ; RUN: opt < %s -passes='require,no-op-loop,require' -S \ ; RUN: | FileCheck %s --check-prefixes=CHECK,BEFORE +; RUN: opt < %s -passes='loop-nest(loop(require,no-op-loop,require))' -S \ +; RUN: | FileCheck %s --check-prefixes=CHECK,BEFORE ; RUN: opt < %s -passes='require,loop-deletion,require' -S \ ; RUN: | FileCheck %s --check-prefixes=CHECK,AFTER +; RUN: opt < %s -passes='loop-nest(loop(require,loop-deletion,require))' -S \ +; RUN: | FileCheck %s --check-prefixes=CHECK,AFTER define void @foo(i64 %n, i64 %m) nounwind { diff --git a/llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll b/llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll --- a/llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll +++ b/llvm/test/Transforms/LoopDeletion/multiple-exit-conditions.ll @@ -1,5 +1,6 @@ ; RUN: opt < %s -loop-deletion -S | FileCheck %s ; RUN: opt < %s -passes='loop(loop-deletion)' -S | FileCheck %s +; RUN: opt < %s -passes='loop-nest(loop(loop-deletion))' -S | FileCheck %s ; ScalarEvolution can prove the loop iteration is finite, even though ; it can't represent the exact trip count as an expression. That's diff --git a/llvm/test/Transforms/LoopNest/print.ll b/llvm/test/Transforms/LoopNest/print.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LoopNest/print.ll @@ -0,0 +1,84 @@ +; RUN: opt -S -passes='loop-nest(print)' < %s 2>&1 >/dev/null | FileCheck %s + +; CHECK: IsPerfect=true, Depth=1, OutermostLoop: for.cond, Loops: ( for.cond ) +define i32 @f1(i32 %n) #0 { +entry: + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %res.0 = phi i32 [ 0, %entry ], [ %add, %for.inc ] + %i.0 = phi i32 [ 0, %entry ], [ %inc, %for.inc ] + %cmp = icmp slt i32 %i.0, %n + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %add = add nsw i32 %res.0, %i.0 + br label %for.inc + +for.inc: ; preds = %for.body + %inc = add nsw i32 %i.0, 1 + br label %for.cond + +for.end: ; preds = %for.cond + %res.0.lcssa = phi i32 [ %res.0, %for.cond ] + ret i32 %res.0.lcssa +} + +; CHECH: IsPerfect=false, Depth=2, OutermostLoop: for.cond, Loops: ( for.cond for.cond1 for.cond5 ) +define i32 @f4(i32 %n) #0 { +entry: + br label %for.cond + +for.cond: ; preds = %for.inc12, %entry + %i.0 = phi i32 [ 0, %entry ], [ %inc13, %for.inc12 ] + %res.0 = phi i32 [ 0, %entry ], [ %res.2.lcssa, %for.inc12 ] + %cmp = icmp slt i32 %i.0, %n + br i1 %cmp, label %for.body, label %for.end14 + +for.body: ; preds = %for.cond + br label %for.cond1 + +for.cond1: ; preds = %for.inc, %for.body + %j.0 = phi i32 [ 0, %for.body ], [ %inc, %for.inc ] + %res.1 = phi i32 [ %res.0, %for.body ], [ %add, %for.inc ] + %cmp2 = icmp slt i32 %j.0, %n + br i1 %cmp2, label %for.body3, label %for.end + +for.body3: ; preds = %for.cond1 + %add = add nsw i32 %res.1, %i.0 + br label %for.inc + +for.inc: ; preds = %for.body3 + %inc = add nsw i32 %j.0, 1 + br label %for.cond1 + +for.end: ; preds = %for.cond1 + %res.1.lcssa = phi i32 [ %res.1, %for.cond1 ] + br label %for.cond5 + +for.cond5: ; preds = %for.inc9, %for.end + %res.2 = phi i32 [ %res.1.lcssa, %for.end ], [ %add8, %for.inc9 ] + %j4.0 = phi i32 [ 0, %for.end ], [ %inc10, %for.inc9 ] + %cmp6 = icmp slt i32 %j4.0, %n + br i1 %cmp6, label %for.body7, label %for.end11 + +for.body7: ; preds = %for.cond5 + %add8 = add nsw i32 %res.2, %j4.0 + br label %for.inc9 + +for.inc9: ; preds = %for.body7 + %inc10 = add nsw i32 %j4.0, 1 + br label %for.cond5 + +for.end11: ; preds = %for.cond5 + %res.2.lcssa = phi i32 [ %res.2, %for.cond5 ] + br label %for.inc12 + +for.inc12: ; preds = %for.end11 + %inc13 = add nsw i32 %i.0, 1 + br label %for.cond + +for.end14: ; preds = %for.cond + %res.0.lcssa = phi i32 [ %res.0, %for.cond ] + ret i32 %res.0.lcssa +} diff --git a/llvm/test/Transforms/LoopRotate/basic.ll b/llvm/test/Transforms/LoopRotate/basic.ll --- a/llvm/test/Transforms/LoopRotate/basic.ll +++ b/llvm/test/Transforms/LoopRotate/basic.ll @@ -2,6 +2,8 @@ ; RUN: opt -S -loop-rotate -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s ; RUN: opt -S -passes='require,require,loop(rotate)' < %s | FileCheck %s ; RUN: opt -S -passes='require,require,loop-mssa(rotate)' -verify-memoryssa < %s | FileCheck %s +; RUN: opt -S -passes='require,require,loop-nest(loop(rotate))' < %s | FileCheck %s +; RUN: opt -S -passes='require,require,loop-nest(loop-mssa(rotate))' -verify-memoryssa < %s | FileCheck %s target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" target triple = "x86_64-apple-darwin10.0.0" diff --git a/llvm/test/Transforms/LoopRotate/freeze-crash.ll b/llvm/test/Transforms/LoopRotate/freeze-crash.ll --- a/llvm/test/Transforms/LoopRotate/freeze-crash.ll +++ b/llvm/test/Transforms/LoopRotate/freeze-crash.ll @@ -1,5 +1,6 @@ ; RUN: opt -loop-rotate -disable-output %s ; RUN: opt -passes=rotate -disable-output %s +; RUN: opt -passes='loop-nest(loop(rotate))' -disable-output %s ; Make sure we don't crash on this test. define void @foo(i32* %arg) { diff --git a/llvm/test/Transforms/LoopRotate/multiple-deopt-exits.ll b/llvm/test/Transforms/LoopRotate/multiple-deopt-exits.ll --- a/llvm/test/Transforms/LoopRotate/multiple-deopt-exits.ll +++ b/llvm/test/Transforms/LoopRotate/multiple-deopt-exits.ll @@ -1,6 +1,7 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -S < %s -loop-rotate -loop-rotate-multi=true | FileCheck %s ; RUN: opt -S < %s -passes='loop(rotate)' -loop-rotate-multi=true | FileCheck %s +; RUN: opt -S < %s -passes='loop-nest(loop(rotate))' -loop-rotate-multi=true | FileCheck %s ; Test loop rotation with multiple exits, some of them - deoptimizing. ; We should end up with a latch which exit is non-deoptimizing, so we should rotate diff --git a/llvm/test/Transforms/LoopRotate/pr35210.ll b/llvm/test/Transforms/LoopRotate/pr35210.ll --- a/llvm/test/Transforms/LoopRotate/pr35210.ll +++ b/llvm/test/Transforms/LoopRotate/pr35210.ll @@ -1,5 +1,7 @@ ;RUN: opt %s -passes='adce,loop(rotate),adce' -S -debug-pass-manager -debug-only=loop-rotate 2>&1 | FileCheck %s ;RUN: opt %s -passes='adce,loop-mssa(rotate),adce' -S -debug-pass-manager -debug-only=loop-rotate -verify-memoryssa 2>&1 | FileCheck %s --check-prefix=MSSA +;RUN: opt %s -passes='adce,loop-nest(loop(rotate)),adce' -S -debug-pass-manager -debug-only=loop-rotate 2>&1 | FileCheck %s --check-prefix=LN +;RUN: opt %s -passes='adce,loop-nest-mssa(loop-mssa(rotate)),adce' -S -debug-pass-manager -debug-only=loop-rotate -verify-memoryssa 2>&1 | FileCheck %s --check-prefix=LNMSSA ;REQUIRES: asserts ; This test is to make sure we invalidate the post dominator pass after loop rotate simplifies the loop latch. @@ -29,6 +31,34 @@ ; CHECK-NEXT: Running analysis: PostDominatorTreeAnalysis on f ; CHECK-NEXT: Finished llvm::Function pass manager run. +; LN: Starting llvm::Function pass manager run. +; LN-NEXT: Running pass: ADCEPass on f +; LN-NEXT: Running analysis: PostDominatorTreeAnalysis on f +; LN-NEXT: Starting llvm::Function pass manager run. +; LN-NEXT: Running pass: LoopSimplifyPass on f +; LN-NEXT: Running analysis: LoopAnalysis on f +; LN-NEXT: Running analysis: DominatorTreeAnalysis on f +; LN-NEXT: Running analysis: AssumptionAnalysis on f +; LN-NEXT: Running pass: LCSSAPass on f +; LN-NEXT: Finished llvm::Function pass manager run. +; LN-NEXT: Running analysis: AAManager on f +; LN-NEXT: Running analysis: TargetLibraryAnalysis on f +; LN-NEXT: Running analysis: ScalarEvolutionAnalysis on f +; LN-NEXT: Running analysis: TargetIRAnalysis on f +; LN-NEXT: Running analysis: InnerAnalysisManagerProxy{{.*}} on f +; LN-NEXT: Running analysis: LoopNestAnalysis on Loop at depth 1 containing: %bb
,%bb4 +; LN-NEXT: Starting LoopNest pass manager run. +; LN-NEXT: Starting Loop pass manager run. +; LN-NEXT: Running pass: LoopRotatePass on Loop at depth 1 containing: %bb
,%bb4 +; LN-NEXT: Folding loop latch bb4 into bb +; LN-NEXT: Invalidating analysis: LoopNestAnalysis on bb +; LN-NEXT: Finished Loop pass manager run. +; LN-NEXT: Finished LoopNest pass manager run. +; LN-NEXT: Invalidating analysis: PostDominatorTreeAnalysis on f +; LN-NEXT: Running pass: ADCEPass on f +; LN-NEXT: Running analysis: PostDominatorTreeAnalysis on f +; LN-NEXT: Finished llvm::Function pass manager run. + ; MSSA: Starting llvm::Function pass manager run. ; MSSA-NEXT: Running pass: ADCEPass on f ; MSSA-NEXT: Running analysis: PostDominatorTreeAnalysis on f @@ -54,6 +84,35 @@ ; MSSA-NEXT: Running analysis: PostDominatorTreeAnalysis on f ; MSSA-NEXT: Finished llvm::Function pass manager run. +; LNMSSA: Starting llvm::Function pass manager run. +; LNMSSA-NEXT: Running pass: ADCEPass on f +; LNMSSA-NEXT: Running analysis: PostDominatorTreeAnalysis on f +; LNMSSA-NEXT: Starting llvm::Function pass manager run. +; LNMSSA-NEXT: Running pass: LoopSimplifyPass on f +; LNMSSA-NEXT: Running analysis: LoopAnalysis on f +; LNMSSA-NEXT: Running analysis: DominatorTreeAnalysis on f +; LNMSSA-NEXT: Running analysis: AssumptionAnalysis on f +; LNMSSA-NEXT: Running pass: LCSSAPass on f +; LNMSSA-NEXT: Finished llvm::Function pass manager run. +; LNMSSA-NEXT: Running analysis: MemorySSAAnalysis on f +; LNMSSA-NEXT: Running analysis: AAManager on f +; LNMSSA-NEXT: Running analysis: TargetLibraryAnalysis on f +; LNMSSA-NEXT: Running analysis: ScalarEvolutionAnalysis on f +; LNMSSA-NEXT: Running analysis: TargetIRAnalysis on f +; LNMSSA-NEXT: Running analysis: InnerAnalysisManagerProxy{{.*}} on f +; LNMSSA-NEXT: Running analysis: LoopNestAnalysis on Loop at depth 1 containing: %bb
,%bb4 +; LNMSSA-NEXT: Starting LoopNest pass manager run. +; LNMSSA-NEXT: Starting Loop pass manager run. +; LNMSSA-NEXT: Running pass: LoopRotatePass on Loop at depth 1 containing: %bb
,%bb4 +; LNMSSA-NEXT: Folding loop latch bb4 into bb +; LNMSSA-NEXT: Invalidating analysis: LoopNestAnalysis on bb +; LNMSSA-NEXT: Finished Loop pass manager run. +; LNMSSA-NEXT: Finished LoopNest pass manager run. +; LNMSSA-NEXT: Invalidating analysis: PostDominatorTreeAnalysis on f +; LNMSSA-NEXT: Running pass: ADCEPass on f +; LNMSSA-NEXT: Running analysis: PostDominatorTreeAnalysis on f +; LNMSSA-NEXT: Finished llvm::Function pass manager run. + ; CHECK-LABEL: define i8 @f() { ; CHECK-NEXT: entry: ; CHECK-NEXT: br label %bb @@ -70,6 +129,22 @@ ; CHECK: declare void @raise_exception() #0 ; CHECK: attributes #0 = { noreturn } +; LN-LABEL: define i8 @f() { +; LN-NEXT: entry: +; LN-NEXT: br label %bb +; LN: bb: ; preds = %bb, %entry +; LN-NEXT: %mode.0 = phi i8 [ 0, %entry ], [ %indvar.next, %bb ] +; LN-NEXT: %tmp5 = icmp eq i8 %mode.0, 1 +; LN-NEXT: %indvar.next = add i8 %mode.0, 1 +; LN-NEXT: br i1 %tmp5, label %bb5, label %bb +; LN: bb5: ; preds = %bb +; LN-NEXT: tail call void @raise_exception() #0 +; LN-NEXT: unreachable +; LN-NEXT: } +; LN: ; Function Attrs: noreturn +; LN: declare void @raise_exception() #0 +; LN: attributes #0 = { noreturn } + ; MSSA-LABEL: define i8 @f() { ; MSSA-NEXT: entry: ; MSSA-NEXT: br label %bb @@ -86,6 +161,22 @@ ; MSSA: declare void @raise_exception() #0 ; MSSA: attributes #0 = { noreturn } +; LNMSSA-LABEL: define i8 @f() { +; LNMSSA-NEXT: entry: +; LNMSSA-NEXT: br label %bb +; LNMSSA: bb: ; preds = %bb, %entry +; LNMSSA-NEXT: %mode.0 = phi i8 [ 0, %entry ], [ %indvar.next, %bb ] +; LNMSSA-NEXT: %tmp5 = icmp eq i8 %mode.0, 1 +; LNMSSA-NEXT: %indvar.next = add i8 %mode.0, 1 +; LNMSSA-NEXT: br i1 %tmp5, label %bb5, label %bb +; LNMSSA: bb5: ; preds = %bb +; LNMSSA-NEXT: tail call void @raise_exception() #0 +; LNMSSA-NEXT: unreachable +; LNMSSA-NEXT: } +; LNMSSA: ; Function Attrs: noreturn +; LNMSSA: declare void @raise_exception() #0 +; LNMSSA: attributes #0 = { noreturn } + define i8 @f() { entry: br label %bb diff --git a/llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp b/llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp --- a/llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp +++ b/llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp @@ -136,6 +136,7 @@ PassBuilder PB(TM.get()); LoopAnalysisManager LAM; + LoopNestAnalysisManager LNAM(LAM); FunctionAnalysisManager FAM; CGSCCAnalysisManager CGAM; ModulePassManager MPM; @@ -146,7 +147,8 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); auto Err = PB.parsePassPipeline(MPM, PassPipeline, false, false); assert(!Err && "Should have been checked during fuzzer initialization"); diff --git a/llvm/tools/opt/NewPMDriver.cpp b/llvm/tools/opt/NewPMDriver.cpp --- a/llvm/tools/opt/NewPMDriver.cpp +++ b/llvm/tools/opt/NewPMDriver.cpp @@ -18,6 +18,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/LoopNestAnalysisManager.h" #include "llvm/Bitcode/BitcodeWriterPass.h" #include "llvm/Config/llvm-config.h" #include "llvm/IR/Dominators.h" @@ -348,6 +349,7 @@ } LoopAnalysisManager LAM(DebugPM); + LoopNestAnalysisManager LNAM(LAM); FunctionAnalysisManager FAM(DebugPM); CGSCCAnalysisManager CGAM(DebugPM); ModuleAnalysisManager MAM(DebugPM); @@ -360,7 +362,8 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); ModulePassManager MPM(DebugPM); if (VK > VK_NoVerifier) diff --git a/llvm/unittests/IR/PassBuilderCallbacksTest.cpp b/llvm/unittests/IR/PassBuilderCallbacksTest.cpp --- a/llvm/unittests/IR/PassBuilderCallbacksTest.cpp +++ b/llvm/unittests/IR/PassBuilderCallbacksTest.cpp @@ -174,6 +174,24 @@ MockPassHandle() { setDefaults(); } }; +template <> +struct MockPassHandle + : MockPassHandleBase, LoopNest, + LoopNestAnalysisManager, LoopStandardAnalysisResults &, + LNPMUpdater &> { + MOCK_METHOD4(run, + PreservedAnalyses(LoopNest &, LoopNestAnalysisManager &, + LoopStandardAnalysisResults &, LNPMUpdater &)); + + static void invalidateLoopNest(LoopNest &LN, LoopNestAnalysisManager &, + LoopStandardAnalysisResults &, + LNPMUpdater &Updater) { + Updater.markLoopNestAsDeleted(LN, LN.getName()); + } + + MockPassHandle() { setDefaults(); } +}; + template <> struct MockPassHandle : MockPassHandleBase, Function> { @@ -226,6 +244,20 @@ MockAnalysisHandle() { this->setDefaults(); } }; +template <> +struct MockAnalysisHandle + : MockAnalysisHandleBase, Loop, + LoopAnalysisManager, + LoopStandardAnalysisResults &> { + MOCK_METHOD3_T(run, typename Analysis::Result(Loop &, LoopAnalysisManager &, + LoopStandardAnalysisResults &)); + + MOCK_METHOD3_T(invalidate, bool(Loop &, const PreservedAnalyses &, + LoopAnalysisManager::Invalidator &)); + + MockAnalysisHandle() { this->setDefaults(); } +}; + template <> struct MockAnalysisHandle : MockAnalysisHandleBase, Function> { @@ -282,6 +314,8 @@ return any_cast(WrappedIR)->getName().str(); if (any_isa(WrappedIR)) return any_cast(WrappedIR)->getName().str(); + if (any_isa(WrappedIR)) + return any_cast(WrappedIR)->getName().str(); if (any_isa(WrappedIR)) return any_cast(WrappedIR)->getName().str(); if (any_isa(WrappedIR)) @@ -395,6 +429,7 @@ PassBuilder PB; ModulePassManager PM; LoopAnalysisManager LAM; + LoopNestAnalysisManager LNAM; FunctionAnalysisManager FAM; CGSCCAnalysisManager CGAM; ModuleAnalysisManager AM; @@ -426,7 +461,7 @@ "}\n")), CallbacksHandle(), PB(nullptr, PipelineTuningOptions(), None, &CallbacksHandle.Callbacks), - PM(true), LAM(true), FAM(true), CGAM(true), AM(true) { + PM(true), LAM(true), LNAM(LAM), FAM(true), CGAM(true), AM(true) { EXPECT_TRUE(&CallbacksHandle.Callbacks == PB.getPassInstrumentationCallbacks()); @@ -469,13 +504,15 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, AM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, AM); } }; using ModuleCallbacksTest = PassBuilderCallbacksTest; using CGSCCCallbacksTest = PassBuilderCallbacksTest; using FunctionCallbacksTest = PassBuilderCallbacksTest; +using LoopNestCallbacksTest = PassBuilderCallbacksTest; using LoopCallbacksTest = PassBuilderCallbacksTest; /// Test parsing of the name of our mock pass for all IRUnits. @@ -731,6 +768,144 @@ PM.run(*M, AM); } +TEST_F(LoopNestCallbacksTest, Passes) { + EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _)); + EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _)) + .WillOnce(WithArgs<0, 1, 2>(Invoke(getAnalysisResult))); + StringRef PipelineText = "test-transform"; + ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded()) + << "Pipeline was: " << PipelineText; + PM.run(*M, AM); +} + +TEST_F(LoopNestCallbacksTest, InstrumentedPasses) { + CallbacksHandle.registerPassInstrumentation(); + // Non-mock instrumentation not specifically mentioned below can be ignored. + CallbacksHandle.ignoreNonMockPassInstrumentation(""); + CallbacksHandle.ignoreNonMockPassInstrumentation("foo"); + CallbacksHandle.ignoreNonMockPassInstrumentation("loop"); + + EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _)); + EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _)) + .WillOnce(WithArgs<0, 1, 2>(Invoke(getAnalysisResult))); + + // PassInstrumentation calls should happen in-sequence, in the same order + // as passes/analyses are scheduled. + ::testing::Sequence PISequence; + EXPECT_CALL(CallbacksHandle, + runBeforePass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL( + CallbacksHandle, + runBeforeNonSkippedPass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL( + CallbacksHandle, + runBeforeAnalysis(HasNameRegex("MockAnalysisHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL( + CallbacksHandle, + runAfterAnalysis(HasNameRegex("MockAnalysisHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL(CallbacksHandle, + runAfterPass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .InSequence(PISequence); + + // Our mock pass does not invalidate IR. + EXPECT_CALL(CallbacksHandle, + runAfterPassInvalidated(HasNameRegex("MockPassHandle"))) + .Times(0); + + StringRef PipelineText = "test-transform"; + ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded()) + << "Pipeline was: " << PipelineText; + PM.run(*M, AM); +} + +TEST_F(LoopNestCallbacksTest, InstrumentedInvalidatingPasses) { + CallbacksHandle.registerPassInstrumentation(); + // Non-mock instrumentation not specifically mentioned below can be ignored. + CallbacksHandle.ignoreNonMockPassInstrumentation(""); + CallbacksHandle.ignoreNonMockPassInstrumentation("foo"); + CallbacksHandle.ignoreNonMockPassInstrumentation("loop"); + + EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _)); + EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _)) + .WillOnce( + DoAll(WithArgs<0, 1, 2, 3>(Invoke(PassHandle.invalidateLoopNest)), + WithArgs<0, 1, 2>(Invoke(getAnalysisResult)))); + + // PassInstrumentation calls should happen in-sequence, in the same order + // as passes/analyses are scheduled. + ::testing::Sequence PISequence; + EXPECT_CALL(CallbacksHandle, + runBeforePass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL( + CallbacksHandle, + runBeforeNonSkippedPass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL( + CallbacksHandle, + runBeforeAnalysis(HasNameRegex("MockAnalysisHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL( + CallbacksHandle, + runAfterAnalysis(HasNameRegex("MockAnalysisHandle"), HasName("loop"))) + .InSequence(PISequence); + EXPECT_CALL(CallbacksHandle, + runAfterPassInvalidated(HasNameRegex("MockPassHandle"))) + .InSequence(PISequence); + EXPECT_CALL(CallbacksHandle, + runAfterPassInvalidated(HasNameRegex("^PassManager"))) + .InSequence(PISequence); + + // Our mock pass invalidates IR, thus normal runAfterPass is never called. + EXPECT_CALL(CallbacksHandle, + runAfterPass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .Times(0); + + StringRef PipelineText = "test-transform"; + ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded()) + << "Pipeline was: " << PipelineText; + PM.run(*M, AM); +} + +TEST_F(LoopNestCallbacksTest, InstrumentedSkippedPasses) { + CallbacksHandle.registerPassInstrumentation(); + // Non-mock instrumentation run here can safely be ignored. + CallbacksHandle.ignoreNonMockPassInstrumentation(""); + CallbacksHandle.ignoreNonMockPassInstrumentation("foo"); + CallbacksHandle.ignoreNonMockPassInstrumentation("loop"); + + // Skip the pass by returning false. + EXPECT_CALL(CallbacksHandle, + runBeforePass(HasNameRegex("MockPassHandle"), HasName("loop"))) + .WillOnce(Return(false)); + + EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _)).Times(0); + EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _)).Times(0); + + // As the pass is skipped there is no afterPass, beforeAnalysis/afterAnalysis + // as well. + EXPECT_CALL(CallbacksHandle, runAfterPass(HasNameRegex("MockPassHandle"), _)) + .Times(0); + EXPECT_CALL(CallbacksHandle, + runAfterPassInvalidated(HasNameRegex("MockPassHandle"))) + .Times(0); + EXPECT_CALL(CallbacksHandle, + runBeforeAnalysis(HasNameRegex("MockAnalysisHandle"), _)) + .Times(0); + EXPECT_CALL(CallbacksHandle, + runAfterAnalysis(HasNameRegex("MockAnalysisHandle"), _)) + .Times(0); + + StringRef PipelineText = "test-transform"; + ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded()) + << "Pipeline was: " << PipelineText; + PM.run(*M, AM); +} + TEST_F(LoopCallbacksTest, Passes) { EXPECT_CALL(AnalysisHandle, run(HasName("loop"), _, _)); EXPECT_CALL(PassHandle, run(HasName("loop"), _, _, _)) diff --git a/llvm/unittests/Transforms/Scalar/CMakeLists.txt b/llvm/unittests/Transforms/Scalar/CMakeLists.txt --- a/llvm/unittests/Transforms/Scalar/CMakeLists.txt +++ b/llvm/unittests/Transforms/Scalar/CMakeLists.txt @@ -11,6 +11,7 @@ add_llvm_unittest(ScalarTests LICMTest.cpp LoopPassManagerTest.cpp + LoopNestPassManagerTest.cpp ) target_link_libraries(ScalarTests PRIVATE LLVMTestingSupport) diff --git a/llvm/unittests/Transforms/Scalar/LICMTest.cpp b/llvm/unittests/Transforms/Scalar/LICMTest.cpp --- a/llvm/unittests/Transforms/Scalar/LICMTest.cpp +++ b/llvm/unittests/Transforms/Scalar/LICMTest.cpp @@ -22,6 +22,7 @@ ModulePassManager MPM; PassBuilder PB; LoopAnalysisManager LAM; + LoopNestAnalysisManager LNAM(LAM); FunctionAnalysisManager FAM; CGSCCAnalysisManager CGAM; ModuleAnalysisManager MAM; @@ -30,7 +31,8 @@ PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.registerLoopNestAnalyses(LNAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); StringRef PipelineStr = "require,loop(licm)"; ASSERT_THAT_ERROR(PB.parsePassPipeline(MPM, PipelineStr), Succeeded()); diff --git a/llvm/unittests/Transforms/Scalar/LoopNestPassManagerTest.cpp b/llvm/unittests/Transforms/Scalar/LoopNestPassManagerTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/Transforms/Scalar/LoopNestPassManagerTest.cpp @@ -0,0 +1,1094 @@ +//===- unittests/Transforms/Scalar/LoopNestPassManagerTest.cpp - LNPM Test ===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Transforms/Scalar/LoopNestPassManager.h" +#include "llvm/Analysis/LoopAnalysisManager.h" +#include "llvm/Analysis/LoopNestAnalysisManager.h" +#include "llvm/AsmParser/Parser.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Support/Regex.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" + +#include +#include + +using namespace llvm; + +namespace { + +using testing::_; +using testing::DoDefault; +using testing::Invoke; +using testing::InvokeWithoutArgs; +using testing::Return; +using testing::WithArgs; + +/// A CRTP base for analysis mock handles +/// +/// This class reconciles mocking with the value semantics implementation of the +/// AnalysisManager. Analysis mock handles should derive from this class and +/// call \c setDefault() in their constroctur for wiring up the defaults defined +/// by this base with their mock run() and invalidate() implementations. +template , + typename... ExtraArgTs> +class MockAnalysisHandleBase { +public: + class Analysis : public AnalysisInfoMixin { + friend AnalysisInfoMixin; + friend MockAnalysisHandleBase; + static AnalysisKey Key; + + DerivedT *Handle; + + Analysis(DerivedT &Handle) : Handle(&Handle) { + static_assert(std::is_base_of::value, + "Must pass the derived type to this template!"); + } + + public: + class Result { + friend MockAnalysisHandleBase; + + DerivedT *Handle; + + Result(DerivedT &Handle) : Handle(&Handle) {} + + public: + // Forward invalidation events to the mock handle. + bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA, + typename AnalysisManagerT::Invalidator &Inv) { + return Handle->invalidate(IR, PA, Inv); + } + }; + + Result run(IRUnitT &IR, AnalysisManagerT &AM, ExtraArgTs... ExtraArgs) { + return Handle->run(IR, AM, ExtraArgs...); + } + }; + + Analysis getAnalysis() { return Analysis(static_cast(*this)); } + typename Analysis::Result getResult() { + return typename Analysis::Result(static_cast(*this)); + } + static StringRef getName() { return llvm::getTypeName(); } + +protected: + // FIXME: MSVC seems unable to handle a lambda argument to Invoke from within + // the template, so we use a boring static function. + static bool invalidateCallback(IRUnitT &IR, const PreservedAnalyses &PA, + typename AnalysisManagerT::Invalidator &Inv) { + auto PAC = PA.template getChecker(); + return !PAC.preserved() && + !PAC.template preservedSet>(); + } + + /// Derived classes should call this in their constructor to set up default + /// mock actions. (We can't do this in our constructor because this has to + /// run after the DerivedT is constructed.) + void setDefaults() { + ON_CALL(static_cast(*this), + run(_, _, testing::Matcher(_)...)) + .WillByDefault(Return(this->getResult())); + ON_CALL(static_cast(*this), invalidate(_, _, _)) + .WillByDefault(Invoke(&invalidateCallback)); + } +}; + +template +AnalysisKey MockAnalysisHandleBase::Analysis::Key; + +/// A CRTP base for pass mock handles +/// +/// This class reconciles mocking with the value semantics implementation of the +/// PassManager. Pass mock handles should derive from this class and +/// call \c setDefault() in their constroctur for wiring up the defaults defined +/// by this base with their mock run() and invalidate() implementations. +template , + typename... ExtraArgTs> +class MockPassHandleBase { +public: + class Pass : public PassInfoMixin { + friend MockPassHandleBase; + + DerivedT *Handle; + + Pass(DerivedT &Handle) : Handle(&Handle) { + static_assert(std::is_base_of::value, + "Must pass the derived type to this template!"); + } + + public: + PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, + ExtraArgTs... ExtraArgs) { + return Handle->run(IR, AM, ExtraArgs...); + } + }; + + static StringRef getName() { return llvm::getTypeName(); } + + Pass getPass() { return Pass(static_cast(*this)); } + +protected: + /// Derived classes should call this in their constructor to set up default + /// mock actions. (We can't do this in our constructor because this has to + /// run after the DerivedT is constructed.) + void setDefaults() { + ON_CALL(static_cast(*this), + run(_, _, testing::Matcher(_)...)) + .WillByDefault(Return(PreservedAnalyses::all())); + } +}; + +struct MockFunctionAnalysisHandle + : MockAnalysisHandleBase { + MOCK_METHOD2(run, Analysis::Result(Function &, FunctionAnalysisManager &)); + + MOCK_METHOD3(invalidate, bool(Function &, const PreservedAnalyses &, + FunctionAnalysisManager::Invalidator &)); + + MockFunctionAnalysisHandle() { setDefaults(); } +}; + +template (-1)> +struct MockLoopNestAnalysisHandleTemplate + : MockAnalysisHandleBase, Loop, + LoopAnalysisManager, + LoopStandardAnalysisResults &> { + using Analysis = typename MockLoopNestAnalysisHandleTemplate::Analysis; + MOCK_METHOD3_T(run, typename Analysis::Result(Loop &, LoopAnalysisManager &, + LoopStandardAnalysisResults &)); + + MOCK_METHOD3_T(invalidate, bool(Loop &, const PreservedAnalyses &, + LoopAnalysisManager::Invalidator &)); + + MockLoopNestAnalysisHandleTemplate() { this->setDefaults(); } +}; + +using MockLoopNestAnalysisHandle = MockLoopNestAnalysisHandleTemplate<>; + +template (-1)> +struct MockLoopAnalysisHandleTemplate + : MockAnalysisHandleBase, Loop, + LoopAnalysisManager, + LoopStandardAnalysisResults &> { + using Analysis = typename MockLoopAnalysisHandleTemplate::Analysis; + MOCK_METHOD3_T(run, typename Analysis::Result(Loop &, LoopAnalysisManager &, + LoopStandardAnalysisResults &)); + + MOCK_METHOD3_T(invalidate, bool(Loop &, const PreservedAnalyses &, + LoopAnalysisManager::Invalidator &)); + + MockLoopAnalysisHandleTemplate() { this->setDefaults(); } +}; + +using MockLoopAnalysisHandle = MockLoopAnalysisHandleTemplate<>; + +struct MockModulePassHandle : MockPassHandleBase { + MOCK_METHOD2(run, PreservedAnalyses(Module &, ModuleAnalysisManager &)); + + MockModulePassHandle() { setDefaults(); } +}; + +struct MockFunctionPassHandle + : MockPassHandleBase { + MOCK_METHOD2(run, PreservedAnalyses(Function &, FunctionAnalysisManager &)); + + MockFunctionPassHandle() { setDefaults(); } +}; + +struct MockLoopNestPassHandle + : MockPassHandleBase { + MOCK_METHOD4(run, + PreservedAnalyses(LoopNest &, LoopNestAnalysisManager &, + LoopStandardAnalysisResults &, LNPMUpdater &)); + + MockLoopNestPassHandle() { setDefaults(); } +}; + +struct MockLoopPassHandle + : MockPassHandleBase { + MOCK_METHOD4(run, + PreservedAnalyses(Loop &, LoopAnalysisManager &, + LoopStandardAnalysisResults &, LPMUpdater &)); + + MockLoopPassHandle() { setDefaults(); } +}; + +/// Helper for HasName matcher that returns getName both for IRUnit and +/// for IRUnit pointer wrapper into llvm::Any (wrapped by PassInstrumentation). +template std::string getName(const IRUnitT &IR) { + return std::string(IR.getName()); +} + +/// Define a custom matcher for objects which support a 'getName' method. +/// +/// LLVM often has IR objects or analysis objects which expose a name +/// and in tests it is convenient to match these by name for readability. +/// Usually, this name is either a StringRef or a plain std::string. This +/// matcher supports any type exposing a getName() method of this form whose +/// return value is compatible with an std::ostream. For StringRef, this uses +/// the shift operator defined above. +/// +/// It should be used as: +/// +/// HasName("my_function") +/// +/// No namespace or other qualification is required. +MATCHER_P(HasName, Name, "") { + *result_listener << "has name '" << getName(arg) << "'"; + return Name == getName(arg); +} + +MATCHER_P(HasNameRegex, Name, "") { + *result_listener << "has name '" << getName(arg) << "'"; + llvm::Regex R(Name); + return R.match(getName(arg)); +} + +std::unique_ptr parseIR(LLVMContext &C, const char *IR) { + SMDiagnostic Err; + return parseAssemblyString(IR, Err, C); +} + +class LoopNestPassManagerTest : public ::testing::Test { +protected: + LLVMContext Context; + std::unique_ptr M; + + LoopAnalysisManager LAM; + LoopNestAnalysisManager LNAM; + FunctionAnalysisManager FAM; + ModuleAnalysisManager MAM; + + MockLoopAnalysisHandle MLAHandle; + MockLoopNestAnalysisHandle MLNAHandle; + + MockLoopPassHandle MLPHandle; + MockLoopNestPassHandle MLNPHandle; + MockFunctionPassHandle MFPHandle; + MockModulePassHandle MMPHandle; + + static PreservedAnalyses + getLoopNestAnalysisResult(LoopNest &LN, LoopNestAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LNPMUpdater &) { + (void)AM.getResult(LN, AR); + return PreservedAnalyses::all(); + } + + static PreservedAnalyses + getLoopAnalysisResult(Loop &L, LoopAnalysisManager &AM, + LoopStandardAnalysisResults &AR, LPMUpdater &) { + (void)AM.getResult(L, AR); + return PreservedAnalyses::all(); + } + +public: + LoopNestPassManagerTest() + : M(parseIR( + Context, + "define void @f(i1* %ptr) {\n" + "entry:\n" + " br label %loop.f.0\n" + "loop.f.0:\n" + " %cond.0 = load volatile i1, i1* %ptr\n" + " br i1 %cond.0, label %loop.f.0.0.ph, label %end\n" + "loop.f.0.0.ph:\n" + " br label %loop.f.0.0\n" + "loop.f.0.0:\n" + " %cond.0.0 = load volatile i1, i1* %ptr\n" + " br i1 %cond.0.0, label %loop.f.0.0, label %loop.f.0.1.ph\n" + "loop.f.0.1.ph:\n" + " br label %loop.f.0.1\n" + "loop.f.0.1:\n" + " %cond.0.1 = load volatile i1, i1* %ptr\n" + " br i1 %cond.0.1, label %loop.f.0.1, label %loop.f.0.latch\n" + "loop.f.0.latch:\n" + " br label %loop.f.0\n" + "end:\n" + " ret void\n" + "}\n" + "\n" + "define void @g(i1* %ptr) {\n" + "entry:\n" + " br label %loop.g.0\n" + "loop.g.0:\n" + " %cond.0 = load volatile i1, i1* %ptr\n" + " br i1 %cond.0, label %loop.g.0, label %loop.g.1.ph\n" + "loop.g.1.ph:\n" + " br label %loop.g.1\n" + "loop.g.1:\n" + " %cond.1 = load volatile i1, i1* %ptr\n" + " br i1 %cond.1, label %loop.g.1.0.ph, label %end\n" + "loop.g.1.0.ph:\n" + " br label %loop.g.1.0\n" + "loop.g.1.0:\n" + " %cond.1.0 = load volatile i1, i1* %ptr\n" + " br i1 %cond.1.0, label %loop.g.1.0, label %loop.g.1.latch\n" + "loop.g.1.latch:\n" + " br label %loop.g.1\n" + "end:\n" + " ret void\n" + "}\n")), + LAM(true), LNAM(LAM), FAM(true), MAM(true) { + // Register mock analysis. + LNAM.registerPass([&] { return MLNAHandle.getAnalysis(); }); + LAM.registerPass([&] { return MLAHandle.getAnalysis(); }); + + // Register loop standard analyses. + FAM.registerPass([&] { return DominatorTreeAnalysis(); }); + FAM.registerPass([&] { return LoopAnalysis(); }); + FAM.registerPass([&] { return AAManager(); }); + FAM.registerPass([&] { return AssumptionAnalysis(); }); + FAM.registerPass([&] { return ScalarEvolutionAnalysis(); }); + FAM.registerPass([&] { return TargetLibraryAnalysis(); }); + FAM.registerPass([&] { return TargetIRAnalysis(); }); + FAM.registerPass([&] { return MemorySSAAnalysis(); }); + + // Register loop nest analysis. + LNAM.registerPass([&] { return LoopNestAnalysis(); }); + + // Register pass instrumentation analysis. + LAM.registerPass([&] { return PassInstrumentationAnalysis(); }); + LNAM.registerPass([&] { return PassInstrumentationAnalysis(); }); + FAM.registerPass([&] { return PassInstrumentationAnalysis(); }); + MAM.registerPass([&] { return PassInstrumentationAnalysis(); }); + + // Cross register analysis manager proxies. + MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); }); + FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); }); + FAM.registerPass( + [&] { return LoopNestAnalysisManagerFunctionProxy(LNAM); }); + FAM.registerPass([&] { return LoopAnalysisManagerFunctionProxy(LAM); }); + LNAM.registerPass( + [&] { return FunctionAnalysisManagerLoopNestProxy(FAM); }); + LAM.registerPass([&] { return FunctionAnalysisManagerLoopProxy(FAM); }); + } +}; + +TEST_F(LoopNestPassManagerTest, Basic) { + ModulePassManager MPM(true); + ::testing::InSequence MakeExpectationsSequenced; + + // First we first visit all the top-level loop nests in both functions, then + // the subloops are visited by the loop passes and loop analyses. By + // definition, the top-level loops will be visited by both kinds of passes and + // analyses. + EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _)) + .WillOnce(Invoke(getLoopNestAnalysisResult)); + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.0"), _, _, _)) + .WillOnce(Invoke(getLoopAnalysisResult)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _)); + EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.1"), _, _, _)) + .WillOnce(Invoke(getLoopAnalysisResult)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _)); + EXPECT_CALL(MLPHandle, run(HasName("loop.f.0"), _, _, _)) + .WillOnce(Invoke(getLoopAnalysisResult)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)); + + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _)) + .WillOnce(Invoke(getLoopNestAnalysisResult)); + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.0"), _, _)); + EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _)) + .WillOnce(Invoke(getLoopAnalysisResult)); + EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)); + + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _)) + .WillOnce(Invoke(getLoopNestAnalysisResult)); + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _)); + EXPECT_CALL(MLPHandle, run(HasName("loop.g.1.0"), _, _, _)) + .WillOnce(Invoke(getLoopAnalysisResult)); + EXPECT_CALL(MLAHandle, run(HasName("loop.g.1.0"), _, _)); + EXPECT_CALL(MLPHandle, run(HasName("loop.g.1"), _, _, _)) + .WillOnce(Invoke(getLoopAnalysisResult)); + EXPECT_CALL(MLAHandle, run(HasName("loop.g.1"), _, _)); + + { + LoopPassManager LPM(true); + LPM.addPass(MLPHandle.getPass()); + LoopNestPassManager LNPM(true); + LNPM.addPass(MLNPHandle.getPass()); + LNPM.addPass(createLoopNestToLoopPassAdaptor(std::move(LPM))); + FunctionPassManager FPM(true); + FPM.addPass(createFunctionToLoopNestPassAdaptor(std::move(LNPM))); + MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); + } + + // Next we reverse the order of loop pass and loop nest pass. The analyses are + // perserved and hence never run. + EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.0"), _, _, _)) + .WillOnce(Invoke(getLoopAnalysisResult)); + EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.1"), _, _, _)) + .WillOnce(Invoke(getLoopAnalysisResult)); + EXPECT_CALL(MLPHandle, run(HasName("loop.f.0"), _, _, _)) + .WillOnce(Invoke(getLoopAnalysisResult)); + EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _)) + .WillOnce(Invoke(getLoopNestAnalysisResult)); + + EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _)) + .WillOnce(Invoke(getLoopAnalysisResult)); + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _)) + .WillOnce(Invoke(getLoopNestAnalysisResult)); + + EXPECT_CALL(MLPHandle, run(HasName("loop.g.1.0"), _, _, _)) + .WillOnce(Invoke(getLoopAnalysisResult)); + EXPECT_CALL(MLPHandle, run(HasName("loop.g.1"), _, _, _)) + .WillOnce(Invoke(getLoopAnalysisResult)); + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _)) + .WillOnce(Invoke(getLoopNestAnalysisResult)); + + { + LoopPassManager LPM(true); + LPM.addPass(MLPHandle.getPass()); + LoopNestPassManager LNPM(true); + LNPM.addPass(createLoopNestToLoopPassAdaptor(std::move(LPM))); + LNPM.addPass(MLNPHandle.getPass()); + FunctionPassManager FPM(true); + FPM.addPass(createFunctionToLoopNestPassAdaptor(std::move(LNPM))); + MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); + } + + EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _)) + .WillOnce(Return(PreservedAnalyses::none())) + .WillOnce(Invoke(getLoopNestAnalysisResult)); + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _)) + .WillOnce(DoDefault()) + .WillOnce(Invoke(getLoopNestAnalysisResult)); + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _)) + .WillOnce(Invoke(getLoopNestAnalysisResult)) + .WillOnce(Return(PreservedAnalyses::none())); + + { + LoopNestPassManager LNPM(true); + LNPM.addPass(MLNPHandle.getPass()); + LNPM.addPass(MLNPHandle.getPass()); + FunctionPassManager FPM(true); + FPM.addPass(createFunctionToLoopNestPassAdaptor(std::move(LNPM))); + MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); + } + + // Inner loops should not be visited by loop nest passes and analyses at all. + EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0.0"), _, _, _)).Times(0); + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0.0"), _, _)).Times(0); + EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0.1"), _, _, _)).Times(0); + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0.1"), _, _)).Times(0); + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1.0"), _, _, _)).Times(0); + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1.0"), _, _)).Times(0); + + MPM.run(*M, MAM); +} + +TEST_F(LoopNestPassManagerTest, DeleteTopLevelLoops) { + ::testing::InSequence MakeExpectationsSequenced; + + EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.0"), _, _, _)); + EXPECT_CALL(MLPHandle, run(HasName("loop.f.0.1"), _, _, _)); + // We mark the top-level loop as deleted in the loop pass, so the loop nest + // pass manager should skip the loop nest. + EXPECT_CALL(MLPHandle, run(HasName("loop.f.0"), _, _, _)) + .WillOnce(WithArgs<0, 3>(Invoke([&](Loop &L, LPMUpdater &U) { + U.markLoopAsDeleted(L, L.getName()); + return PreservedAnalyses::all(); + }))); + + EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _)).Times(0); + + EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _)); + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _)); + // The inner loop is mark as deleted, but it does not affect whether the loop + // nest pass should be run. + EXPECT_CALL(MLPHandle, run(HasName("loop.g.1.0"), _, _, _)) + .WillOnce(WithArgs<0, 3>(Invoke([&](Loop &L, LPMUpdater &U) { + U.markLoopAsDeleted(L, L.getName()); + return PreservedAnalyses::all(); + }))); + EXPECT_CALL(MLPHandle, run(HasName("loop.g.1"), _, _, _)); + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _)); + + ModulePassManager MPM(true); + LoopPassManager LPM(true); + LPM.addPass(MLPHandle.getPass()); + LoopNestPassManager LNPM(true); + LNPM.addPass(createLoopNestToLoopPassAdaptor(std::move(LPM))); + LNPM.addPass(MLNPHandle.getPass()); + FunctionPassManager FPM(true); + FPM.addPass(createFunctionToLoopNestPassAdaptor(std::move(LNPM))); + MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); + + MPM.run(*M, MAM); +} + +TEST_F(LoopNestPassManagerTest, FunctionPassInvalidationOfLoopNestAnalyses) { + ::testing::Sequence FSequence, GSequence; + + // First, force the analysis result to be computed for each loop nest. + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)).InSequence(FSequence); + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.0"), _, _)).InSequence(GSequence); + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _)).InSequence(GSequence); + + FunctionPassManager FPM(true); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + + // No need to re-run if we require again from a fresh loop nest pass manager. + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + + // All analyses are invalidated (the proxy in particular). In this case the + // LoopAnalysisManager (LoopNestAnalysisManager) will be cleared, so the + // invalidation will not happen. + EXPECT_CALL(MFPHandle, run(HasName("f"), _)) + .InSequence(FSequence) + .WillOnce(Return(PreservedAnalyses::none())); + + // Only the MockLoopNestAnalysisHandle::Analysis is invalidated. + PreservedAnalyses PA = getLoopPassPreservedAnalyses(); + PA.preserve(); + if (EnableMSSALoopDependency) + PA.preserve(); + + EXPECT_CALL(MFPHandle, run(HasName("g"), _)) + .InSequence(GSequence) + .WillOnce(Return(PA)); + // The analysis result is not invalidated on loop.g.0, so no need to re-run. + EXPECT_CALL(MLNAHandle, invalidate(HasName("loop.g.0"), _, _)) + .InSequence(GSequence) + .WillOnce(Return(false)); + EXPECT_CALL(MLNAHandle, invalidate(HasName("loop.g.1"), _, _)) + .InSequence(GSequence); + + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)).InSequence(FSequence); + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _)).InSequence(GSequence); + + FPM.addPass(MFPHandle.getPass()); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + + ModulePassManager MPM(true); + MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); + + MPM.addPass( + createModuleToFunctionPassAdaptor(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass< + MockLoopNestAnalysisHandle::Analysis>()))); + + MPM.run(*M, MAM); +} + +TEST_F(LoopNestPassManagerTest, LoopNestPassInvalidationOfLoopAnalyses) { + ::testing::Sequence FSequence, G0Sequence, G1Sequence; + + // First, force the analysis result to be computed for each loop. + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _)) + .InSequence(FSequence); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _)) + .InSequence(FSequence); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)).InSequence(FSequence); + + EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)).InSequence(G0Sequence); + EXPECT_CALL(MLAHandle, run(HasName("loop.g.1.0"), _, _)) + .InSequence(G1Sequence); + EXPECT_CALL(MLAHandle, run(HasName("loop.g.1"), _, _)).InSequence(G1Sequence); + + LoopNestPassManager LNPM(true); + LNPM.addPass(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass())); + + // No need to re-run if we require again from a fresh loop pass manager. + LNPM.addPass(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass())); + + EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _)) + .InSequence(FSequence) + .WillOnce(Return(PreservedAnalyses::none())); + EXPECT_CALL(MLAHandle, invalidate(HasName("loop.f.0.0"), _, _)) + .InSequence(FSequence); + EXPECT_CALL(MLAHandle, invalidate(HasName("loop.f.0.1"), _, _)) + .InSequence(FSequence) + .WillOnce(Return(false)); + EXPECT_CALL(MLAHandle, invalidate(HasName("loop.f.0"), _, _)) + .InSequence(FSequence); + + // Only the MockLoopAnalysisHandle::Analysis is invalidated. + PreservedAnalyses PA = getLoopPassPreservedAnalyses(); + if (EnableMSSALoopDependency) + PA.preserve(); + + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _)) + .InSequence(G0Sequence) + .WillOnce(Return(PA)); + EXPECT_CALL(MLAHandle, invalidate(HasName("loop.g.0"), _, _)) + .InSequence(G0Sequence); + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _)) + .InSequence(G1Sequence); + LNPM.addPass(MLNPHandle.getPass()); + + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _)) + .InSequence(FSequence); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)).InSequence(FSequence); + EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)).InSequence(G0Sequence); + + LNPM.addPass(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass())); + + ModulePassManager MPM(true); + MPM.addPass(createModuleToFunctionPassAdaptor( + createFunctionToLoopNestPassAdaptor(std::move(LNPM)))); + MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor( + RequireAnalysisLoopPass()))); + MPM.run(*M, MAM); +} + +TEST_F(LoopNestPassManagerTest, ModulePassInvalidationOfLoopNestAnalyses) { + ModulePassManager MPM(true); + ::testing::InSequence MakeExpectationsSequenced; + + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.0"), _, _)); + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _)); + MPM.addPass( + createModuleToFunctionPassAdaptor(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass< + MockLoopNestAnalysisHandle::Analysis>()))); + MPM.addPass( + createModuleToFunctionPassAdaptor(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass< + MockLoopNestAnalysisHandle::Analysis>()))); + + EXPECT_CALL(MMPHandle, run(_, _)).WillOnce(InvokeWithoutArgs([] { + auto PA = getLoopPassPreservedAnalyses(); + PA.preserve(); + PA.preserve(); + if (EnableMSSALoopDependency) + PA.preserve(); + return PA; + })); + + EXPECT_CALL(MLNAHandle, invalidate(HasName("loop.f.0"), _, _)); + EXPECT_CALL(MLNAHandle, invalidate(HasName("loop.g.0"), _, _)) + .WillOnce(Return(false)); + EXPECT_CALL(MLNAHandle, invalidate(HasName("loop.g.1"), _, _)); + + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _)); + + MPM.addPass(MMPHandle.getPass()); + MPM.addPass( + createModuleToFunctionPassAdaptor(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass< + MockLoopNestAnalysisHandle::Analysis>()))); + MPM.addPass( + createModuleToFunctionPassAdaptor(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass< + MockLoopNestAnalysisHandle::Analysis>()))); + EXPECT_CALL(MMPHandle, run(_, _)).WillOnce(InvokeWithoutArgs([] { + auto PA = PreservedAnalyses::none(); + PA.preserveSet>(); + PA.preserveSet>(); + return PA; + })); + + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.0"), _, _)); + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _)); + MPM.addPass(MMPHandle.getPass()); + MPM.addPass( + createModuleToFunctionPassAdaptor(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass< + MockLoopNestAnalysisHandle::Analysis>()))); + + MPM.run(*M, MAM); +} + +// Test that if any of the bundled analyses provided in the LNPM's signature +// become invalid, the analysis proxy itself becomes invalid and we clear all +// loop nest analysis and loop analysis results. +TEST_F(LoopNestPassManagerTest, InvalidationOfBoundedAnalyses) { + ModulePassManager MPM(true); + FunctionPassManager FPM(true); + ::testing::InSequence MakeExpectationsSequenced; + + // First, force the analysis result to be computed for each loop nest. + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + FPM.addPass( + createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass()))); + + // No need to re-run if we require again from a fresh loop nest pass manager. + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + FPM.addPass( + createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass()))); + + // Preserving everything but the loop analyses themselves results in + // invalidation and running. + EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { + PreservedAnalyses PA = getLoopPassPreservedAnalyses(); + PA.preserve(); + return PA; + })); + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)); + FPM.addPass(MFPHandle.getPass()); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + FPM.addPass( + createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass()))); + + EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { + PreservedAnalyses PA = getLoopPassPreservedAnalyses(); + PA.preserve(); + PA.preserve(); + return PA; + })); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)); + FPM.addPass(MFPHandle.getPass()); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + FPM.addPass( + createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass()))); + + EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { + PreservedAnalyses PA = getLoopPassPreservedAnalyses(); + PA.preserve(); + PA.preserve(); + return PA; + })); + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + FPM.addPass(MFPHandle.getPass()); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + FPM.addPass( + createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass()))); + + // The rest don't invalidate analyses, they only trigger re-runs because we + // clear the cache completely. + EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { + auto PA = PreservedAnalyses::none(); + PA.preserve(); + // Abandon `AAManager`. + PA.abandon(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + return PA; + })); + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)); + FPM.addPass(MFPHandle.getPass()); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + FPM.addPass( + createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass()))); + + EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { + auto PA = PreservedAnalyses::none(); + PA.preserve(); + PA.preserve(); + // Not preserving `AssumptionAnalysis`. + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + return PA; + })); + // Special case: AssumptionAnalysis will never be invalidated. + FPM.addPass(MFPHandle.getPass()); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + FPM.addPass( + createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass()))); + + EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { + auto PA = PreservedAnalyses::none(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + // Abandon `DominatorTreeAnalysis`. + PA.abandon(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + return PA; + })); + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)); + FPM.addPass(MFPHandle.getPass()); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + FPM.addPass( + createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass()))); + + EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { + auto PA = PreservedAnalyses::none(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + // Abandon the `LoopAnalysis`. + PA.abandon(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + return PA; + })); + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)); + FPM.addPass(MFPHandle.getPass()); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + FPM.addPass( + createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass()))); + + EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { + auto PA = PreservedAnalyses::none(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + // Abandon the `LoopNestAnalysisManagerFunctionProxy`. + PA.abandon(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + return PA; + })); + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)); + FPM.addPass(MFPHandle.getPass()); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + FPM.addPass( + createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass()))); + + EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { + auto PA = PreservedAnalyses::none(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + PA.preserve(); + // Abandon `ScalarEvolutionAnalysis`. + PA.abandon(); + PA.preserve(); + PA.preserve(); + return PA; + })); + EXPECT_CALL(MLNAHandle, run(HasName("loop.f.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0.1"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.f.0"), _, _)); + FPM.addPass(MFPHandle.getPass()); + FPM.addPass(createFunctionToLoopNestPassAdaptor( + RequireAnalysisLoopNestPass())); + FPM.addPass( + createFunctionToLoopNestPassAdaptor(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass()))); + + // The loop analyses and loop nest analyses will be run only on the first + // time. The results are cached in the remaining passes. + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.0"), _, _)); + EXPECT_CALL(MLNAHandle, run(HasName("loop.g.1"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.g.1.0"), _, _)); + EXPECT_CALL(MLAHandle, run(HasName("loop.g.1"), _, _)); + EXPECT_CALL(MFPHandle, run(HasName("g"), _)).Times(9); + + MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); + MPM.run(*M, MAM); +} + +// Test that if a loop analysis is not preserved in the LoopNestPass, the +// analysis results on the corresponding subtree will all be invalidated. +TEST_F(LoopNestPassManagerTest, InvalidationOfLoopAnalysesInSubtree) { + ::testing::Sequence F0Sequence, G0Sequence, G1Sequence; + + // Register two kinds of loop analyses. + enum : size_t { A, B }; + MockLoopAnalysisHandleTemplate MLAHandleA; + MockLoopAnalysisHandleTemplate MLAHandleB; + + LAM.registerPass([&] { return MLAHandleA.getAnalysis(); }); + LAM.registerPass([&] { return MLAHandleB.getAnalysis(); }); + + // Force both kinds of analyses to be cached on all loops. + EXPECT_CALL(MLAHandleA, run(HasName("loop.f.0.0"), _, _)) + .InSequence(F0Sequence); + EXPECT_CALL(MLAHandleA, run(HasName("loop.f.0.1"), _, _)) + .InSequence(F0Sequence); + EXPECT_CALL(MLAHandleA, run(HasName("loop.f.0"), _, _)) + .InSequence(F0Sequence); + + EXPECT_CALL(MLAHandleB, run(HasName("loop.f.0.0"), _, _)) + .InSequence(F0Sequence); + EXPECT_CALL(MLAHandleB, run(HasName("loop.f.0.1"), _, _)) + .InSequence(F0Sequence); + EXPECT_CALL(MLAHandleB, run(HasName("loop.f.0"), _, _)) + .InSequence(F0Sequence); + + EXPECT_CALL(MLAHandleA, run(HasName("loop.g.0"), _, _)) + .InSequence(G0Sequence); + EXPECT_CALL(MLAHandleA, run(HasName("loop.g.1.0"), _, _)) + .InSequence(G1Sequence); + EXPECT_CALL(MLAHandleA, run(HasName("loop.g.1"), _, _)) + .InSequence(G1Sequence); + + EXPECT_CALL(MLAHandleB, run(HasName("loop.g.0"), _, _)) + .InSequence(G0Sequence); + EXPECT_CALL(MLAHandleB, run(HasName("loop.g.1.0"), _, _)) + .InSequence(G1Sequence); + EXPECT_CALL(MLAHandleB, run(HasName("loop.g.1"), _, _)) + .InSequence(G1Sequence); + + LoopNestPassManager LNPM(true); + LNPM.addPass(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass::Analysis>())); + LNPM.addPass(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass::Analysis>())); + + EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _)) + .InSequence(F0Sequence); + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _)) + .InSequence(G0Sequence); + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _)) + .InSequence(G1Sequence); + + LNPM.addPass(MLNPHandle.getPass()); + + // The analyses results should be cached and the analysis passes don't have to + // be executed again after the loop nest pass. + LNPM.addPass(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass::Analysis>())); + LNPM.addPass(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass::Analysis>())); + + // The loop nest pass does not preserve loop analysis B on loop nest f.0, + // which means that analysis B will indeed be invalidated on loops f.0.0, + // f.0.1, and f.0. + EXPECT_CALL(MLNPHandle, run(HasName("loop.f.0"), _, _, _)) + .InSequence(F0Sequence) + .WillOnce(InvokeWithoutArgs([] { + PreservedAnalyses PA; + PA.preserveSet>(); + PA.preserve::Analysis>(); + return PA; + })); + EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.f.0.0"), _, _)) + .InSequence(F0Sequence); + // Returns false on purpose: the analysis pass should be skipped. + EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.f.0.1"), _, _)) + .InSequence(F0Sequence) + .WillOnce(Return(false)); + EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.f.0"), _, _)) + .InSequence(F0Sequence); + + EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.f.0.0"), _, _)); + EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.f.0.1"), _, _)); + EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.f.0"), _, _)); + + // On loop nest g.0, although both analysis A and B are preserved, the + // `invalidation` method will still be invoked since `AllAnalysesOn` is + // not preserved. However, the analysis results are still valid so no need to + // re-run analysis passes in this case. + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.0"), _, _, _)) + .InSequence(G0Sequence) + .WillOnce(InvokeWithoutArgs([] { + PreservedAnalyses PA; + PA.preserveSet>(); + PA.preserve::Analysis>(); + PA.preserve::Analysis>(); + return PA; + })); + + EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.g.0"), _, _)); + EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.g.0"), _, _)); + + // On loop nest g.1, all loop analyses are marked as preserved. In this case, + // the `invalidation` method of the subloops will not be called. + EXPECT_CALL(MLNPHandle, run(HasName("loop.g.1"), _, _, _)) + .InSequence(G1Sequence) + .WillOnce(InvokeWithoutArgs([] { + PreservedAnalyses PA; + PA.preserveSet>(); + PA.preserveSet>(); + return PA; + })); + + EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.g.1"), _, _)).Times(0); + EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.g.1.0"), _, _)).Times(0); + EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.g.1"), _, _)).Times(0); + EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.g.1.0"), _, _)).Times(0); + + LNPM.addPass(MLNPHandle.getPass()); + + // On loop nest f.0, only analysis pass B will be re-run. + EXPECT_CALL(MLAHandleB, run(HasName("loop.f.0.0"), _, _)) + .InSequence(F0Sequence); + EXPECT_CALL(MLAHandleB, run(HasName("loop.f.0"), _, _)) + .InSequence(F0Sequence); + + LNPM.addPass(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass::Analysis>())); + LNPM.addPass(createLoopNestToLoopPassAdaptor( + RequireAnalysisLoopPass::Analysis>())); + + ModulePassManager MPM(true); + MPM.addPass(createModuleToFunctionPassAdaptor( + createFunctionToLoopNestPassAdaptor(std::move(LNPM)))); + + MPM.run(*M, MAM); +} + +} // namespace diff --git a/polly/unittests/ScopPassManager/PassManagerTest.cpp b/polly/unittests/ScopPassManager/PassManagerTest.cpp --- a/polly/unittests/ScopPassManager/PassManagerTest.cpp +++ b/polly/unittests/ScopPassManager/PassManagerTest.cpp @@ -16,6 +16,7 @@ protected: ModuleAnalysisManager MAM; FunctionAnalysisManager FAM; + LoopNestAnalysisManager LNAM; LoopAnalysisManager LAM; CGSCCAnalysisManager CGAM; ScopAnalysisManager SAM; @@ -26,13 +27,14 @@ ScopPassRegistry(const ScopPassRegistry &) = delete; ScopPassRegistry &operator=(ScopPassRegistry &&) = delete; ScopPassRegistry &operator=(const ScopPassRegistry &) = delete; - ScopPassRegistry() { + ScopPassRegistry() : LNAM(LAM) { PassBuilder PB; AM = PB.buildDefaultAAPipeline(); PB.registerModuleAnalyses(MAM); PB.registerFunctionAnalyses(FAM); PB.registerLoopAnalyses(LAM); + PB.registerLoopNestAnalyses(LNAM); PB.registerCGSCCAnalyses(CGAM); FAM.registerPass([] { return ScopAnalysis(); }); @@ -43,7 +45,7 @@ // SAM.registerPass([] { return DependenceAnalysis(); }); SAM.registerPass([this] { return FunctionAnalysisManagerScopProxy(FAM); }); - PB.crossRegisterProxies(LAM, FAM, CGAM, MAM); + PB.crossRegisterProxies(LAM, LNAM, FAM, CGAM, MAM); } };