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     Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
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(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.
249   bool isControlDependent(CFGBlock *A, CFGBlock *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 
274 namespace llvm {
275 
276 /// Clang's CFG contains nullpointers for unreachable succesors, e.g. when an
277 /// if statement's condition is always false, it's 'then' branch is represented
278 /// with a nullptr. This however will result in a nullpointer derefernece for
279 /// dominator tree calculation.
280 ///
281 /// To circumvent this, let's just crudely specialize the children getters
282 /// used in LLVM's dominator tree builder.
283 namespace DomTreeBuilder {
284 
285 using ClangCFGDomChildrenGetter =
286 SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
287                                                              /*Inverse=*/false>;
288 
289 template <>
290 template <>
291 inline ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get(
292     clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
293   auto RChildren = reverse(children<NodePtr>(N));
294   ResultTy Ret(RChildren.begin(), RChildren.end());
295   Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
296   return Ret;
297 }
298 
299 using ClangCFGDomReverseChildrenGetter =
300 SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
301                                                               /*Inverse=*/true>;
302 
303 template <>
304 template <>
305 inline ClangCFGDomReverseChildrenGetter::ResultTy
306 ClangCFGDomReverseChildrenGetter::Get(
307     clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
308   auto IChildren = inverse_children<NodePtr>(N);
309   ResultTy Ret(IChildren.begin(), IChildren.end());
310   Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
311   return Ret;
312 }
313 
314 using ClangCFGPostDomChildrenGetter =
315 SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
316                                                              /*Inverse=*/false>;
317 
318 template <>
319 template <>
320 inline ClangCFGPostDomChildrenGetter::ResultTy
321 ClangCFGPostDomChildrenGetter::Get(
322     clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
323   auto RChildren = reverse(children<NodePtr>(N));
324   ResultTy Ret(RChildren.begin(), RChildren.end());
325   Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
326   return Ret;
327 }
328 
329 using ClangCFGPostDomReverseChildrenGetter =
330 SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
331                                                               /*Inverse=*/true>;
332 
333 template <>
334 template <>
335 inline ClangCFGPostDomReverseChildrenGetter::ResultTy
336 ClangCFGPostDomReverseChildrenGetter::Get(
337     clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
338   auto IChildren = inverse_children<NodePtr>(N);
339   ResultTy Ret(IChildren.begin(), IChildren.end());
340   Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
341   return Ret;
342 }
343 
344 } // end of namespace DomTreeBuilder
345 
346 //===-------------------------------------
347 /// DominatorTree GraphTraits specialization so the DominatorTree can be
348 /// iterable by generic graph iterators.
349 ///
350 template <> struct GraphTraits<clang::DomTreeNode *> {
351   using NodeRef = ::clang::DomTreeNode *;
352   using ChildIteratorType = ::clang::DomTreeNode::const_iterator;
353 
354   static NodeRef getEntryNode(NodeRef N) { return N; }
355   static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
356   static ChildIteratorType child_end(NodeRef N) { return N->end(); }
357 
358   using nodes_iterator =
359       llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
360 
361   static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
362     return nodes_iterator(df_begin(getEntryNode(N)));
363   }
364 
365   static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
366     return nodes_iterator(df_end(getEntryNode(N)));
367   }
368 };
369 
370 template <> struct GraphTraits<clang::CFGDomTree *>
371     : public GraphTraits<clang::DomTreeNode *> {
372   static NodeRef getEntryNode(clang::CFGDomTree *DT) {
373     return DT->getRootNode();
374   }
375 
376   static nodes_iterator nodes_begin(clang::CFGDomTree *N) {
377     return nodes_iterator(df_begin(getEntryNode(N)));
378   }
379 
380   static nodes_iterator nodes_end(clang::CFGDomTree *N) {
381     return nodes_iterator(df_end(getEntryNode(N)));
382   }
383 };
384 
385 } // namespace llvm
386 
387 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
388