LCOV - code coverage report
Current view: top level - include/llvm/Support - GenericDomTree.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 229 298 76.8 %
Date: 2017-09-14 15:23:50 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    17150252 : template <class NodeT> class DomTreeNodeBase {
      55             :   friend struct 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     8576390 :   DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom)
      70    17152780 :       : 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     3404050 :   iterator begin() { return Children.begin(); }
      77     4215938 :   iterator end() { return Children.end(); }
      78     6574498 :   const_iterator begin() const { return Children.begin(); }
      79    11226212 :   const_iterator end() const { return Children.end(); }
      80             : 
      81     2129596 :   NodeT *getBlock() const { return TheBB; }
      82    28895573 :   DomTreeNodeBase *getIDom() const { return IDom; }
      83    12872475 :   unsigned getLevel() const { return Level; }
      84             : 
      85      450214 :   const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; }
      86             : 
      87           0 :   std::unique_ptr<DomTreeNodeBase> addChild(
      88             :       std::unique_ptr<DomTreeNodeBase> C) {
      89    15743811 :     Children.push_back(C.get());
      90     5247937 :     return C;
      91             :   }
      92             : 
      93         892 :   size_t getNumChildren() const { return Children.size(); }
      94             : 
      95           0 :   void clearAllChildren() { Children.clear(); }
      96             : 
      97         363 :   bool compare(const DomTreeNodeBase *Other) const {
      98         726 :     if (getNumChildren() != Other->getNumChildren())
      99             :       return true;
     100             : 
     101         363 :     if (Level != Other->Level) return true;
     102             : 
     103         363 :     SmallPtrSet<const NodeT *, 4> OtherChildren;
     104        1765 :     for (const DomTreeNodeBase *I : *Other) {
     105         313 :       const NodeT *Nd = I->getBlock();
     106         313 :       OtherChildren.insert(Nd);
     107             :     }
     108             : 
     109        1765 :     for (const DomTreeNodeBase *I : *this) {
     110         313 :       const NodeT *N = I->getBlock();
     111         313 :       if (OtherChildren.count(N) == 0)
     112             :         return true;
     113             :     }
     114             :     return false;
     115             :   }
     116             : 
     117      236580 :   void setIDom(DomTreeNodeBase *NewIDom) {
     118             :     assert(IDom && "No immediate dominator?");
     119      236580 :     if (IDom == NewIDom) return;
     120             : 
     121       23474 :     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       35211 :     IDom->Children.erase(I);
     126             : 
     127             :     // Switch to new dominator
     128       11737 :     IDom = NewIDom;
     129       23474 :     IDom->Children.push_back(this);
     130             : 
     131       11737 :     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         170 :   unsigned getDFSNumIn() const { return DFSNumIn; }
     138         170 :   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     2356891 :     return this->DFSNumIn >= other->DFSNumIn &&
     145      788364 :            this->DFSNumOut <= other->DFSNumOut;
     146             :   }
     147             : 
     148       73349 :   void UpdateLevel() {
     149             :     assert(IDom);
     150      133007 :     if (Level == IDom->Level + 1) return;
     151             : 
     152       41073 :     SmallVector<DomTreeNodeBase *, 64> WorkStack = {this};
     153             : 
     154      252863 :     while (!WorkStack.empty()) {
     155      119586 :       DomTreeNodeBase *Current = WorkStack.pop_back_val();
     156      119586 :       Current->Level = Current->IDom->Level + 1;
     157             : 
     158      584239 :       for (DomTreeNodeBase *C : *Current) {
     159             :         assert(C->IDom);
     160      105895 :         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        1020 :   O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} ["
     174         340 :     << 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         170 :   for (typename DomTreeNodeBase<NodeT>::const_iterator I = N->begin(),
     184         170 :                                                        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       64620 :       : From(From), ToAndKind(To, Kind) {}
     215             : 
     216      194110 :   UpdateKind getKind() const { return ToAndKind.getInt(); }
     217      101550 :   NodePtr getFrom() const { return From; }
     218      330396 :   NodePtr getTo() const { return ToAndKind.getPointer(); }
     219           0 :   bool operator==(const Update &RHS) const {
     220          19 :     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);
     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     3955088 : 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             :  protected:
     263             :   // Dominators always have a single root, postdominators can have more.
     264             :   SmallVector<NodeT *, IsPostDom ? 4 : 1> Roots;
     265             : 
     266             :   using DomTreeNodeMapType =
     267             :      DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>;
     268             :   DomTreeNodeMapType DomTreeNodes;
     269             :   DomTreeNodeBase<NodeT> *RootNode;
     270             :   ParentPtr Parent = nullptr;
     271             : 
     272             :   mutable bool DFSInfoValid = false;
     273             :   mutable unsigned int SlowQueries = 0;
     274             : 
     275             :   friend struct DomTreeBuilder::SemiNCAInfo<DominatorTreeBase>;
     276             : 
     277             :  public:
     278     3945642 :   DominatorTreeBase() {}
     279             : 
     280           0 :   DominatorTreeBase(DominatorTreeBase &&Arg)
     281           0 :       : Roots(std::move(Arg.Roots)),
     282           0 :         DomTreeNodes(std::move(Arg.DomTreeNodes)),
     283           0 :         RootNode(Arg.RootNode),
     284           0 :         Parent(Arg.Parent),
     285           0 :         DFSInfoValid(Arg.DFSInfoValid),
     286           0 :         SlowQueries(Arg.SlowQueries) {
     287           0 :     Arg.wipe();
     288           0 :   }
     289             : 
     290           0 :   DominatorTreeBase &operator=(DominatorTreeBase &&RHS) {
     291           0 :     Roots = std::move(RHS.Roots);
     292           0 :     DomTreeNodes = std::move(RHS.DomTreeNodes);
     293           0 :     RootNode = RHS.RootNode;
     294           0 :     Parent = RHS.Parent;
     295           0 :     DFSInfoValid = RHS.DFSInfoValid;
     296           0 :     SlowQueries = RHS.SlowQueries;
     297           0 :     RHS.wipe();
     298           0 :     return *this;
     299             :   }
     300             : 
     301             :   DominatorTreeBase(const DominatorTreeBase &) = delete;
     302             :   DominatorTreeBase &operator=(const DominatorTreeBase &) = delete;
     303             : 
     304             :   /// getRoots - Return the root blocks of the current CFG.  This may include
     305             :   /// multiple blocks if we are computing post dominators.  For forward
     306             :   /// dominators, this will always be a single block (the entry node).
     307             :   ///
     308           0 :   const SmallVectorImpl<NodeT *> &getRoots() const { return Roots; }
     309             : 
     310             :   /// isPostDominator - Returns true if analysis based of postdoms
     311             :   ///
     312           0 :   bool isPostDominator() const { return IsPostDominator; }
     313             : 
     314             :   /// compare - Return false if the other dominator tree base matches this
     315             :   /// dominator tree base. Otherwise return true.
     316          47 :   bool compare(const DominatorTreeBase &Other) const {
     317          47 :     if (Parent != Other.Parent) return true;
     318             : 
     319          47 :     const DomTreeNodeMapType &OtherDomTreeNodes = Other.DomTreeNodes;
     320         141 :     if (DomTreeNodes.size() != OtherDomTreeNodes.size())
     321             :       return true;
     322             : 
     323          94 :     for (const auto &DomTreeNode : DomTreeNodes) {
     324         351 :       NodeT *BB = DomTreeNode.first;
     325         351 :       typename DomTreeNodeMapType::const_iterator OI =
     326             :           OtherDomTreeNodes.find(BB);
     327         351 :       if (OI == OtherDomTreeNodes.end())
     328           0 :         return true;
     329             : 
     330         702 :       DomTreeNodeBase<NodeT> &MyNd = *DomTreeNode.second;
     331         702 :       DomTreeNodeBase<NodeT> &OtherNd = *OI->second;
     332             : 
     333         351 :       if (MyNd.compare(&OtherNd))
     334             :         return true;
     335             :     }
     336             : 
     337          47 :     return false;
     338             :   }
     339             : 
     340     1351775 :   void releaseMemory() { reset(); }
     341             : 
     342             :   /// getNode - return the (Post)DominatorTree node for the specified basic
     343             :   /// block.  This is the same as using operator[] on this class.  The result
     344             :   /// may (but is not required to) be null for a forward (backwards)
     345             :   /// statically unreachable block.
     346           0 :   DomTreeNodeBase<NodeT> *getNode(NodeT *BB) const {
     347    39970166 :     auto I = DomTreeNodes.find(BB);
     348    79940332 :     if (I != DomTreeNodes.end())
     349    67014402 :       return I->second.get();
     350             :     return nullptr;
     351             :   }
     352             : 
     353             :   /// See getNode.
     354      102706 :   DomTreeNodeBase<NodeT> *operator[](NodeT *BB) const { return getNode(BB); }
     355             : 
     356             :   /// getRootNode - This returns the entry node for the CFG of the function.  If
     357             :   /// this tree represents the post-dominance relations for a function, however,
     358             :   /// this root may be a node with the block == NULL.  This is the case when
     359             :   /// there are multiple exit nodes from a particular function.  Consumers of
     360             :   /// post-dominance information must be capable of dealing with this
     361             :   /// possibility.
     362             :   ///
     363           0 :   DomTreeNodeBase<NodeT> *getRootNode() { return RootNode; }
     364       10302 :   const DomTreeNodeBase<NodeT> *getRootNode() const { return RootNode; }
     365             : 
     366             :   /// Get all nodes dominated by R, including R itself.
     367           4 :   void getDescendants(NodeT *R, SmallVectorImpl<NodeT *> &Result) const {
     368           4 :     Result.clear();
     369           4 :     const DomTreeNodeBase<NodeT> *RN = getNode(R);
     370           4 :     if (!RN)
     371           2 :       return; // If R is unreachable, it will not be present in the DOM tree.
     372           4 :     SmallVector<const DomTreeNodeBase<NodeT> *, 8> WL;
     373           2 :     WL.push_back(RN);
     374             : 
     375          12 :     while (!WL.empty()) {
     376           5 :       const DomTreeNodeBase<NodeT> *N = WL.pop_back_val();
     377          10 :       Result.push_back(N->getBlock());
     378          10 :       WL.append(N->begin(), N->end());
     379             :     }
     380             :   }
     381             : 
     382             :   /// properlyDominates - Returns true iff A dominates B and A != B.
     383             :   /// Note that this is not a constant time operation!
     384             :   ///
     385           0 :   bool properlyDominates(const DomTreeNodeBase<NodeT> *A,
     386             :                          const DomTreeNodeBase<NodeT> *B) const {
     387       20195 :     if (!A || !B)
     388             :       return false;
     389       20195 :     if (A == B)
     390             :       return false;
     391       17013 :     return dominates(A, B);
     392             :   }
     393             : 
     394             :   bool properlyDominates(const NodeT *A, const NodeT *B) const;
     395             : 
     396             :   /// isReachableFromEntry - Return true if A is dominated by the entry
     397             :   /// block of the function containing it.
     398     2149761 :   bool isReachableFromEntry(const NodeT *A) const {
     399             :     assert(!this->isPostDominator() &&
     400             :            "This is not implemented for post dominators");
     401     4299522 :     return isReachableFromEntry(getNode(const_cast<NodeT *>(A)));
     402             :   }
     403             : 
     404     2149761 :   bool isReachableFromEntry(const DomTreeNodeBase<NodeT> *A) const { return A; }
     405             : 
     406             :   /// dominates - Returns true iff A dominates B.  Note that this is not a
     407             :   /// constant time operation!
     408             :   ///
     409    10934728 :   bool dominates(const DomTreeNodeBase<NodeT> *A,
     410             :                  const DomTreeNodeBase<NodeT> *B) const {
     411             :     // A node trivially dominates itself.
     412    10934728 :     if (B == A)
     413             :       return true;
     414             : 
     415             :     // An unreachable node is dominated by anything.
     416    10934593 :     if (!isReachableFromEntry(B))
     417             :       return true;
     418             : 
     419             :     // And dominates nothing.
     420    10934455 :     if (!isReachableFromEntry(A))
     421             :       return false;
     422             : 
     423    10927881 :     if (B->getIDom() == A) return true;
     424             : 
     425    10341447 :     if (A->getIDom() == B) return false;
     426             : 
     427             :     // A can only dominate B if it is higher in the tree.
     428    11944878 :     if (A->getLevel() >= B->getLevel()) return false;
     429             : 
     430             :     // Compare the result of the tree walk and the dfs numbers, if expensive
     431             :     // checks are enabled.
     432             : #ifdef EXPENSIVE_CHECKS
     433             :     assert((!DFSInfoValid ||
     434             :             (dominatedBySlowTreeWalk(A, B) == B->DominatedBy(A))) &&
     435             :            "Tree walk disagrees with dfs numbers!");
     436             : #endif
     437             : 
     438     2325150 :     if (DFSInfoValid)
     439           0 :       return B->DominatedBy(A);
     440             : 
     441             :     // If we end up with too many slow queries, just update the
     442             :     // DFS numbers on the theory that we are going to keep querying.
     443      766613 :     SlowQueries++;
     444      766613 :     if (SlowQueries > 32) {
     445        9990 :       updateDFSNumbers();
     446           0 :       return B->DominatedBy(A);
     447             :     }
     448             : 
     449      756623 :     return dominatedBySlowTreeWalk(A, B);
     450             :   }
     451             : 
     452             :   bool dominates(const NodeT *A, const NodeT *B) const;
     453             : 
     454           0 :   NodeT *getRoot() const {
     455             :     assert(this->Roots.size() == 1 && "Should always have entry node!");
     456      280086 :     return this->Roots[0];
     457             :   }
     458             : 
     459             :   /// findNearestCommonDominator - Find nearest common dominator basic block
     460             :   /// for basic block A and B. If there is no such block then return nullptr.
     461       42463 :   NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const {
     462             :     assert(A && B && "Pointers are not valid");
     463             :     assert(A->getParent() == B->getParent() &&
     464             :            "Two blocks are not in same function");
     465             : 
     466             :     // If either A or B is a entry block then it is nearest common dominator
     467             :     // (for forward-dominators).
     468       42463 :     if (!isPostDominator()) {
     469       79536 :       NodeT &Entry = A->getParent()->front();
     470       39768 :       if (A == &Entry || B == &Entry)
     471             :         return &Entry;
     472             :     }
     473             : 
     474       35112 :     DomTreeNodeBase<NodeT> *NodeA = getNode(A);
     475       35112 :     DomTreeNodeBase<NodeT> *NodeB = getNode(B);
     476             : 
     477       35112 :     if (!NodeA || !NodeB) return nullptr;
     478             : 
     479             :     // Use level information to go up the tree until the levels match. Then
     480             :     // continue going up til we arrive at the same node.
     481      455568 :     while (NodeA && NodeA != NodeB) {
     482      630684 :       if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB);
     483             : 
     484      210228 :       NodeA = NodeA->IDom;
     485             :     }
     486             : 
     487       70224 :     return NodeA ? NodeA->getBlock() : nullptr;
     488             :   }
     489             : 
     490           0 :   const NodeT *findNearestCommonDominator(const NodeT *A,
     491             :                                           const NodeT *B) const {
     492             :     // Cast away the const qualifiers here. This is ok since
     493             :     // const is re-introduced on the return type.
     494             :     return findNearestCommonDominator(const_cast<NodeT *>(A),
     495           0 :                                       const_cast<NodeT *>(B));
     496             :   }
     497             : 
     498           0 :   bool isVirtualRoot(const DomTreeNodeBase<NodeT> *A) const {
     499        6584 :     return isPostDominator() && !A->getBlock();
     500             :   }
     501             : 
     502             :   //===--------------------------------------------------------------------===//
     503             :   // API to update (Post)DominatorTree information based on modifications to
     504             :   // the CFG...
     505             : 
     506             :   /// Inform the dominator tree about a sequence of CFG edge insertions and
     507             :   /// deletions and perform a batch update on the tree.
     508             :   ///
     509             :   /// This function should be used when there were multiple CFG updates after
     510             :   /// the last dominator tree update. It takes care of performing the updates
     511             :   /// in sync with the CFG and optimizes away the redundant operations that
     512             :   /// cancel each other.
     513             :   /// The functions expects the sequence of updates to be balanced. Eg.:
     514             :   ///  - {{Insert, A, B}, {Delete, A, B}, {Insert, A, B}} is fine, because
     515             :   ///    logically it results in a single insertions.
     516             :   ///  - {{Insert, A, B}, {Insert, A, B}} is invalid, because it doesn't make
     517             :   ///    sense to insert the same edge twice.
     518             :   ///
     519             :   /// What's more, the functions assumes that it's safe to ask every node in the
     520             :   /// CFG about its children and inverse children. This implies that deletions
     521             :   /// of CFG edges must not delete the CFG nodes before calling this function.
     522             :   ///
     523             :   /// Batch updates should be generally faster when performing longer sequences
     524             :   /// of updates than calling insertEdge/deleteEdge manually multiple times, as
     525             :   /// they can reorder the updates and remove redundant ones internally.
     526             :   ///
     527             :   /// Note that for postdominators it automatically takes care of applying
     528             :   /// updates on reverse edges internally (so there's no need to swap the
     529             :   /// From and To pointers when constructing DominatorTree::UpdateType).
     530             :   /// The type of updates is the same for DomTreeBase<T> and PostDomTreeBase<T>
     531             :   /// with the same template parameter T.
     532             :   ///
     533             :   /// \param Updates An unordered sequence of updates to perform.
     534             :   ///
     535           0 :   void applyUpdates(ArrayRef<UpdateType> Updates) {
     536        5406 :     DomTreeBuilder::ApplyUpdates(*this, Updates);
     537           0 :   }
     538             : 
     539             :   /// Inform the dominator tree about a CFG edge insertion and update the tree.
     540             :   ///
     541             :   /// This function has to be called just before or just after making the update
     542             :   /// on the actual CFG. There cannot be any other updates that the dominator
     543             :   /// tree doesn't know about.
     544             :   ///
     545             :   /// Note that for postdominators it automatically takes care of inserting
     546             :   /// a reverse edge internally (so there's no need to swap the parameters).
     547             :   ///
     548           0 :   void insertEdge(NodeT *From, NodeT *To) {
     549             :     assert(From);
     550             :     assert(To);
     551             :     assert(From->getParent() == Parent);
     552             :     assert(To->getParent() == Parent);
     553         414 :     DomTreeBuilder::InsertEdge(*this, From, To);
     554           0 :   }
     555             : 
     556             :   /// Inform the dominator tree about a CFG edge deletion and update the tree.
     557             :   ///
     558             :   /// This function has to be called just after making the update on the actual
     559             :   /// CFG. An internal functions checks if the edge doesn't exist in the CFG in
     560             :   /// DEBUG mode. There cannot be any other updates that the
     561             :   /// dominator tree doesn't know about.
     562             :   ///
     563             :   /// Note that for postdominators it automatically takes care of deleting
     564             :   /// a reverse edge internally (so there's no need to swap the parameters).
     565             :   ///
     566           0 :   void deleteEdge(NodeT *From, NodeT *To) {
     567             :     assert(From);
     568             :     assert(To);
     569             :     assert(From->getParent() == Parent);
     570             :     assert(To->getParent() == Parent);
     571        1180 :     DomTreeBuilder::DeleteEdge(*this, From, To);
     572           0 :   }
     573             : 
     574             :   /// Add a new node to the dominator tree information.
     575             :   ///
     576             :   /// This creates a new node as a child of DomBB dominator node, linking it
     577             :   /// into the children list of the immediate dominator.
     578             :   ///
     579             :   /// \param BB New node in CFG.
     580             :   /// \param DomBB CFG node that is dominator for BB.
     581             :   /// \returns New dominator tree node that represents new CFG node.
     582             :   ///
     583       32503 :   DomTreeNodeBase<NodeT> *addNewBlock(NodeT *BB, NodeT *DomBB) {
     584             :     assert(getNode(BB) == nullptr && "Block already in dominator tree!");
     585       32503 :     DomTreeNodeBase<NodeT> *IDomNode = getNode(DomBB);
     586             :     assert(IDomNode && "Not immediate dominator specified for block!");
     587       32503 :     DFSInfoValid = false;
     588      195018 :     return (DomTreeNodes[BB] = IDomNode->addChild(
     589       65006 :                 llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get();
     590             :   }
     591             : 
     592             :   /// Add a new node to the forward dominator tree and make it a new root.
     593             :   ///
     594             :   /// \param BB New node in CFG.
     595             :   /// \returns New dominator tree node that represents new CFG node.
     596             :   ///
     597           1 :   DomTreeNodeBase<NodeT> *setNewRoot(NodeT *BB) {
     598             :     assert(getNode(BB) == nullptr && "Block already in dominator tree!");
     599             :     assert(!this->isPostDominator() &&
     600             :            "Cannot change root of post-dominator tree");
     601           1 :     DFSInfoValid = false;
     602           5 :     DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] =
     603             :       llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get();
     604           1 :     if (Roots.empty()) {
     605           0 :       addRoot(BB);
     606             :     } else {
     607             :       assert(Roots.size() == 1);
     608           2 :       NodeT *OldRoot = Roots.front();
     609           2 :       auto &OldNode = DomTreeNodes[OldRoot];
     610           7 :       OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot]));
     611           1 :       OldNode->IDom = NewNode;
     612           1 :       OldNode->UpdateLevel();
     613           2 :       Roots[0] = BB;
     614             :     }
     615           1 :     return RootNode = NewNode;
     616             :   }
     617             : 
     618             :   /// changeImmediateDominator - This method is used to update the dominator
     619             :   /// tree information when a node's immediate dominator changes.
     620             :   ///
     621           0 :   void changeImmediateDominator(DomTreeNodeBase<NodeT> *N,
     622             :                                 DomTreeNodeBase<NodeT> *NewIDom) {
     623             :     assert(N && NewIDom && "Cannot change null node pointers!");
     624       21146 :     DFSInfoValid = false;
     625       21146 :     N->setIDom(NewIDom);
     626           0 :   }
     627             : 
     628        1301 :   void changeImmediateDominator(NodeT *BB, NodeT *NewBB) {
     629        3903 :     changeImmediateDominator(getNode(BB), getNode(NewBB));
     630        1301 :   }
     631             : 
     632             :   /// eraseNode - Removes a node from the dominator tree. Block must not
     633             :   /// dominate any other blocks. Removes node from its immediate dominator's
     634             :   /// children list. Deletes dominator node associated with basic block BB.
     635          85 :   void eraseNode(NodeT *BB) {
     636         170 :     DomTreeNodeBase<NodeT> *Node = getNode(BB);
     637             :     assert(Node && "Removing node that isn't in dominator tree.");
     638             :     assert(Node->getChildren().empty() && "Node is not a leaf node.");
     639             : 
     640             :     // Remove node from immediate dominator's children list.
     641         170 :     DomTreeNodeBase<NodeT> *IDom = Node->getIDom();
     642          85 :     if (IDom) {
     643          85 :       typename std::vector<DomTreeNodeBase<NodeT> *>::iterator I =
     644          85 :           find(IDom->Children, Node);
     645             :       assert(I != IDom->Children.end() &&
     646             :              "Not in immediate dominator children set!");
     647             :       // I am no longer your child...
     648         255 :       IDom->Children.erase(I);
     649             :     }
     650             : 
     651          85 :     DomTreeNodes.erase(BB);
     652             : 
     653          85 :     if (!IsPostDom) return;
     654             : 
     655             :     // Remember to update PostDominatorTree roots.
     656           0 :     auto RIt = llvm::find(Roots, BB);
     657           0 :     if (RIt != Roots.end()) {
     658           0 :       std::swap(*RIt, Roots.back());
     659           0 :       Roots.pop_back();
     660             :     }
     661             :   }
     662             : 
     663             :   /// splitBlock - BB is split and now it has one successor. Update dominator
     664             :   /// tree to reflect this change.
     665           0 :   void splitBlock(NodeT *NewBB) {
     666             :     if (IsPostDominator)
     667           0 :       Split<Inverse<NodeT *>>(NewBB);
     668             :     else
     669       12850 :       Split<NodeT *>(NewBB);
     670           0 :   }
     671             : 
     672             :   /// print - Convert to human readable form
     673             :   ///
     674           9 :   void print(raw_ostream &O) const {
     675           9 :     O << "=============================--------------------------------\n";
     676             :     if (IsPostDominator)
     677           0 :       O << "Inorder PostDominator Tree: ";
     678             :     else
     679           9 :       O << "Inorder Dominator Tree: ";
     680           9 :     if (!DFSInfoValid)
     681          18 :       O << "DFSNumbers invalid: " << SlowQueries << " slow queries.";
     682           9 :     O << "\n";
     683             : 
     684             :     // The postdom tree can have a null root if there are no returns.
     685           9 :     if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1);
     686             :     if (IsPostDominator) {
     687           0 :       O << "Roots: ";
     688           0 :       for (const NodePtr Block : Roots) {
     689           0 :         Block->printAsOperand(O, false);
     690           0 :         O << " ";
     691             :       }
     692           0 :       O << "\n";
     693             :     }
     694           9 :   }
     695             : 
     696             : public:
     697             :   /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking
     698             :   /// dominator tree in dfs order.
     699       10512 :   void updateDFSNumbers() const {
     700       10512 :     if (DFSInfoValid) {
     701         307 :       SlowQueries = 0;
     702         614 :       return;
     703             :     }
     704             : 
     705       10205 :     unsigned DFSNum = 0;
     706             : 
     707             :     SmallVector<std::pair<const DomTreeNodeBase<NodeT> *,
     708             :                           typename DomTreeNodeBase<NodeT>::const_iterator>,
     709       20410 :                 32> WorkStack;
     710             : 
     711       10205 :     const DomTreeNodeBase<NodeT> *ThisRoot = getRootNode();
     712             : 
     713       10205 :     if (!ThisRoot)
     714             :       return;
     715             : 
     716             :     // Even in the case of multiple exits that form the post dominator root
     717             :     // nodes, do not iterate over all exits, but start from the virtual root
     718             :     // node. Otherwise bbs, that are not post dominated by any exit but by the
     719             :     // virtual root node, will never be assigned a DFS number.
     720       30615 :     WorkStack.push_back(std::make_pair(ThisRoot, ThisRoot->begin()));
     721       10205 :     ThisRoot->DFSNumIn = DFSNum++;
     722             : 
     723     3330136 :     while (!WorkStack.empty()) {
     724     6639862 :       const DomTreeNodeBase<NodeT> *Node = WorkStack.back().first;
     725     3319931 :       typename DomTreeNodeBase<NodeT>::const_iterator ChildIt =
     726     3319931 :           WorkStack.back().second;
     727             : 
     728             :       // If we visited all of the children of this node, "recurse" back up the
     729             :       // stack setting the DFOutNum.
     730     6639862 :       if (ChildIt == Node->end()) {
     731     1665068 :         Node->DFSNumOut = DFSNum++;
     732             :         WorkStack.pop_back();
     733             :       } else {
     734             :         // Otherwise, recursively visit this child.
     735     1654863 :         const DomTreeNodeBase<NodeT> *Child = *ChildIt;
     736     4964589 :         ++WorkStack.back().second;
     737             : 
     738     4964589 :         WorkStack.push_back(std::make_pair(Child, Child->begin()));
     739     1654863 :         Child->DFSNumIn = DFSNum++;
     740             :       }
     741             :     }
     742             : 
     743       10205 :     SlowQueries = 0;
     744       10205 :     DFSInfoValid = true;
     745             :   }
     746             : 
     747             :   /// recalculate - compute a dominator tree for the given function
     748           0 :   void recalculate(ParentType &Func) {
     749     3319039 :     Parent = &Func;
     750     3319039 :     DomTreeBuilder::Calculate(*this);
     751           0 :   }
     752             : 
     753             :   /// verify - check parent and sibling property
     754         575 :   bool verify() const { return DomTreeBuilder::Verify(*this); }
     755             : 
     756             :  protected:
     757           0 :   void addRoot(NodeT *BB) { this->Roots.push_back(BB); }
     758             : 
     759           0 :   void reset() {
     760     4673315 :     DomTreeNodes.clear();
     761     9346630 :     Roots.clear();
     762     4673315 :     RootNode = nullptr;
     763     1351775 :     Parent = nullptr;
     764     4673315 :     DFSInfoValid = false;
     765     4673315 :     SlowQueries = 0;
     766           0 :   }
     767             : 
     768             :   // NewBB is split and now it has one successor. Update dominator tree to
     769             :   // reflect this change.
     770             :   template <class N>
     771       12850 :   void Split(typename GraphTraits<N>::NodeRef NewBB) {
     772             :     using GraphT = GraphTraits<N>;
     773             :     using NodeRef = typename GraphT::NodeRef;
     774             :     assert(std::distance(GraphT::child_begin(NewBB),
     775             :                          GraphT::child_end(NewBB)) == 1 &&
     776             :            "NewBB should have a single successor!");
     777       38550 :     NodeRef NewBBSucc = *GraphT::child_begin(NewBB);
     778             : 
     779       25700 :     std::vector<NodeRef> PredBlocks;
     780       67438 :     for (const auto &Pred : children<Inverse<N>>(NewBB))
     781       14444 :       PredBlocks.push_back(Pred);
     782             : 
     783             :     assert(!PredBlocks.empty() && "No predblocks?");
     784             : 
     785       12850 :     bool NewBBDominatesNewBBSucc = true;
     786       79223 :     for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) {
     787       33268 :       if (Pred != NewBB && !dominates(NewBBSucc, Pred) &&
     788        8621 :           isReachableFromEntry(Pred)) {
     789             :         NewBBDominatesNewBBSucc = false;
     790             :         break;
     791             :       }
     792             :     }
     793             : 
     794             :     // Find NewBB's immediate dominator and create new dominator tree node for
     795             :     // NewBB.
     796       12850 :     NodeT *NewBBIDom = nullptr;
     797       12850 :     unsigned i = 0;
     798       25700 :     for (i = 0; i < PredBlocks.size(); ++i)
     799       25700 :       if (isReachableFromEntry(PredBlocks[i])) {
     800       25700 :         NewBBIDom = PredBlocks[i];
     801       12850 :         break;
     802             :       }
     803             : 
     804             :     // It's possible that none of the predecessors of NewBB are reachable;
     805             :     // in that case, NewBB itself is unreachable, so nothing needs to be
     806             :     // changed.
     807       12850 :     if (!NewBBIDom) return;
     808             : 
     809       28888 :     for (i = i + 1; i < PredBlocks.size(); ++i) {
     810        3188 :       if (isReachableFromEntry(PredBlocks[i]))
     811        3180 :         NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]);
     812             :     }
     813             : 
     814             :     // Create the new dominator tree node... and set the idom of NewBB.
     815       12850 :     DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom);
     816             : 
     817             :     // If NewBB strictly dominates other blocks, then it is now the immediate
     818             :     // dominator of NewBBSucc.  Update the dominator tree as appropriate.
     819       12850 :     if (NewBBDominatesNewBBSucc) {
     820        8458 :       DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc);
     821           0 :       changeImmediateDominator(NewBBSuccNode, NewBBNode);
     822             :     }
     823             :   }
     824             : 
     825             :  private:
     826           0 :   bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A,
     827             :                                const DomTreeNodeBase<NodeT> *B) const {
     828             :     assert(A != B);
     829             :     assert(isReachableFromEntry(B));
     830             :     assert(isReachableFromEntry(A));
     831             : 
     832             :     const DomTreeNodeBase<NodeT> *IDom;
     833     7996643 :     while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B)
     834             :       B = IDom;  // Walk up the tree
     835      756623 :     return IDom != nullptr;
     836             :   }
     837             : 
     838             :   /// \brief Wipe this tree's state without releasing any resources.
     839             :   ///
     840             :   /// This is essentially a post-move helper only. It leaves the object in an
     841             :   /// assignable and destroyable state, but otherwise invalid.
     842           0 :   void wipe() {
     843           0 :     DomTreeNodes.clear();
     844           0 :     RootNode = nullptr;
     845           0 :     Parent = nullptr;
     846           0 :   }
     847             : };
     848             : 
     849             : template <typename T>
     850             : using DomTreeBase = DominatorTreeBase<T, false>;
     851             : 
     852             : template <typename T>
     853             : using PostDomTreeBase = DominatorTreeBase<T, true>;
     854             : 
     855             : // These two functions are declared out of line as a workaround for building
     856             : // with old (< r147295) versions of clang because of pr11642.
     857             : template <typename NodeT, bool IsPostDom>
     858    11616757 : bool DominatorTreeBase<NodeT, IsPostDom>::dominates(const NodeT *A,
     859             :                                                     const NodeT *B) const {
     860    11616757 :   if (A == B)
     861             :     return true;
     862             : 
     863             :   // Cast away the const qualifiers here. This is ok since
     864             :   // this function doesn't actually return the values returned
     865             :   // from getNode.
     866    10909201 :   return dominates(getNode(const_cast<NodeT *>(A)),
     867    21818402 :                    getNode(const_cast<NodeT *>(B)));
     868             : }
     869             : template <typename NodeT, bool IsPostDom>
     870       24804 : bool DominatorTreeBase<NodeT, IsPostDom>::properlyDominates(
     871             :     const NodeT *A, const NodeT *B) const {
     872       24804 :   if (A == B)
     873             :     return false;
     874             : 
     875             :   // Cast away the const qualifiers here. This is ok since
     876             :   // this function doesn't actually return the values returned
     877             :   // from getNode.
     878       20504 :   return dominates(getNode(const_cast<NodeT *>(A)),
     879       41008 :                    getNode(const_cast<NodeT *>(B)));
     880             : }
     881             : 
     882             : } // end namespace llvm
     883             : 
     884             : #endif // LLVM_SUPPORT_GENERICDOMTREE_H

Generated by: LCOV version 1.13