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 //===-------------------------------------
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(getEntryNode(N)));
293   }
294 
295   static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
296     return nodes_iterator(df_end(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(getEntryNode(N)));
308   }
309 
310   static nodes_iterator nodes_end(clang::CFGDomTree *N) {
311     return nodes_iterator(df_end(getEntryNode(N)));
312   }
313 };
314 
315 } // namespace llvm
316 
317 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H
318