Enable opt-bisect for the new pass manager

[cuviper]

Summary

This instruments a should-run-optional-pass callback using the existing
OptBisect class to decide if new passes should be skipped. Passes that
force isRequired never reach this at all, so they are not included in
"BISECT:" output nor its pass count.

The test case is resurrected from r267022, an early version of D19172
that had new pass manager support (later reverted and redone without).

[aeubanks]

One of the issues raised in http://lists.llvm.org/pipermail/llvm-dev/2018-September/126477.html was that we'd have to somehow thread the -opt-bisect-limit through two different pass managers. If you look in BackendUtil.cpp's EmitAssemblyHelper::EmitAssemblyWithNewPassManager(), there's a NPM for the optimization pipeline, then a legacy PM for the codegen pipeline. OptBisect.rst says that you can use -opt-bisect-limit through clang -mllvm -opt-bisect-limit=, and I don't think that would properly work with this implementation since the codegen pipeline would restart -opt-bisect-limit.

I guess there aren't any tests for that though, since all references to -opt-bisect-limit are in llvm/test and use opt/llc.

llvm/lib/Passes/StandardInstrumentations.cpp

339–341

I don't think the NPM has a concept of a Region pass, so this shouldn't be necessary.

[cuviper]

Dropped Region from NPM opt-bisect

[cuviper]

Hmm, thanks for those pointers. To combine opt-bisect from the two pass managers, maybe there can be an explicit call to copy stateful instrumentation? I think it helps that they are not interleaved, so we could do MPM.run(), then somehow SI.copy_to(CodeGenPasses), then CodeGenPasses.run(). I still need to read that thread too...

LTOBackend may also need to deal with this, but I don't know if flags like opt-bisect apply there.

[aeubanks]

In D87951#2290564, @cuviper wrote:

Hmm, thanks for those pointers. To combine opt-bisect from the two pass managers, maybe there can be an explicit call to copy stateful instrumentation? I think it helps that they are not interleaved, so we could do MPM.run(), then somehow SI.copy_to(CodeGenPasses), then CodeGenPasses.run(). I still need to read that thread too...

Yeah that makes sense. Or maybe have some global counter, since this is mostly a debugging thing, although that seems fairly hacky.

LTOBackend may also need to deal with this, but I don't know if flags like opt-bisect apply there.

Not sure...
I suppose we can think about interactions with the legacy PM in a later patch, this on its own is an improvement.

Another issue is opt-bisect interacting with required passes. Currently it seems that it'll print out "NOT running pass ..." on a required pass but still run it.
PassInstrumentation::runBeforePass() will check all instrumentations to see if it should skip the pass, but still override that decision if the pass is required.
Before, I had wanted to let the callback know if the pass was required, but at that point just overriding the decision in runBeforePass() worked. The logging seems pretty important here for user understandability.
Thoughts?

llvm/include/llvm/Passes/StandardInstrumentations.h

73

remove?
(I deleted the default constructors above just now)

[aeubanks]

https://reviews.llvm.org/D90545 will make it so we don't even run this instrumentation on required passes, making it so we don't print "skipping pass" on a required pass. It also makes the opt-bisect counter not increment on passes that will run anyway, making it clearer what's going on. After that lands this should be good to go.

[cuviper]

Great, thanks for the update! I will rebase after that lands.

[aeubanks]

That has landed, we should probably amend the test to make sure that it doesn't print "BISECT: (NOT) running pass" for required passes, e.g. verify

[cuviper]

Rebase, and test that required VerifierPass is not bisected

[aeubanks]

Thanks for doing this!

[dmajor]

I'm very happy to see this land, thank you for writing it!

llvm/include/llvm/IR/OptBisect.h

public:
   ///
   /// Most passes should not call this routine directly. Instead, they are
   /// called through helper routines provided by the pass base classes.  For
   /// instance, function passes should call FunctionPass::skipFunction().
   bool shouldRunPass(const Pass *P, StringRef IRDescription) override;
 
   /// isEnabled should return true before calling shouldRunPass
   bool isEnabled() const override { return BisectEnabled; }
-private:
+
+protected:
   bool checkPass(const StringRef PassName, const StringRef TargetDesc);
 
+private:
   bool BisectEnabled = false;
   unsigned LastBisectNum = 0;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_IR_OPTBISECT_H

llvm/include/llvm/Passes/StandardInstrumentations.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_PASSES_STANDARDINSTRUMENTATIONS_H
 #define LLVM_PASSES_STANDARDINSTRUMENTATIONS_H
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/OptBisect.h"
 #include "llvm/IR/PassInstrumentation.h"
 #include "llvm/IR/PassTimingInfo.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/CommandLine.h"
 
 #include <string>
 #include <utility>
 

 public:
   OptNoneInstrumentation() {}
   void registerCallbacks(PassInstrumentationCallbacks &PIC);
 
 private:
   bool skip(StringRef PassID, Any IR);
 };
 
+class OptBisectInstrumentation : public OptBisect {
+public:
+  OptBisectInstrumentation() {}
+  void registerCallbacks(PassInstrumentationCallbacks &PIC);
+};
+
 // Debug logging for transformation and analysis passes.
 class PrintPassInstrumentation {
 public:
   PrintPassInstrumentation(bool DebugLogging) : DebugLogging(DebugLogging) {}
   void registerCallbacks(PassInstrumentationCallbacks &PIC);
 
 private:
   bool DebugLogging;

 
 /// This class provides an interface to register all the standard pass
 /// instrumentations and manages their state (if any).
 class StandardInstrumentations {
   PrintIRInstrumentation PrintIR;
   PrintPassInstrumentation PrintPass;
   TimePassesHandler TimePasses;
   OptNoneInstrumentation OptNone;
+  OptBisectInstrumentation OptBisect;
   PreservedCFGCheckerInstrumentation PreservedCFGChecker;
 
 public:
   StandardInstrumentations(bool DebugLogging) : PrintPass(DebugLogging) {}
 
   void registerCallbacks(PassInstrumentationCallbacks &PIC);
 
   TimePassesHandler &getTimePasses() { return TimePasses; }
 };
 } // namespace llvm
 
 #endif

llvm/lib/Passes/StandardInstrumentations.cpp

bool OptNoneInstrumentation::skip(StringRef PassID, Any IR) {
   if (any_isa<const Function *>(IR)) {
     F = any_cast<const Function *>(IR);
   } else if (any_isa<const Loop *>(IR)) {
     F = any_cast<const Loop *>(IR)->getHeader()->getParent();
   }
   return !(F && F->hasOptNone());
 }
 
+static std::string getBisectDescription(Any IR) {
+  if (any_isa<const Module *>(IR)) {
+    const Module *M = any_cast<const Module *>(IR);
+    assert(M && "module should be valid for printing");
+    return "module (" + M->getName().str() + ")";
+  }
+
+  if (any_isa<const Function *>(IR)) {
+    const Function *F = any_cast<const Function *>(IR);
+    assert(F && "function should be valid for printing");
+    return "function (" + F->getName().str() + ")";
+  }
+
+  if (any_isa<const LazyCallGraph::SCC *>(IR)) {
+    const LazyCallGraph::SCC *C = any_cast<const LazyCallGraph::SCC *>(IR);
+    assert(C && "scc should be valid for printing");
+    return "SCC " + C->getName();
+  }
+
+  if (any_isa<const Loop *>(IR)) {
+    return "loop";
+  }
+
+  llvm_unreachable("Unknown wrapped IR type");
+}
+
+void OptBisectInstrumentation::registerCallbacks(
+    PassInstrumentationCallbacks &PIC) {
+  if (!isEnabled())
+    return;
+
+  std::vector<StringRef> SpecialPasses = {"PassManager", "PassAdaptor"};
+
+  PIC.registerBeforePassCallback(
+      [this, SpecialPasses](StringRef PassID, Any IR) {
+        return isSpecialPass(PassID, SpecialPasses) ||
+               checkPass(PassID, getBisectDescription(IR));
+      });
+}
+
 void PrintPassInstrumentation::registerCallbacks(
     PassInstrumentationCallbacks &PIC) {
   if (!DebugLogging)
     return;
 
   std::vector<StringRef> SpecialPasses = {"PassManager"};
   if (!DebugPMVerbose)
     SpecialPasses.emplace_back("PassAdaptor");

 }
 
 void StandardInstrumentations::registerCallbacks(
     PassInstrumentationCallbacks &PIC) {
   PrintIR.registerCallbacks(PIC);
   PrintPass.registerCallbacks(PIC);
   TimePasses.registerCallbacks(PIC);
   OptNone.registerCallbacks(PIC);
+  OptBisect.registerCallbacks(PIC);
   PreservedCFGChecker.registerCallbacks(PIC);
 }

llvm/test/Other/opt-bisect-new-pass-manager.ll

+; This file verifies the behavior of the OptBisect class, which is used to
+; diagnose optimization related failures.  The tests check various
+; invocations that result in different sets of optimization passes that
+; are run in different ways.
+;
+; Because the exact set of optimizations that will be run is expected to
+; change over time, the checks for disabling passes are written in a
+; conservative way that avoids assumptions about which specific passes
+; will be disabled.
+
+; RUN: opt -disable-output -disable-verify \
+; RUN:     -passes=inferattrs -opt-bisect-limit=-1 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-MODULE-PASS
+; CHECK-MODULE-PASS: BISECT: running pass (1) InferFunctionAttrsPass on module
+
+; RUN: opt -disable-output -disable-verify \
+; RUN:     -passes=inferattrs -opt-bisect-limit=0 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-LIMIT-MODULE-PASS
+; CHECK-LIMIT-MODULE-PASS: BISECT: NOT running pass (1) InferFunctionAttrsPass on module
+
+; RUN: opt -disable-output -disable-verify \
+; RUN:     -passes=early-cse -opt-bisect-limit=-1 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-FUNCTION-PASS
+; CHECK-FUNCTION-PASS: BISECT: running pass (1) EarlyCSEPass on function (f1)
+; CHECK-FUNCTION-PASS: BISECT: running pass (2) EarlyCSEPass on function (f2)
+; CHECK-FUNCTION-PASS: BISECT: running pass (3) EarlyCSEPass on function (f3)
+
+; RUN: opt -disable-output -disable-verify \
+; RUN:     -passes=early-cse -opt-bisect-limit=2 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-LIMIT-FUNCTION-PASS
+; CHECK-LIMIT-FUNCTION-PASS: BISECT: running pass (1) EarlyCSEPass on function (f1)
+; CHECK-LIMIT-FUNCTION-PASS: BISECT: running pass (2) EarlyCSEPass on function (f2)
+; CHECK-LIMIT-FUNCTION-PASS: BISECT: NOT running pass (3) EarlyCSEPass on function (f3)
+
+; RUN: opt -disable-output -disable-verify \
+; RUN:     -passes=function-attrs -opt-bisect-limit=-1 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-CGSCC-PASS
+; CHECK-CGSCC-PASS: BISECT: running pass (1) PostOrderFunctionAttrsPass on SCC (f4)
+; CHECK-CGSCC-PASS: BISECT: running pass (2) PostOrderFunctionAttrsPass on SCC (f2)
+; CHECK-CGSCC-PASS: BISECT: running pass (3) PostOrderFunctionAttrsPass on SCC (f3)
+; CHECK-CGSCC-PASS: BISECT: running pass (4) PostOrderFunctionAttrsPass on SCC (f1)
+
+; RUN: opt -disable-output -disable-verify \
+; RUN:     -passes=function-attrs -opt-bisect-limit=3 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-LIMIT-CGSCC-PASS
+; CHECK-LIMIT-CGSCC-PASS: BISECT: running pass (1) PostOrderFunctionAttrsPass on SCC (f4)
+; CHECK-LIMIT-CGSCC-PASS: BISECT: running pass (2) PostOrderFunctionAttrsPass on SCC (f2)
+; CHECK-LIMIT-CGSCC-PASS: BISECT: running pass (3) PostOrderFunctionAttrsPass on SCC (f3)
+; CHECK-LIMIT-CGSCC-PASS: BISECT: NOT running pass (4) PostOrderFunctionAttrsPass on SCC (f1)
+
+; RUN: opt -disable-output -disable-verify -opt-bisect-limit=-1 \
+; RUN:     -passes='inferattrs,cgscc(function-attrs,function(early-cse))' %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-MULTI-PASS
+; CHECK-MULTI-PASS: BISECT: running pass (1) InferFunctionAttrsPass on module
+; CHECK-MULTI-PASS: BISECT: running pass (2) PostOrderFunctionAttrsPass on SCC (f4)
+; CHECK-MULTI-PASS: BISECT: running pass (3) EarlyCSEPass on function (f4)
+; CHECK-MULTI-PASS: BISECT: running pass (4) PostOrderFunctionAttrsPass on SCC (f2)
+; CHECK-MULTI-PASS: BISECT: running pass (5) EarlyCSEPass on function (f2)
+; CHECK-MULTI-PASS: BISECT: running pass (6) PostOrderFunctionAttrsPass on SCC (f3)
+; CHECK-MULTI-PASS: BISECT: running pass (7) EarlyCSEPass on function (f3)
+; CHECK-MULTI-PASS: BISECT: running pass (8) PostOrderFunctionAttrsPass on SCC (f1)
+; CHECK-MULTI-PASS: BISECT: running pass (9) EarlyCSEPass on function (f1)
+
+; RUN: opt -disable-output -disable-verify -opt-bisect-limit=7 \
+; RUN:     -passes='inferattrs,cgscc(function-attrs,function(early-cse))' %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-LIMIT-MULTI-PASS
+; CHECK-LIMIT-MULTI-PASS: BISECT: running pass (1) InferFunctionAttrsPass on module
+; CHECK-LIMIT-MULTI-PASS: BISECT: running pass (2) PostOrderFunctionAttrsPass on SCC (f4)
+; CHECK-LIMIT-MULTI-PASS: BISECT: running pass (3) EarlyCSEPass on function (f4)
+; CHECK-LIMIT-MULTI-PASS: BISECT: running pass (4) PostOrderFunctionAttrsPass on SCC (f2)
+; CHECK-LIMIT-MULTI-PASS: BISECT: running pass (5) EarlyCSEPass on function (f2)
+; CHECK-LIMIT-MULTI-PASS: BISECT: running pass (6) PostOrderFunctionAttrsPass on SCC (f3)
+; CHECK-LIMIT-MULTI-PASS: BISECT: running pass (7) EarlyCSEPass on function (f3)
+; CHECK-LIMIT-MULTI-PASS: BISECT: NOT running pass (8) PostOrderFunctionAttrsPass on SCC (f1)
+; CHECK-LIMIT-MULTI-PASS: BISECT: NOT running pass (9) EarlyCSEPass on function (f1)
+
+
+declare i32 @g()
+
+define void @f1() {
+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
+}
+
+define i32 @f2() {
+entry:
+  ret i32 0
+}
+
+define i32 @f3() {
+entry:
+  %temp = call i32 @g()
+  %icmp = icmp ugt i32 %temp, 2
+  br i1 %icmp, label %bb.true, label %bb.false
+bb.true:
+  %temp2 = call i32 @f2()
+  ret i32 %temp2
+bb.false:
+  ret i32 0
+}
+
+; This function is here to verify that opt-bisect can skip all passes for
+; functions that contain lifetime intrinsics.
+define void @f4() {
+entry:
+  %i = alloca i32, align 4
+  %tmp = bitcast i32* %i to i8*
+  call void @llvm.lifetime.start(i64 4, i8* %tmp)
+  br label %for.cond
+
+for.cond:
+  br i1 undef, label %for.body, label %for.end
+
+for.body:
+  br label %for.cond
+
+for.end:
+  ret void
+}
+
+declare void @llvm.lifetime.start(i64, i8* nocapture)