Initial implementation of optimization bisect

[andrew.w.kaylor]

Summary

This patch implements a new class that can be used to allow optimizations to be selectively disabled at compile time in response to a command line option. This will allow a binary search for optimization related failures to be performed directly from LLVM-based front end invocations without otherwise changing the compiler's behavior.

I still need to create some sort of test for this code, but I wanted to begin the review process first to see if I could get consensus on this general approach.

The behavior is fairly straightforward. Any time a pass manager is about to run an optimization, it checks with the OptBisect helper object to see whether or not the pass should be run. The OptBisect tool maintains a simple count of the number of optimizations that have been run and returns false once the specified limit is reached. I am also providing (but not currently using) a function that optimization passes can use to opt in for a finer grained control of individual optimizations.

I am making two choices that require discussion. First, I am currently allowing all analysis passes (at least with the legacy pass manager) regardless of the optimization count. My reasoning is that any given analysis pass may be needed for some later pass that cannot be skipped (register allocation passes, for instance) and so running all analysis passes avoids the problem of anticipating such dependencies. I am not currently attempting this with the new pass manager as I haven't yet found a clean and simple way to identify passes as analysis passes at the level at which I am hooking in to the control flow.

Second, because the intention is that a front end will be able to produce object files while using the bisecting feature, certain passes may not be skipped. I am currently handling this in a very clumsy and fragile way by maintaining a hard-coded list of passes which must not be skipped. I hope that a better solution can be implemented and that the current approach will be short-lived (perhaps not even surviving the review process). My list is almost certainly incomplete and may also be overly conservative. I generated the list using x86 targets. Additional passes will need to be added for other target architectures.

[probinson]

Hmmm. When we first did the 'optnone' attribute, we designed in a feature where each pass would identify itself as skippable or not, and the pass manager would run only non-skippable passes on an 'optnone' function.

Chandler was adamant that we NOT do it this way, that the pass manager should remain ignorant of this sort of trickery and each individual pass would need to decide for itself whether 'optnone' was something to pay attention to. So, you now find at the top of a good many passes, a quick check to bail out early for 'optnone' functions. The fiddly bits are all factored out into a base class method, but each pass has to have a two-liner at the top of its Run method to (ahem) opt-in to optnone.

This feels morally equivalent, and I think this mechanism and 'optnone' ought to behave in similar ways.
So, rather than a list of passes that are allowed to run regardless of the bisection state, you'd have each individual pass opt-in to participating in bisection.
It makes for a lot of cut-and-paste across the Transform passes, but that's the existing practice.

[andrew.w.kaylor]

I definitely agree that the pass manager, and by extension the OptBisect class, shouldn't know anything about the passes.

I'd like to have some mechanism to ask the pass (or its pass registry entry) if it can be skipped. That would be pretty trivial to fit into the legacy pass manager interface with a default response (I think it should default to skippable, but we can debate that). I suppose a conceptually similar thing could be done with the new pass manager, but it feels more forced in that case in as much as it is one more bit of interface imposed on the pass concept.

The one thing I'm sure of is that the way I'm currently doing it is wrong.

[MatzeB]

In D18576#386421, @andrew.w.kaylor wrote:

I definitely agree that the pass manager, and by extension the OptBisect class, shouldn't know anything about the passes.

I'd like to have some mechanism to ask the pass (or its pass registry entry) if it can be skipped. That would be pretty trivial to fit into the legacy pass manager interface with a default response (I think it should default to skippable, but we can debate that). I suppose a conceptually similar thing could be done with the new pass manager, but it feels more forced in that case in as much as it is one more bit of interface imposed on the pass concept.

The one thing I'm sure of is that the way I'm currently doing it is wrong.

Maybe the passes that should be skipped for optnone functions are the same passes that can be disabled by OptBisect? Which would mean we could design a common helper functions for both replacing all the optnone checks with it.

[probinson]

In D18576#386425, @MatzeB wrote:

Maybe the passes that should be skipped for optnone functions are the same passes that can be disabled by OptBisect? Which would mean we could design a common helper functions for both replacing all the optnone checks with it.

I'd naively expect that the set of passes that should pay attention to optnone and bisection would be the same, and a common mechanism could work. But I'm not an optimizer person, by any stretch of the imagination.

[andrew.w.kaylor]

One difference I see is that "optnone" is an attribute within the IR and so the pass manager shouldn't be looking for it (maybe that's the "trickery" that Chandler didn't want the pass manager to be in on?) whereas the OptBisect class exists for the sole purpose of deciding to skip optimizations, and so it necessarily (maybe) needs to be aware that there are some passes that can't be skipped.

The obvious alternative is to not have the pass manager involved in any of this and put the shouldRunPass() check directly into the passes themselves. I was trying to avoid having to change a lot of different places to get this working, but that feels a bit more natural and it matches what's going to have to happen to skip individual optimizations.

[mzolotukhin]

Hi,

I don't think optnone-aware passes and the passes we might want to bisect are the same. Even with optnone we probably want to run some very trivial optimizations (e.g. ConstantProp), and I think bisection should cover those too.

Michael

PS: Thanks for doing this, I'm really excited about this feature!

[MatzeB]

In D18576#386443, @andrew.w.kaylor wrote:

One difference I see is that "optnone" is an attribute within the IR and so the pass manager shouldn't be looking for it (maybe that's the "trickery" that Chandler didn't want the pass manager to be in on?) whereas the OptBisect class exists for the sole purpose of deciding to skip optimizations, and so it necessarily (maybe) needs to be aware that there are some passes that can't be skipped.

The obvious alternative is to not have the pass manager involved in any of this and put the shouldRunPass() check directly into the passes themselves. I was trying to avoid having to change a lot of different places to get this working, but that feels a bit more natural and it matches what's going to have to happen to skip individual optimizations.

Maintaining a list of necessary passes in the pass manager sounds wrong to me. The pass author should know best whether a pass is necessary and it would be naturally to specify it together with the pass instead of in a separate file. It also works better for out-of-tree targets or passes loaded as plugins.

[mehdi_amini]

lib/IR/OptBisect.cpp

119

Ew, that's pretty terrible to have this inlined here. But I agree it is not easy to decouple...
Maybe having a new (optional?) API on the Passes themselves may be cleaner.
Something like bool isRequiredForCorrectness()?

[andrew.w.kaylor]

In D18576#386453, @MatzeB wrote:

Maintaining a list of necessary passes in the pass manager sounds wrong to me. The pass author should know best whether a pass is necessary and it would be naturally to specify it together with the pass instead of in a separate file. It also works better for out-of-tree targets or passes loaded as plugins.

Agreed. In spite of that being the code I submitted for review, I really don't want to do it that way. I just wanted to have something functional while searching for a better solution.

The two options I see are:

1. Have the pass managers invoke the "shouldRunPass" check and implement some way for OptBisect to query a pass to see if it is skippable.
2. Have every pass that is skippable make a shouldRunPass call at each skippable level.

I like the first option because it "automatically" provides the capability to skip passes unless the pass author explicitly does something to indicate that the pass shouldn't be skipped, but I like the second option because it gives each pass the ability to determine the granularity at which things can be skipped.

[probinson]

In D18576#386451, @mzolotukhin wrote:

I don't think optnone-aware passes and the passes we might want to bisect are the same. Even with optnone we probably want to run some very trivial optimizations (e.g. ConstantProp), and I think bisection should cover those too.

optnone tries to be as much like -O0 as it can, and I'd think that after you get to the end of the bisection range you'd want to be as much like -O0 as you can. FWIW I'm not seeing ConstantProp run at -O0.

[andrew.w.kaylor]

Updated the means of determining whether or not a pass is can be skipped -- I added a new function (isSkippable) to the Pass base class and the PassConcept template with default implementations (in the PassClass and the PassInfoMixin template) that returns true and updated individual passes that I believe cannot be skipped if they are present with an override that returns false.

[andrew.w.kaylor]

Adding one more unskippable pass (unreachable MBB elimination). With this change, I am able to run clang against a test file I was using at -O3 with -opt-bisect-limit=0. Previously the live variable analysis was asserting because of an unreachable block in a machine function that had been added very early by the AddDiscriminators pass (which I believe must not be skipped).

[andrew.w.kaylor]

Added tests
Moved a few checks so that the bisect check happened before the debug message saying the pass was being executed
Made printing passes unskippable
Updated adapter passes to call the contained pass' isSkippable function

[andrew.w.kaylor]

-Rebased
-Added new unskippable passes (Bitcode Writer and pseudo instruction expansion for ARM and AArch64)
-Added a test to verify code generation works with all skippable passes skipped
-Minor updates to make tests less flaky

[andrew.w.kaylor]

If we can agree on the approach I have taken here, I believe that this code is ready to go. I'm now awaiting review feedback and don't have any more updates to this change set in progress.

[MatzeB]

I still wonder whether we can reuse, the existing OptNone, handling. Would something like this work (pseudo patch):

-  /// skipOptnoneFunction - This function has Attribute::OptimizeNone
-  /// and most transformation passes should skip it.
-  bool skipOptnoneFunction(const Function &F) const;
+  /// Optional passes call this function to check whether the pass should be
+  /// skipped. This is the case when Attribute::OptimizeNone is set or when
+  /// optimization bisect is over the limit.
+  bool skipFunction(const Function &F) const;

-bool FunctionPass::skipOptnoneFunction(const Function &F) const {
+bool FunctionPass::skipFunction(const Function &F) const {
+  LLVMContext &C = F.getContext();
+  if (C.getOptBisect().shouldSkipPass(F))
+    return true;

 bool MyPass::runOnMachineFunction(MachineFunction &MF) {
-  if (skipOptnoneFunction(*MF.getFunction()))
+  if (skipFunction(*MF.getFunction()))

We could add an additional parameter if we find instances where we really want to run a pass when OptNone is set but not in an optimization bisect.

include/llvm/Pass.h

118

Don't repeat the function name in the doxygen comment (we avoid this in new code).

[mehdi_amini]

In D18576#399015, @MatzeB wrote:

-bool FunctionPass::skipOptnoneFunction(const Function &F) const {
+bool FunctionPass::skipFunction(const Function &F) const {
+ LLVMContext &C = F.getContext();
+ if (C.getOptBisect().shouldSkipPass(F))
+ return true;

I don't really get how the LLVMContext becomes involved here?

[MatzeB]

In D18576#399022, @joker.eph wrote:

In D18576#399015, @MatzeB wrote:

-bool FunctionPass::skipOptnoneFunction(const Function &F) const {
+bool FunctionPass::skipFunction(const Function &F) const {
+ LLVMContext &C = F.getContext();
+ if (C.getOptBisect().shouldSkipPass(F))
+ return true;

I don't really get how the LLVMContext becomes involved here?

We have to count how many passes we skipped/did not skip and compare that against the bisect number. This is global information.

[andrew.w.kaylor]

In D18576#399015, @MatzeB wrote:

I still wonder whether we can reuse, the existing OptNone, handling.

I can model that and throw up an alternate implementation. My concern is that would require all passes to opt in to the bisection whereas I'm trying to get it so that everything is included unless it specifically excludes itself. We'll need passes to opt in to the case-by-case handling to get fine grained, but I'd like to avoid that at the pass level so that we don't run into problems where there is a problem in pass A but bisect points to pass B because pass A didn't make the call to opt in.

Otherwise, I agree that having the skip initiated from within the pass itself has some definite benefits from a design perspective. The implementation I have up right now felt particularly awkward with the new pass manager and the propagation of the desired default behavior is a good bit less "automatic" in that case, in that it only happens for passes that derive from the right mix-in templates.

The "OptNone" handling that currently exists only applies to function passes, right? Obviously something analogous can be added to other pass types.

[MatzeB]

In D18576#399057, @andrew.w.kaylor wrote:

In D18576#399015, @MatzeB wrote:

I still wonder whether we can reuse, the existing OptNone, handling.

I can model that and throw up an alternate implementation. My concern is that would require all passes to opt in to the bisection whereas I'm trying to get it so that everything is included unless it specifically excludes itself. We'll need passes to opt in to the case-by-case handling to get fine grained, but I'd like to avoid that at the pass level so that we don't run into problems where there is a problem in pass A but bisect points to pass B because pass A didn't make the call to opt in.

Otherwise, I agree that having the skip initiated from within the pass itself has some definite benefits from a design perspective. The implementation I have up right now felt particularly awkward with the new pass manager and the propagation of the desired default behavior is a good bit less "automatic" in that case, in that it only happens for passes that derive from the right mix-in templates.

The "OptNone" handling that currently exists only applies to function passes, right? Obviously something analogous can be added to other pass types.

skipOptnoneFunction() is available in FunctionPass, BasicBlockPass and LoopPass and seems to be consistently used there.

[andrew.w.kaylor]

In D18576#399046, @MatzeB wrote:

We have to count how many passes we skipped/did not skip and compare that against the bisect number. This is global information.

Is there a good way to get the context from a CallGraphSCC? This is what I came up with:

static LLVMContext *getCGNodeContext(CallGraphNode *Node) {
  Function *F = Node->getFunction();
  if (F)
    return &F->getContext();
  for (CallGraphNode::iterator I = Node->begin(), E = Node->end(); I != E;
       ++I) {
    if (I->first)
      return &cast<Function>(I->first)->getContext();
    Function *CalledFn = I->second->getFunction();
    // A null CalledFn indicates a call to an external node.
    if (!CalledFn)
      continue;
    return &(CalledFn->getContext());
  }
}

bool CallGraphSCCPass::skipSCC(CallGraphSCC &SCC) const {
  CallGraphNode *Node = *(SCC.begin());
  assert(Node);
  if (!Node)
    return false;
  LLVMContext *Context = nullptr;
  for (CallGraphNode *Node : SCC) {
    Context = getCGNodeContext(Node);
    if (Context)
      break;
  }
  assert(Context);
  // If we can't get the context, assume the pass can't be skipped.
  if (!Context)
    return false;
  return !Context->getOptBisect().shouldRunPass(this, &SCC);
}

It feels awful. Is there a better way to do that?

[MatzeB]

In D18576#400442, @andrew.w.kaylor wrote:

In D18576#399046, @MatzeB wrote:

We have to count how many passes we skipped/did not skip and compare that against the bisect number. This is global information.

Is there a good way to get the context from a CallGraphSCC? This is what I came up with:

static LLVMContext *getCGNodeContext(CallGraphNode *Node) {
  Function *F = Node->getFunction();
  if (F)
    return &F->getContext();
  for (CallGraphNode::iterator I = Node->begin(), E = Node->end(); I != E;
       ++I) {
    if (I->first)
      return &cast<Function>(I->first)->getContext();
    Function *CalledFn = I->second->getFunction();
    // A null CalledFn indicates a call to an external node.
    if (!CalledFn)
      continue;
    return &(CalledFn->getContext());
  }
}

bool CallGraphSCCPass::skipSCC(CallGraphSCC &SCC) const {
  CallGraphNode *Node = *(SCC.begin());
  assert(Node);
  if (!Node)
    return false;
  LLVMContext *Context = nullptr;
  for (CallGraphNode *Node : SCC) {
    Context = getCGNodeContext(Node);
    if (Context)
      break;
  }
  assert(Context);
  // If we can't get the context, assume the pass can't be skipped.
  if (!Context)
    return false;
  return !Context->getOptBisect().shouldRunPass(this, &SCC);
}

It feels awful. Is there a better way to do that?

This does indeed look ugly. The best solution I can see would be to give the CallGraphSCC class a reference to the CallGraph (from there you should be able to go CallGraph.getModule().getContext()). CallGraphSCC is only instantiated once per CallGraphSCCPassManager as far as I can see so an extra reference shouldn't hurt.

[andrew.w.kaylor]

The new pass manager design also presents a problem in terms of creating a single, simple check function that goes through the LLVMContext. Right now, I'm testing with the global singleton like this:

if (!getOptBisect().shouldRunPass(name(), &F))
  return PreservedAnalyses::all();

Trying to move that into the context yields something like this:

if (!F.getContext().getOptBisect().shouldRunPass(name(), &F))
  return PreservedAnalyses::all();

That's not terrible, but for loop passes it becomes this:

if (auto *F = L->getHeader()->getParent()) {
  LLVMContext &Context = F->getContext();
  if (!Context.getOptBisect().shouldRunPass(this, L))
    return PreservedAnalyses::all();
}

I could provide global helper functions that perform this check, but that has the feel of false encapsulation.

[andrew.w.kaylor]

I have just created a new differential (D19172) which implements the optnone-based approach. Assuming we agree that approach is preferable, that patch will supersede this one.

include/llvm/Analysis/CGSCCPassManager.h

PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
 
     // By definition we preserve the proxy. This precludes *any* invalidation
     // of CGSCC analyses by the proxy, but that's OK because we've taken
     // care to invalidate analyses in the CGSCC analysis manager
     // incrementally above.
     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
     return PA;
   }
+  bool isSkippable() const { return Pass.isSkippable(); }
 
 private:
   CGSCCPassT Pass;
 };
 
 /// \brief A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename CGSCCPassT>
PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM) {
     // of function analyses by the proxy, but that's OK because we've taken
     // care to invalidate analyses in the function analysis manager
     // incrementally above.
     // FIXME: We need to update the call graph here to account for any deleted
     // edges!
     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
     return PA;
   }
+  bool isSkippable() const { return Pass.isSkippable(); }
 
 private:
   FunctionPassT Pass;
 };
 
 /// \brief A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename FunctionPassT>
 CGSCCToFunctionPassAdaptor<FunctionPassT>
 createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
   return CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
 }
 }
 
 #endif

include/llvm/Analysis/LoopPass.h

 public:
   static char ID;
   explicit LPPassManager();
 
   /// run - Execute all of the passes scheduled for execution.  Keep track of
   /// whether any of the passes modifies the module, and if so, return true.
   bool runOnFunction(Function &F) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   /// Pass Manager itself does not invalidate any analysis info.
   // LPPassManager needs LoopInfo.
   void getAnalysisUsage(AnalysisUsage &Info) const override;
 
   const char *getPassName() const override {
     return "Loop Pass Manager";
   }
 

include/llvm/Analysis/LoopPassManager.h

PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
     }
 
     // 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<LoopAnalysisManagerFunctionProxy>();
     return PA;
   }
+  bool isSkippable() const { return Pass.isSkippable(); }
 
 private:
   LoopPassT Pass;
 };
 
 /// \brief A function to deduce a loop pass type and wrap it in the templated
 /// adaptor.
 template <typename LoopPassT>
 FunctionToLoopPassAdaptor<LoopPassT>
 createFunctionToLoopPassAdaptor(LoopPassT Pass) {
   return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass));
 }
 }
 
 #endif // LLVM_ANALYSIS_LOOPPASSMANAGER_H

include/llvm/Analysis/RegionPass.h

public:
   static char ID;
   explicit RGPassManager();
 
   /// @brief Execute all of the passes scheduled for execution.
   ///
   /// @return True if any of the passes modifies the function.
   bool runOnFunction(Function &F) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   /// Pass Manager itself does not invalidate any analysis info.
   /// RGPassManager needs RegionInfo.
   void getAnalysisUsage(AnalysisUsage &Info) const override;
 
   const char *getPassName() const override {
     return "Region Pass Manager";
   }
 

include/llvm/Bitcode/BitcodeWriterPass.h

explicit BitcodeWriterPass(raw_ostream &OS,
                              bool EmitSummaryIndex = false)
       : OS(OS), ShouldPreserveUseListOrder(ShouldPreserveUseListOrder),
         EmitSummaryIndex(EmitSummaryIndex) {}
 
   /// \brief Run the bitcode writer pass, and output the module to the selected
   /// output stream.
   PreservedAnalyses run(Module &M);
 
+  // If the BitcodeWriterPass is present, it shouldn't be skipped.  The
+  // expecteed result cannot be achieved without it.
+  bool isSkippable() const { return false; }
+
   static StringRef name() { return "BitcodeWriterPass"; }
 };
 
 }
 
 #endif

include/llvm/CodeGen/AsmPrinter.h

public:
 
   /// Emit the specified function out to the OutStreamer.
   bool runOnMachineFunction(MachineFunction &MF) override {
     SetupMachineFunction(MF);
     EmitFunctionBody();
     return false;
   }
 
+  // Don't skip this pass or any of its subclasses while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   //===------------------------------------------------------------------===//
   // Coarse grained IR lowering routines.
   //===------------------------------------------------------------------===//
 
   /// This should be called when a new MachineFunction is being processed from
   /// runOnMachineFunction.
   void SetupMachineFunction(MachineFunction &MF);
 

include/llvm/CodeGen/LiveIntervalAnalysis.h

public:
     VNInfo::Allocator& getVNInfoAllocator() { return VNInfoAllocator; }
 
     void getAnalysisUsage(AnalysisUsage &AU) const override;
     void releaseMemory() override;
 
     /// runOnMachineFunction - pass entry point
     bool runOnMachineFunction(MachineFunction&) override;
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
     /// print - Implement the dump method.
     void print(raw_ostream &O, const Module* = nullptr) const override;
 
     /// intervalIsInOneMBB - If LI is confined to a single basic block, return
     /// a pointer to that block.  If LI is live in to or out of any block,
     /// return NULL.
     MachineBasicBlock *intervalIsInOneMBB(const LiveInterval &LI) const;
 

include/llvm/CodeGen/LiveRegMatrix.h

class LiveRegMatrix : public MachineFunctionPass {
   unsigned RegMaskTag;
   unsigned RegMaskVirtReg;
   BitVector RegMaskUsable;
 
   // MachineFunctionPass boilerplate.
   void getAnalysisUsage(AnalysisUsage&) const override;
   bool runOnMachineFunction(MachineFunction&) override;
   void releaseMemory() override;
+
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 public:
   static char ID;
   LiveRegMatrix();
 
   //===--------------------------------------------------------------------===//
   // High-level interface.
   //===--------------------------------------------------------------------===//
   //

include/llvm/CodeGen/LiveStackAnalysis.h

public:
   VNInfo::Allocator &getVNInfoAllocator() { return VNInfoAllocator; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
   void releaseMemory() override;
 
   /// runOnMachineFunction - pass entry point
   bool runOnMachineFunction(MachineFunction &) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   /// print - Implement the dump method.
   void print(raw_ostream &O, const Module * = nullptr) const override;
 };
 }
 
 #endif /* LLVM_CODEGEN_LIVESTACK_ANALYSIS_H */

include/llvm/CodeGen/LiveVariables.h

private:   // Intermediate data structures
 
   void runOnInstr(MachineInstr *MI, SmallVectorImpl<unsigned> &Defs);
 
   void runOnBlock(MachineBasicBlock *MBB, unsigned NumRegs);
 public:
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   /// RegisterDefIsDead - Return true if the specified instruction defines the
   /// specified register, but that definition is dead.
   bool RegisterDefIsDead(MachineInstr *MI, unsigned Reg) const;
 
   //===--------------------------------------------------------------------===//
   //  API to update live variable information
 
   /// replaceKillInstruction - Update register kill info by replacing a kill

include/llvm/CodeGen/MachineFunctionAnalysis.h

const char* getPassName() const override {
     return "Machine Function Analysis";
   }
 
 private:
   bool doInitialization(Module &M) override;
   bool runOnFunction(Function &F) override;
   void releaseMemory() override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 };
 
 } // End llvm namespace
 
 #endif

include/llvm/CodeGen/SelectionDAGISel.h

public:
   ~SelectionDAGISel() override;
 
   const TargetLowering *getTargetLowering() const { return TLI; }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnMachineFunction(MachineFunction &MF) override;
 
+  // Don't skip this pass or its subclasses while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   virtual void EmitFunctionEntryCode() {}
 
   /// PreprocessISelDAG - This hook allows targets to hack on the graph before
   /// instruction selection starts.
   virtual void PreprocessISelDAG() {}
 
   /// PostprocessISelDAG() - This hook allows the target to hack on the graph
   /// right after selection.

include/llvm/CodeGen/SlotIndexes.h

~SlotIndexes() override {
       indexList.clearAndLeakNodesUnsafely();
     }
 
     void getAnalysisUsage(AnalysisUsage &au) const override;
     void releaseMemory() override;
 
     bool runOnMachineFunction(MachineFunction &fn) override;
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
     /// Dump the indexes.
     void dump() const;
 
     /// Renumber the index list, providing space for new instructions.
     void renumberIndexes();
 
     /// Repair indexes after adding and removing instructions.
     void repairIndexesInRange(MachineBasicBlock *MBB,

include/llvm/CodeGen/VirtRegMap.h

private:
     void operator=(const VirtRegMap&) = delete;
 
   public:
     static char ID;
     VirtRegMap() : MachineFunctionPass(ID), Virt2PhysMap(NO_PHYS_REG),
                    Virt2StackSlotMap(NO_STACK_SLOT), Virt2SplitMap(0) { }
     bool runOnMachineFunction(MachineFunction &MF) override;
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesAll();
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
     MachineFunction &getMachineFunction() const {
       assert(MF && "getMachineFunction called before runOnMachineFunction");
       return *MF;

include/llvm/IR/IRPrintingPasses.h

class PrintModulePass {
   bool ShouldPreserveUseListOrder;
 
 public:
   PrintModulePass();
   PrintModulePass(raw_ostream &OS, const std::string &Banner = "",
                   bool ShouldPreserveUseListOrder = false);
 
   PreservedAnalyses run(Module &M);
-
+  bool isSkippable() const { return false; }
   static StringRef name() { return "PrintModulePass"; }
 };
 
 /// \brief Pass for printing a Function as LLVM's text IR assembly.
 ///
 /// Note: This pass is for use with the new pass manager. Use the create...Pass
 /// functions above to create passes for use with the legacy pass manager.
 class PrintFunctionPass {
   raw_ostream &OS;
   std::string Banner;
 
 public:
   PrintFunctionPass();
   PrintFunctionPass(raw_ostream &OS, const std::string &Banner = "");
 
   PreservedAnalyses run(Function &F);
-
+  bool isSkippable() const { return false; }
   static StringRef name() { return "PrintFunctionPass"; }
 };
 
 } // End llvm namespace
 
 #endif

include/llvm/IR/LegacyPassManagers.h

public:
   /// run - Execute all of the passes scheduled for execution.  Keep track of
   /// whether any of the passes modifies the module, and if so, return true.
   bool runOnFunction(Function &F);
   bool runOnModule(Module &M) override;
 
   /// cleanup - After running all passes, clean up pass manager cache.
   void cleanup();
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   /// doInitialization - Overrides ModulePass doInitialization for global
   /// initialization tasks
   ///
   using ModulePass::doInitialization;
 
   /// doInitialization - Run all of the initializers for the function passes.
   ///
   bool doInitialization(Module &M) override;

include/llvm/IR/OptBisect.h

+//===----------- llvm/IR/OptBisect.h - LLVM Bisect support -------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file declares the interface for bisecting optimizations.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_OPTBISECT_H
+#define LLVM_IR_OPTBISECT_H
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/IR/PassManagerInternal.h"
+#include "llvm/PassRegistry.h"
+
+namespace llvm {
+
+class OptBisect {
+public:
+  OptBisect();
+
+  // Interface function for the legacy pass manager.
+  template <class UnitT>
+  bool shouldRunPass(const Pass *P, const UnitT *U);
+
+  // Interface function for the new pass manager.
+  template <class UnitT>
+  bool shouldRunPass(detail::PassConcept<UnitT> *P, const UnitT *U);
+
+  // Opt-in methods for optimization cases.
+  bool shouldRunCase(const Twine &Msg);
+
+private:
+  bool checkPass(const StringRef PassName, const StringRef TargetDesc,
+                 bool IsSkippable, bool IsAnalysis);
+
+  bool BisectEnabled = false;
+  int LastBisectNum = 0;
+};
+
+extern OptBisect &getOptBisector();
+
+} // namespace llvm
+
+#endif // LLVM_IR_OptBisect_H

include/llvm/IR/PassManager.h

 
 #ifndef LLVM_IR_PASSMANAGER_H
 #define LLVM_IR_PASSMANAGER_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/OptBisect.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManagerInternal.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/TypeName.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Support/type_traits.h"
 #include <list>

 template <typename DerivedT> struct PassInfoMixin {
   /// Returns the name of the derived pass type.
   static StringRef name() {
     StringRef Name = getTypeName<DerivedT>();
     if (Name.startswith("llvm::"))
       Name = Name.drop_front(strlen("llvm::"));
     return Name;
   }
+
+  bool isSkippable() const { return true; }
 };
 
 /// A CRTP mix-in to automatically provide informational APIs needed for
 /// analysis passes.
 ///
 /// This provides some boiler plate for types that are analysis passes. It
 /// automatically mixes in \c PassInfoMixin and adds informational APIs
 /// specifically used for analyses.
public:
   /// \brief Run all of the passes in this manager over the IR.
   PreservedAnalyses run(IRUnitT &IR, AnalysisManager<IRUnitT> &AM) {
     PreservedAnalyses PA = PreservedAnalyses::all();
 
     if (DebugLogging)
       dbgs() << "Starting " << getTypeName<IRUnitT>() << " pass manager run.\n";
 
     for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
+      if (!getOptBisector().shouldRunPass(Passes[Idx].get(), &IR))
+        continue;
       if (DebugLogging)
         dbgs() << "Running pass: " << Passes[Idx]->name() << " on "
                << IR.getName() << "\n";
 
       PreservedAnalyses PassPA = Passes[Idx]->run(IR, AM);
 
       // Update the analysis manager as each pass runs and potentially
       // invalidates analyses. We also update the preserved set of analyses
PreservedAnalyses run(IRUnitT &IR, AnalysisManager<IRUnitT> &AM) {
     return PA;
   }
 
   template <typename PassT> void addPass(PassT Pass) {
     typedef detail::PassModel<IRUnitT, PassT> PassModelT;
     Passes.emplace_back(new PassModelT(std::move(Pass)));
   }
 
+  // Pass managers shouldn't be skipped when bisecting optimization failures.
+  bool isSkippable() const { return false; }
+
   static StringRef name() { return "PassManager"; }
 
 private:
   typedef detail::PassConcept<IRUnitT> PassConceptT;
 
   PassManager(const PassManager &) = delete;
   PassManager &operator=(const PassManager &) = delete;
 
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
     // By definition we preserve the proxy. This precludes *any* invalidation
     // of function analyses by the proxy, but that's OK because we've taken
     // care to invalidate analyses in the function analysis manager
     // incrementally above.
     PA.preserve<FunctionAnalysisManagerModuleProxy>();
     return PA;
   }
 
+  bool isSkippable() const { return Pass.isSkippable(); }
+
 private:
   FunctionPassT Pass;
 };
 
 /// \brief A function to deduce a function pass type and wrap it in the
 /// templated adaptor.
 template <typename FunctionPassT>
 ModuleToFunctionPassAdaptor<FunctionPassT>

include/llvm/IR/PassManagerInternal.h

template <typename IRUnitT> struct PassConcept {
 
   /// \brief 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, AnalysisManager<IRUnitT> &AM) = 0;
 
+  /// \brief The polymorphic API which queries a pass to see if it may be
+  /// skipped without causing incorrect code generation.
+  virtual bool isSkippable() const = 0;
+
   /// \brief Polymorphic method to access the name of a pass.
   virtual StringRef name() = 0;
 };
 
 /// \brief SFINAE metafunction for computing whether \c PassT has a run method
 /// accepting an \c AnalysisManager<IRUnitT>.
 template <typename IRUnitT, typename PassT, typename ResultT>
 class PassRunAcceptsAnalysisManager {
struct PassModel<IRUnitT, PassT, PreservedAnalysesT, true>
   PassModel &operator=(PassModel RHS) {
     swap(*this, RHS);
     return *this;
   }
 
   PreservedAnalysesT run(IRUnitT &IR, AnalysisManager<IRUnitT> &AM) override {
     return Pass.run(IR, AM);
   }
+  bool isSkippable() const override { return Pass.isSkippable(); }
   StringRef name() override { return PassT::name(); }
   PassT Pass;
 };
 
 /// \brief Specialization of \c PassModel for passes that accept an analyis
 /// manager.
 template <typename IRUnitT, typename PassT, typename PreservedAnalysesT>
 struct PassModel<IRUnitT, PassT, PreservedAnalysesT, false>
struct PassModel<IRUnitT, PassT, PreservedAnalysesT, false>
   PassModel &operator=(PassModel RHS) {
     swap(*this, RHS);
     return *this;
   }
 
   PreservedAnalysesT run(IRUnitT &IR, AnalysisManager<IRUnitT> &) override {
     return Pass.run(IR);
   }
+  bool isSkippable() const override { return Pass.isSkippable(); }
   StringRef name() override { return PassT::name(); }
   PassT Pass;
 };
 
 /// \brief Abstract concept of an analysis result.
 ///
 /// This concept is parameterized over the IR unit that this result pertains
 /// to.

include/llvm/IR/Verifier.h

 class VerifierPass : public PassInfoMixin<VerifierPass> {
   bool FatalErrors;
 
 public:
   explicit VerifierPass(bool FatalErrors = true) : FatalErrors(FatalErrors) {}
 
   PreservedAnalyses run(Module &M);
   PreservedAnalyses run(Function &F);
+
+  // Skipping the verifier while bisecting failures would be counterproductive.
+  bool isSkippable() const { return false; }
 };
 
 } // End llvm namespace
 
 #endif

include/llvm/Pass.h

public:
   ///
   virtual bool doInitialization(Module &)  { return false; }
 
   /// doFinalization - Virtual method overriden by subclasses to do any
   /// necessary clean up after all passes have run.
   ///
   virtual bool doFinalization(Module &) { return false; }
 
+  /// isSkippable -- Queries whether the pass may be skipped if it is
+  /// present in a pass manager.  Some passes, such as the register
+  /// allocator, must be run if they are present in order to achieve
+  /// correct code generation.  Other passes may be skipped for
+  /// bisectional analysis of optimization related failures.
+  virtual bool isSkippable() const { return true; }
+
   /// print - Print out the internal state of the pass.  This is called by
   /// Analyze to print out the contents of an analysis.  Otherwise it is not
   /// necessary to implement this method.  Beware that the module pointer MAY be
   /// null.  This automatically forwards to a virtual function that does not
   /// provide the Module* in case the analysis doesn't need it it can just be
   /// ignored.
   ///
   virtual void print(raw_ostream &O, const Module *M) const;

include/llvm/Transforms/IPO/ForceFunctionAttrs.h

 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
 /// Pass which forces specific function attributes into the IR, primarily as
 /// a debugging tool.
 struct ForceFunctionAttrsPass : PassInfoMixin<ForceFunctionAttrsPass> {
   PreservedAnalyses run(Module &M);
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const { return false; }
 };
 
 /// Create a legacy pass manager instance of a pass to force function attrs.
 Pass *createForceFunctionAttrsLegacyPass();
 
 }
 
 #endif // LLVM_TRANSFORMS_IPO_FORCEFUNCTIONATTRS_H

lib/Analysis/CallGraphSCCPass.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/CallGraphSCCPass.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/OptBisect.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/LegacyPassManagers.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
public:
   static char ID;
   explicit CGPassManager() 
     : ModulePass(ID), PMDataManager() { }
 
   /// Execute all of the passes scheduled for execution.  Keep track of
   /// whether any of the passes modifies the module, and if so, return true.
   bool runOnModule(Module &M) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   using ModulePass::doInitialization;
   using ModulePass::doFinalization;
 
   bool doInitialization(CallGraph &CG);
   bool doFinalization(CallGraph &CG);
 
   /// Pass Manager itself does not invalidate any analysis info.
   void getAnalysisUsage(AnalysisUsage &Info) const override {
bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
   // is set to false when we run a function pass so that we know to clean up
   // the callgraph when we need to run a CGSCCPass again.
   bool CallGraphUpToDate = true;
 
   // Run all passes on current SCC.
   for (unsigned PassNo = 0, e = getNumContainedPasses();
        PassNo != e; ++PassNo) {
     Pass *P = getContainedPass(PassNo);
-    
+    if (!getOptBisector().shouldRunPass(P, &CurSCC))
+      continue;
+
     // If we're in -debug-pass=Executions mode, construct the SCC node list,
     // otherwise avoid constructing this string as it is expensive.
     if (isPassDebuggingExecutionsOrMore()) {
       std::string Functions;
   #ifndef NDEBUG
       raw_string_ostream OS(Functions);
       for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
            I != E; ++I) {

lib/Analysis/LoopPass.cpp

 //===- LoopPass.cpp - Loop Pass and Loop Pass Manager ---------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements LoopPass and LPPassManager. All loop optimization
 // and transformation passes are derived from LoopPass. LPPassManager is
 // responsible for managing LoopPasses.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/IR/OptBisect.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
bool LPPassManager::runOnFunction(Function &F) {
   while (!LQ.empty()) {
     bool LoopWasDeleted = false;
     CurrentLoop = LQ.back();
 
     // Run all passes on the current Loop.
     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       LoopPass *P = getContainedPass(Index);
 
+      if (!getOptBisector().shouldRunPass(P, CurrentLoop))
+        continue;
+
       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
                    CurrentLoop->getHeader()->getName());
       dumpRequiredSet(P);
 
       initializeAnalysisImpl(P);
 
       {
         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());

lib/Analysis/RegionPass.cpp

 // This file implements RegionPass and RGPassManager. All region optimization
 // and transformation passes are derived from RegionPass. RGPassManager is
 // responsible for managing RegionPasses.
 // most of these codes are COPY from LoopPass.cpp
 //
 //===----------------------------------------------------------------------===//
 #include "llvm/Analysis/RegionPass.h"
 #include "llvm/Analysis/RegionIterator.h"
+#include "llvm/IR/OptBisect.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Timer.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "regionpassmgr"
 
 //===----------------------------------------------------------------------===//
while (!RQ.empty()) {
     CurrentRegion  = RQ.back();
     skipThisRegion = false;
     redoThisRegion = false;
 
     // Run all passes on the current Region.
     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       RegionPass *P = (RegionPass*)getContainedPass(Index);
 
+      if (!getOptBisector().shouldRunPass(P, CurrentRegion))
+        continue;
+
       if (isPassDebuggingExecutionsOrMore()) {
         dumpPassInfo(P, EXECUTION_MSG, ON_REGION_MSG,
                      CurrentRegion->getNameStr());
         dumpRequiredSet(P);
       }
 
       initializeAnalysisImpl(P);
 

lib/Bitcode/Writer/BitcodeWriterPass.cpp

public:
     explicit WriteBitcodePass(raw_ostream &o, bool ShouldPreserveUseListOrder,
                               bool EmitSummaryIndex)
         : ModulePass(ID), OS(o),
           ShouldPreserveUseListOrder(ShouldPreserveUseListOrder),
           EmitSummaryIndex(EmitSummaryIndex) {}
 
     const char *getPassName() const override { return "Bitcode Writer"; }
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
     bool runOnModule(Module &M) override {
       WriteBitcodeToFile(&M, OS, ShouldPreserveUseListOrder, EmitSummaryIndex);
       return false;
     }
   };
 }
 
 char WriteBitcodePass::ID = 0;
 
 ModulePass *llvm::createBitcodeWriterPass(raw_ostream &Str,
                                           bool ShouldPreserveUseListOrder,
                                           bool EmitSummaryIndex) {
   return new WriteBitcodePass(Str, ShouldPreserveUseListOrder,
                               EmitSummaryIndex);
 }

lib/CodeGen/DwarfEHPrepare.cpp

public:
 
     bool runOnFunction(Function &Fn) override;
 
     bool doFinalization(Module &M) override {
       RewindFunction = nullptr;
       return false;
     }
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
     void getAnalysisUsage(AnalysisUsage &AU) const override;
 
     const char *getPassName() const override {
       return "Exception handling preparation";
     }
   };
 } // end anonymous namespace
 

lib/CodeGen/ExpandISelPseudos.cpp

namespace {
   class ExpandISelPseudos : public MachineFunctionPass {
   public:
     static char ID; // Pass identification, replacement for typeid
     ExpandISelPseudos() : MachineFunctionPass(ID) {}
 
   private:
     bool runOnMachineFunction(MachineFunction &MF) override;
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       MachineFunctionPass::getAnalysisUsage(AU);
     }
   };
 } // end anonymous namespace
 
 char ExpandISelPseudos::ID = 0;
 char &llvm::ExpandISelPseudosID = ExpandISelPseudos::ID;

lib/CodeGen/ExpandPostRAPseudos.cpp

void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addPreservedID(MachineLoopInfoID);
     AU.addPreservedID(MachineDominatorsID);
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
   /// runOnMachineFunction - pass entry point
   bool runOnMachineFunction(MachineFunction&) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 private:
   bool LowerSubregToReg(MachineInstr *MI);
   bool LowerCopy(MachineInstr *MI);
 
   void TransferImplicitDefs(MachineInstr *MI);
 };
 } // end anonymous namespace
 

lib/CodeGen/FuncletLayout.cpp

 class FuncletLayout : public MachineFunctionPass {
 public:
   static char ID; // Pass identification, replacement for typeid
   FuncletLayout() : MachineFunctionPass(ID) {
     initializeFuncletLayoutPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnMachineFunction(MachineFunction &F) override;
+
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   MachineFunctionProperties getRequiredProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::AllVRegsAllocated);
   }
 };
 }
 
 char FuncletLayout::ID = 0;

lib/CodeGen/GCRootLowering.cpp

public:
   static char ID;
 
   LowerIntrinsics();
   const char *getPassName() const override;
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool doInitialization(Module &M) override;
   bool runOnFunction(Function &F) override;
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 };
 
 /// GCMachineCodeAnalysis - This is a target-independent pass over the machine
 /// function representation to identify safe points for the garbage collector
 /// in the machine code. It inserts labels at safe points and populates a
 /// GCMetadata record for each function.
 class GCMachineCodeAnalysis : public MachineFunctionPass {
   GCFunctionInfo *FI;

 
 public:
   static char ID;
 
   GCMachineCodeAnalysis();
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnMachineFunction(MachineFunction &MF) override;
+
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 };
 }
 
 // -----------------------------------------------------------------------------
 
 INITIALIZE_PASS_BEGIN(LowerIntrinsics, "gc-lowering", "GC Lowering", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(GCModuleInfo)

lib/CodeGen/LiveDebugValues.cpp

public:
   }
 
   /// Print to ostream with a message.
   void printVarLocInMBB(const VarLocInMBB &V, const char *msg,
                         raw_ostream &Out) const;
 
   /// Calculate the liveness information for the given machine function.
   bool runOnMachineFunction(MachineFunction &MF) override;
+
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 };
 } // namespace
 
 //===----------------------------------------------------------------------===//
 //            Implementation
 //===----------------------------------------------------------------------===//
 
 char LiveDebugValues::ID = 0;

lib/CodeGen/LiveDebugVariables.h

 
 private:
 
   bool runOnMachineFunction(MachineFunction &) override;
   void releaseMemory() override;
   void getAnalysisUsage(AnalysisUsage &) const override;
   bool doInitialization(Module &) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 };
 
 } // namespace llvm
 
 #endif

lib/CodeGen/LocalStackSlotAllocation.cpp

class LocalStackSlotPass: public MachineFunctionPass {
     bool insertFrameReferenceRegisters(MachineFunction &Fn);
   public:
     static char ID; // Pass identification, replacement for typeid
     explicit LocalStackSlotPass() : MachineFunctionPass(ID) { 
       initializeLocalStackSlotPassPass(*PassRegistry::getPassRegistry());
     }
     bool runOnMachineFunction(MachineFunction &MF) override;
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       AU.addRequired<StackProtector>();
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
   private:
   };

lib/CodeGen/MachineScheduler.cpp

 class MachineScheduler : public MachineSchedulerBase {
 public:
   MachineScheduler();
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnMachineFunction(MachineFunction&) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   static char ID; // Class identification, replacement for typeinfo
 
 protected:
   ScheduleDAGInstrs *createMachineScheduler();
 };
 
 /// PostMachineScheduler runs after shortly before code emission.
 class PostMachineScheduler : public MachineSchedulerBase {

lib/CodeGen/PHIElimination.cpp

public:
     static char ID; // Pass identification, replacement for typeid
     PHIElimination() : MachineFunctionPass(ID) {
       initializePHIEliminationPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnMachineFunction(MachineFunction &Fn) override;
     void getAnalysisUsage(AnalysisUsage &AU) const override;
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
   private:
     /// EliminatePHINodes - Eliminate phi nodes by inserting copy instructions
     /// in predecessor basic blocks.
     ///
     bool EliminatePHINodes(MachineFunction &MF, MachineBasicBlock &MBB);
     void LowerPHINode(MachineBasicBlock &MBB,
                       MachineBasicBlock::iterator LastPHIIt);
 

lib/CodeGen/PrologEpilogInserter.cpp

return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::AllVRegsAllocated);
   }
 
   /// runOnMachineFunction - Insert prolog/epilog code and replace abstract
   /// frame indexes with appropriate references.
   ///
   bool runOnMachineFunction(MachineFunction &Fn) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 private:
   RegScavenger *RS;
 
   // MinCSFrameIndex, MaxCSFrameIndex - Keeps the range of callee saved
   // stack frame indexes.
   unsigned MinCSFrameIndex, MaxCSFrameIndex;
 
   // Save and Restore blocks of the current function. Typically there is a

lib/CodeGen/RegAllocFast.cpp

const char *getPassName() const override {
       return "Fast Register Allocator";
     }
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
     MachineFunctionProperties getSetProperties() const override {
       return MachineFunctionProperties().set(
           MachineFunctionProperties::Property::AllVRegsAllocated);
     }
 
   private:
     bool runOnMachineFunction(MachineFunction &Fn) override;
     void AllocateBasicBlock();

lib/CodeGen/RegAllocGreedy.cpp

public:
   void enqueue(LiveInterval *LI) override;
   LiveInterval *dequeue() override;
   unsigned selectOrSplit(LiveInterval&, SmallVectorImpl<unsigned>&) override;
   void aboutToRemoveInterval(LiveInterval &) override;
 
   /// Perform register allocation.
   bool runOnMachineFunction(MachineFunction &mf) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   static char ID;
 
 private:
   unsigned selectOrSplitImpl(LiveInterval &, SmallVectorImpl<unsigned> &,
                              SmallVirtRegSet &, unsigned = 0);
 
   bool LRE_CanEraseVirtReg(unsigned) override;
   void LRE_WillShrinkVirtReg(unsigned) override;

lib/CodeGen/ShadowStackGCLowering.cpp

class ShadowStackGCLowering : public FunctionPass {
   std::vector<std::pair<CallInst *, AllocaInst *>> Roots;
 
 public:
   static char ID;
   ShadowStackGCLowering();
 
   bool doInitialization(Module &M) override;
   bool runOnFunction(Function &F) override;
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 
 private:
   bool IsNullValue(Value *V);
   Constant *GetFrameMap(Function &F);
   Type *GetConcreteStackEntryType(Function &F);
   void CollectRoots(Function &F);
   static GetElementPtrInst *CreateGEP(LLVMContext &Context, IRBuilder<> &B,
                                       Type *Ty, Value *BasePtr, int Idx1,

lib/CodeGen/SjLjEHPrepare.cpp

public:
   bool doInitialization(Module &M) override;
   bool runOnFunction(Function &F) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {}
   const char *getPassName() const override {
     return "SJLJ Exception Handling preparation";
   }
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
 private:
   bool setupEntryBlockAndCallSites(Function &F);
   void substituteLPadValues(LandingPadInst *LPI, Value *ExnVal, Value *SelVal);
   Value *setupFunctionContext(Function &F, ArrayRef<LandingPadInst *> LPads);
   void lowerIncomingArguments(Function &F);
   void lowerAcrossUnwindEdges(Function &F, ArrayRef<InvokeInst *> Invokes);
   void insertCallSiteStore(Instruction *I, int Number);
 };

lib/CodeGen/StackColoring.cpp

 public:
   static char ID;
   StackColoring() : MachineFunctionPass(ID) {
     initializeStackColoringPass(*PassRegistry::getPassRegistry());
   }
   void getAnalysisUsage(AnalysisUsage &AU) const override;
   bool runOnMachineFunction(MachineFunction &MF) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
 private:
   /// Debug.
   void dump() const;
 
   /// Removes all of the lifetime marker instructions from the function.
   /// \returns true if any markers were removed.
   bool removeAllMarkers();
 

lib/CodeGen/StackSlotColoring.cpp

void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<MachineBlockFrequencyInfo>();
       AU.addPreserved<MachineBlockFrequencyInfo>();
       AU.addPreservedID(MachineDominatorsID);
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
     bool runOnMachineFunction(MachineFunction &MF) override;
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
   private:
     void InitializeSlots();
     void ScanForSpillSlotRefs(MachineFunction &MF);
     bool OverlapWithAssignments(LiveInterval *li, int Color) const;
     int ColorSlot(LiveInterval *li);
     bool ColorSlots(MachineFunction &MF);
     void RewriteInstruction(MachineInstr *MI, SmallVectorImpl<int> &SlotMapping,
                             MachineFunction &MF);

lib/CodeGen/TwoAddressInstructionPass.cpp

void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addPreserved<LiveIntervals>();
     AU.addPreservedID(MachineLoopInfoID);
     AU.addPreservedID(MachineDominatorsID);
     MachineFunctionPass::getAnalysisUsage(AU);
   }
 
   /// Pass entry point.
   bool runOnMachineFunction(MachineFunction&) override;
+
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 };
 } // end anonymous namespace
 
 char TwoAddressInstructionPass::ID = 0;
 INITIALIZE_PASS_BEGIN(TwoAddressInstructionPass, "twoaddressinstruction",
                 "Two-Address instruction pass", false, false)
 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 INITIALIZE_PASS_END(TwoAddressInstructionPass, "twoaddressinstruction",

lib/CodeGen/UnreachableBlockElim.cpp

 #include "llvm/Pass.h"
 #include "llvm/Target/TargetInstrInfo.h"
 using namespace llvm;
 
 namespace {
   class UnreachableBlockElim : public FunctionPass {
     bool runOnFunction(Function &F) override;
   public:
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
     static char ID; // Pass identification, replacement for typeid
     UnreachableBlockElim() : FunctionPass(ID) {
       initializeUnreachableBlockElimPass(*PassRegistry::getPassRegistry());
     }
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addPreserved<DominatorTreeWrapperPass>();
     }

 }
 
 
 namespace {
   class UnreachableMachineBlockElim : public MachineFunctionPass {
     bool runOnMachineFunction(MachineFunction &F) override;
     void getAnalysisUsage(AnalysisUsage &AU) const override;
     MachineModuleInfo *MMI;
+
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
   public:
     static char ID; // Pass identification, replacement for typeid
     UnreachableMachineBlockElim() : MachineFunctionPass(ID) {}
   };
 }
 char UnreachableMachineBlockElim::ID = 0;
 
 INITIALIZE_PASS(UnreachableMachineBlockElim, "unreachable-mbb-elimination",

lib/CodeGen/VirtRegMap.cpp

 
 public:
   static char ID;
   VirtRegRewriter() : MachineFunctionPass(ID) {}
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnMachineFunction(MachineFunction&) override;
+
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   MachineFunctionProperties getSetProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::AllVRegsAllocated);
   }
 };
 } // end anonymous namespace
 
 char &llvm::VirtRegRewriterID = VirtRegRewriter::ID;

lib/CodeGen/WinEHPrepare.cpp

 public:
   static char ID; // Pass identification, replacement for typeid.
   WinEHPrepare(const TargetMachine *TM = nullptr) : FunctionPass(ID) {}
 
   bool runOnFunction(Function &Fn) override;
 
   bool doFinalization(Module &M) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   const char *getPassName() const override {
     return "Windows exception handling preparation";
   }
 
 private:
   void insertPHIStores(PHINode *OriginalPHI, AllocaInst *SpillSlot);

lib/IR/CMakeLists.txt

add_llvm_library(LLVMCore
   LLVMContextImpl.cpp
   LegacyPassManager.cpp
   MDBuilder.cpp
   Mangler.cpp
   Metadata.cpp
   Module.cpp
   ModuleSummaryIndex.cpp
   Operator.cpp
+  OptBisect.cpp
   Pass.cpp
   PassManager.cpp
   PassRegistry.cpp
   Statepoint.cpp
   Type.cpp
   TypeFinder.cpp
   Use.cpp
   User.cpp

lib/IR/IRPrintingPasses.cpp

PrintModulePassWrapper(raw_ostream &OS, const std::string &Banner,
                          bool ShouldPreserveUseListOrder)
       : ModulePass(ID), P(OS, Banner, ShouldPreserveUseListOrder) {}
 
   bool runOnModule(Module &M) override {
     P.run(M);
     return false;
   }
 
+  bool isSkippable() const override { return P.isSkippable(); }
+
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
   }
 };
 
 class PrintFunctionPassWrapper : public FunctionPass {
   PrintFunctionPass P;
 
 public:
   static char ID;
   PrintFunctionPassWrapper() : FunctionPass(ID) {}
   PrintFunctionPassWrapper(raw_ostream &OS, const std::string &Banner)
       : FunctionPass(ID), P(OS, Banner) {}
 
   // This pass just prints a banner followed by the function as it's processed.
   bool runOnFunction(Function &F) override {
     P.run(F);
     return false;
   }
 
+  bool isSkippable() const override { return P.isSkippable(); }
+
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
   }
 };
 
 class PrintBasicBlockPass : public BasicBlockPass {
   raw_ostream &Out;
   std::string Banner;
 
 public:
   static char ID;
   PrintBasicBlockPass() : BasicBlockPass(ID), Out(dbgs()) {}
   PrintBasicBlockPass(raw_ostream &Out, const std::string &Banner)
       : BasicBlockPass(ID), Out(Out), Banner(Banner) {}
 
   bool runOnBasicBlock(BasicBlock &BB) override {
     Out << Banner << BB;
     return false;
   }
 
+  bool isSkippable() const override { return false; }
+
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
   }
 };
 
 }
 
 char PrintModulePassWrapper::ID = 0;

lib/IR/LegacyPassManager.cpp

 //===- LegacyPassManager.cpp - LLVM Pass Infrastructure Implementation ----===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the legacy LLVM Pass Manager infrastructure.
 //
 //===----------------------------------------------------------------------===//
 
 
 #include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/OptBisect.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/IR/LegacyPassManagers.h"
 #include "llvm/IR/LegacyPassNameParser.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
public:
   // Prepare for running an on the fly pass, freeing memory if needed
   // from a previous run.
   void releaseMemoryOnTheFly();
 
   /// run - Execute all of the passes scheduled for execution.  Keep track of
   /// whether any of the passes modifies the module, and if so, return true.
   bool run(Function &F);
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   /// doInitialization - Run all of the initializers for the function passes.
   ///
   bool doInitialization(Module &M) override;
 
   /// doFinalization - Run all of the finalizers for the function passes.
   ///
   bool doFinalization(Module &M) override;
 
Pass *createPrinterPass(raw_ostream &O,
                           const std::string &Banner) const override {
     return createPrintModulePass(O, Banner);
   }
 
   /// run - Execute all of the passes scheduled for execution.  Keep track of
   /// whether any of the passes modifies the module, and if so, return true.
   bool runOnModule(Module &M);
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   using llvm::Pass::doInitialization;
   using llvm::Pass::doFinalization;
 
   /// doInitialization - Run all of the initializers for the module passes.
   ///
   bool doInitialization();
 
   /// doFinalization - Run all of the finalizers for the module passes.
Pass *createPrinterPass(raw_ostream &O,
                           const std::string &Banner) const override {
     return createPrintModulePass(O, Banner);
   }
 
   /// run - Execute all of the passes scheduled for execution.  Keep track of
   /// whether any of the passes modifies the module, and if so, return true.
   bool run(Module &M);
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   using llvm::Pass::doInitialization;
   using llvm::Pass::doFinalization;
 
   /// doInitialization - Run all of the initializers for the module passes.
   ///
   bool doInitialization();
 
   /// doFinalization - Run all of the finalizers for the module passes.
bool BBPassManager::runOnFunction(Function &F) {
 
   bool Changed = doInitialization(F);
 
   for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I)
     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       BasicBlockPass *BP = getContainedPass(Index);
       bool LocalChanged = false;
 
+      if (!getOptBisector().shouldRunPass(BP, &(*I))) 
+        continue;
+
       dumpPassInfo(BP, EXECUTION_MSG, ON_BASICBLOCK_MSG, I->getName());
       dumpRequiredSet(BP);
 
       initializeAnalysisImpl(BP);
 
       {
         // If the pass crashes, remember this.
         PassManagerPrettyStackEntry X(BP, *I);

 // Execute all the passes managed by this top level manager.
 // Return true if any function is modified by a pass.
 bool FunctionPassManagerImpl::run(Function &F) {
   bool Changed = false;
   TimingInfo::createTheTimeInfo();
 
   initializeAllAnalysisInfo();
   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) {
+    if (getOptBisector().shouldRunPass(getContainedManager(Index), &F))
       Changed |= getContainedManager(Index)->runOnFunction(F);
     F.getContext().yield();
   }
 
   for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index)
     getContainedManager(Index)->cleanup();
 
   wasRun = true;
   return Changed;
bool FPPassManager::runOnFunction(Function &F) {
 
   // Collect inherited analysis from Module level pass manager.
   populateInheritedAnalysis(TPM->activeStack);
 
   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     FunctionPass *FP = getContainedPass(Index);
     bool LocalChanged = false;
 
+    if (!getOptBisector().shouldRunPass(FP, &F))
+      continue;
+      
     dumpPassInfo(FP, EXECUTION_MSG, ON_FUNCTION_MSG, F.getName());
     dumpRequiredSet(FP);
 
     initializeAnalysisImpl(FP);
 
     {
       PassManagerPrettyStackEntry X(FP, F);
       TimeRegion PassTimer(getPassTimer(FP));
MPPassManager::runOnModule(Module &M) {
   // Initialize module passes
   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index)
     Changed |= getContainedPass(Index)->doInitialization(M);
 
   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
     ModulePass *MP = getContainedPass(Index);
     bool LocalChanged = false;
 
+    if (!getOptBisector().shouldRunPass(MP, &M))
+      continue;
+
     dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, M.getModuleIdentifier());
     dumpRequiredSet(MP);
 
     initializeAnalysisImpl(MP);
 
     {
       PassManagerPrettyStackEntry X(MP, M);
       TimeRegion PassTimer(getPassTimer(MP));

lib/IR/OptBisect.cpp

+//===------- llvm/IR/OptBisect/Bisect.cpp - LLVM Bisect support --------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements support for a bisecting optimizations based on a
+// command line option.
+//
+// A singleton is used so that consistent numbering is used across the runs of
+// multiple pass managers.  A typical invocation of clang (for instance) will
+// run three pass managers: one for function level optimizations, one for module
+// level optimizations (which also runs function passes) and one for code
+// generation (which also runs module and function passes).  For more details
+// see clang/lib/CodeGen/BackendUtil.cpp, particularly the functions
+// EmitAssemblyHelper::CreatePasses() and EmitAssemblyHelper::EmitAssembly().
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/StringSet.h"
+#include "llvm/Analysis/CallGraphSCCPass.h"
+#include "llvm/Analysis/LazyCallGraph.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/RegionInfo.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/OptBisect.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Support/ManagedStatic.h"
+#include <sstream>
+
+using namespace llvm;
+
+////////////////////////////////////////////////////////////////////////////////
+// Command line options
+////////////////////////////////////////////////////////////////////////////////
+
+static cl::opt<int> OptBisectLimit("opt-bisect-limit", cl::Hidden,
+                                   cl::init(INT_MAX), cl::Optional,
+                                   cl::desc("Maximum optimization to perform"));
+
+////////////////////////////////////////////////////////////////////////////////
+// Singleton definition, accessor and constructor
+////////////////////////////////////////////////////////////////////////////////
+
+static ManagedStatic<OptBisect> OptBisector;
+
+OptBisect &llvm::getOptBisector() { return *OptBisector; }
+
+OptBisect::OptBisect() {
+  BisectEnabled = OptBisectLimit != INT_MAX;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// Output formatters
+////////////////////////////////////////////////////////////////////////////////
+
+static StringRef getModifiers(bool IsAnalysis, bool IsNecessary) {
+  StringRef DbgModifier;
+  if (IsNecessary)
+    if (IsAnalysis)
+      DbgModifier = " necessary analysis";
+    else
+      DbgModifier = " necessary";
+  else if (IsAnalysis)
+    DbgModifier = " analysis";
+  else
+    DbgModifier = "";
+  return DbgModifier;
+}
+
+static void printPassMessage(const StringRef &Name, int PassNum,
+                             bool IsAnalysis, bool IsNecessary,
+                             StringRef TargetDesc, bool Running) {
+  StringRef Status = Running ? "" : "NOT ";
+  StringRef Modifiers = getModifiers(IsAnalysis, IsNecessary);
+  assert(PassNum != -1 || IsNecessary || IsAnalysis);
+  dbgs() << "BISECT: " << Status << "running" << Modifiers << " pass ";
+  if (PassNum != -1)
+    dbgs() << "(" << PassNum << ") ";
+  dbgs() << Name << " on " << TargetDesc << "\n";
+}
+
+static void printCaseMessage(int CaseNum, StringRef Msg, bool Running) {
+  if (Running)
+    dbgs() << "BISECT: running case (";
+  else
+    dbgs() << "BISECT: NOT running case (";
+  dbgs() << CaseNum << "): " << Msg << "\n";
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// Target description helpers
+////////////////////////////////////////////////////////////////////////////////
+
+static std::string getDescription(const Module *M) {
+  return "module (" + M->getName().str() + ")";
+}
+
+static std::string getDescription(const Function *F) {
+  return "function (" + F->getName().str() + ")";
+}
+
+static std::string getDescription(const BasicBlock *BB) {
+  return "basic block (" + BB->getName().str() + ") in function (" +
+         BB->getParent()->getName().str() + ")";
+}
+
+static std::string getDescription(const Loop *L) {
+  // FIXME: I'd like to be able to provide a better description here, but
+  //        calling L->getHeader() would introduce a new dependency on the
+  //        LLVMCore library.
+  return "loop";
+}
+
+static std::string getDescription(const Region *R) {
+  // FIXME: I'd like to be able to provide a better description here, but
+  //        calling R->getEntry() or R->getExit() would introduce a new
+  //        dependency on the LLVMCore library.
+  return "region";
+}
+
+static std::string getDescription(const CallGraphSCC *SCC) {
+  std::string Desc = "SCC (";
+  bool First = true;
+  for (CallGraphNode *CGN : *SCC) {
+    if (First)
+      First = false;
+    else
+      Desc += ", ";
+    auto *F = CGN->getFunction();
+    if (F)
+      Desc += F->getName();
+    else
+      Desc += "<<null function>>";
+  }
+  Desc += ")";
+  return Desc;
+}
+
+static std::string getDescription(const LazyCallGraph::SCC *SCC) {
+  std::string Desc = "SCC (";
+  bool First = true;
+  for (LazyCallGraph::Node &CGN : *SCC) {
+    if (First)
+      First = false;
+    else
+      Desc += ", ";
+    auto &F = CGN.getFunction();
+    Desc += F.getName();
+  }
+  Desc += ")";
+  return Desc;
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// Criteria functions
+////////////////////////////////////////////////////////////////////////////////
+
+// Force instantiations.
+template bool OptBisect::shouldRunPass(const Pass *, const Module *);
+template bool OptBisect::shouldRunPass(const Pass *, const Function *);
+template bool OptBisect::shouldRunPass(const Pass *, const BasicBlock *);
+template bool OptBisect::shouldRunPass(const Pass *, const Region *);
+template bool OptBisect::shouldRunPass(const Pass *, const Loop *);
+template bool OptBisect::shouldRunPass(const Pass *, const CallGraphSCC *);
+template bool OptBisect::shouldRunPass(detail::PassConcept<Module> *,
+                                       const Module *);
+template bool OptBisect::shouldRunPass(detail::PassConcept<Function> *,
+                                       const Function *);
+template bool OptBisect::shouldRunPass(detail::PassConcept<BasicBlock> *,
+                                       const BasicBlock *);
+template bool OptBisect::shouldRunPass(detail::PassConcept<Region> *,
+                                       const Region *);
+template bool OptBisect::shouldRunPass(detail::PassConcept<Loop> *,
+                                       const Loop *);
+template bool
+OptBisect::shouldRunPass(detail::PassConcept<LazyCallGraph::SCC> *,
+                         const LazyCallGraph::SCC *);
+
+template <class UnitT>
+bool OptBisect::shouldRunPass(const Pass *P, const UnitT *U) {
+  if (!BisectEnabled)
+    return true;
+  bool IsAnalysis = false;
+  const PassInfo *PI =
+      PassRegistry::getPassRegistry()->getPassInfo(P->getPassID());
+  if (PI)
+    IsAnalysis = PI->isAnalysis() || PI->isAnalysisGroup();
+  return checkPass(P->getPassName(), getDescription(U), P->isSkippable(),
+                   IsAnalysis);
+}
+
+// Interface function for the new pass manager.
+template <class UnitT>
+bool OptBisect::shouldRunPass(detail::PassConcept<UnitT> *P, const UnitT *U) {
+  if (!BisectEnabled)
+    return true;
+  // FIXME: Check for analysis passes.
+  return checkPass(P->name(), getDescription(U), P->isSkippable(), false);
+}
+
+bool OptBisect::checkPass(const StringRef PassName, const StringRef TargetDesc,
+                          bool IsSkippable, bool IsAnalysis) {
+  assert(BisectEnabled);
+
+  // Don't take a number for passes we can't skip.
+  if (IsAnalysis || !IsSkippable) {
+    printPassMessage(PassName, -1, IsAnalysis, !IsSkippable, TargetDesc, true);
+    return true;
+  }
+
+  int CurBisectNum = ++LastBisectNum;
+  bool ShouldRun = (OptBisectLimit == -1 || CurBisectNum <= OptBisectLimit);
+  printPassMessage(PassName, CurBisectNum, IsAnalysis, !IsSkippable, TargetDesc,
+                   ShouldRun);
+  return ShouldRun;
+}
+
+bool OptBisect::shouldRunCase(const Twine &Msg) {
+  assert(BisectEnabled);
+  int CurFuelNum = ++LastBisectNum;
+  bool ShouldRun = (OptBisectLimit == -1 || CurFuelNum <= OptBisectLimit);
+  printCaseMessage(CurFuelNum, Msg.str(), ShouldRun);
+  return ShouldRun;
+}

lib/IR/Verifier.cpp

struct VerifierLegacyPass : public FunctionPass {
 
   bool doFinalization(Module &M) override {
     if (!V.verify(M) && FatalErrors)
       report_fatal_error("Broken module found, compilation aborted!");
 
     return false;
   }
 
+  // Skipping the verifier while bisecting failures would be counterproductive.
+  bool isSkippable() const override { return false; }
+
+
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesAll();
   }
 };
 }
 
 char VerifierLegacyPass::ID = 0;
 INITIALIZE_PASS(VerifierLegacyPass, "verify", "Module Verifier", false, false)

lib/Passes/PassBuilder.cpp

 
 static Regex DefaultAliasRegex("^(default|lto-pre-link|lto)<(O[0123sz])>$");
 
 namespace {
 
 /// \brief No-op module pass which does nothing.
 struct NoOpModulePass {
   PreservedAnalyses run(Module &M) { return PreservedAnalyses::all(); }
+  bool isSkippable() const { return true; }
   static StringRef name() { return "NoOpModulePass"; }
 };
 
 /// \brief No-op module analysis.
 class NoOpModuleAnalysis : public AnalysisInfoMixin<NoOpModuleAnalysis> {
   friend AnalysisInfoMixin<NoOpModuleAnalysis>;
   static char PassID;
 
 public:
   struct Result {};
   Result run(Module &) { return Result(); }
   static StringRef name() { return "NoOpModuleAnalysis"; }
 };
 
 /// \brief No-op CGSCC pass which does nothing.
 struct NoOpCGSCCPass {
   PreservedAnalyses run(LazyCallGraph::SCC &C) {
     return PreservedAnalyses::all();
   }
+  bool isSkippable() const { return true; }
   static StringRef name() { return "NoOpCGSCCPass"; }
 };
 
 /// \brief No-op CGSCC analysis.
 class NoOpCGSCCAnalysis : public AnalysisInfoMixin<NoOpCGSCCAnalysis> {
   friend AnalysisInfoMixin<NoOpCGSCCAnalysis>;
   static char PassID;
 
 public:
   struct Result {};
   Result run(LazyCallGraph::SCC &) { return Result(); }
   static StringRef name() { return "NoOpCGSCCAnalysis"; }
 };
 
 /// \brief No-op function pass which does nothing.
 struct NoOpFunctionPass {
   PreservedAnalyses run(Function &F) { return PreservedAnalyses::all(); }
+  bool isSkippable() const { return true; }
   static StringRef name() { return "NoOpFunctionPass"; }
 };
 
 /// \brief No-op function analysis.
 class NoOpFunctionAnalysis : public AnalysisInfoMixin<NoOpFunctionAnalysis> {
   friend AnalysisInfoMixin<NoOpFunctionAnalysis>;
   static char PassID;
 
 public:
   struct Result {};
   Result run(Function &) { return Result(); }
   static StringRef name() { return "NoOpFunctionAnalysis"; }
 };
 
 /// \brief No-op loop pass which does nothing.
 struct NoOpLoopPass {
   PreservedAnalyses run(Loop &L) { return PreservedAnalyses::all(); }
+  bool isSkippable() const { return true; }
   static StringRef name() { return "NoOpLoopPass"; }
 };
 
 /// \brief No-op loop analysis.
 class NoOpLoopAnalysis : public AnalysisInfoMixin<NoOpLoopAnalysis> {
   friend AnalysisInfoMixin<NoOpLoopAnalysis>;
   static char PassID;
 

lib/Target/AArch64/AArch64ExpandPseudoInsts.cpp

public:
   AArch64ExpandPseudo() : MachineFunctionPass(ID) {
     initializeAArch64ExpandPseudoPass(*PassRegistry::getPassRegistry());
   }
 
   const AArch64InstrInfo *TII;
 
   bool runOnMachineFunction(MachineFunction &Fn) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   const char *getPassName() const override {
     return AARCH64_EXPAND_PSEUDO_NAME;
   }
 
 private:
   bool expandMBB(MachineBasicBlock &MBB);
   bool expandMI(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI);
   bool expandMOVImm(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI,

lib/Target/ARM/ARMExpandPseudoInsts.cpp

public:
 
     bool runOnMachineFunction(MachineFunction &Fn) override;
 
     MachineFunctionProperties getRequiredProperties() const override {
       return MachineFunctionProperties().set(
           MachineFunctionProperties::Property::AllVRegsAllocated);
     }
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
     const char *getPassName() const override {
       return "ARM pseudo instruction expansion pass";
     }
 
   private:
     void TransferImpOps(MachineInstr &OldMI,
                         MachineInstrBuilder &UseMI, MachineInstrBuilder &DefMI);
     bool ExpandMI(MachineBasicBlock &MBB,

lib/Target/X86/X86ExpandPseudo.cpp

public:
 
   const X86Subtarget *STI;
   const X86InstrInfo *TII;
   const X86RegisterInfo *TRI;
   const X86FrameLowering *X86FL;
 
   bool runOnMachineFunction(MachineFunction &Fn) override;
 
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
+
   MachineFunctionProperties getRequiredProperties() const override {
     return MachineFunctionProperties().set(
         MachineFunctionProperties::Property::AllVRegsAllocated);
   }
 
   const char *getPassName() const override {
     return "X86 pseudo instruction expansion pass";
   }

lib/Target/X86/X86FloatingPoint.cpp

void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<EdgeBundles>();
       AU.addPreservedID(MachineLoopInfoID);
       AU.addPreservedID(MachineDominatorsID);
       MachineFunctionPass::getAnalysisUsage(AU);
     }
 
     bool runOnMachineFunction(MachineFunction &MF) override;
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
     MachineFunctionProperties getRequiredProperties() const override {
       return MachineFunctionProperties().set(
           MachineFunctionProperties::Property::AllVRegsAllocated);
     }
 
     const char *getPassName() const override { return "X86 FP Stackifier"; }
 
   private:

lib/Target/X86/X86InstrInfo.cpp

bool runOnMachineFunction(MachineFunction &MF) override {
         BuildMI(FirstMBB, MBBI, DL, TII->get(X86::ADD32ri), GlobalBaseReg)
           .addReg(PC).addExternalSymbol("_GLOBAL_OFFSET_TABLE_",
                                         X86II::MO_GOT_ABSOLUTE_ADDRESS);
       }
 
       return true;
     }
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
     const char *getPassName() const override {
       return "X86 PIC Global Base Reg Initialization";
     }
 
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.setPreservesCFG();
       MachineFunctionPass::getAnalysisUsage(AU);
     }

lib/Target/X86/X86VZeroUpper.cpp

public:
     VZeroUpperInserter() : MachineFunctionPass(ID) {}
     bool runOnMachineFunction(MachineFunction &MF) override;
     MachineFunctionProperties getRequiredProperties() const override {
       return MachineFunctionProperties().set(
           MachineFunctionProperties::Property::AllVRegsAllocated);
     }
     const char *getPassName() const override {return "X86 vzeroupper inserter";}
 
+    // Don't skip this pass while bisecting failures.
+    bool isSkippable() const override { return false; }
+
   private:
 
     void processBasicBlock(MachineBasicBlock &MBB);
     void insertVZeroUpper(MachineBasicBlock::iterator I,
                           MachineBasicBlock &MBB);
     void addDirtySuccessor(MachineBasicBlock &MBB);
 
     typedef enum { PASS_THROUGH, EXITS_CLEAN, EXITS_DIRTY } BlockExitState;

lib/Transforms/IPO/ForceFunctionAttrs.cpp

if (ForceAttributes.empty())
       return false;
 
     for (Function &F : M.functions())
       addForcedAttributes(F);
 
     // Conservatively assume we changed something.
     return true;
   }
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 };
 }
 
 char ForceFunctionAttrsLegacyPass::ID = 0;
 INITIALIZE_PASS(ForceFunctionAttrsLegacyPass, "forceattrs",
                 "Force set function attributes", false, false)
 
 Pass *llvm::createForceFunctionAttrsLegacyPass() {
   return new ForceFunctionAttrsLegacyPass();
 }

lib/Transforms/Scalar/LowerExpectIntrinsic.cpp

 class LowerExpectIntrinsic : public FunctionPass {
 public:
   static char ID;
   LowerExpectIntrinsic() : FunctionPass(ID) {
     initializeLowerExpectIntrinsicPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); }
+
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 };
 }
 
 char LowerExpectIntrinsic::ID = 0;
 INITIALIZE_PASS(LowerExpectIntrinsic, "lower-expect",
                 "Lower 'expect' Intrinsics", false, false)
 
 FunctionPass *llvm::createLowerExpectIntrinsicPass() {
   return new LowerExpectIntrinsic();
 }

lib/Transforms/Utils/AddDiscriminators.cpp

 namespace {
 struct AddDiscriminators : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   AddDiscriminators() : FunctionPass(ID) {
     initializeAddDiscriminatorsPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnFunction(Function &F) override;
+
+  // Don't skip this pass while bisecting failures.
+  bool isSkippable() const override { return false; }
 };
 } // end anonymous namespace
 
 char AddDiscriminators::ID = 0;
 INITIALIZE_PASS_BEGIN(AddDiscriminators, "add-discriminators",
                       "Add DWARF path discriminators", false, false)
 INITIALIZE_PASS_END(AddDiscriminators, "add-discriminators",
                     "Add DWARF path discriminators", false, false)

test/Other/opt-bisect-helper.py

+#!/usr/bin/env python
+
+import os
+import sys
+import argparse
+import subprocess
+
+parser = argparse.ArgumentParser()
+
+parser.add_argument('--start', type=int, default=0)
+parser.add_argument('--end', type=int, default=(1 << 32))
+parser.add_argument('--optcmd', default=("opt"))
+parser.add_argument('--filecheckcmd', default=("FileCheck"))
+parser.add_argument('--prefix', default=("CHECK-BISECT"))
+parser.add_argument('--test', default=(""))
+
+args = parser.parse_args()
+
+start = args.start
+end = args.end
+
+opt_command = [args.optcmd, "-O2", "-opt-bisect-limit=%(count)s", "-S", args.test]
+check_command = [args.filecheckcmd, args.test, "--check-prefix=%s" % args.prefix]
+last = None
+while start != end and start != end-1:
+    count = int(round(start + (end - start)/2))
+    cmd = [x % {'count':count} for x in opt_command]
+    print("opt: " + str(cmd))
+    opt_result = subprocess.Popen(cmd, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
+    filecheck_result = subprocess.Popen(check_command, stdin=opt_result.stdout)
+    opt_result.stdout.close()
+    opt_result.stderr.close()
+    filecheck_result.wait(10)
+    if filecheck_result.returncode == 0:
+        start = count
+    else:
+        end = count
+
+print("Last good count: %d" % start)

test/Other/opt-bisect-legacy-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.
+;
+; This set of tests exercises the legacy pass manager interface to the OptBisect
+; class.  Because the exact set of optimizations that will be run may
+; change over time, these tests are written in a more general manner than the
+; corresponding tests for the new pass manager.
+;
+; Don't use NEXT checks or hard-code pass numbering so that this won't fail if
+; new passes are inserted.
+
+
+; Verify that the file can be compiled to an object file at -O3 with all
+; skippable passes skipped.
+
+; RUN: opt -O3 -opt-bisect-limit=0 < %s | llc -O3 -opt-bisect-limit=0
+
+
+; Verify that no skippable passes are run with -opt-bisect-limit=0.
+
+; RUN: opt -disable-output -disable-verify -debug-pass=Executions \
+; RUN:     -O3 -opt-bisect-limit=0 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-SKIP-ALL
+; CHECK-SKIP-ALL: Executing Pass 'Function Pass Manager' on Module
+; CHECK-SKIP-ALL-NOT: BISECT: running pass ({{[0-9]+}})
+
+
+; Verify that we can use the opt-bisect-helper.py script (derived from
+; utils/bisect) to locate the optimization that inlines the call to
+; f2() in f3().
+
+; RUN: %python %S/opt-bisect-helper.py --start=0 --end=256 --optcmd=opt \
+; RUN:         --filecheckcmd=FileCheck --test=%s \
+; RUN:         --prefix=CHECK-BISECT-INLINE-HELPER \
+; RUN:         | FileCheck %s --check-prefix=CHECK-BISECT-INLINE-RESULT
+; The helper script uses this to find the optimization that inlines the call.
+; CHECK-BISECT-INLINE-HELPER: call i32 @f2()
+; These checks verifies that the optimization was found.
+; CHECK-BISECT-INLINE-RESULT-NOT: Last good count: 0
+; CHECK-BISECT-INLINE-RESULT: Last good count: {{[0-9]+}}
+
+
+; Test a module pass.
+
+; RUN: opt -disable-output -disable-verify -debug-pass=Executions \
+; RUN:     -deadargelim -opt-bisect-limit=-1 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-DEADARG
+; CHECK-DEADARG: BISECT: running pass ({{[0-9]+}}) Dead Argument Elimination on module
+; CHECK-DEADARG: Executing Pass 'Dead Argument Elimination' on Module
+
+; RUN: opt -disable-output -disable-verify -debug-pass=Executions \
+; RUN:     -deadargelim -opt-bisect-limit=0 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-NOT-DEADARG
+; CHECK-NOT-DEADARG: BISECT: NOT running pass ({{[0-9]+}}) Dead Argument Elimination on module
+; CHECK-NOT-DEADARG-NOT: Executing Pass 'Dead Argument Elimination' on Module
+
+
+; Test an SCC pass.
+
+; RUN: opt -disable-output -disable-verify -debug-pass=Executions \
+; RUN:     -inline -opt-bisect-limit=-1 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-INLINE
+; CHECK-INLINE: BISECT: running pass ({{[0-9]+}}) Function Integration/Inlining on SCC (<<null function>>)
+; CHECK-INLINE: Executing Pass 'Function Integration/Inlining' on Call Graph Nodes
+; CHECK-INLINE: BISECT: running pass ({{[0-9]+}}) Function Integration/Inlining on SCC (g)
+; CHECK-INLINE: Executing Pass 'Function Integration/Inlining' on Call Graph Nodes 'Call graph node for function: 'g'
+; CHECK-INLINE: BISECT: running pass ({{[0-9]+}}) Function Integration/Inlining on SCC (f1)
+; CHECK-INLINE: Executing Pass 'Function Integration/Inlining' on Call Graph Nodes 'Call graph node for function: 'f1'
+; CHECK-INLINE: BISECT: running pass ({{[0-9]+}}) Function Integration/Inlining on SCC (f2)
+; CHECK-INLINE: Executing Pass 'Function Integration/Inlining' on Call Graph Nodes 'Call graph node for function: 'f2'
+; CHECK-INLINE: BISECT: running pass ({{[0-9]+}}) Function Integration/Inlining on SCC (f3)
+; CHECK-INLINE: Executing Pass 'Function Integration/Inlining' on Call Graph Nodes 'Call graph node for function: 'f3'
+; CHECK-INLINE: BISECT: running pass ({{[0-9]+}}) Function Integration/Inlining on SCC (<<null function>>)
+; CHECK-INLINE: Executing Pass 'Function Integration/Inlining' on Call Graph Nodes
+
+; RUN: opt -disable-output -disable-verify -debug-pass=Executions \
+; RUN:     -inline -opt-bisect-limit=0 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-NOT-INLINE
+; CHECK-NOT-INLINE: BISECT: NOT running pass ({{[0-9]+}}) Function Integration/Inlining on SCC (<<null function>>)
+; CHECK-NOT-INLINE-NOT: Executing Pass 'Function Integration/Inlining' on Call Graph Nodes
+; CHECK-NOT-INLINE: BISECT: NOT running pass ({{[0-9]+}}) Function Integration/Inlining on SCC (g)
+; CHECK-NOT-INLINE-NOT: Executing Pass 'Function Integration/Inlining' on Call Graph Nodes 'Call graph node for function: 'g'
+; CHECK-NOT-INLINE: BISECT: NOT running pass ({{[0-9]+}}) Function Integration/Inlining on SCC (f1)
+; CHECK-NOT-INLINE-NOT: Executing Pass 'Function Integration/Inlining' on Call Graph Nodes 'Call graph node for function: 'f1'
+; CHECK-NOT-INLINE: BISECT: NOT running pass ({{[0-9]+}}) Function Integration/Inlining on SCC (f2)
+; CHECK-NOT-INLINE-NOT: Executing Pass 'Function Integration/Inlining' on Call Graph Nodes 'Call graph node for function: 'f2'
+; CHECK-NOT-INLINE: BISECT: NOT running pass ({{[0-9]+}}) Function Integration/Inlining on SCC (f3)
+; CHECK-NOT-INLINE-NOT: Executing Pass 'Function Integration/Inlining' on Call Graph Nodes 'Call graph node for function: 'f3'
+; CHECK-NOT-INLINE: BISECT: NOT running pass ({{[0-9]+}}) Function Integration/Inlining on SCC (<<null function>>)
+; CHECK-NOT-INLINE-NOT: Executing Pass 'Function Integration/Inlining' on Call Graph Nodes
+
+
+; Test a function pass.
+
+; RUN: opt -disable-output -disable-verify -debug-pass=Executions \
+; RUN:     -early-cse -opt-bisect-limit=-1 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-EARLY-CSE
+; CHECK-EARLY-CSE: BISECT: running pass ({{[0-9]+}}) Early CSE on function (f1)
+; CHECK-EARLY-CSE: Executing Pass 'Early CSE' on Function 'f1'...
+; CHECK-EARLY-CSE: BISECT: running pass ({{[0-9]+}}) Early CSE on function (f2)
+; CHECK-EARLY-CSE: Executing Pass 'Early CSE' on Function 'f2'...
+; CHECK-EARLY-CSE: BISECT: running pass ({{[0-9]+}}) Early CSE on function (f3)
+; CHECK-EARLY-CSE: Executing Pass 'Early CSE' on Function 'f3'...
+
+; RUN: opt -disable-output -disable-verify -debug-pass=Executions \
+; RUN:     -early-cse -opt-bisect-limit=0 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-NOT-EARLY-CSE
+; CHECK-NOT-EARLY-CSE: BISECT: NOT running pass ({{[0-9]+}}) Early CSE on function (f1)
+; CHECK-NOT-EARLY-CSE-NOT: Executing Pass 'Early CSE' on Function 'f1'...
+; CHECK-NOT-EARLY-CSE: BISECT: NOT running pass ({{[0-9]+}}) Early CSE on function (f2)
+; CHECK-NOT-EARLY-CSE-NOT: Executing Pass 'Early CSE' on Function 'f2'...
+; CHECK-NOT-EARLY-CSE: BISECT: NOT running pass ({{[0-9]+}}) Early CSE on function (f3)
+; CHECK-NOT-EARLY-CSE-NOT: Executing Pass 'Early CSE' on Function 'f3'...
+
+
+; Test a loop pass.
+
+; RUN: opt -disable-output -disable-verify -debug-pass=Executions \
+; RUN:     -loop-reduce -opt-bisect-limit=-1 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-LOOP-REDUCE
+; CHECK-LOOP-REDUCE: BISECT: running necessary pass Loop Pass Manager on function (f1)
+; CHECK-LOOP-REDUCE: Executing Pass 'Loop Pass Manager' on Function 'f1'
+; CHECK-LOOP-REDUCE: BISECT: running analysis pass Induction Variable Users on loop
+; CHECK-LOOP-REDUCE: Executing Pass 'Induction Variable Users' on Loop
+; CHECK-LOOP-REDUCE: BISECT: running pass ({{[0-9]+}}) Loop Strength Reduction on loop
+; CHECK-LOOP-REDUCE: Executing Pass 'Loop Strength Reduction' on Loop
+; CHECK-LOOP-REDUCE: BISECT: running analysis pass Induction Variable Users on loop
+; CHECK-LOOP-REDUCE: Executing Pass 'Induction Variable Users' on Loop
+; CHECK-LOOP-REDUCE: BISECT: running pass ({{[0-9]+}}) Loop Strength Reduction on loop
+; CHECK-LOOP-REDUCE: Executing Pass 'Loop Strength Reduction' on Loop
+; CHECK-LOOP-REDUCE: BISECT: running analysis pass Induction Variable Users on loop
+; CHECK-LOOP-REDUCE: Executing Pass 'Induction Variable Users' on Loop
+; CHECK-LOOP-REDUCE: BISECT: running pass ({{[0-9]+}}) Loop Strength Reduction on loop
+; CHECK-LOOP-REDUCE: Executing Pass 'Loop Strength Reduction' on Loop
+; CHECK-LOOP-REDUCE: BISECT: running analysis pass Induction Variable Users on loop
+; CHECK-LOOP-REDUCE: Executing Pass 'Induction Variable Users' on Loop
+; CHECK-LOOP-REDUCE: BISECT: running pass ({{[0-9]+}}) Loop Strength Reduction on loop
+; CHECK-LOOP-REDUCE: Executing Pass 'Loop Strength Reduction' on Loop
+; CHECK-LOOP-REDUCE: BISECT: running analysis pass Induction Variable Users on loop
+; CHECK-LOOP-REDUCE: Executing Pass 'Induction Variable Users' on Loop
+; CHECK-LOOP-REDUCE: BISECT: running pass ({{[0-9]+}}) Loop Strength Reduction on loop
+; CHECK-LOOP-REDUCE: Executing Pass 'Loop Strength Reduction' on Loop
+
+; RUN: opt -disable-output -disable-verify -debug-pass=Executions \
+; RUN:     -loop-reduce -opt-bisect-limit=0 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-NOT-LOOP-REDUCE
+; CHECK-NOT-LOOP-REDUCE: BISECT: running necessary pass Loop Pass Manager on function (f1)
+; CHECK-NOT-LOOP-REDUCE: Executing Pass 'Loop Pass Manager' on Function 'f1'
+; CHECK-NOT-LOOP-REDUCE: BISECT: running analysis pass Induction Variable Users on loop
+; CHECK-NOT-LOOP-REDUCE: Executing Pass 'Induction Variable Users' on Loop
+; CHECK-NOT-LOOP-REDUCE: BISECT: NOT running pass ({{[0-9]+}}) Loop Strength Reduction on loop
+; CHECK-NOT-LOOP-REDUCE-NOT: Executing Pass 'Loop Strength Reduction' on Loop
+; CHECK-NOT-LOOP-REDUCE: BISECT: running analysis pass Induction Variable Users on loop
+; CHECK-NOT-LOOP-REDUCE: Executing Pass 'Induction Variable Users' on Loop
+; CHECK-NOT-LOOP-REDUCE: BISECT: NOT running pass ({{[0-9]+}}) Loop Strength Reduction on loop
+; CHECK-NOT-LOOP-REDUCE-NOT: Executing Pass 'Loop Strength Reduction' on Loop
+; CHECK-NOT-LOOP-REDUCE: BISECT: running analysis pass Induction Variable Users on loop
+; CHECK-NOT-LOOP-REDUCE: Executing Pass 'Induction Variable Users' on Loop
+; CHECK-NOT-LOOP-REDUCE: BISECT: NOT running pass ({{[0-9]+}}) Loop Strength Reduction on loop
+; CHECK-NOT-LOOP-REDUCE-NOT: Executing Pass 'Loop Strength Reduction' on Loop
+; CHECK-NOT-LOOP-REDUCE: BISECT: running analysis pass Induction Variable Users on loop
+; CHECK-NOT-LOOP-REDUCE: Executing Pass 'Induction Variable Users' on Loop
+; CHECK-NOT-LOOP-REDUCE: BISECT: NOT running pass ({{[0-9]+}}) Loop Strength Reduction on loop
+; CHECK-NOT-LOOP-REDUCE-NOT: Executing Pass 'Loop Strength Reduction' on Loop
+; CHECK-NOT-LOOP-REDUCE: BISECT: running analysis pass Induction Variable Users on loop
+; CHECK-NOT-LOOP-REDUCE: Executing Pass 'Induction Variable Users' on Loop
+; CHECK-NOT-LOOP-REDUCE: BISECT: NOT running pass ({{[0-9]+}}) Loop Strength Reduction on loop
+; CHECK-NOT-LOOP-REDUCE-NOT: Executing Pass 'Loop Strength Reduction' on Loop
+
+
+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
+}

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 -debug-pass-manager \
+; RUN:     -passes=no-op-module -opt-bisect-limit=-1 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-MODULE-PASS
+; CHECK-MODULE-PASS: Starting llvm::Module pass manager run.
+; CHECK-MODULE-PASS-NEXT: BISECT: running pass (1) NoOpModulePass on module
+; CHECK-MODULE-PASS-NEXT: Running pass: NoOpModulePass
+; CHECK-MODULE-PASS-NEXT: Finished llvm::Module pass manager run.
+
+; RUN: opt -disable-output -disable-verify -debug-pass-manager \
+; RUN:     -passes=no-op-module -opt-bisect-limit=0 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-LIMIT-MODULE-PASS
+; CHECK-LIMIT-MODULE-PASS: Starting llvm::Module pass manager run.
+; CHECK-LIMIT-MODULE-PASS-NEXT: BISECT: NOT running pass (1) NoOpModulePass on module
+; CHECK-LIMIT-MODULE-PASS-NOT: Running pass: NoOpModulePass
+; CHECK-LIMIT-MODULE-PASS-NEXT: Finished llvm::Module pass manager run.
+
+; RUN: opt -disable-output -disable-verify -debug-pass-manager \
+; RUN:     -passes=no-op-function -opt-bisect-limit=-1 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-FUNCTION-PASS
+; CHECK-FUNCTION-PASS: Starting llvm::Module pass manager run.
+; CHECK-FUNCTION-PASS-NEXT: BISECT: running necessary pass ModuleToFunctionPassAdaptor
+; CHECK-FUNCTION-PASS-NEXT: Running pass: ModuleToFunctionPassAdaptor
+; CHECK-FUNCTION-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-FUNCTION-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-FUNCTION-PASS-NEXT: BISECT: running pass (1) NoOpFunctionPass on function (f1)
+; CHECK-FUNCTION-PASS-NEXT: Running pass: NoOpFunctionPass
+; CHECK-FUNCTION-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-FUNCTION-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-FUNCTION-PASS-NEXT: BISECT: running pass (2) NoOpFunctionPass on function (f2)
+; CHECK-FUNCTION-PASS-NEXT: Running pass: NoOpFunctionPass
+; CHECK-FUNCTION-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-FUNCTION-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-FUNCTION-PASS-NEXT: BISECT: running pass (3) NoOpFunctionPass on function (f3)
+; CHECK-FUNCTION-PASS-NEXT: Running pass: NoOpFunctionPass
+; CHECK-FUNCTION-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-FUNCTION-PASS-NEXT: Finished llvm::Module pass manager run.
+
+; RUN: opt -disable-output -disable-verify -debug-pass-manager \
+; RUN:     -passes=no-op-function -opt-bisect-limit=2 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-LIMIT-FUNCTION-PASS
+; CHECK-LIMIT-FUNCTION-PASS: Starting llvm::Module pass manager run.
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: BISECT: running necessary pass ModuleToFunctionPassAdaptor
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: Running pass: ModuleToFunctionPassAdaptor
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: BISECT: running pass (1) NoOpFunctionPass on function (f1)
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: Running pass: NoOpFunctionPass
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: BISECT: running pass (2) NoOpFunctionPass on function (f2)
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: Running pass: NoOpFunctionPass
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: BISECT: NOT running pass (3) NoOpFunctionPass on function (f3)
+; CHECK-LIMIT-FUNCTION-PASS-NOT: Running pass: NoOpFunctionPass
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-LIMIT-FUNCTION-PASS-NEXT: Finished llvm::Module pass manager run.
+
+; RUN: opt -disable-output -disable-verify -debug-pass-manager \
+; RUN:     -passes=no-op-cgscc -opt-bisect-limit=-1 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-CGSCC-PASS
+; CHECK-CGSCC-PASS: Starting llvm::Module pass manager run.
+; CHECK-CGSCC-PASS-NEXT: BISECT: running necessary pass ModuleToPostOrderCGSCCPassAdaptor
+; CHECK-CGSCC-PASS-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor
+; CHECK-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-CGSCC-PASS-NEXT: Running analysis: LazyCallGraphAnalysis
+; CHECK-CGSCC-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-CGSCC-PASS-NEXT: BISECT: running pass (1) NoOpCGSCCPass on SCC (f2)
+; CHECK-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
+; CHECK-CGSCC-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-CGSCC-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-CGSCC-PASS-NEXT: BISECT: running pass (2) NoOpCGSCCPass on SCC (f3)
+; CHECK-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
+; CHECK-CGSCC-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-CGSCC-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-CGSCC-PASS-NEXT: BISECT: running pass (3) NoOpCGSCCPass on SCC (f1)
+; CHECK-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
+; CHECK-CGSCC-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-CGSCC-PASS-NEXT: Finished llvm::Module pass manager run.
+
+; RUN: opt -disable-output -disable-verify -debug-pass-manager \
+; RUN:     -passes=no-op-cgscc -opt-bisect-limit=2 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-LIMIT-CGSCC-PASS
+; CHECK-LIMIT-CGSCC-PASS: Starting llvm::Module pass manager run.
+; CHECK-LIMIT-CGSCC-PASS-NEXT: BISECT: running necessary pass ModuleToPostOrderCGSCCPassAdaptor
+; CHECK-LIMIT-CGSCC-PASS-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor
+; CHECK-LIMIT-CGSCC-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-CGSCC-PASS-NEXT: Running analysis: LazyCallGraphAnalysis
+; CHECK-LIMIT-CGSCC-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-LIMIT-CGSCC-PASS-NEXT: BISECT: running pass (1) NoOpCGSCCPass on SCC (f2)
+; CHECK-LIMIT-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
+; CHECK-LIMIT-CGSCC-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-LIMIT-CGSCC-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-LIMIT-CGSCC-PASS-NEXT: BISECT: running pass (2) NoOpCGSCCPass on SCC (f3)
+; CHECK-LIMIT-CGSCC-PASS-NEXT: Running pass: NoOpCGSCCPass
+; CHECK-LIMIT-CGSCC-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-LIMIT-CGSCC-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-LIMIT-CGSCC-PASS-NEXT: BISECT: NOT running pass (3) NoOpCGSCCPass on SCC (f1)
+; CHECK-LIMIT-CGSCC-PASS-NOT: Running pass: NoOpCGSCCPass
+; CHECK-LIMIT-CGSCC-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-LIMIT-CGSCC-PASS-NEXT: Finished llvm::Module pass manager run.
+
+; RUN: opt -disable-output -disable-verify -debug-pass-manager \
+; RUN:     -passes=no-op-loop -opt-bisect-limit=-1 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-LOOP-PASS
+; CHECK-LOOP-PASS: Starting llvm::Module pass manager run.
+; CHECK-LOOP-PASS-NEXT: BISECT: running necessary pass ModuleToFunctionPassAdaptor
+; CHECK-LOOP-PASS-NEXT: Running pass: ModuleToFunctionPassAdaptor
+; CHECK-LOOP-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LOOP-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-LOOP-PASS-NEXT: BISECT: running necessary pass FunctionToLoopPassAdaptor
+; CHECK-LOOP-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
+; CHECK-LOOP-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LOOP-PASS-NEXT: Running analysis: LoopAnalysis
+; CHECK-LOOP-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-LOOP-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LOOP-PASS-NEXT: BISECT: running pass (1) NoOpLoopPass on loop
+; CHECK-LOOP-PASS-NEXT: Running pass: NoOpLoopPass on loop.1.0
+; CHECK-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LOOP-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LOOP-PASS-NEXT: BISECT: running pass (2) NoOpLoopPass on loop
+; CHECK-LOOP-PASS-NEXT: Running pass: NoOpLoopPass on loop.1
+; CHECK-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LOOP-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LOOP-PASS-NEXT: BISECT: running pass (3) NoOpLoopPass on loop
+; CHECK-LOOP-PASS-NEXT: Running pass: NoOpLoopPass on loop.0.0
+; CHECK-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LOOP-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LOOP-PASS-NEXT: BISECT: running pass (4) NoOpLoopPass on loop
+; CHECK-LOOP-PASS-NEXT: Running pass: NoOpLoopPass on loop.0.1
+; CHECK-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LOOP-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LOOP-PASS-NEXT: BISECT: running pass (5) NoOpLoopPass on loop
+; CHECK-LOOP-PASS-NEXT: Running pass: NoOpLoopPass on loop.0
+; CHECK-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LOOP-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-LOOP-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-LOOP-PASS-NEXT: BISECT: running necessary pass FunctionToLoopPassAdaptor
+; CHECK-LOOP-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
+; CHECK-LOOP-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LOOP-PASS-NEXT: Running analysis: LoopAnalysis
+; CHECK-LOOP-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-LOOP-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-LOOP-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-LOOP-PASS-NEXT: BISECT: running necessary pass FunctionToLoopPassAdaptor
+; CHECK-LOOP-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
+; CHECK-LOOP-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LOOP-PASS-NEXT: Running analysis: LoopAnalysis
+; CHECK-LOOP-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-LOOP-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-LOOP-PASS-NEXT: Finished llvm::Module pass manager run.
+
+; RUN: opt -disable-output -disable-verify -debug-pass-manager \
+; RUN:     -passes=no-op-loop -opt-bisect-limit=2 %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-LIMIT-LOOP-PASS
+; CHECK-LIMIT-LOOP-PASS: Starting llvm::Module pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: BISECT: running necessary pass ModuleToFunctionPassAdaptor
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running pass: ModuleToFunctionPassAdaptor
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-LOOP-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: BISECT: running necessary pass FunctionToLoopPassAdaptor
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running analysis: LoopAnalysis
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-LIMIT-LOOP-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: BISECT: running pass (1) NoOpLoopPass on loop
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running pass: NoOpLoopPass on loop.1.0
+; CHECK-LIMIT-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: BISECT: running pass (2) NoOpLoopPass on loop
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running pass: NoOpLoopPass on loop.1
+; CHECK-LIMIT-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: BISECT: NOT running pass (3) NoOpLoopPass on loop
+; CHECK-LIMIT-LOOP-PASS-NOT: Running pass: NoOpLoopPass on loop.0.0
+; CHECK-LIMIT-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: BISECT: NOT running pass (4) NoOpLoopPass on loop
+; CHECK-LIMIT-LOOP-PASS-NOT: Running pass: NoOpLoopPass on loop.0.1
+; CHECK-LIMIT-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: BISECT: NOT running pass (5) NoOpLoopPass on loop
+; CHECK-LIMIT-LOOP-PASS-NOT: Running pass: NoOpLoopPass on loop.0
+; CHECK-LIMIT-LOOP-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: BISECT: running necessary pass FunctionToLoopPassAdaptor
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running analysis: LoopAnalysis
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-LIMIT-LOOP-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: BISECT: running necessary pass FunctionToLoopPassAdaptor
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running analysis: LoopAnalysis
+; CHECK-LIMIT-LOOP-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-LIMIT-LOOP-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-LIMIT-LOOP-PASS-NEXT: Finished llvm::Module pass manager run.
+
+; RUN: opt -disable-output -disable-verify -debug-pass-manager -opt-bisect-limit=-1 \
+; RUN:     -passes='no-op-module,cgscc(no-op-cgscc,function(no-op-function,loop(no-op-loop)))' %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-MULTI-PASS
+; CHECK-MULTI-PASS: Starting llvm::Module pass manager run.
+; CHECK-MULTI-PASS-NEXT: BISECT: running pass (1) NoOpModulePass on module
+; CHECK-MULTI-PASS-NEXT: Running pass: NoOpModulePass
+; CHECK-MULTI-PASS-NEXT: BISECT: running necessary pass ModuleToPostOrderCGSCCPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-MULTI-PASS-NEXT: Running analysis: LazyCallGraphAnalysis
+; CHECK-MULTI-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-MULTI-PASS-NEXT: BISECT: running pass (2) NoOpCGSCCPass on SCC (f2)
+; CHECK-MULTI-PASS-NEXT: Running pass: NoOpCGSCCPass on f2
+; CHECK-MULTI-PASS-NEXT: BISECT: running necessary pass CGSCCToFunctionPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running pass: CGSCCToFunctionPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-MULTI-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-MULTI-PASS-NEXT: BISECT: running pass (3) NoOpFunctionPass on function (f2)
+; CHECK-MULTI-PASS-NEXT: Running pass: NoOpFunctionPass on f2
+; CHECK-MULTI-PASS-NEXT: BISECT: running necessary pass FunctionToLoopPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-MULTI-PASS-NEXT: Running analysis: LoopAnalysis
+; CHECK-MULTI-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-MULTI-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-MULTI-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-MULTI-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-MULTI-PASS-NEXT: BISECT: running pass (4) NoOpCGSCCPass on SCC (f3)
+; CHECK-MULTI-PASS-NEXT: Running pass: NoOpCGSCCPass on f3
+; CHECK-MULTI-PASS-NEXT: BISECT: running necessary pass CGSCCToFunctionPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running pass: CGSCCToFunctionPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-MULTI-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-MULTI-PASS-NEXT: BISECT: running pass (5) NoOpFunctionPass on function (f3)
+; CHECK-MULTI-PASS-NEXT: Running pass: NoOpFunctionPass on f3
+; CHECK-MULTI-PASS-NEXT: BISECT: running necessary pass FunctionToLoopPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-MULTI-PASS-NEXT: Running analysis: LoopAnalysis
+; CHECK-MULTI-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-MULTI-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-MULTI-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-MULTI-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-MULTI-PASS-NEXT: BISECT: running pass (6) NoOpCGSCCPass on SCC (f1)
+; CHECK-MULTI-PASS-NEXT: Running pass: NoOpCGSCCPass on f1
+; CHECK-MULTI-PASS-NEXT: BISECT: running necessary pass CGSCCToFunctionPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running pass: CGSCCToFunctionPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-MULTI-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-MULTI-PASS-NEXT: BISECT: running pass (7) NoOpFunctionPass on function (f1)
+; CHECK-MULTI-PASS-NEXT: Running pass: NoOpFunctionPass on f1
+; CHECK-MULTI-PASS-NEXT: BISECT: running necessary pass FunctionToLoopPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
+; CHECK-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-MULTI-PASS-NEXT: Running analysis: LoopAnalysis
+; CHECK-MULTI-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-MULTI-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-MULTI-PASS-NEXT: BISECT: running pass (8) NoOpLoopPass on loop
+; CHECK-MULTI-PASS-NEXT: Running pass: NoOpLoopPass on loop.1.0
+; CHECK-MULTI-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-MULTI-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-MULTI-PASS-NEXT: BISECT: running pass (9) NoOpLoopPass on loop
+; CHECK-MULTI-PASS-NEXT: Running pass: NoOpLoopPass on loop.1
+; CHECK-MULTI-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-MULTI-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-MULTI-PASS-NEXT: BISECT: running pass (10) NoOpLoopPass on loop
+; CHECK-MULTI-PASS-NEXT: Running pass: NoOpLoopPass on loop.0.0
+; CHECK-MULTI-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-MULTI-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-MULTI-PASS-NEXT: BISECT: running pass (11) NoOpLoopPass on loop
+; CHECK-MULTI-PASS-NEXT: Running pass: NoOpLoopPass on loop.0.1
+; CHECK-MULTI-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-MULTI-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-MULTI-PASS-NEXT: BISECT: running pass (12) NoOpLoopPass on loop
+; CHECK-MULTI-PASS-NEXT: Running pass: NoOpLoopPass on loop.0
+; CHECK-MULTI-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-MULTI-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-MULTI-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-MULTI-PASS-NEXT: Finished llvm::Module pass manager run.
+
+; RUN: opt -disable-output -disable-verify -debug-pass-manager -opt-bisect-limit=8 \
+; RUN:     -passes='no-op-module,cgscc(no-op-cgscc,function(no-op-function,loop(no-op-loop)))' %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-LIMIT-MULTI-PASS
+; CHECK-LIMIT-MULTI-PASS: Starting llvm::Module pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running pass (1) NoOpModulePass on module
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: NoOpModulePass
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running necessary pass ModuleToPostOrderCGSCCPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: LazyCallGraphAnalysis
+; CHECK-LIMIT-MULTI-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running pass (2) NoOpCGSCCPass on SCC (f2)
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: NoOpCGSCCPass on f2
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running necessary pass CGSCCToFunctionPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: CGSCCToFunctionPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-MULTI-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running pass (3) NoOpFunctionPass on function (f2)
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: NoOpFunctionPass on f2
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running necessary pass FunctionToLoopPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: LoopAnalysis
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-LIMIT-MULTI-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running pass (4) NoOpCGSCCPass on SCC (f3)
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: NoOpCGSCCPass on f3
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running necessary pass CGSCCToFunctionPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: CGSCCToFunctionPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-MULTI-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running pass (5) NoOpFunctionPass on function (f3)
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: NoOpFunctionPass on f3
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running necessary pass FunctionToLoopPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: LoopAnalysis
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-LIMIT-MULTI-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: Starting llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running pass (6) NoOpCGSCCPass on SCC (f1)
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: NoOpCGSCCPass on f1
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running necessary pass CGSCCToFunctionPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: CGSCCToFunctionPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-MULTI-PASS-NEXT: Starting llvm::Function pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running pass (7) NoOpFunctionPass on function (f1)
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: NoOpFunctionPass on f1
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running necessary pass FunctionToLoopPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: LoopAnalysis
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-LIMIT-MULTI-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: running pass (8) NoOpLoopPass on loop
+; CHECK-LIMIT-MULTI-PASS-NEXT: Running pass: NoOpLoopPass on loop.1.0
+; CHECK-LIMIT-MULTI-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: NOT running pass (9) NoOpLoopPass on loop
+; CHECK-LIMIT-MULTI-PASS-NOT: Running pass: NoOpLoopPass on loop.1
+; CHECK-LIMIT-MULTI-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: NOT running pass (10) NoOpLoopPass on loop
+; CHECK-LIMIT-MULTI-PASS-NOT: Running pass: NoOpLoopPass on loop.0.0
+; CHECK-LIMIT-MULTI-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: NOT running pass (11) NoOpLoopPass on loop
+; CHECK-LIMIT-MULTI-PASS-NOT: Running pass: NoOpLoopPass on loop.0.1
+; CHECK-LIMIT-MULTI-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: Starting llvm::Loop pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: BISECT: NOT running pass (12) NoOpLoopPass on loop
+; CHECK-LIMIT-MULTI-PASS-NOT: Running pass: NoOpLoopPass on loop.0
+; CHECK-LIMIT-MULTI-PASS-NEXT: Finished llvm::Loop pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: Finished llvm::Function pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: Finished llvm::LazyCallGraph::SCC pass manager run.
+; CHECK-LIMIT-MULTI-PASS-NEXT: Finished llvm::Module pass manager run.
+
+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
+}

unittests/Analysis/CGSCCPassManagerTest.cpp

struct TestModulePass {
   TestModulePass(int &RunCount) : RunCount(RunCount) {}
 
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) {
     ++RunCount;
     (void)AM.getResult<TestModuleAnalysis>(M);
     return PreservedAnalyses::all();
   }
 
+  bool isSkippable() const { return true; }
+
   static StringRef name() { return "TestModulePass"; }
 
   int &RunCount;
 };
 
 struct TestSCCPass {
   TestSCCPass(int &RunCount, int &AnalyzedInstrCount,
                    int &AnalyzedSCCFunctionCount,
if (OnlyUseCachedResults) {
         // Just ensure we get the immutable results.
         (void)FAM.getResult<TestImmutableFunctionAnalysis>(N.getFunction());
       }
     }
 
     return PreservedAnalyses::all();
   }
 
+  bool isSkippable() const { return true; }
+
   static StringRef name() { return "TestSCCPass"; }
 
   int &RunCount;
   int &AnalyzedInstrCount;
   int &AnalyzedSCCFunctionCount;
   int &AnalyzedModuleFunctionCount;
   bool OnlyUseCachedResults;
 };
 
 struct TestFunctionPass {
   TestFunctionPass(int &RunCount) : RunCount(RunCount) {}
 
   PreservedAnalyses run(Function &M) {
     ++RunCount;
     return PreservedAnalyses::none();
   }
 
+  bool isSkippable() const { return true; }
+
   static StringRef name() { return "TestFunctionPass"; }
 
   int &RunCount;
 };
 
 std::unique_ptr<Module> parseIR(const char *IR) {
   LLVMContext &C = getGlobalContext();
   SMDiagnostic Err;

unittests/Analysis/LoopPassManagerTest.cpp

if (OnlyUseCachedResults) {
       // Typical path just runs the analysis as needed.
       auto &AR = AM.getResult<TestLoopAnalysis>(L);
       AnalyzedBlockCount += AR.BlockCount;
     }
 
     return PreservedAnalyses::all();
   }
 
+  bool isSkippable() const { return true; }
+
   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<Loop> &AM) {
     return L.getName() == Name ? PreservedAnalyses::none()
                                : PreservedAnalyses::all();
   }
 
+  bool isSkippable() const { return true; }
+
   static StringRef name() { return "TestLoopInvalidatingPass"; }
 };
 
 std::unique_ptr<Module> parseIR(const char *IR) {
   LLVMContext &C = getGlobalContext();
   SMDiagnostic Err;
   return parseAssemblyString(IR, Err, C);
 }