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   // Ensure base-class overloads are visible.
39   using Base::dominates;
40 
41   /// Return true if \p I1 dominates \p I2. This checks if \p I2 comes before
42   /// \p I1 if they belongs to the same basic block.
43   bool dominates(const Instruction *I1, const Instruction *I2) const;
44 };
45 
46 /// Analysis pass which computes a \c PostDominatorTree.
47 class PostDominatorTreeAnalysis
48     : public AnalysisInfoMixin<PostDominatorTreeAnalysis> {
49   friend AnalysisInfoMixin<PostDominatorTreeAnalysis>;
50 
51   static AnalysisKey Key;
52 
53 public:
54   /// Provide the result type for this analysis pass.
55   using Result = PostDominatorTree;
56 
57   /// Run the analysis pass over a function and produce a post dominator
58   ///        tree.
59   PostDominatorTree run(Function &F, FunctionAnalysisManager &);
60 };
61 
62 /// Printer pass for the \c PostDominatorTree.
63 class PostDominatorTreePrinterPass
64     : public PassInfoMixin<PostDominatorTreePrinterPass> {
65   raw_ostream &OS;
66 
67 public:
68   explicit PostDominatorTreePrinterPass(raw_ostream &OS);
69 
70   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
71 };
72 
73 struct PostDominatorTreeWrapperPass : public FunctionPass {
74   static char ID; // Pass identification, replacement for typeid
75 
76   PostDominatorTree DT;
77 
78   PostDominatorTreeWrapperPass();
79 
80   PostDominatorTree &getPostDomTree() { return DT; }
81   const PostDominatorTree &getPostDomTree() const { return DT; }
82 
83   bool runOnFunction(Function &F) override;
84 
85   void verifyAnalysis() const override;
86 
87   void getAnalysisUsage(AnalysisUsage &AU) const override {
88     AU.setPreservesAll();
89   }
90 
91   void releaseMemory() override {
92     DT.releaseMemory();
93   }
94 
95   void print(raw_ostream &OS, const Module*) const override;
96 };
97 
98 FunctionPass* createPostDomTree();
99 
100 template <> struct GraphTraits<PostDominatorTree*>
101   : public GraphTraits<DomTreeNode*> {
102   static NodeRef getEntryNode(PostDominatorTree *DT) {
103     return DT->getRootNode();
104   }
105 
106   static nodes_iterator nodes_begin(PostDominatorTree *N) {
107     if (getEntryNode(N))
108       return df_begin(getEntryNode(N));
109     else
110       return df_end(getEntryNode(N));
111   }
112 
113   static nodes_iterator nodes_end(PostDominatorTree *N) {
114     return df_end(getEntryNode(N));
115   }
116 };
117 
118 } // end namespace llvm
119 
120 #endif // LLVM_ANALYSIS_POSTDOMINATORS_H
121