Introduce analysis pass to compute PostDominators in the new pass manager. 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 PostDominators part.

[etherzhhb]

Include the changes in RegionInfo.cpp

[grosser]

Hi ether,

this change looks good to me. The introduction of the post-dominator tree follows precisely Chandler's template in other passes and the DotGraphTraits look good as well.

include/llvm/Analysis/PostDominators.h

 
 #include "llvm/IR/Dominators.h"
 
 namespace llvm {
 
 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
 /// compute the post-dominator tree.
 ///
-struct PostDominatorTree : public FunctionPass {
-  static char ID; // Pass identification, replacement for typeid
-  DominatorTreeBase<BasicBlock>* DT;
-
-  PostDominatorTree() : FunctionPass(ID) {
-    initializePostDominatorTreePass(*PassRegistry::getPassRegistry());
-    DT = new DominatorTreeBase<BasicBlock>(true);
-  }
-
-  ~PostDominatorTree() override;
-
-  bool runOnFunction(Function &F) override;
-
-  void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.setPreservesAll();
-  }
-
-  inline const std::vector<BasicBlock*> &getRoots() const {
-    return DT->getRoots();
-  }
+struct PostDominatorTree : public DominatorTreeBase<BasicBlock> {
+  PostDominatorTree() : DominatorTreeBase<BasicBlock>(true) {}
+};
 
-  inline DomTreeNode *getRootNode() const {
-    return DT->getRootNode();
-  }
+/// \brief Analysis pass which computes a \c PostDominatorTree.
+class PostDominatorTreeAnalysis {
+public:
+  /// \brief Provide the result typedef for this analysis pass.
+  typedef PostDominatorTree Result;
+
+  /// \brief Opaque, unique identifier for this analysis pass.
+  static void *ID() { return (void *)&PassID; }
+
+  /// \brief Run the analysis pass over a function and produce a post dominator
+  ///        tree.
+  PostDominatorTree run(Function &F);
 
-  inline DomTreeNode *operator[](BasicBlock *BB) const {
-    return DT->getNode(BB);
-  }
+  /// \brief Provide access to a name for this pass for debugging purposes.
+  static StringRef name() { return "PostDominatorTreeAnalysis"; }
 
-  inline DomTreeNode *getNode(BasicBlock *BB) const {
-    return DT->getNode(BB);
-  }
+private:
+  static char PassID;
+};
 
-  inline bool dominates(DomTreeNode* A, DomTreeNode* B) const {
-    return DT->dominates(A, B);
-  }
+/// \brief Printer pass for the \c PostDominatorTree.
+class PostDominatorTreePrinterPass {
+  raw_ostream &OS;
+
+public:
+  explicit PostDominatorTreePrinterPass(raw_ostream &OS);
+  PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM);
 
-  inline bool dominates(const BasicBlock* A, const BasicBlock* B) const {
-    return DT->dominates(A, B);
-  }
+  static StringRef name() { return "PostDominatorTreePrinterPass"; }
+};
 
-  inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const {
-    return DT->properlyDominates(A, B);
-  }
+struct PostDominatorTreeWrapperPass : public FunctionPass {
+  static char ID; // Pass identification, replacement for typeid
+  PostDominatorTree DT;
 
-  inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const {
-    return DT->properlyDominates(A, B);
+  PostDominatorTreeWrapperPass() : FunctionPass(ID) {
+    initializePostDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
   }
 
-  inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) {
-    return DT->findNearestCommonDominator(A, B);
-  }
+  PostDominatorTree &getPostDomTree() { return DT; }
+  const PostDominatorTree &getPostDomTree() const { return DT; }
 
-  inline const BasicBlock *findNearestCommonDominator(const BasicBlock *A,
-                                                      const BasicBlock *B) {
-    return DT->findNearestCommonDominator(A, B);
-  }
+  bool runOnFunction(Function &F) override;
 
-  /// Get all nodes post-dominated by R, including R itself.
-  void getDescendants(BasicBlock *R,
-                      SmallVectorImpl<BasicBlock *> &Result) const {
-    DT->getDescendants(R, Result);
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
   }
 
   void releaseMemory() override {
-    DT->releaseMemory();
+    DT.releaseMemory();
   }
 
   void print(raw_ostream &OS, const Module*) const override;
 };
 
 FunctionPass* createPostDomTree();
 
 template <> struct GraphTraits<PostDominatorTree*>

include/llvm/InitializePasses.h

 void initializePEIPass(PassRegistry&);
 void initializePHIEliminationPass(PassRegistry&);
 void initializePartialInlinerPass(PassRegistry&);
 void initializePeepholeOptimizerPass(PassRegistry&);
 void initializePostDomOnlyPrinterPass(PassRegistry&);
 void initializePostDomOnlyViewerPass(PassRegistry&);
 void initializePostDomPrinterPass(PassRegistry&);
 void initializePostDomViewerPass(PassRegistry&);
-void initializePostDominatorTreePass(PassRegistry&);
+void initializePostDominatorTreeWrapperPassPass(PassRegistry&);
 void initializePostOrderFunctionAttrsLegacyPassPass(PassRegistry&);
 void initializePostRASchedulerPass(PassRegistry&);
 void initializePostMachineSchedulerPass(PassRegistry&);
 void initializePrintFunctionPassWrapperPass(PassRegistry&);
 void initializePrintModulePassWrapperPass(PassRegistry&);
 void initializePrintBasicBlockPassPass(PassRegistry&);
 void initializeProcessImplicitDefsPass(PassRegistry&);
 void initializePromotePassPass(PassRegistry&);

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeLazyValueInfoPass(Registry);
   initializeLintPass(Registry);
   initializeLoopInfoWrapperPassPass(Registry);
   initializeMemDepPrinterPass(Registry);
   initializeMemDerefPrinterPass(Registry);
   initializeMemoryDependenceAnalysisPass(Registry);
   initializeModuleDebugInfoPrinterPass(Registry);
   initializeObjCARCAAWrapperPassPass(Registry);
-  initializePostDominatorTreePass(Registry);
+  initializePostDominatorTreeWrapperPassPass(Registry);
   initializeRegionInfoPassPass(Registry);
   initializeRegionViewerPass(Registry);
   initializeRegionPrinterPass(Registry);
   initializeRegionOnlyViewerPass(Registry);
   initializeRegionOnlyPrinterPass(Registry);
   initializeSCEVAAWrapperPassPass(Registry);
   initializeScalarEvolutionWrapperPassPass(Registry);
   initializeTargetTransformInfoWrapperPassPass(Registry);

lib/Analysis/DivergenceAnalysis.cpp

 
 } /// end namespace anonymous
 
 // Register this pass.
 char DivergenceAnalysis::ID = 0;
 INITIALIZE_PASS_BEGIN(DivergenceAnalysis, "divergence", "Divergence Analysis",
                       false, true)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_END(DivergenceAnalysis, "divergence", "Divergence Analysis",
                     false, true)
 
 FunctionPass *llvm::createDivergenceAnalysisPass() {
   return new DivergenceAnalysis();
 }
 
 void DivergenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<DominatorTreeWrapperPass>();
-  AU.addRequired<PostDominatorTree>();
+  AU.addRequired<PostDominatorTreeWrapperPass>();
   AU.setPreservesAll();
 }
 
 bool DivergenceAnalysis::runOnFunction(Function &F) {
   auto *TTIWP = getAnalysisIfAvailable<TargetTransformInfoWrapperPass>();
   if (TTIWP == nullptr)
     return false;
 
   TargetTransformInfo &TTI = TTIWP->getTTI(F);
   // Fast path: if the target does not have branch divergence, we do not mark
   // any branch as divergent.
   if (!TTI.hasBranchDivergence())
     return false;
 
   DivergentValues.clear();
+  auto &PDT = getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
   DivergencePropagator DP(F, TTI,
                           getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
-                          getAnalysis<PostDominatorTree>(), DivergentValues);
+                          PDT, DivergentValues);
   DP.populateWithSourcesOfDivergence();
   DP.propagate();
   return false;
 }
 
 void DivergenceAnalysis::print(raw_ostream &OS, const Module *) const {
   if (DivergentValues.empty())
     return;

lib/Analysis/DomPrinter.cpp

struct DomOnlyViewer : public DOTGraphTraitsViewer<
   DomOnlyViewer()
       : DOTGraphTraitsViewer<DominatorTreeWrapperPass, true, DominatorTree *,
                              DominatorTreeWrapperPassAnalysisGraphTraits>(
             "domonly", ID) {
     initializeDomOnlyViewerPass(*PassRegistry::getPassRegistry());
   }
 };
 
-struct PostDomViewer
-  : public DOTGraphTraitsViewer<PostDominatorTree, false> {
+struct PostDominatorTreeWrapperPassAnalysisGraphTraits {
+  static PostDominatorTree *getGraph(PostDominatorTreeWrapperPass *PDTWP) {
+    return &PDTWP->getPostDomTree();
+  }
+};
+
+struct PostDomViewer : public DOTGraphTraitsViewer<
+                          PostDominatorTreeWrapperPass, false,
+                          PostDominatorTree *,
+                          PostDominatorTreeWrapperPassAnalysisGraphTraits> {
   static char ID;
   PostDomViewer() :
-    DOTGraphTraitsViewer<PostDominatorTree, false>("postdom", ID){
+    DOTGraphTraitsViewer<PostDominatorTreeWrapperPass, false,
+                         PostDominatorTree *,
+                         PostDominatorTreeWrapperPassAnalysisGraphTraits>(
+        "postdom", ID){
       initializePostDomViewerPass(*PassRegistry::getPassRegistry());
     }
 };
 
-struct PostDomOnlyViewer
-  : public DOTGraphTraitsViewer<PostDominatorTree, true> {
+struct PostDomOnlyViewer : public DOTGraphTraitsViewer<
+                            PostDominatorTreeWrapperPass, true,
+                            PostDominatorTree *,
+                            PostDominatorTreeWrapperPassAnalysisGraphTraits> {
   static char ID;
   PostDomOnlyViewer() :
-    DOTGraphTraitsViewer<PostDominatorTree, true>("postdomonly", ID){
+    DOTGraphTraitsViewer<PostDominatorTreeWrapperPass, true,
+                         PostDominatorTree *,
+                         PostDominatorTreeWrapperPassAnalysisGraphTraits>(
+        "postdomonly", ID){
       initializePostDomOnlyViewerPass(*PassRegistry::getPassRegistry());
     }
 };
 } // end anonymous namespace
 
 char DomViewer::ID = 0;
 INITIALIZE_PASS(DomViewer, "view-dom",
                 "View dominance tree of function", false, false)
DomOnlyPrinter()
       : DOTGraphTraitsPrinter<DominatorTreeWrapperPass, true, DominatorTree *,
                               DominatorTreeWrapperPassAnalysisGraphTraits>(
             "domonly", ID) {
     initializeDomOnlyPrinterPass(*PassRegistry::getPassRegistry());
   }
 };
 
 struct PostDomPrinter
-  : public DOTGraphTraitsPrinter<PostDominatorTree, false> {
+  : public DOTGraphTraitsPrinter<
+                            PostDominatorTreeWrapperPass, false,
+                            PostDominatorTree *,
+                            PostDominatorTreeWrapperPassAnalysisGraphTraits> {
   static char ID;
   PostDomPrinter() :
-    DOTGraphTraitsPrinter<PostDominatorTree, false>("postdom", ID) {
+    DOTGraphTraitsPrinter<PostDominatorTreeWrapperPass, false,
+                          PostDominatorTree *,
+                          PostDominatorTreeWrapperPassAnalysisGraphTraits>(
+        "postdom", ID) {
       initializePostDomPrinterPass(*PassRegistry::getPassRegistry());
     }
 };
 
 struct PostDomOnlyPrinter
-  : public DOTGraphTraitsPrinter<PostDominatorTree, true> {
+  : public DOTGraphTraitsPrinter<
+                            PostDominatorTreeWrapperPass, true,
+                            PostDominatorTree *,
+                            PostDominatorTreeWrapperPassAnalysisGraphTraits> {
   static char ID;
   PostDomOnlyPrinter() :
-    DOTGraphTraitsPrinter<PostDominatorTree, true>("postdomonly", ID) {
+    DOTGraphTraitsPrinter<PostDominatorTreeWrapperPass, true,
+                          PostDominatorTree *,
+                          PostDominatorTreeWrapperPassAnalysisGraphTraits>(
+        "postdomonly", ID) {
       initializePostDomOnlyPrinterPass(*PassRegistry::getPassRegistry());
     }
 };
 } // end anonymous namespace
 
 
 
 char DomPrinter::ID = 0;

lib/Analysis/PostDominators.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/SetOperations.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Instructions.h"
+#include "llvm/IR/PassManager.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/GenericDomTreeConstruction.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "postdomtree"
 
 //===----------------------------------------------------------------------===//
 //  PostDominatorTree Implementation
 //===----------------------------------------------------------------------===//
 
-char PostDominatorTree::ID = 0;
-INITIALIZE_PASS(PostDominatorTree, "postdomtree",
+char PostDominatorTreeWrapperPass::ID = 0;
+INITIALIZE_PASS(PostDominatorTreeWrapperPass, "postdomtree",
                 "Post-Dominator Tree Construction", true, true)
 
-bool PostDominatorTree::runOnFunction(Function &F) {
-  DT->recalculate(F);
+bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) {
+  DT.recalculate(F);
   return false;
 }
 
-PostDominatorTree::~PostDominatorTree() {
-  delete DT;
+void PostDominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
+  DT.print(OS);
 }
 
-void PostDominatorTree::print(raw_ostream &OS, const Module *) const {
-  DT->print(OS);
+FunctionPass* llvm::createPostDomTree() {
+  return new PostDominatorTreeWrapperPass();
 }
 
+char PostDominatorTreeAnalysis::PassID;
 
-FunctionPass* llvm::createPostDomTree() {
-  return new PostDominatorTree();
+PostDominatorTree PostDominatorTreeAnalysis::run(Function &F) {
+  PostDominatorTree PDT;
+  PDT.recalculate(F);
+  return PDT;
 }
 
+PostDominatorTreePrinterPass::PostDominatorTreePrinterPass(raw_ostream &OS)
+  : OS(OS) {}
+
+PreservedAnalyses
+PostDominatorTreePrinterPass::run(Function &F, FunctionAnalysisManager *AM) {
+  OS << "PostDominatorTree for function: " << F.getName() << "\n";
+  AM->getResult<PostDominatorTreeAnalysis>(F).print(OS);
+
+  return PreservedAnalyses::all();
+}

lib/CodeGen/MachineRegionInfo.cpp

void MachineRegionInfoPass::verifyAnalysis() const {
   // a regionpass (marked PreservedAll) finish.
   if (MachineRegionInfo::VerifyRegionInfo)
     RI.verifyAnalysis();
 }
 
 void MachineRegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequiredTransitive<DominatorTreeWrapperPass>();
-  AU.addRequired<PostDominatorTree>();
+  AU.addRequired<PostDominatorTreeWrapperPass>();
   AU.addRequired<DominanceFrontier>();
 }
 
 void MachineRegionInfoPass::print(raw_ostream &OS, const Module *) const {
   RI.print(OS);
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)

lib/Passes/PassBuilder.cpp

 #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/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"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRPrintingPasses.h"

lib/Passes/PassRegistry.def

 #undef CGSCC_PASS
 
 #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("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("early-cse", EarlyCSEPass())
 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<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

test/Analysis/PostDominators/pr1098.ll

 ; RUN: opt < %s -postdomtree -analyze | FileCheck %s
+; RUN: opt < %s -passes='print<postdomtree>' 2>&1 | FileCheck %s
 ; PR932
 
 define void @foo(i1 %x) {
 ; CHECK: entry
 entry:
         br i1 %x, label %bb1, label %bb0
 bb0:            ; preds = %entry, bb0
         br label %bb0
 bb1:            ; preds = %entry
         br label %bb2
 bb2:            ; preds = %bb1
         ret void
 }
 

unittests/IR/DominatorTreeTest.cpp

namespace llvm {
   void initializeDPassPass(PassRegistry&);
 
   namespace {
     struct DPass : public FunctionPass {
       static char ID;
       bool runOnFunction(Function &F) override {
         DominatorTree *DT =
             &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-        PostDominatorTree *PDT = &getAnalysis<PostDominatorTree>();
+        PostDominatorTree *PDT =
+            &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
         Function::iterator FI = F.begin();
 
         BasicBlock *BB0 = &*FI++;
         BasicBlock::iterator BBI = BB0->begin();
         Instruction *Y1 = &*BBI++;
         Instruction *Y2 = &*BBI++;
         Instruction *Y3 = &*BBI++;
 
struct DPass : public FunctionPass {
         EXPECT_EQ(DT->getNode(BB3)->getDFSNumOut(), 3UL);
         EXPECT_EQ(DT->getNode(BB4)->getDFSNumIn(), 5UL);
         EXPECT_EQ(DT->getNode(BB4)->getDFSNumOut(), 6UL);
 
         return false;
       }
       void getAnalysisUsage(AnalysisUsage &AU) const override {
         AU.addRequired<DominatorTreeWrapperPass>();
-        AU.addRequired<PostDominatorTree>();
+        AU.addRequired<PostDominatorTreeWrapperPass>();
       }
       DPass() : FunctionPass(ID) {
         initializeDPassPass(*PassRegistry::getPassRegistry());
       }
     };
     char DPass::ID = 0;
 
     std::unique_ptr<Module> makeLLVMModule(DPass *P) {
TEST(DominatorTree, Unreachable) {
       Passes.add(P);
       Passes.run(*M);
     }
   }
 }
 
 INITIALIZE_PASS_BEGIN(DPass, "dpass", "dpass", false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_END(DPass, "dpass", "dpass", false, false)