Index: include/llvm/Analysis/LoopPass.h =================================================================== --- include/llvm/Analysis/LoopPass.h +++ include/llvm/Analysis/LoopPass.h @@ -102,6 +102,9 @@ /// 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; Index: include/llvm/Analysis/RegionPass.h =================================================================== --- include/llvm/Analysis/RegionPass.h +++ include/llvm/Analysis/RegionPass.h @@ -97,6 +97,9 @@ /// @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; Index: include/llvm/Bitcode/BitcodeWriterPass.h =================================================================== --- include/llvm/Bitcode/BitcodeWriterPass.h +++ include/llvm/Bitcode/BitcodeWriterPass.h @@ -63,6 +63,10 @@ /// 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"; } }; Index: include/llvm/CodeGen/AsmPrinter.h =================================================================== --- include/llvm/CodeGen/AsmPrinter.h +++ include/llvm/CodeGen/AsmPrinter.h @@ -207,6 +207,9 @@ 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. //===------------------------------------------------------------------===// Index: include/llvm/CodeGen/LiveIntervalAnalysis.h =================================================================== --- include/llvm/CodeGen/LiveIntervalAnalysis.h +++ include/llvm/CodeGen/LiveIntervalAnalysis.h @@ -266,6 +266,9 @@ /// 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; Index: include/llvm/CodeGen/LiveRegMatrix.h =================================================================== --- include/llvm/CodeGen/LiveRegMatrix.h +++ include/llvm/CodeGen/LiveRegMatrix.h @@ -59,6 +59,9 @@ 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(); Index: include/llvm/CodeGen/LiveStackAnalysis.h =================================================================== --- include/llvm/CodeGen/LiveStackAnalysis.h +++ include/llvm/CodeGen/LiveStackAnalysis.h @@ -90,6 +90,9 @@ /// 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; }; Index: include/llvm/CodeGen/LiveVariables.h =================================================================== --- include/llvm/CodeGen/LiveVariables.h +++ include/llvm/CodeGen/LiveVariables.h @@ -183,6 +183,9 @@ 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; Index: include/llvm/CodeGen/MachineFunctionAnalysis.h =================================================================== --- include/llvm/CodeGen/MachineFunctionAnalysis.h +++ include/llvm/CodeGen/MachineFunctionAnalysis.h @@ -48,6 +48,9 @@ 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 Index: include/llvm/CodeGen/SelectionDAGISel.h =================================================================== --- include/llvm/CodeGen/SelectionDAGISel.h +++ include/llvm/CodeGen/SelectionDAGISel.h @@ -66,6 +66,9 @@ 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 Index: include/llvm/CodeGen/SlotIndexes.h =================================================================== --- include/llvm/CodeGen/SlotIndexes.h +++ include/llvm/CodeGen/SlotIndexes.h @@ -390,6 +390,9 @@ 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; Index: include/llvm/CodeGen/VirtRegMap.h =================================================================== --- include/llvm/CodeGen/VirtRegMap.h +++ include/llvm/CodeGen/VirtRegMap.h @@ -72,6 +72,9 @@ 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); Index: include/llvm/IR/IRPrintingPasses.h =================================================================== --- include/llvm/IR/IRPrintingPasses.h +++ include/llvm/IR/IRPrintingPasses.h @@ -68,7 +68,7 @@ bool ShouldPreserveUseListOrder = false); PreservedAnalyses run(Module &M); - + bool isSkippable() const { return false; } static StringRef name() { return "PrintModulePass"; } }; @@ -85,7 +85,7 @@ PrintFunctionPass(raw_ostream &OS, const std::string &Banner = ""); PreservedAnalyses run(Function &F); - + bool isSkippable() const { return false; } static StringRef name() { return "PrintFunctionPass"; } }; Index: include/llvm/IR/LegacyPassManagers.h =================================================================== --- include/llvm/IR/LegacyPassManagers.h +++ include/llvm/IR/LegacyPassManagers.h @@ -458,6 +458,9 @@ /// 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 /// Index: include/llvm/IR/OptBisect.h =================================================================== --- include/llvm/IR/OptBisect.h +++ include/llvm/IR/OptBisect.h @@ -0,0 +1,50 @@ +//===----------- 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 + bool shouldRunPass(const Pass *P, const UnitT *U); + + // Interface function for the new pass manager. + template + bool shouldRunPass(detail::PassConcept *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 Index: include/llvm/IR/PassManager.h =================================================================== --- include/llvm/IR/PassManager.h +++ include/llvm/IR/PassManager.h @@ -42,6 +42,7 @@ #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" @@ -179,6 +180,8 @@ Name = Name.drop_front(strlen("llvm::")); return Name; } + + bool isSkippable() const { return true; } }; /// A CRTP mix-in to automatically provide informational APIs needed for @@ -242,6 +245,8 @@ dbgs() << "Starting " << getTypeName() << " 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"; @@ -276,6 +281,9 @@ 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: Index: include/llvm/IR/PassManagerInternal.h =================================================================== --- include/llvm/IR/PassManagerInternal.h +++ include/llvm/IR/PassManagerInternal.h @@ -42,6 +42,10 @@ /// analysis manager in the pass pipeline. virtual PreservedAnalyses run(IRUnitT &IR, AnalysisManager &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; }; @@ -99,6 +103,7 @@ PreservedAnalysesT run(IRUnitT &IR, AnalysisManager &AM) override { return Pass.run(IR, AM); } + bool isSkippable() const override { return Pass.isSkippable(); } StringRef name() override { return PassT::name(); } PassT Pass; }; @@ -125,6 +130,7 @@ PreservedAnalysesT run(IRUnitT &IR, AnalysisManager &) override { return Pass.run(IR); } + bool isSkippable() const override { return Pass.isSkippable(); } StringRef name() override { return PassT::name(); } PassT Pass; }; Index: include/llvm/IR/Verifier.h =================================================================== --- include/llvm/IR/Verifier.h +++ include/llvm/IR/Verifier.h @@ -68,6 +68,9 @@ 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 Index: include/llvm/Pass.h =================================================================== --- include/llvm/Pass.h +++ include/llvm/Pass.h @@ -115,6 +115,13 @@ /// 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 Index: include/llvm/Transforms/IPO/ForceFunctionAttrs.h =================================================================== --- include/llvm/Transforms/IPO/ForceFunctionAttrs.h +++ include/llvm/Transforms/IPO/ForceFunctionAttrs.h @@ -23,6 +23,8 @@ /// a debugging tool. struct ForceFunctionAttrsPass : PassInfoMixin { 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. Index: lib/Analysis/CallGraphSCCPass.cpp =================================================================== --- lib/Analysis/CallGraphSCCPass.cpp +++ lib/Analysis/CallGraphSCCPass.cpp @@ -20,6 +20,7 @@ #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" @@ -53,6 +54,9 @@ /// 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; @@ -115,6 +119,9 @@ PMDataManager *PM = P->getAsPMDataManager(); if (!PM) { + if (!getOptBisector().shouldRunPass(P, &CurSCC)) + return false; + CallGraphSCCPass *CGSP = (CallGraphSCCPass*)P; if (!CallGraphUpToDate) { DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false); Index: lib/Analysis/LoopPass.cpp =================================================================== --- lib/Analysis/LoopPass.cpp +++ lib/Analysis/LoopPass.cpp @@ -14,6 +14,7 @@ //===----------------------------------------------------------------------===// #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" @@ -185,6 +186,9 @@ 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); Index: lib/Analysis/RegionPass.cpp =================================================================== --- lib/Analysis/RegionPass.cpp +++ lib/Analysis/RegionPass.cpp @@ -15,6 +15,7 @@ //===----------------------------------------------------------------------===// #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" @@ -84,6 +85,9 @@ 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()); Index: lib/CodeGen/DwarfEHPrepare.cpp =================================================================== --- lib/CodeGen/DwarfEHPrepare.cpp +++ lib/CodeGen/DwarfEHPrepare.cpp @@ -69,6 +69,9 @@ 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 { Index: lib/CodeGen/ExpandISelPseudos.cpp =================================================================== --- lib/CodeGen/ExpandISelPseudos.cpp +++ lib/CodeGen/ExpandISelPseudos.cpp @@ -33,6 +33,9 @@ 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); } Index: lib/CodeGen/ExpandPostRAPseudos.cpp =================================================================== --- lib/CodeGen/ExpandPostRAPseudos.cpp +++ lib/CodeGen/ExpandPostRAPseudos.cpp @@ -47,6 +47,8 @@ /// 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); Index: lib/CodeGen/FuncletLayout.cpp =================================================================== --- lib/CodeGen/FuncletLayout.cpp +++ lib/CodeGen/FuncletLayout.cpp @@ -28,6 +28,9 @@ } bool runOnMachineFunction(MachineFunction &F) override; + + // Don't skip this pass while bisecting failures. + bool isSkippable() const override { return false; } }; } Index: lib/CodeGen/GCRootLowering.cpp =================================================================== --- lib/CodeGen/GCRootLowering.cpp +++ lib/CodeGen/GCRootLowering.cpp @@ -50,6 +50,8 @@ 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 @@ -75,6 +77,9 @@ 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; } }; } Index: lib/CodeGen/LiveDebugValues.cpp =================================================================== --- lib/CodeGen/LiveDebugValues.cpp +++ lib/CodeGen/LiveDebugValues.cpp @@ -105,6 +105,9 @@ /// 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 Index: lib/CodeGen/LiveDebugVariables.h =================================================================== --- lib/CodeGen/LiveDebugVariables.h +++ lib/CodeGen/LiveDebugVariables.h @@ -68,6 +68,8 @@ 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 Index: lib/CodeGen/LocalStackSlotAllocation.cpp =================================================================== --- lib/CodeGen/LocalStackSlotAllocation.cpp +++ lib/CodeGen/LocalStackSlotAllocation.cpp @@ -82,6 +82,9 @@ } 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(); Index: lib/CodeGen/MachineScheduler.cpp =================================================================== --- lib/CodeGen/MachineScheduler.cpp +++ lib/CodeGen/MachineScheduler.cpp @@ -123,6 +123,9 @@ 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: Index: lib/CodeGen/PHIElimination.cpp =================================================================== --- lib/CodeGen/PHIElimination.cpp +++ lib/CodeGen/PHIElimination.cpp @@ -66,6 +66,9 @@ 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. Index: lib/CodeGen/PrologEpilogInserter.cpp =================================================================== --- lib/CodeGen/PrologEpilogInserter.cpp +++ lib/CodeGen/PrologEpilogInserter.cpp @@ -64,6 +64,8 @@ /// bool runOnMachineFunction(MachineFunction &Fn) override; + // Don't skip this pass while bisecting failures. + bool isSkippable() const override { return false; } private: RegScavenger *RS; Index: lib/CodeGen/RegAllocFast.cpp =================================================================== --- lib/CodeGen/RegAllocFast.cpp +++ lib/CodeGen/RegAllocFast.cpp @@ -159,6 +159,8 @@ MachineFunctionPass::getAnalysisUsage(AU); } + // Don't skip this pass while bisecting failures. + bool isSkippable() const override { return false; } private: bool runOnMachineFunction(MachineFunction &Fn) override; void AllocateBasicBlock(); Index: lib/CodeGen/RegAllocGreedy.cpp =================================================================== --- lib/CodeGen/RegAllocGreedy.cpp +++ lib/CodeGen/RegAllocGreedy.cpp @@ -332,6 +332,9 @@ /// 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: Index: lib/CodeGen/ShadowStackGCLowering.cpp =================================================================== --- lib/CodeGen/ShadowStackGCLowering.cpp +++ lib/CodeGen/ShadowStackGCLowering.cpp @@ -50,6 +50,8 @@ 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); Index: lib/CodeGen/SjLjEHPrepare.cpp =================================================================== --- lib/CodeGen/SjLjEHPrepare.cpp +++ lib/CodeGen/SjLjEHPrepare.cpp @@ -62,6 +62,9 @@ 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); Index: lib/CodeGen/StackColoring.cpp =================================================================== --- lib/CodeGen/StackColoring.cpp +++ lib/CodeGen/StackColoring.cpp @@ -135,6 +135,9 @@ 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; Index: lib/CodeGen/StackSlotColoring.cpp =================================================================== --- lib/CodeGen/StackSlotColoring.cpp +++ lib/CodeGen/StackSlotColoring.cpp @@ -101,6 +101,9 @@ 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); Index: lib/CodeGen/TwoAddressInstructionPass.cpp =================================================================== --- lib/CodeGen/TwoAddressInstructionPass.cpp +++ lib/CodeGen/TwoAddressInstructionPass.cpp @@ -167,6 +167,9 @@ /// Pass entry point. bool runOnMachineFunction(MachineFunction&) override; + + // Don't skip this pass while bisecting failures. + bool isSkippable() const override { return false; } }; } // end anonymous namespace Index: lib/CodeGen/UnreachableBlockElim.cpp =================================================================== --- lib/CodeGen/UnreachableBlockElim.cpp +++ lib/CodeGen/UnreachableBlockElim.cpp @@ -42,6 +42,8 @@ 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()); @@ -97,6 +99,10 @@ 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) {} Index: lib/CodeGen/VirtRegMap.cpp =================================================================== --- lib/CodeGen/VirtRegMap.cpp +++ lib/CodeGen/VirtRegMap.cpp @@ -176,6 +176,9 @@ void getAnalysisUsage(AnalysisUsage &AU) const override; bool runOnMachineFunction(MachineFunction&) override; + + // Don't skip this pass while bisecting failures. + bool isSkippable() const override { return false; } }; } // end anonymous namespace Index: lib/CodeGen/WinEHPrepare.cpp =================================================================== --- lib/CodeGen/WinEHPrepare.cpp +++ lib/CodeGen/WinEHPrepare.cpp @@ -60,6 +60,9 @@ 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 { Index: lib/IR/CMakeLists.txt =================================================================== --- lib/IR/CMakeLists.txt +++ lib/IR/CMakeLists.txt @@ -39,6 +39,7 @@ Module.cpp ModuleSummaryIndex.cpp Operator.cpp + OptBisect.cpp Pass.cpp PassManager.cpp PassRegistry.cpp Index: lib/IR/LegacyPassManager.cpp =================================================================== --- lib/IR/LegacyPassManager.cpp +++ lib/IR/LegacyPassManager.cpp @@ -13,6 +13,7 @@ #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" @@ -258,6 +259,9 @@ /// 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; @@ -322,6 +326,9 @@ /// 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; @@ -420,6 +427,9 @@ /// 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; @@ -1326,7 +1336,7 @@ initializeAnalysisImpl(BP); - { + if (getOptBisector().shouldRunPass(BP, &(*I))) { // If the pass crashes, remember this. PassManagerPrettyStackEntry X(BP, *I); TimeRegion PassTimer(getPassTimer(BP)); @@ -1496,7 +1506,8 @@ initializeAllAnalysisInfo(); for (unsigned Index = 0; Index < getNumContainedManagers(); ++Index) { - Changed |= getContainedManager(Index)->runOnFunction(F); + if (getOptBisector().shouldRunPass(getContainedManager(Index), &F)) + Changed |= getContainedManager(Index)->runOnFunction(F); F.getContext().yield(); } @@ -1543,7 +1554,7 @@ initializeAnalysisImpl(FP); - { + if (getOptBisector().shouldRunPass(FP, &F)) { PassManagerPrettyStackEntry X(FP, F); TimeRegion PassTimer(getPassTimer(FP)); @@ -1615,6 +1626,9 @@ ModulePass *MP = getContainedPass(Index); bool LocalChanged = false; + if (!getOptBisector().shouldRunPass(MP, &M)) + continue; + dumpPassInfo(MP, EXECUTION_MSG, ON_MODULE_MSG, M.getModuleIdentifier()); dumpRequiredSet(MP); Index: lib/IR/OptBisect.cpp =================================================================== --- lib/IR/OptBisect.cpp +++ lib/IR/OptBisect.cpp @@ -0,0 +1,231 @@ +//===------- 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 + +using namespace llvm; + +//////////////////////////////////////////////////////////////////////////////// +// Command line options +//////////////////////////////////////////////////////////////////////////////// + +static cl::opt 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 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 += "<>"; + } + 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 *, + const Module *); +template bool OptBisect::shouldRunPass(detail::PassConcept *, + const Function *); +template bool OptBisect::shouldRunPass(detail::PassConcept *, + const BasicBlock *); +template bool OptBisect::shouldRunPass(detail::PassConcept *, + const Region *); +template bool OptBisect::shouldRunPass(detail::PassConcept *, + const Loop *); +template bool +OptBisect::shouldRunPass(detail::PassConcept *, + const LazyCallGraph::SCC *); + +template +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 +bool OptBisect::shouldRunPass(detail::PassConcept *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; +} Index: lib/IR/Verifier.cpp =================================================================== --- lib/IR/Verifier.cpp +++ lib/IR/Verifier.cpp @@ -4348,6 +4348,10 @@ 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(); } Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -66,6 +66,7 @@ /// \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"; } }; @@ -85,6 +86,7 @@ PreservedAnalyses run(LazyCallGraph::SCC &C) { return PreservedAnalyses::all(); } + bool isSkippable() const { return true; } static StringRef name() { return "NoOpCGSCCPass"; } }; @@ -102,6 +104,7 @@ /// \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"; } }; @@ -119,6 +122,7 @@ /// \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"; } }; Index: lib/Target/X86/X86ExpandPseudo.cpp =================================================================== --- lib/Target/X86/X86ExpandPseudo.cpp +++ lib/Target/X86/X86ExpandPseudo.cpp @@ -48,6 +48,9 @@ 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 "X86 pseudo instruction expansion pass"; } Index: lib/Target/X86/X86FloatingPoint.cpp =================================================================== --- lib/Target/X86/X86FloatingPoint.cpp +++ lib/Target/X86/X86FloatingPoint.cpp @@ -76,6 +76,9 @@ bool runOnMachineFunction(MachineFunction &MF) override; + // Don't skip this pass while bisecting failures. + bool isSkippable() const override { return false; } + const char *getPassName() const override { return "X86 FP Stackifier"; } private: Index: lib/Target/X86/X86InstrInfo.cpp =================================================================== --- lib/Target/X86/X86InstrInfo.cpp +++ lib/Target/X86/X86InstrInfo.cpp @@ -7357,6 +7357,9 @@ 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"; } Index: lib/Target/X86/X86VZeroUpper.cpp =================================================================== --- lib/Target/X86/X86VZeroUpper.cpp +++ lib/Target/X86/X86VZeroUpper.cpp @@ -40,6 +40,9 @@ bool runOnMachineFunction(MachineFunction &MF) override; 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); Index: lib/Transforms/IPO/ForceFunctionAttrs.cpp =================================================================== --- lib/Transforms/IPO/ForceFunctionAttrs.cpp +++ lib/Transforms/IPO/ForceFunctionAttrs.cpp @@ -109,6 +109,8 @@ // Conservatively assume we changed something. return true; } + // Don't skip this pass while bisecting failures. + bool isSkippable() const override { return false; } }; } Index: lib/Transforms/Scalar/LowerExpectIntrinsic.cpp =================================================================== --- lib/Transforms/Scalar/LowerExpectIntrinsic.cpp +++ lib/Transforms/Scalar/LowerExpectIntrinsic.cpp @@ -180,6 +180,9 @@ } bool runOnFunction(Function &F) override { return lowerExpectIntrinsic(F); } + + // Don't skip this pass while bisecting failures. + bool isSkippable() const override { return false; } }; } Index: lib/Transforms/Utils/AddDiscriminators.cpp =================================================================== --- lib/Transforms/Utils/AddDiscriminators.cpp +++ lib/Transforms/Utils/AddDiscriminators.cpp @@ -79,6 +79,9 @@ } bool runOnFunction(Function &F) override; + + // Don't skip this pass while bisecting failures. + bool isSkippable() const override { return false; } }; } // end anonymous namespace Index: unittests/Analysis/CGSCCPassManagerTest.cpp =================================================================== --- unittests/Analysis/CGSCCPassManagerTest.cpp +++ unittests/Analysis/CGSCCPassManagerTest.cpp @@ -135,6 +135,8 @@ return PreservedAnalyses::all(); } + bool isSkippable() const { return true; } + static StringRef name() { return "TestModulePass"; } int &RunCount; @@ -187,6 +189,8 @@ return PreservedAnalyses::all(); } + bool isSkippable() const { return true; } + static StringRef name() { return "TestSCCPass"; } int &RunCount; @@ -204,6 +208,8 @@ return PreservedAnalyses::none(); } + bool isSkippable() const { return true; } + static StringRef name() { return "TestFunctionPass"; } int &RunCount; Index: unittests/Analysis/LoopPassManagerTest.cpp =================================================================== --- unittests/Analysis/LoopPassManagerTest.cpp +++ unittests/Analysis/LoopPassManagerTest.cpp @@ -81,6 +81,8 @@ return PreservedAnalyses::all(); } + bool isSkippable() const { return true; } + static StringRef name() { return "TestLoopPass"; } }; @@ -96,6 +98,8 @@ : PreservedAnalyses::all(); } + bool isSkippable() const { return true; } + static StringRef name() { return "TestLoopInvalidatingPass"; } };