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
116