contrib/llvm/include/llvm/Support/GenericDomTreeConstruction.h

   1 //===- GenericDomTreeConstruction.h - Dominator Calculation ------*- C++ -*-==//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 /// \file
  10 ///
  11 /// Generic dominator tree construction - This file provides routines to
  12 /// construct immediate dominator information for a flow-graph based on the
  13 /// Semi-NCA algorithm described in this dissertation:
  14 ///
  15 ///   Linear-Time Algorithms for Dominators and Related Problems
  16 ///   Loukas Georgiadis, Princeton University, November 2005, pp. 21-23:
  17 ///   ftp://ftp.cs.princeton.edu/reports/2005/737.pdf
  18 ///
  19 /// This implements the O(n*log(n)) versions of EVAL and LINK, because it turns
  20 /// out that the theoretically slower O(n*log(n)) implementation is actually
  21 /// faster than the almost-linear O(n*alpha(n)) version, even for large CFGs.
  22 ///
  23 //===----------------------------------------------------------------------===//
  24
  25 #ifndef LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
  26 #define LLVM_SUPPORT_GENERICDOMTREECONSTRUCTION_H
  27
  28 #include "llvm/ADT/DepthFirstIterator.h"
  29 #include "llvm/ADT/SmallPtrSet.h"
  30 #include "llvm/Support/GenericDomTree.h"
  31
  32 namespace llvm {
  33 namespace DomTreeBuilder {
  34
  35 template <typename NodePtr, bool Inverse>
  36 struct ChildrenGetter {
  37   static auto Get(NodePtr N) -> decltype(reverse(children<NodePtr>(N))) {
  38     return reverse(children<NodePtr>(N));
  39   }
  40 };
  41
  42 template <typename NodePtr>
  43 struct ChildrenGetter<NodePtr, true> {
  44   static auto Get(NodePtr N) -> decltype(inverse_children<NodePtr>(N)) {
  45     return inverse_children<NodePtr>(N);
  46   }
  47 };
  48
  49 // Information record used by Semi-NCA during tree construction.
  50 template <typename NodeT>
  51 struct SemiNCAInfo {
  52   using NodePtr = NodeT *;
  53   using DomTreeT = DominatorTreeBase<NodeT>;
  54   using TreeNodePtr = DomTreeNodeBase<NodeT> *;
  55
  56   struct InfoRec {
  57     unsigned DFSNum = 0;
  58     unsigned Parent = 0;
  59     unsigned Semi = 0;
  60     NodePtr Label = nullptr;
  61     NodePtr IDom = nullptr;
  62     SmallVector<NodePtr, 2> ReverseChildren;
  63   };
  64
  65   std::vector<NodePtr> NumToNode;
  66   DenseMap<NodePtr, InfoRec> NodeToInfo;
  67
  68   void clear() {
  69     NumToNode.clear();
  70     NodeToInfo.clear();
  71   }
  72
  73   NodePtr getIDom(NodePtr BB) const {
  74     auto InfoIt = NodeToInfo.find(BB);
  75     if (InfoIt == NodeToInfo.end()) return nullptr;
  76
  77     return InfoIt->second.IDom;
  78   }
  79
  80   TreeNodePtr getNodeForBlock(NodePtr BB, DomTreeT &DT) {
  81     if (TreeNodePtr Node = DT.getNode(BB)) return Node;
  82
  83     // Haven't calculated this node yet?  Get or calculate the node for the
  84     // immediate dominator.
  85     NodePtr IDom = getIDom(BB);
  86
  87     assert(IDom || DT.DomTreeNodes[nullptr]);
  88     TreeNodePtr IDomNode = getNodeForBlock(IDom, DT);
  89
  90     // Add a new tree node for this NodeT, and link it as a child of
  91     // IDomNode
  92     return (DT.DomTreeNodes[BB] = IDomNode->addChild(
  93                 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode)))
  94         .get();
  95   }
  96
  97   static bool AlwaysDescend(NodePtr, NodePtr) { return true; }
  98
  99   // Custom DFS implementation which can skip nodes based on a provided
 100   // predicate. It also collects ReverseChildren so that we don't have to spend
 101   // time getting predecessors in SemiNCA.
 102   template <bool Inverse, typename DescendCondition>
 103   unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition,
 104                   unsigned AttachToNum) {
 105     assert(V);
 106     SmallVector<NodePtr, 64> WorkList = {V};
 107     if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum;
 108
 109     while (!WorkList.empty()) {
 110       const NodePtr BB = WorkList.pop_back_val();
 111       auto &BBInfo = NodeToInfo[BB];
 112
 113       // Visited nodes always have positive DFS numbers.
 114       if (BBInfo.DFSNum != 0) continue;
 115       BBInfo.DFSNum = BBInfo.Semi = ++LastNum;
 116       BBInfo.Label = BB;
 117       NumToNode.push_back(BB);
 118
 119       for (const NodePtr Succ : ChildrenGetter<NodePtr, Inverse>::Get(BB)) {
 120         const auto SIT = NodeToInfo.find(Succ);
 121         // Don't visit nodes more than once but remember to collect
 122         // RerverseChildren.
 123         if (SIT != NodeToInfo.end() && SIT->second.DFSNum != 0) {
 124           if (Succ != BB) SIT->second.ReverseChildren.push_back(BB);
 125           continue;
 126         }
 127
 128         if (!Condition(BB, Succ)) continue;
 129
 130         // It's fine to add Succ to the map, because we know that it will be
 131         // visited later.
 132         auto &SuccInfo = NodeToInfo[Succ];
 133         WorkList.push_back(Succ);
 134         SuccInfo.Parent = LastNum;
 135         SuccInfo.ReverseChildren.push_back(BB);
 136       }
 137     }
 138
 139     return LastNum;
 140   }
 141
 142   NodePtr eval(NodePtr VIn, unsigned LastLinked) {
 143     auto &VInInfo = NodeToInfo[VIn];
 144     if (VInInfo.DFSNum < LastLinked)
 145       return VIn;
 146
 147     SmallVector<NodePtr, 32> Work;
 148     SmallPtrSet<NodePtr, 32> Visited;
 149
 150     if (VInInfo.Parent >= LastLinked)
 151       Work.push_back(VIn);
 152
 153     while (!Work.empty()) {
 154       NodePtr V = Work.back();
 155       auto &VInfo = NodeToInfo[V];
 156       NodePtr VAncestor = NumToNode[VInfo.Parent];
 157
 158       // Process Ancestor first
 159       if (Visited.insert(VAncestor).second && VInfo.Parent >= LastLinked) {
 160         Work.push_back(VAncestor);
 161         continue;
 162       }
 163       Work.pop_back();
 164
 165       // Update VInfo based on Ancestor info
 166       if (VInfo.Parent < LastLinked)
 167         continue;
 168
 169       auto &VAInfo = NodeToInfo[VAncestor];
 170       NodePtr VAncestorLabel = VAInfo.Label;
 171       NodePtr VLabel = VInfo.Label;
 172       if (NodeToInfo[VAncestorLabel].Semi < NodeToInfo[VLabel].Semi)
 173         VInfo.Label = VAncestorLabel;
 174       VInfo.Parent = VAInfo.Parent;
 175     }
 176
 177     return VInInfo.Label;
 178   }
 179
 180   template <typename NodeType>
 181   void runSemiNCA(DomTreeT &DT, unsigned NumBlocks) {
 182     // Step #1: Number blocks in depth-first order and initialize variables used
 183     // in later stages of the algorithm.
 184     const unsigned N = doFullDFSWalk(DT, AlwaysDescend);
 185
 186     // It might be that some blocks did not get a DFS number (e.g., blocks of
 187     // infinite loops). In these cases an artificial exit node is required.
 188     const bool MultipleRoots =
 189         DT.Roots.size() > 1 || (DT.isPostDominator() && N != NumBlocks);
 190
 191     // Initialize IDoms to spanning tree parents.
 192     for (unsigned i = 1; i <= N; ++i) {
 193       const NodePtr V = NumToNode[i];
 194       auto &VInfo = NodeToInfo[V];
 195       VInfo.IDom = NumToNode[VInfo.Parent];
 196     }
 197
 198     // Step #2: Calculate the semidominators of all vertices.
 199     for (unsigned i = N; i >= 2; --i) {
 200       NodePtr W = NumToNode[i];
 201       auto &WInfo = NodeToInfo[W];
 202
 203       // Initialize the semi dominator to point to the parent node.
 204       WInfo.Semi = WInfo.Parent;
 205       for (const auto &N : WInfo.ReverseChildren)
 206         if (NodeToInfo.count(N)) {  // Only if this predecessor is reachable!
 207           unsigned SemiU = NodeToInfo[eval(N, i + 1)].Semi;
 208           if (SemiU < WInfo.Semi)
 209             WInfo.Semi = SemiU;
 210         }
 211     }
 212
 213     // Step #3: Explicitly define the immediate dominator of each vertex.
 214     //          IDom[i] = NCA(SDom[i], SpanningTreeParent(i)).
 215     // Note that the parents were stored in IDoms and later got invalidated
 216     // during path compression in Eval.
 217     for (unsigned i = 2; i <= N; ++i) {
 218       const NodePtr W = NumToNode[i];
 219       auto &WInfo = NodeToInfo[W];
 220       const unsigned SDomNum = NodeToInfo[NumToNode[WInfo.Semi]].DFSNum;
 221       NodePtr WIDomCandidate = WInfo.IDom;
 222       while (NodeToInfo[WIDomCandidate].DFSNum > SDomNum)
 223         WIDomCandidate = NodeToInfo[WIDomCandidate].IDom;
 224
 225       WInfo.IDom = WIDomCandidate;
 226     }
 227
 228     if (DT.Roots.empty()) return;
 229
 230     // Add a node for the root.  This node might be the actual root, if there is
 231     // one exit block, or it may be the virtual exit (denoted by
 232     // (BasicBlock *)0) which postdominates all real exits if there are multiple
 233     // exit blocks, or an infinite loop.
 234     NodePtr Root = !MultipleRoots ? DT.Roots[0] : nullptr;
 235
 236     DT.RootNode =
 237         (DT.DomTreeNodes[Root] =
 238              llvm::make_unique<DomTreeNodeBase<NodeT>>(Root, nullptr))
 239             .get();
 240
 241     // Loop over all of the reachable blocks in the function...
 242     for (unsigned i = 2; i <= N; ++i) {
 243       NodePtr W = NumToNode[i];
 244
 245       // Don't replace this with 'count', the insertion side effect is important
 246       if (DT.DomTreeNodes[W])
 247         continue; // Haven't calculated this node yet?
 248
 249       NodePtr ImmDom = getIDom(W);
 250
 251       assert(ImmDom || DT.DomTreeNodes[nullptr]);
 252
 253       // Get or calculate the node for the immediate dominator
 254       TreeNodePtr IDomNode = getNodeForBlock(ImmDom, DT);
 255
 256       // Add a new tree node for this BasicBlock, and link it as a child of
 257       // IDomNode
 258       DT.DomTreeNodes[W] = IDomNode->addChild(
 259           llvm::make_unique<DomTreeNodeBase<NodeT>>(W, IDomNode));
 260     }
 261   }
 262
 263   template <typename DescendCondition>
 264   unsigned doFullDFSWalk(const DomTreeT &DT, DescendCondition DC) {
 265     unsigned Num = 0;
 266     NumToNode.push_back(nullptr);
 267
 268     if (DT.Roots.size() > 1) {
 269       auto &BBInfo = NodeToInfo[nullptr];
 270       BBInfo.DFSNum = BBInfo.Semi = ++Num;
 271       BBInfo.Label = nullptr;
 272
 273       NumToNode.push_back(nullptr);  // NumToNode[n] = V;
 274     }
 275
 276     if (DT.isPostDominator()) {
 277       for (auto *Root : DT.Roots) Num = runDFS<true>(Root, Num, DC, 1);
 278     } else {
 279       assert(DT.Roots.size() == 1);
 280       Num = runDFS<false>(DT.Roots[0], Num, DC, Num);
 281     }
 282
 283     return Num;
 284   }
 285
 286   static void PrintBlockOrNullptr(raw_ostream &O, NodePtr Obj) {
 287     if (!Obj)
 288       O << "nullptr";
 289     else
 290       Obj->printAsOperand(O, false);
 291   }
 292
 293   // Checks if the tree contains all reachable nodes in the input graph.
 294   bool verifyReachability(const DomTreeT &DT) {
 295     clear();
 296     doFullDFSWalk(DT, AlwaysDescend);
 297
 298     for (auto &NodeToTN : DT.DomTreeNodes) {
 299       const TreeNodePtr TN = NodeToTN.second.get();
 300       const NodePtr BB = TN->getBlock();
 301       if (!BB) continue;
 302
 303       if (NodeToInfo.count(BB) == 0) {
 304         errs() << "DomTree node ";
 305         PrintBlockOrNullptr(errs(), BB);
 306         errs() << " not found by DFS walk!\n";
 307         errs().flush();
 308
 309         return false;
 310       }
 311     }
 312
 313     return true;
 314   }
 315
 316   // Check if for every parent with a level L in the tree all of its children
 317   // have level L + 1.
 318   static bool VerifyLevels(const DomTreeT &DT) {
 319     for (auto &NodeToTN : DT.DomTreeNodes) {
 320       const TreeNodePtr TN = NodeToTN.second.get();
 321       const NodePtr BB = TN->getBlock();
 322       if (!BB) continue;
 323
 324       const TreeNodePtr IDom = TN->getIDom();
 325       if (!IDom && TN->getLevel() != 0) {
 326         errs() << "Node without an IDom ";
 327         PrintBlockOrNullptr(errs(), BB);
 328         errs() << " has a nonzero level " << TN->getLevel() << "!\n";
 329         errs().flush();
 330
 331         return false;
 332       }
 333
 334       if (IDom && TN->getLevel() != IDom->getLevel() + 1) {
 335         errs() << "Node ";
 336         PrintBlockOrNullptr(errs(), BB);
 337         errs() << " has level " << TN->getLevel() << " while it's IDom ";
 338         PrintBlockOrNullptr(errs(), IDom->getBlock());
 339         errs() << " has level " << IDom->getLevel() << "!\n";
 340         errs().flush();
 341
 342         return false;
 343       }
 344     }
 345
 346     return true;
 347   }
 348
 349   // Checks if for every edge From -> To in the graph
 350   //     NCD(From, To) == IDom(To) or To.
 351   bool verifyNCD(const DomTreeT &DT) {
 352     clear();
 353     doFullDFSWalk(DT, AlwaysDescend);
 354
 355     for (auto &BlockToInfo : NodeToInfo) {
 356       auto &Info = BlockToInfo.second;
 357
 358       const NodePtr From = NumToNode[Info.Parent];
 359       if (!From) continue;
 360
 361       const NodePtr To = BlockToInfo.first;
 362       const TreeNodePtr ToTN = DT.getNode(To);
 363       assert(ToTN);
 364
 365       const NodePtr NCD = DT.findNearestCommonDominator(From, To);
 366       const TreeNodePtr NCDTN = NCD ? DT.getNode(NCD) : nullptr;
 367       const TreeNodePtr ToIDom = ToTN->getIDom();
 368       if (NCDTN != ToTN && NCDTN != ToIDom) {
 369         errs() << "NearestCommonDominator verification failed:\n\tNCD(From:";
 370         PrintBlockOrNullptr(errs(), From);
 371         errs() << ", To:";
 372         PrintBlockOrNullptr(errs(), To);
 373         errs() << ") = ";
 374         PrintBlockOrNullptr(errs(), NCD);
 375         errs() << ",\t (should be To or IDom[To]: ";
 376         PrintBlockOrNullptr(errs(), ToIDom ? ToIDom->getBlock() : nullptr);
 377         errs() << ")\n";
 378         errs().flush();
 379
 380         return false;
 381       }
 382     }
 383
 384     return true;
 385   }
 386
 387   // The below routines verify the correctness of the dominator tree relative to
 388   // the CFG it's coming from.  A tree is a dominator tree iff it has two
 389   // properties, called the parent property and the sibling property.  Tarjan
 390   // and Lengauer prove (but don't explicitly name) the properties as part of
 391   // the proofs in their 1972 paper, but the proofs are mostly part of proving
 392   // things about semidominators and idoms, and some of them are simply asserted
 393   // based on even earlier papers (see, e.g., lemma 2).  Some papers refer to
 394   // these properties as "valid" and "co-valid".  See, e.g., "Dominators,
 395   // directed bipolar orders, and independent spanning trees" by Loukas
 396   // Georgiadis and Robert E. Tarjan, as well as "Dominator Tree Verification
 397   // and Vertex-Disjoint Paths " by the same authors.
 398
 399   // A very simple and direct explanation of these properties can be found in
 400   // "An Experimental Study of Dynamic Dominators", found at
 401   // https://arxiv.org/abs/1604.02711
 402
 403   // The easiest way to think of the parent property is that it's a requirement
 404   // of being a dominator.  Let's just take immediate dominators.  For PARENT to
 405   // be an immediate dominator of CHILD, all paths in the CFG must go through
 406   // PARENT before they hit CHILD.  This implies that if you were to cut PARENT
 407   // out of the CFG, there should be no paths to CHILD that are reachable.  If
 408   // there are, then you now have a path from PARENT to CHILD that goes around
 409   // PARENT and still reaches CHILD, which by definition, means PARENT can't be
 410   // a dominator of CHILD (let alone an immediate one).
 411
 412   // The sibling property is similar.  It says that for each pair of sibling
 413   // nodes in the dominator tree (LEFT and RIGHT) , they must not dominate each
 414   // other.  If sibling LEFT dominated sibling RIGHT, it means there are no
 415   // paths in the CFG from sibling LEFT to sibling RIGHT that do not go through
 416   // LEFT, and thus, LEFT is really an ancestor (in the dominator tree) of
 417   // RIGHT, not a sibling.
 418
 419   // It is possible to verify the parent and sibling properties in
 420   // linear time, but the algorithms are complex. Instead, we do it in a
 421   // straightforward N^2 and N^3 way below, using direct path reachability.
 422
 423
 424   // Checks if the tree has the parent property: if for all edges from V to W in
 425   // the input graph, such that V is reachable, the parent of W in the tree is
 426   // an ancestor of V in the tree.
 427   //
 428   // This means that if a node gets disconnected from the graph, then all of
 429   // the nodes it dominated previously will now become unreachable.
 430   bool verifyParentProperty(const DomTreeT &DT) {
 431     for (auto &NodeToTN : DT.DomTreeNodes) {
 432       const TreeNodePtr TN = NodeToTN.second.get();
 433       const NodePtr BB = TN->getBlock();
 434       if (!BB || TN->getChildren().empty()) continue;
 435
 436       clear();
 437       doFullDFSWalk(DT, [BB](NodePtr From, NodePtr To) {
 438         return From != BB && To != BB;
 439       });
 440
 441       for (TreeNodePtr Child : TN->getChildren())
 442         if (NodeToInfo.count(Child->getBlock()) != 0) {
 443           errs() << "Child ";
 444           PrintBlockOrNullptr(errs(), Child->getBlock());
 445           errs() << " reachable after its parent ";
 446           PrintBlockOrNullptr(errs(), BB);
 447           errs() << " is removed!\n";
 448           errs().flush();
 449
 450           return false;
 451         }
 452     }
 453
 454     return true;
 455   }
 456
 457   // Check if the tree has sibling property: if a node V does not dominate a
 458   // node W for all siblings V and W in the tree.
 459   //
 460   // This means that if a node gets disconnected from the graph, then all of its
 461   // siblings will now still be reachable.
 462   bool verifySiblingProperty(const DomTreeT &DT) {
 463     for (auto &NodeToTN : DT.DomTreeNodes) {
 464       const TreeNodePtr TN = NodeToTN.second.get();
 465       const NodePtr BB = TN->getBlock();
 466       if (!BB || TN->getChildren().empty()) continue;
 467
 468       const auto &Siblings = TN->getChildren();
 469       for (const TreeNodePtr N : Siblings) {
 470         clear();
 471         NodePtr BBN = N->getBlock();
 472         doFullDFSWalk(DT, [BBN](NodePtr From, NodePtr To) {
 473           return From != BBN && To != BBN;
 474         });
 475
 476         for (const TreeNodePtr S : Siblings) {
 477           if (S == N) continue;
 478
 479           if (NodeToInfo.count(S->getBlock()) == 0) {
 480             errs() << "Node ";
 481             PrintBlockOrNullptr(errs(), S->getBlock());
 482             errs() << " not reachable when its sibling ";
 483             PrintBlockOrNullptr(errs(), N->getBlock());
 484             errs() << " is removed!\n";
 485             errs().flush();
 486
 487             return false;
 488           }
 489         }
 490       }
 491     }
 492
 493     return true;
 494   }
 495 };
 496
 497 template <class FuncT, class NodeT>
 498 void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT,
 499                FuncT &F) {
 500   using NodePtr = typename GraphTraits<NodeT>::NodeRef;
 501   static_assert(std::is_pointer<NodePtr>::value,
 502                 "NodePtr should be a pointer type");
 503   SemiNCAInfo<typename std::remove_pointer<NodePtr>::type> SNCA;
 504   SNCA.template runSemiNCA<NodeT>(DT, GraphTraits<FuncT *>::size(&F));
 505 }
 506
 507 template <class NodeT>
 508 bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<NodeT>> &DT) {
 509   using NodePtr = typename GraphTraits<NodeT>::NodeRef;
 510   static_assert(std::is_pointer<NodePtr>::value,
 511                 "NodePtr should be a pointer type");
 512   SemiNCAInfo<typename std::remove_pointer<NodePtr>::type> SNCA;
 513
 514   return SNCA.verifyReachability(DT) && SNCA.VerifyLevels(DT) &&
 515          SNCA.verifyNCD(DT) && SNCA.verifyParentProperty(DT) &&
 516          SNCA.verifySiblingProperty(DT);
 517 }
 518
 519 }  // namespace DomTreeBuilder
 520 }  // namespace llvm
 521
 522 #endif