diff options
Diffstat (limited to 'include/llvm/Support/GenericDomTree.h')
| -rw-r--r-- | include/llvm/Support/GenericDomTree.h | 444 |
1 files changed, 190 insertions, 254 deletions
diff --git a/include/llvm/Support/GenericDomTree.h b/include/llvm/Support/GenericDomTree.h index 601633d41cff5..394a45387d8ac 100644 --- a/include/llvm/Support/GenericDomTree.h +++ b/include/llvm/Support/GenericDomTree.h @@ -58,40 +58,6 @@ template <typename GT> using DominatorTreeBaseByGraphTraits = typename detail::DominatorTreeBaseTraits<GT>::type; -/// \brief Base class that other, more interesting dominator analyses -/// inherit from. -template <class NodeT> class DominatorBase { -protected: - std::vector<NodeT *> Roots; - bool IsPostDominators; - - explicit DominatorBase(bool isPostDom) - : Roots(), IsPostDominators(isPostDom) {} - - DominatorBase(DominatorBase &&Arg) - : Roots(std::move(Arg.Roots)), IsPostDominators(Arg.IsPostDominators) { - Arg.Roots.clear(); - } - - DominatorBase &operator=(DominatorBase &&RHS) { - Roots = std::move(RHS.Roots); - IsPostDominators = RHS.IsPostDominators; - RHS.Roots.clear(); - return *this; - } - -public: - /// getRoots - Return the root blocks of the current CFG. This may include - /// multiple blocks if we are computing post dominators. For forward - /// dominators, this will always be a single block (the entry node). - /// - const std::vector<NodeT *> &getRoots() const { return Roots; } - - /// isPostDominator - Returns true if analysis based of postdoms - /// - bool isPostDominator() const { return IsPostDominators; } -}; - /// \brief Base class for the actual dominator tree node. template <class NodeT> class DomTreeNodeBase { friend struct PostDominatorTree; @@ -99,12 +65,14 @@ template <class NodeT> class DomTreeNodeBase { NodeT *TheBB; DomTreeNodeBase *IDom; + unsigned Level; std::vector<DomTreeNodeBase *> Children; mutable unsigned DFSNumIn = ~0; mutable unsigned DFSNumOut = ~0; public: - DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom) : TheBB(BB), IDom(iDom) {} + DomTreeNodeBase(NodeT *BB, DomTreeNodeBase *iDom) + : TheBB(BB), IDom(iDom), Level(IDom ? IDom->Level + 1 : 0) {} using iterator = typename std::vector<DomTreeNodeBase *>::iterator; using const_iterator = @@ -117,6 +85,7 @@ template <class NodeT> class DomTreeNodeBase { NodeT *getBlock() const { return TheBB; } DomTreeNodeBase *getIDom() const { return IDom; } + unsigned getLevel() const { return Level; } const std::vector<DomTreeNodeBase *> &getChildren() const { return Children; } @@ -134,6 +103,8 @@ template <class NodeT> class DomTreeNodeBase { if (getNumChildren() != Other->getNumChildren()) return true; + if (Level != Other->Level) return true; + SmallPtrSet<const NodeT *, 4> OtherChildren; for (const DomTreeNodeBase *I : *Other) { const NodeT *Nd = I->getBlock(); @@ -150,18 +121,19 @@ template <class NodeT> class DomTreeNodeBase { void setIDom(DomTreeNodeBase *NewIDom) { assert(IDom && "No immediate dominator?"); - if (IDom != NewIDom) { - typename std::vector<DomTreeNodeBase *>::iterator I = - find(IDom->Children, this); - assert(I != IDom->Children.end() && - "Not in immediate dominator children set!"); - // I am no longer your child... - IDom->Children.erase(I); + if (IDom == NewIDom) return; - // Switch to new dominator - IDom = NewIDom; - IDom->Children.push_back(this); - } + auto I = find(IDom->Children, this); + assert(I != IDom->Children.end() && + "Not in immediate dominator children set!"); + // I am no longer your child... + IDom->Children.erase(I); + + // Switch to new dominator + IDom = NewIDom; + IDom->Children.push_back(this); + + UpdateLevel(); } /// getDFSNumIn/getDFSNumOut - These return the DFS visitation order for nodes @@ -177,6 +149,23 @@ private: return this->DFSNumIn >= other->DFSNumIn && this->DFSNumOut <= other->DFSNumOut; } + + void UpdateLevel() { + assert(IDom); + if (Level == IDom->Level + 1) return; + + SmallVector<DomTreeNodeBase *, 64> WorkStack = {this}; + + while (!WorkStack.empty()) { + DomTreeNodeBase *Current = WorkStack.pop_back_val(); + Current->Level = Current->IDom->Level + 1; + + for (DomTreeNodeBase *C : *Current) { + assert(C->IDom); + if (C->Level != C->IDom->Level + 1) WorkStack.push_back(C); + } + } + } }; template <class NodeT> @@ -186,9 +175,10 @@ raw_ostream &operator<<(raw_ostream &O, const DomTreeNodeBase<NodeT> *Node) { else O << " <<exit node>>"; - O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "}"; + O << " {" << Node->getDFSNumIn() << "," << Node->getDFSNumOut() << "} [" + << Node->getLevel() << "]\n"; - return O << "\n"; + return O; } template <class NodeT> @@ -201,40 +191,28 @@ void PrintDomTree(const DomTreeNodeBase<NodeT> *N, raw_ostream &O, PrintDomTree<NodeT>(*I, O, Lev + 1); } +namespace DomTreeBuilder { +template <class NodeT> +struct SemiNCAInfo; + // The calculate routine is provided in a separate header but referenced here. template <class FuncT, class N> void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT, FuncT &F); +// The verify function is provided in a separate header but referenced here. +template <class N> +bool Verify(const DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT); +} // namespace DomTreeBuilder + /// \brief Core dominator tree base class. /// /// This class is a generic template over graph nodes. It is instantiated for /// various graphs in the LLVM IR or in the code generator. -template <class NodeT> class DominatorTreeBase : public DominatorBase<NodeT> { - bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, - const DomTreeNodeBase<NodeT> *B) const { - assert(A != B); - assert(isReachableFromEntry(B)); - assert(isReachableFromEntry(A)); - - const DomTreeNodeBase<NodeT> *IDom; - while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B) - B = IDom; // Walk up the tree - return IDom != nullptr; - } - - /// \brief Wipe this tree's state without releasing any resources. - /// - /// This is essentially a post-move helper only. It leaves the object in an - /// assignable and destroyable state, but otherwise invalid. - void wipe() { - DomTreeNodes.clear(); - IDoms.clear(); - Vertex.clear(); - Info.clear(); - RootNode = nullptr; - } +template <class NodeT> class DominatorTreeBase { + protected: + std::vector<NodeT *> Roots; + bool IsPostDominators; -protected: using DomTreeNodeMapType = DenseMap<NodeT *, std::unique_ptr<DomTreeNodeBase<NodeT>>>; DomTreeNodeMapType DomTreeNodes; @@ -242,117 +220,30 @@ protected: mutable bool DFSInfoValid = false; mutable unsigned int SlowQueries = 0; - // Information record used during immediate dominators computation. - struct InfoRec { - unsigned DFSNum = 0; - unsigned Parent = 0; - unsigned Semi = 0; - NodeT *Label = nullptr; - - InfoRec() = default; - }; - DenseMap<NodeT *, NodeT *> IDoms; + friend struct DomTreeBuilder::SemiNCAInfo<NodeT>; + using SNCAInfoTy = DomTreeBuilder::SemiNCAInfo<NodeT>; - // Vertex - Map the DFS number to the NodeT* - std::vector<NodeT *> Vertex; - - // Info - Collection of information used during the computation of idoms. - DenseMap<NodeT *, InfoRec> Info; - - void reset() { - DomTreeNodes.clear(); - IDoms.clear(); - this->Roots.clear(); - Vertex.clear(); - RootNode = nullptr; - DFSInfoValid = false; - SlowQueries = 0; - } - - // NewBB is split and now it has one successor. Update dominator tree to - // reflect this change. - template <class N> - void Split(typename GraphTraits<N>::NodeRef NewBB) { - using GraphT = GraphTraits<N>; - using NodeRef = typename GraphT::NodeRef; - assert(std::distance(GraphT::child_begin(NewBB), - GraphT::child_end(NewBB)) == 1 && - "NewBB should have a single successor!"); - NodeRef NewBBSucc = *GraphT::child_begin(NewBB); - - std::vector<NodeRef> PredBlocks; - for (const auto &Pred : children<Inverse<N>>(NewBB)) - PredBlocks.push_back(Pred); - - assert(!PredBlocks.empty() && "No predblocks?"); - - bool NewBBDominatesNewBBSucc = true; - for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) { - if (Pred != NewBB && !dominates(NewBBSucc, Pred) && - isReachableFromEntry(Pred)) { - NewBBDominatesNewBBSucc = false; - break; - } - } - - // Find NewBB's immediate dominator and create new dominator tree node for - // NewBB. - NodeT *NewBBIDom = nullptr; - unsigned i = 0; - for (i = 0; i < PredBlocks.size(); ++i) - if (isReachableFromEntry(PredBlocks[i])) { - NewBBIDom = PredBlocks[i]; - break; - } - - // It's possible that none of the predecessors of NewBB are reachable; - // in that case, NewBB itself is unreachable, so nothing needs to be - // changed. - if (!NewBBIDom) - return; - - for (i = i + 1; i < PredBlocks.size(); ++i) { - if (isReachableFromEntry(PredBlocks[i])) - NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]); - } - - // Create the new dominator tree node... and set the idom of NewBB. - DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom); - - // If NewBB strictly dominates other blocks, then it is now the immediate - // dominator of NewBBSucc. Update the dominator tree as appropriate. - if (NewBBDominatesNewBBSucc) { - DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc); - changeImmediateDominator(NewBBSuccNode, NewBBNode); - } - } - -public: - explicit DominatorTreeBase(bool isPostDom) - : DominatorBase<NodeT>(isPostDom) {} + public: + explicit DominatorTreeBase(bool isPostDom) : IsPostDominators(isPostDom) {} DominatorTreeBase(DominatorTreeBase &&Arg) - : DominatorBase<NodeT>( - std::move(static_cast<DominatorBase<NodeT> &>(Arg))), + : Roots(std::move(Arg.Roots)), + IsPostDominators(Arg.IsPostDominators), DomTreeNodes(std::move(Arg.DomTreeNodes)), RootNode(std::move(Arg.RootNode)), DFSInfoValid(std::move(Arg.DFSInfoValid)), - SlowQueries(std::move(Arg.SlowQueries)), IDoms(std::move(Arg.IDoms)), - Vertex(std::move(Arg.Vertex)), Info(std::move(Arg.Info)) { + SlowQueries(std::move(Arg.SlowQueries)) { Arg.wipe(); } DominatorTreeBase &operator=(DominatorTreeBase &&RHS) { - DominatorBase<NodeT>::operator=( - std::move(static_cast<DominatorBase<NodeT> &>(RHS))); + Roots = std::move(RHS.Roots); + IsPostDominators = RHS.IsPostDominators; DomTreeNodes = std::move(RHS.DomTreeNodes); RootNode = std::move(RHS.RootNode); DFSInfoValid = std::move(RHS.DFSInfoValid); SlowQueries = std::move(RHS.SlowQueries); - IDoms = std::move(RHS.IDoms); - Vertex = std::move(RHS.Vertex); - Info = std::move(RHS.Info); RHS.wipe(); return *this; } @@ -360,6 +251,16 @@ public: DominatorTreeBase(const DominatorTreeBase &) = delete; DominatorTreeBase &operator=(const DominatorTreeBase &) = delete; + /// getRoots - Return the root blocks of the current CFG. This may include + /// multiple blocks if we are computing post dominators. For forward + /// dominators, this will always be a single block (the entry node). + /// + const std::vector<NodeT *> &getRoots() const { return Roots; } + + /// isPostDominator - Returns true if analysis based of postdoms + /// + bool isPostDominator() const { return IsPostDominators; } + /// compare - Return false if the other dominator tree base matches this /// dominator tree base. Otherwise return true. bool compare(const DominatorTreeBase &Other) const { @@ -468,6 +369,13 @@ public: if (!isReachableFromEntry(A)) return false; + if (B->getIDom() == A) return true; + + if (A->getIDom() == B) return false; + + // A can only dominate B if it is higher in the tree. + if (A->getLevel() >= B->getLevel()) return false; + // Compare the result of the tree walk and the dfs numbers, if expensive // checks are enabled. #ifdef EXPENSIVE_CHECKS @@ -499,7 +407,7 @@ public: /// findNearestCommonDominator - Find nearest common dominator basic block /// for basic block A and B. If there is no such block then return NULL. - NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) { + NodeT *findNearestCommonDominator(NodeT *A, NodeT *B) const { assert(A->getParent() == B->getParent() && "Two blocks are not in same function"); @@ -511,54 +419,24 @@ public: return &Entry; } - // If B dominates A then B is nearest common dominator. - if (dominates(B, A)) - return B; - - // If A dominates B then A is nearest common dominator. - if (dominates(A, B)) - return A; - DomTreeNodeBase<NodeT> *NodeA = getNode(A); DomTreeNodeBase<NodeT> *NodeB = getNode(B); - // If we have DFS info, then we can avoid all allocations by just querying - // it from each IDom. Note that because we call 'dominates' twice above, we - // expect to call through this code at most 16 times in a row without - // building valid DFS information. This is important as below is a *very* - // slow tree walk. - if (DFSInfoValid) { - DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); - while (IDomA) { - if (NodeB->DominatedBy(IDomA)) - return IDomA->getBlock(); - IDomA = IDomA->getIDom(); - } - return nullptr; - } - - // Collect NodeA dominators set. - SmallPtrSet<DomTreeNodeBase<NodeT> *, 16> NodeADoms; - NodeADoms.insert(NodeA); - DomTreeNodeBase<NodeT> *IDomA = NodeA->getIDom(); - while (IDomA) { - NodeADoms.insert(IDomA); - IDomA = IDomA->getIDom(); - } + if (!NodeA || !NodeB) return nullptr; - // Walk NodeB immediate dominators chain and find common dominator node. - DomTreeNodeBase<NodeT> *IDomB = NodeB->getIDom(); - while (IDomB) { - if (NodeADoms.count(IDomB) != 0) - return IDomB->getBlock(); + // Use level information to go up the tree until the levels match. Then + // continue going up til we arrive at the same node. + while (NodeA && NodeA != NodeB) { + if (NodeA->getLevel() < NodeB->getLevel()) std::swap(NodeA, NodeB); - IDomB = IDomB->getIDom(); + NodeA = NodeA->IDom; } - return nullptr; + return NodeA ? NodeA->getBlock() : nullptr; } - const NodeT *findNearestCommonDominator(const NodeT *A, const NodeT *B) { + const NodeT *findNearestCommonDominator(const NodeT *A, + const NodeT *B) const { // Cast away the const qualifiers here. This is ok since // const is re-introduced on the return type. return findNearestCommonDominator(const_cast<NodeT *>(A), @@ -597,7 +475,6 @@ public: assert(!this->isPostDominator() && "Cannot change root of post-dominator tree"); DFSInfoValid = false; - auto &Roots = DominatorBase<NodeT>::Roots; DomTreeNodeBase<NodeT> *NewNode = (DomTreeNodes[BB] = llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, nullptr)).get(); if (Roots.empty()) { @@ -605,8 +482,10 @@ public: } else { assert(Roots.size() == 1); NodeT *OldRoot = Roots.front(); - DomTreeNodes[OldRoot] = - NewNode->addChild(std::move(DomTreeNodes[OldRoot])); + auto &OldNode = DomTreeNodes[OldRoot]; + OldNode = NewNode->addChild(std::move(DomTreeNodes[OldRoot])); + OldNode->IDom = NewNode; + OldNode->UpdateLevel(); Roots[0] = BB; } return RootNode = NewNode; @@ -673,45 +552,6 @@ public: if (getRootNode()) PrintDomTree<NodeT>(getRootNode(), O, 1); } -protected: - template <class GraphT> - friend typename GraphT::NodeRef - Eval(DominatorTreeBaseByGraphTraits<GraphT> &DT, typename GraphT::NodeRef V, - unsigned LastLinked); - - template <class GraphT> - friend unsigned ReverseDFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT, - typename GraphT::NodeRef V, unsigned N); - - template <class GraphT> - friend unsigned DFSPass(DominatorTreeBaseByGraphTraits<GraphT> &DT, - typename GraphT::NodeRef V, unsigned N); - - template <class FuncT, class N> - friend void Calculate(DominatorTreeBaseByGraphTraits<GraphTraits<N>> &DT, - FuncT &F); - - DomTreeNodeBase<NodeT> *getNodeForBlock(NodeT *BB) { - if (DomTreeNodeBase<NodeT> *Node = getNode(BB)) - return Node; - - // Haven't calculated this node yet? Get or calculate the node for the - // immediate dominator. - NodeT *IDom = getIDom(BB); - - assert(IDom || DomTreeNodes[nullptr]); - DomTreeNodeBase<NodeT> *IDomNode = getNodeForBlock(IDom); - - // Add a new tree node for this NodeT, and link it as a child of - // IDomNode - return (DomTreeNodes[BB] = IDomNode->addChild( - llvm::make_unique<DomTreeNodeBase<NodeT>>(BB, IDomNode))).get(); - } - - NodeT *getIDom(NodeT *BB) const { return IDoms.lookup(BB); } - - void addRoot(NodeT *BB) { this->Roots.push_back(BB); } - public: /// updateDFSNumbers - Assign In and Out numbers to the nodes while walking /// dominator tree in dfs order. @@ -767,23 +607,119 @@ public: template <class FT> void recalculate(FT &F) { using TraitsTy = GraphTraits<FT *>; reset(); - Vertex.push_back(nullptr); if (!this->IsPostDominators) { // Initialize root NodeT *entry = TraitsTy::getEntryNode(&F); addRoot(entry); - Calculate<FT, NodeT *>(*this, F); + DomTreeBuilder::Calculate<FT, NodeT *>(*this, F); } else { // Initialize the roots list for (auto *Node : nodes(&F)) if (TraitsTy::child_begin(Node) == TraitsTy::child_end(Node)) addRoot(Node); - Calculate<FT, Inverse<NodeT *>>(*this, F); + DomTreeBuilder::Calculate<FT, Inverse<NodeT *>>(*this, F); } } + + /// verify - check parent and sibling property + bool verify() const { + return this->isPostDominator() + ? DomTreeBuilder::Verify<Inverse<NodeT *>>(*this) + : DomTreeBuilder::Verify<NodeT *>(*this); + } + + protected: + void addRoot(NodeT *BB) { this->Roots.push_back(BB); } + + void reset() { + DomTreeNodes.clear(); + this->Roots.clear(); + RootNode = nullptr; + DFSInfoValid = false; + SlowQueries = 0; + } + + // NewBB is split and now it has one successor. Update dominator tree to + // reflect this change. + template <class N> + void Split(typename GraphTraits<N>::NodeRef NewBB) { + using GraphT = GraphTraits<N>; + using NodeRef = typename GraphT::NodeRef; + assert(std::distance(GraphT::child_begin(NewBB), + GraphT::child_end(NewBB)) == 1 && + "NewBB should have a single successor!"); + NodeRef NewBBSucc = *GraphT::child_begin(NewBB); + + std::vector<NodeRef> PredBlocks; + for (const auto &Pred : children<Inverse<N>>(NewBB)) + PredBlocks.push_back(Pred); + + assert(!PredBlocks.empty() && "No predblocks?"); + + bool NewBBDominatesNewBBSucc = true; + for (const auto &Pred : children<Inverse<N>>(NewBBSucc)) { + if (Pred != NewBB && !dominates(NewBBSucc, Pred) && + isReachableFromEntry(Pred)) { + NewBBDominatesNewBBSucc = false; + break; + } + } + + // Find NewBB's immediate dominator and create new dominator tree node for + // NewBB. + NodeT *NewBBIDom = nullptr; + unsigned i = 0; + for (i = 0; i < PredBlocks.size(); ++i) + if (isReachableFromEntry(PredBlocks[i])) { + NewBBIDom = PredBlocks[i]; + break; + } + + // It's possible that none of the predecessors of NewBB are reachable; + // in that case, NewBB itself is unreachable, so nothing needs to be + // changed. + if (!NewBBIDom) return; + + for (i = i + 1; i < PredBlocks.size(); ++i) { + if (isReachableFromEntry(PredBlocks[i])) + NewBBIDom = findNearestCommonDominator(NewBBIDom, PredBlocks[i]); + } + + // Create the new dominator tree node... and set the idom of NewBB. + DomTreeNodeBase<NodeT> *NewBBNode = addNewBlock(NewBB, NewBBIDom); + + // If NewBB strictly dominates other blocks, then it is now the immediate + // dominator of NewBBSucc. Update the dominator tree as appropriate. + if (NewBBDominatesNewBBSucc) { + DomTreeNodeBase<NodeT> *NewBBSuccNode = getNode(NewBBSucc); + changeImmediateDominator(NewBBSuccNode, NewBBNode); + } + } + + private: + bool dominatedBySlowTreeWalk(const DomTreeNodeBase<NodeT> *A, + const DomTreeNodeBase<NodeT> *B) const { + assert(A != B); + assert(isReachableFromEntry(B)); + assert(isReachableFromEntry(A)); + + const DomTreeNodeBase<NodeT> *IDom; + while ((IDom = B->getIDom()) != nullptr && IDom != A && IDom != B) + B = IDom; // Walk up the tree + return IDom != nullptr; + } + + /// \brief Wipe this tree's state without releasing any resources. + /// + /// This is essentially a post-move helper only. It leaves the object in an + /// assignable and destroyable state, but otherwise invalid. + void wipe() { + DomTreeNodes.clear(); + RootNode = nullptr; + } }; // These two functions are declared out of line as a workaround for building |