Index: include/llvm/Analysis/LoopInfo.h =================================================================== --- include/llvm/Analysis/LoopInfo.h +++ include/llvm/Analysis/LoopInfo.h @@ -469,6 +469,15 @@ return DebugLoc(); } + StringRef getName() const { + // TODO: Is the name of the header block sufficient, or should we have + // something like " loop
"? + if (BasicBlock *Header = getHeader()) + if (Header->hasName()) + return Header->getName(); + return ""; + } + private: friend class LoopInfoBase; explicit Loop(BasicBlock *BB) : LoopBase(BB) {} Index: include/llvm/Analysis/LoopPassManager.h =================================================================== --- /dev/null +++ include/llvm/Analysis/LoopPassManager.h @@ -0,0 +1,273 @@ +//===- LoopPassManager.h - Loop pass management -----------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// This header provides classes for managing passes over loops in LLVM IR. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_LOOPPASSMANAGER_H +#define LLVM_ANALYSIS_LOOPPASSMANAGER_H + +#include "llvm/ADT/PostOrderIterator.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/IR/PassManager.h" +#include + +namespace llvm { + +/// \brief The loop pass manager. +/// +/// See the documentation for the PassManager template for details. It runs a +/// sequency of loop passes over each loop that the manager is run over. This +/// typedef serves as a convenient way to refer to this construct. +typedef PassManager LoopPassManager; + +/// \brief The loop analysis manager. +/// +/// See the documentation for the AnalysisManager template for detail +/// documentation. This typedef serves as a convenient way to refer to this +/// construct in the adaptors and proxies used to integrate this into the larger +/// pass manager infrastructure. +typedef AnalysisManager LoopAnalysisManager; + +template <> class IRUnitTraits { +public: + static bool hasBeenInvalidated(Loop &IR) { return IR.isInvalid(); } +}; + +/// \brief A function analysis which acts as a proxy for a loop analysis +/// manager. +/// +/// This primarily proxies invalidation information from the function analysis +/// manager and function pass manager to a loop analysis manager. You should +/// never use a loop analysis manager from within (transitively) a function +/// pass manager unless your parent function pass has received a proxy result +/// object for it. +class LoopAnalysisManagerFunctionProxy { +public: + class Result { + public: + explicit Result(LoopAnalysisManager &LAM) : LAM(&LAM) {} + // We have to explicitly define all the special member functions because + // MSVC refuses to generate them. + Result(const Result &Arg) : LAM(Arg.LAM) {} + Result(Result &&Arg) : LAM(std::move(Arg.LAM)) {} + Result &operator=(Result RHS) { + std::swap(LAM, RHS.LAM); + return *this; + } + ~Result(); + + /// \brief Accessor for the \c LoopAnalysisManager. + LoopAnalysisManager &getManager() { return *LAM; } + + /// \brief Handler for invalidation of the function. + /// + /// If this analysis itself is preserved, then we assume that the function + /// hasn't changed and thus we don't need to invalidate *all* cached data + /// associated with a \c Loop* in the \c LoopAnalysisManager. + /// + /// Regardless of whether this analysis is marked as preserved, all of the + /// analyses in the \c LoopAnalysisManager are potentially invalidated based + /// on the set of preserved analyses. + bool invalidate(Function &F, const PreservedAnalyses &PA); + + private: + LoopAnalysisManager *LAM; + }; + + static void *ID() { return (void *)&PassID; } + + static StringRef name() { return "LoopAnalysisManagerFunctionProxy"; } + + explicit LoopAnalysisManagerFunctionProxy(LoopAnalysisManager &LAM) + : LAM(&LAM) {} + // We have to explicitly define all the special member functions because MSVC + // refuses to generate them. + LoopAnalysisManagerFunctionProxy(const LoopAnalysisManagerFunctionProxy &Arg) + : LAM(Arg.LAM) {} + LoopAnalysisManagerFunctionProxy(LoopAnalysisManagerFunctionProxy &&Arg) + : LAM(std::move(Arg.LAM)) {} + LoopAnalysisManagerFunctionProxy & + operator=(LoopAnalysisManagerFunctionProxy RHS) { + std::swap(LAM, RHS.LAM); + return *this; + } + + /// \brief Run the analysis pass and create our proxy result object. + /// + /// This doesn't do any interesting work, it is primarily used to insert our + /// proxy result object into the function analysis cache so that we can proxy + /// invalidation to the loop analysis manager. + /// + /// In debug builds, it will also assert that the analysis manager is empty as + /// no queries should arrive at the loop analysis manager prior to this + /// analysis being requested. + Result run(Function &F); + +private: + static char PassID; + + LoopAnalysisManager *LAM; +}; + +/// \brief A loop analysis which acts as a proxy for a function analysis +/// manager. +/// +/// This primarily provides an accessor to a parent function analysis manager to +/// loop passes. Only the const interface of the function analysis manager is +/// provided to indicate that once inside of a loop analysis pass you cannot +/// request a function analysis to actually run. Instead, the user must rely on +/// the \c getCachedResult API. +/// +/// This proxy *doesn't* manage the invalidation in any way. That is handled by +/// the recursive return path of each layer of the pass manager and the +/// returned PreservedAnalysis set. +class FunctionAnalysisManagerLoopProxy { +public: + /// \brief Result proxy object for \c FunctionAnalysisManagerLoopProxy. + class Result { + public: + explicit Result(const FunctionAnalysisManager &FAM) : FAM(&FAM) {} + // We have to explicitly define all the special member functions because + // MSVC refuses to generate them. + Result(const Result &Arg) : FAM(Arg.FAM) {} + Result(Result &&Arg) : FAM(std::move(Arg.FAM)) {} + Result &operator=(Result RHS) { + std::swap(FAM, RHS.FAM); + return *this; + } + + const FunctionAnalysisManager &getManager() const { return *FAM; } + + /// \brief Handle invalidation by ignoring it, this pass is immutable. + bool invalidate(Function &) { return false; } + + private: + const FunctionAnalysisManager *FAM; + }; + + static void *ID() { return (void *)&PassID; } + + static StringRef name() { return "FunctionAnalysisManagerLoopProxy"; } + + FunctionAnalysisManagerLoopProxy(const FunctionAnalysisManager &FAM) + : FAM(&FAM) {} + // We have to explicitly define all the special member functions because MSVC + // refuses to generate them. + FunctionAnalysisManagerLoopProxy(const FunctionAnalysisManagerLoopProxy &Arg) + : FAM(Arg.FAM) {} + FunctionAnalysisManagerLoopProxy(FunctionAnalysisManagerLoopProxy &&Arg) + : FAM(std::move(Arg.FAM)) {} + FunctionAnalysisManagerLoopProxy & + operator=(FunctionAnalysisManagerLoopProxy RHS) { + std::swap(FAM, RHS.FAM); + return *this; + } + + /// \brief Run the analysis pass and create our proxy result object. + /// Nothing to see here, it just forwards the \c FAM reference into the + /// result. + Result run(Loop &) { return Result(*FAM); } + +private: + static char PassID; + + const FunctionAnalysisManager *FAM; +}; + +/// \brief Adaptor that maps from a function to its loops. +/// +/// Designed to allow composition of a LoopPass(Manager) and a +/// FunctionPassManager. Note that if this pass is constructed with a \c +/// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy +/// analysis prior to running the loop passes over the function to enable a \c +/// LoopAnalysisManager to be used within this run safely. +template class FunctionToLoopPassAdaptor { +public: + explicit FunctionToLoopPassAdaptor(LoopPassT Pass) + : Pass(std::move(Pass)) {} + // We have to explicitly define all the special member functions because MSVC + // refuses to generate them. + FunctionToLoopPassAdaptor(const FunctionToLoopPassAdaptor &Arg) + : Pass(Arg.Pass) {} + FunctionToLoopPassAdaptor(FunctionToLoopPassAdaptor &&Arg) + : Pass(std::move(Arg.Pass)) {} + friend void swap(FunctionToLoopPassAdaptor &LHS, + FunctionToLoopPassAdaptor &RHS) { + using std::swap; + swap(LHS.Pass, RHS.Pass); + } + FunctionToLoopPassAdaptor &operator=(FunctionToLoopPassAdaptor RHS) { + swap(*this, RHS); + return *this; + } + + void enqueueLoop(Loop *L, std::deque &LQ) { + LQ.push_back(L); + for (auto *NestedLoop : reverse(*L)) + enqueueLoop(NestedLoop, LQ); + } + + /// \brief Runs the loop passes across every loop in the function. + PreservedAnalyses run(Function &F, FunctionAnalysisManager *AM) { + assert(AM && "We need analyses to compute the loop structure!"); + + // Setup the loop analysis manager from its proxy. + LoopAnalysisManager *LAM = + &AM->getResult(F).getManager(); + // Get the loop structure for this function + LoopInfo &LI = AM->getResult(F); + + PreservedAnalyses PA = PreservedAnalyses::all(); + + std::deque LQ; + for (auto *L : reverse(LI)) + enqueueLoop(L, LQ); + + for (auto *L : reverse(LQ)) { + PreservedAnalyses PassPA = Pass.run(*L, LAM); + + // We know that the loop pass couldn't have invalidated any other loop's + // analyses (that's the contract of a loop pass), so directly handle the + // loop analysis manager's invalidation here. Also, update the + // preserved analyses to reflect that once invalidated these can again + // be preserved. + PassPA = LAM->invalidate(*L, std::move(PassPA)); + + // Then intersect the preserved set so that invalidation of module + // analyses will eventually occur when the module pass completes. + PA.intersect(std::move(PassPA)); + } + + // By definition we preserve the proxy. This precludes *any* invalidation of + // loop analyses by the proxy, but that's OK because we've taken care to + // invalidate analyses in the loop analysis manager incrementally above. + PA.preserve(); + return PA; + } + + static StringRef name() { return "FunctionToLoopPassAdaptor"; } + +private: + LoopPassT Pass; +}; + +/// \brief A function to deduce a loop pass type and wrap it in the templated +/// adaptor. +template +FunctionToLoopPassAdaptor +createFunctionToLoopPassAdaptor(LoopPassT Pass) { + return FunctionToLoopPassAdaptor(std::move(Pass)); +} +} + +#endif // LLVM_ANALYSIS_LOOPPASSMANAGER_H Index: include/llvm/IR/PassManager.h =================================================================== --- include/llvm/IR/PassManager.h +++ include/llvm/IR/PassManager.h @@ -166,6 +166,11 @@ // Forward declare the analysis manager template. template class AnalysisManager; +template class IRUnitTraits { +public: + static bool hasBeenInvalidated(IRUnitT &IR) { return false; } +}; + /// \brief Manages a sequence of passes over units of IR. /// /// A pass manager contains a sequence of passes to run over units of IR. It is @@ -225,6 +230,12 @@ // context and it isn't yet clear what the right pattern is for yielding // in the new pass manager so it is currently omitted. //IR.getContext().yield(); + + if (IRUnitTraits::hasBeenInvalidated(IR)) { + if (DebugLogging) + dbgs() << IR.getName() << " is invalid. Skipping remaining passes.\n"; + break; + } } if (DebugLogging) Index: include/llvm/Passes/PassBuilder.h =================================================================== --- include/llvm/Passes/PassBuilder.h +++ include/llvm/Passes/PassBuilder.h @@ -18,6 +18,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/LoopPassManager.h" #include "llvm/IR/PassManager.h" namespace llvm { @@ -56,6 +57,13 @@ /// still manually register any additional analyses. void registerFunctionAnalyses(FunctionAnalysisManager &FAM); + /// \brief Registers all available loop analysis passes. + /// + /// This is an interface that can be used to populate a \c LoopAnalysisManager + /// with all registered loop analyses. Callers can still manually register any + /// additional analyses. + void registerLoopAnalyses(LoopAnalysisManager &LAM); + /// \brief Parse a textual pass pipeline description into a \c ModulePassManager. /// /// The format of the textual pass pipeline description looks something like: @@ -91,6 +99,9 @@ bool parseModulePassName(ModulePassManager &MPM, StringRef Name); bool parseCGSCCPassName(CGSCCPassManager &CGPM, StringRef Name); bool parseFunctionPassName(FunctionPassManager &FPM, StringRef Name); + bool parseLoopPassName(LoopPassManager &LPM, StringRef Name); + bool parseLoopPassPipeline(LoopPassManager &LPM, StringRef &PipelineText, + bool VerifyEachPass, bool DebugLogging); bool parseFunctionPassPipeline(FunctionPassManager &FPM, StringRef &PipelineText, bool VerifyEachPass, bool DebugLogging); @@ -99,7 +110,6 @@ bool parseModulePassPipeline(ModulePassManager &MPM, StringRef &PipelineText, bool VerifyEachPass, bool DebugLogging); }; - } #endif Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -41,6 +41,7 @@ LoopAccessAnalysis.cpp LoopInfo.cpp LoopPass.cpp + LoopPassManager.cpp MemDepPrinter.cpp MemDerefPrinter.cpp MemoryBuiltins.cpp Index: lib/Analysis/LoopPassManager.cpp =================================================================== --- /dev/null +++ lib/Analysis/LoopPassManager.cpp @@ -0,0 +1,45 @@ +//===- LoopPassManager.cpp - Loop pass management -------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/LoopPassManager.h" + +using namespace llvm; + +char LoopAnalysisManagerFunctionProxy::PassID; + +LoopAnalysisManagerFunctionProxy::Result +LoopAnalysisManagerFunctionProxy::run(Function &F) { + // TODO: In FunctionAnalysisManagerModuleProxy we assert that the + // AnalysisManager is empty, but if we do that here we run afoul of the fact + // that we still have results for previous functions alive. Should we be + // clearing those when we finish a function? + //assert(LAM->empty() && "Loop analyses ran prior to the function proxy!"); + return Result(*LAM); +} + +LoopAnalysisManagerFunctionProxy::Result::~Result() { + // Clear out the analysis manager if we're being destroyed -- it means we + // didn't even see an invalidate call when we got invalidated. + LAM->clear(); +} + +bool LoopAnalysisManagerFunctionProxy::Result::invalidate( + Function &F, const PreservedAnalyses &PA) { + // If this proxy isn't marked as preserved, then we can't even invalidate + // individual loop analyses, there may be an invalid set of Loops in the cache + // making it impossible to incrementally preserve them. Just clear the entire + // manager. + if (!PA.preserved(ID())) + LAM->clear(); + + // Return false to indicate that this result is still a valid proxy. + return false; +} + +char FunctionAnalysisManagerLoopProxy::PassID; Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -99,6 +99,24 @@ char NoOpFunctionAnalysis::PassID; +/// \brief No-op loop pass which does nothing. +struct NoOpLoopPass { + PreservedAnalyses run(Loop &L) { return PreservedAnalyses::all(); } + static StringRef name() { return "NoOpLoopPass"; } +}; + +/// \brief No-op loop analysis. +struct NoOpLoopAnalysis { + struct Result {}; + Result run(Loop &) { return Result(); } + static StringRef name() { return "NoOpLoopAnalysis"; } + static void *ID() { return (void *)&PassID; } +private: + static char PassID; +}; + +char NoOpLoopAnalysis::PassID; + } // End anonymous namespace. void PassBuilder::registerModuleAnalyses(ModuleAnalysisManager &MAM) { @@ -119,6 +137,12 @@ #include "PassRegistry.def" } +void PassBuilder::registerLoopAnalyses(LoopAnalysisManager &LAM) { +#define LOOP_ANALYSIS(NAME, CREATE_PASS) \ + LAM.registerPass(CREATE_PASS); +#include "PassRegistry.def" +} + #ifndef NDEBUG static bool isModulePassName(StringRef Name) { #define MODULE_PASS(NAME, CREATE_PASS) if (Name == NAME) return true; @@ -151,6 +175,16 @@ return false; } +static bool isLoopPassName(StringRef Name) { +#define LOOP_PASS(NAME, CREATE_PASS) if (Name == NAME) return true; +#define LOOP_ANALYSIS(NAME, CREATE_PASS) \ + if (Name == "require<" NAME ">" || Name == "invalidate<" NAME ">") \ + return true; +#include "PassRegistry.def" + + return false; +} + bool PassBuilder::parseModulePassName(ModulePassManager &MPM, StringRef Name) { #define MODULE_PASS(NAME, CREATE_PASS) \ if (Name == NAME) { \ @@ -212,6 +246,66 @@ return false; } +bool PassBuilder::parseLoopPassName(LoopPassManager &FPM, + StringRef Name) { +#define LOOP_PASS(NAME, CREATE_PASS) \ + if (Name == NAME) { \ + FPM.addPass(CREATE_PASS); \ + return true; \ + } +#define LOOP_ANALYSIS(NAME, CREATE_PASS) \ + if (Name == "require<" NAME ">") { \ + FPM.addPass(RequireAnalysisPass()); \ + return true; \ + } \ + if (Name == "invalidate<" NAME ">") { \ + FPM.addPass(InvalidateAnalysisPass()); \ + return true; \ + } +#include "PassRegistry.def" + + return false; +} + +bool PassBuilder::parseLoopPassPipeline(LoopPassManager &LPM, + StringRef &PipelineText, + bool VerifyEachPass, + bool DebugLogging) { + for (;;) { + // Parse nested pass managers by recursing. + if (PipelineText.startswith("loop(")) { + LoopPassManager NestedLPM(DebugLogging); + + // Parse the inner pipeline inte the nested manager. + PipelineText = PipelineText.substr(strlen("loop(")); + if (!parseLoopPassPipeline(NestedLPM, PipelineText, VerifyEachPass, + DebugLogging) || + PipelineText.empty()) + return false; + assert(PipelineText[0] == ')'); + PipelineText = PipelineText.substr(1); + + // Add the nested pass manager with the appropriate adaptor. + LPM.addPass(std::move(NestedLPM)); + } else { + // Otherwise try to parse a pass name. + size_t End = PipelineText.find_first_of(",)"); + if (!parseLoopPassName(LPM, PipelineText.substr(0, End))) + return false; + // TODO: Ideally, we would run a LoopVerifierPass() here in the + // VerifyEachPass case, but we don't have such a verifier yet. + + PipelineText = PipelineText.substr(End); + } + + if (PipelineText.empty() || PipelineText[0] == ')') + return true; + + assert(PipelineText[0] == ','); + PipelineText = PipelineText.substr(1); + } +} + bool PassBuilder::parseFunctionPassPipeline(FunctionPassManager &FPM, StringRef &PipelineText, bool VerifyEachPass, @@ -232,6 +326,20 @@ // Add the nested pass manager with the appropriate adaptor. FPM.addPass(std::move(NestedFPM)); + } else if (PipelineText.startswith("loop(")) { + LoopPassManager NestedLPM(DebugLogging); + + // Parse the inner pipeline inte the nested manager. + PipelineText = PipelineText.substr(strlen("loop(")); + if (!parseLoopPassPipeline(NestedLPM, PipelineText, VerifyEachPass, + DebugLogging) || + PipelineText.empty()) + return false; + assert(PipelineText[0] == ')'); + PipelineText = PipelineText.substr(1); + + // Add the nested pass manager with the appropriate adaptor. + FPM.addPass(createFunctionToLoopPassAdaptor(std::move(NestedLPM))); } else { // Otherwise try to parse a pass name. size_t End = PipelineText.find_first_of(",)"); @@ -392,7 +500,7 @@ // If this looks like a CGSCC pass, parse the whole thing as a CGSCC // pipeline. - if (isCGSCCPassName(FirstName)) { + if (PipelineText.startswith("cgscc(") || isCGSCCPassName(FirstName)) { CGSCCPassManager CGPM(DebugLogging); if (!parseCGSCCPassPipeline(CGPM, PipelineText, VerifyEachPass, DebugLogging) || @@ -404,7 +512,7 @@ // Similarly, if this looks like a Function pass, parse the whole thing as // a Function pipelien. - if (isFunctionPassName(FirstName)) { + if (PipelineText.startswith("function(") || isFunctionPassName(FirstName)) { FunctionPassManager FPM(DebugLogging); if (!parseFunctionPassPipeline(FPM, PipelineText, VerifyEachPass, DebugLogging) || @@ -414,5 +522,19 @@ return true; } + // If this looks like a Loop pass, parse the whole thing as a Loop pipeline. + if (PipelineText.startswith("loop(") || isLoopPassName(FirstName)) { + LoopPassManager LPM(DebugLogging); + if (!parseLoopPassPipeline(LPM, PipelineText, VerifyEachPass, + DebugLogging) || + !PipelineText.empty()) + return false; + FunctionPassManager FPM(DebugLogging); + FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); + MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); + return true; + } + + return false; } Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -82,3 +82,17 @@ FUNCTION_PASS("verify", VerifierPass()) FUNCTION_PASS("verify", DominatorTreeVerifierPass()) #undef FUNCTION_PASS + +#ifndef LOOP_ANALYSIS +#define LOOP_ANALYSIS(NAME, CREATE_PASS) +#endif +LOOP_ANALYSIS("no-op-loop", NoOpLoopAnalysis()) +#undef LOOP_ANALYSIS + +#ifndef LOOP_PASS +#define LOOP_PASS(NAME, CREATE_PASS) +#endif +LOOP_PASS("invalidate", InvalidateAllAnalysesPass()) +LOOP_PASS("no-op-loop", NoOpLoopPass()) +LOOP_PASS("print", PrintLoopPass(dbgs())) +#undef LOOP_PASS Index: test/Other/loop-pass-ordering.ll =================================================================== --- /dev/null +++ test/Other/loop-pass-ordering.ll @@ -0,0 +1,35 @@ +; RUN: opt -disable-output -debug-pass-manager \ +; RUN: -passes='no-op-loop' %s 2>&1 \ +; RUN: | FileCheck %s + +; @f() +; / \ +; loop.0 loop.1 +; / \ \ +; loop.0.0 loop.0.1 loop.1.0 +; +; CHECK: Running pass: NoOpLoopPass on loop.1.0 +; CHECK: Running pass: NoOpLoopPass on loop.1 +; CHECK: Running pass: NoOpLoopPass on loop.0.0 +; CHECK: Running pass: NoOpLoopPass on loop.0.1 +; CHECK: Running pass: NoOpLoopPass on loop.0 +define void @f() { +entry: + br label %loop.0 +loop.0: + br i1 undef, label %loop.0.0, label %loop.1 +loop.0.0: + br i1 undef, label %loop.0.0, label %loop.0.1 +loop.0.1: + br i1 undef, label %loop.0.1, label %loop.0 +loop.1: + br i1 undef, label %loop.1, label %loop.1.bb1 +loop.1.bb1: + br i1 undef, label %loop.1, label %loop.1.bb2 +loop.1.bb2: + br i1 undef, label %end, label %loop.1.0 +loop.1.0: + br i1 undef, label %loop.1.0, label %loop.1 +end: + ret void +} Index: test/Other/pass-pipeline-parsing.ll =================================================================== --- test/Other/pass-pipeline-parsing.ll +++ test/Other/pass-pipeline-parsing.ll @@ -137,6 +137,46 @@ ; CHECK-NESTED-MP-CG-FP: Finished pass manager ; CHECK-NESTED-MP-CG-FP: Finished pass manager +; RUN: opt -disable-output -debug-pass-manager \ +; RUN: -passes='no-op-loop,no-op-loop' %s 2>&1 \ +; RUN: | FileCheck %s --check-prefix=CHECK-TWO-NOOP-LOOP +; CHECK-TWO-NOOP-LOOP: Starting pass manager +; CHECK-TWO-NOOP-LOOP: Running pass: ModuleToFunctionPassAdaptor +; CHECK-TWO-NOOP-LOOP: Starting pass manager +; CHECK-TWO-NOOP-LOOP: Running pass: FunctionToLoopPassAdaptor +; CHECK-TWO-NOOP-LOOP: Starting pass manager +; CHECK-TWO-NOOP-LOOP: Running pass: NoOpLoopPass +; CHECK-TWO-NOOP-LOOP: Running pass: NoOpLoopPass +; CHECK-TWO-NOOP-LOOP: Finished pass manager +; CHECK-TWO-NOOP-LOOP: Finished pass manager +; CHECK-TWO-NOOP-LOOP: Finished pass manager + +; RUN: opt -disable-output -debug-pass-manager \ +; RUN: -passes='module(function(loop(no-op-loop)))' %s 2>&1 \ +; RUN: | FileCheck %s --check-prefix=CHECK-NESTED-FP-LP +; RUN: opt -disable-output -debug-pass-manager \ +; RUN: -passes='function(loop(no-op-loop))' %s 2>&1 \ +; RUN: | FileCheck %s --check-prefix=CHECK-NESTED-FP-LP +; RUN: opt -disable-output -debug-pass-manager \ +; RUN: -passes='loop(no-op-loop)' %s 2>&1 \ +; RUN: | FileCheck %s --check-prefix=CHECK-NESTED-FP-LP +; RUN: opt -disable-output -debug-pass-manager \ +; RUN: -passes='no-op-loop' %s 2>&1 \ +; RUN: | FileCheck %s --check-prefix=CHECK-NESTED-FP-LP +; CHECK-NESTED-FP-LP: Starting pass manager +; CHECK-NESTED-FP-LP: Running pass: ModuleToFunctionPassAdaptor +; CHECK-NESTED-FP-LP: Starting pass manager +; CHECK-NESTED-FP-LP: Running pass: FunctionToLoopPassAdaptor +; CHECK-NESTED-FP-LP: Starting pass manager +; CHECK-NESTED-FP-LP: Running pass: NoOpLoopPass +; CHECK-NESTED-FP-LP: Finished pass manager +; CHECK-NESTED-FP-LP: Finished pass manager +; CHECK-NESTED-FP-LP: Finished pass manager + + define void @f() { - ret void +entry: + br label %loop +loop: + br label %loop } Index: tools/opt/NewPMDriver.cpp =================================================================== --- tools/opt/NewPMDriver.cpp +++ tools/opt/NewPMDriver.cpp @@ -16,6 +16,7 @@ #include "NewPMDriver.h" #include "llvm/ADT/StringRef.h" #include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/LoopPassManager.h" #include "llvm/Bitcode/BitcodeWriterPass.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/IRPrintingPasses.h" @@ -44,6 +45,7 @@ bool ShouldPreserveBitcodeUseListOrder) { PassBuilder PB(TM); + LoopAnalysisManager LAM(DebugPM); FunctionAnalysisManager FAM(DebugPM); CGSCCAnalysisManager CGAM(DebugPM); ModuleAnalysisManager MAM(DebugPM); @@ -52,6 +54,7 @@ PB.registerModuleAnalyses(MAM); PB.registerCGSCCAnalyses(CGAM); PB.registerFunctionAnalyses(FAM); + PB.registerLoopAnalyses(LAM); // Cross register the analysis managers through their proxies. MAM.registerPass(FunctionAnalysisManagerModuleProxy(FAM)); @@ -60,6 +63,8 @@ CGAM.registerPass(ModuleAnalysisManagerCGSCCProxy(MAM)); FAM.registerPass(CGSCCAnalysisManagerFunctionProxy(CGAM)); FAM.registerPass(ModuleAnalysisManagerFunctionProxy(MAM)); + FAM.registerPass(LoopAnalysisManagerFunctionProxy(LAM)); + LAM.registerPass(FunctionAnalysisManagerLoopProxy(FAM)); ModulePassManager MPM(DebugPM); if (VK > VK_NoVerifier) Index: unittests/Analysis/CMakeLists.txt =================================================================== --- unittests/Analysis/CMakeLists.txt +++ unittests/Analysis/CMakeLists.txt @@ -10,6 +10,7 @@ CallGraphTest.cpp CFGTest.cpp LazyCallGraphTest.cpp + LoopPassManagerTest.cpp ScalarEvolutionTest.cpp MixedTBAATest.cpp ValueTrackingTest.cpp Index: unittests/Analysis/LoopPassManagerTest.cpp =================================================================== --- /dev/null +++ unittests/Analysis/LoopPassManagerTest.cpp @@ -0,0 +1,256 @@ +//===- llvm/unittest/Analysis/LoopPassManagerTest.cpp - LPM tests ---------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "gtest/gtest.h" +#include "llvm/Analysis/LoopPassManager.h" +#include "llvm/AsmParser/Parser.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/PassManager.h" +#include "llvm/Support/SourceMgr.h" + +using namespace llvm; + +namespace { + +class TestLoopAnalysis { + /// \brief Private static data to provide unique ID. + static char PassID; + + int &Runs; + +public: + struct Result { + Result(int Count) : BlockCount(Count) {} + int BlockCount; + }; + + /// \brief Returns an opaque, unique ID for this pass type. + static void *ID() { return (void *)&PassID; } + + /// \brief Returns the name of the analysis. + static StringRef name() { return "TestLoopAnalysis"; } + + TestLoopAnalysis(int &Runs) : Runs(Runs) {} + + /// \brief Run the analysis pass over the loop and return a result. + Result run(Loop &L, AnalysisManager *AM) { + ++Runs; + int Count = 0; + + for (auto I = L.block_begin(), E = L.block_end(); I != E; ++I) + ++Count; + return Result(Count); + } +}; + +char TestLoopAnalysis::PassID; + +class TestLoopPass { + std::vector &VisitedLoops; + int &AnalyzedBlockCount; + bool OnlyUseCachedResults; + +public: + TestLoopPass(std::vector &VisitedLoops, int &AnalyzedBlockCount, + bool OnlyUseCachedResults = false) + : VisitedLoops(VisitedLoops), AnalyzedBlockCount(AnalyzedBlockCount), + OnlyUseCachedResults(OnlyUseCachedResults) {} + + PreservedAnalyses run(Loop &L, AnalysisManager *AM) { + VisitedLoops.push_back(L.getName()); + + if (OnlyUseCachedResults) { + // Hack to force the use of the cached interface. + if (auto *AR = AM->getCachedResult(L)) + AnalyzedBlockCount += AR->BlockCount; + } else { + // Typical path just runs the analysis as needed. + auto &AR = AM->getResult(L); + AnalyzedBlockCount += AR.BlockCount; + } + + return PreservedAnalyses::all(); + } + + static StringRef name() { return "TestLoopPass"; } +}; + +// A test loop pass that invalidates the analysis for loops with the given name. +class TestLoopInvalidatingPass { + StringRef Name; + +public: + TestLoopInvalidatingPass(StringRef LoopName) : Name(LoopName) {} + + PreservedAnalyses run(Loop &L, AnalysisManager *AM) { + return L.getName() == Name ? PreservedAnalyses::none() + : PreservedAnalyses::all(); + } + + static StringRef name() { return "TestLoopInvalidatingPass"; } +}; + + +// A test loop pass that deletes any loops with the given name. +class TestLoopDeletingPass { + StringRef Name; + +public: + TestLoopDeletingPass(StringRef LoopName) : Name(LoopName) {} + + PreservedAnalyses run(Loop &L, AnalysisManager *AM) { + if (L.getName() != Name) + return PreservedAnalyses::all(); + + auto &FAM = AM->getResult(L).getManager(); + + Function *F = L.getHeader()->getParent(); + auto *LI = FAM.getCachedResult(*F); + + LI->markAsRemoved(&L); + + PreservedAnalyses PA; + PA.preserve(); + PA.preserve(); + return PA; + } + + static StringRef name() { return "TestLoopDeletingPass"; } +}; + + +std::unique_ptr parseIR(const char *IR) { + LLVMContext &C = getGlobalContext(); + SMDiagnostic Err; + return parseAssemblyString(IR, Err, C); +} + +class LoopPassManagerTest : public ::testing::Test { +protected: + std::unique_ptr M; + +public: + LoopPassManagerTest() + : M(parseIR("define void @f() {\n" + "entry:\n" + " br label %loop.0\n" + "loop.0:\n" + " br i1 undef, label %loop.0.0, label %end\n" + "loop.0.0:\n" + " br i1 undef, label %loop.0.0, label %loop.0.1\n" + "loop.0.1:\n" + " br i1 undef, label %loop.0.1, label %loop.0\n" + "end:\n" + " ret void\n" + "}\n" + "\n" + "define void @g() {\n" + "entry:\n" + " br label %loop.g.0\n" + "loop.g.0:\n" + " br i1 undef, label %loop.g.0, label %end\n" + "end:\n" + " ret void\n" + "}\n")) {} +}; + +#define EXPECT_N_ELEMENTS_EQ(N, EXPECTED, ACTUAL) \ + do { \ + EXPECT_EQ(N##UL, ACTUAL.size()); \ + for (int I = 0; I < N; ++I) \ + EXPECT_TRUE(EXPECTED[I] == ACTUAL[I]) << "Element " << I << " is " \ + << ACTUAL[I] << ". Expected " \ + << EXPECTED[I] << "."; \ + } while (0) + +TEST_F(LoopPassManagerTest, Basic) { + LoopAnalysisManager LAM(true); + int LoopAnalysisRuns = 0; + LAM.registerPass(TestLoopAnalysis(LoopAnalysisRuns)); + + FunctionAnalysisManager FAM(true); + FAM.registerPass(DominatorTreeAnalysis()); // Needed by LoopAnalysis + FAM.registerPass(LoopAnalysis()); + FAM.registerPass(LoopAnalysisManagerFunctionProxy(LAM)); + LAM.registerPass(FunctionAnalysisManagerLoopProxy(FAM)); + + ModuleAnalysisManager MAM(true); + MAM.registerPass(FunctionAnalysisManagerModuleProxy(FAM)); + FAM.registerPass(ModuleAnalysisManagerFunctionProxy(MAM)); + + ModulePassManager MPM(true); + FunctionPassManager FPM(true); + + // Visit all of the loops. + std::vector VisitedLoops1; + int AnalyzedBlockCount1 = 0; + { + LoopPassManager LPM; + LPM.addPass(TestLoopPass(VisitedLoops1, AnalyzedBlockCount1)); + + FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); + } + + // Only use cached analyses. + std::vector VisitedLoops2; + int AnalyzedBlockCount2 = 0; + { + LoopPassManager LPM; + LPM.addPass(TestLoopInvalidatingPass("loop.g.0")); + LPM.addPass(TestLoopPass(VisitedLoops2, AnalyzedBlockCount2, + /*OnlyUseCachedResults=*/true)); + + FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); + } + + // Remove a Loop partway through our traversal. + std::vector VisitedLoops3; + int AnalyzedBlockCount3 = 0; + std::vector VisitedLoops4; + int AnalyzedBlockCount4 = 0; + { + LoopPassManager LPM; + LPM.addPass(TestLoopPass(VisitedLoops3, AnalyzedBlockCount3)); + LPM.addPass(TestLoopDeletingPass("loop.0.0")); + LPM.addPass(TestLoopPass(VisitedLoops4, AnalyzedBlockCount4)); + + FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); + } + + MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); + MPM.run(*M, &MAM); + + StringRef ExpectedLoops[] = {"loop.0.0", "loop.0.1", "loop.0", "loop.g.0"}; + + // Validate the counters and order of loops visited. + // loop.0 has 3 blocks whereas loop.0.0, loop.0.1, and loop.g.0 each have 1. + EXPECT_N_ELEMENTS_EQ(4, ExpectedLoops, VisitedLoops1); + EXPECT_EQ(6, AnalyzedBlockCount1); + + EXPECT_N_ELEMENTS_EQ(4, ExpectedLoops, VisitedLoops2); + // The block from loop.g.0 won't be counted, since it wasn't cached. + EXPECT_EQ(5, AnalyzedBlockCount2); + + // We recalculate the analysis for loop.g.0, so we visit everything again. + EXPECT_N_ELEMENTS_EQ(4, ExpectedLoops, VisitedLoops3); + EXPECT_EQ(6, AnalyzedBlockCount3); + // Now loop.0.0 has been removed, so it won't be visited at all. + StringRef ExpectedLoops3[] = {"loop.0.1", "loop.0", "loop.g.0"}; + EXPECT_N_ELEMENTS_EQ(3, ExpectedLoops3, VisitedLoops4); + EXPECT_EQ(5, AnalyzedBlockCount4); + + // The first LPM runs the loop analysis for all four loops, the second uses + // cached results for everything, and the last uses cached results for all but + // loop.g.0. + EXPECT_EQ(5, LoopAnalysisRuns); +} +}