[NewPM] Allow passes to never be skipped

[ychen]

Summary

A pass declares itself unskippable by defining a method static bool isRequired().

Also, this patch makes pass managers and adaptor passes required (unskippable).

PassInstrumentation before-pass-callbacks could be used to skip passes by returning false.
However, some passes should not be skipped at all. Especially so for special-purpose passes such as pass managers and adaptor passes since if they are skipped for any reason, the passes contained by them would also be skipped ignoring contained passes's return value of isRequired().

[ychen]

• Update

[ychen]

llvm/include/llvm/IR/PassManagerInternal.h

106

Using ifdef may not work, I will fix this.

[ychen]

• Simplify by letting pass optionally implement static bool isSkippable(). This also make the skipping logic internal to PassInstrumentation, no change is needed in PassManger itself for the sake of performing skipping.
• All the implementation are through the type-erased API. The type traits in PassInstrumentation is for handling cases where adaptor passes instantiated for regular passes.

[ychen]

By Eric's suggestion, I'll add a test case to make the intent more clear.

[ychen]

• Add test. The test covers all changes except when a user pass is wrapped

in a adaptor pass directly(without nested pass manager). So part of the type
traits in PassInstrumentation.h is not tested. The reason is PassInstrumentation
unit tests are relying on parsePassPipeline which could not parse adaptor-wrapped user passes.
See D82698.

[ychen]

• Seems this could clear the TODO in PassInstrumentation.cpp (provided this implementation is in favor.)

[aeubanks]

I think I prefer https://reviews.llvm.org/D83575 over this, this uses too much template metaprogramming for my liking. WDYT?

llvm/include/llvm/Analysis/CGSCCPassManager.h

359

This is saying that only a ModuleToPostOrderCGSCCPassAdaptor around a CGSCCPassManager isn't skippable, all other ModuleToPostOrderCGSCCPassAdaptor are? What about a wrapper around a normal CGSCC pass that isn't skippable?

[ychen]

In D82344#2144872, @aeubanks wrote:

I think I prefer https://reviews.llvm.org/D83575 over this, this uses too much template metaprogramming for my liking. WDYT?

I'm happy if either this or D83575 are landed and slightly in favor of this. The difference between this and D83575 is that if we want the pass to implement an extra require method all the time. I choose not too because I think it is less pervasive and I imagine the use cases for require are limited. I'm kind of want to hide this detail from most pass developers so they don't need to worry about this in most cases. The template stuff is used so we don't mandate a require method all the time and the templates could be simplified using is_detected.

Other than the points I made I think it is perfectly reasonable to pursue D83575. For one thing, I'd prefer require over skippable. And it requires less code diff FWIW.

Anyway since we're authors of the alternatives and I'm probably biased. It would be a good thing to solicit other opinions. Thoughts?

llvm/include/llvm/Analysis/CGSCCPassManager.h

359

What about a wrapper around a normal CGSCC pass that isn't skippable?

Good point! I was not considering the case of normal passes declaring require. I think it should return false unconditionally here to mean the adaptor itself is always required.

[aeubanks]

In D82344#2145031, @ychen wrote:

In D82344#2144872, @aeubanks wrote:

I think I prefer https://reviews.llvm.org/D83575 over this, this uses too much template metaprogramming for my liking. WDYT?

I'm happy if either this or D83575 are landed and slightly in favor of this. The difference between this and D83575 is that if we want the pass to implement an extra require method all the time. I choose not too because I think it is less pervasive and I imagine the use cases for require are limited. I'm kind of want to hide this detail from most pass developers so they don't need to worry about this in most cases. The template stuff is used so we don't mandate a require method all the time and the templates could be simplified using is_detected.

Other than the points I made I think it is perfectly reasonable to pursue D83575. For one thing, I'd prefer require over skippable. And it requires less code diff FWIW.

Anyway since we're authors of the alternatives and I'm probably biased. It would be a good thing to solicit other opinions. Thoughts?

Alina, Hans, any preference between these two?

[asbirlea]

I'm inclined to favor having the isRequired() method optional with the SFINAE in this patch.
It's up to you two which patch to actually keep, but I'd say update this patch, with renaming to isRequired() (and flipping the bool value), adding the default to true in isRequired() for all adaptors and if, as you mentioned the diff can be simplified, great, but if not, this one makes sense.

[aeubanks]

Alright let's go with this one then, with skippable -> required.

llvm/include/llvm/Analysis/CGSCCPassManager.h

359

Maybe we can just return whether or not the CGSSC pass is skippable? If that's doable. That's a small optimization.

[ychen]

• skippable -> isRequired
• simplify SFINAE with is_detected

[ychen]

• 'required' to 'isRequired' in PassInstrumentation.h

[aeubanks]

lgtm, thanks!

[ychen]

• fix a typo in comment

[ebrevnov]

This change causes problems to us. Even though "enable-npm-optnone" is false by default it affects us because we use custom pass instrumentation callback which causes passes to be skipped under some conditions.

Here is a short reproducer for the problem:

opt -enable-new-pm -enable-npm-optnone -passes=licm test.ll
cat test.ll

define i32 @test1(i32 %a) #0 {
entry:

br label %body

body:

%i.0 = phi i32 [ 0, %entry ], [ %inc, %body ]
%inc = add nsw i32 %i.0, 1
%cmp = icmp slt i32 %i.0, %a
br i1 %cmp, label %body, label %end

end:

ret i32 %inc

}

attributes #0 = { optnone noinline }

It fails with assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) && "Loops must remain in LCSSA form!") at FunctionToLoopPassAdaptor::run:311. The problem here is that LoopSimplify and LCSAA passes of LoopCanonicalizationFPM was skipped and we hit the assert. Interestingly, even if I move "if (!PI.runBeforePass<Loop>(Pass, *L)) continue;" from line 318 to be above the assert we still hit this assert. That happens because loop pass is PassManager itself and is not skipped. One possible solution which comes to my mind would be to run LCSSA verification pass by means of pass manger so it would be skipped by the same mechanism.

[ychen]

In D82344#2184414, @ebrevnov wrote:

This change causes problems to us. Even though "enable-npm-optnone" is false by default it affects us because we use custom pass instrumentation callback which causes passes to be skipped under some conditions.

Here is a short reproducer for the problem:

opt -enable-new-pm -enable-npm-optnone -passes=licm test.ll
cat test.ll

define i32 @test1(i32 %a) #0 {
entry:

br label %body

body:

%i.0 = phi i32 [ 0, %entry ], [ %inc, %body ]
%inc = add nsw i32 %i.0, 1
%cmp = icmp slt i32 %i.0, %a
br i1 %cmp, label %body, label %end

end:

ret i32 %inc

}

attributes #0 = { optnone noinline }

It fails with assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) && "Loops must remain in LCSSA form!") at FunctionToLoopPassAdaptor::run:311. The problem here is that LoopSimplify and LCSAA passes of LoopCanonicalizationFPM was skipped and we hit the assert. Interestingly, even if I move "if (!PI.runBeforePass<Loop>(Pass, *L)) continue;" from line 318 to be above the assert we still hit this assert. That happens because loop pass is PassManager itself and is not skipped. One possible solution which comes to my mind would be to run LCSSA verification pass by means of pass manger so it would be skipped by the same mechanism.

Thanks. Confirmed. Considering it is a debugging feature like pass logging, I think I'm going to add another BeforeNonSkipped callback (D84774) to run this since it is probably useful to verify other IR unit before/after a real pass in the future.

[aeubanks]

In D82344#2185182, @ychen wrote:

In D82344#2184414, @ebrevnov wrote:

This change causes problems to us. Even though "enable-npm-optnone" is false by default it affects us because we use custom pass instrumentation callback which causes passes to be skipped under some conditions.

Here is a short reproducer for the problem:

opt -enable-new-pm -enable-npm-optnone -passes=licm test.ll
cat test.ll

define i32 @test1(i32 %a) #0 {
entry:

br label %body

body:

%i.0 = phi i32 [ 0, %entry ], [ %inc, %body ]
%inc = add nsw i32 %i.0, 1
%cmp = icmp slt i32 %i.0, %a
br i1 %cmp, label %body, label %end

end:

ret i32 %inc

}

attributes #0 = { optnone noinline }

It fails with assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) && "Loops must remain in LCSSA form!") at FunctionToLoopPassAdaptor::run:311. The problem here is that LoopSimplify and LCSAA passes of LoopCanonicalizationFPM was skipped and we hit the assert. Interestingly, even if I move "if (!PI.runBeforePass<Loop>(Pass, *L)) continue;" from line 318 to be above the assert we still hit this assert. That happens because loop pass is PassManager itself and is not skipped. One possible solution which comes to my mind would be to run LCSSA verification pass by means of pass manger so it would be skipped by the same mechanism.

Thanks. Confirmed. Considering it is a debugging feature like pass logging, I think I'm going to add another BeforeNonSkipped callback (D84774) to run this since it is probably useful to verify other IR unit before/after a real pass in the future.

+1, thanks!

llvm/include/llvm/Analysis/CGSCCPassManager.h

public:
   operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
     swap(*this, RHS);
     return *this;
   }
 
   /// Runs the CGSCC pass across every SCC in the module.
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 
+  static bool isSkippable() {
+    return !std::is_base_of<CGSCCPassT, CGSCCPassManager>::value;
+  }
+
 private:
   CGSCCPassT Pass;
 };
 
 /// A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename CGSCCPassT>
 ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
 
     // We've also ensured that we updated the call graph along the way.
     PA.preserve<LazyCallGraphAnalysis>();
 
     return PA;
   }
 
+  static bool isSkippable() {
+    return !std::is_base_of<FunctionPassT, FunctionPassManager>::value;
+  }
+
 private:
   FunctionPassT Pass;
 };
 
 /// A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename FunctionPassT>
 CGSCCToFunctionPassAdaptor<FunctionPassT>

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"
private:
   SmallVector<llvm::unique_function<AfterPassInvalidatedFunc>, 4>
       AfterPassInvalidatedCallbacks;
   SmallVector<llvm::unique_function<BeforeAnalysisFunc>, 4>
       BeforeAnalysisCallbacks;
   SmallVector<llvm::unique_function<AfterAnalysisFunc>, 4>
       AfterAnalysisCallbacks;
 };
 
+// Template argument PassT of PassInstrumentation::runBeforePass could be two
+// kinds: (1) a regular pass inherited from PassInfoMixin (happen when creating
+// a adaptor pass for a regular pass); (2) a type-erased PassConcept created
+// from (1). Here we want to make case (1) skippable unconditionally since they
+// are regular passes. We call PassConcept::isSkippable to decide for case (2).
+template <typename C> struct MaybeSkippablePass {
+private:
+  template <typename T>
+  static constexpr auto check(T *) ->
+      typename std::is_same<decltype(std::declval<T>().isSkippable()),
+                            bool>::type;
+  template <typename> static constexpr std::false_type check(...);
+
+  typedef decltype(check<C>(0)) type;
+
+public:
+  static constexpr bool value = type::value;
+};
+
 /// This class provides instrumentation entry points for the Pass Manager,
 /// doing calls to callbacks registered in PassInstrumentationCallbacks.
 class PassInstrumentation {
   PassInstrumentationCallbacks *Callbacks;
 
+  template <typename PassT>
+  static std::enable_if_t<MaybeSkippablePass<PassT>::value, bool>
+  isSkippable(const PassT &Pass) {
+    return Pass.isSkippable();
+  }
+  template <typename PassT>
+  static std::enable_if_t<!MaybeSkippablePass<PassT>::value, bool>
+  isSkippable(const PassT &Pass) {
+    return true;
+  }
+
 public:
   /// Callbacks object is not owned by PassInstrumentation, its life-time
   /// should at least match the life-time of corresponding
   /// PassInstrumentationAnalysis (which usually is till the end of current
   /// compilation).
   PassInstrumentation(PassInstrumentationCallbacks *CB = nullptr)
       : Callbacks(CB) {}
 
   /// BeforePass instrumentation point - takes \p Pass instance to be executed
   /// and constant reference to IR it operates on. \Returns true if pass is
   /// allowed to be executed.
   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));
+    ShouldRun = ShouldRun || !isSkippable(Pass);
     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

public:
   template <typename PassT> void addPass(PassT Pass) {
     using PassModelT =
         detail::PassModel<IRUnitT, PassT, PreservedAnalyses, AnalysisManagerT,
                           ExtraArgTs...>;
 
     Passes.emplace_back(new PassModelT(std::move(Pass)));
   }
 
+  static bool isSkippable() { return false; }
+
 private:
   using PassConceptT =
       detail::PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...>;
 
   std::vector<std::unique_ptr<PassConceptT>> Passes;
 
   /// Flag indicating whether we should do debug logging.
   bool DebugLogging;
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
     //
     // We also preserve all analyses on Functions, because we did all the
     // invalidation we needed to do above.
     PA.preserveSet<AllAnalysesOn<Function>>();
     PA.preserve<FunctionAnalysisManagerModuleProxy>();
     return PA;
   }
 
+  static bool isSkippable() {
+    return !std::is_base_of<FunctionPassT, FunctionPassManager>::value;
+  }
+
 private:
   FunctionPassT Pass;
 };
 
 /// A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename FunctionPassT>
 ModuleToFunctionPassAdaptor<FunctionPassT>

llvm/include/llvm/IR/PassManagerInternal.h

 
 template <typename IRUnitT> class AllAnalysesOn;
 template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager;
 class PreservedAnalyses;
 
 /// Implementation details of the pass manager interfaces.
 namespace detail {
 
+template <typename C> struct PassHasSkippableMethod {
+private:
+  template <typename T>
+  static constexpr auto check(T *) ->
+      typename std::is_same<decltype(T::isSkippable()), bool>::type;
+
+  template <typename> static constexpr std::false_type check(...);
+
+  typedef decltype(check<C>(0)) type;
+
+public:
+  static constexpr bool value = type::value;
+};
+
 /// Template for the abstract base class used to dispatch
 /// polymorphically over pass objects.
 template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs>
 struct PassConcept {
   // Boiler plate necessary for the container of derived classes.
   virtual ~PassConcept() = default;
 
   /// The polymorphic API which runs the pass over a given IR entity.
   ///
   /// 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;
+
+  /// Polymorphic method to to let a pass optionally exempted from skipping by
+  /// PassInstrumentation.
+  /// To opt-in, pass should implement `static bool isSkippable()`. It's no-op
+  /// to have `isSkippable` always return true since that is the default.
+  virtual bool isSkippable() 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(); }
 
+  template <typename T>
+  static std::enable_if_t<PassHasSkippableMethod<T>::value, bool>
+  passIsSkippable() {
+    return T::isSkippable();
+  }
+  template <typename T>
+  static std::enable_if_t<!PassHasSkippableMethod<T>::value, bool>
+  passIsSkippable() {
+    return true;
+  }
+
+  bool isSkippable() const override { return passIsSkippable<PassT>(); }
+
   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

#endif
     // that concept doesn't exist yet.
     PA.preserve<AAManager>();
     PA.preserve<BasicAA>();
     PA.preserve<GlobalsAA>();
     PA.preserve<SCEVAA>();
     return PA;
   }
 
+  static bool isSkippable() {
+    return !std::is_base_of<LoopPassT, LoopPassManager>::value;
+  }
+
 private:
   LoopPassT Pass;
 
   FunctionPassManager LoopCanonicalizationFPM;
 
   bool UseMemorySSA = false;
 };
 

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"), _));