contrib/llvm-project/clang/include/clang/Analysis/Analyses/Dominators.h

   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() {
 171     DT.releaseMemory();
 172   }
 173
 174   /// Converts the dominator tree to human readable form.
 175   virtual void print(raw_ostream &OS, const llvm::Module* M= nullptr) const {
 176     DT.print(OS);
 177   }
 178
 179 private:
 180   CFG *cfg;
 181   DominatorTreeBase DT;
 182 };
 183
 184 using CFGDomTree = CFGDominatorTreeImpl</*IsPostDom*/ false>;
 185 using CFGPostDomTree = CFGDominatorTreeImpl</*IsPostDom*/ true>;
 186
 187 template<> void CFGDominatorTreeImpl<true>::anchor();
 188 template<> void CFGDominatorTreeImpl<false>::anchor();
 189
 190 } // end of namespace clang
 191
 192 namespace llvm {
 193 namespace IDFCalculatorDetail {
 194
 195 /// Specialize ChildrenGetterTy to skip nullpointer successors.
 196 template <bool IsPostDom>
 197 struct ChildrenGetterTy<clang::CFGBlock, IsPostDom> {
 198   using NodeRef = typename GraphTraits<clang::CFGBlock>::NodeRef;
 199   using ChildrenTy = SmallVector<NodeRef, 8>;
 200
 201   ChildrenTy get(const NodeRef &N) {
 202     using OrderedNodeTy =
 203         typename IDFCalculatorBase<clang::CFGBlock, IsPostDom>::OrderedNodeTy;
 204
 205     auto Children = children<OrderedNodeTy>(N);
 206     ChildrenTy Ret{Children.begin(), Children.end()};
 207     Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
 208     return Ret;
 209   }
 210 };
 211
 212 } // end of namespace IDFCalculatorDetail
 213 } // end of namespace llvm
 214
 215 namespace clang {
 216
 217 class ControlDependencyCalculator : public ManagedAnalysis {
 218   using IDFCalculator = llvm::IDFCalculatorBase<CFGBlock, /*IsPostDom=*/true>;
 219   using CFGBlockVector = llvm::SmallVector<CFGBlock *, 4>;
 220   using CFGBlockSet = llvm::SmallPtrSet<CFGBlock *, 4>;
 221
 222   CFGPostDomTree PostDomTree;
 223   IDFCalculator IDFCalc;
 224
 225   llvm::DenseMap<CFGBlock *, CFGBlockVector> ControlDepenencyMap;
 226
 227 public:
 228   ControlDependencyCalculator(CFG *cfg)
 229     : PostDomTree(cfg), IDFCalc(PostDomTree.getBase()) {}
 230
 231   const CFGPostDomTree &getCFGPostDomTree() const { return PostDomTree; }
 232
 233   // Lazily retrieves the set of control dependencies to \p A.
 234   const CFGBlockVector &getControlDependencies(CFGBlock *A) {
 235     auto It = ControlDepenencyMap.find(A);
 236     if (It == ControlDepenencyMap.end()) {
 237       CFGBlockSet DefiningBlock = {A};
 238       IDFCalc.setDefiningBlocks(DefiningBlock);
 239
 240       CFGBlockVector ControlDependencies;
 241       IDFCalc.calculate(ControlDependencies);
 242
 243       It = ControlDepenencyMap.insert({A, ControlDependencies}).first;
 244     }
 245
 246     assert(It != ControlDepenencyMap.end());
 247     return It->second;
 248   }
 249
 250   /// Whether \p A is control dependent on \p B.
 251   bool isControlDependent(CFGBlock *A, CFGBlock *B) {
 252     return llvm::is_contained(getControlDependencies(A), B);
 253   }
 254
 255   // Dumps immediate control dependencies for each block.
 256   LLVM_DUMP_METHOD void dump() {
 257     CFG *cfg = PostDomTree.getCFG();
 258     llvm::errs() << "Control dependencies (Node#,Dependency#):\n";
 259     for (CFGBlock *BB : *cfg) {
 260
 261       assert(BB &&
 262              "LLVM's Dominator tree builder uses nullpointers to signify the "
 263              "virtual root!");
 264
 265       for (CFGBlock *isControlDependency : getControlDependencies(BB))
 266         llvm::errs() << "(" << BB->getBlockID()
 267                      << ","
 268                      << isControlDependency->getBlockID()
 269                      << ")\n";
 270     }
 271   }
 272 };
 273
 274 } // namespace clang
 275
 276 namespace llvm {
 277
 278 /// Clang's CFG contains nullpointers for unreachable succesors, e.g. when an
 279 /// if statement's condition is always false, it's 'then' branch is represented
 280 /// with a nullptr. This however will result in a nullpointer derefernece for
 281 /// dominator tree calculation.
 282 ///
 283 /// To circumvent this, let's just crudely specialize the children getters
 284 /// used in LLVM's dominator tree builder.
 285 namespace DomTreeBuilder {
 286
 287 using ClangCFGDomChildrenGetter =
 288 SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
 289                                                              /*Inverse=*/false>;
 290
 291 template <>
 292 template <>
 293 inline ClangCFGDomChildrenGetter::ResultTy ClangCFGDomChildrenGetter::Get(
 294     clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
 295   auto RChildren = reverse(children<NodePtr>(N));
 296   ResultTy Ret(RChildren.begin(), RChildren.end());
 297   Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
 298   return Ret;
 299 }
 300
 301 using ClangCFGDomReverseChildrenGetter =
 302 SemiNCAInfo<clang::CFGDomTree::DominatorTreeBase>::ChildrenGetter<
 303                                                               /*Inverse=*/true>;
 304
 305 template <>
 306 template <>
 307 inline ClangCFGDomReverseChildrenGetter::ResultTy
 308 ClangCFGDomReverseChildrenGetter::Get(
 309     clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
 310   auto IChildren = inverse_children<NodePtr>(N);
 311   ResultTy Ret(IChildren.begin(), IChildren.end());
 312   Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
 313   return Ret;
 314 }
 315
 316 using ClangCFGPostDomChildrenGetter =
 317 SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
 318                                                              /*Inverse=*/false>;
 319
 320 template <>
 321 template <>
 322 inline ClangCFGPostDomChildrenGetter::ResultTy
 323 ClangCFGPostDomChildrenGetter::Get(
 324     clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/false>) {
 325   auto RChildren = reverse(children<NodePtr>(N));
 326   ResultTy Ret(RChildren.begin(), RChildren.end());
 327   Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
 328   return Ret;
 329 }
 330
 331 using ClangCFGPostDomReverseChildrenGetter =
 332 SemiNCAInfo<clang::CFGPostDomTree::DominatorTreeBase>::ChildrenGetter<
 333                                                               /*Inverse=*/true>;
 334
 335 template <>
 336 template <>
 337 inline ClangCFGPostDomReverseChildrenGetter::ResultTy
 338 ClangCFGPostDomReverseChildrenGetter::Get(
 339     clang::CFGBlock *N, std::integral_constant<bool, /*Inverse=*/true>) {
 340   auto IChildren = inverse_children<NodePtr>(N);
 341   ResultTy Ret(IChildren.begin(), IChildren.end());
 342   Ret.erase(std::remove(Ret.begin(), Ret.end(), nullptr), Ret.end());
 343   return Ret;
 344 }
 345
 346 } // end of namespace DomTreeBuilder
 347
 348 //===-------------------------------------
 349 /// DominatorTree GraphTraits specialization so the DominatorTree can be
 350 /// iterable by generic graph iterators.
 351 ///
 352 template <> struct GraphTraits<clang::DomTreeNode *> {
 353   using NodeRef = ::clang::DomTreeNode *;
 354   using ChildIteratorType = ::clang::DomTreeNode::iterator;
 355
 356   static NodeRef getEntryNode(NodeRef N) { return N; }
 357   static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
 358   static ChildIteratorType child_end(NodeRef N) { return N->end(); }
 359
 360   using nodes_iterator =
 361       llvm::pointer_iterator<df_iterator<::clang::DomTreeNode *>>;
 362
 363   static nodes_iterator nodes_begin(::clang::DomTreeNode *N) {
 364     return nodes_iterator(df_begin(getEntryNode(N)));
 365   }
 366
 367   static nodes_iterator nodes_end(::clang::DomTreeNode *N) {
 368     return nodes_iterator(df_end(getEntryNode(N)));
 369   }
 370 };
 371
 372 template <> struct GraphTraits<clang::CFGDomTree *>
 373     : public GraphTraits<clang::DomTreeNode *> {
 374   static NodeRef getEntryNode(clang::CFGDomTree *DT) {
 375     return DT->getRootNode();
 376   }
 377
 378   static nodes_iterator nodes_begin(clang::CFGDomTree *N) {
 379     return nodes_iterator(df_begin(getEntryNode(N)));
 380   }
 381
 382   static nodes_iterator nodes_end(clang::CFGDomTree *N) {
 383     return nodes_iterator(df_end(getEntryNode(N)));
 384   }
 385 };
 386
 387 } // namespace llvm
 388
 389 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_DOMINATORS_H