[NewPM] Allow passes to never be skipped

[aeubanks]

Summary

PassInfoMixin now declares that passes inheriting from it are by default
optional. Using RequiredPassInfoMixin overrides the pass to be required.

All adaptors/managers must be required, since the pass(es) they are
wrapping may be required.

In the future, optnone, opt-bisect and llc -startr/-stop will use this mechanism to
determine which passes to skip.

This is an alternative to https://reviews.llvm.org/D82344.

[aeubanks]

Actually use isRequired() in PassInstrumentation::runBeforePass()

[aeubanks]

Add tests (taken from https://reviews.llvm.org/D82344, thanks ychen)

llvm/include/llvm/Analysis/CGSCCPassManager.h

 /// Designed to allow composition of a CGSCCPass(Manager) and
 /// a ModulePassManager. Note that this pass must be run with a module analysis
 /// manager as it uses the LazyCallGraph analysis. It will also run the
 /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
 /// pass over the module to enable a \c FunctionAnalysisManager to be used
 /// within this run safely.
 template <typename CGSCCPassT>
 class ModuleToPostOrderCGSCCPassAdaptor
-    : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> {
+    : public RequiredPassInfoMixin<
+          ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>> {
 public:
   explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass)
       : Pass(std::move(Pass)) {}
 
   // We have to explicitly define all the special member functions because MSVC
   // refuses to generate them.
   ModuleToPostOrderCGSCCPassAdaptor(
       const ModuleToPostOrderCGSCCPassAdaptor &Arg)

 /// Designed to allow composition of a FunctionPass(Manager) and
 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
 /// to a \c CGSCCAnalysisManager it will run the
 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
 /// within this run safely.
 template <typename FunctionPassT>
 class CGSCCToFunctionPassAdaptor
-    : public PassInfoMixin<CGSCCToFunctionPassAdaptor<FunctionPassT>> {
+    : public RequiredPassInfoMixin<CGSCCToFunctionPassAdaptor<FunctionPassT>> {
 public:
   explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
       : Pass(std::move(Pass)) {}
 
   // We have to explicitly define all the special member functions because MSVC
   // refuses to generate them.
   CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
       : Pass(Arg.Pass) {}

llvm/include/llvm/IR/PassInstrumentation.h

 ///      control to all the registered callbacks. Note that we specifically wrap
 ///      'const IRUnitT*' so as to avoid any accidental changes to IR in
 ///      instrumenting callbacks.
 ///
 ///    - Some instrumentation points (BeforePass) allow to control execution
 ///      of a pass. For those callbacks returning false means pass will not be
 ///      executed.
 ///
-/// TODO: currently there is no way for a pass to opt-out of execution control
-/// (e.g. become unskippable). PassManager is the only entity that determines
-/// how pass instrumentation affects pass execution.
-///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_PASSINSTRUMENTATION_H
 #define LLVM_IR_PASSINSTRUMENTATION_H
 
 #include "llvm/ADT/Any.h"
 #include "llvm/ADT/FunctionExtras.h"
 #include "llvm/ADT/SmallVector.h"
public:
   template <typename IRUnitT, typename PassT>
   bool runBeforePass(const PassT &Pass, const IRUnitT &IR) const {
     if (!Callbacks)
       return true;
 
     bool ShouldRun = true;
     for (auto &C : Callbacks->BeforePassCallbacks)
       ShouldRun &= C(Pass.name(), llvm::Any(&IR));
+    // Required passes should always be run.
+    ShouldRun |= Pass.isRequired();
     return ShouldRun;
   }
 
   /// AfterPass instrumentation point - takes \p Pass instance that has
   /// just been executed and constant reference to \p IR it operates on.
   /// \p IR is guaranteed to be valid at this point.
   template <typename IRUnitT, typename PassT>
   void runAfterPass(const PassT &Pass, const IRUnitT &IR) const {

llvm/include/llvm/IR/PassManager.h

 
 // Forward declare the analysis manager template.
 template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager;
 
 /// A CRTP mix-in to automatically provide informational APIs needed for
 /// passes.
 ///
 /// This provides some boilerplate for types that are passes.
+/// Use this for optional (usually optimization) passes.
 template <typename DerivedT> struct PassInfoMixin {
   /// Gets the name of the pass we are mixed into.
   static StringRef name() {
     static_assert(std::is_base_of<PassInfoMixin, DerivedT>::value,
                   "Must pass the derived type as the template argument!");
     StringRef Name = getTypeName<DerivedT>();
     if (Name.startswith("llvm::"))
       Name = Name.drop_front(strlen("llvm::"));
     return Name;
   }
+
+  /// This pass is not required to produce a valid executable.
+  /// Use RequiredPassInfoMixin for required passes.
+  static bool isRequired() { return false; }
+};
+
+/// A CRTP mix-in to automatically provide informational APIs needed for
+/// passes.
+///
+/// Use this for passes required to produce a valid executable.
+template <typename DerivedT>
+struct RequiredPassInfoMixin : PassInfoMixin<DerivedT> {
+  /// This pass is required to produce a valid executable.
+  static bool isRequired() { return true; }
 };
 
 /// A CRTP mix-in that provides informational APIs needed for analysis passes.
 ///
 /// This provides some boilerplate for types that are analysis passes. It
 /// automatically mixes in \c PassInfoMixin.
 template <typename DerivedT>
 struct AnalysisInfoMixin : PassInfoMixin<DerivedT> {

 ///
 /// When you run a pass manager, you provide an \c AnalysisManager<IRUnitT>
 /// argument. The pass manager will propagate that analysis manager to each
 /// pass it runs, and will call the analysis manager's invalidation routine with
 /// the PreservedAnalyses of each pass it runs.
 template <typename IRUnitT,
           typename AnalysisManagerT = AnalysisManager<IRUnitT>,
           typename... ExtraArgTs>
-class PassManager : public PassInfoMixin<
+class PassManager : public RequiredPassInfoMixin<
                         PassManager<IRUnitT, AnalysisManagerT, ExtraArgTs...>> {
 public:
   /// Construct a pass manager.
   ///
   /// If \p DebugLogging is true, we'll log our progress to llvm::dbgs().
   explicit PassManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {}
 
   // FIXME: These are equivalent to the default move constructor/move

 /// FIXME: Make the above true for all of LLVM's actual passes, some still
 /// violate this principle.
 ///
 /// Note that although function passes can access module analyses, module
 /// analyses are not invalidated while the function passes are running, so they
 /// may be stale.  Function analyses will not be stale.
 template <typename FunctionPassT>
 class ModuleToFunctionPassAdaptor
-    : public PassInfoMixin<ModuleToFunctionPassAdaptor<FunctionPassT>> {
+    : public RequiredPassInfoMixin<ModuleToFunctionPassAdaptor<FunctionPassT>> {
 public:
   explicit ModuleToFunctionPassAdaptor(FunctionPassT Pass)
       : Pass(std::move(Pass)) {}
 
   /// Runs the function pass across every function in the module.
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
     FunctionAnalysisManager &FAM =
         AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();

llvm/include/llvm/IR/PassManagerInternal.h

struct PassConcept {
   /// Note that actual pass object can omit the analysis manager argument if
   /// desired. Also that the analysis manager may be null if there is no
   /// analysis manager in the pass pipeline.
   virtual PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM,
                                 ExtraArgTs... ExtraArgs) = 0;
 
   /// Polymorphic method to access the name of a pass.
   virtual StringRef name() const = 0;
+
+  /// Whether or not this pass is required to create executable code.
+  ///
+  /// Used for optnone and opt-bisect.
+  virtual bool isRequired() const = 0;
 };
 
 /// A template wrapper used to implement the polymorphic API.
 ///
 /// Can be instantiated for any object which provides a \c run method accepting
 /// an \c IRUnitT& and an \c AnalysisManager<IRUnit>&. It requires the pass to
 /// be a copyable object.
 template <typename IRUnitT, typename PassT, typename PreservedAnalysesT,
struct PassModel : PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...> {
 
   PreservedAnalysesT run(IRUnitT &IR, AnalysisManagerT &AM,
                          ExtraArgTs... ExtraArgs) override {
     return Pass.run(IR, AM, ExtraArgs...);
   }
 
   StringRef name() const override { return PassT::name(); }
 
+  bool isRequired() const override { return PassT::isRequired(); }
+
   PassT Pass;
 };
 
 /// Abstract concept of an analysis result.
 ///
 /// This concept is parameterized over the IR unit that this result pertains
 /// to.
 template <typename IRUnitT, typename PreservedAnalysesT, typename InvalidatorT>

llvm/include/llvm/Transforms/Scalar/LoopPassManager.h

 ///
 /// 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 <typename LoopPassT>
 class FunctionToLoopPassAdaptor
-    : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> {
+    : public RequiredPassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> {
 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());
   }

llvm/unittests/IR/PassBuilderCallbacksTest.cpp

TEST_F(ModuleCallbacksTest, InstrumentedPasses) {
   PM.run(*M, AM);
 }
 
 TEST_F(ModuleCallbacksTest, InstrumentedSkippedPasses) {
   CallbacksHandle.registerPassInstrumentation();
   // Non-mock instrumentation run here can safely be ignored.
   CallbacksHandle.ignoreNonMockPassInstrumentation("<string>");
 
-  // Skip the pass by returning false.
-  EXPECT_CALL(CallbacksHandle, runBeforePass(HasNameRegex("MockPassHandle"),
-                                             HasName("<string>")))
-      .WillOnce(Return(false));
+  // Skip all passes by returning false. Pass managers and adaptor passes are
+  // also passes that observed by the callbacks.
+  EXPECT_CALL(CallbacksHandle, runBeforePass(_, _))
+      .WillRepeatedly(Return(false));
 
   EXPECT_CALL(AnalysisHandle, run(HasName("<string>"), _)).Times(0);
   EXPECT_CALL(PassHandle, run(HasName("<string>"), _)).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,
               runBeforeAnalysis(HasNameRegex("MockAnalysisHandle"), _))
       .Times(0);
   EXPECT_CALL(CallbacksHandle,
               runAfterAnalysis(HasNameRegex("MockAnalysisHandle"), _))
       .Times(0);
 
-  StringRef PipelineText = "test-transform";
+  // Order is important here. `Adaptor` expectations should be checked first
+  // because the its argument contains 'PassManager' (for example:
+  // ModuleToFunctionPassAdaptor{{.*}}PassManager{{.*}}). Here only check
+  // `runAfterPass` to show that they are not skipped.
+
+  // Pass managers are not ignored.
+  // 5 = (1) ModulePassManager + (2) FunctionPassMangers + (1) LoopPassManager +
+  //     (1) CGSCCPassManager
+  EXPECT_CALL(CallbacksHandle, runAfterPass(HasNameRegex("PassManager"), _))
+      .Times(5);
+  EXPECT_CALL(CallbacksHandle,
+              runAfterPass(HasNameRegex("ModuleToFunctionPassAdaptor"), _))
+      .Times(1);
+  EXPECT_CALL(
+      CallbacksHandle,
+      runAfterPass(HasNameRegex("ModuleToPostOrderCGSCCPassAdaptor"), _))
+      .Times(1);
+  EXPECT_CALL(CallbacksHandle,
+              runAfterPass(HasNameRegex("CGSCCToFunctionPassAdaptor"), _))
+      .Times(1);
+  EXPECT_CALL(CallbacksHandle,
+              runAfterPass(HasNameRegex("FunctionToLoopPassAdaptor"), _))
+      .Times(1);
+
+  // Ignore analyses introduced by adaptor passes.
+  EXPECT_CALL(CallbacksHandle,
+              runBeforeAnalysis(Not(HasNameRegex("MockAnalysisHandle")), _))
+      .Times(AnyNumber());
+  EXPECT_CALL(CallbacksHandle,
+              runAfterAnalysis(Not(HasNameRegex("MockAnalysisHandle")), _))
+      .Times(AnyNumber());
+
+  // Register Funtion and Loop version of "test-transform" for testing
+  PB.registerPipelineParsingCallback(
+      [](StringRef Name, FunctionPassManager &FPM,
+         ArrayRef<PassBuilder::PipelineElement>) {
+        if (Name == "test-transform") {
+          FPM.addPass(MockPassHandle<Function>().getPass());
+          return true;
+        }
+        return false;
+      });
+  PB.registerPipelineParsingCallback(
+      [](StringRef Name, LoopPassManager &LPM,
+         ArrayRef<PassBuilder::PipelineElement>) {
+        if (Name == "test-transform") {
+          LPM.addPass(MockPassHandle<Loop>().getPass());
+          return true;
+        }
+        return false;
+      });
+
+  StringRef PipelineText = "test-transform,function(test-transform),cgscc("
+                           "function(loop(test-transform)))";
   ASSERT_THAT_ERROR(PB.parsePassPipeline(PM, PipelineText, true), Succeeded())
       << "Pipeline was: " << PipelineText;
 
   PM.run(*M, AM);
 }
 
 TEST_F(FunctionCallbacksTest, Passes) {
   EXPECT_CALL(AnalysisHandle, run(HasName("foo"), _));

polly/include/polly/ScopPass.h

private:
   bool InvalidateCurrentScop;
   SmallPriorityWorklist<Region *, 4> &Worklist;
   ScopAnalysisManager &SAM;
   template <typename ScopPassT> friend class FunctionToScopPassAdaptor;
 };
 
 template <typename ScopPassT>
 class FunctionToScopPassAdaptor
-    : public PassInfoMixin<FunctionToScopPassAdaptor<ScopPassT>> {
+    : public RequiredPassInfoMixin<FunctionToScopPassAdaptor<ScopPassT>> {
 public:
   explicit FunctionToScopPassAdaptor(ScopPassT Pass) : Pass(std::move(Pass)) {}
 
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
     PreservedAnalyses PA = PreservedAnalyses::all();
     auto &SD = AM.getResult<ScopAnalysis>(F);
     auto &SI = AM.getResult<ScopInfoAnalysis>(F);
     if (SI.empty())