diff options
Diffstat (limited to 'llvm')
| -rw-r--r-- | llvm/include/llvm/Analysis/DominanceFrontier.h | 88 | ||||
| -rw-r--r-- | llvm/include/llvm/InitializePasses.h | 2 | ||||
| -rw-r--r-- | llvm/lib/Analysis/Analysis.cpp | 2 | ||||
| -rw-r--r-- | llvm/lib/Analysis/DominanceFrontier.cpp | 50 | ||||
| -rw-r--r-- | llvm/lib/Analysis/RegionInfo.cpp | 6 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/MachineFunctionPass.cpp | 2 | ||||
| -rw-r--r-- | llvm/lib/CodeGen/MachineRegionInfo.cpp | 2 | ||||
| -rw-r--r-- | llvm/lib/Passes/PassBuilder.cpp | 1 | ||||
| -rw-r--r-- | llvm/lib/Passes/PassRegistry.def | 2 | ||||
| -rw-r--r-- | llvm/test/Analysis/DominanceFrontier/new_pm_test.ll | 50 |
10 files changed, 137 insertions, 68 deletions
diff --git a/llvm/include/llvm/Analysis/DominanceFrontier.h b/llvm/include/llvm/Analysis/DominanceFrontier.h index fb730054a8e..b4b8a6baf0a 100644 --- a/llvm/include/llvm/Analysis/DominanceFrontier.h +++ b/llvm/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 <typename IRUnitT> class AnalysisManager; +class PreservedAnalyses; + //===----------------------------------------------------------------------===// /// DominanceFrontierBase - Common base class for computing forward and inverse /// dominance frontiers for a function. @@ -133,78 +138,69 @@ public: const DomSetType &calculate(const DomTreeT &DT, const DomTreeNodeT *Node); }; -class DominanceFrontier : public FunctionPass { - ForwardDominanceFrontierBase<BasicBlock> Base; - +class DominanceFrontier : public ForwardDominanceFrontierBase<BasicBlock> { public: typedef DominatorTreeBase<BasicBlock> DomTreeT; typedef DomTreeNodeBase<BasicBlock> DomTreeNodeT; typedef DominanceFrontierBase<BasicBlock>::DomSetType DomSetType; typedef DominanceFrontierBase<BasicBlock>::iterator iterator; typedef DominanceFrontierBase<BasicBlock>::const_iterator const_iterator; +}; +class DominanceFrontierWrapperPass : public FunctionPass { + DominanceFrontier DF; +public: static char ID; // Pass ID, replacement for typeid - DominanceFrontier(); - - ForwardDominanceFrontierBase<BasicBlock> &getBase() { return Base; } - - inline const std::vector<BasicBlock *> &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<BasicBlock>; +extern template class ForwardDominanceFrontierBase<BasicBlock>; - 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<BasicBlock> &Other) const { - return Base.compare(Other); - } + /// \brief Run the analysis pass over a function and produce a dominator tree. + DominanceFrontier run(Function &F, AnalysisManager<Function> *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<Function> *AM); - void dump() const; + static StringRef name() { return "DominanceFrontierAnalysis"; } }; -extern template class DominanceFrontierBase<BasicBlock>; -extern template class ForwardDominanceFrontierBase<BasicBlock>; - } // End llvm namespace #endif diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h index 5f2b886a18a..c5fae37000d 100644 --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -111,7 +111,7 @@ void initializeDomOnlyPrinterPass(PassRegistry&); void initializeDomOnlyViewerPass(PassRegistry&); void initializeDomPrinterPass(PassRegistry&); void initializeDomViewerPass(PassRegistry&); -void initializeDominanceFrontierPass(PassRegistry&); +void initializeDominanceFrontierWrapperPassPass(PassRegistry&); void initializeDominatorTreeWrapperPassPass(PassRegistry&); void initializeEarlyIfConverterPass(PassRegistry&); void initializeEdgeBundlesPass(PassRegistry&); diff --git a/llvm/lib/Analysis/Analysis.cpp b/llvm/lib/Analysis/Analysis.cpp index 9c53dedad03..b9c97c058b9 100644 --- a/llvm/lib/Analysis/Analysis.cpp +++ b/llvm/lib/Analysis/Analysis.cpp @@ -38,7 +38,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializeDelinearizationPass(Registry); initializeDemandedBitsPass(Registry); initializeDivergenceAnalysisPass(Registry); - initializeDominanceFrontierPass(Registry); + initializeDominanceFrontierWrapperPassPass(Registry); initializeDomViewerPass(Registry); initializeDomPrinterPass(Registry); initializeDomOnlyViewerPass(Registry); diff --git a/llvm/lib/Analysis/DominanceFrontier.cpp b/llvm/lib/Analysis/DominanceFrontier.cpp index 90e7fd00dba..ef7062da775 100644 --- a/llvm/lib/Analysis/DominanceFrontier.cpp +++ b/llvm/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 DominanceFrontierBase<BasicBlock>; template class ForwardDominanceFrontierBase<BasicBlock>; } -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<DominatorTreeWrapperPass>().getDomTree()); + DF.analyze(getAnalysis<DominatorTreeWrapperPass>().getDomTree()); return false; } -void DominanceFrontier::getAnalysisUsage(AnalysisUsage &AU) const { +void DominanceFrontierWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequired<DominatorTreeWrapperPass>(); } -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<DominatorTreeAnalysis>(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<DominanceFrontierAnalysis>(F).print(OS); + + return PreservedAnalyses::all(); +} diff --git a/llvm/lib/Analysis/RegionInfo.cpp b/llvm/lib/Analysis/RegionInfo.cpp index dac0cddc168..b4ba5af099f 100644 --- a/llvm/lib/Analysis/RegionInfo.cpp +++ b/llvm/lib/Analysis/RegionInfo.cpp @@ -129,7 +129,7 @@ bool RegionInfoPass::runOnFunction(Function &F) { auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); auto PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree(); - auto DF = &getAnalysis<DominanceFrontier>(); + auto DF = &getAnalysis<DominanceFrontierWrapperPass>().getDominanceFrontier(); RI.recalculate(F, DT, PDT, DF); return false; @@ -146,8 +146,8 @@ void RegionInfoPass::verifyAnalysis() const { void RegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequiredTransitive<DominatorTreeWrapperPass>(); - AU.addRequired<DominanceFrontier>(); AU.addRequired<PostDominatorTreeWrapperPass>(); + AU.addRequired<DominanceFrontierWrapperPass>(); } void RegionInfoPass::print(raw_ostream &OS, const Module *) const { @@ -165,8 +165,8 @@ char RegionInfoPass::ID = 0; 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) diff --git a/llvm/lib/CodeGen/MachineFunctionPass.cpp b/llvm/lib/CodeGen/MachineFunctionPass.cpp index 05463fc6a1e..5ca41bec3c3 100644 --- a/llvm/lib/CodeGen/MachineFunctionPass.cpp +++ b/llvm/lib/CodeGen/MachineFunctionPass.cpp @@ -53,7 +53,7 @@ void MachineFunctionPass::getAnalysisUsage(AnalysisUsage &AU) const { // because CodeGen overloads that to mean preserving the MachineBasicBlock // CFG in addition to the LLVM IR CFG. AU.addPreserved<BasicAAWrapperPass>(); - AU.addPreserved<DominanceFrontier>(); + AU.addPreserved<DominanceFrontierWrapperPass>(); AU.addPreserved<DominatorTreeWrapperPass>(); AU.addPreserved<AAResultsWrapperPass>(); AU.addPreserved<GlobalsAAWrapperPass>(); diff --git a/llvm/lib/CodeGen/MachineRegionInfo.cpp b/llvm/lib/CodeGen/MachineRegionInfo.cpp index 0f7ebb3da83..fc32183c7f6 100644 --- a/llvm/lib/CodeGen/MachineRegionInfo.cpp +++ b/llvm/lib/CodeGen/MachineRegionInfo.cpp @@ -105,7 +105,7 @@ void MachineRegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequiredTransitive<DominatorTreeWrapperPass>(); AU.addRequired<PostDominatorTreeWrapperPass>(); - AU.addRequired<DominanceFrontier>(); + AU.addRequired<DominanceFrontierWrapperPass>(); } void MachineRegionInfoPass::print(raw_ostream &OS, const Module *) const { diff --git a/llvm/lib/Passes/PassBuilder.cpp b/llvm/lib/Passes/PassBuilder.cpp index bd30fce7dc9..7d0fe7e681b 100644 --- a/llvm/lib/Passes/PassBuilder.cpp +++ b/llvm/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" diff --git a/llvm/lib/Passes/PassRegistry.def b/llvm/lib/Passes/PassRegistry.def index ccb40064cc8..51d9310745e 100644 --- a/llvm/lib/Passes/PassRegistry.def +++ b/llvm/lib/Passes/PassRegistry.def @@ -58,6 +58,7 @@ FUNCTION_ANALYSIS("aa", AAManager()) 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", PrintFunctionPass(dbgs())) FUNCTION_PASS("print<assumptions>", AssumptionPrinterPass(dbgs())) FUNCTION_PASS("print<domtree>", DominatorTreePrinterPass(dbgs())) FUNCTION_PASS("print<postdomtree>", PostDominatorTreePrinterPass(dbgs())) +FUNCTION_PASS("print<domfrontier>", DominanceFrontierPrinterPass(dbgs())) FUNCTION_PASS("print<loops>", LoopPrinterPass(dbgs())) FUNCTION_PASS("print<scalar-evolution>", ScalarEvolutionPrinterPass(dbgs())) FUNCTION_PASS("simplify-cfg", SimplifyCFGPass()) diff --git a/llvm/test/Analysis/DominanceFrontier/new_pm_test.ll b/llvm/test/Analysis/DominanceFrontier/new_pm_test.ll new file mode 100644 index 00000000000..30b2fa6ff1a --- /dev/null +++ b/llvm/test/Analysis/DominanceFrontier/new_pm_test.ll @@ -0,0 +1,50 @@ +; REQUIRES: asserts +; RUN: opt < %s -passes='print<domfrontier>' 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" |
