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