include/llvm/Support/GenericDomTree.h

   1 //===- GenericDomTree.h - Generic dominator trees for graphs ----*- 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 /// This file defines a set of templates that efficiently compute a dominator
  12 /// tree over a generic graph. This is used typically in LLVM for fast
  13 /// dominance queries on the CFG, but is fully generic w.r.t. the underlying
  14 /// graph types.
  15 ///
  16 //===----------------------------------------------------------------------===//
  17
  18 #ifndef LLVM_SUPPORT_GENERICDOMTREE_H
  19 #define LLVM_SUPPORT_GENERICDOMTREE_H
  20
  21 #include "llvm/ADT/DenseMap.h"
  22 #include "llvm/ADT/DepthFirstIterator.h"
  23 #include "llvm/ADT/GraphTraits.h"
  24 #include "llvm/ADT/SmallPtrSet.h"
  25 #include "llvm/ADT/SmallVector.h"
  26 #include "llvm/Support/Compiler.h"
  27 #include "llvm/Support/raw_ostream.h"
  28 #include <algorithm>
  29
  30 namespace llvm {
  31
  32 /// \brief Base class that other, more interesting dominator analyses
  33 /// inherit from.
  34 template <class NodeT> class DominatorBase {
  35 protected:
  36   std::vector<NodeT *> Roots;
  37   const bool IsPostDominators;
  38   inline explicit DominatorBase(bool isPostDom)
  39       : Roots(), IsPostDominators(isPostDom) {}
  40
  41 public:
  42   /// getRoots - Return the root blocks of the current CFG.  This may include
  43   /// multiple blocks if we are computing post dominators.  For forward
  44   /// dominators, this will always be a single block (the entry node).
  45   ///
  46   inline const std::vector<NodeT *> &getRoots() const { return Roots; }
  47
  48   /// isPostDominator - Returns true if analysis based of postdoms
  49   ///
  50   bool isPostDominator() const { return IsPostDominators; }
  51 };
  52
  53 template <class NodeT> class DominatorTreeBase;
  54 struct PostDominatorTree;
  55
  56 /// \brief Base class for the actual dominator tree node.
  57 template <class NodeT> class DomTreeNodeBase {
  58   NodeT *TheBB;
  59   DomTreeNodeBase<NodeT> *IDom;
  60   std::vector<DomTreeNodeBase<NodeT> *> Children;
  61   mutable int DFSNumIn, DFSNumOut;
  62
  63   template <class N> friend class DominatorTreeBase;
  64   friend struct PostDominatorTree;
  65
  66 public:
  67   typedef typename std::vector<DomTreeNodeBase<NodeT> *>::iterator iterator;
  68   typedef typename std::vector<DomTreeNodeBase<NodeT> *>::const_iterator
  69       const_iterator;
  70
  71   iterator begin() { return Children.begin(); }
  72   iterator end() { return Children.end(); }
  73   const_iterator begin() const { return Children.begin(); }
  74   const_iterator end() const { return Children.end(); }
  75
  76   NodeT *getBlock() const { return TheBB; }
  77   DomTreeNodeBase<NodeT> *getIDom() const { return IDom; }
  78   const std::vector<DomTreeNodeBase<NodeT> *> &getChildren() const {
  79     return Children;
  80   }
  81
  82   DomTreeNodeBase(NodeT *BB, DomTreeNodeBase<NodeT> *iDom)
  83       : TheBB(BB), IDom(iDom), DFSNumIn(-1), DFSNumOut(-1) {}
  84
  85   DomTreeNodeBase<NodeT> *addChild(DomTreeNodeBase<NodeT> *C) {
  86     Children.push_back(C);
  87     return C;
  88   }
  89
  90   size_t getNumChildren() const { return Children.size(); }
  91
  92   void clearAllChildren() { Children.clear(); }
  93
  94   bool compare(const DomTreeNodeBase<NodeT> *Other) const {
  95     if (getNumChildren() != Other->getNumChildren())
  96       return true;
  97
  98     SmallPtrSet<const NodeT *, 4> OtherChildren;
  99     for (const_iterator I = Other->begin(), E = Other->end(); I != E; ++I) {
 100       const NodeT *Nd = (*I)->getBlock();
 101       OtherChildren.insert(Nd);
 102     }
 103
 104     for (const_iterator I = begin(), E = end(); I != E; ++I) {
 105       const NodeT *N = (*I)->getBlock();
 106       if (OtherChildren.count(N) == 0)
 107         return true;
 108     }
 109     return false;
 110   }
 111
 112   void setIDom(DomTreeNodeBase<NodeT> *NewIDom) {
 113     assert(IDom && "No immediate dominator?");
 114     if (IDom != NewIDom) {
 115       typename std::vector<DomTreeNodeBase<NodeT> *>::iterator I =
 116           std::find(IDom->Children.begin(), IDom->Children.end(), this);
 117       assert(I != IDom->Children.end() &&
 118              "Not in immediate dominator children set!");
 119       // I am no longer your child...
 120       IDom->Children.erase(I);
 121
 122       // Switch to new dominator
 123       IDom = NewIDom;
 124       IDom->Children.push_back(this);
 125     }
 126   }
 127
 128   /// getDFSNumIn/getDFSNumOut - These are an internal implementation detail, do
 129   /// not call them.
 130   unsigned getDFSNumIn() const { return DFSNumIn; }
 131   unsigned getDFSNumOut() const { return DFSNumOut; }
 132
 133 private:
 134   // Return true if this node is dominated by other. Use this only if DFS info
 135   // is valid.
 136   bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const {
 137     return this->DFSNumIn >= other->DFSNumIn &&
 138            this->DFSNumOut <= other->DFSNumOut;
 139   }
 140 };
 141
 142 template <class NodeT>
 143 inline raw_ostream &operator<<(raw_ostream &o,
 144                                const DomTreeNodeBase<NodeT> *Node) {
 145   if (Node->getBlock())
 146     Node->getBlock()->printAsOperand(o, false);
 147   else
 148     o << " <<exit node>>";
 149
 150   o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}";
 151
 152   return o << "\n";
 153 }
 154
 155 template <class NodeT>
 156 inline void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o,
 157                          unsigned Lev) {
 158   o.indent(2 * Lev) << "[" << Lev << "] " << N;
 159   for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
 160                                                        E = N->end();
 161        I != E; ++I)
 162     PrintDomTree<NodeT>(*I, o, Lev + 1);
 163 }
 164
 165 // The calculate routine is provided in a separate header but referenced here.
 166 template <class FuncT, class N>
 167 void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType> &DT,
 168                FuncT &F);
 169
 170 /// \brief Core dominator tree base class.
 171 ///
 172 /// This class is a generic template over graph nodes. It is instantiated for
 173 /// various graphs in the LLVM IR or in the code generator.
 174 template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
 175   bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
 176                                const DomTreeNodeBase<NodeT> *B) const {
 177     assert(A != B);
 178     assert(isReachableFromEntry(B));
 179     assert(isReachableFromEntry(A));
 180
 181     const DomTreeNodeBase<NodeT> *IDom;
 182     while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B)
 183       B = IDom; // Walk up the tree
 184     return IDom != nullptr;
 185   }
 186
 187 protected:
 188   typedef DenseMap<NodeT *, DomTreeNodeBase<NodeT> *> DomTreeNodeMapType;
 189   DomTreeNodeMapType DomTreeNodes;
 190   DomTreeNodeBase<NodeT> *RootNode;
 191
 192   mutable bool DFSInfoValid;
 193   mutable unsigned int SlowQueries;
 194   // Information record used during immediate dominators computation.
 195   struct InfoRec {
 196     unsigned DFSNum;
 197     unsigned Parent;
 198     unsigned Semi;
 199     NodeT *Label;
 200
 201     InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(nullptr) {}
 202   };
 203
 204   DenseMap<NodeT *, NodeT *> IDoms;
 205
 206   // Vertex - Map the DFS number to the NodeT*
 207   std::vector<NodeT *> Vertex;
 208
 209   // Info - Collection of information used during the computation of idoms.
 210   DenseMap<NodeT *, InfoRec> Info;
 211
 212   void reset() {
 213     for (typename DomTreeNodeMapType::iterator I = this->DomTreeNodes.begin(),
 214                                                E = DomTreeNodes.end();
 215          I != E; ++I)
 216       delete I->second;
 217     DomTreeNodes.clear();
 218     IDoms.clear();
 219     this->Roots.clear();
 220     Vertex.clear();
 221     RootNode = nullptr;
 222   }
 223
 224   // NewBB is split and now it has one successor. Update dominator tree to
 225   // reflect this change.
 226   template <class N, class GraphT>
 227   void Split(DominatorTreeBase<typename GraphT::NodeType> &DT,
 228              typename GraphT::NodeType *NewBB) {
 229     assert(std::distance(GraphT::child_begin(NewBB),
 230                          GraphT::child_end(NewBB)) == 1 &&
 231            "NewBB should have a single successor!");
 232     typename GraphT::NodeType *NewBBSucc = *GraphT::child_begin(NewBB);
 233
 234     std::vector<typename GraphT::NodeType *> PredBlocks;
 235     typedef GraphTraits<Inverse<N>> InvTraits;
 236     for (typename InvTraits::ChildIteratorType
 237              PI = InvTraits::child_begin(NewBB),
 238              PE = InvTraits::child_end(NewBB);
 239          PI != PE; ++PI)
 240       PredBlocks.push_back(*PI);
 241
 242     assert(!PredBlocks.empty() && "No predblocks?");
 243
 244     bool NewBBDominatesNewBBSucc = true;
 245     for (typename InvTraits::ChildIteratorType
 246              PI = InvTraits::child_begin(NewBBSucc),
 247              E = InvTraits::child_end(NewBBSucc);
 248          PI != E; ++PI) {
 249       typename InvTraits::NodeType *ND = *PI;
 250       if (ND != NewBB && !DT.dominates(NewBBSucc, ND) &&
 251           DT.isReachableFromEntry(ND)) {
 252         NewBBDominatesNewBBSucc = false;
 253         break;
 254       }
 255     }
 256
 257     // Find NewBB's immediate dominator and create new dominator tree node for
 258     // NewBB.
 259     NodeT *NewBBIDom = nullptr;
 260     unsigned i = 0;
 261     for (i = 0; i < PredBlocks.size(); ++i)
 262       if (DT.isReachableFromEntry(PredBlocks[i])) {
 263         NewBBIDom = PredBlocks[i];
 264         break;
 265       }
 266
 267     // It's possible that none of the predecessors of NewBB are reachable;
 268     // in that case, NewBB itself is unreachable, so nothing needs to be
 269     // changed.
 270     if (!NewBBIDom)
 271       return;
 272
 273     for (i = i + 1; i < PredBlocks.size(); ++i) {
 274       if (DT.isReachableFromEntry(PredBlocks[i]))
 275         NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
 276     }
 277
 278     // Create the new dominator tree node... and set the idom of NewBB.
 279     DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom);
 280
 281     // If NewBB strictly dominates other blocks, then it is now the immediate
 282     // dominator of NewBBSucc.  Update the dominator tree as appropriate.
 283     if (NewBBDominatesNewBBSucc) {
 284       DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc);
 285       DT.changeImmediateDominator(NewBBSuccNode, NewBBNode);
 286     }
 287   }
 288
 289 public:
 290   explicit DominatorTreeBase(bool isPostDom)
 291       : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {}
 292   virtual ~DominatorTreeBase() { reset(); }
 293
 294   /// compare - Return false if the other dominator tree base matches this
 295   /// dominator tree base. Otherwise return true.
 296   bool compare(const DominatorTreeBase &Other) const {
 297
 298     const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
 299     if (DomTreeNodes.size() != OtherDomTreeNodes.size())
 300       return true;
 301
 302     for (typename DomTreeNodeMapType::const_iterator
 303              I = this->DomTreeNodes.begin(),
 304              E = this->DomTreeNodes.end();
 305          I != E; ++I) {
 306       NodeT *BB = I->first;
 307       typename DomTreeNodeMapType::const_iterator OI =
 308           OtherDomTreeNodes.find(BB);
 309       if (OI == OtherDomTreeNodes.end())
 310         return true;
 311
 312       DomTreeNodeBase<NodeT> *MyNd = I->second;
 313       DomTreeNodeBase<NodeT> *OtherNd = OI->second;
 314
 315       if (MyNd->compare(OtherNd))
 316         return true;
 317     }
 318
 319     return false;
 320   }
 321
 322   virtual void releaseMemory() { reset(); }
 323
 324   /// getNode - return the (Post)DominatorTree node for the specified basic
 325   /// block.  This is the same as using operator[] on this class.
 326   ///
 327   inline DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
 328     return DomTreeNodes.lookup(BB);
 329   }
 330
 331   inline DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const {
 332     return getNode(BB);
 333   }
 334
 335   /// getRootNode - This returns the entry node for the CFG of the function.  If
 336   /// this tree represents the post-dominance relations for a function, however,
 337   /// this root may be a node with the block == NULL.  This is the case when
 338   /// there are multiple exit nodes from a particular function.  Consumers of
 339   /// post-dominance information must be capable of dealing with this
 340   /// possibility.
 341   ///
 342   DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
 343   const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
 344
 345   /// Get all nodes dominated by R, including R itself.
 346   void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
 347     Result.clear();
 348     const DomTreeNodeBase<NodeT> *RN = getNode(R);
 349     if (!RN)
 350       return; // If R is unreachable, it will not be present in the DOM tree.
 351     SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
 352     WL.push_back(RN);
 353
 354     while (!WL.empty()) {
 355       const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
 356       Result.push_back(N->getBlock());
 357       WL.append(N->begin(), N->end());
 358     }
 359   }
 360
 361   /// properlyDominates - Returns true iff A dominates B and A != B.
 362   /// Note that this is not a constant time operation!
 363   ///
 364   bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
 365                          const DomTreeNodeBase<NodeT> *B) const {
 366     if (!A || !B)
 367       return false;
 368     if (A == B)
 369       return false;
 370     return dominates(A, B);
 371   }
 372
 373   bool properlyDominates(const NodeT *A, const NodeT *B) const;
 374
 375   /// isReachableFromEntry - Return true if A is dominated by the entry
 376   /// block of the function containing it.
 377   bool isReachableFromEntry(const NodeT *A) const {
 378     assert(!this->isPostDominator() &&
 379            "This is not implemented for post dominators");
 380     return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
 381   }
 382
 383   inline bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const {
 384     return A;
 385   }
 386
 387   /// dominates - Returns true iff A dominates B.  Note that this is not a
 388   /// constant time operation!
 389   ///
 390   inline bool dominates(const DomTreeNodeBase<NodeT> *A,
 391                         const DomTreeNodeBase<NodeT> *B) const {
 392     // A node trivially dominates itself.
 393     if (B == A)
 394       return true;
 395
 396     // An unreachable node is dominated by anything.
 397     if (!isReachableFromEntry(B))
 398       return true;
 399
 400     // And dominates nothing.
 401     if (!isReachableFromEntry(A))
 402       return false;
 403
 404     // Compare the result of the tree walk and the dfs numbers, if expensive
 405     // checks are enabled.
 406 #ifdef XDEBUG
 407     assert((!DFSInfoValid ||
 408             (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
 409            "Tree walk disagrees with dfs numbers!");
 410 #endif
 411
 412     if (DFSInfoValid)
 413       return B->DominatedBy(A);
 414
 415     // If we end up with too many slow queries, just update the
 416     // DFS numbers on the theory that we are going to keep querying.
 417     SlowQueries++;
 418     if (SlowQueries > 32) {
 419       updateDFSNumbers();
 420       return B->DominatedBy(A);
 421     }
 422
 423     return dominatedBySlowTreeWalk(A, B);
 424   }
 425
 426   bool dominates(const NodeT *A, const NodeT *B) const;
 427
 428   NodeT *getRoot() const {
 429     assert(this->Roots.size() == 1 && "Should always have entry node!");
 430     return this->Roots[0];
 431   }
 432
 433   /// findNearestCommonDominator - Find nearest common dominator basic block
 434   /// for basic block A and B. If there is no such block then return NULL.
 435   NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) {
 436     assert(A->getParent() == B->getParent() &&
 437            "Two blocks are not in same function");
 438
 439     // If either A or B is a entry block then it is nearest common dominator
 440     // (for forward-dominators).
 441     if (!this->isPostDominator()) {
 442       NodeT &Entry = A->getParent()->front();
 443       if (A == &Entry || B == &Entry)
 444         return &Entry;
 445     }
 446
 447     // If B dominates A then B is nearest common dominator.
 448     if (dominates(B, A))
 449       return B;
 450
 451     // If A dominates B then A is nearest common dominator.
 452     if (dominates(A, B))
 453       return A;
 454
 455     DomTreeNodeBase<NodeT> *NodeA = getNode(A);
 456     DomTreeNodeBase<NodeT> *NodeB = getNode(B);
 457
 458     // If we have DFS info, then we can avoid all allocations by just querying
 459     // it from each IDom. Note that because we call 'dominates' twice above, we
 460     // expect to call through this code at most 16 times in a row without
 461     // building valid DFS information. This is important as below is a *very*
 462     // slow tree walk.
 463     if (DFSInfoValid) {
 464       DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
 465       while (IDomA) {
 466         if (NodeB->DominatedBy(IDomA))
 467           return IDomA->getBlock();
 468         IDomA = IDomA->getIDom();
 469       }
 470       return nullptr;
 471     }
 472
 473     // Collect NodeA dominators set.
 474     SmallPtrSet<DomTreeNodeBase<NodeT> *, 16> NodeADoms;
 475     NodeADoms.insert(NodeA);
 476     DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom();
 477     while (IDomA) {
 478       NodeADoms.insert(IDomA);
 479       IDomA = IDomA->getIDom();
 480     }
 481
 482     // Walk NodeB immediate dominators chain and find common dominator node.
 483     DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom();
 484     while (IDomB) {
 485       if (NodeADoms.count(IDomB) != 0)
 486         return IDomB->getBlock();
 487
 488       IDomB = IDomB->getIDom();
 489     }
 490
 491     return nullptr;
 492   }
 493
 494   const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) {
 495     // Cast away the const qualifiers here. This is ok since
 496     // const is re-introduced on the return type.
 497     return findNearestCommonDominator(const_cast<NodeT *>(A),
 498                                       const_cast<NodeT *>(B));
 499   }
 500
 501   //===--------------------------------------------------------------------===//
 502   // API to update (Post)DominatorTree information based on modifications to
 503   // the CFG...
 504
 505   /// addNewBlock - Add a new node to the dominator tree information.  This
 506   /// creates a new node as a child of DomBB dominator node,linking it into
 507   /// the children list of the immediate dominator.
 508   DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
 509     assert(getNode(BB) == nullptr && "Block already in dominator tree!");
 510     DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
 511     assert(IDomNode && "Not immediate dominator specified for block!");
 512     DFSInfoValid = false;
 513     return DomTreeNodes[BB] =
 514                IDomNode->addChild(new DomTreeNodeBase<NodeT>(BB, IDomNode));
 515   }
 516
 517   /// changeImmediateDominator - This method is used to update the dominator
 518   /// tree information when a node's immediate dominator changes.
 519   ///
 520   void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
 521                                 DomTreeNodeBase<NodeT> *NewIDom) {
 522     assert(N && NewIDom && "Cannot change null node pointers!");
 523     DFSInfoValid = false;
 524     N->setIDom(NewIDom);
 525   }
 526
 527   void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
 528     changeImmediateDominator(getNode(BB), getNode(NewBB));
 529   }
 530
 531   /// eraseNode - Removes a node from the dominator tree. Block must not
 532   /// dominate any other blocks. Removes node from its immediate dominator's
 533   /// children list. Deletes dominator node associated with basic block BB.
 534   void eraseNode(NodeT *BB) {
 535     DomTreeNodeBase<NodeT> *Node = getNode(BB);
 536     assert(Node && "Removing node that isn't in dominator tree.");
 537     assert(Node->getChildren().empty() && "Node is not a leaf node.");
 538
 539     // Remove node from immediate dominator's children list.
 540     DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
 541     if (IDom) {
 542       typename std::vector<DomTreeNodeBase<NodeT> *>::iterator I =
 543           std::find(IDom->Children.begin(), IDom->Children.end(), Node);
 544       assert(I != IDom->Children.end() &&
 545              "Not in immediate dominator children set!");
 546       // I am no longer your child...
 547       IDom->Children.erase(I);
 548     }
 549
 550     DomTreeNodes.erase(BB);
 551     delete Node;
 552   }
 553
 554   /// removeNode - Removes a node from the dominator tree.  Block must not
 555   /// dominate any other blocks.  Invalidates any node pointing to removed
 556   /// block.
 557   void removeNode(NodeT *BB) {
 558     assert(getNode(BB) && "Removing node that isn't in dominator tree.");
 559     DomTreeNodes.erase(BB);
 560   }
 561
 562   /// splitBlock - BB is split and now it has one successor. Update dominator
 563   /// tree to reflect this change.
 564   void splitBlock(NodeT *NewBB) {
 565     if (this->IsPostDominators)
 566       this->Split<Inverse<NodeT *>, GraphTraits<Inverse<NodeT *>>>(*this,
 567                                                                    NewBB);
 568     else
 569       this->Split<NodeT *, GraphTraits<NodeT *>>(*this, NewBB);
 570   }
 571
 572   /// print - Convert to human readable form
 573   ///
 574   void print(raw_ostream &o) const {
 575     o << "=============================--------------------------------\n";
 576     if (this->isPostDominator())
 577       o << "Inorder PostDominator Tree: ";
 578     else
 579       o << "Inorder Dominator Tree: ";
 580     if (!this->DFSInfoValid)
 581       o << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
 582     o << "\n";
 583
 584     // The postdom tree can have a null root if there are no returns.
 585     if (getRootNode())
 586       PrintDomTree<NodeT>(getRootNode(), o, 1);
 587   }
 588
 589 protected:
 590   template <class GraphT>
 591   friend typename GraphT::NodeType *
 592   Eval(DominatorTreeBase<typename GraphT::NodeType> &DT,
 593        typename GraphT::NodeType *V, unsigned LastLinked);
 594
 595   template <class GraphT>
 596   friend unsigned DFSPass(DominatorTreeBase<typename GraphT::NodeType> &DT,
 597                           typename GraphT::NodeType *V, unsigned N);
 598
 599   template <class FuncT, class N>
 600   friend void
 601   Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType> &DT, FuncT &F);
 602
 603   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
 604   /// dominator tree in dfs order.
 605   void updateDFSNumbers() const {
 606     unsigned DFSNum = 0;
 607
 608     SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
 609                           typename DomTreeNodeBase<NodeT>::const_iterator>,
 610                 32> WorkStack;
 611
 612     const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
 613
 614     if (!ThisRoot)
 615       return;
 616
 617     // Even in the case of multiple exits that form the post dominator root
 618     // nodes, do not iterate over all exits, but start from the virtual root
 619     // node. Otherwise bbs, that are not post dominated by any exit but by the
 620     // virtual root node, will never be assigned a DFS number.
 621     WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
 622     ThisRoot->DFSNumIn = DFSNum++;
 623
 624     while (!WorkStack.empty()) {
 625       const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
 626       typename DomTreeNodeBase<NodeT>::const_iterator ChildIt =
 627           WorkStack.back().second;
 628
 629       // If we visited all of the children of this node, "recurse" back up the
 630       // stack setting the DFOutNum.
 631       if (ChildIt == Node->end()) {
 632         Node->DFSNumOut = DFSNum++;
 633         WorkStack.pop_back();
 634       } else {
 635         // Otherwise, recursively visit this child.
 636         const DomTreeNodeBase<NodeT> *Child = *ChildIt;
 637         ++WorkStack.back().second;
 638
 639         WorkStack.push_back(std::make_pair(Child, Child->begin()));
 640         Child->DFSNumIn = DFSNum++;
 641       }
 642     }
 643
 644     SlowQueries = 0;
 645     DFSInfoValid = true;
 646   }
 647
 648   DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) {
 649     if (DomTreeNodeBase<NodeT> *Node = getNode(BB))
 650       return Node;
 651
 652     // Haven't calculated this node yet?  Get or calculate the node for the
 653     // immediate dominator.
 654     NodeT *IDom = getIDom(BB);
 655
 656     assert(IDom || this->DomTreeNodes[nullptr]);
 657     DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom);
 658
 659     // Add a new tree node for this NodeT, and link it as a child of
 660     // IDomNode
 661     DomTreeNodeBase<NodeT> *C = new DomTreeNodeBase<NodeT>(BB, IDomNode);
 662     return this->DomTreeNodes[BB] = IDomNode->addChild(C);
 663   }
 664
 665   inline NodeT *getIDom(NodeT *BB) const { return IDoms.lookup(BB); }
 666
 667   inline void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
 668
 669 public:
 670   /// recalculate - compute a dominator tree for the given function
 671   template <class FT> void recalculate(FT &F) {
 672     typedef GraphTraits<FT *> TraitsTy;
 673     reset();
 674     this->Vertex.push_back(nullptr);
 675
 676     if (!this->IsPostDominators) {
 677       // Initialize root
 678       NodeT *entry = TraitsTy::getEntryNode(&F);
 679       this->Roots.push_back(entry);
 680       this->IDoms[entry] = nullptr;
 681       this->DomTreeNodes[entry] = nullptr;
 682
 683       Calculate<FT, NodeT *>(*this, F);
 684     } else {
 685       // Initialize the roots list
 686       for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F),
 687                                              E = TraitsTy::nodes_end(&F);
 688            I != E; ++I) {
 689         if (TraitsTy::child_begin(I) == TraitsTy::child_end(I))
 690           addRoot(I);
 691
 692         // Prepopulate maps so that we don't get iterator invalidation issues
 693         // later.
 694         this->IDoms[I] = nullptr;
 695         this->DomTreeNodes[I] = nullptr;
 696       }
 697
 698       Calculate<FT, Inverse<NodeT *>>(*this, F);
 699     }
 700   }
 701 };
 702
 703 // These two functions are declared out of line as a workaround for building
 704 // with old (< r147295) versions of clang because of pr11642.
 705 template <class NodeT>
 706 bool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) const {
 707   if (A == B)
 708     return true;
 709
 710   // Cast away the const qualifiers here. This is ok since
 711   // this function doesn't actually return the values returned
 712   // from getNode.
 713   return dominates(getNode(const_cast<NodeT *>(A)),
 714                    getNode(const_cast<NodeT *>(B)));
 715 }
 716 template <class NodeT>
 717 bool DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A,
 718                                                  const NodeT *B) const {
 719   if (A == B)
 720     return false;
 721
 722   // Cast away the const qualifiers here. This is ok since
 723   // this function doesn't actually return the values returned
 724   // from getNode.
 725   return dominates(getNode(const_cast<NodeT *>(A)),
 726                    getNode(const_cast<NodeT *>(B)));
 727 }
 728
 729 }
 730
 731 #endif