include/llvm/Analysis/PostDominators.h

   1 //=- llvm/Analysis/PostDominators.h - Post Dominator Calculation --*- C++ -*-=//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file exposes interfaces to post dominance information.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef LLVM_ANALYSIS_POSTDOMINATORS_H
  14 #define LLVM_ANALYSIS_POSTDOMINATORS_H
  15
  16 #include "llvm/ADT/DepthFirstIterator.h"
  17 #include "llvm/IR/Dominators.h"
  18 #include "llvm/IR/PassManager.h"
  19 #include "llvm/Pass.h"
  20
  21 namespace llvm {
  22
  23 class Function;
  24 class raw_ostream;
  25
  26 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
  27 /// compute the post-dominator tree.
  28 class PostDominatorTree : public PostDomTreeBase<BasicBlock> {
  29 public:
  30   using Base = PostDomTreeBase<BasicBlock>;
  31
  32   PostDominatorTree() = default;
  33   explicit PostDominatorTree(Function &F) { recalculate(F); }
  34   /// Handle invalidation explicitly.
  35   bool invalidate(Function &F, const PreservedAnalyses &PA,
  36                   FunctionAnalysisManager::Invalidator &);
  37 };
  38
  39 /// Analysis pass which computes a \c PostDominatorTree.
  40 class PostDominatorTreeAnalysis
  41     : public AnalysisInfoMixin<PostDominatorTreeAnalysis> {
  42   friend AnalysisInfoMixin<PostDominatorTreeAnalysis>;
  43
  44   static AnalysisKey Key;
  45
  46 public:
  47   /// Provide the result type for this analysis pass.
  48   using Result = PostDominatorTree;
  49
  50   /// Run the analysis pass over a function and produce a post dominator
  51   ///        tree.
  52   PostDominatorTree run(Function &F, FunctionAnalysisManager &);
  53 };
  54
  55 /// Printer pass for the \c PostDominatorTree.
  56 class PostDominatorTreePrinterPass
  57     : public PassInfoMixin<PostDominatorTreePrinterPass> {
  58   raw_ostream &OS;
  59
  60 public:
  61   explicit PostDominatorTreePrinterPass(raw_ostream &OS);
  62
  63   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
  64 };
  65
  66 struct PostDominatorTreeWrapperPass : public FunctionPass {
  67   static char ID; // Pass identification, replacement for typeid
  68
  69   PostDominatorTree DT;
  70
  71   PostDominatorTreeWrapperPass() : FunctionPass(ID) {
  72     initializePostDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry());
  73   }
  74
  75   PostDominatorTree &getPostDomTree() { return DT; }
  76   const PostDominatorTree &getPostDomTree() const { return DT; }
  77
  78   bool runOnFunction(Function &F) override;
  79
  80   void verifyAnalysis() const override;
  81
  82   void getAnalysisUsage(AnalysisUsage &AU) const override {
  83     AU.setPreservesAll();
  84   }
  85
  86   void releaseMemory() override {
  87     DT.releaseMemory();
  88   }
  89
  90   void print(raw_ostream &OS, const Module*) const override;
  91 };
  92
  93 FunctionPass* createPostDomTree();
  94
  95 template <> struct GraphTraits<PostDominatorTree*>
  96   : public GraphTraits<DomTreeNode*> {
  97   static NodeRef getEntryNode(PostDominatorTree *DT) {
  98     return DT->getRootNode();
  99   }
 100
 101   static nodes_iterator nodes_begin(PostDominatorTree *N) {
 102     if (getEntryNode(N))
 103       return df_begin(getEntryNode(N));
 104     else
 105       return df_end(getEntryNode(N));
 106   }
 107
 108   static nodes_iterator nodes_end(PostDominatorTree *N) {
 109     return df_end(getEntryNode(N));
 110   }
 111 };
 112
 113 } // end namespace llvm
 114
 115 #endif // LLVM_ANALYSIS_POSTDOMINATORS_H