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 DomTreeNodeBase *I : *Other) {
113      const NodeT *Nd = I->getBlock();
114      OtherChildren.insert(Nd);
115    }
116
117    for (const DomTreeNodeBase *I : *this) {
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 return the DFS visitation order for nodes
142  /// in the dominator tree. They are only guaranteed valid if
143  /// updateDFSNumbers() has been called.
144  unsigned getDFSNumIn() const { return DFSNumIn; }
145  unsigned getDFSNumOut() const { return DFSNumOut; }
146
147private:
148  // Return true if this node is dominated by other. Use this only if DFS info
149  // is valid.
150  bool DominatedBy(const DomTreeNodeBase<NodeT> *other) const {
151    return this->DFSNumIn >= other->DFSNumIn &&
152           this->DFSNumOut <= other->DFSNumOut;
153  }
154};
155
156template <class NodeT>
157raw_ostream &operator<<(raw_ostream &o, const DomTreeNodeBase<NodeT> *Node) {
158  if (Node->getBlock())
159    Node->getBlock()->printAsOperand(o, false);
160  else
161    o << " <<exit node>>";
162
163  o << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}";
164
165  return o << "\n";
166}
167
168template <class NodeT>
169void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &o,
170                  unsigned Lev) {
171  o.indent(2 * Lev) << "[" << Lev << "] " << N;
172  for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
173                                                       E = N->end();
174       I != E; ++I)
175    PrintDomTree<NodeT>(*I, o, Lev + 1);
176}
177
178// The calculate routine is provided in a separate header but referenced here.
179template <class FuncT, class N>
180void Calculate(DominatorTreeBase<typename GraphTraits<N>::NodeType> &DT,
181               FuncT &F);
182
183/// \brief Core dominator tree base class.
184///
185/// This class is a generic template over graph nodes. It is instantiated for
186/// various graphs in the LLVM IR or in the code generator.
187template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> {
188  DominatorTreeBase(const DominatorTreeBase &) = delete;
189  DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
190
191  bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
192                               const DomTreeNodeBase<NodeT> *B) const {
193    assert(A != B);
194    assert(isReachableFromEntry(B));
195    assert(isReachableFromEntry(A));
196
197    const DomTreeNodeBase<NodeT> *IDom;
198    while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B)
199      B = IDom; // Walk up the tree
200    return IDom != nullptr;
201  }
202
203  /// \brief Wipe this tree's state without releasing any resources.
204  ///
205  /// This is essentially a post-move helper only. It leaves the object in an
206  /// assignable and destroyable state, but otherwise invalid.
207  void wipe() {
208    DomTreeNodes.clear();
209    IDoms.clear();
210    Vertex.clear();
211    Info.clear();
212    RootNode = nullptr;
213  }
214
215protected:
216  typedef DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>
217      DomTreeNodeMapType;
218  DomTreeNodeMapType DomTreeNodes;
219  DomTreeNodeBase<NodeT> *RootNode;
220
221  mutable bool DFSInfoValid;
222  mutable unsigned int SlowQueries;
223  // Information record used during immediate dominators computation.
224  struct InfoRec {
225    unsigned DFSNum;
226    unsigned Parent;
227    unsigned Semi;
228    NodeT *Label;
229
230    InfoRec() : DFSNum(0), Parent(0), Semi(0), Label(nullptr) {}
231  };
232
233  DenseMap<NodeT *, NodeT *> IDoms;
234
235  // Vertex - Map the DFS number to the NodeT*
236  std::vector<NodeT *> Vertex;
237
238  // Info - Collection of information used during the computation of idoms.
239  DenseMap<NodeT *, InfoRec> Info;
240
241  void reset() {
242    DomTreeNodes.clear();
243    IDoms.clear();
244    this->Roots.clear();
245    Vertex.clear();
246    RootNode = nullptr;
247    DFSInfoValid = false;
248    SlowQueries = 0;
249  }
250
251  // NewBB is split and now it has one successor. Update dominator tree to
252  // reflect this change.
253  template <class N, class GraphT>
254  void Split(DominatorTreeBase<typename GraphT::NodeType> &DT,
255             typename GraphT::NodeType *NewBB) {
256    assert(std::distance(GraphT::child_begin(NewBB),
257                         GraphT::child_end(NewBB)) == 1 &&
258           "NewBB should have a single successor!");
259    typename GraphT::NodeType *NewBBSucc = *GraphT::child_begin(NewBB);
260
261    std::vector<typename GraphT::NodeType *> PredBlocks;
262    typedef GraphTraits<Inverse<N>> InvTraits;
263    for (typename InvTraits::ChildIteratorType
264             PI = InvTraits::child_begin(NewBB),
265             PE = InvTraits::child_end(NewBB);
266         PI != PE; ++PI)
267      PredBlocks.push_back(*PI);
268
269    assert(!PredBlocks.empty() && "No predblocks?");
270
271    bool NewBBDominatesNewBBSucc = true;
272    for (typename InvTraits::ChildIteratorType
273             PI = InvTraits::child_begin(NewBBSucc),
274             E = InvTraits::child_end(NewBBSucc);
275         PI != E; ++PI) {
276      typename InvTraits::NodeType *ND = *PI;
277      if (ND != NewBB && !DT.dominates(NewBBSucc, ND) &&
278          DT.isReachableFromEntry(ND)) {
279        NewBBDominatesNewBBSucc = false;
280        break;
281      }
282    }
283
284    // Find NewBB's immediate dominator and create new dominator tree node for
285    // NewBB.
286    NodeT *NewBBIDom = nullptr;
287    unsigned i = 0;
288    for (i = 0; i < PredBlocks.size(); ++i)
289      if (DT.isReachableFromEntry(PredBlocks[i])) {
290        NewBBIDom = PredBlocks[i];
291        break;
292      }
293
294    // It's possible that none of the predecessors of NewBB are reachable;
295    // in that case, NewBB itself is unreachable, so nothing needs to be
296    // changed.
297    if (!NewBBIDom)
298      return;
299
300    for (i = i + 1; i < PredBlocks.size(); ++i) {
301      if (DT.isReachableFromEntry(PredBlocks[i]))
302        NewBBIDom = DT.findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
303    }
304
305    // Create the new dominator tree node... and set the idom of NewBB.
306    DomTreeNodeBase<NodeT> *NewBBNode = DT.addNewBlock(NewBB, NewBBIDom);
307
308    // If NewBB strictly dominates other blocks, then it is now the immediate
309    // dominator of NewBBSucc.  Update the dominator tree as appropriate.
310    if (NewBBDominatesNewBBSucc) {
311      DomTreeNodeBase<NodeT> *NewBBSuccNode = DT.getNode(NewBBSucc);
312      DT.changeImmediateDominator(NewBBSuccNode, NewBBNode);
313    }
314  }
315
316public:
317  explicit DominatorTreeBase(bool isPostDom)
318      : DominatorBase<NodeT>(isPostDom), DFSInfoValid(false), SlowQueries(0) {}
319
320  DominatorTreeBase(DominatorTreeBase &&Arg)
321      : DominatorBase<NodeT>(
322            std::move(static_cast<DominatorBase<NodeT> &>(Arg))),
323        DomTreeNodes(std::move(Arg.DomTreeNodes)),
324        RootNode(std::move(Arg.RootNode)),
325        DFSInfoValid(std::move(Arg.DFSInfoValid)),
326        SlowQueries(std::move(Arg.SlowQueries)), IDoms(std::move(Arg.IDoms)),
327        Vertex(std::move(Arg.Vertex)), Info(std::move(Arg.Info)) {
328    Arg.wipe();
329  }
330  DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
331    DominatorBase<NodeT>::operator=(
332        std::move(static_cast<DominatorBase<NodeT> &>(RHS)));
333    DomTreeNodes = std::move(RHS.DomTreeNodes);
334    RootNode = std::move(RHS.RootNode);
335    DFSInfoValid = std::move(RHS.DFSInfoValid);
336    SlowQueries = std::move(RHS.SlowQueries);
337    IDoms = std::move(RHS.IDoms);
338    Vertex = std::move(RHS.Vertex);
339    Info = std::move(RHS.Info);
340    RHS.wipe();
341    return *this;
342  }
343
344  /// compare - Return false if the other dominator tree base matches this
345  /// dominator tree base. Otherwise return true.
346  bool compare(const DominatorTreeBase &Other) const {
347
348    const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
349    if (DomTreeNodes.size() != OtherDomTreeNodes.size())
350      return true;
351
352    for (const auto &DomTreeNode : this->DomTreeNodes) {
353      NodeT *BB = DomTreeNode.first;
354      typename DomTreeNodeMapType::const_iterator OI =
355          OtherDomTreeNodes.find(BB);
356      if (OI == OtherDomTreeNodes.end())
357        return true;
358
359      DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
360      DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
361
362      if (MyNd.compare(&OtherNd))
363        return true;
364    }
365
366    return false;
367  }
368
369  void releaseMemory() { reset(); }
370
371  /// getNode - return the (Post)DominatorTree node for the specified basic
372  /// block.  This is the same as using operator[] on this class.  The result
373  /// may (but is not required to) be null for a forward (backwards)
374  /// statically unreachable block.
375  DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
376    auto I = DomTreeNodes.find(BB);
377    if (I != DomTreeNodes.end())
378      return I->second.get();
379    return nullptr;
380  }
381
382  /// See getNode.
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 EXPENSIVE_CHECKS
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      addRoot(entry);
726
727      Calculate<FT, NodeT *>(*this, F);
728    } else {
729      // Initialize the roots list
730      for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F),
731                                             E = TraitsTy::nodes_end(&F);
732           I != E; ++I)
733        if (TraitsTy::child_begin(&*I) == TraitsTy::child_end(&*I))
734          addRoot(&*I);
735
736      Calculate<FT, Inverse<NodeT *>>(*this, F);
737    }
738  }
739};
740
741// These two functions are declared out of line as a workaround for building
742// with old (< r147295) versions of clang because of pr11642.
743template <class NodeT>
744bool DominatorTreeBase<NodeT>::dominates(const NodeT *A, const NodeT *B) const {
745  if (A == B)
746    return true;
747
748  // Cast away the const qualifiers here. This is ok since
749  // this function doesn't actually return the values returned
750  // from getNode.
751  return dominates(getNode(const_cast<NodeT *>(A)),
752                   getNode(const_cast<NodeT *>(B)));
753}
754template <class NodeT>
755bool DominatorTreeBase<NodeT>::properlyDominates(const NodeT *A,
756                                                 const NodeT *B) const {
757  if (A == B)
758    return false;
759
760  // Cast away the const qualifiers here. This is ok since
761  // this function doesn't actually return the values returned
762  // from getNode.
763  return dominates(getNode(const_cast<NodeT *>(A)),
764                   getNode(const_cast<NodeT *>(B)));
765}
766
767}
768
769#endif
770