LCOV - code coverage report
Current view: top level - include/llvm/Support - GenericDomTree.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 195 263 74.1 %
Date: 2018-07-13 00:08:38 Functions: 40 212 18.9 %
Legend: Lines: hit not hit

          Line data    Source code
       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,
      18             : /// NodeRef->getParent() must return the parent node that is also a pointer.
      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 <algorithm>
      28             : #include <cassert>
      29             : #include <cstddef>
      30             : #include <iterator>
      31             : #include <memory>
      32             : #include <type_traits>
      33             : #include <utility>
      34             : #include <vector>
      35             : #include "llvm/ADT/DenseMap.h"
      36             : #include "llvm/ADT/GraphTraits.h"
      37             : #include "llvm/ADT/PointerIntPair.h"
      38             : #include "llvm/ADT/STLExtras.h"
      39             : #include "llvm/ADT/SmallPtrSet.h"
      40             : #include "llvm/ADT/SmallVector.h"
      41             : #include "llvm/Support/raw_ostream.h"
      42             : 
      43             : namespace llvm {
      44             : 
      45             : template <typename NodeT, bool IsPostDom>
      46             : class DominatorTreeBase;
      47             : 
      48             : namespace DomTreeBuilder {
      49             : template <typename DomTreeT>
      50             : struct SemiNCAInfo;
      51             : }  // namespace DomTreeBuilder
      52             : 
      53             : /// Base class for the actual dominator tree node.
      54    10546172 : template <class NodeT> class DomTreeNodeBase {
      55             :   friend class PostDominatorTree;
      56             :   friend class DominatorTreeBase<NodeT, false>;
      57             :   friend class DominatorTreeBase<NodeT, true>;
      58             :   friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, false>>;
      59             :   friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase<NodeT, true>>;
      60             : 
      61             :   NodeT *TheBB;
      62             :   DomTreeNodeBase *IDom;
      63             :   unsigned Level;
      64             :   std::vector<DomTreeNodeBase *> Children;
      65             :   mutable unsigned DFSNumIn = ~0;
      66             :   mutable unsigned DFSNumOut = ~0;
      67             : 
      68             :  public:
      69    10547502 :   DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
      70    21095004 :       : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {}
      71             : 
      72             :   using iterator = typename std::vector<DomTreeNodeBase *>::iterator;
      73             :   using const_iterator =
      74             :       typename std::vector<DomTreeNodeBase *>::const_iterator;
      75             : 
      76           0 :   iterator begin() { return Children.begin(); }
      77           0 :   iterator end() { return Children.end(); }
      78     6900199 :   const_iterator begin() const { return Children.begin(); }
      79    11473447 :   const_iterator end() const { return Children.end(); }
      80             : 
      81     3626596 :   NodeT *getBlock() const { return TheBB; }
      82    31126992 :   DomTreeNodeBase *getIDom() const { return IDom; }
      83    11172228 :   unsigned getLevel() const { return Level; }
      84             : 
      85           0 :   const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
      86             : 
      87           0 :   std::unique_ptr<DomTreeNodeBase> addChild(
      88             :       std::unique_ptr<DomTreeNodeBase> C) {
      89    18571619 :     Children.push_back(C.get());
      90           0 :     return C;
      91             :   }
      92             : 
      93       13233 :   size_t getNumChildren() const { return Children.size(); }
      94             : 
      95           0 :   void clearAllChildren() { Children.clear(); }
      96             : 
      97        6538 :   bool compare(const DomTreeNodeBase *Other) const {
      98        6538 :     if (getNumChildren() != Other->getNumChildren())
      99             :       return true;
     100             : 
     101        6537 :     if (Level != Other->Level) return true;
     102             : 
     103             :     SmallPtrSet<const NodeT *, 4> OtherChildren;
     104       12414 :     for (const DomTreeNodeBase *I : *Other) {
     105             :       const NodeT *Nd = I->getBlock();
     106        5877 :       OtherChildren.insert(Nd);
     107             :     }
     108             : 
     109       12414 :     for (const DomTreeNodeBase *I : *this) {
     110             :       const NodeT *N = I->getBlock();
     111        5877 :       if (OtherChildren.count(N) == 0)
     112             :         return true;
     113             :     }
     114             :     return false;
     115             :   }
     116             : 
     117     1184167 :   void setIDom(DomTreeNodeBase *NewIDom) {
     118             :     assert(IDom && "No immediate dominator?");
     119     1184167 :     if (IDom == NewIDom) return;
     120             : 
     121       74698 :     auto I = find(IDom->Children, this);
     122             :     assert(I != IDom->Children.end() &&
     123             :            "Not in immediate dominator children set!");
     124             :     // I am no longer your child...
     125       37349 :     IDom->Children.erase(I);
     126             : 
     127             :     // Switch to new dominator
     128       37349 :     IDom = NewIDom;
     129       74698 :     IDom->Children.push_back(this);
     130             : 
     131       37349 :     UpdateLevel();
     132             :   }
     133             : 
     134             :   /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes
     135             :   /// in the dominator tree. They are only guaranteed valid if
     136             :   /// updateDFSNumbers() has been called.
     137         195 :   unsigned getDFSNumIn() const { return DFSNumIn; }
     138         192 :   unsigned getDFSNumOut() const { return DFSNumOut; }
     139             : 
     140             : private:
     141             :   // Return true if this node is dominated by other. Use this only if DFS info
     142             :   // is valid.
     143           0 :   bool DominatedBy(const DomTreeNodeBase *other) const {
     144     2680025 :     return this->DFSNumIn >= other->DFSNumIn &&
     145      905258 :            this->DFSNumOut <= other->DFSNumOut;
     146             :   }
     147             : 
     148      242261 :   void UpdateLevel() {
     149             :     assert(IDom);
     150      445440 :     if (Level == IDom->Level + 1) return;
     151             : 
     152       78164 :     SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
     153             : 
     154      958872 :     while (!WorkStack.empty()) {
     155             :       DomTreeNodeBase *Current = WorkStack.pop_back_val();
     156      459895 :       Current->Level = Current->IDom->Level + 1;
     157             : 
     158      880708 :       for (DomTreeNodeBase *C : *Current) {
     159             :         assert(C->IDom);
     160      420813 :         if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
     161             :       }
     162             :     }
     163             :   }
     164             : };
     165             : 
     166             : template <class NodeT>
     167         183 : raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) {
     168         183 :   if (Node->getBlock())
     169         167 :     Node->getBlock()->printAsOperand(O, false);
     170             :   else
     171          16 :     O << " <<exit node>>";
     172             : 
     173         732 :   O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
     174           0 :     << Node->getLevel() << "]\n";
     175             : 
     176         183 :   return O;
     177             : }
     178             : 
     179             : template <class NodeT>
     180         183 : void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
     181             :                   unsigned Lev) {
     182         366 :   O.indent(2 * Lev) << "[" << Lev << "] " << N;
     183             :   for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
     184             :                                                        E = N->end();
     185         339 :        I != E; ++I)
     186         156 :     PrintDomTree<NodeT>(*I, O, Lev + 1);
     187         183 : }
     188             : 
     189             : namespace DomTreeBuilder {
     190             : // The routines below are provided in a separate header but referenced here.
     191             : template <typename DomTreeT>
     192             : void Calculate(DomTreeT &DT);
     193             : 
     194             : template <typename DomTreeT>
     195             : void InsertEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
     196             :                 typename DomTreeT::NodePtr To);
     197             : 
     198             : template <typename DomTreeT>
     199             : void DeleteEdge(DomTreeT &DT, typename DomTreeT::NodePtr From,
     200             :                 typename DomTreeT::NodePtr To);
     201             : 
     202             : // UpdateKind and Update are used by the batch update API and it's easiest to
     203             : // define them here.
     204             : enum class UpdateKind : unsigned char { Insert, Delete };
     205             : 
     206             : template <typename NodePtr>
     207             : struct Update {
     208             :   using NodeKindPair = PointerIntPair<NodePtr, 1, UpdateKind>;
     209             : 
     210             :   NodePtr From;
     211             :   NodeKindPair ToAndKind;
     212             : 
     213          96 :   Update(UpdateKind Kind, NodePtr From, NodePtr To)
     214      286643 :       : From(From), ToAndKind(To, Kind) {}
     215             : 
     216           0 :   UpdateKind getKind() const { return ToAndKind.getInt(); }
     217     1275582 :   NodePtr getFrom() const { return From; }
     218           0 :   NodePtr getTo() const { return ToAndKind.getPointer(); }
     219           0 :   bool operator==(const Update &RHS) const {
     220     4405573 :     return From == RHS.From && ToAndKind == RHS.ToAndKind;
     221             :   }
     222             : 
     223             :   friend raw_ostream &operator<<(raw_ostream &OS, const Update &U) {
     224             :     OS << (U.getKind() == UpdateKind::Insert ? "Insert " : "Delete ");
     225             :     U.getFrom()->printAsOperand(OS, false);
     226             :     OS << " -> ";
     227             :     U.getTo()->printAsOperand(OS, false);
     228             :     return OS;
     229             :   }
     230             : };
     231             : 
     232             : template <typename DomTreeT>
     233             : void ApplyUpdates(DomTreeT &DT,
     234             :                   ArrayRef<typename DomTreeT::UpdateType> Updates);
     235             : 
     236             : template <typename DomTreeT>
     237             : bool Verify(const DomTreeT &DT, typename DomTreeT::VerificationLevel VL);
     238             : }  // namespace DomTreeBuilder
     239             : 
     240             : /// Core dominator tree base class.
     241             : ///
     242             : /// This class is a generic template over graph nodes. It is instantiated for
     243             : /// various graphs in the LLVM IR or in the code generator.
     244             : template <typename NodeT, bool IsPostDom>
     245     3463434 : class DominatorTreeBase {
     246             :  public:
     247             :   static_assert(std::is_pointer<typename GraphTraits<NodeT *>::NodeRef>::value,
     248             :                 "Currently DominatorTreeBase supports only pointer nodes");
     249             :   using NodeType = NodeT;
     250             :   using NodePtr = NodeT *;
     251             :   using ParentPtr = decltype(std::declval<NodeT *>()->getParent());
     252             :   static_assert(std::is_pointer<ParentPtr>::value,
     253             :                 "Currently NodeT's parent must be a pointer type");
     254             :   using ParentType = typename std::remove_pointer<ParentPtr>::type;
     255             :   static constexpr bool IsPostDominator = IsPostDom;
     256             : 
     257             :   using UpdateType = DomTreeBuilder::Update<NodePtr>;
     258             :   using UpdateKind = DomTreeBuilder::UpdateKind;
     259             :   static constexpr UpdateKind Insert = UpdateKind::Insert;
     260             :   static constexpr UpdateKind Delete = UpdateKind::Delete;
     261             : 
     262             :   enum class VerificationLevel { Fast, Basic, Full };
     263             : 
     264             : protected:
     265             :   // Dominators always have a single root, postdominators can have more.
     266             :   SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
     267             : 
     268             :   using DomTreeNodeMapType =
     269             :      DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
     270             :   DomTreeNodeMapType DomTreeNodes;
     271             :   DomTreeNodeBase<NodeT> *RootNode;
     272             :   ParentPtr Parent = nullptr;
     273             : 
     274             :   mutable bool DFSInfoValid = false;
     275             :   mutable unsigned int SlowQueries = 0;
     276             : 
     277             :   friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
     278             : 
     279             :  public:
     280     3451995 :   DominatorTreeBase() {}
     281             : 
     282           0 :   DominatorTreeBase(DominatorTreeBase &&Arg)
     283             :       : Roots(std::move(Arg.Roots)),
     284           0 :         DomTreeNodes(std::move(Arg.DomTreeNodes)),
     285           0 :         RootNode(Arg.RootNode),
     286           0 :         Parent(Arg.Parent),
     287           0 :         DFSInfoValid(Arg.DFSInfoValid),
     288           0 :         SlowQueries(Arg.SlowQueries) {
     289             :     Arg.wipe();
     290           0 :   }
     291             : 
     292           0 :   DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
     293             :     Roots = std::move(RHS.Roots);
     294           0 :     DomTreeNodes = std::move(RHS.DomTreeNodes);
     295           0 :     RootNode = RHS.RootNode;
     296           0 :     Parent = RHS.Parent;
     297           0 :     DFSInfoValid = RHS.DFSInfoValid;
     298           0 :     SlowQueries = RHS.SlowQueries;
     299             :     RHS.wipe();
     300           0 :     return *this;
     301             :   }
     302             : 
     303             :   DominatorTreeBase(const DominatorTreeBase &) = delete;
     304             :   DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
     305             : 
     306             :   /// getRoots - Return the root blocks of the current CFG.  This may include
     307             :   /// multiple blocks if we are computing post dominators.  For forward
     308             :   /// dominators, this will always be a single block (the entry node).
     309             :   ///
     310           0 :   const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
     311             : 
     312             :   /// isPostDominator - Returns true if analysis based of postdoms
     313             :   ///
     314           0 :   bool isPostDominator() const { return IsPostDominator; }
     315             : 
     316             :   /// compare - Return false if the other dominator tree base matches this
     317             :   /// dominator tree base. Otherwise return true.
     318         662 :   bool compare(const DominatorTreeBase &Other) const {
     319         662 :     if (Parent != Other.Parent) return true;
     320             : 
     321         662 :     if (Roots.size() != Other.Roots.size())
     322             :       return true;
     323             : 
     324         662 :     if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
     325             :       return true;
     326             : 
     327         662 :     const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
     328         662 :     if (DomTreeNodes.size() != OtherDomTreeNodes.size())
     329             :       return true;
     330             : 
     331        7859 :     for (const auto &DomTreeNode : DomTreeNodes) {
     332        6538 :       NodeT *BB = DomTreeNode.first;
     333        6538 :       typename DomTreeNodeMapType::const_iterator OI =
     334             :           OtherDomTreeNodes.find(BB);
     335        6538 :       if (OI == OtherDomTreeNodes.end())
     336           1 :         return true;
     337             : 
     338             :       DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
     339             :       DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
     340             : 
     341        6538 :       if (MyNd.compare(&OtherNd))
     342             :         return true;
     343             :     }
     344             : 
     345         660 :     return false;
     346             :   }
     347             : 
     348           0 :   void releaseMemory() { reset(); }
     349             : 
     350             :   /// getNode - return the (Post)DominatorTree node for the specified basic
     351             :   /// block.  This is the same as using operator[] on this class.  The result
     352             :   /// may (but is not required to) be null for a forward (backwards)
     353             :   /// statically unreachable block.
     354           0 :   DomTreeNodeBase<NodeT> *getNode(const NodeT *BB) const {
     355    51256685 :     auto I = DomTreeNodes.find(BB);
     356    51256685 :     if (I != DomTreeNodes.end())
     357           0 :       return I->second.get();
     358             :     return nullptr;
     359             :   }
     360             : 
     361             :   /// See getNode.
     362           0 :   DomTreeNodeBase<NodeT> *operator[](const NodeT *BB) const {
     363           0 :     return getNode(BB);
     364             :   }
     365             : 
     366             :   /// getRootNode - This returns the entry node for the CFG of the function.  If
     367             :   /// this tree represents the post-dominance relations for a function, however,
     368             :   /// this root may be a node with the block == NULL.  This is the case when
     369             :   /// there are multiple exit nodes from a particular function.  Consumers of
     370             :   /// post-dominance information must be capable of dealing with this
     371             :   /// possibility.
     372             :   ///
     373           0 :   DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
     374       10811 :   const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
     375             : 
     376             :   /// Get all nodes dominated by R, including R itself.
     377          12 :   void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
     378             :     Result.clear();
     379          12 :     const DomTreeNodeBase<NodeT> *RN = getNode(R);
     380          12 :     if (!RN)
     381           2 :       return; // If R is unreachable, it will not be present in the DOM tree.
     382             :     SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
     383          10 :     WL.push_back(RN);
     384             : 
     385          48 :     while (!WL.empty()) {
     386             :       const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
     387          38 :       Result.push_back(N->getBlock());
     388          19 :       WL.append(N->begin(), N->end());
     389             :     }
     390             :   }
     391             : 
     392             :   /// properlyDominates - Returns true iff A dominates B and A != B.
     393             :   /// Note that this is not a constant time operation!
     394             :   ///
     395           0 :   bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
     396             :                          const DomTreeNodeBase<NodeT> *B) const {
     397       23071 :     if (!A || !B)
     398             :       return false;
     399       23071 :     if (A == B)
     400             :       return false;
     401       19659 :     return dominates(A, B);
     402             :   }
     403             : 
     404             :   bool properlyDominates(const NodeT *A, const NodeT *B) const;
     405             : 
     406             :   /// isReachableFromEntry - Return true if A is dominated by the entry
     407             :   /// block of the function containing it.
     408     2991858 :   bool isReachableFromEntry(const NodeT *A) const {
     409             :     assert(!this->isPostDominator() &&
     410             :            "This is not implemented for post dominators");
     411     2991858 :     return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
     412             :   }
     413             : 
     414     2991858 :   bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
     415             : 
     416             :   /// dominates - Returns true iff A dominates B.  Note that this is not a
     417             :   /// constant time operation!
     418             :   ///
     419    11899306 :   bool dominates(const DomTreeNodeBase<NodeT> *A,
     420             :                  const DomTreeNodeBase<NodeT> *B) const {
     421             :     // A node trivially dominates itself.
     422    11899306 :     if (B == A)
     423             :       return true;
     424             : 
     425             :     // An unreachable node is dominated by anything.
     426    11899155 :     if (!isReachableFromEntry(B))
     427             :       return true;
     428             : 
     429             :     // And dominates nothing.
     430    11898997 :     if (!isReachableFromEntry(A))
     431             :       return false;
     432             : 
     433    11891265 :     if (B->getIDom() == A) return true;
     434             : 
     435    11169096 :     if (A->getIDom() == B) return false;
     436             : 
     437             :     // A can only dominate B if it is higher in the tree.
     438     6660760 :     if (A->getLevel() >= B->getLevel()) return false;
     439             : 
     440             :     // Compare the result of the tree walk and the dfs numbers, if expensive
     441             :     // checks are enabled.
     442             : #ifdef EXPENSIVE_CHECKS
     443             :     assert((!DFSInfoValid ||
     444             :             (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
     445             :            "Tree walk disagrees with dfs numbers!");
     446             : #endif
     447             : 
     448     2634050 :     if (DFSInfoValid)
     449           0 :       return B->DominatedBy(A);
     450             : 
     451             :     // If we end up with too many slow queries, just update the
     452             :     // DFS numbers on the theory that we are going to keep querying.
     453      869857 :     SlowQueries++;
     454      869857 :     if (SlowQueries > 32) {
     455       10574 :       updateDFSNumbers();
     456           0 :       return B->DominatedBy(A);
     457             :     }
     458             : 
     459      859283 :     return dominatedBySlowTreeWalk(A, B);
     460             :   }
     461             : 
     462             :   bool dominates(const NodeT *A, const NodeT *B) const;
     463             : 
     464           0 :   NodeT *getRoot() const {
     465             :     assert(this->Roots.size() == 1 && "Should always have entry node!");
     466      159675 :     return this->Roots[0];
     467             :   }
     468             : 
     469             :   /// findNearestCommonDominator - Find nearest common dominator basic block
     470             :   /// for basic block A and B. If there is no such block then return nullptr.
     471      125194 :   NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
     472             :     assert(A && B && "Pointers are not valid");
     473             :     assert(A->getParent() == B->getParent() &&
     474             :            "Two blocks are not in same function");
     475             : 
     476             :     // If either A or B is a entry block then it is nearest common dominator
     477             :     // (for forward-dominators).
     478             :     if (!isPostDominator()) {
     479      124903 :       NodeT &Entry = A->getParent()->front();
     480      124903 :       if (A == &Entry || B == &Entry)
     481             :         return &Entry;
     482             :     }
     483             : 
     484             :     DomTreeNodeBase<NodeT> *NodeA = getNode(A);
     485             :     DomTreeNodeBase<NodeT> *NodeB = getNode(B);
     486             : 
     487      116360 :     if (!NodeA || !NodeB) return nullptr;
     488             : 
     489             :     // Use level information to go up the tree until the levels match. Then
     490             :     // continue going up til we arrive at the same node.
     491     1927532 :     while (NodeA && NodeA != NodeB) {
     492      905586 :       if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
     493             : 
     494      905586 :       NodeA = NodeA->IDom;
     495             :     }
     496             : 
     497      116360 :     return NodeA ? NodeA->getBlock() : nullptr;
     498             :   }
     499             : 
     500           0 :   const NodeT *findNearestCommonDominator(const NodeT *A,
     501             :                                           const NodeT *B) const {
     502             :     // Cast away the const qualifiers here. This is ok since
     503             :     // const is re-introduced on the return type.
     504             :     return findNearestCommonDominator(const_cast<NodeT *>(A),
     505           0 :                                       const_cast<NodeT *>(B));
     506             :   }
     507             : 
     508           0 :   bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
     509        3909 :     return isPostDominator() && !A->getBlock();
     510             :   }
     511             : 
     512             :   //===--------------------------------------------------------------------===//
     513             :   // API to update (Post)DominatorTree information based on modifications to
     514             :   // the CFG...
     515             : 
     516             :   /// Inform the dominator tree about a sequence of CFG edge insertions and
     517             :   /// deletions and perform a batch update on the tree.
     518             :   ///
     519             :   /// This function should be used when there were multiple CFG updates after
     520             :   /// the last dominator tree update. It takes care of performing the updates
     521             :   /// in sync with the CFG and optimizes away the redundant operations that
     522             :   /// cancel each other.
     523             :   /// The functions expects the sequence of updates to be balanced. Eg.:
     524             :   ///  - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
     525             :   ///    logically it results in a single insertions.
     526             :   ///  - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
     527             :   ///    sense to insert the same edge twice.
     528             :   ///
     529             :   /// What's more, the functions assumes that it's safe to ask every node in the
     530             :   /// CFG about its children and inverse children. This implies that deletions
     531             :   /// of CFG edges must not delete the CFG nodes before calling this function.
     532             :   ///
     533             :   /// Batch updates should be generally faster when performing longer sequences
     534             :   /// of updates than calling insertEdge/deleteEdge manually multiple times, as
     535             :   /// it can reorder the updates and remove redundant ones internally.
     536             :   /// The batch updater is also able to detect sequences of zero and exactly one
     537             :   /// update -- it's optimized to do less work in these cases.
     538             :   ///
     539             :   /// Note that for postdominators it automatically takes care of applying
     540             :   /// updates on reverse edges internally (so there's no need to swap the
     541             :   /// From and To pointers when constructing DominatorTree::UpdateType).
     542             :   /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
     543             :   /// with the same template parameter T.
     544             :   ///
     545             :   /// \param Updates An unordered sequence of updates to perform.
     546             :   ///
     547           0 :   void applyUpdates(ArrayRef<UpdateType> Updates) {
     548       11367 :     DomTreeBuilder::ApplyUpdates(*this, Updates);
     549           0 :   }
     550             : 
     551             :   /// Inform the dominator tree about a CFG edge insertion and update the tree.
     552             :   ///
     553             :   /// This function has to be called just before or just after making the update
     554             :   /// on the actual CFG. There cannot be any other updates that the dominator
     555             :   /// tree doesn't know about.
     556             :   ///
     557             :   /// Note that for postdominators it automatically takes care of inserting
     558             :   /// a reverse edge internally (so there's no need to swap the parameters).
     559             :   ///
     560           0 :   void insertEdge(NodeT *From, NodeT *To) {
     561             :     assert(From);
     562             :     assert(To);
     563             :     assert(From->getParent() == Parent);
     564             :     assert(To->getParent() == Parent);
     565         469 :     DomTreeBuilder::InsertEdge(*this, From, To);
     566           0 :   }
     567             : 
     568             :   /// Inform the dominator tree about a CFG edge deletion and update the tree.
     569             :   ///
     570             :   /// This function has to be called just after making the update on the actual
     571             :   /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
     572             :   /// DEBUG mode. There cannot be any other updates that the
     573             :   /// dominator tree doesn't know about.
     574             :   ///
     575             :   /// Note that for postdominators it automatically takes care of deleting
     576             :   /// a reverse edge internally (so there's no need to swap the parameters).
     577             :   ///
     578           0 :   void deleteEdge(NodeT *From, NodeT *To) {
     579             :     assert(From);
     580             :     assert(To);
     581             :     assert(From->getParent() == Parent);
     582             :     assert(To->getParent() == Parent);
     583        1270 :     DomTreeBuilder::DeleteEdge(*this, From, To);
     584           0 :   }
     585             : 
     586             :   /// Add a new node to the dominator tree information.
     587             :   ///
     588             :   /// This creates a new node as a child of DomBB dominator node, linking it
     589             :   /// into the children list of the immediate dominator.
     590             :   ///
     591             :   /// \param BB New node in CFG.
     592             :   /// \param DomBB CFG node that is dominator for BB.
     593             :   /// \returns New dominator tree node that represents new CFG node.
     594             :   ///
     595       40576 :   DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
     596             :     assert(getNode(BB) == nullptr && "Block already in dominator tree!");
     597             :     DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
     598             :     assert(IDomNode && "Not immediate dominator specified for block!");
     599       40576 :     DFSInfoValid = false;
     600       81152 :     return (DomTreeNodes[BB] = IDomNode->addChild(
     601       40576 :                 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
     602             :   }
     603             : 
     604             :   /// Add a new node to the forward dominator tree and make it a new root.
     605             :   ///
     606             :   /// \param BB New node in CFG.
     607             :   /// \returns New dominator tree node that represents new CFG node.
     608             :   ///
     609           1 :   DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
     610             :     assert(getNode(BB) == nullptr && "Block already in dominator tree!");
     611             :     assert(!this->isPostDominator() &&
     612             :            "Cannot change root of post-dominator tree");
     613           1 :     DFSInfoValid = false;
     614           2 :     DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
     615             :       llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
     616           1 :     if (Roots.empty()) {
     617           0 :       addRoot(BB);
     618             :     } else {
     619             :       assert(Roots.size() == 1);
     620           1 :       NodeT *OldRoot = Roots.front();
     621             :       auto &OldNode = DomTreeNodes[OldRoot];
     622             :       OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
     623           1 :       OldNode->IDom = NewNode;
     624           1 :       OldNode->UpdateLevel();
     625           1 :       Roots[0] = BB;
     626             :     }
     627           1 :     return RootNode = NewNode;
     628             :   }
     629             : 
     630             :   /// changeImmediateDominator - This method is used to update the dominator
     631             :   /// tree information when a node's immediate dominator changes.
     632             :   ///
     633           0 :   void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
     634             :                                 DomTreeNodeBase<NodeT> *NewIDom) {
     635             :     assert(N && NewIDom && "Cannot change null node pointers!");
     636       26214 :     DFSInfoValid = false;
     637       26214 :     N->setIDom(NewIDom);
     638           0 :   }
     639             : 
     640        1518 :   void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
     641             :     changeImmediateDominator(getNode(BB), getNode(NewBB));
     642        1518 :   }
     643             : 
     644             :   /// eraseNode - Removes a node from the dominator tree. Block must not
     645             :   /// dominate any other blocks. Removes node from its immediate dominator's
     646             :   /// children list. Deletes dominator node associated with basic block BB.
     647        2350 :   void eraseNode(NodeT *BB) {
     648        4700 :     DomTreeNodeBase<NodeT> *Node = getNode(BB);
     649             :     assert(Node && "Removing node that isn't in dominator tree.");
     650             :     assert(Node->getChildren().empty() && "Node is not a leaf node.");
     651             : 
     652        2350 :     DFSInfoValid = false;
     653             : 
     654             :     // Remove node from immediate dominator's children list.
     655           0 :     DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
     656        2350 :     if (IDom) {
     657             :       const auto I = find(IDom->Children, Node);
     658             :       assert(I != IDom->Children.end() &&
     659             :              "Not in immediate dominator children set!");
     660             :       // I am no longer your child...
     661        2350 :       IDom->Children.erase(I);
     662             :     }
     663             : 
     664        2350 :     DomTreeNodes.erase(BB);
     665             : 
     666        2350 :     if (!IsPostDom) return;
     667             : 
     668             :     // Remember to update PostDominatorTree roots.
     669             :     auto RIt = llvm::find(Roots, BB);
     670           0 :     if (RIt != Roots.end()) {
     671             :       std::swap(*RIt, Roots.back());
     672             :       Roots.pop_back();
     673             :     }
     674             :   }
     675             : 
     676             :   /// splitBlock - BB is split and now it has one successor. Update dominator
     677             :   /// tree to reflect this change.
     678           0 :   void splitBlock(NodeT *NewBB) {
     679             :     if (IsPostDominator)
     680           0 :       Split<Inverse<NodeT *>>(NewBB);
     681             :     else
     682       17522 :       Split<NodeT *>(NewBB);
     683           0 :   }
     684             : 
     685             :   /// print - Convert to human readable form
     686             :   ///
     687          13 :   void print(raw_ostream &O) const {
     688          13 :     O << "=============================--------------------------------\n";
     689             :     if (IsPostDominator)
     690           2 :       O << "Inorder PostDominator Tree: ";
     691             :     else
     692          11 :       O << "Inorder Dominator Tree: ";
     693          13 :     if (!DFSInfoValid)
     694          26 :       O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
     695          13 :     O << "\n";
     696             : 
     697             :     // The postdom tree can have a null root if there are no returns.
     698          13 :     if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
     699             :     if (IsPostDominator) {
     700           2 :       O << "Roots: ";
     701          10 :       for (const NodePtr Block : Roots) {
     702           4 :         Block->printAsOperand(O, false);
     703           4 :         O << " ";
     704             :       }
     705           2 :       O << "\n";
     706             :     }
     707          13 :   }
     708             : 
     709             : public:
     710             :   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
     711             :   /// dominator tree in dfs order.
     712       11100 :   void updateDFSNumbers() const {
     713       11100 :     if (DFSInfoValid) {
     714         302 :       SlowQueries = 0;
     715         604 :       return;
     716             :     }
     717             : 
     718             :     SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
     719             :                           typename DomTreeNodeBase<NodeT>::const_iterator>,
     720             :                 32> WorkStack;
     721             : 
     722             :     const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
     723             :     assert((!Parent || ThisRoot) && "Empty constructed DomTree");
     724       10798 :     if (!ThisRoot)
     725             :       return;
     726             : 
     727             :     // Both dominators and postdominators have a single root node. In the case
     728             :     // case of PostDominatorTree, this node is a virtual root.
     729       10798 :     WorkStack.push_back({ThisRoot, ThisRoot->begin()});
     730             : 
     731             :     unsigned DFSNum = 0;
     732       10798 :     ThisRoot->DFSNumIn = DFSNum++;
     733             : 
     734     2931162 :     while (!WorkStack.empty()) {
     735     2920364 :       const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
     736     2920364 :       const auto ChildIt = WorkStack.back().second;
     737             : 
     738             :       // If we visited all of the children of this node, "recurse" back up the
     739             :       // stack setting the DFOutNum.
     740     2920364 :       if (ChildIt == Node->end()) {
     741     1465581 :         Node->DFSNumOut = DFSNum++;
     742             :         WorkStack.pop_back();
     743             :       } else {
     744             :         // Otherwise, recursively visit this child.
     745     1454783 :         const DomTreeNodeBase<NodeT> *Child = *ChildIt;
     746             :         ++WorkStack.back().second;
     747             : 
     748     1454783 :         WorkStack.push_back({Child, Child->begin()});
     749     1454783 :         Child->DFSNumIn = DFSNum++;
     750             :       }
     751             :     }
     752             : 
     753       10798 :     SlowQueries = 0;
     754       10798 :     DFSInfoValid = true;
     755             :   }
     756             : 
     757             :   /// recalculate - compute a dominator tree for the given function
     758           0 :   void recalculate(ParentType &Func) {
     759     4345032 :     Parent = &Func;
     760     2488044 :     DomTreeBuilder::Calculate(*this);
     761           0 :   }
     762             : 
     763             :   /// verify - checks if the tree is correct. There are 3 level of verification:
     764             :   ///  - Full --  verifies if the tree is correct by making sure all the
     765             :   ///             properties (including the parent and the sibling property)
     766             :   ///             hold.
     767             :   ///             Takes O(N^3) time.
     768             :   ///
     769             :   ///  - Basic -- checks if the tree is correct, but compares it to a freshly
     770             :   ///             constructed tree instead of checking the sibling property.
     771             :   ///             Takes O(N^2) time.
     772             :   ///
     773             :   ///  - Fast  -- checks basic tree structure and compares it with a freshly
     774             :   ///             constructed tree.
     775             :   ///             Takes O(N^2) time worst case, but is faster in practise (same
     776             :   ///             as tree construction).
     777           0 :   bool verify(VerificationLevel VL = VerificationLevel::Full) const {
     778         656 :     return DomTreeBuilder::Verify(*this, VL);
     779             :   }
     780             : 
     781             : protected:
     782           0 :   void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
     783             : 
     784           0 :   void reset() {
     785     6046211 :     DomTreeNodes.clear();
     786             :     Roots.clear();
     787     6046211 :     RootNode = nullptr;
     788     1695706 :     Parent = nullptr;
     789     6046211 :     DFSInfoValid = false;
     790     6046211 :     SlowQueries = 0;
     791           0 :   }
     792             : 
     793             :   // NewBB is split and now it has one successor. Update dominator tree to
     794             :   // reflect this change.
     795             :   template <class N>
     796       17522 :   void Split(typename GraphTraits<N>::NodeRef NewBB) {
     797             :     using GraphT = GraphTraits<N>;
     798             :     using NodeRef = typename GraphT::NodeRef;
     799             :     assert(std::distance(GraphT::child_begin(NewBB),
     800             :                          GraphT::child_end(NewBB)) == 1 &&
     801             :            "NewBB should have a single successor!");
     802           0 :     NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
     803             : 
     804             :     std::vector<NodeRef> PredBlocks;
     805       74010 :     for (const auto &Pred : children<Inverse<N>>(NewBB))
     806       19483 :       PredBlocks.push_back(Pred);
     807             : 
     808             :     assert(!PredBlocks.empty() && "No predblocks?");
     809             : 
     810             :     bool NewBBDominatesNewBBSucc = true;
     811       59120 :     for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
     812       43684 :       if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
     813        9804 :           isReachableFromEntry(Pred)) {
     814             :         NewBBDominatesNewBBSucc = false;
     815             :         break;
     816             :       }
     817             :     }
     818             : 
     819             :     // Find NewBB's immediate dominator and create new dominator tree node for
     820             :     // NewBB.
     821             :     NodeT *NewBBIDom = nullptr;
     822             :     unsigned i = 0;
     823       35044 :     for (i = 0; i < PredBlocks.size(); ++i)
     824       17522 :       if (isReachableFromEntry(PredBlocks[i])) {
     825       35044 :         NewBBIDom = PredBlocks[i];
     826       17522 :         break;
     827             :       }
     828             : 
     829             :     // It's possible that none of the predecessors of NewBB are reachable;
     830             :     // in that case, NewBB itself is unreachable, so nothing needs to be
     831             :     // changed.
     832       17522 :     if (!NewBBIDom) return;
     833             : 
     834       38966 :     for (i = i + 1; i < PredBlocks.size(); ++i) {
     835        1961 :       if (isReachableFromEntry(PredBlocks[i]))
     836        3912 :         NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
     837             :     }
     838             : 
     839             :     // Create the new dominator tree node... and set the idom of NewBB.
     840       17522 :     DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
     841             : 
     842             :     // If NewBB strictly dominates other blocks, then it is now the immediate
     843             :     // dominator of NewBBSucc.  Update the dominator tree as appropriate.
     844       17522 :     if (NewBBDominatesNewBBSucc) {
     845           0 :       DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
     846             :       changeImmediateDominator(NewBBSuccNode, NewBBNode);
     847             :     }
     848             :   }
     849             : 
     850             :  private:
     851           0 :   bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
     852             :                                const DomTreeNodeBase<NodeT> *B) const {
     853             :     assert(A != B);
     854             :     assert(isReachableFromEntry(B));
     855             :     assert(isReachableFromEntry(A));
     856             : 
     857             :     const DomTreeNodeBase<NodeT> *IDom;
     858     7841659 :     while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B)
     859             :       B = IDom;  // Walk up the tree
     860      859283 :     return IDom != nullptr;
     861             :   }
     862             : 
     863             :   /// Wipe this tree's state without releasing any resources.
     864             :   ///
     865             :   /// This is essentially a post-move helper only. It leaves the object in an
     866             :   /// assignable and destroyable state, but otherwise invalid.
     867           0 :   void wipe() {
     868           0 :     DomTreeNodes.clear();
     869           0 :     RootNode = nullptr;
     870           0 :     Parent = nullptr;
     871           0 :   }
     872             : };
     873             : 
     874             : template <typename T>
     875             : using DomTreeBase = DominatorTreeBase<T, false>;
     876             : 
     877             : template <typename T>
     878             : using PostDomTreeBase = DominatorTreeBase<T, true>;
     879             : 
     880             : // These two functions are declared out of line as a workaround for building
     881             : // with old (< r147295) versions of clang because of pr11642.
     882             : template <typename NodeT, bool IsPostDom>
     883    12646553 : bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
     884             :                                                     const NodeT *B) const {
     885    12646553 :   if (A == B)
     886             :     return true;
     887             : 
     888             :   // Cast away the const qualifiers here. This is ok since
     889             :   // this function doesn't actually return the values returned
     890             :   // from getNode.
     891             :   return dominates(getNode(const_cast<NodeT *>(A)),
     892    11855282 :                    getNode(const_cast<NodeT *>(B)));
     893             : }
     894             : template <typename NodeT, bool IsPostDom>
     895       44222 : bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
     896             :     const NodeT *A, const NodeT *B) const {
     897       44222 :   if (A == B)
     898             :     return false;
     899             : 
     900             :   // Cast away the const qualifiers here. This is ok since
     901             :   // this function doesn't actually return the values returned
     902             :   // from getNode.
     903             :   return dominates(getNode(const_cast<NodeT *>(A)),
     904       38070 :                    getNode(const_cast<NodeT *>(B)));
     905             : }
     906             : 
     907             : } // end namespace llvm
     908             : 
     909             : #endif // LLVM_SUPPORT_GENERICDOMTREE_H

Generated by: LCOV version 1.13