Index: llvm/trunk/include/llvm/Analysis/DominanceFrontier.h =================================================================== --- llvm/trunk/include/llvm/Analysis/DominanceFrontier.h +++ llvm/trunk/include/llvm/Analysis/DominanceFrontier.h @@ -24,6 +24,11 @@ namespace llvm { +// FIXME: Replace this brittle forward declaration with the include of the new +// PassManager.h when doing so doesn't break the PassManagerBuilder. +template class AnalysisManager; +class PreservedAnalyses; + //===----------------------------------------------------------------------===// /// DominanceFrontierBase - Common base class for computing forward and inverse /// dominance frontiers for a function. @@ -133,78 +138,69 @@ const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node); }; -class DominanceFrontier : public FunctionPass { - ForwardDominanceFrontierBase Base; - +class DominanceFrontier : public ForwardDominanceFrontierBase { public: typedef DominatorTreeBase DomTreeT; typedef DomTreeNodeBase DomTreeNodeT; typedef DominanceFrontierBase::DomSetType DomSetType; typedef DominanceFrontierBase::iterator iterator; typedef DominanceFrontierBase::const_iterator const_iterator; +}; +class DominanceFrontierWrapperPass : public FunctionPass { + DominanceFrontier DF; +public: static char ID; // Pass ID, replacement for typeid - DominanceFrontier(); - - ForwardDominanceFrontierBase &getBase() { return Base; } - - inline const std::vector &getRoots() const { - return Base.getRoots(); - } - - BasicBlock *getRoot() const { return Base.getRoot(); } - - bool isPostDominator() const { return Base.isPostDominator(); } + DominanceFrontierWrapperPass(); - iterator begin() { return Base.begin(); } + DominanceFrontier &getDominanceFrontier() { return DF; } + const DominanceFrontier &getDominanceFrontier() const { return DF; } - const_iterator begin() const { return Base.begin(); } - - iterator end() { return Base.end(); } - - const_iterator end() const { return Base.end(); } + void releaseMemory() override; - iterator find(BasicBlock *B) { return Base.find(B); } + bool runOnFunction(Function &) override; - const_iterator find(BasicBlock *B) const { return Base.find(B); } + void getAnalysisUsage(AnalysisUsage &AU) const override; - iterator addBasicBlock(BasicBlock *BB, const DomSetType &frontier) { - return Base.addBasicBlock(BB, frontier); - } + void print(raw_ostream &OS, const Module * = nullptr) const override; - void removeBlock(BasicBlock *BB) { return Base.removeBlock(BB); } + void dump() const; +}; - void addToFrontier(iterator I, BasicBlock *Node) { - return Base.addToFrontier(I, Node); - } +extern template class DominanceFrontierBase; +extern template class ForwardDominanceFrontierBase; - void removeFromFrontier(iterator I, BasicBlock *Node) { - return Base.removeFromFrontier(I, Node); - } +/// \brief Analysis pass which computes a \c DominanceFrontier. +class DominanceFrontierAnalysis { +public: + /// \brief Provide the result typedef for this analysis pass. + typedef DominanceFrontier Result; - bool compareDomSet(DomSetType &DS1, const DomSetType &DS2) const { - return Base.compareDomSet(DS1, DS2); - } + /// \brief Opaque, unique identifier for this analysis pass. + static void *ID() { return (void *)&PassID; } - bool compare(DominanceFrontierBase &Other) const { - return Base.compare(Other); - } + /// \brief Run the analysis pass over a function and produce a dominator tree. + DominanceFrontier run(Function &F, AnalysisManager *AM); - void releaseMemory() override; + /// \brief Provide access to a name for this pass for debugging purposes. + static StringRef name() { return "DominanceFrontierAnalysis"; } - bool runOnFunction(Function &) override; +private: + static char PassID; +}; - void getAnalysisUsage(AnalysisUsage &AU) const override; +/// \brief Printer pass for the \c DominanceFrontier. +class DominanceFrontierPrinterPass { + raw_ostream &OS; - void print(raw_ostream &OS, const Module * = nullptr) const override; +public: + explicit DominanceFrontierPrinterPass(raw_ostream &OS); + PreservedAnalyses run(Function &F, AnalysisManager *AM); - void dump() const; + static StringRef name() { return "DominanceFrontierAnalysis"; } }; -extern template class DominanceFrontierBase; -extern template class ForwardDominanceFrontierBase; - } // End llvm namespace #endif Index: llvm/trunk/include/llvm/InitializePasses.h =================================================================== --- llvm/trunk/include/llvm/InitializePasses.h +++ llvm/trunk/include/llvm/InitializePasses.h @@ -111,7 +111,7 @@ void initializeDomOnlyViewerPass(PassRegistry&); void initializeDomPrinterPass(PassRegistry&); void initializeDomViewerPass(PassRegistry&); -void initializeDominanceFrontierPass(PassRegistry&); +void initializeDominanceFrontierWrapperPassPass(PassRegistry&); void initializeDominatorTreeWrapperPassPass(PassRegistry&); void initializeEarlyIfConverterPass(PassRegistry&); void initializeEdgeBundlesPass(PassRegistry&); Index: llvm/trunk/lib/Analysis/Analysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/Analysis.cpp +++ llvm/trunk/lib/Analysis/Analysis.cpp @@ -38,7 +38,7 @@ initializeDelinearizationPass(Registry); initializeDemandedBitsPass(Registry); initializeDivergenceAnalysisPass(Registry); - initializeDominanceFrontierPass(Registry); + initializeDominanceFrontierWrapperPassPass(Registry); initializeDomViewerPass(Registry); initializeDomPrinterPass(Registry); initializeDomOnlyViewerPass(Registry); Index: llvm/trunk/lib/Analysis/DominanceFrontier.cpp =================================================================== --- llvm/trunk/lib/Analysis/DominanceFrontier.cpp +++ llvm/trunk/lib/Analysis/DominanceFrontier.cpp @@ -9,6 +9,7 @@ #include "llvm/Analysis/DominanceFrontier.h" #include "llvm/Analysis/DominanceFrontierImpl.h" +#include "llvm/IR/PassManager.h" using namespace llvm; @@ -17,41 +18,60 @@ template class ForwardDominanceFrontierBase; } -char DominanceFrontier::ID = 0; +char DominanceFrontierWrapperPass::ID = 0; -INITIALIZE_PASS_BEGIN(DominanceFrontier, "domfrontier", +INITIALIZE_PASS_BEGIN(DominanceFrontierWrapperPass, "domfrontier", "Dominance Frontier Construction", true, true) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_END(DominanceFrontier, "domfrontier", +INITIALIZE_PASS_END(DominanceFrontierWrapperPass, "domfrontier", "Dominance Frontier Construction", true, true) -DominanceFrontier::DominanceFrontier() - : FunctionPass(ID), - Base() { - initializeDominanceFrontierPass(*PassRegistry::getPassRegistry()); + DominanceFrontierWrapperPass::DominanceFrontierWrapperPass() + : FunctionPass(ID), DF() { + initializeDominanceFrontierWrapperPassPass(*PassRegistry::getPassRegistry()); } -void DominanceFrontier::releaseMemory() { - Base.releaseMemory(); +void DominanceFrontierWrapperPass::releaseMemory() { + DF.releaseMemory(); } -bool DominanceFrontier::runOnFunction(Function &) { +bool DominanceFrontierWrapperPass::runOnFunction(Function &) { releaseMemory(); - Base.analyze(getAnalysis().getDomTree()); + DF.analyze(getAnalysis().getDomTree()); return false; } -void DominanceFrontier::getAnalysisUsage(AnalysisUsage &AU) const { +void DominanceFrontierWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequired(); } -void DominanceFrontier::print(raw_ostream &OS, const Module *) const { - Base.print(OS); +void DominanceFrontierWrapperPass::print(raw_ostream &OS, const Module *) const { + DF.print(OS); } #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) -LLVM_DUMP_METHOD void DominanceFrontier::dump() const { +LLVM_DUMP_METHOD void DominanceFrontierWrapperPass::dump() const { print(dbgs()); } #endif + +char DominanceFrontierAnalysis::PassID; + +DominanceFrontier DominanceFrontierAnalysis::run(Function &F, + FunctionAnalysisManager *AM) { + DominanceFrontier DF; + DF.analyze(AM->getResult(F)); + return DF; +} + +DominanceFrontierPrinterPass::DominanceFrontierPrinterPass(raw_ostream &OS) + : OS(OS) {} + +PreservedAnalyses +DominanceFrontierPrinterPass::run(Function &F, FunctionAnalysisManager *AM) { + OS << "DominanceFrontier for function: " << F.getName() << "\n"; + AM->getResult(F).print(OS); + + return PreservedAnalyses::all(); +} Index: llvm/trunk/lib/Analysis/RegionInfo.cpp =================================================================== --- llvm/trunk/lib/Analysis/RegionInfo.cpp +++ llvm/trunk/lib/Analysis/RegionInfo.cpp @@ -129,7 +129,7 @@ auto DT = &getAnalysis().getDomTree(); auto PDT = &getAnalysis().getPostDomTree(); - auto DF = &getAnalysis(); + auto DF = &getAnalysis().getDominanceFrontier(); RI.recalculate(F, DT, PDT, DF); return false; @@ -146,8 +146,8 @@ void RegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequiredTransitive(); - AU.addRequired(); AU.addRequired(); + AU.addRequired(); } void RegionInfoPass::print(raw_ostream &OS, const Module *) const { @@ -165,8 +165,8 @@ INITIALIZE_PASS_BEGIN(RegionInfoPass, "regions", "Detect single entry single exit regions", true, true) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(DominanceFrontier) INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(DominanceFrontierWrapperPass) INITIALIZE_PASS_END(RegionInfoPass, "regions", "Detect single entry single exit regions", true, true) Index: llvm/trunk/lib/CodeGen/MachineFunctionPass.cpp =================================================================== --- llvm/trunk/lib/CodeGen/MachineFunctionPass.cpp +++ llvm/trunk/lib/CodeGen/MachineFunctionPass.cpp @@ -53,7 +53,7 @@ // because CodeGen overloads that to mean preserving the MachineBasicBlock // CFG in addition to the LLVM IR CFG. AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); Index: llvm/trunk/lib/CodeGen/MachineRegionInfo.cpp =================================================================== --- llvm/trunk/lib/CodeGen/MachineRegionInfo.cpp +++ llvm/trunk/lib/CodeGen/MachineRegionInfo.cpp @@ -105,7 +105,7 @@ AU.setPreservesAll(); AU.addRequiredTransitive(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); } void MachineRegionInfoPass::print(raw_ostream &OS, const Module *) const { Index: llvm/trunk/lib/Passes/PassBuilder.cpp =================================================================== --- llvm/trunk/lib/Passes/PassBuilder.cpp +++ llvm/trunk/lib/Passes/PassBuilder.cpp @@ -22,6 +22,7 @@ #include "llvm/Analysis/BasicAliasAnalysis.h" #include "llvm/Analysis/CFLAliasAnalysis.h" #include "llvm/Analysis/CGSCCPassManager.h" +#include "llvm/Analysis/DominanceFrontier.h" #include "llvm/Analysis/LazyCallGraph.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/PostDominators.h" Index: llvm/trunk/lib/Passes/PassRegistry.def =================================================================== --- llvm/trunk/lib/Passes/PassRegistry.def +++ llvm/trunk/lib/Passes/PassRegistry.def @@ -58,6 +58,7 @@ FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis()) FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis()) FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis()) +FUNCTION_ANALYSIS("domfrontier", DominanceFrontierAnalysis()) FUNCTION_ANALYSIS("loops", LoopAnalysis()) FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis()) FUNCTION_ANALYSIS("scalar-evolution", ScalarEvolutionAnalysis()) @@ -91,6 +92,7 @@ FUNCTION_PASS("print", AssumptionPrinterPass(dbgs())) FUNCTION_PASS("print", DominatorTreePrinterPass(dbgs())) FUNCTION_PASS("print", PostDominatorTreePrinterPass(dbgs())) +FUNCTION_PASS("print", DominanceFrontierPrinterPass(dbgs())) FUNCTION_PASS("print", LoopPrinterPass(dbgs())) FUNCTION_PASS("print", ScalarEvolutionPrinterPass(dbgs())) FUNCTION_PASS("simplify-cfg", SimplifyCFGPass()) Index: llvm/trunk/test/Analysis/DominanceFrontier/new_pm_test.ll =================================================================== --- llvm/trunk/test/Analysis/DominanceFrontier/new_pm_test.ll +++ llvm/trunk/test/Analysis/DominanceFrontier/new_pm_test.ll @@ -0,0 +1,50 @@ +; REQUIRES: asserts +; RUN: opt < %s -passes='print' 2>&1 | FileCheck %s + +define void @a_linear_impl_fig_1() nounwind { +0: + br label %"1" +1: + br label %"2" +2: + br label %"3" +3: + br i1 1, label %"13", label %"4" +4: + br i1 1, label %"5", label %"1" +5: + br i1 1, label %"8", label %"6" +6: + br i1 1, label %"7", label %"4" +7: + ret void +8: + br i1 1, label %"9", label %"1" +9: + br label %"10" +10: + br i1 1, label %"12", label %"11" +11: + br i1 1, label %"9", label %"8" +13: + br i1 1, label %"2", label %"1" +12: + switch i32 0, label %"1" [ i32 0, label %"9" + i32 1, label %"8"] +} + +; CHECK: DominanceFrontier for function: a_linear_impl_fig_1 +; CHECK-DAG: DomFrontier for BB %"0" is: +; CHECK-DAG: DomFrontier for BB %"11" is: %"8" %"9" +; CHECK-DAG: DomFrontier for BB %"1" is: %"1" +; CHECK-DAG: DomFrontier for BB %"2" is: %"1" %"2" +; CHECK-DAG: DomFrontier for BB %"3" is: %"1" %"2" +; CHECK-DAG: DomFrontier for BB %"13" is: %"1" %"2" +; CHECK-DAG: DomFrontier for BB %"4" is: %"1" %"4" +; CHECK-DAG: DomFrontier for BB %"5" is: %"1" %"4" +; CHECK-DAG: DomFrontier for BB %"8" is: %"1" %"8" +; CHECK-DAG: DomFrontier for BB %"6" is: %"4" +; CHECK-DAG: DomFrontier for BB %"7" is: +; CHECK-DAG: DomFrontier for BB %"9" is: %"1" %"8" %"9" +; CHECK-DAG: DomFrontier for BB %"10" is: %"1" %"8" %"9" +; CHECK-DAG: DomFrontier for BB %"12" is: %"1" %"8" %"9"