clang 19.0.0git
Dominators.h
Go to the documentation of this file.
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
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
30namespace llvm {
31
32class Module;
33
34} // namespace llvm
35
36namespace clang {
37
38using DomTreeNode = llvm::DomTreeNodeBase<CFGBlock>;
39
40/// Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase.
41template <bool IsPostDom>
43 virtual void anchor();
44
45public:
46 using DominatorTreeBase = llvm::DominatorTreeBase<CFGBlock, IsPostDom>;
47
49
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.
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.
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.
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.
150 return DT.findNearestCommonDominator(A, B);
151 }
152
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.
161 DT.changeImmediateDominator(N, NewIDom);
162 }
163
164 /// Tests whether \p A is reachable from the entry block.
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
177private:
178 CFG *cfg;
180};
181
182using CFGDomTree = CFGDominatorTreeImpl</*IsPostDom*/ false>;
183using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>;
184
185template<> void CFGDominatorTreeImpl<true>::anchor();
187
188} // end of namespace clang
189
190namespace llvm {
191namespace IDFCalculatorDetail {
192
193/// Specialize ChildrenGetterTy to skip nullpointer successors.
194template <bool IsPostDom>
195struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> {
196 using NodeRef = typename GraphTraits<clang::CFGBlock *>::NodeRef;
198
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(Ret, nullptr);
206 return Ret;
207 }
208};
209
210} // end of namespace IDFCalculatorDetail
211} // end of namespace llvm
212
213namespace clang {
214
216 using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>;
219
220 CFGPostDomTree PostDomTree;
221 IDFCalculator IDFCalc;
222
223 llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;
224
225public:
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.
233 auto It = ControlDepenencyMap.find(A);
234 if (It == ControlDepenencyMap.end()) {
235 CFGBlockSet DefiningBlock = {A};
236 IDFCalc.setDefiningBlocks(DefiningBlock);
237
238 CFGBlockVector ControlDependencies;
239 IDFCalc.calculate(ControlDependencies);
240
241 It = ControlDepenencyMap.insert({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.
250 return llvm::is_contained(getControlDependencies(A), 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(BB))
264 llvm::errs() << "(" << BB->getBlockID()
265 << ","
266 << isControlDependency->getBlockID()
267 << ")\n";
268 }
269 }
270};
271
272} // namespace clang
273
274namespace llvm {
275
276//===-------------------------------------
277/// DominatorTree GraphTraits specialization so the DominatorTree can be
278/// iterable by generic graph iterators.
279///
280template <> struct GraphTraits<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
289 llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
290
292 return nodes_iterator(df_begin(getEntryNode(N)));
293 }
294
296 return nodes_iterator(df_end(getEntryNode(N)));
297 }
298};
299
300template <> struct GraphTraits<clang::CFGDomTree *>
301 : public GraphTraits<clang::DomTreeNode *> {
303 return DT->getRootNode();
304 }
305
307 return nodes_iterator(df_begin(getEntryNode(N)));
308 }
309
311 return nodes_iterator(df_end(getEntryNode(N)));
312 }
313};
314
315} // namespace llvm
316
317#endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
This file defines AnalysisDeclContext, a class that manages the analysis context data for context sen...
Represents a single basic block in a source-level CFG.
Definition: CFG.h:604
Dominator tree builder for Clang's CFG based on llvm::DominatorTreeBase.
Definition: Dominators.h:42
virtual void releaseMemory()
Releases the memory held by the dominator tree.
Definition: Dominators.h:170
virtual void print(raw_ostream &OS, const llvm::Module *M=nullptr) const
Converts the dominator tree to human readable form.
Definition: Dominators.h:173
CFGBlock * findNearestCommonDominator(CFGBlock *A, CFGBlock *B)
Definition: Dominators.h:149
bool compare(CFGDominatorTreeImpl &Other) const
Compares two dominator trees.
Definition: Dominators.h:73
CFGBlock * getRoot() const
Definition: Dominators.h:61
void dump()
Dumps immediate dominators for each block.
Definition: Dominators.h:94
void buildDominatorTree(CFG *cfg)
Builds the dominator tree for a given CFG.
Definition: Dominators.h:87
~CFGDominatorTreeImpl() override=default
llvm::DominatorTreeBase< CFGBlock, IsPostDom > DominatorTreeBase
Definition: Dominators.h:46
const CFGBlock * findNearestCommonDominator(const CFGBlock *A, const CFGBlock *B)
Definition: Dominators.h:153
bool properlyDominates(const CFGBlock *A, const CFGBlock *B) const
Tests whether A properly dominates B.
Definition: Dominators.h:143
DomTreeNode * getRootNode()
Definition: Dominators.h:66
void changeImmediateDominator(CFGBlock *N, CFGBlock *NewIDom)
Update the dominator tree information when a node's immediate dominator changes.
Definition: Dominators.h:160
DominatorTreeBase & getBase()
Definition: Dominators.h:56
bool dominates(const CFGBlock *A, const CFGBlock *B) const
Tests whether A dominates B.
Definition: Dominators.h:136
bool isReachableFromEntry(const CFGBlock *A)
Tests whether A is reachable from the entry block.
Definition: Dominators.h:165
Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt.
Definition: CFG.h:1214
iterator end()
Definition: CFG.h:1295
iterator begin()
Definition: CFG.h:1294
LLVM_DUMP_METHOD void dump()
Definition: Dominators.h:254
const CFGBlockVector & getControlDependencies(CFGBlock *A)
Definition: Dominators.h:232
const CFGPostDomTree & getCFGPostDomTree() const
Definition: Dominators.h:229
bool isControlDependent(CFGBlock *A, CFGBlock *B)
Whether A is control dependent on B.
Definition: Dominators.h:249
The base class of a hierarchy of objects representing analyses tied to AnalysisDeclContext.
The JSON file list parser is used to communicate input to InstallAPI.
llvm::DomTreeNodeBase< CFGBlock > DomTreeNode
Definition: Dominators.h:38
@ Other
Other implicit parameter.
YAML serialization mapping.
Definition: Dominators.h:30
static nodes_iterator nodes_end(clang::CFGDomTree *N)
Definition: Dominators.h:310
static nodes_iterator nodes_begin(clang::CFGDomTree *N)
Definition: Dominators.h:306
static NodeRef getEntryNode(clang::CFGDomTree *DT)
Definition: Dominators.h:302
static NodeRef getEntryNode(NodeRef N)
Definition: Dominators.h:284
::clang::DomTreeNode::const_iterator ChildIteratorType
Definition: Dominators.h:282
static ChildIteratorType child_end(NodeRef N)
Definition: Dominators.h:286
static nodes_iterator nodes_begin(::clang::DomTreeNode *N)
Definition: Dominators.h:291
static ChildIteratorType child_begin(NodeRef N)
Definition: Dominators.h:285
llvm::pointer_iterator< df_iterator<::clang::DomTreeNode * > > nodes_iterator
Definition: Dominators.h:289
static nodes_iterator nodes_end(::clang::DomTreeNode *N)
Definition: Dominators.h:295
typename GraphTraits< clang::CFGBlock * >::NodeRef NodeRef
Definition: Dominators.h:196