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