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 | CFGDominatorTreeImpl() = default; |
49 | |
50 | CFGDominatorTreeImpl(CFG *cfg) { |
51 | buildDominatorTree(cfg); |
52 | } |
53 | |
54 | ~CFGDominatorTreeImpl() override = default; |
55 | |
56 | DominatorTreeBase &getBase() { return DT; } |
57 | |
58 | 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 | DomTreeNode *getRootNode() { |
67 | return DT.getRootNode(); |
68 | } |
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 | void buildDominatorTree(CFG *cfg) { |
88 | assert(cfg); |
89 | this->cfg = cfg; |
90 | DT.recalculate(*cfg); |
91 | } |
92 | |
93 | /// Dumps immediate dominators for each block. |
94 | void dump() { |
95 | llvm::errs() << "Immediate " << (IsPostDom ? "post " : "" ) |
96 | << "dominance tree (Node#,IDom#):\n" ; |
97 | for (CFG::const_iterator I = cfg->begin(), |
98 | E = cfg->end(); I != E; ++I) { |
99 | |
100 | assert(*I && |
101 | "LLVM's Dominator tree builder uses nullpointers to signify the " |
102 | "virtual root!" ); |
103 | |
104 | DomTreeNode *IDom = DT.getNode(*I)->getIDom(); |
105 | if (IDom && IDom->getBlock()) |
106 | llvm::errs() << "(" << (*I)->getBlockID() |
107 | << "," |
108 | << IDom->getBlock()->getBlockID() |
109 | << ")\n" ; |
110 | else { |
111 | bool IsEntryBlock = *I == &(*I)->getParent()->getEntry(); |
112 | bool IsExitBlock = *I == &(*I)->getParent()->getExit(); |
113 | |
114 | bool IsDomTreeRoot = !IDom && !IsPostDom && IsEntryBlock; |
115 | bool IsPostDomTreeRoot = |
116 | IDom && !IDom->getBlock() && IsPostDom && IsExitBlock; |
117 | |
118 | assert((IsDomTreeRoot || IsPostDomTreeRoot) && |
119 | "If the immediate dominator node is nullptr, the CFG block " |
120 | "should be the exit point (since it's the root of the dominator " |
121 | "tree), or if the CFG block it refers to is a nullpointer, it " |
122 | "must be the entry block (since it's the root of the post " |
123 | "dominator tree)" ); |
124 | |
125 | (void)IsDomTreeRoot; |
126 | (void)IsPostDomTreeRoot; |
127 | |
128 | llvm::errs() << "(" << (*I)->getBlockID() |
129 | << "," << (*I)->getBlockID() << ")\n" ; |
130 | } |
131 | } |
132 | } |
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 | virtual void releaseMemory() { DT.reset(); } |
171 | |
172 | /// Converts the dominator tree to human readable form. |
173 | virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const { |
174 | DT.print(OS); |
175 | } |
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 | ChildrenTy get(const NodeRef &N) { |
200 | using OrderedNodeTy = |
201 | typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy; |
202 | |
203 | auto Children = children<OrderedNodeTy>(N); |
204 | ChildrenTy Ret{Children.begin(), Children.end()}; |
205 | llvm::erase(C&: Ret, V: nullptr); |
206 | return Ret; |
207 | } |
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 | : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {} |
228 | |
229 | const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; } |
230 | |
231 | // Lazily retrieves the set of control dependencies to \p A. |
232 | const CFGBlockVector &getControlDependencies(CFGBlock *A) { |
233 | auto It = ControlDepenencyMap.find(Val: A); |
234 | if (It == ControlDepenencyMap.end()) { |
235 | CFGBlockSet DefiningBlock = {A}; |
236 | IDFCalc.setDefiningBlocks(DefiningBlock); |
237 | |
238 | CFGBlockVector ControlDependencies; |
239 | IDFCalc.calculate(IDFBlocks&: ControlDependencies); |
240 | |
241 | It = ControlDepenencyMap.insert(KV: {A, ControlDependencies}).first; |
242 | } |
243 | |
244 | assert(It != ControlDepenencyMap.end()); |
245 | return It->second; |
246 | } |
247 | |
248 | /// Whether \p A is control dependent on \p B. |
249 | bool isControlDependent(CFGBlock *A, CFGBlock *B) { |
250 | return llvm::is_contained(Range: getControlDependencies(A), Element: B); |
251 | } |
252 | |
253 | // Dumps immediate control dependencies for each block. |
254 | LLVM_DUMP_METHOD void dump() { |
255 | CFG *cfg = PostDomTree.getCFG(); |
256 | llvm::errs() << "Control dependencies (Node#,Dependency#):\n" ; |
257 | for (CFGBlock *BB : *cfg) { |
258 | |
259 | assert(BB && |
260 | "LLVM's Dominator tree builder uses nullpointers to signify the " |
261 | "virtual root!" ); |
262 | |
263 | for (CFGBlock *isControlDependency : getControlDependencies(A: BB)) |
264 | llvm::errs() << "(" << BB->getBlockID() |
265 | << "," |
266 | << isControlDependency->getBlockID() |
267 | << ")\n" ; |
268 | } |
269 | } |
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 | static NodeRef getEntryNode(NodeRef N) { return N; } |
285 | static ChildIteratorType child_begin(NodeRef N) { return N->begin(); } |
286 | static ChildIteratorType child_end(NodeRef N) { return N->end(); } |
287 | |
288 | using nodes_iterator = |
289 | llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>; |
290 | |
291 | static nodes_iterator nodes_begin(::clang::DomTreeNode *N) { |
292 | return nodes_iterator(df_begin(G: getEntryNode(N))); |
293 | } |
294 | |
295 | static nodes_iterator nodes_end(::clang::DomTreeNode *N) { |
296 | return nodes_iterator(df_end(G: getEntryNode(N))); |
297 | } |
298 | }; |
299 | |
300 | template <> struct GraphTraits<clang::CFGDomTree *> |
301 | : public GraphTraits<clang::DomTreeNode *> { |
302 | static NodeRef getEntryNode(clang::CFGDomTree *DT) { |
303 | return DT->getRootNode(); |
304 | } |
305 | |
306 | static nodes_iterator nodes_begin(clang::CFGDomTree *N) { |
307 | return nodes_iterator(df_begin(G: getEntryNode(DT: N))); |
308 | } |
309 | |
310 | static nodes_iterator nodes_end(clang::CFGDomTree *N) { |
311 | return nodes_iterator(df_end(G: getEntryNode(DT: N))); |
312 | } |
313 | }; |
314 | |
315 | } // namespace llvm |
316 | |
317 | #endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H |
318 | |