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