1 //=- llvm/Analysis/PostDominators.h - Post Dominator Calculation-*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file exposes interfaces to post dominance information.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_ANALYSIS_POSTDOMINATORS_H
15 #define LLVM_ANALYSIS_POSTDOMINATORS_H
16 
17 #include "llvm/IR/Dominators.h"
18 
19 namespace llvm {
20 
21 /// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to
22 /// compute the post-dominator tree.
23 ///
24 struct PostDominatorTree : public FunctionPass {
25   static char ID; // Pass identification, replacement for typeid
26   DominatorTreeBase<BasicBlock>* DT;
27 
PostDominatorTreePostDominatorTree28   PostDominatorTree() : FunctionPass(ID) {
29     initializePostDominatorTreePass(*PassRegistry::getPassRegistry());
30     DT = new DominatorTreeBase<BasicBlock>(true);
31   }
32 
33   ~PostDominatorTree() override;
34 
35   bool runOnFunction(Function &F) override;
36 
getAnalysisUsagePostDominatorTree37   void getAnalysisUsage(AnalysisUsage &AU) const override {
38     AU.setPreservesAll();
39   }
40 
getRootsPostDominatorTree41   inline const std::vector<BasicBlock*> &getRoots() const {
42     return DT->getRoots();
43   }
44 
getRootNodePostDominatorTree45   inline DomTreeNode *getRootNode() const {
46     return DT->getRootNode();
47   }
48 
49   inline DomTreeNode *operator[](BasicBlock *BB) const {
50     return DT->getNode(BB);
51   }
52 
getNodePostDominatorTree53   inline DomTreeNode *getNode(BasicBlock *BB) const {
54     return DT->getNode(BB);
55   }
56 
dominatesPostDominatorTree57   inline bool dominates(DomTreeNode* A, DomTreeNode* B) const {
58     return DT->dominates(A, B);
59   }
60 
dominatesPostDominatorTree61   inline bool dominates(const BasicBlock* A, const BasicBlock* B) const {
62     return DT->dominates(A, B);
63   }
64 
properlyDominatesPostDominatorTree65   inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const {
66     return DT->properlyDominates(A, B);
67   }
68 
properlyDominatesPostDominatorTree69   inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const {
70     return DT->properlyDominates(A, B);
71   }
72 
findNearestCommonDominatorPostDominatorTree73   inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) {
74     return DT->findNearestCommonDominator(A, B);
75   }
76 
findNearestCommonDominatorPostDominatorTree77   inline const BasicBlock *findNearestCommonDominator(const BasicBlock *A,
78                                                       const BasicBlock *B) {
79     return DT->findNearestCommonDominator(A, B);
80   }
81 
82   /// Get all nodes post-dominated by R, including R itself.
getDescendantsPostDominatorTree83   void getDescendants(BasicBlock *R,
84                       SmallVectorImpl<BasicBlock *> &Result) const {
85     DT->getDescendants(R, Result);
86   }
87 
releaseMemoryPostDominatorTree88   void releaseMemory() override {
89     DT->releaseMemory();
90   }
91 
92   void print(raw_ostream &OS, const Module*) const override;
93 };
94 
95 FunctionPass* createPostDomTree();
96 
97 template <> struct GraphTraits<PostDominatorTree*>
98   : public GraphTraits<DomTreeNode*> {
99   static NodeType *getEntryNode(PostDominatorTree *DT) {
100     return DT->getRootNode();
101   }
102 
103   static nodes_iterator nodes_begin(PostDominatorTree *N) {
104     if (getEntryNode(N))
105       return df_begin(getEntryNode(N));
106     else
107       return df_end(getEntryNode(N));
108   }
109 
110   static nodes_iterator nodes_end(PostDominatorTree *N) {
111     return df_end(getEntryNode(N));
112   }
113 };
114 
115 } // End llvm namespace
116 
117 #endif
118