/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/Analyses/Dominators.h
Line | Count | Source (jump to first uncovered line) |
1 | | //- Dominators.h - Implementation of dominators tree for Clang CFG -*- 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 implements the dominators tree functionality for Clang CFGs. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H |
14 | | #define LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H |
15 | | |
16 | | #include "clang/Analysis/AnalysisDeclContext.h" |
17 | | #include "clang/Analysis/CFG.h" |
18 | | #include "llvm/ADT/DepthFirstIterator.h" |
19 | | #include "llvm/ADT/GraphTraits.h" |
20 | | #include "llvm/ADT/iterator.h" |
21 | | #include "llvm/Support/GenericIteratedDominanceFrontier.h" |
22 | | #include "llvm/Support/GenericDomTree.h" |
23 | | #include "llvm/Support/GenericDomTreeConstruction.h" |
24 | | #include "llvm/Support/raw_ostream.h" |
25 | | |
26 | | // FIXME: There is no good reason for the domtree to require a print method |
27 | | // which accepts an LLVM Module, so remove this (and the method's argument that |
28 | | // needs it) when that is fixed. |
29 | | |
30 | | namespace llvm { |
31 | | |
32 | | class Module; |
33 | | |
34 | | } // namespace llvm |
35 | | |
36 | | namespace clang { |
37 | | |
38 | | using DomTreeNode = llvm::DomTreeNodeBase<CFGBlock>; |
39 | | |
40 | | /// Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase. |
41 | | template <bool IsPostDom> |
42 | | class CFGDominatorTreeImpl : public ManagedAnalysis { |
43 | | virtual void anchor(); |
44 | | |
45 | | public: |
46 | | using DominatorTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>; |
47 | | |
48 | 20 | CFGDominatorTreeImpl() = default; clang::CFGDominatorTreeImpl<false>::CFGDominatorTreeImpl() Line | Count | Source | 48 | 10 | CFGDominatorTreeImpl() = default; |
clang::CFGDominatorTreeImpl<true>::CFGDominatorTreeImpl() Line | Count | Source | 48 | 10 | CFGDominatorTreeImpl() = default; |
|
49 | | |
50 | 5.12k | CFGDominatorTreeImpl(CFG *cfg) { |
51 | 5.12k | buildDominatorTree(cfg); |
52 | 5.12k | } |
53 | | |
54 | 5.14k | ~CFGDominatorTreeImpl() override = default; clang::CFGDominatorTreeImpl<false>::~CFGDominatorTreeImpl() Line | Count | Source | 54 | 10 | ~CFGDominatorTreeImpl() override = default; |
clang::CFGDominatorTreeImpl<true>::~CFGDominatorTreeImpl() Line | Count | Source | 54 | 5.13k | ~CFGDominatorTreeImpl() override = default; |
|
55 | | |
56 | 5.12k | DominatorTreeBase &getBase() { return DT; } |
57 | | |
58 | 9 | CFG *getCFG() { return cfg; } |
59 | | |
60 | | /// \returns the root CFGBlock of the dominators tree. |
61 | | CFGBlock *getRoot() const { |
62 | | return DT.getRoot(); |
63 | | } |
64 | | |
65 | | /// \returns the root DomTreeNode, which is the wrapper for CFGBlock. |
66 | 0 | DomTreeNode *getRootNode() { |
67 | 0 | return DT.getRootNode(); |
68 | 0 | } |
69 | | |
70 | | /// Compares two dominator trees. |
71 | | /// \returns false if the other dominator tree matches this dominator tree, |
72 | | /// false otherwise. |
73 | | bool compare(CFGDominatorTreeImpl &Other) const { |
74 | | DomTreeNode *R = getRootNode(); |
75 | | DomTreeNode *OtherR = Other.getRootNode(); |
76 | | |
77 | | if (!R || !OtherR || R->getBlock() != OtherR->getBlock()) |
78 | | return true; |
79 | | |
80 | | if (DT.compare(Other.getBase())) |
81 | | return true; |
82 | | |
83 | | return false; |
84 | | } |
85 | | |
86 | | /// Builds the dominator tree for a given CFG. |
87 | 5.14k | void buildDominatorTree(CFG *cfg) { |
88 | 5.14k | assert(cfg); |
89 | 0 | this->cfg = cfg; |
90 | 5.14k | DT.recalculate(*cfg); |
91 | 5.14k | } clang::CFGDominatorTreeImpl<false>::buildDominatorTree(clang::CFG*) Line | Count | Source | 87 | 10 | void buildDominatorTree(CFG *cfg) { | 88 | 10 | assert(cfg); | 89 | 0 | this->cfg = cfg; | 90 | 10 | DT.recalculate(*cfg); | 91 | 10 | } |
clang::CFGDominatorTreeImpl<true>::buildDominatorTree(clang::CFG*) Line | Count | Source | 87 | 5.13k | void buildDominatorTree(CFG *cfg) { | 88 | 5.13k | assert(cfg); | 89 | 0 | this->cfg = cfg; | 90 | 5.13k | DT.recalculate(*cfg); | 91 | 5.13k | } |
|
92 | | |
93 | | /// Dumps immediate dominators for each block. |
94 | 18 | void dump() { |
95 | 18 | llvm::errs() << "Immediate " << (IsPostDom ? "post "9 : ""9 ) |
96 | 18 | << "dominance tree (Node#,IDom#):\n"; |
97 | 18 | for (CFG::const_iterator I = cfg->begin(), |
98 | 154 | E = cfg->end(); I != E; ++I136 ) { |
99 | | |
100 | 136 | assert(*I && |
101 | 136 | "LLVM's Dominator tree builder uses nullpointers to signify the " |
102 | 136 | "virtual root!"); |
103 | | |
104 | 0 | DomTreeNode *IDom = DT.getNode(*I)->getIDom(); |
105 | 136 | if (IDom && IDom->getBlock()127 ) |
106 | 118 | llvm::errs() << "(" << (*I)->getBlockID() |
107 | 118 | << "," |
108 | 118 | << IDom->getBlock()->getBlockID() |
109 | 118 | << ")\n"; |
110 | 18 | else { |
111 | 18 | bool IsEntryBlock = *I == &(*I)->getParent()->getEntry(); |
112 | 18 | bool IsExitBlock = *I == &(*I)->getParent()->getExit(); |
113 | | |
114 | 18 | bool IsDomTreeRoot = !IDom && !IsPostDom9 && IsEntryBlock9 ; |
115 | 18 | bool IsPostDomTreeRoot = |
116 | 18 | IDom && !IDom->getBlock()9 && IsPostDom0 && IsExitBlock9 ; |
117 | | |
118 | 18 | assert((IsDomTreeRoot || IsPostDomTreeRoot) && |
119 | 18 | "If the immediate dominator node is nullptr, the CFG block " |
120 | 18 | "should be the exit point (since it's the root of the dominator " |
121 | 18 | "tree), or if the CFG block it refers to is a nullpointer, it " |
122 | 18 | "must be the entry block (since it's the root of the post " |
123 | 18 | "dominator tree)"); |
124 | | |
125 | 0 | (void)IsDomTreeRoot; |
126 | 18 | (void)IsPostDomTreeRoot; |
127 | | |
128 | 18 | llvm::errs() << "(" << (*I)->getBlockID() |
129 | 18 | << "," << (*I)->getBlockID() << ")\n"; |
130 | 18 | } |
131 | 136 | } |
132 | 18 | } clang::CFGDominatorTreeImpl<false>::dump() Line | Count | Source | 94 | 9 | void dump() { | 95 | 9 | llvm::errs() << "Immediate " << (IsPostDom ? "post "0 : "") | 96 | 9 | << "dominance tree (Node#,IDom#):\n"; | 97 | 9 | for (CFG::const_iterator I = cfg->begin(), | 98 | 77 | E = cfg->end(); I != E; ++I68 ) { | 99 | | | 100 | 68 | assert(*I && | 101 | 68 | "LLVM's Dominator tree builder uses nullpointers to signify the " | 102 | 68 | "virtual root!"); | 103 | | | 104 | 0 | DomTreeNode *IDom = DT.getNode(*I)->getIDom(); | 105 | 68 | if (IDom && IDom->getBlock()59 ) | 106 | 59 | llvm::errs() << "(" << (*I)->getBlockID() | 107 | 59 | << "," | 108 | 59 | << IDom->getBlock()->getBlockID() | 109 | 59 | << ")\n"; | 110 | 9 | else { | 111 | 9 | bool IsEntryBlock = *I == &(*I)->getParent()->getEntry(); | 112 | 9 | bool IsExitBlock = *I == &(*I)->getParent()->getExit(); | 113 | | | 114 | 9 | bool IsDomTreeRoot = !IDom && !IsPostDom && IsEntryBlock; | 115 | 9 | bool IsPostDomTreeRoot = | 116 | 9 | IDom && !IDom->getBlock()0 && IsPostDom0 && IsExitBlock0 ; | 117 | | | 118 | 9 | assert((IsDomTreeRoot || IsPostDomTreeRoot) && | 119 | 9 | "If the immediate dominator node is nullptr, the CFG block " | 120 | 9 | "should be the exit point (since it's the root of the dominator " | 121 | 9 | "tree), or if the CFG block it refers to is a nullpointer, it " | 122 | 9 | "must be the entry block (since it's the root of the post " | 123 | 9 | "dominator tree)"); | 124 | | | 125 | 0 | (void)IsDomTreeRoot; | 126 | 9 | (void)IsPostDomTreeRoot; | 127 | | | 128 | 9 | llvm::errs() << "(" << (*I)->getBlockID() | 129 | 9 | << "," << (*I)->getBlockID() << ")\n"; | 130 | 9 | } | 131 | 68 | } | 132 | 9 | } |
clang::CFGDominatorTreeImpl<true>::dump() Line | Count | Source | 94 | 9 | void dump() { | 95 | 9 | llvm::errs() << "Immediate " << (IsPostDom ? "post " : ""0 ) | 96 | 9 | << "dominance tree (Node#,IDom#):\n"; | 97 | 9 | for (CFG::const_iterator I = cfg->begin(), | 98 | 77 | E = cfg->end(); I != E; ++I68 ) { | 99 | | | 100 | 68 | assert(*I && | 101 | 68 | "LLVM's Dominator tree builder uses nullpointers to signify the " | 102 | 68 | "virtual root!"); | 103 | | | 104 | 0 | DomTreeNode *IDom = DT.getNode(*I)->getIDom(); | 105 | 68 | if (IDom && IDom->getBlock()) | 106 | 59 | llvm::errs() << "(" << (*I)->getBlockID() | 107 | 59 | << "," | 108 | 59 | << IDom->getBlock()->getBlockID() | 109 | 59 | << ")\n"; | 110 | 9 | else { | 111 | 9 | bool IsEntryBlock = *I == &(*I)->getParent()->getEntry(); | 112 | 9 | bool IsExitBlock = *I == &(*I)->getParent()->getExit(); | 113 | | | 114 | 9 | bool IsDomTreeRoot = !IDom && !IsPostDom0 && IsEntryBlock0 ; | 115 | 9 | bool IsPostDomTreeRoot = | 116 | 9 | IDom && !IDom->getBlock() && IsPostDom0 && IsExitBlock; | 117 | | | 118 | 9 | assert((IsDomTreeRoot || IsPostDomTreeRoot) && | 119 | 9 | "If the immediate dominator node is nullptr, the CFG block " | 120 | 9 | "should be the exit point (since it's the root of the dominator " | 121 | 9 | "tree), or if the CFG block it refers to is a nullpointer, it " | 122 | 9 | "must be the entry block (since it's the root of the post " | 123 | 9 | "dominator tree)"); | 124 | | | 125 | 0 | (void)IsDomTreeRoot; | 126 | 9 | (void)IsPostDomTreeRoot; | 127 | | | 128 | 9 | llvm::errs() << "(" << (*I)->getBlockID() | 129 | 9 | << "," << (*I)->getBlockID() << ")\n"; | 130 | 9 | } | 131 | 68 | } | 132 | 9 | } |
|
133 | | |
134 | | /// Tests whether \p A dominates \p B. |
135 | | /// Note a block always dominates itself. |
136 | | bool dominates(const CFGBlock *A, const CFGBlock *B) const { |
137 | | return DT.dominates(A, B); |
138 | | } |
139 | | |
140 | | /// Tests whether \p A properly dominates \p B. |
141 | | /// \returns false if \p A is the same block as \p B, otherwise whether A |
142 | | /// dominates B. |
143 | | bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const { |
144 | | return DT.properlyDominates(A, B); |
145 | | } |
146 | | |
147 | | /// \returns the nearest common dominator CFG block for CFG block \p A and \p |
148 | | /// B. If there is no such block then return NULL. |
149 | | CFGBlock *findNearestCommonDominator(CFGBlock *A, CFGBlock *B) { |
150 | | return DT.findNearestCommonDominator(A, B); |
151 | | } |
152 | | |
153 | | const CFGBlock *findNearestCommonDominator(const CFGBlock *A, |
154 | | const CFGBlock *B) { |
155 | | return DT.findNearestCommonDominator(A, B); |
156 | | } |
157 | | |
158 | | /// Update the dominator tree information when a node's immediate dominator |
159 | | /// changes. |
160 | | void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom) { |
161 | | DT.changeImmediateDominator(N, NewIDom); |
162 | | } |
163 | | |
164 | | /// Tests whether \p A is reachable from the entry block. |
165 | | bool isReachableFromEntry(const CFGBlock *A) { |
166 | | return DT.isReachableFromEntry(A); |
167 | | } |
168 | | |
169 | | /// Releases the memory held by the dominator tree. |
170 | 0 | virtual void releaseMemory() { DT.reset(); } Unexecuted instantiation: clang::CFGDominatorTreeImpl<false>::releaseMemory() Unexecuted instantiation: clang::CFGDominatorTreeImpl<true>::releaseMemory() |
171 | | |
172 | | /// Converts the dominator tree to human readable form. |
173 | 0 | virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const { |
174 | 0 | DT.print(OS); |
175 | 0 | } Unexecuted instantiation: clang::CFGDominatorTreeImpl<false>::print(llvm::raw_ostream&, llvm::Module const*) const Unexecuted instantiation: clang::CFGDominatorTreeImpl<true>::print(llvm::raw_ostream&, llvm::Module const*) const |
176 | | |
177 | | private: |
178 | | CFG *cfg; |
179 | | DominatorTreeBase DT; |
180 | | }; |
181 | | |
182 | | using CFGDomTree = CFGDominatorTreeImpl</*IsPostDom*/ false>; |
183 | | using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>; |
184 | | |
185 | | template<> void CFGDominatorTreeImpl<true>::anchor(); |
186 | | template<> void CFGDominatorTreeImpl<false>::anchor(); |
187 | | |
188 | | } // end of namespace clang |
189 | | |
190 | | namespace llvm { |
191 | | namespace IDFCalculatorDetail { |
192 | | |
193 | | /// Specialize ChildrenGetterTy to skip nullpointer successors. |
194 | | template <bool IsPostDom> |
195 | | struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> { |
196 | | using NodeRef = typename GraphTraits<clang::CFGBlock *>::NodeRef; |
197 | | using ChildrenTy = SmallVector<NodeRef, 8>; |
198 | | |
199 | 16.1k | ChildrenTy get(const NodeRef &N) { |
200 | 16.1k | using OrderedNodeTy = |
201 | 16.1k | typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy; |
202 | | |
203 | 16.1k | auto Children = children<OrderedNodeTy>(N); |
204 | 16.1k | ChildrenTy Ret{Children.begin(), Children.end()}; |
205 | 16.1k | llvm::erase_value(Ret, nullptr); |
206 | 16.1k | return Ret; |
207 | 16.1k | } |
208 | | }; |
209 | | |
210 | | } // end of namespace IDFCalculatorDetail |
211 | | } // end of namespace llvm |
212 | | |
213 | | namespace clang { |
214 | | |
215 | | class ControlDependencyCalculator : public ManagedAnalysis { |
216 | | using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>; |
217 | | using CFGBlockVector = llvm::SmallVector<CFGBlock *, 4>; |
218 | | using CFGBlockSet = llvm::SmallPtrSet<CFGBlock *, 4>; |
219 | | |
220 | | CFGPostDomTree PostDomTree; |
221 | | IDFCalculator IDFCalc; |
222 | | |
223 | | llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap; |
224 | | |
225 | | public: |
226 | | ControlDependencyCalculator(CFG *cfg) |
227 | 5.12k | : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {} |
228 | | |
229 | 0 | const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; } |
230 | | |
231 | | // Lazily retrieves the set of control dependencies to \p A. |
232 | 9.49k | const CFGBlockVector &getControlDependencies(CFGBlock *A) { |
233 | 9.49k | auto It = ControlDepenencyMap.find(A); |
234 | 9.49k | if (It == ControlDepenencyMap.end()) { |
235 | 5.03k | CFGBlockSet DefiningBlock = {A}; |
236 | 5.03k | IDFCalc.setDefiningBlocks(DefiningBlock); |
237 | | |
238 | 5.03k | CFGBlockVector ControlDependencies; |
239 | 5.03k | IDFCalc.calculate(ControlDependencies); |
240 | | |
241 | 5.03k | It = ControlDepenencyMap.insert({A, ControlDependencies}).first; |
242 | 5.03k | } |
243 | | |
244 | 9.49k | assert(It != ControlDepenencyMap.end()); |
245 | 0 | return It->second; |
246 | 9.49k | } |
247 | | |
248 | | /// Whether \p A is control dependent on \p B. |
249 | 9.42k | bool isControlDependent(CFGBlock *A, CFGBlock *B) { |
250 | 9.42k | return llvm::is_contained(getControlDependencies(A), B); |
251 | 9.42k | } |
252 | | |
253 | | // Dumps immediate control dependencies for each block. |
254 | 9 | LLVM_DUMP_METHOD void dump() { |
255 | 9 | CFG *cfg = PostDomTree.getCFG(); |
256 | 9 | llvm::errs() << "Control dependencies (Node#,Dependency#):\n"; |
257 | 68 | for (CFGBlock *BB : *cfg) { |
258 | | |
259 | 68 | assert(BB && |
260 | 68 | "LLVM's Dominator tree builder uses nullpointers to signify the " |
261 | 68 | "virtual root!"); |
262 | | |
263 | 0 | for (CFGBlock *isControlDependency : getControlDependencies(BB)) |
264 | 68 | llvm::errs() << "(" << BB->getBlockID() |
265 | 68 | << "," |
266 | 68 | << isControlDependency->getBlockID() |
267 | 68 | << ")\n"; |
268 | 68 | } |
269 | 9 | } |
270 | | }; |
271 | | |
272 | | } // namespace clang |
273 | | |
274 | | namespace llvm { |
275 | | |
276 | | //===------------------------------------- |
277 | | /// DominatorTree GraphTraits specialization so the DominatorTree can be |
278 | | /// iterable by generic graph iterators. |
279 | | /// |
280 | | template <> struct GraphTraits<clang::DomTreeNode *> { |
281 | | using NodeRef = ::clang::DomTreeNode *; |
282 | | using ChildIteratorType = ::clang::DomTreeNode::const_iterator; |
283 | | |
284 | 0 | static NodeRef getEntryNode(NodeRef N) { return N; } |
285 | 0 | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
286 | 0 | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
287 | | |
288 | | using nodes_iterator = |
289 | | llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>; |
290 | | |
291 | 0 | static nodes_iterator nodes_begin(::clang::DomTreeNode *N) { |
292 | 0 | return nodes_iterator(df_begin(getEntryNode(N))); |
293 | 0 | } |
294 | | |
295 | 0 | static nodes_iterator nodes_end(::clang::DomTreeNode *N) { |
296 | 0 | return nodes_iterator(df_end(getEntryNode(N))); |
297 | 0 | } |
298 | | }; |
299 | | |
300 | | template <> struct GraphTraits<clang::CFGDomTree *> |
301 | | : public GraphTraits<clang::DomTreeNode *> { |
302 | 0 | static NodeRef getEntryNode(clang::CFGDomTree *DT) { |
303 | 0 | return DT->getRootNode(); |
304 | 0 | } |
305 | | |
306 | 0 | static nodes_iterator nodes_begin(clang::CFGDomTree *N) { |
307 | 0 | return nodes_iterator(df_begin(getEntryNode(N))); |
308 | 0 | } |
309 | | |
310 | 0 | static nodes_iterator nodes_end(clang::CFGDomTree *N) { |
311 | 0 | return nodes_iterator(df_end(getEntryNode(N))); |
312 | 0 | } |
313 | | }; |
314 | | |
315 | | } // namespace llvm |
316 | | |
317 | | #endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H |