LCOV - code coverage report
Current view: top level - include/llvm/Support - GenericDomTree.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 187 262 71.4 %
Date: 2018-02-22 04:41:24 Functions: 39 212 18.4 %
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             : /// \brief Base class for the actual dominator tree node.
      54    10426557 : 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    10427856 :   DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
      70    20855712 :       : 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     7281604 :   const_iterator begin() const { return Children.begin(); }
      79    12340147 :   const_iterator end() const { return Children.end(); }
      80             : 
      81     3407579 :   NodeT *getBlock() const { return TheBB; }
      82    32106783 :   DomTreeNodeBase *getIDom() const { return IDom; }
      83    11153379 :   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    19394223 :     Children.push_back(C.get());
      90           0 :     return C;
      91             :   }
      92             : 
      93        8132 :   size_t getNumChildren() const { return Children.size(); }
      94             : 
      95           0 :   void clearAllChildren() { Children.clear(); }
      96             : 
      97        3981 :   bool compare(const DomTreeNodeBase *Other) const {
      98        3981 :     if (getNumChildren() != Other->getNumChildren())
      99             :       return true;
     100             : 
     101        3981 :     if (Level != Other->Level) return true;
     102             : 
     103             :     SmallPtrSet<const NodeT *, 4> OtherChildren;
     104        7622 :     for (const DomTreeNodeBase *I : *Other) {
     105             :       const NodeT *Nd = I->getBlock();
     106        3641 :       OtherChildren.insert(Nd);
     107             :     }
     108             : 
     109        7622 :     for (const DomTreeNodeBase *I : *this) {
     110             :       const NodeT *N = I->getBlock();
     111        3641 :       if (OtherChildren.count(N) == 0)
     112             :         return true;
     113             :     }
     114             :     return false;
     115             :   }
     116             : 
     117     1238713 :   void setIDom(DomTreeNodeBase *NewIDom) {
     118             :     assert(IDom && "No immediate dominator?");
     119     1238713 :     if (IDom == NewIDom) return;
     120             : 
     121       69950 :     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       34975 :     IDom->Children.erase(I);
     126             : 
     127             :     // Switch to new dominator
     128       34975 :     IDom = NewIDom;
     129       69950 :     IDom->Children.push_back(this);
     130             : 
     131       34975 :     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         182 :   unsigned getDFSNumIn() const { return DFSNumIn; }
     138         179 :   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     2486703 :     return this->DFSNumIn >= other->DFSNumIn &&
     145      828270 :            this->DFSNumOut <= other->DFSNumOut;
     146             :   }
     147             : 
     148      241314 :   void UpdateLevel() {
     149             :     assert(IDom);
     150      443691 :     if (Level == IDom->Level + 1) return;
     151             : 
     152       77874 :     SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
     153             : 
     154      966635 :     while (!WorkStack.empty()) {
     155             :       DomTreeNodeBase *Current = WorkStack.pop_back_val();
     156      463849 :       Current->Level = Current->IDom->Level + 1;
     157             : 
     158      888761 :       for (DomTreeNodeBase *C : *Current) {
     159             :         assert(C->IDom);
     160      424912 :         if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C);
     161             :       }
     162             :     }
     163             :   }
     164             : };
     165             : 
     166             : template <class NodeT>
     167         170 : raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) {
     168         170 :   if (Node->getBlock())
     169         156 :     Node->getBlock()->printAsOperand(O, false);
     170             :   else
     171          14 :     O << " <<exit node>>";
     172             : 
     173         680 :   O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
     174           0 :     << Node->getLevel() << "]\n";
     175             : 
     176         170 :   return O;
     177             : }
     178             : 
     179             : template <class NodeT>
     180         170 : void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O,
     181             :                   unsigned Lev) {
     182         340 :   O.indent(2 * Lev) << "[" << Lev << "] " << N;
     183             :   for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
     184             :                                                        E = N->end();
     185         317 :        I != E; ++I)
     186         147 :     PrintDomTree<NodeT>(*I, O, Lev + 1);
     187         170 : }
     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           0 :   Update(UpdateKind Kind, NodePtr From, NodePtr To)
     214      281005 :       : From(From), ToAndKind(To, Kind) {}
     215             : 
     216           0 :   UpdateKind getKind() const { return ToAndKind.getInt(); }
     217     1278394 :   NodePtr getFrom() const { return From; }
     218           0 :   NodePtr getTo() const { return ToAndKind.getPointer(); }
     219           0 :   bool operator==(const Update &RHS) const {
     220     4601644 :     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             : /// \brief 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     3131703 : 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     4518662 :   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         340 :   bool compare(const DominatorTreeBase &Other) const {
     319         340 :     if (Parent != Other.Parent) return true;
     320             : 
     321         340 :     if (Roots.size() != Other.Roots.size())
     322             :       return true;
     323             : 
     324         340 :     if (!std::is_permutation(Roots.begin(), Roots.end(), Other.Roots.begin()))
     325             :       return true;
     326             : 
     327         340 :     const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
     328         340 :     if (DomTreeNodes.size() != OtherDomTreeNodes.size())
     329             :       return true;
     330             : 
     331        4661 :     for (const auto &DomTreeNode : DomTreeNodes) {
     332        3981 :       NodeT *BB = DomTreeNode.first;
     333        3981 :       typename DomTreeNodeMapType::const_iterator OI =
     334             :           OtherDomTreeNodes.find(BB);
     335        3981 :       if (OI == OtherDomTreeNodes.end())
     336           0 :         return true;
     337             : 
     338             :       DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
     339             :       DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
     340             : 
     341        3981 :       if (MyNd.compare(&OtherNd))
     342             :         return true;
     343             :     }
     344             : 
     345         340 :     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(NodeT *BB) const {
     355    51583122 :     auto I = DomTreeNodes.find(BB);
     356    51583122 :     if (I != DomTreeNodes.end())
     357           0 :       return I->second.get();
     358             :     return nullptr;
     359             :   }
     360             : 
     361             :   /// See getNode.
     362           0 :   DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const { return getNode(BB); }
     363             : 
     364             :   /// getRootNode - This returns the entry node for the CFG of the function.  If
     365             :   /// this tree represents the post-dominance relations for a function, however,
     366             :   /// this root may be a node with the block == NULL.  This is the case when
     367             :   /// there are multiple exit nodes from a particular function.  Consumers of
     368             :   /// post-dominance information must be capable of dealing with this
     369             :   /// possibility.
     370             :   ///
     371           0 :   DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
     372       11689 :   const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
     373             : 
     374             :   /// Get all nodes dominated by R, including R itself.
     375          10 :   void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
     376             :     Result.clear();
     377          10 :     const DomTreeNodeBase<NodeT> *RN = getNode(R);
     378          10 :     if (!RN)
     379           2 :       return; // If R is unreachable, it will not be present in the DOM tree.
     380             :     SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
     381           8 :     WL.push_back(RN);
     382             : 
     383          42 :     while (!WL.empty()) {
     384             :       const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
     385          34 :       Result.push_back(N->getBlock());
     386          17 :       WL.append(N->begin(), N->end());
     387             :     }
     388             :   }
     389             : 
     390             :   /// properlyDominates - Returns true iff A dominates B and A != B.
     391             :   /// Note that this is not a constant time operation!
     392             :   ///
     393           0 :   bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
     394             :                          const DomTreeNodeBase<NodeT> *B) const {
     395       20872 :     if (!A || !B)
     396             :       return false;
     397       20872 :     if (A == B)
     398             :       return false;
     399       17578 :     return dominates(A, B);
     400             :   }
     401             : 
     402             :   bool properlyDominates(const NodeT *A, const NodeT *B) const;
     403             : 
     404             :   /// isReachableFromEntry - Return true if A is dominated by the entry
     405             :   /// block of the function containing it.
     406     2708090 :   bool isReachableFromEntry(const NodeT *A) const {
     407             :     assert(!this->isPostDominator() &&
     408             :            "This is not implemented for post dominators");
     409     2708090 :     return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
     410             :   }
     411             : 
     412     2708090 :   bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
     413             : 
     414             :   /// dominates - Returns true iff A dominates B.  Note that this is not a
     415             :   /// constant time operation!
     416             :   ///
     417    11724977 :   bool dominates(const DomTreeNodeBase<NodeT> *A,
     418             :                  const DomTreeNodeBase<NodeT> *B) const {
     419             :     // A node trivially dominates itself.
     420    11724977 :     if (B == A)
     421             :       return true;
     422             : 
     423             :     // An unreachable node is dominated by anything.
     424    11724842 :     if (!isReachableFromEntry(B))
     425             :       return true;
     426             : 
     427             :     // And dominates nothing.
     428    11724693 :     if (!isReachableFromEntry(A))
     429             :       return false;
     430             : 
     431    11717849 :     if (B->getIDom() == A) return true;
     432             : 
     433    11047095 :     if (A->getIDom() == B) return false;
     434             : 
     435             :     // A can only dominate B if it is higher in the tree.
     436     6502785 :     if (A->getLevel() >= B->getLevel()) return false;
     437             : 
     438             :     // Compare the result of the tree walk and the dfs numbers, if expensive
     439             :     // checks are enabled.
     440             : #ifdef EXPENSIVE_CHECKS
     441             :     assert((!DFSInfoValid ||
     442             :             (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
     443             :            "Tree walk disagrees with dfs numbers!");
     444             : #endif
     445             : 
     446     2598192 :     if (DFSInfoValid)
     447           0 :       return B->DominatedBy(A);
     448             : 
     449             :     // If we end up with too many slow queries, just update the
     450             :     // DFS numbers on the theory that we are going to keep querying.
     451      951194 :     SlowQueries++;
     452      951194 :     if (SlowQueries > 32) {
     453       11435 :       updateDFSNumbers();
     454           0 :       return B->DominatedBy(A);
     455             :     }
     456             : 
     457      939759 :     return dominatedBySlowTreeWalk(A, B);
     458             :   }
     459             : 
     460             :   bool dominates(const NodeT *A, const NodeT *B) const;
     461             : 
     462           0 :   NodeT *getRoot() const {
     463             :     assert(this->Roots.size() == 1 && "Should always have entry node!");
     464      146792 :     return this->Roots[0];
     465             :   }
     466             : 
     467             :   /// findNearestCommonDominator - Find nearest common dominator basic block
     468             :   /// for basic block A and B. If there is no such block then return nullptr.
     469      124393 :   NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
     470             :     assert(A && B && "Pointers are not valid");
     471             :     assert(A->getParent() == B->getParent() &&
     472             :            "Two blocks are not in same function");
     473             : 
     474             :     // If either A or B is a entry block then it is nearest common dominator
     475             :     // (for forward-dominators).
     476             :     if (!isPostDominator()) {
     477      124110 :       NodeT &Entry = A->getParent()->front();
     478      124110 :       if (A == &Entry || B == &Entry)
     479             :         return &Entry;
     480             :     }
     481             : 
     482             :     DomTreeNodeBase<NodeT> *NodeA = getNode(A);
     483             :     DomTreeNodeBase<NodeT> *NodeB = getNode(B);
     484             : 
     485      116063 :     if (!NodeA || !NodeB) return nullptr;
     486             : 
     487             :     // Use level information to go up the tree until the levels match. Then
     488             :     // continue going up til we arrive at the same node.
     489     1932677 :     while (NodeA && NodeA != NodeB) {
     490      908307 :       if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
     491             : 
     492      908307 :       NodeA = NodeA->IDom;
     493             :     }
     494             : 
     495      116063 :     return NodeA ? NodeA->getBlock() : nullptr;
     496             :   }
     497             : 
     498           0 :   const NodeT *findNearestCommonDominator(const NodeT *A,
     499             :                                           const NodeT *B) const {
     500             :     // Cast away the const qualifiers here. This is ok since
     501             :     // const is re-introduced on the return type.
     502             :     return findNearestCommonDominator(const_cast<NodeT *>(A),
     503           0 :                                       const_cast<NodeT *>(B));
     504             :   }
     505             : 
     506           0 :   bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
     507        3832 :     return isPostDominator() && !A->getBlock();
     508             :   }
     509             : 
     510             :   //===--------------------------------------------------------------------===//
     511             :   // API to update (Post)DominatorTree information based on modifications to
     512             :   // the CFG...
     513             : 
     514             :   /// Inform the dominator tree about a sequence of CFG edge insertions and
     515             :   /// deletions and perform a batch update on the tree.
     516             :   ///
     517             :   /// This function should be used when there were multiple CFG updates after
     518             :   /// the last dominator tree update. It takes care of performing the updates
     519             :   /// in sync with the CFG and optimizes away the redundant operations that
     520             :   /// cancel each other.
     521             :   /// The functions expects the sequence of updates to be balanced. Eg.:
     522             :   ///  - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
     523             :   ///    logically it results in a single insertions.
     524             :   ///  - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
     525             :   ///    sense to insert the same edge twice.
     526             :   ///
     527             :   /// What's more, the functions assumes that it's safe to ask every node in the
     528             :   /// CFG about its children and inverse children. This implies that deletions
     529             :   /// of CFG edges must not delete the CFG nodes before calling this function.
     530             :   ///
     531             :   /// Batch updates should be generally faster when performing longer sequences
     532             :   /// of updates than calling insertEdge/deleteEdge manually multiple times, as
     533             :   /// it can reorder the updates and remove redundant ones internally.
     534             :   /// The batch updater is also able to detect sequences of zero and exactly one
     535             :   /// update -- it's optimized to do less work in these cases.
     536             :   ///
     537             :   /// Note that for postdominators it automatically takes care of applying
     538             :   /// updates on reverse edges internally (so there's no need to swap the
     539             :   /// From and To pointers when constructing DominatorTree::UpdateType).
     540             :   /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
     541             :   /// with the same template parameter T.
     542             :   ///
     543             :   /// \param Updates An unordered sequence of updates to perform.
     544             :   ///
     545           0 :   void applyUpdates(ArrayRef<UpdateType> Updates) {
     546       10753 :     DomTreeBuilder::ApplyUpdates(*this, Updates);
     547           0 :   }
     548             : 
     549             :   /// Inform the dominator tree about a CFG edge insertion and update the tree.
     550             :   ///
     551             :   /// This function has to be called just before or just after making the update
     552             :   /// on the actual CFG. There cannot be any other updates that the dominator
     553             :   /// tree doesn't know about.
     554             :   ///
     555             :   /// Note that for postdominators it automatically takes care of inserting
     556             :   /// a reverse edge internally (so there's no need to swap the parameters).
     557             :   ///
     558           0 :   void insertEdge(NodeT *From, NodeT *To) {
     559             :     assert(From);
     560             :     assert(To);
     561             :     assert(From->getParent() == Parent);
     562             :     assert(To->getParent() == Parent);
     563         334 :     DomTreeBuilder::InsertEdge(*this, From, To);
     564           0 :   }
     565             : 
     566             :   /// Inform the dominator tree about a CFG edge deletion and update the tree.
     567             :   ///
     568             :   /// This function has to be called just after making the update on the actual
     569             :   /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
     570             :   /// DEBUG mode. There cannot be any other updates that the
     571             :   /// dominator tree doesn't know about.
     572             :   ///
     573             :   /// Note that for postdominators it automatically takes care of deleting
     574             :   /// a reverse edge internally (so there's no need to swap the parameters).
     575             :   ///
     576           0 :   void deleteEdge(NodeT *From, NodeT *To) {
     577             :     assert(From);
     578             :     assert(To);
     579             :     assert(From->getParent() == Parent);
     580             :     assert(To->getParent() == Parent);
     581        1235 :     DomTreeBuilder::DeleteEdge(*this, From, To);
     582           0 :   }
     583             : 
     584             :   /// Add a new node to the dominator tree information.
     585             :   ///
     586             :   /// This creates a new node as a child of DomBB dominator node, linking it
     587             :   /// into the children list of the immediate dominator.
     588             :   ///
     589             :   /// \param BB New node in CFG.
     590             :   /// \param DomBB CFG node that is dominator for BB.
     591             :   /// \returns New dominator tree node that represents new CFG node.
     592             :   ///
     593       38017 :   DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
     594             :     assert(getNode(BB) == nullptr && "Block already in dominator tree!");
     595             :     DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
     596             :     assert(IDomNode && "Not immediate dominator specified for block!");
     597       38017 :     DFSInfoValid = false;
     598       76034 :     return (DomTreeNodes[BB] = IDomNode->addChild(
     599       38017 :                 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
     600             :   }
     601             : 
     602             :   /// Add a new node to the forward dominator tree and make it a new root.
     603             :   ///
     604             :   /// \param BB New node in CFG.
     605             :   /// \returns New dominator tree node that represents new CFG node.
     606             :   ///
     607           1 :   DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
     608             :     assert(getNode(BB) == nullptr && "Block already in dominator tree!");
     609             :     assert(!this->isPostDominator() &&
     610             :            "Cannot change root of post-dominator tree");
     611           1 :     DFSInfoValid = false;
     612           2 :     DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
     613             :       llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
     614           1 :     if (Roots.empty()) {
     615           0 :       addRoot(BB);
     616             :     } else {
     617             :       assert(Roots.size() == 1);
     618           1 :       NodeT *OldRoot = Roots.front();
     619             :       auto &OldNode = DomTreeNodes[OldRoot];
     620             :       OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
     621           1 :       OldNode->IDom = NewNode;
     622           1 :       OldNode->UpdateLevel();
     623           1 :       Roots[0] = BB;
     624             :     }
     625           1 :     return RootNode = NewNode;
     626             :   }
     627             : 
     628             :   /// changeImmediateDominator - This method is used to update the dominator
     629             :   /// tree information when a node's immediate dominator changes.
     630             :   ///
     631           0 :   void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
     632             :                                 DomTreeNodeBase<NodeT> *NewIDom) {
     633             :     assert(N && NewIDom && "Cannot change null node pointers!");
     634       24835 :     DFSInfoValid = false;
     635       24835 :     N->setIDom(NewIDom);
     636           0 :   }
     637             : 
     638        1412 :   void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
     639             :     changeImmediateDominator(getNode(BB), getNode(NewBB));
     640        1412 :   }
     641             : 
     642             :   /// eraseNode - Removes a node from the dominator tree. Block must not
     643             :   /// dominate any other blocks. Removes node from its immediate dominator's
     644             :   /// children list. Deletes dominator node associated with basic block BB.
     645          88 :   void eraseNode(NodeT *BB) {
     646         176 :     DomTreeNodeBase<NodeT> *Node = getNode(BB);
     647             :     assert(Node && "Removing node that isn't in dominator tree.");
     648             :     assert(Node->getChildren().empty() && "Node is not a leaf node.");
     649             : 
     650          88 :     DFSInfoValid = false;
     651             : 
     652             :     // Remove node from immediate dominator's children list.
     653           0 :     DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
     654          88 :     if (IDom) {
     655             :       const auto I = find(IDom->Children, Node);
     656             :       assert(I != IDom->Children.end() &&
     657             :              "Not in immediate dominator children set!");
     658             :       // I am no longer your child...
     659          88 :       IDom->Children.erase(I);
     660             :     }
     661             : 
     662          88 :     DomTreeNodes.erase(BB);
     663             : 
     664          88 :     if (!IsPostDom) return;
     665             : 
     666             :     // Remember to update PostDominatorTree roots.
     667             :     auto RIt = llvm::find(Roots, BB);
     668           0 :     if (RIt != Roots.end()) {
     669             :       std::swap(*RIt, Roots.back());
     670             :       Roots.pop_back();
     671             :     }
     672             :   }
     673             : 
     674             :   /// splitBlock - BB is split and now it has one successor. Update dominator
     675             :   /// tree to reflect this change.
     676           0 :   void splitBlock(NodeT *NewBB) {
     677             :     if (IsPostDominator)
     678           0 :       Split<Inverse<NodeT *>>(NewBB);
     679             :     else
     680       16314 :       Split<NodeT *>(NewBB);
     681           0 :   }
     682             : 
     683             :   /// print - Convert to human readable form
     684             :   ///
     685           9 :   void print(raw_ostream &O) const {
     686           9 :     O << "=============================--------------------------------\n";
     687             :     if (IsPostDominator)
     688           0 :       O << "Inorder PostDominator Tree: ";
     689             :     else
     690           9 :       O << "Inorder Dominator Tree: ";
     691           9 :     if (!DFSInfoValid)
     692          18 :       O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
     693           9 :     O << "\n";
     694             : 
     695             :     // The postdom tree can have a null root if there are no returns.
     696           9 :     if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
     697             :     if (IsPostDominator) {
     698           0 :       O << "Roots: ";
     699           0 :       for (const NodePtr Block : Roots) {
     700           0 :         Block->printAsOperand(O, false);
     701           0 :         O << " ";
     702             :       }
     703           0 :       O << "\n";
     704             :     }
     705           9 :   }
     706             : 
     707             : public:
     708             :   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
     709             :   /// dominator tree in dfs order.
     710       11995 :   void updateDFSNumbers() const {
     711       11995 :     if (DFSInfoValid) {
     712         315 :       SlowQueries = 0;
     713         630 :       return;
     714             :     }
     715             : 
     716             :     SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
     717             :                           typename DomTreeNodeBase<NodeT>::const_iterator>,
     718             :                 32> WorkStack;
     719             : 
     720             :     const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
     721             :     assert((!Parent || ThisRoot) && "Empty constructed DomTree");
     722       11680 :     if (!ThisRoot)
     723             :       return;
     724             : 
     725             :     // Both dominators and postdominators have a single root node. In the case
     726             :     // case of PostDominatorTree, this node is a virtual root.
     727       11680 :     WorkStack.push_back({ThisRoot, ThisRoot->begin()});
     728             : 
     729             :     unsigned DFSNum = 0;
     730       11680 :     ThisRoot->DFSNumIn = DFSNum++;
     731             : 
     732     3626188 :     while (!WorkStack.empty()) {
     733     3614508 :       const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
     734     3614508 :       const auto ChildIt = WorkStack.back().second;
     735             : 
     736             :       // If we visited all of the children of this node, "recurse" back up the
     737             :       // stack setting the DFOutNum.
     738     3614508 :       if (ChildIt == Node->end()) {
     739     1813094 :         Node->DFSNumOut = DFSNum++;
     740             :         WorkStack.pop_back();
     741             :       } else {
     742             :         // Otherwise, recursively visit this child.
     743     1801414 :         const DomTreeNodeBase<NodeT> *Child = *ChildIt;
     744             :         ++WorkStack.back().second;
     745             : 
     746     1801414 :         WorkStack.push_back({Child, Child->begin()});
     747     1801414 :         Child->DFSNumIn = DFSNum++;
     748             :       }
     749             :     }
     750             : 
     751       11680 :     SlowQueries = 0;
     752       11680 :     DFSInfoValid = true;
     753             :   }
     754             : 
     755             :   /// recalculate - compute a dominator tree for the given function
     756           0 :   void recalculate(ParentType &Func) {
     757     3951505 :     Parent = &Func;
     758     2282354 :     DomTreeBuilder::Calculate(*this);
     759           0 :   }
     760             : 
     761             :   /// verify - checks if the tree is correct. There are 3 level of verification:
     762             :   ///  - Full --  verifies if the tree is correct by making sure all the
     763             :   ///             properties (including the parent and the sibling property)
     764             :   ///             hold.
     765             :   ///             Takes O(N^3) time.
     766             :   ///
     767             :   ///  - Basic -- checks if the tree is correct, but compares it to a freshly
     768             :   ///             constructed tree instead of checking the sibling property.
     769             :   ///             Takes O(N^2) time.
     770             :   ///
     771             :   ///  - Fast  -- checks basic tree structure and compares it with a freshly
     772             :   ///             constructed tree.
     773             :   ///             Takes O(N^2) time worst case, but is faster in practise (same
     774             :   ///             as tree construction).
     775           0 :   bool verify(VerificationLevel VL = VerificationLevel::Full) const {
     776         653 :     return DomTreeBuilder::Verify(*this, VL);
     777             :   }
     778             : 
     779             : protected:
     780           0 :   void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
     781             : 
     782           0 :   void reset() {
     783     5537756 :     DomTreeNodes.clear();
     784             :     Roots.clear();
     785     5537757 :     RootNode = nullptr;
     786     1581100 :     Parent = nullptr;
     787     5537757 :     DFSInfoValid = false;
     788     5537757 :     SlowQueries = 0;
     789           0 :   }
     790             : 
     791             :   // NewBB is split and now it has one successor. Update dominator tree to
     792             :   // reflect this change.
     793             :   template <class N>
     794       16314 :   void Split(typename GraphTraits<N>::NodeRef NewBB) {
     795             :     using GraphT = GraphTraits<N>;
     796             :     using NodeRef = typename GraphT::NodeRef;
     797             :     assert(std::distance(GraphT::child_begin(NewBB),
     798             :                          GraphT::child_end(NewBB)) == 1 &&
     799             :            "NewBB should have a single successor!");
     800           0 :     NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
     801             : 
     802             :     std::vector<NodeRef> PredBlocks;
     803       69004 :     for (const auto &Pred : children<Inverse<N>>(NewBB))
     804       18188 :       PredBlocks.push_back(Pred);
     805             : 
     806             :     assert(!PredBlocks.empty() && "No predblocks?");
     807             : 
     808             :     bool NewBBDominatesNewBBSucc = true;
     809       55123 :     for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
     810       40517 :       if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
     811        9011 :           isReachableFromEntry(Pred)) {
     812             :         NewBBDominatesNewBBSucc = false;
     813             :         break;
     814             :       }
     815             :     }
     816             : 
     817             :     // Find NewBB's immediate dominator and create new dominator tree node for
     818             :     // NewBB.
     819             :     NodeT *NewBBIDom = nullptr;
     820             :     unsigned i = 0;
     821       32628 :     for (i = 0; i < PredBlocks.size(); ++i)
     822       16314 :       if (isReachableFromEntry(PredBlocks[i])) {
     823       32628 :         NewBBIDom = PredBlocks[i];
     824       16314 :         break;
     825             :       }
     826             : 
     827             :     // It's possible that none of the predecessors of NewBB are reachable;
     828             :     // in that case, NewBB itself is unreachable, so nothing needs to be
     829             :     // changed.
     830       16314 :     if (!NewBBIDom) return;
     831             : 
     832       36376 :     for (i = i + 1; i < PredBlocks.size(); ++i) {
     833        1874 :       if (isReachableFromEntry(PredBlocks[i]))
     834        3738 :         NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
     835             :     }
     836             : 
     837             :     // Create the new dominator tree node... and set the idom of NewBB.
     838       16314 :     DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
     839             : 
     840             :     // If NewBB strictly dominates other blocks, then it is now the immediate
     841             :     // dominator of NewBBSucc.  Update the dominator tree as appropriate.
     842       16314 :     if (NewBBDominatesNewBBSucc) {
     843           0 :       DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
     844             :       changeImmediateDominator(NewBBSuccNode, NewBBNode);
     845             :     }
     846             :   }
     847             : 
     848             :  private:
     849           0 :   bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
     850             :                                const DomTreeNodeBase<NodeT> *B) const {
     851             :     assert(A != B);
     852             :     assert(isReachableFromEntry(B));
     853             :     assert(isReachableFromEntry(A));
     854             : 
     855             :     const DomTreeNodeBase<NodeT> *IDom;
     856     9109368 :     while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B)
     857             :       B = IDom;  // Walk up the tree
     858      939759 :     return IDom != nullptr;
     859             :   }
     860             : 
     861             :   /// \brief Wipe this tree's state without releasing any resources.
     862             :   ///
     863             :   /// This is essentially a post-move helper only. It leaves the object in an
     864             :   /// assignable and destroyable state, but otherwise invalid.
     865           0 :   void wipe() {
     866           0 :     DomTreeNodes.clear();
     867           0 :     RootNode = nullptr;
     868           0 :     Parent = nullptr;
     869           0 :   }
     870             : };
     871             : 
     872             : template <typename T>
     873             : using DomTreeBase = DominatorTreeBase<T, false>;
     874             : 
     875             : template <typename T>
     876             : using PostDomTreeBase = DominatorTreeBase<T, true>;
     877             : 
     878             : // These two functions are declared out of line as a workaround for building
     879             : // with old (< r147295) versions of clang because of pr11642.
     880             : template <typename NodeT, bool IsPostDom>
     881    12432251 : bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
     882             :                                                     const NodeT *B) const {
     883    12432251 :   if (A == B)
     884             :     return true;
     885             : 
     886             :   // Cast away the const qualifiers here. This is ok since
     887             :   // this function doesn't actually return the values returned
     888             :   // from getNode.
     889             :   return dominates(getNode(const_cast<NodeT *>(A)),
     890    11696190 :                    getNode(const_cast<NodeT *>(B)));
     891             : }
     892             : template <typename NodeT, bool IsPostDom>
     893       28194 : bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
     894             :     const NodeT *A, const NodeT *B) const {
     895       28194 :   if (A == B)
     896             :     return false;
     897             : 
     898             :   // Cast away the const qualifiers here. This is ok since
     899             :   // this function doesn't actually return the values returned
     900             :   // from getNode.
     901             :   return dominates(getNode(const_cast<NodeT *>(A)),
     902       23285 :                    getNode(const_cast<NodeT *>(B)));
     903             : }
     904             : 
     905             : } // end namespace llvm
     906             : 
     907             : #endif // LLVM_SUPPORT_GENERICDOMTREE_H

Generated by: LCOV version 1.13