Initial implementation of optimization bisect support.

This patch implements a optimization bisect feature, which will allow optimizations to be selectively disabled at compile time in order to track down test failures that are caused by incorrect optimizations.

The bisection is enabled using a new command line option (-opt-bisect-limit).  Individual passes that may be skipped call the OptBisect object (via an LLVMContext) to see if they should be skipped based on the bisect limit.  A finer level of control (disabling individual transformations) can be managed through an addition OptBisect method, but this is not yet used.

The skip checking in this implementation is based on (and replaces) the skipOptnoneFunction check.  Where that check was being called, a new call has been inserted in its place which checks the bisect limit and the optnone attribute.  A new function call has been added for module and SCC passes that behaves in a similar way.

Differential Revision: http://reviews.llvm.org/D19172

llvm-svn: 267022

6 files changed, 178 insertions, 10 deletions

diff --git a/llvm/include/llvm/Analysis/CallGraphSCCPass.h b/llvm/include/llvm/Analysis/CallGraphSCCPass.h
index 9c7f7bd34cc..fd9ea56385d 100644
--- a/llvm/include/llvm/Analysis/CallGraphSCCPass.h
+++ b/llvm/include/llvm/Analysis/CallGraphSCCPass.h
@@ -77,15 +77,21 @@ public:
   /// the call graph.  If the derived class implements this method, it should
   /// always explicitly call the implementation here.
   void getAnalysisUsage(AnalysisUsage &Info) const override;
+
+protected:
+  /// Optional passes call this function to check whether the pass should be
+  /// skipped. This is the case when optimization bisect is over the limit.
+  bool skipSCC(CallGraphSCC &SCC) const;
 };
 
 /// CallGraphSCC - This is a single SCC that a CallGraphSCCPass is run on.
 class CallGraphSCC {
+  const CallGraph &CG; // The call graph for this SCC.
   void *Context; // The CGPassManager object that is vending this.
   std::vector<CallGraphNode*> Nodes;
 
 public:
-  CallGraphSCC(void *context) : Context(context) {}
+  CallGraphSCC(CallGraph &cg, void *context) : CG(cg), Context(context) {}
 
   void initialize(CallGraphNode *const *I, CallGraphNode *const *E) {
     Nodes.assign(I, E);
@@ -101,6 +107,8 @@ public:
   typedef std::vector<CallGraphNode *>::const_iterator iterator;
   iterator begin() const { return Nodes.begin(); }
   iterator end() const { return Nodes.end(); }
+
+  const CallGraph &getCallGraph() { return CG; }
 };
 
 } // End llvm namespace
diff --git a/llvm/include/llvm/Analysis/LazyCallGraph.h b/llvm/include/llvm/Analysis/LazyCallGraph.h
index 4e72052b9b8..b3e919d1626 100644
--- a/llvm/include/llvm/Analysis/LazyCallGraph.h
+++ b/llvm/include/llvm/Analysis/LazyCallGraph.h
@@ -923,6 +923,15 @@ public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 };
 
+/// Check with the OptBisect object to determine whether the described pass
+/// should be skipped.
+///
+/// This is a helper function which abstracts the details of accessing OptBisect
+/// through an LLVMContext obtained from an SCC.
+bool skipPassForSCC(const StringRef PassName, const LazyCallGraph::SCC &SCC);
+// This function is implemented in OptBisect.cpp but must be declared
+// here to avoid include file dependency problems.
+
 }
 
 #endif
diff --git a/llvm/include/llvm/Analysis/LoopPass.h b/llvm/include/llvm/Analysis/LoopPass.h
index 2cf734e53bb..89debec04e9 100644
--- a/llvm/include/llvm/Analysis/LoopPass.h
+++ b/llvm/include/llvm/Analysis/LoopPass.h
@@ -88,9 +88,10 @@ public:
   virtual void deleteAnalysisLoop(Loop *L) {}
 
 protected:
-  /// skipOptnoneFunction - Containing function has Attribute::OptimizeNone
-  /// and most transformation passes should skip it.
-  bool skipOptnoneFunction(const Loop *L) 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 skipLoop(const Loop *L) const;
 };
 
 class LPPassManager : public FunctionPass, public PMDataManager {
diff --git a/llvm/include/llvm/IR/LLVMContext.h b/llvm/include/llvm/IR/LLVMContext.h
index 1d05269ab73..8f13171f962 100644
--- a/llvm/include/llvm/IR/LLVMContext.h
+++ b/llvm/include/llvm/IR/LLVMContext.h
@@ -32,6 +32,7 @@ class DiagnosticInfo;
 template <typename T> class SmallVectorImpl;
 class Function;
 class DebugLoc;
+class OptBisect;
 
 /// This is an important class for using LLVM in a threaded context.  It
 /// (opaquely) owns and manages the core "global" data of LLVM's core
@@ -226,6 +227,9 @@ public:
     return OptionRegistry::instance().template get<ValT, Base, Mem>();
   }
 
+  /// \brief Access the object which manages optimization bisection for failure
+  /// analysis.
+  OptBisect &getOptBisect();
 private:
   LLVMContext(LLVMContext&) = delete;
   void operator=(LLVMContext&) = delete;
diff --git a/llvm/include/llvm/IR/OptBisect.h b/llvm/include/llvm/IR/OptBisect.h
new file mode 100644
index 00000000000..d4c8fcf9a44
--- /dev/null
+++ b/llvm/include/llvm/IR/OptBisect.h
@@ -0,0 +1,139 @@
+//===----------- 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.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file declares the interface for bisecting optimizations.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_OPTBISECT_H
+#define LLVM_IR_OPTBISECT_H
+
+namespace llvm {
+
+class Pass;
+class StringRef;
+class Twine;
+
+/// This class implements a mechanism to disable passes and individual
+/// optimizations at compile time based on a command line option
+/// (-opt-bisect-limit) in order to perform a bisecting search for
+/// optimization-related problems.
+class OptBisect {
+public:
+  /// \brief Default constructor, initializes the OptBisect state based on the
+  /// -opt-bisect-limit command line argument.
+  ///
+  /// By default, bisection is disabled.
+  ///
+  /// Clients should not instantiate this class directly.  All access should go
+  /// through LLVMContext.
+  OptBisect();
+
+  /// Checks the bisect limit to determine if the specified pass should run.
+  ///
+  /// This function will immediate return true if bisection is disabled. If the
+  /// bisect limit is set to -1, the function will print a message describing
+  /// the pass and the bisect number assigned to it and return true.  Otherwise,
+  /// the function will print a message with the bisect number assigned to the
+  /// pass and indicating whether or not the pass will be run and return true if
+  /// the bisect limit has not yet been exceded or false if it has.
+  ///
+  /// Most passes should not call this routine directly.  Instead, it is called
+  /// through a helper routine provided by the pass base class.  For instance,
+  /// function passes should call FunctionPass::skipFunction().
+  template <class UnitT>
+  bool shouldRunPass(const Pass *P, const UnitT &U);
+
+  /// Checks the bisect limit to determine if the specified pass should run.
+  ///
+  /// This function will immediate return true if bisection is disabled. If the
+  /// bisect limit is set to -1, the function will print a message describing
+  /// the pass and the bisect number assigned to it and return true.  Otherwise,
+  /// the function will print a message with the bisect number assigned to the
+  /// pass and indicating whether or not the pass will be run and return true if
+  /// the bisect limit has not yet been exceded or false if it has.
+  ///
+  /// In order to avoid duplicating the code necessary to access OptBisect
+  /// through the LLVMContext class, passes may call one of the helper
+  /// functions that get the context from an IR object.  For instance,
+  /// function passes may call skipPassForFunction().
+  template <class UnitT>
+  bool shouldRunPass(const StringRef PassName, const UnitT &U);
+
+  /// Checks the bisect limit to determine if the optimization described by the
+  /// /p Desc argument should run.
+  ///
+  /// This function will immediate return true if bisection is disabled. If the
+  /// bisect limit is set to -1, the function will print a message with the
+  /// bisect number assigned to the optimization along with the /p Desc
+  /// description and return true.  Otherwise, the function will print a message
+  /// with the bisect number assigned to the optimization and indicating whether
+  /// or not the pass will be run and return true if the bisect limit has not
+  /// yet been exceded or false if it has.
+  ///
+  /// Passes may call this function to provide more fine grained control over
+  /// individual optimizations performed by the pass.  Passes which cannot be
+  /// skipped entirely (such as non-optional code generation passes) may still
+  /// call this function to control whether or not individual optional
+  /// transformations are performed.
+  bool shouldRunCase(const Twine &Desc);
+
+private:
+  bool checkPass(const StringRef PassName, const StringRef TargetDesc);
+
+  bool BisectEnabled = false;
+  unsigned LastBisectNum = 0;
+};
+
+// Access to OptBisect should go through LLVMContext, but for the
+// new pass manager there is no single base class from which a
+// helper function to abstract the messy details can be provided.
+// Instead, we provide standalone helper functions for each IR
+// type that must be handled.
+
+class Module;
+class Function;
+//class BasicBlock;
+//class Loop;
+
+/// Check with the OptBisect object to determine whether the described pass
+/// should be skipped.
+///
+/// This is a helper function which abstracts the details of accessing OptBisect
+/// through an LLVMContext obtained from a Module.
+bool skipPassForModule(const StringRef PassName, const Module &M);
+
+/// Check with the OptBisect object to determine whether the described pass
+/// should be skipped.
+///
+/// This is a helper function which abstracts the details of accessing OptBisect
+/// through an LLVMContext obtained from a Function.
+bool skipPassForFunction(const StringRef PassName, const Function &F);
+#if 0
+/// Check with the OptBisect object to determine whether the described pass
+/// should be skipped.
+///
+/// This is a helper function which abstracts the details of accessing OptBisect
+/// through an LLVMContext obtained from a BasicBlock.
+bool skipPassForBasicBlock(const StringRef PassName, const BasicBlock &BB);
+
+/// Check with the OptBisect object to determine whether the described pass
+/// should be skipped.
+///
+/// This is a helper function which abstracts the details of accessing OptBisect
+/// through an LLVMContext obtained from a Loop.
+bool skipPassForLoop(const StringRef PassName, const Loop &L);
+#endif
+// skiPassForSCC is declared in LazyCallGraph.h because of include file
+// dependency issues related to LazyCallGraph::SCC being nested.
+
+} // end namespace llvm
+
+#endif // LLVM_IR_OPTBISECT_H
diff --git a/llvm/include/llvm/Pass.h b/llvm/include/llvm/Pass.h
index 99604cdbc9c..7fcdcbc22bc 100644
--- a/llvm/include/llvm/Pass.h
+++ b/llvm/include/llvm/Pass.h
@@ -251,6 +251,11 @@ public:
   explicit ModulePass(char &pid) : Pass(PT_Module, pid) {}
   // Force out-of-line virtual method.
   ~ModulePass() override;
+
+protected:
+  /// Optional passes call this function to check whether the pass should be
+  /// skipped. This is the case when optimization bisect is over the limit.
+  bool skipModule(Module &M) const;
 };
 
 
@@ -310,9 +315,10 @@ public:
   PassManagerType getPotentialPassManagerType() const override;
 
 protected:
-  /// 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;
 };
 
 
@@ -359,9 +365,10 @@ public:
   PassManagerType getPotentialPassManagerType() const override;
 
 protected:
-  /// skipOptnoneFunction - Containing function has Attribute::OptimizeNone
-  /// and most transformation passes should skip it.
-  bool skipOptnoneFunction(const BasicBlock &BB) 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 skipBasicBlock(const BasicBlock &BB) const;
 };
 
 /// If the user specifies the -time-passes argument on an LLVM tool command line