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 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" @@ -242,6 +243,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"; 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" @@ -115,6 +116,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/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" @@ -1326,7 +1327,7 @@ initializeAnalysisImpl(BP); - { + if (getOptBisector().shouldRunPass(BP, &(*I))) { // If the pass crashes, remember this. PassManagerPrettyStackEntry X(BP, *I); TimeRegion PassTimer(getPassTimer(BP)); @@ -1496,7 +1497,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 +1545,7 @@ initializeAnalysisImpl(FP); - { + if (getOptBisector().shouldRunPass(FP, &F)) { PassManagerPrettyStackEntry X(FP, F); TimeRegion PassTimer(getPassTimer(FP)); @@ -1615,6 +1617,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,296 @@ +//===------- 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; +} + +//////////////////////////////////////////////////////////////////////////////// +// Necessary pass list -- lookup by pass name +//////////////////////////////////////////////////////////////////////////////// + +// FIXME: There should be a better way to do this. This is a fragile way to +// force passes to be run. It's just here to get things up and running. +// TODO: Add any passes needed for additional targets. This list was generated +// for x86 compilation. +static const StringSet<> NecessaryPasses{ + // This is a list of non-analysis passes that are run at -O0. + // These aren't all strictly necessary, so we should trim this list. + "Function Pass Manager", + "Module Verifier", + "Add DWARF path discriminators", + "Force set function attributes", + "CallGraph Pass Manager", + "A No-Op Barrier Pass", + "Rewrite Symbols", + "Expand Atomic calls in terms of either load-linked & store-conditional or cmpxchg", + "Lower Garbage Collection Instructions", + "Shadow Stack GC Lowering", + "Remove unreachable blocks from the CFG", + "Windows exception handling preparation", + "Exception handling preparation", + "Safe Stack instrumentation pass", + "Insert stack protectors", + "Machine Function Analysis", + "X86 DAG->DAG Instruction Selection", + "X86 PIC Global Base Reg Initialization", + "Expand ISel Pseudo-instructions", + "Local Stack Slot Allocation", + "X86 Optimize Call Frame", + "Eliminate PHI nodes for register allocation", + "Two-Address instruction pass", + "Fast Register Allocator", + "X86 FP Stackifier", + "Prologue/Epilogue Insertion & Frame Finalization", + "Post-RA pseudo instruction expansion pass", + "X86 pseudo instruction expansion pass", + "Analyze Machine Code For Garbage Collection", + "X86 vzeroupper inserter", + "Contiguously Lay Out Funclets", + "StackMap Liveness Analysis", + "Live DEBUG_VALUE analysis", + "X86 Assembly / Object Emitter", + // Added passes needed for optimized compilation + "Live Variable Analysis", + "Slot index numbering", + "Merge disjoint stack slots", + "Live Interval Analysis", + "Machine Instruction Scheduler", + "Debug Variable Analysis", + "Live Stack Slot Analysis", + "Virtual Register Map", + "Live Register Matrix", + "Greedy Register Allocator", + "Virtual Register Rewriter", + "Stack Slot Coloring", + "Lower 'expect' Intrinsics" +}; + +static bool isNecessary(StringRef Name) { + return (NecessaryPasses.count(Name) != 0); +} + +//////////////////////////////////////////////////////////////////////////////// +// 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(Name) || IsAnalysis); + dbgs() << Status << "BISECT: 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: Another 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), 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), false); +} + +bool OptBisect::checkPass(const StringRef PassName, const StringRef TargetDesc, + bool IsAnalysis) { + assert(BisectEnabled); + + // Don't take a number for passes we can't skip. + bool IsNecessary = isNecessary(PassName); + if (IsAnalysis || IsNecessary) { + printPassMessage(PassName, -1, IsAnalysis, IsNecessary, TargetDesc, true); + return true; + } + + int CurBisectNum = ++LastBisectNum; + bool ShouldRun = (OptBisectLimit == -1 || CurBisectNum <= OptBisectLimit); + printPassMessage(PassName, CurBisectNum, IsAnalysis, IsNecessary, 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; +}