/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/include/llvm/IR/Dominators.h
Line | Count | Source (jump to first uncovered line) |
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/DenseMapInfo.h" |
19 | | #include "llvm/ADT/DepthFirstIterator.h" |
20 | | #include "llvm/ADT/GraphTraits.h" |
21 | | #include "llvm/ADT/Hashing.h" |
22 | | #include "llvm/IR/BasicBlock.h" |
23 | | #include "llvm/IR/CFG.h" |
24 | | #include "llvm/IR/PassManager.h" |
25 | | #include "llvm/Pass.h" |
26 | | #include "llvm/Support/GenericDomTree.h" |
27 | | #include <utility> |
28 | | |
29 | | namespace llvm { |
30 | | |
31 | | class Function; |
32 | | class Instruction; |
33 | | class Module; |
34 | | class raw_ostream; |
35 | | |
36 | | extern template class DomTreeNodeBase<BasicBlock>; |
37 | | extern template class DominatorTreeBase<BasicBlock, false>; // DomTree |
38 | | extern template class DominatorTreeBase<BasicBlock, true>; // PostDomTree |
39 | | |
40 | | namespace DomTreeBuilder { |
41 | | using BBDomTree = DomTreeBase<BasicBlock>; |
42 | | using BBPostDomTree = PostDomTreeBase<BasicBlock>; |
43 | | |
44 | | extern template struct Update<BasicBlock *>; |
45 | | |
46 | | using BBUpdates = ArrayRef<Update<BasicBlock *>>; |
47 | | |
48 | | extern template void Calculate<BBDomTree>(BBDomTree &DT); |
49 | | extern template void Calculate<BBPostDomTree>(BBPostDomTree &DT); |
50 | | |
51 | | extern template void InsertEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From, |
52 | | BasicBlock *To); |
53 | | extern template void InsertEdge<BBPostDomTree>(BBPostDomTree &DT, |
54 | | BasicBlock *From, |
55 | | BasicBlock *To); |
56 | | |
57 | | extern template void DeleteEdge<BBDomTree>(BBDomTree &DT, BasicBlock *From, |
58 | | BasicBlock *To); |
59 | | extern template void DeleteEdge<BBPostDomTree>(BBPostDomTree &DT, |
60 | | BasicBlock *From, |
61 | | BasicBlock *To); |
62 | | |
63 | | extern template void ApplyUpdates<BBDomTree>(BBDomTree &DT, BBUpdates); |
64 | | extern template void ApplyUpdates<BBPostDomTree>(BBPostDomTree &DT, BBUpdates); |
65 | | |
66 | | extern template bool Verify<BBDomTree>(const BBDomTree &DT); |
67 | | extern template bool Verify<BBPostDomTree>(const BBPostDomTree &DT); |
68 | | } // namespace DomTreeBuilder |
69 | | |
70 | | using DomTreeNode = DomTreeNodeBase<BasicBlock>; |
71 | | |
72 | | class BasicBlockEdge { |
73 | | const BasicBlock *Start; |
74 | | const BasicBlock *End; |
75 | | |
76 | | public: |
77 | | BasicBlockEdge(const BasicBlock *Start_, const BasicBlock *End_) : |
78 | 16.8M | Start(Start_), End(End_) {} |
79 | | |
80 | | BasicBlockEdge(const std::pair<BasicBlock *, BasicBlock *> &Pair) |
81 | 27 | : Start(Pair.first), End(Pair.second) {} |
82 | | |
83 | | BasicBlockEdge(const std::pair<const BasicBlock *, const BasicBlock *> &Pair) |
84 | 0 | : Start(Pair.first), End(Pair.second) {} |
85 | | |
86 | 16.9M | const BasicBlock *getStart() const { |
87 | 16.9M | return Start; |
88 | 16.9M | } |
89 | | |
90 | 36.0M | const BasicBlock *getEnd() const { |
91 | 36.0M | return End; |
92 | 36.0M | } |
93 | | |
94 | | /// Check if this is the only edge between Start and End. |
95 | | bool isSingleEdge() const; |
96 | | }; |
97 | | |
98 | | template <> struct DenseMapInfo<BasicBlockEdge> { |
99 | | using BBInfo = DenseMapInfo<const BasicBlock *>; |
100 | | |
101 | | static unsigned getHashValue(const BasicBlockEdge *V); |
102 | | |
103 | 5.25k | static inline BasicBlockEdge getEmptyKey() { |
104 | 5.25k | return BasicBlockEdge(BBInfo::getEmptyKey(), BBInfo::getEmptyKey()); |
105 | 5.25k | } |
106 | | |
107 | 4.09k | static inline BasicBlockEdge getTombstoneKey() { |
108 | 4.09k | return BasicBlockEdge(BBInfo::getTombstoneKey(), BBInfo::getTombstoneKey()); |
109 | 4.09k | } |
110 | | |
111 | 2.57k | static unsigned getHashValue(const BasicBlockEdge &Edge) { |
112 | 2.57k | return hash_combine(BBInfo::getHashValue(Edge.getStart()), |
113 | 2.57k | BBInfo::getHashValue(Edge.getEnd())); |
114 | 2.57k | } |
115 | | |
116 | 29.5k | static bool isEqual(const BasicBlockEdge &LHS, const BasicBlockEdge &RHS) { |
117 | 29.5k | return BBInfo::isEqual(LHS.getStart(), RHS.getStart()) && |
118 | 25.2k | BBInfo::isEqual(LHS.getEnd(), RHS.getEnd()); |
119 | 29.5k | } |
120 | | }; |
121 | | |
122 | | /// \brief Concrete subclass of DominatorTreeBase that is used to compute a |
123 | | /// normal dominator tree. |
124 | | /// |
125 | | /// Definition: A block is said to be forward statically reachable if there is |
126 | | /// a path from the entry of the function to the block. A statically reachable |
127 | | /// block may become statically unreachable during optimization. |
128 | | /// |
129 | | /// A forward unreachable block may appear in the dominator tree, or it may |
130 | | /// not. If it does, dominance queries will return results as if all reachable |
131 | | /// blocks dominate it. When asking for a Node corresponding to a potentially |
132 | | /// unreachable block, calling code must handle the case where the block was |
133 | | /// unreachable and the result of getNode() is nullptr. |
134 | | /// |
135 | | /// Generally, a block known to be unreachable when the dominator tree is |
136 | | /// constructed will not be in the tree. One which becomes unreachable after |
137 | | /// the dominator tree is initially constructed may still exist in the tree, |
138 | | /// even if the tree is properly updated. Calling code should not rely on the |
139 | | /// preceding statements; this is stated only to assist human understanding. |
140 | | class DominatorTree : public DominatorTreeBase<BasicBlock, false> { |
141 | | public: |
142 | | using Base = DominatorTreeBase<BasicBlock, false>; |
143 | | |
144 | 846k | DominatorTree() = default; |
145 | 53.0k | explicit DominatorTree(Function &F) { recalculate(F); } |
146 | | |
147 | | /// Handle invalidation explicitly. |
148 | | bool invalidate(Function &F, const PreservedAnalyses &PA, |
149 | | FunctionAnalysisManager::Invalidator &); |
150 | | |
151 | | /// \brief Returns *false* if the other dominator tree matches this dominator |
152 | | /// tree. |
153 | 47 | inline bool compare(const DominatorTree &Other) const { |
154 | 47 | const DomTreeNode *R = getRootNode(); |
155 | 47 | const DomTreeNode *OtherR = Other.getRootNode(); |
156 | 47 | return !R || !OtherR47 || R->getBlock() != OtherR->getBlock()47 || |
157 | 47 | Base::compare(Other); |
158 | 47 | } |
159 | | |
160 | | // Ensure base-class overloads are visible. |
161 | | using Base::dominates; |
162 | | |
163 | | /// \brief Return true if Def dominates a use in User. |
164 | | /// |
165 | | /// This performs the special checks necessary if Def and User are in the same |
166 | | /// basic block. Note that Def doesn't dominate a use in Def itself! |
167 | | bool dominates(const Instruction *Def, const Use &U) const; |
168 | | bool dominates(const Instruction *Def, const Instruction *User) const; |
169 | | bool dominates(const Instruction *Def, const BasicBlock *BB) const; |
170 | | |
171 | | /// Return true if an edge dominates a use. |
172 | | /// |
173 | | /// If BBE is not a unique edge between start and end of the edge, it can |
174 | | /// never dominate the use. |
175 | | bool dominates(const BasicBlockEdge &BBE, const Use &U) const; |
176 | | bool dominates(const BasicBlockEdge &BBE, const BasicBlock *BB) const; |
177 | | |
178 | | // Ensure base class overloads are visible. |
179 | | using Base::isReachableFromEntry; |
180 | | |
181 | | /// \brief Provide an overload for a Use. |
182 | | bool isReachableFromEntry(const Use &U) const; |
183 | | |
184 | | /// \brief Verify the correctness of the domtree by re-computing it. |
185 | | /// |
186 | | /// This should only be used for debugging as it aborts the program if the |
187 | | /// verification fails. |
188 | | void verifyDomTree() const; |
189 | | |
190 | | // Pop up a GraphViz/gv window with the Dominator Tree rendered using `dot`. |
191 | | void viewGraph(const Twine &Name, const Twine &Title); |
192 | | void viewGraph(); |
193 | | }; |
194 | | |
195 | | //===------------------------------------- |
196 | | // DominatorTree GraphTraits specializations so the DominatorTree can be |
197 | | // iterable by generic graph iterators. |
198 | | |
199 | | template <class Node, class ChildIterator> struct DomTreeGraphTraitsBase { |
200 | | using NodeRef = Node *; |
201 | | using ChildIteratorType = ChildIterator; |
202 | | using nodes_iterator = df_iterator<Node *, df_iterator_default_set<Node*>>; |
203 | | |
204 | 9.16M | static NodeRef getEntryNode(NodeRef N) { return N; } llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::BasicBlock>, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::BasicBlock>**> >::getEntryNode(llvm::DomTreeNodeBase<llvm::BasicBlock>*) Line | Count | Source | 204 | 690k | static NodeRef getEntryNode(NodeRef N) { return N; } |
llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::BasicBlock> const, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::BasicBlock>* const*> >::getEntryNode(llvm::DomTreeNodeBase<llvm::BasicBlock> const*) Line | Count | Source | 204 | 8.47M | static NodeRef getEntryNode(NodeRef N) { return N; } |
|
205 | 63.5M | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::BasicBlock>, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::BasicBlock>**> >::child_begin(llvm::DomTreeNodeBase<llvm::BasicBlock>*) Line | Count | Source | 205 | 4.65M | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::BasicBlock> const, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::BasicBlock>* const*> >::child_begin(llvm::DomTreeNodeBase<llvm::BasicBlock> const*) Line | Count | Source | 205 | 58.9M | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
|
206 | 117M | static ChildIteratorType child_end(NodeRef N) { return N->end(); } llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::BasicBlock>, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::BasicBlock>**> >::child_end(llvm::DomTreeNodeBase<llvm::BasicBlock>*) Line | Count | Source | 206 | 8.03M | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
llvm::DomTreeGraphTraitsBase<llvm::DomTreeNodeBase<llvm::BasicBlock> const, std::__1::__wrap_iter<llvm::DomTreeNodeBase<llvm::BasicBlock>* const*> >::child_end(llvm::DomTreeNodeBase<llvm::BasicBlock> const*) Line | Count | Source | 206 | 109M | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
|
207 | | |
208 | | static nodes_iterator nodes_begin(NodeRef N) { |
209 | | return df_begin(getEntryNode(N)); |
210 | | } |
211 | | |
212 | | static nodes_iterator nodes_end(NodeRef N) { return df_end(getEntryNode(N)); } |
213 | | }; |
214 | | |
215 | | template <> |
216 | | struct GraphTraits<DomTreeNode *> |
217 | | : public DomTreeGraphTraitsBase<DomTreeNode, DomTreeNode::iterator> {}; |
218 | | |
219 | | template <> |
220 | | struct GraphTraits<const DomTreeNode *> |
221 | | : public DomTreeGraphTraitsBase<const DomTreeNode, |
222 | | DomTreeNode::const_iterator> {}; |
223 | | |
224 | | template <> struct GraphTraits<DominatorTree*> |
225 | | : public GraphTraits<DomTreeNode*> { |
226 | 60.7k | static NodeRef getEntryNode(DominatorTree *DT) { return DT->getRootNode(); } |
227 | | |
228 | 307 | static nodes_iterator nodes_begin(DominatorTree *N) { |
229 | 307 | return df_begin(getEntryNode(N)); |
230 | 307 | } |
231 | | |
232 | 307 | static nodes_iterator nodes_end(DominatorTree *N) { |
233 | 307 | return df_end(getEntryNode(N)); |
234 | 307 | } |
235 | | }; |
236 | | |
237 | | /// \brief Analysis pass which computes a \c DominatorTree. |
238 | | class DominatorTreeAnalysis : public AnalysisInfoMixin<DominatorTreeAnalysis> { |
239 | | friend AnalysisInfoMixin<DominatorTreeAnalysis>; |
240 | | static AnalysisKey Key; |
241 | | |
242 | | public: |
243 | | /// \brief Provide the result typedef for this analysis pass. |
244 | | using Result = DominatorTree; |
245 | | |
246 | | /// \brief Run the analysis pass over a function and produce a dominator tree. |
247 | | DominatorTree run(Function &F, FunctionAnalysisManager &); |
248 | | }; |
249 | | |
250 | | /// \brief Printer pass for the \c DominatorTree. |
251 | | class DominatorTreePrinterPass |
252 | | : public PassInfoMixin<DominatorTreePrinterPass> { |
253 | | raw_ostream &OS; |
254 | | |
255 | | public: |
256 | | explicit DominatorTreePrinterPass(raw_ostream &OS); |
257 | | |
258 | | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
259 | | }; |
260 | | |
261 | | /// \brief Verifier pass for the \c DominatorTree. |
262 | | struct DominatorTreeVerifierPass : PassInfoMixin<DominatorTreeVerifierPass> { |
263 | | PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); |
264 | | }; |
265 | | |
266 | | /// \brief Legacy analysis pass which computes a \c DominatorTree. |
267 | | class DominatorTreeWrapperPass : public FunctionPass { |
268 | | DominatorTree DT; |
269 | | |
270 | | public: |
271 | | static char ID; |
272 | | |
273 | 516k | DominatorTreeWrapperPass() : FunctionPass(ID) { |
274 | 516k | initializeDominatorTreeWrapperPassPass(*PassRegistry::getPassRegistry()); |
275 | 516k | } |
276 | | |
277 | 63.9M | DominatorTree &getDomTree() { return DT; } |
278 | 0 | const DominatorTree &getDomTree() const { return DT; } |
279 | | |
280 | | bool runOnFunction(Function &F) override; |
281 | | |
282 | | void verifyAnalysis() const override; |
283 | | |
284 | 484k | void getAnalysisUsage(AnalysisUsage &AU) const override { |
285 | 484k | AU.setPreservesAll(); |
286 | 484k | } |
287 | | |
288 | 11.3M | void releaseMemory() override { DT.releaseMemory(); } |
289 | | |
290 | | void print(raw_ostream &OS, const Module *M = nullptr) const override; |
291 | | }; |
292 | | |
293 | | } // end namespace llvm |
294 | | |
295 | | #endif // LLVM_IR_DOMINATORS_H |