]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
1 | //===- Dominators.h - Dominator Info 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 defines the DominatorTree class, which provides fast and efficient | |
11 | // dominance queries. | |
12 | // | |
13 | //===----------------------------------------------------------------------===// | |
14 | ||
15 | #ifndef LLVM_IR_DOMINATORS_H | |
16 | #define LLVM_IR_DOMINATORS_H | |
17 | ||
18 | #include "llvm/ADT/DenseMap.h" | |
19 | #include "llvm/ADT/DepthFirstIterator.h" | |
20 | #include "llvm/ADT/GraphTraits.h" | |
21 | #include "llvm/ADT/SmallPtrSet.h" | |
22 | #include "llvm/ADT/SmallVector.h" | |
23 | #include "llvm/IR/BasicBlock.h" | |
24 | #include "llvm/IR/CFG.h" | |
25 | #include "llvm/IR/Function.h" | |
26 | #include "llvm/Pass.h" | |
27 | #include "llvm/Support/Compiler.h" | |
28 | #include "llvm/Support/GenericDomTree.h" | |
29 | #include "llvm/Support/raw_ostream.h" | |
30 | #include <algorithm> | |
31 | ||
32 | namespace llvm { | |
33 | ||
85aaf69f SL |
34 | // FIXME: Replace this brittle forward declaration with the include of the new |
35 | // PassManager.h when doing so doesn't break the PassManagerBuilder. | |
36 | template <typename IRUnitT> class AnalysisManager; | |
37 | class PreservedAnalyses; | |
38 | ||
1a4d82fc JJ |
39 | EXTERN_TEMPLATE_INSTANTIATION(class DomTreeNodeBase<BasicBlock>); |
40 | EXTERN_TEMPLATE_INSTANTIATION(class DominatorTreeBase<BasicBlock>); | |
41 | ||
42 | #define LLVM_COMMA , | |
43 | EXTERN_TEMPLATE_INSTANTIATION(void Calculate<Function LLVM_COMMA BasicBlock *>( | |
44 | DominatorTreeBase<GraphTraits<BasicBlock *>::NodeType> &DT LLVM_COMMA | |
45 | Function &F)); | |
46 | EXTERN_TEMPLATE_INSTANTIATION( | |
47 | void Calculate<Function LLVM_COMMA Inverse<BasicBlock *> >( | |
48 | DominatorTreeBase<GraphTraits<Inverse<BasicBlock *> >::NodeType> &DT | |
49 | LLVM_COMMA Function &F)); | |
50 | #undef LLVM_COMMA | |
51 | ||
52 | typedef DomTreeNodeBase<BasicBlock> DomTreeNode; | |
53 | ||
54 | class BasicBlockEdge { | |
55 | const BasicBlock *Start; | |
56 | const BasicBlock *End; | |
57 | public: | |
58 | BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) : | |
59 | Start(Start_), End(End_) { } | |
60 | const BasicBlock *getStart() const { | |
61 | return Start; | |
62 | } | |
63 | const BasicBlock *getEnd() const { | |
64 | return End; | |
65 | } | |
66 | bool isSingleEdge() const; | |
67 | }; | |
68 | ||
69 | /// \brief Concrete subclass of DominatorTreeBase that is used to compute a | |
70 | /// normal dominator tree. | |
71 | class DominatorTree : public DominatorTreeBase<BasicBlock> { | |
72 | public: | |
73 | typedef DominatorTreeBase<BasicBlock> Base; | |
74 | ||
75 | DominatorTree() : DominatorTreeBase<BasicBlock>(false) {} | |
76 | ||
85aaf69f SL |
77 | DominatorTree(DominatorTree &&Arg) |
78 | : Base(std::move(static_cast<Base &>(Arg))) {} | |
79 | DominatorTree &operator=(DominatorTree &&RHS) { | |
80 | Base::operator=(std::move(static_cast<Base &>(RHS))); | |
81 | return *this; | |
82 | } | |
83 | ||
1a4d82fc JJ |
84 | /// \brief Returns *false* if the other dominator tree matches this dominator |
85 | /// tree. | |
86 | inline bool compare(const DominatorTree &Other) const { | |
87 | const DomTreeNode *R = getRootNode(); | |
88 | const DomTreeNode *OtherR = Other.getRootNode(); | |
89 | ||
90 | if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) | |
91 | return true; | |
92 | ||
93 | if (Base::compare(Other)) | |
94 | return true; | |
95 | ||
96 | return false; | |
97 | } | |
98 | ||
99 | // Ensure base-class overloads are visible. | |
100 | using Base::dominates; | |
101 | ||
102 | /// \brief Return true if Def dominates a use in User. | |
103 | /// | |
104 | /// This performs the special checks necessary if Def and User are in the same | |
105 | /// basic block. Note that Def doesn't dominate a use in Def itself! | |
106 | bool dominates(const Instruction *Def, const Use &U) const; | |
107 | bool dominates(const Instruction *Def, const Instruction *User) const; | |
108 | bool dominates(const Instruction *Def, const BasicBlock *BB) const; | |
109 | bool dominates(const BasicBlockEdge &BBE, const Use &U) const; | |
110 | bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const; | |
111 | ||
112 | // Ensure base class overloads are visible. | |
113 | using Base::isReachableFromEntry; | |
114 | ||
115 | /// \brief Provide an overload for a Use. | |
116 | bool isReachableFromEntry(const Use &U) const; | |
117 | ||
118 | /// \brief Verify the correctness of the domtree by re-computing it. | |
119 | /// | |
120 | /// This should only be used for debugging as it aborts the program if the | |
121 | /// verification fails. | |
122 | void verifyDomTree() const; | |
123 | }; | |
124 | ||
125 | //===------------------------------------- | |
126 | // DominatorTree GraphTraits specializations so the DominatorTree can be | |
127 | // iterable by generic graph iterators. | |
128 | ||
129 | template <> struct GraphTraits<DomTreeNode*> { | |
130 | typedef DomTreeNode NodeType; | |
131 | typedef NodeType::iterator ChildIteratorType; | |
132 | ||
133 | static NodeType *getEntryNode(NodeType *N) { | |
134 | return N; | |
135 | } | |
136 | static inline ChildIteratorType child_begin(NodeType *N) { | |
137 | return N->begin(); | |
138 | } | |
139 | static inline ChildIteratorType child_end(NodeType *N) { | |
140 | return N->end(); | |
141 | } | |
142 | ||
143 | typedef df_iterator<DomTreeNode*> nodes_iterator; | |
144 | ||
145 | static nodes_iterator nodes_begin(DomTreeNode *N) { | |
146 | return df_begin(getEntryNode(N)); | |
147 | } | |
148 | ||
149 | static nodes_iterator nodes_end(DomTreeNode *N) { | |
150 | return df_end(getEntryNode(N)); | |
151 | } | |
152 | }; | |
153 | ||
154 | template <> struct GraphTraits<DominatorTree*> | |
155 | : public GraphTraits<DomTreeNode*> { | |
156 | static NodeType *getEntryNode(DominatorTree *DT) { | |
157 | return DT->getRootNode(); | |
158 | } | |
159 | ||
160 | static nodes_iterator nodes_begin(DominatorTree *N) { | |
161 | return df_begin(getEntryNode(N)); | |
162 | } | |
163 | ||
164 | static nodes_iterator nodes_end(DominatorTree *N) { | |
165 | return df_end(getEntryNode(N)); | |
166 | } | |
167 | }; | |
168 | ||
169 | /// \brief Analysis pass which computes a \c DominatorTree. | |
85aaf69f SL |
170 | class DominatorTreeAnalysis { |
171 | public: | |
172 | /// \brief Provide the result typedef for this analysis pass. | |
173 | typedef DominatorTree Result; | |
174 | ||
175 | /// \brief Opaque, unique identifier for this analysis pass. | |
176 | static void *ID() { return (void *)&PassID; } | |
177 | ||
178 | /// \brief Run the analysis pass over a function and produce a dominator tree. | |
179 | DominatorTree run(Function &F); | |
180 | ||
181 | /// \brief Provide access to a name for this pass for debugging purposes. | |
182 | static StringRef name() { return "DominatorTreeAnalysis"; } | |
183 | ||
184 | private: | |
185 | static char PassID; | |
186 | }; | |
187 | ||
188 | /// \brief Printer pass for the \c DominatorTree. | |
189 | class DominatorTreePrinterPass { | |
190 | raw_ostream &OS; | |
191 | ||
192 | public: | |
193 | explicit DominatorTreePrinterPass(raw_ostream &OS); | |
194 | PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); | |
195 | ||
196 | static StringRef name() { return "DominatorTreePrinterPass"; } | |
197 | }; | |
198 | ||
199 | /// \brief Verifier pass for the \c DominatorTree. | |
200 | struct DominatorTreeVerifierPass { | |
201 | PreservedAnalyses run(Function &F, AnalysisManager<Function> *AM); | |
202 | ||
203 | static StringRef name() { return "DominatorTreeVerifierPass"; } | |
204 | }; | |
205 | ||
206 | /// \brief Legacy analysis pass which computes a \c DominatorTree. | |
1a4d82fc JJ |
207 | class DominatorTreeWrapperPass : public FunctionPass { |
208 | DominatorTree DT; | |
209 | ||
210 | public: | |
211 | static char ID; | |
212 | ||
213 | DominatorTreeWrapperPass() : FunctionPass(ID) { | |
214 | initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry()); | |
215 | } | |
216 | ||
217 | DominatorTree &getDomTree() { return DT; } | |
218 | const DominatorTree &getDomTree() const { return DT; } | |
219 | ||
220 | bool runOnFunction(Function &F) override; | |
221 | ||
222 | void verifyAnalysis() const override; | |
223 | ||
224 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |
225 | AU.setPreservesAll(); | |
226 | } | |
227 | ||
228 | void releaseMemory() override { DT.releaseMemory(); } | |
229 | ||
230 | void print(raw_ostream &OS, const Module *M = nullptr) const override; | |
231 | }; | |
232 | ||
233 | } // End llvm namespace | |
234 | ||
235 | #endif |