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

Generated by: LCOV version 1.13