[PM] Convert post-dominator to mimic dominator passes

[david2050]

I made these changes to support a new pass which is not directly relevant. I modeled them after the changes to Dominator and thought they might be valuable alone

[david2050]

overtaken by events

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);
+struct PostDominatorTree {
+  DominatorTreeBase<BasicBlock> *DT;
+  PostDominatorTree() : DT(new DominatorTreeBase<BasicBlock>(true)) { }
+  PostDominatorTree(PostDominatorTree &&PDT) {
+    DT = PDT.DT;
+    PDT.DT = nullptr;
+  }
+  PostDominatorTree & operator= (PostDominatorTree &&PDT) {
+    DT = PDT.DT;
+    PDT.DT = nullptr;
+    return *this;
+  }
+  void releaseMemory() { DT->releaseMemory(); }
+  
+  void print(raw_ostream &OS, const Module *) const;
+  
+  ~PostDominatorTree() {
+    if(DT) {
+      delete DT;
     }
-
-  ~PostDominatorTree() override;
-
-  bool runOnFunction(Function &F) override;
-
-  void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.setPreservesAll();
   }
   
-  inline const std::vector<BasicBlock*> &getRoots() const {
+  inline const std::vector<BasicBlock *> &getRoots() const {
     return DT->getRoots();
   }
 
   inline DomTreeNode *getRootNode() const {
     return DT->getRootNode();
   }
 
   inline DomTreeNode *operator[](BasicBlock *BB) const {
inline const BasicBlock *findNearestCommonDominator(const BasicBlock *A,
     return DT->findNearestCommonDominator(A, B);
   }
 
   /// Get all nodes post-dominated by R, including R itself.
   void getDescendants(BasicBlock *R,
                       SmallVectorImpl<BasicBlock *> &Result) const {
     DT->getDescendants(R, Result);
   }
-
-  void releaseMemory() override {
-    DT->releaseMemory();
-  }
-
-  void print(raw_ostream &OS, const Module*) const override;
 };
 
 FunctionPass* createPostDomTree();
 
 template <> struct GraphTraits<PostDominatorTree*>
   : public GraphTraits<DomTreeNode*> {
   static NodeType *getEntryNode(PostDominatorTree *DT) {
     return DT->getRootNode();
   }
 
   static nodes_iterator nodes_begin(PostDominatorTree *N) {
     if (getEntryNode(N))
       return df_begin(getEntryNode(N));
     else
       return df_end(getEntryNode(N));
   }
 
   static nodes_iterator nodes_end(PostDominatorTree *N) {
     return df_end(getEntryNode(N));
   }
 };
 
+/// \brief Legacy analysis pass which computes a \c PostDominatorTree.
+class PostDominatorTreeWrapperPass : public FunctionPass {
+  PostDominatorTree DT;
+
+public:
+  static char ID;
+
+  PostDominatorTreeWrapperPass() : FunctionPass(ID) {
+    initializePostDominatorTreeWrapperPassPass(
+        *PassRegistry::getPassRegistry());
+  }
+
+  PostDominatorTree &getDomTree() { return DT; }
+  const PostDominatorTree &getDomTree() const { return DT; }
+
+  bool runOnFunction(Function &F) override;
+
+  void verifyAnalysis() const override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+
+  void releaseMemory() override { DT.DT->releaseMemory(); }
+
+  void print(raw_ostream &OS, const Module *M = nullptr) const override;
+};
+
+/// \brief Analysis pass which computes a \c DominatorTree.
+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);
+
+  /// \brief Provide access to a name for this pass for debugging purposes.
+  static StringRef name() { return "PostßDominatorTreeAnalysis"; }
+
+private:
+  static char PassID;
+};
+
 } // End llvm namespace
 
 #endif

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 initializePostOrderFunctionAttrsPass(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();
-  DivergencePropagator DP(F, TTI,
-                          getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
-                          getAnalysis<PostDominatorTree>(), DivergentValues);
+  DivergencePropagator DP(
+      F, TTI, getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
+      getAnalysis<PostDominatorTreeWrapperPass>().getDomTree(),
+      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 *DTWP) {
+    return &DTWP->getDomTree();
+  }
+};
+
+struct PostDomViewer : public DOTGraphTraitsViewer<
+                           PostDominatorTreeWrapperPass, false, PostDominatorTree *,
+                           PostDominatorTreeWrapperPassAnalysisGraphTraits> {
   static char ID;
-  PostDomViewer() :
-    DOTGraphTraitsViewer<PostDominatorTree, false>("postdom", ID){
-      initializePostDomViewerPass(*PassRegistry::getPassRegistry());
-    }
+  PostDomViewer()
+      : DOTGraphTraitsViewer<PostDominatorTreeWrapperPass, false, PostDominatorTree *,
+                             PostDominatorTreeWrapperPassAnalysisGraphTraits>(
+            "postdom", ID) {
 };
 
 struct PostDomOnlyViewer
-  : public DOTGraphTraitsViewer<PostDominatorTree, true> {
+    : public DOTGraphTraitsViewer<
+          PostDominatorTreeWrapperPass, true, PostDominatorTree *,
+          PostDominatorTreeWrapperPassAnalysisGraphTraits> {
   static char ID;
-  PostDomOnlyViewer() :
-    DOTGraphTraitsViewer<PostDominatorTree, true>("postdomonly", ID){
-      initializePostDomOnlyViewerPass(*PassRegistry::getPassRegistry());
-    }
+  PostDomOnlyViewer()
+      : DOTGraphTraitsViewer<PostDominatorTreeWrapperPass, true,
+                             PostDominatorTree *,
+                             PostDominatorTreeWrapperPassAnalysisGraphTraits>(
+            "postdomonly", ID) {
 };
 } // end anonymous namespace
 
 char DomViewer::ID = 0;
 INITIALIZE_PASS(DomViewer, "view-dom",
                 "View dominance tree of function", false, false)
 
 char DomOnlyViewer::ID = 0;
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/Support/GenericDomTreeConstruction.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "postdomtree"
 
 //===----------------------------------------------------------------------===//
 //  PostDominatorTree Implementation
 //===----------------------------------------------------------------------===//
+void PostDominatorTree::print(raw_ostream &OS, const Module *) const {
+  DT->print(OS);
+}
 
-char PostDominatorTree::ID = 0;
-INITIALIZE_PASS(PostDominatorTree, "postdomtree",
-                "Post-Dominator Tree Construction", true, true)
 
-bool PostDominatorTree::runOnFunction(Function &F) {
-  DT->recalculate(F);
-  return false;
+//===----------------------------------------------------------------------===//
+//  DominatorTreeAnalysis and related pass implementations
+//===----------------------------------------------------------------------===//
+//
+// This implements the DominatorTreeAnalysis which is used with the new pass
+// manager. It also implements some methods from utility passes.
+//
+//===----------------------------------------------------------------------===//
+PostDominatorTree PostDominatorTreeAnalysis::run(Function &F) {
+  PostDominatorTree DT;
+  DT.DT->recalculate(F);
+  return DT;
 }
 
-PostDominatorTree::~PostDominatorTree() {
-  delete DT;
+char PostDominatorTreeAnalysis::PassID;
+
+FunctionPass* llvm::createPostDomTree() {
+  return new PostDominatorTreeWrapperPass();
 }
 
-void PostDominatorTree::print(raw_ostream &OS, const Module *) const {
-  DT->print(OS);
+//===----------------------------------------------------------------------===//
+//  DominatorTreeWrapperPass Implementation
+//===----------------------------------------------------------------------===//
+//
+// The implementation details of the wrapper pass that holds a DominatorTree
+// suitable for use with the legacy pass manager.
+//
+//===----------------------------------------------------------------------===//
+
+char PostDominatorTreeWrapperPass::ID = 0;
+INITIALIZE_PASS(PostDominatorTreeWrapperPass, "postdomtree",
+                "Post-Dominator Tree Construction", true, true)
+
+bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) {
+  DT.DT->recalculate(F);
+  return false;
 }
 
+void PostDominatorTreeWrapperPass::verifyAnalysis() const {
+#if 0
+  if (VerifyDomInfo)
+    DT.DT->VerifyDomTree();
+#endif
+}
 
-FunctionPass* llvm::createPostDomTree() {
-  return new PostDominatorTree();
+void PostDominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {
+  DT.DT->print(OS);
 }
 

lib/Analysis/RegionInfo.cpp

 RegionInfoPass::~RegionInfoPass() {
 
 }
 
 bool RegionInfoPass::runOnFunction(Function &F) {
   releaseMemory();
 
   auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  auto PDT = &getAnalysis<PostDominatorTree>();
+  auto PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getDomTree();
   auto DF = &getAnalysis<DominanceFrontier>();
 
   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<PostDominatorTree>();
+  AU.addRequired<PostDominatorTreeWrapperPass>();
   AU.addRequired<DominanceFrontier>();
 }
 
 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(PostDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominanceFrontier)
 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();
   }
 }
 

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/Target/Hexagon/HexagonCommonGEP.cpp

public:
     virtual bool runOnFunction(Function &F);
     virtual const char *getPassName() const {
       return "Hexagon Common GEP";
     }
 
     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
       AU.addRequired<DominatorTreeWrapperPass>();
       AU.addPreserved<DominatorTreeWrapperPass>();
-      AU.addRequired<PostDominatorTree>();
-      AU.addPreserved<PostDominatorTree>();
+      AU.addRequired<PostDominatorTreeWrapperPass>();
+      AU.addPreserved<PostDominatorTreeWrapperPass>();
       AU.addRequired<LoopInfoWrapperPass>();
       AU.addPreserved<LoopInfoWrapperPass>();
       FunctionPass::getAnalysisUsage(AU);
     }
 
+    
   private:
     typedef std::map<Value*,GepNode*> ValueToNodeMap;
     typedef std::vector<Value*> ValueVect;
     typedef std::map<GepNode*,ValueVect> NodeToValuesMap;
 
     void getBlockTraversalOrder(BasicBlock *Root, ValueVect &Order);
     bool isHandledGepForm(GetElementPtrInst *GepI);
     void processGepInst(GetElementPtrInst *GepI, ValueToNodeMap &NM);
namespace {
   };
 }
 
 
 char HexagonCommonGEP::ID = 0;
 INITIALIZE_PASS_BEGIN(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
       false, false)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
-INITIALIZE_PASS_DEPENDENCY(PostDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 INITIALIZE_PASS_END(HexagonCommonGEP, "hcommgep", "Hexagon Common GEP",
       false, false)
 
 namespace {
   struct GepNode {
     enum {
       None      = 0,
bool HexagonCommonGEP::runOnFunction(Function &F) {
   // For now bail out on C++ exception handling.
   for (Function::iterator A = F.begin(), Z = F.end(); A != Z; ++A)
     for (BasicBlock::iterator I = A->begin(), E = A->end(); I != E; ++I)
       if (isa<InvokeInst>(I) || isa<LandingPadInst>(I))
         return false;
 
   Fn = &F;
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  PDT = &getAnalysis<PostDominatorTree>();
+  PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getDomTree();
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   Ctx = &F.getContext();
 
   Nodes.clear();
   Uses.clear();
   NodeOrder.clear();
 
   SpecificBumpPtrAllocator<GepNode> Allocator;

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>().getDomTree();
         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)