Introduce DominanceFrontierAnalysis to the new PassManager to compute DominanceFrontier. NFC

[etherzhhb]

Summary

I am going to introduce the analysis passes to compute PostDominators, DominanceFrontier and RegionInfo in the new pass manager, such that later we can rewrite passes in Polly in new pass manager style and make interprocedural analysis in Polly become easier.

This is the DominanceFrontier part.

[grosser]

Hi ether,

this patch looks good to me as well. I know we currently have no actual dominance frontier tests, but I think this would be a good occasion to add one. Domfrontier is hopefully removed at some point in time, but until this time comes it is good to have at least some basic test coverage.

Best,
Tobias

[etherzhhb]

In D17570#361584, @grosser wrote:

Hi ether,

this patch looks good to me as well. I know we currently have no actual dominance frontier tests, but I think this would be a good occasion to add one. Domfrontier is hopefully removed at some point in time, but until this time comes it is good to have at least some basic test coverage.

Best,
Tobias

I am going to add one from RegionInfo tests

llvm/trunk/include/llvm/Analysis/DominanceFrontier.h

 #define LLVM_ANALYSIS_DOMINANCEFRONTIER_H
 
 #include "llvm/IR/Dominators.h"
 #include <map>
 #include <set>
 
 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.
 ///
 template <class BlockT>
 class DominanceFrontierBase {
 public:
   typedef std::set<BlockT *> DomSetType;                // Dom set for a bb
void analyze(DomTreeT &DT) {
     assert(this->Roots.size() == 1 &&
            "Only one entry block for forward domfronts!");
     calculate(DT, DT[this->Roots[0]]);
   }
 
   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

llvm/trunk/include/llvm/InitializePasses.h

 void initializeDeadMachineInstructionElimPass(PassRegistry&);
 void initializeDelinearizationPass(PassRegistry &);
 void initializeDependenceAnalysisPass(PassRegistry&);
 void initializeDivergenceAnalysisPass(PassRegistry&);
 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&);
 void initializeExpandPostRAPass(PassRegistry&);
 void initializeAAResultsWrapperPassPass(PassRegistry &);
 void initializeGCOVProfilerPass(PassRegistry&);
 void initializePGOInstrumentationGenPass(PassRegistry&);
 void initializePGOInstrumentationUsePass(PassRegistry&);

llvm/trunk/lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeCFGPrinterPass(Registry);
   initializeCFGOnlyViewerPass(Registry);
   initializeCFGOnlyPrinterPass(Registry);
   initializeCFLAAWrapperPassPass(Registry);
   initializeDependenceAnalysisPass(Registry);
   initializeDelinearizationPass(Registry);
   initializeDemandedBitsPass(Registry);
   initializeDivergenceAnalysisPass(Registry);
-  initializeDominanceFrontierPass(Registry);
+  initializeDominanceFrontierWrapperPassPass(Registry);
   initializeDomViewerPass(Registry);
   initializeDomPrinterPass(Registry);
   initializeDomOnlyViewerPass(Registry);
   initializePostDomViewerPass(Registry);
   initializeDomOnlyPrinterPass(Registry);
   initializePostDomPrinterPass(Registry);
   initializePostDomOnlyViewerPass(Registry);
   initializePostDomOnlyPrinterPass(Registry);

llvm/trunk/lib/Analysis/DominanceFrontier.cpp

 //===- DominanceFrontier.cpp - Dominance Frontier Calculation -------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/DominanceFrontier.h"
 #include "llvm/Analysis/DominanceFrontierImpl.h"
+#include "llvm/IR/PassManager.h"
 
 using namespace llvm;
 
 namespace llvm {
 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();
+}

llvm/trunk/lib/Analysis/RegionInfo.cpp

 
 }
 
 bool RegionInfoPass::runOnFunction(Function &F) {
   releaseMemory();
 
   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;
 }
 
 void RegionInfoPass::releaseMemory() {
   RI.releaseMemory();
 }
 
 void RegionInfoPass::verifyAnalysis() const {
     RI.verifyAnalysis();
 }
 
 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 {
   RI.print(OS);
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void RegionInfoPass::dump() const {
   RI.dump();
 }
 #endif
 
 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)
 
 // Create methods available outside of this file, to use them
 // "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by
 // the link time optimization.
 
 namespace llvm {
   FunctionPass *createRegionInfoPass() {
     return new RegionInfoPass();
   }
 }
 

llvm/trunk/lib/CodeGen/MachineFunctionPass.cpp

void MachineFunctionPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addPreserved<MachineFunctionAnalysis>();
 
   // MachineFunctionPass preserves all LLVM IR passes, but there's no
   // high-level way to express this. Instead, just list a bunch of
   // passes explicitly. This does not include setPreservesCFG,
   // 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>();
   AU.addPreserved<IVUsers>();
   AU.addPreserved<LoopInfoWrapperPass>();
   AU.addPreserved<MemoryDependenceAnalysis>();
   AU.addPreserved<ScalarEvolutionWrapperPass>();
   AU.addPreserved<SCEVAAWrapperPass>();
   AU.addPreserved<StackProtector>();
 
   FunctionPass::getAnalysisUsage(AU);
 }

llvm/trunk/lib/CodeGen/MachineRegionInfo.cpp

void MachineRegionInfoPass::verifyAnalysis() const {
   if (MachineRegionInfo::VerifyRegionInfo)
     RI.verifyAnalysis();
 }
 
 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 {
   RI.print(OS);
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void MachineRegionInfoPass::dump() const {

llvm/trunk/lib/Passes/PassBuilder.cpp

 
 #include "llvm/Passes/PassBuilder.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasAnalysisEvaluator.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #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"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"

llvm/trunk/lib/Passes/PassRegistry.def

 
 #ifndef FUNCTION_ANALYSIS
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
 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())
 FUNCTION_ANALYSIS("targetlibinfo", TargetLibraryAnalysis())
 FUNCTION_ANALYSIS("targetir",
                   TM ? TM->getTargetIRAnalysis() : TargetIRAnalysis())
 
 #ifndef FUNCTION_ALIAS_ANALYSIS

 FUNCTION_PASS("instcombine", InstCombinePass())
 FUNCTION_PASS("invalidate<all>", InvalidateAllAnalysesPass())
 FUNCTION_PASS("no-op-function", NoOpFunctionPass())
 FUNCTION_PASS("lower-expect", LowerExpectIntrinsicPass())
 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())
 FUNCTION_PASS("sroa", SROA())
 FUNCTION_PASS("verify", VerifierPass())
 FUNCTION_PASS("verify<domtree>", DominatorTreeVerifierPass())
 #undef FUNCTION_PASS
 

llvm/trunk/test/Analysis/DominanceFrontier/new_pm_test.ll

+; 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"